操作系统内存管理之虚拟内存

　1、虚拟内存概念：

　　在前面的讨论我们知道，在计算机操作系统中，我们用户看到的内存和计算机中的实际物理内存是不一样的，我们需要将计算机的逻辑地址一对一的映射到物理内存中，但是我们在实际进程执行过程中，我们会发现，调入内存的一些页我们并不使用，也就是说我们没必要把这些页调入内存，这就是按需调用的概念，那么，这样的话，我们的逻辑地址与物理地址就可以不是一对一的关系了，因此我们提出虚拟内存的概念，此时我们的逻辑地址的空间可以大于物理地址的空间，但是在调入内存的时候，我们的逻辑地址所占的空间不能大于物理地址的空间，这会出错，但是在调入内存之前的逻辑地址空间可以大于物理地址空间。在进程执行过程中，需要执行的时候，调入内存即可。

　　2、虚拟内存技术的实现

　　虚拟内存中，允许将一个作业分多次调入内存。釆用连续分配方式时，会使相当一部分内存空间都处于暂时或“永久”的空闲状态，造成内存资源的严重浪费，而且也无法从逻辑上扩大内存容量。因此，虚拟内存的实现需要建立在离散分配的内存管理方式的基础上。虚拟内存的实现有以下三种方式：

请求分页存储管理。
请求分段存储管理。
请求段页式存储管理。

不管哪种方式，都需要有一定的硬件支持。一般需要的支持有以下几个方面：

一定容量的内存和外存。
页表机制（或段表机制），作为主要的数据结构。
中断机构，当用户程序要访问的部分尚未调入内存，则产生中断。
地址变换机构，逻辑地址到物理地址的变换

　　3、请求分页管理方式实现虚拟内存

　　请求分页系统建立在基本分页系统基础之上，为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能。请求分页是目前最常用的一种实现虚拟存储器的方法。
　　在请求分页系统中，只要求将当前需要的一部分页面装入内存，便可以启动作业运行。在作业执行过程中，当所要访问的页面不在内存时，再通过调页功能将其调入，同时还可以通过置换功能将暂时不用的页面换出到外存上，以便腾出内存空间。
　　为了实现请求分页，系统必须提供一定的硬件支持。除了需要一定容量的内存及外存的计算机系统，还需要有页表机制、缺页中断机构和地址变换机构。

　　3.1、页表机制

　　请求分页系统的页表机制不同于基本分页系统，请求分页系统在一个作业运行之前不要求全部一次性调入内存，因此在作业的运行过程中，必然会出现要访问的页面不在内存的情况，如何发现和处理这种情况是请求分页系统必须解决的两个基本问题。为此，在请求页表项中增加了四个字段。

请求分页系统中的页表项

　增加的四个字段说明如下：

状态位P：用于指示该页是否已调入内存，供程序访问时参考。
访问字段A：用于记录本页在一段时间内被访问的次数，或记录本页最近己有多长时间未被访问，供置换算法换出页面时参考。
修改位M：标识该页在调入内存后是否被修改过。
外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入该页时参考。

　　3.2、缺页中断机构

　　在请求分页系统中，每当所要访问的页面不在内存时，便产生一个缺页中断，请求操作系统将所缺的页调入内存。此时应将缺页的进程阻塞（调页完成唤醒)，如果内存中有空闲块，则分配一个块，将要调入的页装入该块，并修改页表中相应页表项，若此时内存中没有空闲块，则要淘汰某页（若被淘汰页在内存期间被修改过，则要将其写回外存)。

　　缺页中断作为中断同样要经历，诸如保护CPU环境、分析中断原因、转入缺页中断处理程序、恢复CPU环境等几个步骤。但与一般的中断相比，它有以下两个明显的区别：

在指令执行期间产生和处理中断信号，而非一条指令执行完后，属于内部中断。一条指令在执行期间，可能产生多次缺页中断。

　3.3、地址变换机构

　　请求分页系统中的地址变换机构，是在分页系统地址变换机构的基础上，为实现虚拟内存，又增加了某些功能而形成的。

请求分页中的地址变换过程

　　在进行地址变换时，先检索快表：

若找到要访问的页，便修改页表项中的访问位（写指令则还须重置修改位)，然后利用页表项中给出的物理块号和页内地址形成物理地址。
若未找到该页的页表项，应到内存中去查找页表，再对比页表项中的状态位P，看该页是否已调入内存，未调入则产生缺页中断，请求从外存把该页调入内存。

　　4、页面置换算法

　　进程运行时，若其访问的页面不在内存而需将其调入，但内存已无空闲空间时，就需要从内存中调出一页程序或数据，送入磁盘的对换区。

　　选择调出页面的算法就称为页面置换算法。好的页面置换算法应有较低的页面更换频率，也就是说，应将以后不会再访问或者以后较长时间内不会再访问的页面先调出。

常见的置换算法有以下四种。

　　4.1、最佳置换算法(OPT)

