Queues, memory management, and the ABA problem

Prev: Linked lists: the role of locking Next: Stacks and elimination

Exercises

Exercise 10.1. Change the SynchronousDualQueue<T> class to work correctly with null items.

---

Exercise 10.2. Consider the queue presented below, a variant of the simple lock-free queue for a single enqueuer and a single dequeuer described in Chapter 3. This queue is blocking; that is, removing an item from an empty queue, or adding an item to a full one, causes the threads to spin. Surprisingly, this queue requires only loads and stores, and not a more powerful read-modify-write synchronization operation.

Does the queue implementation, however, require the use of a memory barrier? If so, where in the code is such a barrier needed and why? If not, explain why not.

class TwoThreadLockFreeQueue<T> {
  int head = 0, tail = 0;
  T[] items;
 
  public TwoThreadLockFreeQueue(int capacity) {
    head = 0;
    tail = 0;
    items = (T[]) new Object[capacity];
  }
 
  public void enq(T x) {
    while (tail - head == items.length) {}
    items[tail % items.length] = x;
    tail++;
  }
 
  public Object deq() {
    while (tail - head == 0) {}
    Object x = items[head % items.length];
    head++;
    return x;
  }
}

---

Exercise 10.3. Design a bounded lock-based queue implementation using an array instead of a linked list.

1. Allow parallelism by using two separate locks for head and tail.
2. Try to transform your algorithm to be lock-free. Where do you run into difficulty?

---

Exercise 10.4. In the deq() method of the unbounded lock-based queue, Fig. 10.8, is it necessary to hold the lock when checking that the queue is not empty? Explain.

---

Exercise 10.5. In Dante’s Inferno, he describes a visit to Hell. In a recently discovered chapter, he encounters five people sitting at a table with a pot of stew in the middle. Although each one holds a spoon that reaches the pot, each spoon’s handle is much longer than each person’s arm, so no one can feed him- or herself. They are famished and desperate.

Dante then suggests: “Why do you not feed one another?”

The rest of the chapter is lost.

1. Write an algorithm to allow these unfortunates to feed one another. Two or more people may not feed the same person at the same time. Your algorithm must be, well, starvation-free.
2. Discuss the advantages and disadvantages of your algorithm. Is it centralized or decentralized, high or low in contention, and deterministic or randomized?

---

Exercise 10.6. Consider the linearization points of the enq() and deq() methods of the lock-free queue in Figs. 10.11 and 10.12.

1. Can we choose the point at which the returned value is read from a node as the linearization point of a successful deq()? Explain.
2. Can we choose the linearization point of the enq() method to be the point at which the tail field is updated, possibly by other threads? Explain.

---

Exercise 10.7. Consider the unbounded queue implementation shown below. This queue is blocking, meaning that the deq() method does not return until it has found an item to dequeue.

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

public class HWQueue<T> {
  AtomicReference<T>[] items;
  AtomicInteger tail;
  ...
 
  public void enq(T x) {
    int i = tail.getAndIncrement();
    items[i].set(x);
  }
 
  public T deq() {
    while (true) {
      int range = tail.get();
      for (int i = 0; i < range; i++) {
        T value = items[i].getAndSet(null);
        if (value != null) {
          return value;
        }
      }
    }
  }
}

1. Are the enq() and deq() methods wait-free? If not, are they lock-free? Explain.
2. Identify linearization points for the enq() and deq() methods. Careful: they may be execution-dependent.

Prev: Linked lists: the role of locking Next: Stacks and elimination