[운영체제]멀티 레벨 피드백 큐

멀티 레벨 피드백 큐(MLFQ)에 대해 알아보자.

MLFQ가 해결하려고 하는 기본적인 문제는 두가지이다.

 

1.짧은 작업을 먼저 실행 시켜 반환 시간을 최적화.(SJF,STCF 같은 작업은 작업 시간을 알아야 한다는 단점.)

2.MLFQ는 I/O를 사용하는 사용자에게 응답 시간을 최적화.(RR 같은 작업은 응답 시간을 단축시키지만 반환 시간이 최악.)

 

우리가 프로세스에 대한 정보가 없다면 스케줄러를 어떻게 만들 수 있을까?

실행 중인 작업의 특성을 알아내고 이를 이용하여 더 나은 스케줄링 결정을 하기 위한 방법은?

 

MLFQ의 기본 규칙

MLFQ는 여러 개의 큐로 구성되며, 각각 다른 우선순위가 배정된다. 실행 준비가 된 프로세스는 이 중 하나의 큐에 존재한다.

MLFQ는 실행 순서를 위해 우선순위 사용한다. 우선순위가 높을수록 먼저 실행된다.

큐에 둘 이상의 작업이 존재할 수 있다. 같은 큐에 위치하는 작업은 같은 우선순위를 가지며, RR 스케줄링이 적용된다.

 

MLFQ의 핵심은 우선순위를 정하는 방식이다. 각 작업에 고정된 우선순위를 부여하는 것이 아니라 각 작업의 특성에 따라 동적으로 우선순위를 부여한다. 예를 들어 I/O를 반복적으로 인터럽트하는 작업하는 경우, 우선순위를 높게 유지한다. 대신 한 작업이 오랫동안 CPU를 점유해야 한다면 우선순위를 낮춘다.

 

규칙1 : A의 우선순위 > B의 우선순위 -> A 실행.

규칙2 : A의 우선순위 = B의 우선순위 -> A와 B는 RR방식으로 실행.

 

위 사진과 같이 우선순위가 정해졌다. 그럼 A와 B가 실행되는 동안 C,D는 실행되지 못한다.

사진만으로는 MLFQ의 동작을 정확히 알 수 없다. 시간에 따른 우선순위의 변화를 알아보자.

 

우선순위 조정

우선순위는 곧 큐의 위치이다.

짧은 실행 시간을 갖는 CPU를 자주 양보하는 대화형 작업과 긴 CPU 시간을 요구하지만 응답시간은 중요하지 않은 작업이 섞여 있다.

우선순위 조정을 위한 첫번째 시도는 다음과 같다.

 

규칙3 : 작업이 시스템에 처음 진입하면 가장 높은 우선순위에 놓여진다.

규칙4-1 : 주어진 타임 슬라이스를 모두 사용하면 우선순위는 낮아진다.(제 시간내에 작업을 끝내지 못하면 우선순위가 낮아진다.)

규칙4-2 : 타임 슬라이스가 끝나기 전에 CPU를 양도하면(대화형 or 작업 끝) 같은 우선순위를 유지한다.

 

한 개의 긴 실행 시간을 가진 작업

 

 

위 사진처럼 작업이 최고 우선순위에 진입한 후 타임 슬라이스(10msec)내에 작업을 마치지 못하면 우선순위가 낮아진다(Q1). 낮은 우선순위에서 작업을 마지치 못하면 또 낮아진다(Q0).

 

짧은 작업과 함께

A(검정색)는 일정시간 실행되다가 B(회색)가 도착했다. B가 도착했을 때 가장 높은 우선순위에서 작업을 진행한다. 당연히 A는 작업을 멈춘다. B가 2번의 타임 슬라이스만에 작업을 끝냈다. 이 후 A는 다시 낮은 우선순위에서 작업을 진행한다.

이 예에서 알 수 있는 것은 스케줄러가 작업의 소요 시간은 알지못하기 때문에 무조건 짧은 소요 시간을 가졌다고 가정한다. 진짜 짧다면 가장 낮은 우선순위에 도달하기 전에 작업을 끝낼 것이고 아니라면 낮은 우선순위에 도달할 것이다.

이러한 방식으로 MLFQ는 SJF와 비슷한 방법을 사용한다.

 

입출력 작업이 있는 경우는?

 

규칙 4-2처럼 프로세스가 타임 슬라이스를 소진하기 전에 CPU를 양도하면 같은 우선순위를 유지하게 된다.이 규칙의 의도는 다음과 같다.대화형 작업이 키보드나 마우스로부터 사용자 입력을 대기하며 자주 입출력을 수행한다면 타임 슬라이스가 종료되기 전에 CPU를 양도한다. 그런 경우 우선순위를 유지하게 된다.

 

