CPU 스케줄링

게시 2025/10/19

By Jinhyeok Ko

조회 22 분읽는 시간

CPU 스케줄링

CPU 스케줄링은 단기 스케줄러(Short-term Scheduler) 가 Ready 큐에 있는 프로세스(혹은 커널 수준 스레드) 중에서 CPU를 할당받을 프로세스를 선택하는 정책(Policy) 및 알고리즘을 의미합니다.

현대 시분할(Time-Sharing) OS에서 스케줄링은 CPU가 쉴 틈 없이 일하게(Utilization 극대화) 하면서도, 사용자에게는 모든 프로그램이 동시에 실행되는 듯한 환상(Responsiveness)을 제공하는 핵심 기술입니다.

스케줄링의 목표(성능 척도)

OS가 스케줄러를 설계할 때 고려하는 목표들이며, 이들은 종종 서로 상충(Trade-off) 됩니다.

시스템 관점 (효율성)

CPU 이용률 (Utilization) : 전체 시간 중 CPU가 낭비되지 않고 일한 시간의 비율(최대화 목표)
처리율 (Throughput) : 단위 시간당 완료된 프로세스(작업)의 수(최대화 목표)

사용자 관점 (응답성)

반환 시간 (Turnaround Time) : 프로세스가 시스템에 제출된 순간부터 완료될 때까지 걸린 총 시간(대기 시간 + 실행 시간)
대기 시간 (Waiting Time) : 프로세스가 Ready 큐에서 CPU를 기다린 시간의 총합(스케줄러가 최소화하려는 핵심 대상)
응답 시간 (Response Time) : 사용자가 요청을 보낸 후, 첫 번째 응답이 오기까지 걸린 시간(대화형 시스템에서 매우 중요)

처리율을 극대화하려면 CPU를 오래 쓰는 긴 작업을 먼저 처리하는 것이 유리할 수 있지만, 이는 응답 시간을 희생시킵니다. 스케줄링 알고리즘은 이 목표들 사이의 균형점을 찾는 과정입니다.

디스패처(Dispatcher)

스케줄링을 이야기할 때 ‘스케줄러’와 ‘디스패처’를 구분해야 합니다.

스케줄러 (Scheduler) : 정책을 담당. “다음엔 A 프로세스를 실행하자”라고 결정(Select) 합니다.
디스패처 (Dispatcher) : 실행을 담당. 스케줄러의 결정을 받아 CPU의 제어권을 실제로 A 프로세스에게 넘겨주는 커널 모듈입니다.

디스패처가 이 작업을 완료하는 데 걸리는 시간을 디스패치 지연 시간(Dispatch Latency) 이라 하며, 이는 시스템의 순수 오버헤드이므로 가능한 한 빨라야 합니다.

문맥 교환(Context Switching)

문맥 교환은 스케줄링이 일어날 때 반드시 수반되는 ‘비용(Cost)’ 또는 ‘오버헤드(Overhead)’ 입니다.

문맥 교환이란, 현재 CPU를 점유하고 있는 프로세스(A)의 실행을 멈추고, 그 프로세스의 문맥(Context) 을 자신의 PCB(A) 에 저장한 뒤, 새로 실행할 프로세스(B)의 문맥을 PCB(B) 에서 가져와 CPU에 복원(Restore)하는 전 과정을 의미합니다. 이 실제 작업을 수행하는 커널 모듈이 바로 디스패처(Dispatcher) 입니다.

문맥 교환 (디스패처 동작) 단계

(Save) : 현재 실행 중인 프로세스(A)의 문맥(CPU 레지스터, PC 값 등)을 해당 프로세스의 PCB(A)에 저장합니다.
(Select) : 스케줄러가 다음으로 실행할 프로세스(B)를 Ready 큐에서 선택합니다.
(Restore) : 선택된 프로세스(B)의 문맥을 PCB(B)에서 CPU 레지스터로 복원(Restore)합니다.
(Jump) : 복원된 프로그램 카운터(PC) 값으로 점프하여 프로세스(B)의 실행을 재개합니다. (이때 필요시 사용자 모드로 전환)

