本文是我在上UCSD的 CSE 120: Principles of Operating Systems (Winter 2020) 整理的笔记，这一课主要介绍了操作系统里面虚拟内存的概念，主要是对上一节课的逻辑内存的一部分补充，关于segment和page的概念可以参考上一篇笔记。
Review
Segments and Pages
Structuring memory as segements/pages allows:
- partitioning memory for convenient allocation
- reorganizing memory for convenient usage
Approaches
- Relocation via address translation
- Protection via matching operations with objects
Result: a logically organized memory
Optimization
Not all pieces need to be in memory
- Need only piece being referenced
- Other pieces can be on disk
- Bring pieces in only when needed
Illusion: there is much more memory
Needed:
- A way to identify whether a piece is in memory
- A way to bring in a piece (from where to where?)
- Relocation (address translation)
From logical to virtual memory
Logical memory becomes virtual memory
- Still logical (seperate organization from physical)
- Virtual: memory seems to exist, regardless of how (memory or disk)
Virtual memory: illusion of large memory
- Keep only portion of logical memory in physical
- Rest is kept on disk (larger, slower, cheaper)
- Unit of memory is segment or page (or both)
Logical address space $\rightarrow$ virtual address space
Virtual memory based on paging
Paged virtual memory
- All of pages reside on disk
- Some also reside in physical memory (which ones?)
Contents of page table entry
- Valid: is entry valid (page in physical memory or not)
- Ref: has this page been referenced yet?
- Mod: has this page been modified?
- Frame: what frame is this page in?
- Prot: what are the allowable operations?
Address Translation
Process:
- Get entry: index page table with page number
If valid bit is off, which cause a page fualt, then trap into kernel
- Find page on disk
Read it into a free frame
- may need to make room if there is no available frame: page replacement
Record frame number in page table entry
- Set valid bit and other fields
Retry instruction (return from page-fault trap)
Possible faults under segmentation/paging
two kinds of address:
- Virtual address: (segment s, page p, offset i)
- Physical address: (frame f, offset i)
[ ] Use s to index segment table (to get page table)
- may get a segment fualt
[ ] Check bound (Is p < bound?)
- may get a segmentation violation
[ ] Use p to index page table (to get frame f)
- may get a page fault
[ ] Physical address: concatenate f and i
Cost of page faults is high
- Disk: 5 ~ 6 orders magnitude slower than RAM
Example:
- RAM access time: 100 nsec
- Disk access time: 10 msec
- p = page fault probability
- Effective access time: 100 + p * 10,000,000 nsec
- if p = 0.1%, effective access time = 10,100 nsec (100 times slower!)
Possible implementation
Principle of Locality
Not all pieces referenced uniformly over time
- Make sure most referenced pieces in memory
- If not, thrashing: constant fetching of pieces
References cluster in time/space
- Will be same or neighboring areas
- Allows prediction based on past
Page replacement policy
- Goal: remove page not in locality of reference
Page replacement is about:
- which page(s) to remove
- when to remove them
How to do it in cheapest way possible, with:
- least amount of additional hardware
- least amount of software overhead
Basic Page Replacement Algorithms
FIFO: select page that is oldest
- Simple: keep pointer to next frame after last loaded
- Doesn’t perform well (oldest may be popular)
OPT: Optimal Page Replacement
- Optimal: replace page that will be accessed furthest in future
Not realistic:
- Requires predicting the future
- Useful as a benchmark
LRU: Least Recently Used
Replace page that was least recently used
- LRU means used furthest in the past
Takes advantage of locality of reference
- Must have some way of tracking frame with LRU page : requires hardware support
Others
Approximating LRU: Clock Algorithm
Select page that is old and not recently used
- Clock (second chance) is approximation of LRU
Hardware support: reference bit
- Associated with each frame is a reference bit
- Reference bit is in page table entry
How reference bit is used
- When frame filled with page, set bit to 0 (by OS)
- If frame is accessed, set bit to 1 (by hardware)
Working process
- Arrange all frames in circle (clock)
- Clock hand: next frame to consider
Page fault: find frame
- If ref bit 0, select frame
- Else, set ref bit to 0
- Advance clock hand
- If frame found, break out of loop, else repeat
If frame had modified page, must write it to disk
Resident Set Management
Resident set: process’s pages in physical memory
- One set per process
- How big should resident set be? Which pages?
- Who provides frame (same process or another)?
Local: limit frame selection to request process
- Isolates effects of page behavior on processes
- Inefficient: some processes have unused frames
Global: select any frame (from any process)
- Efficient: resident sets grow/shrink accordingly
- No isolation: process can negatively affect another (by replacing other process’s important pages)
Multiprogramming Level
- Multiprogramming level: number of processes in physical memory (non-empty resident sets)
- Goal: increase multiprogramming level - how?
- However, beyond certain point: thrashing (make processor utilization pretty low since many processes may not be working)
- Resident set should contain the working set
Denning’s Working Set Model
Introduction
Working set: $W(t, \Delta)$
- Pages referenced during last delta (process time)
Process given frames to hold working set
- Add/remove pages according to $W(t, \Delta)$
- If working set doesn’t fit, swap process out
Working set is a local replacement policy
- Process’s page fault behavior doesn’t affect others
Problem: difficult to implement
- Must timestamp pages in working set
- Must determine if timestamp older than $t - \Delta$
- How should $\Delta$ be determined?
Contrast to Clock
- Clock: simple, easy to implement, global policy