操作系统课件第四版第四章

1、 4.1 4.1 存储器的层次结构存储器的层次结构 4.2 4.2 程序的装入和链接程序的装入和链接 4.3 4.3 连续分配存储管理方式连续分配存储管理方式 4.4 4.4 对换对换4.5 4.5 分页存储管理方式分页存储管理方式 4.6 4.6 分段存储管理方式分段存储管理方式 n微机中的存储层次组织：微机中的存储层次组织：n访问速度越慢，容量越大，价格越便宜；访问速度越慢，容量越大，价格越便宜；n最佳状态应是最佳状态应是各层次的存储器各层次的存储器都处于都处于均衡的繁忙状均衡的繁忙状态态（如：缓存命中率正好使主存读写保持繁忙）。（如：缓存命中率正好使主存读写保持繁忙）。外存(second

2、ary storage)DOS核心命令处理程序内存(primary storage)快速缓存(cache)寄存器(register)n快速缓存：快速缓存：Data CacheData Cachen内存：内存：DRAM, SDRAMDRAM, SDRAM等等n外存：软盘、硬盘、光盘、磁带等外存：软盘、硬盘、光盘、磁带等4.1 4.1 存储器的层次结构存储器的层次结构 操作系统课程主要介绍以下两类存储器的管理：操作系统课程主要介绍以下两类存储器的管理：内存储器内存储器（简称内存、（简称内存、主存、物理存储器）主存、物理存储器）n处理机能直接访问的处理机能直接访问的存储器。用来存放系存储器。用来存放

3、系统和用户的程序和数统和用户的程序和数据，其特点是存取速据，其特点是存取速度快，存储方式是以度快，存储方式是以新换旧，断电信息丢新换旧，断电信息丢失。失。外存储器外存储器（简称外存、（简称外存、辅助存储器）辅助存储器）n处理机不能直接访问处理机不能直接访问的存储器。用来存放的存储器。用来存放用户的各种信息，存用户的各种信息，存取速度相对内存而言取速度相对内存而言要慢得多，但它可用要慢得多，但它可用来长期保存用户信息。来长期保存用户信息。将在设备管理一章中将在设备管理一章中介绍。介绍。* 存储器管理目的和存储器管理目的和功能：功能：1.1.主存储器的分配与回收主存储器的分配与回收 为每一道程序分

4、配内存空间，使它们为每一道程序分配内存空间，使它们“各得其所各得其所”；在；在用户作业不再需要它时，及时回收，以供其它用户使用。用户作业不再需要它时，及时回收，以供其它用户使用。2.2.提高主存储器的利用率提高主存储器的利用率 允许允许多道程序多道程序动态共享主存，并共享内存中某个区域的动态共享主存，并共享内存中某个区域的信息。信息。3.3.存储保护存储保护 确保每道程序都在自己的内存空间运行，互不干扰。确保每道程序都在自己的内存空间运行，互不干扰。4.4.内存扩充内存扩充 从逻辑上来扩充内存容量，使用户认为系统所拥有的内从逻辑上来扩充内存容量，使用户认为系统所拥有的内存空间远比其实际的内存空

5、间（硬件存空间远比其实际的内存空间（硬件RAMRAM）大的多。）大的多。5.5.地址映射地址映射 将程序地址空间中使用的逻辑地址变换成主存中的地址将程序地址空间中使用的逻辑地址变换成主存中的地址的过程。的过程。4.2 4.2 程序的装入和链接程序的装入和链接 将一个用户源程序变为一个可在内存中执行将一个用户源程序变为一个可在内存中执行的程序（进程），需要以下准备工作：的程序（进程），需要以下准备工作：编辑编辑 编译编译 链接链接 装入装入 源文件源文件 目标模块目标模块 可执行文件可执行文件 进程进程在这个过程中，原程序的地址将产生变化：在这个过程中，原程序的地址将产生变化： （1）编辑编辑：

6、使用符号地址使用符号地址 （2）编译编译：模块内符号地址模块内符号地址解析解析 （3）链接链接：模块间符号地址模块间符号地址解析解析 （4）装入装入：使用物理地址使用物理地址符号地址：符号地址：在源程序中，是通过符号名来访问子程序和在源程序中，是通过符号名来访问子程序和数据的，把程序中符号名的集合称为数据的，把程序中符号名的集合称为“名字空间名字空间”。逻辑地址逻辑地址（相对地址，虚地址）：源程序经过汇编或编（相对地址，虚地址）：源程序经过汇编或编译后，形成目标程序，每个目标程序都是以译后，形成目标程序，每个目标程序都是以0为基址顺为基址顺序进行编址的，原来用序进行编址的，原来用符号名符号名访

7、问的单元用具体的数访问的单元用具体的数据据 单元号取代。把逻辑地址的集合称为单元号取代。把逻辑地址的集合称为“逻辑地逻辑地址空间址空间”或简称为或简称为“地址空间地址空间”。物理地址物理地址（绝对地址，实地址）：把内存分成若干个大（绝对地址，实地址）：把内存分成若干个大小相等的存储单元，每个单元给一个编号，这个编号称小相等的存储单元，每个单元给一个编号，这个编号称为物理地址。物理地址可直接寻址。存储单元占为物理地址。物理地址可直接寻址。存储单元占8位，位，称作字节（称作字节（byte）。）。当程序装入内存时当程序装入内存时, 操作系统要为该程序分配一操作系统要为该程序分配一个合适的内存空间，由

