multithreadingconcurrencysynchronizationcpuprocessors

Multiple Processes on Multiple CPU Reading and Writing Same Data


I am studying concurrency now and I have some doubts.

Let's take the example on wiki. http://en.wikipedia.org/wiki/Atomic_(computer_science)

The naive, non-atomic way reads a value, adds 1, then writes back. If 2 processes are running at the same time, the steps may interleave with each other. For example, the 1st process reads and adds 1, but it gets suspended. The 2nd process reads, adds 1 and writes back and gets interrupted. The 1st process resumes and writes back an old value.

I understand how the atomic compare-and-swap solves the problem. It reads, adds 1, and use compare-and-swap to write, and retry if the compare-and-swap fails.

However, I am imagining a scenario where we have multiple cores executing the multiple threads. What if the 1st process and the 2nd process runs at exactly the same time on different cores? i.e. Process1 on CPU1 does read, add, compare-and-swap at the same time that Process2 on CPU2 does read, add, compare-and-swap. I think the compare-and-swap will succeed too.

Is this situation even possible? If so, how is it dealt with?


Solution

  • Compare-and-swap is implemented in hardware; roughly speaking the processor works with the memory bus to ensure that the core executing the compare-and-swap has exclusive access to shared memory. So it is literally not possible for the two processes to run at the same time: One will be the first to get the (hardware-guaranteed) lock of the shared memory.

    For instance, on Intel, atomic compare-and-swap is implemented by LOCK CMPXCHG. The LOCK prefix ensures that:

    In a multiprocessor environment, the LOCK# signal ensures that the processor has exclusive use of any shared memory while the signal is asserted.

    (Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 2 (2A, 2B & 2C): Instruction Set Reference, A-Z, vol 2A p. 3-462).