Building Spin locks Using Test-and-Set

 

Building Spin locks Using Test-and-Set

1. What is a Spin lock?

A spin lock is a simple synchronization mechanism used to protect a critical section.

When a thread wants to enter a critical section:

• It keeps checking (spins) until the lock becomes available.

• Once the lock is free, the thread acquires it and enters the critical section.

• After finishing, the thread releases the lock so others can enter.

Spinlocks are called spin locks because waiting threads busy-wait instead of sleeping.

---

2. Why Do We Need Hardware Support?

Simple software solutions (like Peterson’s solution) may fail on modern processors due to:

• Instruction reordering

• Multiple cores executing in parallel

To guarantee correctness, we rely on atomic hardware instructions. One of the most important of these is test-and-set.

---

3. The Test-and-Set Instruction

The test-and-set instruction performs two actions atomically (as one uninterruptible operation):

1. It reads the current value of a memory location.

2. It sets that memory location to true.

A simplified definition is:

boolean test_and_set(boolean *target) {
    boolean old = *target;
    *target = true;
    return old;
}

• The key idea: no other thread can interrupt this operation

• Even on multicore systems, test-and-set executes safely

---

4. Building a Spin lock with Test-and-Set

We use a shared boolean variable called lock:

boolean lock = false;

• false → lock is free (0)

• true → lock is held by some thread (1)

Lock Acquisition

while (test_and_set(&lock))
    ;   // busy waiting

• If lock was false, test-and-set returns false

  • The thread acquires the lock

• If lock was true, test-and-set returns true

  • The thread keeps spinning

Critical Section

/* critical section */

Only one thread can be here at a time.

Lock Release

lock = false;

This allows another waiting thread to acquire the lock.

---

5. Why This Works (Correctness)

✅ Mutual Exclusion

• Only one thread can change lock from false to true

• Atomic test-and-set prevents simultaneous entry

⚠ No Bounded Waiting

• Threads may spin indefinitely

• Some threads may starve if unlucky

⚠ Busy Waiting

• Threads waste CPU cycles while waiting

• Not efficient on single-core systems

---

6. When Are Spinlocks Useful?

Spinlocks are most useful when:

• The critical section is very short

• The system has multiple CPU cores

• Context switching would cost more than spinning

Rule of thumb:
Use a spinlock if the lock will be held for less time than a context switch.

---

7. Advantages and Disadvantages

Advantages

• Simple to implement

• No context-switch overhead

• Efficient for short critical sections

Disadvantages

• Wastes CPU time (busy waiting)

• Can cause starvation

• Poor choice for long critical sections

---

8. Summary

• Test-and-set is a hardware-supported atomic instruction

• It allows us to build spin locks

• Spinlocks ensure mutual exclusion

• Best suited for short critical sections on multicore systems