Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
 
3.
Modification in the assembly code
4.
TSL Instruction
4.1.
Mutual Exclusion
4.2.
Progress
4.3.
Bounded Waiting 
4.4.
Neutrality in Architecture
5.
Execution Step
6.
Frequently Asked Questions
6.1.
How does set and test work?
6.2.
TSL is a type of operating system.
6.3.
What Is Busy Waiting?
6.4.
In OS, what is a mutex?
6.5.
What is the definition of a long-term scheduler?
7.
Conclusion
Last Updated: Mar 27, 2024

Test Set Lock Mechanism

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @
Operating Systems

Introduction

This article will explain Test Set Lock Mechanism. The hardware solution to the synchronization problem is TestAndSet. We have a shared lock variable in Test and Set that may take one of two values: 0 or 1.

A procedure checks the lock before proceeding to the critical part. If it's locked, it'll keep waiting until it's unlocked; if it's not, it'll take the lock and run the essential portion.

The Lock Variable Mechanism Process will occasionally read the old value of the lock variable and proceed to the crucial portion. As a result, more than one process may enter the essential area. The code displayed in part one of the next section, on the other hand, can be substituted with the code shown in part two. This does not affect the algorithm, but it does allow us to give mutual exclusion to a degree, although not totally.

Also Read About, FCFS Scheduling Algorithm, Multiprogramming vs Multitasking

 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Modification in the assembly code

The value of Lock is loaded into the local register R0 in the revised version of the code, and then the value of Lock is set to 1.

In step 3, however, the initial lock value (stored in R0) is compared to 0. If this is 0, the process will immediately enter the critical part; otherwise, it will wait by executing the loop constantly.

The advantage of setting the lock to 1 by the process is that the process now enters the crucial section with the updated value of the lock variable, which is 1.

It will not enter the crucial area if it is preempted and scheduled again, regardless of the current value of the lock variable, because it already knows what the new value of the lock variable is.

Modification in Assmebly Code

TSL Instruction

Although the solution in the preceding segment enables mutual exclusion to some extent, it does not guarantee that mutual exclusion will always be present. There is a chance that the critical portion will contain many processes.

What if the process is preempted right after the first instruction of the section 2 assembly code is executed? In that instance, it will reach the critical area with the old value of the lock variable, regardless of knowing the current value of the lock variable. This could cause the two processes to coexist in the critical section.

To solve this issue, we must ensure that preemption does not occur immediately after loading the previous value of the lock variable and before setting it to 1. If we can combine the first two commands, we can solve the problem.

The operating system includes a special instruction called Test Set Lock (TSL) to handle the problem, which simply loads the value of the lock variable into the local register R0 and sets it to 1 at the same time.

The first process to execute the TSL will enter the critical area, and no other methods will be allowed to enter until the first process exits. Even if the first process is preempted, no process can execute the essential part.

Assembly Code of the Solution

Let's look at TSL in terms of the four criteria

Mutual Exclusion

Because a process can never be preempted right before setting the lock variable, mutual exclusion is enforced in the TSL mechanism. Because only one method can perceive the lock variable as 0 at any given time, mutual exclusion is guaranteed.

Progress

According to the progress definition, a process that does not want to access the crucial section should not prevent other functions from doing so. A process will only execute the TSL instruction if it intends to enter the critical region using the TSL mechanism. If no process wants to join the required area, the lock value will always be 0, ensuring progress is always assured in TSL.

Bounded Waiting 

TSL does not guarantee bounded waiting. Some processes may not be given a chance for a long time. We can't ensure that a process will get an opportunity to access the critical part after a specific period.

Neutrality in Architecture

TSL does not provide architectural Neutrality. The hardware platform determines this. The operating system offers the TSL instruction. This may not be available on all platforms. As a result, it isn't architecturally natural.

Execution Step

Step 1: If you hit P0 here, the process P0 will be moved from the queue to the entry area. When it first reaches the entry area, the lock's value will be 0. A register will enter the image once it gets the vital part. The register's value will be 1.

The exchange of values between the register and the lock takes place in the entry section itself.

As a result, the lock value will be 1,, and the register value will be 0.
 

Step 2: If you hit P0 again, the process P0 will go from the entrance to the crucial portion. Only one process may happen at a time in the crucial area.

Step 3: P1 will now go from the queue to the admission section if you hit P1. If you press P1 again, there will be an issue because only one process can enter the vital part.

P0 has already entered the critical part, so P1 must wait for P0 to complete the process.

The register value will become 1 because process P0 is already in the critical region, and process P1 will enter the while loop and never enter the required area.

The website will display a warning message stating that process P1 must wait for process P0 to exit the critical portion before proceeding.
 

Step 4: When you press P0 again, the process P0 will switch from the crucial to the exit sections.

The value of the lock and the value of the register will be set to 0 in the exit section. If you press P1 again at the exact moment, the lock value will be reset to 1.
 

Step 5: Similarly, if process P1 is in the critical section and process P0 is in the entrance section, pressing P0 will prevent P0 from entering the required region.

The register's value will increase from zero to one, and process P0 will enter an infinite while loop, preventing it from approaching the crucial area.

Process P0 will receive an alert message stating that it must wait for process P1 to exit the critical area.
 

Step 6: Consider the situation when processes P0 and P1 are in the queue at the start. Process P0 will now proceed to the entrance section. As a result, the lock value will be 1,, and the register value will be 0.

Process P1 will now arrive simultaneously and enter the entry section.

Because the value of the register has changed to 1, neither process P0 nor process P1 may enter the critical region, resulting in a Deadlock.

Step 7: Now, if any process moves from the critical section to the exit section, the lock and register values will reset to 0, allowing any other method to execute and use the crucial area.

FCFS Scheduling

Frequently Asked Questions

How does set and test work?

The test-and-set instruction is a single atomic (i.e., non-interruptible) operation that writes 1 to a memory address and returns its old value. The caller can then "test" the result to determine if it altered the state. 

TSL is a type of operating system.

The operating system includes a special instruction called Test Set Lock (TSL) to handle the problem, which simply loads the value of the lock variable into the local register R0 and sets it to 1 at the same time. 

What Is Busy Waiting?

Busy waiting, also known as spinning or busy looping, is a synchronization strategy in which a process/task waits for a condition to be satisfied before continuing with its execution.

In OS, what is a mutex?

Terms. Only one job (depending on OS abstraction, a thread, or process) can acquire the mutex. It denotes that a mutex has an owner and that only the owner can unlock the lock (mutex). 

What is the definition of a long-term scheduler?

Job Scheduler is another name for Long-Term Scheduler. The long-term scheduler controls the programs chosen for processing by the system. The programs are placed in a queue, the best task is determined based on the requirements, and the processes are taken from the job pool.

Conclusion

This article has gone through Test Set Lock Mechanism. The hardware solution to the synchronization problem is TestAndSet. We have a shared lock variable in TestAndSet that may take one of two values: 0 or 1. Want to learn more about the Functions Of An Operating System? Click here.

Recommended Readings: 


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Ninja, have a great time learning.

Previous article
Mutex Lock
Next article
Priority Inversion
Live masterclass