操作系统原理第6章存储器管理

1、操作系统原理操作系统原理Operating System Principles四川大学计算机学院段 磊2014 Spring第第6章章 存储器管理存储器管理n 计算机的存储系统主要包括内存储器和外存储器。n 外存储器保存的信息必须进入内存储器后才能被处理器运行。n 存储器管理是操作系统的主要功能之一。n 内存管理分为连续管理方式和离散管理方式。2022-6-8计算机操作系统- 第6章3/130知识点分布难点难点高级知识高级知识 中级知识中级知识 基础知识基础知识进程进程同步同步信号量信号量虚存虚存页面分配页面分配页面置换页面置换分页分段分页分段文件系统文件系统I/O磁盘管理磁盘管理 实践教学实

2、践教学2022-6-8计算机操作系统- 第6章4/130讲在前面存储管理目的n操作系统的“方便”性n便于用户装入程序，无须了解底层细节n可实现动态的存储空间伸缩，适应不同程序的需要n操作系统的“合理”性n合理分配内存空间，保证多道程序的顺利运行n合理保护内存空间，防止各种可能的破坏泄漏n操作系统的“有效”性n有效保持内存空间的可用性，防止对资源的浪费n有效实现“小空间大容量”，提高计算机的适应性n有效配合CPU的调度过程，实现系统运行的稳定2022-6-8计算机操作系统- 第6章5/130讲在前面存储管理目的n使得用户和用户程序不涉及内存物理的细节。 n为用户程序完成程序的装入。 n提高内存的

3、利用率，弥补用户对内存容量的需求与内存实际容量之间的差距。 n解决内存速度与CPU速度不匹配的问题。n实现内存共享。2022-6-8计算机操作系统- 第6章6/130讲在前面存储管理的功能n内存的管理、分配与回收n空间的使用情况记录位图、分配表、分区表n空间的分配与回收定长与不定长、静态与动态n地址重定位（地址映射）n物理地址与逻辑地址的差别n实模式与保护模式n共享与保护n内存共享：进程与线程、中间件应用n内存保护：如何防止地址越界或操作越权？n内存的扩充n虚拟存储：如何使用小内存空间来运行大的程序？2022-6-8计算机操作系统- 第6章7/130讲在前面地址空间n 程序的名空间n 用户编程

4、所用的地址称为逻辑地址(或程序地址，或虚地址)。 由逻辑地址组成的空间称为逻辑地址空间(或程序地址空间)。n 内存的每个存储单元都有一个编号，这种编号称为内存地址(或称为物理地址，绝对地址)。 内存地址的集合称为内存空间(或物理地址空间)。2022-6-8计算机操作系统- 第6章8/130地址映射地址映射Load A 200 3456 。 。物理地址空间物理地址空间Load A data1data1 3456源程序源程序Load A 200 3456编译编译连接连接逻辑地址空间逻辑地址空间 源程序经过汇编或编译后，形成目标程序，每个目标程源程序经过汇编或编译后，形成目标程序，每个目标程序都是以

5、序都是以0 0为基址顺序进行编址的，原来用符号名访问的单为基址顺序进行编址的，原来用符号名访问的单元用具体的数据元用具体的数据单元号取代。单元号取代。 这样生成的目标程序占据一定的地址空间，称为作业的这样生成的目标程序占据一定的地址空间，称为作业的逻辑地址空间，简称逻辑空间。逻辑地址空间，简称逻辑空间。 在逻辑空间中每条指令的地址和指令中要访问的操作数在逻辑空间中每条指令的地址和指令中要访问的操作数地址统称为逻辑地址。地址统称为逻辑地址。讲在前面地址空间2022-6-8计算机操作系统- 第6章9/130地址映射地址映射Load A 200 3456 。 。1200物理地址空间物理地址空间Loa

6、d A data1data1 3456源程序源程序Load A 200 34560100200编译编译连接连接逻辑地址空间逻辑地址空间BA=1000 把内存分成若干个大小相等的存储单元，每个单元给一个把内存分成若干个大小相等的存储单元，每个单元给一个编号，这个编号称为内存地址（物理地址、绝对地址、实地编号，这个编号称为内存地址（物理地址、绝对地址、实地址），存储单元占址），存储单元占8 8位，称作字节（位，称作字节（bytebyte）。）。 物理地址的集合称为物理地址空间（主存地址空间），它物理地址的集合称为物理地址空间（主存地址空间），它是一个一维的线性空间。是一个一维的线性空间。讲在前面地

7、址空间2022-6-8计算机操作系统- 第6章10/130讲在前面存储管理的方案n分区存储管理n段式存储管理n页式存储管理n段页式存储管理n交换和覆盖技术n是一种连续存储管理方案，但需要一次性全部装入内存。n是一种不连续存储管理方案，段和段之间可以不连续，但需要一次性全部装入内存。n是一种不连续存储管理方案，也需要一次性全部装入内存。n是一种不连续存储方案，如果采用纯分页和分段思想，需要一次性全部装入内存；如果采用虚拟存储思想，则不需要一次性全部装入内存。n是存储扩充的两种技术，其中交换技术的优点是编写程序时不需要特殊的控制，也不会影响程序的结构。2022-6-8计算机操作系统- 第6章11/

