0x05. CPU 스케줄링

기본 개념

멀티프로그래밍과 멀티태스킹 환경에서 CPU 활용률을 최대화하는 것이 CPU 스케줄링의 핵심 목표다. 여러 프로세스가 CPU를 포함한 자원을 공유하기 때문에, 어떤 프로세스에 CPU를 언제 할당할 것인가를 결정하는 메커니즘이 필요하다.

멀티프로그래밍과 CPU 공유

CPU-I/O 버스트 사이클

프로세스 실행은 CPU 실행(CPU burst) 과 I/O 대기(I/O burst) 의 반복 사이클로 구성된다. 첫 번째와 마지막 버스트는 항상 CPU 버스트다.

프로세스는 CPU 사용 패턴에 따라 두 유형으로 나뉜다.

I/O 바운드 프로세스 (예: vi 에디터): 짧은 CPU 버스트가 많다
CPU 바운드 프로세스 (예: 컴파일러): 긴 CPU 버스트가 적다

예를 들어 CPU 버스트가 100번 발생하면, I/O 버스트는 99번이다. CPU 버스트와 I/O 버스트가 번갈아 나타나기 때문이다.

CPU-I/O 버스트 사이클

CPU 버스트 시간 분포

CPU 버스트 시간의 히스토그램은 지수 분포(exponential) 또는 초지수 분포(hyper-exponential) 형태를 보인다. 대부분의 CPU 버스트는 짧고, 긴 버스트는 드물다.

CPU 버스트 시간 히스토그램

CPU 스케줄러

CPU 스케줄러(= 단기 스케줄러, Short-term Scheduler)는 레디 큐(Ready Queue) 에서 프로세스를 선택하여 CPU를 할당하는 역할을 한다.

레디 큐의 구현 방식은 다양하다.

FIFO 큐, 우선순위 큐(Priority Queue), 트리, 비정렬 연결 리스트
각 프로세스는 PCB(Process Control Block) 로 표현된다

레디 큐 구현

선점형 스케줄링

선점형 스케줄링(Preemptive Scheduling) 이란 프로세스가 실행 중일 때도 강제로 CPU를 빼앗을 수 있는 방식이다. 인터럽트가 발생하거나 더 높은 우선순위의 프로세스가 도착했을 때 현재 프로세스를 중단시킨다.

스케줄링이 발생하는 시점

스케줄링 발생 시점

프로세스가 실행 상태에서 대기 상태로 전환될 때 (CPU가 유휴 상태가 됨)
프로세스가 실행 상태에서 준비 상태로 전환될 때 (예: 인터럽트 발생)
프로세스가 대기 상태에서 준비 상태로 전환될 때 (예: I/O 완료 후 우선순위가 높은 경우)
프로세스가 종료될 때

여기서 1번과 4번은 필수적(inevitable) 이고, 2번과 3번은 선택적(optional) 이다.

비선점형(Non-preemptive) 스케줄링 (= 협력적 스케줄링)

1번, 4번 상황에서만 스케줄링이 발생한다
실행 중인 프로세스가 중단되지 않는다

선점형(Preemptive) 스케줄링

1, 2, 3, 4번 모든 상황에서 스케줄링이 발생할 수 있다
하드웨어 지원과 공유 데이터 처리가 필요하다
여러 프로세스가 데이터를 공유할 때 경쟁 조건(Race Condition) 이 발생할 수 있다. 이는 탐지하기 어려운 버그로, 이를 해결하기 위해 동기화(Synchronization) 기법이 필요하다

커널의 선점

선점형 커널(Preemptive Kernel) 은 시스템 콜 실행 중에도 선점을 허용하는 커널이다.

응답성이 높아 실시간 응용(로봇, 자율주행)에 적합하지만, 성능 오버헤드가 발생한다

선점형 커널

대부분의 OS에서 시스템 콜은 비선점형으로 처리된다. 커널 구조를 단순하게 유지할 수 있기 때문이다.

디스패처

디스패처(Dispatcher) 는 단기 스케줄러가 선택한 프로세스에게 CPU 제어권을 넘겨주는 모듈이다. 구체적으로 다음 작업을 수행한다.

컨텍스트 스위칭(Context Switching)
사용자 모드로 전환
사용자 프로그램의 적절한 위치로 점프

디스패치 지연 시간(Dispatch Latency) 은 한 프로세스를 멈추고 다른 프로세스를 시작하는 데 걸리는 시간이다.

