I/O scheduling
Input/output (I/O) scheduling is the method that computer operating systems use to decide in which order I/O operations will be submitted to storage volumes. I/O scheduling is sometimes called disk scheduling.
Purpose
I/O scheduling usually has to work with hard disk drives that have long access times for requests placed far away from the current position of the disk head (this operation is called a seek). To minimize the effect this has on system performance, most I/O schedulers implement a variant of the elevator algorithm that reorders the incoming randomly ordered requests so the associated data would be accessed with minimal head movement.
I/O schedulers can have many purposes depending on the goals; common purposes include the following
- To minimize time wasted by hard disk seeks
- To prioritize a certain processes' I/O requests
- To give a share of the disk bandwidth to each running process
- To guarantee that certain requests will be issued before a particular deadline
Disciplines
Common scheduling disciplines include the following:
- Random scheduling (RSS)
- First In, First Out (FIFO), also known as First Come First Served (FCFS)
- Last In, First Out (LIFO)
- Shortest seek first, also known as Shortest Seek / Service Time First (SSTF)
- Elevator algorithm, also known as SCAN (including its variants, C-SCAN, LOOK, and C-LOOK)
- N-Step-SCAN SCAN of N records at a time
- FSCAN, N-Step-SCAN where N equals queue size at start of the SCAN cycle
- Budget Fair Queueing (BFQ) scheduler on Linux[2][3]
- Completely Fair Queuing (CFQ) scheduler on Linux
- Anticipatory scheduling
- Noop scheduler
- Deadline scheduler
- mClock scheduler[4]
- Kyber[5][6]
- NONE (used for NVM Express drives)
- mq-deadline (used for SSD SATA drives)
- cfq bfq and bfq-mq (used for HDD drives)
See also
- Tagged Command Queuing (TCQ)
- Native Command Queuing (NCQ)
References
- Werner Fischer; Georg Schönberger (2015-06-01). "Linux Storage Stack Diagram". Thomas-Krenn.AG. Retrieved 2015-06-08.
- "Budget Fair Queueing I/O Scheduler".
- "BFQ I/O Scheduler Queued For Linux 4.12 - Phoronix". www.phoronix.com.
- "mClock: Handling Throughput Variability for Hypervisor IO Scheduling". VMware Inc. Retrieved 2015-07-12.
- "blk-mq: Kyber multiqueue I/O scheduler [LWN.net]". lwn.net. 14 Apr 2017. Retrieved 2019-07-19.
- "BFQ I/O Scheduler Lands Along With New Kyber Scheduler - Phoronix". www.phoronix.com. 1 May 2017.
Further reading
- Linux I/O schedulers, from Ubuntu Wiki
- Operating Systems: Three Easy Pieces, by Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau. Arpaci-Dusseau Books, 2014. Relevant chapter: Hard Disk Drives
- Love, R. (2005). Linux Kernel Development, Novell Press. ISBN 0-672-32720-1
- Operating Systems: Internals and Design Principles, seventh edition, by William Stallings.
External links
Media related to I/O scheduling at Wikimedia Commons