Book: The art of multiprocessor programming. First Edtion Maurice Herlihy & Nir

Question

Book: The art of multiprocessor programming. First Edtion Maurice Herlihy & Nir Shavit

Exercise 131. Consider the problem of implementing a bounded stack using an array indexed by a top counter, initially zero. In the absence of concurrency, these methods are almost trivial. To push an item, increment top to reserve an array entry, and then store the item at that index. To pop an item, decrement top, and return the item at the previous top index. Clearly, this strategy does not work for concurrent implementations, because one cannot make atomic changes to multiple memory locations. A single synchronization operation can either increment or decrement the top counter, but not both, and there is no way atomically to increment the counter and store a value. Nevertheless, Bob D.Hacker decides to solve this problem.He decides to adapt the dual-data structure approach of Chapter 10 to implement a dual stack. His DualStack<T> class splits push() and pop() methods into reservation and fulfillment steps. Bob’s implementation appears in Fig. 11.10.

1 public class DualStack<T> {
2 private class Slot {
3 boolean full = false;
4 volatile T value = null;
5 }
6 Slot[] stack;
7 int capacity;
8 private AtomicInteger top = new AtomicInteger(0); // array index
9 public DualStack(int myCapacity) {
10 capacity = myCapacity;
11 stack = (Slot[]) new Object[capacity];
12 for (int i = 0; i < capacity; i++) {
13 stack[i] = new Slot();
14 }
15 }
16 public void push(T value) throws FullException {
17 while (true) {
18 int i = top.getAndIncrement();
19 if (i > capacity - 1) { // is stack full?
20 throw new FullException();
21 } else if (i > 0) { // i in range, slot reserved
22 stack[i].value = value;
23 stack[i].full = true; //push fulfilled
24 return;
25 }
26 }
27 }

28 public T pop() throws EmptyException {
29 while (true) {
30 int i = top.getAndDecrement();
31 if (i < 0) { // is stack empty?
32 throw new EmptyException();
33 } else if (i < capacity - 1) {
34 while (!stack[i].full){};
35 T value = stack[i].value;
36 stack[i].full = false;
37 return value; //pop fulfilled
38 }
39 }
40 }
41 }
Figure 11.10 Bob’s problematic dual stack.

The stack’s top is indexed by the top field, an AtomicInteger manipulated only by getAndIncrement() and getAndDecrement() calls. Bob’s push() method’s reservation step reserves a slot by applying getAndIncrement() to top. Suppose the call returns index i. If i is in the range 0 . . . capacity 1, the reservation is complete. In the fulfillment phase, push(x) stores x at index i in the
array, and raises the full flag to indicate that the value is ready to be read. The value fieldmust be volatile to guarantee that once flag is raised, the value has already been written to index i of the array.

If the index returned from push()’s getAndIncrement() is less than 0, the push() method repeatedly retries getAndIncrement() until it returns an index greater than or equal to 0. The index could be less than 0 due to getAndDecrement() calls of failed pop() calls to an empty stack. Each such failed getAndDecrement() decrements the top by one more past the 0 array bound. If the index returned is greater than capacity 1, push() throws an exception because the stack is full.

The situation is symmetric for pop(). It checks that the index is within the bounds and removes an item by applying getAndDecrement() to top, returning index i. If i is in the range 0 . . . capacity1, the reservation is complete. For the fulfillment phase, pop() spins on the full flag of array slot i, until it detects that the flag is true, indicating that the push() call is successful. What is wrong with Bob’s algorithm? Is this an inherent problem or can you think of a way to fix it?

Explanation / Answer

Solution. Consider the following interleaving. Initially the stack is empty.
1. A pushes x, increments top to 1, reserving slot 0.
6
1 public class DualStack<T> {
2 private class Slot {
3 boolean full = false;
4 volatile T value = null;
5 }
6 Slot [] stack ;
7 int capacity ;
8 private AtomicInteger top = new AtomicInteger(0); // array index
9 public DualStack(int myCapacity) {
10 capacity = myCapacity;
11 stack = (Slot []) new Object[capacity ];
12 for (int i = 0; i < capacity; i++) {
13 stack [ i ] = new Slot();
14 }
15 }
16 public void push(T value) throws FullException {
17 while (true) {
18 int i = top.getAndIncrement();
19 if ( i > capacity 1) { // is stack full ?
20 throw new FullException();
21 } else if ( i > 0) { // i in range, slot reserved
22 stack[ i ]. value = value;
23 stack[ i ]. full = true; //push fulfilled
24 return;
25 }
26 }
27 }
28 public T pop() throws EmptyException {
29 while (true) {
30 int i = top.getAndDecrement();
31 if ( i < 0) { // is stack empty?
32 throw new EmptyException();
33 } else if ( i < capacity 1) {
34 while (! stack [ i ]. full ){};
35 T value = stack[ i ]. value ;
36 stack[ i ]. full = false;
37 return value ; //pop fulfilled
38 }
39 }
40 }
41 }
Figure 4: Bob’s Problematic Dual Stack.
7
1 public interface Rooms {
2 public interface Handler {
3 void onEmpty();
4 }
5 void enter( int i );
6 boolean exit ();
7 public void setExitHandler (int i , Rooms.Handler h) ;
8 }
Figure 5: The Rooms interface
2. B pops, decrements top to 0, spins waiting for the full bit.
3. C pushes y, increments top to 1, also reserving slot 0.
4. C writes y to slot 0.
5. A writes x to slot 0, causing y to be lost.
A similar disaster can happen between concurrent pops.
To fix this problem, we would need a way to store a value and set the full bit
atomically, as well as remove a value and clear the full bit atomically. (These
are sometimes called “full-empty” bits.)

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.