CFQ
Encyclopedia
Completely Fair Queuing (CFQ) is an I/O scheduler
for the Linux kernel
which was written in 2003 by Jens Axboe
.
into a number of per-process queues and then allocates timeslices for each of the queues to access the disk
. The length of the time slice and the number of requests a queue is allowed to submit depends on the IO priority of the given process. Asynchronous requests for all processes are batched together in fewer queues, one per priority. While CFQ does not do explicit anticipatory
IO scheduling, it achieves the same effect of having good aggregate throughput for the system as a whole, by allowing a process queue to idle at the end of synchronous IO thereby "anticipating" further close IO from that process. It can be considered a natural extension of granting IO time slices to a process.
4 used this I/O scheduler as the default even though it used a kernel based on a 2.6.9.
/queue/scheduler variable in the sysfs
filesystem.
.
I/O scheduling
Input/output scheduling is a term used to describe the method computer operating systems decide the order that block I/O operations will be submitted to storage volumes...
for the Linux kernel
Linux kernel
The Linux kernel is an operating system kernel used by the Linux family of Unix-like operating systems. It is one of the most prominent examples of free and open source software....
which was written in 2003 by Jens Axboe
Jens Axboe
Jens Axboe is a Linux kernel hacker. He is the current Linux kernel maintainer of the block layer and other block devices, along with contributing the CFQ I/O scheduler, Noop scheduler, Deadline scheduler and splice IO architecture. Jens is also the author of the blktrace utility and kernel parts,...
.
Description
CFQ places synchronous requests submitted by processesProcess (computing)
In computing, a process is an instance of a computer program that is being executed. It contains the program code and its current activity. Depending on the operating system , a process may be made up of multiple threads of execution that execute instructions concurrently.A computer program is a...
into a number of per-process queues and then allocates timeslices for each of the queues to access the disk
Disk storage
Disk storage or disc storage is a general category of storage mechanisms, in which data are digitally recorded by various electronic, magnetic, optical, or mechanical methods on a surface layer deposited of one or more planar, round and rotating disks...
. The length of the time slice and the number of requests a queue is allowed to submit depends on the IO priority of the given process. Asynchronous requests for all processes are batched together in fewer queues, one per priority. While CFQ does not do explicit anticipatory
Anticipatory scheduling
Anticipatory scheduling is an algorithm for scheduling hard disk input/output. It seeks to increase the efficiency of disk utilization by "anticipating" synchronous read operations....
IO scheduling, it achieves the same effect of having good aggregate throughput for the system as a whole, by allowing a process queue to idle at the end of synchronous IO thereby "anticipating" further close IO from that process. It can be considered a natural extension of granting IO time slices to a process.
Prior to the integration
In February 2003 Andrea Arcangeli put forward his idea for a Stochastic Fair Queueing I/O scheduler to Jens Axboe who then implemented it. Jens Axboe made improvements to his first implementation, calling the new version the Completely Fair Queueing scheduler, and produced a patch to apply it to the 2.5.60 development series kernel.Kernel 2.6.6 (10 May 2004)
The CFQ I/O scheduler was first integrated into the mainline kernel as an optional I/O scheduler. It is possible to change the scheduler at boot time with the 'elevator' parameter to kernel.Kernel 2.6.9 (19 October 2004)
Red Hat Enterprise LinuxRed Hat Enterprise Linux
Red Hat Enterprise Linux is a Linux-based operating system developed by Red Hat and targeted toward the commercial market. Red Hat Enterprise Linux is released in server versions for x86, x86-64, Itanium, PowerPC and IBM System z, and desktop versions for x86 and x86-64...
4 used this I/O scheduler as the default even though it used a kernel based on a 2.6.9.
Kernel 2.6.10 (24 December 2004)
The second release of the CFQ scheduler dubbed CFQv2 is included in the 2.6.10, improvements include better responsiveness and the elimination of some starvation issues which were present in the earlier version. The scheduler now is also switchable at run time by modifying the /sys/block/Sysfs
Sysfs is a virtual file system provided by Linux 2.6. Sysfs exports information about devices and drivers from the kernel device model to user space, and is also used for configuration...
filesystem.
Kernel 2.6.13 (27 June 2005)
CFQ scheduler moved to a new time sliced design dubbed CFQv3. Among other things, it implements ioprio_get(2) and ioprio_set(2) which allows user to set per-process I/O priorities, usually using ionice(1) command (although using nice(1) also modifies I/O priorities somewhat)Kernel 2.6.18 (20 September 2006)
CFQ became the default scheduler, replacing the anticipatory schedulerAnticipatory scheduling
Anticipatory scheduling is an algorithm for scheduling hard disk input/output. It seeks to increase the efficiency of disk utilization by "anticipating" synchronous read operations....
.
Other I/O schedulers
- Noop schedulerNoop schedulerThe 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....
- Anticipatory schedulerAnticipatory schedulingAnticipatory scheduling is an algorithm for scheduling hard disk input/output. It seeks to increase the efficiency of disk utilization by "anticipating" synchronous read operations....
- Deadline schedulerDeadline schedulerDeadline scheduler is an I/O scheduler for the Linux kernel which was written in 2002 by Jens Axboe.- Overview :The goal of the Deadline scheduler is to guarantee a start service time for a request. It does that by imposing a deadline on all I/O operations to prevent starvation of requests. It also...