Pluggable disk scheduler for FreeBSD

The FreeBSD disk scheduler is the standard “elevator”, also known as C-LOOK, which is designed to maximize throughput, but cannot grant fairness among clients of the disk subsystem. In fact, large sequential I/O requests, or certain access patterns from one or a few processes, might almost completely starve other processes. This is particularly critical for applications with soft real time requirements such as audio/video players (or, to some degree, recorders).BR The problem could be solved by: BR 1) Implementing support for pluggable (ie. run-time selectable) disk schedulers, and BR 2) Implementing some of the disk schedulers presented in the literature that give better fairness guarantees. This would not only allow users with specific requirements to fulfill them, but also help experimenting with new proposals in this area. Our choice will be one called Hybrid, which is a variant of a proportional share scheduler.

17/07/2005: Hybrid scheduler is now implemented and works on FreeBSD 4.x (however a lot of testing should be done by now). Implementation can only ensure fairness among processes for now; I'm currently working to get fairness among users an groups, too (an accounting system).BR Scheduler switching is the major issue now: we need a way to move requests from the old scheduler to the new one. On FreeBSD 4.x it is easy, because it does not use semaphores: we just disable interrupts and we can access without issues to the disk queues.BR On FreeBSD 5.x and 6.x however things are not so easy. Queues are protected with semaphores which are used by the ATA driver when needed. bio_* functions are always called with the queue locked so we can do what we want there. But during scheduler switching we need a way to obtain the lock to work on the queue. However this is neither easy nor clean: sempahore is a driver “private” member. Driver knows when lock and unlock it, and a direct access to the semaphore will break incapsulation; this means that we could cause deadlocks and others bad things.BR One way to address the problem may be the following:BR we know that each request is inserted invoking bioq_disksort and deleted calling bioq_remove. When a scheduler switching is involved we put all incoming requests in a support queue, which is different from the one used by the scheduler. Eventually, the scheduler queue will become empty after consequentially calls to bioq_remove. When this happens, we can do the very scheduler switching and insert requests from the support queue to the new sheduler queue. An important thing to say is that inserting requests is NOT done by calling the bio_disksort (as previously stated we should obtain a lock before calling disksort and we can't); instead we call the “strategy” function. strategy is generally called by the filesystem to read/write a request from/to the disk. Its work is to initialize the driver to accept requests (which among all things also means obtain the lock to the driver queue) and then calling bioq_disksort. If we call strategy to insert requests to the new driver we do not need to worry about the semaphore because strategy function will do this for us.

07/07/2005: What stated in the previous report is now implemented on FreeBSD 4.x. The 'id' is a string which is “cscan” for the default scheduler and will be “hybrid” for the new scheduler which I'm implementing just now. Scheduler switching can be done with a sysctl call like: “sysctl vfs.scheduler.name=foo”. On FreeBSD 5.x, default functions have little different names:

1. bio_disksort, called by filesystem to schedule disk requests
2. bio_first, called by phisical device to get the next request to serve
3. bio_remove, called by phisical device to remove a request from the queue (This is always called AFTER bufq_first).

Changes to FreeBSD 4.x should work in the same way in the 5.x branch, too, but are not implemented just now.BR Note: I shall decide what happens to pending requests when a scheduler switching is involved. Basic idea is to add two function pointers to the elements of the linked list, named “init” and “flush” respectively. When a scheduler switching in involved, we can call the “flush” function for the exiting scheduler and “init” for the starting one. There are to way to manage pending requests:

1. A scheduler should put all pending requests a data structure which is returned by “flush” and then passed to the starting scheduler using “init”. This method requires a bit of programming.
2. When exiting, a scheduler can put pending requests into the default queue (the one used by cscan) and the new one can read requests from there. There is no need to write code for this solution, but it's not a “clean” way to manage the issue

01/07/2005: FreeBSD 4.x scheduling interface exports three functions called by OS:

1. bufqdisksort, called by filesystem to schedule disk requests
2. bufq_first, called by phisical device to get the next request to serve
3. bufq_remove, called by phisical device to remove a request from the queue (This is always called AFTER bufq_first).

Whatever scheduler you'd like implementing, you need to rewrite the previous three functions to do the “dirty” job.BR Actually, FreeBSD has no support for scheduler switching, so the first thing to do is to add it.BR Basic idea is to make bufqdisksort, bufq_first and bufq_remove pointer functions so that they can “point” to the specific scheduler procedures.BR We will create a linked list, in which each element represets a scheduler. An element should have the following fields:

• An 'id', which is unique among all schedulers
• Function pointers to the scheduler specific bufqdisksort, bufq_first and bufq_remove

The default FreeBSD scheduler (aka. CLOOK) shall be added to this list, too. Using the 'sysctl' command (and passing it the 'id') at runtime is possible to select the current scheduler. Each time a scheduler is selected, we shall copy the functions pointer contained in the list element to the “global” bufqdisksort, bufq_first and bufq_remove. This also have a big advantage: we don't need to change parts in the kernel which contains call to those functions.

s223560@studenti.ing.unipi.it