第七章、换入换出用磁盘和时间来换取一个规整的虚拟内存
一、引言
我们知道，物理内存是和虚拟与内存建立关联的，只有建立关联以后，存放在“虚拟内存”中的物品才会真正的被存放在物理内存中。这个关联的建立会带来一个问题，一块虚拟内存区域映射到一块物理内存区域，这就要求物理内存和虚拟内存的大小是相同的，这样才能确保正确的关联，但是往往这是不实际的，在32位系统中的虚拟内存大小为2^32=4GB,64位系统的虚拟内存大小位16GB，目前的电脑似乎都能拥有这样的物理内存，但对于以前的只有1GB或者3GB的电脑来说，这样的虚拟内存显然是过大了，那应该怎么办才可以时虚拟内存中的每个虚拟页面都正确映射到物理页框中呢？
二、虚拟内存的换入
1.换入/换出概述
通过虚拟页面的换入/换处机制呢，就实现了每个虚拟内存中的页面都能正确的映射到物理内存当中，具体是什么意思呢？当物理内存中为空时，当然虚拟页面可以直接建立映射，但是当物理内存中不足以映射一个虚拟页面时，就需要将一个最近时间内最少用到的程序（其实应该是程序的一部分）换出物理内存，腾出空间来再将虚拟页面换入。
2.换入的具体实现
（1）内存换入的核心
内存换入的核心是，缺少虚拟页时请求调页，操作系统实现换入就是实现请求调页。
（2）请求调页的过程概述
首先当MMU发现虚拟页面在页表项的有效位为0时开始，这个时候MMU会向CPU发出缺页中断，缺页中断的调用号为14。操作系统在缺页中断后，会从虚拟内存中查找相应的虚拟页面，并将这个虚拟页面换入物理页框中，再更新页表记录下这个映射关系。映射关系建立好后，中断返回，返回的地址为被中断的指令的地址**（14号中断执行时，PC指针不会自动下移）**，返回地址为被中断的指令的地址的好处是，中断执行完后，这段指令所在的页面一定添加到了物理内存中，所以接下来再执行指令时，再去查段表，页表肯定都是有效的，可以顺利得到物理地址。
有图辅助理解：
（3）页面调入的具体实现
1.首先就是进行页错误中断处理函数的设置，这个很基本，前几个章节讲到过，就是在系统启动的时候的一系列的init()；
void trap_init(){
set_trap_gate(14,&page_fault);
}
set_trap_gate是一段完成IDT表设置的宏，宏展开大概是这样的
#define set_trap_gate(n,addr)
_set_gate(&idt[n],15,0,addr)
跟以前提到的系统调用是不是特别像，以前的系统调用中的DPL位被设置为了3，而现在的DPL位设置为了0，为什么可以用0呢？0不是内核的特权级吗？——因为缺页的错误是由MMU发现的并且中断处理命令是由MMU直接发送给CPU的，并不需要从用户态进入内核态，所以中断处理函数为0即可。
2.调用page_faul页错误中断处理函数
page_fault:
xchgl %eax,(%esp)
movl %cr2,%edx
pushl %edx
pushl %eax
testl $1,%eax
jne 1f
call do_no_page
jmp 2f
1:
call do_wp_page
2:
………………
iret
在page_fault函数主要内容执行之前，一定是需要将用户态的执行现场保存下来，也就是疯狂压栈的过程
该代码首先要取出错误类型，保存到eax中，并将eax压栈，作为后面的调用的函数的参数来使用，接着将cr2寄存器中的内存读写错误的虚拟地址存入edx，并将edx压栈，同样作为参数使用
textl相当于用立即数1和eax中的内容做与运算，判断错误类型，<mark>因为前面eax已经压栈，这里的操作不影响之后函数的使用。</mark>
no——缺页
wp——保护
3.开始进行缺页处理
步骤：
（1）算出所缺的虚拟页号
（2）找到一个空闲的物理内存
（3）从磁盘上将这个虚拟页内容导入物理页框中
（4）填写页表
void do_no_page(unsigned long error_code,unsigned long address){
address &=0xfffff000;
//将后12位去掉，得到虚拟页号（后十二位是页内偏移）
page=get_free_page();
//获得一块空闲物理内存（在物理内存中找到一块值为0的项）
bread_page(page,current->executable->i_dev,nr);
//将虚拟页面内容读入到物理内存中，executable为进程对应可执行文件
put_page(page,address);
//填写页表项，完成映射
}
三、物理内存的换出
1.基础的页面换出算法
（1）FIFO——先进先出算法
这个算法的缺陷就是，页面换入换出次数多，而页面换入换出都需要访问硬盘，我们知道访问硬件的代价是很大的，所以这个算法不好。
（2）OPT——最优置换算法
这个算法就是选择未来最远使用的页面进行淘汰
但是这个算法的不可实现性很明显，我们不可能知道未来的内存使用情况，这是不现实的算法
（3）LRU——最近最少使用算法
这个算法基于程序的局部性原理，在最近时间内最少使用的部分很有可能是未来也经常不会访问的部分，根据过去预测未来，虽然没有直接看到未来那么准~~（狗头）~~。LRU算法也是最有可能且有意义实现的算法
2.LRU算法的实现
（1）时间戳
就是根据页面使用的时间戳来比较找出最近最少使用的页面，怎么做呢，就是每执行一个页面时，就将这个页面的时间戳，相较于上一个使用的页面的时间戳+1，每次需要淘汰的时候就淘汰时间戳最少的就可以了。
听起来不错是吧……同志，你还是太乐观了~
时间戳的实现很有难度，而且很不划算，因为每一次页面的使用都需要维护一次时间戳，并且每一次淘汰也都要维护一次时间戳。，而且由于时间戳与页表关联，时间戳一定位于对应页表项上，但是如果机器执行时间过长，那么即使页表项设置的再大，也总有爆内存的情况出现。
（2）页面栈
就是每使用一次页面，就将这个页面浮动到栈顶，当需要淘汰的时候，只要淘汰栈底的页面即可，但是这也有童谣的问题，指针维护的开销过大，每次维护页面栈的时候都要伴随几次指针的读写，每次地址访问都要维护页面栈，每次地址访问都要伴随几次内存访问，内存读写的效率就太低了，会影响计算机的工作效率。
3.clock算法
（1）clock算法概述——第二次机会置换（SCR）算法
clock算法是对LRU算法的一种典型近似，clock算法的基础是页表项中有一个近似时间戳的信息，里面是0/1。
为什么说clock算法只是LRU算法的一种典型近似呢？——因为clock算法的R位只能表示最近是否访问过，不能表示最少概念。
将分配给进程的所有页框组织成环形线性表，产生缺页时，从当前的线性表指针处开始循环，如果扫描到的R位为1，就将其置成0，当扫描到的R位为0，就淘汰掉这个页表。
（2）clock算法的缺陷
当缺页情况发生过少时，那么最近访问的最近这段时间就会过长，会导致所有页面在最近这段时间都被访问过，所有页面的R位都为1，这会导致，当产生缺页时，我们扫描一次线性表，将所有R位变成0，然后淘汰掉当前扫描指针指向的那个页面，扫描指针后移。然后再等待下一个缺页，所有R位又变成1，换出的又是扫描指针指向的页面，这就导致了<mark>clock算法退化为了FIFO算法</mark>。
（3）clock算法的改进
再引入一个扫描指针，定期扫描一次线性表，将所有R位变成0。这样就能保证真的是**“最近“**了，就不会退化成FIFO算法。
ps：算法需要尽量简单，尽量用硬件来实现。
四、页框个数分配
1.引入
页框的个数分配是我们一定需要考虑的问题，一个好的页框分配，可以使页面的换入换出的次数减少，提高计算机的效率，为什么这么说呢？——因为程序具有局部性，如果物理页框分配的个数不能完全映射常用的虚拟页面，那么就会频繁的换入换出来执行这段本来就经常执行的局部程序。这是很不划算的，所以就需要一个良好的页面分配，正好包含所有的常用页面，又不过剩太多。
系统颠簸图像就是由于上述原因出现。
那么如何解决这个问题呢？——我们引出工作集模型的数学概念
2.工作集模型
（1）核心
该模型的核心就是统计最近一个历史窗口中访问了哪些页，这些页的集合就被成为工作集WS，这个集合的大小就被称为工作集大小，即为WSS，操作系统为进程Pi 分配页框时，就分配WSSi个页框即可。
但是工作集模型在实际系统中很难完美工作，因为既要考虑窗口大小，又要考虑时刻的问题。
五、全局置换策略
1.概述
全局置换策略就是当某个进程需要物理页框的时候，操作系统会去一个全局空闲物理页框链表取出一个空闲物理页框进行分配，定期扫描分配给进程的所有页面（clock算法），最近一段时间内没有被访问的页面，就将其换出到磁盘上，并将对应的物理页框释放到空闲页框链表中。
2.缺点
一个局部较大的进程容易长期占据大量的物理页框，获得更多的内存资源。
例如：嵌套for循环。
京公网安备 11010502036488号