Group C — Long / Numerical Questions (15 Marks Each)

Banker's Algorithm & Deadlock Recovery

Part (a): Solving Banker's Algorithm

Given Matrices:

1. Calculate Need Matrix (\(Need = Max - Allocation\)):

• P0: (7-0, 5-1, 3-0) = 7, 4, 3
• P1: (3-2, 2-0, 2-0) = 1, 2, 2
• P2: (9-3, 0-0, 2-2) = 6, 0, 0
• P3: (2-2, 2-1, 2-1) = 0, 1, 1
• P4: (4-0, 3-0, 3-2) = 4, 3, 1

2. Find Safe Sequence:

• Initial Work = (3, 3, 2)
• Check P0: Need (7, 4, 3) ≤ Work (3, 3, 2)? False.
• Check P1: Need (1, 2, 2) ≤ Work (3, 3, 2)? True.
  Execute P1. New Work = (3, 3, 2) + Allocation(2, 0, 0) = (5, 3, 2)
• Check P2: Need (6, 0, 0) ≤ Work (5, 3, 2)? False.
• Check P3: Need (0, 1, 1) ≤ Work (5, 3, 2)? True.
  Execute P3. New Work = (5, 3, 2) + Allocation(2, 1, 1) = (7, 4, 3)
• Check P4: Need (4, 3, 1) ≤ Work (7, 4, 3)? True.
  Execute P4. New Work = (7, 4, 3) + Allocation(0, 0, 2) = (7, 4, 5)
• Check P0: Need (7, 4, 3) ≤ Work (7, 4, 5)? True.
  Execute P0. New Work = (7, 4, 5) + Allocation(0, 1, 0) = (7, 5, 5)
• Check P2: Need (6, 0, 0) ≤ Work (7, 5, 5)? True.
  Execute P2. New Work = (7, 5, 5) + Allocation(3, 0, 2) = (10, 5, 7)

Safe Sequence: <P1, P3, P4, P0, P2>

3. Request from P1 for (1,0,2):

• Check Request ≤ Need: (1, 0, 2) ≤ (1, 2, 2)? True.
• Check Request ≤ Available: (1, 0, 2) ≤ (3, 3, 2)? True.
• Simulate allocation:
  New Available = (3, 3, 2) - (1, 0, 2) = (2, 3, 0)
  New Allocation P1 = (2, 0, 0) + (1, 0, 2) = (3, 0, 2)
  New Need P1 = (1, 2, 2) - (1, 0, 2) = (0, 2, 0)
• Run Safety Algorithm with new Available (2, 3, 0).
  - P3's need (0,1,1) ≤ (2,3,0)? False.
  - P1's need (0,2,0) ≤ (2,3,0)? True. Run P1. Work = (2,3,0) + (3,0,2) = (5,3,2).
  - P3's need (0,1,1) ≤ (5,3,2)? True. Run P3. Work = (5,3,2) + (2,1,1) = (7,4,3).
  - P4's need (4,3,1) ≤ (7,4,3)? True. Run P4. Work = (7,4,3) + (0,0,2) = (7,4,5).
  - P0's need (7,4,3) ≤ (7,4,5)? True. Run P0. Work = (7,4,5) + (0,1,0) = (7,5,5).
  - P2's need (6,0,0) ≤ (7,5,5)? True.
• The new state is safe. Request granted immediately.

Part (b): Deadlock Recovery Techniques

If a system allows deadlocks to occur, it must detect them and recover. Recovery methods include:

1. Process Termination:
   • Abort all deadlocked processes: Fast but loses all partial computations.
   • Abort one process at a time: Abort one, re-run deadlock detection, repeat until cycle breaks. Overhead is high.
2. Resource Preemption:
   • Selecting a Victim: Choose a process to preempt resources from based on cost (e.g., lower priority, has consumed less CPU time).
   • Rollback: Return the victim process to a previous safe state (checkpoint) and restart it from there.
   • Starvation Check: Ensure the same process isn't always chosen as the victim.

Page Replacement Algorithms

Part (a): Calculate Page Faults

Reference String: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7. Frames = 3.

Total FIFO Faults = 11

Total LRU Faults = 10

Total OPT Faults = 8

Part (b): Belady's Anomaly Example

Belady's Anomaly states that for certain reference strings, increasing the number of physical frames can increase the number of page faults when using the FIFO algorithm.

Reference String: 0, 1, 2, 3, 0, 1, 4, 0, 1, 2, 3, 4

• With 3 Frames (FIFO): The string generates 9 page faults.
• With 4 Frames (FIFO): The same string generates 10 page faults.

This contradicts intuition. It happens because FIFO lacks the stack property (the set of pages in memory with N frames is not always a subset of the pages with N+1 frames).

Disk Scheduling Algorithms

Part (a): Head Movement Calculation

Queue: 98, 183, 37, 122, 14, 124, 65, 67. Current Head = 53. Cylinders: 0 to 199.

• Sequence: 53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183
• Calculations: |53-65| + |65-67| + |67-37| + |37-14| + |14-98| + |98-122| + |122-124| + |124-183|
• = 12 + 2 + 30 + 23 + 84 + 24 + 2 + 59 = 236 cylinders

