[OSTEP] Ch3.3. Scheduling: Multi-level Feedback Queue(MLFQ)

Operating Systems: Three Easy Pieces: Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau
https://pages.cs.wisc.edu/~remzi/OSTEP/
본 글은 위 교재을 주교재로 한 학교 '운영체제(Operating Systems)' 수업을 들으며 공부한 내용을 정리한 글입니다.

해당 글은 개인 공부 및 교육 목적으로 작성하였으며, 일부 교재에 첨부된 사진(또는 교재에서 강의노트로 첨부된 사진)들을 포함하고 있습니다.
교재 출처 사진을 최소화하고자 블로그에는 핵심 사진을 제외하곤 옮기지 않은 사진들도 있습니다. 따라서 고의로 누락한 사진들이 존재하며, 해당 사진들을 언급하는 내용이 있을 수 있습니다. 누락한 사진들은 직접 교재를 참고해 주세요.

혹시 문제가 있다면, 댓글 남겨주시면 빠른 시일 내에 확인 후 적절한 조치를 취하겠습니다.

---

Multi-Level Feedback Queue (MLFQ)

• 과거로부터 학습해서 미래를 예측하는 스케쥴러(또는 스케쥴링 방식)임.
• 목적:
  • 짧은 작업을 먼저 실행시켜, turnaround time을 최적화하자!
    • → 아까 SJF로 turnaround time을 줄일 수 있었잖음!!
    • → 그러니 SJF의 알고리즘을 일부 따오자.
  • 사용자에게 빠른 응답을 제공하기 위해, response time을 최소화하자!
    • 단, 우리에겐 작업의 길에에 대한 사전 정보가 미리 주어지지 않는다.(a priori knowledge of job length가 없음.)
    • → 아까 RR로 response time을 줄일 수 있었잖음!!
    • → 그러니 RR의 알고리즘을 일부 따오자.
• 핵심은:
  • ‘작업의 실행 시간에 대한 사전 정보 없이,
  • 어떻게 response time을 최소화하면서
  • 동시에 turnaround time을 최적화하는 스케쥴러를 설계할 수 있을까??
    • 즉, 우리가 작업 완료 시간을 모르기에 STCF를 쓸 수 없게 됐는데, 이제 어떻게 turnaround time을 줄일 수 있을까?
• 마지막에 보면 그래서 RR보다 MLFQ가 왜 더 개선됐냐고 물을 수 있는데,
  • RR은 대화형 작업을 구분하지 못하고 배치 작업과 동일한 우선순위로 반복하기에,
    • response time이 MLFQ보다 길어짐.
  • 또한, 짧은 작업들을 MLFQ는 먼저 끝낼 수 있기에,
    • (전체적인) turnaround time도 짧아짐.
    • turnaround time이 아까 SJF/STCF에서 짧은 놈을 먼저 끝내서 개선됐다는 걸 기억!!
• GPT답변) RR 대비 MLFQ가 좋은 점.다단계 피드백 큐(Multilevel Feedback Queue, MLFQ)는 라운드 로빈(Round Robin, RR)에 비해 여러 측면에서 개선된 스케줄링 방식이며, 특히 Turnaround Time과 Response Time의 관점에서 다음과 같은 장점이 있습니다.

• 다단계 피드백 큐(Multilevel Feedback Queue, MLFQ)는 라운드 로빈(Round Robin, RR)에 비해 여러 측면에서 개선된 스케줄링 방식이며, 특히 Turnaround Time과 Response Time의 관점에서 다음과 같은 장점이 있습니다.
• 1. Turnaround Time 개선
  • RR은 모든 프로세스에 동일한 시간 할당량(Time Quantum)을 적용하므로, 짧은 작업이든 긴 작업이든 동일한 방식으로 스케줄링됩니다. 이로 인해 긴 작업은 여러 번 실행되면서 문맥 교환(Context Switching)이 증가하고, 전체적인 Turnaround Time이 증가할 수 있습니다.
  • 반면 MLFQ는 자주 실행되는 짧은 작업을 우선 처리하고, 긴 작업은 점차 낮은 우선순위 큐로 이동시킵니다. 즉, 짧은 작업은 빠르게 끝나도록 처리하여 짧은 작업의 평균 Turnaround Time을 줄이고, 긴 작업도 효율적으로 실행할 수 있습니다.
