The Art of Multiprocessor Programming
Including examples, models, exercises, and PowerPoint slides, this comprehensive book presents the principles and tools available for programming multiprocessor machines.
TABLE OF CONTENTS The Art of Multiprocessor Programming
Chapter 15: Priority Queues
15.1 Introduction
A priority queue is a multiset of items, where each item has an associated priority, a score that indicates its importance (by convention, smaller scores are more important, indicating a higher priority). A priority queue typically provides an add() method to add an item to the set, and a removeMin() method to remove and return the item of minimal score (highest priority). Priority queues appear everywhere from high-level applications to low-level operating system kernels.
A bounded-range priority queue is one where each item's score is taken from a discrete set of items, while an unbounded-range priority queue is one where scores are taken from a very large set, say 32-bit integers, or floating-point values. Not surprisingly, bounded-range priority queues are generally more efficient, but many applications require unbounded ranges. Fig. 15.1 shows the priority queue interface.
15.1.1 Concurrent Priority Queues
In a concurrent setting, where add() and removeMin() method calls can overlap, what does it mean for an item to be in the set?
Here, we consider two alternative consistency conditions, both introduced in Chapter 3. The first is linearizability, which requires that each method call appear to take effect at some instant between its invocation and its response. The second is quiescent consistency, a weaker condition that requires that in any execution, at any point, if no additional method calls are introduced, then when all pending method calls complete, the values they return are consistent with some...
Copyright Elsevier Inc. 2008 under license agreement with Books24x7
