Ans: An Operating System is system software that acts as an intermediary between the user and the computer hardware. It manages all resources (CPU, main memory, I/O devices, files) and provides an environment in which programs can be executed conveniently and efficiently, e.g. UNIX, Linux, Windows.

Ans: The Kernel is the core, memory-resident part of the OS that executes in privileged (kernel) mode and remains loaded for the entire time the machine is on. It directly performs process scheduling, memory management, interrupt handling and device control; everything else runs as user-mode utilities.

Ans: A System Call is the programmatic interface through which a user-mode process requests a service from the kernel. It executes a trap (software interrupt) that switches the CPU from user mode to kernel mode, e.g. fork(), read(), exec().

Ans: The Process Control Block (PCB) is the kernel data structure that represents a process, storing its PID, process state, program counter, CPU registers, scheduling and priority information, memory-management information (base/limit or page-table pointer), accounting data and I/O status. It is the block saved and restored during a context switch.

Ans: Process State defines the current stage of process execution (New, Ready, Running, Waiting, Terminated) managed by the OS scheduler.

Ans: Context Switching is the act of saving the context (program counter and CPU registers) of the currently running process into its PCB and loading the saved context of the next scheduled process. It is pure overhead — no useful user work is done during the switch.

Ans: Throughput is the number of processes completed per unit of time, i.e. \( \text{Throughput} = \dfrac{\text{No. of processes completed}}{\text{Total time}} \). It is a measure of the total work done by the system and should be maximised.

Ans: Turnaround Time (TAT) is the total time elapsed from the submission (arrival) of a process to its completion: \( TAT = CT - AT \). Equivalently \( TAT = WT + BT \), since it includes both waiting and execution time.

Ans: Waiting Time (WT) is the total time a process spends in the ready queue waiting for the CPU: \( WT = TAT - BT \). It excludes time spent executing on the CPU or blocked on I/O.

Ans: Response Time is the time from submission of a request until the first response is produced, i.e. \( RT = \text{Time of first CPU allocation} - AT \). It measures responsiveness in interactive systems, not completion time.

Ans: First-Come First-Served (FCFS) is the simplest non-preemptive scheduling algorithm, in which the CPU is allocated to processes in the order of their arrival using a FIFO ready queue. It is simple but gives a high average waiting time and suffers from the convoy effect.

Ans: The Convoy Effect occurs in FCFS when one long CPU-bound process holds the CPU while many short processes queue behind it, forcing them all to wait. This lowers both CPU and I/O device utilisation and raises the average waiting time.

Ans: Shortest Job First (SJF) selects the process with the smallest CPU burst time. Its preemptive variant is Shortest Remaining Time First (SRTF), which yields optimal minimal average waiting time.

Ans: Shortest Remaining Time First (SRTF) is the preemptive version of SJF: on every new arrival the scheduler compares remaining burst times and preempts the running process if the newcomer has a shorter remaining burst. It gives the provably minimum average waiting time but can starve long processes.

Ans: Round Robin (RR) is a preemptive scheduling algorithm designed for time-sharing systems, in which each process gets the CPU for at most one fixed time quantum; on expiry it is preempted and placed at the tail of the ready queue. It guarantees a bounded response time and is starvation-free.

Ans: The Time Quantum (time slice) is the fixed, small unit of CPU time (typically 10–100 ms) for which a process may run in Round Robin before being preempted. If the quantum is too large RR degenerates into FCFS; if too small, context-switch overhead dominates.

Ans: In Priority Scheduling each process is given a priority number and the CPU is allocated to the process with the highest priority (conventionally the smallest integer); equal priorities are broken by FCFS. It may be preemptive or non-preemptive and suffers from starvation, which is cured by aging.

Ans: Starvation (indefinite blocking) is the situation in which a low-priority process waits in the ready queue indefinitely because a continuous stream of higher-priority processes keeps being scheduled ahead of it.

Ans: Aging is a technique that gradually increases the priority of a process the longer it waits in the ready queue, so that even a low-priority process eventually attains a high enough priority to execute. It is the standard cure for starvation in priority scheduling.

Ans: In Multilevel Queue Scheduling the ready queue is permanently partitioned into several separate queues (e.g. system, interactive, batch), each with its own scheduling algorithm, and a process is permanently assigned to one queue. Scheduling between the queues is done by fixed priority or time-slicing; processes do not migrate (migration is allowed only in Multilevel Feedback Queue).

Ans: A Critical Section is the segment of a process's code in which it accesses shared resources (shared variables, files, tables). The critical-section problem requires that no two processes execute in their critical sections at the same time.

Ans: Mutual Exclusion is the requirement that if one process is executing in its critical section, then no other process may execute in its critical section simultaneously. It is the first of the three requirements of a correct critical-section solution.

Ans: The Progress requirement states that if no process is executing in its critical section and some processes wish to enter, then only those processes not in their remainder section may participate in deciding which enters next, and this selection cannot be postponed indefinitely.

