PAPER 1 PAPER 2 PAPER 3

OPERATING SYSTEMS · COMPLETE SOLUTIONS

Question Paper 1
Every question solved in full detail · Click any card to expand

SECTION A — SHORT QUESTIONS

▾
Q1(a) What is operating system? Explain the main purposes of an operating system. 4 Marks

▸ DEFINITION

An Operating System (OS) is system software that acts as an intermediary between the user/application programs and
computer hardware. It manages all hardware resources and provides a convenient and efficient environment for
program execution.

Think of the OS as a government: it doesn't do the actual work itself, but it manages all resources, enforces rules, and
provides services.

▸ MAIN PURPOSES

Resource Management: Manages CPU, memory, disk, and I/O devices — allocates them efficiently among competing
processes.

Process Management: Creates, schedules, suspends, resumes, and terminates processes. Handles CPU scheduling.

Memory Management: Tracks which parts of memory are in use, allocates memory to processes, and deallocates
when done.

File System Management: Organises data into files and directories, manages read/write/delete operations, controls
access.

Device Management: Controls hardware devices via device drivers; manages I/O operations.

Security & Protection: Prevents unauthorized access to resources; isolates processes from each other.

User Interface: Provides CLI (Command Line Interface) or GUI (Graphical User Interface) for users to interact with
the computer.

Networking: Manages network connections, protocols, and communication between systems.

▾
Q1(b) Briefly explain dual mode operation. How can a user program access services provided by an OS? 4 Marks

▸ DUAL MODE OPERATION

Dual mode operation protects the OS from user programs and protects users from each other by separating execution
into two modes using a mode bit in hardware:

User Mode (Mode bit = 1): Restricted mode. User applications run here. Privileged instructions (direct I/O, changing
mode bit, modifying interrupt vectors) are NOT allowed. A violation causes a trap to the OS.

Kernel Mode (Mode bit = 0): Privileged mode. The OS kernel runs here. ALL instructions are permitted including
privileged ones.

User Program OS Kernel

[User Mode] ──trap──► [Kernel Mode]
mode bit = 1 mode bit = 0
◄──return──────────────────────

▸ HOW USER PROGRAMS ACCESS OS SERVICES

User programs access OS services through System Calls:

1. User program calls a library function (e.g., read())

2. Library executes a special trap instruction (software interrupt)

3. CPU switches from user mode → kernel mode (mode bit: 1→0)

4. OS handles the request via a system call handler

5. OS returns result to the user program

6. CPU switches back to user mode (mode bit: 0→1)

Examples of system calls: fork() (create process), read()/write() (I/O), open()/close() (files), exit() (terminate).

▾
Q1(c) What are the differences between blocking and non-blocking system call? 2 Marks

ASPECT BLOCKING SYSTEM CALL NON-BLOCKING SYSTEM CALL

Process waits (is suspended) until the Returns immediately whether or not
Behaviour
operation completes operation is done

CPU Process gives up CPU while waiting Process can continue doing other work

More complex (needs polling or

Programming Simpler to write
callbacks)

Non-blocking read returns -1 if no

Example read() waits until data is available
data yet

▾
Q2(a) What do you mean by job and process? 2 Marks

Job: A unit of work or program submitted by a user to the computer for execution. It is a static entity — it sits on
disk waiting to be executed. In batch systems, jobs are queued and processed one after another. A job becomes a
process when the OS loads it into memory.

Process: A program in execution. It is a dynamic entity with its own Program Counter, stack, data section, heap, and
CPU registers. A process has a lifetime (New → Running → Terminated) and is managed by the OS via its PCB.

Key difference: A job is passive (on disk). A process is active (in memory, using CPU or waiting for resources).

▾
Q2(b) Draw a process control block. 3 Marks

A Process Control Block (PCB) is a data structure maintained by the OS for every process. It is the "identity card" of a
process.

┌─────────────────────────────────────┐
│ PROCESS CONTROL BLOCK │
├─────────────────────────────────────┤
│ Process ID (PID) → 1234 │ ← unique identifier
├─────────────────────────────────────┤
│ Process State → Ready │ ← New/Ready/Running/Wait/Term
├─────────────────────────────────────┤
│ Program Counter (PC) → 0x4A2 │ ← next instruction address
├─────────────────────────────────────┤
│ CPU Registers │ ← AX, BX, CX, SP, flags...
│ (saved context) │
├─────────────────────────────────────┤
│ CPU Scheduling Info │ ← priority, queue pointers
├─────────────────────────────────────┤
│ Memory Management Info │ ← page tables / base-limit regs
├─────────────────────────────────────┤
│ Accounting Info │ ← CPU time used, time limits
├─────────────────────────────────────┤
│ I/O Status Info │ ← open files, I/O devices list
└─────────────────────────────────────┘

When a context switch occurs, the OS saves all this information for the current process and loads it for the next one.

▾
Q2(c) Draw the process state diagram and explain it. 5 Marks

admitted
┌───────┐ ──────────► ┌───────┐ scheduler dispatch ┌─────────┐
│ NEW │ │ READY │ ───────────────────► │ RUNNING │
└───────┘ └───────┘ └─────────┘
▲ │ │
│ interrupt / preempt │ │ I/O or
└───────────────────────────┘ │ event wait
▼
┌──────────────┐
┌────────────┐ ◄── exit ───────────────────── │ WAITING │
│ TERMINATED │ └──────────────┘
└────────────┘ I/O or event completion │
──────────────────────────────────►│ (back to READY)

▸ STATE EXPLANATIONS

New: Process is being created. PCB is allocated. Program is loaded from disk.

Ready: Process is loaded in memory and waiting in the ready queue for CPU time. It has everything it needs except
the CPU.

Running: Process is currently executing on the CPU. Only ONE process can be running per CPU at a time.

Waiting (Blocked): Process cannot proceed until some event occurs (e.g., I/O completion, semaphore signal, child
process finishes). CPU is freed for other processes.

Terminated: Process has finished execution (normally or abnormally). PCB is eventually deallocated. May remain as a
"zombie" until parent reads exit status.

▸ TRANSITIONS

New → Ready: Process admitted by OS (long-term scheduler)

Ready → Running: Short-term scheduler dispatches process

Running → Ready: Timer interrupt / preemption

Running → Waiting: Process requests I/O or waits for event

Waiting → Ready: I/O completes or event occurs

Running → Terminated: Process calls exit()

▾
Q3(a) Explain the life cycle of a process. Describe PCB. 4 Marks

▸ PROCESS LIFE CYCLE

The complete life cycle of a process from creation to termination:

1. Creation (New state): User runs a program or OS creates a system process. A new PCB is allocated. The process is
admitted to the ready queue.

2. Ready state: Process waits in the ready queue. The short-term (CPU) scheduler picks it when CPU is free.

3. Execution (Running state): CPU executes process instructions. Process runs until: it finishes, requests I/O, or is
preempted.

4. Waiting state: If the process needs I/O (e.g., disk read), it is moved to the waiting queue. CPU is given to another
process.

5. Back to Ready: When I/O completes, process moves back to ready queue.

6. Termination: Process calls exit() or is killed. Resources are released. PCB is removed.

▸ PCB DESCRIPTION

See Q2(b) — PCB is the data structure that stores all info about a process (PID, state, PC, registers, memory info, I/O
info, accounting info). It enables the OS to manage, schedule, and context-switch between processes.

▾
Q3(b) What do you mean by thread? Is there any advantage of thread over process? 4 Marks

▸ THREAD

A thread is the smallest unit of CPU execution. It is also called a lightweight process (LWP). A process can contain one
or more threads. All threads within a process share the same:

Code section (text)

Data section (global variables)

Open files and OS resources

But each thread has its own:

Thread ID, Program Counter

Register set

Stack (local variables, function calls)

▸ ADVANTAGES OF THREAD OVER PROCESS

ADVANTAGE EXPLANATION

Thread creation is 10–100× faster than process creation (no need to

Faster creation
duplicate address space)

Less memory Threads share process memory — no separate address space needed

Fast communication Threads share memory directly; no need for expensive IPC mechanisms

Cheaper context Switching between threads of the same process is faster (shared memory
switch mapping stays)

Better CPU use While one thread waits for I/O, another thread of same process can run

Scalability Multiple threads can run truly in parallel on multi-core CPUs

▾
Q3(c) What do you mean by busy waiting? 2 Marks

Busy Waiting (also called spin-waiting) is a synchronization technique where a process continuously and repeatedly
tests a condition in a loop while waiting for a resource to become available, without giving up the CPU.

// Example of busy waiting:

while (flag == 1) {
; // do nothing, just keep looping
}
// flag becomes 0 when resource is free

Disadvantage: Wastes CPU cycles — the CPU is occupied doing nothing useful.

Use case: Acceptable in multiprocessor systems for very short critical sections (spinlocks), where the wait is
expected to be extremely brief.

Better alternative: Use sleep/wakeup mechanisms (semaphores) so the waiting process gives up the CPU.

▾
Q4(a) Briefly write the direct and indirect method for inter process communication. 4 Marks

▸ DIRECT COMMUNICATION

Processes name each other explicitly when sending/receiving messages.

