Operating System Concepts: Optimal Page Replacement Algorithm

Questions and Answers

To achieve the lowest page-fault rate on both first access and re-access (correct)

To minimize the number of page faults on the first access

To maximize the number of page faults on the re-access

To allocate frames to each process equally

It has no effect on the number of page faults

It may increase or decrease the number of page faults, depending on the reference string (correct)

It always increases the number of page faults

It always reduces the number of page faults

To manage the memory hierarchy

To allocate frames to each process based on its priority

To determine the optimal page-replacement strategy

To determine how many frames to give each process and which frames to replace (correct)

It includes only page numbers Signup and view all the answers

It is an optimal page-replacement algorithm Signup and view all the answers

It does not cause a page fault Signup and view all the answers

To compare the performance of different algorithms Signup and view all the answers

A phenomenon where adding more frames to a system increases the number of page faults Signup and view all the answers

By evaluating its performance on a particular string of memory references Signup and view all the answers

The number of page faults depends on the page-replacement algorithm and the reference string Signup and view all the answers

Study Notes

Optimal algorithm: replaces the page that will not be used for the longest period of time
Can't know the future, so it's used for measuring performance of other algorithms

Occurs when a process does not have enough pages, leading to a high page-fault rate
Page fault -> replace existing frame -> quickly need replaced frame back -> leads to low CPU utilization, increase in degree of multiprogramming, and addition of another process to the system
Thrashing: a process is busy swapping pages in and out

Restart the instruction that caused the page fault
Steps: find location of desired page on disk, find a free frame, bring desired page into free frame, update page and frame tables, and continue process

Prevents over-allocation of memory by modifying page-fault service routine to include page replacement
Uses 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, allowing for large virtual memory on smaller physical memory

Frame-allocation algorithm determines how many frames to give each process and which frames to replace
Page-replacement algorithm aims for lowest page-fault rate on both first access and re-access
Evaluated by running on a particular string of memory references (reference string) and computing the number of page faults

Reference string: 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1
3 frames: 15 page faults
Can vary by reference string, and adding more frames can cause more page faults (Belady's Anomaly)