[Operating System] I/O Devices

I/O Bus

• 빠른 I/O와 느린 I/O를 구분하기 위해서 여러 hierarchy의 I/O bus가 존재한다.
• I/O 버스는 I/O 디바이스와 3가지 요소를 통하여 연결된다. (port, interface, controller)

Canonical Device

 

• OS는 device register의 status, command, data에 R/W를 한다.
• 디바이스 레지스터는 OS에 보이지만 디바이스의 내부에 대한 정보는 hidden black box이다. 따라서 OS와 디바이스는 device register의 인터페이스에 따라서만 통신할 수 있고, OS는 정해진 인터페이스 내에서만 디바이스의 operation을 control할 수 있다.
• spinning을 어떻게 피하는가? interrupt

 

write protocol

Interrupt (Blocking)

• I/O 요청을 보낸 process는 sleep 상태에 두고 context switch를 하여 다른 프로세스를 스케줄링한다. (blocking)
• I/O가 끝나면 BLOCK 상태에 있던 프로세스를 다시 READY 상태로 만든다.
• 단점: context swtich 오버헤드 (모든 blocking 방식의 공통점...)
  • flood of interrupt: interrupt가 동시에 너무 많이 발생하면 livelock 문제가 발생함(실제 CPU 작업이 진행되지 못함)

Polling (Non-blocking)

• I/O가 끝날때까지 device status register를 계속 체크(spin)하면서 기다린다.
  • while(STATUS == BUSY) { ; }
• 단순하고 context switch 오버헤드가 없다는 장점이 있다.
• 하지만 I/O가 끝나길 기다리는 동안 CPU가 idle 상태에서 낭비된다.
• 만약 작은 크기의 I/O 요청이거나 I/O 속도가 빠른 device라면 그냥 spin을 하면서 기다리는 것이 context switch 오버헤드 보다 작을 수 있다.

Improved Solution

• Interrupt Coalescing: I/O가 발생하는 매번 interrupt 하지 않고 여러 개를 모아서 batch 단위로 interrupt를 발생시켜 한번에 처리한다.
• Polling + Interrupt: 요청의 크기에 따라서 동적으로 처리한다. (금방 끝나는 요청이면 polling을, 그렇지 않으면 interrupt를 사용)

 

DMA (Direct Memory Access)

CPU에서는 memory에서 disk로 데이터를 copy할 때 상당히 많은 시간을 소비한다. 따라서 copy와 같은 간단한 작업은 CPU 말고 다른 하드웨어에게 맡기고 CPU는 다른 작업을 하는 것이 효율적이다.

 

• CPU를 대신하여 I/O장치와 Memory사이의 데이터전송을 담당하는 장치
• mem to disk copy 시에 data copy 작업은 DMA controller에게 맡기고 CPU는 다른 프로세스 task를 처리한다.
• DMA가 disk로 copy를 끝내면 interrupt를 발생시키고, 이 때부터는 disk에서 I/O가 시작된다.

 

DMA와 반대되는 PIO(Programmed I/O)에서는 장치들 사이에 전송되는 모든 데이터가 CPU를 거쳐가는 방식이다. DMA는 PIO의 단점을 보완하기 위해 고안된 기능이다.

 

Device Interaction

• OS는 device와 어떻게 소통하는가?
  • I/O instruction(Programmed I/O): in, out과 같은 어셈블리 명령을 통해서 특정 디바이스에 I/O를 할 수 있다.
    • I/O port의 개수가 HW마다 다르기 때문에 호환성 문제가 있다.
  • Memory-mapped I/O: 마치 가상 메모리 주소처럼 disk 레지스터에도 가상의 주소가 있고, OS는 memory가 아니라 device에 대해서 load, store 명령을 수행할 수 있다.

 

File System Abstraction

