Operating Systems Interview Questions and Numerical Problems

How to use this page

This is the revision lesson for the Operating Systems track. It collects the questions that come up most often in OS interview rounds for software-engineering roles, from campus placements to experienced backend interviews, with a short model answer for each. After the questions come eight numerical problems of the kind asked in written tests and whiteboard rounds, each solved step by step, and finally a one-page checklist.

How to practise:

1. Read the question and answer it out loud before reading the model answer. Interviews test explanation, not recognition.
2. Aim for the shape of the model answers: a one-sentence definition, the key mechanism, then one example or trade-off. Two to four sentences is the right length for a first answer; the interviewer will ask for more if they want it.
3. Where an answer feels thin, follow the link to the full lesson.
4. Solve each numerical problem on paper before reading the solution.

Interviewers rarely stop at the first answer. Each group below ends with the follow-up questions that typically come next, so you can prepare the second layer too.

Processes and threads

Full lessons: Introduction, Processes, Threads.

Q1. What is an operating system?

An operating system is the software layer that manages hardware resources (CPU, memory, storage, devices) and provides services and abstractions (processes, files, sockets) to programs. It acts as a resource allocator, deciding who gets what, and as a control program, preventing errors and misuse. The kernel is the part that always runs in privileged mode.

Q2. What is the difference between a program and a process?

A program is a passive file of instructions on disk. A process is a program in execution: it has its own address space (code, data, heap, stack), registers including the program counter, open files and a state. One program can run as many processes at once, such as several terminal windows.

Q3. What are the states of a process?

New (being created), ready (waiting for a CPU), running (executing), waiting or blocked (waiting for an event such as I/O), and terminated. A running process moves to ready when pre-empted, to waiting when it requests I/O, and from waiting back to ready when the event completes. Only the scheduler moves a process from ready to running.

Q4. What is a process control block (PCB)?

The kernel data structure that represents a process. It holds the process ID, state, saved registers and program counter, scheduling information, memory-management information (page table pointer), open-file table and accounting data. On a context switch the kernel saves the running process's state into its PCB and loads the next one's.

Q5. What is a context switch and why is it costly?

Switching the CPU from one process or thread to another by saving the current register state and loading the next. Direct cost is the save and restore plus kernel code; indirect cost is larger: caches and the TLB lose their useful contents (unless tagged with ASIDs) and the new task starts cold. Too many switches waste CPU time that could run useful work.

Q6. What is the difference between a process and a thread?

A process is a unit of resource ownership with its own address space; a thread is a unit of execution within a process. Threads of one process share code, heap, global data and open files but each has its own stack, registers and program counter. Threads are cheaper to create and switch between, but a bug in one thread can corrupt memory for all of them.

Q7. What are user-level and kernel-level threads?

User-level threads are managed by a library in user space, so they are cheap but the kernel sees only one schedulable entity, and one blocking system call can block all of them. Kernel-level threads are scheduled by the kernel, can run in parallel on several cores and block independently. Linux and Windows map each user thread to a kernel thread (one-to-one); runtimes such as Go multiplex many lightweight goroutines onto fewer kernel threads (many-to-many).

Q8. What does fork() return, and what does exec() do?

fork() creates a child that is a copy of the parent; it returns the child's PID in the parent, 0 in the child and -1 on failure. exec() replaces the calling process's program image with a new program, keeping the PID and open descriptors. A shell runs a command by forking and then calling exec in the child.

Q9. What are zombie and orphan processes?

A zombie has exited, but its parent has not yet called wait() to collect its status, so its process-table entry remains. An orphan is a running process whose parent has exited; it is adopted by init (PID 1), which reaps it when it exits. Many zombies indicate a parent that does not call wait().

Q10. What are the main inter-process communication (IPC) mechanisms?

Shared memory (fastest, needs synchronisation), message passing (pipes, FIFOs, message queues, sockets), signals for simple notifications, and memory-mapped files. Shared memory avoids kernel copies after setup; message passing is simpler and works across machines with sockets.

Typical follow-ups: what happens to the parent's open files after fork() (they are shared, including offsets), why fork() is cheap (copy-on-write), and how threads in one process communicate (shared memory protected by locks).

CPU scheduling

Full lesson: CPU scheduling.

Q11. What are the goals of CPU scheduling?

Maximise CPU utilisation and throughput, and minimise turnaround time, waiting time and response time, while staying fair. The goals conflict: batch systems favour throughput, interactive systems favour response time, real-time systems need deadlines met.

Q12. Define turnaround time, waiting time and response time.

