고급 스케줄링 알고리즘

기본 알고리즘들은 개념을 이해하기에 좋지만, 실제 OS는 더 정교한 스케줄링이 필요합니다.

데스크톱에서는 워드프로세서, 음악 플레이어, 컴파일러가 동시에 돌고, 서버에서는 웹 요청, 배치 작업, 시스템 모니터링이 공존합니다.

다양한 성격의 프로세스가 공존하는 환경에서, 하나의 알고리즘만으로는 모든 요구를 충족할 수 없습니다.

우선순위 스케줄링

각 프로세스에 우선순위(Priority)를 부여하고, 우선순위가 높은 프로세스를 먼저 실행합니다.

대부분의 실제 OS 스케줄러의 기반이 되는 알고리즘입니다.

우선순위의 표현은 시스템마다 다릅니다.

Linux도 값의 종류에 따라 다릅니다. 일반 작업의 nice 값은 작을수록 CPU 가중치가 크지만, 실시간 sched_priority는 클수록 우선합니다.

중요한 것은 어떤 프로세스가 먼저 CPU를 받느냐입니다.

먼저 비교 대상을 실행 가능한 Ready 작업으로 한정합니다. 디스크 응답을 기다려 Blocked인 높은 우선순위 작업은 그동안 CPU를 받을 후보가 아닙니다. 예를 들어 A가 I/O를 기다리고 B만 Ready라면 B가 실행될 수 있습니다. 우선순위는 기다리는 I/O 자체를 완료시키는 장치가 아닙니다. nice 값의 CPU 가중치와 실시간 클래스의 엄격한 우선순위도 같은 숫자표로 비교하지 않습니다.

우선순위는 두 가지 방식으로 결정됩니다.

내부적 결정: OS가 프로세스의 특성을 분석하여 자동으로 설정합니다.

교과서적 정책에서는 예상 버스트나 대기 이력 등을 고려할 수 있습니다. 모든 OS가 메모리 사용량·열린 파일 수로 우선순위를 정하거나 I/O 바운드 작업을 항상 우대하는 것은 아닙니다.

외부적 결정: 사용자나 관리자가 명시적으로 설정합니다.

Linux의 nice 값이 대표적입니다.

프로세스의 중요도에 대한 정책적 판단입니다.

우선순위 스케줄링은 선점형과 비선점형 모두 가능합니다.

선점형의 기본 모델에서는 더 높은 우선순위 작업이 준비되면 현재 작업을 선점합니다. 실제 전환에는 커널의 선점 가능 지점과 지연이 영향을 줍니다.

비선점형에서는 현재 프로세스가 자발적으로 CPU를 놓을 때까지 기다립니다.

기아와 에이징

우선순위 스케줄링의 가장 큰 문제는 기아(Starvation)입니다.

높은 우선순위의 프로세스가 계속 도착하면, 낮은 우선순위의 프로세스는 Ready Queue에서 무한히 대기합니다.

이론적으로 영원히 실행되지 못할 수 있습니다.

에이징(Aging)은 오래 기다린 작업의 우선순위를 높여 기아 문제를 완화하는 방법입니다.

프로세스가 Ready Queue에서 대기한 시간에 비례하여 우선순위를 점진적으로 높입니다.

예를 들어 127을 최저로 쓰는 가상 정책에서 15분마다 우선순위 수치를 1씩 줄일 수 있습니다. 최고 단계에 도달한 작업도 공정하게 선택하는 규칙과 실행 기회가 있어야 기아 방지를 설명할 수 있습니다. 이 수치는 Linux 설정값이 아닙니다.

멀티레벨 큐

멀티레벨 큐(Multilevel Queue)는 Ready Queue를 여러 개의 큐로 분리하고, 각 큐에 다른 스케줄링 알고리즘을 적용합니다.

프로세스의 성격에 따라 적합한 큐에 영구적으로 배치합니다.

