Page Replacement

Page replacement: -                                                                            When the number of available real memory frames on the free list becomes low, a page stealer is invoked. A page stealer moves through the Page Frame Table (PFT), looking for pages to steal.

The PFT includes flags to signal which pages have been referenced and which have been modified. If the page stealer encounters a page that has been referenced, it does not steal that page, but instead, resets the reference flag for that page. The next time the clock hand (page stealer) passes that page and the reference bit is still off, that page is stolen. A page that was not referenced in the first pass is immediately stolen.

The modify flag indicates that the data on that page has been changed since it was brought into memory. When a page is to be stolen, if the modify flag is set, a page out call is made before stealing the page. Pages that are part of working segments are written to paging space; persistent segments are written to disk.

Figure 1. Page Replacement Example. The illustration consists of excerpts from three tables. The first table is the page frame table with four columns that contain the real address, the segment type, a reference flag, and a modify flag. A second table is called the free list table and contains addresses of all free pages. The last table represents the resulting page frame table after all of the free addresses have been removed.   

 In addition to the page-replacement, the algorithm keeps track of both new page faults (referenced for the first time) and repage faults (referencing pages that have been paged out), by using a history buffer that contains the IDs of the most recent page faults. It then tries to balance file (persistent data) page outs with computational (working storage or program text) page outs.

When a process exits, its working storage is released immediately and its associated memory frames are put back on the free list. However, any files that the process may have opened can stay in memory.

Page replacement is done directly within the scope of the thread if running on a uniprocessor. On a multiprocessor system, page replacement is done through the lrud kernel process, which is dispatched to a CPU when the minfree threshold has been reached. Starting with AIX® 4.3.3, the lrud kernel process is multithreaded with one thread per memory pool. Real memory is split into evenly sized memory pools based on the number of CPUs and the amount of RAM. The number of memory pools on a system can be determined by running the vmstat -v command.

You can use the vmo -r -o me pools= <number of memory pools> command to change the number of memory pools that will be configured at system boot. The values for the minfree and maxfree parameters in the vmo command output is the sum of the min free and max free parameters for each memory pool.

1.  RAND (Random)

• choose any page to replace at random
• assumes the next page to be referenced is random
• can test other algorithms against random page replacement

2. MIN (minimum) or OPT (optimal):

• Be lady’s optimal algorithm for the minimum number of page faults
• replace the page that will be referenced furthest in the future or not at all
• problem: we cannot implement it, because we cannot predict the future
• this is the best case
• can use it to compare other algorithms against

3. FIFO (First In, First Out):

• select the page that has been in main memory the longest
• use a queue (data structure)
• problem: although a page has been present for a long time, it may be really useful
• Windows NT and Windows 2000 use this algorithm, as a local page replacement algorithm (described separately), with the pool method (described in more detail separately)
• create a pool of the pages that have been marked for removal
• manage the pool in the same way as the rest of the pages
• if a new page is needed, take a page from the pool
• if a page in the pool is referenced again before being replaced in memory, it is simply reactivated
• this is relatively efficient

4. LRU (Least Recently Used):

• choose the page that was last referenced the longest time ago
• assumes recent behavior is a good predictor of the near future
• can manage LRU with a list called the LRU stack or the paging stack (data structure)
• In the LRU stack, the first entry describes the page referenced least recently, the last entry describes to the last page referenced.
• if a page is referenced, move it to the end of the list
• problem: requires updating on every page referenced
• too slow to be used in practice for managing the page table, but many systems use approximations to LRU

5. NRU (Not Recently Used):

• as an approximation to LRU, select one of the pages that has not been used recently (as opposed to identifying exactly which one has not been used for the longest amount of time)
• keep one bit called the "used bit" or "reference bit", where 1 => used recently and 0 => not used recently
• variants of this scheme are used in many operating systems, including UNIX and Macintosh
• Most variations use a scan pointer and go through the page frames one by one, in some order, looking for a page that has not been used recently.

                          

SUBMITTED BY:-Diksha

                 Class:-B.sc 2^nd year (c.s)

                 Roll no.:-2319

                 Topic:-Page Replacement