To clarify, I take atomic aligned reads and writes of machine-sized integers (say 32bit) for granted. I'm not aware of any machines where these simple read and

To clarify, I take atomic aligned reads and writes of machine-sized integers (say 32bit) for granted. I'm not aware of any machines where these simple read and write operations aren't atomic. So I don't consider those "atomics". By "atomics" I understand something like atomic exchange, compare-and-swap, atomic inc/dec. You can implement practical SRSW queues without atomics. Preventing reordering in compiler and CPU is enough. I believe you don't need atomics to achieve mutual exclusion, at least not for 2 processes (Peterson's algorithm). > You always need control over your compiler Yes, this was the other poster's point, you cannot implement threading purely as a library. Function calls like pthread_mutex_lock() must be synchronization points and the compiler must not reorder any instructions around them.