Community Hub0 Subscribers
Community hub
Memory management (operating systems)
View on Wikipediafrom Wikipedia
In operating systems, memory management is the function responsible for managing the computer's primary memory.[1]:ā105ā208ā
The memory management function keeps track of the status of each memory location, either allocated or free. It determines how memory is allocated among competing processes, deciding which gets memory, when they receive it, and how much they are allowed. When memory is allocated it determines which memory locations will be assigned. It tracks when memory is freed or unallocated and updates the status.
This is distinct from application memory management, which is how a process manages the memory assigned to it by the operating system.
Memory management techniques
[edit]Single contiguous allocation
[edit]Single allocation is the simplest memory management technique. All the computer's memory, usually with the exception of a small portion reserved for the operating system, is available to a single application. MS-DOS is an example of a system that allocates memory in this way. An embedded system running a single application might also use this technique.
A system using single contiguous allocation may still multitask by swapping the contents of memory to switch among users. Early versions of the MUSIC operating system used this technique.
Partitioned allocation
[edit]Partitioned allocation divides primary memory into multiple memory partitions, usually contiguous areas of memory. Each partition might contain all the information for a specific job or task. Memory management consists of allocating a partition to a job when it starts and unallocating it when the job ends.
Partitioned allocation usually requires some hardware support to prevent the jobs from interfering with one another or with the operating system. The IBM System/360 uses a lock-and-key technique. The UNIVAC 1108, PDP-6 and PDP-10, and GE-600 series use base and bounds registers to indicate the ranges of accessible memory.
Partitions may be either static, that is defined at Initial Program Load (IPL) or boot time, or by the computer operator, or dynamic, that is, automatically created for a specific job. IBM System/360 Operating System Multiprogramming with a Fixed Number of Tasks (MFT) is an example of static partitioning, and Multiprogramming with a Variable Number of Tasks (MVT) is an example of dynamic. MVT and successors use the term region to distinguish dynamic partitions from static ones in other systems.[2]
Partitions may be relocatable with base registers, as in the UNIVAC 1108, PDP-6 and PDP-10, and GE-600 series. Relocatable partitions are able to be compacted to provide larger chunks of contiguous physical memory. Compaction moves "in-use" areas of memory to eliminate "holes" or unused areas of memory caused by process termination in order to create larger contiguous free areas.[3]
Some systems allow partitions to be swapped out to secondary storage to free additional memory. Early versions of IBM's Time Sharing Option (TSO) swapped users in and out of time-sharing partitions.[4][a]
Paged memory management
[edit]Paged allocation divides the computer's primary memory into fixed-size units called page frames, and the program's virtual address space into pages of the same size. The hardware memory management unit maps pages to frames. The physical memory can be allocated on a page basis while the address space appears contiguous.
Usually, with paged memory management, each job runs in its own address space. However, there are some single address space operating systems that run all processes within a single address space, such as IBM i, which runs all processes within a large address space, and IBM OS/VS1 and OS/VS2 (SVS), which ran all jobs in a single 16MiB virtual address space.
Paged memory can be demand-paged when the system can move pages as required between primary and secondary memory.
Segmented memory management
[edit]Segmented memory is the only memory management technique that does not provide the user's program with a "linear and contiguous address space."[1]:ā165ā Segments are areas of memory that usually correspond to a logical grouping of information such as a code procedure or a data array. Segments require hardware support in the form of a segment table which usually contains the physical address of the segment in memory, its size, and other data such as access protection bits and status (swapped in, swapped out, etc.)
Segmentation allows better access protection than other schemes because memory references are relative to a specific segment and the hardware will not permit the application to reference memory not defined for that segment.
It is possible to implement segmentation with or without paging. Without paging support the segment is the physical unit swapped in and out of memory if required. With paging support the pages are usually the unit of swapping and segmentation only adds an additional level of security.
Addresses in a segmented system usually consist of the segment id and an offset relative to the segment base address, defined to be offset zero.
The Intel IA-32 (x86) architecture allows a process to have up to 16,383 segments of up to 4GiB each. IA-32 segments are subdivisions of the computer's linear address space, the virtual address space provided by the paging hardware.[5]
The Multics operating system is probably the best known system implementing segmented memory. Multics segments are subdivisions of the computer's physical memory of up to 256 pages, each page being 1K 36-bit words in size, resulting in a maximum segment size of 1MiB (with 9-bit bytes, as used in Multics). A process could have up to 4046 segments.[6]
Rollout/rollin
[edit]Rollout/rollin (RO/RI) is a computer operating system memory management technique where the entire non-shared code and data of a running program is swapped out to auxiliary memory (disk or drum) to free main storage for another task. Programs may be rolled out "by demand end or...when waiting for some long event."[7] Rollout/rollin was commonly used in time-sharing systems,[8] where the user's "think time" was relatively long compared to the time to do the swap.
Unlike virtual storageāpaging or segmentation, rollout/rollin does not require any special memory management hardware; however, unless the system has relocation hardware such as a memory map or base and bounds registers, the program must be rolled back in to its original memory locations. Rollout/rollin has been largely superseded by virtual memory.
Rollout/rollin was an optional feature of OS/360 Multiprogramming with a Variable number of Tasks (MVT)
Rollout/rollin allows the temporary, dynamic expansion of a particular job beyond its originally specified region. When a job needs more space, rollout/rollin attempts to obtain unassigned storage for the job's use. If there is no such unassigned storage, another job is rolled outāi.e., is transferred to auxiliary storageāso that its region may be used by the first job. When released by the first job, this additional storage is again available, either (1) as unassigned storage, if that was its source, or (2) to receive the job to be transferred back into main storage (rolled in).[9]
In OS/360, rollout/rollin was used only for batch jobs, and rollin does not occur until the jobstep borrowing the region terminates.
See also
[edit]Notes
[edit]- ^ Known as TSO regions
References
[edit]- ^ a b Madnick, Stuart; Donovan, John (1974). Operating Systems. McGraw-Hill Book Company. ISBN 0-07-039455-5.
- ^ IBM Corporation (1970). IBM System/360 Operating System: Concepts and Facilities (PDF). p. 73.
- ^ Samanta, D. (2004). Classic Data Structures. PHI Learning Pvt. Ltd. p. 94. ISBN 8120318749.
- ^ IBM Corporation (1972). IBM System/360 Operating System Time Sharing Option Guide (PDF). p. 10.(GC28-6698-5)
- ^ Intel Corporation. IA-32 Intel Architecture Software Developer's Manual Volume 1: Basic Architecture.
- ^ Green, Paul. "Multics Virtual Memory ā Tutorial and Reflections". Archived from the original on 2001-03-05. Retrieved May 9, 2012.
- ^ Walraet, Bob (2014). Programming, The Impossible Challenge. Elsevier. p. 124. ISBN 978-0-444-87128-2. Retrieved Aug 24, 2018.
- ^ "rollin/rollout" International Symposium on Computer Performance Modeling, Measurement, and Evaluation. Association for Computing Machinery. March 29ā31, 1976. p. 137. Retrieved Aug 24, 2018.
- ^ IBM Corporation (June 1970). IBM System/360 Operating System: .Concepts and Facilities (PDF). p. 55. Retrieved Aug 24, 2018.
| Hardware |
|
|---|---|
| Virtual memory | |
| Segmentation | |
| Allocator | |
| Manual means | |
| Garbage collection | |
| Safety | |
| Issues | |
| Other | |
Memory management (operating systems)
View on Grokipediafrom Grokipedia
Basic Concepts
Address Spaces
In operating systems, the logical address space, also known as the virtual address space, represents the range of addresses that a process perceives as its available memory during execution. This abstraction is generated by the CPU as the process runs, allowing programs to operate without knowledge of the actual physical memory layout. The logical address space provides isolation and simplifies programming by presenting a contiguous, process-specific view of memory, independent of other processes or the underlying hardware configuration.[6][7] The physical address space, in contrast, corresponds to the actual locations in the system's random-access memory (RAM), where data and instructions are stored and retrieved by the hardware. Mapping from logical to physical addresses occurs to translate the process's view into real hardware accesses, ensuring that multiple processes can share the same physical memory without interference. This separation enables efficient resource utilization while maintaining security through address isolation.[8][9] Address binding determines when instructions and data are associated with specific memory locations, occurring at three primary stages: compile time, load time, or execution time. At compile time, if the exact memory location is known in advance, absolute code is produced with fixed physical addresses, suitable for embedded systems or OS kernels where relocation is unnecessary. However, for flexibility in multiprogrammed environments, relocatable code is generated, where addresses are symbolic offsets that can be adjusted later. Load-time binding resolves these offsets to physical addresses when the program is loaded into memory, assuming a fixed location post-loading. Execution-time binding, used in dynamic systems, postpones this until runtime, allowing processes to relocate during execution via hardware support like base registers, which is essential for swapping and virtual memory.[10][11][7] In multiprogramming, each process is assigned its own logical address space, typically starting from address zero, to provide isolation from other processes and the operating system kernel. This per-process namespace prevents one program from accessing or corrupting another's memory, enhancing security and stability in shared environments. The operating system manages these spaces, ensuring that logical addresses map uniquely to physical ones without overlap, supporting concurrent execution of multiple programs.[12][13] Historically, early operating systems from the 1950s and early 1960s relied solely on physical addressing, where programs directly referenced actual RAM locations without abstraction. This approach, common in single-user batch systems, limited multiprogramming because manual memory management led to inefficiencies, such as idle CPU time during I/O and challenges in protecting or relocating code. The introduction of logical address spaces in systems like the THE multiprogramming system in the 1960s marked a pivotal evolution, enabling better resource sharing and isolation to overcome these constraints.[14][15]Memory Hierarchy
The memory hierarchy in operating systems organizes storage into multiple levels, each differing in speed, capacity, volatility, and cost, to optimize performance while managing economic constraints. At the top are CPU registers, providing the fastest access at sub-nanosecond latencies but with minimal capacity (typically tens to hundreds of bytes per core). These are followed by on-chip caches, including L1 (split instruction and data caches, 16-64 KB per core, 1-4 cycles or ~0.25-1 ns access), L2 (256 KB-2 MB per core, 10-20 cycles or ~2.5-5 ns), and L3 (shared 8-64 MB, 30-50 cycles or ~7.5-12.5 ns), all implemented in static RAM (SRAM) for low latency but high cost (approximately 100 times that of dynamic RAM per bit). Main memory, or RAM, uses dynamic RAM (DRAM) with capacities of 8-128 GB in modern systems, access times of 10-100 ns, and costs around $5 per GB. Secondary storage includes hard disk drives (HDDs) with 1-20 TB capacities, seek times of 5-10 ms, and costs of ~$0.015 per GB, alongside solid-state drives (SSDs) offering 1-8 TB, read latencies of 10-100 Āµs, and costs of| Level | Technology | Typical Capacity | Access Time | Cost per GB (approx., 2025) |
|---|---|---|---|---|
| Registers | Flip-flops | Bytes to KB | <1 ns | N/A (integrated) |
| L1 Cache | SRAM | 16-64 KB/core | 0.25-1 ns | ~$1000+ (effective) |
| L2 Cache | SRAM | 256 KB-2 MB/core | 2.5-5 ns | ~$100+ (effective) |
| L3 Cache | SRAM | 8-64 MB (shared) | 7.5-12.5 ns | ~$50+ (effective) |
| Main Memory (RAM) | DRAM | 8-128 GB | 10-100 ns | $5 |
| Secondary (SSD) | NAND Flash | 1-8 TB | 10-100 Āµs | $0.05 |
| Secondary (HDD) | Magnetic | 1-20 TB | 5-10 ms | $0.015 |
| Tertiary (Tape) | Magnetic | Up to PB | Seconds-minutes | $0.005 |
Contiguous Allocation Techniques
Single Contiguous Allocation
Single contiguous allocation represents the simplest form of memory management in operating systems, where the operating system dedicates the entire available physical memory, excluding a small portion reserved for the OS itself, to a single process at a time.[2] This approach, characteristic of monoprogramming environments, involves loading the process into a continuous block of memory at load time, with address binding performed using basic hardware registers such as a base register (to handle relocation) and a limit register (to enforce bounds checking and protection).[21] Predominant in first-generation operating systems from the 1940s to 1950s, which relied on vacuum tubes and manual operation without true multitasking, it persisted into second-generation batch systems of the 1950s and 1960s on transistor-based mainframes.[21] The mechanism's simplicity stems from the absence of complex partitioning or sharing, allowing the OS to treat memory as one large block for the active program, which executes until completion before the next is loaded.[22] In systems like the Primary Control Program (PCP) variant of IBM OS/360, introduced in 1964 for mainframes, this enabled sequential job step execution without partitioning, suiting early batch processing on 1960s hardware.[23] Advantages of single contiguous allocation include minimal runtime overhead, as no additional mapping or fragmentation occurs within the allocated block, facilitating straightforward implementation and efficient execution in resource-constrained environments.[2] It provides basic relocation and protection through the base and limit registers, ensuring the process cannot access memory outside its bounds, and supports high I/O performance since data access involves a single contiguous seek.[21] This made it ideal for batch systems on 1960s mainframes, where jobs were processed non-interactively, and for monoprogramming setups like early personal computers.[24] However, the technique's limitations become evident in its inefficiency for multiprogramming, as only one program can run at a time, leaving the CPU idle during I/O operations and preventing concurrent execution.[25] Relocation demands hardware support via the base register, and without it, programs must be linked for absolute addresses, restricting flexibility.[22] An example is a monoprogramming environment where the OS loads a single batch job into memory, executes it to completionāsuch as a scientific computation on an IBM 7090āand then terminates it before loading the next, a common practice in pre-1970 systems now largely obsolete outside specialized embedded applications.[21] This paved the way for partitioned allocation methods to enable multiprogramming.[23]Partitioned Allocation
Partitioned allocation is a contiguous memory management technique that divides physical memory into multiple partitions, each capable of holding a single process, to enable multiprogramming and improve CPU utilization by allowing concurrent execution of several programs. This approach contrasts with single contiguous allocation by supporting multiple processes simultaneously, though it introduces challenges related to fragmentation. Partitions are typically managed by the operating system kernel, which tracks allocation status and enforces boundaries using hardware relocation registers for address translation.[24] In fixed partitioning, also known as static partitioning, physical memory is divided into a set of non-overlapping regions of predetermined sizesāeither equal or unequalāestablished at system initialization or boot time. Each partition can accommodate at most one process at a time, with the operating system assigning incoming processes to suitable partitions based on size compatibility; processes larger than the largest partition may require overlays or rejection. This scheme suffers from internal fragmentation, where unused space within an allocated partition is wasted because processes cannot span multiple partitions, leading to inefficiency when a process occupies less memory than the partition's capacityāfor instance, a 20 KB process in a 32 KB partition wastes 12 KB. To mitigate uneven utilization, unequal partitioning assigns smaller processes to smaller partitions, reducing average waste compared to equal-sized ones.[26][27][24] Variable partitioning, or dynamic partitioning, addresses the rigidity of fixed schemes by creating partitions on demand, sized precisely to fit each incoming process's memory requirements, allowing for more flexible utilization of available space. As processes terminate, their partitions become free, but this leads to external fragmentation, where scattered "holes" of unused memory accumulate between allocated partitions, potentially preventing allocation of larger processes despite sufficient total free space. Compaction is employed to resolve external fragmentation by relocating active processes to consolidate free holes into a single contiguous block; this process is computationally expensive, often requiring O(n) time proportional to the number of words in memory, as it involves moving entire partitions and updating relocation information. Partial compaction, which only merges adjacent holes, is less costly but less effective. Free space in variable partitioning is commonly managed using bitmaps, where each bit represents the status of a memory unit (free or allocated), or linked lists that chain free blocks for quick traversal.[27][26][24] Process allocation in partitioned schemes, particularly variable partitioning, relies on heuristic algorithms to select free holes: first-fit scans the list of holes from the beginning and allocates the first sufficiently large one, achieving average O(n) time complexity where n is the number of holes; best-fit searches the entire list to find the smallest fitting hole, minimizing wasted space but increasing search time to O(n); worst-fit selects the largest available hole to leave larger remnants for future allocations, also O(n) but often performing worse in simulations due to excessive fragmentation. These algorithms balance allocation speed and memory efficiency, with first-fit generally favored for its lower average overhead. Internal fragmentation persists in both fixed and variable schemes within allocated blocks, while external fragmentation is unique to variable partitioning and necessitates periodic compaction.[26][27][7] Historically, partitioned allocation was prevalent in 1960s and 1970s mainframe systems; for example, IBM's OS/360 Multiprogramming with a Fixed number of Tasks (MFT) used fixed partitions defined at system generation, with up to 15 concurrent jobs limited by partition sizes starting from 8 KB, while Multiprogramming with a Variable number of Tasks (MVT) employed dynamic regions adjustable via job parameters for better adaptability. These approaches laid groundwork for later non-contiguous techniques but were largely superseded due to fragmentation overhead.[24][23]Non-Contiguous Allocation Techniques
Paging
Paging is a memory management technique that enables non-contiguous allocation by dividing the logical address space of a process into fixed-size units called pages and the physical memory into corresponding units called frames or page frames.[28] Typically, pages are 4 KB in size, allowing the operating system to map pages to any available frames without regard to contiguity.[28] A per-process page table serves as the mapping structure, where each entry associates a virtual page number with a physical frame number.[28] Address translation in paging splits a logical address into a page number and a page offset. The page number is obtained by shifting the logical address right by the number of offset bits (e.g., 12 bits for 4 KB pages), and the offset is the least significant bits. The physical address is then computed as the frame number (from the page table) shifted left by the offset bits, plus the offset:
[28]
The page table is an array of page table entries (PTEs), one per virtual page, containing the frame number, a valid bit (indicating if the page is in memory), and protection bits (e.g., read/write permissions).[28] For large address spaces, such as 32-bit systems with 4 KB pages, a single-level page table can be enormous (e.g., 4 MB for 1 million entries of 4 bytes each), so multi-level page tables are used to reduce overhead.[29] In a two-level scheme for 32-bit addresses, the outer page directory indexes into inner page tables, allocating only tables for used address regions, thus supporting sparse spaces efficiently.[29]
Paging eliminates external fragmentation since pages can be placed in any frames, but it introduces internal fragmentation limited to the unused portion of the last page, which is less than one full page size.[28] It also facilitates efficient swapping of individual pages and sharing of pages, such as read-only code pages among processes running the same executable.[28]
In implementation, the operating system dynamically allocates physical frames from a free list or buddy system as pages are needed.[28] Paging was first introduced in the Atlas computer in 1962, using 512-word pages and page address registers for mapping, treating core memory and drum storage as a unified address space to avoid fragmentation.[30] It became widespread in Unix-like systems during the late 1970s, with paging and virtual memory introduced in 3BSD in 1979, enhancing support for multi-programming and shared code segments.[31]
Segmentation
Segmentation is a non-contiguous memory allocation technique in operating systems that divides a process's logical address space into variable-sized segments, each corresponding to a logical module of the program such as the code segment, data segment, or stack.[32] This approach allows segments to be of different lengths to better match the natural structure of programs, unlike fixed-size paging.[33] Introduced in the Multics operating system around 1969, segmentation enables direct addressing of program components while facilitating modularity.[34] In the segmentation mechanism, the operating system maintains a segment table for each process, where each entry specifies the physical base address of the segment and its length (limit).[32] A logical address consists of two parts: a segment number identifying the segment and an offset within that segment.[35] During address translation, the hardware first checks if the offset is less than the segment's limit; if valid, the physical address is computed as the base address plus the offset.[32] This mapping is performed by the memory management unit, ensuring that segments can be placed non-contiguously in physical memory.[36] One key advantage of segmentation is its alignment with program structure, allowing developers to treat segments as independent units for easier code organization and maintenance.[35] It also supports efficient sharing of segments, such as shared libraries or code modules between processes, by mapping multiple processes to the same physical segment.[33] Additionally, protection can be applied per segment, enabling fine-grained access controls like read-only for code segments.[32] However, segmentation suffers from external fragmentation, similar to variable partitioning, where free memory becomes scattered in small holes that cannot accommodate new segments despite sufficient total free space.[35] To mitigate this, many systems combine segmentation with paging in hybrid approaches; for example, the x86 architecture uses segments divided into fixed-size pages for address translation.[36] Historically, segmentation originated in the Multics system developed by MIT, Bell Labs, and General Electric starting in 1965, with the first operational version in 1969 on the GE-645 computer.[34] It influenced subsequent architectures, including the PDP-11 minicomputers from Digital Equipment Corporation in 1970, which incorporated segmentation in their memory management units to support up to eight segments per process.[36] The PDP-11's design, in turn, inspired the Intel 8086 microprocessor in 1978, which adopted a segmented memory model to expand addressing beyond 64 KB.[37] Today, pure segmentation is less common, overshadowed by paging's simplicity and lack of external fragmentation in modern operating systems that favor flat address spaces.[35]Virtual Memory Management
Demand Paging
Demand paging is a core mechanism in virtual memory systems that enables the logical address space of a process to exceed the available physical memory by loading pages from secondary storage into main memory only upon their first access, a process known as demand loading or lazy loading. This approach, building on basic paging where memory is divided into fixed-size pages, avoids the need to preload the entire address space at process startup, thereby reducing initial memory allocation overhead and startup time while allowing larger programs to execute than would fit in physical RAM alone. Pages initially reside on disk, and the operating system maintains a page table to map virtual pages to physical frames or indicate their absence in memory.[38] When a process attempts to access a page not present in physical memory, a page fault occurs, triggering an interrupt that transfers control to the operating system kernel. The OS then handles the fault by first validating the address and checking for protection violations; if valid, it allocates a free physical frame from the available pool, schedules disk I/O to load the page from its backing store into the frame, updates the page table entry with the new mapping, and resumes the process from the faulting instruction. Page faults are classified as minor if they involve only in-memory operations like updating tables without disk access, or major if they require disk I/O, which introduces significant latency due to mechanical seek times and transfer rates. This fault handling ensures transparent virtualization, making the process unaware of the paging mechanism.[39] The performance of demand paging is quantified by the effective access time (EAT), which accounts for the probability of page faults and their overhead:
where $ p $ is the page fault probability, $ t_m $ is the memory access time, and $ t_f $ is the total page fault service time including disk I/O, context switching, and scheduling delays. Disk I/O typically dominates $ t_f $, often by orders of magnitude compared to $ t_m $ (e.g., milliseconds versus nanoseconds), so minimizing $ p $ through techniques like prepaging is critical to maintaining acceptable system throughput. Even low fault rates, such as 0.001, can degrade performance substantially if $ t_f $ is high.[40]
In demand paging, the backing store serves as the persistent repository for page images on disk, typically a dedicated swap area or partition formatted for efficient random access, where pages are written when evicted from memory to free frames. This swap area holds unmodified code pages as well as modified data pages, ensuring the full virtual address space can be reconstructed if needed. For efficiency in Unix-like systems, copy-on-write (COW) is employed during process creation via fork(), where parent and child initially share physical pages with read-only mappings; modifications trigger private copies, avoiding unnecessary duplication and conserving memory.[41][42]
Demand paging was pioneered in the THE multiprogramming system developed by Edsger W. Dijkstra and colleagues in 1968, which implemented one of the earliest software-based paged virtual memory schemes to support multiprogramming on limited hardware. This concept became a standard feature in modern operating systems, including Linux, where demand paging has been integral to the kernel since its initial 0.01 release in 1991, enabling efficient resource sharing across diverse workloads.[43][44]
Swapping and Overlaying
Swapping is a memory management technique in operating systems that enables multiprogramming when physical memory is limited by moving an entire process's memory image between main memory and a dedicated disk area known as swap space. To free memory, the operating system suspends a low-priority or inactive process by writing its full imageāincluding code, data, and stackāto disk (swap out), then loads a higher-priority process from disk into the vacated space (swap in). This coarse-grained approach was essential in early time-sharing systems to support multiple concurrent users without excessive memory requirements.[45] In the context of process scheduling, the medium-term scheduler oversees swapping decisions, evaluating factors like process priority, CPU utilization, and memory pressure to determine which processes to suspend or resume. Swapped-out processes are placed on a suspend queue, awaiting re-entry into memory when conditions allow, such as when a running process terminates or another is swapped out. This mechanism contrasts with finer-grained paging by handling entire processes at once, avoiding partial loads but introducing delays from full-image transfers. Early implementations, like those in Unix on PDP-11 systems, relied on fixed-head disks for these operations, with higher-priority processes preempting lower ones in core memory.[46][45] Swapping facilitates greater degrees of multiprogramming by allowing the system to accommodate more processes than physical memory can hold simultaneously, thereby improving CPU utilization in multitasking environments. However, its primary disadvantage is the substantial I/O overhead from disk accesses, which can cause significant latencyāoften orders of magnitude slower than memory operationsāand lead to thrashing if swapping frequency becomes too high. While integral to 1970s Unix systems for handling memory constraints on limited hardware, swapping persists in modern operating systems like Linux and Windows as a fallback for extreme memory pressure, though virtual memory techniques have largely supplanted it for routine use.[46][45] Overlaying provides a manual method for executing programs exceeding available physical memory by partitioning the code into hierarchical modules, or overlays, and loading only the active portions sequentially into the same memory region. The programmer designates a core "root" segment that remains resident, alongside non-overlapping modules loaded on demandāsuch as replacing a calculation routine with an output moduleāmanaged by an overlay driver or linker that tracks dependencies and triggers loads via explicit calls. This technique requires no special hardware support and was common in batch processing systems where program execution followed predictable phases.[45] Historically, overlaying saw widespread use in memory-constrained environments, including 1950s-1960s mainframes like the IBM 704 and later in MS-DOS applications during the 1980s, where developers structured large programs to fit within 640 KB limits by overlaying infrequently used sections. Its key advantage lies in memory efficiency, enabling execution of oversized programs without expanding hardware, but it demands intricate manual design, increasing development complexity and susceptibility to errors in module interdependencies. Overlaying became obsolete with the rise of virtual memory in the 1970s, which automates similar functionality transparently; remnants appear today in resource-limited embedded systems, where manual module management aids in optimizing scarce RAM.[45]Hardware Support
Memory Management Unit
The Memory Management Unit (MMU) is a hardware component integrated into the central processing unit (CPU) that handles the translation of virtual or logical addresses generated by software into corresponding physical addresses in the system's main memory. This translation supports various memory management techniques, including contiguous allocation via base and limit registers as well as non-contiguous methods using page or segment tables. In contiguous modes, the MMU employs base registers to offset the starting physical address of a process's memory block and limit registers to enforce boundary checks, preventing access beyond allocated regions. For non-contiguous allocation, it walks through page or segment tablesādata structures maintained by the operating systemāto map scattered physical frames to a continuous virtual space.[47][48] Key components of the MMU include translation logic for address mapping, an interface to the Translation Lookaside Buffer (TLB) for caching translations, and mechanisms for protection checks such as read, write, and execute permission bits in table entries. These permission bits determine allowable operations on memory regions, with the MMU enforcing separation between kernel and user modes to restrict privileged access. For instance, user-mode processes are typically barred from executing kernel code or writing to protected areas, ensuring system stability. The MMU also validates address ranges against table entries, supporting both single-level and multi-level table walks for complex address spaces.[49][50] During operation, the MMU intervenes on every memory access initiated by the CPU: it first checks the virtual address against current mode and permissions, then performs translation using cached TLB entries or by fetching table data from memory. If the translation is valid and permissions allow, the physical address is generated for memory access; otherwise, the MMU triggers a page fault or protection violation exception, handing control to the operating system for handling, such as loading a page from disk. This process ensures efficient and secure memory utilization without software overhead for each access. In the context of paging, the MMU references page table structures briefly to resolve virtual page numbers to physical frames, though detailed table formats are managed separately.[51][47] The evolution of MMUs traces back to the 1960s with early implementations in systems like the DEC PDP-8, where optional units such as the Type 183 Memory Extension Controller provided basic relocation and bank switching using 12-bit virtual addresses mapped to larger physical memory. Modern MMUs, such as those in ARMv8 architectures introduced in the 2010s, support advanced features like 4KB page granules and 48-bit virtual address spaces, enabling vast memory mappings up to 256 terabytes. The operating system interacts closely with the MMU by populating and updating translation tables in memory; during context switching between processes, the OS reloads MMU control registersāsuch as the x86 CR3 register pointing to the page directory baseāto activate the new address space, invalidating prior translations as needed.[52][53][50]Translation Lookaside Buffer
The Translation Lookaside Buffer (TLB) serves as a high-speed cache within the memory management unit (MMU) to store recent virtual-to-physical address translations, thereby reducing the latency associated with accessing page tables during memory operations.[54] By caching mappings for frequently used pages, the TLB enables faster address resolution, exploiting spatial and temporal locality in program execution to minimize the overhead of full page table lookups.[54] Structurally, the TLB is a small, fully associative or set-associative array typically comprising 64 to 1024 entries, each holding a virtual page number (VPN), corresponding physical frame number (PFN), and control flags such as valid, protection, dirty, and reference bits.[54][55] In modern processors like the Intel Core series from the 2000s onward, TLBs often employ multi-level hierarchies, with separate instruction TLBs (ITLBs) and data TLBs (DTLBs); for example, the Intel Core i7 features a 64-entry 4-way set-associative L1 DTLB and a 512-entry 4-way L2 unified TLB per core.[55] These designs use replacement policies like least recently used (LRU) to manage entries, ensuring that active translations remain readily available.[54] In operation, every virtual address translation begins with a parallel lookup in the TLB using the VPN portion of the address. On a hit, the cached PFN combines with the page offset to yield the physical address in approximately 1 clock cycle, bypassing slower memory accesses.[54] A miss triggers a page table walk by hardware or software, fetching the translation from the page table and inserting it into the TLB, potentially evicting an existing entry; the operating system manages insertions in software-managed TLBs via privileged instructions.[54] Context switches typically require TLB flushing to prevent stale entries, though address space identifiers (ASIDs) can tag entries to avoid full invalidations and maintain performance across processes.[54] The performance benefits of the TLB are substantial, as a hit avoids the multi-level page table traversal that can consume 10 to 100 cycles or more, depending on cache residency and hierarchy depth; for instance, some workloads incur up to 135 cycles per data TLB miss.[56] Miss rates remain low, often below 1%, due to locality principles, yielding effective translation speeds that approach direct physical addressing in well-behaved applications.[54] Operating systems handle TLB misses through page fault handlers, which resolve the translation and update the TLB, integrating with broader virtual memory mechanisms.[54] In multiprocessor systems, maintaining TLB coherence poses challenges, as updates to shared page tables require invalidating remote TLB entries to prevent inconsistencies; this "TLB shootdown" process involves the updating processor interrupting others to flush specific mappings, incurring overheads of tens to hundreds of microseconds per operation.[57] Additionally, the limited size of TLBs constrains their coverage of large address spaces, prompting hybrid approaches that combine paging with segmentation or superpages to enhance effective reach without proportional increases in TLB capacity.[58]Protection and Sharing
Memory Protection Mechanisms
Memory protection mechanisms in operating systems ensure that processes operate within isolated address spaces, preventing unauthorized access to memory regions belonging to other processes or the kernel, thereby maintaining system stability and security. These mechanisms rely on hardware support from the memory management unit (MMU) to enforce boundaries during address translation. At the core are base techniques embedded in page or segment tables, where each entry includes a valid/invalid bit to indicate whether a virtual page maps to physical memory; an invalid bit triggers a page fault if accessed, allowing the OS to handle out-of-bounds or unmapped references. Additionally, protection bits specify granular permissions such as read, write, or execute for each page or segment, denying operations that violate these rules and generating protection faults to isolate errant processes.[59] Kernel and user modes provide a foundational layer of protection by partitioning execution privileges. In user mode, processes are restricted from executing privileged instructionsāsuch as those modifying hardware state or accessing kernel memoryāwhich are reserved for kernel mode to prevent direct manipulation of system resources. This separation is enforced through protection rings in architectures like x86, which define four hierarchical levels (rings 0 to 3), with ring 0 granting full privileges to the kernel and ring 3 limiting user processes to non-privileged operations; attempts to execute privileged instructions from lower rings result in general protection exceptions. To further thwart exploits like buffer overflows that target predictable memory layouts, address space layout randomization (ASLR) randomizes the base addresses of key regions such as the stack, heap, and libraries at process load time, making it harder for attackers to predict targets; ASLR was first introduced in OpenBSD in 2003 and became widespread in Linux and Windows by the late 2000s.[50][60] Formal models like capabilities and access matrices offer theoretical frameworks for implementing protection, though full realizations are rare in modern systems. Capabilities act as unforgeable tokens granting specific rights (e.g., read or write) to objects, stored in protected memory and checked by hardware or the OS during access, as detailed in Saltzer and Schroeder's seminal work on descriptor-based systems. The access matrix model, proposed by Lampson, represents protection as a table where rows denote subjects (e.g., processes) and columns denote objects (e.g., memory segments), with entries specifying allowed operations; this abstracts policy from mechanism, enabling implementations via capabilities (row-based) or access control lists (column-based). Violations of these protections, such as invalid accesses, are handled via traps or exceptions that interrupt execution and transfer control to the OS kernel for resolution, potentially terminating the offending process. For safe sharing during operations like process forking, copy-on-write (COW) marks shared pages as read-only initially; a write attempt triggers a page fault, prompting the OS to duplicate the page and update mappings, thus preserving isolation without immediate full copying.[61][62][63]Inter-Process Memory Sharing
Inter-process memory sharing enables multiple processes to access the same physical memory regions, facilitating efficient inter-process communication (IPC) and resource utilization while maintaining isolation through operating system mechanisms. This technique is particularly useful for reducing memory duplication and enabling fast data exchange between cooperating processes. In modern operating systems, shared memory is implemented via standardized APIs that allow controlled access to common buffers or objects.[64] Key methods for inter-process memory sharing include memory-mapped files and dedicated shared memory segments. In POSIX-compliant systems, themmap() function establishes a mapping between a process's virtual address space and a file, shared memory object, or typed memory object, with the MAP_SHARED flag enabling modifications to be visible to all processes mapping the same object, while MAP_PRIVATE provides copy-on-write semantics for isolated views.[64] System V IPC, an older but widely supported mechanism, uses shmget() to create or obtain a shared memory segment identifier based on a key, followed by shmat() to attach it to the process's address space, allowing multiple processes to reference the same segment.[65] These approaches differ in that mapped files integrate with the file system for persistence, whereas System V segments are anonymous and managed via kernel identifiers.[64][66]
Synchronization is essential to prevent race conditions when multiple processes access shared data concurrently. POSIX semaphores, defined in the <semaphore.h> header, provide a robust mechanism for this, where named semaphores (created via sem_open()) or unnamed semaphores (placed within shared memory regions) enforce mutual exclusion or signaling; for inter-process use, unnamed semaphores must reside in shared memory to ensure visibility across address spaces.[67] Mutexes from POSIX threads (pthreads) can also be used if adapted for shared memory, but semaphores are preferred for their lightweight counting capabilities in producer-consumer scenarios. Proper synchronization avoids data corruption by ensuring atomic operations on critical sections within the shared region.[67]
Common use cases include IPC through shared buffers, where processes exchange data directly without kernel mediation, offering lower latency than message passing.[68] Another prominent application is dynamic linking of shared libraries, as in Linux's ELF format, where the dynamic linker (ld.so) maps library code and data into multiple processes' address spaces, allowing code reuse and reducing overall memory footprint; for instance, standard C libraries like libc are loaded once and shared across applications.[69][70]
Security in inter-process memory sharing relies on reference counting to manage deallocation safely. In POSIX shared memory, objects created via shm_open() persist until all file descriptors are closed and mappings (via munmap()) are removed, with the kernel maintaining an internal reference count; shm_unlink() removes the name but does not deallocate until references reach zero, preventing premature freeing.[71] This mechanism, combined with ownership models enforced by the API (e.g., explicit attachment and detachment), mitigates risks like dangling pointers by ensuring shared regions are not accessed after deallocation, though user-level synchronization is still required to avoid invalid references.
Modern examples highlight the scalability of shared memory in parallel and containerized environments. In containerization, Linux namespaces, particularly the IPC namespace introduced in kernel version 2.6.19, isolate shared memory segments, semaphores, and message queues; however, tools like Docker (since its 2013 release) allow controlled sharing by configuring containers to join the host's IPC namespace (e.g., via --ipc=host), enabling efficient communication in multi-container setups while preserving isolation for unshared resources.