고급 스케줄링 알고리즘

기본 알고리즘들은 개념을 이해하기에 좋지만, 실제 OS는 더 정교한 스케줄링이 필요합니다. 데스크톱에서는 워드프로세서, 음악 플레이어, 컴파일러가 동시에 돌고, 서버에서는 웹 요청, 배치 작업, 시스템 모니터링이 공존합니다. 다양한 성격의 프로세스가 공존하는 환경에서, 하나의 알고리즘만으로는 모든 요구를 충족할 수 없습니다.

우선순위 스케줄링

각 프로세스에 우선순위(Priority)를 부여하고, 우선순위가 높은 프로세스를 먼저 실행합니다. 대부분의 실제 OS 스케줄러의 기반이 되는 알고리즘입니다.

우선순위의 표현은 시스템마다 다릅니다. Linux에서는 숫자가 작을수록 우선순위가 높고, 일부 시스템에서는 반대입니다. 중요한 것은 어떤 프로세스가 먼저 CPU를 받느냐입니다.

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

내부적 결정: OS가 프로세스의 특성을 분석하여 자동으로 설정합니다. 메모리 사용량, 열린 파일 수, CPU 버스트 대비 I/O 버스트 비율 등을 기반으로 합니다. I/O 바운드 프로세스는 높은 우선순위를 받습니다 — 잠깐 CPU를 쓰고 I/O로 돌아가므로, 빨리 처리하는 것이 전체 시스템 효율에 좋습니다.

외부적 결정: 사용자나 관리자가 명시적으로 설정합니다. Linux의 nice 값이 대표적입니다. 프로세스의 중요도에 대한 정책적 판단입니다.

우선순위 스케줄링은 선점형과 비선점형 모두 가능합니다. 선점형에서는 더 높은 우선순위의 프로세스가 도착하면 현재 프로세스를 즉시 중지하고 새 프로세스를 실행합니다. 비선점형에서는 현재 프로세스가 자발적으로 CPU를 놓을 때까지 기다립니다.

기아와 에이징

우선순위 스케줄링의 가장 큰 문제는 기아(Starvation)입니다. 높은 우선순위의 프로세스가 계속 도착하면, 낮은 우선순위의 프로세스는 Ready Queue에서 무한히 대기합니다. 이론적으로 영원히 실행되지 못할 수 있습니다.

MIT의 IBM 7094 컴퓨터에서 1973년에 시스템을 종료했을 때, 1967년에 제출된 프로세스가 아직 실행되지 않고 대기 중이었다는 일화가 있습니다. 6년 동안 기아 상태였던 것입니다.

에이징(Aging)은 기아 문제의 우아한 해결책입니다. 프로세스가 Ready Queue에서 대기한 시간에 비례하여 우선순위를 점진적으로 높입니다. 처음에 우선순위 127(최저)인 프로세스라도, 매 15분마다 우선순위가 1씩 올라가면, 충분히 오래 기다리면 결국 가장 높은 우선순위가 되어 실행됩니다.

멀티레벨 큐

멀티레벨 큐(Multilevel Queue)는 Ready Queue를 여러 개의 큐로 분리하고, 각 큐에 다른 스케줄링 알고리즘을 적용합니다. 프로세스의 성격에 따라 적합한 큐에 영구적으로 배치합니다.

전형적인 구성 예시

[시스템 프로세스 큐]  ←── 최고 우선순위 (우선순위 스케줄링)
        ↓
[대화형 프로세스 큐]  ←── 높은 우선순위 (라운드 로빈, q=20ms)
        ↓
[ 배치 프로세스 큐 ]  ←── 낮은 우선순위 (FCFS)

시스템 프로세스(커널 데몬, 시스템 서비스)가 최고 우선순위를 받고, 대화형 프로세스(GUI 앱, 에디터)가 그 다음, 배치 프로세스(컴파일, 데이터 분석)가 가장 낮습니다.

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

고정 우선순위: 상위 큐가 비어야만 하위 큐의 프로세스가 실행됩니다. 구현이 단순하지만, 하위 큐의 기아 가능성이 있습니다.

시간 할당: 각 큐에 CPU 시간의 비율을 할당합니다. 예: 시스템 큐 10%, 대화형 큐 70%, 배치 큐 20%. 배치 프로세스도 최소한 20%의 CPU 시간을 보장받습니다. 기아를 방지하면서도 대화형 프로세스의 응답성을 유지합니다.

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

멀티레벨 피드백 큐

