CSC264 · TU past paper

Operating Systems 2078 question paper

The complete TU 2078 exam paper for Operating Systems (CSC264), all 12 questions with solved model answers written to the mark scheme.

Past Papers2081 2080.1 2080 2079 2078 2076

Tap a question to open its answer.

110 marksSleep and WakeupHideAnswer
What kind of problem arises with sleep and wakeup mechanism of achieving mutual exclusion? Explain with suitable code snippet.[10]
Sleep and Wakeup is an inter-process communication mechanism used to achieve mutual exclusion and process synchronization. As stated in the notes: "Sleep is a system call that causes the caller to block (i.e., to be suspended) until anot...

210 marksNumericalPage Replacement AlgorithmsAnswer

Why OPR is best but not practically feasible page replacement algorithm? Calculate the number of page faults for OPR, LRU and Clock page replacement algorithm for the reference string: 1, 3, 4, 2, 3, 5, 4, 3, 1, 2, 4, 6, 3, 2, 1, 4, 2. Assume the memory size is 3.[10]

OPR Page Replacement and Page Fault Calculations

Given Data

Reference String: 1, 3, 4, 2, 3, 5, 4, 3, 1, 2, 4, 6, 3, 2, 1, 4, 2
Number of Frames: 3

Why OPR is Best but Not Practically Feasible

Optimal Page Replacement (OPR) replaces the page that will not be used for the longest period of time in the future.

Why BEST:

Yields the minimum possible page faults for a given string and frame count.
Used as a benchmark to evaluate other algorithms.
Free from Belady's anomaly.

Why NOT feasible:

Requires future knowledge of the reference string.
The OS cannot predict which pages a process will reference next.
Hence impossible to implement; only a theoretical reference point.

1. Optimal (OPR)

Rule: replace the page whose next use is farthest in the future.

Step	Ref	Frames	Fault/Hit
1	1	[1]	Fault
2	3	[1,3]	Fault
3	4	[1,3,4]	Fault
4	2	next: 1→9, 3→5, 4→7 → replace 1 → [2,3,4]	Fault
5	3	[2,3,4]	Hit
6	5	next: 2→10, 3→8, 4→7 → replace 2 → [5,3,4]	Fault
7	4	[5,3,4]	Hit
8	3	[5,3,4]	Hit
9	1	next: 5→never, 3→13, 4→11 → replace 5 → [1,3,4]	Fault
10	2	next: 1→15, 3→13, 4→11 → replace 1 → [2,3,4]	Fault
11	4	[2,3,4]	Hit
12	6	next: 2→14, 3→13, 4→16 → replace 4 → [2,3,6]	Fault
13	3	[2,3,6]	Hit
14	2	[2,3,6]	Hit
15	1	next: 2→17, 3→never, 6→never → replace 3 → [2,1,6]	Fault
16	4	next: 2→17, 1→never, 6→never → replace 6 → [2,1,4]	Fault
17	2	[2,1,4]	Hit

OPR Page Faults = 10, Hits = 7

2. LRU (Least Recently Used)

Replace the page unused for the longest time.

Step	Ref	Frames (after)	Fault/Hit	Recency (recent→old)
1	1	[1]	Fault	1
2	3	[1,3]	Fault	3,1
3	4	[1,3,4]	Fault	4,3,1
4	2	evict 1 → [2,3,4]	Fault	2,4,3
5	3	[2,3,4]	Hit	3,2,4
6	5	evict 4 → [2,3,5]	Fault	5,3,2
7	4	evict 2 → [4,3,5]	Fault	4,5,3
8	3	[4,3,5]	Hit	3,4,5
9	1	evict 5 → [4,3,1]	Fault	1,3,4
10	2	evict 4 → [2,3,1]	Fault	2,1,3
11	4	evict 3 → [2,4,1]	Fault	4,2,1
12	6	evict 1 → [2,4,6]	Fault	6,4,2
13	3	evict 2 → [3,4,6]	Fault	3,6,4
14	2	evict 4 → [3,2,6]	Fault	2,3,6
15	1	evict 6 → [3,2,1]	Fault	1,2,3
16	4	evict 3 → [4,2,1]	Fault	4,1,2
17	2	[4,2,1]	Hit	2,4,1

