操作系统学习笔记——Swap跟虚拟存储

操作系统学习笔记——Swap和虚拟存储

Swap技术和虚拟存储技术都是针对内存不足所采取的解决措施，都有换入换出的操作,主要区别是swap技术是在内存紧张时将整个进程兑换出来，换入换出以进程为单位，虚拟存储是允许一个进程不必全部在内存中就可以执行的技术，换入换出以页为单位。

本文内容如下

swap技术

虚拟存储技术

概念
局部性原理
基本思想
优点
请求页式

请求页式的一般过程

页表

缺页中断

页替换

帧的分配

抖动

内存映射文件 Memory-Mapped-Files

比较：写时复制　Copy-On-Write

1. Swap技术

进程要执行就必须在内存中（可以不必全部在内存中）。一个进程可以暂时从内存中被兑换出来到备份存储(backing store)。备份区通常是一个快速磁盘，要足够大，足以容纳所有用户的内存映像的副本，并且不含有文件系统。

如图所示

系统维护一个就绪队列，包含着已经准备好执行的进程，这些进程的内存映像可能在内存中也可能在备份存储（backing store）中，cpu scheduler决定执行进程时，调用dispatcher，他检查队列的下一个进程是否在内存中，如果不在，并且没有空闲内存区域，dispatcher兑换出一个当前内存中的进程，把将被执行的进程兑换进来。然后重新装入寄存器然后把控制权转移的选中的进程。

Swap会受到一些限制，上下文切换的时间很高，如果I/O进行到一半，还需要等待I/O。

Unix采用一个改进的swapping策略，swap平时关闭，当有许多进程执行并且内存占用达到了一个阈值（threshold）时，swap就会开启。系统负载下降时，swap就会再次挂起。

2.虚拟存储技术

什么是虚拟存储？

虚拟存储器指的是仅把作业的一部分装入内存便可运行作业，具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。

局部性原理（Local Principle, Principle of Locality）

时间局部性

如果程序的某条指令某时刻执行了，那么不久后该指令可能会再次执行，比如循环

如果某个数据结构某时刻被访问，那么不久以后该数据结构可能会再次被访问，比如循环访问一个数据结构

空间局部性

一旦程序访问了某个位置的存储单元，不久之后，其附近的存储单元可能也被访问，比如一个数组

虚拟存储的基本思想

1. 基于局部性原理，一个作业运行之前，没必要全部装入内存，而仅将当前需要的那部分页或段，先装入内存几个启动运行，其余暂时留在磁盘上。

2. 如果程序需要的页或段不再内存中，成为缺页或缺段，程序应利用操作系统提供的请求页式或请求段式的功能，将他们调入内存，以便进程能继续执行下去。

3. 如果此时内存已满，无法再装入新的页（段），则还须再利用页（段）的置换功能，将内存中暂时不用的页（段）调出至磁盘上，腾出足够的内存空间后，再将所要访问的（段）调入内存，使程序继续执行；

虚拟存储的优点

程序可以比物理内存大/逻辑地址空间可以大于物理地址空间

允许多个进程共享地址空间/易于实现多个进程共享文件和共享内存。

提供一种高效的进程创建机制

对于用户来说，逻辑内存和物理内存分离开。

请求页式

虚拟存储一般有请求页式，请求段式，段页式虚拟存储，下面以请求页式为例介绍虚拟存储技术。

请求页式是一个可以换页的页式系统。程序执行时，一个页只有被需要时，才被装入内存中；一个不被访问的页不会装入内存中。需要在页表中提供支持信息。

请求页式的一般过程，

1.当一个页面被需要时，也就是被引用时，要检测这个页是否在内存中

如果从页表查到是无效引用，中止，

是有效引用但是不再内存中，需要将页装入内存；

2.当访问页不再内存中，将会发生缺页中断（page-faulttrap），操作系统需要在发生缺页中断时完成一系列的工作；

3.把页面装入内存时，内存中没有空闲帧，需要进行页面置换（page replacement），页置换有一些策略，相应有一些算法。

4.页面置换有时过于频繁，会引起系统不稳定，发生抖动（thrashing 颠簸，颤抖，颤动），操作系统对于抖动又有一些处理方式

页表

包含帧号，有效位，记录地址是否有效，或者添加存在位，记录是否在内存中

如图所示操作系统学习笔记——Swap跟虚拟存储

缺页中断

如果对一个页有一个引用，对页的第一次引用将会产生一个陷阱（trap）给操作系统。

操作系统首先比对系统页表和进程页表以确定一个页面的引用是非法页面还是一个尚未装入内存的合法页面。

找到一个空闲的帧

把引用的页装入到帧里

重新设置页表

