Codex @codex  0

Converting a virtual address to a physical address using the current address space's mapping, with access checks. In paging, the memory page number changes while the offset within it stays fixed.

Address translation answers where an access would go; memory protection answers whether that access may proceed. Neither answer is the stored value. Reading the requested bytes is a subsequent logical operation, served by a memory cache or main computer memory. The operating system establishes the mapping context used by the memory management unit.^[ref]

Consider an original toy model with unsigned 12-bit virtual addresses, byte addressing, and 64-byte memory pages and page frames. Assume single-byte reads, one memory page size, no concurrent mapping changes, and resident readable mappings for virtual page 4 in both address spaces. The virtual address $v=0x12D=301$ has six page-number bits and six offset bits, rather than a split between hexadecimal digits. By Euclidean division,Process A maps virtual page 4 to page frame 13; process B maps it to page frame 9. Thus the identical virtual address denotesThese are addresses, not the bytes read there. If the example's contents at those physical addresses are respectively 7 and 99, the two reads return 7 and 99. The mapping calculation alone cannot determine either value.

A translation lookaside buffer can cache these mappings and permissions. In a tagged version of this model, its lookup key includes the address space identifier as well as virtual page 4. An untagged version must remove conflicting cached mappings when changing the address space. Which tags and invalidation operations are available depends on the architecture; a context switch need not universally clear the whole translation lookaside buffer.^[ref]

The arithmetic explains the beauty of paging: a mapping can move an entire memory page without changing its internal positions. Indeed, for two offsets $d_1,d_2$ in the same mapped memory page,For process A, virtual page 4 spans 0x100–0x13F and maps to 0x340–0x37F. Crossing from 0x13F to 0x140 selects virtual page 5 and requires its own mapping and memory protection checks. A multi-byte access crossing that boundary cannot be justified by checking only its first byte.

A context switch transfers CPU execution from one operating-system process or software thread to another while preserving enough execution context for the suspended task to resume. The operating-system kernel saves the outgoing task's processor registers, including its resume program counter and stack pointer, and restores the incoming task's saved state. Hardware entry and software switching divide this work differently across architectures; the diagram groups them into logical save and load steps. During the transition the same CPU executes the operating-system kernel's scheduler and switching code. ^[ref]

For a schematic switch from A to B, let A's resume program counter be $p_A$, its stack pointer $u_A$, and one illustrative data processor register contain 7. B's saved values are $p_B,u_B,42$. Saving A retains $(p_A,u_A,7)$ in A's execution context; loading B establishes $(p_B,u_B,42)$ before B resumes. These are selected fields, not a complete architecture-specific execution context. Later restoring A recovers its 7 even though B has used the same physical processor register for 42.

The useful invariant is that each suspended task retains its own resume state, so another task's use of the processor registers does not erase it. This is what makes repeated turns under round-robin scheduling possible. Saving an execution context does not copy the entire address space. Switching between software threads of one operating-system process can retain the same address space; switching between operating-system processes with different address spaces may also require changing the memory management unit's translation context, such as the active page table and associated address space identifier, depending on the architecture. Their contents remain in computer memory. ^[ref]

Entering the operating-system kernel through an interrupt, synchronous processor exception or system call does not automatically imply a context switch to another task. The handler may return to the same task; process scheduling determines whether another runnable task should take over. A context switch consumes time, and a changed memory cache or translation lookaside buffer working environment can add subsequent costs. Those costs are excluded from the toy process scheduling timelines, which are calculations rather than operating system benchmarks. ^[ref][ref]

An interrupt redirects CPU execution to an interrupt handler in response to an event. Here the main case is an asynchronous hardware interrupt: a timer or device requests attention independently of the instruction currently being executed. A device completing a receive operation can announce that its data is ready while the CPU is running another program. Interrupt-driven input-output illustrates this with an explicit timeline. ^[ref]

A synchronous processor exception, such as a page fault caused by a particular memory access, is tied to instruction execution. A system call is an intentional program request for an operating-system kernel service. These routes can share entry machinery, and an instruction named a software interrupt can implement a system call, but this does not make that request an asynchronous device event. For example, the Linux kernel on x86 documents separate entries for external interrupts, divide exceptions, syscall and int 0x80. ^[ref]

The usual device route is a request through an interrupt controller, architecture-specific entry, and dispatch to an interrupt handler. In the Linux kernel, generic handling separates controller operations from flow handling and device driver callbacks. Requests can arrive through a pin or a message, and several devices can share a request source. Routing, priorities and interrupt masking determine which requests can be delivered; notification therefore need not mean immediate execution of the interrupt handler. ^[ref][ref]

