스케줄링 알고리즘

스케줄링 알고리즘 (Scheduling Algorithms)

CPU 스케줄링은 준비 큐에 있는 프로세스 중 어떤 프로세스에 CPU 코어를 할당할지 결정하는 문제입니다. 다양한 CPU 스케줄링 알고리즘이 존재하며, 이 섹션에서는 그중 몇 가지를 설명합니다. 대부분의 현대 CPU 아키텍처는 여러 처리 코어를 가지고 있지만, 여기서는 하나의 처리 코어만 사용 가능한 상황을 가정하고 이러한 스케줄링 알고리즘을 설명합니다. 즉, 단일 CPU가 하나의 처리 코어를 가지므로, 시스템은 한 번에 하나의 프로세스만 실행할 수 있습니다. 5.5절에서는 다중 프로세서 시스템에서의 CPU 스케줄링을 논의합니다.

선입선출 (First-Come, First-Served) 스케줄링

가장 간단한 CPU 스케줄링 알고리즘은 선입선출(FCFS) 스케줄링 알고리즘입니다. 이 방식에서는 CPU를 먼저 요청한 프로세스에 CPU가 먼저 할당됩니다. FCFS 정책의 구현은 FIFO 큐(FIFO queue)로 쉽게 관리됩니다. 프로세스가 준비 큐에 진입하면, 해당 PCB(Process Control Block)는 큐의 꼬리에 연결됩니다. CPU가 비어 있으면, 큐의 머리에 있는 프로세스에 할당됩니다. 실행 중인 프로세스는 큐에서 제거됩니다. FCFS 스케줄링 코드는 작성하고 이해하기 쉽습니다.

단점으로는 FCFS 정책 하에서의 평균 대기 시간(average waiting time)이 종종 상당히 길다는 것입니다. 예를 들어, CPU 버스트 시간이 밀리초 단위로 주어진 다음 프로세스 집합이 있다고 가정해 봅시다 (모든 프로세스는 시간 0에 도착합니다):

프로세스

버스트 시간 (ms)

만약 프로세스가 P1, P2, P3 순서로 도착하고 FCFS 순서로 서비스된다면, 다음 간트 차트(Gantt chart)와 같은 결과가 나옵니다:

P1의 대기 시간은 0ms, P2는 24ms, P3는 27ms입니다. 따라서 평균 대기 시간은 (0 + 24 + 27) / 3 = 17ms입니다. 그러나 프로세스가 P2, P3, P1 순서로 도착한다면, 결과는 다음 간트 차트와 같습니다:

평균 대기 시간은 (6 + 0 + 3) / 3 = 3ms로 크게 줄어듭니다. 이처럼 FCFS 정책 하에서의 평균 대기 시간은 일반적으로 최소가 아니며, 프로세스의 CPU 버스트 시간이 크게 다르면 상당히 달라질 수 있습니다.

또한, 동적인 상황에서 FCFS 스케줄링의 성능을 고려해 봅시다. 하나의 CPU 집중 프로세스와 많은 I/O 집중 프로세스가 있다고 가정하면, 다음과 같은 시나리오가 발생할 수 있습니다. CPU 집중 프로세스가 CPU를 점유하면, 다른 모든 프로세스는 I/O를 마치고 준비 큐에 들어가 CPU를 기다리게 됩니다. 프로세스들이 준비 큐에서 기다리는 동안 I/O 장치는 유휴 상태가 됩니다. 결국, CPU 집중 프로세스는 CPU 버스트를 마치고 I/O 장치로 이동합니다. 이 시점에서 짧은 CPU 버스트를 가진 모든 I/O 프로세스들은 빠르게 실행되고 다시 I/O 큐로 돌아갑니다. 이때 CPU는 유휴 상태가 됩니다. CPU 집중 프로세스는 다시 준비 큐로 돌아와 CPU를 할당받습니다. 다시 모든 I/O 프로세스는 CPU 집중 프로세스가 작업을 마칠 때까지 준비 큐에서 기다리게 됩니다. 이를 **호송 효과(convoy effect)**라고 하는데, 모든 다른 프로세스들이 하나의 큰 프로세스가 CPU에서 벗어나기를 기다리는 것입니다. 이 효과는 짧은 프로세스가 먼저 실행되도록 허용했을 때보다 CPU 및 장치 활용률을 낮춥니다.

