> For the complete documentation index, see [llms.txt](https://sois-organization.gitbook.io/today-i-learned/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://sois-organization.gitbook.io/today-i-learned/undefined-2/03.-cpu.md).

# CPU 스케줄링

## cpu 스케줄링 개요

### 컴퓨터 자원의 분류

1. 필수장치 : CPU, 메모리 등
2. 주변장치 : 하드디스크, 키보드, 마우스 등

### CPU (필수장치)의 개요

* 프로그램이 실행되면, 메모리에 프로세스가 생성된다. 또한 그 프로세스 안에는 1개 이상의 쓰레드가 존재한다.
* 프로세스는 CPU를 차지하기 위해 운영체제의 명령을 기다린다.
* CPU 스케줄러 = 운영체제가 모든 프로세스에게 CPU를 할당 및 해제하는 과정
* 고려사항

  * 어떤 프로세스에게 CPU 사용권을 주어야하는가?
  * CPU를 할당받은 프로세스가 얼마의 시간동안 사용해야하는가?

  ⇒ 컴퓨터의 성능에 큰 영향을 끼친다.

### 용어

* CPU Burst : CPU를 할당받아 실행하는 작업
* I/O Burst : 입출력 작업

***

## CPU 스케줄러의 동작

### 프로세스 상태

* 총 5가지의 상태로 구분할 수 있다.

  ![Untitled](https://s3-us-west-2.amazonaws.com/secure.notion-static.com/a645a689-3637-46c2-97f4-ab1599c9646e/Untitled.png)

### 다중큐

* 프로세스 상태 중, 프로세스가 대기하는 **준비상태와 대기상태는 큐로 관리**한다.
  * Running → Ready : 프로세스의 우선순위를 보고, 준비 큐에 넣는다.
  * Runnign → Waiting : I/O 종류에 따라 분류된 큐에 넣는다. (HDD, LAN, 키보드 등)
* 큐에 프로세스가 들어가는 것이 아니라, PCB가 들어간다. (프로세스 정보가 저장된 것)

### 정리

* CPU 스케줄러는 준비상태의 다중큐를 참조해서 실행시킬 프로세스들을 결정한다.
* I/O 작업이 발생하면, I/O로 분류된 큐를 참조해 스케줄링을 한다.

***

## 스케줄링 목표

1. 리소스 사용률 극대화
   * CPU, I/O Device의 사용률을 극대화한다.
2. 오버헤드 최소화
   * 스케줄링을 위한 계산이 너무 복잡하거나, 컨텍스트 스위칭을 너무 자주해서는 안 된다.
   * 이러한 오버헤드를 최소화한다.
3. 공평성
   * 모든 프로세스에게 공평하게 할당되어야한다.
   * 시스템에 따라서 공평의 의미는 달라질 수 있다.
     * 자율주행 시스템 → 안전에 이유로 자율주행 관련 프로세스가 더 많은 cpu 시간을 가져가는 것이 공평하다.
4. 처리량
   * 같은 시간 내에 더 많은 작업을 처리한다.
5. 대기시간
   * 작업 요청 후, 실제 작업이 이루어지기 전까지 대기 시간이 짧아야한다.
6. 응답시간
   * 대화형 시스템에서 사용자의 요청에 빨리 반응해야한다.

* 이러한 목표들은 서로 상반되는 상황이 존재한다.
  * 처리량 vs 응답시간

    처리량이 높으려면, 하나의 프로세스에 CPU 할당 시간이 길어야하며, 응답시간이 짧으려면 각각의 CPU 할당 시간이 짧아야한다. ⇒ 시스템에 따라 결정된다.

***

## CPU 스케줄링 알고리즘

### CPU 스케줄링의 성능

* cpu 스케줄링의 성능 = 프로세스의 평균 대기시간
  * 여러개의 프로세스가 실행될 대, 모든 프로세스가 실행되기까지의 평균 대기시간을 의미한다.
  * 예) 프로세스 1 = 25초, 프로세스 2 = 5초, 프로세스3 = 4초라고 가정한다.

    1→2→3 으로 실행시 : (0 + 25 + 30) / 3

    3→2→1 으로 실행시 : (0 + 4 + 9) / 3

### FIFO 알고리즘

* First in First out의 약자로, 먼저 들어온 프로세스를 먼저 실행하는 것이다.
  * 즉, 스케줄링 큐에 들어온 프로세스를 먼저 실행한다.
* 단순하고 직관적인 장점이 있다.
* 먼저 들어온 프로세스가 무조건 끝나야 다음 프로세스가 실행될 수 있어서 다음과 같은 단점이 있다.
  * 실행시간이 짧은 프로세스가 늦게 도착한다면, 이전 프로세스가 종료될때까지 계속 기다려야한다.(평균 대기시간이 길어진다)
  * I/O 작업이 있으면, 그만큼 CPU의 대기시간이 생겨서 CPU의 사용률이 떨어진다.
* FIFO 알고리즘은 프로세스의 Burst Time에 따라 성능의 차이가 심하게 난다.
  * 현대 운영체제에서 사용하지 않고, 일괄처리 시스템에서 사용된다.

### SJF (Shortest Job First)

* 이론적으로만 나온 알고리즘이다. (문제가 있어 사용되지 않았다)
  * 이론적으로는 FIFO보다 성능이 더 좋다. (프로세스 평균 대기시간이 짧아지니까)
* 문제점
  * 프로세스의 실행시간을 예측하는 것이 거의 불가능하다. (사용자에 따라 결정되는 경우가 많으므로)
  * burst time이 긴 프로세스는, 오랫동안 실행되지 않을 가능성이 높다.

***

### RR(Round Robin)

* FIFO 알고리즘의 단점을 해결하기 위한 방법
  * 한 프로세스에게 일정 시간만큼만 CPU를 제공한다. 할당 시간이 지나면, 다음 프로세스에게 CPU를 넘기는 방법이다. (이전 프로세스는 큐 맨 뒤로 이동한다.)
  * 여기서 일정시간을 타임 슬라이스라고 부른다.
* 타임 슬라이스에 따라 RR의 성능이 결정된다.
* 적절한 타임 슬라이스 결정이 가장 중요하다.
  * 타임 슬라이스가 너무 큰 경우
    * FIFO 알고리즘과 동일하다.
    * 만약 FIFO 알고리즘과 스케줄링 성능이 비슷하다면 RR이 더 비효율적일 것이다. (context switching도 일어나기 때문에)
    * 프로그램이 매우 버벅일 것이다.
  * 타임 슬라이스가 너무 작은 경우
    * 컨텍스트 스위칭이 너무 자주 일어난다. (너무 큰 오버헤드 발생)

***

### MLFQ(Multi Level Feedback Queue)

* 오늘날 OS에서 가장 일반적으로 사용되는 CPU 스케줄링 기법이다.
* RR의 업그레이드 버전이다.
  * 타임 슬라이스가 너무 짧은 경우, 응답시간은 빨랐지만, 컨텍스트 스위칭이 너무 자주 발생해 오버헤드가 크다는 것에서 착안된 기법이다.

    ![Untitled](https://s3-us-west-2.amazonaws.com/secure.notion-static.com/c5d33ae9-b48a-4d47-9c4b-8fb65ff0eb9e/Untitled.png)
* 특징
  * 프로세스를 주로 CPU 작업을 하는 **CPU Bound Process**와 입출력을 주로 하는 **I/O Bound Process**로 구분한다.
  * CPU Bound Process는 CPU 사용률과 처리량을 중요하게 생각하고, I/O Bound Process는 응답 시간을 중요하게 생각한다.
  * 이에 CPU Bound Process는 타임 슬라이스를 크게 주는 방식이다.
* CPU Bound와 I/O Bound를 어떻게 구분할 수 있을까?
  * CPU를 스스로 반납하는 경우 I/O Bound일 확률이 높고, CPU를 강제로 뺏기는 프로세스는 CPU Bound일 확률이 높다.
  * 이에 CPU를 강제로 빼앗기면, 우선순위가 더 낮은 큐로 이동하여 다음 차례에서는 CPU를 더 오랜 시간 차지할 수 있도록 하는 것이다.
  * 우선순위가 낮을수록 CPU를 더 오랜시간 가질 수 있또록 하는 것이다.

***