디스패처와 디스패치 지연

스케줄링 평가 기준

스케줄링 알고리즘을 평가하는 주요 기준은 다음과 같다.

CPU 이용률(Utilization): CPU를 가능한 한 바쁘게 유지
처리량(Throughput): 단위 시간당 완료되는 프로세스 수
반환 시간(Turnaround Time): 프로세스가 레디 큐에 들어간 시점부터 완료될 때까지의 시간
대기 시간(Waiting Time): 레디 큐에서 대기한 시간의 합
응답 시간(Response Time): 요청 제출 시점부터 첫 번째 응답이 나올 때까지의 시간

각 기준의 중요도는 시스템의 목적에 따라 달라진다.

스케줄링 알고리즘

FCFS (First-Come, First-Served)

FCFS는 CPU를 먼저 요청한 프로세스에게 먼저 할당하는 가장 단순한 방식이다.

비선점형 스케줄링이다
평균 대기 시간이 상당히 길어질 수 있다
CPU와 I/O 장치의 활용 효율이 낮다

아래는 시각 0에 도착한 세 프로세스의 FCFS 스케줄링 예시다.

FCFS 스케줄링 예시

SJF (Shortest-Job-First)

SJF는 다음 CPU 버스트가 가장 짧은 프로세스에게 CPU를 할당하는 방식이다.

SJF 스케줄링 예시

SJF 알고리즘은 최소 대기 시간 측면에서 최적(optimal) 이다. 그러나 현실적으로 다음 CPU 버스트의 길이를 정확히 아는 것이 어렵다는 문제가 있다.

이를 해결하기 위해 과거 기록을 기반으로 다음 CPU 버스트를 지수 평균(Exponential Averaging) 으로 예측한다.

지수 평균 공식

지수 평균 그래프

SJF의 선점형 버전: SRTF

최소 잔여 시간 우선(Shortest-Remaining-Time-First, SRTF) 스케줄링은 SJF의 선점형 버전이다. 새 프로세스가 도착했을 때 남은 CPU 버스트가 더 짧으면 현재 프로세스를 선점한다.

SRTF 스케줄링 예시

우선순위 스케줄링

우선순위 스케줄링은 가장 높은 우선순위를 가진 프로세스에게 CPU를 할당한다. 우선순위가 같으면 FCFS를 적용한다. 여기서는 낮은 숫자가 높은 우선순위를 의미한다.

우선순위 스케줄링 예시

우선순위는 내부적 또는 외부적으로 지정할 수 있다.

내부 우선순위: 시간 제한, 메모리 요구량, 열린 파일 수, I/O 버스트와 CPU 버스트의 비율 등 측정 가능한 값으로 결정한다. 예를 들어 gcc(CPU 바운드)와 vi(I/O 바운드)가 동시에 실행되면, 사용자와 상호작용해야 하는 vi가 더 높은 우선순위를 받는다.
외부 우선순위: 중요도, 정치적 요인 등 외부에서 지정한다

우선순위 스케줄링은 선점형으로도, 비선점형으로도 구현할 수 있다.

가장 큰 문제는 무기한 대기(Indefinite Blocking), 즉 기아(Starvation) 현상이다. 낮은 우선순위 프로세스가 영원히 실행되지 못할 수 있다. 해결책은 에이징(Aging) 기법으로, 오래 대기한 프로세스의 우선순위를 점진적으로 높여주는 것이다.

라운드 로빈 스케줄링

라운드 로빈 개념

라운드 로빈(Round-Robin, RR) 스케줄링은 FCFS와 유사하지만 선점형이다. 시분할 시스템(Time-sharing System)을 위해 설계되었다.

CPU 시간을 타임 퀀텀(Time Quantum) 또는 타임 슬라이스(Time Slice) 라는 단위로 나눈다
일반적으로 타임 퀀텀은 10~100 ms 수준이다 (참고: 컨텍스트 스위칭 지연은 약 10 us로, 1000배 작다)
레디 큐를 원형 큐(Circular Queue) 로 취급한다
CPU 스케줄러가 레디 큐를 순회하면서 각 프로세스에 최대 1 타임 퀀텀만큼 CPU 시간을 할당한다

라운드 로빈 스케줄링 예시

RR 스케줄링의 성능은 타임 퀀텀의 크기에 크게 좌우된다.

타임 퀀텀이 매우 작으면: 프로세서 공유(Processor Sharing) 효과로 응답성은 좋지만, 컨텍스트 스위칭 오버헤드가 커진다
타임 퀀텀이 매우 크면: FCFS와 동일해진다