Ans: Bounded Waiting requires that there exists a bound (limit) on the number of times other processes are allowed to enter their critical sections after a process has made a request to enter and before that request is granted. It prevents starvation of any waiting process.

Ans: A Semaphore is an integer variable \(S\) that, apart from initialisation, can be accessed only through two indivisible (atomic) operations — wait(S) / P which decrements and blocks if \(S < 0\), and signal(S) / V which increments and wakes a blocked process. It is used for mutual exclusion and process synchronisation.

Ans: A Binary Semaphore takes only the values 0 and 1 and therefore behaves as a lock providing mutual exclusion over a single resource. A Mutex is a binary lock with ownership — only the process that locked it is allowed to unlock it.

Ans: A Counting Semaphore is a semaphore whose value may range over an unrestricted domain and is initialised to the number of available instances of a resource. Each wait() consumes one instance and each signal() releases one, so it controls access to a resource having multiple identical instances.

Ans: Busy Waiting occurs when a process waiting to enter its critical section continuously loops testing a lock variable, wasting CPU cycles; a lock implemented this way is called a Spinlock. It is acceptable only on multiprocessors when the expected waiting time is shorter than the cost of a context switch.

Ans: Deadlock is a situation in which a set of processes is permanently blocked because every process in the set is holding a resource and waiting to acquire a resource held by another process in the same set, so none can ever proceed.

Ans: The four necessary conditions, all of which must hold simultaneously, are: (i) Mutual Exclusion, (ii) Hold and Wait, (iii) No Preemption, and (iv) Circular Wait (Coffman conditions).

Ans: A Resource Allocation Graph (RAG) is a directed graph with process vertices (circles) and resource vertices (rectangles), a request edge \(P_i \rightarrow R_j\) and an assignment edge \(R_j \rightarrow P_i\). If every resource type has a single instance, a cycle implies deadlock; with multiple instances a cycle is only a necessary, not sufficient, condition.

Ans: Deadlock Prevention is a set of static restrictions on how resource requests may be made, designed so that at least one of the four necessary conditions can never hold (e.g. request all resources at once, or impose a total ordering on resources). It guarantees no deadlock but causes low device utilisation and reduced throughput.

Ans: Deadlock Avoidance requires each process to declare in advance the maximum number of resources of each type it may need; before granting any request the system dynamically checks whether the resulting state is safe, and grants it only if it is. Banker's algorithm is the standard example.

Ans: Banker's Algorithm (Dijkstra) is a deadlock avoidance algorithm that evaluates if allocating requested resources leaves the system in a safe state where a safe sequence \(\langle P_1, P_2, \dots, P_n \rangle\) exists.

Ans: A system is in a Safe State if there exists a safe sequence \(\langle P_1, P_2, \dots, P_n \rangle\) such that the remaining need of each \(P_i\) can be satisfied by the currently available resources plus the resources held by all \(P_j\) with \(j < i\). A safe state is never a deadlocked state, though an unsafe state need not be deadlocked.

Ans: Paging is a non-contiguous memory-allocation scheme in which physical memory is divided into fixed-size blocks called frames and logical memory into blocks of the same size called pages; any page may be placed in any free frame. It completely eliminates external fragmentation.

Ans: A Page is a fixed-size block of a process's logical (virtual) address space, while a Frame is a block of physical memory of exactly the same size (a power of 2, e.g. 4 KB). Paging loads one page into one frame, and the page table records the mapping.

Ans: A Page Table is a per-process kernel data structure that maps each page number to its frame number in physical memory; it is located through the Page Table Base Register (PTBR). Each entry also carries the valid–invalid bit, protection bits, and dirty (modify) and reference bits.

Ans: The Translation Lookaside Buffer (TLB) is a small, fast, fully-associative hardware cache that holds recently used page-number → frame-number translations, so that a hit avoids the extra memory access needed to read the page table. With hit ratio \(h\), TLB access \(c\) and memory access \(m\): \( EMAT = h(c+m) + (1-h)(c+2m) \).

Ans: Internal Fragmentation is the memory wasted inside an allocated fixed-size block because the process needs slightly less than the whole block. In paging it occurs only in the last page of a process and averages half a page per process.

Ans: External Fragmentation exists when the total free memory is large enough to satisfy a request but it is not contiguous, so the request cannot be granted. It afflicts variable-partition allocation and segmentation, and is removed by compaction or by paging.

Ans: Virtual Memory is a technique that allows the execution of processes that are not completely in main memory, by separating the logical address space seen by the user from physical memory. It allows programs larger than physical memory to run and increases the degree of multiprogramming; it is usually implemented by demand paging.

Ans: A Page Fault is the trap raised by the hardware when a process references a page whose valid–invalid bit is set to invalid, i.e. the page is not present in main memory. The OS then locates the page on the backing store, swaps it into a free frame, updates the page table and restarts the interrupted instruction.

Ans: Demand Paging is a virtual-memory implementation in which a page is brought into main memory only when it is referenced (by a page fault) and never in advance; the module that does this is called a lazy swapper or pager. It reduces I/O traffic, memory usage and process start-up time.

