CPU 스케줄링 알고리즘

개요

CPU 스케줄링(CPU Scheduling)은 운영체제에서 프로세스가 CPU를 사용할 수 있도록 순서를 결정하는 핵심 기술이다. 다중 프로세스 환경에서는 CPU 자원을 효율적으로 배분하여 성능을 최적화해야 하며, 이를 위해 다양한 CPU 스케줄링 알고리즘이 사용된다. 본 글에서는 CPU 스케줄링의 개념과 주요 알고리즘, 평가 기준 및 활용 사례를 살펴본다.

---

1. CPU 스케줄링이란?

CPU 스케줄링은 여러 프로세스가 동시에 실행될 때 CPU를 어떤 프로세스가 먼저 사용할지 결정하는 작업이다. 운영체제는 **스케줄러(Scheduler)**를 통해 프로세스를 관리하며, 최적의 실행 순서를 결정한다.

CPU 스케줄링의 목적:

• CPU 활용률 극대화
• 프로세스 응답 시간(Response Time) 최소화
• 대기 시간(Waiting Time) 감소
• 공정성(Fairness) 유지
• 시스템 처리량(Throughput) 최적화

CPU 스케줄러의 종류:

• 단기 스케줄러(Short-term Scheduler): 실행할 프로세스를 CPU에 할당하는 역할
• 중기 스케줄러(Medium-term Scheduler): 메모리에서 일시적으로 프로세스를 제거(스왑)하여 자원 최적화 수행
• 장기 스케줄러(Long-term Scheduler): 새로운 프로세스를 시스템에 추가하여 실행 여부 결정

---

2. CPU 스케줄링 알고리즘 종류

CPU 스케줄링 알고리즘은 크게 **비선점형(Non-Preemptive)**과 선점형(Preemptive) 알고리즘으로 나뉜다.

알고리즘 유형	설명
비선점형(Non-Preemptive)	프로세스가 CPU를 점유하면 완료될 때까지 다른 프로세스가 선점할 수 없음
선점형(Preemptive)	실행 중인 프로세스가 일정 조건에서 CPU를 선점당할 수 있음

1) 비선점형 스케줄링 알고리즘

1. FCFS(First-Come, First-Served, 선입선출)
   • 먼저 도착한 프로세스부터 실행
   • 단순하지만 대기 시간이 길어질 수 있음 (Convoy Effect 문제 발생)
2. SJF(Shortest Job First, 최단 작업 우선)
   • 실행 시간이 가장 짧은 프로세스를 먼저 실행
   • 평균 대기 시간이 짧아지지만, 긴 프로세스는 계속 대기할 수 있음 (기아 현상 발생 가능)
3. HRRN(Highest Response Ratio Next, 최고 응답 비율 우선)
   • (대기 시간 + 실행 시간) / 실행 시간 값을 기준으로 높은 순서대로 실행
   • 기아 현상을 방지하면서도 평균 대기 시간을 최적화

2) 선점형 스케줄링 알고리즘

1. RR(Round Robin, 라운드 로빈)
   • 각 프로세스에 동일한 CPU 시간(Time Quantum) 할당
   • 공정성을 보장하지만 짧은 타임 슬라이스에서는 컨텍스트 스위칭 비용 증가
2. SRTF(Shortest Remaining Time First, 최단 남은 시간 우선)
   • SJF의 선점형 버전으로, 남은 실행 시간이 가장 짧은 프로세스가 우선 실행됨
   • 평균 대기 시간이 짧아지지만, 문맥 전환(Context Switching) 비용이 증가할 수 있음
3. Priority Scheduling(우선순위 스케줄링)
   • 프로세스마다 우선순위를 부여하고, 우선순위가 높은 프로세스부터 실행
   • 낮은 우선순위 프로세스가 무한 대기하는 기아 현상(Starvation) 발생 가능
   • 해결책: **노화 기법(Aging)**을 적용하여 오래된 프로세스의 우선순위를 점진적으로 증가
4. MLQ(Multi-Level Queue, 다단계 큐 스케줄링)
   • 프로세스를 여러 개의 큐로 나누어 각 큐에 서로 다른 스케줄링 알고리즘 적용
   • 예: 시스템 프로세스는 RR, 사용자 프로세스는 FCFS 방식 적용 가능
5. MLFQ(Multi-Level Feedback Queue, 다단계 피드백 큐 스케줄링)
   • MLQ의 확장 버전으로, 프로세스가 실행되면서 우선순위가 동적으로 변함
   • 대기 시간이 길어지면 상위 우선순위로 이동하여 기아 현상 방지

---

3. CPU 스케줄링 알고리즘 평가 기준

CPU 스케줄링 알고리즘의 성능을 평가하는 주요 기준은 다음과 같다.

평가 기준	설명
CPU 활용률(CPU Utilization)	CPU가 실제로 작업을 수행하는 시간 비율
처리량(Throughput)	일정 시간 동안 완료된 프로세스의 수
대기 시간(Waiting Time)	프로세스가 실행을 기다린 총 시간
응답 시간(Response Time)	프로세스가 요청된 후 처음 실행될 때까지 걸리는 시간
턴어라운드 타임(Turnaround Time)	프로세스가 시스템에 제출된 후 완료될 때까지 걸리는 시간

---

4. CPU 스케줄링 활용 사례

1. 운영체제(OS) 프로세스 관리: Windows, Linux, Unix 등의 운영체제에서 프로세스 실행 순서를 최적화
2. 클라우드 및 데이터센터: 서버 가상화 및 클라우드 환경에서 리소스 효율성 극대화
3. 실시간 시스템(Real-Time Systems): 자동차 제어 시스템, 의료 장비 등의 실시간 응답 요구 환경에서 적용
4. 슈퍼컴퓨터 및 고성능 컴퓨팅(HPC): 대규모 연산을 수행하는 환경에서 최적의 성능 유지

---

결론

CPU 스케줄링 알고리즘은 운영체제에서 프로세스를 효율적으로 실행하기 위해 필수적인 요소이다. 다양한 스케줄링 기법이 존재하며, 시스템의 목적과 환경에 따라 적절한 알고리즘을 선택해야 한다. 최신 컴퓨팅 환경에서는 **다단계 피드백 큐(MLFQ)**와 같은 동적 스케줄링 기법이 주로 활용되며, 클라우드 및 가상화 환경에서도 최적의 CPU 자원 관리를 위한 연구가 지속되고 있다.