I/O scheduling#Disciplines

{{Short description|Arbiter for mass storage access in an operating system}}

{{for multi|process scheduling|Scheduling (computing)|process management|Process management (computing)}}

File:The Linux Storage Stack Diagram.svg's storage stack.{{Cite web

| url = https://www.thomas-krenn.com/en/wiki/Linux_Storage_Stack_Diagram

| title = Linux Storage Stack Diagram

| date = 2015-06-01 | accessdate = 2015-06-08

| author1 = Werner Fischer | author2 = Georg Schönberger

| publisher = Thomas-Krenn.AG

}}]]

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
mClock scheduler{{Cite web

| url = https://labs.vmware.com/academic/publications/mclock

| title = mClock: Handling Throughput Variability for Hypervisor IO Scheduling

| accessdate = 2015-07-12

| publisher = VMware Inc.

}}

In Linux kernel:
anticipatory (until 2.6.32)
noop (until 4.10) 🠊 none (since 4.11)
deadline (until 4.10) 🠊 mq-deadline (since 4.11)
cfq (Completely Fair Queuing) (until 4.11) 🠊 bfq (Budget Fair Queueing) (since 4.12){{cite web |url=http://algo.ing.unimo.it/people/paolo/disk_sched/ |title=Budget Fair Queueing I/O Scheduler}}{{cite web|url=https://www.phoronix.com/scan.php?page=news_item&px=BFQ-Queued-Linux-4.12|title=BFQ I/O Scheduler Queued For Linux 4.12 - Phoronix|website=www.phoronix.com}}
kyber (since 4.12){{Cite web|url=https://lwn.net/Articles/720071/|title=blk-mq: Kyber multiqueue I/O scheduler [LWN.net]|date=14 Apr 2017|website=lwn.net|access-date=2019-07-19}}{{cite web|url=https://www.phoronix.com/scan.php?page=news_item&px=Linux-4.12-BFQ-Kyber|title=BFQ I/O Scheduler Lands Along With New Kyber Scheduler - Phoronix|date=1 May 2017|website=www.phoronix.com}}

References

External links

{{Commonscatinline}}

I/O scheduling#Disciplines

Purpose

Disciplines

See also

References

Further reading

External links