存储系统

内存是计算机中重要资源,计算机运行时所需的各种数据几乎都存在内存中.

正如帕金森定律指出的, 不管存储器有多大程序总能将其填满.分层存储为这个问题提供了廉价的解决方案

现代个人计算机的存储器通常由3层组成:

MB级, 快速, 昂贵, 易失的高速缓存(cache)
GB级, 速度和价格中等, 易失的内存(memory)
TB级, 低速, 廉价, 持久存储的磁盘

这里的易失性是指存储器断电后会丢失数据.

操作系统的内存管理器(Memory Management Unit, MMU)为我们提供了虚拟内存服务, 以解决内存冲突和空间不足等问题.

假设所有进程都可以访问任意的内存地址, 这样不同进程之间的存储区极易发生冲突, 恶意程序也可以轻易地破坏其它程序的运行.

虚拟内存为每个进程创建了一个独立的虚拟内存空间, MMU会将进程对虚拟内存地址的访问映射到物理地址.

进程不关心虚拟内存的具体位置, 只需了解空间大小.同样, 进程也无法访问未授权访问的空间.

进程总是希望得到连续的空间, 但是在内存中寻找或清理连续空间开销很大. 虚拟内存可以将分散的物理空间映射为连续的虚拟空间, 同时也可以方便地使用新的内存块扩展虚拟内存的大小.

在实际运行环境中, 大多数程序只是对少部分数据进行频繁访问. 这就允许我们将少数频繁使用的数据存放在内存中, 大量很少使用的数据存储在磁盘上,在需要时读入内存.因为可以使用磁盘存储数据, 一些程序可以在内存不足的系统上运行了.

虚拟内存的最大地址取决于操作系统寻址宽度(字长), 16位操作系统地址范围从0到64K, 即使计算机只有32K的物理内存.

CPU, 内存和总线等硬件设备的宽度由电路结构决定, 但是他们也可以模拟半字长甚至双倍字长工作模式.

分页

很多虚拟内存系统采用分页(paging)的技术, 即将虚拟空间地址按照固定大小划分成称为页面(page)的小单元, 在物理空间中对应的单元称为页框(page frame).

以4KB的页面为例, 在64K地址空间(16位)和32K物理内存的系统上得到16个页面和8个页框.

虚拟地址被分为页号(高位部分)和页内偏移量(低位部分),对于16位地址和4KB页面, 高4位用于指定页面, 低12位用于指定页内偏移.

页表是分页系统的一种简单实现, 用于保存页和页框之间的映射关系, 每个虚拟页的页表项依次为:

高速缓存禁止位: 禁止页被写入高速缓存, 主要用于映射到设备寄存器而非内存的页.
访问位(referenced): 标记该页近期是否被访问过, 一般会被定时清零
修改位(modified): 标记该页是否被修改过, 如果该页已经被修改过(也称页是脏的)则必须写回磁盘, 若该页未被修改过(该页是干净的)则无需更新副本, 置换时可以直接丢弃.
保护位: 表示该页允许以什么方式访问, 最简单的只有一位代表是否可以访问, 也可以使用三位表示是否允许读,写和执行.
页框号: 页表的核心部分, 页框的内存地址.

页表只负责将虚拟地址转换为物理地址, 不存储页在磁盘中存储的位置.当内存中没有保存页面时将产生一个缺页中断, 处理机制会将页从磁盘上置换进来.

随着操作系统寻址宽度从32位增加到64位, 虚拟地址空间增加到30PB, 传统的页表结构很难索引如此多的页.

采用多级页表可以很方便地扩展容量,但是会降低寻址速度.

64位操作系统中虽然虚拟内存地址增加到30PB, 但是物理内存仍然只有GB级.倒排页表采用将页框地址映射到虚拟地址, 这样页表只有GB级空间对应的页项, 但是每次映射都需要遍历整个页表.

TLB

因为每次访问内存都需要查询一次页表, 加快页表访问速度是非常有意义的.

大多数程序总是频繁访问少数的页, 我们可以将这些页的页项写入高速缓存中, 这个缓冲区称为转换检测缓冲区(Translation Lookaside Buffer, TLB), 也被翻译做快表.

在使用硬件MMU的系统中, 硬件将会并行搜索TLB, 若TLB中不存在页项则会进行置换, 只有页面不在内存中才需要操作系统处理.

许多RISC操作系统页面管理完全由软件实现.在使用软件TLB的系统中,缺页失效有两种可能:

软失效(soft miss): 页在内存中, 页表项不在TLB中, 此时只需要更新TLB即可.
硬失效(hard miss): 页不在内存中, 此时需要进行页面置换.

页面置换算法

最优页面置换算法

最优页面置换算法非常容易理解, 若两个页面A和B, A会在10K条指令后被访问, B在100K条指令后被访问那么将首先置换页面A.

但是操作系统无法预知访问请求, 该算法实际上无法实现.

但是最优算法为我们提供了一个评价标准, 一个算法的效果若非常接近最优算法, 则付出很大努力改进只能带来非常有限的性能提升.

最近未使用页面置换算法

最近未使用(Not Recently Used, NRU)算法, 是一种简单但基本满足需求的算法.

在提供虚拟内存的操作系统中, 页项一般有访问标记R和修改标记M. 当然即使没有, 也可以采用软件模拟的方式.

