[운영체제] 07. 스케줄러

Korean translation of Operating Systems: Three Easy Pieces
Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau(University of Wisconsin-Madison), translation by Youjip Won, Minkyu Park, Sungjin Lee
위 교재를 읽고 공부하며 작성한 글으로, 잘못된 내용이 있을 수 있습니다. 글에서 사용된 이미지의 출처는 위 교재입니다.

 

07장의 핵심 질문 : 스케줄링 정책은 어떻게 개발하는가?

---

📍 워크로드에 대한 5가지 가정

다음에 어떤 프로세스를 실행할 지는 스케줄링 정책(Scheduling policy)에 의해 결정된다. 먼저 프로세스에 대해 5가지의 가정을 하고, 설명을 시작하겠다. 이 가정들은 현실과 거리가 멀다. 점차 이 가정들을 하나씩 무너뜨리면서 설명을 진행할 것이니까 일단 받아들이고 공부해보자. 

1. 모든 작업은 같은 시간 동안 실행된다.
2. 모든 작업은 동시에 도착한다.
3. 각 작업은 시작되면 완료될 때까지 실행된다.
4. 모든 작업은 CPU만 사용한다.(즉, 입출력을 수행하지 않는다.)
5. 각 작업의 실행 시간은 사전에 알려져 있다.

▲ 워크로드(workload)에 대한 가정

---

📍 스케줄링 평가 항목 : 반환 시간, 공정성

스케줄링 정책을 비교하려면 평가 항목(scheduling metric)이 있어야 한다. 스케줄링 평가 항목은 다양하게 존재하는데, 그 중 하나는 반환 시간(turnaround time)이다. 작업 반환 시간은 작업이 완료된 시각에서 작업이 시스템에 도착한 시간을 뺀 시간을 정의된다.

$T_{turnaround} = T_{completion} - T_{arrival}$

반환 시간은 성능 측면에서의 평가 기준이다. 또 다른 평가 기준으로는 공정성(fairness)가 있다. 성능과 공정성은 스케줄링에서 서로 상충되는 목표이다.

---

📍 선입선출(FIFO, 선도착 선처리 FCFS)

먼저 가장 기초적인 선입선출 알고리즘에 대해 알아보자. 선입 선출(FIFO, First In First Out) 또는 선도착선처리(Fisrt Come Fisrt Served, FCFS)라고도 불린다. FIFO는 단순하고 구현하기가 쉽다.

시스템에 3개의 작업 A, B, C가 거의 동시에 도착했다고 가정하자.($T_{arrival}$ = 0). 근데 간발의 차이로 A,B,C 순서대로 도착했다. 각 작업은 10초 동안 실행된다고 하면 이 작업들의 평균 반환 시간은?

• A의 반환 시간 : 10 - 0 = 10
• B의 반환 시간 : 20 - 0 = 20
• C의 반환 시간 : 30 - 0 = 30
• A, B, C의 평균 반환 시간 : $\frac{(10+20+30)}{3} = 20$

 

📢 이때 1번 가정을 완화한다면?
모든 작업은 같은 시간 동안 실행된다. ➡︎ 작업의 실행 시간은 같지 않을 수 있다.

100초 동안 실행되는 A, 10초 동안 실행되는 B, C를 FIFO 스케줄링으로 실행시킨다고 하자. 그러면 이 작업들의 평균 반환 시간은?

• A의 반환 시간 : 100 - 0 = 100
• B의 반환 시간 : 110 - 0 = 110
• C의 반환 시간 : 120 - 0 = 120
• A, B, C의 평균 반환 시간 : $\frac{(100+110+120)}{3} = 110$

평균 반환 시간이 매우 길어졌다. 이 문제점을 convoy effect라고 한다. 짧은 시간 동안 자원을 사용할 프로세스들이 자원을 오랫동안 사용하는 프로세스의 종료를 기다리는 현상을 말한다.

이 문제점을 해결하기 위해서는 FIFO 말고 다른 알고리즘이 필요하겠다.

---

📍 최단 작업 우선(Shortest Job First, SJF)

