운영체제 11장 - I/O Management and Disk Scheduling


IO장치는 여러 종류가 있다
사람이 읽을수 있는것, 기계가 읽는것, 통신장치


위로 갈수록 고속으로 전송


다양한 장치는 다양한 방법으로 프로그램 하게 되는데
programmed io는 프로세서가 io 명령을 실행을 해서 실행에 따라 io장치들이 동작하는것
interrup-driven io는 프로그램이 동작을 시켜놓고 처리가 끝난 다음 인터럽트에 의해서 사용자 프로그램이 인터럽트를 받아서 처리를 끝냄
DMA는 data block을 옮길때 io장치와 유저 프로그램 영역간에 데이터를 옮길때 dma라는 장치를 사용해서, 프로세서의 메모리 사이클을 훔쳐서 메모리 사이클 동안에 데이터를 덩어리로 옮기게 하는 장치. 이것을 사용해서 io장치의 버퍼와 메인 메모리간의 데이터를 옮기는 방법이 있었다
디스크, 모뎀같은 대용량의 데이터를 옮기는것은 dma를 사용하고 있다


인터럽트를 사용하는지 안하는지
cpu를 사용하여 데이터를 옮기는지, dma를 사용해서 옮기는지에 따라서
프로그램들의 방법을 분류한것


io장치를 컴퓨터에 붙기에 되면
첫번째로 프로세서를 사용해서 직접 컨트롤하는 방법을 사용하게 되고
그다음엔 컨트롤러(io채널, io모듈)를 사용하게 되고 
인터럽트 사용해서 컨트롤러 동작
DMA사용
io모듈에 독립적인 프로세서를 둬서 
io모듈이 로컬 메모리를 갖고 그것과 cpu사이에 데이터를 전송하는 방법


DMA의 구조
몇개의 바이트를 옮겨야 하는지 카운터를 두고
데이터 레지스터, 주소 레지스터가 있다
control logic은 cpu와 연결되고, 다른 라인들은 각각 버스에 연결된다


dma는 다양한 configuration이 있다


io management를 설계하는데 있어서 중요한 두가지 목적은
efficiency
입출력 장치가 느리므로 성능의 bottleneck이 될수 있다. 효율적으로 메인메모리와 io 버퍼간의 데이터 전송이 되도록 해야. disk io가 성능에 영향을 많이 미친다

generality
여러 장치들을 다루면서도 일반화된 인터페이스를 제공해야
계층적인 아키텍쳐를 사용해서 설계하게 된다


운영체제는 복잡한 장치를 연결하는데, 복잡함을 감추기 위해서 계층구조를 사용한다
설계에 유용하고, 구현도 간편하고 전체 비용을 줄이는 산업측면에서도 유용




이러한 여러 모듈들이 연결될때는 버퍼링을 사용하여 사용자에게 고속의 데이터 전송을 가능하게 제공하고 있다
하드디스크와 같은 블럭단위로 읽는 디바이스는 정보들이 고정된 사이즈의 데이터 블록으로 io장치와 메인메모리 사이에 전송이 된다. 이러한 블록들의 고유 번호를 가지고 데이터 전송의 요청을 하게 된다, 디스크나 USB가 예시
stream-oriented device는 데이터를 stream of byte로 전송하게 된다, 터미널, 프린터, 통신장치가 예시



이러한 장치를 구성할때, 고속의 데이터 전송을 하는데
io장치와 유저 프로세스간의 속도차를 극복하기 위해서 버퍼를 사용하게 된다. 사용자 속도가 느리다면 쌓아뒀다가 전달하고, 빠르다면 거의 실시간으로 전달하게 된다
io장치가 고속일때는 유저프로세스에서 요구하는 속도로 그대로 전송하는것이 좋기 때문에, 중간에 버퍼 없이 직접적으로 포인터를 가지고 전달해주게 된다(no buffer)


싱글 버퍼를 사용하는 경우, block oriented divice와 연결되는 경우 block oriented single buffer 제공
싱글 버퍼가 있기 때문에 reading하는 경우 사전에 input의 데이터를 버퍼에 쌓아두게 된다, 그렇게 해서 speed up을 제공하고
운영체제에 이것을 관리하는 로직이 있어야 한다는 어려움이 있다
블럭 버퍼에 저장되는 데이터를 어떻게 swapping과 관련되서 관리할지를 잘 프로그램 해야 함


stream-oriented single buffer
stream oriented divice에 싱글 버퍼를 사용하여 사용자 프로그램과 io장치를 연결
라인단위로 전송하는것과 바이트 단위로 전송하는 것이 있다
바이트단위는 터미널과 같은 저속 장치에 사용하고
라인단위는 스크롤모드 터미널과 같은곳에 사용


더블버퍼는 하나의 버퍼 대신 두개 버퍼를 사용, buffer swapping이라고 한다
보통 frame buffer라고 해서 비디오 버퍼의 경우 이런 방식을 사용
한쪽에서 입력을 해준다면, 다른쪽에서 이미 업데이트 된 내용을 화면에 보여주도록 한다. 교대로 사용하는것


circular buffer
원형 큐의 형태로 사용
보통 고속의 데이터를 받을때 사용 이더넷 같은 곳에서 


버퍼는 유튜브를 볼때 제공하는 기능과 같다, 데이터의 스무딩 기능 제공.
보내는 속도가 일정하지 않더라도, 화면에 보여지는 영상은 일정한 속도가 되는것처럼



