操作系统精髓与设计原理--虚拟内存

概述

        为了更高效的利用处理器和IO设备，需要在内存中运行更多的进程；同时使程序开发时不受内存大小的影响，而解决这两个问题的方法是使用虚拟内存技术。

        通过虚拟内存技术，将本要分配在实内存的进程，可以部分分配到磁盘上，当需要访问时再将其换出到实内存里。使用逻辑地址访问访问，在运行时转为实地址，让使用者感觉使用的是更大的一片内存。而分配在磁盘的存储空间，被称为虚拟内存。

        如果不使用虚拟内存技术，当没有使用覆盖技术时，就必须将进程的所有页存储在内存里；而使用虚拟内存时，可以将当前运行的进行页存储到内存页框里，非运行的进程页存储到磁盘里，在需要时读入到内存（当将一页读入到内存时，就可能将一页写入到内存里）。虚拟存储技术可以和分段、分页的内存管理技术相结合，具体有虚拟分页、虚拟分段等内存分配方式。（关于覆盖技术和交换技术的区别见此）

        支持虚拟内存技术的两个基本方法是分页和分段。对于分页，每个进程化分为相对比较小且大小固定的页，而分段可以使用大小可变的块。还可以把分页和分段组合在一个内存管理方案中。

        由于可以通过逻辑地址访问，同时在运行时转化为实地址，因此虚拟内存技术允许一个进程分布在不连续的内存块里，并且可以随时间的变化而改变，甚至可以运行时不需要将所有的块存储在内存里。

        虚拟内存管理方案要求硬件和软件的支持。硬件支持由处理器提供，包括把虚拟地址动态转换为物理地址，当访问的页或端不在内存时产生一个中断。这类中断触发操作系统中的内存管理软件。

使用非虚存与虚存的分页、分段内存管理技术的对比

操作系统对内存管理支持的相关设计问题

读取策略：

        进程页可以在请求时读取；或者使用预先分页策略，使用的簇的方式一次读取许多页

• 请求分页：只有当访问到某页的一个单元时才将该页取入内存。这个策略并是不最优有的，因为存在下述情况：一个进程第一次启动时，会在一段时间出现大量的缺页中断；当越来越多的页被取入后，局部性原理表明大多数将来访问的页都是最近读取的页。在一段时间后缺页率会逐渐减少，缺页中断的数目会降低。
• 预先分页：读取的页并不是缺页中断请求的页，该策略利用了大多数辅存设备（如磁盘）的特性，这些设备有寻道时间和合理的延迟。如果一个进程的页被连续存储在辅存中，则一次读取许多连续的页比隔一段时间读取一页更有效。如果大多数额外读取的页没有被引用到，则此策略是低效的。当进程第一次启动时，可以使用预先分页策略，在此情况下程序员必须以某种方式指定需要的页；当发生缺页中断是也可以采用预先分页策略，由于这个过程对程序员是不可见得，因而表现的更可取一些，但预先分页的实用工具程序还没有建立。
• 预先分页和交换是不同的：当一个进程被换出内存并且被置于挂起状态时，它的所有驻留页都被换出，当该进程被唤醒时，所有一切在内存的内都被重新置回到内存中。

放置策略：

        决定一个进程块驻留在实存的什么地方。当在纯粹的分段系统中，放置策略并不是重要的设计问题，因为有最佳适配、首次适配等都可以选择。但对于在纯粹的分页系统或段页式的系统，如何放置通常没有关系的，因为地址转换硬件和内存访问硬件可以以相同的效率为任何页框组合执行它们的功能。

        有一个关注放置问题的领域是非一致性存储访问（NonUiform Memory Access，NUMA）多处理器。在非一致性存储访问多处理器之中，机器分布的共享内存可以被该机器的任何处理器访问，但访问某一特定的物理单元所需要的时间随处理器和内存模块之间距离的不同而改变。因此其性能很大程度上依赖于数据驻留的位置与使用此数据的处理器的距离。对于NUMA系统，自动放置策略希望能把也分配到能够提供最佳性能的内存。

