07 CPU Scheduling (1)

OS는 나름의 scheduling policy (혹은 discipline)을 가지고 여러 프로세스를 실행한다.

scheduling policy를 구성하는 데에는 어떠한 원리가 숨어있는지 알아보자.

 

여러 방식의 scheduling policy를 비교하기 위해서는 이를 위한 평가기준(scheduling metric)이 필요하다.

turnaround time(반환시간)이란 '(작업이 완료된 시각) - (작업이 시스템에 도착한 시각)'을 의미한다.

반환시간은 performance 측면에서의 평가기준이고 fairness를 측정하는 수단은 아니다.

 

workload란 일련의 프로세스들이 실행하는 상황을 의미한다. 여러 workload를 가정해보면서 OS의 scheduling policy 구성 방법에 대해 공부할 수 있다.

우선 다음과 같은 가정을 두고 시작하자.

1. 모든 작업은 같은 시간 동안 실행된다.

2. 모든 작업은 동시에 시스템에 도착한다.

3. 각 작업은 시작되면 완료될 때 까지 실행된다.

4. 모든 작업은 CPU만 사용한다. (입출력 x)

5. 각 작업의 실행시간은 사전에 알려져있다. (unreal한 가정이다)

 

가장 기초적인 알고리즘은 First In First Out (FIFO) (혹은 First Come First Served, FCFS)이다.

작업 A, B, C의 실행시간이 모두 같다면 이는 좋은 알고리즘일것이다.

 

하지만 작업 A의 실행시간이 B와 C에 비해 월등히 길다면?

A를 먼저 실행시키고 B, C를 실행시켰을 때 평균 반환시간이 늘어나게 될 것이다.

이 문제점은 convoy effect라고 불린다.

이를 해결하기위한 방법으로는 Shortest Job First (SJF) 방식이 있다.

모든 작업이 동시에 시스템에 도착한다면 SJF가 optimal scheduling algorithm이다.

 

이번엔 작업 B, C가 시스템에 더 늦게 도착한다면?

SJF를 더 발전시킨 Shortest Time-to-Completion FIrst (STCF) (혹은, Preemptive SJF, PSJF) 방식을 사용하면 된다.