FCFS 스케줄링 알고리즘은 **비선점형(nonpreemptive)**입니다. CPU가 프로세스에 할당되면, 프로세스는 종료되거나 I/O를 요청하여 CPU를 해제할 때까지 CPU를 유지합니다. 따라서 FCFS 알고리즘은 각 프로세스가 정기적으로 CPU를 할당받는 것이 중요한 대화형 시스템에 특히 문제가 됩니다. 한 프로세스가 CPU를 장시간 점유하도록 허용하는 것은 치명적일 수 있습니다.

최단 작업 우선 (Shortest-Job-First) 스케줄링

CPU 스케줄링에 대한 다른 접근 방식은 최단 작업 우선(SJF) 스케줄링 알고리즘입니다. 이 알고리즘은 각 프로세스에 다음 CPU 버스트의 길이를 연결합니다. CPU를 사용할 수 있게 되면, 다음 CPU 버스트가 가장 짧은 프로세스에 할당됩니다. 두 프로세스의 다음 CPU 버스트 길이가 같으면 FCFS 스케줄링이 동점 처리(tie-breaking)에 사용됩니다. 이 스케줄링 방식의 더 적절한 용어는 "최단 다음 CPU 버스트 알고리즘"일 것입니다. 왜냐하면 스케줄링은 프로세스의 전체 길이가 아니라 다음 CPU 버스트의 길이에 따라 달라지기 때문입니다. 여기서는 "SJF"라는 용어를 사용하는데, 대부분의 사람과 교과서가 이러한 유형의 스케줄링을 지칭할 때 이 용어를 사용하기 때문입니다.

SJF 스케줄링의 예시로, CPU 버스트 시간이 밀리초 단위로 주어진 다음 프로세스 집합을 고려해 봅시다 (모든 프로세스는 시간 0에 도착합니다):

프로세스

버스트 시간 (ms)

SJF 스케줄링을 사용하면, 다음 간트 차트에 따라 프로세스가 스케줄됩니다:

대기 시간은 P1이 3ms, P2가 16ms, P3가 9ms, P4가 0ms입니다. 따라서 평균 대기 시간은 (3 + 16 + 9 + 0) / 4 = 7ms입니다. FCFS 스케줄링 방식을 사용했을 때의 평균 대기 시간은 10.25ms와 비교하면 상당한 감소입니다.

SJF 스케줄링 알고리즘은 주어진 프로세스 집합에 대해 최소 평균 대기 시간을 제공한다는 점에서 최적(optimal)임이 입증되었습니다. 짧은 프로세스를 긴 프로세스보다 먼저 이동시키면 짧은 프로세스의 대기 시간이 감소하는 반면, 긴 프로세스의 대기 시간 증가는 이보다 적습니다. 결과적으로 평균 대기 시간은 감소합니다.

SJF 알고리즘은 최적이지만, 다음 CPU 버스트의 길이를 알 수 있는 방법이 없기 때문에 CPU 스케줄링 수준에서는 구현하기 어렵습니다. 이 문제에 대한 한 가지 접근 방식은 SJF 스케줄링을 근사하는 것입니다. 다음 CPU 버스트의 길이를 알 수는 없지만, 그 값을 예측할 수 있을 수 있습니다. 다음 CPU 버스트는 이전 버스트들과 길이가 비슷할 것으로 예상됩니다. 다음 CPU 버스트 길이에 대한 근사치를 계산하여, 가장 짧은 예측 CPU 버스트를 가진 프로세스를 선택할 수 있습니다.

다음 CPU 버스트는 일반적으로 이전 CPU 버스트의 측정된 길이에 대한 **지수 평균(exponential average)**으로 예측됩니다. t_n을 n번째 CPU 버스트의 길이라 하고, τ_n+1을 다음 CPU 버스트에 대한 예측 값이라고 하면, α (0 ≤ α ≤ 1)에 대해 다음과 같이 정의할 수 있습니다:

τ_n+1 = α * t_n + (1 - α) * τ_n.

t_n 값은 가장 최근 정보를 포함하고, τ_n은 과거 기록을 저장합니다. α 매개변수는 예측에서 최근 기록과 과거 기록의 상대적 가중치를 제어합니다.

