I/O Management and Disk Scheduling Lecture #10 I/O Management and Disk Scheduling

I/O 장치 분류 (1) Human readable 컴퓨터 사용자와 통신하기 위해 사용하는 장치 프린터 비디오 디스플레이 터미널 디스플레이 장치 키보드 마우스

I/O 장치 분류 (2) Machine readable 주변 전자 장치와 통신하기 위해 사용하는 입출력 장치 디스크 및 테이프 드라이브 I/O Controllers Sensors Actuators

I/O 장치 분류 (3) Communication 원격 장치와 통신하기 위해 사용하는 장치 Digital line drivers Modems

I/O 장치의 차이점 (1) Data rate 데이터 전송 속도 May be differences of several orders of magnitude between the data transfer rates

I/O 장치의 차이점 (2) Application(응용) 파일을 저장하는 디스크에 입출력하기 위해서는 파일 관리 소프트웨어를 요구된다 가상 메모리 페이지를 저장하는 디스크로의 입출력은 특수한 하드웨어와 소프트웨어를 요구한다 시스템 관리자가 사용하는 터미널(콘솔)은 다른 터미널보다 더 높은 우선 순위를 가진다

I/O 장치의 차이점 (3) Complexity of control Unit of transfer Data may be transferred as a stream of bytes for a terminal or in larger blocks for a disk Data representation Encoding schemes Error conditions Devices respond to errors differently

I/O 수행 기법 (1) Programmed I/O Interrupt-driven I/O Process is busy-waiting for the operation to complete Interrupt-driven I/O I/O command is issued Processor continues executing instructions I/O module sends an interrupt when done Direct Memory Access (DMA) DMA module controls exchange of data between main memory and the I/O device Processor interrupted only after entire block has been transferred

I/O 수행 기법 (1) I/O 기법의 비교 pp. 546, 표 11.2 참조

I/O 기능의 발전 과정 (1) Processor directly controls a peripheral device Controller or I/O module is added Processor uses programmed I/O without interrupts Processor does not need to handle details of external devices Controller or I/O module with interrupts Processor does not spend time waiting for an I/O operation to be performed Direct Memory Access Blocks of data are moved into memory without involving the processor Processor involved at beginning and end only

I/O 기능의 발전 과정 (2) I/O module is a separate processor I/O processor I/O Channel I/O processor I/O module has its own local memory It’s a computer in its own right

DMA(Direct Memory Access) (1) 주기억장치와 I/O 모듈사이에 직접 데이터를 전송 DMA 장치는 I/O를 수행하기 위해 시스템 제어를 가져온다 시스템 버스를 통해 메모리에 데이터를 전송하기 위해 CPU로부터 시스템 제어를 가져온다 Cycle Stealing(사이클 훔치기) 프로세서가 버스를 사용하지 않을 때에 버스를 사용 프로세서가 잠정적으로 연산을 일시 정지하도록 하여 버스를 사용 – 일반적인 접근법 No interrupts occur 인터럽트 처리에 따른 오버헤드가 없다

DMA(Direct Memory Access) (2)

DMA(Direct Memory Access) (3) Cycle stealing는 CPU의 처리 속도를 떨어뜨린다 CPU는 DMA 중단점 에서 DMA I/O가 발생하면 일시 중지한다

DMA(Direct Memory Access) (4) DMA 모듈과 I/O 모듈이 시스템 버스를 공유하는 방식 그림 11.4(a) 비용은 적게 들지만 비효율적  하나의 워드를 전송하기 위해 두 번의 시스템 버스 주기를 사용 DMA와 I/O 기능을 통합하는 방식 그림 11.4(b) DMA 모듈과 I/O 장치들간에 별도의 경로를 유지  요구되는 버스 사이클 수가 감소 가능 DMA 모듈의 I/O 인터페이스 수가 증가 별도의 I/O 버스를 이용하여 DMA 모듈을 연결하는 방식 그림 11.4(c) DMA 모듈과 I/O 모듈사이의 데이터 전송은 시스템 버스를 경유하지 않음

DMA(Direct Memory Access) (5)

DMA(Direct Memory Access) (6)

DMA(Direct Memory Access) (7)

I/O 기능 설계 이슈 (1) 효율성(Efficiency) 대부분의 I/O 장치는 주기억장치 및 CPU와 비교하여 속도가 아주 느리다 속도 차이에 대한 접근법으로 다중프로그래밍 기법을 사용 어떤 프로세스들이 I/O 연산을 기다리는 동안에 다른 프로세스가 실행하도록 허용 여전히 I/O 장치의 소도가 CPU 속도를 따라가지 못해 디스크에서 실행 준비된 프로세스를 로드하는 스와핑(swapping)을 요구하는 경우가 발생 Swapping도 I/O를 요구 시스템 성능 향상을 위해서는 효율적인 I/O를 요구

