# 디스크 스케줄링

디스크 스케줄링 기법의 평가 기준은 단위 시간당 처리량, 평균 응답 시간, 응답 시간의 예측성이 있는데, 이 중 응답 시간의 예측성이란, 디스크 입출력 요구를 보낸 측에서 얼마 후 자신의 요청에 대한 서비스가 끝날 것인지를 추측할 수 있는가에 대한 것이다. 예측성을 판단하기 위한 요소로 응답 시간들의 분산을 사용하며, 분산이 작은 경우에는 예측성이 좋고, 큰 경우에는 예측성이 좋지 않다고 한다. 응답 시간의 분산을 줄이고 예측성을 높이는 스케줄링 기법을 사용하면 궁극적으로 무기한 연기 등의 상황을 방지할 수 있다.

1. FCFS(First Come First Served)

디스크 입출력 요구들을 도착한 순서대로 서비스하는 기법이며, 어떤 형태의 최적화 기법도 사용하지 않는다.

스케줄링으로 인한 오버헤드가 작아 디스크 입출력에 대한 부하가 작을 경우에 적합하다.

예) 

총 256개의 실린더, 현재 헤드의 위치는 100이고, 현재 큐에 도착한 입출력 요구가 아래와 같다.

160

200

90

170

20

190

120

130

가장 먼저 입력된 요구인 160을 시작으로,

160 → 200 → 90 → 170 → 20 → 190 → 120 → 130

순으로 처리 되며, 헤드의 총 이동 거리는

60 + 40 110 +80 +150 +170 + 70 +10 = 690 이다.

2. SSTF(Shortest Seek Time First)

현재 헤드의 위치로부터 가장 가까운 요구를 먼저 서비스한다.

큐의 요구들을 처리하는 동안 헤드가 이동해야 하는 거리를 극소화하며, 따라서 단위 시간당 처리량을 극대화시키는 기법이다. 시스템 측의 부하가 크지 않은 경우에는 평균 응답 시간도 어느 정도 낮게 유지할 수 있다. 하지만, 디스크 입출력 요구들에 대한 응답 시간의 분산이 커져 응답 시간에 대한 예측성이 저하된다.

예) 

총 256개의 실린더, 현재 헤드의 위치는 100이고, 현재 큐에 도착한 입출력 요구가 아래와 같다.

160

200

90

170

20

190

120

130

헤드와 가장 가까운 90을 먼저 처리한다. 이후, 90에서 가장 가까운 120을 처리한다. 따라서,

90 → 120 → 130 → 160 → 170 → 190 → 200 → 20

순으로 처리 되며, 헤드의 총 이동 거리는

10 +30 +10 + 30 + 10 + 20 + 10 + 180 = 300 이다.

이 기법은 헤드가 일정 영역을 벗어나지 못하고 그 영역 안의 실린더들에 대한 요구들만을 계속해서 처리하는 무기한 연기 상황이 발생할 수 있으며, 이를 제거하기 위한 기법을 SCAN기법이 제시되었다.

3. SCAN

SSFT와 비슷한 형태로 큐에 있는 요구들을 서비스하지만, 현재 헤드의 진행 방향으로만 디스크 입출력 요구들을 처리하며, 마지막 실린더, 즉 양 끝의 실린더에 도착했을 때에만 방향을 전환하여 나머지 요구들을 처리한다.

예) 

총 256개의 실린더, 현재 헤드의 위치는 100이고, 현재 큐에 도착한 입출력 요구가 아래와 같다.

160

200

90

170

20

190

120

130

헤드와 가장 가까운 90을 먼저 처리한다. 90은 100보다 안쪽에 위치하므로, 헤드는 안쪽으로 움직이며 요구를 처리한다. 따라서, 90을 처리한 후에 20을 처리하며, 헤드가 끝에 다다르면 반대로 진행하면서 요구를 처리한다.

요구가 처리되는 순서는,

90 → 20 → 120 → 130 → 160 → 170 → 190 → 200

이며, 총 이동 거리는

10 +70 + 20(0까지 이동한 거리) + 120 +10 + 30 + 10 + 20 + 10 = 300 이다.

4. LOOK 스케줄링

SCAN과 거의 유사하며, 헤드가 진행하는 도중 진행 방향의 앞쪽으로 더 이상의 요구가 없으면 양 끝의 실린더까지 진행하지 않고 그 자리에서 방향을 바꾼다.

예) 

총 256개의 실린더, 현재 헤드의 위치는 100이고, 현재 큐에 도착한 입출력 요구가 아래와 같다.

160

200

90

170

20

190

120

130

헤드와 가장 가까운 90을 먼저 처리한다. 90은 100보다 안쪽에 위치하므로, 헤드는 안쪽으로 움직이며 요구를 처리한다. 따라서, 90을 처리한 후에 20을 처리한다. 진행하는 방향에 대해 더 이상의 요구가 없으므로 헤드는 반대 방향으로 진행하며 요구를 처리 한다. 요구가 처리되는 순서는,

