------------------------------------------------------
Session 32 – April 28, 2003
------------------------------------------------------
AGENDA:
0 Admin
1 Ch. 4.4: page replacement policies
2 Ch. 4.5: design issues for paging systems

------------------------------------------------------
0 – ADMIN
------------------------------------------------------
P6 due next Monday night
* quick discussion of speaker control

------------------------------------------------------
1 – CH 4.4 PAGE REPLACEMENT ALGORITHMS
------------------------------------------------------
Discuss following algorithms
* Optimal
* Not recently used page (NRU)
  - R (referenced) & M (modified) bits
  - 4 possible combinations
  - clear R every clock tick or so
  - not optimal, but adequate
* FIFO
  - dumb algorithm, dumps frequently used along
    with rarely used
* 2nd chance
  - modification to FIFO
  - if reference bit (R) is 0, old and unused => dump
    else set R to 0 and move to end of FIFO as though
    had just arrived
  - ok, but inefficient
* clock
  - more efficient version of 2nd chance
* least recently used (LRU)
  - fig 4-15 p. 336
* simulating LRU in software
  - fig 4-16 p. 337
  - devious solution :-)



------------------------------------------------------
2 – CH 4.5 DESIGN ISSUES FOR PAGING SYSTEMS
------------------------------------------------------
Working set model
* demand paging
* locality of reference
* thrashing
* working set model
* prepaging
* Peter Denning
  - wsclock

Local vs. global allocation policies
* local page replacement algorithm
* global algorithm
  - how allocate memory among processes?
  - example 1 instr. referencing 6 pages
  - page fault frequency (PFF) algorithm
    + fig 4-18 p. 341
* page size
  - fragmentation issues


COS 421 – Lecture Notes #32		SPRING 2003	
COS421-lect-2003-04-28	Page 2	Printed 28.04.03