Model Question Paper - KTU BTech PCCST403 OS Operating System 2024 Scheme - Answer Key

                                PART A

1.On a Linux-based system, a process holding an array of 1 million integers executes fork(). The child process only reads the array to compute a sum, while the parent continues modifying the array.

If the parent modifies 10% of the pages and the array spans 2000 pages:

1. How many physical copies of the array exist immediately after fork()?
2. How many pages get duplicated due to the modifications?

✅ Answer

Key Concepts Involved

• fork() in Linux uses Copy-On-Write (COW)
• Initially, parent and child share the same physical pages
• A page is copied only when one process modifies it

---

Step-by-Step Reasoning

1. Immediately after fork()

• No pages are copied yet
• Parent and child share all 2000 pages
• So:

👉 Physical copies of the array = 1 (shared)

---

2. When the parent modifies 10% of pages

• Total pages = 2000
• Modified pages = 10% of 2000 = 200 pages

Because of COW:

• These 200 pages are duplicated
• Parent gets private copies of these pages
• Child continues using original pages (since it only reads)

2.On a system with n processors, what is the minimum and maximum number of processes that can be in the following states at any instant?

• Ready
• Running
• Blocked

---

✅ Answer

🔹 1. Running State

• A processor can execute only one process at a time
• With n processors, up to n processes can run simultaneously

👉 Minimum: 0 (if no process is ready to run)
👉 Maximum: n

---

🔹 2. Ready State

• Ready processes are those waiting for CPU allocation

👉 Minimum: 0 (if all processes are either running or blocked)
👉 Maximum: Unbounded (depends on total number of processes in the system)

---

🔹 3. Blocked State

• Blocked processes are waiting for I/O or some event

👉 Minimum: 0 (if no process is waiting)
👉 Maximum: Unbounded (depends on how many processes are waiting for events)

3.Processes P1 and P2 use the following code for synchronization. Assume flag is a shared variable initialized to false.

if(flag == false)
{
    flag = true;
    criticalSection();
    flag = false;
}

1. Does this guarantee mutual exclusion?
2. Can it lead to deadlock?

---

✅ Answer

🔹 1. Mutual Exclusion — ❌ Not Guaranteed

This solution fails to guarantee mutual exclusion.

💡 Why?

The check and update of flag are not atomic.

⚠️ Possible Interleaving:

1. P1 checks flag == false → TRUE
2. Context switch happens before setting flag = true
3. P2 checks flag == false → TRUE
4. Both processes set flag = true
5. Both enter criticalSection() ❌

👉 Result: Two processes are in the critical section simultaneously → Violation of mutual exclusion

---

🔹 2. Deadlock — ❌ No, it does not lead to deadlock

💡 Why?

• A process does not wait if flag == true
• It simply skips the critical section and continues
• There is no circular waiting

👉 Result: No deadlock occurs

4.An operating system has 3 processes, each requiring 2 units of a resource R.

What is the minimum number of instances of R required so that the system is deadlock-free?

---

✅ Answer

👉 Minimum number of instances required = 4

---

💡 Explanation

To ensure a system is deadlock-free, we must prevent a situation where:

• Each process holds one unit of resource R
• And waits indefinitely for one more unit

---

🔍 Worst-Case Scenario

• Total processes = 3
• Each needs 2 units
• Suppose each process acquires 1 unit

👉 Resources allocated = 3 units
👉 Each process still needs 1 more unit

If only 3 units exist:

• No free resource is available
• All processes are stuck waiting ❌ → Deadlock

For n processes, each requiring at most k instances of a resource:

$$\boxed{\text{Minimum instances required} = n \times (k - 1) + 1}$$

6.A computer has four page frames. The following information is given:

Page	TLD	TLA	R	M
0	126	280	1	0
1	230	265	0	1
2	240	270	1	0
3	110	285	1	1

Where:

• TLD = Time of Last Loading
• TLA = Time of Last Access
• R = Reference bit
• M = Modified bit

