Sleeping Instead of Spinning: Queue-Based Locks

1. Why Spinning and Yielding Are Not Enough

Earlier locking approaches had serious drawbacks:

Spin locks

• Waste CPU cycles by busy waiting

• Terrible on single-CPU systems

• Can cause priority inversion

• No fairness → starvation possible

Yield-based locks

• Reduce spinning

• Still cause many context switches

• Still no control over which thread gets the lock next

• Starvation still possible

Core Problem

The scheduler decides who runs next — not the lock.

If the scheduler makes poor decisions, threads either spin or yield repeatedly, wasting time and still not guaranteeing fairness.

---

2. Key Idea: Explicit Control with Queues

The solution is to explicitly control who gets the lock next.

👉 Instead of:

• Spinning (wasting CPU), or

• Yielding randomly (scheduler decides),

we:

• Put waiting threads to sleep

• Maintain a queue of waiting threads

• Wake up exactly one thread when the lock is released

This requires OS support.

---

3. Required OS Support

The solution uses two OS primitives (as in Solaris):

Primitive	Purpose
park()	Put the calling thread to sleep
unpark(threadID)	Wake up a specific thread

These allow threads to block instead of spinning.

---

4. Data Structures Used

typedef struct __lock_t {
    int flag;        // Is the lock held?
    int guard;       // Spinlock protecting lock metadata
    queue_t *q;      // Queue of waiting threads
} lock_t;

Meaning of Fields

• flag

  • 0 → lock is free

  • 1 → lock is held

• guard

  • A small spin lock protecting flag and the queue

  • Held only for a few instructions

• queue

  • Stores thread IDs of waiting threads

  • Ensures FIFO ordering → fairness

---

5. How Lock Acquisition Works

Step-by-Step (lock())

1. Acquire the guard spin lock (very short critical section)

while (TestAndSet(&m->guard, 1) == 1)
    ;   // acquire guard (short spin)

---

If the lock is free:
Acquire it
Release the guard
Enter critical section
if (m->flag == 0) {
    m->flag = 1;
    m->guard = 0;
}

---

If lock is held:
Add yourself to the waiting queue
Release the guard
Go to sleep (park)

else {
    queue_add(m->q, gettid());
    m->guard = 0;
    park();
}

✅ No spinning
✅ No yielding loops
✅ No CPU waste

---

Diagram: Lock Acquisition

Thread T1 holds lock
Thread T2 arrives
↓
Queue: [T2]
T2 → park() → SLEEP

---

6. How Lock Release Works

Step-by-Step (unlock())

1. Acquire the guard lock

while (TestAndSet(&m->guard, 1) == 1)
    ;   // acquire guard

---

If no waiting threads:
Simply free the lock
if (queue_empty(m->q))
    m->flag = 0;

---

If threads are waiting:
Wake exactly one thread from the queue
Lock ownership is passed directly to it
else
    unpark(queue_remove(m->q));

---

m->guard = 0;

4. Release the guard

---

Diagram: Lock Release

Queue: [T2, T3]
T1 unlocks
↓
unpark(T2)
T2 runs immediately holding lock

---

7. Why flag Is NOT Set to 0 in This Case

This is subtle but crucial.

• The awakened thread resumes after park()

• It does not re-enter lock()

• So it never sets flag = 1

👉 Therefore, the lock is passed directly
from the unlocking thread to the next thread.

This avoids races and extra locking overhead.

---

8. Why a Guard Spinlock Is Still Used

You might notice:

“Wait — aren’t we still spinning?”

Yes, but only briefly.

• Guard protects very small critical sections

• Only a few instructions

• No user code inside

✅ This is acceptable
❌ Spinning on long critical sections is not

---

9. Avoiding Starvation

This approach explicitly avoids starvation:

• Threads are queued

• FIFO order is enforced

• Each waiting thread will eventually run

✔ Mutual exclusion
✔ Progress
✔ Bounded waiting

---

10. Wakeup/Waiting Race (Important Detail)

The Problem

A thread might:

1. Add itself to the queue

2. Get interrupted

3. Another thread releases the lock and calls unpark

4. Then the first thread calls park() → sleeps forever

Solution: setpark()

queue_add(m->q, gettid());
setpark();
m->guard = 0;

• Signals intent to sleep

• Ensures park() won’t miss a wakeup

---

11. Priority Inversion (Why This Helps)

Spin locks can cause priority inversion:

• High-priority thread spins

• Low-priority thread holds lock but never runs

Sleeping locks:

• Block waiting threads

• Allow scheduler to run lock holder

• Can work with priority inheritance

---

12. Big Picture Summary

Approach	CPU Waste	Fairness	Starvation
Spin lock	High	No	Yes
Yield lock	Medium	No	Yes
Queue + sleep	Low	Yes	No

---

13. Key  Takeaways

• Queue-based locks sleep instead of spin

• Require OS primitives (park, unpark)

• Maintain explicit wait queues

• Ensure fairness and prevent starvation

• Used in real systems (Solaris, Linux futexes)

• Spinning is limited to very short guard sections