---
description: CPU 스케줄링
---

# Week3 CPU Scheduling

<details>

<summary>참고: 프로세스 스케줄링 != CPU 스케줄링</summary>

프로세스 스케줄링은 CPU 스케줄링의 상위 개념.

#### 비유로 설명:

* **프로세스 스케줄링**은 회사에서 **직원들을 각각의 회의실(또는 컴퓨터)로 배치하는 일**입니다. 어떤 직원이 어떤 회의실에서 일할지를 정하는 과정입니다.
* **CPU 스케줄링**은 특정 회의실(또는 컴퓨터)에 들어온 **직원들 중에서 누가 먼저 발표(또는 작업)를 할지를 정하는 일**입니다.

프로세스 스케줄링 종류:

* I/O 스케줄링
* 메모리 스케줄링
* 네트워크 스케줄링
* CPU 스케줄링

</details>



## 기아 상태가 뭔가요?

* 우선순위 기반 스케줄링 시스템에서 **우선순위가 낮은 프로세스**가 **계속해서 자원을 할당받지 못하는 상태**



## 기아 상태를 어떻게 해결할 수 있나요?

* **에이징(Aging)** 기법: 오랫동안 자원을 할당받지 못한 프로세스의 **우선순위를 점진적으로 증가**시
* 라운드 로빈: 공정한 CPU 사용 기회



## CPU 스케줄링에 대해 설명해주세요.

<div data-full-width="true"><figure><img src="https://2804243633-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FfV6clXG953LqFieNgWUf%2Fuploads%2Forj6AsZqdi6KBYN32jzK%2Fimage.png?alt=media&#x26;token=1b9c315d-8977-40ba-b82a-6498d9610106" alt=""><figcaption></figcaption></figure></div>

* **시스템의 CPU 자원을 효율적으로 관리**하고 **프로세스의 성능을 극대화**하기 위해, 여러 프로세스 중에서 **어떤 프로세스가 CPU를 사용할지 결정하는 과정**
* **처리량(Throughput)**&#xC744; 극대화 **응답시간(Response Time)** 최소화, **CPU 자원의 효율적 사용**
* FCFS, SJF, 라운드 로빈, 우선순위 스케줄링



## 스케줄러의 종류는 무엇이 있나요?

단기 스케줄러: CPU에서 어떤 프로세스를 실행할지 결정

* Ready 상태에 있는 프로세스들 중에서 다음 프로세스 실행 결정(CPU 스케줄링 알고리즘)

중기 스케줄러: 메모리에서 프로세스를 스왑 인/아웃하여 메모리 자원 관리

* 메모리 관리 역할. 프로세스가 과부하 상태 또는 메모리 부족일 경우, 프로세스를 일시적으로 디스크로 **swap-out** 하는 역할. 자원이 충분해지면 다시 **swap-in**

장기 스케줄러: 디스크에 있는 작업을 메모리로 가져와 실행할지 결정하는 역할

* 새로운 프로세스를 시스템에 진입시킬지 여부를 결정.
* 다중 프로그래밍 정도(한번에 메모리에 적재되는 프로세스 수)를 관리



## 선점형 스케줄링과 비선점형 스케줄링의 차이

비선점형 스케줄링(FCFS, SJF)

* 프로세스가 실행되는 도중에 **다른 프로세스가 CPU를 강제로 빼앗을 수 없습니다**.
* 컨텍스트 스위칭: 적음
* 응답시간: 느림

선점형 스케줄링(라운드 로빈, SRTF-Shortest Remain Time First)

* **현재 실행 중인 프로세스가 CPU를 점유하고 있더라도**, **더 높은 우선순위**를 가진 프로세스가 도착하면 **강제로 CPU를 빼앗길 수 있는 방식**
* **컨텍스트 스위칭: 많음**
* **응답시간: 실시간**



## 선입선출 스케줄링(FCFS)에 대해 설명해주세요.

* 비선점형 스케줄링 알고리즘 (작업을 완료할 때까지 CPU를 독점)
* 장 먼저 대기 큐에 도착한 프로세스부터 순서대로 CPU를 할당
* 단점: Convoy 효과. CPU 사용시간이 긴 프로세스가 먼저 도착하면 짧은 CPU 작업을 가진 프로세스들이 긴 시간을 대기.



## 최단 작업 우선 스케줄링(SJF)

* 비선점형 스케줄링 알고리즘 (작업을 완료할 때까지 CPU를 독점)
* **CPU 실행 시간이 가장 짧은 프로세스**를 먼저 실행
* 단점으로는 CPU 실행 시간을 미리 알아야 하고, Starvation 현상이 발생할 수 있음.