当页面被创建时R和M都被值为0, 若被访问R则被置为1, 若被修改则W被置为1, 同时R被定期地清零.

根据两个标志位的状态, 算法确定置换优先级, 从高到低为:

R=0, W=0
R=0, W=1
R=1, W=0
R=1, W=1

高优先级的页面会被首先置换入磁盘. 每次置换都需要扫描整个页表, 开销略大.

第二种情况貌似不会出现, 考虑到R会被定期清零, 状态4被清零后即产生了状态2.

先入先出置换算法

先入先出(First-In, First-Out, FIFO)是一种开销略小的算法.

纯粹的FIFO算法中, 先创建的页面会首先被置换显然会频繁地产生缺页.

第二次机会置换算法

二次机会置换算法是对FIFO算法的改进, 当最老的页面将被置换出内存之前检查它的R标志位.

如果R标志位为0则将其置换出去, 若R标志位为1则将其重置为0, 然后作为新的页面加入到队列尾部.

这个算法很好的平衡了避免缺页和搜索的开销.

时钟页面置换算法

尽管第二次机会置换算法是一个比较合理的算法, 但需要经常在链表中移动页面既降低了效率又不是很有必要.

一个更好的方法是把所有页面都保存在一个类似表盘的环形列表中, 一个指针指向最老的页面.

当需要置换时检查指针指向的页面, 若R为0则置换出去, 否则重置为0, 让指针指向前一个页面.

指针指向前一个页面的过程等价于将队尾重置为队首, 大幅度降低了开销.

最近最少使用页面置换算法

最近最少使用算法(Least Recently Used, LRU)算法的思想是若一个页面最近很少被使用则它在最近一段时间内也很少被使用.

LRU虽然可以实现但是代价巨大, 为了实现LRU需要在内存中维护一个所有页面的链表.每次访问都需要更新被访问页面的位置.

最不常用(Not Frequently Used, NFU)是LRU算法的一种软件模拟. 每个页面拥有一个软件计数器, 计数器初值为0.

操作系统定时扫描所有页面并将其R位加到计数器上, 发生缺页中断时置换计数最小的页面.

NFU的问题在于因为R位不被清零, 第一次扫描时被频繁使用的页面在后续的扫描中可能仍然被认为是频繁使用的.

对于这个问题只需要进行引入老化(aging)机制, 每次扫描原来计数值右移一位, R标记加在最高位.

这样时间越长的访问记录权重就越小直至被丢弃.

工作集页面置换算法

在纯粹的分页系统中, 进程开始运行时内存中没有页面, 初期的内存访问将产生大量的缺页中断.

在运行一段时间后, 被频繁访问的页面大部分已经被放入内存了.一个进程运行过程中正在使用的页面称为进程的工作集.

在多任务操作系统中, 经常会将进程转移到磁盘上, 即将进程的所有页面转移到磁盘上.

当再次开始执行这个进程时,初期将会产生大量中断降低运行速度.

若操作系统跟踪进程的工作集, 并在再次运行进程之前将它们提前调入内存, 可以减少运行初期的缺页中断提高速度, 这就是工作集置换算法.

分段

程序员经常遇到需要将堆栈,指令和数据在内存中分别放置的需求,但是页只能提供有一维地址的定长存储.

在页式虚拟内存下, 程序员不得不在程序中控制各部分的起始地址和长度, 并自行处理地址冲突等问题.

内存中还有空间, 但是A和B已经碰撞,除非移走其中一个否则A的空间不能继续延长.

分段技术可以将虚拟内存地址分为多个独立的称为段(segment)的一维地址空间.

每个段的地址均从0开始, 长度可以动态变化, MMU会处理其增长过程中与其它段的冲突.

我们可以将一个程序的虚拟内存空间分为数据段, 指令段, 堆栈段等, 每个段地址从0开始, 不必关心其它细节.

因为段的长度是动态的, 采用纯分段的方法容易产生大小不一, 难以利用的内存碎片.

如果一个段的长度过大, 将它整个保存在内存中是浪费甚至是不可能的, 因此我们考虑将分段和分页两种方式结合起来.

MULTICS是第一个支持段页式虚拟内存的系统, 它将一个段视作一个虚拟内存并加以分页.

MULTICS下每个程序拥有一个段表, 使用段描述符来保存段的信息.

每个段被分为多个页进行保存和置换, 若段的一个页在内存中那么就认为段在内存中.段表本身也是一个段, 并被分页.

段描述符中包含了段的页表所在内存地址, 段长度(以页为单位), 页长度, 是否分页, 以及保护位等信息.

Intel Pentium的虚拟内存与MULTICS类似同样采用段页结合的方式.

Pentium的虚拟内存核心是两张表, 局部描述符表(Local Descriptor Table, LDT)和全局描述符表(Global Descriptor Table, GDT).

每个进程拥有一个独立的LDT, 所有进程共享一个GDT. LDT用于保存进程自身的段, GDT描述系统段.

为了访问一个段, 进程必须把一个段的选择码(selector)装入寄存器中.

选择码中有一位标记该项(选择码)位于GDT还是LDT中, 使用两位描述其权限, 剩余的13位为段描述符索引.

Pentium设计了4级的段机制保证安全, 从高到低为:

0: 内核
1: 系统调用
2: 共享库
3: 用户程序

高权限程序可以访问低权限段, 低权限程序则无法访问高权限的段.