Remzi H. Arpaci-Dusseau coauthored Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and others. The book organizes operating systems around virtualization, concurrent computing and persistence: sharing hardware, coordinating overlapping execution and retaining data. Its worked models connect process scheduling, virtual memory and file systems to the mechanisms that implement those goals.^[ref]

Pat Morin wrote Open Data Structures: An Introduction by Pat Morin, an open textbook presenting implementations of data structures together with mathematical analyses of their operation costs. Its topics include hashing, search trees, heaps and graphs. The text makes the representation part of the performance argument, rather than treating an abstract operation name as a sufficient cost model.^[ref]

A store of selected information kept for faster reuse. A translation lookaside buffer is a memory cache of address translations; a buffer cache instead holds device-block contents.

For a data memory cache, the useful bargain is to keep a small selection of computer memory close to the CPU. A cache hit serves a read from that selection; a cache miss requires obtaining the contents elsewhere. Temporal locality helps a retained cache block serve repeated reads, and spatial locality helps one transferred cache line serve neighbouring bytes. Placement, capacity and LRU replacement determine whether that opportunity survives until the next read. ^[ref]

The worked memory access trace below uses twelve single-byte reads at these decimal physical addresses, in this fixed order:Assume an initially empty fully associative cache, 16-byte aligned cache blocks, and capacity two cache slots: 32 bytes of cached data, excluding metadata. Use exact LRU replacement, refreshing recency on every read, including cache hits. Every cache miss fetches its requested cache line completely before the next read; only a full memory cache needs an eviction. There are no writes, fetching ahead of requests, external invalidations, or overlapping reads. All addresses denote ordinary cacheable computer memory, and address translation is outside this model. These are deliberately synthetic assumptions, not specifications of a particular CPU.

This makes the outcome reproducible from the memory access trace, rather than from an informal impression that data are “nearby” or “recent”. The cache line geometry below identifies the requested unit; fully associative cache enumerates the resulting states; average memory access time translates the counts into a simple timing calculation.

A unit of information; throughout these examples, one byte contains eight bits and is the smallest independently addressed unit of computer memory.

An address in the physical address system, obtained from a virtual address by address translation in the examples here. Physical address ranges can also identify devices, so not every physical address denotes ordinary computer memory.

An access to a location in computer memory, such as an instruction fetch, a read or a write. A page-level reference sequence records the corresponding memory page for each access, retaining repetitions and order.

Tracking how many references retain an object. For the copy-on-write model, the object is a page frame and each mapping retains it; removing the last reference permits reclamation. Real operating-system kernels can track other kinds of ownership too. ^[ref]

Vector graphics represent a picture by geometric objects and instructions for drawing them: positions, shapes, fills, boundary strokes and transformations. A circle can be stored as a centre and radius; a rectangle as a corner, width and height; a polygon as an ordered list of vertices. These geometric primitives describe whole objects rather than assigning a colour to every pixel. SVG provides elements for such basic shapes and for paths assembled from line segments and curves.^[ref]

The useful separation is between the stored geometry and the finite output. A circle of radius 2 remains the same geometric description whether rendered across twenty or two thousand output pixels. This is the sense in which vector graphics are resolution independent: increasing the output grid can evaluate the original geometry again. The resulting raster image still has finite spatial resolution, and numerical coordinates have finite precision. Enlarging a previously rendered raster image through interpolation instead works with its existing samples. Neither operation guarantees that arbitrarily thin details remain visible at every size.

An SVG path uses a current point and drawing commands. For example, M 1 4 L 5 4 L 3 1 Z moves to $(1,4)$, draws two line segments, then closes back to the starting point, giving a triangle. Uppercase commands use absolute coordinates; the corresponding lowercase commands use offsets from the current point. Thus M 1 4 l 4 0 l -2 -3 z describes the same triangle. The coordinates belong to the current user Cartesian coordinate system, not necessarily to output pixels.^[ref]

For a curved example, the path M 1 4 Q 3 0 5 4 Z uses one quadratic Bézier curve followed by a closing line segment. With control points $P_0=(1,4)$, $P_1=(3,0)$ and $P_2=(5,4)$, its curved boundary isThe endpoints are $P_0,P_2$, and $B(1/2)=(3,2)$; the interior control point $P_1$ is not a point on the curve. A fill paints the enclosed region, while a stroke paints a band around its boundary with a chosen width. One can use either or both: geometry and paint instructions are distinct.^[ref][ref]

The first illustration uses increasing $y$ downward, following the initial SVG coordinate convention. Its dashed control polygon guides the eye; it is not part of the filled path. Apply the affine mapThis combines horizontal scaling, a shear mapping and a translation. The transformed control points are $(4.5,5)$, $(5.5,1)$ and $(10.5,5)$, giving the path M 4.5 5 Q 5.5 1 10.5 5 Z. Its curved midpoint is $T(3,2)=(6.5,3)$. The affine equivariance of a geometric basis explains why transforming only the control points transforms the entire Bézier curve: its weights sum to one, so the translation is added exactly once. The enclosed area is ${\int }_0^{1}8t(1-t)\cdot 4dt=16/3$ before transformation and $|\det A|\cdot 16/3=8$ afterwards. These checks concern the filled region, excluding the width of any stroke.

