操作系统之存储管理(下)

简介: 操作系统之存储管理

3.5.2 先进先出算法(FIFO)(重点)

  • 选择在内存中驻留时间最长的页并置换它
  • 实现:页面链表法

3.5.3 第二次机会算法(SCR)

在先进先出算法的基础上进行该机而来的,此算法按照先进先出算法选择某一页面,检查其访问位R,如果为0,则置换该页;如果为1,则给第二次机会,并将访问位置零,并将其从链头取下放到链尾。

image.png

3.5.4 时钟算法(CLOCK)

在第二次机会算法中当给某个页面第二次机会的时候,将其访问位置零,然后将其挂到链尾,这都是需要开销的,于是我们改进为时钟算法。

image.png

**说明:**其实就是将之前的链表改为了环形链表,当给某个页面第二次机会的时候不需要将其取下然后挂到链尾,只需要移动一下指针即可,这样可以降低开销。

3.5.5 最近未使用算法(NRU)

  • 选择在最近一段时间内未使用过的一页并置换
  • 实现:置换页表表象的两位,访问位R,修改位M。硬件会设置这些位,如果硬件没有这些位,则可用软件模拟。
  • 进程启动时,R、M位置零,R位被定期清零。
  • 发生缺页中断时,操作系统检查R、M
*   第一类:无访问,无修改(`00`)
  • 第二类:无访问,有修改(01
  • 第三类:有访问,无修改(10
  • 第四类:有访问,有修改(11
  • 算法思想
    随机从编号最小的非空类中选择一页置换出去。
  • 时钟算法的实现

对此算法有一个时钟算法的实现


1、从指针的当前位置开始,扫描页框缓冲区,选择遇到的第一个页框(r=0,m=0)用于置换(本扫描过程中,对使用位不做任何修改)


2、如果第一步失败,则重新扫描,选择第一个(r=0;m=1)的页框(本次扫描工程中,对每个跳过的页框,将其使用位置为零)


3、如果第二部失败,指针将回到它的最初位置,并且集合中的所有页框的使用位均为零。重复第一步,并且,如果有必要,重复第二步,这样将可以找到置换的页框。

3.5.6 最近最少使用(LRU)(重点)

选择最后一次访问时间距离当前时间最长的一页并置换,即置换未使用时间最长的一页。

性能接近最佳页面置换算法

实现:时间戳或维护一个访问页的栈,导致开销较大。

硬件实现

  • 页面访问顺序0,1,2,3,2,1,0,3,2,3,该图案例只有四页。

image.png

访问第0页时先将页的第0行置为1,然后将第0列置为0

以此类推,在访问完之后将行编号最小的那一页置换出去。我们看到j中最小的是第1行,于是将第1页置换出去。

3.5.7 最不经常使用算法(NFU)

Not frequently Used,选择访问次数最少的页面置换

  • 一开始提出此算法是LRU(最近最少使用算法)的一种软件解决方案,但是实际上差距有点大。
  • 实现
*   软件计数器,一页一个,初值为零
  • 每次时钟中断时,计数器加R
  • 发生缺页中断时,选择计数器值最小的一页置换。

3.5.8 老化算法(AGING)

  • 改进(模拟LRU):计数器在加R前先右移一位,R位加到计数器的最左端。

image.png

这样如果R值为零,则计数器没有影响,如果值为1,则会变得很大,于是如果一个页面长久不被访问,则计数器值就会越来越小。最后选择值最小的置换出去。

3.5.9 页面置换算法的应用

例子:

  • 系统给某进程分配了三个页框(采用固定分配策略),初始为空
  • 进程执行时,页面访问顺序为:2 3 2 1 5 2 4 5 3 2 5 2


要求:计算应用FIFO、LRU、OPT算法时的缺页次数

应用FIFO、LRU页面置换算法

image.png

可以看到FIFO发生六次缺页异常,而LRU发生四次缺页异常。

应用OPT页面置换算法

image.png

发生三次缺页异常。

3.5.10 BELADY现象

例子:系统给某进程分配m个页框,初始为空页面访问顺序为


1 2 3 4 1 2 5 1 2 3 4 5,采用FIFO算法,计算当m=3和m=4时的缺页中断次数。


结论:m=3时,缺页中断九次;m=4时,缺页中断十次。注意:FIFO页面置换算法会产生异常现象(Belady现象),即:当分配给进程的物理页面数增加时,缺页次数反而增加。


3.5.11 页面缓冲算法(PBA)(重点)

该算法采用了可变分配和局部置换方式,置换算法则采用FIFO。

该算法规定将一个被淘汰的页放入两个链表中的一个,

若页面未被修改,直接放入空闲链表末尾,否则放入已修改页面链表末尾。

这种方式使得已修改和未修改的页面都仍然留在内存中,当进程以后再次访问这些页面时,只需花较小的开销,使这些页面又返回到该进程的驻留集中。

当被修改页面达到一定数量时,才一次性地将他们写回到外存,这样就显著地减少了外存的I/O次数


假设采取FIFO固定分配局部置换,每次缺页都要淘汰该进程最早装入内存的页面,而这里采用可变分配局部置换,即分配进程一个空白块,将原本应该淘汰的最早装入的页面挂在两个队列之一,直到没有空白块或修改页面达到上限才启动磁盘写回外存

3.6 页面置换算法2:工作集算法

3.6.1 影响缺页次数的因素

  • 页面置换算法的不同
  • 页面本身的大小
  • 程序的编制方法
  • 分配给进程的页框数量

缺页越多,系统的性能越差,这称为颠簸(抖动):虚存中,页面在内存与磁盘之间频繁调度,使得调度页面所需的时间比进程实际运行的时间还多,这样导致系统效率急剧下降,这种现象称为颠簸或抖动。

3.6.2 页面尺寸问题

  • 确定页面大小对分页的硬件设计非常重要,而对操作系统是个可选的参数
  • 要考虑的因素
    内部碎片
    页表长度
    辅存的物理特性
  • Intel 80x86/Pentium: 40964M
  • 多种页面尺寸:为了有效使用TLB带来灵活性,但给操作系统带来复杂性。

3.6.3 程序编制方法对缺页次数的影响

例子:

分配了一个页框,页面大小为128个整数,矩阵A(128 x 128)按行存放。

image.png

可以看到左边是按列赋值,右边是按行赋值。按列编制就是首先读入第一页(一行,因为矩阵是按行存放的),然后给第0个位置赋值,每次读入一行,直到将第0列赋值完,读完之后再给第1列赋值,这样会产生128*128次缺页异常;而按行赋值,第一次读入一页,给第0行的所有元素赋值,这样会产生128次缺页异常。于是可以看到程序的编制方法对缺页次数是有很大影响的。


3.6.4 分配给进程的页框数与缺页率的关系

image.png

**说明:**可以看到页框数越多那么缺页率越低,但是我们不可能给出所有的页框,于是需要找到一个平衡点W,超过这个点之后页框数的增加对缺页率的降低有限,这也是工作集算法的出发点。

3.7 工作集模型

  • 基本思想
    根据程序的局部性原理,一般情况下,进程在一段时间内总是集中访问一些页面,这些页面称为活跃页面,如果分配给一个进程的物理页面数太少了,使得该进程所需的活跃页面不能全部装入内存,则进程在运行过程中将频繁发生中断。

如果能为进程提供与活跃页面数相等的物理页面数,则可减少缺页中断次数,这是由Denning提出的。

  • 工作集:一个进程当前正在使用的页框集合

image.png

  • 例子

image.png

3.8 工作集算法

  • 基本思路
    找出一个不在工作集的页面并置换它
*   每个页表项中有一个字段:记录该页面最后一次被访问的时间
  • 设置一个时间值T
  • 判断

           根据一个页面的访问时间是否落在“当前时间 - T”之前或之中决定其在工作集      之外还是之内。


实现:扫描所有页表项,执行操作

1、如果一个页面的R位是1,则将该页面的最后一次访问时间设为当前时间,将R位清零

2、如果一个页面的R位为0,则检查该页面的访问时间是否在“当前时间 - T”之前,如果是,则该页面是需要被置换的页面;否则,记录当前所有被扫描过页面的最后访问时间里面最小值。扫描下一个页面并重复上述操作。

四、其他与存储管理相关技术

4.1 内存映射文件

  • 基本思想
    进程通过一个系统调用(mmap)将一个文件(或部分)映射到其虚拟地址空间的一部分,访问这个文件就像访问内存中的一个大数组,而不是对文件进行读写
  • 在多数实现中,在映射共享的页面时不会实际读入页面的内容,而是在访问页面时,页面才会被每次一页的读入,磁盘文件则被当作后备存储。
  • 当进程退出或显式地解除文件映射时,所有被修改页面会写回文件

1.png

4.2 支持写时复制技术

image.png

如图,两个进程共享同一块物理内存,每个页面都被标志成了写时复制。注意:共享的物理内存中每个页面都是只读的。如果每个进程想改变某个页面时,就会与只读标记冲突,而系统在检测出页面是写时复制的,则会在内存中复制一个页面,然后进行写操作。新复制的页面对执行写操作的进程是私有的,对其他共享写时复制页面的进程是不可见的。


目录
相关文章
|
7月前
|
存储 算法
【操作系统】虚拟存储管理-页面置换算法
【操作系统】虚拟存储管理-页面置换算法
733 0
|
5月前
|
Unix API 数据格式
云计算存储问题之API在不同操作系统上的实现如何解决
云计算存储问题之API在不同操作系统上的实现如何解决
|
7月前
|
存储 算法 固态存储
半导体存储品牌企业江波龙加入龙蜥社区,完成与 Anolis OS 适配
江波龙与 Anolis OS 的成功适配,进一步验证了 Anolis OS 能满足对存储容量灵活性和系统整体稳定性的高标准要求,可以为广大用户提供优质、高性能产品。
|
存储 算法 调度
操作系统实验五:存储管理设计
操作系统实验五:存储管理设计
337 0
|
存储 缓存 Linux
实验 通过命令和代码初步感受存储管理【操作系统】
实验 通过命令和代码初步感受存储管理【操作系统】
140 0
|
7月前
|
存储 算法 大数据
认识操作系统段页式存储
存储管理负责高效地分配、管理和回收计算机的内存资源。这一过程对于确保计算机系统的稳定性、性能和可扩展性至关重要。
200 0
|
7月前
|
存储 算法
操作系统:虚拟存储管理技术
操作系统:虚拟存储管理技术
198 0
|
存储 边缘计算 固态存储
SSD 存储领域厂商大普微加入龙蜥社区,完成与龙蜥操作系统适配
欢迎大普微加入龙蜥社区,拟在技术、产品与商业化三个方面深入合作
SSD 存储领域厂商大普微加入龙蜥社区,完成与龙蜥操作系统适配
|
存储 算法
计算机操作系统实验四 存储管理
计算机操作系统实验四 存储管理
333 0
|
存储
操作系统分配存储时网络无法正常连接
操作系统分配存储时网络无法正常连接
64 0