[OS] 멀티 레벨 피드백 큐

기존의 스케줄링 알고리즘 SJF 와 STCF와 RR의 문제점을 먼저 알아봅시다.

SJF/STCF 와 RR의 문제점

• SJF와 STCF의 문제점: 현실적 예측 불가능 
  • 작업의 실행 시간을 미리 알아야 최단 작업을 선택할 수 있습니다. 그러나 실제 시스템에서는 작업이 언제 끝날지 정확히 예측하기 어렵기 때문에 구현이 비현실적입니다.
• RR의 문제점 : 긴 반환 시간
  • RR은 모든 작업에 동일한 시간 할당(타임 슬라이스)을 부여합니다. 이로 인해 짧은 작업도 긴 작업과 동일한 대기 시간을 가지게 되어 반환 시간이 길어집니다.

 

이러한 문제점을 해결하기 위해 멀티 레벨 피드백 큐(Multi-Level Feedback Queue, MLFQ)가 태어났습니다.

Mulit Level Feed Back Queue

MLFQ는 여러 개의 큐를 배치하고 각 큐에 우선순위를 설정하여 기존 알고리즘의 단점을 보완한 스케줄링 방식입니다.

작업의 특성에 따라 동적으로 우선순위를 조정하며, 짧은 작업의 응답 시간을 개선하고 긴 작업의 처리도 적절히 관리합니다.

 

https://medium.com/@francescofranco_39234/multilevel-feedback-queue-3ae862436a95

 

동작방식은 다음과 같습니다.

1. 우선순위가 설정된 큐 배치: Q1(최고 우선순위), Q2, Q3 등 여러 큐를 설정합니다.
2. 신규 작업 배치: 새로 들어온 작업은 가장 높은 우선순위 큐(Q1)에 배치됩니다.
3. 타임 슬라이스 할당: 각 큐는 고유의 시간 할당(타임 슬라이스)을 가집니다. 예: Q1은 10ms, Q2는 20ms 등.
4. 우선순위 강등: 작업이 할당된 시간 내에 완료되지 않으면 다음 낮은 우선순위 큐로 이동합니다.
5. 실행 순서: 높은 우선순위 큐의 작업이 먼저 실행됩니다.

 

이 방식은 초기에는 SJF의 빠른응답과 RR의 공정성을 결합하려 했으나, 다음과 같은 문제점이 발생했습니다.

1. 기아(Starvation) 상태가 발생합니다.

작업 소요 시간이 긴 경우, 낮은 우선순위 큐(예: Q3)로 계속 강등되어 CPU를 할당받지 못할 수 있습니다.

높은 우선순위 큐에 짧은 작업이 계속 들어오면 긴 작업은 무한정 대기하게 됩니다.

2. 작업우선순위를 사용자가 조작이 가능합니다.

사용자가 작업의 CPU 사용 패턴을 조작할 수 있습니다. 예를 들어, 타임 슬라이스를 모두 소요하기 직전에 I/O 요청을 발생시켜 CPU를 반납하면 우선순위 강등을 피할 수 있습니다. 이로 인해 특정 작업이 높은 우선순위를 유지하며 CPU를 독점할 가능성이 생깁니다.

해결방안

1. 주기적 우선순위 상향 조정

일정 시간이 지나면 모든 작업을 최고 우선순위 큐로 이동시켜 기아를 방지시킵니다.

2. CPU 사용 시간 측정 및 동적 조정

사용자 조작을 피하기 위해 각 큐에서 작업이 사용한 CPU시간을 추적합니다. 

주어진 단계에서 시간 할당량을 소진하면 (CPU를 몇 번 양도하였는지 상관없이) 우선순위를 강등시킵니다.

 

이러한 방식으로 위의 문제점을 해결해나갔습니다. 

필요한 변수들은 어떻게 설정할 것인가?

우리가 논의해봐야할게

1. 몇 개의 큐가 존재해야 하는가?
2. 큐당 타임 슬라이스의 크기는 얼마로 해야 하는가?
3. 기아를 피하고 변화된 행동을 반영하기 위하여 얼마나 자주 우선순위가 상향 조정되어야 하는가?

하지만, 우리는 이 질문에 대해 쉽게 대답이 불가능하다. 경험해보며 설정해나가는것이 좋습니다.

관련된 내용은 구현된 MLFQ 스케줄러를 찾아봅시다.