置换策略

        用于处理在必须读取一个页时，要置换内存中的哪个页的情况，其目标是移除最近不可能访问的页。由于局部性原理，最近访问历史和最近将要访问的模式间有很大的相关性，因此大多数策略都基于过去的行为来预测将来的行为。

        置换策略有许多使用的算法，要注意的是关于置换策略的一个约束：内存中的某些页框可能是被锁定的，即当前保存在该页框的页就不能被置换。大部分操作系统内核和重要的控制结构就保存在锁定的页框中，同时I/O缓冲区和其他对时间要求严格的区域页框内锁定在内存的页框中。锁定是通过给每个页框关联一个LOCK位实现的，这一位可以包含在页框表和当前页表里。

        基本算法：

• 最佳（OPT）：选择下次访问距当前时间最长的页，此算法导致的缺页率最低，但由于操作系统要知道将来的事件，因此是不可能实现的，属于理想模型，可以作为一个标准来衡量其他算法性能。
• 最近最少使用（LRU）：置换上层使用距当前最远的页。由局部性原理可知，这也是最近最不可访问到的页。而实际上LRU策略接近与OPT，问题在与比较难实现，一种方法是给每一页添加一个最后一次访问时的时间标签，必须在每次访问存储器时，都更新这个标签；另一种方法是维护一个关于访问页的栈，两者的开销大。
• 先进先出（FIFO）：把分配给进程的页框看做是一个循环缓冲区，按循环的方式移动页。所需要的只是一个指针，且让指针在该进程的页框中循环，此策略实现起来非常简单。该此策略所隐含的逻辑是置换驻留在内存中时间最长的页，到现在可能不会再用到，但此推测常常错误，因为经常会有一部分程序或数据在整个程序的生命周期中使用频率都很高的情况，此时该策略会反复地需要被换入换出。
• 时钟：最简单的策略需要给每一页框关联一个附加位，称为使用位。当某一页首次转入内存中时，将该为置1，当被访问到时（产生缺页中断之后），同样被置为1。用于置换的候选页框集合（当前进程或整个内存）被看着一个循环缓冲区，并有一个指针与其相关联。当要一页被置换时，指针被设置为指向缓冲区的下一页框；当要置换一页时，操作系统扫描缓冲区，以查找使用位被置为0的页框。如果扫描是遇到使用位为1的页框时，将其置为0；如果开始时所用页框都为0，则置换遇到的第一个页框；如果所有页框的使用位都为1，则扫描一遍后将所用使用位置为0，并置换刚开始指向的页框。类似与FIFO，不同的是该策略跳过使用位为1的页框。类似的有其他时钟策略的变种，如添加策略位数目的使用（添加一个修改位，如果修改则在写入到辅存前不能被置换到内存；优先将未修改的页框置换出内存，由于没有被修改则不需要写回到辅存里）。

驻留集策略

        对于分页式的虚拟内存，在准备执行时，不需要也不可能把一个进程的所有页都读取到内存。因此操作系统必须决定要读取多少页，即给特定的进程分配多大的内存空间。这要考虑以下因素：

• 分配给一个进程的存储量越小，则任何时候驻留在内存的进程数越多。增加了操作系统至少找到一个就绪进程的可能性，从而减少了由于交换而消耗的处领取时间
• 如果一个进程在内存中的页比较少，虽然有局部性原理，但缺页率任然较高。
• 给特定进程分配的内存超过一定大小后，由于局部性原理，缺页率没有明显变化。

        基于这些因素，操作系统常常使用两种策略：

• 固定分配策略：为一个进程在内存中分配固定数目的页框用于执行时的使用。此数目在最初加载（进程创建）时决定的，根据进程的类型（交互、批处理、应用类）或者基于程序员或系统管理员的需求来确定。一旦缺页中断出现，该进程的一页必须被它所需要的页面置换。
• 可变分配策略：分配给进程的页框在该进程的生命周期中不断发生变化。如果一个进程的缺页率一直高，则该进程的局部性比较弱。应该多分配页框以减少缺页率；如果一个进程的缺页率特别低，则其局部性原理比较强，可以在不会明显增加缺页率的前提下减少分配给它的页框。虽然开上去性能更优，但难点在于要求操作系统评估活动进程的行为，必然需要操作系统的软件开销，同时依赖于处理平台提供的硬件机制。 置换范围有区分：
• 局部置换策略：仅仅在产生此次缺页的进程驻留页中选择置换页。
• 全局置换策略：在内存中所以未被锁定的页作为置换的候选页。

        两种策略的关联： 使用固定分配策略，则意味着使用局部置换策略：为保持驻留集大小固定，从内存中移出的一页必须由同一个进程的另一个页置换。因此有以下三种组合：

