[운영체제(OS)] CPU 스케줄링 - (2) 스케줄링 알고리즘

0.🚶들어가며

 지난 글에서는 CPU 스케줄링이 무엇인지에 대해 알아보았습니다. 이번 글에서는 CPU 스케줄링 성능을 측정할 때 척도는 무엇이 있는지, 스케줄링 알고리즘은 어떤 것들이 있는지에 대해 알아보겠습니다.

---

1.⏰CPU 스케줄링 성능 척도

 스케줄링 알고리즘에 대해 알아보기 전, 각 알고리즘의 성능은 어떤 기준으로 측정할 것인지에 대해 먼저 알아보겠습니다.

 

 CPU 스케줄링의 성능은 시스템 입장에서의 성능과 사용자 입장에서의 성능, 두 가지로 나누어 고려해볼 수 있습니다. 시스템 입장에서는 CPU를 쉬지 않고 최대한 많이 돌리는 것이 중요하고, 사용자 입장에서는 자신이 요청한 작업이 빨리 처리되는 것이 중요합니다. 하지만 두 입장 모두를 만족시키는 것이 쉽지 않습니다. 따라서 상황에 맞게 CPU 스케줄링을 설계하는 것이죠.

 

 시스템 입장과 사용자 입장은 음식점에서 사장과 손님의 입장으로 비유할 수 있습니다. 사장은 가게에 손님을 많이 받기를 원하고 손님은 음식을 빨리 받기를 원하죠. 이러한 관점에서 아래의 성능 척도를 살펴보시면 조금 더 이해에 도움이 될 것 같습니다.

1) 시스템 입장에서의 성능 척도

• CPU Utilization (CPU 이용률) : 전체 시간 중 CPU가 일한 시간의 비율을 말합니다.
• Throughput (처리량) : 단위 시간당 처리량 즉, 단위 시간당 프로세스를 몇개 완료시켰는가를 말합니다. 

2) 사용자 입장에서의 성능 척도

• Waiting time (대기 시간) : 프로세스가 Ready queue에서 기다린 시간입니다.
• Response time (응답 시간) : 프로세스가 최초로 CPU를 얻기까지 걸린 시간입니다.
• Turnaround Time (소요시간, 반환 시간) : 프로세스가 처음 도착해서 끝나기까지 걸린 시간입니다.

---

2. FCFS(First-Come First-Served) 스케줄링

 FCFS 스케줄링의 경우 먼저 온 프로세스를 먼저 처리해주는 방식입니다. Non-preemptive 방식이구요. 개념 자체도 쉽고 굉장히 공평해보입니다. 실생활에서 줄서기와 비슷한 상황인것이죠.

 

 하지만 FCFS 알고리즘의 경우 도착한 프로세스의 순서에 따라 Average waiting time이 크게 달라지는 단점이 있습니다. 먼저 온 프로세스가 엄청 오래걸리는 경우 그 뒤 프로세스들이 많은 시간을 기다려야하는 상황이 생기게 됩니다. 간편한 만큼 불합리한 점이 많은 스케줄링 알고리즘입니다. 특히 IO 작업이 많은 프로세스의 경우 더욱 불합리하게 느낄 수 있는 스케줄링 방식입니다.

---

3. SJF(Shortest Job First) 스케줄링

 SJF는 FCFS의 알고리즘을 개선한 방식입니다. FCFS에서는 수행 시간이 짧은 프로세스들이 오래 걸리는 프로세스때문에 과도하게 많이 기다려야한다는 문제점이 있었습니다. 이러한 점을 보완하기 위해 SJF에서는 CPU를 가장 짧게 쓰려는 프로세스에게 CPU를 먼저 주는 방식을 사용합니다. 이런 방식으로 스케줄링을 하게되면 wating time 측면에서 가장 최적의 방법이 됩니다. 즉, 주어진 프로세스들에 대해 minimum average waiting time을 보장하게 되는 것이죠.

 

 SJF의 경우 Non-preemptive, Preemptive(SRTF) 두 가지 방식으로 구현할 수 있습니다. Non-preemptive 방식의 경우 일단 프로세스가 CPU를 잡으면 CPU burst가 완료될 때까지 CPU를 빼앗기지 않습니다. 반면에 Preemptive 방식에서는 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가진 새 프로세스가 도착하면 CPU를 빼앗아 버립니다. 

 

 SJF의 경우 FCFS의 문제점을 잘 해결한 것처럼 보입니다! 하지만 여기에도 치명적인 약점이 두가지 있는데요. 아래에서 살펴보겠습니다.

• Starvation이 발생한다. 즉 waiting time면에서 너무 효율성만 따지다보니 CPU burst time이 긴 프로세스의 경우 영원히 CPU를 못 얻는 경우가 생길 수 있습니다. 식당에서 오래 걸리는 음식을 주문했다고 계속해서 나의 음식이 늦어지는 상황인 것이죠. 이 역시 긴 CPU 사용시간을 가진 프로세스 입장에서는 상당히 불합리합니다.
• 프로세스의 CPU burst time을 정확히 알 수가 없습니다. 프로세스의 CPU burst time을 예측하고자 할 때 과거 CPU burst time을 가지고 예측은 가능할 수 있습니다. 하지만 하나의 프로세스의 CPU 사용 시간을 정확히, 미리 알기란 어렵습니다. 

