CSCAN scheduler implemented

I have completed the implementation of the CSCAN I/O scheduler for Linux kernel 2.6.10. The patch is avaliable here . Once you patch the kernel and built it, you need to boot it with "elevator=cscan" as the kernel option.

Got CSCAN implemented

Got the CSCAN disk scheduling algorithm implemented inside the 2.6 Linux kernel. However the implementatin currently has only sorting implemented and no merging. Need to work on that next.

Disk Scheduler for the 2.6 kernel

Few days ago I started on an ambitious project of implementing a new disk scheduler for the 2.6 Linux kernel. The scheduler was to make use of the T-Algorithm . This involved some learning curve and I still haven't done much on it. Also with Bonda being at my place I could hardly get to it.

I have also being pondering about how much of practical use T-Algorithm is, since it is of order O(n^2). I am planning to instead implement the CSCAN disk scheduling algorithm which by making use of the Red Black Trees will have the time complexity of O(log n). However my earlier experiments did show that the average wait time in case of T-Algorithm is better than the CSCAN algorithm

CSCAN Sorting with Time Complexity O(log n)

Maintain two queues which will be sorted in ascending order using Red Black Trees. When a disk request arrives and if the block number it refers to is greater than the block number of the current request being served add (merge) it to the first sorted queue or else add (merge) it to the second sorted queue. Keep on servicing the requests from the first request queue until it is empty after which switch over to the second queue and now reverse the roles of the two queues. Simple and Sweet.

I am a rebel

Who am I?

Have taken the personality type tests a couple of times before. Took it again few days ago and the result has been the same as before. My type is ESTJ i.e. Extraverted Sensing Thinking Judging. The charachteristics for this type definately match my personality. I am hoping to understand my short comings so that I can overcome them.

Rocking Clemson

Had been to Clemson this weekend along with Bonda and Bully. Met Dsu and Korade and had a blast. Click here to view the madness.

Red Black Trees

Studied using the Red Black Trees (Balanced Binary Trees) in the Linux kernel. Also wrote some sample C programs to test the functionality. The deadline I/O scheduler implementation in the 2.6 kernel makes use of these for keeping a sorted queues of read and write requests.

The Usual Suspects

Will be driving over to Clemson for a get together with Bonda, Bully, Korade and Dsu. Miss U Pal!!!