CS학습2026년 9월 7일

FCFS: 도착 순서대로 처리하는 가장 단순한 CPU 스케줄링

FCFS(First-Come, First-Served)는 프로세스가 준비 큐(ready queue)에 도착한 순서대로 CPU를 할당하는 비선점형(non-preemptive) 스케줄링 알고리즘이다. 구현이 단순하지만 호위 효과(convoy effect)로 인해 평균 대기 시간이 크게 늘어날 수 있다. 다른 스케줄링 알고리즘(SJF, RR 등)을 이해하기 위한

송민성5분 읽기

1. 개념

FCFS(First-Come, First-Served)는 CPU를 요청한 프로세스를 도착한 순서 그대로 큐(queue)에 넣고, 그 순서대로 CPU를 할당하는 스케줄링 알고리즘이다. 자료구조 관점에서 보면 선입선출(FIFO) 큐를 그대로 CPU 스케줄러에 적용한 것이다.

한 번 CPU를 할당받은 프로세스는 자발적으로 CPU를 반납(종료 또는 I/O 요청)할 때까지 실행을 계속한다. 즉 비선점형(non-preemptive) 방식이며, 실행 중인 프로세스를 중간에 강제로 빼앗지 않는다.

2. 왜 사용하는가

구현이 극도로 단순하다. 큐에 넣고 빼는 로직만 있으면 된다.
우선순위 계산이나 실행 시간 예측 같은 추가 정보가 필요 없다.
모든 프로세스를 순서대로 공정하게 처리한다는 직관적인 공평성을 제공한다(단, 실제로는 대기 시간 공평성이 보장되지 않는다).
배치 처리 시스템(batch system)처럼 응답 시간보다 처리량 자체가 중요한 초기 컴퓨터 시스템에서 널리 쓰였다.

3. 동작 원리

프로세스가 준비 큐에 도착하면 큐의 맨 뒤에 삽입된다.
CPU가 유휴 상태가 되면 큐의 맨 앞 프로세스를 꺼내 실행한다.
실행 중인 프로세스는 종료되거나 I/O를 요청할 때까지 CPU를 점유한다.
CPU를 반납하면 다음 큐의 맨 앞 프로세스가 실행된다.

대기 시간(waiting time)과 반환 시간(turnaround time)은 프로세스의 도착 순서와 CPU 버스트 시간(burst time)에 의해 결정된다.

대기 시간 = 시작 시각 - 도착 시각
반환 시간 = 종료 시각 - 도착 시각

여기서 핵심 문제인 호위 효과(convoy effect)가 발생한다. CPU 버스트가 긴 프로세스가 먼저 도착하면, 뒤에 도착한 짧은 프로세스들이 모두 그 뒤에서 대기해야 한다. 마치 고속도로에서 느린 트럭 뒤에 차량들이 줄지어 서는 것과 같은 현상이다.

4. 코드 예제

python

from dataclasses import dataclass

@dataclass
class Process:
    pid: str
    arrival_time: int
    burst_time: int
    start_time: int = 0
    finish_time: int = 0
    waiting_time: int = 0
    turnaround_time: int = 0


def fcfs_schedule(processes: list[Process]) -> list[Process]:
    # 도착 시각 순으로 정렬 (FCFS의 핵심: 도착 순서 = 실행 순서)
    processes.sort(key=lambda p: p.arrival_time)

    current_time = 0
    for p in processes:
        # CPU가 유휴 상태였다면 프로세스 도착 시각까지 대기
        if current_time < p.arrival_time:
            current_time = p.arrival_time

        p.start_time = current_time
        p.finish_time = current_time + p.burst_time
        p.waiting_time = p.start_time - p.arrival_time
        p.turnaround_time = p.finish_time - p.arrival_time

        current_time = p.finish_time

    return processes


