第4章 存储器管理

第四章存储器管理主要内容4.1存储管理概述4.2连续分配方式4.3分页式存储管理4.4分段式存储管理4.5覆盖与交换技术4.6虚拟存储器的基本概念4.7请求分页存储管理4.8请求分段存储管理目的和要求通过本章的学习，使学生理解和掌握存储器管理的有关概念、主要功能、工作原理和实现方法，并能够进行定量及定性的性能分析。重点和难点1、存储器管理的主要功能；2、逻辑地址、物理地址、地址映射、内存碎片、虚拟存储器等概念；3、分区存储管理的实现思想；4、（请求）分页存储管理的实现思想；5、（请求）分段存储管理的实现思想；6、常用的页面置换算法。4.1存储管理概述4.1.1存储器的层次结构存储器是信息处理的来源与归宿，占据重要位置任何一种存储装置，都无法同时从速度与容量两方面，满足用户的需求实际上它们组成了一个速度由快到慢，容量由小到大的存储装置层次结构存储器层次高速缓存内存外存存取时间减少存取速度增加存取成本增加存储容量减少在辅助硬件和OS的支持下,将快速存储设备和大容量存储设备构成为统一的整体从而形成一种存储器层次结构,称存储体系虚拟存储器就是一种内存-外存层次结构高速缓存是一种高速缓存-内存层次结构4.1.2存储管理的功能1.内存的分配和管理分配结构：登记内存使用情况位示图法空闲区表空闲区链放置策略：一种选择内存空闲区的策略回收策略：确定回收时机，修改分配结构调入策略：控制外存数据的调入置换策略：控制内存数据的换出2.内存的共享和保护内存的共享纯代码共享：节省内存空间数据共享：进程通信内存的保护两个方面•防止地址越界•防止操作越权三种手段•下限寄存器+上限寄存器•基址寄存器+限长寄存器——界限寄存器+CPU状态•存储键+存取权限3.内存容量的“扩充”内存容量的扩充是逻辑上的扩充有三种技术可以扩充内存覆盖技术：要求用户提供覆盖结构交换技术：通过中级调度缓解内存压力虚拟存储器技术：内存、外存结合引入：请求调入功能置换功能4.地址映射符号空间（符号地址）进程空间（逻辑地址）存储空间（物理地址）相关概念符号空间程序员定义的标识符程序符号的集合没有地址的概念符号指令数据说明I/O说明•由编译、链接得到的可执行模块•逻辑(相对)地址的集合•访问信息的地址集合进程空间•由装配程序生成的物理单元的集合•物理(绝对)地址的集合•读取信息的地址集合存储空间地址映射将用户程序中的逻辑地址转换为运行时可由机器指令直接寻址的物理地址，也称重定位用A表示进程空间，用M表示存储空间则地址映射可表示成：f：A→W地址映射有两种方式：静态地址映射动态地址映射地址映射LoadA120034561200物理空间LoadAdata1data13456源程序LoadA20034560100200编译/链接逻辑空间BA=1000符号空间、进程空间、存储空间1100三种装入方式绝对装入编译时给出绝对地址相对地址与绝对地址相同，无须地址转换适用于单道程序环境静态重定位装入相对地址与绝对地址不同装入时一次性给出绝对地址动态重定位装入相对地址与绝对地址不同地址的转换推迟到指令运行时才进行程序装入时一次性实现地址映射由重定位装入程序(软件)完成转换一次性装入整个程序且必须占用连续空间静态地址映射静态地址映射示意程序运行时再进行地址转换由硬件地址变换机构完成映射可连续存放，也可离散存放实现方式重定位寄存器：存放基地址表映象方式：采用页表描述虚页、实页之间的关系动态地址映射动态地址映射示意4.2连续分配方式4.2.1单一连续分配1.工作原理在单道环境下，任何一段时间内只有一个进程在内存内存可以划分为：系统区、用户区用户区是一个连续的存储区，又称单一连续区存储管理单一连续区存储分配示意0用户程序位于RAM中的操作系统0xFFF...0位于RAM中的操作系统用户程序0ROM中的设备驱动程序用户程序位于RAM中的操作系统0xFFF...0xFFF...2.工作流程采用静态分配和静态重定位方式由装入程序检查其绝对地址是否越界即可达到保护系统的目的3.存在的问题不支持多道程序内存利用率不高受内存容量限制4.2.2连续分区存储管理将内存划分成若干个连续区域，称为分区每个分区只能存储一个程序，而且程序也只能在它所驻留的分区中运行(连续性)是实现多道程序的最简单的存储管理方案根据划定的分区是否可变，分为固定分区和可变分区管理1.固定分区基本思想由OS在初启时，将内存空间划分为若干连续区域，一个区域称为一个分区每个分区的大小固定不变，每个分区装一个且只能装一个进程每个分区大小可以相同也可以不同数据结构分区说明表：分区号、起始地址、大小、状态分区请求表：进程号、内存大小分区号始址(K)大小(K)状态123420329215012605850可用已用已用可用大小(K)进程号5204510882367分区说明表分区请求表分区分配改变状态：未用→已用返回分区号分区回收改变状态：已用→未用地址映射采用静态重定位,不存在拼接/紧凑问题存在的问题造成大量的内部碎片2.可变分区基本思想系统初启时，用户区是一个连续的空间随着进程对内存的请求和释放，动态形成内存已用分区和可用分区交错的局面分区分配：按需划分分区回收：合并回收与固定分区的区别分区的创建时机•可变：进程装入时动态创建•固定：初启时由OS创建分区的大小和数目•可变：动态变化•固定：始终不变数据结构分区分配表•空闲分区表：包括分区号、始址、大小•占用分区表：包括始址、大小、进程号空闲分区链：包括分区大小、分区状态及指向前、后分区的指针分区请求表：包括进程号、请求分区大小0K15K38K48K68K80K110K120K分区号始址大小515K23K848K20K1680K30K始址大小标志0K15KJ138K10KJ268K12KJ3110K10KJ4空空分区分配表占用分区表空闲分区表空闲分区链分区分配为避免形成外部碎片，预定义限定值size•剩余空间≥size：按需划分；•否则：分配整个分区碎片的解决办法：拼接或紧凑拼接时机•回收分区时：开销大；•分配分区时：次数少；分区分配操作从头开始查表检索完否？m.sizeu.size?m.size-u.size≤size?从该分区中划出u.size大小的分区分配给请求者修改相应数据结构返回分区号及始址返回∑m.size≥u.size？实施拼接，形成大分区修改相应的数据结构分配失败分配m.size大小分区YNNYYNYN分区回收操作F1回收区F2回收区F1+回收区•F1表项•始址—F1•大小—F1+回收区回收区+F2•F2表项•始址—回收区•大小—回收区+F2分区回收操作F1回收区F2回收区F1+回收区+F2•F1表项•始址—F1•大小—F1+回收区+F2•删除F2表项回收区•新表项•始址—回收区•大小—回收区4.2.3分区分配算法有五种分配算法首次适应法循环首次适应法最佳适应法最坏适应法快速适应算法要求空闲分区按地址递增次序排列从头顺序搜索空闲分区表(链)，直至找到第一个大小合适的分区为止进行分区分配固定分区：将整个分区分配给请求进程可变分区：根据需要划分适当分区特点地址低端利用充分，保留地址高端大空间对固定分区容易形成内碎片对可变分区容易形成外碎片首次适应法(FirstFit)要求空闲分区按地址递增次序排列从上次搜索位置继续搜索空闲分区表(链)，直至找到大小合适的分区为止分配方式同首次适应法特点空闲分区利用均匀缺乏大的空闲分区循环首次适应法(NextFit)要求空闲分区按大小递增次序排列从头搜索空闲分区表(链)，直至找到第一个大小合适的最小分区为止特点找到的分区是最接近进程要求的对固定分区而言，内碎片小对可变分区而言，易形成外碎片最佳适应法(BestFit)要求空闲分区按大小递减次序排列从头搜索空闲分区表(链)，直至找到第一个大小满足要求的最大分区为止特点找到的分区远大于进程的要求对固定分区而言，内碎片大对可变分区而言，剩余分区可再次利用最坏适应法(WorstFit)将空闲分区按大小分类，为大小相同的分区建立空闲分区链表；建立一张管理索引表，指向不同类型空闲分区链表的表头指针；查找能满足进程需求的最小空闲区链表，取下第一块空闲区整体分配；能保留大的空闲区；分区回收时较复杂。快速适应法(QuickFit)例：设作业A(40K)、B(160K)、C(100K)依次请求内存分配，内存采用可变分区管理；现有F1(220K)、F2(120K)两个空闲区，如图所示：分区分配举例0K已用F1(220K)已用F2(120K)已用1000K画出分别采用首次适应、最佳适应和最差适应算法的内存分配情况示意图1.引入固定分区限制了活动进程的数目，内存碎片严重；可变分区算法复杂，系统开销大；伙伴系统是对两种方法的折衷。伙伴：1）大小相同；2）位置相邻。4.2.4伙伴系统2.基本原理分区大小为2k(l≤k≤m)，2l表示最小分区大小，2m表示最大分区大小(初始为整个可分配内存的大小)；当进程请求大小为n的空间时，计算i值，使得：2i-1n≤2i；在大小为2i的空闲分区链中查找：若找到，把空闲分区分配给该进程；否则，在大小为2i+1的空闲分区链中查找。若存在大小为2i+1的空闲分区，则将其等分为两个分区，称为一对伙伴：一个用于分配，另一个加入大小为2i的空闲分区链中；若大小为2i+1的空闲分区也不存在，则继续查找大小为2i+2的空闲分区；若找到，则进行两次分割：1)将其分割为大小为2i+1的两个分区，一个进行二次分割，一个加入空闲分区链；2)将二次分割的分区等分为大小为2i的两个分区，一个用于分配，一个加入空闲分区链。若找不到大小为2i+2的空闲分区，则继续查找大小为2i+3的空闲分区，依此类推；在最坏情况下，可能需要对2k的空闲分区进行k次分割才能得到所需分区。一次分区回收也要经过多次合并：回收大小为2i的分区时，若事先存在2i的空闲分区，则将其与伙伴合并为2i+1的空闲分区；若事先存在2i+1的空闲分区，继续与其伙伴合并为2i+2的空闲分区，依此类推。在伙伴系统中，令buddyk(x)表示大小为2k、地址为x的块的伙伴地址，则buddyk(x)的同要通用表达式为：x+2k-[(x/2k)%2]*2k+1例题：在一个伙伴系统中，若内存大小为1024K，则起始地址为640K、大小为128K的内存块的伙伴地址是多少？若起始地址为512K、大小为256K的内存块的伙伴地址是多少？按大小将空闲区链成空闲区链，通过管理索引表查找合适的空闲区链；如果对空闲分区分类较细，则查找开销增大。哈希算法的思想：构造哈希函数，建立分区大小与空闲区表表头指针之间的对应关系，形成哈希表；分区分配时，根据所需分区的大小，通过哈希函数的计算，得对应空闲区表的头指针，实现最佳分配。4.2.5哈希算法4.2.6覆盖与对换技术分区分配方式下，逻辑扩充内存的方法覆盖技术主要用在早期的操作系统中交换技术被广泛用于小型分时系统中，交换技术的发展导致了虚存技术的出现覆盖技术把程序划分为若干个相对独立的程序段让不会同时执行的程序段共享同一分区——称作一个覆盖共享区域的大小等于相互覆盖的程序段中最长段的大小由程序员提供覆盖结构，由系统完成自动覆盖对用户不透明，增加了用户负担覆盖技术示意图A(15K)B(10K)C(20K)D(35K)E(12K)A(15K)B(10K)C/D(35K)E(12K)覆盖内存空间(72KB)程序结构(92KB)YN对换技术1.对换的引入是进程在内存和外存之间的动态调度：内存紧张时，把不具备执行条件的进程从内存暂时移到外存；把外存中具备执行条件的进程换进内存，占据调出进程所占用的区域对换以整个进程为单位——对换技术；对换