Paging
From Wikipedia, the free encyclopedia
- Alternate meanings: See paging (telecommunications). See radio paging. Bank switching is also sometimes referred to as paging.
In computer operating systems, paging memory allocation, paging refers to the process of managing program access to virtual memory pages that do not currently reside in RAM. It is implemented as a task that resides in the kernel of the operating system and gains control when a page fault takes place. Its main functions performed are:
- determine the location of the data in auxiliary storage.
- determine the page in RAM to use as a container for the data.
- write the existing page to auxiliary storage if it has been modified since it was last loaded.
- load the requested data into the available page.
The fault that triggers this operation is caused by a program trying to reference an address within a page that is not currently residing in RAM.
[edit] Detail
When a page has to be loaded and all existing pages in RAM are currently in use, one of the existing pages must be swapped with the requested new page. The paging system must determine the page to swap by choosing one based on an algorithm that determines the best choice: the page least likely to be needed within a short time.
Most operating systems use LRU: least recently used. The theory behind LRU is that the least recently used page is the most likely one not to be needed shortly. This algorithm is most often correct but not always: e.g. a sequential process moves forward through memory and never again accesses the most recently used page.
The need to reference RAM at a particular address arises from two main sources:
- Programs that are loading instructions to be executed.
- Data being accessed by a program.
Most programs that become active reach a steady state in their demand for memory locality both in terms of instructions fetched and data being accessed. This steady state is usually much less than the total memory required by the program. This steady state is sometimes referred to as the working set: the set of memory pages that are most frequently accessed.
Virtual memory systems work most efficiently when the ratio of the working set to the total number of pages that can be stored in RAM is low enough to minimize the number of page faults. A misbehaving program or one that works with huge arrays that cross many pages will sometimes require a working set that is too large to be efficiently managed by the page system resulting in constant page faults that drastically slow down the system. This condition is referred to as thrashing: a page is swapped out and then accessed causing frequent faults.
An interesting characteristic of thrashing is that as the working set grows, there is very little increase in the number of faults until the ratio hits the critical point and then the faults go up dramatically. If one graphs the number of faults on one axis and working set size on the other, the graph will look like a hockey stick.
