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

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. 디스크 성능 제고를 위한 방안

방안	설명
하드웨어 기반 기법	– 디스크의 저장 밀도 높임, 고정 헤드 사용 – 디스크 팩의 회전 속도(RPM) 증가
운영체제 기반 기법	– 같은 데이터를 디스크 여러 곳에 중복 배치 – 순차 데이터를 디스크 트랙에 섹터 별 배치 – 필요 시 디스크 데이터들의 위치 재구성
응용 시스템 기반 기법	– 인덱스 사용, 데이터 압축 기법 사용 – 보조 기억장치 해싱 기법 사용