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 singlesynchronization 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 class splits push () and pop () methods into reservation and fulfil-ment steps. Bob’s implementation appears in Fig. 11.10.

Transcribed Image Text:

1 public class DualStack { private class Slot { boolean full false; volatile T value null; 123 4 5 6 7 8 private AtomicInteger top = new AtomicInteger (0); // array index public DualStack(int myCapacity) { 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 } Slot [] stack; int capacity; } capacity myCapacity; stack (Slot[]) new Object [capacity]; for (int i = 0; i < capacity; i++) { stack [1] = new Slot (); } public void push(T value) throws FullException { while (true) { int i top.getAnd Increment (); if (i > capacity - 1) { // is stack full? throw new FullException(); } else if (1 > 0) {// iin range, slot reserved stack [1].value= value; stack [1]. full = true; //push fulfilled return; } public T pop () throws EmptyException { while (true) { int i = top.getAnd Decrement (); if (i < 0) { // is stack empty? throw new EmptyException (); } else if (i < capacity 1) { while (!stack[i].full) {}; T value= stack[1].value; stack[i].full = false; return value; //pop fulfilled Figure 11.10 Bob's problematic dual stack. 1 public class DualStack { private class Slot { boolean full false; volatile T value null; 123 4 5 6 7 8 private AtomicInteger top = new AtomicInteger (0); // array index public DualStack(int myCapacity) { 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 } Slot [] stack; int capacity; } capacity myCapacity; stack (Slot[]) new Object [capacity]; for (int i = 0; i < capacity; i++) { stack [1] = new Slot (); } public void push(T value) throws FullException { while (true) { int i top.getAnd Increment (); if (i > capacity - 1) { // is stack full? throw new FullException(); } else if (1 > 0) {// iin range, slot reserved stack [1].value= value; stack [1]. full = true; //push fulfilled return; } public T pop () throws EmptyException { while (true) { int i = top.getAnd Decrement (); if (i < 0) { // is stack empty? throw new EmptyException (); } else if (i < capacity 1) { while (!stack[i].full) {}; T value= stack[1].value; stack[i].full = false; return value; //pop fulfilled Figure 11.10 Bob's problematic dual stack.