[0] https://divan.dev/posts/go_concurrency_visualize/

It does require some waiting around to see how things develop (versus the at-a-glance approach) but it really feels so very graspable & clear to me.

That said, I don't really think interleavings are the best way to show weak memory effects either, since they give the impression that there is some global order that is the same in all threads. I'm not sure how to do a nice visualization of the reality though.

One idea: show the interleaving of atomic operations, and based on that, show what values each other read might see. Maybe even let the user change the interleaving by dragging stuff around, and show how it changes which other values can be observed.

The original futex code used physical addresses, and pinned the page, which is simple: if you can share memory somehow, you can use a futex.

Of course, most people use pthreads and increasingly the idea of a Linux userspace locking primitive gave way to a glibc-pthread accelerator...

If you can share memory and you have coherent caches you can use a futex. (In particular, many embedded systems have weaker cache coherency than x86, so "it works on my laptop" is not enough!)

In the worst case, without coherent caches you may need to do a cache shootdown IPI, which means entering the kernel anyway.

I have a vague recollection that it's something to do with whether caches snoop the memory bus for reads of lines they "own" but I could be mistaken. Whatever it was, there were cases where buggy code meant that a core could read a stale value from memory for multiple seconds after another core wrote to the same address.

ARM still has a coherent cache, however. Basically every modern OS and program depends on having a coherent data cache (though ARM doesn't keep i-cache and d-cache coherent with each other, which basically only comes in play with self-modifying code)

ARM and x86 both can delay stores behind later loads. "Timeliness" of when stores might become visible is almost never specified exactly by any ISA or implementation (maybe some real-time CPUs, but Linux does not depend on such), but you will never get into the situation where a memory operation reads "stale" data beyond a fairly strict specification of memory consistency.

ARM does have some weaker ordering than x86, but this is all about how operations within a single CPU/thread behave. An ARM CPU can perform two loads out of order, and perform two stores out of order (with respect to what other CPUs can observe). Use barriers to order those, and you have ~same semantics as x86, and those barriers don't need to "reach out" on the interconnect or to the caches of other CPUs. Once the data leaves your store queues, both x86 and ARM, all other CPUs will see the result, because for it to be accepted into coherent caches, all other copies in other caches need to be invalidated first.

[1] Linux does work on some CPUs where instruction caches and/or the instruction fetch/execution pipeline are not coherent with data operations so there can be some situations on some CPUs where code modification may need to send IPIs to other CPUs to flush their instruction caches or pipelines, so speaking purely about memory data operations and data caches above.

As an aside -- it would be interesting to see what the analog on Windows is. I know from experience the platform-provided mutex implementation on win32 is horrendously slow, and it would be nice to know if it's even possible on that platform to implement a 'real' mutex that doesn't suck. Anyone know of a reference implementation of mutexes on Windows?

[1]: https://learn.microsoft.com/en-us/windows/win32/api/synchapi...

[2]: https://github.com/ziglang/zig/blob/295b8ca467da36cd1066395e...

(That said, I think I heard somewhere that windows mutexes are decent now?)

https://crates.io/crates/parking_lot

IIRC the only platform specific part is the thread parking logic, so I'd assume it's pretty fast on Windows in the common case.

If you don't need cross-process sync, you should really be using a Critical Section instead. The kernel-level interface, which is largely undocumented, is I believe either an Event object or a Keyed Event on later versions.

There's some interesting related discussion on that here: https://microsoft.public.win32.programmer.kernel.narkive.com...

Anyone know of a reference implementation of mutexes on Windows?

Look in the WINE source.

Sorry, but this sounds like FUD to me. First off, there is no single Win32 mutex implementation. The Win32 'Mutex' object is indeed heavy weight, but it is meant for inter-process synchronization. For thread synchronization you would rather use 'CriticalSection' or 'SRWLOCK'; they both avoid calling into the kernel in the uncontended case. SRWLOCK in particular is very fast.

    .         DIJKSTRA P FUNCTION
    .
    .
    .         LA,U      A0,<QUEUE>
    .         LMJ       X11,P
    .         <RETURN>                      X5 DESTROYED
    .
    P*        TS        QHEAD,A0            LOCK THE QUEUE
              LX        X5,QN,A0            LOAD QUEUE COUNT
              ANX,U     X5,1                BACK UP THE COUNT
              SX        X5,QN,A0            REPLACE THE COUNT IN THE QUEUE
              TN        X5                  DO WE NEED TO DEACTIVATE HIM ?
              J         PDONE               NO.  SKIP DEACTIVATION
              ON        TSQ=0
              LX        X5,QHL,A0           LOAD BACK LINK OF QUEUE
              SX        X5,QHL,X4           PUT INTO BACK LINK OF ACTIVITY
              SX        X4,QFL,X5           CHAIN ACTIVITY TO LAST ACTIVITY
              SA        A0,QFL,X4           CHAIN HEAD TO NEW ACTIVITY
              SX        X4,QHL,A0           MAKE THE NEW ACTIVITY LAST ON QUEUE
              CTS       QHEAD,A0            RELEASE PROTECTION ON QUEUE HEAD
    SCHDACT*  DACT$     .                   DEACTIVATE PROCESS
              OFF
              ON        TSQ
              C$TSQ     QHEAD,A0            WAIT FOR C$TSA
              OFF
              J         0,X11               RETURN AFTER ACTIVATION
    .
    PDONE     CTS       QHEAD,A0            UNLOCK THE QUEUE
              J         0,X11               RETURN

[1] https://www.fourmilab.ch/documents/univac/fang/

Exactly as you said, the problem with a Benaphore is that if your program wants 100 Benaphores, you're creating 100 OS-wide semaphores, even if your program is literally never experiencing contended locking, that's 100x scarce OS resource used up just in case. If you ask for one million Benaphores, the program won't run, the entire OS only allows (IIRC) 65536 total.

Putting together this fast path + the wait queue idea = a futex, very fast yet very cheap.

From the code comments, it is likely that UNIVAC is using something like solaris park/unpark and the queue is fully in userspace.

Futexes were in Linux over two decades ago: https://www.kernel.org/doc/ols/2002/ols2002-pages-479-495.pd... :)

And before that I believe glibc did something similar to what I described in the post, using signals

I’m not sure that’s correct, it’s “waitQueue” that is hashed. In a super naive simple implementation the attributes are just a hash map.

That way you avoid cache misses and cache invalidation at the same time. And your software can run at full speed across multiple threads/cores.

Also, few or no CPUs can perform atomic operations on 64 bytes of memory without using transactional memory (which has its own drawbacks), and in any case atomic operations and cacheline alignment don't save you from cache misses and invalidations if CPUs operate on the same data.

You need the array to contain structures that fill the cache line to avoid invalidation when two cores write/read structures close to each other.

When two cores write/read to/from the same atomic variable in the same structure you of course need to know what the consequences will be, but most of the time it will only result on gliches and not crashes... say if the position of a player is updated by the physics and incoming network at the same time and read by the render core... the player will glitch to some location that might be wrong for the other writing core so you have to make sure that is handled to not behave in a non playable way, but performance on the CPU is the _only_ bottleneck we will ever have and we're already there.

You could also look at Javas concurrency package. It's mostly atomic.

Linux was 1991 - as a minimal monolithic single arch student level kludge made from studying SunOS API calls and the MINIX project.

Solaris was 1993 .. a succusor to SunOS and a turn away from the SunOS BSD roots towards UNIX System V Release 4.

Both Linux and Solaris had deep prior art roots in the "Unix-like" sphere, many ideas cropped up over there originally but only really gained traction somewhere else.

( Other ideas of that time, such as capability based permissions, never really took off until decades later )

I meant, when did the futex (linux) and park() (Solaris) functionality become available in both? Some Linux things have an [uncredited] history as a Solaris feature first.

To the best of my recollection, with some links I see that back this:

Futex appeared in Linux circa 2002 ( late kernel ver 2.5 series ), (Net) BSD _lwp_park() appeared circa 2009 but ... I have an inkling it popped up earlier in sources I don't have online access to right now (archived drives | tapes in a shed some distance away)

This post 2000 era is right when I moved away from heavy Sun workstation usage and low level tinkering and into other domains.

Didn't all the unices of the day have C2-secure (and even tighter) "orange book" versions? Windows as well I believe. And definitely some other unices. That's so long ago I don't recall but didn't starting at C2 require MAC and this implies some kind of privilege system.

Solaris has had privileges (analogous to Linux capabilities) since 2005. Looks like Linux had it since 1999 but of more limited scope until 2008 when it got extended.

So I'd say "a decade", not "decades". ;)

park/unpark simply remove the thread from the run queue and require userspace to keep the waitqueue and identify which thread to wakeup. The semantics of futex is that the kernel will maintain the waitqueue. The advantage is that futex can be used across processes, not just threads and are possibly easier, on the other hand, high performance signaling primitives implementations probably want to maintain the waitqueue in userspace anyway, so park/unpark might be a better, if lower level, primitive.

That said, I was completely unaware that futex can work across processes as IPC! Sorry I'm being lazy here but I don't know if park/unpark/setpark offer that -- I doubt it. However on Solaris you have doors which is an ultrafast IPC.

It was discussed here two years ago: https://news.ycombinator.com/item?id=24958504

But I only recently believe I ran into it in the wild when testing some high-concurrency multithreading code for several days. It would run a few hundred million operations successfully and then hang, CPU busy, on pthread_cond_wait().