L-3.7: Turn Variable | Strict Alteration Method | Process Synchronization

Summary

In this educational video, the concept of 'Turn Variable' or 'Strict Alternation Method' is explored for process synchronization in a two-process system. The method operates in user mode without kernel support, using a 'turn' variable that initially holds a value of 0 or 1 to determine which process enters the critical section first. The script explains how mutual exclusion is achieved, ensuring that only one process accesses the critical section at a time. However, it points out that progress is not guaranteed as processes may block each other, and bounded waiting is ensured, preventing indefinite waiting. The method is platform-independent, making it versatile for various hardware and software environments.

Takeaways

• 🔐 **Strict Alteration Method**: The video introduces the Strict Alteration Method, also known as the Turn Variable, for process synchronization.
• 🚫 **Two-Process Limitation**: This method is designed to work with only two processes, making it unsuitable for more than two.
• 🛠️ **User Mode Operation**: It operates in user mode, without requiring kernel support, allowing applications to run it directly.
• 🔄 **Turn Variable**: A key component is the 'turn' variable, which can be initialized to either 0 or 1 to determine which process runs first.
• 🔒 **Mutual Exclusion**: The method ensures that when one process is in its critical section, the other cannot enter, thus satisfying mutual exclusion.
• ❌ **Lack of Progress**: Despite mutual exclusion, the method does not guarantee progress, as processes can block each other from entering the critical section.
• 🔁 **Strict Alternation**: Processes take turns entering the critical section, which is the essence of 'strict alteration', ensuring bounded waiting.
• 🌐 **Platform Independence**: The method is not dependent on specific hardware or software, making it versatile across different platforms.
• 🔄 **Entry Code**: The script explains the use of entry code, which involves a while loop checking the 'turn' variable to determine if a process can enter the critical section.
• 🔧 **Exit Code**: The exit code is crucial as it updates the 'turn' variable, allowing the other process to enter the critical section in the next cycle.

Q & A

What is the Strict Alternation Method?

The Strict Alternation Method, also known as the Turn Variable method, is a synchronization technique used in operating systems to manage access to critical sections by two processes in a way that ensures mutual exclusion and strict alternation.

How many processes does the Strict Alternation Method support?

The Strict Alternation Method supports only two processes. It is designed specifically for a two-process solution and cannot be extended to more than two processes.

In which mode does the Strict Alternation Method operate?

The Strict Alternation Method operates in user mode, meaning it does not require the support of the kernel or the operating system. It can be implemented directly through application code without the need for system-level intervention.

What is the purpose of the 'turn' variable in the Strict Alternation Method?

The 'turn' variable is used to determine which process gets to enter the critical section. It can initially be set to either 0 or 1, and its value dictates which process runs first, ensuring strict alternation between the two processes.

How does the mutual exclusion condition work in the Strict Alternation Method?

Mutual exclusion is ensured by the entry code that checks if the 'turn' variable matches the process's identifier. If it does not match, the process enters a loop until the condition is met, preventing the process from entering the critical section while the other is inside.

Is progress guaranteed in the Strict Alternation Method?

Progress is not guaranteed because the method can lead to a situation where one process continuously enters the critical section, causing the other process to wait indefinitely if it does not get the chance to enter when the critical section is empty.

What is the concept of bounded waiting in the context of the Strict Alternation Method?

Bounded waiting ensures that no process is made to wait indefinitely. In the Strict Alternation Method, each process gets a turn to enter the critical section after the other has exited, thus preventing any process from being starved of access.

Is the Strict Alternation Method dependent on any specific hardware or software?

No, the Strict Alternation Method is independent of hardware and software. It can be implemented on any platform without the need for specific hardware or software support.

How does the Strict Alternation Method handle the situation when the critical section is empty?

When the critical section is empty, the process whose turn it is, as indicated by the 'turn' variable, can enter. If the 'turn' variable does not match the process's identifier, it enters a loop until its turn comes, ensuring that the other process does not block its entry.

What are the key characteristics of the Strict Alternation Method?

The key characteristics of the Strict Alternation Method include mutual exclusion, lack of progress guarantee, bounded waiting, platform independence, and its applicability to only two processes.

