HDD: Hard Disk Drives

  여지껏 CPU나 memory를 가상화하거나 스레드, synchronization 등을 통해 concurrency를 얻어내는 방법등에 대해 알아보았다. 이번 글에서는 어떻게 정보를 연속성 있게, 즉 시스템이 꺼져도 정보가 날아가지 않게 storage에 저장할 수 있는 방법에 대해 알아볼 것이다.

I/O Device

A Typical I/O Device

fig 1

  fig 1에서 키보드 장치를 확인할 수 있다. 그리고 키보드에는 매우 작은 micro controller(fig 1에서는 ARM Cortex-M3)가 있는데 이것이 CPU나 메모리와 통신하면서 장치를 사용하게 된다. 이 micro controller 내부에는 CPU, 메모리 등 여러가지 구성요소가 있고 이것들을 컨트롤하기 위한 firmware가 존재한다. 이 firmware를 통해 host(cpu, ...)와 통신을 통해서 장치에 값을 읽어오거나 쓸 수 있게 된다.

  이런 I/O 장치를 사용하기 위한 방법은 2가지가 있다. x86같은 HW에서는 in&out같은 특별한 instruction을 이용해서 실제로 CPU와 연결되어 있는 device에 명령을 직접 보낸다. 그것 말고 memory mapped I/O라는 방법에서는 메모리 address space 상에서 micro controller가 동작가능한 공간을 mapping 시켜놓고 실제로 메모리에 쓰거나 읽는(load&store) 기법을 사용할 수도 있다.

  그리고 data를 전송하기 위한 방법은 programmed I/O(PIO)와 DMA가 있고, status를 체크하는 방법으로는 polling과 interrupts가 있었다.

fig 2

  각각의 I/O장치에는 port라는 것이 있다. 위에서 말했듯이 I/O 장치는 fig 2의 첫번째 경우 처럼 port에 직접 전기적 신호를 주고 받아 값을 읽어오거나 쓰는 방법이 있고, 두번째 경우처럼 직접적인 in&out instruction을 통해 제어하는 것이 아니라 어떤 메모리 공간에 load&store를 통해 port가 mapping시키는 방법이 있다. 이 방법에서는 mapping된 메모리에 값을 읽거나 쓰면서 이 device의 상태나 값을 활용한다. 그리고 이 두개를 합한 hybrid 방식도 존재한다.

 

Data Transfer Mode

  Programmed I/O는 data를 I/O 장치에서 메모리로 옮기는데 CPU cycle이 사용되는 방법이었다. DMA(Direct Memory Access) 방법은 CPU가 개입하지 않고 I/O 장치에서 data가 메모리로 복사되거나 그 반대 경우가 수행되어 그 동안 CPU는 다른 작업을 할 수 있는 것이다. 

 

Classifying I/O Devices

  I/O 장치는 Block device와 Character device로 나눌 수 있다. 두 개의 차이점은 접근 단위가 byte 단위로 접근할 수 있냐(character device), 아니냐(block device)이다. 예를 들어 disk 같은 storage는 byte가 아닌 512B, 4KB등 fixed size로만 접근할 수 있다. 

 

I/O Stack

fig 3

  read&write 등의 I/O가 일어난다는 것은 user process에서 I/O 요청을 생성하고 이것이 device-independent SW의 추상화를 해준 뒤 해당 장치의 device driver(장치를 제어하는 SW)를 거쳐서 interrupt handler를 통해서 HW에 접근하여 DMA를 활용하거나 I/O 작업이 완료됐는지 등을 확인할 수 있다.

  반대로 키보드로 입력을 하거나 network를 통해 요청이 들어오게 되면 위의 역순으로 user process에게 data를 전달할 수 있을 것이다.

 

Blocking & Nonblocking I/O

fig 4

  blocking I/O는 어떤 I/O 작업이 끝날 때까지 그 프로세스가 더 이상 진행되지 않고 중단되는 것을 말한다. 반면 nonblocing I/O는 I/O를 요청한 다음 곧바로 다른 작업을 수행하는 것이다. 예를 들어 write()처럼 data를 storage에 쓸때 이것은 CPU 입장에서는 매우 느린 작업인데다가 다른 작업을 실행하고 있어도 크게 문제되지 않으므로 다른 작업을 수행한다. 반면 read()는 어떤 값을 버퍼에 읽어온 뒤 이것을 이용해 다음 작업을 주로 수행하므로 입력을 받기 전까지 다른 작업은 blocking 되어야 한다.

  어쨌든 가능하다면 프로세는 I/O 작업이 진행 중일 때 프로세서가 다른 작업을 asynchronous하게 처리할 수 있도록 해야한다. 그러다 I/O 작업이 끝났을 때, signal을 발생시켜서 처리해준 뒤 계속 이어서 작업한다. 

 

