L-3.5: LOCK Variable in OS | Process Synchronization

Summary

In this educational video, the concept of the Lock Variable is explored as a method to address the critical section problem in operating systems. The Lock Variable is a fundamental approach where a process must acquire a lock before entering the critical section and release it afterward. The video delves into the implementation using pseudo-code, illustrating how it operates in user mode without kernel support. It discusses the potential for mutual exclusion failure due to preemption, highlighting the limitations of this method. The presenter also hints at the Test and Set concept as a solution for achieving mutual exclusion, providing a comprehensive overview suitable for students and professionals in the field.

Takeaways

• 🔐 **Lock Variable Fundamentals**: The script introduces the concept of a lock variable as a method to handle critical section problems in operating systems.
• 📚 **Reference to Galvin's Book**: The video script is based on Galvin's book, which is considered authoritative for operating systems, emphasizing its reliability.
• 👨‍🏫 **Educational Purpose**: The video is designed to educate students about lock variables, aiming to assist them in competitive exams, college/university exams, and interviews.
• 🔄 **Lock Variable Operation**: The lock variable works by allowing a process to enter the critical section only after acquiring the lock, which it must release upon completion.
• 💡 **Pseudo-code Explanation**: The implementation of the lock variable is explained through pseudo-code, highlighting its application in user mode without kernel or OS support.
• 🔁 **Multiprocess Applicability**: The solution is not limited to two processes; it can be extended to accommodate multiple processes, showcasing its scalability.
• 🚫 **No Kernel or OS Involvement**: The lock variable method operates at the application level, independent of the underlying kernel or operating system.
• 🔄 **Lock Value Representation**: A lock value of 0 indicates the critical section is vacant, while a value of 1 signifies it is occupied, providing a clear status.
• 🔄 **Process Execution Flow**: The script outlines how processes interact with the lock variable, detailing the steps they take to enter and exit the critical section.
• ⚠️ **Mutual Exclusion Concerns**: The script highlights that the lock variable method does not guarantee mutual exclusion, which is a critical requirement in critical section problems.
• 🔄 **Pre-emption Risks**: The video discusses the risks of pre-emption, explaining how it can lead to a failure in ensuring mutual exclusion, thus undermining the lock variable's reliability.

Q & A

What is a LOCK Variable?

A LOCK Variable is a method used to solve the critical section problem in concurrent programming. It allows a process to enter the critical section only if the lock is available (i.e., set to 0 or false), and once inside, it sets the lock to 1 or true, preventing other processes from entering until it releases the lock.

Why is the LOCK Variable considered one of the oldest methodologies?

The LOCK Variable is considered one of the oldest methodologies because it is a fundamental concept in operating systems that has been used for a long time to manage access to critical sections in a multi-process environment.

What does the value of the LOCK Variable represent?

The value of the LOCK Variable represents the availability of the critical section. A value of 0 or false indicates that the critical section is vacant, while a value of 1 or true indicates that it is occupied by a process.

How does the LOCK Variable help in implementing mutual exclusion?

The LOCK Variable helps in implementing mutual exclusion by ensuring that only one process can enter the critical section at a time. When a process wants to enter the critical section, it checks if the lock is available (0 or false), and if so, it sets the lock to 1 or true, thereby preventing other processes from entering until it releases the lock.

What is the entry code for a process using the LOCK Variable?

The entry code for a process using the LOCK Variable typically involves checking if the lock is available (lock == 0), and if it is, setting the lock to 1 to indicate that the critical section is now occupied.

Can the LOCK Variable guarantee mutual exclusion in all cases?

No, the LOCK Variable does not guarantee mutual exclusion in all cases. If a process is preempted after checking the lock but before setting it, another process could enter the critical section, leading to a violation of mutual exclusion.

What is the significance of the 'pre-empt' scenario mentioned in the script?

The 'pre-empt' scenario is significant because it demonstrates a potential weakness in the LOCK Variable method. If a process is preempted after checking the lock but before it sets the lock, another process can enter the critical section, thus violating the principle of mutual exclusion.

Why is it important to release the lock after a process has completed its work in the critical section?

It is important to release the lock after a process has completed its work in the critical section to allow other processes to enter the critical section. Failing to release the lock would result in a deadlock, where no other process can access the critical section.

What alternative methods are mentioned in the script to address the limitations of the LOCK Variable?

