操作系统-第四章存储器管理

操作系统_第四章存储器管理第一页，共105页。4.1存储器的层次结构

4.1.1多级存储器结构

寄存器高速缓存主存磁盘缓存磁盘可移动存储介质CPU寄存器主存辅存图4－1计算机系统存储层次示意第二页，共105页。1主存储器2寄存器4.1.2主存储器与寄存器

第三页，共105页。1高速缓存 CPU产品中，一级缓存的容量基本在4KB到64KB之间，一级缓存容量各产品之间相差不大。二级缓存容量则是提高CPU性能的关键。二级缓存容量的提升是由CPU制造工艺所决定的，容量增大必然导致CPU内部晶体管数的增加，要在有限的CPU面积上集成更大的缓存，对制造工艺的要求也就越高4.1.3高速缓存与磁盘缓存第四页，共105页。上溯到上个世纪80年代，由于处理器的运行速度越来越快，慢慢地，处理器需要从内存中读取数据的速度需求就越来越高了。然而内存的速度提升速度却很缓慢，而能高速读写数据的内存价格又非常高昂，不能大量采用。从性能价格比的角度出发，英特尔等处理器设计生产公司想到一个办法，就是用少量的高速内存和大量的低速内存结合使用，共同为处理器提供数据。这样就兼顾了性能和使用成本的最优。而那些高速的内存因为是处于CPU和内存之间的位置，又是临时存放数据的地方，所以就叫做缓冲存储器了，简称“缓存”。第五页，共105页。它的作用就像仓库中临时堆放货物的地方一样，货物从运输车辆上放下时临时堆放在缓存区中，然后再搬到内部存储区中长时间存放。货物在这段区域中存放的时间很短，就是一个临时货场。现在，为了适应速度更快的处理器P4EE，已经出现了三级缓存了，它的容量更大，速度相对二级缓存也要慢一些，但是比内存可快多了。缓存的出现使得CPU处理器的运行效率得到了大幅度的提升，这个区域中存放的都是CPU频繁要使用的数据，所以缓存越大处理器效率就越高，同时由于缓存的物理结构比内存复杂很多，所以其成本也很高。大量使用二级缓存带来的结果是处理器运行效率的提升和成本价格的大幅度不等比提升。举个例子，服务器上用的至强处理器和普通的P4处理器其内核基本上是一样的，就是二级缓存不同。至强的二级缓存是2MB～16MB，P4的二级缓存是512KB，于是最便宜的至强也比最贵的P4贵，原因就在二级缓存不同。第六页，共105页。IntelCorei7-980XExtremeEdition3.33GHz12ML3CacheLGA1366六核处理

厂商IntelCPU名称E6500

系列PentiumDuo

接口类型LGA775

核心数量双核工作频率2.93GHz

前端总线1066MHz

一级缓存2x(32k+32k)二级缓存2MB

是否支持64位运算是制造工艺45nm

2磁盘缓存第七页，共105页。4.2程序的装入和链接

编辑――编译――链接――装入――运行图4-2对用户程序的处理步骤第八页，共105页。4.2.1程序的装入

1、绝对装入：编译后，装入前已产生了绝对地址（内存地址），装入时不再作地址重定位,适用于单道系统。绝对地址的产生：（1）由编译器完成，（2）由程序员编程完成。对（1）而言，编程用符号地址。2、可重定位装入；静态重定位：装入时完成，主要工作是对相对地址中的指令和数据地址的调整过程，例：图4－3第九页，共105页。图4-3作业装入内存时的情况

第十页，共105页。4.2.1程序的装入

3.动态运行时装入可重定位装入方式在装入后不能移动程序该情况一般在执行时才完成相对——绝对地址的转换且有硬件的支持,能保证进程的可移动性。RoutineisnotloadeduntilitiscalledBettermemory-spaceutilization;unusedroutineisneverloaded.Usefulwhenlargeamountsofcodeareneededtohandleinfrequentlyoccurringcases.Nospecialsupportfromtheoperatingsystemisrequiredimplementedthroughprogramdesign.第十一页，共105页。4.2.2程序的链接1、静态链接：事先连接a．对相对地址的修改b．变换外部调用符号2、装入时动态链接：边装入边连接a.便于修改和更新b.便于实现对目标模块的共享

第十二页，共105页。(a)目标模块模块ACALLB;RETURN模块BCALLC;RETURN模块CRETURN0L-10M-10N-1模块AJSRL;RETURN模块BJSRL+M;RETURN模块CRETURN0L-1LL+M-1L+ML+M+N-1(b)装入模块图4-4程序链接示意图