## 최소 잔류 시간 우선 스케줄링(SRTF)

* 선점형 스케줄링 알고리즘
* **현재 CPU에서 실행 중인 프로세스의 남은 실행 시간**과 **새롭게 도착한 프로세스의 실행 시간을 비교**하여, **남은 시간이 더 짧은 프로세스**가 있으면 현재 작업 중인 프로세스의 CPU를 선점하여 처리하는 방식
* 장점으로는 Convoy효과가 발생하지 않고 평균 대기 시간을 최소화
* 단점으로는 CPU 실행 시간 예측이 어렵다는 것, Starvation 효과, 컨텍스트 스위칭이 자주 발생



## 우선순위 스케줄링에 대해 설명해주세요

* 선점형, 비선점형 모두 가능.
* **프로세스에 우선순위를 부여**하고, **우선순위가 높은 프로세스**가 먼저 CPU를 할당받는 스케줄링 방식
* 우선순위는 CPU 실행시간/ 프로세스 중요도/ 메모리 사용량에 따라 결정
* 장점으로는 응답시간 최소화, 다양한 스케줄링 정책 적용 가능
* 단점으로는 Starvation현상 -> 에이징 기법으로 해결
* 선점형일 경우 높은 컨텍스트 스위칭 비용



## 라운드 로빈 스케줄링에 대해 설명해주세요.

* 선점형 스케줄링 알고리즘
* **정해진 시간(Time Quantum, 타임 퀀텀)** 동안만 CPU를 사용하고, **시간이 지나면 강제로 CPU를 반납**한 후 대기 큐의 맨 뒤로 이동. 공평하게 CPU를 사용할 기회
* 타임 퀀텀에 따라 응답시간이 짧아지거나 프로세스가 CPU를 더 오래 사용(비선점형에 가까워짐)
* 장점으로는 기아 현상이 발생하지 않고, 대화형 시스템에 적합합니다.
* 단점으로는 컨텍스트 스위칭 오버헤드가 발생할 수 있고, 타임 퀀텀 설정이 중요합니다.

<details>

<summary>Time Quantum을 정하는 방식</summary>

프로세스들의 평균 CPU 버스트 시간 기반 설정

응답 시간 목표 기반 설정

컨텍스트 스위칭 오버헤드 고려

동적 타임 퀀텀 설정(Dynamic Time Quantum)

* **프로세스의 우선순위**나 **현재 시스템 부하**에 따라 타임 퀀텀이 짧아지거나 길어질 수 있습니다.
* 예시: **CPU 사용량이 높은 프로세스**에게 더 긴 타임 퀀텀을 부여하거나, 시스템 부하가 커지면 타임 퀀텀을 줄여 많은 프로세스가 번갈아 실행되도록 조정할 수 있습니다.

</details>



## 멀티 레벨 큐 스케줄링이 뭔가요?

* **여러 개의 큐**를 사용하여 **다양한 우선순위를 가진 프로세스들을 그룹으로 나누어** 각각의 큐에서 스케줄링하는 방식
* **프로세스의 특성에 따라** 서로 다른 큐에 배정하고, **각 큐에 대해 다른 스케줄링 알고리즘**을 적용
* **전위 큐(Foreground Queue)**: 일반적으로 **대화형 프로세스**(응답 시간이 중요한 프로세스)가 들어가는 큐로, 라운드 로빈(Round Robin)과 같은 **선점형 스케줄링**이 적용됩니다.
* **후위 큐(Background Queue)**: **배치 작업**이나 우선순위가 낮은 작업이 들어가는 큐로, FCFS(First-Come, First-Served)와 같은 **비선점형 스케줄링**이 적용될 수 있습니다.
* 장점으로는 다양한 유형에 맞는 스케줄링으로 유연하게 관리 가능
* 단점으로는 각 큐의 알고리즘에 따른 기아현상 발생 가능 -> 에이징 기법으로 해결
* 단점으로 큐 간 이동 불가. 프로세스의 특성이 변해도 다른 큐로 이동 불가

큐 간에도 스케줄링이 존재.

* 우선순위 기반
* 타임 슬라이드(타임 퀀텀)
* 에이징 기법



## 멀티 레벨 피드백 큐 스케줄링에 대해 설명해주세요.

"**프로세스가 계속해서 동일한 큐에 머무는 것이 아니라**, **CPU 사용 패턴에 따라 큐 사이를 이동**한다는 점"

* 여러 개의 **우선순위 큐**를 사용하여 **프로세스의 상태나 CPU 사용 패턴에 따라** 프로세스가 **다른 큐로 이동할 수 있는** 스케줄링 방식
* **동적인 스케줄링 알고리즘**으로, 각 프로세스의 **실행 시간과 우선순위**에 따라 **다른 큐로 재배치**

