Month: November 2018

Interest Variable | Process Synchronization

Operating System

Process Synchronization-

 

Before you go through this article, make sure that you have gone through the previous article on Process Synchronization.

 

We have discussed-

  • Process Synchronization provides a synchronization among the processes.
  • Synchronization mechanisms allow the processes to access critical section in a synchronized manner.
  • This avoids the inconsistent results.

 

Interest Variable-

 

  • Interest variable is a synchronization mechanism that provides synchronization among two processes.
  • It uses an interest variable to provide the synchronization.

 

It is implemented as-

 

 

Initially, interest [0] and interest [1] are set to False.

  • Interest value [0] = False means that process P0 is not interested to enter the critical section.
  • Interest value [0] = True means that process P0 is interested to enter the critical section.
  • Interest value [1] = False means that process P1 is not interested to enter the critical section.
  • Interest value [1] = True means that process P1 is interested to enter the critical section.

 

Working-

 

This synchronization mechanism works as explained in the following scenes-

 

Scene-01:

 

  • Process P0 arrives.
  • It sets interest[0] = True.
  • Now, it executes while loop condition- interest [1] == True.
  • Since interest [1] is initialized to False, so it returns value 0 to the while loop.
  • The while loop condition breaks.
  • Process P0 enters the critical section and executes.
  • Now, even if process P0 gets preempted in the middle, process P1 can not enter the critical section.
  • Process P1 can not enter unless process P0 completes and sets the interest [0] = False.

 

Scene-02:

 

  • Process P1 arrives.
  • It sets interest[1] = True.
  • Now, it executes while loop condition- interest [0] == True.
  • Process P0 has already shown its interest by setting interest [0] = True.
  • So, it returns value 1 to the while loop.
  • The while loop condition satisfies.
  • The process P1 is trapped inside an infinite while loop.
  • The while loop keeps the process P1 busy until the interest [0] value becomes False and its condition breaks.

 

Scene-03:

 

  • Process P0 comes out of the critical section and sets the interest [0] value to False.
  • The while loop condition of process P1 breaks.
  • Now, the process P1 waiting for the critical section enters the critical section and execute.
  • Now, even if process P1 gets preempted in the middle, process P0 can not enter the critical section.
  • Process P0 can not enter unless process P1 completes and sets the interest [1] = False.

 

Also Read- Criteria For Synchronization Mechanisms

 

Characteristics-

 

The characteristics of this synchronization mechanism are-

  • It ensures mutual exclusion.
  • It does not follow strict alternation approach.
  • It ensures progress since if a process is not interested to enter the critical section, it never stops the other process to enter the critical section.
  • It is architectural neutral since it does not require any support from the operating system.
  • It is a busy waiting solution which keeps the CPU busy when the process is actually waiting.
  • It suffers from deadlock.
  • Since it suffers from deadlock, it does not guarantee bounded waiting.

 

How it suffers from deadlock?

 

  • This synchronization mechanism may cause deadlock between the processes.
  • Deadlock may occur through the following sequence of scenes-

 

Scene-01:

 

  • Process P0 arrives.
  • It sets interest[0] = True.
  • Now, it gets preempted and process P1 gets scheduled.

 

Scene-02:

 

  • Process P1 arrives.
  • It sets interest[1] = True.
  • Now, it gets preempted.

 

Scene-03:

 

  • Process P0 gets scheduled again.
  • Now, it can not break the while loop condition- interest [1] == True since process P1 has shown its interest for executing critical section before its arrival.
  • It keeps waiting in the infinite while loop for process P1 to complete its execution first.

 

Scene-04:

 

  • Later, Process P1 gets scheduled again.
  • Now, it also can not break the while loop condition- interest [0] == True since process P0 is also interested for executing critical section.
  • It keeps waiting in the infinite while loop for process P0 to complete its execution first.

Thus, both the processes are deadlocked.

 

To gain better understanding about Interest Variable,

Watch this Video Lecture

 

Next Article- Practice Problems On Synchronization Mechanisms

 

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun

Turn Variable | Process Synchronization

Operating System

Process Synchronization-

 

Before you go through this article, make sure that you have gone through the previous article on Process Synchronization.

 

We have discussed-

  • Process Synchronization provides a synchronization among the processes.
  • Synchronization mechanisms allow the processes to access critical section in a synchronized manner.
  • This avoids the inconsistent results.

 

Turn Variable-

 

  • Turn variable is a synchronization mechanism that provides synchronization among two processes.
  • It uses a turn variable to provide the synchronization.

 

It is implemented as-

 

 

Initially, turn value is set to 0.

  • Turn value = 0 means it is the turn of process P0 to enter the critical section.
  • Turn value = 1 means it is the turn of process P1 to enter the critical section.

 