send(P, message) — send a message to process P

receive(Q, message) — receive a message from process Q

A communication link is automatically established between every pair of processes.

Exactly one link between each pair.

Usually bidirectional.

Drawback: Hard-coded process IDs — changing a process name requires finding and updating all references.

▸ INDIRECT COMMUNICATION

Messages are sent to and received from mailboxes (also called ports). Processes don't need to know each other.

send(A, message) — send to mailbox A

receive(A, message) — receive from mailbox A

A link exists only if both processes share a mailbox.

A link can be shared among more than two processes.

Multiple links can exist between each pair (via different mailboxes).

Advantage: More flexible — multiple processes can communicate through one mailbox.

Mailboxes can be owned by a process (destroyed when process exits) or by the OS (persistent).

▾
Q4(b) Which scheduling algorithms could result in starvation and why? (FCFS, Round Robin, SJF) 3 Marks

FCFS — NO Starvation. Every process runs in the order it arrives. A process that arrives first will eventually get the
CPU regardless of burst time. No process waits indefinitely.

Round Robin — NO Starvation. Each process gets a time quantum in a circular manner. Every process is guaranteed
CPU time in each cycle. Fair by design.

Shortest Job First (SJF) — CAUSES STARVATION. ✗

Why SJF causes starvation: SJF always picks the process with the shortest burst time. If a stream of short processes
keeps arriving, they will always be preferred over a long process. The long process may wait in the ready queue
indefinitely — it never gets CPU time. This is called starvation.

Solution to SJF starvation: Aging. Gradually increase the priority of processes that have been waiting for a long time.
Eventually the long process gets a high enough priority to be scheduled.

▾
Q4(c) Explain the logical address and physical address. 3 Marks

Logical Address (Virtual Address): The address generated by the CPU during program execution. The user program
only sees logical addresses. The set of all logical addresses is the logical address space. Each process has its own
logical address space starting from 0.

Physical Address: The actual location in RAM (physical memory). The memory controller uses this to read/write data.
The user program never sees physical addresses directly.

CPU generates MMU translates Physical RAM

logical addr ──────────────────► physical addr
0x0500 (using page table) 0x8500

MMU = Memory Management Unit (hardware chip)

LOGICAL ADDRESS PHYSICAL ADDRESS

Generated by CPU Loaded into memory address register

User program sees this User program never sees this

Can be same across processes (each starts at 0) Always unique in RAM

Translated at runtime by MMU Actual hardware address

SECTION B — LONG QUESTIONS

▾
Q5(a) Compare FCFS and Round Robin CPU scheduling algorithms. 3 Marks

FEATURE FCFS ROUND ROBIN

Full Name First Come First Served Round Robin

Type Non-preemptive Preemptive

Starvation No No

Convoy Effect Yes — long jobs block short ones No

Response Time Poor for short processes Good — fair for all

Context Switches Minimal Many (every quantum)

Overhead Low Higher

Best For Batch systems Time-sharing / interactive

Implementation Simple queue (FIFO) Circular queue with timer

Throughput Lower (convoy effect) Better for mixed workloads

▾
Q5(b) Priority Scheduling — Calculate WT, TAT, Avg WT, Avg TAT. P0(AT=7,BT=7,Pri=3), P1(AT=3,BT=8,Pri=1), 4 Marks

P2(AT=6,BT=12,Pri=2)

▸ GIVEN DATA (PRIORITY 1 = HIGHEST)

PROCESS ARRIVAL TIME BURST TIME PRIORITY

P0 7 7 3 (lowest)

P1 3 8 1 (highest)

P2 6 12 2

▸ SCHEDULING (NON-PREEMPTIVE PRIORITY)

t=0 to t=3: No process has arrived → CPU is IDLE

t=3: P1 arrives (Priority 1 — highest) → starts executing immediately
t=11: P1 finishes (3+8=11). Ready queue: P2(pri=2), P0(pri=3)
→ Pick highest priority → P2 starts
t=23: P2 finishes (11+12=23). Ready queue: P0(pri=3)
→ P0 starts
t=30: P0 finishes (23+7=30)

▸ GANTT CHART

IDLE P1 P2 P0

0 3 11 23 30

▸ CALCULATIONS

PROCESS AT BT PRIORITY START TIME COMPLETION TIME TAT = CT−AT WT = TAT−BT

P0 7 7 3 23 30 23 16

P1 3 8 1 3 11 8 0

P2 6 12 2 11 23 17 5

Average Waiting Time = (16 + 0 + 5) / 3 = 21 / 3 = 7.00 ms

Average Turnaround Time = (23 + 8 + 17) / 3 = 48 / 3 = 16.00 ms

▾
Q5(c) Define: i) Throughput ii) CPU utilization iii) Response time 3 Marks

Throughput: The number of processes that complete execution per unit of time. A higher throughput means more
work is being done. Formula: Throughput = Number of completed processes / Total time. Goal: Maximize throughput.

CPU Utilization: The percentage of time the CPU is busy (not idle). Formula: CPU Utilization = (CPU Busy Time / Total
Time) × 100%. Target: 40% (lightly loaded) to 90% (heavily loaded). Goal: Maximize CPU utilization.

Response Time: The time from when a request is submitted until the first response is produced (not the final
output). Especially important in interactive systems (e.g., clicking a button should show instant feedback). Formula:
Response Time = Time of first CPU run − Arrival Time. Goal: Minimize response time.

▾
Q6(a) What is semaphore? Explain how semaphore can be implemented. 6 Marks

▸ DEFINITION

A Semaphore is an integer variable used for process synchronization. It is accessed only through two atomic
(indivisible) operations: wait() and signal(). Introduced by Dijkstra.

▸ TYPES

Binary Semaphore (Mutex): Can only take values 0 or 1. Used for mutual exclusion. Initialized to 1.

Counting Semaphore: Can take any non-negative integer value. Used to control access to a resource pool with
multiple instances. Initialized to the number of available resources.

▸ BASIC IMPLEMENTATION (WITH BUSY WAITING)

wait(S): signal(S):
while (S <= 0) S = S + 1;
; // busy wait
S = S - 1;

Usage Pattern:
wait(mutex); // enter critical section — lock
// ... critical section ...
signal(mutex); // exit critical section — unlock

▸ BETTER IMPLEMENTATION (WITHOUT BUSY WAITING)

To avoid wasting CPU with busy waiting, we associate a waiting queue with each semaphore:

typedef struct {
int value;
struct process *list; // waiting queue
} semaphore;

wait(S):
[Link]--;
if ([Link] < 0) {
add this process to [Link];
block(); // put process to sleep — releases CPU
}

signal(S):
[Link]++;
if ([Link] <= 0) {
remove a process P from [Link];
wakeup(P); // wake it up — move to ready queue
}

This eliminates busy waiting. A process that cannot proceed is blocked (sleeps) instead of looping. When the resource
becomes free, signal() wakes up a waiting process.

▾
Q6(b) Explain all three requirements to solve the critical section problem. 4 Marks

The Critical Section is a segment of code where a process accesses shared resources (variables, files, etc.). Any
correct solution must satisfy all three requirements:

1. Mutual Exclusion: If process Pi is executing in its critical section, then no other process can be executing in their
critical section at the same time.

This prevents race conditions — ensures only one process modifies shared data at a time.

2. Progress: If no process is in the critical section and some processes want to enter, only those processes not in their
remainder section can participate in deciding who enters next. This decision cannot be postponed indefinitely. The
system must make progress.

This prevents deadlock — if the critical section is free, some process must be allowed to enter.

3. Bounded Waiting: There must be a bound (limit) on the number of times other processes can enter their critical
section after a process has made a request to enter and before that request is granted.

This prevents starvation — no process should wait forever to enter its critical section.

▾
Q7(a) What do you mean by deadlock? Explain the necessary conditions for deadlock. 5 Marks

▸ DEADLOCK DEFINITION

A deadlock is a situation where a set of processes are permanently blocked, each waiting for a resource that is held by
another process in the set. No process can proceed — the system is stuck.

Example:
Process P1 holds Resource R1, waiting for R2
Process P2 holds Resource R2, waiting for R1
→ P1 and P2 are deadlocked forever.

▸ FOUR NECESSARY CONDITIONS (COFFMAN CONDITIONS)

ALL four conditions must hold simultaneously for a deadlock to occur. Preventing even ONE prevents deadlock.

1. Mutual Exclusion: At least one resource must be non-shareable — only one process can use it at a time. If another
process requests it, it must wait.

2. Hold and Wait: A process must be holding at least one resource AND waiting to acquire additional resources that are
currently held by other processes.

3. No Preemption: Resources cannot be forcibly taken away from a process. A resource can only be released
voluntarily by the process holding it, after it has completed its task.

4. Circular Wait: There must exist a circular chain of two or more processes: P1 → P2 → P3 → … → Pn → P1, where each
Pi is waiting for a resource held by P(i+1).

▾
Q7(b) Define different types of resource allocation graphs. 3 Marks

A Resource Allocation Graph (RAG) is a directed graph used to describe the state of resource allocation and detect
deadlocks.

▸ COMPONENTS

Vertices: Two types — Processes (circles: P1, P2...) and Resources (rectangles: R1, R2...)

