[운영체제] CPU 스케줄링

기본 개념

---

CPU - I/O 버스트 사이클 (CPU - I/O Burst Cycle)

프로세스 실행은 CPU 실행과 I/O 대기의 사이클로 구성된다.

프로세스의 실행은 CPU Burst로 시작된다. 뒤이어 I/O Burst가 발생하고, 그 뒤를 이어 또 다른 CPU Burst가 발생하며, 이어 또 다른 I/O Burst 등등으로 진행된다. 결국 아래의 그림처럼 마지막 CPU Burst는 실행을 종료하기 위한 시스템 요청과 함께 끝난다.

선점/비선점 스케줄링 (Preemptive/Nonpreemptive Scheduling)

CPU 스케줄링 결정은 다음의 네 가지 상황에서 발생할 수 있다.

1. 한 프로세스가 실행 상태에서 대기 상태로 전환될 때 (I/O 발생)
2. 프로세스가 실행 상태에서 준비 완료 상태로 전환될 때 (인터럽트 발생)
3. 프로세스가 대기 상태에서 준비 완료 상태로 전환될 때 (I/O 종료)
4. 프로세스가 종료할 때

비선점형 스케줄링(nonpreemptive): 한 프로세스가 CPU를 할당받으면 작업 종료 후 CPU 반환 시까지 다른 프로세스는 PCU 점유가 불가능한 스케줄링 방식

선점형 스케줄링(preemptive): 하나의 프로세스가 CPU를 차지하고 있을 때, 우선순위가 높은 다른 프로세스가 현재 프로세스를 중단시키고 CPU를 점유하는 스케줄링 방식

스케줄링 기준

---

• CPU 이용률(Utilization): 어느 기간 동안 또는 특정 SNAPSHOT에서의 CPU의 이용률을 말한다.
• 처리량(Throughput): 단위 시간당 완료된 프로세스의 개수.
• 총처리 시간(Turnaround Time): 프로세스의 제출 시간과 완료 시간의 간격.
• 대기 시간(Waiting Time): 프로세스가 준비 큐에서 대기하면서 보낸 시간의 합.
• 응답 시간(Response Time): 하나의 Request를 제출한 후 첫 번째 Response가 나올 때까지의 시간.

CPU 이용량(Utilization)과 처리량(Throughput)을을 최대화하고 총처리 시간, 대기 시간, 응답 시간 (Turaround Time, Waiting Time, Response Time)을 최소화 하는 알고리즘의 선택이 바람직한 선택이다.

 

스케줄링 알고리즘

---

1. FIFO (First Come First Served Scheduling)

CPU를 가장 먼저 요청하는 프로세스가 CPU를 먼저 할당받는 방식. Queue의 FIFO(First-In First-Out)와 동일하다.

수행 시간이 큰 프로세스가 먼저 들어오면 그 뒤에 들어온 프로세스들이 불필요하게 오랜 시간을 기다리게 되는 호위 효과(Convoy effect)가 발생한다.

선입 선처리 스케줄링 알고리즘은 비선점형 알고리즘이다. 일단 CPU가 한 프로세스에 할당되면, 그 프로세스가 종료하는지 또는 I/O 처리를 요구하든지 하여 CPU를 방출할 때까지 CPU를 점유한다.

 

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

 

2. SJF (Shortest Job First)

프로세스의 수행 시간이 짧은 순서에 따라 프로세서에 할당하는 방식.

FCFS에서 발생하는 콘보이 효과를 해결할 수 있다. 최적 알고리즘이지만 수행 시간을 정확히 알 수 없다. (앞서 처리한 프로세스들의 기록을 보고 추측한다.)

버스트 시간이 큰 프로세스는 계속 뒤로 밀려나는 기아(Starvation)가 발생한다.

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

 

최단 작업 우선(SJF) 스케줄링 알고리즘은 주어진 프로세스 집합에 대해 최소의 평균대기 시간을 가진다는 점에서 최적임을 증명할 수 있다. 하지만 각 프로세스의 CPU 버스트 길이는 알 수 있는 방법이 없기 때문에 CPU 스케줄링 수준에서는 구현하기가 어렵다. 따라서 우리는 프로세스별 CPU 버스트의 길이를 예측해서 스케줄링 해야만 한다.

SJF 알고리즘은 선점형이거나 비선점형일 수 있다. 앞의 프로세스가 실행되는 동안 새로운 프로세스가 준비 큐에 도착하면 선택이 발생한다. 새로운 프로세스의 길이가 실행하고 있는 프로세스의 남은 시간보다 짧을 때, 선점형 SJF 알고리즘은 새로운 프로세스를 실행할 것이고, 비선점형 SJF 알고리즘은 현재 실행하고 있는 프로세스가 자신의 CPU 버스트를 끝내도록 한다. 선점형 SJF 알고리즘은 최소 잔여 시간 우선(shortest remaining time first) 스케줄링이라고 불린다. SRF는 SJF에서 발생하는 기아 문제를 해결할 수 있다.

 