SJF 알고리즘은 선점형일 수도 있고 비선점형일 수도 있습니다. 선택은 새로운 프로세스가 준비 큐에 도착하는 동시에 이전 프로세스가 여전히 실행 중일 때 발생합니다. 새로 도착한 프로세스의 다음 CPU 버스트가 현재 실행 중인 프로세스의 남은 시간보다 짧을 수 있습니다. 선점형 SJF 알고리즘은 현재 실행 중인 프로세스를 선점하지만, 비선점형 SJF 알고리즘은 현재 실행 중인 프로세스가 CPU 버스트를 마치도록 허용합니다. 선점형 SJF 스케줄링은 때때로 최단-남은-시간-우선(shortest-remaining-time-first) 스케줄링이라고도 불립니다.

예를 들어, CPU 버스트 시간이 밀리초 단위로 주어진 다음 네 가지 프로세스를 고려해 봅시다:

프로세스

도착 시간 (ms)

버스트 시간 (ms)

프로세스가 표시된 시간에 준비 큐에 도착하고 표시된 버스트 시간이 필요하다면, 결과적인 선점형 SJF 스케줄은 다음 간트 차트에 표시됩니다:

이 예시의 평균 대기 시간은 [(10 - 1) + (1 - 1) + (17 - 2) + (5 - 3)] / 4 = 26 / 4 = 6.5ms입니다. 비선점형 SJF 스케줄링은 평균 대기 시간이 7.75ms가 될 것입니다.

라운드 로빈 (Round-Robin) 스케줄링

라운드 로빈(RR) 스케줄링 알고리즘은 FCFS 스케줄링과 유사하지만, 시스템이 프로세스 간 전환을 가능하게 하기 위해 **선점(preemption)**이 추가됩니다. **시간 할당량(time quantum) 또는 타임 슬라이스(time slice)**라고 불리는 작은 시간 단위가 정의됩니다. 시간 할당량은 일반적으로 10밀리초에서 100밀리초 사이입니다. 준비 큐는 원형 큐(circular queue)로 처리됩니다. CPU 스케줄러는 준비 큐를 순회하며 각 프로세스에 최대 1시간 할당량의 시간 간격 동안 CPU를 할당합니다.

RR 스케줄링을 구현하기 위해, 준비 큐를 다시 프로세스의 FIFO 큐로 취급합니다. 새로운 프로세스는 준비 큐의 꼬리에 추가됩니다. CPU 스케줄러는 준비 큐에서 첫 번째 프로세스를 선택하고, 1시간 할당량 후에 인터럽트를 발생시키도록 타이머를 설정한 다음, 프로세스를 디스패치합니다.

그러면 다음 두 가지 중 하나가 발생합니다. 프로세스의 CPU 버스트가 1시간 할당량보다 짧을 수 있습니다. 이 경우 프로세스는 자발적으로 CPU를 해제합니다. 그런 다음 스케줄러는 준비 큐의 다음 프로세스로 진행합니다. 현재 실행 중인 프로세스의 CPU 버스트가 1시간 할당량보다 길면, 타이머가 작동하여 운영체제에 인터럽트를 발생시킵니다. 컨텍스트 전환이 실행되고, 프로세스는 준비 큐의 꼬리에 놓입니다. 그런 다음 CPU 스케줄러는 준비 큐의 다음 프로세스를 선택합니다.

RR 정책 하에서의 평균 대기 시간은 종종 깁니다. CPU 버스트 시간이 밀리초 단위로 주어진 다음 프로세스 집합이 시간 0에 도착한다고 가정해 봅시다:

프로세스

버스트 시간 (ms)

시간 할당량을 4밀리초로 사용하면, P1은 처음 4밀리초를 얻습니다. 20밀리초가 더 필요하므로, 첫 번째 시간 할당량 후에 선점되고, CPU는 큐의 다음 프로세스인 P2에 주어집니다. P2는 4밀리초가 필요하지 않으므로, 시간 할당량이 만료되기 전에 종료됩니다. 그런 다음 CPU는 다음 프로세스인 P3에 주어집니다. 각 프로세스가 1시간 할당량을 받은 후, CPU는 P1에 추가 시간 할당량을 위해 반환됩니다. 결과적인 RR 스케줄은 다음과 같습니다:

이 스케줄의 평균 대기 시간을 계산해 봅시다. P1은 6밀리초 (10 - 4), P2는 4밀리초, P3는 7밀리초를 기다립니다. 따라서 평균 대기 시간은 17 / 3 = 5.66 밀리초입니다.

