Scheduling Algorithms - gon2gon2/pintos-kaist GitHub Wiki

• CPU 스케줄링 알고리즘엔 여러 종류가 있다.
• schedule metrics중 내가 원하는 Task를 위해 최적화 할 지표를 선택하고 그에 어울리는 알고리즘을 고른다.

1.FCFS(First-Come, First-Served) Scheduling

• 들어오는 요청 순서대로 처리한다.(non-preemptive)
• 대부분의 경우, Average Waiting Time이 길다.
• Convoy Effect: CPU를 오래 사용하는 job때문에 사용 시간이 짧은 job이 작업을 못하고 기다리는 현상
• context switching overhead가 적어 CPU utilization이 좋다.

2.SJF(Shortest Job First) Scheduling

• 가장 짧은 CPU burst를 가진 job부터 스케줄링 하기 때문에 최적의 waiting time을 낸다.
• non-preemptive와 preemptive 둘 다 가능하다. preemptive 방식은 현재 실행중인 프로세스의 남은 cpu burst보다 더 짧은 프로세스가 ready queue에 도착했을 때, 더 짧은 프로세스를 먼저 수행한다.
• 이 알고리즘은 각 job이 어느정도의 CPU burst를 가질 지 알 수 없기 때문에 현실적으로 불가능하지만, 다음 요청은 이전 요청과 유사할 것이라는 가정하에 exponential average를 사용해 근사치를 예측한다.

3.RR(Round-Robin) Scheduling

• FCFS와 비슷하지만 프로세스간의 스위치가 일어날 수 있도록 preemption이 추가됐다.
• Time Slice 혹은 Time Quantum이라고 불리는 작은 단위시간 동안 ready queue의 맨 앞의 작업을 수행하고, 시간안에 프로세스가 종료된다면 CPU를 자진해서 반납하고 그렇지 않으면 ready queue맨 뒤에 insert한 다음 다음 프로세스를 실행한다.
• RR의 성능은 time quantum에 강하게 의존적이다. 너무 크면 FCFS 방식이 되고, 너무 작으면 context switching overhead가 커진다.
• 대부분 현대 시스템에서는 time quantum을 10~100 milliseconds 사이로 설정한다.
• response time이 짧아지는 장점이 있어 실시간 시스템, 사용자와 상호작용하는 시스템에 적합하다.

4.Priority Scheduling

• 가장 높은 우선순위를 가진 프로세스에게 CPU가 할당되는 방식이다.
• 동일한 우선순위 간에는 FCFS로 수행된다.
• 우선순위의 범위는 07, 04095등 다양하게 설정될 수 있고, 0을 높은 혹은 낮은 우선순위로 설정할 수도 있다.
• non-preemptive, preemptive 둘 다 가능하다. 새로 추가된 프로세스와 진행중인 프로세스 간의 우선순위를 비교하고, 높은 프로세스로 context switching해주면 preemptive 방식이다.
• 우선순위가 낮은 프로세스는 평생(또는 매우 오랜 시간) 대기하게 되는 경우가 있을 수 있다. 이러한 문제를 indefinit blocking 또는 aging이라고 부른다.
• 오래 기다린 프로세스의 우선순위를 올려주는 aging을 도입하거나, round-robin과 결합하여 사용할 수도 있다.
• (SJF 알고리즘은 Priority Scheduling의 특수한 버전이다.)

5.MLQ(Multi-Level Queue) Scheduling

• Priority나 RR 방식의 문제는 모든 ready상태의 프로세스들이 하나의 ready queue에만 저장되기 때문에 큐의 관리방식에 따라 실행시킬 프로세스를 탐색하는데 최악의 경우 O(n)의 시간이 걸린다.
• MLQ는 우선순위에 따라 큐를 여러개로 나눠 관리하는 방식이고, 각 큐에 대해서 RR 방식을 사용하면 잘 작동한다.
• 프로세스는 처음 배정된 큐를 벗어나지 못한다.
• 프로세스의 타입(real-time, interactive, system, batch)에 따라 분리하는 방식으로도 사용할 수 있다.

6.MLFQ(Multi-Level Feedback Queue) Scheduling

• MLQ는 프로세스들이 처음 배정된 큐를 벗어날 수 없다는 한계 때문에 스케줄링 오버헤드를 줄일 수는 있지만, 유연한 대처가 불가능하다.

• MLFQ는 프로세스들의 CPU bursts에 따라 큐 사이를 이동할 수 있다.

• CPU burst가 낮은 프로세스들(I/O bound, interactive)이나 오래 대기한 프로세스들은 high priority queue에서 처리된다.

• 낮은 우선순위의 큐에 들어있는 프로세스들은 높은 우선순위들의 큐가 모두 비었을 때만 실행가능하다.

• 다음과 같은 파라미터들이 필요하다.

  • 큐의 수
  • 각 큐마다의 스케줄링 알고리즘(높은 우선순위는 짧은 time quantum의 RR,가장 낮은 우선순위는 FCFS)
  • 어떤 프로세스를 상향/하향 시켜줄 것인가.
  • 프로세스가 service가 필요할 때 어떤 큐에 넣어줄지에 대한 방법

• 가장 일반적인 CPU 스케줄러이지만, 설정할 파라미터가 많아 가장 복잡하다.