#8. CPU 스케쥴링 알고리즘(2)

Shortest-Job-First

- Example: AWT = (0 + 3  + 9 + 16) / 4 = 7msec

  * cf. 10.25 msec(FCFS)

- Provably optimal

(* 증명되어진 최적화 : 대기시간을 줄이는 방법으로써는 가장 최적화되어있다. 그러면 가장 베스트 방법이라는 건데 무조건 이걸 쓰면 될까?? 아쉽지만 밑에 말 처럼 비현실적인 방법이다.

* 실제로는 Process가 실제 CPU Burst Time이 얼마인지 알 수 없다. 따라서 현실적인 방법이 아닌 이상적인 방법이다. 만약 이 방법을 적용하고 싶다면 CPU Burst Time을 예측 해서 해야한다.

* 이런게 가능하려면 overhead가 적어야 한다. 과거의 작업 시간을 참고해서 예측이 가능하니까...)

- Not realistic, prediction may be needed

Process	Burst Time(msec)
P1	6
P2	8
P3	7
P4	3

(FCFS방식으로 계산하면)

AWT = (0 + 6 + 14 + 21) / 4 = 10.25 msec

(SJF방식으로 계산하면)

AWT = (0 + 3 + 9 + 16) / 4 = 7 msec

 

Shortest-Job-First(2)

- Preemptive or Nonpreemtive

  * cf. Shortest-Remaining-Time-First (최소잔여시간 우선)

Process	Arrival Time	Burst Time(msec)
P1	0	8
P2	1	4
P3	2	9
P4	3	5

- Example

  * Preemptive: AWT = (9 + 0 + 15 + 2) / 4 = 26 / 4 = 6.5msec

  * Nonpreemptive: AWT = (0 + 7 + 15 + 9) / 4 = 7.75msec

(Arrival Time은 현재 Memory에 해당 프로세스가 Arrival Time 후에 적재됨. 따라서 최초 CPU 서비스를 받는 프로세스는 무조건 P1임. 최초 기준 1초 후에 P2가 적재되고, 2초 후에  P3가 적재되고, 3초 후에 P4가 적재됨. Preemptive는 선점 방식으로 진행되므로 BurstTime이 짧은 프로세스가  Nonpreemtive방식의 경우 P1 -> P2 -> P4 -> P3 순으로 진행 쉽게 해당 순서로 (0 + 8 + 12 + 17) / 4라고 생각하면 않된다. 각 프로세스 별 Memory에 들어온 시간(Arrival Time)이 다르므로 그것을 고려해야 한다.

따라서

Non-preemptive AWT = (0 + (8 - 1) + (12 - 3) + (17 - 2)) / 4 = 7.75msec

preemptive AWT =  ((10 - 1) + 0 + (17 - 2) + (5 - 3)) / 4 = 6.5msec 

 

Priority(우선순위): typically an integer number

- Low number represents high priority in general (Unix/Linux)

- Example

  * AWT = 8.2msec

Process	Burst Time	Priority
P1	10	3
P2	1	1
P3	2	4
P4	1	5
P5	5	2

계산해보기

AWT = (0 + 1 + 6 + 16 + 18) / 5 = 8.2msec 

 

Priority Scheduling(2)

- Priority

  * Internal: time limit, memory requirement, I/O to CPU burst, ...

  * External: amount of funds being paid, political factors, ...

(Priority는 위와 같은 기준으로 Performance를 높일 수 있는 방향으로 결정한다.)

- Preemptive or Nonpreemptive

- Problem

  * Indefinite blocking: starvation(기아)

(이것이 어떤 문제이냐면 Ready Queue에 A, B, C프로세스가 있고 B 프로세스가 우선순위가 가장 낮으며, 현재 CPU는 D 프로세스를 실행중이라고 가정해보자.

여기서 새로운 프로세스 E, F, G 등의 프로세스가 들어왔다. 그런데 E, F, G등의 프로세스의 우선순위가 B프로세스보다 높다면?? 최악의 경우 B는 무한정 기다려야 한다.

그래서 이 문제를 해결하기 위해 againg, 어떤 프로세스가 Ready Queue에 오래 머물고 있다면 점진적으로 우선순위를 조금씩 높여준다. 그렇다면 외부에서 프로세스가 들어오더라도 처리가 될 수 있도록 하는 해결법)

  * Solution: againg

 

Round-Robin(1)

- Time-sharing system (시분할/시공유 시스템)

(프로세스들의 작업 시간을 쪼개서 실행)

- Time quantum 시간양자 = time slice(10 ~ 100msec)

- Preemptive scheduling

- Example

  * Time quantum을 4msec로 놓으면,

   * AWT = 17/3 = 5.66msec

Process	Burst Time(msec)
P1	24
P2	3
P3	3

AWT : ((10 - 4) + 4 + 7) / 3 = 5.66msec

(당연히 time quantum을 얼마로 잡느냐에 따라 AWT는 달라짐.)

 

Round-Robin(2)

- Performance depends on the size of the time quantum

  * time quantum -> infinite : FCFS (same) 

  * time quantom -> 0 : Processor sharing (* context switching overhead)

(거의 동시에 프로세스가 실행되는 것처럼 되겠지만, context switching이 매우 빈번하게 발생하면서 overhead가 점점 커진다.)

 

- Example : Average turnaround time (ATT)

  * ATT = 11.0 msec (time quantum = 1), 12.25 msec (time quantum = 5)

Process	Burst Time(msec)
P1	6
P2	3
P3	1
P4	7

(Arrival Time이 다르면 Gantt Chart나 계산 방식이 달라짐)