Attend XDA's Second Annual Developer Conference, XDA:DevCon 2014!
5,740,156 Members 40,339 Now Online
XDA Developers Android and Mobile Development Forum

Information about I/O Schedulers

Tip us?
 
dheeraj (dhlalit11)
Old
(Last edited by dheeraj (dhlalit11); 15th February 2013 at 04:10 PM.) Reason: added ROW Scheduler
#1  
dheeraj (dhlalit11)'s Avatar
Recognized Contributor - OP
Thanks Meter 1439
Posts: 2,440
Join Date: Sep 2011
Location: fatehabad (hry)
Lightbulb Information about I/O Schedulers

What is I/O Scheduler

Quote:
I/O:- short form of Input & Output

Quote:
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.

Info on I/O Scheduler

Quote:
ROW:- ROW stands for "READ Over WRITE"which is the main requests dispatch policy of this algorithm. The ROW IO scheduler was developed with the mobile devices needs in mind. In mobile devices we favor user experience upon everything else,thus we want to give READ IO requests as much priority as possible. In mobile devices we won¡¯t have as much parallel threads as on desktops. Usually it¡¯s a single thread or at most 2 simultaneous working threads for read & write. Favoring READ requests over WRITEs decreases the READ latency greatly.

The main idea of the ROW scheduling policy is: If there are READ requests in pipe - dispatch them but don't starve the WRITE requests too much. Bellow you¡¯ll find a small comparison of ROW to existing schedulers. The test that was run for these measurements is parallel read and write.
Quote:
FIOS:- Flash-based solid-state drives (SSDs) have the potential to eliminate the I/O bottlenecks in data-intensive applications However the large performance discrepancy between Flash reads and writes introduces challenges for fair resource usage. Further, existing fair queueing and quanta-based I/O schedulers poorly manage the I/O anticipation for Flash I/O fairness and efficiency. Some also suppress the I/O parallelism which causes substantial performance degradation on Flash. This paper develops FIOS, a new Flash I/O scheduler that attains fairness and high efficiency at the same time. FIOS employs a fair I/O timeslice management with mechanisms for read preference, parallelism, and fairness-oriented I/O anticipation. Evaluation demonstrates that FIOS achieves substantially better fairnessand efficiency compared to the Linux CFQ scheduler, the SFQ(D) fair queueing scheduler, and the Argon quanta-based scheduler on several Flash-based storage devices (including a CompactFlash card in a low-power wimpy node). In particular, FIOS reduces the worst-case slowdown bya factor of 2.3 or more when the read-only SPECweb workload runs together with the write-intensive TPC-C.
Quote:
SIO:- scheduler is based on the deadline scheduler but it's more like a mix between no-op and deadline.In other words, SIO is like a lighter version of deadline but it doesn't do any kind of sorting, so it's aimed mainly for random-access devices (like SSD hard disks) where request sorting is no needed (as any sector can be accesed in a constant time, regardless of its physical location).
Quote:
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.

Quote:
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.

Quote:
ADAPTIVE ANTICIPATORY SCHEDULER:- For the anticipatory scheduler, we scale up the anticipation timeout (antic expire) using the latency scaling factor over time. When the virtual disk latencies are low a small scaling of the timeout is sucient to prevent deceptive idleness, whereas when the latencies are high a larger scaling of the timeout value may be required to achieve the same. Note that such dynamic setting of the timeout value ensures that we attain a good trade-o between throughput (lost due to idling) and deceptive idleness mitigation. Setting a high value for the scaling factor (increasing idling time) only happens when the disk service latencies themselves are higher. This may not necessarily cause a signicant loss in throughput, because submitting a request from another process instead of idling is not going to improve throughput if the virtual disk itself does not get any faster than it is at the current period. A higher anticipation timeout might also be capable of absorbing process scheduling eects inside the VM. The results for the adaptive anticipatory scheduler are shown in Figure 2. The read time with our modied implementation (third bar in the dierent scheduler combi- nations) shows that it is possible to mitigate the eects of deceptive idleness by adapting the timeout. An interesting related observation is that the level to which the improve- ment is possible varies for dierent Domain-0 schedulers; noop - 39%, anticipatory - 67% and cfq - 36%. This again points to the fact that the I/O scheduler used in Domain-0 is important for the VM's ability in enforcing I/O scheduling guarantees. Dierent Domain-0 I/O schedulers likely have a dierent service latency footprint inside the VMs, contributing to dierent levels of improvement.

Quote:
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.

Quote:
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.

Quote:
V(R):- 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.

Quote:
SIMPLE:- Does not do any kind of sorting, as it is aimed foraleatory access devices, but it does some basic merging. We try to keep minimum overhead to achieve low latency.
Quote:
BFQ:- 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-timeapplications.
The Following 160 Users Say Thank You to dheeraj (dhlalit11) For This Useful Post: [ Click to Expand ]
 
