Talk:Page replacement algorithm

Section 5.4 is missing words

The part about the second-chance algorithm seems to miss some words especially in the last sentence

As its name suggests, Second-chance gives every page a "second-chance" - an old page that has been referenced is

Maybe the author could finish this77.1.49.98 (talk) 14:21, 15 March 2009 (UTC)

Outdated information about time-stamp counters

The article says

Another way, which requires hardware support is as follows: suppose the hardware has a 64-bit counter which 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 simply picks out the page which has the lowest counter, and swaps it out. This is not feasible in present hardware as there exists no such hardware counters,

yet in Intel’s x86 System Programming, section 15.7, “Time-Stamp Counters”, [1]:

The time-stamp counter (as implemented in the Pentium 4, Intel Xeon, P6 family, and Pentium processors) is a 64-bit counter that is set to 0 following the hardware reset of the processor. Following reset, the counter is incremented every processor clock cycle, even when the processor is halted by the HLT instruction or the external STPCLK# pin. However, the assertion of the external DPSLP# pin may cause the time-stamp counter to stop and Intel SpeedStep® technology transitions may cause the frequency at which the time-stamp counter increments to change in accordance with the processor's internal clock frequency.

The RDTSC instruction reads the time-stamp counter and is guaranteed to return a monotonically increasing unique value whenever executed, except for 64-bit counter wraparound. Intel guarantees, architecturally, that the time-stamp counter frequency and configuration will be such that it will not wraparound within 10 years after being reset to 0. The period for counter wrap is several thousands of years in the Pentium 4, Intel Xeon, P6 family, and Pentium processors ..

—Mikael Brockman 17:32, 5 January 2006 (UTC)

Actually, the feasability is in having a 64bit counter per page. Last I checked the PTE (page table entries) on x86 only use a single access bit tagging the page was accessed since the bit was last reset. —--TooLazyToLogin, Oct 13 2006

After adding references to ARC, I've been expanding references and links with citations. This work is not yet finished. I've also replaced some links to citeseer (which was not available at this time) with links to the original publishers (ACM, Usenix). Henk Langeveld 22:15, 22 January 2007 (UTC)

I've removed this unattributed sentence:

With present hardware, this is not feasible because the OS needs to examine the counter for every page in the cache memory.

Page access timestamps ("counters") stored in a priority queue do not require examining the "counter" (timestamp) for every page in the cache memory. AHMartin (talk) 19:34, 12 July 2019 (UTC)

Multics

Of fundamental importance to any algorithm that controls the movement of pages, and of prime interest in the description of any paging system, is the main memory replacement algorithm, known in the literature as the "Page Replacement Algorithm," or PRA. The Multics PRA was one of the first to ever be implemented; the version as it exists today is a direct descendant of Corbató's original algorithm (see the references at the end of the next section).

Pages are kept in a circular list, the core used list, implemented by the double thread of CMEs. A logical pointer is kept to a selected point on the list, this being implemented by the SST-relative pointer sst.usedp. A direction called forward or ahead is arbitrarily defined as the direction on the list followed by chasing the sst-relative pointers cme.fp.

Picture missing

The basis of the algorithm is that the pointer moves forward on demand for page frames. It tries to approximate the "Least Recently Used," or LRU algorithm, where the least recently used page (not page frame) is the one which will be evicted to free its page frame. The page frame right ahead of the pointer (the one pointed to) contains the supposedly least-recently-used page. Going further and further down the list produces pages more and more recently used, until the page right behind the pointer is the most recently used. Since pages are referenced by every instruction that runs, it is impossible to thread them to represent true recency of use. Therefore, we translate "recently used" into "recently noticed as used." When we notice that a page has been used, we turn off the bit ptw.phu, in the PTW for that page, the bit via which the hardware communicates the fact that a page has been used. Thus, this bit being on in a given PTW indicates that the page has been used since this observation was last made.