문맥 교환이 일어나는 시점

문맥 교환은 OS 커널이 CPU의 제어권을 가져왔을 때 발생합니다.

인터럽트 (Interrupt)
- 타이머 인터럽트 : 프로세스의 할당 시간(Time Slice)이 만료되었을 때(선점형 스케줄링)
- I/O 완료 인터럽트 : I/O를 기다리던 프로세스(Blocked)가 Ready 상태가 되었을 때(새로 Ready가 된 프로세스의 우선순위가 더 높다면 교환 발생)
시스템 콜 (System Call / Trap)
- Running 상태의 프로세스가 I/O를 요청하여 스스로 Blocked 상태가 될 때(CPU가 유휴 상태가 되므로 다음 프로세스를 선택)

문맥 교환은 그 자체로는 아무런 ‘유용한 일’도 하지 않는 시간입니다. 문맥 교환이 너무 잦으면 오버헤드가 커져 시스템 전체 성능(처리율)이 저하됩니다.

비선점형(Non-preemptive) 알고리즘

프로세스가 Running 상태에 돌입하면, 그 프로세스가 I/O 요청으로 Blocked 상태가 되거나, 실행이 Terminated 될 때까지 OS가 강제로 CPU를 빼앗을 수 없는 방식입니다.

문맥 교환 오버헤드가 적고, 스케줄러 구현이 단순합니다.
응답 시간 예측 불가 : CPU를 오래 쓰는(CPU-bound) 프로세스 하나가 CPU를 독점하면, 다른 모든 프로세스가 무한정 기다려야 합니다.
Convoy Effect (호위 효과) : CPU 사용 시간이 긴 프로세스(A)가 먼저 도착하고, CPU 사용 시간이 짧은 여러 프로세스(B, C, D)가 뒤따라오면, A가 끝날 때까지 B, C, D가 모두 기다려야 하는 비효율이 발생합니다.

FCFS(First-Come, First-Served)

Ready 큐에 도착한 순서대로 CPU를 할당하는 가장 단순한 방식입니다. (큐 자료구조 그 자체)

호위 효과(Convoy Effect) 에 매우 취약합니다. 평균 대기 시간이 길어질 수 있습니다.

SJF(Shortest Job First)

Ready 큐에 있는 프로세스 중, 예상 CPU 실행 시간(Burst Time)이 가장 짧은 프로세스에게 CPU를 할당합니다. 모든 알고리즘 중 평균 대기 시간(Average Waiting Time) 을 최소화할 수 있음이 수학적으로 증명되었습니다.

기아 상태 (Starvation) : 실행 시간이 긴 프로세스는, 실행 시간이 짧은 프로세스들이 계속 도착하면 CPU를 영원히 할당받지 못할 수 있습니다.
예측의 어려움 : 프로세스의 미래 실행 시간을 정확히 예측하는 것이 불가능합니다. (보통 과거의 실행 기록으로 추정)

CPU Burst와 I/O Burst
프로세스 실행 중 발생하는 CPU 작업과 I/O 작업의 시간을 나타냅니다. 프로세스는 CPU Burst와 I/O Burst 를 교대로 반복하며 실행됩니다.
CPU Burst : 프로세스가 CPU를 사용해 계산이나 데이터 처리 작업을 수행하는 시간
I/O Burst : 프로세스가 I/O 장치를 사용해 데이터를 입출력하는 시간

선점형(Preemptive) 알고리즘

Running 상태의 프로세스라도, 할당된 시간(Time Quantum)이 만료되거나, 그보다 우선순위가 높은 프로세스가 Ready 큐에 도착하면, OS가 강제로 그 프로세스를 멈추고(Ready 상태로 돌려보냄) 다른 프로세스에게 CPU를 할당하는 방식입니다.

응답 시간이 빠르고 공정합니다. (시분할 시스템의 핵심)
문맥 교환 오버헤드: 문맥 교환이 비선점형보다 훨씬 자주 발생합니다.
경쟁 조건 (Race Condition) : 공유 데이터에 접근하던 중에 선점당하면 데이터 일관성이 깨질 수 있습니다. (동기화 문제 발생)

