CS 3400: Operating Systems

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

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 book, our guide to the xv6 operating system source code.

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 or a spreadsheet.

  2. 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 a new scheduler to xv6/modify the existing scheduled to support priorities.

    Processes will need a way to switch between a small set of fixed priority levels. The scheduler should round-robin between processes in the highest priority level with tasks ready to run. It should only move to a lower priority level when no processes are ready to run at a higher priority level.

    In addition to implementing the scheduler, you must design userspace tests to show that it works.

Presentations

Last Updated 12/08/2020