이 글은 건국대학교 2024년 1학기 운영체제 수업과 『Operating Systems: Three Easy Pieces』 를 참고하여 작성되었습니다.
『Operating Systems: Three Easy Pieces』
8장. Multi-Level Feedback Queue
지난 게시글에서 다룬 CPU 스케줄링의 성능 지표로 Turnaround time과 Response time을 다뤘습니다. 여기서 Turnaround time은 process가 도착한 시점부터 처리가 완료되어 종료될 때까지의 시간을 의미하며, Response time은 프로세스가 도착한 후 최초로 CPU를 할당받아 실행될 때까지의 시간을 말합니다.
- 𝑇 𝑡𝑢𝑟𝑛𝑎𝑟𝑜𝑢𝑛𝑑 = 𝑇 𝑐𝑜𝑚𝑝𝑙𝑒𝑡𝑖𝑜𝑛− 𝑇 𝑎𝑟𝑟𝑖𝑣𝑎𝑙
- 𝑇 𝑟𝑒𝑠𝑝𝑜𝑛𝑠𝑒 = 𝑇 𝑓𝑖𝑟𝑠𝑡𝑟𝑢𝑛− 𝑇 𝑎𝑟𝑟𝑖𝑣𝑎𝑙
CPU 스케줄링 알고리즘에는 다양한 종류가 있으며, 각기 다른 성능 지표를 최소화하는 데 초점을 맞춥니다. SJF(Short Job First), STCF(Shortest Time to Completion First) 는 Turnaround time을 최소화하는 반면, RR(Round Robin) 은 Response time 최소화에 유리합니다.
이러한 알고리즘들은 Turnaround time과 Response time을 동시에 최소화하는 데 한계가 있습니다. 이번 글에서는 모든 프로세스의 실행시간을 사전에 알 수 없는 상황에서 두 성능 지표를 모두 최소화할 수 있는 방법에 대해서 알아보겠습니다.
Multi-Level Feedback Queue (MLFQ)
MLFQ 알고리즘에선 각 CPU 코어 내에 서로 다른 우선순위를 가진 큐들이 여러개 존재합니다. 우선순위가 높은 프로세스는 우선순위가 높은 큐에 들어가고, 낮은 프로세스는 낮은 큐에 들어갑니다. 하나의 프로세스는 하나의 큐에만 들어갈 수 있습니다.
MLFQ : Basic rules
rule 1. 우선순위가 높은 프로세스를 먼저 실행한다.
rule 2. 우선순위가 같은 프로세스가 여러개 있으면, RR (Round Robin) 방식으로 여러 개를 동시에 번갈아가며 실행한다.
위의 예시 상황을 통해 MLFQ 작동 방식을 살펴보겠습니다. 우선순위가 가장 높은 큐에 있는 프로세스 A, B가 RR로 실행되고, 둘 다 종료되면 프로세스 C가 실행됩니다. C가 종료된 후에 D가 실행됩니다.
하지만, 2개의 rule로는 Turnaround time과 Response time 모두 최소화할 수 없다는 문제점이 있습니다. 우선순위를 어떠한 기준으로 부여하는지를 고려하고 이를 수정하며 두 성능 지표를 모두 개선해봅시다.
우선순위 결정 방법
job들의 우선순위는 OS가 프로세스의 CPU 사용량에 따라서 결정합니다.
CPU를 많이 사용하는 프로세스 (CPU-bound)는 우선순위가 낮아지고, CPU를 계속해서 포기하는 프로세스 (I/O-bound)는 우선순위가 높아집니다. 응용 프로세스는 자신의 우선순위를 변경할 수 없습니다.
priority adjustment algorithm 초안
rule 3. job 처음 도착했을 때, 모든 프로세스에게 가장 높은 우선순위를 부여한다.
-> 이를 통해 모든 job들의 response time을 최소화할 수 있다.
rule 4-a. 만약 job이 주어진 time slice를 모두 사용하면, job의 우선순위를 한 단계 낮춘다.
rule 4-b. 만약 job이 time slice를 모두 사용하기 전에 blocked 상태가 된다면, job의 우선순위를 유지한다. (여기서 말한 time slice는 각 프로세스의 CPU 사용량을 파악하기 위한 지표로, RR의 time slice와는 별개의 개념입니다.)
위 방식에는 3가지 문제점이 있습니다.
1. starvation
2. gaming the scheduler
3. changing behavior
문제 1. starvation → 해결 : priority boost
🚨 문제 상황
파란색, 초록색 프로세스 : I/O bound 한 프로세스 → 우선순위가 높다.
노란색 프로세스 : CPU bound 한 프로세스 → 우선순위가 낮다.
→ 우선순위가 낮은 프로세스가 starvation을 겪고 있는 상황
현재에는 우선순위가 낮아지는 방법만 존재하기 때문에, I/O-bound job의 개수가 많아지면 우선순위가 낮은 job들은 CPU를 오랜 시간동안 할당받지 못하는 문제가 발생할 수 있습니다. (starvation) 이를 해결하기 위한 방법이 바로 'priority boost' 입니다. priority boost는 모든 job들의 우선순위를 주기적으로 높이는 것입니다.
rule 5. 일정 시간 S마다 시스템 내에 있는 모든 job들을 topmost queue로 옮긴다.
이 규칙을 추가함으로써 1.starvation, 3.changing behavior 문제를 해결할 수 있습니다.
위 예시에서는 priority boost가 50ms 마다 한 번씩 발생한다고 설정되어 있습니다. 이 설정에 따라 노란색 프로세스는 50ms 마다 우선순위가 높아지므로 실행 기회를 얻게 됩니다. 이러한 메커니즘을 통해 특정 프로세스가 지나치게 오랜 시간동안 실행되지 못하는 문제, 즉 'starvation' 현상을 방지할 수 있습니다.
문제 2. gaming the scheduler
🚨 문제 상황
규칙 4-a, 4-b 에 따르면, job들은 time slice가 끝나기 직전마다 짧은 I/O 작업을 요청함으로써 스케줄러를 속이고 우선순위를 지속적으로 높게 유지할 수 있습니다.
이러한 편법을 방지하기 위해, 프로세스가 짧은 I/O 작업으로 인해 blocked 상태가 되었다고 해도 time slice는 초기화되지 않고 계속 누적됩니다. time slice의 누적 값이 한도를 다 채우면 그 때 초기화(refresh)가 일어납니다. OS는 이렇게 누적된 CPU 사용 시간을 기반으로 프로세스의 우선순위를 조정합니다. 이러한 방식을 'better accounting' 이라고 합니다. 이는 프로세스가 CPU를 얼마나 자주 포기하는지와 상관없이 누적 시간으로만 우선순위를 조정합니다.
rule 4. 프로세스가 time slice를 모두 사용하기 전에 blocked 상태가 되더라도, time slice는 초기화되지 않는다. CPU 사용 시간의 누적 값을 통해 우선순위를 조정한다.
문제 상황에서 파란색 프로세스의 우선순위가 Q2로 계속 유지됐던 것과 달리, rule 4가 적용된 위 그림에서는 파란색 프로세스가 blocked 된 후에도 time slice가 계속 누적되어 time slice를 모두 사용한 후, 파란색 프로세스의 우선순위가 조정되는 것을 볼 수 있습니다.
문제 3. changing behavior
하나의 프로세스(job)는 항상 CPU-bound 혹은 I/O-bound 상태만을 유지하지 않고, 실행 도중 상태가 바뀔 수 있습니다. 이러한 변화를 어떻게 우선순위에 적용할 수 있을까요?
priority boost 를 통해 이 문제를 해결할 수 있습니다. 프로세스가 CPU-bound 상태일 때는 priority boost가 된 후 우선순위가 빠르게 하락하며, I/O-bound 상태일 때는 priority boost가 된 후 우선순위가 천천히 하락하거나 유지됩니다. 이를 통해 프로세스의 현재 상태에 따라 우선순위가 조정됩니다.
이 때, priority boost의 주기 설정이 중요합니다. 너무 긴 주기는 프로세스가 과도하게 대기하는 문제가 야기하고, 너무 짧은 주기는 비효율적일 뿐만 아니라 우선순위 설정의 의미를 퇴색시킬 수 있습니다. 따라서 priority boost가 적절한 주기마다 이루어지도록 설정하는 것이 중요합니다.
priority adjustment algorithm (최종)
rule 1. 우선순위가 높은 프로세스를 먼저 실행한다.
rule 2. 우선순위가 같은 프로세스가 여러개 있으면, RR (Round Robin) 방식으로 여러 개를 동시에 번갈아가며 실행한다.
rule 3. job 처음 도착했을 때, 모든 프로세스에게 가장 높은 우선순위를 부여한다.
rule 4. 프로세스가 time slice를 모두 사용하기 전에 blocked 상태가 되더라도, time slice는 초기화되지 않는다. CPU 사용 시간의 누적 값을 통해 우선순위를 조정한다.
rule 5. 일정 시간 S마다 시스템 내에 있는 모든 job들을 topmost queue로 옮긴다.
Q. priority boost의 적절한 주기는 어떻게 계산할 수 있을까?
A. 과거 solaris라는 OS에서는 priority boost 주기를 1s로 하드코딩하였다. 그 때의 CPU 속도를 고려하면 적절한 시간일 수 있으나 현재는 아닐 수 있다.
Q. 추가로, 우선순위를 조정하는 기준이 되는 time slice의 길이를 어떻게 설정해야할까?
A. 과거 solaris라는 OS에서는 높은 우선순위를 가지는 큐에서는 time slice를 짧게 설정하고, 낮은 우선순위를 가지는 큐에서는 time slice를 길게 설정했다.