Turnaround time is completion time minus arrival time. Waiting time is turnaround time minus CPU burst time, the time spent in the ready queue. Response time is the time from arrival until the process first gets the CPU.

Q13. What is the difference between pre-emptive and non-pre-emptive scheduling?

In non-pre-emptive scheduling a process keeps the CPU until it blocks or finishes. In pre-emptive scheduling the OS can take the CPU away, typically on a timer interrupt or when a higher-priority process becomes ready. All general-purpose OSes today are pre-emptive, which gives better responsiveness but requires careful synchronisation.

Q14. Explain FCFS, SJF and SRTF.

FCFS runs processes in arrival order; simple but short jobs wait behind long ones (the convoy effect). SJF runs the shortest next burst first and is optimal for average waiting time among non-pre-emptive algorithms. SRTF is its pre-emptive version, switching whenever a new arrival has a shorter remaining time; both need burst predictions and can starve long jobs.

Q15. How does Round Robin work, and how do you choose the quantum?

Each ready process runs for at most one time quantum, then goes to the back of the queue. A very large quantum makes it behave like FCFS; a very small one causes too many context switches. A common guideline is that most CPU bursts should finish within one quantum, with the quantum much larger than the context-switch cost.

Q16. What is starvation and how does aging solve it?

Starvation is a ready process waiting indefinitely because others are always chosen first, as can happen with priority scheduling or SJF. Aging gradually raises the priority of processes that have waited a long time, so they are eventually scheduled.

Q17. What is a multilevel feedback queue?

Several ready queues with different priorities and quanta. New processes start in the top queue; a process that uses its whole quantum moves down, and one that waits too long can move up. It approximates SJF without knowing burst lengths, favouring interactive, I/O-bound processes.

Q18. What is priority inversion?

A high-priority task waits for a lock held by a low-priority task, while medium-priority tasks pre-empt the low-priority one, so the high-priority task effectively waits for the medium ones. Priority inheritance fixes it by temporarily raising the lock holder's priority to that of the highest waiter. It famously affected the Mars Pathfinder lander in 1997.

Typical follow-ups: compute average waiting time for a given set (see numerical problem 2), how Linux schedules normal tasks (CFS, replaced by EEVDF in 6.6), and what makes a process I/O-bound versus CPU-bound.

Synchronization

Full lessons: Synchronization, Classic synchronization problems.

Q19. What is a race condition?

A bug where the result depends on the unpredictable interleaving of threads accessing shared data, at least one of them writing. For example two threads doing count++ can lose an update because the read, add and write steps interleave. It is fixed by making the access atomic or mutually exclusive.

Q20. What is a critical section, and what must a solution guarantee?

A critical section is code that accesses shared data. A correct solution must guarantee mutual exclusion (one thread inside at a time), progress (if nobody is inside, a waiting thread can enter without indefinite postponement), and bounded waiting (a limit on how often others can enter before a waiting thread does).

Q21. What is the difference between a mutex and a semaphore?

A mutex is a lock with ownership: only the thread that locked it should unlock it, and it guards one critical section. A semaphore is an integer counter with atomic wait (decrement, block if zero) and signal (increment) operations, with no owner; a counting semaphore can admit N threads, and semaphores are also used for signalling between threads. A binary semaphore resembles a mutex but lacks ownership and features like priority inheritance.

Q22. What is a spinlock and when is it appropriate?

A lock where a waiting thread loops checking the lock instead of sleeping. It avoids context-switch cost, so it suits very short critical sections on multiprocessors, especially inside kernels. On a single CPU, or for long waits, it wastes CPU time.

Q23. What are monitors and condition variables?

A monitor is a language-level construct that bundles shared data with procedures and guarantees only one thread runs inside at a time. Condition variables let a thread inside wait for a condition, releasing the lock, and be woken by another thread's signal. Java's synchronized with wait/notify and pthread mutexes with condition variables follow this model; always re-check the condition in a loop because of spurious wake-ups.

Q24. What hardware support do locks rely on?

Atomic instructions such as test-and-set, compare-and-swap (CAS), and fetch-and-add, plus memory barriers that stop the CPU and compiler from reordering memory operations across the lock. Pure software solutions like Peterson's algorithm work in theory but fail on modern CPUs without barriers.

Q25. Explain the producer-consumer problem and its semaphore solution.

Producers add items to a bounded buffer and consumers remove them; producers must wait when it is full and consumers when it is empty. Use semaphores empty (initially N), full (initially 0) and a mutex: a producer waits on empty, locks, inserts, unlocks, signals full; a consumer mirrors this. Waiting on the mutex before empty can deadlock.

Q26. What is the readers-writers problem?