8、于个合适的内存空间，由于程序的逻辑地址与分配到内程序的逻辑地址与分配到内存物理地址不一致存物理地址不一致, 而而CPU执行指令时，是按物理地执行指令时，是按物理地址进行的，所以要进行地址转换。址进行的，所以要进行地址转换。地址重定位地址重定位：将用户程序中的逻辑地址转换为运行时：将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址。这个过程也称为由机器直接寻址的物理地址。这个过程也称为地址映地址映射射（map）。）。 地址空间的程序和数据经过地址重定位处理后，地址空间的程序和数据经过地址重定位处理后，就变成了可由就变成了可由CPU直接执行的物理地址程序。把这一直接执行的物理地址程序。把这

9、一地址集合称为地址集合称为“物理地址空间物理地址空间”或或“存储空间存储空间”。 程序的名字空间、地址空间和存储空间程序的名字空间、地址空间和存储空间之间的关系如图所示：之间的关系如图所示： 汇编汇编/编译编译 地址重定位地址重定位 链链 接接 装装 入入 名字空间名字空间 地址空间地址空间 存储空间存储空间 （相对地址（相对地址/ （绝对地址（绝对地址/ 逻辑地址空间）逻辑地址空间） 物理地址空间）物理地址空间） 符符 号号源源 程程 序序相对目标相对目标程序程序（装配模块）（装配模块）绝对目标绝对目标程序程序如果事先知道程序将驻留在内存的什么位置，在编如果事先知道程序将驻留在内存的什么位置

10、，在编译时，编译程序将产生物理地址。或由程序员直接按物译时，编译程序将产生物理地址。或由程序员直接按物理地址编程，但这种程序在系统中是不能做任何移动的，理地址编程，但这种程序在系统中是不能做任何移动的，否则就会出错。否则就会出错。即在程序的即在程序的编辑或编译时期编辑或编译时期确定确定地址映射地址映射关系，装关系，装入时直接定位在上述入时直接定位在上述(即文件中记录的地址即文件中记录的地址)物理地址。物理地址。n优点：装入过程简单。优点：装入过程简单。n缺点：过于依赖于硬件结构，不适于多道程序系统。缺点：过于依赖于硬件结构，不适于多道程序系统。一、程序的装入一、程序的装入1. 1. 绝对装入方

11、式绝对装入方式2.2.可重定位装入方式（也称为静态重定位或静可重定位装入方式（也称为静态重定位或静态地址映射）态地址映射） 是在程序执行之前进行重定位。它根据装配模是在程序执行之前进行重定位。它根据装配模块将要装入的内存起始地址，直接修改装配模块中块将要装入的内存起始地址，直接修改装配模块中的有关使用地址的指令。即当用户的有关使用地址的指令。即当用户程序被装入内存程序被装入内存时时，一次性，一次性实现实现逻辑地址到物理逻辑地址到物理地址的转换地址的转换，以后，以后不再转换（一般在装入内存时由软件完成）。不再转换（一般在装入内存时由软件完成）。 例如在例如在图中以图中以“0”作为参考地址的装配模

12、块，作为参考地址的装配模块，要装入以要装入以10000为起始地址的存储空间。显然在装入为起始地址的存储空间。显然在装入程序之前，程序必须做一些修改才能正确运行。程序之前，程序必须做一些修改才能正确运行。 0 0： 1000010000： 100： LOAD 1，2500 10100： LOAD 1，12500 2500： 365 12500： 365 2600： 12600： 程序的地址空间程序的地址空间 内存的地址空间内存的地址空间静态重定位虽然有无须硬件支持的优点，但是也静态重定位虽然有无须硬件支持的优点，但是也存在明显的存在明显的缺点缺点：一一是程序重定位以后就不能在内存是程序重定位以后

13、就不能在内存中移动；中移动；二二是要求程序的存储空间是连续的，不能把是要求程序的存储空间是连续的，不能把程序存储到若干个不连续的区域中。程序存储到若干个不连续的区域中。3.3.动态运行时装入方式（也称为动态重定位或动动态运行时装入方式（也称为动态重定位或动态地址映射）态地址映射）是指在是指在程序执行过程程序执行过程中进行中进行地址重定位地址重定位，即在每，即在每次访问内存单元前才进行地址变换。动态重定位可使次访问内存单元前才进行地址变换。动态重定位可使装配模块不加任何修改就装入内存，装配模块不加任何修改就装入内存，但是它需要硬但是它需要硬件件 重定位寄存器的支持。重定位寄存器的支持。n优点：优

14、点：nOS可以移动程序，有利用实现共享。可以移动程序，有利用实现共享。n能够支持程序执行中产生的地址引用，如指针变量（而能够支持程序执行中产生的地址引用，如指针变量（而不仅是生成可执行文件时的地址引用）。不仅是生成可执行文件时的地址引用）。n缺点：缺点： 需要硬件支持，需要硬件支持，OS实现较复杂。实现较复杂。n它是虚拟存储的基础。它是虚拟存储的基础。 0 0： 1000010000： 100： LOAD 1，2500 10100： LOAD 1，2500 2500： 365 12500： 365 2600： 12600： 程序的地址空间程序的地址空间 内存的地址空间内存的地址空间10000重

15、定位寄存器重定位寄存器动态重定位的示意图动态重定位的示意图二、程序的链接二、程序的链接1.1.静态链接方式静态链接方式（1）对相对地址进行修改）对相对地址进行修改（2）变换外部调用符号）变换外部调用符号模块ACALL B；Return模块BCALL C；Return;模块CReturn;模块AJSR“L”Return;模块BJSR“L+M”Return;模块CReturn;LL+M-10L-1L+ML+M+N-10M-10L-10N-1目标模块目标模块装入模块装入模块2.2.装入时动态链接装入时动态链接 目标模块在装入内存时，边装入边链接。目标模块在装入内存时，边装入边链接。优点优点：（1）便

