Process Scheduling 2

Burst (time)

- CPU Burst : CPU가 실행하면서 걸리는 시간

- I/O Burst : CPU가 I/O를 기다리는 시간

프로세스는 CPU Burst 와 I/O Burst의 반복으로 이루어 질 수 있다!

 

Bound

- I/O bound : I/O를 blocking 하기 전 상대적으로 짧은 CPU Burst

- CPU bound : I/O를 blocking 하기 전 상대적으로 긴 CPU Burst

 

 

스케줄링

• CPU utilization : CPU 이용률 ( I/O utilization도 있다)
• Throughput : 단위시간당 몇 개의 job을 했는지.(시스템중심, 주로 최대화 하는 전략)
• Turnaround time : 프로세스가 수행되는데 걸리는 시간
• Response time : 어떤 요청이 submit된 후로 첫 번째 반응이 올 때까지의 시간
• Deadline : 데드라인. realtime system에서 중요하다.
• Fairness : 얼마나 공정하게 스케줄링 되었는지.
• Scheduling Overhead도 고려한다.

Which metrics are important?

Scenario and Obsercation

- Super computer : 사용자에게 큰 long인 running job들이 submit되고 대부분 CPU bound process들이다. I/O job은 별로 없다.

- Personal computer : 보통 사용자와 상호작용. I/O작업이 필연적이도 I/O bound process들이 많다.

- Embedded system : 긴급한 task가 많이 있다. mixed of criticality. priority,deadline이 중요하다.

- Server Computer for Cloud Server : fairness가 중요. proportional share. 가상 시스템에서 물리적인 서버가 있는 것처럼 illusion제공. 이럴 때 proportional fairness, deadline, ~time , CPU utilization, throughput 등등 중요하다.

 

스케줄링 메트릭은 모두 만족시킬 순 없다. 각 시스템에 맞게끔 스케줄링 메트릭을 정해야한다.

 

 

FIFO vs SPN/RR

* SPN/SRT/HRRN 비슷한 성격이기에 SPN을 대표로 나타냄.

Turnaround time 은 SPN이 가장 우수하다.

동일한 time의 process일 때는 FIFO와 SPN의 turnaround time이 우수하다.

FIFO는 O(1)time 이기에 workload에 따라 FIFO가 좋은 스케줄링 방식이 될 수 있다.

 

 

Round Robin (according to TS)

TS가 작을수록 response time은 좋아진다(줄어든다). turnaround time도 줄어들었지만 turnaround time도 항상 줄어든다고 보장할 수는 없다..

이 경우,ts가 줄어들었을 때 turnaround time은 늘어났는데 response time은 줄어들었다.

 

-> turn around time과 reponse time은 trade off관계이다. = 동시에 만족시킬 수 없다.

 

<짧은 time slice>

- 짧을수록 reponse time이 좋아진다.

- timeout 자주 일어나 프로세스 스위치가 빈번하게 일어날 수 있어 오버헤드가 커진다.

- SPN전략과 비슷 : 오버헤드가 매우 크다.

 

<긴 time slice>

- 길수록 response time이 나빠진다.

- context switch 오버헤드가 적다.

- FCFS전략과 비슷하다.

 

Scheduling Incorporating I/O

 

A는 10ms 수행 후 50ms동안 I/O를 기다리고,

B는 기다리기 않는다고 가정한다.

 

time slice가 100ms일 때는 A가 수행되고 10ms에서 수행이 끝나 B가 수행되며 A는 60ms까지 I/O를 기다린다. B는 110ms에서 timeout되고 또 다시 A가 수행된다.

이 때, 110까지를 한 주기로 보고 I/O utilization = 60/110이다.

 

time slice 10ms 일 때는 A수행 후 timeout되고 B가 수행되고 또 10ms뒤에 timeout이 된다. A는 blocked queue에 있기에 B가 수행된다.

60ms 시점에서는 I/O인터럽트가 발생되어 다시 A가 수행된다.

이 때, I/O utilization = 50/60으로 더 높다.

 

=> timeslice가 낮으면 I/O를 고려했을 때 이용률 관점(I/O bound관점)에서 더 좋다. 하지만 CPU bound process는 인터럽트 발생으로 핸들링을 해야한다.

 

Time quantum

Time quantum 결정할 때 useful한 가이드

 

 

실제 프로세스 보면 마우스눌리고 핸들하고 등 인터럽트 처리할만한 시간을 통계적으로 얻어서 그 시간보다 크게 잡으면 즉 요구하는 리스폰스보다 타임퀀텀 크게 잡으며 ㄴ좋다. 만약 타임퀀텀이 더 짧게 잡으면 타임슬라이스를 두 번 걸쳐야해서 리스폰스타임이 길어질 수 있다.

 

 

 

프로그램들을 분석해보면 보통 특정 burst duration안으로 처리된다. 이에 따라 time quantum을 적절히 결정해야한다.

 

 

Virtual Round Robin

• Longer process에 대한 편향성이 있는 RR의 문제점을 해결하기 위한 아이디어
• RR에서 I/O bound process는 짧은 CPU burst를 가지기에 time slice를 다 못쓰고 나온다.
• Virtual Round Robin은 보조큐를 가지고 있다. I/O request하는 프로세스들(time slice를 모두 사용하지 못한 채 끝남)은 blocked state로 가는데 이 프로세스가 이벤트가 발생해서 ready state가 될 때 ready queue로 가는 것이 아니라 보조큐로 간다.
• 스케줄러는 보조큐에 있는 프로세스를 먼저 수행하기에 Fairness가 유지될 수 있다.

Virtual Round Robin

 

CPU bound process는 time slice를 모두 쓰는 경향이 있고 I/O bound process는 time slice를 모두 쓰지 못하는 경향이 있다!

 

 

Multi-Level Feedback Queues

• workload에 따라 전략을 달리한다.(adaptive mechanism)

n개의 queue를 가지며 n개가 각각 다른 알고리즘을 가지고 있다.

n이 작을수록 priority가 크고, time slice는 작다고 가정한다.

가장 높은 우선순위를 가진 RQ0부터 시작하여 time slice를 모두 소진하면 우선순위가 낮아진다.

위 방식은 shortest job(I/O bound process)를 우선하면서 이런 job이 없을 때 time quantum을 늘려가며 CPU bound process 수행한다. 따라서 overhead를 최소화할 수 있다.

하지만 starvation이 발생할 수 있다는 문제점이 있다. 이러한 문제는 대기시간을 계산하여 프로모션하는 방법으로 해결한다.