Consider the unbounded queue implementation shown in Fig. 10.21. This queue is blocking, meaning that the deq () method does not return until it has found an item to dequeu

 

The queue has two fields: items is a very large array, and tail is the index of the next unused element in the array.

1. Are the enq () and deq () methods wait-free? If not, are they lock-free? Explain.

2. Identify the linearization points for enq () and deq(). (Careful! They may be execution-dependent.)

Transcribed Image Text:

1 public class HWQueue<T> ( 2 AtomicReference<T>[] items; Atomic Integer tail; 3 4 5 6 7 public void enq (T x) { int i = tail.getAnd Increment (); items [1].set(x); } public T deq () ( while (true) { int range tail.get(); for (int i = 0; i < range; i++) { T value items [1].getAndSet (null); if (value != null) { return value; 8 9 10 11 12 13 14 15 16 17 18. 19 20 } Figure 10.21 Queue used in Exercise 125. 1 public class HWQueue<T> ( 2 AtomicReference<T>[] items; Atomic Integer tail; 3 4 5 6 7 public void enq (T x) { int i = tail.getAnd Increment (); items [1].set(x); } public T deq () ( while (true) { int range tail.get(); for (int i = 0; i < range; i++) { T value items [1].getAndSet (null); if (value != null) { return value; 8 9 10 11 12 13 14 15 16 17 18. 19 20 } Figure 10.21 Queue used in Exercise 125.

Answer rating: 100% (QA)

Lets analyze the provided queue implementation Waitfree or lockfree The enq method increments the ta... View the full answer