Operating Systems Interview Guide: Processes, Scheduling, Deadlocks and Memory

Why operating systems matter in interviews

Operating systems (OS) is one of the three big "core CS" subjects, with networks and databases. Service companies ask definitions, differences and numericals; product companies ask how the ideas connect to real problems such as a slow server, a race condition or a memory leak. See the core CS subjects guide for how this fits into your full plan.

A good answer follows one pattern: definition, why it exists, a small example, a trade-off. Practise saying each topic that way.

1. What an operating system does

An OS manages hardware on behalf of programs. Its jobs: process management (running programs and sharing the CPU), memory management, file system management, device management (drivers), security and protection and a user interface (shell or GUI).

• The kernel is the privileged core of the OS. Applications run in user mode; the kernel runs in kernel mode.
• A system call (such as read, write, fork, open) is how a program asks the kernel for a service; it switches from user mode to kernel mode and back.
• Kernel designs: monolithic (everything in the kernel, fast; Linux), microkernel (minimal kernel, services in user space, more isolation) and hybrid.
• Types of OS: batch, multiprogramming, time-sharing, real-time (hard and soft), distributed and embedded (embedded roadmap).
• Multiprogramming keeps several programs in memory so the CPU is never idle; multitasking switches between them quickly; multiprocessing uses several CPUs.

2. Processes

A process is a program in execution, with its own address space (code, data, heap, stack), registers and open files. The Process Control Block (PCB) stores everything the OS needs to pause and resume it: process id, state, program counter, registers, memory information and open files.

States: new, ready, running, waiting (blocked) and terminated. Transitions: ready to running (scheduler dispatch), running to ready (time slice ends or preemption), running to waiting (waits for I/O) and waiting to ready (I/O finishes).

Context switch: the OS saves the state of the running process in its PCB and loads another's. It is pure overhead, with no useful work during it, and also disturbs CPU caches.

Process creation (Unix): fork() creates a child that is a copy of the parent; it returns 0 in the child and the child's pid in the parent. exec() replaces the process image with a new program. wait() lets the parent collect the child's exit status.

pid_t pid = fork();
if (pid == 0) {
    execlp("ls", "ls", "-l", NULL);   // child runs ls
} else {
    wait(NULL);                        // parent waits
}

Classic puzzle: fork() called n times creates 2^n - 1 child processes. Zombie: a finished child whose parent has not yet called wait. Orphan: a child whose parent has finished; it is adopted by init.

Inter-process communication (IPC): pipes, named pipes (FIFOs), message queues, shared memory (fastest, needs synchronisation) and sockets.

3. Threads

A thread is a unit of execution inside a process. Threads share the code, data, heap and open files of their process, but each has its own stack, registers and program counter.

	Process	Thread
Memory	Separate address space	Shared with other threads of the process
Creation and switching	Heavier	Lighter
Communication	IPC needed	Shared memory directly
Failure	Isolated	One crashing thread can bring down the process

Models: user-level threads (fast, but a blocking call can block all), kernel-level threads, and mappings such as many-to-one, one-to-one and many-to-many. Benefits of multithreading: responsiveness, resource sharing, use of multiple cores. Risks: race conditions, deadlocks and harder debugging (Java multithreading).

4. CPU scheduling

The scheduler picks which ready process runs next. Goals: high CPU utilisation and throughput, low turnaround, waiting and response time, and fairness.

• Turnaround time = completion time minus arrival time
• Waiting time = turnaround time minus burst time
• Response time = time of first run minus arrival time

Algorithms:

• FCFS: first come, first served; non-preemptive; simple but causes the convoy effect
• SJF (shortest job first): minimises average waiting time; non-preemptive. The preemptive version is SRTF. Risk: starvation of long jobs.
• Priority scheduling: highest priority first; starvation is solved by aging (raising priority over time)
• Round robin: each process gets a time quantum and goes to the back of the queue; good for interactive systems; a very small quantum means too many context switches, a very large one behaves like FCFS
• Multilevel queue and multilevel feedback queue: several queues with different policies; processes can move between queues

Worked example (FCFS). Processes P1, P2, P3 arrive at time 0 with burst times 6, 8 and 3.

Process	Burst	Completion	Turnaround	Waiting
P1	6	6	6	0
P2	8	14	14	6
P3	3	17	17	14

Average waiting time = (0 + 6 + 14) / 3 = 6.67. With SJF the order is P3, P1, P2: waiting times are 0, 3 and 9, average 4. SJF wins here, which is the point of the algorithm. Practise 10 such numericals, including round robin with a quantum, and draw the Gantt chart every time.

5. Synchronisation

A race condition occurs when the result depends on the order in which threads access shared data. The critical section is the code that touches shared data. A correct solution needs mutual exclusion, progress and bounded waiting.

// two threads doing counter++ can lose updates:
// load counter -> add 1 -> store counter   (three steps, not atomic)

Tools:

• Mutex (lock): one owner at a time; the thread that locks must unlock
• Semaphore: an integer with wait (P) and signal (V); a binary semaphore acts like a lock, a counting semaphore controls access to N resources
• Monitor and condition variables: a language-level construct (synchronized, wait, notify in Java)
• Spinlock: busy-waits instead of sleeping; useful only for very short waits
• Atomic operations (compare-and-swap) and lock-free structures at an introductory level
• Mutex vs semaphore: a mutex has ownership and protects a critical section; a semaphore is a signalling mechanism and can be released by a different thread

