Timeline and progress

I am working on...

Complete documentation

Steps done:

Tuning and benchmarking BFQ

For detailed information, please see:
BFQ documentation
Results of benchmarks

Add features into BFQ scheduler

  • Disk peak rate estimating
  • Average seek distance estimating
  • Averate thinking time estimating

Merge B-WF^2Q+ into BFQ scheduler

The first version of BFQ has been committed into the repository. this version is implemented according to the algorithm on the BFQ tech report. However, that report have hidden some details that may be possible optimizing points, such as:

  • Dynamically changing maximum budget (currently hard wired in bfq.h)
  • Dynamically changing anticipatory waiting time (currently hard wired in bfq.h)
  • A good selecting function which can distinct between sync and async requests from one process(currently a simple FIFO per process)

Implement B-WF^2Q+ queueing algorithm

B-WF^2Q+ queueing algorithm is used to select next thread to be served, it uses augmented rb-tree to index all threads. This step includes:

  • Porting a augment featured tree.h from other BSDs to DFBSD
  • Implement functions (include interfaces get called by BFQ) of B-WF^2Q+
  • Test the algorithm with some user land test programs
Download the test program

Test request polling feature

Since the request polling emulation is implemented, some tests is needed to ensure it works as I expect and can provide enough functions to the BFQ scheduler.

Some additional issues that I may encounter when implementing BFQ should be considered now. One of them is how to realize the anticipatory tricks: a dequeue() call will block (or simply return) when:

  • The next bio to be dispatched is not from the same process who passes the last bio
  • The scheduler's waiting time for more bios coming from that process is not over

I will adjust the request polling FIFO policy to an anticipatory FIFO policy when I figure out a solution.

Implement request polling emulation on dsched

When considering the BFQ scheduler as a blackbox, it needs two interfaces: 1) by which bios get pushed into BFQ; 2) by which the driver poll bios from BFQ. We have to implement the latter one, at least make an effective emulation of driver polling.

To emulate request polling, I will add interfaces for dsched to support a scheduling policy register its "dequeue()" functions, which will get called when an emulation of request polling happens. A specific biodone function will be implemented for the scheduling policy, which will call the registered function when the disk's TCQ may be not full.

Timeline

Note: this timeline may change during as the project goes on.

Revised on July, 14th

Week 1-3 Implement request polling emulation on dsched. [DONE]
Week 4 Test request polling feature. [DONE]
Week 5-6 Implement B-WF^2Q+ queueing algorithm. [DONE]
Week 7-8 Implement BFQ main algorithm. [DONE]
Mid-term evaluation (July 17th): request polling and BFQ scheduler draft code will be ready.
Week 9 Merge B-WF^2Q+ into BFQ scheduler. [DONE]
Week 9-10 Add features into BFQ scheduler. [DONE]
Week 10-12 Tune and benchmark BFQ scheduler and the AS scheduler [DONE]
Week 13-14 Complete documentation. [Working]
Firm pencil-down date (August 26th): All codes and documentations will be submitted.