预备

地址的生成

物理地址

首先一个内存地址代表一个物理内存中一个内存单元的存储空间。

例如：

地址能表示的范围和cpu有关，如果cpu是32位的，按字节编址的话。

首地址是：0，

最后的地址是：2^32 - 1，

地址的个数是：2^32，

内存大小是：地址的个数 * 8（字节的大小） = 4GB，也就是说如果cpu只有32位大小的话，那么寻址空间只有4GB的大小，如果内存超过4GB那么超过4GB的内存空间会被浪费掉，cpu无法查找那么大的内存地址。

逻辑地址

在编程语言中，一个变量是逻辑地址，在机器语言中，一个01序列是一个逻辑地址（因为实际地址要等于逻辑地址+基址寄存器中的值）。

如果要将逻辑地址变为物理地址，我们要通过cpu中的内存管理单元（MMU），MMU提供将逻辑地址通过某种方式映射为物理地址功能。

逻辑地址 ——》物理地址的过程：

内存的分配

连续内存分配

连续内存的分配指的是给一个程序分配一块连续的内存地址空间。这个内存地址空间的大小符合程序所需要的大小。可以过大，但是不能太小。

空闲空间的管理：位图法，和链表法。

• 位图法: 将内存划分成N个分配单元，每个单元在用位图中的一位表示，如果该单元被使用则为1，如果未被使用则为0。
• 链表法: 维护一个由空闲区和进程区表示的链表，其中链表项由空闲和进程指示标志和起始地址还有内存块大小表示。

分配内存的方法：

载入程序
	first fit: 从内存地址的首地址（index：0)开始向后查找，如果找到一块地址空间足够大，可以分配给该程				序，那么就将该程序装入该地址空间。

	worst fit: 将空闲的内存地址空间排序，从这个空闲内存地址空间序列中的头部（最大空闲块）开始给程序分配内			   存地址空间。

	best fit: 从内存地址空间的首地址开始向后查找，找到一块地址空间和该程序所需内存空间最适合的空闲块，分				  配给该程序。

程序申请存放要用的值：程序的堆栈段。

连续地址空间的分配方式会产生内存空间碎片，就是有些内存空间太小，小到不足以存放任何程序，而且这些小内存分布在内存的各个地方。

内存空间碎片分为：

• 内碎片：就是分配给程序，但是程序没有使用的空间。
• 外碎片：各个程序地址空间之间的内存地址空间。

内存碎片的处理方法：

swap：如果一个程序的地址空间不够用了，那么就将内存中的一个未被使用到的内存放入磁盘的交换区。为该程 序提供一个更大的地址空间

压缩算法（memory compaction）：就是将内存中的程序相邻存放，将内存碎片合成一个更大的内存地址空间。

非连续内存的分配

分页

分页是虚拟内存系统中的一种技术。将程序拥有的内存空间划分为N个大小相同的地址空间，这个块被称为页，每个页都有自己的连续地址范围，这些页可以被映射到物理地址空间中。

映射过程:

MMU映射的方式是通过页表来查找page frame number在加上offset位生成物理地址一个页包含多个单元地址空间，通过offset指出是页中的哪个地址空间。

所以我们可以看出一个页的结构由页号加上偏移位。

物理内存中与页所对应的连续内存地址块被称为page frame。

页中的offset和page frame的offset大小相同，offset指的是页大小。

所以虚拟地址转换位物理地址的过程：

​ MMU页表寄存器找到页表的存放的首地址，通过虚拟页号找到page frame number通过与offset相加得到物理地址。

使用虚拟内存还会遇到两个问题，一个是时间，还有一个是空间。

时间指的是：页表通常存放在主存中，不在cache中，如果为了访问内存中的数据，就要访问内存两次（一次是访问页表，一次访问内存数据）这样虚拟内存并未对计算机设计有多大的帮助。

空间指的是：如果虚拟地址有64位，而offset只有14位，那么存放一个页表就需要2^50 * 50 / 8 = 6 400Tib的内存空间来存放页表，这是不可能的。

我们用TLB（快表）来存放经常访问的几个页表项。

用多级页表和反向页表解决页表过大的问题（具体就说将用到的虚拟地址空间存入虚拟内存中，不用的先不存）。

这部分的内容在p112 ~ 116。

虚拟内存

由于程序对内存容量需求的增长快于内存容量的增长，为了使得计算机可以并发运行多个程序，但是要解决内存不足的问题，虚拟内存技术就出现了。

在虚拟内存之前，还有两个解决内存不足的方法：

• overlay（覆盖）

  overlay需要程序员将一个程序划分成多个代码块，多个代码块之前分组公用一个代码块，但是被调代码块不能够与调用的代码块公用一块内存块，所以overlay还需要程序员指定好每个代码块的内存块。
  
  在代码块被换出内存时，操作系统要保护好被换出代码块的所有信息。待该代码块换入内存时，能够恢复被换出前的所有状态，不影响接下去的执行。
  
  具体的如下图所示。
  

  

• swap

  swap就是将程序载入内存，待程序执行一段时间后，将程序换出到磁盘中去，主存中只保留需要执行的进程，而空闲进程就保留在磁盘中。
  

