操作系统第四章存储器管理

1、第四章第四章 存储器管理存储器管理本章主要内容本章主要内容 4.1 存储器的层次结构存储器的层次结构 4.2 程序的装入和链接程序的装入和链接 4.3 连续分配方式连续分配方式 4.4 对换对换 4.5 分页存储管理方式分页存储管理方式 4.6 分段存储管理方式分段存储管理方式4.1 存储器的层次结构存储器的层次结构4.1.1 多级存储器结构1.存储器的多层结构2.可执行存储器 寄存器和主存储器又被称为可执行存储器 访问机制不同，所需耗费的时间不同 进程可以在很少的时钟周期内使用一条load或store指令对可执行存储器进行访问 辅存的访问通过I/O 设备来实现，访问中将涉及到访问则中断、设备

2、驱动程序以及物理设备的运行，所需耗费的时间相差3个数量级甚至更多。4.1.2 主存储器与寄存器 1主存储器 主存储器(简称内存或主存)是计算机系统中一个主要部件，用于保存进程运行时的程序和数据，也称可执行存储器 CPU的控制部件只能从主存储器中取得指令和数据，数据能够从主存储器读取并将它们装入到寄存器中，或者相反 主存储器的访问速度远低于CPU执行指令的速度，引入寄存器和高速缓存。 2寄存器 寄存器访问速度最快，完全能与CPU协调工作，但价格却十分昂贵，因此容量不可能做得很大 寄存器用于加速存储器的访问速度，如用寄存器存放操作数，或用作地址寄存器加快地址转换速度等4.1.3 高速缓存和磁盘缓存

3、 1高速缓存 高速缓存是现代计算机结构中的一个重要部件，其容量大于或远大于寄存器，而比内存约小两到三个数量级左右。 根据程序执行的局部性原理，将主存中一些经常访问的信息存放在高速缓存中，减少访问主存储器的次数，可大幅度提高程序执行速度。 进程的程序和数据是存放在主存储器中，每当使用时，被临时复制到一个速度较快的高速缓存中。 当CPU访问一组特定信息时，首先检查它是否在高速缓存中，如果已存在，可直接从中取出使用，以避免访问主存，否则，再从主存中读出信息。2磁盘缓存 由于目前磁盘的I/O 速度远低于对主存的访问速度，因此将频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，可减少访问磁盘的次数。

4、 磁盘缓存本身并不是一种实际存在的存储介质，它依托于固定磁盘，提供对主存储器存储空间的扩充，即利用主存中的存储空间，来暂存从磁盘中读出(或写入)的信息。 主存也可以看做是辅存的高速缓存 一个文件的数据可能出现在存储器层次的不同级别中，例如，一个文件数据通常被存储在辅存中(如硬盘)，当其需要运行或被访问时，就必须调入主存，也可以暂时存放在主存的磁盘高速缓存中。 大容量的辅存常常使用磁盘，磁盘数据经常备份到磁带或可移动磁盘组上，以防止硬盘故障时丢失数据本章主要内容本章主要内容4.1 存储器的层次结构存储器的层次结构4.2 程序的装入和链接程序的装入和链接 4.2 程序的装入和链接程序的装入和链接如

5、何将一个用户源程序变成一个可在内存中执如何将一个用户源程序变成一个可在内存中执行的程序，通常要经过行的程序，通常要经过3步骤：步骤： :由编译程序（由编译程序（Compiler）将用户源代码编）将用户源代码编译成若个译成若个目标模块目标模块 。:由链接程序（由链接程序（Linker）将编译后形成的一）将编译后形成的一组目标模块，以及它们所需要的库函数链接在组目标模块，以及它们所需要的库函数链接在一起，形成一个完整的一起，形成一个完整的装入模块装入模块 。:由装入程序（由装入程序（Loader）将装入模块装入内）将装入模块装入内存。存。 1. 程序的装入程序的装入 (1)绝对装入方式绝对装入方式

6、 如果知道程序将驻留在如果知道程序将驻留在内存内存的什么位置，那么，的什么位置，那么，将产生将产生绝对绝对地址的目标代码。地址的目标代码。 按照装入模块中的地址，将程序和按照装入模块中的地址，将程序和数据装入内存。数据装入内存。 由于程序中的由于程序中的 (2)可重定位装入方式可重定位装入方式 由装入程序将装入模块装入内存后，装入模块中由装入程序将装入模块装入内存后，装入模块中程序所访问的所有程序所访问的所有逻辑地址逻辑地址与实际装入内存的与实际装入内存的物物理地址理地址不同不同 ，必须进行变换。，必须进行变换。把在把在装入装入时对目标程序中指令和数据的变换过程时对目标程序中指令和数据的变换过

