1a) Describe FCFS CPU Scheduling Algorithm

(4 Marks – CO2, BTL2)

Definition

First Come First Served (FCFS) is the simplest non-preemptive CPU scheduling algorithm in which the
process that arrives first in the ready queue is executed first.

Working Principle

 Processes are executed in the order of their arrival

 Once a process gets CPU, it runs till completion
 Implemented using FIFO (First In First Out) queue

Characteristics

 Non-preemptive
 Simple to implement
 No starvation

Advantages

 Easy to understand and implement

 Fair scheduling (arrival order respected)

Disadvantages

 Convoy effect
 Poor average waiting time
 Not suitable for time-sharing systems

1b) Illustrate FCFS Algorithm and Calculate Average Waiting

Time
(8 Marks – CO2, BTL5)

Given Data

Process Burst Time

P1 5
P2 10
P3 4

Order of process entry:

P2 → P1 → P3

Step 1: Draw Gantt Chart

0 10 15 19
| P2 | P1 | P3 |

Step 2: Calculate Waiting Time

Waiting Time = Start Time − Arrival Time
(Arrival time assumed 0 for all, since order is given)

Process Start Time Waiting Time

P2 0 0
P1 10 10
P3 15 15

Step 3: Calculate Average Waiting Time

0+10+15 25
Average Waiting Time= ¿ =8.33 units
3 3

Final Answer
 Gantt Chart: Drawn correctly
 Waiting Times:
o P2 = 0
o P1 = 10
o P3 = 15
 Average Waiting Time = 8.33 units

Conclusion

FCFS scheduling executes processes in arrival order but may lead to high waiting time, especially when
long processes arrive first.
2(a) Round Robin CPU Scheduling Algorithm
Definition

Round Robin (RR) is a preemptive CPU scheduling algorithm in which each process is assigned a fixed
time quantum and the CPU is allocated to processes in a cyclic order.

Working Principle

 Each process is given CPU for a fixed time quantum

 If the process finishes within the quantum, it releases the CPU
 If not, the process is preempted
 The preempted process is placed at the end of the ready queue
 The next process is scheduled for execution

Characteristics

 Preemptive scheduling
 Time-sharing based algorithm
 Uses circular ready queue
 Avoids starvation

Advantages

 Fair allocation of CPU to all processes

 Suitable for time-sharing and multi-user systems
 Good response time

Disadvantages

 Performance depends on size of time quantum

 Large quantum → behaves like FCFS
 Small quantum → high context switching overhead

2(b) Illustrate Round Robin Algorithm (Quantum = 4)

(8 Marks – CO2, BTL5)

Given Data:

Process Burst Time

P1 12
P2 5
P3 6
Time Quantum (TQ) = 4

(All processes arrive at time 0)

Step 1: Execution Order

 P1 executes for 4 → remaining 8
 P2 executes for 4 → remaining 1
 P3 executes for 4 → remaining 2
 P1 executes for 4 → remaining 4
 P2 executes for 1 → completes
 P3 executes for 2 → completes
 P1 executes for 4 → completes

Gantt Chart:
0 4 8 12 16 17 19 23
|----|----|----|----|----|----|----|
P1 P2 P3 P1 P2 P3 P1
(4) (4) (4) (4) (1) (2) (4)

Step 2: Completion Time

Process Completion Time
P1 23
P2 17
P3 19

Step 3: Turnaround Time

Turnaround Time=Completion Time−Arrival Time
Process Turnaround Time
P1 23
P2 17
P3 19

Step 4: Waiting Time

Waiting Time=Turnaround Time−Burst Time
Process Waiting Time
P1 23 − 12 = 11
P2 17 − 5 = 12
P3 19 − 6 = 13

Average Waiting Time

11+12+13 36
Average Waiting Time= ¿ =12 milliseconds
3 3
Result:
 Average Waiting Time = 12 ms
 Round Robin ensures fairness
 Suitable for time-sharing systems

OR

2b )

