操作系统陆丽娜版课件5

1、第五章第五章 内存管理内存管理内存管理基础内存管理基础 内存管理概念内存管理概念 交换与覆盖交换与覆盖 连续分配管理方式连续分配管理方式 非连续分配管理方式非连续分配管理方式虚拟内存管理虚拟内存管理 虚拟内存基本概念虚拟内存基本概念 请求分页管理方式请求分页管理方式 页面置换算法页面置换算法 页面分配策略页面分配策略 抖动抖动 请求分段管理方式请求分段管理方式 存储器是计算机系统的重要组成部分，存储器是计算机系统的重要组成部分，虽然内存容量在不断扩大，但内存仍是宝贵虽然内存容量在不断扩大，但内存仍是宝贵资源，如何提高主存储器利用率，并扩充大资源，如何提高主存储器利用率，并扩充大主存，对主存，对

2、主存信息实现有效保护主存信息实现有效保护是存储器管是存储器管理主要任务，也是各种不同理主要任务，也是各种不同存储管理方法存储管理方法的的目标。目标。外存(secondary storage)DOS核心命令处理程序内存(primary storage)快速缓存(cache)寄存器(register)存储器的层次结构存储器的层次结构存储管理的基本概念存储管理的基本概念存储管理目的和存储管理目的和功能功能n主存储器的分配、回收和地址映射主存储器的分配、回收和地址映射 内存分配的主要任务是为每一道程序分配内存分配的主要任务是为每一道程序分配内存空间，使它们内存空间，使它们“各得其所各得其所”，每一道程

3、序，每一道程序完完成后回收内存空间。分配时完成地址变换，地成后回收内存空间。分配时完成地址变换，地址映射是把程序地址空间的相对地址转换成内址映射是把程序地址空间的相对地址转换成内存中的绝对地址。存中的绝对地址。存储保护存储保护 内存保护的任务是确保每道程序都在内存保护的任务是确保每道程序都在自己的内存空间运行，互不干扰。保护系自己的内存空间运行，互不干扰。保护系统程序区不被用户侵犯（有意或无意的），统程序区不被用户侵犯（有意或无意的），不允许用户程序读写不属于自己地址空间不允许用户程序读写不属于自己地址空间的数据（系统区地址空间，其他用户程序的数据（系统区地址空间，其他用户程序的地址空间）。的

4、地址空间）。 存储管理目的和功能存储管理目的和功能（续）（续）存储管理目的和功能（续）存储管理目的和功能（续）n提高主存储器的利用率提高主存储器的利用率n 减少不可用的存储空间，允许多道程序减少不可用的存储空间，允许多道程序动态共享主存。动态共享主存。n内存扩充内存扩充 n内存扩充的任务是从逻辑上来扩充内存容内存扩充的任务是从逻辑上来扩充内存容量，使用户认为系统所拥有的内存空间远量，使用户认为系统所拥有的内存空间远比其实际的内存空间大的多比其实际的内存空间大的多。对用户程序的处理步骤对用户程序的处理步骤 库链接程序装入模块装入程序编译程序产生的目标模块第一步第二步第三步内存 程序的装入和链接程

5、序的装入和链接地址重定位地址重定位n名字空间、地址空间和存储空间名字空间、地址空间和存储空间n在源程序中，是通过符号名来访问子程序和数在源程序中，是通过符号名来访问子程序和数据的，我们把程序中符号名的集合称为据的，我们把程序中符号名的集合称为“名字名字空间空间”。汇编语言源程序经过汇编，或者高级。汇编语言源程序经过汇编，或者高级语言源程序经过编译，得到的目标程序是以语言源程序经过编译，得到的目标程序是以“0”0”作为参考地址的模块。然后多个目标模块由连作为参考地址的模块。然后多个目标模块由连接程序连接成一个具有统一地址的装配模块，接程序连接成一个具有统一地址的装配模块，以便最后装入内存中执行。

6、以便最后装入内存中执行。n装配模块虽然具有统一的地址空间，但是仍装配模块虽然具有统一的地址空间，但是仍是以是以“0”0”作为参考地址，即是浮动的。要作为参考地址，即是浮动的。要把它装入内存执行，就要确定装入内存的实把它装入内存执行，就要确定装入内存的实际物理地址，并修改程序中与地址有关的代际物理地址，并修改程序中与地址有关的代码，这一过程称为地址重定位。码，这一过程称为地址重定位。n我们把目标模块中的地址称为相对地址（或称我们把目标模块中的地址称为相对地址（或称为为“逻辑地址逻辑地址”），而把相对地址的集合称为），而把相对地址的集合称为“相对地址空间相对地址空间/逻辑地址空间逻辑地址空间”或简

7、称为或简称为“地址地址空间空间”。n地址空间的程序和数据经过地址重定位处理后，就变成地址空间的程序和数据经过地址重定位处理后，就变成了可由了可由CPUCPU直接执行的绝对地址程序。我们把这一地址直接执行的绝对地址程序。我们把这一地址集合称为集合称为“绝对地址空间绝对地址空间”或或“存储空间存储空间”。程序的名。程序的名字空间、地址空间和存储空间之间的关系如图所示：字空间、地址空间和存储空间之间的关系如图所示： 源源 程程 序序相对目标程相对目标程序（装配模序（装配模块）块）绝对目标程绝对目标程序序名字空间名字空间 地址空间地址空间 相对地址相对地址/逻辑地逻辑地址空间址空间存储空间存储空间绝对

