[OSTEP-8] Multi Level Feedback Queue

개요

• MLFQ 는 짧은 작업을 먼저 실행시켜 반환 시간을 최적화 하고 대화형 사용자에게 응답이 빠른 시스템이라는 느낌을 주기 위해 고안된 알고리즘임
• SJF, STCF 와 같은 알고리즘은 작업시간의 실행 시간 정보를 필요로 하지만, 운영체제는 이 시간을 알 수가 없음
• RR 과 같은 알고리즘은 응답 시간을 단축시키지만 반환 시간은 최악임

핵심: 정보 없이 스케줄 하는 방법은 무엇인가.

작업의 실행 시간에 대한 선행 정보 없이 대화형 작업의 응답 시간을 최소화 할 수 있는 방법은?

기본 규칙

• 여러개의 큐로 구성되며 각각 다른 우선순위(priority level) 가 배정된다
• 실행 준비가 된 프로세스는 이중 하나의 큐에 존재한다.
• 높은 우선순위 큐에 존재하는 작업이 선택된다.
• 큐에는 둘 이상의 작업이 존재할 수 있고, RR 스케줄링 알고리즘이 사용된다.

우선순위의 변경

• 짧은 실행 시간을 갖는 CPU 를 자주 양보하는 대화형 작업과, 많은 CPU 시간을 요구하지만 응답 시간은 중요하지 않는 긴 실행 시간의 CPU 위주 작업이 혼재되어 있음

규칙 3: 작업이 시스템에 진입하면 가장 높은 우선순위, 즉 맨 위의 큐에 놓여짐

규칙 4a: 주어진 타임 슬라이스를 모두 사용하면 우선순위는 낮아짐. 한 단계 아래 큐로 이동함

규칙4b: 타임 슬라이스를 소진하기 전에 CPU 를 양도하면 같은 우선순위를 일단 유지함

한 개의 긴 실행을 가진 작업

1. 최고 우선순위로 진입 (Q2)
2. 10ms 타임 슬라이스가 하나 지나면 우선순위 감소 (Q1)
3. 하나의 타임 슬라이스동안 Q1에서 실행후 끝나면 Q0 로 이동

 

짧은 작업과 함께

어떻게 SJF 에 근접할 수 있을지를 이해 해야 함

• 스케줄러는 처음에 해당 작업이 짧은 작업인지 긴 작업인지 알 수 없기 때문에 일단 짧은 작업이라고 가정 한 이후 우선순위를 점점 낮춤
• 짧은 작업이 들어오면 우선순위가 낮은 큐에 들어가기전에 실행이 종료될꺼임
• 이런 방식이면 SJF 알고리즘과 근사하게 실행 할 수 있음

입출력 작업에 대해서

• 대화형 작업이 키보드나 마우스로부터 사용자 입력을 대기하며 자주 입출력을 수행하면 타임슬라이스가 종료되기 전에 CPU를 양도하게 됨, 이럴 경우 우선순위를 유지함

 

현재 MLFQ 의 문제점

• 시스템에 너무 많은 대화형 작업이 존재하면 긴 실행 시간 작업은 CPU를 할당받지 못함
• 똑똑한 사용자라면 스케줄러를 자신에게 유리하게 동작하도록 프로그램을 다시 작성할 수 있음

시도2: 우선순위의 상향조정

일정 기간 S 가 지나면, 시스템의 모든 작업을 최상위 큐로 이동한다

• 기아 현상을 해결할 수 있다
• CPU 위주의 작업이 대화형 작업으로 특성이 변할 경우 우선순위 상향을 통해 스케줄러가 변경된 특성에 적합한 스케줄링 방법을 적용한다.
• S 가 너무 크면 긴 실행시간을 가진 작업은 굶을 수 있으며, 너무 작으면 대화형 작업이 적절한 양의 CPU 시간을 사용할 수 없게 됨

 

시도 3: 더 나은 시간 측정

스케줄러가 본인에게 유리하게 동작하도록 하는 것을 어떻게 막을 수 있을까

• MLFQ의 각 단계에서 CPU 총 사용시간을 측정함
• 스케줄러는 각 단계에서 프로세스가 소진한 CPU 사용 시간을 저장함
• 프로세스가 타임 슬라이스에 해당하는 시간을 모두 소진하면 걍 다음 우선순위 큐로 강등됨
• 규칙 4a, 4b 를 주어진 단계에서 시간 할당량을 소진하면 걍 우선순위를 낮춤

 

MLFQ 조정과 다른 쟁점들

• 몇개의 큐가 존재해야하는가, 큐당 타임 슬라이스의 크기는 얼마로 해야 하는가, 얼마나 자주 우선순위가 상향 조정되어야 하는가
• 결국 워크로드에 대해 충분히 경험하고 계속 조정해 나가면서 균형점을 찾아야 함
• 대부분의 MLFQ는 큐별로 다른 타임 슬라이스 시간을 셋 할 수 있는데 보통 낮은 우선순위는 긴 CPU 작업을 포함하므로 긴 슬라이스, 높은 우선순위는 대화형 작업이 많으므로 짧은 슬라이스 값을 세팅함

요약

지정된 작업의 우선순위를 정하기 위하여 피드백을 사용함, 과거에 보여준 행동이 우선순위 지정의 지침이 됨

규칙 1: 우선순위(A) > 우선순위(B) 일경우 A 가 실행, B는 실행되지 않음

규칙 2: 우선순위(A) = 우선순위(B) 일 경우 A 와 B는 RR 방식으로 실행됨

규칙 3: 작업이 시스템에 들어가면 최상단 큐에 배치됨

규칙 4: 작업이 지정된 단계에서 배정받은 시간을 소진하면, 작업의 우선순위는 감소함

규칙 5: 일정 주기 S 가 지난 후, 시스템의 모든 작업을 최상위 큐로 이동시킴