Therefore, when a demand is made for a frame (via a call to find_core, in page_fault), the page at the head of the used list is inspected to see if it has indeed been used since last inspection. If so, it is now, clearly, the page most "recently noticed as used." Thus, the pointer moves forward, putting this page at the tail of the used list by so doing, in keeping with its newfound status as "most recently noticed as used." The "used" bit is turned off, pending the next inspection, and the next page is considered, until one is found whose used bit is off. Such a page is clearly the one which was seen most recently as used the furthest time in the past. This page is evicted from its main memory frame, and the latter is now free.

The algorithm just described is known in the literature as the "clock" algorithm, as the motion of the pointer around the used list is similar to the motion of a hand of a clock about the face of the clock.

There are several complications to this algorithm. Most important, if a page is found whose used bit is off (evicted, see above) by the scan of the pointer, this eviction would require a write to disk or paging device if the page has been stored into (modified) since it was brought into that page frame, as the information in its correct form exists only in main memory, and nowhere else. Thus, a modified page whose used bit is off, takes more work to evict than one that is not modified. Specifically, the I/O may take an indefinite time to complete, and the main memory request on hand must be satisfied immediately. Therefore, the pointer skips over pages that are modified, even though they are not used--they will be dealt with shortly. The pointer only stops when a page that is neither modified nor used is found--only this kind can be evicted with no I/O. The page multilevel algorithm also complicates matters some here,there are pages that are neither used nor modified which require I/O to evict, if the page multilevel algorithm wishes to migrate them to the paging device at this time; these pages are called "not-yet-on-paging-device," (ptw.nypd signifies this state). This will be dealt with in the next section.

Therefore, the pointer does not stop until it finds a page that is neither used (since last turning-off of the used bit), modified (since last writing), or not-yet-on-paging-device. Some pages are routinely skipped, such as those that are wired or abs-wired. Pages on which I/O is going on are not even in the list, and are thus not an issue. When such a page is found, it is evicted, and the frame which it had occupied returned to the caller of find_core.

In passing over modified and not-yet-on-paging-device pages, the pointer implicitly left work behind to be done. These pages should be evicted from main memory, but this could not be done on the spot, as the process that needed a page frame could be satisfied immediately with some other frame, not much worse, and could not wait for the indeterminate completion of these writes. Therefore, a procedure called claim_mod_core, in page_fault, exists to do the work which the replacement algorithm decided not to do, in order to satisfy its real-time constraint of producing a usable page-frame on the spot. It runs either at a later time than find_core, or is called by find_core when the latter encounters certain limit situations (see Section VIII). The procedure claim_mod_core maintains a second pointer into the used list, which is sst.wusedp (for "writing" used-pointer). Generally, it is pointing to the same place as the regular "usedp" clock-hand of the find_core routine. However, when a demand is made for a page-frame of main memory, find_core advances the "usedp" hand until a freeable, evictable frame is found. Thus, the distance between the wusedp hand and the usedp is the "cleanup" work that must be processed by claim_mod_core. The procedure claim_mod_core is invoked during page-fault processing at a time to overlap its operation, which may involve substantial computation inside the disk DIM, with the reading-in of the page necessary to satisfy the page fault. Note that this reading could not begin until a page-frame into which to read the page had been found, by find_core. claim_mod_core processes all page-frames between wusedp and usedp; those that are not used, but modified, have writes started for them, which removes their CMEs from the used list. In order for claim_mod_core to be able to distinguish the used-and-modified ones from the not-used-but-modified ones, find_core avoids turning off the used bits, leaving this for claim_mod_core. Pages "not-yet-on-paging-device" are migrated to the paging device, as appropriate, until wusedp and usedp again coincide. Note that these writes are started while no particular process is waiting for these writes to complete for any reason--when these writes are complete, the interrupt side will place these page frames at the head of the used list, making them excellent candidates for eviction if and only if they have not been used while or after being written.