8、地址绝对地址/物理地物理地址空间址空间汇编汇编/编译编译链接链接地址重定位地址重定位装装 入入地址重定位（续地址重定位（续) )逻辑地址、物理地址和地址映射逻辑地址、物理地址和地址映射地址映射地址映射BA=1000BA=1000Load A 200 3456 。 。 。12001200物理地址空间物理地址空间Load A data1data1 3456源程序源程序Load A 200 34560 0100100200200编译连接编译连接逻辑地址空间逻辑地址空间n绝对装入方式绝对装入方式n可重定位装入方式可重定位装入方式n动态运行时装入方式动态运行时装入方式n程序的装入程序的装入1. 1. 绝

9、对装入方式绝对装入方式(Absolute Loading Mode)(Absolute Loading Mode) n如果内存位置已知，可生成绝对代码；如果开如果内存位置已知，可生成绝对代码；如果开始位置改变，需要重新编译代码。始位置改变，需要重新编译代码。n程序中所使用的绝对地址，既可在编译或汇编程序中所使用的绝对地址，既可在编译或汇编时给出，时给出， 也可由程序员直接赋予。也可由程序员直接赋予。n只能将目标模块装入到内存中事先指定的位置，只能将目标模块装入到内存中事先指定的位置，适用于单道程序环境。适用于单道程序环境。例如：读卡器，传感器结点属于绝对装入方式例如：读卡器，传感器结点属于绝对

10、装入方式n地址变换通常是在装入时一次完成的，以后不再地址变换通常是在装入时一次完成的，以后不再改变，故又称为静态重定位。改变，故又称为静态重定位。n程序重定位以后就不能在内存中移动；程序重定位以后就不能在内存中移动；n要求程序的存储空间是连续的，不能把程序存储要求程序的存储空间是连续的，不能把程序存储到若干个不连续的区域中。到若干个不连续的区域中。2. 2. 可重定位装入方式可重定位装入方式(Relocation Loading Mode)(Relocation Loading Mode) 作业装入内存时的情况作业装入内存时的情况 LOAD 1,2500365LOAD 1,2500365100

11、001100012500150005000250010000作业地址空间内存空间LOAD 1,125003. 3. 动态运行时装入方式动态运行时装入方式(Denamle Run-time Loading)(Denamle Run-time Loading) n在把装入模块装入内存后，并不立即把装入在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进这种地址转换推迟到程序真正要执行时才进行。因此，行。因此， 装入内存后的所有地址都仍是相装入内存后的所有地址都仍是相对地址。对地址。 n进程在执行时可

12、以在内存中移动。进程在执行时可以在内存中移动。n需要硬件对地址映射的支持。需要硬件对地址映射的支持。n动态重定位动态重定位LOAD 1，25003650：1001002500250026002600程序的地址空间LOAD 1，2500365100001000010100 12500 12500物理地址物理地址内存的地址空间重定位寄存器重定位寄存器中央处理器中央处理器CPUCPU指令寄存器指令寄存器LOAD 1,2500LOAD 1,25002500(2500(逻辑地址逻辑地址) )MMU(存储管理部件)CPU芯片+ +10000n静态链接静态链接(Static Linking) (Static

13、 Linking) n程序运行之前，将各目标模块及所需库函数，程序运行之前，将各目标模块及所需库函数，链接成完整的装配模块以后不再拆开，链接成完整的装配模块以后不再拆开，静态静态链接是在生成可执行文件时进行的。链接是在生成可执行文件时进行的。n动态链接动态链接(Dynamic Linking) (Dynamic Linking) n装入内存时，边装入边链接装入内存时，边装入边链接n在在装入或运行装入或运行时进行链接。时进行链接。n程序的链接程序的链接 1. 1. 静态链接方式静态链接方式模块 ACALL B；Return；0L1模块 BCALL C；Return；0M1模块 CReturn；0

14、N10模块 AJSR“L”Return；L1模块 BJSR“LM”Return；LLM1LMLMN1模块 CReturn；(a) 目标模块(b) 装入模块 在将这几个目标模块装配成一个装入模块时，在将这几个目标模块装配成一个装入模块时，须解决以下两个问题：须解决以下两个问题： (1) (1) 对相对地址进行修改。对相对地址进行修改。 (2) (2) 变换外部调用符号：将外部调用符号转变换外部调用符号：将外部调用符号转换为对定位后的逻辑地址的调用。换为对定位后的逻辑地址的调用。 2. 2. 动态链接方式动态链接方式n近几年流行起来的运行时动态链接方式，这种链接方近几年流行起来的运行时动态链接方式

15、，这种链接方式是将对某些模块的链接推迟到执行时才进行链接，式是将对某些模块的链接推迟到执行时才进行链接，亦即，在执行过程中，当发现一个被调用模块尚未装亦即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由入内存时，立即由OSOS去找到该模块并将之装入内存，去找到该模块并将之装入内存， 把它链接到调用者模块上。凡在执行过程中未被用到把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。量的内存空间。n

16、通常被链接的共享代码称为动态链接库通常被链接的共享代码称为动态链接库(DLL, (DLL, Dynamic-Link Library)Dynamic-Link Library)或共享库或共享库(shared library)(shared library)。内存管理的存储保护功能内存管理的存储保护功能n上下界保护和地址检查机构上下界保护和地址检查机构( (静态地址定位静态地址定位) ) 内存管理的功能（续内存管理的功能（续2 2）n基址、限长寄存器和动态地址转换机构（基址、限长寄存器和动态地址转换机构（动态动态地址定位地址定位） 这两中寄存器分别存放运行程序在内存的起始地址和其总长度。 2.2