SRTF(Shortest Remaining Time First)

선점형 SJF. 현재 실행 중인 프로세스의 남은 시간보다, Ready 큐에 새로 도착한 프로세스의 전체 실행 시간이 더 짧다면, OS가 즉시 CPU를 빼앗아 새 프로세스에게 할당합니다.

SJF의 장점을 가지면서 응답성이 개선됩니다.
잦은 선점으로 인한 문맥 교환 오버헤드가 크며, 여전히 기아 상태 문제가 존재합니다.

Priority Scheduling

각 프로세스에 우선순위(정수)를 할당하고, Ready 큐에서 우선순위가 가장 높은 프로세스를 선택합니다. (선점형, 비선점형 모두 구현 가능)

선점형 스케줄링 방식에는 더 높은 우선순위의 프로세스가 도착하면 그 프로세스에게 CPU를 빼앗깁니다.
비선점형 스케줄링 방식에서는 더 높은 우선순위의 프로세스가 도착하더라도 그 프로세스는 우선 ready queue에 위치하게 됩니다.
기아 상태 (Starvation) : 우선순위가 낮은 프로세스는 영원히 실행되지 못할 수 있습니다.
- 해결책 (Aging) : 오래 기다린 프로세스의 우선순위(등급)를 시간이 지남에 따라 조금씩 높여주어, 언젠가는 반드시 실행될 수 있도록 보장합니다.

RR(Round Robin)

FCFS 알고리즘에 ‘타임 퀀텀(Time Quantum)’ 이라는 시간 할당량을 추가한 방식입니다. 프로세스는 할당된 퀀텀만큼만 실행되고, 시간이 만료되면(타이머 인터럽트 발생) 강제로 Ready 큐의 맨 뒤로 보내집니다. OS는 Ready 큐의 다음 프로세스를 실행합니다.

모든 프로세스가 (퀀텀의 배수 내에서) 공평하게 CPU를 얻으므로, 응답 시간이 매우 빠르고 기아 상태가 없습니다. 현대 시분할 시스템의 근간입니다.

Time Quantum의 크기
퀀텀이 너무 크면? (10초) : FCFS와 동일하게 동작하며, 응답 시간이 나빠집니다.
퀀텀이 너무 작으면? (1ms) : 문맥 교환이 너무 자주 발생하여, 오버헤드로 인해 실제 작업(처리율)이 저하됩니다. (Context Switching 시간 < Quantum 시간)
일반적으로 10ms ~ 100ms 사이의 값이 사용됩니다.

현대의 알고리즘 사용 방식

현대 OS(Windows, Linux, macOS)는 위에서 설명한 단일 알고리즘을 그대로 사용하지 않습니다. 이들을 조합한 다단계 큐(Multilevel Queue) 방식을 사용합니다.

다단계 큐(MLQ)

Ready 큐를 여러 개로 분리합니다.

전경(Foreground) 큐 : 응답 시간이 중요한 대화형 작업(UI 반응 등). (알고리즘 : RR)
배경(Background) 큐 : 처리율이 중요한 일괄 작업(파일 인코딩 등). (알고리즘 : FCFS)
스케줄러는 전경 큐를 먼저 모두 처리한 뒤, 배경 큐를 처리합니다. (기아 상태 발생 가능)

다단계 피드백 큐(MLFQ, Multilevel Feedback Queue)

MLQ에서 한 단계 더 나아가, 프로세스가 큐 사이를 이동할 수 있게 만든 방식입니다.

