2021-05-14 现代操作系统 《现代操作系统 第4版》第3章 内存管理——总结上

计算机的存储体系 ：内存是计算机很重要的一个资源，因为程序只有被加载到内存中才可以运行；此外，CPU所需要的指令与数据也都是来自内存的。可以说，内存是影响计算机性能的一个很重要的因素。

操作系统内存管理：总的来说，操作系统内存管理包括物理内存管理和虚拟内存管理。
1、物理内存管理：包括程序装入等概念、交换技术、连续分配管理方式和非连续分配管理方式（分页、分段、段页式）。
2、虚拟内存管理：虚拟内存管理包括虚拟内存概念、请求分页管理方式、页面置换算法、页面分配策略、工作集和抖动。

问：在不适用存储器抽象的情况下是否可以运行多个程序：
答：可以。
再问：为什么br> 操作系统只需要把当前内存中所有内容保存到磁盘文件中（交换方式），然后把要运行的程序读入到内存中运行即可(只要在某一个时间内存中也只有一个程序，那么就不会发生冲突)。
再问：还有别的方式吗br> 答：有。 通过硬件，比如（IBM360）：内存划分为内存块（2KB），每个块分配一个“4位的保护键”，存在CPU的特殊寄存器中。每个进程都拥有程序状态字寄存器，其中存放着一个4位码，当进程需要访问相应内存块时，需要让其内存块的保护键和PSW中的4位码有联系才可。（这样就防止了进程间，进程和OS间的互相干扰）。但是缺点就是：虽然两个程序（进程）不会相互影响，但是当他们同时进入内存，他们各自的指令可能会互相调用，而这就是因为他们都用了绝对物理地址，这时我们需要一套私有的本地地址进行内存寻址。
再问：什么叫私有的本地地址进行内存寻址br> 答：通过静态重定位：就是把当前程序（进程）的第一条指令的直接物理地前加上当前在内存中的地址，依此类推，但是会减装载速度，并不是很好。
再加一句：计算世界的发展总是重复历史，虽然现在直接引用物理地址很少见，但是在嵌入式和智能卡中也是很常见的。

无内存抽象带来的问题：
1、用户程序可以访问任意内存，容易破坏操作系统，造成崩溃（可以使用特殊的硬件进行保护比如IBM360）
2、同时运行多个程序特别困难
改进：随着计算机技术发展，要求操作系统支持多进程的需求，所谓多进程，并不需要同时运行这些进程，只要它们都处于 ready 状态，操作系统快速地在它们之间切换，就能达到同时运行的假象。每个进程都需要内存，Context Switch 时，之前内存里的内容怎么办单粗暴的方式就是先 dump 到磁盘上，然后再从磁盘上 restore 之前 dump 的内容（如果有的话），但效果并不好，太慢了！

一种内存抽象：地址空间 ：
问： 为什么要出现这种内存抽象br> 答：因为在无内存抽象中，当多个程序同时处于内存中并互不影响，有两个敌人：保护和重定位。通过硬件保护（IBM360）可以解决第一个敌人“保护”，但是无法解决重定位（静态重定位大大降低了效率）！————-这时！“地址空间”横空出世！
再问：那什么是地址空间呢br> 答：一种新的存储器抽象（被面试官打死）！嗯！想了想：我可不想被挂，那应该是什么呢竟是存储器抽象，当然是为了寻址，那么就是—-一个进程可用于寻址内存的一套地址集合。类比于：进程—创造了一类抽象的CPU以运行程序。
再问:给我举几个地址空间的应用br> 答：比如：端口，IP地址，域名(eg:.com)，电话 码，身份证 码等！
再问：通过什么方法,可以让每个程序有不同的物理地址br> 答：动态重定位，通过给每个CPU配置两个特殊的硬件寄存器，基址寄存器和界限寄存器：当要运行的程序（进程）装载到内存的时候，无法重定位。是因为当一个程序运行时，程序的每个起始物理地址装载到基址寄存器中，程序的长度装载到界限寄存器中。比如当进程访问内存时，需要相应的内存地址，都会自动先加上基址寄存器的内容，然后通过界限寄存器看是否超过这个程序的长度br> 问：那基址寄存器和界限寄存器有什么缺点么br> 答：每次访问内存都需要进行加法和比较运算。