17、.交换与覆盖交换与覆盖n为什么引入？为什么引入？ 在多道环境下扩充内存的方法，解决在较小的存储空在多道环境下扩充内存的方法，解决在较小的存储空间中运行较大程序时遇到的矛盾间中运行较大程序时遇到的矛盾n覆盖技术主要用在早期的操作系统中覆盖技术主要用在早期的操作系统中n交换技术被广泛用于小型分时系统中，交换技术的交换技术被广泛用于小型分时系统中，交换技术的发展导致了虚存技术的出现发展导致了虚存技术的出现n交换技术与覆盖技术共同点：交换技术与覆盖技术共同点： 进程的程序和数据主要放在外存，当前需要执行的部分进程的程序和数据主要放在外存，当前需要执行的部分放在内存，内外存之间进行信息交换放在内存，内外

18、存之间进行信息交换2.2.交换与覆盖（续交换与覆盖（续1 1）n覆盖技术覆盖技术n指一个作业的某些程序段，或几个作业的某些部分指一个作业的某些程序段，或几个作业的某些部分轮流使用某一段存储空间。轮流使用某一段存储空间。n基本思想是把内存中同一区域，静态地分配给一道基本思想是把内存中同一区域，静态地分配给一道程序的若干个子程序或数据段，在开始时只让一部程序的若干个子程序或数据段，在开始时只让一部分程序装入内存，根据运行的情况，交替轮流使用。分程序装入内存，根据运行的情况，交替轮流使用。n和单用户连续区分配、分区分配技术配合使用。和单用户连续区分配、分区分配技术配合使用。n用户需要小心设计程序的数

19、据结构，使其覆盖模块用户需要小心设计程序的数据结构，使其覆盖模块具有相对独立性。具有相对独立性。内存管理基础内存管理基础例例 2.2.交换与覆盖（续交换与覆盖（续2 2）缺点：缺点： 对用户不透明，增加了用户负担对用户不透明，增加了用户负担 例子：目前这一技术用于小型系统中的系统程例子：目前这一技术用于小型系统中的系统程序的内存管理上，序的内存管理上，MS-DOSMS-DOS的启动过程中，多次的启动过程中，多次使用覆盖技术；启动之后，用户程序区使用覆盖技术；启动之后，用户程序区TPATPA的的高端部分与高端部分与COMMAND.COMCOMMAND.COM暂驻模块也是一种覆暂驻模块也是一种覆盖

20、结构盖结构 2.2.交换与覆盖（续交换与覆盖（续3 3）n交换技术交换技术n当内存空间紧张时当内存空间紧张时，系统将内存中某些进程暂时移，系统将内存中某些进程暂时移到外存，把外存中某些进程换进内存，占据前者所到外存，把外存中某些进程换进内存，占据前者所占用的区域，这种技术是进程在内存与外存之间的占用的区域，这种技术是进程在内存与外存之间的动态调度动态调度n多用于分时系统中多用于分时系统中n使用外存做缓存，通过不断换出换入而运行大作业使用外存做缓存，通过不断换出换入而运行大作业n分分进程交换进程交换和和部分交换部分交换（页面交换和分段交换）（页面交换和分段交换）n提高内存利用率，增加并发进程数，

21、提高系统效率提高内存利用率，增加并发进程数，提高系统效率n交换使用的技术较多：交换使用的技术较多：换出进程的选择、交换时机换出进程的选择、交换时机的确定、需要一个盘交换区及管理、换入回内存时的确定、需要一个盘交换区及管理、换入回内存时位置的确定等位置的确定等3.3.连续分配管理方式连续分配管理方式（1 1）单一连续存储管理）单一连续存储管理n基本原理基本原理 n将内存划分为系统区和用户区；将内存划分为系统区和用户区；n内存中仅驻留一道程序，整个系统资源和用户区只内存中仅驻留一道程序，整个系统资源和用户区只为一个用户所独占；为一个用户所独占；n仅适用于单用户、单任务操作系统。仅适用于单用户、单任

22、务操作系统。 内存管理基础内存管理基础（1 1）单一连续存储管理（续）单一连续存储管理（续1 1）n主存空间的分配与回收主存空间的分配与回收n主存空间的分配主存空间的分配 ：系统区和用户区系统区和用户区 n主存空间的回收主存空间的回收 ：运行结束，释放主存空间：运行结束，释放主存空间 作业作业 1 1装入程序装入程序操作系统区操作系统区作业作业1 1的的程序和数据程序和数据界限地址界限地址界限地址界限地址+ +逻辑地址逻辑地址内存管理基础内存管理基础（1 1）单一连续存储管理（续）单一连续存储管理（续2 2）n优缺点优缺点n简单、易实现简单、易实现n仅适合单道程序，处理机和内存不能充分利用仅适

23、合单道程序，处理机和内存不能充分利用n基本原理基本原理 n预先把可分配的内存空间分割成若干个连续区域，预先把可分配的内存空间分割成若干个连续区域，每一区域称为分区每一区域称为分区n每个分区的大小可以相同也可以不同，分区大小固每个分区的大小可以相同也可以不同，分区大小固定不变，每个分区装一个且只能装一个作业定不变，每个分区装一个且只能装一个作业n存储分配：如果有一个空闲区，则分配给进程存储分配：如果有一个空闲区，则分配给进程（2 2）固定分区存储管理）固定分区存储管理内存管理基础内存管理基础固定分区存储管理是最早使用的一种运行多道程固定分区存储管理是最早使用的一种运行多道程序的存储管理方式。序的

