第五章 存储器管理.ppt

第五章存储器管理,掌握动态分区存储管理，分页式存储管理、段式存贮管理的实现、分配与回收算法；掌握固定式存贮管理的实现及分配与回收算法；段式和页式管理的实现及地址变换算法。,本章重点：,请求段式和请求页式的地址变换；段页式存贮管理的实现。,本章难点：,存贮器管理的功能单一连续区存储器管理固定式分区存贮管理动态分区存储管理页式存贮管理请求页式存贮管理段式存贮管理段页式存贮管理,51存贮器管理的功能,1.内存的分配及回收：根据不同的管理机制有不同的分配回收算法。但是，无论何种机制，一个有效的机制必须做到用户申请时立即响应，预以分配；用户用完立即回收，以供其它用户使用，为此存贮区分配应有如下机制。,记住每个区域的状态（已分。未分）,实施分配（修改数据结构）,接受系统或用户释放的区域（修改数据结构）,2.内存信息的保护（存贮）(必须有硬件支持)：,违例,防止越界,防止非法访问,3.内存信息共享：使多道程序能动态地共享内存，最好能共享内存的信息,4.地址变换（重定位）（需要硬件支持）,1）逻辑地址(相对地址)：用户编程时总是从0开始编址，这种用户编程所用的地址称逻辑地址,2）物理地址（内存地址、绝对地址）：内存是由若干存贮单元组成的，每个存贮单元有一个编号称为物理地址。,3）地址空间,逻辑地址空间：用户编程空间，是由CPU的地址总线扫描出来的。,物理地址空间：由物理存贮单元组成的空间由存贮器的地址总线扫描出来的空间。,4）重定位（地址变换）：把逻辑地址转换为相应物理地址叫重定位,5）重定位（地址变换）方式：,静态定位方式：地址变换是在程序装入时进行。,动态定位方式：地址变换是在指令执行时进行的。,优点：不需要硬件支持,缺点：程序装入之后不能移动。,必须占用连续空间。,动态定位方式：地址变换是在指令执行时进行的。,优点：可以对内存进行非连续分配。,可以实现虚存,可以实现共享,缺点：需要硬件支持,必须事先确定存储量。,5.内存扩充（软扩充、虚拟存贮）,利用外存来扩充内存叫内存存存贮。,基本原理：逻辑地址空间先放到外存上，内存只装入一部分，其它的部分需要时再装入。,1）覆盖技术：在程序内实现。,B和C是互斥的，可以互相覆盖即B和C不互相调用，且B的运行与C不发生任何关系，反之亦然。,那么B和C可以互相覆盖，但覆盖区必须满足二者中较大的区域。,不采用覆盖技术需要用内存：,10K+20K+15K,采用覆盖技术用内存：,10K+20K=30K,缺点：对用户不完全透明,2）交换技术：,允许一个进程的地址空间全部放在外存上，需要时再把它放入内存。,覆盖是在同一进程的地址空间进行,交换则是在整个系统的范围内进行的。,3）虚拟存贮器（VS）又叫虚拟技术,虚存：系统提供给用户的编程空间。,虚存思想的核心：在动态地址重定位的计算机系统中，把作业的地址空间和实际内存空间分离开来。,实现：先把程序的地址空间放在外存，只装入一部分其它的内容需要时再装入。,利用了局部性原理：,时间局部,空间局部,优点：对用户完全透明，内存扩充量比交换大。,缺点：实现起来比较复杂。,52单一连续区存储器管理,一、实现：,整个用户只放一道程序，给作业分配的是整个用户区，,碎片：一块无用的存贮区；,分为两种：,内碎片：作业（或进程）自己浪费的碎片；,外碎片：系统分不出去的碎片。,二、分配与回收：非常简单，整体分配、整体回收。,三、信息保护：只要做越界保护，防止用户访问OS区。,53固定式分区存贮管理,一、实现：,把内存分成几个固定大小的区域，每个作业占一个分区存贮区。,分区的划分是在系统初启时规定的，在系统运行期间不发生变化（包括大小和边界）。,分区数据结构：,二、分配与回收,将作业分成分个队列：,如：15K一队,30K一队,30一队,要求size大小分区,取分区说明表第一项,表结束吗？,无法分配,是,否,该分区空闲吗？,取下一表项,否,是,分区大小=size吗？,否,是,修改状态位,返回分区号,三、信息保护,越界保护,实现：需要硬件支持，使用一对界限寄存器来实现。,四、地址变换：采用静态地址重定位。,五、共享：没有共享,六、内存扩充：可以采用覆盖和交换两种技术。,优点：简单、系统开销小，可以实现多道、采用静态重定位，硬件开销小。,缺点：,有内碎片,可以实现多道，但同时进入内存的道数受分区限制,不能共享,不能实现虚存,54动态分区存贮管理,一、实现：,系统初启时，只有一个OS区和一个用户区，分区的大小由申请的作业决定,二、分配与回收,分区数据结构：,分配算法：,最先适应法（首次适应法，空闲区按起始地址从小到大排序）,最佳适应法（空闲区按分区大小从小到大排序）；,最坏适应法（选所有满足条件的分区中最大的）；,下次适应法,开销：时间开销：最坏适应法时的开销最小。,空间开销：,最佳适应法：按地址由低到高排序。（折中）,最坏适应法：按空间大小由小到大排序。,（破坏大区、碎片少）,最佳适应法：按空间大小由小到大。,破坏小区，碎片多,均衡,再次适应法：,最佳适应法产生的碎片多。,首次适应分配算法,要求size大小分区,取空闲区表第一项,表结束吗？,无法分配,是,否,分区大小=size吗？,取下一表项,否,是,分区大小=size吗,否,是,从空闲区表中删除该表项,返回分区号,从空闲区表中截取所需大小修改调整空闲区表,回收考虑合并问题,三、信息保护：（同固定式分区）,四、信息共享：无,五、移动（浮动）地址空间在内存中移动,优点：合并碎片,缺点：时间开销大，以时间换取空间。,六、地址变换：采用动态地址重定位。,七、内存扩充：覆盖、交换，不能实现虚存。,八、特点：内存利用率高，支持的道数多，分配与回收复杂，不能共享，产生外碎片。,动态分区练习,下表给出了某系统中的空闲分区表，系统采用动态分区存储管理策略。现有以下作业序列：96K、20K、200K。若用首次适应法和最佳适应法来处理这些作业序列，哪一种算法可以满足该作业序列的请求，为什么？,某操作系统采用可变式分区存储管理方法，用户区为512k且起始地址为0，用空闲区表管理空闲区。若分配时采用分配空闲区低地址部分的方案，且初始时用户区的512k空间空闲，对下述申请序列：JOB1申请300k，JOB2申请100k，JOB1释放300kJOB3申请150k，JOB4申请30k，JOB5申请40kJOB6申请60k，JOB4释放30k回答下列问题：（1）采用首次适应算法，空闲区表（2）采用最佳适应法的空闲区表（3）若再申请100k，对（1）和（2）各有什么结果？,55页式存贮管理,一、实现：,作业的地址空间分成若干大小相等的页，,二、分配与回收,内存分成与页大小相等的块（页面）,页的大小是2的整数次方，,一般为1K，2K，4K，8K等,数据基：位示图，每个二进制位（bit）表示1块0未分,1已分,通过计数count来标识空块数量,位示图要占一定的空间：如果内存有1024个页面，每个内存单元长20bit，位示图将占1024/20个内存单元,问：1GB的内存，每块1024B，每个内存单元长32位，位示图占多大空间？,（数据基：每个作业有一张表，叫页表，格式：）,系统提供一个寄存器叫页表控制寄存器。,11,20,23,内存中有n个空闲页面吗？,请求n个页面,设置页表，将页表始址、页表长度等置入请求表中,搜索页面空间，分配n个页面，将页号、页面号等填入页表,返回,是,无法分配,否,分配算法,回收算法：,拆除页表,位示图相关各位置1,2500H的物理地址？,内存,虚地址,页表控制寄存器,+,物理地址,内存,逻辑地址：1500H,三、地址变换：,对给定的虚地址，系统自动分离页号和页内地址,4500H的物理地址？,页号4位，页内地址12位,则逻辑地址为1，500,页号2位，页内地址14位结果如何？,虚地址是10进制，每页大小为1024，结果如何？,R,地址变换步骤：,给定逻辑地址LA，页面大小size，页表，求物理地址PA,（1）页号p=int（LA/size）,（2）页内偏移量offset=LAmodsize,（3）查页表获取页面号f（若有转4，否则地址越界）,（4）PA=f*size+offset,三、信息保护：在分析指令时由硬件自动完成,分页技术执行指令时访存两次，所以时间开销比较大。为解决速度问题，需要处理机提供硬件支持,一种高速缓存,用来存放页表的工具,联想存贮器,一个作业中有一部分页表放在高速缓存中，一部分放在内存中,高速缓存中的叫快表，内存中的叫慢表,慢表快表,页式地址变换练习,某一页式存储管理系统，页表如下，已知页面大小为1024B，试将逻辑地址1011，2148，3000，4000，5012转化为相应的物理地址,56请求页式存贮管理,一、实现：,开始时只装入部分页，其它的页需要时再装入，当内存没有空块时，选择某些内存页淘汰。,二、要解决的问题:(把不在内存的页叫缺页)。,1)如何发现缺页？；,2)如何在外存中找到缺页；,3)内存没有空块怎么办；,4)如何选择要淘汰的页；,5)如何知道一页是否被引用；,6)如何知道一页是否被修改；,页号页面号权限,状态位,外存地址,引用位,修改位,（淘汰）,（淘汰算法）,三、流程：,四、淘汰算法：,1最佳淘汰算法：,选择从此后不再使用或最长时间内不再使用的页（不能实现，做为标准）,70120304230321201,内存有3块,7,7,0,7,0,1,2,0,1,2,0,3,2,0,4,2,0,3,2,0,1,缺页8次,2先进先出（FIFO）：,选择最先进入内存的页进行淘汰（适用于顺序结构的程序，无循环，无条件转移）,70120304230321201,7,7,0,7,0,1,2,0,1,2,3,1,2,3,0,4,3,0,4,2,0,4,2,3,0,2,3,0,1,3,0,1,2,缺页12次,R,3最近最久未使用法LRU（LeastRecentlyUsed）：,选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。,70120304230321201,7,7,0,7,0,1,2,0,1,2,0,3,4,0,3,4,0,2,4,3,2,0,3,2,1,3,2,1,0,2,缺页11次,思想：如果某页被访问了，则马上可能还要访问，如果某页很长时间没被访问，则马上访问的可能性较大。,实现较难，因此用该算法的近似算法,最近没有使用页面淘汰算法NUR，选择最近一段时间内未被访问的页淘汰。,最近没有使用页面淘汰算法NUR，选择最近一段时间内未被访问的页淘汰。,通过访问位确定是否被访问，系统周期性对引用位清0,最近最不经常使用法LFU（LeastFrequentlyUsed）：,70120304230321201,7,7,0,7,0,1,2,0,1,2,0,3,4,0,3,4,0,2,3,0,2,1,0,2,缺页9次,选择到当前为止访问次数最少的那一页。,五、请求页式的性能问题,抖动：页的频繁调入调出。,减少缺页率的办法：,1）确立最小工作集；,2）选择好的淘汰算法,3）设计好的程序,局部性能好避免用GOTO,缺页次数,内存块数,例：两个数组求和。,按行计算还是按列计算。,根据：数组存放是按行存放还是按列存放。,Belady现象,如果分配给作业或进程的页面数多，则缺页次数反而多,缺页次数,内存块数,正常情况,Belady现象,内存块数,缺页次数,Belady现象的例,FIFO算法分配给进程3个页面时，,缺页9次,123412512345,1,1,2,1,2,3,4,2,3,4,1,3,4,1,2,5,1,2,5,3,2,5,3,4,分配给进程4个页面时，,123412512345,1,1,2,1,2,3,1,2,3,4,5,2,3,4,5,1,3,4,5,4,1,2,4,5,1,2,3,4,1,2,3,4,2,3,5,缺页10次,六、页式特点：,优点：,实现共享、虚存技术，,内存分配与回收简单,缺点：,速度受影响，硬件开销大,有内碎片,可能抖动,软件开销大,碎片减少,页面置换练习,已知对某进程的页的请求序列为：1、2、1、3、1、2、4、2、1、3、4，且开始执行时主存中没有页，若只给该作业分配2个物理块，当采用FIFO页面淘汰算法时缺页率为多少？假定现在有一种淘汰算法，该算法淘汰页面的策略是当需要淘汰页面时，就把刚使用过的页面淘汰出去，试问对相同的请求序列，缺页次数为多少？缺页中断和一般中断的区别是什么？有一请求分页存储管理系统，页面大小为100字节。有一个5050的整形数组按行连续存放，每个整数占2B，将数组初始化为0的程序描述如下：,页面置换作业,缺页中断和一般中断的区别是什么？有一请求分页存储管理系统，页面大小为100字节。有一个5050的整形数组按行连续存放，每个整数占2B，将数组初始化为0的程序描述如下：Inta5050;IntI,j;For(i=0;i=49;i+)for(j=0;j=49;j+)aij=0;若程序执行时只用一个内存块存放数组，会产生多少次缺页中断？若数组是按列存放的，结果又如何？,3.有一页式存储管理系统，向用户提供的逻辑地址空间为16页，每页为2048B，内存共有8个页面，试问逻辑地址至少应该为多少位？内存空间多大？4.请求页式存储管理系统中，一个作业的页的请求序列为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的页面数分别为3、4时，试