Can you provide a simple example of how the Strict Alternation Method works?

Sure, let's say 'turn' is initially set to 0. Process P0 checks if 'turn' equals 0, which it does, so it enters the critical section. Meanwhile, Process P1 checks if 'turn' equals 1, which it does not, so it enters a loop until 'turn' becomes 1. Once P0 exits the critical section, it sets 'turn' to 1, allowing P1 to enter next.

Outlines

00:00

🔐 Introduction to Strict Alternation Method

The video begins with an introduction to the 'Strict Alternation Method,' also known as the 'Turn Variable' approach, which is a synchronization technique used in computer science. The method is designed for two processes and operates in user mode without the need for kernel support. The concept revolves around a 'turn' variable that can be initialized to either 0 or 1, determining which process gets to enter the critical section first. The video explains that if the 'turn' variable is 0, process P0 runs first, and if it's 1, process P1 runs first. The method ensures mutual exclusion by allowing only one process to enter the critical section at a time, preventing both processes from entering simultaneously. The presenter emphasizes the importance of subscribing to the channel and engaging with the content to better understand these concepts.

05:03

🔄 Progress and Bounded Waiting in Strict Alternation

The second paragraph delves into the concepts of progress and bounded waiting within the context of the Strict Alternation Method. It highlights that while mutual exclusion is achieved, progress is not guaranteed as one process can prevent the other from entering the critical section even when it's empty. The video illustrates this by showing that if process P0 enters first and sets the 'turn' variable to 1, process P1, despite wanting to enter, is unable to do so because it's not its 'turn'. The concept of bounded waiting is introduced to explain that no process is made to wait indefinitely; each process will have its turn to enter the critical section after the other has finished. The video concludes by stating that the Strict Alternation Method is platform-independent, meaning it can be implemented on any system without reliance on specific hardware or software.

Keywords

💡Turn Variable

The 'Turn Variable' is a synchronization mechanism used in concurrent programming to ensure that only one process accesses a critical section at a time. In the context of the video, it is part of the Strict Alternation Method, which is a solution for process synchronization that works with two processes. The turn variable is initialized to either 0 or 1, determining which process gets to enter the critical section first. It is a key element in demonstrating mutual exclusion, as it ensures that when one process is in the critical section, the other waits.

💡Strict Alternation Method

The 'Strict Alternation Method' is a process synchronization technique that allows two processes to alternate their access to a critical section. As explained in the video, this method is restricted to two processes and does not require kernel support, operating at the user mode. It ensures that if one process is in the critical section, the other cannot enter, thus maintaining mutual exclusion. The method also guarantees that each process will eventually get a turn, preventing starvation.

💡Process

In the video, a 'process' refers to an instance of a computer program that is being executed by the system. The script discusses a scenario with two processes, P0 and P1, which are trying to access a shared resource. The concept of 'process' is central to understanding synchronization, as it is the unit of work that must be managed to prevent conflicts and ensure efficient resource utilization.

💡Critical Section

The 'Critical Section' is a part of a program where multiple processes need exclusive access to shared resources. In the context of the video, the critical section is the code that must be executed without interference from other processes to maintain data consistency and integrity. The Turn Variable and Strict Alternation Method are used to manage access to this section, ensuring that only one process can enter at a time.

💡Mutual Exclusion

Mutual Exclusion is a property of concurrent programming where two or more threads or processes cannot be in their critical sections at the same time. The video script explains that the Strict Alternation Method ensures mutual exclusion by using the turn variable to control which process can enter the critical section. This prevents data corruption and ensures that shared resources are accessed safely.

💡User Mode

In the video, 'User Mode' refers to the state of a process where it operates without the privileges of the operating system kernel. The Strict Alternation Method is said to run in user mode, meaning it does not require kernel-level support. This is significant because it implies that the method can be implemented at the application level without relying on lower-level system resources.

💡Progress

Progress in the context of the video refers to the condition where if a process's critical section is empty and a process wishes to enter, it should not be unduly delayed by other processes. The script explains that while mutual exclusion is satisfied, progress is not guaranteed in the Strict Alternation Method because one process can continuously enter the critical section, preventing the other from entering, thus not satisfying the progress condition.

