第四章存储管理

1、第第4 4章章 存储管理存储管理教学内容教学内容:1、程序的装入和链接、程序的装入和链接2、分区存储管理方式、分区存储管理方式3、虚拟存储器的基本概念、虚拟存储器的基本概念4、分页存储管理方式、分页存储管理方式5、页面置换算法、页面置换算法6、分段存储管理方式、分段存储管理方式7、段页存储管理方式、段页存储管理方式教学重点教学重点:1、程序的装入（地址空间、名字空间、物理空间、地址重定位）、程序的装入（地址空间、名字空间、物理空间、地址重定位）2、虚拟存储器的基本概念、虚拟存储器的基本概念3、分页存储管理方式、分页存储管理方式4、页面置换算法、页面置换算法教学难点教学难点:1、地址重定位、地址

2、重定位2、分页存储管理方式、分页存储管理方式3页面置换算法页面置换算法4.1 4.1 引言引言l 内存管理的需求内存管理的需求l 内存管理使用的技术内存管理使用的技术+ 分区式管理：固定式、可变式分区、多重分区分区式管理：固定式、可变式分区、多重分区+ 页式管理、页式管理、+ 段式管理段式管理+ 段页式管理段页式管理l 操作系统的存储管理机构必须解决以下问题操作系统的存储管理机构必须解决以下问题+ 内存分配内存分配+ 存储保护存储保护+ 地址变换地址变换+ 存储共享存储共享+ 存储扩充存储扩充差距差距硬件无关、应用相关硬件无关、应用相关用户对内存的使用要求用户对内存的使用要求硬件相关、应用无关

3、硬件相关、应用无关内存硬件的使用特性内存硬件的使用特性操作系统内存管理功能的工作范围：操作系统内存管理功能的工作范围：一、主存管理一、主存管理二、存储层次、性能指标、主存作用二、存储层次、性能指标、主存作用 1、存储层次、存储层次、性能指标性能指标( (容量、速度、存取频度、成本容量、速度、存取频度、成本) ) 内存 寄存器 外存容量小速度高 存取频度高 成本高存储器主存（内存）辅存（外存）系统区（OS标准子程序） 用户区（用户程序、数据）2、主存作用、主存作用中中级级对主存的性能要求:(1)主存速度要快到与CPU执行指令的速度相匹配主存技术的实际发展由于技术原因和经济原因,速度赶不上CPU速

4、度容量赶不上或勉强赶上应用程序长增长(2)主存容量要大到能装下当前运行的程序与数据(3)开机上电时主存能一 直正常工作保持稳定可靠4.2 4.2 分区式存储管理分区式存储管理l 地址重定位地址重定位+ 静态重定位静态重定位+ 动态重定位动态重定位l 固定式分区固定式分区l 可变式分区可变式分区l 多重分区多重分区l 覆盖与交换覆盖与交换l 可变分区分配和释放算法可变分区分配和释放算法为多个程序安排内存为多个程序安排内存PCB1PCB2PCB3程序1程序2程序3 OS 分配内存程序1程序2程序3名字空间名字空间:程序中符号名的集合地址空间地址空间:一个目标程序所限定的地址范围, 通常把编译程序形

5、成的从0开始编址的地址空间称为作业的地址空间。每个可执行程序都有一个自己的地址空间。存储空间：存储空间：是指主存中一系列存储信息的物理单元的集合。这些单元的编号称为物理地址或绝对地址、内存地址。存储空间的大小是由主存的实际存储空间的大小是由主存的实际容量决定的。容量决定的。存储空间按字节编址，从0开始，扩展到系统配置可用的最大数量。32位计算机的内存空间最大值？地址空间是逻辑地址的集合。存储空间是物理地址的集合一个是虚的概念，一个是实的物体。程序的名字空间、地址空间及存储空间符号符号源程序源程序目标目标代码代码可执行可执行代码代码汇编汇编编译编译连接连接地址重定位地址重定位名 字 空 间名 字

