[OSTEP] Virtualization) 8. Multi-level Feedback

[OSTEP] 8. Multi-level Feedback

이 포스팅은 $<$Operating Systems: Three Easy Pieces$>$, Remzi H. Arpaci-Dusseau & Andrea C. Arpaci-Dusseau을 읽고 개인 학습용으로 정리한 글입니다.

CH8. 멀티 레벨 피드백 큐

• 작업의 실행시간에 대한 선행 정보 없이 대화형 작업의 응답시간을 최소화하고 동시에 반환시간을 최소화하는 스케쥴러를 어떻게 설계할 수 있는가?

1. MLFQ: 기본 규칙

• 각각 다른 우선순위(priority level)가 배정된 여러 개의 큐로 구성

• 실행 준비가 된 프로세스는 이 중 하나의 큐에 존재

• 높은 우선순위를 가진 작업 선택
  = 높은 우선순위를 가진 큐에 존재하는 작업 선택

• 큐에 둘 이상의 작업 존재 가능
  -> 모두 같은 우선순위를 가진다
  -> 이 작업들 사이에는 RR 스케쥴링 알고리즘 사용

• MLFQ는 각 작업에 고정된 우선순위 부여 X
  -> 각 작업의 특성에 따라 동적으로 우선순위 부여

• 작업이 진행되는 동안 해당 작업의 정보를 얻고, 이 정보를 이용하여 미래 행동 예측
  -> 작업이 반복적으로 CPU를 양보하면 해당 작업의 우선순위 높게 유지
  -> 작업이 긴 시간동안 CPU를 집중적으로 사용하면 해당 작업의 우선순위 낮춤

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

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

예

2. 시도 1: 우선순위의 변경

• 규칙 3: 작업이 시스템에 진입하면, 가장 높은 우선순위에 놓는다

• 규칙 4a: 주어진 타임 슬라이스를 다 사용하면 우선순위는 낮아진다

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

• 스케쥴러는 작업이 짧은 작업인지 긴 작업인지 알 수 없음
  -> MLFQ는 일단 짧은 작업이라고 가정하여 높은 우선순위를 부여
  -> 짧은 작업이라면 빨리 실행되어 바로 종료됨
  -> 짧은 작업이 아니라면 천천히 우선순위 낮아짐
  => SJF를 근사할 수 있게 됨

한 개의 긴 실행을 가진 작업

짧은 작업과 함께 (반환시간 최적화)

• 작업 A: 오래 실행되는 CPU 위주 작업, 얼마 동안 이미 실행해온 상태

• 작업 B: 실헹 시간 20ms의 짧은 대화형 작업, T= 100에 시스템에 도착

• A는 가장 낮은 우선순위 큐에서 실행되고 있음

• B는 시스템에 도착하고 가장 높은 우선순위 큐에 놓여짐
  -> 실행시간이 짧기 때문에 두 번의 타임 슬라이스를 소모하면 바닥 큐에 도착하기 전에 종료

• A는 낮은 우선순위에서 실행 재개

입출력 작업 (응답시간 최적화)

• 작업 B(회색): 대화형 작업, 입출력을 수행하기 전에 1msec동안만 실행됨

• 작업 A(검정색): 긴 배치형 작업, B와 CPU를 사용하기 위해 경쟁

• B는 CPU를 계속해서 양도하기 때문에 MLFQ는 B를 가장 높은 우선순위로 유지

• B가 대화형 작업이라면 MLFQ는
  대화형 작업을 빨리 실행시킨다는 목표에 근접하게 됨

현재 MLFQ의 문제점

• 기아 상태 (starvation)
  -> 프로세스에 너무 많은 대화형 작업이 있는 경우 긴 실행시간 작업은 CPU 할당 X

• 스케쥴러를 자신에게 유리하게 동작하도록 프로그램 작성 가능
  -> 타임슬라이스가 끝나기 전에 아무 파일을 대상으로 입출력 요청을 내려 CPU 양도
  -> 같은 우선순위의 큐에 머무르며 더 많은 CPU 시간 얻게됨

• 프로그램은 시간에 따라 특성이 변할 수 있음
  -> CPU 위주 작업이 대화형 작업으로 바뀌는 경우 다른 대화형 작업들과 같은 대우 받을 수 X

