So what is the best scheduler algorithm? In fact there is no such thing as a "best" one. Instead, there are a number of different schedulers, each one suited to different types of servers. The four principal schedulers common to most Linux systems are:
This is the simplest scheduler, and it does nothing beyond merging requests and placing them in a queue to be processed in the order they arrive at the head of the queue.
The noop scheduler is useful in a system which uses a modern RAID controller which can schedule I/O better than the operating system. It is also useful on systems with solid state drives (including RAM disks,) which have a fixed seek time for all data, regardless of where it is stored on the device.
The deadline scheduler is designed to overcome the problem of a read request for a remote part of a disk getting serviced too slowly because it is constantly shunted to the back of the queue by requests arriving for closer parts of the disk. This is analogous to trying to get to the top floor of a building in an elevator that keeps stopping to let people on and off at intermediate floors. To overcome this, each request is given a waiting time or "deadline." If the request is not serviced before the deadline expires, it is then put to the front of the queue, merged with any requests for nearby disk locations and serviced immediately.
The deadline scheduler is useful for real-time applications because in most cases it keeps latency low since all requests are serviced within a relatively short time frame dictated by the deadline.
The anticipatory scheduler works by anticipating that the next request will be for the disk block that follows the one that has just been serviced. After carrying out a read or write, the scheduler enforces a slight delay to give an application time to submit a request for the next disk block. If such a request arrives (as anticipated), the disk head will be in the right place to service the request, instead of having moved away to service another request.
Using the elevator analogy, imagine a situation where an office block is host to a number of companies, each of which occupies, say, two floors. If an office worker gets on at a given floor, it's a good bet she will want to get off at the next floor, which also belongs to her company. So it is sensible for the elevator to wait until the office worker has pressed the button for the floor she wants before it shoots past the next floor.
These slight delays add up to a small amount of latency added to the system, but in some circumstances this can easily be outweighed by the efficiency gained from having the head anticipate where it next has to go.
The anticipatory scheduler is suited to tasks that don't get regularly interrupted by external requests. It tends to be useful for web servers and workstations that often access data in a linear fashion, but not for database servers that access data in a more random fashion.
cfq stands for "completely fair queuing." In this system the scheduler maintains a number of internal request queues, and each process running on the system is assigned to one of these queues. The schedule then takes the requests from the front of each queue and places them into a dispatch queue, where they are ordered to minimize seek time and serviced. The scheduler then goes back to the internal request queues and brings more requests from the front of these queues to refill the dispatch queue.
This is analogous to a building with a single elevator, with separate queues for each company that has offices in the building. Each time the lift arrives in the lobby it takes staff from the front of the queue for each company, so no individual company can hog the elevator excessively. Cfq works well for medium and large multi-processor systems, and is the default scheduler for Linux distros such as Red Hat Enterprise Linux.