이 예는 위에서 아래로 시스템 → 대화형 → 배치 순서의 우선순위를 둡니다.

큐 간 스케줄링은 두 가지 방식이 있습니다.

고정 우선순위: 상위 큐가 비어야만 하위 큐의 프로세스가 실행됩니다.

구현이 단순하지만, 하위 큐의 기아 가능성이 있습니다.

시간 할당: 각 큐에 CPU 시간의 비율을 할당합니다.

예: 시스템 큐 10%, 대화형 큐 70%, 배치 큐 20%.

이 비율을 강제하는 모델에서는 실행 가능한 배치 큐에 20%의 몫을 배정합니다. 큐의 몫과 그 안의 개별 작업에 대한 대기 상한은 별개입니다.

멀티레벨 큐의 한계는 프로세스가 큐 사이를 이동할 수 없다는 것입니다.

프로세스의 행동이 바뀌어도 (예: 처음에는 I/O 바운드였다가 나중에 CPU 바운드로 변하는 경우) 원래 배치된 큐에 머물러야 합니다.

멀티레벨 피드백 큐

멀티레벨 피드백 큐(Multilevel Feedback Queue, MLFQ)는 프로세스가 큐 사이를 이동할 수 있는 확장 모델입니다.

가장 유연하고, 현대 스케줄러의 이론적 기반이 되는 구조입니다.

핵심 아이디어: 프로세스의 과거 행동을 관찰하여 미래를 예측합니다.

다음 버스트 길이를 직접 알지 못해도 짧은 작업을 우대하려는 휴리스틱입니다. SJF의 최적성이나 데드라인을 보장하는 것은 아닙니다.

동작 원리

다음과 같이 3개의 큐가 있다고 합시다.

1. 새 프로세스는 Q0(최고 우선순위, 가장 짧은 퀀텀)에 배치됩니다.
2. 8ms 안에 완료되면 끝입니다 → 짧은 작업은 높은 우선순위에서 빠르게 처리됩니다.
3. 8ms를 다 써도 완료되지 않으면 Q1으로 강등됩니다 → CPU를 많이 쓰는 프로세스로 판단.
4. Q1에서 16ms를 다 써도 완료되지 않으면 Q2(FCFS)로 강등됩니다.
5. I/O를 요청해 CPU를 빨리 반납한 프로세스는 높은 큐에 유지되거나 구현에 따라 승격될 수 있습니다 → I/O 바운드(대화형)로 판단.

이렇게 하면 SJF처럼 동작하되, 실행 시간을 미리 알 필요가 없습니다.

한 번의 실행 구간과 한 큐의 총 할당량을 구분하기

퀀텀은 같은 우선순위 작업들이 번갈아 실행할 때 한 번에 쓰는 시간이고, 할당량은 강등 전까지 그 작업이 해당 큐에서 누적해서 쓸 수 있는 CPU 시간입니다. 이 예는 Q0의 두 값을 8ms로 맞춰 단순화했지만 일반적인 정책에서는 다를 수 있습니다. I/O 대기나 다른 작업이 실행한 시간은 이 작업의 CPU 사용량에 더하지 않습니다.

Q2의 FCFS는 같은 Q2 안의 순서를 뜻합니다. 큐 사이에는 높은 Ready 큐를 우선하고 선점한다고 정한 이 모델에서, Q2 작업이 실행 중이어도 새 Q0 작업이 Ready가 되면 먼저 실행할 수 있습니다. ‘Q2가 FCFS이므로 상위 큐까지 모두 기다린다’는 해석은 큐 내부 정책과 큐 사이 정책을 섞은 것입니다.

짧은 작업은 Q0에서 빠르게 끝나고, CPU 바운드 작업은 자연스럽게 Q2로 내려가서 낮은 우선순위를 받습니다.

I/O 바운드(대화형) 프로세스는 잠깐 CPU를 쓰고 I/O로 가므로 높은 큐에 머무를 가능성이 커져 응답성이 좋아집니다.

