Information Technology Reference
In-Depth Information
Exercises
For convenience, the exercises from the body of the chapter are repeated here.
1. Show that solution 3 to the Too Much Milk problem is safe|that it guar-
antees that at most one roommate buys milk.
2. Precisely describe the set of possible outputs that could occur when the
program shown in Figure 5.5
is run.
3. Suppose that a programmer mistakenly creates an automatic (aka local)
variable v in one thread t1 and passes it to another thread t2. Is it possible
for a write by t1 to some variable other than v will change the state of v as
observed by t2? If so, explain how this can happen and give an example.
If not, explain why not.
4. Suppose that a programmer mistakenly creates an automatic (aka local)
variable v in one thread t1 and passes it to another thread t2. Is it possible
for a write by t2 to v will cause t2 to execute the wrong code? If so, so,
explain how. If not, explain why not.
5. Assuming Hansen semantics for condition variables, our implementation
of the blocking bounded queue in Figure 5.10 does not guarantee free-
dom from starvation: if a continuous stream of threads makes insert() (or
remove()) calls, it is possible for a waiting thread to wait forever. For
example, a thread may call
insert()
and wait in the
while(isFull())
loop; then, every time another thread calls
remove()
and signals on the
itemRemoved
condition variable, a different thread might call
insert()
,
see that the queue is not full, and insert an item before the waiting
thread resumes. Then, when the waiting thread resumes, it will retest
the
isFull()
predicate, see that the queue is full, and
wait()
.
Prove that under Hoare semantics and assuming that when a signal occurs,
it is the longest-waiting thread that is resumed, our implementation of
BBQ ensures freedom from starvation. That is, that if a thread waits in
insert()
, then it is guaranteed to proceed after a bounded number of
remove()
calls complete, and vice versa.
6. As noted in the previous problem, our implementation of the blocking
bounded queue in Figure 5.10 does not guarantee freedom from starvation.
Modify the code to ensure freedom from starvation so that if a thread waits
in
insert()
, then it is guaranteed to proceed after a bounded number of
remove()
calls complete, and vice versa. Note: Your implementation
must work under Hansen/Mesa semantics for condition variables.
