课件第4章存储器管理

1、12022-3-20第第4章章 存储器管理存储器管理n计算机系统中的存储器可以分为两种：内存储器计算机系统中的存储器可以分为两种：内存储器和辅助存储器。前者可被和辅助存储器。前者可被CPU直接访问，后者不直接访问，后者不能。辅助存储器与能。辅助存储器与CPU之间只能够在输入输出控之间只能够在输入输出控制系统的管理下，进行信息交换。制系统的管理下，进行信息交换。n既然内存储器可被既然内存储器可被CPU直接访问，因此它是计算直接访问，因此它是计算机系统中的一种极为重要的资源。在操作系统中，机系统中的一种极为重要的资源。在操作系统中，把管理内存储器的部分称为把管理内存储器的部分称为“存储器管理存储器

2、管理”。能。能否合理地使用内存，会在很大程度上影响到整个否合理地使用内存，会在很大程度上影响到整个计算机系统的性能。计算机系统的性能。22022-3-20存储器管理的主要任务存储器管理的主要任务 n存储管理的主要任务是尽可能方存储管理的主要任务是尽可能方便用户和提高内存储器的使用效便用户和提高内存储器的使用效率，使内存储器在成本、速度和率，使内存储器在成本、速度和规模之间获得较好的权衡。规模之间获得较好的权衡。 32022-3-204.1存储器的层次结构存储器的层次结构 n多级存储器结构多级存储器结构n一般计算机，存储层次至少应具有三级：最高层为一般计算机，存储层次至少应具有三级：最高层为CP

3、U寄存寄存器，中间为主存，最底层是辅存。较高档计算机中，根据具器，中间为主存，最底层是辅存。较高档计算机中，根据具体功能分为体功能分为6层，如图层，如图4.1寄存器高速缓存主存磁盘缓存磁盘可移动存储介质42022-3-204.1存储器的层次结构存储器的层次结构 n多级存储器结构多级存储器结构n在存储层次中越往上，存储介质的访问速度在存储层次中越往上，存储介质的访问速度越快，价格越高，相对存储容量也越小。寄越快，价格越高，相对存储容量也越小。寄存器、高速缓存、主存储器和磁盘缓存属于存器、高速缓存、主存储器和磁盘缓存属于操作系统存储管理的管辖范畴。操作系统存储管理的管辖范畴。52022-3-204

4、.1存储器的层次结构存储器的层次结构 n主存储器与寄存器主存储器与寄存器 n（1）主存储器（又称内存和主存）是计算机系统）主存储器（又称内存和主存）是计算机系统中一个主要部分，用于保存进程运行时的程序数据。中一个主要部分，用于保存进程运行时的程序数据。CPU本身读取指令和数据与外围设备的数据交换都本身读取指令和数据与外围设备的数据交换都需要通过主存储器。由于主存储器的访问速度远低需要通过主存储器。由于主存储器的访问速度远低于于CPU执行指令的速度，为缓和这一矛盾，计算机执行指令的速度，为缓和这一矛盾，计算机系统中引入了寄存器和高速缓存。系统中引入了寄存器和高速缓存。n（2）寄存器访问速度最快，

5、但价格昂贵。）寄存器访问速度最快，但价格昂贵。62022-3-204.1存储器的层次结构存储器的层次结构 n高速缓存与磁盘缓存高速缓存与磁盘缓存 n（1）高速缓存介于主存与寄存器之间，速度）高速缓存介于主存与寄存器之间，速度比主存快，比寄存器慢，价格比寄存器要低。比主存快，比寄存器慢，价格比寄存器要低。n（2）磁盘缓存用于缓和磁盘的）磁盘缓存用于缓和磁盘的I/O速度远低速度远低于对主存的访问速度的矛盾，磁盘缓存实际于对主存的访问速度的矛盾，磁盘缓存实际上是从主存空间中划出一块区域，用来暂存上是从主存空间中划出一块区域，用来暂存频繁使用的一部分磁盘数据和信息。频繁使用的一部分磁盘数据和信息。72

6、022-3-20习题习题 n在计算机系统存储层次中，属于操作系统存在计算机系统存储层次中，属于操作系统存储管理的管理范畴的有（）。储管理的管理范畴的有（）。n在计算机系统存储层次中，访问速度最快的在计算机系统存储层次中，访问速度最快的是（）。是（）。 A. 高速缓存高速缓存 B. 主存主存 C. 磁盘缓存磁盘缓存 D.寄存器寄存器 n磁盘缓存实际上占用了（）空间。磁盘缓存实际上占用了（）空间。 A.高速缓存高速缓存 B.主存主存 C.磁盘磁盘 D.可移动存可移动存储介质储介质82022-3-204.2 程序的装入与链接程序的装入与链接 n4.2.1程序的装入程序的装入n4.2.2程序的链接程序

7、的链接 92022-3-20程序的装入和链接程序的装入和链接 n在多道程序环境下，要使程序运行，在多道程序环境下，要使程序运行，必须先为之创建进程。而创建进程的必须先为之创建进程。而创建进程的第一件事，就是将程序和数据装入内第一件事，就是将程序和数据装入内存。存。102022-3-20源程序的执行过程源程序的执行过程 n将一个用户源程序变为一个可在内存中执行将一个用户源程序变为一个可在内存中执行的程序，通常要经过编译、链接和装入几个的程序，通常要经过编译、链接和装入几个步骤步骤n（1）编译。由编译程序将用户源代码编译成）编译。由编译程序将用户源代码编译成若干个目标模块。若干个目标模块。n（2）