RR 스케줄링 알고리즘에서는 어떤 프로세스도 연속해서 1시간 할당량 이상 CPU를 할당받지 않습니다 (실행 가능한 프로세스가 유일한 경우가 아니라면). 프로세스의 CPU 버스트가 1시간 할당량을 초과하면, 해당 프로세스는 선점되어 준비 큐로 다시 들어갑니다. 따라서 RR 스케줄링 알고리즘은 **선점형(preemptive)**입니다.

준비 큐에 n개의 프로세스가 있고 시간 할당량이 q라면, 각 프로세스는 최대 q 시간 단위로 CPU 시간의 1/n을 얻습니다. 각 프로세스는 다음 시간 할당량까지 (n - 1) × q 시간 단위보다 더 오래 기다려서는 안 됩니다. 예를 들어, 5개의 프로세스와 20밀리초의 시간 할당량이 있다면, 각 프로세스는 100밀리초마다 최대 20밀리초를 얻게 됩니다.

RR 알고리즘의 성능은 시간 할당량의 크기에 크게 좌우됩니다. 극단적으로, 시간 할당량이 매우 크다면, RR 정책은 FCFS 정책과 동일합니다. 반대로, 시간 할당량이 매우 작다면 (예: 1밀리초), RR 접근 방식은 많은 컨텍스트 전환(context switch)을 초래할 수 있습니다. 예를 들어, 10시간 단위의 프로세스가 하나만 있다고 가정해 봅시다. 시간 할당량이 12시간 단위라면, 프로세스는 오버헤드 없이 1시간 할당량 이내에 완료됩니다. 그러나 시간 할당량이 6시간 단위라면, 프로세스는 2시간 할당량이 필요하며 컨텍스트 전환이 발생합니다. 시간 할당량이 1시간 단위라면 9번의 컨텍스트 전환이 발생하여 프로세스 실행 속도가 그에 비례하여 느려집니다.

따라서 시간 할당량은 컨텍스트 전환 시간에 비해 커야 합니다. 컨텍스트 전환 시간이 시간 할당량의 약 10%라면, CPU 시간의 약 10%가 컨텍스트 전환에 사용될 것입니다. 실제로 대부분의 현대 시스템은 시간 할당량이 10밀리초에서 100밀리초 사이입니다. 컨텍스트 전환에 필요한 시간은 일반적으로 10마이크로초 미만이므로, 컨텍스트 전환 시간은 시간 할당량의 작은 부분에 불과합니다.

반환 시간(turnaround time)도 시간 할당량의 크기에 따라 달라집니다. 시간 할당량의 크기가 증가함에 따라 프로세스 집합의 평균 반환 시간이 반드시 개선되는 것은 아닙니다. 일반적으로 대부분의 프로세스가 단일 시간 할당량 내에 다음 CPU 버스트를 완료하면 평균 반환 시간을 개선할 수 있습니다. 예를 들어, 각각 10시간 단위의 프로세스 세 개와 1시간 단위의 시간 할당량이 주어지면, 평균 반환 시간은 29입니다. 그러나 시간 할당량이 10이라면, 평균 반환 시간은 20으로 떨어집니다. 컨텍스트 전환 시간이 추가되면, 더 많은 컨텍스트 전환이 필요하므로 더 작은 시간 할당량에 대해 평균 반환 시간이 더욱 증가합니다.

시간 할당량은 컨텍스트 전환 시간에 비해 커야 하지만, 너무 커서도 안 됩니다. 앞서 지적했듯이, 시간 할당량이 너무 크면 RR 스케줄링은 FCFS 정책으로 퇴화합니다. 일반적인 규칙은 CPU 버스트의 80%가 시간 할당량보다 짧아야 한다는 것입니다.

우선순위 스케줄링 (Priority Scheduling)

SJF 알고리즘은 일반적인 **우선순위 스케줄링 알고리즘(priority-scheduling algorithm)**의 특수한 경우입니다. 각 프로세스에는 우선순위가 연결되어 있으며, 가장 높은 우선순위를 가진 프로세스에 CPU가 할당됩니다. 우선순위가 같은 프로세스들은 FCFS 순서로 스케줄됩니다. SJF 알고리즘은 단순히 우선순위(p)가 (예측된) 다음 CPU 버스트의 역수인 우선순위 알고리즘입니다. CPU 버스트가 길수록 우선순위는 낮아지고, 짧을수록 우선순위는 높아집니다.