8、130本章目录n6.1 存储器管理概述 n存储器的层次n程序准备执行n覆盖技术n紧凑技术n对换技术n6.2 连续存储空间管理 n6.3 分页式存储管理 n6.4 分段式存储管理 2022-6-8计算机操作系统- 第6章12/1306.1.1 存储器的层次存储空间的分类与性质2022-6-8计算机操作系统- 第6章13/130计算机系统存储层次示意解决主存访问速度 vs CPU指令执行速度的矛盾减少访存次数，提高程序执行速度减少访问磁盘的次数,并提供对主存空间的扩充2022-6-8计算机操作系统- 第6章14/1306.1.2 程序的准备执行n相关知识回顾n进程创建n高级调度（作业调度）n程序的

9、执行过程n编译：源代码形成（多个）目标模块n链接：链接相关库函数，形成装入模块n装入：装入内存n运行2022-6-8计算机操作系统- 第6章15/130程序的准备执行2022-6-8计算机操作系统- 第6章16/130程序的准备执行-链接n静态链接n对相对地址的修改n变换外部调用符号n装入时链接n便于修改和更新n便于实现对目标模块的共享n运行时动态链接形成一个完整的装入模块，即形成一个完整的装入模块，即可执行文件，运行时直接装入可执行文件，运行时直接装入内存。内存。边装入，边链接，即在装入过边装入，边链接，即在装入过程中发生调用事件，由装入程程中发生调用事件，由装入程序找到对应模块，装入内存。

10、序找到对应模块，装入内存。执行过程中发生调用事件，找执行过程中发生调用事件，找到对应模块装入内存并链接到到对应模块装入内存并链接到调用模块上。调用模块上。 统称统称“动态链接动态链接”，被链接，被链接的共享代码称为动态链接库的共享代码称为动态链接库DLLDLL(Dynamic Link Library)(Dynamic Link Library)或共或共享库享库(shared library)(shared library)。2022-6-8计算机操作系统- 第6章17/130模块模块A ACALL BCALL B；RETURNRETURN模块模块B BCALL CCALL C；RETURNR

11、ETURN模块模块C CRETURNRETURN0 0L-1L-10 0M-1M-10 0N-1N-1(a)(a)目标模块目标模块模块模块A AJSR L;JSR L;RETURNRETURN模块模块B BJSR L+M;JSR L+M;RETURNRETURN模块模块C CRETURNRETURN0 0L-1L-1L LL+M-1L+M-1L+ML+ML+M+N-1L+M+N-1(b)(b)装入模块装入模块程序的准备执行-静态链接2022-6-8计算机操作系统- 第6章18/130程序的准备执行-动态链接n动态链接n优点共享：共享：多个进程可以共用一个多个进程可以共用一个DLLDLL，比较节

12、省内存，从而，比较节省内存，从而可以减少文件的交换。可以减少文件的交换。n缺点部分装入：部分装入：一个进程可以将多种操作分散在不同的一个进程可以将多种操作分散在不同的DLLDLL中中实现，而只将当前操作的实现，而只将当前操作的DLLDLL装入内存。装入内存。便于局部代码修改：便于局部代码修改：即便于代码升级和代码重用；只要即便于代码升级和代码重用；只要函数的接口参数函数的接口参数( (输入和输出输入和输出) )不变，则修改函数及其不变，则修改函数及其DLLDLL时，无需对可执行文件重新编译或链接。时，无需对可执行文件重新编译或链接。便于适应运行环境：便于适应运行环境：调用不同的调用不同的DLL

13、DLL，就可以适应多种使，就可以适应多种使用环境并提供不同的功能。用环境并提供不同的功能。 增加了程序执行时的链接开销。增加了程序执行时的链接开销。 程序由多个文件组成，因此增加程序由多个文件组成，因此增加了管理复杂度。了管理复杂度。2022-6-8计算机操作系统- 第6章19/130程序的准备执行-装入n绝对装入方式n静态重定位装入方式n动态重定位装入方式Load A 200 3456 。 。物理地址空间物理地址空间Load A 200 3456逻辑地址空间逻辑地址空间逻辑地址与实际内存地址一致逻辑地址与实际内存地址一致适用于单道程序环境适用于单道程序环境2022-6-8计算机操作系统- 第

14、6章20/130程序的准备执行-装入n绝对装入方式n静态重定位装入方式n动态重定位装入方式地址映射地址映射/ /地址重定位地址重定位把用户程序装入内存时对有关指令的地址把用户程序装入内存时对有关指令的地址部分的修改定义为从程序地址到内存地址部分的修改定义为从程序地址到内存地址的地址映射，或称为地址重定位。的地址映射，或称为地址重定位。静态地址映射静态地址映射动态地址映射动态地址映射2022-6-8计算机操作系统- 第6章21/130程序的准备执行-装入n静态地址映射（静态重定位）n程序被装入内存时，由操作系统的连接装入程序完成程序的逻辑地址到内存地址的转换。n假定程序装入内存的首地址为BR，程

15、序地址为VR，内存地址为MR，则地址映射按下式进行：MR=BR+VR 。n例如，程序装入内存的首地址为1000，则装配程序就按MR=1000+VR对程序中所有地址部分进行修改，修改后指令Load A，200就变为Load A，1200优点：不需要硬件的支持。优点：不需要硬件的支持。 缺点：程序必须占用连续的内存空间，缺点：程序必须占用连续的内存空间， 一旦程序装入后不能移动。一旦程序装入后不能移动。 2022-6-8计算机操作系统- 第6章22/130程序的准备执行-装入n动态地址映射（动态重定位）n动态地址重定位是在程序执行的过程中，每次访问内存之前，将要访问的程序地址转换为内存地址。一般来