8、链接。由链接程序将编译后形成的目标）链接。由链接程序将编译后形成的目标模块以及它们所需要的库函数，链接在一起，模块以及它们所需要的库函数，链接在一起，形成一个装入模块。形成一个装入模块。n（3）装入。由装入程序将装入模块装入主存）装入。由装入程序将装入模块装入主存的过程。的过程。112022-3-20源程序的执行过程源程序的执行过程 n通常要经过编译、链接和装入几个步骤通常要经过编译、链接和装入几个步骤库链接程序装入模块装入程序编译程序产生的目标模块第一步第二步第三步内存122022-3-204.1.1程序的装入程序的装入n程序的装入就是把程序装入内存空间。以无需程序的装入就是把程序装入内存空

9、间。以无需进行链接的单目标模块的装入过程为例。进行链接的单目标模块的装入过程为例。n采用采用三种三种方式方式 u（1）绝对装入方式：是由装入程序根据装入模块中）绝对装入方式：是由装入程序根据装入模块中的地址，将程序和数据装入内存。的地址，将程序和数据装入内存。 u（2）可重定位方式）可重定位方式 ：是由装入程序根据内存当前的：是由装入程序根据内存当前的实际使用情况，将装入模块装入到内存适当的地方。实际使用情况，将装入模块装入到内存适当的地方。 u（3）动态运行时装入方式：动态运行时的装入程序，）动态运行时装入方式：动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的在把装入模块

10、装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟相对地址转换为绝对地址，而是把这种地址转换推迟到程序要真正执行时才进行。到程序要真正执行时才进行。 132022-3-20程序的装入程序的装入n绝对装入方式：是由装入程序根据装入模绝对装入方式：是由装入程序根据装入模块中的地址，将程序和数据装入主存块中的地址，将程序和数据装入主存u若知道程序在内存的位置，编译程序将产生若知道程序在内存的位置，编译程序将产生绝对地址目标模块绝对地址目标模块u绝对地址一般由编译程序给出绝对地址一般由编译程序给出u程序被装入内存后，由于程序中的逻辑地址程序被装入内存后，由于程序中的逻辑地

11、址与实际内存地址完全相同，所以不允许改变与实际内存地址完全相同，所以不允许改变程序和数据的地址程序和数据的地址u只适于单道环境只适于单道环境142022-3-20程序的装入程序的装入u绝对装入方式只能将目标模块装入到内绝对装入方式只能将目标模块装入到内存中事先指定的位置。在多道程序环境存中事先指定的位置。在多道程序环境下，编译程序不可能预知所编译的目标下，编译程序不可能预知所编译的目标模块应放在内存的什么地方，因此在多模块应放在内存的什么地方，因此在多道程序环境下，所得到的目标模块的起道程序环境下，所得到的目标模块的起始地址通常是从始地址通常是从0开始的，程序中的其开始的，程序中的其它地址都是

12、相对于起始地址计算的。因它地址都是相对于起始地址计算的。因此采用重定位装入方式。此采用重定位装入方式。152022-3-20程序的装入程序的装入u可重定位方式可重定位方式 ：是由装入程序根据主存当是由装入程序根据主存当前的实际使用情况，将装入模块装入到主存前的实际使用情况，将装入模块装入到主存适当的地方。适当的地方。 F重定位：在装入时对目标程序中指令重定位：在装入时对目标程序中指令和数据的修改过程。会使装入模块中和数据的修改过程。会使装入模块中的所有逻辑地址与实际装入内存的物的所有逻辑地址与实际装入内存的物理地址不同理地址不同162022-3-20程序的装入程序的装入u可重定位方式可重定位方

13、式 ：Load 1,6Add 1,8Store 1,10ABLoad 1,6Add 1,8Store 1,10ABLoad 1,106Add 1,108Store 1,110AB172022-3-20可重定位装入方式可重定位装入方式(Relocation Loading Mode) 图 4-2 作业装入内存时的情况 LOAD 1,2500365LOAD 1,2500365100001100012500150005000250010000作业地址空间内存空间12500182022-3-20程序的装入程序的装入u可重定位方式可重定位方式F把在装入时对目标程序中指令和数据把在装入时对目标程序中指令和

14、数据的修改过程称为重定位的修改过程称为重定位F地址变换通常是在装入时一次完成，地址变换通常是在装入时一次完成，以后不再改变，故称为静态重定位以后不再改变，故称为静态重定位F适于多道环境但不允许程序在内存中适于多道环境但不允许程序在内存中移动移动192022-3-20程序的装入程序的装入u动态运行时装入方式：动态运行时的装动态运行时装入方式：动态运行时的装入程序，在把装入模块装入内存后，并入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到绝对地址，而是把这种地址转换推迟到程序要真正执行时才进行。程序要真正执行时

15、才进行。 F适于多道环境F允许程序移动，如切换F动态重定位F需要特殊硬件支持（重定位寄存器）202022-3-20程序的装入程序的装入u动态运行时装入方式：动态运行时装入方式：LOAD1,25003650100250050002500相对地址10000重定位寄存器LOAD1,250036510000101001250015000作业J处理机一侧 存储器一侧主存212022-3-204.2.2程序的链接程序的链接 n链接程序的功能是将经过编译或汇编后所得到链接程序的功能是将经过编译或汇编后所得到的一组目标模块以及它们所需要的库函数，装的一组目标模块以及它们所需要的库函数，装配成一个完整的装入模块

