디스크 스케줄링 알고리즘과 저장장치 I/O 요청 처리

I/O 요청 순서가 접근 시간을 바꾸는 이유

운영체제는 여러 프로세스가 동시에 보낸 디스크 I/O 요청을 어떤 순서로 처리할지 결정해야 한다. 하드디스크에서는 헤드가 트랙을 옮기는 탐색 시간과 섹터를 기다리는 회전 지연이 발생하므로, 요청 순서는 전체 처리 성능에 직접 영향을 준다.

디스크 접근 시간은 탐색 시간, 회전 지연, 전송 시간, 컨트롤러 지연으로 구성된다. 이 가운데 헤드 이동에 따른 탐색 시간이 가장 큰 비중을 차지하므로, 스케줄링은 불필요한 헤드 이동을 줄이는 데 초점을 둔다.

⤢✕

스케줄러가 다루는 목표는 서로 충돌할 수 있다. 평균 대기 시간을 낮추고 처리량을 높이는 한편, 특정 요청이 무한히 밀리지 않게 하며 일관된 응답 시간을 제공해야 한다.

도착 순서를 따르는 FCFS

FCFS(First-Come First-Served)는 요청이 들어온 순서대로 처리하는 방식이다. FIFO 큐로 구현할 수 있어 단순하고, 먼저 들어온 요청이 계속 뒤로 밀리지 않으므로 기아가 발생하지 않는다.

반면 요청 위치가 무작위로 분포하면 헤드가 넓은 범위를 오가게 된다. 긴 요청이 뒤따르는 짧은 요청을 지연시키는 컨보이 효과도 생길 수 있다.

요청 큐: 98, 183, 37, 122, 14, 124, 65, 67
현재 헤드 위치: 53
FCFS 순서: 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67
총 헤드 이동: |98-53| + |183-98| + |37-183| + ... = 640 트랙

가까운 요청부터 처리하는 SSTF

SSTF(Shortest Seek Time First)는 현재 헤드 위치에서 가장 가까운 요청을 우선 처리한다. 매 순간 남은 요청 가운데 이동 거리가 가장 짧은 대상을 고르는 욕심쟁이 알고리즘이며, 전역 최적해를 보장하지는 않아도 FCFS보다 평균 탐색 시간을 크게 줄일 수 있다.

문제는 헤드 주변에 요청이 계속 들어올 때다. 양 끝 트랙의 요청은 우선순위를 얻지 못한 채 대기할 수 있으며, 가운데 트랙 요청에 처리 기회가 집중된다.

요청 큐: 98, 183, 37, 122, 14, 124, 65, 67
현재 헤드 위치: 53
SSTF 순서: 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183
총 헤드 이동: |65-53| + |67-65| + |37-67| + ... = 236 트랙

헤드의 진행 방향을 활용하는 SCAN 계열

SCAN은 엘리베이터처럼 헤드가 한 방향으로 이동하면서 경로 위의 요청을 처리하고, 끝에 닿으면 방향을 바꾸는 방식이다. 0번 트랙과 최대 트랙 사이를 왕복하므로 SSTF에서 발생할 수 있는 기아를 완화한다.

다만 양 끝 트랙은 대기 시간이 길어질 수 있고, 가운데 트랙은 양쪽 방향의 스캔에서 더 자주 방문된다. FCFS보다 응답 시간이 더 일관적이라는 특성이 있다.

요청 큐: 98, 183, 37, 122, 14, 124, 65, 67
현재 헤드 위치: 53, 방향: 증가
SCAN 순서: 65 → 67 → 98 → 122 → 124 → 183 → 199(끝) → 37 → 14
총 헤드 이동: (199-53) + (199-14) = 331 트랙

C-SCAN(Circular SCAN)은 한 방향으로만 요청을 처리한다. 끝에 도달하면 시작점으로 이동하지만, 그 복귀 구간에서는 요청을 서비스하지 않는다. 트랙을 원형으로 본다는 발상이며, SCAN보다 대기 시간을 더 균등하게 만들 수 있다. 대신 복귀하는 동안 서비스가 중단되고 처리량은 SCAN보다 약간 낮을 수 있다.

