Scheduling:Introduction

Scheduling Metrics

Scheduling Metrics에는 Performance Metric과 Fairness Metric이 있다. 참고로 밑에 예시들은 I/O input이 없는 경우이다.

trunaround time의 개념

---

First In, First Out(FIFO)

먼저 오는 것이 먼저 실행되는 방식이다.

FIFO 실행 방식

FIFO 단점인 예

위와 같이 먼저 온 것의 실행시간이 긴 경우 Average turnaround time이 늘어나게 되고, convey effect가 발생할 수 있다.

---

Convey Effect

Convey Effect란, 예를 들어서 cpu intensive한 p1과 I/O를 많이 실행하는 p2~p10이 있다고 할 때, p1이 먼저 run할 경우에 p2~p10에서 SSD를 사용해야 하지만 p1이 실행 되는 긴 시간 동안에 SSD는 IDLE Time을 가지게 된다. CPU는 바쁜데 다른 하드웨어들이 놀고 있는 현상을 Convey Effect라고 한다.

---

Shortest Job First (SJF)

가장 실행시간이 작은 것부터 실행 시키는 프로그램이다. (실질적으로는 프로그램의 실행 시간을 알 수 없다)

B,C,A가 동시에 왔을 경우 Average turnaround time이 50초 밖에 되지 않는다.

하지만 위에 같이 A가 먼저오고 B,C가 오는 경우에 또 Average turnaround time이 많이 늘어나게 된다.

---

Shortest Time-to-Completion First(STCF)

SFJ에서 발생하는 문제를 해결하기 위해 실행 중에 새로운 파일이 들어오면 크기가 작은 파일을 먼저 실행하도록 한다.

---

Round Robin (RR) Scheduling

여태까지 turnaround time을 줄이는 것이 목적이었다면 이 scheduling은 response time을 줄이는 것이 목적이다.

response time 정의

RR은 실행 파일들을 queue에 넣고 하나씩 꺼내 time slice만큼 실행시키고 다시 queue에 넣는 것을 반복하는 scheduling이다. RR은 굉장히 fair하지만 around time측면에서는 최선이 아닐 수 있다.

RR을 구현할 때, time slice를 지정해 주는 것이 매우 중요하다.

time slice를 작게하면 response time은 좋아지겠지만 context switching하는데 비용이 크게 늘어날 것이다.

반대로, 늘리면 context switching하는데 비용은 줄지만 response time은 안 좋아진다.

따라서, 위와 같은 특성은 시스템 디자이너에게 trade-off이다.

---

Incorporating I/O

 

I/O가 있다면 당연히 첫 번째 처럼 scheduling하는 것보다 밑에 처럼 scheduling하는 것이 더 좋다.