동작
1. 모든 작업은 가장 높은 우선순위 큐(퀀텀이 짧은 RR 큐)에 들어갑니다.
2. 자기 퀀텀을 다 쓰고도 끝나지 않으면(I/O 없이 CPU만 계속 씀), 더 낮은 우선순위 큐(퀀텀이 긴 RR 큐)로 강등됩니다.
3. I/O 작업을 오래 기다리다가 깨어난 프로세스(I/O-bound)는 다시 높은 우선순위 큐로 승급될 수 있습니다. (Aging)
결과 : CPU-bound 작업은 자연스럽게 낮은 우선순위로 내려가고, I/O-bound(대화형) 작업은 높은 우선순위를 유지하며 응답성을 보장합니다. (SJF의 ‘예측’ 문제를 실제 행동 패턴으로 해결)

멀티프로세서 스케줄링

지금까지의 내용은 CPU가 하나(Core 1개)라고 가정한 것입니다. 하지만 현대 CPU는 여러 개의 코어를 가지므로, OS는 “여러 개의 Ready 큐” 혹은 “공유된 Ready 큐”에서 어떤 코어에 프로세스를 할당할지 추가로 결정해야 합니다.

멀티프로세서 스케줄링의 접근법

비대칭 다중 처리(Asymmetric Multiprocessing, AMP)

하나의 ‘마스터’ 코어가 모든 스케줄링 결정과 I/O를 처리하고, 나머지 ‘슬레이브’ 코어들은 사용자 코드만 실행합니다. 구조는 단순하지만, 마스터 코어에 병목 현상이 발생하여 비효율적입니다. (현재 거의 사용되지 않음)

대칭 다중 처리 (Symmetric Multiprocessing, SMP)

현대 OS의 표준 방식(Linux, Windows, macOS 모두 사용)이며, 각 코어가 독립적인 스케줄러를 가지고 작동합니다. 모든 코어가 커널 코드에 접근하여 스케줄링을 수행할 수 있습니다. (이때 커널 자료구조, 예: Ready 큐 접근 시 동기화 문제가 발생할 수 있음)

SMP 스케줄링의 핵심 과제 : 캐시 vs 부하

SMP 환경의 스케줄러는 두 가지 상충되는 목표 사이에서 트레이드오프를 결정해야 합니다.

프로세서 선호도(Processor Affinity) - (캐시 효율)

프로세스가 한 코어(Core A)에서 실행되면, 그 데이터는 해당 코어의 L1/L2 캐시에 저장됩니다. 만약 이 프로세스가 다음번에 다른 코어(Core B)에서 실행되도록 스케줄링되면, Core B는 Core A의 캐시를 사용할 수 없습니다. (Cache Miss)

즉, 프로세스가 여러 코어를 불필요하게 옮겨 다니면 캐시 효율이 급격히 떨어집니다.

선호도(Affinity): OS가 프로세스를 가급적 이전에 실행했던 코어에 다시 할당하려는 경향입니다.
- 소프트 선호도 (Soft Affinity) : OS가 ‘노력’하지만 보장하지는 않음(일반적)
- 하드 선호도 (Hard Affinity) : 사용자가 특정 프로세스를 특정 코어에서만 실행하도록 ‘강제’함

부하 균형 (Load Balancing) - (CPU 이용률)

Core A는 Ready 큐에 10개의 프로세스가 대기 중인데, Core B는 아무 일도 하지 않고(Idle) 있다면, 시스템 전체의 CPU 이용률(Utilization) 이 저하됩니다. OS는 모든 코어가 공평하게 바쁘도록 프로세스들을 큐 간에 이주(Migration) 시켜야 합니다.

Push Migration : 특정 코어가 주기적으로 다른 코어들의 부하를 검사하여, 일이 많은 코어에서 적은 코어로 작업을 밀어냅니다(Push).
Pull Migration : 유휴 상태(Idle)인 코어가 할 일이 없으면, 바쁜 코어의 Ready 큐에서 작업을 가져옵니다(Pull).

부하 균형을 위해 프로세스를 다른 코어로 이주시키면(Migration), 프로세서 선호도가 깨져 캐시 효율이 떨어집니다. 현대 OS 스케줄러(Linux의 CFS 등)는 이 두 목표 사이의 균형을 맞추는 것을 핵심 과제로 삼습니다. (부하 격차가 아주 심할 때만 캐시 손해를 감수하고 이주시키는 방식)

운영체제