Question

(a) Write the assembly code to implement an atomic compare&swap using load-linked and store-conditional. Compare&swap(r1,r2,x) works as follows: Typically r1 is 0 (for unlocked) and r2 is 1 (for locked)

If (r1 == MEM[x]) then { r2 = MEM[x]

MEM[x] = r2

}

FYI: atomic swap is implemented in some systems (e.g., IBM POWER and Intel x86).

(b) Test-and-set incurs high traffic while spin waiting. What happens to compare&swap?

Answer 1

(a)

```assembly

CompareAndSwap:

LL r3, 0(r1) // Load r3 with the value at MEM[x]

CMP r3, r2 // Compare r3 with r2 (expected value)

BNE CompareAndSwap // If not equal, retry

SC r4, 0(r1) // Store r4 (new value) to MEM[x]

BNE CompareAndSwap // If store-conditional fails, retry

// At this point, the swap is successful

// r1 contains the original value at MEM[x]

// r2 contains the new value (r4)

// Further processing can be added here

```

(b)

The compare&swap (CAS) operation reduces traffic compared to test-and-set (TAS) while spin waiting. TAS continuously polls the lock, causing high bus traffic. In contrast, CAS only updates the value if the expected condition is met, minimizing unnecessary bus transactions. CAS enhances efficiency by avoiding contention on the memory bus during spin waiting, making it a more scalable solution for synchronization in multi-processor systems.

Step-by-step explanation:

In the provided assembly code for compare&swap (CAS), the LL (Load-Linked) instruction loads the current value at MEM[x] into register r3. The CMP (Compare) instruction checks if the loaded value (r3) is equal to the expected value (r2). If the values match, the SC (Store-Conditional) instruction stores the new value (r4) in MEM[x]. If the store-conditional operation is successful, the CAS operation is complete.

CAS minimizes bus traffic during spin waiting by only updating the memory when the expected condition is met. This is in contrast to TAS, which continuously polls the lock, causing high bus traffic even when no update is needed. CAS's efficiency stems from its ability to perform the update atomically, reducing contention on the memory bus and making it suitable for scalable synchronization in multi-processor systems.

In summary, CAS provides a more efficient approach to synchronization compared to TAS, especially in scenarios with high contention, as it minimizes unnecessary bus transactions during spin waiting.