ROW scheduling Algorithm

The ROW scheduling algorithm will be used in mobile devices as default block layer IO scheduling algorithm. 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 lmdd read and write. The tests were performed on:
kernel version: 3.4
Underline device driver: mmc
Host controller: msm-sdcc
Card:standard emmc NAND flash

--------------------------------------------------------------------------

   Algorithm   |   Throughput [mb/sec]   |   Worst case Latency [msec]   |
               |     READ    |   WRITE   |     READ      |     WRITE     |
--------------------------------------------------------------------------
Noop           |    12.12    |   25.18   |     4407      |      4804     |
Deadline       |    12.02    |   24.6    |     705       |      5130     | 
CFQ	       |    20.81    |   15.23   |     230       |      9370     |
ROW	       |    27.75    |   15.34   |      85       |     12025     |

-------------------------------------------------------------------------|

Tatyana Brokhman (2):
block: Expose kblock_schedule_delayed_work()
block: Adding ROW scheduling algorithm

 Documentation/block/row-iosched.txt |  117 ++++++
 block/Kconfig.iosched               |   22 ++
 block/Makefile                      |    1 +
 block/row-iosched.c                 |  675 +++++++++++++++++++++++++++++++++++
 include/linux/blkdev.h              |    2 +
 5 files changed, 817 insertions(+), 0 deletions(-)
 create mode 100644 Documentation/block/row-iosched.txt
 create mode 100644 block/row-iosched.c

1.7.6
--
Sent by a consultant of the Qualcomm Innovation Center, Inc.
The Qualcomm Innovation Center, Inc. is a member of the Code Aurora Forum.

This function is exported in blk-core.c to be used in other modules but it's definition in h file is missing.

---
 include/linux/blkdev.h |    2 ++
 1 files changed, 2 insertions(+), 0 deletions(-)

index dc63297..ac0d069 100644
@@ -1208,6 +1208,8 @@ static inline void put_dev_sector(Sector p)
 
 struct work_struct;
 int kblockd_schedule_work(struct request_queue *q, struct work_struct *work);
