· 虚拟内存技术

前面介绍的传统连续分配和传统离散分配内存策略具有以下特点或者说缺点。

1、一次性：作业必须一次性全部装入内存后才能开始运行。这会造成两个问题：①作业很大时，不能全 部装入内存，导致大作业无法运行；②由于需要将作业整个装入内存，内存能容纳的作业数减少，并发度下降。

2、驻留性：一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。

事实上，作业的不同数据段和程序段在整个进程运行期间只有若干个时间段会被用到，而非每时每刻都被用到，这就导致了内存中会驻留大量的、暂时用不到的 程序段和代码段，浪费了宝贵的内存资源。

为了解决这个问题，可以使用虚拟内存技术。

虚拟内存技术是指在程序装入内存时，可以将程序很快会用到的部分装入内存，暂时用不到的部分留在外存；程序运行时，当访问的信息不在内存时（缺页），OS将该进程所需信息从外存调入内存，继续运行程序。调入内存时在内存空间不够的情况下，OS将内存中暂时用不到的信息（例如不在运行态的其他进程 或 本进程暂时用不到的存储单元）换出到外存。之所以可以这样做是因为程序运行遵循局部性原理。

在操作系统的换入换出下，在用户进程看来似乎有一个比实际 内存大得多的内存可以容纳得下它们，所以叫虚拟内存。实 际的物理内存大 小没有变，只是 在逻辑上进行了 扩充。

虚拟内存的特征（正好相对应传统内存分配策略）

1、多次性：进程可以分多次装入内存，而非一次性装入；

2、对换性：进程无需一直常驻内存，允许在进程运行、就绪和阻塞时换入换出；

3、虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量大于实际内存容量，能够分配给更多进程。

连续分配策略要求进程被分配连续的内存空间，这意味着进程无法分多次调入内存，必须一次性全部调入内存，因此连续分配技术很难使用虚拟内存技术（或者说使用了虚拟内存技术，就很难做到连续分配）。

虚拟内存的实现需要建立在离散分配管理的基础上。

例如一个进程A会占4M空间，OS实行连续分配和虚拟内存技术，允许该进程分多次装入，第一次装入1M，在物理内存的范围是 4096~5120。随着时间推移，0~4096和 5120~+∞的内存空间可能被其他进程占用。进程A第二次再调入1M到内存中，后面这个1M和前面的1M就不是连续的。

基本的分页存储、分段存储和段页式存储结合虚拟内存技术，演变为现在的请求分页存储、请求分段存储和请求段页式存储。

在请求分页存储中，当访问的页面不在 内存时，OS将所需页面从外 存调入内存，该过程称为请求调页；内存空间不够时，OS将内存 中暂时用不到的页面换出到外存，该过程称为页面置换；

· 请求分页管理

请求分页管理在基本分页管理的基础上增加了 请求调页（换入） 和 页面置换（换出） 这两个功能。

要实现 请求调页 和 页面置换 需要考虑以下问题：

1、OS请求一个页面时要知道该页面是否在内存中；

2、如果不在，则该页面的外存地址是多少；

3、内存不足时，要换出哪些页面；

4、要换出的页面是否被修改过（如果被修改过则该页面需要写回外存，覆盖更新外存的页面；如果没被修改过，则内存的该页面可以被直接覆盖）；

为了实现上述4个点，OS在页表增加了 状态位、外存地址、修改位 和 访问次数 这4个字段。

在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然 后由操作系统的缺页中断处理程序处理中断。

此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。

如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修 改页表中相应的页表项。

如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内 存期间被修改过，则要将其写回外存。未修改过的页面不用写回外存。

因此，请求分页管理比基本分页管理的地址变换机构多了3个步骤：

请求调页（缺页时发生）；页面置换（调入页面但内存不足时发生）；修改页表；

注意：

1、缺页中断属于内中断（故障中断），一条指令执行可能会引发多次缺页中断，如：copy A to B，即将逻辑地址A中的数据复制到 逻辑地址B，而A、B属于不同的页面，则有可能产生两次缺页中断。

2、快表中的表项对应的页面一定是内存中存在的页面，页面换出外存则快表中对应表项也要删除，否则会访问到错误页面。

3、访问页面导致的页表项修改（如修改位置为1，访问次数+1）时，只需改动快表中的表项，只有当快表表项删除时才写回内存的页表中，这样可以减少访存次数。但页面调入内存时既需要修改快表也要修改慢表表项。

4、只有执行写指令才需要修改“修改位”。

5、换入换出页面都需要启动慢速的磁盘IO操作，如果换出换出太频繁会严重影响进程执行效率，也会导致CPU频繁切换进程把CPU时间浪费在切换上。

· 页面置换算法

页面置换算法决定内存不足时由哪个页面换出，页面的换入换出需要磁盘IO，因此一个好的页面算法应该追求更少的缺页率。

