스케줄링 알고리즘의 종류

다양한 스케줄링 알고리즘

운영체제에서 프로세스에 CPU 등의 자원을 할당할 때는 여러 스케줄링 알고리즘을 사용한다. 각 알고리즘은 프로세스들을 어떤 순서로 우선 실행시킬지 결정하는 전략을 가지고 있으며, 실행 환경이나 요구사항(반응 속도, 처리량 등)에 따라 그 장단점이 달라진다. 이번 장에서는 대표적인 스케줄링 알고리즘들을 간략히 살펴본다.

 

---

1. 선입 선처리 스케줄링(FCFS: First Come First Served)

1.1 개념

• 준비 큐(Ready Queue)에 도착한 순서대로 프로세스에 CPU를 할당하는 비선점형 스케줄링 방식이다.
• 단순하고 이해하기 쉽지만, CPU 사용 시간이 긴 프로세스가 먼저 오면 호위 효과(Convoy Effect) 가 발생해 이후 프로세스들이 장시간 대기하는 문제가 있다.

_{(그림 출처: 혼자 공부하는 컴퓨터 구조 + 운영체제)}

1.2 특징 요약

• 장점: 구현이 쉽고 공정해 보인다(도착 순으로 처리).
• 단점: 긴 CPU 버스트를 가진 프로세스가 먼저 오면, 뒤에 온 짧은 프로세스가 오래 대기(호위 효과).

 

---

2. 최단 작업 우선 스케줄링(SJF: Shortest Job First)

2.1 개념

• 준비 큐에 있는 프로세스 중 CPU 이용 시간이 가장 짧은 프로세스부터 먼저 실행한다.
• 비선점형 방식으로 구현된 경우가 일반적이지만, 선점형 버전(최소 잔여 시간 우선, SRTF)도 존재한다.

_{(그림 출처: 혼자 공부하는 컴퓨터 구조 + 운영체제)}

2.2 특징 요약

• 장점: CPU 사용 시간이 짧은 프로세스를 빨리 끝낼 수 있어 평균 대기 시간을 줄일 수 있다.
• 단점: 새로 오는 프로세스의 CPU 사용 시간을 정확히 예측하기 어렵다.
• 문제점: CPU 사용 시간이 긴 프로세스가 기아(Starvation) 상태에 빠질 수 있다(짧은 프로세스가 계속 선점).

 

---

3. 라운드 로빈 스케줄링(Round Robin)

3.1 개념

• 선입 선처리(FCFS) 방식에 타임 슬라이스(Time Quantum) 개념을 추가한 선점형 스케줄링이다.
• 프로세스는 정해진 짧은 시간(q 밀리초) 동안 CPU를 사용하고, 시간이 끝나면 문맥 교환이 발생해 다음 프로세스로 넘어간다.
• 남은 작업이 있다면 준비 큐 뒤에 다시 들어가 차례를 기다린다.

_{(그림 출처: 혼자 공부하는 컴퓨터 구조 + 운영체제)}

3.2 타임 슬라이스가 중요한 이유

• 너무 크면: 사실상 FCFS와 다를 바 없어 호위 효과 발생.
• 너무 작으면: 문맥 교환(Context Switch) 비용이 증가, 오버헤드가 커져 CPU가 스위칭에만 많은 시간 낭비.

 

---

4. 최소 잔여 시간 우선 스케줄링(SRTF: Shortest Remaining Time First)

4.1 개념

• SJF(최단 작업 우선) 과 Round Robin(선점형) 을 합친 형태.
• 정해진 타임 슬라이스마다, 현재 남은 CPU 시간이 가장 짧은 프로세스에게 CPU를 할당한다(혹은 새 프로세스가 도착할 때마다 재결정).
• 선점형 최단 작업 우선으로 이해할 수 있다.

4.2 특징 요약

• 장점: 평균 대기 시간을 최소화하는 효과가 큼(짧은 작업 우선).
• 단점: 남은 시간 추정이 필요하고, 긴 작업이 계속 뒤로 밀려 기아 가능성이 높다.

 

---

5. 우선순위 스케줄링(Priority Scheduling)

5.1 개념

• 각 프로세스에 우선순위(Priority)를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 CPU를 할당하는 방식.
• 선점형과 비선점형 모두 가능.

