• 2024.06.07: 복습 및 글 다듬기

Operating Systems : Three Easy Pieces를 보고 번역 및 정리한 내용들입니다.

Multi-level Feedback Queue(MLFQ)에서 해결되어야 하는 과제는 두 가지다.

1. 반환 시간 최적화
   • OS는 일반적으로 작업이 얼마나 오래 실행될지 모른다.
2. 응답 시간 최소화
   • RR의 경우, 응답 시간에 있어서는 최적이지만 반환 시간에 있어서는 최악이다.

1. MLFQ : Basic Rules

MLFQ는 여러 개의 다른 큐들을 가지고 있으며, 이 큐들은 서로 다른 우선 순위를 가지고 있다. 특정 시간에 실행될 작업은 하나의 큐에 들어가 있는데, MLFQ는 해당하는 시간에 실행할 작업을 선택하기 위해서 큐의 우선 순위를 사용하며, 우선 순위가 높은 작업은 먼저 실행되도록 선택된다.

물론 하나 이상의 작업이 같은 우선 순위를 가진 큐에 있을 수도 있는데, 이 경우에는 라운드 로빈을 사용한다.

Rule 1: 작업 A의 우선 순위가 B보다 높으면 A가 실행된다.
Rule 2: 작업 A, B의 우선 순위가 서로 같으면 라운드 로빈 방식으로 실행된다.

MLFQ 스케줄링의 핵심은 스케줄러가 우선순위를 어떻게 설정하는지에 있다. MLFQ는 각 작업에 고정된 우선순위를 부여하기보다는 작업의 행동을 관찰하고 그에 따라 우선 순위를 변화시킨다.

예를 들어 작업이 계속해서 키보드 입력을 대기하면서 CPU 소유권을 포기하는 경우, MLFQ는 해당 작업의 우선순위를 높게 유지한다. 반대로 만약 작업이 CPU를 오랫동안 많이 사용했다면, MLFQ는 그 우선순위를 줄인다. 이런 방식으로 MLFQ는 프로세스들이 실행되면서 프로세스들에 대해서 배우고, 미래의 행동을 예측하기 위해 작업 이력을 사용한다. 시간이 지남에 따라 작업의 우선 순위가 어떻게 바뀌는지 알아보자.

2. Attempt #1 : How To Change Priority

MLFQ가 작업의 lifetime에 따라 작업의 우선 순위를 어떻게 바꾸는지를 정해야 한다. 워크로드에는 실행 시간이 짧고 인터랙티브한 작업들과 오랫동안 실행되며 CPU 시간을 많이 사용하며 응답 시간은 크게 중요하지 않은 작업들이 있다고 하자.

이를 위해 우리는 작업의 allotment라는 새로운 개념을 사용한다. Allotment는 스케줄러가 작업의 우선 순위를 줄이기 전에 특정한 우선 순위 수준에서 쓰는 시간의 양을 말한다.

Rule 3: 작업이 시스템에 들어오면, 이는 가장 높은 우선 순위의 큐에 들어간다.
Rule 4a: 만약 작업이 그 allotment를 전부 사용하면 우선 순위가 낮아진다.
Rule 4b: 만약 작업이 allotment를 다 쓰기 전에 I/O 연산 등으로 CPU 사용을 포기하면 우선 순위를 유지한다.

예제 1. A Single Long-Running Job

오랫동안 실행되는 하나의 작업 A만이 있다고 하자. 이 작업은 시스템에 들어오면 가장 높은 우선 순위를 가지고 실행된다. 여기서 시스템은 time-sharing이므로 작업은 작은 시간 단위로 나뉘어 실행된다. 이때 작업의 allotment와 작업이 나뉘는 시간 단위가 서로 동일하다고 가정하자.

1. 작업 A가 가장 높은 우선 순위 레벨에서 한 시간 단위동안 실행된다.
2. allotment를 다 썼으므로 우선 순위가 낮은 큐로 이동한다.
3. 해당 레벨에서 시간 단위동안 실행된다.
4. allotment를 다 썼으므로 우선 순위가 낮은 큐로 이동한다.
5. ...
6. 가장 우선 순위가 낮은 큐까지 가고 우선 순위를 유지하며 실행된다.

