[운영체제] - MLFQ Scheduling

👍MLFQ(Multi-level Feedback Scheduling)

📢 개요

• Corbato에 의해 개발됨.
• SJF(Shortest Job First), STCF(Shortest Time to Completion First) 방식은 Turnaround time을 줄이는데 유리하고, RR(Round-robin) 방식은 Response time을 줄이는데 유리하다.
• MLFQ Scheduling은 Turnaround time과 Response time을 모두 줄이는데 유리하다.

📢 MLFQ의 기본적인 다섯가지 규칙

• MLFQ에는 여러개의 Ready queue가 존재하며, 이 Ready queue끼리의 우선순위는 서로 다르다.

📜 I. 우선순위가 높은 프로세스부터 실행한다.
📜 II. 우선순위가 서로 같다면, RR(Round-robin)의 방식으로 스케쥴링 한다.

• 여기선 우선순위가 높은 Q8에 들어있는 프로세스 A, B가 먼저 실행되는데, 이 두 프로세스의 우선순위는 동일하므로 A,B 가 Round-robin의 방식으로 실행되게 된다.

📜 III. 프로세스가 처음으로 Ready queue에 들어올 때는 우선순위가 가장 높은 큐에 배치된다.
📜 IV. 프로세스가 Time slice를 모두 소진시킬 시 우선순위를 1 감소시킨다.
📜 V. 프로세스가 Time slice를 소진하지 않고 그 전에 스스로 CPU를 release 할 시 우선순위를 유지한다.

📢 Interactive process: 주로 I/O request를 기다리며 time slice를 소모하기 전 스스로 CPU를 release하기 때문에, 높은 우선순위가 계속해서 유지된다.
📢 Batch process: 주로 time slice를 소모하며 계속해서 실행되어야 하기 때문에, 우선순위가 낮아지게 된다.
=> 따라서, 프로세스의 실행시간 정보를 알지 못하더라도 이 프로세스가 interactive한지, CPU-bound한지를 예상하고 스케쥴링 하는 것이 가능하다.

📢 MLFQ의 추가적인 규칙

• 5개의 기본적인 규칙만 적용하게 되면 3가지 문제점이 발생할 수 있다.
  📢 Starvation: Interactive한 프로세스들이 time slice 소모전 CPU를 release한다면 우선순위가 계속 유지 되며 우선 순위가 낮은 프로세스들은 CPU를 할당받지 못하게 된다.
  📢 악의적 동작: 만일 프로세스가 악의적으로 CPU를 점유하기 위해 의미없는 I/O request등을 보내는 등 우선순위를 계속 유지하려는 시도를 한다면 이를 막을 방법이 없다.
  📢 프로세스 특성 변화: 만일 초기에는 CPU-bound한 작업만을 하다가 나중에는 interactive한 동작을 하는 프로세스의 경우에는 우선순위를 높일 방법이 없어 CPU 점유가 어렵다.

📜 Solution I) 우선순위 초기화(Priority Boost)

• 특정 시간이 지나면 모든 프로세스의 우선순위를 초기화한다!
• Aging(오래 기다린 프로세스는 우선순위 올라감)도 방법임
  

  • 왼쪽의 경우 검정 프로세스는 실행되다가 뒤에 interactive한 프로세스들이 몰리게 되면 실행될 수 없으나(starvation), priority boost가 일어난 오른쪽의 경우에는 interactive한 프로세스와 검정 프로세스의 우선순위가 같아지며 실행이 가능하게 된다.

📜 Solution II) Better Accounting

• 전의 실행정보를 기억해두었다가 그 임계치를 넘으면 우선순위를 무조건 감소시킨다.
  

  • 왼쪽의 경우 악의적인 프로세스가 time slice보다 살짝 짧은 시간에 CPU를 release하게 되면 우선순위가 유지되나, 오른쪽의 경우에는 전에 실행했던 시간이 누적되며 우선순위가 내려가는 것을 확인 할 수 있다. (Time slice = 10일 때 그 전 실행에서 9.9를 실행하고 release했다면, 그 다음 실행에는 0.1만 실행해도 우선순위를 낮춤)

📜추가)

• 추가적으로 우선순위가 낮을수록 time slice의 길이를 늘리는 것이 좋다.