OS - CPU 스케줄링

CPU 스케줄링 (FCFS, SJF, RR)

CPU는 컴퓨터에서 가장 비싸고 가장 빠른 자원이다. 한 대의 컴퓨터에서 수십·수백 개의 프로세스가 동시에 실행되는 것처럼 보이는 이유는 운영체제가 매우 짧은 시간 단위로 CPU를 여러 프로세스에 번갈아 할당하기 때문이며, 이 분배를 결정하는 알고리즘이 바로 CPU 스케줄링이다. 어떤 알고리즘을 쓰느냐에 따라 평균 대기 시간이 5배 차이 나고, 응답 시간이 보장되거나 망가지며, 일부 프로세스가 영원히 실행되지 못하는 기아 상태(starvation)가 발생하기도 한다. 본 글은 스케줄링의 평가 기준부터 다섯 가지 핵심 알고리즘, 그리고 다단계 큐 같은 실전 운영 기법을 세심하게 정리한다(출처: 위키백과 — Scheduling (computing)). 제가 학교 OS 실습에서 같은 프로세스 집합을 FCFS·SJF·RR 세 알고리즘으로 시뮬레이션해 본 후 평균 대기 시간이 28·12·15로 떨어지는 모습을 직접 본 후로는 "스케줄링 한 줄의 차이가 사용자 체감 응답성을 결정한다"는 사실을 손끝으로 받아들였다.

 

스케줄링 분류와 평가 기준

CPU 스케줄링은 가장 큰 분류 기준이 선점(Preemptive)과 비선점(Non-preemptive)의 구분이다. 비선점 스케줄링은 한 번 CPU를 점유한 프로세스가 자발적으로 양보하거나 종료될 때까지 다른 프로세스가 끼어들 수 없는 방식이며, 선점 스케줄링은 더 우선순위가 높은 프로세스가 들어오거나 시간 할당량이 끝나면 운영체제가 강제로 CPU를 빼앗는 방식이다. 여기서 선점이란 운영체제가 실행 중인 프로세스로부터 CPU를 강제로 회수해 다른 프로세스에 넘기는 동작을 가리키며, 응답성 보장의 핵심 메커니즘이다.

분류	의미	대표 알고리즘
비선점	한 번 잡으면 끝까지	FCFS, SJF(non-preemptive), HRRN
선점	우선순위·시간 만료 시 회수	Round Robin, SRT, MLFQ

스케줄링 알고리즘을 평가하는 표준 척도가 다섯 가지 있다. 시험에서 자주 출제되는 항목이다.

척도	의미	목표
CPU 이용률	전체 시간 중 CPU가 실제 작업한 비율	최대화
처리량(Throughput)	단위 시간당 완료된 프로세스 수	최대화
반환 시간(Turnaround)	도착 → 종료까지 걸린 총 시간	최소화
대기 시간(Waiting)	준비 큐에서 기다린 시간의 합	최소화
응답 시간(Response)	도착 → 첫 실행까지 걸린 시간	최소화 (특히 대화형)

이 다섯 척도는 서로 트레이드오프 관계에 있어 한 척도를 극대화하면 다른 척도가 희생되는 경우가 많다. 따라서 한 알고리즘이 모든 상황에 최적이라는 결론은 없으며, 시스템의 사용 패턴(배치 vs 대화형)에 따라 적합한 알고리즘이 갈린다는 사실이 시험 답안의 핵심이다.

5대 핵심 스케줄링 알고리즘

가장 단순한 알고리즘부터 차례로 보자. 각 알고리즘의 동작 원리와 장단점을 정확히 외워두는 것이 시험 답안의 안정적인 점수원이 된다(출처: Operating System Concepts (Silberschatz)).

FCFS(First-Come, First-Served)는 가장 단순한 비선점 알고리즘으로, 도착한 순서대로 CPU를 할당한다. 구현이 가장 간단하다는 강점이 있지만, 긴 작업이 먼저 도착하면 뒤에 도착한 짧은 작업들이 모두 기다려야 하는 호위 효과(Convoy Effect)가 발생한다. 여기서 호위 효과란 긴 작업 한 개 뒤로 짧은 작업들이 길게 줄을 서면서 평균 대기 시간이 폭증하는 현상을 의미한다.

SJF(Shortest Job First)는 실행 시간이 가장 짧은 작업부터 처리하는 알고리즘이다. 평균 대기 시간이 이론적으로 최적임이 증명되어 있다는 결정적 강점을 가지지만, 두 가지 약점이 있다. 첫째, 각 작업의 실행 시간을 미리 알아야 하므로 현실에서는 추정이 필요하다. 둘째, 긴 작업이 영원히 실행되지 못하는 기아 상태(starvation)가 발생할 수 있다. SJF의 선점 버전이 SRT(Shortest Remaining Time)이며, 새 작업이 들어올 때마다 남은 실행 시간이 더 짧은 작업이 있으면 현재 작업을 멈추고 그쪽으로 전환한다.

우선순위 스케줄링(Priority Scheduling)은 각 프로세스에 부여된 우선순위에 따라 CPU를 할당하는 알고리즘이다. 우선순위는 외부(사용자 지정)·내부(메모리 요구량·시간 한도 등) 기준으로 정해지며, 같은 우선순위에서는 FCFS로 처리된다. SJF는 사실 우선순위 스케줄링의 특수 사례(우선순위 = 1/실행 시간)로 볼 수 있다. 약점은 SJF와 같이 기아 상태이며, 이를 막기 위해 에이징(Aging) 기법을 적용한다. 에이징이란 오래 기다린 프로세스의 우선순위를 점진적으로 올려 결국에는 실행되도록 만드는 보정 기법을 가리킨다.

