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