虚拟内存：
问：虚拟内存的由来br> 答：前面的抽象虽然满足了一定的多进程的要求，比如交换技术，但是它需要进程运行的时候需要完整调入到内存，有时候这也是一种缺陷，那么我们进一步改进，这就是覆盖技术。
问：那交换技术的进一步改进是什么br> 答：将一个程序分为多个块，基本思想是先将块0加入内存，块0执行完后，将块1加入内存。依次往复，这个解决方案最大的问题是需要程序员去程序进行分块，这是一个费时费力让人痛苦不堪的过程。后来这个解决方案的修正版就是虚拟内存。
问：那你说说虚拟内存的思想：
答：每个进程有独立的地址空间，内存被分为大小相等的多个块,称为页(Page).每个页都是一段连续的地址。这些页被映射到物理地址内存，但不是所有的页都必须在内存中才能运行程序。当程序引用到一部分 不在物理内存中的地址空间时，由硬件立即执行必要的映射。当映射到一部分不在物理内存中的地址空间时，由OS负责将缺失的部分装入物理内存再次执行刚才的指令。
问：我还是没懂虚拟内存到底用来干嘛的br> 答：虚拟内存是将一个进程独立的整个地址空间用相对较小的单元映射到物理内存（也就是进程的一部分映射到物理内存中）。

那下面我们就讲一讲怎么通过虚拟内存进行离散分配吧！！！！！！

问： 虚拟地址怎么用，MMU是做什么的/strong>
由程序生成的地址称为虚拟地址，它们构成了一个虚拟地址空间。在没有虚拟内存的计算机上，系统直接将虚拟地址送到内存总线上；但是在使用虚拟地址的情况下，虚拟地址不是直接送到内存总线上，而是被送到内存管理单元（MMU），MMU把虚拟地址映射为物理内存地址。

• 页框 ：物理内存的基本单位的索引
• “在/ 不在位”：表示虚拟内存中页面是否映射到了物理地址的页框，如果没有则访问会产生缺页中断。
• 保护位：指出一个页允许访问什么类型，一般有三位，读，写，执行。
• 修改位：写入时由硬件自动设置修改位，有利于OS重新分配页框是非常有用的。如果页面被修改过，也就是修改位有值（变”脏”），那么需要把它写回磁盘。
• 访问位：有利于发生缺页中断时，选择要被淘汰的页面。
• 高速缓存禁止位：当把虚拟内存映射到寄存器中，而不是物理内存，这时就不需要将值先经过缓存，而是直接读取数据（让我想到了volatile）。

问：再说一遍虚拟内存到底干什么的/strong>
答：沉思了一下。虚拟内存就是将虚拟地址空间分解成页，并且将每一个页映射到物理内存的某个页框或（暂时）解除映射。

问： 既然你知道了虚拟内存，以及作用，那你说说我们在运用虚拟内存映射的时候需要注意什么的/strong>
答：我想，应该注意的是，虚拟地址映射到物理地址的时候要非常快，并且如果虚拟地址空间很大，页表也会很大。
再问：那怎么做到映射快呢/strong>
答：我们加速分页过程就好了，但是怎么加呢了想，因为页表我们通常是MMU中，副本一般放在主存中。当启动一个进程时，OS把保存在内存中得进程页表的副本载入到寄存器中（如上图，放在MMU中）。优点：简单且在映射过程中不需要访问内存。缺点：页表很大的时候，代价很大，并且每次上下文切换（上下文切换就是不同线程的调度，也可以是任务的调度）的时候，都需要装载整个页表。（我自己想法：就是每个进程相应的页表都在主存中，当切换进程时，我们把这个内存中页表的副本考入到CPU中的寄存器MMU中就好了，下面的方法是不考入寄存器中，直接在内存中映射。）
再问：还有别的方法加速分页过程吗一般用上面那种）
答：将整个页表都保存在内存中。不过我们需要一个指向页表起始位置的寄存器。这种设计在每次上下文切换时，只需要装载一个寄存器，但缺点就是：在执行每条指令时，都需要一次或者多次进行内存访问来完成页表项的读入，速度慢。

