[운영체제] 11. CPU Scheduling (2) - CPU 스케줄링 알고리즘 : Multilevel Queue & Multilevel Feedback Queue

스케줄링 알고리즘은 크게 non-preemptive / preemptive 방식으로 나뉘게 된다. 

Scheduling Criteria 성능 척도 

1. CPU utilization (이용률) : 전체 시간중에서 CPU 가 일한 시간. CPU 는 가능한 busy 해야 한다. 
   - CPU 는 비싼 자원이기 때문에 효율적으로 활용하기 위해서는 CPU 는 항상 일을 해야 한다. 
2. Throughput (처리량) : 주어진 시간동안 몇개의 프로세스들을 완료 했는가 
3. Turnaround time (소요시간, 반환시간) : 특정 process를 실행하는데 걸리는 시간 
4. Waiting time (대기 시간) : 프로세스가 ready queue에서 대기하고 있는 시간 
5. Response time (응답 시간) : 요청이 왔을 때 처음으로 응답하기까지 걸린 시간 
   - 최초로 CPU 를 얻게 되기까지 걸린 시간 

• System 입장에서의 성능 척도 : 1, 2
• 프로그램 입장에서 성능 척도 : 3, 4, 5

Multilevel Queue 

1. Ready queue 를 여러개로 분할 

• foreground : interactive 한 job 
• background : batch job 

2. 각 queue는 독립적인 스케줄링 알고리즘을 가진다. 

• foreground : Round Robin 
• background : FCFS

3. queue에 대한 스케줄링

1) Fixed priority scheduling 

• foreground job 을 모두 실행한 후, background job을 실행 
• starvation 이 발생할 수 있다. 

2) Time Slice 사용하는 스케줄링 - starvation 을 예방한다. 

• 각 queue에 CPU time 을 적절한 비율로 할당한다. 
• ex. foreground in RR 이 80%, background in FCFS 에 20% 

but 차별을 두고 있는 방법으로, 우선순위를 완전히 바꿀 수는 없으므로 융통성이 적다는 단점이 있다. 이를 해결하기 위해 multilevel feedback queue가 등장했다. 

Multilevel Feedback Queue 

처음 들어온 프로세스는 우선순위가 가장 높은 queue (그림에서는 Queue1)에 넣는다.

• 우선순위가 가장 높은 queue는 RR에서 할당 시간을 짧게 준다. (time quantum=8)
• 이보다 우선순위가 낮은 queue는 할당 시간을 늘린다. (time quantum=16)
• 마지막으로 내려오면 FCFS 방식으로 운영한다. 
• 현재 queue에서 작업을 끝내지 못하면 한단계 아래로 강등하는 방식으로 운영된다. 

즉, 다단계 피드백 큐는 CPU 시간을 짧게 먹는 프로세스에게 우선순위를 크게 부여하는 방식이다. 

 

특이한 경우에서의 스케줄링 

1. Multiple-Processor Scheduling 

- CPU가 여러개인 경우의 스케줄링이다. 

1) processor 성능이 동일할 때 

• queue를 한줄로 세워서 각 processor 가 알아서 꺼내가도록 처리 
• 반드시 특정 processor 에서 수행되어야 하는 프로세스가 있는 경우는 처리하기 어려울 것이다. 

2) Load sharing 

• 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 분산시키는 메커니즘 
• 별개의 queue를 두는 방법 vs 공통 queue를 사용하는 방법 

3) Symmetric Multiprocessing (대칭 다중 처리)

각 프로세서가 스스로 스케줄링할 수 있다. 

4) Asymmetric Multiprocessing 

하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 그 방식에 따른다. 

 

Real-Time Scheduling 

1) Hard real-time systems 

CPU에서 정해진 시간 안에 처리가 끝나는 것을 반드시 보장해야 함. 
주어진 Job들을 미리 스케줄링하여 데드라인을 보장하는 방식으로 운영된다. 
주기성을 가지는 경우가 많다. (ex. 10초에 한번씩..)

2) Soft real-time systems 

일반 프로세스에 비해 높은 priority 를 갖도록 해야함. 

Thread Scheduling 

1. Local Scheduling 

User level thread의 경우, 사용자 수준의 thread library 에 의해 스케줄링 된다. OS가 아니라, 사용자 Process 가 직접 내부에서 어떤 thread를 스케줄링할 지 결정될 것이다. 

2. Global Scheduling 

Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정한다.