[TIL/혼공컴운] 2025/02/19

CPU 스케줄링 ✍️

1. CPU 스케줄링 개요 🌿

1-1. 프로세스 우선순위 ⚙️

CPU 스케줄링은, 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것을 말한다. 선착순으로 처리하는 것이 언뜻 보기에는 합리적이다. 하지만 프로세스마다 우선순위가 다르기에 문제가 된다.

우선순위가 높은 프로세스란 빨리 처리해야 하는 프로세스를 의미한다. 입출력 작업이 많은 프로세스는 우선순위가 높은 프로세스 중 하나다. 관련해서, ``입출력 집중 프로세스(I/O bound process)`와 `CPU 집중 프로세스(CPU bound process)``에 관해 살펴보자.

입출력 집중 프로세스는 실행 상태보다는 입출력을 위한 대기 상태에 더 많이 머무르고, CPU 집중 프로세스는 대기 상태보다는 실행 상태에 더 많이 머무르게 된다.

즉 CPU 집중 프로세스가 CPU를 더 많이 사용해야 하는 프로세스인데, 입출력 집중 프로세스와 동일한 빈도로 CPU를 사용하는 것은 합리적이라고 볼 수 없다. 그래서 ``입출력 집중 프로세스의 우선순위가 더 높다``. 이게 무슨 말이냐!

잠깐만 실행하면 대기 상태가 될 입출력 집중 프로세스를 먼저 실행하면, 다른 프로세스가 CPU를 사용할 수 있게 된다. CPU를 차례대로 돌아가며 사용하는 것보다, 각각의 상황에 맞게 CPU를 배분하는 것이 더 효율적이라는 점이 핵심이다. 이렇듯 프로세스마다 우선순위가 있는데, 운영체제는 각 프로세스의 PCB에 우선순위를 명시한다.

macOS을 사용하고 있어서 ``ps -el``로 우선순위를 확인해 봤다.

1-2. 스케줄링 큐 ⚙️

그런데 운영체제가, CPU를 사용할 다음 프로세스를 찾기 위해 일일이 모든 프로세스의 PCB를 뒤적거리는 것은 비효율적이다. 그래서 운영체제는 "줄을 서서 기다릴 것"을 요구하고, 해당 줄을 ``스케줄링 큐(scheduling queue)``로 구현하고 관리한다.

이때, CPU를 이용하고 싶은 프로세스들이 서는 줄이 ``준비 큐(ready queue)`이고, 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄이 `대기 큐(waiting queue)``이다.

준비 큐든 대기 큐든, 운영체제는 PCB들이 큐에 삽입된 순서대로 프로세스를 하나씩 꺼내어 실행한다. 단, 그중 우선순위가 높은 프로세스를 먼저 실행한다. 우선순위가 높은 프로세스가 긴 줄에서 소위 VIP처럼 대우받는 것이다.

1-3. 선점형 / 비선점형 스케줄링 ⚙️

한 단계 더 나아가 보자. 만약 우선순위대로 프로세스를 처리하다가, 다른 프로세스가 CPU를 먼저 사용하기를 요청한다면 어떻게 처리해야 할까?

반대로 ```비선점형 스케줄링```은, 해당 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까지는, 다른 프로세스가 끼어들 수 없는 스케줄링 방식을 의미한다. 오버헤드는 선점형 스케줄링에 비해 적을 수 있으나, 모든 프로세스가 골고루 자원을 사용할 수 없다는 단점이 있다.


## 2. CPU 스케줄링 알고리즘 🌿

### 2-1. 스케줄링 알고리즘 종류 ⚙️

#### 2-1-1. 선입 선처리 스케줄링 ✅

평균 대기시간은 (22+17+0)/3이므로 13ms다. 2ms 프로세스를 실행하기 위해 22ms를 대기해야 하는 대참사가 벌어진다. 이러한 현상을 ``호위 효과(convoy effect)``라고 한다.

#### 2-1-2. 최단 작업 우선 스케줄링 ✅

호위 효과(convoy effect)를 제거하기 위해, 단순히 생각해 보면 CPU 사용 시간이 긴 프로세스를 나중에 실행하면 된다.

평균 대기시간은 (7+2+0)/3, 3ms로 줄어든다. 이처럼 CPU 이용 시간의 길이가 가장 짧은 프로세스부터 실행하는 스케줄링 방식을 ``최단 작업 우선 스케줄링``이라고 부른다. SJF(Shortest Job First Scheduling)이라고 부르면 더 멋있다.

#### 2-1-3. 라운드 로빈 스케줄링 ✅

![](https://velog.velcdn.com/images/minkwan/post/08466194-11dd-4ce5-9669-a0cfb813bb92/image.png)

라운드 로빈 스케줄링의 핵심은 타임 슬라이스의 크기다.

타임 슬라이스가 지나치게 크면 선입 선처리 스케줄링 방식과 다를 바 없어 호위 효과가 생길 여지가 있고, 타임 슬라이스가 너무 작으면 context switching에 발생하는 비용이 커지게 된다.

#### 2-1-4. 최소 잔여 시간 우선 스케줄링 ✅

SRT(Shortest Remaining Time), ```최소 잔여 시간 우선 스케줄링```은, ```최단 작업 우선 스케줄링 알고리즘에 라운드 로빈 알고리즘을 더한 스케줄링``` 방식이다.

프로세스들이 정해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스로는 남아있는 작업 시간이 가장 적은 프로세스가 선택된다.

달리 표현하면 최소 잔여 시간 우선 스케줄링은, ```선점형 최단 작업 우선 스케줄링```이라고 할 수 있다.

#### 2-1-5. 우선순위 스케줄링 ✅

앞서 설명한 ``최단 적업 우선 스케줄링`과 `최소 잔여 시간 우선 스케줄링`은 둘 다 우선순위 스케줄링의 일종으로 볼 수 있다. 최단 작업 우선 스케줄링은 `작업 시간이 짧은 프로세스에 높은 우선순위`를 부여하고, 최소 잔여 시간 우선 스케줄링은 `남은 시간이 짧은 프로세스에 높은 우선순위``를 부여하기 때문이다.

문제는, 우선순위가 낮은 프로세스는 준비 큐에 먼저 삽입되었음에도 불구하고, 우선순위가 높은 프로세스들에 의해 실행이 계속해서 연기될 수 있는데, 이를 ``기아(starvation) 현상``이라고 한다.

기아 현상을 방지하기 위한 기법이 ``에이징(aging) 기법``이다. 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식이라고 볼 수 있다.

#### 2-1-6. 다단계 큐 스케줄링 ✅