• Head moves from 53 towards 199, servicing requests in path, hits the end (199), and reverses.
• Sequence: 53 → 65 → 67 → 98 → 122 → 124 → 183 → 199 (End) → 37 → 14
• Calculations: (199 - 53) + (199 - 14)
• = 146 + 185 = 331 cylinders

• Head moves to 199, immediately jumps to 0 without servicing, then services remaining.
• Sequence: 53 → 65 → 67 → 98 → 122 → 124 → 183 → 199 (End) → 0 (Jump) → 14 → 37
• Calculations: (199 - 53) + (199 - 0) + (37 - 0)
• = 146 + 199 + 37 = 382 cylinders

Part (b): SSTF vs SCAN Performance

• SSTF minimizes average seek time by always choosing the closest request. However, it can cause starvation for requests at the edges of the disk if a heavy stream of requests arrives near the current head position.
• SCAN provides a more bounded waiting time and prevents starvation by systematically sweeping the disk. Its total head movement is slightly higher than SSTF, but its variance in response time is much lower, making it fairer under heavy loads.

Round Robin Scheduling

Part (a): Solving Round Robin (Quantum = 2)

Given: P1(0,5), P2(1,3), P3(2,1), P4(3,2), P5(4,4). (Format: Arrival, Burst)

• T=0: P1 arrives. RQ = [P1]. Execute P1 for 2ms. (Remaining: P1=3).
• T=1: P2 arrives. RQ = [P2].
• T=2: P3 arrives. P1 quantum expires. RQ = [P2, P3, P1]. Execute P2 for 2ms. (Remaining: P2=1).
• T=3: P4 arrives. RQ = [P3, P1, P4].
• T=4: P5 arrives. P2 quantum expires. RQ = [P3, P1, P4, P5, P2]. Execute P3 for 1ms.
• T=5: P3 finishes. RQ = [P1, P4, P5, P2]. Execute P1 for 2ms. (Remaining: P1=1).
• T=7: P1 quantum expires. RQ = [P4, P5, P2, P1]. Execute P4 for 2ms.
• T=9: P4 finishes. RQ = [P5, P2, P1]. Execute P5 for 2ms. (Remaining: P5=2).
• T=11: P5 quantum expires. RQ = [P2, P1, P5]. Execute P2 for 1ms.
• T=12: P2 finishes. RQ = [P1, P5]. Execute P1 for 1ms.
• T=13: P1 finishes. RQ = [P5]. Execute P5 for 2ms.
• T=15: P5 finishes. All done.

• Average Turnaround Time (TAT): (13 + 11 + 3 + 6 + 11) / 5 = 44 / 5 = 8.8 ms
• Average Waiting Time (WT): (8 + 8 + 2 + 4 + 7) / 5 = 29 / 5 = 5.8 ms

Part (b): Round Robin vs Preemptive Priority

• Round Robin: Treats all processes equally. It is designed for fairness and fast response times in interactive time-sharing systems. Time slices are distributed evenly regardless of process importance.
• Preemptive Priority: Processes are assigned priority levels. The CPU is always given to the highest-priority process. If a low-priority process is running and a high-priority process arrives, the CPU is preempted. It can lead to starvation of low-priority processes (solved via aging).

Hardware Synchronization & Readers-Writers

Part (a): Hardware Synchronization (Test-And-Set & Swap)

Modern processors provide atomic (indivisible) hardware instructions to implement mutual exclusion effectively without software traps.

• Test-And-Set: Atomically reads the original value of a boolean variable and sets it to true.
  boolean TestAndSet(boolean *target) { boolean rv = *target; *target = true; return rv; }
  To implement a mutex lock: a process loops while(TestAndSet(&lock)). The first process sees false, sets it to true, and enters. Others see true and keep spinning.
• Swap: Atomically swaps two boolean variables.
  void Swap(boolean *a, boolean *b) { boolean temp = *a; *a = *b; *b = temp; }
  To implement a lock: a process sets key = true, and loops while(key == true) Swap(&lock, &key). When lock is false, the swap makes key false and lock true, allowing entry.

Part (b): Readers-Writers Problem in C (using Semaphores)

This code ensures multiple readers can read concurrently, but writers have exclusive access.

Virtual Memory Architecture & EAT

Part (a): Virtual Memory, Paging, and TLB

Virtual Memory creates an illusion for processes that they have a massive, contiguous block of memory, even if physical RAM is small and fragmented. It is implemented primarily via Demand Paging.

• Paging & TLB: Logical addresses are split into a Page Number and Offset. The CPU first checks the TLB (Translation Lookaside Buffer), a high-speed hardware cache. If the page mapping is there (TLB Hit), physical address generation is immediate. If not (TLB Miss), it consults the Page Table in main memory.
• Page Fault Handling: If the Page Table indicates the page is invalid (not in RAM), a Page Fault occurs. The OS traps the fault, pauses the process, finds a free physical frame (using a replacement algorithm like LRU if needed), issues a disk I/O to fetch the page, updates the Page Table, and restarts the instruction.

Part (b): Effective Access Time (EAT) Calculation

Given Parameters:

• TLB Hit Ratio (\(h\)) = 80% = 0.80
• TLB Search Time (\(\epsilon\)) = 20 ns
• Memory Access Time (\(m\)) = 100 ns
• Page Fault Rate (\(p\)) = Assume 0 for baseline TLB calculation, but wait, the question implies EAT with page faults. If page fault rate \(p\) is not given, we assume \(p = 0\) for the memory access phase, or the question implies a separate calculation. Assuming standard TLB EAT without page faults:

