22 - Swapping Policies

Memory Pressure

forces the OS to start paging out to make room for actively-used pages

Encapsulated

deciding which page to evict is _ within the replacement policy of the OS

Minimize the number of cache misses

cache management, goal in picking a replacement policy for this cache is to _ _ _ _ _ _

(Phit * Tm) + (Pmiss * Td)

formula of AMAT

Cost of accessing memory

meaning of Tm

Cost of accessing disk

meaning of Td

Probability of finding data

meaning of Phit

Probability of not finding data

meaning of Pmiss

Optimal Replacement Policy

leads to the fewest number of misses overall

Future

replaces the page that will be accessed furthest in the _ , optimal replacement policy

Fewest possible

resulting in the _ _ cache misses , optimal replacement policy

Optimal Replacement Policy

serve only as a comparison point, to known how close we are to perfect

FIFO

pages are placed in a queue when they enter the system

Belady’s Anomaly

expect the cache hit rate to increase when the cache gets larger. But in this case, with FIFO, it gets worse

Random

picks a random page to replace under memory pressure

History

lean on the past and use _

Recency

the more recently a page has been accessed the more likely it will be accessed again

LRU

algorithm of recency

Frequency

if a page has been accessed many times, it should not be replaced as it clearly has some value

LFU

algorithm of frequency

No Locality Workload

each reference is to a random page within the set of accessed page

100

workload accesses _ unique pages over time

Random

choosing the next page to refer to at _

Every memory reference

to keep track of which pages have been least-and-recently used, the system has to do some accounting work on _ _ _ (implementing historical algorithm)

Referenced, 1

approximating LRU, whenever a page is _ the use bit is set by hardware to _

Never clears, OS

approximating LRU, hardware _ _ clears the bit; though that is the responsibility of the _

Clock Algorithm

all pages of the system arranged in a circular list

Clock Algorithm

a clock hand points to some particular page to begin with

0

clock algorithm, the algorithm continues until it finds a use bit that is set to _

Dirty Pages

the hardware include a modified bit or dirty bit

Prefetching

the OS guess that a page is about to be used, and this bring it in ahead of time

Clustering, Grouping

collect a number of pending writes together in memory and write them to disk in one write

Thrashing

memory is oversubscribed and the memory demands of the set of running processes exceeds the available physical memory