Computer Science 330
Operating Systems
Fall 2020, Siena College
Lecture 0x10: Demand Paging; Virtual Memory
Date: Friday, October 23, 2020
Agenda
- Announcements
- The next readings/activities from OS zyBook: Chapter 8, due Monday
- The next Term Project this week: form groups and create and share repositories by today, proposals due Wednesday
- Programming Project 3: The Roger Bacon Shell [HTML] [PDF] discussion
- need to have made significant progress by now
- Part 1 functionality due tonight, but you should be well into other functionality
- good use of Issues, refer to them in your commits
- In-class exercises for 20 lab points
- OS zyBook Exercise 6.3.1
- OS zyBook Exercise 6.3.2
- OS zyBook Exercise 6.3.3
- OS zyBook Exercise 6.4.4
- 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