15. Persistence - IO Devices, HDD

Modern System Architecture

• 현대 컴퓨터는 CPU, memory, I/O device가 bus와 controller를 통해 연결되어 있다.
• CPU는 직접 모든 장치를 세세하게 제어하지 않는다.
• 각 I/O device는 보통 device controller를 가진다.
• 예 다음과 같은 controller가 있다.
  • disk controller
  • graphics adapter
  • USB controller
  • network adapter
• CPU와 memory는 system bus / memory bus를 통해 연결된다.
• I/O device는 I/O bus를 통해 연결된다.
• OS는 device controller를 통해 device에 명령을 내리고, device는 작업 완료를 interrupt 등으로 알린다.

Background: I/O Subsystem

A Typical I/O Device

• device 제어 방식에는 여러 선택지가 있다.
  • Control
    • special instruction
    • memory-mapped I/O
  • Data transfer
    • Programmed I/O
    • DMA
  • Status check
    • polling
    • interrupts

I/O Design Question

• I/O에서 핵심 설계 질문은 다음이다.

  • How to perform I/Os efficiently?

• I/O device는 CPU보다 느리지만, I/O device와 CPU는 동시에 동작할 수 있다.

• 각 device controller는 특정 device type을 담당한다.

• 각 device는 local buffer를 가질 수 있다.

• CPU는 I/O command를 device에 전달한다.

• 그리고 data를 main memory와 device buffer 사이에서 이동시켜야 한다. 문제는 CPU가 귀한 자원이라는 것이다.

• CPU가 다음 일을 계속 직접 하면 비효율적이다.

  • memory와 device buffer 사이의 data 이동
  • device command 완료 여부를 계속 확인

• 따라서 OS와 hardware는 CPU 사용을 줄이기 위해 DMA와 interrupt 같은 mechanism을 사용한다.

Data Transfer Modes: Programmed I/O

• PIO(Programmed I/O): CPU가 직접 data를 옮김
  • CPU가 device register에서 한 word를 읽고, memory에 쓴다.
  • 또는 memory에서 한 word를 읽고, device register에 쓴다.

Data Transfer Modes: DMA

• DMA(Direct Memory Access)
  • DMA는 high-speed I/O device에서 많이 사용됨
  • DMA에서는 device controller가 main memory에 직접 접근하여 data block을 옮김
  • CPU는 처음에 DMA transfer를 설정하며, 이후 실제 data 이동은 device controller가 수행함
• data transfer가 끝나면 device가 interrupt를 발생시켜 CPU에게 알린다.

Event Notification: Polling

• I/O 작업이 끝났는지 확인하는 방법 중 하나는 polling이다.
• polling은 CPU나 kernel이 device status register를 반복해서 확인하는 방식이다.

while (device_not_ready()) {
    ;
}

• 구현이 단순하지만, 작업이 끝날 때까지 CPU가 계속 기다림(busy waiting)

Event Notification: Interrupts

• interrupt는 device가 CPU에게 I/O 완료를 알리는 hardware mechanism이다.
• CPU는 I/O 작업이 진행되는 동안 다른 일을 할 수 있음.
• 하지만 interrupt에도 overhead가 있다.
  • interrupt handling 비용
  • context switching 가능성
  • cache disruption
• 그래서 매우 빈번한 event에서는 polling이 더 나을 때도 있음. 실제 system에서는 섞어씀

Disk I/O Real Example

• SATA disk I/O의 예시 흐름은 대략 다음과 같다.
  • OS/driver가 SATA controller에 read command를 보낸다.
  • controller가 command를 queue에 넣고 acknowledge한다.
  • disk가 실제 read를 수행한다.
  • disk 내부 buffer에 data를 담는다.
  • controller가 DMA를 설정한다.
  • data가 DMA로 main memory에 전송된다.
  • 작업이 끝나면 interrupt가 발생한다.
• 이 과정에서 CPU는 처음 명령을 내리고, 끝났을 때 interrupt를 처리함. data의 실제 이동은 DMA가 담당

I/O Address Space

• CPU가 device register에 접근하는 방식은 크게 두 가지다.
  • Port-mapped I/O
  • Memory-mapped I/O
• Port-mapped I/O는 memory address space와 I/O address space가 분리되어 있다.
• x86에서는 in, out 같은 special instruction을 통해 I/O port에 접근할 수 있다.
• Memory-mapped I/O는 device register를 memory address처럼 mapping한다.
• CPU는 load/store instruction으로 device register에 접근한다.
• memory-mapped I/O는 device control을 memory access처럼 다룰 수 있어 편리하다.
• 많은 modern system은 memory-mapped I/O를 사용한다.

