Operating System

Monolithic Kernel vs. Microkernel:

• Monolithic Kernel: All core OS services (VFS, IPC, device drivers, network stack, memory management) run in privileged kernel space within a single shared address space (e.g. Linux, Traditional Unix). High performance, but a driver crash can crash the entire OS.
• Microkernel: Only bare minimum primitives (low-level memory allocation, thread scheduling, basic IPC) run in kernel space; drivers and file systems execute as user-space daemons communicating via message passing (e.g. QNX, Minix, Mach). High stability and modularity with modest IPC context-switch overhead.

Process Control Block (PCB):

A PCB (or task struct) is a kernel data structure representing an execution instance of a process.

1. Process ID (PID) and State: Current state (New, Ready, Running, Waiting, Terminated).
2. Program Counter (PC): Memory address of the next machine instruction to execute.
3. CPU Registers: Accumulators, index registers, stack pointers saved during context switches.
4. Memory Management Information: Page tables, base/limit registers, segment tables.

Context Switch & Overhead:

A context switch is the mechanism of saving the execution state (registers, PC) of the currently running process into its PCB and restoring the state of another scheduled process.

• Overhead Sources: Pure non-productive CPU cycles spent copying registers, flushing the Translation Lookaside Buffer (TLB), invalidating CPU L1/L2 data caches, and updating kernel dispatch tables.

Preemptive vs. Non-Preemptive Scheduling:

• Preemptive: The OS scheduler can forcibly interrupt and suspend a currently running process before its burst completes upon timer interrupt or arrival of a higher-priority task (e.g. Round Robin, SRTF, Linux CFS).
• Non-Preemptive: Once allocated CPU time, a process retains control until it voluntarily yields by issuing an I/O wait request or terminating (e.g. FCFS, Non-preemptive SJF).

Zombie vs. Orphan Processes:

• Zombie Process: A process that has completed execution but remains in the process table because its parent has not yet read its exit status code via wait() / waitpid().
• Orphan Process: A running process whose parent process terminated before it; it is immediately adopted by the root init/systemd process (PID 1), which reaps it upon termination.

CPU Scheduling Analysis:

(a) FCFS Scheduling:

Execution order follows arrival: P1 (0 to 8), P2 (8 to 12), P3 (12 to 21), P4 (21 to 26).

• Average Turnaround Time: $\frac{8 + 11 + 19 + 23}{4} = \frac{61}{4} = \mathbf{15.25\text{ ms}}$
• Average Waiting Time: $\frac{0 + 7 + 10 + 18}{4} = \frac{35}{4} = \mathbf{8.75\text{ ms}}$

---

(b) SRTF (Preemptive SJF):

• At $t = 0$: P1 starts (remaining: 8).
• At $t = 1$: P2 arrives with $BT=4$; P1 has 7 remaining. Since $4 < 7$, preempt P1, run P2.
• At $t = 2$: P3 arrives ($BT=9$). P2 has 3 remaining. Continue P2.
• At $t = 3$: P4 arrives ($BT=5$). P2 has 2 remaining. Continue P2.
• At $t = 5$: P2 finishes ($CT=5$). Remaining: P1(7), P4(5), P3(9). Smallest is P4 $\implies$ run P4.
• At $t = 10$: P4 finishes ($CT=10$). Remaining: P1(7), P3(9). Run P1.
• At $t = 17$: P1 finishes ($CT=17$). Run P3.
• At $t = 26$: P3 finishes ($CT=26$).

• Average Turnaround Time (SRTF): $\frac{17 + 4 + 24 + 7}{4} = \frac{52}{4} = \mathbf{13.00\text{ ms}}$
• Average Waiting Time (SRTF): $\frac{9 + 0 + 15 + 2}{4} = \frac{26}{4} = \mathbf{6.50\text{ ms}}$

User-Level Threads (ULT) vs. Kernel-Level Threads (KLT):

• ULT: Managed entirely by a user-space thread library without kernel awareness. Switching is fast ($O(1)$) with zero kernel traps, but if one thread blocks on system I/O, the entire process stalls.
• KLT: Supported and scheduled directly by the OS kernel. If a thread blocks, the kernel can schedule another thread of the same process. Context switching is heavier.

Three Multithreading Mapping Models:

1. Many-to-One Model: Many ULTs mapped to a single KLT. Inability to leverage multi-core processors; one blocking call stalls all threads.
2. One-to-One Model (Linux/Windows): Each ULT maps to a dedicated KLT. True multi-core concurrency; overhead scales with thread count.
3. Many-to-Many Model: Multiplexes $M$ user threads over $N$ kernel threads ($M \ge N$). Combines lightweight user management with kernel concurrency.

Shared Memory vs. Message Passing:

System Call Execution Flow (read()):

A system call provides the programmatic interface between user applications and privileged OS kernel services.

Step-by-Step Transition Flow:

1. Invocation: User program calls standard C library wrapper read(fd, buffer, count).
2. Setup: Library pushes system call number (e.g. __NR_read) into a CPU register (e.g., rax) and loads parameters into registers.
3. Trap to Kernel: Executes software trap instruction (syscall / int 0x80), switching CPU privilege from User Mode (Ring 3) to Kernel Mode (Ring 0).
4. Dispatcher: Kernel looks up the system call number in the System Call Table and invokes sys_read().
5. I/O Execution: Kernel verifies buffer permissions, calls VFS, triggers disk DMA transfer, and places the calling thread in I/O wait state.
6. Return: When data arrives in memory, CPU registers are restored, mode switches back to User Mode, and control returns with byte count.

