CPU Virtualization(Scheduling)

Scheduling

scheduling은 resource를 필요로하는 프로세스들에게 이를 할당해주는 작업을 의미한다. CPU scheduling은 우리가 정한 기준에 맞춰 적절한 프로세스에게 CPU time을 할당하는 것이다.

CPU scheduling을 설명하기 위해 몇 가지의 가정을 설정한다.

1. 각 job은 같은 시간동안 실행된다.
2. 모든 job은 CPU에 동시에 도착한다.
3. 모든 job은 CPU만 사용한다 (I/O등을 실행하지 않음).
4. 각 job의 실행 시간을 사전에 알 수 있다.

Scheduling Metrics

scheduling 방법을 평가하기 위한 기준은 2개가 있다.

Turnaround time

(Turnaround time) = (Completion time) - (Arrival time)

turnaround time은 arrival time과 completion time의 interval이다. 프로그램이 CPU에 도착한 후에 기다린 시간을 포함해 실행이 완료될 때까지 걸린 시간의 총 합이다.

Fairness

(Response time) = (First run time) - (Arrival time)

여러 프로세스가 얼마나 공평한 기회를 갖고 실행되는가와 연관이 있다.
job이 도착해서 처음 실행될 때 까지의 걸리는 시간을 의미한다.

---

FIFO (First In, First Out)

FIFO는 다른 말로 FCFS(first come, first served)라고도 부른다.
매우 간단하고 구현이 쉬운 것이 장점이다.

만약 10s동안 실행되는 job A, B, C가 매우 근소한 차이를 두고 거의 동시에 도착했다면 각 job은 다음과 같이 실행될 것이다.
B와 C는 기다린 시간이 turnaround time에 추가된다.

FIFO는 service time과 arrival time을 안다면 자주 쓰인다. 혹은 average execution time을 아는 경우에도.. 은행업무와 같은 것들을 보면 어차피 몇분밖에 안걸린다는걸 아니까 FIFO가 잘 동작하는 것처럼.

하지만 FIFO는 문제가 있다. 바로 convoy effect이다.

Assumtion 1을 release해보자.

1. 각 job은 같은 시간동안 실행된다. -> 각 job은 동일한 시간동안 실행되지 않을 수 있다.
2. 모든 job은 CPU에 동시에 도착한다.
3. 모든 job은 CPU만 사용한다 (I/O등을 실행하지 않음).
4. 각 job의 실행 시간을 사전에 알 수 있다.

그러면 문제가 발생한다.
만약 A, B, C가 매우 근소한 차이를 두고 거의 동시에 도착했지만 A가 100s동안 실행된다면 FIFO는 아래와 같이 동작한다.
B와 C가 A의 실행이 완료될 때까지 무한정 기다리게 되면서 turnaround time이 매우 안좋아진 것을 확인할 수 있다.
이는 먼저 들어온 프로세스를 무조건 먼저 실행하는 FIFO의 특성 때문이다.

SJF (Shortest Job First)

SJF는 들어온 job들 중 실행 길이가 제일 짧은 것을 먼저 선택해 실행한다.
SJF는 non-preemptive scheduler이다. 여기서 preemptive란, 한 프로세스가 실행중일 때 강제로 CPU를 뺏어서 다른 프로세스를 실행시키는 것을 의미한다. CPU를 뺏는 것은 job이 complete 되었는지 아닌지와는 관련이 없다.
따라서 non-preemptive scheduler라는 의미는 프로세스가 한 번 실행되면 그 실행이 끝날 때까지 CPU를 뺏지 않음을 의미한다.

SJF를 사용하면 FIFO의 convoy effect문제를 해결할 수 있다.
위에서 보았던 동일한 상황, 만약 A, B, C가 매우 근소한 차이를 두고 거의 동시에 도착했지만 A가 100s동안 실행된다면 SJF는 아래와 같이 동작한다.
세 job이 거의 동시에 도착했으므로 SJF는 그 실행시간을 비교해서 실행이 제일 오래걸리는 A를 가장 마지막에 실행하였다. 이로 인해 FIFO에서보다 turnaround time이 좋아진 것을 확인할 수 있다.

