프로세스 스케줄링 알고리즘
요약
운영체제의 핵심, 프로세스 스케줄링을 마스터하세요. 선점형(SRT, Round Robin)과 비선점형(FIFO, SJF, HRN 등) 알고리즘의 원리를 이해하고, 평균 대기 및 반환 시간 계산 문제로 실전 감각을 키웁니다.
프로세스 스케줄링 알고리즘 정리
| 비선점형 | 선점형 |
|---|---|
| FIFO(도착 순서대로 할당) | Round Robin(FIFO + 시간 지정) |
| SJF(실행 시간 짧은 프로세스에 할당, 비선점형/선점형 둘다 가능) | SRT(선점형 SJF) |
| HRN(SJF + 대기 시간 고려) | |
| 기한부(마감시간 임박한 프로세스 먼저) | |
| 우선순위(우선순위에 따라 할당) |
프로세스 스케줄링, 왜 필요할까?
컴퓨터는 여러 프로세스를 동시에 처리해야 합니다. 이때, 어떤 프로세스에 CPU를 할당할지 결정하는 규칙이 바로 프로세스 스케줄링입니다. 스케줄링의 목표는 CPU를 효율적으로 사용하고, 모든 프로세스에 공평한 기회를 주며, 사용자의 대기 시간을 최소화하는 것입니다.
스케줄링 방식은 크게 비선점형(Non-preemptive) 과 선점형(Preemptive) 두 가지로 나뉩니다.
- 비선점형 스케줄링: 한 프로세스가 CPU를 할당받으면, 해당 프로세스가 종료되거나 입출력(I/O) 작업을 위해 스스로 CPU를 반납할 때까지 다른 프로세스가 CPU를 빼앗을 수 없습니다.
- 선점형 스케줄링: 운영체제가 필요하다고 판단하면, 현재 실행 중인 프로세스를 중단시키고 다른 프로세스에 CPU를 강제로 할당할 수 있습니다. 시분할 시스템에 적합합니다.
프로세스 상태 (Process State)
스케줄러가 어떤 프로세스에 CPU를 줄지 결정하려면, 먼저 각 프로세스가 지금 어떤 상태인지 알아야 합니다. 정처기 실기에서는 다음 세 가지 주요 상태를 매칭하는 형태로 자주 출제됩니다.
- 준비(Ready): 실행에 필요한 자원을 모두 가지고 있고 CPU만 할당되면 즉시 실행 가능한 상태. 준비 큐(Ready Queue) 에서 자기 차례를 기다립니다.
- 실행(Run / Running): 스케줄러가 CPU를 할당하여 실제로 명령어를 수행 중인 상태. CPU 코어 1개당 한 시점에 한 프로세스만 실행 상태가 됩니다.
- 대기(Wait / Block / Blocked): 입출력(I/O) 같은 외부 사건이 끝날 때까지 CPU를 반납하고 멈춰 있는 상태. 사건이 완료되면 다시 준비 상태로 돌아갑니다.
전이 흐름은 다음과 같습니다.
- 준비 → (디스패치) → 실행
- 실행 → (I/O 요청) → 대기
- 대기 → (I/O 완료) → 준비
- 실행 → (시간 할당량 만료, 선점형 스케줄링) → 준비
IPC (Inter-Process Communication)
운영체제는 프로세스마다 독립된 메모리 공간을 할당합니다. 그래서 한 프로세스가 다른 프로세스의 변수를 직접 읽거나 쓸 수 없죠. 대신 운영체제가 제공하는 통신 메커니즘을 통해서만 데이터를 주고받을 수 있는데, 이를 IPC(Inter-Process Communication) 라고 합니다.
대표적인 IPC 기법:
- 공유 메모리(Shared Memory): 여러 프로세스가 같은 메모리 영역을 매핑하여 직접 읽고 씁니다. 가장 빠른 IPC 기법이며, 동기화는 별도로 처리해야 합니다.
- 소켓(Socket): 네트워크 프로토콜을 이용한 양방향 통신 채널. 같은 호스트뿐 아니라 다른 호스트의 프로세스와도 통신할 수 있습니다.
- 세마포어(Semaphore): 임계 구역(Critical Section)에 대한 동시 접근을 제어하는 동기화 도구. P(wait)/V(signal) 연산으로 자원 카운트를 관리합니다.
- 메시지 큐(Message Queue): 커널이 관리하는 큐에 메시지를 넣고 다른 프로세스가 꺼내 가는 비동기 통신 방식.
- 파이프(Pipe)·시그널(Signal): 부모-자식 관계의 프로세스 간 단방향 데이터 전달이나 비동기 알림에 사용됩니다.
비선점형 스케줄링 (Non-preemptive Scheduling)
한 번 할당되면 끝날 때까지 아무도 막을 수 없는 방식입니다.
FIFO (First-In, First-Out) 또는 FCFS (First-Come, First-Served)
가장 간단한 방식으로, 준비 큐(Ready Queue)에 도착한 순서대로 CPU를 할당합니다.
- 장점: 구현이 쉽고 공평합니다.
- 단점: 실행 시간이 긴 프로세스가 먼저 도착하면 뒤따르는 짧은 프로세스들이 하염없이 기다려야 하는 콘보이 효과(Convoy Effect) 가 발생할 수 있습니다.
SJF (Shortest Job First)
실행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당합니다.
- 장점: 평균 대기 시간을 최소화하는 최적의 알고리즘입니다.
- 단점: 실행 시간이 긴 프로세스는 계속해서 새로운 짧은 프로세스에 밀려 무한정 기다릴 수 있는 기아 현상(Starvation) 이 발생할 수 있습니다. 또한, 각 프로세스의 실행 시간을 미리 정확히 예측하기 어렵습니다.
HRN (Highest Response-ratio Next)
SJF의 기아 현상을 보완하기 위해 만들어졌습니다. 대기 시간과 실행 시간(서비스 시간)을 모두 고려하여 우선순위를 동적으로 결정합니다.
- 우선순위 계산:
(대기 시간 + 서비스 시간) / 서비스 시간 - 특징: 이 값이 가장 높은 프로세스에게 CPU를 할당합니다. 대기 시간이 길어질수록 우선순위가 높아지므로 기아 현상을 방지할 수 있습니다.
기한부 (Deadline)
프로세스에 주어진 마감 시간(Deadline) 안에 작업을 완료해야 하는 실시간 시스템에서 사용됩니다. 마감 시간이 가장 임박한 프로세스에 높은 우선순위를 부여합니다.
우선순위 (Priority)
각 프로세스에 부여된 정적 우선순위에 따라 CPU를 할당합니다. 우선순위가 가장 높은 프로세스가 먼저 실행됩니다. SJF처럼 기아 현상이 발생할 수 있습니다.
선점형 스케줄링 (Preemptive Scheduling)
실행 중인 프로세스를 언제든 중단시키고 다른 프로세스에 CPU를 넘겨줄 수 있는 유연한 방식입니다.
라운드 로빈 (Round Robin, RR)
FIFO에 시간 할당량(Time Quantum 또는 Time Slice) 개념을 추가한 방식입니다. 모든 프로세스는 정해진 시간 할당량만큼만 CPU를 사용하고, 시간이 다 되면 준비 큐의 맨 뒤로 돌아갑니다.
- 장점: 모든 프로세스가 공평하게 CPU 시간을 보장받아 대화형 시스템에 적합합니다.
- 단점: 시간 할당량이 너무 크면 FIFO와 같아지고, 너무 작으면 문맥 교환이 너무 잦아져 오버헤드가 커집니다. 적절한 시간 할당량을 설정하는 것이 중요합니다.
SRT (Shortest Remaining Time)
선점형 SJF알고리즘입니다. 현재 실행 중인 프로세스의 남은 시간보다 더 짧은 실행 시간을 가진 새로운 프로세스가 도착하면, 즉시 CPU를 빼앗아 그 새로운 프로세스에 할당합니다.
- 장점: 평균 대기 시간을 더 줄일 수 있습니다.
- 단점: 잦은 문맥 교환(Context Switching)으로 인한 오버헤드가 발생할 수 있으며, 여전히 기아 현상이 발생할 수 있습니다.