디스크 스케줄링과 헤드 이동 최적화

요청 큐의 순서가 디스크 접근 시간을 바꾼다

디스크 스케줄링은 디스크 데이터를 읽고 쓰기 위해 헤드가 지나갈 경로를 정하는 기법이다. 여러 I/O 요청이 큐에 쌓였을 때 처리 순서를 조정해 암 이동을 줄이고, 처리량과 평균 응답 시간을 개선하며, 요청별 응답 시간 편차를 낮추는 데 목적이 있다. 동시에 특정 요청이 계속 밀리는 기아(Starvation)도 피해야 한다.

이 판단에는 탐색 시간, 회전 지연 시간, 전송 시간이 함께 관여한다. 이동 헤드 디스크에서는 특히 헤드의 물리적 이동과 회전 대기가 스케줄링 선택에 직접적인 영향을 준다.

접근 시간은 헤드 이동과 회전 대기로 나뉜다

탐색 시간(Seek Time)은 헤드가 현재 트랙에서 대상 트랙까지 이동하는 데 걸리는 시간이다. 디스크 접근 시간에서 40-50%를 차지하며, 암의 물리적 이동 거리와 비례하므로 스케줄링의 주요 최적화 대상이 된다. HDD의 평균 탐색 시간은 약 5-10ms이고, 최대 탐색 시간은 전체 트랙을 이동하는 시간이다.

회전 지연 시간(Rotational Latency)은 헤드가 목표 트랙에 도착한 뒤 원하는 섹터가 헤드 아래로 올 때까지 기다리는 시간이다. 회전 속도에 반비례하며 평균 회전 지연은 0.5회전 시간이다.

• 7200 RPM: 평균 4.17ms
• 10000 RPM: 평균 3ms
• 15000 RPM: 평균 2ms

전송 시간(Transfer Time)은 디스크와 메모리 사이에서 데이터를 실제로 옮기는 시간이다. 전송 속도와 데이터 크기에 비례하며, 접근 시간에서는 비교적 작은 부분을 차지한다. HDD 전송 속도는 약 100-200 MB/s이고, 4KB 블록 전송에는 약 0.02-0.04ms가 걸린다.

총 액세스 시간 = 탐색 시간 + 회전 지연 시간 + 전송 시간

전체 접근 시간에서 탐색 시간과 회전 지연 시간은 각각 40-50%, 전송 시간은 5-10%를 차지한다.

큐 도착 순서를 그대로 따르는 FCFS

FCFS(First-Come-First-Served)는 요청이 들어온 순서대로 처리한다. 구현이 단순하고 먼저 도착한 요청이 뒤로 밀리지 않으므로 기아가 없다. 반면 요청 위치를 고려하지 않기 때문에 탐색 시간이 길어지고 성능은 낮을 수 있다.

예를 들어 요청 큐가 98, 183, 37, 122, 14, 124, 65, 67이고 현재 헤드가 53에 있다면, 이동 순서는 다음과 같다.

• 이동 순서: 53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67
• 총 이동 거리: 640 트랙

I/O 요청이 적고 공정성을 우선하는 단순한 시스템에 적합하다.

가까운 요청을 고르는 SSTF와 기아 문제

SSTF(Shortest Seek Time First)는 현재 헤드 위치에서 탐색 거리가 가장 짧은 요청을 먼저 처리한다. 평균 탐색 시간을 낮춰 처리량을 높일 수 있지만, 멀리 떨어진 요청은 계속 가까운 요청에 밀려 무한히 기다릴 수 있다. 응답 시간 편차도 커질 수 있다.

같은 요청 큐와 현재 헤드 위치에서는 다음 순서가 된다.

• 이동 순서: 53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183
• 총 이동 거리: 236 트랙

처리량이 최우선이고 기아 문제를 무시할 수 있는 환경에서 선택할 수 있다.

방향을 정해 처리하는 SCAN 계열

SCAN은 헤드가 한 방향으로 이동하면서 경로에 있는 요청을 처리하고, 끝에 닿으면 방향을 바꿔 반대 방향 요청을 처리한다. SSTF에서 발생할 수 있는 기아를 해소하고 한 사이클 안에서 요청 처리를 보장한다. 다만 중간 트랙의 서비스 빈도가 양 끝 트랙보다 높다.

요청 큐가 98, 183, 37, 122, 14, 124, 65, 67이고, 현재 헤드가 53, 이동 방향이 증가 방향이면 다음과 같이 움직인다.

