7. Scheduling: Introduction

서론

파트 6에서 cpu에서 돌아가는 프로세스를 바꿀때 os의 역할이 무엇이고 어떤 일이 벌어지는지 살펴봤다.

이번 파트에서는 os가 어떤 기준으로 다음 프로세스를 스케쥴링 하는지 한번 살펴보자

 

Workload Assumptions

이번 파트의 내용을 이해하기 위해서는 몇가지 가정이 필요하다

1. 각각의 작업은 같은 시간동안 수행된다.

2. 모든 작업은 cpu에 같은 시간에 도착한다.

3. 각각의 작업은 끝날때까지 멈추지 않고 동작한다.

4. 모든 작업은 I/O같은 동작 없이 cpu만 사용한다.

5. os는 각각의 작업의 총 수행시간을 알고있다.

 

Scheculing Metrics

운영체제의 스케쥴링 성능을 측정하는 기준을 scheduling metric이라고 부른다.

그 중 하나인 turnaround time은 작업이 도착해서 수행 완료 되기 까지의 시간이다.

 

First In, First Out (FIFO)

스케쥴링 정책으로 하나 고려해 볼 수 있는게 FIFO이다.

도착한 순서대로 실행하니 매우 합리적인 방법처럼 보인다.

하지만 모든 작업이 같은 시간에 도착했다고 가정하면 상황이 달라진다.

위에서 본 turnaround time을 적용시키면 그렇게 좋은 성능을 보이지는 않는다.

가정 2(모든 작업은 cpu에 같은 시간에 도착한다)를 지워보자.

다음과 같이 처음에 실행하는 작업의 수행시간이 너무 길어버리면 다른 작업들은 이를 기다려야 하는데 이를 convoy effect라고 부른다.

딱 봐도 성능이 좋아보이지는 않는다.

 

Shortest Job First (SJF)

SJF는 수행시간이 짧은 작업을 먼저 실행하는 방법이다.

위와 같은 상황인데 수행시간이 짧은 B, C가 먼저 실행됨으로서 turnaround time에서 좋은 성능을 보인다.

하지만 위와 같이 수행시간이 긴 A가 실행되는 도중에 B, C가 도착한다면?

결국 convoy effect가 발생해 SJF의 장점을 드러내기는 힘들 것이다.

 

Shortest Time-to-Completion First (STCF)

위에서 언급한 가정 3(각각의 작업은 끝날때까지 멈추지 않고 동작한다)을 지워보자.

여기에서 나온 방법이 STCF이다.

STCF는 프로세스가 실행하는 중 이라고 해도 수행시간이 짧은 프로세스가 들어오면 그 프로세스부터 실행하는 방법이다.

여기에서 중요한 개념이 나온다.

non-preemptive(비선점형) scheduler: 프로세스가 끝날 때까지 다른 프로세스로 변경하지 않는다.

preemptive(선점형) scheduler: 프로세스 실행 중간에 멈추고 context switch같은 방법을 이용해 다른 프로세스로 변경한다.

STCF는 preemptive scheduler이다.

그러므로 A가 실행하고 있어도 남아있는 실행시간이 짧은 B, C가 들어오자 그 프로세스들로 스케쥴링된다.

이렇게 되면 turnaround time이 짧아지는 이점이 생긴다.

 

A New Metric: Response Time

새로운 metric이 등장한다.

Response Time은 프로세스가 처음 도착하고 스케쥴링 될 때 까지의 시간이다.

앞에서 살펴본 SJF를 다시 살펴보자.

한 프로세스가 다 끝날때까지 대기해야 하기 때문에 response time에서는 좋은 성능을 내지 못한다.

 

Round Robin

Round-Robin(RR) 스케쥴링은 작업을 time-slice만큼만 수행하고 다른 프로세스로 바꾼다.

이 time-slice는 timer-interrupt를 통해 결정된다.

여기에서 time-slice는 timer-interrupt 간격의 정수배가 되어야 한다는 사실을 파악할 수 있다. 

그렇다면 time-slice를 짧게 할수록 성능이 무조건 좋아진다? 그건 아니다.

time-slice가 짧다는 것은 context switch를 많이 한다는 뜻인데 context swtich과정에 적지 않은 자원이 소모되기 때문이다.

그래서 이 context switch에 소모되는 시간과 잘 조율하여 time-slice를 설정할 필요가 있다.

 

RR 스케쥴링은 response time을 기준으로 한다면 매우 좋은 성능을 보인다.

하지만 turnaroud time을 기준으로 본다면? 

모든 프로세스가 늦은 시간에 끝마치기 때문에 좋은 성능을 보인다고 할 수가 없다.

이처럼 RR 스케쥴링은 response time에서 좋은 성능을 얻은 대신 turnaroud time은 잃었다.

비슷하게 SJF와 STCF 스케쥴링은 turnaround time에서 좋은 성능을 얻은 대신 response time은 잃는다.

이런 trade-off를 잘 고려하여 스케쥴링 정책을 세워야 한다.

 

Incorporationg I/O

거의 모든 프로세스는 I/O작업을 수행한다.

가정 4(모든 작업은 I/O같은 동작 없이 cpu만 사용한다)를 지워보자.

프로세스가 I/O작업을 수행하면 그 시간동안은 Block상태가 되어 위 그림처럼 cpu를 사용하지 않게 된다.

이 시간동안 다른 프로세스를 실행한다면?

그러면 위 그림처럼 cpu가 노는 시간없이 효율적으로 사용할 수 있다.