디스크 스케줄링 유형

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보다 처리량많음
  • 탐색 시간이 회전 지연 시간보다 훨씬 작을 경우, 시스템은 회전 시간 최적화에 초점 필요

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