johnl@iecc.cambridge.ma.us (John R. Levine) (04/24/91)
In article <1991Apr23.184737.15377@dvorak.amd.com> you write: >[How to implement CAS on a MIPS, and then ...] >On a side note, I think the only real benefit of the compare-and-swap over >the more simpler test-and-set is that it semantically defines when the write >is to take place. Compare and swap is fundamentally more powerful. With CAS you can implement wait-free interlocking with arbitrarily many contending processors for such operations as allocating buffers from a pool or linking request blocks into a queue. Test and set doesn't let you implement wait-free interlocks at all for more than two processes, it's mostly only good for spin locks. There is an interesting article by Maurice Herlihy in the January TOPLAS comparing the ability of various constructs to implement wait-free synchronization, and it turns out that nothing he looked at weaker than compare and swap is adequate to synchronize arbitrarily many processes without waiting. (The only other one he found was atomically updated queues with peeking at the top entry, a lot more complex than compare and swap.) In many cases, the penalty for spin locks is low, because you only lock a small straight-line piece of code, but not always. For one thing, it's not always desirable to lock out all interrupts during a locked section, since the cost of turning interrupts on and off may be considerably greater than that of the locked code, particularly if the code is running as part of a user program. If the lock is in a user program, there is also the possibility that the operating system will time-slice, page, swap, or otherwise slow down the locked code at an inconvenient time. In any system, there is always the possibility that one process or processor will crash, and spin locks make it a lot harder to recover from crashes. Regards, John Levine, johnl@iecc.cambridge.ma.us, {spdcc|ima|world}!iecc!johnl