Computer Science 330
Operating Systems

Spring 2012, Siena College

Home     Syllabus     Schedule

Agenda

• Announcements
  • shortened lab session tomorrow
  • no office hours Friday afternoon
• Shell project status
• Be thinking about groups and topics for the final project
• Lecture assignment 15 recap
• 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
  • 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 16

Due at the start of class, Tuesday, March 27.

Please submit answers to these questions either as a hard copy (typeset or handwritten are OK) or by email to jteresco AT siena.edu by the start of class. Please use a clear subject line when submitting by email (e.g., CS 330 Lecture Assignment 16, Joe Student). We will discuss these questions at the start of class, so no late submissions are accepted.

• SG&G Exercise 8.28, p. 376 (5 points)
• SG&G Exercise 8.32, p. 377 (5 points)

You need not submit answers to these questions, but you will have a chance to ask questions about them at the start of class.

• SG&G Practice Exercise 7.5, p. 313
• SG&G Practice Exercise 8.2, p. 371
• SG&G Practice Exercise 8.8, p. 372 (Do only the cases of three, five, and seven frames)
• SG&G Practice Exercise 8.10, p. 373