디스크 스케줄링

Disk Scheduling

지연 시간 구성

스케줄링	설명
탐색 시간(Seek Time)	헤드를 해당 데이터가 존재하는 트랙이나 실린더에 위치시키는 데 소요 시간
회전 지연시간(Latency Time)	디스크 원판이 회전하여 섹터가 헤드의 바로 아래에 위치할 때까지 소요 시간
전송 시간(Transfer Time)	디스크와 주 기억장치 간 실제 데이터가 이동하는데 소요 시간

종류

FCFS

First Come First Served

먼저들어온 요청부터 처리

• 알고리즘이 단순하고 구현 용이
• 공정한 스케줄링
• 비효율적

SSTF

Shortest Seek Time First

현재 헤드 위치에서 가장 가까운 트랙부터 처리

• 헤드 이동 거리 최소화
• 단위시간당 처리량 최대화
• Starvation 가능성
• 응답시간의 편차가 큼

SCAN

aka. 엘리베이터 알고리즘

실린더의 양쪽 끝을 왕복하여 진행 방향에 있는 요청 처리

• 진행 방향의 실린더 끝에 도달하면 방향을 전환하는 방식
• SSTF의 응답시간 편차를 극복하기 위해 Denning이 제안
• 현재 가장 널리 사용됨(C-SCAN 포함)
• SSTF 대비 탐색시간의 편차 감소
• SSTF 대비 Starvation 해소
• 실린더 끝에 위치한 블록은 상대적으로 대기시간 및 대기 편차 큼

C-SCAN

Circular SCAN

한쪽 방향으로 진행하며 진행 방향에 있는 요청 처리

• 진행 방향의 실린더 끝에 도달하면 반대편 실린더 끝으로 한번에 이동 후, 동일한 방향으로 진행함
• SCAN의 응답시간 편차 개선
• 처리할 블럭이 없어도 끝까지 이동하므로 비효율적

LOOK

진행방향에 있는 마지막 블럭을 처리하면 방향을 전환하여 진행

• SCAN과 같이 처리하되, 처리 블럭이 있는 첫 지점, 마지막 지점 까지만 이동
• 진행여부 결정에 오버헤드 발생

C-LOOK

Circular Look

진행방향에 있는 마지막 블럭을 처리하면 반대편 끝과 가까운 요청 블럭으로 이동

• C-SCAN과 같이 처리하되, 처리 블럭이 있는 첫 지점부터 시작하고 더이상 처리할 블럭이 없으면 되돌아 옴
• 진행여부 결정에 오버헤드 발생

N-Step Scan

진행하는동안 새로 요청된 블럭은 다음 진행에서 처리

• 기존 블럭들은 Scan과 같은 방식으로 처리

SLTF

Shortest Latency Time First

회전 지연시간이 가장 짧은 것을 먼저 서비스

• 고정 헤드 장치에 적합

Eschenbach

C-SCAN처럼 전체 트랙을 한바퀴 돌 동안 요청을 재배열

• 부하가 큰 항공 시스템을 위해 개발
• 탐색 시간과 회전 지연 시간을 최적화하기 위한 최초의 기법