Multi-Level Feedback Queue Design
• Desing goals
MLFQ가 해결할는 기본적인 문제는 다음과 같다.
- 짧은 작업을 먼저 실행시켜 반환 시간을 최적화
- MFLQ는 대화형 사용자에게 응답이 빠른 시스템을 제공, 응답시간을 최적화
앞서 MLFQ : Intro에서와 마찬가지로 한번에 모든조건을 만족하는 policy를 찾긴 힘드므로, 단계별로 규칙을 만든후 현실적인 조건에 맞게 수정한다.
• Basic Rules
MLFQ는 여러 개의 큐(Multi Level Queue)로 구성되며 각각 다른 우선순위(priority level)가 배정
» 규칙
규칙 1. 높은 우선순위 큐에 존재하는 작업을 실행
규칙 2. 같은 우선순위 큐에 존재하는 작업들끼리는 RR scheduling 적용
우선순위는 각 작업의 특성에 따라 동적으로 부여,
작업이 진행되는 동안 해당 작업의 정보를 얻고, 이를 통해 미래의 행동을 예측(Feedback)
• 우선순위 규칙 만들기
워크로드의 특성을 반영
짧은 실행 시간을 갖는 cpu를 자주 양보하는 대화형 작업, 많은 cpu시간을 요구하지만 응답 시간은 중요하지 않은 긴 실행시간의 cpu작업을 구분
» 규칙
규칙 3. 작업이 시스템에 진입하면 가장 높은 우선순위 부여(맨 위의 큐)
규칙 4a. 타임 슬라이스 소진 시 우선순위 한단계 하락(한단계 아래 큐)
규칙 4b. 타임 슬라이스 소진 전 CPU양도 시 같은 우선순위 유지
» 이유
규칙3, 4a
스케줄러는 작업시간을 알 수 없으므로, 일단 짧은 작업이라고 가정해 높은 우선순위를 일단 부여함
진짜 짧은 작업이면 빨리 실행후 종료할 것이고, 아니라면 우선순위가 점점 낮아져 긴 배치형 작업임을 증명하게 됨
규칙 4b
대화형(interactive) 작업의 응답속도 향상가능
대화형 작업의 경우 키보드나 마우스 등으로 부터 사용자 입력을 받기위한 입출력을 자주 수행,
프로세스의 전 과정이 대화형 작업이 아닌 프로세스들도
[OSTEP] Virtualization : Process의 Process optimization에서 서술했듯 process가 하나라도 빨리 끝날수록 CPU사용성이 좋아지므로 전채 모든프로세스가 끝나는 시간은 짧아지는것도 규칙 4b의 장점이 될듯
» 문제점
기아상태 (starvation)
너무 많은 대화형 작업이 존재하면, 그들이 모든 CPU 시간을 소모하고 긴 실행시간의 작업은 CPU를 할당받지 못한다.
악의적인 스케쥴러 조작
타임 슬라이스를 모두 소모하기 직전에 임의의 입출력 요청을 통해 CPU를 양도하면 계속 높은 우선순위를 유지, 많은 CPU시간을 유지 가능
예컨데, 타임슬라이스의 99%를 실행 후 입출력 요청하면 거의 독점가능
프로세스 특성 변화
시간 흐름에 따라 프로세스의 특성(대화형인지 긴 cpu작업시간 작업인지)이 변할 수 있다.
초기에 긴 cpu작업이지만 나중엔 대화형작업으로 전환되는 프로세스는 초기에 우선순위가 하락된다. 추후 대화형 작업으로 전환되어도 우선순위가 향상되지 못함.
대화형 작업으로 전환되었을때는 응답시간이 매우 떨어져 대화형 작업 원활히 수행 불가능
• 우선순위규칙 문제점 해결
» 우선순위의 상향 조정
기아 문제를 방지하기 위해 주기적으로 모드 작업의 우선순위를 상향 조정 (boost)한다.
규칙 5. 일정 기간 S가 지나면 시스템의 모든 작업을 최상위 큐로 이동
최상위 큐로 모두 이동해 타임 슬라이스 소진 전까지 RR Scheduling을 통해 cpu를 사용함
이는 기아상태 문제, 시간에 따라 프로세스 특성이 변화하는 문제를 모두 해결한다.
voo-doo constants
S값은 너무 크면 기아문제가, 너무 작으면 대화형작업의 응답성능이 나빠진다. 적절한 상수가 필요하며 이를 voo-doo constants라고 한다.
» CPU사용시간 측정법 개선
규칙 4 a,b를 악용한 스케쥴러 조작을 방지하기 위해, MLFQ 각 단계에서 cpu 총 사용 시간을 측정하도록 한다.
스케쥴러는 현재 우선순위 큐에서 프로세스가 소진한 cpu시간을 저장한다.
타임슬라이스에 해당하는 시간을 모두 소진하면 한단계 아래로 강등시킨다.
규칙 4a,b를 합쳐 하나로 재정의한다
규칙 4. 주어진 단계에서 시간할당량을 모두 소진하면, CPU 양도와 관계없이 우선순위가 낮아진다.
MLFQ Rules (최종)
• 규칙
규칙 1. 우선순위가 높은 프로세스부터 실행
규칙 2. 같은 우선순위면 RR Scheduling
규칙 3. 작업이 처음 시스템에 들어가면 최상위 우선순위 배정
규칙 4. 현재 우선순위에서 할당받은 타임 슬라이스를 소진시,
우선순위 하락규칙 5. 일정 주기 S마다 시스템의 모든 작업을 최상위 큐로 이동
• 설명
• MLFQ 특징
MLFQ는 작업 특성에 대한 정보 없이, 작업의 실행을 관찰한 후 그에 따라 우선순위를 지정
반환시간과 응답시간 모두를 최적화함
짧게 실행되는 대화형 작업에 대해서 전반적으로 우수한 성능(반환시간, 응답시간) 제공(STCF의 장점 반영),
오래 실행되는 cpu집중 워크로드에는 공정하게 실행하고 조금이라도 진행되도록 함
• MLFQ방식의 OS
위 특성에 설명된 장점들 때문에
BSD Unix와 그에서 파생된 운영체제들, Solaris, Windows NT, Windows 운영체제 등의 많은 시스템이 MLFQ를 기본 스케줄러로 사용
.jpg)