Hi Chris, I took a detailed look at your post about your lock free queue and I think I've grasped the subtleties but I had two questions regarding putting head and tail into a struct. First, would you mind explaining this in a bit more detail: > While this entire structure can be atomically loaded just like the 32-bit integer, C11 (and later) do not permit non-atomic accesses to these atomic fields in an unshared copy loaded from an atomic. Also you state that: > Technically with two loads this could extract a head/tail pair that were never contemporaneous. The worst case is the queue appears empty even if it was never actually empty. Under what condition could this occur? Is this a problem that storing the head and tail in the single atomic 32-bit unsigned integer would avoid? Thanks, Stedman
> Under what condition could this occur? Imagine the queue has one element, and consumers load head first, tail second. It loads head, a producer pushes, a different consumer pops, and then the consumer loads tail. It observes head==tail (empty), but at no point was the queue actually empty. Flip the load order, and it's less likely, but can still occur if the queue wraps around (in terms of the masked indices), which is more likely to happen for smaller queues. Since it's single producer, producers do not face this problem: The head does not move concurrently for the producer. I hadn't though about this until now, but that means the producer need not atomically load the head (similarly: for single-consumer queues, consumers need not atomically load the tail either). Unfortunately C11 atomics are too restrictive and so, at best, can only turn it into a relaxed atomic load. > Is this a problem that storing the head and tail in the single atomic > 32-bit unsigned integer would avoid? By loading them together in one atomic load you're guaranteed to get an exact snapshot of the queue at some instant in time. It's not possible to observe an empty queue if the queue was never empty. Separate loads allow one or the other to change in between. It's not necessarily catastrophic, but it must be tolerated if loads are made separately.