清华大学操作系统课程笔记:虚拟存储

本文已收录于 清华大学操作系统课程笔记 系列,共计 6 篇,本篇是第 2 篇

虚拟存储(虚存)

非连续内存分配之上实现将内存暂存到磁盘中,实现应用程序可使用更多的内存空间,有点像linux中的swap。

覆盖技术

dos系统,程序员自己写覆盖控制。开发难度增加。

交换技术

以进程为单位的交换技术:

局部性原理

操作系统决定什么东西换出,什么换入。与后面的页置换算法有关。

如果是在内存中,是没有变化的。但如果利用了虚拟存储,用后面的方法会提高程序的性能。

虚拟存储概念

什么是虚拟内存?简单地说是指程序员或CPU“看到”的内存

  1. 虚拟内存单元不一定有实际的物理内存单元对应,即实际的物理内存单元可能不存在;
  2. 如果虚拟内存单元对应有实际的物理内存单元,那二者的地址一般是不相等的;
  3. 通过操作系统实现的某种内存映射可建立虚拟内存与物理内存的对应关系,使得程序员或CPU访问的虚拟内存地址会自动转换为一个物理内存地址。

首先,在有了分页机制后,程序员或CPU“看到”的地址已经不是实际的物理地址了,这已经有一层虚拟化,我们可简称为内存地址虚拟化。

有了内存地址虚拟化,我们就可以通过设置页表项来限定软件运行时的访问空间确保软件运行不越界,完成内存访问保护的功能。

通过内存地址虚拟化,可以使得软件在没有访问某虚拟内存地址时不分配具体的物理内存,而只有在实际访问某虚拟内存地址时,操作系统再动态地分配物理内存,建立虚拟内存到物理内存的页映射关系,这种技术称为按需分页(demand paging)。

把不经常访问的数据所占的内存空间临时写到硬盘上,这样可以腾出更多的空闲内存空间给经常访问的数据;当CPU访问到不经常访问的数据时,再把这些数据从硬盘读入到内存中,这种技术称为页换入换出(page swap in/out)(分页机制)。这种内存管理技术给了程序员更大的内存“空间”,从而可以让更多的程序在内存中并发运行。

覆盖和交换前面讲过了。

虚拟页式存储:在页式存储之上把一部分放在外存(磁盘)。

为什么要做虚拟存储?——原因是快速增长的内存需求。

上图:操作系统这么做是为了方便上层用户。

到这,我们就可以实现虚拟存储了。

我们还需要:

虚拟页式存储(重点)

把交换的单位设置为页的时候,就是虚拟页式存储。

之前的:

操作系统要做的事情就是接管,找页,把这一个符号变为有效:

这一小点的变化会导致修改:

虚拟存储的话需要加一些标志位:

举个栗子:

执行MOV REG, 8192

可以找到页,访问没有问题。

缺页:

X86页表结构:

这一部分跟前面所讲的页是一样的,变化在下面:

缺页异常

发现这一页不在物理内存中。

能找到空闲页的情况:

实际代码中又要复杂一些。

虚拟页式存储中的外存管理

虚拟页式存储管理的性能

置换算法

置换算法的概念

功能:

核心点是:选择被置换的物理页面

设计目标:

页面锁定

有些页面不能被换出到外存。通过锁定位实现。

如何评价一种置换算法?

页面置换算法分类

局部页面置换算法

最优页面置换算法(OPT)——理想情况,实际无法实现

2020-05-23 05:52:46.024000

2020-05-23 05:54:42.0180002020-05-23 05:54:42.222000

2020-05-23 05:55:25.976000

其根本问题在于我们无法知道后面的执行顺序。

先进先出算法(FIFO)——会饥饿

2020-05-23 05:57:21.843000

我们通常不会把它作为独立的算法,会与其他算法柔和在一起使用。

使用链表实现FIFO算法:

2020-05-23 05:59:53.493000

2020-05-23 06:00:43.609000

在Lab3的实验中,我们完成FIFO页替换算法。

最近最久未使用算法(LRU)

最近最久未使用算法(LRU)是一种折中的办法

2020-05-23 06:04:09.022000

实现思路:

2020-05-23 06:06:02.861000

2020-05-23 06:07:02.628000

使用栈或链表实现LRU算法:

2020-05-23 06:09:52.635000

2020-05-23 06:11:08.440000

2020-05-23 06:11:41.042000

2020-05-23 06:12:45.220000

这种做法平时的开销很大。

2020-05-23 06:13:53.845000

时钟置换算法

2020-05-23 06:18:12.668000

大致统计:看过去的一段时间中页面是否被访问过,如果被访问过就留下,没有被访问过就置换出去。

通过上面的方法可以使程序缺页的情况下置换,正常的情况下访问。

改进的时钟算法(challenge部分实现):

可参考《现代操作系统》

最不常用算法(LFU)

使用栈维护LFU算法:

使用时间要维护栈,统计次数就简单点。

Belady现象

所谓Belady现象是指:在分页式虚拟存储器管理中,发生缺页时的置换算法采用FIFO(先进先出)算法时,如果对一个进程未分配它所要求的全部页面,有时就会出现分配的页面数增多但缺页率反而提高的异常现象。

FIFO是最早出现的页置换算法之一。Belady现象的原因是FIFO算法(先进先出算法)的置换特征与进程访问内存的动态特征是矛盾的,即被置换的页面并不是进程不会访问的,因而FIFO并不是一个好的置换算法。

Belady是人名,一般翻译为贝莱迪。一般来说,缓存越大,命中率越高,缺页率越低。但有一个计算机学者,名字叫Belady。在1969年研究FIFO算法时,发现了一个反例,使用4个页框时的缺页次数比3个页框时的缺页多,因此这种奇怪的情况称为Belady异常。

这种异常的原因是对于FIFO算法来说,在同一时刻,使用4个页框时缓存中保存的页面并不完全包含使用3个页框时保存的页面,二者不是超集子集关系,造成都某些特殊的页面请求序列,4个页框命中率反而低。

对LRU算法,任何时刻,缓存大的算法中保存的页面,都包含了缓存小的算法中的页面,多以缓存越大,命中率越高。

作者:grasshoper97

链接:https://www.zhihu.com/question/278329594/answer/453578379

来源:知乎

著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

LRU(最近最久未使用算法)没有Belady现象。

算法比较

全局置换算法

工作集置换算法

再多缓存一页就可以很有效的避免缺页。

缺页率置换算法

目前我们能控制的是页面置换算法。

目的是让缺页率保持在某个范围。

缺页率比较低,相当于常驻集过大,需要把不用的页置换出去。

缺页率过高,需要增加常驻集。

举个例子:

把置换这种事放在缺页中断的时候完成。这时候开销会降下来。

抖动和负载控制

负载控制

 

作者: 高志远

高志远,23岁,男生,毕业于上海杉达学院电子商务系。

发表评论

邮箱地址不会被公开。