虚拟内存技术的出现:

overlay需要程序的支持,会给程序员的编码带来额外的工作和负担,而swap技术如果进程的内存容量大那么换入换出的成本太高了。虚拟内存技术可以将原本需要程序员来做的程序分块交由操作系统来完成，也是通过swap方法，但是不是大块程序的换入换出，而是更加细小的程序块换入换出。这个内存块被称为页，分页技术也是目前实现虚拟内存的主要技术。

虚拟内存的特征：

• 大空间

  每个程序都有自己的虚拟内存地址空间，虚拟内存地址空间 = 主存 + 外存。

• 部分交换

  将目前执行程序，需要用的页载入内存，不需要的页换出外存（只有当内存空间满了，但是又要载入页的时候才将内存中不需要的页换出）

• 不连续性

  虚拟内存技术是，每个程序都有连续的虚拟内存地址，但是虚拟内存地址映射到物理内存上的时候是不一定连续的。这个也解决了内存碎片的问题。

缺页（page fault）处理：

页表项说明：

一个页表项由Valid、dirty、ref、物理内存地址组成。

valid：表示这个虚拟内存所对应的物理内存存不存在。

dirty：表示这个虚拟内存所对应的物理内存又没有被重写。当这个位1时，这个物理内存要从内存地址中置换出去时，我们要先把数据写回外存才可以清空这物理内存的信息，将新页置换进来。

ref：这个虚拟内存所对应的物理内存最近有没有被引用。这个位是为置换算法服务的。这个位隔一段时间就被置0，当被cpu访问的时候被置1。

cpu将逻辑地址(虚拟内存地址)提交给MMU,MMU首先查看TLB,如果TLB有所对应的内存地址,就之间访问该内存,取出数据.如果没有所对应的内存地址,MMU就去访问内存中的page table,如果page table有对应的物理内存地址,那就将该页表现换入快表中(如果TLB中的dirty位为1时,我们要先将该项的dirty位写回内存所对应的页表项中),如果没有的话,cpu就发出异常,操作系统根据异常提供逻辑地址的信息,去外存中找到相应的页换入内存中去(如果内存中的dirty位为1时,就要先将数据写回外存).

页换出的位置:

如果时程序文件,就是换出到程序所在的外存位置.
如果时程序运行过程中的临时数据,就换出到操作系统的swap空间中去.

置换算法

最近未被使用（NRU）

NRU算法根据页表中的页表项的ref位和dirty位将所有页表了分为四类：

当每次缺页中断发生时，操作系统检查页表中的所有页表项，随机挑一个编号（表中，由ref和dirty位组成的2位二进制表示的十进制数的编号）最小的页表项替换出去。其中ref位就是访问位会定期的清零。

如果硬件没有提供ref位和dirty位，那么根据缺页异常来设置内部表中的ref位和dirty位。例如：读取某个页面发生缺页异常时，操作系统捕获异常，设置内部表的R位，并添加页表项指向正确的页面，设置该页为只读模式，如果写入某个页面发生缺页异常，那么操作系统设置W为，设置该页为可读可写页。

先入先出（FIFO）

操作系统维护一个链表，根据页表的换入内存的时间为顺序，越早换入内存的页表越靠近表头，越晚换入内存的链表越靠近表尾，当发生缺页异常时，操作系统将表头的页面换入外存，并将新的页面换入主存。

第二次机会法

第二次机会算法是对FIFO算法的一个优化，因为一个表头的页面可能是一个经常访问的页面，虽然他最早换入内存，如果它被换出去，由于经常访问的原因，后续指令可能很快又需要访问该页面导致缺页异常。那么我们就要设置相应的机制，不让它替换出去。

那就是当缺页异常发生时，将表头的替换出内存时，我们要检查该页的ref位，如果该ref位是1，那么就证明该页还有被引用，因此我们将该页换到表尾，然后检查下一页，直到ref为0，将缺失的页再载入到内存中去，并加到表尾。

时钟页面置换算法

二次机会算法要做链表项的移动处理，移动处理不仅没有必要还降低算法的效率。时钟页面置换算法将链表的表头表尾相联，使用一个指向链表项的指针，该指针指向最早加入链表的页。当发生缺页异常时，操作系统就检查指针所指的页面，如果ref位为0就清除该页，并将新页替换到该位置，指向指向下一个页。如果ref位为1就将ref设置为0并将指针指向下一位，直到找到一个ref位为0的页。

最近最少使用页面置换算法（LRU）

LRU算法的基础是程序具有局部性原理，因为LRU是根据历史推测未来，如果一个页最近一直被使用，那么它就符合时间局部性原理，未来它还可能接着被使用，那么我们不能将该页置换出去，如果一个页最近使用的频率很低，那么就不符合时间局部性原理。未来可能不会再被使用，那么我们就可以将该页替换出去。如果程序不具有局部性，那么LRU的推测将毫无作用，因为LRU是假定程序具有局部性原理的前提下的一个算法。

但是LRU的算法实现代价很高，因为LRU需要维护一个链表，使用频率越高的页越靠近表头，使用频率越低的页越靠近表尾。那么这就需要大量的链表操作。因为没访问一个页，记录页的使用频率的值就要加一，这个值一变化就要调整链表的顺序。

