This assignment is due February 15 by noon. Hardcopies of your
assignments should be submitted at the beginning of class.
In this assignment, you will implement lottery scheduling, as
discussed in class. This assignment is to be done on an individual
basis, no collaboration allowed. The implementation is to be done
using the VM that has been assigned to you. You are required to
submit source code, a README file documenting your files and code, and
a test run of your programs. For source code submissions, you only
need to submit new source code files that you created and kernel
source code files that you changed. You should clearly indicate your
name, email address, and assigned VM number on your submission.
You will build your own Linux kernel for this assignment. The image
of the kernel you build for this assignment should be vmlinuz.hmwk1.
Grading for this assignment will be done based on vmlinuz.hmwk1.
- Compile and install your own Linux kernel on your VM. To ensure
that you can recover from problems with your kernel, do not
overwrite the existing Linux kernel image. Instead, create a new
kernel image that you can boot from using LILO. For this
assignment, the image of the kernel you build should be named
vmlinuz.hmwk1. Configure /etc/lilo.conf to allow you to boot your
hmwk1 kernel.
- Implement a CPU lottery scheduler in Linux. You may use any
uniformly distributed random number generator but you must document
the source if the algorithm is not Park-Miller. Implement
compensation tickets for client processes that only consume portion
of its time quantum. Call it SCHED_LOT. You will need to modify the
sched_setscheduler() system call to allow users to select your new
scheduling policy and to assign tickets to a processes. You can
assume that all tickets are in the base currency, and you need not
implement hierarchical currencies.
- Write a test program and script to show your lottery scheduler is
working correctly. Demonstrate that: (a) the execution time matches
those of allocated tickets, (b) when a process is blocked, other
processes are getting bigger share of time, (c) ticket compensation
works for processes that consume portion of its time quantum.
- Compare the performance of your lottery scheduler with the
default Linux time-sharing scheduler. Which scheduler does a
better job of providing fair CPU allocation among some number of
processes? Which scheduler does a better job of supporting
proportional-share CPU allocation among some number of processes?
Which scheduler has less performance overhead? For the
measurements of performance overhead, you should consider how the
performance overhead changes with the number of processes.
State clearly what experiments you conduct and provide graphs that
justify your conclusions.
|