• Abstaction: 여러 종류의 다양한 file system과 OS가 소통하기 위해서는 어떤 디바이스와도 호환 가능한 abstraction interface가 정의 되어야한다.
  • Device Driver: 각각 디바이스가 서로 다른 protocol을 사용하고 있더라도 OS와 통신 가능하도록 디바이스 제조사에서 제작한다.
    • file system과 scheduler에서 특정 device를 바라 볼 때, 그 내부의 specification은 보이지 않고, 똑같은 disk로 바라보고 통신한다.
  • File-system abstraction: 각 FS는 자신이 어떤 disk class를 사용하고 있는지 명시한다.
    • Application과 FS는 POSIX API(open, read, write와 같은 syscall)을 통해 통신
    • FS와 Generic Block Layer는 Generic Block Interface를 통해서 통신
      • 유저 app에서는 블록 사이즈에 대해서 신경 쓰지 않고 read, write를 하지만 generric block interface에서는 동적으로 정해지는 block size 단위로 read, write 처리가 이루어진다.
    • Generic block layer는 device driver와 specific block interface를 통해서 통신

 

 

---

Hard Disk

• disk는 여러개의 sector(512-byte block)들로 구성된다.

  • 전체 디스크는 n개의 sector로 이루어져있고, 각각의 sector는 주소를 가진다.

    • 만약 16bit 주소공간을 사용한다면, $512 * 2^{16} = 32MB$

    • sector 단위로 R/W를 하기 때문에 메모리 가상주소처럼 offset을 위한 주소공간은 필요없다.

    • sector 하나에 대해서 R/W 하는 것은 atomicity가 보장된다.

    • 일반적으로 FS에서 I/O를 할 때 sector 하나가 아닌 여러 개의 묶음을 단위로 한다. (4KB 단위)

      • Torn write: sector 하나에 대해서만 atomicity가 보장되므로 chunk 단위로 I/O를 하면 crash가 발생했을 때 일부만 쓰일 수 있다.

• 구조

  • Platter: 각 platter는 2개의 surface로 구성(양 surface에 R/W 가능)

  • Spindle: 회전하는 모터와 연결된 부분 (회전 단위 = RPM)

    • 10000RPM인 경우 => 10000번: 60sec = 1번: $x$ sec
      $x = 60 * 10^{-4} = 6 * 10^{-3} = 6ms$

  • Track: sector 여러개로 이루어진 circle

  • disk head, disk arm

  • cylinder
    
    

 

Disk Latency

1. Seek Time

• R/W하려는 sector가 있는 track으로 head를 이동시키는 데 걸리는 시간
• acceleration(가속) => coasting(최고속도) => deceleration(감속) => settling(트랙의 정확한 위치에 안착)
  • settling이 가장 까다롭고 시간도 오래 걸림.

2. Rotational Delay

• Platter가 회전하여 원하는 sector에 head가 도달하기까지의 시간

3. Transfer Time

• 실제로 R/W를 하는데 걸리는 시간

 

[NOTE] servo burst: disk head가 sector를 찾아가면서 자신의 위치를 정확히 파악하는 건 매우 어렵다. 따라서 servo burst라는 마크를 일정 sector 간격으로 두어 위치를 파악, 조정한다.

 

I/O time 계산하기

• I/O time: $T_{I/O} = T_{seek} + T_{rotation} + T_{transfer}$
• Rate of I/O: $R_{I/O} = \frac{size_{transfer}}{T_{I/O}}$
• Workload
  • Random / Sequential
    • Disk R/W 시엔 실제로 data transfer가 이루어지는 transfer time 보다 seek time, rotation delay에 매우 많은 시간이 소요되는데, random access 시엔 seek, rotation 대기를 많이 하게 되므로 매우 비효율적.
    • 반면 sequential access에선 seek, rotation의 비중이 적고 transfer time이 주를 이루는데, 이는 매우 빠르므로 시간이 훨씬 적게 든다.

 

Disk Optimization

1. Track Skew

• seek을 하는 동안에도 원판이 회전하고 있기 때문에 트랙 간에 연속적으로 접근을하는 sector의 경우에 seek에 걸리는 시간을 고려하여 비스듬히 배치해야한다.

2. Zone

• 면적이 큰 바깥 쪽 트랙은 더 많은 섹터로 나눈다.

3. Cache (Track Buffer)

