L-3.6: Test and Set Instruction in OS | Process Synchronization
Summary
TLDRIn 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
🔒 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.
🛠 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.
Mindmap
Keywords
💡Test and Set instruction
💡Process synchronization
💡Critical section
💡Lock variable
💡Preemption
💡Atomic operation
💡Mutual exclusion
💡Call by reference
💡Pointer variable
💡Infinite loop
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.
関連動画をさらに表示
L-3.5: LOCK Variable in OS | Process Synchronization
L-3.7: Turn Variable | Strict Alteration Method | Process Synchronization
Lamport's Mutual Exclusion Distributed Systems Synchronization
Peterson’s Solution
Rational Inequalities
RISC vs CISC | RISC | Reduced Instruction Set Computer | CISC | Complex Instruction Set Computer
5.0 / 5 (0 votes)