Many readers may read shared data simultaneously, but a writer needs exclusive access. The first variant favours readers and can starve writers; the second favours writers and can starve readers. Read-write locks such as pthread_rwlock_t implement it.

Q27. What is the dining philosophers problem, and how do you avoid deadlock in it?

Five philosophers share five forks and need both neighbouring forks to eat; if each picks up the left fork first, all can wait forever. Solutions: impose an order (pick up the lower-numbered fork first), allow at most four philosophers to sit, or pick up both forks atomically. It illustrates deadlock and starvation in resource sharing.

Typical follow-ups: what is a deadlock between two mutexes and how lock ordering prevents it, what volatile does and does not guarantee, and how atomic variables differ from locks.

Deadlocks

Full lesson: Deadlocks.

Q28. What is a deadlock?

A set of processes each waiting for a resource held by another process in the set, so none can proceed. For example T1 holds lock A and waits for B, while T2 holds B and waits for A.

Q29. What are the four necessary conditions for deadlock?

Mutual exclusion (resources cannot be shared), hold and wait (a process holds resources while requesting more), no pre-emption (resources cannot be forcibly taken), and circular wait (a cycle of processes each waiting for the next). All four must hold simultaneously; breaking any one prevents deadlock.

Q30. How can deadlock be prevented?

By ensuring one condition can never hold: make resources shareable where possible, require processes to request all resources at once (no hold and wait), allow pre-emption of resources, or impose a global ordering on resource acquisition (no circular wait). Lock ordering is the most practical technique in real code.

Q31. What is the difference between deadlock prevention and avoidance?

Prevention restricts how requests can be made so a deadlock is structurally impossible. Avoidance allows requests but, using advance knowledge of each process's maximum needs, grants one only if the system remains in a safe state, as in the Banker's algorithm. Avoidance gives better utilisation but needs information that is rarely available in general-purpose systems.

Q32. What is a safe state?

A state in which there is at least one order (a safe sequence) in which every process can obtain its maximum remaining needs and finish. An unsafe state is not necessarily deadlocked, but it may lead to deadlock. The Banker's algorithm keeps the system in safe states only.

Q33. How is deadlock detected and recovered from?

With single instances of each resource, look for a cycle in the wait-for graph; with multiple instances, run a detection algorithm similar to the Banker's safety check. Recovery means terminating processes (all, or one at a time until the cycle breaks) or pre-empting resources and rolling processes back. Databases detect deadlocks this way and abort one transaction.

Q34. What do real operating systems do about deadlock?

Most general-purpose OSes ignore it for application resources (the "ostrich" approach), leaving prevention to programmers through lock ordering and timeouts. The kernel itself uses strict lock-ordering rules, and Linux has a run-time checker (lockdep) that reports potential ordering violations during development.

Typical follow-ups: work through a Banker's safety check (numerical problem 3), the difference between deadlock and livelock, and whether a resource allocation graph with a cycle always means deadlock (only if each resource has a single instance).

Memory management

Full lesson: Memory management.

Q35. What is the difference between logical and physical addresses?

A logical (virtual) address is generated by the CPU while running a program; a physical address is the actual RAM location. The MMU translates between them on every access, which lets each process have its own address space and lets the OS place it anywhere in memory.

Q36. What is the difference between internal and external fragmentation?

Internal fragmentation is wasted space inside an allocated block because blocks come in fixed sizes, for example the unused part of a process's last page. External fragmentation is free memory split into small non-contiguous holes, none big enough for a request, even though the total is sufficient. Paging removes external fragmentation; segmentation and variable partitioning suffer from it.

Q37. Compare first fit, best fit and worst fit.

First fit takes the first hole large enough and is fastest. Best fit takes the smallest adequate hole, leaving tiny unusable slivers and requiring a full search. Worst fit takes the largest hole so that leftovers are large, but it quickly destroys big holes; simulations generally favour first or best fit.

Q38. What is paging?

A scheme that divides logical memory into fixed-size pages and physical memory into frames of the same size, mapping pages to any free frames through a per-process page table. An address splits into a page number, used to index the page table, and an offset, copied unchanged. It eliminates external fragmentation and makes sharing and virtual memory easy.

Q39. What is a TLB?

A small, fast associative cache of recent page-to-frame translations inside the CPU. A hit avoids reading the page table from memory; a miss requires a page-table walk. Because of locality, hit rates are very high, and entries may be tagged with address-space IDs to avoid flushing on every context switch.

Q40. Why use multi-level page tables?