Request Edge (P → R): Process P is requesting resource R (drawn as arrow from process to resource)

Assignment Edge (R → P): Resource R has been allocated to process P (drawn as arrow from resource to process)

▸ TYPES / INTERPRETATIONS

No cycle in RAG: No deadlock — system is safe.

Cycle + single instance per resource: Deadlock definitely exists.

Cycle + multiple instances per resource: Deadlock may or may not exist — need further analysis.

Wait-For Graph (WFG): A simplified version of RAG with only process nodes. An edge Pi → Pj means Pi is waiting for
a resource held by Pj. If WFG has a cycle → deadlock exists.

▾
Q7(c) What is the meaning of the term busy waiting? 2 Marks

See Q3(c) above — Busy waiting is when a process repeatedly checks a condition in a tight loop while waiting,
consuming CPU cycles without doing useful work.

▾
Q8(a) Explain paging in detail. Describe how logical address is converted into physical address. 5 Marks

▸ PAGING — CONCEPT

Paging is a memory management technique that eliminates external fragmentation by dividing memory into fixed-size
units:

Physical memory is divided into fixed-size blocks called frames

Logical memory (process address space) is divided into same-size blocks called pages

When a process is loaded, its pages can be placed in any available frames — they do NOT need to be contiguous in
physical memory

The OS maintains a Page Table per process that maps each page number to its frame number

▸ LOGICAL TO PHYSICAL ADDRESS TRANSLATION

Logical Address = [ Page Number (p) | Page Offset (d) ]

upper bits lower bits

Page size = 2^n bytes → offset uses n bits

Remaining bits = page number bits

Translation Steps:
1. CPU generates logical address → extract p and d
2. Use p to index into the Page Table → get frame number f
3. Physical Address = f × (page size) + d

Diagram:
Logical Address Page Table Physical Address
┌──────┬──────┐ ┌───┬───┐ ┌──────┬──────┐
│ p │ d │ → page[p] → │ p │ f │ ──────► │ f │ d │
└──────┴──────┘ └───┴───┘ └──────┴──────┘

▸ WORKED EXAMPLE

Given: Page size = 4 KB = 4096 bytes = 2^12

So: offset = 12 bits, remaining bits = page number

Logical address: 0x2100 = page 2, offset 256

Page Table:
Page 0 → Frame 3
Page 1 → Frame 7
Page 2 → Frame 5 ← look up page 2
Page 3 → Frame 1

Physical Address = Frame 5 × 4096 + 256

= 20480 + 256 = 20736 = 0x5100 ✓

▸ ADVANTAGES & DISADVANTAGES

✅ Eliminates external fragmentation

✅ Process doesn't need contiguous physical memory
✅ Easy to implement virtual memory
❌ Internal fragmentation (last page may not be full)
❌ Page table overhead (extra memory + access time)

▾
Q8(b) What are requirements of memory management? Explain segmentation with example. 5 Marks

▸ REQUIREMENTS OF MEMORY MANAGEMENT

Relocation: A program may be loaded into different memory locations each time. The OS must be able to run the
program regardless of where it is placed in memory.

Protection: Each process must be protected from interference by other processes. No process should be able to
access another process's memory without permission.

Sharing: Some memory regions (shared libraries, shared memory IPC) should be accessible by multiple processes
simultaneously.

Logical Organisation: Programs are written as logical units (modules, procedures). Memory management should
reflect this logical structure.

Physical Organisation: The system must manage the flow of information between main memory (RAM) and
secondary storage (disk) efficiently.

▸ SEGMENTATION

Segmentation is a memory management scheme that supports the programmer's view of memory. A process is
divided into variable-length segments, each representing a logical unit (code, data, stack, heap, etc.).

Logical Address = [ Segment Number (s) | Offset (d) ]

Segment Table entry for each segment:

{ Base (starting physical address), Limit (maximum size) }

Translation:
1. Extract s and d from logical address
2. Look up segment s in Segment Table → get Base and Limit
3. If d >= Limit → ADDRESSING ERROR (protection violation)
4. Physical Address = Base + d

▸ EXAMPLE

Segment Table:
Seg 0 (code): Base = 1000, Limit = 600
Seg 1 (data): Base = 2500, Limit = 400
Seg 2 (stack): Base = 9000, Limit = 500

Logical Address (1, 100):

s=1, d=100. Limit=400. 100 < 400 ✓
Physical = 2500 + 100 = 2600 ✓

Logical Address (0, 650):

s=0, d=650. Limit=600. 650 >= 600 ✗ → TRAP (Segmentation Fault!)

Segmentation can cause external fragmentation since segments are variable-sized. It provides better protection and
sharing than paging because segments have meaningful boundaries.
 PAPER 1 PAPER 2 PAPER 3

OPERATING SYSTEMS · COMPLETE SOLUTIONS

Question Paper 2
Every question solved in full detail · All questions open by default

SECTION A — SHORT QUESTIONS

▾
Q1(a) What is an Operating system? Discuss the functions of operating system. 3 Marks

An Operating System (OS) is system software that manages hardware and software resources and provides services to
application programs. It acts as an intermediary between users and hardware.

▸ FUNCTIONS OF AN OPERATING SYSTEM

Process Management: Creates, schedules, and terminates processes. Handles CPU scheduling, context switching,
process synchronization.

Memory Management: Allocates and deallocates memory. Manages paging, segmentation, virtual memory.

File System Management: Creates/deletes files and directories. Controls read/write permissions. Manages disk
space.

Device Management: Controls I/O devices through device drivers. Manages device queues and buffering.

Security & Protection: Protects system resources from unauthorized access. Enforces access control policies.

User Interface: Provides CLI (terminal) or GUI (desktop environment) for user interaction.

Networking: Manages network protocols, connections, and data transfer between systems.

Error Detection & Handling: Detects hardware/software errors and takes corrective action.

▾
Q1(b) What is the difference between multiprogramming and multiprocessing? 3 Marks

ASPECT MULTIPROGRAMMING MULTIPROCESSING

Multiple programs kept in memory

Multiple CPUs/cores executing
Definition simultaneously; CPU switches when one waits
different processes simultaneously
for I/O

CPUs Single CPU Multiple CPUs

Execution Concurrent (interleaved — appears parallel) Truly parallel (at the same instant)

Increase throughput via real

Goal Keep CPU busy, maximize utilization
parallelism

Memory Multiple programs in RAM Shared or distributed memory

Old single-core computers running multiple Modern multi-core CPUs, server

Example
apps clusters

In multiprogramming, only ONE process runs at a time but the CPU rapidly switches. In multiprocessing, MULTIPLE
processes run at the exact same instant on different CPUs.

▾
Q1(c) What is fragmentation? How many types of fragmentation occur in Operating System? 4 Marks

▸ DEFINITION

Fragmentation is the phenomenon of wasted memory space that cannot be utilised effectively, even though enough
total free memory exists to satisfy a request.

▸ TYPES OF FRAGMENTATION

External Fragmentation: Total free memory is sufficient, but it is scattered in small non-contiguous holes throughout
memory. A large process cannot be loaded because no single hole is big enough, even though the total free space
would fit it.

Memory: [P1:10KB][FREE:5KB][P2:8KB][FREE:3KB][P3:6KB][FREE:5KB]
Process needs 12KB → Total free = 13KB but no single block is 12KB!
Solution: Compaction (shuffle processes to merge free space)

Occurs in: Variable-size partition allocation, Segmentation.

Internal Fragmentation: Memory allocated to a process is slightly larger than what the process actually needs. The
unused space inside the allocated block is wasted.

Process needs 18KB → Allocated 20KB (fixed block size)

Internal fragmentation = 20 - 18 = 2KB wasted inside the block

Occurs in: Fixed-size partition, Paging (last page may be partially filled).

FEATURE EXTERNAL FRAGMENTATION INTERNAL FRAGMENTATION

Location Between allocated blocks (outside) Within an allocated block (inside)

Cause Variable-size allocation Fixed-size allocation

Solution Compaction, Paging Smaller block sizes

▾
Q2(a) Explain the situation when the CPU switches from a process to another process. 3 Marks

▸ CONTEXT SWITCH

This situation is called a Context Switch. The OS saves the complete state of the current process and loads the state of
another process.

▸ WHEN DOES IT OCCUR?

Process's time quantum expires (preemption by timer interrupt)

Process requests I/O (goes from Running → Waiting)

A higher-priority process becomes ready (preemption)

Process calls yield() voluntarily

Process terminates

▸ STEPS DURING CONTEXT SWITCH

Step 1: Save state of Process A into A's PCB

(save PC, registers, stack pointer, memory maps)
Step 2: Update A's state (Running → Ready or Waiting)
Step 3: Scheduler selects Process B to run next
Step 4: Load state of Process B from B's PCB into CPU
(restore PC, registers, stack pointer)
Step 5: Update B's state (Ready → Running)
Step 6: Resume execution of B

Context switch is pure overhead — NO useful work is done during the switch. Modern OS minimizes switch time using
hardware support.

▾
Q2(b) Define turnaround time, waiting time and response time. 3 Marks

