Linux I/O Scheduler 추가자료

리눅스에서 제공하는 여러 I/O 스케줄러에 대한 이해를 돕기 위한 글이 있어 일부 발췌하였습니다.

출처는 아래와 같습니다.
http://osinside.net/osinside/osinside.htm

각 스케줄러가 등장하는 순서와 이유를 보시면 이해가 쉬울 것으로 생각합니다.

내용 중 LBA와 TCQ에 관한 정보는 아래 URL을 참고하세요.

LBA : http://thehermes.kr/entry/하드디스크의-CHS와-LBA-그리고-CHS-LBA-Translator
NCQ : http://swblog.net/entry/Native-Command-Queue-1 (NCQ는 TCQ와 비슷한 알고리즘입니다)
NCQ and TCQ explained : http://www.hardwaresecrets.com/article/315

---

I/O Scheduler

대표적인 device type인 block device에서의 I/O Scheduler를 Linux를 통해서 살펴보겠습니다. 각 block device는 request queue를 유지하고 있습니다. 이런 request queue에는 file system등의 상위 시스템에서 read/write요청(request)가 왔을때 쌓여있다가 실제 장치로 command가 내려가게되는 것입니다(commit). 따라서 각 장치들은 자신의 request queue가 비어있지 않는한 항상 바쁘게 일하고 있게 됩니다. 여기서 하나의 request란 adjacent block들에 대한 read/write요청입니다. 가장 단순하게 이러한 request queue가 FIFO방식이라면, 즉 들어온 순서대로 장치에 commit한다면, 디스크의 경우 큰 문제가 됩니다. seek가 너무 많이 일어나기때문입니다. 따라서 이러한 request들을 적절히 배열하고 적절한 순서로 장치에 commit할 필요가 있습니다. 이러한 역할을 해주는것이 I/O scheduler입니다. process scheduler와 혼동하지 마시기 바랍니다. process scheduler가 CPU를 virtualize하여서 제공한다고하면 I/O scheduler는 block device를 virtualize해서 제공한다고 할 수 있습니다.

I/O scheduler는 결국 request queue를 적절히 조작하여 seek time을 최소화하면서 global throughput을 최대화하는것인데, 여기엔 merging과 sorting의 두개의 기본 동작이 쓰입니다. 즉 request가 들어왔을때 큐에 이미 그 request가 있거나 adjacent한 block에 대한 request가 있을때 두개의 request를 합치는것입니다. 또한 디스크의 seek를 줄이기 위해서 새로 들어온 request를 FIFO방식으로 뒤에 붙이는것이 아니라 이미 기다리고 있는 request들 사이에 block번호에 따라 sorting된 상태가 되게끔 삽입해 넣는것입니다. 이렇게 함으로써 디스크의 seek를 최소화하고 disk의 arm은 디스크를 왕복 횡단하면서 서비스를 할수 있게됩니다. 이러한 모습은 마치 elevator와 비슷하기 때문에 I/O scheduler는 elevator라고도 불리웁니다.

요즘의 디스크들은 Logical Block Address를 사용하며, 디스크는 block number만을 주면 자신의 geometry에 맞춰서 해당하는 블럭을 찾아가기때문에 OS에서는 디스크의 geometry를 신경쓸 필요가 없습니다. 여기서 중요한 가정은, 디스크가 block number를 각 block에 매핑시키는것이 sequential한 경향이 있다는점입니다. 즉 logical block number n과 logical block number n+1은 물리적으로 adjacent하는 경향이 있다는것입니다. (이것이 지켜지지 않을때는 어떻게 될까요?? 또 왜 이것을 지키지 않을때가 있을것이며, 그럴때 I/O스케쥴러는 어떻게 되야하는걸까요?)

이 주제에 대한 더욱 자세한 내용을 여기에서 살펴보시기 바랍니다. - http://www.linuxjournal.com/article/6931

Linus Elevator

