기출 HDD

문제

다음 디스크 스케줄링 기법인 FCFS (First Come First Served), SSTF (Shortest Seek Time First), SCAN, C-SCAN (Circular SCAN)에 대해 설명하고, 주어진 디스크 대기 큐를 이용해 FCFS, SCAN, C-SCAN 알고리즘에 따른 디스크 헤드의 움직임을 설명하세요. (현재 헤드 위치는 트랙 80에 있으며, 트랙 0 방향으로 이동 중입니다.)

디스크 대기 큐 (트랙 번호): 88, 198, 35, 45, 98, 13, 151, 50, 66

답안

1. 디스크 스케줄링 기법 설명

(1) FCFS (First Come First Served)

•	개념: 디스크 요청이 들어온 순서대로 처리하는 가장 단순한 스케줄링 알고리즘입니다.
•	장점: 구현이 간단하며, 요청 순서를 유지해 공정성을 보장합니다.
•	단점: 요청 트랙들이 무작위로 분포된 경우 탐색 시간이 크게 증가할 수 있어 효율이 낮을 수 있습니다.

(2) SSTF (Shortest Seek Time First)

•	개념: 현재 헤드 위치에서 가장 가까운 트랙을 우선적으로 처리합니다.
•	장점: 탐색 시간을 줄여 성능을 개선할 수 있습니다.
•	단점: 특정 요청이 계속 뒤로 밀리는 기아(Starvation) 현상이 발생할 수 있습니다.

(3) SCAN

•	개념: 엘리베이터 스케줄링이라고도 불리며, 헤드가 한 방향으로 이동하면서 요청을 처리하다가 끝에 도달하면 반대 방향으로 이동해 처리합니다.
•	장점: 탐색 방향을 한정해 전체 탐색 시간을 줄일 수 있습니다.
•	단점: 끝에서 방향을 바꾸는 과정에서 오버헤드가 발생할 수 있습니다.

(4) C-SCAN (Circular SCAN)

•	개념: SCAN의 변형으로, 헤드가 한쪽 끝까지 이동하여 요청을 처리한 후 다시 처음으로 돌아가 요청을 처리하는 방식입니다.
•	장점: 모든 요청이 공평하게 처리되어 기아 현상을 방지할 수 있습니다.
•	단점: SCAN에 비해 회귀 시간이 추가되면서 일부 오버헤드가 발생할 수 있습니다.

2. 주어진 디스크 대기 큐에 대한 FCFS, SCAN, C-SCAN 알고리즘 적용

   • 초기 조건:
   • 현재 헤드 위치: 트랙 80
   • 이동 방향: 트랙 0 방향
   • 디스크 대기 큐: 88, 198, 35, 45, 98, 13, 151, 50, 66

(1) FCFS 스케줄링에 따른 디스크 헤드 움직임

FCFS 알고리즘은 요청이 들어온 순서대로 처리합니다.

1.	현재 헤드 위치: 80
2.	88 - (80에서 88로 이동)
3.	198 - (88에서 198로 이동)
4.	35 - (198에서 35로 이동)
5.	45 - (35에서 45로 이동)
6.	98 - (45에서 98로 이동)
7.	13 - (98에서 13로 이동)
8.	151 - (13에서 151로 이동)
9.	50 - (151에서 50으로 이동)
10.	66 - (50에서 66으로 이동)

헤드의 총 이동 거리는 위의 순서로 이동 거리를 계산하여 구할 수 있습니다.

(2) SCAN 스케줄링에 따른 디스크 헤드 움직임

SCAN 알고리즘은 현재 방향인 트랙 0 방향으로 이동하면서 요청을 처리합니다. 0번 트랙에 도달한 후 반대 방향으로 이동하여 남은 요청을 처리합니다.

1.	현재 헤드 위치: 80
•	트랙 0 방향으로 이동 중이므로 트랙 80 이하의 요청을 우선 처리합니다.
•	35, 45, 13, 50, 66이 트랙 80 이하의 요청으로, 이를 순서대로 처리하고 0번 트랙에 도달한 후 방향을 변경합니다.
2.	트랙 0에 도달 후 방향 전환
•	남은 요청 88, 98, 151, 198을 순서대로 처리합니다.

헤드의 움직임 순서는 80 -> 66 -> 50 -> 45 -> 35 -> 13 -> 0 (반대 방향 전환) -> 88 -> 98 -> 151 -> 198입니다.

(3) C-SCAN 스케줄링에 따른 디스크 헤드 움직임

C-SCAN 알고리즘에서는 헤드가 트랙 0에 도달하면 끝 트랙으로 이동하여 계속 같은 방향으로 요청을 처리합니다.

1.	트랙 80에서 트랙 0 방향으로 이동하면서 80 이하의 요청을 처리합니다.
•	요청 순서: 66, 50, 45, 35, 13
2.	트랙 0에 도달한 후 끝 트랙으로 이동하여 다음 요청을 처리합니다.
3.	트랙의 끝(예: 트랙 199)에서 트랙 0까지 이동하면서 요청을 처리합니다.
•	남은 요청 순서: 88, 98, 151, 198

헤드의 움직임 순서는 80 -> 66 -> 50 -> 45 -> 35 -> 13 -> 0 (트랙 끝으로 이동) -> 88 -> 98 -> 151 -> 198입니다.

C-SCAN은 SCAN보다 일정하게 탐색 시간을 유지하며, 모든 요청이 공평하게 처리되도록 합니다.