16、。配成一个完整的装入模块。n实现链接的方法有实现链接的方法有三种三种u静态链接：事先进行链接，以后不再拆开的链接方式静态链接：事先进行链接，以后不再拆开的链接方式u装入时动态链接：用户源程序经编译后所得到的目标装入时动态链接：用户源程序经编译后所得到的目标模块，是在装入内存时，边装入边链接的。模块，是在装入内存时，边装入边链接的。 u运行时动态链接：某些目标模块的链接，是在程序执运行时动态链接：某些目标模块的链接，是在程序执行中需要该（目标）模块时，才对它进行链接行中需要该（目标）模块时，才对它进行链接222022-3-204.2.2程序的链接程序的链接 u静态链接：事先进行链接，以后不再拆开

17、的链接方式静态链接：事先进行链接，以后不再拆开的链接方式 F对相对地址进行修改对相对地址进行修改F变换外部调用符号变换外部调用符号模块 ACALL B；Return；0L1模块 BCALL C；Return；0M1模块 CReturn；0N10模块 AJSR“L”Return；L1模块 BJSR“LM”Return；LLM1LMLMN1模块 CReturn；(a) 目标模块(b) 装入模块JSR：保：保存返回存返回地址，地址，跳转到跳转到新地址新地址232022-3-20程序的链接程序的链接 u装入时动态链接：用户源程序经编译后所得到的目装入时动态链接：用户源程序经编译后所得到的目标模块，是在

18、装入主存时，边装入边链接的。标模块，是在装入主存时，边装入边链接的。 F改变相对地址的方式如方法一F便于修改和更新F便于实现目标模块共享模块 ACALL B；Return；0L1模块 BCALL C；Return；0M1模块 CReturn；0N10模块 AJSR“L”Return；L1模块 BJSR“LM”Return；LLM1LMLMN1模块 CReturn；(a) 目标模块(b) 装入模块模块模块A模块模块B模块模块CACBBACA静态链接静态链接BCA动态链接动态链接242022-3-20程序的链接程序的链接 u运行时动态链接：可将某些目标模运行时动态链接：可将某些目标模块的链接，推迟

19、到执行时才进行。块的链接，推迟到执行时才进行。F便于实现目标模块的修改、更新和共享F加快程序的装入过程 F提高内存利用率252022-3-20练习练习 u静态重定位是在作业的（）中进行静态重定位是在作业的（）中进行的，动态重定位是在作业（）中进的，动态重定位是在作业（）中进程的程的F编译过程F装入过程F修改过程F执行过程262022-3-20练习练习 u把作业装入内存中随即进行地址变把作业装入内存中随即进行地址变换的方式称为（），而在作业执行换的方式称为（），而在作业执行期间期间,当访问到指令或数据时才进行当访问到指令或数据时才进行地址变换的方式称为（）地址变换的方式称为（） 。272022-

20、3-20练习练习 u静态链接是在（）中进行的，而动静态链接是在（）中进行的，而动态链接是在（）或（）中进行的，态链接是在（）或（）中进行的，其中在（）进行链接，可使得内存其中在（）进行链接，可使得内存利用率最高利用率最高F编译某段程序时F装入某段程序时F调用某段程序时F紧凑时F装入程序之前282022-3-204.3连续分配方式连续分配方式 u连续分配方式：为一个用户程序分连续分配方式：为一个用户程序分配一个连续的内存空间配一个连续的内存空间F单一连续分配F固定分区分配 F动态分区分配F动态重定位分区分配292022-3-204.3连续分配方式连续分配方式 u单一连续分配单一连续分配F只能用于

21、单用户，单任务的操作系统。F把内存分为系统区和用户区两部分 F系统区给OS使用，通常在低址部分F用户区给用户使用。在主存中仅驻留一道程序，整个用户区为一用户独占。当用户作业空间大于用户区时，该作业不能装入。302022-3-204.3连续分配方式连续分配方式 u单一连续分配单一连续分配312022-3-204.3连续分配方式连续分配方式 u固定分区分配固定分区分配F将内存中的用户空间划分为若干个固定大小将内存中的用户空间划分为若干个固定大小的区域的区域 F每个分区中只装入一道作业，一个作业也只每个分区中只装入一道作业，一个作业也只能装入一个分区中，这样可以装入多个作业，能装入一个分区中，这样可

22、以装入多个作业，使它们并发执行。当有一个空闲分区时，便使它们并发执行。当有一个空闲分区时，便可从外存的后备队列中，选择一个适当大小可从外存的后备队列中，选择一个适当大小的作业装入该分区；当该作业运行完时，又的作业装入该分区；当该作业运行完时，又可从后备队列中选择另一个作业装入该分区可从后备队列中选择另一个作业装入该分区（分区大小可以相同也可以不同）。（分区大小可以相同也可以不同）。 322022-3-204.3连续分配方式连续分配方式 u固定分区分配固定分区分配F可运行多道程序的存储管理方式可运行多道程序的存储管理方式F要求把作业全部装入主存，且装入一个连续要求把作业全部装入主存，且装入一个连

