Page replacement

1. Page Replacement Davin.J.Abraham SRM/ M.Tech /DB 1701310002

2. What is 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. In the paging memory-management scheme, the operating system retrieves data from secondary storage in same-size blocks called  pages . Advantage: is that it allows the physical address space of a process to be  non-contiguous. Before paging came into use, systems had to fit whole programs into storage contiguously, which caused various  storage and fragmentation problems.

3. 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 . The operating system must then take control and handle the page fault, in a manner invisible to the program. Therefore, the operating system must: Determine the location of the data in secondary storage. Obtain an empty  page frame  in RAM to use as a container for the data. Load the requested data into the available page frame. Update the  page table  to show the new data . A  page table  is the data structure used by a  virtual memory  system in a  computer   operating system  to store the mapping between  virtual addresses  and  physical addresses . Virtual addresses are those unique to the accessing  process . Physical addresses are those unique to the hardware, i.e.,  RAM . Return control to the program, transparently retrying the  instruction  that caused the page fault.

4. Need for Page Replacement Until there is not enough RAM to store all the data needed The process of obtaining an empty page frame does not involve removing another page from RAM. But If all page frames are non-empty, obtaining an empty page frame requires choosing a page frame containing data to empty . Efficient paging systems must determine the page frame to empty by choosing one that is least likely to be needed within a short time Limited physical memory --> limited number of frame --> limited number of frame allocated to a process . Thus we need various Page Replacement Algorithms

5. Page Replacement Algorithms FIFO page replacement Optimal page replacement LRU page replacement LRU-Approximation page replacement Counting-Based page replacement

6. FIFO-PR First In First Out Page Replacement Algorithm I s a low-overhead algorithm that requires little book-keeping 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 oldest arrival in front. When a page needs to be replaced, the page at the front of the queue (the oldest page) is selected Easy to understand and program.

7. FIFO Example

8. Drawbacks of FIFO-PR A page which is being accessed quite often may also get replaced because it arrived earlier than those present Ignores locality of reference. A page which was referenced last may also get replaced, although there is high probability that the same page may be needed again. Performance is not always good. Suffers from Belady’s Anomaly Page fault increases with increase in number of frames. Thus, it is rarely used in its unmodified form.

9. Least Recently Used Algorithm Free from Belady’s Anomaly . LRU keeps track of page usage over a short period of time 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 Problem : How to order the frame defined by the time of last use. Solution : Counters Queue

10. LRU example

11. LRU-Expensive but Effective 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.

12. Thank You