The critical-section problem can be addressed using various techniques, including hardware solutions that simplify programming tasks and enhance system efficiency. Software-based solutions like Peterson’s algorithm are not always reliable on modern computer architectures. Hardware instructions help solve the critical-section problem by using locks to protect critical regions.
Simple Hardware Instructions
In a single-processor environment, the critical-section problem could be solved by preventing interrupts while a shared variable is being modified. This ensures the current sequence of instructions executes without preemption, making the kernel nonpreemptive. However, this approach is impractical in multiprocessor environments due to the time-consuming process of disabling interrupts across multiple processors, which degrades system efficiency.
Many modern systems provide special hardware instructions to test and modify the content of a word or swap the contents of two words atomically (i.e., as one uninterruptible unit). These instructions can simplify the solution to the critical-section problem. Two such instructions are test and set() and compare and swap().
Test and Set Instruction
The test and set() instruction can be defined as follows:
boolean test_and_set(boolean *target) {
boolean rv = *target;
*target = true;
return rv;
}
Definition of the test and set() instruction.
The key characteristic of this instruction is that it executes atomically. If two test and set() instructions are executed simultaneously on different CPUs, they will be executed sequentially in some arbitrary order. With this instruction, mutual exclusion can be implemented by declaring a boolean variable lock, initialized to false. The process structure is as follows:
do {
while (test_and_set(&lock))
; /* do nothing */
/* critical section */
lock = false;
/* remainder section */
} while (true);
Mutual-exclusion implementation with test and set().
Compare and Swap Instruction
The compare and swap() instruction operates on three operands and is defined as follows:
int compare_and_swap(int *value, int expected, int new_value) {
int temp = *value;
if (*value == expected)
*value = new_value;
return temp;
}
Definition of the compare and swap() instruction.
This instruction also executes atomically. Mutual exclusion can be provided by declaring a global variable lock initialized to 0. The first process to invoke compare and swap() sets lock to 1 and enters its critical section. Other processes will not succeed until lock is reset to 0. The process structure is as follows:
do {
while (compare_and_swap(&lock, 0, 1) != 0)
; /* do nothing */
/* critical section */
lock = 0;
/* remainder section */
} while (true);
Mutual-exclusion implementation with compare and swap().
Bounded-Waiting Mutual Exclusion
While test and set() and compare and swap() provide mutual exclusion, they do not satisfy the bounded-waiting requirement. A modified algorithm using test and set() can meet all critical-section requirements. The common data structures are:
boolean waiting[n];
boolean lock;
These are initialized to false. The process structure is:
do {
waiting[i] = true;
key = true;
while (waiting[i] && key)
key = test_and_set(&lock);
waiting[i] = false;
/* critical section */
j = (i + 1) % n;
while ((j != i) && !waiting[j])
j = (j + 1) % n;
if (j == i)
lock = false;
else
waiting[j] = false;
/* remainder section */
} while (true);
Bounded-waiting mutual exclusion with test and set().
This algorithm ensures mutual exclusion, progress, and bounded-waiting. When a process leaves its critical section, it scans the waiting array in cyclic order to find and designate the next process to enter the critical section. Any process waiting will enter its critical section within n - 1 turns.
BCABSCNOTES 