缺页时未必发生页面置换。若还有可用的空闲内存块， 就不用进行页面置换。

1.最佳置换算法（OPT）

每次选择淘汰的页面是最长时间内不被访问的页面，这样可以保证最低的缺页率。

遍历在内存中的页面（假如当前有 0,1,2这3个页在内存中，需要置换这3个页中的其中一个），从前往后在待访问页面中找最后一个出现的页号就是要淘汰的页面（例如1号页面是待访问页面中最后一个页面则淘汰1号页）。

最佳置换算法无法实现，因为系统无法预判进程执行过程中会访问哪些页面，以及访问的顺序，系统只能知道当前指令要访问那个页面。

虽然该算法无法实现，但是可以作为其他算法的标准，其他算法的缺页率也接近OPT算法，就说明该算法性能越好，越接近完美。

2、先进先出置换算法（FIFO）

将调入内存的页面根据调入顺序排成一个队列，需要换出页面时选择队头页面（最早换入到内存的页）即可。

队列的最大长度取决于系统为进程分配了多少个内存块。

FIFO可能会出现Belady异常，即当系统为进程分配的内存块数增大时，缺页次数不减反增的异常现象。

该算法与进程实际运行时的 规律不适应，因为先进入的页面也有可能最经常被访问。因此，算法性能差。

3、最近最少未使用算法（LRU）

使用哈希链表实现

实现方式可以参见

操作系统如何管理内存——哈希链表和LRU算法

4、最不经常使用算法（LFU）

操作系统如何管理内存——LFU算法

5、时钟置换算法（CLOCK）

时钟置换算法的理念是优先换出内存中未访问的页中最早进入内存的页，该算法和LRU算法的理念极为相似，都是先换出内存中最久未访问的页。

具体实现如下：每个页面在页表项中对应一个访问位字段（0或1表示最近是否访问过）。内存中的页面链接成 一个循环队列，用一个指针p指向当前访问的页的下一个节点。

当某页被访问时，其访问位置为1。

当需要淘汰一个页面时，检查指针p指向的页的访问位。

如果是0，就选择该页换出；如果是1，则将它置为0，暂不换出，指针p++继续检查下一个页面，若第一轮扫扫描中，所有页面都是1，再进行第二轮扫描（第二轮扫描中一定会

有访问位为0的页面，因此简单的CLOCK 算法选择一个淘汰页面最多会经过两轮扫描）

和LRU不同的是，clock算法使用了一个循环队列，不会改变队列中节点的位置，但是会更新节点的访问位。时钟算法又称为最近未使用算法（NRU）。

6、改进型的时钟置换算法

简单的时钟置换算法仅考虑到页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过， 就不需要执行I/O操作写回外存。

因此，优先考虑最近未被访问过页面中，未被被修改过的页面作为换出的页面 就是改进型的时钟置换算法的思想。

修改位=0，表示页面没有被修改过；修改位=1，表示页面被修改过。用（访问位，修改位）的形式表示各页面状态。如（1，1）表示一个页面近期被访问过， 且被修改过。

改进型时钟置换算法会发生最多4轮循环列表的扫描：

第一轮：从当前位置开始扫描到第一个（0, 0）的帧用于替换。本轮扫描不修改任何标志位

第二轮：若第一轮扫描失败，则重新扫描，查找第一个（0, 1）的帧用于 替换。本轮将所有扫描过的帧访问位设为0

第三轮：若第二轮扫描失败，则重新扫描，查找第一个（0, 0）的帧用于 替换。本轮扫描不修改任何标志位

第四轮：若第三轮扫描失败，则重新扫描，查找第一个（0, 1）的帧用于 替换。

第三、四轮扫描总会成功选择到要置换出去的页。

第一优先级：最近没访问， 且没修改的页面；第二优先级：最近没访问， 但修改过的页面；

第三优先级：最近访问过， 但没修改的页面；第四优先级：最近访问过， 且修改过的页面。

7、页面缓冲算法（PB，page buffering)

该算法是在FIFO算法的基础上，区分内存中修改过和未修改过的页面，优先置换未修改过的页面。

该算法维护两个链表管理某进程所有在内存中的页，一个是修改页链表，一个是非修改页链表。

a. 当某进程内存不足且发生缺页时，以非修改页链表的头部弹出页面节点，该页面A作为被置换页面（该过程遵循FIFO），被换入的页面B被读访问则链入非修改页链表末尾，被写访问则链入修改页链表末尾。

虽然页面A被换出，但由于它没被修改过，因此A不会写回到磁盘，而是直接被覆盖。

b. 当非修改页链表中有页面被修改，则该页节点会放入到修改页链表末尾。当修改页达到一定数量时，一次性将他们一起写回磁盘（可以异步操作），减少磁盘IO请求次数（一次IO请求写回多个页）。写回磁盘后，系统将他们的修改位置为0，并将修改页链表的节点统统链入到非修改页链表尾部。

