Editing Test-and-set (section)

== Software implementation of test-and-set ==
Some instruction sets have an atomic test-and-set machine language instruction. Examples include [[x86]]<ref>{{Cite web|url=http://www.felixcloutier.com/x86/BTS.html|title=BTS—Bit Test and Set|website=www.felixcloutier.com|access-date=2016-11-21}}</ref> and [[IBM System/360]] and its successors (including [[z/Architecture]]).<ref>{{Cite web|url=http://www.ibm.com/support/knowledgecenter/SSB23S_1.1.0.13/gtpc3/tasinst.html|title=IBM Knowledge Center|website=www.ibm.com|access-date=2016-11-21}}</ref>
Those that do not can still implement an atomic test-and-set using a [[read-modify-write]] or [[compare-and-swap]] instruction.

The test and set instruction, when used with boolean values, uses logic like that shown in the following function, except that the function must execute [[atomic (computer science)|atomically]]. That is, no other process must be able to interrupt the function mid-execution, thereby seeing a state that only exists while the function executes. That requires hardware support; it cannot be implemented as shown. Nevertheless, the code shown helps to explain the behaviour of test-and-set.  NOTE: In this example, 'lock' is assumed to be passed by reference (or by name) but the assignment to 'initial' creates a new value (not just copying a reference).

 '''function''' TestAndSet(boolean_ref lock) {
     boolean initial = lock;
     lock = true;
     '''return''' initial;
 }

Not only is the code shown not atomic, in the sense of the test-and-set instruction, it also differs from the descriptions of DPRAM hardware test-and-set above. Here, the value being set and the test are fixed and invariant, and the value is updated regardless of the outcome of the test, whereas for the DPRAM test-and-set, the memory is set only when the test succeeds, and the value to set and the test condition are specified by the CPU.  Here, the value to set can only be 1, but if 0 and 1 are considered the only valid values for the memory location, and "value is nonzero" is the only allowed test, then this equates to the case described for DPRAM hardware (or, more specifically, the DPRAM case reduces to this under these constraints).  From that viewpoint, this can, correctly, be called "test-and-set" in the full, conventional sense of that term.  The essential point to note is the general intent and principle of test-and-set: a value is both tested and set in one atomic operation such that no other program thread or process can change the target memory location after it is tested but before it is set. (This is because the location must only be set if it currently has a certain value, not if it had that value sometime earlier.)

In the [[C (programming language)|C programming language]], the implementation would be like:
<syntaxhighlight lang="c">
#define LOCKED 1

int test_and_set(int* lockPtr) {
    int oldValue;

    // -- Start of atomic segment --
    // This should be interpreted as pseudocode for illustrative purposes only.
    // Traditional compilation of this code will not guarantee atomicity, the
    // use of shared memory (i.e., non-cached values), protection from compiler
    // optimizations, or other required properties.
    oldValue = *lockPtr;
    *lockPtr = LOCKED;
    // -- End of atomic segment --

    return oldValue;
}
</syntaxhighlight>

The code also shows that there are really two operations: an atomic read-modify-write and a test. Only the read-modify-write needs to be atomic.  (This is true because delaying the value comparison by any amount of time will not change the result of the test once the value to test has been obtained.  Once the code writes the initial value, the result of the test has been established, even if it has not been computed yet — e.g., by the == operator.)