Improve dsched interfaces and implement BFQ disk scheduling policy

Name: Zhuo Peng
Email: brillsp@gmail.com
Phone number (include country and area code):+8615120033106
Project title: Improve dsched interfaces and implement BFQ disk scheduling policy

Description of project goals, including details of how the delivered code will operate:

I. Background

Currently, two disk scheduling policy are implemented on dsched:1) no-op scheduler, which is default and simply implement a FIFO queue which ensures good throughput but may cause starvation; 2) FQ scheduler, which tends to improve the interactivity but some interbench show that it still need improvement to catch up with BFQ and CFQ.[1] Moreover, FQ and no-op are more demonstrations to show how dsched works than complex schedulers focusing on productivity.

Vendatesh Srinivas mentioned BFQ and CFQ disk schedulers in reply of my questions on the mailing list[2] and I found BFQ a good candidate for a further dsched policy to make up the disadvantages above.

BFQ[3](Budget Fair Queueing) is a fair queueing disk scheduler aiming at interactivity. Compared to its major competitor, Linux's CFQ scheduler, BFQ shows better performance and fairness on many respects and the worst cases performance similar to CFQ's.[4, 5] Besides, the author of BFQ published the detailed algorithm of BFQ in a technical report[6], and with the help of it I will be able to implement BFQ scheduler on dsched from scratch to avoid licensing issues (BFQ is under GPL).

II. Project Goals

A. Implement request polling feature for dsched

Current dsched implementation only features request dispatching. However, many scheduling algorithms including BFQ need the queued requests polled by lower drivers. These algorithms are based on queueing theory and maintain queues of requests which need a "dequeue" signal triggered to drive the whole algorithm. The trigger is independent of the events of enqueueing but dependent upon whether the hardware resource is available. Hence, no matter how the lower drivers process the requests (queue them again or dispatch them to the raw hardware), a polling interface has to be provided. The implementations of such interface varies on different OSs. The idea of request polling is more straightforward and less complex than other implementations such as that in "Linux elevator" (where a kernel thread "plug" and "unplug" the queue periodically)[7] and need no additional worker threads.

The implementation includes following parts:

1. Implement interfaces in dsched that can be called by driver when they asks for more requests.
2. Implement driver's polling mechanism by modify the driver itself. Note that lots of drivers support scheduling policies, so the implementations varies upon different drivers. I will firstly cover the most common cases such as nata and scsi_da drivers.
3. Ensure backward compatibility of drivers and dsched: both request polling and request dispatching will be supported and can vary from different policies (By deliberately implement the strategy() function of each driver featuring request polling; Drivers not featuring polling need no modification).
4. To test the implementation, a dummy scheduler, which behaves like no-op scheduler will be implemented.

B. Implement BFQ scheduler on dsched

This goal is straightforward: I will realize BFQ scheduler according to the technical report from scratch. The design of BFQ is structured and contains two parts:

1. The queueing algorithm: BFQ uses B-WF^2Q+ queueing algorithm to select next process (or thread) to serve. The algorithm is modular and provides a set of interfaces for BFQ main algorithm. There can be some extension that implement different queueing algorithm for BFQ.
2. The BFQ main algorithm: the algorithm will provides interfaces to applications to collect their I/O requests and to disk drivers for polling the next request to serve.

C. Tune and benchmark BFQ

BFQ has several parameters needs to be tuned for better performance. Lots of tests on different hardwares will be needed. The tuning and benchmarking starts simultaneously. Linux's implementation of CFQ and BFQ will be set as the control group. I will write scripts to cover as many aspects as possible to test the throughput, interactivity, fairness, etc.

III. What will be achieved by the end of the projects(-), and the future plan(*)

  - A more functional set of dsched interfaces

  - A mature disk scheduling policy may improve experience on desktop applications

  * More drivers will be modified to feature request polling and then, BFQ scheduler

  * Implement other scheduling policies on dsched. (Deadline, anticipatory, etc.)

Project timeline broken down by week, with details on when each feature described in the project goals will be available.

Note: Because my summer break starts at June 25th, and I have to prepare for final examinations during first 2 weeks of the project, I arranged less work on these weeks.

Week 1-3: Implement request polling for nata, scsi_da and vn (for debugging with vkernel in the future) drivers.
Week 4: Test request polling feature.
Week 5-6: Implement B-WF^2Q+ queueing algorithm.
Week 7-8: Implement BFQ main algorithm.
* Mid-term evaluation (July 17th): request polling and BFQ scheduler draft code will be ready.
Week 9: Merge B-WF^2Q+ into BFQ scheduler.
Week 10-12: Tune and benchmark BFQ scheduler.
Week 13-14: Complete documentation.
* Firm pencil-down date (August 26th): All codes and documentations will be submitted.

What additional resources as hardware or software will be needed for this project?

My own laptop is enough for coding and debugging, but I will need community's help in the tuning and benchmarking phase.

Please include or provide links to prior code related to this area of work.

[1] http://leaf.dragonflybsd.org/mailarchive/kernel/2011-03/msg00047.html
[2] http://leaf.dragonflybsd.org/mailarchive/kernel/2011-03/msg00044.html
[3] http://algo.ing.unimo.it/people/paolo/disk_sched/
[4] http://algo.ing.unimo.it/people/paolo/disk_sched/results.php
[5] http://kerneltrap.org/Linux/Budget_Fair_Queuing_IO_Scheduler
[6] http://algo.ing.unimo.it/people/paolo/disk_sched/bfq-techreport.pdf
[7] Daniel P.Bovet and Marco Cesati, Understanding Linux Kernel, Section 14.3: The I/O Scheduler

About Me

I am a junior undergraduate student from Peking University, China. I major in computer science and feel very interested in operating systems after taking OS courses in last semester, during which I completed MIT's 6.828 labs -- these labs cover how operating systems are organized and the basic principles of each part of OS. I was quite excited when the shell of JOS finally starts and decided to participate in an open source OS project to see what a real OSs are.

Knowledge and skills related to the project:

• Principles of operating systems internal. (And some simple/classic implementations on several parts of OS)
• Proficient in C
• Knowledge about compliers and x86 assembly language. (I wrote a toy C compiler targeting on Unicore-32 architecture, CPUs developed by MPRC labs of Peking University)
• Used to work under Linux/Unix(FreeBSD and ArchLinux on my laptop).