Are indivisible operations still indivisible on multiprocessor and multicore systems?

Question

As per the title, plus what are the limitations and gotchas.

For example, on x86 processors, alignment for most data types is optional - an optimisation rather than a requirement. That means that a pointer may be stored at an unaligned address, which in turn means that pointer might be split over a cache page boundary.

Obviously this could be done if you work hard enough on any processor (picking out particular bytes etc), but not in a way where you'd still expect the write operation to be indivisible.

I seriously doubt that a multicore processor can ensure that other cores can guarantee a consistent all-before or all-after view of a written pointer in this unaligned-write-crossing-a-page-boundary situation.

Am I right? And are there any similar gotchas I haven't thought of?

Answer 1

The very notion of a single memory visible to all threads ceases to work with several cores having individual caches. StackOverflow questions on memory barriers may be of interest; say, this one.

I think an example to illustrate the problem with the "single memory" model is this one: Initially, x = y = 0.

Thread 1:

X = x;
y = 1;

Thread 2:

Y = y;
x = 1;

Of course, there is a race condition. The secondary problem besides the obvious race condition is that one possible outcome is X=1, Y=1. Even without compiler optimizations (even if you write the above two threads in assembly).

Answer 2

Is it possible for this class to output “False”?

class Unsafe
{
  static bool underwearOn, trousersOn;

  static void Main( )
  {
    new Thread(Wait).Start( );    // Start up the busy waiter
    Thread.Sleep(1000);           // Give it a second to start up!

    underwearOn = true;
    trousersOn = true;
  }

  static void Wait(  )
  {
    while (!trousersOn)
        ; // Spin until trousersOn
    Console.Write(underwearOn);
  }
}

Yes, on multicore machines. Value types, such as bools, can be stored in machine registers, and the order registers are synchronized is machine-specific. underwearOncould be synchronized before trousersOn.

You could lock the assignments and while loop, but this will harm performance. A better solution is to declare the bool variables volatile. Such variables are not stored in registers.

Edit:

This is a simplified example from a presentation available at Threading Complete.

Answer 3

Maybe I misunderstand the example but the "unaligned pointer" problem is the same as on a single-core execution. If a datum can be partially written to memory then different threads can see partial updates (if there's no appropriate locking) on any machine with preemtive multitasking (even on a single-CPU system).

You don't have to worry about the cache unless you are writing drivers for DMA-capable peripherals. Modern multi-processors are cache coherent so the hardware guarantees that a thread on processor A will have the same view of memory as a thread on processor B. If the thread on A reads a memory location that is cached on B then the thread on A will get the correct value from Bs cache.

You do have to worry about values in registers and from a programming standpoint that difference may not be a visible one, but in my opinion involving the cache in a concurrency discussion often just introduces unnecessary confusion.

Any operation that is labeled "indivisible" by the programming manual for a ISA must reasonably keep being indivisible in a multiprocessing system built with processors using that ISA or backwards compatibility would break. However, this does not mean that operations that were never promised to be indivisible, but happened to be in a particular processor implementation, will be indivisible in future implementations (such as in a multiprocessor system).

[Edit] Completion to the comment below

1. Anything written to memory will be coherently visible to all threads, regardless of the number of cores (in a cache coherent system).
2. Anything written to memory non-atomically can end up being partially read by unsynchronized threads in the presence of preemption (even on a single-core system).

If the pointer is written to an unaligned address in a single, atomic write then the cache coherence hardware will make sure that all threads see it completed, or not at all. If the pointer is written non-atomically (such as with two separate write operations) then any threads may see the partial update even on a single-core system with true preemption.

Answer 4

On a x86 then the answer is yes if the assembler operation was prefixed by a lock instruction then the processor asserts a hardware signal that ensures that the following instruction is atomic (in some processors the caches coordinate to ensure the operation is atomic).

Making operations atomic is something compilers don't do, on multiprocessor systems atomic assembly language operations are very expensive and are generally used to implement the locking primitives offered by the OS / C library.

No purely high level language memory operations should be regarded as atomic. If you have multiple threads writing to the same shared memory location then you need to use some mutex/lock mechanism to avoid races.