1.2.1 - Paging, segmentation and virtual memory

Allocating and protecting memory

Memory management organises the working memory used by the OS and running processes. A process is a running instance of a program. The OS tracks which regions are available, allocates space when a process needs it and releases space when it is no longer required. It also supports protection so a process cannot freely overwrite another process's memory.

A process uses a logical address space, the addresses through which it refers to its instructions and data. Address translation maps these to physical RAM locations. The OS maintains the mapping and protection information; processor memory-management hardware can apply it during access. Thus two processes may both use a logical address of zero without storing their data in the same physical location.

Suppose a photo editor closes. Releasing its allocation makes memory available to another application. Leaving every finished process's allocation unavailable would gradually prevent new work, even though those data are no longer needed. In a different failure, allowing an editor to write over a media player's instructions could corrupt the player's execution. Allocation and protection solve different problems: finding space and controlling access.

The mappings also allow a process's physical location to differ from the addresses it uses. Paging and segmentation organise those mappings in different ways. Neither scheme changes the meaning of a program's stored data merely by moving its physical location.

Fixed-size pages and frames

Paging divides a process's logical address space into fixed-size pages and physical RAM into equal-size frames. A page fits in any available frame of that size. The process's pages need not occupy adjacent frames, because a page table records the page-to-frame mapping.

In this example, pages and frames each hold 1,024 bytes. The process has page 0 in frame 3, page 1 in frame 0 and page 2 in frame 2. Frame 1 belongs to another process. A logical address contains a page number and an offset within that page; translation replaces the page number with the frame number and keeps the offset.

[DIAGRAM: A process's pages mapped to separate RAM frames; asset_slug: paging-map; caption: The page table preserves logical order while equal-size pages occupy nonadjacent physical frames.]

For logical byte address 1,400, one whole page fits before that address: page number 1 and offset $1{,}400 - 1{,}024 = 376$. Page 1 is in frame 0. Multiply the frame number by frame size and add the offset: the physical byte address is $0 \times 1{,}024 + 376 = 376$. The translated address need not resemble the original address, but it identifies the same requested byte through the mapping.

Fixed-size allocation can waste part of the last page. A process needing 2,800 bytes requires three 1,024-byte frames. It receives $3 \times 1{,}024 = 3{,}072$ bytes, with $3{,}072 - 2{,}800 = 272$ bytes unused inside its final allocation. This is internal fragmentation. Paging avoids needing one long contiguous free region for the whole process, although page tables and translation require resources.

Logical segments and external fragmentation

Segmentation divides a process into logical sections of variable size, such as its code, data or stack. A segment table can record each segment's physical base address, length and access permissions. In the simple model here, each individual segment occupies one contiguous region, but different segments need not be next to one another.

To access the data segment at offset 250, check that the offset is nonnegative and below its length, 600. The physical address is then $8{,}000 + 250 = 8{,}250$. Offset 650 is invalid: adding it to the base would produce a number, but it would be outside this segment. Bounds and permissions matter as well as address arithmetic. For example, a code segment can be protected against unwanted writes.

Variable sizes match the program's logical structure, but allocating and freeing them can leave scattered holes. If free holes are 300 bytes and 500 bytes, they total 800 bytes. A new 600-byte segment still cannot fit in either hole in this contiguous-per-segment model. This is external fragmentation: free space exists between allocations but cannot satisfy the required contiguous region. Compaction may gather free space, but moving allocations and updating mappings takes work.

Compare like with like. Paging uses equal-size units that can occupy separate frames and may waste space inside the final page. Segmentation uses variable-size logical units and can leave unusable gaps between allocated segments. Neither a blanket claim that all segmentation is faster nor that paging wastes no memory follows from these mechanisms.

Virtual memory and page faults

Virtual memory allows a process to use an address space whose pages need not all be resident in RAM at once. Secondary storage backs pages that are not currently in RAM. This lets a system support a working demand larger than available RAM, within its configured limits, but it does not create equally fast physical memory.

If an instruction accesses a page marked as not resident, a page fault transfers control to the OS. The OS locates the page on secondary storage and obtains a frame. If no frame is free, it selects a resident page to replace. A page that has been changed must be written back if needed to preserve its contents. An unchanged page with an existing backing copy may not need that write. The required page is read into the frame, the mapping is updated, and the interrupted access can resume. A page fault is therefore not necessarily a program error.

To trace replacement, the policy must be specified. In this teaching model there are three initially empty frames. Each named page is one page; every access completes before the next. Use FIFO replacement: evict the resident page loaded earliest. A hit does not refresh its FIFO position. Ignore transfer time and assume backing copies are already available.

There are four page faults, including the first three loads into empty frames. FIFO is an explicit trace assumption, not the definition of virtual memory and not a required universal OS policy.

RAM access is much faster than reading pages from secondary storage. Occasional transfers can be worthwhile because they allow programs to continue without fitting all pages in RAM. If the actively needed pages repeatedly exceed the resident capacity, the system may spend much of its time transferring pages rather than doing useful execution: thrashing. Adding enough RAM or reducing the working demand can reduce this problem. A larger page file alone does not remove the transfer bottleneck.

Virtual memory supports running processes; network virtual storage presents remotely held files as local. The word “virtual” in both names does not give them the same function.