16、说这种转换是由专门的硬件机构来完成的。n最简单的硬件机构是重定位寄存器。n在地址重定位机构中，有一个基地址寄存器BR和一个程序地址寄存器VR，一个内存地址寄存器MR。03456.LOAD A 200.0100200300.LOAD A 2003456110012001300200VR+1000BR2022-6-8计算机操作系统- 第6章23/130程序的准备执行-装入n动态地址映射（动态重定位）n动态地址重定位是在程序执行的过程中，每次访问内存之前，将要访问的程序地址转换为内存地址。一般来说这种转换是由专门的硬件机构来完成的。n最简单的硬件机构是重定位寄存器。n在地址重定位机构中，有一个基地址

17、寄存器BR和一个程序地址寄存器VR，一个内存地址寄存器MR。2022-6-8计算机操作系统- 第6章24/130程序的准备执行-装入n动态地址映射（动态重定位）过程描述：1.程序装入内存后，它所占用的内存区的首地址由系统送入基地址寄存器BR中。2.在程序执行的过程中，若要访问内存，将访问的逻辑地址送入VR中。 3.地址转换机构把VR和BR中的内容相加，并将结果送入MR中，作为实际访问的地址。2022-6-8计算机操作系统- 第6章25/130load 1,2500365load 1,25003650 01001002500250050005000250025001000010000100001

18、00001010010100+ +12500125001500015000作业作业J J处理机一侧处理机一侧存储器一侧存储器一侧重定位寄存器重定位寄存器相对地址相对地址2022-6-8计算机操作系统- 第6章26/130程序的准备执行-装入n动态地址映射（动态重定位）优点：n程序占用的内存空间是动态可变的，当程序从某个存储区移到另一个区域时，只需要修改相应的寄存器BR的内容即可。n一个程序不一定要求占用一个连续的内存空间。n可以部分地装入程序运行。n便于多个进程共享同一个程序的代码。2022-6-8计算机操作系统- 第6章27/130程序的准备执行-装入n动态地址映射（动态重定位）缺点：n需要

19、硬件的支持。n实现存储管理的软件算法较为复杂。2022-6-8计算机操作系统- 第6章28/1306.1.3 覆盖技术n当内存空间有限时，某些大的用户程序不能一次全部装入内存时，系统需要采取覆盖技术解决这一问题。1.将大的用户程序划分为一个个相对独立的程序单位2.将程序执行时不需要同时装入内存的程序单位组成覆盖段。3.覆盖段的长度不能超过已有内存空间大小，每个覆盖段分先后顺序进入到所分配的内存空间，后进入内存空间的段将先进入内存空间的段覆盖。2022-6-8计算机操作系统- 第6章29/130覆盖技术n采用了覆盖的程序执行比没有采用覆盖的程序执行慢n采用覆盖程序执行过程中增加了读覆盖段的过程（

20、输入操作），需要花费相当多的时间。 n覆盖技术要求程序员具有完整的程序指令、代码和数据结构方面的知识。n覆盖仅限于微型计算机和物理内存有限而又不支持更先进技术的系统 2022-6-8计算机操作系统- 第6章30/1306.1.4 紧凑技术n紧凑技术通过改变进程在内存中的位置，移动存储器中某些已分配分区中的信息，使分散在内存中的“碎片”能够汇集成一片，再分配给进程使用，达到充分利用内存的目的。n提高内存的利用率2022-6-8计算机操作系统- 第6章31/130操作系统用户程序1用户程序3用户程序6用户程序910kb10kb操作系统用户程序1用户程序3用户程序6用户程序926kb26kb14kb

21、14kb30kb30kb80kb80kb紧凑技术2022-6-8计算机操作系统- 第6章32/130紧凑技术紧凑技术的缺点：n增加了系统的开销n移动已分配的内存区域会花费处理器大量的时间。n影响进程正常运行n当系统进行紧凑时，必须停止所有进程的执行。n外设与内存交换数据的进程，不可随便移动n实时操作系统，会影响实时任务的完成。n需要重新定义内存地址n在紧凑之后，作业在内存中的地址发生了变化，需要重新定义内存地址。2022-6-8计算机操作系统- 第6章33/1302022-6-8计算机操作系统- 第6章34/1306.1.5 对换技术n当内存空间紧张时，将某些暂时不运行的进程从内存移到外存，并

22、将内存空间分配给其他进程或新创建的进程；当内存空间富余时再给被移出到外存的进程重新分配内存，让进程进入内存，这样的方式称为对换技术对换技术。n对换技术是为了提高系统的性能和多道度而采取的进程在内存和外存之间的换出与换入。 2022-6-8计算机操作系统- 第6章35/130对换技术n对换的引入n所有可运行的进程必须小于内存空间n当进程处于阻塞或就绪时交换到磁盘n进程在运行过程中将多次进出内存进程A操作系统未用内存区进程A操作系统未用内存区进程B进程A操作系统未用内存区进程B进程C未用内存区操作系统未用内存区进程B进程C未用内存区操作系统未用内存区进程B进程C进程D进程D操作系统未用内存区进程C

23、未用内存区2022-6-8计算机操作系统- 第6章36/130存储器系统包括哪些基本层次？存储器系统包括哪些基本层次？层次之间的关系是怎样的层次之间的关系是怎样的？解释逻辑地址和物理地址；解释逻辑地址和物理地址；为什么要实现地址变换？为什么要实现地址变换？什么是紧凑技术？什么是紧凑技术？该技术有何缺点？该技术有何缺点？覆盖技术和对换技术有何不同？覆盖技术和对换技术有何不同？问题2022-6-8计算机操作系统- 第6章37/130本章目录n6.1 存储器管理概述 n6.2 连续存储空间管理n单一连续分配 n固定分区分配n可变分区分配n6.3 分页式存储管理 n6.4 分段式存储管理 2022-6