7、程称为重定位。称为重定位。 因为地址变换是在因为地址变换是在装入装入时一次完成的，以后不再时一次完成的，以后不再改变，故称为改变，故称为。 采用采用静态静态重定位方法将程序装入内存重定位方法将程序装入内存,称为称为 装入程序将目标模块装入内存后，并不立即把装入程序将目标模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序执行时进行把这种地址转换推迟到程序执行时进行，在硬，在硬件地址变换机构的支持下，随着对每条指令或件地址变换机构的支持下，随着对每条指令或数据的访问自动进行地址变换，故称为数据的访问自动进行地址变换，故

8、称为2. 程序的链接程序的链接 源程序经过编译后，得到一组目标模块，再利源程序经过编译后，得到一组目标模块，再利用链接程序将其链接形成装入模块。用链接程序将其链接形成装入模块。，可把链接分成如下三种：，可把链接分成如下三种：。在程序。在程序运行运行之前，先将各目之前，先将各目标模块及它们所需的库函数，链接成一个完整标模块及它们所需的库函数，链接成一个完整的装配模块（又称执行模块），以后不再拆开。的装配模块（又称执行模块），以后不再拆开。 事先进行链接的方式称为静态链接方式。事先进行链接的方式称为静态链接方式。模块 ACALL B；Return；0L1模块 BCALL C；Return；0M1模

9、块 CReturn；0N10模块 AJSR“L”Return；L1模块 BJSR“LM”Return；LLM1LMLMN1模块 CReturn；(a) 目标模块(b) 装入模块对相对地址进行修改对相对地址进行修改 目标模块中，使用的都是相对地址，其目标模块中，使用的都是相对地址，其起始地址都为起始地址都为0，在链接成一个装入模块时，在链接成一个装入模块时修改模块的相对地址。修改模块的相对地址。 如把原如把原B中的所有相对地址都加上中的所有相对地址都加上L，把，把原原C中所有相对地址都加上中所有相对地址都加上LM。变换外部引用地址变换外部引用地址 将每个模块中所用的外部调用符号也都将每个模块中所

10、用的外部调用符号也都变换为相对地址。例如将变换为相对地址。例如将call B 变换为变换为JSR “L”是指将用户源程序编译后所得到的一组目标是指将用户源程序编译后所得到的一组目标模块，在装入内存时，采用模块，在装入内存时，采用边装入边链接边装入边链接的链接的链接方式。方式。 在装入一个目标模块时，若发生一个外部模块在装入一个目标模块时，若发生一个外部模块调用事件，将引起装入程序去找出相应的外部目调用事件，将引起装入程序去找出相应的外部目标模块，并将它装入内存标模块，并将它装入内存 即即分别装入各模块，并且在装入的过程中修改分别装入各模块，并且在装入的过程中修改相对地址和外部引用地址。相对地址

11、和外部引用地址。 便于修改和更新便于修改和更新 若采用动态链接方式，由于各目标模块是分若采用动态链接方式，由于各目标模块是分开存放的，所以要修改或更新各目标模块，是件开存放的，所以要修改或更新各目标模块，是件非常容易的事。非常容易的事。便于实现对目标模块的共享便于实现对目标模块的共享 在采用装入时动态链接方式时，在采用装入时动态链接方式时，OS则很容易则很容易将一个目标模块链接到几个应用模块上，实现多将一个目标模块链接到几个应用模块上，实现多个应用程序对该模块的共享。个应用程序对该模块的共享。 各模块被独立装入系统，而且也不进行链接，各模块被独立装入系统，而且也不进行链接，运运行时行时发现引用

12、的地址是相对地址或者外部地址时，发现引用的地址是相对地址或者外部地址时，才发起链接，寻找正确的引用地址。才发起链接，寻找正确的引用地址。：凡在执行过程中未被用到的目标模块，都：凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空可加快程序的装入过程，而且可节省大量的内存空间。间。该方法是目前最常使用的链接方式。该方法是目前最常使用的链接方式。本章主要内容本章主要内容 4.1 存储器的层次结构存储器的层次结构 4.2 程序的装入和链接程序的装入和链接 4.3 连续分配方式连续分配方