MLFQ의 문제와 해결

교묘한 프로세스가 의도적으로 타임 퀀텀이 끝나기 직전에 불필요한 I/O를 요청하면, 높은 우선순위를 유지하려고 스케줄러 정책을 악용할 수 있습니다.

이것을 게이밍(Gaming)이라고 합니다.

해결책은 회계(Accounting)입니다.

프로세스가 각 큐에서 사용한 총 CPU 시간을 추적합니다.

총 사용 시간이 해당 큐의 할당량에 도달하면, 중간에 I/O를 했더라도 강등됩니다.

독립 확인: 이 MLFQ에서 Q0의 누적 CPU 할당량은 8ms입니다. 작업이 Q0에서 3ms 실행한 뒤 I/O로 양보하고, 복귀 후 다시 4ms 사용했다면 어느 큐에 있으며 Q0에서 얼마나 더 쓸 수 있을까요? 부스트·다른 작업·추가 비용이 없는 조건에서 다음 1ms도 사용한다고 가정해 보세요.

또 다른 문제는 장기 실행 프로세스의 기아입니다.

CPU 바운드 프로세스가 Q2에 계속 머물면 실행 기회가 매우 적어집니다.

주기적 부스트(Priority Boost)로 해결합니다.

일정 주기(예: 1초)마다 모든 프로세스를 Q0으로 올립니다.

그러면 다시 행동을 관찰하여 적절한 큐로 재배치됩니다.

부스트만으로 모든 작업의 대기 시간이 1초 이하가 되는 것은 아닙니다. 부스트 뒤에도 같은 큐의 선택 규칙과 앞선 작업 수에 따라 기다립니다. 유한한 Ready 작업을 공정한 RR로 순환시키는 등의 조건이 있어야 실행 기회를 설명할 수 있으며, 이는 실시간 데드라인 보장과 별개입니다. 부스트 시 누적 회계를 어떻게 초기화하는지도 구현 정책에 포함해 정합니다. OSTEP의 MLFQ 설명은 회계와 부스트가 해결하는 문제를 구분합니다.

고급 스케줄러는 공정성, 반응성, 데드라인 중 무엇을 더 강하게 보장할지에 따라 구조가 갈립니다.

실시간 스케줄링

실시간 시스템(Real-Time System)은 "빠르게"가 아니라 "정해진 시간 안에" 작업을 완료하는 것이 핵심입니다.

데드라인을 지키느냐 못 지키느냐가 시스템의 정확성을 결정합니다.

태스크와 이번 job의 마감 시각

주기 태스크는 같은 일을 반복하는 규칙이고, job은 그 규칙에 따라 한 번 도착한 실행 단위입니다. 실행 시간 상한을 C, 주기를 T, 상대 데드라인을 D라고 쓰면, 시각 r에 도착한 job의 절대 데드라인은 r+D입니다. C는 평균 실행 시간이 아니라 보장 판단에 사용할 최악 실행 시간 상한입니다. 아래 단일 CPU 계산은 각 job이 그 상한까지 CPU를 사용해도 되는지 판단하며, I/O·잠금 대기나 문맥 전환 비용을 추가하려면 모델도 함께 바뀝니다. Linux의 데드라인 이론 정리가 이 단위를 설명합니다.

경성 실시간(Hard Real-Time): 데드라인을 반드시 지켜야 합니다.

놓치면 시스템 실패 또는 인명 피해입니다.

• 항공기 비행 제어 시스템: 센서와 제어 루프가 정해진 시간 안에 반복 실행되어야 합니다.
• 자동차 ABS: 브레이크 제어 신호를 매우 짧은 시간 안에 처리해야 합니다.
• 의료 장비: 환자 상태 감시와 제어 동작이 정해진 지연 한계를 넘지 않아야 합니다.