24、-8计算机操作系统- 第6章38/130引起内存分配和回收的原因n进程的开始的结束。n进程运行的过程中，它所占用的内存也可能发生变化，如栈的变化。n进程映像在内存和外存之间传递。由于内存有限，系统中不可能容纳所有进程，有些进程的映像可以存放在外存，当要运行这些进程时，必须把它们调入内存。n系统为了充分利用内存空间，有时可能对内存空间进行调整。2022-6-8计算机操作系统- 第6章39/130存储保护 n上、下界存储保护：n上、下界保护是一种简单的存储保护技术。n系统可为每个作业设置一对上、下界寄存器，分别用来存放当前运行作业在内存空间的上、下边界地址，用它们来限制用户程序的活动范围。 n基址

25、限长存储保护：n上、下界保护的一个变种是采用基址-限长存储保护。 上下界保护上下界保护基址限长保护基址限长保护2022-6-8计算机操作系统- 第6章40/1306.2.1 单一连续分配n最简单的管理方式（只有分配与回收）n操作系统和用户程序共享RAMn除了嵌入式系统外，其他的计算机不再使用这种方式用户程序用户程序RAM中的中的OS用户程序用户程序ROM中的中的OS用户程序用户程序RAM中的中的OSROM：DEV早期大型机使用早期大型机使用的内存管理方式的内存管理方式少数掌上电脑和嵌入式系少数掌上电脑和嵌入式系统使用的内存管理方式统使用的内存管理方式早期早期PCPC使用的内存使用的内存管理方式

26、（管理方式（MS-DOS)MS-DOS)2022-6-8计算机操作系统- 第6章41/1306.2.2 固定分区分配n早期支持多道程序的管理方式n将用户可使用内存区划分为固定大小，根据作业长度分配内存n支持多道程序的大型机使用，目前几乎不再使用可用分区可用分区1RAM中的OS可用分区可用分区2可用分区可用分区3分区号起始地址终止地址分区大小分区1100K200K100K分区2200K400K200K分区3400K700K300K2022-6-8计算机操作系统- 第6章42/130固定分区分配n有n个分区，则可同时装入n个作业/任务。n分区大小：n相等n不相等，利用率较高n内存分配：n数据结构

27、n将分区按大小排序，并将其地址、分配标识作记录n特点：n简单n有碎片（内零头）2022-6-8计算机操作系统- 第6章43/130固定分区分配分区号大小(K) 起址(K)状态11220已分配23232已分配36464已分配4128128已分配操作系统作业A作业B作业C24K32K64K128K256K分配情况分配情况2022-6-8计算机操作系统- 第6章44/130固定分区分配分区号大小(K) 起址(K)状态11220已分配23232已分配36464已分配4128128已分配操作系统作业A作业B作业C24K32K64K128K256K分配情况分配情况性能分析性能分析 在作业大小和出现频率均已

28、知的情况下，固定分区是合适的。在这种情况下分区的大小选择与作业大小相当，这样内存的使用效率较高。 但是若作业的大小和出现的频率不知道时，势必造成分区的大小和作业的大小相差甚远，这样就会造成存储空间的浪费，从而影响整个系统的效率。 2022-6-8计算机操作系统- 第6章45/130固定分区分配n内存分配与回收n多队列最优适配、最小适配、合理适配（种种变化）n内存回收机制非常简单，只需要进行分区表操作n内存地址的重定位与保护n最简单的策略：在调入内存时直接修改指令n最严格的办法：密码校验，PSW的使用n最普遍的做法：引入硬件基址和界限存储器2022-6-8计算机操作系统- 第6章46/1306.

29、2.3 可变分区分配n要点n在运行的过程中建立分区n使分区的大小刚好与作业的大小相等n空闲分区的组织方式n分配的三种情况n分配算法n回收方法n空闲区表或队列的排序n按空闲区首址递增的次序n按空闲区大小的递增或递减次序n无满足要求的空闲区n空闲区大小 = SIZEn空闲区大小 SIZEn首次适应：地址递增n最佳适应：大小递增n最坏适应：大小递减n上相邻n下相邻n上下均相邻n上下均不相邻2022-6-8计算机操作系统- 第6章47/130可变分区分配n在系统运行的过程中建立分区，并使分区的大小刚好与作业的大小相等。n可解决固定分区严重浪费内存的问题。n是一种较为实用的存储管理方法。n要解决的问题n

30、数据结构n分区分配算法n分区分配操作2022-6-8计算机操作系统- 第6章48/130描述分区的数据结构n数据结构n在动态分区存储管理中，要有相应的数据结构来登记空闲区的说明信息，它包括空闲区的大小和位置。n不同系统根据设计要求采用不同的结构。n常用的有表结构和队列结构。n系统还要设置了等待分区队列，当系统中无空闲区或无满足要求的空闲区时，则把申请者送入等待队列中，等待别的进程释放内存之后再唤醒队列中的进程。2022-6-8计算机操作系统- 第6章49/130描述分区的数据结构2022-6-8计算机操作系统- 第6章50/130可变分区分配n分配算法n在采用分区存储管理的系统中，系统初启后，

