none
How Interlocked.CompareExchange make sure it is atomic ? RRS feed

Answers

  • I think that Compare-and-Exchange can be implemented using the CMPXCHG instruction, and according to documentation (Instruction Set Reference) “this instruction can be used with a LOCK prefix to allow the instruction to be executed atomically”. Therefore Interlocked.CompareExchange can be translated to LOCK CMPXCHG, so that the atomicity is ensured by the hardware.

    Tuesday, May 10, 2016 11:49 AM
  • You can make any operation atomic by just adding mutual exclusion to it/around it. That is what DBMS/DB's do.
    The natural downside is that you create a artificial bottleneck, but such is the price of avoiding race conditions.

    In C# you can do Mutex using the lock language statement.
    For variables, consider the volatile keyword instead, wich may impact how the CPU interprets the code.

    But in the end you have little to no control over what the CPU does in .NET. What exactly happens behind lock and volatile are maters of Framework, Driver and Hardware implementations - 2-3 layers of abstraction removed from your code.

    • Marked as answer by Jacky_shen Friday, May 20, 2016 5:20 AM
    Tuesday, May 10, 2016 12:01 PM
  • Thank you for all of you.

    Now the question is how "LOCK CMPXCHG" make sure it is atomic beside the sense? any more detail information for that instruction?


    For authoritative answer about Intel processors please ask on Intel developer forums here or maybe here

    On ARM, the Interlocked intrinsics also guaranteed to be atomic, though the machine instructions and their performance  are different. Maybe the WinCE (a.k.a. Windows Embedded Compact) forums are the place to ask, because they deal with ARM for quite long time.

    -- pa

    • Marked as answer by Jacky_shen Friday, May 20, 2016 5:20 AM
    Tuesday, May 10, 2016 1:02 PM
  • As Viorel mentions, they are implemented at the processor level using asembly instructions that the processor provides.  Under the .NET hood the methods are implemented by calling the corresponding Win32 API which itself is an intrinsic function that generates the instructions directly inline. Since the processor provides the operation as atomic then it is atomic. The details of how the processor implements atomic (and how it relates to memory barriers) will need to be asked in Intel/AMD's forums.

    Michael Taylor
    http://www.michaeltaylorp3.net
    • Marked as answer by Jacky_shen Friday, May 20, 2016 5:20 AM
    Tuesday, May 10, 2016 1:42 PM
    Moderator
  • It's hardware.  All Intel processors have a "lock" pin that is used for this kind of concurrency.  When you run an instruction with the LOCK prefix, the processor asserts that pin.  Only one processor at a time can have it, and while it is turned on, all of the other processors temporarily pause.

    That's all it takes to guarantee atomicity.


    Tim Roberts, Driver MVP Providenza & Boekelheide, Inc.

    • Marked as answer by Jacky_shen Friday, May 20, 2016 5:20 AM
    Tuesday, May 10, 2016 11:20 PM
  • I'm rather baffled at this point. You asked a lot of questions about this subject but this particular question, as already pointed out by others, is beyond the scope of this forum. It's one thing to ask about the semantics of volatile or about how lock is implemented by the compiler and/or the runtime and it's a completely different thing to ask how the hardware ensures atomicity.

    I suppose you could start by looking at Intel's System Programming Guide, chapter 8 and chapter 11 have some details about this kind of stuff. But those manuals are more about what the processor does and not how it does.

    Wednesday, May 11, 2016 7:15 AM
    Moderator
  • Thank you all especially Mike,

    It seems I got some clues from the following article.

    http://heather.cs.ucdavis.edu/~matloff/50/PLN/lock.pdf

    • Proposed as answer by Linki Tan Thursday, May 19, 2016 9:27 AM
    • Marked as answer by Jacky_shen Friday, May 20, 2016 5:20 AM
    Wednesday, May 11, 2016 12:39 PM
  • If you want more interesting reading on these matters, try this:

    https://channel9.msdn.com/Shows/Going+Deep/Cpp-and-Beyond-2012-Herb-Sutter-atomic-Weapons-1-of-2



    Great videos, Thank you.
    • Marked as answer by Jacky_shen Saturday, May 21, 2016 3:07 AM
    Saturday, May 21, 2016 3:06 AM

