Input/output (I/O) scheduling is the method that computer

operating system An operating system (OS) is system software that manages computer hardware, software resources, and provides common services for computer programs. Time-sharing operating systems schedule tasks for efficient use of the system and may also in ...

s 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 drive A hard disk drive (HDD), hard disk, hard drive, or fixed disk is an electro-mechanical data storage device that stores and retrieves digital data using magnetic storage with one or more rigid rapidly rotating platters coated with magnet ...

s that have long

access time Access time is the time delay or latency between a request to an electronic system, and the access being completed or the requested data returned * In a computer, it is the time interval between the instant at which an instruction control uni ...

s 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 The elevator algorithm (also SCAN) is a hard disk, disk-I/O scheduling, scheduling algorithm to determine the motion of the disk's arm and head in servicing read and write requests. This algorithm is named after the behavior of a building elevat ...

that reorders the incoming randomly ordered requests so the associated data would be accessed with minimal arm/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 A hard disk drive (HDD), hard disk, hard drive, or fixed disk is an electro-mechanical data storage device that stores and retrieves digital data using magnetic storage with one or more rigid rapidly rotating platters coated with magnet ...

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 Shortest seek first (or shortest seek time first) is a secondary storage scheduling algorithm to determine the motion of the disk read-and-write head in servicing read and write requests. Description This is a direct improvement upon a first- ...

, also known as Shortest Seek / Service Time First (SSTF) *

Elevator algorithm The elevator algorithm (also SCAN) is a hard disk, disk-I/O scheduling, scheduling algorithm to determine the motion of the disk's arm and head in servicing read and write requests. This algorithm is named after the behavior of a building elevat ...

, also known as SCAN (including its variants, C-SCAN, LOOK, and C-LOOK) *

N-Step-SCAN N-Step-SCAN (also referred to as N-Step LOOK) is a disk scheduling algorithm to determine the motion of the disk's arm and head in servicing read and write requests. It segments the request queue into subqueues of length ''N''. Breaking the queue ...

SCAN of ''N'' records at a time *

FSCAN FSCAN is a disk scheduling algorithm to determine the motion of the disk's arm and head in servicing read and write requests. It uses two sub-queues. During the scan, all of the requests are in the first queue and all new requests are put into the ...

, N-Step-SCAN where ''N'' equals queue size at start of the SCAN cycle * Completely Fair Queuing (CFQ) on Linux *

Anticipatory scheduling Anticipatory scheduling is an algorithm for scheduling hard disk input/output (I/O scheduling). It seeks to increase the efficiency of disk utilization by "anticipating" future synchronous I/O, synchronous read operations. I/O scheduling "Deceptive ...

Noop scheduler The NOOP scheduler is the simplest I/O scheduler for the Linux kernel. This scheduler was developed by Jens Axboe. Overview The NOOP scheduler inserts all incoming I/O requests into a simple FIFO queue and implements request merging. This ...

Deadline scheduler The deadline scheduler is an I/O scheduler for the Linux kernel which was written in 2002 by Jens Axboe. Overview The main goal of the Deadline scheduler is to guarantee a start service time for a request. It does so by imposing a deadline on ...

* mClock scheduler * Budget Fair Queueing (BFQ) scheduler. * Kyber *NONE (used for NVM Express drives) *mq-deadline (used for SSD SATA drives) *cfq bfq and bfq-mq (used for HDD drives)

References

External links

*{{Commonscatinline

Purpose

Disciplines

See also

References

Further reading

External links