11/3: Weensy Pipes

This exercise aims to teach you about one of the most important and powerful abstractions provided by modern operating system kernels, the pipe. You’ll implement a pipe inside a weensy kernel.

Check out the shell1x directory of your cs61-exercises repository (you’ll need to pull first). This weensy kernel runs two processes, p-pipewriter and p-pipereader, with a “pipe” between them. The pipewriter repeatedly writes a message into the pipe, prints it, then waits for 1–3 seconds. The pipereader repeatedly reads a line from the pipe and prints it.

Currently, though, the weensy pipe is very expensive. In one run it took 13,844 system calls to write the message “I am a plumber.”! Your goal in this exercise is to make the weensy OS pipe more efficient: it should take fewer system calls to write and fewer system calls to read.

Part 0

Look at the code and understand how it works.

Note: As in the memory-mapped weensy exercise, this weensy OS has kernel isolation (the kernel’s memory is protected from processes by the page table), but not full process isolation (all processes share the same page table, kernel_pagetable).

Test your understanding: Answer Part 0’s survey questions!

In the rest of this exercise, you’ll reduce the overhead of the weensy pipe using different techniques.

Part 1: Scheduling

First, change how the WeensyOS kernel schedules its processes. Specifically, if a system call made by process P can’t do useful work until some other process runs, then the kernel should probably not run P again (it should run some other process).

Using this simple technique, you can reduce the number of system calls made by p-pipewriter to close to the minimum (say, no more than 4x the minimum).

Answer Part 1’s survey questions!

Part 2: Buffer size

Second, change the size of the WeensyOS kernel’s pipe buffer, and change the system call handlers in exception accordingly.

Using this simple technique, you can reduce the number of system calls made by p-pipewriter to 1 per message. But be careful: your code should handle all cases (e.g., writing into a partially-full buffer, writing data larger than the buffer, reading N characters from a buffer containing M characters where M > N, etc.).

Answer Part 2’s survey questions!

Part 3: Blocking

Finally, change the WeensyOS kernel so that a reader blocks when it tries to read from an empty pipe, rather than polling from the empty pipe. (A process is blocked if it is not scheduled until some condition changes. This means it doesn’t occupy the CPU, leaving more time for other processes—and wasting less energy.) The reader should be woken up only when the buffer has characters to read. Use process state P_BLOCKED to represent “blocked on reading pipe.”

Using this simple technique, you can reduce the number of system calls made by p-pipereader to roughly 2 per message!

Answer Part 3’s survey questions!

Optional advanced work

This exercise touches on several big ideas in operating systems design, with respect to both performance (scheduling, blocking vs. polling) and convenience (the pipe abstraction). Here’s how to go further.