[운영체제] Ch5(1) Scheduling Criteria & Scheduling Algorithms

개요

CPU burst: cpu가 일을 하는 시간

I/O burst: I/O를 기다리는 시간

 

CPU utilization: CPU가 노는 일이 없게 하는 것.

 

아래 그래프: CPU burst duration은 짧은것에 비하여 frquency는 높다. 
--> CPU는 시간이 짧게 걸리는 일을 자주한다.

---

CPU Scheduler: ready queue에서 어떤 프로세스들에게 CPU시간을 할당하지 정한다.

 

[cpu scheduling 결정을 해야하는 순간들]

• 1. Switches from running to waiting state
• 2. Switches from running to ready state
• 3. Switches from waiting to ready
• 4. Terminates

 

1, 4: CPU를 사용하던 프로세스가 CPU가 필요없게 된 경우

2: cpu를 사용하던 프로세스가 CPU time sharing에 의해 다른 프로세스에게 CPU를 넘겨주는 경우

3: I/O입력을 받고 CPU가 할당되기를 기다리는 경우

 

[nonpreemptive VS preemptive]

1, 4: Nonpreemptive(비선취) : CPU를 한 번 잡으면 끝날 때까지 쓴다.

2, 3: preemptive(선취): CPU를 번갈아 가면서 쓴다.

---

Dispatcher(=context switching)

P0를 멈추고 P1으로 바꿔치기하는 동작(수행하던 거 중지, 중지된 거 시작)

 

Dispatch latency: Dispatcher가 save, reload하는데 걸리는 시간

---

Scheduling Criteria

 

• CPU utilization
  –keep the CPU as busy as possible
  -CPU 사용률
  -증가시켜야 함
• Throughput
  – # of processes that complete their execution per time unit
  -처리률
  -증가시켜야 함
• Turnaround time
  – amount of time to execute a particular process
  --반환시간
  -CPU를 기다리는 시간 + 자신이 일을 하는 시간
  --낮춰야 함
• Waiting time
  – amount of time a process has been waiting in the ready queue
  -CPU를 기다리는 시간 총합(ready queue에서 기다리는 시간 총합)
  - 낮춰야 함
• Response time
  – amount of time it takes from when a request was submitted until the first response is produced, not output  (for time-sharing environment)
  --처음으로 CPU할당을 받을 때까지의 시간
  --낮춰야 함

---

Scheduling Algorithms

First-Come, Fisrt-Served (FCFS) p10

• 온 순서대로 하는 것.
• Convoy effect: 긴 프로세스가 먼저 와서 수행하고 있으면 뒤에 온 짧은 프로세스가 많이 기다리게 되는 것.

장: 구현이 쉽다.

단: Convoy effect

---

Shortest-Job First (SJF) p12

• 무조건 짧은 프로세스를 수행하는 것.
• Nonpreemptive (한번 잡으면 중간에 끊지 않고 끝날 때까지 하는 것)

장: average waiting time이 가장 짧다.

단: 어떤 프로세스의 길이를 미리 아는 건 현실상 불가능하다.

 

단점 보완-->

[다음 CPU Burst의 길이를 예측하기]

알파=1/2

알파=1/2라면 --> N번째: (N-1)번째 실측값의 비중: 1/2 , (N-2)번째 실측값의 비중: 1/4 + (N-3)번째 실측값의 비중: 1/8 ...

---

Shortest-remaining-time-First(preemptive SJF) p17

• SJF의 preemptive버전 (preemptive SJF)

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

---

Round Robin(RR) p18

• q(time quantum)을 정해서 프로세스들에게 돌아가면서 q를 할당한다. 

• q가 너무 클 때: 그냥 FIFO
• q가 너무 작을 때: context switching때문에 overhead가 일어난다.
• 일반적으로, SJF보다 average turnaround가 높지만 reponse time은 낮다.
• q가 증가해도 average turnaround은 낮아지지 않는다. (그냥 운)

---

Priority Scheduling p22

• 우선순위 높은 걸 먼저 수행하는 것.

FCFS는 들어온 순서에 의해, SJF은 Burst Time에 의해서 우선순위가 정해진다.

문제점: Starvation-우선순위가 낮은 것들은 오랫동안 CPU할당을 못 받는 것.

해결방안: Aging-CPU를 할당받지 못하면 서서히 우선순위를 높여주고 CPU할당을 받으면 우선순위를 낮추는 것.

 

왼: 단순 우선순위 스케줄링 / 우: 우선순위&RR 스케줄링

---

Multilevel Queue

Multilevel  Feedback Queue

 

• Multilevel queue는 우선순위에 따라 특정 queue에 들어가면 끝인데, 
• MUltileve feedback queue는 특정 queue에 들어가도 다른 queue로 옮거갈 수 있다. (하이브리드 버전)