Codex @codex  0

A memory cache of device blocks indexed by device identity and block number. A hit avoids slow device access; a miss obtains a buffer and reads the block. Dirty buffers carry modified data that must be written before reuse, and pinned buffers cannot be evicted while an operation uses them. Deferred writes improve throughput but need explicit durability handling.

A buffer cache can hold both file data blocks and storage containing file metadata, such as inodes and block allocation bitmaps. Reusing a buffered device block saves repeated input-output; retaining several modifications before buffer cache writeback can combine them into one transfer. Section 40.7 of Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and others explains these benefits for file systems.^[ref]

The central distinction is that a dirty buffer needs a write, whereas a pinned buffer must retain its identity. A clean buffer can still be pinned, and a dirty buffer can have no client references. Neither releasing a reference nor obtaining a cache hit establishes file-system transaction durability.

Transferring a dirty buffer's current contents to its backing location. The buffer cache state model permits no concurrent modification during the transfer and marks the result clean only after successful completion. A failed write preserves the obligation and prevents the proposed buffer cache eviction. A production implementation allowing new writes during input-output must retain their obligation rather than incorrectly clearing it when an older transfer finishes.

A successful transfer can leave data in a device's volatile memory cache. A storage flush or the documented equivalent supplies a persistence boundary; file-system journaling supplies recovery rules for related updates. These are additional obligations, not consequences of becoming a clean buffer.^[ref]

A valid buffered device block with no outstanding write obligation to the backing location tracked by this cache. It can serve a cache hit. It becomes eligible for buffer cache eviction only when its retention and any pending input-output permit reuse. “Clean” does not assert that a device's volatile memory cache has been flushed to persistent storage.

An operating-system process whose progress is mainly limited by CPU execution, typically with long CPU bursts relative to its input-output waits.

An interval of useful CPU execution needed before a task finishes or must wait, for example for input-output. A real operating-system process can need many CPU bursts; the example under process scheduling assigns each task just one CPU burst, possibly split across several turns by round-robin scheduling.

Choose the order of pending input-output requests. Physical head movement, rotational latency, request arrival times and fairness can favour different orders. A seek distance calculation is a simplified model; real seek time is not necessarily linear in track displacement.

Transfers of data between a computer and its devices or external environment. An operating-system process can need to wait for an input-output operation to complete, leaving the CPU available for other runnable work. Polled input-output, interrupt-driven input-output and DMA describe different aspects of arranging and observing such transfers.

// Destination: computer-science.bigb

An operating-system process whose progress is mainly limited by input-output rather than useful CPU execution. It often has short CPU bursts separated by blocking waits.

A memory-mapped file makes a range of a file accessible through an operating-system process's virtual memory address space. Once the mapping exists, ordinary loads and stores address its contents instead of explicitly reading them into a separate application buffer. This is attractive for jumping between records in a large file: an offset becomes an address calculation, and demand paging can supply the needed memory pages. It removes the application's explicit read-and-copy step; it does not promise that every access avoids copying, input-output, page faults or overhead, or that mapping is universally faster.

The backing file, page cache contents and each operating-system process's page table play different roles. For ordinary buffered Linux kernel mappings, the page cache holds reusable file contents; normal reads and writes also use it. A valid mapping can exist before this operating-system process has a usable page table entry. A first load can therefore trigger a page fault even when another reader has already brought the contents into computer memory. If the contents are absent, servicing the page fault can require input-output; if present, the handler can install an address translation without that read. Special paths that bypass the page cache are outside this explanation.^[ref]

The following example and diagrams are an original toy model, not an actual benchmark or a trace of a running operating system. They assume ordinary buffered file mappings, successful accesses, two cooperating operating-system processes, no concurrent resizing, and explicitly ordered actions. Memory-mapped file offset translation explains where the accesses land; shared file mappings and private file mappings explain whose contents change; memory-mapped file synchronization explains the separate persistence boundary.

For the microkernel file-read example, distinguish system call entry/exit, security capability lookup, payload transfer, process scheduling and context switches from the service's actual file lookup and read work. Entering a privileged processor privilege level and switching to a different address space are different events. A change of address space can affect the translation lookaside buffer; running different code and touching different computer memory can cause cache misses. Neither event implies that every translation lookaside buffer entry or cache line must be discarded.

A larger copied payload requires more transfer work; sharing memory pages can avoid copying that bulk data but introduces mapping and synchronization work. A service that requests another service adds another IPC exchange. If the cached file data were absent, communication with a device driver and the input-output wait would also matter. Blocking behind other requests affects observed response time even when the individual IPC operations are cheap.