💡Bounded Waiting

Bounded Waiting is a property of synchronization algorithms that ensures that a process will not wait indefinitely to enter its critical section. The video script mentions that the Strict Alternation Method satisfies bounded waiting because each process will eventually get its turn to enter the critical section after the other process has finished, thus preventing starvation and ensuring fairness.

💡Platform Independence

The term 'Platform Independence' in the video indicates that the Strict Alternation Method is not dependent on specific hardware or software platforms. It can be implemented and will function correctly across various systems. This is an important feature for synchronization methods, as it allows for greater flexibility and portability in software development.

💡Non-Critical Section

The 'Non-Critical Section' is the part of a program where processes can execute concurrently without the need for synchronization. In the video, processes operate in their non-critical sections until they need to access shared resources, at which point they must enter the critical section. The Turn Variable and Strict Alternation Method manage the transition between these sections, coordinating access to ensure proper synchronization.

Highlights

Introduction to Turn Variable, also known as Strict Alternation Method, and its application in competitive exams, college/university exams, and interviews.

Turn Variable is a method designed for 2-process synchronization with a restriction of not supporting more than two processes.

The method operates in user mode without the need for kernel support, allowing direct application code execution.

Pseudo-code explanation for the implementation of the Turn Variable with two processes, P0 and P1.

The turn variable can initially be set to 0 or 1, determining which process runs first.

Entry code for processes to enter the critical section based on the value of the turn variable.

Mutual exclusion is guaranteed as one process in the critical section prevents the other from entering.

Progress is not satisfied as processes can block each other from entering the critical section even when it's empty.

Bounded waiting is ensured, as processes take turns entering the critical section and do not wait indefinitely.

The method is platform-independent and can be run on any hardware or software.

Explanation of how the turn variable ensures that no process is indefinitely postponed from entering the critical section.

Detailed walkthrough of the process flow when the turn variable is set to 0 and P0 gets priority.

Detailed walkthrough of the process flow when the turn variable is set to 1 and P1 gets priority.

Discussion on how the strict alternation method ensures that every process gets a fair chance to enter the critical section.

The method's simplicity and its reliance on a single variable to manage process synchronization.

The potential for the Turn Variable method to be used in various synchronization scenarios where only two processes are involved.

Conclusion and a reminder to note all aspects of the Turn Variable method for potential questions in exams or interviews.

Transcripts

Dear students welcome to Gate Smashers in this video I'm going to explain Turn Variable

which we call Strict Alteration Method and in this video we will discuss all the points

related to Turn Variable which in your competitive exams, college/ university exams, interviews

anywhere if you are asked you can easily answer.

So guys quickly like the video, subscribe the channel if you have not done yet

and even if you have then you can subscribe from more devices, subscribers are very important.

So let's start Turn Variable, before this I have told you in the process synchronization

about the basic lock mechanism then we talked about Test and set instruction

then we are going to talk about here Turn Variable. So it is again a 2 process solution means

this method that we are making this strict alteration method that we are applying,

it works for only 2 processes, you cannot take more than 2 processes that is the restriction.

Second, it runs at the user mode means where does it work? It works on user mode.

Support of kernel is not required here, kernel, operating system we are not using here,

means directly we will write the code through application and we will directly run it.

So it works on user mode. This becomes its pseudo-code, okay. We take process P0, process P1

any name you can take, there are 2 processes P0 and P1. And this turn variable that we have,

the turn variable int turn its value you can initially take 0 or 1 because we have 2 processes

so there can be only 2 values either 0 or 1. If we take its value 0,

so means process P0 will run first, if I take turn value 1 first then process P1 will work first.

So you can take any value, let's say initially we take value of int turn as 0.

Now what our entry code says, means before this it is our non-critical section.

Before entering critical section entry code, on entry code when you run while turn not equal to 0,

now look value of turn is what? 0. 0 not equal to 0, what will this return?

This will give what output? False. Because 0 not equal to 0, but 0 is equal to 0 so means

what will this give? False. So as soon as it becomes false, what is outside? Semicolon,

so means this will go out of this, if this was true then

it would have been trapped in an infinite loop inside it. But this became false, came out,