예제 2. Along Came A Short Job

이번에는 두 종류의 작업이 있다고 하자.

• 작업 A : 오랫동안 실행되며 CPU를 많이 사용하는 작업
• 작업 B : 짧게 실행되는 인터랙티브한 작업

작업들이 시스템에 도달했을 때, 스케줄러는 이 작업들의 실행 시간에 대해서는 알지 못한다. 그러므로 일단은 짧은 작업이라 가정하고 높은 우선 순위의 큐에 해당 작업을 집어 넣어보자. 만약 해당 작업이 정말 짧았다면 큐를 얼마 내려가지 않고도 작업을 완료할 수 있고, 사실 너무 길었다면 계속해서 레벨을 내려가면서 작업을 완수할 것이다.

A가 가장 낮은 우선 순위의 큐에서 실행되고 있을 때 작업 B가 들어온다고 하자. 이때 B는 가장 높은 우선 순위 큐에 들어오게되므로 CPU는 B를 실행한다. 만약 B가 가장 낮은 우선 순위의 큐까지 내려가지 않아도 될 만큼 충분히 짧다면 CPU는 B를 계속 완료하고 나서야 A를 재실행하게 된다. 이런 방식으로 작동한다면 MLFQ는 SJF에 근사한다고 할 수도 있다.

예제 3. What About I/O?

프로세스가 allotment를 전부 사용하기 전에 I/O를 사용해야하는 경우, 프로세스는 우선 순위 레벨을 유지한다. 그 이유는 간단하다. 인터랙티브한 작업이 많은 I/O 작업을 동반할 때, 이 작업은 allotment가 끝나지 않았음에도 CPU 제어권을 계속 포기해야한다. 이러한 경우 해당 작업에 페널티를 주는 것은 그다지 바람직한 방식이 아니기 때문에 우선 순위를 유지해줘야 한다.

현재 MLFQ가 가지고 있는 문제

MLFQ에는 여전히 몇 가지의 심각한 결함이 있다.

1. 기아(starvation) 문제
   • 인터랙티브한 작업이 너무 많아 이 작업들을 처리하는 데에 CPU 시간을 모두 써야 하는 경우, 오랫동안 실행되어 우선 순위가 낮아진 작업들은 CPU를 사용할 수 없게 된다
2. 게이밍(gaming) 문제
   • 스케줄러를 속여 정상적으로 해당 프로세스에서 허용되어야 하는 자원 이상을 사용할 수 있게 되는 문제.
   • 다음과 같은 공격에 취약하다.
     - allotment가 전부 사용되기 전에 I/O 작업을 발생시켜 CPU 사용을 포기하게 한다.
     - 작업은 같은 레벨의 큐에 유지되므로 I/O 작업 이후 CPU를 재사용한다.
     - 결국 해당 프로세스는 CPU 독점할 수 있게 된다.
3. 프로그램들이 시간에 지남에 따라 다른 행동을 하는 경우를 커버하지 못한다.
   • CPU를 많이 쓰던 작업이 인터랙티브한 작업으로 바뀔 수 있다.
   • 현재의 접근법에서는 작업의 과거 이력을 보고 미래를 예측하므로, 이렇게 프로그램의 특징이 급변하는 경우는 제대로 처리하지 못할 수 있다

3. Attempt #2: The Priority Boost

우선은 어떻게 기아 문제를 해결할 수 있는지 보자. 간단한 아이디어는 주기적으로 시스템 내 모든 작업들의 우선 순위를 올리는 것인데, 이를 위해서도 많은 방법이 있지만 여기서는 간단히 모두 가장 높은 우선순위의 큐로 올려보도록 한다.

Rule 5: 특정 기간 $S$가 지나면 시스템 내 모든 작업들은 가장 높은 우선 순위의 큐로 올라간다.

이 새 규칙은 두 문제를 해결한다.