Count faults: steps 1,2,3,4,6,7,9,10,11,12,13,14,15,16 = 14 faults, Hits = 3

LRU Page Faults = 14

3. Clock (Second-Chance)

Circular list of 3 frames with a reference bit; on fault the pointer advances, clearing set bits until it finds a bit=0 to replace. On a hit, the page's reference bit is set to 1.

Let frame slots be positions 0,1,2. Pointer starts at 0.

Step	Ref	Action	Frames (bit)	Ptr after	F/H
1	1	load pos0	1(1) - -	1	Fault
2	3	load pos1	1(1) 3(1) -	2	Fault
3	4	load pos2	1(1) 3(1) 4(1)	0	Fault
4	2	ptr0: 1 bit1→0, ptr1:3→0, ptr2:4→0, ptr0:1 bit0 replace	2(1) 3(0) 4(0)	1	Fault
5	3	hit, set 3→1	2(1) 3(1) 4(0)	1	Hit
6	5	ptr1:3 bit1→0, ptr2:4 bit0 replace	2(1) 3(0) 5(1)	0	Fault
7	4	ptr0:2→0, ptr1:3 bit0 replace	2(0) 4(1) 5(1)	2	Fault
8	3	ptr2:5→0, ptr0:2 bit0 replace	3(1) 4(1) 5(0)	1	Fault
9	1	ptr1:4→0, ptr2:5 bit0 replace	3(1) 4(0) 1(1)	0	Fault
10	2	ptr0:3→0, ptr1:4 bit0 replace	3(0) 2(1) 1(1)	2	Fault
11	4	ptr2:1→0, ptr0:3 bit0 replace	4(1) 2(1) 1(0)	1	Fault
12	6	ptr1:2→0, ptr2:1 bit0 replace	4(1) 2(0) 6(1)	0	Fault
13	3	ptr0:4→0, ptr1:2 bit0 replace	4(0) 3(1) 6(1)	2	Fault
14	2	ptr2:6→0, ptr0:4 bit0 replace	2(1) 3(1) 6(0)	1	Fault
15	1	ptr1:3→0, ptr2:6 bit0 replace	2(1) 3(0) 1(1)	0	Fault
16	4	ptr0:2→0, ptr1:3 bit0 replace	2(0) 4(1) 1(1)	2	Fault
17	2	hit, set 2→1	2(1) 4(1) 1(1)	2	Hit

Faults: all steps except 5 and 17 = 15 faults, Hits = 2

Clock Page Faults = 15

Summary

Algorithm	Page Faults
OPR	10
LRU	14
Clock	15

(OPR gives the fewest faults, confirming it as the optimal benchmark.)

310 marksNumericalHandling DeadlocksAnswer

How unsafe state differs from deadlocked state? Consider the following initial state and identify whether requested is granted or denied for the given cases. What will happen if process D requests 1 resource? What will happen if process A requests 1 resource?

Process	Has	Max
A	2	6
B	1	5
C	2	3
D	3	8

$\text{Free} = 2$

[10]

Process	Has	Max
A	2	6
B	1	5
C	2	3
D	3	8

$$\text{Free} = 2$$

[10]

Unsafe State vs Deadlocked State, and Banker's Algorithm Application

Given Data

Process	Has	Max	Need = Max − Has
A	2	6	4
B	1	5	4
C	2	3	1
D	3	8	5

Free = 2

Total resources $= (2+1+2+3) + 2 = 10$ (single resource type).

Part 1: Unsafe State vs Deadlocked State

