123 Operating Systems Interview Questions and Answers (2026)

Kernel mode is a privileged CPU state where code can execute any instruction and touch any hardware, while user mode is a restricted state where privileged operations are forbidden. This hardware-enforced separation is what stops a buggy or malicious program from corrupting the system.

• Kernel mode (supervisor/ring 0):

  • Full access: privileged instructions, all memory, direct I/O and device control.

  • The OS kernel and drivers run here.

• User mode (ring 3):

  • Restricted: no direct hardware access, only its own allotted memory.

  • Application code runs here.

• Crossing the boundary:

  • A user program requests privileged work via a system call (a trap/software interrupt) that switches to kernel mode, validates the request, then returns.

  • A mode bit in the CPU tracks the current state; privileged instructions in user mode raise a trap.

• Why it matters for security:

  • Enforces isolation: a crashing app can't corrupt the kernel or other processes.

  • Mediation: every sensitive action goes through the kernel, which can enforce permissions and resource limits.

An operating system's primary purpose is to act as an intermediary between hardware and programs: it manages the machine's resources and provides an abstraction layer that makes the hardware convenient and safe to use. In short, it is a resource manager and a control program.

• Two guiding goals:

  • Convenience/abstraction: hide hardware details behind clean interfaces (files, processes, sockets).

  • Efficiency/protection: share limited resources fairly and safely among many programs and users.

• Core functions:

  1. Process management: create, schedule, and synchronize processes/threads on the CPU.

  2. Memory management: allocate and track RAM, provide virtual memory and isolation.

  3. File and storage management: organize data as files/directories on persistent storage.

  4. I/O and device management: drive hardware via drivers and buffer/schedule I/O.

  5. Protection and security: enforce access control, user permissions, and dual-mode isolation.

• How programs use it: Applications request these services through system calls, the OS's controlled API to privileged operations.

Privileged instructions are machine instructions that can affect the whole system (I/O, memory mapping, halting the CPU), so the hardware restricts them to kernel mode to prevent a user program from corrupting or hijacking the machine.

• What they are: Instructions that manage hardware or global state: setting the interrupt vector, loading page-table registers, direct device I/O, masking interrupts, halting the CPU.

• The dual-mode mechanism:

  • The CPU has a mode bit: kernel mode (0) and user mode (1). Privileged instructions are only allowed when the bit says kernel mode.

  • Attempting one in user mode raises a trap (exception), transferring control to the OS instead of executing it.

• Why the restriction exists:

  • Protection: one buggy or malicious process must not disable interrupts, remap another process's memory, or crash the system.

  • Isolation and fairness: the OS stays in control of resources and can enforce scheduling and access rules.

• How user code still uses them: Via a system call: a controlled trap that switches to kernel mode, runs the privileged operation on the program's behalf, then returns to user mode.

OS types are categorized by how they schedule work and what workload they serve, ranging from throughput-oriented batch systems to deadline-driven real-time systems.

• Batch OS: Jobs with similar needs are grouped and run without user interaction; maximizes throughput but has no responsiveness (high turnaround time).

• Time-sharing (multitasking) OS: CPU time sliced among many users/processes via rapid context switching, giving each the illusion of a dedicated machine. Optimizes response time (e.g. Unix, Linux desktops).

• Real-time OS (RTOS):

  • Correctness depends on meeting deadlines, not just computing the right answer.

  • Hard real-time: missing a deadline is a failure (avionics, pacemakers). Soft real-time: deadlines are best-effort (video streaming).

• Distributed OS: Manages a collection of independent networked machines so they appear as one system; enables resource sharing and fault tolerance.

• Embedded OS: Runs on resource-constrained special-purpose devices (routers, appliances); small footprint, often overlaps with RTOS.

Multiprogramming keeps several jobs in memory at once so that whenever the running job blocks on I/O, the CPU immediately switches to another ready job, keeping the CPU busy instead of idle.

• The problem it solves: A single program alternates between CPU bursts and I/O waits; during I/O the CPU would otherwise sit idle, wasting cycles.

• How it works:

  • Multiple jobs reside in memory; the OS picks one to run and, when it requests I/O, switches the CPU to another ready job.

  • Requires job scheduling, memory management to hold many jobs, and CPU scheduling to choose among them.

• Why utilization improves: CPU and I/O devices operate in parallel: the CPU computes one job while another does I/O, overlapping work.

• Distinction from related terms: Multiprogramming aims for throughput; time-sharing adds preemption/time slices for interactive response. Multiprogramming does not by itself guarantee responsiveness.

The process state diagram models a process's lifecycle through states like New, Ready, Running, Waiting (Blocked), and Terminated. The key distinction: a process leaves Running to Waiting voluntarily when it needs something unavailable, but to Ready involuntarily when the scheduler preempts it.

• The core states: New: being created; Ready: runnable and waiting for the CPU; Running: executing on a core; Waiting/Blocked: parked pending an event; Terminated: finished.

• Running to Waiting (voluntary block):

  • Triggered by the process needing an unavailable resource: an I/O request, waiting on a lock/semaphore, or a sleep()/wait() call.

  • It cannot proceed, so it yields the CPU until the event completes.

• Running to Ready (involuntary preemption):

  • Triggered by the scheduler: a timer/quantum expiry or a higher-priority process arriving.

  • The process is still runnable, it just lost the CPU, so it goes back to the ready queue.

• Waiting to Ready: When the awaited event finishes (I/O completes, lock released), the process becomes runnable again but must wait its turn for the CPU.

• Key insight: There is no direct Waiting to Running transition: a woken process always passes through Ready first.

A process is an independent program in execution with its own private address space; a thread is a lightweight unit of execution that lives inside a process and shares that address space with sibling threads. Processes isolate; threads share.

• Memory sharing:

  • Processes have separate address spaces: they must use IPC (pipes, shared memory, sockets) to communicate.

  • Threads share the same heap, code, and global data, so communication is just shared memory (but needs synchronization).

• What's private: Each thread has its own stack, registers, and program counter; each process has its own everything.

• Overhead:

  • Creating a process is expensive (new address space, page tables); creating a thread is cheap.

  • Context switching between processes needs an address-space (page table / TLB) swap; between threads it doesn't.

• Isolation and failure: A crash in one process doesn't affect others; a crash (or memory corruption) in one thread can take down the whole process.

A Process Control Block (PCB) is the kernel data structure that represents a process: it holds everything the OS needs to suspend, resume, and manage that process. On a context switch, the OS saves the running process's state into its PCB and loads the next one's.

• Identification: Process ID (PID), parent PID, and owner/user info.

• CPU state (for resuming):

  • Program counter and register contents saved at the last switch.

  • Current process state (Ready, Running, Waiting, etc.).

• Scheduling info: Priority, scheduling queue pointers, and accounting stats (CPU time used).

• Memory management: Page tables, base/limit registers, or segment information for the address space.

• I/O and resources: Open file descriptors, allocated devices, and signal handlers.

• Why it matters: The PCB is what makes a process resumable: saving/restoring it is the essence of a context switch.

Threads of one process share everything that belongs to the process as a whole (its address space and resources), but each keeps a private execution context so it can run independently. The rule of thumb: shared = process-wide state, private = per-thread execution state.

• Shared across threads:

  • The code/text segment, heap, and global/static data.

  • Open file descriptors, signal handlers, and the process's address space (page tables).

  • Because memory is shared, access to shared data needs synchronization (locks, atomics).

• Private per thread:

  • Its own stack (local variables, call frames).

  • Its own registers and program counter.

  • Thread-local storage (TLS) and typically its own errno.

• Why this split: A private stack/registers lets each thread have an independent call path; shared memory lets them collaborate cheaply.

A program is passive code on disk, a process is that program in execution with its own resources, and a thread is the actual unit of execution running inside a process.

• Program: A passive entity: an executable file (instructions and static data) stored on disk. It does nothing until loaded and run.

• Process:

  • An active instance of a program with its own address space, open files, and OS-tracked state (via a PCB).

  • Processes are isolated from one another, so communication needs explicit IPC (pipes, shared memory, sockets).

• Thread:

  • A lightweight unit of execution within a process: it has its own stack, registers, and program counter but shares code, heap, and files with sibling threads.

  • Because they share memory, threads communicate cheaply but risk race conditions without synchronization.

• Relationship: one program can spawn many processes, and one process contains one or more threads.

Multithreading boosts responsiveness and throughput by letting one process do several things at once, but it adds synchronization complexity and its own overhead.

• Benefits:

  • Responsiveness: one thread can keep the UI alive while another blocks on I/O.

  • Resource sharing: threads share code, heap, and files by default, so no expensive IPC.

  • Economy: creating and switching threads is cheaper than processes (shared address space).

  • Scalability: threads can run truly in parallel across multiple CPU cores.

• Costs:

  • Synchronization: shared data invites race conditions, requiring locks, which risk deadlock and contention.

  • Debugging difficulty: bugs are timing-dependent and hard to reproduce.

  • Overhead: too many threads cause context-switch thrashing and memory pressure from stacks.

  • Fragility: one thread crashing (e.g. a segfault) can bring down the whole process.

A system call requests a service directly from the OS kernel and requires a switch to kernel mode, whereas a standard library function is ordinary user-mode code that may or may not eventually make a system call.

• System call:

  • Crosses the user/kernel boundary via a trap; needed for privileged operations (I/O, memory allocation, process creation).

  • Relatively expensive due to the mode switch and argument validation.

  • Examples: read(), write(), fork(), open().