24、存储管理方式。（2 2）固定分区存储管理（续）固定分区存储管理（续1 1）n主存空间的分配与回收主存空间的分配与回收 n数据结构与主存分区分配表数据结构与主存分区分配表 内存管理基础内存管理基础( (a a) )分区说明表分区说明表( (b b) )存储空间分配表存储空间分配表分区号分区号大小大小（K K ）起址地址（起址地址（K K）状态状态1 18 81616JobJob1 12 2161624240 03 316164040JobJob2 24 432325656JobJob3 3操作系统操作系统JobJob1 10 0JobJob2 2JobJob3 30 01616K K2424K

25、K4040K K5656K K（2 2）固定分区存储管理（续）固定分区存储管理（续2 2）固定式分区表固定式分区表 ( (a a) )分区号分区号1 12 23 34 45 5大小大小8 8 KBKB3232 KBKB3232 KBKB120120 KBKB520520 KBKB起始地址起始地址312312 KBKB320320 KBKB352352 KBKB384384 KBKB504504 KBKB状态状态在使用在使用在使用在使用在使用在使用未用未用未用未用( (b b) )操作系统操作系统504 KB504 KB384 KB384 KB352 KB352 KB320 KB320 KB31

26、2 KB312 KB0 0520 KB520 KB120 KB120 KB32 KB32 KB32 KB32 KB8 KB8 KB312 KB312 KB状态栏的值为状态栏的值为0，表示未分配，作业装入后改成作，表示未分配，作业装入后改成作业名。业名。固定式分区举例固定式分区举例 分区号分区号 分区容量分区容量 作业容量作业容量 剩余容量剩余容量 1 12 23 34 45 58KB8KB32KB32KB32KB32KB120KB120KB520KB520KB1KB1KB9KB9KB9KB9KB33KB33KB121KB121KB7KB7KB23KB23KB23KB23KB87KB87KB39

27、9KB399KB合合 计计 712 KB 712 KB 173 KB 173 KB 539 KB 539 KB 操作系统操作系统504 KB504 KB384 KB384 KB352 KB352 KB320 KB320 KB312 KB312 KB0 0520 KB520 KB120 KB120 KB32 KB32 KB32 KB32 KB8 KB8 KB312 KB312 KBJ1J1J2J2J3J3J4J4J5J5内存利用内存利用率不高率不高（2 2）固定分区存储管理（续）固定分区存储管理（续3 3）管理特点管理特点 n一个作业只能装入一个分区。当一个分区的大小不一个作业只能装入一个分区。

28、当一个分区的大小不能满足一个作业的要求时，该作业暂时不能装入。能满足一个作业的要求时，该作业暂时不能装入。n通过对通过对“分区分配表分区分配表”的改写，来实现主存的分配的改写，来实现主存的分配与回收。简单、易行，适合多道程序设计。与回收。简单、易行，适合多道程序设计。n当分区较大而作业较小时，容易形成碎片，造成主当分区较大而作业较小时，容易形成碎片，造成主存空间的浪费。存空间的浪费。n这种方式分区总数固定，也限制了并发执行的作业这种方式分区总数固定，也限制了并发执行的作业数目。数目。 定义：在存储分配过程中，分配给用户而未被利用的定义：在存储分配过程中，分配给用户而未被利用的 那部分内存，称为

29、内存的那部分内存，称为内存的“内零头内零头”或或“内碎内碎片片”作业进入时有两种作业排队策略作业进入时有两种作业排队策略（3 3）可变分区存储管理）可变分区存储管理n基本思想基本思想n内存不是预先划分好分区的，而是根据装入作业的内存不是预先划分好分区的，而是根据装入作业的实际需要动态地划分存储空间。分区的个数和大小实际需要动态地划分存储空间。分区的个数和大小是不固定的是不固定的n作业装入时，根据作业的需求和内存空间的使用情作业装入时，根据作业的需求和内存空间的使用情况来决定是否分配况来决定是否分配n若有足够的空间，则按需要分割一部分分区给该若有足够的空间，则按需要分割一部分分区给该进程；进程；

30、n否则令其等待内存空间否则令其等待内存空间（3 3）可变分区存储管理（续）可变分区存储管理（续1 1）n主存空间的分配主存空间的分配n数据结构数据结构n分区分配表分区分配表 n空闲分区表空闲分区表n分区分配与回收操作分区分配与回收操作n动态分配动态分配n三种分配算法：三种分配算法：首次适应算法、最佳适应算法、首次适应算法、最佳适应算法、最坏适应算法最坏适应算法（3 3）可变分区存储管理（续）可变分区存储管理（续2 2）可变分区的分配和回收示例可变分区的分配和回收示例J1J1J2J2J3J3J4J4J1J1J2J2J3J3J4J4J5J5J6J6分配策略分配策略/算法算法n 首次首次/ /最先适

31、应最先适应First fitFirst fit：n空白区按地址大小递增顺序排列。查找分空白区按地址大小递增顺序排列。查找分区说明表，找到第一个满足申请长度的空区说明表，找到第一个满足申请长度的空闲区，分配并分割。剩余部分保留在空白闲区，分配并分割。剩余部分保留在空白区表中原来的位置。区表中原来的位置。n最先适应算法：尽可能利用存储器的低地最先适应算法：尽可能利用存储器的低地址部分，因此在低地址部分会很快地产生址部分，因此在低地址部分会很快地产生大量碎片。大量碎片。n 最佳适应（最优）最佳适应（最优） Best fit Best fit ：n空白区表中的空白区按其空白区表中的空白区按其容量以递增