Ans: Belady's Anomaly is the counter-intuitive phenomenon in which, for certain reference strings, increasing the number of allocated frames increases the number of page faults. It occurs in FIFO replacement but never in stack algorithms such as LRU and Optimal.

Ans: Thrashing is the condition in which a process spends more time servicing page faults (paging in and out) than executing, because it does not have enough frames to hold its working set. CPU utilisation falls sharply while paging-device utilisation approaches 100%.

Ans: The Working Set Model defines \(WS(t,\Delta)\) as the set of pages referenced in the most recent \(\Delta\) page references (the working-set window), which approximates the process's locality. If \(D = \sum WSS_i\) is the total demand and \(m\) the number of available frames, then \(D > m\) causes thrashing.

Ans: Shortest Seek Time First (SSTF) selects the pending request whose cylinder is closest to the current head position, thus minimising the seek time for the next request. It gives far better average seek time than FCFS but is not optimal and can starve requests located far from the head.

Ans: SCAN (Elevator) scheduling moves the disk head in one direction servicing every request on the way until it reaches the end of the disk, then reverses direction and services the requests on the return sweep. It avoids the starvation of SSTF but favours cylinders in the middle of the disk.

Ans: C-SCAN (Circular SCAN) services requests in one direction only; on reaching the last cylinder the head jumps immediately back to the first cylinder without servicing any request on the return trip. Treating the disk as circular gives a more uniform waiting time than SCAN.

Ans: An Inode (index node) is the on-disk UNIX data structure that stores all the metadata of one file — file type, permissions, owner/group ID, size, timestamps and link count — together with the direct and single/double/triple indirect pointers to its data blocks. The file name is not stored in the inode; it is kept in the directory entry, which maps name → inode number.

Ans: A Zombie (defunct) Process is a process that has terminated but whose entry still remains in the process table because its parent has not yet executed wait() to read its exit status. It holds no memory or other resources, only the PCB entry.

Ans: An Orphan Process is a process whose parent has terminated while the child is still running. It is immediately re-parented (adopted) by init/systemd (PID 1), which subsequently calls wait() to reap it.

5-State Process Transition Diagram

A process in an operating system transitions through different states during its lifecycle, managed by the OS Process Manager.

• New: The process is being created and its Process Control Block (PCB) is initialized.
• Ready: The process is loaded in main memory and is waiting to be assigned to a processor by the short-term scheduler.
• Running: Instructions are being executed by the CPU. A single CPU can only have one running process at a time.
• Waiting (Blocked): The process cannot execute further until some event occurs (e.g., I/O completion, waiting for a signal).
• Terminated: The process has finished execution and the OS reclaims its allocated resources.

CPU Scheduling Criteria

Different CPU scheduling algorithms have different properties. To evaluate them, we use standard performance metrics:

• CPU Utilization: The percentage of time that the CPU is busy executing processes rather than being idle. We want this as close to 100% as possible.
• Throughput: The number of processes that complete their execution per time unit. A measure of overall system productivity.
• Turnaround Time (TAT): The total time taken from the submission of a process until its completion.
  Formula: \(TAT = \text{Completion Time (CT)} - \text{Arrival Time (AT)}\)
• Waiting Time (WT): The total time a process spends waiting in the Ready queue.
  Formula: \(WT = TAT - \text{Burst Time (BT)}\)
• Response Time (RT): The time taken from the submission of a request until the first response is produced (i.e., when the process gets the CPU for the very first time).

FCFS Scheduling Numerical

First-Come, First-Served (FCFS) is a non-preemptive algorithm where the process that requests the CPU first is allocated the CPU first.

Given: All processes arrive at \(T=0\). Burst Times: \(P1=6, P2=8, P3=7, P4=3\).

Gantt Chart

Calculations Table

• Average Turnaround Time: \((6 + 14 + 21 + 24) / 4 = 16.25 \text{ ms}\)
• Average Waiting Time: \((0 + 6 + 14 + 21) / 4 = 10.25 \text{ ms}\)

SJF vs SRTF Scheduling

Shortest Job First (SJF) scheduling allocates the CPU to the process with the smallest next CPU burst. It yields the minimum average waiting time for a given set of processes. SJF can be implemented in two modes:

1. Non-Preemptive SJF

• Once the CPU is assigned to a process, it cannot be preempted until that process completes its burst.
• If a new process arrives with a shorter burst time than the currently running process, the CPU will not switch until the current process finishes.

2. Preemptive SJF (Shortest Remaining Time First - SRTF)

• If a new process arrives in the Ready queue with a CPU burst length shorter than the remaining time of the currently executing process, the CPU is preempted.
• The current process is paused and placed back in the Ready queue, and the newly arrived shorter process begins execution immediately.
• Advantage: SRTF generally results in a lower average waiting time compared to non-preemptive SJF.
• Disadvantage: Higher context-switching overhead and risk of starvation for long processes.

