[Operating Systems] Scheduling

Modern Scheduling에 대해 알아보기 위해 몇 가지 사전 가정을 해보자.

(실제로 그렇지 않다 하더라도)

 

1. 각각의 Job들은 모두 같은 시간동안 동작한다.

2. 모든 Job들은 같은 시간에 도착한다

3. 모든 Job들은 작업 시간동안 전부 CPU를 사용한다

4. 모든 Job들의 Running-Time은 알려져 있다.

 

Scheduling Metrics

 

어떤 Scheduling 방법의 효율성을 측정하기 위한 몇 가지 지표가 있는데, 자주 사용되는 두 가지의 지표를 소개하겠다.

 

1.  Turnaround Time

 

Job Complete Time- arrived time in system으로 정의된다.

 

Job이 System에 도착하고 나서 끝날 때 까지 얼마만큼의 시간이 지났는지를 나타내는 지표이다.

 

2. Response Time

 

First Run TIme- arrived time in system 으로 정의된다.

 

Job이 System에 도착하고 나서 일이 시작될 때 까지 얼마만큼의 시간이 지났는지를 나타내는 지표이다.

 

First In, First Out (FIFO)

 

먼저 들어온 것을 가장 높은 우선순위로 처리하고 계속해서 그 다음을 처리하는 방법이다.

 

즉 실행시간이 10초인 3개의 Job이 있으면

 

ABC는 동시에 도착하고

A는 0~10초

B는 10~20초

C는 20~30초 동안 실행된다.

 

Average Turnaround Time을 계산하면

 

T= (10+20+30)/3= 20이 된다.

 

그런데 만약 A의 실행시간이 100초라고 가정하면

 

Average Turnaround Time은 

T= (100+ 110+ 120)/3= 110이 되어 매우 비효율적이다.

 

Shortest Job First (SJF)

 

SJF는 가장 짧은 작업 시간을 가진 Job을 가장 먼저 실행하는 방법이다.

 

기본 가정 첫번째의 가정을 이제 배제한다.

 

더이상 모든 Job들의 실행 시간은 동일하지 않다.

 

1. 각각의 Job들은 모두 같은 시간동안 동작한다.

2. 모든 Job들은 같은 시간에 도착한다

3. 모든 Job들은 작업 시간동안 전부 CPU를 사용한다

4. 모든 Job들의 Running-Time은 알려져 있다.

 

즉 A가 100초동안 동작하고 B, C가 10초동안 동작한다고 하면

 

A,B,C는 동시에 도착하고

B는 0~10초

C는 10~20초

A는 20~120초 동안 실행된다.

 

Average Turnaround Time은 

T= (10+ 20+ 120)/3= 50으로 FIFO보다 훨씬 우수하다.

 

그런데 실제 System에서는 가정 2(모든 Job들은 같은 시간에 도착한다)는 상당히 비현실적이다.

 

이제 가정 2를 삭제하고 다른 예를 한번 보도록 하자.

 

1. 각각의 Job들은 모두 같은 시간동안 동작한다.

2. 모든 Job들은 같은 시간에 도착한다

3. 모든 Job들은 작업 시간동안 전부 CPU를 사용한다

4. 모든 Job들의 Running-Time은 알려져 있다.

 

A는 0초에 도착하고, B와 C는 10초 뒤에 도착한다고 가정해 보자.

 

A의 동작 시간은 100초

B와 C의 동작 시간은 10초라고 하면

 

A는 0~100초

B는 100~110초

C는 110~120초 동안 실행된다.

 

다시한번 Average Turnaround Time을 계산해 보면 103.333...초가 나온다.

 

즉 좀 더 현실적인 관점에서 SJF역시 상당히 비효율적임을 알 수 있다.

 

Shortest Time to Completion First (STCF)

 

SJF에서 Preempt(선점)개념을 추가한 Scheduling 방법이다.

 