Aspect	Unsafe State	Deadlocked State
Definition	No guaranteed safe sequence exists to let all processes finish	A set of processes is permanently blocked, each waiting on a resource held by another
Progress	Processes may still run; deadlock has not necessarily happened	No process can proceed at all
Nature	A warning/potential problem	An actual, current problem
Relationship	Superset: not every unsafe state leads to deadlock	A deadlocked state is always unsafe (deadlock ⊆ unsafe)
Handling	Banker's Algorithm avoids it by denying dangerous requests	Requires detection + recovery

An unsafe state means the system might deadlock if unlucky future requests occur; a deadlocked state means it has already got stuck.

Part 2: Is the Initial State Safe?

Apply safety check with Free = 2. Look for a process with $\text{Need} \le \text{Free}$ .

C: Need = 1 ≤ 2 → run. Free = $2 + 2 = 4$
A: Need = 4 ≤ 4 → run. Free = $4 + 2 = 6$
B: Need = 4 ≤ 6 → run. Free = $6 + 1 = 7$
D: Need = 5 ≤ 7 → run. Free = $7 + 3 = 10$

Safe sequence: C → A → B → D. The initial state is SAFE.

Part 3: Process D Requests 1 Resource

Request = 1 ≤ Need(D) = 5 ✓
Request = 1 ≤ Free = 2 ✓ (tentatively grant)

Tentative state: D: Has = 4, Need = 4. Free = $2 - 1 = 1$ .

Safety check with Free = 1:

Process	Need	Need ≤ Free?
A	4	No
B	4	No
C	1	Yes
D	4	No

Run C: Free = $1 + 2 = 3$
Remaining A(4), B(4), D(4): none ≤ 3 → stuck

No safe sequence exists → UNSAFE state.

Conclusion: D's request is DENIED.

Part 4: Process A Requests 1 Resource

Request = 1 ≤ Need(A) = 4 ✓
Request = 1 ≤ Free = 2 ✓ (tentatively grant)

Tentative state: A: Has = 3, Need = 3. Free = $2 - 1 = 1$ .

Process	Has	Max	Need
A	3	6	3
B	1	5	4
C	2	3	1
D	3	8	5

Safety check with Free = 1:

C: Need = 1 ≤ 1 → run. Free = $1 + 2 = 3$
A: Need = 3 ≤ 3 → run. Free = $3 + 3 = 6$
B: Need = 4 ≤ 6 → run. Free = $6 + 1 = 7$
D: Need = 5 ≤ 7 → run. Free = $7 + 3 = 10$

Safe sequence: C → A → B → D. The resulting state is SAFE.

Conclusion: A's request is GRANTED.

Summary

Request	Result
Initial state	SAFE (C → A → B → D)
D requests 1	DENIED (leads to unsafe state)
A requests 1	GRANTED (state remains safe)

Parts 2 and 3 give an initially safe state with D's request denied, and Part 4 shows that A's request is GRANTED.

Unsafe State vs Deadlocked State, and Banker's Algorithm Application

Given Data

Process	Has	Max	Need = Max − Has
A	2	6	4
B	1	5	4
C	2	3	1
D	3	8	5

Free = 2

Total resources $= (2+1+2+3) + 2 = 10$ (single resource type).

Part 1: Unsafe State vs Deadlocked State

Aspect	Unsafe State	Deadlocked State
Definition	No guaranteed safe sequence exists to let all processes finish	A set of processes is permanently blocked, each waiting on a resource held by another
Progress	Processes may still run; deadlock has not necessarily happened	No process can proceed at all
Nature	A warning/potential problem	An actual, current problem
Relationship	Superset: not every unsafe state leads to deadlock	A deadlocked state is always unsafe (deadlock ⊆ unsafe)
Handling	Banker's Algorithm avoids it by denying dangerous requests	Requires detection + recovery

An unsafe state means the system might deadlock if unlucky future requests occur; a deadlocked state means it has already got stuck.

Part 2: Is the Initial State Safe?

Apply safety check with Free = 2. Look for a process with $\text{Need} \le \text{Free}$.

