[OS] CPU 스케줄링(CPU Scheduling)

 

CPU 스케줄링(CPU Scheduling)

---

CPU 스케줄링은 다중 프로그램 운영체제의 기본입니다. 운영체제는 CPU를 프로세스 간에 교환함으로써, 컴퓨터를 보다 생산적으로 만듭니다. 이번에는 기본적인 스케줄링 개념을 소개하고 정리해보겠습니다.

코어가 하나인 시스템에서는 한순간에 오직 하나의 프로세스만이 실행될 수 있습니다. 나머지 프로세스는 CPU의 코어가 가용 상태가 되어 다시 스케줄 될 수 있을 때까지 기다려야 합니다. 다중 프로그래밍의 목적은 CPU 이용률을 최대화하기 위해 항상 실행 중인 프로세스를 가지게 하는 데 있습니다. 다중 프로그래밍에 대한 기본 아이디어는 비교적 간단합니다. 하나의 프로세스는, 전형적인 어떤 I/O 요청이 완료되기를 기다려야만 할 때까지 실행됩니다. 이렇게 되면, 단순한 컴퓨터 시스템에서 CPU는 그저 놀고 있게 됩니다. 이러한 모든 대기 시간은 낭비되며, 어떤 유용한 작업도 수행하지 못합니다. 다중 프로그래밍에서는, 우리는 이러한 시간을 생산적으로 활용하려고 시도합니다.

1. 어느 한순간에 다수의 프로세스를 메모리 내에 유지합니다.
2. 어떤 프로세스가 대기해야 할 경우, 운영체제는 CPU를 그 프로세스로부터 회수해 다른 프로세스에 할당합니다.

이러한 패턴은 계속 반복됩니다. 하나의 프로세스가 대기해야 할 때마다, 다른 프로세스가 CPU 사용을 양도받을 수 있습니다. 다중 코어 시스템에서 CPU를 바쁘게 유지하는 이 개념은 시스템의 모든 처리 코어로 확장됩니다.

 이러한 종류의 스케줄링은 운영체제의 기본적인 기능입니다. 거의 모든 컴퓨터 자원들은 사용되기 전에 스케줄 됩니다. 물론 CPU는 중요한 컴퓨터 자원 중의 하나입니다. 따라서 CPU 스케줄링은 운영체제 설계의 핵심이 됩니다.

(1) CPU 스케줄러(_CPU Scheduler)

CPU가 유휴 상태가 될 때마다, 운영체제는 준비 큐에 있는 프로세스 중에서 하나를 선택해야 합니다. 선택 절차는 CPU 스케줄러에 의해 수해됩니다. 스케줄러는 실행 준비가 되어 있는 메모리 내의 프로세스 중에서 선택하여, 이들 중 하나에게 CPU를 할당합니다.

 준비 큐는 반드시 선입선출(FIFO) 방식의 큐가 아니어도 되는 것에 유의해야 합니다. 여러 가지 스케줄링 알고리즘들을 고려할 때 알게 되겠지만, 준비 큐는 선입선출 큐, 우선순위 큐, 트리 또는 단순히 순서가 없는 연결 리스트로 구현할 수 있습니다. 그러나 개념적으로 볼 때 준비 큐에 있는 모든 프로세스들은 CPU에서 실행될 기회를 기다리며 대기하고 있습니다. 큐에 있는 레코드들은 일반적으로 프로세스들의 프로세스 제어 블록(PCB)들입니다.

준비 상태의 다중 큐

(2) 선점 및 비선점 스케줄링(_Preemptive and Nonpreemptive Scheduling)

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

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

상황 1과 4의 경우, 스케줄링 면에서는 선택의 여지가 없습니다. 실행을 위해 새로운 프로세스(준비 큐에 하나라도 존재할 경우)가 반드시 선택되어야 합니다. 그러나 상황 2와 3을 위해서는 선택의 여지가 있습니다.

 상황 1과 4에서만 스케줄링이 발생할 경우, 우리는 이러한 스케줄링 방법을 비선점(nonpreemptive) 또는 협조적(cooperative)라고 합니다. 그렇지 않으면, 그것은 선점(preemptive)이라고 합니다. 비선점 스케줄링 하에서는, 일단 CPU가 한 프로세스에 할당되면 프로세스가 종료하든지, 또는 대기 상태로 전환해 CPU를 방출할 때까지 점유합니다. Windows, macOS, Linux 및 UNIX를 포함한 거의 모든 최신 운영체제들은 선점 스케줄링 알고리즘을 사용합니다.

선점형 스케줄러(Preemptive Scheduling)	하나의 프로세스가 다른 프로세스 대신에 프로세스 CPU를 차지할(뺏을) 수 있음
비선점형(Non-preemptive Scheduling)	하나의 프로세스가 끝나지 않으면 다른 프로세스는 CPU를 사용할(뺏을) 수 없음