The script mentions the 'Test and Set' concept as an alternative method to address the limitations of the LOCK Variable. This concept includes changes to ensure mutual exclusion is achieved even in cases where preemption occurs.

How does the LOCK Variable work in a multi-process environment?

In a multi-process environment, the LOCK Variable works by allowing each process to check the lock's value before entering the critical section. If the lock is available, a process can set the lock and enter the critical section. Once done, it releases the lock, allowing other processes to proceed.

What is the role of the operating system in the LOCK Variable methodology?

In the LOCK Variable methodology, the operating system does not play a direct role. The locking mechanism is implemented in user mode, using application-level code, without relying on kernel support or operating system services.

Outlines

00:00

🔐 Introduction to Lock Variable for Critical Section Problem

The speaker begins by welcoming students to the Gate Smashers channel and introduces the topic of the LOCK variable, a fundamental method for solving the critical section problem in operating systems. The video aims to help students with competitive exams, college/university exams, and interviews by covering all aspects of the LOCK variable. The speaker emphasizes the importance of subscribers and likes for the channel. The LOCK variable methodology is explained as a way to control access to the critical section of a program, where a process must acquire the lock before entering and release it afterward. The speaker mentions that the LOCK variable is implemented in user mode without kernel support, using pseudo-code. The video will cover different cases to illustrate how the LOCK variable works, starting with a simple two-process scenario. The initial state of the lock variable is set to 0, indicating the critical section is vacant. The process flow for two processes, P1 and P2, is described, where P1 enters the critical section first because the lock value is 0, and then sets it to 1. P2, finding the lock value as 1, enters an infinite loop, waiting for the lock to be released. The speaker concludes by questioning the guarantee of mutual exclusion provided by the LOCK variable, hinting at potential issues that will be discussed in the next case.

05:09

🔒 Pre-emption Issue with Lock Variable

In the second paragraph, the speaker delves into a specific case where the LOCK variable fails to guarantee mutual exclusion due to pre-emption. The scenario involves two processes, P1 and P2, with the lock initially set to 0. P1 begins execution and checks the lock value, which is 0, allowing it to proceed. However, before P1 can set the lock to 1, it gets pre-empted, leaving the lock value at 0. P2 then arrives, sees the lock as 0, and also proceeds to set the lock to 1, entering the critical section. Meanwhile, P1 returns from its pre-emption and, unaware of P2's entry, overwrites the lock value to 1 and enters the critical section as well, leading to a violation of mutual exclusion. The speaker highlights the problem with the LOCK variable when pre-emption occurs between the check and set operations, allowing multiple processes to enter the critical section simultaneously. The video concludes with a teaser for the next concept, Test and Set, which aims to address this issue and ensure mutual exclusion.

Keywords

💡Lock Variable

A Lock Variable is a fundamental concept in operating systems used to manage access to critical sections of code, ensuring that only one process can execute a critical section at a time. In the video, the Lock Variable is described as a simple yet crucial tool for solving critical section problems. It is implemented by setting the variable to 1 when a process enters the critical section and resetting it to 0 upon exit. The video script uses the Lock Variable to illustrate the basic methodology of controlling access to critical sections, highlighting its simplicity and the need for proper implementation to avoid issues like mutual exclusion violations.

💡Critical Section

A Critical Section refers to a portion of a program where multiple processes need exclusive access to shared resources. In the context of the video, the critical section is the part of the code that must be executed without interference from other processes to maintain data integrity and consistency. The script explains how the Lock Variable is used to ensure that only one process can enter its critical section at a time, thus preventing conflicts and ensuring proper synchronization.

💡Mutual Exclusion

Mutual Exclusion is a key requirement in concurrent programming where the execution of critical sections by multiple processes must be exclusive to prevent data corruption and ensure system stability. The video emphasizes the importance of mutual exclusion and discusses how the Lock Variable can be used to achieve it. However, it also points out that the basic Lock Variable method does not guarantee mutual exclusion in all cases, such as when a process is preempted after checking the lock but before setting it.

💡Preemption

Preemption occurs when a running process is temporarily suspended by the operating system to allow another process to run. In the video, preemption is used as an example of a scenario where the basic Lock Variable method can fail to ensure mutual exclusion. If a process is preempted after checking the lock value but before it can set the lock, another process might incorrectly believe that the critical section is free and enter it, leading to a violation of mutual exclusion.

