전공서에서 다루는 CPU 스케줄링 알고리즘
운영체제마다, 그리고 시스템의 목적에 따라 서로 다른 CPU 스케줄링 알고리즘을 사용합니다. 각 알고리즘의 작동 방식과 장단점을 이해하면 운영체제가 어떻게 컴퓨터의 성능을 최적화하는지 알 수 있습니다.
크게 비선점형(빼앗을 수 없음)과 선점형(빼앗을 수 있음), 그리고 우선순위 기반으로 나누어 살펴보겠습니다.
1. 선입 선처리 스케줄링 (FCFS)
First Come, First Served
가장 단순한 방식입니다. "먼저 온 손님을 먼저 대접한다"는 식당의 원칙과 같습니다.
- 방식: 준비 큐에 도착한 순서대로 CPU를 할당합니다. (비선점형)
- 장점: 알고리즘이 단순하고 이해하기 쉽습니다.
- 단점 (호위 효과, Convoy Effect): 만약 맨 앞에 줄 선 프로세스가 엄청나게 긴 작업(CPU 사용 시간이 긴)이라면? 뒤에 있는 간단한 작업들은 하염없이 기다려야 합니다.
- 비유: 편의점에서 앞사람이 로또를 100장 사고 있어서, 뒤에 껌 하나 사려는 사람이 10분을 기다리는 상황과 같습니다.
2. 최단 작업 우선 스케줄링 (SJF)
Shortest Job First
FCFS의 단점을 보완하기 위해 "가장 짧게 걸리는 일부터 먼저 하자"는 방식입니다.
- 방식: 준비 큐에 있는 프로세스 중, CPU 사용 시간이 가장 짧은 프로세스부터 실행합니다. (주로 비선점형)
- 장점: 평균 대기 시간을 줄이는 데 가장 효율적입니다.
- 단점:
- 예측의 어려움: 실제로 프로세스가 CPU를 얼마나 쓸지 미리 정확히 알기 어렵습니다.
- 기아 현상: 긴 작업은 짧은 작업들이 계속 들어오면 영원히 실행되지 못할 수 있습니다.
3. 라운드 로빈 스케줄링 (RR)
Round Robin
현대 컴퓨터가 여러 프로그램을 동시에 실행하는 것처럼 보이게 하는 핵심 알고리즘입니다. "공평하게 시간(Time Slice)을 정해서 돌아가며 쓰자"는 방식입니다.
- 방식: FCFS처럼 순서대로 줄을 서지만, 각자 타임 슬라이스(Time Slice)라는 정해진 시간만큼만 CPU를 사용합니다. 시간이 다 되면 하던 일을 멈추고 큐의 맨 뒤로 다시 줄을 섭니다. (선점형)
- 특징:
- 타임 슬라이스가 너무 크면: FCFS와 다를 게 없어집니다.
- 타임 슬라이스가 너무 작으면: 문맥 교환(Context Switch)이 너무 자주 일어나서 오버헤드가 커집니다.
- 비유: 친구들과 노래방에 가서 '1절만 부르기' 규칙을 정해 마이크를 계속 돌리는 것과 같습니다.
4. 최소 잔여 시간 우선 스케줄링 (SRT)
Shortest Remaining Time
SJF(짧은 것 먼저)와 RR(시간 제한)을 합친 방식입니다. "남은 시간이 가장 적은 녀석부터 먼저 처리하자"는 것입니다.
- 방식: 기본적으로 라운드 로빈처럼 동작하지만, 다음 프로세스를 고를 때 남은 작업 시간이 가장 적은 프로세스를 선택합니다. (선점형 SJF)
- 특징: 만약 실행 중인 프로세스보다 더 빨리 끝날 수 있는 새 프로세스가 들어오면, 바로 CPU를 빼앗아 새 프로세스에게 줍니다.
5. 우선순위 스케줄링 (Priority Scheduling)
모든 프로세스에 우선순위(점수)를 매기고, 점수가 높은 순서대로 실행하는 방식입니다.
- 특징: SJF나 SRT도 넓은 의미에서는 '작업 시간'을 우선순위로 둔 스케줄링의 일종입니다.
- 치명적 단점 (기아 현상, Starvation): 우선순위가 낮은 프로세스는 준비 큐에 아무리 오래 있어도 실행되지 못할 수 있습니다.
- 해결책 (에이징, Aging): 오랫동안 기다린 프로세스의 우선순위를 조금씩 높여주는 방법입니다. "너 너무 오래 기다렸으니 점수 좀 더 줄게"라고 하여 결국 실행되게 만듭니다.
6. 다단계 큐 스케줄링 (Multilevel Queue)
우선순위별로 아예 줄(큐)을 여러 개 만드는 방식입니다.
- 방식:
- 우선순위가 가장 높은 '상위 큐'에는 중요한 시스템 작업들이 줄을 섭니다.
- 우선순위가 낮은 '하위 큐'에는 덜 중요한 작업들이 줄을 섭니다.
- 각 큐마다 서로 다른 스케줄링 알고리즘(예: 상위 큐는 RR, 하위 큐는 FCFS)을 적용할 수 있습니다.
- 단점: 한번 특정 큐에 들어가면 다른 큐로 이동할 수 없습니다. 융통성이 부족하여 하위 큐의 기아 현상이 발생할 수 있습니다.
7. 다단계 피드백 큐 스케줄링 (Multilevel Feedback Queue)
Multilevel Feedback Queue (MFQ)
다단계 큐의 단점(이동 불가)을 해결한 가장 완성형에 가까운 스케줄링 방식입니다.
- 방식: 프로세스들이 큐 사이를 이동할 수 있습니다.
- 처음 프로세스가 들어오면 가장 높은 우선순위 큐에 넣습니다.
- 만약 거기서 할당된 시간을 다 쓰고도 안 끝나면(CPU 집중 프로세스), "너는 오래 걸리는구나" 하고 한 단계 아래 큐로 강등시킵니다.
- 반대로 낮은 큐에서 너무 오래 기다리면(기아 현상), 다시 상위 큐로 승격시켜줍니다(에이징).
- 장점: 짧은 작업은 빨리 끝내고, 긴 작업은 알아서 아래로 내려가며, 오래 기다린 작업은 챙겨주는 유연함을 가집니다. 현대 운영체제 CPU 스케줄링의 근간이 되는 모델입니다.
기록해야 (살아)남는다 !