CMPXCHG and critical section implementation

Question

The CMPXCHG statement works as follows:

CMPXCHG (common, old, new):
    int temp
    temp <- common
    if common = old then
           common <- new
    return temp    

What is the simplest possible algorithm for implementing a critical section, if a CMPXCHG atomic instruction is available?

Answer 1

If you want to create a simple critical section (using the Windows definition of a CRITICAL_SECTION), you can look at the following pseduo-code:

EnterCS(cs):
    If CMPXCHG(cs,0,1) = 0 
        Return True
    Return False

ExitCS:
    If CMPXCHG(cs,1,0) = 1 
        Return True
    Return False

Then using it becomes a simple case of:

If EnterCS(cs)
    SomeValue <- SomeValue + 10 
    ExitCS(cs)

This acquisition is actually more like a try-to-acquire, to extend to to the more common acquisition scheme of CS's, we alter the method like so

EnterCS(cs):
    While CMPXCHG(cs,0,1) != 0
        SpinOneCycle()
    Return True

This simple lock has its various issues, such as the inability to handle recursion, for which you need to keep a recursive lock count. I would recommend using something provided by the operating system. If you do need to write your own locks, Intel has a few publications on writing high-performance and scalable spinlocks, you can read one of them for Xeon processors here and another for x86 here. Lockless Inc also has an article on spinlocks here.