操作系统--虚拟内存管理

• • • Objectives
    •  背景
    •  请求分页
    •  即写即拷
    • **页面替换**
  • 帧的分配
  • • 抖动

Objectives

 描述虚拟内存的好处
 解释请求分页、页面替换算法和页面分配的概念

讨论工作集模型的原理

 背景

背景
虚拟内存 用户逻辑内存与物理内存的分离。
 只有部分程序需要在内存中执行
 因此，逻辑地址空间可以比物理地址空间大得多
 允许多个进程共享地址空间
 允许更高效的流程创建虚拟内存可以通过以下方式实
现:

 请求分页

 请求页面调度
 需求细分
Virtual Memory > Physical Memory
使用虚拟内存的共享库
虚拟地址空间
Shared Library Using Virtual Memory
请求页面调度
 只有在需要的时候才把一页放入内存
 所需的输入/输出更少
 需要更少的内存
 更快的响应
 更多用户
 页面需要 =>访问存储器
 不正当的无效访问=> 中止
 不在内存中的=>添加进来
 惰性交换——除非需要页面，否则不要将页面交换到内
存中
 处理页面的转换器是寻呼机
Transfer of a Paged Memory to Contiguous Disk
Space
有效-无效位
 每个页表条目都与一个有效-无效位相关联

 初始有效–无效位在所有条目上都设置为 I
 页表快照示例: /valid-无效位
 在地址转换期间，如果页表条目中的有效-无效位是 i 页
错误
Page Table When Some Pages Are Not in Main
Memory
页错误
如果有对某个页面的引用，那么首先引用该页面会导致操作系统
陷入页错误

1. 操作系统查看另一张表来决定:
    无效参考 中止
    只是不在记忆中
2. 从物理内存中获取空帧
3. 将页面从磁盘交换到框架中
4. 重置表格
5. 设置验证位= v9.15
6. 重新启动导致页面错误的指令
   Steps in Handling a Page Fault
   v9.17
   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 (page fault overhead

+swap page out

+swap page in

+restart overhead)
按需分页示例
 内存访问时间= 200 纳秒
 平均页面故障服务时间= 8 毫秒

EAT =(1–p)x
200+p(8 毫秒)
=(1–p)x 200+p x 8，000，000
= 200 + p x 7，999，8009.19
9.20
如果 1000 次访问中有一次导致页面错误，那么 EAT = 8.2 微秒。
这是一个 40 倍的减速！9.21
Process Creation
 Virtual memory allows other benefits
during process creation:

• 虚拟内存还有其他好处

  在创建流程的过程中:

  ——即写即拷

  -内存映射文件(稍后)

   即写即拷

  写时复制
  写时复制(COW)允许父进程和子进程最初在内存中共享相同的页面
   如果任何一个进程修改了一个共享页面，那么该
  页面才会被复制
   COW 允许更高效的流程创建，因为只复制修改过
  的页面
   空闲页面是从零输出页面池中分配的
  Before Process 1 Modifies Page C
  After Process 1 Modifies Page C
  What happens if there is no free frame?

页面替换——在内存中找到一些页面，但是

不用了，换掉吧

算法

性能-希望一个算法将

导致页面错误的最小数量

相同的页面可能被带入内存多个

次

页面替换

 通过修改页面错误服务例程以包括页面替换来防
止内存过度分配
 使用修改(脏)位来减少页面传输开销–只有修改过
的页面才会写入磁盘9.29
页面替换完成了逻辑内存和物理内存之间的分离——可以在较小的物理内存上提供较大的虚拟内存9.31
Need For Page Replacement

Basic Page Replacement

1. 找到所需页面在磁盘上的位置

2. 找到一个自由的框架:

   -如果有一个自由帧，使用它

   -如果没有自由框架，使用一个页面

   替换算法选择受害者帧

   3.把你想要的页面变成(新)免费的

   框架;更新页面和框架表

   4. 重新启动过程

   Page Replacement
   Page Replacement Example

   Page Replacement Algorithms

   想要最低的页面错误率

   通过运行特定的算法来评估算法

   内存引用字符串(引用字符串)

   并计算页数上的错误

   该字符串

   在我们所有的例子中，引用字符串是

   1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 59.36

   Optimal Page Replacement
   Total number of page faults = 99.42
   最近最少使用(LRU)算法
    计数器实现
   每个页面条目都有一个计数器；每次通过这个条目引用页面时，将时钟复制到计数器中
    当页面需要更改时，查看计数器以确定要更
   改的内容
   LRU 页面替换
   页面错误总数= 129.47
   LRU 算法(续)。
   堆栈实现 以双链接形式保存一堆页码
   引用的页面:
   移动到最上面
   需要改变六个指针
    不搜索替换–替换堆栈的底部页面
   堆栈实现
   LRU Approximation Algorithms
   参考点

   每个页面关联一个位，初始= 0

   当page被引用位设置为1替换为0(如果存在)

   然而，我们不知道订单

   ​ 第二次机会

   需要参考位

   时钟替换

   如果要替换的页面(按时钟顺序)有参考位= 1，则:

   设置引用位0将页面留在内存中

   更换下一页(按时钟顺序)，遵循相同的规则 Second-Chance (clock) Page-Replacement Algorithm
   计数算法
    记录每页引用的次数
    LFU 算法:用最小计数替换页面
    MFU Algorithm: based on the argument that the
   page with the smallest count was probably just
   brought in and has yet to be used9.53

   帧的分配

    每个进程需要最少的页数
    示例:IBM 370–6 页处理不锈钢移动指令:
    指令为 6 字节，可能跨越 2 页
    要处理的 2 页
    要处理的 2 页
    两个主要的分配方案
    固定分配9.54
    优先级分配
   固定分配
    平均分配——例如，如果有 100 个帧和 5 个进程，给每个进程 20 个帧。
    比例分配——根据流程的大小进行分配。
   优先级分配
    使用比例分配方案，使用优先级而不是大小
    如果进程 Pi 产生页面错误，
    选择替换它的一个帧
    从优先级较低的进程中选择一个帧进行替换
   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

   抖动

   rocess does not have “enough” pages, the
   page-fault rate is very high. This leads to:
    low CPU utilization
    operating system thinks that it needs to
   increase the degree of multiprogramming
    another process added to the system
    Thrashing a process is busy swapping pages in
   and out
   Thrashing (Cont.)
   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 size9.62
   Locality In A Memory-Reference Pattern9.63
   工作集模型
    工作集窗口 固定数量的页面引用，例如:10，000
   指令9.64
   9.65
   WSSi(进程 Pi 的工作集)=在最近的 中引用的总页数(随时间变化)
    如果 太小，将不会包括整个地区
    如果 太大，将包括几个地方
    如果 将包含整个项目
    D = WSSi 总需求框架
    如果 被痛打一顿
    如果 D > m，则暂停其中一个进程9.66
   Working-set model9.67
   跟踪工作集
    用间隔定时器+一个参考位近似
    例如 ，000
    每 5000 个时间单位后定时器中断
    每页在内存中保留 2 位
    每当定时器中断复制并将所有参考位的值设置为 0 时9.68
   9.69
   如果内存中的一个位=工作集中的 1 个 页面，为什么这不完全准确？
    Improvement = 10 bits and interrupt every 1000 time units9.70
   Page-Fault Frequency Scheme
    Establish “acceptable” page-fault rate
    If actual rate too low, process loses frame
    If actual rate too high, process gains frame9.71
   Working Sets and Page Fault Rates9.72