• Library function:

  • Runs entirely in user space; often just computation (e.g. strlen(), sqrt()) with no kernel involvement.

  • Some library functions are thin wrappers that eventually invoke a system call.

• The overlap:

  • printf() is a library function that buffers in user space and then calls the write() system call to actually output.

  • So library calls can add convenience/buffering on top of the raw kernel interface.

Non-preemptive scheduling lets a process keep the CPU until it blocks or finishes; preemptive scheduling can forcibly take the CPU away (e.g. on a timer interrupt or a higher-priority arrival). Preemptive gives better responsiveness and fairness; non-preemptive is simpler and has less switching overhead.

• Non-preemptive:

  • CPU released only voluntarily (process terminates or blocks on I/O).

  • Simple, low context-switch overhead, no race conditions from mid-execution interruption, but one long job can starve others (poor response time).

• Preemptive:

  • OS reclaims the CPU via timer or priority changes; enables time-sharing.

  • Better response time and fairness, but more context switches and needs careful synchronization of shared data.

• When to prefer each:

  • Preemptive: interactive and real-time systems where responsiveness matters.

  • Non-preemptive: simple batch systems, or embedded contexts where predictability and low overhead are valued.

These are three distinct scheduling metrics: throughput measures how many processes finish per unit time (system view), turnaround time measures total time from submission to completion (job view), and response time measures how quickly a process first starts producing output (interactive user view).

• Throughput: Number of processes completed per unit time; a system-wide efficiency measure. Higher is better.

• Turnaround time:

  • Total elapsed time = completion time − arrival time. Includes waiting, execution, and I/O.

  • Equals waiting time + burst time.

• Response time: Time from submission until the first response, not full completion. Matters most for interactive systems.

• Key contrast: A scheduler can have good response time but poor turnaround (e.g. Round Robin) or vice versa; optimizing one often trades off another.

When a process doesn't finish within its time quantum, Round Robin preempts it via a timer interrupt, saves its state, and moves it to the tail of the ready queue so the next process can run; the preempted process resumes on a later turn.

• Preemption by timer: A timer interrupt fires at the end of the quantum, forcing a context switch.

• Requeue at the tail: The unfinished process goes to the back of the ready queue, keeping the scheduling fair and cyclic.

• Repeats until completion: A long job simply takes multiple quanta, interleaved with other processes.

• Quantum size tradeoff: Too large behaves like FCFS; too small causes excessive context-switch overhead. A good rule: the quantum should exceed most CPU bursts but stay short enough for responsiveness.

Priority scheduling assigns each process a priority number and always runs the ready process with the highest priority; the CPU is given to the most important task rather than simply the earliest or shortest one.

• How it works:

  • The scheduler picks the highest-priority ready process (convention varies: often a lower number means higher priority).

  • Can be preemptive (a higher-priority arrival immediately takes the CPU) or non-preemptive (it waits for the running process to yield).

• How priorities are assigned:

  • Static / external: set by the user, admin, or importance (e.g. Unix nice values) and don't change on their own.

  • Dynamic / internal: computed by the OS from metrics like memory needs, I/O-to-CPU ratio, or waiting time, and adjusted at runtime.

• Main problem: starvation: Low-priority processes may never run if high-priority ones keep arriving.

• Fix: aging: Gradually raise the priority of processes that have waited a long time, guaranteeing they eventually run.

A race condition occurs when two or more threads access shared data concurrently and the final result depends on the unpredictable order of their execution. It arises because operations that look atomic in source code are actually multiple machine steps that can interleave.

• Why it happens:

  • A statement like count++ is really read, modify, write: three steps that can be interrupted mid-way.

  • If two threads interleave those steps, one update can silently overwrite the other (a lost update).

• Conceptual example (two threads increment count = 5):

  1. Thread A reads count = 5.

  2. Thread B reads count = 5 (before A writes back).

  3. A computes 6 and writes 6; B computes 6 and writes 6.

  4. Result is 6, but two increments should have given 7: one update was lost.

• The fix: Serialize access to the shared data with synchronization (mutex, atomic operation) so the read-modify-write is indivisible.

The four Coffman conditions must all hold simultaneously for a deadlock to be possible; breaking any one prevents deadlock.

1. Mutual exclusion: At least one resource is held in a non-sharable mode: only one process can use it at a time.

2. Hold and wait: A process holds at least one resource while waiting to acquire others held by different processes.

3. No preemption: Resources cannot be forcibly taken; they are released only voluntarily by the holder.

4. Circular wait: A closed chain of processes exists where each waits for a resource held by the next.

The first three make deadlock possible; circular wait is what actually locks the cycle in place.

Virtual memory is an abstraction that gives each process its own large, contiguous address space that is decoupled from physical RAM. The OS and MMU map virtual pages to physical frames on demand, keeping only the actively used pages in RAM and storing the rest on disk (swap), so a program's address space can exceed installed physical memory.

• Demand paging is the key mechanism: Pages are loaded only when first accessed (a page fault brings them in), not all at once, so a program starts and runs with only part of it resident.

• RAM acts as a cache for disk: The full address space lives in the backing store; RAM holds the hot subset. Cold pages are evicted to swap when frames are needed.

• Locality makes it work: Programs touch a small working set at any moment, so even a huge program runs acceptably as long as its working set fits in RAM.

• The cost is thrashing: If the working set exceeds RAM, the system spends most time paging in/out rather than computing.

Virtual memory gives every process the illusion of a private, large, contiguous address space independent of physical RAM layout. Beyond enabling programs larger than RAM, its main value to the programmer is a simpler, safer, and isolated memory model.

• Simplified programming model: Each program sees a uniform address space starting at 0; you don't manage where in physical RAM your data lands or fit around other processes.

• Process isolation and protection: Separate address spaces mean one process can't read or corrupt another's memory; per-page permission bits (read/write/execute) enforce protection.

• Runs programs larger than RAM: Demand paging keeps only the working set resident, swapping the rest to disk.

• Efficient sharing: The same physical frames can be mapped into multiple processes (shared libraries, copy-on-write after fork()), saving memory.

• Relocation and flexibility: Physical placement can change without the program noticing; contiguous virtual regions map to scattered physical frames.

Directory structures organize how file names map to files; they evolved from flat listings to hierarchical trees and shared graphs to solve naming collisions, isolation, and sharing.

• Single-level directory:

  • One directory for all files on the system.

  • Simple, but every file name must be globally unique and it doesn't scale for multiple users.

• Two-level directory:

  • A separate directory per user under a master file directory.

  • Solves name collisions between users, but no sub-grouping and sharing is awkward.

• Tree-structured directory:

  • Arbitrary nesting of directories; each file has one unique absolute path.

  • Supports absolute and relative paths and a current working directory; the standard model.

  • Limitation: strictly one parent, so true sharing needs duplication.

• Acyclic-graph directory:

  • Allows shared subdirectories/files via links (e.g. hard links), so one file has multiple paths.

  • Must avoid cycles and handle deletion carefully: use reference counts so a file is freed only when the last link is removed (dangling-pointer problem with symbolic links).

File access methods define how a program reads and writes the bytes of a file: sequentially in order, directly to any position, or through an index that locates records.

• Sequential access:

  • Read/write in linear order; a pointer advances automatically with each operation.

  • Simplest and natural for tapes, logs, and streaming; jumping around is inefficient.

• Direct (relative) access:

  • File is a numbered set of fixed-length blocks/records; you can jump to any block by number.

  • Ideal for databases and random lookups; implemented with an explicit seek/offset.

• Indexed access:

  • An index maps a key to the block containing that record; you search the index, then do direct access.

  • Built on top of direct access; large files may need a multi-level index. Common in database and mainframe file systems.

A pipe is a unidirectional IPC channel where one process writes bytes and another reads them in FIFO order, acting like an in-kernel buffer. The distinction is naming: an unnamed pipe exists only between related processes, while a named pipe has a filesystem name so unrelated processes can use it.

• Unnamed (anonymous) pipe:

  • Created with pipe(); no name in the filesystem.

  • Only usable between related processes (parent/child) that inherit the file descriptors via fork().

  • Vanishes when all descriptors are closed; this is what the shell | operator uses.

• Named pipe (FIFO):

  • Created with mkfifo; appears as a special file with a path name.

  • Unrelated processes can open it by name to communicate; persists in the filesystem until deleted.

• Shared properties:

  • Byte-stream, FIFO order, fixed-size kernel buffer; a full buffer blocks the writer and an empty one blocks the reader.

  • Classic pipes are half-duplex (one direction); two are needed for bidirectional flow.

A pipe is a unidirectional in-kernel byte stream with two file descriptors: one read end and one write end. A parent creates it before forking so the child inherits the same descriptors, giving both processes a shared communication channel.

• Creation and inheritance:

  • pipe(fd) returns fd[0] (read) and fd[1] (write).

  • After fork(), the child inherits copies of both descriptors, so they point at the same kernel pipe buffer.

• Set the direction: Each side closes the end it doesn't use (e.g. parent closes read, child closes write) to fix a one-way flow and enable proper EOF detection.

• Kernel-buffered byte stream:

  • Data written flows through a fixed-size kernel buffer; there are no message boundaries, just bytes.

  • A full buffer blocks the writer; an empty buffer blocks the reader (flow control for free).

• EOF and errors:

  • When all write ends are closed, the reader gets EOF (read returns 0).

  • Writing when no read end is open raises SIGPIPE.

• Limitation: anonymous pipes only work between related processes; use a named pipe (mkfifo) for unrelated processes.