Formula: \(EAT = h \times (\epsilon + m) + (1-h) \times (\epsilon + 2m)\)

\(EAT = 0.80 \times (20 + 100) + 0.20 \times (20 + 200)\)

\(EAT = 0.80 \times 120 + 0.20 \times 220 = 96 + 44 = \mathbf{140 \text{ ns}}\)

(Note: The 10ms page fault service time is irrelevant unless a specific page fault rate 'p' is provided. If \(p\) was provided, the formula expands to: \((1-p) \times 140\text{ns} + p \times 10\text{ms}\)).

UNIX Inode Structure

Part (a): Inode Structure and Disk Organization

In UNIX, directories do not contain file data or metadata directly. A directory simply maps a human-readable filename to an Inode Number. The Inode (Index Node) is a data structure on the disk that stores all metadata (owner, permissions, timestamps, size) and the locations of the data blocks.

To balance the need for fast access to small files and support for massive files, the Inode uses a hierarchical pointer structure containing direct, single-indirect, double-indirect, and triple-indirect pointers.

Part (b): Calculate Max File Size

Given:

• Block Size = 4 KB = 4096 bytes
• Pointer Size = 4 bytes
• Number of pointers per block = \(\frac{4096}{4} = 1024\) pointers.

Calculations:

1. 12 Direct Pointers:
   Capacity = \(12 \times 4 \text{ KB} = 48 \text{ KB}\)
2. 1 Single Indirect Pointer: Points to 1 block containing 1024 direct pointers.
   Capacity = \(1024 \times 4 \text{ KB} = 4096 \text{ KB} = 4 \text{ MB}\)
3. 1 Double Indirect Pointer: Points to 1 block containing 1024 single indirect pointers.
   Capacity = \(1024 \times 1024 \times 4 \text{ KB} = 1,048,576 \times 4 \text{ KB} = 4 \text{ GB}\)
4. 1 Triple Indirect Pointer: Points to 1 block containing 1024 double indirect pointers.
   Capacity = \(1024 \times 1024 \times 1024 \times 4 \text{ KB} = 1,073,741,824 \times 4 \text{ KB} = 4 \text{ TB}\)

Maximum File Size = 48 KB + 4 MB + 4 GB + 4 TB ≈ 4.004 Terabytes (TB)

Segmentation with Paging

Part (a): Architecture overview

Both Segmentation and Paging have advantages: Segmentation aligns with the user's logical view of memory (functions, arrays, stack), while Paging eliminates external fragmentation and simplifies physical memory management. Modern systems (like x86 architecture and MULTICS) combine them by paging the segments.

Instead of storing an entire variable-length segment contiguously in physical memory, the OS divides each segment into standard-sized pages. The physical memory remains divided into frames.

Part (b): Address Translation Pipeline

The CPU generates a Logical Address formatted as: [Segment Number (s), Offset (d)].

1. Segment Table Lookup: The CPU uses s to index into the Segment Table. Instead of yielding a physical base address, the Segment Table entry provides the base address of a Page Table specifically created for segment s. It also checks if d is less than the segment limit.
2. Offset Splitting: The offset d is further split into a Page Number p and a Page Offset d'.
3. Page Table Lookup: The CPU uses p to index into the specific Page Table for segment s. This yields the Physical Frame Number f.
4. Physical Address Generation: The physical address is generated by appending the Page Offset d' to the Frame Number f.

Process Synchronization in Kernels

Part (a): Sync in Linux / Windows Kernels

Operating System kernels are heavily multithreaded and handle asynchronous interrupts. If two CPUs access kernel data structures (like the process queue) simultaneously, data corruption occurs. Hence, kernels employ strict internal synchronization primitives.

Part (b): Primitives Explained

• Atomic Operations: The simplest primitive. Mathematical operations (like atomic_inc(&counter)) execute in a single, uninterruptible hardware clock cycle. Used for simple counters without the overhead of locking.
• Spinlocks: A lock where the thread simply waits in a while loop ("spins") repeatedly checking if the lock is available.
  • Pros: No context-switching overhead.
  • Cons: Wastes CPU cycles. Only used in Multiprocessor kernels for very short critical sections (e.g., inside interrupt handlers where context switching is forbidden).
• Mutexes (Mutual Exclusion): A sleeping lock. If the lock is held, the requesting thread is put to sleep (blocked) and placed in a wait queue until the lock is freed.
  • Pros: Frees the CPU to do other work.
  • Cons: Context-switch overhead. Used for long critical sections.
• Reader-Writer Locks: A specialized lock that allows multiple threads to hold the lock simultaneously for reading, but demands exclusive access for writing. Improves concurrency for data structures that are read frequently but modified rarely.

Deadlock Detection Algorithm

Part (a): The Algorithm for Multiple Resources

If a system does not employ Deadlock Prevention or Avoidance, it must periodically run a Detection algorithm to see if a circular wait has formed. The algorithm uses Available, Allocation, and Request matrices.

1. Initialize Work = Available.
2. Initialize Finish[i] = false if Allocation[i] ≠ 0; otherwise Finish[i] = true.
3. Find an index \(i\) such that both:
   a) Finish[i] == false
   b) Request[i] ≤ Work
   If no such \(i\) exists, go to Step 5.
