Homework 4: Lazy Memory Allocation Solution

As we discussed in class, one thing that paging hardware can be used for is lazy allocation -- only giving out physical memory when it's used, rather than when it's allocated. In this assignment, we'll modify xv6 to use a lazy allocator. We won't cover every corner case, but by the end of it we will have a basic working implementation.

Getting the Code from Github
As with last time, we'll be working off of a slightly modified version of xv6. The major difference is that the cat program has been modified so that it uses dynamic memory allocation rather than static allocation, which will allow us to uncover an edge case in a naive implementation.

If you still have your xv6 directory from last time, remove or rename it first. Then get the base xv6 code for this assignment:

$ git clone https://github.com/moyix/xv6-public.git Cloning into 'xv6-public'... remote: Counting objects: 4501, done. remote: Compressing objects: 100% (17/17), done. remote: Total 4501 (delta 3), reused 0 (delta 0), pack-reused 4484 Receiving objects: 100% (4501/4501), 11.68 MiB | 3.46 MiB/s, done. Resolving deltas: 100% (1800/1800), done. Checking connectivity... done. $ cd xv6-public/ $ git checkout hw5 Branch hw5 set up to track remote branch hw5 from origin. Switched to a new branch 'hw5'
Part 1: Use the debugger
In order to get acquanted with the debugger, we will start with debugging XV6. XV6 has a Makefile rule to make debugging simple, however you will need to have two open command line windows. Type the following commands on each:

Command Line 1: $ make qemu-gdb
Command Line 2: $ gdbtui kernel
Command line 1 is going to basically create a debuggeable version of XV6. Command line 2, is going to start the debugger.

Now we will setup a breakpoint in the system call that allocates memory. The call that user-process use in xv6 to allocate memory is called sbrk(); it's kernel-mode implementation is sys_sbrk() in sysproc.c. Set a breakpoint in this function. In order to do that, you might need a gdb cheatsheet like the one in NYU classes. Then answer the following questions when you submit your patch:

Run a user process like: 'ls'
What is the size of n when your breakpoint gets hit?
Print out the stackframe (backtrace) for this call.
Part 2: Removing Eager Allocation
Change sys_sbrk() so that it just adjusts proc-sz and returns the old proc-sz (i.e., remove the call to growproc()).

After rebuilding xv6, try running a command like echo hello:

init: starting sh $ echo hello pid 3 sh: trap 14 err 6 on cpu 0 eip 0x12bb addr 0x4004--kill proc
What went wrong, and why? (Answering this question is not part of the assignment, just think about it).

Part 3: Implementing Lazy Allocation
The message above comes from the trap() function in trap.c. It indicates that an exception (number 14, which corresponds to a page fault on x86) was raised by the CPU; it happened when eip (the program counter) was 0x12bb, and the faulting address was 0x4004. It then kills the process by setting proc-killed to 1. Can you find in the code in trap.c where that happened? (Answering this question is not part of the assignment either, just getting you familiar with the code)

Add code to trap() to recognize this particular exception and allocate and map the page on-demand.

Once you have implemented the allocation, try running echo hello again. It should work normally.

Hints:

The constant T_PGFLT, defined in traps.h, corresponds to the exception number for a page fault.
The virtual address of the address that triggered the fault is available in the cr2 register; xv6 provides the rcr2() function to read its value.
Look at the code in allocuvm() to see how to allocate a page of memory and map it to a specific user address.
Remember that the first access might be in the middle of the page, and so you'll have to round down to the nearest PGSIZE bytes. xv6 has a handy function called PGROUNDDOWN you can use for this.
You will need to use the mappages() function, which is declared as static, meaning it can't be seen from other C files. You'll need to make it non-static, and then add its prototype to some header file that is included by both trap.c and vm.c (defs.h is a good choice).
Part 4: Handling Some Edge Cases
Although simple commands like echo work now, there are still some things that are broken. For example, try running cat README. Depending on how you implemented Part 2, you may see:

init: starting sh $ cat README unexpected trap 14 from cpu 1 eip 80105282 (cr2=0x3000) cpu1: panic: trap 8010683a 801064fa 80101f4e 80101174 80105725 8010556a 801066f9 801064fa 0 0
Why is this happening? Debug the problem and find a fix (if this part works already, you don't need to make any changes).

Next, let's see if pipes work, by running cat
README | grep the

$ cat README | grep the cpu0: panic: copyuvm: page not present 8010828e 80104693 8010630b 8010556a 801066f9 801064fa 0 0 0 0
Find out what's going on, and implement a fix.

Hints

Think about what happens if the kernel tries to read an address that hasn't been mapped yet (for example, if we use sbrk() to allocate some memory and then hand that buffer to the read() syscall). Read the code in trap() with that case in mind.
Making pipes work is a very tiny change -- just one line in one file. Don't overthink it.
Submitting
As with HW3, you will use git to create a patch.

Commit your changes:

$ git commit --all --message="Implement lazy allocation" [hw5 ef751c0] Implement lazy allocation 4 files changed, 30 insertions(+), 10 deletions(-)
(Note: if you added any new files, you will also have to use git
add <filename before you run git
commit.)

Now create the patch file:

$ git format-patch hw4.unmodified 0001-Implement-lazy-allocation.patch
The command creates a file, 0001-Implement-lazy-allocation.patch, containing the changes you've made. Submit this file on NYU Classes, along a partner.txt listing your partner (if any).

Final Notes
Although this covers most use cases, there are still a few stray things that it doesn't handle:

Negative arguments to sbrk() should reduce the size of the process and deallocate the pages.
This code will allow multiple processes to collectively allocate more memory than the system has (overcommit).
It may be helpful, if you want to understand the material better, to think about how you could fix these issues.

Credit: Adapted from a homework by Brendan-Dolan Gavit.

Credit: Adapted from MIT's 6.828 in-class exercise xv6 lazy page allocation




Switch to the homework branch:







$ cd xv6-public

$ git checkout hw4

Branch hw4 set up to track remote branch hw4 from origin.

Switched to a new branch 'hw4'




The modified version has some new features:




It contains a random number generator. You can use it by including `rand.h` in a source file and then calling the function



long random_at_most(long max)







To get a random number between `0` and `max`, *inclusive*.




2. It contains a new system call,

`int gettime(struct rtcdate *date)`,







which retrieves the current date and time from the CMOS RTC and stores it in an `rtcdate` structure (you can see how `struct rtcdate` is defined by looking at `date.h`).




It contains a program designed to test the lottery scheduler you will develop, in the source file `lotterytest.c`.



Important Note




For simplicity in testing, you should run the tests for this assignment

in QEMU with just one CPU. You can do this by invoking the Makefile as:




make qemu CPUS=1







Lottery Scheduling




For this assignment, you will implement and test *lottery scheduling*, a randomized algorithm (discussed in class and in the reading) that allows processes to receive a proportional share of the CPU without explicitly tracking how long each process has been run.




Specifically, you should modify xv6 so that:




Each `struct proc` has an additional field, `tickets`, that tracks how many tickets it has.



New processes are assigned 10 lottery tickets when they are created.
When the scheduler runs, it picks a random number between 0 and the
total number of tickets. It then uses the algorithm described in class to loop over runnable processes and pick the one with the winning ticket.




User processes have a new system call, `settickets`, that allows a process to specify how many lottery tickets it wants. Normally this would be a bad idea, since it would let a process hog the CPU by specifying an arbitrary number of tickets -- but xv6 has no security anyway, so this is not that big a deal.



In addition to Tannenbaum's description of lottery scheduling in *Modern Operating Systems*, you may find it helpful to read over [Operating Systems: Three Easy Pieces, Chapter 9: Scheduling: Proportional Share](http://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched-lottery.pdf).




Of course, once you have implemented this, you will want to test that the scheduler works. Aside from basic tests that the system is still functioning, you should verify that allocating more tickets to a process does increase its share of the CPU allotted by the scheduler.




Included in the source distribution is a new program, `lotterytest`, which forks two children, sets their priorities, and runs a CPU-intensive task in each, timing the results. The test assigns 80 tickets to one and 20 to the other, so the first should be scheduled 4 times as often as the second (an 80% / 20% split).




To build `lotterytest`, just add it to the `UPROGS` list in the `Makefile` (taking care to use a tab character for indentation rather than 4 spaces). Note that it will not compile until you have added the `settickets` system call. The relevant portion of the `Makefile` is shown below:




.PRECIOUS: %.o







UPROGS=\

_cat\




_echo\

_forktest\

_grep\

_init\

_kill\

_ln\

_ls\




_mkdir\

_rm\

_sh\

_stressfs\

_usertests\




_wc\

_zombie\




_hackbench\




fs.img: mkfs README $(UPROGS)




./mkfs fs.img README $(UPROGS)




Given two processes started at the same time, that do the same amount of work, we expect that they will finish at the same time if they have the same number of tickets. We can predict how long they should take when the CPU is divided between them at various ratios. Suppose that we have two tasks T<sub1</sub and T<sub2</sub, each of which takes 5 seconds to run. Regardless of the share of the CPU each has, they will take 10 seconds total for both to finish. Running them with an equal share of




the CPU will cause them both to finish at the same time. We can calculate the expected runtime of T<sub1</sub when given a certain fraction of the CPU as:




R(T<sub1</sub, 1.0) = 5 seconds







R(T<sub1</sub, 0.5) = 10 seconds




R(T<sub1</sub, x) = 1/x * R(T<sub1</sub, 1.0)




So from this we can compute that if T<sub1</sub is given an 80% share of the CPU, it should finish in 6.25 seconds; T<sub2</sub will still finish in 10 seconds (remember, the scheduler is just redistributing the work to be done, so running the two tasks still takes 10 seconds no matter what







By running `lotterytest` a few times, you should be able to verify that the process with 80 tickets finishes sooner than the process with only 20. For example, here's the output I get:




$ make qemu CPUS=1




qemu-system-i386 -nographic -hdb fs.img xv6.img -smp 1 -m 512




WARNING: Image format was not specified for 'fs.img' and probing guessed raw.




Automatically detecting the format is dangerous for raw images, write operations on block 0 will be restricted.




Specify the 'raw' format explicitly to remove the restrictions.




WARNING: Image format was not specified for 'xv6.img' and probing guessed raw.




Automatically detecting the format is dangerous for raw images, write operations on block 0 will be restricted.




Specify the 'raw' format explicitly to remove the restrictions.

xv6...

cpu0: starting




sb: size 1000 nblocks 941 ninodes 200 nlog 30 logstart 2 inodestart 32 bmap start 58




init: starting sh

$ lotterytest

starting test at 17 hours 22 minutes 22 seconds




spin with 80 tickets ended at 17 hours 22 minutes 28 seconds spin with 20 tickets ended at 17 hours 22 minutes 32 seconds







You can see that the process with 80 tickets finished after 6 seconds, while the process with 20 tickets finished after 10 seconds. You can also play with the numbers in `lotterytest` to see the effect of varying the number of tickets.




**Hints**:




One possible way to track the total number of tickets is by carefully finding each place where the process state changes, and adding or subtracting tickets from a global as appropriate. However, this is actually rather tricky to get right. An alternative is to simply compute the number of tickets each time we enter the scheduler loop, before choosing the winning ticket.



Right now, the scheduler loop picks up where it left off after scheduling a process -- so if it finds a runnable process at index `i`, the next time the scheduler runs it will keep going through the list at index `i+1`. In order to make the lottery algorithm work, you will need to restructure the scheduler loop so that it starts back at the beginning of the list every time we return to the scheduler.



No changes are needed to the process list itself; you can continue to use the `ptable.proc` array (i.e., you don't have to implement a process queue).



You can consult the slides to find out how to add a new system call when adding



`settickets`.

As with the previous homework, the use of gdb to debug your code is highly encouraged.
If you want to see the list of running processes at any time, you can type `Control-p` at the xv6 console and it will print out a list of running processes. You may also want to modify this function (`procdump`in `proc.c`) to print out the number of tickets each process has so that you can debug your `settickets` call.



Submitting




You will use git to create a patch that contains your changes. First, tell git who you are:




$ git config --global user.email "you@example.com"




$ git config --global user.name "Your Name"




Then, commit your changes:




$ git commit --all --message="Implement lottery scheduling"




[hw4 94b0cf7] Implement lottery scheduling

7 files changed, 60 insertions(+), 7 deletions(-)







(Note: if you added any new files, you will also have to use




`git add <filename` before you run `git commit`.)







Finally, create a patch file. The command takes an argument that specifies what code we're comparing against to make the patch; in this case I have created a git *tag* that refers to the unmodified Homework 4 called `hw4.unmodified`, so you should run:




$ git format-patch hw4.unmodified




0001-Implement-lottery-scheduling.patch




The command creates a file, `0001-Implement-lottery-scheduling.patch`, containing the changes you've made. Submit this file on NYU Classes, along with the usual `partner.txt` listing your partner (if any).




**Submission Note**




Don't try to edit the patch file after creating it. Doing so will most likely corrupt the patch file and make it impossible to apply. Instead, change the original file, commit your changes, and run `git format-patch` again:




$ git commit --all --message="Description of your change here"




[hw4 7cc4977] Description of your change here




file changed, 1 insertion(+), 1 deletion(-) $ git format-patch hw4.unmodified
0001-Implement-lottery-scheduling.patch 0002-Description-of-your-change-here.patch




Then submit *both* patch files.