Skip to content
Tutorials Center
My learning

Topics

Lesson 25 of 77 ยท C, C++ and Systems Interview Questions

Operating Systems: Processes, Threads and Deadlocks

Answer operating systems interview questions on scheduling, context switches, mutex versus semaphore, deadlock conditions and paging with runnable simulators.

Operating systems questions test whether you understand what happens underneath your code: how many programs share one CPU, why threads are cheaper than processes, why two locks can freeze a program forever, and how a computer pretends to have more memory than it does. They appear in systems, backend and generalist interviews alike.

You cannot run a real scheduler or kernel inside a web page, so the ideas here come with stand-ins: small Node.js programs that simulate a scheduler, a mutex and a semaphore, a deadlock and a page table. They are teaching models with simplified rules, not an operating system. Related earlier lessons: C and C++: Pointers, Memory and Undefined Behavior for the stack and heap, and Java: Concurrency, Streams and Modern Java for locks in practice.

Processes, threads and context switches

Q: What is the difference between a process and a thread? A process is a running program with its own virtual address space, open files and resources, isolated from other processes. A thread is a unit of execution inside a process: threads of one process share its memory (heap, globals, open files) but each has its own stack and registers. Sharing makes threads cheap and fast to communicate, and also makes data races possible. Processes are heavier but a crash in one does not corrupt another; communication needs IPC (pipes, sockets, shared memory, message queues).

Process or thread?

Process Own memory. Strong isolation.
Thread Shared memory. Cheap to create.

Threads share the heap but never the stack.

1 / 2

Q: What is a context switch, and why does it cost something? When the OS stops one thread and runs another, it saves the first thread's registers and program counter, loads the second's, and (when switching between processes) changes the address space too. The direct cost is the save and restore; the larger hidden cost is that CPU caches and the TLB are now full of the wrong data. Too many threads means too many switches, which is why thread pools exist.

Q: What are the process states? New, ready (waiting for a CPU), running, waiting or blocked (for I/O or a lock) and terminated. A blocked process becomes ready when its event completes.

CPU scheduling

Q: Name some scheduling algorithms and their trade-offs.

  • First-come, first-served (FCFS): simple, but one long job makes short ones wait (the convoy effect).
  • Shortest job first (SJF): minimizes average waiting time but needs to know run lengths and can starve long jobs. The preemptive version is shortest remaining time first.
  • Round robin (RR): each process gets a time quantum in turn; fair and responsive. A tiny quantum wastes time on switches, a huge one degenerates into FCFS.
  • Priority scheduling: the highest priority runs first; low priorities can starve unless the OS applies aging.
  • Multilevel feedback queue: real systems combine queues, moving jobs between them based on observed behavior.

Useful terms: turnaround time (finish minus arrival), waiting time (turnaround minus run time), response time (first run minus arrival).

The stand-in schedules the same three jobs with FCFS, SJF and round robin (all arrive at time 0) and reports average waiting time:

Node.js Stand-in: FCFS, SJF and round robin

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or process.stdin), it gets the next line from this box.

Mutex versus semaphore

Q: What is the difference between a mutex and a semaphore? A mutex (mutual exclusion lock) protects a critical section: at most one thread holds it, and the thread that locked it is the one that must unlock it (it has an owner). A semaphore is a counter with two atomic operations, wait (decrement, block if zero) and signal (increment, wake a waiter). A counting semaphore allows up to N holders (for example, a pool of N connections). A binary semaphore (0 or 1) looks like a lock, but any thread may signal it, so it is also used for signaling between threads (a consumer waits until a producer signals).

Related terms: a critical section is code that touches shared data; a race condition is an outcome that depends on timing; a monitor bundles a lock with condition variables; a spinlock busy-waits instead of sleeping, only sensible for very short waits on multi-core machines.

C
pthread_mutex_lock(&lock);       // enter critical section
shared_counter++;
pthread_mutex_unlock(&lock);     // same thread leaves it

sem_wait(&free_slots);           // take a slot, block if none (semaphore)
sem_post(&used_slots);           // another thread can now consume

The code above is the real POSIX API, shown read-only. The stand-in models the two ideas with promises:

Node.js Stand-in: owner-checked mutex and a counting semaphore

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or process.stdin), it gets the next line from this box.

Deadlock

Q: What is a deadlock, and what are the four conditions? A set of threads each waiting for a resource another holds, so none can ever proceed. It requires all four Coffman conditions at once:

  1. Mutual exclusion: a resource can be held by only one thread.
  2. Hold and wait: a thread holds one resource while waiting for another.
  3. No preemption: resources cannot be forcibly taken away.
  4. Circular wait: a cycle of threads each waits for the next one's resource.

