+/EE360P

distributed systems

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

vijaygarg1data structures addedfb612a0

master
1.6 KiB34 linesraw
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