하드디스크는 data transfer를 위해 이런 시간이 필요하다
디바이스가 available할때까지 대기시간
컨트롤러인 channel을 기다리는 시간
요청이 채널에 전달되었을때 헤드가 움직이는 시간 seek time
원하는 섹터의 위치를 기다리는 시간 rotational delay
실제로 데이터를 읽거나 쓰는시간

디바이스에 있는 채널에 요청이 전달되어 처리하는데 걸리는 시간이 device busy
seek time, rotational delay를 줄이는게 성능의 관건


디스크 드라이브가 동작을 할때, 일정 속도로 회전
읽거나 쓰는 동작을 하기 위해 한 위치에 헤드가 위치해야.
seek time, rotational delay둘을 더해서 access time이라고 한다


여러가지 디스크 스케줄링 알고리즘이
다음 access할 트랙이 주어졌을때, 트랙 개수로 속도가 결정되므로 트랙 개수를 비교해서 성능비교를 한것


FIFO
요청이 주어진 순서대로 서비스를 하는방법
모든 프로세스가 fair하게 서비스를 받게 되고, 요청이 오는 순서대로 서비스를 받기에 랜덤하게 들어온다면 random scheduling이 된다


PRI
interactive job, short batch job이 더 서비스를 잘 받도록, 우선순위를 갖게 한다
이렇게 함으로서 interactive response time이 좀더 좋게 함


SSTF
헤드에 최소한의 움직임을 하는 요청부터 처리, seek time을 minimize


SCAN
헤드를 최대한으로 움직이게 하는 job은 항상 느리게 서비스 되거나 starvation이 발생할 수 있다. 골고루 전체를 스캔하면서 처리
arm의 움직임을 한쪽 방향으로 처리, 헤드도 관성의 영향을 받으므로 이렇게 하는것이 좋을거라고 생각했기 때문
엘리베이터가 최고층에서 1층으로 오가는것처럼 움직이므로 엘리베이터 알고리즘이라고 하며, 
이때 중간에 있는 요청이 서비스를 받을 확률이 높다. 확률적으로 가운데가 favor가 높다


C-SCAN
이것을 공평하게 하기 위해서 한 방향으로 움직일때만 서비스를 하고, 다른 방향으로 움직일때는 하지 않는 방법 고안


N-step-SCAN
현재 읽고 있는 트랙 근처에 있는것을 먼저 읽게 하는것은 arm이 고정되는 문제를 가질수 있다
이러한것을 해결하기 위해서 여러개의 step으로 나누어서 SCAN하는 방법이 고안되어 있다


FSCAN
두개의 subqueue를 나누고 한 큐를 처리하고 다음 큐를 처리하는 방식, 앞에서 본 favor를 없애는 방법이다


요약


RAID
여러 디스크를 사용해서 하나의 디스크처럼 제공, recover가능



0
여러개의 물리적인 디스크가 있을때 redundant한 데이터가 없이 데이터를 나누어 저장
논리적인 디스크는 strip으로 나누어져서 읽는 속도와 쓰는 속도를 빠르게 할수 있다
각각의 디스크를 동작시켜서 RW를 병렬로 실행, 버스가 이들 데이터를 전달할수 있는 속도가 충분하다면 4배의 속도가 된다


1
strip을 나누는것은 같은데
redundant를 둬서 중복되게 저장. drive fail시 백업을 사용하여 복구
디스크를 두배로 사용해서 비용문제


2
strip보다 적은 개수의 디스크를 사용해서 복구를 위해 저장
해밍 코드를 둬서, 해밍 distance보다 작은 크기를 갖는 오류를 복구하게 된다


3
한개의 디스크를 사용해서 데이터를 복구


4
블럭 단위로 parity를 계산
parity가 있는 디스크와 다른 디스크 하나가 같이 깨지면 복구가 불가


5
parity를 흩어놓아서 부분적으로 깨졌을때 복구가 가능하게 함


6
parity를 두가지 다른 방식으로 계산하여 흩어놓는 방식



디스크를 사용할때도 캐시를 사용하여 읽고 쓰는속도 개선 가능하다
한 블럭을 읽었을때 인접한 블럭도 읽을 가능성이 높다는걸 이용
필요한 섹터를 이미 읽어냈는지 확인하고 있다면 캐시를 사용하여 디스크의 요구를 해결



캐시를 LRU 방식을 사용하여 관리
자주 reference되는 포인터를 맨 위에 올려 놓음으로서 구현


LFU
각 블럭이 얼마나 참조되는지를 저장하고 있다가 그것이 작은 블록을 replace하는 방법도 있다


유닉스에는 두가지 타입의 io가 있다





그 방법을 제공하는것에 x 표시됨


리눅스
모든 io장치는 디바이스 밑의 special file로 연결되어 있고
block, character, network device로 연결되어 관리됨
linux elevator알고리즘 사용


엘리베이터 알고리즘은 starvation을 막기위한 프로시저가 있지만
데드라인을 만족시키지 못하는 경우가 있다. 입출력 요청의 불균형에 따른것
이것을 해결하기 위해 deadline scheduler를 제공
큐를 3개 두고 여러 서비스를 각각 다른 큐에 두고 스케줄링함, 엘리베이터 알고리즘을 통해 디스크로 전달






윈도우