[운영체제] CPU Scheduling (2)

CPU와 I/O Burst

컴퓨터 시스템에서는 긴 경우/짧은 경우 모두 섞여 있음.

Ready Queue에 있는 프로세스 중 어떤 프로세스에게 CPU를 줄 것인가에 대한 문제 -> CPU scheduling.

(특히 i/o bound job이 오래 기다리지 않도록 하는 스케쥴링 필요)

---

Scheduling Criteria

시스템 입장에서의 성능 척도 (CPU 하나로 최대한 일을 많이 시킴.)

• CPU utilization (이용률) : 일한 시간의 비율을 높임.
• Throughput (처리량) : 주어진 시간 안에 몇 개의 작업을 완수했는지. ( 가능하면 많이 처리할 수록 좋음.)

 

프로그램 입장에서의 성능 척도 (시간과 관련한 척도 많음.)

• Turnaround time (소요시간, 평균 시간) : CPU를 다 쓰고 나갈 때 까지 걸리는 시간.
• Waiting time (대기 시간) : 순수하게 기다린 시간.
• Response time (응답 시간) : Ready Queue에 들어와서 처음으로 CPU를 얻기까지 걸리는 시간.

[waiting time과 response time과 다른 점]

Preemptive 스케쥴링 : 얻었다가 뺏긴 스케쥴링

 - waiting time은 줄 서서 기다리게 됨. -> 기다리는 시간을 모두 합친 개념 (waiting time)

 - 최초의 CPU를 얻기 까지의 기다리는 시간 (response time)

 - turnaround = waiting + response 

 

 

Scheduling Algorithm

Process	Burst Time
P1	24
P2	3
P3	3

 

- FCFS (First-Come First-Served)

앞에 어떠한 프로세스가 있는지가 영향이 큼. (conboy effect)

먼저 온 순서대로 처리. 효율적이지는 않음.

 waiting time : P1=24, P2=3, P3=3

 average waiting time : (0+24+27)/3 = 17

 

- SJF (Shortest-Job-First)

짧은 프로세스를 먼저 실행. 

주어진 프로세스에 대해 minimun average time 보장.

•  Nonpreemptive : CPU를 잡으면 burst가 완료될 때까지 선점 당하지 않음.

  예시

 

Process	Arrival Time	Burst Time
P1	0.0	7
P2	2.0	4
P3	4.0	1
P4	5.0	4

제일 먼저 도착한 P1 프로세스 실행. 

P1의 Burst time 동안 전부 도착. 가장 짧은 P3 -> P2 -> P4 실행

waiting time : P1=0, P3=7-4, P2=8-2, P4=12-5

Average waiting time = (0+3+6+7)/4 = 4

•  Preemptive : CPU를 줬다가도 더 짧은 프로세스에게 CPU를 줌. (이 때 짧은 건 실행하고 남은 시간과 비교)

예시

 

Process	Arrival Time	Burst Time
P1	0.0	7
P2	2.0	4
P3	4.0	1
P4	5.0	4

P1 프로세스 시작 -> 더 짧은 프로세스 도착 시 뺏김.

[시작]

P1

 

[2초]

P1(7-2) vs P2(4) -> P2

P1(2초) - P2

 

[4초]

P2(4-2) vs P3(1) -> P3

P1(2초) - P2(2초) - P3(1초) 

 

[5초]

P2(4-2) vs P3(4) vs P1(7-2)-> P2

P1(2초) - P2(2초) - P3(1초) - P2(2초)   

 

: P1(2초) - P2(2초) - P3(1초) - P2(2초) - P4(4초) - P1(5초)

P1	P2	P3	P2	P4	P1	끝
0	2	4	5	7	11	16

waiting time : P1=(11-2), P2=(5-4), P3=0, P4=(7-5)

average waiting time = (9+1+0+2)/4 = 3

SJF는 극단적으로 CPU 사용이 짧은 job을 선호. 긴 프로세스는 영원히 CPU를 사용하지 못할 수 있음.

 

 

다음 CPU Burst Time 예측

-> 추정(estimate)만이 가능

-> 과거의 CPU Burst Time을 이용해 추정. (exponential averaging)

 

- Priority Scheduling

우선순위(highest priority)를 가진 프로세스에게 CPU 할당.

priority number (integer) -> 작은 숫자가 더 높음.

: 문제 - Starvation (기아 현상)

: 해결책 - Aging (노화)

 

- Round Robin (RR)

: 현대 CPU 기반 

각 프로세스는 동일한 크기의 할당 시간(time quantum : 일반적으로 10-100 ms)을 가짐.

할당 시간 지나면 프로세스는 선점 당하고 ready queue에 제일 뒤에 가서 다시 줄을 선다.

n 개의 프로세스 ready queue.

할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻음.

-> 어떤 프로세스도 (n-1)q time unit 이상을 기다리지 않는다.

 

q 시간이 너무 크면 fcfs 가 됨.

q 시간이 너무 작으면 context switch 오버헤드 커짐.

 

예시

 

Process	Burst Time
P1	53
P2	17
P3	68
P4	24

(Time Quantum = 20)

P1(20) - P2(37) - P3(57) - P4(77) - P1(97) - P3(117) - P1(11) - P3(134) - P3(154) - P3 (162)

 

: 일반적으로 SJF 보다 average turnaround time이 길지만 response time은 더 짧다.