Geom-based Disk Schedulers
Disk scheduling is a consolidated topic in computer science. Some of the well-known results reached by the research community have not made it into FreeBSD, for more than a single reason. A previous Summer of Code project, Hybrid introduced a modular framework for pluggable schedulers and a novel fair queueing algorithm; due to architectural limitations anyway it didn't explore the feasibility of anticipatory scheduling, a technique that can increase significantly the throughput of synchronous sequential workloads on rotational media.
With Luigi Rizzo, we have developed a prototype framework to introduce pluggable disk schedulers in the Geom layer. It basically consists in a Geom class that queues up requests going to the provider it is attached to, and releases them according to the algorithm, which is implemented in an external module.
We also implemented a couple of algorithms, gsched_as which is a simple anticipatory scheduler with no per-client info, and gsched_rr which does anticipation and round robin among per-client queues.
This project's goals are, mainly, bringing the prototype developed in so far to a more usable form, and extending the capabilities of the scheduling algorithms shipped with the current code.
The main steps that will be taken to reach these goals are:
- a mechanism to introduce a geom between running nodes; i.e., something allowing hot-plugging a scheduling class between existing geom nodes while they're being accessed. This will be quite relevant to the diffusion the project will have;
- a classification mechanism, to associate each request to its client, and a credential mechanism to regulate how clients can access disk device.
- Extend our initial gsched_rr scheduler, introducing some basic heuristics to improve its performance under significative workloads. The first simple heuristics we will consider are seekiness and thinktime estimation, to better drive the anticipation mechanism. We will try to consider nonrotational media, to the extent permitted by the available hardware. The side-effect of this part of the project will be the production of a hopefully wide and complete set of benchmarking, together with some stressing of the code.
The project status will be tracked at http://feanor.sssup.it/~fabio/freebsd/geom_sched/.