Hardware Based Solution to Synchronization

There is no guarantee that the Software-based solution like Peterson’s will work on modern architecture. Hence, certain hardware-based solution to synchronization are proposed. Two such solutions are:
1. TestAndSet() instruction
2. Swap() instruction

Both these instructions are atomic instructions which means that when a process is executing any of these instructions it can not be preempted until the instruction is complete.

1. TestAndSet() Instructions

TestAndSet() instruction uses a boolean variable lock. The initial value of the lock is false. The variable lock ensures mutual exclusion. If the value of lock is false, this means that no process is in its critical section. Hence, the value true means that some process is running in its critical section.

boolean TestAndSet(boolean *lock) {
boolean initial = *lock;
*lock = TRUE;
return initial ;
}

do {
  while (TestAndSet(&lock));
  critical section
lock = FALSE;
  remainder section
} while(TRUE);

Working of TestAndSet()

Consider that process P1 wants to enter critical section, so it calls
while(TestAndSet(&lock));
Now, what is the initial value of lock?
Ans: false

Now, when TestAndSet() function executes the value of lock is false. The address is passed so that when the value of lock is changed it is reflected globally (recall the difference between Call by Value and Call by Reference). Next, inside TestAndSet(), the variable initial is assigned the value of lock (which is false), so the value of initial becomes false. Finally, the value of lock is changed to true and the value of initial is returned i.e., TestAndSet() returns false.
So, What does while(TestAndSet(&lock)) get?
Ans: false
So, while(false);, the control comes out of the loop and P1 enters the critical section.

Next, if any other process, let’s suppose P2 tries to enter critical section, it calls

 while(TestAndSet(&lock));

Now, what is the value of the variable lock?
Ans: true, because it was changed by P1..read above

Now, when TestAndSet() function executes the value of lock is true. Next, inside TestAndSet(), the variable initial is assigned the value of lock (which is true), so the value of initial becomes true. Finally, the value of lock is changed to true(which it already is) and the value of initial is returned i.e., TestAndSet() returns true.
So, what is the value inside while in the below statement?

while(TestAndSet(&lock))

Ans: true
So,

while(true);

the process keeps executing the while loop and P2 is not able to enter the critical section.

Similarly, no other process will be able to enter the critical section until P1 comes out of the critical section and change the value of lock back to false by executing the statement
lock = FALSE;

2. Swap() Instruction

The swap() instruction uses two boolean variables lock and key.

void Swap(boolean *a, boolean *b)
{
Boolean t = *a;
*a = *b;
*b = t;
}

do {
key = TRUE;
while (key == TRUE)
     Swap(&lock, &key);
//critical section

lock = FALSE;

//remainder section
} while (TRUE);

To understand the working of Swap() consider two processes just as we did above for TestAndSet(). Thereafter, execute the statements of each process one at a time. The Swap() instruction uses two boolean variable, namely, lock and key.

PPT on Hardware-Based Solution to Synchronization

Note: Click within the slide area for animations. Clicking on the “next” slide button will not display any animation

Previous                                       Next
Semaphores                    Deadlock