13、式4.3 连续分配方式连续分配方式连续分配方式，是指连续分配方式，是指为一个用户程序分配为一个用户程序分配一个连续的内存空间一个连续的内存空间。 连续分配方式有四种：连续分配方式有四种：单一连续分配单一连续分配固定分区分配固定分区分配动态分区分配动态分区分配1. 可重定位分区分配可重定位分区分配(汤子瀛汤子瀛)4.3.1 单一连续分配单一连续分配 这是最早、最简单的一种存储分配方式。这是最早、最简单的一种存储分配方式。它规定它规定整个内存的用户区中只驻留一个用整个内存的用户区中只驻留一个用户的一个程序户的一个程序，因此该方式，因此该方式只适用于单用只适用于单用户、单任务的操作系统户、单任务的操

14、作系统。4.3.1 单一连续分配单一连续分配为了防止为了防止OS的代码和数据被用户进程所破坏，的代码和数据被用户进程所破坏，把内存分为系统区和用户区两部分：把内存分为系统区和用户区两部分：系统区：系统区：仅提供给仅提供给0S使用，通常是放在内存的低使用，通常是放在内存的低址部分；址部分；用户区：用户区：是指除系统区以外的全部内存空间，提是指除系统区以外的全部内存空间，提供给唯一的用户使用，存放用户程序和数据。供给唯一的用户使用，存放用户程序和数据。 1. 优缺点：优缺点：简单、内存利用率低。简单、内存利用率低。4.3.2 分区管理分区管理-固定分区分配固定分区分配固定分区分配思想：固定分区分配

15、思想：将内存用户空间划分为将内存用户空间划分为若干个若干个固定大小固定大小的区域，每个区域称为一个的区域，每个区域称为一个分区（分区（region），在每个分区中只装入），在每个分区中只装入一道一道作业作业 ，从而支持多道程序并发设计。，从而支持多道程序并发设计。 。当程序太小时，会造成内存空。当程序太小时，会造成内存空间的浪费间的浪费 。当程序太大时，一个分区又不足以。当程序太大时，一个分区又不足以装入该程序，致使该程序无法运行。装入该程序，致使该程序无法运行。 。可把内存区划成含有多个较小。可把内存区划成含有多个较小的分区、适量的中等分区及少量的大分区。的分区、适量的中等分区及少量的大分区

16、。 1、如何知道哪些分区可以分配？、如何知道哪些分区可以分配？采用分区描述表记录每个分区的状态信息，如下采用分区描述表记录每个分区的状态信息，如下图所示。图所示。内存分配情况内存分配情况分区分区编号编号大小（大小（KB） 起始地址起始地址（KB）状态状态13030分配分配24060分配分配330100分配分配440130未分配未分配540170分配分配作业作业D空闲分区空闲分区作业作业C作业作业B作业作业A操作系统操作系统03060100130170210分区描述表分区描述表 2、如何分配各分区？、如何分配各分区？当有作业要装入内存时，当有作业要装入内存时，内存分配程序内存分配程序检索分检索分

17、区描述表，从中找出尚未使用的区描述表，从中找出尚未使用的最接近大小最接近大小的分的分区分配给该作业，然后修改分区的状态；如果找区分配给该作业，然后修改分区的状态；如果找不到合适的分区就拒绝为该作业分配内存。不到合适的分区就拒绝为该作业分配内存。当程序运行完成时，系统回收内存资源，并修当程序运行完成时，系统回收内存资源，并修改分区描述表中分区的状态。改分区描述表中分区的状态。4.3.2 分区管理分区管理-固定分区分配固定分区分配 固定分区式分配固定分区式分配 的的优缺点优缺点：可运行多道程：可运行多道程序的存储管理方式序的存储管理方式 。存在。存在“内零头内零头”会造成会造成存储空间的浪费。存储

