Feature FCFS (First-Come, First-Served) SJF (Shortest Job First)

Basic Logic Executes processes in the order of Executes the process with the shortest CPU
arrival (FIFO queue). burst time first.
Selection Criteria Arrival time Burst time
Preemptive Non-preemptive Generally non-preemptive, but preemptive
Nature version exists (SRTF – Shortest Remaining
Time First).
Average Waiting Usually high Minimum among all scheduling algorithms
Time
Convoy Effect Present Not present.
(short processes
wait for long
time).
Starvation No starvation Possible starvation of long processes.
Response Time Poor for short processes Better response time for short processes
Throughput Lower compared to SJF Higher than FCFS
Implementation Very simple to implement using Complex to implement
queue
Suitability Suitable for batch systems Suitable when burst time is known in
advance
Overhead Very low overhead because it simply More overhead because the system must
follows the arrival order. No extra check and compare burst times to choose
calculations are needed. the shortest job.
Critical Section Problem:-
Critical Section:-
• A critical section (CS) is a part of a process’s code where it accesses or modifies shared resources and
then exits it, releasing the resources.
• Because multiple processes may attempt to access the same shared resource, executing this section
without control can lead to race conditions and data inconsistency.

Critical Section Problem Defination:-

• The Critical Section Problem deals with how to design a synchronization protocol such that when one
process is in its critical section, no other process should enter its critical section at the same
[Link] should cooperate and wait their turn safely and fairly.
• It occurs in concurrent processing environments where processes run in parallel and compete for
shared resources.

Structure:-
Every process typically consists of:-
• Entry Section:-Code where a process requests permission to enter the critical section.
• Critical Section:-Code that accesses shared resources.
• Exit Section:-Code where the process releases the resource and signals others.
• Remainder Section:-Rest of the codes that does not access shared resources.

Key Requirements for a Valid Solution

Any protocol that solves the critical section problem must satisfy three essential conditions:-
• Mutual Exclusion:-Only one process can be inside the critical section at any time.
• Progress:-If no process is in the critical section and some processes wish to enter, only those processes
not in their remainder section can participate in the decision, and this selection cannot be postponed
indefinitely.
• Bounded Waiting:-There must be a limit on how many times other processes can enter the critical
section after a process has requested entry before it can actually [Link] ensures no process waits
forever (no starvation).

Solutions to the Critical Section Problem

• Hardware Solutions:-
1. These use special CPU instructions to ensure atomic (non-interruptible) operations.
2. Use special instructions like test-and-set, compare-and-swap to enforce atomic operations.
3. It is Effective but limited to multiprocessor systems.
• Software Solutions:-
1. Algorithms designed without special hardware support.
2. Peterson’s Algorithm:-Works for 2 processes only.
3. Bakery Algorithm:-Works for multiple processes.
• OS-Level Synchronization Tools:-
1. These are used in real operating systems.
2. Mutex (Lock):-Process locks before entering critical [Link] after leaving critical section.
3. Semaphore:-It uses integer [Link] uses wait() and signal() operations.
4. Monitor:-Only one process can execute inside the monitor at a [Link] in high-level languages.
5. Sleep/Wakeup (Blocking):-If a resource is not available, a process goes to sleep and waits until it is
awakened.
Deadlock:-
• Defination:-
1. Deadlock is a situation where two or set of processes are blocked because each process is holding a
resource and waiting for another resource required by some other process.
2. Deadlock involves conflicting needs for resources by two or more processes.
3. In deadlock situation the system becomes stuck and none of the processes can proceed.
4. Deadlock is permanent waiting [Link] process holds one resource and waits for another
resource

• How Deadlock Occurs

Deadlock occurs when:-
1. Processes hold some resources.
2. They continue waiting for additional resources.
3. The required resources are held by other waiting processes.
4. A circular chain of waiting is formed.
This results in permanent blocking, where no process can proceed.

System Model:-
• In an Operating System, multiple processes execute [Link] complete their tasks, these
processes require system resources such as CPU,Memory,Files,Printers,I/O Devices
• The System Model explains how processes request, use, and release resources, and how improper
interaction between them can lead to deadlock.

• Types of System Resources