C: Need = 1 ≤ 2 → run. Free = $2 + 2 = 4$
A: Need = 4 ≤ 4 → run. Free = $4 + 2 = 6$
B: Need = 4 ≤ 6 → run. Free = $6 + 1 = 7$
D: Need = 5 ≤ 7 → run. Free = $7 + 3 = 10$

Safe sequence: C → A → B → D. The initial state is SAFE.

Part 3: Process D Requests 1 Resource

Request = 1 ≤ Need(D) = 5 ✓
Request = 1 ≤ Free = 2 ✓ (tentatively grant)

Tentative state: D: Has = 4, Need = 4. Free = $2 - 1 = 1$.

Safety check with Free = 1:

Process	Need	Need ≤ Free?
A	4	No
B	4	No
C	1	Yes
D	4	No

Run C: Free = $1 + 2 = 3$
Remaining A(4), B(4), D(4): none ≤ 3 → stuck

No safe sequence exists → UNSAFE state.

Conclusion: D's request is DENIED.

Part 4: Process A Requests 1 Resource

Request = 1 ≤ Need(A) = 4 ✓
Request = 1 ≤ Free = 2 ✓ (tentatively grant)

Tentative state: A: Has = 3, Need = 3. Free = $2 - 1 = 1$.

Process	Has	Max	Need
A	3	6	3
B	1	5	4
C	2	3	1
D	3	8	5

Safety check with Free = 1:

C: Need = 1 ≤ 1 → run. Free = $1 + 2 = 3$
A: Need = 3 ≤ 3 → run. Free = $3 + 3 = 6$
B: Need = 4 ≤ 6 → run. Free = $6 + 1 = 7$
D: Need = 5 ≤ 7 → run. Free = $7 + 3 = 10$

Safe sequence: C → A → B → D. The resulting state is SAFE.

Conclusion: A's request is GRANTED.

Summary

Request	Result
Initial state	SAFE (C → A → B → D)
D requests 1	DENIED (leads to unsafe state)
A requests 1	GRANTED (state remains safe)

Parts 2 and 3 give an initially safe state with D's request denied, and Part 4 shows that A's request is GRANTED.

45 marksHandling System CallsHideAnswer
What is system call? Discuss process of handling system calls briefly. [5]
A system call is the interface between a process (i.e., a user program) and the operating system. It provides a mechanism through which a user-level program can request services from the operating system kernel, such as process managemen...
55 marksImplementing Mutual ExclusionHideAnswer
What is lock variable? Discuss its working and problems associated with it in detail. [5]
A lock variable is a single, shared variable used to implement mutual exclusion among competing processes. It is initially set to 0 and acts as a flag to indicate whether any process is currently inside its critical region. - Lock = 0 → ...
65 marksNumericalMemory Allocation StrategiesHideAnswer
Differentiate between internal and external fragmentation? Suppose that we have memory of 100 KB with 5 partitions of size 150 KB, 200 KB, 250 KB, 100 KB, and 300 KB. Where the processes A and B of size 175 KB and 125 KB will be loaded, if we used Best-Fit, and Worst-Fit Strategy? [5]
Aspect Internal Fragmentation External Fragmentation --------- Definition Wasted memory inside an allocated partition when the process is smaller than the block assigned to it Total free memory is enough, but it is split into scattered n...
75 marksFile OverviewHideAnswer
What is ment by file attributes? Discuss any one technique of implementing directories in detail. [5]
Every file has a name and the data it contains. In addition, a file system stores extra information associated with each file, known as file attributes (also called metadata). These attributes describe the properties of the file and help...
85 marksDisk FormattingHideAnswer
Why the concept of disk interleaving is important? Explain with suitable example. [5]
--- Disk interleaving (also called sector interleaving) is a technique used to improve disk read/write performance by arranging the logical order of sectors on a disk track differently from their physical order. Instead of numbering sect...
95 marksHandling DeadlocksHideAnswer
What is resource allocation graph? Explain the process of detecting deadlocks when there is single instance of each resources with suitable example? [5]
Resource Allocation Graph and Deadlock Detection (Single Instance)