이러한 스케줄링을 하기 위한 스케줄링 알고리즘 기법들은 아래에서 살펴보겠습니다.

 

스케줄링 기준(_Scheduling Criteria)

---

서로 다른 CPU 스케줄링 알고리즘들은 다른 특성이 있으며 한 부류의 프로세스들을 다른 부류보다 더 선호할 수 있습니다. 특정 상황에서 어떠한 알고리즘을 선택하려면, 우리는 다양한 알고리즘들의 서로 다른 특성을 반드시 고려해야 합니다.

 CPU 스케줄링 알고리즘을 비교하기 위한 여러 기준이 제시되었습니다. 비교하는 데 사용되는 특성에 따라서 최선의 알고리즘을 결정하는 데 큰 차이가 발생합니다. 사용되는 기준은 다음을 포함합니다.

• 대기시간(waiting time): 프로세스가 생성된 후 실행되기 전까지 대기하는 시간(준비 큐에서 대기한 시간)
• 평균 대기 시간: 모든 프로세스의 대기 시간을 합한 뒤 프로세스의 수로 나눈 값
• 응답 시간(response time): 첫 작업을 시작한 후 첫 번째 출력(반응)이 나오기 전까지 시간
• 실행시간: 프로세스 작업이 시작된 후 종료되기까지의 시간
• 반환시간(turn around time): 대기 시간을 포함하여 실행이 종료될 때까지의 시간

  

  대기시간, 응답시간, 실행시간, 반환 시간의 관계

 

스케줄링 알고리즘(_Scheduling Algorithms)

---

대부분의 최신 CPU 아키텍처에는 여러 개의 처리 코어가 있지만 이러한 스케줄링 알고리즘을 처리 코어가 하나뿐이라고 가정하고 설명하겠습니다.

1. 선입 선처리 스케줄링(_First Come First-Served Scheduling, FCFS) 
2. 최단 작업 우선 스케줄링(_Short-Job- First Scheduling, SJF)
3. 라운드 로빈 스케줄링(_Round-Robin Scheduling, RR)
4. 우선순위 스케줄링(_Priority Scheduling)

(1) 선입 선처리 스케줄링(_First Come First-Served Scheduling, FCFS) 

• 준비 큐에 도착하면 순서대로 CPU를 할당하는 비선점형 방식
• 한 번 실행되면 그 프로세스가 끝나야만 다음 프로세스를 실행할 수 있음
• 큐가 하나라 모든 프로세스는 우선순위가 동일

프로세스들이 P1, P2, P3 순으로 도착하고, 선입 선처리 순으로 서비스받는다면, 다음의 Gantt 차트에 보인 결과를 얻습니다.

프로세스 P1의 대기 시간은0밀리 초이며, 프로세스 P2는 24밀리 초이고, 프로세스 P3은 27밀리 초입니다. 그러므로, 평균 대기시간은(0+24+27)/3 = 17 밀리초입니다. 그러나 프로세스들이 P2, P3, P4 순으로 도착하면, 결과는 다음과 같습니다.

평균 대기 시간은 이제 (6 + 0 + 3)/3 = 3밀리 초입니다. 이러한 감소는 상당히 큰 것입니다. 그러므로 선입 선처리 정책 하에서 평균 대기 시간은 일반적으로 최소가 아니며, 프로세스 CPU 버스트 시간이 크게 변할 경우에는 평균 대기 시간도 상당히 변할 수 있습니다.

이러한 FCFS 스케줄링의 단점은 모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 호위 효과(convoy effect)의 발생입니다. 이 효과는 짧은 프로세스들이 먼저 처리되도록 허용될 때보다 CPU와 장치 이용률이 저하되는 결과를 낳습니다.

 

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

• 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 방식
• FCFS의 문제점인 호위 효과(convoy effect)를 완화하여 시스템의 효율성을 높임
• 최소 잔여 시간 우선(shortest remaining time first) 스케줄링 이라고도 불림

SJF 스케줄링을 이용하면, 우리는 위의 프로세스를 다음의 Gantt 차트와 같이 스케줄 할 수 있습니다.

프로세스 P1의 대기 시간은 3밀리 초, 프로세스 p2의 대기 시간은 16밀리 초, 프로세스 P3는 9밀리 초이고, 프로세스 P4는 0초입니다. 그러므로, 평균 대기 시간은 (3 + 16 + 9 + 0)/4 = 7밀리 초입니다. 비교 차원에서 만일 선입선출(FCFS) 스케줄링을 사용한다면, 평균 대기시간은 10.25밀리 초가 되었을 것입니다.

 SJF 스케줄링 알고리즘은 주어진 프로세스 집합에 대해 최소의 평균 대기 시간을 가진다는 점에서 최적임을 증명할 수 있습니다. 짧은 프로세스를 긴 프로세스의 앞으로 이동함으로써, 짧은 프로세스의 대기 시간을 긴 프로세스의 대기 시간이 증가하는 것보다 더 많이 줄일 수 있습니다. 결과적으로, 평균 대기 시간이 줄어듭니다.

 SJF 알고리즘이 최적이긴 하지만, 다음 CPU 버스트의 길이를 알 방법이 없기 때문에 CPU 스케줄링 수준에서는 구현할 수 없습니다.

 