6、 空 间*.C地址空间地址空间*.OBJ存储空间存储空间*.EXE:x=x+1:R=XR=R+1X=R:0:K100:100+K:R=XR=R+1X=R:地址重定位地址重定位: :地址空间中使用的逻辑地址变换成主存空间中的物理地址的过程。物理（实际）地址=相对（逻辑）地址+定位地址 虚拟空间虚拟空间 内存空间内存空间 12345Load A,500 0：100：500：800： 1000：0+1000 123451500：500+10001800：800+1000Load A,150015001100：100+1000静态地址重定位静态地址重定位 装入一个作业时，把作业中的指令地址全部转换为绝

7、对地址（地址转换工作在作业执行前集中一次完成）在作业执行过程中无须再进行地址转换工作。优点：加快作业的运行速度。缺点：作业一旦被装入内存，不允许再移动；程序的存储空间连续。动态地址重定位：动态地址重定位： 动态地址重地位是在程序执行过程中，在cpu访问内存之前,将要访问的程序或数据地址转换成内存地址. 动态重定位依靠硬件地址变换机构完成。 虚拟空间虚拟空间 内存空间内存空间 12345Load A,500 0：100：500：1000 1500： BRLoad A,15001000：1100： 12345Load A,500500 优点：（1）目标模快不加修改而装入内存（2）一个程序有若干个相

8、对独立的目标组成时，各目标模快装入内存的存储区不必相连600：1600：实际地址-相对地址:1000-0+ VR500程序在其生命周期各阶段表现出的地址形式程序在其生命周期各阶段表现出的地址形式（1）编译或汇编阶段 n编译u 两个转换:F将语句转换为机器指令F将符号转换为内存地址u注意:1.转换出的地址可能是相对地址2.可能不是所有符号都已转换为内存地址（2）连接阶段(可执行目标程序) a.统一各目标程序中的相对地址为该程序的相对地址 b.符号地址 内存地址（相对地址）（3）装入阶段 可能需要重定位可能需要重定位（4）执行阶段 可能需要重定位可能需要重定位（5）释放空间 以二进制文件驻流在硬盘

9、上一、一、分区式存储管理分区式存储管理将内存划分成若干个连续的区域，每个分区只能存储一个程序。缺点：内存不能充分利用、内存不能扩充二、固定分区分配二、固定分区分配 运行其间不再划分。内存利用率不高区号区号大小大小起始地址起始地址标志标志123416K32K64K124K20K36K68K132K已分配已分配已分配已分配已分配已分配未分配未分配操作系统操作系统作业作业A作业作业C作业作业B020K36K68K132K第第1分区分区第第2分区分区第第3分区分区第第4分区分区（未分配）（未分配）（b） 内存分配内存分配图图（a） 分区说明表分区说明表可可变变分分区区示示例例三、可变分区分配三、可变分

10、区分配 分区的个数大小不是固定不变、分区根据装入的作业动态划分可变分区说明表可变分区说明表序号序号P P大小大小起址起址状态状态1 18 8K K2020K K已分配已分配2 23232K K2828K K已分配已分配3 3空表目空表目4 4120120K K9292K K已分配已分配5 5空表目空表目已分配分区说明已分配分区说明 序号序号F大小大小起址起址状态状态132K60K空闲空闲2300K212K空闲空闲3空表目空表目4空表目空表目5空表目空表目空闲分区说明表空闲分区说明表 可变分区分配和释放算法可变分区分配和释放算法分配算法一般有：最佳适应（Best Fit）算法，它从全部空闲区中找

11、出能满足作业需求的容量最小的空闲区分配之，此法的着眼点是使碎片尽量小。最先适应（First Fit）算法，它按序查找，把最先找到的满足需求的空闲区分配之，此法的目的在于尽量减少查找时间。最坏适应（Worst Fit）算法,此法的目的在于使剩下的空区最大，减少空区碎片机会。下次适应算法（Next Fit），此法将空闲区链成环形链，每次分配从上次分配的位置开始查找合适的空闲区。 可变分区的分配算法可变分区的分配算法F=F+1置空闲区号置空闲区号F =1=LocF的起始地址的起始地址置置置置F的状态的状态=空表目空表目置置置置P的大小的大小=Xk置置P的始址的始址=Loc置置P的的=已分配已分配本次

