SHORT ANSWERS

i. Define an operating system. What are its

basic functions?
An operating system (OS) is system software
that manages hardware and provides services
to user programs.
Basic functions: process management
(create/schedule/terminate processes),
memory management (allocate/virtual
memory), file system management, I/O device
management, resource allocation and
protection, user interface (CLI/GUI), and
security/authorization.
ii. Pre-emptive vs non-pre-emptive scheduling
Pre-emptive: CPU may be taken from a
running process (context switch) before it
finishes (e.g., Round Robin, Pre-emptive SJF).
Good for responsiveness, needs more context
switches and protection.
Non-pre-emptive: Once a process gets the
CPU it runs until it blocks or finishes (e.g.,
FCFS, non-preemptive SJF). Simpler, less
overhead, but poor responsiveness for long
jobs.
iii. What are semaphores? Types
A semaphore is a synchronization primitive
(integer + atomic operations) used to control
access to shared resources.
Types:
Binary semaphore (mutex): values {0,1} —
for mutual exclusion.
Counting semaphore: integer can represent
number of available resources.
Operations: wait()/P()/down() and
signal()/V()/up() (atomic).
iv. Round Robin (RR) scheduling
RR gives each ready process a time quantum
(time slice). Processes are in a FIFO ready
queue; the CPU runs the head for one
quantum (or until it finishes), then if not
finished it is enqueued back. Good for time-
sharing and fairness. Performance depends on
quantum: too small → high overhead; too
large → poor responsiveness.
v. Belady’s anomaly
Phenomenon where increasing the number of
page frames increases page faults for some
page-replacement algorithms (observed with
FIFO). Not observed for stack algorithms (e.g.,
LRU, OPT).
vi. Mutual exclusion — example of hardware
solution
Mutual exclusion: ensuring only one
process/thread executes a critical section
accessing shared data at a time.
Hardware example: test-and-set instruction or
compare-and-swap used to implement locks
atomically.
vii. Fragmentation: internal vs external
Fragmentation: wasted memory.
Internal fragmentation: allocated block larger
than requested → wasted space inside
assigned region (e.g., fixed partition).
External fragmentation: free memory is split
into small noncontiguous blocks so a large
request can't be satisfied even though total
free memory is enough.
viii. Necessary conditions for a deadlock (all
must hold simultaneously — Coffman
conditions)

1. Mutual exclusion (resource non-shareable)

2. Hold and wait (process holds resources
while waiting for others)
3. No pre-emption (resources cannot be
forcibly taken)
4. Circular wait (circular chain of processes
each waiting for next)

MEDIUM ANSWERS
Q2a — Multiprogramming, Time-sharing, Real-
time OS (brief)
Multiprogramming: Multiple programs loaded
in memory; CPU switches among them to
maximize CPU utilization. Goal: reduce idle
time due to I/O. Not necessarily interactive.
Time-sharing (multitasking): Extension of
multiprogramming with short time quanta,
provides interactive user response. Each
user/process appears to have a dedicated
machine (RR-like scheduling).
Real-time OS: Designed to meet timing
constraints.
Hard real-time: missing deadline = system
failure (e.g., avionics).
Soft real-time: missing deadlines degrades
performance (e.g., multimedia).
RTOS features: deterministic scheduling (rate
monotonic, earliest deadline first), low
interrupt latency, predictable behaviour.
Q2b — FCFS, SJF, Priority Scheduling (brief)
FCFS (First Come First Serve): Simple queue,
Non-pre-emptive. Pros: simple, fair by arrival.
Cons: convoy effect — long wait for short jobs.
SJF (Shortest Job First): Choose job with
smallest burst time (can be pre-emptive or
Non-pre-emptive:). Minimizes average waiting
time if exact burst times known. Cons:
requires knowledge/prediction and can starve
long jobs.
Priority scheduling: Assign priorities; CPU to
highest priority (pre-emptive or Non-pre-
emptive). Cons: starvation for low priority —
use aging to avoid.
Q3a — Producer–Consumer with semaphores
(classic solution)
Let buffer size = N. Semaphores:
empty = N (counting), full = 0 (counting),
mutex = 1 (binary).
Producer:
while true:
produce item()
wait(empty)
wait(mutex)
insert item(buffer, item)
 signal(mutex)
signal(full)

Consumer:
while true:
wait(full)
wait(mutex)
remove_item(buffer,item)
signal(mutex)
signal(empty)
consume_item(item)

Q3b — Process states (textual diagram)

Typical states: New → Ready ↔ Running →
Blocked (Waiting) → Terminated.
Ready: waiting for CPU.
Running: executing on CPU.
Blocked: waiting for I/O or event. Scheduler
moves between Ready and Running
(preemption scheduler may pre-empt Running
→ Ready).

Q4a — First fit, Best fit, Worst fit

