[운영체제/OS] CPU 스케쥴링 - (3)

0. 들어가면서

지난 시간에는 FCFS, RR, SJF 스케줄링 기법에 대해 공부했습니다. 그리고 그 중에서 SJF 스케줄링은 Expected burst time이 가장 작은 작업에 우선순위를 높게 할당하는 방식이라고 설명했는데요.

 

이번 글은 어떻게 burst time을 추정해야 하는가에 대해 이야기하는 것으로 시작하려고 합니다.

---

1. CPU Burst time 추정의 한계

CPU burst time을 측정을 위해서는 과거에 이 프로세스가 CPU를 사용했던 시간 기록을 이용하는데요.

 

CPU burst time을 측정하는 크게 두 가지 방법이 있습니다.

• Simple Average : 이 프로세스의 과거 CPU 사용 시간들에 대해 동일한 Weight를 주는 방식으로 평균값을 구한다.
• Exponential Average : 최근에 거쳤던 작업시간이 현재 작업 시간을 결정하는데 큰 영향을 미치리라는 가능성으로 가까운 시간에 대해 더 큰 Weight를 주는 방식으로 평균값을 구한다.  

 

아래는 Simple averaging과 Exponential averaging을 이용했을 때 실제 burst time과 비교한 그래프입니다.

그림을 보면 Exponential averaging 방법이 실제 시간과 조금 더 근접하게 맞춘다는 것을 볼 수 있습니다. 하지만 Exponential Averaging이 모든 burst time을 예측하는데 가장 좋은 방법이라고 할 수도 없고, 실제로는 더 복잡한 과정을 통해 예측이 이루어집니다.

 

그리고 어떻게 모든 프로세스가 과거의 데이터를 그대로 따라서 Burst time이 정해질까요? 거의 불가능에 가깝겠죠.

 

그래서 결국 이전 시간에 살펴본 SJF 스케줄링 기법은 어떻게 CPU burst time을 측정할 것인가에 대한 문제로부터 자유로워지지 못하게 되죠.

---

이어서, 지난 시간에 배운 스케줄링 기법에 더해 조금은 복잡한 스케줄링 기법 몇 가지를 소개해보려고 합니다.

 

2. 멀티레벨 큐(Multi-lelevel Queue) 스케줄링

OS가 복잡해지면서 스케줄링을 하는 방식도 상당히 복잡해졌습니다. 이에 따라 하나의 Ready Queue만 가지고 정말 많은 프로세스들을 관리하기가 어려워졌죠.

 

따라서 다양한 유형의 프로세스들을 관리하기 위해서는 여러 개의 큐를 가지고(Multi-level queue) 각자 다른 알고리즘으로 스케줄링하는 방식이 필요해졌습니다. 그리고 이 필요에 의해 생겨난 스케줄링이 바로 멀티레벨 큐 스케줄링이죠.

 

* 멀티레벨 피드백 큐(Multilevel Feedback Queue Schedulig(MLFQ))

멀티레벨 피드백 큐(Multilevel Feedback Queue) 스케줄링은 한 프로세스가 여러 단계의 큐를 지나면서 각 큐에 배정된 스케줄링 정책을 따르는 방식입니다. 약간 말이 어렵죠?

Multilevel Feedback Queue

위 그림을 보면 가장 상위에 존재하는 큐가 우선순위가 높게 설정되어 있습니다. 이에 따라 가장 아래에 있는 큐는 위쪽의 큐가 모두 비어있는 상태가 되어야 사용이 가능해집니다.

 

MLFQ에서는 첫번째 큐의 Time slice를 작게 해서 I/O bound process인 경우 대부분이 첫 큐에서 끝나서 나가게 하고, CPU bound process의 경우 아래로 내려가게 만듭니다. 그리고 아래로 내려갈수록 Time slice를 조금 더 길게 주는 방식을 채택하죠.

 

그러면 이전에 배운 스케줄링에서 문제가 됐던 CPU bound 프로세스와 I/O bound 프로세스 간의 불공평을 조금 없앨 수 있겠죠? 그리고  작업이 끝난 프로세스를 빨리 내보내고, 밑으로 내려갈수록 Time slice를 길게함으로써 프로세스의 스위칭에 따른 오버헤드도 조금씩 줄어들 것 같습니다.

 

