IBM 610 workstation computer 3412

one of the issues may be that some state involves syncronous updating of multiple memory locations ... sort of like an update in databases where there is transfer from one account to another, the account record that is debited and the account record that is credited need to be both updated as a consistent commit.

cache coherency will make sure that an update of any single piece of data consistently occurs across all caches in the infrastructure (regargless of whether it is main memory is numa or not).

however, for kernel stuff, in uniprocessor operation ... it frequently dependent on straight-thru code end with no interruptions to achieve consistent status update involving multi-location status.

in multiprocessor operation with multiple processors potentially executing the same code ... not only do you have to prevent interruptions (in the kernel) to get consistent state update ... but you also have to make sure that any other processors aren't concurrently updating the same set of locations in an inconsistent manner.

360 had the test&set instruction that could be used for implementing locking protocols. a single storage location was defined as the lock, and the test&set instruction was a special instruction that was allowed to fetch, conditional update, and store the results in a single atomic operation. this is in contrast to most fetch-update-store instructions which allowed multi-processor race conditions ... i.e. multiple processors could fetch, update, and store the same location concurrently, the resulting location value was a race condition on which ever processor was last ... the last value would be consistent across all processors ... but the value itself wouldn't be consistent. This is the bank account scenario ... where you have an account with $1000 and three concurrent debits were happeing, all for $100 each. each debit concurrently fetched $1000, subtracted $100, and stored back $900 ... when in fact, you needed them to be individually serialized to that the final resulting value was $700 (not $900).

test&set was pretty limited instruction, mostly used for things like spin-locks. it could test a location for zero, and if it wasn't zero it would set it to non-zero (and set the condition code whether it set the value or not) ... in a single, atomic operation. simplest code as something like

TS location BNZ *-8 serialized code sequence .... ... MVI location,0

a processor would "get the lock" by changing "location" from zero to non-zero. when it was done, it would reset the value back to zero. any other processors attempting to get the same lock would "spin" (loop) on the non-zero branch until the "location" returned to zero.

the instruction is still available:

as mentioned in the above, you can now use compare-and-swap. when charlie was working at the science center on fine-grained locking for cp67 (running on 360-67), he observed that a large number of test&set useage involved serializing very short sequences of simple, single location storage update ... like push-pop top element on threaded list. he invented what was to be called compare-and-swap (we had to come up with a mnemonic that matched his initials CAS). The first pbutt at trying to get compare-and-swap added to 370 was met with rejection, the architecture red book people in POK saying that 370 didn't need any additional multiprocessor specific instructions (other than the test&set from 360). If compare-and-swap was to be added to 370, it had to have a non-multiprocessor specific use. thus we came up with the scenarios where compare-and-swap instruction in multi-threaded application code (enabled for interrupts, but equally applicable to whether running on single-processor or multi-processor configuration).

more recent description of compare-and-swap

for inclusion into 370, it was expanded to two instructions, single word atomic operation and double word operation

what use to compare-and-swap "programming notes" has since been moved to a section in the appendix on "multiprogramming and multiprocessing" examples ("multiprogramming" is mainframe for multi-threaded from at least the 60s)

lots of past posts on smp operation as well as compare-and-swap

801-RIOS (i.e. power, etc) had no provisions for cache consistency and-or atomic syncronization instructions. however, they found that some number of applications, like large database operations, had adopted the compare-and-swap paradigm for multi-threaded operations (even for single-processor operations). eventually AIX had to provide a simulation of the compare-and-swap instruction. A mnemonic was created for compare-and-swap that executed a supervisor call into the kernel that has highly optimized pathlength in the supervisor call interrupt handle (it simulated the operation of compare-and-swap semantics inside the supervisor call interrupt handler and immediately retuned to the invoking application).

--