4. Simulate release of resources:
   Work = Work + Allocation[i]
Finish[i] = true
   Go back to Step 3.
5. If Finish[i] == false for any \(i\), then the system is in a Deadlock state, and process \(P_i\) is deadlocked.

Part (b): Example Execution

Suppose 3 processes and 3 resources (A,B,C). Available = (0,0,0).

• Work = (0,0,0). Finish = [F, F, F, F]
• P1's Request (0,0,0) ≤ Work (0,0,0). True. Run P1. Work = (0,0,0)+(0,1,0) = (0,1,0). Finish[P1]=T.
• P3's Request (0,0,0) ≤ Work (0,1,0). True. Run P3. Work = (0,1,0)+(3,0,3) = (3,1,3). Finish[P3]=T.
• P4's Request (1,0,0) ≤ Work (3,1,3). True. Run P4. Work = (3,1,3)+(2,1,1) = (5,2,4). Finish[P4]=T.
• P2's Request (2,0,2) ≤ Work (5,2,4). True. Run P2. Work = (5,2,4)+(2,0,0) = (7,2,4). Finish[P2]=T.

All processes finished (Finish == True). No Deadlock exists.

Shared Memory vs Message Passing IPC

Part (a): Comparison of IPC Mechanisms

Inter-Process Communication (IPC) is required for independent processes to share data.

• Shared Memory: The OS creates a shared region of memory that both processes can map into their logical address space. Once established, all data exchange is treated as routine memory access without OS assistance.
  Advantages: Extremely fast. Ideal for large amounts of data.
  Disadvantages: Requires processes to manage synchronization (using semaphores) to avoid race conditions.
• Message Passing: Processes communicate by exchanging discrete messages via OS system calls (e.g., send() and receive()).
  Advantages: Easier to set up for small data. Built-in synchronization (receivers block until a message arrives). Scales well across networks (distributed systems).
  Disadvantages: Slower, as every message requires a context switch into the kernel.

Part (b): POSIX Shared Memory in C

Below is a simplified example of creating and writing to shared memory.

File System Implementation

Part (a): Directory Entry, FAT, and Inode

• Directory Entry: A directory is a file that contains a list of directory entries. Each entry maps a human-readable file name to a unique file identifier (like an inode number) or directly to the starting disk block.
• File Allocation Table (FAT): Used by older OSs (MS-DOS). The start of the disk partition contains a table with one entry for every disk block. The directory points to the first block of the file. The FAT entry for the first block contains the block number of the next block, forming a linked list.
• Inode Implementation: Used by UNIX/Linux. Each file is represented by an Inode data structure stored on disk. The inode contains file attributes and an array of direct and indirect pointers to the data blocks. Directories only map names to Inode numbers.

Part (b): FAT-32 vs ext4

Memory Protection & Page Tables

Part (a): Memory Protection Techniques

Memory protection ensures a process cannot access memory outside its allocated space.

• Base & Limit Registers: Used in contiguous allocation and segmentation. The Base register holds the smallest legal physical address. The Limit register holds the size of the range. The CPU hardware checks every generated address against these registers and traps to the OS on violation.
• Page Table Protection Bits: Used in paging. Each page table entry has a Valid/Invalid bit (valid means the page is in RAM and belongs to the process). It also has permission bits like Read, Write, and Execute (R/W/X). If a process tries to write to a read-only page, a hardware trap occurs.

Part (b): Page Table Structures

• Hierarchical (Multi-level) Page Tables: For 32-bit or 64-bit systems, a single continuous page table is too large. The page table itself is broken into pages. The logical address is split into multiple page numbers (e.g., outer page table, inner page table, offset).
• Hashed Page Tables: Used for address spaces > 32 bits. The logical page number is hashed. The hash table entry contains a linked list of elements (handling collisions). The CPU traverses the list to match the logical page number and fetch the physical frame.
• Inverted Page Tables: Instead of one page table per process, there is exactly one page table for the entire system, indexed by the Physical Frame number. It reduces memory usage drastically but requires a hash map to speed up the translation from logical page to physical frame.

Distributed Systems & Logical Clocks

Part (a): Network OS vs Distributed OS

Part (b): Logical Clocks and Lamport's Timestamps

In distributed systems, there is no shared global memory and no perfect global physical clock. Therefore, determining the exact order of events across different machines is difficult.

Lamport's Logical Clocks provide a way to establish a partial ordering of events based on the "happens-before" relation (\(\rightarrow\)).

1. Each process \(P_i\) maintains a local counter, \(L_i\), initialized to 0.
2. Before executing any event (internal, send, or receive), \(P_i\) increments its counter: \(L_i = L_i + 1\).
3. When \(P_i\) sends a message \(m\), it attaches its current clock value: \((m, L_i)\).
4. When process \(P_j\) receives \((m, L_i)\), it updates its own clock to be strictly greater than the sender's clock and its own previous clock: \(L_j = \max(L_j, L_i) + 1\).

If Event A happens before Event B (\(A \rightarrow B\)), then the Lamport timestamp of A is strictly less than B: \(L(A) < L(B)\).

Real-Time CPU Scheduling

Part (a): Rate Monotonic vs Earliest Deadline First

