[Operating System] CPU Scheduling (3)

Multilevel Queue Scheduling

• highest-priority access를 위해서는 O(n) search를 필요로 한다.
  

• multilevel queue

  • 각각의 priority에 대해서 큐를 만들게 되면 priority scheduling이 highest-priority queue에 있는 프로세스만 스케줄하는 것으로 바뀌게 된다.
  • priority scheduling이 round-robin과 결합했을 때에도 잘 동작한다 : 만약 highest priority queue 안에 여러 프로세스가 있을 경우, round-robin order로 실행된다.
  • 가장 일반화된 접근 방식은 각 프로세스에 priority가 부여되고, 프로세스는 실행시간 동안 같은 queue에 남아있게 된다.
  • multilevel queue scheduling algorithm은 process type에 따라서 나누어지는 데에도 사용된다.
    • ex) foreground(interactive), background(batch) process로 나눌 수 있다. 이 둘은 response-time에서 차이가 나기 때문에 scheduling need가 다를 수 있다. 이렇게 서로 다른 두 개의 queue에 두 종류로 나누어서 프로세스들을 넣고, 각 queue에서 필요에 따라 서로 다른 scheduling algorithm을 실행할 수도 있다.
  • queue간에도 schedule 되어야 하는데, 보통 fixed-priority preemptive scheduling이 이루어진다. ex) real-time queue may have absolute priority over the interactive queue.
    • ex) 아래 4개의 queue를 바탕으로 multilevel queue scheduling algorithm을 적용해 보자. 우선순위가 높은 순서대로 나열한 것이다.
      1. Real-time processes
      2. System processes
      3. Interactive processes
      4. Batch processes
      • Each queue has absolute priority over lower-priority queues. 그래서 예를들어 batch process의 경우 1,2,3번 queue가 다 비기 전까지 실행될 수 없고, batch 프로세스가 실행중일 때 system process가 들어오면 preempted가 된다.
  • 또 다른 방법 : queue간에 time-slice를 한다.
    • 각각의 queue는 CPU time의 일부를 할당받게 되고, 그 시간 내에서 각 queue에서의 scheduling이 이루어지게 된다.
    • ex) foreground-background queue
      • foreground queue의 경우 CPU time의 80%를 할당받고 RR scheduling을 시행한다.
      • background queue의 경우 CPU time의 20%를 할당받고 FCFS를 시행한다.

Multilevel Feedback Queue Scheduling

• 앞서 말한 multilevel queue scheduling algorithm에서는, process들은 시스템에 들어올 때 부터 하나의 queue에 영구적으로 들어가게 된다. 다른 queue로 이동할 수 없다. 이는 scheduling overhead를 줄이는 데에는 도움이 되지만, 유연하지 못하다.
• multilevel feedback queue는 process가 queue간에 움직일 수 있게 한다.
  • 아이디어 : 프로세스를 각자의 CPU burst의 특성에 따라서 나눈다.
  • 너무 많은 CPU time을 사용한 프로세스는 lower-priority queue에 가고, I/O-bound와 interactive process를 higher-priority queue로 가게 된다.
  • 또한 lower-priority queue에 너무 오래 있는 process는 higher-priority queue로 가게 되어 이러한 aging을 통해 starvation을 막을 수 있다.
  • ex) 0 ~ 2까지의 3개의 큐로 이루어진 multilevel feedback queue
    
    • scheduler는 queue 0에 있는 모든 프로세스를 실행하고, queue 1에 있는 프로세스는 queue 0이 모두 비어있을 때에만 실행된다. 물론 여기서 preempt도 존재한다.
    • entering process는 queue 0에 놓이게 된다. queue 0의 프로세스는 8ms의 time quantum을 가지게 되고, 그 시간안에 끝나지 않으면 다음 queue의 tail로 들어가게 된다. 마찬가지로 queue 1의 프로세스는 16ms의 time quantum을 가지고 queue 0과 같이 동작한다. starvation을 막기 위해 오래 기다리는 프로세스는 higher-priority queue로 이동한다.
    • 이 알고리즘은 CPU burst가 8ms 이하인 프로세스에게 highest priority를 부여한다.
    • 8 ~ 24ms의 프로세스는 나름 빨리 수행되지만, 그 이하인 프로세스에 비해서는 느리다.
    • 긴 프로세스들은 자동으로 queue 2로 떨어지게 된다.
• 일반적으로, multilevel feedback queue scheduler는 다음 parameters로 정의된다 :
  • The number of queues
  • The scheduling algorithm for each queue
  • The method used to determine when to upgrade a process to a higher-priority queue
  • The method used to determine when to demote a process to a lower-priority queue
  • The method used to determine which queue a process will enter when that process needs service
• multilevel feedback queue scheduler는 가장 general한 CPU-scheduling algorithm에 해당한다. -> system에 따라서 자세한 디자인이 달라지지만, 그만큼 복잡한 알고리즘이긴 하다.

참고 자료

• Abraham Silberschatz, Operating System Concepts, 10th edition