Operating System | Gate Vidyalay

Category: Operating System

Test and Set | Process Synchronization

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 P₀ 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 P₀ enters the critical section and executes.
Now, even if process P₀ gets preempted in the middle, no other process can enter the critical section.
Any other process can enter only after process P₀ completes and sets the lock value to 0.

Scene-02:

Another process P₁ 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 P₁ is trapped inside an infinite while loop.
The while loop keeps the process P₁ busy until the lock value becomes 0 and its condition breaks.

Scene-03:

Process P₀ comes out of the critical section and sets the lock value to 0.
The while loop condition breaks.
Now, process P₁ waiting for the critical section enters the critical section.
Now, even if process P₁ gets preempted in the middle, no other process can enter the critical section.
Any other process can enter only after process P₁ 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 P₀ 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 P₀ gets preempted in the middle, no other process can enter the critical section.
Any other process can enter only after process P₀ completes and sets the lock value to 0.

Scene-02:

Another process P₁ 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 P₁ is trapped inside an infinite while loop.
The while loop keeps the process P₁ busy until the lock value becomes 0 and its condition breaks.

Scene-03:

Process P₀ comes out of the critical section and sets the lock value to 0.
The while loop condition of process P₁ breaks.
It sets the lock value to 1 and enters the critical section.
Now, even if process P₁ gets preempted in the middle, no other process can enter the critical section.
Any other process can enter only after process P₁ 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 P₀ 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 P₀ gets preempted before it sets the lock value to 1.

Scene-02:

Another process P₁ 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 P₁ gets preempted in the middle of the critical section.

Scene-03:

Process P₀ 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-

Mutual Exclusion
Progress
Bounded Wait
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.

Process Synchronization | Race Condition in OS

Operating System

Process Synchronization-

When multiple processes execute concurrently sharing system resources, then inconsistent results might be produced.

Process Synchronization is a mechanism that deals with the synchronization of processes.
It controls the execution of processes running concurrently to ensure that consistent results are produced.

Need of Synchronization-

Process synchronization is needed-

When multiple processes execute concurrently sharing some system resources.
To avoid the inconsistent results.

Critical Section-

Critical section is a section of the program where a process access the shared resources during its execution.

Example-

The following illustration shows how inconsistent results may be produced if multiple processes execute concurrently without any synchronization.

Consider-

Two processes P₁ and P₂ are executing concurrently.
Both the processes share a common variable named “count” having initial value = 5.
Process P1 tries to increment the value of count.
Process P2 tries to decrement the value of count.

In assembly language, the instructions of the processes may be written as-

Now, when these processes execute concurrently without synchronization, different results may be produced.

Case-01:

The execution order of the instructions may be-

P₁(1), P₁(2), P₁(3), P₂(1), P₂(2), P₂(3)

In this case,

Final value of count = 5

Case-02:

The execution order of the instructions may be-

P₂(1), P₂(2), P₂(3), P₁(1), P₁(2), P₁(3)

In this case,

Final value of count = 5

Case-03:

The execution order of the instructions may be-

P₁(1), P₂(1), P₂(2), P₂(3), P₁(2), P₁(3)

In this case,

Final value of count = 6

Case-04:

The execution order of the instructions may be-

P₂(1), P₁(1), P₁(2), P₁(3), P₂(2), P₂(3)

In this case,

Final value of count = 4

Case-05:

The execution order of the instructions may be-

P₁(1), P₁(2), P₂(1), P₂(2), P₁(3), P₂(3)

In this case,

Final value of count = 4

It is clear from here that inconsistent results may be produced if multiple processes execute concurrently without any synchronization.

Race Condition-

Race condition is a situation where-

The final output produced depends on the execution order of instructions of different processes.
Several processes compete with each other.

The above example is a good illustration of race condition.

PRACTICE PROBLEM BASED ON PROCESS SYNCHRONIZATION-

Problem-

The following two functions P1 and P2 that share a variable B with an initial value of 2 execute concurrently-

The number of distinct values that B can possibly take after the execution is-

Solution-

Different execution order of the instructions of P1 and P2 produce different results.

Case-01:

The execution order of the instructions may be-

P₁(1), P₁(2), P₂(1), P₂(2)

In this case,

Final value of B = 3

Case-02:

The execution order of the instructions may be-

P₂(1), P₂(2), P₁(1), P₁(2)

In this case,

Final value of B = 4