第十三页，共105页。3、运行时动态链接DynamicLinking近几年流行起来的运行时动态链接方式，是对上述在装入时链接方式的一种改进。这种链接方式是将对某些模块的链接推迟到执行时才执行，亦即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。第十四页，共105页。4.3连续分配方式

4.3.1单一连续分配用于单用户，单任务中4.3.2分区式分配固定式动态分区分配可重定位分区分配第十五页，共105页。4.3.1单一连续分区这是最简单的一种存储管理方式，但只能用于单用户、单任务的操作系统中。采用这种存储管理方式时，可把内存分为系统区和用户区两部分，系统区仅提供给OS使用，通常是放在内存的低址部分；用户区是指除系统区以外的全部内存空间，提供给用户使用。第十六页，共105页。4.3.2固定分区特点：有n个分区，则可同时装入n个作业/任务。一、分区大小：相等:不相等：不相等利用率更高。二、内存分配：数据结构将分区按大小排序，建立分区使用表，并将其地址、分配标识作记录三、特点：简单，有碎片（内零头）,浪费。第十七页，共105页。图4-5固定分区使用表

第十八页，共105页。4.3.3动态分区分配一、数据结构1．空闲分区表2．空闲分区链图4-6空闲链结构

第十九页，共105页。二、分配算法1．首次适应算法FF。要求：分区按低址――高址链接特点：找到第一个大小满足的分区，划分。有外零头，低址内存使用频繁。2．循环首次适应算法。从1中上次找到的空闲分区的下一个开始查找。特点：空闲分区分布均匀，提高了查找速度；缺乏大的空闲分区。3．最佳适应算法分区按大小递增排序；分区释放时需插入到适当位置分割后留下小碎片，难以利用。4.3.3动态分区分配第二十页，共105页。二、分配算法4．最坏适应算法WF。总是挑选最大的空闲分区分割给作业使用分区按大小递减排序；优点：剩下碎片不至于太小缺点：缺乏大的空闲分区5.快速适应算法QF分类搜索：将空闲分区根据容量大小分类设立管理索引表优点：查找效率高；不要分割缺点：分区归还主存时复杂，开销大4.3.3动态分区分配第二十一页，共105页。三、分区分配操作1．分配：图4-72．回收：（1）上邻空闲区：合并，改大小（2）下邻空闲区：合并，改大小，首址。（3）上、下邻空闲区：合并，改大小。（4）不邻接，则建立一新表项。4.3.3动态分区分配第二十二页，共105页。图4-7内存分配流程第二十三页，共105页。2)回收内存

图4-8内存回收时的情况

第二十四页，共105页。例1某系统采用动态分区分配方式管理内存，内存空间为640K，高端40K用来存放操作系统。在内存分配时，系统优先使用空闲区低端的空间。对下列的请求序列：作业1申请130K、作业2申请60K、作业3申请100K、作业2释放60K、作业4申请200K、作业3释放100K、作业1释放130K、作业5申请140K、作业6申请60K、作业7申请50K、作业6释放60K，请分别画图表示出使用首次适应算法和最佳适应算法进行内存分配和回收后内存的实际使用情况。第二十五页，共105页。首次适应算法最佳适应算法解第二十六页，共105页。4.3.6可重定位分区分配1.动态重定位的引入连续式分配中，总量大于作业大小的多个小分区不能容纳作业。紧凑通过作业移动将原来分散的小分区拼接成一个大分区。每次紧凑后，都必须对移动了的程序或数据进行重定位。第二十七页，共105页。图4-9紧凑的示意

第二十八页，共105页。2、动态重定位的实现图4-10动态重定位示意图

动态重定位：相对地址－》物理地址是在程序执行时自动进行第二十九页，共105页。3.动态重定位分区分配算法

图4-11动态重定位分区分配算法流程图

