디스크 스케줄링 유형

I. 디스크 I/O 최적화를 위한, 디스크 스케줄링

• 초기 디스크 접근 시간의 대부분은 탐색 시간이었으므로 탐색 시간 최적화 개선에 집중
• 현재 디스크는 탐색 시간과 평균 회전 지연 시간이 비슷하여 회전 최적화로도 성능 개선

II. 탐색 시간 최적화 위한 디스크 스케줄링 기법

가. SSTF(Shortest Seek Time First) 알고리즘

구분	설명
개념	– 응답 큐에 대기중 요구 중, 현재 헤드 위치부터 가장 가까운 요구 먼저 서비스
사례	– 디스크 위치 – 70번 실린더, Seek rate = 5msec – 대기 큐: 60, 143, 15, 185, 85, 120, 33, 28, 146
헤드 이동
성능 평가	– 총 헤드 이동 거리: 10 + … + 13 = 305 cylinders – 총 탐색 시간 = 305 x 5 = 1525 ms

• SSTF의 경우 안, 바깥쪽 트랙에 기아 발생 가능

나. C-SCAN (Circular-SCAN) 알고리즘

구분	설명
개념	– 헤드가 한 방향으로 이동하며 경로 상 요청 서비스 – 응답 편차가 작아지고, 부하 많은 상황에 효율
사례	– 디스크 위치 – 70번 실린더, Seek rate = 5msec – 대기 큐: 60, 143, 15, 185, 85, 120, 33, 28, 146
헤드 이동
성능 평가	– 총 헤드 이동 거리: 29 + … + 60 = 388 cylinders – 총 탐색 시간 = 388 x 5 = 1940 ms

• C-SCAN 변화형인 에센바흐 알고리즘은 헤드 진행 때 새로 도착한 요청 저장 후 다음 헤드 진행 때 재배열

다. FSCAN (Freeze SCAN) 알고리즘

구분	설명
개념	– 두 서브 큐를 이용하여 서비스 진행 중 도착 요청은 방향 전환 후 서비스, 기존 큐 동결(Freeze)
사례	– 디스크 위치 – 70번 실린더, Seek rate = 5msec – 대기 큐: 60, 143, 15, 185, 85, 120, 33, 28, 146 – 146 진행 중 170 요청, 60 진행 중 50 요청
헤드 이동

• FSCAN의 경우 두 개의 큐를 사용하므로 새로 도착한 요청들은 큐에 넣어 기아 현상 해소

라. 탐색시간 최적화 디스크 스케줄링 기법 유형

방식	개념	특징
FCFS	– First Come First Served – 먼저도착 요청 우선서비스	– 구현이 간단 – 오버헤드 발생
SSTF	– Shortest Seek Time First – 짧은거리 요청 우선서비스	– 일괄 처리에 유용 – 기아 현상 발생
SCAN (엘리베이터)	– 헤드 진행 방향 짧은 거리 요청 먼저 서비스 – 헤드는 끝에서 방향 전환	– 기아 현상 방지 – 낮은 응답 편차
LOOK	– SCAN 방식과 유사 – 마지막 요청 후 방향 전환	– 기아 현상 방지 – 낮은 응답 편차
C-SCAN	– 헤드 항상 바깥→안쪽 이동 – 안쪽 도달 시 바깥쪽 이동	– 대기 시간 균등화 – 응답 편차 작음
C-LOOK	– C-SCAN 방식과 유사 – 마지막 요청 후 끝 이동	– 대기 시간 균등화 – 응답 편차 작음
N-Step SCAN	– 최초 요청만 서비스, 방향 전환 후 추가 요청 서비스	– 현재 큐 요청만 처리
에센바흐	– C-SCAN 처럼 동작 – 전체 트랙 회전 시 서비스 – 회전위치따라 요청 재배열	– 탐색 시간 뿐아니라 회전 시간 최적화 시도

 

III. 회전 지연 시간 최적화 위한 디스크 스케줄링 기법

유형	개념도	설명
SLTF Shortest Latency Time First		– 최단 지연시간 우선 – 요청 중 회전 지연 시간 짧은 요청우선 – Sector Queueing
SPTF Shortest Positioning Time First		– 최단 위치결정 시간 – 탐색+회전 지연시간 합 가장 짧은 요청 – 처리량 많고 반응시간 짧은 스케줄링 유리 – 요청 무기 연기가능
SATF Shortest Access Time First		– 최단 접근시간 우선 – 탐색+회전지연+전송 시간 합 최소 우선 – SPTF보다 처리량많음

• 탐색 시간이 회전 지연 시간보다 훨씬 작을 경우, 시스템은 회전 시간 최적화에 초점 필요