[LG Optimus Black] knzo:
Due to popular demand, it's now time for a thread like this.

Post #1 - Governors

Post #2 - I/O Schedulers

#2 - I/O Schedulers

So, what's a I/O Scheduler?

Input/output (I/O) 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. I/O Scheduling is sometimes called 'disk scheduling'.

I/O schedulers can have many purposes depending on the goal of the I/O
scheduler, some common goals are:

- To minimize time wasted by hard disk 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.

There is not so much offer when it comes to I/O Schedulers and the improvements aren't nearly as visible as choosing a gung ho governor but trust me they are there. Just to name one improvement you could see is for example the opening and closing of applications.

Listing of knzo-known I/O Schedulers:

Noop *

Anticipatory *@+

CFQ *&

Deadline *@+

VR +

Simple +&

BFQ #

Legend

: & - default | @ - disabled by default | * - exists in stock kernel | + - added in Quasar kernel | # - not included in Quasar kernel

And now a summary for each and brief comment by myself:

Noop:

The NOOP scheduler inserts all incoming I/O requests into a simple, unordered
FIFO queue and implements request merging.

The scheduler assumes I/O performance optimization will be handled at some
other layer of the I/O hierarchy; e.g., at the block device; by an intelligent HBA
such as a Serial Attached SCSI (SAS) RAID controller or by an externally
attached controller such as a storage subsystem accessed through a switched
Storage Area Network).

NOOP scheduler is best used with solid state devices such as flash memory
or in general with devices that do not depend on mechanical movement to
access data (meaning typical "hard disk" drive technology consisting of seek
time primarily, plus rotational latency). Such non-mechanical devices do not
require re-ordering of multiple I/O requests, a technique that groups together
I/O requests that are physically close together on the disk, thereby reducing
average seek time and the variability of I/O service time.

Noop isn't actually that bad. It's a simple I/O Scheduler and when it comes to Android, the simplest the better.

I think in G1 one known "tweak" was to set Noop as default I/O Scheduler.

Anticipatory:

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.

"Deceptive idleness" is a situation where a process appears to be finished
reading from the disk when it is actually processing data in preparation of
the next read operation. This will cause a normal work-conserving I/O
scheduler to switch to servicing I/O from an unrelated process. This situation
is detrimental to the throughput of synchronous reads, as it degenerates into
a seeking workload. Anticipatory scheduling overcomes deceptive idleness
by pausing for a short time (a few milliseconds) after a read operation in
anticipation of another close-by read requests.

I have no idea if this fares well in Android devices. It's disabled in stock kernel and also in Quasar kernel since I've never heard of anyone using it or even recommending it. I read it's more in servers and what nots.

CFQ:

CFQ, also known as "Completely Fair Queuing", is an I/O scheduler for the
Linux kernel which was written in 2003 by Jens Axboe.

CFQ works by placing synchronous requests submitted by processes into
a number of per-process queues and then allocating 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.

Well, like Ondemand is to governors, CFQ is to I/O Schedulers. It's the most balanced one, aiming to perform well in most scenarios. However, in Android since things work differently, it's not the most suitable I/O Schedulers. There are many tweaks spreaded throughout XDA for improving this baby.

Deadline:

The goal of the Deadline scheduler is to attempt 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 maintains two deadline queues, in
addition to the sorted queues (both read and write). Deadline queues are basically
sorted by their deadline (the expiration time), while the sorted queues are sorted
by the sector number.

Before serving the next request, the Deadline scheduler decides which queue to
use. Read queues are given a higher priority, because processes usually block
on read operations. Next, the Deadline scheduler checks if the first request in the
deadline queue has expired. Otherwise, the scheduler serves a batch of requests
from the sorted queue. In both cases, the scheduler also serves a batch of requests
following the chosen request in the sorted queue.

Deadline is actually quite popular along with BFQ. It is used in some known kernels for example Netarchy's for Nexus S. However, even though it's better than CFQ for Android devices it still falls short in comparison with VR.

VR:

/*
* V(R) I/O Scheduler
*
* Copyright (C) 2007 Aaron Carroll <aaronc@gelato.unsw.edu.au>
*
*
* The algorithm:
*
* The next request is decided based on its distance from the last
* request, with a multiplicative penalty of `rev_penalty' applied
* for reversing the head direction. A rev_penalty of 1 means SSTF
* behaviour. As this variable is increased, the algorithm approaches
* pure SCAN. Setting rev_penalty to 0 forces SCAN.
*
* Async and synch requests are not treated seperately. Instead we
* rely on deadlines to ensure fairness.
*
*/

VR is a very good I/O Scheduler with Deadline elements. Probably the best for MTD Android devices and it's used also in known kernels such as IntersectRaven's for Nexus One. It's probably the one who can score the most in benchmarks but it's also one of the most... unstable. Its performance fluctuates, it can peak above average or it can go below it. But when it peaks... it's the best.

Simple:

/*
* Simple IO scheduler
* Based on Noop, Deadline and V(R) IO schedulers.
*
* Copyright (C) 2010 Miguel Boton <mboton@gmail.com>
*
*
* This algorithm does not do any kind of sorting, as it is aimed for
* aleatory access devices, but it does some basic merging. We try to
* keep minimum overhead to achieve low latency.
*
* Asynchronous and synchronous requests are not treated separately, but
* we relay on deadlines to ensure fairness.
*
*/

Like the name suggests, Simple I/O is a simple one. Remember me saying that I/O Schedulers for Android devices, the simpler the better? This is such a case. Especially for EMMC devices. It's reliable and while not as good as VR when it peaks, it's still one of the best performance-wise. It's at the moment the default one in Quasar kernel.

BFQ:

/*
* BFQ, or Budget Fair Queueing, disk scheduler.
*
* Based on ideas and code from CFQ:
* Copyright (C) 2003 Jens Axboe <axboe@kernel.dk>
*
* Copyright (C) 2008 Fabio Checconi <fabio@gandalf.sssup.it>
*	Paolo Valente <paolo.valente@unimore.it>
*
* Licensed under the GPL-2 as detailed in the accompanying COPYING.BFQ file.
*
* BFQ is a proportional share disk scheduling algorithm based on the
* slice-by-slice service scheme of CFQ. But BFQ assigns budgets,
* measured in number of sectors, to tasks instead of time slices.
* The disk is not granted to the active task for a given time slice,
* but until it has exahusted its assigned budget. This change from
* the time to the service domain allows BFQ to distribute the disk
* bandwidth among tasks as desired, without any distortion due to
* ZBR, workload fluctuations or other factors. BFQ uses an ad hoc
* internal scheduler, called B-WF2Q+, to schedule tasks according to
* their budgets. Thanks to this accurate scheduler, BFQ can afford
* to assign high budgets to disk-bound non-seeky tasks (to boost the
* throughput), and yet guarantee low latencies to interactive and
* soft real-time applications.
*
*/

Here it is, the wrongly assumed best I/O Scheduler which happens to be the most popular one. It's based in CFQ but it has an inferior performance than VR or Simple, even if it's BFQv2 (although it seems to perform well in USB transfers rate).

To sum up:

(in my humble opinion)

Performance

: 1st place - VR

Reliability

: 1st place - Simple