• Disk에도 8~16MB 정도의 작은 메모리를 따로 두어 disk data를 캐싱한다.
• Read-ahead Buffering: Rotational delay 동안 타겟 sector에 도달하기까지의 경로에 있는 트랙 내 다른 sector들을 캐싱한다.
• Tagged Command Queueing: 버퍼에 있는 request들을 reordering 하여 더 효율적으로 만드는 것

 

"Work Conservation" vs "Anticipatory"

• Work Conseravtion: I/O request가 생기면 그 순서대로 즉각 처리한다.
• Anticipatory: 여러 I/O 요청들을 버퍼에 모았다가 reordering하여 한 번에 처리

 

Write-back vs Write-through
- write-back: 메모리에 쓰이면 write가 끝났다고 인식
- write-through: 디스크에까지 데이터가 쓰이고 난 뒤에야 write가 끝났다고 인식

 

4. I/O Merging

• 매번 R/W 명령이 실행될 때 disk I/O를 하는 것이 아니라 버퍼링을 하여 서로 가까운 block들에 대한 I/O는 하나의 요청으로 merge한다.
• positioning overhead를 줄일 수 있다.
• Gap filling

 

Gap Filling

Read하는 경우
- 만약 33 -> 35 -> 37번 블록 순으로 read를 한다면 33~37 블록 전체를 merge해서 read를하고, read 대상이 아닌 34, 36번 블록은 discard한다.

Write하는 경우
- 33 -> 35 -> 37번 블록 순으로 write를 한다고 하자.
- 만약 34, 36번 블록이 비어있다면, 33~37번 블록을 한번에 묶어서 write하되, 34, 36번 블록은 비어둔채로 write한다.

 

Disk Scheduling

Disk scheduling에서는 I/O 대상 데이터에 얼마나 빨리 포지셔닝할 수 있는가가 핵심이다.

 

1. SSTF (Shortest Seek Time First)

• 현재 head 위치에서 가까운 track 부터 읽는다.
• 단점
  • seek time이 OS에게 공개되지 않은 경우가 많다.
    • NBF(Nearest Block First)로 대체
  • Starvation: 현재 head에 가까운 track에 연속적으로 request가 들어오는 경우

 

2. Elevator 알고리즘 (SCAN / C-SCAN)

• SCAN 알고리즘에서는disk arm이 디스크의 한 끝에서 시작하여 다른 끝으로 이동하며 가는 길에 있는 모든 요청을 처리한다. 다른 한쪽 끝에 도달하면 역 방향으로 이동하면서 오는 길에 있는 요청을 처리 한다. 엘리베이터처럼 왕복하며 처리하므로 엘리베이터(elevator algorithm)이라고도 부른다.

 

• C-SCAN 스케줄링은 각 요청에 걸리는 시간을 좀 더 균등하게 하기 위한 SCAN의 변형이다. SCAN과 같이 C-SCAN은 한쪽 방향으로 헤드를 이동해 가면서 요청을 처리하지만 한쪽 끝에 다다르면 반대 방향으로 헤드를 이동하며 처리하는 것이 아니라 처음 시작했던 자리로 다시 되돌아가서 서비스를 시작한다. 즉, C-SCAN 스케줄링 알고리즘에서는 마지막 실린더가 처음 실린더와 맞닿은 원형 리스트구조를 갖는다.

 

3. SPTF (Shortest Positioning Time First)

• seek time과 rotational delay를 모두 고려하여 positioning이 빠른 것부터 처리한다.

 

4. CFQ (Completely Fair Queueing: linux default)

• 각 프로세스마다 I/O request queue가 존재
• 큐 간에는 WRR policy로 스케줄링
• 각각의 queue 내에선 elevator 알고리즘으로 최적화

 

seek time이나 rotational delay는 디스크 제조사에서 대부분 공개를 안 하기 때문에 OS 레벨에서는 LBA(Logical Block Address) 정도밖에 이용하지 못한다.

 

[NOTE] 느린 device일 수록 스케줄링과 최적화가 필요하다. $\to$ HDD에서 SSD로 넘어오면서 스케줄링을 하는 것이 별다른 의미가 없어졌다. (SSD는 positioning time이 존재하지 않기 때문에 앞에서 살펴본 disk scheduling이 필요가 없다.)