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)
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','' ACM Operating
Systems Review, Vol. 23, No. 1, 1989;
John A. Trono and William E. Taylor, ``Further Comments on
`A Correct and Unrestrictive Implementation of General Semaphores',''
ACM Operating Systems Review, Vol. 35, No. 3, 2000.)
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.