요청 큐: 98, 183, 37, 122, 14, 124, 65, 67
현재 헤드 위치: 53, 방향: 증가
C-SCAN 순서: 65 → 67 → 98 → 122 → 124 → 183 → 199(끝) → 0(시작) → 14 → 37
총 헤드 이동: (199-53) + (199-0) + (37-0) = 382 트랙

요청이 있는 범위만 훑는 LOOK과 C-LOOK

LOOK은 SCAN의 왕복 방식은 유지하되, 실제 요청이 있는 최대·최소 트랙까지만 이동한다. 디스크의 물리적 끝까지 갈 필요가 없으므로 불필요한 이동을 줄일 수 있으며, 대부분의 실제 시스템에서 사용된다.

C-LOOK은 C-SCAN처럼 한 방향으로 요청을 처리하지만 실제 요청 범위 안에서만 이동한다. 양쪽 끝까지 이동하지 않아 C-SCAN보다 헤드 이동 거리를 줄일 수 있고, 현대 OS에서 많이 채택된다.

요청 큐: 98, 183, 37, 122, 14, 124, 65, 67
현재 헤드 위치: 53, 방향: 증가
LOOK 순서: 65 → 67 → 98 → 122 → 124 → 183 → 37 → 14
총 헤드 이동: (183-53) + (183-14) = 299 트랙

C-LOOK 순서: 65 → 67 → 98 → 122 → 124 → 183 → 14 → 37
총 헤드 이동: (183-53) + (183-14) + (37-14) = 336 트랙

큐를 분리해 새 요청의 영향을 제한하는 방식

N-step SCAN은 요청 큐를 N개씩의 부분 큐로 나누고, 한 부분 큐를 SCAN으로 처리하는 동안 새 요청은 다음 부분 큐에 넣는다. 처리 중인 배치를 신규 요청이 방해하지 않으므로 응답 시간과 공평성의 균형을 잡을 수 있고, 무한 대기를 막으며 최대 대기 시간도 예측할 수 있다. 다만 N 값은 성능에 영향을 준다.

FSCAN은 서비스 큐와 대기 큐를 따로 둔다. 현재 SCAN이 처리하는 요청은 서비스 큐에 고정하고, 처리 중 도착한 요청은 대기 큐에 넣는다. 서비스 큐가 끝나면 두 큐의 역할을 바꾼다. N-step SCAN에서 N=무한대인 경우이며, 두 개 큐로 구현할 수 있지만 신규 요청은 한 사이클을 기다린다.

알고리즘을 비교할 때 보는 지점

평균 대기 시간은 모든 요청의 대기 시간 합을 요청 수로 나눈 값이다. 낮을수록 사용자 응답성이 좋아지며, 알고리즘 비교에서는 FCFS > SCAN > SSTF로 제시된다. 다만 실제 결과는 접근 패턴에 따라 달라진다.

총 헤드 이동 거리는 탐색 시간을 추정하는 기준이다. 이동 거리가 줄면 전력 소비를 낮추고 이동 시간을 줄여 처리량을 높일 수 있으므로, 대부분의 알고리즘이 이를 주요 최적화 대상으로 삼는다.

공평성은 요청별 대기 시간의 표준편차, 최대 대기 시간, 기아 발생 여부, 중요한 요청에 우선순위를 줄 수 있는지를 함께 본다. 실시간 시스템에서는 비슷한 요청이 비슷한 응답 시간을 받는지와 최악의 응답 시간을 보장할 수 있는지가 중요하며, SLA(Service Level Agreement)와도 연결된다.

SSD에서는 무엇이 달라지는가

SSD에는 기계적 헤드가 없고 모든 위치의 접근 시간이 동일하다. 다중 채널과 칩을 통한 병렬 접근이 가능하며, 쓰기 횟수를 분산하는 웨어 레벨링도 고려해야 한다.

이 특성 때문에 SSD에서는 복잡한 요청 정렬보다 FCFS가 선호될 수 있다. NCQ(Native Command Queuing)는 드라이브 내부 최적화에 쓰이고, TRIM 명령은 삭제된 블록 정보를 전달한다. 순차 쓰기를 선호해 쓰기 증폭을 최소화하는 관점도 필요하다.

NOOP 스케줄러는 요청 순서를 유지하며 별도 스케줄링을 하지 않는다. SSD에서 가장 효율적이고 CPU 오버헤드를 줄이며, 요청 최적화를 드라이브 내부 컨트롤러에 맡기는 방식이다.