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

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) 증가
운영체제
기반 기법
– 같은 데이터를 디스크 여러 곳에 중복 배치
– 순차 데이터를 디스크 트랙에 섹터 별 배치
– 필요 시 디스크 데이터들의 위치 재구성
응용 시스템
기반 기법
– 인덱스 사용, 데이터 압축 기법 사용
– 보조 기억장치 해싱 기법 사용

 

콘텐츠 사용 시 출처 표기 부탁 드리고, 댓글은 큰 힘이 됩니다^^