Linux 2.4에서 쓰이던 I/O scheduler는 Linus elevator라고 불리우는 간단한 스케쥴러입니다. 새로운 request가 오면, 먼저 merging을 시도합니다. 이게 잘 안되면 sorting된 상태가 될수있는 적당한 위치를 찾아 삽입을 해넣게 되는데, 만약 이때 기존 request들중에서 너무 오래된(미리 정해진 값이 있습니다)것이 발견되면 삽입을 하지 않고 큐의 끝에 넣게 됩니다. 이것은 가까이 뭉쳐있는 request들이 bursty하게 들어오게될때 이로 인해 기존의 다른 request들이 starvation하게 될것이기때문에 이를 방지하기 위한 것입니다. 그러나 이 age check방식이 아주 훌륭한것은 아닙니다. request latency를 줄여주기는 하지만 여전히 request starvation이 발생할 수 있었기 때문입니다. 이러한 starvation은 Linux 2.4 I/O scheduler의 문제점이었습니다. global throughput때문에 fairness의 문제가 생기는것입니다.

write는 보통 process와는 asynchronous하게 수행됩니다. 즉 process가 write콜을 했을때 그 내용들은 실제 디스크가 아닌 버퍼에 쓰인 후에 곧바로 return되고 실제로 request queue에는 나중에 들어가서 디스크에 쓰여지는 것입니다. 이런 writeback으로 인해서 bursty하게 디스크에 쓰여지게 됩니다. 반면에 read의 경우는 file system이 한 구역을 조금 읽고, 다시 다음 구역을 조금 읽고, 하는 방식이 됩니다. 더구나 meta data를 읽기위해서 엉뚱한 구역을 또 조금 읽은 후 그 내용에 따라서 또 다른 read를 하게 됩니다. 더 중요한것은 process와 synchronous하게 동작한다는것입니다. 즉 하나의 read가 완료되기전까지 process는 block되게 됩니다. 이러한 차이점은 I/O scheduler입장에서 보면 write request는 근접한 영역에 bursty하게 들어오는 반면 read request는 시간적 여유를 두고 조금씩 들어오는 것입니다. (dependent read request들이 들어온다는 것입니다.)

이럴때 request starvation문제가 심각해집니다. write request의 bursty함때문에 request starvation의 희생양은 주로 read request가 되는것이고, 더구나 이런 천천히 연달아 들어오고 있는 read request가 모두 starvation에 시달리게되면 해당 process는 극심하게 느려지게 될수밖에 없습니다. 이것을 writes-starving-reads라고 합니다. global throughput을 위해서 디스크의 한 지역에 대한 서비스를 먼저 해주는것이 디스크의 다른 지역에 대한 서비스를 못하게끔 하는, 이러한 unfairness가 발생하는것입니다. 사실 write는 늦어져도 별 상관없지만 (물론 그렇다고 버퍼에 오래두는것은 좋지 않지만) read의 경우 프로세스가 다음일을 진행할 수 없기때문에, 즉 process가 block되게 되고, 이것은 곧바로 latency가 되기 때문에 심각한 문제가 됩니다.

Deadline I/O scheduler

이러한 문제를 해결하기 위해서 Deadline I/O scheduler가 도입됩니다. global throughput을 최대한 보장하면서도 local unfairness를 해결하기 위해서입니다. Deadline I/O scheduler는 기존의 request queue를 sorted queue라고 부르고, 여전히 block number에 대해서 sorting된 상태로 유지하고 있습니다. 여기에 추가로 2개의 큐를 더 추가하는데, 각각 read FIFO queue와 write FIFO queue입니다. 새로 들어오는 request는 sorted queue뿐 아니라 그 종류에 따라서 나머지 둘중에 하나의 큐에 들어가게 됩니다. 다만 이 두개의 큐에서는 FIFO방식으로 들어갑니다. 시간에 따라 배열되는것입니다. 그리고 read FIFO queue는 (기본값) 500ms의, 그리고 write FIFO queue는 (기본값) 5초의 expiration time을 가지고 있습니다. 보통때는 sorted queue에서 request들을 꺼내서 처리하다가, 만약 나머지 두개의 큐에서 시간이 다되었다면, (이것은 현재 시간이 각 큐에서 정해진 expiration time보다 커지는 경우입니다. 각 큐의 첫번째 request가 가장 오래된것이므로 이 request들의 시간만 보면 되는것입니다. 따라서 soft deadline입니다.) 해당 FIFO queue를 처리하게 됩니다. 이렇게 해서 FIFO queue들의 request들이 expiration time을 크게 넘기지 않고 처리됩니다. 물론, deadline이 엄격하게 지켜지고 있지는 않습니다. 이것으로 request starvation을 해결할수 있습니다. write보다 read가 훨씬 작은 expiration time을 가지기 때문에 writes-starving-reads를 해결할수 있습니다.

