We assume you are familiar with the thread abstraction and the primitives for thread sysnchronization from CS31a. Concurrency is important and complicated 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 reading 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.
Read S&K Chapter 4, Section 1 and 2 on enforcing modularity with clients and servers.
In preparation of this meeting, read the paper on the X window
system (reading #5). The X window system was developed at MIT and is used
all over the world (including at Brandeis). X is an excellent example of
a well-designed
system and demonstrates many of the system organization topics we will discuss
in CS 146a.
For this reading we ask you to do TWO things, complete
a hands-on assignment and create a prezi answering the following
question:
How did the designers of X use modularity, abstraction, hierarchy, and layering to manage the complexity of their graphics system?
In the lecture we discuss the material on enforcing modularity with clients and servers from S&K Chapter 4 A+B. Please review.
System aphorism of the week
Everything should be made as simple as possible, but not simpler.
(A. Einstein)
CS 146a Assignment 2, issued 3/9/09