Round Robin Scheduling & Time Quantum

Round Robin (RR) is a preemptive CPU scheduling algorithm designed specifically for time-sharing systems. The Ready queue is treated as a circular queue.

• Mechanism: The CPU scheduler goes around the Ready queue allocating the CPU to each process for a time interval of up to 1 Time Quantum (TQ) (or time slice).
• If a process's burst time is less than 1 TQ, it releases the CPU voluntarily.
• If the burst time is longer than 1 TQ, the OS timer interrupts the process after the quantum expires, context switches it to the back of the Ready queue, and dispatches the next process.

Impact of Time Quantum Size

• If TQ is too small: The algorithm causes too many context switches. The overhead of saving/loading registers degrades system performance significantly.
• If TQ is too large: The overhead decreases, but RR degenerates into First-Come-First-Served (FCFS) scheduling, resulting in poor response times for short interactive processes.
• Rule of Thumb: 80% of CPU bursts should be shorter than the time quantum.

The Critical Section Problem

A Critical Section is a segment of code where a process accesses and modifies shared resources (like common variables, files, or tables). To prevent data inconsistency and race conditions, a system must ensure that when one process is executing in its critical section, no other process is allowed to execute in its critical section.

Any solution to the Critical Section problem must satisfy three strict requirements:

1. Mutual Exclusion: The core requirement. If process \(P_i\) is executing in its critical section, then no other processes can be executing in their critical sections.
2. Progress: If no process is executing in its critical section and some processes wish to enter theirs, then only those processes that are not executing in their remainder sections can participate in deciding which will enter its critical section next. This selection cannot be postponed indefinitely (no deadlock).
3. Bounded Waiting: There exists a bound, or limit, on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted (no starvation).

Peterson's Solution

Peterson's Solution is a classic software-based algorithmic solution to the critical section problem specifically designed for two processes (\(P_0\) and \(P_1\)) that alternate execution.

Data Structures

• int turn; // Indicates whose turn it is to enter the CS.
• boolean flag[2]; // flag[i] = true indicates that \(P_i\) is ready to enter its CS.

Code for Process i (where j is the other process)

Proof of correctness: Mutual exclusion is preserved because both processes can be stuck in the while loop only if turn == 0 and turn == 1 simultaneously, which is impossible. Progress is met because a process only gets stuck if the other process intends to enter and has the turn.

Semaphores in OS

A Semaphore (S) is an integer variable used for process synchronization and controlling access to common resources in a concurrent system. Unlike pure software locks like Peterson's, Semaphores are managed by the OS and avoid busy waiting.

Semaphores can only be accessed via two indivisible (atomic) standard operations:

1. wait(S) or P(S) or down(S)

Used to acquire a resource. It decrements the semaphore value. If the value becomes negative, the process is blocked and placed in the semaphore's waiting queue.

2. signal(S) or V(S) or up(S)

Used to release a resource. It increments the semaphore value. If there are processes waiting in the queue (value \(\le 0\)), one of them is awakened.

Producer-Consumer Problem

The Producer-Consumer (Bounded Buffer) problem involves a Producer process that generates data and puts it into a fixed-size buffer, and a Consumer process that takes data out of the buffer. They must be synchronized so the producer doesn't insert into a full buffer, and the consumer doesn't remove from an empty buffer.

Semaphore Initialization

• mutex = 1; (Binary semaphore for mutual exclusion on the buffer)
• empty = N; (Counting semaphore counting empty slots, initially N)
• full = 0; (Counting semaphore counting filled slots, initially 0)

Producer Code

Consumer Code

Readers-Writers Problem

The Readers-Writers problem deals with situations where a database is shared among several concurrent processes. Some processes only want to read (Readers), while others want to update (Writers). We must ensure that:

1. Multiple readers can read simultaneously.
2. If a writer is writing, no other reader or writer can access the database (Exclusive access).

Semaphore Initialization

• mutex = 1; (Ensures mutual exclusion when updating the read_count variable)
• rw_mutex = 1; (Ensures mutual exclusion for the actual database writers)
• int read_count = 0; (Tracks how many readers are currently reading)

Writer Code

Reader Code

Dining Philosophers Problem

The Dining Philosophers Problem is a classic synchronization problem. Five philosophers sit around a circular table. Each has a plate of spaghetti. Between each pair of plates is one chopstick (total 5). To eat, a philosopher needs both the left and right chopsticks.

The Problem (Deadlock)

If all 5 philosophers simultaneously pick up their left chopstick, all 5 chopsticks are taken. When they reach for their right chopstick, it is held by their neighbor. Everyone waits indefinitely, causing a Deadlock.

Deadlock Avoidance Solutions

1. Resource Hierarchy (Asymmetric Solution): Number the chopsticks 1 to 5. Philosophers must always pick up the lower-numbered chopstick first. This breaks the circular wait condition.
2. Capacity Limitation: Allow at most 4 philosophers to sit at the table with 5 chopsticks. This guarantees at least one philosopher can get two chopsticks.
3. Both-or-Nothing (Monitor): A philosopher only picks up chopsticks if both are available simultaneously in a critical section.