3. RR (Round Robin)

일정 시간 할당량(Time quantum) 또는 타임슬라이스(Time slice)라고 하는 단위로 여러 프로세스를 번갈아가며 프로세서에 할당한다.

반응성이 좋다. 주로 우선순위 스케줄링(Priority scheduling)과 결합해 프로세스의 시간 할당량을 조절하는 방식으로 활용한다.

시간 할당량에 따라 운영체제가 계속 개입하는 선점 스케줄링 방식이다.

time quantum이 4인 경우. 평균대기 시간: (6+4+7)/3 = 5.66

RR 알고리즘의 성능은 시간 할당량의 크기에 매우 많은 영향을 받는다. 극단적인 경우, 시간 할당량이 매우 크면, RR 정책은 FCFS와 같다. 반대로 시간 할당량이 매우 적다면 RR 정책은 매우 많은 문맥 교환을 야기한다.

 

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

특정 기준으로 프로세스에게 우선순위를 부여해 우선순위에 따라 프로세서에 할당한다.

우선순위는 내부적 또는 외부적으로 정의될 수 있다. 시간 제한, 메모리 요구, 열린 파일의 수, 평균 I/O 버스트의 평균 CPU에 대한 비율 등이 내부적 우선순위를 결정한다. 외부적 우선순위는 프로세스의 중요성, 컴퓨터 사용을 위해 지불되는 비용 등과 같은 운영체제 외부적 기준에 의해 결정된다. 

우선순위 스케줄링 알고리즘의 문제는 무한 봉쇄(indefinite blocking) 또는 기아(starvation)이다.

• 실행 준비는 되어 있으나 CPU를 사용하지 못하는 프로세스는 CPU를 기다리면서 봉쇄 된 것으로 간주할 수 있다. (Blocking)
• 부하가 과중한 컴퓨터 시스템에서는 높은 우선순위의 프로세스들이 꾸준히 들어와서 낮은 우선순위의 프로세스들이 CPU를 얻지 못하게 될 수 도 있다. (Starvation)

낮은 우선순위의 프로세스들이 무한히 봉쇄되는 문제에 대한 한가지 해결 방안은 에이징(aging)이다. 에이징은 오랫동안 시스템에서 대기한 프로세스들의 우선순위를 높이는 방식이다. SRF의 경우 남은 수행 시간을 기준으로 우선순위를 부여한다고 할 수 있다.

우선순위 스케줄링의 문제점을 해결할 수 있는 또 다른 방법은 우선순위 스케줄링과 라운드 로빈 스케줄링을 결합하는 방법이다. 시스템에서 우선순위가 가장 높은 프로세스를 실행하고, 우선순위가 같은 프로세스들은 RR을 사용하여 스케줄 하는 방식이다.

 

5. 다단계 큐 스케줄링(Multilevel Queue Scheduling)

가장 높은 우선순위 큐의 프로세스에 CPU를 할당하는 방식. 각 큐는 라운드 로빈이나 FCFS등 독자적 스케줄링 사용 가능하다.

큐들 간의 프로세스 이동이 불가하기 때문에 스케줄링 부담이 적지만 유연성이 떨어진다. 우선순위가 낮은 프로세스가 오랫동안 CPU 할당을 기다리는 기아 현상이 발생할 수도 있다.

 

6. 다단계 피드백 큐 스케줄링 (Multilevel Feedback Queue Scheduling)

다단계 큐 스케줄링 알고리즘에서는 일반적으로 프로세스들이 시스템 진입 시에 영구적으로 하나의 큐에 할당된다. 이와 반대로 다단계 피드백 큐 스케줄링 알고리즘에서는 프로세스가 큐들 사이를 이동하는 것을 허용한다.

다단계 피드백 큐 스케줄링 알고리즘은 Aging과 Starvation을 예방한다. MFQ에서는 가장 우선순위가 낮은 큐를 제외하고는 모두 RR스케줄링을 사용한다.

이 알고리즘은 특정 시스템에 부합하도록 구성이 가능함으로 현대 사용되는 CPU 스케줄링 알고리즘 중 가장 일반적인 CPU 스케줄링 알고리즘이다. 하지만, 가장 좋은 스케줄러로 동작하기 위해서는 모든 매개변수 값들을 선정하는 특정 방법이 필요하기 떄문에 가장 복잡한 알고리즘이기도하다.