연성 실시간(Soft Real-Time): 데드라인을 놓쳐도 성능 저하로 끝납니다.

시스템이 멈추지는 않습니다.

• 동영상 스트리밍: 30fps로 재생할 때, 한 프레임(33ms)을 놓치면 화면이 잠깐 끊기지만 계속 재생됩니다.
• VoIP: 패킷이 지연되면 음질이 나빠지지만 통화는 가능합니다.

Rate Monotonic (RM)

Rate Monotonic은 주기가 짧은 작업에 높은 우선순위를 부여하는 정적 우선순위 알고리즘입니다.

상대 데드라인이 주기와 같다는 가정에서 짧은 주기에 높은 고정 우선순위를 줍니다. 현재 job의 절대 데드라인 순서와 항상 일치하지는 않습니다.

예시: Task A(주기 20ms, 실행 시간 5ms)와 Task B(주기 50ms, 실행 시간 15ms)가 있으면, A의 주기가 더 짧으므로 A가 높은 우선순위를 받습니다.

RM의 대표적인 충분 조건: 단일 CPU·선점 가능·독립적인 주기 태스크·데드라인=주기·실행 시간 상한을 알고 문맥 전환 및 블로킹 비용을 무시하는 모델에서, CPU 이용률이 $n(2^{1/n} - 1)$ 이하이면 스케줄 가능하다고 보장할 수 있습니다.

n=2면 약 82.8%, n이 무한대로 가면 약 69.3%(= $\ln 2$)에 수렴합니다.

이 값은 충분 조건이지, 이를 넘으면 반드시 불가능하다는 뜻은 아닙니다.

앞의 A와 B의 CPU 이용률 상한 합은 5/20 + 15/50 = 0.25 + 0.30 = 0.55입니다. 두 태스크의 충분 조건 약 0.828보다 작으므로 앞서 나열한 이상 모델에서 RM 스케줄 가능성을 보장하는 조건을 만족합니다. 두 태스크가 t=0에 함께 시작하는 첫 50ms를 추적하면 A가 0~5, B가 5~20, 다음 A가 20~25에 실행하고, 준비된 작업이 없는 25~40은 유휴, 다음 A가 40~45에 실행합니다. 첫 B의 완료 t=20은 데드라인 t=50보다 이릅니다. 첫 구간의 그림만으로 임의의 다른 모델을 증명하는 것은 아니며, 여기서는 충분 조건과 해당 조건의 추적을 함께 확인합니다.

독립 확인: 같은 이상 모델에서 X의 실행 시간/주기가 4/10ms, Y가 5/20ms라면 두 태스크의 이용률 합은 얼마이며, RM의 두 태스크 충분 조건으로 판단할 수 있나요?

RM의 장점은 정적 우선순위이므로 구현이 단순하고 오버헤드가 적다는 것입니다.

이를 넘는 예를 직접 비교해 봅니다. 같은 이상 모델에서 A는 C=5ms, T=D=10ms이고 B는 C=8ms, T=D=20ms이며 두 태스크가 t=0부터 주기적으로 도착한다고 합시다. 이용률은 0.5+0.4=0.9로 약 0.828보다 크지만, RM은 A를 0~5, B를 5~10, 다음 A를 10~15, 남은 B를 15~18에 실행하고 18~20은 쉽니다. A job은 각각 t=5와 15에, B job은 t=18에 완료해 마감 10·20·20을 지킵니다. t=20에 두 주기의 패턴이 다시 시작하므로 같은 조건에서 반복할 수 있습니다. 충분 조건을 만족하지 않는 것과 실제 마감 실패는 다릅니다.

고정 우선순위로 태스크를 선택하는 RTOS에서는 개발자가 주기에 맞게 우선순위를 정해 RM 정책을 구성할 수 있습니다. 예를 들어 FreeRTOS의 우선순위 스케줄링을 사용한다고 해서 커널이 모든 태스크의 주기·최악 실행 시간을 자동 분석해 RM의 보장을 만들어 주는 것은 아닙니다. FreeRTOS의 태스크 우선순위와 분석 모델을 구분하세요.

