+/EE360P

distributed systems

git clone https://git.julia.blue/+/EE360P

vijaygarg1data structures addedfb612a0

master
2.9 KiB60 linesraw
1 Non-Blocking Concurrent Queue Algorithm
2
3  structure pointer_t {ptr: pointer to node_t, count: unsigned integer}
4  structure node_t {value: data type, next: pointer_t}
5  structure queue_t {Head: pointer_t, Tail: pointer_t}
6  
7  initialize(Q: pointer to queue_t)
8     node = new_node()		// Allocate a free node
9     node->next.ptr = NULL	// Make it the only node in the linked list
10     Q->Head.ptr = Q->Tail.ptr = node	// Both Head and Tail point to it
11  
12  enqueue(Q: pointer to queue_t, value: data type)
13   E1:   node = new_node()	// Allocate a new node from the free list
14   E2:   node->value = value	// Copy enqueued value into node
15   E3:   node->next.ptr = NULL	// Set next pointer of node to NULL
16   E4:   loop			// Keep trying until Enqueue is done
17   E5:      tail = Q->Tail	// Read Tail.ptr and Tail.count together
18   E6:      next = tail.ptr->next	// Read next ptr and count fields together
19   E7:      if tail == Q->Tail	// Are tail and next consistent?
20               // Was Tail pointing to the last node?
21   E8:         if next.ptr == NULL
22                  // Try to link node at the end of the linked list
23   E9:            if CAS(&tail.ptr->next, next, <node, next.count+1>)
24  E10:               break	// Enqueue is done.  Exit loop
25  E11:            endif
26  E12:         else		// Tail was not pointing to the last node
27                  // Try to swing Tail to the next node
28  E13:            CAS(&Q->Tail, tail, <next.ptr, tail.count+1>)
29  E14:         endif
30  E15:      endif
31  E16:   endloop
32         // Enqueue is done.  Try to swing Tail to the inserted node
33  E17:   CAS(&Q->Tail, tail, <node, tail.count+1>)
34  
35  dequeue(Q: pointer to queue_t, pvalue: pointer to data type): boolean
36   D1:   loop			     // Keep trying until Dequeue is done
37   D2:      head = Q->Head	     // Read Head
38   D3:      tail = Q->Tail	     // Read Tail
39   D4:      next = head.ptr->next    // Read Head.ptr->next
40   D5:      if head == Q->Head	     // Are head, tail, and next consistent?
41   D6:         if head.ptr == tail.ptr // Is queue empty or Tail falling behind?
42   D7:            if next.ptr == NULL  // Is queue empty?
43   D8:               return FALSE      // Queue is empty, couldn't dequeue
44   D9:            endif
45                  // Tail is falling behind.  Try to advance it
46  D10:            CAS(&Q->Tail, tail, <next.ptr, tail.count+1>)
47  D11:         else		     // No need to deal with Tail
48                  // Read value before CAS
49                  // Otherwise, another dequeue might free the next node
50  D12:            *pvalue = next.ptr->value
51                  // Try to swing Head to the next node
52  D13:            if CAS(&Q->Head, head, <next.ptr, head.count+1>)
53  D14:               break             // Dequeue is done.  Exit loop
54  D15:            endif
55  D16:         endif
56  D17:      endif
57  D18:   endloop
58  D19:   free(head.ptr)		     // It is safe now to free the old node
59  D20:   return TRUE                   // Queue was not empty, dequeue succeeded
60