最近最少使用页面置换算法（LRU，Least Recently Used）：选择最近最长时间未访问过的页面予以淘汰，它认为过去一段时间内未访问过的页面，在最近的将来可能也不会被访问。该算法为每个页面设置一个访问字段，来记录页面自上次被访问以来所经历的时间，淘汰页面时选择现有页面中值最大的予以淘汰(虽然可以实现，但是代价太高，因为需要在内存中维护一个所有页面的链表。最近最多使用的在表头，最近最少使用的在表尾，每次访问内存都必须更新整个链表，并且每次排列链表也是很费时的)。

问：那怎么解决这个问题呢/strong>

答：
①、 我们使用特殊的硬件实现LRU，要求硬件有一个64位计数器C，它在每条指令执行完成后自动加1，每个页表项有一个容纳这个计数器值的域，每次访问后，将当前的C值保存到被访问页面的页表项中。一旦缺页中断，OS将检查所有页表项中得计数器的值，找到值最小的一个页面，然后就是最近最少使用的页面。然后还有别的计数方法。
②、如图

问：那怎么如何实现工作集模型呢/strong>
答： OS必须跟踪哪些页面在工作集中，以此确定工作集模型，然后根据工作集模型推出信息置换算法。
问： 通过w(k,t)我们可以发现，通过确定k的值，页面集合也就是工作集就被确定了。那你能告诉我怎么确定工作集么/strong>
答： 向后找最近k次的内存访问（没有被使用过）。设想有一个长度为k次的移位寄存器，每进行一次内存访问就左移一位，然后再最右端插入刚才所访问过的页面 。移位寄存器中的k个页面 的集合就是工作集。理论上，当缺页中断发生时，只要读出移位寄存器中的内容，并排序删除重复页面后，结果就是工作集。然而，维护寄存器并在缺页中断时处理它所需要的开销很大，因此该技术没有被使用过。
问：这种技术不被使用，那用什么技术确定工作集呢/strong>
答：既然不能考虑k，那我们可以考虑t呀，我们定义在过去t秒实际运行时间中它所访问的页面的集合。

工作集页面置换算法：
基本思路是找出一个不在工作集中的页面并淘汰它。在页表中，每个表项至少包含了两条信息：上次使用该页面的近似时间和R(访问)位。其他的域如页框 、保护位、M(修改)位在该算法中不需要，被忽略(用空白域表示)。

• FIFO算法：是通过维护链表来记录它们装入内存的顺序。淘汰最老的页面，虽然该页面仍在使用，但并不是一个好选择。
• 第二次机会算法：是对FIFO的改进，它在移出页面前先检查该页面是否正在被使用，如果没有被使用则放到链表尾部，重新计算
• 时钟算法：是第二次机会算法的改进，不需要放到链表尾部，直接形成环就好了。FIFO->第二次机会算法->时钟算法
• LRU：很优秀的算法，但是一般需要硬件实现。
• NFU：LRU+通过计算器实现，但是计算器虽然能统计访问的次数，但是不能说明在什么时间访问的，如果是很早之前就不好了。
• 老化算法：可以更有效的实现LRU，我认为更是NFU的改进，也是计算访问量，只不过通过右移的方法对不同时间的访问量加了权值，越靠近现在的，权值越大。 LRU->NFU->老化算法
• 最后两种都使用了工作集：工作集算法有合理的性能，但它的实现开销较大，工作集时钟算法是它的变体，不仅具有良好的性能，还能更好实现。
• 总结：老化算法、工作集时钟算法最重要，性能最好！

与分页有关实现问题：
1、 分页相关工作的时间段：进程创建时，调度进程执行时，缺页中断时和程序终止时。
问：进程创建时需要做什么/strong>
答：当进程创建的时候，OS需要根据程序和数据的大小创建页表，然后在内存中为页表分配空间并初始化，只有运行进程的时候，才要求页表在内存中。在磁盘交换空间分配空间，因为当进程不用需要置换出时，需要磁盘有放置此进程的空间，然后程序和数据还要对磁盘交换区初始化，这样发生缺页中断，可以调入回去。因为进程都有进程表，所以页表和磁盘交换区的信息存储在进程表中。
问：调度进程执行时需要做什么/strong>
答： 重置MMU，刷新TLB（说明TLB在MMU中，而页表不一定，大部分在内存）。
问：缺页中断时需要做什么/strong>
答：读硬件寄存器->哪个虚拟地址造成了缺页中断->是哪个页面->磁盘上定位该页面->在内存中找合适的页框，并置换老的页面，然后把所需的页面读入页框->回退到程序计数器使其能重新执行发生缺页中断的指令。
问：进程退出时需要做什么/strong>
答：OS必须释放页表，页面和页面在硬盘上所占用的空间，当然要注意共享页面，是要等所有进程都不需要了，才能释放。