<details>

<summary>Example</summary>

* **3개의 우선순위 큐**가 있습니다:
  * **큐 1**: **가장 높은 우선순위**, 타임 퀀텀 5ms (대화형 작업)
  * **큐 2**: **중간 우선순위**, 타임 퀀텀 10ms (중간 정도의 CPU 사용량 작업)
  * **큐 3**: **가장 낮은 우선순위**, 타임 퀀텀 20ms (긴 배치 작업)
* **4개의 프로세스**가 있습니다:
  * **P1**: 도착 시간 0ms, 실행 시간 16ms
  * **P2**: 도착 시간 1ms, 실행 시간 6ms
  * **P3**: 도착 시간 2ms, 실행 시간 10ms
  * **P4**: 도착 시간 3ms, 실행 시간 25ms

**1단계: 처음 도착한 프로세스 처리**

* **시간 0ms**:
  * P1이 도착합니다. \*\*큐 1(가장 높은 우선순위)\*\*에 할당되어 CPU를 받습니다.
  * P1은 5ms 동안 실행되고 타임 퀀텀을 모두 소모하지만, \*\*전체 실행 시간(16ms)\*\*을 완료하지 못합니다.
  * **남은 시간**은 11ms입니다.
  * P1은 \*\*큐 2(중간 우선순위)\*\*로 이동합니다.

**2단계: 새로운 프로세스 도착**

* **시간 1ms**:
  * P2가 도착합니다. **큐 1**에 들어갑니다.
  * P1이 **큐 2**로 이동한 상태이므로, P2는 CPU를 할당받습니다.
  * P2는 5ms의 타임 퀀텀 동안 실행되고 **6ms 중 5ms를 사용**했으므로, 남은 **1ms**가 남습니다.
  * **큐 1**에서 계속 대기하지 않고, **큐 2**로 이동합니다.

**3단계: 추가 프로세스 도착**

* **시간 2ms**:
  * P3가 도착하여 **큐 1**에 들어갑니다.
  * P3가 CPU를 할당받고, 5ms 동안 실행되어 **전체 10ms 중 5ms**를 사용합니다.
  * 남은 시간은 **5ms**이며, P3도 **큐 2**로 이동합니다.

**4단계: 또 다른 프로세스 도착**

* **시간 3ms**:
  * P4가 도착하여 **큐 1**에 들어갑니다.
  * P4는 5ms 동안 실행되어 **25ms 중 5ms**를 사용합니다.
  * 남은 **20ms**를 완료하기 위해 **큐 2**로 이동합니다.

**5단계: 큐 2의 처리**

* **시간 6ms\~10ms**:
  * **큐 1**에 남아있는 프로세스가 없기 때문에, **큐 2**에서 처리 시작됩니다.
  * P1이 먼저 **큐 2**에서 CPU를 할당받습니다. **타임 퀀텀 10ms**로 실행되고 남은 11ms 중 **10ms를 모두 사용**합니다.
  * P1은 이제 **남은 시간이 1ms**이므로, \*\*큐 3(가장 낮은 우선순위)\*\*로 이동합니다.

**6단계: 계속되는 큐 2 처리**

* **시간 11ms\~20ms**:
  * **큐 2**에서 P2가 다시 CPU를 받습니다. P2는 **남은 1ms**만 남아 있었으므로, 실행을 마치고 종료됩니다.
  * 이후 P3가 CPU를 받습니다. P3는 5ms를 더 실행하여 **10ms를 모두 완료**하고 종료됩니다.
  * 마지막으로 P4가 CPU를 받습니다. **큐 2**에서 10ms를 사용해 남은 20ms 중 **10ms를 완료**합니다.
  * P4는 남은 10ms로 **큐 3**으로 이동합니다.

**7단계: 큐 3 처리**

* **시간 21ms\~30ms**:
  * **큐 3**에서 가장 먼저 도착한 P1이 **남은 1ms**를 처리하여 종료됩니다.
  * 이후 P4가 CPU를 할당받아 **남은 10ms**를 처리하고 종료됩니다.

#### **최종 프로세스 완료 시간**:

* **P1**: 22ms에 종료
* **P2**: 12ms에 종료
* **P3**: 20ms에 종료
* **P4**: 30ms에 종료

</details>

"큐3이 실행되다가 큐1에 새로운 프로세스가 도착하면 큐3의 타임 슬라이스가 끝나면 큐1의 프로세스를 실행하고, 큐1의 프로세스의 타임슬라이스가 끝나면 큐2로 가게되고, 큐1의 프로세스가 없으면 큐2를 실행한뒤에 큐3으로 배치"
