TL;DR:
TS, CAS and CAS2 work thru bus locking
CAS2 was introduced with the '020, the '030 had to have it for compatibility
While the 'cost' of locking for a complex operation is high, it's not higher than for simpler versions doing the same
CAS2 is overall more performant than a series of CAS/TS instructions
[While all 4 points are valid, the second would rectify the effort on its own]
The Long Read:
The CAS2 instruction [...] for making lock-free and wait-free data structures
Not really. CAS2, like CAS and all similar, are locking instructions. For them to perform they need to make sure that no other access to the memory locations in question happens during execution.
The are not only atomic within the CPU but in relation to memory as well. For simple write operations these is done by such an operation being already atomic on memory. For more complex the CPU has to
lock the memory region before/with reading and keep locked until the last related write is done.
Or, more general, lock all of memory access during that time
Or, most 'primitive' way, with the assumption of the bus system being the only way to access memory for all components in a system doing so.
68k CPUs do exactly the last approach, they take and lock the bus during such a read/modify/write operation.
- For early (68000) versions TS as a byte wide operation was the only such and locking was done by applying Address Strobe low over the whole read and write cycle.
This worked fine as it's one and the same address that got read and written, no address change was needed, so AS could be used to lock the bus, saving the need for a dedicated RMW-Lock Signal (*1)
- Later, with CAS2 multiple addresses had to be read/written, thus AS was needed to signal each address, requiring the introduction of RMC (Read Modify Cycle) as a locking signal.
But it is also extremely expensive, as it must atomically compare two different memory locations against two registers and proceed to update them (still under the atomic constraint) both if and only if both comparisons are equal.
Per se, not expensive at all. It's a simple sequence of memory access operation. What you may think about here is effort in cache handling (as mentioned).
For a number of reasons, including that it would totally nuke performance on a multicore due to the synchronization required.
No it doesn't - or more exact, not more as any other atomic memory operation does. Each TAS has the same issues regarding to multiple cores and memory caching.
But it was implemented in the 68030 and 68040!
A 030 not compatible with the preceding 020 would have been a bad sell, wouldn't it?
So my question is: How, circa the late 1980s (the 68030 was introduced in '87, development must have started at least a year earlier?) did Motorola's engineers (and program managers) come to decide that such an unusual and expensive operation was desirable in their chip?
It was already part of the 68020 instruction set - sold as a high performance feature for modern 32 bit OSes. So any 030 design was bound to support it as well - unless Motorola was inclined to get bad press that important instructions at the core of modern OS management had to be replaced by some slower emulation or worse, existing OS couldn't run straight away on the newer faster chip.
what specific use case(s) did they have in mind
Exactly what you think about: handling linked lists in a most performant way. After all, they are at the core of data handling past the most trivial. Having CAS2 can speed up everything from task switch to data base caching.
(Apparently the first published research AFAIK to use CAS2 (aka DCAS) was in 1991 (Massalin, Pu. A lock-free multiprocessor OS kernel, TR, Columbia University, June 1991); publications on lock free data structures using CAS or LL/SC started around 1991 and interest in DCAS came later, I believe. There was quite a lot of academic research interest in DCAS in the early 90's.)
Are you sure? CAS style instructions date back to the 1960s. IBM introduced CS (Compare and Swap) with the /370 for all machines in 1970 (*2, *3). CAS2 like operations were as well available on other computers. For example the Siemens X-Series CPUs (/370 based) had a linked list operations (EXST - Execute Stack) that could do the same as CAS2 plus a few more steps like following a linked list until the insertion point was found.
And all of that was done of course in multi processor environments. Heck, that's where the real additional value is gained - let the hardware do synchronisation, not slow software.
The mentioned linked list operations (EXST) extreme potent compared with simple TS and CS operation. Not just in theory but very obvious in practical usage. When the OS finally got modified to take advantage of these instructions, an over all performance increase of OS functions of up to 20% could be seen. Most within the lowest level and thus most often needed ones. After all, an OS is most of it's time occupied with book keeping, mostly walking (*4) and rearranging lists.
So for the performance argument often made against operations like CAS2, is is only true when looking at the single operation compared to what others cost but not looking at the gain realized. Yes, they need to synchronize memory between cache levels and CPUs, but so does each and every 'simple' CAS. But in contrast to a series of CAS that are needed to replace a CAS2, that CAS2 will use less resources.
*1 - Intel type bus uses bus lock anyway.
*2 - It was available on certain /360 before.
*3 - By having the 68020 add a CS to the 68000 TS, Motorola more or less just copied IBM move here a decade later as the /360 had a TS (Test and Set) instruction first, to be complemented by CS with the /370.
*4 - The reason why several early CPUs had an indirect addressing feature using a bit within an address word to indicate that another addressing cycle is to be used to follow that address. It removes all the overhead of looping thru a series of high level instructions when all that's needed is a sequence of memory access cycles.
