《计算机操作系统》汤小丹

1、湘 潭 大 学第第5 5章章存储器管理存储器管理5.1 5.1 存储器的层次结构存储器的层次结构主存辅存5.2 5.2 程序的装入和链接程序的装入和链接在多道程序环境下，要运行程序就必须为之创建进程，创建进程的第一件事就是要将程序和数据装入内存。将一个用户源程序变为一个可在内存中执行的程序，通常要经过以下几步：编译。源程序目标模块链接。目标模块，库函数装入模块1) 装入。将装入模块装入内存45.2.1 5.2.1 程序的装入程序的装入 以无须链接的单个目标模块的装入过程为例来讨论。该目标模块也就是装入模块。将一个装入模块装入内存可采用三种方式：绝对装入方式。已知程序在内存的地址，编译产生绝对地

2、址编址的目标代码。由装入程序根据装入模块中的地址，将程序和数据装入内存。可重定位方式。目标代码采用相对地址编址，装入程序根据内存当时的实际使用情况，将装入模块装入到内存的适当地方。动态运行时装入方式。绝对装入方式(Absolute Loading Mode):编译时，若知道程序将驻留在内存的某位置，则编译程序将产生绝对地址的目标代码，绝对装入程序按照装入模块的地址，将程序和数据直接装入指定内存。该地址既可在编译和汇编时给出，也可以由程序员直接赋予。程序员直接给出绝对地址，使得程序修改时很可能要修改所有地址。因此宁可在程序中采用符号地址，在编译时再去转换成绝对地址。单道程序环境下，可用此种方式。

3、而在多道程序环境下，目标模块的起始地址通常从0开始，程序中的其他地址，都相对于起始地址计算。这样的模块称为相对装入模块。程序程序JUMP iJUMP iLOAD jLOAD jDATADATAJUMP 400LOAD 1200JUMP 1424LOAD 2224符号地址绝对地址相对地址i ij j1024102414241424222422240 040040012001200图图4-1 4-1 绝对绝对和可重定位装入模和可重定位装入模块块（a）目标模块（b）绝对装入模块（c）相对装入模块 可重定位装入方式(Relocatable loading mode): 把在装入时对目标程序中的指令和数

4、据地址的修改过程称为重定位。 对于相对装入模块，应采用可重定位装入方式来把装入模块装入内存。 装入相对装入模块时，装入程序要将模块的起始地址与内存某位置的地址相加，才能将模块定位到正确的物理地址，同样，模块中的指令地址和数据地址都要相应修改。 因地址变换只是在装入时一次完成，以后不再改变，故称为静态重定位。LOAD 1,2500365 0 1000 2500 5000作业地址空间LOAD 1,12500365 10000 12500 15000内存空间图4-2 作业装入内存时的情况 90009程序的装入（程序的装入（3 3）动态运行时装入(Dynamic Run-Time loading):多

5、道程序环境下，程序在内存的位置可能要经常改变，如进程的换入换出，每次换入到内存的位置一般是不同的，这样，就应采用动态运行时的装入方式。 动态运行时的装入程序，把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是等到程序真正要执行时才进行地址转换。因此，装入内存后的所有地址仍是相对地址。为使地址转换不影响指令的执行速度，这种方式需要一定的特殊硬件的支持。5.2.2 5.2.2 程序的链接程序的链接 实现链接的方法有三种：静态链接、装入时动态链接和运行时动态链接。一、静态链接：模块A CALL B:RETURN模块B CALL C:RETURN模块C RETURN模块A JSR

6、 “L”RETURN模块B JSR “L+M”RETURN模块C RETURN0L-10M-10N-10L-1LL+M-1L+ML+M+N-1需要解需要解决决的的两个问题两个问题：1 1、对对相相对对地地址址进进行修改行修改2 2、变换变换外部外部调调用符用符号号目标模块装入模块二、装入时动态链接(Load-Time Dynamic linking):是在目标模块装入内存时，边装入边链接。即在装入一个目标模块时，若发现一个外部模块调用，即引起装入程序去找出相应的外部模块，并将它装入内存以及修改目标模块中的相对地址。其优点有：1、便于软件版本的修改和更新。2、便于实现目标模块共享。三、运行时动态

