Computer Science 330
Operating Systems

Fall 2022, Siena College

Home     Syllabus     Schedule

Agenda

• Announcements
  • Programming Project 4: Roger Bacon Shell with Pipes and Redirection [HTML] [PDF] updated due dates
  • The next readings/activities from OS zyBook: Chapter 8, due December 2
  • Sign up for the CS Holiday Party!
• Exam 2 recap
• Updated example with pipes and fork: pipefork.c in https://github.com/SienaCSISOperatingSystems/sysprog-examples
• 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/third-chance 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
• Looking at exercises from OS zyBook Chapter 7
  • Section 7.1, all

Terminology

• virtual memory
• demand paging
• present bit
• page fault
• page replacement
• modified bit
• reference string
• optimal page replacement
• FIFO page replacement
• LRU page replacement
• referenced bit
• aging register
• aging page replacement
• second chance page replacement
• third chance/not recently used page replacement
• working set
• optimal working set
• working set page replacement
• page-fault-frequency replacement