operating-systems hardware concurrency
Definition
Test-and-Set
Test-and-set is a hardware instruction that provides atomic read-modify-write access to a memory location. It ensures that the operations of reading a value, testing it, and setting it to a new value are performed as a single, ununterruptable unit.
This atomicity is essential for implementing mutual exclusion in multiprocessor environments.
Mechanism
The logic of the testset function can be described as follows:
function testset (var i: integer): boolean;
begin
if i = 0 then
begin
i := 1;
return true; // Success: lock acquired
end
else return false; // Failure: lock was already held
end;Implementation of Mutual Exclusion
Using the testset instruction, a simple spinlock can be implemented for an arbitrary number of processes:
// global variable: var b: integer; (initialised to 0)
// Process Pi:
while not testset (b) do nothing; // Busy Waiting
// --- Critical Section ---
b := 0; // Release lock
// --- Remainder Section ---Characteristics
- Simplicity: Provides a very simple entry protocol for critical sections.
- Starvation: While it ensures mutual exclusion, it does not guarantee bounded waiting, as the order in which processes acquire the lock is determined by hardware arbitration rather than a queue.