CSCI 420

Homework Assignment #4

Due 12/08/2005

In this final assignment I would like you to return to the Linux kernel that you have previously modified. This time your task is to modify the kernel scheduler to implement a “last come, first served” scheduling algorithm. In order to do this you will need to modify the kernel/sched.c function in the kernel source tree. What we want to do is change the way the scheduler treats expiring tasks, always letting the currently running process to continue running (i.e. moving it to the head of the active queue). This means that a running job keeps running until it suspends, terminates, or a new process arrives in the active queue. This is not exactly LC/FS but the point here is to get into the code and change the guts of the scheduler J

Please turn in your modified scheduler code and a detailed write up explaining what you did to change the scheduler’s behavior. This should be submitted via email prior to the day of the class final. Send the email to hoffman@dlhoffman.com.

I suggest that you read the comments in the sched.c file as they are quite informative. You will also want to take a look at some of the following:

1) http://josh.trancesoftware.com/linux/linux_cpu_scheduler.pdf . This is pretty much the definitive 2.6 scheduler paper. In particular read the sections on Run Queues and Priority Arrays.

2) http://www.linuxjournal.com/article/7178. A good overview article that talks about differences between 2.4 and 2.6.

There will be a question or two about the implementation of the Linux O(1) scheduler and how the Run Queues and Priority Arrays are used on the Final!