操作系统总结之虚存

虚拟内存
前一章内存管理介绍了几种技术如分页分段把一个进程分成多个页，分开存放，在PCB中维持一个页表。进程执行的前提是进程的全部页都已经在内存中了。
虚拟内存技术就解决了这个问题，不需要一个进程把全部的页都放在内存才能执行。
动态载入虽然也解决了这个问题，但是需要程序员完成，非常麻烦。
其实我们发现，一个程序包含了很多条件语句还有异常处理等，这些代码肯定要选择执行的。所以全部调入会显得冗余，增加了磁盘到内存的传输时间。并且减少一个进程的空间可以使得内存容纳更多的进程，增加

多道程序的度。
虚拟地址空间就是一个逻辑视图，通过MMU映射到物理地址空间。
稀地址空间：进程的堆和栈之间的空白的虚拟地址空间。
进程虚拟地址空间内容：堆向上伸展，栈向下伸展，代码和数据。中间放共享库。
虚拟内存可以通过共享页将文件或内存共享给多个进程。每个进程都认为库位于自己的虚拟地址空间。
按需调页：一个进程分成多个页，在需要时调入相应的页，也称为懒惰交换。
按需调页对于性能的影响很大，因为会发生页错误，所以尽量减少页错误。
交换是将整个进程看成一个整体，通过交换程序进行交换，而懒惰交换是将一个进程看成多个页，通过调页程序进行交换。 /*pager VS swapper*/
而我们通过有一张页表维护有效-无效位来区分哪些页在内存，哪些页在磁盘。如果在内存且页号有效，则记为v，如果在磁盘上，则为i。
如果访问无效位的页，则通过页错误方式来解决即如果发现要访问的页不在内存，则：
1.终止进程，保存现场，并通知操作系统。
2.寻找空闲帧，如果没找到，用到页面置换技术。
3.将磁盘上的页调度到相应帧中。
4.重新开始指令。
纯粹按需调页：不断页错误，不断将页调入内存。
页错误发生也是有不同代价的，如果在取指时就发生，则只需要重新取指，如果在获得操作数时发生，则需要重新取指，译码，取操作数，代价就大了很多。
但是如果ADD A,B,A A+B->A，当写入A时出错，重新执行这条指令，但是A已经被改变了，所以结果会不对。解决方案是用临时的寄存器保存原来的值。

有效访问时间：（1-p）*内存访问时间+p*页错误时间。 /*考点*/
页错误的具体过程：
1.告知操作系统。
2.保存现场。
3.确定页表的i代表页错误，因为i可能代表页不存在。
4.磁盘读入空闲帧。
5.修改页表和帧表。
6.恢复。
页错误处理时间主要是：
1.处理页错误。
2.读入页。
3.恢复。
磁盘专门有个交换空间，用于交换数据，处理速度要快。可以在交换空间执行按页调度。
写时复制：创建进程的开始可能不需要按需调页，子进程共享父进程的资源和地址空间。当任何一个进程写入时，就为另一个进程创建一个页面副本。fork
分配空闲页当作页面副本也有技巧，可以通过空闲缓冲池，分配时采用按需填零即只在分配之时清零，清除以前内容。

增加多道程序的度数会有“过度分配”的情况，当页错误发生，需要调入页面，但是内存中没有空闲帧，那么必须页置换。页置换是将页错误的时间加倍了，因为要换入和换出。
基本页置换：
按需调页中需要在内存中有一块空闲帧来存放调入的页，如果没有空闲帧，就要发生页置换。
页置换过程：挑一个牺牲帧，并更新帧表和页表。
可以用修改位或脏位降低开销，当修改位被设置，则意味着这个页从磁盘读入后已被修改，那么就需要写回，如果修改位没被修改，则不需写回。
引用串用来评估一个页置换算法的性能：内存引用的页号序列。如1，2，3 表示引用页号1，2，3。
当不考虑内存帧的数量的情况下，只有页的第一次引用发生页错误，但是如果帧的数量限制，则会复杂的多。
1.FIFO页置换：
将内存的页看成是一个FIFO队列，替换的页是最旧的页即最先调入内存的页，加入的页放到队列的尾部。这不是一个好办法，因为最先进入的页可能是一直要用到的页，如果替换的是活动页，则此页会马上又一次页