The interaction of find_core, the replacer, and claim_mod_core, the purifier, may be stated as this: the replacement algorithm claims only pure (unmodified) pages. Those that are found impure, but would have been claimed, are left for the purifier to purify. When the purification is complete, these pages are again candidates for replacement.

There are a large number of call-side actions, such as deactivation and truncation, and some ALM actions, such as the discovery of zeros by the page-writing primitive (write_page in page_fault) that cause page-frames to become explicitly free; these actions all aid the replacement algorithm and simplify its task by putting these page frames at the head of the used list, wherever it currently is, making these frames immediately claimable by find_core.

The successful completion of any read operation places the CME for the frame into which the reading was done at the tail of the used list, as presumedly, the reason that this read occurred is that someone wanted the page, and thus, it is "most recently noticed as used" at the time of the completion of the read.

Papers about the Multics Page Replacement Algorithm:

Corbató, F. J. "A Paging Experiment with the Multics System," in Ingard, In Honor of P.M._Morse, M.I.T. Press, Cambridge, Mass., (1969), pp. 217-228 Greenberg, B. S., "An Experimental Analysis of Program Reference Patterns in the Multics Virtual Memory," M.I.T. Project MAC Technical Report TR-127, M.I.T. Dept. of Electrical Engineering, May, 1974 Greenberg, B.S., and Webber, S.H., "The Multics Multilevel Paging Hierarchy," in Proceedings of the 1975 IEEE Intercon, Institute of Electrical and Electronic Engineers, N.Y., 1975 —Preceding unsigned comment added by 12.53.38.125 (talk) 21:28, 27 March 2008 (UTC)

merge

I suggest moving the detailed descriptions of the various anticipatory paging techniques (the sections titled "Anticipatory paging", "Swap prefetch", "Pre-cleaning", etc.) from the "paging" article to the "page replacement algorithm" article. Then leave the "paging" article with only 2 sections on these techniques ("Anticipatory paging" and "Demand paging") that Wikipedia: Summary style summarize and link to more detailed articles ("page replacement algorithm" and "demand paging"). --68.0.124.33 (talk) 13:19, 5 March 2009 (UTC)

I don't think that's a good idea. The concept of Paging in itself is different from the techniques used to implement it. If a merge is required, it might make more sense to make the Page Replacement Algorithms a sub-section of Paging. --129.110.5.90 (talk) 07:00, 19 April 2010 (UTC)

• Oppose per the above reason. elektrikSHOOS 23:19, 6 July 2010 (UTC)

I agree that the abstract concept of Paging is different from the techniques used to implement it. Therefore, I propose moving the detailed descriptions of various paging implementations from the abstract "paging" article (the sections titled "Swap prefetch", "Pre-cleaning", etc.) to the more implementation-oriented "page replacement algorithm" article. --68.0.124.33 (talk) 14:18, 6 August 2010 (UTC)

According to the introductory paragraph of this article, "page replacement algorithms decide which memory pages to page out (swap out, write to disk) when a page of memory needs to be allocated." "Anticipatory paging" doesn't decided what pages to page out, it decides what pages to page in before they're referred to. If that moves here, this article should probably be renamed "paging algorithms", as it would cover more than page replacement algorithms. Guy Harris (talk) 02:21, 15 July 2011 (UTC)

Which OS?

Can you include in each section example implementations like operating systems that use that variant? —Preceding unsigned comment added by 96.224.69.6 (talk) 19:13, 10 August 2010 (UTC)

clock replacement unclear

i'm trying to do my homework and i'm pretty sure the explanation is not complete. I think you have to turn on the dirty bit when you get a page hit on the particular page. —Preceding unsigned comment added by 169.229.125.116 (talk) 04:03, 17 September 2010 (UTC) we can also add some algorithms in cru, —Preceding unsigned comment added by 115.248.98.27 (talk) 10:27, 30 September 2010 (UTC)

Second Chance - mistake