Round Robin(RR)은 가장 널리 사용되는 선점 알고리즘으로, 각 프로세스에 동일한 시간 할당량(time quantum)을 주고 끝나지 않으면 큐의 맨 뒤로 보낸다. 여기서 시간 할당량이란 한 프로세스가 한 번에 점유할 수 있는 최대 CPU 시간을 의미하며, 일반적으로 10~100ms 사이로 설정된다. RR의 강점은 응답 시간이 보장된다는 점이며, 대화형 시스템과 시분할 시스템의 표준 알고리즘으로 자리 잡았다. 시간 할당량이 너무 크면 FCFS에 가까워지고, 너무 작으면 컨텍스트 스위칭 오버헤드가 폭증한다는 트레이드오프가 있다.

HRRN(Highest Response Ratio Next)은 SJF의 기아 문제를 해결한 비선점 알고리즘이다. 응답 비율 = (대기 시간 + 실행 시간) / 실행 시간으로 계산하며, 이 비율이 가장 높은 작업을 선택한다. 짧은 작업이 우선시되면서도 오래 기다린 작업의 비율이 자연스럽게 올라가 결국 실행되기 때문에 기아 상태가 발생하지 않는다.

# 간단한 RR 시뮬레이션
from collections import deque

def round_robin(processes, quantum):
    # processes: [(name, arrival, burst), ...]
    time = 0
    q = deque()
    remaining = {p[0]: p[2] for p in processes}
    arrived = sorted(processes, key=lambda p: p[1])
    completed = {}
    idx = 0

    while remaining:
        while idx < len(arrived) and arrived[idx][1] <= time:
            q.append(arrived[idx][0]); idx += 1
        if not q:
            time = arrived[idx][1]; continue
        name = q.popleft()
        run = min(quantum, remaining[name])
        time += run
        remaining[name] -= run
        while idx < len(arrived) and arrived[idx][1] <= time:
            q.append(arrived[idx][0]); idx += 1
        if remaining[name] == 0:
            completed[name] = time; del remaining[name]
        else:
            q.append(name)
    return completed

print(round_robin([("A",0,5), ("B",1,3), ("C",2,8)], quantum=2))

다단계 큐와 실전 운영 — MLQ·MLFQ

현실의 운영체제는 단일 알고리즘으로는 다양한 워크로드(배치·대화형·실시간)를 모두 만족시킬 수 없다. 그래서 등장한 것이 다단계 큐(Multilevel Queue, MLQ)와 다단계 피드백 큐(Multilevel Feedback Queue, MLFQ)이다.

MLQ는 여러 개의 준비 큐를 두고 각 큐마다 다른 스케줄링 알고리즘을 적용한다. 예를 들어 대화형 프로세스용 큐에는 RR을, 배치 프로세스용 큐에는 FCFS를, 시스템 프로세스용 큐에는 우선순위 스케줄링을 적용하는 식이다. 큐 간 우선순위를 정해 두면 상위 큐가 비어 있을 때만 하위 큐가 실행된다. 다만 프로세스가 한 큐에 영구히 묶여 있어 워크로드 변화에 대응하지 못한다는 약점이 있다.

MLFQ는 MLQ의 진화 버전으로, 프로세스가 큐 사이를 이동할 수 있게 만든 알고리즘이다. CPU를 오래 점유하는 프로세스는 점점 낮은 우선순위 큐로 떨어지고, 짧게 끊어 쓰는 프로세스는 높은 우선순위에 머문다. 그 결과 짧은 작업은 빠르게 응답받고, 긴 작업은 자기에게 적합한 낮은 우선순위 큐에서 차분히 처리되는 흐름이 자연스럽게 만들어진다. Linux의 CFS(Completely Fair Scheduler)와 Windows의 스레드 스케줄러가 모두 MLFQ 계열의 발전형이다.

알고리즘	선점	평균 대기	기아 가능	응답성	채택
FCFS	×	나쁨 (호위 효과)	없음	나쁨	단순 배치
SJF	×	최적	있음	보통	작업 시간 예측 가능 시
SRT	○	매우 좋음	있음	좋음	대화형
Priority	둘 다	보통	있음(에이징 필요)	보통	실시간
RR	○	보통	없음	매우 좋음	시분할 표준
HRRN	×	좋음	없음	보통	균형 잡힌 비선점
MLFQ	○	매우 좋음	없음(피드백)	매우 좋음	현대 OS 표준

솔직히 이건 예상 밖이었는데, 학교에서는 FCFS·SJF·RR이 따로 따로 배워지지만 실제 Linux나 Windows의 스케줄러는 이들 모두를 혼합한 MLFQ 변형이라는 사실을 알고 나서야 "단일 알고리즘은 시험에서나 존재하고 실무에서는 항상 하이브리드"라는 점을 손끝으로 받아들였다. 마지막으로 시험 답안에서 자주 쓰이는 정형 표현을 정리하면, "CPU 스케줄링은 한정된 CPU 자원을 여러 프로세스에 공정하고 효율적으로 분배하는 알고리즘이며, 비선점(FCFS·SJF·HRRN)과 선점(RR·SRT·MLFQ)으로 나뉜다. RR은 시분할 시스템의 표준이고, 현대 운영체제는 거의 모두 MLFQ 계열 변형을 채택한다"는 두 문장이 표준 답안 표현으로 통한다.

---

메타 디스크립션: CPU 스케줄링의 평가 기준 5종(이용률·처리량·반환·대기·응답)과 5대 핵심 알고리즘(FCFS·SJF·우선순위·RR·HRRN), 그리고 MLQ·MLFQ 같은 실전 운영 기법을 코드 예시와 비교표로 OS 입문자 관점에서 세심하게 정리합니다.