第三十页，共105页。内存扩充实现内存扩充的三种技术：覆盖技术(overlay)交换技术(s)虚拟存储器（virtualmemory）第三十一页，共105页。覆盖(overlay)引入：其目标是在较小的可用内存中运行较大的程序。常用于多道程序系统，与分区存储管理配合使用。原理：一个程序的几个代码段或数据段，按照时间先后来占用公共的内存空间。将程序的必要部分（常用功能）的代码和数据常驻内存；可选部分（不常用功能）在其他程序模块中实现，平时存放在外存中（覆盖文件），在需要用到时才装入到内存；不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖。(即不同时用的模块可共用一个分区)第三十二页，共105页。注：另一种覆盖方法：(100K)A(20K)占一个分区：20K；B(50K)、D(20K)和E(40K)共用一个分区：50K；F(30K)和C(30K)共用一个分区：30K；覆盖技术第三十三页，共105页。4.3.7对换（S）1对换的引入将阻塞进程，暂时不用的程序，数据换出。将具备运行条件的进程换入。类型：整体对换：进程对换，解决内存紧张部分对换：页面对换/分段对换：提供虚存支持2对换空间的管理外存对换区比文件区侧重于对换速度。因此，对换区一般采用连续分配。采用数据结构和分配回收类似于可变化分区分配。第三十四页，共105页。4.3.7对换3换出与换入（1）换出选出被换出进程： 因素：优先级，驻留时间，进程状态换出过程：对于共享段：计数减1，是0则换出，否则不换修改PCB和内存分配表（2）换入：选择换入进程：优先级，换出时间等。申请内存。换入第三十五页，共105页。4.4基本分页存储管理

连续分配引起:碎片碎片问题的解决：紧凑方式消耗系统开销。离散分配分页不具备页面对换功能的称为基本分页存储管理方式分段段页第三十六页，共105页。1.页面页面和物理块：逻辑空间和内存空间，页内碎片页面大小由机器的地址结构决定页太大，页内碎片大。页太小：页表可能很长，换入/出效率低2.地址结构31 1211 0逻辑地址A；页大小L(设为1024)；页内偏移d

P=Int[A/L] d=AmodL如：A＝2170B.则P=2,d=1224.4.1页面与页表页号P位移W第三十七页，共105页。3.页表--实现从页号到物理块号的地址映射0页1页2页3页4页5页n页021326384950123456789用户程序页表页号块号内存第三十八页，共105页。PagingExample

第三十九页，共105页。

例1：某系统采用页式存储管理策略，拥有逻辑空间32页，每页2K，拥有物理空间1M①写出逻辑地址的格式②若不考虑访问权限等，进程的页表有多少项？每项至少有多少位？③如果物理空间减少一半，页表结构应相应作怎样的改变？第四十页，共105页。

答：①该系统拥有逻辑空间32页，故逻辑地址中页号必须用5位描述；而每页为2K，因此，页内地址必须用11位描述，格式如下：15 1110 0②每个进程最多32个页面，因此进程的页表项最多为32项；页表项只需给出页所对应的物理块块号，1M的物理空间可分为29个内存块，故每个页表项至少有9位。③如果物理空间减少一半，则页表中页表项数不变，但每项的长度减少1位。页号 页内地址第四十一页，共105页。4.4.2地址变换机构

基本任务：借助页表完成逻辑页号-物理块号的映射。1、基本地址变换机构： 页表寄存器：页表始址，页表长度平时每个进程未执行时将其信息（如页表长度、始址）放在PCB中，执行时将它们装入页表寄存器。地址变换机构自动将有效地址分为页号和页内地址越界保护检索页表生成物理地址第四十二页，共105页。第四十三页，共105页。

例2：已知某分页系统，主存容量为64K，页面大小为1K，对一个4页大的作业，其0、1、2、3页分别被分配到主存的2、4、6、7块中。（1）将十进制的逻辑地址1023、2500、3500、4500转换成物理地址？（2）以十进制的逻辑地址1023为例画出地址变换过程图？第四十四页，共105页。

答： ①逻辑地址1023：1023/1K，得页号为0，页内地址为1023，查页表找到对应的物理块号为2，故物理地址为2×1K+1023=3071②逻辑地址2500：2500/1K，得页号为2，页内地址为452，查页表找到对应的物理块号为6，故物理地址为6×1K+452=6596③逻辑地址3500：3500/1K，得页号为3，页内地址为428，查页表找到对应的物理块号为7，故物理地址为7×1K+428=7596④逻辑地址4500：4500/1K，得页号为4，页内地址为404，因页号不小于页表长度，故产生越界中断。第四十五页，共105页。（2）地址变换过程图第四十六页，共105页。2.具有快表的地址变换机构Associativememory–parallelsearch Addresstranslation(A´,A´´)IfA´isinassociativeregister,getframe#out.Otherwisegetframe#frompagetableinmemoryPage#Frame#第四十七页，共105页。2.具有快表的地址变换机构先查快表，若有则得出块号若无，则再查页表，得出块号，并重新修改快表第四十八页，共105页。2.具有快表的地址变换机构

不具快表，则需两次访问内存。（1）访页表，得到物理地址（2）得到物理地址中的数据有快表，命中率高，速度提高。快表贵，不能太多。第四十九页，共105页。

