운영체제 05 : 스케줄링

개요

 

 일반적으로 프로세서(CPU)의 개수보다 프로세스의 개수가 많기 때문에, 비둘기집의 원리를 근거로 반드시 한 프로세서(CPU)는 다수의 프로세스를 수행해야합니다.

 

현대에서는 멀티 쓰레딩을 지원하기 때문에, 정확히 말하면 프로세서는 다수의 쓰레드를 실행하고, 여기에 하이퍼 쓰레드를 지원하는 프로세서는 동시에 실행하기도 합니다만 운영체제를 공부함에 있어 심화된 내용이므로 현재는 프로세스 단위로 이야기 하겠습니다.

 

 그렇다면, 한 CPU는 한번에 한 프로세스만 실행시킬 수 있다고 이번 포스트에서는 가정합시다.(실제 현대 프로세서의 아키텍쳐는 프로세스 단위의 스케줄링을 하지도 않고, 한 개의 쓰레드만 실행하지도 않습니다)

 여기에서 CPU가 어떤 프로세스를 실행시킬 것인가에 대한 운영체제가 제시하는 정답을 스케줄링 정책이라고 합니다. 오늘은 이 정책들에 대하여 논의해 보겠습니다.

---

평가

 

정책들을 논의하기 전에, 이러한 정책들을 평가할 지표를 먼저 소개하겠습니다. 

• 반환시간 : 반환시간 = 프로세스의 완료시간 - 프로세스의 도착시간

• 응답시간 : 응답시간 = 프로세스가 처음으로 수행되는 시간 - 프로세스의 도착 시간

반환시간은 프로세스들이 도착한 뒤 얼마나 빠르게 완료하는가? 에 대한 지표이고, 응답시간은 프로세스가 도착한 뒤 얼마나 빠르게 실행되었는가? 에 대한 지표입니다.

 

예를 들어 어떤 파일의 압축을 해제하려고 .zip파일을 더블클릭했다고 합시다. 그러면, 알집프로세스가 스케줄러에게 도착하게 되는데 응답시간이 늦으면 사용자는 클릭을 했음에도 프로그램이 한참 뒤에 뜨게 될 것입니다. 반대로 반환시간이 늦으면 사용자는 압축을 해제하는 것에 오랜시간이 걸릴 것입니다.

 

 

---

정책

어떤 프로세스를 먼저 실행시킬것인가에 대한 스케줄링 정책으로 다룰 것은 다음과 같습니다. 문제는 오늘 다룰 스케줄링 정책들은 아주 큰 착각을 하고 있는 스케줄링 정책들입니다. 읽으시면서 그 착각이 무엇인지 상상해봅시다.

---

비선점 스케줄링

수행하고 있는 프로세스를 완료한 뒤 다른 프로세스를 수행하는 스케줄링 방법입니다. 실행 중간에 프로세스를 바꾸지 않습니다.(문맥교환이 X)

---

(1) FCFS (First come fist served)

 

이 정책은 FIFO로도 불리고 한국어로는 선입선출, 선도착선처리 스케줄링이라고도 불립니다. 말 그대로 먼저 온 task를 먼저 수행하자는 정책입니다. 

 

이 방식의 문제는 Convey effect라고 하는 현상에서 나옵니다. (www.geeksforgeeks.org/convoy-effect-operating-systems/). Convey effect란 긴 작업을 다른 작은 작업들이 기다리는 것을 말합니다.

주유소에 주유를 하러 갔을 때, 내 순번 앞에 16톤 트럭이 먼저 도착해서 주유를 하기 위해 기다리고 있다고 생각해봅시다. 해당 트럭의 뒤의 모든 차는 한참을 기다린 뒤, 주유를 시작합니다.  즉, 내 주유에 걸리는 시간은 내 앞의 모든 차의 주유시간 + 내 차의 주유시간 이기 때문에 반환시간이 굉장히 늦게 됩니다. 막막하지 않나요?

---

