#7. CPU 스케쥴링 알고리즘(1)

Context Switching(문맥전환)

- Scheduler

- Dispatcher

(스케줄러가 선택한 process를 실행하도록, PCB에 저장된 process state, base, limit reg, pc, sp 등의 값을 현재 Processor의 SP, PC MMU의 레지스터 값 등의 context를 restore(복원)하거나 store(저장)하는 일을 Dispatcher가 함. Dispatcher는 OS내부 Process Management안에 있음.)

(당연히 overhead가 있음. 부하가 있다는 말임. 자주 switching하는 작업 자체가 부하가 걸리는 작업임.)

- Context switching overhead

(그래서 overhead가 발생 할 수 있기에, OS설계 시 low level 코드로 작성하는 것을 고려함.)

 

 CPU Scheduling

왜 CPU Scheduling일까?? 현재 job(process)이 끝나면 ready상태가 되고, 다른 job(process)을 실행하는데

CPU가 어떤 job에게 CPU 서비스를 받게 해줄 것인가? 에서 이런 이름이 나옴.

- Preemptive vs Non-preemptive

  * 선점 vs 비선점

(현재 CPU가 어떤 job을 실행하고 있고, I/O작업을 할 것도 아니고, 끝나지도 않았는데 현재 job을 쫓아내고,

새로운 job을 실행하는 것을 preemptive 라고 하며,

Non-preemptive는 일반적인 job의 작업이 끝나고 새로운 job을 실행하는 일반적인 상황에 해당한다.

병원의 환자들일 대기하며 진료를 기다리는 상황을 연상 Non-preemptive, 그런데 간혹 응급환자가 발생하면 기존 진료 받고 있는 환자를 내보내고, 응급환자부터 진료함. 즉, preemptive한 상황이 생김.

Preemptive를 허용하는 OS의 경우 CPU Scheduler가 이러한 Preemprive한 작업이 생기면, 현재 Job을 빼고, Preemptive한 Job을 실행함.)

 

(그렇다면 이러한 scheduling밖에 없을까? 그렇지 않다. 다양한 방식이 존재하며 이를 Scheduling criteria(척도)라고 한다.)

- Scheduling criteria

  * CPU Utilization (CPU 이용률 job count) : 최대한 CPU가 쉬지 않고 일하도록 스케쥴링

  * Throughput (처리율 jobs/second) : 주어진 시간 동안 가장 많은 작업을 끝낼 수 있도록 하는 스케쥴링

  * Turnaround time (반환시간 time) : 작업이 끝나고 나올때까지 걸리는 시간 순으로 스케쥴링 

  * Waiting time (대기시간 second) : 대기 시간(CPU서비스를 받기 위해 대기한 시간 Ready Queue에서 얼마나 기다렸는가)에 따라 스케쥴링 (대기 시간이 짧은 job들이 많을 수록 좋음)

  * Response time (응답시간) : 처음 응답이 나올때까지 걸리는 시간순으로 스케쥴링(interactive computer에서 주로 사용)

...

 

CPU Scheduling Algorithms

- First-Come, First-Served (FCFS) : 먼저 들어온 순

- Shortest-Job-First (SJF) : 작업 시간이 짧은 순

(Shortest-Remaining-Time-First)

- Priority : 우선 순

- Round-Robin (RR) : 뱅뱅 돌면서 서비스

- Multilevel Queue : Queue를 여러개 둠

- Multilevel Feedback Queue : Queue를 여러개 둠

 

First-Come, First-Served

- Simple & Fair

- Example : Find Average Waiting Time

  * AWT = (0 + 24 + 27) / 3 = 17msec cf. 3msec

- Gantt Chart

이것을 막대 그래프 형식으로 그리는데 이를 Gantt Chart라고 부름

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

(CPU burst time 이란 : cpu가 일을 수행하는 시간을 CPU burst time이라고한다.)

- Convoy Effect(호위효과)

: 왕, 대통령 등은 시중들이 있음. 이렇게 뒤에 붙어서 호위하는 효과처럼 BurstTime이 긴 Process가

동작하는 동안 대기하는 Process들이 모두 기다리며 호위하는 것과 같다 해서 Convoy Effect(호위효과)

- Non-preemptive scheduling

(정말 단순하게 먼저 들어온것부터 먼저 서비스를 받는다는 아주 공평한 방식인데,

꼭 좋은것만은 아니다. P2, P3의 경우 Burst Time이 3msec밖에 안되는데 먼저 들어온 P1때문에 24msec이상 기다려야 한다.

ex) 위의 예제의 AWT(Average Waiting Time) 계산

P1->P2->P3순으로 실행한다고 하고 ready time의 평균을 구해본다.

* AWT = (0 + 24 + 27) / 3 = 17msec

P2(P3)->P3(P2)->P1순으로 실행한다면

* AWT = (0 + 3 + 6) / 3 = 3msec )

 

Shortest-Job-First

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

  * cf. 10.25 msec(FCFS)

- Provably optimal

- 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

 

이렇게 SJF 알고리즘 스케쥴링이 더 효과적일 때가 있다.