90 → 20 → 120 → 130 → 160 → 170 → 190 → 200

이며, 총 이동 거리는

10 + 70 + 100 +10 + 30 + 10 + 20 + 10 = 260 이다.

5. N-step SCAN

SCAN과 같지만, 헤드가 방향을 바꾸는 시점에서 큐에 대기 중인 요구들만을 대상으로 서비스를 진행하며, 서비스가 진행 중에 큐에 도착하는 요구들에 대해서는 다음번 방향을 바꾼 후에 처리한다.

예) 

총 256개의 실린더, 현재 헤드의 위치는 100이고, 현재 큐에 도착한 입출력 요구가 아래와 같다.

160

200

90

170

20

190

120

130

헤드와 가장 가까운 90을 먼저 처리하다, 80의 요구가 들어왔다면, 이 80이 비록 90보다 안쪽에 위치하더라도 이 요구는 처리되지 않는다. 80이라는 요청은 헤드가 끝(0)에 다다른 후, 진행 방향이 바뀌었을 때 비로소 처리된다. 따라서, 요구가 처리되는 순서는,

90 → 20 → 80 → 120 → 130 → 160 → 170 → 190 → 200

이며, 총 이동 거리는

10 + 70 + 0 + 80 + 40 +10 + 30 + 10 + 20 + 10 = 280 이다.

이 기법은 SSTF나 SCAN보다 응답 시간의 분산이 작아지며, 무기한 연기의 가능성은 완전히 사라진다.

6. C-SCAN(Circular-SCAN)

SCAN과 비슷하지만, 서비스 방향을 안쪽 또는 바깥쪽으로 미리 정해놓고 정해진 방향으로 헤드가 이동할 때에만 큐의 요구들을 처리한다.

예) 

총 256개의 실린더, 현재 헤드의 위치는 100이고, 현재 큐에 도착한 입출력 요구가 아래와 같다.

160

200

90

170

20

190

120

130

안쪽으로 진행하며 요구들을 처리하다 디스크의 끝에 도달했을 때, 255 실린더로 요구에 대한 처리없이 이동하여 다시 안쪽으로 진행하며 요구들을 처리한다. 이에 따라 처리되는 요구의 순서는,

90 → 20 → 200 → 190 →170 → 160 → 130 → 120

이며, 총 이동 거리는,

10 + 70 + 20 + 255 + 55 +10 + 20 + 10 + 30 + 10 = 490 이다.

이 기법은 응답 시간의 분산이 매우 작으며, 따라서 응답 시간에 대한 예측성이 매우 높다.

C-LOOK은 C-SCAN과 기본적으로 비슷하지만, 헤드의 진행 방향으로 더 이상의 요구가 없으면 즉시 방향을 전환한다.

7. Eschenbach

디스크 시스템의 입출력 요구들이 대기하는 큐에는 같은 실린더에 대한 서비스를 원하는 요구들이 여러 개 있을 수 있다. 더구나 한 실린더 내의 서로 다른 표면에 대한 같은 번호의 섹터들을 대상으로 하는 입출력 요구들도 큐에 동시에 존재할 수 있는데, 이런 경우 해당 실린더에 대한 요구들을 모두 처리하기 위해서는 헤드가 실린더로 이동한 후에 디스크 팩이 여러 번 회전하는 동안 기다려야 한다.

Eschenbach는 헤드가 진행하는 과정에서 각 실린더에 대해 디스크 팩의 한번의 회전 시간 동안만 입출력 요구들을 처리한다. 즉, 한 회전 동안 서비스를 받지 못하는 요구들에 대한 처리는 다음으로 미룬다. 이를 위해서는 한 실린더 내의 트랙이나 섹터들에 대한 요구들을 별도로 순서화하는 메커니즘이 필요하며, 결국 Eschenbach는 탐구 시간의 최적화와 회전 지연 시간의 최적화를 동시에 추구한다.

8. 섹터 큐잉(sector queueing)

SLTF(Shortest Latency Time First)라고도 한다.

디스크 시스템의 각 섹터별로 별도의 큐를 두어 관리하며, 하나의 실린더 또는 트랙에 대한 여러 개의 입출력 요구가 도착할 경우 이들을 각 섹터별로 설정되어 있는 큐에 삽입한다.

디스크 헤드의 탐구 과정이 끝나고 헤드가 특정 실린더에 도착한 뒤에 헤드 아래에 먼저 도착하는 순서대로 각 섹터에 대한 서비스를 진행한다. 이는 회전 지연 시간에 대한 스케줄링 기법으로 거의 최적에 가까우며, 대부분의 시스템에서 필요한 경우 이 섹터 큐잉 기법을 사용한다.

참조 자료

엄영익·정태명 공저, 『컴퓨터 운영체제론』, 생능출판사