선입 선처리(FCFS: First-Come First-Served) 스케줄링

프로세스들이 도착한 순서대로 CPU를 할당하는 방법이다. 도착 순서란, 프로세스들이 준비 대기열(Ready Queue)에 연결되는 순서를 말한다. 비선점형이다.

프로세스 CPU버스트 시간
P1 30
P2 3
P3 6 
P1->P2->P3 순서로 실행 될 때

평균 대기 시간 = (0 + 30 + 33) / 3 = 21
평균 응답 시간 = (30 + 33 + 39) / 3 = 34

P2->P3->P1 순서로 실행 될 때

평균 대기 시간 = (0 + 3 + 9) / 3 = 4
평균 응답 시간 = (3 + 9 + 39) / 3 = 17

이 처럼 먼저 온 프로세스가 뒤에 온 프로세스에 영향을 많이 주는데 이런 현상을 호위 효과(Convoy Effect) 라고 한다.

최단 작업 우선(SJF: Shortest Job First)

준비 대기열에 존재하는 프로세스들을 도착한 순서대로 처리하는 것이 아니라, 이들 중 CPU버스트가 가장 짧은 프로세스에게 CPU를 먼저 할당하는 전략이다. SPN(Shortest Process Next)라 부르기도 한다. 비선점형이다.

무조건 P2->P3->P1로 실행

평균 대기 시간 = (0 + 3 + 9) / 3 = 4
평균 응답 시간 = (3 + 9 + 39) / 3 = 17

그러나, 계산 위주의 긴 프로세스에게 CPU가 할당된 상태에서 다수의 입출력 위주 짧은 프로세스들이 도착한다면 FCFS에서와 마찬가지로 호위 효과 가 나타날 수 있다. 또한 CPU가 짧은 프로세스에게 할당된 상태에서 짧은 프로세스만 지속적으로 도착한다면, 상대적으로 긴 프로세스는 계속해서 지연되는 단점이 있는데 이를 기아상태(Starvation) 라고한다.

최단 잔여 시간 우선(SRTF : Shortest Remaining Time First)

SJF스케줄링의 단점을 보완하기 위해, 준비 대기열에 새로운 프로세스가 도착하면, 현재 진행 중인 프로세스의 잔여 실행 시간과 새로운 프로세스의 CPU버스트 시간을 비교하여 새 프로세스의 실행 시간이 더 짧으면 CPU를 강제 회수하여 새로운 프로세스에게 할당하는 선점형 스케줄링 전략이다.

프로세스 도착 시간 CPU 버스트 시간
P1 0 30
P2 1 15
P3 2 10 
SRTF 평균 대기 시간 = (25 + 10 + 0) / 3 = 11.7

CPU나 입출력 장치의 이용률 저하 현상 발생을 억제할 수 있으나, 기아 상태 발생 가능성은 더 높인다.

최고 응답률 우선(HRRF : Highest Response Ratio First)

각 프로세스의 응답률을 계산하여 응답률이 가장 큰 프로세스를 먼저 처리한다.

응답률 = (준비 큐 대기 시간 + CPU 버스트 시간) / (CPU 버스트 시간) = 1 + ((준비 큐 대기 시간) / (CPU 버스트 시간))

CPU버스트 시간에 대한 준비 대기열 대기 시간이 상대적으로 클수록 응답률이 높아져 CPU스케줄링 우선 순위가 높아진다. 만약 대기 시간이 동일하다면 즉, 동일 시각에 도착한 프로세스들에게는 CPU버스트 시간이 짧을수록 응답률이 높아져 SJF나 SRTF와 동일한 스케줄링이 적용된다. HRN(Highest Response Next)라고 하기도 한다. 선점형이나 비선점형 중 어느 형태로도 운영이 가능하다.

라운드 로빈(RR: Round Robin) 스케줄링

RR은 전형적인 선점형 스케줄링전략으로, 모든 프로세스에게 동일한 최대 CPU 점유 시간 즉, 타임 권텀을 설정하고 처리중인 프로세스의 CPU실행 시간이 타임 퀀텀을 초과하면 CPU를 강제로 회수하여 다음 프로세스에게 할당하는 방식이다. 현대 대부분의 시분할 운영체제에서 채택한 방식이다.

RR스케줄링 전략에서 적절한 타임 퀀텀의 설정은 매우 중요하다. 만약 타임 퀀텀을 아주 작게 설정하면 CPU할당이 교체될 때마다 일어나는 프로세스 문맥 교환 횟수가 증가하여 시스템 부담을 증가시키고, 이는 전체적인 처리율의 감소로 이어진다. 또한 타임 퀀텀을 늘리는 것도 평균응답시간이 늘어난다.

다단계 큐(MQ : Multi-level Queue)

multi-level queue

박스 하나는 큐를 나타내고 맨위의 큐가 우선순위가 가장 높고 순서대로 순위가 낮아진다.

다단계 피드백 큐(MFQ : Multi-level Feedback Queue) 스케줄링

MQ스케줄링을 변형하였다. 프로세스는 진행 상황에따라 대화형일 수 있고, 계산 위주일 수도 있는데,

  • 실행 중인 프로세스가 해당 큐의 타임 퀀텀을 소진하지 못하고 입출력 등으로 CPU를 자진 반납하면, 이 프로세스는 입출력 성향이 강해진 것으로 인식하여 입출력 쪽으로 한 단계 높은 준비 큐로 이동시킨다.

  • 반대로, 실행 중인 프로세스가 주어진 타임 퀀텀을 모두 소진한 후 CPU를 강제로 회수당하면, 이 프로세스는 계산 성향이 강해진 것으로 인식하여 이 프로세스를 입출력 성향 기준 한 단계 낮은 준비 큐로 이동시킨다.