Virtual Memory

Typical range of parameters for virtual memory
block (page) size          512-8192 bytes
hit time                           1-10 clock cycles
miss penalty                  100,000-600,000 clocks
(access time)                  (100,000-500,000 clocks)
(transfer time)                 (10,000-100,000 clocks)
miss rate                          0.00001% - 0.001%
main memory size          4 MB - 2048 MB

compare to cache these figure are 10x - 100,000x
cache miss is 4 -20 x costly as cache hit
page fault is 1000 - 10,000 x costly as page hit
page fault latency 1-100ms which a 10 MIPS processor can execute 10,000 - 1,000,000 instructions.

Mapping VA to PA

page table indexed by virtual page number.
hashing VA to the size of the number of physical pages (inverted page table)
cache, called Table Lookaside Buffer (TLB), is used for address translation ( to avoid the pagetable being paged out)

Typical parameters for TLB
block size           4-8 bytes (1 page-table entry)
hit time               1 clock
miss penalty      10-30 clocks
miss rate             0.1%-2%
TLB size             32-8192 bytes

one-level mapping
two-level mapping  : segment number, page number

paging vs segmentation
paging : one dimension, large contiguous linear space
segmentation : two dimensions, segment and offset, variable size, contiguous only in a segment.

Replacement algorithm

different from cache
* page faults are very costly
* latency is large, can perform memory management
* VM run on multitask

Thrashing, very high traffic between main memory and sec. mem.
Working set : the footprint of a program execution over a short period of time.

How to find working set

W(t,w)  the working set at time t for window w.  It is the set of pages referenced in the last w seconds at time t.
1 when page fault, add a new page to the working set
2 from set of pages not ref. within w, delete LRU
   otherwise let the set grow
3 if two or more pages not ref. within w, delete two LRU pages

w is measured by process time.

Page-fault frequency method

high page fault signals the change in phase, new working set
1 threshold Z
2 when page fault, estimate freq. f = 1/(t1-t0)
3 f > Z assume change phase, add page to working set
4 f < Z assume stable. add new page, remove old page (LRU)
5 f < Z over some period, assume stable and dead pages, reduce working set and delete unref. page (LRU)

How to allocate the number of pages to a program

optimal is to get least page-fault rate.  (multiprocess)
let Ri(xi)  be fault rate of process i with xi be the memory allocation.
optimal in the following sense :

            d Ri(x)/dx  x=xi  = d Rj(x)/dx x = xj

fault rate for each process for their respective allocation are equal.
optimum allocation depends on fault rate derivatives.

Summary : working set VS page-fault frequency
working set
 page-fault frequency
assumption immediate future will be like the recent past transient between two program phases signaled by higher than normal fault rate
implementation difficult because of sliding window observable quantities use hardware logging