第4章 存储.ppt

《第4章 存储.ppt》由会员分享，可在线阅读，更多相关《第4章 存储.ppt（75页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第4章章 存储管理存储管理存储器管理n存储器的层次n高速缓冲存储器（cache）n内存（主存）n外存（辅存）n主存分为：系统区用户区存储器管理要管理的区域存储器管理的功能思考思考：要运行你编写的C语言程序，首先要把你的程序装入内存。如何为程序分配一片存储空间？n内存的分配和回收n地址变换n内存共享与保护n虚拟存储器地址重定位n逻辑地址：用户程序中以“0”开始的地址。n物理地址：内存中的地址。n地址重地位：把逻辑地址转换成物理地址的过程。n地址重地位的方式：根据定位的时机不同，分为静态静态地址重定位和动态动态地址重定位。静态地址重定位n在作业装入内存时，进行的地址重定位。n程序中的地址都是物理

2、地址。n优点：简单，无需增加硬件地址转换机构。n缺点：n一旦装入，就不能在内存中移动位置。n用户无法共享。动态地址重定位n在程序执行时进行的地址重地位。n硬件支持：重定位寄存器（基址寄存器）。n程序中的地址是逻辑地址。n物理地址=基址寄存器+逻辑地址n例：基址寄存器的值为1000，LOAD A，500 则操作数的地址为：1500。load a,50023670500逻辑地址空间1000定位寄存器2367物理地址空间+动态地址重定位n优点优点：n程序占用的内存空间动态可变。n容易实现内存共享。n缺点缺点：n需要硬件支持，增加成本。n管理软件比较复杂。n现代计算机中普遍采用动态重定位动态重定位的定

3、位方式。主要的内存管理技术n单道连续存储管理n分区存储管理n固定分区存储管理n可变分区存储管理n页式存储管理n虚拟存储管理4.3 单道连续存储管理1、基本原理：内存分为两部分：用户区和系统区。任何时刻，内存中最多只有一个用户作业。2、内存分配算法：用户请求是否小于用户区？分配Y不能运行4.3 单道连续存储管理3、存储保护：保护系统程序不会遭用户程序的破坏。措施：设置一个界限寄存器，存放当前可供用户使用的主存区域的起始地址。4、多用户共享（分时系统）对换（swapping）技术：让多个用户的作业轮流进入主存储器。硬件支持：大容量高速辅助存储器。5、地址重地位方式：静态地址重地位。4.3 覆盖技术

4、如果作业逻辑地址空间用户区，怎么处理？n原理：n作业分段n主段始终保留在内存（驻留区）n其它段保存在辅存中，轮流进入主存n谁来分段？n用户把如何分段和覆盖情况写成一个“覆盖描述文件”分区存储管理1、基本原理基本原理：将内存划分为若干个连续的存储区域（称为一个分区），每一个分区中可以（也只能）装入一个作业。2、分区的种类：根据分区的时机不同，分为：固定分区和可变分区两种。.固定分区存储管理1、基本原理：在作业加载内存之前之前，将内存划分为若干个连续的区域。一旦划分好后，主存储器中的分区个数和大小就确定了，不能改变。各个分区的大小可以不同（长作业区和短作业区）。2、内存分配与回收 问题：如何知道哪

5、些分区已分配；各个分区的大小和位置？（1）分区说明表：记录系统中所有分区的情况，结构如下：固定分区存储管理 区号 起始地址 长度 占用标志 其中，“占用标志”表示该分区是已分配还是空闲。（2）分配算法：从分区说明表中查找一个状态是“空闲”、大小满足作业要求的分区，并将状态改为“已分配”。（3）回收算法：只需要将分区说明表中的“状态”值改为“空闲”即可。用户作业LP=0是否越界？N长度L？分配（状态改为“已分配”）YP=P+1状态为“空？”YNN无法分配Y固定分区存储管理3、地址转换地址转换：静态重定位的方式。4、存储保护存储保护：上下界地址法。处理器设置一对寄存器：上界寄存器和下界寄存器，作业