7、链接(Run-Time Dynamic linking): 这种链接方式，可将某些目标模块的链接，推迟到执行时才进行。即在执行过程中，若发现一个被调用模块尚未装入内存时，由OS去找到该模块，将它装入内存，并把它链接到调用者模块上。 前述的动态装入方式，可将装入模块装入到内存的任何位置。但装入模块的结构是静态的，这里的静态是指：一，在进程的整个执行期间，模块是不改变的；二，每次运行时的装入模块都是相同的。而实际上，每次要运行的模块可能是不同的，但装入时只能将所有可能要运行的模块全部链接在一起，使每次执行时的装入模块是相同的。5.3 5.3 连续分配存储管理方式连续分配存储管理方式 连续分配是指为

8、一个用户程序分配一个连续的内存空间。连续分配方式可分为：单连续分配；固定分区分配；动态分区分配；基于顺序搜索的分区分配；基于索引搜索的分区分配；可重定位分区分配。5.3.1 5.3.1 单一连续分配单一连续分配 内存中仅驻留一道程序，整个用户区为一个用户独占。 最简单的一种存储管理方式，只能用于单用户、单任务的OS中。这种管理方式将内存分为：系统区。仅供OS使用，通常为内存的低址部分。 用户区。除系统区以外的内存空间，供用户使用。5.3.2 5.3.2 固定分区分配固定分区分配 固定分区分配是将内存空间划分为若干固定大小的区域，每个区域中可以装入一道作业。划分分区的方法：其方法有两种。分区大小

9、相同。分区大小不同。是将内存划分出多个较小的分区，适量的中等分区和少量的大分区。1. 内存分配：为便于内存分配，通常按分区的大小排队，并建立一张分区使用表。表中记录了各分区的起始地址、大小和状态。当一用户程序要装入时，由内存分配程序检索该表，从表中找出一尚未分配且大小能满足要求的分区，分配给该程序，然后修改表中的状态项，否则拒绝为该程序分配内存。165.3.3 5.3.3 动态分区分配动态分区分配 动态分区分配是根据进程的实际需要，动态地为之分配连续的内存空间。实现这种存储管理方式，必须解决三问题：一、分区分配中的数据结构：常用来记录内存使用情况的数据结构形式有：1、空闲分区表：每个表项记录一

10、个尚未分配出去的分区。2、空闲分区链：在每个分区的头尾设置一些分区分配控制信息和前后向指针，将所有分区链接成一个双向链。分区分配出去后，改变状态位，这时前后向指针已无意义。序号分区大小（KB）始址KB状态16444可用224132可用340210可用4前向指针后向指针N+20N+20N个字节可用三、分区分配操作：主要的操作是分配和回收内存。1、分配内存：首先，系统按照某种分配算法，从空闲链（表）中找到所需的分区，若找到的分区切割成请求的分区的大小后，剩余部分太小，则不切割，将整个分区分配给请求者。否则，从该区中切割出与请求的大小相等的内存空间分配出去，余下部分仍留在链（表）中。最后将分配区的首

11、址返回给调用者。18动态分区分配（动态分区分配（6 6）2、回收内存：当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链找到相应的插入点，此时可能出现以下四种情况之一：（1）回收区与插入点的前一个分区相邻接。（2）回收区与插入点的后一个分区相邻接。（3）回收区同时与前后两个分区邻接。（4）回收区不与前后两个分区邻接。 这时应为回收区单独建立一新表项，填写回收区的大小，并根据其首址，插入到空闲链中的适当位置。图4-7 内存回收时的情况F1回收区回收区F2F1回收区F2合并,不为回收区分配新表项.修改F1区的大小(2)合并,用回收区的首址作为新空闲区的首址,大小为两者之和.(3)三区合并,

