왜 디스크에도 스케줄링이 필요한가

07~08편에서 다룬 CPU 스케줄링이 “여러 프로세스 중 CPU를 누구에게 먼저 줄까”를 정했다면, 이 편의 디스크 스케줄링(disk scheduling)은 “디스크에 쌓인 여러 입출력 요청 중 헤드를 어디로 먼저 움직일까”를 정하는 문제입니다. 하드디스크는 회전하는 원판(플래터) 위를 헤드(head)가 물리적으로 이동해 데이터를 읽고 쓰므로, 요청을 어떤 순서로 처리하느냐에 따라 헤드가 움직이는 총 거리가 크게 달라지고, 이는 곧 응답 시간의 차이로 이어집니다.

쉽게 말하면: 여러 층에 걸쳐 배달 요청이 들어온 엘리베이터가 있다고 합시다. 요청이 들어온 순서대로 갈지, 가까운 층부터 갈지, 한쪽 끝까지 쭉 갔다가 돌아올지에 따라 엘리베이터가 움직이는 총 거리가 달라집니다. 디스크 헤드도 똑같습니다.

1. 디스크 접근 시간의 구성

디스크에서 데이터 한 조각을 읽는 데 걸리는 시간은 세 부분으로 나뉩니다.

• 탐색 시간(seek time): 헤드가 목표 트랙(원판 위의 동심원 하나)까지 이동하는 시간. 디스크 스케줄링이 줄이려는 대상이 바로 이 시간입니다.
• 회전 지연(rotational latency): 헤드가 목표 트랙에 도착한 뒤, 원판이 회전해 원하는 섹터가 헤드 아래로 올 때까지 기다리는 시간.
• 전송 시간(transfer time): 실제로 데이터를 읽거나 쓰는 데 걸리는 시간.

세 시간 중 탐색 시간이 가장 크고 가변적이므로, 디스크 스케줄링 알고리즘은 여러 요청을 어떤 순서로 처리해야 탐색 시간(헤드 이동 거리)의 합이 최소가 되는가에 집중합니다.

2. 네 가지 디스크 스케줄링 알고리즘

• FCFS(First-Come First-Served): 요청이 들어온 순서 그대로 헤드를 이동시킵니다. 구현이 단순하지만 요청 위치가 들쭉날쭉하면 헤드가 디스크를 이리저리 오가며 이동 거리가 커집니다.
• SSTF(Shortest Seek Time First): 현재 헤드 위치에서 가장 가까운 요청부터 처리합니다. 이동 거리는 짧아지지만, 헤드 근처에 요청이 계속 몰리면 먼 곳의 요청이 한없이 뒤로 밀리는 기아 상태(starvation, 11편의 교착상태와는 다른, “순서가 계속 밀려 영원히 처리되지 못하는” 현상)가 발생할 수 있습니다.
• SCAN: 헤드가 한쪽 끝에서 반대쪽 끝까지 이동하며 그 경로에 있는 요청을 모두 처리한 뒤, 끝에 도달하면 방향을 바꿔 되돌아오는 방식입니다. 엘리베이터가 위아래로 오가는 모습과 닮아 엘리베이터 알고리즘이라고도 부릅니다.
• C-SCAN(Circular SCAN): SCAN처럼 한 방향으로 끝까지 이동하지만, 반대쪽 끝에 도달하면 되돌아오지 않고 처음 위치로 바로 점프한 뒤 같은 방향으로만 다시 진행합니다. 이렇게 하면 모든 트랙이 대기 시간 면에서 더 고르게 처리됩니다.

3. 손계산 예제 — 요청 큐 98, 183, 37, 122, 14, 124, 65, 67

디스크 트랙이 0번부터 199번까지 있고, 헤드가 현재 53번 트랙에 있으며, 처리해야 할 요청 큐가 다음 순서로 도착했다고 가정합니다.

요청 큐: 98, 183, 37, 122, 14, 124, 65, 67
현재 헤드 위치: 53

FCFS — 도착 순서 그대로

