UNIT-III

Deadlock and Indefinite Postponement

1. Basic Concepts
 Resource: Any entity a process needs to complete execution.
Examples: CPU cycles, memory, files, printers, I/O devices.
 Deadlock:
A situation in which a set of processes are blocked because each process is holding a
resource and waiting for another resource held by some other process in the set.
 Indefinite Postponement (Starvation):
A process waits for a resource for an unbounded (infinite) period of time because higher-
priority processes continuously preempt it.

2. Four Necessary Conditions for Deadlock (Coffman’s conditions)

Deadlock can occur only if all these holds simultaneously:
1. Mutual Exclusion
o At least one resource must be held in a non-sharable mode.

o Only one process at a time can use the resource.

2. Hold and Wait

o A process is holding at least one resource and is waiting to acquire additional
resources held by other processes.
3. No Preemption
o A resource cannot be forcibly taken away from a process. It must be released
voluntarily.
4. Circular Wait
o A closed chain of processes exists, where each process holds at least one resource
and waits for a resource held by the next process in the chain.
3. Deadlock Handling Methods
There are three main approaches:
(A) Deadlock Prevention
 Goal: Ensure that at least one of the four necessary conditions never holds.
  Methods:
o Mutual Exclusion: Not possible for all resources (e.g., printers).

o Hold and Wait: Require processes to request all resources at once (can lead to
low resource utilization).
o No Preemption: If a process cannot get all resources, release those it already
holds.
o Circular Wait: Impose a linear ordering of resource types and require processes
to request resources in increasing order.

(B) Deadlock Avoidance

 Goal: Make sure the system never enters an unsafe state.
 Key Concept: Safe State
o A state where there exists at least one sequence of process execution such that
each process can finish without leading to deadlock.
Banker’s Algorithm (Dijkstra’s Algorithm)
 Works like a bank loaning money (resources).
 A process must declare maximum resource needs in advance.
 The system checks whether granting a request leads to a safe state:
o If yes → request granted.

o If no → request delayed.

Steps:
1. Available = vector of available resources.
2. Max = maximum demand of each process.
3. Allocation = resources currently allocated.
4. Need = Max – Allocation.
5. Algorithm checks if resources can be allocated in some safe order.
Key Data Structures
For n processes and m resource types:
 1. Available[ m ]
o Vector showing how many resources of each type are available.

2. Max[ n ][ m ]
o Maximum demand of each process for each resource type.

3. Allocation[ n ][ m ]
o Resources currently allocated to each process.

4. Need[ n ][ m ]
o Resources still required by process =

Need[i][j]=Max[i][j]−Allocation[i][j]Need[i][j] = Max[i][j] - Allocation[i][j]Need[i]

[j]=Max[i][j]−Allocation[i][j]
Safety Algorithm (Check if state is safe)
Steps:
1. Work = Available (copy of available resources).
2. Finish[i] = false (for all processes).
3. Find a process Pᵢ such that:
o Finish[i] == false

o Need[i] ≤ Work

4. If found:
o Work = Work + Allocation[i] (simulate process completion).

o Finish[i] = true.

o Repeat Step 3.

5. If no such process exists and all Finish[i] == true → Safe State.

6. If some Finish[i] == false → Unsafe (possible deadlock).
Resource-Request Algorithm (When a process requests resources)
1. If Request[i] ≤ Need[i] → valid request. Otherwise → Error.
2. If Request[i] ≤ Available → resources are free, else process must wait.
3. Pretend to allocate:
 o Available = Available – Request[i]

o Allocation[i] = Allocation[i] + Request[i]

o Need[i] = Need[i] – Request[i]

4. Run Safety Algorithm:

o If safe → grant request.

o If unsafe → rollback allocation, make process wait.

Example
 Processes: P1, P2, P3
 Resources: A, B, C (3 types)
Available = [3, 3, 2]

Process Max (A,B,C) Allocation (A,B,C)

P1 7, 5, 3 0, 1, 0

P2 3, 2, 2 2, 0, 0

P3 9, 0, 2 3, 0, 2

Step 1: Calculate Need = Max – Allocation

Process Need (A,B,C)

P1 7, 4, 3

P2 1, 2, 2

P3 6, 0, 0

(C) Deadlock Detection and Recovery

 Detection:
Wait-for Graph (for single instances of each resource).
Resource Allocation Graph + Algorithms (for multiple instances).
 Recovery:
o Process Termination: Kill one or more processes until deadlock breaks.

o Resource Preemption: Take resources from processes (may cause starvation).

Deadlock Detection and Recovery
When deadlocks are not prevented or avoided, the system must detect them and then recover.
1. Deadlock Detection
 The operating system must have a method to check if a deadlock has occurred.
 Detection depends on resource type:
(A) Single Instance of Each Resource Type
 Use a Wait-For Graph (WFG):
o Processes = nodes.

o An edge Pᵢ → Pⱼ means process Pᵢ is waiting for a resource held by Pⱼ.

o Deadlock exists if and only if there is a cycle in the graph.

(B) Multiple Instances of Each Resource Type

 Use an algorithm similar to Banker’s safety check:
Data Structures:
 Available[m] → number of available instances of each resource.
 Allocation[n][m] → how many resources of each type are allocated to each process.
 Request[n][m] → current requests of each process.
Detection Algorithm (Steps):
1. Work = Available.
2. Finish[i] = false if Allocation[i] ≠ 0, else true.
3. Find a process i such that:
o Finish[i] == false, and

o Request[i] ≤ Work.

4. If found:
o Work = Work + Allocation[i].

o Finish[i] = true.

o Repeat step 3.
 5. If no such i exists → stop.
6. If some Finish[i] == false → those processes are in deadlock.

2. Deadlock Recovery
Once deadlock is detected, the system must break it. Methods:
(A) Process Termination
1. Kill all deadlocked processes
o Simple but costly (wasted computation).

2. Kill processes one by one until deadlock breaks

o Choose victim based on:

 Priority
 How much work is done/remaining
 Resources held
 Process importance

(B) Resource Preemption

 Take resources away from processes and give them to others until deadlock breaks.
 Issues:
o Selecting victim: Which process loses its resources?

o Rollback: Process may need to restart after losing resources.

o Starvation: Same process may always be chosen as victim (solution → use

aging).

3. Example
Suppose 3 processes (P1, P2, P3) and 2 resources (R1, R2).
 P1 holds R1 and waits for R2.
 P2 holds R2 and waits for R1.
  P3 is independent.
Wait-For Graph:
 P1 → P2
 P2 → P1

 Cycle detected ⇒ Deadlock between P1 and P2.

Recovery:
 Option 1: Kill P1 (free R1, then P2 continues).
 Option 2: Preempt R1 from P1 and give it to P2.
4. Indefinite Postponement (Starvation)
 A process may be delayed indefinitely if scheduling is unfair.
 Example:
o In priority scheduling, low-priority processes may never execute.

 Solutions:
o Use aging technique (gradually increase priority of waiting processes).

o Ensure fair resource allocation policies.

UNIT-IV
1. Scheduling Levels
Scheduling occurs at three levels:
1. Long-term Scheduling (Job Scheduling)
o Decides which jobs enter the system for processing.

o Controls degree of multi programming (number of processes in memory).

o Example: Batch processing systems.

2. Medium-term Scheduling
o Temporarily suspends or resumes processes (swapping).

o Improves CPU utilization and balances workload.

3. Short-term Scheduling (CPU Scheduling)

 o Decides which ready process gets the CPU next.

o Executed frequently (in milliseconds).

2. Scheduling Objectives
1. CPU Utilization
 Definition: Percentage of time the CPU is actively executing processes (not idle).
 Goal: Keep CPU as busy as possible.
 Objective:
o Maximize CPU utilization (typical values: 40% for lightly loaded, up to 90%
for heavily loaded).
 Example: If CPU executes 90 out of 100 time units → Utilization = 90%.

2. Throughput
 Definition: Number of processes completed per unit time.
 Goal: Maximize system productivity.
 Example:
o If 10 processes finish in 100 seconds → throughput = 0.1 process/sec.

 Objective: Higher throughput = more jobs done in less time.

3. Turnaround Time
 Definition: Time interval between process submission and completion.
Turnaround Time=Completion Time−Arrival TimeTurnaround\ Time = Completion\ Time
- Arrival\ TimeTurnaround Time=Completion Time−Arrival Time
 Includes waiting time + execution time + I/O time.
 Objective: Minimize average turnaround time.
 Example: A job submitted at 0s, finished at 20s → turnaround = 20s.

4. Waiting Time
  Definition: Time a process spends waiting in the ready queue.
