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로 가장 짧은 평균대기
시간을 갖는다.
4장연습문제.hwp | |
---|---|
1에 도착한 프로세스의 대기시간은 7 아닌가요?