All replies

  • I think that Compare-and-Exchange can be implemented using the CMPXCHG instruction, and according to documentation (Instruction Set Reference) “this instruction can be used with a LOCK prefix to allow the instruction to be executed atomically”. Therefore Interlocked.CompareExchange can be translated to LOCK CMPXCHG, so that the atomicity is ensured by the hardware.

    Tuesday, May 10, 2016 11:49 AM
  • You can make any operation atomic by just adding mutual exclusion to it/around it. That is what DBMS/DB's do.
    The natural downside is that you create a artificial bottleneck, but such is the price of avoiding race conditions.

    In C# you can do Mutex using the lock language statement.
    For variables, consider the volatile keyword instead, wich may impact how the CPU interprets the code.

    But in the end you have little to no control over what the CPU does in .NET. What exactly happens behind lock and volatile are maters of Framework, Driver and Hardware implementations - 2-3 layers of abstraction removed from your code.

    • Marked as answer by Jacky_shen Friday, May 20, 2016 5:20 AM
    Tuesday, May 10, 2016 12:01 PM
  • Thank you for all of you.

    Now the question is how "LOCK CMPXCHG" make sure it is atomic beside the sense? any more detail information for that instruction?


    • Edited by Jacky_shen Tuesday, May 10, 2016 12:46 PM
    Tuesday, May 10, 2016 12:45 PM
  • Thank you for all of you.

    Now the question is how "LOCK CMPXCHG" make sure it is atomic beside the sense? any more detail information for that instruction?


    For authoritative answer about Intel processors please ask on Intel developer forums here or maybe here

    On ARM, the Interlocked intrinsics also guaranteed to be atomic, though the machine instructions and their performance  are different. Maybe the WinCE (a.k.a. Windows Embedded Compact) forums are the place to ask, because they deal with ARM for quite long time.

    -- pa

    • Marked as answer by Jacky_shen Friday, May 20, 2016 5:20 AM
    Tuesday, May 10, 2016 1:02 PM
  • As Viorel mentions, they are implemented at the processor level using asembly instructions that the processor provides.  Under the .NET hood the methods are implemented by calling the corresponding Win32 API which itself is an intrinsic function that generates the instructions directly inline. Since the processor provides the operation as atomic then it is atomic. The details of how the processor implements atomic (and how it relates to memory barriers) will need to be asked in Intel/AMD's forums.

    Michael Taylor
    http://www.michaeltaylorp3.net
    • Marked as answer by Jacky_shen Friday, May 20, 2016 5:20 AM
    Tuesday, May 10, 2016 1:42 PM
    Moderator
  • It's hardware.  All Intel processors have a "lock" pin that is used for this kind of concurrency.  When you run an instruction with the LOCK prefix, the processor asserts that pin.  Only one processor at a time can have it, and while it is turned on, all of the other processors temporarily pause.

    That's all it takes to guarantee atomicity.


    Tim Roberts, Driver MVP Providenza & Boekelheide, Inc.

    • Marked as answer by Jacky_shen Friday, May 20, 2016 5:20 AM
    Tuesday, May 10, 2016 11:20 PM
  • The LOCK pin is more or less obsolete. Modern Intel CPU's tend to rely on the cache coherency protocol to implement atomic operations.
    Wednesday, May 11, 2016 5:31 AM
    Moderator
  • The LOCK pin is more or less obsolete. Modern Intel CPU's tend to rely on the cache coherency protocol to implement atomic operations.

    Any more detail information\implementation for this "cache coherency protocol" can be used to describe this atomic operations ?

    • Edited by Jacky_shen Wednesday, May 11, 2016 6:28 AM
    Wednesday, May 11, 2016 6:21 AM
  • I'm rather baffled at this point. You asked a lot of questions about this subject but this particular question, as already pointed out by others, is beyond the scope of this forum. It's one thing to ask about the semantics of volatile or about how lock is implemented by the compiler and/or the runtime and it's a completely different thing to ask how the hardware ensures atomicity.

    I suppose you could start by looking at Intel's System Programming Guide, chapter 8 and chapter 11 have some details about this kind of stuff. But those manuals are more about what the processor does and not how it does.

    Wednesday, May 11, 2016 7:15 AM
    Moderator
  • Thank you all especially Mike,

    It seems I got some clues from the following article.

    http://heather.cs.ucdavis.edu/~matloff/50/PLN/lock.pdf

    • Proposed as answer by Linki Tan Thursday, May 19, 2016 9:27 AM
    • Marked as answer by Jacky_shen Friday, May 20, 2016 5:20 AM
    Wednesday, May 11, 2016 12:39 PM
  • Hi Jacky,

    Please remember to close your threads by marking helpful posts as answer and then start a new thread if you have a new question.


    • Edited by Linki Tan Thursday, May 19, 2016 9:28 AM
    Thursday, May 19, 2016 9:28 AM
  • If you want more interesting reading on these matters, try this:

    https://channel9.msdn.com/Shows/Going+Deep/Cpp-and-Beyond-2012-Herb-Sutter-atomic-Weapons-1-of-2


    • Edited by Pavel A Friday, May 20, 2016 10:11 PM
    Friday, May 20, 2016 10:09 PM
  • If you want more interesting reading on these matters, try this:

    https://channel9.msdn.com/Shows/Going+Deep/Cpp-and-Beyond-2012-Herb-Sutter-atomic-Weapons-1-of-2



    Great videos, Thank you.
    • Marked as answer by Jacky_shen Saturday, May 21, 2016 3:07 AM
    Saturday, May 21, 2016 3:06 AM