여기서는 높은 우선순위와 낮은 우선순위라는 용어로 스케줄링을 논의합니다. 우선순위는 일반적으로 0부터 7 또는 0부터 4,095와 같이 고정된 숫자 범위로 표시됩니다. 그러나 0이 가장 높은 우선순위인지 가장 낮은 우선순위인지에 대한 일반적인 합의는 없습니다. 일부 시스템은 낮은 숫자를 낮은 우선순위로 사용하고, 다른 시스템은 낮은 숫자를 높은 우선순위로 사용합니다. 이러한 차이는 혼란을 야기할 수 있습니다. 이 책에서는 낮은 숫자가 높은 우선순위를 나타낸다고 가정합니다.

예를 들어, CPU 버스트 시간이 밀리초 단위로 주어진 다음 프로세스 집합을 고려해 봅시다 (모든 프로세스는 시간 0에 P1, P2, ..., P5 순서로 도착합니다):

프로세스

버스트 시간 (ms)

우선순위

우선순위 스케줄링을 사용하면, 다음 간트 차트에 따라 프로세스가 스케줄됩니다:

평균 대기 시간은 8.2 밀리초입니다.

우선순위는 내부적으로 정의될 수도 있고 외부적으로 정의될 수도 있습니다. 내부적으로 정의된 우선순위는 하나 이상의 측정 가능한 양을 사용하여 프로세스의 우선순위를 계산합니다. 예를 들어, 시간 제한, 메모리 요구 사항, 열린 파일 수, 평균 I/O 버스트 대 평균 CPU 버스트 비율 등이 우선순위 계산에 사용되었습니다. 외부 우선순위는 운영체제 외부의 기준(예: 프로세스의 중요성, 컴퓨터 사용에 지불되는 자금 유형 및 금액, 작업 후원 부서 및 기타 정치적 요인)에 의해 설정됩니다.

우선순위 스케줄링은 선점형일 수도 있고 비선점형일 수도 있습니다. 새로운 프로세스가 준비 큐에 도착했을 때, 현재 실행 중인 프로세스의 우선순위와 비교됩니다. 새로 도착한 프로세스의 우선순위가 현재 실행 중인 프로세스의 우선순위보다 높으면 **선점형 우선순위 스케줄링 알고리즘(preemptive priority scheduling algorithm)**이 CPU를 선점합니다. 비선점형 우선순위 스케줄링 알고리즘은 단순히 새로운 프로세스를 준비 큐의 머리에 놓을 것입니다.

우선순위 스케줄링 알고리즘의 주요 문제는 **무한 블로킹(indefinite blocking) 또는 기아(starvation)**입니다. 실행 준비 상태이지만 CPU를 기다리는 프로세스는 블로킹된 것으로 간주될 수 있습니다. 우선순위 스케줄링 알고리즘은 일부 낮은 우선순위 프로세스가 무한정 대기하도록 내버려 둘 수 있습니다. 높은 부하의 컴퓨터 시스템에서, 꾸준히 들어오는 높은 우선순위 프로세스들은 낮은 우선순위 프로세스가 CPU를 얻는 것을 영원히 막을 수 있습니다. 일반적으로 두 가지 중 하나가 발생합니다. 프로세스가 결국 실행되거나 (새벽 2시 일요일, 시스템 부하가 마침내 낮아졌을 때), 컴퓨터 시스템이 결국 충돌하여 완료되지 않은 낮은 우선순위 프로세스를 모두 잃게 됩니다.

낮은 우선순위 프로세스의 무한 블로킹 문제에 대한 해결책은 **노화(aging)**입니다. 노화는 시스템에서 오랫동안 대기하는 프로세스의 우선순위를 점진적으로 증가시키는 것을 포함합니다. 예를 들어, 우선순위가 127(낮음)에서 0(높음)까지라면, 주기적으로(예: 매초) 대기 중인 프로세스의 우선순위를 1씩 증가시킬 수 있습니다. 결국, 초기 우선순위가 127인 프로세스조차도 시스템에서 가장 높은 우선순위를 가지게 되어 실행될 것입니다.

다른 옵션은 라운드 로빈과 우선순위 스케줄링을 결합하여, 시스템이 가장 높은 우선순위 프로세스를 실행하고 동일한 우선순위를 가진 프로세스를 라운드 로빈 스케줄링을 사용하여 실행하는 것입니다. 다음 프로세스 집합을 이용하여 예를 들어 봅시다 (버스트 시간은 밀리초 단위):