Memory-Mapped I/O

• memory-mapped I/O에서는 device register가 physical address range에 mapping된다.
• CPU가 특정 memory address에 load/store를 하면 실제로는 device register를 읽거나 쓰게 된다.
• 장점은 다음과 같다.
  • 일반 memory instruction으로 device 제어 가능
  • special I/O instruction이 필요 없음
  • compiler나 CPU architecture 관점에서 통합된 interface 제공
• 하지만 주의할 점도 있다.
  • 일반 memory와 달리 caching이나 reordering이 문제가 될 수 있다.
  • device register 접근은 정확한 순서가 중요할 수 있다.
• 그래서 OS는 memory-mapped I/O 영역에 대해 cache policy나 memory barrier를 신경 써야 한다.

Block Device

• fixed-size block 단위로 정보를 저장
  • 각 block은 address를 가진다.
  • block 크기는 보통 512B 또는 4KB다.
  • 각 block은 독립적으로 read/write할 수 있다.
  • 대표적인 block device는 다음과 같다.
    • HDD
    • SSD
    • tape

Character Device

• character stream을 전달하거나 받는 장치
• block처럼 address를 지정해서 seek하는 개념이 없고, 순차적인 stream으로 data를 주고받는다.
• 대표적인 character device는 다음과 같다.
  • keyboard
  • mouse
  • printer
  • network interface

I/O Stack

• user process는 read/write 같은 system call을 호출한다.
• device-independent software는 naming, protection, buffering, allocation 같은 공통 기능을 처리한다.
• device driver는 특정 device의 register와 protocol을 이해하고 제어한다.
• interrupt handler는 device가 I/O 완료를 알렸을 때 실행된다.
• hardware는 실제 I/O operation을 수행한다.

Interrupt Handlers

• interrupt handler는 device interrupt를 처리하는 kernel code다. interrupt handler는 가능한 짧게 실행되어야 한다. interrupt handler의 작업은 크게 세 종류로 볼 수 있다.

1. critical actions
   • interrupt controller에 interrupt를 acknowledge한다.
   • device controller를 다시 설정한다.
   • device와 processor가 함께 접근하는 data structure를 update한다.
2. noncritical actions
   • processor만 접근하는 data structure를 update한다.
   • 예를 들어 keyboard scan code를 읽는 작업이 있을 수 있다.
3. noncritical deferred actions
   • 나중에 처리해도 되는 작업이다.
   • 예를 들어 buffer 내용을 process address space로 copy하는 작업이다.
   • Linux에서는 bottom half 같은 개념으로 지연 처리한다.

Blocking and Nonblocking I/O

• I/O call의 동작 방식은 크게 세 가지로 볼 수 있다.
  • blocking I/O
  • nonblocking I/O
  • asynchronous I/O

Blocking I/O

• I/O가 끝날 때까지 process가 suspended됨
  • 장점은 사용하기 쉽고 이해하기 쉬움
  • programmer는 I/O가 끝난 뒤 다음 줄이 실행된다고 생각하면 됨
  • process가 기다리는 동안 다른 일을 못 한다는 것이다.
  • OS는 그동안 다른 process를 실행할 수 있다.

Nonblocking I/O

• I/O call이 바로 return하는 방식
  • data가 있으면 가능한 만큼 읽고, 없으면 기다리지 않고 return함
  • user interface나 event-driven program에서 유용함
  • 하지만 programmer가 “아직 data가 없음”을 직접 처리해야 한다.
• 따라서 blocking I/O보다 programming이 복잡할 수 있다.
• nonblocking I/O는 multi-threading이나 event loop와 함께 자주 사용된다.

Asynchronous I/O

• asynchronous I/O는 process가 I/O를 요청한 뒤, I/O가 진행되는 동안 계속 실행되는 방식
  • I/O가 끝나면 OS가 process에게 알려줌.( callback, signal, completion queue 등)
• 장점은 CPU와 I/O를 더 잘 overlap할 수 있다는 것이다.
• 단점은 사용하기 어렵다는 것이다.
• 프로그램 구조가 복잡해질 수 있다.
• 따라서 high-performance server나 database system에서 중요하게 쓰인다.

Three I/O Methods

• Blocking I/O
  • requesting process가 I/O 완료까지 기다린다.
  • device driver와 hardware가 작업하는 동안 process는 sleep한다.
