CS학습2026년 9월 8일

Priority Scheduling: 우선순위 기반 CPU 스케줄링과 기아 상태 문제

Priority Scheduling(우선순위 스케줄링)은 각 프로세스에 우선순위 값을 부여하고 가장 높은 우선순위의 프로세스에 CPU를 할당하는 스케줄링 알고리즘이다. 응답성이 중요한 작업을 먼저 처리할 수 있다는 장점이 있지만, 낮은 우선순위 프로세스가 영원히 실행되지 못하는 기아 상태(Starvation)를 유발할 수 있다. 이 문제를 해결하기 위해 에

송민성6분 읽기

1. 개념

Priority Scheduling은 준비 큐(Ready Queue)에 있는 프로세스 중 우선순위(Priority)가 가장 높은 프로세스를 선택해 CPU를 할당하는 스케줄링 알고리즘이다. 우선순위는 정수 값으로 표현하며, 시스템에 따라 낮은 숫자가 높은 우선순위를 의미하기도 하고(예: UNIX의 nice 값) 그 반대인 경우도 있다.

동일한 우선순위를 가진 프로세스가 여러 개 있으면 보통 FCFS(First-Come First-Served, 선입선출) 방식으로 처리한다. 우선순위는 정적(Static)으로 프로세스 생성 시 고정될 수도 있고, 동적(Dynamic)으로 실행 중에 시스템 상태에 따라 변할 수도 있다.

2. 왜 사용하는가

FCFS나 SJF(Shortest Job First)만으로는 실제 시스템의 요구사항을 충분히 반영하기 어렵다. 예를 들어 실시간 시스템에서는 센서 데이터 처리처럼 긴급한 작업을 일반 배치(Batch) 작업보다 먼저 처리해야 한다.

Priority Scheduling을 사용하면 다음과 같은 요구를 만족시킬 수 있다.

시스템 프로세스(커널 작업, 인터럽트 처리)를 사용자 프로세스보다 먼저 실행
대화형(Interactive) 프로세스에 배치 프로세스보다 높은 우선순위 부여
실시간(Real-time) 작업의 데드라인 준수

3. 동작 원리

스케줄러는 매 스케줄링 시점마다 준비 큐를 우선순위 기준으로 정렬하거나, 우선순위 큐(Priority Queue) 자료구조를 사용해 최고 우선순위 프로세스를 O(log n) 시간에 꺼낸다.

선점형(Preemptive) 방식: 새로 도착한 프로세스의 우선순위가 현재 실행 중인 프로세스보다 높으면 즉시 CPU를 빼앗아 재할당한다. 응답 시간은 빨라지지만 문맥 교환(Context Switch) 오버헤드가 늘어난다.

비선점형(Non-preemptive) 방식: 현재 실행 중인 프로세스가 끝나거나 스스로 CPU를 반납할 때까지 기다린 후 우선순위를 비교한다.

기아 상태(Starvation) 문제: 높은 우선순위 프로세스가 계속 들어오면 낮은 우선순위 프로세스는 CPU를 영원히 할당받지 못할 수 있다. 이를 "무기한 봉쇄(Indefinite Blocking)"라고도 부른다.

에이징(Aging) 해법: 대기 시간이 길어질수록 프로세스의 우선순위를 점진적으로 높여주는 기법이다. 예를 들어 1시간마다 우선순위를 1씩 올리면 아무리 낮은 우선순위라도 언젠가는 가장 높은 우선순위가 되어 실행 기회를 얻는다.

4. 코드 예제

우선순위 큐(최소 힙 기준, 숫자가 작을수록 높은 우선순위)를 이용한 비선점형 Priority Scheduling 시뮬레이션이다.

python

import heapq
from dataclasses import dataclass, field

@dataclass
class Process:
    pid: str
    arrival_time: int
    burst_time: int
    priority: int          # 숫자가 작을수록 높은 우선순위
    wait_time: int = field(default=0, compare=False)

def priority_scheduling(processes: list[Process]) -> list[tuple[str, int, int]]:
    """
    비선점형 Priority Scheduling.
    반환값: (pid, 시작 시각, 종료 시각) 리스트
    """
    processes = sorted(processes, key=lambda p: p.arrival_time)
    ready_heap = []  # (priority, arrival_time, process) 튜플로 heapq 사용
    result = []
    current_time = 0
    i = 0
    n = len(processes)

    while i < n or ready_heap:
        # 현재 시각까지 도착한 프로세스를 큐에 삽입
        while i < n and processes[i].arrival_time <= current_time:
            p = processes[i]
            heapq.heappush(ready_heap, (p.priority, p.arrival_time, p.pid, p.burst_time))
            i += 1

        if not ready_heap:
            # 준비 큐가 비어있으면 다음 도착 시각으로 시간 점프
            current_time = processes[i].arrival_time
            continue

        priority, arrival, pid, burst = heapq.heappop(ready_heap)
        start = current_time
        end = start + burst
        result.append((pid, start, end))
        current_time = end

    return result


if __name__ == "__main__":
    procs = [
        Process(pid="P1", arrival_time=0, burst_time=5, priority=3),
        Process(pid="P2", arrival_time=1, burst_time=3, priority=1),
        Process(pid="P3", arrival_time=2, burst_time=8, priority=4),
        Process(pid="P4", arrival_time=3, burst_time=6, priority=2),
    ]

    schedule = priority_scheduling(procs)
    for pid, start, end in schedule:
        print(f"{pid}: {start} -> {end}")

