cs341 Lecture Notes
Spring 2002
Week 7, Monday

For today you should have

0) finished hw04.

1) read Sections 12.3 and 12.4 and written answers to
   the preparation questions.

2) read the next semaphore problem.

3) prepared for a quiz.


For next time, you should:

1) solve the next semaphore problem.  please write your solution
   neatly on one of the forms.

2) In the cow book, read Chapter 12 on structures and pages
304--316 on modules and Makefiles.  Also, in the Anderson handout,
read pages 15--18 on pointers to structures.

3) Start hw5

Masiello        Pollard
Choy            Connor
Muenchow        Schwenck
Chang           Train
Carlin          Ahmad
Siyam           Wan
Golder          Stadler
Wada            Mushtaque       Cameron

Again, look for ways to split up the work with your partner.


Page replacement strategies
---------------------------

What is Belady's optimal strategy?





Under what conditions is it optimal?





What is LRU?





What is the principle of OS design that makes us think LRU is good?





What is LFU?



Why does LFU sound good?

Why isn't it?

   inertia: slow response to changes in access patterns

   reset counter when page is loaded?


Why is FIFO dumb?


What's a stack algorithm?


What nice property do stack algorithms have?


LRU and LFU are stack algorithms.


LRU implementation: 

why is LRU hard to implement?



what's a reference bit?





what's a dirty bit?







What's the clock algorithm?