• 이동 순서: 53 → 65 → 67 → 98 → 122 → 124 → 183 → 199(끝) → 37 → 14
• 총 이동 거리: 331 트랙

C-SCAN(Circular SCAN)은 한 방향에서만 요청을 처리한다. 끝에 도달하면 요청을 처리하지 않은 채 처음으로 돌아가 같은 방향으로 다시 처리한다. 양 끝 트랙의 대기 시간을 더 공평하게 만들고 응답 시간 편차를 더 균일하게 하지만, SCAN보다 처리량은 약간 감소한다.

• 이동 순서: 53 → 65 → 67 → 98 → 122 → 124 → 183 → 199(끝) → 0(처음) → 14 → 37
• 총 이동 거리: 382 트랙

일반적인 시스템에서 기아를 방지하면서 균형 잡힌 성능이 필요하면 SCAN 또는 C-SCAN을 고려할 수 있다.

끝 트랙까지 가지 않는 LOOK 계열

LOOK은 SCAN처럼 한 방향 요청을 처리하지만 물리적 끝 트랙까지 이동하지 않는다. 해당 방향에서 마지막 요청까지만 처리한 뒤 방향을 바꾼다. SCAN보다 불필요한 이동을 줄이며, 기아 없이 동작한다.

C-LOOK은 C-SCAN의 방향성을 유지하면서도 끝 트랙까지 가지 않는다. 한 방향의 마지막 요청을 처리한 다음 반대편의 첫 요청으로 점프한다. C-SCAN보다 효율적이고 응답 시간을 균일하게 유지한다.

LOOK과 C-LOOK은 현대 디스크 시스템에서 높은 성능과 공정성이 함께 필요한 경우에 적합하며 가장 널리 사용된다.

N-Step SCAN은 요청을 N개 단위로 묶은 뒤 각 그룹에 SCAN을 적용한다. 현재 그룹을 처리하는 동안 새로 들어온 요청은 다음 그룹으로 넘긴다. 이 방식은 요청의 무한 연기를 방지하고 응답 시간 상한과 공정성을 높인다.

회전 위치를 우선하는 고정 디스크 스케줄링

SLTF(Shortest Latency Time First)는 최소 회전 지연 시간을 가진 요청을 먼저 처리한다. 현재 헤드가 있는 트랙에서 가장 가까운 섹터를 고르므로 회전 지연을 줄이는 데 초점이 맞춰져 있다. 같은 트랙에 여러 요청이 있을 때 유용하며 드럼 메모리와 고정 헤드 디스크에 적합하다.

SPTF(Shortest Positioning Time First)는 탐색 시간과 회전 지연 시간의 합이 가장 작은 요청을 우선한다. SSTF와 SLTF를 결합해 전체 위치 결정 시간을 줄이며, 고성능 디스크 시스템과 데이터베이스 서버에 적용할 수 있다.

알고리즘별 특성과 선택 기준

알고리즘	평균 탐색 시간	처리량	기아 가능성	응답 시간 편차	구현 복잡도
FCFS	높음	낮음	없음	매우 큼	매우 낮음
SSTF	낮음	높음	있음	큼	낮음
SCAN	중간	중간	없음	중간	중간
C-SCAN	중간	중간	없음	작음	중간
LOOK	낮음	높음	없음	중간	중간
C-LOOK	낮음	높음	없음	작음	중간

HDD 기반 시스템에서는 탐색 시간과 회전 지연 시간을 어떻게 줄일지에 따라 스케줄링 전략이 달라진다. FCFS는 단순성과 공정성이 강점이고, SSTF는 처리량을 높이는 대신 기아 가능성을 감수한다. SCAN과 C-SCAN은 이동 방향을 관리해 기아를 줄이며, LOOK과 C-LOOK은 그 과정에서 끝 트랙까지의 불필요한 이동을 없앤다.

SSD의 등장으로 디스크 스케줄링의 중요성은 감소했다. SSD는 플래시 메모리를 사용하고 기계적 이동이 없으므로 Seek Time이 거의 0이며, 랜덤 접근과 순차 접근의 성능 차이도 감소한다. 따라서 전통적인 탐색 시간 최적화 알고리즘의 중요성은 낮아지고, Wear Leveling과 Garbage Collection이 중요한 고려 대상이 된다. 빠른 응답이 필요한 자주 접근하는 데이터는 SSD에 두고 대용량 저장은 비용 효율적인 HDD에 두는 방식으로 함께 사용하기도 하며, OS 레벨에서 데이터 배치를 자동으로 최적화할 수도 있다.