Objectives
To describe the benefits of a virtual memorysystem
To explain the concepts of demand paging,page-replacement algorithms, and allocationof page frames
To discuss the principle of the working-setmodel
描述虚拟内存系统的优点
解释需求分页、页面替换算法和页面框架分配的概念
讨论工作集模型的原理
1. 背景 Background
Virtual memory – separation of user logical memoryfrom physical memory.
◼ Only part of the program needs to be in memory forexecution
◼ Logical address space can therefore be much largerthan physical address space
◼ Allows address spaces to be shared by severalprocesses
◼ Allows for more efficient process creation
Virtual memory can be implemented via:
◼ Demand paging
◼ Demand segmentation
虚拟内存 – 将用户逻辑内存与物理内存分离。
◼ 只有部分程序需要在内存中执行
◼ 因此，逻辑地址空间可以比物理地址空间大得多
◼ 允许多个进程共享地址空间
◼ 允许更高效的流程创建
虚拟内存可以通过以下方式实现：
◼ 需求分页
◼ 需求分段
两个特点：
◼ 进程中所有存储器访问都是逻辑地址，这些逻辑地址在运行时被转换为物理地址；（MMU将虚拟地址转为物理地址）
◼ 一个进程可以划分为许多块， 在执行过程中， 这些块不需要连续地位于主存中。（可通过分页来管理）
两个效果：
◼ 在主存中保留多个进程：
由于对任何特定的进程都仅仅装入它的某些块， 因此就有足够的空间放置更多进程。
◼ 进程可以比主存的全部空间还大
通过分段或分页的虚拟内存， 程序员可以获得巨大的主存（特指物理内存）， 大小与磁盘储存器相关。
在具有层次结构存储器的计算机系统中，采用自动实现部分装入和部分对换功能（主存和磁盘之间的对换），为用户提供一个比物理主存容量大得多的，可寻址的一种“主存储器”。
虚拟内存(virtualmemory)将用户逻辑内存与物理内存分开。这在现有物理内存有限的情况下，为程序员提供了巨大的虚拟内存(如图 9-1所示)。虚拟内存使得编程更加容易因为程序员不再需要担心有限的物理内存空间，只需要关注所要解决的问题。
进程的虚拟地址空间(virtual address space)就是进程如何在内存中存放的逻辑(或虚拟)视图。通常，进程从某一逻辑地址(如地址0)开始，连续存放，如图 9-2 所示。根据第8章所述，物理地址可以按来组织，并且分配给进程的物理顿也可以不连续。这就需要内存管理单元(MMU)将逻辑页映射到内存的物理页顿。
2. 请求调页 Demand Paging
另一种策略是，仅在需要时才加载页面。这种技术被称为请求调页(demand paging)，常常用于虚拟内存系统。
Bring a page into memory only when it is needed
◼ Less I/O needed
◼ Less memory needed
◼ Faster response
◼ More users
Page is needed -> reference to it
◼ invalid reference -> abort
◼ not-in-memory -> bring to memory
Lazy swapper – never swaps a page into memoryunless page will be needed
◼ Swapper that deals with pages is a pager
仅在需要时将页面放入内存中(优点：)
◼ 所需的 I/O 更少
◼ 所需内存更少
◼ 更快的响应
◼ 更多用户
需要页面 - >引用它（何时算需要呢？）
◼ 无效引用 （即不在物理内存中）-> 中止
◼ 不在内存中 - >带到内存中
懒惰交换器 – 从不将页面交换到内存中，除非需要页面（即只有需要的时候才交换，才从磁盘中取出放入到主存中）
◼ 处理页面的交换器是一个调页程序
交换器操纵整个进程，而调页程序(pager)只涉及进程的页面，因此，在讨论请求调页时，我们使用“调页程序”，而不是“交换器”。
2.1 基本概念
Valid-Invalid Bit
With each page table entry a valid–invalid bit is associated(v -> in-memory, i -> not-in-memory)
Initially valid–invalid bit is set to i on all entries
Example of a page table snapshot:
During address translation, if valid–invalid bit in page table entry is I -> page fault
每个页表条目都关联一个有效-无效位（v -> 在内存中，i -> 不在内存中）
初始有效 – 所有条目上的无效位都设置为 i
页表快照示例：
在地址转换过程中，如果页表条目中的有效-无效位为 i->页错误
Page Table When Some Pages Are Not in Main Memory
Page Fault :
If there is a reference to a page, first reference to that page will trap to operating system:page fault
-
Operating system looks at another table to decide:
◼ Invalid reference -> abort
◼ Just not in memory
-
Get empty frame
-
Swap page into frame
-
Reset tables
-
Set validation bit = v
-
Restart the instruction that caused the page fault
但是，如果进程试图访问那些尚未调入内存中的页面时，情况会如何呢?对标记为无效的页面访问会产生缺页错误(page fault)。分页硬件在通过页表转换地址时会注意到无效位被设置，从而陷人操作系统。这种陷阱是由于操作系统未能将所需的页面调入内存引起的。处理这种缺页错误的程序很简单(图9-6):
- 检查这个进程的内部表(通常与 PCB(Process Control Block，进程控制块)一起保存)，以确定该引用是有效的还是无效的内存访问。
- 如果引用无效，那么终止进程。如果引用有效但是尚未调入页面，那么现在就应调入。
- 找到一个空闲帧(例如，从空闲顿链表上得到一个)。
- 调度一个磁盘操作，以将所需页面读到刚分配的帧。
- 当磁盘读取完成时，修改进程的内部表和页表，即设置验证位 = v，以指示该页现在处于内存中。
- 重新启动被陷阱中断的指令。该进程现在能访问所需的页面，就好像它总是在内存中。
2.2 请求调页的性能 Performance of Demand Paging
Page Fault Rate 0 <= p <= 1.0
◼ if p = 0 no page faults
◼ if p = 1, every reference is a fault
Effective Access Time (EAT)
EAT = (1 – p) x memory access+ p x (page fault overhead + swap page out + swap page in + restart overhead )
页面错误率 0 <= p <= 1.0
◼ 如果 p = 0 无页面错误
◼ 如果 p = 1，则每个引用都是错误
有效访问时间
EAT = （1 – p） * 内存访问 + p *（页面错误中断处理 + 换出 + 换入 + 重启动）
EAT = （1 – p） * 内存访问 + p * 缺页错误时间
（缺页错误时间 = 页面错误中断处理 + 换出 + 换入 + 重启动）
Memory access time = 200 nanoseconds
Average page-fault service time = 8 milliseconds
EAT = (1 – p) x 200 + p (8 milliseconds) = (1 – p） x 200 + p x 8,000,000 = 200 + p x 7,999,800
If one access out of 1,000 causes a page fault, then EAT = 8.2 microseconds.
内存访问时间 = 200 纳秒
平均页面错误服务时间 = 8 毫秒
EAT = （1 – p） x 200 + p （8 毫秒） = （1 – p ）x 200 + p x 8，000，000 = 200 + p x 7，999，800
如果 1，000 次访问中的一次导致页面错误，则 EAT = 8.2 微秒。
Process Creation
Virtual memory allows other benefits during process creation:
- Copy-on-Write
- Memory-Mapped Files (later)
虚拟内存在进程创建过程中具有其他优势：
- 写入时复制
- 内存映射文件（更高版本）
3. 写时复制 Copy-on-Write
Copy-on-Write (COW) allows both parentand child processes to initially share thesame pages in memory If either process modifies a shared page,only then is the page copied
COW allows more efficient processcreation as only modified pages are copied
Free pages are allocated from a pool of zeroed-out pages
写入时复制 （COW） 允许父进程和子进程最初共享内存中的相同页面 如果任一进程修改了共享页面，则仅复制页面
COW 允许更高效的流程创建，因为只复制修改的页面
空页面是从清零页面池中分配的
书上内容：
然后，子进程会修改复制的页面，而不是属于父进程的页面。显然，当使用写时复制技术时，仅复制任何一进程修改的页面，所有未修改的页面可以由父进程和子进程共享。
当确定采用写时复制来复制页面时，重要的是注意空闲页面的分配位置。许多操作系统为这类请求提供了一个空闲的页面池(page pool)。当进程的堆栈或堆要扩展时或有写时复制页面需要管理时，通常分配这些空闲页面。操作系统分配这些页面通常采用称为按需填零zero-fll-on-demand)的技术。按需填零页面在需要分配之前先填零，因此清除了以前的内容
What happens if there is no free frame?
如何找到空闲帧？如果没有空闲帧怎么办？
Page replacement – find some page inmemory, but not really in use, swap it out
◼ algorithm
◼ performance – want an algorithm whichwill result in minimum number of pagefaults
Same page may be brought into memoryseveral times
页面替换 – 在内存中找到一些页面，但并未真正使用，将其换出
◼ 算法
◼ 性能 – 想要一种算法，这将导致最少的页面错误数量
同一页面可能会多次进入内存（频繁的换入换出会导致大量的页面错误，所以如何选择合适的换出页面是一个值得思考的问题）
4. 页面置换算法 Page Replacement
Prevent over-allocation of memory by modifyingpage-fault service routine to include pagereplacement
Use modify (dirty) bit to reduce overhead ofpage transfers – only modified pages arewritten to disk
Page replacement completes separationbetween logical memory and physical memory– large virtual memory can be provided on asmaller physical memory
通过修改页面错误服务例程以包含页面替换来防止内存过度分配
使用修改（脏）位来减少页面传输的开销 - 仅将修改的页面写入磁盘
页面替换完成了逻辑内存和物理内存之间的分离 – 可以在较小的物理内存上提供大型虚拟内存
4.1 基本页面置换 Basic Page Replacement
-
Find the location of the desired page on disk
-
Find a free frame:
- If there is a free frame, use it
- If there is no free frame, use a page replacement algorithm to select a victim frame
-
Bring the desired page into the (newly) free frame; update the page and frame tables
-
Restart the process
-
在磁盘上查找所需页面的位置
-
查找可用帧：
如果有空闲帧，请使用它
如果没有空闲帧，请使用页面替换算法选择牺牲帧
-
将所需的页面带入（新）自由框架;更新页面和框架表
-
重新启动进程
书上的内容：
页面置换: 1.找到所需页面的磁盘位置。
2.找到一个空闲帧:
a.如果有空闲帧，那么就使用它。
b.如果没有空闲顿，那么就使用页面置换算法来选择一个牺牲(victimframe)。
c.将牺牲帧的内容写到磁盘上，修改对应的页表和帧表。
3.将所需页面读人(新的)空闲帧，修改页表和帧表。
4.从发生缺页错误位置，继续用户进程。
==请注意，如果没有空闲帧，那么需要两个页面传输(一个调出，一个调人)。这种情况实际上加倍了缺页错误处理时间，并相应地增加了有效访问时间。==
=
Want lowest page-fault rate
Evaluate algorithm by running it on a particularstring of memory references (reference string)and computing the number of page faults on thatstring
In all our examples, the reference string is1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
想要最低的页面错误率
通过在特定的内存引用字符串（引用字符串）上运行算法并计算该字符串上的页面错误数来评估算法
在我们的所有示例中，引用字符串为 1， 2， 3， 4， 1， 2， 5， 1， 2， 3， 4， 5
Graph of Page Faults Versus The Number of Frames ：
4.2 First-In-First-Out (FIFO) Algorithm
算法： 总是淘汰最先调入主存的那一页，或者说在主存中驻留时间最长的那一页（常驻的除外）。
理由： 最早调入内存的页面，其不再被访问的可能性最大。
特点：实现简单、适合线性访问、对其他情况效率不高
异常情况：在某些情况下会出现分配给进程的页面数增多，缺页次数反而增加的奇怪现象
4.3 最优页面算法 Optimal Algorithm
Replace page that will not be used for longest periodof time
4 frames example1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
How do you know this?
Used for measuring how well your algorithm performs
替换不会长时间使用的页面
4帧示例1， 2， 3， 4， 1， 2， 5， 1， 2， 3， 4， 5
怎么知道不会长时间使用的页面的？
用于衡量算法的性能
算法： 调入一页而必须淘汰一个旧页时， 所淘汰的页应该是以后不再访问的页或距现在最长时间后再访问的页。
特点： 不是实际可行的算法， 可用来作为衡量各种具体算法的标准， 具有理论意义。
4.4 LRU页面置换 Least Recently Used (LRU) Algorithm
Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Counter implementation
◼ Every page entry has a counter; every timepage is referenced through this entry, copy theclock into the counter
◼ When a page needs to be changed, look at thecounters to determine which are to change
计数器实现
◼ 每个页面条目都有一个计数器;每个时间页面都通过此条目引用，将时钟复制到计数器中
◼ 当页面需要更改时，请查看计数器以确定要更改的内容
算法： 淘汰的页面是在最近一段时间里较久未被访问的那页。
原理： 根据程序局部性原理， 那些刚被使用过的页面， 可能马上还要被使用， 而在较长时间里未被使用的页面， 可能不会马上使用到。
4.5 计数算法 Counting Algorithms
Keep a counter of the number of references that have been made to each page
LFU Algorithm: replaces page with smallest count
MFU Algorithm: based on the argument that the page with the smallest count was probably just brought in and has yet to be used
保留对每个页面的引用数量的计数器
LFU（最不经常使用）算法：替换计数最小的页面
MFU（最经常使用）算法：基于以下论点：计数最小的页面可能刚刚引入并且尚未使用
5. 帧分配 Allocation of Frames
Each process needs minimum number of pages
Example: IBM 370 – 6 pages to handle SS MOVEinstruction:
◼ instruction is 6 bytes, might span 2 pages
◼ 2 pages to handle from
◼ 2 pages to handle to
Two major allocation schemes
◼ fixed allocation
◼ priority allocation
每个进程需要最少的页数
示例：IBM 370 – 处理 SS 移动指令的 6 页：
◼ 指令为 6 个字节，可能跨越 2 页
◼ 2 页处理自
◼ 要处理的 2 页
两大分配方案
◼ 固定分配（给每个进程固定分配空间）
◼ 优先级分配
5.3 全局分配和局部分配 Global vs. Local Allocation
Global replacement – process selects a replacement frame from the set of all frames; one process can take a frame from another
Local replacement – each process selects from only its own set of allocated frames
全局替换 – 过程从所有帧集中选择一个替换帧;一个进程可以从另一个进程中获取帧
本地替换 – 每个进程仅从自己的一组分配帧中进行选择
6. 系统抖动/颠簸现象
If a process does not have “enough” pages, thepage-fault rate is very high. This leads to:
◼ low CPU utilization
◼ operating system thinks that it needs toincrease the degree of multiprogramming
◼ another process added to the system
Thrashing = a process is busy swapping pagesin and out
如果进程没有“足够”的页面，则页面错误率非常高。这导致：
◼ 低 CPU 利用率
◼ 操作系统认为需要提高多进程并发程度
◼ 添加到系统的另一个进程
==抖动 = 进程正忙于交换页面进出==
Demand Paging and Thrashing
Why does demand paging work?Locality model
◼ Process migrates from one locality to another
◼ Localities may overlap
Why does thrashing occur?
Σsize of locality > total memory size
为什么需求分页有效？局部性模型
◼ 进程从一个位置迁移到另一个位置
◼ 地点可能重叠
为什么会发生系统抖动？
Σ局部大小>总内存大小
6.2 工作集模型 Working-Set Model
▲= working-set window = a fixed number of pagereferences
Example: 10,000 instruction
WSSi (working set of Process Pi) = total number of pages referenced in the most recent ▲ (varies in time)
◼ if ▲ too small will not encompass entire locality
◼ if ▲ too large will encompass several localities
◼ if ▲ = ∞ -> will encompass entire program
D = Σ WSSi = total demand frames
if D > m -> Thrashing
Policy if D > m, then suspend one of the processes
▲= 工作集窗口 = 固定数量的页面引用
示例：10，000 条指令
WSSi（流程 Pi 的工作集）= 最近 ▲ 中引用的总页数（随时间变化）
◼ 如果 ▲ 太小将无法涵盖整个地区
◼ 如果 ▲ 太大将包含多个地区
◼ 如果 ▲ = ∞ -> 将包含整个程序
D = Σ WSSi = 总需求帧
如果 D > m -> 系统抖动
策略如果 D > m，则暂停其中一个进程