6、地址应满足：下限地址绝对地址上限地址 否则，发生“地址越界”中断事件。5、存在问题：内存利用率很低。措施：提高内存利用率的措施（1）按统计规律划分分区。（2）按分区大小顺序排列，低地址部分是较小的分区，在分区说明表中按从小到大顺序登记。为作业分配满足条件的最小的分区。（3）按作业对主存储器的需求量排成多个队列，每个作业队列中的作业只能依次装入一个分区中。可变分区存储管理基本原理基本原理在作业要求装入主存时，根据作业的大小从空闲内存区中“切出”一片连续的区域分区的大小和个数是不确定的 初始时，系统中只有一个连续的用户区域，随着作业的到达和撤消，用户区就被划分为若干个大小不等的区域。内存OS作业A

7、作业B作业C内存分配与回收内存分配与回收1、空闲区的管理（1）空闲分区表空闲分区表 序号 起始地址 大小 状态 注意：这里的状态是指该表目的状态，其值表示该表目是空闲还是已使用。（2）空闲分区链空闲分区链空闲区大小；下一空闲区起始地址 分配算法（1）1、最先适配算法：空闲分区表按地址地址从小小到大大排列，从第一个开始，找到第一个满足条件的分区，根据作业的大小切出一片连续的区域。作业请求LP=1是否越界？Y不能分配状态为空闲？NP=P+1长度LNY长度=L状态置为“空表目”YN起始地址=起始地址+L长度=长度-L分配算法（分配算法（2）2、最优适配算法最优适配算法 原理：将空闲区按大小大小从小到

8、大排列，将满足需求的最小的空闲区分配给作业。基于：为了更好地满足大作业的需求。但是：这样切下的空闲区容易变成“碎碎片片”。算法流程与最先适配法相同。分配算法（3）3、最坏适配算法 从满足需求的最大的空闲区中为作业分配空间。空闲分区表按大小大小从大到小排列。基于：切完后的空闲区仍能满足某个作业的需求，减少碎片的数量。但对大作业不利。其流程为：用户作业请求取分区表的第一个表项长度起始地址起始地址长度长度长度状态置空表目不能分配N回收算法回收算法、待回收区：其起始地址为，长度为。、上空闲区和下空闲区、可能的四种情况：（）上下都不空。（）上空，下不空。（）下空，上不空。（）上下都为空。待回收区作业区作

9、业区上下都不空上下都不空待回收区作业区上空下不空上空下不空在空闲分区表中找一个空表目，将其内容填入。上空闲区：大小大小待回收区作业区待回收区下空上不空下空上不空下空闲区：起始地址=A大小=大小+L上下都为空上下都为空上空闲区：长度=长度+L+下空闲区起址不变。注注 意意n如何判断待回收区是否与空闲区相连？地址+长度=下一空闲区首地址n空闲区的管理：为了便于空闲区的合并，采用链接结构。n按地址从小到大排序。n第一块和最后一块的情况。可变分区存在的问题及解决办法n碎片问题：一些很小的内存区域。n移动技术n将离散的碎片集合在一起。n不是任何时候都可以移动。n移动技术需要很大的系统开销。n 保护问题n

10、界地址法：基址和长度寄存器。上上 机机 题目题目1、编写可变分区存储管理算法（最先适配法）2、编写可变分区的内存回收算法。分区存储管理的缺点n“碎片”问题n原因：作业要求连续的存储空间。n解决办法：允许作业占据不连续的空间。页式存储管理基本原理内存分配地址变换内存保护和内存共享虚拟存储器基本原理n“等分”内存。n把内存划分为大小相同的“块”。n把用户作业空间划分为大小相同的“页”。n页和块的大小相同。n在把作业加载到内存时，页和页之间不再连续。n但页内连续。n也不必把所有的页都一次性加载内存，只需要加载那些马上要用到的页。其余的页在需要时再加载。地址变换n逻辑地址：页号+页内地址n如何转变为内

