操作系统第5章.ppt

第5章 存储管理,5.1 存储管理的功能5.2 分区存储管理5.3 覆盖与交换技术5.4 页式管理5.5 段式与段页式管理5.6 局部性原理和抖动问题本章小结习题,5.1 存储管理的功能存储管理的功能如下:1.主存空间的分配与回收 2.地址转换 3.主存空间的共享和保护 4.主存空间的扩充,5.1.2 重定位一.绝对地址和逻辑地址内存地址的集合称为内存空间或物理地址空间。内存中，每一个存储单元都与相应的称为内存地址的编号相对应。显然，内存空间是一维线性空间。二.虚存的一维线性空间或多维线性空间变换到内存的唯一的一维物理线性空间1.虚拟空间的划分问题2.把虚拟空间中已链接和划分好的内容装入内存，并将虚拟地址映射为内存地址的问题。,1.静态地址重定位在虚空间程序执行之前由装配程序完成地址映射工作.静态重定位的优点是不需要硬件支持。缺点:不能移动在程序执行之前将有关部分全部装入必须占用连续的内存空间，这就难以做到程序和数据的共享。,2.动态地址重定位动态地址重定位（dynamic address relocation）是在程序执行过程中，在CPU访问内存之前，将要访问的程序或数据地址转换成内存地址。动态重定位依靠硬件地址变换机构完成。地址重定位机构需要一个(或多个)基地址寄存器BR和一个(或多个)程序虚拟地址寄存器VR。指令或数据的内存地址MA与虚拟地址的关系为:MA=(BR)+(VR)这里，(BR)与(VR)分别表示寄存器BR与VR中的内容。,图5.3 动态地址重定位,动态重定位的主要优点有:(1)可以对内存进行非连续分配。(2)动态重定位提供了实现虚拟存储器的基础。(3)有利于程序段的共享。,5.1.3 内外存数据传输的控制1.是用户程序自己控制:覆盖技术2.是操作系统控制:交换(swapping)方式请求调入(on demand)方式和预调入(on prefetch)方式。,5.1.4 内存的分配与回收几种策略和数据结构:分配结构(2)放置策略(3)交换策略(4)调入策略。(5)回收策略,5.1.5 内存信息的共享与保护常用的内存信息保护方法有硬件法、软件法和软硬件结合三种。1.上下界保护法是一种常用的硬件保护法,2.保护键法。,图5.5 保护键保护法,3.界限寄存器与CPU的用户态或核心态工作方式相结合的保护方式。在这种保护模式下，用户态进程只能访问那些在界限寄存器所规定范围内的内存部分，而核心态进程则可以访问整个内存地址空间。UNIX系统就是采用的这种内存保护方式。,5.2 分区存储管理5.2.1 分区管理基本原理 分区管理的基本原理是给每一个内存中的进程划分一块适当大小的存储区,以连续存储各进程的程序和数据，使各进程得以并发执行。按分区的时机，分区管理可以分为固定分区和动态分区两种方法。,1.固定分区法 把内存区固定地划分为若干个大小不等的区域。划分的原则由系统操作员或操作系统决定。分区一旦划分结束，在整个执行过程中每个分区的长度和内存的总分区个数将保持不变。系统对内存的管理和控制通过数据结构分区说明表进行，,图5.6 固定分区法,2.动态分区法 动态分区法在作业执行前并不建立分区，分区的建立是在作业的处理过程中进行的，且其大小可随作业或进程对内存的要求而改变。这就改变了固定分区法中那种即使是小作业也要占据大分区的浪费现象，从而提高了内存的利用率,图5.7 内存初始分配情况,图5.8 内存分配变化过程,内存管理用数据结构:可用分区表:每个表目记录一个空闲区可用分区自由链:查找比可用表困难，但不必占用额外的内存区。请求表:请求表的每个表目描述请求内存资源的作业或进程号以及所请求的内存大小。,图5.9 可用表、自由链及请求表,图5.10 固定分区分配算法,5.2.2 分区的分配与回收1.固定分区时的分配与回收,2.动态分区时的分配与回收动态分区时的分配与回收主要解决三个问题:(1)对于请求表中的要求内存长度，从可用表或自由链中寻找出合适的空闲区分配程序。(2)分配空闲区之后，更新可用表或自由链。(3)进程或作业释放内存资源时，和相邻的空闲区进行链接合并，更新可用表或自由链。,动态分区时的分配方法：最先适应法(first fit algorithm)最佳适应法(best fit algorithm)最坏适应法(worst fit algoriathm)(1)最先适应法按起始地址递增的次序排列(2)最佳适应算法最佳适应算法要求从小到大的次序组成空闲区可用表或自由链。(3)最坏适应算法最坏适应算法要求空闲区按其大小递减的顺序组成空闲区可用表或自由链。,图5.11 最先适应算法,4.几种分配算法的比较思考：三种分配算法的各自特点从查找速度、释放速度及空闲区的利用等三个方面对上述三种算法进行比较。,内存回收4种情况：如果释放区与上下两空闲区相邻如果释放区只与上空闲区相邻如果释放区与下空闲区相邻如果释放区不与任何空闲区相邻,图5.12 空闲区的合并,5.2.3 有关分区管理其他问题的讨论1.关于虚存的实现2.关于内存扩充3.关于地址变换和内存保护设CPU指令所要访问的虚拟地址为D静态重定位:在上下限寄存器中值之间动态重定位若DVR(VR是限长寄存器中的限长值)，则说明地址越界若D=VR，则该地址是合法的，由硬件完成对该虚拟地址的动态重定位。保护键法也可用来对内存各分区提供保护。,4.分区存储管理的主要优缺点分区存储管理的主要优点如下:(1)实现了多个作业或进程对内存的共享，有助于多道程序设计，从而提高了系统的资源利用率。(2)该方法要求的硬件支持少，管理算法简单，因而实现容易。主要缺点有:(1)内存利用率仍然不高。和单一连续分配算法一样，存储器中可能含有从未用过的信息。而且，还存在着严重的碎小空闲区(碎片)不能利用的问题。(2)作业或进程的大小受分区大小控制，除非配合采用覆盖和交换技术。(3)难以实现各分区间的信息共享。,5.3.1 覆盖技术 把程序划分为若干个功能上相对独立的程序段，按照程序的逻辑结构让那些不会同时执行的程序段共享同一块内存区。覆盖技术要求程序员提供一个清楚的覆盖结构，程序员负担较重。,5.3 覆盖与交换技术,图5.13 覆盖示例,5.3.2 交换技术 交换是指先将内存某部分的程序或数据写入外存交换区，再从外存交换区中调入指定的程序或数据到内存中来，并让其执行的一种内存扩充技术。交换主要是在进程或作业之间进行，而覆盖则主要在同一个作业或进程内进行。交换进程由换出和换入两个过程组成。其中换出(swap out)过程把内存中的数据和程序换到外存交换区，而换入(swap in)过程把外存交换区中的数据和程序换到内存分区中。,1.各进程的虚拟空间被划分成若干个长度相等的页(page)。进程的虚地址变为页号p与页内地址的d所组成。2.把内存空间也按页的大小划分为片或页面(page frame)。3.用户进程在内存空间内除了在每个页面内地址连续之外，每个页面之间不再连续。19 10 9 0图5.14 页的划分,5.4 页 式 管 理5.4.1 页式管理的基本原理,优点：第一是实现了内存中碎片的减少，因为任一碎片都会小于一个页面。第二是实现了由连续存储到非连续存储这个飞跃，为在内存中局部地、动态地存储那些反复执行或即将执行的程序和数据段打下了基础。,5.4.2 静态页面管理 静态页面管理方法在作业或进程开始执行之前，把该作业或进程的程序段和数据全部装入内存的各个页面中，并通过页表(page mapping table)和硬件地址变换机构实现虚拟地址到内存物理地址的地址映射。,(1)页表最简单的页表由页号与页面号组成。页式管理时每个进程至少拥有一个页表。图5.15 基本页表示例,1.内存页面分配与回收,(2)请求表请求表用来确定作业或进程的虚拟空间的各页在内存中的实际对应位置。请求表整个系统一张，如图5.16所示。图5.16 请求表示例,(3)存储页面表存储页面表也是整个系统一张，存储页面表指出内存各页面是否已被分配出去,以及未分配页面的总数。位示图空闲页面链图5.17 位示图,图5.18 页面分配算法流图,2.分配算法,图5.19 页号与页面号设每个页面长度为1K，指令LOAD 1，2500的虚地址为100，怎样通过图5.19所示页表来找到该指令所对应的物理地址呢?,3.地址变换,图5.20 地址变换,取一个数据或指令至少要访问内存两次以上办法1：就是把页表放在寄存器中而不是内存中，但由于寄存器价格太贵，这样做是不可取的办法2：是在地址变换机构中加入一个高速联想存储器，构成一张快表。在快表中，存入那些当前执行进程中最常用的页号与所对应的页面号，从而以提高查找速度。,静态页式管理优点：解决了分区管理时的碎片问题。缺点：在执行前全部装入内存 作业或进程的大小仍受内存可用页面数的限制,5.4.3 动态页式管理分为请求页式管理和预调入页式管理。共同点：请求页式管理和预调入页式管理在作业或进程开始执行之前，都不把作业或进程的程序段和数据段一次性地全部装入内存，而只装入被认为是经常反复执行和调用的工作区部分。其他部分则在执行过程中动态装入。主要区别：在调入方式上 请求页式管理：当需要执行某条指令而又发现它不在内存时或当执行某条指令需要访问其他的数据或指令时，这些指令和数据不在内存中，从而发生缺页中断，系统将外存中相应的页面调入内存。预调入方式：系统对那些在外存中的页进行调入顺序计算，估计出这些页中指令和数据的执行和被访问的顺序，并按此顺序将它们顺次调入和调出内存。,问题1：虚页不在内存中的-扩充页表的方法解决。增设该页是否在内存的中断位以及该页在外存中的副本起始地址。扩充后的页表如图5.21。图5.21 加入中断处理后的页表,问题2：虚页不在内存时的处理。第一，采用何种方式把所缺的页调入内存。-产生缺页中断信号，由中断处理程序做出相应的处理第二，如果内存中没有空闲页面时，把调进来的页放在什么地方。-置换算法在页表中还应增加一项以记录该页是否曾被改变。增加改变位后的页表项如图5.22所示。,图5.22 加入改变位后的页表,图5.23 动态页式管理流图,置换算法 抖动(thrashing)现象：如果置换算法选择不当，有可能产生刚被调出内存的页又要马上被调回内存，调回内存不久又马上被调出内存，如此反复的局面。这使得整个系统的页面调度非常频繁，以致大部分时间都花费在主存和辅存之间的来回调入调出上。这种现象被称为抖动(thrashing)现象。,5.4.4 请求页式管理中的置换算法(1)随机淘汰算法。(2)轮转法和先进先出算法。由实验和测试发现FIFO算法和RR算法的内存利用率不高。先进先出算法的另一个缺点是它有一种陷阱现象在未给进程或作业分配足它所要求的页面数时，有时会出现分配的页面数增多，缺页次数反而增加的奇怪现象。这种现象称为Belady现象。,图5.24 FIFO算法的Belady现象,下面的例子可以用来说明FIFO算法的正常换页情况和Belady现象。例:设进程P共有8页，且已在内存中分配有3个页面，程序访问内存的顺序(访问串)为7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1。图5.25 Belady现象示例(1)缺页率为12/17=70.5%,图5.26 Belady现象示例(2)如果给进程P分配4个页面，共发生9次缺页，其缺页率为9/17=52.9%,设进程P可分为5页，访问串为1，2，3，4，1，2，5，1，2，3，4，5。当进程P分得3个页面时，执行过程中内存页面变化如图5.27所示。图5.27 Belady现象示例(3)缺页9次，其缺页率为9/12=75%。,如果为进程P分配4个内存页面图5.28 Belady现象示例(4)缺页次数为10次。即缺页率=10/12=83.3%。先进先出算法产生Belady现象的原因在于它根本没有考虑程序执行的动态特征。,(3)最近最久未使用页面置换算法(least recently used)。该算法的基本思想是:当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。常用的近似算法有:a)最不经常使用页面淘汰算法LFU(least frequently used)。增设一个访问计数器b)最近没有使用页面淘汰算法NUR。该算法在需要淘汰某一页时，从那些最近一个时期内未被访问的页中任选一页淘汰。增设一个访问位(4)理想型淘汰算法OPT(optimal replacement algorithm)。,5.4.5 存储保护页式管理可以为内存提供两种方式的保护。一种是地址越界保护，另一种是通过页表控制对内存信息的存取操作方式以提供保护。地址越界保护可由地址变换机构中的控制寄存器的值页表长度和所要访问的虚地址相比较来完成。存取控制保护的实现则是在页表中增加相应的保护位即可。,5.4.6 页式管理的优缺点优点:(1)有效地解决了碎片问题。(2)动态页式管理提供了内存和外存统一管理的虚存实现方式主要缺点是:要求有相应的硬件支持(2)增加了系统开销(3)请求调页的算法如选择不当，有可能产生抖动现象。(4)虽然消除了碎片，但每个作业或进程的最后一页内总有一部分空间得不到利用。如果页面较大，则这一部分的损失仍然较大。,5.5 段式与段页式管理5.5.1 段式管理的基本思想段式管理的基本思想是:把程序按内容或过程(函数)关系分成段，每段有自己的名字。一个用户作业或进程所包含的段对应于一个二维线性虚拟空间，也就是一个二维虚拟存储器。段式管理程序以段为单位分配内存有利于:不同作业或进程之间共享 动态链接,5.5.2 段式管理的实现原理1.段式虚存空间每个段是一个首地址为零的、连续的一维线性空间。段式管理把一个进程的虚地址空间设计成二维结构，即段号s 与段内相对地址w。,2.段式管理的内存分配与释放段式管理中以段为单位分配内存，每段分配一个连续的内存区。同一进程所包含的各段之间不要求连续。段式管理的内存分配与释放与可变分区相同,另一种情况:内存中没有足够的空闲区满足调入段的内存要求时-置换算法一次调入时所需淘汰的段数与段的大小有关,图5.29 缺段中断处理过程,图5.30 段表,3.段式管理的地址变换(1)段表(segment mapping table),(2)动态地址变换 通过访问段表寄存器，得到该进程的段表始址从而可开始访问段表。由虚地址中的段号s为索引，查段表。若该段在内存，则判断其存取控制方式是否有错。如果存取控制方式正确，则从段表相应表目中查出该段在内存的起始地址，并将其和段内相对地址w相加，从而得到实际内存地址。不在内存，则产生缺段中断,找到足够长度的空闲区来装入所需要的段。如果内存中的可用空闲区总数小于所要求的段长时，则检查段表中访问位，以淘汰那些访问概率低的段并将需要段调入。段式管理时的地址变换过程也必须经过二次以上的内存访问。高速联想寄存器的方法也可以用在段式地址变换中。,图5.31 段式地址变换过程,图5.32 段式系统中共享内存副本,4.段的共享与保护(1)段的共享,段表中可设立相应的共享位来判别该段是否正被某个进程调用,(2)段的保护段式管理的保护主要有两种。一种是地址越界保护法，段表中的段长项与虚拟地址中的段内相对地址比较进行的。若段内相对地址大于段长，系统就会产生保护中断。不过，在允许段动态增长的系统中，段内相对地址大于段长是允许的。为此，段表中设置相应的增补位以指示该段是否允许该段动态增长。另一种是存取方式控制保护法。,5.5.3 段式管理的优缺点(1)段式管理也提供了内外存统一管理的虚存实现(2)在段式管理中，段长可根据需要动态增长。便于对具有完整逻辑功能的信息段进行共享。(4)便于实现动态链接。要求有更多的硬件支持。这就提高了机器成本。在碎片问题以及为了消除碎片所进行的合并等问题上较分页式管理要差。允许段的动态增长也会给系统管理带来一定的难度和开销。段式管理的另一个缺点就是每个段的长度受内存可用区大小的限制。和页式管理一样，段式管理系统在选择淘汰算法时也必须十分慎重，否则也有可能产生抖动现象。,5.5.4 段页式管理的基本思想5.5.5 段页式管理的实现原理1.虚地址的构成虚拟地址由三部分组成:即段号s，页号p和页内相对地址d。如下所示:,图5.33 段页式管理中段表、页表与内存的关系,2.段表和页表,3.动态地址变换过程至少需要访问三次以上的内存。为了提高地址转换速度，设置快速联想寄存器就显得比段式管理或页式管理时更加需要。,图5.34 段页式地址变换,段页式管理的地址变换机构,段页式管理优缺点:具有页式管理和段式管理二者的优点。但反过来说，由于管理软件的增加，复杂性和开销也就随之增加了。另外，需要的硬件以及占用的内存也有所增加。更重要的是，如果不采用联想寄存器的方式提高CPU的访内速度，将会使得执行速度大大下降。,5.6 局部性原理和抖动问题动态页式管理，段式管理以及段页式管理都提供了一种将内存和外存统一管理的实现方法。然而，由于上述实现方法实质上要在内存和外存之间交换信息，因此，就要不断地启动外部设备以及相应的处理过程。一般来说，计算机系统的外部存储器具有较大的容量而访问速度并不高。为了进行数据的读写而涉及到的一系列处理程序也要耗去大量的时间。如果内存和外存之间数据交换频繁，势必会造成对输入/输出设备的巨大压力和使得机器的主要开销大多用在反复调入调出数据和程序段上，从而无法完成用户所要求的工作。因此，要求在内存中存放一个不小于最低限度的程序段或数据，而且它们必须是那些正在被调用，或那些即将被调用的部分。,由模拟实验知道，在几乎所有的程序的执行中，在一段时间内，CPU总是集中地访问程序中的某一个部分而不是随机地对程序所有部分具有平均访问概率。把这种现象称为局部性原理。与CPU访问该局部内的程序和数据的次数相比，该局部段的移动速率相当慢。这就使得前面所讨论的页式管理、段式管理以及段页式管理所实现的虚存系统成为可能。但是，如果不能正确地将那些系统所需要的局部段放入内存的话，则显然系统的效率会大大降低，甚至无法有效地工作。试验表明，任何程序在局部性放入时，都有一个临界值要求。当内存分配小于这个临界值时，内存和外存之间的交换频率将会急剧增加，而内存分配大于这个临界值时，再增加内存分配也不能显著减少交换次数。,这个内存要求的临界值被称为工作集。图5.35说明这种情况。图5.35 内存与交换次数的关系,一个进程执行过程中缺页(missing page)的发生有两种可能。一种是并发进程所要求的工作集总和大于内存可提供的可用区。这时，系统将无法正常工作，因为缺乏足够的空间装入所需要的程序和数据。另一种可能性是，虽然存储管理程序为每个并发进程分配了足够的工作集，但系统无法在开始执行前选择适当的程序段和数据进入内存。这种情况下，只能依靠执行过程中，当CPU发现所要访问的指令或数据不在内存时，由硬件中断后转入中断处理程序，将所需要的程序段和数据调入。这是一种很自然的处理方法。,当给进程分配的内存小于所要求的工作集时，由于内存外存之间交换频繁，访问外存时间和输入/输出处理时间大大增加，反而造成CPU因等待数据空转，使得整个系统性能大大下降，这就造成了系统抖动。可以利用统计模型进一步分析工作集与抖动之间的关系。设r为CPU在内存中存取一个内存单元的时间，t为从外存中读出一页数据所需时间，p(s)为CPU访问内存时，所访问的页正好不在内存的概率，这里s是当前进程在内存中的工作集。显然，在虚存情况下存取一个内存单元的平均时间可描述为T=r+p(s)*t,由程序模拟可知，p(s)=ae-bs这里，0a1b，ae-bsr另外，假定内存中各并发进程具有相同的统计特性，而且对于一个并发进程来说，只有发生缺页时才变成等待状态。这是为了简化讨论而忽略了外部设备和进程通信功能的存在。由于访问外存一个页面的速度为t，且缺页发生的概率为p(s)，则在处理机访问一个内存单元的r时间内，平均每秒引起的内外存之间页传送率为p(s)/r。也就是每r/p(s)秒需要从外存向内存传送一页。从而，对于一个在虚存范围内执行的进程，它可以处于三种可能的状态之中，即:(1)t r/p(s)(2)t r/p(s)(3)t=r/p(s),对于第一种情况，由于页传送速度大于访问外存页面的速度，因此，进程在执行过程中发生缺页的次数较少，并不经常从外存调页。但是，在第二种情况时，由于内外存之间的页面传送速度已经小于访问外存页面速度，因此，进程在执行过程中发生缺页的次数已经多到外存供不应求的地步。事实上，这时的系统已处于抖动状态。第三种情况是一种较理想的情况，即进程在执行过程中所需要的页数正好等于从外存可以调入的页数。此时该进程在内存中占有最佳工作集。根据以上讨论可知，一个进程在内存中占有最佳工作集的条件是:p(w)=r/t这里，r是CPU访问内存单元所需平均时间，t是访问外存一个页面所需平均时间。,因为 p(w)可表示为p(w)=ae-bw从而有，w=ln(at/r)/b 即，与内存存取速度r相比，若外存传送速度越慢，所需工作集就越大。当然，上面讨论是在作了许多近似的情况下得出的结论。事实上，由于各进程所包含的程序段多少，选用的淘汰算法等不一样，工作集的选择也不一样。一般来说，选择工作集有静态和动态两种选择方法，这里不再进一步介绍。另外，由以上讨论，我们可以找出解决抖动问题的几种关键办法。,抖动只有在 tr/p(s)时才会发生。而p(s)等于ae-bs是一个与工作集s、参数a和b有关的概率值。p(s)是可以改变的。对于给定的系统来说，t和r则是一个很难改变的数字。显然，解决抖动问题的最关键办法是将p(s)减少到使t=r/p(s)。这只需要:(1)增加s，也就是扩大工作集，或是(2)改变参数a和b，也就是选择不同的淘汰算法以解决抖动问题。在物理系统中，为了防止抖动的产生，在进行淘汰或置换时，一般总是把缺页进程锁住，不让其换出，而调入的页或段总是占据那些暂时得不到执行的进程所占有的内存区域，从而扩大缺页进程的工作集。UNIX System 中就是采用的这种方法。,本 章 小 结本章介绍了各种常用的内存管理方法，它们是分区式管理、页式管理、段式管理和段页式管理。内存管理的核心问题是如何解决内存和外存的统一，以及它们之间的数据交换问题。内存和外存的统一管理使得内存的利用率得到提高，用户程序不再受内存可用区大小的限制。与此相关联，内存管理要解决内存扩充、内存的分配与释放、虚拟地址到内存物理地址的变换、内存保护与共享、内外存之间数据交换的控制等问题。图5.36系统地对几种存储管理方法所提供的功能和所需硬件支持作了一个比较。,图5.36 各种存储方法比较,习 题5.1 存储管理的主要功能是什么？5.2 什么是虚拟存储器，其特点是什么？5.3 实现地址重定位的方法有哪几类？形式化地描述动态重定位过程。5.4 常用的内存信息保护方法有哪几种？它们各自的特点是什么？5.5 如果把DOS的执行模式改为保护模式，起码应作怎样的修改？5.6 动态分区式管理的常用内存分配算法有哪几种？比较它们各自的优缺点。,5.7 5.2节讨论的分区式管理可以实现虚存吗？如果不能，需怎样修改？试设计一个分区式管理实现虚存的程序流程图。如果能，试说明理由。5.8 简述什么是覆盖？什么是交换？覆盖和交换的区别是什么？5.9 什么是页式管理？静态页式管理可以实现虚存吗？5.10 什么是请求页式管理？试设计和描述一个请求页式管理时的内存页面分配和回收算法（包括缺页处理部分)。5.11 请求页式管理中有哪几种常用的页面置换算法？试比较它们的优缺点。,5.12 什么是Belady现象？找一个Belady现象的例子。5.13 描述一个包括页面分配与回收、页面置换和存储保护的请求页式存储管理系统。5.14 什么是段式管理？它与页式管理有何区别？5.15 段式管理可以实现虚存吗？如果可以，简述实现方法。5.16 为什么要提出段页式管理？它与段式管理及页式管理有何区别？5.17 为什么说段页式管理时的虚地址仍是二维的？5.18 段页式管理的主要缺点是什么？有什么改进办法？5.19 什么是局部性原理？什么是抖动？你有什么办法减少系统的抖动现象？,