Given:
P1 = 12, P2 = 5, P3 = 6 (assume all arrive at time 0; initial order P1, P2, P3)
q=4

Gantt Chart
0 4 8 12 16 17 19 23
|----|----|----|----|----|----|----|
P1 P2 P3 P1 P2 P3 P1
(4) (4) (4) (4) (1) (2) (4)

Completion, Turnaround, Waiting Times

 Completion times (CT):

P1 = 23, P2 = 17, P3 = 19
 Turnaround time (TAT = CT − Arrival):
P1 = 23, P2 = 17, P3 = 19
 Waiting time (WT = TAT − Burst):
P1 = 23 − 12 = 11
P2 = 17 − 5 = 12
P3 = 19 − 6 = 13

Averages

 Average Waiting Time: (11 + 12 + 13) / 3 = 12 units

 Average Turnaround Time: (23 + 17 + 19) / 3 = 59/3 ≈ 19.67 units

Notes: RR improves fairness and response time compared to FCFS, especially for mixed interactive
workloads. The chosen q = 4 keeps response reasonable with moderate context switching.
4a. Describe the Solution to Critical Section Problem
(6 Marks)

Introduction

In an operating system, a critical section is a part of a program where shared resources (such as variables,
files, or memory) are accessed.
The critical section problem is to design a solution that allows processes to share resources safely without
causing inconsistency or race conditions.

Requirements for a Correct Solution

Any solution to the critical section problem must satisfy the following three conditions:

1) Mutual Exclusion

 Only one process at a time can be inside the critical section.

 If one process is using a shared resource, other processes must wait.

2) Progress

 If no process is in the critical section and some processes want to enter, the system should decide
quickly which process will enter next.
 The decision should not be postponed indefinitely.

3) Bounded Waiting

 There must be a limit on how long a process waits to enter the critical section.
 No process should suffer from starvation.

Conclusion
A correct solution to the critical section problem ensures safe and fair access to shared resources.
By satisfying mutual exclusion, progress, and bounded waiting, the operating system prevents race
conditions and maintains system correctness.
Describe Peterson’s Solution with the Help of Code
(6 Marks)

Introduction

Peterson’s Solution is a software-based solution to the critical section problem.

It provides mutual exclusion between two processes without using any special hardware instructions.

It ensures that only one process at a time enters the critical section.

Working of Peterson’s Solution

1. A process sets its flag to true to show interest in entering the critical section.
2. It gives priority to the other process using the turn variable.
3. If both processes want to enter, only one is allowed based on turn.
4. After leaving the critical section, the process resets its flag to false.
Conclusion
Peterson’s Solution guarantees:

 Mutual Exclusion
 Progress
 Bounded Waiting

It is simple and effective for two processes, but it is mainly used for educational purposes in modern
operating systems.

5) Illustrate dining philosopher problem with neat diagram

6) What are the Four Necessary Conditions of Deadlock
(12 Marks)

Introduction

A deadlock is a situation in an operating system where a group of processes are permanently blocked
because each process is waiting for a resource that is held by another process in the same group.

Deadlock occurs only when all four necessary conditions hold simultaneously.
These conditions were first identified by Coffman et al.

Four Necessary Conditions of Deadlock

1) Mutual Exclusion
Explanation

Mutual exclusion means that at least one resource must be held in a non-shareable mode.
Only one process at a time can use the resource.

If another process requests that resource, it must wait until the resource is released.

Example

 Printer
 Tape drive
 Mutex lock

Only one process can use a printer at a time.

Importance

Without mutual exclusion, shared resources could be accessed simultaneously, and deadlock would not
occur.

2) Hold and Wait

Explanation

Hold and wait means that a process is holding at least one resource and is waiting to acquire additional
resources that are currently held by other processes.

The process does not release its currently held resources while waiting.

Example
  Process P1 holds a printer and waits for a scanner
 Process P2 holds the scanner and waits for the printer

Importance

This condition allows a process to block other processes, contributing to deadlock.

3) No Preemption
Explanation

No preemption means that resources cannot be forcibly taken from a process.