Working-

 

This synchronization mechanism works as explained in the following scenes-

 

Scene-01:

 

  • Process P0 arrives.
  • It executes the turn!=0 instruction.
  • Since turn value is set to 0, so it returns value 0 to the while loop.
  • The while loop condition breaks.
  • Process P0 enters the critical section and executes.
  • Now, even if process P0 gets preempted in the middle, process P1 can not enter the critical section.
  • Process P1 can not enter unless process P0 completes and sets the turn value to 1.

 

Scene-02:

 

  • Process P1 arrives.
  • It executes the turn!=1 instruction.
  • Since turn value is set to 0, so it returns value 1 to the while loop.
  • The returned value 1 does not break the while loop condition.
  • The process P1 is trapped inside an infinite while loop.
  • The while loop keeps the process P1 busy until the turn value becomes 1 and its condition breaks.

 

Scene-03:

 

  • Process P0 comes out of the critical section and sets the turn value to 1.
  • The while loop condition of process P1 breaks.
  • Now, the process P1 waiting for the critical section enters the critical section and execute.
  • Now, even if process P1 gets preempted in the middle, process P0 can not enter the critical section.
  • Process P0 can not enter unless process P1 completes and sets the turn value to 0.

 

Also Read- Criteria For Synchronization Mechanisms

 

Characteristics-

 

The characteristics of this synchronization mechanism are-

  • It ensures mutual exclusion.
  • It follows the strict alternation approach.

 

Strict Alternation Approach

 

In strict alternation approach,

  • Processes have to compulsorily enter the critical section alternately whether they want it or not.
  • This is because if one process does not enter the critical section, then other process will never get a chance to execute again.

 

  • It does not guarantee progress since it follows strict alternation approach.
  • It ensures bounded waiting since processes are executed turn wise one by one and each process is guaranteed to get a chance.
  • It ensures processes does not starve for the CPU.
  • It is architectural neutral since it does not require any support from the operating system.
  • It is deadlock free.
  • It is a busy waiting solution which keeps the CPU busy when the process is actually waiting.

 

To gain better understanding about Turn Variable,

Watch this Video Lecture

 

Next Article- Interest Variable | Synchronization Mechanism

 

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Test and Set | Process Synchronization

Operating System

Process Synchronization-

 

Before you go through this article, make sure that you have gone through the previous article on Process Synchronization.

 

We have discussed-

  • Process Synchronization provides a synchronization among the processes.
  • Synchronization mechanisms allow the processes to access critical section in a synchronized manner.
  • This avoids the inconsistent results.

 

Test and Set Lock –

 

  • Test and Set Lock (TSL) is a synchronization mechanism.
  • It uses a test and set instruction to provide the synchronization among the processes executing concurrently.

 

Test-and-Set Instruction

 

  • It is an instruction that returns the old value of a memory location and sets the memory location value to 1 as a single atomic operation.
  • If one process is currently executing a test-and-set, no other process is allowed to begin another test-and-set until the first process test-and-set is finished.

 

It is implemented as-

 

 

Initially, lock value is set to 0.

  • Lock value = 0 means the critical section is currently vacant and no process is present inside it.
  • Lock value = 1 means the critical section is currently occupied and a process is present inside it.

 

Working-

 

This synchronization mechanism works as explained in the following scenes-

 

Scene-01:

 

  • Process P0 arrives.
  • It executes the test-and-set(Lock) instruction.
  • Since lock value is set to 0, so it returns value 0 to the while loop and sets the lock value to 1.
  • The returned value 0 breaks the while loop condition.
  • Process P0 enters the critical section and executes.
  • Now, even if process P0 gets preempted in the middle, no other process can enter the critical section.
  • Any other process can enter only after process P0 completes and sets the lock value to 0.

 

Scene-02:

 

  • Another process P1 arrives.
  • It executes the test-and-set(Lock) instruction.
  • Since lock value is now 1, so it returns value 1 to the while loop and sets the lock value to 1.
  • The returned value 1 does not break the while loop condition.
  • The process P1 is trapped inside an infinite while loop.
  • The while loop keeps the process P1 busy until the lock value becomes 0 and its condition breaks.

 

Scene-03:

 

  • Process P0 comes out of the critical section and sets the lock value to 0.
  • The while loop condition breaks.
  • Now, process P1 waiting for the critical section enters the critical section.
  • Now, even if process P1 gets preempted in the middle, no other process can enter the critical section.
  • Any other process can enter only after process P1 completes and sets the lock value to 0.

 

Characteristics-

 