💡Pseudo-code

Pseudo-code is a high-level description of an algorithm or a program that uses the structure of a programming language but is intended for human reading rather than machine execution. In the video script, pseudo-code is used to illustrate how the Lock Variable works in practice, providing a clear and simplified example of how processes might check and set the lock before entering their critical sections.

💡API

An Application Programming Interface (API) is a set of routines, protocols, and tools for building software applications. In the context of the video, the API refers to the set of functions and procedures that allow user-mode applications to implement locking mechanisms without direct support from the kernel or operating system. The script mentions that the Lock Variable is implemented at the application level, using APIs to manage access to critical sections.

💡User Mode

User Mode is a state of a computer program when it is executing with limited access to the system resources and hardware. The video script mentions that the Lock Variable operates in user mode, meaning it is implemented at the application level without the need for kernel-level privileges or intervention. This approach simplifies the implementation but may have limitations in terms of ensuring system-wide mutual exclusion.

💡Galvin's Book

In the script, Galvin's book is referred to as the 'Bible of Operating Systems,' indicating its authoritative status and widespread use as a reference in the field. The video's reliance on Galvin's book for the explanation of the Lock Variable underscores the importance of established literature in understanding and teaching fundamental concepts in computer science.

💡Test and Set

Test and Set is a concept mentioned at the end of the video script as an alternative to the basic Lock Variable for ensuring mutual exclusion. While not fully explained in the provided script, it is implied that Test and Set is a more robust mechanism that addresses the limitations of the Lock Variable, particularly in handling preemption and ensuring that only one process can enter the critical section at a time.

💡Peterson's Solution

Peterson's Solution is an algorithm for mutual exclusion in a two-process system, mentioned in the script as an example of a method that is specifically designed for two processes. Unlike the general Lock Variable approach, which can be applied to multiple processes, Peterson's Solution is tailored for a two-process scenario. The script uses this to highlight the variety of solutions available for different contexts and the importance of choosing the right method based on the specific requirements of the system.

Highlights

Introduction to LOCK Variable as a method for solving critical section problems.

Reference to Galvin's book as an authoritative source on operating systems.

Explanation of the basic concept of a Lock Variable: acquiring a lock to enter and releasing it after exiting the critical section.

Discussion on the implementation of Lock Variable through pseudo-code without kernel support.

Case study of two processes, P1 and P2, demonstrating how the Lock Variable works.

Description of the initial state of the lock variable as 0, indicating the critical section is vacant.

Process P1's entry into the critical section when the lock variable is 0.

Process P2's attempt to enter the critical section while P1 holds the lock, resulting in an infinite loop.

Clarification that mutual exclusion is not guaranteed with the basic Lock Variable method.

Case 2 scenario illustrating a potential failure of mutual exclusion due to process preemption.

Example of process P1 being preempted after checking the lock variable but before acquiring it.

Process P2's successful entry into the critical section while P1 is preempted.

Return of process P1 after preemption and its overwrite of the lock variable.

Simultaneous entry of processes P1 and P2 into the critical section, violating mutual exclusion.

Introduction of the Test and Set concept as an improvement over the basic Lock Variable method.

Conclusion on the limitations of the Lock Variable method in ensuring mutual exclusion.

Transcripts

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

means to solve critical section problem what we are using? Lock variable.

It is one of the oldest methodology. If we say, I have written here from Galvin's book as it is

because we consider Galvin as Bible of Operating System. So from that funda,

I have written main points here. In your competitive exams, college/university exams, interview

if anything is asked from anywhere related to this, this video will help you a lot.

We will cover all the aspects in this. So guys, quickly like the video,

subscribe the channel if you haven't done yet and if you have, you can subscribe from more devices

subscribers are very important. So let's start.

What is the funda of Lock? Lock says that whatever wants to go in Critical Section

should acquire lock, when you complete work in critical section then release lock.

Basic methodology says this, but how to implement it, its pseudo-code?

Because it actually works on user mode. Meaning in this we don't take any support from kernel,

we don't take any support from operating system, we do it through API, it is an application

and in that application we have written a simple code and lock code,

not in full just the pseudo-code I have actually written over here.

So how it works I will tell you case wise. Like first case, second case and so on.

Look, let's say if I talk about case 1 firstly what we did, let's say there are 2 processes