Round Robin (RR) Scheduling & Time Quantum ($q$):

Round Robin is a preemptive scheduling algorithm designed for time-sharing systems where the ready queue is treated as a circular FIFO queue. Each process gets a discrete slice of CPU time called a Time Quantum ($q$).

Impact of Quantum Size ($q$):

• If $q \to \infty$ (Excessively Large): RR degenerates into First-Come, First-Served (FCFS) scheduling. Interactive response times suffer severely.
• If $q \to 0$ (Extremely Small): Mimics theoretical Processor Sharing, where each of $N$ processes appears to run at $1/N$-th speed. However, excessive context switches overwhelm the CPU with kernel overhead, degrading actual throughput.
• Rule of Thumb: $q$ should be chosen such that approximately $80\%$ of CPU bursts complete within a single quantum (typically 10 - 100 ms).

Multilevel Feedback Queue (MLFQ):

MLFQ separates the ready queue into multiple distinct priority levels with varying time quanta (e.g., Queue 0: $q = 8\text{ ms}$, Queue 1: $q = 16\text{ ms}$, Queue 2: FCFS).

Operational Rules:

1. New processes enter the highest priority queue (Queue 0).
2. Demotion: If a process exhausts its full time quantum without releasing CPU, it is demoted to the next lower priority queue (penalizing CPU-bound batch jobs).
3. Promotion: If a process yields CPU before quantum expiration (interactive I/O-bound jobs), it remains in or is promoted to higher queues.
4. Starvation Prevention (Priority Boost): Periodically, the scheduler moves all waiting processes to the highest priority queue, ensuring compute-intensive jobs do not starve.

The Critical Section Problem & Peterson’s Solution:

A critical section is a segment of code where multiple concurrently executing threads access and manipulate shared variables, shared memory, or shared files, creating potential race conditions.

---

Three Cardinal Criteria for a Valid Solution:

1. Mutual Exclusion: If process $P_i$ is executing in its critical section, no other process can be executing in its critical section simultaneously.
2. Progress: If no process is in its critical section and some processes wish to enter, only those processes not in their remainder section can participate in deciding who enters next, and selection cannot be postponed indefinitely.
3. Bounded Waiting: There must be a bound on the number of times other processes are allowed to enter their critical sections after a process has made a request to enter, before that request is granted (preventing starvation).

---

Peterson’s Algorithm (Two Processes: $P_0$ and $P_1$):

Shared state variables:

int turn;              // Whose turn it is to enter
bool flag[2];          // flag[i] == true indicates Pi wants to enter

Process $P_i$ Implementation ($j = 1 - i$):

do {
    flag[i] = true;              // 1. Declare intent to enter
    turn = j;                    // 2. Give preference to other process
    while (flag[j] && turn == j); // 3. Busy-wait while rival wants in and it's rival's turn

    // --- CRITICAL SECTION ---
    critical_section();

    flag[i] = false;             // 4. Exit section: relinquish interest

    // --- REMAINDER SECTION ---
    remainder_section();
} while (true);

---

Proof of Compliance:

1. Mutual Exclusion: For both $P_0$ and $P_1$ to enter simultaneously, both while loop conditions must evaluate to false. That requires turn == 1 and turn == 0 simultaneously, which is logically impossible since turn holds a single scalar integer.
2. Progress: If $P_j$ is not interested, flag[j] == false, so $P_i$ enters immediately. If both request simultaneously, turn will be either 0 or 1, allowing exactly one process to pass while the other waits.
3. Bounded Waiting: When $P_i$ exits, it sets flag[i] = false. If it immediately loops back, it sets turn = j, giving $P_j$ priority. Thus, $P_j$ waits at most one entry cycle.

Synchronization Primitives & Classic Problems:

• Mutex: Binary locking mechanism providing exclusive access ($0$ or $1$). The locking thread must be the thread that unlocks it.
• Semaphore: An integer synchronization variable accessed only through atomic operations:
  • wait(S) / P(S): Decrements $S$; if $S < 0$, calling thread blocks.
  • signal(S) / V(S): Increments $S$; wakes up one blocked thread.

---

(a) Bounded-Buffer Producer-Consumer Solution:

Buffer size $N$. Shared state:

semaphore mutex = 1;     // Binary semaphore for mutual exclusion on buffer
semaphore empty = N;     // Counting semaphore: tracks vacant buffer slots
semaphore full = 0;      // Counting semaphore: tracks populated items

Producer Process:

do {
    item = produce_item();
    wait(empty);         // Decrement empty slots; wait if buffer full
    wait(mutex);         // Lock buffer access
    insert_item(item);
    signal(mutex);       // Release buffer lock
    signal(full);        // Notify consumer of new item
} while (true);

Consumer Process:

do {
    wait(full);          // Wait until at least one item is present
    wait(mutex);         // Lock buffer access
    item = remove_item();
    signal(mutex);       // Release lock
    signal(empty);       // Increment vacant slot count
    consume_item(item);
} while (true);

---

(b) Dining Philosophers Problem & Deadlock Prevention:

5 philosophers seated around a table with 5 chopsticks. Each philosopher needs both left chopstick $i$ and right chopstick $(i+1)\%5$ to eat.

• Deadlock Condition: If all 5 pick up their left chopstick simultaneously, all right chopsticks are unavailable; all starve waiting forever.

Deadlock-Free Asymmetric Solution:

Enforce asymmetric pickup ordering:

• Odd philosophers pick up Left then Right.
• Even philosophers pick up Right then Left.
• Or restrict table occupancy to a maximum of 4 philosophers simultaneously via a counting semaphore initialized to 4.