Priority Queues

Prev: Skiplists and balanced search Next: Scheduling and work distribution

Exercises

Exercise 15.1. Give an example of a quiescently consistent priority queue execution that is not linearizable.

---

Exercise 15.2. Implement a quiescently consistent Counter with a lock-free implementation of the boundedGetAndIncrement() and boundedGetAndDecrement() methods using a counting network or diffracting tree.

---

Exercise 15.3. In the SimpleTree algorithm, what would happen if we replace the boundedGetAndDecrement() method with a regular getAndDecrement()?

---

Exercise 15.4. Use boundedGetAndIncrement() methods in TreeNode counters to devise a SimpleTree algorithm with bounded capacity.

---

Exercise 15.5. In the SimpleTree class, what would happen if add(), after placing an item in the appropriate Bin, incremented counters in the same top-down manner as in the removeMin() method? Give a detailed example.

---

Exercise 15.6. Prove that the SimpleTree is a quiescently consistent priority queue implementation.

---

Exercise 15.7. Modify FineGrainedHeap to allocate new heap nodes dynamically. What are the performance limitations of this approach?

---

Exercise 15.8. Fig. 15.16 shows a bit-reversed counter. We could use the bit-reversed counter to manage the next field of the FineGrainedHeap class. Prove the following: For any two consecutive insertions, the two paths from the leaves to the root have no common nodes other than the root. Why is this a useful property for the FineGrainedHeap?

public class BitReversedCounter {
  int counter, reverse, highBit;
 
  BitReversedCounter(int initialValue) {
    counter = initialValue;
    reverse = 0;
    highBit = -1;
  }
 
  public int reverseIncrement() {
    if (counter++ == 0) {
      reverse = highBit = 1;
      return reverse;
    }
    int bit = highBit >> 1;
    while (bit != 0) {
      reverse ^= bit;
      if ((reverse & bit) != 0) break;
      bit >>= 1;
    }
    if (bit == 0)
      reverse = highBit <<= 1;
    return reverse;
  }
 
  public int reverseDecrement() {
    counter--;
    int bit = highBit >> 1;
    while (bit != 0) {
      reverse ^= bit;
      if ((reverse & bit) == 0) {
        break;
      }
      bit >>= 1;
    }
    if (bit == 0) {
      reverse = counter;
      highBit >>= 1;
    }
    return reverse;
  }
}

---

Exercise 15.9. Provide code for PrioritySkipList’s add() and remove() methods.

---

Exercise 15.10. The PrioritySkipList class used in this chapter is based on the LockFreeSkipList class. Write a PrioritySkipList class based on the LazySkipList class.

---

Exercise 15.11. Describe a scenario in the SkipQueue implementation in which contention would arise from multiple concurrent removeMin() method calls.

---

Exercise 15.12. The SkipQueue class is quiescently consistent but not linearizable. Here is one way to make this class linearizable by adding a simple timestamping mechanism. After a node is completely inserted into the SkipQueue, it acquires a timestamp. A thread performing a removeMin() notes the time at which it starts its traversal of the lower level of the SkipQueue, and only considers nodes whose timestamp is earlier than the time at which it started its traversal, effectively ignoring nodes inserted during its traversal. Implement this class and justify why it works.

Prev: Skiplists and balanced search Next: Scheduling and work distribution