FACTOID # 1: Idaho produces more milk than Iowa, Indiana and Illinois combined.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Page replacement algorithm

In a computer operating system that utilises paging for virtual memory memory management, page replacement algorithms decide which memory pages to page out (swap out, write to disk) when a page of memory needs to be allocated. Paging happens when a page fault occurs and a free page cannot be used to satisfy the allocation, either because there are none, or because the number of free pages is lower than some threshold. Wikipedia does not have an article with this exact name. ... It has been suggested that page replacement algorithm be merged into this article or section. ... The NASA Columbia Supercomputer. ... // An operating system (OS) is a set of computer programs that manage the hardware and software resources of a computer. ... 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... How virtual memory maps to physical memory Virtual memory is an addressing scheme implemented in hardware and software that allows non-contiguous memory to be addressed as if it were contiguous. ... Memory management is the act of managing computer memory. ... In computer storage technology, a page is a fixed length block of memory that is used as a unit of transfer between physical memory and external storage like a disk, and a page fault is an interrupt (or exception) to the software raised by the hardware, when a program accesses...


When the page that was selected for replacement and paged out is referenced again it has to be paged in (read in from disk), and this involves waiting for I/O completion. This determines the quality of the page replacement algorithm: the less time waiting for page-ins, the better the algorithm. A page replacement algorithm looks at the limited information about accesses to the pages provided by hardware, and tries to guess which pages should be replaced to minimize the total number of page misses, while balancing this with the costs (primary storage and processor time) of the algorithm itself.

Contents

History

Page replacement algorithms were a hot topic of research and debate in the 1960s and 1970s. That mostly ended with the development of sophisticated LRU approximations and working set algorithms. Since then, some basic assumptions made by the traditional page replacement algorithms were invalidated, resulting in a revival of research. In particular, the following trends in the behavior of underlying hardware and user-level software has affected the performance of page replacement algorithms: Year 1960 (MCMLX) was a leap year starting on Friday (link will display full calendar) of the Gregorian calendar. ... 1970 (MCMLXX) was a common year starting on Thursday. ...

  • Size of primary storage has increased by multiple orders of magnitude. With several gigabytes of primary memory, algorithms that require a periodic check of each and every memory frame are becoming less and less practical.
  • Memory hierarchies have grown taller. The cost of a CPU cache miss is far more expensive. This exacerbates the previous problem.

Requirements for page replacement algorithms have changed due to differences in operating system kernel architectures. In particular, most modern OS kernels have unified virtual memory and file system caches, requiring the page replacement algorithm to select a page from among the pages of both user program virtual address spaces and cached files. The latter pages have specific properties. For example, they can be locked, or can have write ordering requirements imposed by journaling. Moreover, as the goal of page replacement is to minimize total time waiting for memory, it has to take into account memory requirements imposed by other kernel sub-systems that allocate memory. As a result, page replacement in modern kernels (Linux, FreeBSD, and Solaris) tends to work at the level of a general purpose kernel memory allocator, rather than at the higher level of a virtual memory subsystem. Memory Locality is a term in computer science used to denote the temporal or spatial proximity of memory access. ... Object-oriented programming (OOP) is a programming paradigm that uses objects to design applications and computer programs. ... In computer science, a tree is a widely-used computer data structure that emulates a tree structure with a set of linked nodes. ... In computer science, a hash table is a data structure that speeds up searching for information by a particular aspect of that information, called a key. ... In computer science, garbage collection (also known as GC) is a form of automatic memory management. ... A kernel connects the application software to the hardware of a computer. ... A journaling (or journalling) file system is a file system that logs changes to a journal (usually a circular log in a specially-allocated area) before actually writing them to the main file system. ... Linux (IPA pronunciation: ) is a Unix-like computer operating system. ... FreeBSD is a Unix-like free operating system descended from AT&T UNIX via the Berkeley Software Distribution (BSD) branch through the 386BSD and 4. ... Solaris is a computer operating system developed by Sun Microsystems. ...


Local vs. global replacement

Replacement algorithms can be local or global.


When a process incurs a page fault, a local page replacement algorithm selects for replacement some page that belongs to that same process (or a group of processes sharing a memory partition). A global replacement algorithm is free to select any page in memory.


