Yield-Based Locks

 

Lock with Yield: “Just Yield, Baby!”

1. Why Do We Need Yield-Based Locks?

From earlier sections, we learned that:

• Spin locks waste CPU time when a thread spins while holding no useful work

• The problem is worst on a single CPU

• If the lock holder is preempted, other threads spin endlessly

So the big question is:

Instead of spinning uselessly, can a waiting thread give up the CPU?

This leads to the yield-based lock idea.

---

2. Basic Idea of Yield-Based Locking

The key idea is very simple:

👉 If a thread cannot acquire the lock, it voluntarily yields the CPU instead of spinning.

This avoids wasting CPU cycles checking the lock repeatedly.

---

3. The Code (Conceptual View)

void lock() {
    while (TestAndSet(&flag, 1) == 1)
        yield();   // give up the CPU
}

void unlock() {
    flag = 0;
}

What is happening?

• TestAndSet() atomically checks and sets the lock

• If the lock is already held (flag == 1)

• The thread calls yield() instead of spinning

---

4. What Does yield() Do?

yield() is an operating system primitive.

• Moves the thread from running → ready

• The thread deschedules itself

• Another thread is allowed to run

Thread states involved:

RUNNING  --yield()-->  READY

This is very different from spinning, where the thread stays running and wastes CPU time.

---

5. Why Yield Helps (Simple Case)

Two threads on one CPU

1. Thread A acquires the lock and enters the critical section

2. Thread A is preempted

3. Thread B tries to acquire the lock

4. Lock is held → Thread B calls yield()

5. Thread A runs again, exits the critical section, releases the lock

6. Thread B can now acquire the lock

✅ Result:

• No spinning

• No wasted CPU cycles

• Works well for small systems

---

6. The Problem with Many Threads

Now consider a system with 100 threads contending for the same lock.

What happens?

1. One thread holds the lock and is preempted

2. The other 99 threads:

   • Run one by one

   • Try to acquire the lock

   • Fail

   • Call yield()

This causes:

• 99 context switches

• Each context switch is expensive

• CPU time is still wasted (just less obviously than spinning)

---

Comparison with Spin Locks

Approach	Waste Type
Spin lock	Wastes CPU cycles spinning
Yield-based lock	Wastes CPU time on context switches

Yield is better than spinning, but still inefficient at scale.

---

7. Starvation Problem (Major Weakness)

The yield-based lock does not guarantee fairness.

What can go wrong?

• A thread may repeatedly:

  • Try to acquire the lock

  • Fail

  • Yield

• Meanwhile, other threads:

  • Acquire the lock

  • Release it

  • Reacquire it

🚨 Result:
A thread may starve indefinitely, stuck in a yield loop.

---

8. Why Yield Alone Is Not Enough

The yield-based approach:

✅ Reduces spinning
✅ Helps in simple cases
❌ Causes many context switches
❌ Does not prevent starvation
❌ Still wastes CPU time under heavy contention

That’s why the text concludes:

We need an approach that directly addresses starvation.

This motivates:

• Sleeping locks

• Queue-based locks

• OS-managed blocking mechanisms

---

9. Key Takeaways 

• Yield-based locks replace spinning with voluntary CPU yielding

• yield() moves a thread from running to ready state

• Works well for small numbers of threads

• Performs poorly with many contending threads

• Does not guarantee fairness

• Starvation is still possible

• Better than spinning, but not the final solution