Hardware Solution to Synchronization: (Test & Set)
The critical problem can be solved in a single-processor system at hardware level. We can stop interrupts to occur during modification of a shared variable so that the instruction can be executed without preemption. This solution is not applicable in multi-processor system because disabling of interrupts is time-consuming.
Many machines provide hardware instruction to test and modify a word and swap
the contents of words atomically without any interruption. The TestAndSet
instruction is executed atomically.
The definition of TestAndSet is as follows:
boolean TestAndSet (boolean &target)
{
boolean rv = target;
target = true;
return rv;
}
A machine that supports TestAndSet instruction, can implement mutual exclusion by using a Boolean variable lock, initialized to false. The structure of such implementation is as follows:
while (1)
{
while (TestAndSet(Iock));
critical section;
lock = false;
remainder section;
}
The Swap instruction is also executed atomically and operates on two word to
interchange their contents.
The definition of Swap is as follows:
void Swap(boolean &a, boolean &b)
{
boolean temp = a;
a = b;
b = temp;
}
The implementation of TestAndSet is as follows:
while (1)
{
waiting[I] = true;
key = true;
while (waiting[l] && key)
key = TestAndSet(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;
}
Proof
- Mutual Exclusion: Here, Pi can enter its critical section only if either waiting[i] is true or key is false. The value of key can be false only if
TestAndSet instruction is executed. When a process executes, it will find key =
false. The remaining processes will have to wait. The value of waiting[i] can be
false only if another process leaves its critical section: In this way, only one
waiting[i] is false, which maintains mutual exclusion.
- Progress: A process that leaves its critical section either sets lock to false
or sets Waiting[j] to false. It allows a waiting process to enter its critical
section.
- Bounded Waiting: A process that leaves its critical section, visits
the array in a cycle and finds out any process with waiting[j] = true. It
designates that process to enter its critical section. The selected process will
also do so when leaving its critical section.
|