Local page replacement assumes some form of memory partitioning that determines how many pages are to be assigned to a given process or a group of processes. Most popular forms of partitioning are fixed partitioning and balanced set algorithms based on the working set model. The advantage of local page replacement is its scalability: each process can handle its page faults independently without contending for some shared global data structure. Working set is the set of physical memory pages currently dedicated to a specific process. ...


Precleaning

Most replacement algorithms simply return the target page as their result. This means that if target page is dirty (that is, contains data that have to be written to the stable storage before page can be reclaimed), I/O has to be initiated to send that page to the stable storage (to clean the page). In the early days of virtual memory, time spent on cleaning wasn't of much concern, because virtual memory was first implemented on systems with full duplex channels to the stable storage, and cleaning was customarily overlapped with pagein. Contemporary commodity hardware, on the other hand, doesn't support full duplex transfers, and cleaning of target pages becomes an issue. Duplex is the having of two principal elements or parts. ...


To deal with this situation, various precleaning policies are implemented. Precleaning is the mechanism that starts I/O on dirty pages that are (likely) to be replaced soon. The idea is that by the time the precleaned page is actually selected for the replacement, the I/O will complete and the page will be clean. Precleaning assumes that it is possible to identify pages that will be replaced next. Precleaning that is too eager can waste I/O bandwidth by writing pages that manage to get re-dirtied before being selected for replacement.


The theoretically optimal page replacement algorithm

The theoretically optimal page replacement algorithm (also known as OPT or clairvoyant replacement algorithm) is an algorithm that works as follows: when a page needs to be swapped in, the operating system swaps out the page whose next use will occur farthest in the future. For example, a page that is not going to be used for the next 6 seconds will be swapped out over a page that is going to be used within the next 0.4 seconds. Clairvoyance, from 17th century French Clair meaning clear and voyant meaning seeing, is a term used to describe the transference of information about an object, location or physical event through means other than the 5 traditional senses (See Psi). ... // An operating system (OS) is a set of computer programs that manage the hardware and software resources of a computer. ...


This algorithm cannot be implemented in the general purpose operating system because it is impossible to reliably compute how long it will be before a page is going to be used, except when all software that will run on a system is either known beforehand and is amenable to the static analysis of its memory reference patterns, or only a class of applications allowing run-time analysis is allowed. Despite this limitation, algorithms exist that can offer near-optimal performance — on the first run of a program, the operating system keeps track of all pages referenced by the program, and it uses this data to decide which pages to swap in and out on subsequent runs. This algorithm can offer near-optimal performance, but not on the first run of a program, and only if the program's memory reference pattern is relatively consistent each time it runs.


Analysis of the paging problem has also been done in the field of online algorithms. Efficiency of randomized online algorithms for the paging problem is measured using amortized analysis. In computer science, an online algorithm is one that can process its input piece-by-piece, without having the entire input available from the start. ... In computational complexity theory, amortized analysis is the time per operation averaged over a worst_case sequence of operations. ...


Not recently used

The not recently used (NRU) page replacement algorithm is an algorithm that favours keeping pages in memory that have been recently used. This algorithm works on the following principle: when a page is referenced, a referenced bit is set for that page, marking it as referenced. Similarly, when a page is modified (written to), a modified bit is set. The setting of the bits is usually done by the hardware, although it is possible to do so on the software level as well.


At a certain fixedtime interval, the clock interrupt triggers and clears the referenced bit of all the pages, so only pages referenced within the current clock interval are marked with a referenced bit. When a page needs to be replaced, the operating system divides the pages into four classes: // An operating system (OS) is a set of computer programs that manage the hardware and software resources of a computer. ...

  • Class 0: not referenced, not modified
  • Class 1: not referenced, modified
  • Class 2: referenced, not modified
  • Class 3: referenced, modified

Although it does not seem possible for a page to be not referenced yet modified, this happens when a category 3 page has its referenced bit cleared by the clock interrupt. The NRU algorithm picks a random page from the lowest category for removal. Note that this algorithm implies that a referenced page is more important than a modified page.


First-in, first-out

The first-in, first-out (FIFO) page replacement algorithm is a low-overhead algorithm that requires little bookkeeping on the part of the operating system. The idea is obvious from the name - the operating system keeps track of all the pages in memory in a queue, with the most recent arrival at the back, and the earliest arrival in front. When a page needs to be replaced, the page at the front of the queue (the oldest page) is selected. While FIFO is cheap and intuitive, it performs poorly in practical application. Thus, it is rarely used in its unmodified form. This algorithm experiences Belady's anomaly. // An operating system (OS) is a set of computer programs that manage the hardware and software resources of a computer. ... Beladys anomaly states that it is possible to have more page faults when increasing the number of page frames while using FIFO method of frame management. ...