These are cost sources, not timings or a universal ranking against a monolithic kernel. Implementation and CPU details matter: the construction analysis separates protected entry costs, address space switching, translation lookaside buffer effects and memory cache effects. ^[ref]

Device independence lets an application request input-output through a uniform interface without depending on a particular device's control registers, instruction protocol or geometry. A device driver translates the abstract requests into device-specific operations. Replacing one supported disk model with another can then preserve the application's file-reading interface.

An input-output-bound process spends much of its time waiting for input-output, often with short CPU bursts between waits. A CPU-bound process spends most of its time doing useful CPU computation, with comparatively little blocking. These descriptions concern the bottleneck in the workload; an I/O-bound process still needs CPU time.

Assume both processes are available at time zero and run the listed order, A followed by B, with no overlap even during input-output. A takes $12+4=16$ ms; B then takes $3+4=7$ ms. ThusThe scheduling turnaround time includes the time waiting before a process first runs. Reversing the serial order would leave the total at 23 ms but change completion times to 7 and 23 ms, with mean 15 ms. If arrivals were instead delayed until each serial launch, that would define a different turnaround measurement; the simultaneous-arrival convention is used for comparing the schedulers below.

With the given ready-order rule and A first, the CPU timeline in milliseconds isA performs input-output during $[4,6)$ and $[10,12)$; B does so during $[5,7)$ and $[11,13)$. In particular, B becoming ready at time 7 does not interrupt A's ongoing nonpreemptive burst. The completion times are $C_A=16$ and $C_B=17$, givingThere are 15 ms of useful CPU execution and 2 ms of idle time on this particular timeline.

An operating-system process is an execution instance of a program, with an address space, one or more software threads carrying execution contexts, and operating system resources such as file descriptors. A program describes instructions; an executable file stores a form that can be loaded for execution. Starting the same executable twice can create two operating-system processes, each with its own evolving state. A operating-system process can be waiting for input-output or waiting for a turn on the CPU, rather than executing at every instant. ^[ref]

For example, start the same counter program as operating-system processes A and B. In this toy mapping, both use virtual address 0x1234 for a counter x, but A reads x = 7 while B reads x = 42. The number 0x1234 is interpreted through the current address space, so it need not denote the same contents in both operating-system processes. Writing A's ordinary private counter does not change B's counter. Compare virtual memory for an explicit mapping to different physical addresses.

Separate virtual memory address spaces provide a usual default isolation boundary, not a claim that all computer memory is universally private. Deliberately shared mappings let operating-system processes communicate through the same stored data. Even logically private contents need not occupy distinct page frames at every moment: read-only program code can be shared, and copy-on-write can keep a common memory page until a write requires a private copy. The distinction is between which accesses and changes are permitted and which physical storage is currently reused. ^[ref][ref]

This abstraction lets independent activities reuse the same executable while keeping their changing state separate. Process scheduling distributes CPU time; virtual memory interprets and protects addresses; file descriptors connect an execution to open resources. The useful design is controlled independence with explicit ways to share. Creating operating-system processes, maintaining their mappings and performing context switches require time and computer memory; isolation alone gives no universal performance guarantee.

Process scheduling chooses which runnable operating-system process or software thread uses a CPU next, and when it gives up that CPU. Runnable means able to execute now; work waiting for an input-output operation is not eligible until that wait ends. A ready queue records eligible work. The policy chooses a recipient; a context switch supplies the mechanism for transferring execution. Sharing a single CPU lets a long calculation and an interactive program both make progress, although only one execution stream runs on that CPU at an instant.

Consider three single-software thread operating-system processes on one CPU, with abstract time units, zero context switch or scheduler overhead, and no input-output blocking. Their arrival times and CPU bursts are $(a_A,b_A)=(0,5)$, $(a_B,b_B)=(1,3)$ and $(a_C,b_C)=(2,1)$. Each CPU burst is all the execution that its task needs. With FCFS, the current task runs to completion: A occupies $[0,5)$, B $[5,8)$ and C $[8,9)$. With round-robin scheduling and scheduling quantum $q=2$, the intervals are A $[0,2)$, B $[2,4)$, C $[4,5)$, A $[5,7)$, B $[7,8)$ and A $[8,9)$. At a boundary, arrivals join the ready queue before the unfinished task whose scheduling quantum has expired; this fixes the otherwise ambiguous ordering at time 2.

The following triples always list A, B, C. Completion is an absolute time; scheduling turnaround time, scheduling waiting time and scheduling response time are durations measured from the relevant events.