A flat page table must cover the entire virtual address space, for example 4 MB per process for 32-bit addresses with 4 KB pages, or 512 GB for 48-bit addresses with 8-byte entries. Multi-level tables allocate only the inner tables for regions actually in use. The trade-off is one extra memory access per level on a TLB miss.

Q41. What is an inverted page table?

One table for the whole system with one entry per physical frame, recording which process and virtual page occupy it. Its size depends on RAM, not on the number of processes, but lookups need hashing and sharing a frame between processes is awkward.

Q42. What is segmentation, and how does it differ from paging?

Segmentation divides a process into variable-size logical units (code, stack, heap) addressed as (segment, offset) and translated with a base and limit per segment. It matches the programmer's view and gives natural protection, but causes external fragmentation. Paging uses fixed invisible units; x86-64 effectively uses paging only.

Typical follow-ups: split an address into page number and offset (numerical problem 4), compute effective access time (numerical problem 5), and explain how shared libraries are shared between processes.

Virtual memory

Full lesson: Virtual memory.

Q43. What is virtual memory?

A technique that lets a process run with only part of its address space in RAM, keeping the rest on disk and loading pages on demand. It allows programs larger than physical memory, more processes in memory at once, and cheap features like copy-on-write and memory-mapped files.

Q44. What is a page fault, and what happens when one occurs?

A trap raised when a process accesses a page not currently mapped in RAM. The kernel checks the access is legal (otherwise it sends SIGSEGV), finds a free frame or evicts a victim (writing it back if dirty), reads the page from disk while the process blocks, updates the page table and restarts the instruction.

Q45. Compare FIFO, LRU and Optimal page replacement.

FIFO evicts the oldest loaded page; it is simple but may evict heavily used pages and shows Belady's anomaly. Optimal evicts the page not needed for the longest time in the future; it gives the minimum faults but cannot be implemented. LRU evicts the page unused for the longest time in the past, usually close to optimal, and is approximated in practice with reference bits.

Q46. What is Belady's anomaly?

The counter-intuitive case where giving FIFO more frames increases page faults, for example the string 1,2,3,4,1,2,5,1,2,3,4,5 gives 9 faults with 3 frames but 10 with 4. LRU and Optimal are stack algorithms and never show it.

Q47. How does the Clock (second-chance) algorithm work?

Frames form a circle with a pointer. On a fault, if the page under the pointer has its reference bit set, the bit is cleared and the pointer moves on; the first page found with a clear bit is evicted. It approximates LRU using the hardware reference bit at FIFO-like cost.

Q48. What is thrashing, and how is it prevented?

Thrashing is when processes spend most of their time page-faulting because their combined active pages exceed RAM, so CPU utilisation collapses. It is prevented by limiting the degree of multiprogramming with the working-set model or page-fault-frequency control, suspending processes, or adding memory.

Q49. What is the working set?

The set of distinct pages a process referenced in the most recent window of Δ references, approximating its current locality. If the sum of working-set sizes exceeds available frames, the OS should suspend a process to avoid thrashing.

Q50. What is copy-on-write?

After fork(), parent and child share all pages read-only instead of copying them. When either writes, a fault makes the kernel copy just that page for the writer. Most pages are never copied, especially when the child immediately calls exec().

Typical follow-ups: trace a reference string (numerical problem 6), what the Linux OOM killer does and why malloc rarely fails on Linux (overcommit), and what huge pages are for (fewer TLB misses).

File systems

Full lesson: File systems.

Q51. What is an inode?

A per-file on-disk record holding metadata (type, permissions, owner, size, timestamps, link count) and pointers to the file's data blocks. It does not store the file name; directories map names to inode numbers.

Q52. What is the difference between a hard link and a symbolic link?

A hard link is another directory entry for the same inode, so the data remains until every link is removed and no process has it open; it cannot cross file systems or point to directories. A symbolic link is a separate small file containing a path; it can point anywhere but dangles if the target is moved or deleted.

Q53. Compare contiguous, linked and indexed allocation.

Contiguous allocation is fast for sequential and random access but suffers external fragmentation and makes files hard to grow. Linked allocation avoids fragmentation but makes random access slow and is fragile; FAT moves the links into a cached table. Indexed allocation stores all block pointers in an index block, giving fast random access; Unix inodes combine direct and indirect index blocks.

Q54. What is journaling?

A file system writes intended metadata (and optionally data) changes to a log, then a commit record, before applying them in place. After a crash it replays committed transactions and discards incomplete ones, making recovery fast and keeping structures consistent. ext4 journals metadata in ordered mode by default.

Q55. What happens when you delete a file that is still open?