31、除操作系统占用一个分区外，其余存储区为一个大的空闲区。n分区的分配是指系统根据用户的请求，在空闲区表或空闲区队列中寻找一个满足用户要求的空闲区，把这个空闲区分配给用户。n以空闲区表为例，当用户要求一个大小为SIZE的存储空间时，系统查询空闲区表，找一个大于或等于SIZE的空闲区。2022-6-8计算机操作系统- 第6章51/130可变分区分配n分配算法n 空闲区表或队列的排序n 按空闲区首址递增的次序n 按空闲区大小的递增或递减次序2022-6-8计算机操作系统- 第6章52/130可变分区分配n分区分配的三种情况系统中无满足要求的空闲区，则分配失败。系统中无满足要求的空闲区，则分配失败。空闲

32、区大小与空闲区大小与SIZESIZE相等，则修改空闲区表相应表相等，则修改空闲区表相应表目，向用户返回该空闲区首址，表示此空闲区已目，向用户返回该空闲区首址，表示此空闲区已分给了要求的用户。分给了要求的用户。空闲区大于空闲区大于SIZESIZE，这时将空闲区一分为二。，这时将空闲区一分为二。2022-6-8计算机操作系统- 第6章53/130可变分区分配n分区分配的三种情况策略一：从空闲区的上部开始划出策略一：从空闲区的上部开始划出SIZESIZE大小的空闲区大小的空闲区给用户；给用户；策略二：从空闲区的底部开始向上划出策略二：从空闲区的底部开始向上划出SIZESIZE大小的空大小的空闲区给用

33、户。闲区给用户。一般常采用第二种办法，因为这样划分时，余下的部一般常采用第二种办法，因为这样划分时，余下的部分在空闲区表中的首地址不变，只需要修改一下大小分在空闲区表中的首地址不变，只需要修改一下大小就行了。就行了。2022-6-8计算机操作系统- 第6章54/130可变分区分配n分区分配的算法首次适应算法首次适应算法FFFF：原理、优点、缺点：原理、优点、缺点要求空闲区按首址递增的次序组织空闲区表（队列）要求空闲区按首址递增的次序组织空闲区表（队列）循环首次适应算法：原理、优点、缺点循环首次适应算法：原理、优点、缺点最佳适应算法：原理、优点、缺点最佳适应算法：原理、优点、缺点要求按空闲区大小

34、从小到大的次序组成空闲区表（队列）。要求按空闲区大小从小到大的次序组成空闲区表（队列）。最坏适应算法：原理、优点、缺点最坏适应算法：原理、优点、缺点要求空闲区按大小递减的顺序组织空闲区表（或队列）。要求空闲区按大小递减的顺序组织空闲区表（或队列）。2022-6-8计算机操作系统- 第6章55/130可变分区分配n分区分配的算法：首次适应法n分配：当进程申请大小为SIZE的内存时，系统从空闲区表的第一个表目开始查询，直到首次找到等于或大于SIZE的空闲区。从该区中划出大小为SIZE的分区分配给进程，余下的部分仍作为一个空闲区留在空闲区表中，但要修改其首址和大小。n回收：按释放区的首址，查询空闲区

35、表，若有与释放区相邻的空闲区，则合并到相邻的空闲区中，并修改该区的大小和首址，否则，把释放区作为一个空闲区，将其大小和首址按照首地址大小递增的顺序插入到空闲区表的适当位置。2022-6-8计算机操作系统- 第6章56/130可变分区分配n分区分配的算法：首次适应法n注意：每次分配和回收后空闲区表或空闲区队列都要按首址递增的次序排序。n首次适应法的优点：n释放某一存储区时，若与空闲区相邻则合并到相邻空闲分区中去，这种情况并不改变该区在表中的位置，只要修改其大小或首址。n这种算法是尽可能地利用低地址空间，从而保证高地址空间有较大的空闲区。 2022-6-8计算机操作系统- 第6章57/130可变分

36、区分配n分区分配的算法：最佳适应法n分配：当进程申请一个存储区时，系统从表头开始查找，当找到第一个满足要求的空闲区时，停止查找，并且这个空闲区是最佳的空闲区。n所谓最佳即选中的空闲区是满足要求的最小空闲区。n回收：按释放区的首址，查询空闲区表（队列） ，若有与释放区相邻的空闲区，则合并到相邻的空闲区中，并修改该区的大小和首址，否则，把释放区作为一个空闲区插入空闲区表（队列）。n分配和回收后要对空闲区表（队列）重新排序。2022-6-8计算机操作系统- 第6章58/130可变分区分配n分区分配的算法：最佳适应法n优点：n在系统中若存在一个与申请分区大小相等的空闲区，必定会被选中，而首次适应法则不

37、一定。n若系统中不存在与申请分区大小相等的空闲区，则选中的空闲区是满足要求的最小空闲区，而不致于毁掉较大的空闲区。n缺点：n空闲区的大小一般与申请分区大小不相等，因此将其一分为二，留下来的空闲区一般情况下是很小的，以致无法使用。随着时间的推移，系统中的小空闲区会越来越多，从而造成存储区的大量浪费。 2022-6-8计算机操作系统- 第6章59/130可变分区分配n分区分配的算法：最坏适应法n分配：进程申请一个大小为SIZE的存储区时，总是检查空闲区表的第一个空闲区的大小是否大于或等于SIZE。若空闲区小于SIZE，则分配失败；否则从空闲区中分配SIZE的存储区给用户，然后修改和调整空闲区表。n