하지만 SJF도 완벽하지는 않다.
Assumtion 2를 release해보자.

1. 각 job은 같은 시간동안 실행된다. -> 각 job은 동일한 시간동안 실행되지 않을 수 있다.
2. 모든 job은 CPU에 동시에 도착한다. -> job은 어느 때이든 CPU에 arrive할 수 있다.
3. 모든 job은 CPU만 사용한다 (I/O등을 실행하지 않음).
4. 각 job의 실행 시간을 사전에 알 수 있다.

만약 t=0일 때 A가 가장 먼저 도착해 100s동안 실행되고 10s동안 실행되는 B와 C가 t=10에 도착한다면 non-preemptive scheduler인 SJF는 A의 실행을 기다리게 된다.
그래서 또 다시 turnaround time이 좋지 않은 것을 확인할 수 있다.
이 문제는 non-preemtive이기 때문에 발생한다.

PSJF (Preemtive Shortest Job First)

PSJF는 STCF(shortest time-to-completion first)라고 불리기도 한다.
PSJF는 SJF에 preemption이 포함된 것이다. 새로운 job이 도착하면 남은 job들과 새로 들어온 job을 비교해서 실행을 결정하게 된다.

위에서와 동일하게 t=0일 때 A가 가장 먼저 도착해 100s동안 실행되고 10s동안 실행되는 B와 C가 t=10에 도착한다면 PSJF는 t=10에 현재 실행중인 A의 남은 실행 시간과 B, C의 남은 실행시간을 비교하고 그 중 실행시간이 제일 짧은 것을 먼저 실행한다.따라서 SJF와는 다르게 B, C가 먼저 실행되었다.

PSJF는 그다지 좋은 response time을 가지고 있지 않다. job이 도착한 시점에 remaining execution time을 비교해서 한 번 실행 순서가 정해지면 해당 프로세스의 실행이 끝날 때까지 다른 job은 기다려야하기 때문이다.
실행 순서를 비교하는 시점은 오로지 새로운 job이 도착했을 때 뿐이고 그 이후에 기다리게 되는 것은 똑같다.

Round Robin(RR) Scheduling

RR은 time slicing scheduling으로, 한 job을 정해진 time slice만큼 실행하고 나면 run queue에 있는 다음 job으로 switch하는 방식이다.
time slice는 scheduling quantum이라고 부르기도 한다.

이 과정은 job이 끝날 때까지 반복되며 time slice는 timer-interrupt period의 배수여야 한다.

RR은 fair하지만 turnaround 측면에선 매우 안좋다.

• time slice의 길이가 짧은 경우 : response time이 좋지만 context switching을 하는 데에 드는 cost가 performance에 큰 영향을 미친다.
• time slice의 길이가 긴 경우 : context switching에 드는 비용을 줄일 수 있지만 response time이 안좋다.

  time slice의 길이는 system designer에게 trade-off의 관계이다.

Incorporating I/O

Assumtion 3을 release해보자.

1. 각 job은 같은 시간동안 실행된다. -> 각 job은 동일한 시간동안 실행되지 않을 수 있다.
2. 모든 job은 CPU에 동시에 도착한다. -> job은 어느 때이든 CPU에 arrive할 수 있다.
3. 모든 job은 CPU만 사용한다 (I/O등을 실행하지 않음). -> 모든 job은 I/O를 수행한다.
4. 각 job의 실행 시간을 사전에 알 수 있다.

A와 B가 각각 50ms의 CPU time을 필요로 하고 A의 I/O가 수행될 때마다 10ms가 걸린다고 가정한다. B는 그저 50ms동안 CPU만 사용하고 I/O를 수행하지 않으며 scheduler가 A를 먼저 실행한다고 가정한다.
I/O request가 발생하면 I/O가 완료될 때까지 job을 block하고 그 동안 다른 job을 실행할 수 있다.
이후 I/O가 완료되면 interrupt가 발생해 OS가 block되었던 프로세스를 ready state로 바꿔준다.