操作系统中管理分层存储体系的部分称为存储管理器(memory manager)。它的任务是有效的管理内存,即记录哪些内存是正在使用的,哪些内存是空闲的;在进程需要时为其分配内存,在进程使用完后释放内存。

一、无存储抽象

早期大型计算机(20世纪60年代之前)、小型计算机(20世纪70年代之前)和个人计算机(20世纪80年代之前)都没有存储抽象。每一个程序都直接访问物理地址。
那时呈现给编程人员的存储器模型就是简单的物理内存:从0到某个上限的集合,每一个地址对应一个可容纳一定数目二进制位的存储单元,通常是8个。

二、一种存储器抽象:地址空间

地址空间就像进程的概念创造了一类抽象的CPU以运行程序一样,地址空间为程序创造了一种抽象的内存。地址空间是一个进程可用于寻址内存的一套地址集合。每个进程都有一个自己的地址空间,并且这个地址空间独立于其他地址的进程空间(除了在一些特殊情况下进程需要共享它们的地址空间外)。

  • 交换技术:
  • 交换技术即把一个进程完整调入内存,使该进程运行一段时间,然后把它存入磁盘。交换在内存中产生了多个空闲区(hole,也称空洞),通过把所有的进程尽可能向下移动,有可能将这些小的空闲区合成一大块。该技术称为内存紧缩(memory compaction)。通常不进行这个操作,因为需要耗费大量的CPU。
  • 通过交换技术,系统可以同时运行总内存占用超过实际物理内存大小的多个进程。如果一个进程没有内存空间可用,它将会被交换到磁盘上。内存和磁盘上的空闲空间可以使用位图或空闲区链表来记录。

空闲内存管理:

  1. 使用位图的存储管理:内存可能被划分成小到几个字或大到几千个字节的分配单元。每个分配单元对应于位图中的一位,0表示空闲,1表示占位(或者相反)。
  2. 使用链表的存储管理:维护一个记录以分配内存段和空闲内存段的链表。其中链表中的一个结点或者包含一个进程,或者是两个进程间的一块空闲区。链表中的每一个结点都包含以下域:空闲区(H)或进程(P)的指示标志、起始地址、长度和指向下一结点的指针。

三、虚拟内存

程序大于内存的问题在20世纪60年代所采取的解决办法是:把程序分成许多片段,称为覆盖(overlay)。这个办法需要把一个大程序分割成小的、模块化的片段是非常费时和枯燥的,并且易于出错。很少使用覆盖技术。另一个办法就是虚拟内存(virtual memory)。基本思想是:每个程序拥有自己的地址空间,这个空间被分割成多个块,每一块称作页或页面(page)。每一页有连续的地址范围。这些页被映射到物理内存,但并不是所有的页都必须在内存中才能运行程序。当程序引用到一部分的物理内存中的地址空间时,由硬件立刻执行必要的映射。当程序引用到一部分不在物理内存中的地址空间时,由操作系统负责将缺失的部分装入物理内存并重新执行失败的命令。从某种角度来讲,虚拟内存是对基址寄存器和界限寄存器的一种综合。

  • 分页
  • 大部分虚拟内存系统中都使用一种称为分页(paging)的技术,在任何一台计算机上,程序引用了一组内存地址。地址可以通过索引、基址寄存器、段寄存器或其他方式产生。
  • 由程序产生的这些地址称为虚拟地址(virtual address),它们构成了一个虚拟地址空间(virtual address space)。在没有虚拟内存的计算机上,系统直接将虚拟地址送到内存总线上,读写操作使用具有同样地址的物理内存字;而在使用虚拟内存的情况下,虚拟地址不是被直接送到内存总线上,而是被送到内存管理单元(Memory Management Unit,MMU),MMU把虚拟地址映射为物理内存地址。
  • 虚拟地址空间按照固定大小划分成被称为页面(page)的若干单元。在物理内存中对应的单元称为页框(page frame)。
  • 页表
  • 虚拟页号可以作为页表的索引,以找到该虚拟页面对应的页表项。由页表项可以找到页框号(如果有的话)。然后把页框号拼接到偏移量的高位端,以替换掉虚拟页号,形成送往内存的物理地址。
  • 页表目的是把虚拟页面映射为页框。从数学角度来说,也表是一个函数,它的参数是虚拟页号,结果是物理页框号。通过这个函数可以把虚拟地址中的虚拟页面域替换成页框域,从而形成物理地址。
  • 针对大内存的页表:1.多级页表 2.倒排页表

四、页面置换算法