Break any one and deadlock is impossible. In practice the easiest is to remove circular wait: acquire locks in one global order. Other tools: acquire everything at once (no hold and wait), use tryLock with a timeout and back off, and detect-and-recover (for example, a database aborts one transaction of a deadlocked pair). Do not mix up related problems: starvation (a thread never gets a turn although others progress), livelock (threads keep reacting to each other and make no progress) and priority inversion (a high-priority task waits on a low-priority lock holder).

Four conditions

Mutual exclusion
Hold and wait
No preemption
Circular wait

Remove any one and deadlock cannot happen.

1 / 2

The stand-in runs two threads step by step. Each step either takes a lock or has to wait. When every unfinished thread is waiting, it reports the deadlock; with a consistent lock order, the same program finishes.

Node.js Stand-in: two threads, two locks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or process.stdin), it gets the next line from this box.

Virtual memory and paging

Q: What is virtual memory? Each process sees its own contiguous address space. The OS and the CPU's memory management unit translate virtual addresses to physical ones using a page table: memory is cut into fixed-size pages (commonly 4 KB) that map to physical frames. Benefits: isolation between processes, no need for contiguous physical memory, and the ability to keep only part of a program in RAM, with the rest on disk.

Q: What is a page fault? Accessing a page that is not currently mapped in RAM. The OS handles it by loading the page from disk (a slow operation, a major fault), possibly evicting another page first. If a process spends more time faulting than computing, the system is thrashing. The TLB is a small cache of recent translations that makes most lookups fast.

Q: Which page replacement policy is best? The theoretical optimum evicts the page used farthest in the future, which is impossible to know. LRU (least recently used) approximates it using past behavior and is good but costly to track exactly, so real systems use cheaper approximations such as the clock algorithm. FIFO is simple but can suffer Belady's anomaly: with some access patterns, adding more frames causes more faults. LRU does not have this anomaly.

Node.js Stand-in: FIFO versus LRU page replacement

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or process.stdin), it gets the next line from this box.

Deeper OS questions: Banker's algorithm, Peterson, page tables, disk scheduling, RAID and FAT

These come up in university-style interviews and in questions for systems roles. The code runs in Python so you can change the numbers and watch the answer change.

Deadlock avoidance: Banker's algorithm

Q: How can the OS avoid deadlock instead of detecting it afterwards? By granting a resource request only if the system stays in a safe state. A state is safe if some order exists in which every process can obtain its remaining needs and finish, one after another. An unsafe state does not mean deadlock has happened, only that it might happen.

The Banker's algorithm keeps these tables: Available (free units of each resource type), Max (the most each process may ever need), Allocation (what each holds now) and Need = Max - Allocation. Safety check: repeatedly find a process whose Need <= Work (starting with Work = Available), pretend it finishes, add its allocation back to Work, and continue. If all processes finish, the state is safe and the order is a safe sequence. Resource request: check the request is within Need and Available, pretend to grant it, and run the safety check; if unsafe, roll back and make the process wait. Cost: O(mยทnยฒ) for n processes and m resource types. It needs the maximum demand in advance and a fixed number of processes, which is why general-purpose systems rarely use it.

Python Banker's algorithm: safe sequence and a request

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the P4 line: (3, 3, 0) fits inside the free (3, 3, 2), so the request can be satisfied right now. But after granting it no process could be sure of finishing, so Banker's refuses. That is the point of avoidance: a request can be satisfiable and still lead to an unsafe state.

Peterson's solution to the critical-section problem

Q: Can two threads share a critical section using only shared variables, no hardware locks? Yes, for two threads: Peterson's algorithm. Each thread i sets flag[i] = true ("I want in") and then sets turn = j ("but you go first"). It waits while the other thread wants in and it is the other thread's turn. The turn variable breaks ties; the flags show interest. It satisfies mutual exclusion, progress (a thread outside the section never blocks the other) and bounded waiting (the other thread enters at most once ahead).

C
// Read-only: the pattern. It needs sequential consistency, which modern CPUs and
// compilers do not give for plain variables, so real code uses atomics or a mutex.
flag[i] = 1;
turn = j;
while (flag[j] && turn == j) { /* spin */ }
/* critical section */
flag[i] = 0;

The caveat is the interview point: on modern hardware, reordering of reads and writes breaks the algorithm unless you add memory fences or use atomic operations. In practice you use a mutex, which is built on atomic instructions such as compare-and-swap.

Instead of racing real threads (the outcome would depend on timing), the next TryIt explores every possible interleaving of the two threads' steps and checks whether both can be in the critical section at once. This is a tiny model checker.

