SFQ disk scheduler

Hi,

Here's a simple stochastic fairness queueing disk scheduler, for current 2.5.59-BK. It has known limitations right now, mainly because I didn't bother making it complete. But it should suffice for some rudimentary testing, at least.

I'm not going to go into great detail about how it works, see Andrea's initial post of the paper referenced. This version may not be completely true to the SFQ concept, but should be close enough I think. It divides traffic into a fixed number of buckets (64 per default), and perturbs the hash every 5 seconds (hash shamelessly borrowed from networking atm, see comment).

To avoid too many disk seeks, when it's time to dispatch requests to the driver, we round robin all non-empty buckets and grab a single request from each. These requests are sorted into the dispatch queue.

For performance reasons, io scheduler request merging is still a per-queue function (and not per-bucket).

In closing, let me stress that this version has not really been tested all that much. It passes simple SCSI and IDE testing, should work on any hardware basically.

===== drivers/block/Makefile 1.14 vs edited =====

@@ -8,7 +8,8 @@
 # In the future, some of these should be built conditionally.
 #
 
-obj-y	:= elevator.o ll_rw_blk.o ioctl.o genhd.o scsi_ioctl.o deadline-iosched.o
+obj-y	:= elevator.o ll_rw_blk.o ioctl.o genhd.o scsi_ioctl.o \
+	    deadline-iosched.o sfq-iosched.o
 
 obj-$(CONFIG_MAC_FLOPPY)	+= swim3.o
 obj-$(CONFIG_BLK_DEV_FD)	+= floppy.o

===== drivers/block/ll_rw_blk.c 1.149 vs edited =====

@@ -1279,7 +1279,8 @@
 	if (blk_init_free_list(q))
 		return -ENOMEM;
 
-	if ((ret = elevator_init(q, &iosched_deadline))) {
+	//if ((ret = elevator_init(q, &iosched_deadline))) {
+	if ((ret = elevator_init(q, &iosched_sfq))) {
 		blk_cleanup_queue(q);
 		return ret;
 	}

===== include/linux/elevator.h 1.18 vs edited =====

@@ -73,6 +73,8 @@
  */
 extern elevator_t iosched_deadline;
 
+extern elevator_t iosched_sfq;
+
 extern int elevator_init(request_queue_t *, elevator_t *);
 extern void elevator_exit(request_queue_t *);
 extern inline int bio_rq_in_between(struct bio *, struct request *, struct list_head *);

Jens Axboe

Cool, that was fast! ;)

I tend to think 5 seconds is too small, 30 sec would be better IMHO (it should be tested at bit).

Unsure if it worth, but it probably it won't make that much difference, likely different workloads are working on different part of the disk anyways.

How does it feel?

Andrea

It's pretty easy to do in 2.5 :-). A 2.4 backport is of course feasible, but requires a bit more work (and possibly abstracting some of the elevator stuff there).

It probably is too small, testing will show. I don't see too many collisions from a dbench 32 or 64, so...

The rate of unrelated merging is typically quite low, so no it probably doesn't provide much of a performance benefit. However, it also keeps the code simpler to simply have a single merge hash per queue.

I don't know yet, haven't booted it on my work station yet. Will do so soon :)

Jens Axboe

Hi,

In the nature of taking this concept to the extreme, here's a CFQ disk scheduler (it should be obvious by now, that I'm simply making up a TLA as I see fit :-), or Complete Fair Queueing. It never suffers from queue collisions.

So how does it work? As with SFQ, a hash of busy queues is maintained. If a queue for a given queue doesn't exist, one is simply allocated. The actual queueing of requests works like the SFQ scheduler I sent out yesterday, with little twist: we try to put at least cfq_quantum number of requests on the dispatch queue. If only a small number of processes are waiting for io, then this significantly helps throughput by minimizing the time spent between finishing one request and starting a new one.

Other changes/fixes from SFQ:

- Leave request mergeable even while on the dispatch list, to make the merge window as big as possible.

- The dispatch_sort() would sometimes not order requests correctly.

- Various small fixes.

Interestingly, dbench results show little variance between runs with this CFQ scheduler. Another point of interesting to folks may be that it would be trivial to add process io priorities on top of CFQ (or SFQ for that matter, but I consider CFQ to be the superiour scheduler).

If you play with this, let me know how it fares. Patch is against 2.5.60.

===== drivers/block/Makefile 1.14 vs edited =====

@@ -8,7 +8,8 @@
 # In the future, some of these should be built conditionally.
 #
 
-obj-y	:= elevator.o ll_rw_blk.o ioctl.o genhd.o scsi_ioctl.o deadline-iosched.o
+obj-y	:= elevator.o ll_rw_blk.o ioctl.o genhd.o scsi_ioctl.o \
+	    deadline-iosched.o cfq-iosched.o
 
 obj-$(CONFIG_MAC_FLOPPY)	+= swim3.o
 obj-$(CONFIG_BLK_DEV_FD)	+= floppy.o

===== drivers/block/ll_rw_blk.c 1.149 vs edited =====

@@ -1279,7 +1279,7 @@
 	if (blk_init_free_list(q))
 		return -ENOMEM;
 
-	if ((ret = elevator_init(q, &iosched_deadline))) {
+	if ((ret = elevator_init(q, &iosched_cfq))) {
 		blk_cleanup_queue(q);
 		return ret;
 	}

===== include/linux/elevator.h 1.18 vs edited =====

@@ -73,6 +73,8 @@
  */
 extern elevator_t iosched_deadline;
 
+extern elevator_t iosched_cfq;
+
 extern int elevator_init(request_queue_t *, elevator_t *);
 extern void elevator_exit(request_queue_t *);
 extern inline int bio_rq_in_between(struct bio *, struct request *, struct list_head *);

Jens Axboe