Book Errata
- Page 33
bottom.
- Each time a one-point crossover operation is performed
the crossover point is chosen randomly.
- Page 54.
- ``If a thread in the running state calls its yield method
it gives up the CPU and is put back in the runnable set
in the runnable state.''
Even if several threads are runnable
there is no guarantee that the next thread to run on the CPU is
not the one that just yielded.
- Page 55.
- ``The Java thread scheduler ensures that the highest priority
runnable thread (or one of them if there are several)
is running on the CPU.''
This is not accurate.
According to page 415 of The Java Language Specification [21]
the scheduler usually ensures this
but it is not guaranteed that the
highest priority thread is always executing on the CPU.
- Page 57.
- Thus Library Class 3.2 (Scheduler)
does not guarantee time slicing
but it works in practice.
- Page 79.
- Change ``But it does allow starvation in the presence of contention''
to ``It also does not allow starvation in the presence of contention.''
- Page 79.
- Delete ``In contrast to Dekker's solution
''
- Page 81.
- Change the right-most entry in Table 3.2's line for Dekker's algorithm
from ``no'' to ``yes.''
- Page 87
Exercise 6.
- Change ``Show how starvation in the presence of contention might occur
in Dekker's solution.'' to ``Show that starvation in the presence of
contention does not occur in Dekker's solution even if one thread
executes on a fast CPU and the other thread on a slow CPU ([25] page 25
is in error).''
- Page 90.
- The producer and consumer code using shared binary semaphores does
illustrate a delay/wakeup without the race condition described in
Section 3.5.4 on page 83. However
the page 90 code still has many
race conditions and bugs. Finding and fixing them makes a good exercise.
- Pages 106
121.
- The commands to induce starvation should be (change -n5 to
-p5)
javac dphi.java dpdr.java
java DiningPhilosophers -p5 -R300 1 100 10 1 1 100 100 1 100 1
- Page 119.
- Exercise 0. Fix the Remaining Bugs.
Find and fix the bugs and race conditions remaining in the producer
and consumer shared binary semaphore code on page 90.
- Page 128.
- Exercise 18. Fix Another Bug.
Although the code on page 114 fixes the scheduling flaw
it has a race
condition rendering it incorrect. The race condition can be fixed by
adding if (wakeup == 1) after wakeup++ and before
V(blocked) in the up() method. Devise a sequence
of events illustrating this race condition and verify the fix.
(David Hemmendinger
``Comments on `A Correct and Unrestrictive
Implementation of General Semaphores' (by Kearns)'
'' ACM Operating
Systems Review
Vol. 23
No. 1
1989.)
- Page 135.
- If several threads are blocked
waiting to acquire the lock on
an object that is currently held by some other thread
there is no guarantee that the thread waiting the longest will be
the next one to acquire the lock when it is released.
- Page 137
top.
- A notify() removes an arbitrary thread from the wait set
if there is one. The thread must reacquire the monitor lock and therefore
competes with all other threads trying to acquire the monitor lock
having called a synchronized method
or reacquire the monitor
lock
having been notified. Thus the notified thread is not necessarily
in the runnable (ready) set
but might still be blocked.
- Pages 139--140 and 391.
- Class 5.7.
There is a race condition in this platoon-based monitor for the
starvation-free database readers and writers problem. Suppose several
readers are currently reading the database. Then
suppose several
writers arrive and wait. Next
suppose several more readers arrive and
wait due to the waiting writers. Then
suppose the currently reading
readers all finish and exit the database. One of the waiting writers
now writes the database. When it finishes
all waiting readers that
arrived before it finished writing are to enter the database next.
However
if one of those readers enters and exits the database before
any of the other readers enters
then one of the waiting writers and
one of the remaining readers can enter the database at the same time
possible corrupting it.
- Page 166.
- Exercise 27. Fix Class 5.7.
Fix the platooning so that when a writer finishes writing all waiting
readers that arrived before it finished writing are allowed into the
database before another writer is allowed to enter.
- Page 393.
- Library Class 5.1.
The interrupt/notify race condition is still present. Suppose several
threads are blocked in wait() inside P(). Next
suppose
one is notified by a thread calling V(). The notified thread
is removed from the wait set and now needs to reacquire the monitor lock
in order to continue execution in the monitor. Now suppose the notified
thread is interrupted before reacquiring the monitor lock. An
InterruptedException exception is thrown and the thread executes
its catch block when it reacquires the monitor lock. However
value is less than zero
so the thread does another wait
and the notify is lost.
- Page 399.
- Class 5.9.
A similar problem to Library Class 5.1 on page 393.
SJH
shartley@mcs.drexel.edu
Permission is granted to copy and distribute this material for
educational purposes only, provided that the following credit line
is included: "Concurrent Programming using Java, Copyright 1997 Stephen
J. Hartley." Permission is granted to alter and distribute this material
provided that the following credit line is included: "Adapted from
Concurrent Programming using Java, Copyright 1997 Stephen J. Hartley."