Classic problems: producer-consumer (bounded buffer), readers-writers and dining philosophers. Know the idea of each solution: for producer-consumer use two counting semaphores (empty, full) and one mutex.

6. Deadlock

A deadlock is when a set of processes wait forever for resources held by each other. It needs all four Coffman conditions:

1. Mutual exclusion: a resource is held by only one process
2. Hold and wait: a process holds resources while waiting for others
3. No preemption: resources cannot be forcibly taken
4. Circular wait: a cycle of processes each waiting for the next

Handling:

• Prevention: break one condition (for example, impose a global ordering on locks to prevent circular wait)
• Avoidance: only grant a request if the system stays in a safe state; the Banker's algorithm
• Detection and recovery: build a resource-allocation graph; recover by killing a process or preempting resources
• Ignore it: the "ostrich algorithm" used by many general-purpose OSs

// deadlock risk: thread 1 locks A then B, thread 2 locks B then A
// fix: every thread locks in the same order (A then B)

Also know livelock (processes keep changing state without progress) and starvation (a process never gets resources). A strong answer to "how do you avoid deadlock in your own code?": consistent lock ordering, holding locks briefly, lock timeouts and avoiding nested locks.

7. Memory management

Address spaces: a program uses logical (virtual) addresses; the MMU translates them to physical addresses.

• Contiguous allocation: first fit, best fit, worst fit; suffers from external fragmentation (free space is scattered) and needs compaction
• Paging: physical memory is split into fixed-size frames, logical memory into pages; a page table maps pages to frames. No external fragmentation, but internal fragmentation in the last page.
• Segmentation: memory divided into logical segments (code, data, stack); causes external fragmentation
• TLB (translation lookaside buffer): a small, fast cache of page-table entries. Effective access time = hit ratio × (TLB time + memory time) + miss ratio × (TLB time + 2 × memory time) for a single-level page table.

Address translation example: with a 4 KB page size, a logical address is split into a page number (high bits) and an offset (low 12 bits). The page number indexes the page table to get the frame number; the physical address is frame number combined with the same offset.

8. Virtual memory

Virtual memory lets a process run even if it is only partly in RAM, by keeping unused pages on disk. Benefits: programs larger than memory, more processes in memory and isolation between processes.

• Demand paging: a page is loaded only when first used
• Page fault: the process touches a page not in memory; the OS finds a free frame (or evicts one), reads the page from disk and restarts the instruction
• Page replacement algorithms:
  • FIFO: evict the oldest page; can show Belady's anomaly (more frames can cause more faults)
  • Optimal: evict the page not needed for the longest time; theoretical benchmark
  • LRU (least recently used): evict the page unused for the longest time; good in practice, implemented with counters, a stack or approximations such as the clock algorithm
• Thrashing: the system spends more time swapping pages than executing, because too many processes compete for too little memory. Fix by reducing the degree of multiprogramming or using the working-set model.

Worked example (LRU, 3 frames). Reference string: 7, 0, 1, 2, 0, 3, 0, 4. Step by step: 7, 0 and 1 are faults that fill the frames. Reference 2 is a fault and evicts 7 (least recently used), leaving 0, 1, 2. Reference 0 is a hit. Reference 3 is a fault and evicts 1, leaving 0, 2, 3. Reference 0 is a hit again. Reference 4 is a fault and evicts 2, leaving 0, 3, 4. Total: 6 page faults and 2 hits. Always write the frame contents and the recency order after each reference; that habit prevents most mistakes.

9. File systems, disks and I/O

• Files, directories, inodes (metadata plus pointers to data blocks), hard links (another name for the same inode) vs symbolic links (a file holding a path)
• Allocation methods: contiguous, linked and indexed
• Disk scheduling: FCFS, SSTF, SCAN (elevator), C-SCAN; numericals ask for total head movement
• Buffering, caching and spooling, polling vs interrupts vs DMA
• Permissions and everyday commands (Linux essentials)

10. Frequently asked questions

1. What is an OS? What are its main functions?
2. Process vs thread; process vs program
3. What is a context switch? Why is it expensive?
4. What is a PCB? What are process states?
5. Zombie vs orphan process; what does fork() return?
6. Preemptive vs non-preemptive scheduling; compare FCFS, SJF, round robin
7. What is a race condition? What is a critical section?
8. Mutex vs semaphore; what is a spinlock?
9. Deadlock: conditions, prevention, avoidance (Banker's algorithm)
10. Paging vs segmentation; internal vs external fragmentation
11. What is virtual memory? What is a page fault? What is thrashing?
12. LRU vs FIFO; what is Belady's anomaly?
13. What happens when you type a command and press Enter?
14. Hard link vs soft link; what is an inode?
15. What is the difference between user mode and kernel mode?

11. How to study and answer

• Learn each topic in three layers: a one-line definition, a small diagram and a real example
• Solve at least 10 scheduling, page-replacement and disk-scheduling numericals by hand
• Write a small multithreaded program that has a race condition, then fix it with a lock (C guide)
• Explain each topic aloud without notes; if you cannot, you do not know it yet
• In the interview, give the simple answer first, then offer more depth: "Would you like me to go into how the Banker's algorithm works?"

Revise in the final week with the technical interview checklist.