An SVG viewBox specifies a rectangle in user coordinates to map into a display region. For example, viewBox="0 0 6 6" in a square viewport of 120 by 120 display units gives a scale of 20 display units per user unit; in a square viewport of 600 by 600 it gives 100. The path's control points need not change. For unequal proportions, preserveAspectRatio controls whether the mapping preserves proportions or stretches the axes separately. These display units need not correspond one for one to physical display pixels.^[ref][ref]

Rasterization converts the geometric drawing into a raster image on a chosen grid. Deciding whether each pixel centre lies inside a filled region is a simple rule, but a moving diagonal boundary can make entire pixels switch abruptly. Antialiasing reduces these sampling artifacts by accounting for a footprint around each sample, rather than treating every pixel as a single inside-or-outside decision. This connects vector graphics to raster sampling and reconstruction and aliasing; a finer grid and a better sampling rule solve different parts of the problem.

For an exact analytical model, fill the region $R=\{(x,y)\in [0,4{]}^2:y\le x+1/4\}$. For a square pixel footprint $S$, letHere ${\alpha }_S$ is geometric coverage, and $L$ is relative luminance for ideal opaque neutral shades, with $L_{\mathrm{fill}}=0$ and $L_{\mathrm{background}}=1$. The intersection and area determine how much of the footprint is covered. This is a specified area-average model, not a claim that every SVG renderer uses exact coverage. The SVG shape-rendering property supplies rendering hints and permits implementation tradeoffs, including disabling antialiasing for some choices.^[ref]

On the $4\times 4$ grid of unit squares, $S=[0,1]\times [0,1]$ has coverage ${\alpha }_S=1-(3/4{)}^2/2=23/32$, whereas the pixel centre $(1/2,1/2)$ lies inside $R$ and gives coverage 1 under the centre rule. The adjacent square $[0,1]\times [1,2]$ has coverage $1/32$ but its centre lies outside. The entire filled area is $16-(15/4{)}^2/2=287/32$. Summing exact coverage times cell area gives this value on both the $4\times 4$ and $16\times 16$ grids; the coarse centre rule instead gives 10. Coverage values are displayed after sRGB encoding of the modeled relative luminance. The thin coloured line is a geometry overlay, not an extra sampled stroke. Enlarging the middle panel by nearest-neighbor interpolation would repeat its sixteen values; re-rendering the geometry produces the 256 independently evaluated footprints in the right panel. Antialiasing reduces abrupt edges but cannot make a finite grid preserve every geometric detail.

The attractive feature of vector graphics is editability at the level of intent: move one control point to bend a boundary, change a circle's radius, or transform a whole diagram while keeping its parts aligned. Logos, technical diagrams and outline fonts benefit because their structure can be expressed with relatively few shapes and curves. A complicated photograph may require enormous geometric detail, so vector graphics do not imply a smaller file than raster graphics. Nor does an SVG container guarantee that every object is vector geometry: its image element can embed or reference a PNG raster image. Transforming that embedded raster image changes its placement and reconstruction, but does not recover missing original detail.^[ref]

sRGB specifies a red-green-blue colour encoding. Restricting attention to component values in $[0,1]$, its encoded component $s$ corresponds to the linear-light componentThus the conversion is piecewise, not a single power law. The reverse conversion used here isThese conventional rounded thresholds are used by the W3C conversion routines; they give a tiny mismatch at the join rather than a mathematically exact pair of inverses everywhere.^[ref][ref]

For an eight-bit neutral grayscale code $q$, use $s=q/255$ in all three components. Its relative luminance is then $D(s)$. For example, $D(0.5)\approx 0.21404$, whereas $E(0.5)\approx 0.73536$. This is why averaging encoded values and averaging linear light give different answers. sRGB is a specified interpretation; merely calling a raster image grayscale does not imply it uses sRGB.

Raster graphics describe a picture by an array of pixels on a grid. For a rectangular image of width $W$ and height $H$, write its stored values as $p_{rc}$, with $0\le r<H$ and $0\le c<W$. A grayscale pixel can have one shade value; a colour pixel can have several component values. The grid specifies where values belong, while the encoding specifies what those values mean. A raster image therefore needs dimensions and an interpretation of its samples, not just a string of numbers.

The appealing feature is that pictures become explicit data: selecting a rectangle selects entries of an array; comparing two images compares their pixel values; image compression can exploit repeated or related values. Raster sampling and reconstruction explains why the stored grid and the displayed picture are different objects. A square drawn around a sample is one display convention, not a claim that the original scene consisted of little squares.

For example, a $6\times 4$ grayscale raster image stores 24 pixel values, even when displayed across a much larger rectangle. With one unsigned eight-bit sample per pixel, its uncompressed sample payload is $24\cdot 8=192$ bits; a file format can additionally require a file header, padding and other information, and image compression can change the stored size.