Waiting Time=Turnaround Time−Burst TimeWaiting\ Time = Turnaround\ Time - Burst\
TimeWaiting Time=Turnaround Time−Burst Time
 Objective: Minimize average waiting time for all processes.
 Example: If a job runs 10s but turnaround is 25s → waiting = 15s.

5. Response Time
 Definition: Time from process submission until it produces first response (not
completion).
 Important for interactive systems (e.g., typing in a terminal, clicking a button).
 Objective: Minimize response time → improve user experience.
 Example: If user submits a query at 0s and first output comes at 3s → response = 3s.

6. Fairness
 Definition: Equal and just allocation of CPU among processes/users.
 Prevents starvation (indefinite postponement of some jobs).
 Objective: Ensure all processes get a fair share of CPU time.
 Example: Priority scheduling without aging may cause starvation → unfair.

7. Predictability
 Users should be able to predict system performance (how long their jobs will take).
 Objective: Reduce variability in waiting/turnaround times.

8. Deadline Meeting (for Real-Time Systems)

 In real-time systems, processes often have deadlines.
 Objective: Ensure jobs finish before their deadlines.
 Example: Air traffic control or medical monitoring → missing deadlines can cause
failure.
9. Balanced Resource Utilization
 Not just CPU, but also I/O devices must be efficiently used.
 Objective: Avoid CPU-bound jobs hogging CPU while I/O devices remain idle.

10. Minimize Context Switching (Secondary Objective)

 Frequent preemptions cause overhead due to context switching.
 Objective: Balance responsiveness with minimal switching overhead.

3. Scheduling Criteria
1. CPU Utilization
 Definition: Fraction of time CPU is actively executing processes.
 Formula:
CPU Utilization=CPU Busy TimeTotal Time×100%CPU\ Utilization = \frac{CPU\ Busy\ Time}
{Total\ Time} \times 100\%CPU Utilization=Total TimeCPU Busy Time×100%
 Goal: Maximize utilization. (Typical values: 40–90%).
 Example: If CPU works 80 out of 100 seconds → Utilization = 80%.
2. Throughput
 Definition: Number of processes completed per unit time.
 Goal: Maximize throughput (more jobs done in less time).
 Example:
o 10 jobs finished in 50s → Throughput = 0.2 jobs/sec.

3. Turnaround Time
 Definition: Total time taken from submission of process to its completion.
 Formula:
Turnaround Time=Completion Time−Arrival TimeTurnaround\ Time = Completion\ Time -
Arrival\ TimeTurnaround Time=Completion Time−Arrival Time
 Goal: Minimize average turnaround time.
  Example: Job submitted at 0s, finished at 25s → Turnaround = 25s.
4. Waiting Time
 Definition: Time spent waiting in the ready queue (not executing).
 Formula:
Waiting Time=Turnaround Time−Burst TimeWaiting\ Time = Turnaround\ Time - Burst\
TimeWaiting Time=Turnaround Time−Burst Time
 Goal: Minimize waiting time.
 Example: Burst = 10s, Turnaround = 30s → Waiting = 20s.
5. Response Time
 Definition: Time between submission of a process and the first response/output.
 Important in interactive systems.
 Goal: Minimize response time for better user experience.
 Example: Query submitted at 0s, first reply at 2s → Response Time = 2s.
6. Fairness
 Definition: Equal CPU time distribution among processes/users.
 Prevents starvation (indefinite waiting).
 Goal: Fair allocation of resources.
 Example: If only high-priority jobs run, low-priority ones may starve → unfair.
7. Predictability (Consistency)
 Definition: Predictable performance for similar jobs.
 Goal: Reduce variation in waiting and turnaround times.
 Example: If two jobs of same length take very different times, scheduling is
unpredictable.
8. Deadlines (Real-Time Criteria)
 Definition: Meeting process deadlines in real-time systems.
 Goal: Ensure all time-critical tasks finish before their deadlines.
 Example: Air traffic control must update every 1s → cannot miss deadline.
9. Resource Utilization (System-Oriented Criteria)
  Not only CPU, but also I/O devices, memory should be kept busy.
 Goal: Balance CPU-bound and I/O-bound jobs to avoid bottlenecks.
4. Preemptive vs Non-Preemptive Scheduling
1. Preemptive Scheduling
 Definition: The CPU can be taken away (preempted) from a running process before it