(3) 라운드 로빈 스케줄링(_Round-Robin Scheduling, RR)

• 한 프로세스가 할당받은 시간(타임 슬라이스: time slice, time quantum) 동안 작업 을 하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식
• 선점형 알고리즘 중 가장 단순하고 대표적인 방식
• 프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행

RR 스케줄링

만일 우리가 시간 할당량을 4밀리초로 한다면, 프로세스 P1은 처음의 4밀리초를 사용합니다. 이 프로세스는 20밀리초가 더 필요하기 때문에, 이 프로세스는 첫 번째 시간 할당량 이후에 선점되고, CPU는 큐에 있는 다음 프로세스인 P2에 할당됩니다. 프로세스 P2는 4밀리초를 필요로 하지 않기 때문에, 시간 할당량이 끝나기도 전에 종료합니다. CPU는 이어 다음 프로세스인 P3에 할당됩니다. 일단 각 프로세스가 할당량을 받으면 CPU는 다음의 시간 할당량을 프로세스 P1에게 할당합니다. 라운드 로빈 스케줄의 결과는 다음과 같습니다.

RR 스케줄링

이 스케줄에 따르는 평균대기 시간을 계산해 봅시다. P1은 6밀리초(10 - 4)를 기다리고, P2는 4밀리초, 그리고 P3는 7밀리초를 기다립니다. 따라서 평균대기 시간은 17/3 = 5.66 밀리초입니다.

 라운드 로빈 스케줄링 알고리즘에서는, 유일하게 실행 가능한 프로세스가 아니라면 연속적으로 두 번 이상의 시간 할당량을 할당받는 프로세스는 없습니다. 만일 CPU 버스트가 한 번의 시간 할당량을 초과하면, 프로세스는 선점되고 준비 큐로 되돌아갑니다. 따라서 RR 스케줄링 알고리즘은 선점형입니다.

타임 슬라이스(Time Slice or Time Quantum)의 크기와 문맥 교환
 -> 라운드 로빈 스케줄링이 효과적으로 작동하려면 문맥 교환에 따른 추가 시간을 고려하여 타임 슬라이스를 적절히 설정해야 함
 
타임 슬라이스가 큰 경우
 -> 하나의 작업이 끝난 뒤 다음 작업이 시작되는 것처럼 보여 FCFS 스케줄링과 다를게 없음
 
타임 슬라이스가 작은 경우
 -> 문맥 교환이 너무 자주 일어나 문맥 교환에 걸리는 시간이 실제 작업 시간보다 상대적으로 커지며, 문맥 교환에 많은 시간을 낭비하여 실제 작업을 못하는 문제가 발생

타임 슬라이스 크기와 문맥 교환의 관계

따라서 RR스케줄링은 타임 슬라이스는 되도록 작게 설정하되 문맥 교환에 걸리는 시간을 고려하여 적당한 크기로 하는 것이 중요합니다.

 

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

SJF 알고리즘은 일반적인 우선순위 스케줄링 알고리즘의 특별한 경우입니다. 우선순위가 각 프로세스들에 연관되어 있으며, CPU는 가장 높은 우선순위를 가진 프로세스에 할당됩니다. 우선순위가 같은 프로세스들은 선입 선처리(FCFS) 순서로 스케줄 됩니다. SJF 알고리즘은 우선순위가 예상되는 다음 CPU 버스트의 역인 단순한 우선순위 알고리즘 입니다. CPU 버스트가 클수록 우선순위가 낮으며, 설계에 따라 그 역도 성립합니다.

우선순위 스케줄링

우선 순위 스케줄링을 이용해, 다음의 Gantt 차트와 같이 이들 프로세스를 스케줄 할 수 있습니다.

우선순위 스케줄링

평균 대기 시간은 8.2밀리초입니다.

 우선순위 스케줄링은 선점형이거나 또는 비선점형이 될 수 있습니다. 프로세스가 준비 큐에 도착하면, 새로 도착한 프로세스의 우선순위를 현재 실행 중인 프로세스의 우선순위와 비교합니다.