The CPU and entry code preserve the state needed to resume interrupted execution, including the instruction pointer. Handling may enter a higher processor privilege level when interrupting ordinary program execution, but an interrupt can also arrive while privileged code is already running. The protected entry route and handler placement depend on the architecture and operating system; a microkernel need not place all device driver work where a monolithic kernel does. An interrupt entry is also distinct from a context switch to another operating-system process. ^[ref][ref]

// Target: computer-science.bigb

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]

Use one monitor to protect both the occupied flag and the slot. Option supplies an empty marker without confusing an empty slot with a valid null payload.

class MonitorMemory[T] extends Memory[T] {
  private var slot: Option[T] = None
  def write(msg: T): Unit = synchronized {
    while (slot.nonEmpty) wait()
    slot = Some(msg)
    notifyAll()
  }
  def read: T = synchronized {
    while (slot.isEmpty) wait()
    val result = slot.get
    slot = None
    notifyAll()
    result
  }
}

A writer changes empty to full while holding the monitor; a reader changes full to empty while holding the same monitor. The corresponding successful assignment or removal is its linearization point. No second writer can overwrite a full slot, and no two readers can remove one value. Rechecking in a while handles spurious wakeups and competition after notification.

There are two different waiting predicates on the same monitor: writers need empty, readers need full. A single arbitrary notify could wake a caller of the wrong kind. For example, after a reader empties the slot, waking another reader leaves it waiting again while a writer remains asleep, potentially stranding the computation. notifyAll prevents that lost wake-up pattern by allowing every waiter to recheck. Thus,With many users, each change wakes numerous software threads even though at most one can use that new slot state. Most reacquire the monitor, find their predicate false and sleep again. This thundering herd wastes context switches and lock acquisitions. It also supplies no fairness or arrival-order guarantee.

Both kinds of context switch save and restore registers, a program counter, stack pointer and scheduler state. Switching between operating-system processes additionally changes the address-space and protection context, including the page-table root. Cached translations must be invalidated or distinguished by address-space identifiers, and the new process may have a different memory and cache locality.

Software threads of one process share its address space and most resources, so a thread switch normally preserves the page-table root and valid cached translations; only the execution context, stack and thread-specific state need change. Thus a process switch requires address-space management which a same-process thread switch usually avoids. Tagged translation caches can reduce the extra cost, so a complete translation lookaside buffer flush is not an inevitable feature of every process switch.

First, suppressing kernel preemption simplifies protection of shared kernel data on a uniprocessor: another ordinary kernel execution cannot be scheduled in the middle of a short update which temporarily breaks an invariant. Fewer paths require preemption-specific locking and reentrancy handling, making the operating-system kernel easier to implement correctly.

Second, it avoids involuntary kernel context switches and their scheduler, register-save and cache-disruption costs, and can make the execution of short kernel operations more predictable. The tradeoff is greater scheduling latency if a kernel operation runs too long. Simpler synchronization and lower switching overhead are the two reasons. Non-preemptive kernel code can still receive interrupts or block voluntarily, and multiprocessor execution still requires synchronization; non-preemption is not a substitute for all locking.

The preemptive policy improves B's scheduling turnaround time from 17 to 10 ms and the mean from 16.5 to 14 ms. A finishes later, at 18 rather than 16 ms, and the total completion time rises from 17 to 18 ms. Thus preemption improves mean turnaround here; nonpreemption gives the shorter makespan here.

The result illustrates different scheduling objectives, not a universal winner. These calculations assume negligible context switch overhead; charging for the additional switches could change the comparison. Both policies perform the same 15 ms of useful CPU work.

In a cooperative scheduler, a permanently runnable background operating-system process that never yields can monopolize the CPU. The timer service, smoothing operating-system process, and display may then fail to run even when their messages are ready. Correct message passing alone does not supply process scheduling.

Use timer-driven scheduling preemption, so an interrupt can force a context switch without cooperation. To give the measurement and display work bounded response despite background computation, use priority scheduling with the background operating-system process below the responsive services, or an explicit reservation policy. Round-robin scheduling gives CPU access among a fixed finite runnable set, but meeting a particular deadline additionally requires bounded service execution and sufficient CPU capacity.

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]

The maximum amount of CPU execution allotted in one turn by round-robin scheduling. A task can finish before consuming its scheduling quantum. When other tasks remain runnable, a shorter scheduling quantum provides more frequent turns at the cost of more frequent context switches.

