第六章存储管理.ppt

《第六章存储管理.ppt》由会员分享，可在线阅读，更多相关《第六章存储管理.ppt（76页珍藏版）》请在三一文库上搜索。

1、第六章 存储管理,重要资源 “瓶颈”：关键、紧张 帕金森定律： 内存多大，程序多长,存储器的层次结构,快 贵 慢,存储器的层次结构,高速缓存（Cache）： 少量的、非常快速、昂贵、易变的。 内存（RAM）： 若干兆字节、中等速度、中等价格、易变的。 磁盘： 数百兆或数千兆字节、低速、廉价、不易变的。,存储器的层次结构,由操作系统协调这些存储器的使用。 重要性：直接存储要求内存速度尽量快到与CPU取值速度相匹配，大到能装下当前运行的程序与数据，否则CPU执行速度就会受到内存速度和容量的影响而得不到充分发挥。,存储器的层次结构,内存：是由存储单元（字节或字）组成的一维连续的地址空间，简称内存空间

2、。用来存放当前正在运行程序的代码及数据，是程序中指令本身地址所指的，亦即程序计数器所指的存储器。 内存可以分为： 系统区：用于存放操作系统。 用户区：用于装入并存放用户程序和数据。,存储管理的目的,1、充分利用内存，为多道程序并发执行提供存储基础。 2、尽可能方便用户使用。 自动装入用户程序 用户程序中不必考虑硬件细节 3、系统能够解决程序空间比实际内存空间大的问题。,存储管理的目的,4、程序在执行时可以动态伸缩； 5、内存存取速度快； 6、存储保护与安全； 7、共享与通信； 8、了解有关资源的使用情况； 9、实现性价比。,6.1 存储管理的功能,1、存储分配 记录内存的使用情况 设置相应的内

3、存分配表（内存分配回收的依据） 内存空间的划分问题？ 静态或动态，等长或不等长,6.1 存储管理的功能,内存分配表 位示图表示法：用一位（bit）表示一个空闲页面（0：空闲，1：占用）,1 0 1 0,第0页,第i页,第1页,第n-1页,6.1 存储管理的功能,空闲页面表：包括首页面号和页面个数，连接若干个页面作为一组登记在表中 空闲块表：空闲块首地址和空闲块长度，没有记录的区域即为进程所占用 空闲块链表：将所有的空闲块连成一个链表。,6.1 存储管理的功能,确定分配算法 实施内存分配 回收内存 分配回收方式：静态分配与动态分配,6.1 存储管理的功能,2、存储共享 内存共享：两个或多个进程共

4、用内存中相同的区域 目的：节省内存空间，提高内存效率。 实现进程通信（数据共享） 共享内容：代码共享（要求代码为纯代码） 数据共享,6.1 存储管理的功能,3、存储保护 目的：为多个程序共享内存提供保障，使在内存中的各道程序，只能访问它自己的区域，避各道程序间相互干扰，特别是当一道程序发生错误时，不至于影响其它程序的运行。通常由硬件完成保护功能，由软件辅助实现。 含义： 保护系统程序不被用户侵犯 不允许用户程序读写不属于自己地址空间的数据,6.1 存储管理的功能,保护过程：每个进程都有自己独立的进程空间，如果一个进程在运行时所产生的地址在其地址空间之外，则发生地址越界。即当进程要访问某个内存单

5、元时，由硬件检查是否允许，如果允许则执行，否则产生地址越界中断，由操作系统进行相应处理。 一般由硬件提供一对寄存器 基址寄存器：存放起始地址 限长寄存器：存放长度（上下界寄存器）,6.1 存储管理的功能,4、存储扩充 通过虚拟存储技术实现 用户在编制程序时，不应该受内存容量限制，所以要采用一定的技术来“扩充”内存容量，使用户得到比实际内存容量大得多的内存空间。 具体实现：在硬件的支持下，软硬件相互协作，将内存和外存结合起来统一使用。通过这种方法把内存扩充，使用户在编制程序时不受内存限制。,6.1 存储管理的功能,5、地址映射（地址重定位、地址变换） 逻辑地址（相对地址、虚地址） 物理地址（绝对

6、地址、实地址） 地址映射,源 程 序,目标文件 （逻辑地 址空间）,运行时 （物理地 址空间）,编译、链接,库函数,地址映射,6.1 存储管理的功能,由于用户的逻辑地址空间都是从0开始的，而当该程序装入内存运行时又不是从0开始，因此就需要将逻辑地址转换成实际的内存地址。,6.3 存储管理方式,单一连续的 存储管理,固定分区的 存储管理,可变分区的 存储管理,程序浮动、多重分区,页式存储管理,交换、覆盖,请求页式管理 （虚拟存储管理）,段式存储管理,段页式存储管理,6.3.1 单一连续的存储管理,所谓单一，是指内存中只驻留一道作业。为便于地址转换，把作业连续的存放在内存中，而不是离散的存放。 单