👉 Which page will be replaced using:

1. FIFO
2. LRU
3. Modified Clock algorithm

---

✅ Answer

🔹 1. FIFO (First-In, First-Out)

• Replace the page with the smallest TLD (oldest loaded)

Page	TLD
3	110 (smallest)

👉 Replaced Page = 3

---

🔹 2. LRU (Least Recently Used)

• Replace the page with the smallest TLA (least recently accessed)

Page	TLA
1	265 (smallest)

👉 Replaced Page = 1

---

🔹 3. Modified Clock Algorithm

This algorithm prefers pages in this order:

1. (R=0, M=0) → best candidate
2. (R=0, M=1)
3. (R=1, M=0)
4. (R=1, M=1) → worst candidate

---

👉 Only Page 1 falls in (0,1)

👉 Replaced Page = 1

---

📊 Final Summary

Algorithm	Page Replaced
FIFO	3
LRU	1
Modified Clock	1

11b) A multithreaded web server maintains a cache using a hash table (1024 buckets). Each bucket contains a doubly linked list of cached pages.The cache supports three operations: insert, lookup, and delete. It is proposed to use mutex locks for synchronization.

👉 Discuss the pros and cons of the following locking strategies:

1. One mutex for the entire cache
2. One mutex per bucket
3. One mutex per bucket + one per node

---

✅ Answer

---

🔹 (i) One Mutex for Entire Cache

✔️ Pros

• Simple to implement
• Easy to ensure correctness
• No risk of deadlock
• Minimal design complexity

❌ Cons

• Poor concurrency
  • Only one thread can access the cache at a time
• Becomes a bottleneck under high load
• Threads performing lookup (read) still block each other

👉 Use case: Small systems or low contention scenarios

---

🔹 (ii) One Mutex per Bucket

✔️ Pros

• Better concurrency
  • Threads accessing different buckets can proceed in parallel
• Reduces contention significantly
• Good balance between performance and complexity

❌ Cons

• Threads accessing the same bucket still serialize
• Performance depends on hash distribution
• Slightly more complex than global lock

👉 Use case: Most practical and commonly used approach

---

🔹 (iii) One Mutex per Bucket + One per Node

✔️ Pros

• Maximum concurrency
  • Multiple threads can operate on the same bucket simultaneously
• Fine-grained locking allows:
  • Parallel traversal of linked lists
  • Better performance for large buckets

❌ Cons

• High complexity
  • Difficult to implement correctly
• Risk of deadlocks
  • Need careful lock ordering
• Increased locking overhead
• Harder to debug and maintain

👉 Use case: High-performance systems with heavy contention

---

📊 Summary Comparison

13a)Translate the logical address 0001010010111010 into its corresponding physical address under a segmentation system with a maximum segment size of 1024, using a segment table where the base address of each segment is determined as: 22 + 4,096 × segment number .

Given:

• Segmentation system
• Maximum segment size = 1024 = 2¹⁰
• Segment base address =

$$\text{Base} = 22 + 4096 \times (\text{segment number})$$

---

✅ Step 1: Split Logical Address

• Logical address = 16 bits
• Max segment size = $2^{10}$ ⇒ offset = 10 bits
• Remaining = 6 bits for segment number

---

🔹 Segment Number (first 6 bits)

000101 = 5

🔹 Offset (last 10 bits)

0010111010

Convert offset to decimal:

$$0010111010 = 186$$

---

✅ Step 2: Compute Base Address

$$\text{Base} = 22 + 4096 \times 5$$
$$= 22 + 20480 = 20502$$

---

✅ Step 3: Compute Physical Address

$$\text{Physical Address} = \text{Base} + \text{Offset}$$ $$= 20502 + 186 = 20688$$

---

🎯 Final Answer

👉 Physical Address = 20688 (decimal)

