Subject:Conccurrency The question is from the book called \"The art of multiproc
ID: 664498 • Letter: S
Question
Subject:Conccurrency
The question is from the book called "The art of multiprocessor programming"
chapter 10,
Exercise 125. 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 dequeue.
1 public class HWQueue<T> {
2 AtomicReference<T>[] items;
3 AtomicInteger tail;
4 ...
5 public void enq(T x) {
6 int i = tail.getAndIncrement();
7 items[i].set(x);
8 }
9 public T deq() {
10 while (true) {
11 int range = tail.get();
12 for (int i = 0; i < range; i++) {
13 T value = items[i].getAndSet(null);
14 if (value != null) {
15 return value;
16 }
17 }
18 }
19 }
20 }
Figure 10.21 Queue used in Exercise 125.
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.)
Explanation / Answer
Answer:
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.)