Question

A spin lock acquire() can be implemented with a test-and- set instruction as follows:

while (test-and-set(&lock->held) == 1); // spin

Recall that test-and-set instruction returns the old value at the address while atomically setting it to 1.

A test-and-set instruction consumes more CPU cycles than an instruction that simply compares the values of memory variables. Thus, the test-and-set instruction is said expensive.

Now, suppose we implement a new lock acquire() as follows:

1: while (1) {
2: while (lock->held > 0)
3: ; // spin
4: if (test-and-set(&lock->held) == 0)
5: return;
6: }

a) Does the above new lock acquire() implementation work? Explain how the new lock acquire() operation works.
b) Is the modified lock implementation more efficient than the first one? Justify your answer.

Answer 1

a) Does the above new lock acquire() implementation work? Explain how the new lock acquire() operation works.

Answer:

Yes, the above new lock acquire() implementation works.

Working:

The lock spins until it finds the lock is free.

This is done at line 2 to line 3:

while (lock->held > 0)
// spin

Then it uses the atomic test-and-set for acquiring the lock. If the atomic lock acquisition fails, it goes back to the outer loop for trying again.

b) Is the modified lock implementation more efficient than the first one? Justify your answer.

Answer:

The behaviour of the lock has changed as follows:

This implementation will call “test-and-set” less frequently as compared to the first implementation. It spins only until it considers that the lock is free.

Therefore, this implementation is more efficient.

This implementation matches the actual implementation in the real-world locks.