타임 퀀텀과 컨텍스트 스위칭 오버헤드

반환 시간(Turnaround Time) 도 타임 퀀텀 크기에 따라 달라진다. 평균 반환 시간은 타임 퀀텀에 비례하지도, 반비례하지도 않는다.

대부분의 프로세스가 한 번의 타임 퀀텀 안에 다음 CPU 버스트를 마칠 수 있으면 평균 반환 시간이 개선된다
하지만 타임 퀀텀이 지나치게 길어도 바람직하지 않다
경험적 기준(Rule of Thumb): CPU 버스트의 약 80% 가 타임 퀀텀보다 짧아야 한다
I/O 바운드 프로세스는 한 퀀텀 안에 버스트가 끝나지만, CPU 바운드 프로세스는 여러 퀀텀에 걸쳐 실행된다

타임 퀀텀과 반환 시간 1

반환 시간은 대기 시간과 실행 시간의 합이다.

타임 퀀텀과 반환 시간 2

다단계 큐 스케줄링

다단계 큐(Multilevel Queue) 스케줄링은 프로세스를 메모리 요구량, 우선순위, 프로세스 유형 등에 따라 여러 그룹으로 분류하고, 각 그룹에 다른 스케줄링을 적용한다.

레디 큐를 여러 개의 별도 큐로 분할하며, 각 큐는 자체 스케줄링 알고리즘을 가진다.

다단계 큐 구조

큐 간 스케줄링 방식은 두 가지다.

고정 우선순위 선점형 스케줄링: 높은 우선순위 큐가 모두 비어야 낮은 우선순위 큐의 프로세스가 실행된다
큐 간 타임 슬라이싱: 예를 들어 포그라운드 큐(대화형 프로세스)에 80%, 백그라운드 큐(배치 프로세스)에 20%를 할당한다

중요한 특성으로, 프로세스의 큐 배정은 영구적이다. 한 번 배정된 큐에서 다른 큐로 이동할 수 없다.

다단계 피드백 큐 스케줄링

다단계 피드백 큐(Multilevel Feedback Queue) 스케줄링은 다단계 큐와 유사하지만, 프로세스가 큐 사이를 이동할 수 있다는 점이 다르다.

핵심 아이디어는 CPU 버스트 특성에 따라 프로세스를 분리하는 것이다.

CPU 시간을 너무 많이 사용하는 프로세스(CPU 바운드) 는 낮은 우선순위 큐로 이동한다
I/O 바운드, 대화형 프로세스는 높은 우선순위 큐에 유지된다

예를 들어 레디 큐가 Q0, Q1, Q2 세 개로 구성된 경우를 살펴보자.

Q0: 타임 퀀텀 = 8 ms
Q1: 타임 퀀텀 = 16 ms
Q2: FCFS

새 프로세스는 Q0에 들어간다. 타임 퀀텀을 초과하면 낮은 우선순위 큐로 이동한다.

다단계 피드백 큐 예시

다단계 피드백 큐 스케줄러를 정의하려면 다음 매개변수가 필요하다.

큐의 개수
각 큐의 스케줄링 알고리즘
프로세스를 상위 우선순위 큐로 승격시키는 기준
프로세스를 하위 우선순위 큐로 강등시키는 기준
프로세스가 서비스 요청 시 어떤 큐에 진입할지 결정하는 방법

가장 복잡한 스케줄링 알고리즘이지만, 그만큼 유연하다.

다중 프로세서 스케줄링

다중 프로세서(Multiple-Processor) 시스템에서는 부하 분산(Load Sharing) 이 가능해지지만, 스케줄링 문제는 더 복잡해진다. 일반적으로 최선의 해결책이라고 할 만한 단일 솔루션은 없다. 여기서는 모든 프로세서가 동일하다고 가정한다.

대칭형 vs. 비대칭형 멀티프로세싱

대칭형 멀티프로세싱(SMP): 모든 프로세서가 동일한 역할을 수행한다. 대부분의 현대 시스템이 이 방식을 사용한다.
비대칭형 멀티프로세싱(AMP): 프로세서마다 역할이 다르다.

레디 큐 구성 전략

모든 스레드를 공통 레디 큐(Common Ready Queue) 에 넣는 방식. 이 경우 두 프로세서가 같은 스레드를 선택하거나 큐에서 스레드가 유실되지 않도록 보장해야 한다.
각 프로세서가 자체 레디 큐(Private Queue) 를 가지는 방식.

