第3章存储系统及存储管理5存储器管理概述

3.5存储管理存储管理的功能地址重定位分区存储管理页式存储管理虚拟存储管理存储器管理存储器的层次高速缓冲存储器（cache）内存（主存）外存（辅存）主存分为：系统区用户区存储器管理要管理的区域存储器管理的功能思考：要运行你编写的JAVA语言程序，首先要把你的程序装入内存。如何为程序分配一片存储空间？内存的分配和回收地址变换内存共享与保护虚拟存储器地址重定位逻辑地址：用户程序中以“0”开始的地址。物理地址：内存中的地址。地址重地位：把逻辑地址转换成物理地址的过程。地址重地位的方式：根据定位的时机不同，分为静态地址重定位和动态地址重定位。静态地址重定位在作业装入内存时，进行的地址重定位。程序中的地址都是物理地址。优点：简单，无需增加硬件地址转换机构。缺点：一旦装入，就不能在内存中移动位置。用户无法共享。动态地址重定位在程序执行时进行的地址重地位。硬件支持：重定位寄存器（基址寄存器）。程序中的地址是逻辑地址。物理地址=基址寄存器+逻辑地址例：基址寄存器的值为1000，LOADA，500则操作数的地址为：1500。loada,50023670500逻辑地址空间1000定位寄存器2367物理地址空间+动态地址重定位优点：程序占用的内存空间动态可变。容易实现内存共享。缺点：需要硬件支持，增加成本。管理软件比较复杂。现代计算机中普遍采用动态重定位的定位方式。主要的内存管理技术单道连续存储管理分区存储管理固定分区存储管理可变分区存储管理页式存储管理虚拟存储管理单道连续存储管理1、基本原理：内存分为两部分：用户区和系统区。任何时刻，内存中最多只有一个用户作业。2、内存分配算法：用户请求是否小于用户区？分配Y不能运行单道连续存储管理3、存储保护：保护系统程序不会遭用户程序的破坏。措施：设置一个界限寄存器，存放当前可供用户使用的主存区域的起始地址。4、多用户共享（分时系统）

对换（swapping）技术：让多个用户的作业轮流进入主存储器。

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

问题：如何知道哪些分区已分配；各个分区的大小和位置？（1）分区说明表：记录系统中所有分区的情况，结构如下：固定分区存储管理区号起始地址长度占用标志

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

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

