Concurrent Double-Ended Priority Queues

Double-ended priority queues (DEPQs) have several applications, including job scheduling and external sorting, while they are also used in computer graphics and other applications where elements might need to be accessed in a prioritized way from both ends. In concurrent environments, they can be implemented using existing concurrent implementations of balanced trees but with significant performance penalties due to the need for costly rebalancing. In this paper, we present FRX, a new concurrent DEPQ algorithm, which is inspired by sequential DEPQ techniques using dual structures and combines different synchronization techniques to avoid performance costs for all operations.