%0 Journal Article %1 1073770 %A Sundell, H\aakan %A Tsigas, Philippas %C Orlando, FL, USA %D 2005 %I Academic Press, Inc. %J J. Parallel Distrib. Comput. %K LockFree Me:ToRead %N 5 %P 609--627 %R 10.1016/j.jpdc.2004.12.005 %T Fast and lock-free concurrent priority queues for multi-thread systems %U http://portal.acm.org/citation.cfm?id=1073765.1073770&coll=Portal&dl=GUIDE&CFID=84819369&CFTOKEN=40932755 %V 65 %X We present an efficient and practical lock-free implementation of a concurrent priority queue that is suitable for both fully concurrent (large multi-processor) systems as well as pre-emptive (multi-process) systems. Many algorithms for concurrent priority queues are based on mutual exclusion. However, mutual exclusion causes blocking which has several drawbacks and degrades the overall performance of the system. Non-blocking algorithms avoid blocking, and several implementations have been proposed. Previously known non-blocking algorithms of priority queues did not perform well in practice because of their complexity, and they are often based on non-available atomic synchronization primitives. Our algorithm is based on the randomized sequential list structure called Skiplist, and a real-time extension of our algorithm is also described. In our performance evaluation we compare our algorithm with a well-representable set of earlier known implementations of priority queues. The experimental results clearly show that our lock-free implementation outperforms the other lock-based implementations in practical scenarios for 3 threads and more, both on fully concurrent as well as on pre-emptive systems.

@article{1073770, abstract = {We present an efficient and practical lock-free implementation of a concurrent priority queue that is suitable for both fully concurrent (large multi-processor) systems as well as pre-emptive (multi-process) systems. Many algorithms for concurrent priority queues are based on mutual exclusion. However, mutual exclusion causes blocking which has several drawbacks and degrades the overall performance of the system. Non-blocking algorithms avoid blocking, and several implementations have been proposed. Previously known non-blocking algorithms of priority queues did not perform well in practice because of their complexity, and they are often based on non-available atomic synchronization primitives. Our algorithm is based on the randomized sequential list structure called Skiplist, and a real-time extension of our algorithm is also described. In our performance evaluation we compare our algorithm with a well-representable set of earlier known implementations of priority queues. The experimental results clearly show that our lock-free implementation outperforms the other lock-based implementations in practical scenarios for 3 threads and more, both on fully concurrent as well as on pre-emptive systems.}, added-at = {2010-04-05T13:10:58.000+0200}, address = {Orlando, FL, USA}, author = {Sundell, H{\aa}kan and Tsigas, Philippas}, biburl = {https://www.bibsonomy.org/bibtex/2edefd2a0758ec8ba4dd7f96c0ef8eacb/gron}, description = {Fast and lock-free concurrent priority queues for multi-thread systems}, doi = {10.1016/j.jpdc.2004.12.005}, interhash = {f7b81a1f37fa0832c58b1a701692ede3}, intrahash = {edefd2a0758ec8ba4dd7f96c0ef8eacb}, issn = {0743-7315}, journal = {J. Parallel Distrib. Comput.}, keywords = {LockFree Me:ToRead}, number = 5, pages = {609--627}, publisher = {Academic Press, Inc.}, timestamp = {2010-04-05T13:10:59.000+0200}, title = {Fast and lock-free concurrent priority queues for multi-thread systems}, url = {http://portal.acm.org/citation.cfm?id=1073765.1073770&coll=Portal&dl=GUIDE&CFID=84819369&CFTOKEN=40932755}, volume = 65, year = 2005 }