A critical section is the part of a process where it accesses or modifies shared data or a shared resource.
When multiple processes execute concurrently, two or more processes may try to access the same shared resource at the same time. This can produce incorrect or inconsistent results.
┌──────────────────┐
│ Entry Section │
└────────┬─────────┘
↓
┌──────────────────┐
│ Critical Section │
│ │
│ Access Shared │
│ Data / Resource │
└────────┬─────────┘
↓
┌──────────────────┐
│ Exit Section │
└────────┬─────────┘
↓
┌──────────────────┐
│ Remainder │
│ Section │
└──────────────────┘
Entry Section:
A process requests permission to enter the critical section.
Critical Section:
The process accesses the shared resource.
Exit Section:
The process releases the critical section.
Remainder Section:
The process performs other operations that do not involve shared resources.
Suppose two processes, P1 and P2, want to increment the same variable:
Shared variable:
count = 5
Both execute:
count = count + 1
This operation actually involves multiple steps:
Read count
↓
Add 1
↓
Write count
Suppose both processes execute at the same time:
P1: Read count = 5 P2: Read count = 5 P1: Add 1 → 6 P2: Add 1 → 6 P1: Write 6 P2: Write 6
Expected result:
Actual result:
This is called a race condition.
> Race Condition = Result depends on the order/timing of process execution.
The critical-section problem aims to prevent such incorrect access to shared data.
A correct solution must satisfy three important requirements.
If one process is executing inside its critical section, no other process can enter its critical section.
P1 → CRITICAL SECTION
↑
P2 must wait
Example
If P1 is updating a shared bank account, P2 must wait until P1 finishes.
> Mutual Exclusion = ONE process at a time
If no process is currently inside the critical section, and some processes want to enter, the selection of the next process should not be unnecessarily delayed.
Critical Section = FREE
P1 wants to enter
P2 wants to enter
↓
One of them should be selected
A process outside its critical section should not unnecessarily prevent another process from entering.
> Progress = If it's free, someone should be allowed to enter.
A process requesting entry should not have to wait forever.
There must be a limit on the number of times other processes can enter before the waiting process gets its turn.
P1 waiting ↓ P2 enters ↓ P3 enters ↓ P4 enters ↓ P1 keeps waiting forever ❌
A correct solution prevents this situation.
> Bounded Waiting = Nobody waits forever
Operating systems provide different mechanisms to solve critical-section and synchronization problems.
Important mechanisms include:
- Mutex Locks
- Semaphores
- Monitors
- Hardware Atomic Instructions
A mutex (mutual exclusion) lock allows only one process/thread to access a critical section at a time.
It has two basic operations:
release()
Working
Process ↓ acquire lock ↓ Critical Section ↓ release lock
Example
acquire(lock); balance = balance + 100; release(lock);
If another process tries to acquire the locked mutex, it must wait.
> Mutex = Lock the door → Enter → Work → Unlock
A semaphore is a synchronization variable used to control access to shared resources.
Two main operations are:
signal()
Example
wait(S); Critical Section; signal(S);
If S indicates that a resource is unavailable, the process waits.
After finishing its work, the process performs signal() to indicate that the resource is available.
Binary Semaphore
It can have values:
It is commonly used for mutual exclusion.
Counting Semaphore
It can have values:
It is useful when there are multiple identical resources.
Example
If there are 3 printers:
Each process uses:
When a printer is released:
A monitor is a high-level synchronization mechanism that combines:
Procedures
Synchronization
Only one process can execute inside a monitor at a time.
Basic idea
MONITOR
┌─────────────────────┐
│ Shared Data │
│ │
│ Procedure 1 │
│ Procedure 2 │
│ Procedure 3 │
└─────────────────────┘
↑
Processes
Monitors provide mutual exclusion automatically, making synchronization easier for programmers.
Modern processors provide special atomic instructions that can be used to implement mutual exclusion.
Examples:
Compare-and-Swap
These operations are performed atomically, meaning they cannot be interrupted halfway.
Example: Test-and-Set
while (TestAndSet(lock))
; // wait
Critical Section
lock = false;
If the lock is already set, the process waits.
If it is free, the process acquires it.
| Mechanism | Main Purpose | Important Feature |
|---|---|---|
| Mutex | Mutual exclusion | Lock/Unlock |
| Binary Semaphore | Mutual exclusion | 0 or 1 |
| Counting Semaphore | Resource management | Multiple values |
| Monitor | High-level synchronization | One process inside |
| Hardware Instructions | Low-level synchronization | Atomic operations |
Critical Section:
Entry → Critical → Exit → Remainder
Requirements:
M → P → B
> Mutual Exclusion → Progress → Bounded Waiting
Synchronization:
> Mutex → Semaphore → Monitor → Hardware
A semaphore is a synchronization tool used by the operating system to control access to shared resources and coordinate concurrent processes.
A semaphore is generally represented by an integer variable:
Processes do not directly modify the semaphore. They use two atomic operations:
signal(S)
These operations are also commonly represented as:
V(S) → signal
A binary semaphore has only two possible values:
1 → Resource available
It is commonly used for mutual exclusion.
Example
Semaphore S = 1
P1 → wait(S)
Critical Section
signal(S)
P2 → wait(S)
Critical Section
signal(S)
Only one process can enter at a time.
A counting semaphore can have values greater than 1.
It is useful when there are multiple instances of a resource.
Example
Suppose there are 3 identical printers:
Three processes can obtain printers.
When all three printers are occupied:
The next process must wait.
The wait() operation is used when a process wants to acquire a resource.
Conceptually:
wait(S)
{
while (S <= 0)
wait;
S--;
}
The actual implementation uses atomic synchronization; the above is only a simplified representation.
Meaning
If the resource is available:
the process can proceed and the semaphore is decreased.
If the resource is unavailable:
the process waits.
> wait() = Ask for / Acquire resource
The signal() operation is used when a process releases a resource.
Conceptually:
signal(S)
{
S++;
}
A waiting process may then be allowed to proceed.
> signal() = Release / Notify
Suppose two processes access a shared variable.
Initialize:
Process P1
wait(S);
// Critical Section
shared_data++;
signal(S);
Process P2
wait(S);
// Critical Section
shared_data++;
signal(S);
Working
P1 → wait(S) → Critical Section → signal(S)
↓
P2 → wait(S) → Critical Section → signal(S)
If P1 is inside the critical section, P2 must wait.
Thus, the semaphore provides mutual exclusion.
Suppose a system has:
Initialize:
When a process wants a printer:
When it finishes:
Working
3 printers available P1 → wait → Printer 1 P2 → wait → Printer 2 P3 → wait → Printer 3 P4 → wait → Must wait P1 → signal → Printer released P4 → Gets printer
This allows the OS to control the number of processes using the resource.
Semaphores are used to solve several synchronization problems.
Ensures that only one process accesses shared data at a time.
wait(mutex); Critical Section signal(mutex);
Semaphores coordinate producers and consumers sharing a common buffer.
Typical semaphores:
full
mutex
Where:
empty → Number of empty buffer spaces
full → Number of filled buffer spaces
mutex → Protects the buffer
Semaphores can coordinate readers and writers accessing shared data.
They ensure that writers do not modify data while conflicting accesses are occurring.
Counting semaphores can control access to a fixed number of resources.
Example:
Database connections
Memory buffers
A semaphore operation should be atomic.
That means:
Otherwise, two processes could modify the semaphore simultaneously and create synchronization errors.
Semaphore = Traffic Police 🚦
Think of a semaphore as a traffic controller.
Resource available
↓
wait()
↓
Process enters
↓
Critical Section
↓
signal()
↓
Resource released
> wait() → Enter / Acquire
signal() → Exit / Release
A critical section is the portion of a process where it accesses or modifies shared data or resources.
When multiple processes execute concurrently, simultaneous access can result in a race condition.
Structure
┌─────────────────┐
│ Entry Section │
└────────┬────────┘
↓
┌─────────────────┐
│ Critical │
│ Section │
└────────┬────────┘
↓
┌─────────────────┐
│ Exit Section │
└────────┬────────┘
↓
┌─────────────────┐
│ Remainder │
│ Section │
└─────────────────┘
A race condition occurs when multiple processes access shared data simultaneously and the final result depends on execution timing.
Example
Two processes execute:
count = count + 1
Both may read 10 before either writes the result.
P1 reads 10 P2 reads 10 P1 writes 11 P2 writes 11
Expected:
Actual:
Therefore, access to count must be protected.
A correct solution must satisfy:
Mutual Exclusion
Only one process can execute its critical section at a time.
Progress
If the critical section is free, a process that wants to enter should not be unnecessarily delayed.
Bounded Waiting
A process should not wait indefinitely to enter its critical section.
> MPB = Mutual → Progress → Bounded
Peterson's Algorithm is a software-based solution for achieving mutual exclusion between two processes.
The two processes are usually:
P1
It uses two shared variables:
boolean flag[2]; int turn;
flag[i]
Indicates whether process Pi wants to enter the critical section.
means:
turn
Indicates whose turn it is to enter if both processes want to enter.
For process Pi:
flag[i] = true;
turn = j;
while (flag[j] && turn == j)
; // wait
// Critical Section
flag[i] = false;
// Remainder Section
Where:
j = other process
flag[0] = true;
turn = 1;
while (flag[1] && turn == 1)
;
// Critical Section
flag[0] = false;
flag[1] = true;
turn = 0;
while (flag[0] && turn == 0)
;
// Critical Section
flag[1] = false;
Suppose both P0 and P1 want to enter.
P0:
flag[0] = true turn = 1
P1:
flag[1] = true turn = 0
Both have indicated that they want to enter.
The turn variable determines which process gets priority.
One process enters the critical section while the other waits.
After the first process finishes:
The waiting process can enter.
Peterson's algorithm satisfies the three requirements:
Mutual Exclusion
Only one process can enter the critical section at a time.
Progress
If only one process wants to enter, it can enter without unnecessary delay.
Bounded Waiting
A process will not be postponed forever.
> Flag = "I want to enter"
Turn = "You go first"
Modern processors provide special atomic instructions to implement mutual exclusion.
Two important examples are:
Compare-and-Swap
These instructions perform their operation atomically.
Atomic means:
Another processor cannot interrupt the operation halfway through.
A simple Test-and-Set operation can be represented as:
boolean TestAndSet(boolean *target)
{
boolean old = *target;
*target = true;
return old;
}
A lock is initially:
Process:
while (TestAndSet(&lock))
;
// Critical Section
lock = false;
Suppose:
P1 executes:
It gets:
and sets:
Therefore, P1 enters the critical section.
If P2 tries while P1 is inside:
P2 keeps waiting.
After P1 finishes:
P2 can enter.
| Peterson's Algorithm | Hardware Solution |
|---|---|
| Software-based | Hardware-supported |
| Mainly designed for two processes | Can support synchronization in modern multiprocessor systems |
| Uses flag and turn | Uses atomic instructions |
| No special hardware instruction required | Requires processor atomic instruction support |
Peterson:
> FLAG + TURN
Flag: I want to enter.
Turn: You go first.
Hardware:
> Test → Set → Lock
A semaphore is a synchronization variable used to control access to shared resources and coordinate concurrent processes.
It is accessed using two atomic operations:
signal()
A binary semaphore has only:
It is commonly used to achieve mutual exclusion.
Example:
A counting semaphore can have values:
It is used when there are multiple instances of a resource.
Example:
A semaphore can be represented as:
typedef struct {
int value;
process waiting_queue;
} semaphore;
The semaphore has:
Value → Represents resource availability.
Waiting queue → Holds processes waiting for the resource.
The operations must be atomic.
Conceptually:
wait(S)
{
S--;
if (S < 0)
{
add process to waiting queue;
block();
}
}
The process is blocked if the required resource is unavailable.
> wait = Try to get resource
Conceptually:
signal(S)
{
S++;
if (S <= 0)
{
remove process from waiting queue;
wakeup(process);
}
}
It releases the resource and can wake a waiting process.
> signal = Give back resource
The Producer–Consumer problem, also called the Bounded Buffer problem, involves:
A Consumer
A Shared Buffer
Produces items and places them into the buffer.
Removes items from the buffer and consumes them.
Stores items temporarily.
Producer
│
│ produces
↓
┌──────────────────────┐
│ BOUNDED BUFFER │
│ [ ][ ][ ][ ][ ] │
└──────────────────────┘
│
│ consumes
↓
Consumer
Two important problems must be prevented.
Problem 1: Buffer Overflow
The producer must not add an item when the buffer is full.
Buffer = FULL
↓
Producer must WAIT
Problem 2: Buffer Underflow
The consumer must not remove an item when the buffer is empty.
Buffer = EMPTY
↓
Consumer must WAIT
There is also a third requirement:
Mutual Exclusion
Producer and consumer should not modify the shared buffer simultaneously.
Three semaphores are commonly used:
empty
full
mutex
Used for mutual exclusion.
Only one process can access the buffer at a time.
empty
Represents the number of empty slots.
If buffer size is N:
full
Represents the number of filled slots.
Initially:
The producer follows:
while (true)
{
item = produce_item();
wait(empty);
wait(mutex);
insert_item(item);
signal(mutex);
signal(full);
}
Explanation
wait(empty)
Checks whether an empty buffer slot exists.
If the buffer is full, producer waits.
wait(mutex)
Locks the buffer so that only the producer can modify it.
insert_item()
Adds the item to the buffer.
signal(mutex)
Releases the buffer.
signal(full)
Increases the number of filled slots and allows a waiting consumer to proceed.
The consumer follows:
while (true)
{
wait(full);
wait(mutex);
item = remove_item();
signal(mutex);
signal(empty);
consume_item(item);
}
Explanation
wait(full)
Checks whether at least one item is available.
If the buffer is empty, consumer waits.
wait(mutex)
Locks the buffer.
remove_item()
Removes an item.
signal(mutex)
Releases the buffer.
signal(empty)
Indicates that one empty buffer slot is now available.
PRODUCER
│
│
produce item
│
↓
wait(empty)
│
↓
wait(mutex)
│
↓
┌──────────────┐
│ BUFFER │
│ [ ][X][X][ ] │
└──────────────┘
│
↓
signal(mutex)
│
↓
signal(full)
│
↓
CONSUMER
The consumer performs the reverse operations:
Consumer ↓ wait(full) ↓ wait(mutex) ↓ Remove item ↓ signal(mutex) ↓ signal(empty)
Suppose the buffer has 5 slots.
Initially:
full = 0
mutex = 1
Producer adds one item:
full = 1
Consumer removes that item:
full = 0
If all five slots become occupied:
full = 5
The producer executes:
and must wait.
If the consumer removes an item:
full = 4
The producer can now continue.
| Semaphore | Initial Value | Purpose |
|---|---|---|
| mutex | 1 | Protects shared buffer |
| empty | N | Counts empty slots |
| full | 0 | Counts filled slots |
> EMPTY = Can Producer enter?
FULL = Can Consumer enter?
MUTEX = Who can touch the buffer?
For these four long questions, remember this structure:
PROCESS SYNCHRONIZATION
│
┌──────────────┴──────────────┐
↓ ↓
CRITICAL SECTION SEMAPHORES
│ │
├─ Race Condition ├─ wait()
│ ├─ signal()
├─ Mutual Exclusion ├─ Binary
├─ Progress └─ Counting
└─ Bounded Waiting
│
├──────────────┐
↓ ↓
PETERSON HARDWARE
│ │
FLAG + TURN Test-and-Set
│
↓
PRODUCER-CONSUMER
│
┌────────┼────────┐
↓ ↓ ↓
EMPTY FULL MUTEX
│ │ │
Producer Consumer Buffer
waits waits protection
A deadlock is a situation in which a group of processes are permanently blocked, because every process is waiting for a resource held by another process in the same group.
Simple example
Suppose there are two processes and two resources:
P1 has Printer → wants Scanner P2 has Scanner → wants Printer Now: P1 → waiting for Scanner → held by P2 P2 → waiting for Printer → held by P1
Neither process can continue.
P1
/ \
↓ ↑
Printer Scanner
↑ ↓
\ /
P2
This is a deadlock.
> Deadlock = Everyone is waiting, so nobody can move.
A computer system contains a number of resources that processes need in order to execute.
Examples of resources:
Printer
Scanner
Memory
Files
Database locks
I/O devices
A process normally follows this sequence:
Step 1: Request
The process requests a resource.
If the resource is available, the OS allocates it.
Step 2: Use
The process uses the resource.
Step 3: Release
The process finishes using the resource and releases it.
Basic resource usage model
Process
│
↓
Request
│
↓
Resource Available?
/ \
Yes No
↓ ↓
Allocate Wait
│
↓
Use
│
↓
Release
Resources can generally be considered as resource types.
For example:
R2 = Scanner
R3 = Disk
A resource type may have one or more instances.
Example
If a system has:
then two processes may use the two printers simultaneously.
For a resource with a single instance:
only one process can hold it at a time.
A Resource-Allocation Graph (RAG) is used to represent the relationship between:
Resources
Requests
Allocations
Symbols
Rectangle = Resource
Request edge
means:
Assignment edge
means:
Example
P1 ─────→ R2
↑ │
│ ↓
R1 ←────── P2
This represents a circular dependency.
For a system where each resource type has only one instance, a cycle in the resource-allocation graph indicates a deadlock.
When resource types have multiple instances, a cycle indicates a possibility of deadlock, but not necessarily a deadlock.
Deadlock can be characterized using the relationship between processes and resources.
A deadlock exists when there is a group of processes such that:
That resource is held by another process in the same group.
No process can proceed until another process releases its resource.
Example
P1 holds R1 and waits for R2 P2 holds R2 and waits for R3 P3 holds R3 and waits for R1
This creates:
This is a circular wait.
Because each process depends on another, none can proceed.
All four conditions must exist simultaneously for a deadlock to occur.
These are:
- Mutual Exclusion
- Hold and Wait
- No Preemption
- Circular Wait
Mutual Exclusion means that a resource can be used by only one process at a time.
If P1 is using a printer:
P2 cannot use the same printer at that exact time.
Example
P2 → Waiting
The resource is non-shareable.
> Mutual Exclusion = One resource, one user at a time.
A process is holding at least one resource while waiting to obtain another resource.
Example
P1 holds Printer P1 waits for Scanner So: P1 ├── Holds → Printer └── Wants → Scanner
This condition allows processes to maintain resources while waiting for additional resources.
> Hold one → Wait for another
No Preemption means a resource cannot be forcibly taken away from a process.
The process must release the resource voluntarily after completing its operation.
Example
If P1 has a printer:
the OS cannot simply take the printer away from P1 in the middle of its operation.
P1 must finish and release it.
> No Preemption = Resource cannot be forcibly taken.
A Circular Wait exists when a set of processes form a circular chain, where each process is waiting for a resource held by the next process.
Example
P1 waits for R2 R2 held by P2 P2 waits for R3 R3 held by P3 P3 waits for R1 R1 held by P1
Graphically:
This forms a cycle.
> Circular Wait = Everyone is waiting in a circle.
Consider:
Resources:
R2 = Scanner
Initial state:
P2 holds R2
Then:
P2 requests R1
Now:
P1 → waiting for R2 → held by P2 P2 → waiting for R1 → held by P1
Therefore:
Neither can proceed.
Why?
All four conditions are present:
| Condition | Example |
|---|---|
| Mutual Exclusion | Printer/Scanner used by one process |
| Hold and Wait | Each process holds one resource and waits for another |
| No Preemption | Resource cannot be forcibly taken |
| Circular Wait | P1 waits for P2, P2 waits for P1 |
Therefore, a deadlock occurs.
> M → H → N → C
Mutual Exclusion
Hold and Wait
No Preemption
Circular Wait
Easy sentence:
> “My Hands Never Cross.”
My → Mutual
Hands → Hold
Never → No Preemption
Cross → Circular
Deadlock prevention ensures that at least one of the four necessary conditions for deadlock is never allowed to occur.
The four conditions are:
Hold and Wait
No Preemption
Circular Wait
If even one condition is eliminated, deadlock cannot occur.
Mutual exclusion cannot always be eliminated because some resources are naturally non-shareable.
However, for resources that can be shared, sharing can prevent this condition.
Example
A read-only file can be accessed by multiple processes simultaneously.
P1 ──┐ P2 ──┼──→ Read-only File P3 ──┘
Since the resource is shareable, mutual exclusion is not required.
Limitation
Resources such as:
Certain locks
Exclusive devices
cannot normally be shared simultaneously.
Therefore, this method is not always practical.
One method is to require a process to request all required resources before it begins execution.
Example
Suppose P1 needs:
Instead of:
P1 → Waits for Scanner
it must request both:
If both are available, it gets them.
If not, P1 waits without holding any resource.
Advantage
This prevents:
Disadvantage
Resources may remain unused for a long time.
To prevent the No Preemption condition, resources may be taken away under certain circumstances.
Example
Suppose P1 holds:
and requests:
but R2 is unavailable.
The system can force P1 to release R1 and make P1 wait.
Later, when both resources are available, P1 can obtain them.
P1 holds R1
↓
Requests R2
↓
R2 unavailable
↓
Release R1
↓
Wait
↓
Get R1 + R2 together later
Preemption is practical only for resources whose state can be safely saved and restored.
A common technique is to impose a fixed ordering on resource types.
Suppose:
Processes must request resources only in increasing order.
R1 → R2 → R3
is allowed.
But:
is not allowed.
Example
If:
Scanner = R2
a process must always request:
and never:
> Fixed order → No circle → No deadlock
| Necessary Condition | Prevention Method |
|---|---|
| Mutual Exclusion | Share resources where possible |
| Hold and Wait | Request all resources together |
| No Preemption | Preempt/reclaim resources where possible |
| Circular Wait | Impose resource ordering |
Deadlock avoidance does not permanently eliminate any condition.
Instead, the OS examines each resource request and determines whether granting it will leave the system in a safe state.
Basic idea
Process requests resource
↓
OS checks request
↓
Will system remain safe?
/ \
Yes No
↓ ↓
Allocate Make process wait
A system is in a safe state if there is at least one order in which all processes can finish without causing deadlock.
This order is called a safe sequence.
Example
means:
then P3 can finish
then P2 can finish
Therefore, the system can safely complete all processes.
An unsafe state means the system cannot guarantee that all processes will finish without deadlock.
> Unsafe does not always mean deadlocked.
It means:
> The system has entered a state where deadlock may occur.
The most common deadlock avoidance technique is the Banker's Algorithm.
It checks whether granting a resource request maintains a safe state.
It uses:
Maximum
Allocation
Need
with:
| Prevention | Avoidance |
|---|---|
| Eliminates at least one necessary condition. | Allows conditions but carefully controls allocation. |
| Uses fixed restrictions. | Makes decisions dynamically. |
| Simpler conceptually. | Requires information about maximum resource needs. |
| Example: Resource ordering. | Example: Banker's Algorithm. |
> Prevention = Break the conditions
Avoidance = Check before allocating
Prevention
Force: R1 → R2 → R3 Circular Wait impossible
Avoidance
Request ↓ Safety check ↓ Safe? ── Yes → Allocate │ No ↓ Wait
A deadlock can occur only when all four conditions exist at the same time.
A resource can be assigned to only one process at a time.
Example
P2 must wait.
Prevention
Where possible, make resources shareable.
Example:
A process holds at least one resource while waiting for another.
Example
Holds → Printer
Waits → Scanner
Prevention
Require the process to request all required resources at once.
Request: Printer + Scanner
If both are unavailable, the process gets nothing and waits.
A resource cannot be forcibly taken from a process.
Example
P2 requests Printer
P2 cannot forcibly take it.
Prevention
Allow the system to preempt/reclaim resources when appropriate.
For example, if a process requests a resource that is unavailable, it may be required to release resources it currently holds.
A circular chain of waiting processes exists.
Example
Prevention
Impose a strict ordering:
Processes must request resources in increasing order.
Thus:
is allowed, while:
is prohibited.
If a resource can be safely shared, allow multiple processes to use it simultaneously.
Example
Read-only file
↓
P1 + P2 + P3
This eliminates the need for mutual exclusion for that resource.
A process must request all the resources it needs before beginning execution.
Example
P1 requires:
It requests both together.
One unavailable → Wait without holding any
This eliminates Hold and Wait.
If a process cannot obtain a requested resource, the OS can make it release resources it already holds, where the resource and application semantics permit.
Example
Holds R1
Requests R2
R2 unavailable
↓
Release R1
↓
Wait
This helps eliminate No Preemption.
Assign an order to resource types.
A process must request:
R2 before R3
This prevents circular waiting.
Consider:
P2 holds Scanner and requests Printer.
Without prevention:
P1 → Scanner → P2 P2 → Printer → P1
Deadlock occurs.
Using resource ordering:
Suppose:
Scanner = R2
Both processes must request:
P2 cannot request Scanner first and then Printer.
Therefore, the circular wait is broken.
| Condition | How to Prevent |
|---|---|
| Mutual Exclusion | Share resources where possible |
| Hold and Wait | Request all resources together |
| No Preemption | Allow resource preemption where possible |
| Circular Wait | Impose resource ordering |
> Share → All-at-once → Take-back → Order
The Banker's Algorithm is a deadlock avoidance algorithm.
It checks whether granting a process's resource request will keep the system in a safe state.
The basic idea is:
It is called the Banker's Algorithm because it works like a bank that gives loans only when it can still satisfy all customers safely.
For n processes and m resource types, the Banker's Algorithm uses:
Maximum
Allocation
Need
Available[j] represents the number of available instances of resource type j.
means the system currently has:
2 instances of R2
1 instance of R3
Max[i][j] represents the maximum number of resources of type j that process Pi may need.
Allocation[i][j] represents the number of resource instances of type j currently allocated to process Pi.
Need[i][j] represents how many more resources process Pi may still require.
The formula is:
Example
If:
Allocation = 3
then:
| Term | Meaning |
|---|---|
| Available | Currently free resources |
| Max | Maximum possible requirement |
| Allocation | Resources currently given |
| Need | Resources still required |
| Safe State | System can finish all processes safely |
| Unsafe State | System cannot guarantee safe completion |
The Safety Algorithm determines whether the current system state is safe.
Step 1: Initialize
Set:
Create a Finish array for all processes:
Step 2: Find a process
Find a process Pi such that:
and
Need[i] <= Work
This means the process's remaining requirements can be satisfied using currently available resources.
Step 3: Pretend it finishes
If such a process exists, assume it gets the needed resources, finishes, and releases all resources it held.
Update:
Then:
Step 4: Repeat
Repeat the process until:
No suitable process can be found.
Work = Available
For each process Pi:
Finish[i] = false
Find Pi such that:
Finish[i] == false
and Need[i] <= Work
If found:
Work = Work + Allocation[i]
Finish[i] = true
repeat
If all Finish[i] == true:
System is SAFE
Else:
System is UNSAFE
Suppose:
| Process | Need | Allocation |
|---|---|---|
| P1 | 1 | 2 |
| P2 | 2 | 1 |
| P3 | 4 | 3 |
Step 1
P1 needs 1:
So P1 can finish.
After P1 completes:
= 5
Step 2
P2 needs 2:
P2 can finish.
= 6
Step 3
P3 needs 4:
P3 can finish.
Therefore the safe sequence is:
The system is SAFE.
The Resource-Request Algorithm is used when a process makes a new resource request.
Suppose process Pi requests:
The following steps are performed.
Step 1: Check Request Against Need
If:
the process is asking for more than its declared maximum.
Therefore:
Step 2: Check Request Against Available
If:
the required resources are currently unavailable.
Therefore:
Step 3: Pretend to Allocate
If:
and
Request[i] <= Available
temporarily allocate the resources:
Allocation[i] = Allocation[i] + Request[i]
Need[i] = Need[i] − Request[i]
Step 4: Run Safety Algorithm
After the temporary allocation, the OS runs the Safety Algorithm.
Request is granted
If unsafe:
Allocation is rolled back
Process must wait
Request[i] = resource request of Pi
if Request[i] > Need[i]
Error
else if Request[i] > Available
Pi must wait
else
{
Available = Available - Request[i]
Allocation[i] =
Allocation[i] + Request[i]
Need[i] =
Need[i] - Request[i]
if Safety Algorithm says SAFE
Grant request
else
{
Roll back allocation
Pi must wait
}
}
Process requests resources
↓
Request ≤ Need ?
/ \
No Yes
↓ ↓
Error Request ≤ Available?
/ \
No Yes
↓ ↓
Wait Temporarily allocate
↓
Run Safety Algorithm
↓
Safe or Unsafe
/ \
Safe Unsafe
↓ ↓
Grant Roll back
request and wait
| Safety Algorithm | Resource-Request Algorithm |
|---|---|
| Checks whether current state is safe. | Handles a new resource request. |
| Uses Work and Finish. | Uses Request, Available, Need, Allocation. |
| Finds a safe sequence. | Decides whether a request can be granted. |
| Used after temporary allocation in request checking. | First checks the validity and availability of a request. |
The most important formula in Banker's Algorithm is:
> What I MAY need − What I ALREADY have = What I STILL need
RESOURCE REQUEST
│
↓
Request ≤ Need ?
/ \
No Yes
↓ ↓
Error Request ≤ Available?
/ \
No Yes
↓ ↓
Wait Temporary
Allocation
│
↓
Safety Algorithm
│
┌─────┴─────┐
↓ ↓
SAFE UNSAFE
↓ ↓
Grant Rollback
Request + Wait
0 Comments