[운영체제] 23. Disk Format & Arm Scheduling

Sector 구조

 

하드디스크의 하나의 섹터는 위와 같은 포맷으로 되어있다.

우선 실제 데이터가 들어가는 부분이 제일 중요할 것이고 그 앞 뒤로는 부가 정보를 저장한다.

데이터는 보통 512byte 크기가 저장된다.

 

Preamble : bit pattern 으로 시작하며, 이 부분이 섹터의 시작임을 나타낸다.

또한 실런더 넘버와 섹터 넘버와 같은 정보가 들어있다.

 

ECC : Error-Correcting Code, read error 가 발생했을 때 복구할 수 있도록, 여분 정보가 저장되어 있다.

 

디스크에는 일부 섹터가 망가지는 것을 대비해서 여분의 spare sector를 남겨둔다.

그리고 이와 같이 초기 세팅을 하는 것을 low-level formatting 이라고 한다.

 

 

 

Cylinder Skew (★)

 

하드 디스크는 반시계 방향으로 돌고, 섹터 번호는 시계방향으로 증가하는 모습을 보여준다.

그런데 각 트랙을 보면, 각 트랙의 0번 섹터 위치가 서로 제각각임을 알 수 있다.

즉, 각 트랙의 섹터마다 오프셋이 존재하는 것을 알 수 있다.

 

오프셋이 존재하는 이유는 여러 트랙에 걸쳐서 저장된 데이터를 읽을 때, 하나의 트랙을 읽고 다음 트랙으로 arm이 이동하는 동안 원판이 회전하기 때문에 발생한다.

 

이제 하드디스크의 동작에 대한 정보가 주어질 때, 이 오프셋(실린더 스큐)을 계산해보자. (중요)

- 하드디스크는 10000rpm (분당 회전수)

- 트랙당 300 섹터

- track-to-track seek time = 800µs

 

오프셋은 결국 한 트랙일 이동했을 때, 몇 개의 섹터가 지나갔겠느냐를 계산하는 것과 같다.

이를 구하기 위해 섹터 하나를 지나가는데 걸리는 시간을 계산해서 800µs 동안 몇개의 섹터를 지나는 지 계산해보자.

 

먼저 하드디스크는 1분에 1만번 회전하므로, 1회전에는 60초 / 1만 시간이 걸린다.

이때 초를 µs 로 환산하면 60 * 100만 µs / 1만 시간이 걸리므로, 6000µs 가 걸린다.

이때 1 트랙은 300개 섹터로 구성되어 있으므로 300개 섹터를 지나는데 6000µs 가 걸리는 것과 같다.

따라서 1개 섹터를 지날 때는 20µs 가 걸림을 알 수 있다.

 

마지막으로 트랙을 이동하는데 걸리는 시간이 800µs 이므로, 이 시간동안에는 40개의 섹터를 지나는 것을 알 수 있다.

따라서 구하는 cylinder skew = 40섹터 이다.

 

 

 

 

위 그림은 디스크 interleaving 에 대한 그림을 보여준다.

각 디스크를 위에서 본 모습에서 트랙을 생략하고 섹터를 중심으로 보여주고 있다.

 

인터리빙은 섹터를 사이사이에 간격을 두고 저장하는 것을 말한다.

(a)는 인터리빙이 없는 경우를 보여주고, (b)는 1개의 인터리빙, (c)는 2개의 인터리빙이 존재하는 상황이다.

 

인터리빙을 두는 이유는 하나의 섹터에서 데이터를 읽은 뒤, 에러를 체크하고 버퍼에 올리는 동안 시간이 흐르고, 그 시간동안 디스크가 회전하기 때문에 바로 옆에 다음 섹터가 있다면 이 시간 동안 다음 섹터가 지나가 버리는 문제가 발생할 수 있기 때문에 둔다.

 

그래서 에러를 확인하고 전송하는데 걸리는 시간에 따라서 인터리빙을 1개 또는 2개를 두어 버퍼에 저장한 뒤에는 자연스럽게 다음 섹터를 읽을 수 있도록 한다.

(참고로 현대의 하드디스크는 모든 섹터마다 각각 버퍼가 존재해서 인터리빙을 할 필요가 없다고 한다.)

 

 

Disk Formatting 순서

1. low-level formatting

각 트랙과 섹터를 구분하고, 섹터 번호를 매핑한다. (실린더 스큐에서 보는 것처럼, 이때 트랙마다 오프셋이 존재한다.)

 

2. paritioning

파티션을 나누고 MBR (Master Boot Record) 와 파티션 테이블을 구성한다.

파티션 테이블에는 시작 섹터 위치와 파티션 크기를 저장한 엔트리가 저장되어 있다.

또 어느 파티션이 부팅되는 파티션인지에 대한 정보도 저장된다.

 

3. high-level formatting

