Page replacement algos (8+9)

Question 1

goal of page replacement algorithm (policy)

Answer 1

manage page access from pages referenced in virtual address space so as to minimize page faults for all pages belonging to a process

Question 2

Replacement algos run on which data structure?

Answer 2

Strings of memory page references - page references are pointers to actual memory pages

Question 3

Basic steps followed when page fault occurs

Answer 3

Select a page from a string of referenced pages (pages scheduled to be run)
retrieve page from memory storage and find free frame - if full, evict a victim frame
selected frame loaded into victim frame
victim frame loaded into TLB or secondary storage
update page table
OS exits kernel mode and continues from where it was interrupted (by page fault trap)

Question 4

Explain random page replacement

Answer 4

Simplest

random frame evicted

Question 5

issues with random page replacement

Answer 5

unpredictable doesn’t achieve goal of minimizing page faults and does not fit with principle of locality

Question 6

principle of locality

Answer 6

tendency of CPU to access same set of mem locations repetitively over a short period of time - since these locations correspond to a few processes that CPU scheduled to execute during the given period

Question 7

Basic idea of FIFO page replacement

Answer 7

allow every page to spend same amount of time in phys mem - first in first out - page that has been loaded in the longest is the first to be swapped out when a new page needs to be swapped in

maintains a linked list of all pages which keeps the order in which pages entered memory - page at front of list is replaced

Question 8

advantage of FIFO

Answer 8

easy to implement - single pointer needed

Question 9

Main disadvantage of FIFO

Answer 9

doesnt keep frequently used pages in main mem - page that has been in longest could be the most used page but FIFO will swap it out (and cause page faults)

Question 10

Explain the OPT algorithm (page replacement)

Answer 10

used as benchmark algorithm
Assumes that page that will not be used for longest time should be selected for replacements

BUT - needs to assume perfect knowledge of the future
If an algorithm is within 5% of OPT then it’s effective

Question 11

Explain LRU page replacement algorithm

Answer 11

Least Recently Used uses a record of page page replacement to replace pages that have not been used recently
On each page replacement, it places new page at head of list. The list tail is removed.

Implemented with linked list

Question 12

Main advantage of LRU

Answer 12

accounts for principle of locality - same set of pages tend to be frequently used while the process is executing, so these pages should not be swapped out of main mem

Question 13

How LRU implements a counter

Answer 13

Every page has associated counter, every time a page is used, counter is incremented (represents time at which page was used in main mem) - we now replace the page with the smallest time value (oldest page)

Question 14

Relationship between number of frames and number of faults (FIFO)

Answer 14

more frames = more faults

Question 15

What is Belady’s anomaly?

Answer 15

increasing number of page frames increases the page faults for a given mem access pattern. Seen in fifo, random and second chance algorithms. Does not occur for stack based algorithms

Question 16

Stack based algorithm?

Answer 16

can be shown that if there are N pages in memory, then that set of pages is a subset of the pages that would be in memory with N+1 frames

e.g. for LRU - using K frames will always be a subset of k+N frames and any page faults that occur for k+N frames will also occur for k+N frames

Question 17

Explain MRU algorithm

Answer 17

Most recently used page is replaced

Based on argument that page with the largest count has been used enough and new pages have yet to be used

Question 18

Assumptions that perfect LRU makes and issues with this

Answer 18

OS keeps time stamp for each page referenced and keeps doubly linked list of pages ordered by time referenced

too expensive

Question 19

clock replacement algorithm

Answer 19

uses a reference bit to approximate LRU - achieve benefits of LRU without overhead. Reference bit corresponds to used-bit that is set for each page reference

Question 20

What does it mean if the used bit is not set and where is used-bit stored

Answer 20

not seet - page not been referenced in a long time

stored for each page in page table or TLB

Question 21

Explain the 3 stages that a page can be in - that is determined by the referenced bit

Answer 21

bit = 1: page present in memory and recently used - no page fault
bit = 0: page is present in memory but not recently used. If page fault - if page in TLB (for example), the page replacement algorithm will only change reference bit to 1
page not in mem - look at clock hand

Question 22

Explain how the clock algo works

Answer 22

arranges physical pages in a conceptual circle with single pointer (clock hard) pointing to one page at a given time
hand pointing to page with ubit = 1: flip to 0 and increment pointer (clock hand) to next page
If find a page where ubit = 0: replace that page and then mark as recently used (flip ubit to 1) and increment pointer again

Question 23

Best and worst case for clock algorithm

Answer 23

best - next page will have a cleared reference bit (reference-bit = 0)
worst - all reference bits = 1

Question 24

More accurate way to implement clock algorithm

Answer 24

extra reference bits

Page fault would require a search through all pages to check which one is oldest

Question 25

Issues with clock algorithm

Answer 25

best - next page will have a cleared reference bit (reference-bit = 0)
worst - all reference bits = 1 - have to loop through all pages
Computational cost for placing pages whose dirty bits are set - before dirty page is replaced must be written to disk before it is replaced

Question 26

what does it mean if the clock hand s moving fast vs slow

Answer 26

slow - many page faults

fast - fewer page faults

Question 27

Dirty page

Answer 27

page which is modified in a buffer cache (been swapped out of secondary storage and into a main mem frame) - dirty bit is set in page table
one dirty bit for each physical page frame -

Question 28

How does the clock algorithm account for dirty pages?

Answer 28

give additional preference to dirty pages
e.g. if reference bit is cleared but dirty bit is set - algorithm will not replace the page now but rather clear the dirty bit and start writing the page to secondary storage - dirty pages always survive one sweep of the clock hand

Question 29

Second chance clock algorithm

Answer 29

if reference bit is cleared but dirty bit is set - algorithm will not replace the page now but rather clear the dirty bit and start writing the page to secondary storage - dirty pages always survive one sweep of the clock hand

to be replaced reference and dirty bits both have to be cleared

Question 30

Basic reasoning behind N-chance clock algorithm

Answer 30

give frequently used pages as much of a chance of possible to remain in main mem before being replaced
Algorithm keeps a counter for each page - clock hand can pass each page N times before replacing it

Question 31

How N-chance clock algorithm works

Answer 31

Counter is stored (per page in cache) to indicate no. sweeps
Given page fault - check ubit. If 1, used bit is cleared and counter also cleared (because recently used in the last sweep). used bit = 0, increment counter. If counter = N, replace page and set its used bit = 1

Question 32

Disadvantage of N-chance clock algorithm

Answer 32

Extra parameter

more expensive - overhead because uses additional cache mem to store N and account for dirty pages

Question 33

larger vs smaller values for N in N-chance clock algorithm

Answer 33

Larger values approximate LRU better since least recently used pages spend longer in main mem. Lower N - selects more recently used pages for replacement but is more efficient because for large N - more revolutions of the clock need to be done searching for a page where counter = N