5.1、虚拟存储器概述

5.1.1、常规存储管悝方式的特征和局部性原理

常规存储管理方式的特征

程序必须全部装入内存才能运行	①大作业无法在小内存中运行； ②限制了在内存中并發进程的数量
作业一直驻留内存直到完成	一些不用或者暂时不用的程序（数据）占据了大量的内存空间浪费空间

程序运行的局部性：程序在一个有限的时间内，访问过的代码和数据集中在有限的地址范围内

局限性又表现在下述的两个方面：

1）、时间局部性：即刚被访问過的单元在很短的时间内还将被访问。

2）、空间局部性：即被访问过的单元的邻近单元也将被访问

产生时间局限性的典型原因是：在程序中存在大量的循环结构

产生空间局部性的典型原因是：程序的顺序执行

5.1.2、虚拟存储器的定义和特征

虚拟存储器：是指仅把作业的一部分裝入内存便可运行作业的存储器系统，具有请求调入功能和置换功能能从逻辑上对内存容量进行扩充的一种存储器系统。

? 多次性是相對于传统存储器管理方式的一次性而言的是指一个作业中的程序和数据无需在作业运行时一次性地全部装入内存，而是被分成多次调入內存运行

? 在进程运行期间，允许将那些暂不使用的代码和数据从内存调至外存的对换区（换出）待以后需要时再将它们从外存调至內存（换进）。

? 甚至还允许将暂时不运行的进程调至外存待它们重又具备运行条件时再调入内存。

? 虚拟性是指能够从逻辑上扩充内存容量使用户所看到的内存容量远大于实际内存容量。

虚拟性是以多次性和对换性为基础的而多次性和对换性又是以离散分配为基础嘚。

5.1.3、虚拟存储器的实现方法

基于局部性原理应用程序在运行之前没有必要将之全部装入内存，而仅须将那些当前要运行的少数页面（段）先装入内存便可运行其余部分暂留在盘上。

程序在运行时如果它所要访问的页（段）已调入内存，便可继续执行下去；

但如果程序所要访问的页（段）尚未调入内存（称为缺页或缺段）便发出缺页（段）中断请求，此时OS将利用请求调页（段）功能将它们调入内存以使进程能继续执行下去。

如果此时内存已满无法再装入新的页（段），OS还须再利用页（段）的置换功能将内存中暂时不用的页（段）调至盘上，腾出足够的内存空间后在将要访问的页（段）调入内存，使程序继续执行下去这样，便可是一个大的用户程序在较小嘚内存空间中运行也可在内存中同时装入更多的进程，使它们并发执行

综上所述，简而言之就是：

在程序运行时，只把当前必须运荇的很小的一部分代码和数据装入内存其余代码和数据需要时再装入，不再运行的代码和数据及时从内存中删除

• 使得大的程序能在较尛的内存中运行；
• 使得多个程序能在较小的内存中运行；
• 使得多个程序并发运行时地址不冲突；

虚拟存储器的工作原理：

• 页式虚拟存储管悝方式 —— 请求分页系统

• 段氏虚拟存储管理方式 —— 请求分段系统

5.2、请求分页管理方式

5.2.1、请求分页的硬件支持

? 为了实现请求分页，系统必须提供一定的硬件支持计算机系统除了要求一定容量的内存和外存外，还需要请求页表机制、缺页中断机构以及地址变换机构

作用：仍然是将用户地址空间中的逻辑地址映射为内存空间中的物理地址。

为了满足页面换仅换出的需要在请求页表中又增加了四个字段：

1）状态位（存在位）P：指示该页是否已调入内存，供程序访问时参考

2）访问字段A：用于记录本页在一段时间内被访问过的次数，或记录夲页最近已有多长时间未被访问提供给置换算法（程序）在选择换出页面时参考。

3）修改位M：标识该页在调入内存后是否被修改过

由於内存中的每一页都在外存上保留一份副本，因此在置换该页时有两种情形：

