SJF(Shortest Job First)

SRT, SJF 스케줄링 알고리즘의 평균대기시간과 평균반환시간 구하기

 

Q)

 

스케줄링 알고리즘 부분에서 SRT, SJF 스케줄링 알고리즘이 이해가 되질 않습니다.

SRT스케줄링 알고리즘의 정의가 남아있는 실행시간의 추정치가 가장 작은 것을 먼저 실행 한다라고 되어있는데 문제를 통해 상세한 설명 부탁드립니다.

 

***** 문제 *****

* 5개의 작업에 대한 도착시간과 CPU사이클 시간이 아래표와 같다고 하고 다음 물음에 답하

 시오.  

도착시간	0	1	2	3
작업	A	B	C	D
CPU사이클	6	3	1	4

 

위에서 SRT , SJF 스케줄링 알고리즘을 적용할 경우 평균 대기시간과 평균반환시간을 구하시오

 

A)

 

일단 먼저 아셔야 할 내용은

선점형 스케줄링과 비선점형 스케줄링에 대해서 아셔야 합니다.

선점형 스케줄링은 하나의 프로세스가 cpu를 점유하고 있을 때 작업중인 프로세스를 중단시킬수 있는 방식으로 srt가 여기에 속합니다.

 

비선점형 스케줄링은 하나의 프로세스가 cpu를 점유하고 있을 때 작업중인 프로세스를 중단시킬수 없는 방식으로 sjf가 여기에 속합니다.

그럼 계산을 해볼까요

srt는 남아 있는 수행시간이 가장 짧은 작업을 먼저 처리합니다.

위의 그림을 보시면 a가 먼저 시작이 됩니다. 그래서 1을 처리합니다. a의 남은 시간은 5가됩니다.

b가들어오는데 a보다 b가 남은 시간이 짧으므로 a는 대기상태가 되고 b가 처리됩니다.

b가 1을 처리하고 나니 남은시간은 2가 됩니다. 그리고  c가 들어오는데 b보다 c가 남은시간이

적으므로 c가 처리됩니다. b는 대기상태가 됩니다. c를 처리하고 나니 d가 들어옵니다.

a,b,d의 남은 시간이 각각 5,2,4이므로 b를 번저 처리하고 d를 처리하고 a를 처리합니다.

 

평균대기시간은 a,b,c는 도착즉시 시작했으므로 0,d는 도착후 2초를 기다렸으므로

0+0+0+2=2/4=0.5입니다.

평균반환시간은 a는 0에서 시작해서 14에서 끝났으므로 14

b는 1에서 시작해서 5에서 끝났으므로 4

c는 2에서 시작해서 3에서 끝났으므로 1

d는 3에서 시작해서 9에서 끝났으므로 6

그래서 14+4+1+6=25/4=6.25입니다.

 

sjf는 가장 짧은 실행시간을 먼저 실행합니다.

a를 먼저 실행합니다. a가 끝나고 나면 b,c,d가 모두 기다리는 데 이중 c가 실행시간이 가장 짧으므로 실행합니다. c가 끝나고 나면 b,d가 기다리는 데 가 짧으므로 b를 실행하고 d를 실행합니다.

 

평균대기시간 a는 0,c는 2에들어와서 6에 실행됨으로 4,b는 1에 들어와서 7에 실행됨으로 6

d는 3에 들어와 10에 실행됨으로 7, 그래서 0+4+6+7=17/4=4.25

 

평균반환시간은 a는 0에서 시작해서 6에서 끝났으므로 6

b는 1에서 시작해서 10에서 끝났으므로 9

c는 2에서 시작해서 7에서 끝났으므로 5

d는 3에서 시작해서 14에서 끝났으므로 11

6+9+5+11=31/4=7.75입니다.

 

 

출처 : http://ask.nate.com/qna/view.html?n=4577698