11、存物理地址？n考虑：物理地址=块号*块长度+块内地址块长度一定，块内地地址与页内地址相同。n问题变为：如何根据页号得到块号？n页表页表：页号页内地址页表地址变换过程1、根据页号查页表，得到块号。2、根据块号和页内地址计算物理地址。3、例题：例题例题：在分页存储管理系统中，用户编程空间共32个页，每页大小为1024B，内存为16KB。假定某一时刻用户页表如下，若逻辑地址为035E（H），求其所对应的物理地址。页号 物理块号 0 5 1 10 2 3 3 7分析分析：（1）根据题意，页内地址为10位，页号为5位。210=1024，25=32 （2）根据给定的逻辑地址得到页号和页内地址。035E（H

12、）=（0000001101011110）2 从左边数10位为页内地址，剩余为页号。页号为0。（3）根据页号查页表，得到块号为5。（4）将块号与块内地址组合为物理地址：01011101011110=175E（H）页表的实现快表n从上述地址变换过程可以看出：CPU每取一条指令或数据，都必须经过页表。n因此，页表的每一个表项都是一个动态重定位机构。n如何实现页表，将影响系统的效率。n方式：n硬件实现：用寄存器组。但代价太高，特别是内存很大时，是不可能的。n软件实现：将页表放在内存中。每取一条指令，要两次访问内存。快 表n软硬件结合：将页表中使用最频繁的表项（页表的的一个子集）放在cache中。称为“

13、快表”。ncache也称为“联想寄存器”，它不是根据地址而是根据所存信息的全部特征或部分特征进行存取。在这里为页号。n若要访问的页在cache中，则只需一次访问内存。若不在，则到内存中去找，同时把新的页表表项写入cache。例题：对于利用快表且页表存于内存的分页系统，假定CPU的一次访问内存时间为1s，访问快表时间忽略不计。如果85%的地址映射可直接通过快表完成，那么进程完成一次内存读写的平均有效时间是多少？分析：（1）若直接通过快表完成，则只需一次访问内存。（2）若不能，则需要两次访问内存。（3）平均时间=1*85%+2*15%内 存 分 配n用户需求：需要多少块？n内存空闲块的管理：位示图

14、。位示图：在内存中划出一片区域，用一位代表一个块，该位的值表示所代表的块的状态：0：空闲；1：已分配。内存分配n块号与字号、字长的关系：系统的字长一定，内存块从0开始编号，则有：块号=字号*字长+位号 字号=块号/字长（取整的意思）位号=块号 MOD 字长 用户作业请求：块数B扫描位示图，查找为0的位空闲块数BN无法分配计算块号建立页表例 题（1）一个32位计算机系统有主存128M和辅助存储器10G，这个系统的虚拟空间是多少？（2）页式虚拟存储管理采用位示图技术，设主存有16384块，采用32位的512个字作为位示图。若块号、字号和位号（从高位到低位）分别从1、0、0开始。试计算：5998块对

15、应的字号和位号；198字的20位对应于哪一块？页式系统的内存保护和共享n保护保护：在页表上添加一个保护位。在做地址变换时，检查对页面的访问是否合法。n共享共享：根据地址转换过程可知：如果在不同用户的页表中填上相同的页表表项（块号），就能够访问相同的内存空间。块号保护位5 R12 WR555用户1 用户2 用户355虚拟存储技术基本原理实现过程页面替换页式虚拟存储技术n虚拟存储器：内存扩充技术，为用户提供一个比实际内存大得多的内存空间。n虚拟存储的理论依据:局部性原理。n页式虚拟的基本原理：加载作业时，只加载那些最活跃的页，其余的页需要时再加载。“请求调页技术”和“预调页技术”。实现虚拟的三个三

16、个条件n程序中的哪些页已经加载内存。n当要访问的页不在内存时，如何将其调入内存？n若此时内存空间已满，如何选择换出的页？一、如何知道哪些已在内存在页表中添加一个标志位（中断位），标志该页是否已在内存：0：不在 1：在内存 块号 保护位 标志位二、当要访问的页不在内存时n发生“缺页中断”。n缺页中断的处理过程：n保存现场n在内存中找到一个空闲块。n从磁盘上找到要调入的页。n读磁盘到内存。n恢复现场。n重新调度运行。三、在调入内存时，若内存已满n进行“页面替换”：从内存中选择一个页调出内存，为新调入的页让出空间。n问题问题：选择哪一个页换出？n如果替换的不合适，则发生“抖动”或“颠簸”现象：页在内

