프로세스 스케줄링 알고리즘
요약
운영체제의 핵심, 프로세스 스케줄링을 마스터하세요. 선점형(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를 강제로 할당할 수 있습니다. 시분할 시스템에 적합합니다.
비선점형 스케줄링 (Non-preemptive Scheduling)
한 번 할당되면 끝날 때까지 아무도 막을 수 없는 방식입니다.
1. FIFO (First-In, First-Out) 또는 FCFS (First-Come, First-Served)
가장 간단한 방식으로, 준비 큐(Ready Queue)에 도착한 순서대로 CPU를 할당합니다.
- 장점: 구현이 쉽고 공평합니다.
- 단점: 실행 시간이 긴 프로세스가 먼저 도착하면 뒤따르는 짧은 프로세스들이 하염없이 기다려야 하는 콘보이 효과(Convoy Effect) 가 발생할 수 있습니다.
2. SJF (Shortest Job First)
실행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당합니다.
- 장점: 평균 대기 시간을 최소화하는 최적의 알고리즘입니다.
- 단점: 실행 시간이 긴 프로세스는 계속해서 새로운 짧은 프로세스에 밀려 무한정 기다릴 수 있는 기아 현상(Starvation) 이 발생할 수 있습니다. 또한, 각 프로세스의 실행 시간을 미리 정확히 예측하기 어렵습니다.
3. HRN (Highest Response-ratio Next)
SJF의 기아 현상을 보완하기 위해 만들어졌습니다. 대기 시간과 실행 시간을 모두 고려하여 우선순위를 동적으로 결정합니다.
- 우선순위 계산:
(대기 시간 + 실행 시간) / 실행 시간 - 특징: 이 값이 가장 높은 프로세스에게 CPU를 할당합니다. 대기 시간이 길어질수록 우선순위가 높아지므로 기아 현상을 방지할 수 있습니다.
4. 기한부 (Deadline)
프로세스에 주어진 마감 시간(Deadline) 안에 작업을 완료해야 하는 실시간 시스템에서 사용됩니다. 마감 시간이 가장 임박한 프로세스에 높은 우선순위를 부여합니다.
5. 우선순위 (Priority)
각 프로세스에 부여된 정적 우선순위에 따라 CPU를 할당합니다. 우선순위가 가장 높은 프로세스가 먼저 실행됩니다. SJF처럼 기아 현상이 발생할 수 있습니다.
선점형 스케줄링 (Preemptive Scheduling)
실행 중인 프로세스를 언제든 중단시키고 다른 프로세스에 CPU를 넘겨줄 수 있는 유연한 방식입니다.
1. 라운드 로빈 (Round Robin, RR)
FIFO에 시간 할당량(Time Quantum 또는 Time Slice) 개념을 추가한 방식입니다. 모든 프로세스는 정해진 시간 할당량만큼만 CPU를 사용하고, 시간이 다 되면 준비 큐의 맨 뒤로 돌아갑니다.
- 장점: 모든 프로세스가 공평하게 CPU 시간을 보장받아 대화형 시스템에 적합합니다.
- 단점: 시간 할당량이 너무 크면 FIFO와 같아지고, 너무 작으면 문맥 교환이 너무 잦아져 오버헤드가 커집니다. 적절한 시간 할당량을 설정하는 것이 중요합니다.
2. SRT (Shortest Remaining Time)
선점형 SJF알고리즘입니다. 현재 실행 중인 프로세스의 남은 시간보다 더 짧은 실행 시간을 가진 새로운 프로세스가 도착하면, 즉시 CPU를 빼앗아 그 새로운 프로세스에 할당합니다.
- 장점: 평균 대기 시간을 더 줄일 수 있습니다.
- 단점: 잦은 문맥 교환(Context Switching)으로 인한 오버헤드가 발생할 수 있으며, 여전히 기아 현상이 발생할 수 있습니다.
정보처리기사 실기 기출 문제
| 기출 | ||||||||||||||||
| 문제 |
위 표와 같은 프로세스들이 순서대로 준비 큐에 도착했을 때, 라운드 로빈 스케줄링을 사용할 경우 평균 대기 시간(ms)을 계산하시오.(시간할당량은 4ms, 컨텍스트 스위칭 시간은 무시한다.) | |||||||||||||||
| 답변 | ||||||||||||||||
| 정답 | 정답 보기 |
| 기출 | |
| 문제 | (1)은 CPU 실행 시간이 짧은 프로세스를 우선적으로 처리하는 스케줄링 방식으로 선점형 또는 비선점형으로 둘다 가능하다.
(2)는 (1)의 선점형 알고리즘이다. 실행 중인 프로세스보다 짧은 실행 시간을 가진 프로세스가 도착하면 현재 CPU를 선점한다. |
| 답변 | (1): (2): |
| 정답 | 정답 보기 |
정보처리기사 실기 대비 문제
| 문제 |
위 표와 같은 프로세스들이 순서대로 준비 큐에 도착했을 때, SJF 스케줄링을 사용할 경우 평균 대기 시간과 평균 반환 시간을 계산하시오. | |||||||||||||||
| 답변 | 평균 대기 시간: 평균 반환 시간: | |||||||||||||||
| 정답 | 정답 보기 |
| 문제 |
위 표와 같은 프로세스들이 순서대로 준비 큐에 도착했을 때, SRT(선점형) 스케줄링을 사용할 경우 평균 대기 시간과 평균 반환 시간을 계산하시오. | |||||||||||||||
| 답변 | 평균 대기 시간: 평균 반환 시간: | |||||||||||||||
| 정답 | 정답 보기 |
| 문제 |
위 표와 같은 프로세스들이 순서대로 준비 큐에 도착했을 때, 라운드 로빈(RR, 시간 할당량=2) 스케줄링을 사용할 경우 평균 대기 시간과 평균 반환 시간을 계산하시오. | |||||||||||||||
| 답변 | 평균 대기 시간: 평균 반환 시간: | |||||||||||||||
| 정답 | 정답 보기 |