16、于修改和更新）便于修改和更新（2）便于实现对目标模块的共享）便于实现对目标模块的共享3.3.运行时动态链接运行时动态链接 对某些模块的链接推迟到执行时才进行。对某些模块的链接推迟到执行时才进行。优点优点： 既可加快程序的装入过程，又可节省大量的内存既可加快程序的装入过程，又可节省大量的内存空间。空间。4.3 4.3 连续分配存储管理方式连续分配存储管理方式一、单一连续分配一、单一连续分配 这是一种最简单的存储管理方式，但只能用于这是一种最简单的存储管理方式，但只能用于单用户、单任务的操作系统，如在单用户、单任务的操作系统，如在8位和位和16位微机上位微机上的的CP/M和和MS-DOS操作系统。

17、它将内存分为两个区：操作系统。它将内存分为两个区： 系统区系统区：仅供操作系统使用，通常设置在内存的：仅供操作系统使用，通常设置在内存的低段；低段； 用户区用户区：指除系统区以外的全部内存空间，提供：指除系统区以外的全部内存空间，提供给用户使用。给用户使用。 采用这种管理方式时，处理器中设置一个采用这种管理方式时，处理器中设置一个界限界限寄存器寄存器，寄存器中的内容为当前可供用户使用的主，寄存器中的内容为当前可供用户使用的主存区域的起始地址。存区域的起始地址。作业作业2作业作业1.CPU界限寄存器界限寄存器a作业队列作业队列操作系统操作系统空闲区空闲区主存主存0abc用户区用户区注：注：(1)

