Podcast
Questions and Answers
What is the primary goal of a page-replacement algorithm?
What is the primary goal of a page-replacement algorithm?
What is the effect of adding more frames to the FIFO algorithm?
What is the effect of adding more frames to the FIFO algorithm?
What is the purpose of a frame-allocation algorithm?
What is the purpose of a frame-allocation algorithm?
What is the characteristic of a page reference string?
What is the characteristic of a page reference string?
Signup and view all the answers
Which of the following is NOT a characteristic of the FIFO algorithm?
Which of the following is NOT a characteristic of the FIFO algorithm?
Signup and view all the answers
What is the effect of repeated access to the same page in a page reference string?
What is the effect of repeated access to the same page in a page reference string?
Signup and view all the answers
What is the purpose of evaluating a page-replacement algorithm?
What is the purpose of evaluating a page-replacement algorithm?
Signup and view all the answers
What is Belady's Anomaly?
What is Belady's Anomaly?
Signup and view all the answers
How is the performance of a page-replacement algorithm typically evaluated?
How is the performance of a page-replacement algorithm typically evaluated?
Signup and view all the answers
What is the relationship between the number of frames available and the number of page faults?
What is the relationship between the number of frames available and the number of page faults?
Signup and view all the answers
Study Notes
Page Replacement Algorithms
- 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
Least Recently Used (LRU) Algorithm
- Replaces the page that has not been used for the most amount of time
- Associates time of last use with each page
- Performs better than FIFO but worse than OPT (12 faults)
Thrashing
- 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
Handling a Page Fault
- 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
Page Replacement
- 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
Page and Frame Replacement Algorithms
- 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
First-In-First-Out (FIFO) Algorithm
- 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)
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Related Documents
Description
Determine the optimal page replacement algorithm in Operating System Concepts, 9th Edition by Silberschatz, Galvin and Gagne. Learn how to identify the best approach based on the reference string.
