chapter45存储器管理

计算机操作系统第四章存储器管理河北经贸大学信息技术学院河北经贸大学信息技术学院22021/7/29第四章存储器管理教学要求：1、掌握：连续分配的五种方式及其区别，基本分页/分段存储管理方式，请求分页/分段存储管理方式。OPT、FIFO、LRU、NRU页面置换算法。2、理解：程序的装入和链接的三种方式及其区别，对换的概念，不同存储管理方式下的信息共享方法，段页式存储管理方式，局部性原理，虚拟存储器的基本概念，实现方法和特征，LFU、PBA页面置换算法。3、了解：抖动问题。河北经贸大学信息技术学院32021/7/29第四章存储器管理4.1存储器的层次结构4.2程序的装入和链接4.3连续分配方式4.4基本分页存储管理方式4.5基本分段存储管理方式4.6虚拟存储器的基本概念4.7请求分页存储管理方式4.8页面置换算法4.9请求分段存储管理方式河北经贸大学信息技术学院42021/7/294.1存储器的层次结构理想存储器：速度快；容量大；价格便宜但是，理想破灭！4.1.1多级存储器结构寄存器高速缓存主存磁盘缓存磁盘可移动存储介质CPU寄存器主存辅存河北经贸大学信息技术学院52021/7/294.2程序的装入和链接库链接程序装入模块装入程序编译程序产生的目标模块第一步第二步第三步内存…图4-2对用户程序的处理步骤河北经贸大学信息技术学院62021/7/294.2.1程序的装入1.绝对装入方式(AbsoluteLoadingMode)编译程序产生含绝对地址的目标代码，装入时按装入模块中的地址将程序和数据装入内存。逻辑地址==物理地址条件:编译时须知道程序将驻留在内存的什么位置。缺点：程序员要熟悉内存使用情况；不适合多道程序环境。72021/7/292.可重定位装入方式(RelocationLoadingMode)LOAD1,2500365LOAD1,2500365100001100012500150005000250010000作业地址空间内存空间图4-3作业装入内存时的情况河北经贸大学信息技术学院82021/7/294.2.1程序的装入3.动态运行时装入方式(DynamicRun-timeLoading)动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址都仍是相对地址。运行时再进行地址转换。需要重定位寄存器的支持。河北经贸大学信息技术学院92021/7/294.2.2程序的链接1.静态链接方式(StaticLinking)模块ACALLB；Return；0L－1模块BCALLC；Return；0M－1模块CReturn；0N－10模块AJSR“L”Return；L－1模块BJSR“L＋M”Return；LL＋M－1L＋ML＋M＋N－1模块CReturn；(a)目标模块(b)装入模块(1)对相对地址进行修改。(2)变换外部调用符号。河北经贸大学信息技术学院102021/7/294.2.2程序的链接2.装入时动态链接(Load-timeDynamicLinking)在装入一个目标模块时，若发生一个外部模块调用事件，将引起装入程序去找出相应的外部目标模块，并将它装入内存。装入时动态链接方式有以下优点：(1)便于修改和更新。(2)便于实现对目标模块的共享。河北经贸大学信息技术学院112021/7/294.2.2程序的链接3.运行时动态链接(Run-timeDynamicLinking)在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。优点：不仅可加快程序的装入过程，而且可节省大量的内存空间河北经贸大学信息技术学院122021/7/294.3连续分配方式4.3.1单一连续分配最简单，只能用于单用户、单任务OS内存分为系统区和用户区河北经贸大学信息技术学院132021/7/294.3.2固定分区分配最简单的一种可运行多道程序的存储管理方式。将内存用户空间划分为若干个固定大小的区域，在每个分区中只装入一道作业。1.划分分区的方法(1)分区大小相等(2)分区大小不等(多个小分区、适量中等分区、少量大分区)河北经贸大学信息技术学院142021/7/292.内存分配将分区按大小进行排队，并建立一张分区使用表。操作系统作业A作业B作业C24KB32KB64KB128KB256KB分区号大小/KB起址/KB状态11220已分配23232已分配36464已分配4128128未分配(b)存储空间分配情况(a)分区说明表图4-5固定分区使用表河北经贸大学信息技术学院152021/7/294.3.3动态分区分配分配方法=数据结构+分区分配算法+分配与回收操作1.分区分配中的数据结构(1)空闲分区表(2)空闲分区链图4-6空闲链结构前向指针0N个字节可用后向指针0N+2N+2河北经贸大学信息技术学院162021/7/292.分区分配算法1)首次适应算法(firstfit)空闲分区链以地址递增次序链接。倾向于优先利用内存中低址部分的空闲分区，保留了高址部分的大空闲区。低址不断被划分，内存碎片多，搜索又是从低址开始，增加搜索开销。2)循环首次适应算法(nextfit)从上次找到的空闲分区的下一个空闲分区开始查找。空闲分区分布均匀，减少查找开销。缺乏大的空闲分区。河北经贸大学信息技术学院172021/7/293)最佳适应算法(bestfit)最佳：分配满足要求的最小空闲分区。空闲分区按容量从小到大排序。分配后剩余部分最小，内存碎片多。4)最坏适应算法(worstfit)最坏：挑最大空闲分区分割给作业使用。优点：产生碎片几率最小；对中、小作业有利；查找效率高(空闲分区按从大到小排序)。缺点：导致缺乏大的空闲分区。5)快速适应算法(quickfit)(分类搜索法)将空闲分区按容量大小分类，分属多个空闲分区链表。优点：查找效率高；不分割，无碎片；保留大分区。缺点：回收算法复杂(质疑)，存在空间浪费。河北经贸大学信息技术学院182021/7/293.分区分配操作1)分配内存从头开始查表检索完否？m.size＞u.size?m.size-u.size≤size?从该分区中划出u.size大小的分区将该分区分配给请求者修改有关数据结构返回返回继续检索下一个表项将该分区从链中移出YNNYYN图4-7内存分配流程河北经贸大学信息技术学院192021/7/293.分区分配操作2)回收内存图4-8内存回收时的情况河北经贸大学信息技术学院202021/7/294.3.4伙伴系统伙伴系统规定，无论已分配分区或空闲分区，其大小均为2的k次幂，k为整数，l≤k≤m，其中：2l表示分配的最小分区的大小，2m表示分配的最大分区的大小，通常2m是整个可分配内存的大小。不同大小的空闲分区形成了k个空闲分区链表当需要为进程分配一个长度为n的存储空间时，首先计算一个i值，使2i－1n≤2i，然后在空闲分区大小为2i的空闲分区链表中查找。若找到，即把该空闲分区分配给进程。否则，表明长度为2i的空闲分区已经耗尽，则在分区大小为2i＋1的空闲分区链表中寻找。若存在2i＋1的一个空闲分区，则把该空闲分区分为相等的两个分区，这两个分区称为一对伙伴，其中的一个分区用于分配，而把另一个加入分区大小为2i的空闲分区链表中。河北经贸大学信息技术学院212021/7/294.3.6可重定位分区分配1.动态重定位的引入操作系统用户程序1用户程序310KB30KB用户程序614KB用户程序926KB操作系统用户程序1用户程序3用户程序6用户程序980KB(a)紧凑前(b)紧凑后河北经贸大学信息技术学院222021/7/292.动态重定位的实现图4-10动态重定位示意图LOAD1,25003650100250050002500相对地址10000重定位寄存器＋LOAD1,250036510000101001250015000作业J处理机一侧存储器一侧主存河北经贸大学信息技术学院232021/7/293.动态重定位分区分配算法图4-11动态分区分配算法流程图请求分配u.size分区检索空闲分区链(表)找到大于u.size的可用区否?按动态分区方式进行分配修改有关的数据结构返回分区号及首批空闲分区总和≥u.size?进行紧凑形成连续空闲区修改有关的数据结构否是无法分配返回否址242021/7/294.3.7对换1.对换(Swapping)的引入所谓“对换”，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据，调入内存。对换是提高内存利用率的有效措施。整体对换：进程对换部分对换：页面对换或分段对换实现进程对换：对换空间的管理、进程的换出和换入河北经贸大学信息技术学院252021/7/294.3.7对换2.对换空间的管理在具有对换功能的OS中，通常把外存分为文件区和对换区。对换区采用连续分配方式。对对换区中的空闲盘块的管理：数据结构、对换空间的分配与回收与动态分区方式相同。河北经贸大学信息技术学院河北经贸大学信息技术学院262021/7/294.3.7对换3.进程的换出与换入(1)进程的换出选择处于阻塞状态且优先级最低的进程作为换出进程；启动磁盘，将该进程的程序和数据传送到磁盘的对换区上；回收该进程内存空间，修改进程控制块。河北经贸大学信息技术学院272021/7/294.3.7对换3.进程的换出与换入(2)进程的换入定时地查看所有进程的状态，从中找出“就绪”状态但已换出的进程，将其中换出时间(换出到磁盘上)最久的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止。河北经贸大学信息技术学院282021/7/294.4基本分页存储管理方式4.4.1页面与页表1.页面1)页面和物理块将一个进程的逻辑地址空间分成若干个大小相等的片——页面或页(从0开始编号)。将内存空间分成与页面相同大小的若干个存储块——(物理)块或页框(frame)。页内碎片河北经贸大学信息技术学院292021/7/294.4.1页面与页表2)页面大小页面太小内存碎片减小，减少内存碎片总空间，提高内存利用率；每个进程占用页面多，从而页表过长，占用大量内存；降低页面换进换出效率。页面较大减少页表长度，提高页面换进换出速度；但页内碎片增大。页面大小应适中，通常是2的幂。河北经贸大学信息技术学院302021/7/292.地址结构分页地址中的地址结构如下：页号P位移量W3112110对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得：MODLAdLAINTP][(页号从0开始)河北经贸大学信息技术学院312021/7/293.页表图4-12页表的作用用户程序0页1页2页3页4页5页…n页页表页号块号02132638495……内存012345678910河北经贸大学信息技术学院322021/7/294.3.2地址变换机构1.基本的地址变换机构图4-13分页系统的地址变换机构页表寄存器页表始址页表长度＞页号(3)页内地址＋逻辑地址L越界中断1块号b页表页号012物理地址3(PTR,置于PCB)(内存)(内存)=?河北经贸大学信息技术学院332021/7/292.图4-14具有快表的地址变换机构页表寄存器页表始址页表长度＞页号页内地址＋逻辑地址L越界中断块号b页表页号页号输入寄存器块号bb快表d物理地址河北经贸大学信息技术学院342021/7/294.4.3两级和多级页表假设一个32位的OS，逻辑地址空间为4GB，页面大小为4KB，页表项占4个字节，则页表占用内存空间大小能达到多少？页表占用内存空间太大，且为连续分配方式解决方法：采用离散分配方式来解决难以找到一块连续的大内存空间的问题