Operating System IA Test-2
MODULE-3 IMPORTANT QUESTIONS
1. SCHEDULING CRITERIA
When choosing a CPU scheduling algorithm, we compare them using some common criteria. These
criteria tell us how good or efficient an algorithm is.
1. CPU Utilization
• Means how busy the CPU is.
• Range can be 0% to 100%.
• Goal → Keep CPU as busy as possible.
• In real systems:
o Light load → around 40%
o Heavy load → around 90%
• Higher CPU utilization = better performance.
2. Throughput
• Means number of processes completed per unit time.
• If CPU finishes more processes → throughput is high.
• For long jobs → maybe 1 process/hour.
• For short jobs → maybe 10 processes/second.
• Higher throughput = system works faster.
3. Turnaround Time
• Total time taken to finish a process from submission to completion.
• Includes:
o Time waiting to enter memory
o Time in ready queue
o CPU execution time
o I/O time
• Lower turnaround time = better.
Formula (conceptual):
Turnaround Time = Completion Time – Arrival Time
Operating System IA Test-2
4. Waiting Time
• Time a process spends only in the ready queue waiting for CPU.
• Scheduling affects this time because it decides the order of execution.
• Shorter waiting time = better scheduling.
Formula:
Waiting Time = Turnaround Time – CPU Burst Time
5. Response Time
• Used mainly in interactive systems (like user applications).
• Means time from submitting a request to getting the first response.
• Does not mean full output, only the first reply or reaction.
• Lower response time → system feels faster to user.
Short Summary (best for last paragraph in exam)
• CPU Utilization: Keep CPU busy.
• Throughput: Finish more processes per time.
• Turnaround Time: Total time to finish a process.
• Waiting Time: Time spent waiting in the ready queue.
• Response Time: Time to get the first response in interactive systems.
Here is a very simple, exam-friendly explanation of Critical Section Problem with neat points. Easy to
write and remember!
2. CRITICAL SECTION PROBLEM
What is a Critical Section?
• A critical section is a part of the program where a process accesses shared data (like common
variables, files, tables).
• Only one process should execute its critical section at a time → to avoid data inconsistency.
System With n Processes
• Suppose the system has n processes: P₀, P₁, …, Pₙ₋₁.
• Each process has:
Operating System IA Test-2
o Entry Section → asks permission to enter critical section
o Critical Section → shared resource is used
o Exit Section → leaves critical section
o Remainder Section → rest of the program
Why We Need a Critical Section Protocol?
• To make sure no two processes enter the critical section at the same time.
• To avoid race conditions, inconsistent data, and unexpected results.
• The goal is to create a protocol that safely allows processes to cooperate.
Three Requirements of a Good Critical Section Solution
Memorize these three — they are always asked in exams!
1. Mutual Exclusion
• At any time, only one process can be in its critical section.
• If Pi is inside its critical section → no other process should enter.
• This avoids conflicts and keeps shared data safe.
In simple words:
No two processes can be inside the critical section at the same time.
2. Progress
• If no process is currently inside the critical section:
o Only the processes that WANT to enter and are not in remainder section should take
part in decision-making.
• The decision of "who enters next" must happen within a finite time.
• There should be no unnecessary waiting.
In simple words:
If the critical section is free, someone who wants to enter must be allowed without delay.
3. Bounded Waiting
• There must be a limit on how long a process waits.
Operating System IA Test-2
• Once a process requests to enter the critical section, other processes should not repeatedly jump
ahead.
• No process should wait forever → avoids starvation.
In simple words:
A process will not wait infinitely; it must get its turn within a fixed limit.
Short Summary
• Critical section = part where shared data is used.
• Only one process should be allowed at a time.
• A good solution must satisfy:
1. Mutual Exclusion – Only one process in CS.
2. Progress – If CS is empty, someone waiting must enter soon.
3. Bounded Waiting – Every process gets a turn; no infinite waiting.
Below is a very simple, exam-friendly, clean explanation of Peterson’s Solution — perfect for 5-mark
or 10-mark answers. I’ve rewritten everything in clear points while keeping the meaning accurate.
3. PETERSON’S SOLUTION
Introduction
• Peterson’s solution is a classic software-based algorithm for solving the critical section
problem.
• It is a two-process solution (works only for P₀ and P₁).
• Although modern CPUs may not guarantee correctness due to hardware optimizations, it remains
important because:
o It clearly demonstrates mutual exclusion, progress, and bounded waiting.
o It helps understand the logic behind process synchronization.
Shared Data Used
Peterson’s solution uses:
boolean flag[2];
int turn;
1. flag[i]
Operating System IA Test-2
• flag[i] = true → Process Pi wants to enter the critical section.
• flag[i] = false → Pi is not interested.
2. turn
• Indicates whose turn it is to enter the critical section.
• Example:
If turn = i, then Pi gets preference.
Algorithm Working (Process Pi)
Entry Section
1. Pi sets flag[i] = true → it wants to enter CS.
2. Pi sets turn = j → gives chance to the other process.
3. Pi waits in the loop:
while (flag[j] == true && turn == j);
If the other process wants the CS and it is its turn, Pi waits.
Critical Section (CS)
• When the above condition is false → Pi enters the critical section safely.
Exit Section
• Pi sets flag[i] = false → it leaves CS.
• Why It Works? (3 Conditions Proof)
1. Mutual Exclusion
To enter critical section, Pi requires:
(flag[j] == false) OR (turn == i)
• If both processes want to enter, both set flag[] = true.
• But turn can hold only one value (0 or 1, not both).
• So only one process will find turn == i true, and the other must wait.
• Therefore, both cannot be inside the critical section together.
✔ Mutual Exclusion is preserved.
2. Progress
A process Pi can be forced to wait only in the case:
flag[j] == true AND turn == j
Operating System IA Test-2
• If process Pj does not want to enter CS → flag[j] = false
→ Pi immediately enters CS.
• If both want to enter, the decision depends only on turn.
• This decision happens in finite time, not infinite.
✔ Progress is satisfied.
3. Bounded Waiting
• Once Pi sets flag[i] = true, it will not wait forever.
• Even if Pj enters CS first:
o When Pj exits, it sets flag[j] = false, allowing Pi to enter.
• If Pj again wants CS, it must set turn = i, giving Pi preference next.
✔ Pi waits for at most one turn of Pj.
✔ Bounded waiting is satisfied.
Short Summary
• Peterson’s solution is a software algorithm for two processes.
• Uses two shared variables: flag[] and turn.
• Ensures:
o Mutual Exclusion → only one process in CS at a time
o Progress → decision of who enters CS happens without delay
o Bounded Waiting → no process waits forever
• Provides a clear understanding of concurrency control, even if not always valid on modern CPUs.
Here is a simple, clean, exam-friendly answer for:
4. Define Deadlock & Necessary Conditions
Definition of Deadlock
A deadlock is a situation in a system where two or more processes are permanently blocked, each
waiting for a resource that is held by another process in the set.
As a result, none of the processes can continue execution.
Simple meaning:
Processes wait forever because each one is waiting for the other to release resources.
Necessary Conditions for Deadlock
Operating System IA Test-2
(These four conditions must hold simultaneously for deadlock to occur. If any one is removed, deadlock
is prevented.)
1. Mutual Exclusion
• At least one resource must be held in a non-shareable mode.
• Only one process can use the resource at a time.
• If another process requests it → it must wait.
2. Hold and Wait
• A process is holding at least one resource and is waiting for additional resources.
• It does not release the resource it already holds while waiting.
3. No Preemption
• Resources cannot be forcibly taken from a process.
• A resource can be released only voluntarily by the process holding it.
4. Circular Wait
• A set of processes exists such that:
P₁ waits for a resource held by P₂
P₂ waits for a resource held by P₃
… and so on
Pₙ waits for a resource held by P₁
This forms a circular chain of waiting.
Short Summary
• Deadlock → processes wait forever for resources.
• Required conditions:
1. Mutual Exclusion
2. Hold and Wait
3. No Preemption
4. Circular Wait
5. Methods to Recover from Deadlocks
Deadlock recovery means handling a system after a deadlock has already occurred.
There are two major approaches:
Operating System IA Test-2
1. Process termination
2. Resource preemption
Each method is explained below.
1. Process Termination
In this method, the system chooses one or more deadlocked processes and terminates them to break the
circular wait.
There are two ways to do this:
a) Abort All Deadlocked Processes
• The simplest method.
• All processes involved in the deadlock are terminated.
• All resources are released at once.
• System becomes free from deadlock immediately.
Disadvantages:
• Causes loss of a large amount of work.
• Not suitable for long-running or important processes.
b) Abort Processes One by One
• Terminate one process at a time until the deadlock cycle is broken.
• System carefully selects which process to kill based on factors like:
o Process priority
o Amount of work already done
o Future CPU/resource needs
o Number of resources held
o How many more resources the process may need
o Whether the process is interactive or batch
• Causes less work loss, but requires repeated checks for deadlock.
Disadvantage:
• Slower method because deadlock detection must be repeated after each termination.
2. Resource Preemption
Instead of killing processes, the system can take resources away from some processes and give them to
others to break the deadlock.
Operating System IA Test-2
Key issues in preemption:
a) Selecting a Victim
• Choose which resource or which process will be preempted.
• Victim selection is usually based on minimizing:
o Cost of rollback
o Amount of work lost
o System overhead
b) Rollback
• The selected process is rolled back to a safe state.
• The process may need to be rolled back partially or fully.
• After rollback, the resource can be allocated to another process.
c) Starvation Problem
• A process chosen repeatedly as a victim may never finish.
• To avoid starvation:
o The system tracks the number of rollbacks
o A process becomes "more important" after each rollback
o Eventually it will be allowed to complete
Summary
Deadlock recovery can be done by:
1. Process Termination
o Abort all deadlocked processes
o Abort one process at a time
2. Resource Preemption
o Select a victim
o Rollback the victim
o Prevent starvation
All these methods aim to break the circular wait and return the system to a consistent state.
Operating System IA Test-2
6. Semaphore?
A semaphore is a synchronization tool used in operating systems to manage concurrent processes and
avoid problems like race conditions.
It is an integer variable that is accessed only through two atomic operations:
1. wait(S) or P(S)
• Decreases the semaphore value.
• If the value becomes negative → the process is blocked.
2. signal(S) or V(S)
• Increases the semaphore value.
• If some process is waiting → one blocked process will be awakened.
Use of semaphores:
✔ To achieve mutual exclusion
✔ To avoid deadlocks
✔ To coordinate access to shared resources
Dining Philosopher Problem (Definition)
• Five philosophers sit around a circular table.
• Each philosopher alternates between thinking and eating.
• There is one chopstick between each pair of philosophers.
• To eat, a philosopher needs two chopsticks (left and right).
• Problem: If all philosophers pick one chopstick at the same time → deadlock.
Goal:
Design a solution using semaphores so that no deadlock happens and philosophers eat without conflict.
Semaphore-Based Solution
We use:
• A binary semaphore for each chopstick
• semaphore chopstick[5] = {1,1,1,1,1};
• Each semaphore represents a chopstick (1 = free, 0 = in use)
Algorithm for Philosopher i
do {
think();
Operating System IA Test-2
wait(chopstick[i]); // pick left chopstick
wait(chopstick[(i+1) % 5]); // pick right chopstick
eat();
signal(chopstick[i]); // put left chopstick
signal(chopstick[(i+1) % 5]); // put right chopstick
} while(true);
How This Works
• Only one philosopher can hold a chopstick at a time → ensured by semaphore’s mutual exclusion.
• A philosopher must successfully perform two wait() operations before eating.
• After eating, chopsticks are released using signal() operations, allowing others to use them.
Deadlock Prevention (Common Fix)
To prevent deadlock, one common rule is:
Allow only 4 philosophers to try picking chopsticks at once
(using an additional semaphore "room" initialized to 4):
semaphore room = 4;
wait(room); // allow only 4 philosophers
wait(chopstick[i]);
wait(chopstick[(i+1)%5]);
eat();
signal(chopstick[i]);
signal(chopstick[(i+1)%5]);
signal(room);
This prevents all 5 from grabbing the first chopstick together → deadlock is avoided.
Short Summary
• Semaphore = integer variable used for process synchronization, accessed only through wait() and
signal().
• Dining Philosopher Problem = philosophers need two chopsticks to eat; naive implementation
leads to deadlock.
Operating System IA Test-2
• Semaphore Solution:
o Use one semaphore per chopstick.
o Philosophers pick left and right chopsticks using wait().
o Release them with signal() after eating.
o Optionally use a room semaphore to avoid deadlock completely.
7. Resource Allocation Graph
What is a Resource Allocation Graph?
A Resource Allocation Graph (RAG) is a directed graph used to represent processes, resources, and
the relationships between them in an operating system.
It helps visualize:
• Which processes are holding resources
• Which processes are waiting for resources
• Whether a deadlock (deadly embrace) exists
Graph Components
• Processes → shown as circles (P₁, P₂, P₃...)
• Resources → shown as squares (R₁, R₂, R₃...)
• Request edge (process → resource)
o P₁ → R₁ : P₁ is requesting resource R₁
• Assignment edge (resource → process)
o R₁ → P₁ : resource R₁ is allocated to P₁
Why RAG is Useful?
• It visually shows who is waiting for what.
• Helps detect cycles in the graph.
• A cycle in the graph indicates the possibility of deadlock.
• For single-instance resources → a cycle means deadlock for sure.
• For multi-instance resources → cycle means deadlock may occur.
Example: Deadly Embrace (Deadlock) Using RAG
Consider two processes and two resources:
Operating System IA Test-2
• Processes: P₁, P₂
• Resources: R₁, R₂
Current Situation:
1. P₁ holds R₁ and requests R₂
o Allocation: R₁ → P₁
o Request: P₁ → R₂
2. P₂ holds R₂ and requests R₁
o Allocation: R₂ → P₂
o Request: P₂ → R₁
Graph Representation
• R₁ → P₁ (P₁ is holding R₁)
• P₁ → R₂ (P₁ is waiting for R₂)
• R₂ → P₂ (P₂ is holding R₂)
• P₂ → R₁ (P₂ is waiting for R₁)
This forms a cycle:
P₁ → R₂ → P₂ → R₁ → P₁
Why is this a Deadly Embrace?
• P₁ will not release R₁ until it gets R₂
• P₂ will not release R₂ until it gets R₁
• Neither can proceed → both are blocked forever
This situation is called a deadly embrace (deadlock).
How RAG Helps
• The moment a cycle appears in the graph, we can immediately detect:
o Processes are holding some resources
o Those same processes are waiting for resources held by others
• This visual representation makes it easy to identify deadlock conditions.
Summary
• Resource Allocation Graph is a directed graph showing relationships between processes and
resources.
Operating System IA Test-2
• It uses request edges and assignment edges to represent current system state.
• A cycle in the graph indicates a deadly embrace (deadlock).
• Example:
o P₁ holds R₁ and waits for R₂
o P₂ holds R₂ and waits for R₁
o Cycle forms → deadlock occurs
8. MONITORS – Syntax and Schematic View
What is a Monitor?
A monitor is a high-level synchronization construct used in operating systems and programming
languages.
It provides a safe and structured way to allow only one process or thread to execute inside the
monitor at a time.
✔ Prevents race conditions
✔ Supports mutual exclusion automatically
✔ Uses condition variables for waiting and signaling
Syntax of a Monitor
A monitor typically consists of:
• Shared variables
• Procedures (functions)
• Initialization code
• Condition variables (for waiting and signaling)
General Syntax
monitor MonitorName {
// shared data / variables
shared variables;
// condition variables
condition x, y;
// procedures for synchronization
Operating System IA Test-2
procedure proc1(...) {
...
procedure proc2(...) {
...
// optional initialization
initialization_code {
...
Important Features of Monitor Syntax
1. Only one process can execute a monitor procedure at a time
o Mutual exclusion is automatically provided.
2. Condition variables
Used for waiting inside the monitor:
o [Link]() → process waits
o [Link]() → wakes one waiting process
3. Monitor procedures
These procedures define how resources are accessed safely.
Schematic view:
• The monitor encloses both data and procedures.
• Only one process can be inside the monitor block at once.
• Condition variables x, y act as waiting areas inside the monitor.
Why Monitors Are Useful?
• They make synchronization easier than semaphores.
• Avoids programmer errors like forgetting to signal or mismatched waits.
• Provide safe access to shared resources using structured programming.
Short Summary
• A monitor is a synchronization tool that ensures only one process executes inside it at a time.
Operating System IA Test-2
• Contains shared data, procedures, condition variables, and initialization.
• Condition variables support:
o wait()
o signal()
• Schematic view shows a protected region containing data + procedures.
9. Readers–Writers Problem Using Semaphores
Introduction:
The Readers–Writers Problem is a classic synchronization problem that deals with multiple processes
reading and writing shared data.
The rules are:
1. Multiple readers can read simultaneously. ✔
2. Only one writer can write at a time. ✔
3. When a writer is writing, no reader or writer should access the shared data.
To ensure this, semaphores are used for proper synchronization.
Semaphores Used
We use three semaphores:
1. mutex
o Protects the shared counter readcount
o Ensures mutual exclusion while updating the counter
2. wrt
o Ensures writers get exclusive access
o When locked, no readers or other writers can enter
3. readcount (integer)
o Counts how many readers are currently reading
Initialization
semaphore mutex = 1;
semaphore wrt = 1;
Operating System IA Test-2
int readcount = 0;
Reader Process (Using Semaphores)
while (true) {
wait(mutex); // enter critical section to update readcount
readcount++;
if (readcount == 1)
wait(wrt); // first reader locks writers out
signal(mutex); // exit CS
// ----- Reading section -----
read();
// ---------------------------
wait(mutex); // update readcount after reading
readcount--;
if (readcount == 0)
signal(wrt); // last reader releases writers
signal(mutex);
Writer Process (Using Semaphores)
while (true) {
wait(wrt); // writer gets exclusive access
// ----- Writing section -----
write();
// ----------------------------
signal(wrt); // release access for others
Explanation of Working
Operating System IA Test-2
✔ When Readers Enter
• The first reader executes wait(wrt), blocking any writer.
• All additional readers simply increase readcount and enter simultaneously.
• This allows multiple readers at the same time.
✔ When Writers Enter
• Writer uses wait(wrt), ensuring exclusive access.
• Since wrt was locked by the first reader, writers must wait until all readers finish.
✔ When Readers Exit
• They decrement readcount.
• The last reader executes signal(wrt), allowing writers to proceed.
This ensures fairness and correctness.
Why Semaphores Solve the Problem
• mutex ensures safe modification of readcount.
• wrt ensures exclusive access for writers.
• Readers can read in parallel; writers get complete exclusivity.
✔ No race conditions
✔ No data corruption
✔ Proper synchronization between readers and writers
Short Summary
• Readers–Writers Problem allows multiple readers but only one writer at a time.
• Semaphores used:
1. mutex → protects readcount
2. wrt → ensures writers' exclusive access
3. readcount → number of active readers
• First reader blocks writers; last reader releases them.
• Writers block everyone until done.