Atomic Operations with Test-and-Set

The Problem with Simple Software Locks

Let's first revisit why a naive software approach to locking fails. Imagine we use a shared boolean variable, lock, initialized to false. A process wanting to enter the critical section might do this:

// Initial shared state:
boolean lock = false;

// Entry section for a process:
while (lock == true) {
    // do nothing, spin
}
lock = true; // acquire the lock

// --- CRITICAL SECTION ---

// Exit section:
lock = false; // release the lock

On the surface, this looks plausible. However, given your background in concurrent systems, you can likely spot the race condition. A process could read lock as false, get preempted by the scheduler before it sets lock to true, and another process could then do the same.

To see this failure in action, let's watch a short video that clearly illustrates this exact problem.

This failure happens because testing the lock and setting it are two separate instructions. To solve this, we need them to be a single, atomic operation. This is where hardware support comes in.

The Test-and-Set Atomic Instruction

The Test-and-Set instruction is a hardware-level operation that solves the problem above by making the act of testing and setting a lock indivisible. From the CPU's perspective, once a Test-and-Set instruction begins, it will finish without any other instruction (or process on another core) interfering with the memory location it's working on.

Here's how it's defined logically:

boolean TestAndSet(boolean *target) {
    boolean original_value = *target; // Atomically read the original value
    *target = true;                    // Atomically set the new value to true
    return original_value;             // Return the original value
}

The key is that the entire body of this function is executed atomically by the hardware.

Now, a process can use this instruction in its entry section like this:

// Entry section
while (TestAndSet(&lock) == true) {
    // spin, the lock was already set
}

// --- CRITICAL SECTION ---

// Exit section
lock = false;

Let's trace this:

1. First Process (P1): lock is initially false. P1 calls TestAndSet(&lock).
   • The instruction atomically reads the value false.
   • It atomically sets lock to true.
   • It returns the original value, false.
   • The while loop condition (false == true) is false, so P1 breaks the loop and enters the critical section.
2. Second Process (P2) arrives: lock is now true. P2 calls TestAndSet(&lock).
   • The instruction atomically reads the value true.
   • It atomically sets lock back to true (no change).
   • It returns the original value, true.
   • The while loop condition (true == true) is true, so P2 stays in the loop, "spinning" until the lock is released.

The video you started watching provides an excellent walkthrough of this exact logic.

This hardware-level approach is often represented in a form closer to assembly language, highlighting its nature as a single, indivisible CPU instruction.

Analyzing Test-and-Set's Correctness

Now for the critical part of your GATE preparation: evaluating this solution against the three necessary conditions for a correct critical section solution.

1. Mutual Exclusion: Is it satisfied?

   • Yes. As our trace showed, the atomic nature of Test-and-Set guarantees that only one process can ever receive false from the function call at any given time. Any subsequent process will receive true and be forced to wait.

2. Progress: Is it satisfied?

   • Yes. If the critical section is free (lock is false), and a process wishes to enter, it will call Test-and-Set, get false back, and proceed. The decision to enter is not postponed indefinitely.

3. Bounded Waiting: Is it satisfied?

   • No. This is the crucial limitation of the basic Test-and-Set implementation. If multiple processes are spinning on the lock, the hardware gives no guarantee about which one will get to acquire the lock next when it is released. It's a free-for-all. A process could, in theory, be unlucky and repeatedly lose the race to other processes, leading to starvation.

The following video provides a concise analysis of these three properties.

Test-and-Set and Schedulers: A GATE-Level Problem

The most interesting—and testable—scenarios arise when you consider how a low-level spinlock (built with Test-and-Set) interacts with a high-level OS scheduler.

Consider the following GATE-style problem:

Two processes, a High-Priority Process (HPP) and a Low-Priority Process (LPP), use a Test-and-Set spinlock. A preemptive priority scheduler is being used.

Scenario:

1. The LPP starts running and successfully acquires the lock (TestAndSet returns false). It enters the critical section.
2. While the LPP is in its critical section, the HPP becomes ready to run.
3. The scheduler immediately preempts the LPP and schedules the HPP.
4. The HPP now tries to acquire the lock by spinning on while(TestAndSet(&lock));.

What will happen in this system?

Think about it for a moment. The HPP is spinning, waiting for the lock. The LPP holds the lock but cannot run to release it. This creates a classic deadlock situation known as priority inversion. The high-priority process is stuck waiting for a lower-priority process that will never be scheduled.

Now, what if we used a Round-Robin scheduler instead? In that case, the HPP would spin for its time slice, and then the scheduler would preempt it and give the CPU back to the LPP. The LPP would then be able to finish its critical section and release the lock, resolving the contention.

This interaction is a key concept. Let's solidify this by reading a well-written explanation of this exact problem.

Conclusion

In this lesson, we made the jump from software to hardware-assisted synchronization. You've learned how a single atomic instruction, Test-and-Set, can elegantly solve the critical section problem where simpler software locks fail.

Key Takeaways:

• Atomicity is Key: The fundamental problem with software locks is the race condition between checking a lock's value and changing it. Atomic hardware instructions like Test-and-Set solve this by making these two steps an indivisible operation.
• Properties of Test-and-Set: It successfully provides Mutual Exclusion and Progress.
• Limitation of Test-and-Set: It does not provide Bounded Waiting, which can lead to starvation as there's no guarantee which waiting process will get the lock next.
• System-Level Interaction: The use of Test-and-Set for busy-waiting (a spinlock) can lead to serious problems like deadlock when combined with certain scheduling policies, such as priority scheduling.

We've seen that Test-and-Set is a powerful primitive, but its basic implementation leads to busy-waiting, which wastes CPU cycles, and it doesn't solve starvation. In our next lesson, we will build upon this foundation to explore Mutex Locks. We will see how an operating system can use instructions like Test-and-Set to create more sophisticated locking mechanisms that can avoid busy-waiting by putting waiting processes to sleep.