Projects

As an extra-credit/makeup opportunity, you may complete a substantial individual systems programming task, either from the menu of options below or (if we approve) of your own choosing. You’ll turn in your code, and then we’ll interview you about it one-on-one. We’ll assign extra credit based on a combination of your understanding of your own code and that code’s quality (e.g., ambition, performance, correctness, completeness). We will also hold a little project day on Wednesday 12/9 (the day before the final) where you can present your project to classmates if you want. (We’ll bring food.)

If you choose to do a project, you must:

  1. Tell us by 11/10 that you are planning to do a project.

    • Create a directory called project/ in your cs61-psets directory.
    • Create and fill out project/README.md to briefly describe your project.
    • Click “Grade this commit” on the “project” entry on the grading server.

    If your project is not in the list below, you then need to meet with Eddie to get approval.

  2. Turn in your project code by end of reading period (also via the grading server).

  3. Be in town until at least Tuesday 12/15 to schedule the one-on-one interview. (Attendance at project day is encouraged, but not required.)

As is true for all coding assignments in this class, you are allowed to use AI. However, we will evaluate your project based on your understanding of the code. If you can’t explain the code during the one-on-one interview, you will not get credit. We encourage you to implement your project yourself: ask the AI assistant questions, but come up with the code yourself.

Your project should be tested and not just written. You will turn in your tests as well as your code.

We cannot be specific about how much credit an average project will earn, but an excellent project, coupled with an excellent interview, will be enough to turn a B+ into an A-.

Below, we list some pre-approved projects based on previous problem sets. A strong implementation of any of these projects could be excellent.

Problem set 1

Fast allocator: Implement O(1) memory allocation (or O(log N) memory allocation), for at least some classes of allocation.

Your current implementation likely walks over all freed allocations, or all total allocations, to find free blocks, and thus likely has computational complexity O(F) or O(N) (where F is the number of free blocks and N is the number of bytes of memory in the allocation buffer). There are many algorithms with higher performance, including:

You don’t have to implement a concurrent allocator, but an allocator with concurrency support (i.e., a multithreaded allocator) would earn additional difficulty points as long as you test it well!

Allocator visualization: A student suggested a visualizer for the M61 allocator, inspired by the WeensyOS memory display. This could be a fun project, but to make it substantive, make sure the display is informative and build tests that stress it (many of the torture tests run quickly and/or make few allocations, and so are uninteresting to visualize).

Problem set 2

A new bomb framework: Your binary bombs are built from a framework that chooses random phases from a collection of phase templates, parameterizes them with random constants, and compiles them into machine code. Build your own framework with your own phases. We’ll look for creative, but solvable, phases and code quality of the framework and harness that selects phases. (Over the years we have written many bomb phases ourselves and some of them were too difficult for humans to solve :) )

Problem set 3

Copy-on-write fork: The copy-on-write technique allows multiple processes to share writable memory. This would normally violate process isolation, since one process could see the other’s writes. The key to safe sharing is to share the memory read-only. This will mean that any write attempt causes a page fault. The kernel’s page fault handler then:

  1. Verifies that the write attempt was to a copy-on-write page.
  2. Allocates a new physical page and copies the read-only page’s data there. This new page is isolated—no other process can see it.
  3. Maps the new page in place of the read-only page, but maps it read-write.
  4. Restarts the instruction that attempted the write.

This effectively creates isolation lazily, on demand! It’s a neat way to save memory and speed up fork.

But a full implementation isn’t trivial and requires some design. For instance:

Advanced virtual memory management techniques: One of the great operating systems research works of the 21st century is “Memory Resource Management in VMware ESX Server”, by Carl A. Waldspurger. The paper is relatively clear and contains a ton of fun hacks. Transparent page sharing and content-based page sharing could be implemented by a WeensyOS kernel.

Pipes: Implement a true sys_pipe system call that creates a pipe abstraction, and sys_read and sys_write system calls that access pipes by file descriptor number. Include file descriptor table cloning on fork; closing on exit or other termination; blocking (by sys_read on empty pipes, and by sys_write on full ones) with automatic wakeup; and end-of-file detection.

More (check with Eddie): WeensyOS lacks many other features of production operating systems, and adding those features would be a strong project, though sometimes quite difficult. For instance, you could implement a version of Linux containers, which are capable of restricting the number of processes one process can fork; or system call restrictions, by which a process can restrict the system calls it’s allowed to make in future.

Problem set 4

Shell functions and control structures: In your problem set, you implemented a small subset of the shell programming language. Real shells support complex control structures including if, case, while, and for, and allow users to write shell functions—a collection of command lines that behaves like a command. For instance, here is a shell function that executes a command with encouragement:

encourage () {
	echo "Come on, $1, I know you can do it"
	echo "Let's goooooooooo"
	"$@"
	echo "Good job!"
}

Here’s how that function works in practice:

$ echo Ho hum
Ho hum
$ encourage echo Ho hum
Come on, echo, I know you can do it
Let's goooooooooo
Ho hum
Good job!

Like any command, shell function commands have an exit status, can be redirected, can be put in pipelines, and so forth.

Implement shell functions, either based on the Unix sh syntax (tutorial, reference) or some other syntax of your choice. Your implementation should support at least if-type and while-type constructions as well as functions.

Other shell features: Real shells have many other features, including configurable prompts, arithmetic, variables, filename expansion (check out zsh’s extensive expansion types), and more. A collection of features could be a good project. (A pedestrian implementation of a single feature—say, simple variable expansion only—might not reach the substantiveness bar.)

Problem set 5

Performance requires benchmarks, so for stdio projects specifically, make sure you write new tests and workloads that exercise your work and demonstrate actual performance differences from a simple baseline. Our two project ideas involve new caching algorithms that could outperform a simple stdio cache for some workloads, but as with the pset, it’s important that your cache continue to behave correctly for any workload.

Learning cache: Implement a cache that can successfully learn unusual access patterns and improve its performance. You’ll need to implement programs that have unusual access patterns and then show that your learning cache outperforms a well-engineered default cache.

Segcache or S3-FIFO in stdio: Implement Prof. Juncheng Yang’s segcache work, or his S3-FIFO cache eviction algorithm, in the context of stdio. This will require an initial step where you map the segcache/S3-FIFO workloads onto stdio workloads; for instance, you could say that the “small objects” considered in segcache/S3-FIFO correspond to subsegments of a large file.