12、无法分配本次无法分配=申请分配一个申请分配一个xk大小的分区大小的分区F 已超出最大项号？已超出最大项号？F 的状态的状态=空表目？空表目？F的大小的大小 Xk?在已分配表中找一个在已分配表中找一个状态状态=空表目的序号空表目的序号P返回序号返回序号P否否是是是是否否否否否否大于大于等于等于F的大小的大小 Xk=新空闲块大小新空闲块大小Loc+Xk=新起始地址新起始地址回收示意图回收示意图空闲区空闲区F1程序区程序区回收区回收区R空闲区空闲区F1 空闲区空闲区F2程序区程序区回收区回收区R 空闲区空闲区F2程序程序程序程序回收区回收区R 程序区程序区程序区程序区回收区回收区R 空闲区空闲区F2

13、程序区程序区程序区程序区回收区回收区R可变分区的回收算法可变分区的回收算法=置新空闲分区的置新空闲分区的大小大小=Size始址始址=Loc状态状态=空闲空闲在空闲分区表中置在空闲分区表中置F2为空闲表目为空闲表目分区分区R与与F1邻接？邻接？分区分区R与与F1邻接？邻接？在空闲分区表中在空闲分区表中找一个空闲表目找一个空闲表目分区分区R与与F2邻接？邻接？SizeSize+ F2的大小的大小已分配区说明表中已分配区说明表中置置R的状态的状态 = 空表目空表目Size分区分区R的大小的大小Loc分区的起始地址分区的起始地址否否是是是是是是否否否否请求回收分区请求回收分区R置空闲分区置空闲分区F

14、F2 2的大小的大小 =Size+ F1的大小的大小置空闲分区置空闲分区F2的的大小大小=Size始址始址=Loc返回返回F F1 1四、多重分区四、多重分区基址寄存器基址寄存器1作业作业1作业作业1OS限长寄存器限长寄存器1基址寄存器基址寄存器2限长寄存器限长寄存器2提出背景：大程序、小空间解决方法：按需装入数据，按需装入数据，不同时刻执行的代码或数据相互覆盖、需要事先确定所有代码和数据的位置（相互覆盖位置）五、覆盖技术五、覆盖技术覆盖技术举例覆盖技术举例A 20KB 50KF 30KC 30KD 20KE 40KRAMA 20K覆盖区覆盖区0 50K覆盖区覆盖区1 40KBCFDE对覆盖的

15、认识对覆盖的认识（1）覆盖由操作系统自动化完成，但要求作业各模块间有 明确的调用结构，程序员必须正确设计覆盖结构和编程， 任务繁重（2）额外的I/O操作 覆盖通常限于用在微机和其他内存容量有限的或缺乏对更 先进技术的硬件支持的系统中交换（swap）技术：发生进程切换时，总是把当前进程的所有代码、数据、栈全部从内存复制至外存，再把新当前进程的所有代码、数据、栈全部从外存复制至内存。盘交换区：在外存外存中用于存放所有换出进程的代码、数据、栈。六、交换技术六、交换技术交换技术中的五个问题交换技术中的五个问题:1.将哪个进程换出(入)内存?2.何时应发生交换?3.交换时需要做那些工作?4.换回位置的确

16、定原则5.交换所需时间导致对时间片的影响、对程序长度保存使用要求、动态扩充时要及时登记的管理要求4.3 4.3 分页式存储管理分页式存储管理l实存管理实存管理+ 分页原理分页原理+ 页表页表+ 地址变换机构地址变换机构l虚存管理虚存管理+ 页表的扩充页表的扩充+ 缺页中断处理缺页中断处理+ 页面淘汰算法页面淘汰算法+ 快表快表+ 页面共享页面共享一、分页原理一、分页原理1、等分内存、等分内存2、等分地址空间、等分地址空间3、地址形式、地址形式4、页面尺寸、页面尺寸:512-8KB0 0 0 0 01 0 0 0 0 0 0 0 0 0 0 页内地址页内地址 页号页号相对页号相对页号P页内地值页