• Rate Monotonic Scheduling (RMS): A static-priority algorithm. The priority of a periodic task is inversely proportional to its period. (Shorter period = Higher priority). It is easy to implement but cannot always guarantee scheduling if CPU utilization exceeds ~69%.
• Earliest Deadline First (EDF): A dynamic-priority algorithm. The priority of a task changes based on how close its absolute deadline is. The task whose deadline is closest gets the highest priority. It can achieve 100% CPU utilization.

Part (b): Solving EDF Scheduling for 2 Periodic Tasks

Given 2 Tasks:

• Task 1 (T1): Execution Time (\(E_1\)) = 1, Period (\(P_1\)) = 4
• Task 2 (T2): Execution Time (\(E_2\)) = 2, Period (\(P_2\)) = 5

Check Schedulability (Utilization): \(U = (1/4) + (2/5) = 0.25 + 0.40 = 0.65\). Since \(0.65 \le 1.0\), it is fully schedulable by EDF.

EDF Trace (Hyperperiod = LCM(4,5) = 20):

• T=0: Both arrive. T1 deadline=4, T2 deadline=5. T1 has earlier deadline. Run T1 (0 to 1).
• T=1: T1 done. Run T2 (1 to 3). T2 done.
• T=3: Idle.
• T=4: T1 arrives. Deadline=8. Run T1 (4 to 5).
• T=5: T2 arrives. Deadline=10. Run T2 (5 to 7).
• T=7: Idle.
• T=8: T1 arrives. Deadline=12. Run T1 (8 to 9).
• T=9: Idle.
• T=10: T2 arrives. Deadline=15. Run T2 (10 to 12).
• T=12: T1 arrives. Deadline=16. Run T1 (12 to 13).

The scheduler dynamically re-evaluates the absolute deadlines at each period boundary.

Threading Models & POSIX Threads

Part (a): Threading Models

Modern OSs map user-level threads (created by libraries) to kernel-level threads (managed by the OS) using different models:

1. Many-to-One: Many user-level threads map to a single kernel thread. Thread management is fast (done in user space), but if one thread makes a blocking system call, the entire process blocks. Cannot run in parallel on multicore systems.
2. One-to-One: Each user-level thread maps directly to one kernel thread (used by Windows, Linux). Allows true parallelism on multicores. Drawback: creating a user thread requires creating a kernel thread, which has overhead.
3. Many-to-Many: Multiplexes many user-level threads to a smaller or equal number of kernel threads. Combines the best of both worlds, but is extremely complex to implement.

Part (b): POSIX Threads (pthreads) API

The pthreads API is a POSIX standard for thread creation and synchronization used heavily in UNIX/Linux systems.

• pthread_create(): Creates a new thread and passes it a function to execute.
• pthread_join(): Suspends the calling thread (usually the main thread) until the specified target thread terminates.
• pthread_exit(): Terminates the calling thread.
• pthread_mutex_lock() / unlock(): Used to protect critical sections and prevent race conditions between threads.

I/O System Architecture & DMA

Part (a): I/O Transfer Mechanisms

• Programmed I/O (Polling): The CPU repeatedly checks a status register on the I/O device to see if it is ready. This wastes an enormous amount of CPU cycles (busy-waiting).
• Interrupt-Driven I/O: The CPU starts the I/O transfer and goes to do other work. When the device is ready or finished, it sends an interrupt signal to the CPU over the system bus. The CPU halts, runs the ISR, and resumes.
• Direct Memory Access (DMA): For bulk data transfers (like disk reads). A specialized DMA Controller takes over the system bus to transfer data directly between the I/O device and Main Memory, bypassing the CPU entirely.

Part (b): DMA Controller Working Cycle

1. The CPU writes a command block to the DMA Controller containing: source address, destination address in memory, read/write instruction, and byte count.
2. The CPU issues a "start" command to the DMA and resumes other process execution.
3. The DMA Controller requests control of the system bus. Through a technique called cycle stealing, it grabs the bus for one memory cycle to transfer a block of data directly to RAM.
4. The DMA decrements the byte count. It repeats step 3 until the count reaches zero.
5. Once the entire transfer is complete, the DMA Controller sends a single interrupt to the CPU to signal completion.

Security, Protection & Buffer Overflows

Part (a): Security and Protection Mechanisms

• Authentication: Verifying the identity of a user or system (e.g., passwords, biometrics, 2FA, RSA keys).
• Access Control: Enforcing policies on what authenticated users can do (e.g., Access Control Matrix, ACLs, Role-Based Access Control).
• Protection: Internal OS mechanisms ensuring processes cannot interfere with each other (e.g., Memory protection using Base/Limit registers, Dual Mode operation: User vs Kernel mode).

Part (b): Buffer Overflow exploit and protection

The Exploit: A Buffer Overflow occurs when a program writes more data to a fixed-length memory block (buffer) than it was allocated for, usually on the call stack. By overflowing a local array variable, an attacker can overwrite the adjacent Return Address of the function. When the function finishes, instead of returning to the caller, the CPU jumps to the overwritten address, executing malicious shellcode injected by the attacker.

Stack Protection Mechanisms:

• Stack Canaries: The compiler injects a random secret integer (canary) onto the stack between local variables and the return address. Before the function returns, it checks if the canary was altered. If it changed, a buffer overflow occurred, and the OS terminates the program immediately.
• ASLR (Address Space Layout Randomization): Randomizes the memory locations of the stack, heap, and libraries every time the program runs, making it nearly impossible for the attacker to guess the exact memory address to jump to.
• NX Bit (No-eXecute): Hardware feature marking stack memory as non-executable. Even if the attacker injects shellcode on the stack, the CPU refuses to run it.

Free Space Management on Disk

Part (a): Free Space Management Techniques

• Bit Vector: 1 bit per disk block (1 = free, 0 = allocated). Fast for finding contiguous blocks using bit-manipulation, but takes up RAM.
• Linked List: Link free blocks together. No extra space overhead, but traversing the list to find multiple blocks is horribly slow (requires disk seeks).
• Grouping: Store the addresses of \(N\) free blocks in the first free block. The first \(N-1\) addresses point to actual free data blocks, and the \(N\)-th address points to another block that contains the addresses of the next \(N\) free blocks. Faster than linked list.
• Counting (Extents): Because space is often allocated in contiguous runs, the OS keeps a list of entries formatted as: [Start Block Address, Count of contiguous free blocks]. Excellent for Contiguous Allocation systems.

Part (b): Calculate Bit Vector Size

Given: Disk Size = 1 TB, Block Size = 4 KB.

1. Calculate total number of blocks on disk:
   Total Blocks = \(\frac{1 \text{ TB}}{4 \text{ KB}} = \frac{1024 \text{ GB}}{4 \text{ KB}} = \frac{1024 \times 1024 \text{ MB}}{4 \text{ KB}} = \frac{1024 \times 1024 \times 1024 \text{ KB}}{4 \text{ KB}}\)
   Total Blocks = \(1024 \times 1024 \times 256 = 268,435,456\) blocks.
2. Since each block requires 1 bit in the Bit Vector:
   Bit Vector Size = 268,435,456 bits.
3. Convert to Bytes:
   Size in Bytes = \(\frac{268,435,456}{8} = 33,554,432\) bytes.
4. Convert to Megabytes:
   Size in MB = \(\frac{33,554,432}{1024 \times 1024} = 32 \text{ MB}\).

The Bit Vector requires 32 MB of memory.

Complete OS Case Study: File I/O

Part (a) & (b): Tracing a User Program Reading a File

Let's trace what happens when a user program calls open("test.txt"), read(), and printf().

1. System Call & Mode Switch: The C library translates open() into a software trap (interrupt). The CPU switches from User Mode (unprivileged) to Kernel Mode (privileged) and jumps to the System Call Handler in the OS kernel.
2. VFS and File System: The OS Virtual File System layer receives the request, parses the path, and asks the specific file system driver (e.g., ext4) to locate the file's Inode on disk.
3. Buffer Cache & Disk I/O: When read() is called, the OS first checks the Buffer Cache in RAM. If the file data isn't there (Cache Miss), the OS instructs the Disk Device Driver to fetch it.
4. Interrupt & Context Switch: Disk I/O is slow. The OS puts the user process to sleep (Blocked state) and context-switches to another Ready process to keep the CPU busy.
5. DMA and ISR: The Disk Controller uses DMA to transfer the file data directly into kernel RAM. Once done, it fires a hardware interrupt. The CPU halts its current work and runs the Interrupt Service Routine (ISR).
6. Wakeup & Return: The ISR marks the waiting process as Ready. The OS copies the data from kernel buffer to the user program's buffer and switches the CPU back to User Mode.
7. Console Output: printf() translates to a write() system call to the terminal device file, triggering the graphics/terminal driver to render the characters on the screen.

SJF and SRTF Scheduling

Part (a) & (b): Non-Preemptive SJF vs Preemptive SRTF

Given: P1(0,8), P2(1,4), P3(2,2), P4(3,1), P5(4,3). (Format: Arrival, Burst)

Once a process gets the CPU, it cannot be interrupted until it finishes. If multiple processes are in the Ready Queue, the one with the shortest burst time is selected.

• T=0: P1 arrives. Runs for 8ms.
• T=1 to 4: P2, P3, P4, P5 arrive and wait.
• T=8: P1 finishes. Queue: [P2(4), P3(2), P4(1), P5(3)]. Shortest is P4.
• T=8: P4 runs for 1ms.
• T=9: P4 finishes. Queue: [P2(4), P3(2), P5(3)]. Shortest is P3.
• T=9: P3 runs for 2ms.
• T=11: P3 finishes. Queue: [P2(4), P5(3)]. Shortest is P5.
• T=11: P5 runs for 3ms.
• T=14: P5 finishes. Queue: [P2(4)].
• T=14: P2 runs for 4ms. Finishes at 18.

Average WT (SJF) = (0+13+7+5+7)/5 = 32/5 = 6.4 ms

If a new process arrives with a burst shorter than the remaining time of the running process, preempt.