17、外存之间频繁地调入调出，系统开销很大。换出换入页面替换算法n先进先出法（FIFO）：将最先调入内存的页调出内存。n最近最少使用算法（LRU：least recently used）。将最近一段时间内没有用过的页调出内存。页面替换算法n最近最少使用算法（LFU）：最近一段时间内使用次数最少的页调出内存。为每一个在内存的页设置一个计数器，选择计数器中的值最小的调出。n最优算法（OPT）：把将来一段时间内被使用的可能性最小的页调出内存。利用预测方法先来预测将来的使用情况。n注意注意：LRU、LFU之间的区别。例例 题：题：有一个分页式虚拟存储管理系统，每个进程在内存有3页数据区、1页程序区，刚开始时

18、数据区为空。现有一个进程有以下访问序列：1，5，4，1，2，3，2，1，5，4，2，4，3，5，1若系统采用：（1）最近最少使用（LRU）淘汰算法（2）先进先出（FIFO）淘汰算法请计算缺页次数和发生缺页中断后的淘汰页号。分析：（1）采用FIFO方法：将内存中的页按进入的先后次序排队，后来的加入队尾，先来的先出去。（1）FIFO算法访问队列：1 5 4 1 2 3 2 1 5 4 2 4 3 5 1 1 5 4 4 2 3 3 1 5 4 2 2 3 5 1内 存 1 5 5 4 2 2 3 1 5 4 4 2 3 5 1 1 5 4 4 2 3 1 5 5 4 2 3缺页中断 页面替换 1

19、5 4 2 3 1 5 4 3答案：缺页中断的次数为12次，页面替换的次序是：1 5 4 2 3 1 5 4 3。（2）LRU算法：访问队列：1 5 4 1 2 3 2 1 5 4 2 4 3 5 1 1 5 4 4 2 3 3 3 5 4 2 2 3 5 1内 存 1 5 5 1 2 2 2 1 5 4 4 2 3 5 1 1 4 1 1 1 2 1 5 5 4 4 3缺页中断 页面替换 5 4 3 2 1 5 2 4答案：缺页中断的次数为11次，页面替换的次序是：5 4 3 2 1 5 2 441.某系统采用页式存储管理，运行一个共有九页的作业，依次访问的页面的次序为12378214123

20、1526393526，若前五页已装入主存且维持五个页在主存工作，试问分别用FIFO和LRU调度算法时，完成该作业会产生的缺页中断次数和淘汰页面的次序?答案：（1）FIFO：中断次数为 7 次，淘汰页面的次序为1237851（2）LRU：中断次数为 5 次，淘汰页面的次序为37841综合应用题综合应用题 FIFO算法 1 2 3 7 8 2 1 4 1 2 3 1 5 2 6 3 9 3 5 2 6缺页替换88 8 8 8 8 8 4 1 2 3 3 5 5 6 6 9 9 9 9 9 7 7 7 7 7 7 7 8 4 1 2 2 3 3 5 5 6 6 6 6 63 3 3 3 3 3 3

21、7 8 4 1 1 2 2 3 3 5 5 5 5 52 2 2 2 2 2 2 3 7 8 4 4 1 1 2 2 3 3 3 3 31 1 1 1 1 1 1 2 3 7 8 8 4 5 1 1 2 2 2 2 2 1 2 3 7 8 5 1 LRU算法 1 2 3 7 8 2 1 4 1 2 3 1 5 2 6 3 9 3 5 2 6缺页替换88 8 8 8 8 8 4 4 4 3 3 5 5 6 6 9 9 9 9 9 7 7 7 7 7 7 7 1 1 1 2 2 1 1 2 2 3 3 3 3 33 3 3 3 3 3 3 2 2 2 1 1 3 3 5 5 6 6 6 6 62