unlink removes the name and decrements the link count, but the inode and data blocks are freed only when the last open descriptor is closed. That is why deleting a large log file being written by a running process does not free disk space until the process closes it or restarts.

Q56. What is the VFS?

The Virtual File System is a kernel layer with common objects (superblock, inode, dentry, file) and operation tables that each file system implements. It lets the same system calls work across ext4, XFS, NFS, FAT and pseudo file systems like /proc.

Q57. How is free space tracked?

With a bitmap (one bit per block; easy to find contiguous runs), a linked list of free blocks, grouping (a free block stores addresses of other free blocks) or counting (start and length of free runs, as extents). A bitmap for a 1 TiB disk with 4 KiB blocks takes 32 MiB.

Typical follow-ups: maximum file size with direct and indirect pointers (numerical problem 8), why write() returning does not mean data is on disk (fsync), and how mounting works.

I/O and storage

Full lesson: Storage and I/O.

Q58. Compare the disk scheduling algorithms.

FCFS serves in arrival order; fair but slow. SSTF serves the nearest request; low movement but can starve distant requests. SCAN sweeps end to end like an elevator; LOOK reverses at the last request; C-SCAN and C-LOOK serve in one direction only for more uniform waiting times.

Q59. What is DMA?

Direct memory access lets a device controller transfer a block of data between the device and memory without the CPU copying each word. The CPU sets up the transfer and receives one interrupt at the end, freeing it for other work during bulk I/O.

Q60. Polling versus interrupts: when is each better?

Interrupts let the CPU work until a device signals it, which is efficient for slow or infrequent events. Polling repeatedly checks device status; it wastes cycles for slow devices but beats interrupts when the device responds almost immediately or events arrive at very high rates, which is why high-speed network and NVMe drivers can switch to polling.

Q61. Compare RAID 0, 1, 5 and 10.

RAID 0 stripes data with no redundancy for full capacity and speed. RAID 1 mirrors for redundancy with one disk's capacity. RAID 5 stripes with distributed parity, giving n - 1 disks of capacity and tolerance of one failure, at the cost of a small-write penalty. RAID 10 stripes over mirrored pairs, giving half the capacity with good write performance and fast rebuilds.

Q62. How does epoll differ from select?

select scans all watched descriptors on every call and is limited to 1024 descriptors by default. epoll registers interest once and returns only ready descriptors, so its cost scales with active connections rather than total connections. That is why event-driven servers on Linux use epoll.

Typical follow-ups: compute head movement for a request queue (numerical problem 7), why SSDs need TRIM and do not benefit from seek-optimising schedulers, and the difference between non-blocking and asynchronous I/O.

Linux and security

Full lessons: Linux internals, Virtualization and security.

Q63. What is a system call, and how does it differ from a library function call?

A system call is a request to the kernel through a controlled entry point that switches the CPU from user mode to kernel mode, such as read or fork. A library call like strlen runs entirely in user space; some library functions such as printf eventually make system calls (write). System calls are far more expensive because of the mode switch and checks.

Q64. What is the difference between SIGTERM and SIGKILL?

SIGTERM asks a process to terminate and can be caught so it can clean up; SIGKILL cannot be caught or ignored and terminates the process immediately. Send SIGTERM first and SIGKILL only after a grace period; exit code 137 means a process was killed with SIGKILL.

Q65. What makes a container different from a virtual machine?

A container is a set of host processes isolated by namespaces (what they can see) and limited by cgroups (what they can use), sharing the host kernel. A VM runs its own kernel on virtual hardware provided by a hypervisor. Containers are lighter and faster to start; VMs offer stronger isolation.

Q66. What are user mode and kernel mode?

Two CPU privilege levels. Kernel mode can run privileged instructions and access all memory; user mode cannot, and attempts trap to the kernel. Applications run in user mode and enter the kernel only through system calls, exceptions or interrupts.

Q67. What does chmod 755 mean?

Owner rwx (7 = 4 + 2 + 1), group r-x (5), others r-x (5): everyone can read and execute, only the owner can modify. It is the usual mode for executables and public directories.

Q68. How do ASLR, NX and stack canaries prevent buffer overflow exploits?

Canaries detect overwrites of the stack frame before a function returns. NX marks stack and heap pages non-executable so injected code cannot run. ASLR randomises memory layout so attackers cannot predict the addresses needed to reuse existing code. Each blocks a different step, so they are used together.

Typical follow-ups: reading free and top output (watch available, not free), finding which process holds a port (ss -ltnp or lsof -i), and what a zombie is.

Eight numerical problems with solutions

Every number below has been checked by simulation. Work each problem before reading the solution.