32、容量以递增的次序的次序排列。当要求分配一个空白区时，由小到大排列。当要求分配一个空白区时，由小到大顺序查找分区说明表，找到第一个满足申请顺序查找分区说明表，找到第一个满足申请长度的最小空闲区，分配并分割。如果有剩长度的最小空闲区，分配并分割。如果有剩余部分，作为一个空白区将其插入适当的位余部分，作为一个空白区将其插入适当的位置；置；n最佳适应算法：选择容量接近的空闲区来分最佳适应算法：选择容量接近的空闲区来分配，产生大量碎片。配，产生大量碎片。n 最差适应（最坏）最差适应（最坏） Worst fit Worst fit ：n空白区表中的空白区按其空白区表中的空白区按其容量以递减容量以递减的次的

33、次序排列。查找分区说明表，找到第一个满序排列。查找分区说明表，找到第一个满足申请长度的空闲区，分配并分割。剩余足申请长度的空闲区，分配并分割。剩余部分插入适当位置。部分插入适当位置。n最差适应算法：分割大空闲区后，还可以最差适应算法：分割大空闲区后，还可以产生较大的空闲区，空闲区均匀地减小，产生较大的空闲区，空闲区均匀地减小，以避免碎片。以避免碎片。n 唯一最佳适应算法（唯一最佳适应算法（single best fitsingle best fit）n分区按大小顺序分级（分区按大小顺序分级（8KB8KB、16KB16KB、32 32 KBKB、 ）n作业按请求容量也分成相应的存储级，仅当作业按

34、请求容量也分成相应的存储级，仅当PDTPDT中相应级的分区为空闲时，才进行内存分中相应级的分区为空闲时，才进行内存分配，即使有更大的分区空闲也不予以分配。配，即使有更大的分区空闲也不予以分配。（3 3）可变分区存储管理（续）可变分区存储管理（续3 3）n内存回收内存回收 当某一块归还后，前后空间合并，修改内存空当某一块归还后，前后空间合并，修改内存空 闲块表闲块表 考虑：上邻、下邻、上下相邻、上下不相邻考虑：上邻、下邻、上下相邻、上下不相邻n “ “碎片碎片”问题问题 经过一段时间的分配回收后，内存中存在很多小的空经过一段时间的分配回收后，内存中存在很多小的空闲块。它们每一个都很小，不足以满足

35、分配要求；但闲块。它们每一个都很小，不足以满足分配要求；但其总和满足分配要求。这些空闲块被称为其总和满足分配要求。这些空闲块被称为外碎片外碎片 造成存储资源的浪费造成存储资源的浪费申请分配一个申请分配一个XKBXKB大小的分区大小的分区置空白区号置空白区号f f =1=1f f 大于最后大于最后一个空白区号？一个空白区号？空白区可用？空白区可用？保存空白区的起始地址保存空白区的起始地址空白区空白区 f f的大小的大小x xKBKB空白区的空白区的状态状态= =空项空项修改空白区的大小修改空白区的大小和起始地址和起始地址在已分配表中找一个状在已分配表中找一个状态态= =空项的分区号空项的分区号

36、P P置分区置分区P P的大小为的大小为 x xKBKB置分区起始地址置分区起始地址置分区状态为已分配置分区状态为已分配返回一个返回一个分区号分区号此次无法分配此次无法分配f f +1 +1 f fY YY YN NN N = =可变式分区中请求一个分区的流程可变式分区中请求一个分区的流程可变式分区中释放一个分区的流程可变式分区中释放一个分区的流程 请求释放请求释放一个分区一个分区 P P保存分区保存分区P P的的大小和起始地址大小和起始地址置分区的置分区的状态为空项状态为空项分区分区P P有邻有邻接的空白区接的空白区? ?修改新空白区的大小修改新空白区的大小起始地址和状态起始地址和状态返回返

37、回修改空白修改空白区的状态区的状态修改新空白区的修改新空白区的大小和起始地址大小和起始地址在未分配表在未分配表中找一空表目中找一空表目置新空白区大小置新空白区大小和起始地址和起始地址置空白区状置空白区状态为可用态为可用在两个空在两个空白区之间白区之间有一个有一个空白区空白区N N（4 4）可再定位式分区分配）可再定位式分区分配n“碎片碎片”问题解决问题解决 内存中存在许多不能充分利用的小空闲区，降低了多道内存中存在许多不能充分利用的小空闲区，降低了多道程序设计的程度，还造成内存空间的严重浪费。程序设计的程度，还造成内存空间的严重浪费。 紧凑技术紧凑技术： 通过在内存移动程序，将所有小的空闲区域

38、合并为大通过在内存移动程序，将所有小的空闲区域合并为大的空闲区域的空闲区域 （又称：紧缩技术，紧致技术，浮动技术，搬家技术）（又称：紧缩技术，紧致技术，浮动技术，搬家技术） 问题问题：系统开销系统开销 大大 移动时机移动时机 ？可再定位式分区分配的靠拢过程 作业7(256 KB)(a)(b)(c)作业6 (256 KB)作业5 (128 KB)作业4 (24 KB)作业1 (8 KB)OS作业7 (256 KB)作业6 (256 KB)作业5 (128 KB)作业4 (24 KB)作业1(8 KB)OS01024 KB504 KB352 KB320 KB312 KB888 KB652 KB37

