2025. 2. 23. 05:43ㆍIT자격증/정보보안기사
정보보안기사(2023. 3. 11.)
2. 디스크 스케줄링 알고리즘 중 엘리베이터 알고리즘이라고 불리는 기법은?
- ① SCAN
- ② SSTF
- ③ C-SCAN
- ④ FCFS
정답은 ① SCAN입니다.
엘리베이터 알고리즘은 디스크 헤드를 실린더 번호가 낮은 순서대로 이동시키다가, 디스크의 끝에 도달하면 방향을 바꿔 실린더 번호가 높은 순서대로 이동시키는 알고리즘입니다. 이러한 동작이 엘리베이터의 동작과 유사하다고 하여 엘리베이터 알고리즘이라고 불립니다. 따라서 디스크 스케줄링 알고리즘 중 엘리베이터 알고리즘이라고 불리는 기법은 SCAN입니다.
디스크 스케줄링 알고리즘은 하드디스크의 입출력(I/O) 성능을 최적화하기 위해 사용되는 알고리즘입니다. 디스크는 회전하는 플래터(plate)와 움직이는 헤드를 사용하여 데이터를 읽고 쓰므로, 효율적인 요청 처리 순서를 결정하는 것이 중요합니다.
🔹 디스크 스케줄링 알고리즘 종류
1️⃣ FCFS (First Come First Serve) - 선입선출
- 설명: 요청이 들어온 순서대로 처리하는 방식
- 장점: 구현이 간단함
- 단점: 요청 순서에 따라 탐색 시간이 비효율적일 수 있음 (예: 헤드가 먼 위치로 이동해야 하는 경우)
예시: 요청 순서: (98, 183, 37, 122, 14, 124, 65, 67)
초기 헤드 위치: 53
이동 순서: 53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67
총 이동 거리: 크고 비효율적일 수 있음
2️⃣ SSTF (Shortest Seek Time First) - 최단 탐색 시간 우선
- 설명: 현재 헤드 위치에서 가장 가까운 요청을 먼저 처리
- 장점: 평균 탐색 시간이 짧아짐
- 단점: 가까운 요청을 계속 먼저 처리하다 보면 일부 요청이 오랫동안 대기하는 기아(starvation) 현상 발생 가능
예시:
요청 순서: (98, 183, 37, 122, 14, 124, 65, 67)
초기 헤드 위치: 53
이동 순서: 53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183
→ 평균 탐색 시간이 줄어듦
3️⃣ SCAN (전방향 이동, "엘리베이터 알고리즘")
- 설명: 헤드는 한 방향으로 끝까지 이동하면서 요청을 처리한 뒤, 반대 방향으로 이동하며 요청을 처리
(즉, 헤드는 계속 왕복하며 움직임) - 장점: FCFS보다 성능이 좋고 기아 현상이 적음
- 단점: 끝까지 가는 동안 중간에 있는 요청이 기다려야 함
예시:
요청 순서: (98, 183, 37, 122, 14, 124, 65, 67)
초기 헤드 위치: 53, 이동 방향: 오른쪽
이동 순서: 53 → 65 → 67 → 98 → 122 → 124 → 183 → 끝까지 이동 → 반대 방향 이동 → 37 → 14
4️⃣ C-SCAN (Circular SCAN, "순환 스캔")
- 설명: SCAN과 유사하지만 한쪽 방향으로만 이동하며 요청을 처리하고, 끝까지 이동한 후 헤드를 다시 시작점으로 이동하여 반복
- 장점: 요청 처리의 균형이 맞춰짐 (모든 요청이 같은 대기 시간을 가짐)
- 단점: 헤드가 한쪽 끝에서 반대쪽 끝으로 이동할 때 시간이 소요됨
이동 순서:
53 → 65 → 67 → 98 → 122 → 124 → 183 → (끝까지 이동 후 처음으로 돌아감) → 14 → 37
5️⃣ LOOK (SCAN의 최적화 버전)
- 설명: SCAN과 유사하지만, 디스크의 끝까지 가지 않고 마지막 요청까지 처리한 후 방향을 바꿈
- 장점: 불필요한 이동이 줄어듦
- 단점: SCAN과 비슷한 단점이 있음
이동 순서:
53 → 65 → 67 → 98 → 122 → 124 → 183 → (끝까지 가지 않고 반대 방향) → 37 → 14
6️⃣ C-LOOK (Circular LOOK)
- 설명: LOOK과 유사하지만 헤드가 한쪽 끝까지 이동한 후, 반대쪽 끝의 요청으로 점프
- 장점: C-SCAN보다 효율적 (불필요한 끝까지의 이동이 없음)
이동 순서:
53 → 65 → 67 → 98 → 122 → 124 → 183 → (가장 작은 요청으로 점프) → 14 → 37