6.1 虚拟存储器概述
1. 传统存储器
连续分配：
单一连续分配
固定分区分配
动态分区分配
非连续分配：
基本分页存储管理
基本分段存储管理
基本段页式存储管理
2.传统存储器特征
一次性：作业必须一次性全部装入内存后，才能开始运行。这会导致两种情况：
①当作业很大而不能全部被装入内存时，将使该作业无法运行；②当大量作业要求运行时，由于内存不足以容纳所有作业，只能使少数作业先运行，导致多道程序度的下降。驻留性：作业被装入内存后，就一直驻留在内存中，其任何部分都不会被换出，直至作业运行结束。运行中的进程会因等待IO而被阻塞，可能处于长期等待状态。
由以上分析可知，许多在程序运行中不用或暂时不用的程序（数据）占据了大量的内存空间，而一些需要运行的作业又无法装入运行，显然浪费了宝贵的内存资源。
3.局部性原理
快表、页高速缓存及虚拟内存技术都属于高速缓存技术，这个技术所依赖的原理就是局部性原理。
时间局部性：程序中的某条指令一且执行，不久后该指令可能再次执行；某数据被访问过，不久后该数据可能再次被访问。产生的原因是程序中存在着大量的循环操作。
空间局部性：一旦程序访问了某个存储单元，在不久后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，因为指令通常是顺序存放、顺序执行的，数据也一般是以向量、数组、表等形式聚存储的。
6.1.2 虚拟存储器的定义与特征
程序不需全部装入即可运行，运行时根据需要动态调入数据，若内存不够，还需换出一些数据。系统好像为用户提供了一个比实际内存容量大得多的存储器，称为虚拟存储器。
多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存。对换性：无需在作业运行时一直常驻内存，而是允许在作业运行过程中，将作业换入、换出。虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量。
6.1.3 虚拟存储器的实现方式
请求分页系统
请求分段系统
请求段页式存储
所需要的硬件支持
一定容量的内存和外存。页表机制（或段表机制），作为主要的数据结构。中断机构，当用户程序要访问的部分尚未调入内存时，则产生中断。地址变换机构，逻辑地址到物理地址的变换。
访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存（请求调页功能）
内存空间不够时，将内存中暂时用不到的信息换出到外存（页面置换功能）
6.2 请求分页存储器管理
请求分页系统建立在基本分页系统基础之上，为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能。请求分页是目前最常用的一种实现虚拟存储器的方法。
6.2.1 分页中的硬件支持
1.请求页表机制
请求分页系统在一个作业运行之前不要求全部一次性调入内存，因此在作业的运行过程中，必然会出现要访问的页面不在内存中的情况。因此在请求页表项中增加了 4个字段，如下图所示
状态位P：用于指示该页是否已调入内存，供程序访问时参考。访问字段A：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供置换算法换出页面时参考。修改位M：标识该页在调入内存后是否被修改过，以确定页面置换时是否写回外存。外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入该页时参考。
2.缺页中断机构
在请求分页系统中，每当所要访问的页面不在内存中时，便产生一个缺页中断，请求操作系统将所缺的页调入内存。同样会经历保护现场、分析中断原因、恢复现场等。
缺页中断执行过程
先将缺页的进程阻塞（调页完成唤醒)，若内存中有空闲块，则分配一个块，将要调入的页装入该块，并修改页表中的相应页表项，若此时内存中没有空闲块，则要淘汰某页（若被淘汰页在内存期间被修改过，则要将其写回外存）。 缺页中断和一般中断的区别：
在指令执行期间而非一条指令执行完后产生和处理中断信号，属于内部异常。一条指令在执行期间，可能产生多次缺页中断。
3.地址变换机构
请求分页系统中的地址变换机构，是在分页系统地址变换机构的基础上，为实现虚拟内存，又增加了某些功能而形成的，如产生和处理缺页中断，及从内存中换出一页的功能等等。
新增步骤1：请求调页（查到页表项时进行判断）新增步骤2：页面置换（需要调入页面，但没有空闲内存块时进行)新增步骤3：需要修改请求页表中新增的表项
①只有“写指令”才需要修改“修改位”。并且，一般来说只需修改快表中的数据，只有要将快表项删除时才需要写回内存中的慢表。这样可以减少访存次数。
②和普通的中断处理一样，缺页中断处理依然需要保留CPU现场。
③需要用某种“页面置换算法”来决定一个换出页面（下节内容）
④换入/换出页面都需要启动慢速的I/O操作，可见，如果换入换出太频繁，会有很大的开销。
⑤页面调入内存后，需要修改慢表，同时也需要将表项复制到快表中。
6.2.2 请求分页中的内存分配
1.驻留集（物理块）的大小
给一个进程分配的物理页框的集合就是这个进程的驻留集。
分配给一个进程的页框越少，驻留在主存中的进程就越多，从而可提高CPU的利用率。若一个进程在主存中的页面过少，则尽管有局部性原理，缺页率仍相对较高。若分配的页框过多，则由于局部性原理，对该进程的缺页率没有太明显的影响。
2. 内存分配策略
在请求分页系统中，可采取两种内存分配策略，即固定和可变分配策略。在进行置换时，也可采取两种策略，即全局置换和局部置换。
固定分配：操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。即，驻留集大小不变可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。即驻留集大小可变局部置换：发生缺页时只能选进程自己的物理块进行置换。全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。
固定分配VS可变分配：区别在于进程运行期间驻留集大小是否可变
局部置换VS全局置换：区别在于发生缺页时是否只能从进程自己的页面中选择一个换出
固定分配局部置换
它为每个进程分配一定数目的物理块，在整个运行期间都不改变。
若进程在运行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面。
可变分配全局置换
为系统中的每个进程分配一定数目的物理块，操作系统自身也保持一个空闲物理块队列。
当某进程发生缺页时，系统从空闲物理块队列中取出物理块分配给该进程，井将欲调入的页装入其中。
可变分配局部置换
它为每个进程分配一定数目的物理块，当某进程发生缺页时，只允许从该进程在内存的页面中选出一页换出动态变换，频繁缺页，分配物理块，缺页率低，减少物理块
3.物理块分配算法
采用固定分配策略时，将系统中的空闲物理块分配给各个进程，可采用下述几种算法。
平均分配算法，将系统中所有可供分配的物理块平均分配给各个进程。按比例分配算法，根据进程的大小按比例分配物理块。优先权分配算法，为重要和紧迫的进程分配较多的物理块。通常采取的方法是把所有可分配的物理块分成两部分：一部分按比例分配给各个进程；一部分则根据优先权分配。
6.2.3 页面调入策略
1.何时调入页面
为确定系统将进程运行时所缺的页面调入内存的时机，可采取以下两种调页策略：
**预调页策略：**将预计在不久后便会被访问的页面预先调入内存；主要用于进程的首次调入，由程序员指出应先调入哪些页。**请求调页策略：**进程在运行中需要访问的页面不再内存而提出请求，由系统将所需页面调入内存。每次仅调入一页，增加了磁盘I/O开销。
2.从何调入页面
请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。
对换区采用连续分配方式，而文件区采用离散分配方式，因此对换区的磁盘IO速度比文件区的更快。这样，当发生缺页请求时，系统从何处将缺页调入内存就分为三种情况：
系统拥有足够的对换区空间
可以全部从对换区调入所需页面，以提高调页速度。为此，在进程运行前，需将与该进程有关的文件从文件区复制到对换区。
系统缺少足够的对换区空间
凡是不会被修改的文件都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出。但对于那些可能被修改的部分，在将它们换出时须调到对换区，以后需要时再从对换区调入（因为读比写的速度快）。
UNIX方式
运行之前进程有关的数据全部放在文件区，故未使用过的页面，都可从文件区调入。若被使用过的页面需要换出，则写回对换区，下次需要时从对换区调入。进程请求的共享页面若被其他进程调入内存，则无须再从对换区调入
3. 如何调入页面
当进程所访问的页面不在内存中时（存在位为0)，便向CPU发出缺页中断，中断响应后便转入缺页中断处理程序。
该程序通过查找页表得到该页的物理块，此时如果内存未满，则启动磁盘I/O，将所缺页调入内存，并修改页表。
如果内存已满，则先按某种置换算法从内存中选出一页准备换出；
如果该页未被修改过（修改位为0)，则无须将该页写回磁盘；如果该页已被修改（修改位为1)，则必须将该页写回磁盘，然后将所缺页调入内存，并修改页表中的相应表项，置其存在位为1。
调入完成后，进程就可利用修改后的页表形成所要访问数据的内存地址。
4.缺页率
6.3 页面置换算法
进程运行时，若其访问的页面不在内存中而需将其调入，但内存已无空闲空间时，就需要从内存中调出一页程序或数据，送入磁盘的对换区，选择调出页面的算法就称为页面置换算法
1.最佳页面置换算法（*optimal , OPT)
贝莱迪（Belady) 提出的理论算法，无法实现
选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。
2. 先进先出页面置换算法（first in first out ,FIFPO）
优先淘汰最早进入内存的页面，即在内存中驻留时间最久的页面。
3.最近最久未使用页面置换算法（least recetly used, LRU)
选择最近最长时间未访问过的页面予以淘汰，它认为过去一段时间内未访问过的页面，在最近的将来可能也不会被访问。
向后看
4.最少使用页面置换算法（least frequently used ,LFU )
缺页中断率最低
使用移位寄存器记录访问频率，将最近时期使用最少的页面淘汰。
5.Clock页面置换算法又称最近未用置换算法（not recently used ,NRU)
为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出；如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描）
6.改进CLOCK页面置换算法（加入修改位）
简单时钟问题：简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过，就不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。
因此，除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面，避免I/O操作。这就是改进型的时钟置换算法的思想。
修改位=0，表示页面没有被修改过：修改位=1，表示页面被修改过。
算法规则：将所有可能被置换的页面排成一个循环队列，用（访问位A，修改位M）表示各页面状态。
替换帧优先级：
1类A=0，M=0：最近未被访问且未被修改，是最佳淘汰页。2类A=0，M=1：最近未被访问，但已被修改，不是很好的淘汰页。3类A=1，M=0：最近已被访问，但未被修改，可能再被访问。4类A=1，M=1：最近已被访问且已被修改，可能再被访问。
第一轮：第一优先级——最近设访问，且没修改的页面
从当前位置开始扫描到第一个(0，0)的帧用于替换。本轮扫描不修改任何标志位
第二轮：第二优先级——最近没访问，但修改过的页面
若第一轮扫描失败，则重新扫描，查找第一个（0，1）的帧用于替换。本轮将所有扫描过的帧访问位设为0
第三轮：第三优先级——最近访问过，但没修改的页面
若第二轮扫描失败，则重新扫描，查找第一个（0，0）的帧用于替换。本轮扫描不修改任何标志位
第四轮：第四优先级——最近访问过，且修改过的页面
若第三轮扫描失败，则重新扫描，查找第一个（0，1）的帧用于替换。
由于第二轮己将所有帧的访问位设为0，因此经过第三轮、第四轮扫描定会有一个帧被选中，因此改进型CLOCK置换算法选择一个淘汰页面最多会进行四轮扫描。
性能：算法开销较小，性能也不错
对比：
6.3.4 页面缓冲算法（page buffering algorithm ,PBA)
1. 影响页面换入\换出 效率的因素
1）页面置换算法
2）已修改页面写回磁盘的频率
3 ）将磁盘内容读入内存的频率
2.页面缓冲算法
保存已修改需要换出的页面，等被换出的页面数量达到一定值时，在一起换出至磁盘，以达到减少页面换出开销的目的。
6.3.5 请求分页系统的内存有效访问时间
6.4 “抖动”与工作集
1. 抖动
定义：抖动，又称颠簸，指在页面置换过程中，刚刚换出的页面马上又要换入主存，刚刚换入的页面马上又要换出主存。
抖动发生的原因：系统中同时运行的进程太多，由此分配给每个进程的物理块太少，不能满足进程正常运行的基本要求，致使每个进程在运行时频繁地出现缺页，必须请求系统将所缺页面调入内存。
抖动的危害：
使得在系统中排队等待页面调入/调出的进程数目增加。对磁盘的有效访问时间也随之急剧增加，造成每个进程的大部分时间都用于页面的换入/换出，而几乎不能再去做任何有效的工作，进而导致发生处理机的利用率急剧下降并趋于零的情况。
2.工作集
由于抖动的发生与系统为进程分配物理块的多少有关，于是又提出了关于进程工作集的概念。
工作集是指在某段时间间隔内，进程要访问的页面集合。
基于局部性原理，可以用最近访问过的页面来确定工作集。一般来说，工作集W WW可由时间t tt和工作集窗口大小Δ ΔΔ来确定。例如，某进程对页面的访问次序如下：
假设系统为该进程设定的工作集窗口大小Δ ΔΔ为5，则在t 1 t_1t1时刻，进程的工作集为{2,3,5}，在t 2 t_2t2时刻，进程的工作集为{1,2,3,4}。
工作集大小一般会比窗口小很多，工作集反映了进程在接下来的一段时间内很有可能会频繁访问的页面集合，因此，若分配给进程的物理块小于工作集大小，则该进程就很有可能频繁缺页。
一般来说分配给进程的物理块数（即驻留集大小）要大于工作集大小。
6.4.3 抖动预防的方法（p190)
1.采取局部置换策略
2. 把工作集算法融入处理机调度中
3. 利用“L=s ”准则调节缺页率
4. 选择暂停的进程
6.5 请求分段存储管理方式
6.5.1 请求分段中的硬件支持
1. 请求段表机制
2. 缺段中断机制
3. 地址变换机构
6.6 内存映射文件
6.7 地址翻译
（参考王道3.2.8）
地址翻译（虚拟地址-＞Cache）_虚拟地址cache-CSDN博客
1）为什么要引入虚拟内存？
上一节提到过，多道程序并发执行不仅使进程之间共享了处理器，而且同时共享了主存。然而，随着对处理器需求的增长，进程的执行速度会以某种合理平滑的方式慢下来。但是，若同时运行的进程太多，则需要很多的内存，当一个程序没有内存空间可用时，那么它甚至无法运行。所以，在物理上扩展内存相对有限的条件下，应尝试以一些其他可行的方式在逻辑上扩充内存。
2）虚拟内存（虚存）空间的大小由什么因素决定？
虚存的容量要满足以下两个条件
虚存的实际容量 ≤ 内存容量和外存容量之和，这是硬件的硬性条件规定的，若虚存的实际容量超过了这个容量，则没有相应的空间来供虚存使用。 虚存的最大容量 ≤ 计算机的地址位数能容纳的最大容量。假设地址是32位的，按字节编址，一个地址代表1B存储空间，则虚存的最大容量≤4GB（2^32B）。这是因为若虚存的最大容量超过4GB，则32位的地址将无法访问全部虚存，也就是说4GB以后的空间被浪费了，相当于没有一样，没有任何意义 。 实际虚存的容量是取条件1和2的交集，即两个条件都要满足，仅满足一个条件是不行的。
3）虚拟内存是怎么解决问题的？会带来什么问题？
虚拟内存使用外存上的空间来扩充内存空间，通过一定的换入/换出，使得整个系统在逻辑上能够使用一个远远超出其物理内存大小的内存容量。因为虚拟内存技术调换页面时需要访问外存，会导致平均访存时间增加，若使用了不合适的替换算法，则会大大降低系统性能。 本节学习了4种页面置换算法，要将它们与处理机调度算法区分开。当然，这些调度算法之间也是有联系的，它们都有一个共同点，即通过一定的准则决定资源的分配对象。在处理机调度算法中这些准则比较多，有优先级、响应比、时间片等，而在页面调度算法中就比较简单，即是否被用到过或近段时间内是否经常使用。在操作系统中，几乎每类资源都会有相关的调度算法读者通过将这些调度算法作为线索，可将整个操作系统的课程连成一个整体。