List the steps needed to perform page replacement. Explain the different page replacement policies. Also list out the main requirements, which should be satisfied by a page replacement policy. (8) Ans: The steps needed to perform page replacement are: 1.Determine which page is to be removed from the memory. 2.Perform a page-out operation. 3.Perform a page-in operation. Different page replacement algorithms are briefly described below: 1. First-in, first-out The first-in, first-out (FIFO) page replacement algorithm is a low-overhead algorithm. Here the operating system keeps track of all the pages in memory in a queue, with the most recent arrival at the back, and the earliest arrival in front. When a page needs to be replaced, the page at the front of the queue (the oldest page) is selected. Advantage: FIFO is cheap and intuitive. Disadvantage: 1. Performs poorly in practical application. 2. Suffers from Belady’s anomaly. 2. Not recently used The not recently used (NRU) page replacement algorithm works on the following principle: when a page is referenced, a referenced bit is set for that page, marking it as referenced. Similarly, when a page is modified (written to), a modified bit is set. At a certain fixed time interval, the clock interrupt triggers and clears the referenced bit of all the pages, so only pages referenced within the current clock interval are marked with a referenced bit. When a page needs to be replaced, the operating system divides the pages into four classes: • Class 0: not referenced, not modified • Class 1: not referenced, modified • Class 2: referenced, not modified • Class 3: referenced, modified. The NRU algorithm picks a random page from the lowest category for removal. 3. Optimal page replacement algorithm The optimal page replacement algorithm (also known as OPT )is an algorithm that works as follows: when a page needs to be swapped in, the operating system swaps out the page whose next use will occur farthest in the future. For example, a page that is not going to be used for the next 6 seconds will be swapped out over a page that is going to be used within the next 0.4 seconds. Disadvantage: This algorithm cannot be implemented in the general purpose operating system because it is impossible to compute reliably how long it will be before a page is going to be used. The main requirements, which should be satisfied by a page replacement policy, are: 1. Non-interference with the program’s locality of reference: The page replacement policy must not remove a page that may be referenced in the immediate future. 2. The page fault rate must not increase with an increase in the memory allocation for a program.