Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

I/O Scheduling in Linux

DZone's Guide to

I/O Scheduling in Linux

Learn the different types of I/O schedulers in Linux, like Noop, CFQ, and BFQ, and learn how they can help you reach high performance.

Free Resource

Download our Introduction to API Performance Testing and learn why testing your API is just as important as testing your website, and how to start today.

First and foremost, let's recall what scheduling in the operating system is. We can distinguish two types of schedulers in operating systems: process scheduler and I/O scheduler. We are interested in the latter. I/O scheduler is a layer between block devices and low-level drivers. It's intended to provide optimal process access to the disk device. Despite the apparent simplicity of the scheduler's work, this simplicity is dispelled due to the facts that working with disks is a very slow operation and that the search for the necessary sectors on the disk does not happen quickly. At the same time, the processes are waiting for their turn to access the disk. I/O scheduler should be able to give information as per the priorities and ensure that data is received by the application within a certain amount of time.

In earlier versions of Linux, there was only one I/O scheduler: Linus Elevator. It was too primitive, and therefore in the 2.6 kernel, there appeared to be three more schedulers. Let's consider schedulers in detail.

Noop

Noop is the simplest scheduler. It trivially places all requests in the FIFO queue and executes them. Note that this happens for all processes that exist in the system, regardless of the type of I/O requests. Also, noop is capable of merging a few requests. Read/write requests of a similar purpose are combined to reduce the number of disk operations and increase the length of system calls.

CFQ

CFQ appeared as an extension to the network scheduler SFQ (stochastic fair queuing). CFQ differs from Noop in that it has the individual queue for every single process. The scheduler serves each process in a loop while the queue is not empty or the specified time quantum doesn't expire ( the last condition is similar to the process scheduler). In the scope of each queue, the read operation has higher priority over writing. 

Deadline

Deadline is the standard scheduler. As is obvious from its name, Deadline tries to execute the request at the specified time. Deadline supports two special deadline queues (sorted by the expiration time) and two sorted queues for read and write operations (sorted by the sector number). Deadline queues are aimed at preventing the starvation of requests. Deadline serves requests in batches. Batches are the sequences of I/O operations that are in increasing LBA order. Read operations have higher priority over write operations, like in CFQ, because processes usually block on read operations. So, the read operation has an expiration time of 500 ms, while write has 5 seconds. Before next request, Deadline must choose a queue for usage (read or write). This algorithm is more suitable for systems where there are many read operations, like databases and web servers.

BFQ

BFQ (Budget Fair Queueing) is a proportional share disk scheduling algorithm based on CFQ. BFQ converts Round Robin scheduling algorithms based on time intervals so that it focuses on the number of disk sectors. Each task has a dedicated sector budget, which may vary depending on the behavior of the task. BFQ ensures that disk traffic will be distributed more honestly between tasks, and reduces the complexity of querying disk data to O (1).

Anticipatory I/O Scheduler

Anticipatory I/O scheduler tries to guess to which blocks of the disk the following requests will be executed and attempts to aggregate and/or re-order requests improving locality and reducing disk seek operations. This algorithm makes preparation for the next read operation when the current read operation appears to be finished.

Scheduling algorithms that are effective on read operations (like Deadline or Anticipatory) can bring a performance boost to web server or database. You can sufficiently speed up your Apache web server with tuning scheduler parameters.

You can check the list of available schedulers via this command (the current scheduler is allocated in square brackets):

$ cat /sys/block/sda/queue/scheduler

The output on my Linux machine is noop [deadline] cfq .

There a lot of nice tools that allow comparing the performance of scheduling algorithms. I use hdparm for the writing benchmarks. hdparm contains default benchmarks (but you can use your own). The usage of hdparm is:

$ apt-get install hdparm
$ hdparm -tT /dev/sda

For comparing the performance of algorithms, we must change the scheduler from default to arbitrary. You can use the next command for this action:

$ echo {SCHEDULER_NAME} > /sys/block/sda/queue/scheduler

hdparm provides timing cached reads and timing buffered disk reads. Of course, you can use other approaches for testing like the dd command or bonnie++.

Find scaling and performance issues before your customers do with our Introduction to High-Capacity Load Testing guide.

Topics:
linux

Opinions expressed by DZone contributors are their own.

THE DZONE NEWSLETTER

Dev Resources & Solutions Straight to Your Inbox

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.

X

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}