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

1 public class HWQueue ( 2 AtomicReference [] 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.