23、续的存储空间。的存储空间。332022-3-20固定分区分配固定分区分配 u划分分区的方法划分分区的方法F分区大小相等分区大小相等 缺点：缺乏灵活性缺点：缺乏灵活性 可被用于利用一台计算机去控制多个相同可被用于利用一台计算机去控制多个相同对象的场合对象的场合F分区大小不等。分区大小不等。342022-3-20固定分区分配固定分区分配 u内存分配内存分配 为了记录各个分区的基本情况和使用情况，方便主存为了记录各个分区的基本情况和使用情况，方便主存空间的分配与回收操作，设置了一张分区使用表。空间的分配与回收操作，设置了一张分区使用表。分区使用表的内容包括：分区序号、起始地址、大小、分区使用表的内容

24、包括：分区序号、起始地址、大小、状态。状态。状态栏的值为状态栏的值为“0”表示分区空闲，可以装入作业；当表示分区空闲，可以装入作业；当装入作业后，其值改为已分配装入作业后，其值改为已分配352022-3-20固定分区分配固定分区分配 u内存分配内存分配 20图 4-4 固定分区使用表 未未362022-3-20区号 大小 起始地址 状态 0 20K 40K 未分配 1 40K 60K 已分配 2 80K 100K 已分配 3 160K 180K 未分配 4 320K 340K 已分配 ： ： ： ： 作业号 大小 区号 0 55K 2 1 10K 0 2 150K 4 ： ： ： 作业表 内存

25、分区表 OS 作业 1 作业 0 ： ： 作业 2 ： ： ： 0 区 1 区 2 区 5 区 4 区 内存 区号 大小 起始地址 状态 0 20K 40K 未分配 1 40K 60K 已分配 2 80K 100K 已分配 3 160K 180K 未分配 4 320K 340K 已分配 ： ： ： ： 作业号 大小 区号 0 55K 2 1 10K 0 2 150K 4 ： ： ： 作业表 内存分区表 OS 作业 1 作业 0 ： ： 作业 2 ： ： ： 0 区 1 区 2 区 5 区 4 区 内存 固定分区分配固定分区分配描述内存中每一个区描述内存中每一个区域的情况域的情况描述存放于区域中

26、的描述存放于区域中的作业作业 3 3 3区号 大小 起始地址 状态 0 20K 40K 未分配 1 40K 60K 已分配 2 80K 100K 已分配 3 160K 180K 未分配 4 320K 340K 已分配 ： ： ： ： 作业号 大小 区号 0 55K 2 1 10K 0 2 150K 4 ： ： ： 作业表 内存分区表 OS 作业 1 作业 0 ： ： 作业 2 ： ： ： 0 区 1 区 2 区 5 区 4 区 内存 未未已已 将内存空间由小到大划将内存空间由小到大划分为若干个分为若干个位置固定大小不位置固定大小不等等的区域，每个区域可以存的区域，每个区域可以存放一个作业，存放

27、于不同区放一个作业，存放于不同区域的域的作业可以并行作业可以并行。 用户逻辑地址空间依然用户逻辑地址空间依然是一个连续的整体，在作业是一个连续的整体，在作业申请进入内存时申请进入内存时一次性装入一次性装入。 372022-3-20固定分区分配固定分区分配 u内存分配内存分配 例：某系统的内存容量为例：某系统的内存容量为256K256K，操作系统占用低地址的，操作系统占用低地址的20K20K，其余空间划分成其余空间划分成4 4个固定大小的分区。如下图个固定大小的分区。如下图382022-3-20固定分区分配的管理特点固定分区分配的管理特点 n（1）一个作业只能装入一个分区，不能装入两个）一个作业

28、只能装入一个分区，不能装入两个或多个相邻的分区。一个分区只能装入一个作业，或多个相邻的分区。一个分区只能装入一个作业，当分区大小不能满足作业的要求时，该作业暂时不当分区大小不能满足作业的要求时，该作业暂时不能装入。能装入。n（2）通过对）通过对“分区使用表分区使用表”的改写，来实现主存的改写，来实现主存的分配与回收。作业在执行时，不会改变存储区域，的分配与回收。作业在执行时，不会改变存储区域，所以采用静态地址重定位方式。此方法易于实现，所以采用静态地址重定位方式。此方法易于实现，系统开销小。系统开销小。n（3）当分区较大作业较小时，仍然浪费许多主存）当分区较大作业较小时，仍然浪费许多主存空间空