39、6 KB作业6 (256 KB)作业5 (128 KB)作业4 (24 KB)作业1 (8 KB)OS 只要改变浮动寄存器的内容利用浮动寄存器进行地址变换 L 1，352 K + 980001557100352 KB352 KB + 50352 KB + 9800376 KB352 KB + 9800-32 KB+L 1，352 KB + 980001557100320KB320 KB + 50320 KB + 9800344 KB计算地址地址变换有效地址浮动寄存器再定位寄存器或称为浮动寄存器实现地址变换：320k-352K=-32K当执行每条指令时，由CPU计算出有效地址，在访问操作数之前，

40、将浮动寄存器的内容与计算出的有效地址相加，得到实际的物理地址。即在移到新的位置后作业的指令和数据都没有改变，在执行时利用浮动寄存器自动完成地址变换的。例如：指令L 1,352KB+9800的执行，仍将位于320KB+9800处的数据01557100取至1号寄存器。可再定位式分区分配算法流程可再定位式分区分配算法流程 请求分配请求分配一个大小为一个大小为x xKBKB 的分区的分区有大于有大于x xKBKB 的空白区的空白区吗？吗？空白区的总空白区的总和和x xKBKB执行靠拢操作执行靠拢操作并修改状态表并修改状态表分配一个分区并修分配一个分区并修改状态表改状态表返回一个返回一个分区号分区号此时

41、无此时无法分配法分配Y YY YN NN N（5 5）分区的保护措施）分区的保护措施 作业作业 2 2的分区的分区60 KB60 KB124 KB124 KB256 KB256 KB0 060 KB60 KB基址寄存器基址寄存器64 KB64 KB限长寄存器限长寄存器作业作业 2 2的分区的分区60 KB60 KB124 KB124 KB256 KB256 KB0 060 KB60 KB下界寄存器下界寄存器124 KB124 KB上界寄存器上界寄存器使用界地址保户和存储键保护使用界地址保户和存储键保护n总结总结n分区存储管理要求把作业的地址空间装入到连续的存分区存储管理要求把作业的地址空间装入

42、到连续的存储空间内储空间内n在动态分区的存储管理中，常常由于存在一些不足以在动态分区的存储管理中，常常由于存在一些不足以装入任何作业的小的分区而浪费掉部分存储空间装入任何作业的小的分区而浪费掉部分存储空间- -碎片碎片n采用采用“内存紧凑内存紧凑”技术可以解决碎片问题，但要移动技术可以解决碎片问题，但要移动大量指令和数据，花费处理机时间，代价比较高。大量指令和数据，花费处理机时间，代价比较高。如何改进？如何改进？非连续分配管理非连续分配管理 4.4.非连续分配管理方式非连续分配管理方式（1 1）简单分页存储管理）简单分页存储管理n基本思想基本思想n等分内存等分内存 把内存存储空间划分成大小相等

43、的单位，称为存储把内存存储空间划分成大小相等的单位，称为存储块，或页框（块，或页框（Page FramePage Frame）n用户逻辑地址空间分页用户逻辑地址空间分页 把用户逻辑地址空间划分成大小相等的单位，称为把用户逻辑地址空间划分成大小相等的单位，称为 页面或页（页面或页（PagePage）。给各页从）。给各页从0 0开始编制页号，开始编制页号，页页 内地址是相对于内地址是相对于0 0编址编址 （1 1）简单分页存储管理（续）简单分页存储管理（续1 1）n逻辑地址的表示逻辑地址的表示n用户的逻辑地址从基址用户的逻辑地址从基址0 0开始编址，即是相对地址。开始编址，即是相对地址。n每个相对

44、地址用一个数对（每个相对地址用一个数对（p,wp,w）表示，）表示，p p是页号，是页号，w w是页内地址，是该页内的偏移量是页内地址，是该页内的偏移量2 21010=1K=1K2 21111=2K=2K2 21212=4K=4Kn逻辑地址与页号及页内偏移地址之间的逻辑地址与页号及页内偏移地址之间的PageNoPageNo = INT = INTAddrAddr/ /PageLengthPageLength PageOffset PageOffset = = AddrAddr MOD MOD PageLengthPageLength举例：对于举例：对于1KB1KB页面，若给定逻辑地址页面，若给

45、定逻辑地址2170B2170B，则，则 PageNoPageNo = 2= 2，PageOffset PageOffset = 122= 122n页的划分是由系统自动完成的，对用户是透明的。页的划分是由系统自动完成的，对用户是透明的。一页的大小为一页的大小为2 2的整数次幂的整数次幂，地址的高位部分为，地址的高位部分为页号，低位部分为页内地址页号，低位部分为页内地址n页面大小选择页面大小选择n由机器的地址结构所决定由机器的地址结构所决定n页面大页面大/ /小评析小评析n2 210-10-2 21212KBKB之间之间例例 设一个逻辑地址空间有设一个逻辑地址空间有8 8页，每页页，每页10241

