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

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.把你想要的页面变成(新)免费的

框架;更新页面和框架表

  1. 重新启动过程

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

标签: 内存, 虚拟内存, 页面, 替换, page, Page, 详解

相关文章推荐

添加新评论，含*的栏目为必填