内存扩充 | snowFlakeXue

覆盖与交换是内存扩充的两种方法

覆盖技术

解决程序大小大于物理内存总和的问题，即将程序分为多个段，常用的段常驻在内存，不常用的段在需要的时候调入内存

内存被分为一个固定区和若干个覆盖区，需常驻内存的段放在固定去，调入后不再调出(除非运行结束)，不常用的段放在覆盖区内，需要时调入内存，不需要时调出内存

如下面的栗子

覆盖技术

如图则是按照程序的逻辑将不可能同时被访问的程序段放在一个共享的覆盖区上，在逻辑上看，内存是被扩展了的。但上图程序的逻辑操作系统并不知道，只能由程序员声明覆盖结构

也就是覆盖技术的缺点：对用户不透明，增加了用户编程的负担

覆盖技术只适用于早期的操作系统，已成为历史

交换技术

设计思想：内存空间紧张时，系统将内存中某些进程暂时换到外存，把外存中已经具备运行条件的进程换入内存(进程在内存和磁盘中的调度–中级调度)，注意PCB会常驻内存，不被调出

那么就有了下面的几个问题

应该在外存的哪里保存换出来的进程？

首先要补充一个知识，磁盘存储空间分为对换区和文件区，文件区是存放文件的，主要追求存储空间的利用率，因此对文件空间的管理采用离散分配方式；对换区只占磁盘空间的一小部分，被换出的进程就放在这里，由于对换速度直接影响系统整体速度，所以对换区采用连续分配方式，因而对换区的I/O速度比文件区更快

什么时候进行交换？

在内存紧张时进行，系统负荷降低就暂停

应该换出哪些进程？

阻塞进程；优先级低的进程；有时考虑到有可能因为优先级低一进来就被调出，有的系统还会考虑进程在内存中的驻留时间

虚拟存储技术

我们知道，传统的存储管理再加上覆盖技术或者交换技术就可以实现内存扩充，提高效率。现在再讲一种扩容方法-虚拟存储技术

下面来看看传统的存储管理的缺点

传统的存储管理(连续分配，非连续分配)，很多时候暂时用不到的数据仍会占用内存，导致内存利用率不高。
(一次性)作业又必须一次性全部装入内存才能运行，这就导致两个问题，一个是作业很大时，不能全部装入内存，导致大作业无法运行，第二个问题是，当有大量作业要求运行时，由于内存无法容纳所有作业，因此只有少量作业可以运行，导致多道程序并发度降低。
(驻留性)一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束，事实上，在上一个时间段，只需要访问作业的一小部分数据即可正常运行，这就导致了内存中驻留大量的，暂时用不到的数据，浪费了宝贵的内存资源。

但！虚拟存储可以解决上面的所有问题

还记得之前讲过的两个局部性原理吗？一个是时间局部性，就是某条指令或数据可能会被经常多次刚问(比方说循环)，另一个是空间局部性，就是一块数据他周围的数据很可能被接连访问(比方说数据被连续，顺序存储)

那怎么利用这两个局部性来扩充内存呢？

答案是高速缓冲技术：将近期会频繁访问的数据放到更高速的存储器中，暂时用不到的数据放在更低速存储器中

下面这幅图就是计算机存储器的层次结构，我们可以看到越往上越快，越贵，越小，就比方说之前提到的快表机制，就是将近期经常访问的页表项副本放到更高速的联想寄存器中，这样我们就可以快速的拿到要用的，将其他不常用的用更小的成本存储起来

这样，基于局部性原理，在程序装入时，可以将程序中很快会用到的布恩装入内存，暂时用不到的部分留在外存，就可以让程序开始执行

在程序执行过程中，当所访问的信息不在内存中时，由操作系统负责将所需信息从外存调到内存，然后继续执行程序

当内存空间不够时，由操作系统负责将内存中暂时用不到的信息换到外存

在操作系统的管理下，用户会觉得有一个比实际内存大得多的内存，这就是虚拟内存(这就是操作系统虚拟性的体现，实际的物理内存没有变，只是在逻辑上进行了扩充)

需要注意的是

虚拟内存的最大容量是计算机的地址结构(CPU寻址范围)确定的

虚拟内存的实际容量是min(内存和外存之和，CPU寻址范围)

虚拟内存的三大特征

多次性：无需在作业运行时将作业一次性全部装入内存，而是允许分为多次调入内存
对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入，换出
虚拟性：从逻辑上扩充了内存的容量，远大于实际的容量

那怎么实现虚拟内存技术呢？

因为我们需要允许一个作业多次调入内存，就肯定不能采用连续分配方式，会不方便实现，那虚拟内存的实现就需要建立在离散分配的内存管理方式的基础上，也就有了虚拟内存技术的三种方式

与传统的离散分配有两点区别

在程序执行中，当所需信息不在内存，操作系统需要从外存调进来，也就是说操作系统要提供请求调页(或请求调段功能)
如果内存空间不够，操作系统还要负责将内存中暂时用不到的信息换到外存，也就是说操作系统要有页面置换(或段置换)的功能

请求分页存储管理

页表机制

