OS - 05. Input / Output

Block Device & Character Device

Block Device

- Read/Write Unit: Block(입출력 단위: Block)

- block마다 주소가 존재하며 HDD, CD-ROM, USB등이 있다.

Character Device

- Read/Write Unit: Char(입출력 단위: Char)

- 각 char는 주소가 없으며 Mouse, Printer, Modem, Keyboard등이 있다.

Device Controllers

Block Device

- Read/Write Unit: Block(입출력 단위: Block)

- block마다 주소가 존재하며 HDD, CD-ROM, USB등이 있다.

Device Controller

- 각 device들은 여러 device들을 다루도록 도와주는 device controller가 존재한다.

- controller는 CPU에 interrupt를 보내거나 block을 bit로 변환하거나 buffer를 관리하는 등의 작업을 수행한다.

Memory Bus Architecture

single bus/ dual bus architecture. dual-bus로 구성하면 전용 버스가 생기므로 메모리 접근 속도가 빨라진다.

Direct Memory Access (DMA)

프로그램이 디스크로부터 데이터를 읽기 위해서는 CPU와 디스크의 속도차이가 존재하기 때문에 DMA controller를 통해 데이터를 접근한다. CPU가 디스크의 데이터를 읽으려면 DMA Controller에게 주소와 count등의 정보를 넘겨주면 스스로 interrupt한다. DMA Controller는 CPU에게 전달받은 정보를 바탕으로 동작을 수행하여 값을 읽어와 버퍼에 넣는다. 버퍼에 가져온 데이터는 Cycling Stealing(Bus transfer mode)을 통해 CPU-Memory간의 버스를 이용하여 메인 메모리에 데이터를 copy한다. 작업이 완료되었다면 CPU는 꺠어나 메인 메모리의 데이터를 이용하여 작업을 계속 수행한다.

Interrupts Revisited

bus에 interrupt 라인이 존재하여 CPU에 신호를 보낼 수 있으며 CPU는 신호를 받으면 현재 실행하는 명령까진 실행 한 후 멈추고 다른작업을 한다.

1. interrupt controller는 I/O device의 작업이 수행이 끝나면
2. CPU에 interrupt를 발생시킨다.
3. CPU는 interrupt가 끝났다는 신호를 보낸다.

Precise and Imprecise Interrupts

precise interrupt의 속성

1. PC(Program Counter)는 알려진 장소에서 저장되어야한다.
2. PC이전에는 모두(fully) 실행되어야한다.
3. PC 이후는 하나도 실행되지 않은 상태여야한다.
4. PC가 가리키는 위치는 정확히 알아야한다.

- Precise interrupt - PC 이전에는 모두 실행되며 이후에는 한개도 실행되지 않은 상태.

- imprecise interrupt - 아주 많은 명령이 조금씩 실행된 상태. 이 상태를 그대로 저장 및 복구해서 실행하는것은 어렵기 때문에 현실은 a방식으로 동작하게 한다.

Goal of I/O Software

• Device Independency : 각 device는 독립적이어야한다.
• Uniform Naming : 디바이스마다 이름이 지정되어야한다.(OS가 해준다)
• Error Handling : 버퍼또는 메모리가 없는경우 등에는 에러처리를 해야한다.
• Synchronous vs asynchronous : 동기적으로 처리(입력후멈추고 하나씩 처리되기를 기다림)하면 속도가 느려지므로 디바이스는 대부분 비동기적인 방식을 사용한다.
• Buffering : 디바이스의 데이터는 OS 내부의 버퍼로 데이터를 가져와서 프로그램(CPU)에 copy하여 전해진다.
• Sharable vs dedicated devices : disk는 공유가능하다.

Buffering

user space의 데이터를 OS의 버퍼로 옮기고, DMA회로를 통해 네트워크 컨트롤러 카드의 버퍼로 옮긴다. 이 데이터를 네트워크를 통해 전송한 뒤 반대의 과정이 일어난다. 5번의 많은 copy가 발생한다!

Magnetic Disks

RAID(Redundant Array of Independent Disk)