重新启动产生缺页错误的指令。

如图所示

操作系统学习笔记——Swap跟虚拟存储

缺页中断和一般的中断有所区别，缺页中断发生在指令的执行期间，当发现要访问的指令或者数据不再内存中时产生缺页中断并由操作系统进行处理；一般的中断在执行周期之后，也就是中断周期进行检查和处理。

一条指令执行期间，可能产生多次缺页中断，最多可能发生的次数和计算机的体系结构有关。

举例 IBM-370，可能需要6个页面处理SS MOVE　指令；指令是６个字节，可能跨两个页面，移动的源可能跨２个页面，移动的目的地也可能跨２个页面。这样一条MOVE指令可能产生６次缺页中断，如图所示

操作系统学习笔记——Swap跟虚拟存储

页替换

一个页面被请求时，内存中没有空闲的帧，从内存中选择一个没有使用的帧，释放（将该帧的内容写到兑换空间并修改页表，以表明该帧以不再内存中）。

页置换算法的目的是保证性能，要有尽可能小的页面中断次数。

如图所示

操作系统学习笔记——Swap跟虚拟存储

下面是几个用于页面替换的算法的大概思想。

FIFO页面替换

在选择受害者时，“先入先出”，先到来的页面先被置换出去，可以使用一个队列维护内存中的各个页面来实现这一算法

最优替换算法

策略是把将来最远用到的页面置换出去，这种方式可以证明是最优的，但是难以实现，无法预料将来最远用到的页面是哪一个，虽然难以实现，但是可以用来比较其他算法的性能。

LRU页面替换，least-recently-used。为一个进程分配固定的帧数目，然后把最不常用的页面置换出去。这个算法的思想也是基于局部性原理，“用不远的过去，预测不远的将来”，这样来接近最优替换算法。其实现有计数实现，栈实现，以及几种LRU近似算法，比如附加位，第二次机会，增强第二次机会等。这些算法的具体描述不再给出。

帧的分配

一个是初始化时的分配,

纯虚拟存储，初始时，不分配，需要时再分配。一般而言，考虑到性能因素，在初始化时，要为每个进程分配最小数目的帧，这个数目取决于计算机的体系结构，比如IBM 370可能就需要6个。分配时，有几个分配算法:固定分配，又包括均等分配和比例分配，均等分配就是各个进程平均分配，比例分配是按照进程大小比例进行分配，固定分配还有一种称为优先级分配，是按优先级高底作为比例或者结合优先级和进程大小作为比例进行分配。

另一个是页面置换时的分配

一种方式是全局分配，就是说，分配给一个进程的内存已经没有空闲帧时，可以将进程内部一个没有使用的帧释放，将请求的页面装入，也可以将其他进程的没有使用的帧释放，将将请求的页面装入;局部分配则是只能在进程内部进行替换。

抖动：

抖动是指高频地进行换页的状态。一个进程，忙于把进程从内存中换进换出，花费在换页上的时间超过了执行的时间。

原因：如果一个进程没有足够的帧，也错误率会很高，导致：

低的CPU效用

操作系统认为需要增加多道程序的度（以提高CPU效用）

另一个进程添加到了内存中

导致更低的CPU效用，如此恶性循环。

如何解决？

一个是限制抖动的影响，采用局部替换算法，一个进程抖动时不会影响其他进程也发生抖动。

另一个采用一个基于局部性假设的工作集模型。定义工作集窗口为Δ，工作集定义为最近的Δ个引用的页面构成的集合，作为对程序局部的估计，操作系统记录每个进程的工作集，为进程分配足够的内存以足够容纳其工作集，如果所有进程的工作集之和超过了系统可用帧数，这样就达到了抖动的条件，操作系统需要选择一个进程并挂起，令其释放内存，将释放出的内存分配给其他需要的进程，释放内存可以将这个进程以ｓｗａｐ的方式整个兑换出去。

还有一个是基于页错误出现率的方案。首先确定一个可容忍的页错误出现率，操作系统记录每个进程的错误率，如果高于容忍值，进程获得内存帧；如果低于容忍值，进程失去物理帧。

内存映射文件 Memory-Mapped-Files

这个技术使得像读写内存那样续写磁盘，它通过利用虚拟存储技术，将磁盘块映射到内存的页中，通过虚拟存储，将文件I/O转化为读写内存而不是通过read和write系统调用；而且允许多个进程映射相同的文件，允许内存中的页被共享。

具体来说，就是文件开始时，使用普通的请求页式读（导致缺页错误），一个页大小的文件部分可以从文件系统读到物理页中，之后的文件读写和普通的内存读写相同。

如图所示

操作系统学习笔记——Swap跟虚拟存储