4 Necessary Conditions for Deadlock

A deadlock situation can arise if and only if the following four conditions hold simultaneously in a system (known as Coffman conditions):

1. Mutual Exclusion: At least one resource must be held in a non-sharable mode. If another process requests that resource, the requesting process must be delayed until the resource has been released.
2. Hold and Wait: A process must be holding at least one resource and waiting to acquire additional resources that are currently being held by other processes.
3. No Preemption: Resources cannot be preempted; that is, a resource can be released only voluntarily by the process holding it, after that process has completed its task.
4. Circular Wait: There must exist a set \(\{P_0, P_1, \dots, P_n\}\) of waiting processes such that \(P_0\) is waiting for a resource held by \(P_1\), \(P_1\) is waiting for a resource held by \(P_2\), \(\dots\), and \(P_n\) is waiting for a resource held by \(P_0\).

Resource Allocation Graph (RAG)

A Resource Allocation Graph (RAG) is a directed graph used to visually model the state of an OS, showing which processes hold which resources and which processes are requesting resources. It helps in deadlock detection.

• Vertices (V): Two types: Processes (\(P = \{P_1, P_2, \dots\}\) represented as circles) and Resources (\(R = \{R_1, R_2, \dots\}\) represented as rectangles with dots indicating instances).
• Edges (E):
  • Request Edge (\(P_i \rightarrow R_j\)): Process \(P_i\) requests an instance of \(R_j\).
  • Assignment Edge (\(R_j \rightarrow P_i\)): An instance of \(R_j\) is allocated to \(P_i\).

Cycle Detection and Deadlock

• If the RAG contains no cycles, then no process is deadlocked.
• If the RAG contains a cycle:
  1. If each resource type has exactly one instance, a cycle implies a Deadlock has definitely occurred.
  2. If each resource type has multiple instances, a cycle does not necessarily imply a deadlock (it is a necessary but not sufficient condition).

Deadlock Prevention vs Deadlock Avoidance

Banker's Safety Algorithm

The Safety Algorithm (part of Banker's Algorithm) determines if a system is in a "safe state" where all processes can finish without deadlocking. It uses three matrices: Allocation, Max, and Need (where \(Need = Max - Allocation\)), and a vector Available.

Algorithm Steps:

1. Initialization:
   Let Work and Finish be vectors of length \(m\) (resources) and \(n\) (processes).
   Initialize: Work = Available
   Initialize: Finish[i] = false for \(i = 0, 1, \dots, n-1\).
2. Find a candidate process:
   Find an index \(i\) such that both:
   a) Finish[i] == false (Process has not finished)
   b) Need[i] ≤ Work (System can satisfy its needs)
   If no such \(i\) exists, go to Step 4.
3. Simulate execution:
   The system temporarily grants resources to \(P_i\). When \(P_i\) finishes, it returns all its held resources to the system.
   Work = Work + Allocation[i]
Finish[i] = true
   Go back to Step 2.
4. Check Status:
   If Finish[i] == true for all \(i\), then the system is in a Safe State. The order in which processes finished is the Safe Sequence.
   If any Finish[i] == false, the system is in an Unsafe State (deadlock possible).

Paging Architecture

Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory. It avoids external fragmentation by breaking memory into fixed-sized blocks.

• Logical Address Space is divided into blocks of the same size called Pages.
• Physical Memory is divided into fixed-sized blocks called Frames (where Page Size == Frame Size).

Address Translation

The CPU generates a Logical Address divided into two parts: Page Number (\(p\)) and Page Offset (\(d\)). The OS uses a Page Table to map \(p\) to a Physical Frame Number (\(f\)). The physical address is \(f\) concatenated with \(d\).

Segmentation Architecture

Segmentation is a memory management scheme that supports the user's view of memory. A logical address space is a collection of variable-sized segments (e.g., main program, functions, stack, symbol table). Unlike paging where all pages are the same size, segments have variable lengths based on logical program units.

Address Translation

The logical address consists of two parts: Segment Number (\(s\)) and Offset (\(d\)). Address translation is done using a Segment Table. Each entry in the segment table has:

• Base: Contains the starting physical address where the segment resides in memory.
• Limit: Specifies the length of the segment.

Internal vs External Fragmentation

Translation Lookaside Buffer (TLB)

Because the Page Table is stored in main memory, every data access requires two memory accesses: one for the page table, one for the actual data. This slows down the system by a factor of 2. To solve this, OS uses a Translation Lookaside Buffer (TLB).

The TLB is a small, fast hardware associative cache built directly into the MMU. It stores the most recently used Page-to-Frame translations.

• TLB Hit: Page number is found in TLB. Physical address is generated immediately.
• TLB Miss: Page number not in TLB. Must look up in main memory Page Table, then load it into TLB for future use.

Effective Access Time (EAT)

