I/O scheduling
Input/output (I/O) scheduling is the method that computer operating systems use to decide which order block I/O operations will be submitted to storage volumes. I/O Scheduling is sometimes called 'disk scheduling'.
Purpose
I/O schedulers can have many purposes depending on the goal of the I/O scheduler. Some common ones are:
- 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
Implementation
I/O Scheduling usually has to work with hard disks which share the property that there is long access time for requests which are 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 which re-orders the incoming randomly ordered requests into the order in which they will be found on the disk.
Common scheduling disciplines
- 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
- Completely Fair Queuing (CFQ) on Linux
- Anticipatory scheduling
- Noop scheduler
- Deadline scheduler
See also
References
- ↑ Evgeny Budilovsky (April 2013). "Kernel-Based Mechanisms for High-Performance I/O" (PDF). Tel Aviv University. p. 8. Retrieved 2014-12-28.
Further reading
- 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