Editing Priority queue (section)

=== Concurrent parallel access ===
If the priority queue allows concurrent access, multiple processes can perform operations concurrently on that priority queue. However, this raises two issues. First of all, the definition of the semantics of the individual operations is no longer obvious. For example, if two processes want to extract the element with the highest priority, should they get the same element or different ones? This restricts parallelism on the level of the program using the priority queue. In addition, because multiple processes have access to the same element, this leads to contention.
[[File:concurrent_prio_queue_conflict.svg|thumb|Node 3 is inserted and sets the pointer of node 2 to node 3. Immediately after that, node 2 is deleted and the pointer of node 1 is set to node 4. Now node 3 is no longer reachable.]]

The concurrent access to a priority queue can be implemented on a Concurrent Read, Concurrent Write (CRCW) PRAM model. In the following the priority queue is implemented as a [[skip list]].<ref name = skiplist>{{cite journal |last1= Sundell |first1=Håkan |last2= Tsigas |first2= Philippas |date=2005 |title=Fast and lock-free concurrent priority queues for multi-thread systems |url= https://doi.org/10.1016/j.jpdc.2004.12.005 |journal= Journal of Parallel and Distributed Computing |volume= 65 |issue= 5 |pages= 609–627 |doi= 10.1109/IPDPS.2003.1213189|s2cid=20995116 |citeseerx= 10.1.1.67.1310 }}</ref><ref>{{citation|surname1=Lindén, Jonsson|periodical=Technical Report 2018-003|title=A Skiplist-Based Concurrent Priority Queue with Minimal Memory Contention|date=2013|language=de|url=http://www.it.uu.se/research/publications/reports/2018-003/
}}</ref> In addition, an atomic synchronization primitive, [[Compare-and-swap|CAS]], is used to make the skip list [[Lock (computer science)|lock]]-free. The nodes of the skip list consists of a unique key, a priority, an [[array data structure|array]] of [[Pointer (computer programming)|pointers]], for each level, to the next nodes and a ''delete'' mark. The ''delete'' mark marks if the node is about to be deleted by a process. This ensures that other processes can react to the deletion appropriately.
*''insert(e)'': First, a new node with a key and a priority is created. In addition, the node is assigned a number of levels, which dictates the size of the array of pointers. Then a search is performed to find the correct position where to insert the new node. The search starts from the first node and from the highest level. Then the skip list is traversed down to the lowest level until the correct position is found. During the search, for every level the last traversed node will be saved as parent node for the new node at that level. In addition, the node to which the pointer, at that level, of the parent node points towards, will be saved as the successor node of the new node at that level. Afterwards, for every level of the new node, the pointers of the parent node will be set to the new node. Finally, the pointers, for every level, of the new node will be set to the corresponding successor nodes.
*''extract-min'': First, the skip list is traversed until a node is reached whose ''delete'' mark is not set. This ''delete'' mark is than set to true for that node. Finally the pointers of the parent nodes of the deleted node are updated.

If the concurrent access to a priority queue is allowed, conflicts may arise between two processes. For example, a conflict arises if one process is trying to insert a new node, but at the same time another process is about to delete the predecessor of that node.<ref name = skiplist/> There is a risk that the new node is added to the skip list, yet it is not longer reachable. ([[:File:concurrent_prio_queue_conflict.svg|See image]])