[운영체제(OS)] 5-2) 스케줄링 알고리즘

---

<스케줄링 알고리즘>

: 선점형(preemptive), 비선점형(non-preemptive) 알고리즘으로 나뉩니다. 비선점형 알고리즘이 컨텍스트 스위칭으로 인한 오버헤드가 적지만, 대기 시간이 길어질 수 있기 때문에 일반적으로는 선점형 알고리즘이 주로 사용됩니다.

 

1. 선입 선처리 스케줄링(First-come, First-Served. FCFS)

: CPU를 먼저 요청하는 프로세스가 먼저 할당받으며, Queue로 관리합니다. 비선점형 스케줄링입니다.

* 장점 : 가장 간단한 형태의 스케줄링이어서 코드 작성이 쉽고 이해하기 쉽습니다.

* 단점 : 순서에 따라서 대기 시간의 차이가 클 수 있습니다. 모든 다른 프로세스들이 길이가 긴 프로세스가 CPU를 양도해주기를 기다려야 합니다(호위효과(Convoy effect). ready queue에서 오래 기다리는 현상). 비선점형이기 때문에 시분할 시스템에 부적합합니다. 

 

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

: CPU burst가 짧을수록 먼저 할당받습니다. 비선점형 스케줄링입니다.

* 장점 : 평균 대기 시간이 가장 짧습니다.

* 단점 : 다음 CPU 요청의 길이 예측이 어렵습니다.

 

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

: 우선순위가 높은 프로세스들에게 먼저 CPU를 할당해줍니다. 비선점형 스케줄링입니다.

* 장점 : 내부적인 정의(시간 제한, 메모리 요구, open files의 수 등), 외부적 정의(프로세스의 중요성, 컴퓨터 사용을 위해 지불되는 비용의 유형과 양)를 활용하여 우선순위를 결정할 수 있습니다.

* 단점 : 무한 봉쇄, 기아 상태에 들어갈 수 있으므로 Aging(얼마나 대기했는지?)을 고려해야합니다.

 

4. 라운드 로빈 스케줄링(Round-Robin)

: 작은 단위의 시간을 정의(시간 할당량. Time Quntum)하고, 한 번에 한 프로세스에게 한 번의 시간 할당량동안 CPU를 할당합니다. 선점형 스케줄링입니다.

* 장점 : 시분할 시스템에 최적화되어 있습니다.

* 단점 : 시간 할당량에 따른 영향을 받습니다. 할당량이 너무 큰 경우, FCFS와 동일한 알고리즘이 되며, 너무 작은 경우 Context switch에 시간을 더 뺏기게 됩니다.

 

5. 다단계 큐 스케줄링

: 프로세스의 타입에 따라 몇 개의 큐로 나누어서 분류합니다. 각 큐는 우선순위를 가지게 됩니다.

다단계 큐의 우선순위

각 큐들은 일정 비율로 CPU할당을 나눠가지는데, 포그라운드(RR)가 CPU 시간의 80%, 백그라운드(FCFS)가 CPU 시간의 20% 정도를 나눠가집니다. 

 

다단계 큐 스케줄링에서는 프로세스가 큐들 사이를 이동하는 것을 허용합니다.