A value written directly in program text, such as an integer numeral or a quoted string, rather than obtained through a program identifier. Distinct spellings can denote the same value.

A name used by a program, such as x in a variable assignment. An abstract syntax tree can record the name without determining which value it denotes.

A parser recognizes how text fits a programming language syntax and can construct a parse tree or abstract syntax tree.

Recognition of lexical tokens in program text before or during parsing.

A processor register identifying the current position in a stack, commonly a call stack; the exact convention depends on the architecture. Restoring a stack pointer selects the saved stack position, rather than copying the whole call stack.

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]

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

The duration from a task's arrival $a_i$ until its completion $c_i$: $T_i=c_i-a_i$. It includes execution and all intervening waits. For A under round-robin scheduling in process scheduling, $T_A=9-0=9$, despite a scheduling response time of zero.

The delay from a task's arrival $a_i$ until its first execution $f_i$: $R_i=f_i-a_i$. This measures access to initial CPU service, rather than completion of an entire user request. For C under round-robin scheduling in process scheduling, $R_C=4-2=2$; its scheduling turnaround time is instead $5-2=3$.

Taking the CPU away from a still-runnable task before it voluntarily yields or finishes. Round-robin scheduling uses scheduling preemption when a scheduling quantum expires, commonly using a timer interrupt to regain control. Kernel preemption is the more specific question of whether an execution already within the operating-system kernel can be suspended for another runnable context.

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.

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.

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.

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]

A nonnegative integer identifying an open access in one operating-system process. The program passes its value to operations such as reading and closing; the operating-system kernel interprets it through that operating-system process's descriptor table. In the toy example, table entry 3 refers to an open file description for inode 42. Another operating-system process's entry 3 can reach a different file, and a closed file descriptor value can be reused. ^[ref]

Cited passages: the definition starts on printed p. 205. Equation (4.1.5) and Theorem 4.1.13 on p. 212 give the law of total expectation and nested tower property. Theorem 4.1.15 on p. 213 gives the conditional mean as an orthogonal projection and the best predictor under mean squared error.

A statistician develops or applies methods for collecting data and learning from it under uncertainty. The work connects experimental design, probability models, estimation and statistical hypothesis testing. For example, deciding how many independent observations to collect requires linking the desired precision of a confidence interval to the variation expected under a statistical model. Interpreting results also requires examining sampling bias, missing data and assumptions about dependence.

Linear least squares minimizes $\Vert Ax-b{\Vert }^2$ over a vector $x$. Its normal equations for linear least squares are $A^{T}Ax=A^{T}b$; geometrically $Ax$ is the orthogonal projection of $b$ onto the range of $A$.

A coupling of probability distributions $\mu ,\nu$ is a joint probability distribution of random variables $(X,Y)$ whose marginal distributions are $\mu ,\nu$. It lets us choose the statistical dependence between two random constructions while preserving the individual laws. This choice can make a comparison much easier: giving two simulations the same random input may keep their paths close, even though separately generating both paths would hide that relationship.^[ref]

For example, two fair coin tosses can be generated independently, with mismatch probability $1/2$, or by tossing once and setting $Y=X$, with mismatch probability zero. Both constructions have the same two Bernoulli distributions as marginals. Their joint laws differ. A maximal coupling makes the values agree as often as possible; a coalescing coupling arranges permanent agreement of two processes after a random time. Minimizing expected geometric separation instead leads to Wasserstein distance.

A centered random variable $X$ is sub-exponential with parameters $({\nu }^2,b)$ ifwhere $\nu ,b>0$. Unlike a sub-Gaussian random variable, the moment-generating-function bound is needed only near zero. Optimizing exponential Markov inequality over this restricted interval gives a two-sided tail bound of the formwith an absolute constant $c>0$. Small deviations therefore have a quadratic exponent and large deviations a linear exponent. Equivalently, up to constant changes in parameters, $\mathbb{E}{e}^{|X|/K}$ is bounded for some finite scale $K$.

For an exponential random variable $Y$ of mean one, $X=Y-1$ has moment-generating function $e^{-t}/(1-t)$ for $t<1$. Its logarithm is ${\sum }_{k\ge 2}{t}^k/k$, which is at most $t^2$ for $|t|\le 1/2$, proving a sub-exponential bound. The Centered square of a sub-Gaussian random variable is another example. The term here refers to exponential-tail concentration, and differs from the subexponential distribution defined by heavy-tail convolution asymptotics.