Problem 1: counting fork() calls

How many times does this program print hello, and how many child processes are created?

#include <stdio.h>
#include <unistd.h>

int main(void) {
    for (int i = 0; i < 3; i++)
        fork();
    printf("hello from %d\n", getpid());
    return 0;
}

Solution.

1. Before the loop there is 1 process.
2. Each fork() call is executed by every process that exists at that point, and each one doubles the count: after iteration 0 there are 2 processes, after iteration 1 there are 4, after iteration 2 there are 8.
3. All 8 reach printf, so hello is printed 8 times (2^3).
4. Child processes created = 8 - 1 = 7 (2^n - 1).

            P
      fork  |  i=0
        +---+---+
        P       C1
  fork  | i=1   | i=1
     +--+--+  +-+--+
     P    C2  C1   C3
 i=2: each of the 4 forks again -> 8 processes

General rule: n sequential fork() calls executed by every process give 2^n processes.

Problem 2: Round Robin scheduling

Quantum = 2. When a process's quantum expires at the same moment new processes arrive, the new arrivals join the ready queue before the pre-empted process.

Find the Gantt chart, the average turnaround time and the average waiting time.

Solution. Trace the ready queue:

1. t = 0: only P1. P1 runs 0 to 2 (remaining 3). P2 (1) and P3 (2) have arrived, then P1 rejoins. Queue: P2, P3, P1.
2. P2 runs 2 to 4 (remaining 1). P4 (3) and P5 (4) arrive, then P2 rejoins. Queue: P3, P1, P4, P5, P2.
3. P3 runs 4 to 5 and finishes (burst 1). Queue: P1, P4, P5, P2.
4. P1 runs 5 to 7 (remaining 1). Queue: P4, P5, P2, P1.
5. P4 runs 7 to 9 and finishes. Queue: P5, P2, P1.
6. P5 runs 9 to 11 (remaining 1). Queue: P2, P1, P5.
7. P2 runs 11 to 12 and finishes.
8. P1 runs 12 to 13 and finishes.
9. P5 runs 13 to 14 and finishes.

| P1 | P2 | P3| P1 | P4 | P5 |P2 |P1 |P5 |
0    2    4   5    7    9    11  12  13  14

Turnaround = completion - arrival; waiting = turnaround - burst.

Average turnaround = (13 + 11 + 3 + 6 + 10) / 5 = 43 / 5 = 8.6. Average waiting = (8 + 8 + 2 + 4 + 7) / 5 = 29 / 5 = 5.8.

If a problem uses the other tie-breaking convention (pre-empted process first), the chart can change, so always state the convention.

Problem 3: Banker's algorithm safety check

Three resource types A, B, C with totals (9, 6, 9). Is this state safe? If so, give a safe sequence.

Solution.

1. Total allocated = (1+2+3+0+1, 1+1+0+2+1, 2+2+1+0+2) = (7, 5, 7).
2. Available = (9, 6, 9) - (7, 5, 7) = (2, 1, 2).
3. Need = Max - Allocation:

1. Work = (2, 1, 2). Scan for a process whose need fits within Work, let it finish, and add its allocation back:
   • P0 needs (3, 2, 1): A 3 > 2, no.
   • P1 needs (1, 1, 0) fits. Work = (2, 1, 2) + (2, 1, 2) = (4, 2, 4).
   • P2 needs (6, 0, 1): A 6 > 4, no.
   • P3 needs (7, 3, 3): no.
   • P4 needs (1, 0, 1) fits. Work = (4, 2, 4) + (1, 1, 2) = (5, 3, 6).
   • Second pass, P0 needs (3, 2, 1) fits. Work = (5, 3, 6) + (1, 1, 2) = (6, 4, 8).
   • P2 needs (6, 0, 1) fits. Work = (6, 4, 8) + (3, 0, 1) = (9, 4, 9).
   • P3 needs (7, 3, 3) fits. Work = (9, 4, 9) + (0, 2, 0) = (9, 6, 9).
2. All processes finish, so the state is safe, with safe sequence P1, P4, P0, P2, P3. Other safe sequences may exist. The final Work equals the totals, a useful arithmetic check.

Problem 4: paging address translation

A system has 32-bit virtual addresses, 8 KiB pages and 4-byte page table entries.

(a) How many bits are the page number and offset? (b) How large is a flat page table? (c) Translate virtual address 0x00403A7C if that page is in frame 0x2B1. (d) Split the page number for a two-level table in which each inner table fills exactly one page.

Solution.

(a) 8 KiB = 2^13, so the offset is 13 bits and the page number is 32 - 13 = 19 bits.