38、回收：按释放区的首址，查询空闲区表（队列） ，若有与释放区相邻的空闲区，则合并到相邻的空闲区中，并修改该区的大小和首址，否则，把释放区作为一个空闲区插入空闲区表（队列）。n分配和回收后要对空闲区表（队列）重新排序。2022-6-8计算机操作系统- 第6章60/130可变分区分配n分区分配的算法：最坏适应法n最坏适应法看起来公似乎有些荒唐，但在更加严密地考察后，还是有它的优点：n 当程序装入内存中最大的空闲区后，剩下的空闲区还可能相当大，还能装下较大的程序。n 另一方面每次仅作一次查询工作。2022-6-8计算机操作系统- 第6章61/130n分配方法举例分分配配前前的的状状态态2022-6-8

39、计算机操作系统- 第6章62/130n首次适应法分分配配后后的的状状态态2022-6-8计算机操作系统- 第6章63/130n最佳适应法分分配配后后的的状状态态2022-6-8计算机操作系统- 第6章64/130n最坏适应法分分配配后后的的状状态态2022-6-8计算机操作系统- 第6章65/130不同分配算法的对比分分配配前前的的状状态态首次分配首次分配最佳分配最佳分配最坏分配最坏分配2022-6-8计算机操作系统- 第6章66/130可变分区分配n分配算法的分析n分配算法各有利弊，到底哪种最好不能一概而论，而应针对具体作业序列来分析。n对于某一作业序列来说，某种算法能将该作业序列中所有作业

40、安置完毕，那么我们说该算法对这一作业序列是合适的。n对于某一算法而言，如它不能立即满足某一要求，而其它算法却可以满足此要求，则这一算法对该作业序列是不合适的。 2022-6-8计算机操作系统- 第6章67/130可变分区分配n 碎片问题n由于空闲区的大小与申请内存的大小相等的情况是很少的，绝大多数情况是从一个空闲区中切去一块，剩下的部分作为一个空闲区仍留在空闲区表中，随着时间的推移，空闲区的发展趋势是越来越小，直至不能满足任何用户要求。n这种不能被任何用户使用的极小的空闲区称为碎片。碎片的出现造成了存储空间的浪费。2022-6-8计算机操作系统- 第6章68/130可变分区分配解决方案解决方案

41、n规定门限值（由操作系统规定，如1K），分割空闲区时，若剩余部分小于门限值，则不再分割此空闲区。n定期压缩存储空间，将所有空闲区集中到内存的一端，但这种方法的系统开销太大。2022-6-8计算机操作系统- 第6章69/130可变分区分配内存分配流程图2022-6-8计算机操作系统- 第6章70/130分区回收n内存回收F1F1回收区回收区F2F2回收区回收区F2F2F1F1回收区回收区F1F1回收区回收区F2F22022-6-8计算机操作系统- 第6章71/130碎片的产生碎片的产生固定分区碎片（内零头固定分区碎片（内零头）动态分区外部零头动态分区外部零头碎片的处理碎片的处理思考2022-6-

42、8计算机操作系统- 第6章72/130n关于内存空间的分配与回收n如何定义内存管理的数据结构？n如何设计内存管理的基本算法？n关于内存空间的共享和保护n你能够想象到哪些硬件保护机制？n你能够想象到哪些软件保护机制？n关于内存空间的扩充n你能够想象到哪些可以运行大程序的方法？n关于内存管理面临的性能问题n有哪些性能参数？如何保证内存管理的性能？思考2022-6-8计算机操作系统- 第6章73/130课堂练习：可变分区分配n例1：有作业序列：作业A要求18K；作业B要求25K，作业C要求30K。系统中空闲区按不同算法组成的空闲区队列2022-6-8计算机操作系统- 第6章74/130课堂练习：可变

43、分区分配n例1：有作业序列：作业A要求18K；作业B要求25K，作业C要求30K。系统中空闲区按不同算法组成的空闲区队列n经分析可知：最佳适应法对这个作业序列是合适的，而其它算法对该作业序列是不合适的。n经分析可知：最佳适应法对这个作业序列是合适的，而其它算法对该作业序列是不合适的。2022-6-8计算机操作系统- 第6章75/130课堂练习：可变分区分配n有作业序列：作业A要求21K；作业B要求30K，作业C要求25K。2022-6-8计算机操作系统- 第6章76/130课堂练习：可变分区分配n已知主存有256KB容量，其中OS占用低址20KB，可以有这样的一个作业序列：作业1要求 80KB

44、；作业2要求16KB；作业3要求140KB；作业1完成；作业3完成；作业4要求 80KB；作业5要求120KB。试用首次适应算法首次适应算法和最佳适应最佳适应算法算法分别处理上述作业序列(在存储分配时，从空白区高址处分割作为已分配区)，并完成以下各步：n(1) 画出作业1、2、3进入主存后，主存的分配情况。 n(2) 作业1、3完成后，画出主存分配情况。 n(3) 画出两种算法中空白区的分区描述器信息(假定分区描述器所需占用的字节数已包含在作业所要求的主存容量中)及空白区链接情况。n(4) 哪种算法对该作业序列而言是适合的？2022-6-8计算机操作系统- 第6章77/130本章目录n6.1