Resource Allocation Graph (RAG)

A Resource Allocation Graph is a directed graph used to precisely describe and detect deadlocks in a system. It consists of:
- Vertices (V): Two types:
  
  P = {P1, P2, ..., Pn} - set of all active processes (represented as circles)
  
  R = {R1, R2, ..., Rm} - set of all resource types (represented as rectangles)
- Edges (E): Two types:
  
  Request Edge: Pi → Rj (process Pi is requesting resource Rj)
  
  Assignment Edge: Rj → Pi (resource Rj is assigned to process Pi)
Key Rule: If the RAG contains no cycle, no deadlock exists. If it contains one or more cycles, a deadlock exists (when each resource has only a single instance).

Deadlock Detection with Single Instance of Each Resource

When there is only one instance of each resource type, we construct a resource allocation graph and check for cycles. Any process that is part of a cycle is deadlocked.

Example

Consider a system with 7 processes (A to G) and 6 resources (R to W) with the following state:

Process Holds Wants
A R S
B Nothing T
C Nothing S
D U S and T
E T V
F W S
G V U

Step 1: Draw the RAG

Assignment Edges (Resource → Process):
- R → A
- U → D
- T → E
- W → F
- V → G
Request Edges (Process → Resource):
- A → S
- B → T
- C → S
- D → S, D → T
- E → V
- F → S
- G → U
Step 2: Trace for Cycles

Tracing the graph:
D → T → E → V → G → U → D (Cycle Found!)
This forms a cycle: D → T → E → V → G → U → D

Step 3: Identify Deadlocked Processes

The processes involved in the cycle are:

D, E, and G are deadlocked.
- Process D holds U, wants T
- Process E holds T, wants V
- Process G holds V, wants U
Each is waiting for a resource held by another in the cycle, and none can proceed.

Processes A, B, C, and F are not deadlocked (they are not part of any cycle), even though they may be waiting.

Conclusion

In a single-instance resource system, deadlock detection reduces to cycle detection in the Resource Allocation Graph. If a cycle exists, all processes in that cycle are deadlocked.
105 marksProcess SchedulingHideAnswer
Discuss the concept of SJF and SRTN scheduling algorithms with suitable example. [5]
SJF is a non-preemptive CPU scheduling algorithm in which the process with the smallest burst time (CPU time) is selected next for execution from the ready queue. Once a process starts executing, it runs to completion without interruptio...
115 marksFree Space ManagementHideAnswer
What approaches are using for managing free disk spaces? Explain linked list approaches with example. [5]
The system maintains a free space list to keep track of disk blocks not allocated to any file or directory. The two main approaches are: 1. Bitmap (Bit Vector) 2. Linked List --- In the linked list approach, all free disk blocks are link...

Process	Holds	Wants
A	R	S
B	Nothing	T
C	Nothing	S
D	U	S and T
E	T	V
F	W	S
G	V	U

125 marksInter-process CommunicationAnswer

Write short notes on: a. IPC in Linux b. Disk access [5]

Short Notes: IPC in Linux and Disk Access

a. IPC in Linux (Inter-Process Communication)

Inter-Process Communication (IPC) refers to the mechanisms that allow processes running in Linux to communicate and synchronize with each other.

In Linux, processes are independent units of execution. However, many applications require processes to share data or coordinate their activities. Linux provides several IPC mechanisms:

Key IPC Mechanisms in Linux:

Mechanism	Description
Pipes	Allow one-way communication between related processes (parent-child). Data flows in a single direction.
Named Pipes (FIFOs)	Similar to pipes but allow communication between unrelated processes using a file name in the filesystem.
Signals	Used to notify a process that a particular event has occurred (e.g., SIGKILL, SIGTERM).
Message Queues	Allow processes to send and receive messages in a queue format, managed by the kernel.
Shared Memory	Allows multiple processes to access the same region of memory, providing the fastest form of IPC.
Semaphores	Used for synchronization between processes to avoid race conditions when accessing shared resources.
Sockets	Allow communication between processes on the same machine or across a network.