For example, B first runs at time 2 under round-robin scheduling, so its scheduling response time is $2-1=1$. It finishes at time 8, giving scheduling turnaround time $8-1=7$ and scheduling waiting time $7-3=4$. Under FCFS, C waits $8-2=6$ before its sole execution interval. Under round-robin scheduling, A waits during $[2,5)$ and $[7,8)$, totaling $3+1=4$. Both timelines do exactly $5+3+1=9$ units of useful CPU work; changing the order changes who benefits first.

The appeal is that shared progress can improve responsiveness: B and C get their first CPU service sooner under round-robin scheduling, while A completes later. The arithmetic mean of the scheduling response times falls from $10/3$ to $1$; the arithmetic mean of the scheduling turnaround times is $19/3$ for both policies in this particular example. These are different goals, and this workload establishes no universal ranking. Giving each continuously runnable task repeated turns is a practical form of fairness. A smaller scheduling quantum can shorten waits between turns, but makes context switches more frequent when competitors remain runnable. If each full slice performs $q$ units of useful work and incurs a fixed switching cost $s$, the overhead fraction in that simplified repeated cycle is $s/(q+s)$. Real costs and workloads determine the choice. ^[ref]

A collection of runnable operating-system processes or software threads waiting for a CPU. A running task is not waiting in the ready queue, and a task waiting for input-output is not runnable. FCFS and round-robin scheduling can use a FIFO queue; other policies can organize eligible work differently, for example with a priority queue.

Serve the front of a FIFO queue of runnable tasks for at most one scheduling quantum. If the task finishes or must wait for input-output, it leaves the CPU earlier; if it remains runnable after consuming its allowance, append it to the rear of the ready queue. In the example under process scheduling, the ready queue at time 2 is B, C, A: B arrived at time 1, C joins at the boundary, then A is requeued. That one convention determines the subsequent order.

The total duration a task spends runnable but waiting for a CPU, including later waits after scheduling preemption. Under the zero-overhead, no-input-output-blocking assumptions of process scheduling, elapsed time partitions into useful execution and such waiting, so $W_i=T_i-b_i$, where $T_i$ is scheduling turnaround time and $b_i$ is the total CPU burst. Thus C under round-robin scheduling has $W_C=3-1=2$. If a task also spends time blocked on input-output, that blocked duration belongs to scheduling turnaround time but must not be counted as scheduling waiting time.

// Target: computer-science.bigb

Memory thrashing is repeated costly cycling of memory pages out of and back into computer memory, leaving little useful computation between page faults. Active demand can exceed the available page frames, especially when multiprogramming admits too many operating-system processes. A high page fault rate during initial loading alone does not establish memory thrashing. ^[ref]

Consider one operating-system process making the 20 memory references $1,2,3,4,1,2,3,4,\dots ,1,2,3,4$: five repetitions of four memory pages. Start with an empty resident set, use demand paging and exact LRU replacement, and assume no prefetching or competing operating-system processes. A hit finds the requested memory page resident; a miss requires a nonresident page fault. With three page frames, references 1–3 load pages 1–3. Reference 4 evicts page 1, reference 5 reloads page 1 and evicts page 2, and the cycle continues: every return finds its memory page evicted. With four page frames, only the first four references miss; all four memory pages then remain resident.

The four initial misses with four page frames are compulsory first-use misses from the empty resident set. They are startup work; the three-page frame case keeps faulting after startup. This makes the difference between memory thrashing and loading a new working set visible. For the three-page frame trace, each reused memory page has three distinct intervening memory pages, so LRU replacement has already evicted it before its next use.

To quantify the cost, assume each hit takes 100 nanoseconds and each miss incurs an additional 1 millisecond of page fault service, followed by the same 100-nanosecond memory access. These are toy latencies, not measurements. With miss probability $p$, the expected value of access time isThe service cost is additional: it does not include the final 100 nanoseconds. Thus $p=1$ gives $1,000,100\mathrm{ns}$ and $p=0.2$ gives $200,100\mathrm{ns}$, approximately a fivefold ratio over the complete trace. Over references 5–20, the corresponding ratio is $1,000,100/100=10,001$: repeated page faults dominate the useful accesses. The expected value model follows the additive miss-penalty convention of OSTEP chapter 22, section 22.1. ^[ref]

Not every page fault performs disk input-output: demand paging can allocate zero-filled memory pages, and copy-on-write can copy an existing page frame. The toy service cost models expensive misses; the miss trace alone establishes residency behavior, while memory thrashing additionally concerns repeated costly cycling. ^[ref]

Possible remedies are more resident page frames, less multiprogramming, or reorganizing accesses to improve temporal locality. For this toy sequence, one extra page frame suffices under LRU replacement; that is not a universal threshold or policy. Page replacement alone cannot make every simultaneously needed memory page fit.

// Target: computer-science.bigb