46、024字节，字节，映射到映射到3232块的物理内存上。试问：块的物理内存上。试问：（1 1）逻辑地址空间需要多少位来表示？）逻辑地址空间需要多少位来表示？（2 2）物理地址空间需要多少位来表示？）物理地址空间需要多少位来表示？（1 1）逻辑地址空间需要）逻辑地址空间需要1313位来表示。其中页号需要位来表示。其中页号需要3 3位，因为位，因为2 23 3=8=8；页内地址需要；页内地址需要1010位，因为位，因为2 21010=1024=1024。（2 2）物理地址空间需要）物理地址空间需要1515位来表示。其中块号需要位来表示。其中块号需要5 5位，因为位，因为2 25 5=32=32；块内

47、地址需要；块内地址需要1010位，因为位，因为2 21010=1024=1024。（1 1）简单分页存储管理（续）简单分页存储管理（续2 2）n主存空间的分配与回收主存空间的分配与回收 n内存分配原则内存分配原则n作业的逻辑地址是连续的，用户在编制程序时仍作业的逻辑地址是连续的，用户在编制程序时仍只须使用顺序的地址，而不必考虑如何去分页。只须使用顺序的地址，而不必考虑如何去分页。n由地址转换机构和操作系统管理来决定页面和主由地址转换机构和操作系统管理来决定页面和主存分块的大小。存分块的大小。n用户进程在主存空间中的每个页框内的地址是连用户进程在主存空间中的每个页框内的地址是连续的，但页框和页框

48、之间的地址可以不连续。续的，但页框和页框之间的地址可以不连续。 存储地址由连续到离散的变化，存储地址由连续到离散的变化，即分配时，即分配时，逻辑上相邻的页，物理上不一定相邻的快逻辑上相邻的页，物理上不一定相邻的快 （1 1）简单分页存储管理（续）简单分页存储管理（续3 3）n采用的数据结构采用的数据结构 n页表页表：系统为每个进程建立一个页表，页表给出逻辑：系统为每个进程建立一个页表，页表给出逻辑页号和具体内存块号相应的关系。页号和具体内存块号相应的关系。页表放在内存，属页表放在内存，属于进程的现场信息于进程的现场信息n作业表作业表：也叫主存分配表，包括作业名，作业对应页：也叫主存分配表，包括

49、作业名，作业对应页表的起始地址和页表的长度。内存中的每个作业在作表的起始地址和页表的长度。内存中的每个作业在作业表中有一个登记项。整个系统只有一张作业表。业表中有一个登记项。整个系统只有一张作业表。n位示图位示图：空闲块管理。页式存储管理以块为单位分配：空闲块管理。页式存储管理以块为单位分配主存空间，由于块的大小是固定的，所以只要在主存主存空间，由于块的大小是固定的，所以只要在主存分配表中指出哪些块已分配和哪些块未分配以及当前分配表中指出哪些块已分配和哪些块未分配以及当前剩余的空闲块数。最简单的办法是用一张剩余的空闲块数。最简单的办法是用一张“位示图位示图”构成主存分配表。构成主存分配表。 0

50、 0页页1 1页页2 2页页3 3页页4 4页页5 5页页n n页页用户程序用户程序0 012121 113132 216163 318184 419195 51717n n页表页表页号页号块号块号第第1212块块第第1313块块第第1414块块第第1515块块第第1616块块第第1717块块第第1818块块第第1919块块内存内存（1 1）简单分页存储管理（续）简单分页存储管理（续3 3）作业作业2 2( (0 0页页) )操作系统操作系统作业作业2 2( (1 1页页) )作业作业3 3( (0 0页页) )作业作业1 1( (0 0页页) )作业作业1 1( (1 1页页) )作业作业2

51、 2( (2 2页页) )0 05 51 16 60 01 12 22 24 47 70 08 8作业作业1 1作业作业2 2作业作业3 31 KB1 KB2 KB2 KB0 00 01 KB1 KB2 KB2 KB0 03 KB3 KB1 KB1 KB0 0逻辑地址空间逻辑地址空间页面变换表页面变换表物理地址空间物理地址空间页号页号 块号块号1 KB1 KB2 KB2 KB3 KB3 KB4 KB4 KB5 KB5 KB6 KB6 KB7 KB7 KB8 KB8 KB9 KB9 KB10 KB10 KB（1 1）简单分页存储管理（续）简单分页存储管理（续4 4）（1 1）简单分页存储管理（续

52、）简单分页存储管理（续5 5）空闲块管理空闲块管理位示图位示图块号字长块号字长字号位号字长字号位号字长i ij j （i i和和j j的编号都是从的编号都是从0 0开始）开始） （1 1）简单分页存储管理（续）简单分页存储管理（续6 6）n内存的分配与回收内存的分配与回收n计算一个进程所需要的总块数计算一个进程所需要的总块数N Nn查位示图：是否还有查位示图：是否还有N N个空闲块个空闲块n如果有足够的空闲块，则页表长度设为如果有足够的空闲块，则页表长度设为N N，可填，可填入入PCBPCB中；申请页表区，把页表始址填入中；申请页表区，把页表始址填入PCB PCB n依次分配依次分配N N个空

53、闲块，将块号和页号填入页表个空闲块，将块号和页号填入页表n修改位示图修改位示图请求分配请求分配x xKBKB的地址空间的地址空间计算所需块数计算所需块数N NN N=x xKB/4KBKB/4KB有有N N个可个可用的块？用的块？在作业表中找空表目置页在作业表中找空表目置页表长度表长度= =N N，状态，状态= =已分配已分配分配该作业的分配该作业的PMTPMT 表，并在表，并在作业表中登记该作业表中登记该PMTPMT 的始址的始址检查内存分块表，分配检查内存分块表，分配N N个可个可用存储块，在每块的状态栏用存储块，在每块的状态栏内填入作业序号，再将存储内填入作业序号，再将存储块号填入块号填