清除策略

        与读取策略相反，此策略用于何时将一个被修改过得页写回到辅存。有两种选择：请求式清除和预约式清除。

• 请求式清除：当一页被选择用于置换时才被写回到辅存。缺点是写入一个被修改的页和读入一个新页是成对出现的，并且写出在读入之前。相比预约式清除可以减少写页，但意味着发生缺页中断时，进程在解除阻塞之前必须等待两次页传送，可能降低处理器的利用率。
• 预约式清除：将这些被修改的多个页在需要用到它们所占据的页框之前被成批的写回到辅存。缺点是一个被写回辅存的页可以仍然留在内存中，指定页面置换算法指示它被移出。虽然允许成批写到页，但可能写回的页大部分在置换之前又被修改，因此没有太大意义。辅存的传输能力有限，不应该浪费在实际上不太需要的清除操作上。

        一个比较好的方法是结合页缓冲技术，只清除可以用于置换的页，但去除了清除和置换操作之间的成对关系。被置换的页可以放置在两个表里：修改和未修改。修改表的页可以周期性地被成批写出，并移到未修改表里。未修改表的一页或因为被访问而被回收，或它的页框被分配该另一页时被淘汰。

加载控制

        影响驻留在内存中的进程数目，称作为系统并发度。如果某一时刻进程驻留少，则所有进程同时处于阻塞状态概率较大，因而有许多时间花费在交互上；如果驻留过多，平均驻留集合大小不够用，就会频繁发生缺页中断，从而导致抖动。

        随着系统并发度的增加，刚开始很少出现所以驻留进程都被阻塞的情况，处理器利用率随着增加；当达到某一点，平均驻留集不够使用，缺页率中断数目迅速增加，出现抖动，从而使处理器利用率下降。

        解决这个问题有多种方法：

• 工作集或缺页中断频率算法隐含了加载控制，只有驻留集足够大的进程才允许执行。当为每个活动进程提供需要的驻留集大小时，该策略自动并且动态的确定了活动进程的数目。
• L=S准则：调整系统并发度，使缺页中断之间的平局时间等于一次缺页中断所需要的平均时间，此情况下的处理器的利用率最大。同时有一个类似效果的策略，即将分页设备的利用率保持在50%，此时的处理器的利用率同样最大。
• 时钟页面置换算法：使用全局范围的技术，监视算法中扫描页框的指针循环缓冲区的速度，如果速度低于某个阈值，则表示有以下一种或两种情况：很少发生缺页，因此很少要求指针前进；对每个请求，指针扫描的平局页框数很小，表示有许多驻留页每页被访问到，并且都易置换。此时系统并发度可以安全的增加。相似的，如果指针扫描速度唱一个最大阈值，则表示缺页率高，或者难找到可以置换的页，即表示系统并发度高。

        如果让系统并发度减少，则要让一个或多个进程被挂起（换出），其被挂起（换出）的可能性有以下几种：

• 最低优先级进程：实现调度策略决策，与性能问题无关。
• 缺页中断进程：有可能是缺页中断任务的工作集还没有驻留，因而挂起它对性能影响最小。此外由于阻塞了一个一定要将被阻塞的进程，并且消除了页面置换和I/O操作的开销，所以此选择可以立即收到成效。
• 最后一个被激活的进程：这个进程的工作集可能还没有驻留。
• 驻留集最小的进程：将来再次转入时开销小，但不利于局部性较小的程序。
• 最大空间的进程：这可以在一个过量使用的内存中得到最多的空闲页框，使得不会很快又处于去活状态。
• 具有最大剩余执行窗口的进程：一个进程在被中断或放置在就绪队列末尾之前只运行一定的时间，类似最短处理时间优先的调度原则。