프로세스

버스트 시간 (ms)

우선순위

동일 우선순위 프로세스에 대해 라운드 로빈을 사용하는 우선순위 스케줄링을 사용하고 시간 할당량을 2밀리초로 사용하면, 다음 간트 차트에 따라 프로세스가 스케줄됩니다:

이 예시에서 P4는 가장 높은 우선순위를 가지므로, 완료될 때까지 실행됩니다. P2와 P3는 그 다음으로 높은 우선순위를 가지며, 라운드 로빈 방식으로 실행됩니다. P2가 시간 16에 완료되면 P3가 가장 높은 우선순위 프로세스가 되므로, 완료될 때까지 실행됩니다. 이제 P1과 P5만 남았고, 동일한 우선순위를 가지므로 완료될 때까지 라운드 로빈 순서로 실행됩니다.

다단계 큐 (Multilevel Queue) 스케줄링

우선순위 및 라운드 로빈 스케줄링 모두에서 모든 프로세스는 단일 큐에 배치될 수 있으며, 스케줄러는 가장 높은 우선순위 프로세스를 선택하여 실행합니다. 큐가 관리되는 방식에 따라 가장 높은 우선순위 프로세스를 결정하기 위해 O(n) 검색이 필요할 수 있습니다. 실제로 각 고유 우선순위에 대해 별도의 큐를 갖는 것이 더 쉬운 경우가 많으며, 우선순위 스케줄링은 단순히 가장 높은 우선순위 큐에 있는 프로세스를 스케줄합니다. 이 접근 방식을 다단계 큐(multilevel queue) 스케줄링이라고 하며, 우선순위 스케줄링이 라운드 로빈과 결합될 때도 잘 작동합니다. 즉, 가장 높은 우선순위 큐에 여러 프로세스가 있는 경우, 라운드 로빈 순서로 실행됩니다. 이 접근 방식의 가장 일반적인 형태에서는 각 프로세스에 정적으로 우선순위가 할당되며, 프로세스는 실행 시간 동안 동일한 큐에 남아 있습니다.

다단계 큐 스케줄링 알고리즘은 프로세스 유형에 따라 프로세스를 여러 별도의 큐로 분할하는 데 사용될 수도 있습니다. 예를 들어, 전면(대화형) 프로세스와 후면(배치) 프로세스 간에 일반적인 구분이 이루어집니다. 이 두 가지 유형의 프로세스는 응답 시간 요구 사항이 다르므로 다른 스케줄링 요구가 있을 수 있습니다. 또한 전면 프로세스는 후면 프로세스보다 우선순위가 높을 수 있습니다(외부적으로 정의됨). 전면 및 후면 프로세스에 대해 별도의 큐를 사용할 수 있으며, 각 큐에는 자체 스케줄링 알고리즘이 있을 수 있습니다. 예를 들어, 전면 큐는 RR 알고리즘에 의해 스케줄될 수 있고, 후면 큐는 FCFS 알고리즘에 의해 스케줄될 수 있습니다.

또한, 큐 간에 스케줄링이 이루어져야 하며, 이는 일반적으로 고정 우선순위 선점형 스케줄링으로 구현됩니다. 예를 들어, 실시간 큐는 대화형 큐에 대해 절대 우선순위를 가질 수 있습니다. 배치 큐의 프로세스는 예를 들어, 실시간 프로세스, 시스템 프로세스, 대화형 프로세스를 위한 큐가 모두 비어 있지 않으면 실행될 수 없습니다. 배치 프로세스가 실행 중인 동안 대화형 프로세스가 준비 큐에 진입하면 배치 프로세스는 선점됩니다.

또 다른 가능성은 큐 간에 **시간 분할(time-slice)**을 하는 것입니다. 여기서 각 큐는 CPU 시간의 특정 부분을 얻으며, 이를 자체 프로세스 간에 스케줄할 수 있습니다. 예를 들어, 전면-후면 큐 예시에서 전면 큐에는 RR 스케줄링을 위해 CPU 시간의 80%가 주어지고, 후면 큐에는 FCFS 기준으로 프로세스에 20%의 CPU가 주어집니다.

다단계 피드백 큐 (Multilevel Feedback Queue) 스케줄링