* 한편, 여기서 각 Queue마다 Time slice가 있다는 것은 MLFQ가 Preemptive Schedulig 방식을 취한다는 것을 의미합니다.

 

 

 

---

3. 실시간 시스템 스케줄링(Real-Time Scheduling)

실시간 시스템 스케줄링은 쉽게 말해 "이 프로세스를 주어진 시간 안에 끝내라"는 스케줄링 기법인데요. 제조 산업이나 공정, 방위 산업 등에서 중요한 스케줄링 방식입니다.

 

그리고 이 스케줄링 기법에는 두 가지 갈래가 존재합니다.

 

첫번째 방식은 Hard Real-Time Scheduling입니다. 이 방식은 각 프로세스가 끝나는 시점이 무조건 데드라인 안에 들어와야 한다는 모티브를 가지고 있는데요.

 

이를 위해서는 각 프로세스가 그들이 필요한 사용량을 제공해야 하고, 최악의 경우에 어느 정도 시간이 소요되는지에 대한 고려도 해야합니다.

 

두번째 방식은 Soft Real-Time Scheduling입니다. 이 방식에서는 프로세스가 종료 데드라인을 못 맞춰도 프로그램이 흘러가기는 합니다. 따라서 엄밀히 따지자면 실시간 시스템의 의미가 퇴색되기는 하죠.

 

그럼에도 불구하고, 이 스케줄링 기법에서도 역시 중요한 프로세스에게 더 높은 우선순위를 주고 우선순위 스케줄링을 돌립니다. 그래서 급한 녀석을 빨리 처리하게 하죠.

 

그러면 이 스케줄링 방식은 위의 Hard Real-time 스케줄링보다는 좀 낫지 않을까요? 약간의 자유도 주어지면서 급한 녀석을 빨리 처리할 수 있으니까요. 하지만 이 스케줄링 기법 역시 문제가 있습니다. 

 

* Priority Inversion Problem(우선순위 역전 문제)

우선순위 역전 문제

위 그림을 이해해보면 우선순위가 역전된다는 문제가 무엇인지 바로 이해할 수 있을 것 같은데요.

 

위 그림에서는 P1, P2, P3와 같이 우선순위가 각기 다른 프로세스나 쓰레드가 존재합니다. 그리고 처음에 우선 순위가 낮은 프로세스(P3)가 들어와서 작업을 수행하며 공유 메모리에 대해 Lock을 걸었습니다.

 

그런데 시간이 지나 Time quantum이 끝나서 Lock을 해놓은 상태로 P2에게 작업권이 넘어가고, 또 시간이 지나 더 높은 우선순위를 가진 프로세스에게(P3) 작업권이 넘어간 상황입니다.

 

이 때, 가장 위에 존재하는 프로세스(P3)는 P1이 사용했던 것과 같은 공유 메모리를 사용하려고 했는데, 낮은 우선순위의 프로세스(P1)가 blocking 중이어서 사용하지 못하게 됐습니다.

 

그러면 P1 프로세스가 작업을 안하니까 그 아래 우선순위를 가진(P2)가 CPU를 사용하게 되죠. 즉, 공유 메모리에 대한 접근 불가로 가장 우선순위가 높은 프로세스가 정작 CPU를 할당받지 못하고, 그보다 아래에 있는 프로세스에게 우선순위가 역전되버리는 것입니다.

 

이 문제를 해결하기 위해서는 순간적으로 문제의 원인이 됐던 P3 프로세스에 대해 P1이 자신의 우선순위를 상속해주어야 합니다. 그러면 낮은 레벨에 있던 P3 프로세스가 얼른 작업을 끝내고 다시 높은 우선순위 프로세스가 작업을 할 수 있도록 하죠. 급한 불은 껐지만, 우선순위가 역전되는 현상 자체는 어쩔 수 없죠.

 

 

---

4. 마치면서

사실 스케줄링 기법은 워낙 방법론이 많고 각 운영체제마다, 사용자마다 다르게 사용되며 지금도 연구되고 있기 때문에 모든 것을 다 이해할 수는 없습니다.

 

하지만 지금까지 배운 내용을 토대로 왜 CPU 스케줄링이 필요하며 각 스케줄링 기법이 어떤 장점과 단점이 있는지를 이해하면 될 것 같습니다.

 

이상으로 CPU 스케줄링에 대한 정리를 마치겠습니다.