Turnaround Time (TAT): The total time from when a process is submitted to when it completes. It includes: waiting in
ready queue + execution time + I/O time.
Formula: TAT = Completion Time − Arrival Time
Goal: Minimize TAT

Waiting Time (WT): Total time a process spends waiting in the ready queue (not executing, not doing I/O). Pure
waiting time for CPU.
Formula: WT = TAT − Burst Time or WT = Start Time − Arrival Time
Goal: Minimize WT

Response Time: Time from process submission until the first response is produced. In interactive systems, this is the
time until the user sees the first output.
Formula: Response Time = First CPU Time − Arrival Time
Goal: Minimize Response Time (especially for interactive systems)

TAT ≥ Response Time ≥ WT. A process can have good response time but poor turnaround time (e.g., in Round Robin).

▾
Q2(c) Briefly write the direct and indirect method for inter process communication. 4 Marks

▸ DIRECT COMMUNICATION

Processes must name each other explicitly to communicate. The sender specifies who to send to, and the receiver
specifies who to receive from.

send(P, message) — send message directly to process P

receive(Q, message) — receive message from process Q

A link is established automatically between each communicating pair

Exactly one link per pair of processes

Link is usually bidirectional

Disadvantage: Hard-coded process IDs reduce modularity

▸ INDIRECT COMMUNICATION

Messages are sent to and received from mailboxes (ports). Processes communicate through a shared mailbox without
knowing each other directly.

send(mailbox_A, message) — send to mailbox A

receive(mailbox_A, message) — receive from mailbox A

A link exists only if both processes share a mailbox

Multiple processes can share one mailbox

One pair of processes can have multiple links (via different mailboxes)

Mailbox can be owned by the OS (persistent) or a process (dies with process)

Advantage: Flexible — easy to connect many processes

▾
Q3(a) Why are process control blocks important? 2 Marks

PCBs are fundamentally important because they are the foundation of multitasking. Here's why:

Enable Context Switching: The PCB stores all CPU registers, PC, and state so a process can be paused and resumed
perfectly — making multitasking possible.

Process Identification: Each PCB contains a unique PID, allowing the OS to track and manage individual processes.

Scheduling: PCBs contain scheduling information (priority, queue pointers) that the scheduler uses to decide which
process runs next.

Resource Tracking: PCBs store memory allocation info, open file descriptors, and I/O device assignments — the OS
knows exactly what each process owns.

Protection & Isolation: Each process has its own PCB with separate memory mappings, ensuring processes don't
interfere with each other.

Without PCBs, the OS could not pause a process, save its state, and resume it later — multitasking would be
impossible.

▾
Q3(b) Define context switch. How is a PCB used in context switching? 4 Marks

▸ CONTEXT SWITCH DEFINITION

A Context Switch is the process of saving the state (context) of a currently executing process into its PCB and loading
the saved state of another process from its PCB so that the CPU can execute it. It enables multiple processes to share
a single CPU.

▸ HOW PCB IS USED IN CONTEXT SWITCHING

PROCESS A running...
│
│ ← interrupt/trap occurs
▼
OS saves A's context into A's PCB:
[Link] = current program counter
[Link] = all CPU registers (AX,BX,SP,flags...)
[Link] = "Ready" or "Waiting"
│
▼
Scheduler selects Process B
│
▼
OS loads B's context from B's PCB:
[Link] ← [Link]
[Link] ← [Link]
[Link] = "Running"
│
▼
PROCESS B resumes from exactly where it left off

The PCB acts like a snapshot or bookmark — it captures the exact state of a process so it can be perfectly restored
later.

▾
Q3(c) Define different types of resource allocation graphs. 4 Marks

▸ RESOURCE ALLOCATION GRAPH (RAG)

A Resource Allocation Graph is a directed graph that represents the state of resource allocation in a system and helps
detect deadlocks.

Components:

Process nodes (circles): P1, P2, P3... represent processes

Resource nodes (rectangles): R1, R2... represent resource types. Dots inside = instances of that resource.

Request Edge P→R: Process P is requesting an instance of resource R (arrow from process to resource)

Assignment Edge R→P: An instance of resource R is assigned to process P (arrow from resource to process)

(P1) ──request──► [R1] ← P1 wants R1

(P2) ◄──assign─── [R1] ← R1 is given to P2

▸ DEADLOCK DETECTION USING RAG

No cycle in RAG: No deadlock possible. System is safe.

Cycle + single instance per resource type: Deadlock definitely exists. The cycle itself is the deadlock.

Cycle + multiple instances per resource type: Deadlock may or may not exist. Need to check further (e.g., Banker's
algorithm).

▸ WAIT-FOR GRAPH (WFG)

A simplified version of RAG for single-instance resources. Resource nodes are removed. Edge Pi→Pj means Pi is waiting
for Pj to release a resource. If WFG has a cycle → deadlock exists.

▾
Q4(a) What do you mean by a process? 2 Marks

A process is a program in execution. It is the basic unit of work in an OS. Unlike a program (which is a passive entity
stored on disk), a process is an active entity with resources allocated to it.

A process consists of:

Text section: The program code (executable instructions)

Data section: Global and static variables

Heap: Memory dynamically allocated at runtime (malloc, new)

Stack: Temporary data — function parameters, return addresses, local variables

Program Counter (PC): Points to the next instruction to execute

CPU Registers: Current working values

Process State: Current state (New/Ready/Running/Waiting/Terminated)

▾
Q4(b) What are the different states of a process? 4 Marks

New: The process is being created. PCB is allocated. Program code is being loaded. Process is admitted into the
ready queue by the long-term scheduler.

Ready: The process is in memory, loaded and ready to run. It is waiting in the ready queue for the CPU scheduler to
dispatch it. Everything is ready except the CPU itself.

Running: The process is currently executing on the CPU. Instructions are being carried out. Only ONE process per
CPU can be in this state at a time.

Waiting (Blocked): The process cannot continue until some event occurs — e.g., I/O operation completes, a
semaphore is signaled, a child process finishes. The CPU is released and given to another process.

Terminated: The process has finished execution (called exit() or was killed). Resources are released. The PCB may
remain briefly (zombie state) until the parent process reads the exit status.

New ──► Ready ──dispatch──► Running ──exit──► Terminated

▲ │ │
│ interrupt │ │ I/O wait
└────────────────────┘ ▼
Waiting
│ I/O done
└──► Ready

▾
Q4(c) What is the difference between micro kernel and macro kernel? 4 Marks

FEATURE MICRO KERNEL MACRO (MONOLITHIC) KERNEL

Only essential services in kernel All OS services in one large kernel

Architecture
(IPC, basic scheduling, memory) (files, drivers, networking, etc.)

Most services run as user-space server

User space Everything runs in kernel space
processes

Size Small, minimal kernel Large, complex kernel

Slower — services communicate via Faster — direct function calls between

Speed
message passing (IPC overhead) components

More reliable — a crashed server Less reliable — a bug in any module can
Reliability
doesn't bring down the kernel crash the whole OS

Portability More portable and extensible Harder to port, harder to extend

Examples Minix, QNX, L4, macOS (partially) Linux, Unix, Windows (early versions)

Micro Kernel: Monolithic Kernel:

┌──────────────────────┐ ┌──────────────────────┐
│ File Server (user) │ │ │
│ Device Driver (user) │ │ File System │
│ Network Server (user)│ │ Device Drivers │
├──────────────────────┤ │ Network Stack │
│ Micro Kernel │ │ Memory Management │
│ (IPC, basic sched, │ │ Process Scheduling │
│ basic memory) │ │ All in KERNEL space │
└──────────────────────┘ └──────────────────────┘

SECTION B — LONG QUESTIONS

▾
Q5(a) What do you mean by deadlock? Explain the necessary conditions for deadlock. 3 Marks

▸ DEADLOCK

A deadlock is a state where a set of processes are permanently blocked — each process is waiting for a resource held
by another process in the same set. No process can proceed forward.

▸ FOUR NECESSARY CONDITIONS (ALL MUST HOLD SIMULTANEOUSLY)

1. Mutual Exclusion: At least one resource type must be non-shareable. Only one process can use it at a time. If
another process needs it, it must wait.

2. Hold and Wait: A process must currently be holding at least one resource while waiting to acquire additional
resources that are currently held by other processes.

3. No Preemption: Once a resource is allocated, it cannot be forcibly taken from the process. Resources can only be
released voluntarily by the holding process after it finishes using them.

4. Circular Wait: A circular chain exists: P1 waits for P2, P2 waits for P3, ..., Pn waits for P1. Each process is waiting for a
resource held by the next one in the chain.

Preventing even ONE of these four conditions prevents deadlock. This is the basis of deadlock prevention algorithms.

▾
Q5(b) Describe and explain with an example the Banker's algorithm for deadlock avoidance. 5 Marks

▸ BANKER'S ALGORITHM — CONCEPT

The Banker's Algorithm (by Dijkstra) is a deadlock avoidance algorithm. Before granting any resource request, it checks
whether granting it would leave the system in a safe state. If safe, the request is granted; if not, the process must wait.

A safe state = a sequence (safe sequence) exists where all processes can complete in some order, each getting all
resources it needs.

▸ DATA STRUCTURES