I/O 기능 설계 이슈 (2) 범용성(Generality) 장치의 다양한 특성으로 인해 동일한 방식으로 접근하는 범용성은 실제적으로 어렵다 계층적 모듈 접근법 운영체제의 상위 레벨에서는 일반적인 기능으로 장치에 접근 운영체제의 하위 레벨에서는 I/O 장치의 특성을 고려하여 장치에 접근함으로써 상위 레벨에 I/O 장치의 상세한 부분을 감출 수 있도록 한다

I/O 기능 설계 이슈 (3) I/O 기능의 논리적 구조 계층적 구성 기법을 적용한 I/O 기능의 구성 적절한 인터페이스를 정의함으로써 하위 레벨의 변경은 상위 레벨 구조에 영향을 미치지 않도록 한다 I/O 기능의 계층적 구조 예:

I/O Buffering (1) I/O 버퍼링의 필요성 프로세스는 상대적으로 느린 I/O가 완료될 때까지 대기 상태에 있다 단일 프로세스 교착상태를 유발

I/O Buffering (2) I/O 버퍼링은 입출력 장치의 동작 특성을 고려 블록 위주(Block-oriented) I/O 장치 대개 고정된 크기의 블록 단위로 정보를 저장 한번에 하나의 블록을 전송 디스크 장치, 테이프 장치 등 스트림 위주(Stream-oriented) I/O 장치 바이트 스트림 형태로 데이터를 전송 터미널, 프린터, 통신 포트, 마우스 등

I/O Buffering (3)

I/O Buffering (4)

Single Buffer (1) 운영체제는 I/O 요구에 대해 주기억장치의 시스템 영역에 하나의 버퍼를 할당한다 블록 위주 장치 입력 전송은 시스템 버퍼로 이루어진다 프로세스는 입력된 블록 데이터를 사용자 영역으로 이동시키고 즉각적으로 다른 블록을 요구 Read ahead or Anticipated input 프로세스는 다음 블록이 입력되는 동안 하나의 블록을 처리 입력이 주기억장치의 시스템 영역에서 이루어지기 때문에 입출력을 요구한 프로세스를 스와핑할 수 있다 운영체제는 프로세스에 할당된 시스템 버퍼들에 대한 기록을 유지함으로써 처리 절차가 복잡해짐

Single Buffer (2) 스트림 위주 장치 한번에 하나의 라인이나 한 바이트를 전송 터미널의 경우 한번에 하나의 라인을 입력하거나 한 라인을 출력 시스템 버퍼는 단일 라인을 저장 프로세스는 한 라인의 데이터가 입력될 때까지 일시 정지

Double Buffer 두 개의 시스템 버퍼를 할당 운영체제가 하나의 버퍼에 데이터를 채우는 동안에 프로세스는 다른 버퍼에 접근하여 데이터를 처리 단일 버퍼보다는 성능 향상

Circular Buffer 제한된 메모리 영역에서 두개 이상의 버퍼를 구성하여 사용 I/O 연산이 어느 순간 집중적으로 발생하는 경우 이중 버퍼로는 부족 원형 버퍼의 각 버퍼는 하나의 전송 단위가 된다 I/O 연산과 프로세스의 속도가 비슷할 경우에 적합

디스크 성능 인자 (1) 디스크 입출력 동작 디스크 입출력을 위해서는 디스크 헤드가 원하는 트랙으로 이용하고 원하는 섹터의 시작 위치로 이동한다 헤드 아래의 있는 섹터가 회전할 때에 데이터를 읽어 전송한다

디스크 성능 인자 (2) 탐색 시간(Seek time) 헤드가 원하는 트랙에 위치하는데 걸리는 시간 헤드가 수평방향으로 이동하는데 요구되는 시간 회전 지연 시간(Rotational delay or rotational latency) 헤드가 데이터 전송이 요구되는 섹터에 위치하는데 걸리는 시간 디스크 접근 시간(Access time) 탐색 시간과 회전 지연 시간의 합 디스크 입출력를 위해 원하는 위치로 이동하는데 걸리는 시간

Timing of a Disk I/O Transfer

디스크 스케줄링 정책 (1) 탐색 시간(Seek time)는 디스크 입출력 성능 차이의 원인 하나의 디스크에 대해 다수의 입출력 요구가 존재 입출력 요구에 대한 서비스 순서에 따라 탐색 시간이 증감함으로 디스크 입출력 성능이 좌우 입출력 요구를 임의적으로 선택하여 서비스하면 (random scheduling) 디스크 입출력 성능은 최저 성능을 얻게 된다  디스크 성능의 최적화를 위해 디스크 스케줄링이 필요