P1 and P2 although this is a multiprocesses solution meaning

not like it is applicable on only two processes, there are many solutions like Peterson, etc.

which works on only 2 processes but in this you can run multiple processes also.

So look, let's say I take only 2, P1 and P2. Initially what we have the lock variable

its value is 0 at the start. You can take 0 or false, in terms of true or false

or in terms of 1 and 0. When value of lock is 0, what does this show?

It shows that the critical section is vacant. And if value of lock is 1 then what it shows is

that your critical section is full means in it already there is some process, okay.

Now look, value of lock is obviously 0 at start because we are just starting.

At start I will mention here value of lock as 0. So let's say case 1 P1 comes first,

process runs entry code, what is entry code? Lock==1. What is value of lock?

Value of lock is 0 at start, 0==1 is false, then it will come out and run on next line.

This and this, means you may understand you can take lock==1. It is possible that

it is given in the book like this, Lock!=0. Okay, it is the same thing. Lock not equal to 0

or lock is double equal to 1 is the same thing, at many places it may be given like this.

Now look, P1 comes, it executes line number 1, 0 is double equal to 1, false. And went to next line

lock is equal to 1. Value of lock is set from 0 to 1 and who enters the critical section?

P1 enters the critical section. P1 runs the first instruction, second one and

after running the thrid one it enters the critical section. Now at this time let's say,

P2 says I also want to go so P2 does what at first, While lock, what is value of lock? 1,

1==1, true. The moment it became true what happens to this? It gets stuck in infinite loop.

Getting the point or not? Because it is true, While true means there is a semicolon here,

so this gets stuck in infinite loop so P2 cannot go inside. Getting the point or not?

So here when P1 completes its work it comes out from critical section, executes line number 4,

value of lock was made 0 again. Now P2 says I want to go, so what is value of lock? 0==1, false.

Lock value is made 1 and P2 will enter the critical section. Getting the point?

So first P1 came then P2, you can run P2 first too it is the same thing.

So this way we generally use the lock funda but if you are asked is there any guarantee?

Look here, is there any guarantee that mutual exclusion will always be there?

Because in critical section problems the most important instruction is mutual exclusion.

Do yo give guarantee, does lock give guarantee that mutual exclusion will occur?

Looking at this case it feels that it will. But there is no guarantee. I will show you how here.

I'll take case 2, you note this in your notebook. Let's say again we take case 2, okay.

Now, what we do in case 2, in case 2 again we take P1, P2,

lock value is 0 at start means it is vacant. Now look P1 came first, it executed line number 1.

Line number 1 means what is the lock value at start? 0, okay. Lock value at start is 0.

So what it did? 0==1, false, went to the next line means it successfully executed line number 1

but keep in mind, note this down, after executing line number 1

as it was about to execute line number 2 it got pre-empt means it had some emergency,

after executing line number 1 as it was about to execute line number 2 means

as it was about to make lock=1, here in between these two it got pre-empt, had an emergency,

had to go to the washroom. It went away, and immediately P2 comes. P2 says now I will come

P2 sees value of lock is 0, 0==1, false.

P2 executes line number 1, goes to next line lock=1, value of lock becomes 1,

executes line number 2 also and who enters the critical section? P2 enters critical section.

Getting the point? Line number 1, 2 and 3 were executed. P1 comes back,

after completing its emergency P1 turned around and came back.

When it came back it will not restart, it has already run 1 instruction.

As soon as it returned it saw lock=1 means make value of lock as 1.

But value of lock whether it was 0 or 1, it ran this instruction, value of lock was already 1,

it overwrites 1 and made it 1. Because this instruction has nothing to do with

what is the previous value. That we have already done, it has already done that.

What it did? It executed line number 2 and after executing line number 2

entered the critical section. Now P1 has come and P2 has also come, mutual exclusion is gone,

nowhere near. In this case you can put P3, P4 as many processes as you want,

mutual exclusion is not there. Getting the point or not?

So this actually is a problem in lock variable because in between these two if pre-emption happens

then this funda fails. So next we will use the Test and Set concept where I will tell you

what changes were made in that and how mutual exclusion was achieved.

So these were the main points, works on user mode, application is used here,

kernel and operating system has nothing to do. We use it for multiprocess and

mutual exclusion is not guaranteed. So this is all about, and this is more than sufficient

related to the lock variable, thank you.