Data를 strip단위로 쪼개어 여러개의 디스크를 하나의 디스크처럼 사용하기위해 묶어주는 방법이다.

a: RAID level 0

b: RAID level 1, 왼쪽의 disk strip들을 그대로 오른쪽에 복제하여 저장하는 방법이다.(미러링) 하지만 이 방법은 비용이 증가할 수 있다.

c: RAID level 2, bit 1~4를 fraction하여 저장한다. 만약 bit4가 고장났다면 1~3과 5~7을 읽어 복구할 수 있다.

d: RAID level 3, 4bit를 쪼개서 parity를 적는다. 만약 bit4가 고장났다면 나머지 bit와 parity를 읽어서 복구할 수 있다.

e: RAID level 4, strip 0~3으로 나누어 parity를 strip 묶음마다 저장한다.

f: RAID level 5, level 4에서 parity disk는 자주 참조될 수 있으므로 여기에 parity를 분산하여 저장한다.

Disk Formatting

b: single interleaving. c: double interleaving

-> interleaving: 만약 0번 섹터를 읽고 바로 다음 1번섹터에 쓸려면 디스크가 돌아가 지나치게되어 한바퀴를 더 돌고 써야한다. 이를 방지하기위해 연속 섹터에 간격을 주어 1칸 또는 2칸씩 떨어뜨리는 방법을 사용할 수 있다.

Disk Arm Scheduling Algorithms

• Read/write time factors

1. Seek time
2. Rotational delay
3. Actual data transfer time

• Seek time dominates
• Error checking is done by controllers

First-in, first-out (FIFO)

요청이 도착한 순서대로 실행하는 방법이다. 실린더 번호 순서대로 요청이 처리된다.

Shortest Service Time First

현재 헤드 위치에서 가장 가까운것을 읽는 방법이다. 다만 이 방법은 현재 헤드 위치와 먼 요청은 starvation이 일어날 수 있다는 문제가 있다.

SCAN or elevator algorithm

헤드의 트랙의 방향을 정한 후 더이상 처리할게 없으면 방향을 바꾸어 처리한다. 엘리베이터와 똑같이 작동하는 방식이다.

-> starvation이 없다! 요청들의 바깥쪽,안쪽과 중간부분의 서비스타임 편차가 존재한다(가운데 부분이 가장 서비스 많이됨)

 

C-SCAN (Circular-SCAN)

헤드가 양 방향으로 움직이지않고 오직 한 방향으로 움직이는 방식이다. 번호가 큰쪽으로 헤드가 이동하고, 끝까지 읽으면 다시 처음 0번부터 헤드를 빠르게 움직인 다음 서비스한다. 입출력요청이 많은 시스템에서 헤드가 움직이면 운이 좋은 트랙은 바로 서비스되지만 운이 나쁜 트랙은 (헤드가 떠난 다음 요청) 서비스 시간이 오래걸린다.

N-step-SCAN

Queue가 여러개 존재한다. 한 큐에는 최대 N개까지 요청이 오며, C-SCAN으로 가면서 큐마다 처리한다. (N개의 요청 안에서만 편차-운이 좋고 나쁜 시스템이 존재한다)

FSCAN

Queue를 2개 사용한다. 한번 서비스를 시작했으면 이 후에 서비스 요청이 왔다면 다른 큐에 매달리고, 한 큐가 끝나면 다른 큐를 서비스하며 번갈아가며 실행한다.

Error Handling

-> 트랙마다 spare 섹터가 존재하여서 Bad sector가 있다면 이 공간으로 교체한다.(b) 또는 한 섹터씩 미뤄서 섹터를 연속적으로 만들 수도 있다.(c)

Stable Storage

b: ECC error(변경하다 죽음) ~ crash가 발생하면 a상태로 복구하고, crash가 발생하지 않으면 c상태가 된다.

d: 마찬가지로 crash가 발생하면 1번 disk를 copy하여 e상태가 된다.

(새로운 데이터를 기록하다가 crash가 나면 나중에 데이터를 읽어보다가 ECC에 에러를 확인한다.)