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
Liked this article? Share it with your friends and classmates now-