12、使用F1的首址取消F2的表项.205.3.4 5.3.4 基于顺序搜索的分区分配算法基于顺序搜索的分区分配算法1、首次适应算法FF:该算法要求分区链以地址递增的次序链接。内存分配时，从链首开始顺序查找，直至找到一个能满足其大小要求的空闲区为止。然后，再按照作业的大小，从该区中划出一块内存分配给请求者，余下的空闲分区仍留在空闲链中。 该算法倾向于优先利用内存中低址部分的空闲区，高址部分的很少利用，从而保留了高址部分的大空闲区，为以后到达的大作业分配大的内存空间创造了条件。但低址部分留下许多难以利用的很小的空闲区 ，每次查找又都从低址部分开始，这样，增加了查找开销。2、循环首次适应算法：由FF算法

13、演变而来，分配内存时，不再每次从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直到找到第一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间。 为实现该算法，应设置一起始查询指针，并采用循环查找方式。该算法能使内存中的空闲分区分布得更均匀，减少查找空闲分区的开销，但这会缺乏大的空闲分区。 3、最佳适应算法：“最佳”的含义是指每次为作业分配内存时，总是把既能满足要求又是最小的空闲分区分配给作业，避免“大材小用”。为加速查询，该算法要求将所有的空闲区按其大小以递增的顺序链接成一空闲区链。这样，第一次找到的满足要求的空闲区，必然是最优的。孤立地看，这似乎是最佳的，但从宏观

14、上看却不一定。因为每次分配后所切割下的剩余部分，总是最小的，在存储器中会留下许多难以利用的小空闲区。 4、最坏适应算法：在扫描整个空闲分区表或链表时，总是挑选一个最大的空闲区，从中分割一部分空间给作业。其策略与最佳适应算法相反。该算法要求将所以空闲分区，按容量从大到小的顺序，形成一空闲分区链，查找时，只要看第一个分区能否满足作业要求即可。5.3.5 5.3.5 基于索引搜索的分区分配算法基于索引搜索的分区分配算法 1、快速适应算法：将空闲分区根据其容量大小进行分类。为每一类分区单独设立一个空闲分区链表，同时在内存中设立一张管理索引表，每个表项对应一种空闲分区类型，并记录空闲分区链表的表头指针。

15、空闲分区的分类是根据进程常用的空间大小进行划分。 该算法在搜索空闲分区时分二步：第一步是根据进程长度从索引表中找到能容纳它的最小空闲区链表；第二步是从链表中取下第一块进行分配。 2、Buddy System Tries to allow a variety of block sizes while avoiding excess fragmentation Blocks generally are of size 2k, for a suitable range of k Initially, all memory is one block of 2U If a request of size

16、 s such that 2U-1 s 2100段号S段长基址1K6K6004K5008K2009200段号0321+82928K82928692有效地址物理地址主存位移量段表寄存器越界四、分页与分段的主要区别：分页和分段系统有许多相似之处，但在概念上二者完全不同：（1）页是信息的物理单位，仅仅是出于系统管理的需要；段是信息的逻辑单位，其目的是满足用户的需要。（2）页的大小固定且由系统确定，一个系统只能有一种大小的页面；段的长度不固定，决定于用户所编写的程序。（3）分页的作业地址空间是一维的；分段的作业地址空间是二维的。五、信息共享：分段系统的一个突出优点是易于实现段的共享。即允许若干个进程共享一个或多个段，而且对段的保护也简单易行。在分页系统中，虽然也能实现共享，但远不如分段系统来得方便。 可重入代码(Reentrant Code)又称为纯代码(Pure code)，是一种允许多个进程同时访问的代码。进程在运行过程中是不允许修改可重入代码的。595.6.4 5.6.4 段页式存储管理方式段页式存储管理方式一、基本原理：段页式