Section notes for CS162 
Section #9, April 2, 2002 
Barbara Hohlt <hohltb@cs.berkeley.edu>

CACHING and TLBs
  - TLB, Translation Lookaside Buffer. Caching applied to
    address translation.
  - Direct Mapped - restrict each virtual page to use specific TLB entry 
  - Set Associative - parition TLB into N separate banks. Select entry with low
    order virtual page number bits. Compare all N entries in parallel. 
  - Fully Associative - Compare entire TLB in parallel. Only one entry per bank.

EFFECTIVE ACCESS TIME IN TLB
	= P(hit) * cost of hit + P(miss) * cost of miss 

EX: 20 ns ==> TLB access
    100 ns ==> Memory access
    P(hit) = .80

    EAT = .80(120) + .20(220) = 140 ns

DEMAND PAGING
  - Each page-table entry contains a 'valid' bit which
    indicates that the associated page is BOTH legal
    AND in memory. On x86 is low-order bit; if 0, valid, 
    if 1, not valid. 
  - If not valid and legal, page table entry holds some OS-specific 
    information to maintain location of page on disk. Generally will be 
    a disk block number
  - When page table entry is not valid, check if the address
	is both legal and memory resident.
  - If illegal address, terminate process.
  - If legal address, do pagefault
    - allocate new page, read from disk, restart faulting instruction

  - NOTE: Page tables themselves can be paged!
    - Recall two-level page table structure
    - Top-level table always present
    - Second-level tables may be swapped out...

PAGE REPLACEMENT

  - Random - solution for TLBs. Implemented in hardware.
  - FIFO - Replace oldest page. Bad because removes hot pages.  
  - MIN - Replace the page that will not be used for the longest
	  period of time. Optimal algorithm. Requires future knowledge. 
  - LRU - Replace the page that has not been used for the longest
	  period of time. Approximates MIN.

LRU APPROXIMATION ALGORITHMS
  - CLOCK - Relace an old page. Hardware  keeps 'use' bit per physical frame. 
  - N Chance - Clock algorithm with 'use' bit and counter.

PAGE REPLACEMENT POLICY EXAMPLE

3 pages of physical mem, 5 pages of virtual mem 
(from different processes, say): ABCDE
Access pattern is ABCDDEECBADECBA

With FIFO policy:

Phys addr   A B C D D E E C B A D E C B A
1           A     D           A     C
2             B       E         D     B
3               C           B     E     A

How many page faults?  12! What is hit rate? 3/15 ! 
Only 3 out of 15 of our accesses did not necessitate a page fault. 

How many compulsory misses? 5, since we had to bring in each page 
at least one time during the string of accesses.

How many capacity and conflict misses? The problem is that capacity 
and conflict misses assume that we had an optimal replacement strategy 
to begin with, and that we COULD NOT AVOID those misses regardless.
Since FIFO is hardly optimal, then probably best to characterize all
of these misses as "policy" misses. (Note that on a quiz or final exam,
it still might ask you for capacity/conflict misses for a non-optimal
strategy. Technically the answer depends on whether the misses were
caused by lack of capacity (no place to put the new page) or conflict
(the place you want to put the new page is the same as another page
due to limited associativity).

How many policy misses? In this case, we have 7 -- all of the misses
except for the first 5. 

With MIN policy:

Phys addr   A B C D D E E C B A D E C B A
1           A     D   E               B <----- Could go anywhere
2             B               A D       A <--- Could go anywhere 
3               C          

How many page faults? 9
How many compulsory misses? 5 
How many capacity misses? Since this is an "optimal" policy we
  can talk about that. If we had an infinite physical memory then we would
  have no capacity misses. But since we have only 3 pages, we have to miss
  for A, D, B, and A -- in other words, 4 misses.
How many conflict misses? None, really, since the reason we miss the
  cache has to do with capacity rather than limited associativity.
How many policy misses? None - see above.

With LRU policy:

Phys addr   A B C D D E E C B A D E C B A
1           A     D         B     E     A 
2             B       E       A     C  
3               C               D     B  

This is similar to FIFO! Not surprising, since LRU replaces the
page that was referenced the longest time in the past. So, LRU will
behave badly when the next reference is to the least recently used
page.  Note that this is not going to NECESSARILY be the same as 
FIFO - it depends on the access pattern.

Extra Problem with Clock policy:

Phys addr  A C B D B A E F B F A G E F A
1          A           E
2	     C           F
3 	       B                 G	
4                D             A