Editing Test-and-set (section)

== Mutual exclusion using test-and-set ==
One way to implement [[mutual exclusion]] is by using a test-and-set based lock<ref>{{Cite book|title=Operating Systems: Three Easy Pieces|last=Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau|publisher=Arpaci-Dusseau Books|year=2015|edition=0.91}}</ref><ref>{{Cite book|title=Fundamentals of parallel computer architecture : multichip and multicore systems|last=Solihin|first=Yan|year=2009|isbn=9780984163007|pages=252}}</ref> as follows:

=== Pseudo-C implementation of a spin lock ===
<syntaxhighlight lang="c">
volatile int lock = 0;

void critical() {

    // Spin lock: loop forever until we get the lock.
    // We know the lock was successfully obtained after exiting 
    // this while loop because the test_and_set() function locks 
    // the lock but returns the _previous_ lock value. 
    // If (and only if) the previous lock value was 1 then the lock was
    // **already** locked by another thread or process, so we stay in the
    // loop and retry.
    // When the previous lock value was 0, that indicates the 
    // lock was **not** locked before we locked it.  It **is** locked now
    // because _we_ locked it, so we own the lock and can exit the spinloop.
    while (test_and_set(&lock) == 1);  

    critical section  // only one process can be in this section at a time

    // Release the lock when finished with the critical section.
    // It was 1 (because we locked it). 
    // Any other process that "changed" it since then
    // was not in the critical section, so the
    // other processes also set it to 1, but
    // did not obtain the lock or enter the
    // critical section, and (either gave up or)
    // are still waiting in their own spinloops.
    lock = 0;  
}
</syntaxhighlight>
The lock variable is a shared variable i.e. it can be accessed by all processors/threads. Note the ''[[Volatile variable|volatile]]'' keyword. In absence of volatile, the compiler and/or the CPU(s) may optimize access to lock and/or use cached values, thus rendering the above code erroneous. Conversely, and unfortunately, the presence of ''volatile'' does ''not'' guarantee that reads and writes are committed to memory. Some compilers issue [[memory barrier]]s to ensure that operations are committed to memory, but since the semantics of ''volatile'' in C/C++ is quite vague, not all compilers will do that. Consult your compiler's documentation to determine if it does.

This spin lock function can be called by multiple processes, but it is guaranteed that only one process will be in the [[critical section]] at a time. The rest of the processes will keep spinning until they get the lock. It is possible that a process is never granted the lock. In such a case it will loop endlessly. This is a drawback of a spin lock implementation as it doesn't ensure fairness. These issues are further elaborated in the [[Test-and-set#Performance evaluation of test-and-set locks|performance section]].

=== Assembly implementation ===
<syntaxhighlight lang="nasm">
enter_region:        ; A "jump to" tag; function entry point.

  tsl reg, flag      ; Test and Set Lock; flag is the
                     ; shared variable; it is copied
                     ; into the register reg and flag
                     ; then atomically set to 1.

  cmp reg, #0        ; Was flag zero on entry_region?

  jnz enter_region   ; Jump to enter_region if
                     ; reg is non-zero; i.e.,
                     ; flag was non-zero on entry.

  ret                ; Exit; i.e., flag was zero on
                     ; entry. If we get here, tsl
                     ; will have set it non-zero; thus,
                     ; we have claimed the resource
                     ; associated with flag.

leave_region:
  move flag, #0      ; store 0 in flag
  ret                ; return to caller
</syntaxhighlight>

Here <code>tsl</code> is an atomic instruction and <code>flag</code> is the lock variable. The process doesn't return unless it acquires the lock.