실행 결과는 다음과 같다.

text

P1: 0 -> 5
P2: 5 -> 8
P4: 8 -> 14
P3: 14 -> 22

P1은 도착 시점(0)에 유일한 프로세스라서 먼저 실행되고, 이후 우선순위(숫자가 작을수록 우선)에 따라 P2, P4, P3 순서로 처리된다.

에이징을 적용한 우선순위 계산 예시는 다음과 같다.

python

def apply_aging(base_priority: int, wait_time: int, aging_factor: int = 10) -> int:
    """
    대기 시간이 aging_factor만큼 지날 때마다 우선순위를 1 낮춰서(숫자를 낮춰서)
    실질적으로 우선순위를 높인다. 숫자가 작을수록 높은 우선순위 체계 기준.
    """
    aged_priority = base_priority - (wait_time // aging_factor)
    return max(aged_priority, 0)  # 우선순위는 0 미만으로 내려가지 않도록 제한

5. 시간 복잡도 또는 성능 특성

최고 우선순위 프로세스 선택: 우선순위 큐(이진 힙, Binary Heap)를 사용하면 삽입과 삭제 모두 O(log n)이다. 정렬되지 않은 리스트를 매번 순회하면 O(n)이다.
전체 스케줄링: 프로세스가 n개일 때 힙 기반 구현은 O(n log n)이다.
평균 대기 시간(Average Waiting Time): 우선순위 분포에 따라 크게 달라진다. SJF는 사실 "최단 작업 시간이 최고 우선순위"인 Priority Scheduling의 특수한 경우로 볼 수 있다.
문맥 교환 비용: 선점형 방식은 우선순위 역전이 자주 발생하는 환경에서 문맥 교환 횟수가 늘어나 오버헤드가 커질 수 있다.

6. 실무 사용 사례

Linux CFS(Completely Fair Scheduler): 완전히 동일하지는 않지만 nice 값(우선순위 -20~19)을 통해 프로세스 간 CPU 시간 배분 비율을 조정한다. nice 값이 낮을수록(음수) 높은 우선순위를 의미한다.
실시간 운영체제(RTOS): VxWorks, FreeRTOS 등에서는 태스크마다 고정 우선순위를 부여하고, 우선순위 기반 선점형 스케줄링을 기본으로 사용한다.
메시지 큐 시스템: RabbitMQ의 Priority Queue 기능, AWS SQS의 우선순위 처리 패턴 등에서도 동일한 개념이 적용된다.
작업 큐(Job Queue) 라이브러리: Bull(Node.js), Celery(Python) 같은 백그라운드 작업 큐에서 job에 우선순위를 부여해 긴급한 작업을 먼저 처리한다.

sql

-- 우선순위 기반 작업 큐 테이블 설계 예시 (PostgreSQL)
CREATE TABLE job_queue (
    id SERIAL PRIMARY KEY,
    payload JSONB NOT NULL,
    priority INT NOT NULL DEFAULT 5,  -- 숫자가 작을수록 높은 우선순위
    created_at TIMESTAMPTZ NOT NULL DEFAULT now(),
    status TEXT NOT NULL DEFAULT 'pending'
);

-- 에이징 효과를 흉내낸 조회: 오래 대기한 작업일수록 우선순위 가중치를 낮춤
SELECT id, payload,
       priority - (EXTRACT(EPOCH FROM (now() - created_at)) / 60)::INT AS effective_priority
FROM job_queue
WHERE status = 'pending'
ORDER BY effective_priority ASC
LIMIT 1
FOR UPDATE SKIP LOCKED;

7. 주의할 점

기아 상태(Starvation)를 반드시 고려한다. 우선순위만으로 스케줄링하면 낮은 우선순위 작업이 무한정 대기할 수 있으므로 에이징 같은 보완 기법을 함께 설계해야 한다.
우선순위 역전(Priority Inversion) 문제도 있다. 낮은 우선순위 프로세스가 공유 자원의 락(Lock)을 잡고 있으면, 높은 우선순위 프로세스가 그 자원을 기다리며 오히려 중간 우선순위 프로세스에 CPU를 뺏길 수 있다. 이를 해결하려면 우선순위 상속(Priority Inheritance) 프로토콜을 적용한다.
선점형 방식은 문맥 교환 비용을 반드시 함께 측정한다. 우선순위가 자주 바뀌는 환경에서는 오버헤드가 성능 이득을 상쇄할 수 있다.
우선순위 부여 기준을 명확히 문서화한다. 사람이 임의로 우선순위를 정하면 시스템 전체의 공정성(Fairness)이 깨질 위험이 있다.

8. 핵심 정리

Priority Scheduling은 우선순위가 높은 프로세스를 먼저 실행해 응답성과 긴급도 요구를 반영하는 스케줄링 알고리즘이며, 우선순위 큐를 사용하면 O(log n)에 최고 우선순위 프로세스를 선택할 수 있다. 다만 기아 상태와 우선순위 역전이라는 두 가지 대표적 문제를 안고 있으므로, 실무에서는 에이징이나 우선순위 상속 같은 보완 기법을 함께 적용해야 안정적으로 동작한다.