1、整理第4章存储器管理95191第四章 存储器管理第一节 基本概念1 程序的装入和链接在多道程序环境下，要使程序运行，必须创建进程，而创建进程第一件事就是将程序和数据装入内存。一个用户源程序要变为在内存中可执行的程序，通常要进行以下处理：（1）编译：由编译程序将用户源程序编译成若干个目标模块（2）链接：由链接程序将目标模块和相应的库函数链接成装入模块（3）装入：由装入程序将装入模块装入内存1.1 一些概念 逻辑地址-用户程序经编译后，每个目标模块以0为基地址进行的顺序编址。也就是相对与初始地址的，逻辑地址又称相对地址，相对基地址而言。 物理地址-内存中各物理存储单元的地址从统一的基地址进行的顺序
2、编址。物理地址又称绝对地址，它是数据在内存中的实际存储地址。 地址空间（名空间）：指用户程序使用的全部地址。地址空间中的每个地址单元编号称为逻辑地址（logical address），由于通常逻辑地址都是相对于程序的起始地址的，故又称为相对地址（relative address）。 存储空间：指内存中存储数据的物理单元的集合。这些物理单元的集合称为物理地址（physical address）或绝对地址（absolute address）。 重定位：当作业的地址空间与存储空间不一致时，所进行的地址调整以便使作业能够执行的过程称为重定位。重定位实质是地址变换，即作业地址空间中的逻辑地址变换为主存空
3、间的物理地址。根据地址变换进行的时间及采用技术手段不同，可分为静态重定位和动态重定位两类。1.2 程序的装入将装入模块装入内存时。可以有以下装入方式。1.2.1 绝对装入方式思想:编译时，若知道程序将驻留内存的什么位置，则编译程序将产生绝对地址的目标代码，链接得到装入模块。绝对装入程序按照装入模块中的地址，将程序和数据装入内存。装入模块被装入内存后，由于程序中的逻辑地址与实际内存地址完全相同，因此不用对程序和数据进行修改。适用：单道程序环境1.2.2重定位装入方式基本思想：在多道环境下，不可能预知程序应该放在内存的哪个位置，装入程序在装入时根据内存的实际情况把相对地址（逻辑地址）转换为绝对地址
4、，装入到适当的位置。（在装入时进行地址转换）静态重定位。适用：用于多道程序环境。课本例子见下图P1041.2.3动态运行时装入方式（动态重定位的装入方式）思想：在把装入模块装入内存后，并不立即进行地址转换，而是把相对地址到绝对地址的的地址转换推迟到程序真正开始运行的时候再进行。需要一个重定位寄存器支持。其本质就是在程序运行的过程中进行地址转换。适用：多道环境中程序在内存中改变位置。1.2.4 三种装入方式的对比绝对装入方式只能将装入模块装入到内存中事先指定的位置，在多道程序环境下是不可能事先知道每一道程序在内存中的位置的，因此这种装入方式只能用于单道程序环境。地址转换时机：程序中所使用的绝对地
5、址，既可在编译或汇编时给出，也可由程序员直接赋予。适用于单道 环境。可重定位装入方式可将装入模块装入到内存中任何允许的位置，故可用于多道程序环境；然而它不允许程序在运行中移动位置。地址转换时机发生于程序装入内存时发生。适用于动态运行时装入方式允许程序在运行中移动位置，需要特殊硬件的支持。地址转换时机发生于程序运行时。适用于1.2 程序的链接由链接程序将目标模块和相应的库函数链接成装入模块。按照链接时间不同分为三种：1.2.1 静态链接方式思想：我们常说静态链接实在生成可执行文件时进行的。是一种事先链接方式，即在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装入模块(执行文件)
6、，以后不再拆开。实现静态链接应解决的问题：（1）相对地址的修改。每个模块中所有相对地址的修改。比如，原起始地址为0，现在为L。则模块中所有相对地址都要加L。（2）变换外部调用符号。每个模块中所用的外部调用符号也都要变换。存在问题：（1）不便于对目标模块的修改和更新（2）无法实现对目标模块的共享如图1.2.2 动态链接在装入或运行时进行链接。通常被链接的共享代码称为动态链接库(DLL, Dynamic-Link Library)或共享库(shared library)。优点 共享：多个进程可以共用一个DLL，节省内存，减少文件交换。 部分装入：一个进程可以将多种操作分散在不同的DLL中实现，而只
7、将当前操作相应的DLL装入内存。 便于局部代码修改：即便于代码升级和代码重用；只要函数的接口参数（输入和输出）不变，则修改函数及其DLL，无需对可执行文件重新编译或链接。 便于运行环境适应：调用不同的DLL，就可以适应多种使用环境和提供不同功能。如：不同的显示卡只需厂商为其提供特定的DLL，而OS和应用程序不必修改。1.2.2.1 装入时动态链接思想：指将一组目标模块在装入内存时，边装入边链接的方式。具有便于修改和更新、便于实现对目标模块的共享。存在问题： 由于程序运行所有可能用的目标模块在装入时均全部链接在一起，所以将会把一些不会运行的目标模块也链接进去。如程序中的错误处理模块1.2.2.2
8、 运行时动态链接思想：在程序运行中需要某些目标模块时，才对它们进行链接的方式。具有高效且节省内存空间的优点。第二节 连续分配方式1 单一连续分配（单独分区分配）最简单的一种存储管理方式，但只能用于单用户、单任务的OS中。概念：单一连续分配就是整个主存区域的用户空间均归一个用户作业使用。存储管理方法：将内存分为系统区（内存低端，分配给OS用）和用户区（内存高端，分配给用户用）。其中用户区是指除了系统区外的内存空间，提供给用户程序使用。采用静态分配方式，即作业一旦进入内存，就要等待它运行结束后才能释放内存。主要特点：管理简单，只需小量的软件和硬件支持，便于用户了解和使用。但因内存中只装入一道作业运
9、行，内存空间浪费大，各类资源的利用率也不高。例子：一个容量为256KB的内存，操作系统占用32KB，剩下224KB全部分配给用户作业，如果一个作业仅需64KB，那么就有160KB的存储空间被浪费。2 固定分区分配分区分配方式是满足多道程序设计需要的一种最简单的存储管理方法。2.1 思想：将内存分成若干个分区（大小相等/不相等），除OS占一区外，其余的每一个分区容纳一个用户程序。这样来实现多道并发。2.2 分区划分方法：分区大小相等，分区大小不等。但事先必须确定，在运行时不能改变。即分区大小及边界在运行时不能改变。2.3 内存分配：首先：要先建立一张分区说明表或使用表，以记录分区号、分区大小、分
10、区的起始地址及状态（已分配或未分配）。其次：当某个用户程序要装入内存时，由内存分配程序检索分区说明表，从表中找出一个满足要求的尚未分配的分区分配该程序，同时修改说明表中相应分区的状态；若找不到大小足够的分区，则拒绝为该程序分配内存。第三：当程序执行完毕，释放占用的分区，管理程序将修改说明表中相应分区的状态为未分配，实现内存资源的回收。2.4 特点主要特点：管理简单，但因作业的大小并不一定与某个分区大小相等，从而使一部分存储空间被浪费。所以主存的利用率不高3 动态分区分配3.1 基本思想：根据进程的实际需要，动态的为其分配内存空间。因此分区大小是动态可变的，分区的个数也是可变的。3.2 主要特点
11、管理简单，只需小量的软件和硬件支持，便于用户了解和使用。进程的大小与某个分区大小相等，从而主存的利用率有所提高。3.3 分区分配的数据结构为描述空闲分区合已分配的分区，引入如下数据结构。3.3.1 空闲分区表用于记录每个空闲分区的情况。每个空闲分区占一个表目，表目重含有分区序号，分区起始地址，分区大小等数据项。如下图3.3.2 空闲分区链用链头指针将系统中的空闲分区链接起来，构成空闲分区链。每个空闲分区的起始部分存放相应的控制信息(如大小,指向下一空闲分区的指针等).就是在分区头设置一个前向指针，分区尾部设置一个后向指针，这样把所有空闲分区连起来。3.4 分区分配算法把一个新作业装入内存，须按
12、照一定的分配算法，从空闲分区表或空闲分区链中选择一合适分区分配给该作业。有下面三种分配算法：3.4.1 首次适应算法算法过程：算法要求空闲分区（链）按地址递增的次序排列。在进行内存分配时,从空闲分区表/链首开始顺序查找,直到找到第一个满足其大小要求的空闲分区为止。然后再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲分区表（链）中。算法的特点 优先利用内存低地址部分的空闲分区,从而保留了高地址部分的大空闲区。但由于低地址部分不断被划分,致使低地址端留下许多难以利用的很小的空闲分区(碎片或零头),而每次查找又都是从低地址部分开始,这无疑增加了查找可用空闲分区的开销。
13、3.4.2 循环首次适应算法算法过程：由首次适应算法发展而来，每次为进程分配内存空间时，不是从链首开始，而是从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个满足要求的空闲分区。该算法要设置一个起始查寻指针。用于标识下一次起始查寻的空闲分区。算法特点 使存储空间的利用更加均衡，不致使小的空闲区集中在存储区的一端，但这会导致缺乏大的空闲分区。3.4.3 最佳适应算法算法过程：算法要求空闲分区表/链按容量大小递增的次序排列。在进行内存分配时，从空闲分区表/链的首开始顺序查找，直到找到第一个满足其大小要求的空闲分区为止。按这种方式为作业分配内存，就能把既满足作业要求又与作业大小最接近的空闲分
14、区分配给作业。如果该空闲分区大于作业的大小，则与首次适应算法相同，将剩余空闲分区仍留在空闲分区表/链中。算法特点 若存在与作业大小一致的空闲分区,则它必然被选中，若不存在与作业大小一致的空闲分区，则只划分比作业稍大的空闲分区，,从而保留了大的空闲分区,但空闲区一般不可能正好和它申请的内存空间大小一样,因而将其分割成两部分时,往往使剩下的空闲区非常小,从而在存储器中留下许多难以利用的小空闲区（碎片或零头）。3.5 分区分配操作这里所谓的操作是：分配内存和回收内存。3.5.1 分配内存操作实际上是分区的分割。具体过程如下：设请求的分区大小为u.size，空闲分区的大小为m.size,若m.size
15、-u.sizesize(size是事先规定的不再切割的剩余分区的大小)，说明多余部分太小，可不再切割，将整个分区分配给请求者；否则,即多余部分超过size，从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分区表/链中，然后，将分配区的首址返回给调用者。分配流程图：3.5.2 回收内存操作 基本过程：当作业执行结束时，应回收已使用完毕的分区。系统根据回收分区的大小及首地址，在空闲分区表中检查是否有邻接的空闲分区，如有，则合成为一个大的空闲分区，然后修改有关的分区状态信息。回收分区与已有空闲分区的相邻情况有以下四种： 1）回收分区上邻接一个空闲分区,合并后首地址为空闲分区的首
16、地址,大小为二者之和。 2）回收分区下邻接一个空闲分区,合并后首地址为回收分区的首地址,大小为二者之和。 3）回收分区上下邻接空闲分区,合并后首地址为上空闲分区的首地址,大小为三者之和。 4）回收分区不邻接空闲分区，这时在空闲分区表中新建一表项，并填写分区大小等信息，并根据其首地址插入到空闲链的适当位置。如下图：4 可重定位分区分配4.1 动态重定位的引入在连续分配方式中，我们必须把一个系统或用户程序装入一个连续的内存空间。但是，如果在系统中只有一些小分区并且这些分区不相邻链接，即使它们的相加之后的空间大于要装入的程序，也不可能把程序装入这些内存中。这些小分区就叫做“零头”或“碎片”。处理思路
17、“紧凑”：将内存中的所有作业移动到内存的另一端，使它们全部相邻。这样，就可以把原来分散的多个小分区拼接成一个大分区，这时就可把作业装入了。称为“紧凑”或“拼接”。出现问题：紧凑后，明显可以看出内存中的数据和程度的存放位置发生了变化，如果不对程序和数据的地址加以更改，则程序不能运行，因此我们需要重定位。也就是说在每次紧凑之后需要重定位。4.2 动态重定位的实现引入重定位寄存器，程序在执行时，真正访问的内存地址是相对地址和重定位寄存器中的地址相加后的地址。见课本图p111动态重定位：地址变换过程是在程序执行期间，随着对每条指令或数据的访问时才进行的。因此称为动态重定位。4.3 动态重定位分区分配算
18、法和动态分区分配算法基本相同，只是增加了紧凑功能。算法流程如下：5 对换 了解多道程序环境下，会出现某些进程未执行而占据内存空间，而大量的作业在外存而不能进入内存执行。为了充分的利用内存空间，我们引入了覆盖和对换。覆盖是早期的操作系统中运用，有兴趣的同学了解一下对换：将暂时不用的某个进程及数据（首先是处于阻塞状态优先级最低的，根据系统的采用算法决定）部分（或全部）从内存移到到外存（备份区或对换区，采用连续分配的动态存储管理方式）中去，让出内存空间，同时将某个需要的进程调入到内存中，让其运行。交换到外存的进程需要时可以被再次交换回（选择换出时间最久的，也是根据系统采用的算法决定）内存中继续执行。
19、这种内存扩充技术就是交换技术。6 覆盖6.1 引入：覆盖实现了在较小的可用内存中运行较大的程序。常用于多道程序系统，与分区存储管理配合使用。6.2 原理：一个程序的几个代码段或数据段，按照时间先后来占用公共的内存空间。 将程序的必要部分（常用功能）的代码和数据常驻内存； 可选部分（不常用功能）在其他程序模块中实现，平时存放在外存中（覆盖文件），在需要用到时才装入到内存； 不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖。(即不同时用的模块可共用一个分区)覆盖示例如下：第三节 基本分页存储管理方式1 基本概念概念：在分页式存储管理方式中，如果不具备页面对换功能，不支持虚拟存储器功能，在调
20、度作业运行时，必须将它的所有页面一次调入内存，若内存没有足够的块，则作业等待，则称为纯分页或基本的分页存储管理方式。1.1 基本思想就是先划分在装块。 空间划分：（1）地址空间的划分：将一个用户进程的逻辑地址空间划分成若干个大小相等的区域，称为页或页面,并将各页从0开始编号。（2）物理空间的划分：内存空间也分成若干个与页大小相等的区域，称为（存储、物理）块或页框（frame），同样从0开始编号。 内存分配：在为进程分配内存时,以块为单位,将进程中若干页装入到多个不相邻的块中,最后一页常装不满一块而出现页内碎片。注：需要CPU的硬件支持（地址变换机构）。1.2 页面页面的概念前面提到了。若页面较
21、小： 减少页内碎片和内存碎片的总空间，有利于提高内存利用率。 每个进程页面数增多，从而使页表长增加，占用内存就较大。 页面换进换出速度将降低。 若页面较大： 每个进程页面数减少，页表长度减少，占用内存就较小。 页面换进换出速度将提高。 会增加页内碎片不利于提高内存利用率。页面大小-选择适中，通常为2的幂，一般在512B-8KB之间。分页地址的地址结构-如下图：页面的大小其实由位移量来确定。课本P131有计算公式，可以看一下。1.3 页表1.3.1 什么是页表记录页号到物理块号之间的对应关系，映射的映射表就是页表，1.3.2 页表的作用就是实现从进程的页号到内存物理块号的地址映射。如图示1.3.
22、3 页表的性质 记录了页面在内存中对应的块号。 页表一般存放在内存中。 访问一个字节的数据/指令需访问内存2次(页表一次,内存一次),所以出现内存访问速度降低的问题。 一般分页系统中，常在页表中设置一个存取控制字段，用于标识对该存储块的内容保护也就是存取权限。表示允许读/写，只读等等。2 地址变换机构引入：由于由页号到物理块号，页内地址到块内地址都是将逻辑地址，变换为内存空间的物理地址，因此在系统中必须设置地址变换机构。2.1 地址变换机构的基本任务实现逻辑地址向物理地址的转换（由页号-块号）。由于，页表就是实现从页号到物理块号的变换，因此地址变换借助页表来完成。2.2 基本地址变换机构过程描
23、述：页表驻留在内存。系统中设置一个页表寄存器PTR，在其中存放页表在内存的起始地址和页表的长度。进程未执行时，页表的起始地址和页表长度存放再本进程的PCB中，当该进程被调度时，这两个数据装入页表寄存器。当进程执行时要访问某个逻辑地址中的数据时，地址变换机构会自动把逻辑地址分为页号和页内地址两部分。用页号为索引来检索页表。先将页号和页表长度比较，若页号大于等于页表长度，则表示本次所访问的地址超过进程的地址空间，越界错误中断。若无，则将页表起始地址与页号和页表项长度的乘积相加，便得到该表项再页表中的位置，由此可找到该页的物理块号。同时页内地址送入物理地址寄存器的块内地址字段中。这样便完成了逻辑地址
24、到物理地址的转换。如下图例1： 若在一分页存储管理系统中，某作业的页表如表所示，已知页面大小为1024B，试将逻辑地址1011，2148，5012转化为相应的物理地址？画出其地址转换图。页号块号02132136解：分析：页面大小是1024B,即1M，可知页面是10bit.由题知逻辑地址为： 物理地址为：（1）逻辑地址1011（十进制）的二进制表示为 00 1111110011 由此可知逻辑地址1011的页号0，查页表知该页放在第2物理块中，其物理地址的二进制表示为 010 * 所以逻辑地址1011对应的物理地址为0BF3H.其地址转换图如后所示。 （2）略 （3）逻辑地址5012（十进制）的二
25、进制表示为：100 1110010100 可知该逻辑地址的页号为4，查页表知该页为不合法页，则产生越界中断。2.3 具有快表的地址变换机构2.3.1 引入基本的地址变换机构存在的问题是CPU每次存取一个数据时，需要访问内存两次，一次是访问内存中的页表，最终得到物理地址，第二次才是真正的访问数据。因此降低了速度。因此为了提高地址变换速度，我们引入了“快表”。2.3.2 基本原理快表就是一个高速缓冲存储器，存放当前访问的那些页表项，也就是快表中存放的是部分页表。CPU产生的逻辑地址的页首先在快表中寻找，若找到（命中），就找出其对应的物理块；若未找到（未命中），再到内存的页表中找其对应的物理块，之后
26、还要修改当前快表，把这个页表项添加到快表中。图见课本p133若快表中内容满，则按某种算法淘汰某些页。2.4 两级和多级页表2.4.1 引言当一个计算机系统的逻辑地址空间非常大。则页表就会很大，要占用大的内存空间，而且要采用连续存储方式。这实际上是没法满足的。因此我们提出两个解决方法：1、 采用离散分配方式取代找一个大的内存空间来存放页表的问题。2、 只将当前需要的部分页表放在内存，其他页表驻留在磁盘，需要时调入。2.4.2 两级页表采用的是第一种方法，用离散分配方式解决。基本原理：把页表也进行分页，并离散地将各个页面分别存放在不同的物理块中。这样也就需要为离散分配的页表再建一个页表，称之为外层
27、页表，其用于记录页表页面所对应的物理块号。如图示 过程是：利用外层页号（页面页表号），作为外层页表的索引，从中找到指定页表分页的起始地址，再利用内层页号找到指定的页表项，其中含有该页所在的块号，在和页内地址构成实际的内存物理地址。详见P134。2.4.3 多级页表将外层页表再进行分页，也将各外层页表页面离散地存放在不同的物理块中，再利用第2级的外层页表来记录它们之间的对应的关系。逻辑地址：如图第四节 基本分段存储管理方式1 分段存储管理方式的引入为什么要引入分段？分段有哪些优点？我们现在了解一下。1 方便编程： 因为实际编程中，用户作业通常按照逻辑关系分为几个段，每个段都是从0开始编址，并有名
28、字和长度，访问的逻辑地址由段名和段内偏移量决定。此存储管理方式就按逻辑上有联系的段来进行管理，方便编程。2 信息共享： 从上面可以得知，段是信息的逻辑单位，也就是段具有实际的逻辑意义。这和前一讲的“页”完全不同。因此要实现段的共享，就要求存储管理能与用户程序的分段组织方式相适应。3 信息保护： 信息保护同样是对信息的逻辑单位进行保护，因此分段管理方式能有效的实现信息保护。4 动态增长： 实际应用中，某些段（数据段）会不断增长，前面的存储管理方法均难以实现。而分段却可以解决这个问题。5 动态链接： 要求以段为单位。 由此我们理解为什么要引入分段存储管理。2 分段系统的基本原理2.1 空间划分（分
29、段）将用户作业的地址空间依照相应的逻辑信息组的长度来划分若干个段，各段的长度不等。各段有段名（常用段号代替），段内首地址为0。段地址结构如下图：一般我们常见的有代码段、数据段、共享段等等。允许一个作业最长又64个段，每个段最大长度是64kB。2.2 内存分配在为作业分配内存时，也以段为单位，分配一段连续的物理地址空间；段间不必连续。如下图注意：整个作业的逻辑地址空间是二维的，其逻辑地址由段号和段内地址组成。1、 需要CPU的硬件支持（地址变换机构）2.3 段表 概念：系统中为每个进程建立一张段映射表，就是段表。 段表内容：每个段在表中占有一个表项，其中记录了该段在内存中的起始地址（又叫“基址”
30、）和段的长度。段表如下图 存储位置：可以存储于寄存器。但一般存放在内存。 作用：记录了段与内存位置的对应关系 注意：访问一个字节的数据/指令需访问内存2次(段表一次,内存一次),所以也出现内存访问速度降低的问题。利用段表实现地址映射如下图2.4 地址变换机构地址变换过程：系统中设置段表寄存器，用于存放段表起始地址和段表长度TL。在进行地址变换时，系统将逻辑地址中的段号与段表长度TL进行比较。若STL，则访问越界。否则，根据段表的起始地址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内存中的起始地址。再检查段内地址D是否超过该段的段长SL。若超过则越界，否则将该段的基址和段内地址相加，
31、即可得到要访问的内存物理地址。如下图例1：在一个段式存储管理系统中，其段表为： 段号 内存起始地址 段长 0 210 500 1 2350 20 2 100 90 3 1350 590 4 1938 9504302120试求表中逻辑地址对应的物理地址是什么？解：逻辑地址为：段号段内地址逻辑地址 0430对应的物理地址为：210+430=640逻辑地址 2120因为段内地址120段长90，所为该段为非法段。2.5 分页和分段的主要区别3 信息共享与保存3.1共享：分页系统中虽然也能实现程序和数据的共享，但远不如分段系统方便。分段系统的一个突出优点是易于实现段的共享，允许若干个进程共享一个或多个分段，且对段的保护十分简单易行。分段系统中，实现共享只需要
