StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POAre there any implementations of concurrent lock-free blocking queues?
primarykey
Id
5734547
data
AcceptedAnswerId
5736575
AnswerCount
2
ClosedDate
CommentCount
24
CommunityOwnedDate
CreationDate
2011-04-20T17:55:58.217
FavoriteCount
2
LastActivityDate
2011-04-21T17:47:51.133
LastEditDate
2011-04-21T13:27:32.353
LastEditorUserId
28760
OwnerUserId
28760
ParentId
0
PostTypeId
1
Score
4
ViewCount
1819
LastEditorDisplayName
text
Body
I'm aware of blocking-queues and lock-free queues, a great example of those implementations being provided by <a href="http://www.research.ibm.com/people/m/michael/podc-1996.pdf" rel="nofollow">Scott et al.</a>, but are there any implementations of a lock-free-blocking-queue? In a lock-free-blocking-queue the dequeue will require no locking, but if there are no items in the queue it will block the consumer. Are there any implementations of such a beast? I prefer if they're C# implementations, but any implementation would technically work. Update: I think I end up with a race condition on line D14.1: <pre><code>initialize(Q: pointer to queue t) node = new node() // Allocate a free node node–>next.ptr = NULL // Make it the only node in the linked list Q–>Head = Q–>Tail = node // Both Head and Tail point to it signal = new ManualResetEvent() // create a manual reset event enqueue(Q: pointer to queue t, value: data type) E1: node = new node() // Allocate a new node from the free list E2: node–>value = value // Copy enqueued value into node E3: node–>next.ptr = NULL // Set next pointer of node to NULL E4: loop // Keep trying until Enqueue is done E5: tail = Q–>Tail // Read Tail.ptr and Tail.count together E6: next = tail.ptr–>next // Read next ptr and count fields together E7: if tail == Q–>Tail // Are tail and next consistent? E8: if next.ptr == NULL // Was Tail pointing to the last node? E9: if CAS(&tail.ptr–>next, next, <node, next.count+1>) // Try to link node at the end of the linked list E10.1: signal.Set() // Signal to the blocking dequeues E10.2: break // Enqueue is done. Exit loop E11: endif E12: else // Tail was not pointing to the last node E13: CAS(&Q–>Tail, tail, <next.ptr, tail.count+1>) // Try to swing Tail to the next node E14: endif E15: endif E16: endloop E17: CAS(&Q–>Tail, tail, <node, tail.count+1>) // Enqueue is done. Try to swing Tail to the inserted node dequeue(Q: pointer to queue t, pvalue: pointer to data type): boolean D1: loop // Keep trying until Dequeue is done D2: head = Q–>Head // Read Head D3: tail = Q–>Tail // Read Tail D4: next = head–>next // Read Head.ptr–>next D5: if head == Q–>Head // Are head, tail, and next consistent? D6: if head.ptr == tail.ptr // Is queue empty or Tail falling behind? D7: if next.ptr == NULL // Is queue empty? D8.1: signal.WaitOne() // Block until an enqueue D8.X: // remove the return --- return FALSE // Queue is empty, couldn’t dequeue D9: endif D10: CAS(&Q–>Tail, tail, <next.ptr, tail.count+1>) // Tail is falling behind. Try to advance it D11: else // No need to deal with Tail // Read value before CAS, otherwise another dequeue might free the next node D12: *pvalue = next.ptr–>value D13: if CAS(&Q–>Head, head, <next.ptr, head.count+1>) // Try to swing Head to the next node D14.1: if(head.ptr == tail.ptr && next.ptr==NULL) // Is queue empty? <--- POSSIBLE RACE CONDITION??? D14.2: signal.Reset() D14.3: break // Dequeue is done. Exit loop D15: endif D16: endif D17: endif D18: endloop D19: free(head.ptr) // It is safe now to free the old dummy node D20: return TRUE // Queue was not empty, dequeue succeeded </code></pre>
Tags
<c#><multithreading><concurrency><lock-free><blockingqueue>
Title
Are there any implementations of concurrent lock-free blocking queues?
singulars
PostAcceptedAnswerId
1. PO
 singulars
 PostTypePostTypeId
 PTAnswer
PostParentId
1. This table or related slice is empty.
PostTypePostTypeId
1. PTQuestion
UserLastEditorUserId
1. USKiril
UserOwnerUserId
1. USKiril
plurals
PostLinksPostIdRelatedPostId
1. PL
 singulars
 LinkTypeLinkTypeId
 LTLinked
2. PL
 singulars
 LinkTypeLinkTypeId
 LTLinked
3. PL
 singulars
 LinkTypeLinkTypeId
 LTLinked
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. PO
 singulars
 PostTypePostTypeId
 PTAnswer
2. PO
 singulars
 PostTypePostTypeId
 PTAnswer
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 POAre there any implementations of concurrent lock-free blocking queues?
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 POAre there any implementations of concurrent lock-free blocking queues?
 UserUserId
 USjohnnycrash
 VoteTypeVoteTypeId
 VTFavorite
3. VO
 singulars
 PostPostId
 POAre there any implementations of concurrent lock-free blocking queues?
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
CommentsPostId

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.