18、空间的浪费。 内零头内零头在分区内没有利用的部分称为在分区内没有利用的部分称为内零头。内零头。4.3.3 分区管理分区管理-动态分区方式动态分区方式 动态分区分配思想：动态分区分配思想：分区数量和大小都不固分区数量和大小都不固定，根据进程的实际需要，动态地为之分配内定，根据进程的实际需要，动态地为之分配内存空间。存空间。 记录系统中各空闲分区的情况，以便分配时能记录系统中各空闲分区的情况，以便分配时能找到可以分配的空间。找到可以分配的空间。在系统中设置一张空闲分区表，用于记在系统中设置一张空闲分区表，用于记录每个空闲分区的情况（包含空闲分区号、分区大小、录每个空闲分区的情况（包含空闲分区号、分

19、区大小、起始地址）。起始地址）。 。为了实现对空闲分区的分配和链接，为了实现对空闲分区的分配和链接，设置前向指针和后向指针，通过前、后向链接指针将设置前向指针和后向指针，通过前、后向链接指针将所有的空闲分区链接成一个双向链。所有的空闲分区链接成一个双向链。空闲分区链表空闲分区链表前向指针N20N个字节可用后向指针N20(2) 分区分配算法分区分配算法 )：要求要求空闲分空闲分区链以地址递增的次序链接区链以地址递增的次序链接。在分配内存时，。在分配内存时，从链首开始顺序查找，直至找到一个大小能从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止。满足要求的空闲分区为止。为大作业分配大的内

20、存空间创造了为大作业分配大的内存空间创造了条件。低址部分不断被划分，会留下许多难条件。低址部分不断被划分，会留下许多难以利用的、很小的空闲分区。以利用的、很小的空闲分区。 : 将所有的空将所有的空闲分区构成一个循环链表。每次查找时不是闲分区构成一个循环链表。每次查找时不是从头开始，而是从上次结束位置开始。从头开始，而是从上次结束位置开始。能使内存中的空闲分区分布得更均能使内存中的空闲分区分布得更均匀，从而减少了查找空闲分区时的开销，但匀，从而减少了查找空闲分区时的开销，但这样会缺乏大的空闲分区。这样会缺乏大的空闲分区。总是把能满足要求、又是最小的空闲分区分配给作总是把能满足要求、又是最小的空闲

21、分区分配给作业，避免业，避免“大材小用大材小用” 该算法要求将所有的空闲分区按其容量以该算法要求将所有的空闲分区按其容量以从小到从小到大大的顺序形成一空闲分区链。从头开始查找的顺序形成一空闲分区链。从头开始查找，将表中，将表中第一个大于所需求空间大小的空闲区分配给作业第一个大于所需求空间大小的空闲区分配给作业。为大作业分配大的内存空间创造了条件。每为大作业分配大的内存空间创造了条件。每次分配后所切割下来的剩余部分总是最小的，这样，次分配后所切割下来的剩余部分总是最小的，这样，在存储器中会留下许多难以利用的小空闲区。在存储器中会留下许多难以利用的小空闲区。 4.最坏适应算法 与最佳适应算法相反，

22、选择一个最大的空闲区，分割一部分给作业使用，缺乏大的空闲分区。 优点：剩下的空闲区不至于太小，产生碎片的可能性最小，有利于中，小作业； 查找效率很高。 在动态分区存储管理方式中，主要的操作是分配内存和回收内存。 系统应利用某种分配算法，从空闲分区链中找到所需大小的分区。Size 是事先规定的不再切割的剩余分区的大小。（3）分区回收）分区回收 当进程运行完毕释放内存时，需当进程运行完毕释放内存时，需相邻的空闲分区相邻的空闲分区，形成大的分区，称为合并技术。形成大的分区，称为合并技术。 需要合并的情况有如下图所示的三种，不论哪种情况，需要合并的情况有如下图所示的三种，不论哪种情况，只需修改相应的分

23、区信息来完成合并即可。只需修改相应的分区信息来完成合并即可。回收分区前有空闲分区回收分区前有空闲分区 回收分区后有空闲分区回收分区后有空闲分区 回收分区前后都有空闲分区回收分区前后都有空闲分区 4.3.4 动态分区示例动态分区示例-快速适应算法快速适应算法 该算法又称为分类搜索法 空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表 内存中设立一张管理索引表，该表的每一个表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。 空闲分区的分类是根据进程常用的空间大小进行划分，如2 KB、4 KB、8 KB等，对于其它大小的分区，如7 KB这样

