L-3.6: Test and Set Instruction in OS | Process Synchronization

Summary

In this educational video, the concept of the 'Test and Set' instruction for process synchronization is explored. The video addresses the limitations of the lock variable method, where preemption between two instructions can lead to multiple processes entering the critical section simultaneously, violating mutual exclusion. The 'Test and Set' instruction overcomes this by making the test and set operations atomic, preventing preemption and ensuring that only one process accesses the critical section at a time. The video simplifies the understanding of this synchronization technique, making it accessible for students preparing for exams or university coursework.

Takeaways

• 🔐 The 'Test and Set' instruction is used for process synchronization to resolve issues in critical sections.
• 🔄 The problem with the lock variable arises when preemption occurs between checking the lock value and setting it, allowing multiple processes to enter the critical section simultaneously.
• 🛠️ The 'Test and Set' instruction combines the check and set operations into one atomic action to prevent preemption between these steps.
• 💡 The 'Test and Set' function is defined to handle the atomic operation, ensuring that only one process can enter the critical section at a time.
• 📚 The script references Galvin's code, suggesting its relevance for competitive exams and academic settings.
• 🔑 The use of pointers ('call by reference') in the 'Test and Set' function allows for direct manipulation of the lock variable's memory address.
• 🔄 The function returns the previous value of the lock, which is used in a while loop to determine if a process should enter the critical section.
• 🚫 If the returned value is 'true', the process is trapped in an infinite loop, preventing it from entering the critical section when it's already occupied.
• 🔄 The 'Test and Set' mechanism ensures mutual exclusion and progress, allowing processes to enter the critical section only when it's empty and no other process is inside.
• 📖 The video script serves as a supplementary resource to help understand the concept of 'Test and Set' more easily, especially for those studying from books.

Q & A

What is the main issue with the lock variable method in process synchronization?

The main issue with the lock variable method is that preemption can occur between the check (line 1) and the setting (line 2) of the lock variable, allowing multiple processes to enter the critical section simultaneously, thus violating mutual exclusion.

What is the purpose of the Test and Set instruction in process synchronization?

The Test and Set instruction is used to ensure mutual exclusion by making the check and set operations atomic, preventing preemption between these operations and allowing only one process to enter the critical section at a time.

How does the Test and Set instruction prevent multiple processes from entering the critical section simultaneously?

The Test and Set instruction prevents simultaneous entry by combining the test and set operations into a single atomic operation, which means that once a process sets the lock, no other process can test and set the lock until the first process releases it.

What is the significance of the boolean value in the Test and Set function?

The boolean value in the Test and Set function indicates the status of the lock. A false value means the critical section is empty and available, while a true value indicates that the critical section is occupied.

Why is the address of the lock variable passed to the Test and Set function?

The address of the lock variable is passed to the Test and Set function to allow the function to directly modify the value of the lock variable, ensuring that the test and set operations are performed atomically.

What is the role of the 'target' pointer in the Test and Set function?

The 'target' pointer is used to reference the lock variable within the Test and Set function. It allows the function to both read the current value of the lock and set a new value, achieving atomicity.

How does the Test and Set instruction ensure progress in process synchronization?

The Test and Set instruction ensures progress by allowing a process to enter the critical section if it is empty, and by making the test and set operations atomic, it prevents processes from being indefinitely trapped in a loop when the critical section is available.

What is the expected behavior of a process when it encounters a true value in the Test and Set loop?

When a process encounters a true value in the Test and Set loop, it should enter an infinite loop, waiting for the lock to be released, thus not entering the critical section until it is available.

Why is it important for the Test and Set instruction to be atomic?

It is important for the Test and Set instruction to be atomic to prevent race conditions and ensure that only one process can enter the critical section at a time, maintaining the integrity and consistency of shared resources.

How does the Test and Set instruction relate to the concept of mutual exclusion in process synchronization?

The Test and Set instruction is a mechanism for achieving mutual exclusion by ensuring that only one process can acquire the lock and enter the critical section, while others are excluded until the lock is released.

Outlines

00:00

🔒 Introduction to Test and Set Instruction