The last sentence of the paragraph states: "If all the pages have their reference bit set then second chance algorithm degenerates into pure FIFO algorithm." According to my understanding of the algorithm, it should be pure FIFO it all pages have their reference bit cleared, since then the oldest page will be replaced (like in FIFO) instead of being sent to the back of the queue. Dirk Gently (talk) 11:31, 2 March 2011 (UTC)

It degenerates into FIFO in both cases. If all reference bits are set, then each page in order will have its reference bit cleared and will be sent to the back of the queue. Once this has happened for all pages in the queue, all reference bits will be cleared and the oldest page will be at the front of the queue again, leading to a FIFO situation. --Runner5k (talk) 03:06, 11 March 2011 (UTC)

confusing

Starting with the section "The (h,k)-paging problem" up to and including "Conservative algorithms" is not explaining the subject in enought detail that somebody new to the matter will understand it. — Preceding unsigned comment added by Jangirke (talk • contribs) 02:25, 28 January 2014 (UTC)

This is a massive understatement. I'm familiar with most of these algorithms, but the explanations here are still useless without some indication of what h and k even are. Who even wrote all this and didn't think to define their variables? Sigh. 82.20.88.133 (talk) 10:47, 5 June 2015 (UTC)

Variants on LRU contains link to externally hosted pdf

I was disconcerted that a link within the article body prompted the downloaded of an externally hosted pdf. Shouldn't this be a link to a reference instead? — Preceding unsigned comment added by 50.35.176.228 (talk) 13:12, 9 May 2015 (UTC)

Possible references, based on Advances in Grid and Pervasive Computing: 7th International Conference