FIFO page replacement algorithm is used by the VAX/VMS operating system.[1] OpenVMS V7. ...


Second-chance

A modified form of the FIFO page replacement algorithm, known as the Second-chance page replacement algorithm, fares relatively better than FIFO at little cost for the improvement. It works by looking at the front of the queue as FIFO does, but instead of immediately paging out that page, it checks to see if its referenced bit is set. If it is not set, the page is swapped out. Otherwise, the referenced bit is cleared, the page is inserted at the back of the queue (as if it were a new page) and this process is repeated. This can also be thought of as a circular queue. If all the pages have their referenced bit set, on the second encounter of the first page in the list, that page will be swapped out, as it now has its referenced bit cleared.


As its name suggests, Second-chance gives every page a "second-chance" - an old page that has been referenced is probably in use, and should not be swapped out over a new page that has not been referenced.


Clock

Clock is a more efficient version of FIFO than Second-chance because pages don't have to be constantly pushed to the back of the list, but it performs the same general function as Second-Chance. The clock algorithm keeps a circular list of pages in memory, with the "hand" (iterator) pointing to the oldest page in the list. When a page fault occurs and no empty frames exist, then the R (referenced) bit is inspected at the hand's location. If R is 0, the new page is put in place of the page the "hand" points to, otherwise the R bit is cleared and the hand is incremented. This is repeated until a page is replaced. [2]


Least recently used

The least recently used page (LRU) replacement algorithm, though similar in name to NRU, differs in the fact that LRU keeps track of page usage over a short period of time, while NRU just looks at the usage in the last clock interval. LRU works on the idea that pages that have been most heavily used in the past few instructions are most likely to be used heavily in the next few instructions too. While LRU can provide near-optimal performance in theory, it is rather expensive to implement in practice. There are a few implementation methods for this algorithm that try to reduce the cost yet keep as much of the performance as possible.


The most expensive method is the linked list method, which uses a linked list containing all the pages in memory. At the back of this list is the least recently used page, and at the front is the most recently used page. The cost of this implementation lies in the fact that items in the list will have to be moved about every memory reference, which is a very time-consuming process.


Another method that requires hardware support is as follows: suppose the hardware has a 64-bit counter that is incremented at every instruction. Whenever a page is accessed, it gains a value equal to the counter at the time of page access. Whenever a page needs to be replaced, the operating system selects the page with the lowest counter and swaps it out. With present hardware, this is not feasible because the required hardware counters do not exist. // An operating system (OS) is a set of computer programs that manage the hardware and software resources of a computer. ...


Because of implementation costs, one may consider algorithms (like those that follow) that are similar to LRU, but which offer cheaper implementations.


One important advantage of LRU algorithm is that it is amenable to full statistical analysis. It has been proved, for example, that LRU can never result in more than N-times more page faults than OPT algorithm, where N is proportional to the number of pages in the managed pool.


On the other hand, LRU's weakness is that its performance tends to degenerate under many quite common reference patterns. For example, if there are N pages in the LRU pool, an application executing a loop over array of N + 1 pages will cause a page fault on each and every access. As loops over large arrays are common, much effort has been put into modifying LRU to work better in such situations. Many of the proposed LRU modifications try to detect looping reference patterns and to switch into suitable replacement algorithm, like Most Recently Used (MRU).


Variants on LRU

  1. LRU-K improves greatly on LRU with regard to locality in time. It's also known as LRU-2, for the case that K=2. LRU-1 (i.e. K=1) is the same as normal LRU.
  1. The ARC[3] algorithm extends LRU by maintaining a history of recently evicted pages and uses this to change preference to recent or frequent access. It is particularly resistant to sequential scans.

A comparison of ARC with other algorithms (LRU,MQ,2Q,LRU-2,LRFU,LIRS) can be found in Megiddo & Modha[4] Adaptive Replacement Cache (ARC) is a cache management algorithm with better performance[1] than LRU (Least Recently Used) developed[2] at the IBM Almaden Research Center. ...


Random