17、内地值D物理块号物理块号页号页号二、建立页表二、建立页表有效（虚地址）有效（虚地址）操作系统操作系统物理块号物理块号特征特征页号页号作业作业2页表页表4528物理地址物理地址物理块号物理块号页表起始地址页表起始地址页表长度页表长度页表始址寄存器页表始址寄存器页号页号页内相对位移页内相对位移内存内存8644外存外存LOAD 1,25004522150三、地址变换过程三、地址变换过程2022/2/20思考思考1 1： 对指令对指令LOAD A 5000LOAD A 5000进行地址重定位（页面长进行地址重定位（页面长1K1K；页表中页面对应关系为；页表中页面对应关系为0-10-1、1-31-3、2

18、-42-4、3-63-6、4-74-7、5-85-8、6-96-9）。）。思考思考2 2： 对指令对指令LOAD A 5000LOAD A 5000进行地址重定位（页面长进行地址重定位（页面长2K2K；页表中页面对应关系为；页表中页面对应关系为0-10-1、1-31-3、2-42-4、3-63-6、4-74-7、5-85-8、6-96-9）。）。请求分页页表请求分页页表页号特征内存块号外存块号修改位 访问位0 0 011011淘汰优先级0 1此页不在内存此页在内存Linux页表项定义页表项定义缺缺页页中中断断处处理理四、缺页处理四、缺页处理产生原因：产生原因： 当前要执行的页信息不在主存中当前

19、要执行的页信息不在主存中调用过程：调用过程： 文件系统管理文件系统管理 设备管理设备管理 进程状态地转换进程状态地转换 缺页缺页中断处理中断处理过程过程页表页表相对页号物理块号特征位外存地址0123m-1存放位置、页表始址寄存器（当前运行用户程序的页表始址）存放位置、页表始址寄存器（当前运行用户程序的页表始址）快表快表序号相对页号物理块号访问过特征位0123m-1快表地址映象快表地址映象35805628快表的地址映象操作快表的地址映象操作 五、页面交换五、页面交换1、调页方式 请调：动态地址变换机构产生一个缺页中断信号，OS接到信号后调用缺页中断处理程序。 预调：按照某种算法，预测不久将要用到

20、的页面并预先调入内存待用。2、淘汰时机 设置空闲临界量3、淘汰算法 抖动：频繁进行页面调度，造成系统效率下降。页面淘汰算法页面淘汰算法l先进先出(FIFO)l最近最久未使用淘汰算法(LRU)l最近不频繁使用淘汰算法(LFU)l最优算法(OPT) 以上几种淘汰算法中，FIFO算法最简单，但效率不高，有异常现象。LRU的近似算法和LFU是较为实用的算法，效果较好，实现也不难。OPT算法是一种最佳算法，但并不实用，因为要跟踪各页面方可预测未来。而这种预测往往是很困难的。目的：减少页面交换次数，节约处理机时间其他补救措施：1、在内存中的页若未被修改则在被淘汰时不必写回外存2、预淘汰方式，内存保留少量空

21、页，减少延迟时间3、优化访问磁盘次序页式存储管理的保护措施：1、程序隔离：页面映像方法2、页面的存取控制：在页表中设置一个保护位2022/2/20思考思考3 3： 采用先进先出页面淘汰算法的系统中，采用先进先出页面淘汰算法的系统中，一进程在内存占一进程在内存占4 4块，页面访问序列为块，页面访问序列为1 1、2 2、3 3、4 4、1 1、2 2、5 5、1 1、2 2、3 3、4 4、5 5、6 6、。运行、。运行时会产生时会产生( )( )次缺页中断。次缺页中断。4.4 4.4 分段存储管理分段存储管理一、原因一、原因: (1)分区容易出现碎片分区容易出现碎片(固定、动态固定、动态) (2)分页是利用率不高分页是利用率不高 页式系统中一页或页号相连的几个逻辑页上存页式系统中一页或页号相连的几个逻辑页上存放的内容一般不是一个逻辑意义完整的信息单位，放的内容一般不是一个逻辑意义完整的信息单位，请调一页时可能只用到一部分内容。请调一页时可能只用到一部分内容。 段式地址结构段式地址结构段号段号s 段内位移段内位移w分段地址空间分段地址空间:段表段表:二、段式地址变换二、段式地址变换段号段号段内地址段内地址s w长度长度基址基址段表段表第第s段