注意：这里的状态是指该表目的状态，其值表示该表目是空闲还是已使用。（2）空闲分区链空闲区大小；下一空闲区起始地址……分配算法（1）1、最先适配算法：空闲分区表按地址从小到大排列，从第一个开始，找到第一个满足条件的分区，根据作业的大小切出一片连续的区域。作业请求LP=1是否越界？Y不能分配状态为空闲？NP=P+1长度≥LNY长度=L状态置为“空表目”YN起始地址=起始地址+L长度=长度-L分配算法（2）2、最优适配算法原理：将空闲区按大小从小到大排列，将满足需求的最小的空闲区分配给作业。基于：为了更好地满足大作业的需求。但是：这样切下的空闲区容易变成“碎片”。算法流程与最先适配法相同。分配算法（3）3、最坏适配算法从满足需求的最大的空闲区中为作业分配空间。空闲分区表按大小从大到小排列。基于：切完后的空闲区仍能满足某个作业的需求，减少碎片的数量。但对大作业不利。其流程为：用户作业请求Ｌ取分区表的第一个表项长度≥ＬＹ起始地址＝起始地址＋Ｌ长度＝长度－Ｌ长度＝ＬＮＹ状态置空表目不能分配N回收算法１、待回收区：其起始地址为Ａ，长度为Ｌ。２、上空闲区和下空闲区３、可能的四种情况：（１）上下都不空。（２）上空，下不空。（３）下空，上不空。（４）上下都为空。待回收区作业区作业区上下都不空待回收区作业区上空下不空在空闲分区表中找一个空表目，将其内容填入。上空闲区：大小＝大小＋Ｌ待回收区作业区待回收区下空上不空下空闲区：起始地址=A大小=大小+L上下都为空上空闲区：长度=长度+L+下空闲区起址不变。注意如何判断待回收区是否与空闲区相连？地址+长度=下一空闲区首地址空闲区的管理：为了便于空闲区的合并，采用链接结构。按地址从小到大排序。第一块和最后一块的情况。可变分区存在的问题及解决办法碎片问题：一些很小的内存区域。移动技术将离散的碎片集合在一起。不是任何时候都可以移动。移动技术需要很大的系统开销。保护问题界地址法：基址和长度寄存器。上机题目1、编写可变分区存储管理算法（最先适配法）2、编写可变分区的内存回收算法。分区存储管理的缺点“碎片”问题原因：作业要求连续的存储空间。解决办法：允许作业占据不连续的空间。页式存储管理基本原理内存分配地址变换内存保护和内存共享虚拟存储器基本原理“等分”内存。把内存划分为大小相同的“块”。把用户作业空间划分为大小相同的“页”。页和块的大小相同。在把作业加载到内存时，页和页之间不再连续。但页内连续。也不必把所有的页都一次性加载内存，只需要加载那些马上要用到的页。其余的页在需要时再加载。地址变换逻辑地址：页号+页内地址如何转变为内存物理地址？考虑：物理地址=块号*块长度+块内地址块长度一定，块内地地址与页内地址相同。问题变为：如何根据页号得到块号？页表：页号页内地址页表地址变换过程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）=（0000001101011110）2从左边数10位为页内地址，剩余为页号。页号为0。（3）根据页号查页表，得到块号为5。（4）将块号与块内地址组合为物理地址：01011101011110=175E（H） 页表的实现—快表从上述地址变换过程可以看出：CPU每取一条指令或数据，都必须经过页表。因此，页表的每一个表项都是一个动态重定位机构。如何实现页表，将影响系统的效率。方式：硬件实现：用寄存器组。但代价太高，特别是内存很大时，是不可能的。软件实现：将页表放在内存中。每取一条指令，要两次访问内存。快表软硬件结合：将页表中使用最频繁的表项（页表的的一个子集）放在cache中。称为“快表”。cache也称为“联想寄存器”，它不是根据地址而是根据所存信息的全部特征或部分特征进行存取。在这里为页号。若要访问的页在cache中，则只需一次访问内存。若不在，则到内存中去找，同时把新的页表表项写入cache。例题：对于利用快表且页表存于内存的分页系统，假定CPU的一次访问内存时间为1µs，访问快表时间忽略不计。如果85%的地址映射可直接通过快表完成，那么进程完成一次内存读写的平均有效时间是多少？分析：（1）若直接通过快表完成，则只需一次访问内存。（2）若不能，则需要两次访问内存。（3）平均时间=1*85%+2*15%内存分配用户需求：需要多少块？内存空闲块的管理：位示图。位示图：在内存中划出一片区域，用一位代表一个块，该位的值表示所代表的块的状态：0：空闲；1：已分配。内存分配块号与字号、字长的关系：系统的字长一定，内存块从0开始编号，则有：块号=字号*字长+位号字号=[块号/字长]（取整的意思）位号=块号MOD字长用户作业请求：块数B扫描位示图，查找为0的位空闲块数BN无法分配计算块号建立页表例题（1）一个32位计算机系统有主存128M和辅助存储器10G，这个系统的虚拟空间是多少？（2）页式虚拟存储管理采用位示图技术，设主存有16384块，采用32位的512个字作为位示图。若块号、字号和位号（从高位到低位）分别从1、0、0开始。试计算：5998块对应的字号和位号；198字的20位对应于哪一块？页式系统的内存保护和共享保护：在页表上添加一个保护位。在做地址变换时，检查对页面的访问是否合法。共享：根据地址转换过程可知：如果在不同用户的页表中填上相同的页表表项（块号），就能够访问相同的内存空间。块号保护位5R12WR555用户1用户2用户355虚拟存储技术基本原理实现过程页面替换页式虚拟存储技术虚拟存储器：内存扩充技术，为用户提供一个比实际内存大得多的内存空间。虚拟存储的理论依据:局部性原理。页式虚拟的基本原理：加载作业时，只加载那些最活跃的页，其余的页需要时再加载。“请求调页技术”和“预调页技术”。实现虚拟的三个三个条件程序中的哪些页已经加载内存。当要访问的页不在内存时，如何将其调入内存？若此时内存空间已满，如何选择换出的页？一、如何知道哪些已在内存在页表中添加一个标志位（中断位），标志该页是否已在内存：0：不在1：在内存块号保护位标志位二、当要访问的页不在内存时发生“缺页中断”。缺页中断的处理过程：保存现场在内存中找到一个空闲块。从磁盘上找到要调入的页。读磁盘到内存。恢复现场。重新调度运行。三、在调入内存时，若内存已满进行“页面替换”：从内存中选择一个页调出内存，为新调入的页让出空间。问题：选择哪一个页换出？如果替换的不合适，则发生“抖动”或“颠簸”现象：页在内外存之间频繁地调入调出，系统开销很大。换出换入页面替换算法先进先出法（FIFO）：将最先调入内存的页调出内存。最近最少使用算法（LRU：leastrecentlyused）。将最近一段时间内没有用过的页调出内存。页面替换算法最近最少使用算法（LFU）：最近一段时间内使用次数最少的页调出内存。为每一个在内存的页设置一个计数器，选择计数器中的值最小的调出。最优算法（OPT）：把将来一段时间内被使用的可能性最小的页调出内存。利用预测方法先来预测将来的使用情况。注意：LRU、LFU之间的区别。例题：有一个分页式虚拟存储管理系统，每个进程在内存有3页数据区、1页程序区，刚开始时数据区为空。现有一个进程有以下访问序列：1，5，4，1，2，3，2，1，5，4，2，4，3，5，1若系统采用：（1）最近最少使用（LRU）淘汰算法（2）先进先出（FIFO）淘汰算法请计算缺页次数和发生缺页中断后的淘汰页号。分析：（1）采用FIFO方法：将内存中的页按进入的先后次序排队，后来的加入队尾，先来的先出去。（1）FIFO算法访问队列：154123215424351

