Ready Queue 혹은 메인 메모리 안에 여러 개의 프로세스가 기다리고 있을 때, 지금 실행 중인 프로세스가 끝나면 어떤 프로세스에게 다음 서비스를 받게 할 것인지 결정하는 작업
어떤 프로세스가 현재 실행중임에도 강제로 쫓아내고 새로운 프로세스를 실행시키는 스케줄링 방식
현재 실행 중인 프로세스가 끝나거나 새로운 인터럽트가 발생하기 전에는 새로운 프로세스를 실행시킬 수 없는 스케줄링 방식
스케줄링의 효율적인 정도를 측정하는 척도
먼저 도착한 프로세스가 먼저 CPU를 점유하는 방식
매우 단순하고 공평하며 많이 사용되지만 항상 효율적이지는 않다.
시간이 가장 오래 걸리는 작업이 제일 먼저 실행된다면 다른 작업들은 시간이 훨씬 짧을지라도 꼼짝없이 기다려야 한다.
가장 짧은 프로세스가 제일 먼저 실행되는 방식이다.
그 어떤 방식보다도 평균 대기시간이 제일 짧은 방식이다.
하지만 SJF 방식은 매우 비현실적이다. 왜냐하면 현실적으로 각 프로세스가 CPU를 얼마나 사용하는지를 알 수 없기 때문이다. 따라서 각 프로세스의 점유 시간을 예측해야 하는데, 이는 상당한 Overhead를 발생시킨다.
즉, 문맥 전환이 일어날 때마다 모든 프로세스의 점유 시간을 예측해야 하므로 Overhead가 매우 크게 발생한다.
선점 버전은 SRTF(Shortest Remaining Time First)라고 별도로 부르며, 새 프로세스가 도착할 때마다 남은 실행 시간이 가장 짧은 프로세스를 선택한다. 현재 진행 중인 프로세스보다 더 짧은 프로세스가 있다면 갈아끼울 수 있고, (SRTF, 선점) 현재 진행 중인 프로세스가 제일 빨리 끝난다면 갈아끼우지 않는다. (SJF, 비선점)
우선순위 (Priority)가 제일 높은 프로세스를 제일 먼저 실행하는 알고리즘이다. 일반적으로 우선순위는 정수로 나타내며, 숫자가 낮을수록 우선순위가 높음을 의미한다.
우선순위는 크게 내부 요인, 외부 요인으로 나눠서 결정할 수 있다.
Priority Scheduling은 Starvation (기아) 현상이 발생할 수 있다.
Starvation 현상은 aging을 통해 해결할 수 있는데, aging이란 너무 오래 기다리는 프로세스는 그 우선순위를 조금씩 올려주는 방식이다. 따라서 오래 기다릴수록 우선순위가 조금씩 높아져서 언젠가는 수행될 수 있게 된다.
Round-Robin이란 마치 원 모양으로 모든 프로세스가 돌아가며 수행되는 방식이며 주로 시분할 시스템에서 많이 사용된다.
전체 시간을 일정하게 나눈 후, 각 시간마다 서로 다른 프로세스를 할당하는 방식이다. 즉, 일정 시간 동안 하나의 프로세스가 수행되고, 그 다음 똑같은 시간 동안 또 다른 프로세스 수행되는 방식이다. 이렇게 모든 프로세스가 한번씩 수행되고 마지막 프로세스가 끝나면 다시 처음 프로세스부터 다시 시작된다.
다시 처음 프로세스부터 다시 시작하는 이유는 프로세스를 일정 시간 만큼만 수행하는 것이지, 이 프로세스가 끝날 때까지 계속 수행하는 것이 아니기 때문이다. 프로세스가 끝나는지 여부와 상관 없이 일정 시간이 지나면 무조건 다음 프로세스로 넘어가게 된다.
이때 여러 개로 나뉘어진 일정 시간을 시간 양자 (Time Slice 혹은 Time Quantum)라고 한다.
Round-Robin은 일정 시간이 지나야지만 다음 프로세스가 수행되므로 선점 방식이다.
Round Robin 방식은 Time quantum의 크기에 따라 그 작동 방식이 크게 달라진다. 만약 각각의 Time Quantum이 무한대라면 FCFS 방식과 동일하게 동작한다. 또한 Time Quantum이 매우 작아질수록 컨텍스트 스위칭이 극도로 빈번해져, 마치 모든 프로세스가 동시에 실행되는 것처럼 보이게 된다 (동시 실행 효과, Concurrency).
프로세스는 사실 여러 가지의 종류가 있다.
서로 다른 종류의 프로세스를 하나의 Ready Queue (Single Ready Queue)에 몰아넣는 것은 비효율적이라는 판단에서 등장한 것이 바로 Multilevel Queue Scheduling 즉, 프로세스의 각 종류에 맞춰서 여러개의 Queue (Several Separate Queues)를 두는 방식이다.
각각의 Queue에 우선순위를 부여하여 Queue의 실행 순서를 정할 수 있다. 그림에서의 Highest Priority ~ Lowest Priority가 바로 Queue 우선순위이다. 또는 CPU 시간을 각 Queue에 차등배분 할 수도 있고, 각 Queue마다 서로 다른 Scheduling 정책을 반영할 수도 있다.
Multilevel Queue Scheduling과 같이 여러 개의 Queue를 사용한다는 점은 맞지만, 하나의 Queue에서 할당된 시간이 지났는데도 프로세스가 끝나지 않는다면, 그 프로세스는 우선순위가 낮은 다른 Queue로 이동한다는 차이가 있다.
그림에서 보듯이 모든 프로세스는 하나의 입구로 진입한다. 하나의 프로세스가 Queue에서 할당된 시간(Time Quantum)을 초과하면 Time Out이 발생하고, 해당 프로세스는 우선순위가 낮은 다른 Queue로 이동한다. 만약 Starvation (기아) 상태가 발생한다면 우선순위가 낮은 Queue 안에 있는 Process를 우선순위가 높은 Queue로 옮길 수 있다.
