Operating Systems Interview Questions — Medium

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).