A resource can be released only voluntarily by the process holding it, after it has completed its task.

Example

 CPU registers
 Printer usage

The OS cannot forcibly remove a printer from a running process.

Importance

If resources could be preempted, deadlock could be avoided by taking resources away from waiting
processes.

4) Circular Wait
Explanation

Circular wait occurs when there exists a circular chain of processes, where each process is waiting for a
resource held by the next process in the chain.

Example

 P1 waits for resource held by P2

 P2 waits for resource held by P3
 P3 waits for resource held by P1

This forms a closed loop.

Importance

Circular wait is the final condition that locks the system into deadlock.

Diagram: Circular Wait Condition (Optional but Good for Marks)

P1 → waits for → P2
↑ ↓
P3 ← waits for ←

Summary Table
Condition Description
Mutual Exclusion Resources cannot be shared
Hold and Wait Process holds one resource while waiting for others
No Preemption Resources cannot be forcibly taken
Circular Wait Closed chain of waiting processes

Key Observation
✔ Deadlock occurs if and only if all four conditions occur together
✔ If any one condition is eliminated, deadlock can be prevented

Conclusion
The four necessary conditions—Mutual Exclusion, Hold and Wait, No Preemption, and Circular Wait
—form the foundation of deadlock theory.
Understanding these conditions is essential for designing deadlock prevention, avoidance, and detection
strategies in operating systems.

10 ) Explain Deadlock Prevention and the Four Necessary

Conditions for Deadlock
(12 Marks)

Introduction
A deadlock is a situation in an operating system where a set of processes are blocked forever, each waiting
for a resource held by another process.

Deadlock prevention is a technique used by the operating system to ensure that deadlock never occurs by
eliminating at least one of the four necessary conditions for deadlock.

Deadlock Prevention
Definition

Deadlock prevention is a strategy in which the operating system restricts the way resources are
requested and allocated, such that one or more necessary conditions for deadlock cannot occur.

If even one condition is prevented, deadlock is impossible.

Continue 6 answer four conditions

Describe Deadlock Avoidance with the Help of Graph

(12 Marks)

Introduction
Deadlock avoidance is a method used by the Operating System to make sure that deadlock never occurs.
Instead of stopping deadlock conditions completely, the OS checks every resource request and allows it
only if the system remains safe.

For deadlock avoidance, the OS must know in advance how many resources each process may need.

Definition of Deadlock Avoidance

Deadlock avoidance is a technique in which the Operating System allocates resources carefully so that the
system never enters an unsafe state and deadlock does not occur.

Safe State Concept

 A system is in a safe state if all processes can finish their execution in some order.
 This order is called a safe sequence.
 If no safe sequence exists, the system is in an unsafe state and deadlock may occur.
Resource Allocation Graph (RAG)
A Resource Allocation Graph is a diagram used to show processes, resources, and their relationships.

Components of RAG

 Processes → shown as circles (P1, P2, …)

 Resources → shown as squares (R1, R2, …)
 Request edge (Pi → Rj) → process requests a resource
 Assignment edge (Rj → Pi) → resource is given to a process
 Claim edge (Pi →→ Rj) → process may request the resource in future

Deadlock Avoidance Using RAG

The Operating System checks the resource allocation graph before granting a request.

 If granting the request creates a cycle, the request is not allowed

 If no cycle is created, the request can be granted

Graph Representation
Safe State (No Cycle)
P1 →→ R1 → P2
P2 →→ R2

 No cycle present
 System is in safe state
 Resource can be allocated

Unsafe State (Cycle Formed)

P1 →→ R1 → P2
↑ |
| ↓
R2 ←← P1 ← R2

 Cycle is present
 System becomes unsafe
 Deadlock may occur

Working of Deadlock Avoidance

1. OS maintains a resource allocation graph with claim edges
2. When a process requests a resource:
o Claim edge is changed to request edge
 3. OS checks the graph:
o If a cycle appears → request is denied
o If no cycle → request is granted
4. Resource is allocated and graph is updated

