cpu和cache关于内存换入换出

##一、内存换入

####1.引出换入 从前面我们知道，在内存中段页同时存在

但是实际情况是虚拟内存的大小一般大于物理内存，我们又不得不实现虚拟内存，所以，用换入换出实现这一差别(建立虚拟内存与物理内存的映射)。

分段分页的核心是虚拟内存，而要实现虚拟内存，就需要进行内存的换入和换出

当要访问某一个段的时候，将该段映射到物理内存中，不向相关的数据可以覆盖。

####2.请求调页 先用逻辑地址通过查段表计算出虚拟地址时，再由虚拟地址查页表计算物理地址，当用虚拟地址查页表发现该虚拟地址没有映射，即该页没有载入内存时，需要从磁盘中将该页载入物理内存（请求调页）

逻辑地址CS:IP，首先根据CS在段表中找到对应的基址，加上偏移得到虚拟地址：页号+偏移。然后根据页号在页表中找到对应的页框号，加上偏移得到物理地址。

但是如果在页表中找不到对应的页号对应的页框地址，就要从磁盘上将这一页换入了。

通过虚拟地址查页表找不到映射的情况称作缺页，发现缺页后就要从磁盘中请求调页，这个过程一般比较长，同时需要进入内核，所以在中断中进行。一旦发生缺页，就进入缺页中断，在中断中请求调页。同时建立虚拟内存的该页与物理内存的映射，当请求调页完成时，映射也建立好了

将某页从磁盘换入到内存的，从中断服务函数开始。cpu有专门的中断会就去查找中断号，然后转去执行该中断服务程序。这些东西是在系统初始化的时候就做好了

##二、内存换出 ####1.引入换出 由于物理内存大小是有限的，在内存换入多次后，物理内存就会满，因此必须换页，才能腾出空间给新换入的页。

换页的核心问题是需要选择一页淘汰，换出到磁盘，选择哪一页？类似于进程调度

####2.FIFO算法 即每次缺页的时候就替换掉最开始的那一页（先进先出）

在第一次换D的时候将A换入，但是后面紧跟着又要换入A… 这种算法在这个方面肯定不是最好的算法，因为它没有任何机制保证替换次数尽可能少

####3.MIN算法 选最远（不常用的）将使用的页淘汰， 是最优方案

但是，MIN需要知道将来发生的事，在实际中不可行

####4.LRU算法 选最近最长一段时间没有使用的页淘汰(最近最少使用)

用过去的历史预测将来，可以通过前面调用的页的顺序来推测未来哪些页是常用的，理论基础就是程序的空间局部性。

######实现一：时间戳

用时间戳来记录每页的访问时间

第一次将A放入页框中，并记录当前时间为1；第二次将B放入页框中，并记录当前时间为2；第三次将C放入页框中，并记录当前时间为3；第四次又是访问A页，更新A页访问时间，第五次访问B页，更新B页访问时间；第六次访问D页，不存在，那么就在A、B、C页中选择一个最早使用的也就是数字最小的替换，即C页。

理论上算法可行，但是，每次地址访问都需要修改时间戳， 需维护一个全局时钟， 需找到最小值 … 实现代价较大

######实现二：页码栈

每次选择栈底换出

每次地址访问都需要修改栈(修改10次左右栈指针) … 实现代价仍然较大

####5.Clock算法 LRU的近似实现 – 将时间计数变为是和否

实现这一算法：Second Chance Replacement（再给一次机会）

具体思想：每页增加一个引用位( R )，每一次访问该页时，就将该位置为1。当发生缺页时用一个指针查看每一页的引用位，如果是1则将其置为0，如果是0就直接淘汰。

每次访问一页时， 硬件自动设置该位 选择淘汰页： 扫描该位， 是1时清0， 并继续扫描； 是0时淘汰该页

这种方法提高了内存的效率，只要维护R位（在PCB中）

但是，如果缺页很少，可能会出现所以的R为1（在实际中，缺页的情况不会很多；如果缺页很多了，说明内存太小了或者算法不行）

当发生缺页时，指针转一圈之后将所有的页的引用位都置为0，没找到能替换的，继续转，这时候发现最开始的页引用位为0，将其换出，指针后移

然后又一段时间没有发生缺页，所有页的引用位都为1，当发生缺页之后，又会将这一轮最开始的页换出，然后指针后移，一段时间之后发生缺页，又会将这一轮最开始的页换出，这不就直接退化为FIFO了吗？

原因：记录了太长的历史信息

解决：定时清除R位 再加一个指针用来清除每一页的引用位（这个指针的移动速度要快），可以放在时钟中断里面，定时清除

##三、帧frame 现在置换策略有了，但是还有一个问题：给进程分配多少个页框(帧frame)?

如果分配多，请求调页导致的内存高效利用就没有用。而且内存就那么大，如果每一个进程分配很多的话，跑的进程数量就少了。

如果分配的少，系统内进程增多，每个进程的缺页率增大，当缺页率大到一定程度，进程就会总等待调页完成，导致cpu利用率降低，这一现象为颠簸(thrashing)

所以，先给进程分配一定数量的页框，如果增加页框能增加cpu利用率，就缓慢增加，如果导致cpu利用率减少，就降低页框分配。当然实际情况下每个进程对应的页框数量肯定是得动态调整的。