13b)A computer provides each process with 65,536 bytes of address space divided into pages of 4096 bytes each. A particular process has a text size of 32,768 bytes, a data size of 16,386 bytes, and a stack size of 15,870 bytes.Will this process fit in the machine’s address space? Suppose that instead of 4096 bytes, the page size was 512 bytes, would it then fit? Each page must contain either text, data, or stack, not a mixture of two or three of them.

• Virtual address space per process = 65,536 bytes (64 KB)
• Page size:
  • Case 1: 4096 bytes
  • Case 2: 512 bytes

Process memory:

• Text = 32,768 bytes
• Data = 16,386 bytes
• Stack = 15,870 bytes

👉 Each page can contain only one type (no mixing)

---

✅ Step 1: Total Available Pages

🔹 Case 1: Page size = 4096 bytes

$$\frac{65536}{4096} = 16 \text{ pages}$$

---

🔹 Case 2: Page size = 512 bytes

$$\frac{65536}{512} = 128 \text{ pages}$$

---

✅ Step 2: Pages Required (Case 1: 4096 bytes)

🔹 Text

$$\frac{32768}{4096} = 8 \text{ pages (exact)}$$

---

🔹 Data

$$\frac{16386}{4096} \approx 4.0005 \Rightarrow 5 \text{ pages}$$

---

🔹 Stack

$$\frac{15870}{4096} \approx 3.87 \Rightarrow 4 \text{ pages}$$

---

🔹 Total Pages Needed

$$8 + 5 + 4 = 17 \text{ pages}$$

👉 Available = 16 pages
👉 Required = 17 pages

❌ Does NOT fit

---

✅ Step 3: Pages Required (Case 2: 512 bytes)

🔹 Text

$$\frac{32768}{512} = 64 \text{ pages}$$

---

🔹 Data

$$\frac{16386}{512} \approx 32.01 \Rightarrow 33 \text{ pages}$$

---

🔹 Stack

$$\frac{15870}{512} \approx 30.99 \Rightarrow 31 \text{ pages}$$

---

🔹 Total Pages Needed

$$64 + 33 + 31 = 128 \text{ pages}$$

👉 Available = 128 pages
👉 Required = 128 pages

✔️ Fits exactly

---

🎯 Final Answer

Page Size	Fits?
4096 bytes	❌ No
512 bytes	✔️ Yes

14a) Consider the following C program:

int X[N], step = M;

for (int i = 0; i < N; i += step)

X[i] = X[i] + 1;

If this program is run on a machine with a 4-KB page size and 64-entry TLB, what values of M and N will cause a TLB miss for every execution of the inner loop?

Page size = 4 KB = 4096 bytes

TLB entries = 64

Assume int = 4 bytes

✅ Key Idea

To get a TLB miss every time:

• Each access must go to a different page
• And we must never reuse a page already in TLB

---

🔍 Step 1: Elements per Page

$$\frac{4096}{4} = 1024 \text{ integers per page}$$

---

🔹 Step 2: Condition for Different Page Access

We want each X[i] to be on a new page.

👉 So:

$$M \geq 1024$$

• If $M < 1024$ → multiple accesses within same page → TLB hit occurs ❌
• If $M \geq 1024$ → each access jumps to a new page ✔️

---

🔹 Step 3: Condition to Overflow TLB

TLB can hold 64 entries.

To ensure every access is a miss:

• We must access more than 64 distinct pages without reuse

👉 So:

$$\frac{N}{M} > 64$$

---

🔹 Step 4: Combine Conditions

Final Conditions:

$$\boxed{M \geq 1024}$$ $$\boxed{N > 64 \times M}$$

---

🎯 Example Values

• $M = 1024$
  
• $N = 65536$
  

Then:

• Each access → new page
• Total pages accessed = 64+
• TLB cannot hold all → continuous eviction

👉 Every iteration → TLB miss

14b)Consider the following page reference string:

1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6.

With a frame allocation of 4, determine the number of page faults for the FIFO, optimal and LRU page replacement policies.

