Changelog:

Your Task

  1. Add support for tracking the number of “tickets” in a process:
    • Add a system call called settickets which sets the number of “tickets” for the current process with the following prototype: int settickets(int number). The first process should have 10 tickets. You can assume that the maximum number of tickets per process is 100000. The number of tickets should be inherited by children created via fork.

  2. Add a system call called getprocessesinfo with the following prototype

    int getprocessesinfo(struct processes_info *p);

    where struct processses_info is defined as:

    struct processes_info {
    int num_processes;
    int pids[NPROC];       
    int times_scheduled[NPROC];       // times_scheduled = number of times process has been scheduled
    int tickets[NPROC];     // tickets = number of tickets set by settickets()
};

    (NPROC is a constant defined in param.h)

    The system call should fill in the struct pointed to by its arguments by:

    • setting num_processes to the total number of non-UNUSED processes in the process table
    • for each i from 0 to num_processes, setting:
      • pids[i] to the pid of ith non-UNUSED process in the process table;
      • times_scheduled[i] to the number of times this process has been scheduled since it was created (don’t adjust for whether or not the process used its whole time quantum);
      • tickets[i] to the number of tickets assigned to each process.
  3. Add support for a lottery scheduler to xv6, by:
    • changing the scheduler in proc.c to use the number of tickets to randomly choose a process to run based on the number of tickets it is assigned;
  4. Submit your code by running make submit and submitting the result .tar.gz file.

Some Supplied Test Programs

We have supplied some testing programs to aid you in figuring out whether your implementation is correct. Note that these programs are not complete tests. For example, they do not test that you set the correct default ticket count, that ticket counts are inherited by child processes correctly, and they may miss combinations of ticket counts some implementation techniques have problems with.

processlist.c

We have supplied processlist.c which is a test program which runs getprocessesinfo and outputs the information in the struct.

You can add this test program the same way you added a test program for the xv6intro assignment.

timewithtickets.c

We have supplied timewithtickets.c which is a test program which:

lotterytest.c

If you get an error about __divdi3 not being defined when trying to use this, try running sudo apt install gcc-multilib and recompiling after running make clean.

We have supplied an automated test program lotterytest.c [last modified 2021-03-04] which essentially runs several cases of timewithtickets.c and checks the number of times scheduled reported. It also has a couple of test cases to make sure that programs that are not runnable don’t confuse your scheduler. Like timewithtickets.c, it also verifies that getprocessesinfo returns output with correct numbers of tickets, etc.

It has some rather complicated code that attempts to perform a statistical test. We’ve set the parameters of the test so it should almost never indicate your code is wrong because of “bad luck”. However, this test might be sensitive enough to detect if you don’t use unbiased randomness (particularly if you use a pseudorandom number generator with a small range). I’m hoping this code is correct, but it’s very tricky and not easy to test if it’s too sensitive or not sensitive enough. See also the note on bias below.

Some notes on this test:

Hints

Reading on xv6’s scheduler

  1. Read Chapter 5 of the xv6 book for documentation on xv6’s existing scheduler.

  2. You can review Chapter 3 of the book, and/or the instructions on the intro homework on how to add system call and utility functions like argptr.

Reading on Lottery Scheduling

  1. For an alternate explanation to the lecture slides, see Chapter 9 of Arpaci-Dusseau.

Suggested order of operations

  1. Implement settickets, but don’t actually use ticket counts for anything.

  2. Implement getprocessesinfo. Use the processlist.c or other programs (e.g. ones you write) based on it to verify that it works.

  3. Add tracking of the number of times a process is scheduled. Use the timewithtickets.c or other programs based on it to verify that it works. Note that with round-robin scheduling, if multiple processes are CPU-bound, then each process should run for approximately the same amount of time.

  4. Implement the lottery scheduing algorithm. Use the timewithtickets.c to test it. Then use lotterytest.c to further test it.

Tracking the number of times a process is scheduled

  1. proc.h contains xv6’s process control block, to which you can add a member variable to track the number of times a process is scheduled a process has used.

  2. You may need to modify fork (in proc.c) or related functions to make sure the times scheduled variable is initialized correctly.

Adding settickets

  1. You can use argint to retrieve the integer argument to your system call. (Making sys_settickets take an argument will not work.)

  2. Like for tracking the number of times a process was scheduled, you will need to edit the process control block in proc.h.

  3. Follow the example of similar system calls in sysproc.c.