Case-03:

The execution order of the instructions may be-

P₁(1), P₂(1), P₂(2), P₁(2)

In this case,

Final value of B = 2

Case-04:

The execution order of the instructions may be-

P₂(1), P₁(1), P₁(2), P₂(2)

In this case,

Final value of B = 3

Case-05:

The execution order of the instructions may be-

P₁(1), P₂(1), P₁(2), P₂(2)

In this case,

Final value of B = 3

Case-06:

The execution order of the instructions may be-

P₂(1), P₁(1), P₂(2), P₁(2)

In this case,

Final value of B = 2

From here,

Distinct values that may be produced are 2, 3 and 4.
Number of distinct values that may be produced = 3

Thus, Option (A) is correct.

To gain better understanding of Process Synchronization,

Watch this Video Lecture

Next Article- Synchronization Mechanisms

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

CPU Scheduling | Practice Problems | Numericals

Operating System

CPU Scheduling Algorithms-

Various CPU scheduling algorithms are-

PRACTICE PROBLEMS BASED ON CPU SCHEDULING ALGORITHMS-

Problem-01:

Consider three process, all arriving at time zero, with total execution time of 10, 20 and 30 units respectively. Each process spends the first 20% of execution time doing I/O, the next 70% of time doing computation, and the last 10% of time doing I/O again. The operating system uses a shortest remaining compute time first scheduling algorithm and schedules a new process either when the running process gets blocked on I/O or when the running process finishes its compute burst. Assume that all I/O operations can be overlapped as much as possible. For what percentage of does the CPU remain idle?

0%
10.6%
30.0%
89.4%

Solution-

According to question, we have-

	Total Burst Time	I/O Burst	CPU Burst	I/O Burst
Process P1	10	2	7	1
Process P2	20	4	14	2
Process P3	30	6	21	3

The scheduling algorithm used is Shortest Remaining Time First.

Gantt Chart-

Percentage of time CPU remains idle

= (5 / 47) x 100

= 10.638%

Thus, Option (B) is correct.

Problem-02:

Consider the set of 4 processes whose arrival time and burst time are given below-

Process No.	Arrival Time	Burst Time
Process No.	Arrival Time	CPU Burst	I/O Burst	CPU Burst
P1	0	3	2	2
P2	0	2	4	1
P3	2	1	3	2
P4	5	2	2	1

If the CPU scheduling policy is Shortest Remaining Time First, calculate the average waiting time and average turn around time.

Solution-

Gantt Chart-

Now, we know-

Turn Around time = Exit time – Arrival time
Waiting time = Turn Around time – Burst time

Also read- Various Times Of Process

Process Id	Exit time	Turn Around time	Waiting time
P1	11	11 – 0 = 11	11 – (3+2) = 6
P2	7	7 – 0 = 7	7 – (2+1) = 4
P3	9	9 – 2 = 7	7 – (1+2) = 4
P4	16	16 – 5 = 11	11 – (2+1) = 8

Now,

Average Turn Around time = (11 + 7 + 7 + 11) / 4 = 36 / 4 = 9 units
Average waiting time = (6 + 4 + 4 + 8) / 4 = 22 / 5 = 4.4 units

Problem-03:

Consider the set of 4 processes whose arrival time and burst time are given below-

Process No.	Arrival Time	Priority	Burst Time
Process No.	Arrival Time	Priority	CPU Burst	I/O Burst	CPU Burst
P1	0	2	1	5	3
P2	2	3	3	3	1
P3	3	1	2	3	1

If the CPU scheduling policy is Priority Scheduling, calculate the average waiting time and average turn around time. (Lower number means higher priority)

Solution-

The scheduling algorithm used is Priority Scheduling.

Gantt Chart-

Now, we know-

Turn Around time = Exit time – Arrival time
Waiting time = Turn Around time – Burst time

Process Id	Exit time	Turn Around time	Waiting time
P1	10	10 – 0 = 10	10 – (1+3) = 6
P2	15	15 – 2 = 13	13 – (3+1) = 9
P3	9	9 – 3 = 6	6 – (2+1) = 3

Now,

Average Turn Around time = (10 + 13 + 6) / 3 = 29 / 3 = 9.67 units
Average waiting time = (6 + 9 + 3) / 3 = 18 / 3 = 6 units

Next Article- Introduction to Process Synchronization

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

← Older Posts

Newer Posts →