# 디스크 구조와 스케줄링

1. 디스크 구조와 접근 과정

1) 디스크 팩

● 데이터를 영구적으로 보존할 수 있는 기록 매체

● 여러 장의 디스크 원반들을 같은 중심축에 쌓아 놓음

● 섹터(Sector) : 물리적으로 디스크 시스템에 데이터가 저장되거나 판독되는 단위

● 트랙(Track) : 디스크 원반의 한 면에서 중심으로부터 같은 거리에 있는 섹터의 집합

● 실린더(Cylinder) : 디스크 팩에서 같은 반지름을 갖는 트랙들의 집합

● 디스크 원반(Platter) : 원형 금속판의 양면에 자성 물질을 입혀 데이터를 기록하고 판독할 수 있도록 만든 장치

● 표면(surface) : 한 장의 드스크 원반에는 윗면과 아래면 등 두 개의 면을 가짐

2) 디스크 드라이브

디스크 팩에 데이터를 기록하거나 기록된 데이터를 판독하는 장치

스핀들(spindle) : 디스크 팩을 고정시킴. 디스크 팩의 회전축 역할

붐(boom) : 암(arm)과 헤드(head)를 지탱하면서 헤드로 하여금 원하는 트랙에서 데이터를 판독하거나 저장할 수 있도록 위치 이동시킴

암(arm) : 헤드를 고정시키고 지탱하는 역할

헤드(head) : 실제 디스크 표면으로부터 데이터를 판독하거나 기록하는 역할

3) 디스크 시스템에서의 물리적 주소

디스크 시스템에서 데이터 전송 단위는 물리적으로 섹터 단위이다. 임의의 시스템에서 하나의 섹터를 정확히 지정하기 위해서는 실린더 번호(또는 트랙 번호)와 표면 번호, 그리고 섹터 번호가 필요하다.

Cylinder Number

Surface Number

Sector Number

이 같은 물리적 주소는 표현 방법이 복잡해 좀 더 간단한 논리적인 상대주소 표현법이라는 주소 지정 기법을 사용하기도 한다. 이 기법에서는 디스크 시스템 측의 데이터 전체를 블럭들의 나열로 보고 각 블럭들에 대해 블럭 번호를 부여하여 임의의 블럭에 접근할 수 있게 한다.

B0

B1

B2

…

Bn-2

Bn-1

4) 디스크 시스템에서의 데이터 접근 과정

① 디스크 주소 상의 실린더 번호(또는 트랙 번호)를 보고 디스크의 헤드를 실린더로 이동시킨다. 이 과정을 탐구(seek) 과정이라 하며, 이에 필요한 시간을 탐구 시간(seek time)이라 한다.

② 디스크 헤드가 지정된 실린더를 찾아간 후에 헤드는 섹터 번호에 따라 지정된 섹터가 헤드 아래에 도착할 때까지 기다리게 되며 이에 필요한 시간을 회전 지연 시간(rotati0onal delay, latency time)이라 한다.

③ 지정된 섹터가 헤드 아래에 도착하면 디스크 주소 상의 표면 번호에 따라 필요한 헤드가 동작을 시작하여 해당 섹터를 읽어 전송하거나 정송되어온 데이터를 해당 섹터에 기록한다. 이에 필요한 시간을 데이터 전송 시간(data transmission time)이라 한다.

일반적으로, 탐구 시간-회전 지연 시간 순으로 시간이 오래 걸린다.

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

2. 디스크 스케줄링

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)라고도 한다.

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

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

참조 자료

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

http://forensic-proof.com/archives/355