1. 프로세스들은 기아 문제에 시달리지 않는다.
   • 프로세스들이 가장 높은 우선 순위의 큐에 들어가게 되므로, 작업들은 RR 방식으로 CPU를 사용해 서비스를 받을 수 있게 된다.
2. CPU를 많이 쓰는 작업이 인터랙티브하게 바뀌었을 때, 우선 순위 격상이 일어난 후 스케줄러는 이를 제대로 인터랙티브하게 처리할 수 있다.

문제는 그 기간 $S$를 얼마로 정하느냐는 것이다. 이건 사실 취향의 문제인데, 이 기간이 너무 길면 오랫 동안 실행되는 작업은 서비스를 받지 못하게 되고. 너무 짧으면 인터랙티브한 작업들이 CPU 작업을 잘 끝내지 못하게 된다. 이 $S$를 찾는 것은 시스템 관리자가 알아서 해결해야 할 문제이지만, 현대에는 기계 학습을 통해 자동으로 찾는 방법들도 개발되고 있다.

4. Attempt #3: Better Accounting

남은 문제는 스케줄러 게이밍 문제다. 여기서 문제가 되는 규칙은 4a와 4b다. I/O 작업을 수행할 때 해당 레벨에서 어느 정도의 allotment를 사용했는지를 잊어버리지 않고, 스케줄러가 이를 계속 추적하게 하자. 프로세스는 allotment를 전부 사용하면 낮은 우선 순위로 격하된다. 이제 프로세스가 allotment를 한 번에 길게 사용했는지, 혹은 짧게 여러 번 나눠서 사용했는지는 문제가 되지 않는다.

Rule 4: 작업이 해당 레벨에서의 allotment를 전부 사용하면 그 우선 순위는 줄어든다.

5. Tuning MLFQ And Other Issues

스케줄러와 관련된 다른 이슈에는 스케줄러를 매개변수화(parameterize)하는 것이다. 예를 들면 다음과 같은 문제들이다.

• 얼마나 많은 큐를 사용할 것인가?
• 큐마다 어느 정도 길이의 시간 단위를 사용할 것인가?
• allotment는 어떻게 설정할 것인가?
• 작업들의 우선 순위는 얼마나 자주 격상시킬 것인가?

이 문제에 대해서는 간단한 해법이 없고, 경험과 지속적인 스케줄러 튜닝을 통해서 균형을 찾을 수 밖에 없다. 예를 들어 MLFQ들은 큐마다 서로 다른 time slice를 사용하게 할 수 있다. 높은 우선 순위의 큐는 보통 인터랙티브한 작업들로 이루어져 있으므로 짧게, 낮은 우선 순위의 큐는 반대로 길게 실행되는 작업들을 포함하기 때문에 길게 둘 수 있다.

스케줄러들은 이외에도 다른 많은 특징들을 가지는데, 어떤 것은 가장 높은 우선 순위의 큐를 OS를 위해서만 사용하고 유저 작업들은 쓰지 못하게 하기도 하고, 어떤 것은 유저 advice로 우선 순위를 직접 지정할 수 있게 할 수도 있다. (ex. nice 커맨드)

6. Summary

MLFQ는 여러 계층의 큐를 사용하며, 작업의 우선순위를 정하기 위해 피드백을 사용한다.

Rules
Rule 1: If Priority(A) > Priority(B), A runs.
Rule 2: If Priority(A) = Priority(B), A & B run in RR fashion.
Rule 3: When a job enters the system, it is placed at the highest priority.
Rule 4: Once a job uses up its time allotment at a given level, its priority is reduced.
Rule 5: After some time period $S$, move all the jobs in the system to the topmost queue.

MLFQ는 작업에 대한 선험적인 지식 대신, MLFQ는 작업의 실행을 관찰하고 그에 따라 우선 순위를 부여한다. 이렇게 함으로써 MLFQ는 짧은 인터랙티브한 작업에도 전반적으로 우수한 성능을 제공할 수 있고, CPU를 많이 쓰는 긴 작업도 공정하게 처리할 수 있게 된다.