dheeraj (dhlalit11)
Old
(Last edited by dheeraj (dhlalit11); 15th February 2013 at 04:11 PM.)
#2  
dheeraj (dhlalit11)'s Avatar
Recognized Contributor - OP
Thanks Meter 1439
Posts: 2,440
Join Date: Sep 2011
Location: fatehabad (hry)
added ROW scheduler

added Fios scheduler

added sio scheduler
The Following 5 Users Say Thank You to dheeraj (dhlalit11) For This Useful Post: [ Click to Expand ]
 
Svennen
Old
#3  
Svennen's Avatar
Senior Member
Thanks Meter 75
Posts: 156
Join Date: Jan 2012
So, witch should I choose?
 
dheeraj (dhlalit11)
Old
#4  
dheeraj (dhlalit11)'s Avatar
Recognized Contributor - OP
Thanks Meter 1439
Posts: 2,440
Join Date: Sep 2011
Location: fatehabad (hry)
Quote:
Originally Posted by Svennen View Post
So, witch should I choose?
if you have vr then it is good for performance
The Following User Says Thank You to dheeraj (dhlalit11) For This Useful Post: [ Click to Expand ]
 
dheeraj (dhlalit11)
Old
#5  
dheeraj (dhlalit11)'s Avatar
Recognized Contributor - OP
Thanks Meter 1439
Posts: 2,440
Join Date: Sep 2011
Location: fatehabad (hry)
guys if you know about any other scheduler then write it here and i will add the info
The Following 2 Users Say Thank You to dheeraj (dhlalit11) For This Useful Post: [ Click to Expand ]
 
Caliyork
Old
#6  
Caliyork's Avatar
Senior Member
Thanks Meter 64
Posts: 419
Join Date: Dec 2011
Location: Riverside, CA
Awesome, thanks for the info! So if I've got the choice between bfq, cfq, noop, anticipatory, and deadline, which do you think is best for performance. My (un)educated guess would be anticipatory.
 
Doc_cheilvenerdi.org
Old
#7  
Doc_cheilvenerdi.org's Avatar
Senior Member
Thanks Meter 344
Posts: 123
Join Date: Oct 2011
Location: Ferrara - Ravenna
Quote:
Originally Posted by Caliyork View Post
...So if I've got the choice between bfq, cfq, noop, anticipatory, and deadline, which do you think is best for performance. My (un)educated guess would be anticipatory.
Here is my experience (no benchmarks but my own feelings) comparing CFQ and deadline (Samsung Base Kernel options I get are only these ones plus noop) while using a lightly tweaked 2.3.4 Stock firmware with /data and /system both on SD card 8Gb class 4 (just to heavy fill I/O queue...) and actually the smoother config (I repeat: own feelings...) I figured out is:
- CFQ
- read_ahead_kb = 1024


Sent from my GT-S5570 on Train
The Following User Says Thank You to Doc_cheilvenerdi.org For This Useful Post: [ Click to Expand ]
 
dheeraj (dhlalit11)
Old
#8  
dheeraj (dhlalit11)'s Avatar
Recognized Contributor - OP
Thanks Meter 1439
Posts: 2,440
Join Date: Sep 2011
Location: fatehabad (hry)
Quote:
Originally Posted by Doc_cheilvenerdi.org View Post
Here is my experience (no benchmarks but my own feelings) comparing CFQ and deadline (Samsung Base Kernel options I get are only these ones plus noop) while using a lightly tweaked 2.3.4 Stock firmware with /data and /system both on SD card 8Gb class 4 (just to heavy fill I/O queue...) and actually the smoother config (I repeat: own feelings...) I figured out is:
- CFQ
- read_ahead_kb = 1024


Sent from my GT-S5570 on Train
I also think of anticipatory as it increase the efficiency of disk utilization.
 
Svennen
Old
#9  
Svennen's Avatar
Senior Member
Thanks Meter 75
Posts: 156
Join Date: Jan 2012
Quote:
Originally Posted by dhlalit11 View Post
I also think of anticipatory as it increase the efficiency of disk utilization.
What kernel are you using to get that?
 
LeQuazz
Old
(Last edited by LeQuazz; 24th March 2012 at 03:51 AM.)
#10  
Senior Member
Thanks Meter 25
Posts: 113
Join Date: Feb 2012
Hi, emanom v5 rom has sio IO scheduler in it. Do you know what that does exactly? It's default so I'm assuming it's good.

I found this on another dev forum about sio

"SIO:

SIO Scheduler is based on the deadline scheduler but it's more like a mix between no-op and deadline.
In other words, SIO is like a lighter version of deadline but it doesn't do any kind of sorting, so it's aimed mainly for random-access devices (like SSD hard disks) where request sorting is no needed (as any sector can be accesed in a constant time, regardless of its physical location). "

The Following 2 Users Say Thank You to LeQuazz For This Useful Post: [ Click to Expand ]
Tags
android, i/o scheduler, info, kernel, xda
Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes