~skeeto/public-inbox

1

Questions about your lock free queue

Steadman Dillroper <dillstead@gmail.com>
Details
Message ID
<CAOJH3v7gucAW5z9fbMG6GU6W3ZZFiMNSzrozoqYRyQgWem898Q@mail.gmail.com>
DKIM signature
pass
Download raw message
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
Details
Message ID
<20220609154610.4r4bptdtjvwtrbwv@nullprogram.com>
In-Reply-To
<CAOJH3v7gucAW5z9fbMG6GU6W3ZZFiMNSzrozoqYRyQgWem898Q@mail.gmail.com> (view parent)
DKIM signature
missing
Download raw message
> 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.
Reply to thread Export thread (mbox)