엘리베이터 알고리즘과 에센바흐 알고리즘

I. 디스크 읽기/쓰기 절차, 디스크 스케줄링

가. 디스크 스케줄링의 개념

• 디스크 접근 요청들을 디스크 위치 기준 효율적 처리 위한 디스크 스케줄링 알고리즘

나. 디스크 스케줄링 알고리즘의 유형

• 스케줄링 방법에 따라 시스템의 성능이 달라지며 탐색 시간 최적화가 스케줄링의 결정 요소

II. SSTF(Shortest Seek Time First) 개념/처리예시 및 문제점

가. SSTF의 개념 및 처리 예시

구분	설명
개요	– 현재 헤드에서 가장 가까운 트랙에 해당하는 요청을 우선 처리하는 스케줄링 기법
처리 예시	현재 헤드: 53, 입력 순서: 98,183,37,122,14,124, 65,67 – 헤드가 이동하는 거리 최소화

나. SSTF의 문제점

III. SSTF 문제 해결을 위한 엘리베이터, 에센바흐 알고리즘

가. 엘리베이터 알고리즘

구분	설명
개요	– SSTF와 유사한 방식이지만 한쪽 방향으로 진행 후 끝에 도달 시 반대 방향 전환하는 SCAN 기반 기법
처리 예시	현재 헤드: 53, 입력 순서: 98,183,37,122,14,124, 65,67
장점	– 탐색 시간 개선: SSTF 보다 간단하며, 탐색시간개선 – 기아 현상 개선: SSTF 대표적 문제점 해결
단점	– 방향비트 필요: 이동 방향 관리 위한 별도 비트필요 – 복잡한 알고리즘: 과부하 처리 위한 매커니즘 요구

나. 에센바흐 알고리즘

구분	설명
개요	– 탐색시간과 회전 지연시간 최적화를 목적으로, 헤드는 C-SCAN과 유사하며 요청과 관계 없이 트랙 한바퀴 회전할 동안 요청을 재배열하여 처리 기법
처리 예시	현재 헤드: 53, 입력 순서: 98,183,37,122,14,124, 65,67 – 헤드는 C-SCAN으로 처리 – 회전 지연시간 단축을 위한 요청 재배열
장점	– 회전지연시간 최적화: 회전최적화로 성능 개선 – 균등 처리: C-SCAN 기반에 따른 바깥쪽→안쪽 처리
단점	– 재배열 처리 필요: 에센바흐 스케줄링 위한 별도의 재배열 처리 알고리즘 필요 – 불필요 이동: 안/바깥쪽 처리 블록 미존재에도 이동

IV. 디스크 성능 제고를 위한 방안