+/EE360P
distributed systems
git clone https://git.julia.blue/+/EE360P
fb612a0
master
1 Two-Lock Concurrent Queue Algorithm 2 3 structure node_t {value: data type, next: pointer to node_t} 4 structure queue_t {Head: pointer to node_t, Tail: pointer to node_t, 5 H_lock: lock type, T_lock: lock type} 6 7 initialize(Q: pointer to queue_t) 8 node = new_node() // Allocate a free node 9 node->next = NULL // Make it the only node in the linked list 10 Q->Head = Q->Tail = node // Both Head and Tail point to it 11 Q->H_lock = Q->T_lock = FREE // Locks are initially free 12 13 enqueue(Q: pointer to queue_t, value: data type) 14 node = new_node() // Allocate a new node from the free list 15 node->value = value // Copy enqueued value into node 16 node->next = NULL // Set next pointer of node to NULL 17 lock(&Q->T_lock) // Acquire T_lock in order to access Tail 18 Q->Tail->next = node // Link node at the end of the linked list 19 Q->Tail = node // Swing Tail to node 20 unlock(&Q->T_lock) // Release T_lock 21 22 dequeue(Q: pointer to queue_t, pvalue: pointer to data type): boolean 23 lock(&Q->H_lock) // Acquire H_lock in order to access Head 24 node = Q->Head // Read Head 25 new_head = node->next // Read next pointer 26 if new_head == NULL // Is queue empty? 27 unlock(&Q->H_lock) // Release H_lock before return 28 return FALSE // Queue was empty 29 endif 30 *pvalue = new_head->value // Queue not empty. Read value before release 31 Q->Head = new_head // Swing Head to next node 32 unlock(&Q->H_lock) // Release H_lock 33 free(node) // Free node 34 return} TRUE // Queue was not empty, dequeue succeeded