本文是我在上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
-