멀티 레벨 피드백 큐(우선순위 스케쥴링)

📌 들어가기 전에

Scheduling Policy 의 발전 과정과 장단점 1(Round Robin 까지)
지난 글에서 FIFO(First In First Out, 선입선출)부터 시작해서 RR(Round Robin) 스케줄링 알고리즘까지 정리를 해봤다. 해당 내용까지 잘 모르는 부분이 있다면 보고 오는 것을 추천한다!

지난 글에 올렸던 알고리즘들은 '어떤 문제점' 들이 있었고, 그를 해결하기 위한 방법으로 멀티 레벨 피드백 큐라는 가장 유명한 알고리즘이 있다고 언급하였다. 이 글에선 MLFQ로 해결한 문제들과 MLFQ의 규칙, MLFQ가 발전하면서 당면한 문제들과 그 해결과정에 대해 정리해보고자 한다.

📌 해결하고자 하는 두 가지 문제

1 . 짧은 작업을 먼저 실행시켜 반환시간을 최적화하고자 함.

SJF(Shortest Job First)나 STCF(Shortest Time Complete First) 같은 알고리즘은 작업의 실행 시간 정보를 필요로 하지만, 운영체제는 실행 시간 정보를 미리 알 수 없었다.

2 . MLFQ는 대화형 사용자에게 응답이 빠른 시스템이라는 느낌을 주고 싶었기 때문에 응답 시간을 최적화한다.

RR과 같은 알고리즘은 응답 시간을 단축시키지만 반환시간은 거의 최악이었기 때문이다.

핵심은 이렇다.

정보없이 스케줄하는 방법은 무엇인가, 동시에 응답시간까지 빠르게 하려면?

📌 MLFQ의 규칙

MLFQ의 기본 규칙

MLFQ는 이름에서부터 알 수 있듯이 여러 개의 큐로 구성되어 있고 각각 큐마다 다른 우선순위가 배정된다. 그리고 큐에는 프로세스가 배정되고 한 큐에 여러 개의 프로세스가 배정될 수 있다.

그리고 우선순위가 높은 큐에 있는 작업이 먼저 실행된다. 또, 같은 큐에 있는 여러 작업은 RR 스케줄링을 적용하여 실행한다. 여기서 핵심이 나온다. 핵심은 우선순위를 정하는 방식이다. 각 작업마다 고정된 우정순위를 부여하는 것이 아니라 각 작업의 특성에 따라 동적으로 우선순위를 부여하는 방식을 사용한다.

예를 들어, 어떤 작업이 키보드 입력을 기다리며 반복적으로 CPU를 양보하면 MLFQ는 해당작업의 우선순위를 높게 유지한다. 반면, 한 작업이 긴 시간동안 CPU를 집중적으로 사용하면 MLFQ는 해당 작업의 우선순위를 낮춘다. 이처럼 작업이 진행되는 동안 해당 작업의 정보를 얻고 이 정보를 이용해서 미래 행동을 예측한다.

규칙 1 : Priority(A) > Priority(B)이면 A가 실행된다.(B는 실행되지 않는다.)

규칙 2 : Priority(A) = Priority(B)이면 A와 B는 RR 방식으로 실행된다

위의 그림같이 큐에 작업 A, B, C, D가 있는 경우에는 A, B만 RR 스케줄링으로 서로 번갈아가면서 실행이 되고 C, D는 실행이 되지 않는다. 그럼 어떻게 C, D는 실행이 될까? 다음 규칙을 보자.

우선순위를 변경하는 규칙

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

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

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

몇가지 예시를 보면서 규칙을 이해해보도록 하자.
💁🏻‍♂️ 예 1 : 한개의 긴 실행시간을 가진 작업

위 그림은 세 개의 큐가 존재하는 스케줄러에서 긴 실행시간을 가진 작업 도착했을 때의 그림이다.
먼저 규칙 3번에 따라 가장 우선순위가 높은 큐인 Queue2에 진입한다. 일정 타임슬라이스 (예, 10msec)가 지나면 스케줄러는 작업의 우선순위를 한단계 낮추어 Queue1으로 이동시킨다. 다음 타임슬라이스가 지나면 작업은 가장 낮은 우선순위를 가진 Queue0으로 이동하게 되고 이후 Queue0에서 계속 머무르게 된다.

💁🏻‍♂️ 예 2 : 짧은 작업이 들어오는 경우

위 그림은 긴 작업을 하는 도중 짧은 대화형 작업이 들어왔을 때의 스케줄러를 보여주는 그림이다. 이와 같이 긴 작업을 하는 도중이더라도 새로운 작업이 들어온 경우에는 우선순위가 가장 높은 큐에 있는 작업을 먼저 스케줄링 하게 된다. 그리고 짧은 작업이 먼저 끝나고 다시 원래 하던 작업으로 스케줄링 됨을 알 수 있다. 이와 같은 방식으로 작업의 실행시간을 미리 알지 못하더라도 SJF(Shortest Job First)와 같은 근사한 결과를 만들어 내었다.

💁🏻‍♂️ 예 3 : 입출력 작업에 대해서는?

위 그림은 긴 작업(초록색)중에 짧은 입출력 작업(빨간색)이 반복해서 들어올 때의 스케줄러를 나타낸 그림이다. 빨간색 작업은 타임슬라이스를 다 소진하기 전에 CPU를 양도하기 때문에 규칙 4b에 의해 계속해서 높은 우선순위를 유지할 수 있다. 따라서 대화형 작업일 경우 MLFQ의 대화형 작업을 빨리 실행시킨다는 목표에 가까워졌다.