7、一连续的存储管理思想主要用在早期的单道批处理系统中，采用静态分配的方式，即作业或进程一进入内存，就要等到它运行结束后才能释放内存。,优缺点,优点：方法简单，易于实现。 缺点： 1)内存利用率低：一个作业独占主存储空间，降低存储空间的利用率； 2)处理器利用率低：处理器和外部设备串行工作； 3)外设的利用率低：系统中的资源为一个用户控制。,分区式存储管理,分区管理的基本思想就是给每一个内存中的进程划分一段存储区，用以连续存放各进程的程序和数据，使各进程并发执行。 这是能满足多道程序设计需要的最简单的存储管理技术 固定式分区 动态式分区,预先把可分配的内存空间分割成若干个连续区域，每一区域称为分区

8、。 每个分区的大小可以相同，也可以不同。分区大小固定不变，每个分区装一个且只能装一个作业。 两个固定： 1、各分区的大小固定不变； 2、总分区的个数固定不变。,1、固定式分区,存储分配情况,缺点,1、预先规定了分区大小，大程序无法装入，必须采用覆盖技术； 2、主存的利用率不高：每个分区的作业不可能恰好占满该区，剩余的部分空间又不能为其它作业利用。碎片问题 3、内存的扩充和共享是困难的。,在作业装入和处理过程中建立分区，并且要使分区的容量能正好适应作业的大小。在作业进入系统前，根据作业的大小来申请所需存储容量，然后由系统分配。 可变式分区，通常采用动态重定位的方法来实现地址转换。存储保护仍用界地

9、址存储器，不具备虚拟存储器的功能。 两个可变： 1、各分区的大小可变； 2、总分区的个数可变。,2、可变式分区,OS,OS,OS,OS,进程A,进程A,进程A,进程A,进程B,进程B,进程C,进程B,进程C,进程D,进程A 8K,进程B 16K,进程C 64K,进程D 124K,存储分配情况,在系统初始状态，除了操作系统常驻内存部分之外，只有一个空闲分区，随后，分配程序将该区划分给调度选中的作业。,分区式存储管理,系统为了管理主存分区分配情况，需要建立两个张表，他们是一张分区表和一张可用空间表。 分区表 可用空间表,1)最佳适应算法,优点： 1）平均而言，只要查找一半的表格便能找到最佳适应的空

10、闲区； 2）如果有一个空闲区的容量正好满足要求，则它必被选中； 3）如果不存在恰好满足需要的空闲区，则选择一个容量接近的空闲区，而较大的空闲区被保留下来。以后如果要求分配一个较大的空闲区时，就容易得到满足。 缺点： 空闲区一般不可能恰好满足要求，在分配之后的剩余部分通常非常小，以致小到无法使用。换言之，发展下去最后剩下许多非常小的空闲区（即形成碎片）。,2)最差适应算法,优点： 1）只要比较第一项就能判定能否满足要求，如满足要求便立即进行分配； 2）分配后剩下的空闲区可能比较大，可供以后使用。 缺点： 分配进行一段时间以后就不能满足对于较大空闲区的分配要求。,3)最先适应算法,优点： 空闲区按

11、从小到大排列时, 最先适用分配算法能尽可能使用低地址区,从而高地址空间有较大的空闲区容纳大的作业。 缺点： 在低地址部分很快集中了许多非常小的空闲区，因而在空闲区分配时，搜索次数增加，影响工作效率。,适应算法的比较,搜索空闲区速度及主存利用率：最先适应分配、最佳适应算法比最坏适应算法性能好。 如果空闲区按从小到大排列,则最先适用分配算法等于最佳适应分配算法。 如果空闲区按从大到小排列,则最先适用分配算法等于最坏适应分配算法。 最先适应算法简单、快速，在实际的操作系统中用得较多；其次是最佳适应算法。,程序浮动,作业,多重分区,作业,存储扩充-覆盖技术,覆盖技术：作业之间或作业内部的若干程序段共享

12、主存的技术。 缺点：编程时必须划分程序模块和确定程序模块之间的覆盖关系，增加编程难度。,存储扩充-覆盖技术,程序大小=28K,主程序（2K）,A(3K),D(4K),C(1K),B(4K),E(3K),G(4K),F(4K),H(3K),2k,4k,4k,3k,占用内存空间=13K,存储扩充-交换技术,分时系统中，同时执行几个作业（进程）。但是，这些同时存在于内存中的作业（进程），有的处于执行状态或就绪状态，而有的则处于等待状态。 如果让这些等待状态中的进程继续驻留内存，必定会造成存储空间的浪费，因此应该把处于等待状态的进程换出内存，交换就是基于这种目标的一种内存扩充技术。,存储扩充-交换技术

