Page replacement algorithm
In a computer operating system that uses paging for virtual memory management, page replacement algorithms decide which memory pages to page out, sometimes called swap out, or write to disk, when a page of memory needs to be allocated. Page replacement happens when a requested page is not in memory (page fault) 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.
- Comment
- enIn a computer operating system that uses paging for virtual memory management, page replacement algorithms decide which memory pages to page out, sometimes called swap out, or write to disk, when a page of memory needs to be allocated. Page replacement happens when a requested page is not in memory (page fault) 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.
- Has abstract
- enIn a computer operating system that uses paging for virtual memory management, page replacement algorithms decide which memory pages to page out, sometimes called swap out, or write to disk, when a page of memory needs to be allocated. Page replacement happens when a requested page is not in memory (page fault) 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. 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. The page replacing problem is a typical online problem from the competitive analysis perspective in the sense that the optimal deterministic algorithm is known.
- Is primary topic of
- Page replacement algorithm
- Label
- enPage replacement algorithm
- Link from a Wikipage to an external page
- www.usenix.org/conference/2001usenixannualtechnicalconference
- minds.wisconsin.edu/handle/1793/60102%7Ctitle=Technical
- csdl2.computer.org/persagen/DLAbsToc.jsp%3FresourcePath=/dl/proceedings/euromicro/&toc=comp/proceedings/euromicro/1997/8215/00/8215toc.xml
- www.informit.com/articles/article.aspx%3Fp=25260
- dl.acm.org/citation.cfm%3Fid=258612
- dl.acm.org/citation.cfm%3Fid=258681
- dl.acm.org/citation.cfm%3Fid=301453&picked=prox
- dl.acm.org/citation.cfm%3Fid=511334&picked=prox
- www.usenix.org/events/osdi2000/
- web.archive.org/web/20040918122454/http:/ssrnet.snu.ac.kr/~choijm/paper/IC-2000-OSDI-UBM.pdf
- www.usenix.org/legacy/events/osdi2000/full_papers/kim/kim.pdf
- archive.org/details/modernoperatings00tane
- archive.org/details/operatingsystems00tane
- archive.wikiwix.com/cache/20160304000000/http:/www.amherst.edu/~sfkaplan/courses/spring-2004/cs40/papers/SKW:EELRUSEAPR.pdf
- www.amherst.edu/~sfkaplan/courses/spring-2004/cs40/papers/SKW:EELRUSEAPR.pdf
- archive.wikiwix.com/cache/20190612074945/http:/www.cse.ohio-state.edu/hpcs/WWW/HTML/publications/papers/TR-02-6.pdf
- www.cse.ohio-state.edu/hpcs/WWW/HTML/publications/papers/TR-02-6.pdf
- usenix.org/publications/library/proceedings/usenix01/full_papers/zhou/zhou.pdf
- web.archive.org/web/20051124142243/http:/www.usenix.org/events/usenix01/full_papers/zhou/zhou.pdf%7C
- Link from a Wikipage to another Wikipage
- 1,0,1,0,1,1%5D, %5B1,1,0,0,1,0%5D, %5B1,1,0,1,0,1%5D, %5B1,0,0,0,1,0%5D, %5B0,1,1,0,0,0
- 390
- Adaptive replacement cache
- Amortized analysis
- Anonymous pipe
- Arithmetic shift
- ARM architecture
- ARMv8
- Bélády's anomaly
- Binary number
- Block device
- Category:Articles with example Python (programming language) code
- Category:Memory management algorithms
- Category:Online algorithms
- Category:Virtual memory
- Clairvoyance
- Computer
- CPU cache
- Demand paging
- Dirty bit
- Fernando J. Corbató
- FreeBSD
- Full duplex
- Garbage collection (computer science)
- Hash table
- Heap (programming)
- Intel i860
- Journaling file system
- Kernel (computer science)
- László Bélády
- Linux
- Linux (kernel)
- Linux kernel
- Locality of reference
- Memory management
- Memory management (operating systems)
- Mmap
- Object-oriented programming
- Online algorithm
- Online problem
- OpenVMS
- Operating system
- Page (computer memory)
- Page fault
- Page replacement algorithm
- Page table
- Paging
- Prefetch input queue
- Python (programming language)
- Sbrk
- Scheduling (computing)
- Shared memory
- Solaris (operating system)
- Stack-based memory allocation
- The LIRS caching algorithm
- Tmpfs
- Tree data structure
- User-space
- VAX
- Virtual memory
- Working set
- X86
- X86-64
- SameAs
- Algorithmes de remplacement des lignes de cache
- Algoritma penggantian halaman
- Algoritmo de reemplazo de páginas
- Algoritmo de troca de página
- m.0362yx
- MRHb
- Orriak ordezteko algoritmoak
- Page replacement algorithm
- Page replacement algorithm
- Q1330967
- Sayfa yer değiştirme algoritması
- Stránkovací algoritmy
- Алгоритми за преместување на мемориски страници
- Задача заміщення сторінок
- الگوریتم جایگزینی صفحه
- خوارزم تبديل الصفحات
- ページ置換アルゴリズム
- 快取文件置換機制
- 페이지 교체 알고리즘
- SeeAlso
- Paging
- Virtual memory
- Subject
- Category:Articles with example Python (programming language) code
- Category:Memory management algorithms
- Category:Online algorithms
- Category:Virtual memory
- WasDerivedFrom
- Page replacement algorithm?oldid=1121435709&ns=0
- WikiPageLength
- 48520
- Wikipage page ID
- 727476
- Wikipage revision ID
- 1121435709
- WikiPageUsesTemplate
- Template:About
- Template:Citation needed
- Template:Cite book
- Template:Cite conference
- Template:Cite journal
- Template:Clarify
- Template:Cn
- Template:Confusing
- Template:Div col
- Template:Div col end
- Template:Main
- Template:Mvar
- Template:Reflist
- Template:See also
- Template:Short description
- Template:Use dmy dates
- Template:Val