The paragraph introduces the concept of the Test and Set instruction in process synchronization, specifically to resolve issues in critical sections. It discusses the limitations of a lock variable, which can lead to problems when processes preempt each other between checking the lock value and entering the critical section. The paragraph explains how the Test and Set instruction combines the check and set operations into a single atomic operation, preventing preemption and ensuring mutual exclusion. It also introduces the idea of using a hardware-level instruction to achieve this, ensuring that once a process enters the critical section, no other process can do so until it exits.

05:02

🛠 Deep Dive into Test and Set Functionality

This paragraph delves deeper into the functionality of the Test and Set instruction. It uses a hypothetical scenario with two processes, P1 and P2, to illustrate how the Test and Set instruction works. The paragraph explains the use of a pointer variable 'target' to reference the lock variable, which is passed by address to ensure call by reference. It details the steps within the Test and Set function, including how the lock value is checked and set to true, and how the function returns a boolean value based on the initial state of the lock. The paragraph concludes by emphasizing the mutual exclusion achieved by the Test and Set instruction and the concept of progress, which ensures that if the critical section is empty, a waiting process can enter without hindrance.

Keywords

💡Test and Set instruction

The 'Test and Set' instruction is a fundamental concept in process synchronization used to ensure mutual exclusion in a multi-process environment. It is a hardware-level atomic operation that checks and sets a variable in a single step, preventing race conditions. In the video, this instruction is used to solve the problem of concurrent access to a critical section by multiple processes, ensuring that only one process can enter the critical section at a time. The script explains how the Test and Set instruction combines two operations into one atomic action, preventing preemption between them and thus achieving mutual exclusion.

💡Process synchronization

Process synchronization is a mechanism in operating systems that coordinates the execution of multiple processes to manage concurrent access to shared resources. It is crucial for maintaining data integrity and system stability. In the context of the video, process synchronization is used to resolve problems that arise when multiple processes try to access a critical section simultaneously. The script discusses how the Test and Set instruction plays a role in achieving synchronization by preventing race conditions.

💡Critical section

A critical section is a portion of the code in a program where multiple processes need exclusive access to shared resources. It is a critical part of concurrency control where proper synchronization is necessary to avoid conflicts. The video script uses the critical section to illustrate the problem of mutual exclusion, where the Test and Set instruction is introduced to ensure that only one process can execute the critical section at a time, preventing data corruption and ensuring system consistency.

💡Lock variable

A lock variable is a simple synchronization mechanism used to control access to a critical section. It is typically a boolean variable that indicates whether a critical section is currently being accessed by a process. In the script, the lock variable is initially introduced as a solution to mutual exclusion but is later shown to have issues with preemption. The Test and Set instruction is then presented as an improvement over the lock variable, providing an atomic operation to set and test the lock state.

💡Preemption

Preemption in the context of operating systems refers to the action of temporarily suspending a process's execution, allowing the system to allocate resources to other processes. The video script highlights the issue of preemption occurring between the check and set operations on a lock variable, which can lead to multiple processes entering the critical section simultaneously, violating mutual exclusion. The Test and Set instruction is presented as a solution to this problem by making the check and set operations atomic, thus preventing preemption from occurring between them.

💡Atomic operation

An atomic operation is a single, indivisible step in a program's execution that completes without interruption. It is crucial in multi-threaded or multi-process environments to ensure data consistency and prevent race conditions. The video script discusses how the Test and Set instruction is an atomic operation that combines the testing and setting of a lock variable into one step, preventing preemption and ensuring that only one process can enter the critical section at a time.

💡Mutual exclusion

Mutual exclusion is a principle in concurrent programming that ensures that when a process is using a shared resource, no other process can access it simultaneously. This is essential for maintaining the integrity of shared data. The video script explains how the Test and Set instruction helps achieve mutual exclusion by ensuring that only one process can enter the critical section at a time, thus preventing conflicts and ensuring correct program execution.

💡Call by reference

Call by reference is a parameter passing mechanism in programming where the memory address of the actual variable is passed to the function instead of its value. This allows the function to modify the original variable. In the script, the Test and Set function uses call by reference to modify the lock variable directly, ensuring that the change is reflected in the original variable, which is crucial for the proper functioning of the synchronization mechanism.