18、不管空闲区有多大，都不用来装另一个作业。不管空闲区有多大，都不用来装另一个作业。 (2)通常采用覆盖技术来运行比内存空间大的作业。通常采用覆盖技术来运行比内存空间大的作业。二、固定分区分配二、固定分区分配 固定式分区固定式分区是在作业装入之前，内存就被划分成是在作业装入之前，内存就被划分成若干个分区。一旦划分完成，在系统运行期间不再重若干个分区。一旦划分完成，在系统运行期间不再重新划分，即分区的个数不可变，分区的大小不可变，新划分，即分区的个数不可变，分区的大小不可变，所以，固定式分区又称为所以，固定式分区又称为静态分区静态分区。(注：注：操作系统操作系统占用其中一个分区。）占用其中一个分区。

19、） 1.1.划分分区的方法划分分区的方法 （1）分区大小相等：）分区大小相等： 只适合于多个相同程序的并发执行（处理多个类只适合于多个相同程序的并发执行（处理多个类型相同的对象）。型相同的对象）。 （2）分区大小不等：）分区大小不等： 多个小分区、适量的中等分区、少量的大分区。多个小分区、适量的中等分区、少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。根据程序的大小，分配当前空闲的、适当大小的分区。2.2.内存分配内存分配 将分区按大小进行排队，并在系统中建立一张分区将分区按大小进行排队，并在系统中建立一张分区说明表，每个表目说明一个分区的大小、起始地址和是说明表，每个表目说明一

20、个分区的大小、起始地址和是否已分配的使用标志。分区说明表和内存分配图如下所否已分配的使用标志。分区说明表和内存分配图如下所示。示。区号区号 大小大小 起址起址 标志标志 1 16KB 20K 已分配已分配 2 32KB 36K 已分配已分配 3 64KB 68K 已分配已分配 4 124KB 132K 未分配未分配 (a) 分区说明表分区说明表0k： 20k： 第第1分区（分区（16kb）36k： 第第2分区（分区（32kb） （已分配）（已分配） 68k： 第第3分区（分区（64kb） （已分配）（已分配）132k： 第第4分区分区(124kb) （未分配）（未分配） 256k： （b）内存

21、分配图）内存分配图操作系统操作系统作业作业A（16k）作业作业B（26k）作业作业C（56k） n优点：优点：固定式分区实现技术简单，适用于作业的大固定式分区实现技术简单，适用于作业的大小和多少事先都比较清楚的系统。它用于小和多少事先都比较清楚的系统。它用于6060年代的年代的IBM-360IBM-360的的MFTMFT操作系统中。操作系统中。n缺点：缺点：内存的利用率不高，内存的利用率不高，“零头零头”空间不能充分空间不能充分利用。此管理方法已基本被淘汰了。利用。此管理方法已基本被淘汰了。三、动态分区分配三、动态分区分配 在分配时，首先找到一个足够大的空闲分区，在分配时，首先找到一个足够大的

22、空闲分区，即这个空闲区的大小比作业要求的要大，系统则将即这个空闲区的大小比作业要求的要大，系统则将这个空闲分区分成两部分：一部分成为已分配的分这个空闲分区分成两部分：一部分成为已分配的分区，剩余的部分仍作为空闲区。区，剩余的部分仍作为空闲区。1.1.分区分配中的数据结构分区分配中的数据结构空闲分区表空闲分区表 空闲分区表为每个尚未分配的分区设置一个表项，空闲分区表为每个尚未分配的分区设置一个表项，包括分区的包括分区的序号序号、大小大小、始址始址和和状态状态。 空闲分区链空闲分区链 为了实现对空闲分区的分配和链接，在每个分区为了实现对空闲分区的分配和链接，在每个分区的的起始部分起始部分，设置一些

23、用于控制分区分配的信息（如，设置一些用于控制分区分配的信息（如分区的大小和状态位），以及用于链接其它分区的前分区的大小和状态位），以及用于链接其它分区的前向指针；在向指针；在分区尾部分区尾部，设置了一个后向指针，为了检，设置了一个后向指针，为了检索方便也设置了控制分区分配的信息。然后，通过前、索方便也设置了控制分区分配的信息。然后，通过前、后向指针将所有的分区链接成一个后向指针将所有的分区链接成一个双向链表双向链表。 0k 0k： 20k20k： 52k52k： 116k116k： 164k164k： 260k260k： 512k512k： （c c）内存分配图）内存分配图N N个字节个字节可

24、可 用用序号序号P P 大小大小起址起址状态状态 1 148k48k116k116k空闲空闲 2 2252k252k260k260k空闲空闲 3 3空表目空表目 4 4空表目空表目 5 5空表目空表目 （a a）空闲分区表）空闲分区表 操作系统操作系统作业作业1 1（32k32k）作业作业2 2（64k64k）空闲区（空闲区（48k48k）作业作业4 4（96k96k）空闲区（空闲区（252k252k）（b b）空空闲闲链链结结构构前向前向指针指针N+20后向后向指针指针N+202.2.分区分配算法分区分配算法 由于内存分配算法对系统性能有很大的影响，所由于内存分配算法对系统性能有很大的影响，

25、所以人们进行了广泛深入的研究，产生了许多动态分区以人们进行了广泛深入的研究，产生了许多动态分区分配算法。分配算法。 下一节将详细介绍。下一节将详细介绍。3.3.分区分配操作分区分配操作1）分配内存）分配内存YNNNY申请分配一个申请分配一个u.size大小的分区大小的分区从头开始查表从头开始查表是否检索完毕？是否检索完毕？本次无法分配本次无法分配m.sizeu.size m.size-u.sizesize？从该分区中划出从该分区中划出u.size大小的分区大小的分区继续检索下一继续检索下一个表项个表项将该表目以上的所有将该表目以上的所有表目下移一格表目下移一格将该分区分配给申请者，将该分区分配

26、给申请者，修改有关的数据结构修改有关的数据结构 返返 回回2）回收内存）回收内存 当一个作业运行完毕释放内存时，系统根据释当一个作业运行完毕释放内存时，系统根据释放区的首地址，从空闲区说明表中找到相应的插入放区的首地址，从空闲区说明表中找到相应的插入点，此时可能出现下列四种情况（如下图点，此时可能出现下列四种情况（如下图所示，其所示，其中中F1F1，F2F2表示回收区的前、后空闲区）表示回收区的前、后空闲区）：n 当回收区既不与当回收区既不与F1F1邻接，又不与邻接，又不与F2F2邻接时（如邻接时（如A A），应为回收区单独建立一项新表目，填写回收区的起应为回收区单独建立一项新表目，填写回收区

27、的起址和大小，并根据其起址，插入到空闲区说明表的址和大小，并根据其起址，插入到空闲区说明表的适当位置。适当位置。n 当回收区只与插入点的前一个分区当回收区只与插入点的前一个分区F1F1相邻接时相邻接时（如（如B B），应将回收区与插入点的前一个分区合并，），应将回收区与插入点的前一个分区合并，不再为回收区分配新的表目，而只需修改不再为回收区分配新的表目，而只需修改F1分区表分区表目的大小即可。目的大小即可。n当回收区只与插入点的后一个分区当回收区只与插入点的后一个分区F2F2相邻接时相邻接时（如（如C C），将把两个空闲区合并，把回收区的起址作为），将把两个空闲区合并，把回收区的起址作为新空闲

28、区的起址，大小为两个分区之和。新空闲区的起址，大小为两个分区之和。n当回收区与插入点的前、后两个分区（当回收区与插入点的前、后两个分区（F1F1和和F2F2）都相邻接时（如都相邻接时（如D D），合并三个分区，用），合并三个分区，用F1F1表目的起址表目的起址作为新空闲区的起址，修改其大小为三块分区之和，作为新空闲区的起址，修改其大小为三块分区之和，最后取消最后取消F2F2的表目。的表目。A A B B C C D D F1 回收区回收区 F2 回收区回收区 F2 回收区回收区 F1 回收区回收区n首次适应算法（首次适应算法（First FitFirst Fit）：）： 从从空闲分区表空闲分区

29、表的第一个表目起查找该表的第一个表目起查找该表，把最，把最先能够满足要求的空闲区分配给作业，这种方法目先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。为适应这种算法，空闲分区的在于减少查找时间。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要表（空闲区链）中的空闲分区要按按地址地址由低到高进由低到高进行排序行排序。 特点：特点：该算法的分配和释放的时间性能较好，较大的该算法的分配和释放的时间性能较好，较大的空闲分区可以被保留在内存高端。空闲分区可以被保留在内存高端。 如果找出的自由区长度恰好等于申请的长度则如果找出的自由区长度恰好等于申请的长度则是最合适的了；如果比申请的长

30、度略大，则分割后是最合适的了；如果比申请的长度略大，则分割后剩下的自由区就很小，这种自由区不但不能被再度剩下的自由区就很小，这种自由区不但不能被再度使用，而且还白白占用自由区链表的一个结点。当使用，而且还白白占用自由区链表的一个结点。当小自由区结点过多时，本算法的性能急剧下降。小自由区结点过多时，本算法的性能急剧下降。 四、基于顺序搜索的动态分区分配算法四、基于顺序搜索的动态分区分配算法n循环首次适应算法循环首次适应算法(Next Fit)： 该算法是首次适应算法的变种。在分配内存空该算法是首次适应算法的变种。在分配内存空间时，不再每次从表头（链首）开始查找，而是从间时，不再每次从表头（链首）

31、开始查找，而是从上次找到的空闲区的下一个空闲区开始查找，直到上次找到的空闲区的下一个空闲区开始查找，直到找到第一个能满足要求的的空闲区为止，并从中划找到第一个能满足要求的的空闲区为止，并从中划出一块与请求大小相等的内存空间分配给作业。出一块与请求大小相等的内存空间分配给作业。 特点：特点： 该算法能使内存中的空闲区分布得比较均匀。该算法能使内存中的空闲区分布得比较均匀。但较大的空闲分区不易保留。但较大的空闲分区不易保留。n最佳适应算法（最佳适应算法（Best Fit）：）： 它从全部空闲区中找出能满足作业要求的、且它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量

32、小。大小最小的空闲分区，这种方法能使碎片尽量小。为适应这种算法，空闲分区表（空闲区链）中的空为适应这种算法，空闲分区表（空闲区链）中的空闲分区要闲分区要按按大小大小从小到大进行排序从小到大进行排序，自表头开始查自表头开始查找到第一个满足要求的自由分区分配。找到第一个满足要求的自由分区分配。 若系统中有与申请区大小相等的空闲区，这种若系统中有与申请区大小相等的空闲区，这种算法肯定能将这种空闲区分配给申请者。（首次适算法肯定能将这种空闲区分配给申请者。（首次适应算法则不一定）。应算法则不一定）。 特点：特点：最大的缺点是分割后的空闲区将会很小，直最大的缺点是分割后的空闲区将会很小，直至无法使用，而

33、造成浪费。至无法使用，而造成浪费。n最坏适应算法（最坏适应算法（Worst FitWorst Fit）：）： 从所有未分配的分区中挑选从所有未分配的分区中挑选最大的最大的且且大于和等大于和等于于作业大小的分区分给要求的作业；空闲分区作业大小的分区分给要求的作业；空闲分区按大按大小由大到小排序小由大到小排序，每次查找从链头开始。，每次查找从链头开始。 特点：特点：由于过多的分割大的自由区，当遇到较大空由于过多的分割大的自由区，当遇到较大空间申请时，无法满足其申请的可能性较大。本算法间申请时，无法满足其申请的可能性较大。本算法对中、小作业比较有利。对中、小作业比较有利。起址起址 大小大小 状态状态

34、 a a16k16k c c14k14k e e10k10k g g30k30k 空闲分区表空闲分区表 *操作系统操作系统16K空闲区空闲区14K空闲区空闲区10K空闲区空闲区30K空闲区空闲区abcdefg0Job1 Job1 要求要求 13K13KJob2Job2Job3Job3 作业队列作业队列首次适应算法首次适应算法起址起址 大小大小 状态状态 e e10k10k c c14k 14k a a16k 16k g g30k30k 最优适应算法最优适应算法例：分配例：分配一个一个13KB分区分区起址起址 大小大小 状态状态 g g30k 30k a a16k16k c c14k14k e

35、e10k10k 最坏适应算法最坏适应算法思考题：思考题：下表给出了某系统中的空闲分区表，系统采用可变式下表给出了某系统中的空闲分区表，系统采用可变式分区存储管理策略。现有以下作业序列：分区存储管理策略。现有以下作业序列：96K、20K、200K，若用首次适应算法和最佳适应算法来处理这些，若用首次适应算法和最佳适应算法来处理这些作业序列，试问哪一种算法可以满足该作业的请求，为作业序列，试问哪一种算法可以满足该作业的请求，为什么？什么？分区号分区号大小大小 起始地址起始地址132K100K210K150K35K200K4218K220K596K530Kn快速适应算法（快速适应算法（Quick Fi

36、tQuick Fit）：）： 是将空闲分区根据其容量大小分类，对于每一是将空闲分区根据其容量大小分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，同时在内存中设立一张管理索引表，闲分区链表，同时在内存中设立一张管理索引表，该表的每一个表项对应了一种空闲分区类型，并记该表的每一个表项对应了一种空闲分区类型，并记录了该类型空闲链表表头的指针。录了该类型空闲链表表头的指针。n伙伴系统伙伴系统 性能优于快速适应算法性能优于快速适应算法n哈希算法哈希算法五、基于索引搜索的动态分区分配算法五、基于索引搜索的动态分区分配算法六、动态可重定位分区

37、分配六、动态可重定位分区分配1.1.紧凑紧凑可变式分区也有零头问题。在系统不断地分配可变式分区也有零头问题。在系统不断地分配和回收中，必定会出现一些不连续的小的空闲区，称和回收中，必定会出现一些不连续的小的空闲区，称为为外零头外零头。虽然可能所有零头的总和超过某一个作业。虽然可能所有零头的总和超过某一个作业的要求，但是由于不连续而无法分配。的要求，但是由于不连续而无法分配。操作系统用户程序 1 用户程序 3用户程序 6用户程序 910KB30KB14KB26KB 如图所示，如图所示，虽然当前内存中虽然当前内存中的空闲分区的总的空闲分区的总容量达到容量达到80KB80KB，却无法装入一个却无法装

38、入一个40KB40KB的作业。的作业。 解决零头的方法是解决零头的方法是拼接拼接（或称（或称紧凑紧凑），即向一个），即向一个方向（例如向低地址端）移动已分配的作业，使那些方向（例如向低地址端）移动已分配的作业，使那些零散的小空闲区在另一方向连成一片。零散的小空闲区在另一方向连成一片。 分区的拼接技术，一方面分区的拼接技术，一方面是要求能够对作业进行重定位，是要求能够对作业进行重定位，另一方面系统在拼接时要耗费另一方面系统在拼接时要耗费较多的时间。较多的时间。操作系统用户程序 1用户程序 3用户程序 6用户程序 98 0KB2.2.动态重定位动态重定位 允许作业在运行过程中在内存中移动的技术必须

39、获允许作业在运行过程中在内存中移动的技术必须获得硬件支持。只有具有得硬件支持。只有具有动态重定位硬件机构动态重定位硬件机构的计算机系的计算机系统，才有可能采取动态重定位可变分区多道管理技术，统，才有可能采取动态重定位可变分区多道管理技术，系统的硬件包括系统的硬件包括重定位寄存器和加法器重定位寄存器和加法器。* * 动态重定位地址转换动态重定位地址转换 程序的目标模块在装入内存时，与地址有关的指令程序的目标模块在装入内存时，与地址有关的指令都无须进行修改，如在图都无须进行修改，如在图中中LOAD 1，2500这条指令中这条指令中仍保持相对地址仍保持相对地址2 2500。当该模块被操作系统调度到处

40、理。当该模块被操作系统调度到处理机上执行时，操作系统首先把该模块装入的实际起始地机上执行时，操作系统首先把该模块装入的实际起始地址减去目标模块的相对基地址（图址减去目标模块的相对基地址（图中该模块的基地址为中该模块的基地址为0），然后将其差值装入重定位寄存器。），然后将其差值装入重定位寄存器。 当当CPU取一条访问内存的指令时，地址变换硬件逻取一条访问内存的指令时，地址变换硬件逻辑自动将指令中的相对地址与重定位寄存器中的值相加，辑自动将指令中的相对地址与重定位寄存器中的值相加，再根据和值作为内存的绝对地址去访问该单元的数据。再根据和值作为内存的绝对地址去访问该单元的数据。 重定位寄存器重定位寄

41、存器 10000 0： 10000： 100：LOAD 1，2500 10100： LOAD 1，2500 2500： 365 12500： 365 2600： 12600： 程序的地址空间程序的地址空间 内存的地址空间内存的地址空间 由此可见，动态重定位是在指令执行过程中动态进由此可见，动态重定位是在指令执行过程中动态进行，这样可以带来两个行，这样可以带来两个好处好处： 目标程序装入内存时无需任何修改，所以装入之后目标程序装入内存时无需任何修改，所以装入之后再移动也不会影响其正确运行，这便于存储器用紧缩来再移动也不会影响其正确运行，这便于存储器用紧缩来解决存储器的碎片问题。解决存储器的碎片问

42、题。 一个程序由若干个相对独立的目标模块组成时，也一个程序由若干个相对独立的目标模块组成时，也可将每个目标模块各装入一个存储区域，这些存储区域可将每个目标模块各装入一个存储区域，这些存储区域可以不相邻接，只要各个模块有自己对应的重定位寄存可以不相邻接，只要各个模块有自己对应的重定位寄存器就可以了。器就可以了。3.3.动态重定位分区分配算法动态重定位分区分配算法动态重定位分区管理中何时进行存储器紧缩有二种动态重定位分区管理中何时进行存储器紧缩有二种不同的解决办法：不同的解决办法：n在某个分区被释放后立即进行紧缩，系统总是只有在某个分区被释放后立即进行紧缩，系统总是只有一个连续的分区而无碎片，此法

43、很花费机时。一个连续的分区而无碎片，此法很花费机时。n当当“请求分配模块请求分配模块”找不到足够大的自由分区分给找不到足够大的自由分区分给用户时再进行紧缩，这样紧缩的次数比上种方法少用户时再进行紧缩，这样紧缩的次数比上种方法少得多，但管理复杂。采用此法的动态重定位分区分得多，但管理复杂。采用此法的动态重定位分区分配算法框图如下：配算法框图如下：动态重定位分区动态重定位分区 分配分配算法框图算法框图 N N Y Y 请求分配请求分配u.size分区分区检索空闲分区链（表）检索空闲分区链（表）无法分无法分配返回配返回空闲分区总空闲分区总和和u.size找到大于找到大于u.size的可用的可用区否？

44、区否？进行紧凑形成进行紧凑形成连续空闲区连续空闲区 修改有关的修改有关的 数据结构数据结构 按动态分区方式按动态分区方式 进行分配进行分配 修改有关的修改有关的 数据结构数据结构返回分区号及首址返回分区号及首址 交换技术交换技术最早用在麻省理工学院的兼容分时系最早用在麻省理工学院的兼容分时系统统CTSS中。中。一、多道程序环境下的对换技术一、多道程序环境下的对换技术1.1.对换的引入对换的引入 在多道程序环境下为了提高内存和在多道程序环境下为了提高内存和CPU的利用的利用率，增加系统吞吐量，系统中增设了对换，率，增加系统吞吐量，系统中增设了对换，把内存中把内存中暂不能运行的进程（或程序和数据）

45、调出到外存上，暂不能运行的进程（或程序和数据）调出到外存上，以腾出足够的内存空间，把已具备运行条件的进程或以腾出足够的内存空间，把已具备运行条件的进程或进程所需要的程序和数据换入内存。进程所需要的程序和数据换入内存。 UNIX系统早期已引入对换功能并一直保留至今，系统早期已引入对换功能并一直保留至今，系统中专门设置一个对换进程完成以上功能。系统中专门设置一个对换进程完成以上功能。4.4 4.4 对换对换2.2.对换的类型对换的类型（1）整体对换）整体对换 处理机中级调度实际上就是存储器的对换功能。处理机中级调度实际上就是存储器的对换功能。（2）页面（分段）对换）页面（分段）对换 如果对换是以进

46、程的一个如果对换是以进程的一个“页面页面”或或“分段分段”为为单位进行的，则称为单位进行的，则称为“部分对换部分对换”，目的是为了支持，目的是为了支持虚拟存储系统。虚拟存储系统。 为了实现进程对换，系统必须能实现对为了实现进程对换，系统必须能实现对对换空间对换空间的管理的管理，进程换入进程换入、换出换出等三项功能。等三项功能。二、对换空间的管理二、对换空间的管理1.1.对换空间管理的主要目标对换空间管理的主要目标 通常把磁盘空间分为文件区和对换区。通常把磁盘空间分为文件区和对换区。 文件区占用磁盘空间的大部分空间，用于存放各类文件区占用磁盘空间的大部分空间，用于存放各类文件，对文件区管理目标是

47、提高文件存储空间的利用率，文件，对文件区管理目标是提高文件存储空间的利用率，为此系统采用为此系统采用离散分配方式离散分配方式； 对换区只占用磁盘空间的小部分，用于存放从内存对换区只占用磁盘空间的小部分，用于存放从内存换出的进程，它的管理目标是提高进程换入换出速度，换出的进程，它的管理目标是提高进程换入换出速度，为此系统采用连续分配方式。为此系统采用连续分配方式。2.2.对换区空闲盘块管理中的数据结构对换区空闲盘块管理中的数据结构 与内存在动态分区分配方式中所用数据结构相似。与内存在动态分区分配方式中所用数据结构相似。3.3.对换空间的分配与回收对换空间的分配与回收 对换空间的分配与回收与动态分

48、区方式时的内对换空间的分配与回收与动态分区方式时的内存分配与回收方法雷同。存分配与回收方法雷同。三、进程的换出与换入三、进程的换出与换入1.1.进程的换出进程的换出 当内核发现内存不足时调用对换进程，对换进当内核发现内存不足时调用对换进程，对换进程检查驻留在内存的进程，选择处于阻塞和睡眠状程检查驻留在内存的进程，选择处于阻塞和睡眠状态的进程换出，如无，则选择优先级低的驻留内存态的进程换出，如无，则选择优先级低的驻留内存时间长的处于就绪状态的进程换出。时间长的处于就绪状态的进程换出。2.2.进程的换入进程的换入 对换进程将定时执行换入操作，在对换区中选对换进程将定时执行换入操作，在对换区中选择换

49、出时间长的处于就绪态的进程调入。择换出时间长的处于就绪态的进程调入。4.5 4.5 分页存储管理方式分页存储管理方式连续分配方式导致了内存碎片问题，降低了内存连续分配方式导致了内存碎片问题，降低了内存资源的利用率，而通过资源的利用率，而通过“紧凑紧凑”方法来拼接碎片，系方法来拼接碎片，系统付出开销太大，所以提出采用统付出开销太大，所以提出采用离散分配方式离散分配方式存储进存储进程。程。 如果离散分配的基本单位是页，则称为分页存储如果离散分配的基本单位是页，则称为分页存储管理方式。管理方式。基本分页存储管理方式基本分页存储管理方式( (或称纯分页存储管或称纯分页存储管理方式理方式) )，要求把每

50、个作业全部装入内存后方要运行。，要求把每个作业全部装入内存后方要运行。一、分页存储管理的基本方法一、分页存储管理的基本方法1 1页面和物理块页面和物理块（1 1）页面）页面 分页存储管理是将一个进程的地址空间划分成若干分页存储管理是将一个进程的地址空间划分成若干个大小相等的区域，称为个大小相等的区域，称为页页。相应地，将内存空间划分。相应地，将内存空间划分成与页相同大小的若干个物理块，称为成与页相同大小的若干个物理块，称为块或页框块或页框。在为。在为进程分配内存时，将进程中若干页分别装入多个不相邻进程分配内存时，将进程中若干页分别装入多个不相邻接的块中。接的块中。 （2 2）页面大小）页面大小

51、 小小 内碎片小内碎片小, ,页表过长；大页表过长；大 页表短，管理开页表短，管理开销小，与外存交换时效率高，但页内碎片增大。页面大销小，与外存交换时效率高，但页内碎片增大。页面大小一般是小一般是2 2的幂，通常为的幂，通常为512B-8KB512B-8KB。2.2.地址结构地址结构一个进程的地址空间划分成若干个大小相等的页一个进程的地址空间划分成若干个大小相等的页后，各个页面从后，各个页面从0 0开始依次编号，称作页号，每个页面开始依次编号，称作页号，每个页面内也从内也从0 0开始编址，称为页内地址。因此，分页系统的开始编址，称为页内地址。因此，分页系统的地址结构由两部分组成：前一部分为页号

52、地址结构由两部分组成：前一部分为页号P P；后一部分；后一部分为位移量为位移量W W，即页内地址。，即页内地址。图中的地址长度为图中的地址长度为3232位，其中位，其中0 01111位为页内地址位为页内地址（每页的大小为（每页的大小为4K4K），），12123131位为页号，所以允许地位为页号，所以允许地址空间的大小最多为址空间的大小最多为1M1M个页。个页。 页号页号 P 位移量位移量W31 12 11 031 12 11 0 若给定一个逻辑地址空间中的地址为若给定一个逻辑地址空间中的地址为A，页面的大，页面的大小为小为L，则页号，则页号P和页内地址和页内地址d可由下式求得：可由下式求得：P

53、INT ALdA MOD L 例如例如 L=1000B，设，设 A=3456，则，则 P=3，d=456。 但每访问一个主存单元都做一次除法运算以得到页但每访问一个主存单元都做一次除法运算以得到页号号P和页内地址和页内地址 d，效率太低。可根据页的大小是，效率太低。可根据页的大小是2的几的几次幂，将逻辑地址从第几位分成两部分，高位部分所表次幂，将逻辑地址从第几位分成两部分，高位部分所表示的数即页号示的数即页号P，低位部分表示的数即为页内地址，低位部分表示的数即为页内地址d。 见下图：见下图： 3.3.页表页表 在将进程的每一页离散地分配到内存的多个物在将进程的每一页离散地分配到内存的多个物理块

54、中后，系统应能保证能在内存中找到每个页面理块中后，系统应能保证能在内存中找到每个页面所对应的物理块。为此，系统为每个进程建立了一所对应的物理块。为此，系统为每个进程建立了一张张页面映射表页面映射表，简称，简称页表页表（如下图（如下图所示所示）。）。每个页每个页在页表中占一个表项在页表中占一个表项，记录该页在内存中对应的物，记录该页在内存中对应的物理块号。进程在执行时，通过查找页表，就可以找理块号。进程在执行时，通过查找页表，就可以找到每页所对应的物理块号。可见，到每页所对应的物理块号。可见，页表的作用页表的作用是实是实现从页号到物理块号（即逻辑地址到物理地址）的现从页号到物理块号（即逻辑地址到

55、物理地址）的地址映射。地址映射。页表一般驻留在内存中。页表一般驻留在内存中。页表的作用页表的作用.01234560123456作业的作业的地址空间地址空间页框页框（物理块）（物理块）页号页号页表页表主存中页框主存中页框（物理块）（物理块）.分页系统还常在页表中增加一个存取控制字段，分页系统还常在页表中增加一个存取控制字段，表示该页的存取控制权限。表示该页的存取控制权限。存取控制信息包括：存取控制信息包括： 禁止做任何操作禁止做任何操作 只能执行只能执行 只能读只能读 能读能读/写写当有一程序要访问某页时，先判断该页的存取控当有一程序要访问某页时，先判断该页的存取控制和存储保护信息是否允许。制和

56、存储保护信息是否允许。添加了存取控制信息的页表表目如下图所示：添加了存取控制信息的页表表目如下图所示： 页号页号存取控制存取控制信息信息块号块号二、地址变换机构二、地址变换机构1.1.基本的地址变换机构基本的地址变换机构地址变换机构的基本任务地址变换机构的基本任务是把用户程序中的逻辑是把用户程序中的逻辑地址变换成内存中的物理地址。由于页内地址和块内地址变换成内存中的物理地址。由于页内地址和块内地址是一一对应的，所以地址变换实际上就是利用页地址是一一对应的，所以地址变换实际上就是利用页表将用户程序中的页号变换成内存中的物理块号。表将用户程序中的页号变换成内存中的物理块号。 每个进程都有一张页表，

57、页表所在内存的起始地每个进程都有一张页表，页表所在内存的起始地址和长度存放在该进程的址和长度存放在该进程的PCB中。为了实现地址变换中。为了实现地址变换功能，在系统中设置功能，在系统中设置页表寄存器页表寄存器，当某进程被调度时，当某进程被调度时，才将其页表始址和长度装入页表寄存器。才将其页表始址和长度装入页表寄存器。 在单处理机环境下，也只需要一个页表寄存器即在单处理机环境下，也只需要一个页表寄存器即可。可。 在进行地址变换时，系统将页号与页表长度进行在进行地址变换时，系统将页号与页表长度进行比较，如果页号大于页表寄存器中的页表长度，则比较，如果页号大于页表寄存器中的页表长度，则访访问越界问越

58、界，产生，产生越界中断越界中断。如未出现越界，则根据页表。如未出现越界，则根据页表寄存器中的页表始址和页号计算出寄存器中的页表始址和页号计算出该页在页表项中的该页在页表项中的位置位置，得到该页的物理块号，将此物理块号装入物理，得到该页的物理块号，将此物理块号装入物理地址寄存器中。与此同时，将有效地址（逻辑地址）地址寄存器中。与此同时，将有效地址（逻辑地址）寄存器中页内地址直接装入物理地址寄存器的块内地寄存器中页内地址直接装入物理地址寄存器的块内地址字段中，这样便完成了从逻辑地址到物理地址的变址字段中，这样便完成了从逻辑地址到物理地址的变换。换。地址变换过程地址变换过程 越界中断越界中断 页表寄

59、存器页表寄存器 逻辑地址逻辑地址2500 页号页号 块块 号号 0 1 2 页式地址变换举例页式地址变换举例块号块号5 块内地址块内地址452 页号页号2 页内地址页内地址452页表始址页表始址 页表长度页表长度 2 45例题：例题： 借助页表，将给出的逻辑地址转换成物理地址借助页表，将给出的逻辑地址转换成物理地址1. 1. 虚地址（逻辑地址、程序地址）以十六进制、八虚地址（逻辑地址、程序地址）以十六进制、八进制、二进制的形式给出进制、二进制的形式给出n将虚地址转换成二进制的数；将虚地址转换成二进制的数；n按页的大小分离出页号和位移量按页的大小分离出页号和位移量（低位部分是位移（低位部分是位移

60、量，高位部分是页号）；量，高位部分是页号）；n将位移量直接复制到内存地址寄存器的低位部分；将位移量直接复制到内存地址寄存器的低位部分；n以页号查页表，得到对应页装入内存的块号以页号查页表，得到对应页装入内存的块号，并将，并将块号转换成二进制数填入地址寄存器的高位部分，块号转换成二进制数填入地址寄存器的高位部分，从而形成内存地址。从而形成内存地址。例例1 1：有一系统采用页式存储管理，有一作业大小是：有一系统采用页式存储管理，有一作业大小是8KB8KB，页大小为页大小为2KB2KB，依次装入内存的第，依次装入内存的第7 7、9 9、A A、5 5块，试块，试将虚地址将虚地址0AFEH0AFEH，