Synchronization hardware is a hardware-based solution to resolve the critical section problem. In our earlier content of the critical section, we have discussed how the multiple processes sharing common resources must be synchronized to avoid inconsistent results.
Well, we can synchronize the processes sharing a common variable in two ways. First is the software-based solution which includes Peterson’s solution and the second is the hardware-based solution which is also referred to as synchronization hardware or hardware synchronization.
In this context, we will discuss the two hardware-based solutions to the critical section problem. We will also discuss how these hardware solutions resolve the critical section problem.
Synchronization Hardware
Synchronization hardware i.e. hardware-based solution for the critical section problem which introduces the hardware instructions that can be used to resolve the critical section problem effectively. Hardware solutions are often easier and also improves the efficiency of the system.
Consider, a system with a single processor where just by preventing the occurrence interrupts while a shared variable is being modified can assure that only the current sequence of the instructions will be executed without any preemption.
This assures you that no unfair modifications will be made to the shared variable. This method is often used by the systems with non-preemptive kernels.
Now, consider the system with multiple processors, where disabling interrupts would require a message to be sent to all the processors which would cause unnecessary delay to the processes to enter into their critical section. This also decreases the efficiency of the system.
The hardware-based solution to critical section problem is based on a simple tool i.e. lock. The solution implies that before entering into the critical section the process must acquire a lock and must release the lock when it exits its critical section. Using of lock also prevent the race condition.
The hardware synchronization provides two kinds of hardware instructions that are TestAndSet and Swap. We will discuss each of the instruction briefly. But before jumping on to the instructions let us discuss what conditions they must verify to resolve the critical section problem.
- Mutual Exclusion: The hardware instruction must verify that at a point in time only one process can be in its critical section.
- Bounded Waiting: The processes interested to execute their critical section must not wait for long to enter their critical section.
- Progress: The process not interested in entering its critical section must not block other processes from entering into their critical section.
TestAndSet Hardware Instruction
The TestAndSet() hardware instruction is atomic instruction. Atomic means both the test operation and set operation are executed in one machine cycle at once. If the two different processes are executing TestAndSet() simultaneously each on different CPU. Still, they will be executed sequentially in some random order.
The TestAndSet() instruction can be defined as in the code below:
do {
while (TestAndSet(&lock));
// critical section
lock = FALSE;
// remainder section
} while (TRUE);
Now, as a solution to the critical section, how this TestAndSet() instruction be implemented to achieve mutual exclusion, bounded wait and progress. Let us do it one by one, first, we will try to achieve mutual exclusion using TestAndSet() instruction and for that, you have to globally declare a Boolean variable lock and initialize it to false.
Consider we have three processes P0, and P1 are interested to enter their critical section. So the structure for achieving mutual exclusion is as follow.
do {
while (TestAndSet(&lock));
// critical section
lock = FALSE;
// remainder section
} while (TRUE);
Let’s say process P0 wants to enter the critical section it executes the code above which let while loop invokes TestAndSet() instruction.
Using the TestAndSet() instruction the P0 modifies the lock value to true to acquire the lock and enters the critical section.
Now, when P0 is already in its critical section process P1 also wants to enter in its critical section. So it will execute the do-while loop and invoke TestAndSet() instruction only to see that the lock is already set to true which means some process is in the critical section which will make P1 repeat while loop unless P0 turns the lock to false.
Once the process P0 complete executing its critical section its will turn the lock variable to false. Then P1 can modify the lock variable to true using TestAndSet() instruction and enter its critical section.
This is how you can achieve mutual exclusion with the do-while structure above i.e. it let only one process to execute its critical section at a time. But this structure does not assure bounded wait as it may happen that process P0 may keep on executing its critical section again and again and P1 has to keep on waiting.
So we have another structure that will ensure the bounded wait condition. The structure below has a global Boolean array waiting[i] and a global Boolean variable lock where both are initialized to false. Also, a local variable key associated with each process that is interested to execute their critical section.
{
do
waiting[i] = TRUE;
key = TRUE;
while (waiting[i] && 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;
// remainder section
}
while (TRUE);
Now first we will check how the structure above satisfies mutual exclusion condition. Any process Pi is allowed to get into its critical section only if the first while loop turns to be false i.e. either waiting[i] ==false or key==false.
The very first process executing this code will get the chance to set the key==false and will enter the critical section and refrains other processes from entering into their critical section. This satisfies mutual exclusion.
Now about bounded wait and progress, the process executing the critical section will either set lock==false or it will set waiting[j]==false. Here, both the settings will let processes waiting to enter their critical section to proceed.
The process exiting its critical section scans the waiting[j] array, where j = (i+ 1, i + 2, …, n-1, 0, …, i-1). Thus letting the processes waiting to enter its critical section in n-1 turns.
Swap Hardware Instruction
Like TestAndSet() instruction the swap() hardware instruction is also an atomic instruction. With a difference that it operates on two variables provided in its parameter. The structure of swap() instruction is:
do {
key = TRUE;
while (key == TRUE)
Swap(&lock, &key);
// critical section
lock = FALSE;
// remainder section
} while (TRUE);
To achieve mutual exclusion using swap() instruction, the structure we use is a follow:
do {
key = TRUE;
while (key == TRUE)
Swap(&lock, &key);
// critical section
lock = FALSE;
// remainder section
} while (TRUE);
The structure above operates on one global shared Boolean variable lock and another local Boolean variable key. Both of which are initially set to false. The process P0 interested in executing its critical section execute code above and set lock as true and enter its critical section. Thus refrain other processes from executing their critical section satisfying mutual exclusion.
Advantages and Disadvantages of Synchronization Hardware
Advantages of Hardware Instruction
- Hardware instructions are easy to implement and improves the efficiency of the system.
- Supports any number of processes may it be on the single or multiple processor system.
- With hardware instructions, you can implement multiple critical sections each defined with a unique variable.
Disadvantages of Hardware Instruction
- Processes waiting for entering their critical section consumes a lot of processors time which increases busy waiting.
- As the selection of processes to enter their critical section is arbitrary. It may happen that some processes are waiting for the indefinite time which leads to process starvation.
- Deadlock is also possible.
This is how we can use a hardware solution to overcome the critical section problem. But overviewing the drawback of hardware solution there we have to opt for some other mechanism i.e. semaphore.
Ataklti says
So great ful lecture