54、入 PMTPMT 表表返回返回本次无法分配本次无法分配N NY Y分页存储分配算法流程分页存储分配算法流程 （1 1）简单分页存储管理（续）简单分页存储管理（续7 7）n地址变换机构地址变换机构 由硬件实现，操作系统配合。由硬件实现，操作系统配合。 关键在于页号到物理块号的转变关键在于页号到物理块号的转变n系统设置一对寄存器系统设置一对寄存器n页表始址寄存器页表始址寄存器 用于保存正在运行进程的页表的始址用于保存正在运行进程的页表的始址n页表长度寄存器页表长度寄存器 用于保存正在运行进程的页表的长度用于保存正在运行进程的页表的长度n地址变换过程地址变换过程 见下图见下图地址变换机构地址变换机构

55、位移量位移量进程进程地址变换机构地址变换机构内存内存有效地址有效地址页表寄存器页表寄存器块号块号页框页框页页号号块号块号页号页号块号块号位移量位移量+ +页表始址页表始址 页表长度页表长度页表页表物理地址物理地址块号块号位移量位移量PCBPCB页表始址页表始址页表长度页表长度 越界中断越界中断1 12 23 34 45 5红线部分的工红线部分的工作在进程被调作在进程被调度时由调度程度时由调度程序完成序完成绝对地址计算：绝对地址计算：块号块号块长页内地址块长页内地址 页表始址页表始址页表长度页表长度页表寄存器页表寄存器页号页号(3)(3)逻辑地址寄存器逻辑地址寄存器BlockNoBlockNo页

56、表页表BlockNoBlockNo物理地址寄存器物理地址寄存器+ +越界中断越界中断页号页号物理块号物理块号0 01 12 23 3地址变换例地址变换例1 1n页式存储系统的逻辑地址是由页号和页内地址两部分页式存储系统的逻辑地址是由页号和页内地址两部分组成，地址变换过程如图所示。假定页面的大小为组成，地址变换过程如图所示。假定页面的大小为8K8K，计算图中所示的十进制逻辑地址计算图中所示的十进制逻辑地址96129612经过地址变换后，经过地址变换后，形成的物理地址形成的物理地址a a应为多少？应为多少？ 地址变换例地址变换例2 2 某分页系统的逻辑地址为某分页系统的逻辑地址为1616位，其中高

57、位，其中高6 6位为页号，低位为页号，低1010位为页内地址。请问：位为页内地址。请问： （1 1）这样的地址结构一页有多少字节？逻辑地址）这样的地址结构一页有多少字节？逻辑地址可有多少页？一个作业最大的使用空间是多少？可有多少页？一个作业最大的使用空间是多少？ （2 2）逻辑地址）逻辑地址23182318、40964096、850850对应的页号、页对应的页号、页 内地址分别是多少？内地址分别是多少？ （1 1）简单分页存储管理（续）简单分页存储管理（续8 8）n相联存储器相联存储器快表快表 用途用途：为了提高地址映射速度：为了提高地址映射速度( (两次读内存两次读内存) ) 保存正在运行进

58、程的页表的子集（部分页保存正在运行进程的页表的子集（部分页 表项）表项） 特点特点：按内容并行查找：按内容并行查找 快表表项快表表项： 页号；内存块号；页号；内存块号；n具有块表地址变换过程具有块表地址变换过程 见下图见下图 n页表空间问题页表空间问题n现代计算机系统支持非常大的逻辑地址空间现代计算机系统支持非常大的逻辑地址空间(2(23232226464) )，页表变得庞大。例如，对于具有页表变得庞大。例如，对于具有3232位逻辑地址空间的分位逻辑地址空间的分页系统，规定页面大小为页系统，规定页面大小为4KB4KB即即2 21212B B，则每个进程页表，则每个进程页表的页表项可达的页表项可

59、达1M1M个；若同时设定页表项大小为个；若同时设定页表项大小为4B4B，则每，则每个进程仅页表便需占用个进程仅页表便需占用4MB 4MB 内存空间，且要求是连续的。内存空间，且要求是连续的。n解决方案解决方案 多级页表多级页表( (页表分页及对换页表分页及对换) )或反置页表或反置页表 一个简单的解决方法是使用两层分页方法，就是将页表再一个简单的解决方法是使用两层分页方法，就是将页表再分页，如下图所示。分页，如下图所示。分页存储管理方案的评价分页存储管理方案的评价 n采用动态地址变换会增加计算机硬件成本和采用动态地址变换会增加计算机硬件成本和 降低处理机的速度。降低处理机的速度。n各种表格要占

60、用一定容量的主存空间，各种表格要占用一定容量的主存空间， 而且而且还要花费一部分处理机时间用来建立和管理这还要花费一部分处理机时间用来建立和管理这些表格。些表格。n虽然说碎片消除了，但每个作业的最后一页一虽然说碎片消除了，但每个作业的最后一页一般都有不能充分利用的空白区般都有不能充分利用的空白区( (内碎片内碎片) )。n存储扩充问题仍未得到解决。存储扩充问题仍未得到解决。（2 2）段式存储管理）段式存储管理 段式存储管理方式的引入主要是为了满足程序段式存储管理方式的引入主要是为了满足程序员在编程和使用上的要求。员在编程和使用上的要求。n基本思想基本思想n 用户程序划分用户程序划分 按程序自身