An xv$6$ Lottery SchedulerDetails

You'll need two new system calls to implement this scheduler. The first is int settickets$($int number$),$ which sets the number of tickets of the calling process. By default, each process should get one ticket; calling this routine makes it such that a process can raise the number of tickets it receives, and thus receive a higher proportion of CPU cycles. This routine should return $0$ if successful, and $-1$ otherwise $($if$,$ for example, the caller passes in a number less than one$).$

The second is int getpinfo$($struct pstat $*).$ This routine returns some information about all running processes, including how many times each has been chosen to run and the process ID of each. You can use this system call to build a variant of the command line program ps$,$ which can then be called to see what is going on$.$ The structure pstat is defined below; note, you cannot change this structure, and must use it exactly as is$.$ This routine should return $0$ if successful, and $-1$ otherwise $($if$,$ for example, a bad or NULL pointer is passed into the kernel$).$

Most of the code for the scheduler is quite localized and can be found in proc.c; the associated header file, proc.h will also need some modification. To change the scheduler, not much needs to be done; study its control flow and then try some small changes.

You'll need to assign tickets to a process when it is created. Specifically, you'll need to make sure a child process inherits the same number of tickets as its parents. Thus, if the parent has $10$ tickets, and calls fork$()$ to create a child process, the child should also get $10$ tickets.

You'll also need to figure out how to generate random numbers in the kernel; some searching $($e$.$g$.$ grep rand$)$ should lead you to a simple pseudo$-$random number generator, which you can then include in the kernel and use as appropriate.

Finally, you'll need to understand how to fill in the structure pstat in the kernel and pass the results to user space. The structure should look like what you see here, in a file you'll have to include called pstat.h:

#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 tickets$[$NPROC$]$; $//$ the number of tickets this process has

int pid$[$NPROC$]$; $//$ the PID of each process

int ticks$[$NPROC$]$; $//$ the number of ticks each process has accumulated

$\}$;

#endif $//\_$PSTAT$\_$H$\_$

Good examples of how to pass arguments into the kernel are found in existing system calls. In particular, follow the path of read$(),$ which will lead you to sys$\_$read$(),$ which will show you how to use argptr$()($and related calls$)$ to obtain a pointer that has been passed into the kernel. Note how careful the kernel is with pointers passed from user space $--$ they are a security threat$(!),$ and thus must be checked very carefully before usage.

The attached program below uses the system calls described above and generates a test. It takes approximately $100$ seconds to run and prints something approximately once per second.

The last line should look something like:

$1(1,23)2(1,17)3(1,147)4(30,4480)5(20,2978)6(10,1552)$

Reading from left to right, process $1$ has $1$ ticket and won the lottery $23$ times. The interesting processes are $4,5,6$ which have $30,20,$ and $10$ tickets each and won the scheduling lottery $4480,2978,$ and $1552$ times. Your numbers may differ, but the proporitions between the $3$ processes should be pretty close.

totalticks $=4480+2978+1552=9010$

propA $=4480/9010$ ~$=0\mathrm{.}497$

propB $=2978/9010$ ~$=0\mathrm{.}331$

propC $=1552/9010$ ~$=0\mathrm{.}172$

Below is schedtest.c$.$ It should be added to your repository and added to the list of programs built for running inside of xv$6($look at stressfs for an example in the Makefile$).$

pl