프로세서 친화성

프로세스를 한 프로세서에서 다른 프로세서로 이주(Migration) 시키면 캐시 무효화와 재채움 오버헤드가 발생한다.

프로세서 친화성(Processor Affinity) 은 이 오버헤드를 피하기 위해 프로세스를 동일한 프로세서에서 계속 실행시키는 전략이다.

소프트 친화성(Soft Affinity): OS가 동일 프로세서 실행을 시도하지만, 프로세스가 다른 프로세서로 이주할 수도 있다
하드 친화성(Hard Affinity): 프로세스가 다른 프로세서로 이주하는 것을 완전히 차단한다

부하 균형

부하 균형(Load Balancing) 은 모든 프로세서에 작업 부하를 고르게 분배하려는 시도다. 각 프로세서가 자체 레디 큐를 가지는 시스템(대부분의 현대 OS)에서 특히 필요하다.

두 가지 접근 방식이 있다.

푸시 이주(Push Migration): 특정 태스크가 주기적으로 각 프로세서의 부하를 확인하고, 불균형이 발견되면 바쁜 프로세서에서 유휴 프로세서로 프로세스를 옮긴다
풀 이주(Pull Migration): 유휴 프로세서가 바쁜 프로세서의 대기 중인 태스크를 가져온다

푸시 이주와 풀 이주는 동시에 구현될 수 있다 (예: Linux, FreeBSD ULE 스케줄러).

주의할 점은 부하 균형이 프로세서 친화성의 이점을 상쇄할 수 있다는 것이다.

멀티코어 프로세서

멀티코어 프로세서는 하나의 물리적 칩에 여러 프로세서 코어를 탑재한 것이다. 각 프로세서가 별도의 칩을 가지는 시스템보다 빠르고 전력 소비가 적다.

멀티코어 프로세서의 스케줄링에서 주요 이슈는 메모리 스톨(Memory Stall) 이다. 캐시에 없는 데이터를 접근하는 등의 이유로 메모리 접근 시 상당한 시간을 대기하게 된다.

해결책은 멀티스레드 프로세서 코어를 사용하는 것이다. 각 코어에 두 개 이상의 하드웨어 스레드를 할당하여, 한 스레드가 메모리 스톨 상태일 때 다른 스레드가 실행될 수 있도록 한다.

멀티코어 프로세서의 메모리 스톨

멀티스레드 프로세서 코어

스레드 스케줄링

스레드는 두 종류가 있다.

사용자 스레드(User Thread): 스레드 라이브러리가 지원하며, LWP(Lightweight Process) 를 통해 간접적으로 스케줄링된다
커널 스레드(Kernel Thread): OS 커널이 지원한다

실제로 OS가 스케줄링하는 단위는 프로세스가 아니라 커널 스레드다.

스레드 스케줄링

경쟁 범위

PCS(Process-Contention Scope): 같은 프로세스 내의 사용자 스레드 간에 LWP를 두고 경쟁한다. Many-to-one 또는 many-to-many 모델에서 사용되며, 우선순위 기반이다.
SCS(System-Contention Scope): 시스템 전체에서 커널 스레드 간에 CPU를 두고 경쟁한다.

PCS와 SCS

스케줄러 활성화(Scheduler Activation)와 LWP

스케줄러 활성화와 LWP

Pthread 스케줄링

Pthreads에서 스레드 생성 시 PCS 또는 SCS를 지정할 수 있다.

PTHREAD_SCOPE_PROCESS (PCS): many-to-one 모델에서는 PCS만 가능하다
PTHREAD_SCOPE_SYSTEM (SCS): one-to-one 모델에서는 SCS만 가능하다
특정 시스템(Linux, macOS 등)에서는 특정 값만 허용된다

실시간 CPU 스케줄링

실시간 시스템(Real-time System) 은 정해진 시간 제한 안에 요청을 처리해야 하는 시스템이다. 자율주행, 로봇 등이 대표적인 예다.

실시간 운영체제(RTOS, Real-Time Operating System) 는 실시간 시스템을 지원하기 위한 OS로, 우선순위 큐 기반의 빠른 시스템 콜과 실시간 프로세스에 높은 우선순위를 부여하는 스케줄링이 핵심이다. 예를 들어 ABS(Anti-lock Brake System) 는 3~5 ms 이내의 지연 시간을 요구한다.

