PAGE REPLACEMENT:
->Prevent over-allocation of memory by modifying page-fault service routine to include page replacement
->Use modify (dirty) bit to reduce overhead of page transfers – only modified pages are written to disk

->Page replacement completes separation between logical memory and physical memory – large virtual memory can be provided on a smaller physical memory

Basic Page Replacement:
1.Find the location of the desired page on disk
2.Find a free frame:
-If there is a free frame, use it
-If there is no free frame, use a page replacement algorithm to select a victim frame
-Write victim frame to disk if dirty
3.Bring the desired page into the (newly) free frame; update the page and frame tables
4.Continue the process by restarting the instruction that caused the trap

=>Note now potentially 2 page transfers for page fault – increasing EAT

Page and Frame Replacement Algorithms:
=>Frame-allocation algorithm determines
-How many frames to give each process
-Which frames to replace
=>Page-replacement algorithm
-Want lowest page-fault rate on both first access and re-access
=>Evaluate algorithm by running it on a particular string of memory references (reference string) and computing the number of page faults on that string
-String is just page numbers, not full addresses
-Repeated access to the same page does not cause a page fault

-Results depend on number of frames available

Page Replacement Algorithms:
-FIFO
-OPTIMAL REPLACEMENT
-LRU REPLACEMENT

-SECOND CHANCE PAGE REPLACEMENT

-FIFO:First In First Out (FIFO) –
This is the simplest page replacement algorithm. In this algorithm, the operating system keeps track of all pages in the memory in a queue, the oldest page is in the front of the queue. When a page needs to be replaced page in the front of the queue is selected for removal.
-OPTIMAL REPLACEMENT:
In this algorithm, pages are replaced which would not be used for the longest duration of time in the future.
-LRU REPLACEMENT:
Least Recently Used –In this algorithm page will be replaced which is least recently used.
-SECOND CHANCE PAGE REPLACEMENT:
the Second Chance replacement policy is called the Clock replacement policy.
In the Second Chance page replacement policy, the candidate pages for removal are consider in a round robin matter, and a page that has been accessed between consecutive considerations will not be replaced.The page replaced is the one that - considered in a round robin matter - has not been accessed since its last consideration.