13、,就绪队列,磁盘,内存,换入,调度,换出,覆盖与交换比较,1)交换不要求程序员给出程序之间的覆盖结构；覆盖需要。 2)交换主要是在进程或作业之间进行；而覆盖则主要在同一个作业或进程内进行。 3)覆盖只能覆盖那些与覆盖程序段无关的程序段。,6.3.2 页式存储管理,为什么要引进分页技术? 分区式存储管理：程序要求连续存放，会产生碎片问题。大程序进入时需要移动已在主存中的信息。 分页式存储管理允许把一个作业存放到若干不相邻接的分区中 免去移动信息 充分利用主存空间,分页式存储管理就是要实现从逻辑地址空间到物理地址空间的一种变换，即： f：LS 其中，L、S分别表示逻辑地址空间和实际地址空间。 页架

14、：把物理内存空间划分为若干个等份，每一份叫做一个页架。 页面：把用户程序按页架划分成大小相等的部分，称为页面。从0开始编制页号，页内地址相对于0编址。,基本原理,地址结构,用户程序的划分是由系统自动完成的，对用户是透明的。一般一页的大小为2的整数次幂。因此，地址的高位部分为页面号，低位部分为页内地址。,地址结构,如给定一个地址空间的地址为W，页面大小为L，则页面号P和页内地址D可按下式求得： P=INT W / L D=W MOD L 其中，INT是整除函数，MOD是取余函数。 例如： 系统的页面大小为1KB，设W=2230，则可求得P=2，D=182,地址转换机构,地址转换机构,页地址映像表

15、（页表）： 记录了一个作业的各个页面对应的页架。 寄存器硬件成本过高，所以采用主存中开辟存储区存放页表，另设一个页表主存起址和长度控制寄存器，存放当前作业的页表起止和页表长。,地址转换具体过程（页表）,页表长度,页表基址,控制寄存器,p,d,p,d,页号,页表,页号,偏移量,内存,b,bp,b,页架号,p,相联存储器,为了提高查页表的速度，在地址变换机构中加入了一组高速寄存器（8个或者16个），这些寄存器连同管理他们的硬件构成了一个容量较小的寄存器，称之为高速相联存储器，也称快表。,地址转换具体过程（快表）,页表长度,页表基址,控制寄存器,p,d,p,d,页号,页表,页号,偏移量,内存,b,b

16、p,b,页架号,p,快表,p,确定页面尺寸,设内存为M，作业平均尺寸为J，一个页表项占一个单位，问最佳页面尺寸P=?,虚拟页式存储管理是将作业信息的副本存放在磁盘中，当作业被调度投入运行时，不把作业的程序和数据全部装入主存，而仅装入立即使用的页面，在执行过程中访问到不在主存的页面时，产生缺页中断，再把它们动态地装入 。,虚拟页式存储管理,虚拟页式存储管理,虚拟存储管理应解决以下问题： 1、把哪一部分装入内存 2、何时把页面装入 3、装入内存什么位置 4、当内存设备有空间时，淘汰哪个页面,遵循的原则,拿来策略： 拿来策略就是缺哪页装哪页 页面调入时机 主要有两个策略：预调页策略和请求调页策略 放

17、置策略,虚拟页式存储管理的页面表,每个虚页号不仅对应一个页架号，还增设一个该页是否在主存的中断位和该页在外存中的副本起始地址。,如果内存没有空闲页面，就应该用某种淘汰策略选中内存中的一个页面。 如果被淘汰的页已经被修改了，应该把修改后的页重新写回外存，要是没有被修改，因为外存有副本，就不用重新写回外存。 因此，需要在页表中加入一项记录该页是否改变的内容，即增加一项纪录该页是否改变的位。,页面置换策略,加入改变位的页表,页面置换策略：当内存中没有可以利用的页架时，根据一定的策略从内存中选择一个页面，把它置换到外存，称为页面置换策略。 常用置换策略： 先进先出淘汰算法（FIFO） 最近最少使用的先

18、淘汰（LRU） 最近不用的先淘汰（NUR） 最佳淘汰算法（OPT）,页面置换策略,基本思想：总是淘汰最先调入主存的那一页，或者说在主存中驻留时间最长的那一页（常驻的除外）。 理由：最早调入内存的页面，其不再被访问的可能性最大。比如顺序程序，执行过的指令可能就不再需要了。 特点：实现简单、适合线性访问、对其他情况效率不高。 异常情况：在某些情况下会出现分配给进程的页面数增多，缺页次数反而增加的奇怪现象。（Belady现象）,1)先进先出淘汰算法（FIFO）,基本思想：淘汰的页面是在最近一段时间里较久未被访问的那页。 理由：根据程序局部性原理，那些刚被使用过的页面，可能马上还要被使用，而在较长时间

