【简记】Operating System—— virtual memory
This memo is based on the course of Dr.Li with Operating System as the reference book.
本章内容：
- 虚拟内存的概念
- 按需调页
- 页置换
- 帧分配
- 系统抖动
9.1 背景
研究实际程序会发现，在许多情况下并不需要将整个程序放到内存中：
- 程序通常有处理异常错误条件的代码。由于这些错误即使有也是很少发生，所以这种代码几乎不执行。
- 数组、链表和表通常分配了比实际所需要的更多的内存。
- 程序的某些选项或功能可能很少使用。
能够执行只有部分在内存中的程序可带来很多好处：
- 程序不再受现有的物理内存空间限制
- 因为每个用户程序使用了更少的物理内存，所以更多的程序可以同时执行， CPU 使用率也相应增加，而响应时间或周转时间并不增加
- 由于载入或交换每个用户程序到内存内所需的I/O会更少，用户程序会运行得更快。
（所以当我们在操作系统中增加虚拟内存的值时，也就意味着利用硬盘的空间，存储了程序运行时所需的部分“资料”，当虚拟内存更大时，也就意味着可以将更多的程序放入硬盘中，等需要时再调用，减轻了物理内存的压力）
虚拟内存也允许文件和内存通过共享页而为两个或多个进程所共享。
(1)状态位P用于指示该页是否已调入内存，供程序访问时参考。
(2)访问字段A用于记录本页在一段时间被访问的次数，或最近多长时间未被访问，供置换算法选择换出页面时参考。
(3)修改位M表示该页在调入内存后是否被修改过。由于内存的每一页在外存都有备份，所以在该页被换出时，若该页被修改过，则必须将该页写回外存;若未被修改过，则直接进行覆盖，无须写回。
(4)外存地址用于指出该页在外存上的地址，通常是物理块号，供调入该页时使用。
虚拟存储器的定义：具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。
特征：
1. 多次性：一个作业中的程序可以不用一次性的装入内存，允许被多次装入内存。
2. 对换性：允许作业在运行过程中可以进行换入和换出，无须在作业运行时一直常驻于内存中。
3. 虚拟性: 虚拟性指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。
虚拟性以多次性和对换性为基础。
请求分页系统是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页式虚拟存储系统。为了实现请求调页和置换功能，系统必须提供必要的硬件支持。
其中，最重要的是：（1）请求分页的页表机制。（2）缺页中断机构（3）地址变换机构
9.2 按需调页
现在当该位设置为”有效”时， 该值表示相关的页既合法且也在内存中。 当该位设置为”无效”时，该值表示相关的页为无效〈也就是，不在进程的逻辑地址空间内)，或者有效但是在磁盘上。
当进程试图访问那些尚未调入到内存的页时：（③、④、⑤是操作系统在做）
①检查进程的内部页表(通常与PCB 一起保存)，以确定该引用是合法还是非法的地址访问。
②如果引用非法，那么终止进程。如果引用有效但是尚未调入页面， 那么现在应调入。
③找到一个空闲帧（例如，从空闲帧链表中选取一个）。
④调度一个磁盘操作，以便将所需要的页调入刚分配的帧。
⑤当磁盘读操作完成后， 修改进程的内部表和页表，以表示该页已在内存中。
⑥重新开始因陷阱而中断的指令。进程现在能访问所需的页，就好像它似乎总在内存中(虚拟内存的精髓）
===
9.2.2 按需调页的性能
9.3 写时复制
写时复制( copy-on-write ) 的技术。这种方法允许父进程与子进程开始时共享同一页面。这些页面标记为写时复制页， 即如果任何一个进程需要对页进行写操作，那么就创建一个共享页的副本。
9.4 页面置换
9.4.1 基本页置换
①查找所需页在磁盘上的位置。
②查找一个空闲帧:
a. 如果有空闲帧，那么就使用它。
b. 如果没有空闲帧，那么就使用页置换算法以选择一个”牺牲”帧( victim frame) 。
c. 将”牺牲”帧的内容写到磁盘上，改变页表和帧表。
③将所需页读入(新)空闲帧，改变页表和帧表。
④重启用户进程。
分析页面置换算法：追求最低的缺页率。
通常，增加物理内存就会增加帧的数量。随着帧数量的增加， 页错误数量会降低至最小值。
===
9.4.2 FIFO页置换
FIFO 页置换算法为每个页记录着该页调入内存的时间。当必须置换一页时，将选择最旧的页。可以创建一个FIFO 队列来管理内存中的所有页。
其性能并不总是很好。所替代的页可能是很久以前使用的、现己不再使用的初始化模块。另一方面，所替代的页可能包含一个以前初始化的并且不断使用的常用变量。
Belady异常( Belady’s anomaly ) :对有的页置换算法，页错误率可能会随着所分配的帧数的增加而增加。
===
9.4.3 最优置换（作为比较基准）
最优页置换算法是所有算法中产生页错误率最低的， 且绝没有Belady 异常的问题。
这种算法会置换今后最长时间不会使用的页，称为最优置换（OPT）
最优算法主要用于比较研究。作为基准值。实际无法实现。
===
9.4.4 LRU页置换（没有次数概念，是以时间为标准衡量）
LRU 置换为每个页关联该页上次使用的时间。当必须置换一页时， LRU 选择最长时间没有被使用的页。
实现：
- 每次内存引用时， 时钟寄存器的内容会被复制到相应页所对应页表项的使用时间域内。用这种方式就得到每页的最近引用时间。
- 栈，每当引用一个页， 该页就从栈中删除并放在顶部。这样，栈顶部总是最近使用的页，栈底部总是LRU页。由于必须从栈中部删除项，所以该栈可实现为具有头指针和尾指针的双向链表。
===
9.4.5 近似LRU页置换
很少有计算机系统能提供足够的硬件来支持真正的LRU页置换。
许多系统都通过引用位方式提供一定的支持。页表内的每项都关联着一个引用位（ reference bit ) 。每当引用一个页时(无论是对页的字节进行读或写) ，相应页表的引用位就被硬件置位。
二次机会算法
二次机会置换的基本算法是FIFO 置换算法。当要选择一个页时， 检查其引用位，如果其值为0，那么就直接置换该页。如果引用位为1，那么就给该页第二次机会（但会把引用为置0），并选择下一个FIFO页。
一种实现二次机会算法〈有时称为时钟算法〉的方法是采用循环队列。用一个指针表示下次要置换哪一页。当需要一个帧时，指针向前移动直到找到一个引用位为0 的页，在向前移动时， 它将清除引用位(见图9. 17 ) 。一旦找到牺牲页， 就置换该页， 新页就插入
到循环队列的该位置。注意: 在最坏情况下，所有位均已设置，指针会遍历整个循环队列，以便给每个页第二次机会。它将清除所有引用位后再选择页来置换。这样，如果所有位均已设置，那么二次机会置换就变成了FIFO置换。
http://blog.****.net/u012432778/article/details/46519709（clock算法）
===
9.4.6 基于计数的页置换
可以为每个页保留一千用于记录其引用次数的计数器，并可形成如下两个方案：
- 最不经常使用页置换算法
- 最常使用页置换算法
9.5 帧分配
9.5.1 帧的最少数量
进程帧的最小数量是6个帧。
===
9.5.2 分配算法
- 平均分配
- 比例分配 。根据进程大小，而将可用内存分配给每个进程。
9.5.3 全局分配与局部分配
为各个进程分配帧的另一个重要因素是页置换。当有多个进程竞争帧时，可将页置换算法分为两大类：全局置换( global replacement) 和局部置换（local replacement ) 。全局置换允许一个进程从所有帧集合中选择一个置换帧， 而不管该帧是否己分配给其他进程，即一个进程可以从另一个进程中拿到帧。局部置换要求每个进程仅从其自己的分配帧中进行选择。
基于这些因素，现代操作系统通常釆用三种策略：
固定分配局部置换。它为每个进程分配一定数目的物理块，在整个运行期间都不改变。若进程在运行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面。实现这种策略难以确定为每个进程应分配的物理块数目：太少会频繁出现缺页中断，太多又会使CPU和其他资源利用率下降。
可变分配全局置换。这是最易于实现的物理块分配和置换策略，为系统中的每个进程分配一定数目的物理块,操作系统自身也保持一个空闲物理块队列。当某进程发生缺页时，系统从空闲物理块队列中取出一个物理块分配给该进程，并将欲调入的页装入其中。
可变分配局部置换。它为每个进程分配一定数目的物理块，当某进程发生缺页时，只允许从该进程所在内存的页面中选出一页换出，这样就不会影响其他进程的运行。如果进程在运行中频繁地缺页，系统再为该进程分配若干物理块，直至该进程缺页率趋于适当程度； 反之，若进程在运行中缺页率特别低，则可适当减少分配给该进程的物理块。
9.6 系统颠簸
当进程没能拥有足够的页帧，会导致很高的缺页次数。这时，必须置换某个页。
这种频繁的页调度行为称为颠簸( thrashing ). 如果一个进程在换页上用的时间要多于执行时间，那么这个进程就在颠簸。
9.6.1 系统颠簸的原因
通过局部置换算法（或优先置换算法）能限制系统颠簸。
因为局部模型说明，当进程执行时，它从一个局部移向另一个局部。
假设为每个进程都分配了可以满足其当前局部的帧。该进程在其局部内会出现页错误，直到所有页均在内存中；接着它不再会出现页错误直到它改变局部为止。如果分配的帧数少于现有局部的大小，那么进程会颠簸，这是因为它不能将所有经常使用的页放在内存中。
===
9.6.2 工作集合模型
http://blog.****.net/u011240016/article/details/53314170
⑵把工作集算法融入到处理机调度中
在调度中融入了工作集算法，则在调度程序从外存调入作业之前必须先检查每个进程在内存的驻留页面（驻留集也称为工作集）是否足够多。