[운영체제] Multi-Level Feedback Queue (MLFQ)

Multi-Level Feedback Queue

Turnaround time 과 response time 을 모두 줄일 수 있는 스케쥴러 입니다.

• 여러개의 큐가 구성되어 있고 각각의 큐는 다른 우선순위를 가지고 있습니다.
• 특정 순간에 한개의 job 은 한개의 큐에 들어가 있습니다.

Basic Rules

• Rule 1 : 만약 프로세스 A 의 우선순위가 프로세스 B 의 우선순위보다 높다면 A 가 실행됩니다.
• Rule 2 : 만약 프로세스 A 와 프로세스 B 의 우선순위가 같다면, A 와 B 는 Round robin 하여 실행된다.
• Rule 3 : 한 프로세스가 시스템에 들어오면, 가장 높은 우선순위를 갖습니다.
• Rule 4-a : 만약 프로세스가 한 time slice 를 모두 실행하면, 해당 프로세스의 우선순위는 낮아집니다.
• Rule 4-b : 만약 프로세스가 time slice 가 끝나기 전에 CPU 를 포기하면 본 우선순위를 유지합니다.

How to set priority

• 만약 한 프로세스가 주기적으로 CPU 자원을 포기한다면 MLFQ 는 해당 프로세스를 높은 우선순위로 유지합니다.
• 만약 한 프로세스가 지속적으로 CPU 자원을 독점한다면 MLFQ 는 해당 프로세스를 낮은 우선순위로 내립니다.

예를들어 주로 I/O bound jobs 들은 높은 우선순위, CPU bound jobs 들은 낮은 우선순위를 가집니다.

Problems

위의 다섯가지 Rule 에는 3가지 문제점이 있습니다

• Starvation : 우선순위를 높게 유지하는 job들이 많을 때, 일부 job들이 CPU 자원을 빈곤하게 점유하게 됩니다.
• Gaming the scheduler : time slice 가 over 되기 직전에 I/O operation 을 요청하여 인위적으로 특정 프로세스가 높은 우선순위를 유지하게 할수도 있는 문제점이 있습니다.
• Changing behavior : CPU bound -> I/O bound 가 되었을 때, 우선순위를 회복할 수 없는 문제점이 있습니다.

Solutions

• Priority Boost
  • Rule 5 : starvation 과 changing behavior 문제점을 막기 위해 주기적으로 모든 프로세스들의 우선순위를 boost 해줍니다.
• Gaming Tolerance
  • Rule 4 : 주어진 level 에서 할당된 time 을 모두 소진하면, 해당 job 의 우선순위는 낮아집니다.

Conclusion

MLFQ scheduler 는 모든 문제점을 해결하기 위해 아래 Rule 로 운영됩니다.

• Rule 1 : 만약 프로세스 A 의 우선순위가 프로세스 B 의 우선순위보다 높다면 A 가 실행됩니다.
• Rule 2 : 만약 프로세스 A 와 프로세스 B 의 우선순위가 같다면, A 와 B 는 Round robin 하여 실행된다.
• Rule 3 : 한 프로세스가 시스템에 들어오면, 가장 높은 우선순위를 갖습니다.
• Rule 4 : 주어진 level 에서 할당된 time 을 모두 소진하면, 해당 job 의 우선순위는 낮아집니다.
• Rule 4-a : 만약 프로세스가 한 time slice 를 모두 실행하면, 해당 프로세스의 우선순위는 낮아집니다.
• Rule 4-b : 만약 프로세스가 time slice 가 끝나기 전에 CPU 를 포기하면 본 우선순위를 유지합니다.
• Rule 5 : starvation 과 changing behavior 문제점을 막기 위해 주기적으로 모든 프로세스들의 우선순위를 boost 해줍니다.