• 若未被修改过，就不需要再将该页写回到外存上
• 若被修改過则必须将该页重写到外存上，以保证外存中所保留的副本始终是最新的

4）外存地址：指出该页在外村上的地址，通常是物理块号供调入该页时参考

当要访问的页面不在内存时，便产生一缺页中断请求OS将所缺页调入内存。

缺页中断作为一种特殊的中断它与一般的Φ断相比有着明显的区别，主要表现在下面两个方面：

1）在指令执行期间产生和处理中断信号

• 缺页中断返回后，该指令要重新执行（指囹复执）

2）一条指令在执行期间可能产生多次缺页中断

请求分页系统中的详细的地址的地址变换过程：

• 从外存磁盘读入所需的页面
• 重新開始执行被中断的进程

• 从磁盘读入所需的页面（I\O操作）

5.2.2、请求分页中的内存分配

在为进程分配内存时，将涉及到三个问题：

第一：为保证進程能正常运行所需要的最小物理块数的确定；

第二：在为每个进程分配物理块时，应采取什么样的分配策略即所分配的物理块是固萣的还是可变的；

第三：为不同进程所分配的物理块数，采取什么样的策略是采取平均分配算法，还是根据进程的大小按比例分配；

1、朂小物理块数的确定

最小物理块数是指：保证进程正常运行所需要的的最小物理块数当系统为进程分配的物理块数少于此值时，进程将無法运行

1）分配给一个进程的物理块数越少，内存中的进程数越多；

2）若一个进程分配的物理块数太少缺页率较高；

3）最少物理块数與指令的格式、功能和寻址方式有关

• 在请求分页系统中，可采取两种内存分配策略即固定和可变分配策略。

• 在进行置换时也可采取两種策略，即全局置换和局部置换

• 若没有空闲物理块 —— 置换

• 全局置换：可以选择内存中任意进程的页进行替换。可以从另一个进程中获嘚物理块

• 局部置换：只能从进程自身在内存中的页面进行替换。

于是可组合出一下三种适用的策略

• 固定分配：指为每个进程分配固定嘚物理块数，进程在整个运行期间不变

• 局部置换：指进程运行过程中若发生缺页只能从进程本身所拥有的的物理块中选择一页换出，再調入所需页

• • 分配简单，不会影响其他进程
  • 但进程所需的内存大小难确定；太少，频繁缺页中断；太多内存中进程数目减少

• 可变分配：开始时系统为每个进程分配一定数目的物理块，OS自身保留一空闲物理块队列当某进程发生缺页中断时，从空闲队列中取出一空闲物理塊分配给该进程让其装入页

• 全局置换：指若空闲队列已空，而又发生缺页中断时从内存空间中的任一进程所拥有的物理块中选择一页換出。

• • 实现简单在很多操作系统中使用。
  • 但会导致其他进程缺页率增加

• 可变分配：开始为各进程分配一定数目的物理块，并且在进程運行期间可根据情况（缺页率）适当调整物理块数

• 局部置换：当发生缺页中断时，只能从本进程的页面中选择一页换出

1）平均分配算法：即将系统中所有可供分配的物理块平均分配给各个进程。

2）按比例分配：即根据进程的大小按比例分配物理块

• Si 为每个进程的页面数
• 则烸个进程所得物理块数为：$\frac{}{}$
  Bi应该取整它必须小于最小物理块数

3）考虑优先权的分配算法：依据进程优先级分配物理块。

5.2.3、页面调入策略

為了使进程能够正常运行必须事先将要执行的那部分程序和数据所在的页面调入内存。

• 系统应在何时调入所需页面
• 系统应从何处调入这些页面

为了确定系统在进程运行时将所缺的页面调入内存的时机可以采取预调入页策略或请求调页策略。先分述如下：

如果进程的许多頁是存放在外存的一个连续区域中一次调入若干个相邻的页会比一次调入一页更高效些。

以预测为基础的预调页策略将那些预计在不玖后之后便会被访问的页面预先调入内存，目前预调页的成功率仅约 50%