EAT calculates the average time to access memory given the hit ratio (\(\alpha\)), TLB lookup time (\(\epsilon\)), and memory access time (\(m\)).

Where \((\epsilon + 2m)\) is the penalty for a TLB miss (one memory access for page table, one for data).

Demand Paging and Page Fault Handling

Demand Paging is a virtual memory technique where pages are loaded from the disk into main memory only when they are explicitly demanded (i.e., referenced) during program execution, rather than loading the entire program at once.

Page Fault Handling Process

If a process tries to access a page that was not brought into memory (invalid bit in page table), it causes a Page Fault trap to the OS.

1. The OS intercepts the trap and checks an internal table to see if the memory reference was valid (but page is on disk) or invalid (segmentation fault).
2. If valid, the OS finds a free frame in physical memory. (If no free frame exists, a Page Replacement Algorithm like LRU runs).
3. The OS schedules a disk I/O operation to read the required page into the newly allocated free frame.
4. Once the disk read completes, the OS updates the Page Table, marking the page as valid and mapping it to the new frame.
5. The OS restarts the instruction that was interrupted by the trap, allowing the process to access the page seamlessly.

FIFO Page Replacement & Belady's Anomaly

First-In, First-Out (FIFO) is the simplest page replacement algorithm. It maintains a queue of all pages in memory. When a page fault occurs and a page must be replaced, the oldest page (the one at the front of the queue) is chosen for replacement.

• Pros: Very easy to understand and implement using a standard FIFO queue.
• Cons: Its performance is generally poor because it replaces the oldest page, which might still be heavily used by the program.

Belady's Anomaly

Generally, one expects that increasing the number of physical frames in memory will result in fewer page faults. However, Belady's Anomaly is a phenomenon where increasing the number of page frames increases the number of page faults for certain page reference strings when using the FIFO algorithm.

This happens because FIFO does not possess the stack property (unlike LRU or Optimal), meaning the set of pages in memory with \(N\) frames is not necessarily a subset of the pages in memory with \(N+1\) frames.

LRU Page Replacement Algorithm

Least Recently Used (LRU) page replacement replaces the page that has not been used for the longest period of time. It relies on the heuristic that pages heavily used in the recent past will likely be used again in the near future.

LRU is considered an excellent algorithm because it does not suffer from Belady's Anomaly, but it requires significant hardware support to implement efficiently. Two common implementations are:

1. Counters (Time-of-Use)

• Every page table entry has a "time-of-use" register.
• The CPU is equipped with a logical clock or counter that increments on every memory reference.
• Whenever a page is referenced, the clock value is copied into the page's register.
• On a page fault, the OS searches the page table for the page with the smallest time value and replaces it. (Requires searching the whole table).

2. Stack Implementation

• Maintain a stack (typically a doubly linked list) of page numbers.
• Whenever a page is referenced, it is removed from its current position and pushed to the top of the stack.
• On a page fault, the page at the bottom of the stack is chosen for replacement. (Requires updating pointers on every memory access).

Optimal Page Replacement (OPT)

The Optimal Page Replacement Algorithm has the lowest possible page fault rate of all algorithms and does not suffer from Belady's Anomaly.

The Strategy: Replace the page that will not be used for the longest period of time in the future.

• If the OS knows the exact sequence of upcoming page references, it can look ahead in the string.
• It selects the page currently in memory whose next reference is furthest away in the future sequence.

Why is it used?

In practice, OPT is impossible to implement because the OS cannot predict the future memory references of a program. It is solely used as a benchmark to evaluate the performance of other algorithms (like LRU and FIFO). If LRU performs within a few percent of OPT, it is considered highly efficient.

Thrashing & Working Set Model

Thrashing

Thrashing occurs when a system spends more time paging (swapping pages in and out of the disk) than executing actual instructions. It happens when a process does not have "enough" physical frames to hold its actively used pages. The CPU utilization plummets because processes are constantly blocked waiting for page faults.

The Working Set Model

The OS uses the Working Set Model to prevent thrashing. It is based on the concept of locality of reference.

• Working Set Window (\(\Delta\)): A fixed number of most recent page references.
• Working Set (\(WS\)): The set of distinct pages actually referenced in the most recent \(\Delta\) accesses. This represents the pages the process is currently actively using.
• Working Set Size (\(WSS_i\)): The total number of pages in the working set for process \(i\).

Prevention: The OS calculates the total demand \(D = \sum WSS_i\). If the total demand \(D\) exceeds the total available physical memory frames (\(m\)), thrashing will occur. In this case, the OS suspends one or more processes to free up frames and stabilize the system.

File Allocation Methods

Directory Structures

• Single-Level Directory: The simplest structure. All files from all users are contained in the same single directory.
  • Pros: Easy to support and understand.
  • Cons: Naming collisions (no two files can have the same name system-wide) and poor grouping for multiple users.
• Two-Level Directory: Each user has their own separate User File Directory (UFD). A Master File Directory (MFD) points to all UFDs.
  • Pros: Solves name collision between different users. Supports user isolation.
  • Cons: Users cannot easily share files or group files into logical sub-categories.