• Nonblocking I/O
  • 요청이 즉시 return한다.
  • available한 data만 처리하거나, 아직 준비되지 않았음을 알린다.
• Asynchronous I/O
  • process는 요청 후 계속 실행된다.
  • device driver와 hardware가 background에서 작업한다.
  • 완료되면 interrupt handler 등을 통해 알림이 전달된다.

Device Drivers

• 특정 I/O device를 제어하는 OS code, device-specific code
  • device register 설정
  • command 전달
  • status 확인
  • interrupt 처리와 연결
  • data transfer 설정
• driver는 kernel에 static하게 link될 수도 있고, boot time에 선택적으로 load될 수도 있다.
• hot-pluggable device처럼 실행 중에 dynamically load될 수도 있다.
• device driver 작성이 어려운 이유는 device가 매우 다양하기 때문이다.
• 각 device마다 protocol과 register interface가 다르다.
• OS는 device driver를 통해 다양한 hardware를 공통 interface로 추상화한다.

OS Reliability and Device Drivers

• OS reliability에서 device driver는 큰 문제 원인이다.
• driver는 kernel extension으로 동작하는 경우가 많고, kernel mode에서 실행되므로 driver bug는 system 전체 crash로 이어질 수 있다.
• device 종류가 매우 많고, driver version도 많다.
• driver는 core kernel보다 덜 숙련된 개발자에 의해 작성되는 경우도 있다.
• 따라서 driver 안정성은 OS reliability에서 매우 중요하다.

Hard Disk Drives

• 대표적인 secondary storage
  • instruction을 직접 실행할 수 없다.
  • machine load instruction으로 직접 data를 가져올 수 없다.
  • 보통 sector array로 추상화된다.

• HDD의 block 또는 sector 크기는 보통 512 bytes 또는 4096 bytes다.
• HDD의 특징은 다음과 같다.
  • large
    • 수백 GB 이상 저장 가능
  • cheap
    • byte당 비용이 낮다.
  • persistent
    • power loss 이후에도 data가 남는다.
  • slow
    • access 시간이 millisecond 단위다.
• main memory access가 nanosecond 단위인 것과 비교하면 HDD는 매우 느리다.

HDD Architecture

1. electromechanical part
   • rotating disks
   • arm assembly
   • read/write head
2. electronics part
   • disk controller
   • buffer
   • host interface

• HDD는 platter가 회전하고, arm이 원하는 track으로 이동한 뒤, sector가 head 아래에 올 때까지 기다린다.
• 따라서 HDD 성능은 mechanical movement에 크게 영향을 받는다.
• 이것이 SSD와 가장 큰 차이다.
• HDD는 순차 접근은 비교적 빠르지만, random access는 매우 느릴 수 있다.

A Modern HDD

• HDD specification에는 보통 다음 정보가 포함된다.
  • capacity
  • heads
  • discs
  • tracks per inch
  • areal density
  • spindle speed
  • internal cache buffer
  • average seek time
  • interface bandwidth
  • sustained transfer rate
  • power-on to ready time
• 예를 들어 7200 RPM disk는 한 바퀴 도는 데 약 8.3ms가 걸린다.
• 평균적으로 원하는 sector가 head 아래 올 때까지 반 바퀴를 기다린다고 보면 rotational delay는 약 4.2ms다.
• 여기에 seek time과 transfer time이 더해져 전체 I/O 시간이 결정된다.

Interfacing with HDDs

CHS(Cylinder-Head-Sector)

• block을 다음 세 값으로 주소 지정한다.
  • cylinder number
  • head number
  • sector number
• 과거에는 OS가 disk geometry를 알아야 했다.
• 즉 cylinder, head, sector 구조를 OS가 고려해야 했다.
• 하지만 modern disk에서는 실제 내부 구조가 더 복잡해졌고, 이 방식은 덜 사용된다.

LBA(Logical Block Addressing)

• disk를 logical block의 배열로 추상화한다.
• block은 0, 1, 2, ..., N-1로 번호가 붙는다.
• OS는 logical block address만 사용한다.
• disk 내부에서 LBA를 실제 physical location으로 mapping한다.
• 이 방식은 SCSI에서 처음 도입되었다.
• LBA의 장점은 disk의 physical geometry를 OS로부터 숨긴다는 것이다.
• OS는 disk를 단순한 block array처럼 다룰 수 있다.

HDD Performance Factors

• HDD 성능을 결정하는 주요 요소는 세 가지다.
  • seek time
  • rotational delay
  • transfer time

Seek Time

