Chapter 8: Virtual Memory
虚拟内存技术，即匀出一部分硬盘空间来充当内存使用。当内存耗尽时，电脑就会自动调用硬盘来充当内存，以缓解内存的紧张。
Resident set: 进程执行的任何时候都在内存的部分
Thrashing（系统抖动）：Too much loading and unloading
Principle of locality avoids thrashing
Hardware and Control Structures
Support Needed for Virtual Memory
•hardware must support paging and segmentation
•operating system must include software for managing the movement of pages and/or segments between secondary memory and main memory
Paging
每个进程有自己的page table
P(present)表示是否存在于内存中
M(modified)表示相应页的内容从上次装入内存到现在是否已改变
Translation Lookaside Buffer(TLB)
每次虚拟访问会引起两次物理内存访问：
- –one to fetch the page table entry
- –one to fetch the data
导致内存访问时间加倍
为了克服这个缺陷，most virtual memory schemes make use of a special high-speed cache called a translation lookaside buffer
Page Size
-
页越小，内部碎片越少。
但是，页越小，每个进程需要的页的数量就越多，这意味着更大的页表。
对于多道程序设计环境的大程序，活动进程的一部分页表在虚存而非内存中。
因此，there may be a double page fault for a single reference to memory:
first to bring in the needed portion of the page table and second to bring in the process page.
-
the physical characteristics of most secondary-memory devices favor a larger page size (more efficient block transfer of data)
Segmentation
Segmentation allows the programmer to view memory as consisting of multiple address spaces or segments
Advantages
- simplifies handling of growing data structures
- allows programs to be altered and recompiled independently
- 有助于进程内的空间共享
- 有助于保护
Combined Paging and Segmentation
用户的地址空间被分成许多段。每段依次分为许多固定大小的页，页的长度等于内存中页框大小
Protection and Sharing
保护：Segmentation entries have a base address and length
共享：一个segment可能会在多个进程的段表中引用
Operating System Software
前两个主要取决于硬件平台
Fetch Policy
决定某页何时换入内存
- demand paging(请求分页)
- 只有当访问到某页中的一个单元时才将该页取入内存
- 进程首次启动时，会出现大量page fault, 取入越来越多的页之后，局部性原理表明大多数将来访问的页都是最近读取的页，因此在一段时间后错误会逐渐减少，缺页中断的数量会降到很低。
- prepaging(预先分页)
- 读取的页并不是缺页中请求的页
- 一个进程的页连续存在secondary memory中，则一次读取许多连续的页比隔一段时间读取一页更有效
- 若大多数额外读取的页未引用到，则这个策略是低效的
Placement Policy
决定一个process piece驻存在real memory的什么位置
•Important design issue in a segmentation system
•Paging or combined paging with segmentation placing is irrelevant because hardware performs functions with equal efficiency
Replacement Policy
Deals with the selection of a page in main memory to be replaced when a new page must be brought in
目标：移出最近最不可能访问的页
Frame Locking
内存中某些页框可能是被锁定的
-
kernel of the OS as well as key control structures are held in locked frames
-
I/O buffers and time-critical areas may be locked into main memory frames
-
locking is achieved by associating a lock bit with each frame
基本算法
-
Optional
置换下次访问距离当前时间最长的页（不可能实现）
-
Least Recently used(LRU)
置换最长时间未被引用的页
•Difficult to implement
–one approach is to tag each page with the time of last reference
this requires a great deal of overhead
-
First-in-first-out(FIFO)
•Treats page frames allocated to a process as a circular buffer
-
Clock
When a page is first loaded in memory or referenced, the use bit is set to 1
Page Buffering
VAX VMS方法
不丢弃置换出的页，而是把他们放到下面两表之一
Resident Set Management
•The OS must decide how many pages to bring into main memory
–the smaller the amount of memory allocated to each process, the more processes can reside in memory
–small number of pages loaded increases page faults
–beyond a certain size, further allocations of pages will not effect the page fault rate
Fixed-allocation
发生缺页中断，该进程的一页就必须被它所需要的页面置换
Variable-allocation
Replacement Scope
两种类型都是在没有空闲的page frame时由一个page fault激活的
- global（considers all unlocked pages in main memory）
- local（仅在产生这次缺页的进程的驻留页中选择）
全局置换策略实现简单，开销更小。
Fixed Allocation, Local Scope
Necessary to decide ahead of time the amount of allocation to give a process
- If allocation is too small, there will be a high page fault rate
- If allocation is too large, there will be too few programs in main memory.有很多空闲时间，并把大量时间花费在交换上。
Variable Allocation , Global Scope
•OS maintains a list of free frames
•Free frame is added to resident set of process when a page fault occurs
•If no frames are available, the OS must choose a page currently in memory
•One way to counter potential problems is to use page buffering
Variable Allocation, Local Scope
•When a page fault occurs, select the page to replace from among the resident set of the process that suffers the fault
•Decision to increase or decrease a resident set size is based on the assessment of the likely future demands of active processes