• 2. Response Time 개선
  • RR에서는 모든 프로세스가 동일한 Time Quantum을 가지므로, 대기 시간이 길어질 수 있습니다. 특히 짧은 작업이 긴 작업과 섞여 있을 경우, 짧은 작업도 긴 작업과 동일한 방식으로 실행되기 때문에 불필요한 대기 시간이 발생할 수 있습니다.
  • MLFQ는 새로운 작업을 가장 높은 우선순위 큐에 배치하므로 짧은 작업이나 I/O 중심 작업이 즉시 실행될 가능성이 큽니다. 따라서 사용자가 체감하는 Response Time이 RR보다 개선됩니다.
• 결론
  • MLFQ는 짧은 작업을 먼저 실행하여 Turnaround Time을 줄이고, 새로운 프로세스를 빠르게 실행하여 Response Time을 개선하는 구조를 가지고 있습니다.
  • 반면 RR은 모든 프로세스를 공평하게 다루지만, 짧은 작업도 긴 작업과 동일한 방식으로 처리되어 효율성이 떨어지는 경우가 있습니다.
  • 이러한 이유로 MLFQ는 다양한 프로세스가 혼합된 환경에서 RR보다 성능이 뛰어난 스케줄링 기법으로 평가됩니다.

MLFQ: Basic Rules

• MLFQ는 여러 개의 큐(queue)를 가지고 있는데,
  • 각각의 큐에는 각기 다른 우선순위 레벨(priority level)이 할당되어 있음.
• 레디(ready) 상태인 작업들은 다들 어떤 큐 안에 들어가있게 되는데,
  • 규칙1: 더 높은 우선순위를 가진 큐에 있는 작업이 먼저 선택받아 실행된다.
  • 규칙2: 같은 우선순위를 가진 큐에 있는 작업들끼리는 RR 스케쥴링 방식을 사용한다.
• 수식으로 나타내면 아래와 같다.

Rule 1:
 If Priority(A) > Priority(B), A runs (B doesn’t).
Rule 2:
 If Priority(A) = Priority(B), A & B run in RR.

MLFQ Example

• (우리가 지금까지 배운) MLFQ 알고리즘에 따르면,
  • 스케쥴러는 가장 높은 우선순위를 가진 큐의 A와 B만을 번갈아 실행할 것이다.
  • 불쌍한 작업 C와 D는 A, B가 완료되기 전까진 실행되지도 않는다!!!!! ㅠㅠ C, D의 response time은 나락에 가게 된다.
• 따라서, 우린 작업들의 우선순위를 유동적으로 바꿔줄 필요가 있다.

MLFQ: 우선순위 조정 기본 아이디어

• MLFQ는 각 작업의 관찰된 행동에 따라 우선순위를 바꿔나간다.
  • 여기서, 우선순위를 바꾼다는 것은, 해당 작업을 다른 우선순위를 가진 큐로 옮긴다는 것이다.