Key Points:

Linux processes run in foreground or background mode
The Linux kernel mediates and controls access to system resources including IPC facilities
IPC mechanisms are managed through kernel modules stored in /lib/modules subdirectories
Proper synchronization is essential to prevent data corruption when multiple processes share resources

b. Disk Access

Disk access refers to the process of reading from or writing data to a hard disk drive. Understanding disk access is important for optimizing I/O performance.

Disk Structure (from notes):

A disk is divided into:

Tracks: Concentric circles on each platter surface
Cylinders: The same track across all platters
Sectors: Subdivisions of each track

Each platter has 2 surfaces with read/write heads for each surface.

Disk Access Time Formula:

Disk Access Time = Seek Time + Rotational Latency + Transfer Time

Components Explained:

Component	Definition
Seek Time	Time taken to move the disk arm to the specified track where the read/write request will be satisfied
Rotational Latency	Time taken for the desired sector to rotate into position under the read/write head
Transfer Time	Time to actually transfer the data; depends on rotating speed and number of bytes to be transferred

Additional Terms:

Random Access Time = Seek Time + Rotational Latency
Disk Response Time: Average time spent by a request waiting to perform its I/O operation
Transmission Time: Total time taken to access the whole record
Transfer Rate: Rate at which data moves from disk to the computer

Example:

If Seek Time = 5 ms, Rotational Latency = 3 ms, Transfer Time = 2 ms:

Disk Access Time = 5 + 3 + 2 = 10 ms

Optimization:

RAID (Redundant Array of Independent Disks) improves disk performance by striping data across multiple disks, allowing overlapping I/O operations
Virtual Memory uses disk as an extension of RAM (swap space), though disk access is slower than RAM access

Both topics are core components of Operating System I/O and process management as covered in the Linux OS architecture.

Keep going

Important questions + predictions

Full syllabus Flashcards and practice

Other papers

2081 paper 2080.1 paper 2080 paper 2079 paper 2076 paper

Operating Systems 2078 question paper

OPR Page Replacement and Page Fault Calculations

Given Data

Why OPR is Best but Not Practically Feasible

1. Optimal (OPR)

2. LRU (Least Recently Used)

3. Clock (Second-Chance)

Summary

Unsafe State vs Deadlocked State, and Banker's Algorithm Application

Given Data

Part 1: Unsafe State vs Deadlocked State

Part 2: Is the Initial State Safe?

Part 3: Process D Requests 1 Resource

Conclusion: D's request is DENIED.

Part 4: Process A Requests 1 Resource

Conclusion: A's request is GRANTED.

Summary

Unsafe State vs Deadlocked State, and Banker's Algorithm Application

Given Data

Part 1: Unsafe State vs Deadlocked State

Part 2: Is the Initial State Safe?

Part 3: Process D Requests 1 Resource

Conclusion: D's request is DENIED.

Part 4: Process A Requests 1 Resource

Conclusion: A's request is GRANTED.

Summary

Resource Allocation Graph and Deadlock Detection (Single Instance)

Resource Allocation Graph (RAG)

Deadlock Detection with Single Instance of Each Resource

Example

Step 1: Draw the RAG

Step 2: Trace for Cycles

Step 3: Identify Deadlocked Processes

Conclusion

Short Notes: IPC in Linux and Disk Access

a. IPC in Linux (Inter-Process Communication)

Key IPC Mechanisms in Linux:

Key Points:

b. Disk Access

Disk Structure (from notes):

Disk Access Time Formula:

Components Explained:

Additional Terms:

Example:

Optimization:

Unsafe State vs Deadlocked State, and Banker's Algorithm Application

Given Data

Part 1: Unsafe State vs Deadlocked State

Part 2: Is the Initial State Safe?

Part 3: Process D Requests 1 Resource

Conclusion: D's request is DENIED.

Part 4: Process A Requests 1 Resource

Conclusion: A's request is GRANTED.

Summary