45、存储器管理概述 n6.2 连续存储空间管理n6.3 分页式存储管理n分页存储管理的基本原理 n页表 n地址变换机构n快表n多级页表n反置页表n页面共享和保护n6.4 分段式存储管理 2022-6-8计算机操作系统- 第6章78/130连续分配方式连续分配方式 碎片碎片 紧凑紧凑 代价代价6.3 分页式存储管理离散分配方式离散分配方式分页分页 分段分段 段页式段页式基本的分页存储管理方式（纯分页存储管理方式）基本的分页存储管理方式（纯分页存储管理方式） 分页技术是由曼彻斯特大学提分页技术是由曼彻斯特大学提出，并于出，并于19601960年前后在年前后在AtlasAtlas计算计算机上实现。这种技

46、术对操作系统的机上实现。这种技术对操作系统的发展产生了深远影响。发展产生了深远影响。2022-6-8计算机操作系统- 第6章79/130n用户程序划分n把用户程序按逻辑页划分成大小相等的部分，称为页（page）。从0开始编制页号，页内地址是相对于0编址。n逻辑地址n用户程序的划分是由系统自动完成的，对用户是透明的。n通常，一页的大小为2的整数次幂。因此，地址的高位部分为页号，低位部分为页内地址6.3.1 分页存储管理基本思想2022-6-8计算机操作系统- 第6章80/130n内存空间n按页的大小划分为大小相等的区域，称为块或内存块（物理页面，页框）n内存分配n以页为单位进行分配，并按作业的页

47、数多少来分配。逻辑上相邻的页，物理上不一定相邻分页存储管理基本思想2022-6-8计算机操作系统- 第6章81/130页地址映射n页表 n页大小的选择 n页地址映射 n分页存储管理中的信息保护 n快表和联想存储器n两级页表和多级页表 2022-6-8计算机操作系统- 第6章82/1306.3.2 页表内容n页表包含以下几个表项：n页号：登记程序地址空间的页号。n块号：登记相应的页所对应的内存块号n其它：登记与存储信息保护有关的信息。页号块号其它051652132022-6-8计算机操作系统- 第6章83/130n页面n页面和物理块：逻辑空间和内存空间n由机器的地址结构决定n页太大，页内碎片大。

48、n页太小：页表可能很长，换入/出效率低n地址结构 31 12 11 0n设: 逻辑地址A; 页大小L(设为1024); 页内偏移d; 页号P PINT（A/L） dA mod L 如： A2170B. 则P2，d122 页面与页表页号P 位移W 2022-6-8计算机操作系统- 第6章84/130页面与页表n设：逻辑地址A；页大小L(设为1024)；页内偏移d；页号P PINT（A/L） dA mod Ln又如：页面大小为4KB的系统中，若逻辑地址为28024，则由上式求得页号为6，页内偏移量为3448。n如何得到页号和页内地址呢？n 28024的二进制用32位表示为：n 0000 0000

49、0000 0000 0110 1101 0111 1000n 因为页面大小为4KB，则取低12位为页内地址，剩余高位是页号。2022-6-8计算机操作系统- 第6章85/130页面与页表0页1页2页3页4页5页n页021326384950123456789用户程序用户程序页表页表页号页号块号块号内存内存2022-6-8计算机操作系统- 第6章86/1306.3.3 地址变换机构 完成以下任务：n逻辑页号物理块号的映射，由页表完成。n基本地址变换机构：越界保护每个进程对应一页表，其信息（如长度、始址）放在PCB中，执行时将其首地址装入页表寄存器。2022-6-8计算机操作系统- 第6章87/13

50、0分页系统的地址变换机构分页系统的地址变换机构 地址变换机构 2022-6-8计算机操作系统- 第6章88/130 页号页号3 3与页表寄存器中的页表长度比较判断是否越界，如果越界，与页表寄存器中的页表长度比较判断是否越界，如果越界，则转错误中断处理，否则转；则转错误中断处理，否则转；2022-6-8计算机操作系统- 第6章89/130 页表中该项在内存中的对应地址页表中该项在内存中的对应地址= =页表始地址页表始地址R+R+页号页号3 3页表项页表项长度长度i i，访问该地址，访问该地址R+3iR+3i，得到物理块号，得到物理块号1111；2022-6-8计算机操作系统- 第6章90/130

51、 11(11(块块号号) )1024(1024(块块大小大小)+723()+723(页内地址页内地址) ) = 11987( = 11987(物理地址物理地址) )；2022-6-8计算机操作系统- 第6章91/130 访问内存访问内存1198711987单元，得到需要的数据单元，得到需要的数据365365。2022-6-8计算机操作系统- 第6章92/1306.3.4 快表具有快表的地址变换机构n不具快表，则需两次访问内存。n第一次：访问页表n第二次：得到绝对地址内容n有快表，速度提高。n快表贵，不能太多。2022-6-8计算机操作系统- 第6章93/130快表2022-6-8计算机操作系统

52、- 第6章94/130快表n例：有一页式系统，其页表存放在主存中： 如果对主存的一次存取需要1.5s，试问实现一次页面访问的存取时间是多少? 如果系统加有快表，平均命中率为85%，当页表项在快表中时，其查找时间忽略为0，试问此时的存取时间是多少?2022-6-8计算机操作系统- 第6章95/130答：若页表存放在主存中，则要实现一次页面访问需两次访问主存：一次是访问页表，确定所存取页面的物理地址（称为定位）。第二次才根据该地址存取页面数据。 页表在主存的存取访问时间 = 1.5*2 =3(s) 增加快表后的存取访问时间 = 0.85*1.5+(1-0.85)*2*1.5 = 1.725(s)快

