Operating systemsLesson 3 of 3 in the course Memory management

Page Replacement: Policies, Analysis, and Memory Reclamation

5 flashcards · 5 quiz questions · 5 match pairs · 5 fill-in sentences · English

Save course
Lesson progress
0 / 5

Your progress is kept in this browser only.Sign up to save it

Summary

An operating system using paging divides virtual memory and physical memory into fixed-size units called pages and frames. A page table maps a process's virtual pages to physical frames. Only some of a process's pages need to be in physical memory at a given time; other pages can remain on storage.

When a process references a page that is not currently in memory, a page fault occurs. The operating system must locate the page on storage and bring it into a physical frame. If a free frame is available, it can use that frame. If no free frame is available—or the number of free frames has fallen below a system threshold—the operating system must choose a page to remove.

All flashcards

What does a page replacement algorithm do?
It selects a resident page to evict when a requested page needs a frame and no suitable free frame is available.
What does a dirty bit indicate?
The page has been modified and may need to be written to storage before its frame is reused.
What is precleaning?
Writing anticipated victim pages to storage before their frames are urgently needed.
What does OPT do?
It evicts the page whose next use is farthest in the future.
What is a process's working set?
The pages it is expected to use during a particular time interval.

Quiz questions

  1. How does the theoretical OPT page-replacement algorithm choose a victim?Answer: It evicts the page whose next use is farthest in the future.
  2. What rule defines a marking algorithm during a stage?Answer: It does not evict pages marked during that stage.
  3. What property makes a paging algorithm conservative with cache size kk?Answer: It incurs at most kk faults on any consecutive sequence containing at most kk distinct pages.
  4. What is Bélády's anomaly in page replacement?Answer: Adding frames can increase the number of page faults for some request sequences.
  5. What can happen when LRU holds NN pages while a program repeatedly cycles through N+1N+1 pages?Answer: Each access can cause a page fault.

Based on the Wikipedia article Page replacement algorithm, licensed CC BY-SA 4.0. Adapted into a summary, flashcards and quizzes.

More in Operating systems

All Operating systems lessons
Operating systemsProcess Management: Resources, Lifecycle, Scheduling, and IPC5 flashcards · 5 quiz questions · 4 gamesPlay free →Operating systemsDevice Drivers: Interfaces, Frameworks, Virtualization, and Security5 flashcards · 5 quiz questions · 4 gamesPlay free →Operating systemsThreads: Execution, Scheduling, Synchronization, and Threading Models5 flashcards · 5 quiz questions · 4 gamesPlay free →Operating systemsOperating-System Scheduling: Algorithms, Policies, and Kernel Implementations5 flashcards · 5 quiz questions · 4 gamesPlay free →Operating systemsDeadlock Conditions, Handling Strategies, and Distributed Variants5 flashcards · 5 quiz questions · 4 gamesPlay free →Operating systemsUnix Inodes: Metadata, Links, Identity, and Storage5 flashcards · 5 quiz questions · 4 gamesPlay free →