운영체제 - CPU 스케줄링

# 1. CPU 스케줄링이란

> Ready 상태의 프로세스 중 어떤 프로세스에게 CPU를 할당할지 결정하는 것
> 

## 1.1 스케줄링 목적

CPU 스케줄링의 목적은 모든 프로세스가 적절하고 공평하며 효율적으로 자원을 할당받는 것입니다.

- **공평성** : 프로세스 간 자원 배분이 공정해야 함.
- **효율성** : CPU가 유휴 상태가 되지 않도록 자원을 최대한 활용해야 함.
- **안정성** : 중요한 프로세스에 우선권을 부여하며, 시스템이 증가해도 안정적으로 작동해야 함.
- **확장성** : 추가적인 CPU나 메모리 자원이 생겼을 때 효과적으로 활용 가능해야 함.
- **반응 시간 보장** : 프로세스 요청에 적절한 시간 안에 응답해야 함.
- **무한 연기 방지** : 특정 프로세스가 무한정 대기하는 상황을 방지해야 함.

## 1.2 스케줄링 시 고려사항

### 선점형 vs 비선점형 스케줄링

### **선점형 스케줄링**

- 실행 중인 프로세스라도 운영체제가 CPU를 강제로 회수하여 다른 프로세스에 할당할 수 있음.
- 현대 운영체제에서 주로 사용됨.
- 처리 시간이 긴 프로세스의 CPU 독점을 방지할 수 있음.
- 하지만 **Context Switching**으로 인해 오버헤드가 발생할 수 있음.
- CPU 스케줄러가 스케줄링을 결정하는 시점:
    
    ```
    1) 실행(running) → 대기(waiting) 전환 시
    2) 실행(running) → 준비(ready) 전환 시
    3) 대기(waiting) → 준비(ready) 전환 시
    4) 종료(terminated) 시
    ```
    

### **비선점형 스케줄링**

- 실행 중인 프로세스가 자발적으로 종료될 때까지 CPU를 점유함.
- 강제로 프로세스를 중단하지 않음.
- Context Switching으로 인한 부하가 적음.
- 하지만 **프로세스 배치에 따라 효율성이 달라질 수 있음**.
- CPU 스케줄러가 스케줄링을 결정하는 시점:
    
    ```
    1) 실행(running) → 대기(waiting) 전환 시
    2) 종료(terminated) 시
    ```
    

### 프로세스 우선순위

| 우선순위 높음 |  | 우선순위 낮음 |
| --- | --- | --- |
| 커널 프로세스 | ↔ | 일반 프로세스 |
| 전면 프로세스 | ↔ | 후면 프로세스 |
| 대화형 프로세스 | ↔ | 일괄 처리 프로세스 |
| 입출력 집중 프로세스 | ↔ | CPU 집중 프로세스 |

# 2. 스케줄링 성능 척도

## 2.1 시스템 관점

- **CPU 이용률 (CPU Utilization)** : 전체 시간 중 CPU가 사용된 비율
- **처리량 (Throughput)** : 단위 시간당 처리된 프로세스 개수

## 2.2 사용자 관점

- **대기 시간 (Waiting Time)** : 프로세스가 Ready Queue에서 대기한 시간
- **응답 시간 (Response Time)** : 프로세스가 최초로 CPU를 얻기까지 걸린 시간
- **소요 시간 (Turnaround Time)** : 프로세스가 도착해서 종료될 때까지의 총 시간

# 3. 스케줄링 알고리즘

## 3.1 비선점형 스케줄

### 3.1.1 FCFS (First Come, First Served)


- 가장 먼저 요청한 프로세스에게 CPU를 할당하는 **선착순 방식**.
- 실행 시간이 긴 프로세스로 인해 전체 OS가 느려질 수 있음 → **Convoy Effect 발생 가능**.

### 3.1.2 SJF (Shortest Job First)


- 실행 시간이 가장 짧은 프로세스를 우선 실행.
- **평균 대기 시간이 짧음**.
- 하지만 긴 실행 시간이 필요한 프로세스가 무기한 대기할 가능성 있음 → **Starvation 발생 가능**.

### 3.1.3 우선순위 (Priority)


- 각 프로세스는 우선순위를 가지며, 우선순위가 높은 프로세스가 먼저 실행됨.
- **SJF의 경우 Starvation이 발생할 수 있는데, 이를 방지하기 위해 Aging(낮은 우선순위 프로세스의 우선순위를 점진적으로 상승시키는 기법)을 사용할 수 있음**.

## 3.2 선점형 **스케줄링**

### 3.2.1 RR (Round Robin)


- **현대 운영체제에서 가장 많이 사용하는 방식**.
- 각 프로세스에 **동일한 시간 할당량(Time Quantum)** 부여 → 해당 시간 동안만 CPU 사용 가능.
- **응답 시간이 빠름**.
- 하지만 **할당 시간이 길면 FCFS처럼 동작**하고, 너무 짧으면 오버헤드 발생 가능.

### 3.2.2 SRTF (Shortest Remaining Time First)


- 현재 실행 중인 프로세스보다 더 짧은 실행 시간이 필요한 프로세스가 들어오면 **기존 프로세스를 중단하고 새로운 프로세스를 실행**.
- 평균 대기 시간을 줄일 수 있음.
- 하지만 다음 프로세스의 **CPU 실행 시간을 예측하기 어려움**.

### 3.2.3 다단계 큐


- **우선순위에 따라 여러 개의 큐를 구성하여 프로세스를 분류**.
- 각 큐는 고유한 스케줄링 알고리즘을 가질 수 있음.
- **높은 우선순위 큐가 우선 실행되므로 낮은 우선순위 프로세스는 실행되지 않을 수도 있음** → Starvation 발생 가능.
- 큐 간 이동이 불가능하여 유연성이 낮음.
- **다단계 피드백 큐 (MLFQ, Multilevel Feedback Queue) - 보완 방식**
    - **다단계 큐의 단점(Starvation, 유연성 부족)을 해결한 방식**.
    - 프로세스가 낮은 우선순위 큐에서 높은 우선순위 큐로 이동 가능.

### +) 스케줄링 알고리즘 비교
| 알고리즘 | 선점 여부 | 우선순위 고려 | 장점 | 단점 |
| --- | --- | --- | --- | --- |
| **FCFS** | X | X | 구현이 간단함 | Convoy Effect 발생 가능 |
| **SJF** | X | O | 평균 대기 시간이 짧음 | Starvation 발생 가능 |
| **RR** | O | X | 반응 시간이 빠름 | Context Switching 오버헤드 |
| **SRTF** | O | O | 대기 시간을 줄일 수 있음 | CPU 실행 시간 예측 어려움 |
| **다단계 큐** | O | O | 다양한 프로세스 유형 지원 | 낮은 우선순위 프로세스가 무한 대기 가능 |
| **다단계 피드백 큐** | O | O | 유연성 증가, Starvation 해결 가능 | 알고리즘 복잡도 증가 |