Computer Science 322 Operating Systems Mount Holyoke College Spring 2008

Agenda

• Announcements
  • Extra office hours again today - sign up if you want a slot
• Exam 2 Done - hand it in!
• Final Projects
  • Can we find a time other than in class to meet for the talks?
• Memory Management
  • Page replacement algorithms
    • Least Recently Used (LRU)
      • select the page that we have not used for the longest time
      • actually used in practice
      • direct implementation may involve timestamps or a stack of page references
      • may be too expensive to implement directly
    • LRU approximation algorithms
      • Second-chance or Clock Algorithm uses one reference bit and a clock pointer, treating the frames of memory as a circular array
      • Gold's Clock Algorithm also considers a "dirty" bit to try to avoid selecing pages that need to be written back to disk because they are more expensive
    • Counting algorithms
      • Least-frequently used (LFU)
      • Most-frequently used (MFU)
      • not obvious why or when these are useful - something to think about
      • direct implementations may suffer from same overhead costs as a direct implementation of LRU
  • Frame allocation
    • each process needs some number of frames
      • pages for instructions, local data, global data
    • how do we decide how many frames are allocated to each process?
      • equal allocation - everyone gets the same
      • proportional allocation - processes get frames proportional to the amount of logical memory
      • priority allocation - prioritize memory like we prioritize CPU scheduling
    • local replacement vs. global replacement - does a victim have to be selected from the page faulting process' frames?
    • thrashing
      • if we have too many processes, not enough frames to keep a reasonably low page fault rate
      • the medium-term scheduler may notice a low CPU utilization (everyone's waiting on page faults) and add more processes to the mix
      • this will only make the situation worse
      • need to be able to detect this and have the medium-term or long-term scheduler reduce the degree of multiprogramming
    • Working set model
      • each process will have a set of pages on which it is working frequently at a given time
      • this is the working set of a process
      • a process' working set changes over time
      • approximate the working set as the set of pages that a process has accessed within some window of time into the recent past
      • if this working set window is too small, the working set we detect will not encompass the true locality
      • if it is too large, pages will remain in the working set too long after the process has moved on
      • total demand for frames in the system is the sum of the working sets of all processes
      • thrashing is likely when this total demand outstrips availability
      • this is used in reality in many modern systems (Solaris, Windows NT, to name two)

Lecture Assignment

Due at the start of class, Friday, April 18.

Turn in short answers to these questions. Please turn in a hard copy (typeset or handwritten are OK). We will discuss these questions during class, so no late submissions are accepted.

SG&G 9.6, 9.10

Look at and think about, but do not turn in answers to these questions. We will also discuss these in class on Friday.

SG&G 9.7, 9.8