Test and Set | Process Synchronization

Process Synchronization-

 

Before you go through this article, make sure that you have gone through the previous article on Process Synchronization.

 

We have discussed-

• Process Synchronization provides a synchronization among the processes.
• Synchronization mechanisms allow the processes to access critical section in a synchronized manner.
• This avoids the inconsistent results.

 

Test and Set Lock –

 

• Test and Set Lock (TSL) is a synchronization mechanism.
• It uses a test and set instruction to provide the synchronization among the processes executing concurrently.

 

Test-and-Set Instruction   It is an instruction that returns the old value of a memory location and sets the memory location value to 1 as a single atomic operation. If one process is currently executing a test-and-set, no other process is allowed to begin another test-and-set until the first process test-and-set is finished.

 

It is implemented as-

 

 

Initially, lock value is set to 0.

• Lock value = 0 means the critical section is currently vacant and no process is present inside it.
• Lock value = 1 means the critical section is currently occupied and a process is present inside it.

 

Working-

 

This synchronization mechanism works as explained in the following scenes-

 

Scene-01:

 

• Process P₀ arrives.
• It executes the test-and-set(Lock) instruction.
• Since lock value is set to 0, so it returns value 0 to the while loop and sets the lock value to 1.
• The returned value 0 breaks the while loop condition.
• Process P₀ enters the critical section and executes.
• Now, even if process P₀ gets preempted in the middle, no other process can enter the critical section.
• Any other process can enter only after process P₀ completes and sets the lock value to 0.

 

Scene-02:

 

• Another process P₁ arrives.
• It executes the test-and-set(Lock) instruction.
• Since lock value is now 1, so it returns value 1 to the while loop and sets the lock value to 1.
• The returned value 1 does not break the while loop condition.
• The process P₁ is trapped inside an infinite while loop.
• The while loop keeps the process P₁ busy until the lock value becomes 0 and its condition breaks.

 

Scene-03:

 

• Process P₀ comes out of the critical section and sets the lock value to 0.
• The while loop condition breaks.
• Now, process P₁ waiting for the critical section enters the critical section.
• Now, even if process P₁ gets preempted in the middle, no other process can enter the critical section.
• Any other process can enter only after process P₁ completes and sets the lock value to 0.

 

Characteristics-

 

The characteristics of this synchronization mechanism are-

• It ensures mutual exclusion.
• It is deadlock free.
• It does not guarantee bounded waiting and may cause starvation.
• It suffers from spin lock.
• It is not architectural neutral since it requires the operating system to support test-and-set instruction.
• It is a busy waiting solution which keeps the CPU busy when the process is actually waiting.

 

Also Read- Criteria For Synchronization Mechanisms

 

Explanations-

 

Point-01:

 

This synchronization mechanism guarantees mutual exclusion.

 

Explanation-

 

• The success of the mechanism in providing mutual exclusion lies in the test-and-set instruction.
• Test-and-set instruction returns the old value of memory location (lock) and updates its value to 1 simultaneously.
• The fact that these two operations are performed as a single atomic operation ensures mutual exclusion.
• Preemption after reading the lock value was a major cause of failure of lock variable synchronization mechanism.
• Now, no preemption can occur immediately after reading the lock value.

 

Also read- Lock Variable Synchronization Mechanism

 

Point-02:

 

This synchronization mechanism guarantees freedom from deadlock.

 

Explanation-

 

• After arriving, process executes the test-and-set instruction which returns the value 0 to while loop and sets the lock value to 1.
• Now, no other process can enter the critical section until the process that has begin the test-and-set finishes executing the critical section.
• Other processes can enter only after the process that has begin the test-and-test finishes and set the lock value to 0.
• This prevents the occurrence of deadlock.

 

Also read- Deadlock in Operating System

 

Point-03:

 

This synchronization mechanism does not guarantee bounded waiting.

 

Explanation-

 

• This synchronization mechanism may cause a process to starve for the CPU.
• There might exist an unlucky process which when arrives to execute the critical section finds it busy.
• So, it keeps waiting in the while loop and eventually gets preempted.
• When it gets rescheduled and comes to execute the critical section, it finds another process executing the critical section.
• So, again, it keeps waiting in the while loop and eventually gets preempted.
• This may happen several times which causes that unlucky process to starve for the CPU.

 

Point-04:

 

This synchronization mechanism suffers from spin lock where the execution of processes is blocked.

 

Explanation-

 

Consider a scenario where-

• Priority scheduling algorithm is used for scheduling the processes.
• On arrival of a higher priority process, a lower priority process is preempted  from the critical section.

Now,

• Higher priority process comes to execute the critical section.
• But synchronization mechanism does not allow it to enter the critical section before lower priority process completes.
• But lower priority process can not be executed before the higher priority process completes execution.
• Thus, the execution of both the processes is blocked.

 

To gain better understanding about Test and Set Lock,

Watch this Video Lecture

 

Next Article- Turn Variable | Synchronization Mechanism

 

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.