• Tree-Structured Directory: Generalizes the two-level directory into an arbitrary tree. Users can create subdirectories within subdirectories.
  • Pros: Excellent for logical grouping and organization. Absolute and relative path naming. Currently used by Windows, Linux, macOS.
  • Cons: Does not allow sharing of files (a file cannot exist in two different directories simultaneously unless linked).

Disk Scheduling Algorithms

Disk scheduling optimizes the movement of the read/write head (seek time) to serve pending I/O requests.

• FCFS (First-Come, First-Served): Processes requests strictly in the order they arrive.
  Pros: Fair. Cons: Extremely inefficient, causes wild head swings across the disk.
• SSTF (Shortest Seek Time First): Selects the request closest to the current head position.
  Pros: Minimizes seek time significantly. Cons: Can cause starvation for requests far from the current head position.
• SCAN (Elevator Algorithm): The head starts from one end, moves towards the other end servicing requests, and when it hits the end, it reverses direction.
  Pros: Solves starvation. Cons: Unequal wait times (requests near the edge wait longer when the head reverses).
• C-SCAN (Circular SCAN): Like SCAN, but when the head reaches one end, it immediately returns to the beginning without servicing requests on the return trip.
  Pros: Provides a much more uniform waiting time for all cylinders.

UNIX Inode Structure

In UNIX file systems, every file is represented by an Inode (Index Node). An inode contains metadata about the file (permissions, owner, size, timestamps) and, most importantly, pointers to the data blocks on the disk.

To support files of vastly different sizes while keeping the inode small, UNIX uses a multi-level index pointer structure:

1. Direct Pointers (Usually 12 or 15): Point directly to disk blocks containing the file's data. Sufficient for small files.
2. Single Indirect Pointer: Points to a disk block that contains an array of direct pointers. Used when the file grows beyond the direct pointers.
3. Double Indirect Pointer: Points to a block containing pointers to single-indirect blocks. Allows for very large files.
4. Triple Indirect Pointer: Points to a block containing pointers to double-indirect blocks. Allows for enormous files (terabytes in size).

User-Level vs Kernel-Level Threads

UNIX Process Control System Calls

• fork(): Creates a new process (the child). The child is an exact clone of the parent's memory space.
  • Returns 0 to the child process.
  • Returns the child's PID to the parent process.
• exec(): Replaces the entire memory space (code, data, heap, stack) of the calling process with a brand new program loaded from disk. It never returns unless there's an error. Typically called by the child after a fork().
• wait(): Called by the parent process to pause its execution until one of its child processes terminates. It also retrieves the exit status of the child and prevents the child from becoming a zombie.
• exit(): Terminates the calling process gracefully. It flushes I/O buffers, closes files, and deallocates memory, passing an exit status back to the parent (via wait()).

Free Space Management

The OS must keep track of available (free) blocks on the disk to allocate space to new files.

1. Bit Vector (Bit Map)

The free space list is implemented as a bitmap. Each block on the disk is represented by 1 bit. If the block is free, the bit is 1. If the block is allocated, the bit is 0.

• Advantage: Very simple and extremely fast for finding contiguous free blocks (the OS searches for sequences of 1s using bitwise CPU instructions).
• Disadvantage: Requires extra memory to store the bitmap. For a 1TB disk with 4KB blocks, the bitmap requires 32MB of main memory to be kept resident for good performance.

2. Linked List

The OS links all free disk blocks together, keeping a pointer to the first free block in a special location on disk. The first block contains a pointer to the next free block, and so on.

• Advantage: No waste of space. The pointers are stored directly inside the free blocks themselves.
• Disadvantage: Extremely inefficient to traverse. Finding a large number of free blocks requires reading multiple disk sectors sequentially, which is very slow.

Memory Allocation Strategies

When a process requests memory in a contiguous allocation system, the OS must choose a free "hole" from the list of available memory blocks.

• First-Fit: Allocates the first hole that is big enough.
  • Pros: Fastest algorithm, minimal search time.
  • Cons: Can leave many small fragments near the beginning of memory.
• Best-Fit: Allocates the smallest hole that is big enough. Requires searching the entire list (unless sorted by size).
  • Pros: Minimizes the size of the leftover fragment.
  • Cons: Slowest. Tends to create tiny, useless holes (external fragmentation) that cannot satisfy any future requests.
• Worst-Fit: Allocates the largest hole available. Requires searching the entire list.
  • Pros: Leaves a large leftover hole, which might be useful for a subsequent large process.
  • Cons: Generally performs worse than First-Fit and Best-Fit in terms of storage utilization.

Inverted Page Table

In traditional paging, each process has its own page table, which maps logical pages to physical frames. For systems with large 64-bit address spaces, traditional page tables become gigabytes in size per process, which is unmanageable.

An Inverted Page Table solves this by having exactly one page table for the entire system, containing one entry for every physical frame of memory.

Architecture