例3：有一页式系统，其页表存放在主存中：①如果对主存的一次存取需要1.5μs,试问实现一次页面访问的存取时间是多少?②如果系统加有快表,平均命中率为85%,当页表项在快表中时,其查找时间忽略为0,试问此时的存取时间是多少?第五十页，共105页。答：若页表存放在主存中，则要实现一次页面访问需两次访问主存：一次是访问页表，确定所存取页面的物理地址（称为定位）。第二次才根据该地址存取页面数据。■页表在主存的存取访问时间=1.5*2=3(μs)■增加快表后的存取访问时间=0.85*1.5+(1-0.85)*2*1.5=1.725(μs)第五十一页，共105页。4.4.3两级和多级页表

页表可能很大，将其离散存放在不同页块中。建一“外部页表”来管理这些离散页表块。相当于单级页表中的页表寄存器，一般应常驻内存。每项记录页表始址，且增加存在位。64位机器页表一般>3级，最外层页表常驻。1.两级页表(Two-LevelPageTable)

逻辑地址结构可描述如下：

第五十二页，共105页。图4-15两级页表结构

第五十三页，共105页。第五十四页，共105页。例4某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面对应的物理块号如下表：页号物理块号051102437则逻辑地址0A5C（H）所对应的物理地址为多少？第五十五页，共105页。答0A5C＝0000,1010,0101,1100页号为2，对应块号为4，有：物理地址：0001，0010,0101,1100即：125C（H）第五十六页，共105页。4.5基本分段存储管理

引入分页存储管理方式的目的是提高内存利用率4.5.1分段存储管理方式的引入

满足用户和程序员的以下需求：（1）方便编程；（2）分段共享；（3）分段保护；（4）动态增长；（如数据段的增长）（5）动态链接；第五十七页，共105页。4.4.2分段系统的基本原理

分段对用户而言，分段是2维的。段号+段内地址。得到编译程序的支持段表：基址+段长逻辑段—map—物理内存区地址变换机构：图4－17，4－18段表寄存器、两种越界中断分页与分段的主要区别：（1）页是信息的物理单位，段是逻辑单位（2）页长度固定，段长度不固定（由用户指定）（3）一维与二维第五十八页，共105页。第五十九页，共105页。8第六十页，共105页。例5对于下面的段表，请将逻辑地址（0,137），（1,4000），(2,3600)，(5,230)转换成物理地址。段号内存地址段长050K10K160K3K270K5K3120K8K4150K4K第六十一页，共105页。答物理地址为：50K+137=51337段内地址超过段长3K，产生越界中断。物理地址为：70K+3600=75280段号等于段表长，段号不合法，产生越界中断。第六十二页，共105页。4.5.3信息共享

分段的优点：段式系统易于共享例：图4-19及4-20分页与分段共享比较可重入代码（纯代码）可重入代码是一种不允许任何进程对它进行修改的代码各个进程应保留局部数据区第六十三页，共105页。图4-19分页系统中共享editor的示意图第六十四页，共105页。图4-20分段系统中共享editor的示意图第六十五页，共105页。4.5.4段页式存储管理分页优点：提高内存利用率分段优点：方便用户，易于共享，保护，动态链接。1、段页式系统基本原理段号+段内页号+页内地址注意： 对用户而言，仍然是二维编址。对系统而言，则是三维编址图4-20

图4-21第六十六页，共105页。图4-21作业地址空间和地址结构第六十七页，共105页。图4-22利用段表和页表实现地址映射第六十八页，共105页。4.5.4段页式存储管理2、地址变换三次访内存操作，为提高速度，在地址变换机构中增设一高速缓冲寄存器（Cache）第六十九页，共105页。4.6虚拟存储器 分页内存分配和分段内存分配方法可以解决程序在内存中离散存放的问题，但是，这两种方式都要求程序整个装入内存。事实上，很多时候，程序本身比内存要大得多，那么简单的分页和分段的内存方式就无法解决这个问题了。可以采用虚拟存储器的方法，使用请求分配和置换策略来实现存储管理。第七十页，共105页。4.6.虚拟存储器为什么需要虚拟存储器：程序大于内存程序暂时不执行或运行完是否还要占用内存程序的局部性原理第七十一页，共105页。4.6虚拟存储器4.6.1引入1.常规存储管理的特征：一次性（指全部装入）、驻留性（指驻留在内存不换出）2、局部性原理时间局部性：如循环执行空间局部性：如顺序执行。3、虚拟存贮器具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储系统。实质：以时间换空间，但时间牺牲不大。虚存大小由_______决定。第七十二页，共105页。虚拟存储器技术需要解决的问题：地址映射