24、的空闲区，既可以放在8 KB的链表中，也可以放在一个特殊的空闲区链表中。 优点：查找效率高，仅需要根据进程的长度，寻找到能容纳它的最小空闲区链表，并取下第一块进行分配即可。 进行空闲分区分配时，不会对任何分区产生分割，所以能保留大的分区，满足对大空间的需求，也不会产生内存碎片。 缺点：分区归还主存时算法复杂，系统开销较大。 分配空闲分区时是以进程为单位，一个分区只属于一个进程，因此在为进程所分配的一个分区中，或多或少地存在一定的浪费。空闲分区划分越细，浪费则越严重，整体上会造成可观的存储空间浪费，这是典型的以空间换时间的作法。4.3.5 分区管理分区管理-动态分区示例动态分区示例-伙伴系统伙伴

25、系统 伙伴系统是一种不需要紧凑的动态分区算法。伙伴系统是一种不需要紧凑的动态分区算法。 伙伴系统是内存块管理机制，采用伙伴系统是内存块管理机制，采用二进制数二进制数的方式来分配和回收空间。提高回收空间时的方式来分配和回收空间。提高回收空间时合并空闲分区的速度，合并空闲分区的速度，Linux操作系统使用操作系统使用该算法分配和回收页面块。该算法分配和回收页面块。 优点：分配和回收内存速度快，且不会产生优点：分配和回收内存速度快，且不会产生很多小碎片。很多小碎片。 缺点：内存利用率不高，分配的内存大小为缺点：内存利用率不高，分配的内存大小为2的幂，假如只需要的幂，假如只需要65个页面，也需要分配个

26、页面，也需要分配128个页面的块，从而浪费了个页面的块，从而浪费了63个页面，即个页面，即产生内部碎片。产生内部碎片。4.3.5伙伴系统 伙伴系统规定，无论已分配分区或空闲分区，其大小均为2 的k 次幂，k 为整数， lkm，其中：21 表示分配的最小分区的大小，2m 表示分配的最大分区的大小，通常2m是整个可分配内存的大小。 假设系统的可利用空间容量为2m个字，则系统开始运行时，整个内存区是一个大小为2m的空闲分区。 在系统运行过程中，由于不断的划分，可能会形成若干个不连续的空闲分区， 将这些空闲分区根据分区的大小进行分类，对于每一类具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表。

27、 不同大小的空闲分区形成了k(0km)个空闲分区链表 当需要为进程分配一个长度为n 的存储空间时，首首先先计算一个i 值，使2i-1 越界； 段内地址段长-越界 像分页系统一样，当段表放在内存中时，每要访问一个数据，都须访问两次内存，从而极大地降低了计算机的速率。 解决的方法增设一个联想存储器，用于保存最近常用的段表项。 段比页大，段表项的数目比页表项少，联想存储器也相对较小，便可以显著地减少存取数据的时间 比起没有地址变换的常规存储器的存取速度来仅慢约10%15% 4分页和分段的主要区别 ：（1）页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率。分页仅仅是由

28、于系统管理的需要而不是用户的需要. 段则是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。 （2）页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能有一种大小的页面； 段的长度不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。 （3）分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址； 分段的作业地址空间是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。 4.6.3信息共享 分段系统的一个突出优点，是易

29、于实现段的共享，即允许若干个进程共享一个或多个分段，且对段的保护也十分简单易行。 在分页系统中，实现代码共享应在每个进程的页表中都建立相同个页表项和占用相同的页号。例子 有一个多用户系统，可同时接纳40个用户，他们都执行一个文本编辑程序(Text Editor)。如果文本编辑程序有160 KB的代码和另外40 KB的数据区， 则总共需有 8 MB的内存空间来支持40 个用户。 如果160 KB的代码是可重入的(Reentrant)，则无论是在分页系统还是在分段系统中，该代码都能被共享，在内存中只需保留一份文本编辑程序的副本，此时所需的内存空间仅为 1760 KB(4040+160)，而不是8000 KB。 假定每个页面的大小为 4 KB，那么，160 KB的代码将占用 40 个页面，数据区占 10 个页面。 为实现代码的共享，应在每个进程的页表中都建立40个页表项，它们的物理块号都是21#60#。 在每个进程的页表中，还须为自己的数据区建立页表项，它们的物理块号分别是61#70#、71#80#、81#90#，等等 图4-19 分页系统中共享editor的示意图 图4-20 分段系统中