[운영체제 OS] 스케줄링 알고리즘 - FCFS, RR, SJF, SRT, Priority, MLQ, MFQ 스케줄링

 

1. CPU 스케줄러란?

• CPU에 대한 스케줄링
• 다중 프로그래밍을 가능하게 하는 OS의 동작 기법
• 순서를 정하여 CPU를 프로세스에 할당/해제하는 일
• OS 설계 시 핵심사항 중 하나
• 목적: CPU의 이용률을 높임

 

Q. 언제 스케줄링이 일어나나요?

 A. 현재 실행상태에 있던 프로세스가 다른 상태로 천이될 때 다음 실행시킬 프로세스의 선정이 필요한 경우 스케줄링이 발생합니다. 스케줄링 대상은 준비 리스트에 들어있는 프로세스들에 한해 스케줄링을 합니다.

CPU 스케줄러의 알고리즘들을 설명하기에 앞서 CPU 성능 평가의 기준은 무엇인지, CPU Burst Time은 무엇인지, 또한 선점, 비선점 스케줄링의 차이점을 설명드리고자 합니다.

- 성능 평가의 기준

CPU 사용률 (CPU Utilization)	CPU 활용 정도를 나타내는 비율
처리율 (Throughput)	단위 시간당 완료되는 프로세스의 수
반환 시간 (Turnaround Time)	프로세스가 생성되어 작업을 마치고 종료될 때까지의 걸리는 시간
대기 시간 (Waiting Time)	프로세스가 생성되어 작업을 마치고 종료될 때까지 큐에서 기다리는 시간
반응 시간 (Response Time)	대화형 시스템에서 임의 요구(예: 키보드 입력)에 대하여 시스템이 반응을 시작하는 데까지 걸리는 시간

효율성을 추구! => CPU 사용률과 처리율은 최대화하고 반환시간, 대기시간, 반응시간은 최소화하는 스케줄러 선정

공평성을 추구! => 각 기준에 있어서 최적의 평균값과 이들 간의 편차의 최소화를 함께 고려하여 스케줄러를 선정

대화형 시스템! => 반응시간의 편차가 적은 스케줄러 선정

시스템 용도에 따라 선정 기준이 달라질 수 있고, 기준 간의 Trade-Off가 있을 수 있습니다.

 

 

- CPU Burst TIme 

 

CPU Burst Time 이란 CPU 할당 후 입출력 요구 시까지의 시간을 뜻합니다.

위의 Historgram은 평균적으로 Hyperexponential 분포를 보입니다.

 

CPU Bound : 프로세스 진행 속도가 CPU 속도에 의해 제한됨을 의미합니다. 작은 숫자를 곱하는 것과 같이 작은 숫자 집합에서 계산을 수행하는 작업은 CPU Bound 될 가능성이 높으며, I/O빈도가 낮고 CPU를 오래 사용하는 프로세스를 CPU Bound Job이라 합니다.

I/O Bound : 프로세스가 진행되는 속도가 I/O 하위 시스템의 속도에 의해 제한됨을 의미합니다. 예를 들어, 파일의 행 수를 계산하는 등 디스크에서 데이터를 처리하는 작업은 I/O Bound 될 가능성이 높으며, I/O빈도가 많은 프로세스를 I/O Bound Job이라고 합니다.

Memory Bound : 프로세스가 진행되는 속도가 사용 가능한 메모리 양과 해당 메모리 액세스 속도에 의해 제한됨을 의미합니다. 큰 행렬을 곱하는 것과 같이 많은 양의 메모리를 처리하는 작업은 Memory Bound 될 가능성이 높습니다. 

Cache Bound : 프로세스 진행률이 사용 가능한 캐시의 양과 속도에 의해 제한되는 비율을 의미합니다. 캐시의 제한을 넘어서는 처리 작업은 Cache Bound 될 가능성이 높습니다.

 

 