위 그림을 보면 B(회색)는 대화형 작업으로 입출력을 수행하기 전에 1msec만 실행된다. A(검정색)는 오랜 시간이 걸리기 때문에 낮은 우선순위에 위치해 있다. 낮은 우선순위에 있던 A는 작업 도중 B에게 CPU를 양보한다. B는 타임 슬라이스 내에 작업을 끝냈기 때문에 높은 우선순위를 유지할 수 있다. 

 

현재 MLFQ의 문제점

1.기아 문제(starvation)

많은 대화형 작업이 존재하면 이들이 모든 CPU를 차지하기 때문에 우선순위가 낮은 프로세스들은 작업을 진행할 수 없다.

 

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

스케줄러를 자신에게 유리하도록 만든다는 것은 지정된 시간보다 더 많은 시간을 할당하도록 하는 것이다.

예를 들어 다음과 같은 공격이다. 타임 슬라이스가 끝나기 전에 아무 파일을 대상으로 입출력 요청을 보내 CPU를 양보한다.

그렇게 하면 같은 우선순위에 머무를 수 있고 CPU 점유시간도 올라간다. 타임 슬라이스의 99%를 사용하고 CPU를 양보한 후 다시 작업하면 거의 독점할 수 있다.

 

다른 문제를 해결할 수 있는 방안을 찾아보자.

 

우선순위 상향 조정

기아 문제를 해결하기 위한 방법이 뭐가 있을까?

간단한 방법으로는 모든 작업의 우선순위를 상향 조정하는 것이다.

모든 작업을 최상위로 올리는 것이다.

 

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

 

이 규칙에 의해 두 가지 문제를 해결할 수 있다.

첫번째, 기아 현상으로 부터 벗어날 수 있다. 최상위 큐에 위치해 있으니 다른 프로세스보다 우선적으로 작업을 진행할 수 있다.

두번째, CPU위주의 작업보다 대화형 작업이 많을경우 우선순위 상향을 통해 스케줄러가 변경된 특성에 적합한 스케줄링 방법을 적용한다.

 

예를 들어 긴 실행 시간을 가진 작업과 두 개의 대화형

작업이 CPU를 사용한다 할때, 왼쪽은 우선순위 상향이 없는 그래프, 오른쪽은 있는 그래프이다.

긴 작업은 두 개의 작업이 시작된 이후 CPU를 점유 할 수 없다. 하지만 50msec 마다 우선순위 상향이 있을 경우 꾸준히 작업을 진행 할 수 있다. 하지만 몇msec마다 실행하지는 결정해야 한다. 이 값을 부두 상수라고 한다.

 

더 나은 시간 측정

위 방법으로 기아 문제는 해결했다 하지만 CPU반환을 조작하는 문제는 어떻게 해결할까?

결과를 먼저 말하자면 각 단계에서 CPU 총 사용 시간을 측정하는 것이다.

스케줄러는 현재 단계에서 프로세스가 소진한 CPU 사용시간을 저장한다. 프로세스가 해당 시간을 모두 소비하면 다음  우선순위 큐로 강등된다. 타음 슬라이스를 한번에 소비하든 짧게 여러 번 소비하든 상관 없다. 이제 4-1과 4-2를 합쳐 새로 만든다.

 

규칙4 : 주어진 단계에서 시간 할당량을 소진하면 우선순위가 강등된다.

 

위 그림의 왼쪽은 4-1,4-2 규칙을 적했을 때, 오른쪽은 새로운 규칙 4를 적용했을 때 이다.

왼쪽은 B(회색)가 타임 슬라이스가 끝나기 직전에 CPU를 잠깐 반환해 우선순위를 유지한다.

오른쪽은 사용시간이 정해져 있기 때문에 B(회색)가 사용 시간을 모두 소비하면 우선 순위가 강등된다.

 

MLFQ 조정과 다른 문제들

필요한 변수들을 스케줄러가 어떻게 설정해야 하는지도 중요한 문제이다.

예를 들어 몇개의 큐가 필요한가? 부두 상수는 어떻게 설정해야 하는가? 우선순위 조정 부두 상수는 어떻게 조정하는가?

이러한 부분은 워크로드에 대해 충분히 경험하고 계속 조정을 해야한다.

대부분의 MLFQ들은 큐 별로 타임 슬라이스를 정할 수 있다. 우선순위가 높은 큐는 짧은 타임 슬라이스 시간을 가진다. 대부분 대화형 작업으로 구성되기 때문에 빠르게 교체하는데에 의미가 있다. 낮은 우선순위는 긴 CPU 점유 시간을 가지니 오랜 타임 슬라이스 시간을 가진다.