Skip to end of metadata
Go to start of metadata

MP4 is due on Monday, November 15, 4:00 PM.

Related Readings

For this MP, you will be working with Disk I/O in Linux. The following book chapters would be useful for understanding the overall design of the Disk I/O component of Linux. 
Love: Chapters 13, 14.
Bovet and Cesati: Chapters 12, 14.


Linux I/O Scheduler

In this MP, you will be working with the Disk I/O scheduler in Linux and will implement your own scheduler. The Linux Kernel currently provides four I/O schedulers: the elevator scheduler, the anticipatory elevator scheduler, the completely fair queueing scheduler, and the no-op scheduler. All of the schedulers are defined under the block/ directory. They are responsible for deciding which disk request should be served next by the block device associated with this scheduler. Each device is associated with a request queue and a different class of scheduler. More detailed information can be found on the readings listed above.

Shortest Seek Time Scheduler

In this exercise, you are going to implement a shortest seek time scheduler. Upon receiving a disk request, the scheduler would first perform merging as usual. If the merging is unsuccessful and the request must be inserted into the queue, the scheduler would try to insert it so that the expected seek time would be minimized. It estimates this by trying to schedule the next request to be closest to the last request served by the disk.


The linux kernel provides a no-op scheduler that does nothing but merging the requests. You can choose to implement the shortest seek time scheduler directly within that file, or you can create your own file. Keep in mind that if you create your own file, you also need to change the KConfig file under the block directory so that your kernel can compile the new scheduler. Generally, we would recommend you implement the scheduler on top of the current no-op scheduler.

The complete API of an scheduler is defined in struct elevator_ops in include/linux/elevator.h. Your scheduler, however, does not need to implement all those functions. The functions you implemented would be declared as the .ops field in a static struct elevator_type in your scheduler. Please refer to the existing schedulers as examples.

Some of the functions in this ops are:

* elevator_merge_fn checks whether a new request can be coalesced with an existing request as described above. It also specifies the position at which a request is inserted in the request queue.
elevator_merge_req_fn coalesces two requests into a single request; elevator_merged_fn is invoked after two requests have been merged (it performs clean-up work and returns management data of the I/O scheduler that are no longer needed because of the merge to the system).
* elevator_dispatch_fn selects which request from a given request queue should be dispatched next. 
elevator_queue_empty_fn checks whether the queue contains requests ready for processing
elevator_add_req_fn and elevator_remove_req_fn add and remove a request to/from the request queue.
elevator_set_req_fn and elevator_put_req_fn are invoked when a new request is instantiated and returned to memory management (at this point in time the requests are not yet or no longer associated with any queue or have been satisfied).
* elevator_former_req_fn and elevator_latter_req_fn find the predecessor and successor request of a given request; this is useful when performing merging.

The existing linux kernel already provides a lot of helper functions. You may find the following functions in linux/include/elevator.h useful for your implementation

extern struct request *elv_rb_add(struct rb_root *, struct request *);
extern void elv_rb_del(struct rb_root *, struct request *);
extern struct request *elv_rb_find(struct rb_root *, sector_t);

The following functions from include/linux/blkdev.h are also useful for finding the sector of each request.

* blk_rq_pos()                 : the current sector
* blk_rq_bytes()               : bytes left in the entire request
* blk_rq_cur_bytes()           : bytes left in the current segment
* blk_rq_err_bytes()           : bytes left till the next error boundary
* blk_rq_sectors()             : sectors left in the entire request
* blk_rq_cur_sectors()         : sectors left in the current segment

To implement the Shortest Seek Time Scheduler, you need to keep the request list sorted, remember the last request dispatched, and select the block closest to the last dispatched block as the next request for dispatch. You can refer to the existing schedulers for moving the request to the dispatch queue.


In this MP, you can first test your implementation on a vanilla linux kernel by putting printk() statements in your scheduler. You can create a patch using diff. A good tutorial can be found here and here. Then you can apply the patch to the Android kernel, compile it according to the instructions from the last MP, and try run it either over the emulator or the actual phone. In all your experiments, you should make the new scheduler the I/O scheduler for your main storage devices, which is the disk on kernel, or the SD card on Android. Functionality, instead of speed, is what we look for for this MP.

Submission and Grading

This MP is due on Nov 15th at 4pm. Please email your code and an execution trace to both of the TAs. It is preferable that you get the scheduler working on the Android devices. But if there are technical difficulties in getting the scheduler work properly in the Android devices, you can also submit an execution trace for running the scheduler on a laptop or desktop. The grading would be broken down as follows:

* Design and Implementation. (40%)
* Execution Trace showing functionality of your scheduler (40%)
* Code Readability (20%)
* Extra Credit: Running the scheduler on the phone, and show it is working correctly by downloading and storing an App to the SD Card on the phone (5%).

MP Grading Section Sign-up

MP4 Grading Section Sign-up

Unable to render {include} Couldn't find a space with key: CS423student
Enter labels to add to this page:
Please wait 
Looking for a label? Just start typing.