The characteristics of this synchronization mechanism are-

  • It ensures mutual exclusion.
  • It is deadlock free.
  • It does not guarantee bounded waiting and may cause starvation.
  • It suffers from spin lock.
  • It is not architectural neutral since it requires the operating system to support test-and-set instruction.
  • It is a busy waiting solution which keeps the CPU busy when the process is actually waiting.

 

Also Read- Criteria For Synchronization Mechanisms

 

Explanations-

 

Point-01:

 

This synchronization mechanism guarantees mutual exclusion.

 

Explanation-

 

  • The success of the mechanism in providing mutual exclusion lies in the test-and-set instruction.
  • Test-and-set instruction returns the old value of memory location (lock) and updates its value to 1 simultaneously.
  • The fact that these two operations are performed as a single atomic operation ensures mutual exclusion.
  • Preemption after reading the lock value was a major cause of failure of lock variable synchronization mechanism.
  • Now, no preemption can occur immediately after reading the lock value.

 

Also read- Lock Variable Synchronization Mechanism

 

Point-02:

 

This synchronization mechanism guarantees freedom from deadlock.

 

Explanation-

 

  • After arriving, process executes the test-and-set instruction which returns the value 0 to while loop and sets the lock value to 1.
  • Now, no other process can enter the critical section until the process that has begin the test-and-set finishes executing the critical section.
  • Other processes can enter only after the process that has begin the test-and-test finishes and set the lock value to 0.
  • This prevents the occurrence of deadlock.

 

Also read- Deadlock in Operating System

 

Point-03:

 

This synchronization mechanism does not guarantee bounded waiting.

 

Explanation-

 

  • This synchronization mechanism may cause a process to starve for the CPU.
  • There might exist an unlucky process which when arrives to execute the critical section finds it busy.
  • So, it keeps waiting in the while loop and eventually gets preempted.
  • When it gets rescheduled and comes to execute the critical section, it finds another process executing the critical section.
  • So, again, it keeps waiting in the while loop and eventually gets preempted.
  • This may happen several times which causes that unlucky process to starve for the CPU.

 

Point-04:

 

This synchronization mechanism suffers from spin lock where the execution of processes is blocked.

 

Explanation-

 

Consider a scenario where-

  • Priority scheduling algorithm is used for scheduling the processes.
  • On arrival of a higher priority process, a lower priority process is preempted  from the critical section.

Now,

  • Higher priority process comes to execute the critical section.
  • But synchronization mechanism does not allow it to enter the critical section before lower priority process completes.
  • But lower priority process can not be executed before the higher priority process completes execution.
  • Thus, the execution of both the processes is blocked.

 

To gain better understanding about Test and Set Lock,

Watch this Video Lecture

 

Next Article- Turn Variable | Synchronization Mechanism

 

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Lock Variable | Process Synchronization

Operating System

Process Synchronization-

 

Before you go through this article, make sure that you have gone through the previous article on Process Synchronization.

 

We have discussed-

  • Process Synchronization provides a synchronization among the processes.
  • Synchronization mechanisms allow the processes to access critical section in a synchronized manner.
  • This avoids the inconsistent results.

 

Lock Variable-

 

  • Lock variable is a synchronization mechanism.
  • It uses a lock variable to provide the synchronization among the processes executing concurrently.
  • However, it completely fails to provide the synchronization.

 

It is implemented as-

 

 

Initially, lock value is set to 0.

  • Lock value = 0 means the critical section is currently vacant and no process is present inside it.
  • Lock value = 1 means the critical section is currently occupied and a process is present inside it.

 

Working-

 

This synchronization mechanism is supposed to work as explained in the following scenes-

 

Scene-01:

 

  • Process P0 arrives.
  • It executes the lock!=0 instruction.
  • Since lock value is set to 0, so it returns value 0 to the while loop.
  • The while loop condition breaks.
  • It sets the lock value to 1 and enters the critical section.
  • Now, even if process P0 gets preempted in the middle, no other process can enter the critical section.
  • Any other process can enter only after process P0 completes and sets the lock value to 0.

 

Scene-02:

 

  • Another process P1 arrives.
  • It executes the lock!=0 instruction.
  • Since lock value is set to 1, so it returns value 1 to the while loop.
  • The returned value 1 does not break the while loop condition.
  • The process P1 is trapped inside an infinite while loop.
  • The while loop keeps the process P1 busy until the lock value becomes 0 and its condition breaks.

 

Scene-03:

 

  • Process P0 comes out of the critical section and sets the lock value to 0.
  • The while loop condition of process P1 breaks.
  • It sets the lock value to 1 and enters the critical section.
  • Now, even if process P1 gets preempted in the middle, no other process can enter the critical section.
  • Any other process can enter only after process P1 completes and sets the lock value to 0.

 

