操作系统概念_第九章_虚拟内存
概述
第八章提到的所有内存管理策略都是为了将多道程序同时放入内存，方便调用。但通过这种方式，进程执行前整个进程都必须放入内存中。
动态载入可能会减轻这一限制，但这需要程序员小心的做一些额外的工作。
实际情况下，在很多情况下，进程不需要完全放入内存中。例如：
- 处理异常部分的错误代码。一个成型的项目，错误会很少发生，因此这部分代码几乎不执行。
- 数组和链表通常占用了更多的空间，即声明的空间没有得到完全的利用
- 程序的某些功能被使用的频率很少。
因此，出现了虚拟内存技术，它允许执行进程不必完全在内存中，这种方案有以下优点：
- 能够实现程序比物理内存大，用户可以为一个更大的虚拟地址空间编写程序。
- 每个用户使用了更少的物理内存，让更多的进程得到了执行。这样CPU使用率也能够上升，但响应时间和周转时间并不增加（ ？）
- 载入或交换每个用户程序到内存所需要的IO会更少，用户程序会运行的更快（ ？）
虚拟内存实现了逻辑地址和物理地址分开，同时也使文件和内存能够通过共享而被多个进程使用。这种方式有以下优点
- 共享对象可以映射到虚拟地址空间。如系统库可以以只读的形式被多个程序共享。
- 进程共享内存能够让进程间可以通过使用共享内存进行通信。
- 系统调用
fork()期间能够使用共享页，从而加快了进程创建。
按需调页
按需调页（demand paging）是实现虚拟内存的一种方式，即在需要时才调入相应的页（在这之前都是在进程装载时将整个程序载入内存）
使用该方案时，进程驻留在第二级存储器上（通常为磁盘），并采用懒惰交换（lazy swapper）方式，即不将整个程序载入，而是只有在需要页时才将其调入内存。
通过这种操作，调页程序避免了读入不使用的页、减少了交换时间和所需的物理空间。
进程是一系列的页，按需调页中，调页程序（pager）是对进程的单个页进行操作。而之前提到的交换程序（swapper）是对整个进程进行操作，两者概念不同。
硬件支持
硬件需要区分哪些页在内存中，哪些在磁盘中。因此可以使用之前提过的“有效-无效位”技术：
- 有效表示相关的页合法，并且在内存中
- 无效表示相关的页无效，（不在进程的逻辑地址空间中，或者是有效但是在磁盘中）
另一方面，支持按需调页的硬件与分页和交换的硬件一样：
- 支持有效-无效位标记的页表。
- 次级存储器，通常为快速磁盘，用于交换的部分称为交换空间（Swap space），在第12章讨论。
页错误中断
如上所述的有效-无效实现，如果访问有效位则不会有任何问题，如果访问无效位，则会产生错误，这个时候，则通过页错误中断（page-fault trap）来处理：
- 检查进程的内部页表（通常与PCB一起保存），以确定该引用是否是合法的地址访问。
- 如果引用非法，则终止进程
- 如果合法，则：
- 找到一个空闲帧（如从空闲帧链表中选一个）
- 调度一个磁盘操作，将所需要的页调入刚分配的帧
- 磁盘读操作完成后，修改进程内部页表和页表，表示该页已在内存中。
- 重新开始中断前的指令。
从理论上讲，当一个指令访问多个内存，并产生多个页错误的时候，会严重的影响性能，但从实际应用上来看，这种情况极为少见。这是程序的局部引用（locality of reference）特性，这保证了按需调页的性能。
纯粹按需调页（pure demand paging）是只有出现中断的时候才开始调页，这样一开始所有的页都不在内存中，这样进程执行过程中会不断出现页错误直到所有需要的页都在内存中。
一部分详情查看P276
性能分析
内存的有效访问时间（effective access time）的计算：
其中，内存访问时间用ma表示，页错误概率用P表示 ，则 有效访问时间 = (1-P)×ma+P×页错误时间
关于页错误发生的多余的操作，查看P277
写时复制
写时复制是指在进程进行复制的时候，一开始共享同一页面，只有当其中一个进程对某页面要进行写操作的时候，才创建一个该页的副本。
这个时候不能修改的页（如可执行代码的页）就可以一直被父进程和子进程共享。
页面置换
多道程序是让多个程序同时装入内存，这有可能导致过度分配（over-allocating），这将可能导致：一个进程发生页错误的时候，内存中没有可用空间。
因此需要采用页置换算法，来替换新页到旧页上来使进程继续执行下去。
基本页置换方式
查找当前没有使用的帧，将其内容写到交换空间，并改变页表（和所有其他表）以表示该页不在内存中，这个时候就有了空闲帧。
注意这个时候需要采用两次页传输（一个换出，一个换入），这就增加了页错误处理时间，也就增加了有效访问时间。
修改位和脏位可以用来提高性能:P282
页置换算法
页置换算法可以通过一串随机生成或者记录下来的内存引用序列来评估，这一序列叫做引用串（reference string）。为了简化，一般只考虑页码，且序列中连续的两个页码不会重复。
以如下引用串为例讨论页置换算法（设可用帧数量为3）：
7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1页码不会重复的原因以及引用串如何简化等详情参照P283.
FIFO页置换
最简单的页置换算法，选择最旧的页进行置换，即先进先出。
具体方式：创建一个FIFO队列来管理内存中的所有页，队列中的首页被置换，而新调入的页则加到队列的尾部。
FIFO算法容易理解和实现，但性能不总是很好：所替代的页可能仍在使用，换出去以后马上报页错误，要求换回来。
另外，FIFO算法还会产生belady异常
最优置换
最优页置换算法（optimal page-replacement algorithm）是所有算法中错误率最低的，它置换最长时间不会使用的页。
这个算法也叫OPT或MIN，另外注意条件：最长时间不会使用。也就是这个算法还需要知道页”未来”的信息
最优方法虽然最优，但是难以实现，因此该算法主要用于研究和对比其他算法的优劣，科科
LRU页置换
最近最少使用算法（least-recently-used algorithm，LRU）是对OPT的一种近似，其同样没有belady异常，而且是可实现的，当必须置换一页的时候，LRU置换选择最长时间没有使用的页。
其实现需要一些硬件支持，如计数器和栈，不然同样是难以实现的，具体详情参考P287
近似LRU页置换
如上文所说，LRU页置换算法需要硬件支持，所以不是所有系统都支持该算法，但可以通过引用位的设置来提供一个支持。
引用位：与页表内的每项都相关联。每当引用（即对一个页进行读或写操作时），该引用位会被硬件置 “1”。
通过检查引用位，就可以知道哪些页能使用过，哪些页没有使用过。
引用位是大多实现近似LRU页置换算法的基础
附加引用位算法
为位于内存内的每个表中的页保留一个8位的字节。每间隔一个周期（如100ms），就将当前的8个字节右移，并将引用位置最高位。
很显然，00000000表示在最近的八个周期，该页都没有被使用，11111111表示最近的八个周期一直在使用，而10000000表示在最近的一个周期里该页被使用。
另外，附加引用位（也叫做历史位）不一定是8位，可以根据机器自行决定。
二次机会算法
当附加引用位为0位，即只有引用位本身时，这种近似LRU算法被称为二次机会置换算法（second-chance page-replacement algorithm）
该算法基于FIFO算法，当要选择一个页时，检查其引用位，如果其引用位为0，则替换；如果为1，则将其引用位置0，并选择下一个FIFO页（即给了该页第二次机会）
其一种实现方法参考P288
增强型二次机会算法
历史位仍然为0位，但增加了一个修改位（如果页被修改了，那么在置换时需要将页写入磁盘才能置换），因此（引用位，修改位）作为一个有序对来参与算法，共有四种情况：
- (0,0)：最近没有使用也没有修改-置换的最佳选择
- (0,1)：最近没有使用但有修改-不是最佳选择，因为置换前需要写IO
- (1,0)：最近使用过但没有修改-不是最佳，因为很可能会被再次使用
- (1,1)：最近使用过也被修改过-可能会被再次使用，且置换需要提前写IO
这种算法的一个优点是：将修改过的页给予*别，从而减少了IO操作
基于计数的页置换
最不经常使用页置换算法
替换掉页使用次数少的页，另外计数器按一定时间间隔右移，形成指数型衰减
计数器右移是为了避免有一些页一开始使用次数过多但之后不再使用但一直保留的情况。
最常使用页置换算法
这种算法是为了避免刚刚进来的页还未使用即被替换的情况
页缓冲算法
P290,这里不太明白，先空着[TODO]
Belady异常
一个想当然的情况是随着帧增加，页错误率会下降，但实际情况并不是这样。
考虑使用FIFO算法和如下引用串：
1，2，3，4，1，2，5，1，2，3，4，5其出错次数如下所示：
帧分配
如何为进程分配足够的内存，保证所有的进程都能顺利执行，这需要考虑很多因素
帧的最少数量
初次给每个进程分配的帧的数量越少，页错误就会越多。另外，当指令完成前发生页错误时，指令必须重新执行。因此，必须有足够的帧来容纳单个指令所引用的页。
由于指令的不同，每个进程帧分配的最少数量是由其体系结构决定的，而最大数量是由物理内存决定的，为进程分配多少的帧，则是由帧分配算法决定的。
平均分配与比例分配
根据进程数量和帧总数取平均值，叫做平均分配。
平均分配在大多数情况下肯定是不合适的，因此有了比例分配（proportional allocation）根据所有进程的大小，按比例进行空闲帧的分配。
采用平均分配和比例分配，分配的帧的多少与进程的优先级无关，这显然在大多数情况下也是不合适的。另一个方案就是通过进程优先级来实现比例分配的算法。
全局分配与局部分配
- 全局置换（global replacement）：一个进程可以从所有帧集合中选择一个置换帧（不管这个帧是否是别的进程的）
- 局部置换（local replacement）：一个进程仅从自己的分配帧中进行选择
基于这两种置换方式，可以来考虑具体的分配方案了：
- 允许高优先级进程从低优先级进程中选择帧来分配
- …
局部置换不能使用其他进程不常用的内存，所以有可能阻碍一个进程；全局置换通常有更好的系统吞吐率，更为常用。
全局置换算法的一个问题是进程无法控制其页错误率，因为多个进程互相影响，一个进程的位于内存的页集合不仅取决于进程本身的调页行为，还取决于其他进程的调页行为，所以环境不同，一个进程的执行时间会有所不同。
系统颠簸
如果一个进程在换页上用的时间多于执行时间，那么这个进程就在颠簸（thrashing），颠簸其实就是频繁的页调度行为。
系统颠簸的原因
如果一个进程没有分配到足够的页，那么就会导致页置换不断的发生，这将导致：
- 低CPU利用率
- 低CPU利用率导致系统认为需要引入新进程，增加多道程序的程度。
- 进程分配到的帧会更少
- …死循环
这种死循环到达一定程度后，最终会导致颠簸的发生。
采用局部置换算法或优先置换算法（priority replacement algorithm）能够限制系统颠簸的发生。具体参考P295
工作集合模型
工作集合策略定义了进程执行的局部模型（locality model）。
当一个子程序被调用时，它就定义了一个新局部。在这个局部里，内存引用包括该子程序的指令、其局部变量和全局变量的子集。子程序退出时，因为该子程序的局部变量和指令不再使用，进程离开该局部。
工作集合模型基于局部性假设。模型使用参数△定义工作集合窗口（working-set window），其思想是检查最近△个页的引用，这最近△个页的引用就称为工作集合（working set）
上图为
△=10，△为10个内存引用，t1和t2时的工作集合WS(t)如图所示。
如果一个页正在使用，那么它就在工作集中；如果它不再使用，那么它就会在其上次引用的△个时间单位后从工作集合中删除。
因此工作集合可以看做是局部的近似。
工作集合的精度：
- 如果
△太小，那么它不能包含整个局部 - 如果
△太大，则会包含多个局部
工作集合的大小：
工作集合中最为重要的属性是其大小，如果经计算而得到系统内每个进程的工作结合为WSSi那么：
D = ∑ WSSi
//其中D为总的帧需求量。如果总的帧需求量大于可用帧的数量，那么有的进程就会得不到足够的帧，就会出现颠簸。
正确选择工作集的大小，对存储器的利用率和系统吞吐量的提嵩，都将产生重要影响。
工作集合模型的使用：
确认了△之后，操作系统跟踪每个进程的工作集合，并为进程分配大于其工作集合的帧数。随后会出现两种情况：
- 如果还有空闲帧，那么就启动另一个进程。
- 如果所有工作集合之和的增加超过了可用帧的总数，那么操作系统就暂停一个进程。该进程的页被写出，随后被分配给其他进程。挂起的进程稍后可以重新启动。
工作集合的缺点：
- 跟踪工作集合困难。工作集合窗口是移动窗口，每次移动时，会增加新引用，而老的引用会失去。
通过固定定时中断和引用位，能够近似模拟工作集合模型。
具体参考P297
对工作集模型的一个简要的解释
工作集（或驻留集）是指在某段时间间隔内，进程要访问的页面集合。经常被使用的页面需要在工作集中，而长期不被使用的页面要从工作集中被丢弃。为了防止系统出现抖动现象，需要选择合适的工作集大小。
工作集模型的原理是：让操作系统跟踪每个进程的工作集，并为进程分配大于其工作集的物理块。如果还有空闲物理块，则可以再调一个进程到内存以增加多道程序数。如果所有工作集之和增加以至于超过了可用物理块的总数，那么操作系统会暂停一个进程，将其页面调出并且将其物理块分配给其他进程，防止出现抖动现象。
页错误频率
工作集合模型是有效的，且能用于预先调页，但用于控制颠簸不是很灵活，一种更直接的方式是采用页错误频率（page-fault frequency）策略
为一个进程期望的页错误率设置上限和下限，如果页错误率太高，说明可能需要多分配帧；如果页错误率太低，说明分配的帧可能太多，可以从该进程中移走帧。
内存映射文件
文件的内存映射（memory-mapping）允许一部分虚拟内存与文件逻辑相关联。这样的结果是能够通过虚拟内存技术来将文件IO作为普通内存来访问。
利用虚拟内存技术将文件I/O作为普通内存访问的方法叫做文件的内存映射
基本机制
文件的内存映射可将一磁盘块映射成内存的一页。开始的页面访问按照普通页面请求调度进行，会产生页错误，从而一页大小的部分文件从文件系统读入物理页，随后的文件读写操作就按正常的内存操作进行。
对于映射到内存的文件进行读写操作可能不会及时的更新到磁盘的文件当中。更新文件的操作通常由两种方式：
一、通过定期检查内存映射页是否改变来判断是否应该写磁盘
二、在关闭文件的时候将内存映射页写回磁盘，并从进程的虚拟内存中删除。
有的系统仅通过特殊的系统调用提供内存映射，其他文件IO通过标准的系统调用处理。
内存映射实现的共享内存
多个进程可以将一个文件映射到各自的虚拟内存中，以允许数据共享。
如上图，每个进程的虚拟内存表都指向物理内存的同一页，该页有磁盘块的复制。
另外写时复制，互斥等机制也同样可以在其中实现。
实例：Solaris
- 如果一个文件说明为内存映射，那么Solaris将该文件映射到进程的地址空间中。
- 如果一个文件采用普通的系统调用如
read()，open()，Solaris仍然使用内存映射，不过是将文件映射到内核地址空间。
实例：win32 API
- 首先为要映射的文件创建一个文件映射
- 然后在进程的虚拟地址空间中确立一个映射文件的视图
- 另一个进程同样可以在它的虚拟地址空间中打开和创建映射文件的视图
映射文件代表了共享内存对象，从而可以实现进程间的通信。
内核内存的分配
内核内存的分配与普通用户（从进程空闲链表中获取）不同：
- 内核分配内存时，有时需要的空间不到一页。因此，需要谨慎的分配内存，减少浪费。
- 有些硬件需要直接和物理内存交互，因此需要分配连续的物理页
buddy 系统
buddy系统是从物理上连续的大小固定的段上进行分配。每次分配的内存按2的幂次进行分配（2KB、4KB…），如果请求不为2的幂，那么就按下一个2的幂次来分配（如果请求11KB，则分配16KB）。
其分配是从最大的段开始尝试分配
- 如果满足要求，那么段平均分为两部分，取其中一半继续开始尝试分配
- 如果不满足要求，那么就取上一次满足尝试分配的大小分配。
优点：
- 可通过合并快速的形成更大的段
缺点：
- 容易产生碎片（如33KB的需求需要64KB才能满足）
slab分配
slab提出的原因：由于操作系统在运行中会不断产生、使用、释放大量重复的对象，所以对这样的重复对象的生成进行改进可以大大提高效率
简单解释
slab是Linux操作系统的一种内存分配机制。其工作是针对一些经常分配并释放的对象，如进程描述符等。
这些对象的大小一般比较小，如果直接采用buddy系统来进行分配和释放，不仅会造成大量的内存碎片，而且处理速度也太慢。
slab分配器是基于对象进行管理的，相同类型的对象归为一类(如进程描述符就是一类)。
每当要申请这样一个对象，slab分配器就从一个slab列表中分配一个这样大小的单元出去。
当要释放时，将其重新保存在该列表中，而不是直接返回给buddy系统，从而避免这些内碎片。
slab分配器并不丢弃已分配的对象，而是释放并把它们保存在内存中。当以后又要请求新的对象时，就可以从内存直接获取而不用重复初始化。
具体实现
- slab由一个或多个物理上的页组成
- 高速缓存（cache）含有一个或多个slab
- 每个内核数据结构含有一个cache，如进程描述符，文件对象，信号量等。
- 每个cache含有内核数据结构的对象实例
- 当cache被创建时，将所有的对象标记为空闲（free）
- 当需要内核数据结构的对象时，可以从cache上直接获取，并将该对象标记为使用（used）
slab有三种状态：
- 满的： slab中所有对象被标记为使用
- 空的： slab中所有对象被标记为空闲
- 部分： slab中部分对象被标记为使用
分配过程：
- slab分配器首先从部分空闲的slab进行分配
- 如没有部分空闲的slab，则从空的slab进行分配
- 如没有空的slab，则从物理连续页上分配新的slab，并将该slab赋给一个cache，再重复上述过程。
优点：
- 没有因碎片引起的内存浪费
- 内存请求可以快速满足
其他考虑
预调页
纯按需调页的一个显著特性是当一个进程开始的时候会出现大量页错误，这是由于试图将最初局部调入到内存的结果。
预调页的目的是阻止这种大量的初始调页，其策略为：同时将所需要的所有页一起调入内存中。
目测有计算题，参考P306
页大小
页面大小通常为2的幂，在选择页大小时候，有以下因素需要考虑：
- 页表大小，因为每个活动进程必须要有自己的页表，所以较大的页是比较理想的。
- 如何更好的利用内存，为了减少碎片，需要小的页
- 页读写所需要的时间，寻道和延迟时间远远超过运输时间，因此加倍页的大小将导致时间开销更大，因此需要较大的页。
- 还有很多因素需要考虑，如页大小与调页设备的扇区大小的关系，页错误率等
总体来说，是趋向更大的页。
TLB范围
[TODO],P308