💡Pointer variable

A pointer variable is a variable that stores the memory address of another variable. It is used in programming to access and manipulate the value of the variable indirectly. In the video script, pointer variables are used to implement the Test and Set function, where the address of the lock variable is passed to the function, allowing it to both test and set the value of the lock variable in an atomic operation.

💡Infinite loop

An infinite loop is a loop in a program that continues to execute indefinitely because its terminating condition is never met. In the context of the video, an infinite loop is used as a mechanism to keep a process waiting outside the critical section until it is safe to enter. When the Test and Set function returns true, indicating that the critical section is occupied, the process enters an infinite loop, waiting for the lock to be released before it can proceed.

Highlights

Introduction to Test and Set instruction for process synchronization.

Explanation of the problem with lock variables in critical section management.

Demonstration of how preemption can lead to multiple processes entering the critical section simultaneously.

The concept of atomicity in instructions to prevent preemption between critical operations.

Introduction of the Test and Set instruction as a hardware-based solution for mutual exclusion.

Description of how Test and Set makes the test and set operations atomic.

Explanation of the Test and Set function and its role in mutual exclusion.

The use of pointers in the Test and Set function to achieve call by reference.

Detailed walkthrough of the Test and Set function's execution flow.

How the Test and Set function prevents multiple processes from entering the critical section simultaneously.

Ensuring mutual exclusion and progress in process synchronization using Test and Set.

The importance of mutual exclusion in maintaining the integrity of shared resources.

The role of progress in allowing processes to enter the critical section when it's empty.

The simplicity of the Test and Set concept and its practical applications.

Advice on how to understand the Test and Set concept through the video and supplemental reading.

Transcripts

Dear students, welcome to Gate Smashers. In today's video I'm going to explain

Test and Set instruction. So look, in process synchronization to resolve problem

in critical section next method we use Test and Set instruction. So in the last video I told you

about lock variable. So lock variable works fine, but what is the problem here?

The problem I have told in the last video, once again I'll quickly tell that

let's say there is a process P1 and process P2, 2 processes are there, P1 comes first,

it runs line number 1. At the start value of lock is what? 0. Means critical section is empty.

P1 comes it sees While lock 0==1, becomes false, it will come out from here after becoming false.

Means P1 executed line number 1 after executing it will execute line number 2

then it will come to critical section. But the problem that occurred was that

as soon as it executed line number 1 it checked value of lock 0==1, false.

On coming out from here what did it become? Pre-empt. Let's say we made it pre-empt.

This case is made intentionally so that you come to know what was the problem in lock variable.

So look P1 executes first line and becomes preempt. P2 comes. P2 also executes line number 1,

What is the value of lock? still 0. Still there is no change in lock value

because line number 2 was not executed so P2 executes line number 1, 0==1, becomes false, came out

as soon as it comes out lock=1 was done. When lock was made 1, from 0 to 1,

who entered critical section? P2 entered critical section means where did P2 enter? P2 enters.

Now look P2 is now already in critical section now P1 again woke up, means let's say

it went to the washroom after executing line number 1 now it came back,

when it comes back it will not restart again it has already executed line number 1

and it has to directly execute line number 2. As soon as it executes line number 2,

what does line number 2 say? Lock=1. Lock is already 1 it was overwritten again by 1.

No problem, value of lock is to be made 1 then value of lock whatever it is we made it 1 again.

Whether it was 0 or 1, again cut and made it 1 and who entered critical section? P1 also entered.

Getting the point? Now this way you can enter P2, P3, P4, P5 as many as you want in critical section.

Meaning mutual exclusion is not there in it. Getting the point?

So what actually is the problem here? You just have to reach the root of the problem.

What is the problem? The problem is that between instruction number 1 and number 2 pre-emption occurs.

Pre-emption is occurring between number 1 and 2. So the next upcoming Test and Set instruction

what did it do? It combined these two, meaning made these two instructions atomic, combined

and made it this. While test and set M present lock. Means now look critical section was this