+int kblockd_schedule_delayed_work(struct request_queue *q,
+			struct delayed_work *dwork, unsigned long delay);
 
 #ifdef CONFIG_BLK_CGROUP
 /*

1.7.6
--
Sent by a consultant of the Qualcomm Innovation Center, Inc.
The Qualcomm Innovation Center, Inc. is a member of the Code Aurora Forum.

This patch adds the implementation of a new scheduling algorithm - ROW. The policy of this algorithm is to prioritize READ requests over WRITE as much as possible without starving the WRITE requests.

---
 Documentation/block/row-iosched.txt |  117 ++++++
 block/Kconfig.iosched               |   22 ++
 block/Makefile                      |    1 +
 block/row-iosched.c                 |  675 +++++++++++++++++++++++++++++++++++
 4 files changed, 815 insertions(+), 0 deletions(-)
 create mode 100644 Documentation/block/row-iosched.txt
 create mode 100644 block/row-iosched.c

new file mode 100644
index 0000000..987bd88
@@ -0,0 +1,117 @@
+Introduction
+============
+
+The ROW scheduling algorithm will be used in mobile devices as default
+block layer IO scheduling algorithm. 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.
+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.
+
+Software description
+====================
+The requests are kept in queues according to their priority. The
+dispatching of requests is done in a Round Robin manner with a
+different slice for each queue. The dispatch quantum for a specific
+queue is defined according to the queues priority. READ queues are
+given bigger dispatch quantum than the WRITE queues, within a dispatch
+cycle.
+
+At the moment there are 6 types of queues the requests are
+distributed to:
+-	High priority READ queue
+-	High priority Synchronous WRITE queue
+-	Regular priority READ queue
+-	Regular priority Synchronous WRITE queue
+-	Regular priority WRITE queue
+-	Low priority READ queue
+
+If in a certain dispatch cycle one of the queues was empty and didn't
+use its quantum that queue will be marked as "un-served". If we're in a
+middle of a dispatch cycle dispatching from queue Y and a request
+arrives for queue X that was un-served in the previous cycle, if X's
+priority is higher than Y's, queue X will be preempted in the favor of
+queue Y. This won't mean that cycle is restarted. The "dispatched"
+counter of queue X will remain unchanged. Once queue Y uses up it's quantum
+(or there will be no more requests left on it) we'll switch back to queue X
+and allow it to finish it's quantum.
+
+For READ requests queues we allow idling in within a dispatch quantum in
+order to give the application a chance to insert more requests. Idling
+means adding some extra time for serving a certain queue even if the
+queue is empty. The idling is enabled if we identify the application is
+inserting requests in a high frequency.
+
+For idling on READ queues we use timer mechanism. When the timer expires,
+if there are requests in the scheduler we will signal the underlying driver
+(for example the MMC driver) to fetch another request for dispatch.
+
+The ROW algorithm takes the scheduling policy one step further, making
+it a bit more "user-needs oriented", by allowing the application to
+hint on the urgency of its requests. For example: even among the READ
+requests several requests may be more urgent for completion then others.
+The former will go to the High priority READ queue, that is given the
+bigger dispatch quantum than any other queue.
+
+ROW scheduler will support special services for block devices that
+supports High Priority Requests. That is, the scheduler may inform the
+device upon urgent requests using new callback make_urgent_request.
+In addition it will support rescheduling of requests that were
+interrupted. For example, if the device issues a long write request and
+a sudden high priority read interrupt pops in, the scheduler will
+inform the device about the urgent request, so the device can stop the
+current write request and serve the high priority read request. In such
+a case the device may also send back to the scheduler the reminder of
+the interrupted write request, such that the scheduler may continue
+sending high priority requests without the need to interrupt the
+ongoing write again and again. The write remainder will be sent later on
+according to the scheduler policy.
+
+Design
+======
+Existing algorithms (cfq, deadline) sort the io requests according LBA.
+When deciding on the next request to dispatch they choose the closest
+request to the current disk head position (from handling last
+dispatched request). This is done in order to reduce the disk head
+movement to a minimum.
+We feel that this functionality isn't really needed in mobile devices.
+Usually applications that write/read large chunks of data insert the
+requests in already sorted LBA order. Thus dealing with sort trees adds
+unnecessary complexity.
+
+We're planing to try this enhancement in the future to check if the
+performance is influenced by it.
+
+SMP/multi-core
+==============
+At the moment the code is acceded from 2 contexts:
+- Application context (from block/elevator layer): adding the requests.
+- Underlying driver context (for example the mmc driver thread): dispatching
+  the requests and notifying on completion.
+
+One lock is used to synchronize between the two. This lock is provided
+by the underlying driver along with the dispatch queue.
+
+Config options
+==============
+1. hp_read_quantum: dispatch quantum for the high priority READ queue
+2. rp_read_quantum: dispatch quantum for the regular priority READ queue
+3. hp_swrite_quantum: dispatch quantum for the high priority Synchronous
+   WRITE queue
+4. rp_swrite_quantum: dispatch quantum for the regular priority
+   Synchronous WRITE queue
+5. rp_write_quantum: dispatch quantum for the regular priority WRITE
+   queue
+6. lp_read_quantum: dispatch quantum for the low priority READ queue
+7. lp_swrite_quantum: dispatch quantum for the low priority Synchronous
+   WRITE queue
+8. read_idle: how long to idle on read queue in Msec (in case idling
+   is enabled on that queue).
+9. read_idle_freq: frequency of inserting READ requests that will
+   trigger idling. This is the time in Msec between inserting two READ
+   requests
+

index 421bef9..401f42d 100644
@@ -21,6 +21,17 @@ config IOSCHED_DEADLINE
 	  a new point in the service tree and doing a batch of IO from there
 	  in case of expiry.
 
+config IOSCHED_ROW
+	tristate "ROW I/O scheduler"
+	default y
+	---help---
+	  The ROW I/O scheduler gives priority to READ requests over the
+	  WRITE requests when dispatching, without starving WRITE requests.
+	  Requests are kept in priority queues. Dispatching is done in a RR
+	  manner when the dispatch quantum for each queue is calculated
+	  according to queue priority.
+	  Most suitable for mobile devices.
+
 config IOSCHED_CFQ
 	tristate "CFQ I/O scheduler"
 	default y

@@ -49,6 +60,16 @@ choice
 	config DEFAULT_DEADLINE
 		bool "Deadline" if IOSCHED_DEADLINE=y
 
+	config DEFAULT_ROW
+		bool "ROW" if IOSCHED_ROW=y
+		help
+		  The ROW I/O scheduler gives priority to READ requests
+		  over the WRITE requests when dispatching, without starving
+		  WRITE requests. Requests are kept in priority queues.
+		  Dispatching is done in a RR manner when the dispatch quantum
+		  for each queue is defined according to queue priority.
+		  Most suitable for mobile devices.
+
 	config DEFAULT_CFQ
 		bool "CFQ" if IOSCHED_CFQ=y
 

@@ -60,6 +81,7 @@ endchoice
 config DEFAULT_IOSCHED
 	string
 	default "deadline" if DEFAULT_DEADLINE
+	default "row" if DEFAULT_ROW
 	default "cfq" if DEFAULT_CFQ
 	default "noop" if DEFAULT_NOOP
 

index 39b76ba..dd80dc2 100644
@@ -14,6 +14,7 @@ obj-$(CONFIG_BLK_CGROUP)	+= blk-cgroup.o
 obj-$(CONFIG_BLK_DEV_THROTTLING)	+= blk-throttle.o
 obj-$(CONFIG_IOSCHED_NOOP)	+= noop-iosched.o
 obj-$(CONFIG_IOSCHED_DEADLINE)	+= deadline-iosched.o
+obj-$(CONFIG_IOSCHED_ROW)	+= row-iosched.o
 obj-$(CONFIG_IOSCHED_CFQ)	+= cfq-iosched.o
 
 obj-$(CONFIG_BLOCK_COMPAT)	+= compat_ioctl.o

1.7.6
--
Sent by a consultant of the Qualcomm Innovation Center, Inc.
The Qualcomm Innovation Center, Inc. is a member of the Code Aurora Forum.

Perhaps you could start off by describing the workload, and describing why the existing I/O schedulers do not perform well. Then, you could go on to say why you feel that the existing I/O schedulers could not be modified to perform better under your workload, and wrap the whole thing up with some convincing performance numbers (including your testing procedures so others could verify your work independently).

Without the above, I think you'll have a difficult time getting yet another I/O scheduler merged into the kernel.

Cheers,
Jeff

Hi Jeff

First of all - thank you for your input! I think I did address at least some of the issues you mentioned. But allow me to elaborate

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.
The existing I/O schedulers add unnecessary complexity (CFQ) or don't give read requests as much priority over write as we would like them to get.

We ran tests with existing I/O schedulers and tried tuning them to serve our purposes better but it didn't give us the results we were able to achieve with ROW.

Aren't the test results I published convincing? It shows that ROW has the best READ throughput and the lowest READ latency. Actually, when playing with ROW tunable the READ throughput can go up to 34 mb/sec and READ latency down to 70 msec (with WRITE throughput at ~15 mb/sec). The downside is that in such configuration the write latency is ~13 sec which is a bit too much.

I was testing on our Android based device. I don't know what numbers will ROW produce if you run it on a PC because as I mentioned, ROW was developed to run on mobile devices.
As I mentioned, the test I performed was parallel READ and WRITE using lmdd. I'm not sure I understand what info is missing in order for others to reproduce it...

Thanks,
Tanya Brokhman
---
Sent by an consultant of the Qualcomm Innovation Center, Inc. The Qualcomm Innovation Center, Inc. is a member of the Code Aurora Forum.

My setup is a 1 GB RAM Atom N450 netbook, combined with the use of dm-crypt for the 5400 rpm disk, which limits the effective write throughput to somewhere around 20–26 MB/s. Now try this:

ddrescue /dev/zero ~/bluntfile (or)

(remote)# >nullfile
(remote)# truncate -s 10G nullfile
(local)# rsync -HPavz remote:nullfile .

The transfer rates of ddrescue/rsync first show 50–60 MB/s. Wait until writeout is forced - which is after ~700–800 MB in my case when all buffers are full. The transfer rates then drop to the aforementioned 20–26 MB/s.

In the so-loaded system, try to start an xterm (preferably by the use of a shortcut, or starting one from another xterm). The wait time for the shell prompt to appear is then the measure for interactivity, with lower being better.

I have casually observed that ROW has 1/4th of the wait time in this heavy disk write scenario (around 5 s) for the shell to start up than with CFQ (20–21 s). "Casual" meaning I had a clock with 1.0 s granularity beside me and ran this for like 3 times for each scheduler, averaging it out.

There seems to a bug with ROW. After about 43 hours of continued operation, programs (./configure was what I ran at the time this happened) first become slow, then got stuck in D state within a minute. Ctrl-C/Z worked at first, soon not, then these messages appeared in dmesg.

[319952.630605] row: forced dispatching is broken (nr_sorted=17), please report
this
[319952.631174] row: forced dispatching is broken (nr_sorted=17), please report

this

Hi Jan

Ctrl-

(nr_sorted=17),

Thank you very much for reporting this!
We're now at the testing phase as well. We didn't encounter the bug you observed but I'll look into it. Thanks again.

Thanks,
Tanya Brokhman
---
QUALCOMM ISRAEL, on behalf of Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by The Linux Foundation

Hi

I tested with this patch on my board.
But i didn't get any performance benefit.
Which benchmark did you use?
And sometime this scheduler didn't work well read/write operation. (i didn't know exactly what problem.)

The below is my environment:
Kernel Version: linux-3.4
Card: eMMC4.5 (50MHz DDR mode, 8-bit buswidth) Host controller : dw-mmc (DesignWare MMC controller) Benchmark : IOzone

*CFQ Scheduler
Read : 35MB
Write : 17MB

*ROW Scheduler
Read : 28MB
Write : 17MB

How do you think about this result?

Best Regards,
Jaehoon Chung

Hi Chung

As I already mentioned I used lmdd. The results I published were collected using the bellow command run in parallel:
adb shell /data/lmdd if=internal of=/data/writefile bs=128k count=3000
adb shell /data/lmdd if=/data/readfile of=internal bs=128k count=3000

With lmdd we did see great improvement both in throughput and in read latency:
CFQ: READ 20.81 MB/sec, WRITE 15.23 MB/sec Worst case READ latency 230 msec Worst case write latency 9370 msec
ROW: READ 27.75 MB/sec WRITE 15.34 MB/sec Worst case READ latency 85 msec Worst case write latency 12025 msec

ROW can be configured to perform at ~34 MB/sec throughput in the above scenario but in this configuration worst case write latency increases to ~13 sec.

This may be. We're still working on testing the scheduler and improving it. It's not yet totally "bug free". I've uploaded the code as RFC.

My environment is similar except the host controller which is msm-sdcc. Could you please give me the exact iozone command you used? I'll replay it on my setup.

Thanks,
Tanya Brokhman
---
Sent by an consultant of the Qualcomm Innovation Center, Inc. The Qualcomm Innovation Center, Inc. is a member of the Code Aurora Forum.

I will try to test with lmdd.

iozone -A -s 200m -U /data/ -f /data/test -e and iozone -A -s 200m -f /data/test -e -I

Best Regards,
Jaehoon Chung

Hi Chung

I run your cmd of iozone on my setup and got a bit different results:
CFQ scheduler:

          204800   16384   27903   27248    40345    40399

READ: 40 MB/sec WRITE: 27 MB/sec

ROW scheduler:
READ: 39.6 MB/sec WRITE: 27MB/sec

As you can see the results are the same for both schedulers.
Anyway, the improvement added by ROW is in scenario of parallel read and write, which iozone doesn't do so running iozone for comparing ROW to CFQ is useless. If it's not too difficult I would appreciate if you could run the bellow 2 commands simultaneously on your setup:
adb shell /data/lmdd if=internal of=/data/writefile bs=128k count=3000
adb shell /data/lmdd if=/data/readfile of=internal bs=128k count=3000
You'll see an improvement in throughput when using ROW over CFQ.
We have a patch that also measures latency and we saw that read latency was also improved greatly when using ROW.

Thanks,
Tanya Brokhman
---
Sent by an consultant of the Qualcomm Innovation Center, Inc. The Qualcomm Innovation Center, Inc. is a member of the Code Aurora Forum.

Hi,

i will try the test with your comment. and will share the result. Thanks for reply.

Best Regards,
Jaehoon Chung

2012/8/9 Tanya Brokhman <[email protected]>:

On Thursday, August 09, 2012 2:06 PM, Tanya Brokhman <[email protected]> wrote:
Thank you for interesting patch.
Here is other test result.

* Test environment
kernel version: 3.4
Underline device driver: mmc
Host controller: dw_mmc
Card:standard emmc NAND flash

* lmdd with parallel read and write
/data/lmdd if=internal of=/data/writefile bs=128k count=3000 /data/lmdd if=/data/readfile of=internal bs=128k count=3000
READ WRITE
CFQ 37MB 23MB
ROW 41MB 23MB

* iozone with parallel read and write /data/iozone -i0 -r4096k -s200m -I -e -w -f/data/write /data/iozone -i1 -r4096k -s200m -I -e -f/data/read
READ WRITE
CFQ 23MB 24MB
ROW 40MB 17MB

Results show that read throughput of ROW is better than CFQ. However, write throughput is degraded in case of IOZONE test. Depending on user scenario, write can be considered to be important. It needs to check the starvation of write.

Thanks,
Seungwon Jeon