• Example:
  • 만약 어떤 작업이 I/O 작업을 계속 발생시키며 CPU를 계속 양보(포기)한다면:
    • → 이 작업은 (I/O가 잦아서 짧은 응답이 중요한) 대화형 작업이라고 판단하여 우선순위를 높게 유지한다.
  • 만약 어떤 작업이 오랜 시간동안 CPU를 집중적으로 사용하고 있다면:
    • → 이 작업은 그다지 대화형 프로세스는 아닌 것 같고, 따라서 짧은 응답이 중요해보이진 않으니 우선순위를 낮게 설정함.
    • 즉, 해당 작업이 배치형 작업이라고 판단한 것이다.
  • 대화형 시스템(작업)(Interactive System): 사용자의 요청에 대한 결과를 곧바로 얻을 수 있어, 컴퓨터와 사용자가 1:1 처럼 보이는 시스템.
    • 즉, 사용자가 명령어를 입력하면 그 결과를 빠른 시간 내에 화면에 표시해준다는 것이다.
    • 대화형 작업들은 즉각적인 피드백이 중요하므로, 입력이 들어왔을 때 빠르게 CPU를 가져와서 처리하고 출력으로 내보낼 수 있어야 함. 따라서 CPU 우선순위를 최대한 높게 가져야 함.
  • 배치 작업(batch job): 백그라운드에서 오래 실행되며, CPU 집중적인 작업.
    • 보통 사용자에게 빠른 응답이 필요하지 않은 작업들임.
    • 파일 다운로드, 비디오 인코딩 등.
    • 배치 작업에는 낮은 우선순위를 주도록 설계해야 함.
• 이런 식으로 하면, MLFQ는 SJF에 근사한다.

MLFQ: How to Change Priority

• 이제, 위의 기본 아이디어를 알고리즘으로 구현하자.
• MLFQ 우선순위 조정 알고리즘(MLFQ priority adjustment algorithm)
  • 규칙3: 만약 어떤 작업이 시스템에 도착하면,
    • 해당 작업을 가장 높은 우선순위의 큐에 넣는다.
  • 규칙 4a: 만약 어떤 작업이 실행되는 동안 time slice 하나를 통째로 다 사용했으면,
    • 해당 작업의 우선순위를 낮춘다.
    • (다시 말해, 해당 작업을 더 낮은 우선순위의 큐에 넣는다.)
  • 규칙 4b: 만약 어떤 작업이 time slice 하나를 다 사용하기 전에 CPU를 포기했으면(I/O 작업을 한다든가…),
    • 그 작업은 현재 우선순위 레벨을 유지한다.
• 즉, MLFQ는 작업의 우선순위가 고정되어 있지 않으며, 이는 각 작업의 과거 행동에 기반해 변경된다는 거임.
  • MLFQ의 F가 Feedback인 이유가 여기서 나옴.

Example 1: A Single Long-Running Job

• time slice가 10ms고, 세 개의 큐를 가진 스케쥴러가 있다.
• 긴 실행 시간을 가진 하나의 작업이 시스템에 도착하면, 우선 Q2로 진입한다.
• 그리고 10ms짜리 time slice 하나가 지나면, 스케쥴러는 해당 작업의 우선순위를 한 단계 낮추어 Q1으로 이동시킨다.
• 다시 A1에서 10ms짜리 time slice 하나가 지나면, Q0으로 이동하게 되며 이후에는 계속 Q0에 계속 머무르게 된다.

Example 2: Along Came a Short Job

• 가정:
  • 작업 A: CPU 집중적으로 오래 실행되고 있는 작업
  • 작업 B: 대화형의 짧게 실행되는 작업(20ms 런타임)
  • A는 이미 얼마 동안 실행되고 있던 상황이고, B가 T=100일 때 시스템에 도착함.
• 보면, MLFQ가 마치 SJF처럼, A에게서 제어권을 빼앗아 B를 실행시키고 있음을 볼 수 있다.
  • 즉, MLFQ 스케쥴러는 작업이 짧은 작업인지 긴 작업인지 알 수가 없기 때문에,
  • 일단 짧은 작업이라고 가정하여 높은 우선순위를 부여한다.
    • 그 후, 진짜 짧은 작업이라면 빨리 실행되고 바로 종료될 것이고,
    • 짧은 작업이 아니라면 천천히 아래 큐로 이동하여 CPU 집중적으로 천천히 실행될 것이다.

Example 3: What About I/O?

• 가정:
  • 작업 A: CPU 집중적으로 오래 실행되고 있는 작업
  • 작업 B: I/O를 수행하기 전에 CPU를 1ms동안만 원하는 대화형의 작업
• 보면, 작업 B는 time slice 하나를 다 쓰기 전에 CPU를 계속 포기(양보)해버리고 있으므로, 스케쥴러는 작업 B의 우선순위를 그대로 유지한다.
  • 이는 B같이 CPU를 계속 포기하는 작업은, I/O 작업이 잦은 대화형 프로세스가 나타내는 전형적인 패턴이기 때문에,
  • 대화형 작업을 빨리 실행시켜 사용자가 느끼는 response time을 최소화하겠다는 당초의 목적과 부합한다.

Problems with the Basic MLFQ

• 현재 MLFQ는 잘 동작하는 것처럼 보이지만, 아직까지는 다음과 같은 심각한 결점들을 가진다.

1. Starvation(기아 상태)
   • 시스템에 너무 많은 대화형 작업들이 존재하면,
   • 긴 실행 시간 작업들은 CPU 시간을 거의 할당받지 못해 굶어 죽을 것이다.
   • 우리는 이러한 시나리오에서도 긴 실행 시간 작업들이 굶어죽이 않고, 실행될 수 있게 만들고 싶다.
2. 똑똑한 사용자라면 스케쥴러를 자신에게 유리하게 동작하도록 만들 수 있다.
   • 이는 스케쥴러를 속여서 지정된 몫보다 더 많은 시간을 내 프로세스가 할당받도록 만드는 것이다.
   • time slice가 99% 등 거의 다 끝나갈 때 아무 파일을 대상으로 입출력 요청을 내려 CPU를 양도하면,
   • 해당 작업은 더 높은 퍼센트의 CPU 시간을 가져가게 된다.
3. 프로그램은 시간이 흐름에 따라 그 행동(behavior)이 변할 수 있다.
   • CPU 집중 작업이 대화형 작업으로 바뀔 수도 있다는 것이다.
   • 현재 구현 방식으로는 그렇게 바뀐 작업은 다른 대화형 작업들과 같은 대우를 받을 수 없다.

The Priority Boost

• 규칙을 보환하여, 기아 문제를 방지할 수 있는지 살펴보자. 어떻게 해야 CPU 집중 작업이 조금이라도 진행되게 할 수 있을까?
  • → 주기적으로 모든 작업의 우선순위를 상향 조정(boost)하면 된다. 모두 최상위 큐로 보내는 것이다.
• 규칙5: 일정 기간 S가 지나면, 시스템의 모든 작업을 최상위 큐로 이동시킨다.
• 이는 두 가지 문제를 해결하는데:
  • 이러면, 이제 CPU 집중 작업은 최상위 큐에 있는 동안은 RR에 의해 time slice단위로 조금씩이나마 실행이 가능해, 굶지 않게 된다.
  • 또한, CPU 집중 작업이 대화형 작업으로 행동이 변할 경우, 우선순위 상향을 통해 스케쥴러가 변경된 작업을 진정한 대화형 작업으로 대하게 된다.
• Example:

  

  • 위는 긴 실행 시간을 가진 작업 A가 두 개의 대화형 작업들과 CPU를 두고 경쟁하는 모습이다.
  • 왼쪽은 우선순위 상향(boost)가 없는 상황, 오른쪽은 있는 상황을 보고 있다.
  • 오른쪽은 50ms마다 우선순위 상향이 일어나, 꾸준히나마 CPU 집중 프로세스 또한 굶어 죽지 않고 조금식 실행된다.
• 여기서 몇 초마다 우선순위 상향(boost)을 해줘야 할지, 즉 적절한 S값을 정하는 것이 필요하다.
  • 너무 크면 긴 실행 시간을 가진 작업은 굶을 수 있으며,
  • 너무 작으면 대화형 작업이 적절한 양의 CPU 시간을 사용할 수 없을 것임.

Better Accounting

• 어떻게 사용자를 속이는 프로세스가 스케쥴러을 갖고 노는 걸 방지할 수 있을까?
  • 이는 규칙 4a와 4b떄문에 생긴 꼼수였다.
• 해결책: MLFQ 각 단계에서 CPU 총 사용 시간을 측정하는 것이다.
  • 스케쥴러는 현재 단계에서 프로세스가 소진한 CPU 사용 시간을 저장한다.
  • 프로세스가 time slice에 해당하는 시간을 모두 소진하면, 우선순위를 하나 내린다.