- 비선점 VS 선점 스케줄링

 

1) 비선점 스케줄링(Non-Preemptive Scheduling)

프로세스가 입출력 요구 등으로 CPU를 자진 반납할 때까지 CPU에 의한 실행을 보장해주는 스케줄링을 뜻합니다. 작업 실행 시간 전체 또는 한 번의 CPU배당에 대해 적용됩니다. 비선점 스케줄링의 예로는 FCFS(First Come First Served), SJF(Shortest Job First, 최단 작업 우선), 우선순위(Priority) 스케줄링이 있습니다.

 

2) 선점 스케줄링(Preemptive Scheduling)

시분할 시스템에서 타임슬라이스가 소진되었거나, 인터럽트 혹은 시스템 호출 종료 시에 그 여파로 현 프로세스보다 높은 우선순위의 프로세스가 나타나는 경우, 현 프로세스로부터 강제로 CPU를 회수하는 것을 말합니다. 선점 스케줄링의 예로는 라운드로빈, 다단계 큐, 다단계 피드백 큐 스케줄링이 있습니다.

 

2. CPU 스케줄러 알고리즘

 

- 비선점 스케줄링 알고리즘

1) FCFS 스케줄링(First Come First Served Scheduling)

• 프로세스의 도착순으로 CPU를 배정(실행 중 입출력을 요구하면 다시 다음 준비 상태에서 FCFS 적용)
• 장기 스케줄러에서 사용가능(Batch 작업등)
• 시분할 시스템에서는 time slice를 적용하지 않는 프로세스에 대해 사용 가능(백그라운드 또는 실시간 프로세스 등)
• 수행 중인 긴 작업을 여러 개의 짧은 작업들이 기다리게 되는 호위(호송) 효과(Convoy Effect)의 문제가 발생한다.

작업	Burst Time
P1	24
P2	3
P3	3

도착 순서  1 => 2 => 3

간트차트

- 평균 반환시간 = (24+27+30) / 3 = 27

- 평균 대기시간 = (0+24 +27) / 3 = 17

 

2) 최단 작업 우선 스케줄링(SJF, Shortest Job First Scheduling)

• 대기하는 작업 중 CPU Burst Time이 가장 작은 작업에 CPU를 할당하는 기법
• 평균 대기 시간에 있어 최적의 알고리즘
• CPU 요구시간(Burst TIme)을 미리 알기가 어렵다. 일괄 처리 시스템의 장기 스케줄링의 경우, 작업 시간 예측치를 제출하는데 단기 스케줄링에서는 다음 CPU Burst TIme을 미리 알 수가 없기 때문에 사용에 어려움이 있다. 따라서 다음 CPU Burst Time은 이전 Burst TIme의 지수적 평균으로 간주하여 예측하는 해결방안이 생겼다.

작업	Burst Time
P1	6
P2	3
P3	8
P4	7

간트차트

- 평균 반환시간 = (3+9+16+24) / 4 = 13

- 평균 대기시간 = (3+0+16+9) / 4 = 7

 

만약 도착시간을 고려한다면..?

작업	도착시간	Burst TIme
P1	0	7
P2	2	4
P3	4	1
P4	5	4

간트차트

- 평균 반환시간 = (7+10+4+11) / 4 = 8

(예 : P2의 경우 2에 도착하여 8에 시작하므로 대기시간은 6이며 12에 끝나므로 반환시간은 10이다.)

- 평균 대기시간 = (0+6+3+7) / 4 = 4

 

3) 우선순위 스케줄링(Priority Scheduling)