缺页中断处理：
问：麻烦说一说缺页中断发生的细节以及时间顺序
答：
1、（保存信息） 硬件陷入内核，在堆栈中保存程序计数器（为了回退并重新执行引发缺页中断的指令）。大多数机器将当前指令的各种状态信息保存在特殊的CPU寄存器中。
2、（进一步保存信息）启动一个汇编代码例程保存通用寄存器和其他易失的信息，以免被操作系统破坏。这个例程将操作系统作为一个函数来调用。
3、（找引发缺页中断的页面）当操作系统发现一个缺页中断时，尝试发现需要哪个虚拟页面。通常一个硬件寄存器（读硬件寄存器）包含了这一信息，如果没有的话，操作系统必须检索程序计数器，取出这条指令，用软件分析这条指令，看看它在缺页中断时正在做什么。
4、（检查这个虚拟地址是否有效） 一旦知道了发生缺页中断的虚拟地址，操作系统检查这个地址是否有效，并检查存取与保护是否一致。如果不一致，向进程发出一个信 或杀掉该进程。如果地址有效且没有保护错误发生，系统则检查是否有空闲页框。如果没有空闲页框，执行页面置换算法寻找一个页面来淘汰。
5、 （置换老的”脏“的页框时的措施） 如果选择的页框“脏”了，安排该页写回磁盘，并发生一次上下文切换，挂起产生缺页中断的进程，让其他进程运行直至磁盘传输结束。无论如何，该页框被标记为忙，以免因为其他原因而被其他进程占用。
6、（置换老的”脏“的页框刷新到磁盘之后） 一旦页框“干净”后（无论是立刻还是在写回磁盘后），操作系统查找所需页面在磁盘上的地址，通过磁盘操作将其装入。该页面被装入后，产生缺页中断的进程仍然被挂起，并且如果有其他可运行的用户进程，则选择另一个用户进程运行。
7、 （更改页面映射关系） 当磁盘中断发生时，表明该页已经被装入，页表已经更新可以反映它的位置，页框也被标记为正常状态。
8、（回到第一步的前半部分，回退，重新执行引发缺页中断的指令） 恢复发生缺页中断指令以前的状态，程序计数器重新指向这条指令。
9、（因为置换脏的页框，上下文切换，别的进程在运行，所以这时候需要返回引发缺页中断的进程） 调度引发缺页中断的进程，操作系统返回调用它的汇编语言例程。
10、（回到第一步的后半部分作用，不过恢复的是寄存器） 该例程恢复寄存器和其他状态信息。*

指令备份：
当程序访问不在内存中的页面时，将引起页面失效的指令停止并产生OS的陷阱。在OS系统取出所需的页面后，我们需要重新启动引起陷阱的指令，但这并不容易。
解决方案：使用隐藏的内部寄存器复制程序计数器的内容

锁定内存中的页面：
虚拟内存和I/O通过微妙的方式相互作用着。如果分页算法是全局算法，包含I/O缓冲区的页面会有很小的机会（但不是没有）被选中换出内存。
问：那为什么包含I/O缓冲区的页面很少被选中换出内存/strong>
答：（保证正在做I/O操作的页面不会被移出内存。）当一个进程刚刚通过系统调用从文件或其他设备中读取数据到其地址空间中的缓冲区。在等待I/O完成时，该进程被挂起。另一进程被允许进行。但是！如果I/O设备正处在对该页面进行DMA传出的过程中，将这个页面移出会导致部分数据写入它们所属的缓冲区，而部分数据被写入到最新装入的页面。 解决方法就是：锁住正在进行I/O操作的页面。或者在”内核缓冲区“中完成所有I/O操作，再把数据复制到用户页面。