System resources are classified into two types:
1. Preemptable Resources
o These resources can be taken away from a process without causing serious issues.
o The operating system can reassign them to another process.
o Examples: CPU, Memory

2. Non-Preemptable Resources
o These resources cannot be forcibly taken back once allocated.
o The process must release them voluntarily after completing its task.
 o Examples: Printers, Files
• Deadlocks mainly occur with non-preemptable resources, because they cannot be forcefully recovered.

• Process and Resource Behavior:-

A process follows three main steps to use a resource:
1. Request the resource
2. Use the resource
3. Release the resource
If the requested resource is unavailable, the process enters a waiting (blocked) state.

Types of deadlock models:-

Deadlock models are used to represent, analyze, and detect deadlock in a system.
Resourse Allocation Graph (RAG) :-
• Definition:-
1. Resource Allocation Graph is a graphical representation of processes and resources which helps to
understand how resources are assigned in an operating system.

• Features:-
1. A Resource Allocation Graph (RAG) is used to detect deadlocks by analyzing the relationships
between processes and resources in a system.
2. It visually represents how resources are allocated.
3. It visually represents how resources are requested.
4. It helps in detecting deadlock by analyzing cycles in the graph.
5. It helps to visualize deadlocks more clearly than tables.
6. Processes = circles, Resources = squares and edges show allocation or request.

• Deadlock Detection Using RAG

1. If no cycle → No Deadlock
2. If cycle exists:
o If only one instance per resource type → Deadlock exists
o If multiple instances per resource type → Deadlock may or may not exist

• Advantages
1. Easy to understand
2. Visual representation
3. Useful for systems with single resource instance
• Disadvantages
 1. Becomes complex for large systems
2. Difficult when multiple resource instances exist

Wait-For Graph (WFG):-

• Definition:-
1. Wait-For Graph is a simplified version of RAG used for deadlock detection.
2. It is mainly used when each resource has only one instance.

• Features:-
1. In this algorithm,we only have processes as vertices in the graph.
2. WFG is obtained by removing resource nodes from [Link] directly shows process-to-process
dependency.
3. Less complex than Resource Allocation Graph and provides faster deadlock detection

• Used for Deadlock Detection

1. If cycle exists → Deadlock definitely exists
2. If no cycle → No deadlock

• Advantages
1. Easy to analyze
2. Less complex than RAG
3. Faster detection
• Disadvantages
1. Works properly only for single instance resources
2. Not suitable for multiple instances

Necessary Conditions for Deadlock

• Deadlock occurs only when all four conditions happen [Link] even one condition is removed,
deadlock will not occur.
• Mutual Exclusion
1. Mutual Exclusion condition requires that at least one resource be held in a non-shareable mode
2. Only one process can use a resource at a time.
3. Other processes must wait.
4. Example:
Only one process can use the printer at a time.
• Hold and Wait
1. This condition implies the existence of a process holding some resources and waiting for another one
that is held by some other process in the system.
2. A process is holding at least one resource.
3. At the same time, it is waiting for another resource.
4. It does not release the resource it already has.
5. Example:
Process P1 holds printer and waits for file.

• No Preemption
1. Preemption is the act of taking a resource from a process before it has finished its task.
2. According to the no preemption condition, resources cannot be taken forcibly from a process, a
process can only release resources voluntarily after completing its task
3. A resource cannot be taken forcibly from a process.
4. The process must release it voluntarily after finishing.
5. Example:
If Process P1 has the printer, it will not release it until its work is [Link] if Process P2 needs it
urgently.

• Circular Wait
1. This condition refers to the waiting of processes in a circular manner where the process waits for the
resource which is held by the next one.
2. A circular chain of processes is formed.
3. Each process waits for a resource held by the next process.
4. Example:
Process P1 waits for P2 to release resource R2.
P2 waits for P3 to release resource R3.
P3 waits for P1 to release resource R1.
 Forms circular chain.