🔹 1. FIFO (First-In First-Out)

👉 Replace oldest loaded page

Step	Ref	Frame1	Frame2	Frame3	Frame4	Fault/Hit
1	1	1	-	-	-	F
2	2	1	2	-	-	F
3	3	1	2	3	-	F
4	4	1	2	3	4	F
5	2	1	2	3	4	H
6	1	1	2	3	4	H
7	5	5	2	3	4	F
8	6	5	6	3	4	F
9	2	5	6	2	4	F
10	1	5	6	2	1	F
11	2	5	6	2	1	H
12	3	3	6	2	1	F
13	7	3	7	2	1	F
14	6	3	7	6	1	F
15	3	3	7	6	1	H
16	2	3	7	6	2	F
17	1	1	7	6	2	F
18	2	1	7	6	2	H
19	3	1	3	6	2	F
20	6	1	3	6	2	H

👉 Total FIFO faults = 14

---

🔹 2. LRU (Least Recently Used)

👉 Replace least recently used page

Step	Ref	Frame1	Frame2	Frame3	Frame4	Fault/Hit
1	1	1	-	-	-	F
2	2	1	2	-	-	F
3	3	1	2	3	-	F
4	4	1	2	3	4	F
5	2	1	2	3	4	H
6	1	1	2	3	4	H
7	5	1	2	5	4	F
8	6	1	2	5	6	F
9	2	1	2	5	6	H
10	1	1	2	5	6	H
11	2	1	2	5	6	H
12	3	1	2	3	6	F
13	7	1	2	3	7	F
14	6	6	2	3	7	F
15	3	6	2	3	7	H
16	2	6	2	3	7	H
17	1	6	2	3	1	F
18	2	6	2	3	1	H
19	3	6	2	3	1	H
20	6	6	2	3	1	H

👉 Total LRU faults = 10

---

🔹 3. Optimal

👉 Replace page used farthest in future

Step	Ref	Frame1	Frame2	Frame3	Frame4	Fault/Hit
1	1	1	-	-	-	F
2	2	1	2	-	-	F
3	3	1	2	3	-	F
4	4	1	2	3	4	F
5	2	1	2	3	4	H
6	1	1	2	3	4	H
7	5	1	2	3	5	F
8	6	1	2	3	6	F
9	2	1	2	3	6	H
10	1	1	2	3	6	H
11	2	1	2	3	6	H
12	3	1	2	3	6	H
13	7	1	2	3	7	F
14	6	1	2	3	6	F
15	3	1	2	3	6	H
16	2	1	2	3	6	H
17	1	1	2	3	6	H
18	2	1	2	3	6	H
19	3	1	2	3	6	H
20	6	1	2	3	6	H

👉 Total Optimal faults = 8

---

📊 Final Summary

Algorithm	Page Faults
FIFO	14
LRU	10
Optimal	8

15a)The disk controller for a hypothetical disk with 200 tracks receives the following sequence of disk track requests

27, 129, 110, 186, 147, 41, 10, 64, 120.

Assume that the disk head is initially positioned over track 100 and is moving in the direction of decreasing track number. Given that a seek between adjacent tracks takes 3ms, determine the better policy between SSTF and ELEVATOR algorithms if the judgement criterion is total seek time to serve all the requests. ELEVATOR and CLOOK algorithms if the judgement criterion is total seek time to serve all the requests.

 Given

• Tracks: 0–199 (200 tracks)
• Initial head position: 100
• Initial direction: towards lower tracks
• Requests:

27, 129, 110, 186, 147, 41, 10, 64, 120

• Seek time per track = 3 ms

---

🔹 1. SSTF (Shortest Seek Time First)

👉 Always go to closest request

Step-by-step movement

Step	From → To	Distance
100 → 110	10
110 → 120	10
120 → 129	9
129 → 147	18
147 → 186	39
186 → 64	122
64 → 41	23
41 → 27	14
27 → 10	17

