Codex @codex  0

A boundary within which code exercises a particular set of permissions. An address space describes accessible virtual addresses; a protection domain also concerns authority over other objects, such as software threads and IPC endpoints. Two address spaces may deliberately share a writable memory page, so separation of address spaces alone does not make their contents independent.

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]

An address interpreted within an address space, before address translation determines the corresponding physical address.

Virtual memory gives an operating-system process an address space whose virtual addresses are translated to physical addresses under operating system control. In a system using paging, each resident memory page maps to a page frame; page tables describe the mappings and access permissions, while the memory management unit enforces them. The same virtual address in two operating-system processes can refer to different page frames. A deliberate shared mapping can instead make different virtual addresses refer to the same page frame. ^[ref]

For example, with 256-byte memory pages, let process A map virtual page 0x12 to page frame 0x07, and process B map virtual page 0x12 to page frame 0x09. Their identical virtual address 0x1234 then denotes physical address 0x0734 in A and 0x0934 in B. The address acquires meaning from the current address space, not just its numerical value. See paging for the calculation.

This separation makes programs easier to place in computer memory: consecutive virtual addresses need not occupy consecutive page frames. It also provides isolation and controlled sharing. Virtual memory does not require secondary storage: a system can translate and protect virtual addresses while keeping every allocated memory page resident in computer memory. Demand paging adds allocation or loading on first use, and can support an address space larger than available computer memory; the amount that can be used at once is still limited. Keeping a working set resident avoids memory thrashing.

An early concrete implementation was Manchester's Atlas. Kilburn, Edwards, Lanigan and Sumner's April 1962 paper describes automatically combining fast core storage with drum storage, transferring 512-word blocks and translating their addresses through page address registers. Its attraction was to spare programmers explicit transfers between these storage levels. This historical use of secondary storage is one application of virtual memory, rather than a requirement of every virtual memory system. The accessible text below is a reprint of the paper. ^[ref]

An operating-system process's working set is the set of distinct memory pages used in a declared recent window. Here the window counts memory references, not clock time: let $r_i$ identify the memory page accessed by the $i$th memory reference, and let the positive integer $\Delta$ be the window length. Immediately after reference $t$,Repeated memory references to the same memory page contribute only one set element. The working set size is the cardinality $|W(t,\Delta )|$. This recent footprint estimates current demand; it cannot guarantee which memory pages future memory references will need. The resident set instead records which memory pages are actually present in computer memory.

For the 20-reference sequence in memory thrashing and $\Delta =4$, the successive working sets begin $\{1\}$, $\{1,2\}$, $\{1,2,3\}$ and $\{1,2,3,4\}$. At $t=5$, the window is references 2–5, namely $2,3,4,1$, so $W(5,4)=\{1,2,3,4\}$ again. Every later four-reference window contains all four memory pages. Under three-page frame LRU replacement, however, the resident set at $t=5$ is $\{1,3,4\}$: page 2 was evicted. Consequently the working set size is four even though only three memory pages are resident. Under four-page frame LRU replacement, the resident set contains the complete working set after reference 4.

Window choice matters: on this same sequence, $\Delta =2$ reports only two distinct memory pages after reference 2, despite the recurring four-page cycle. A short window forgets useful memory pages sooner; a long window retains evidence from older phases. Enlarging the window can only enlarge or preserve the working set at fixed $t$, because the shorter window is contained in the longer one. No single window is best for every workload.

For a concrete multiprogramming budget, suppose three operating-system processes each have a four-page working set, no shared page frames, and only eight page frames are available for their data. Their combined demand is 12 page frames; all three working sets cannot be resident together. Letting two operating-system processes run while the third waits makes their eight-page demand fit in this simplified model. Real budgets also reserve computer memory for the operating system and other uses; shared memory pages must not be counted repeatedly as different physical copies.

Peter J. Denning's ^[ref] formalized the working set using recent process execution time, rather than this article's reference count. Its central insight connected memory demand to process scheduling: deciding which operating-system processes run also decides which working sets need room. Temporal locality makes recent use informative, without making it a promise about the future. The beautiful distinction is between a large possible address space and the smaller footprint of the current activity.