Anticipatory I/O scheduler

deadline I/O scheduler가 훌륭하기는 하지만, 여전히 문제가 있습니다. 그런 read latency를 줄인것은 결국 global throughput을 희생한것이기 때문입니다. 그리고 이런 현상이 가끔은 심각하게 나타날수 있습니다. write가 심하게 일어나는중에 read request가 주기적으로 들어오고 있는 경우에는 디스크는 write를 하다가 read request하나를 처리하기 위해서 seek를 하고, 다시 돌아와서 write를 하다가 다시 read request를 하기 위해서 seek를 하고, 이것을 반복할수 있습니다. 이것은 오히려 read request때문에 seek가 심해져 read와 write모두 손해를 보고있는 경우가 됩니다. anticipatory I/O scheduler는 이런 점을 해결하기 위해 deadline I/O scheduler를 좀더 똑똑하게 동작하도록 바꾼것입니다.(anticipation heuristic이 추가됩니다.) anticipatory I/O scheduler에서는 read request가 디스크에 commit된 이후에 바로 다른 request를 처리하는것이 아니라 아무것도 하지 않고 잠시 기다립니다. (디볼트값은 6ms) 그리고 이 사이에 들어온 근접한 영역에 대한 request는 곧바로 처리합니다. 보통 이때에 연달아 그 다음 read request가 들어오기때문에 불필요한 seek를 없애고 read request처리에 집중할수가 있는것입니다. 그 사이에 그런 request가 없었다면 다시 이전 상태로 돌아가 원래대로 다음 request를 처리하게 됩니다. 이 예측이 성공하면 2번의 seek를 아끼는것이고, 실패한다면 기다린 시간은 버려지는것입니다. 이것을 위해서는 process와 file system의 행동을 잘 예측해야하는데, 이를 위해 heuristic들을 사용합니다. anticipatory I/O scheduler는 각 프로세스별로 block I/O와 관련된 통계치들을 가지고 이를 토대로 예측을 합니다. 이를 통해 read latency를 줄이면서도 global througput을 높이게 됩니다. 대부분의 workload에서 잘 작동합니다. (서버를 위한 스케쥴러라고 하는데, seek-happy databases관련된 특수한 경우에는 매우 안좋다고 합니다.)

The complete Fair Queuing I/O Scheduler

CFQ I/O scheduler는 지금까지의 스케쥴러와는 다릅니다. 각 process는 자신만의 request queue를 가지고 있고, request들은 이러한 자신만의 request queue로 들어가게 됩니다. 그리고 각 큐들에서 request들은 merge가 되고 sorting이 됩니다. 차이점은 각 process가 자신만의 request queue를 가진다는것입니다. 이후 CFQ I/O scheduler는 한번에 정해진수(기본값 4개)만큼의 request들을 round robin방식으로 각 큐들에서부터 처리합니다. 즉 process level에서 fairness를 보장합니다. 이 방식은 multimedia workload에 맞춰서 설계된 방식이지만 거의 모든 workload에서 이상 현상없이 잘 동작합니다. desktop 환경에서 추천되는 스케쥴러입니다.

The Noop I/O Scheduler

Noop I/O scheduler는 단지 merging만을 하는, 그외에는 전혀 아무런 작업도 하지 않는 스케쥴러입니다. 이 스케쥴러는 디스크가 아닌, 플래시 메모리와 같은 완전히 random-access인 장치들을 위한 스케쥴러입니다.