1.4 内存管理

虚拟内存

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

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

分页系统地址映射

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

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

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

分页系统地址映射

页面置换算法

在程序运行的过程中，如果访问的页面不在内存中（缺页），就需要从磁盘读取。如果此时内存已满，就需要淘汰部分内容腾出空间。这个过程与缓存的淘汰策略类似。

页面置换算法的主要目标是使得页面置换频率最低。

1. 最长时间不访问（最优，理论存在）

OPT，Optimal replacement algorithm，是一种理论上的算法，因为无法知道一个页面多长时间不再被访问。

2. 最近最久未使用

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

3. 最近未使用

NRU，not recently used

每个页面都有两个状态位：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）。

4. 先进先出

FIFO，First In First Out，该算法会使经常访问的页面被换出，从而使缺页率升高。

5. 第二次机会算法

对先进先出算法的改进，当页面被访问时设置该页面的R=1，需要替换时，检查最老页面的R，如果R=0，换出，如果R=1，设置R=0，并将该页面放在链表的尾端，修改它的装入时间为新装入，继续从链表的头部开始搜索。

第二次机会算法

6. 时钟

对第二次机会算法的改进，第二次机会算法移动链表，降低效率，时钟算法使用环形链表将页面链接起来，再使用一个指针指向最老的页面。

时钟

分段

虚拟内存采用的是分页技术，也就是将地址空间划分成固定大小的页，每一页再与内存进行映射，动态增长的表存在覆盖的问题。

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

段页式

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

分页和分段的比较

• 对程序员的透明性：分页透明，分段需要显式划分；

• 地址空间的维度：分页是一维空间，分段是二维的；

• 大小是否可以改变：页的大小不可变，段的大小可以动态改变；

• 出现的原因：分页主要用于实现虚拟内存，从而获得更大的地址空间；分段是为了保护。