当发生缺页中断时,操作系统必须在内存中选择一个页面将其换出内存,以便为即将调入的页面腾出空间。如果要换出的页面在内存驻留期间已经被修改过,就必须把它写会磁盘以更新该页面在磁盘上的副本;如果该页面没有别修改过(如一个包含程序正文的页面),那么它在磁盘上的副本已经是最新的,不需要回写。直接调入的页面覆盖被淘汰的页面就可以了。
下面是一些页面置换算法:

算法注释
最优算法不可实现,但可以做基准
NRU(最近未使用)算法LRU的很粗糙的近似
FIFO(先进先出)算法可能抛弃重复页面
第二次机会算法比FIFO有较大的改善
时钟算法现实的
LRU(最近最少使用)算法很优秀,但很难实现
NFU(最不经常使用)算法LRU的相对粗略的相似
老化算法非常近似LRU的有效算法
工作集算法实现起来开销很大
工作集时钟算法好的有效算法

五、分页系统中的设计问题

  • 局部分配策略与全局分配策略:局部算法可以有效地为每个进程分配固定的内存片段。全局算法在可运行进程之间动态的分配页框因此分配给各个进程的页框数是随时间变化的。全局算法在通常情况下工作得比局部算法好,当工作集的大小随进程运行时间发生变化时这种现象更加明显。
  • 内存映射文件:这中机制的思想是:进程可以通过发起一个系统调用,将一个文件映射到其虚拟地址空间的一部分。在多数实现中,在映射共享的页面时不会实际读入页面的内容,而是在访问页面时才会被每次一页地读入,磁盘文件则被当作后被储存。当进程退出或显式地解除文件映射时,所有被改动的页面会被写回到磁盘文件中。
  • 清除策略:为保证有足够的空闲页框,很多分页系统有一个称为分页守护进程(paging daemon)的后台进程,它在大多数时候睡眠,但定期被唤醒以检查内存的状态。如果空闲页框过少,分页守护进程通过预定的页面置换算法选择页面换出内存。如果这些页面装入内存后被修改过,则将它们写回磁盘。

六、有关实现的问题

缺页中断处理发生时的顺序如下:

  1. 硬件陷入内核,在堆栈中保存程序计数器。大多数机器将当前指令的各种状态信息保存特殊的CPU寄存器中。
  2. 启动一个汇编代码例程保存通用寄存器和其他易失的信息,以免被操作系统破坏。这个例程将操作系统作为-一个函数来调用。
  3. 当操作系统发现一个缺页中断时,尝试发现需要哪个虚拟页面。通常一个硬件寄存器包含了这一信息,如果没有的话,操作系统必须检索程序计数器,取出这条指令,用软件分析这条指令,看看它在缺页中断时正在做什么。
  4. 且知道了发生缺页中断的虚拟地址,操作系统检查这 个地址是否有效,并检查存取与保护是否一致。如果不一致, 向进程发出一个信号或杀掉该进程。如果地址有效且没有保护错误发生,系统则检查是否有空闲页框。如果没有空闲页框,执行页面置换算法寻找一个页面来淘汰。
  5. 如果选择的页框“脏”了,安排该页写回磁盘,并发生一次上下文切换,挂起产生缺页中断的进程,让其他进程运行直至磁盘传输结束。无论如何,该框被标记为忙, 以免因为其他原因而被其他进程占用。
  6. 一旦页框“干净”后(无论是立刻还是在写回磁盘后),操作系统查找所需页面在磁盘上的地址,通过磁盘操作将其装入。该页面正在被装入时,产生缺页中断的进程仍然被挂起,并且如果有其他可运行的用户进程,则选择另一个用户进程运行。
  7. 当磁盘中断发生时,表明该页已经被装人,页表已经更新可以反映它的位置,页框也被标记为正常状态。
  8. 恢复发生缺页中断指令以前的状态,程序计数器重新指向这条指令。
  9. 调度引发缺页中断的进程,操作系统返回调用它的汇编语言例程。
  10. 该例程恢复寄存器和其他状态信息,返回到用户空间继续执行,就好像缺页中断没有发生过一一样。

七、分段

一种能不用管理表扩张和收缩的方法:在机器上提供多个互相独立的称为段的地址空间。每个段由一个从0到最大的线性地址序列构成。各个段的长度可以是0到某个允许的最大值之间的任何一个值。 不同的段的长度可以不同,并且通常情况下也都不相同。段的长度在运行期间可以动态改变,比如,堆栈段的长度在数据被压人时会增长,在数据被弹出时又会减小。
需要强调的是,段是一个逻辑实体。一个段能包括一个过程、一个数组、一个堆栈、一组数值变量,但一般不会同时包含多种不同类型的内容。
如果要处理在执行过程中大小有变化的数据结构,分段是一个有用的选择,它还能简化链接和共享。不仅如此,分段还有利于为不同的段提供不同的保护。有时,可以把分段和分页结合起来,以提供二维的虚拟内存。