[운영체제 03] 스케줄링 알고리즘

목차

1. 스케줄링 성능 평가 기준
2. FCFS 스케줄링
3. SJF 스케줄링
4. SRT 스케줄링
5. RR 스케줄링
6. HRN 스케줄링
7. 다단계 피드백 큐 스케줄링

스케줄링 성능 평가 기준

1. 평균 대기시간(Average waiting time)
   • 각 프로세스가 수행이 완료될 때까지 준비 큐에서 기다리는 시간의 합의 평균값
2. 평균 반환시간(Average turnaround time)
   • 각 프로세스가 생성된 시점(여기서는 준비 큐에 들어온 시점과 동일한 것으로 가정)부터 수행이 완료된 시점까지의 소요시간의 평균값

FCFS 스케줄링

• 비선점 방법이자 스케줄링 알고리즘 중 가장 간단한 기법이다.
• 프로세스는 준비 큐에서 도착순서에 따라 디스패치되며, 일단 한 프로세스가 CPU를 차지하면 그 프로세스의 수행이 완료된 후에 그 다음 프로세스가 CPU 차지하고 수행된다.
• 겉보기에는 공정하지만, 짧은 작업이 긴 작업을 기다리게 되기도 하고 중요한 프로세스가 나중에 수행될 수 있는 불합리함이 있어 대화식 시스템에 부적합하다
• 최근 시스템에서 FCFS 스케줄링은 주요 방법이 아니라 다른 방법과 결합하여 쓰이고 있다.

예제

4개의 프로세스가 다음과 같은 실행시간을 가지고 있다고 가정해보자. 4개의 프로세스 A, B, C, D가 거의 동시에 입력되었다면, FCFS 스케줄링 알고리즘의 수행결과는 다음과 같다.

프로세스	A	B	C	D
CPU 사이클	6	3	1	4
대기시간	0	6	9	10
반환시간	6	9	10	14

SJF(Shortest Job First) 스케줄링

• 준비 큐에서 기다리는 프로세스 중 실행시간이 가장 짧다고 예상된 것을 먼저 디스패치하여 실행하는 비선점 스케줄링 알고리즘이다.
• 일괄처리 환경에서 구현이 쉽고 알고리즘으로 실행할 프로세스의 CPU 소요시간이 미리 주어진다.

예제 1

4개의 프로세스가 동시에 입려되어 모두 준비 큐에 들어 있고 예상한 프로세스 각각의 실행시간은 다음과 같다.

프로세스	A	B	C	D
CPU 사이클	6	3	1	4

SJF 스케줄링 알고리즘은 4개의 프로세스를 분석한 후 실행시간이 가장 짧은 것부터 실행하기 때문에 다음과 같은 실행결과를 도출한다.

예제 2

이번에는 4개의 프로세스가 1단위의 CPU 사이클 시간의 차이를 두고 연속적으로 입력되는 경우를 가정해본다.

도착시간	0	1	2	3
프로세스	A	B	C	D
CPU 사이클	6	3	1	4
대기시간	0	6	4	7
반환시간	6	9	5	11

먼저 도착한 A가 먼저 실행된다. 그동안 B, C, D가 차례로 도착하고 B, C, D 프로세스를 분석해 실행시간이 가장 짧은 C -> B -> D 순서로 실행한다.

SRT(Shortest Remaining Time) 스케줄링

• SJF 알고리즘의 선점(preemptive) 알고리즘 버전으로, 새로 들어오는 프로세스를 포함하여 실행이 끝날때까지 남은 시간 추정치가 가장 짧은 프로세스를 먼저 디스패치하여 실행한다.
• 대화형 운영체제에 유용하다.
• SRT가 SJF보다 평균 대기시간이나 평균 반환시간에서 효율적이다.
• SRT는 실행되는 각 작업의 실행시간을 추적하여 각 프로세스가 서비스를 받은 시간이 기록되어야 하며 때로는 선점을 위한 문맥 교환되 해야 하므로 SJF보다 오버헤드가 더 크다.
• SRT는 빠르지만 일반적인 운영체제에서는 그러한 장점이 문맥교환에 요구되는 시간을 고려하여 평가되어야 한다.