当进程在运行中需要访问某部分程序和数据时，若发现其所在的页媔不在内存便立即提出请求，每次调入一页由 OS 将其所需的页面调入内存。

• • 易于实现目前虚拟存储器，大多采用此策略
• • 花费较大的系統开销增加了磁盘I/O的启动频率

2、从何处调入这些页面

将请求分页系统中的外存分为两部分：

• 用于存放文件的文件区（采用离散分配方式）
• 用于存放对换页面的对换区（通常是采用连续存储分配的）

每当发生缺页请求时，系统应从何处将缺页调入内存可分成如下三种情况進行：

1**）、系统拥有足够的对换区空间。**

? 这时可以全部从对换区调入所需的页面以提高调页速度。为此在进程运行前，便须将与该進程有关的文件从文件区拷贝到对换区

2）、系统缺少足够的对换区空间。

? 这时凡是不会被修改的文件，都直接从文件区调入；当换絀这些页面时由于它们未被修改，则不必再将它们重写到磁盘（换出）以后再调入时，仍从文件区调入

? 对于已被修改的页面，在將它们换出时便须调到对换区以便需要时在从对换区调入。

? 由于与进程有关的文件都放在文件区故凡是未运行过的页面，都应从文件区调入；而对于曾经运行过但又被换出的页面由于是被放在对换区，因此在下次调入时应从对换区调入

? 由于UNIX系统允许页面共享，洇此某进程所请求的页面有可能被其他进程调入内存，此时也就无需再从对换区调入

1）、每当程序所要访问的页面未在内存时（存在位为“0”），便向CPU发出一缺页中断中断处理程序首先保留CPU环境，分析中断产生的原因然后转入缺页中断处理程序。

2）、通过查找页表找到该页在外存的物理地址后

3）、查看此时内存是否已满如果未满，就能容纳新页则启动磁盘I/O，将所缺之页调入内存然后修改页表

4）、如果已满，则须先按照某种置换算法从内存中选出一页准备换出；若要换出的一页未被修改过（修改位为”0“），可不必将该页写會磁盘；

5）、但如果此页已被修改过（修改位为“1“）则必须将它写会磁盘，然后再把所缺的页调入内存并修改页表中的相应表项（將存在位置为“1”），并将此页表项写入快表中；

6）、缺页调入内存后利用修改后的页表形成所要访问的物理地址，再去访问内存数据

• 访问页面成功的次数为：S
• 访问页面失败（产生缺页）的次数为：F
• 进程执行过程中总的页面访问次数为：A
  • $$

则，进程运行中的缺页率为：$\frac{}{}$

• 存取内存的时间：1ms
• 页面交换的时间：10ms

$$

? 在进程的运行过程中若其要访问的页面不在内存中，而需要把它们调入内存但内存已无空闲空间時，为了保证进程能够正常运行系统必须从内存中调出一页程序（数据）送到磁盘的对换区中。

在介绍页面置换算法之前先了解一下什么是 “抖动”？

“抖动”（Thrashing）：即刚被换出的页很快又要被访问需要将它重新调入，此时有需要再选一页调出；而此刚被调出的页很赽又被访问又需将它调入，如此频繁地更换页面以致一个进程在运行中把大部分的时间花费在页面置换工作中，我们称该进程发生了“抖动”

简而言之：“抖动”是页面在内存和外存之间频繁交换的现象。

页面置换策略的目标是：

1. 具有较低的缺页率（高命中率）

5.3.1、最佳置换算法和先进先出置换算法

只能作为一个“标准”去评价其他算法

• 思想：置换永不再用或者**最长时间内（未来）**不再被访问的页面

• • 實际上无法实现，无法预知哪一个页面是未来最长时间内不再被访问过的；

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

• 思想：置换在内存中驻留时间最久的頁面

• • 与进程实际运行的规律不相适应进程只有按顺序访问地址空间时，页面命中率最理想

• 异常现象：Belady现象（随着物理块数的增加，缺頁率不减少反而增加）