53、表2022-6-8计算机操作系统- 第6章96/1306.3.5 两级和多级页表 n页表可能很大，将其离散存放在不同页块中。n建一“外部页表”来管理这些离散页表块。n相当于单级页表中的页表寄存器，一般应常驻内存。每项记录页表始址，且增加存在位。n64位机器页表一般3级，最外层页表常驻。 2022-6-8计算机操作系统- 第6章97/130两级和多级页表 2022-6-8计算机操作系统- 第6章98/130举例例：某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面对应的物理块号如下表：页号物理块号051102437则逻辑地址0A5C（H）

54、所对应的物理地址为：125C2022-6-8计算机操作系统- 第6章99/1300A5C0000,1010,0101,1100 0000,1010,0101,1100页号为2，对应块号为4，有：物理地址：0001,0010,0101,1100即：125C举例2022-6-8计算机操作系统- 第6章100/130分页存储管理方案的评价n优点：n便于多道程序设计，提高了内存的利用率，而不必像动态分区分配那样执行紧凑操作。n缺点1：n采用动态地址映射会增加计算机成本和降低处理机的速度。n缺点2：n各种表格要占用一定容量的内存空间，而且还要花费一部分处理机时间来建立和管理这些表格。n缺点3：n虽然消除

55、了大量碎片，但每个作业的最后一页一般都有不能充分利用的空白区；减少页面大小，可以减少内存的浪费，但页表的长度又增加了，这也是一个矛盾。n缺点4：n存储扩充问题仍未得到解决。当没有足够空间能装下整个作业地址空间时，该作业还是无法运行。2022-6-8计算机操作系统- 第6章101/130一维虚拟存储管理-分页式n逻辑地址、虚拟地址、物理地址n一个程序经编译得到的指令地址空间，叫做逻辑地址空间n当逻辑地址空间大于物理地址空间时，叫做虚拟地址空间n逻辑地址空间虚拟地址空间MMU单元物理地址空间2022-6-8计算机操作系统- 第6章102/130一维虚拟存储管理-分页式n分页式存储管理的核心思想n制

56、定统一的地址空间描述机制：页与页表n对逻辑地址而言，使用分页机制实现对虚拟地址空间的划分n对物理地址而言：使用分页机制实现对物理地址空间的管理n虚拟存储的核心思想：以页为基本单位，不同地址空间的转换和映射2022-6-8计算机操作系统- 第6章103/130一维虚拟存储管理-分页式n分页式存储管理的困难和问题n地址映射与保护：如何快速、有效的实现地址映射？n虚拟存储的关键：如何实现页面的置换？如何保证程序运行的效率？2022-6-8计算机操作系统- 第6章104/130二维虚拟存储管理-分段式n分页式虚拟存储管理的难题n设计与实现机制复杂，需要软件和硬件的精妙配合n影响性能因素多样化，保证存储

57、体系的高效很困难n仅从计算机角度出发，人难以理解、监控和管理2022-6-8计算机操作系统- 第6章105/130二维虚拟存储管理-分段式n分段式存储管理思想的产生n遵循程序的逻辑化特性，将其分为不同的“段”，易于理解和监控n继承虚拟地址的思想，以“段号段内偏移”实现地址映射n对物理内存进行一维分割，内存使用则体现二维逻辑性2022-6-8计算机操作系统- 第6章106/130二维虚拟存储管理-分段式n分段式存储的优点和缺点n优点1：存储管理过程简单、灵活简便的适应各类程序n优点2：易于程序的编译、链接，易于不同程序间的共享n缺点：管理粒度较大，操作系统的管理职能不深入，无法保证稳定性2022

58、-6-8计算机操作系统- 第6章107/130反置页表的基本原理反置页表的基本原理分页方式中的共享与保护分页方式中的共享与保护问题2022-6-8计算机操作系统- 第6章108/130本章目录n6.1 存储器管理概述 n6.2 连续存储空间管理n6.3 分页式存储管理n6.4 分段式存储管理n分段存储管理n段表和地址变换机构n分段与分页的区别n具有分页的分段n段的共享和保护2022-6-8计算机操作系统- 第6章109/130引入 n每个段可有其逻辑意义及功能，使得便于：n方便编程n分段共享n分段保护n动态增长（如数据段的增长）n动态链接2022-6-8计算机操作系统- 第6章110/130分

59、段系统的基本原理 n分段n在分段式存储管理中，段名用段号代替，段地址从0开始编址，因为各段的逻辑信息内容不同，所以段长度不同。n当一个用户程序装入内存时，系统为每个段分配一个连续的内存区域，而各个段之间可以离散存放。2022-6-8计算机操作系统- 第6章111/1306.4.1 分段系统的基本原理 n分段：n对用户而言，分段是2维的。n段号+段内地址。n段表：n逻辑段map物理段n地址变换机构n分页与分段：n页是信息的物理单位，段是逻辑单位n页长度固定，段长度不固定（由用户指定）n一维与二维 2022-6-8计算机操作系统- 第6章112/130分段系统的基本原理 2022-6-8计算机操作系统- 第6章113/130分段系统的基本原理 2022-6-8计算机操作系统- 第6章114/1306.4.2 地址变换机构 段号段号3 3与段表寄存器存放的段表长度比较以判断是否越界，如果与段表寄存器存放的段表长度比较以判断是否越界，如果越界，则转错误中断处理，否则转；越界，则转错误中断处理，否则转；2022-6-8计算机操作系统- 第6章115/1306.4.2