Swapping: Policies

Memory Pressure

forces the OS to start PAGING OUT pages to make room for actively-used pages

Minimize the Number of Cache Misses

Goal in picking a replacement policy for this cache

Average Memory Access Time (AMAT)

The number of cache hits and misses

AMAT = (Phit * Tm) + (Pmiss * Td)

Formula of AMAT

Definition of Tm, Td, P hit, and P miss

Tm - The cost of accessing memory

Td - The cost of accessing disk

P hit - The probability of finding the data item in the cache (a hit)

P miss - The probability of not finding the date in the cache (a miss)

Optimal Replacement Policy

• Lead to the fewest number of misses overall

• Replaces the page that will be accessed furthest in the future

• Resulting in the FEWEST POSSIBLE cache misses

• Serve only as a comparison point, to know how to close we are to PERFECT

Simple Policy: FIFO

• Pages are place in QUEUE

• The page tail of the queue is evicted

Belady’s Anomaly

We expect the cache hit rate to increase, but in FIFO, it gets worse

Simple Policy: Random

Picks a random page to replace under memory pressure

Using History

Lean on the past

2 Types of Historical Information

Recency - More recently page is accessed, more likely to be accessed again

Frequency - If page is accessed many times, it should NOT be replaced

Clock Algorithm

All pages of the system arranged in CIRCULAR list

Dirty Pages

Page has been MODIFIED

Page Selection Policy

The OS has to decide WHEN to bring a page into memory

Prefetching

The OS GUESS that a page is about to be used

Clustering/Grouping

Collect a number of PENDING WRITES in memory and write them to disk in ONE WRITE

Thrashing

• Memory is OVERSCRIBED

• Memory demands set of processes EXCEEDS to available physical memory