커널 2.6에서는 deadline으로 진화함. 2.4 까지만 사용됨. deadline을 설명하기 위해 기록
큐에서 요청을 (block number 순으로) Insertion sort 하다가 age가 오래 된 요청이 있으면 그거부터 처리하는 방식이다.
Completely Fair Queuing (CFQ)
기본 I/O scheduler
CFQ 스케줄러는 광범위한 응용 프로그램과 I/O 시스템 설계에 최상의 성능을 제공하기 때문에 기본 스케줄러로 선택이 되었다. 16개의 CPU를 가지고 있고, Ultra SCSI와 Fiber channel로 구성된 2~64개의 LUN을 가진 시스템에서 CFQ는 탁월한 성능을 발휘한 것으로 알려져 있다. 게다가 CFQ는 다른 I/O subsystem의 성능과 일치할 수 있도록 /proc/sys/scsi subsystem에 있는 nr_requests 파라미터를 조정하여 쉽게 최적화 할 수 있다.
CFQ(Complete Fair Queuing)는 각 프로세스 마다 작업 큐를 가지고 있고 이것들이 round robin방식으로 돌며 정해진 time slice 내에서 작업을 수행하게 된다. time slice안에 작업을 모두 끝내게 되어도 10ms 정도를 추가로 기다리며 혹시나 있을 I/O 작업을 대기하다가 안들어오면 다른 프로세스의 큐로 이동한다. 각 큐에서는 synchronous 요청이 asynchronous보다 우선순위를 가지고 진행되어 writes-starving-reads 문제를 해결한다.
Deadline
Deadline 스케줄러는 real-time 같은 single I/O 처럼 연속된 read를 빠르고 효율적으로 처리하기 위하여 대기 시간을 가지는 방식이다. Single I/O 환경에서는 빠르지만 multip HBA 또는 파일시스템간의 트랜젝션에는 항상 최상의 선택이 될 수는 없다.
Linux Elevator의 작업 큐외에 별도의 read/write 큐를 둔다. 작업 큐에는 요청이 block 번호 순서로 정렬되어 있고, read/write큐는 FIFO로 (요청 들어온 순서대로) 들어간다. I/O Scheduler는 작업 큐에 정렬된 요청들을 가지고 작업을 하다가 expiration time에 넘은 요청이 발견되면 그 요청을 가지고 있는 read(혹은 write)큐에가서 작업을 진행한다. 일반적으로 read 큐는 expiration time이 500ms로 짧고 write 큐는 5초정도로 준다.
Anticipatory
추천 대상
제한된 I/O 설정을 가지고 있는 경우
1 또는 2개의 LUN만 가지고 잇는 작은 시스템
I/O 대기시간 보다 대화형 응답시간에 우선권을 주는 것이 유리할 경우 (대부분의 workstation들..)
연속된 부분의 read 요청의 경우 디스크의 헤더는 이미 다른 위치로 이동해 있는 상태에서 다시 이전의 위치로 이동하여 작업을 수행하게 되는 낭비가 있다. 때문에 연속적인 read를 위해 한번의 read가 마쳐지면 최대 6ms 까지 아무일도 수행하지 않고 (헤드의 위치를 이동하지 않고) 대기해서 연속적인 read작업시 시간을 아끼는 방식의 스케쥴링을 anticipatory I/O scheduler라고 한다.
NOOP
블럭 번호 순으로 정렬은 하지 않고 merging만 하는 스케쥴러 이다. Hard Disk 방식의 controller (sata/sas)를 사용하는 SSD의 경우, 이 방식을 선택하도록 한다.
별도 controller를 가지고 있을 경우, driver단에서 이미 최적화 알고리즘을 가지고 있기 때문에 신경쓸 필요 없음. (예.. Fusion IO)
