CS 3400: Operating Systems

Fall 2018 Topics Project Reading
Aug 20–24 introduction, os structure building and running xv6 3ep intro, xv6 ch 0
Aug 27–31 concurrency reproduce graphs from ch 29 3ep ch 25–30, xv6 ch 4
Sep 3–7 (Labor Day) semaphores, bugs, event loops 3ep ch 31–34
Sep 10–14 pc hardware, boot sequence sharks and divers xv6 appendix a, b
Sep 17–21 processes and address spaces 3ep ch 3–5, xv6 ch 1
Sep 24–28 virtual memory 3ep ch 12–15, xv6 ch 2
Oct 1–5 page replacement malloc and free 3ep ch 16–24
Oct 8–12 (Fall break) interrupts and system calls xv6 ch 3
Oct 15–19 copy-on-write fork, part 1
Oct 22–26
Oct 29–Nov 2 scheduling copy-on-write fork, part 2 3ep ch 6–7, xv6 ch 5
Nov 5–9 3ep ch 8–11
Nov 12–16 file systems 3ep ch 35–38, xv6 ch 6
Nov 19–23 (Thanksgiving) recovery, RAID random scheduler 3ep ch 39–43, 37
Nov 26–30 distributed file systems MLFQ scheduler 3ep ch 44–47
Dec 3–7 virtualization

Changes to the schedule 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.


Resourses

Assignments

  1. Reproduce the 3 graphs from 3ep ch 29. 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 exercises 2 and 3 from Chapter 4 of the xv6 commentary, and 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 first checkpoint, you should write a detailed implementation plan that you will present to the class. You should describe:

      • What will happen at fork time to give both the parent and the child page their own page tables but use the same memory.
      • How you will track how many processes currently reference a single read-only page
      • What sequence of events happens when a page fault occurs
      • How and when you will convert a read-only page into a writeable page, and how and when you will copy a read-only page to create a new writable copy.
      • What happens when a process exits.

      You should be prepared to walk through the various use cases that will exercise this code, and talk about the precise modifications to xv6 that will be necessary.

      Here are writeups from other courses with a similar project:

    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.

  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 10/08/2018