[운영체제 OS] CPU Scheduling

Scheduling Criteria

스케줄링의 성능평가에는 크게 5가지 지표가 사용된다. 이 지표들은 앞선 Process 글에서 설명했던 CPU-bound Process와 I/O-bound Process관점으로 나누어볼 수 있다.

 

1. CPU 사용률 : 전체시간 중 CPU가 놀지않고 일한 시간

2. 처리량 : 단위시간당 처리량

3. 소요시간 : 프로세스가 다 수행되고 도착하는데까지 걸리는 시간

4. 대기시간 : Ready Queue에서 기다리는 시간

5. 응답시간 : 중간중간 사용자에게 응답주는 시간 

 

시간보다 처리량이 중요한 CPU-bound Process에서는 1,2번을 maximize하는 방향으로, 사용자와 interactive한 I/O-bound Process에서는 3,4,5번을 minimize하는 방향으로 처리해야한다. 

---

CPU Scheduling Algorithm

우선, CPU스케줄링 방식는 크게 2가지가 존재한다. 바로 선점형 방식과 비선점형 방식이다.

 

선점형 방식

CPU에서 수행중인 프로세스가 있어도 더 중요한 프로세스가 들어오면, 동작 중이던 프로세스를 ready상태로 바꾸고 새로 들어온 프로세스를 수행하는 것

 

비선점형 방식

CPU에서 수행중인 프로세스가 있을때 프로세스가 들어와도, 동작하던 프로세스를 끝까지 수행하고, 그 이후 다시 스케줄링해서 중요한 프로세스를 수행하는 것

 

---

(CPU Scheduling Algorithm : Ready Queue에 있는 프로세스 중 어떤 프로세스를 CPU에 올릴지 선택하는 방법)

1. FCFS / FIFO

Ready Queue에 들어온 순서대로 프로세스를 올리는 비선점형 방식

 

장점

가장 단순하면서 공평하다.

 

단점

대기시간 측면 우수하지 않다.

Convoy effect(소요시간이 긴 프로세스가 먼저 도달하여 시간을 잡아먹는 현상)가 존재한다.

 

 

---

2. SJF (Shortest-Job-First)

Ready Queue에 있는 프로세스 중 수행시간이 짧은 프로세스부터 처리하는 비선점형 방식

 

장점

사용자와 소통하는 Interactive system에 효율적이다.

 

단점

특정 프로세스가 지나치게 차별받는 Starvation 현상이 발생한다.

 

---

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

SJF의 선점형 방식으로 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 갖는 프로세스 도착 시, 새로 도착한 프로세스에게 CPU할당

 

장점

최소 대기 시간을 보장한다.

 

단점

Starvation현상이 여전히 발생한다.

새로운 프로세스의 CPU 시간을 예측하기 어렵기 때문에 현실적으로 구현하기 어렵다.

 

---

4. Priority Scheduling

우선순위를 정한 뒤, 우선순위가 높은 프로세스에게 CPU할당. SJF, SRTF도 CPU burst time을 우선순위로 정한 Priority Scheduling의 일종.

 

단점

우선순위 낮은 프로세스는 계속 수행이 안되는 Starvation현상이 발생한다.

 

해결

시간이 지날수록 프로세스의 우선순위를 높여주는 Aging방식이 있다.

 

---

5. RR (Round Robin)

각 프로세스는 동일한 크기의 할당시간(time quantum)을 가지며, 이 시간동안만 CPU를 이용. 할당시간 동안 처리를 다하지 못하면, CPU를 빼앗고 다음 프로세스에게 넘기는 선점형 방식 

 

장점

공평하다.

Starvation 현상이 발생하지 않는다.

 

단점

할당 시간이 너무 길면 FCFS와 비슷하게 동작하며 FCFS와 동일한 문제점을 야기한다. (CPU-bound process에 유리)

할당 시간이 너무 짧으면 잦은 Context Switch로 오버헤드가 증가한다. (I/O bound process에 유리)

=> 이러한 Tradeoff가 발생하므로 적절한 할당 시간을 정하는게 핵심. 평균 CPU burst랑 비슷하거나 좀더 크게 설정해주는게 이상적.

---

6. Multilevel Queue

우선순위에 따라 Ready Queue를 여러 개 사용하는 방식. 한번 우선순위가 정해지면 바뀌지 않으며, 우선순위가 높은 큐에 먼저 CPU가 할당되어 큐에 속한 모든 프로세스가 처리되야 다음 우선순위 큐가 실행. 

(서야하는 줄이 생성과 동시에 운명적으로 정해졌다고 생각)

 

장점

한 번 우선순위가 매겨저 레디 큐에 들어가면 이동 및 변경이 불가능하므로 오버헤드가 낮다.

 

단점

Starvation 현상이 있다.

공평하지 않다. 

 

---

7. Multilevel Feedback Queue

다단계 큐의 공평성 문제를 해결하는 방식으로 상황에 따라 우선순위 변경이 가능. 즉, 큐 사이간 이동이 가능.

(서야하는 줄이 상황에 따라 다르다고 생각)

 

동작방식

처음 들어오는 프로세스는 우선순위가 가장 높은 큐에 위치한다. 각 큐마다 할당된 quantum이 있고, 하위 큐로 내려갈수록 그 값이 커진다. quantum = 8인 큐에서 CPU 할당 하였을 때 이 단계에서 수행이 완료되면 빠져나가고, 수행을 다 마치지 못했으면 하위큐(우선순위가 낮은 큐)로 이동한다. 나중에는 CPU burst time이 긴 프로세스만 남으므로 FCFS방식으로 처리한다. 이것도 

 

장점

Multilevel Queue의 공평성 문제를 해결한다.

 

단점

결국 우선순위에 의해 처리하는 스케줄링 방식이므로 Starvation 현상이 있다.

=> Aging으로 해결

 

 

( 그림 참고 : https://www.studytonight.com/operating-system/ )