• T=0: P1 runs. Remaining: P1(8).
• T=1: P2 arrives (4). P1 remaining is 7. 4 < 7. Preempt P1! P2 runs.
• T=2: P3 arrives (2). P2 remaining is 3. 2 < 3. Preempt P2! P3 runs.
• T=3: P4 arrives (1). P3 remaining is 1. Tie. Let P3 continue (or P4, assume P3). P3 runs.
• T=4: P3 finishes. P5 arrives (3). Queue: [P1(7), P2(3), P4(1), P5(3)]. Shortest is P4. P4 runs.
• T=5: P4 finishes. Queue: [P1(7), P2(3), P5(3)]. Tie P2 and P5. Run P2.
• T=8: P2 finishes. Queue: [P1(7), P5(3)]. Run P5.
• T=11: P5 finishes. Run P1.
• T=18: P1 finishes.

Average WT (SRTF) = (10+3+0+1+4)/5 = 18/5 = 3.6 ms

Dining Philosophers using Monitors

Part (a): Solution Design

A Monitor is a high-level synchronization construct provided by programming languages (like Java) that encapsulates shared variables and the procedures that operate on them. Only one process can be active inside a monitor at a time.

To avoid deadlock in the Dining Philosophers problem using a monitor, a philosopher can only pick up chopsticks if both the left and right chopsticks are available. This is tracked using a state array (THINKING, HUNGRY, EATING) for each philosopher.

Part (b): Monitor Code

Two-Phase Locking (2PL) Protocol

Part (a): Two-Phase Locking (2PL)

In database and OS transaction systems, 2PL ensures Serializability (the concurrent execution of transactions leaves the database in the same state as if they were executed sequentially).

A transaction under 2PL must acquire and release locks in two distinct phases:

1. Growing Phase: The transaction can acquire locks (Shared or Exclusive) but cannot release any locks.
2. Shrinking Phase: Once the transaction releases its first lock, it enters this phase. It can release locks but cannot acquire any new ones.

Note: While 2PL guarantees serializability, it does not prevent Deadlocks.

Part (b): Strict 2PL vs Rigorous 2PL

• Strict 2PL: A transaction obeys 2PL, but additionally, it holds all its Exclusive (Write) locks until the transaction commits or aborts.
  • Benefit: Prevents "Cascading Rollbacks" (where aborting one transaction forces others to abort because they read uncommitted data).
• Rigorous 2PL: A transaction holds ALL locks (both Shared/Read and Exclusive/Write) until it commits or aborts.
  • Benefit: Even easier to implement and recover from crashes than Strict 2PL, though it restricts concurrency slightly more.

Swap Space Management

Part (a): Swap Space in Linux/UNIX

Swap space is a dedicated area on a hard disk used as an extension of main memory (Virtual Memory). When physical RAM becomes full, the OS moves inactive pages out of RAM and stores them in the swap space (Swapping/Paging out) to free up memory for active processes.

Because disk I/O is vastly slower than RAM access, the management of swap space heavily impacts system performance. The OS attempts to optimize swap space for speed rather than storage efficiency (e.g., allocating swap blocks contiguously to minimize seek times).

Part (b): Swap Partition vs Swap File

• Swap Partition: A dedicated raw partition on the hard drive.
  • Pros: Maximum performance. The OS bypasses the file system entirely and uses raw block I/O, eliminating file system overhead (like updating inodes or fragmentation checks).
  • Cons: Inflexible. Resizing a raw partition is difficult and dangerous.
• Swap File: A large, pre-allocated file within the standard file system (e.g., pagefile.sys in Windows or a .swap file in Linux).
  • Pros: Highly flexible. Can be created, resized, or deleted easily without repartitioning the drive.
  • Cons: Slightly slower due to file system overhead, although modern OS optimizations make the performance difference negligible on SSDs.

Memory Fragmentation & Compaction

Part (a): Fragmentation Algorithms

• External Fragmentation: Exists when there is enough total free memory to satisfy a process request, but the memory is not contiguous (split into small, unusable holes). Happens in variable-partition contiguous allocation.
• Internal Fragmentation: Exists when a process is allocated a fixed-size block (page) that is slightly larger than what it requested. The leftover space inside the block is wasted.
• Compaction: The algorithmic solution to External Fragmentation. The OS pauses all user processes and physically copies all allocated memory segments to one end of the RAM, consolidating all the small free holes into one massive, contiguous free block at the other end.

Part (b): Execution Trace of Compaction

Assume physical memory is 100MB. Current layout:

• [0-20MB]: OS (Fixed)
• [20-40MB]: Process A
• [40-50MB]: Free Hole (10MB)
• [50-80MB]: Process B
• [80-100MB]: Free Hole (20MB)

Total Free = 30MB. Request: Process C needs 25MB. Fails due to external fragmentation.

Compaction Execution:

1. The OS identifies Process B (30MB size) is sitting after a 10MB hole.
2. The OS calculates Process B's new Base Address: 40MB.
3. The OS copies the 30MB chunk of data from address 50MB to address 40MB.
4. The OS updates Process B's Relocation Register (Base register) to 40MB.
5. The free holes are merged: Memory from 70MB to 100MB is now a single 30MB contiguous free block.
6. Process C (25MB) is allocated at 70MB.

System Call Implementation

Part (a): Interrupt Vectors and Software Traps

A System Call provides an interface for user programs to request privileged services from the OS kernel (like file I/O or process creation).