• 규칙 4a와 규칙 4b를 다음과 같이 다시 정의하자.
  • 규칙 4: 어떤 작업이 CPU를 얼마나 포기해왔는지에 상관없이, 주어진 단계에서 그것의 time 할당량을 다 써버렸다면, 그것의 우선순위를 하나 내린다.
• Example:

  

  • 9 1 9 1 1 9 9 1 1 9 9 1 1 9 생각
  • A가 처음 2번 내려간 건 자기의 타임 슬라이스 10초 다 써서.
  • 그리고 A가 찍먹하고 올라온 건 9초 때의 CPU 사용 필요성 땜에.
  • 이거 좀 비정확한 사진임 아래가 그나마 더 정확(위는 I/O 9초가 반영이 안 돼있음.)
  • 9 1 1 8 1 2 8 7 1 3 9 6 1 4 9 5 1 5
  • 그냥 다 됐고, 한글 11.6 짤(이해하기 더 쉬움)에 왼쪽에서 오른쪽으로 가는 거에서, ‘자기꺼 다 쓰면 우선순위 내려감’ 하나만 추가된 거임.
    • 즉, 전역적인 타임슬라이스 개념은 유효함.
    • 엄격한 구현은 아래 9 8 7… 인 듯
  • 저 하얀색으로 A(B?)가 찍고 다시 올라오는 건, 9초마다 CPU 사용해서임.
  • 아닌가… 또 헷갈리네…
  • 보면, 왼쪽에서는 아까처럼 해당 프로세스가 꼼수를 부려가며 I/O를 발생시키고 있는데,
  • 오른쪽에서는 아까처럼 꼼수를 부리려고 해도 다음 CPU 사용 단계에서 누적된 time slice를 하나 소진해버리기 때문에, 우선순위가 내려가게 된다.
    • 따라서, 결국 CPU 집중 작업과 우선순위가 같아지게 되어, RR 방식으로 작업을 진행하게 된다.
      • 이거 좀 이해 안갈 수도 있는데, 자세히 보면 Q0이 두 줄로 돼어있어서 헷갈리는 거임. 천천히 살펴보면 해당 꼼수 프로세스는 우선순위가 한 수준씩 내려오고 있고, Q1 → Q0 순간부터 RR로 작동해 time slice를 다 쓰면 context switching이 일어남.
  • 참고로, 보면 A가 I/O 일으키는 시점을 9초 시점이라 생각하면, 8초, 7초, 6초, … 이렇게 점점 밀리는 걸 볼 수 있다.
• 이거 보면 좀 이상함... 교재에서는 쉽게 설명하기 위해 좀 엄밀한 설명을 포기한 거 아닐까 싶은데... 기존의 time slice의 전역적인 적용을 여기서도 똑같이 적용해야 하는지, 아님 locally한 본인의 time slice개념만 적용해야 하는지 안 나와있음... 헷갈림.
  • 따라서, 위에 저렇게 엄밀하게 생각해보려고 하지 말고, 그냥 "이젠 각 작업이 자신의 time slice를 소진하면 우선순위가 내려가게 되어, 사용자를 속이는 프로세스가 스케쥴러를 갖고 노는 걸 방지할 수 있게 됐다!!"고만 생각하고 넘어가자. 지금 단계에서 내가 너무 과하게 파고들 내용은 아닌 듯함.

Tuning MLFQ And Other Issues

• MLFQ 스케쥴링에는 여러 쟁점들이 남아 있다.
• 필요한 변수들을 스케쥴러가 어떻게 설정해야 하는가?
  • 예를 들어, 몇 개의 큐가 존재해야 하는가?
  • 큐 당 time slice의 길이는 얼마로 해야 하는가?
  • 기아를 피하고 변화된 행동을 반영하기 위하여 얼마나 자주 우선순위가 상향 조정되어야 하는가?(즉, S값을 몇으로 해야 하는가?)