• 선점형 우선순위 스케줄링 알고리즘: 새로 도착한 프로세스의 우선순위가 현재 실행되는 프로세스의 우선순위보다 높다면 CPU를 선점한다.
• 비선점형 우선순위 스케줄링 알고리즘: 단순히 준비완료 큐의 머리 부분에 새로운 프로세스를 넣는다.

 우선순위 스케줄링 알고리즘의 주요 문제는 무한 봉쇄(indefinite blocking) 또는 기아 상태(starvation)입니다. 실행 준비는 되어 있으나 CPU를 사용하지 못하는 프로세스는 CPU를 기다리면서 봉쇄된 것으로 간주할 수 있습니다. 우선순위 스케줄링 알고리즘을 사용할 경우 낮은 우선순위 프로세스들이 CPU를 무한히 대기하는 경우가 발생합니다. 부하가 과중한 컴퓨터 시스템에서는 높은 우선순위의 프로세스들이 꾸준히 들어와서 낮은 우선순위의 프로세스들이 CPU를 얻지 못하게 될 수도 있습니다.

낮은 우선순위의 프로세스들이 무한히 봉쇄되는 문제를 해결하는 두 가지 방법이 있습니다.

1. 노화(aging)
2. 라운드 로빈과 우선순위 스케줄링의 결합

첫번째 방법인 노화(aging)는 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시킵니다. 예를 들어, 우선순위가 127(낮음)에서 0(높음)까지의 범위라면, 우리는 주기적으로(예, 1초마다) 대기 중인 프로세스의 우선순위를 1씩 증가시킬 수 있을 것입니다. 결국에는 초기의 우선순위가 127이었던 프로세스도 시스템에서 최고의 우선순위를 갖게 되어 실행 될 것입니다.

두 번째 방법은 라운드 로빈과 우선순위 스케줄링을 결합하는 방법입니다. 시스템이 우선순위가 가장 높은 프로세스를 실행하고 우선순위가 같은 프로세스들은 라운드 로빈 스케줄링을 사용하여 스케줄 하는 방식입니다. 다음과 같은 프로세스 집합을 예로 들어 스케줄링을 설명해 보겠습니다. 프로세스의 버스트는 밀리초 단위입니다.

RR+Priority 스케줄링

우선순위 스케줄링과 우선순위가 같은 프로세스들은 라운드 로빈으로 스케줄링하고, 시간 할당량을 2밀리초로 했을 경우 위 프로세스들은 다음 Gantt 차트와 같이 스케줄링 될 것입니다.

RR+Priority 스케줄링

 이 예에서 프로세스 P4의 우선순위가 가장 높으므로 완료될 때까지 실행됩니다. 프로세스 P2 및 P3는 다음으로 가장 높은 우선순위를 가지며 라운드 로빈 방식으로 실행됩니다. 프로세스 P2가 시간 16에서 완료되면 프로세스 P3가 우선순위가 가장 높은 프로세스이므로 실행이 완료될 때까지 실행됩니다. 이제 프로세스 P1과 P5만 남아 있으며 우선순위가 같으므로 완료될 때까지 라운드 로빈 순서로 실행됩니다.

 

정리

---

1. CPU 스케줄링은 준비 큐에서 대기 프로세스를 선택하고 CPU를 할당하는 작업이다. 디스패처에 의해 선택된 프로세스에 CPU가 할당된다.
2. 스케줄링 알고리즘은 선점적(CPU를 프로세스로부터 뺏을 수 있는 경우) 또는 비선점적(프로세스가 자발적으로 CPU 제어를 포기해야 하는 경우)일 수 있다. 거의 모든  최신 운영체제가 선점적이다.
3. 스케줄링 알고리즘은 (1) CPU 이용률, (2) 처리량, (3) 총처리 시간, (4) 대기 시간, (5) 응답 시간의 5가지 기준에 따라 평가할 수 있다.
4. 선입 선처리(FCFS) 스케줄링은 가장 단순한 스케줄링 알고리즘이지만 짧은 프로세스가 매우 긴 프로세스를 기다리게 할 수 있다.
5. 최단 작업 우선(SJF) 스케줄링은 최적이며 평균 대기 시간이 가장 짧다. 그러나 다음 CPU 버스트의 길이를 예측하기 어려우므로 SJF 스케줄링을 구현하는 것은 어렵다.
6. 라운드 로빈(RR) 스케줄링은 CPU를 시간 할당량 동안 프로세스에 할당한다. 프로세스가 시간 할당량이 만료되기 전에 CPU를 포기하지 않으면 프로세스가 선점되고 다른 프로세스가 시간 할당량 동안 실행되도록 스케줄 된다.
7. 우선순위 스케줄링은 각 프로세스에 우선순위를 배정하고 CPU는 우선순위가 가장 높은 프로세스에 할당된다. 우선순위가 동일한 프로세스는 FCFS 순서로 또는 RR 스케줄링을 사용하여 스케줄 할 수 있다.