Computer Science 432/563
Operating Systems

Spring 2016, The College of Saint Rose

Home     Syllabus     Schedule

Agenda

• Announcements
  • Programming Project 3: knish: The Knight Shell stretch run on part 2 functionality underway
  • Term Project term project proposals due today, but I will accept through the end of the week
• Midterm recap
• 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 0x11 Assignment

Due at the start of class, Monday, April 4.

Please submit answers to these questions either as a hard copy (typeset or handwritten are OK) or by email to terescoj AT strose.edu by the start of class. Please use a clear subject line when submitting by email (e.g., CS 432 Lecture 0x11 Assignment, Mary Smith). We will discuss these questions at the start of class, so no late submissions are accepted.

The readings for next class are the handout from the Tanenbaum text.

• SG&G Exercise 8.19, p. 427 (3 points)
• SG&G Exercise 8.23, p. 428 (2 points)
• SG&G Exercise 8.27, p. 429 (5 points)
• SG&G Exercise 8.31, p. 430 (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. 364
• SG&G Practice Exercise 8.2, p. 423
• SG&G Practice Exercise 8.8, p. 425 (Do only the cases of three, five, and seven frames)
• SG&G Practice Exercise 8.10, p. 425