예제 1

4개의 프로세스가 1단위의 CPU 사이클 시간의 차이를 두고 연속적으로 입력되는 경우를 가정해본다.

도착시간	0	1	2	3
프로세스	A	B	C	D
CPU 사이클	6	3	1	4

새로운 프로세스가 도착할 때마다 [n번째 프로세스의 남은 시간 추정치]와 [n+1번째 프로세스들의 시간 추정치]를 비교하여 추정치가 가장 짧은 프로세를 먼저 디스패치하여 실행

프로세스	A	B	C	D
대기시간	8	1	0	2
반환시간	14	4	1	6

RR(Round Robin) 스케줄링

• 대화형 시스템에서 사용되는 선점 스케줄링 방식이다.
• 프로세스가 도착한 순서대로 프로세스를 디스패치하지만 정해진 시간 할당량에 의해 실행을 제한한다.
• 시간 할당량을 매 프로세스에 주고 할당된 시간 안에 완료하지 못한 프로세스는 준비 큐의 맨 뒤에 배치되도록 하여 CPU 독접하지 않고 공평하게 이용이 가능하다.

예제

다음과 같이 4개의 프로세스가 주어지고 시간 할당량은 3이라고 가장하자.

도착시간	0	1	2	3
프로세스	A	B	C	D
CPU 사이클	6	3	1	4

모든 프로세스가 시간할당량 3만큼의 시간을 부여받고 완료하지 못한 프로세스는 준비 큐의 맨 뒤로 배치하여 순서를 기다린다.

프로세스	A	B	C	D
대기시간	7	2	4	7
반환시간	14	5	5	11

HRN(Highest Response Ratio Next) 스케줄링

• 준비 큐에서 기다리는 프로세스 중 응답비율이 가장 큰 것을 먼저 디스패치하여 실행하는 비선점 스케줄링 알고리즘
• 각 프로세스의 응답비율은 다음과 같이 계산한다. 즉, 예상 실행시간이 짧을수록, 그리고 대기시간이 길수록 응답비율이 커진다.

• SJF 스케줄링의 단점을 보완한 것으로 SJF에서는 예상 실행시간이 긴 프로세스가 먼저 들어왔더라도 이후에 실행시간이 짧은 프로세스가 계속해서 들어오면 우선순위에서 계속 밀렸다. 그러나 HRH 스케줄링은 실행시간이 긴 프로세스라 하더라도 대기시간이 길어지면 응답비율도 커져서 자기보다 실행시간이 짧은 프로세스가 들어오더라도 우선순위에서 밀리지 않을 수 있다.

예제

도착시간	0	1	2	3
프로세스	A	B	C	D
CPU 사이클	6	3	1	4

HRN 스케줄링 과정

1) A 도착 시 응답비율	(0+6)/6=1
2) B, C, D는 준비 큐에 대기
3) B, C, D 응답비율 비교	B : (5+3)/6=8/3=2.67	C : (2+2)/2=4/2=2	D : (0+1)/1=1
4) 응답비율 가장 큰 C 실행
5) C, D 응답비율 비교	C: (5+2)/2=3.5	D : (3+1)/1=4
6) 응답비율이 가장 큰 D 실행
7) C 실행

다단계 피드백 큐(Multilevel Feadback Queue) 스케줄링

• 선점 스케줄링 방식
• 입출력 중심인 프로세스와 CPU 중심인 프로세스의 특성에 따라 서로 다른 시간 할당량을 부여
• n개의 단계가 있는 경우, 각 단계마다 하나씩의 큐가 존재하며, 단계 k는 단계 k+1에 피드백을 주며, 단계가 커질수록 시간 할당량은 커지는 형태로 구성

예제

1) 처음 프로세스 도착하면 단계 1 큐에 들어간다.

2) 해당 큐의 시간 할당량 만큼 도착한 순서대로 프로세스 처리(FCFS)

3) 시간 할당량을 다 썼지만 프로세스가 종료되지 못했다면 다음 단계의 큐로 이동 배치

4) 3)의 과정을 반복하며 마지막 n단계 시간 할당량만큼 실행 후 종료되지 못한 경우 RR 스케줄링 방식으로 동작