🔹 Total movement

$$10 + 10 + 9 + 18 + 39 + 122 + 23 + 14 + 17 = 262$$

👉 Total seek time:

$$262 \times 3 = \mathbf{786 \, ms}$$

---

🔹 2. Elevator (SCAN)

👉 Move in one direction (down), then reverse

Order (initially moving ↓):

100 → 64 → 41 → 27 → 10 → (reverse) → 110 → 120 → 129 → 147 → 186

Step-by-step

Step	Movement	Distance
100 → 64	36
64 → 41	23
41 → 27	14
27 → 10	17
10 → 110	100
110 → 120	10
120 → 129	9
129 → 147	18
147 → 186	39

🔹 Total movement

$$36+23+14+17+100+10+9+18+39 = 266$$

👉 Total seek time:

$$266 \times 3 = \mathbf{798 \, ms}$$

---

🔹 3. C-LOOK

👉 Move in one direction, then jump to lowest request (no servicing during return)

Order:

100 → 64 → 41 → 27 → 10 → (jump) → 186 → 147 → 129 → 120 → 110

Step-by-step

Step	Movement	Distance
100 → 64	36
64 → 41	23
41 → 27	14
27 → 10	17
10 → 186	176
186 → 147	39
147 → 129	18
129 → 120	9
120 → 110	10

🔹 Total movement

$$36+23+14+17+176+39+18+9+10 = 342$$

👉 Total seek time:

$$342 \times 3 = \mathbf{1026 \, ms}$$

---

📊 Final Comparison

Algorithm	Total Movement	Seek Time
SSTF	262	786 ms
SCAN (Elevator)	266	798 ms
C-LOOK	342	1026 ms

---

🎯 Final Answer

✔️ Better between SSTF and Elevator:

👉 SSTF is better (786 ms < 798 ms)

✔️ Better between Elevator and C-LOOK:

👉 Elevator (SCAN) is better (798 ms < 1026 ms)

15b)In Unix/Linux file systems, both hard links and symbolic (soft) links allow a file to be accessed through multiple names.
👉 Explain the conceptual difference between them.

---

✅ Core Idea

• Hard link → another name for the same file (same inode)
• Symbolic link (symlink) → a separate file that points to a pathname

---

🔍 Detailed Comparison

🔹 1. Internal Representation

Feature	Hard Link	Symbolic Link
Points to	Same inode	Pathname of file
Nature	Same file, different name	Separate file

👉 Hard links are indistinguishable from the original file
👉 Symlinks are like shortcuts

---

🔹 2. Dependency on Original File

• Hard link:
  • File exists as long as at least one link exists
  • Deleting original name does NOT delete data
• Symbolic link:
  • If original file is deleted → becomes dangling link

---

🔹 3. Storage Behavior

• Hard link:
  • No extra storage (just directory entry)
• Symbolic link:
  • Stores path of target file

---

🔹 4. Access Behavior

• Hard link:
  • Direct access → no indirection
• Symbolic link:
• OS must resolve path → extra lookup

🧩 Example (Linux Commands)

ln file1 file2        # hard link
ln -s file1 file3     # symbolic link

---

📊 Summary Table