1. Armbrust, M., Fox, A., Griffith, R., Joseph, A.D., Katz, R.H., Konwinski, A., Lee, G., Patterson, D.A., Rabkin, A., Stoica, I., Zaharia, M.: Above the clouds: A berkeley view of cloud computing. EECS Department, University of California, Berkeley, Tech. Rep. UCB/EECS-2009-28 (February 2009), http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-28.html
2. Amazon.com, Inc., Amazon web services (2011), http://aws.amazon.com/s3/
3. Google Inc., Google app engine (2011), http://code.google.com/intl/en/appengine/
4. Microsoft, Windows azure (2011), http://www.microsoft.com/windowsazure/
5. Mell, P., Grance, T.: The NIST definition of cloud computing (draft): Recommendations of the national institute of standards and technology. NIST Special Publication 800-145 (Draft) (2011), http://csrc.nist.gov/publications/drafts/800-145/Draft-SP-800-145cloud-definition.pdf
6. Wright, A.: Ready for a web os? Commun. ACM 52, 16–17 (2009)
7. Podlipnig, S., Böszörmenyi, L.: A survey of web cache replacement strategies. ACM Comput. Surv. 35, 374–398 (2003)
8. Arlitt, M., Cherkasova, L., Dilley, J., Friedrich, R., Jin, T.: Evaluating content management techniques for web proxy caches. SIGMETRICS Perform. Eval. Rev. 27, 3–11 (2000)
9. Wessels, D.: Squid: The Definitive Guide. O’Reilly & Associates, Inc., Sebastopol (2004)
10. Abrams, M., Standridge, C.R., Abdulla, G., Fox, E.A., Williams, S.: Removal policies in network caches for world-wide web documents. SIGCOMM Comput. Commun. Rev. 26, 293–305 (1996)
11. Balamash, A., Krunz, M.: An overview of web caching replacement algorithms. IEEE Communications Surveys and Tutorials 6(1-4), 44–56 (2004)
12. Banditwattanawong, T., Hidaka, S., Washizaki, H., Maruyama, K.: Optimization of program loading by object class clustering. IEEJ Transactions on Electrical and Electronic Engineering 1 (2006)From Web Cache to Cloud Cache 15
13. Fielding, R., Gettys, J., Mogul, J., Frystyk, H., Masinter, L., Leach, P., Berners-Lee, T.: Rfc 2616, hypertext transfer protocol – http/1.1, United States (1999)
14. National Laboratory for Applied Network Research, Weekly squid http access logs, http://www.ircache.net/
15. Megiddo, N., Modha, D.S.: Outperforming lru with an adaptive replacement cache algorithm. Computer 37, 58–65 (2004)
16. Jeong, J., Dubois, M.: Cache replacement algorithms with nonuniform miss costs. IEEE Transactions on Computers 55, 353–365 (2006)
17. Chen, H., Xiao, Y., Shen, X.S.: Update-based cache access and replacement in wireless data access. IEEE Transactions on Mobile Computing 5, 1734–1748 (2006)
18. Geetha, K., Gounden, N.A., Monikandan, S.: Semalru: An implementation of modified web cache replacement algorithm. In: NaBIC, pp. 1406–1410. IEEE (2009)
19. Shin, S.-W., Kim, K.-Y., Jang, J.-S.: Lru based small latency first replacement (slfr) algorithm for the proxy cache. In: Proceedings of the 2003 IEEE/WIC International Conference on Web Intelligence, WI 2003, pp. 499–502. IEEE Computer Society, Washington, DC (2003)
20. Shim, J., Scheuermann, P., Vingralek, R.: Proxy cache algorithms: Design, implementation, and performance. IEEE Transactions on Knowledge and Data Engineering 11, 549–562 (1999)
21. Sarma, A.R., Govindarajan, R.: An Efficient Web Cache Replacement Policy. In: Pinkston, T.M., Prasanna, V.K. (eds.) HiPC 2003. LNCS (LNAI), vol. 2913, pp. 12–22. Springer, Heidelberg (2003)
22. Chand, N., Joshi, R., Misra, M.: Data profit based cache replacement in mobile environment. In: 2006 IFIP International Conference on Wireless and Optical Communications Networks, p. 5 (2006)
23. Xu, J., Hu, Q., Lee, W.-C., Lee, D.L.: Performance evaluation of an optimal cache replacement policy for wireless data dissemination. IEEE Transactions on Knowledge and Data Engineering 16, 125–139 (2004)
24. Yin, L., Cao, G., Cai, Y.: A generalized target-driven cache replacement policy for mobile environments. In: IEEE/IPSJ International Symposium on Applications and the Internet, p. 14 (2003)
25. Kim, K., Park, D.: Least popularity-per-byte replacement algorithm for a proxy cache. In: Intl. Conf. on Parallel and Distributed Systems, p. 0780 (2001)
26. Li, K., Nanya, T., Qu, W.: A minimal access cost-based multimedia object replacement algorithm. In: International Symposium on Parallel and Distributed Processing, p. 275 (2007)
27. Triantafillou, P., Aekaterinidis, I.: Web proxy cache replacement: Do’s, don’ts, and expectations. In: IEEE International Symposium on Network Computing and Applications, p. 59 (2003)
28. Chen, Y., Li, Z.-Z., Wang, Z.-W.: A ga-based cache replacement policy. In: Proceedings of 2004 International Conference on Machine Learning and Cybernetics, vol. 1, pp. 263–266 (August 2004)
29. El Aarag, H., Romano, S.: Improvement of the neural network proxy cache replacement strategy. In: Proceedings of the 2009 Spring Simulation Multiconference, SpringSim 2009, Society for Computer Simulation International, San Diego (2009)
30. Bolot, J.-C., Hoschka, P.: Performance engineering of the world wide web: application to dimensioning and cache design. Computer Networks and ISDN Systems 28, 1397–1405 (1996)

MGLRU and ELRU

I'm guessing they are variants of LRU? See https://lwn.net/Articles/894859/ and https://www.suonsivu.net/masters-thesis-Heikki-Suonsivu-1995.pdf The RedBurn (ϕ) 17:49, 8 February 2024 (UTC)