• Each entry in the table represents a physical frame and contains the pair: [Process ID (PID), Page Number (p)].
• When a process references logical page \(p\), the CPU searches the inverted table for a match on [Current PID, p].
• If found at index \(i\), the physical frame number is \(i\).

Pros: Dramatically reduces the memory needed to store the page table (size is proportional to physical memory, not logical space).

Cons: Lookup is slower because the table is sorted by physical frame, not logical page. Finding a match requires searching the entire table, so a hash table is typically used to speed up the search.

Inter-Process Communication (IPC)

IPC mechanisms allow cooperating processes to exchange data and synchronize their actions.

Hardware Synchronization Instructions

To implement software synchronization tools like Mutexes efficiently, OS designers rely on special hardware instructions provided by modern CPUs. These instructions execute atomically (as one uninterrupted unit).

1. TestAndSet (TAS)

The TestAndSet instruction reads a boolean variable and sets it to true in a single, indivisible hardware cycle.

2. Swap (Compare-And-Swap)

The Swap instruction atomically swaps the contents of two memory variables.

Access Control Matrix & ACLs

Security in an OS is managed by tracking which Subjects (Users/Processes) have which access rights (Read, Write, Execute) to which Objects (Files, Devices, Memory).

Access Control Matrix

This is a conceptual table where rows represent domains (subjects) and columns represent objects. Each cell contains the access rights.

• If the matrix is large, it becomes very sparse (most cells are empty), wasting a huge amount of space if stored directly as a 2D array.

Access Control List (ACL)

Instead of storing the empty matrix, the OS implements it column-by-column. An Access Control List is attached to each Object.

• For a specific file, the ACL lists all the users and their specific permissions.
• Example ACL for file1.txt: (UserA: RW), (UserB: R), (GroupX: RX)
• Advantage: Easy to see who has access to a specific file. Easy to revoke access to an object. (This is how Windows NTFS and Linux permissions work).

RAID (Redundant Array of Independent Disks)

RAID is a technology that combines multiple physical disk drives into a single logical unit to improve performance, data redundancy, or both.

• RAID 0 (Striping): Data is split into blocks and distributed across all disks in the array simultaneously.
  • Performance: Excellent (read/write speeds are multiplied by the number of disks).
  • Reliability: Zero. If one disk fails, all data is completely lost.
• RAID 1 (Mirroring): Data is written identically to two (or more) disks.
  • Performance: Good read speeds, normal write speeds.
  • Reliability: High. If one disk fails, the other acts as an exact backup. Costly (50% storage efficiency).
• RAID 5 (Striping with Parity): Data is striped across disks, and "Parity" blocks are distributed across all disks.
  • Performance: Good read speeds, slight penalty on writes (parity calculation).
  • Reliability: Can survive exactly 1 disk failure. If a disk dies, missing data is mathematically reconstructed using the parity blocks on the surviving disks.

Monolithic Kernel vs Microkernel

Type 1 vs Type 2 Hypervisors (Virtualization)

A Hypervisor (or Virtual Machine Monitor - VMM) is software that creates and runs virtual machines (VMs), allowing multiple operating systems to share a single hardware host.

Type 1 Hypervisor (Bare-Metal)

• Placement: Installs directly on the physical hardware of the host machine, bypassing the need for a host operating system. The hypervisor is the OS.
• Performance: Extremely high performance and low latency, as VMs have direct access to hardware resources.
• Use Case: Enterprise data centers and cloud computing servers.
• Examples: VMware ESXi, Microsoft Hyper-V, Xen.

Type 2 Hypervisor (Hosted)

• Placement: Installs as a standard software application on top of an existing host operating system (like Windows or macOS).
• Performance: Slower. Hardware requests from the guest OS must pass through the hypervisor, then through the host OS, before reaching the CPU.
• Use Case: Desktop virtualization, software testing, running Linux on a Windows laptop.
• Examples: Oracle VirtualBox, VMware Workstation, Parallels Desktop.

Real-Time CPU Scheduling

Real-Time Systems (like autopilot avionics or medical pacemakers) have strict deadlines. The scheduler must guarantee that critical tasks complete before their deadline expires.

1. Rate-Monotonic Scheduling (RMS)

• Type: Static priority, preemptive algorithm.
• Rule: Priorities are assigned based on the period of the task. The shorter the period (the more frequently the task occurs), the higher its priority.
• Properties: Very stable and predictable. If the system is overloaded, it is guaranteed that the lowest priority tasks will miss their deadlines first. However, it cannot guarantee utilization up to 100% (the upper bound for schedulability is approx 69% for many tasks).

2. Earliest Deadline First (EDF)

• Type: Dynamic priority, preemptive algorithm.
• Rule: Priorities are assigned dynamically according to deadlines. The task with the earliest (closest) deadline gets the highest priority.
• Properties: More efficient than RMS. It can theoretically achieve 100% CPU utilization while meeting all deadlines. However, if the system becomes overloaded, it behaves unpredictably, and multiple tasks might miss their deadlines simultaneously (a domino effect).

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.