错误，换回内存。
Belady 异常：页错误数随着内存帧数的增加而增加。
2.最优置换 OPT
不会产生Belady异常，并且页错误率是最低的。因为他替换的是将来最久才被用到的页。
3.LRU置换
选择的页是最近最少使用的页。
对于引用串，如果倒转，LRU置换和OPT置换的页错误率是一样的。
LRU实现需要硬件支持：
1.计数器。每个页帧会附带一个最近使用时间，置换出的页就是时间最小的。
2.栈。栈顶加入页，栈尾写出页。
4.近似LRU置换
因为LRU实现需要许多硬件支持，因此可能只能近似的实现LRU。
通过添加引用位，每当一个页被引用，该为就置1.通过检查该位，可以知道哪些页未被使用。
（1）附加引用位算法。
在一个页的引用位保留8位，初始为0000 0000，第一次被使用，则1000 0000，第二次未被使用，则0100 0000.以此类推。找到这8位化为10进制后最小的页置换。
（2）二次机会算法。
也是在页中保留一个引用位，如果为1，则给予第二次机会，如果为0，则直接置换。
（3）增强型二次机会算法。
将引用位和修改位作为有序对，（0，0）表示未被引用和修改，则说明是最佳的LRU置换页。
5.基于计数的页置换
（1）Least frequently used LFU：保留一个计数器，记录引用次数。缺点是以前一直用，但是现在不用，则仍会留在内存。
解决方法：定期将计数右移一位。
（2）MFU：最常使用页置换，即把计数最大的页换出。
6.页缓冲算法
7.应用程序：不需要提供虚拟内存。
生磁盘：没有文件系统的磁盘。

接下来讲帧分配,帧分配的最小数量是根据计算机体系结构，最大数量是根据物理内存数量。
分配方法：
1.平均分配。
2.比例分配。根据优先级和进程大小。
帧分配和页置换是相关联的。
全局置换：一个进程从任意帧中选择一个置换，不管该帧是否已分配。 缺点是不能控制页错误率。
局部置换：仅从自己的分配帧中置换。

颠簸：频繁调页。
颠簸发生情景：
当CPU使用率降低时，CPU导入更多进程，如果用全局置换，如果一个进程需要很多帧，因此发生页错误会从其他进程中拿一点，而如果其他进程也页错误，则会从其他进程中拿帧，因此进程都到进程的等待调页设备

队列，CPU使用率降低，恶性循环。
采用局部置换也不能防止系统颠簸。因此我们必须要预先就分配足够多的帧。因此引入了局部模型。
局部模型是那些经常使用的帧，因此进程分配的帧一定要大于局部模型的帧大小。
1.工作集合模型：working-set model 。基于局部性。
工作集合窗口：预设△是最近用到的页。对于△的取值很关键。
工作集合：在工作窗口中使用的页的集合。
如果总的可用帧数量为W，进程i的工作集合为WSi，则W-WSi为其余的可用帧，直到<0就不分配。
如果在内存中的进程的工作集合之和大于可用帧数量，则系统颠簸。
2.页错误频率PFF。
预先设定页错误率的上下界。当页错误率大于上界，则为进程分配更多的帧。这样非常直接。
当对于一个新的局部进行按需调页时，页错误率达到波峰。

如果调用open()，需要先找目录，再找文件，因此需要内存访问+磁盘访问。如果将文件I/O作为内存的普通访问，则称为文件的内存映射。
在内存中的文件可以修改就不立即写回。
前面讲到内存映射文件，下面是内存映射I/O，一组内存专门映射到设备寄存器，读取该块地址如同读取设备寄存器。

内核内存的分配与用户进程的分配内存不同，用户进程都是按页分配，但是内核分配需要从空闲内存池中获取，而不是通过空闲帧链表中获取。
1.Buddy系统。
通过对于连续物理页进行二分，以至于能够最小包容内核需求内存即可。如如果内核需求23KB空间，则最小得到的空间为32KB，因为要是2的幂。
优点：快速合并。
缺点：内部碎片。
2.slab分配。
slab是由一个或多个物理页组成。
cache都有一个或多个slab。而一个内核数据结构都有一个cache。
cache存储内核。内核需要空间就直接从cache中获得。
slab三种状态：满，空，部分满。
slab先从部分满的slab中分配，再从空的slab中分配。否则，分配新的slab，并赋给Cache。
slab没有内部碎片而且能够快速分配。因为已经Cache中创建好了空间。