154423315422351内存155422315442351154423155423缺页中断页面替换154231543答案：缺页中断的次数为12次，页面替换的次序是：154231543。（2）LRU算法：访问队列：154123215424351

154423335422351内存155122215442351141112155443缺页中断页面替换54321524答案：缺页中断的次数为11次，页面替换的次序是：5432152441.某系统采用页式存储管理，运行一个共有九页的作业，依次访问的页面的次序为123782141231526393526，若前五页已装入主存且维持五个页在主存工作，试问分别用FIFO和LRU调度算法时，完成该作业会产生的缺页中断次数和淘汰页面的次序?答案：（1）FIFO：中断次数为7次，淘汰页面的次序为1237851（2）LRU：中断次数为5次，淘汰页面的次序为37841综合应用题

FIFO算法12378214

1231526393526缺页替换888888412335566999997777777841223355666663333333784112233555552222222378441122333331111111237884511222221237851

√√√√√√√LRU算法123782141231526393526缺页替换8888884443355669999977777771112211223333333333332221133556666622222228884422112222211111117778844335555537841

√√√√√工作集模型虚拟存储技术的理论基础。局部性原理：进程往往会不均匀地高度局部化地访问内存。

时间局部性：刚刚被访问的页，很可能在不久的将来还要访问。例如：循环；子程序；栈；用户记数和总计的变量等。

空间局部性：某个页面被访问，很可能它相临的页也要被访问。例如：数组遍历；代码程序的执行；等等。工作集：进程活跃地访问的页面的集合。工作集模型（续）工作集存储管理策略力求把活跃程序的工作集保存在内存中。从上图可以看出：仅当一个进程的全部工作集都在内存时才能运行该作业。hW(h)h0页式存储管理的缺陷从理论上讲，不同用户共享程序段或数据很简单，只需在不同用户的页表中填上相同的块号，经地址变换后，一定能访问相同的内存空间。但是，由于页的划分是由系统自动进行的，很可能用户要共享的页分布在不同的页中，给共享和保护造成了麻烦。多级页表原理：程序执行的局部性。没有必要把整个页表都存放在内存中。页内地址页号II页号IWindows2000采用的二级页表见教材P109图4-244.8UNIX系统的虚拟存储管理UNIX的虚拟地址三个区段：系统区段、程序区段、控制区段系统区段：常驻内存控制区段：用户栈、核心栈、user区P110图4-25UNIX虚拟地址结构UNIX的页表结