최단 작업 우선(SJF) 알고리즘은 가장 짧은 실행 시간을 가진 작업을 먼저 실행시킨다. 앞에서 보았던 예에 SJF를 적용해보자.
100초 동안 실행되는 A, 10초 동안 실행되는 B, C를 SJF 스케줄링으로 실행시킨다고 하자. 그러면 이 작업들의 평균 반환 시간은?

• B의 반환 시간 : 10 - 0 = 10
• C의 반환 시간 : 20 - 0 = 20
• A의 반환 시간 : 120 - 0 = 120
• A, B, C의 평균 반환 시간 : $\frac{(10+20+120)}{3} = 50$

평균 반환 시간이 50으로 훨씬 줄어들었다. 

📢 이때 2번 가정을 완화한다면?
모든 작업은 동시에 도착한다. ➡︎ 모든 작업은 동시에 도착하는 것이 아닌, 임의의 시간에 도착할 수 있다.

t=0에 도착하고 100초 동안 실행되는 A, t=10에 도착하고 10초 동안 실행되는 B, C를 SJF 스케줄링으로 실행시킨다고 하자. 이 작업들의 평균 반환 시간은?

• A의 반환 시간 : 100 - 0 = 100
• B의 반환 시간 : 110 - 10 = 100
• C의 반환 시간 : 120 - 10 = 110
• A, B, C의 평균 반환 시간 : $\frac{(100+100+110)}{3} = 103.33$

B,C가 A 바로 뒤에 도착한다고 하더라도 A가 끝날 때까지 기다릴 수밖에 없어서 convoy 문제가 다시 발생한다.
이를 해결하기 위해 또 다른 알고리즘이 등장한다. 이 알고리즘은 가정 3번을 완화한다.

📢 3번 가정을 완화한다면?
각 작업은 시작되면 완료될 때까지 실행된다.  ➡︎  각 작업은 실행 중에 중지될 수 있다.

---

📍 최소 잔여시간 우선(Shortest Time-to-Completion First, STCF)

최단 잔여시간 우선(STCF) 혹은 선점형 최단 작업 우선(Preemptive Shortest Job First, PSJF)을 이용할 수 있다. 이 스케줄러는 남아 있는 작업과 새로운 작업의 잔여 실행 시간을 계산하고 그 중 가장 적은 잔여 실행 식나을 가진 작업을 스케줄한다. 위의 예를 STCF로 다시 실행시켜보자.
t=0에 도착하고 100초 동안 실행되는 A, t=10에 도착하고 10초 동안 실행되는 B, C를 STCF 스케줄링으로 실행시킨다고 하자. 이 작업들의 평균 반환 시간은?

• A의 반환 시간 : 120 - 0 = 120
• B의 반환 시간 : 20 - 10 = 10
• C의 반환 시간 : 30 - 10 = 20
• A, B, C의 평균 반환 시간 : $\frac{(120+10+20)}{3} = 50$

평균 반환 시간이 많이 단축되었다.

---

📍 새로운 스케줄링 평가 항목 : 응답 시간

작업의 길이를 미리 알고 있고(가정 5), 작업이 오직 CPU만 사용하며(가정 4), 평가 기준이 반환 시간 하나라면 STCF는 매우 훌륭한 정책이다. 하지만 시분할 컴퓨터가 등장하면서 시스템과 사용자의 원활한 상호작용이 중요해졌다. 그러면서 응답 시간(response time)이 스케줄링 평가 항목으로 새롭게 등장했다. 응답시간은 작업이 도착할 때부터 처음 스케줄 될 때까지의 시간으로 정의된다.

$T_{response} = T_{firstrun} - T_{arrival}$

STCF 같은 정책들은 반환 시간을 평가기준으로 삼으면 좋은 스케줄링 정책이지만, 평가기준이 응답 시간이라면 그리 좋지 않다.
이 문제를 해결하기 위한 스케줄링이 라운드 로빈(Round-Robin, RR)이다.

---

📍 라운드 로빈 (Round-Robin, RR)

RR은 작업이 끝날 때까지 기다리지 않는다. 대신 일정 시간 동안 실행한 후 실행 큐의 다음 작업으로 전환한다. 

...