[운영체제] 2. 스케줄링(Scheduling) 알고리즘

스케줄링(Scheduling) 알고리즘

① FCFS(First Come First Served)

* 특징
1. 먼저 온 고객을 먼저 서비스해주는 선입 선처리(First Come, First Served) 방식, 작업 큐(Job Queue)에 먼저 삽입 된 순서대로 처리.
2. CPU burst가 완료될 때까지 CPU를 반환하지 않는다. 할당되었던 CPU가 반환될 때만 스케줄링이 이루어진다.
3. 비선점형(Non-Preemptive) 스케줄링
* 문제점
1. Convoy Effect(호위효과): burst 시간이 긴 하나의 프로세스가 CPU를 반환할 때까지 다른 모든 프로세스들이 기다리는 현상.
2. 소요 시간이 긴 프로세스가 먼저 도달하면 효율성을 낮추는 현상이 발생함.

※ CPU burst: 프로세스의 실행이 시작되고 CPU가 연산을 수행하는 작업.

 

② SJF(Shortest - Job - First)

* 특징
1. 최단 작업 우선(Shortest Job First) 방식
2. 다른 프로세스가 먼저 도착했어도 CPU burst time이 짧은 프로세스에게 먼저 할당.
3. 최소의 평균 대기 시간을 달성 가능함.
4. CPU burst time이 동일하다면 FCFS를 따름.
5. 기본적으로 비선점형(Non-Preemptive) 스케줄링
* 문제점
1. Starvation - CPU burst time이 긴 프로세스는 영원히 CPU를 할당 받을 수 없는 상황. (이 스케줄링은 작업시간이 짧은 순서대로 할당하기 때문에 실행 시간이 긴 프로세스는 무한대기 상태에 빠질 수 있음.)

 

③ SRTF(Shortest Remaining Time First, SRT라고도 함)

* 특징
1. 선점형(Preemptive) SJF 스케줄링
2. 새로운 프로세스가 도착할 때마다 새로운 스케줄링이 이루어짐.
3. 현재 수행 중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 뺏김.
* 문제점
1. Starvation(기아 상태)
2. 새로운 프로세스가 도착할 때마다 스케줄링을 다시하기 때문에 CPU burst time(CPU 사용 시간)을 측정하기 매우 어려움.

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

* 특징
1. 미리 주어진 우선순위에 따라 CPU를 할당함. (따라서 SJF도 우선순위 스케줄링의 일종이라고 볼 수 있음.)
2. 우선순위는 측정 가능한 숫자가 작을수록 높은 우선순위를 가짐.
3. 선점형(Preemptive) 우선순위 스케줄링: 더 높은 우선순위의 프로세스가 도착하면 실행 중인 프로세스를 멈추고 CPU를 뺏음.
4. 비선점형(Non-Preemptive) 우선순위 스케줄링: 더 높은 우선순위의 프로세스가 도착하면 준비상태 큐(Ready Queue)의 Head에 넣어 다음 순서로 실행함.
* 문제점
1. Starvation => 해결법: Aging(노화) 알고리즘 - 기다리는 시간에 따라 우선순위를 증가시켜주는 방법. 오래 기다린만큼 우선순위를 높여주어 결국에 실행될 수 있도록 함.

 

⑤ RR(Round Robin)

* 특징
1. 가장 현대적인 CPU 스케줄링 방식
2. 선점형(Preemptive) 스케줄링 방식
3. 시간 할당량(Time Quantum)만큼 수행을 한 프로세스는 Ready Queue의 마지막으로 들어가 재할당을 기다림.
4. 시간 할당량은 보통 10~100ms
5. CPU 사용시간이 랜덤한 프로세스들이 섞여 있을 경우에 효율적.
6. RR이 가능한 이유는 프로세스의 문맥 교환(Context Switching)을 통해 프로세스의 상태를 보관할 수 있기 때문임.
* 장점
1. Response time이 줄어들어 사용자에게 빠른 응답을 제공할 수 있음.
2. 프로세스가 기다리는 시간이 CPU 를 사용할 만큼 증가하기 때문에 공정한 스케줄링이라고 할 수 있음.
* 주의할 점
설정한 시간 할당량(Time Quantum)이 너무 커지면 FCFS와 같아짐. 반대로 너무 작아지면, 스케줄링 알고리즘의 목적에는 이상적이지만 잦은 문맥 교환(Context Switching)으로 인한 Overhead가 발생한다. 따라서, 적당한 시간 할당량(Time Quantum)을 설정하는 것이 중요함.

 

⑥ 다단계 큐(Multi-Level Queue)

* 특징
1. 준비완료 큐(Ready Queue)를 여러 개의 큐로 분류하여 각 큐가 각기 다른 스케줄링 알고리즘을 가지게 하는 기법.
2. 메모리 크기, 우선순위, 유형 등의 프로세스 특성에 따라 하나의 큐에 영구적으로 할당.
3. 큐와 큐 사이의 스케줄링도 필요. => 우선순위(Priority) 또는 시분할(Time Slice)로 가능함.
* 우선순위 방식
1. 일반적으로 고정 우선순위의 선점형 스케줄링 방식으로 구현되어 각 큐는 자기보다 낮은 우선순위를 가진 큐보다 절대적인 우선순위를 가짐.
2. Foreground라는 큐(우선순위 높음)와 Background 큐(우선순위 낮음)가 있다고 가정함. Foreground 큐가 비어있지 않다면, Background 큐에 있는 프로세스는 실행될 수 없음. 또한, Background 큐에 있는 프로세스가 실행되고 있는 중이라 하더라도 Foreground 큐에 프로세스가 새로 들어가게 된다면 Background 큐는 CPU를 뺏김.
* 시분할 방식
1. 큐들 사이에 시간을 나누어 사용하는 방법. 각 큐는 CPU 시간의 일정 부분을 할당 받아 자기 큐에 있는 프로세스들을 스케줄링함.
ex) Foreground 큐: 80% 할당, Round Robin방식 / Background 큐: 20% 할당, FCFS 방식

 

⑦ 다단계 피드백 큐(Multi-Level Feedback Queue)

* 특징
1. 기존의 다단계 큐는 프로세스의 특정이 바뀌지 않는다고 보아 프로세스가 큐 사이를 이동하는 것을 허용하지 않음. 따라서, 스케줄링 오버헤드는 적다는 장점을 가지지만 융통성이 부족하다는 단점도 가지고 있음.
2. 다단계 피드백 큐는 프로세스가 큐 사이를 이동하는 것이 허용됨.
3. 큐를 구분하는 기준은 CPU burst임. 입출력 중심의 프로세스와 대화형 프로세스를 높은 우선순위의 큐에 넣음. 반대로 낮은 우선순위의 큐에서 너무 오래 대기하는 프로세스들은 높은 우선순위의 큐로 이동(Aging)하여 기아 상태(Starvation)를 예방함.
* 단점
1. 다단계 큐와 비교하였을 때 단점은 프로세스를 다른 큐로 이동시키는 시기를 결정하거나 이동가능성에 대해 고려할 것이 많아 설계하기 어렵다는 점이 있음.

 

⑧ HRN(Highest Response ratio Next)

* 특징
1. SJF의 단점을 보완한 방법으로 우선순위 알고리즘으로 계산한 값이 큰 프로세트부터 실행하는 방식.
2. 우선순위 = (실행시간 + 대기시간) / 대기시간
3. 비선점형(Non-Preemptive) 스케줄링

 

⑨ 기한부

* 특징
1. 일정 시간 동안 프로세스가 완료되지 않으면 삭제하고 다시 실행함.
2. 비선점형(Non-Preemptive) 스케줄링