分配策略

置换策略

装载控制

第七十三页，共105页。4.6.2虚拟存储器的实现方式需要动态重定位1、请求分页系统以页为单位转换需硬件：（1）请求分页的页表机制（2）缺页中断（3）地址变换机构需实现请求分页机制的软件（页面请调、置换软件等）2、请求分段系统以段为单位转换:（1）请求分段的段表结构（2）缺段中断（3）地址变换机构需实现请求分段机制的软件（段请调、置换软件等）第七十四页，共105页。4.6.3虚存特征1．多次性：局部装入，多次装入。2．对换性：换进、换出3．虚拟性：从逻辑上扩充内存离散分配：支持多次性和对换性，若连续则不可能提供虚存，无法支持大作业小内存运行第七十五页，共105页。请求分页概念

在进程开始运行之前，不是装入全部页面，而是装入几个页面，之后根据进程运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面。第七十六页，共105页。4.7.1请求分页中的数据结构及硬件支持1、页表机制页表项：2、缺页中断机构：可在指令执行期间产生（如图4-24） 转入缺页中断处理程序。3、地址变换机构 比较简单分页机制，增加了中断处理，图4.254.7请求分页存储管理方式页号物理块号状态位P访问字段A修改位M外存地址第七十七页，共105页。

图4－24涉及6次缺页中断的指令第七十八页，共105页。图4-25请求分页中的地址变换过程

MMU第七十九页，共105页。例6现有一请求调页系统，页表保存在寄存器中。若有一个被替换的页未被修改过，则处理一个缺页中断需要8ms；若被替换的页已被修改过，则处理一个缺页中断需要20ms；内存存取时间为1µs，访问页表的时间可忽略不计。假定70%被替换的页被修改过，为保证有效存取时间不超过2µs，可接受的最大缺页率是多少？注：（缺页率=缺页次数/总的页面访问次数）第八十页，共105页。解：如果用p表示缺页率，则有效存取时间不超过2µs可表示为： (1-p)×1µs+p×(0.7×20ms+0.3×8ms+1µs)≤2µs因此可计算出： p≤1/16400≈0.00006第八十一页，共105页。4.7.2内存分配策略和分配算法1、最小物理块数：与计算机的硬件结构有关不同的作业要求不同。如：允许间接寻址：则至少要求3个物理块。 MovA,[B]物理块是否越大越好？第八十二页，共105页。缺页次数Versus物理页框数临界点第八十三页，共105页。4.7.2内存分配策略和分配算法2、页面分配和置换策略。1）固定分配局部置换。缺点：难以确定固定分配的页数.(少：置换率高多：浪费)2）可变分配全局置换3）可变分配局部置换根据进程的缺页率进行页面数调整，进程之间相互不会影响。第八十四页，共105页。3、分配算法

1）平均分配算法2）按进程大小比例分配算法：3）考虑优先权分配算法第八十五页，共105页。4.7.3页面调入策略

1.调入时机：预调：（根据空间局部性）目前：成功率≤50％；适合于首次调入时请求调页：每次调入一页，较费系统开销各有优劣2．从何处调页：对换区：修改过的页被换出时入对换区， 快文件区：稍慢Unix方式对共享页，应判断其是否在内存区。3.页面调入过程第八十六页，共105页。目的：减少对换量，提高系统性能4.8.1最佳置换算法和先进先出算法1、最佳（Optimal）置换算法（理论上的）4.8页置换算法

图4-26利用最佳页面置换算法时的置换图第八十七页，共105页。4.8页面置换算法

2、先进先出（FIFO）页面置换算法

图4-27利用FIFO置换算法时的置换图是否页框数增加就一定会减少缺页数呢？第八十八页，共105页。2、先进先出（FIFO）页面置换算法（续）Referencestring:1,2,3,4,1,2,5,1,2,3,4,53frames(3pagescanbeinmemoryatatimeperprocess)4frames

FIFOReplacement–Belady’sAnomalymoreframeslesspagefaults1231234125349pagefaults10pagefaults12312351245443第八十九页，共105页。FIFOIllustratingBelady’sAnomaly第九十页，共105页。4.8.2最近最久未用LRU置换1、算法描述将“最近的过去”，作为“最近的将来”。图4-28LRU页面置换算法第九十一页，共105页。2.LRU置换算法的硬件支持

1)寄存器为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为R=Rn-1Rn-2Rn-3…R2R1R0

第九十二页，共105页。图4-29某进程具有8个页面时的LRU访问情况第九十三页，共105页。2)栈

图4-30用栈保