소프트 실시간 시스템(Soft Real-time): 데드라인 보장은 못하지만, 실시간 프로세스에 높은 우선순위를 부여하여 자원을 집중시킨다 (예: Linux)
하드 실시간 시스템(Hard Real-time): 태스크가 반드시 데드라인 안에 서비스되어야 한다. 데드라인이 지나면 서비스하지 않은 것과 같다.

지연 시간 최소화

대부분의 실시간 시스템은 이벤트 기반 시스템(Event-driven System) 이다. 이벤트가 발생하면 가능한 한 빠르게 응답하고 서비스해야 한다.

이벤트 지연 시간(Event Latency) 은 이벤트 발생부터 서비스까지 경과하는 시간이며, 크게 인터럽트 지연과 디스패치 지연으로 나뉜다.

이벤트 지연 시간 구성

인터럽트 지연

인터럽트 지연(Interrupt Latency) 은 인터럽트가 CPU에 도착한 시점부터 해당 인터럽트를 처리하는 루틴이 시작되기까지의 시간이다.

인터럽트 지연

디스패치 지연

디스패치 지연(Dispatch Latency) 은 스케줄링 디스패처가 한 프로세스를 중단하고 다른 프로세스를 시작하는 데 걸리는 시간이다. 선점형 커널이 디스패치 지연을 낮게 유지하는 가장 효과적인 기법이다.

디스패치 지연의 충돌 단계(Conflict Phase) 에서는 두 가지 작업이 수행된다.

커널에서 실행 중인 프로세스를 선점한다
고우선순위 프로세스가 필요로 하는 자원을 저우선순위 프로세스로부터 해제한다. 이 과정에서 우선순위 역전(Priority Inversion) 이 발생할 수 있으며, 에이징(Aging) 으로 해결한다.

디스패치 단계에서 고우선순위 프로세스를 가용 CPU에 스케줄링한다.

디스패치 지연

우선순위 기반 스케줄링

RTOS의 가장 중요한 특성은 실시간 프로세스에 즉시 응답하는 것이다. 따라서 스케줄러는 우선순위 기반 선점형 알고리즘을 지원해야 한다. 대부분의 OS는 실시간 프로세스에 최고 우선순위를 부여한다.

그러나 선점형, 우선순위 기반 스케줄러만으로는 소프트 실시간 기능만 보장할 수 있다. 하드 실시간 시스템은 데드라인 요구를 충족시키기 위한 추가 스케줄링 기법이 필요하다.

주기적 프로세스

주기적 프로세스(Periodic Process) 는 일정한 간격(주기)마다 CPU를 필요로 하는 프로세스다. 다음과 같은 매개변수로 정의된다.

처리 시간 t: 한 번 실행에 필요한 고정 시간
데드라인 d: 반드시 이 시간까지 서비스가 완료되어야 한다
주기 p: 실행 요청이 반복되는 간격

이 세 매개변수는 $0 \leq t \leq d \leq p$ 관계를 만족한다. 주기적 태스크의 실행률(Rate) 은 1/p 다.

주기적 프로세스

데드라인 기반 스케줄링

프로세스가 데드라인 요구를 스케줄러에게 알려야 할 수 있다. 수락 제어 알고리즘(Admission-control Algorithm) 을 사용하여 스케줄러는 다음 중 하나를 결정한다.

프로세스를 수락하여 제시간에 완료를 보장하거나
데드라인 충족이 불가능하면 요청을 거부한다

Rate-Monotonic 스케줄링

Rate-Monotonic 스케줄링은 주기적 프로세스 전용 알고리즘으로, 정적 우선순위 정책(Static Priority Policy) 과 선점을 사용한다.

각 주기적 태스크에는 주기에 반비례하는 우선순위가 할당된다. 즉, 주기가 짧을수록 우선순위가 높다(Shortest Period First).

Rate-Monotonic 스케줄링은 정적 우선순위 알고리즘 중 최적으로 간주된다. 이 알고리즘으로 스케줄링할 수 없는 프로세스 집합은, 다른 어떤 정적 우선순위 알고리즘으로도 스케줄링할 수 없다.

한계점: CPU 이용률에 상한이 있어 CPU 자원을 항상 완전히 활용할 수는 없다. 최악의 경우 CPU 이용률은 $N(2^{1/N} - 1)$ 이다 ( $N$ : 프로세스 수).

EDF (Earliest-Deadline-First) 스케줄링