line number 3, the lines before it were combined and it made one instruction here

that is test and set. Means here we used hardware and we made special instruction which tests also

means it is being tested here whether value of lock is 1 or 0, and also sets it

means value of lock to be set as 1. These 2 tasks are done by one instruction so that

pre-emption does not happen in between and we achieve mutual exclusion here.

This is the root of the story. Now look, now we come to test and set. So look

While test and set and here we have set M percent lock, critical section, lock=false.

The same true or false means value of true is 1 and value of false we take 0.

It is the same story, simple. Now look, what is this? It is a function, test and set function.

Who is doing this function? Because while works on true or false, if there is true in while

it will perform according to that, if there is false in while it will perform according to that.

But what did we give in while? Calling of function. Now where is the definition of this function?

Here is the definition of function. So now we will discuss a little bit about this.

It is very simple. First of all let's say again the same, there is P1 and P2, first came P1

who came first? P1. And initially like we made the value of lock 0,

what do we make value of lock initially? 0 so that we can tell that critical section is empty.

Now here we made the value of lock initially as false, 0 means false. Now look,

while(test and set(& lock)) let's say P1 came first and when P1 comes, test and set

means this function will be called, after this function is called means

here our control will be lost. So Boolean because we take true or false, so Boolean test and set,

Boolean this star is target, what is this here? What we did actually here? What is star target?

It is pointer variable with the name of target. I have written Galvin's code so that

in your competitive exams, college/university wherever it is asked you can answer this easily.

So look we too lock as M percent we are using call by reference not call by value,

so in call by reference what do we give? We pass the address. So look

what was initial taken value of lock? False. Its address, for example I took 1000 means

now we will pass 1000. So look Boolean star target. In this target what will be the value? 1000.

Means target is pointing at this false value, meaning target is pointing at value of lock.

Getting the point? Now look, the same simple code of C, working on call by reference.

We put value of target in r. Now look target is 1000 address, we put star ahead means

the value in target is pointing at what? 1000 is pointing at what? False. So we put false,

we take r variable, so initially what we put in r? False. Okay? What was it at start?

Initial value of lock was false, so what comes in r? False. Because we have to return the value.

We have to return in while. And what we did to target? We made it true means what is target? 1000.

Before that is star, star means what is the target pointing to? Lock.

So in that we made true in place of false. Same, we did test also and set also.

To set means to make true. So we made true also and checked it also and finally what did we do?

Return r. Look what was the value of r? False. So what will be returned here? False will be returned.

Same as we do here, what was the value of lock at start? 0. 0==1, false

means coming out in critical section the same task is done here, became false coming out

who entered critical section? P1 entered critical section. Its very easy, okay.

Now what we do? Let's say P2 comes, P2 says I also want to go,

so as soon as P2 goes it will again run this. As soon as P2 came P2 again ran test and set.

Now look, lock comes in here, we come to this code we came on function calling

so from function calling we reached definition. Now look, here what is value of lock?

It has become true because P1 is already in. Now look, what we have to do star target,

target is pointing at what? True. So we put value of true in r. What comes in r? True. Okay.

And what we did? *target= True means what is target pointing at? Lock. We made it true.

This was already true, so no problem. We again overwrote true and let it be true. So this is true

and returned r means the true, value of r was what? True. We returned it so look, now here

what will be return? True. So while true means that this will be trapped in this itself.

Because there is a semicolon, so this will be trapped here in an infinite loop.

So P2 will not be able to enter so you have achieved mutual exclusive. Getting the point or not?

Now it comes to your mind that sir now we cannot do any pre-emption because both these tasks,

the pre-emption occurring here in between before, now we combined both these and

converted into one instruction and through this we achieved mutual exclusion also

and progress is also achieved. What progress means is that if critical section is empty

and whoever wants to come can easily come, nobody will stop it if critical section is empty.

So here mutual exclusion is there and progress too is achieved here by default.

So this is a basic funda of test and set. Generally what happens when we often read from books

then we don't understand in one or two tries, so when you check this video and then

after that read from book you will feel very easy that this is a very simple concept. Thank you.