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.
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.
This synchronization mechanism works as explained in the following scenes-
- 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.
- 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.
- 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.
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
|This synchronization mechanism guarantees mutual exclusion.|
- 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
|This synchronization mechanism guarantees freedom from deadlock.|
- 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
|This synchronization mechanism does not guarantee bounded waiting.|
- 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.
|This synchronization mechanism suffers from spin lock where the execution of processes is blocked.|
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.
- 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,
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.