n = number of processes, m = number of resource types

Available[m] — number of available instances of each resource type

Max[n][m] — maximum demand of each process for each resource
Allocation[n][m] — resources currently allocated to each process
Need[n][m] — remaining need = Max[i][j] - Allocation[i][j]

▸ SAFETY ALGORITHM

1. Work = Available (copy)

Finish[i] = false for all i

2. Find i such that:

Finish[i] == false AND Need[i] ≤ Work (element-wise)

3. If found:
Work = Work + Allocation[i] (process finishes, releases resources)
Finish[i] = true
Go to step 2

4. If all Finish[i] == true → SAFE STATE ✓

Otherwise → UNSAFE STATE (potential deadlock)

▸ WORKED EXAMPLE (3 PROCESSES, 3 RESOURCE TYPES A, B, C)

PROCESS ALLOCATION A,B,C MAX A,B,C NEED A,B,C

P0 0,1,0 7,5,3 7,4,3

P1 2,0,0 3,2,2 1,2,2

P2 3,0,2 9,0,2 6,0,0

P3 2,1,1 2,2,2 0,1,1

P4 0,0,2 4,3,3 4,3,1

Available = [3, 3, 2] (A=3, B=3, C=2)

Run Safety Algorithm:

Work = [3,3,2]

Find process where Need ≤ Work:

P0 needs [7,4,3] > [3,3,2] ✗
P1 needs [1,2,2] ≤ [3,3,2] ✓ → P1 runs, Work = [3,3,2]+[2,0,0] = [5,3,2]
P3 needs [0,1,1] ≤ [5,3,2] ✓ → P3 runs, Work = [5,3,2]+[2,1,1] = [7,4,3]
P4 needs [4,3,1] ≤ [7,4,3] ✓ → P4 runs, Work = [7,4,3]+[0,0,2] = [7,4,5]
P0 needs [7,4,3] ≤ [7,4,5] ✓ → P0 runs, Work = [7,4,5]+[0,1,0] = [7,5,5]
P2 needs [6,0,0] ≤ [7,5,5] ✓ → P2 runs

Safe Sequence: P1 → P3 → P4 → P0 → P2 ✓ SAFE STATE

▾
Q5(c) What is demand paging? 2 Marks

Demand Paging is a virtual memory management strategy where a page is only loaded into physical memory (RAM)
when it is actually needed (demanded), rather than loading the entire process at startup.

How it works:

1. Process starts with NO pages in memory (or only a few)

2. When CPU references a page not in RAM → Page Fault occurs

3. OS finds the page on disk, loads it into a free frame in RAM

4. Updates page table to mark the page as "in memory"

5. Resumes the process — it re-executes the faulting instruction

✅ Less I/O — only needed pages are loaded

✅ Less memory required per process — more processes fit in RAM
✅ Allows programs larger than physical RAM to execute
❌ Page faults cause delay (disk access is slow)

▾
Q6(a) What is semaphore? What is the purpose of binary semaphore? 3 Marks

▸ SEMAPHORE

A semaphore is a synchronization tool — an integer variable that controls access to shared resources in concurrent
programming. It can only be accessed through two atomic operations: wait() (P) and signal() (V).

wait(S): signal(S):
S--; S++;
if S < 0: if S <= 0:
block() wakeup()

▸ BINARY SEMAPHORE (MUTEX)

A binary semaphore can only have values 0 or 1. Its purpose is mutual exclusion (mutex) — ensuring that only one
process can be in a critical section at any time.

mutex = 1 (initialized — resource is free)

Process wanting to enter critical section:

wait(mutex) → mutex = 0 (locked)
// critical section — only ONE process here
signal(mutex) → mutex = 1 (unlocked)

If another process calls wait(mutex) while mutex=0:

→ it blocks until signal() is called (unlocked)

▾
Q6(b) What is starvation in Operating System? 3 Marks

Starvation (also called indefinite postponement) is a situation where a process is perpetually denied the resources it
needs and can never make progress, even though the system is not deadlocked and other processes are making
progress.

▸ WHEN DOES STARVATION OCCUR?

In priority scheduling: If a continuous stream of high-priority processes keeps arriving, low-priority processes never
get CPU time.

In SJF scheduling: Long processes starve if short ones keep arriving.

In resource allocation: A process keeps being denied access because other processes always get priority.

▸ DIFFERENCE FROM DEADLOCK

STARVATION DEADLOCK

Some processes run (system makes progress) No process can run (system stuck)

Starved process is just unlucky/low priority All processes in deadlock are blocked

Solved by Aging Solved by prevention/detection/recovery

Solution — Aging: Gradually increase the priority of processes that have been waiting for a long time, ensuring they
eventually get scheduled.

▾
Q6(c) What are the advantages of multithreaded programming? 4 Marks

Responsiveness: A multithreaded process remains responsive even if part of it is blocked. E.g., a web browser can
download a file in one thread while another thread handles user clicks.

Resource Sharing: Threads share the code, data, and open files of their parent process automatically. This is more
efficient than having separate processes communicate via IPC.

Economy: Creating threads is much cheaper than creating processes (no full address space copy). Context
switching between threads of the same process is also faster.

Scalability / Parallelism: In multiprocessor systems, different threads can run on different cores simultaneously,
dramatically speeding up computation-heavy tasks.

Better CPU Utilisation: When one thread is waiting for I/O, another thread of the same process can use the CPU,
reducing idle time.

Simplified Program Structure: Programs that do multiple things at once (e.g., server handling multiple clients) are
easier to write as multiple threads than as complex single-threaded programs.

▾
Q7(a) Explain logical address and physical address. 3 Marks

Logical Address (Virtual Address): The address generated by the CPU during execution. The user program works
with logical addresses only. Each process has its own logical address space starting from 0, independent of other
processes.

Physical Address: The actual address in the main memory (RAM). The memory controller uses this to physically
access the memory cell. The user program never sees physical addresses directly.

CPU → generates logical address 0x4500

│
▼
MMU (Memory Management Unit)
uses page table to translate
│
▼
Physical address 0xB500 → goes to RAM

PROPERTY LOGICAL ADDRESS PHYSICAL ADDRESS

Generated by CPU during execution MMU via translation

Seen by User program Memory hardware only

Range 0 to max logical (per process) 0 to physical RAM size

Uniqueness Same across processes (each starts at 0) Always unique in RAM

▾
Q7(b) What do you mean by virtual memory technique? What are the advantages of it? 4 Marks

▸ VIRTUAL MEMORY

Virtual Memory is a memory management technique that gives the illusion to each process that it has access to a
large, private memory space (virtual address space), even if physical RAM is limited. The OS uses a combination of RAM
and disk (swap space) to implement this illusion.

Process sees: [0 ─────────────────── Virtual Address Space ── max]

↕ (some pages in RAM, rest on disk)
Physical RAM: [Frame 0][Frame 1][Frame 2]...[Frame n]
Disk (Swap): [Page A][Page B][Page C]...[excess pages]

When a process accesses a page not in RAM → Page Fault → OS loads it from disk.

▸ ADVANTAGES

Run large programs: A process can be much larger than physical RAM. Only the needed pages are in RAM at any
time.

More processes in memory: Since each process uses only a fraction of its virtual space in RAM, more processes fit
simultaneously → better CPU utilization.

Memory isolation: Each process has its own virtual address space → processes are protected from each other.

Shared memory: Different processes can map the same physical pages (e.g., shared libraries like libc) to their own
virtual addresses → saves memory.

Simplified programming: Programmers don't need to worry about physical memory constraints. Each program sees
a large, contiguous address space.

▾
Q7(c) LRU Page Replacement — Frame size 3. String: 5 0 1 2 0 3 0 4 1 2 0 3 2 1 2 0 1 3 Marks

▸ LRU — LEAST RECENTLY USED ALGORITHM

In LRU, when a page fault occurs and all frames are full, the page that was least recently used (longest time since last
access) is replaced.

▸ STEP-BY-STEP TRACE (FRAMES = 3)

REF FRAME 1 FRAME 2 FRAME 3 PAGE FAULT? EVICTED

5 5 - - YES -

0 5 0 - YES -

1 5 0 1 YES -

2 2 0 1 YES 5 (LRU)

0 2 0 1 no -

3 2 0 3 YES 1 (LRU)

0 2 0 3 no -

4 4 0 3 YES 2 (LRU)

1 4 1 3 YES 0 (LRU)

2 4 1 2 YES 3 (LRU)

0 0 1 2 YES 4 (LRU)

3 0 3 2 YES 1 (LRU)

Total Page Faults = 10

Hit count = 2 (references to 0 at position 5, and 0 at position 7)
Page Fault Rate = 10/12 = 83.3%

▾
Q8(a) Briefly explain how a system can be recovered from a deadlock. 3 Marks

▸ DEADLOCK RECOVERY METHODS

Once a deadlock is detected, the system can recover by two main approaches:

▸ 1. PROCESS TERMINATION

Abort all deadlocked processes: Simple and effective but expensive — all work done by those processes is lost.

Abort one process at a time: Kill one process, check if deadlock is resolved, repeat if needed. Choose victim by
minimum cost:
Process priority (kill lowest priority first)