📌 여기까지의 문제점

지금까지 해도 MLFQ가 해결하고 싶었던 두가지의 문제점은 어느 정도 해결이 되었으나 다른 문제가 발견되었다. 그 문제점들을 나열해보고자 한다.

문제 1 . 기아상태가 발생할 수 있음

시스템에 너무 많은 대화형 작업이 존재하면 그들이 모든 CPU시간을 소모하게 되고 긴 실행시간 작업은 CPU시간을 할당받지 못함으로서 계속 작업을 실행하지 못하고 기아상태(starvation)가 발생할 수 있다.

문제 2 . 스케쥴러를 자신에게 유리하게 동작하도록 프로그램을 다시 작성할 수 있음

프로그램을 타임슬라이스가 다 끝나기 바로 직전에 짧은 입출력을 주도록 프로그램을 재작성하면 규칙 4b에 따라 해당 프로그램은 CPU 점유가 긴 작업임에도 불구하고 계속 높은 우선순위를 유지할 수 있게 된다. 이는 CPU 독점의 결과를 유도할 수 있다.

문제 3 . 프로그램은 시간흐름에 따라 특성이 변할 수 있다. CPU 위주 작업이 대화형 작업으로 바뀔 수 있다.

그렇게 되면 작업이 다시는 대화형 작업과 같은 우선순위가 될 수 없는 문제로 반응 시간에 문제가 생긴다.

📌 해결안 1 : 우선순위의 상향 조정

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

기존의 스케줄러가 왼쪽 그림이고 규칙 5를 적용한 스케줄러가 오른쪽 그림이다. 일정시간 S(여기서는 50msec)가 지나면 스케줄러는 모든 작업을 가장 우선순위가 높은 큐로 이동시킨다. 그렇게 되면 오른쪽 그림처럼 짧은 입출력 작업들이 계속 들어오더라도 초록색 작업을 기아상태에 빠지지 않은 상태로 실행시킨다는 것을 알 수 있다. 마찬가지로 3번 문제도 해결이 된다.

하지만 여기서 핵심은 역시 S에 있다. S는 부두상수(voo-doo constants)라고 한다. 말 그대로 이 값을 정하는 것이 가장 큰 핵심이다. 그 방법은 각각의 스케줄러에서 정하기 나름이다. 만약 S가 너무 크면 긴 작업시간을 가진 작업은 기아상태에 빠지고 너무 S가 작다면 짧은 입출력을 대응할 시간을 사용할 수 없게 된다.

📌 해결안 2 : 더 나은 시간 측정

이제 2번문제를 막아보자.

왼쪽 그림은 사용자가 일부러 프로그램을 조작해서 초록색 프로그램을 높은 우선순위 큐에 계속 머무르게 하는 경우이다. 이를 해결하기 위해 각 단계에서 CPU 총 사용시간을 측정하는 방식을 적용한다. 현재 단계에서 프로세스가 소진한 CPU 사용시간을 저장한다. 그 후에 그 시간을 모두 소진하면 다음 우선순위 큐로 강등시킨다.

다음은 규칙 4a와 4b를 합친 규칙 4이다.

규칙 4 : 주어진 단계에서 시간 할당량을 소진하면 (CPU를 몇 번 양도하였는지 상관없이) 우선순위는 낮아진다.(아래 단계의 큐로 이동한다.)

📌 규칙 정리

규칙 1 : Priority(A) > Priority(B)이면 A가 실행된다.
규칙 2 : Priority(A) = Priority(B)이면 A와 B는 RR 방식으로 실행된다.
규칙 3 : 작업이 시스템에 진입하면 가장 높은 우선순위 즉 맨 위의 큐에 놓여진다.
규칙 4 : 주어진 단계에서 시간 할당량을 소진하면 우선순위는 낮아진다.
규칙 5: 일정기간 S가 지나면 시스템의 모든 작업을 최상위 큐로 이동시킨다.

📌 한계

MLFQ는 스케줄러에 정해야할 변수가 많다.
1 . 타임 슬라이스
2 . 우선순위 큐의 개수
3 . 부두상수 S
이러한 변수들을 잘 조정하기 위해서는 워크로드에 대해 충분히 경험하고 조정할 필요가 있다.

예를 들어, 대부분의 MLFQ는 큐마다 타임슬라이스를 다르게 둔다. 높은 우선순위 큐는 보통 짧은 타임 슬라이스를 주어서 대화형 작업들을 빠르게 교체하는 데 의의를 둔다. 그리고 긴 작업들은 긴 슬라이스를 준다.

📌 마치며

지금까지 FIFO 부터 MLFQ까지 스케줄링 알고리즘의 변천사를 알아보았다. 이외에도 다른 알고리즘도 존재하고 멀티 프로세싱에서 다루는 스케줄링도 존재한다. 단순히 현재 쓰이는 알고리즘을 공부하는 것보다 알고리즘의 발전과정을 보며 각각의 장단점을 확인하고 문제점을 해결하기 위한 방법들을 공부하니 컴퓨터 공학적 생각이 성장하는데 더 도움이 되었다고 생각한다. 앞으로도 이런 방식으로 공부해야겠다고 다짐한다.

다음은 메모리 교체 정책 (Replacement Policy)를 이와 같은 방식으로 정리하려고 한다.

도움받은 자료

책 - 운영체제 _ 아주 쉬운 세 가지 이야기