A device driver is the kernel module that knows how to talk to a specific piece of hardware. It translates the OS's generic, uniform I/O requests into the exact register operations, commands, and interrupt handling that particular device requires, hiding hardware detail from the rest of the kernel.

• Its core role:

  • Presents a standard interface (open/read/write/ioctl) upward while driving device-specific registers and DMA downward.

  • Handles the device's interrupts and manages its command/status protocol.

• Place in the I/O subsystem:

  • Sits below the device-independent I/O layer, which handles buffering, naming, and protection uniformly.

  • This layering lets the OS support new hardware by adding a driver, without changing applications or the rest of the kernel.

• Why it matters:

  • Achieves device independence: apps use the same calls for a disk, SSD, or network device.

  • Usually runs in kernel space with high privilege, so a buggy driver is a common source of crashes: some OSes run drivers in user space for isolation.

A Type 1 hypervisor runs directly on the hardware as its own thin OS, while a Type 2 hypervisor runs as an application on top of a conventional host OS. Type 1 is used for servers and cloud; Type 2 for desktops and development.

• Type 1 (bare metal):

  • Installed directly on hardware; the hypervisor itself schedules VMs onto CPU/memory.

  • Lower overhead and stronger isolation (no host OS in the path).

  • Examples: VMware ESXi, Xen, Microsoft Hyper-V.

• Type 2 (hosted):

  • Runs as a normal process on a host OS; guest calls pass through the host.

  • Easier to install and use, but more overhead and a larger attack surface (host OS).

  • Examples: VirtualBox, VMware Workstation.

• Note: KVM blurs the line, turning the Linux kernel itself into a Type 1 hypervisor.

Bootstrapping is the multi-stage process of bringing a machine from power-on to a running OS, where firmware initializes hardware and hands off to a bootloader, which in turn loads and starts the OS kernel. It is called "bootstrapping" because each small stage pulls up a larger one.

• Firmware: BIOS/UEFI:

  • Runs from ROM at power-on; performs POST (power-on self-test) and initializes core hardware.

  • BIOS reads the MBR from disk; UEFI (modern) reads an EFI application from the EFI System Partition and supports Secure Boot.

• Bootloader:

  • Small program (e.g. GRUB) loaded by the firmware.

  • Locates the kernel and initial ramdisk, loads them into memory, and passes boot parameters.

• Kernel handoff:

  • The bootloader transfers control to the kernel, which sets up memory management, drivers, and scheduling.

  • The kernel then starts the first user-space process (init/systemd), which brings up the rest of the system.

Both use multiple CPUs, but SMP treats all processors as equal peers each running the OS, while asymmetric multiprocessing (AMP) designates a master processor that controls subordinate ones assigned specific tasks.

• Symmetric (SMP):

  • Every CPU runs a copy of the same OS and can execute any process; they share memory and a common ready queue.

  • Pro: good load balancing and scalability. Con: needs careful synchronization (locks) to protect shared kernel data. This is the norm today.

• Asymmetric (AMP):

  • One master processor schedules work and handles all system activity; slave processors run assigned tasks or I/O.

  • Pro: simpler (less contention, no shared-state locking on the OS). Con: the master is a bottleneck and single point of failure.

• Core distinction: SMP = peers sharing control; AMP = hierarchy with a controlling master. SMP scales better; AMP is simpler and used in specialized/heterogeneous setups.

Protection is an internal mechanism controlling how processes and users access resources within the system, while security is the broader concern of defending the whole system against external and internal threats, including malicious actors.

• Protection (internal):

  • Controls access of processes/users to system resources: file permissions, memory isolation, CPU mode bits.

  • Answers: is this authorized process allowed to do this operation? Enforced by mechanisms like access-control lists and privilege levels.

• Security (external + policy):

  • Defends against threats: authentication, encryption, defending against viruses, intrusion, denial of service.

  • Assumes adversaries and covers the environment around the OS (users, network), not just internal rule enforcement.

• Relationship: Protection mechanisms are tools; security is the goal that uses them. Good protection is necessary but not sufficient for security (a valid user can still be malicious, or credentials can be stolen).

A zombie is a process that has finished executing but still has an entry in the process table because its parent has not yet read its exit status; an orphan is a still-running process whose parent has terminated first. Reaping via wait() prevents zombies from leaking the process table.

• Zombie (defunct) process:

  • Child has exited but the kernel keeps its PID and exit status until the parent collects it. It holds no memory/CPU, just a table entry.

  • Cleared when the parent calls wait()/waitpid(). Many uncollected zombies exhaust the finite process table.

• Orphan process: Parent died while the child is still running. The child is re-parented to init/systemd (PID 1), which will wait() on it, so it never becomes a lasting zombie.

• Why the parent must wait():

  • To reap the child: retrieve its exit status and let the kernel free the PID and remaining bookkeeping.

  • Without it, entries accumulate and can prevent creating new processes. A common fix is handling SIGCHLD to reap children.

Copy-on-write lets a fork()ed child share the parent's physical pages instead of copying them immediately; pages are only duplicated when one process actually writes to them, so forking is fast and memory-efficient.

• What fork() would do naively: Duplicate the parent's entire address space for the child: expensive in time and memory, and wasteful if the child soon calls exec().

• How COW works:

  • After fork(), parent and child map the same physical pages, all marked read-only in both page tables.

  • Reads are shared freely. On a write, the CPU raises a page fault; the OS copies just that page, gives the writer a private writable copy, and lets it proceed.

• Why it is efficient:

  • Copying is deferred and per-page (lazy): only modified pages are duplicated, so read-mostly or short-lived children cost almost nothing.

  • Pairs perfectly with the common fork()-then-exec() pattern, where copying the parent's memory would be entirely wasted.

User-level threads are managed entirely by a library in user space and are invisible to the kernel, while kernel-level threads are created and scheduled by the OS itself. The tradeoff is speed and portability versus true parallelism and blocking-call resilience.

• User-level threads:

  • Managed by a runtime/library; the kernel sees only one process (one kernel thread).

  • Pro: creation, switching, and scheduling are very fast (no kernel trap) and portable across OSes.

  • Con: one blocking system call blocks all threads (the whole process), and they can't run on multiple cores simultaneously.

• Kernel-level threads:

  • The kernel knows about and schedules each thread individually.

  • Pro: true parallelism on multicore, and one thread blocking doesn't stall the others.

  • Con: every operation (create, switch) requires a kernel mode transition, so it's heavier.

• Mapping models: Many-to-one (user threads on one kernel thread), one-to-one (each user thread maps to a kernel thread, common in Linux/Windows), and many-to-many (hybrid).

• Practical note: Modern systems favor one-to-one; user-level scheduling survives in green-thread/coroutine runtimes (e.g. goroutines) layered over kernel threads.

The Unix model splits process creation into two calls: fork() clones the current process, and exec() replaces the clone's memory image with a new program. Together they let a shell spawn a child and then run a different executable in it.

• fork() creates a child:

  • The child is a near-duplicate of the parent (same code, data, open files).

  • It returns twice: the child's PID in the parent, and 0 in the child, so code can branch on the return value.

• Address space during fork():

  • The child gets a logically independent copy of the parent's entire address space.

  • Modern kernels use copy-on-write (COW): pages are shared read-only and only copied when either process writes, avoiding a full duplication.

• exec() replaces the image:

  • It loads a new program into the current process, discarding the old code, data, heap, and stack.

  • The PID stays the same; open file descriptors typically survive (enabling redirection/piping).

• Why split them: The gap between fork() and exec() lets the child adjust its environment (redirect I/O, set up pipes) before running the new program.

Thread switches are faster because threads of the same process share an address space, so the kernel can skip the most expensive part of a switch: swapping memory mappings and flushing the TLB. Only the CPU execution context needs to change.

• No address-space change:

  • Same-process threads use the same page tables, so there's no page-table pointer reload.

  • The TLB (which caches virtual-to-physical translations) doesn't need to be flushed, avoiding costly post-switch TLB misses.

• Less state to save/restore: A thread switch saves registers, PC, and stack pointer; a process switch also swaps memory context and more kernel bookkeeping.

• Warm caches: Shared address space means CPU caches often stay relevant, reducing cache misses after the switch.

• Caveat: Switching between threads in different processes is just as costly as a process switch, since the address space still changes.

Choose multithreading when tasks need to share large amounts of memory frequently and cheaply, and you can manage synchronization safely. Choose multiprocessing when you need fault isolation, security boundaries, or want to sidestep a global interpreter lock.

• Favor threads when:

  • Tasks share lots of state and communicate often: shared memory is far cheaper than IPC.

  • You want low creation/switch overhead and a small memory footprint.

  • Workload is I/O-bound or the language allows true parallel threads (e.g. C++, Java, Go).