---

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

 Priority Scheduling은 정수로 우선순위 값을 설정하여 스케줄링하는 방식입니다. 즉, 우선순위가 높은 프로세스를 먼저 처리해주는 방식이죠. 잘 생각해보면 SJF도 일종의 우선순위 스케줄링입니다. SJF의 경우 CPU 사용시간을 기준으로 우선순위를 설정한 것이죠. 또한 우선순위 스케줄링 방식 역시 SJF와 SRTF 차이와 같이 Preemptive & Non-Preemptive 방식으로 구현이 가능합니다. CPU를 사용하고 있는 프로세스보다 우선순위가 높은 프로세스가 들어왔을 때 CPU를 빼앗을지 말지에 대한 여부를 정해서 스케줄링 할 수 있다는 뜻이죠.

 

 우선순위 스케줄링 역시 SJF처럼 Starvation 문제가 있을 수 있습니다. 하지만 여기서는 문제 해결 가능성이 있는데요. 바로 Aging이라는 기법을 사용하여 이를 해결합니다. Aging이란 프로세스가 기다리는 시간이 길어질수록 우선순위를 높여 한 프로세스가 무한정 기다리지는 않도록 해주는 방법입니다. 

---

5. RR(Round Robin)

 Round Robin 스케줄링 방식에서는 각 프로세스에 동일한 크기의 시간(time slice)을 할당해줍니다. 할당 시간이 지나면 프로세스를 CPU에서 빼앗고 다시 Ready Queue에 제일 뒤에 줄을 서게합니다. 이러한 방식은 n개의 프로세스가 Ready Queue에 있고 time slice가 t일 때 어떤 프로세스도 (n - 1) * t 이상 기다리지 않게 해줍니다. 사용자 입장의 성능 면에서 좋을 수 있겠죠. 

 

 이때 time slice를 어느 정도로 설정해야할지도 관건일 수 있습니다. 만약 time slice가 너무 커진다면 사실상 FCFS 알고리즘이 되어버리며 time slice가 너무 작아진다면 Context Switch에 대한 오버헤드가 커지게 됩니다. 따라서 time slice를 IO bound process의 CPU burst time 정도로 잡게된다면 합리적이고 일반적으로 10ms ~ 100ms 정도로 설정하게 됩니다. 

 

 RR 스케줄링 방식은 일반적으로 SJF보다 turnaround time은 길지만 response time이 작습니다. 따라서 Interactive 환경에서 장점이 될 수 있습니다.

---

6. Multilevel Queue

 Multilevel Queue는 지금까지 소개한 스케줄링 방식과 다르게 Ready Queue를 여러 개로 분할하여 작업합니다. 우선순위가 높은 큐에는 System Process나 Interactive Process들을 삽입하고 CPU bound process의 경우 후순위 큐에 삽입하게 됩니다.

 

 또한 각 큐마다 독립적인 스케줄링 알고리즘을 적용하여 효율성을 높일 수 있는데요. 예를 들어 Interactive process들이 있는 큐에서는 RR 알고리즘을, Batch Process들이 있는 큐에는 FCFS 알고리즘을 적용하여 각 프로세스의 성격에 맞게 효율적인 알고리즘을 적용할 수 있습니다.

 

 Multilevel Queue에서는 큐들에 대한 스케줄링 역시 필요합니다. 가장 우선순위가 높은 큐부터 비워나가는 방식이 있고 각 큐마다 CPU 시간을 적절한 비율로 할당해주는 경우가 있습니다. 전자의 경우 우선순위가 높은 프로세스부터 빠르게 처리해 나아갈 수 있겠지만 Starvation 가능성이 생길 위험이 있어 후자처럼 보완하는 경우가 있는 것이죠.

---

7. Multilevel Feedback Queue

 Multilevel Feedback Queue 역시 큐를 여러 개로 분할했다는 점에서는 Multilevel Queue와 동일합니다. 다른 점은 바로 프로세스가 다른 큐로 이동이 가능하다는 것입니다. 우선순위가 낮은 큐에 있는 프로세스가 Starvation 가능성이 있다는 점을 고려했을 때 다른 큐로 이동한다는 것은 일종의 Aging 기법 구현 방식 중 하나가 될 수 있습니다. 

 

 프로세스가 다른 큐로 이동하는 방식을 구현하는 방법은 다양합니다. 이때 프로세스를 상위 큐로 보내는 기준, 하위큐로 보낼 기준 등을 고려하고 그 기준을 토대로 구현하는 것입니다.

Multilevel Feedback Queue의 예시

 위 방식은 Multilevel Feedback Queue의 대표적인 구현 예시입니다. 새로운 프로세스는 무조건 우선순위가 높은 큐에 들어가서 8ms의 time slice를 받고 계속해서 우선순위가 낮은 큐로 진행해나아가는 방식입니다!

---

8.💨나가며

 이번 글에서는 스케줄링 성능 척도와 스케줄링 알고리즘에 대해 알아보았습니다. 

 

 CPU 스케줄링은 멀티태스킹 환경에서 굉장히 중요한 주제라고 생각합니다. 스케줄링 알고리즘들은 종류가 굉장히 다양한데 본 글에서 소개한 알고리즘들을 순서대로 보면 어떠한 흐름으로 계속해서 단점을 보완하려했는지가 고스란히 느껴지는 것 같고 이 점에 대해 집중해서 본다면 더 와닿게 이해할 수 있을 것 같습니다.