1. The user program calls a wrapper function in the C Library (e.g., read()).
2. The C Library loads a specific integer representing the system call number into a CPU register (e.g., EAX).
3. The library executes a special hardware instruction known as a Software Trap or Software Interrupt (e.g., int 0x80 on older Linux or syscall on modern x86_64).
4. This instruction flips the CPU into Kernel Mode and looks up an Interrupt Vector Table to find the memory address of the OS's System Call Handler.
5. The Handler uses the integer in the register to index into a table of kernel functions, executes the privileged code, and then returns control to User Mode via an iret instruction.

Part (b): Parameter Passing Methods

Because the kernel runs in a different protected memory space than the user program, passing parameters isn't as simple as standard function calls.

1. Registers: The simplest method. Parameters are placed into CPU registers before the trap. Fast, but limited by the number of hardware registers (usually max 6 parameters).
2. Block/Table in Memory: If there are many parameters, they are stored in a contiguous block in user memory. The address of this block is passed to the kernel in a single register. The kernel then reads the block.
3. Stack: Parameters are pushed onto the user program's stack. The kernel, knowing the stack pointer, pops the parameters off the stack to read them.

File Locking Mechanisms

Part (a): Types of File Locks

File locking ensures data integrity when multiple processes access the same file concurrently.

• Shared Lock (Reader Lock): Multiple processes can acquire a shared lock on a file simultaneously. Prevents any process from acquiring an exclusive lock.
• Exclusive Lock (Writer Lock): Only one process can acquire this lock. Prevents any other process from reading or writing to the file until released.
• Advisory Locking: The OS provides the locking mechanism, but does not enforce it. Processes must willingly check for the lock and respect it. If a rogue process ignores the lock, it can still corrupt the file. (Default in UNIX/Linux).
• Mandatory Locking: The OS strictly enforces the lock at the kernel level. Even if a process ignores the lock, the OS will block its read() or write() system calls. (Default in Windows).

Part (b): fcntl() File Locking Code (C)

Distributed Mutual Exclusion

Part (a): Ricart-Agrawala vs Token Ring

In distributed systems without shared memory, algorithms are required to coordinate critical section (CS) access across network nodes.

• Ricart-Agrawala Algorithm (Permission-Based): When a node wants to enter the CS, it broadcasts a Request message (with a timestamp) to all other \(N-1\) nodes. It can only enter the CS when it receives an OK reply from all \(N-1\) nodes. If two nodes request simultaneously, the one with the older timestamp wins.
• Token Ring Algorithm (Token-Based): Nodes are logically organized in a ring topology. A special message called a Token circulates around the ring. A node can only enter the CS if it possesses the Token. Once finished, it passes the Token to its neighbor.

Part (b): Message Complexity Comparison

Mobile Operating System Architectures

Part (a): Android vs iOS Architectures

• Android Architecture: Built on a modified Linux kernel.
  • Hardware Abstraction Layer (HAL): Provides standard interfaces for hardware vendors.
  • Android Runtime (ART): Compiles Java/Kotlin bytecode into native machine code for execution.
  • Application Framework: Provides APIs for UI, telephony, and location.
• iOS Architecture: Built on the XNU kernel (Darwin/Unix), shared with macOS.
  • Core OS / Core Services: Low-level APIs, SQLite, networking.
  • Media Layer: Audio, video, and Core Graphics engines.
  • Cocoa Touch: The UI framework used to build iOS apps (Swift/Objective-C).

Part (b): Power Management & Background Suspension

Unlike desktop OSs which allow processes to run in the background indefinitely, Mobile OSs aggressively suspend processes to save battery life.

• App Suspension (Tombstoning): When a user switches away from an app, the OS freezes its threads entirely. It consumes RAM but zero CPU/Battery.
• Wake-Locks (Android): If an app must continue running (e.g., playing music, downloading), it must explicitly request a "Wake-Lock" from the OS, preventing the CPU from entering deep sleep.
• Background Fetch (iOS): Instead of letting apps run continuously, the OS wakes suspended apps periodically for a few seconds to fetch new data, then immediately suspends them again.

Kernel Memory Allocation

Part (a): Buddy System vs Slab Allocator

• Buddy System: Allocates memory from a fixed-size segment consisting of physically contiguous pages. Memory is allocated in power-of-2 sizes. If a request is smaller, a large block is repeatedly split in half (buddies) until a tight fit is found. It suffers from internal fragmentation but coalescing free blocks is extremely fast.
• Slab Allocator: Built on top of the buddy system. A cache consists of one or more slabs. A slab is a contiguous page of memory carved into fixed-size chunks tailored for specific kernel data structures (e.g., a cache purely for Inodes, another purely for PCBs). It eliminates internal fragmentation entirely and caches initialized objects for ultra-fast allocation.

Part (b): Buddy System Trace (1MB Total)

Initial State: 1MB block available.

1. Request 100KB:
   • Next power of 2 is 128KB.
   • Split 1024KB → 512KB + 512KB.
   • Split 512KB → 256KB + 256KB.
   • Split 256KB → 128KB + 128KB.
   • Allocate one 128KB block.
   Free blocks remaining: 128KB, 256KB, 512KB.
2. Request 240KB:
   • Next power of 2 is 256KB.
   • An exact 256KB block is already available. Allocate it.
   Free blocks remaining: 128KB, 512KB.
3. Request 60KB:
   • Next power of 2 is 64KB.
   • Split the available 128KB block → 64KB + 64KB.
   • Allocate one 64KB block.
   Free blocks remaining: 64KB, 512KB.