最不常用置换算法（NFU）

每个页都有一个相应的软件计数器关联，每次时钟中断时，操作系统扫描一遍内存，将ref位与相关联的计算器相加，当产生缺页异常的时候，操作系统将计数器值最低的那个页替换出去。

NFU的算法有一个问题就是，当一个页曾经很长的一段时间频繁使用，那么这个页的计数器值很高，导致后来这个页可能不使用了，但是这个值依然很高，它还是会存放在内存中。然后将有用的页给替换出去。

老化算法

老化算法是对NFU算法的一种优化。

首先每次时钟中断，ref位和页相应的计算器相加的时候，先将计数器右移一位，然后将ref位的值和最低位相加。

老化算法就是定时定时减少每个页访问次数计数的值，就像NFU算法的问题一样，一个页面一段时间被进程访问，但是后面不访问了，后面的页面访问的频率并不会都比这个页面高，所以页面常驻内存中，当时老化算法就是针对这一个情况，如果一个页面后面不访问了，那么它将一致衰减直到0，而后面的页面只要访问最少累计访问次数也会是1就不会被换出内存。

工作集页面置换算法

工作集：就是进程目前正在使用页面的一个集合。

常驻集：就是进程目前需要的页面在内存中的集合。

也就是说，如果给进程分配的内存足够大的时候，工作集的页面都可以载入内存中，此时常驻集等于工作集，那么缺页异常的概率就会降低。如果给进程分配的内存不足以装下所有页面，那么常驻集就是工作集的一个真子集。

如果常驻集的元素远小于工作集，那么程序很容易发生抖动。因为工作集代表的是进程当前时刻需要访问的内存，而常驻再内存的页又太少，需要频繁的做换入换出的操作。例如，工作集是0，1，2，3。常驻集是1，2。如果内存中存在在页是0、1那么下一条指令可能需要页2，就要置换出页0或者页1。同理，一条可能需要3，那么又得置换，如果再下一条又需要0。那么此时0已经被置换出内存，需要再置换入内存。大部分时间都花在了io身上。导致进程执行时间很长。

抖动:如果一个进程运行时间(io时间和cpu时间)绝大多数都是io时间,那么这个就是抖动现象,也就是说缺页率太高导致要频繁的执行页面置换工作。

工作集的生成

程序要具有局部性,工作集才好用,如果不具有局部性,那么工作集和页都要频繁的更改.

1. 规定一个数值k,将当前指令访问的页与之前指令访问的(k-1)个页为一组。将这些页提取出来去除重复页，生成的就是一个工作集。

   具体方法就是使用一个k大小移位寄存器, 这个寄存器存放进程最近访问过的k个页面，当进程每做一次内存访问，就将移位寄存器左移一位，并将新页放入寄存器中，当缺页中断发生时，将不在工作集中的页换出，并将移位寄存器的值提取出来，删除重复元素，排序生成工作集。
   

2. 还有一种是基于时间生成的工作集。规定一个时间间隔。

工作集的置换过程

当缺页发生时，操作系统扫描内存。

如果ref == 1将新的访问时间写入，替换旧的访问时间。

如果ref == 0 但是访问时间在规定的时间间隔内，就保留该页面。

如果ref == 0 但是访问时间超过了规定时间间隔，就换出该页。

如果所有页面都在规定的时间间隔内，也就是都在工作集中，那么选择一个ref = 0 并且最早换入的页。

如果ref都等于一，那么就随机替换一个，最好时干净的页。

工作集时钟页面置换算法

与时钟算法一样，但是加入了工作集的限制。

首先将指针指向最早加入链表的页，如果引发缺页中断，那么检查该页

如果ref == 0如果在间隔内，就不适合被淘汰，就跳过该页，

如果等于ref == 1就将ref = 0然后指向下一页。

如果ref == 0并且不在时间间隔内，dirty == 0就替换该页，将新页置换进来

如果ref == 0并且不在时间间隔内，但是如果dirty == 1，那么也要跳过该页，去寻找一个旧的可以替换的页。写回操作可能在跳过后某个时钟周期完成了。完成写回后dirty = 0，那么下次检查时，就可以替换该页了。

局部性策略和全局策略

以上算法均可用于全局策略或者局部策略。

• 局部策略

  局部策略只针对操作系统给该进程分配的物理地址空间上进行操作，如果缺页了被替换的页还是该进程的物理地址空间的页。
  

• 全局策略

  全局策略是针对整个内存进行页面替换操作,就是说,被替换的页是该进程地址空间内的页,也可以上是其他进程地址空间内的页。
  

  在全局策略上进行的算法可以动态的调控每个进程所需要的物理页帧的大小，降低抖动现象的产生，因为需要大物理地址空间的页我们动态的给它分配更多的物理地址空间，通过减少其他进程的物理地址空间，依据缺页中断率（PFF）算法。

  PFF算法:当一个进程的缺页终端率大于一个阈值时,我们就要给该进程增加物理地址空间,当低于一个阈值时,减少它的物理地址空间.