　　最佳(Optimal, OPT)置换算法所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率。但由于人们目前无法预知进程在内存下的若千页面中哪个是未来最长时间内不再被访问的，因而该算法无法实现。
　　最佳置换算法可以用来评价其他算法。假定系统为某进程分配了三个物理块，并考虑有以下页面号引用串：
　　 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
　　进程运行时，先将7, 0, 1三个页面依次装入内存。进程要访问页面2时，产生缺页中断，根据最佳置换算法，选择第18次访问才需调入的页面7予以淘汰。然后，访问页面0时，因为已在内存中所以不必产生缺页中断。访问页面3时又会根据最佳置换算法将页面1淘汰……依此类推，如下图所示。从图中可以看出釆用最佳置换算法时的情况。
可以看到，发生缺页中断的次数为9，页面置换的次数为6。

访问页面	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
物理块1	7	7	7	2		2		2			2			2				7
物理块2		0	0	0		0		4			0			0				0
物理块3			1	1		3		3			3			1				1
缺页否	√		√	√		√		√			√			√				√

利用最佳置换算法时的置换图

　　4.2、先进先出(FIFO)页面置换算法

　　优先淘汰最早进入内存的页面，亦即在内存中驻留时间最久的页面。该算法实现简单，只需把调入内存的页面根据先后次序链接成队列，设置一个指针总指向最早的页面。但该算法与进程实际运行时的规律不适应，因为在进程中，有的页面经常被访问。

访问页面	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
物理块1	7	7	7	2		2	2	4	4	4	0			0	0			7	7	7
物理块2		0	0	0		3	3	3	2	2	2			1	1			1	0	0
物理块3			1	1		1	0	0	0	3	3			3	2			2	2	1
缺页否	√	√	√	√		√	√	√	√	√	√			√	√			√	√	√

利用FIFO置换算法时的置换图

　　这里仍用上面的实例，釆用FIFO算法进行页面置换。进程访问页面2时，把最早进入内存的页面7换出。然后访问页面3时，再把2, 0, 1中最先进入内存的页换出。可以看出，利用FIFO算法时进行了 12次页面置换，比最佳置换算法正好多一倍。
　　FIFO算法还会产生当所分配的物理块数增大而页故障数不减反增的异常现象，这是由 Belady于1969年发现，故称为Belady异常，只有FIFO算法可能出现Belady 异常，而LRU和OPT算法永远不会出现Belady异常。

访问页面	1	2	3	4	1	2	5	1	2	3	4	5
物理块1	1	1	1	4	4	4	5			,5'	5
物理块2		2	2	2	1	1	1			3	3
物理块3			3	3	3	2	2			2	4
缺页否	√	√	√	√	√	√	√			√	√
		1	1	1			5	5	5	5	4	4
物理块2*		2	2	2			2	1	1	1	1	5
物理块3*			3	3			3	3	2	2	2	2
物理块4*				4			4	4	4	3	3	3
缺页否	√	√	√				√	√	√	√	√	√

Belady 异常

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

　　选择最近最长时间未访问过的页面予以淘汰，它认为过去一段时间内未访问过的页面，在最近的将来可能也不会被访问。该算法为每个页面设置一个访问字段，来记录页面自上次被访问以来所经历的时间，淘汰页面时选择现有页面中值最大的予以淘汰。
　　再对上面的实例釆用LRU算法进行页面置换，进程第一次对页面2访问时，将最近最久未被访问的页面7置换出去。然后访问页面3时，将最近最久未使用的页面1换出。

访问页面	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
物理块1	7	7	7	2		2		4	4	4	0			1		1		1
物理块2		0	0	0		0		0	0	3	3			3		0		0
物理块3			1	1		3		3	2	2	2			2		2		7
缺页否	√	√	√	√		√		√	√	√	√			√		√		√

LRU页面置换算法时的置换图

　　前5次置换的情况与最佳置换算法相同，但两种算法并无必然联系。实际上，LRU算法根据各页以前的情况，是“向前看”的，而最佳置换算法则根据各页以后的使用情况，是“向后看”的。
LRU性能较好，但需要寄存器和栈的硬件支持。LRU是堆栈类的算法。理论上可以证明，堆栈类算法不可能出现Belady异常。FIFO算法基于队列实现，不是堆栈类算法。

　　5、页面抖动(颠簸)

　　在页面置换过程中的一种最糟糕的情形是，刚刚换出的页面马上又要换入主存，刚刚换入的页面马上就要换出主存，这种频繁的页面调度行为称为抖动，或颠簸。如果一个进程在换页上用的时间多于执行时间，那么这个进程就在颠簸。
　　频繁的发生缺页中断（抖动），其主要原因是某个进程频繁访问的页面数目高于可用的物理页帧数目。虚拟内存技术可以在内存中保留更多的进程以提髙系统效率。在稳定状态，几乎主存的所有空间都被进程块占据，处理机和操作系统可以直接访问到尽可能多的进程。但如果管理不当，处理机的大部分时间都将用于交换块，即请求调入页面的操作，而不是执行进程的指令，这就会大大降低系统效率。