• 각 프로세스의 우선순위가 정해지면, 우선순위가 제일 높은 프로세스에게 CPU를 할당하되, 우선순위가 같은 경우에는 FCFS 방식을 적용한다.
• 일반적인 연산 위주(CPU Bound) 프로세스보다 입출력 위주(I/O Bound) 프로세스에게 높은 우선순위를 부여하여 대화성을 증진시킨다.
• 우선순위가 높은 작업이 계속적으로 들어올 경우 우선순위가 낮은 작업은 준비상태에서 보장 없이 머물게 된다(기아상태). 따라서 이러한 문제는 시스템에 머무는 시간이 증가할수록 우선순위를 높여주는 에이징(Aging)으로 해결한다.

내부적 우선순위 고려 : 제한 시간, 메모리 요구량, 사용하는 파일 수, 평균 CPU Burst에 대한 평균 I/O Burst의 비율 등

외부적 우선순위 고려 : 사용료, 정책적인 변수 등

 

작업	Burst TIme	우선순위
P1	10	3
P2	1	1
P3	2	3
P4	1	4
P5	5	2

간트차트

- 평균 반환시간 = (16+1+18+19+6) / 5= 12

- 평균 대기시간 = (6+0+16+18+1) / 5 = 8.2

 

 

- 선점 스케줄링 알고리즘

1) SRT 스케줄링(Shortest Remaining Time Scheduling)

• 최단 잔여시간을 우선으로 하는 스케줄링.
• 진행 중인 프로세스가 있어도, 최단 잔여시간인 프로세스를 위해 sleep 시키고 짧은 프로세스를 먼저 할당한다.
• 선점형 SJF 스케줄링이라 불린다.

작업	도착시간	Burst TIme
P1	0	8
P2	1	4
P3	2	9
P4	3	5

간트차트

- 평균 반환시간 = (17+4+24+7) / 4 = 13

- 평균 대기 시간 = (9+0+15+2) / 4 = 6.5

 

2) 라운드 로빈 스케줄링(Round Robin Scheduling)

• 선점형 스케줄링 중 하나로 시분할 시스템을 위해 설계되었다.
• 준비 큐를 원형 큐로 간주하고 순환식으로 각 프로세스에게 작은 단위의 시간량(타임 퀀텀)만큼씩 CPU를 할당하는 방식 (타임 퀀텀이 타임 슬라이스에 해당) 
• 알고리즘의 성능은 시간 할당량의 크기에 좌우된다. 시간할당량이 매우 크면 FCFS 스케줄링과 같아지며, 시간 할당량이 매우 작으면 프로세서 공유와 같아진다.
• 이론 상 n개의 프로세스가 1/n의 속도로 동시에 실행
• 일반적으로 평균 반환시간이 SJF보다 크지만, 프로세스가 공정하게 기회를 얻게 되어 기아상태가 발생하지는 않음
• 타임 퀀텀의 크기가 작으면 잦은 문맥 교환 오버헤드 증가로 처리율(Throughput)이 감소할 수 있으며 성능은 타임 퀀텀의 크기에 많은 영향을 받는다.

 

작업	Burst TIme
P1	53
P2	17
P3	68
P4	24

간트차트

- 평균 반환시간 = (134+37+162+121) / 4 = 113.5

- 평균 대기 시간 = (81+20+94+97) / 4 = 73

 

Q. 라운드 로빈에서 타임 퀀텀이 증가하면 반환시간이 짧아지나요..?

A. 타임 퀀텀이 증가한다고 해서 반드시 평균 반환시간이 개선되는 것은 아닙니다. 그러나 대부분의 프로세스들이 한 타임 퀀텀 내에 하나의 CPU Burst를 끝낸다면 평균 반환시간은 개선됩니다. 경험적으로 볼 때 CPU Burst의 80%는 타임 퀀텀보다 짧도록 타임 퀀텀을 조정하는 것이 좋다고 전문가들은 말합니다.

 

3)다단계 큐 스케줄링(MLQ), 다단계 피드백 큐 스케줄링(MFQ)

https://cocoon1787.tistory.com/124

[운영체제 OS] 다단계 큐 스케줄링(MLQ), 다단계 피드백 큐 스케줄링(MFQ)