Device Drivers

  I/O 장치들을 제어하는 SW가 조금 전 언급했던 device driver이다. 이 SW는 dirver-specific한 코드들로 이루어져 있기에 각각의 I/O 장치들을 제어할 수 있는 것이다.

  키보드나 마우스같이 매우 기초적인 장치에 대한 driver들은 기본적으로 커널에 들어있을 수 있고, USB처럼 plug&play 방식으로 연결 시 driver가 load될 수도 있다. 그럼에도장치의 종류는 매우 많고 각각의 프로토콜을 가질 수 있기 때문에 이것들을 관리하는데 많은 어려움이 있다.

 

Second Storage

  위처럼 정말 많은 I/O 장치들이 있지만 이 글에서 집중할 장치는 Storage(여기선 HDD에 대해 다룸)이고 file을 관리하기 위한 file system에 대해 간단히 알아볼 것이다.

  앞서 잠깐 언급했지만 메모리와 달리 storage는 byte 단위가 아닌 sector라는 block 단위로 접근한다(block device). 그렇기 때문에 load&store 같은 instruction을 통해 storage에 직접 접근할 수 없다. 그 외에 HDD의 특징을 짚고 넘어가자면, 메모리(DRAM)과 다르게 시스템의 전원이 꺼져도 data가 보존되고, 접근 속도가 ns단위인 DRAM에 비해 훨씬 느린 ms단위를 가진다.

 

HDD Architecture

fig 5

  HDD의 구조를 살펴보자. 구조를 살펴보는 이유는 I/O 요청을 내려보낼 때, HDD의 구조에 따라 해당 요청의 성능이 어떻게 변할 수 있는지에 대한 이유를 알아보기 위함이다.

  우선 cd 모양의 둥근 판인 platter가 여러장이 있다. 이 platter 안에는 몇겹의 track이 있고, track 안에는 sector라는 작은 칸이 여러개 있다. 그리고 층은 다르지만 동일한 위치의 track들을 cylinder라고 한다. 그리고 LP 플레이어처럼 arm이 있는데, spindle이 platter를 회전시키고 arm이 이동하며 read-write head가 sector의 data를 읽거나 쓴다.

  fig 5를 보면 알겠지만 HDD가 상대적으로 느린 이유는 spindle이나 arm처럼 기계적으로 동작하는 부분들이 있기 때문이다. 그외에 disk controller를 통해 어떤 platter의 몇번 track과 sector에 접근을 해야하는지 제어하거나 접근된 정보를 buffer에 옮겨놓고 이후 다시 접근되었을 때 buffer를 통해 위치를 연산하지 않고 바로 접근하게끔 하는 등의 동작은 전자적으로 이뤄진다.

  이제 구조를 확인해서 알겠지만 특정 sector에 접근할 때 head와 가까우면 빠르게 접근가능하고 멀수록 접근에 시간이 더 소요됨을 알 수 있다. 예를들어 순차적으로 저장된 파일을 접근할 때에는 head가 특정 track을 차례대로 읽으면 되지만 읽어오고자 하는 data가 HDD 여기저기에 흩어져있으면 각각의 sector에 계속해서 접근해야하기 때문에 더 상대적으로 더 오랜 시간이 소요된다. 예전에 '디스크 조각 모음'을 해준 이유도 이러한 data들을 sector들에 sequential하게 배치하기 위함이다.

 

Interfacing with HDDs

  HDD가 host system(HDD가 장착된 시스템)과 어떻게 상호작용하는지 알아보자. 초장기에는 OS가 HDD의 cylinder, head, sector에 대한 정보를 모두 숙지하여 <cylinder #, head #, Sector#>처럼 각 block에 접근하였다.

fig 6. LBA

  이것을 추상화 한 방식이 LBA(Logical Block Addressing)이다. 이 방법은 HDD의 sector를 logical하게 일렬로 배치한 다음 0~N-1까지의 array 처럼 다뤘다. 이러한 추상화는 firmware가 하고 device driver나 OS는 이런 추상화된 환경을 이용한다. 이 방법은 하나의 block을 접근하기 위해 LBA를 사용하고 disk가 하나의 LBA를 physical loacation으로 mapping한다.

 

HDD Performance Factors

  HDD의 성능을 결정짓는 요소는 3가지다.

