운영체제 - CPU 스케쥴링(2)

운영체제 - CPU 스케쥴링(2)

Scheduling은 Policy + Mechanism이다.

Scheduling Policy

Q. Scheduling policy가 컴퓨터 시스템의 성능에 어떤 영향을 미칠까?

( P : process, C : cpu time )

P1 : C1 = 10, P2 : C2 = 100

1. P1 > P2
• W(p1) = 0, W(p2) = 10, Wavg = 5
2. P2 > P1
• W(p1) = 100, W(p2) = 0, Wavg = 50

즉, Ready Queue에 있는 프로세스 중 무엇을 먼저 수행하느냐에 따라 컴퓨터 시스템의 성능에 차이가 있다.

컴퓨터 시스템의 성능을 나타내는 지표에는 무엇이 있을까?

컴퓨터 시스템 성능평가 척도

1. Throughput : 단위시간당 수행완료되는 프로세스의 수
2. Turnaround time : 프로세스를 실행시키는 데 필요한 시간 총량
3. Waiting time : 프로세스가 작업을 완료하기 위해 Ready Queue에서 기다린 시간의 총량
4. Response time : 사용자가 프로세스의 응답을 받기까지의 시간 총량.

CPU Scheduling의 목적

1. Maximize resource utilization
• CPU utilization, I/O utilization
2. Minimize overhead.
3. Minimize the number of context-switching
4. fairness(CPU를 프로세스별로 공평하게 나누는 것. 1/N 할당방식 또는 우선순위 할당방식+에이징)

Scheduling Policy

1. FIFO

- CPU scheduling은 CPU Burst단위로 FIFO한다.

- First In, First Out방식이다.

장점 : 알고리즘이 단순해서 구현이 쉽다.

단점 : CPU Burst안에 무한루프를 만들어 CPU를 독점하는 경우가 생길 수 있다. 이러한 경우에 대비하여 Timer를 이용한 시간제한을 두고 Timer interrupt를 발생시킨다. 또한, 수행되는 프로세스의 순서에 따라 Wavg(평균 Waiting time)이 천차만별로 달라져서 컴퓨터 시스템의 성능이 안 좋아 질 수 있다.

2. SJF(Shortest Job First)

- CPU Burst Size가 제일 적은 것부터 실행시키는 알고리즘이다.

- 이론적으로 Optimal한 알고리즘으로써 SJF가 가능하다면 가장 빠른 알고리즘이다

그러나, 운영체제가 task의 남은 CPU Burst Size를 예측 할 수 없으므로 현실적으로 불가능한 방법이다.

2-1. non-preemptive SJF

- 현재 수행중인 task가 종료될 때 scheduler가 호출된다.

< non-preemptive SJF >

2-2. preemptive SJF

- 새로운 task가 생성되거나 깨어날 때 scheduler가 호출된다.

< preemptive SJF >

3. Round Robin

- SJF는 이론적으로 optimal한 방법이지만 CPU Burst time을 예측할 수 없기때문에 현실적으로 불가능한 방법이었다.

- 그러므로 FIFO를 base로 하되 SJF와 유사한 방법을 사용하여 컴퓨터 시스템의 성능을 향상시킨 CPU Scheduling방법이 있는데 그것이 Round Robin이다.

- Round Robin은 일정값을 갖는 Time slice를 정의하고 그 만큼의 시간이 경과했을 때 Scheduler가 호출된다. 만약, 실행중이던 task가 time slice안에 종료하지 않았다면 그 task를 Ready Queue로 보내고 새로운 task를 Running함으로써 새로운 task는 time slice보다 실행이 완료 될 것임을 기대하는 알고리즘이다.

Q. engineering problem?

- RR 스케쥴링에서의 Time slice(Time Quantum)값을 무엇으로 할 지가 고민이다.

- Time slice가 무한대라면 FIFO와 동일한 알고리즘이고 Time slice가 0이라면 Interrupt overhead가 무한대로 증가해 불가능한 알고리즘이 된다.

(*Time slice : task에게 CPU가 할당된 후 다음 스케쥴링을 위한 Timer interrupt가 발생할때까지의 시간단위)