CS 3400: Operating Systems

Spring 2014 Schedule

Week Topics Project Reading
Jan 6–10 introduction, os structure building and running xv6 3ep intro, xv6 ch 0
Jan 13–17 concurrency reproduce graphs from ch 28 3ep ch 27–29, xv6 ch 4
Jan 21–24 (MLK day) semaphores, bugs, event loops 3ep ch 30–31
Jan 27–31 pc hardware, boot sequence xv6 ch 4 exercises, sharks xv6 appendix a, b
Feb 3–7 processes and address spaces 3ep ch 4–5, xv6 ch 1
Feb 10–14 virtual memory 3ep ch 12–15, xv6 ch 2
Feb 18–21 (Presidents day) page replacement malloc and free 3ep ch 16–21
Feb 24–28 interrupts and system calls xv6 ch 3
Mar 3–7 copy-on-write fork, part 1
Mar 10–14 (Spring break)
Mar 17–21 scheduling copy-on-write fork, part 2 3ep ch 6–7, xv6 ch 5
Mar 24–28 3ep ch 8–10
Mar 31–Apr 4 file systems 3ep ch 35–36, 38–39, xv6 ch 6
Apr 7–11 recovery, RAID random scheduler 3ep ch 40–43, 37
Apr 14–18 distributed file systems MLFQ scheduler 3ep ch 46–48
Apr 21–23 virtualization

Note: this schedule is tentative. Changes will be announced in class.

“3ep” refers to Operating Systems: Three Easy Pieces, our (free) primary text.

“xv6” refers to the xv6 commentary, our guide to the xv6 operating system source code. The complete source of xv6 with line numbers is available here.

xv6 resourses


  1. Reproduce the 3 graphs from 3ep ch 28. You should use the source code provided in the chapter. You must write some simple test code to run it, gather the results, and create charts using gnuplot.

  2. Complete the exercises from Chapter 4 of the xv6 commentary. For #3, complete the Sharks and Divers exercise.

  3. Implement malloc and free. You must coalesce free blocks, and you must include a tool to audit the heap. When called, it should display a complete list of free and allocated blocks, and verify that all memory is properly accounted for. See chapter 17 of the 3ep book for suggestions.

  4. Make the fork system call in xv6 use copy-on-write. You will do this in two parts:

    1. For the pre-spring break checkpoint, you need to implement the following:

      • Change fork so that it does not copy userspace memory frames, but instead duplicates only the page tables and page directory. Update page tables for parent and child process to mark shared pages as read only
      • Detect and report an attempt to write to one of these read-only pages

      You may find it easier to write this as a new system call called “vfork”, since otherwise it will be challenging to test.

      Before spring break, you should be prepared to demonstrate your code and show how you have tested it.

    2. For this part, you should have a complete, working implementation of copy-on-write forks. If you wrote it as a separate system call initially, you should finish by replacing the old version of fork with your new implementation.

      For this part, you will need to handle attempts to write to a shared page. You will need to make a copy of the page, rewrite the affected page table entry to refer to it, and have the process retry the failed instruction.

      When you copy a page, you should mark the old page as writable for the other process if it is the last process with access to the page. If more than one process still has a reference to it, it should remain read only.

      For each userspace page that is shared between multiple processes, you must keep a reference count that tracks how many processes have access to the page. You can use either of these approaches:

      Use the 3 available bits in the PTE to act as a reference count. When this count reaches its limit, future forks should just copy the page immediately (as it worked before you started this project). Note that each process that refers to the page must maintain the same reference count, so whenever it is changed you must find all affected processes and update their page tables. It is okay to simply scan the entire list of processes and update them. Allocate memory somewhere else to maintain a list of reference counts. This requires extra memory management, but if you index it by physical frame number, you only need to maintain a single reference count per frame. When the reference count reaches 1, you will still need to find the last process that shares the page and set its entry to be writable. For this part, you should have a complete, working implementation of copy-on-write forks. If you wrote it as a separate system call initially, you should finish by replacing the old version of fork with your new implementation.

  5. Add two new schedulers to xv6: a random scheduler and a multi-level feedback queue scheduler. You should also make it possible to switch schedulers.

    Start with the random scheduler. It should function just like the existing round-robin scheduler, but instead of running processes in a strict order, it should randomly select one of the runnable processes each time the scheduler is called.

    You will need to implement a pseudo-random number generator. Have a look around—there are plenty of simple generators to be found.

    Add a mechanism to select which scheduler runs. The scheduler can be selected using a compile-time constant, but it should not require commenting out code or renaming functions to switch schedulers. Write userspace test code to test your new scheduler and compare it with the original scheduler. Can you reliably detect which scheduler is running?

    Next, move on to the multi-level feedback queue scheduler. Implement the version describe in the text. In addition to the policy changes, you will need to update the mechanism to allow for variable-length time slices. Search for “yield” in trap.c to find where processes are forced to give up the CPU.

    In addition to implementing the MLFQ scheduler, you must design userspace tests to show that it works, and to demonstrate a situation where it improves the usability of the system.

Last Updated 11/06/2017