디스크 스케줄링 정책 (2) 선입선출(First-in, first-out :FIFO) 프로세스의 입출력 요구가 도착한 순서대로 처리 모든 프로세스에 대해 공정하다 다수의 입출력 요구가 있는 경우에는 임의 순서 서비스와 성능이 비슷해진다 pp.563 그림 11.7(a), pp.564 표 11.3 참조

디스크 스케줄링 정책 (3) 우선 순위(Priority) 스케줄링 목적이 디스크 사용을 최적화하는 것이 아니라 운영체제의 다른 목적을 만족하기 위함 실행 시간이 짧은 일괄처리 작업이나 대화식 작업에 높은 우선 순위를 할당  좋은 응답 시간을 제공

디스크 스케줄링 정책 (4) 후입 선출(Last-in, first-out : LIFO) 가장 최근의 입출력 요구를 먼저 처리 트랜잭션 처리 시스템에서 좋은 성능을 제공 트랜잭션의 지역성을 이용함으로써 헤드가 거의 이동할 필요가 없다 처리율을 향상시키고 큐의 길이도 짧아 진다 큰 작업의 부하나 다수의 후입 요구로 인해 먼저 도착한 입출력 요구에 대해 기아가 발생할 가능성이 존재

디스크 스케줄링 정책 (5) Shortest Service Time First(SSTF) 디스크 헤드의 현재 위치로 부터 디스크 암의 움직임을 최소화하는 디스크 입출력 요구를 먼저 처리 항상 최소의 탐색 시간의 요구하는 입출력 요구를 선택

디스크 스케줄링 정책 (6) SCAN 우선순위, LIFO, SSTF 등의 스케줄링 기법에서는 기아의 가능성을 내포 새로 도착하는 요구가 이전에 도착한 요구보다 먼저 선택함으로써 큐에 처리되지 않은 요구가 존재할 수 있다 디스크 헤드를 단지 한 방향으로 움직이도록 하고 헤드가 움직이는 방향의 마지막 트랙에 도착하거나 움직이는 방향에 요구가 없을 때까지 그 방향에 존재하는 모든 요구를 처리하는 스케줄링 기법 한 방향으로 서비스가 끝나면 반대 방향으로 검색하면서 서비스한다 가장 안쪽이나 바깥쪽 트랙을 요구하는 작업과 가장 늦게 도착한 작업에 유리

디스크 스케줄링 정책 (7) C-SCAN SCAN 정책에서 디스크 헤드가 단지 한쪽 방향으로만 이동하면서 서비스하도록 제한 한 방향으로 이동하면서 마지막 트랙을 읽으면 헤드는 디스크의 반대 끝으로 이동하여 다시 같은 방향으로 검색한다 SCAN 정책이 양쪽 끝 트랙에 접근하는 작업에 대해 유리하게 동작하는 불공정 문제점을 해결

디스크 스케줄링 정책 (8) SSTF, SCAN, C-SCAN 정책에서는 “암 고착(Arm stickness)” 문제가 발생할 수 있다 입출력 요구들이 한 트랙에 대해 높은 접근율을 가짐으로써 헤드가 오랜 시간 동안 움직이지 않을 수 있다 N-step-SCAN Segments the disk request queue into subqueues of length N Subqueues are process one at a time, using SCAN New requests added to other queue when queue is processed FSCAN Two queues One queue is empty for new request

디스크 스케줄링 알고리즘 비교

RAID 0 (non-redundant)

RAID 1 (mirrored)

RAID 2 (redundancy through Hamming code)

RAID 3 (bit-interleaved parity)

RAID 4 (block-level parity)

RAID 5 (block-level distributed parity)

RAID 6 (dual redundancy)

Disk Cache Buffer in main memory for disk sectors Contains a copy of some of the sectors on the disk

Least Recently Used The block that has been in the cache the longest with no reference to it is replaced The cache consists of a stack of blocks Most recently referenced block is on the top of the stack When a block is referenced or brought into the cache, it is placed on the top of the stack

Least Recently Used The block on the bottom of the stack is removed when a new block is brought in Blocks don’t actually move around in main memory A stack of pointers is used

Least Frequently Used The block that has experienced the fewest references is replaced A counter is associated with each block Counter is incremented each time block accessed Block with smallest count is selected for replacement Some blocks may be referenced many times in a short period of time and then not needed any more

UNIX SVR4 I/O

Windows 2000 I/O

Disk Data Layout Sectors Tracks Inter-sector gap Inter-track gap

Disk Layout Using Constant Angular Velocity Track 2, Sector 7 Track 0, Sector 0