Memory paging
In computer operating systems, memory paging is a memory management scheme that allows the physical memory used by a program to be non-contiguous. This also helps avoid the problem of memory fragmentation and requiring compaction to reduce fragmentation.
Paging is often combined with the related technique of allocating and freeing page frames and storing pages on and retrieving them from secondary storage in order to allow the aggregate size of the address spaces to exceed the physical memory of the system. For historical reasons, this technique is sometimes referred to as swapping.
When combined with virtual memory, it is known as paged virtual memory.
In this scheme, the operating system retrieves data from secondary storage in blocks of the same size.
Paging is an important part of virtual memory implementations in modern operating systems, using secondary storage to let programs exceed the size of available physical memory.
Hardware support is necessary for efficient translation of logical addresses to physical addresses. As such, paged memory functionality is usually hardwired into a CPU through its Memory Management Unit or Memory Protection Unit, and separately enabled by privileged system code in the operating system's kernel. In CPUs implementing the x86 instruction set architecture for instance, the memory paging is enabled via the CR0 control register.
History
In the 1960s, swapping was an early memory management technique. An entire program or entire segment would be "swapped out" from Random-access memory to disk or drum, and another one would be swapped in. A swapped-out program would be current but its execution would be suspended while the RAM was in use by another program; a program with a swapped-out segment could continue running until it needed that segment, at which point it would be suspended until the segment was swapped in.A program might include multiple overlays that occupy the same memory at different times. Overlays are not a method of paging RAM to secondary storage but merely of minimizing the program's RAM use. Subsequent architectures used memory segmentation, and individual program segments became the units exchanged between secondary storage and RAM. A segment was the program's entire code segment or data segment, or sometimes other large data structures. These segments had to be contiguous when resident in RAM, requiring additional computation and movement to remedy fragmentation.
Ferranti's Atlas, and the Atlas Supervisor developed at the University of Manchester, was the first system to implement memory paging. Subsequent early machines, and their operating systems, supporting paging include the IBM M44/44X and its MOS operating system, the SDS 940 and the Berkeley Timesharing System, a modified IBM System/360 Model 40 and the CP-40 operating system, the IBM System/360 Model 67 and operating systems such as TSS/360, CP/CMS and the Michigan Terminal System , the RCA 70/46 and the Time Sharing Operating System , the GE 645 and Multics, and the DEC PDP-10 with added BBN-designed paging hardware and the TENEX operating system.
Those machines, and subsequent machines supporting memory paging, use either a set of page address registers or in-memory page tables to allow the processor to operate on arbitrary pages anywhere in RAM as a seemingly contiguous logical address space. These pages became the units exchanged between secondary storage and RAM.
Page faults
When a process tries to reference a page not currently mapped to a page frame in RAM, the processor treats this invalid memory reference as a page fault and transfers control from the program to the operating system. The operating system must:- Determine whether a stolen page frame still contains an unmodified copy of the page; if so, use that page frame.
- Otherwise, obtain an empty page frame in RAM to use as a container for the data, and:
- * Determine whether the page was ever initialized
- * If so determine the location of the data on secondary storage.
- * Load the required data into the available page frame.
- Update the page table to refer to the new page frame.
- Return control to the program, transparently retrying the instruction that caused the page fault.
The method the operating system uses to select the page frame to reuse, which is its page replacement algorithm, affects efficiency.
The operating system predicts the page frame least likely to be needed soon, often through the least recently used algorithm or an algorithm based on the program's working set. To further increase responsiveness, paging systems may predict which pages will be needed soon, preemptively loading them into RAM before a program references them, and may steal page frames from pages that have been unreferenced for a long time, making them available. Some systems clear new pages to avoid data leaks that compromise security; some set them to installation defined or random values to aid debugging.
Page fetching techniques
Demand paging
When pure demand paging is used, pages are loaded only when they are referenced. A program from a memory mapped file begins execution with none of its pages in RAM. As the program commits page faults, the operating system copies the needed pages from a file, e.g., memory-mapped file, paging file, or a swap partition containing the page data into RAM.Anticipatory paging
Some systems use only demand paging—waiting until a page is actually requested before loading it into RAM.Other systems attempt to reduce latency by guessing which pages not in RAM are likely to be needed soon, and pre-loading such pages into RAM, before that page is requested..
When a page fault occurs, anticipatory paging systems will not only bring in the referenced page, but also other pages that are likely to be referenced soon. A simple anticipatory paging algorithm will bring in the next few consecutive pages even though they are not yet needed ; this is analogous to a prefetch input queue in a CPU. Swap prefetching will prefetch recently swapped-out pages if there are enough free pages for them.
If a program ends, the operating system may delay freeing its pages, in case the user runs the same program again.
Some systems allow application hints; the application may request that a page be made available and continue without delay.
Page replacement techniques
Free page queue, stealing, and reclamation
The free page queue is a list of page frames that are available for assignment. Preventing this queue from being empty minimizes the computing necessary to service a page fault. Some operating systems periodically look for pages that have not been recently referenced and then free the page frame and add it to the free page queue, a process known as "page stealing". Some operating systems support page reclamation; if a program commits a page fault by referencing a page that was stolen, the operating system detects this and restores the page frame without having to read the contents back into RAM.Pre-cleaning
The operating system may periodically pre-clean dirty pages: write modified pages back to secondary storage even though they might be further modified. This minimizes the amount of cleaning needed to obtain new page frames at the moment a new program starts or a new data file is opened, and improves responsiveness.Some systems allow application hints; the application may request that a page be cleared or paged out and continue without delay.
Thrashing
After completing initialization, most programs operate on a small number of code and data pages compared to the total memory the program requires. The pages most frequently accessed are called the working set.When the working set is a small percentage of the system's total number of pages, virtual memory systems work most efficiently and an insignificant amount of computing is spent resolving page faults. As the working set grows, resolving page faults remains manageable until the growth reaches a critical point. Then faults go up dramatically and the time spent resolving them overwhelms time spent on the computing the program was written to do. This condition is referred to as thrashing. Thrashing occurs on a program that works with huge data structures, as its large working set causes continual page faults that drastically slow down the system. Satisfying page faults may require freeing pages that will soon have to be re-read from secondary storage. "Thrashing" is also used in contexts other than virtual memory systems; for example, to describe cache issues in computing or silly window syndrome in networking.
A worst case might occur on VAX processors. A single MOVL crossing a page boundary could have a source operand using a displacement deferred addressing mode, where the longword containing the operand address crosses a page boundary, and a destination operand using a displacement deferred addressing mode, where the longword containing the operand address crosses a page boundary, and the source and destination could both cross page boundaries. This single instruction references ten pages; if not all are in RAM, each will cause a page fault. As each fault occurs the operating system needs to go through the extensive memory management routines perhaps causing multiple I/Os which might include writing other process pages to disk and reading pages of the active process from disk. If the operating system could not allocate ten pages to this program, then remedying the page fault would discard another page the instruction needs, and any restart of the instruction would fault again.
To decrease excessive paging and resolve thrashing problems, a user can increase the number of pages available per program, either by running fewer programs concurrently or increasing the amount of RAM in the computer.