You will build your own Linux kernel for this class. For each homework assignment, you will build a new Linux kernel. The image of the kernel you build for this assignment should be vmlinuz.hmwk4. Grading for this assignment will be done based on vmlinuz.hmwk4.
The Linux scheduler repeatedly switches between all the running tasks on the system, attempting to give a fair amount of CPU time to each task. Fair-share scheduling is a strategy that shares the CPU among sets of processes according to the users that own those processes. For example, suppose that Alice, Bob, and Carol belong to different users and are logged in to a machine that uses fair-share scheduling. Suppose Alice has one runnable process, Bob has three, and Carol has six. Fair-share scheduling views the ten runnable processes as belonging to the three users, and each user receives one-third of the CPU cycles to allocate to the processes that it owns. So Alice's single process would get about 33 percent of the available CPU cycles, each of Bob's three processes would get roughly 11 percent of the available CPU cycles, and each of Carol's six processes would get about 5.5 percent of the CPU cycles.
Add a new scheduling policy to support fair-share scheduling. Call this policy UWRR, for user weighted round-robin scheduling. UWRR should use fair-share scheduling based on each process's UNIX user identification. At each invocation of the scheduler, we will use a hierachical scheme to choose which task to run: first, a user is chosen, then, a task within that user's set of tasks is chosen. If we allow each user's chosen task the same amount of time on the CPU, each user should be represented equally.
Since we are making two choices in each scheduling decision, we need two algorithms: one to choose the user, and one to choose one of that user's tasks. Let's start by assuming we will use a Round-Robin scheme to decide which user to choose. We keep a queue of users, and whichever user was chosen last time we scheduled, we choose the next user in the queue for this schedule. We then choose a task within this user's set of tasks (more on this later), and let it run for a fixed amount of time (the time quantum). Now every user gets an equal amount of CPU time.
Now let's say that some users are more equal than others. Imagine that we associate an integer, which we'll call a weight, with each user, and when a user is chosen, we let the user's chosen tasks run for W time quanta (instead of a single time quantum), where W is the user's weight. In this way we can specify that some users get more CPU time than others, and also how much more. A user with a weight of 3 will get 50% more CPU time than a user with weight 2. This is called proportional sharing. More specifically, this implementation of proportional sharing is called Weighted Round-Robin.
We still haven't specified how a task is to be chosen once we choose
a user. For simplicity, use a simple round-robin (RR) scheduling
algorithm to do that. The intra-user RR scheduler should use the same
default timeslice as the Linux scheduler uses for a task with the
default nice value. Otherwise, the RR scheduler should work the same as
UWRR except that it schedules tasks, not users, and there are no
different task weights.
Recall that SMP operations (CONFIG_SMP) are turned off. Thus,
you do not need to worry about modifying code for the SMP case.
(60 pts) Implement a new task scheduler, which we will call User-based Weighted Round-Robin, or UWRR:
Most of the code of interest for this assignment is in kernel/sched.c
and include/linux/sched.h. These are probably not the
only files you will need to look at, but they're a good start. While
there is a fair amount of code in these files, a key goal of this
assignment is for you to understand how to abstract the scheduler code
so that you learn in detail the parts of the scheduler that are crucial
for this assignment and ignore the parts that are not.
Implement user weights. Add two system calls, getuserweight()
and setuserweight(), with the following prototypes:
int getuserweight(int uid);
int setuserweight(int uid, int weight);
Give getuserweight() syscall number 318, and setuserweight()
number 319. getuserweight() should return the weight of
the specified user, or -1 on error. The default user weight should be
10. setuserweight() should give the specified user the
specified weight, and return 0, or -1 on error.
For either call, a uid value of -1 indicates the current
user (that is, the owner of the task that is making the system call).
Otherwise, the range of valid uids is 0-65535. A bad uid should result
in a return value of -1 and errno set to EINVAL. Only
root is allowed to call setuserweight(); a call by any
other user should return -1 and set errno to EACCES.
Also, a user's weight must be greater than zero. Any attempt to set a
bad weight is an error, and errno should be set to EINVAL.
Put your code for these two system calls at the bottom of kernel/sched.c.
Your scheduler should operate alongside the existing Linux
scheduler. Therefore, you should add a new scheduling policy, SCHED_UWRR.
The value of SCHED_UWRR
should be 4. Only tasks whose policy is set to SCHED_UWRR
(normally done via the system call sched_setscheduler())
should be considered for selection by your new scheduler.
Your scheduler and the existing scheduler should interoperate as follows:
If there are any running tasks whose policy is SCHED_RR
or SCHED_FIFO (the real-time tasks), one of them should
be chosen before any other, according to the existing Linux scheduler
rules.
If there are any running tasks whose policy is SCHED_UWRR
(your scheduler), one of them should be chosen before any SCHED_NORMAL
(the default scheduler) tasks, according to the rules outlined.
If all running tasks have a policy of SCHED_NORMAL
(or SCHED_BATCH), the default scheduler should be used to
choose a task, according to the default scheduler's rules.
In other words, there should be a strict priority
relationship where SCHED_RR and SCHED_FIFO
are first, SCHED_UWRR is second, and SCHED_NORMAL
and SCHED_BATCH are last.
Making your scheduler operate alongside the existing may seem like an unnecessary difficulty, but it spares you the (significant) difficulty of dealing with scheduling during initialization, so you can get a system up and running before any of your own code goes into action.
If a user who has no runnable SCHED_UWRR tasks
has a SCHED_UWRR task become runnable, that user should
go to the end of the round-robin queue (should be the last user to get
a turn).
The base time quantum should be 100 ms. This means that if a
user has a weight of 5, she gets 500 ms at a time with which to
run her SCHED_UWRR tasks. Note that this does not mean that every one of her SCHED_UWRR
tasks runs for 500 ms. How long a task is allowed to run depends on the
intra-user RR scheduler.
Note that you will need to change the timer interrupt
handler so that schedule gets called at the right time. See scheduler_tick()
in kernel/sched.c.
Linux uses an array data structure for keeping track of tasks for scheduling. Tasks in this array are indexed by priority. You may find this data structure useful for implementing UWRR. However, your scheduler should be designed to work with any number of users and should not assume only a fixed number of users.
Hint: when you see the need_resched
field of the currently running task get set to 1, this is a signal to
some assembly code on the return path of the interrupt handler. It
causes schedule() to get called just before returning
from the current interrupt handler, and is the correct way to make a
schedule happen from within an interrupt handler, where you can't call schedule()
directly.
Hint: the user_struct structure in include/linux/sched.h
is used for tracking users. This structure may be helpful in creating a
useful way to keep track of users.
(15 pts) Create a simple test program to show that your
scheduler works. To
do this write a program that goes into an infinite while(1)
loop. This program would normally take up 100% of the cpu. Now
create three different users Alice, Bob, and Carol and have them each
run one or more
copies of the loop program. Use the program top to monitor
the CPU usage, both before and after you make your scheduler
modifications. Show that your scheduler is both fair (i.e., if
the weights are set equally Alice, Bob, and Carol each get 1/3 of the
CPU) and can be weighted (i.e., set weights 3, 2, and 1 and show that
Alice gets three time the CPU of Carol and 50% more than Bob).
Users can be added to the system using the useradd program (e.g., useradd alice).
You should create a patch to store changes you've made to the kernel and to submit your changes for this problem. If you've changed 50 lines of code, a patch will be about 50 lines long. This is much easier to store, email, or move around than the full 283,000-line source tree.
If you are using the KDB patch you applied from Homework 2 (which we recommend), your patch
should be from after that patch is applied; i.e., KDB diffs should not
show up in the patch.
Git is a perfect tool to create a patch and apply it. First back up your .config file, then do a ``make distclean'' in your changed source tree (you don't want object files, config files, etc. in your patch). Then, run git format-patch -k --stdout v2.6.18 > ../homework4.patch. Please run git commit for each step of the homework.