[OSTEP 가상화(virtualization)]Chapter 8 멀티 레벨 피드백 큐

멀티 레벨 피드백 큐로 알려진 가장 유명한 스케줄링 기법에 대해 알아봅시다.

 

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

• 짧은 작업을 먼저 실행시켜 반환시간을 최적화하기
• MLFQ는 대화형 사용자에게 응답이 빠른 시스템이라는 느낌을 주기위해 응답시간을 최적화

즉 반환시간과 응답시간 모두 잡는 기법입니다.

 

📝11.1 MLFQ의 기본규칙

멀티 레벨 피드백 큐의 기본 알고리즘을 알아보자 현재 구현되어있는 MLFQ들은 차이가 있지만 기본적으로 비슷한 방법을 사용한다.

• MLFQ는 여러 개의 큐로 구성되며, 각각 다른 우선순위가 배정된다.
• 실행 준비가 된 프로세스는 이 중 하나의 큐에 존재한다.
• MLFQ는 실행할 프로세스를 결정하기 위하여 우선순위를 이용한다. 높은 우선순위를 가진 작업은 높은 우선순위 큐에 존재한다.
• 큐에 둘 이상의 작업이 당연히 존재할 수 있다. 이들은 모두 같은 우선순위를 가지며 이 작업들은 라운드 로빈(R.R)을 사용한다.
• MLFQ는 각 작업이 고정된 우선순위를 부여하는 것이 아닌 특성에 따라 동적으로 부여한다.
  • 또한 반복적으로 CPU를 양보했으면 우선순위가 높아진다.
  • 한 작업이 긴 시간동안 CPU를 점유하면 해당 작업의 우선순위가 낮아진다.

기본 규칙

• 규칙1: Priority(A) > Priority(B) 이면, A가 실행된다 (B는 실행되지 는다). 
• 규칙2: Priority(A) = Priority(B) 이면, A와 B는 RR 방식으로 실행된다

📝11.2 시도1: 우선순위 변경

MLFQ가 작업의 우선순위를 바꾸는 규칙을 알아보자

• 규칙 3: 작업이 시스템에 진입하면, 가장 높은 우선순위, 즉 맨 위의 큐에 놓여진다.
• 규칙 4a: 주어진 타임 슬라이스를 모두 사용하면 우선순위는 낮아진다. 즉, 한 단계 아래 큐로 이동한다.
• 규칙 4b: 타임 슬라이스를 소진하기 전에 CPU를 양도하면 같은 우선순위를 유지한다.

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

 

위의 그림처럼 처음에는 가장 높은 우선순위로 들어온다.  그 다음 타임 슬라이스가 지나면 작업 순위가 낮아진다.

점점 낮아지고 이후에는 제일 낮은 우선순위 큐에 들어간다.

 

예시 2: 짧은 작업과 함께

이 예시로 MLFQ가 어떻게 SJF와 근접하는지 이해할 수 있다.

이 예는 2개의 작업이 존재한다. A는 오래 실행되는 CPU 위주 작업이고 B는 짧은 대화형이다. 

A는 이미 실행 상태이기에 제일 낮은 우선순위에 있다. B가 도착하면 가장 높은 우선순위가 되어 먼저 처리된다.

만약 B가 길어지면 A와 같은 우선순위에 위치하게 되고 라운드 로빈으로 진행된다.

 

예시 3: 입출력 작업에 대해

 

대화형 작업이 키보드나 마우스로부터 사용자 입력을 대기하며 자주 입출력을 수행하면 타임 슬라이스 전에 CPU를 양도한다. 이것은 규칙 4B로 이렇게 유지되어 입출력 작업은 최상위가 된다.

 

📌현재 MLFQ의 문제점

현재 MLFQ는 단순하다. CPU를 긴 작업들과 짧은 작업들 사이에 잘 공유하고, 입출력- 중점 대화형 작업을 발리 실행한다.

그러나 심각한 결점이 있다.

• 기아 상태(starvation) 가 발생할 수 있다.
  • 시스템에 너무 많은 대화형 작업이 존재하면 그들이 모든 CPU 시간을 소모하게 될 것
  • 긴 실행 시간 작업은 CPU 시간을 할당받지 못할 것
• 스케줄러를 자신에게 유리하게 동작하도록 프로그램을 다시 작성할 수 있다.
  • 스케줄러를 자신에게 유리하게 동작시킨다는 것은 일반적으로 스케줄러를 속여서 지정된 몫보다 더 많은 시간을 할당하도록 하게 만드는 것을 가리킨다.
• 프로그램은 시간 흐름에 따라 특성이 변할 수 있다.
  • CPU 위주 작업이 대화형 작업으로 바뀔 수 있다.

 

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

규칙을 보완하여 기아 문제를 방지하는 방법을 알아보자.

기아 방지에는 CPU 위주 작업이 조금이라도 진행하는 것을 보장하는 것이다. 간단한 아이디어는 주기적으로 모든 작업의 우선순위를 상향 조정하는 것이다. 

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

이 규칙은 두 가지 문제를 한번에 해결한다.

1. 프로세스가 기아 상태에 빠지지 않는다. 최상위 큐에서 RR 방식으로 동작하기 대문이다.
2. CPU 위주의 작업이 대화형 작업으로 특성이 변할 경우 우선순위 상향을 통해 스케줄러가 변경된 특성에 적합한 스케줄링 방법을 적용한다.

 

이때 일정 시간 S는 부두 상수라고 불린다.

 

📝11.4 시도3: 더 나은 시간 측정

해결해야 할 문제가 하나 더 있다. 스케줄러를 자신에게 유리하게 동작시키는 것을 어떻게 막을 수 있을까?

MLFQ의 각 단계에서 CPU 총 사용 시간을 측정하는 것이다.

• 규칙 4: 주어진 단계에서 시간 할당량을 소진하면, 우선순위는 낮아진다.

📝11.5 MLFQ 조정

MLFQ 스케줄링에는 몇가지 다른 쟁점들이 남아있다.

• 몇 개의 큐가 존재해야 하는가?
• 큐당 타임 슬라이스의 크기는?
• 기아를 피하고 변화된 행을 반영하기 위해 우선순위 상향을 얼마나 자주해야하는가?

사실 최선은 없다.

 

📝11.5 MLFQ 요약

• 규칙 1: 우선순위(A) > 우선순위(B) 일 경우, A가 실행, B는 실행되지 않는다.
• 규칙 2: 우선순위(A) = 우선순위(B) 일 경우, A와 B는 RR 방식으로 실행된다.
• 규칙 3: 작업이 시스템에 들어가면 최상위 큐에 배치된다.
• 규칙 4: 작업이 지정된 단계에서 배정받은 시간을 소진하면, 작업의 우선순위는 낮아진다.
• 규칙 5: 일정 주기 S가 지난 후, 시스템의 모든 작업을 최상위 큐로 이동시킨다.