각 파티션에 대해 진행하는 포맷팅

파일 시스템을 만들면서 boot block, super block, root directory 등을 구성한다.

 

---

Disk Arm Scheduling

디스크 블락을 읽는 시간은 총 3가지 시간의 합으로 나타낼 수 있다.

 

1. Seek Time (암이 적절한 실린더(원판)를 찾는 시간)

2. Rotational Delay (데이터가 존재하는 섹터까지 회전하는 시간)

3. actual transfer time (데이터 전송 시간)

 

이 외에도 읽어온 섹터에서 에러를 체크하고 수정하는 과정이 디스크 컨트롤러에 의해 수행되며,

1, 2, 3 중에서는 1번 seek time이 제일 긴 시간을 차지한다.

 

이때 여러 프로세스는 수시로 디스크에게 특정 블록에 대한 데이터 조회를 요청한다.

따라서 디스크는 이 요청을 어떤 순서대로 처리할 것인지 적절한 스케줄링 알고리즘이 필요하다.

 

FCFS (Fisrt Come Fisrt Serve)

요청이 들어오는 순서대로 처리한다.

 

 

위 그림은 하나의 실린더를 쭉 늘어놓은 모습을 보여준다.

이 예시를 기반으로 다양한 디스크 암 스케줄링 알고리즘의 성능을 비교해보자.

먼저 데이터 요청이 다음과 같은 순서로 온다고 해보자.

 

11 - 1 - 36 - 16 - 34 - 9 - 12

 

FCFS 알고리즘은 요청이 들어온 순서대로 처리한다.

따라서 디스크 암의 이동거리를 계산해보면 (참고)

 

10 + 35 + 20 + 18 + 25 + 3 = 111 만큼 이동한다.

 

매우 긴 이동거리를 갖는, 효율적이지는 않은 알고리즘임을 알 수 있다.

 

Shortest Seek First (SSF)

말 그대로 현재 위치에서 가장 짧은 거리로 이동하면 되는 요청을 먼저 처리한다.

 

 

 

같은 그림을 가지고 설명하면 요청 처리 순서는 다음과 같다.

 

시작위치는 11로 고정할 때,

11에서 제일 가까운 요청은 12

12에서 제일 가까운 요청은 9

9에서 제일 가까운 요청은 16

16에서 제일 가까운 요청은 1

1에서 제일 가까운 요청은 34

34에서 제일 가까운 요청은 36

 

순으로 이동하게 된다.

 

따라서 총 이동거리는 61 이다.

앞선 알고리즘보다는 많이 개선되었지만, 이 방법은 양 끝단에 대한 요청이 들어오는 경우, 해당 요청에 대한 처리가 미뤄지기 쉽다는 단점이 있다.

이동하다가 중간 중간 요청이 들어오면 내 현재 위치에서 가까운 요청을 처리하기 위해 그때 그때 방향을 꺾는데, 양 끝단에 있는 노드는 그 위치에서 거리가 항상 멀 가능성이 높기 때문이다.

 

 

Scan Algorithm (Elevator Algorithm)

이 알고리즘은 마치 실제 엘리베이터가 동작하듯 한쪽 방향으로만 훑으면서 지나가는길에 보이는 요청들을 처리하는 알고리즘이다.

그리고 한쪽 끝에 도달하면 방향을 반대로 틀어서 스캔한다.

 

11에서 시작한다면 이 방식을 사용하는 경우, 

 

11 - 12 - 16 - 34- 36 - 9 - 1 순으로 탐색하게 되며, 총 이동거리는 60이다.

(이 경우에는 더 짧게 나왔지만, 이동거리만 놓고보면 보통 SSF 알고리즘이 더 적은 이동거리를 갖는다.)

 

이 알고리즘은 현재 스캔 방향을 특정하기 위해 1bit의 정보를 저장해야 한다.

또한 이 알고리즘의 특징은 최대 이동 거리가 2 * 실린더 개수로 상한이 고정되어있다.

 

스캔 알고리즘은 이동하는 중에 새로운 요청이 들어오면 해당 요청을 지나가면서 모두 처리한다.

하지만 아무리 가깝더라도 진행 방향과 반대 방향으로 요청이 들어온다면 그 요청은 진행 방향을 바꾸었을 때 처리하게 된다.

 

C-Scan (Circular-Scan) algorithm

스캔 알고리즘과 비슷하지만, 방향을 바꾸지 않고 한 방향으로만 계속해서 스캔하는 알고리즘이다.

스캔 알고리즘에 비해 응답 시간에 대한 분산이 더 작다는 장점이 있다. (총 이동 거리와는 상관이 없다.)

이름이 서큘러인 이유는 위에서 본 일자 배열 모양을 둥그렇게 구부리면 반시계 방향으로 계속 돌면서 처리하는 것과 같기 때문에 서큘러라는 이름이 붙었다.