Computer Science 432 Operating Systems Williams College Fall 2006

Agenda

• Announcements
  • CS Colloquium this week - Craig Kaplan, University of Waterloo, "Complexity and Aesthetics in Computer-Generated Mazes". 2:35 PM TCL 206, snacks upstairs before the talk.
• Term project - form your groups, discuss your ideas, write your proposals
• Last lab assignment: a working set simulator
• Lecture assignment recap
• Memory management
  • Demand paging
    • only bring in pages that are actually requested
    • when a page is referenced that is not in memory - generate a page fault
    • page fault traps to OS, bring in the page
    • allows a mechanism for virtual memory
    • if a page fault occurs and no free frame is available, we need to make one - send a frame (the victim) back to disk
    • performance will depend on the page fault rate
    • low page fault rate results in reasonably low effective access times, high page fault rates will make effective access times very high
    • locality of reference will make for a reasonably good effective access time in most circumstances
  • Page replacement algorithms
    • selecting a victim...
    • consider possibilities with a sample page reference string - the sequence of page numbers of the memory accesses by a program
    • First In First Out (FIFO)
      • select the page that has been in memory the longest
      • simple, but may produce many page faults given an unfortunate reference string
      • suffers from Belady's Anomaly - adding frames can actually increase the page fault count in a pathological case
    • Optimal (OPT)
      • replace the page that will not be referenced for the longest time into the future
      • the good news: it's optimal
      • the bad news: we can't know the future
      • but it's a standard to which we can compare
    • 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, Tuesday, November 7.

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 8.10, 9.6

Think about but do not turn in answers to these questions. We will also discuss these in class on Tuesday.

SG&G 9.7, 9.8

No new readings for next time, but be sure to take a look at the chapter from the FreeBSD book.