Operating Systems Interview Questions and Answers

CPU scheduling decides which runnable thread runs next. Common policies:

• First Come First Served: simple and non-preemptive, but suffers the convoy effect when a long job blocks short ones.
• Shortest Job First: optimal average waiting time if burst lengths are known, but starvation is possible and bursts are usually guessed.
• Round Robin: each thread gets a time quantum; good response time, and the quantum trades context-switch overhead against interactivity.
• Priority: the highest priority runs; ageing prevents starvation.
• Multilevel feedback queue: multiple queues with different quanta, promoting interactive jobs and demoting CPU-bound ones.

RR with q=4: A(10) B(3) -> A4 B3 A4 A2

Real schedulers such as Linux's CFS approximate fair sharing by tracking virtual runtime rather than fixed priorities, and modern kernels also care about cache locality and NUMA. The right choice depends on whether the goal is throughput, latency or fairness.

Virtual memory gives each process the illusion of a large, contiguous address space, independent of physical RAM. The CPU's memory management unit translates virtual addresses to physical ones using page tables set up by the kernel.

Memory is divided into fixed-size pages, typically 4 KB, and physical memory into frames. A virtual address splits into a page number and an offset; the page table maps the page to a frame. A translation lookaside buffer caches recent translations to avoid walking the table on every access.

virtual addr = [ page number | offset ]
   -> page table -> [ frame number | offset ] physical

Pages not in RAM live on disk. Accessing one triggers a page fault: the kernel loads the page, possibly evicting another. Demand paging and copy-on-write make this efficient, and the working-set model explains thrashing. Virtual memory also provides isolation, since one process cannot name another's physical frames.

A deadlock is a set of threads each waiting for a resource held by another, so none can proceed. Four Coffman conditions must all hold: mutual exclusion, hold and wait, no preemption, and circular wait.

Thread 1 holds A, wants B
Thread 2 holds B, wants A

Prevention breaks at least one condition. Remove mutual exclusion where possible by making resources shareable. Avoid hold and wait by requesting all resources up front. Allow preemption or rollback. Most practically, impose a global ordering on lock acquisition so a cycle cannot form.

Avoidance uses knowledge of future requests, for example the Banker's algorithm, which grants a request only if the system stays in a safe state. Detection lets deadlocks happen, builds a wait-for graph, finds a cycle and recovers by killing or rolling back a victim. Timeouts are a crude practical mitigation but risk false positives.

A context switch is the act of saving the state of one thread or process and restoring another so execution can resume later. The kernel saves the program counter, registers, stack pointer, status flags and any floating-point state, then loads the saved state of the next runnable entity.

If the switch is between processes rather than threads, the address space changes too, so the page tables are switched and the TLB is flushed or tagged. That makes process switches noticeably more expensive than thread switches within a process.

save regs/PC of A -> choose B -> load regs/PC of B -> resume B

Costs include direct register save and restore, cache pollution because the new workload misses previously cached data, and TLB misses. Mitigations include larger time quanta, thread pools, CPU affinity and reducing syscall frequency. Understanding this overhead explains why very small scheduling quanta hurt throughput.

Both are synchronisation primitives, but they express different ideas.

A mutex provides mutual exclusion: it has an owner, it is locked or unlocked, and only the owner may unlock it. Use it to protect a critical section so only one thread at a time touches shared state.

A counting semaphore holds an integer and supports wait (decrement, block at zero) and signal (increment, wake a waiter). It has no ownership, so one thread can signal and another can wait. It is used to limit concurrency or to signal between threads.

mutex_lock(&m); balance += 10; mutex_unlock(&m);
sem_wait(&slots); /* ... */ sem_post(&slots);

A binary semaphore can act like a mutex but lacks ownership, which weakens invariant checking and priority inheritance. Prefer a mutex for locking and semaphores for signalling or resource counting. Condition variables plus a mutex are often clearer for waiting on a state change.

Thrashing is when a system spends more time paging than doing useful work. It happens when the total working set of active processes exceeds physical memory, so pages are evicted and immediately faulted back in. CPU utilisation collapses and disk I/O saturates.

Signs include high page-fault rates, low CPU utilisation, long run queues and heavy swap activity.

Causes and fixes:

• Too many processes for the available RAM: reduce the degree of multiprogramming or add memory.
• A poor replacement policy: use a good approximation of LRU such as clock, and keep frequently reused pages resident.
• A hot loop touching more data than fits in cache or memory: improve locality of reference.
• Aggressive swapping: tune swap behaviour, though on SSDs swapping can still destroy latency.

The working-set model keeps each process's recently used pages resident and refuses to admit a process that would push the total past available frames, which is a standard admission-control remedy.

The bounded buffer is solved with one mutex plus two counting semaphores, empty and full.

sem_t empty, full;
pthread_mutex_t m;
buffer[N]; int head, tail;

void put(item x) {
    sem_wait(&empty);
    pthread_mutex_lock(&m);
    buffer[tail] = x;
    tail = (tail + 1) % N;
    pthread_mutex_unlock(&m);
    sem_post(&full);
}
void get(item *x) {
    sem_wait(&full);
    pthread_mutex_lock(&m);
    *x = buffer[head];
    head = (head + 1) % N;
    pthread_mutex_unlock(&m);
    sem_post(&empty);
}

empty counts free slots, full counts filled slots, and the mutex protects the buffer and indices. Signal after unlocking so a waiter does not wake and immediately block on the mutex. Initialise empty to N and full to 0. Swapping the wait order, or holding the mutex while waiting on a semaphore, risks deadlock.