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 daemon (computing), services for computer programs. Time-sharing operating systems scheduler (computing), schedule tasks for ef ...

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 mag ...

s 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 The elevator algorithm (also SCAN) is a disk- 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 elevator, where the elevator co ...

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 magn ...

seeks * To prioritize a certain

processes A process is a series or set of activities that interact to produce a result; it may occur once-only or be recurrent or periodic. Things called a process include: Business and management *Business process, activities that produce a specific se ...

' 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 disk- 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 elevator, where the elevator co ...

, 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 th ...

, N-Step-SCAN where ''N'' equals queue size at start of the SCAN cycle *

Completely Fair Queuing Completely Fair Queuing (CFQ) is an I/O scheduler for the Linux kernel which was written in 2003 by Jens Axboe. Description CFQ places synchronous requests submitted by processes into a number of per-process queues and then allocates timeslic ...

(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 read operations. I/O scheduling "Deceptive idleness" is a s ...

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 a ...

* 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