19、里未被使用的页面，可能不会马上使用到。,2)最近最少使用的先淘汰（LRU）,3)最近不用的先淘汰（NUR）,基本思想：需要在页表中设一“引用位”，当页面被访问时，该位由硬件自动置为1，而由页面管理程序周期地把所有引用位置为0。 优点：比较简单，易于实现。 缺点：周期大小不易确定。,4)最佳淘汰算法（OPT）,算法：调入一页而必须淘汰一个旧页时，所淘汰的页应该是以后不再访问的页或距现在最长时间后再访问的页。 特点：不是实际可行的算法，可用来作为衡量各种具体算法的标准，具有理论意义。,例,在一个请求分页系统中，假定系统分给一个作业的物理块数为3，并且此作业的页面走向为2，3，2，1，5，2，4，5

20、，3，2，5，2，用FIFO、LRU和OPT计算缺页。 1）使用FIFO算法 用FIFO算法，缺页数为9,例,2）使用LRU算法 用FIFO算法，缺页数为7,例,3）使用OPT算法 用FIFO算法，缺页数为6 从中可以看到：LRU算法最接近OPT。这表明LRU是优于FIFO的。,Belady现象（异常现象）,作业执行序列：1，2，3，4，1，2，5，1，2，3，4，5,设进程访问内存成功的次数为S，缺页的次数为F，则总访问次数A=S+F 缺页率：W=F/A,缺页率,6.5.1.6 颠簸（抖动）,颠簸：指页面在内存与外存之间频繁的换入换出，以至于系统用于调度页面所需要的时间比进程实际运行作业所占

21、用的时间还要长。 显然，颠簸是由于缺页率很高而引起的，它将严重地影响系统的效率，甚至可能使系统崩溃。,6.5.1.6 颠簸（抖动）,颠簸的原因： 1）分给进程的页架数过少； 2）页面置换算法不合理； 3）程序结构：比如转移指令的频繁出现、分散的全局变量都会破坏程序的局部性，从而增加缺页率，引起颠簸。 颠簸的处理：,6.5.1.7 工作集模型,工作集：一段时间的内存窗口。,缺页率,页架数,拐点,6.6.3 分段式存储管理,分段式存储管理以段为单位分配内存，每段分配一个连续的内存区，但各段之间不要求连续。 内存的分配与回收类似于可变分区管理的分配算法。,段式存储管理数据结构,段式存储管理地址结构,

22、由于段式存储管理系统中作业的地址空间是二维的，因此地址结构也包括两部分：段号和段内位移。,段号 S,位移量 W,0,12,11,31,地址转换,优缺点,优点： 1）提供了内外存统一管理的虚拟存储实现方案； 2）段式虚存每次交换的是一个程序段或数据段； 3）在段式管理中，段长可根据需要动态扩充。 缺点： 1）要求更多的硬件支持，提高了机器的成本； 2）由于在内存空闲区管理方式上与分区式管理相同，因而存在碎片问题； 3）每段的长度受内存可用空闲区大小的限制； 4）若淘汰算法选择不当，也有可能产生颠簸。,6.3.4 段页式存储管理,段页式存储管理是分段和分页的两种存储管理方式结合的结果，综合了两者的

23、优点。 作业有多个段组成，段由大小相同的若干页构成，页面有页内地址。 段页式管理系统的地址结构为（s,p,d） ，其中s为段号，p为段内页号，d为页内偏移量。,地址转换,p,d,实存地址,段表,段s的页表,段表地址寄存器,寄存器,快表,s,s,p1+d,s,p,p1,虚拟地址,+,+,地址转换,若运行进程访问虚地址V（s,p,d），在没有相关存储器的情况下，地址转换过程如下： 1）地址转换硬件将段表地址寄存器内容与指令地址中的段号s相加（按段表的表目长进行适当位移后相加），得到欲访问段s在该进程的段表中表目入口地址。 2）从该表的表目中得到该段的页表起始地址，并将其与地址中的页号p相加后，得到欲访问页p在该段的页表中的表目入口地址。 3）从该表表目中取出其对应的页架号与指令地址中的页内地址d拼接得到主存地址，然后访问。,优缺点,优点： 1）提供了二维地址空间，有利于存储共享； 2）便于段动态扩充，有利于实现动态数据结构； 3）对于大型软件，只需在运行中动态的连接需要的段； 4）把零头转换为页内零头，有利于提高存储空间的利用率。 缺点： 1）复杂性和开销增加了； 2）需要的硬件以及占用的内存也需要增加； 3）如果不采用相联存储器就会大大降低内存的访问效率。,