Random replacement algorithm replaces a random page in memory. However silly that may sound, this algorithm is useful in certain situations. Usually it fares better than FIFO, and for looping memory references it is better than LRU, although generally LRU performs better in practice. OS/390 uses global LRU approximation and falls back to random replacement when LRU performance degenerates, and the Intel i860 processor used a random replacement policy (Rhodehamel 1989). OS/390 is an IBM operating system for the System/370 and System/390 IBM mainframe computers. ... The Intel i860 (also 80860, and code named N10) was a RISC microprocessor from Intel, first released in 1989. ...


Not frequently used

The not frequently used (NFU) page replacement algorithm requires a counter, and every page has one counter of its own, initially zero. At each clock interval, all pages that have been referenced within that interval will have their counter incremented by 1. In effect, the counters keep track of how frequently a page has been used. Thus, the page with the lowest counter can be swapped out when necessary.


The main problem with NFU is that it keeps track of the frequency of use without regard to the time span of use. Thus, in a multi-pass compiler, pages which were heavily used during the first pass, but are not needed in the second pass will be favoured over pages which are comparably lightly used in the second pass, as they have higher frequency counters. This results in poor performance. Other common scenarios exist where NFU will perform similarly, such as an OS boot-up. Thankfully, a similar and better algorithm exists, and its description follows.


Aging

The aging algorithm is a descendant of the NFU algorithm, with modifications to make it aware of the time span of use. Instead of just incrementing the counters of pages referenced, putting equal emphasis on page references regardless of the time, the reference counter on a page is first shifted right (divided by 2), before adding the referenced bit to the left of that binary number. For instance, if a page has referenced bits 1,0,0,1,1,0 in the past 6 clock ticks, its referenced counter will look like this: 10000000, 01000000, 00100000, 10010000, 11001000, 01100100. Page references closer to the present time have more impact than page references long ago. This ensures that pages referenced more recently, though less frequently referenced, will have higher priority over pages more frequently referenced in the past. Thus, when a page needs to be swapped out, the page with the lowest counter will be chosen.


Note that aging differs from LRU in the sense that aging can only keep track of the references in the latest 16/32 (depending on the bit size of the processor's integers) time intervals. Consequently, two pages may have referenced counters of 00000000, even though one page was referenced 9 intervals ago and the other 1000 intervals ago. Generally speaking, knowing the usage within the past 16 intervals is sufficient for making a good decision as to which page to swap out. Thus, aging can offer near-optimal performance for a moderate price.


Working Set

The working set isn't a page replacement algorithm in the strict sense, but a page-replacement algorithm can remove a page if it's not in the working set for a process. For example, the Clock algorithm can be modified to ignore pages currently in the working set, or if the R bit set. (Carr and Hennessey, 1981) Working set is the set of physical memory pages currently dedicated to a specific process. ...


References

  1. ^ Abraham Silberschatz, Peter Baer Galvin, Greg Gagne. Operating Systems Concepts. ?: Wiley 2005. p. 339.
  2. ^ Andrew S. Tanenbaum. Modern Operating Systems (Second Edition). pp. 218 (4.4.5). 2001.
  3. ^ Megiddo & Modha, ARC: A Self-tuning, low overhead replacement cache
  4. ^ Nimrod Megiddo & Dharmendra S. Modha, Outperforming LRU with an Adaptive Replacement Cache AlgorithmPDF (123 KiB), IEEE Computer Magazine, pp. 58-65, April 2004.

See Also: Portable Document Format (PDF) is a file format created by Adobe Systems in 1993 for desktop publishing use. ... A kibibyte (a contraction of kilo binary byte) is a unit of information or computer storage, commonly abbreviated KiB (never kiB). 1 kibibyte = 210 bytes = 1,024 bytes The kibibyte is closely related to the kilobyte, which can be used either as a synonym for kibibyte or to refer to...


  Results from FactBites:
 
Page replacement algorithms - Wikipedia, the free encyclopedia (2464 words)
A page replacement algorithm tries, by looking at the limited information about accesses to the pages provided by hardware, to guess what pages should be replaced in order to minimize total number of page misses, while balancing this with the costs (primary storage and processor time) of algorithm itself.
Replacement algorithms were a hot topic of research and debate in the 1960s and 1970s.
The theoretically optimal page replacement algorithm (also known as OPT or clairvoyant replacement algorithm) is an algorithm which works as follows: when a page needs to be swapped in, the operating system looks at all the pages currently in memory, and sees how long it is before that page will be used.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m