(b) 2^19 entries x 4 bytes = 2^21 bytes = 2 MiB.

(c) The offset is 13 bits, not a multiple of 4, so do it numerically:

1. Page number = 0x00403A7C shifted right by 13 = 0x201 = 513.
2. Offset = 0x00403A7C AND 0x1FFF = 0x1A7C = 6780.
3. Physical address = frame shifted left by 13, plus offset = 0x2B1 x 8192 + 6780 = 0x562000 + 0x1A7C = 0x563A7C.

(d) One page holds 8192 / 4 = 2048 = 2^11 entries, so the inner index is 11 bits and the outer index is 19 - 11 = 8 bits.

 31        24 23              13 12             0
 +-----------+------------------+----------------+
 | outer (8) |    inner (11)    |  offset (13)   |
 +-----------+------------------+----------------+

Problem 5: effective access time with a TLB

A system has a two-level page table, a TLB lookup time of 10 ns, a memory access time of 100 ns, and a TLB hit ratio of 95 percent. Find the effective access time. Assume the TLB is searched before memory.

Solution.

1. Hit: TLB (10) + data access (100) = 110 ns.
2. Miss: TLB (10) + two page-table accesses (2 x 100) + data access (100) = 310 ns.
3. EAT = 0.95 x 110 + 0.05 x 310 = 104.5 + 15.5 = 120 ns.

That is 20 percent slower than a raw memory access. If the question says to ignore TLB time, hit = 100 and miss = 300, giving 0.95 x 100 + 0.05 x 300 = 110 ns.

Problem 6: page replacement

Reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 with 3 frames, initially empty. Count faults for FIFO, LRU and Optimal.

FIFO:

Ref    7  0  1  2  0  3  0  4  2  3  0  3  2
F0     7  7  7  2  2  2  2  4  4  4  0  0  0
F1     -  0  0  0  0  3  3  3  2  2  2  2  2
F2     -  -  1  1  1  1  0  0  0  3  3  3  3
       F  F  F  F     F  F  F  F  F  F

FIFO = 10 faults.

LRU:

Ref    7  0  1  2  0  3  0  4  2  3  0  3  2
F0     7  7  7  2  2  2  2  4  4  4  0  0  0
F1     -  0  0  0  0  0  0  0  0  3  3  3  3
F2     -  -  1  1  1  3  3  3  2  2  2  2  2
       F  F  F  F     F     F  F  F  F

Key steps: at the first ref 2, page 7 is least recently used, so 7 goes; at ref 3, the least recently used of (2, 0, 1) is 1, so 1 goes; at ref 4, of (2, 0, 3) the LRU is 2; at ref 2, of (4, 0, 3) the LRU is 3; at ref 3, of (4, 0, 2) the LRU is 0; at ref 0, of (4, 3, 2) the LRU is 4.

LRU = 9 faults.

Optimal:

Ref    7  0  1  2  0  3  0  4  2  3  0  3  2
F0     7  7  7  2  2  2  2  2  2  2  2  2  2
F1     -  0  0  0  0  0  0  4  4  4  0  0  0
F2     -  -  1  1  1  3  3  3  3  3  3  3  3
       F  F  F  F     F     F        F

Key steps: at ref 2, among (7, 0, 1), page 7 is never used again, so it goes; at ref 3, page 1 is never used again; at ref 4, among (2, 0, 3), page 0 is next used furthest away (after 2 and 3), so 0 goes; at the later ref 0, page 4 is never used again.

Optimal = 7 faults.

Problem 7: disk scheduling

Cylinders 0 to 199. The head is at 100, moving toward higher cylinders. Queue: 55, 58, 39, 18, 90, 160, 150, 38, 184. Find the total head movement for SSTF and LOOK.

SSTF:

1. From 100: 90 (10) is nearer than 150 (50). Go to 90.
2. From 90: 58 (32) versus 150 (60). Go to 58.
3. 55 (3), then 39 (16), then 38 (1), then 18 (20).
4. From 18 the nearest remaining is 150 (132), then 160 (10), then 184 (24).

100 -> 90 -> 58 -> 55 -> 39 -> 38 -> 18 -> 150 -> 160 -> 184
  10 + 32 +  3 + 16 +  1 + 20 + 132 +  10 +  24  = 248

SSTF = 248 cylinders.

LOOK (toward higher first):

1. Up from 100 serving 150, 160, 184: 184 - 100 = 84.
2. Reverse down to the lowest request, serving 90, 58, 55, 39, 38, 18: 184 - 18 = 166.

