1 Fundamentals of paging
Paging is a memory-management method that divides a program’s address space into equal-sized units and matches them with similarly sized units in physical memory. This design reduces the need for contiguous allocation, making it easier for an operating system to place data where space is available. It also provides a foundation for virtual memory, in which a program can use an address range larger than the RAM installed in the machine.
1.1 Memory management concepts
Operating systems must decide where to store code, data, stacks, and shared resources while many programs run at once. Paging addresses this challenge by separating the logical view of memory from its physical location. Instead of requiring a program to fit into one continuous block, the system manages smaller pieces individually, which improves flexibility and helps reduce wasted space.
1.2 Pages and frames
A page is a fixed-size block of a process’s virtual memory, while a frame is a block of the same size in physical memory. Because the units match, any page can be loaded into any free frame. This uniformity simplifies allocation and makes it possible to move pages in and out of RAM without changing the program’s view of memory.
1.3 Page tables
A page table records which physical frame currently holds each virtual page. When a program accesses memory, the system consults this table to find the corresponding location in RAM or determine that the page is absent. Page tables are central to paging because they maintain the mapping between the virtual and physical address spaces.
1.3.1 Page table entries
Each page table entry typically stores a frame number along with status information such as whether the page is present, modified, or allowed to be read and written. Additional bits may record whether the page has been accessed recently or whether it is reserved for special use. These fields allow the operating system and hardware to manage memory efficiently and safely.
1.3.2 Address translation
Address translation converts a virtual address into a physical address by separating the page number from the offset within the page. The page number identifies the relevant entry in the page table, and the offset is carried unchanged into the resulting physical address. This translation may occur in hardware, software, or a combination of both, depending on the architecture.
1.4 Virtual memory
Virtual memory gives each process the illusion of a large, private memory space that is independent of the amount of installed RAM. Only the needed pages must remain in physical memory at any given time, while the rest can stay on secondary storage. This approach supports larger programs, better multitasking, and stronger isolation between processes.
2 Paging in operating systems
Modern operating systems use paging as a core mechanism for allocation, protection, and sharing. By organizing memory around pages, the kernel can control which parts of a process are resident, which are shared, and how access is regulated. Paging also helps the system recover from shortages of physical memory by moving less-used pages out of RAM.
2.1 Role of the operating system
The operating system creates and maintains the data structures needed for paging, including page tables and bookkeeping for free frames. It decides when pages should be loaded, evicted, or shared among processes. In addition, it handles exceptions that arise when a process accesses memory that is not currently available.
2.2 Process address spaces
Each process is usually given its own address space, which lets it use memory without interfering with other programs. The same virtual address can refer to different physical locations in different processes, because each has its own page tables. This abstraction makes programs easier to write and helps the system manage memory more predictably.
2.3 Memory protection and isolation
Paging supports protection by allowing the system to mark pages as readable, writable, executable, or inaccessible. If a process attempts an illegal access, the hardware raises an exception and the operating system intervenes. This mechanism limits accidental corruption and helps contain faults within the offending process.
2.4 Shared pages
Some pages may be mapped into more than one process, such as shared libraries or other common data regions. Shared pages save memory because a single physical copy can serve multiple address spaces. The system can still preserve protection by assigning different access rights to each mapping as needed.
3 Address translation process
Address translation is the procedure that turns a program’s virtual memory reference into a usable physical address. Because this operation happens frequently, systems are designed to perform it quickly. Hardware support is important, as even a small delay on each access can significantly affect performance.
3.1 Logical addresses
A logical address, often called a virtual address, is the address generated by a program. It refers to a location in the process’s private address space rather than directly to RAM. The system interprets this address through paging structures before reaching the physical memory location.
3.2 Physical addresses
A physical address identifies a specific location in RAM. After translation, the memory controller uses this address to read or write the actual data stored in hardware memory. Physical addresses are hidden from ordinary programs, which allows the operating system to reorganize memory without changing software behavior.
3.3 Translation lookaside buffer
A translation lookaside buffer is a small, fast cache that stores recent page-to-frame mappings. Since many programs access the same pages repeatedly, keeping these translations near the processor greatly reduces the cost of address conversion. The TLB is one of the most important performance features in a paged system.
3.3.1 TLB hits and misses
A TLB hit occurs when the required translation is already present in the buffer, allowing the processor to continue quickly. A TLB miss means the translation must be fetched from the page table, which takes more time. Frequent misses slow execution, so operating systems and hardware try to keep the TLB effective.
3.3.2 TLB replacement
Because the TLB has limited capacity, old entries must eventually be removed to make room for new ones. Replacement policies determine which translation is discarded when the buffer is full. Good replacement behavior helps preserve access speed by retaining the mappings most likely to be used again soon.
4 Demand paging
Demand paging delays loading a page until a program actually needs it. This strategy avoids bringing every page into memory at startup and therefore reduces initial loading time and memory usage. It is a major feature of virtual-memory systems and works especially well when programs do not touch all of their allocated pages.
4.1 Page faults
A page fault occurs when a process references a page that is not currently resident in physical memory. The hardware signals the condition to the operating system, which then decides how to satisfy the request. Page faults are normal in demand-paged systems, although they are much more expensive than ordinary memory access.
4.1.1 Handling a page fault
When a page fault occurs, the operating system checks whether the access is valid. If it is, the required page is located on secondary storage and brought into a free frame, or a frame is made available by replacing another page. After the data is loaded and the relevant tables are updated, the instruction is restarted.
4.1.2 Fault overhead
Handling a fault takes much longer than a standard memory reference because it may involve disk I/O, bookkeeping, and process state management. Even a small number of faults can noticeably affect responsiveness if they happen frequently. For that reason, systems aim to keep the page-fault rate low.
4.2 Swapping and backing store
A backing store is secondary storage used to hold pages that are not currently in RAM. Swapping refers broadly to moving pages between memory and this storage to free up space or bring needed content back. Although implementations vary, the basic purpose is to extend memory capacity beyond physical limits.
4.3 Demand-loading strategies
Demand-loading policies determine which pages are brought into memory immediately and which are deferred. Some systems load only the first pages needed to begin execution, while others prefetch a small cluster of related pages. The best approach depends on program behavior, storage speed, and the cost of unnecessary loading.
5 Page replacement
When physical memory is full and a new page must be loaded, the system may need to evict another page. Page replacement selects a victim page to remove from RAM so that the incoming one can be stored. The goal is to choose a page that will not be needed again soon, thereby minimizing future faults.
5.1 Need for replacement
Replacement becomes necessary when the number of active pages exceeds the number of available frames. Without a replacement policy, the system could not continue loading new pages once memory is exhausted. Efficient replacement helps the machine remain usable even under heavy memory demand.
5.2 Replacement algorithms
Different algorithms make different assumptions about future access patterns. Some are simple and fast, while others aim for better decisions at greater computational cost. No single method is perfect for all workloads, so real systems often use approximations.
5.2.1 FIFO
First-in, first-out replacement removes the page that has been in memory the longest. It is easy to implement because pages can be tracked in arrival order. However, it does not consider how recently or how often a page was used, so its choices may be poor for some workloads.
5.2.2 LRU
Least recently used replacement removes the page that has not been accessed for the longest time. This approach is often effective because it assumes pages used recently are more likely to be used again. Exact LRU can be expensive to maintain, so many systems use approximations instead.
5.2.3 Optimal replacement
Optimal replacement discards the page that will not be used for the longest time in the future. It produces the best possible result in theory, but it requires knowledge of future memory references, which is not available in practice. For this reason, it is mainly used as a benchmark for comparison.
5.2.4 Clock algorithm
The clock algorithm is a practical approximation of LRU. It arranges pages in a circular structure and uses a reference bit to give recently used pages a second chance. This method balances simplicity and effectiveness, making it a common replacement strategy in operating systems.
5.3 Thrashing
Thrashing happens when a system spends most of its time paging rather than executing useful work. It usually occurs when there are too many active pages competing for too few frames. Performance then collapses because the processor repeatedly waits for pages to be loaded and evicted.
6 Paging system design
The design of a paging system affects memory usage, translation speed, and overall efficiency. Choices such as page size and table structure influence both hardware complexity and operating-system behavior. Designers therefore weigh space, speed, and implementation cost when selecting a paging model.
6.1 Page size
Page size is the amount of memory covered by each page and frame. Small pages can improve flexibility, while large pages reduce the number of table entries needed. The chosen size affects fragmentation, translation overhead, and how well the system matches typical program behavior.
6.1.1 Trade-offs in page size
Smaller pages reduce wasted memory inside each allocated block and may improve locality for some workloads. Larger pages lower page-table overhead and can reduce the frequency of translations and faults. The ideal size depends on the balance between memory efficiency and management cost.
6.1.2 Internal fragmentation
Internal fragmentation occurs when the final page of an allocation is not completely filled. The unused space inside that page cannot be assigned to other purposes, which leads to some waste. Larger pages tend to increase this effect, especially for small allocations.
6.2 Multilevel paging
Multilevel paging divides the page table into several layers so that only the needed parts must be kept in memory. This structure is useful for large address spaces because it avoids allocating huge page tables for unused regions. It reduces memory overhead at the cost of additional translation steps.
6.3 Inverted page tables
An inverted page table contains one entry per physical frame rather than one per virtual page. Each entry identifies which process and virtual page currently occupies the frame. This design can save space in systems with very large address spaces, though it can make lookup more complex.
6.4 Segmentation and paging
Segmentation and paging are sometimes combined to provide both logical program organization and uniform memory allocation. Segmentation divides memory into variable-sized regions such as code or data, while paging manages them in fixed-size blocks. The combination can improve flexibility, though it also adds complexity to translation.
7 Hardware support for paging
Paging relies on specialized hardware to make address translation fast and to enforce access rules. The processor and memory-management components work together so that most translations happen transparently during normal execution. Without hardware assistance, paging would be much slower and less practical.
7.1 Memory management unit
The memory management unit is the hardware component that performs or assists with address translation. It interprets virtual addresses, consults translation caches or tables, and checks protection bits. The MMU is essential for making paging efficient enough for everyday use.
7.2 Page table support registers
Processors usually provide registers that point to the current page table or define related control information. These registers let the operating system switch address spaces when changing between processes. They also help the hardware locate the proper translation structures quickly.
7.3 Architectures and implementation
Different processor families implement paging in different ways, but the basic principle is the same. Some use large, layered structures, while others combine page tables with translation caches and permission checks. The details vary, yet all aim to support fast and reliable memory mapping.
7.4 Cache interaction
Paging interacts with caches because translated addresses must eventually be used to access cached or main-memory data. The system must ensure that translations and cached data remain consistent with one another. Efficient interaction between the TLB, caches, and memory controller is important for overall speed.
8 Performance considerations
Paging improves flexibility, but it also introduces overhead. The cost of translation, fault handling, and replacement decisions can affect responsiveness if not managed carefully. Performance depends on how often pages are reused, how much memory is available, and how the system balances competing tasks.
8.1 Access time
Memory access time in a paged system includes the time needed for translation as well as the actual read or write. A TLB hit keeps this overhead small, while a miss adds extra steps. Systems are optimized to make the common case fast so that paging does not dominate execution time.
8.2 Page fault rate
The page fault rate measures how often accesses require bringing pages into RAM. A low rate usually indicates that the working set is fitting well in memory. A high rate suggests that the system may be under strain or that the workload is actively moving through a large amount of data.
8.3 Working set behavior
The working set is the collection of pages a process uses actively over a period of time. If those pages remain resident, the process can run efficiently with few faults. When the working set does not fit in memory, the system may see frequent replacements and reduced throughput.
8.4 Memory pressure
Memory pressure arises when many processes compete for limited physical memory. Under pressure, the operating system must make more aggressive decisions about eviction and loading. Paging helps the system continue operating, but heavy pressure can still degrade responsiveness and increase fault activity.
9 Security and reliability
Paging contributes to both security and reliability by controlling access to memory and limiting the impact of errors. Separate address spaces make it harder for one program to interfere with another, while fault handling allows the system to respond to invalid accesses in a controlled way. These features are central to stable multiprogramming.
9.1 Access control
Access control in paging is implemented through permission bits attached to each page. These bits define whether memory can be read, written, or executed. If a process violates the rules, the hardware stops the access and the operating system can take appropriate action.
9.2 Process protection
Process protection ensures that the memory of one process cannot be casually read or altered by another. Paging supports this by mapping different virtual address spaces to different physical regions or by restricting shared mappings. This separation is a key reason modern systems can run many programs at the same time.
9.3 Fault containment
When a program makes an invalid memory reference, paging helps contain the problem by raising an exception instead of allowing silent corruption. The operating system can terminate the process, report an error, or attempt recovery depending on the situation. This behavior limits the spread of damage and protects the rest of the system.
9.4 Reliability implications
Paging can improve reliability by reducing dependence on contiguous memory and by allowing controlled management of scarce resources. It also makes it possible to isolate damaged or misbehaving processes more effectively. At the same time, paging-related overhead and faults must be handled carefully to maintain stable operation.