为了实现请求调页，操作系统需要知道每个页面是否已经调入内存，如果还没有调入，操作系统需要知道页面在外存的什么位置；为了实现页面置换，操作系统需要根据一些指标来判定谁被调出去，有的页面没有被修改过，就不需要再费力把它调回外存，有的页面被修改过，就需要将外存中的旧数据覆盖，因此，操作系统需要记录各个页面是否被修改过

下面是请求分页存储管理的页表与基本分页存储管理的页表的对比

缺页中断机构

在请求分页系统中，每当要访问的信息不在内存中需要去调入时，就会发生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断，这个时候缺页进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列

若果内存中有空闲块，就为该进程分配一个空闲块，将所缺页面装入该快，并修改相应页表中额页表项

若内存中没有空闲块，就要用页面置换算法将一个页面淘汰，若盖爷年在内存期间被修改过，就要写回外存，未修改过的页面不用写会外存

缺页中断是因为当前执行的指令想访问的目标页面未调入内存而产生的，因此属于内中断

一条指令当中可能发生多次缺页中断，比如copy a to b,因为a，b不在一个页面，就可能会发生两次缺页中断

地址变换机构

除上图之外还有几点细节

快表中的页面一定是在内存中，若某个页面被调到外存，快表中的相应表项也要删除，否则可能访问错误的页面

只有写指令才需要修改”修改位”，并且，一般来说只需要修改快表中的数据，只有要将快表项删除时才需要写回内存中的慢表，这样可以减少访存次数

和普通中断处理一样，缺页中断也需要保留CPU现场

需要用某种页面置换算法来决定换出哪个页面

换入换出操作都依赖于I/O操作，因此若换入换出操作太频繁会有很大的开销

页面调入内存后，需要修改慢表，同时也需将表项复制到快表中

页面置换算法

页面的换入换出需要磁盘I/O，会有较大开销，因此好的页面置换算法应该追求更少的缺页率

最佳置换算法：

每次选择淘汰的页面将是以后永不使用或最长时间不被使用的页面，这样可以保证最低的缺页率，拿下面这个例子举例

当要访问页面2时，内存里没有，就发生缺页，这个时候发现内存已经满了，因此要用页面置换算法淘汰一个，若用最佳置换算法，目前内存里有7,1,0这三个页面，看看没页面2后面一次出现0,1,7，因此页面7是最长时间内不被使用的页面，因此淘汰7

当你把这个表完全分析完之后，你会发现，缺页发生了9次，但页面置换只发生了4次，因此却也不一定会发生页面置换，只有在内存中没有空闲块时才会发生页面置换

但是，想使用最佳置换算法就得知道访问页面的顺序，这可想而知，在进程运行时才知道下一步要访问谁，因此最佳置换算法是无法实现的

先进先出置换(FIFO)：

每次选择淘汰的页面是最早进入内存的页面

实现方法：把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面即可，队列的最大长度取决于系统为进程分配了多大内存块

具体过程很简单，就不赘述，但需要注意的是我给进程分了更多的内存块，他的缺页次数却不减反增，这是Belady异常，只有FIFO算法才会产生Belady异常，另外，虽然FIFO算法实现简单，但是该算法与进程实际运行的规律不适应，因为先进入的页面有可能最经常被访问，因此，算法性能差

最近最久未使用置换算法(LRU)：

每次淘汰的是最近最久未使用的页面

实现方法：页表的每一个页表项增添一个”访问字段”，记录该页面自上次被访问以来所经历的时间t，当要淘汰一个页面时，淘汰现有页面t最大的，即最近最久未使用的页面

下面举个栗子来直观感受下这个算法

如图走到箭头位置时，内存给分的内存块都满了，这个时候就要淘汰一个页面，目前内存里有1,8,7,2这四个页面，那根据最近最久，那从3逆向前找，依次找到8,1,2，7,；那7就是最近最久，淘汰7

因为该算法实现需要专门的硬件支持，虽然算法性能很好但实现困难，开销大

时钟置换算法(CLOCK)：

最佳置换算法的性能最好，却无法实现；先进先出置换算法随实现简单但性能差；最近最久未用置换算法性能好，是最接近最佳置换算法的，但实现起来需要硬件支持，算法开销大

时钟置换算法是一种性能和开销均衡的算法，又称最近未使用算法(NRU)

实现方法：为每个页面设置一个访问位

将内存里的页面通过链接指针依次连接成一个循环队列，当某页被访问时，其访问未知为1；当要淘汰页面时，从队头开始，若访问位是0，就将该页换出，若访问位为1，就将它置为0，暂不换出，继续检查下一页面，若第一轮扫描的所有页面都是1，则将这些页面置为0后，进行第二轮扫描时，一定会有访问位为0的页面，因此，时钟置换算法选择淘汰页面最多会经过两轮扫描

要淘汰时，指针开始动，第一次检查在队首，其他看情况而定

淘汰之后，指针才挪到下一位

eg：假设系统为某进程分配了5个内存块，并考虑以下页面引用串：1,3,4,2,5,6,3,4,7

分配了5个内存块，因此访问前五个页面时，只需依次链接成循环队列即可，且每访问一个页面就把该页面的访问位置为1