• seek time은 disk arm을 원하는 cylinder로 이동시키는 시간이다.
• arm이 얼마나 멀리 이동해야 하는지에 따라 달라진다.
• 완전히 선형적이지는 않다.
• 평균 seek time은 보통 full seek time의 약 1/3 정도로 볼 수 있다.
• random I/O에서는 seek time이 큰 비중을 차지한다.

Rotational Delay

• rotational delay는 원하는 sector가 disk head 아래로 회전해 올 때까지 기다리는 시간이다.
• RPM에 따라 결정된다.
• 예를 들어 7200 RPM이면 1분에 7200번 회전한다.
• 한 바퀴 시간은 다음과 같다.
  • 60초 / 7200 = 약 8.3ms
• 평균적으로 반 바퀴를 기다린다고 보면 평균 rotational delay는 약 4.2ms다.
• 15000 RPM disk는 한 바퀴가 약 4ms이고, 평균 rotational delay는 약 2ms다.

Transfer Time

• transfer time은 실제 data를 disk surface에서 disk controller로 읽고, host로 전달하는 시간이다.
• sequential I/O에서는 transfer time이 중요하다.
• random I/O에서는 seek time과 rotational delay가 더 지배적일 수 있다.
• transfer time은 data size와 bandwidth에 따라 결정된다.
• 예를 들어 4KB random read에서는 transfer time 자체는 매우 작지만, seek과 rotation 때문에 전체 latency가 커진다.
• 반대로 100MB sequential read에서는 seek/rotation은 한 번만 발생하고, 대부분 transfer bandwidth가 성능을 결정한다.

HDD Performance Comparison

• random read와 sequential read는 성능 차이가 매우 크다.
• random 4KB read에서는 다음 비용이 모두 들어간다.
  • seek time
  • rotational delay
  • transfer time
• 예를 들어 7200 RPM disk에서 random 4KB read는 seek 9ms, rotational delay 4.2ms 정도가 들어갈 수 있다.
• transfer time은 매우 작지만, mechanical delay가 커서 전체 throughput은 낮다.
• 반면 sequential 100MB read는 arm movement와 rotational delay가 상대적으로 덜 중요하다.
• data를 연속적으로 읽기 때문에 transfer rate에 가까운 성능을 낼 수 있다.
• 따라서 HDD에서는 sequential access가 random access보다 훨씬 빠르다.
• file system과 disk scheduler는 이 특성을 활용해 random access를 줄이고 sequential access를 늘리려고 한다.

Disk Scheduling

• disk scheduling의 질문은 다음이다.
  • 여러 I/O request가 들어왔을 때 어떤 순서로 처리할 것인가?
• disk scheduling은 CPU scheduling과 다르다.
• CPU scheduling에서는 job의 길이나 priority가 중요할 수 있다. 반면 disk scheduling에서는 disk head의 현재 위치와 request 위치가 중요하다. 이유는 seek cost가 매우 크기 때문이다. request 길이보다 head movement가 성능을 더 크게 좌우할 수 있다.
• 따라서 disk scheduler는 seek time을 줄이기 위해 request 순서를 재배열할 수 있다.

Work-Conserving and Non-Work-Conserving

• Work-conserving scheduler
  • 할 일이 있으면 항상 바로 처리한다.
  • device가 idle하지 않게 한다.
• Non-work-conserving scheduler
  • 할 일이 있어도 잠시 기다릴 수 있다.
  • 곧 더 좋은 request가 올 것으로 예상되면 기다리는 것이 더 나을 수 있다.
• HDD에서는 seek가 비싸기 때문에, 바로 처리하는 것보다 조금 기다려 더 가까운 request를 묶는 것이 이득일 때가 있다.

FCFS(First-Come First-Served)

• 들어온 순서대로 request를 처리

SSTF(Shortest Seek Time First)

• 현재 disk head 위치에서 가장 가까운 request를 먼저 처리
• 목표는 arm movement를 줄이는 것이다.
• seek time을 줄이는 데 효과적일 수 있다.
• 하지만 단점도 있다.
  • middle block 근처 request를 계속 선호할 수 있다.
  • 멀리 있는 request는 오래 기다릴 수 있다.
  • starvation이 생길 수 있다.
• disk geometry를 정확히 모르는 경우에는 Nearest-Block-First처럼 logical block 기준으로 가까운 request를 고를 수 있다.
• SSTF는 성능은 좋을 수 있지만 fairness 문제가 있다.

Elevator / SCAN