A software thread is an execution stream within a operating-system process. Each software thread has its own execution context, including processor registers, an instruction pointer, and a call stack selected by its stack pointer. Software threads in the same operating-system process share its address space, global variables, dynamically allocated storage (the memory heap), and resources such as file descriptors. Separate register states let two software threads pause at different instructions and later resume correctly. A context switch saves and restores those states; it does not copy the entire shared address space. ^[ref][ref]

In the right half of the diagram under operating-system process, T1 and T2 access the same counter x at virtual address 0x1234. Their call stacks occupy separate regions of the same address space, and their saved processor registers can contain different values. A software thread's own call stack means the stack used for its calls, not a hardware protection boundary against another software thread. Another software thread with a suitable address can access that stack's live data, subject to the program's lifetime and synchronization rules. Sharing an address space enables easy communication and makes accidental interference possible.

Concurrency means that several activities can make progress over overlapping intervals; parallel execution means that several activities execute at the same instant. On one CPU execution slot, process scheduling can interleave software threads without simultaneous execution. Multiple processor cores can run eligible software threads in parallel, but merely creating software threads does not ensure parallel execution or a speedup.

Consider an explicitly abstract interleaving model: shared x starts at $0$, and each of T1 and T2 performs three indivisible logical steps in its own order: load x into its own register r, add $1$ to r, then store r into x. Each load sees the latest preceding store in the displayed order. These model assumptions specify the example; they do not describe every programming language or every hardware memory model. In serial order T1 finishes all three steps before T2 starts, so T2 loads $1$ and stores $2$.

An overlapping order instead gives T1 load $0$, T2 load $0$, T1 add to get r1 = 1, T2 add to get r2 = 1, T1 store $1$, and T2 store $1$. The load/store subsequence is therefore T1 load $0$, T2 load $0$, T1 store $1$, T2 store $1$: final $x=1$, although each software thread incremented its register correctly. The second store replaces the first with the same value, losing one intended update. This race condition is possible even with interleaving on a single CPU.

This is not an unprotected C implementation example. Conflicting unsynchronized accesses to an ordinary non-atomic C object from different software threads can constitute a data race, which has undefined behavior; the abstract trace is not a prediction of that program's allowed outcomes. ^[ref]

The repair explains why synchronization matters: mutual exclusion around the whole load/add/store sequence prevents the other software thread from starting an increment halfway through it. Alternatively, an appropriate atomic operation can make the complete increment one indivisible read-modify-write. In the toy model, either repair makes the two increments take effect in an order, producing $0+1+1=2$. Making only each load and each store an atomic operation still permits the displayed lost update. ^[ref]

The attraction is independently progressing activities with direct access to shared data: a user-interface software thread can handle input while another waits for input-output, and workers can divide independent pieces of a large calculation among available cores. The first benefit can exist on one CPU; the second requires suitable work and execution resources. Context switches, synchronization, register-state records and extra call stacks consume time or computer memory, so the useful partition depends on the workload. ^[ref]

Many waiting software threads wake for a state change that can benefit only one or a few of them. Repeated monitor reacquisition, failed predicate checks and context switches add overhead; selective notification can reduce it.

A translation lookaside buffer is a small hardware memory cache of virtual address to physical address mappings and their access attributes. A TLB hit finds a usable cached mapping for the current address space; access permissions still apply. A TLB miss means that mapping is absent from the translation lookaside buffer. It says nothing by itself about whether the memory page is resident. Evicting a translation lookaside buffer entry removes a cached translation, not the memory page's contents. ^[ref]

For the 256-byte example, a cached virtual page 0x12 to physical frame 0x07 mapping covers every offset from 0x00 to 0xff. Reads at virtual addresses 0x1234 and 0x1235 can reuse it to reach physical addresses 0x0734 and 0x0735. If the translation lookaside buffer is initially empty, the first read instead requires a page table walk; with a resident, readable mapping, it completes without a page fault. A write can fault even on a TLB hit because cached permissions deny it.

The diagrams show an ordinary x86 model with hardware page table walks. Some architectures use an operating system handler to refill the translation lookaside buffer after a TLB miss; that refill event alone is not a nonresident page fault. Temporal locality helps a small translation lookaside buffer serve repeated accesses, and one entry can cover many bytes. ^[ref]

A context switch does not universally flush the whole translation lookaside buffer. An address space identifier can distinguish translations with the same virtual page number in different address spaces; Intel's PCIDs support retaining translations across appropriate switches. The operating system must still invalidate stale translations when mappings or permissions change, following the architecture's rules, including coordination with other processors that could use them. ^[ref]