Paging

In computer operating systems, paging is a memory management scheme by which a computer stores and retrieves data from secondary storage for use in main memory. In this scheme, the operating system retrieves data from secondary storage in same-size blocks called pages. 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. In computer operating systems, paging is a memory management scheme by which a computer stores and retrieves data from secondary storage for use in main memory. In this scheme, the operating system retrieves data from secondary storage in same-size blocks called pages. 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. For simplicity, main memory is called 'RAM' (an acronym of 'random-access memory') and secondary storage is called 'disk' (a shorthand for 'hard disk drive'), but the concepts do not depend on whether these terms apply literally to a specific computer system. Ferranti introduced paging on the Atlas, but the first mass market memory pages were concepts in computer architecture, regardless of whether a page moved between RAM and disk. For example, on the PDP-8, 7 of the instruction bits comprised a memory address that selected one of 128 (27) words. This zone of memory was called a page. This use of the term is now rare. In the 1960s, swapping was an early virtual memory technique. An entire program would be swapped out (or rolled out) from RAM to disk, and another one would be swapped in (or rolled in). A swapped-out program would be current but its execution would be suspended while its RAM was in use by another program. A program might include multiple overlays that occupy the same memory at different times. Overlays are not a method of paging RAM to disk but merely of minimizing the program's use of RAM. Subsequent architectures used memory segmentation, and individual program segments became the units exchanged between disk 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. The invention of the page table let the processor operate on arbitrary pages anywhere in RAM as a seemingly contiguous logical address space. These pages became the units exchanged between disk and RAM. When a process tries to reference a page not currently present 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: When all page frames are in use, the operating system must select a page frame to reuse for the page the program now needs. If the evicted page frame was dynamically allocated by a program to hold data, or if a program modified it since it was read into RAM (in other words, if it has become 'dirty'), it must be written out to disk before being freed. If a program later references the evicted page, another page fault occurs and the page must be read back into RAM. The method the operating system uses to select the page frame to reuse, which is its page replacement algorithm, is important to efficiency. The operating system predicts the page frame least likely to be needed soon, often through the least recently used (LRU) 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.