Advantages of Deadlock Avoidance

 Deadlock is completely avoided
 Better use of resources
 No need to stop or kill processes

Disadvantages of Deadlock Avoidance

 Requires advance knowledge of resource needs
 Extra overhead to check graph
 Not suitable for large systems

Difference Between Deadlock Avoidance and Prevention

Deadlock Avoidance Deadlock Prevention
Avoids unsafe states Breaks deadlock conditions
Dynamic checking Static rules
Better resource usage Less resource usage

Conclusion
Deadlock avoidance prevents deadlock by checking every resource request and ensuring the system stays
in a safe state.
Though it needs extra information and checking, it is an effective method to maintain a deadlock-free
operating system.
2a) Describe the Solution to Critical Section Problem
(6 Marks)

Introduction

In an operating system, a critical section is a part of a program where shared resources (such as variables,
files, or memory) are accessed.
The critical section problem is to design a solution that allows processes to share resources safely without
causing inconsistency or race conditions.

Requirements for a Correct Solution

Any solution to the critical section problem must satisfy the following three conditions:

1) Mutual Exclusion

 Only one process at a time can be inside the critical section.

 If one process is using a shared resource, other processes must wait.

2) Progress

 If no process is in the critical section and some processes want to enter, the system should decide
quickly which process will enter next.
 The decision should not be postponed indefinitely.

3) Bounded Waiting

 There must be a limit on how long a process waits to enter the critical section.
 No process should suffer from starvation.

Conclusion
A correct solution to the critical section problem ensures safe and fair access to shared resources.
By satisfying mutual exclusion, progress, and bounded waiting, the operating system prevents race
conditions and maintains system correctness.
3a)
4.a. Explain Process State Model with Neat Diagram
(6 Marks)

Introduction

A process is a program in execution.

During its lifetime, a process changes its state based on CPU allocation, I/O requests, and completion.
The process state model describes the different states a process goes through and the transitions between
them.

Process States
1) New

 Process is being created

 OS creates the Process Control Block (PCB)

2) Ready

 Process is loaded into main memory

 Waiting for CPU allocation

3) Running

 Process is currently executing on the CPU

4) Waiting (Blocked)

 Process is waiting for an event such as I/O completion

 CPU is released voluntarily

5) Terminated

 Process has finished execution

 OS releases all resources

Neat Diagram: Process State Model

+-----+
| New |
+-----+
|
v
+-------+
| Ready |
+-------+
 |
v
+---------+
| Running |
+---------+
| |
| v
| +----------+
| | Waiting |
| +----------+
| |
+------+
|
v
+------------+
| Terminated |
+------------+

Explanation of Transitions
 New → Ready : Process admitted to ready queue
 Ready → Running : CPU scheduler selects process
 Running → Waiting : Process requests I/O
 Waiting → Ready : I/O completed
 Running → Terminated : Process finishes execution

Conclusion

The process state model helps the Operating System manage process execution efficiently.
By controlling state transitions, the OS ensures better CPU utilization and system performance.

4b) Explain File Allocation Methods

Introduction

File allocation methods define how disk blocks are assigned to files and how files are stored on secondary
storage.
The Operating System uses different allocation methods to improve disk utilization and access speed.

1) Contiguous File Allocation

Explanation:
A file is stored in continuous disk blocks.

Diagram:

Disk Blocks:
| B1 | B2 | B3 | B4 | B5 | B6 |
File A → B2 B3 B4

Merits: Fast access

Demerits: External fragmentation
2) Linked File Allocation
Explanation:
Each file block contains a pointer to the next block.

Diagram:

File A:
B5 → B9 → B2 → NULL

Merits: No external fragmentation

Demerits: Slow random access

3) Indexed File Allocation

Explanation:
An index block stores addresses of all file blocks.

Diagram:

Index Block
| B3 | B7 | B5 | B9 |

Merits: Supports direct access

Demerits: Extra index overhead

Conclusion

Different file allocation methods are used based on performance and storage requirements.
Among them, indexed allocation is most efficient and widely used.