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 P0 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 P0 enters the critical section and executes.
  • Now, even if process P0 gets preempted in the middle, no other process can enter the critical section.
  • Any other process can enter only after process P0 completes and sets the lock value to 0.

 

Scene-02:

 

  • Another process P1 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 P1 is trapped inside an infinite while loop.
  • The while loop keeps the process P1 busy until the lock value becomes 0 and its condition breaks.

 

Scene-03:

 

  • Process P0 comes out of the critical section and sets the lock value to 0.
  • The while loop condition breaks.
  • Now, process P1 waiting for the critical section enters the critical section.
  • Now, even if process P1 gets preempted in the middle, no other process can enter the critical section.
  • Any other process can enter only after process P1 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.

Summary
Test and Set | Process Synchronization
Article Name
Test and Set | Process Synchronization
Description
In Process Synchronization, Test and Set Lock (TSL) is a synchronization mechanism that uses a test-and-set instruction to provide the synchronization among the processes. It ensures mutual exclusion and freedom from deadlock.
Author
Publisher Name
Gate Vidyalay
Publisher Logo