所以，发生缺页时只需读磁盘，无需写回磁盘，进程可以尽快的重新启动。这两个链表充当了页面缓存的作用。

页面缓冲算法是一种节省磁盘IO请求的理念

· 驻留集

驻留集是OS分配给一个进程的物理块集合。字面意思就是一个进程常驻在物理内存的大小。通俗的来说就是操作系统会分配多大的实际内存给某进程。

考虑一个极端情况，若某进程共 有100个页面，则该进程的驻留 集大小为100时进程可以全部放 入物理内存，运行期间不可能再发生 缺页。若驻留集大小为1，则进 程运行期间必定会极频繁地缺页。

若驻留集太小，会导致缺页频繁（内存抖动），系统要花大量的时间来处理缺页，实际用于进程执行的时间很少；

驻留集太大，又会导致多道程序并发度下降（因为能装入内存的进程数量少了），内存利用率降低。

因此系统为进程分配多少物理内存，一个合适的驻留集有多大决定了进程的运行效率，这也是页面分配策略要做的事情。

· 页面分配策略

页面分配策略分为两种

固定分配：OS在进程装入时运行前为进程分配数量固定的物理块，并且在该进程运行过程中不变。即驻留集大小不可变。

可变分配：OS在进程装入时分配一定数量的物理块，在进程运行期间根据该进程缺页率适当增加或较少分配给它的内存。即驻留集大小可变。

置换策略按在内存不足的情况下，为了换入本进程的页是否允许换出其他进程的页也分为两种

局部置换：发生缺页时，只能选本进程自己的物理块进行置换。

全局置换：发生缺页时，可以将操作系统保留的空闲物理块分配给缺页进程，也可以将其他进程持有的物理块换出到外存，然后分配给缺页进程。

PS：全局置换下，操作系统会保持一个空闲物理块队列，当进程用完了分配给自己的块且缺页时，系统先将队列中的空闲块分配给缺页进程，当队列中的块用完之后，才会选择其他进程未锁定的页面换出外存再分配给缺页进程。但这么一来会导致其他进程的缺页率增加。

锁定的页面如重要的内核数据，这些信息需要常驻内存，用于系统管理。

可变分配全局置换：只要进程缺页就给分配新物理块给该进程。

可变分配局部置换：要根据发生缺页率来动态地增加或减少分配给进程的物理块

页面调入的时机

页面调入的时机有两个：进程初次装入内存时需要分配多个物理块给其运行时马上会用到的代码段和数据段；运行期间缺页时调入页面，该情况下每次只能调入一页，IO开销较大。

运行之前进程有关的代码和数据全部放在磁盘的文件区，因此第一次调入会从文件区调入到内存。运行过程中的页面换入换出则发生在内存和对换区之间。

内存抖动

系统中刚换出的页面马上换入内存，刚换入的页面有马上换出到外存，这种内存页面频繁缺页和换入换出的现象称为内存抖动。

产生抖动的原因是进程经常访问的那些页面数量高于进程可用的物理块数（驻留集不够）。这可能是因为操作系统的页面分配策略不合理，也可能是因为系统投入运行的作业数量太多，导致内存分给每个进程的内存块不足。

产生抖动的后果是CPU时间消耗在页面对换上，而非进程运行上，导致进程运行效率降低。

下面是CPU利用率和多道程序度（数量）的关系：

内存抖动可能引发恶性循环，因为操作系统监控到CPU利用率降低可能会继续把更多进程投入作业导致情况恶化。

避免和控制抖动

1. 挂起优先级低的进程，或者大进程，或者缺页率高的进程（相当于减少作业数量），腾出内存空间供剩余的抖动进程使用。

2.监控每个进程的缺页率，按进程缺页率决定和改变分配的内存块数量（当然，如果所有进程的缺页率都很高，那就只能挂起某些进程）。

3.使用工作集策略。

· 工作集

为了让系统分配一个合适大小的驻留集给进程，科学家们提出了工作集的概念。

工作集是指某进程运行过程中，操作系统划出一个大小为n的固定窗口，窗口内是该进程最近访问的n个页面，n个页面中的不重复页面就是工作集。

一个进程被分配的驻留集大小应大于等于工作集大小（而且该过程是动态的，因为工作集大小也会随时间变化而变化），使得工作集内的页面总是留存在内存中（CPU总能在内存中命中工作集页面），从而有效避免进程频繁缺页。

例如在一个窗口为4的场景，进程运行到正在访问第23个页面时，它的工作集如下

此时系统应该将分配给进程的内存块（驻留集）控制在4或4以上。

此时系统应该将分配给进程的内存块（驻留集）控制在3或3以上。

如果某一时刻，进程的工作集大小/窗口大小越小，说明该段时间内进程集中访问少数的几个页，即说明进程在该段时间内的局部性越强。

最后小结：缺页率与页面置换算法、页面分配策略和置换策略直接相关。

更多内容请关注微信公众号