• Favor processes when:

  • Fault isolation matters: one crash shouldn't kill the whole app (e.g. browser tabs per process).

  • You need security/privilege separation between components.

  • A runtime lock limits thread parallelism (e.g. CPython's GIL makes CPU-bound work scale better with processes).

• The core tradeoff: Threads give cheap sharing at the cost of shared-fate and complex synchronization; processes give robustness at the cost of heavier communication.

A Thread Control Block (TCB) is the kernel data structure that stores the per-thread execution state, while a Process Control Block (PCB) stores the per-process resources shared by all its threads.

• What a TCB holds:

  • Thread ID, program counter, register set, stack pointer, thread state (ready/running/blocked), and scheduling info.

  • Essentially everything needed to pause and resume that one thread.

• What a PCB holds:

  • Process ID, address space / memory maps, open file table, accounting info, and a list of its threads.

  • These are resources shared across all threads of the process.

• Key difference:

  • A PCB is per-process and heavier; a TCB is per-thread and lighter. Multiple TCBs point back to one PCB.

  • This is why thread context switches are cheaper: only the TCB (registers, stack) changes, not the address space in the PCB.

These models describe how user-level threads map to kernel-level threads, trading off concurrency, parallelism, and complexity.

• Many-to-one:

  • Many user threads mapped to a single kernel thread, managed by a user-space library.

  • Fast to manage but no true parallelism, and one blocking system call blocks all threads.

• One-to-one:

  • Each user thread maps to its own kernel thread (Linux, Windows).

  • Gives real parallelism and independent blocking, but each thread costs a kernel resource, limiting how many you can create.

• Many-to-many:

  • Many user threads multiplexed onto a smaller or equal number of kernel threads.

  • Combines the strengths: high concurrency without exhausting kernel resources, but the scheduling coordination is complex to implement.

Both transfer control to the kernel, but an interrupt is asynchronous and hardware-generated, while a trap (exception) is synchronous and caused by the currently executing instruction.

• Interrupt:

  • Asynchronous: raised by external hardware independent of the running instruction.

  • Example: a network card signaling that a packet arrived, or a timer firing to trigger scheduling.

• Trap / Exception:

  • Synchronous: caused directly by an instruction, so it recurs if you re-run that instruction.

  • Example: division by zero, a page fault, or an intentional trap from a system call.

• Key distinction:

  • Interrupts are about outside events (timing unpredictable); traps are about the program's own execution (deterministic given the same state).

  • Some traps are deliberate (system calls), while faults and aborts are involuntary error conditions.

The Interrupt Vector Table (IVT) is a lookup table that maps each interrupt or exception number to the address of its handler routine, letting the CPU jump straight to the correct code when a signal arrives.

• Structure:

  • An array indexed by interrupt number (vector), where each entry holds the address of an Interrupt Service Routine (ISR).

  • It lives at a known memory location so the hardware can find it.

• How it is used:

  • When a device raises interrupt number N, the CPU uses N to index the table and fetch the handler's address.

  • It saves the current context, switches to kernel mode, and jumps to that handler.

• Why it matters:

  • It provides fast, direct dispatch instead of scanning for the right handler.

  • It unifies handling of hardware interrupts, exceptions, and software traps (like system calls) under one indexed mechanism.

These are three techniques for how the CPU transfers data to/from I/O devices, differing in how much the CPU is involved and how it learns a device is ready.

• Polling (programmed I/O):

  • The CPU repeatedly checks a device status register in a loop until the device is ready.

  • Simple, but wastes CPU cycles busy-waiting; fine only when devices respond fast.

• Interrupt-driven I/O:

  • The CPU issues the request and moves on; the device raises an interrupt when done, triggering an interrupt handler.

  • No busy-waiting, but the CPU still copies each word/byte, so per-byte interrupt overhead is high for large transfers.

• Direct Memory Access (DMA):

  • A dedicated DMA controller transfers a whole block directly between device and memory without the CPU touching each byte.

  • The CPU only sets up the transfer and gets one interrupt at completion, freeing it for other work; ideal for large/high-speed transfers (disk, network).

• Progression: polling burns CPU on waiting, interrupts remove the waiting, DMA removes the data-copying too.

A context switch is the act of saving the state of the currently running process/thread and restoring the state of another so the CPU can switch execution between them. It is pure overhead because during the switch no useful user work is done.

• Steps the OS performs:

  1. A trigger occurs: timer interrupt, I/O request, higher-priority process becomes ready, or the process blocks.

  2. Save the outgoing process's CPU state (program counter, registers, stack pointer) into its PCB (Process Control Block).

  3. The scheduler picks the next process to run.

  4. Restore that process's saved state from its PCB and switch the memory context (update page tables / MMU).

  5. Resume execution at the restored program counter.

• Why it's overhead:

  • The CPU spends cycles saving/loading state instead of doing work; this is wasted from the user's perspective.

  • Indirect cost is often larger: cache and TLB entries get invalidated, so the new process suffers cache misses until it warms up.

• Implication: too-frequent switching (e.g. tiny time quantum) degrades throughput.

Starvation is when a low-priority process is indefinitely denied the CPU because higher-priority processes keep arriving and are always chosen first. Aging solves it by gradually raising the priority of processes that have waited a long time, guaranteeing they eventually run.

• The starvation problem:

  • In strict priority scheduling the ready queue always dispatches the highest-priority process.

  • A steady stream of high-priority work means a low-priority process may wait forever (indefinite postponement).

• Aging as the fix:

  • Periodically increase the effective priority of a process based on how long it has been waiting.

  • Eventually its priority rises enough to be scheduled, so waiting time is bounded and no process starves forever.

• Example: bump priority by one level every 10 seconds of waiting; a priority-15 job reaches priority-0 after enough time.

The convoy effect happens in FCFS (First-Come-First-Served) when one long CPU-bound process runs first and forces all the short processes behind it to wait, tanking average waiting time. Preemptive time-slicing like Round Robin mitigates it by not letting any one process monopolize the CPU.

• Why it occurs in FCFS:

  • FCFS is non-preemptive: whoever arrives first runs to completion.

  • A big job at the head makes many short jobs queue behind it, like cars stuck behind one slow truck, raising average waiting and turnaround time.

  • It also hurts device utilization: I/O-bound jobs wait, leaving devices idle while the CPU hog runs.

• How Round Robin helps:

  • Each process gets only a fixed time quantum, then is preempted and sent to the back of the queue.

  • Short jobs no longer wait for a long job to fully finish; they interleave and complete quickly.

• Note: SJF (Shortest Job First) also avoids convoys by running short jobs first, but requires knowing burst lengths.

A Multi-level Feedback Queue (MLFQ) uses several ready queues of different priority, each with its own time quantum, and moves processes between queues based on their observed behavior, so I/O-bound (interactive) jobs stay responsive while CPU-bound jobs still make progress without hurting others.

• Structure:

  • Multiple queues ordered by priority; higher-priority queues have smaller time quanta, lower ones larger quanta.

  • The scheduler always serves the highest non-empty queue first.

• Feedback (the key idea):

  • A process that uses up its full quantum is treated as CPU-bound and demoted to a lower-priority queue.

  • A process that yields early (blocks for I/O) is treated as interactive and stays in or returns to a high-priority queue.

• Why it balances both:

  • I/O-bound jobs get quick, frequent CPU bursts (good response time) since they never exhaust their quantum.

  • CPU-bound jobs run in lower queues with long quanta, getting fewer switches but still finishing.

  • Aging (periodically boosting long-waiting jobs back up) prevents starvation of demoted CPU-bound processes.

A CPU scheduler aims to keep the CPU busy while delivering good performance across several metrics, but these goals conflict: optimizing one (like throughput) often worsens another (like response time), so schedulers make deliberate tradeoffs.

• Primary goals:

  • Maximize CPU utilization: keep the CPU doing useful work.

  • Maximize throughput: number of processes completed per unit time.

  • Minimize turnaround time: total time from submission to completion.

  • Minimize waiting time and response time (time until first response).

  • Ensure fairness: no starvation.

• Key tradeoffs:

  • Throughput vs. response time: frequent preemption (small quantum) improves response time but adds context-switch overhead, lowering throughput.

  • Turnaround vs. response: running short jobs first (SJF) minimizes average turnaround, but interactive systems may prefer fast first response even at the cost of turnaround.

  • Fairness vs. efficiency: strict priority maximizes important-job throughput but can starve others.

• Bottom line: the right balance depends on workload (batch favors throughput/turnaround; interactive favors response time).

Round Robin gives each ready process a fixed time slice (quantum) in circular order, preempting and re-queuing any process that doesn't finish in its slice. The quantum size is the crucial tuning knob: small quanta improve response time but hurt throughput via overhead, while large quanta do the reverse.

• How it works:

  • Ready processes sit in a FIFO circular queue.

  • The head runs for up to one quantum; if it finishes or blocks, it leaves, otherwise a timer preempts it and it goes to the tail.

  • It is preemptive and inherently fair: everyone gets a turn.

• Effect of quantum size:

  • Small quantum: excellent response time (each job runs sooner), but many context switches waste CPU, reducing throughput.

  • Large quantum: fewer switches so higher throughput, but response time degrades; as quantum grows past the longest burst, RR degenerates into FCFS.

• Rule of thumb: pick a quantum large enough that most CPU bursts complete within it, yet small enough to stay responsive (often ~80% of bursts finishing in one quantum).

The three schedulers operate at different frequencies and control different transitions: the long-term scheduler decides which jobs enter the system, the short-term scheduler decides which ready process runs next on the CPU, and the medium-term scheduler swaps processes in and out of memory to control the degree of multiprogramming.

• Long-term scheduler (job scheduler):

  • Selects jobs from the job pool and admits them to the ready queue (new to ready).

  • Runs infrequently; controls the degree of multiprogramming and the CPU-bound vs I/O-bound job mix. Often absent in modern time-sharing systems.

• Short-term scheduler (CPU scheduler):

  • Picks one process from the ready queue to run next (ready to running).

  • Runs very frequently (milliseconds), so it must be fast.

• Medium-term scheduler:

  • Swaps processes out of memory to disk and back in to reduce memory pressure and adjust multiprogramming.

  • Runs at moderate frequency; effectively performs suspend and resume.

Round Robin is a preemptive, fairness-oriented algorithm that gives each process a fixed time quantum in turn, while Shortest Job First picks the process with the smallest burst to minimize average waiting time. Round Robin is preferred in interactive, time-sharing systems where responsiveness and fairness matter more than minimizing average wait.

• Shortest Job First:

  • Provably optimal for minimizing average waiting time.

  • Requires knowing/estimating burst length, and can starve long jobs.

• Round Robin:

  • Fair: every process gets the CPU regularly, so no starvation.

  • Good response time but usually higher average turnaround than SJF, plus context-switch overhead.

• When to prefer Round Robin:

  • Interactive/time-sharing systems where each user needs prompt feedback.

  • When burst times are unknown (SJF can't be applied reliably) or when guaranteeing fairness and avoiding starvation is the priority.

Swapping is temporarily moving a process out of main memory to a backing store (disk) and later bringing it back to continue execution; the medium-term scheduler uses it to free memory, reduce contention, and adjust the degree of multiprogramming.

• Swap out: A process (often blocked or low-priority) is written to disk, freeing its RAM. It enters a suspended state.

• Swap in: The process is later restored to memory and resumes where it left off.

• Why the medium-term scheduler does this:

  • To relieve memory pressure and reduce the multiprogramming degree when memory is overcommitted (e.g. thrashing).

  • To improve the process mix by parking idle or I/O-waiting processes.

• Cost: Swapping is expensive (disk I/O), so it's used judiciously; context/state must be preserved so execution continues correctly.

The dispatcher is the component that actually hands the CPU to the process chosen by the short-term scheduler; dispatch latency is the time it takes to stop one process and start another running.

• Role of the dispatcher:

  • Performs the context switch: saves the old process's state and loads the new one's.

  • Switches to user mode.

  • Jumps to the proper location in the newly selected program to resume it.

• Scheduler vs dispatcher: The scheduler decides which process runs; the dispatcher carries out that decision.

• Dispatch latency:

  • The delay between stopping one process and resuming the next; it is pure overhead, so it should be minimal.

  • Invoked on every context switch, so it directly affects CPU efficiency.

Both schedule by shortest burst, but SJF is non-preemptive (once a process starts it runs to completion) while SRTF is the preemptive version: a newly arrived process with a shorter remaining time preempts the running one.

• SJF (non-preemptive):

  • At scheduling time, picks the process with the smallest total CPU burst and lets it run to completion.

  • A short job arriving mid-execution must wait for the current one to finish.

• SRTF (preemptive SJF):

  • Compares remaining time; if a new arrival has less remaining time than the running process, it preempts.

  • Gives lower average waiting time than SJF, but more context switches and greater risk of starving long jobs.

• Common ground: Both need burst-length estimates and both can starve long processes.

Multilevel Queue scheduling partitions the ready queue into several separate queues, each with its own scheduling policy, and processes are permanently assigned to a queue; Multilevel Feedback Queue is the more flexible variant that lets processes move between queues based on their observed behavior.

• Multilevel Queue (MLQ):

  • Multiple queues by process type (e.g. system, interactive, batch), each with its own algorithm (e.g. Round Robin for interactive, FCFS for batch).

  • Fixed assignment: a process stays in its queue for its lifetime.

  • Scheduling between queues is usually by fixed priority (which can starve lower queues) or time-slicing among queues.

• Multilevel Feedback Queue (MLFQ):

  • Processes move between queues based on behavior: a CPU-heavy process that uses its full quantum is demoted; one that yields early or waits long is promoted (aging prevents starvation).

  • Adapts to a process without prior knowledge, effectively approximating SJF by favoring short/interactive jobs.

• Key difference: MLQ is rigid (no movement); MLFQ is adaptive and dynamic, making it more general and configurable.

A mutex enforces mutual exclusion (ownership of a single resource), while a semaphore is a signaling counter that tracks how many units of a resource are available. Use a counting semaphore when you have multiple identical resources to hand out, and a binary one (or mutex) when there's exactly one.

• Mutex (mutual exclusion lock):

  • Has the notion of ownership: the thread that locks it must be the one to unlock it.

  • Used to protect a critical section so only one thread is inside at a time.

• Semaphore (signaling counter):

  • No ownership: any thread can call wait()/signal() (also called P/V or acquire/release).

  • Good for signaling between threads (e.g. producer signals consumer), not just locking.

• Binary semaphore vs mutex: A binary semaphore has values 0/1 and looks like a mutex, but lacks ownership, so it's really a signal.

• When to use a counting semaphore:

  • When N interchangeable instances exist (e.g. a pool of 5 DB connections): initialize count to 5 so up to 5 threads proceed and the 6th blocks.

  • Also to count available/empty slots in a bounded buffer.

The critical section problem is designing a protocol so that when multiple processes share data, no two are ever executing in their critical section (the code touching the shared data) at the same time. A valid solution must satisfy three requirements: mutual exclusion, progress, and bounded waiting.

• The structure: Each process has an entry section (request access), the critical section, an exit section (release), and a remainder section.

• 1. Mutual exclusion: If one process is in its critical section, no other process may enter its own critical section.

• 2. Progress: If no one is in the critical section and some processes want in, only those not in their remainder section decide who enters, and the choice can't be postponed indefinitely (no deadlock).

• 3. Bounded waiting: There's a limit on how many times other processes can enter before a waiting process gets its turn (no starvation).

A spinlock makes a waiting thread busy-wait in a loop, burning CPU until the lock is free; a blocking lock puts the waiting thread to sleep and lets the OS schedule other work. Prefer a spinlock for very short critical sections on multicore systems, and a blocking lock when the wait may be long.

• Spinlock:

  • Keeps checking the lock in a loop, so no context-switch cost, but wastes CPU cycles while waiting.

  • Only sensible on multiprocessors: on a single core, spinning just blocks the very thread that holds the lock.

• Blocking (sleeping) lock:

  • The thread is descheduled and woken when the lock frees, so CPU is used for other work.

  • Costs two context switches (sleep + wake), which is wasteful if the wait is shorter than that overhead.

• Choosing:

  • Short, predictable critical section and multiple cores: spinlock (e.g. kernel data structures).

  • Long or unpredictable hold time, or you might sleep/do I/O inside: blocking lock.

  • Hybrids exist (adaptive mutex): spin briefly, then block if still held.

The producer-consumer problem has producers adding items to a fixed-size shared buffer and consumers removing them; the challenge is preventing producers from writing to a full buffer, consumers from reading an empty one, and both from corrupting it via simultaneous access. Three semaphores solve it: two counting semaphores to track slots and one mutex for exclusive access.

• The three synchronization tools:

  • empty: counting semaphore initialized to N (number of free slots).

  • full: counting semaphore initialized to 0 (number of filled slots).

  • mutex: binary semaphore protecting the buffer itself so only one thread mutates it at a time.

• Producer flow: wait(empty) (block if full), wait(mutex), add item, signal(mutex), signal(full).

• Consumer flow: wait(full) (block if empty), wait(mutex), remove item, signal(mutex), signal(empty).

• Ordering matters: Always acquire the counting semaphore before the mutex; reversing them can deadlock (holding the mutex while blocked on a full/empty buffer).

A semaphore is an integer counter guarded so that only one process modifies it at a time: wait() (P) decrements and may block, signal() (V) increments and may wake a waiter. They must be atomic so the count is never corrupted by interleaving.

• wait() (P/down): Decrements the counter; if the result is negative the caller is blocked and placed on the semaphore's wait queue instead of busy-waiting.

• signal() (V/up): Increments the counter; if processes are waiting, one is removed from the queue and made ready.

• Why atomicity is essential:

  • The test-and-modify of the counter is a read-modify-write; if two processes interleave it, both could pass a mutex that should admit only one (lost update).

  • Atomicity is enforced by disabling interrupts on a uniprocessor, or by a hardware primitive like Test-and-Set / Compare-and-Swap guarding the critical region on multiprocessors.

• Counting vs binary: A binary semaphore ranges over 0/1 (mutex); a counting semaphore tracks a pool of N identical resources.

A monitor is a high-level synchronization construct that bundles shared data with the procedures that operate on it and guarantees that only one thread is active inside it at a time. Condition variables let a thread wait for a logical condition inside the monitor, and unlike semaphores they have no stored value: their signal() is lost if no one is waiting.

• Monitor = data + procedures + mutual exclusion: The compiler/runtime enforces that at most one thread executes a monitor procedure, so the programmer doesn't manually lock.

• Condition variables:

  • wait(): releases the monitor lock and blocks the thread on that condition's queue.

  • signal(): wakes one waiting thread; if none is waiting it does nothing (no memory).

• Key difference from semaphores:

  • A semaphore's signal() is remembered by incrementing the count; a condition variable's signal is forgotten if no waiter exists.

  • Because signals can be spurious/lost, condition wait() is used inside a while loop that rechecks the predicate.

• Signal semantics:

  • Hoare (signal-and-wait): signaler yields the monitor immediately to the woken thread.

  • Mesa (signal-and-continue, used by Java/pthreads): signaler keeps running, so the woken thread must re-test the condition.

Peterson's solution is a software-only algorithm that gives two processes mutually exclusive access to a critical section using two shared variables: a flag[] array signaling intent to enter and a turn variable that breaks ties.

• The mechanism:

  • Each process sets its flag[i] = true to announce it wants in, then sets turn = j (politely giving the turn to the other).

  • It busy-waits while the other's flag is set AND it is the other's turn; otherwise it enters.

• Guarantees the three requirements: Mutual exclusion, progress (no process outside its CS blocks another), and bounded waiting (at most one bypass).

• Assumptions it relies on:

  • Exactly two processes (classic form).

  • Atomic loads and stores to the shared variables.

  • Sequential consistency: no instruction reordering by compiler or CPU, which modern out-of-order hardware violates without memory barriers.

Atomic hardware instructions like Test-and-Set and Compare-and-Swap perform a read-modify-write on a memory word in a single, uninterruptible step, giving software the atomic building block needed to implement locks and lock-free structures on multiprocessors.

• Test-and-Set (TAS): Atomically sets a word to 1 and returns its old value; a spinlock loops until it sees the old value was 0.

• Compare-and-Swap (CAS):

  • Atomically writes a new value only if the current value equals an expected value, returning success/failure.

  • Enables optimistic, lock-free algorithms: read a value, compute, and only commit if nothing changed underneath.

• Why they matter:

  • Disabling interrupts doesn't scale to multiple cores; these instructions serialize access at the cache-coherence level instead.

  • They are the foundation on which semaphores, mutexes, and higher-level primitives are built.

• Caveats:

  • Simple spinlocks waste CPU busy-waiting and can be unfair.

  • CAS has the ABA problem: a value changes A -> B -> A and CAS wrongly succeeds; fixed with version tags.

The Dining Philosophers problem models five philosophers around a table who alternate thinking and eating, where each needs two shared forks (one on each side). It illustrates deadlock and starvation when concurrent processes compete for shared resources: if all grab their left fork at once, everyone waits forever for the right.

• Why the naive solution deadlocks: Each picks up the left fork then blocks on the right; a circular wait forms and no one eats.

• Deadlock-free solutions:

  • Resource ordering: number the forks and always pick up the lower-numbered one first, breaking circular wait (one philosopher grabs right-then-left).

  • Limit concurrency: allow at most N-1 philosophers at the table via a counting semaphore, so at least one can always get both forks.

  • Atomic pickup: only pick up a fork if both are available, guarded by a mutex or monitor.

  • Asymmetry: odd philosophers grab left first, even grab right first.

• Note on fairness: Avoiding deadlock isn't enough; a scheduling policy is still needed to prevent an individual philosopher from starving.

All three are liveness failures where processes fail to make useful progress, but they differ in mechanism: in deadlock processes are blocked forever waiting on each other, in livelock they keep changing state but accomplish nothing, and in starvation a process is perpetually denied resources it needs while others proceed.

• Deadlock:

  • A set of processes are permanently blocked, each holding a resource and waiting for another in the set (circular wait).

  • No CPU activity from them; they never move again without intervention.

• Livelock:

  • Processes are active and responding to each other but keep repeating the same state changes without progressing (two people stepping aside in a corridor forever).

  • Often caused by overly polite retry/backoff logic; fixed with randomized backoff.

• Starvation:

  • A specific process is indefinitely postponed because the scheduling/allocation policy always favors others (e.g. priority scheduling starving low-priority tasks).

  • The system as a whole makes progress; only the victim doesn't. Mitigated by aging.

• Key contrast: Deadlock = stuck and idle; livelock = busy but stuck; starvation = system progresses but one process is left behind.

A Resource Allocation Graph (RAG) is a directed graph modeling which processes hold or want which resources; a cycle in it signals a possible or actual deadlock depending on resource multiplicity.

• Nodes and edges:

  • Processes are circles, resource types are boxes (with a dot per instance).

  • Request edge: process to resource (P wants R); assignment edge: resource to process (R granted to P).

• Detecting deadlock:

  • Single instance per resource type: a cycle is a necessary and sufficient condition for deadlock.

  • Multiple instances: a cycle is necessary but not sufficient; another instance may free up and break it, so you must run a full detection algorithm.

• Intuition: A cycle means each process in it waits for a resource held by the next, forming a circular wait.

• Use: cheap visual/graph-based deadlock detection, and the basis for algorithmic detection in resource-instance systems.

The Ostrich approach is deliberately ignoring deadlocks ("bury your head in the sand"): the OS provides no prevention, avoidance, or detection, assuming they're rare enough that occasional recovery by rebooting or killing a process is cheaper than the overhead of handling them.

• Why general-purpose OSs use it:

  • Prevention/avoidance impose real costs: reduced concurrency, conservative resource grants, and up-front Max declarations that most programs can't give.

  • Deadlocks in practice are infrequent on systems like Linux and Windows, so paying constant overhead to prevent a rare event is a poor trade.

  • Recovery is easy for users: kill the hung process or reboot.

• When it's inappropriate: Safety-critical or long-running systems (avionics, databases, real-time control) where an undetected deadlock is unacceptable, so they use detection or avoidance instead.

The TLB is a small, fast associative cache inside the MMU that stores recent virtual-to-physical page translations, so the CPU can skip the slow multi-level page-table walk on a hit.

• Why it helps:

  • Without it, every memory access needs extra memory reads to walk the page table (e.g. 4 accesses for a 4-level table).

  • A TLB hit returns the frame number in ~1 cycle, so effective access time stays close to a single memory access.

• How lookup works:

  • TLB hit: the frame is found directly and combined with the page offset.

  • TLB miss: the hardware (or OS) walks the page table, loads the mapping into the TLB, and retries.

• Why it works: locality: Programs reuse a small set of pages, giving high hit rates (often >95%) despite the TLB holding few entries.

• Context switches: TLB entries are per-address-space, so a switch may flush the TLB unless entries are tagged with an ASID (address-space identifier).

Thrashing is when a system spends more time servicing page faults (swapping pages in and out) than executing useful work, because processes collectively need more memory than is physically available. CPU utilization collapses even though the disk is busy.

• Primary cause:

  • The sum of active working sets exceeds physical memory, so pages a process still needs get evicted and immediately faulted back in.

  • Often triggered by over-multiprogramming: the scheduler adds processes to raise CPU use, which shrinks each one's frames and worsens faulting.

• Detection: High page-fault rate combined with high disk I/O and low CPU utilization is the classic signature.

• Prevention / control:

  • Working-set model: track each process's recently used pages and only run it if its working set fits in memory.

  • Page-fault frequency (PFF): give a process more frames if its fault rate is too high, reclaim frames if too low.

  • Reduce the degree of multiprogramming (suspend/swap out whole processes), or add physical RAM.

Both are wasted memory, but internal fragmentation is unused space inside an allocated block, while external fragmentation is free space scattered in small pieces between allocations. Paging suffers internal fragmentation; contiguous allocation suffers external fragmentation.

• Internal fragmentation:

  • A process gets a whole unit (page/frame) but doesn't use all of it: the leftover inside the unit is wasted.

  • Paging: memory is handed out in fixed-size frames, so the last page of a process is usually partly empty (avg ~half a page per process).

• External fragmentation:

  • Enough total free memory exists, but it's split into non-contiguous holes too small to satisfy a request.

  • Contiguous / variable-partition allocation: as processes load and exit, gaps of varying size appear between them.

• Fixes:

  • External: compaction (relocate to coalesce holes) or paging/segmentation to avoid needing contiguity.

  • Internal: smaller page sizes reduce waste but increase page-table size and overhead.

Paging divides memory into fixed-size units invisible to the programmer to eliminate external fragmentation; segmentation divides it into variable-size, logically meaningful units (code, stack, heap) matching the program's structure. Segmented paging combines both to get logical grouping plus efficient physical allocation.

• Paging: Fixed-size pages/frames; address = (page number, offset); no external fragmentation but internal fragmentation and no logical meaning.

• Segmentation: Variable-size segments; address = (segment number, offset); matches program structure and eases protection/sharing per segment, but suffers external fragmentation.

• Segmented paging (the hybrid):

  • Each segment is itself divided into pages, so a segment need not be physically contiguous.

  • Advantages: keeps segmentation's logical units, protection, and sharing while removing external fragmentation (pages fit any free frame).

  • Address translation goes segment table then page table; cost is two lookups, mitigated by the TLB.

A page fault is a hardware trap raised by the MMU when a program accesses a virtual page that is not currently present in physical memory (its present bit is clear). The OS's page-fault handler then decides whether the access is legal and, if so, brings the page in.

• Trap into the kernel: The MMU can't translate the address, so it raises a fault; the CPU switches to the OS handler with the faulting address saved.

• Validate the access: The OS checks the address against the process's VMA/region table. Illegal access (not mapped, or protection violation) triggers a segfault (SIGSEGV). A valid-but-not-resident page continues.

• Find a free frame: If none is free, run the page-replacement algorithm to evict a victim; if the victim is dirty, write it back to disk/swap first.

• Fetch the page: Schedule disk I/O to read the page (from swap or a file) into the chosen frame. The process blocks and the CPU can run others meanwhile.

• Update tables and resume: Update the page table entry (frame number, set present bit), flush stale TLB entries, then restart the faulting instruction, which now succeeds.

• Minor vs major fault: A minor (soft) fault needs no disk I/O (page already in memory, e.g. shared or on a free list); a major fault requires reading from disk and is far slower.

A logical (virtual) address is the address a program generates and sees; a physical address is the actual location in RAM. The MMU (Memory Management Unit) is the hardware that translates every virtual address to a physical one at runtime, using the page tables the OS sets up.

• Logical / virtual address: Generated by the CPU on behalf of a running process; part of that process's private virtual address space and meaningless outside it.

• Physical address: Addresses an actual byte in physical RAM; shared across the whole machine.

• Role of the MMU:

  • Translates each virtual address by splitting it into a page number and offset, looking up the frame in the page table, and combining frame + offset.

  • Enforces protection and presence: raises a page fault if the page is absent or the access violates permissions.

  • Uses the TLB, a small cache of recent translations, to avoid walking the page table on every access.

• Why the split matters: It decouples the program's view from physical layout, enabling isolation, relocation, and virtual memory.

Paging divides the virtual address space into fixed-size pages and physical memory into equal-size frames, then maps any page to any free frame via the page table. Because allocation is in uniform fixed-size units that need not be contiguous, paging eliminates external fragmentation entirely.

• Fixed-size units: Pages and frames are the same size (e.g. 4 KB), so any free frame can hold any page: there are no odd-sized holes to leave behind.

• Why external fragmentation disappears: External fragmentation arises when free memory is split into scattered variable-size chunks too small to satisfy a request. With uniform frames, any free frame is usable, so scattered free frames are never wasted.

• Non-contiguous mapping: A process's contiguous virtual pages map to physically scattered frames; the page table hides this from the program.

• The tradeoff: internal fragmentation: The last page of a region is usually partly unused (on average half a page per region), which is wasted space inside a frame.

All three decide which page to evict on a fault; they differ in what they use to pick a victim: FIFO uses age, LRU uses recency of use, and Optimal uses future knowledge to evict the page needed farthest ahead.

• FIFO (First-In First-Out):

  • Evicts the oldest-loaded page regardless of usage.

  • Simple (a queue), but can evict hot pages and suffers Belady's anomaly: more frames can cause more faults.

• LRU (Least Recently Used):

  • Evicts the page unused for the longest time, assuming recent past predicts near future.

  • Good hit rates and no Belady's anomaly (it's a stack algorithm), but exact tracking needs a timestamp or update on every access, which is costly, so it's usually approximated.

• Optimal (OPT / Belady's / MIN):

  • Evicts the page whose next use is furthest in the future, giving the theoretical minimum fault count.

  • Used as a benchmark to judge how close real algorithms get.

• Why Optimal is impossible in practice:

  • It requires knowing the entire future reference string, which the OS cannot predict at runtime.

  • It's only computable offline (after the fact) from a recorded trace, so it serves as a comparison baseline, not a deployable policy.

Address binding maps a program's symbolic references to physical memory, and it can happen at three stages: compile time, load time, or execution time; the later it happens, the more flexible relocation becomes.

• Compile-time binding:

  • The compiler generates absolute addresses because the load location is known in advance.

  • If the start address changes, the code must be recompiled (e.g. old MS-DOS .COM programs).

• Load-time binding:

  • The compiler produces relocatable code with offsets, and the loader fixes final addresses when the program is loaded.

  • Allows loading anywhere, but the process cannot move once loaded.

• Execution-time (run-time) binding:

  • Binding is deferred until each access; the CPU translates logical to physical addresses on the fly using hardware.

  • Requires MMU support (relocation register, paging), and enables swapping and dynamic relocation, so it's what modern OSes use.

Memory compaction shuffles allocated blocks together at one end of memory so the scattered free holes merge into one large contiguous block; it solves external fragmentation in contiguous allocation.

• The problem: external fragmentation:

  • After many allocations and frees, free memory exists but is split into small non-adjacent holes.

  • A large request can fail even though the total free space is sufficient.

• How compaction helps:

  • Relocate live processes to be adjacent, coalescing all free space into a single usable region.

  • Only possible with execution-time (dynamic) address binding, since process addresses change when moved.

• Costs and alternatives:

  • Expensive: copying memory stalls execution and is done at runtime.

  • Paging avoids the need for compaction entirely by removing the contiguity requirement.

A memory-mapped file maps a file's contents directly into a process's virtual address space so it can be accessed with ordinary memory loads and stores; the pager moves data between file and memory on demand instead of via explicit read/write calls.

• How it works:

  • A call like mmap() associates file pages with virtual pages; a page fault brings a page in, and dirty pages are written back later.

  • Accessing the file is just dereferencing a pointer, no per-operation syscall.

• Advantages over read/write I/O:

  • Fewer syscalls: after mapping, access is via memory, avoiding read()/write() overhead per operation.

  • Avoids extra copies: data can go straight into the page cache the process sees, instead of copying into a user buffer.

  • Lazy, demand-paged loading: only touched pages are read, good for large files with random access.

  • Easy sharing: multiple processes mapping the same file share physical frames, enabling shared memory and fast IPC.

• Caveats:

  • Write-back timing is controlled by the OS, so durability needs an explicit flush (msync()).

  • An I/O error surfaces as a fault (e.g. SIGBUS), which is harder to handle than a return code.

The Clock algorithm approximates LRU using a single reference bit per page and a circular list with a moving hand: instead of tracking exact recency, it just distinguishes recently-used from not, giving pages a second chance before eviction.

• The mechanism:

  • Frames form a circular buffer; a hand points at a candidate victim.

  • Hardware sets a page's reference bit to 1 on each access.

• On a page fault, sweep the hand:

  1. If the pointed page has reference bit = 0, evict it (it wasn't used recently).

  2. If reference bit = 1, clear it to 0 (grant a second chance) and advance the hand.

  3. Repeat until a 0 bit is found; if all were 1, the hand cycles around and now finds the cleared bits.

• Why it approximates LRU:

  • A set reference bit marks a page as recently used, so it survives, while unreferenced pages get evicted first, mimicking LRU's intent.

  • It's coarse: it only knows used-since-last-sweep vs not, not exact order, but needs just one bit and no update on every access, making it cheap.

  • Enhanced version adds the dirty bit to prefer evicting clean pages (no write-back), refining the choice.

An inode (index node) is the on-disk data structure that holds all metadata about a file plus pointers to its data blocks: it represents the file itself, independent of any name. Each file has exactly one inode, identified by an inode number.

• What it stores:

  • File type and permissions (mode), owner UID/GID.

  • Size, timestamps (atime, mtime, ctime).

  • Link count (number of hard links pointing to it).

  • Pointers to data blocks (direct, plus single/double/triple indirect blocks).

• What it does NOT store:

  • The file name: names live in directory entries that map a name to an inode number.

  • The actual file contents (those are in the data blocks it points to).

• Why this matters: Because names are separate, multiple names (hard links) can point to one inode, and a file is only truly deleted when its link count reaches zero.

A hard link is a second directory entry pointing to the same inode (same file), while a symbolic link is a separate small file whose contents are a path to a target. Deleting the original affects them very differently.

• Hard link:

  • Points directly to the inode; all hard links are equal peers, none is 'the original'.

  • Deleting one link just decrements the inode's link count; data survives until the count hits zero.

  • Limitations: cannot span file systems and (typically) cannot link directories.

• Symbolic (soft) link:

  • Its own inode storing a path string to the target; resolution happens at access time.

  • Deleting the target leaves a dangling link that fails when dereferenced (the symlink itself still exists).

  • Can cross file systems and point to directories.

• Deletion summary:

  • Hard link: removing the 'original' name loses nothing; the file remains reachable via other links.

  • Symlink: removing the target breaks the link, leaving it pointing at nothing.

A file descriptor is a small non-negative integer a process uses to refer to an open file; it indexes into the process's per-process file table, which points into a system-wide open-file table, which in turn references the file's inode. This three-level structure lets the OS track offsets and sharing correctly.

• Per-process descriptor table:

  • Each process has its own array; 0, 1, 2 are stdin, stdout, stderr.

  • An entry points to an open-file table entry.

• System-wide open-file table:

  • Each entry holds the current file offset, access mode, and a pointer to the in-memory inode.

  • Two independent open() calls create separate entries with independent offsets, even for the same file.

• Sharing behavior:

  • After fork() or dup(), descriptors share one open-file table entry, so they share the offset (a read by one advances it for the other).

  • The inode is reference-counted so the OS knows when it's safe to release resources on close().

Free-space management tracks which disk blocks are unused. A bit vector uses one bit per block in a compact map, while a linked list chains free blocks together; they trade off lookup speed against space overhead.

• Bit vector (bitmap):

  • One bit per block: 1 = free, 0 = allocated (or vice versa).

  • Easy to find contiguous runs of free blocks by scanning for consecutive bits; hardware often has instructions to find the first set bit.

  • Downside: the whole map must ideally sit in memory, costing space on very large disks.

• Linked list of free blocks:

  • Each free block stores a pointer to the next free block; only the head pointer is kept.

  • Wastes almost no extra space, but finding contiguous free space is hard and traversal requires many disk reads.

  • Optimization: grouping stores addresses of many free blocks in the first free block; counting stores runs as (start block, count).

• Trade-off summary: bitmap favors fast allocation and contiguity; linked list favors low overhead but slow searches.

The File Allocation Table (FAT) is a linked-allocation scheme where a table at the start of the volume, indexed by block number, stores the number of the next block in each file, forming a chain per file.

• Structure:

  • One table entry per disk block; the directory entry stores only the file's first block number.

  • Entry N holds the block number that follows block N, so following entries traces the whole file.

  • A special marker (EOF) ends the chain; another value marks a block as free.

• How lookup works:

  • Start at the first block from the directory, then repeatedly read the FAT entry to jump to the next block.

  • Keeping the FAT cached in memory makes even random access fast, since the chain is walked in RAM, not on disk.

• Pros and cons:

  • Simple and widely portable (FAT12/16/32, used on USB drives and SD cards).

  • Weaknesses: FAT corruption is catastrophic (usually mirrored for safety), and files can become fragmented.

Mounting attaches a filesystem stored on a device to a specific directory (the mount point) in the existing directory tree, making its files accessible as part of the unified namespace.

• What the OS does during mounting:

  • Reads the device's superblock/boot block to identify the filesystem type and verify its structure.

  • Loads filesystem metadata into kernel structures (an in-memory superblock) and records the mount in a mount table.

  • Associates the mount point directory with the filesystem's root so path lookups redirect into it.

• Semantics:

  • Anything previously in the mount point directory becomes hidden until unmount.

  • Unmounting flushes cached writes and detaches it; a busy filesystem (open files) can't be unmounted.

• Example: mounting a USB drive at /mnt/usb makes its files appear under that path via one VFS namespace.

Inter-Process Communication (IPC) lets separate processes exchange data and coordinate. The two foundational models are shared memory (processes read/write a common region) and message passing (processes exchange discrete messages through the kernel): shared memory is faster but harder to synchronize, message passing is slower but simpler and safer.

• Common IPC mechanisms: Shared memory, message queues, pipes/FIFOs, sockets, signals, and semaphores (for synchronization).

• Shared memory:

  • Kernel maps the same physical pages into both address spaces; after setup, data exchange needs no kernel involvement.

  • Fastest option (no copying through the kernel per access), best for large or high-frequency data.

  • Harder to implement: the programmer must synchronize access explicitly (semaphores, mutexes) to avoid races.

• Message passing:

  • Processes use send/receive primitives; the kernel copies data and can handle synchronization.

  • Slower due to kernel mediation and copying, but easier to reason about and works across machines (e.g. sockets).

  • Can be blocking (synchronous) or non-blocking (asynchronous).

• Trade-off: shared memory for raw speed within one machine; message passing for simplicity, isolation, and distribution.

A signal is an asynchronous software interrupt delivered to a process to notify it of an event (e.g. termination request, illegal instruction, timer expiry). It's a lightweight, limited form of IPC: it carries a number, not data, and interrupts the process to run a handler.

• What they are:

  • Small integer notifications like SIGINT, SIGTERM, SIGKILL, SIGSEGV, SIGCHLD.

  • Sent by the kernel (faults, timers) or by processes via kill().

• Handling options:

  • Default action (often terminate), ignore, or catch with a custom handler registered via signal() / sigaction().

  • SIGKILL and SIGSTOP cannot be caught or ignored.

• As an IPC mechanism:

  • Best for notification/control ("reload config", "stop now"), not for transferring data.

  • Delivery is asynchronous and standard signals are not queued: if the same signal arrives repeatedly while pending, it may collapse into one.

• Async-safety trap: A handler interrupts arbitrary code, so it may only call async-signal-safe functions and typically just sets a volatile sig_atomic_t flag.

A socket is a bidirectional communication endpoint that the kernel exposes as a file descriptor. It abstracts a communication channel so processes can exchange data whether they're on the same machine (Unix domain sockets) or across a network (TCP/UDP), all through the same read/write API.

• Endpoint abstraction:

  • socket() returns an fd; the kernel maintains send and receive buffers behind it.

  • Identified by a domain (AF_UNIX, AF_INET) and type (SOCK_STREAM, SOCK_DGRAM).

• Two families for IPC:

  • Unix domain sockets: same host, addressed by a filesystem path; the kernel copies data directly without the network stack, so they're fast.

  • Network sockets: TCP/IP, addressed by IP + port; work across machines but go through the protocol stack.

• Connection lifecycle (stream):

  1. Server: socket() then bind() then listen() then accept().

  2. Client: socket() then connect().

  3. Both then use read()/write() (or send()/recv()) on the fd.

• Why it matters:

  • Full-duplex and works between unrelated processes, unlike anonymous pipes.

  • Same API scales from local IPC to distributed systems: location transparency.

With polling the CPU repeatedly checks a device's status register to see if it's ready; with interrupt-driven I/O the device signals the CPU only when it needs attention, letting the CPU do other work in the meantime. Polling wins when the device is almost always ready and events are extremely frequent, so interrupt overhead would dominate.

• Polling (busy-waiting): CPU loops reading the status bit; simple and low-latency but wastes cycles while the device is slow.

• Interrupt-driven:

  • Device raises an interrupt; CPU stops, runs an interrupt service routine, then resumes other work.

  • Efficient for slow or bursty devices, but each interrupt costs a context switch and handler dispatch.

• When polling is more efficient:

  • Very high-rate devices (e.g. fast NICs at line rate, NVMe): interrupts arrive so often that per-interrupt overhead exceeds the cost of just spinning.

  • When latency must be minimal and the device responds almost immediately, so the CPU wouldn't have anything useful to do anyway.

  • Real systems mix both: e.g. Linux NAPI starts on interrupts then switches to polling under heavy load.

DMA (Direct Memory Access) is a hardware controller that transfers data directly between a device and main memory without the CPU copying each byte. The CPU sets up the transfer, then is free until the DMA controller raises a single interrupt on completion.

• The problem it solves: Programmed I/O makes the CPU move every word between device and memory, burning cycles proportional to data size.

• How it works:

  1. CPU programs the DMA controller with a memory address, count, and direction.

  2. The controller moves the block over the bus while the CPU runs other work.

  3. On completion, DMA raises one interrupt: the CPU handles the whole transfer with a single event.

• Why it's critical for high speed:

  • Frees the CPU for computation, drastically raising throughput for disks, NICs, and GPUs.

  • Reduces per-byte overhead and interrupts to one per block instead of one per word.

• Costs and caveats:

  • DMA and CPU contend for the memory bus (cycle stealing).

  • Requires cache-coherence care so the CPU doesn't read stale cached copies of DMA'd memory.

These describe how a process interacts with an I/O operation that isn't instantly ready. Blocking waits until it completes, non-blocking returns immediately with a status, and asynchronous starts the operation and gets notified later when it's done: blocking/non-blocking is about whether the call waits, while sync/async is about who does the work and how completion is signaled.

• Blocking I/O:

  • The calling thread sleeps until data is ready or the operation finishes.

  • Simple to reason about, but one thread handles one operation at a time.

• Non-blocking I/O:

  • The call returns immediately; if not ready it returns something like EWOULDBLOCK.

  • The caller must poll or use a readiness mechanism (select, epoll) to know when to retry.

• Asynchronous I/O:

  • The kernel performs the full operation in the background and notifies via callback, completion queue, or signal (e.g. io_uring, POSIX aio).

  • The caller never waits and doesn't re-issue: it's told when the result is ready.

• Key distinction: Non-blocking readiness models say "try now, not ready yet"; async completion models say "I'll do it and call you back."

Both decouple a fast producer from a slow device, but buffering smooths the speed mismatch within a single transfer by temporarily holding data in memory, while spooling queues whole independent jobs to storage so many can be submitted and serviced one at a time.

• Buffering:

  • Holds data in memory to bridge speed differences and allow overlap of I/O with computation.

  • Operates on a stream/block level within one transfer; data is consumed as it flows.

  • Example: streaming a video, where seconds of data are buffered ahead so playback stays smooth despite network jitter.

• Spooling:

  • Simultaneous Peripheral Operation On-Line: stores complete jobs on disk to be processed by a device later.

  • Manages a queue of whole jobs from possibly many users, serialized to one device.

  • Example: a print spooler, where multiple print jobs queue on disk and print one at a time while users continue working.

• Core difference: Buffering overlaps parts of a single I/O operation; spooling queues entire jobs and lets a device serve them sequentially.

Buffering and caching both use memory to smooth I/O, but for different reasons: buffering bridges speed and size mismatches between producer and consumer, while caching keeps copies of data to serve repeat requests fast.

• Buffering (holding data in transit):

  • Handles speed mismatch: a fast producer fills a buffer while a slow device drains it (and vice versa).

  • Handles size/transfer-unit mismatch: reassemble fragmented network packets or align to disk block sizes.

  • Enables copy semantics: the kernel copies user data into a buffer so later changes don't corrupt the write in flight.

• Caching (keeping copies for reuse):

  • Stores recently/frequently used data so repeat accesses skip the slow device, exploiting locality.

  • Example: the page cache serves reads from RAM instead of disk.

• Key distinction:

  • A buffer holds the only copy of in-transit data; a cache holds a redundant copy of data that also lives elsewhere.

  • A single memory region can act as both (buffered write also cached for later reads).

• Trade-off: caching risks stale/lost data on crash, so writes may need flushing or write-through policies for durability.

Disk scheduling reorders pending requests to minimize head movement (seek time). SCAN sweeps the head across the disk like an elevator; C-LOOK goes further by only traveling as far as the last request and jumping back, both beating FCFS which honors arrival order regardless of position.

• FCFS (baseline): Serves in arrival order, so the head can zig-zag wildly across the platter, causing large cumulative seek distances.

• SCAN (elevator):

  • Moves in one direction servicing all requests until it reaches the last cylinder, then reverses.

  • Reduces seek time by handling requests in physical order rather than temporal order.

• C-LOOK (circular LOOK):

  • Like LOOK but only travels up to the last request in a direction (not the disk edge), then jumps straight back to the lowest request without servicing on the return.

  • The jump-back gives more uniform wait times, avoiding the bias SCAN shows toward middle cylinders.

• Why they beat FCFS: By sorting requests along the head's path, total seek distance drops sharply and throughput rises, especially under heavy load.