if __name__ == "__main__":
    procs = [
        Process(pid="P1", arrival_time=0, burst_time=24),
        Process(pid="P2", arrival_time=1, burst_time=3),
        Process(pid="P3", arrival_time=2, burst_time=3),
    ]

    result = fcfs_schedule(procs)

    total_waiting = 0
    for p in result:
        print(
            f"{p.pid}: 시작={p.start_time}, 종료={p.finish_time}, "
            f"대기={p.waiting_time}, 반환={p.turnaround_time}"
        )
        total_waiting += p.waiting_time

    print(f"평균 대기 시간: {total_waiting / len(result):.2f}")

실행 결과:

text

P1: 시작=0, 종료=24, 대기=0, 반환=24
P2: 시작=24, 종료=27, 대기=23, 반환=26
P3: 시작=27, 종료=30, 대기=25, 반환=28
평균 대기 시간: 16.00

P1의 버스트 시간이 24로 길기 때문에 P2, P3는 각각 23, 25만큼 기다린다. 이것이 호위 효과의 전형적인 예시다.

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

스케줄링 결정 자체의 시간 복잡도는 O(1)이다. 큐에서 맨 앞 원소를 꺼내기만 하면 되기 때문이다.
전체 프로세스를 도착 순으로 정렬해야 하는 경우(이미 도착 순서대로 큐에 쌓이지 않는 시뮬레이션 등)에는 정렬 비용 O(n log n)이 든다.
평균 대기 시간은 프로세스 도착 순서에 따라 크게 달라진다. 버스트 시간이 짧은 프로세스가 먼저 오면 평균 대기 시간이 짧아지고, 반대의 경우 크게 늘어난다.
SJF(Shortest Job First)와 비교하면 FCFS는 평균 대기 시간 측면에서 최적이 아니다. SJF는 비선점형 스케줄링 중 평균 대기 시간을 최소화하는 것으로 알려져 있다.

6. 실무 사용 사례

현대 범용 OS(리눅스, 윈도우)의 CPU 스케줄러는 FCFS를 단독으로 쓰지 않는다. 대신 CFS(Completely Fair Scheduler) 같은 복잡한 알고리즘을 사용한다.
FCFS는 배치 작업 큐, 프린터 스풀링(print spooling), 메시지 큐(message queue)의 작업 처리 순서처럼 응답 시간보다 순서 보장이 중요한 곳에서 여전히 활용된다.
디스크 스케줄링에서도 FCFS 방식(요청 도착 순서대로 처리)이 기본 개념으로 존재하며, SSTF(Shortest Seek Time First) 같은 알고리즘과 비교 대상이 된다.
네트워크 라우터의 큐 관리 정책 중 하나인 FIFO 큐잉이 FCFS와 동일한 개념이다.

7. 주의할 점

호위 효과 때문에 CPU 버스트가 매우 긴 프로세스 하나가 시스템 전체의 응답성을 크게 떨어뜨릴 수 있다.
비선점형이므로 인터랙티브 시스템(사용자 입력에 실시간으로 반응해야 하는 시스템)에는 부적합하다. 사용자가 짧은 명령을 입력해도 앞선 긴 작업이 끝날 때까지 기다려야 한다.
실무에서 FCFS를 순수하게 단독 사용하는 경우는 드물고, 대부분 다단계 큐(multilevel queue)나 우선순위 큐와 결합해서 사용한다.
알고리즘 자체는 기아 상태(starvation)를 일으키지 않는다는 장점이 있다(모든 프로세스가 결국 실행되긴 한다). 하지만 공평한 처리량 분배를 보장하지는 않는다.

8. 핵심 정리

FCFS는 도착 순서대로 CPU를 할당하는 가장 단순한 비선점형 스케줄링 알고리즘으로, 구현이 쉽고 기아 상태를 방지하지만 호위 효과로 인해 평균 대기 시간이 비효율적일 수 있다. 실무에서는 단독으로 쓰이기보다 다른 스케줄링 기법과 결합되거나, CPU 스케줄링 이론을 이해하기 위한 출발점으로 다뤄진다.