CPU 스케쥴링

1. CPU 스케줄링의 기초

정의 및 중요성

• 운영체제가 여러 프로세스에게 공정하고 합리적으로 CPU 자원을 배분하는 과정이다.
• 스케줄링이 비효율적이면 자원 배분 불균형, 처리량 감소, 무질서 상태가 발생할 수 있다.

프로세스 우선순위

• 프로세스는 성격에 따라 입출력 집중 프로세스(I/O bound)와 CPU 집중 프로세스(CPU bound)로 나뉜다.
• 시스템 효율을 높이기 위해 입출력 장치와 CPU를 동시에 활용할 수 있도록 입출력 집중 프로세스에 더 높은 우선순위를 부여한다.
• 운영체제는 프로세스의 PCB(Process Control Block)에 기록된 우선순위를 바탕으로 스케줄링을 진행한다.

스케줄링 큐

• 준비 큐(Ready Queue)는 CPU를 할당받기 위해 대기하는 프로세스들이 모인 곳이다.
• 대기 큐(Waiting Queue)는 입출력 작업 등이 끝나기를 기다리는 프로세스들이 모인 곳이다.

선점형과 비선점형 스케줄링

• 선점형(Preemptive)은 프로세스가 CPU를 사용 중이더라도 운영체제가 강제로 빼앗을 수 있는 방식이며, 문맥 교환 오버헤드가 크지만 반응성이 좋다.
• 비선점형(Non-preemptive)은 프로세스가 스스로 CPU를 반납할 때까지 기다리는 방식이며, 오버헤드가 적지만 긴 작업이 CPU를 독점하면 무한정 기다리는 비효율이 발생한다.

---

2. 스케줄링 알고리즘

FCFS (선입 선처리)

• 준비 큐에 먼저 도착한 순서대로 처리하는 비선점형 스케줄링이다.
• 실행 시간이 긴 프로세스가 먼저 도착하면 뒤의 짧은 프로세스들이 무작정 기다려야 하는 호위 효과(Convoy Effect)가 발생한다.

SJF (최단 작업 우선)

• CPU 이용 시간이 가장 짧은 프로세스부터 먼저 실행하는 방식이다.
• 평균 대기 시간을 최소화할 수 있으나 현실에서는 프로세스의 실행 시간을 정확히 예측하기 어렵다는 한계가 있다.

RR (라운드 로빈)

• 선입 선처리 방식에 타임 슬라이스(Time Slice)라는 시간제한 개념을 더한 선점형 방식이다.
• 정해진 시간이 지나면 CPU를 빼앗기고 큐의 맨 뒤로 이동하며, 타임 슬라이스의 크기에 따라 성능이 크게 좌우된다.

SRT (최소 잔여 시간 우선)

• 최단 작업 우선(SJF)과 라운드 로빈(RR)의 장점을 결합한 선점형 스케줄링이다.
• 정해진 시간만큼 CPU를 사용한 후, 남아있는 작업 시간이 가장 짧은 프로세스에게 CPU를 넘겨준다.

우선순위 스케줄링

• 부여된 우선순위가 가장 높은 프로세스부터 순서대로 실행한다.
• 우선순위가 낮은 프로세스는 영원히 실행되지 못하는 기아(Starvation) 현상이 발생할 수 있다.
• 이를 방지하기 위해 대기 시간에 비례해 우선순위를 높여주는 에이징(Aging) 기법을 활용한다.

다단계 큐 (Multilevel Queue)

• 우선순위별로 여러 개의 큐를 두어 관리하며, 각 큐마다 서로 다른 스케줄링 알고리즘을 적용할 수 있다.
• 단, 프로세스가 한 번 특정 큐에 배정되면 다른 큐로 이동할 수 없다는 한계가 있다.

다단계 피드백 큐 (Multilevel Feedback Queue)

• 다단계 큐의 한계를 극복하기 위해 프로세스들이 큐 사이를 자유롭게 이동할 수 있도록 만든 방식이다.
• CPU를 오래 사용하는 프로세스는 우선순위가 낮은 큐로 강등되고, 대기 시간이 길어지면 에이징 기법으로 우선순위를 다시 높인다.
• 현대 운영체제에서 가장 보편적으로 사용하는 스케줄링 알고리즘이다.