SJF와 같은 방법을 사용하다가 새로 arrived된 작업이 있으면 다시한번 Shortest Job을 찾아서 그 Job을 먼저 완료되게끔 하는 방법이다.

 

위와 같은 상황을 SJCF를 적용하여 예로 들겠다.

 

A는 0초에 도착하고, B와 C는 10초 뒤에 도착한다고 가정해 보자.

 

A의 동작 시간은 100초

B와 C의 동작 시간은 10초라고 하면

 

A는 0~10초 

B는 10~20초 (B와 C는 10초 지점에 arrived 하므로 CPU를 선점할 수 있다)

C는 20~30초

다시 A는 30~120초 동안 실행된다.

 

이 때의 Average Turnaround Time은 다시 50초가 된다.

 

그러나 우리는 새로운 Metric으로 이것이 진정으로 가장 우수한 것인지 판별할 필요가 있다.

 

Average Response Time을 보자.

 

이 경우에 Average Response Time은 3.33초가 된다.

 

C를 살펴 보면 도착한지 10초가 걸린 뒤에야 비로소 실행되는 것을 알 수 있다.

 

우리가 인터넷을 사용하려고 브라우저를 더블클릭했는데 10초 뒤에 창이 나타나는 모습을 상상해 보자.

 

이는 분명 우리에게 큰 짜증을 안겨줄 것이다.

 

따라서 SJF는 Response Time의 측면에서 좋지 못한 성능을 보임을 알 수 있다.

 

Round Robin (RR)

 

기본적 Idea는 간단하다.

 

한 Job이 끝날 때까지 계속해서 동작하는 대신 time slice(때로는 Scheduling quantum이라고 불린다)라는 단위동안만 실행되게 하는 것이다.

(Time Slice는 timer-interrupt의 배수가 되어야 함을 알아두자)

 

예를 들어 A, B, C가 1초동안 실행되는 Job이라고 하고 time slice가 0.1초라고 하면

 

0.1초동안 A를 실행하고

0.1초동안 B를 실행하고

0.1초동안 C를 실행하고

이것을 A, B, C가 모두 끝날 때 까지 반복한다.

 

직관적으로 알아볼 수 있듯이 RR은 Average Response Time을 획기적으로 줄여준다.

그러나 Turnarround Time에서는 좋지 못한 성능을 보인다.

 

또한 RR에서는 time slice를 어떤 값으로 설정할 것인지에 따라 성능에 크게 영향을 미친다.

 

time slice가 너무 짧다면 Context Switch가 자주 일어남에 따라, Overhead가 커지고 

극단적으로는 Context Switch를 하는 동안에 time slice가 끝나버려 Job을 전혀 진행시키지 못하고 무한히 Context Switch만 반복하게 되는 불상사가 일어날 수도 있다.

 

Incorporating I/O

 

가정3(모든 Job들은 작업 시간동안 전부 CPU를 사용한다)를 제거해 보자.

 

1. 각각의 Job들은 모두 같은 시간동안 동작한다.

2. 모든 Job들은 같은 시간에 도착한다

3. 모든 Job들은 작업 시간동안 전부 CPU를 사용한다

4. 모든 Job들의 Running-Time은 알려져 있다.

 

상당수의 Program들은 CPU뿐만 아니라 Storage를 사용하거나 사용자로부터 입력을 받거나 출력하는 I/O를 사용하기도 한다.

 

이러한 상태일때 우리가 알듯이 그 Process의 상태는 Blocked상태가 되어 CPU를 사용하지 않게 된다.

 

그런데, Blocked상태일때도 CPU를 점유하고 있다면 이것은 상당히 비효율적일 것이다.

 

따라서 실행중인 Job이 CPU를 사용할 수 없는 상태일 때 다른 Job에게 CPU를 양보한다면 더 우수한 성능을 보일 것이다.

 

 

--------------------------------------------------

 

Reference

 

Operating Systems: Three Easy Pieces (Remzi H. Arpaci-Dusesdau, Andrea C. Arpaci-Dusesdau)