_{(그림 출처: 혼자 공부하는 컴퓨터 구조 + 운영체제)}

5.2 기아(Starvation)와 에이징(Aging)

• 문제: 우선순위가 낮은 프로세스는 계속 후순위로 밀려 기아(영원히 실행되지 않음) 상태가 될 수 있다.
• 해결: 오랫동안 대기 중인 프로세스의 우선순위를 점차 높여 주는 에이징(Aging) 기법을 사용한다.

 

---

6. 다단계 큐 스케줄링(Multilevel Queue)

6.1 개념

• 우선순위별(혹은 다른 분류 기준별)로 준비 큐를 여러 개 두고, 우선순위가 높은 큐부터 우선적으로 스케줄링하는 방식.
• 큐마다 서로 다른 스케줄링 알고리즘을 적용할 수도 있다.
• 예: 입출력 집중 프로세스(우선순위 높음) vs. CPU 집중 프로세스(우선순위 낮음)로 큐를 분리.

_{(그림 출처: 혼자 공부하는 컴퓨터 구조 + 운영체제)}

6.2 특징

• 장점: 프로세스 종류나 특성에 맞는 맞춤형 스케줄링 가능(예: 대화형 프로세스 vs. 배치 프로세스).
• 단점: 한 큐에 속하면 우선순위나 분류가 변경되지 않아, 기아 문제 등이 발생할 수 있다.

 

---

7. 다단계 피드백 큐 스케줄링(Multilevel Feedback Queue)

7.1 개념

• 다단계 큐에서 프로세스가 다른 큐로 이동할 수 있게 한 개선된 방식.
• 새 프로세스는 일단 높은 우선순위 큐에 들어가고, CPU를 일정 시간만 써도 완료되지 않으면 더 낮은 우선순위 큐로 내려간다.
• 반대로, 오랫동안 낮은 우선순위 큐에서 대기 중인 프로세스의 우선순위를 에이징으로 끌어올릴 수도 있다.

_{(그림 출처: 혼자 공부하는 컴퓨터 구조 + 운영체제)}

7.2 특징

• CPU를 많이 쓰는 프로세스는 점차 낮은 우선순위 큐로 이동
• CPU를 적게 쓰는(짧은 작업) 프로세스는 높은 우선순위 큐에서 빨리 끝낼 수 있다
• 기아 방지: 오래 대기하면 우선순위 상승(에이징) 으로 상위 큐로 이동 가능
• 현대 OS에서 매우 일반적으로 사용되는 스케줄링 방식

_{(그림 출처: 혼자 공부하는 컴퓨터 구조 + 운영체제)}

 

---

8. 정리

1. FCFS(선입 선처리)
   • 가장 간단하나 호위 효과 발생 가능. 비선점형.
2. SJF(최단 작업 우선) / SRTF(최소 잔여 시간 우선)
   • 짧은 작업 먼저 처리, 평균 대기 시간 최소화. 긴 작업 기아 문제 발생 가능.
3. 라운드 로빈(Round Robin)
   • 타임 슬라이스 기반으로 선점형 동작. 공정하나 슬라이스 설정이 중요.
4. 우선순위 스케줄링
   • 높은 우선순위부터 실행. 기아 문제가 있고, 에이징으로 해결 가능.
5. 다단계 큐(Multilevel Queue)
   • 큐를 여러 개 두어 우선순위별 처리. 프로세스가 다른 큐로 이동 불가.
6. 다단계 피드백 큐(Multilevel Feedback Queue)
   • 프로세스가 큐 간 이동 가능, CPU 많이 쓰면 우선순위 낮춤, 오래 대기하면 우선순위 높임.
   • 현대 OS에서 매우 일반적.

각 알고리즘은 특정 목표(예: 짧은 응답 시간, 높은 처리량, 공정성 등)에 맞춰 선택되고, 실제 운영체제는 종종 둘 이상의 기법(예: 우선순위 + 라운드 로빈 + 다단계 피드백) 등을 혼합하여 사용하기도 한다.

 

---

참고 자료

• 혼자 공부하는 컴퓨터 구조 + 운영체제
• Operating System Concepts (A. Silberschatz, P.B. Galvin, G. Gagne)
• Modern Operating Systems (A.S. Tanenbaum, H. Bos)