Suggested Summer of Code 2011 project idea

The BFS scheduler is a relatively simple scheduler curiously similar to the 4BSD scheduler but apparently even simpler and with improvements for machines with a relatively small number of CPUs (⇐ 16). It would be good to see how it compares to current FreeBSD schedulers, which are fairly complex.

• Good knowledge of C
• Knowledge of what system process scheduling actually is
• Ability to do a “clean room” reimplementation of the GPL code as BSD code

Suggested Summer of Code 2009 project idea

Note: with geom_sched in the system and SSD devices more and more popular, there isn't a real need to do further work on this project

Technical Contact: luigi@freebsd.org

In a 2005 GSoC project, “Pluggable Disk Schedulers”, Emiliano Mennucci explored the feasibility of pluggable disk schedulers for FreeBSD. The project was successful, but we could not explore certain approaches (e.g. “anticipation”, where requests are delayed hoping that some future ones can served without a seek) due to architectural limitations the kernel had at the time.

Since then, the GEOM infrastructure has become available on FreeBSD for interacting with disk I/O requests. GEOM has enabled us to work on disk schedulers in a much more flexible way, allowing a much faster development of disk scheduling algorithms. With Fabio Checconi, we have developed a prototype implementation of some anticipatory schedulers, see GEOM_SCHED.

http://info.iet.unipi.it/~luigi/FreeBSD/#geom_sched works within the geom layer, i.e. above the device driver where queueing of requests may actually occur. The way GEOM_SCHED does scheduling is by limiting the number of outstanding requests to the device, and the performance implications of this approach need to be measured. An alternative approach is to push the scheduler (using the same algorithms developed in GEOM_SCHED, and most likely the same code) within the device drivers. This less general (as it needs to be replicated in all drivers) but it may be an interesting thing to do e.g. for some popular device drivers such as ATA.

The proposed SoC work can address one or more of the following aspects:

• implement suitable classifiers for disk requests;
• implement techniques for the auto-tuning of the scheduler parameters;
• measure the performance implications of doing scheduling above the device driver, and possibly design and implement a suitable mechanism to push the GEOM_SCHED module within the device driver itself.

Ultimately, we expect to end up with a production quality subsystem for use in FreeBSD.

References: The Pluggable Disk Schedulers SoC project, http://www.happyemi.org/hybrid/

• Ability to read and understand foreign C code.
• Ability to write C code.
• Knowledge of GEOM (or interest in getting familiar with it).