4장 연습문제

9. 다음 프로세스들이 아래의 시간에 도착하고 CPU 버스트 시간 단위는 10밀리 초라고 가정한다. 각각의 알고리즘은 선점, 비선점 스케줄링을 사용한다.

프로세스	도착 시간	버스트 시간
P1	0	8
P2	1	4
P3	2	2
P4	3	1

1) FIFO, RR, SJF, SRT 기법을 이용하여 Gantt 차트를 그리고 각 기법의 평균 반환 시간을 구하시오.

가. FIFO 스케줄링(First In First Out, FCFS 기법 - 비선점)

프로세스	도착 시간	버스트 시간	대기 시간	반환 시간
P1	0	8	0	8
P2	1	4	8	12-1 = 11
P3	2	2	12	14-2 = 12
P4	3	1	14	15-3 = 12

P1	P2	P3	P4

0     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15

평균 대기 시간 : ( 0 + 8 + 12 + 14 ) / 4 = 8.5 * 10 ms

평균 반환 시간 : ( 8 + 11 + 12 + 12 ) / 4 = 10.75 * 10 ms

나. RR 스케줄링(Round Robin - 선점)

프로세스	도착 시간	버스트 시간	대기 시간	반환 시간
P1	0	8	0	8
P2	1	4	8	12-1 = 11
P3	2	2	12	14-2 = 12
P4	3	1	14	15-3 = 12

P1	P2	P3	P4

0     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15

평균 대기 시간 : ( 0 + 8 + 12 + 14 ) / 4 = 8.5 * 10 ms

평균 반환 시간 : ( 8 + 11 + 12 + 12 ) / 4 = 10.75 * 10 ms

다. SJF 스케줄링(Shortest Job First - 비선점)

프로세스	도착 시간	버스트 시간	대기 시간	반환 시간
P1	0	8	0	8
P2	1	4	9	15-1 = 14
P3	2	2	8	11-2 = 10
P4	3	1	5	9-3 = 6

P1	P4	P3	P2

0     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15

0초 P1																	대기 0초, 반환 8초
1초 도착 - P2			대기 9초, 반환 14초
2초 도착 - P3					대기 8초																		반환 10초
3초 도착 - P4							대기 5초												반환 6초

평균 대기 시간 : ( 0 + 9 + 8 + 5 ) / 4 = 2.75 * 10 ms

평균 반환 시간 : ( 8 + 14 + 10 + 6 ) / 4 = 9.5 * 10 ms

라. SRT 스케줄링(Short Remaining Time - 선점)

프로세스	도착 시간	버스트 시간	대기 시간	반환 시간
P1	0	8	7	15
P2	1	4	3	8-1 = 7
P3	2	2	0	4-2 = 2
P4	3	1	1	5-3 = 2

P1	P2	P3	P4	P2	P1

0     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15

0초 P1			대기 7초, 반환 15초
1초 도착 - P2					대기 3초												반환 7초
2초 도착 - P3									대기0초, 반환 2초
3초 도착 - P4							대기 1초				반환 2초

평균 대기 시간 : ( 7 + 3 + 0 + 1 ) / 4 = 2.75 * 10 ms

평균 반환 시간 : ( 15 + 7 + 2 + 2 ) / 4 = 6.5 * 10 ms

2) 어느 기법에서 가장 짧은 평균대기 시간을 갖는지 구하시오.

FIFO 기법	: ( 8 + 11 + 12 + 12 ) / 4 = 10.75 * 10 ms

RR 기법	: ( 8 + 11 + 12 + 12 ) / 4 = 10.75 * 10 ms

SJF 기법	: ( 8 + 14 + 10 + 6 ) / 4 = 9.5 * 10 ms

SRT 기법	: ( 15 + 7 + 2 + 2 ) / 4 = 6.5 * 10 ms

이 프로세스 같은 경우에는 SRT 기법이 6.5 * 10 ms로 가장 짧은 평균대기

시간을 갖는다.