Enlarging that image can copy each pixel into a block through nearest-neighbor interpolation, or infer intermediate values through interpolation. Either procedure supplies a reconstruction rule; neither determines which unrecorded detail was present in the original. Vector graphics use a different representation, specifying geometric objects to be rendered onto a chosen grid. Re-rendering such a description and enlarging an existing raster image are different operations.

Hardware translating device DMA addresses to physical addresses, with access restrictions used for device isolation. Availability, configuration and isolation boundaries depend on the platform; merely having an IOMMU does not establish complete isolation. ^[ref]

Direct memory access transfers data between a device and computer memory without the CPU executing a copy instruction for each item. The CPU still sets up the operation and observes completion. DMA answers who moves the data; an interrupt answers how a need for attention is announced. A DMA transfer can therefore finish with interrupt-driven input-output or with polled input-output. ^[ref]

For a toy receive operation, the CPU arranges a four-byte DMA buffer and tells the device its DMA address, length and direction. The device writes the bytes A, B, C, D into that DMA buffer. After completion and any required DMA buffer synchronization, the CPU can read those four bytes. There are four payload bytes, but no four-item CPU copy loop on the device-to-computer memory path. This is a schematic example, not an instruction to operate real hardware.

The useful separation is that the CPU can perform other work while a larger transfer proceeds. The reasoning is a division of responsibilities: setup specifies the destination and extent once; the transfer engine advances through the payload; completion reports the result. The data still crosses an interconnect such as a computer bus, which must share access among competing initiators. Setup, mapping, synchronization and completion cost work, so DMA does not promise a speedup for every transfer size. ^[ref]

Correctness also requires keeping the DMA buffer alive and coordinating its ownership until the device is finished. A DMA address need not equal a CPU virtual address or physical address. An IOMMU, when present and configured, translates device addresses and can restrict access to authorized computer memory; it is not the CPU's memory management unit. Operating-system process isolation through virtual memory alone does not establish those device-access restrictions. ^[ref][ref]

Intel QuickPath Interconnect is a packet-based point-to-point interconnect designed for communication among CPUs and other system components. It includes a cache coherence protocol, allowing distributed memory caches and memory controllers to participate in a coherent memory system. Its layered design separates electrical transmission, reliable link transfer, routing and higher-level transactions.^[ref]

For example, a CPU requesting a cache line may obtain the current data from another CPU's memory cache, coordinated by the cache coherence protocol. The Intel QuickPath Interconnect link layer uses credits representing available receiving buffers: transmission consumes credits, and freeing buffers returns them. This controls how much data the receiver must accept.^[ref]

As with PCI Express, independent links can operate concurrently while traffic sharing a link or destination can contend. The shared buses and point-to-point links distinction prevents applying a single globally shared bus model to the entire interconnect.

// Destination: computer-science.bigb

PCI Express is a packet-based input-output interconnect built from point-to-point links. A PCI Express root complex connects the host system to a hierarchy of endpoints, optionally through PCI Express switches. Each link joins two ports, so the whole hierarchy need not share one electrical path.^[ref]

A PCI Express lane contains a transmit differential signal pair and a receive differential signal pair, allowing traffic in both directions. Several PCI Express lanes can form one wider link.^[ref] For example, independent endpoint links can carry traffic concurrently, but traffic from both endpoints that converges on one upstream link competes for its available capacity. A link's payload throughput depends on its width, signaling and protocol overhead. The distinction under shared buses and point-to-point links therefore matters when interpreting the familiar term computer bus.

The word “bus” is also used for interconnect families that do not give all components a single shared electrical path. Intel's An Introduction to the Intel QuickPath Interconnect (January 2009, p. 8, “Interconnect Overview”) explicitly describes Intel QuickPath Interconnect as a point-to-point link despite the serial-bus terminology, and compares it with PCI Express. Here each link connects two endpoints. Independent links can carry traffic concurrently; traffic converging on one link or target still competes for that resource. The shared-bus timing example's single owner and serialized service must therefore not be assumed for a whole network of links merely because its interfaces are called buses. Serial versus parallel transfer and shared versus point-to-point topology are separate distinctions.

Useful payload completed per unit elapsed time, with the observation interval stated. A raw data bus rate counts available transfer capacity; achieved bus throughput also depends on setup, bus wait states, idle intervals and sharing. Bus contention can increase a requester's delay even when the aggregate bus throughput remains unchanged, as the shared-bus timing example shows.

Selecting among initiators requesting a shared resource. An arbiter grants permission before an initiator starts its bus transaction. Fixed priority can indefinitely postpone a lower-priority requester under continuing higher-priority demand. Rotating priority can provide starvation freedom when every owner releases the resource after bounded work. Neither policy alone determines bus throughput: waiting, setup and target readiness also matter.^[ref]

One requested operation and its completion, potentially including several payload transfers. A bus transaction identifies a target, specifies an operation and exchanges data or status. A CPU or DMA engine can initiate one; a target responds. The terms “master” and “slave” in older hardware documents refer to these initiator and target roles.^[ref]