일반적으로 다단계 큐 스케줄링 알고리즘이 사용될 때, 프로세스는 시스템에 진입할 때 큐에 영구적으로 할당됩니다. 예를 들어, 전면 및 후면 프로세스에 대해 별도의 큐가 있는 경우, 프로세스는 전면 또는 후면 특성을 변경하지 않으므로 한 큐에서 다른 큐로 이동하지 않습니다. 이 설정은 스케줄링 오버헤드가 낮다는 장점이 있지만 유연성이 떨어집니다.

반대로 다단계 피드백 큐(multilevel feedback queue) 스케줄링 알고리즘은 프로세스가 큐 사이를 이동할 수 있도록 허용합니다. 아이디어는 CPU 버스트의 특성에 따라 프로세스를 분리하는 것입니다. 프로세스가 CPU 시간을 너무 많이 사용하면 우선순위가 낮은 큐로 이동됩니다. 이 방식은 짧은 CPU 버스트를 특징으로 하는 I/O 중심 및 대화형 프로세스를 높은 우선순위 큐에 유지합니다. 또한, 우선순위가 낮은 큐에서 너무 오래 기다리는 프로세스는 우선순위가 높은 큐로 이동될 수 있습니다. 이러한 형태의 **노화(aging)**는 **기아(starvation)**를 방지합니다.

예를 들어, 0에서 2까지 번호가 매겨진 세 개의 큐가 있는 다단계 피드백 큐 스케줄러를 고려해 봅시다. 스케줄러는 먼저 큐 0의 모든 프로세스를 실행합니다. 큐 0이 비어 있을 때만 큐 1의 프로세스를 실행합니다. 마찬가지로, 큐 2의 프로세스는 큐 0과 1이 비어 있을 때만 실행됩니다. 큐 1에 도착하는 프로세스는 큐 2의 프로세스를 선점합니다. 큐 1의 프로세스는 다시 큐 0에 도착하는 프로세스에 의해 선점됩니다.

진입하는 프로세스는 큐 0에 배치됩니다. 큐 0의 프로세스에는 8밀리초의 시간 할당량이 주어집니다. 이 시간 내에 완료되지 않으면 큐 1의 꼬리로 이동합니다. 큐 0이 비어 있으면, 큐 1의 머리에 있는 프로세스에 16밀리초의 할당량이 주어집니다. 완료되지 않으면 선점되어 큐 2에 배치됩니다. 큐 2의 프로세스는 FCFS 기반으로 실행되지만, 큐 0과 1이 비어 있을 때만 실행됩니다. 기아를 방지하기 위해, 우선순위가 낮은 큐에서 너무 오래 기다리는 프로세스는 점진적으로 우선순위가 높은 큐로 이동될 수 있습니다.

이 스케줄링 알고리즘은 8밀리초 이하의 CPU 버스트를 가진 모든 프로세스에 가장 높은 우선순위를 부여합니다. 이러한 프로세스는 빠르게 CPU를 얻고, CPU 버스트를 완료하며, 다음 I/O 버스트로 이동합니다. 8밀리초보다 길지만 24밀리초 미만이 필요한 프로세스도 빠르게 서비스되지만, 짧은 프로세스보다 우선순위가 낮습니다. 긴 프로세스는 자동으로 큐 2로 이동하여 큐 0과 1에서 남은 CPU 주기만큼 FCFS 순서로 서비스됩니다.

일반적으로 다단계 피드백 큐 스케줄러는 다음 매개변수에 의해 정의됩니다:

큐의 수
각 큐에 대한 스케줄링 알고리즘
프로세스를 높은 우선순위 큐로 업그레이드할 시기를 결정하는 데 사용되는 방법
프로세스를 낮은 우선순위 큐로 강등할 시기를 결정하는 데 사용되는 방법
프로세스가 서비스를 필요로 할 때 어떤 큐에 진입할지 결정하는 데 사용되는 방법

다단계 피드백 큐 스케줄러의 정의는 이를 가장 일반적인 CPU 스케줄링 알고리즘으로 만듭니다. 설계 중인 특정 시스템에 맞게 구성할 수 있습니다. 불행히도, 모든 매개변수 값을 선택하는 수단이 필요하므로 가장 복잡한 알고리즘이기도 합니다.

Previous스케줄링 기준 NextDNS 실전 교과서

Last updated 1 day ago