First fit: allocate in first hole large enough.
Fast, low search cost. Can leave small leftover
fragments.
Best fit: allocate smallest hole that’s large
enough. Minimizes wasted space in that
allocation but often creates many tiny holes →
more external fragmentation.
Worst fit: allocate largest hole. Idea is to leave
moderate-sized holes, but often not effective
in practice.
Example: free blocks [10, 20, 5], request 6 →
first-fit uses 10 (left 4), best-fit uses 10?
actually best-fit picks 10 or? (smallest ≥ 6 is
10), worst-fit picks 20.
Q4b — Virtual memory & demand paging
(brief)
Virtual memory: abstraction that gives
processes illusion of large contiguous
memory; uses pages mapped to physical
frames. Allows programs larger than RAM.
Demand paging: pages are loaded into
memory only when referenced (page fault
triggers load). Reduces I/O but can cause
page faults and potential thrashing if working
set too large.
Q5 — LRU and FIFO page replacement
Given: 3 empty frames initially, reference
string:
1,2,3,4,2,3,5,6,2,1,2,1,2,3,7,6,7,2,1,3,1,2,3,4
Final pages in frames when process finishes:
FIFO (3 frames): final frames = {1, 3, 4}
(order depends on replacement FIFO queue;
set shown).
LRU (3 frames): final frames = {2, 3, 4} (one
possible frame ordering is [3,2,4]).
Q5 (other) — What is deadlock? Prevention &
detection (brief)
Deadlock: set of processes each waiting for
resources held by others; none can proceed.
Prevention techniques: break one of Coffman
conditions:
Mutual exclusion: make resources sharable
when possible.
Hold-and-wait: require processes to request
all resources at once or release before
requesting new ones.
No preemption: allow preemption of resources
(forcefully take resources away).
Circular wait: impose ordering of resource
types and require processes request in
increasing order.
Detection & recovery: allow deadlocks to
occur, detect via resource-allocation graph /
wait-for graph, then recover by aborting
processes or preempting resources. Example:
run detection algorithm periodically and kill or
rollback one process to break deadlock.
 LONG ANSWERS
Q6 — Goals, structure, and types of OS;
examples of batch & distributed OS.
Goals of OS: provide convenient environment
for program execution, efficiently manage
hardware/resources, ensure fairness, security
and protection, and provide abstractions
(processes, files, virtual memory).
Structure (typical layers): hardware → kernel
(interrupt handlers, device drivers, scheduler,
memory manager) → system calls → user
programs. Variants: monolithic kernel,
microkernel, modular.

Types of OS: single-user/single-tasking, single-

user/multi-tasking, multiuser, real-time,
embedded, distributed, network OS.
Batch OS: jobs batched and processed (e.g.,
historical early systems, IBM OS/360 had
batch modes).
Distributed OS: manages a collection of
independent computers and makes them
appear as one system (e.g., Amoeba, LOCUS).
Modern distributed systems include cluster
management and distributed file systems.
Q7 — Scheduling calculations (worked)
Given processes:
Process Arrival Burst
P1 0 6
P2 1 8
P3 2 7
P4 3 3

SJF (Non-pre-emptive)
Execution order (Non-pre-emptive) SJF
considering arrival):
P1 (0–6) → at t=6 choose shortest among P2
(8),P3(7),P4(3) → P4 (6–9) → P3 (9–16) → P2
(16–24)
Waiting times:
P1 = 0
P4 = start6 − arrival3 = 3
P3 = start9 − arrival2 = 7
P2 = start16 − arrival1 = 15

Avg. waiting time = (0 + 3 + 7 + 15)/4 = 6.25

Turn around times (finish − arrival):
P1 = 6 − 0 = 6
P4 = 9 − 3 = 6
P3 = 16 − 2 = 14
P2 = 24 − 1 = 23
Avg turnaround time = (6 + 6 + 14 + 23)/4 =
12.25
b) FCFS
Order by arrival: P1 (0–6) → P2 (6–14) → P3
(14–21) → P4 (21–24)
Waiting times:
P1 = 0
P2 = 6 − 1 = 5
P3 = 14 − 2 = 12
P4 = 21 − 3 = 18
Avg waiting time = (0 + 5 + 12 + 18)/4 =
8.75
Turn around times:
P1 = 6 − 0 = 6
P2 = 14 − 1 = 13
P3 = 21 − 2 = 19
P4 = 24 − 3 = 21
Avg turnaround time = (6 + 13 + 19 + 21)/4
= 14.75
(So SJF yields lower average waiting &
turnaround here.)
Q8 — Memory management techniques (brief
pros/cons)
Partitioning (fixed / dynamic): simple; fixed
partitioning causes internal fragmentation;
dynamic reduces internal fragmentation but
can cause external fragmentation.
Paging: divides memory into fixed-size
pages/frames. Eliminates external
fragmentation; requires page table overhead
and possible TLB. Fragmentation is internal
only (within last page of a process).
Segmentation: logical variable-sized
segments (e.g., code, data). Easier for
programmer view but can cause external
fragmentation; combining segmentation with
paging reduces fragmentation.
Advantages/disadvantages summarized
above: paging = simple mapping + no
external fragmentation; segmentation =
logical division + flexible but needs
compaction or paging to avoid fragmentation.
Q9 — Banker’s Algorithm (safe sequence)
Given:
Available = (3, 3, 2)
 Max and Allocation: Process Max
Allocation
P1 (7,5,3) (0,1,0)
P2 (3,2,2) (2,0,0)
P3 (9,0,2) (3,0,2)
P4 (2,2,2) (2,1,1)
P5 (4,3,3) (0,0,2)
 Need = Max − Allocation:
P1: (7,4,3)
P2: (1,2,2)
P3: (6,0,0)
P4: (0,1,1)
P5: (4,3,1)
 Apply safety algorithm: one safe sequence
is:P2 → P4 → P5 → P1 → P3
Thus the system is safe and the above
sequence will allow all processes to finish.