Test Set Lock in Process Synchronization
When multiple processes are competing to get into a critical section, you need something that can check whether the section is free and claim it in one shot, with no gap in between for another process to sneak in. That is exactly what the Test and Set Lock does.
The Basic Concept
The whole mechanism revolves around a single shared variable called a lock. This variable can only hold one of two values:
- 0 means the critical section is free and available.
- 1 means someone is already in there and everyone else needs to wait.
When a process wants to enter the critical section, it does not just check the lock and then set it as two separate steps. It does both in a single atomic operation. This is the key detail.
If checking and setting were two separate steps, two processes could both check at the same moment, both see 0, and both set it to 1, resulting in both entering the critical section simultaneously. The atomicity prevents exactly that.
How the Operation Works
The test_and_set function saves the current value of the lock into a temporary variable, then immediately sets the lock to 1, and returns that saved value. All of this happens in one uninterrupted instruction.
bool test_and_set(bool *lock) {
bool old_value = *lock; // Save current state
*lock = true; // Set lock to 1 (locked)
return old_value; // Return what it was BEFORE
}If the returned value was 0 (false), the process knows it successfully grabbed a free lock and can proceed. If the returned value was 1 (true), the lock was already taken and the process has to keep trying.
Step by Step Flow
Process wants to enter:
1. Call test_and_set(lock)
|
+-- Returns 0 (was free) -> Lock is now 1. Process enters.
|
+-- Returns 1 (was taken) -> Lock stays 1. Process loops.
|
2. Execute critical section
|
3. Set lock = 0 -> Release. Next process can enter.The pseudocode looks like this:
do {
// Keep trying until we get the lock
} while (test_and_set(&lock) == true);
// --- Critical Section ---
lock = false; // Release the lock
// --- Remainder Section ---A Concrete Example with Two Processes
Initial: lock = 0 (free)
P1 calls test_and_set(lock)
-> old_value = 0, lock becomes 1
-> Returns 0: P1 enters critical section
P2 calls test_and_set(lock)
-> old_value = 1, lock stays 1
-> Returns 1: P2 spins (busy wait)
... P1 finishes, sets lock = 0 ...
P2 calls test_and_set(lock)
-> old_value = 0, lock becomes 1
-> Returns 0: P2 enters critical sectionFull Implementation in C++
#include <iostream>
#include <thread>
#include <atomic>
#include <chrono>
#include <vector>
std::atomic<bool> lock_var(false); // Shared lock variable
bool test_and_set(std::atomic<bool>& lock) {
return lock.exchange(true); // Atomically set to true, return old value
}
void release_lock(std::atomic<bool>& lock) {
lock.store(false); // Release the lock
}
void process(int id) {
std::cout << "Process " << id << " trying to acquire the lock." << std::endl;
// Busy wait until lock is acquired
while (test_and_set(lock_var)) {
std::cout << "Process " << id << " waiting..." << std::endl;
std::this_thread::sleep_for(std::chrono::milliseconds(100));
}
// --- Critical Section ---
std::cout << "Process " << id << " entered critical section." << std::endl;
std::this_thread::sleep_for(std::chrono::milliseconds(500));
std::cout << "Process " << id << " leaving critical section." << std::endl;
// Release the lock
release_lock(lock_var);
std::cout << "Process " << id << " released the lock." << std::endl;
}
int main() {
std::cout << "Test and Set Lock Simulation" << std::endl;
std::cout << "----------------------------" << std::endl;
std::vector<std::thread> processes;
for (int i = 1; i <= 4; i++) {
processes.push_back(std::thread(process, i));
std::this_thread::sleep_for(std::chrono::milliseconds(50));
}
for (auto& p : processes) {
p.join();
}
std::cout << "----------------------------" << std::endl;
std::cout << "All processes completed." << std::endl;
return 0;
}Output:
Test and Set Lock Simulation
----------------------------
Process 1 trying to acquire the lock.
Process 1 entered critical section.
Process 2 trying to acquire the lock.
Process 2 waiting...
Process 3 trying to acquire the lock.
Process 3 waiting...
Process 1 leaving critical section.
Process 1 released the lock.
Process 2 entered critical section.
Process 4 trying to acquire the lock.
Process 4 waiting...
Process 2 leaving critical section.
Process 2 released the lock.
Process 3 entered critical section.
...
All processes completed.Only one process is ever inside the critical section at a time. The others spin and wait until the lock is released.
Strengths and Weaknesses
| Strengths | Weaknesses |
|---|---|
| Mutual exclusion is guaranteed. The atomic nature makes it impossible for two processes to both see the lock as free at the same moment. | Busy waiting burns CPU cycles. A spinning process does nothing useful while looping. |
| Simple to understand and implement. One variable, one atomic operation. | No bounded waiting guarantee. The lock does not track who has been waiting longest. |
| Lightweight and effective for low-contention situations. | No fairness. When the lock is released, any waiting process might grab it, leading to potential starvation. |
| Hardware-supported: runs as a single CPU instruction on modern processors. | Scales poorly. High contention means many cores spinning, wasting power and memory bandwidth. |
Test-and-Set vs Other Approaches
| Aspect | Test-and-Set | Compare-and-Swap | Peterson's Algorithm |
|---|---|---|---|
| Type | Hardware atomic instruction | Hardware atomic instruction | Software algorithm |
| Processes supported | N (any number) | N (any number) | 2 only |
| Bounded waiting | No | No | Yes |
| Busy waiting | Yes | Yes | Yes |
| Flexibility | Binary lock only | Can compare and conditionally update any value | Flags + turn variable |
| Modern usage | Spinlocks, low-level kernel locks | Lock-free data structures, atomic counters | Academic and educational |
The Test and Set Lock is a hardware-supported primitive that solves the most basic requirement of synchronization: making sure only one process gets into the critical section at a time. It is fast and simple, but the lack of fairness and the busy waiting problem mean it is better suited as a building block for more sophisticated mechanisms rather than a complete solution on its own.
Test-and-Set Return Value
Question 1 of 1Test your understanding of the atomic test_and_set operation.