demand paging:- not all of a process's virtual address space

needs to be loaded in main memory at any given time. Each

page can be either:

o In memory (physical page frame)

o On disk (backing store)

loading the page into the memory from disk when required is

called as demand paging

page faults:-when a process references a page that is in the

backing store,the page fault occurs

replacement algorithms:-various approaches to replace pages

from disk to memory on occurence of page fault

* Page fetching: when to bring pages into memory.

* Page replacement: which pages to throw out of memory.

Page Replacement

* Once all of memory is in use, will need to throw out

one page each time there is a page fault.

* Random: pick any page at random (works surprisingly well!)

* FIFO: throw out the page that has been in memory longest.

* MIN: The optimal algorithm requires us to predict the

future.

* Least Recently Used (LRU): use the past to predict the

future.

* Strange but true: for some placement policies, such as

FIFO, adding more memory can sometimes cause paging

performance to get worse. This is called "Belady's Anomaly"

after Les Belady, who was the first person to notice it.

* Implementing LRU: need hardware support to keep track

of which pages have been used recently.

o Perfect LRU?

+ Keep a register for each page, store

system clock into that register on each memory reference.

+ To choose page for placement, scan through

all pages to find the one with the oldest clock.

+ Hardware costs would have been prohibitive

in the early days of paging; also, expensive to scan all

pages during replacement.

o In practice nobody implements perfect LRU.

Instead, we settle for an approximation that is efficient.

Just find an old page, not necessarily the oldest.

* Clock algorithm (called second chance algorithm in

Silberschatz et al.): keep reference bit for each page

frame, hardware sets the reference bit whenever a page is

read or written. To choose page for placement:

o Start with FIFO approach: cycle through pages in

order circularly.

o If the next page has been referenced, then don't

replace it; just clear the reference bit and continue to the

next page.

o If the page has not been referenced since the

last time we checked it, then replace that page.

* Dirty bit: one bit for each page frame, set by

hardware whenever the page is modified. If a dirty page is

replaced, it must be written to disk before its page frame

is reused.

* The clock algorithm typically gives additional

preference to dirty pages. For example, if the reference but

for a page is clear, but the dirty bit is set, don't replace

this page now, but clear the dirty bit and start writing the

page to disk.

* Free page pool: some systems keep a small list of

clean pages that are available immediately for replacement.

o During replacement, take the page that has been

in the free pool the longest, then run the replacement

algorithm to add a new page to the free pool.

o Pages in the free pool have their exists bit

off, so any references to those pages cause a page fault

o If a page fault occurs for a page in the free

pool, remove it from the free pool and put it back in

service; much faster than reading from disk.

o Provides an extra opportunity for recovery if we

make a poor page replacement decision.

Usually thrashing refers to two or more processes accessing

a shared resource repeatedly such that serious system

performance degradation occurs because the system is

spending a disproportionate amount of time just accessing

the shared resource. Resource access time may generally be

considered as wasted, since it does not contribute to the

advancement of any process. This is often the case when a

CPU can process more information than can be held in

available RAM; consequently the system spends more time

preparing to execute instructions than actually executing them.