操作系统ppt课件第四章

Operating SystemOperating SystemPage 12024/7/18第四章 存储器管理操作系统Page 12023/8/15Operating SystemOperating System第第第第四四四四章章章章 存存存存储储储储器器器器管管管管理理理理q重点重点v理解理解重定位的基本概念重定位的基本概念 v掌握掌握动态分区分配方式动态分区分配方式 v掌握理解掌握理解分页和分段存储管理方式分页和分段存储管理方式 v理解理解虚拟存储器的基本概念虚拟存储器的基本概念 v掌握掌握请求分页系统的基本原理请求分页系统的基本原理 q难点难点v动态分区分配动态分区分配算法算法 v分页和分段地址转换分页和分段地址转换v请求分页系统的地址转换及页面置换算法请求分页系统的地址转换及页面置换算法Page 22024/7/18第四章 存储器管理重点Page 22023/8/15Operating SystemOperating System第第第第四四四四章章章章 存存存存储储储储器器器器管管管管理理理理q知识点知识点v重定位的基本概念重定位的基本概念 v动态分区分配方式及分配算法、分区保护动态分区分配方式及分配算法、分区保护v分页存储管理及地址变换、分段存储管理及地分页存储管理及地址变换、分段存储管理及地址变换，信息共享和保护址变换，信息共享和保护v虚拟存储器的基本概念、特征，页面置换技术虚拟存储器的基本概念、特征，页面置换技术 v请求分页系统，页表机制、地址变换及页面置请求分页系统，页表机制、地址变换及页面置换算法换算法 Page 32024/7/18第四章 存储器管理知识点Page 32023/8/15Operating SystemOperating System第四章第四章第四章第四章 存储器管理存储器管理存储器管理存储器管理q存储器是计算机系统重要的组成部分存储器是计算机系统重要的组成部分q虽然存储器的容量不断扩大，但仍不能满虽然存储器的容量不断扩大，但仍不能满足要求，因此存储器管理是操作系统的重足要求，因此存储器管理是操作系统的重要工作要工作Page 42024/7/18第四章 存储器管理存储器是计算机系统重要的组成部分Page Operating SystemOperating System第四章第四章第四章第四章 存储器管理存储器管理存储器管理存储器管理q存储器包括内存（主存）和外存（磁盘）存储器包括内存（主存）和外存（磁盘）v存储器的功能是保存数据，存储器的发展方向存储器的功能是保存数据，存储器的发展方向是高速、大容量和小体积。是高速、大容量和小体积。内存在访问速度方面的发展：内存在访问速度方面的发展：DRAM、SDRAM、SRAM等；等；硬盘技术在大容量方面的发展：接口标准、硬盘技术在大容量方面的发展：接口标准、存储密度等；存储密度等；q主存储器管理技术分为两大类主存储器管理技术分为两大类v实存储器管理实存储器管理v虚拟存储器管理虚拟存储器管理Page 52024/7/18第四章 存储器管理存储器包括内存（主存）和外存（磁盘）PagOperating SystemOperating System第四章第四章第四章第四章 存储器管理存储器管理存储器管理存储器管理q存储器的物理组织、多级存储器存储器的物理组织、多级存储器v存储组织是指在存储技术和存储组织是指在存储技术和CPU寻址技术许可的寻址技术许可的范围内组织合理的存储结构。范围内组织合理的存储结构。其依据是访问速度匹配关系、容量要求和价其依据是访问速度匹配关系、容量要求和价格。格。“寄存器寄存器-内存内存-外存外存”结构结构“寄存器寄存器-缓存缓存-内存内存-外存外存”结构；结构；v微机中的存储层次组织：微机中的存储层次组织：访问速度越慢，容量越大，价格越便宜；访问速度越慢，容量越大，价格越便宜；最佳状态应是各层次的存储器都处于均衡的最佳状态应是各层次的存储器都处于均衡的繁忙状态（如：缓存命中率正好使主存读写保繁忙状态（如：缓存命中率正好使主存读写保持繁忙）；持繁忙）；Page 62024/7/18第四章 存储器管理存储器的物理组织、多级存储器Page 62Operating SystemOperating System第四章第四章第四章第四章 存储器管理存储器管理存储器管理存储器管理q快速缓存：快速缓存：vData CachevTLB(Translation Lookaside Buffer)q内存：内存：DRAM,SDRAM等；等；q外存：软盘、硬盘、光盘、磁带等；外存：软盘、硬盘、光盘、磁带等；Page 72024/7/18第四章 存储器管理快速缓存：Page 72023/8/15Operating SystemOperating System第四章第四章第四章第四章 存储器管理存储器管理存储器管理存储器管理q主存储器管理功能主存储器管理功能v存储分配和回收存储分配和回收分配和回收算法及相应的数据结构分配和回收算法及相应的数据结构v地址变换和重定位地址变换和重定位可执行文件生成中的链接技术可执行文件生成中的链接技术程序加载程序加载(装入装入)时的重定位技术时的重定位技术进程运行时硬件和软件的地址变换技术和机构进程运行时硬件和软件的地址变换技术和机构v存储共享和保护存储共享和保护代码和数据共享代码和数据共享地址空间访问权限（读、写、执行）地址空间访问权限（读、写、执行）v存储器扩充：存储器的逻辑组织和物理组织；存储器扩充：存储器的逻辑组织和物理组织；由应用程序控制：覆盖；由应用程序控制：覆盖；由由OS控制：交换（整个进程空间），虚拟存储的请求调入和控制：交换（整个进程空间），虚拟存储的请求调入和预调入（部分进程空间）预调入（部分进程空间）Page 82024/7/18第四章 存储器管理主存储器管理功能Page 82023/8/Operating SystemOperating System第第第第四四四四章章章章 存存存存储储储储器器器器管管管管理理理理q程序的装入和链接程序的装入和链接 q连续分配方式连续分配方式 q基本分页存储管理基本分页存储管理 q基本分段存储管理基本分段存储管理q虚拟存储器的基本概念虚拟存储器的基本概念q请求分页存储管理方式请求分页存储管理方式q页面置换算法页面置换算法q请求分段存储管理方式请求分段存储管理方式Page 92024/7/18第四章 存储器管理程序的装入和链接 Page 92023/8Operating SystemOperating System程程程程序序序序的的的的装装装装入入入入和和和和链链链链接接接接q程序的装入程序的装入q程序的链接程序的链接Page 102024/7/18程序的装入和链接程序的装入Page 102023/8/15Operating SystemOperating System程程程程序序序序的的的的装装装装入入入入q多道程序环境下，程序要运行必须为之创建进程，多道程序环境下，程序要运行必须为之创建进程，而创建进程的第一件事就是分配内存而创建进程的第一件事就是分配内存q源程序要运行通常经过源程序要运行通常经过编译（编译（compile）链接链接(link)装入装入(load)等几个步骤等几个步骤Page 112024/7/18程序的装入多道程序环境下，程序要运行必须为之创建进程，而创建Operating SystemOperating System4.1 程序的装入和链接程序的装入和链接 图 4-1 对用户程序的处理步骤 Page 122024/7/184.1 程序的装入和链接 图 4-1 对用户程序的处理步骤 Operating SystemOperating System4.1.1 程序的装入程序的装入1.绝对装入方式绝对装入方式(Absolute Loading Mode)2.可重定位装入方式可重定位装入方式(Relocation Loading Mode)3.动态运行时装入方式动态运行时装入方式(Dynamic Run-time Loading)Page 132024/7/184.1.1 程序的装入1.绝对装入方式(AbsoluteOperating SystemOperating System程程程程序序序序的的的的装装装装入入入入q绝对装入方式绝对装入方式(Absolute Loading Mode)v事先事先确定确定了程序将了程序将驻留在内存驻留在内存的什么的什么位置位置，即，即在内存中的在内存中的绝对地址绝对地址v装入模块被装入内存后，由于程序中的逻辑地装入模块被装入内存后，由于程序中的逻辑地址与实际内存地址完全相同，故不需对程序和址与实际内存地址完全相同，故不需对程序和数据的地址进行修改数据的地址进行修改v绝对地址的产生绝对地址的产生程序员直接赋予。不仅要求程序员熟悉内存程序员直接赋予。不仅要求程序员熟悉内存使用情况，而且一旦程序或数据被修改后，使用情况，而且一旦程序或数据被修改后，可能要改变程序中的所有地址。通常在程序可能要改变程序中的所有地址。通常在程序中采用符号地址，在编译或汇编时，再将符中采用符号地址，在编译或汇编时，再将符号地址转换为绝对地址。号地址转换为绝对地址。编译或汇编时产生编译或汇编时产生Page 142024/7/18程序的装入绝对装入方式(Absolute Loading MOperating SystemOperating System程程程程序序序序的的的的装装装装入入入入q可重定位装入方式可重定位装入方式(Relocation Loading Mode)v绝对装入方式只能将目标模块装入到内存中事绝对装入方式只能将目标模块装入到内存中事先指定的位置先指定的位置v在多道程序环境下，不可能预知目标模块放在在多道程序环境下，不可能预知目标模块放在内存中的地址，因此绝对装入方式不适合在多内存中的地址，因此绝对装入方式不适合在多道环境下使用道环境下使用v程序中程序中目标模块的地址通常从目标模块的地址通常从0开始开始，其他地，其他地址都是相对于址都是相对于0计算计算相对地址相对地址v把在装入时对目标程序中指令和数据的地址修把在装入时对目标程序中指令和数据的地址修改过程称为改过程称为重定位重定位，又因为，又因为地址变换通常是在地址变换通常是在装入时一次完成装入时一次完成的，以后不再改变，故称为的，以后不再改变，故称为静静态重定位态重定位Page 152024/7/18程序的装入可重定位装入方式(Relocation LoadiOperating SystemOperating System程程程程序序序序的的的的装装装装入入入入作业装入内存时的情况作业装入内存时的情况 缺点：不断的分配和回收，造成内存中小空闲块很多，总缺点：不断的分配和回收，造成内存中小空闲块很多，总空闲空间量够，但分配不了空闲空间量够，但分配不了办法：紧凑（移动），但该装入方法不支持办法：紧凑（移动），但该装入方法不支持Page 162024/7/18程序的装入作业装入内存时的情况 缺点：不断的分配和回收，造成Operating SystemOperating SystemLOAD 1,25003655000250010000作业地址空间作业地址空间36510000110001250015000内存空间内存空间LOAD 1,1250036520000210002250025000内存空间内存空间LOAD 1,22500将程序加载到将程序加载到10000？程程程程序序序序的的的的装装装装入入入入将程序移动到将程序移动到20000？Page 172024/7/18LOAD 1,25003655000250010000作业地Operating SystemOperating System程程程程序序序序的的的的装装装装入入入入q动态运行时装入方式动态运行时装入方式(Denamic Run-time Loading)v可重定位方式不允许程序运行时可重定位方式不允许程序运行时在内存中移在内存中移动位置动位置v动态运行时的装入程序，是在把装入模块装动态运行时的装入程序，是在把装入模块装入内存后，并不立即把装入模块中的相对地入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种址转换为绝对地址，而是把这种地址转换推地址转换推迟到程序真正要迟到程序真正要执行执行时才进行时才进行。因此，。因此，装入装入内存后的所有地址都内存后的所有地址都仍是相对地址仍是相对地址Page 182024/7/18程序的装入动态运行时装入方式(Denamic Run-timOperating SystemOperating System程程程程序序序序的的的的装装装装入入入入和和和和链链链链接接接接q程序的装入程序的装入q程序的链接程序的链接Page 192024/7/18程序的装入和链接程序的装入Page 192023/8/15Operating SystemOperating System4.1 程序的装入和链接程序的装入和链接 图 4-1 对用户程序的处理步骤 Page 202024/7/184.1 程序的装入和链接 图 4-1 对用户程序的处理步骤 Operating SystemOperating System4.1.2 程序的链接程序的链接 1.静态链接方式静态链接方式(Static Linking)2.装入时动态链接装入时动态链接(Load-time Dynamic Linking)3.运行时动态链接运行时动态链接(Run-time Dynamic Linking)Page 212024/7/184.1.2 程序的链接 1.静态链接方式(Static Operating SystemOperating System程程程程序序序序的的的的链链链链接接接接q静态链接方式静态链接方式(Static Linking)v在程序在程序运行前运行前，先将各目标模块及所需的库函，先将各目标模块及所需的库函数链接成一个完整的装配模块，以后不再拆开数链接成一个完整的装配模块，以后不再拆开v在将这几个目标模块装配成一个装入模块时，在将这几个目标模块装配成一个装入模块时，须解决以下两个问题须解决以下两个问题 对相对地址进行修改对相对地址进行修改 变换外部调用符号变换外部调用符号Page 222024/7/18程序的链接静态链接方式(Static Linking)PaOperating SystemOperating System程程程程序序序序的的的的链链链链接接接接模块模块 ACALL B；Return；0L1模块模块 BCALL C；Return；0M1模块模块 CReturn；0N1(a)目标模块目标模块(外存外存)装入前装入前链接修链接修改地址改地址0模块模块 AJSR“L”Return；L1模块模块 BJSR“LM”Return；LLM1LMLMN1模块模块 CReturn；(b)装入模块装入模块（外存）（外存）Page 232024/7/18程序的链接模块 ACALL B；Return；0L1模块 Operating SystemOperating System程程程程序序序序的的的的链链链链接接接接q装入时动态链接装入时动态链接(Loadtime Dynamic Linking)v将用户的源程序编译后所得的一组目标模块将用户的源程序编译后所得的一组目标模块在装入内存时采用在装入内存时采用边装入边链接边装入边链接的方式的方式便于修改和更新便于修改和更新 便于实现对目标模块的共享便于实现对目标模块的共享 Page 242024/7/18程序的链接装入时动态链接(Loadtime DynamicOperating SystemOperating System模块模块 ACALL B；Return；0L1模块模块 BCALL C；Return；0M1模块模块 CReturn；0N1外存外存0模块模块 AJSR“L”Return；L1模块模块 BJSR“LM”Return；LLM1LMLMN1模块模块 CReturn；内存内存程程程程序序序序的的的的链链链链接接接接装入时装入时链接修链接修改地址改地址Page 252024/7/18模块 ACALL B；Return；0L1模块 BCALLOperating SystemOperating System程程程程序序序序的的的的链链链链接接接接q运行时动态链接运行时动态链接(Run-time Dynamic Linking)v应用程序在每次运行的模块可能不相同应用程序在每次运行的模块可能不相同v运行时动态链接方式将对某些模块的运行时动态链接方式将对某些模块的链接推链接推迟到迟到执行执行时才进行时才进行，即在执行过程中，当，即在执行过程中，当发现一个被调用模块发现一个被调用模块尚未装入内存尚未装入内存时，立时，立即由即由OS去找到该模块并将之装入内存，去找到该模块并将之装入内存，把把它链接到调用者模块上它链接到调用者模块上v凡在执行过程中未被用到的目标模块，都不凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这会被调入内存和被链接到装入模块上，这样不仅可样不仅可加快程序的装入过程加快程序的装入过程，而且可，而且可节节省大量的内存空间省大量的内存空间Page 262024/7/18程序的链接运行时动态链接(Run-time Dynamic Operating SystemOperating System模块模块 ACALL B；Return；0L1模块模块 BCALL C；Return；0M1模块模块 CReturn；0N1外存外存0模块模块 AJSR“L”Return；L1内存内存执行时执行时链接修链接修改地址改地址Page 272024/7/18模块 ACALL B；Return；0L1模块 BCALLOperating SystemOperating System第第第第四四四四章章章章 存存存存储储储储器器器器管管管管理理理理q程序的装入和链接程序的装入和链接 q连续分配方式连续分配方式 q基本分页存储管理基本分页存储管理 q基本分段存储管理基本分段存储管理q虚拟存储器的基本概念虚拟存储器的基本概念q请求分页存储管理方式请求分页存储管理方式q页面置换算法页面置换算法q请求分段存储管理方式请求分段存储管理方式Page 282024/7/18第四章 存储器管理程序的装入和链接 Page 282023/Operating SystemOperating System连连连连续续续续分分分分配配配配方方方方式式式式q单一连续分配单一连续分配q固定分区分配固定分区分配q动态分区分配动态分区分配q可重定位分区分配可重定位分区分配q对换（对换（SwappingSwapping）Page 292024/7/18连续分配方式单一连续分配Page 292023/8/15Operating SystemOperating System单单单单一一一一连连连连续续续续分分分分配配配配q连续分配方式为连续分配方式为一个用户一个用户程序分配一个连续的程序分配一个连续的内存空间内存空间q单一连续分配单一连续分配是最简单的一种存储管理方式，是最简单的一种存储管理方式，但只能用于但只能用于单用户、单任务单用户、单任务的操作系统中的操作系统中q把内存分为把内存分为v系统区：系统区：OS使用，通常放在内存低址部分使用，通常放在内存低址部分v用户区：用户区：用户可使用的全部内存空间用户可使用的全部内存空间q存储器保护机构不健全，易造成系统破坏存储器保护机构不健全，易造成系统破坏q优点：易于管理优点：易于管理q缺点：对要求内存空间少的程序，造成内存浪缺点：对要求内存空间少的程序，造成内存浪费；程序全部装入，很少使用的程序部分也占费；程序全部装入，很少使用的程序部分也占用内存用内存Page 302024/7/18单一连续分配连续分配方式为一个用户程序分配一个连续的内存空间Operating SystemOperating System单单单单一一一一连连连连续续续续分分分分配配配配用户程序用户程序位于位于RAM中的中的操作系统操作系统0 xFFF.0位于位于RAM中的中的操作系统操作系统用户程序用户程序0ROM中的中的设备驱动程序设备驱动程序用户程序用户程序位于位于RAM中的中的操作系统操作系统0单一连续区存储管理单一连续区存储管理Page 312024/7/18单一连续分配用户程序位于RAM中的操作系统0 xFFF.0Operating SystemOperating System连连连连续续续续分分分分配配配配方方方方式式式式q单一连续分配单一连续分配q固定分区分配固定分区分配q动态分区分配动态分区分配q可重定位分区分配可重定位分区分配q对换（对换（SwappingSwapping）Page 322024/7/18连续分配方式单一连续分配Page 322023/8/15Operating SystemOperating System固固固固定定定定分分分分区区区区分分分分配配配配q最简单的可运行最简单的可运行多道程序多道程序的存储管理方式的存储管理方式q内存用户空间划分为若干个内存用户空间划分为若干个固定大小的区域固定大小的区域，每个分，每个分区中只装入区中只装入一道一道作业作业q划分分区的方法划分分区的方法 v分区大小相等分区大小相等：v即使所有的内存分区大小相等即使所有的内存分区大小相等太大：浪费太大：浪费太小：不够用太小：不够用 v分区大小不等分区大小不等：v划分为多个大、中、小搭配的分区划分为多个大、中、小搭配的分区根据程序大小决定所使用的分区根据程序大小决定所使用的分区 大班在大教室、小班在小教室大班在大教室、小班在小教室Page 332024/7/18固定分区分配最简单的可运行多道程序的存储管理方式Page 3Operating SystemOperating Systemq内存分配内存分配 v分区的信息根据分区使用表管理分区的信息根据分区使用表管理固固固固定定定定分分分分区区区区分分分分配配配配2020v使用界地址寄存器使用界地址寄存器v采用静态重定位采用静态重定位问题：并发进程数受分区个数的制约！问题：并发进程数受分区个数的制约！出现：有内存却不能运行程序或大进程无法运行！出现：有内存却不能运行程序或大进程无法运行！Page 342024/7/18内存分配 固定分区分配20使用界地址寄存器问题：并发进程数受Operating SystemOperating System连连连连续续续续分分分分配配配配方方方方式式式式q单一连续分配单一连续分配q固定分区分配固定分区分配q动态分区分配动态分区分配q可重定位分区分配可重定位分区分配q对换（对换（SwappingSwapping）Page 352024/7/18连续分配方式单一连续分配Page 352023/8/15Operating SystemOperating System动动动动态态态态分分分分区区区区分分分分配配配配q根据进程的实际根据进程的实际需要，动态地为需要，动态地为之分配内存空间之分配内存空间q分配中数据结构分配中数据结构 v空闲分区表空闲分区表 记录每个空闲记录每个空闲分区的情况分区的情况v空闲分区链空闲分区链 实现对空闲分实现对空闲分区的分配和链区的分配和链接接Page 362024/7/18动态分区分配根据进程的实际需要，动态地为之分配内存空间PagOperating SystemOperating System动动动动态态态态分分分分区区区区分分分分配配配配q分区分配算法分区分配算法 v首次适应算法首次适应算法FF v循环首次适应算法循环首次适应算法v最佳适应算法最佳适应算法v最差适应算法最差适应算法Page 372024/7/18动态分区分配分区分配算法 Page 372023/8/15Operating SystemOperating System动动动动态态态态分分分分区区区区分分分分配配配配q分区分配算法分区分配算法 v首次适应算法首次适应算法FF 空闲分区链以空闲分区链以地址递增顺序地址递增顺序链接链接分配时从分配时从链首开始查找链首开始查找，找到一个大小可满足的空，找到一个大小可满足的空闲分区，划出一块给请求者闲分区，划出一块给请求者优点：简单；优先利用低地址空闲区，保留高地址优点：简单；优先利用低地址空闲区，保留高地址大空闲区大空闲区缺点：会造成在低地址部分很多难以利用的小空闲缺点：会造成在低地址部分很多难以利用的小空闲分区，查找效率低分区，查找效率低v循环首次适应算法循环首次适应算法每次分配时每次分配时从上一次找到从上一次找到空闲分区的空闲分区的下一个空闲区下一个空闲区开始查找开始查找优点：减少查找空闲分区开销，空闲分区分布更均优点：减少查找空闲分区开销，空闲分区分布更均匀匀缺点：缺乏大的空闲区缺点：缺乏大的空闲区Page 382024/7/18动态分区分配分区分配算法 Page 382023/8/15Operating SystemOperating System动动动动态态态态分分分分区区区区分分分分配配配配v最佳适应算法最佳适应算法空闲区按容量由小到大排序空闲区按容量由小到大排序每次分配时，把能满足要求、又是每次分配时，把能满足要求、又是最小最小的分区分的分区分配给作业配给作业优点：不缺乏大的空闲区优点：不缺乏大的空闲区缺点：会在存储器中留直许多难以利用的小分区缺点：会在存储器中留直许多难以利用的小分区“零头（或碎片）零头（或碎片）”；查找效率低；查找效率低v最差适应算法最差适应算法空闲区按容量由大到小排序空闲区按容量由大到小排序每次分配时，把能满足要求、又是每次分配时，把能满足要求、又是最大最大的分区分的分区分配给作业配给作业优点：剩余的空间最大化，不出现太小的优点：剩余的空间最大化，不出现太小的“零头零头”缺点：缺乏大的空闲区缺点：缺乏大的空闲区首次适应被认为最好、最快，其次是循环，最佳最差首次适应被认为最好、最快，其次是循环，最佳最差（每次分配后剩下小碎片，难再分，不得不经常压缩（每次分配后剩下小碎片，难再分，不得不经常压缩内存，反而浪费内存，反而浪费CPU）Page 392024/7/18动态分区分配最佳适应算法首次适应被认为最好、最快，其次是循环Operating SystemOperating System动动动动态态态态分分分分区区区区分分分分配配配配q分区分配操作分区分配操作 v分配内存分配内存 从头开始查表从头开始查表检索完否？检索完否？m.sizeu.size?m.sizeu.sizesize?从该分区中划出从该分区中划出u.size大小的分区大小的分区将该分区分配给请求者修将该分区分配给请求者修改有关数据结构改有关数据结构返回返回返回返回继续检索下一个表项继续检索下一个表项将该分区从链中移出将该分区从链中移出YNNYYN解决碎解决碎片问题片问题Page 402024/7/18动态分区分配分区分配操作 从头开始查表检索完否？m.sizeOperating SystemOperating System动动动动态态态态分分分分区区区区分分分分配配配配q分区分配操作分区分配操作 v回收内存回收内存v进程运行结束释放内存时，系统根据回收区的进程运行结束释放内存时，系统根据回收区的首地址，把它插入到空闲链表中。根据回收区首地址，把它插入到空闲链表中。根据回收区的位置，有四种情况需处理：的位置，有四种情况需处理：回收区与插入点的回收区与插入点的前一个前一个空闲分区相邻接空闲分区相邻接回收区与插入点的回收区与插入点的后一个后一个空闲分区相邻接空闲分区相邻接 回收区同时与插入点的回收区同时与插入点的前、后前、后两个分区相邻两个分区相邻接接回收区不与任何空闲区邻接回收区不与任何空闲区邻接Page 412024/7/18动态分区分配分区分配操作 Page 412023/8/15Operating SystemOperating System动动动动态态态态分分分分区区区区分分分分配配配配空闲区空闲区回收区回收区回收区回收区空闲区空闲区空闲区空闲区回收区回收区空闲区空闲区回收区回收区情况情况1 1情况情况2 2情况情况3 3情况情况4 4Page 422024/7/18动态分区分配空闲区回收区回收区空闲区空闲区回收区空闲区回收区Operating SystemOperating System2)回收内存 回收区F1F2回收区F2回收区F1回收区回收区Page 432024/7/182)回收内存 回收区F1F2回收区F2回收区F1回收区回Operating SystemOperating System动动动动态态态态分分分分区区区区分分分分配配配配q分区式存储管理的优缺点分区式存储管理的优缺点 优点：优点：便于动态申请内存便于动态申请内存 便于共享内存便于共享内存 便于动态链接便于动态链接 缺点：缺点：碎片问题碎片问题(外碎片外碎片)，要求连续的内存空间，要求连续的内存空间，内存利用率不高，受实际内存容量限制内存利用率不高，受实际内存容量限制Page 442024/7/18动态分区分配分区式存储管理的优缺点Page 442023/8Operating SystemOperating System动动动动态态态态分分分分区区区区分分分分配配配配q碎片问题碎片问题v经过一段时间的分配回收后，内存中存在很多经过一段时间的分配回收后，内存中存在很多很小的空闲块。它们每一个都很小，不足以满很小的空闲块。它们每一个都很小，不足以满足分配要求；但其总和满足分配要求。这些空足分配要求；但其总和满足分配要求。这些空闲块被称为碎片闲块被称为碎片v造成存储资源的浪费造成存储资源的浪费q碎片问题的解决碎片问题的解决v紧凑技术：通过在内存移动程序，将所有小的紧凑技术：通过在内存移动程序，将所有小的空闲区域合并为大的空闲区域空闲区域合并为大的空闲区域 （紧缩技术，紧致技术，浮动技术，搬家技术）（紧缩技术，紧致技术，浮动技术，搬家技术）v问题：开销大；移动时机问题：开销大；移动时机Page 452024/7/18动态分区分配碎片问题Page 452023/8/15Operating SystemOperating System连连连连续续续续分分分分配配配配方方方方式式式式q单一连续分配单一连续分配q固定分区分配固定分区分配q动态分区分配动态分区分配q可重定位分区分配可重定位分区分配q对换（对换（SwappingSwapping）Page 462024/7/18连续分配方式单一连续分配Page 462023/8/15Operating SystemOperating System4.2.4 可重定位分区分配可重定位分区分配 1.动态重定位的引入动态重定位的引入 80kb用户程序9用户程序6用户程序3用户程序1操作系统紧紧紧紧凑凑凑凑Page 472024/7/184.2.4 可重定位分区分配 1.动态重定位的引入 Operating SystemOperating System可可可可重重重重定定定定位位位位分分分分区区区区分分分分配配配配q动态重定位的引入动态重定位的引入v连续分配存在连续分配存在的问题的问题必须有足够大的必须有足够大的连续空间才能分连续空间才能分配配v解决方法解决方法：“拼接拼接”或或“紧凑紧凑”的引入的引入Page 482024/7/18可重定位分区分配动态重定位的引入Page 482023/8/Operating SystemOperating System可可可可重重重重定定定定位位位位分分分分区区区区分分分分配配配配q动态重定位的实现动态重定位的实现v作业装入内存后的所有地址仍是作业装入内存后的所有地址仍是相对地址相对地址，将，将相相对地址对地址转换转换成成物理地址物理地址的工作的工作在指令执行时在指令执行时进行进行v需要有硬件地址变换机构的支持需要有硬件地址变换机构的支持Page 492024/7/18可重定位分区分配动态重定位的实现Page 492023/8/Operating SystemOperating System3.动态重定位分区分配算法动态重定位分区分配算法 动态重定位分区分配算法，与动态分区分配算法基本上相同；差别仅在于：在这种分配算法中，增加了“紧紧紧紧凑凑凑凑”功能，通常是在找不到足够大的空闲分区来满足用户需求时，进行紧凑。图4-10示出了动态重定位分区分配算法框图。Page 502024/7/183.动态重定位分区分配算法 动态重定位分区分配算Operating SystemOperating System可可可可重重重重定定定定位位位位分分分分区区区区分分分分配配配配q动态重定位分区分配算法动态重定位分区分配算法v在一个分区释放后立即移动在一个分区释放后立即移动v当请求得不到满足时再移动当请求得不到满足时再移动Page 512024/7/18可重定位分区分配动态重定位分区分配算法Page 512023Operating SystemOperating System可可可可重重重重定定定定位位位位分分分分区区区区分分分分配配配配q可重定位分区的优缺点可重定位分区的优缺点v优优点点:解解决决了了可可变变分分区区分分配配所所引引入入的的“外外零零头头”问问题题。消除内存碎片，提高内存利用率。消除内存碎片，提高内存利用率。v缺点缺点:提高硬件成本，紧凑时花费时间。提高硬件成本，紧凑时花费时间。Page 522024/7/18可重定位分区分配可重定位分区的优缺点Page 522023/Operating SystemOperating System连连连连续续续续分分分分配配配配方方方方式式式式q单一连续分配单一连续分配q固定分区分配固定分区分配q动态分区分配动态分区分配q可重定位分区分配可重定位分区分配q对换（对换（SwappingSwapping）Page 532024/7/18连续分配方式单一连续分配Page 532023/8/15Operating SystemOperating System4.2.5 对换对换(Swapping)1.对换的引入对换的引入 对换（也称交换）技术，最早用在单用户系统，在内存中仅驻留一道用户作业。所有其它作业都驻留在外存的后备队列上，只调入一个作业进入内存运行；此作业的时间片用完时，该作业调至外存，再将后备队列上的另一个作业调入内存；也让它运行一个时间片的时间，然后又将它调出，再调下一个作业进入内存。因为其效率太低，其CPU大约有一半的时间，都处于空闲状态。Page 542024/7/184.2.5 对换(Swapping)1.对换的引入 Operating SystemOperating System对对对对换换换换（S Swwa ap pp pi in ng g）q对换的引入对换的引入 v所谓所谓“对换对换”，是指把内存中暂时不能运行，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和具备运行条件的进程或进程所需要的程序和数据，调入内存。对换是数据，调入内存。对换是提高内存利用率提高内存利用率的的有效措施有效措施v如果对换是以整个进程为单位，称为如果对换是以整个进程为单位，称为“整体整体对换对换”或或“进程对换进程对换”v如果对换是以如果对换是以“页页”或或“段段”为单位进行的，为单位进行的，则称为则称为“页面对换页面对换”或或“分段对换分段对换”，又统，又统称为称为“部分对换部分对换”Page 552024/7/18对换（Swapping）对换的引入 Page 552023/Operating SystemOperating System4.2.5 对换对换(Swapping)1.对换的引入对换的引入 对换是以整个进程为单位，便称之为“整整整整体体体体对对对对换换换换”或或或或“进程对换进程对换进程对换进程对换”，解决内存紧张问题；对换是以“页页页页”或或或或“段段段段”为单位，则分别称之为“页页页页面对换面对换面对换面对换”或或或或“分段对换分段对换分段对换分段对换”，又统称为“部分对换部分对换部分对换部分对换”；为了实现进程对换，系统必须能实现以下三方面的功能：（1）对换空间的管理；（2）进程的换出；（3）进程的换入。Page 562024/7/184.2.5 对换(Swapping)1.对换的引入 Operating SystemOperating System对对对对换换换换（S Swwa ap pp pi in ng g）q对换空间的管理对换空间的管理v外存中对换区主要存放从内存中换出的进程，外存中对换区主要存放从内存中换出的进程，对换空间管理的对换空间管理的主要目标主要目标是是提高进程换入和换提高进程换入和换出的速度出的速度v对换区中空闲盘块的管理对换区中空闲盘块的管理：在系统中配置相应：在系统中配置相应的数据结构，记录外存的使用情况。形式与内的数据结构，记录外存的使用情况。形式与内存在动态分区分配方式中所用数据结构相似，存在动态分区分配方式中所用数据结构相似，即用即用空闲分区表或空闲分区链空闲分区表或空闲分区链。在空闲分区表。在空闲分区表中的每个表目中应包含两项，中的每个表目中应包含两项，即即对换区的首址对换区的首址及其及其大小大小，它们的单位是盘块号和盘块数，它们的单位是盘块号和盘块数v对换区的分配采用对换区的分配采用连续分配方式连续分配方式，分配算法可，分配算法可以是以是首次适应算法首次适应算法、循环首次适应算法循环首次适应算法或或最佳最佳适应算法适应算法Page 572024/7/18对换（Swapping）对换空间的管理Page 572023Operating SystemOperating System2.对换空间的管理对换空间的管理 由于对对换区的分配，是采用连续分配方式，对换区 的回收操作也可分为下述四种情况，即：（1）回收区与插入点的前一分区F1相邻接；（2）回收区与插入点的后一分区F2相邻接；（3）回收区还同时与F1和F2二个分区相邻接；（4）回收区的前、后没有与之相邻接的空闲分区。对这几种情况的处理方法也与动态分区分配式的方法相同。回收区F1F2回收区F2回收区F1回收区回收区Page 582024/7/182.对换空间的管理 由于对对换区的分配，是Operating SystemOperating System对对对对换换换换（S Swwa ap pp pi in ng g）q进程的换出与换入进程的换出与换入v进程的换出进程的换出系统先系统先选择选择处于处于“阻塞阻塞”状态状态且且优先级最低优先级最低的进程作为换出进程，然后启动盘块，将该的进程作为换出进程，然后启动盘块，将该进程的程序和数据传送到磁盘的进程的程序和数据传送到磁盘的对换区对换区上。上。若传送未出现错误，便回收其所占用的内存若传送未出现错误，便回收其所占用的内存空间，并对该进程的空间，并对该进程的进程控制块进程控制块做相应的修做相应的修改改v进程的换入进程的换入系统应定时地查看所有进程的状态，从中找系统应定时地查看所有进程的状态，从中找出出“就绪就绪”状态状态但已换出的进程，将其中但已换出的进程，将其中换换出时间出时间(换出到磁盘上换出到磁盘上)最久最久的进程作为换入的进程作为换入进程，将之换入，直至已无可换入的进程或进程，将之换入，直至已无可换入的进程或无可换出的进程为止无可换出的进程为止Page 592024/7/18对换（Swapping）进程的换出与换入Page 59202Operating SystemOperating System可可可可重重重重定定定定位位位位分分分分区区区区分分分分配配配配q可重定位分区的优缺点可重定位分区的优缺点v优优点点:解解决决了了可可变变分分区区分分配配所所引引入入的的“外外零零头头”问问题题。消消除除内内存存碎碎片片，提高内存利用率。提高内存利用率。v缺缺点点:提提高高硬硬件件成成本本，紧凑时花费时间。紧凑时花费时间。Page 602024/7/18可重定位分区分配可重定位分区的优缺点Page 602023/Operating SystemOperating System可可可可重重重重定定定定位位位位分分分分区区区区分分分分配配配配q多重分区多重分区v即即一一个个程程序序可可以以占占据据主主存存中中不不连连续续的的多多个个分分区区可以解决碎片问题可以解决碎片问题v支支持持结结构构化化程程序序设设计计，操操作作系系统统往往往往把把一一道道作作业业分分成成若若干干片片段段如如子子程程序序、主主程程序序、数数据据组等。组等。v需要硬件支持（多对界地址寄存器，需要硬件支持（多对界地址寄存器，重定位重定位寄存器寄存器）v管理复杂管理复杂Page 612024/7/18可重定位分区分配多重分区Page 612023/8/15Operating SystemOperating System可可可可重重重重定定定定位位位位分分分分区区区区分分分分配配配配q多重分区多重分区Page 622024/7/18可重定位分区分配多重分区 Page 622023/8/15Operating SystemOperating Systemq分区的保护分区的保护为为了了防防止止一一道道作作业业有有意意或或无无意意地地破破坏坏操操作作系系统统或或其其它它作作业业。一一般般说说来来，没没有有硬硬件件支支持持，实实现有效的存储保护是困难的。通常采取：现有效的存储保护是困难的。通常采取：v界限寄存器方式界限寄存器方式v保护键方式保护键方式v两种措施，或二者兼而有之。两种措施，或二者兼而有之。可重定位分区分配可重定位分区分配可重定位分区分配可重定位分区分配Page 632024/7/18分区的保护可重定位分区分配Page 632023/8/15Operating SystemOperating Systemq保护过程保护过程防止地址越界防止地址越界 一般由硬件提供一对寄存器：一般由硬件提供一对寄存器：v 基址寄存器：存放起始地址基址寄存器：存放起始地址v 限长寄存器：存放长度限长寄存器：存放长度（上界寄存器（上界寄存器/下界寄存器）下界寄存器）可重定位分区分配可重定位分区分配可重定位分区分配可重定位分区分配Page 642024/7/18保护过程防止地址越界可重定位分区分配Page 64202Operating SystemOperating Systemq界限寄存器保护界限寄存器保护v60K访问地址访问地址=124Kv则产生访问地址界中断则产生访问地址界中断可重定位分区分配可重定位分区分配可重定位分区分配可重定位分区分配Page 652024/7/18界限寄存器保护可重定位分区分配Page 652023/8/1Operating SystemOperating Systemq基址、限长寄存器保护基址、限长寄存器保护v相对地址相对地址限长寄存器的值限长寄存器的值v则产生访问地址界中断则产生访问地址界中断可重定位分区分配可重定位分区分配可重定位分区分配可重定位分区分配Page 662024/7/18基址、限长寄存器保护可重定位分区分配Page 662023/Operating SystemOperating Systemq防止操作越权防止操作越权 对于允许多个进程共享的存储区域，对于允许多个进程共享的存储区域，每个进程都有自己的访问权限。如果一个每个进程都有自己的访问权限。如果一个进程对共享区域的访问违反了权限规定，进程对共享区域的访问违反了权限规定，则发生操作越权则发生操作越权 即读写保护即读写保护可重定位分区分配可重定位分区分配可重定位分区分配可重定位分区分配Page 672024/7/18防止操作越权可重定位分区分配Page 672023/8/15Operating SystemOperating Systemq保护键方式保护键方式可重定位分区分配可重定位分区分配可重定位分区分配可重定位分区分配Page 682024/7/18保护键方式可重定位分区分配Page 682023/8/15Operating SystemOperating System4.3 基本分页存储管理方式基本分页存储管理方式 连续分配方式会形成许多“碎片”，通过“紧凑”方法将碎片拼接成可用的大块空间，但须为此付出很大开销。根据离散分配时所用基本单位的不同，又可把离散分配方式分以下三种：1、分页存储管理、分页存储管理 2、分段存储管理、分段存储管理 3、段页式存储管理、段页式存储管理 Page 692024/7/184.3 基本分页存储管理方式 连续分配方式Operating SystemOperating System存储器管理存储器管理连续分配方式连续分配方式离散分配方式离散分配方式分页存储管理分页存储管理分段存储管理分段存储管理基本分页存储管理基本分页存储管理请求分页存储管理请求分页存储管理基本分段存储管理基本分段存储管理请求分段存储管理请求分段存储管理基本分页存储管理基本分页存储管理基本分段存储管理基本分段存储管理请求分页存储管理请求分页存储管理请求分段存储管理请求分段存储管理段页式存储管理段页式存储管理虚拟存储器虚拟存储器页面置换算法页面置换算法Page 702024/7/18存储器管理连续分配方式离散分配方式分页存储管理分段存储管理基Operating SystemOperating System第第第第四四四四章章章章 存存存存储储储储器器器器管管管管理理理理q程序的装入和链接程序的装入和链接 q连续分配方式连续分配方式 q基本分页存储管理基本分页存储管理 q基本分段存储管理基本分段存储管理q虚拟存储器的基本概念虚拟存储器的基本概念q请求分页存储管理方式请求分页存储管理方式q页面置换算法页面置换算法q请求分段存储管理方式请求分段存储管理方式Page 712024/7/18第四章 存储器管理程序的装入和链接 Page 712023/Operating SystemOperating System4.3 基本分页存储管理方式基本分页存储管理方式 在分页存储管理的方式中，如果不具备页面对对换换功能，则称为基基基基本本本本的的的的（纯纯纯纯）分分分分页页页页管管管管理理理理方方方方式式式式，它不具有支持实现虚拟存储器的功能，它要求把每个作业全部装入内存后方能运行。Page 722024/7/184.3 基本分页存储管理方式 在分页存储管Operating SystemOperating System基基基基本本本本分分分分页页页页存存存存储储储储管管管管理理理理q页面与页表页面与页表q地址变换机构地址变换机构q两级和多级页表两级和多级页表Page 732024/7/18基本分页存储管理页面与页表Page 732023/8/15Operating SystemOperating System离离离离散散散散分分分分配配配配方方方方式式式式q连续分配方式连续分配方式要求为一个进程分配连续的内存空要求为一个进程分配连续的内存空间，会形成许多间，会形成许多“碎片碎片”，尽管采用尽管采用“紧凑紧凑”技技术可以解决这个问题，但要为移动大量信息花去术可以解决这个问题，但要为移动大量信息花去不少的处理机时间，代价较高不少的处理机时间，代价较高q如果允许一个进程直接分散地装入到许多不相邻如果允许一个进程直接分散地装入到许多不相邻接的分区中，称为接的分区中，称为离散分配方式离散分配方式q离散分配方式有离散分配方式有分页存储管理方式分页存储管理方式和和分段存储管分段存储管理方式理方式q分页：把用户程序按逻辑页划分成大小相等的部分页：把用户程序按逻辑页划分成大小相等的部分，称为页或虚页。从分，称为页或虚页。从0 0开始编制页号，页内地址开始编制页号，页内地址是相对于是相对于0 0编址。编址。Page 7