Synchronization Hardware in OS

Hardware Synchronization Algorithms

Process Syncronization problem can be solved by software as well as a hardware solution. Peterson solution is one of the software solutions to the process synchronization problem. Peterson algorithm allows two or more processes to share a single-use resource without any conflict. In this article, we will discuss the Hardware solution to the problem. The hardware solution is as follows:

1. Test and Set
2. Swap
3. Unlock and Lock

Test and Set

Test and set algorithm uses a boolean variable 'lock' which is initially initialized to false. This lock variable determines the entry of the process inside the critical section of the code. Let's first see the algorithm and then try to understand what the algorithm is doing.

In the above algorithm the TestAndSet() function takes a boolean value and returns the same value. TestAndSet() function sets the lock variable to true.

When lock varibale is initially false the TestAndSet(lock) condition checks for TestAndSet(false). As TestAndSet function returns the same value as its argument, TestAndSet(false) returns false. Now, while loop while(TestAndSet(lock)) breaks and the process enters the critical section.

As one process is inside the critical section and lock value is now 'true', if any other process tries to enter the critical section then the new process checks for while(TestAndSet(true)) which will return true inside while loop and as a result the other process keeps executing the while loop.

As no queue is maintained for the processes stuck in the while loop, bounded waiting is not ensured. If a process waits for a set amount of time before entering the critical section, it is said to be a bounded waiting condition.

In test and set algorithm the incoming process trying to enter the critical section does not wait in a queue so any process may get the chance to enter the critical section as soon as the process finds the lock variable to be false. It may be possible that a particular process never gets the chance to enter the critical section and that process waits indefinitely.

Swap

Swap function uses two boolean variables lock and key. Both lock and key variables are initially initialized to false. Swap algorithm is the same as lock and set algorithm. The Swap algorithm uses a temporary variable to set the lock to true when a process enters the critical section of the program.

Let's see the swap algorithm pseudo-code:

In the code above when a process P1 enters the critical section of the program it first executes the while loop

As key value is set to true just before the for loop so swap(lock, key) swaps the value of lock and key. Lock becomes true and the key becomes false. In the next iteration of the while loop breaks and the process, P1 enters the critical section.

The value of lock and key when P1 enters the critical section is lock = true and key = false.

Let's say another process, P2, tries to enter the critical section while P1 is in the critical section. Let's take a look at what happens if P2 tries to enter the critical section.

key is set to true again after the first while loop is executed i.e while(1). Now, the second while loop in the program i.e while(key) is checked. As key is true the process enters the second while loop. swap(lock, key) is executed again. as both key and lock are true so after swapping also both will be true. So, the while keeps executing and the process P2 keeps running the while loop until Process P1 comes out of the critical section and makes lock false.

When Process P1 comes out of the critical section the value of lock is again set to false so that other processes can now enter the critical section.

When a process is inside the critical section than all other incoming process trying to enter the critical section is not maintained in any order or queue. So any process out of all the waiting process can get the chance to enter the critical section as the lock becomes false. So, there may be a process that may wait indefinitely. So, bounded waiting is not ensured in Swap algorithm also.

Unlock and lock

Unlock and lock algorithm uses the TestAndSet method to control the value of lock. Unlock and lock algorithm uses a variable waiting[i] for each process i. Here i is a positive integer i.e 1,2,3,... which corresponds to processes P1, P2, P3... and so on. waiting[i] checks if the process i is waiting or not to enter into the critical section.

All the processes are maintained in a ready queue before entering into the critical section. The processes are added to the queue with respect to their process number. The queue is the circular queue.

Let's see the Unlock and lock algorithm pseudo-code first:

In Unlock and lock algorithm the lock is not set to false as one process comes out of the critical section. In other algorithms like swap and Test and set the lock was being set to false as the process comes out of the critical section so that any other process can enter the critical section.

But in Unlock and lock, once the ith process comes out of the critical section the algorithm checks the waiting queue for the next process waiting to enter the critical section i.e jth process. If there is a jth process waiting in the ready queue to enter the critical section, the waiting[j] of the jth process is set to false so that the while loop while(waiting[i] && key) becomes false and the jth process enters the critical section.

If no process is waiting in the ready queue to enter the critical section the algorithm then sets the lock to false so that any other process comes and enters the critical section easily.

Since a ready queue is always maintained for the waiting processes, the Unlock and lock algorithm ensures bounded waiting.