7장 연습문제

운영체제

4. 번호가 0부터 199까지인 200개의 트랙을 가진 이동 헤드 디스크가 있다. 현재 헤드 위치는 143번을 처리하고 있고 바로 전에 125번 트랙의 요청을 끝냈다. 만일 디스크 요청 큐가 FIFO 큐에 84, 140, 178, 90, 149, 100, 170, 125 순서로 유지된다고 할 때, 다음 각 스케줄링에 이 요청을 만족하려는 헤드의 총 움직임은 얼마인지 계산하시오.

1) FCFS 기법 : 가장 간단한 형태로  먼저 도착한 요청이 선적으로 서비스 받게 되는 기법

▶ 근본적인 공평성 보장, 효율이 낮음

- 125 → 143 → 84 → 140 → 178 → 90 → 149 → 100 → 170 → 125

0       ~      84    90        100                        125             140  143  149                   170       178       ~     199

					59
											56
																			38
						88
													59
							49
																		70
												45

∴ 59 + 56 + 38 + 88 + 59 + 49 + 70 + 45 = 464                 총 헤드 이동거리 : 464

2) SSTF 기법 : 탐색 거리가 가장 짧은 요청이 먼저 서비스를 받는 기법

▶ 응답시간 편차 및 기아 상태 발생 우려, 일괄처리 시스템에 유용

- 125 → 143 → 140 → 149 → 125 → 100 → 90 → 84 → 170 → 178

0       ~      84    90        100                        125             140  143  149                   170       178       ~     199

														3
															9
											24
						25
				10
			6
																			86
																					8

∴ 3 + 9 + 24 + 25 + 10 + 6 + 86 + 8 = 171                     총 헤드 이동거리 : 171

3) SCAN 기법 : SSTF가 갖는 응답시간의 편차에 있어서의 차별 대우와 큰 편차를 극복하기 위해 개발(엘리베이터 알고리즘)한 것으로, SSTF와 같이 동작을 하지만, 헤드진행 방향상의 가장 짧은 거리에 있는 요청을 먼저 서비스 하는 기법

▶ 기아 상태 발생되지 않음, 그러나 현 헤드 진행 방향의 반대에 있는 트랙은 오랜 시간 대기

- 125 → 143 → 149 → 170 → 178 → 199 → 140 → 125 → 100 → 90 → 84

0       ~      84    90        100                        125             140  143  149                   170       178       ~     199

															6
																			21
																					8
																								21
														59
											15
						25
				10
			6

∴ 6 + 21 + 8 + 21 + 59 + 15 + 25 + 10 + 6 = 171                        총 헤드 이동거리 : 171

4) C-SCAN 기법 : SCAN에서의 불공평한 대기 시간을 좀 더 균등하게 하려고 변형을 가한 것으로, 헤드는 항상 바깥쪽 실린더에서 안쪽 실린더로 이동하면서 가장 짧은 탐색 시간을 갖는 요청을 서비스하는 기법

▶ SCAN 방식 개선으로 대기시간 균등화,  회전수 최적화로 오버헤드가 많이 걸리는 때에 효과적

- 125 → 143 → 140 → 125 → 100 → 90 → 199 → 178 → 170 → 149

0       ~      84    90        100                        125             140  143  149                   170       178       ~     199

														3
											15
						25
				10
			6
84
																								199
																						21
																				8
																21

∴ 3 + 15 + 25 + 10 + 6 + 84 + 199 + 21 + 8 + 21 = 392                  총 헤드 이동거리 : 392

5) LOOK 기법

▶ SCAN 기법에서 헤드가 트랙 끝까지 이동하지 않고 마지막 요청 트랙까지 이동 하는 기법

- 125 → 143 → 149 → 170 → 178 → 140 → 125 → 100 → 90 → 84

0       ~      84    90        100                        125             140  143  149                   170       178       ~     199

															6
																			21
																					8
														38
											15
						25
				10
			6

∴ 6 + 21 + 8 + 38 + 15 + 25 + 10 + 6 = 129                             총 헤드 이동거리 : 129

6) C-LOOK 기법

▶ C-SCAN 기법에서 헤드가 트랙 끝까지 이동하지 않고 마지막 요청 트랙까지 이동 하는 기법

- 125 → 143 → 140 → 125 → 100 → 90 → 199 → 178 → 170 → 149

0       ~      84    90        100                        125             140  143  149                   170       178       ~     199

														3
											15
						25
				10
			6
																					94
																				8
																21

∴ 3 + 15 + 25 + 10 + 6 + 94 + 8 + 21 = 182                             총 헤드 이동거리 : 182

7) N-step SCAN 기법 : 헤드가 한쪽 방향으로 이동해 나가면서 요청으로 들어온 것만 서비스하다가 다시 반대쪽으로 오면서 이전에 도착했던 요청들을 서비스하는 기법

▶ SCAN 스케줄링과의 차이점은 현재 큐에 대기 중인 요청만 처리

- 125 → 143 → 149 → 170 → 178 → 199 → 140 → 125 → 100 → 90 → 84

0       ~      84    90        100                        125             140  143  149                   170       178       ~     199

															6
																			21
																					8
																								21
														59
											15
						25
				10
			6

∴ 6 + 21 + 8 + 21 + 59 + 15 + 25 + 10 + 6 = 171                        총 헤드 이동거리 : 171

※ 결 론

FCFS 스케줄링	: 총 헤드 이동거리 - 464
SSTF 스케줄링	: 총 헤드 이동거리 - 171
SCAN 스케줄링	: 총 헤드 이동거리 - 129
C-SCAN 스케줄링	: 총 헤드 이동거리 - 392
LOOK 스케줄링	: 총 헤드 이동거리 - 129
C-LOOK 스케줄링	: 총 헤드 이동거리 - 182
N-step SCAN 스케줄링	: 총 헤드 이동거리 - 171

∴ LOOK 스케줄링이 가장 빠르며 N-step SCAN 스케줄링 같은 경우 도중에 요청된 큐가 없기 때문에 SCAN 스케줄링과 같았음