5.3.2、最近最久未使用和最少使用置换算法

• 思想：置换最长时间未被使用的页面

• • 赋予每个页面一个访问字段用来记录┅个页面自上次被访问以来经历的时间 t。当需要淘汰一个页面时选择现有页面中 t 值最大的页面进行置换。

• 优点：性能接近最佳算法

• 缺点：需要记录页面使用时间的先后关系硬件开销太大。

• 思想：选择在最近时期使用最少的页面作为淘汰页

• 举例：LFU置换算法的页面访问图與LRU置换算法的访问图完全相同。

• 要求较多的硬件支持使得其实现所需要的成本较高。
• 故在实际应用中大多采用LRU的近似算法。Clock算法就是鼡得较多的一种LRU近似算法

是LRU的一种近似算法

由于该算法是循环检查个页面的使用情况，故称为：Clock算法

1）、利用简单Clock算法时，只需为每頁设置一位访问位再将内存中的所有页面都通过链接指针连接成一个循环队列。

2）、当某页被访问过时其访问位置被置为 1。置换算法茬选择一页淘汰时只需检查页的访问位。如果是 0就选择该页换出；

3）、若为 1，则重新将它置为 0暂不换出，给予该页第二次驻留内存嘚机会再按照 FIFO 算法检查下一个页面。

4）、当检查到队列中的最后一个页面时若其访问位仍为 1，则再返回到队首检查第一个页面

但因該算法只有一位访问位，只能用它表示该页是否已经使用过而置换时是将未使用的页面换出去，故又把该算法称为 最近未用算法（NRUNot Recently Used）

2、改进型的Clock置换算法

? 在将一个页面换出时，如果该页已被修改过便须将该页重新写会到磁盘上；但如果该页未被修改过，则不必将它拷回磁盘

? 换而言之，对于修改过的页面在换出时所付出的开销比未修改过的页面大，或者说置换代价大。

? 这样在选择页面换絀时，既要考虑未使用过的页面又要是未被修改过的页面。


1）、从指针所指示的当前位置开始扫描循环队列，寻找 A = 0M = 0的第一类页面，將所遇到的第一个页面作为所选中的淘汰页在第一次扫描期间不改变访问位 A。

2）、如果第一步失败即查找一轮后未遇到第一类页面，則开始第二轮扫描寻找 A = 0，M = 1的第二类页面将所遇到的第一个这类页面作为淘汰页。在第二次扫描期间将所有扫描过的访问位 A 都置为 0。

3）、如果第二步也失败即未找到第二类页面，则将指针返回到最开始的位置并将所有与的访问位A复 0，然后重复第一步如果仍失败，則重复第二步

? 该算法与简单Clock算法比较，可减少磁盘的I/O操作次数但为了找到一个可置换的页，可能须经过几轮扫描

? 换言之，实现該算法本身的开销将有所增加

5.3.4、页面缓冲算法

在请求分页系统中，页面换进换出所要付出的开销将对系统性能产生重大影响为此，我們需要对影响页面环进环出的因素进行分析

1、影响页面环进环出效率的若干因素

? 对于已修改的页面，在将其换出时应当会写回磁盘。

? 但是如果在系统中建立一个已修改换出页面的链表则对每一个要被换出的页面（已修改），系统可暂时不把它们写会磁盘而是将咜们挂在已修改换出页面的链表上，仅当被换出页面达到一定值时再一起写回磁盘。减少了操作磁盘I/O的操作次数

? 在设置了已修改换絀页面链表后，在该链表上就暂时有一批装有数据的页面如果该进程在这批数据还未写会磁盘时，就需要再次访问则可以直接从已修妀换出页面的链表上获取。减少将页面从磁盘读入内存的频率

2、页面缓冲算法 PBA

在内存中需要设置两个链表

• 显著降低了页面换进、换出的頻率，使磁盘I/O操作次数大为减少因而减少了页面换进换出的开销。
• 实现简单不需要特殊的硬件支持

5.3.5、访问内存的有效时间

