Multi-level Feedback Queue
Multi-level Feedback Queue
해결하고자 하는 문제
- 짧은 작업을 먼저 실행시켜 반환 시간을 최적화
- SJF와 같은 알고리즘은 작업의 실행시간을 필요로 한다. 하지만 현실적으로 운영체제는 작업의 실행시간을 미리 알 수 없다는 문제점이 있다.
- 대화형 사용자에게 응답이 빠른 시스템이라는 느낌을 주기위해 응답 시간을 최적화
- RR 알고리즘은 응답 시간을 단축시키지만 반환 시간은 최악이다.
이러한 문제를 해결해줄 수 있는 멀티 레벨 피드백 큐에 대해서 알아보자.
MLFQ(Multi-level Feedback Queue)
MLFQ는 여러 개의 큐로 구성되며, 각각 다른 우선순위가 배정된다. 높은 우선순위 큐에 존재하는 작업이 먼저 선택된다.
같은 우선순위의 큐에 존재하는 작업들은 RR 스케줄링 알고리즘이 사용된다.
우선순위를 정하는 방식
MLFQ 스케줄링의 핵심은 우선순위를 정하는 방식이다. MLFQ는 각 작업에 고정된 우선순위를 부여하는 것이 아니라 각 작업의 특성에 따라 동적으로 우선순위를 부여한다.
- 어떤 작업이 키보드 입력을 기다리며 반복적으로 CPU를 양보하면 MLFQ는 해당 작업의 우선순위를 높게 유지한다.
- 한 작업이 긴 시간 동안 CPU를 집중적으로 사용하면 MLFQ는 해당 작업의 우선순위를 낮춘다.
MLFQ는 작업이 진행되는 동안 해당 작업의 정보를 얻고, 이 정보를 이용하여 미래 행동을 예측한다.
우선순위의 변경 규칙
- 작업이 시스템에 진입하면, 가장 높은 우선순위, 즉 맨 위의 큐에 놓인다.
- 주어진 타임 슬라이스를 모두 사용하면 우선순위는 낮아진다. 즉, 한 단계 아래 큐로 이동한다.
- 타임 슬라이스를 소진하기 전에 CPU를 양도하면 같은 우선순위를 유지한다.
위의 그림에서 검은 작업은 긴 실행 시간을 가지고 있어 바닥의 큐에 도착하여 계속 실행되고 있다. 회색 작업은 실행 시간이 짧기 때문에 바닥의 큐에 도착하기 전에 종료된다.(높은 우선순위에서 시작하므로 검은 작업이 가지고 있던 자원을 선점하여 회색 작업이 이용한다)
스케줄러는 작업이 짧은 작업인지 긴 작업인지 알 수 없기 때문에 일단 짧은 작업이라도 가정하여 높은 우선순위를 부여한다. 진짜 짧은 작업이면 빨리 실행되고 바로 종료할 것이다. 짧은 작업이 아니라면 천천히 아래 큐로 이동하게 되고 스스로 긴 배치형 작업이라는 것을 증명하게 된다. 이러한 방식으로 MLFQ는 SJF를 근사할 수 있다.
현재 MLFQ의 문제점
기아 상태(starvation)
시스템에 너무 많은 대화형 작업이 존재하면 긴 실행 시간 작업은 CPU 시간을 할당받지 못할 것이다.
CPU 독점
타임 슬라이스가 끝나기 전에 아무 파일을 대상으로 입출력 요청을 내려 CPU를 양도하면 같은 큐에 머무를 수 있고 따라서 더 높은 퍼센트의 CPU 시간을 얻게 된다. 만약 타임 슬라이스의 99%를 실행하고 CPU를 양도하게 되면 CPU를 거의 독점할 수 있게 된다.
작업 특성의 변화
프로그램은 시간 흐름에 따라 특성이 변할 수 있다. CPU 위주 작업이 대화형 작업으로 바뀔 수 있다. 현재 구현 방식으로는 그런 작업은 다른 대화형 작업들과 같은 대우를 받을 수 없다.
우선순위의 상향 조정
CPU 위주 작업이 조금이라도 진행하는 것을 보장(기아 문제 방지)하기 위해서는 어떻게 해야할까?
주기적으로 모든 작업의 우선순위를 상향 조정하는 방법이 있다.
- 일정 기간 S가 지나면, 시스템의 모든 작업을 최상위 큐로 이동시킨다.
이 방법을 통해서 기아 문제를 방지하고, 작업 특성의 변화에도 적절히 대처할 수 있다.
(적절한 S 값을 설정하는 것이 중요하다)
더 나은 시간 측정
CPU 독점 문제를 막기 위해서는 CPU 총 사용 시간을 측정하는 방법이 필요하다.
현재 단계에서 프로세스가 소진한 CPU 사용 시간을 저장한다. 프로세스가 타임 슬라이스에 해당하는 시간을 모두 소진하면 다음 우선순위 큐로 강등된다. 타임 슬라이스를 한 번에 소진하든 짧게 여러 번 소진하든 상관없다.
- 주어진 단계에서 시간 할당량을 소진하면(CPU를 몇 번 양도하였는지 상관없이), 우선순위는 낮아진다.
그 외의 기능
대부분의 MLFQ 기법들은 큐 별로 타임 슬라이스를 변경할 수 있다. 우선순위가 높은 큐는 보통 짧은 타임 슬라이스가 주어진다. (높은 우선순위에 있는 큐 → 대화형 작업 이므로 짧은 타임 슬라이스를 갖는 것이 효율적이다.)
일부 스케줄러의 경우 가장 높은 우선순위를 운영체제 작업을 위해 예약해 둔다. 일반적인 사용자 작업은 시스템 내에서 가장 높은 우선순위를 얻을 수 없다.
요약
MLFQ는 멀티레벨 큐를 가지고 있으며, 지정된 작업의 우선순위를 정하기 위하여 피드백을 사용한다. 과거에 보여준 행동이 우선순위 지정의 지침이 된다.
- 규칙 1: 우선순위(A) > 우선순위(B) 일 경우, A가 실행되고, B는 실행되지 않는다.
- 규칙 2: 우선순위(A) = 우선순위(B) 일 경우, A와 B는 RR 방식으로 실행된다.
- 규칙 3: 작업이 시스템에 들어가면 최상위 큐에 배치된다.
- 규칙 4: 작업이 지정된 단계에서 배정받은 시간을 소진하면(CPU를 포기한 횟수와 상관없이), 작업의 우선순위는 감소한다.
- 규칙 5: 일정 주기 S가 지난 후, 시스템의 모든 작업을 최상위 큐로 이동시킨다.
작업의 특성에 대한 정보없이(SJF 스케줄링과 달리), 작업의 실행을 관찰한 후 그에 따라 우선순위를 지정한다. MLFQ는 반환 시간과 응답 시간을 모두 최적화한다. 짧게 실행되는 대화형 작업에 대해서는 우수한 성능을 제공한다(SJF와 유사하게). 오래 실행되는 CPU 집중 작업에 대해서는 공정하게 실행하고 조금이라도 진행되도록 한다(SJF의 단점을 보완).
이런 이유로 많은 시스템이 기본 스케줄러로 MLFQ를 사용한다.(자세한 동작방식은 위의 설명과 조금씩 다를 것이다.)