操作系统原理 Principles of Operating System1第4章 存储管理n存储器是计算机的记忆部件，计算机系统的主要 用途是执行程序，在执行程序时，这些程序及其 所访问的数据必须在内存里。由于内存通常太小 不足以永久地容纳所有数据和程序，因此计算机 系统必须提供外存（如硬盘）以扩充内存的技术 。n在现代计算机系统中，内存是一个关键性的资源 。能否合理而有效地使用它，在很大程度上反映 了操作系统的性能，并直接影响整个计算机系统 作用的发挥。所以，存储管理是目前人们研究操 作系统的中心问题之一。本章我们将讨论多种不 同存储管理方法 24.4.1 存储器的层次n三级存储器结构 n高速缓存（cache）内存（primary storage）外存 （secondary storage） 34.1.2 存储管理的功能n1.内存分配和回收n内存的利用率与内存分配的技术、方式和策略有直接关 系。n2.内存保护n内存保护就是确保多个进程都在各自分配到内存区域内 操作，互不干扰，防止一个进程破坏其他进程的信息。 n3.内存扩充n内存“扩充”包含了存储器利用的提高和扩充两方面的内 容。为用户提供比内存物理空间大得多的地址空间。比 较典型的内存扩充是虚拟存储器。 n4.地址映射n地址映射就是将进程的逻辑地址变换为内存中的物理地 址。我们需要实现从逻辑地址到物理地址的变换，即实 现从虚地址到实地址的变换。这种变换就是重定位。 4几个重要的概念 n逻辑地址n逻辑地址就是指令在程序中的地址，源程序经编译（或解释）后 编排的地址。逻辑地址也叫相对地址或虚拟地址。n逻辑地址空间n逻辑地址空间就是某程序的逻辑地址的集合，逻辑地址空间可简 称为地址空间。n物理地址n物理地址就是进程中的指令和数据在内存中的地址，指令和数据 存放在内存中的内存单元编号。物理地址也叫绝对地址或实地址 。n物理地址空间n物理地址空间是指进程在内存中一系列存储信息的物理单元的集 合。物理地址空间也叫存储空间，存储空间与地址空间既相互关 联，又相互独立，是内存管理的核心概念。54.1.4 重定位n为使程序正确执行。一个程 序装入内存，要进行逻辑地 址到物理地址的重定位，实 现从逻辑地址到物理地址的 变换，重定位可分为静态重 定位和动态重定位。n静态重定位n进程装入内存时，由装入程 序对进程中的指令和数据的 地址进行修改，将程序中的 逻辑地址变换成物理地址。 即物理地址基址+逻辑地 址。 6n优点：简单，无需增加硬件就 可以实现。n缺点：要求连续的内存存储空 间，程序装入内存后就不可移 动，且难以做到程序和数据的 共享，内存的利用率差。n动态重定位n如图4-3所示，进程装入内存 时不定位，在指令执行期间 CPU每次访问内存时进行重定 位，这种定位方法需要硬件的 支持，系统中需设置一个地址 变换机构。 7n优点：内存空间的占有量可以改变，容易实现共 享。n缺点：需硬件支持，成本增加。n动态重定位是一种允许进程在执行过程中在内存 中移动的技术，必须获得硬件地址变换机构的支 持。在多任务操作系统中，多个进程在内存中并 发执行，进程的创建与撤消，多个进程之间频繁 的上下文切换，其内存分配呈现动态性和随机性 。静态重定位仅适应于连续分配，不能满足多任 务操作系统动态性和随机性的要求，因此多任务 操作系统存储管理适合采用离散分配，必须采用 动态重定位。84.2 分区式存储管理n内存分配方式可分为连续分配方式和离散分配方 式，本节将讨论连续分配方式。分区式存储管理 是连续分配方式，为一个进程分配一个连续的存 储空间。分区式存储管理支持多道程序系统和分 时系统，但内存分配存在不可利用的内存空间， 即碎片问题。碎片一般可分为内碎片和外碎片。 前者是指分区内不可利用的内存空间，后者是指 分区之间难以利用的小空闲分区。内碎片和外碎 片都可以降低内存的利用率，但外碎片对系统的 危害更大。关于碎片问题将在各种内存分配方式 中详细讨论。94.2.1单一连续分配n单一连续分配内存分配优缺点 如下：n优点：实现简单，不需要复杂 的软、硬件支持。n缺点：存在内碎片问题。资源 利用率低，由于存储资源利用 率低而造成其他资源利用率低 （如CPU、外设等），特别是 不允许多个进程并发运行，这 是不容忽视的缺点。CP/M和 DOS20以下的版本就是采用 此种方式。 104.2.2固定分区分配n固定分区(fixed partitioning)也叫静态 分区，固定分区存储管理是实现多道 程序设计和分时系统的简单存储管理 技术。如图4-5所示，固定分区就是预 先把内存空间分割成若干个连续区域 ，我们称为分区。每个分区的大小可 以相同也可以不同，但分区大小固定 不变，操作系统占用一个分区，其余 每个分区只能存储一个进程，而且进 程也只能在它所驻留的分区中运行。 固定分区的优缺点n优点：易于实现，开销小，内存分配 和回收算法简单，支持多任务。n缺点：存在内碎片问题，造成内存的 浪费。分区总数固定，限制了并发执 行的进程数目。 114.2.3 动态分区n动态分区分配是根据进程的实际需要动态创建分区， 为之分配连续的存储空间。分区大小正好适合进程的 需要，可谓“量体裁衣”。与固定分区相比较，动态分 区的优点是没有内碎片。但却引入了另一种碎片，即 外碎片。n系统启动后，初始化程序将内存空间分为两个区域： 系统区和用户区。以后每当有进程申请进入，系统就 划出一个大小合适的区域给进程。每当一个进程完成 后，系统就收回该区域。经过一段时间运行，系统就 产生了多个动态分区。这时动态分区的分区分配方式 就是寻找某个空闲分区，其大小需大于或等于进程的 要求。若是大于进程要求，则将该分区分割成两个分 区，其中一个分区为要求的大小并标记为“已分配”， 将该分区分配给进程，而另一个分区为余下部分并标 记为“空闲”。当进程运行完成时，回收进程释放分区 时要考虑一个重要问题，就是将相邻的空闲分区合并 成一个大的空闲分区。121空闲分区链表n每个空闲分区的前后两个单元，放置空闲分区的说明信 息和指针。如图所示，系统设立一个链首指针Free，指 向第一个空闲分区。空闲分区排列需按照一定的规律（ 如按大小、按地址），分配进程可以依照空闲分区链表 ，来查找适合的空闲分区进行分配。132.动态分区的分配算法n首次适应算法n首次适应算法的空闲链是对空闲分区按照地址从低到高的顺序排 列起来。为进程选择分区时总是按地址从低到高搜索，只要找到 可以容纳该进程的空闲区，就把该空闲区切割出进程大小，分配 给该进程，余下的空闲分区仍留在空闲链中。若从链首直至链尾 都不能找到一个能满足要求的分区，则此次内存分配失败返回。n其缺点是低址部分不断被划分，会留下许多难以利用的、很小的 空闲分区（即碎片），而每次查找又都是从低址部分开始，这无 疑会增加查找可用空闲分区链时的开销。 14n循环首次适应算法n循环首次适应算法的空闲链是对空闲分区按照地址从低 到高的顺序排列起来（同上）。每次分区时，总是从上 次查找结束的地方开始，只要找到一个足够大的空闲区 ，就把该空闲区切割出进程大小，分配给该进程，余下 的空闲分区仍留在空闲链中。n该算法能使内存中的空闲分区分布得更均匀，从而减少 了查找空闲分区时的开销，但这样会缺乏大的空闲分区 。15n最佳适应算法n最佳适应算法的空闲链是按空闲区从小到大顺序 排列。为进程选择分区时总是寻找其大小最接近 进程所要求的存储区域。所谓“最佳”是指每次为 进程分配内存时，总是把能满足要求、又是最小 的空闲分区分配给进程，避免“大材小用”。 n因为每次分配后所切割下来的剩余部分总是最小 的，这样将加速碎片的形成。16n最差适应算法n最差适应算法的空闲链是按空闲区从大到小顺序排列。 与最佳适应法相反，它为进程选择存储区时，总是寻找 最大的空白区。最差适应算法可以延缓小空闲区的形成 ，但是无法保留大空闲区。这给以后到达尺寸大的进程 分配内存空间带来了困难。n内存紧缩(compaction)技术 173动态分区内存的分配与回收。n规定不再切割尺寸 大小为size。从空闲 分区链表中找到所 需大小的分区。设 进程请求的尺寸大 小为u.size，空闲分 区的大小可表示为 m.size。若m.size- u.sizesize，说明多 余部分太小，可不 再切割，将整个分 区分配给进程； 18n内存回收 n情况一：前邻空闲区，回收区与插入点的 前一个空闲区F1相邻接。此时应将回收区 与插入点的前一分区合并，不必为回收分 区分配新表项，而只需修改其前一分区Fl 的大小，大小为两者之和。n情况二：前后邻空闲区，回收区同时与插 入点的前空闲区F1和后空闲区F2两个空闲 区邻接。此时将三个分区合并，使用前空 闲区F1的首址作为新空闲区的首址，大小 为三者之和，取消F2的表项。n情况三：后邻空闲区，回收分区与插入点 的后一空闲区F2相邻接。此时也可将两分 区合并，形成新的空闲分区，用回收区的 首址作为新空闲区的首址，大小为两者之 和。n情况四：前后不邻接空闲区，回收区不与 空闲区邻接。这时应为回收区单独建立一 新表项，填写回收区的首址和大小，并根 据其首址插入到空闲链中的适当位置。194.2.6 伙伴系统n其实现原理如下：n一个伙伴系统内存的用户可用空间为2U。进程申请存储空间时， 系统总是为其分配大小为2I的一个空闲分区。其中SIU，2S是 系统允许的最小分区尺寸。在实际操作系统中，最小分区尺寸一 般为212。n如果进程申请的存储空间大小为K，且2I-1K2I，则将整个2I大 小的分区分配给该进程；否则，该分区被分割成两个大小相等的 伙伴分区，大小为2I-1；再判断K是否满足条件：2I-2K2I-1，若 满足条件，则将两个伙伴中的任何一个分配给该进程。否则，将 其中一个伙伴又分成两个大小相等的伙伴分区；此过程一直继续 进行，直到产生的分区满足条件I-JS并2I-J-1K2I-J，将2I-J大小 的分区分配给该进程；当I-J-1S时，系统不再分割成两个大小 相等的伙伴分区，将2S大小的分区分配给该进程。n当进程执行完毕，释放一个尺寸为2I的分区时，系统用下面的算 法回收该分区。n如果被回收空闲分区没有空闲伙伴分区，那么保留该分区为一 个独立的空闲分区，否则执行；n合并回收分区及其伙伴分区，从而得到一个尺寸（2I+1）更大 的回收空闲分区，转移到； 20一个伙伴系统内存分配与回收的例子 21n伙伴系统克服了固定分区和动态分区存储管理技 术的缺陷。但是伙伴系统存在一个问题，即内存 空间需要不断地进行分裂和合并，频繁的伙伴分 区合并操作会浪费很多时间。一种直接的解决方 法是延缓合并，不是在伙伴回收时进行合并，而 是在必要时才进行伙伴合并。n在现代操作系统中，更多地采用分页或分段存储 管理技术，以及虚拟存储技术，但伙伴系统在一 些操作系统中仍然是一种有效的存储管理方法。 随着内存技术的发展，内存容量的不断扩大，伙 伴系统作为存储分配的一种合理有效技术将得到 进一步发展，比较典型的技术是Linux系统采用 的伙伴堆算法，即伙伴系统和分页存储管理技术 相结合,将在本书的Linux系统中讨论。224.3 分页存储管理方式n分页存储管理允许进程的存储空间是离散 的，把进程逻辑地址空间与实际存储空间 分离，增加存储管理的灵活性。将一个进 程分散存储到许多不连续的空间，就可以 避免内存碎片。根据分配时所采用的基本 单位的不同，可将离散分配方式分为以下 三种：分页存储管理、分段存储管理和段 页式存储管理，其中段页式存储管理是前 两种管理方法结合的产物。234.3.1 页与页帧n在分页存储管理方式中，将一个进程的逻辑地址 空间分成若干个大小相等的片，称为页(page)或 页面。每页从0开始依次编号称为页号(page number)。相应地，内存空间也分成与页相同大 小的若干个存储块，称为页帧(page frame)或物 理块。每帧