Operating Systems Interview Questions

The Banker's Algorithm is a deadlock avoidance method used in resource-allocation systems. It simulates resource allocation and determines if the system remains in a Safe State before granting a request.

• Data Structures:
  • Allocation: 2D matrix representing resources currently allocated to each process.
  • Max: 2D matrix representing the maximum resources a process may ever request.
  • Available: Vector indicating the count of free resources of each type.
  • Need: Calculated as $\text{Need} = \text{Max} - \text{Allocation}$.
• The Safety Algorithm:
  1. Find a process whose Need is less than or equal to Available.
  2. If found, assume it completes execution, releases its resources ($\text{Available} = \text{Available} + \text{Allocation}$), and mark it as finished.
  3. Repeat until all processes are finished (Safe State) or a deadlocked state is reached (Unsafe State, request denied).

• Paging:
  • Divides logical memory into fixed-size Pages and physical memory into Frames.
  • The division is completely invisible to the programmer.
  • Eliminates external fragmentation but suffers from internal fragmentation.
• Segmentation:
  • Divides logical memory into variable-size Segments based on logical program units (e.g., main function, stack, library, objects).
  • Visible to the programmer.
  • Suffers from external fragmentation (requires compaction) but has zero internal fragmentation.

The Bounded-Buffer problem involves a buffer of fixed size $N$ shared by producers (creating items) and consumers (removing items):

• The Synchronization Challenge: Prevent producers from adding items to a full buffer, prevent consumers from removing items from an empty buffer, and protect buffer indices from concurrent updates.
• Semaphore Solution: Uses three semaphores:
  • mutex (binary): Protects the critical section of buffer modification.
  • empty (counting, initial $N$): Tracks remaining empty slots.
  • full (counting, initial $0$): Tracks filled slots.

This problem models access to a shared resource (e.g., database) where multiple processes read and write:

• Rules: Multiple readers can access the resource simultaneously, but only one writer can access it exclusively (no other readers or writers allowed).
• First Readers-Writers Problem (No Reader Waits): Readers have priority. If a reader is active, subsequent readers enter immediately, which can cause starvation for writers.
• Second Readers-Writers Problem (No Writer Waits): Writers have priority. Once a writer is ready, no new readers are allowed to start reading, which can cause starvation for readers.

Five philosophers sit around a circular table with 5 chopsticks, alternating between thinking and eating. A philosopher needs both adjacent chopsticks to eat:

• Deadlock Scenario: If every philosopher sits down and simultaneously picks up their left chopstick, all right chopsticks are occupied. They will wait forever, causing a deadlock.
• Deadlock Solutions:
  • Asymmetry: Odd-numbered philosophers pick up their left chopstick first, while even-numbered philosophers pick up their right chopstick first.
  • Limit concurrency: Allow at most 4 philosophers to sit at the table simultaneously.
  • State check: A philosopher only picks up chopsticks if both are free (using a mutex to protect state evaluation).

Unlike traditional queue-based schedulers, CFS uses a time-ordered Red-Black Tree (a self-balancing binary search tree) to schedule processes with $O(\log N)$ efficiency:

• Virtual Runtime (vruntime): Represents the amount of execution time allocated to a process, scaled by its nice/priority value (higher priority = slower vruntime accumulation).
• Scheduling Execution: CFS always schedules the process with the absolute smallest vruntime (the leftmost node in the Red-Black tree).
• Preemption: As a process executes, its vruntime increases. Once its vruntime exceeds that of the leftmost node (or its designated epoch slice finishes), the process is preempted, its tree position is updated, and the new leftmost node is scheduled.

• The ABA Problem: In a concurrent lock-free environment using Compare-and-Swap (CAS), Thread 1 reads value A from memory location X. Thread 2 preempts Thread 1, modifies X to value B, and then reverts it back to A. When Thread 1 resumes, its CAS instruction checks X, sees the expected value A, and succeeds, unaware that the structural state of the underlying data structure was modified.
• Resolution:
  • Tagged State (Version Counters): Associate a numeric version tag with the variable. The CAS instruction updates both the value and the tag atomically (A1 -> B2 -> A3).
  • Memory Reclamation: Deploy techniques like Hazard Pointers or Epoch-Based Reclamation to guarantee that memory locations cannot be recycled while active references exist.

RCU is a lock-free synchronization mechanism optimized for read-heavy scenarios:

• Lock-Free Readers: Readers traverse shared data structures (via pointers) concurrently without acquiring any locks, disabling interrupts, or performing atomic operations.
• Writers (Publish-Subscribe): To modify an element, a writer allocates a new structure, copies the old element, updates the copy, and atomically updates the pointer to publish the new version.
• Grace Period: The old element cannot be deleted immediately because active readers might still be accessing it. The writer waits for a Grace Period—until all CPU cores have undergone a context switch (quiescent state)—guaranteeing no readers hold references to the old version, before safely reclaiming the memory.

• select (POSIX): Monitors file descriptors (FDs) using a bitmask. Limited to a hardcoded maximum of 1024 FDs. It is highly inefficient because it requires copying the FD set from user space to kernel space on every call, and scanning the entire list linearly ($O(N)$) to identify active events.
• poll: Similar to select but uses a dynamically sized array of structures, removing the 1024 limit. Still suffers from $O(N)$ linear scans and user-kernel memory copies.
• epoll (Linux specific):
  • Efficiency ($O(1)$): Monitors FDs using an in-kernel Red-Black tree. Active events are pushed directly into a Ready List (doubly linked list) using device driver callbacks.
  • Memory: Minimizes overhead by registering the FD set once in kernel memory (epoll_ctl), returning only active events (epoll_wait) to user space without copying full arrays.

The kernel manages physical pages using a two-tier allocation hierarchy:

• Buddy Allocator: Handles large, coarse-grained physical memory allocations (power-of-two page sizes).
  • Mechanism: If a block of size $2^K$ is requested, the allocator splits a block of size $2^{K+1}$ into two equal "buddies". When physical memory is freed, adjacent free buddies are coalesced back into a single $2^{K+1}$ block to prevent external fragmentation.
• Slab Allocator (SLAB/SLUB): Eliminates internal fragmentation for small kernel objects (e.g., file descriptors, inodes, task structs).
  • Mechanism: It requests large page blocks from the Buddy Allocator and carves them into caches of pre-allocated, equal-sized object slots (slabs). Objects are allocated and constructed once, kept in memory, and recycled without running constructors/destructors repeatedly.