Python Check every interleaving: Peterson versus two broken versions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Peterson passes both checks. "Flag only" keeps mutual exclusion but can deadlock (both set their flags and wait for each other). "Check then set" avoids deadlock but breaks mutual exclusion: both threads see the other idle, then both enter. The turn variable is what fixes both.

Page tables: hierarchical, hashed and inverted

A single-level page table maps every virtual page to a frame; with a 48-bit address space that table would be gigabytes per process. Real systems use one of three structures:

  • Hierarchical (multi-level) page tables: the page number is split, and inner tables are allocated only for regions that are used. x86-64 uses four or five levels. A walk costs several memory reads, hence the TLB cache.
  • Hashed page tables: the virtual page number is hashed into a table of chains. Useful for sparse, very large (64-bit) address spaces.
  • Inverted page tables: one entry per physical frame (not per virtual page), holding the (process ID, page number) that owns it. Memory use scales with RAM, not with the number of processes, but finding a page means searching, so a hash is used. Sharing pages between processes is harder.

Disk scheduling

On a spinning disk, the cost is dominated by seek time (moving the head). Schedulers reorder the request queue: FCFS (fair, lots of movement), SSTF (shortest seek first: good throughput, can starve far requests), SCAN or the "elevator" (sweep to one end, then back), C-SCAN (sweep one way, jump back, more uniform wait) and LOOK/C-LOOK (like SCAN but turn around at the last request instead of the disk edge). SSDs have no seek time, so these matter much less there.

Python Total head movement for four policies

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

RAID in one table

RAID combines several disks for speed, safety or both. Striping splits data across disks; mirroring copies it; parity stores a checksum so one lost disk can be rebuilt.

Level How Fault tolerance Notes
RAID 0 Striping only None: one disk lost, all data lost Fastest, no redundancy
RAID 1 Mirroring One disk per pair Simple, 50% usable space
RAID 5 Striping + distributed parity One disk Good read speed, slower small writes; at least 3 disks
RAID 6 Striping + two parities Two disks Safer for large arrays
RAID 10 Mirrored pairs, striped One disk per pair (often more) Fast and safe, 50% usable space

RAID is not a backup: it protects against a disk failure, not against deleting a file or ransomware. The parity in RAID 5 is just an XOR of the data blocks, so any single missing block can be recomputed from the others.

Python Rebuild a lost disk from XOR parity

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

File allocation: FAT and friends

Contiguous allocation is fast but suffers fragmentation. Linked allocation chains blocks but makes random access slow (follow n pointers). FAT (file allocation table) keeps all the "next block" pointers in one table loaded into memory, so following a chain is quick and the data blocks hold only data; a directory entry stores the first block, and the table entry says what comes next or marks end-of-file. The cost is that the whole table must be cached, which is why FAT does not scale to huge volumes. Indexed allocation (a Unix inode) keeps all block pointers of a file in one index structure, with indirect blocks for large files, giving fast random access. Modern file systems add journaling or copy-on-write to survive crashes.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What do threads of the same process share?

    Threads share the process's memory and resources but each has its own stack and registers.
  2. 2. Which statement about a mutex and a semaphore is correct?

    Ownership is the key difference. Counting semaphores allow up to N holders, and signaling between threads is a semaphore use case.
  3. 3. Which change reliably prevents the classic two-lock deadlock?

    A consistent lock order removes circular wait, one of the four conditions. Without all four, deadlock cannot occur.
  4. 4. What is Belady's anomaly?

    It is a property of FIFO page replacement on certain reference strings. LRU is a stack algorithm and does not show it.

Summary

  • Processes are isolated programs; threads share a process's memory but have their own stacks. Context switches cost saved state and cold caches.
  • Schedulers trade fairness, throughput and responsiveness: FCFS, SJF, round robin, priority, multilevel feedback.
  • A mutex has an owner and guards a critical section; a semaphore is a counter used for limits and signaling.
  • Deadlock needs mutual exclusion, hold and wait, no preemption and circular wait; a global lock order is the standard fix.
  • Paging maps virtual pages to frames; page faults load from disk; LRU approximates the ideal replacement and FIFO can show Belady's anomaly.
  • Banker's algorithm grants a request only if a safe sequence still exists; unsafe does not mean deadlocked, only possible.
  • Peterson's solution uses flags plus a turn variable for two threads, but needs atomics or fences on modern hardware.
  • Hierarchical, hashed and inverted page tables trade memory for lookup cost; SCAN/LOOK reduce disk seek time; RAID 5 parity is XOR; FAT stores next-block pointers in one table.

Next: HTML and CSS Interview Questions.