coming out means what went in critical section? P0 went in the critical section.

Now look who is there already? P0 is in critical section, now we check can P1 come at this time.

Look P1 comes P1 says I also want to come. Let's say this is our non-critical section so to enter

it runs the entry code while turn not equal to 1, so value of turn is now what? 0.

0 not equal to 1, so 0 not equal to 1 is what? It is true. So while becomes true. True means

it got stuck in loop in semicolon means this cannot enter critical section because it stopped here.

Means when P0 is in then P1 cannot enter. Similarly if you took value of turn initially let's say 1

then first who would have entered? First P1 would have entered and then

when P0 says that I want to come then 1 not equal to 0 would be what? True,

then P0 would be trapped and P0 could not enter means what you can say,

mutual exclusion condition is satisfied here. If you are asked like this anywhere that

whether turn variable and strict alteration always ensures, guarantees that mutual exclusion

will definitely happen, then yes you can say it is totally true because you have already proved it

that if one is in then the other one cannot enter. So this way we can decide that

yes, it is mutually exclusive. Second if we say here, progress. If we talk about progress,

then what progress says is that if my critical section is empty,

and either of the two wants to enter first then they will not stop one another,

progress means what, critical section is empty, P0 says I want to come then P1 will not stop it

which generally happens in India that if one wants to progress then another will pull his leg.

So this story of progress I have told many times before, but here if we check then look

let's say we initially take value of turn as 0, okay. You can take whatever 1 or 0,

initially we take value of turn as 0, critical section is empty, P1 says I want to come, P1 can say

obviously can say if critical section is empty then either of the two can say,

so we say that P1 says that I want to enter. So P1 says that okay in order to enter

I will run the condition turn not equal to 1. What is the value of turn? 0. 0 not equal to 1, true.

Where is this trapped? It is trapped in this in infinite loop, P1 cannot enter critical section.

Why can't P1 enter critical section? Because value of turn is 0.

Now you will feel sir, then how will P1 come? When can P1 come? when P0 goes first,

look P0 goes first, 0 not equal to 0, becomes false. Who enters critical section? P0 enters.

When it comes exits critical section then it runs exit code turn is equal to 1.

So turn= 1 means value of turn becomes 1, now if P1 applies that I want go now what can happen,

P1 can enter. Getting the point or not? Means what? If critical section is empty

and a process wants to enter then the other is stopping it, the other is saying I will go first

when I enter and exit then I will change value of turn, then you can enter. Getting the point?

Similarly if you initially take value of turn as 1 then P0 cannot go, then first P1 will go,

it will make value of turn 0 after coming out then P0 can enter. So what does this mean?

If critical section is empty then either of the two can enter, but these two are stopping each other.

So mutual exclusion occurred but if we talk about progress then that is not satisfied here.

Third if we say bounded waiting, what is bounded waiting? It is not like if one is using

critical section then again it enters, third time again enters, fourth time again enters,

this way the other one will keep waiting. Getting the point or not? It happens many times that

one person took away the opportunity, means took away a job

so when the next guy who was going to take the job he left that job and took the next job.

Means one person is grabbing the opportunity again and again and the other poor guy is waiting,

so bounded waiting means what? Let it wait but for a limited amount of time.

It should not happen that he is waiting infinitely. So if we talk about this then look

if first P1 enters then when P1 exits, let's say first P0 enters so when P0 enters then

when it exits it will make turn value 1. Now again if P0 wants to go, it cannot go because

after that whose turn will come? P1. Similarly let's say first P1 enters and

when P1 exits then what will it make turn value? 0. Then if P1 says I want to go again,

it cannot enter, why? now it is the turn of P0, okay. That is why its name is strict alteration.

First this one's turn then after that this one's turn then after that this one's turn,

this way they are changing turns means bounded weight is there, no one is waiting infinitely here,

everyone will have their turn. Then if we talk about here, what is the fourth option we have?

fourth condition of critical section says that whether it is dependent on some hardware or software?

No, this is independent of hardware and software. You can run this code on any platform,

it will run on all platforms, this is independent of platform, hardware.

So you note all the aspects, out of these some or the question will be asked.

Thank you.