3. 시도 2: 우선순위의 상향

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

• 주기적으로 모든 작업의 우선순위를 상향 조정(boost)
  -> 프로세스는 굶지 않는다는 것을 보장할 수 있게 됨
  -> CPU 위주의 작업이 대화형 작업으로 특성이 변할 경우 스케쥴러가 변경된 특성에 적합한 스케쥴링 방법 적용할 수 있게 됨

• S값 너무 크면 긴 실행시간을 가진 작업은 굶을 수 있음
  S값 너무 작으면 대화형 작업이 적절한 양의 CPU 시간을 사용할 수 없음

예

• 긴 실행 시간을 가진 작업이 두 개의 대화형 작업과 CPU를 경쟁할 때

• 우선순위 상향이 없는 경우(좌쪽):
  긴 실행시간 작업은 두 개의 짧은 작업이 도착한 이후에는 굶게됨

• 50msec 마다 우선순위 상향이 일어나는 경우(우쪽):
  긴 실행시간 작업도 꾸준히 진행된다는 것을 보장 O

4. 시도 3: 더 나은 시간 측정

• 스케쥴러를 자신에게 유리하게 동작시키는 것을 어떻게 막을 수 있는가?

• MLFQ 스케쥴러는 현재 단계에서 프로세스가 CPU를 사용한 총 시간 측정
  -> 프로세스가 타임 슬라이스에 해당하는 시간을 모두 소진하면 다음 우선순위 큐로 강등
  (타임 슬라이스를 한번에 소진하든 짧게 여러번 소진하든 상관 X)

• 규칙 4: 주어진 단계에서 시간 할당량을 소진하면 CPU를 몇 번 양도했는지와 상관없이 우선순위 낮아진다

예

• 조작에 대한 내성이 없는 경우(좌측):
  프로세스는 타임 슬라이스가 끝나기 직전 입출력 명령을 내림
  -> CPU 시간 독점

• 조작에 대한 내성이 있는 경우(우측):
  프로세스의 입출력 행동과 무관하게 아래 단계로 천천히 이동
  -> CPU를 자기 몫 이상으로 사용할 수 X

5. MLFQ 조정과 다른 쟁점들

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

• 워크로드에 대해 충분히 경험하고 계속 조정해 나가며 균형점 찾아야

타임 슬라이스의 크기

• 대부분의 MLFQ에서 큐 별로 타임 슬라이스를 변경할 수 있다

• 우선순위가 높은 큐:
  대화형 작업으로 구성됨, 이 작업들을 빠르게 교체하는 것이 의미 있음
  -> 짧은 타임 슬라이스가 적합 (ex. 10msec 이하)

• 우선순위가 낮은 큐:
  CPU 중심의 오래 실행되는 작업들로 구성됨
  -> 긴 타임 슬라이스가 적합 (ex. 수백msec)

• 일부 스케쥴러의 경우 가장 높은 우선순위를 운영체제 작업을 위해 예약
  -> 일반적인 사용자는 가장 높은 우선순위를 얻을 수 없음

• 일부 시스템은 사용자가 우선순위를 정하는 데 도움을 줄 수 있도록 허용
  -> 작업의 우선순위를 옾이거나 낮춰서 작업의 실행 순서를 바꿀수 있음

스케쥴러의 다른 여러 가능

• 일부 스케쥴러의 경우 가장 높은 우선순위를 운영체제 작업을 위해 예약해둠
  일반적인 사용자 작업은 시스템 내에서 가장 높은 우선순위를 얻을 수 없음

• 일부 시스템은 사용자가 우선순위를 정하는 데 도움을 줄 수 있도록 허용
  ex. ⚡명령어 라인 도구인 nice를 사용하여 작업의 우선순위를 높이거나 낮출 수 있음

6. 요약

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

MKFQ의 특징

• 작업의 특성에 대한 정보 없이, 작업의 실행을 관찰한 후 그에 따라 우선순위를 지정한다

• 반환 시간과 응답 시간을 모두 최적화한다*

• 짧게 실행되는 대화형 작업에 대해서는 우수한 전반적인 성능을 제공한다 (SJF/STCF와 유사)

• 오래 실행되는 CPU-집중 워크로드에 대해서는 공정하게 실행하고 조금이라도 진행되도록 한다