Page Replacement Algorithms

Page Replacement Algorithms

1. Page replacement algorithms U baidullah alias kashif MSCCN-III Sukkur IBA.

2. Paging :- In computer operating systems, paging is one of the memory-management schemes by which a computer can store and retrieve data from secondary storage for use in main memory. Page fault The main functions of paging are performed when a program tries to access pages that are not currently mapped to physical memory (RAM). This situation is known as a page fault.

3. 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. Page replacement algorithm

4. The clock algorithm keeps a circular list of pages in memory, with the "hand" (iterator) pointing to the last examined page frame in the list. Clock

5. 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. Then, the clock hand is incremented and this process is repeated until a page is found with R = 0

6. 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 & NRU

7. ARC improves the basic LRU strategy by splitting the cache directory into two lists, T1 and T2, for recently and frequently referenced entries . In turn, each of these is extended with a ghost list (B1 or B2), which is attached to the bottom of the two lists. These ghost lists act as scorecards by keeping track of the history of recently evicted (expelled) cache entries, and the algorithm uses ghost hits to adapt to recent change in resource usage . Adaptive replacement cache

8. T1, for recent cache entries. T2, for frequent entries, referenced at least twice. B1, ghost entries recently evicted from the T1 cache, but are still tracked. B2, similar ghost entries, but evicted from T2. T1 and B1 together are referred to as L1, a combined history of recent single references. Similarly, L2 is the combination of T2 and B2

9. . . . [ B1 <-[ T1 <-!-> T2 ]-> B2 ] . …. [ ……………. . . . [ . . . . . . ! . .^. …………...... ] …… . . . ] [ fixed cache size (c) ]