Deadlock Handling:-
• Defination:-Deadlock handling methods are strategies used in operating systems to ensure processes
do not remain permanently blocked, maintaining smooth execution and system reliability.
• OS chooses method based on system design. There are 4 ways of deadlock handling:-
1. Preventing or avoiding deadlock:-By avoid allowing the system to become stuck in a loop.
2. Detection and recovery of deadlocks:-When deadlocks are detected, abort the process or preempt
some resources.
3. Ignore the problem(deadlock) entirely.
4. To avoid deadlocks, the system requires more information about all processes.

Deadlock Prevention:-
• Deadlock prevention means we change the system rules so that at least one of the four deadlock
conditions never occurs.

• Preventing Mutual Exclusion:-

1. Convert non-sharable resources into sharable resources, if possible.
2. But some resources like printers cannot be [Link] this method is not always possible.
3. Example:-Make files read-only so multiple processes can access them.

• Preventing Hold and Wait (Most Common Method)

1. Force a process to request all required resources at once, before execution.
2. And allow process to request resources only when it is not holding any other resource.
3. These method make low resource utilization and gives long waiting time

• Preventing No Preemption:-
1. Allow resource preemption. This makes system safe.
2. If a process cannot get a required resource, take back the resources it already holds and allocate
them to another process.
3. But not all resources can be preempted like printers.
• Preventing Circular Wait (Best Practical Method)
1. Assign a fixed order to all resources.
2. Processes can request resources only in increasing order of that numbering.
3. This prevents formation of circular chain.
4. It is Simple and effective practical method.

Deadlock Avoidance:-
• Deadlock avoidance is a strategy where the operating system checks every resource allocation before
granting it to ensure that the system never enters an unsafe state that could lead to deadlock.

• Key Ideas in Deadlock Avoidance

1. Check before Allocation:-Before allocating resources to a process, the system checks if giving the
resources will keep the system in a safe state.
2. Safe and Unsafe States:-
o Safe State: There is at least one sequence of process execution where each process can complete
and release its resources without deadlock.
o Unsafe State: The system might lead to deadlock if resources are allocated improperly.
3. System Needs Advance Knowledge about:-
o Number of resources each process needs
o Currently free resources
o Allocated resources to processes

• Banker’s Algorithm (Dijkstra Algorithm)

1. Defination:-
o The Banker’s Algorithm is the most widely used deadlock avoidance technique.
o It gets its name from banking systems, where a bank grants a loan only if it knows it can repay
all future [Link], the OS grants resources only if the system will remain safe.
o Used when multiple instances of resources exist.
2. How It Works:-
o Each process must declare its maximum required resources in advance.
o When a process requests resources, the system pretends to allocate them and then checks if the
new state is safe.
o If the system is still safe after allocation, the request is granted.
o If the new state is unsafe, the request is denied and the process waits

• Resource Allocation Graph (RAG) Algorithm:-

1. Defination:-
o The Resource Allocation Graph (RAG) Algorithm is a method used in Operating Systems for
deadlock avoidance and detection.
o It uses a graphical representation of processes and resources to check whether allocating a
resource will lead to deadlock.
2. How it Works:-
o When a process requests a resource, check if allocation creates a cycle in the graph.
o If allocation creates a cycle ,do not allocate the resource (unsafe state).
o If allocation does not create a cycle then Allocate the resource (safe state).
Deadlock Recovery:-

• Defination:-
1. Deadlock recovery is the process of resolving a deadlock after it has already occurred.
2. In deadlock recovery, the OS allows deadlocks to occur and then takes steps to break the deadlock
and free the stuck resources.

• Techniques:-
1. Process Termination
o The simplest method is to abort processes involved in the deadlock.
o Abort all deadlocked processes:-Guaranteed to break deadlock but loses a lot of work.
o Abort one process at a time (victim selection):-System aborts processes one by one until deadlock is
[Link] is choosen based on priority, less progress, few resources held, etc.

2. Resource Preemption
o Instead of killing processes, the OS takes some resources away from deadlocked processes and gives
them to others to break the cycle.
o Challenges include which resource to pre-empt
o These may also cause starving of process by repeatedly losing the resources.

3. Process Rollback
o Periodically save the state of [Link] deadlock occurs, roll back one or more processes to a
safe earlier state.
o After rollback, restart processes when resources are available.
o Useful in systems where killing processes is not acceptable like banking.

