We assume you are familiar with the material on threads and the abstractions and primitives for concurrency control from CS31a. Concurrency is a complicated and important topic. Many of the hard-to-find bugs in programs are concurrency bugs, since often they are hard to reproduce. Race condition, a concurrency bug, was behind one of the Therac-25 accidents.
The next reading on the topic of enforcing modularity is therefore "Eraser: A Dynamic Data Race Detector for Multithreaded Programs" (reading #7) that deals with methodology and system support for avoiding race conditions. If you read this paper sequentially, you might not reach all the important issues. Skim over the section describing the Lockset algorithm. After you understand the main concepts of the paper, return to the Lockset algorithm. We do not expect you to memorize this algorithm. Rather, we expect you to learn about dealing with synchronization issues.
In Figure 2 of the paper, remember that "y:=y+1" is not necessarily atomic. First, the processor loads the value of y into a register. Next, the processor increments the register value. Finally, the value is written back to y. Can you find interleavings which result in different values of y? For your convenience, here are some useful definitions:
The Eraser paper refers to "static detection" rather than "static prevention". In dynamic detection, a program will try to catch errors when they happen, but will halt execution when errors arise. In static prevention, a program will try to catch errors before they happen -- preventing errors from happening in the first place.
Your report should briefly address the following question:
The paper talks about the false positive and false negative answers provided by Eraser. What are they? Why do they happen? Contrast their respective dangers.
In the lecture we discuss the material on enforcing modularity with clients and servers from S&K Chapter 4 A+B. Please review.
One of the most unusual features of UNIX file system is special files that treat devices as files. List all the advantages of treating I/O devices this way.
System aphorism of the week
Everything should be made as simple as possible, but not simpler.
(A. Einstein)
CS 146a Assignment 3, issued 9/16/07