EDF 스케줄링은 데드라인이 빠를수록 우선순위가 높은 동적 우선순위 알고리즘이다.

프로세스가 실행 가능해질 때 데드라인을 시스템에 알려야 한다
프로세스가 주기적일 필요가 없고, 버스트당 CPU 시간이 일정할 필요도 없다

이론적으로 최적이다. 각 프로세스가 데드라인을 충족하면서 CPU 이용률을 100%까지 달성할 수 있다.

비례 공유 스케줄링

비례 공유 스케줄러(Proportional Share Scheduler) 는 전체 프로세서 시간을 T개의 지분(Share) 으로 나누고, 각 애플리케이션에 N개의 지분을 할당하여 전체 프로세서 시간의 N/T를 보장한다.

수락 제어 정책과 함께 동작하여, 할당 가능한 지분 총합이 T를 넘지 않도록 한다. 예를 들어 100개 지분 중 85개가 이미 할당된 상태에서 30개를 요구하면 거부된다.

POSIX 실시간 스케줄링

POSIX는 실시간 스레드를 위한 스케줄링 클래스(Scheduling Class) 를 정의한다.

SCHED_FIFO: FCFS 정책. 동일 우선순위 스레드 간 타임 슬라이싱 없음. 가장 높은 우선순위의 실시간 스레드가 종료하거나 블록될 때까지 CPU를 점유한다.
SCHED_RR: 라운드 로빈 정책. SCHED_FIFO와 유사하지만 동일 우선순위 스레드 간 타임 슬라이싱을 적용한다.
SCHED_OTHER: 시스템별 정의. 사용자가 구현 방식을 결정한다.

POSIX API로 스케줄링 정책을 조회하고 설정할 수 있다.

pthread_attr_getschedpolicy(pthread_attr_t *attr, int *policy)
pthread_attr_setschedpolicy(pthread_attr_t *attr, int policy)

int i = 0, policy = 0;
pthread_t tid[NUM_THREADS];
pthread_attr_t attr;

/* 기본 속성 초기화 */
pthread_attr_init(&attr);

/* 현재 스케줄링 정책 조회 */
if (pthread_attr_getschedpolicy(&attr, &policy) != 0)
    fprintf(stderr, "Unable to get policy.\n");
else {
    if (policy == SCHED_OTHER)
        printf("SCHED OTHER\n");
    else if (policy == SCHED_RR)
        printf("SCHED RR\n");
    else if (policy == SCHED_FIFO)
        printf("SCHED FIFO\n");
}

/* 스케줄링 정책을 FIFO로 설정 */
if (pthread_attr_setschedpolicy(&attr, SCHED_FIFO) != 0)
    fprintf(stderr, "Unable to set policy.\n");

/* 스레드 생성 */
for (i = 0; i < NUM_THREADS; i++)
    pthread_create(&tid[i], &attr, runner, NULL);

/* 모든 스레드 종료 대기 */
for (i = 0; i < NUM_THREADS; i++)
    pthread_join(tid[i], NULL);

HGU 전산전자공학부 김인중 교수님의 23-1 운영체제 수업을 듣고 작성한 포스트이며, 첨부한 모든 사진은 교수님 수업 PPT의 사진 원본에 필기를 한 수정본입니다.

기본 개념

CPU-I/O 버스트 사이클

CPU 버스트 시간 분포

CPU 스케줄러

선점형 스케줄링

스케줄링이 발생하는 시점

커널의 선점

디스패처

스케줄링 평가 기준

스케줄링 알고리즘

FCFS (First-Come, First-Served)

SJF (Shortest-Job-First)

SJF의 선점형 버전: SRTF

우선순위 스케줄링

라운드 로빈 스케줄링

다단계 큐 스케줄링

다단계 피드백 큐 스케줄링

다중 프로세서 스케줄링

대칭형 vs. 비대칭형 멀티프로세싱

레디 큐 구성 전략

프로세서 친화성

부하 균형

멀티코어 프로세서

스레드 스케줄링

경쟁 범위

Pthread 스케줄링

실시간 CPU 스케줄링

지연 시간 최소화

인터럽트 지연

디스패치 지연

우선순위 기반 스케줄링

주기적 프로세스

데드라인 기반 스케줄링

Rate-Monotonic 스케줄링

EDF (Earliest-Deadline-First) 스케줄링

비례 공유 스케줄링

POSIX 실시간 스케줄링

운영체제 시리즈9편