22、2 2 2 2 2 2 8 8 8 4 4 2 2 1 1 2 2 2 2 21 1 1 1 1 1 1 7 7 7 8 8 4 4 3 3 5 5 5 5 5 3 7 8 4 1 工作集模型虚拟存储技术的理论基础。局部性原理：进程往往会不均匀地高度局部化地访问内存。时间局部性时间局部性：刚刚被访问的页，很可能在不久的将来还要访问。例如：循环；子程序；栈；用户记数和总计的变量等。空间局部性空间局部性：某个页面被访问，很可能它相临的页也要被访问。例如：数组遍历；代码程序的执行；等等。工作集：进程活跃地访问的页面的集合。工作集模型（续）n工作集存储管理策略力求把活跃程序的工作集保存在内存中。从上图

23、可以看出：仅当一个进程的全部工作集都在内存时才能运行该作业。hW(h)h0页式存储管理的缺陷 从理论上讲，不同用户共享程序段或数据很简单，只需在不同用户的页表中填上相同的块号，经地址变换后，一定能访问相同的内存空间。但是，由于页的划分是由系统自动进行的，很可能用户要共享的页分布在不同的页中，给共享和保护造成了麻烦。多级页表n原理：程序执行的局部性。n没有必要把整个页表都存放在内存中。页内地址页号II页号IWindows2000采用的二级页表见教材P109图4-244.8 UNIX系统的虚拟存储管理nUNIX的虚拟地址n三个区段：系统区段、程序区段、控制区段n系统区段：常驻内存n控制区段：用户栈

24、、核心栈、user区nP110 图4-25 UNIX虚拟地址结构nUNIX的页表结构nP111 图 4-26 n每个区段都有自己的页表n硬件支持：一对页表寄存器，页表起始地址和长度UNIX的页面调度n当有效位V为0时，发生缺页中断nUNIX采取的优化措施n正与外围设备交换信息或正在被装入的页不能替换n采用二次机会页面替换算法n修改标志n页面守护进程（2号进程）本章小结内存管理功能n内存的分配和回收n地址变换n内存共享与保护n虚拟存储器n任何一种管理策略，都需要解决上述问题。n解决上述问题的方法，就是存储管理的内容。本章小结内存管理技术n单道连续存储管理n分区存储管理n固定分区存储管理n可变分区

25、存储管理n页式存储管理n虚拟页式存储管理课课 后后 练练 习习1、在一个分页式虚拟存储管理系统中，每个进程在内存中有3个数据区，2个程序区。现有一进程，其数据的第1、2，3页已装入内存。现有一个访问序列：1、3、4、1、2、5、4、3、2、1、4、3、5、1，已知系统采用最近最少使用（LRU）淘汰算法。请给出缺页次数和发生缺页中断后的淘汰页号。在一个页式虚拟存储管理系统中，用户空间有32个页，每页为1KB，主存为16KB。试问：（1）逻辑地址的有效位是多少？（2）物理地址的有效位是多少？（3）假定某时刻为用户的第0、1、2、3页分别分配的物理块号为5、10、4、7，试将虚拟地址2500转变为物

26、理地址。练习在页式存储管理中，页的大小为1024B，页表如下所示：块号标志位508131110请问：1.逻辑地址为041A（H）的物理地址是多少？2.当访问逻辑地址为0521（H）的数据时，是否会发生缺页中断？综合应用题综合应用题答案及分析答案及分析1.页表中标志位的含义：标志该页是否已在内存n标志位为“0”，不在内存n标志位为“1”，已在内存2.逻辑地址转变为物理地址的过程n计算逻辑地址中的页号和页内地址n根据页号查页表，得到内存块号n物理地址=块号块长+页内地址3.焦点问题：如何计算页号和页内地址？答案及分析答案及分析因为页的大小为1024B，210=1024，所以页号占10位。041A（H）=（0000010000011010）2，低位10位为页号，高位为页号，页号为1根据页表得知：块号为8物理地址为：（0010000000011010）2=201A（H）同理：0521（H）=0000010100100001页号为1，块号为8，该页标志位为1，说明该页已在内存，不会发生缺页中断