How long process has run (kill youngest first)

How many resources it holds

How many more resources it needs

▸ 2. RESOURCE PREEMPTION

Forcibly take resources from some processes (victims) and give them to others.

Rollback: The victim process must be rolled back to a safe state (checkpoint) and restarted later.

Starvation concern: Must ensure the same process is not always chosen as victim. Solution: include number of
rollbacks as a cost factor.

▾
Q8(b) Priority Scheduling — same table as before. Calculate WT, TAT, Avg WT, Avg TAT. 4 Marks

This is the same scheduling problem as Paper 1 Q5(b). Full solution below:

PROCESS AT BT PRIORITY CT TAT WT

P0 7 7 3 30 23 16

P1 3 8 1 11 8 0

P2 6 12 2 23 17 5

Average Waiting Time = (16 + 0 + 5) / 3 = 7.00 ms

Average Turnaround Time = (23 + 8 + 17) / 3 = 16.00 ms

▾
Q8(c) Describe the process of starting a computer system (Boot Process). 3 Marks

BOOT PROCESS (Bootstrapping):

Step 1: POWER ON
CPU resets, mode bit = kernel mode
CPU starts executing from a fixed ROM address

Step 2: BIOS / UEFI (Basic Input/Output System)

POST = Power-On Self Test
Checks RAM, CPU, keyboard, disk, etc.
Locates a bootable device (disk, USB, network)

Step 3: BOOTLOADER
BIOS loads the Master Boot Record (MBR) / EFI partition
into memory and executes it.
Bootloader (e.g., GRUB, Windows Boot Manager) loads
the OS kernel from disk into RAM.

Step 4: KERNEL INITIALIZATION

OS kernel starts executing
Initializes: memory management, CPU scheduler,
device drivers, file systems, network
Mounts the root file system

Step 5: INIT PROCESS

Kernel starts the first user-space process:
init (Unix/Linux) or systemd (modern Linux)
This process (PID=1) starts all system services

Step 6: SYSTEM READY

Login screen / desktop environment appears
System is ready for user interaction
 PAPER 1 PAPER 2 PAPER 3

OPERATING SYSTEMS · COMPLETE SOLUTIONS

Question Paper 3
Every question solved in full detail · All questions open by default

SECTION A — SHORT QUESTIONS

▾
Q1(a) What is an Operating system? Discuss the functions of operating system. 4 Marks

An Operating System (OS) is system software that acts as an intermediary between users/application programs and
computer hardware. It manages hardware resources and provides a platform for applications to run.

▸ FUNCTIONS

Process Management: Creates, schedules (CPU scheduling), synchronizes, and terminates processes. Handles
context switching.

Memory Management: Tracks memory usage, allocates memory to processes, implements

paging/segmentation/virtual memory.

File System Management: Creates/reads/writes/deletes files and directories. Manages disk space and file
permissions.

Device Management: Manages I/O devices through device drivers. Handles device queues, buffering, and caching.

Security & Protection: Authentication, access control — ensures only authorized users/processes access resources.

Error Handling: Detects CPU errors, memory errors, I/O errors and takes corrective action.

User Interface: Provides CLI (terminal/shell) or GUI (desktop) for users to interact with the system.

Networking: Manages network protocols, sockets, and communication between computers.

▾
Q1(b) Relationship between OS and hardware. What is the difference between a Job and a Process? 3 Marks

▸ OS AND HARDWARE RELATIONSHIP

The OS is the resource manager and abstraction layer between hardware and software:

The OS communicates with hardware through device drivers (software that knows how to control specific
hardware).

The OS responds to hardware events via interrupts — hardware signals the CPU when ready.

The OS uses privileged instructions (in kernel mode) to control hardware: managing memory protection registers,
setting up interrupt vectors, performing direct I/O.

Hardware provides the OS with protection mechanisms: the mode bit (user/kernel mode), memory protection
(MMU), and timers to prevent any one process from monopolizing the CPU.

▸ JOB VS PROCESS

JOB PROCESS

Program submitted for execution (static) Program in execution (dynamic)

Passive entity — exists on disk Active entity — loaded in memory, has resources

No CPU register state Has PC, registers, stack, heap, state

Exists before OS processes it Created by OS when job is loaded and started

▾
Q1(c) What do you understand about user mode and kernel mode of operations? 2 Marks

Modern CPUs support at least two modes of operation, controlled by a hardware mode bit:

User Mode (mode bit = 1): Restricted mode. User applications run here. Cannot execute privileged instructions (like
direct I/O, changing interrupt handlers, or modifying memory protection). If a user program tries to execute a
privileged instruction, the CPU generates a trap to the OS.

Kernel Mode (mode bit = 0): Privileged mode. OS kernel runs here. All instructions are allowed. Has direct access to
all hardware.

User Mode: Application code, library code

restricted — cannot harm OS or other processes

Kernel Mode: OS kernel code

unrestricted — full hardware control

Transition: User→Kernel via system call (trap instruction)

Kernel→User via return from system call

Dual mode is the fundamental protection mechanism that prevents user programs from accidentally or maliciously
crashing the OS.

▾
Q2(a) Define process. Draw the process state diagram and explain it. 5 Marks

▸ PROCESS DEFINITION

A process is a program in execution. It is an active entity that includes the program code, current activity (program
counter), CPU registers, stack (local variables/return addresses), data section (global variables), and heap (dynamically
allocated memory).

▸ PROCESS STATE DIAGRAM

admitted by
┌───────┐ long-term scheduler ┌───────┐
│ NEW │ ───────────────────► │ READY │
└───────┘ └───┬───┘
│ ▲
dispatch │ │ interrupt/
│ │ preemption
▼ │
┌──────────┐ ────exit────► ┌────────────┐
│ RUNNING │ │ TERMINATED │
└──────────┘ └────────────┘
│
│ I/O request /
│ wait for event
▼
┌──────────┐
│ WAITING │
└──────────┘
│ I/O complete /
│ event occurred
▼
back to READY

▸ STATE EXPLANATIONS

New: Process is being created. PCB allocated. Program loaded from disk. Admitted to ready queue by long-term
scheduler.

Ready: Process is in memory, ready to execute, waiting in ready queue for CPU. All resources are available except
CPU.

Running: Process is actively executing on CPU. Program counter is advancing. Only ONE per CPU at any instant.

Waiting (Blocked): Process cannot proceed — waiting for I/O to complete, a resource to become available, or a
signal. CPU given to another process.

Terminated: Process finished or killed. Resources released. PCB removed after parent reads exit status.

▾
Q2(b) What do you mean by thread? Is there any advantage of thread over process? 3 Marks

A thread is the smallest unit of CPU execution within a process. A process can have multiple threads (multithreading).
Threads within the same process share code, data, and files but each has its own stack, registers, and program counter.

▸ ADVANTAGES OF THREADS OVER PROCESSES

ADVANTAGE DETAIL

Faster creation No need to duplicate address space; thread creation is 10-100× faster

Cheaper context switch Memory mapping stays the same; only registers/stack change

Less memory Threads share process memory; no separate address space

Direct communication Threads communicate via shared memory without IPC overhead

Better CPU utilization One thread can use CPU while another does I/O in same process

True parallelism Different threads can run on different CPU cores simultaneously

▾
Q2(c) Explain the following allocation algorithms: a) Best fit b) Worst fit 2 Marks

▸ BEST FIT

Allocates the smallest hole that is large enough to satisfy the request. The system searches all free holes and picks the
one closest in size to the requested amount.

Free holes: [100KB] [500KB] [200KB] [300KB]

Request: 180KB
Best Fit: Picks 200KB hole (smallest that fits 180KB)
Leftover: 20KB fragment (small — may be unusable)

✅ Minimises wasted space per allocation

❌ Slow — must scan all holes every time
❌ Leaves many tiny, unusable fragments
▸ WORST FIT

Allocates from the largest available hole. The idea is that the large leftover fragment will be useful for future allocations.

Free holes: [100KB] [500KB] [200KB] [300KB]

Request: 180KB
Worst Fit: Picks 500KB hole (largest)
Leftover: 320KB fragment (large — more likely to be reused)

✅ Leaves larger fragments that can be reused

❌ Slow — must scan all holes every time
❌ Generally performs poorly in practice
❌ The largest holes are quickly consumed

▾
Q3(a) Explain the situation when the CPU switches from a process to another process. 3 Marks

This is called a Context Switch. The OS saves the current process's state and loads another's. It occurs when:

Time quantum expires (timer interrupt — preemptive scheduling)

Process requests I/O (Running → Waiting)

Higher priority process becomes ready

Process terminates

P1 Running...
↓ (interrupt)
OS saves P1's state into P1's PCB:
[Link] = {PC, registers, state="Ready", ...}

Scheduler selects P2

OS loads P2's state from P2's PCB:

CPU ← [Link]
CPU ← [Link]
[Link] = "Running"

P2 Running...

Context switch time is pure overhead — during the switch, no useful user process code is running.

▾
Q3(b) Define turnaround time, waiting time, and response time. 3 Marks

Turnaround Time (TAT): Total elapsed time from process submission to process completion. Includes time spent
waiting + executing + doing I/O. Formula: TAT = Completion Time − Arrival Time