멀티레벨 피드백 큐(Multilevel Feedback Queue, MLFQ)는 프로세스가 큐 사이를 이동할 수 있는 확장 모델입니다. 가장 유연하고, 현대 스케줄러의 이론적 기반이 되는 구조입니다.

핵심 아이디어: 프로세스의 과거 행동을 관찰하여 미래를 예측합니다. SJF가 실행 시간을 예측해야 하는 문제를 자연스럽게 해결합니다.

동작 원리

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

Q0: 타임 퀀텀 8ms  (최고 우선순위, RR)
Q1: 타임 퀀텀 16ms (중간 우선순위, RR)
Q2: FCFS          (최저 우선순위)

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

이렇게 하면 SJF처럼 동작하되, 실행 시간을 미리 알 필요가 없습니다. 짧은 작업은 Q0에서 빠르게 끝나고, CPU 바운드 작업은 자연스럽게 Q2로 내려가서 낮은 우선순위를 받습니다. I/O 바운드(대화형) 프로세스는 잠깐 CPU를 쓰고 I/O로 가므로 항상 높은 큐에 머물러 응답성이 보장됩니다.

MLFQ의 문제와 해결

교묘한 프로세스가 의도적으로 타임 퀀텀이 끝나기 직전에 불필요한 I/O를 요청하면, 항상 높은 우선순위를 유지하면서 CPU를 독점할 수 있습니다. 이것을 게이밍(Gaming)이라고 합니다.

해결책은 회계(Accounting)입니다. 프로세스가 각 큐에서 사용한 총 CPU 시간을 추적합니다. 총 사용 시간이 해당 큐의 할당량을 초과하면, 중간에 I/O를 했더라도 강등됩니다.

또 다른 문제는 장기 실행 프로세스의 기아입니다. CPU 바운드 프로세스가 Q2에 계속 머물면 실행 기회가 매우 적어집니다. 주기적 부스트(Priority Boost)로 해결합니다. 일정 주기(예: 1초)마다 모든 프로세스를 Q0으로 올려버립니다. 그러면 다시 행동을 관찰하여 적절한 큐로 재배치됩니다.

실시간 스케줄링

실시간 시스템(Real-Time System)은 "빠르게"가 아니라 "정해진 시간 안에" 작업을 완료하는 것이 핵심입니다. 데드라인을 지키느냐 못 지키느냐가 시스템의 정확성을 결정합니다.

경성 실시간(Hard Real-Time): 데드라인을 반드시 지켜야 합니다. 놓치면 시스템 실패 또는 인명 피해입니다.

• 항공기 비행 제어 시스템: 센서 데이터를 10ms 안에 처리하지 못하면 비행기가 추락합니다.
• 자동차 ABS: 브레이크 신호를 수 ms 안에 처리해야 합니다.
• 의료 장비: 심박 모니터가 2초간 데이터를 처리하지 않으면 환자에게 위험합니다.

연성 실시간(Soft Real-Time): 데드라인을 놓쳐도 성능 저하로 끝납니다. 시스템이 멈추지는 않습니다.

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

Rate Monotonic (RM)

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

주기가 짧다 = 자주 실행된다 = 데드라인이 빠르다. 직관적으로 더 급한 작업에 높은 우선순위를 주는 것입니다.

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

RM의 스케줄 가능성 조건: n개의 주기적 태스크가 있을 때, CPU 이용률이 $n(2^{1/n} - 1)$ 이하이면 스케줄 가능합니다. n=2면 약 82.8%, n이 무한대로 가면 약 69.3%(= $\ln 2$)에 수렴합니다.

RM의 장점은 정적 우선순위이므로 구현이 단순하고 오버헤드가 적다는 것입니다. RTOS(VxWorks, FreeRTOS)에서 널리 사용됩니다.

Earliest Deadline First (EDF)

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

가장 급한 것부터 처리하므로 직관적입니다. 이론적으로, CPU 이용률이 100% 이하이면 항상 스케줄 가능합니다(RM의 ~69.3%보다 높음). 단, 우선순위가 동적으로 변하므로 런타임 오버헤드가 더 큽니다.

Linux의 실시간 스케줄링

Linux는 범용 OS이지만 SCHED_FIFO와 SCHED_RR이라는 실시간 스케줄링 정책을 제공합니다. 우선순위 199를 가지며, 일반 프로세스(SCHED_OTHER, 우선순위 100139)보다 항상 먼저 실행됩니다.

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

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

실시간 프로세스가 CPU를 독점하면 시스템이 멈출 수 있으므로, /proc/sys/kernel/sched_rt_runtime_us로 실시간 태스크의 최대 CPU 사용 비율을 제한합니다(기본 95%).

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