CPU 스케줄링

프로세스 1편에서 스케줄러 종류(장기/중기/단기)까지 정리했는데, 그중 단기 스케줄러가 실제로 어떤 알고리즘으로 CPU를 할당할 프로세스를 고르는지 -> 즉, CPU 스케줄링에 대해서 정리해본다.

---

1. CPU 스케줄링이란

CPU 스케줄링이란 여러 프로세스가 CPU를 기다리는 상황에서, CPU를 어떤 프로세스에 할당할지 결정하는 과정이다.

이를 스케줄링 알고리즘을 통해 프로세스의 실행 순서를 결정한다.

---

2. CPU 스케줄링 성능 척도

성능을 보는 관점이 두 가지로 나뉜다. 시스템 입장과 프로그램(프로세스) 입장이다.

시스템 입장: CPU 하나로 최대한 많은 일을 시킬수록 좋다

• CPU 이용률(CPU Utilization): 전체 시간 중 CPU가 놀지 않고 일한 시간의 비율 → 높을수록 좋음
• 처리량(Throughput): 주어진 시간 동안 처리되는 프로세스 수 → 높을수록 좋음

 

프로그램 입장: 프로그램이 최대한 빨리 끝날수록 좋음

• 대기 시간(Waiting Time): Ready 상태에서 CPU를 기다린 총 시간 (= Ready Queue에 머문 시간) → 짧을수록 좋음
• 응답 시간(Response Time): Ready 상태의 프로세스에게 최초로 CPU가 할당되기까지 걸린 시간 → 짧을수록 좋음 (= "얼마나 빨리 반응이 오는가")
• 소요 시간(Turnaround Time): 프로세스가 CPU를 요청한 시점부터, 원하는 만큼의 CPU를 모두 사용하는 데 걸린 시간 → 짧을수록 좋음

 

정리하면, CPU 이용률·처리량은 높을수록, 대기·응답·소요 시간은 짧을수록 좋은 스케줄링 방식이다.

---

3. CPU Burst와 I/O Burst

프로세스는 실행되는 동안 CPU 작업과 I/O 작업을 교대로 반복하며 수행된다.

각각의 스케줄링 알고리즘의 동작 방식을 이해하기 위해선 아래 용어들에 대해 이해해야 한다.

• CPU Burst: 프로세스가 CPU를 사용해 계산·데이터 처리를 수행하는 시간
• I/O Burst: 프로세스가 I/O 장치를 사용해 데이터를 입출력하는 시간

CPU 스케줄링 알고리즘들은 대부분 이 CPU Burst 시간을 기준으로 어떤 프로세스에게 CPU를 줄지 판단한다.

---

4. 선점형 vs 비선점형

• 선점형(Preemptive): 실행 중인 프로세스에게서 CPU를 강제로 빼앗을 수 있음
• 비선점형(Non-preemptive): CPU를 강제로 빼앗지 않음. 한 번 CPU를 잡으면 자기가 끝내거나 스스로 반납할 때까지 계속 씀

---

5. 스케줄링 알고리즘

1. FCFS (First-Come First-Served)

• 비선점형
• 먼저 도착한 프로세스부터 CPU를 할당 
• 공정해 보이지만, 소요 시간이 긴 프로세스가 먼저 도착해버리면 뒤에 있는 프로세스들이 오래 대기하게 되어 전체적인 효율성이 떨어짐
• Queue 자료구조 생각하면 편함

 

2. SJF (Shortest-Job-First)

• 비선점형
• CPU Burst가 짧은 프로세스에게 먼저 CPU를 할당
• CPU Burst가 긴 프로세스는 계속 뒤로 밀려서 starvation(자원을 계속 못 받는 상태)이 생길 수 있음. 아무리 먼저 도착했어도, 자기보다 짧은 프로세스가 계속 들어오면 영영 순서가 안 옴

 

3. SRTF (Shortest-Remaining-Time-First)

• SJF와 유사하지만 선점형. 중간에 새로운 프로세스가 도착하면 그 시점에서 다시 스케줄링
• 현재 실행 중인 프로세스의 남은 CPU Burst 시간보다 더 짧은 CPU Burst를 가진 프로세스가 도착하면, 실행 중이던 프로세스는 CPU를 빼앗기고 다시 Ready Queue로 돌아감

 

4. Priority Scheduling

• 우선순위대로 CPU를 할당
• 선점형 방식: 더 높은 우선순위 프로세스가 도착하면 즉시 CPU를 빼앗김
• 비선점형 방식: 더 높은 우선순위 프로세스가 도착해도 일단 Ready Queue에서 대기
• 여기서도 starvation 문제가 생길 수 있어서 aging 기법을 사용. -> aging은 오래 기다린 프로세스일수록 우선순위를 점점 높여주는 방식 → 결국 "우선순위 + 대기 시간"이 판단 기준이 되는 셈

 

Round Robin (RR)

• 현대적인 방식으로써, 각 프로세스에게 동일한 크기의 CPU 할당 시간(time slice)을 줌
• 할당 시간이 지나면 그 프로세스는 Ready Queue의 맨 뒤로 가서 다시 자기 차례를 기다림
• 장점: 가장 빠른 응답 시간을 기대할 수 있음
• 주의점: 할당 시간이 너무 크면 사실상 FCFS처럼 동작해버리고, 너무 짧으면 문맥 교환(Context Switching)이 너무 자주 일어나서 오버헤드가 커짐 → 적절한 할당 시간 설정이 중요

 

Starvation 정리

우선순위가 낮은 프로세스가 장시간 동안 자원을 할당받지 못하는 상태. SJF, SRTF, Priority Scheduling처럼 "더 급한 애 먼저"를 판단 기준으로 삼는 알고리즘에서 공통으로 나올 수 있는 문제고, 그 해결책 중 하나가 위에서 본 aging이다.

---

6. 문맥 교환(Context Switching) 다시 보기

프로세스 1편에서 개념만 짚었던 컨텍스트 스위칭을, 스케줄링 알고리즘까지 학습하고 나면 단계별로 더 명확히 정리할 수 있다.

CPU가 현재 실행 중인 프로세스의 상태(Context)를 저장하고, 새로운 프로세스의 상태를 복구해서 실행을 전환하는 과정(이떄 활용하는 것이 PCB). 이는 여러 프로세스를 동시에 실행하려면 반드시 필요한 작업이다.

컨텍스트 스위칭 동작 4단계

1. 현재 프로세스 상태 저장: 실행 중이던 프로세스의 CPU 레지스터 값(프로그램 카운터, 스택 포인터 등)과 기타 실행 정보를 PCB에 저장
2. 새로운 프로세스 선택: 스케줄러가 Ready Queue에서 다음에 실행할 프로세스를 선택 (여기서 위에서 정리한 알고리즘들이 쓰임)
3. 새로운 프로세스 상태 복구: 선택된 프로세스의 PCB에 저장돼 있던 정보를 읽어, CPU 레지스터에 복구
4. 새로운 프로세스 실행

즉 PCB가 "누구의 상태를 저장/복구하는 저장소"였다면, 스케줄링 알고리즘은 "2단계에서 누구를 고를지" 결정하는 규칙이라고 이어서 이해하면 된다.

---

정리

CPU 스케줄링은 여러 프로세스 중 누구에게 CPU를 줄지 결정하는 과정이고, FCFS·SJF·SRTF·Priority·Round Robin 같은 알고리즘마다 "선점 여부"와 "판단 기준"이 다르다. 대부분의 알고리즘이 starvation 위험을 안고 있고, aging 같은 보완책이 함께 따라온다.