Project 2b: xv6 Scheduler
There are three objectives to this assignment:
With increased sharing in the cloud, compute resources have become a commodity that is sold by the hour. CPU schedulers play an important role in guaranteeing that buyers get what they pay for, and thus schedulers must evolve along with new pricing models.
In this project, you will build a scheduler that simultaneously supports two pricing schemes similar to those used by AWS (Amazon Web Services) and other cloud services: reserved processes and spot processes. Your scheduler will have two levels to support these two process types, and will keep track of a "customer charge" per process in dollars.
Level 1 is for reserved processes and will receive priority over
Level 2. A reserved process is given a probabilistic guarantee of a
certain share of CPU resources. To implement level 1, use
a lottery scheduler, as described in
chapter of the online book.
Level 2 is for spot processes. These should run only using CPU resources that are left over from level 1. A spot process may run if not all CPU time is allocated at level 1, or if not all level 1 processes use their full allocation all the time. Of course, depending on the load at level 1, level 2 processes may never get an opportunity to run. Thus, people use reserved process for time-critical work (e.g., web apps), and only use spot computing for work that can be done at any time (e.g., bitcoin mining). As in AWS, your scheduler should allow each spot process to specify how much the person running the process is willing to pay per CPU-hour, and the scheduler should always choose the highest bidder that is runnable (assuming level 1 has been satisfied).
You'll need three new system calls to implement this scheduler. The first is
The second call is
The third is
Most of the code for the scheduler is quite localized and can be found in proc.c; the associated header file, proc.h is also quite useful to examine. To change the scheduler, not much needs to be done; study its control flow and then try some small changes.
You'll need to figure out how to generate random numbers in the kernel; some searching should lead you to a simple pseudo-random number generator, which you can then include in the kernel and use as appropriate. In this one case, simply copying code for a pseudo-random number generator from online is not considered cheating.
You'll need to understand how to fill in the structure pstat in the kernel and pass the results to user space. The structure looks like what you see in here.
Uptime is tracked with millisecond granularity in the ticks
variable in trap.c.
Beware of overflow. You may wish to use a pair of integers to store charges (e.g., one integer for dollars, and one for microdollars).
(Added Sep 28) There are times when we have not defined what your scheduler should do. For example, if only spot instances are runnable, and they all bid the same, which one should run? As another example, what if there are only reserved processes, but the reservations don't add up to 200%? In any of these cases, you should still run something (don't waste CPU). You can use any reasonable method to choose which process to run in such cases (e.g., pick randomly or with round robin).
(Added Sep 28) Lotteries should be held independently on each core. For example, if a process reserves 20%, that process might have 10 out of 100 tickets on each core (or 100 out of 1000, or whatever you decide).
(Added Sep 28) Currently in xv6, a process can only run on one CPU at a time (you will fix this in a later project). Thus, sometimes processes may have trouble using their full reservation. Processes with higher reservations should get more CPU time, but the fact that a process may get less than its reservation does not always indicate a bug, especially when a large percent is reserved.
(Added Sep 28) One concern is that because processes default to being spot processes with a bid of 0, a new process may never get a chance to set its reservation. You may optionally let each new process run for free for a short time after launch if you like.
The source code for xv6 (and associated README) can be found in ~cs537-2/ta/xv6/. Everything you need to build and run and even debug the kernel is in there.
You may also find the following readings about xv6 useful, written by the same team that ported xv6 to x86: xv6 book.
Particularly useful for this project: Chapter 9
What To Turn In
Beyond the usual code, you'll have to generate one or more graphs that help you argue your implementation is correct. In a file called graphs.txt, give the file names of your graphs, and briefly explain how the graphs show your code is correct. For example, you could show that reserved processes receive their correct share of CPU time, and that spot processes pay less for CPU time but have less predictable performance.