100 -> 150 -> 160 -> 184 -> 90 -> 58 -> 55 -> 39 -> 38 -> 18
total = 84 + 166 = 250

LOOK = 250 cylinders. For comparison, SCAN (going to 199 before reversing) gives 99 + 181 = 280, and C-LOOK gives 84 + 166 + 72 = 322 counting the jump from 184 to 18.

Problem 8: maximum file size with an inode

A file system has 1 KiB blocks and 4-byte block pointers. Each inode has 12 direct pointers, 1 single indirect and 1 double indirect pointer (no triple). What is the maximum file size?

Solution.

1. Pointers per block = 1024 / 4 = 256.
2. Direct: 12 blocks.
3. Single indirect: 256 blocks.
4. Double indirect: 256 x 256 = 65,536 blocks.
5. Total = 12 + 256 + 65,536 = 65,804 blocks.
6. Size = 65,804 x 1024 = 67,383,296 bytes, about 64.26 MiB.

Adding a triple indirect pointer would add 256^3 = 16,777,216 blocks (16 GiB), which is why large files depend almost entirely on the deepest level.

One-page revision checklist

Tick each item when you can explain it aloud without notes.

Processes and threads

• Process versus program versus thread; what threads share and what they do not
• Process states and transitions; contents of a PCB
• fork, exec, wait; zombies and orphans; count processes from n forks (2^n)
• Context switch cost (registers, TLB, caches); user versus kernel threads
• IPC: shared memory, pipes, message queues, sockets, signals

Scheduling

• Turnaround, waiting and response time formulas
• FCFS, SJF, SRTF, priority, Round Robin, MLFQ; convoy effect, starvation, aging
• Draw a Gantt chart and compute averages; state tie-break rules
• Priority inversion and priority inheritance

Synchronization and deadlock

• Race condition; critical section requirements (mutual exclusion, progress, bounded waiting)
• Mutex versus semaphore versus spinlock versus condition variable
• Producer-consumer, readers-writers, dining philosophers
• Four deadlock conditions; prevention, avoidance (Banker's), detection, recovery
• Run a Banker's safety check and give a safe sequence

Memory and virtual memory

• Logical versus physical addresses; base and limit; MMU
• Internal versus external fragmentation; first, best, worst, next fit
• Paging: split an address, page table size, multi-level tables, TLB and EAT
• Segmentation; segmentation with paging; inverted and hashed page tables
• Page fault steps; FIFO, LRU, Optimal, Clock traces; Belady's anomaly
• Thrashing, working set, page-fault frequency; copy-on-write; overcommit and OOM killer

Storage, files and I/O

• Inode contents; hard versus soft links; open-file tables and shared offsets
• Contiguous, linked (FAT), indexed allocation; inode max file size calculation
• Journaling and fsync; ext4 ordered mode; VFS; mounting
• Disk access time; FCFS, SSTF, SCAN, C-SCAN, LOOK, C-LOOK totals
• SSD FTL, TRIM, wear levelling; RAID 0, 1, 5, 6, 10 capacity and tolerance
• Polling, interrupts, DMA; buffering, caching, spooling; select versus epoll

Linux and security

• PID 1, /proc, /sys; SIGTERM versus SIGKILL; exit code 128 + N
• VSZ, RSS; free (watch available); top, vmstat, strace, lsof
• Namespaces plus cgroups equals a container; containers versus VMs
• Type 1 versus type 2 hypervisors; full versus para versus hardware-assisted virtualization
• User and kernel mode; DAC, MAC, RBAC; chmod octal and umask; setuid
• Buffer overflow; canaries, NX, ASLR, seccomp, sandboxing

When you are done, test yourself with the quizzes, or revisit topics through the operating systems playlist.

Key takeaways

• Answer in layers: a one-sentence definition, the mechanism, then an example or trade-off; expect a follow-up on each.
• The highest-frequency topics are processes versus threads, scheduling calculations, mutex versus semaphore, deadlock conditions, paging and TLB maths, page replacement and thrashing.
• For numerical problems, write down conventions first: TLB time, tie-breaks, head direction, return sweeps, and binary versus decimal units.
• n forks give 2^n processes; EAT = h x hit time + (1 - h) x miss time; inode max size = (direct + p + p^2 + p^3) x block size.
• LRU and Optimal never show Belady's anomaly; FIFO can.
• Practical Linux knowledge (signals, free, lsof, cgroups) separates strong backend candidates from those who know only theory.
• Use the checklist the night before, and go back to the linked lessons for anything you cannot explain aloud.

Next lesson

You have finished the Operating Systems track. Start again from the introduction to consolidate, or test yourself with the practice quizzes.