• Seek time(\(T_{seek}\)): arm을 접근하고자 하는 cylinder에 위치시키는 시간이다. 이 시간은 cylinder까지의 물리적인 거리에 의해 결정된다. 평균적인 seek time은 전체 seek time의 1/3 정도 된다.
• Rotational delay(\(T_{rotation}\)): arm을 위치시킨 이후, platter를 회전시켜 head에 track의 sector를 위치시키는데 걸리는 시간이다. 이것은 회전속도인 RPM(Rotation Per Minute)에 의해 결정된다. 
• Transfer time(\(T_{transfer}\)): arm의 head가 sector에 붙어서 data를 읽어 host에 전달하는 시간이다.

 

Disk Scheduling

  HDD의 성능을 개선하기 위해서는 특히 Seek time를 줄여야 하는데 이를 위해 disk scheduling을 이해할 필요가 있다. I/O 요청으로 인해 여러 LBA를 읽어야하는데 어떠한 순서로 읽어야 읽기 시간을 최소화 할 수 있을지에 대한 policy를 살펴보자. 그 전에 용어를 몇개 짚고 넘어가자면 work conserving scheduler는 처리할 작업이 있으면 항상 해당 작업을 하려고 하는 것이고, 이에 반해 non-work conserving scheduler는 처리할 작업이 있긴 하지만 당장 처리하지 않고 잠시 대기했다가 처리하는 것이다. 대기한 다음 실행됐을 때 바로 다음 위치에  있는 data를 읽을 수 있는 경우를 생각해보자.

FCFS: First-Come First-Served

fig 7

  스케줄링 policy에서 늘 가장 먼저 나오는 방법이다. fig 7을 보면 알겠지만 I/O 요청이 들어오는 순서대로 처리하는 것이다. 점과 점사이의 선이 seek time이다. 이 방법은 load가 적을 때에는 적당히 잘돌아가지만, 요청이 많아서 queue가 길어지면 waiting time이 길어진다는 단점이 있다.

SSTF: Shortest Seek Time First

fig 8

  이전에 배웠던 CPU 스케줄링 같은 경우에는 어떤 일이 발생할지 미리 알 수 없었지만 disk 스케줄링의 경우에는 어느 sector에 위치해야 할지 알고 있기 때문에 현재 위치 기준으로 읽어야 할 각 섹터까지의 거리를 쉽게 알 수 있다. 이 방법은 현재 head 위치 기준으로 가장 가까운 sector부터 읽는다. 이렇게 하면 arm의 움직임을 최소화하면서 seek time을 낮출 수 있다.

  이 방법은 seek time은 줄일 수 있지만 특정 부분을 우선적으로 읽게 되므로 starvation이 발생할 수 있다는 단점이 있다.

Scan & F-Scan & C-Scan

fig 9

  scan 방법은 SSTF와 유사하긴 하지만 한 쪽 방향으로만 읽다가 이것이 끝나면 반대 방향으로 읽는다. 그렇기 때문에 wait time이 skew하게 발생할 수 있고 중간에 위치한 block들이 왔다갔다 할 때 한번씩 지나치니 더 높은 favor을 가진다.

  이 방법의 단점은 현재 위치 근처를 읽으라는 I/O요청이 계속해서 들어오면 현재 위치에 멀리있는 block을 읽기까지 매우 오랜 시간이 걸릴 수 있다는 것이다. 이것을 방지하기 위해 이번 scan 중 새롭게 들어오는 요청들은 별도의 queue에 임시로 넣어놓은 뒤 현재 까지의 요청을 그대로 처리하는 f-scan이라는 방법을 사용하기도 한다.

fig 10

  이외에도 한쪽 방향으로만 scan을 하는 C(circular)-scan도 있다. 이처럼 scan 같은 방법을 elevator 알고리즘이라고 부른다.

 

Modern Disk Scheduling

  현대의 I/O 스케줄러는 펌웨어가 아닌 전적으로 OS가 담당한다. OS에서 어떻게 요청을 전달하거나 스케줄링 할지를 잘 제어해서 장치에 내려보냄으로써 더 나은 성능을 얻으려고 한다. disk 스케줄러는 전반적인 disk throughput을 늘리고 starvation을 방지하여야 한다.

  그리고 disk drive에서는 들어오는 여러가지 요청을 처리할 수 있는 최대치를 설정하거나 head의 위치나 track의 구조를 이용해 장치에 요청을 보내야 한다.

---

• Operating System Concepts, Avi Silberschatz et al.
• Operating Systems: Three Easy Pieces
  • Remzi H.Arpaci-Dusseau andAndreaC.Arpaci-Dusseau
  • Available(withseveraloptions)athttp://ostep.org