操作系统（三）

虚拟内存

虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。

为了更好的管理内存，操作系统将内存抽象成地址空间，每个程序拥有自己的地址空间，这个地址空间被分割成多个块，每一块称为一页，这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存，当程序引用到不在物理内存中的页时，由硬件执行必要的映射，将缺失的部分装入物理内存并重新执行失败的指令。

从上面的描述中可以看出，虚拟内存允许程序不用将地址空间中的每一页都映射到物理内存，也就是说一个程序不需要全部调入内存就可以运行，这使得有限的内存运行大程序成为可能。例如有一台计算机可以产生 16 位地址，那么一个程序的地址空间范围是 0~64K。该计算机只有 32KB 的物理内存，虚拟内存技术允许该计算机运行一个 64K 大小的程序。

分页系统地址映射

内存管理单元（MMU）管理着地址空间和物理内存的转换，其中的页表（Page table）存储着页（程序地址空间）和页框（物理内存空间）的映射表。

一个虚拟地址分成两个部分，一部分存储页面号，一部分存储偏移量。

下图的页表存放着 16 个页，这 16 个页需要用 4 个比特位来进行索引定位。例如对于虚拟地址（0010 000000000100），前 4 位是存储页面号 2，读取表项内容为（110 1），页表项最后一位表示是否存在于内存中，1 表示存在。后 12 位存储偏移量。这个页对应的页框的地址为（110 000000000100）。

页面置换算法

在程序运行过程中如果要访问的页面不在内存中，就发生缺页中断从而将该页调入内存中，此时如果内存空间已满，系统就必须从内存中调出一个页面到磁盘对换区腾出空间。

页面置换算法和缓存淘汰策略类似，可以将内存看成磁盘的缓存，在缓存系统中，缓存的大小有限，当有新的缓存到达时需要淘汰一些已经存在的缓存这样才有空间放入新的缓存。

页面置换算法的主要目标使页面置换的频率最低（缺页率最低）

最佳

所选择的被换出的页面是最长时间内未被访问的，这是最理想的状态，因为我们无法得知一个页面的最长不被访问时间。

最近最久未使用

LRU，虽然无法知道将来要使用的页面情况，但是可以知道过去的使用页面情况，LRU将最近最久未使用的页面换出。

为了实现LRU，需要在内存中维护一个所有页面的链表，当一个页面被访问时将这个页面移动到链表表头。这样就能保证链表表尾的页面是最近最久未使用的。

因为每次访问都要更新链表，因此这种方式实现的LRU代价很高。

最近未使用（NRU）

每个页面都有俩个状态位，R,M当页面被访问时设置页面的R=1，当页面被修改时设置M=1，其中R位会定时被清零，可以将页面分成以下四类：

R=0，M=0
R=0，M=1
R=1，M=0
R=1，M=1

当发生缺页中断时NRU算法随机的从类编号最小的非空类中挑选一个页面换出。

NRU优先换出已经被修改的脏界面（R=0,M=1）而不是频繁使用的干净页面（R=1,M=0）

先进先出（FIFO）

选择换出的页面是最先进入的页面。

该算***将那些经常被访问的页面也被换出，从而使缺页率升高。

第二次机会算法

FIFO算法可能会把经常使用的页面置换出去，为了避免这一问题，对该算法做一个简单的修改：当页面被访问（读或写）时设置该页面的R位为1，需要替换的时候，检查最老页面的R位，如果R位是0，那么这个页面即老有没有被使用，可以立即置换掉，如果是1，将R=0,把他放到队尾，修改他的装入时间就像他刚装入一样，然后继续从链表的头部开始搜索。

时钟

第二次机会算法需要在链表中移动页面，降低了效率，时钟算法使用环形链表将页面连接起来，在使用一个指针指向最老的页面。

分段

虚拟内存采用的是分页技术，也就是将地址空间划分为固定大小的页，每一页再与内存进行映射。

下图为一个编译器在编译过程中建立的多个表，有 4 个表是动态增长的，如果使用分页系统的一维地址空间，动态增长的特点会导致覆盖问题的出现。

分段的做法是把每个表分成段，一个段构成一个独立的地址空间。每个段的长度可以不同，并且可以动态增长。

段页式

程序的地址空间划分成多个拥有独立地址空间的段，每个段上的地址空间划分成大小相同的页。这样既拥有分段系统的共享和保护，又拥有分页系统的虚拟内存功能。

分段和分页的比较