• 이러한 질문들에 쉽게 대답할 순 없음. 경험을 쌓아서 균형점을 찾아야 함.
• 예를 들어, 대부분의 MLFQ 기법들은 큐 별로 time slice의 길이를 변경할 수 있다.
  • 일반적으로, 우선순위가 높은 큐에는 짧은 time slice가 적합하다.
    • 이러한 큐에는 짧게 실행되는 대화형 작업들이 자주 존재하게 될 것이므로, 이 작업들을 빠르게 교체하는 것은 의미가 있다.
      • ex. 10ms 이하
  • 반대로, 우선순위가 낮은 큐에는 긴 time slice가 적합하다.
    • 이러한 큐에는 CPU 집중의 오래 실행되는 작업들이 자주 존재하게 될 것이므로, 이 작업들은 그다지 빠르게 교체될 필요가 없다.
      • ex. 수백ms
• 이러한 정보에 따라 MLFQ 스케쥴러를 구성하면, 아래와 같이 나올 수 있다.

The Solaris MLFQ implementation

• 예시로서 Solaris에선 MLFQ가 어떻게 구현되었는지 살펴보자.
• Time-Sharing scheduling class(TS)는 Solaris에서 사용하는 스케쥴링 방식 중 하나인데, MLFQ를 사용하였다.
  • MLFQ 큐의 개수는 60개이고,
  • 천천히 증가하는 time slice 길이를 가진다.
    • 가장 높은 우선순위의 큐는 20ms
    • 가장 낮은 우선순위의 큐는 몇백 ms의 time slice을 가진다.
  • 우선순위 상향은 대략 1분 정도마다 이루어진다.
• 일부 OS들은 가장 높은 우선순위들은 운영체제 작업을 위해 예약해 두기도 한다.
• 보면, 아래 Solaris의 TS에는 총 170개의 큐가 있는데, 이 중 사용자 작업에 해당하는 0~59까지의 우선순위의 큐들은 오른쪽과 같이 time slice과 운영체제를 가진다.
  • (오른쪽 사진의 세, 네 번째 열은 각각 time slice 다 썼을 때 우선순위 어디로 보낼 지, 그리고 time slice 덜 쓰고 끝났을 때 우선순위 어디로 보낼 지가 해당된다.)

https://www.cs.csustan.edu/~john/Classes/CS3750/Notes/Chap05/05_CPU_Scheduling.html

MLFQ: Summary

• 우리가 최종적으로 정의한 MLFQ 규칙들은 다음과 같다.
  • 규칙 1 : 우선순위 (A)> 우선순위 (B) 일 경우, 가 실행, B는 실행되지 않는다.
  • 규칙 2 : 우선순위 (A) = 우선순위 (B), A와 는 RR 방식으로 실행된다.
  • 규칙 3 : 작업이 시스템에 들어가면 최상위 큐에 배치된다.
  • 규칙 4 : 작업이 지정된 단계에서 배정받은 시간을 소진하면 (CPU를 포기한 횟수와 상관 없이), 작업의 우선순위는 감소한다 (즉, 한 단계 아래 큐로 이동한다).
  • 규칙 5 : 일정 주기 S 가 지난 후, 시스템의 모든 작업을 최상위 큐로 이동시킨다
• 이러한 규칙들을 통해, MLFQ는 turnaround time과 response time을 모두 최적화한다.
  • 즉, response time를 최소화하면서, turnaround time도 그리 길지 않게 최적화하고자 하는 게 MLFQ의 도입 목적임.
    • 여기서 MLFQ 사용 시 turnaround time을 최적화하고자 노력한다는 이유는, 짧게 실행되는 대화형 작업에 대해서는 SJF/STCF처럼 전반적으로 우수한 성능을 제공하고,
    • 오해 실행되는 CPU 집중 작업들에 대해서도 최대한 공정하게 실행하여 조금이라도 진행되도록 하기 때문이다.
  • 이러한 이유로, 많은 운영체제들이 기본 스케쥴러로 MLFQ를 사용한다.