Waiting Time (WT): Total time the process spends waiting in the ready queue (not using CPU, not doing I/O). Formula:
WT = TAT − Burst Time or WT = Start Time − Arrival Time

Response Time: Time from request submission until the first response is produced. Important for interactive
systems. Formula: Response Time = First CPU Start − Arrival Time

Goal of scheduling: Maximize throughput and CPU utilization, Minimize TAT, WT, and Response Time.

▾
Q3(c) Briefly write the direct and indirect method for inter process communication. 4 Marks

▸ DIRECT COMMUNICATION

Communicating processes must explicitly name each other. API: send(P, msg) and receive(Q, msg). A single
bidirectional link automatically exists between each pair. Simple but tightly coupled — changing process names
requires updating all references.

▸ INDIRECT COMMUNICATION

Messages pass through mailboxes (ports) shared between processes. API: send(mailbox, msg) and
receive(mailbox, msg). More flexible — many processes can share a mailbox, multiple links can exist. Mailbox can
persist beyond a single process's lifetime if OS-owned.

▾
Q4(a) Explain the criteria for comparing CPU scheduling algorithms. 3 Marks

CPU scheduling algorithms are evaluated on these criteria:

CPU Utilization: Percentage of time CPU is busy. Range: 40% (lightly loaded) to 90% (heavily loaded). Maximize this.

Throughput: Number of processes completing per unit time. For long processes: maybe 1/hr; for short: 10/sec.
Maximize this.

Turnaround Time: Total time from submission to completion. Includes wait + execute + I/O. Minimize this.

Waiting Time: Total time spent waiting in the ready queue. The scheduler can only influence this directly. Minimize
this.

Response Time: Time from submission until first response is produced. Critical for interactive systems. Minimize this.

Fairness: Each process should get a fair share of CPU. No starvation.

No single algorithm optimizes all criteria simultaneously — there are trade-offs. FCFS minimizes overhead but has
poor response time. RR gives good response time but high context-switch overhead.

▾
Q4(b) List the factors that affect a scheduling mechanism of processes. 3 Marks

CPU Burst Length: How long a process uses the CPU before doing I/O. Short bursts → I/O-bound; long bursts →
CPU-bound. Different algorithms suit each.

Arrival Pattern: If all processes arrive at once vs. gradually — affects queue length and waiting times.

Process Priority: Higher priority processes should get CPU first in priority scheduling.

Preemption: Whether processes can be interrupted mid-execution. Preemptive algorithms (RR, SRT) give better
response time but have context-switch overhead.

I/O Behaviour: Processes alternating between CPU and I/O need different handling than pure CPU-bound processes.

Number of processes: More processes in ready queue means each waits longer; scheduler must be efficient.

Time Quantum (for RR): Too small → too many context switches; too large → degenerates to FCFS.

System type: Batch (throughput), Interactive (response time), or Real-time (deadlines) systems need different
scheduling goals.

▾
Q4(c) What is semaphore? Explain how semaphore can be implemented. 4 Marks

A semaphore is an integer synchronization variable accessed only via two atomic operations: wait() and signal(). Used
to solve critical section and synchronization problems.

▸ TYPES

Binary Semaphore (Mutex): Value 0 or 1. Used for mutual exclusion.

Counting Semaphore: Non-negative integer. Used for resource counting (controls access to N instances of a
resource).

▸ IMPLEMENTATION (WITHOUT BUSY WAITING)

struct semaphore {
int value;
queue waiting_list;
};

wait(S):
[Link]--;
if ([Link] < 0) {
add current process to S.waiting_list;
block(); // process sleeps — releases CPU
}

signal(S):
[Link]++;
if ([Link] <= 0) {
remove process P from S.waiting_list;
wakeup(P); // P moved to ready queue
}

Usage for mutual exclusion:

wait(mutex); // lock
// critical section
signal(mutex); // unlock

SECTION B — LONG QUESTIONS

▾
Q5(a) Explain the Round-Robin algorithm with an example. 6 Marks

▸ ROUND ROBIN ALGORITHM

Round Robin (RR) is a preemptive CPU scheduling algorithm designed for time-sharing systems. Each process is
assigned a fixed time interval called a time quantum (q) or time slice. The CPU is given to each process in the ready
queue for at most q milliseconds in a cyclic manner.

Key Rules:

Ready queue is treated as a circular FIFO queue

If a process's burst time ≤ q: it runs to completion, CPU is given to the next

If burst time > q: process is preempted after q ms, moved to the back of the ready queue

No process waits more than (n−1)×q time before getting CPU again (where n = processes)

▸ EXAMPLE (TIME QUANTUM = 4MS)

PROCESS ARRIVAL TIME BURST TIME

P0 0 10

P1 1 4

P2 2 6

t=0: P0 arrives → starts (P0 runs t=0 to t=4)

t=1: P1 arrives → joins ready queue
t=2: P2 arrives → joins ready queue
t=4: P0 used 4ms of its 10ms. Preempted → back of queue.
Queue: [P1, P2, P0]
P1 starts (t=4 to t=8 — P1 burst=4, exactly uses quantum)
t=8: P1 finishes. Queue: [P2, P0]
P2 starts (t=8 to t=12)
t=12: P2 used 4ms of its 6ms. Preempted → back of queue.
Queue: [P0, P2]
P0 starts (t=12 to t=16, P0 has 6ms left, uses 4ms)
t=16: P0 preempted (2ms remaining). Queue: [P2, P0]
P2 starts (t=16 to t=18, P2 has 2ms left — done)
t=18: P2 finishes. Queue: [P0]
P0 starts (t=18 to t=20, P0 has 2ms left — done)
t=20: P0 finishes.

▸ GANTT CHART

P0 P1 P2 P0 P2 P0

0 4 8 12 16 18 20

▸ RESULTS

PROCESS AT BT CT TAT = CT−AT WT = TAT−BT

P0 0 10 20 20 10

P1 1 4 8 7 3

P2 2 6 18 16 10

Average Waiting Time = (10 + 3 + 10) / 3 = 7.67 ms

Average Turnaround Time = (20 + 7 + 16) / 3 = 14.33 ms

▸ CHARACTERISTICS

✅ No starvation — every process gets CPU regularly

✅ Good response time for interactive processes
✅ Fair — all processes treated equally
❌ High context-switch overhead if quantum is too small
❌ Poor average waiting time if quantum is too large (becomes FCFS)
The ideal quantum is slightly larger than a typical CPU burst

▾
Q5(b) SJF Scheduling: P0(AT=1,BT=4), P1(AT=5,BT=8), P2(AT=6,BT=10). Calculate WT, TAT, Avg WT, Avg TAT. 4 Marks

▸ SJF — SHORTEST JOB FIRST (NON-PREEMPTIVE)

When the CPU is free, select the process with the shortest CPU burst time from the ready queue. Once started, the
process runs to completion (non-preemptive).

PROCESS ARRIVAL TIME BURST TIME

P0 1 4

P1 5 8

P2 6 10

▸ SCHEDULING TRACE

t=0: No process has arrived yet → CPU IDLE until t=1

t=1: P0 arrives (BT=4) — only process → P0 starts
t=5: P0 finishes. Ready queue: P1(BT=8) arrived at t=5
→ P1 starts immediately (only process in queue)
[P2 arrives at t=6 while P1 is running]
t=13: P1 finishes. Ready queue: P2(BT=10)
→ P2 starts
t=23: P2 finishes.

▸ GANTT CHART

IDLE P0 P1 P2

0 1 5 13 23

▸ CALCULATIONS

PROCESS AT BT START TIME CT TAT = CT−AT WT = TAT−BT

P0 1 4 1 5 4 0

P1 5 8 5 13 8 0

P2 6 10 13 23 17 7

Average Waiting Time = (0 + 0 + 7) / 3 = 2.33 ms

Average Turnaround Time = (4 + 8 + 17) / 3 = 9.67 ms

Note: In this case P1 arrived first at t=5 (before P2 at t=6) so P1 ran before P2. If P2 had also been available when P1 was
selected, SJF would pick P1 (BT=8) over P2 (BT=10) — same result.

▾
Q6(a) Why are process control blocks important? 3 Marks

PCBs are the cornerstone of OS process management. They are important because:

Enable Multitasking: The PCB stores all CPU registers and program counter so a process can be perfectly paused
and resumed, making time-sharing and multiprogramming possible.

Process Identity: Each PCB has a unique PID allowing the OS to identify, track, and manage each process individually.

Scheduling: PCBs hold priority, state, and queue pointers — the scheduler uses this to decide which process runs
next.

Resource Tracking: PCBs record what memory, open files, and I/O devices each process owns — essential for
resource management and cleanup on termination.

Protection: Each process's separate PCB and memory maps ensure processes are isolated from each other.

▾
Q6(b) Define context switch. 2 Marks

A context switch is the process of saving the execution state (context) of the currently running process into its PCB
and loading the saved state of another process from its PCB so the CPU can execute it.

The "context" includes: Program Counter, all CPU registers (general-purpose, stack pointer, flags), memory management
information (page table base register), and process state.