finishes.
 How it works:
o If a higher-priority or more urgent process arrives, the OS suspends the current
process and allocates CPU to the new one.
o Requires hardware support (timer interrupts, context switching).

 Advantages:
o Better for real-time and interactive systems.

o Improves response time for short or urgent jobs.

o Prevents CPU monopolization by long processes.

 Disadvantages:
o More overhead due to context switching.

o Requires complicated OS design.

o Can lead to starvation of lower-priority processes.

 Examples of Preemptive Algorithms:

o Round Robin (RR)

o Shortest Remaining Time (SRT)

o Priority Scheduling (preemptive)

o Multilevel Feedback Queue (MLFQ)

2. Non-Preemptive Scheduling
 Definition: Once a process is allocated the CPU, it cannot be preempted. It continues
until:
o It finishes execution, OR
 o It voluntarily gives up CPU (e.g., waiting for I/O).

 How it works:
o CPU is never forcibly taken away from a process.

o Simpler implementation.

 Advantages:
o Easier to implement.

o Less context switching (low overhead).

o More predictable for batch jobs.

 Disadvantages:
o Poor response time for short/interactive jobs.

o Long jobs can cause convoy effect (delay many small jobs).

o Can lead to low CPU utilization if I/O-bound processes dominate.

 Examples of Non-Preemptive Algorithms:

o First-Come, First-Served (FCFS / FIFO)

o Shortest Job First (SJF, non-preemptive)

o Priority Scheduling (non-preemptive)

o Highest Response Ratio Next (HRN)

5. Interval Timer or Interrupting Clock

 Hardware device that generates interrupts at fixed time intervals.
 Used in preemptive scheduling to switch processes after time quantum expires.
 Ensures no single process monopolizes CPU.
6. Priorities in Scheduling
 Each process has a priority value.
 CPU is assigned to process with highest priority.
 Problems:
o Starvation: Low-priority jobs may never run.

o Solution: Aging (increase priority of waiting processes over time).

7. Scheduling Algorithms
(A) First-Come, First-Served (FCFS) / FIFO Scheduling
 Non-preemptive.
 Processes are scheduled in order of arrival.
 Simple but can cause convoy effect (long job delays small jobs).
 Example:
o Jobs: P1(5ms), P2(2ms), P3(3ms).

o Order: P1 → P2 → P3.

(B) Round Robin (RR) Scheduling

 Preemptive.
 Each process gets a fixed time slice (quantum).
 After quantum expires, process is preempted and placed at end of ready queue.
 Performance depends on quantum size:
o Too small → too many context switches (overhead).

o Too large → behaves like FCFS.

(C) Shortest Job First (SJF) Scheduling

 Non-preemptive.
 Process with shortest CPU burst time is scheduled first.
 Optimal for average waiting time but requires knowledge of burst time (difficult to
predict).
 Example:
o Jobs: P1(6), P2(8), P3(7), P4(3).

o Order: P4 → P1 → P3 → P2.

(D) Shortest Remaining Time (SRT) Scheduling

 Preemptive version of SJF.
 At arrival of a new process, if it has smaller remaining time than current process,
preemption occurs.
 Better average response time than SJF but higher overhead.
(E) Highest Response Ratio Next (HRN) Scheduling
 Non-preemptive.
 Used to reduce starvation.
 Priority (Response Ratio) calculated as:
HRN Priority=(Waiting Time+Burst Time)Burst Time\text{HRN Priority} = \frac{(Waiting\
Time + Burst\ Time)}{Burst\ Time}HRN Priority=Burst Time(Waiting Time+Burst Time)
 Process with highest ratio scheduled [Link]
 Advantage: Balances short and long processes.

(F) Multilevel Feedback Queue (MLFQ) Scheduling

 Multiple queues with different priority levels.
 Rules:
1. New processes enter at highest priority queue.
2. If they don’t finish within quantum, they move down to lower queue.
3. Lower queues get longer quantums.
4. Aging may be used to avoid starvation.
 Used in modern OS (like Linux, Windows).

(G) Fair-Share Scheduling

 Ensures fair CPU allocation among users/groups, not just processes.
 Example:
o User A has 1 process, User B has 4 processes.

o Without fair-share → User B gets more CPU (since more processes).

o With fair-share → Each user gets 50% CPU (A’s process gets 50%, B’s 4
processes share 50%).
 Used in multi-user systems.