Failure of the Mechanism-

 

  • The mechanism completely fails to provide the synchronization among the processes.
  • It can not even guarantee to meet the basic criterion of mutual exclusion.

 

Also Read- Criteria For Synchronization Mechanisms

 

Explanation-

 

The occurrence of the following scenes may lead to two processes present inside the critical section at the same time-

 

Scene-01:

 

  • Process P0 arrives.
  • It executes the lock!=0 instruction.
  • Since lock value is set to 0, so it returns value 0 to the while loop.
  • The while loop condition breaks.
  • Now, process P0 gets preempted before it sets the lock value to 1.

 

Scene-02:

 

  • Another process P1 arrives.
  • It executes the lock!=0 instruction.
  • Since lock value is still 0, so it returns value 0 to the while loop.
  • The while loop condition breaks.
  • It sets the lock value to 1 and enters the critical section.
  • Now, process P1 gets preempted in the middle of the critical section.

 

Scene-03:

 

  • Process P0 gets scheduled again.
  • It resumes its execution.
  • Before preemption, it had already failed the while loop condition.
  • Now, it begins execution from the next instruction.
  • It sets the lock value to 1 (which is already 1) and enters the critical section.

 

Thus, both the processes get to present inside the critical section at the same time.

 

Similarly,

  • If there are n processes, then all of them may be present inside the critical section at the same time.
  • This happens when each process gets preempted immediately after breaking the while loop condition.

 

Characteristics-

 

The characteristics of this synchronization mechanism are-

  • It can be used for any number of processes.
  • It is a software mechanism implemented in user mode.
  • There is no support required from the operating system.
  • It is a busy waiting solution which keeps the CPU busy when the process is actually waiting.
  • It does not fulfill any criteria of synchronization mechanism.

 

Conclusion-

 

  • The lock variable synchronization mechanism is a complete failure.
  • Thus, it is never used.

 

To gain better understanding about Lock Variable,

Watch this Video Lecture

 

Next Article- Test and Set Lock | Synchronization Mechanism

 

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Critical Section | Critical Section Problem

Operating System

Critical Section-

 

Before you go through this article, make sure that you have gone through the previous article on Process Synchronization.

 

We have discussed-

  • Process Synchronization controls the execution of processes running concurrently so as to produce the consistent results.
  • Critical section is a part of the program where shared resources are accessed by the process.

 

Critical Section Problem-

 

  • If multiple processes access the critical section concurrently, then results produced might be inconsistent.
  • This problem is called as critical section problem.

 

Synchronization Mechanisms-

 

Synchronization mechanisms allow the processes to access critical section in a synchronized manner to avoid the inconsistent results.

 

For every critical section in the program, a synchronization mechanism adds-

  • An entry section before the critical section
  • An exit section after the critical section

 

 

Entry Section-

 

  • It acts as a gateway for a process to enter inside the critical section.
  • It ensures that only one process is present inside the critical section at any time.
  • It does not allow any other process to enter inside the critical section if one process is already present inside it.

 

Exit Section-

 

  • It acts as an exit gate for a process to leave the critical section.
  • When a process takes exit from the critical section, some changes are made so that other processes can enter inside the critical section.

 

Criteria For Synchronization Mechanisms-

 

Any synchronization mechanism proposed to handle the critical section problem should meet the following criteria-

 

 

  1. Mutual Exclusion
  2. Progress
  3. Bounded Wait
  4. Architectural Neutral

 

1. Mutual Exclusion-

 

The mechanism must ensure-

  • The processes access the critical section in a mutual exclusive manner.
  • Only one process is present inside the critical section at any time.
  • No other process can enter the critical section until the process already present inside it completes.

 

2. Progress-

 

The mechanism must ensure-

  • An entry of a process inside the critical section is not dependent on the entry of another process inside the critical section.
  • A process can freely enter inside the critical section if there is no other process present inside it.
  • A process enters the critical section only if it wants to enter.
  • A process is not forced to enter inside the critical section if it does not want to enter.

 

3. Bounded Wait-

 

The mechanism should ensure-

  • The wait of a process to enter the critical section is bounded.
  • A process gets to enter the critical section before its wait gets over.

 

4. Architectural Neutral-

 

The mechanism should ensure-

  • It can run on any architecture without any problem.
  • There is no dependency on the architecture.

 

Important Notes-

 

Note-01:

 

  • Mutual Exclusion and Progress are the mandatory criteria.
  • They must be fulfilled by all the synchronization mechanisms.

 

Note-02:

 

  • Bounded waiting and Architectural neutrality are the optional criteria.
  • However, it is recommended to meet these criteria if possible.

 

To gain better understanding of Critical Section in OS,

Watch this Video Lecture

 

Next Article- Lock Variable | Synchronization Mechanism

 

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.