Context switch time is pure overhead — no user process makes progress during the switch. Hardware support (TLB
flush optimizations, hardware context save) helps minimize this overhead.

▾
Q6(c) Explain the paging system with proper examples. 5 Marks

▸ PAGING SYSTEM

Paging is a non-contiguous memory allocation technique that eliminates external fragmentation. The key idea:

Physical memory is divided into fixed-size blocks called frames

Logical memory (virtual address space) is divided into same-size blocks called pages

When a process runs, its pages are loaded into any available frames (they do NOT need to be contiguous)

The OS maintains a Page Table per process mapping: page number → frame number

▸ ADDRESS TRANSLATION

Logical Address structure:

[ Page Number (p) | Page Offset (d) ]

Steps:
1. CPU generates logical address
2. Split into page number p and offset d
3. Look up p in the Page Table → get frame number f
4. Physical Address = (f × page_size) + d

▸ EXAMPLE

Page size = 512 bytes (= 2^9 → offset = 9 bits)

Logical address space = 4 pages (p uses 2 bits)
So logical address = 11 bits total

Page Table for a process:

Page 0 → Frame 2
Page 1 → Frame 4
Page 2 → Frame 1
Page 3 → Frame 7

Logical Address = 0b01_001100000 = page=1, offset=96

Physical Address = Frame 4 × 512 + 96 = 2048 + 96 = 2144

Logical Address = 0b10_000001010 = page=2, offset=10

Physical Address = Frame 1 × 512 + 10 = 512 + 10 = 522

▸ PROCESS MEMORY LAYOUT IN PAGING

Process pages: Physical frames (can be anywhere):

[Page 0] ──────────────► [Frame 2] at addr 1024-1535
[Page 1] ──────────────► [Frame 4] at addr 2048-2559
[Page 2] ──────────────► [Frame 1] at addr 512-1023
[Page 3] ──────────────► [Frame 7] at addr 3584-4095

▸ PROS AND CONS

ADVANTAGES DISADVANTAGES

No external fragmentation Internal fragmentation in last page

Simple allocation (any free frame) Page table overhead (memory + access time)

Supports virtual memory easily Every memory access needs page table lookup

Easy to share pages between processes Large page tables for large address spaces

▾
Q7(a) Write short note about: i) Authentication ii) One Time Passwords iii) Program Threats 3 Marks

i) Authentication: The process of verifying the identity of a user or process before granting access. Types:
Something you know: password, PIN

Something you have: smart card, hardware token

Something you are: biometrics (fingerprint, retina scan)

Multi-factor authentication (MFA) combines 2+ types for stronger security.

ii) One Time Passwords (OTP): A password valid for only a single login session or transaction. After use it immediately
expires. Generated via:
Time-based (TOTP): changes every 30 seconds (Google Authenticator)

Counter-based (HOTP): increments with each use

SMS OTP: sent to registered mobile number

Prevents replay attacks — even if intercepted, the OTP cannot be reused.

iii) Program Threats: Malicious programs that exploit system vulnerabilities:

Trojan Horse: Useful-looking program that contains hidden malicious code

Virus: Self-replicating code that attaches to other programs

Worm: Self-replicating, spreads across network without human action

Logic Bomb: Dormant code that triggers when a certain condition is met

Trap Door (Back Door): Secret entry point left in code by developer

▾
Q7(b) What is Deadlock and starvation? Write down necessary conditions for deadlock. 3 Marks

▸ DEADLOCK VS STARVATION

Deadlock: A set of processes are ALL permanently blocked — each holding a resource and waiting for a resource
held by another in the set. The system is completely stuck for those processes. None can ever proceed.

Starvation: A process waits indefinitely because other processes keep being scheduled ahead of it. The system IS
making progress (other processes run), but the starved process never gets resources it needs. Caused by poor
scheduling (e.g., always preferring higher-priority processes).

DEADLOCK STARVATION

ALL processes in set are blocked ONE (or some) process waits forever

System progress halted for that group System still progresses (others run)

No process in set can ever proceed Starved process just never gets its turn

Fixed by prevention/detection/recovery Fixed by aging (raise priority over time)

▸ NECESSARY CONDITIONS FOR DEADLOCK

1. Mutual Exclusion: Resource can only be used by one process at a time.

2. Hold and Wait: Process holds a resource while waiting for more.

3. No Preemption: Resources can't be forcibly taken; must be released voluntarily.

4. Circular Wait: A circular chain P1→P2→...→Pn→P1 of waiting processes.

▾
Q7(c) Discuss deadlock detection and prevention algorithm with example. 4 Marks

▸ DEADLOCK PREVENTION

Prevent deadlock by ensuring at least one of the four Coffman conditions never holds:

Eliminate Mutual Exclusion: Make resources sharable where possible (e.g., read-only files can be shared).

Eliminate Hold & Wait:

Require a process to request ALL resources at once before starting

Or: require a process to release all current resources before requesting new ones

Allow Preemption: If a process requesting a new resource can't get it, forcibly take all its currently held resources
away. Process restarts later with all resources.

Eliminate Circular Wait: Impose a total ordering on resource types. Processes must request resources only in
increasing order. E.g., if R1 < R2 < R3, a process holding R1 can only request R2 or R3, never R1 again. This breaks
circular chains.

▸ DEADLOCK DETECTION

Allow deadlock to happen; periodically run a detection algorithm.

Single-instance resources: Use Wait-For Graph (WFG)

- Maintain a directed graph of process-wait dependencies
- If WFG has a CYCLE → deadlock exists
- Example:
P1 waits for P2, P2 waits for P3, P3 waits for P1
→ Cycle! → P1, P2, P3 are deadlocked.

Multi-instance resources: Use a variant of Banker's algorithm

- Find a sequence where all processes can complete
- If no such sequence exists → deadlock

After detection, recover by: terminating one deadlocked process at a time (checking after each) or preempting
resources from a chosen victim process.

▾
Q8(a) Discuss polling and interrupt. What is device driver and functions of device drivers? 3 Marks

▸ POLLING VS INTERRUPT

POLLING INTERRUPT

Device notifies CPU via hardware signal when

CPU continuously checks device status in a loop
ready

Simple to implement More complex (ISR needed)

CPU is free until interrupt arrives —

Wastes CPU cycles (busy waiting)
efficient

Good only when device is very fast and frequently

Better for slow or unpredictable devices
ready

Predictable timing Asynchronous — happens anytime

Polling: Interrupt:
while (device not ready) CPU does other work...
; // wait [device ready] → sends interrupt
read data CPU saves state → jumps to ISR
ISR reads data → returns to prev work

▸ DEVICE DRIVER

A device driver is a software module (usually part of the OS kernel) that controls a specific hardware device. It provides
a standard interface to the OS while hiding the hardware-specific details.

Functions of Device Drivers:

Initialization: Sets up the device when the system boots

Translation: Converts OS-level commands (read/write) to device-specific commands

Interrupt handling: Registers and handles interrupts from the device

Error handling: Detects and reports device errors

Buffering: Manages data buffers between device and memory

Status reporting: Informs the OS of device state (busy, idle, error)

▾
Q8(b) What do you mean by virtual memory technique? What are the advantages of it? 4 Marks

▸ VIRTUAL MEMORY

Virtual Memory is a memory management technique that creates the illusion of a larger memory space than physically
available. Each process has a large virtual address space, but only the actively used pages are kept in physical RAM —
the rest reside on disk (swap space).

Process virtual space: [0 ─────────────── 4GB (or more)]

↕ (MMU mapping)
Physical RAM: [used pages only — e.g., 256MB]
Disk (swap): [remaining pages stored here]

When a page is needed but not in RAM:

→ Page Fault → OS loads page from disk → resume

▸ ADVANTAGES

Run programs larger than RAM: Only needed pages reside in RAM at any time. A 4GB program can run on 1GB RAM.

More processes in memory: Each process uses less physical RAM → higher degree of multiprogramming → better
CPU utilisation.

Memory isolation: Each process has its own virtual address space → processes cannot access each other's memory
(security/protection).

Shared libraries: Common code (e.g., C runtime library) can be mapped into multiple process virtual spaces, sharing
one physical copy → saves RAM.

Simplified programming: Developers work with large, flat virtual address spaces without worrying about physical
memory layout.

Copy-on-Write (COW): fork() can share pages between parent and child until one modifies a page → reduces
memory usage and speeds up process creation.

▾
Q8(c) Explain logical address and physical address. 3 Marks

Logical Address (Virtual Address): Address generated by the CPU. The user program only sees and uses logical
addresses. Each process has its own logical address space starting from 0, so two processes can have the same
logical address (0x1000) without conflict.

Physical Address: Actual location in physical RAM. The memory controller uses this address to read/write data. The
program never sees physical addresses — they are produced by the MMU.

CPU generates → Logical Address (e.g., 0x00004500)

│
MMU + Page Table
│
Physical Address (e.g., 0x00124500) → RAM

LOGICAL ADDRESS PHYSICAL ADDRESS

CPU generates during execution MMU translates from logical

Only memory hardware sees

User program sees this
this

Same logical address in different processes → different physical Unique in the physical
locations memory

The final address sent to

Translation: via page table or segment table
RAM