+/EE360P
distributed systems
git clone https://git.julia.blue/+/EE360P
fb612a0
master
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