Aspect`	Hard Link	Symbolic Link
Type	Same file	Pointer file
Inode	Same	Different
Survives deletion of original	✔️ Yes	❌ No
Cross filesystem	❌ No	✔️ Yes
Directory linking	❌ No	✔️ Yes
Overhead	Low	Slightly higher

---

16a)A disk uses fixed sectors of 512 bytes and has 96 sectors per track. The disk rotates at 360 rpm. A processor reads one sector from the disk using interrupt-driven I/O, where one interrupt is generated for each byte transferred. The processor requires 2.5 μs to service each interrupt. Assume that the desired sector is equally likely to be anywhere on the track when the read request is issued. Ignoring seek time, determine the percentage of the total time for this I/O operation during which the processor is busy servicing interrupts.

Given

• Sector size = 512 bytes
• Sectors per track = 96
• Rotation speed = 360 RPM
• Interrupt per byte
• Interrupt service time = 2.5 μs per byte
• Ignore seek time
• Sector location is random

👉 Find: % of total I/O time CPU is busy handling interrupts

---

🔹 Step 1: Disk Rotation Time

$$360 \text{ RPM} = 6 \text{ rotations/sec}$$
$$\text{Time per rotation} = \frac{1}{6} = 0.1667 \text{ sec} = 166.7 \text{ ms}$$

🔹 Step 2: Average Rotational Latency

Since sector is random:

$$\text{Average latency} = \frac{166.7}{2} = 83.3 \text{ ms}$$

---

🔹 Step 3: Transfer Time for One Sector

• 1 track = 96 sectors
• Time per sector:

$$\frac{166.7}{96} \approx 1.736 \text{ ms}$$

---

🔹 Step 4: Total I/O Time

$$\text{Total time} = \text{latency} + \text{transfer}$$
$$= 83.3 + 1.736 \approx 85.036 \text{ ms}$$

---

🔹 Step 5: CPU Time for Interrupts

• 512 bytes → 512 interrupts
• Each interrupt = 2.5 μs

$$512 \times 2.5 = 1280 \, \mu s = 1.28 \text{ ms}$$

---

🔹 Step 6: Percentage CPU Busy

$$\frac{1.28}{85.036} \times 100 \approx 1.5\%$$

---

🎯 Final Answer

👉 Processor busy ≈ 1.5% of total I/O time

---

📊 Summary

Component	Time
Rotational latency	83.3 ms
Transfer time	1.736 ms
CPU interrupt time	1.28 ms
CPU utilization	~1.5%

16b)Consider a file system that uses inodes to represent files. Disk blocks are 4 KB in size, and a pointer to a disk block requires 8 bytes. Each inode contains 10 direct block pointers, two single-indirect pointers, and three double-indirect pointers. Determine the maximum file size that can be supported by this file system. Show your calculations clearly.

Given

• Block size = 4 KB = 4096 bytes
• Pointer size = 8 bytes
• Inode contains:
  • 10 direct pointers
  • 2 single-indirect pointers
  • 3 double-indirect pointers

👉 Find the maximum file size

---

🔹 Step 1: Pointers per Block

$$\frac{4096}{8} = 512 \text{ pointers per block}$$

---

🔹 Step 2: Contribution of Each Type

✅ (a) Direct Blocks

• 10 pointers → 10 blocks

$$10 \times 4\text{ KB} = 40 \text{ KB}$$

---

✅ (b) Single Indirect Blocks

Each single-indirect pointer:

• Points to 1 block containing 512 pointers
• Each pointer → 1 data block

So:

$$512 \text{ blocks per pointer}$$

For 2 such pointers:

$$2 \times 512 = 1024 \text{ blocks}$$
$$1024 \times 4\text{ KB} = 4096 \text{ KB} = 4 \text{ MB}$$

---

✅ (c) Double Indirect Blocks

Each double-indirect pointer:

• First level: 512 pointers
• Each points to a block with 512 pointers

$$512 \times 512 = 262,144 \text{ blocks}$$

For 3 such pointers:

$$3 \times 262,144 = 786,432 \text{ blocks}$$
$$786,432 \times 4\text{ KB} = 3,145,728 \text{ KB}$$

---

🔹 Step 3: Total Blocks

$$10 + 1024 + 786,432 = 787,466 \text{ blocks}$$

---

🔹 Step 4: Total File Size

$$787,466 \times 4096 = 3,225,460,736 \text{ bytes}$$

---

🎯 Final Answer

👉 Maximum file size ≈ 3.0 GB

---

📊 Summary

Type	Blocks	Size
Direct	10	40 KB
Single indirect	1024	4 MB
Double indirect	786,432	~3 GB
Total	787,466	≈ 3.0 GB