Subject:Concurrency The question is from the book called \"The art of multi proc
ID: 664531 • Letter: S
Question
Subject:Concurrency
The question is from the book called "The art of multi processor programming"
Chapter 10
Exercise 120. Consider the simple lock-free queue for a single enqueuer and a single
dequeuer, described earlier in Chapter 3. The queue is presented in Fig. 10.20.
1 class TwoThreadLockFreeQueue<T> {
2 int head = 0, tail = 0;
3 T[] items;
4 public TwoThreadLockFreeQueue(int capacity) {
5 head = 0; tail = 0;
6 items = (T[]) new Object[capacity];
7 }
8 public void enq(T x) {
9 while (tail - head == items.length) {};
10 items[tail % items.length] = x;
11 tail++;
12 }
13 public Object deq() {
14 while (tail - head == 0) {};
15 Object x = items[head % items.length];
16 head++;
17 return x;
18 }
19 }
Figure 10.20 A Lock-free FIFO queue with blocking semantics for a single enqueuer and single
dequeuer. The queue is implemented in an array. Initially the head and tail fields are equal
and the queue is empty. If the head and tail differ by capacity, then the queue is full. The
enq() method reads the head field, and if the queue is full, it repeatedly checks the head until
the queue is no longer full. It then stores the object in the array, and increments the tail
field. The deq() method works in a symmetric way.
This queue is blocking, that is, removing an item from an empty queue or
inserting an item to a full one causes the threads to block (spin). The surprising
thing about this queue is that it requires only loads and stores and not a more
powerful read–modify–write synchronization operation. Does it however require
the use of a memory barrier? If not, explain, and if so, where in the code is such a
barrier needed and why?
Explanation / Answer
Answer:
it doresnt require memory barrier.