In this assignment, you will be implementing a compensating-lottery scheduler and supporting system calls in xv6. Along with that, you will be updating the process sleep and wakeup mechanisms.
Unlike prior projects, this project can be done in pairs, so find yourself a partner you would like to work out this assignment with.

Learning objectives:

• Understand how a lottery scheduler works.
• Learn how to add new features (such as a new scheduler) to existing code bases.
• Gain experience working with collaborators. Expect to spend a lot of time communicating with each other and working together.

Administrivia:

• This project can be performed in groups of 2.
• Due Date: July 15th, at 11:59PM (slip day policy will apply to both people in the the group)
• The final submission will be tests on lab machinesLinks to an external site., so make sure to test your code on these machines.

Details:

1) Background

The current xv6 scheduler implements a very simple Round Robin (RR) policy.  For example, if there are three processes A, B and C, then the xv6 round-robin scheduler will run the jobs in the order  A B C A B C … , where each letter represents a process.  The xv6 scheduler runs each process for at most one timer tick (10 ms); after each timer tick, the scheduler moves the previous job to the end of the ready queue and dispatches the next job in the list.   The xv6 scheduler does not do anything special when a process sleeps or blocks (and is unable to be scheduled); the blocked job is simply skipped until it is ready and it is again its turn in the RR order.

Since RR treats all jobs equally, it is simple and fairly effective. However, there are instances where this “ideal” property of RR is detrimental: if compute-intensive background jobs (anti-virus checks) are given equal priority to latency-sensitive operations, operations like music streaming (latency-sensitive) suffer. Lottery SchedulingLinks to an external site. is a proportional share policy which fixes this by asking users to grant tickets to processes. The scheduler holds a lottery every tick to determine the next process. Since important processes are given more tickets, they end up running more often on the CPU over a period of time.

2) Scheduler details

1.1) Basic lottery scheduler

In your scheduler, each process runs for an entire tick until interrupted by the xv6 timer. At each tick, the scheduler holds a lottery between RUNNABLE processes and schedules the winner. When a new process arrives, it should have the same number of tickets as its parent. The first process of xv6 should start with 1 ticket. You will also create a system call settickets(int pid, int tickets), to change the number of tickets held by the specified process.
As an example, if there is a process A with 1 ticket and process B with 4 tickets, this is what the timeline might look like:

In this case, A was scheduled for 4 ticks, and B for 16. Given sufficiently large number of ticks, we can expect the ratio of CPU time per process to be approximately the ratio of their tickets.

Scheduling is relatively easy when processes are just using the CPU; scheduling gets more interesting when jobs are arriving and exiting, or performing I/O. There are three events in xv6 that may cause a new process to be scheduled:

• whenever the xv6 10 ms timer tick occurs
• when a process exits
• when a process sleeps.

For simplicity, your scheduler should also not trigger a new scheduling event when a new process arrives or wakes; you should simply mark the process as “RUNNABLE”. The next scheduling decision will be made the next time a timer tick occurs.

1.2) Compensating lottery scheduler

Like we discussed in MLFQ, many schedulers contain some type of incentive for processes that sleep (or block) and voluntarily relinquish the CPU so another process can run; this improves overall system throughput since the process isn’t wastefully holding on to the CPU doing nothing. We will add such an incentive to the lottery scheduler. Your scheduler will track the number of ticks a process was sleeping/blocked. Once it’s runnable, it will boost (double) the number of tickets for the same number of ticks. For instance, if a process slept for 5 ticks, its tickets would be artificially doubled for the next 5 lotteries it participates in.

Example: a process A has 1 ticket and B has 4 tickets. Process A sleeps for 2 ticks, and is therefore given double tickets for the next 2 lotteries after it wakes. This allows the scheduler to keep the CPU usage ratio equal to the ratio of tickets, even when process A is blocked. The timeline could look like the following in this case (description below the timeline):

Note the following:

1. At each tick, we consider the tickets a runnable process has. Ticks 3, 4, 15 and 16 only have 1 runnable process, thus only B participates in the lottery.
2. Once A is no longer blocked, it starts participating in lotteries. If it slept for x ticks, it will participate in the next x lotteries with double the tickets.
3. Make sure that when a process sleeps, it is given compensation ticks for the amount of time it was actually sleeping, not the amount of time it wasn’t scheduled.  For example, process A becomes RUNNABLE at tick 17. You should boost its tickets only for the next 2 lotteries, regardless of whether A actually wins the lottery or not.

1.3) Carrying forward remaining boost

Assume A sleeps for 3 ticks, thus its tickets are boosted for the next 3 ticks. What happens if it sleeps for 3 ticks again while it still has 3 remaining boosts left? In this case, its tickets should be boosted for the next (3+3remaining) rounds after it wakes. This is important for maintaining the lottery scheduler’s proportional-CPU-share property. Given that A couldn’t even participate in the lottery when it was blocked, we need to ensure it has a higher chance of winning in the corresponding number of lotteries.

This is a potential timeline for the described situation. Realize that after tick 5, A was supposed to be boosted for 3 ticks. Since it got blocked before that, we ensure that it doesn’t lose the number of favourable/boosted rounds once it wakes.

3) Enhancing sleep and wakeup mechanism in xv6

Finally, you need to change the existing implementation of sleep() syscall.  The sleep syscall allows processes to sleep for a specified number of ticks.   Unfortunately, the current xv6 implementation of the sleep() syscall forces the sleeping process to wake on every timer tick to check if it has slept for the requested number of timer ticks or not.  This has two drawbacks.  First, it is inefficient to schedule every sleeping process and force it to perform this check.  Second, and more importantly for this project, if the process was scheduled on a timer tick (even just to perform this check), it will lose at least 1 favourable round since it ended up participating in the lottery.

You are required to fix this problem of extra wakeups by changing wakeup1() in proc.c.  You are likely to add additional condition checking to avoid falsely waking up the sleeping process until it is the right time.  You may want to add more fields to struct proc to help wakeup1() decide whether if it is time to wake a process.  You might also use this mechanism to count how many ticks a process was sleeping for so it can be boosted accordingly. You may find the section “sleep and wakeup” in the xv6 book (Links to an external site.) (starting from page 65) helpful.

4) Some implementation details

In order to hold a lottery, we first need a way to generate a random number. Here’s the code to do so:

Copy the following at the top of proc.c after the headers:

#define RAND_MAX 0x7fffffff
uint rseed = 0;

// https://rosettacode.org/wiki/Linear_congruential_generator
uint rand() {
    return rseed = (rseed * 1103515245 + 12345) & RAND_MAX;
}

5) New system calls

You’ll need to create 3 new system calls for this project.

1. int settickets(int pid, int n_tickets).  This syscall is used to set the number of tickets allotted to a process. It returns 0 if the pid value is valid and n_tickets is positive. Else, it returns -1.
2. void srand(uint seed): This sets the rseed variable you defined in proc.c. (Hint: in order to effectively mutate that variable in your sys_srand function, you will need to define extern uint rseed. Check https://stackoverflow.com/a/1433226Links to an external site.).
3. int getpinfo(struct pstat *).   Because your scheduler is all in the kernel, you need to extract useful information for each process by creating this system call so as to better test whether your implementation works as expected. To be more specific, this system call returns 0 on success and -1 on failure (e.g., the argument is not a valid pointer).  If successful, some basic information about each running process will be returned:

struct pstat {
  int inuse[NPROC]; // whether this slot of the process table is in use (1 or 0)
  int pid[NPROC]; // PID of each process
  int tickets[NPROC];  // how many tickets does this process have?
  int runticks[NPROC];  // total number of timer ticks this process has been scheduled
  int boostsleft[NPROC]; // how many more ticks will this process be boosted?
};

You can decide if you want to update your pstat statistics whenever a change occurs, or if you have an equivalent copy of these statistics in ptable and want to copy out information from the ptable when getpinfo() is called.

The file should be copied from ~/cs537-1/public/p4_files/pstat.h.

Do not change the names of the fields in pstat.h. You may want to add a header guard to pstat.h and param.h to avoid redefinition.

6) User-level applications for testing

