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."