Operating Systems Interview Questions — Hard

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.