To demonstrate that your scheduler is doing at least some of the right things, we provide 2 such applications:  loop and schedtest. The code for these programs is available in ~/cs537-1/public/p4_files.  Copy these into your src folder and have xv6 compile these as user programs by modifying the UPROGS variable in the Makefile.

loop is a dummy job that just does some work. It takes exactly 1 argument sleepT. It sleeps for sleepT ticks, then runs a huge loop.

schedtest runs two copies of loop as child processes, controlling the number of tickets and sleep time of each child.  The schedtest application takes exactly 5 arguments in the following order:

prompt> schedtest ticketsA sleepA ticketsB sleepB sleepParent

• schedtest spawns two children processes, each running the loop application.  One child A is given ticketsA tickets and execs loop sleepA; the other child B is given ticketsB tickets and it runs loop sleepB.
• Specifically, the parent process calls fork(), settickets() and exec() for the two children loop processes, A before B.
• The parent schedtest process then sleeps for sleepParent ticks by calling sleep(sleepParent)
• After sleeping, the parent calls getpinfo(), and prints one line of two numbers separated by a space: printf(1, "%d %d: %d
", runticksA, runticksB, runticksA / runticksB), where runticksA is the runticks of process A in the pstat structure and similarly for B.
• The parent then waits for the two loop processes by calling wait() twice, and exits.

You will be able to run schedtest to test the basic compensation behaviour of your scheduler.  For example:

prompt> schedtest 10 0 2 0 120
99 19 5   
# Since it's randomized, it's difficult to completely predict the output of your program.
# However, the key thing to note is that the ratio of runticksA/runticksB is close to the ratio of tickets 10/2.
# You should play around with the number of tickets you grant each process and see the CPU-ratio match.
# As long as one of the child hasn't terminated yet, increasing the sleepParent value should lead to the CPU-use ratio converging to 5.
# You can also modify the code for loop so that it runs longer if needed.

Thus, you might need to write your own userlevel programs to validate your scheduler.

As an example, in order to test the boosted algorithm, you can copy the loop program into another loop-print-info program.  loop-print-info can print  boostsleft using getpinfo() right after it finishes sleeping. Make sure you sleep for >= 10 ticks so that your process has a reasonable chance of getting scheduled during its boosted phase. Thus you can the expect value of boostsleft to be between 0 and 10. You could also print boostsleft just before the loop-print-info program terminates to ensure that boostsleft has counted down successfully.

We will not test your implementation of any other userspace programs: their purpose is to primarily help you test your scheduler. You are welcome to write more user applications and play with different values to test other aspects of the scheduler.

7) Other details

• You should run xv6 on only a single CPU. Make sure in your Makefile CPUS := 1.
• During a boost, you should not double the number of tickets you return in getpinfo. Instead, return the original number of tickets.
• Child processes will inherit the same number of tickets of the parent process irrespective of the number of boostsleft of the process. Boosts don’t carry over to the child process.
• All blocked processes should be boosted. In xv6, a blocked process is in the SLEEPING state. A process could be in SLEEPING state even if it didn’t use the sleep syscall; such processes should be boosted as well. Remember that different processes could be blocked for varying number of ticks.

Hints

Please refer to this documentLinks to an external site. for hints and suggestions regarding this project.

Testing and Handing in

Test cases have been released and can be accessed at ~cs537-1/tests/p4.

The handin directory will be  ~cs537-1/handin/LOGIN/p4 where LOGIN is your CS login. Similar to P2, please create a subdirectory called ‘src’: ~cs537-1/handin/LOGIN/p4/src.

Copy all of your xv6 source files (but not .o files, please, or binaries!) into this directory.

Each project partner should turn in their joint code to each of their handin directories. Each person should place a file named partners.txt in their handin/p4 directory, so that we can tell who worked together on this project.  The format of partners.txt should be exactly as follows:

cslogin1 wiscNetid1 Lastname1 Firstname1
cslogin2 wiscNetid2 Lastname2 Firstname2

It does not matter who is 1 and who is 2.  If you worked alone, your partners.txt file should have only one line.  There should be no spaces within your first or last name; just use spaces to separate fields.

To repeat, both project partners should turn in their code and both should have a turnin/p2a/partners.txt file.