29、间(内零头）。并且分区总数固定，限制了并发执内零头）。并且分区总数固定，限制了并发执行的作业数目。行的作业数目。 392022-3-20固定分区存储管理举例固定分区存储管理举例 n例例u在某系统中采用固定分区分配管理方式，主存分在某系统中采用固定分区分配管理方式，主存分区（单位字节）情况如图所示。现有大小为区（单位字节）情况如图所示。现有大小为1KB、9KB、33KB、121KB的多个作业要求进入主存，的多个作业要求进入主存，试画出它们进入主存后的空间分配情况，并说明试画出它们进入主存后的空间分配情况，并说明主存浪费有多大？主存浪费有多大？ 402022-3-20000 0操作系统操作系统（2

30、0k）作业作业17KB作业作业223KB作业作业331KB作业作业412KB412022-3-20固定分区性能分析固定分区性能分析n在作业大小和出现频率均已知的情况下，固定在作业大小和出现频率均已知的情况下，固定分区是合适的。在这种情况下分区的大小选择分区是合适的。在这种情况下分区的大小选择与作业大小相当，这样内存的使用效率较高与作业大小相当，这样内存的使用效率较高（控制系统）。（控制系统）。n但是若作业的大小和出现的频率不知道时，势但是若作业的大小和出现的频率不知道时，势必造成分区的大小和作业的大小相差甚远，这必造成分区的大小和作业的大小相差甚远，这样就会造成存储空间的浪费，从而影响整个系样

31、就会造成存储空间的浪费，从而影响整个系统的效率。统的效率。 n早期的早期的IBMIBM的的OS/360MFTOS/360MFT（具有固定任务数的多（具有固定任务数的多道程序系统）采用了这种固定分区的方法。道程序系统）采用了这种固定分区的方法。422022-3-204.3.3 动态分区分配动态分区分配n固定分区存储管理中的固定分区存储管理中的“固定固定”有两层含义，有两层含义，一是分区数目固定，一是每个分区的尺寸固定。一是分区数目固定，一是每个分区的尺寸固定。采用这种内存管理技术时，分配出去的分区总可采用这种内存管理技术时，分配出去的分区总可能会有一部分成为内部碎片而浪费掉。究其原因，能会有一部

32、分成为内部碎片而浪费掉。究其原因，是因为进入分区的作业大小，不可能刚好等于该是因为进入分区的作业大小，不可能刚好等于该分区的尺寸。那么能否不事先划分好分区，而是分区的尺寸。那么能否不事先划分好分区，而是按照进入作业的相对地址空间的大小来分配存储，按照进入作业的相对地址空间的大小来分配存储，从而避免固定式分区所产生的存储浪费，这实际从而避免固定式分区所产生的存储浪费，这实际上就是上就是可变分区可变分区（动态分区）（动态分区）存储管理考虑问题存储管理考虑问题的出发点。的出发点。432022-3-20n动态分区存储管理的基本思想是：动态分区存储管理的基本思想是：在作业要求装入内存储器时，如果当在作业

33、要求装入内存储器时，如果当时内存储器中有足够的存储空间满足时内存储器中有足够的存储空间满足该作业的需求，那么就划分出一个与该作业的需求，那么就划分出一个与作业相对地址空间同样大小的分区分作业相对地址空间同样大小的分区分配给它。配给它。442022-3-20452022-3-20n上图是动态分区存储管理思想的示意图。上图是动态分区存储管理思想的示意图。n图图(a)是系统维持的后备作业队列，作业是系统维持的后备作业队列，作业A需要内存需要内存15KB，作业作业B需要需要20KB，作业，作业C需要需要10KB，等等；，等等；n图图(b)表示系统初启时的情形，整个系统里因为没有作业运表示系统初启时的情

34、形，整个系统里因为没有作业运行，因此用户区就是一个空闲分区；行，因此用户区就是一个空闲分区；n图图(c)表示将作业表示将作业A装入内存时，为它划分了一个分区，尺装入内存时，为它划分了一个分区，尺寸为寸为15KB，此时的用户区被分为两个分区，一个是已经分，此时的用户区被分为两个分区，一个是已经分配的，一个是空闲区；配的，一个是空闲区；n图图(d)表示将作业表示将作业B装入内存时，为它划分了一个分区，尺装入内存时，为它划分了一个分区，尺寸为寸为20KB，此时的用户区被分为三个分区；，此时的用户区被分为三个分区；n图图(e) 表示将作业表示将作业C装入内存时，为它划分了一个分区，尺装入内存时，为它划

35、分了一个分区，尺寸为寸为10KB，此时的用户区被分为四个分区。，此时的用户区被分为四个分区。由此可见，动由此可见，动态分区存储管理中的态分区存储管理中的“动态动态”也有两层含义，一是分区的也有两层含义，一是分区的数目随进入作业的多少可变，一是分区的边界划分随作业数目随进入作业的多少可变，一是分区的边界划分随作业的需求可变。的需求可变。462022-3-20n由于实施动态分区存储管理时，分区的划分是按由于实施动态分区存储管理时，分区的划分是按照进入作业的尺寸进行的，因此在这个分区里不照进入作业的尺寸进行的，因此在这个分区里不会出现内部碎片。这就是说，动态分区存储管理会出现内部碎片。这就是说，动态

36、分区存储管理消灭了内部碎片，消灭了内部碎片，不会出现由于内部碎片不会出现由于内部碎片而引起而引起的存储浪费现象。的存储浪费现象。472022-3-20动态分区动态分区 n动态分区存储管理方式是在作业要求装入主动态分区存储管理方式是在作业要求装入主存时，根据作业的大小动态地划分分区，使存时，根据作业的大小动态地划分分区，使分区的大小正好适应作业的要求。各分区的分区的大小正好适应作业的要求。各分区的大小是不定的，主存中分区的数目也是不定大小是不定的，主存中分区的数目也是不定的。的。n动态分区存储管理方式必须解决三个问题：动态分区存储管理方式必须解决三个问题：u一是分区分配中所用的数据结构。一是分区

37、分配中所用的数据结构。u二是分区的分配算法。二是分区的分配算法。u三是分区的分配和回收。三是分区的分配和回收。482022-3-201采用的数据结构采用的数据结构 n为了实现分区分配，系统中必须配置相应为了实现分区分配，系统中必须配置相应的数据结构，用来记录内存的使用情况。的数据结构，用来记录内存的使用情况。比如空闲分区的情况，为作业分配内存空比如空闲分区的情况，为作业分配内存空间提供依据。常用的有空闲分区表和空闲间提供依据。常用的有空闲分区表和空闲分区链。分区链。492022-3-201. 采用的数据结构采用的数据结构 自由分区表 起始地址 大小 作业号 40K 55K 0 95K 10K

38、1 210K 150K 2 ： ： ： 已使用分区表 OS 作业 0 40K 作业 0 作业 2 80 内存 60K 40K 95K 105K 210K 150K 360K 起始地址 大小 105K 40K 150K 60K 360K 80K ： ： 40K 80 60K 自由分区链 根据作业对内存空间根据作业对内存空间的申请来划分主存区的申请来划分主存区域，区域的域，区域的大小可变大小可变、位置可变位置可变、数量也数量也可变可变 描述已被分配的区域描述已被分配的区域 描述内存中的自由区域描述内存中的自由区域 为每一个为每一个自由分区自由分区设置一设置一个个链接链接指针来指向下一个指针来指向下

39、一个自由分区，使所有的自由自由分区，使所有的自由分区形成一个链表分区形成一个链表 1502022-3-201采用的数据结构采用的数据结构 n空闲分区表。记录主存中空闲分区的情况，空闲分区表。记录主存中空闲分区的情况，包括空闲分区序号、起始地址和大小。为包括空闲分区序号、起始地址和大小。为了便于处理，一般情况下空闲分区表中的了便于处理，一般情况下空闲分区表中的空闲分区记录以地址递增的顺序排列。空闲分区记录以地址递增的顺序排列。512022-3-20n空闲分区链空闲分区链在每个分区的起始部分，设置一些用于控制分区分在每个分区的起始部分，设置一些用于控制分区分配的信息，以及用于链接各分区的前向指针，

40、在分配的信息，以及用于链接各分区的前向指针，在分区尾部设置一个后向指针，这样将所有的空闲分区区尾部设置一个后向指针，这样将所有的空闲分区链接成双向链表。也就是说，每个空闲分区中，除链接成双向链表。也就是说，每个空闲分区中，除了存放下一个空闲区起址了存放下一个空闲区起址next外，还存放它的上一外，还存放它的上一个空闲区起址（个空闲区起址（prior）的信息，如图）的信息，如图(a)所示。这样，所示。这样，通过空闲区的双向链表，就可以方便地由通过空闲区的双向链表，就可以方便地由next找到找到一个空闲区的下一个空闲区，也可以由一个空闲区的下一个空闲区，也可以由prior找到一找到一个空闲区的上一

41、个空闲区。个空闲区的上一个空闲区。522022-3-20532022-3-202分区分配算法分区分配算法 n（1）首次适应分配算法（）首次适应分配算法（FF） n（2）循环首次适应分配算法（）循环首次适应分配算法（NF）n（3）最优适应分配算法（）最优适应分配算法（BF） n（4）最坏适应分配算法（）最坏适应分配算法（WF） n（5）快速适应分配算法（）快速适应分配算法（QF）542022-3-20空闲区表或队列的排序空闲区表或队列的排序n按空闲区按空闲区首址首址递增的次序归类组织空闲区表递增的次序归类组织空闲区表或空闲区队列或空闲区队列n按空闲区按空闲区大小大小的递增或递减次序组织空闲区的递

42、增或递减次序组织空闲区表或队列表或队列 552022-3-20(1)(1)首次适应法首次适应法n要求空闲区按要求空闲区按首址递增的次序组织的次序组织空闲区表（队列）。空闲区表（队列）。 562022-3-20n分配：当进程申请大小为分配：当进程申请大小为SIZESIZE的内存时，系的内存时，系统从空闲区链的链首开始查询，直到首次找统从空闲区链的链首开始查询，直到首次找到等于或大于到等于或大于SIZESIZE的空闲区。从该区中划出的空闲区。从该区中划出大小为大小为SIZESIZE的分区分配给进程，余下的部分的分区分配给进程，余下的部分仍作为一个空闲区留在空闲区链中，但要修仍作为一个空闲区留在空闲

43、区链中，但要修改其首址和大小。改其首址和大小。n若找不到满足要求的，则分配失败，返回。若找不到满足要求的，则分配失败，返回。572022-3-20分析分析n注意：每次分配和回收后空闲区链都要按首址递增的次序排序。首次适应法的优点：首次适应法的优点：n这种算法是尽可能地利用低地址空间，从这种算法是尽可能地利用低地址空间，从而保证高地址空间有较大的空闲区。而保证高地址空间有较大的空闲区。 582022-3-20n缺点缺点u容易产生过多的小地址碎片；降低了主存空间容易产生过多的小地址碎片；降低了主存空间利用率。利用率。u每次查找都是从低址开始，增加了查找的开销每次查找都是从低址开始，增加了查找的开销

44、 n改进改进u采用循环首次适应算法。采用循环首次适应算法。 592022-3-20（2 2）循环首次适应算法）循环首次适应算法n不是每次都从链首开始找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲分区。n设置查寻指针；n循环查找方式n使内存中的空闲分区分布得更均匀，减少了查找时的开销，但会缺乏大的空闲分区。602022-3-20（3 3）最佳适应法）最佳适应法n所谓最佳就是每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免大材小用。n要求按空闲区大小从小到大的次序组成空闲区链。612022-3-20n分配：当进程申请一个存储区时，系统从

45、表头开始查找，当找到第一个满足要求的空闲区时，停止查找，并且这个空闲区是最佳的空闲区。n分配和回收后要对空闲区表（队列）重新排分配和回收后要对空闲区表（队列）重新排序。序。622022-3-20分析分析优点：优点：n在系统中若存在一个与申请分区大小相等的空闲区，必定会被选中，而首次适应法则不一定。n若系统中不存在与申请分区大小相等的空闲区，则选中的空闲区是满足要求的最小空闲区，而不致于毁掉较大的空闲区。632022-3-20分析分析缺点：缺点：n空闲区的大小一般与申请分区大小不相等，因此将其一分为二，留下来的空闲区一般情况下是很小的，以致无法使用。随着时间的推移，系统中的小空闲区会越来越多，从

46、而造成存储区的大量浪费。642022-3-20（4 4）最坏适应法）最坏适应法n将作业申请大小与内存中所有未分配区的大小进行比较，直到找到最大的或等于作业空间的区分配给作业。n要求按空闲区大小从大到小的次序组成空闲区链。652022-3-20分析分析优点：优点：n优先使用大的自由空间，在进行分割后剩余空间还可以被使用。缺点：缺点：n大的自由空间无法保留给需要大空间的作业。662022-3-202.分区分配算法分区分配算法20K 80K 60K 40K 120K 20K 25K 60K 40K 120K 20K 80K 60K 40K 120K 20K 80K 5K 40K 120K 20K 8

47、0K 60K 40K 120K 20K 80K 60K 40K 65K 55K 作业空间 （a）最先适应算法 （b）最佳适应算法 （c）最坏适应算法 672022-3-20n对于某一作业序列来说，某种算法能将该作业序列中所有作业安置完毕，那么我们说该算法对这一作业序列是合适的。n对于某一算法而言，如它不能立即满足某一要求，而其它算法却可以满足此要求，则这一算法对该作业序列是不合适的。 682022-3-20举例举例n例1：有作业序列：作业A要求18K；作业B要求25K，作业C要求30K。系统中空闲区按两种算法组成的空闲区队列n经分析可知：最佳适应法对这个作业序列是合适的692022-3-20练

48、习练习n在动态分区式内存管理中，倾向于优先使用低址部分空闲区的算法是（），能使内存空间中空闲区分布得较均匀的算法是（），每次分配时，把既能满足要求，又是最小的空闲区分配给进程的算法是（）。702022-3-20练习练习n最佳适应算法的空白区是（）。A、按大小递减顺序连在一起B、按大小递增顺序连在一起C、按地址由小到大排列D、按地址由大到小排列n在固定分区分配中，每个分区的大小是（）。在固定分区分配中，每个分区的大小是（）。A、相同、相同 B、随作业长度变化、随作业长度变化C、可以不同但预先固定、可以不同但预先固定D、可以不同但根据作业长度固定、可以不同但根据作业长度固定712022-3-20练

49、习练习n某基于动态分区存储管理的计算机，其主存容量为55Mb（初始为空），采用最佳适应分配（Best Fit）算法，分配和释放的顺序为：分配15Mb，分配30Mb，释放15Mb，分配8Mb，分配6Mb，此时主存中最大空闲分区的大小是（） (10年考研) A、7Mb B、9Mb C、10Mb D、15Mbn在以下存储管理方案中，不适用于多道程序设计系统的是（）。A、单用户连续分配 B、固定式分区分配C、可变式分区分配 D、页式存储管理722022-3-20（5 5）快速适应法）快速适应法n将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，这样系统中

50、存在多个空闲分区链表，在内存中设立一张管理索引表，该表的每一个表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。n空闲分区的分类是根据进程常用的空间大小进行划分的。在分配时根据进程的长度，找到能容纳它的最小空闲链表，取下第一块进行分配即可。 732022-3-20分析分析优点：优点：n该算法查找效率高，分配时不对任何分区产生分割，能保留大的分区，满足对大空间的需求。缺点：缺点：n但分区归还时算法复杂，系统开销大，在分配空闲分区时以进程为单位，也有一定的空间浪费。742022-3-20(6)伙伴系统伙伴系统n固定分区和动态分区方式都有不足之处。固固定分区和动态分区方式都有不足之处

51、。固定分区方式限制了活动进程的数目，当进程定分区方式限制了活动进程的数目，当进程大小与空闲分区不匹配时，内存空间利用率大小与空闲分区不匹配时，内存空间利用率低。动态分区方式算法复杂，回收空闲分区低。动态分区方式算法复杂，回收空闲分区时需要进行分区合并等，系统开销较大。伙时需要进行分区合并等，系统开销较大。伙伴系统方式是对以上两种内存方式的一种折伴系统方式是对以上两种内存方式的一种折衷方案。衷方案。752022-3-20 (6)伙伴系统伙伴系统n伙伴系统规定，无论已分配分区或空闲分区，伙伴系统规定，无论已分配分区或空闲分区，其大小均为其大小均为2的的K次幂，次幂，K为整数，为整数，nlkm,km

52、,其中其中：2l表示分配的最小分区的大小，表示分配的最小分区的大小，2m表示分配的最大分区的大小，表示分配的最大分区的大小，762022-3-20 4.3.4伙伴关系伙伴关系n假设存储空间的大小为假设存储空间的大小为2M, M是正整数。伙伴系统是正整数。伙伴系统得名于它的每一个块都有一个对应的同样大小的得名于它的每一个块都有一个对应的同样大小的 “伙伴伙伴”块。对于一个块。对于一个N字节的存储请求（字节的存储请求（N2M），），伙伴系统首先确定使得伙伴系统首先确定使得2k的最小的最小k值。若在空闲区表值。若在空闲区表中能找到中能找到2k大小的空闲块，则进行分配，否则就找大小的空闲块，则进行分配

53、，否则就找一个更大的空闲块，把它均分成两半，不断重复这一个更大的空闲块，把它均分成两半，不断重复这个分割过程，直到生成个分割过程，直到生成2k大小的空闲块，并把它分大小的空闲块，并把它分配出去，因为是均分两半，所以还会有一个配出去，因为是均分两半，所以还会有一个2k大小大小的空闲块，即其的空闲块，即其“伙伴伙伴”块。回收的时候如果其块。回收的时候如果其“伙伴伙伴”块是空闲的就合并成一个大的空闲块，如块是空闲的就合并成一个大的空闲块，如果此空闲块的果此空闲块的“伙伴伙伴”块仍是空闲的，则继续合并，块仍是空闲的，则继续合并，直至其直至其“伙伴伙伴”块不是空闲的。块不是空闲的。772022-3-20

54、 (7)哈希算法哈希算法n利用哈希快速查找的优点，以及空闲分区在利用哈希快速查找的优点，以及空闲分区在可利用空间表中的分布规律，建立哈希函数，可利用空间表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，构造一张以空闲分区大小为关键字的哈希表，该表的每一个表项记录了一个对应的空闲分该表的每一个表项记录了一个对应的空闲分区链表表头指针。当进行空闲分区分配时，区链表表头指针。当进行空闲分区分配时，根据所需空闲分区的大小，通过哈希函数计根据所需空闲分区的大小，通过哈希函数计算，得到相应的空闲分区链表，实现最佳分算，得到相应的空闲分区链表，实现最佳分配策略。配策略。782022-3-

55、203. 3. 分区的分配分区的分配在采用分区存储管理的系统中，系统初启后。除操作系统占用一个分区外，其余存储区为一个大的空闲区。 分区的分配是指系统根据用户的请求，在空闲区表或空闲区队列中寻找一个满足用户要求的空闲区，把这个空闲区分配给用户。 当用户要求一个大小为SIZE的存储空间时，系统查询空闲区链（表），找一个大于或等于SIZE的空闲区。792022-3-20分配时的三种情况分配时的三种情况n其一是系统中无满足要求的空闲区，则分配失败。n其二是空闲区大小与SIZE相等，则修改空闲区表相应表目，向用户返回该空闲区首址，表示此空闲区已分给了要求的用户。802022-3-20 n其三是空闲区大

56、于SIZE，这时将空闲区一分为二。将一个空闲区分成二部分有两种办法：一是从空闲区的上部开始划出SIZE大小的空闲区给用户；二是从空闲区的底部开始向上划出SIZE大小的空闲区给用户。一般常采用第二种办法，因为这样划分时，余下的部分在空闲区表中的首地址不变，只需要修改一下大小就行了。812022-3-20 822022-3-20n主存的分配过程如下：主存的分配过程如下：u首先初始化空闲分区链（首先初始化空闲分区链（1个记录），整个用户个记录），整个用户区为一个空闲区，在空闲分区链（表）中填入区为一个空闲区，在空闲分区链（表）中填入用户区的始址和大小。用户区的始址和大小。u其次，从作业队列中取出队首

57、作业，在空闲分其次，从作业队列中取出队首作业，在空闲分区表中找一个不小于作业的空闲区，装入作业，区表中找一个不小于作业的空闲区，装入作业，在已分分区表中增加一个记录，填上作业所占在已分分区表中增加一个记录，填上作业所占分区的序号、始址、大小、作业名，并修改空分区的序号、始址、大小、作业名，并修改空闲分区表相应记录的始址和大小；若找不到一闲分区表相应记录的始址和大小；若找不到一个空闲区，则显示主存不足的信息，删除该作个空闲区，则显示主存不足的信息，删除该作业或把作业放到队尾，等待大的空闲区。业或把作业放到队尾，等待大的空闲区。u然后，再分配下一个作业，直到所有作业分配然后，再分配下一个作业，直到

58、所有作业分配完毕。完毕。832022-3-20分区的回收分区的回收 当某个进程释放某存储区时，系统首先检查释放区是否与系统中的空闲区相邻，若相邻则把释放区合并到相邻的空闲区中去，否则把释放区作为一个空闲区插入到空闲区表的适当位置。842022-3-20释放区与空闲区相邻的四种情况释放区与空闲区相邻的四种情况852022-3-20说明说明n释放区与前空闲区相邻：将释放区与前空闲区合并为一个空闲区。其首址仍为前空闲区首址，大小为释放区大小与空闲区大小之和。n释放区与后空闲区相邻：则把释放区合并到后空闲区，首地址为释放区首地址，大小为二者大小之和。n释放区与前后两个空闲区相邻：将这三个区合为一个空闲区，其首址为前空闲区首址，大小为这三个区大小之和，并取消原后空闲区表项。n释放区不与任何空闲区相邻：将释放区作为一个空闲区，将其大小和首址插入到空闲区链的适当位置。862022-3-20练习练习n在可变式分区分配方案中，某一作业完成后，系统收回其内存空间并与相邻空闲区合并，为此需修改空闲区表，造成空闲区数减1的情况是（）。A、无上邻空闲区也无下邻空闲区B、有上邻空闲区但无下邻空闲区C、有下邻空闲区但无上邻空闲区D、有上邻空闲区也有下邻空闲区872022-3-20 4.3.6动态可重定位分区分配动态可重定位分区分配 n在连续分配中，必须把一个系统或用户程序在连续分配中，必须把一个系统或用