스케줄링: 멀티 레벨 피드백 큐

스케줄링: 멀티 레벨 피드백 큐

MLFQ, Multi-level Feedback Queue

여러 개의 큐로 구성되며, 각각 다른 우선순위(priority level)가 배정된다.

높은 우선순위를 가진 작업(큐)가 선택된다.

---

📌  배운 것

 

MLFQ가 해결하려는 문제

• 짧은 작업을 먼저 실행시켜 반환시간을 최적화
• 대화형 사용자(화면 앞에 앉아 바로면서 프로세스 종료를 기다리는 사용자)에게 응답이 빠른 시스템이라는 느낌을 주고 싶음. 즉, 응답시간을 최적화

 

MLFQ 규칙

• 규칙 1 : Priority(A) > Priority(B)이면, A가 실행된다.(B는 실행되지 않는다.)
• 규칙 2 : Priority(A) = Priority(B)이면, A와 B는 RR 방식으로 실행된다.
• 규칙 3 : 작업이 시스템에 진입하면, 가장 높은 우선순위, 즉 맨 위의 큐에 놓여진다.
• 규칙 4a : 주어진 타임 슬라이스를 모두 사용하면 우선순위는 낮아진다. 즉, 한 단계 아래 큐로 이동한다.
• 규칙 4b : 타임 슬라이스를 소진하기 전에 CPU를 양도하면 같은 우선순위를 유지한다. 

MLFQ가 SJF에 접근하는 예시

오래 실행되는 A는 우선순위가 낮아진 상태로 실행중이었다.

100초에 B가 도착했고 가장 높은 우선순위(Q2)가 되고 규칙4a에 의해 타임 슬라이스가 소진되니 우선순위가 낮아졌다(Q1). 그 120초부터 140초까지 우선순위 대로 B가 실행되고 모든 작업이 끝난뒤, 다시 140초 부터 A가 실행된다.

SJF와 같이 짧은 작업이 빨리 실행되고 바로 종료되는 것을 확인 할 수 있다.

 

입출력 작업

규칙 4b에 의해 프로세스가 타임 슬라이스를 소진하기 전에 프로세서를 양도하면 같은 우선순위를 유지하게 된다.

키보드나 마우스로부터 사용자 입력을 대기하며 자주 입출력을 수행하면 타임 슬라이스가 종료되기 전에 CPU를 양도하게 될 것이다.

---

MLFQ의 문제점

• 기아 상태(starvation) :  시스템에 너무 많은 대화형 작업이 존재하면 그들이 모든 CPU 시간을 소모해 긴 시간 작업은 CPU 시간을 할당받지 못하게 된다.
• CPU 독점 : CPU 위주의 작업이 대화형 작업으로 특성이 변할 경우

 

우선순위 상향 조정

기아 현상을 방지하기 위해 모든 작업의 우선순위를 상향 조정(boost)하는 것이다.

 

MLFQ 규칙

• 규칙 5 : 일정시간 S가 지나면, 시스템의 모든 작업을 최상위 큐로 이동 시킨다.

 

부두 상수

voo-doo constants

적절한 S는 얼마인가? 불행하게도 S는 변수이다.

너무 크면 긴 실행 시간을 가진 작업이 굶을 수 있고, 너무 작으면 대화형 작업이 적절한 양의 CPU 시간을 사용할 수 없게 된다.

---

스케줄러를 자신에게 유리하게 동작시키는 것을 어떻게 막을 수 있을까?

MLFQ 규칙

• 규칙 4 : 주어진 단계에서 시간 할당량을 소진하면(CPU를 포기한 횟수와 상관없이), 우선순위는 낮아진다(즉, 한 단계 아래 큐로 이동한다).

규칙 4a와 4b를 합쳐 하나의 규칙으로 재정의한다.

 

---

또 다른 쟁점들

필요한 변수들을 스케줄러가 어떻게 설정해야 하는지

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

 

대부분의 MLQF 기법들은 큐 별로 타임 슬라이스를 변경할 수 있다.

부두상수 피하기(Ousterhout's Law)

보통 높은 우선순위 큐는 짧은 타임 슬라이스를 가지고, 낮은 우선순위는 긴 타임 슬라이스를 가진다.

 

 

MLFQ는 미래를 예측하기 위해 과거의 경험을 활용하는 훌륭한 예이다.

 

MLFQ 활용

• 하드웨어 예측기
• 캐시 알고리즘

 

---

📌 회고

cpu선점 작업에 대화형 작업이 많은 부분을 차지하는 문제는 해결하기 쉽지 않아 보인다.

현재도 많은 고민을 하고 있는 문제로 느껴진다!

케이스에 따라 스케줄링을 최적화 하기 위해 멀티 레벨 피드백 큐 개념이 생긴만큼 한번에 이해하기 힘들었다.

 

📌 개선 방향

주말이나, 대면 스터디 때 지금까지 배운 내용을 점검하는 시간을 가져야 할 것같다.

또한 깃 cs공부도 같이 진행하면 좋을 것 같아 이부분에 대해서도 이야기를 나눠봐야 겠다.

 

📌 참고 문서

운영체제 : 아주 쉬운 세 가지 이야기