4. Combination of Methods
o In practice, OS often uses a mix of termination, preemption, and rollback depending on process type
and system design.
Question Bank:-
1. Define Scheduling and state its objectives.

2. State the difference between Preemptive and Non-Preemptive scheduling.

3. Explain Preemptive and Non-Preemptive scheduling with their features.

4. Define CPU-bound program and I/O-bound program.

5. Explain CPU and I/O burst cycle in detail with diagram and example.

6. Explain any five scheduling criteria.

7. Describe First Come First Served (FCFS) scheduling algorithm with example.

8. Describe Shortest Job First (SJF) scheduling algorithm with example.

9. Describe Shortest Remaining Time First (SRTF/SRTN) scheduling algorithm with example.

10. Explain Round Robin (RR) scheduling algorithm with suitable example.

11. Describe Priority scheduling algorithm with example.

12. Describe Multilevel Queue scheduling with labelled diagram.

13. Compare FCFS and SJF scheduling algorithm.

14. Explain Critical Section problem with its structure.

15. Explain solutions to Critical Section Problem.

16. Define Deadlock and state its impact.

17. Define Deadlock. Explain models of Deadlock. Give characteristics of Deadlock.

18. What are the necessary conditions leading to Deadlocks?

19. Describe prevention of deadlock occurrence.

20. Describe avoidance of deadlock occurrence and Banker’s Algorithm steps.

21. Describe recovery after deadlock occurrence.

22. Calculate average waiting time for following data using First Come First Served (FCFS) and Shortest Job
First (SJF) algorithms.
 Process Burst time Arrival time
P0 08 0
P1 04 1
P2 05 2
P3 03 3
Answers:-
• FCFS Average Waiting Time = 7.75 ms
• SJF Average Waiting Time = 7 ms

23. Calculate average waiting time with Round Robin for following processes in memory.(Time Slice = 4ms)
Process Burst time
P1 3
P2 5
P3 7
P4 4
Answers:-
Average Waiting Time = 8.5 ms.

24. Solve given problem by Using FCFS to calculate average waiting time and turnaround time.
Process Arrival time Burst time
P1 0 7
P2 1 4
P3 2 9
P4 3 6
P5 4 8
Answer:-
• Average Waiting Time = 10.8 ms
• Average Turnaround Time = 17.6 ms

25. Solve given problem by using FCFS scheduling algorithm. Draw correct Gantt chart and and average
turnaround time –
Process Arrival time Burst time
P0 0 10
P1 1 29
P2 2 3
P3 3 7
P4 4 12
Answer:-
Average Turnaround Time = 38.2 ms

26. Calculate average waiting time for SJF (Shortest Job First) and Round Robin (RR) algorithm table: (Time
slice 4 ms)
Process Burst Time
p1 10
p2 4
p3 9
 p4 6
Answer:-
SJF Average Waiting Time = 8.25 ms
Round Robin Average Waiting Time = 15.5 ms

27. Consider the four processes P1, P2, P3 and P4 with length of CPO Burst time. Find out Avg waiting time
and Avg turn around time for the following Algorithms.
i) FCFS
ii) RR (Slice-4ms)
iii) SJF(Preemptive and Non-Preemptive)
Process Arrival time Burst time
P1 0 8
P2 1 4
P3 2 9
P4 3 5
Answer:-
• FCFS
Average Waiting Time = 8.75 ms
Average Turnaround Time = 15.25 ms
• Round Robin (Time Slice = 4 ms)
Average Waiting Time = 11.75 ms
Average Turnaround Time = 18.25 ms
• SJF(Non-Preemptive)
Average Waiting Time = 7.75 ms
Average Turnaround Time = 14.25 ms
• SJF(Preemptive)
Average Waiting Time = 6.5 ms
Average Turnaround Time = 13 ms

28. The jobs are scheduled for execution as follows

Process Arrival Time Burst Time
P1 0 7
P2 1 4
P3 2 10
P4 3 6
P5 4 8
Solve the problem using:
(i) SJF
(ii) FCFS
Also find average waiting time using Gantt chart.
Answers:-
SJF Average Waiting Time = 10 ms
FCFS Average Waiting Time = 11.2 ms