총 이동 거리 = 45 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = 640

SSTF — 매번 가장 가까운 요청 선택

총 이동 거리 = 12 + 2 + 31 + 24 + 2 + 59 + 146 + 23 = 299

결과 해석: 같은 요청 큐인데도 FCFS는 640, SSTF는 299로 절반에도 못 미치는 차이가 납니다. 이는 SSTF가 매번 가까운 곳부터 처리해 헤드가 큰 폭으로 왕복하는 상황을 줄이기 때문입니다. 다만 표의 6~7단계처럼, 183번 요청을 처리한 뒤 37번으로 가는 146칸의 큰 이동이 남아 있듯, SSTF도 특정 요청이 뒤로 밀리는 상황 자체를 막지는 못합니다.

SCAN — 큰 방향(199 쪽)으로 이동 후 반대로 복귀

헤드가 53에서 큰 번호 방향으로 이동한다고 가정하면, 경로에 있는 65, 67, 98, 122, 124, 183을 차례로 지나 디스크 끝(199)까지 이동한 뒤, 방향을 바꿔 37, 14를 처리하며 되돌아옵니다.

• 199 - 53 = 146: 헤드가 53에서 디스크 끝(199)까지 이동하는 거리(가는 길에 65, 67, 98, 122, 124, 183을 모두 지나며 처리).
• 199 - 14 = 185: 199에서 방향을 바꿔 가장 먼 남은 요청인 14까지 되돌아오는 거리(오는 길에 37도 함께 처리).

C-SCAN — 큰 방향으로 끝까지 간 뒤 처음으로 점프

C-SCAN은 199까지 간 뒤 반대로 꺾지 않고, 0번 트랙으로 곧장 점프한 다음 다시 같은 방향(큰 번호 쪽)으로 이동하며 남은 요청을 처리합니다.

• 199 - 53 = 146: 53에서 디스크 끝까지 이동(가는 길에 65, 67, 98, 122, 124, 183 처리).
• 199 - 0 = 199: 끝에서 처음 트랙(0)으로 점프하는 이동 거리(점프 구간도 헤드 이동 거리에 포함해 계산하는 것이 일반적입니다).
• 14 - 0 = 14: 0에서 다시 같은 방향으로 이동해 14, 37을 처리.

네 알고리즘 비교표

자주 틀리는 점: SCAN과 C-SCAN을 헷갈려, C-SCAN도 끝에서 방향을 반대로 바꾼다고 착각하는 경우가 많습니다. SCAN은 방향을 반대로 바꾸지만, C-SCAN은 끝에서 처음으로 점프한 뒤 같은 방향으로만 계속 진행한다는 점이 핵심 차이입니다. 또한 “이동 거리가 가장 짧은 알고리즘이 항상 최선”이라고 단정하는 것도 함정입니다. SSTF는 평균 이동 거리는 짧지만 기아 상태 위험이 있으므로, 시험에서는 “평균 응답 시간”과 “요청 간 형평성(기아 방지)“을 별개의 평가 기준으로 구분해서 물어봅니다.

핵심 정리

• 디스크 접근 시간은 탐색 시간, 회전 지연, 전송 시간으로 구성되며 디스크 스케줄링은 탐색 시간(헤드 이동 거리)을 줄이는 데 집중한다.
• FCFS는 단순하지만 이동 거리가 커질 수 있고, SSTF는 이동 거리는 줄이지만 기아 상태 위험이 있다.
• SCAN은 끝까지 갔다가 반대로 되돌아오고, C-SCAN은 끝에서 처음으로 점프한 뒤 같은 방향으로만 진행한다.
• 같은 요청 큐라도 알고리즘에 따라 총 이동 거리가 크게 달라지므로, 계산 문제는 각 단계의 이동 거리를 표로 나눠 빠짐없이 더해야 한다.

마무리 복습

참고 자료

• 운영체제 개론 KOCW 자료 
• 국가평생교육진흥원 독학학위제 - 과목별 평가영역