• SSTF의 starvation 문제를 줄이기 위해 elevator 방식이 사용된다.
• elevator, 또는 SCAN은 엘리베이터처럼 한 방향으로 이동하며 request를 처리한다.
• disk head가 한 방향으로 움직이면서 지나가는 request를 처리한다.
• 끝까지 가면 방향을 바꾼다.
• 장점은 다음과 같다.
  • seek movement를 줄인다.
  • starvation 가능성을 줄인다.
  • FCFS보다 성능이 좋다.
• 단점은 request가 있는 위치와 방향에 따라 waiting time이 달라질 수 있다는 것이다.
• SCAN은 disk head movement를 좀 더 체계적으로 관리하는 방식이다.

F-SCAN

• F-SCAN은 SCAN의 변형이다.
• disk head가 한 방향으로 sweep을 시작할 때 현재 request queue를 freeze한다.
• sweep 도중 새로 들어온 request는 다음 sweep에서 처리한다.
• 이렇게 하면 sweep 중 계속 새 request가 들어와서 멀리 있는 request가 계속 밀리는 문제를 줄일 수 있다.
• 즉 far-away request starvation을 완화한다.

C-SCAN(Circular SCAN)

• Circular SCAN.
• SCAN처럼 elevator algorithm이지만, 한 방향으로만 request를 처리한다.
• 끝까지 가면 다시 처음 쪽으로 돌아가서 같은 방향으로 처리한다.
• SCAN보다 wait time이 더 균일하다.
• SCAN과 C-SCAN은 elevator algorithm이라고 불리며, 둘 다 rotational delay는 고려하지 않는다.

SPTF(Shortest Positioning Time First)

• positioning time은 seek time과 rotational delay를 모두 포함함. 즉 단순히 cylinder가 가까운 request를 고르는 것이 아니라, 실제로 가장 빨리 접근 가능한 request를 고름
  • HDD에서는 rotational delay도 중요하기 때문. 예를 들어 조금 더 멀리 있는 block이라도, 회전 위치가 좋아서 더 빨리 읽을 수 있을 수 있다.
  • SPTF는 이론적으로 더 정확하지만, disk 내부 정보가 필요하다.
  • modern disk는 내부 geometry를 숨기기 때문에 OS가 정확히 계산하기 어려울 수 있다.
  • 그래서 이런 scheduling은 disk firmware 내부에서 수행되기도 한다.

Modern Disk Scheduling

• Host OS의 I/O scheduler는 전체 disk throughput을 높이기 위해 request merge와 request sorting을 수행한다.
• request merge는 인접한 요청들을 합쳐 request 수를 줄이는 것이다.
• request sorting은 disk seek time을 줄이기 위해 request 순서를 조정하는 것이다.
• OS scheduler는 starvation을 막고 process 간 fairness도 고려한다.
• Disk drive 내부에서도 scheduling이 일어난다.
• SATA NCQ(Native Command Queuing) 같은 방식에서는 disk가 여러 outstanding request를 받을 수 있다.
• disk는 head position과 track layout을 알고 있으므로, 내부적으로 더 좋은 순서로 request를 처리할 수 있다.
• SPTF는 seek time뿐 아니라 rotational delay까지 고려하는 방식이다.
• 따라서 현대 시스템에서는 host OS scheduler와 disk drive scheduler가 역할을 나누어 I/O 순서를 최적화한다.

Why Disk Is Slow

• HDD가 느린 이유는 mechanical movement 때문이다.
• memory access는 electronic operation이다.
• 반면 HDD access는 다음 물리 동작을 포함한다.
  • arm 이동
  • platter 회전
  • head 아래 sector 도착 대기
• 이 때문에 random access latency가 millisecond 단위가 된다.
• CPU와 memory 속도에 비해 매우 느리다.
• 따라서 OS는 HDD 접근을 최대한 줄이고, 접근하더라도 sequential하게 만들려고 한다.
• file system, buffer cache, disk scheduling은 모두 이 목표와 관련된다.

Why Sequential Access Matters

• HDD에서는 sequential access가 random access보다 훨씬 빠르다.
• sequential access에서는 한 번 위치를 잡은 뒤 연속 block을 읽을 수 있다.
• 그래서 seek과 rotational delay를 여러 block에 나누어 amortize할 수 있다.
• random access에서는 매 request마다 seek과 rotation이 발생할 수 있다.
• 따라서 file system은 관련 data를 가까이 배치하려고 한다.
• disk scheduler는 request 순서를 조정해 head movement를 줄이려고 한다.
• 이후 FFS 같은 file system에서도 locality를 높이는 배치 전략이 중요하게 등장한다.