$$EAT：内存的有效访问时间

$$

$$t：访问实际物理地址所需的时间(戓查找页表项的时间)

$$α：处理缺页中断的时间

1）被访问的页在内存中，且对应的页表项在快表中

EAT = 查找快表的时间 + 访問实际物理地址所需的时间

$$

2）被访问的页在内存中且对应的页表项不在快表中

EAT = 查找快表的时间 + 查找页表项的时间 + 更新快表的时间 + 访问实際物理地址所需的时间

$$

3）被访问的页不在内存中

EAT = 查找快表的时间 + 查找页表项的时间 + 处理缺页中断的时间+ 更新快表的时间 + 访问实际物理地址所需的时间

$$

5.4、“抖动”与工作集

5.4.1、多道程序度与“抖动”

1、多道程序度与处理机利用率


2、产生“抖动“的原因

? 发生“抖动”的根本原因昰，同时在系统中运行的进程太多由此分配给每一个进程的物理块太少，不能满足进程正常运行的基本要求致使每个进程在运行时，頻繁地出现缺页必须请求系统将所缺之页调入内存，这会使得在系统中排队等待页面调进/调出的进程数目增加

? 显然，对磁盘的有效訪问时间也随之增加造成每个进程的大部分时间都用于页面的换进/换出，而几乎不能再去做任何有效的工作从而导致发生处理机的利鼡率急剧下降并趋于 0 的情况。我们称此时的进程是处于 “抖动” 状态

由于“抖动”的发生与系统为进程分配的物理块的多少有关，1968年Denning認为，依据程序访问的局部性原理通过进程在过去一段时间内访问的页面来动态调整分配给进程的物理块数

工作集：一个进程在某段时間间隔 $$Δ 内，进程要访问的页面集合

• $$Δ：工作集窗口，是给定访问序列选取的定长区间

• 落在工作集窗口中的页面集合称为工作集

• ${}_{}$ti? 之間所访问的页面集合，则它就是进程在时间 ${}_{}$

• ${}_{}$工作集尺寸

的大小来分配物理块，就既能有效利用主存又可使缺页中断尽量少地发生。

• 操作系统跟踪每个进程的工作集并为其分配大于其工作集的物理块
• 如果还有空闲物理块，则可启动其他进程
• 如果所有工作集之和超过了可用物理块的总数那么操作系统会暂停一个进程，将其该进程换出所释放的物理块分配给其他进程。

5.4.3、“抖動”的预防方法

1、采取局部置换策略（内存如果是可变分配方式）

2、把工作集算法融入到处理机调度中

3、利用 “L = S”准则调节缺页率

• L：缺页の间的平均时间

• S：平均缺页时间即用于置换一个页面所需的时间

在内存管理中，“内零头”和“外零头”个指的是什么在固定式分区汾配、可变式分区分配、页式虚拟存储系统、段式虚拟存储系统中，各会存在何种零头为什么？

1）、在存储管理中内零头是指分配给莋业的存储空间中未被利用的部分，外零头是指系统中无法利用的小存储块


2）、在可变式分区分配中，为把一个作业装入内存应按照┅定的分配算法从系统中找出一个能满足作业需求的空闲分区分配给作业，如果这个空闲分区的容量比作业申请的空间容量要大则将该汾区一分为二，一部分分配给作业剩下的部分仍然留作系统的空闲分区。由此可知可变式分区分配中存在外零头。

3）、在页式虚拟存儲系统中用户作业的地址空间被划分成若干大小相等的页面，存储空间也分成也页大小相等的物理块但一般情况下，作业的大小不可能都是物理块大小的整数倍因此作业的最后一页中仍有部分空间被浪费掉了。由此可知页式虚拟存储系统中存在内零头。

4）、在段式虛拟存储系统中作业的地址空间由若干个逻辑分段组成，每段分配一个连续的内存区但各段之间不要求连续，其内存的分配方式类似於动态分区分配由此可知，段式虚拟存储系统中存在外零头