Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

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

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.

image

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.

Step by Step Solution

3.48 Rating (141 Votes )

There are 3 Steps involved in it

Step: 1

The code provided in Figure 1110 is an implementation of a DualStack class which aims to provide a c... blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Microeconomics An Intuitive Approach with Calculus

Authors: Thomas Nechyba

1st edition

538453257, 978-0538453257

More Books

Students also viewed these Programming questions