Earliest Deadline First (EDF)

EDF는 데드라인이 가장 가까운 작업을 먼저 실행하는 동적 우선순위 알고리즘입니다.

가장 급한 것부터 처리하므로 직관적입니다.

단일 CPU, 선점 가능, 독립 태스크, 데드라인이 주기와 같은 전형적인 가정에서는 CPU 이용률이 100% 이하이면 스케줄 가능하다고 볼 수 있습니다.

단, 우선순위가 동적으로 변하므로 런타임 오버헤드와 과부하 상황의 해석이 더 어려울 수 있습니다.

과부하에서는 어느 작업이 마감을 놓치는지 별도로 분석해야 합니다. RM도 낮은 우선순위만 실패한다고 무조건 단정할 수 없습니다. 실제 SCHED_DEADLINE은 EDF 외에 실행 예산과 admission 제어를 함께 사용합니다.

Linux의 실시간 스케줄링

Linux는 범용 OS이지만 SCHED_FIFO와 SCHED_RR이라는 실시간 스케줄링 정책을 제공합니다.

실시간 우선순위는 1~99 범위를 가지며, 숫자가 클수록 더 높은 실시간 우선순위입니다.

실행 가능한 FIFO/RR 태스크는 일반 공정 클래스 작업보다 우선하지만, CPU 친화성·대역폭 제한 등 실행 조건도 적용됩니다.

# SCHED_FIFO, 우선순위 50으로 프로그램 실행
chrt -f 50 ./realtime_app

# 실행 중인 프로세스의 스케줄링 정책 확인
chrt -p 1234

실시간 작업의 CPU 독점은 다른 작업을 굶길 수 있습니다. Linux의 RT 대역폭 제어는 sched_rt_period_us와 sched_rt_runtime_us를 함께 해석하며, 기본 1,000,000μs 중 950,000μs는 95%에 해당합니다. 설정·커널 기능에 따라 달라지며 개별 태스크의 데드라인 보장은 아닙니다. 위 명령은 권한과 대상 프로그램을 준비한 환경용 예시로, 여기서 실행한 결과는 없습니다.

다음 절에서는 Linux CFS·EEVDF와 Windows의 실제 스케줄러 구현을 살펴보겠습니다.

연습: 실행 후보·회계·마감의 기준

1. CPU 할당량 8ms인 Q0에서 작업 P가 3ms 실행하고 I/O를 20ms 기다린 뒤 CPU를 4ms 더 썼습니다. 부스트·추가 비용·다른 작업은 없습니다. 회계하는 CPU 시간, 경과 시간, 남은 Q0 몫을 각각 구하세요. P는 아직 완료되지 않았습니다.
2. 위 C/T=5/10, 8/20 태스크는 이용률 0.9입니다. RM 충분 조건만으로 ‘불가능’이라고 판정할 수 있나요? 0~20ms 추적과 다음 반복이 필요한 이유를 설명하세요.
3. 시각 8ms에 Ready인 두 job이 각각 CPU 1ms를 남겼습니다. A의 태스크 주기는 4ms이고 이번 job의 도착은 8ms·상대 데드라인은 4ms입니다. B의 주기는 10ms이고 이번 job의 도착은 0ms·상대 데드라인은 10ms입니다. 추가 도착·비용은 없습니다. RM과 EDF가 먼저 고르는 job과 두 job의 완료·마감 시각을 계산하세요.
4. Q2의 작업 X가 실행 중이고 Q0의 Y가 새로 Ready가 됩니다. 큐 간 선점 우선순위와 Q2 내부 FCFS를 적용하며 부스트는 없습니다. X를 먼저 끝내야 하나요? 반대로 Y가 계속 Blocked인 경우도 설명하세요.