(2) SJF (Shortest job first)

 

 최단 작업 우선 정책은 가장 짧은 시간이 필요한 작업을 먼저 수행하는 것입니다. 이를 통해 Convey effect를 해결합니다. 즉, 작은 일부터 해결하자는 문제입니다. 이를 통해 평균 반환시간을 줄일 수 있습니다. 그러나, 문제는 여전히 존재합니다. 비선점 스케줄링이기 때문에, 나보다 일찍 도착해서 이미 수행되고 있는 작업에 대해서는 영락없이 기다리고 있어야 하기 때문에, 위(1)에서 제시한 상황은 해결할 수 없습니다.

 

---

선점 스케줄링

 그렇다면, 이미 기름을 넣고 있는 트럭을 다른 소형차가 오면 중지시키고 먼저하게 한다면 어떨까요? 이렇게 수행하고 있는 프로세스를 바꿀 수 있는 정책들을 선점형 스케줄링 정책이라 합니다. 수행하던 프로세스 대신 다른 프로세스를 수행합니다.(문맥교환 O)

 

---

(1) STCF (Shortest time to completion first) = PSJF

 

남은 완료시간이 가장 짧은 것을 먼저 수행합니다. 참 그리디(탐욕)적인 알고리즘입니다. 그 순간 가장 빨리할 수 있는 것을 먼저하면 당연하게도 가장 짧은 평균 반환시간을 얻을 수 있습니다. 우리가 수능 수학을 풀 때, 쉬운 문제를 먼저 풀면, 각 문제들을 완료한 시각의 평균이 가장 작기 때문에 그런 선택을 하는 것과 동일합니다.(이 사실을 모르더라도 사람은 본능적으로 그리디합니다. 마시멜로 이야기를 생각해보세요!)

 

문제는 SJF, STCF는 응답시간이 너무 길다는 것입니다. 컴퓨터를 켜서 뭘 하나 할려고 할 때마다, 다른 작업부터 수행한다고 생각해보세요! 심지어는 게임과 같이 좀 무거운 프로세스를 하려고 하면 다른 가벼운 프로세스들이 끼어들어 영원히 실행을 못한다면요?

 

---

(2) RR (Round robin)

 

타이머 인터럽트 주기의 배수를 타임슬라이스로 선정합니다.(스케줄링 퀀텀, 타임 퀀텀, 문맥교환 주기 등 부르는 명칭이 다양합니다.) 인터럽트 주기의 배수로 해야되는 이유는 문맥교환을 하기 위해서 입니다.

 

 이 타임슬라이스마다 실행하는 프로세스를 변경하는 정책입니다. 이를 통해 좋은 평균 응답시간을 얻을 수 있습니다.   그런데, 역시나 이것도 단점이 있습니다. 쇼핑몰에서 카운터에서 계산할 때, 한 상품 찍고 다음 사람 상품 찍어주고, 모든 사람 상품을 하나씩 찍어준 뒤 내 상품 하나 더 찍고 한다고 생각해봅시다. 먼저 드는 생각이 무엇인가요? 와... 한참 걸리겠다. 아닌가요? 평균 반환시간이 굉장히 안좋게 되는 것 입니다.

 

 또한, 상품을 찍어줄 사람을 매번 바꿔야 하니 귀찮고 복잡합니다. 즉, 문맥교환에 오버헤드가 발생하게 됩니다. 따라서, 전체적인 성능이 저하됩니다. 한마디로, RR은 공정성과 응답시간을 위해 반환시간을 희생하고 성능을 저하시키는 정책입니다.

 

---

이 많은 스케줄링 정책이 착각하는 가장 큰 하나는 운영체제가 프로세스의 수행시간을 알 수 있다는 점입니다. 결국, RR을 제외한 나머지 정책들은 프로세스의 수행시간이 주어졌을때를 가정합니다. 문제는, 운영체제는 커녕 컴퓨터를 쓰는 나조차도 언제까지 게임을 할지는 알 수 없다는 것입니다.

 

 또한, 여전히 논의하자면 끝없는 문제가 많습니다. STCF에서 입출력이 발생한다면? 악의적으로 작업을 짧은 시간의 작업들로 나누어서 보낸다면? 무거운 프로세스를 방해하는 작은 프로세스들이 너무 많다면? 등의 소개드린 스케줄링 정책에서는 해결할 수 없을 것과 같은 많은 문제를 해결하기 위한 방법들을 다음 포스트에서 소개하겠습니다.