[운영체제] CPU Scheduling

 

 

 

Shortest-remaining-time-first (Shortest job first)

Preemptive 방식의 스케줄링이다. (현재 진행중인 프로세스를 밀어내고 다른 프로세스가 끼어들 수 있다.)

t1: P1이 도착하여 작업을 시작한다.

t2: P2가 도착하여 P1과 잔여작업시간을 비교한다. P1은 7초, P2는 4초 남았으므로 P2의 preemption이 일어난다.

t3: P3가 도착하지만 P2의 잔여작업시간이 더 기므로 P2가 지속된다.

t5: P2가 종료되었고, P1, 3, 4 중에서 P4의 잔여작업시간이 가장 기므로 P4가 먼저 시작된다.

t10: P4가 종료되었고, P1과 P3중 P1의 잔여작업시간이 더 짧으므로 P1이 진행된다.

t17: P1이 종료되었고 마지막 P3가 진행된다.

이를 간트 차트로 나열하자면 다음과 같다.

[(10 - 1) + (1 - 1) + (17 - 2) + 5 - 3)] / 4 = 26/4 = 6.5

평균 대기시간은 6.5밀리초가 된다.

 

 

 

우선순위 스케줄링 Priority Scheduling

프로세스마다 우선순위가 부여되어 있고, 그 순서에 따라 처리된다.

우선순위가 높은 프로세스가 도착했을 때 현재 진행중인 프로세스를 밀어낼 수 있다면 preemptive, 그렇지 않다면 nonpreemptive이다.

실시간 운영체제(Realtime OS)에서 주로 사용된다.

 

- 우선순위가 낮은 프로세스는 영원히 실행되지 않을 수 있다. (Starvation)

    기다리는 시간을 우선순위에 반영하면 결국 실행되므로 이 문제를 방지할 수 있다. (Aging)

 

 

t0: P1 - P5 프로세스가 동시에 도착한다. P2의 우선순위가 1로 가장 높으므로 실행된다.

t1: P2가 종료되었고, P5의 우선순위가 2로 가장 높으므로 실행된다.

t6: P5가 종료되었고, P1의 우선순위가 3으로 가장 높으므로 실행된다.

t16: P1이 종료되었고, P3의 우선순위가 4로 더 높으므로 실행된다.

t18: P3이 종료되었고, 마지막으로 P4가 실행된다.

P1 ~ P5의 대기시간 간트 차트는 다음과 같다.

(6 + 0 + 16 + 18 + 1) / 5 = 8.2

평균 대기시간은 8.2밀리초가 된다.

 

 

 

선입선출 First-come, First-Served or FIFO

작업이 들어온 순서대로 처리하는 알고리즘이다.

P1 -> P2 -> P3 순서로 프로세스가 도착하였을 경우 간트 차트는 아래와 같다.

 

각 프로세스의 대기시간은

P1 = 0

P2 = 24

P3 = 27

이며, 평균 대기시간은

(0 + 24 + 27) / 3 = 17초 이다.

 

 

 

위와 동일한 작업이 P2 -> P3 -> P1 순으로 도착했다고 가정하면 대기시간은

P1 = 6

P2 = 0

P3 = 3

이며, 평균 대기시간은

(6 + 0 + 3) / 3 = 3초 이다. 따라서 이전 방식에 비해 효율적이며, 실행시간이 짧은 프로세스를 먼저 진행하는 것이 좋다는 것을 알 수 있다.

Convoy Effect - 실행시간이 긴 프로세스가 먼저 진행되는 것을 기다리느라 뒤에 오는 짧은 프로세스 또한 오래 걸리는 현상

 

 

참고