We noted in Section 13.3.2 that several processors, including the ARM, MIPS, and Power, provide an alternative to compare_and_swap (CAS) known as load_linked/store_conditional (LL/SC). A load_linked instruction loads a memory location into a register and stores certain bookkeeping information into hidden processor registers. A store_ conditional instruction stores the register back into the memory location, but only if the location has not been modified by any other processor since the load_linked was executed. Like compare_and_swap, store_ conditional returns an indication of whether it succeeded or not.

(a) Rewrite the code sequence of Example 13.29 using LL/SC.

(b) On most machines, an SC instruction can fail for any of several “spurious” reasons, including a page fault, a cache miss, or the occurrence of an interrupt in the time since the matching LL. What stepsmust a programmer take to make sure that algorithms work correctly in the face of such failures?

(c) Discuss the relative advantages of LL/SC and CAS. Consider how they might be implemented on a cache-coherent multiprocessor. Are there situations in which one would work but the other would not?