[운영체제] 22. HDD and RAID

Reference - Operating Systems: Three Easy Pieces

 

 

https://pages.cs.wisc.edu/~remzi/OSTEP/

Operating Systems: Three Easy Pieces

 

 

HDD

 

먼저 HDD의 구조를 살펴보자.

 

각 요소들의 명칭은 위와 같고, platter는 양면으로 읽고 쓴다. platter의 spindle부터 platter의 가장자리까지의 원둘레를 쪼개서 얻는 각각의 concentric ring을 track이라 하고, 각 track은 gap으로 분리된 sector를 가지고 있다.

 

이러한 디스크는 병렬적으로 쌓여져있고, ARM은 아래 그림처럼 같이 움직이게 된다. 

 

이렇게 ARM이 같이 움직이면서 얻는 병렬적인 track을 실린더라고 한다.

 

디스크는 데이터를 읽을 때 물리적 특성으로 seek time과 rotational latency가 필연적으로 존재한다.

seek time은 arm이 상하로 움직이며 데이터를 찾는 것이고, rotational latency는 플래터가 회전하는 속도에 의해 데이터를 찾는 속도가 결정된다는 것이다. transfer time은 read에 걸리는 시간이다. 아래 그림을 보면 이해할 수 있다.

 

Rotational rate, Average seek time, Avg # sectors/track을 알면 Disk Access time을 구할 수 있다.

이 Access time은 seek time과 rotational latency에 지배적이다.

 

디스크는 복잡한 디스크 내부를 연속된 4KB logical block으로 추상화시켜 os에게 제공한다.

이때 필요한 mapping은 disk controller 하드웨어에 의해 가능해진다. 이때 디스크는 물리적인 한계로 인해, 연속적인 물리적 섹터로 매핑해야 좋은 성능을 낼 수 있다. 또한 물리적 손상 및 기타 오류로 bad sector가 발생할 수 있는데, 다른 sector로 복사하는 과정을 디스크 내에서 관리한다.

 

Disk Scheduling

 

access time과 throughput을 향상시키려면 어떻게 해야할까?

그 방법은 disk arm의 movement를 최소화하는 것이다.

app에서 I/O request가 일어나면, os에서 성능 효율성을 위해 bulky하게 전송하기 위해 I/O queue에서 잠시 보관한다.

목표는 LBA number(=head pointer) 간의 차이를 최소화하는게 스케줄링의 기본 아이디어다.

Queue가 있기에 스케줄링 알고리즘을 적용할 수 있는데, First Come First Served가 기본 아이디어다.

cost에 해당하는 total head movement는 모든 절댓값 차이의 sum이다.

 

FCFS

 

Shortest Seek Time First를 사용하면, header의 위치에서 가장 가까운 값부터 정렬한다.

하지만 이 방법은 starvation이 발생한다. 헤더에 가까운 프로세스를 먼저 보기에, 해당 프로세스 위주로 접근하게 된다.

 

SSTF

 

이를 해결하기 위한 방법으로 SCAN(called Elevator Algorithm)이 있다. 이 방법은 양과 음 중 한쪽 방향으로 계속 가다가 LBA num이 (0, max)중 하나를 찍은 뒤 반대방향으로 이동한다. 이때 (0, max)를 찍고 가는 이유는 반댓방향으로 방향을 바꾸는 중간에 0 혹은 max에 가까운 값이 들어오면 디스크의 물리적 특성상 rotation 때문에 오랫동안 wait해야되기 때문이다. (물론 구현 시 0, max를 안찍게 구현이 가능하기도 하다.)

 

SCAN

 

SCAN에서 wait 문제가 남아있는데, 이를 해결하기 위해 C-SCAN이 나왔다. 한 방향의 끝을 찍으면 반댓방향으로 프로세스를 접근하지않고 쭉 이동한 뒤 다시 프로세스를 읽어들이는 방법으로 긴 wait time을 방지한다.

 

C-SCAN

SSTF는 일반적이지만 starvation 문제가 있고, heavy load system에 대해선 SCAN과 C-SCAN이 좋게 작용한다.

 

RAID

 

Redundant Array of Inexpensive Disks의 약자로, 느린 디스크 여러개를 모아서 빠르고, 용량이 크고, reliable한 disk system을 만드는 방법론이다.

 

운영체제 입장에선 디스크가 몇개 있는진 상관없다. 선형 logical block으로 추상화되기 때문에, 큰 디스크 하나가 있는걸로 느낀다.

 

 

Evaluation metric은 reliablity(disk faults rate), capacity, performance로 측정한다.

 

RAID 0 - 각 disk에 다른 block을 넣는다. 안정성이 매우 안좋다. failure rate가 디스크 수에 비례해 커진다.

space efficiency는 1이다.

RAID 1 - 각 disk에 같은 block을 넣는다. 안정성이 매우 좋다. failure rate는 디스크 수에 비례해 줄어들고, space efficiency는 반비례한다. (=1/n)

RAID 4 - XOR을 통한 parity disk 하나를 만든다. 하나의 디스크에 failure가 발생해도 아래와 같이 XOR을 진행해 복구가 가능하다.

문제는 하나의 disk가 바뀌더라도 parity를 바꿔주어야하는 I/O가 발생한다. update가 많은 시스템에서 효율이 안좋다. space efficiency는 1-1/n이고, failure rate는 1-(disk 모두 살 확률 + 하나만 깨질 확률)이다.

failure rate r=0.05, 총 디스크 수 n=4라 가정하면,  0.95^4+0.95^3*0.05*4 = 1.4%다.

 

RAID 5 - parity를 여러 disk에 분산하는 방법으로, load balancing 측면에서 좋다.

RAID 6 - disk 내에 parity block의 수를 하나 이상으로 늘리면 XOR이 두개 이상의 failure에 대해서도 안정성을 보장할 수 있어진다. reliablity가 훨씬 올라간다.