Adding getprocessesinfo

  1. struct processes_info needs to be declared somewhere accessible by both user and kernel code. One way of doing this is to declare it twice (make sure the declarations are identical), once in a header file included by kernel code (e.g. defs.h) and once in a header file included by user code (e.g. user.h). Another option would be to add a new header file and include it from both user header file and a kernel header file.

  2. You can use the argptr to retrieve the pointer argument in your system call handler.

    Note that argptr() takes a zero-based index of the number of the argument to retrieve, and returns whether or not retrieving the argument was successful. To actually get the value of the pointer, you should pass argptr() a pointer to the pointer. It will modify the pointed-to pointer when it is successful.

  3. You should iterate through the process list ptable, skipping over UNUSED processes.

  4. Look at the code for kill in proc.c for an example of how to search through the list of processes by pid.

  5. Before and after accessing the process table (ptable), you should acquire ptable.lock and afterwards you should release it. You can see an example of this in kill in proc.c. This will keep you from running into problems if a process is removed while you are iterating through the process table.

Adding the lottery scheduling algorithm

  1. You will need to add a psuedorandom number generator to the kernel. We’ve supplied a suitable version of the Park-Miller psuedo-random number generator (use the next_random function to get a random number between 1 and RANDOM_MAX) from Wikipedia’s page on Lehmer random number generators. You may use psuedorandom number generator code from elsewhere, so long as you clearly cite where obtained the code from.

  2. It is okay if your pseudorandom number generator uses a fixed seed. But if you don’t want to do this xv6 has a function cmostime that reads the current time of day.

  3. The logic in scheduler implements a round-robin scheduling algorithm, by iterating through all processes, scheduling each one as it iterates though them. You most likely will modify it to instead iterate through all processes (perhaps more than once) each time a new process needs to be scheduled to choose which one to run.

  4. xv6 does not support floating point, so you will need to do your random selection without floats or doubles.

  5. getprocessesinfo provides you the information you need to test that your lottery scheduler behaves correctly. You will probably not use it in the implementation of the scheduler itself.

  6. When there are no runnable processes, your scheduler should release the process table lock to give interrupts (like for keypresses) a chance to make programs runnable, then reacquire that lock and iterate through the process table again.

Processes not scheduled enough?

If you get errors from lotterytest.c about not seeing processes scheduled enough, this is because the total times_scheduled we saw from the tests was not enough to get statistically useful results. Common problems include:

Identifying panics

  1. If xv6 prints a message containing something like panic: acquire, this means that something called panic("acquire");. The panic() function stops the OS, printing out an error message. Generally, these panics are caused by assertions in the xv6 code, checking the current state is consistent.

    Most xv6 panic messages include the name of the function that called panic, so you can often search for that function name and see when it called panic.

    In general, you can get grep the xv6 code to find out what exactly the cause was.

    For example, panic("acquire"); appears in acquire() in spinlock.c. It is called if a thread tries to acquire a spinlock that the current thread already holds.

  2. There is a panic in the trap function that triggers when an unexpected trap occurs in kernel mode. You can infer more about those from the table of of trap numbers in traps.h and the message which is printed out before the panic.

    One of the possible traps is a page fault, which means you accessed a memory location that was invalid. This can be caused by using an invalid pointer, going out of bounds of an array, or using more space on the stack than is allocated.

Note on random bias

  1. The most common source of apparent bias is off-by-one errors in using ticket counts. Looking at what process is chosen with small ticket counts (e.g. 1, 2, 3) is helpful for this.

  2. The second most common source of apparent bias, especially errors with relatively large ticket counts, is something like double-counting one process’s tickets.

  3. If you experience only small biases, it is possible that it is a more subtle issue with how you use random numbers. One example of this that is likely if you use a random number generator with a small range of possible outputs compared to the one we suggest:

    • If you take a random number x in the range, say, 0 to 1023, and use it to choose a random number from 0 to 99 using x % 100, then you will choose numbers between 0 and 23 too often. One way to avoid this is to check if x is greater than 999, and, if so, select another random number x between 0 and 1023 (and keep doing this until you get one between 0 and 999 inclusive).

Credit

This assignment is based on Arpaci-Dusseau’s version of an xv6 lottery scheduler project.