An introduction to lockless algorithms [LWN.net]

An introduction to lockless algorithms

Posted Feb 20, 2021 0:12 UTC (Sat) by mpr22 (subscriber, #60784)
In reply to: An introduction to lockless algorithms by pebolle
Parent article: An introduction to lockless algorithms

From the fine article:

"The ordering of events is total within a single thread of execution. In layman's terms, for any two events from the same thread you can always say which came first and which came second."

to post comments

An introduction to lockless algorithms

Posted Feb 20, 2021 0:25 UTC (Sat) by pebolle (guest, #35204) [Link] (1 responses)

> [...] all accesses to the data structure form a total ordering [...]

and

> The ordering of operations is total within a single thread.

Totally clear.

An introduction to lockless algorithms

Posted Feb 20, 2021 7:21 UTC (Sat) by pbonzini (subscriber, #60935) [Link]

"All accesses to the data structure form a total ordering" means that you can always say which access came first and which came second. This is what you'd expect from a mutex, because:

1) you can always say which critical section came first and which came second (lock waits for the other critical section to complete, if there's one), and

2) accesses within a critical section come from a single thread, and there is always a total order (defined in the article) within a thread.