Certain uses of AI are permitted on this assignment. AI use is not
required.| CPSC 331 | Operating Systems | Spring 2026 |
This project has several goals:
Your primary task is to implement lottery scheduling for xv6, as described in the project README and below. As part of this, you will add two system calls to support lottery scheduling and write a simple version of the utility ps. There again isn't a lot of code to write; as with the previous project, the crux of the assignment is understanding what is going on in the relevant portions of xv6.
Review the course policy on academic integrity.
Certain uses of AI are permitted on this assignment. AI use is not
required.
The basic rule: you may use the code completion features of Copilot but may not use features (such as the coding agent) where code is generated from English language prompts. It is also essential that you understand and think critically about any code suggested by Copilot, both to help develop your C programming skills and because while the code suggestions are often uncannily on target, they are not always exactly what you want.
Using the code explanation features of Copilot Chat is permitted, though be careful that this doesn't spill over into code generation.
Review the policy on late work.
Revise and resubmit applies for this assignment. Review the details of how revise and resubmit works.
To hand in your project:
Make sure that you have included a comment at the beginning of your program containing your name and a description of the program, and that you have auto-formatted it.
Copy your entire scheduling-xv6-lottery directory to your handin directory (/classes/cs331/handin/username).
Check that the handin was successful and that the directory structure is correct: your handin folder /classes/cs331/handin/username should contain a folder scheduling-xv6-lottery which in turn contains a src directory.
Do the steps outlined in reddish boxes below before you start writing code.
Copy the scheduling-xv6-lottery directory (and all of its contents) from /classes/cs331 to your workspace folder (~/cs331/workspace). Make sure that you end up with the scheduling-xv6-lottery directory inside your workspace folder, don't just copy its contents.
The provided code includes the xv6 codebase (the same thing you started with for the last project with a few additions described below), some test cases for the system calls you'll add, and a tester program user/schedtest.c to aid in determining if your scheduler is working correctly.
Very important! One of the things the autoformatter can do is reorganize the #include directives in your code. While useful in some circumstances, this will break the xv6 code. You should have taken care of this as part of the setup for the previous xv6 project. (If you didn't, go back and look at that now.)
The provided test cases focus on the two system calls you are implementing. Running them is largely the same as with the previous xv6 project, with the one difference being that if you want to run the provided tests directly (instead of using make test), do so with:
./test-lottery.sh
from the top-level scheduling-xv6-lottery directory.
In addition, a test program schedtest has been provided to help you test your scheduler, but this will need to be run manually. From the xv6 shell prompt in QEMU, run either:
schedtest <n> <ticks> <tickets1> [<tickets2> <tickets3> ...]
or
schedtest <n> <ticks>
where n is the number of processes to start, ticks is the duration (in ticks, which are approximately 10ms each) to let the processes run, and tickets1 etc are the number of tickets assigned to process 1, process 2, and so forth. The second version runs the n processes with the same (default) number of tickets. (This is handy for observing the default round-robin scheduler, or to test that the lottery scheduler acts like a round-robin scheduler when all processes have the same number of tickets.) Note that you do not type the <> or [] symbols — <> denotes something you replace with an actual value and [] denotes optional elements.
Important: schedtest makes use of the getpinfo and settickets system calls that you will be implementing, so you cannot use it (or even compile it) until you've completed those steps. As a result, the provided Makefile does not compile schedtest.c. When you are ready to use schedtest, look for the following lines in src/Makefile:
XUPROGS := #XUPROGS := schedtest
and replace them with
#XUPROGS := XUPROGS := schedtest
(This just switches which line is commented out.) Run make to compile and you should be good to go.
Of particular relevance to this project:
scheduling in xv6: Scheduling (in particular, the section on proc.c)
system calls: review the posted slides from class and the references provided in the previous xv6 project relating to system calls
navigating the xv6 source: review the information on grep and VSCode's "Find in Folder" feature from the previous xv6 project
xv6's printf is much more limited than the standard C version. To help you line things up in columns, a padint function has been added to xv6's standard libraries. Locate its implementation in the xv6 code to see what it does and how to use it. As with printf, you'll need to #include "user.h" in any code that uses padint.
You'll need a random number generator for lottery scheduling, but you don't need to hunt down and implement your own as stated in the README — versions of C's standard rand and srand functions have been added. Look up the C versions in the man pages (man 3 rand) to find out how to use them, but #include "rand.h" instead of the standard C library when you use them in your code.
To print messages for debugging kernel code, use cprintf instead of printf. (printf is only for printing when running in user mode — the two different versions have to do with using different sections of the address space for kernel vs user mode.) cprintf is similar to printf but you don't have to specify the file descriptor first — all output from cprintf goes to the console. Look for where it is defined/used in the xv6 code for examples.
You have one main task: implement lottery scheduling. There are also two supporting tasks: add some additional process statistics and a ps command to help you see whether or not your scheduler is working properly. The project README provides an overview, though note that your implementation should follow what is described below — there are some modified specifications as well as more specifics about how to achieve what the README describes.
To do this:
Work through the sections below, in order. For each, read through the whole section to see what it contains before getting started writing code. There are a number of specific directions and hints that will make things a great deal easier if you are aware of them rather than just launching straight into trying to achieve the specifications.
The first step is to add support for getting information about processes — a system call int getpinfo(struct pstat *) to retrieve the info from the OS and a user command ps that can be run from the shell. (This isn't needed for the scheduler as such, but it will make it possible to see whether the scheduler is working correctly.) To do this:
getpinfo needs to retrieve a lot of information, so we need to define a data structure to hold that info. We'll call this data type pstat, for "process statistics". Use the definition given below rather than the one in the README. Put it in the file include/pstat.h.
Add the getpinfo system call as described in the README; look there for the expected header, behavior, and return values. This will be similar to getreadcount so proceed like you did in the previous project. However, when you get to the body of sys_getpinfo things will be a little different because getpinfo takes a parameter and getreadcount did not. See the discussion below for more on this, and for info on implementing the functionality of getpinfo.
To test: Run the provided tests. Tests 1 and 2 should pass.
Implement ps, a user command which lists information about current processes. (Try the Linux command ps -u to see a version of what your ps will do.) The output should be formatted as shown, with column headers and things neatly lined up:
PID Size State Name 1 12288 2 init 2 16384 2 sh 3 12288 4 ps
This is a user program, not a system call, so follow the pattern of what you did for the hello world program in the previous project. Put your implementation in the file user/ps.c and remember to update the Makefile accordingly so your program will be compiled and the executable copied into xv6's file system. See the Reference section above for some help with getting the columns lined up. Also remember to skip unused process table entries!
To test: There is no provided test for ps — test it interactively by launching xv6 in QEMU (make qemu) and running ps.
Definition for pstat:
#ifndef _PSTAT_H_
#define _PSTAT_H_
#include "param.h"
struct pstat {
int inuse[NPROC]; // whether this slot of the process table is in use (1 or 0)
int pid[NPROC]; // the PID of each process
char name[NPROC][16]; // the name of each process
int state[NPROC]; // the state of each process (as int because enum procstate is not visible in user space)
uintp sz[NPROC]; // the size of each process's memory (bytes)
};
#endif // _PSTAT_H_
As with getreadcount, it is helpful to look for an example already in the code that is similar to what you want to do. Since you are implementing a system call, look over the headers in include/user.h to find anotehr system call with similar parameters to use as a guide — getpinfo takes a struct, so fstat (which takes a different struct) is a good example.
Looking at the body of sys_fstat, you'll see that it does...something...and then calls a helper function filestat. filestat does the real work of the system call; the something before that call is what deals with the system call's parameters. Remember the flow of control when a user program calls a library routine: the handling of the subroutine call involves pushing the subroutine's arguments onto the stack. So that pstat (well, the address of the pstat — struct pstat * means we've passed a pointer) is on the stack, and the body of sys_getpinfo needs to retrieve it. Also, since we're now in kernel mode, the OS should thoroughly check that the parameters are valid. That's what is going on in sys_fstat — a local variable is declared for each of the system call's parameters and argfd, argptr, and argint (not used by sys_fstat) retrieve various types of parameters from the stack into local variables. Read more about this in the following (start with the section on "fetchint" and continue through "argstr").
Follow a similar pattern for getpinfo — retrieve the parameter values and do basic validity checking in the body of sys_getpinfo (return -1 if there is an error), then call a helper to do the real work. The helper should be implemented in kernel/proc.c — if you look for where filestat is implemented, you'll notice that the convention for file-related system calls is to put the sys_ handler in kernel/sysfile.c and the helper in kernel/file.c. Process-related system calls go into sysproc.c and proc.c.
Finally, on to the actual functionality of getpinfo! First check any preconditions (e.g. that the parameter passed in isn't NULL), then go through the processes in the process table (ptable.proc) and copy the relevant information into the pstat parameter. The return value should follow the usual conventions: return -1 if there is any error (such as a violated precondition) and 0 on success. Some notes and tips:
xv6 doesn't have a definition for NULL so use the value 0 instead.
The global ptable variable is the process table, and it has a field ptable.proc which is an array holding the per-process state for each process. NPROC is a global constant defining the number of slots in the array. The per-process state is in a structure of type struct proc, which you can see defined in kernel/proc.h.
Since the process table holds an array of processes, not all of the slots in the array may be in use at a given time. A process state of UNUSED indicates an unused slot; the inuse field of pstat should be a boolean reflecting whether this slot of the process table is in use (state != UNUSED) or not. Possible process states are defined in include/proc.h.
Care is needed when copying strings — a string variable is of type char * and an assignment statement just copies the pointer. Use safestrcpy to copy the process name. Locate where it is implemented in the xv6 code for a brief comment explaining it; you can look up the standard C strncpy in the man pages to understand the reference to strncpy as xv6's version of that works the same. In short, your usage will be something like the following:
safestrcpy(ps->name[i], ptable.proc[i].name, sizeof(ps->name[i]));
The parameters are the destination (where to copy the string), the source (the string to copy), and the number of characters to copy. sizeof returns the size of what it is passed; the idea here is to only copy as many characters as fit in the space a pstat has for the process names.
Be sure to #include "pstat.h" at the beginning of .c files where you reference the struct pstat type so that the compiler can find the definition. In header files (include/user.h and include/defs.h) add struct pstat at the beginning instead.
To help determine whether or not a scheduler is working properly, we need to be able to determine how much CPU time a process is getting.
Add
int ticks; // Number of ticks the process has run
to the definition of struct proc in include/proc.h: we'll store the time the process has run with the rest of the per-process information in the process table. Since xv6 is running through an emulator and is actually just a process itself, actual elapsed time isn't meaningful — instead time will be measured in "ticks", the number of timer interrupts that have occurred.
Initialize ticks to 0 — locate where the per-process information gets initialized when a new process is created. (You did something similar to initialize readcount.)
Update ticks: xv6 invokes the scheduler and does a context switch for every timer interrupt, so a process's ticks counter can be incremented each time we switch to that process. Locate where the scheduler subroutine is implemented — where the context switch happens is noted with a comment within the body of scheduler. Increment ticks right after the process state is set to RUNNING and just before the actual context switch happens.
Finally, update getpinfo and ps to report the accumulated ticks. This means adding a field to pstat for each process's ticks, updating getpinfo to retrieve that information as well, and updating ps to report it as shown.
PID Size State Ticks Name 1 12288 2 30 init 2 16384 2 17 sh 3 12288 4 7 ps
To test: Test manually, by running xv6 in QEMU and using ps.
Lottery scheduling is based on tickets, so we need to add support for tickets.
The number of tickets a process has will be stored with the rest of the per-process information. Add a field to struct proc for the number of tickets and initialize it to 1 (by default, each process should get one ticket) when a new process is created. (These steps are similar to what you did for tracking the number of ticks.)
Child processes should inherit the parent's number of tickets. Locate where the fork system call is handled and where within that other aspects of the parent's state are copied to the child, and add handling for the number of tickets.
Update getpinfo and ps to report the number of tickets, similarly to how you updated them to report the number of ticks. Format ps's output as shown.
PID Tickets Size State Ticks Name 1 1 12288 2 13 init 2 1 16384 2 16 sh 3 1 12288 4 7 ps
Add the settickets system call as described in the README; look there for the expected header, behavior, and return values. This is another system call with parameters, so the pattern will be similar to what you did for getpinfo, though with an integer parameter instead of a struct — look for an existing integer-parameter system call to use as a guide. The actual functionality of settickets is quite short so you don't need a helper — just do everything in sys_settickets.
To test, first enable compilation of tests 3-5 by replacing the following lines in tests/pre:
TESTS=test_1,test_2 #TESTS=test_1,test_2,test_3,test_4,test_5
with
#TESTS=test_1,test_2 TESTS=test_1,test_2,test_3,test_4,test_5
Then run the provided tests; tests 3-5 should now pass. Test ps manually, by running xv6 in QEMU and using ps. (Running ps also lets you see that the number of tickets is being initialized properly and that getpinfo includes ticket counts.)
Finally, scheduling.
The first step is to understand xv6's current scheduler and how the scheduler fits into the whole codebase. There's a link given in the Reference section above that describes how it all works — read it now.
Start up xv6 in QEMU and run schedtest with several processes to see how the current scheduler behaves — (about) how many ticks does each process get? Is that what you from a round-robin scheduler? (See the Testing section above for information on schedtest.) Ignore what is printed about tickets — the default scheduler doesn't use tickets.
Next, review lottery scheduling and how it works. This is covered in the first few sections of chapter 9 in OSTEP.
Implement it! Replace the round-robin part of xv6's scheduler in scheduler with lottery scheduling: in the main loop of the scheduler, determine the total number of tickets of runnable processes, pick a random ticket, loop through the runnable processes to find the winner, and switch to the chosen process (including incrementing the ticks). See the notes and tips below.
To test: start up xv6 in QEMU and run schedtest to see what share of CPU time your processes are getting. Is it (approximately) in line with what you expect from their ticket counts?
Some notes and tips on implementing lottery scheduling:
Keep in mind the discussion of critical sections and the usage of locks to protect them from class, and observe where and how the default xv6 scheduler makes use of locks.
See the Reference section above for information about generating random numbers and printing debugging messages from kernel code.