操作系统第四版第四章

第四章存储器管理渤海大学2014-2015（1）学期第四章存储器管理4.1存储器的层次结构4.2程序的装入和链接4.3连续分配方式4.4对换（Swapping）（自学）4.5基本分页存储管理方式4.6基本分段存储管理方式4.1层次的存储器结构4.1.1多级存储器结构寄存器高速缓存主存磁盘缓存磁盘可移动存储设备CPU寄存器主存辅存容量速度4.1层次的存储器结构4.1.2主存储器与寄存器1.主存储器2.寄存器主存储器是计算机系统中一个主要部件，用于保存运行时的程序和数据，其容量可达是MB到数GB。其速度远低于CPU执行指令的速度，高于外存速度。寄存器访问速度最快，但价格昂贵，但容量小。4.1层次的存储器结构4.1.3高速缓存和磁盘缓存1.高速缓存2.磁盘缓存其容量大于或远大于寄存器，而比内存约小两到三个数量级左右，从几十KB到几MB,访问速度快于主存储器。磁盘的I/O速度远低于对主存的访问速度，因此将频繁使用的一部分磁盘数据和信息，暂时存放在磁盘的缓存中，可以减少访问磁盘的次数。磁盘缓存本身不是一种实际存在的存储介质，它依托于固定磁盘，是利用主存的存储空间，来暂存从磁盘中读出（或写入）的信息。4.2程序的装入和链接图4-1对用户程序的处理步骤库链接程序装入模块装入程序编译程序产生的目标模块第一步第二步第三步内存…4-24.2.1程序的装入1.绝对装入方式(AbsoluteLoadingMode)程序中所使用的绝对地址，既可在编译或汇编时给出，也可由程序员直接赋予。但在由程序员直接给出绝对地址时，不仅要求程序员熟悉内存的使用情况，而且一旦程序或数据被修改后，可能要改变程序中的所有地址。因此，通常是宁可在程序中采用符号地址，然后在编译或汇编时，再将这些符号地址转换为绝对地址。2.可重定位装入方式(RelocationLoadingMode)图4-2作业装入内存时的情况LOAD1,2500365LOAD1,2500365100001100012500150005000250010000作业地址空间内存空间3.动态运行时装入方式(DenamleRun-timeLoading)动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址都仍是相对地址。4.2.2程序的链接1.静态链接方式(StaticLinking)图4-3程序链接示意图模块ACALLB；Return；0L－1模块BCALLC；Return；0M－1模块CReturn；0N－10模块AJSR“L”Return；L－1模块BJSR“L＋M”Return；LL＋M－1L＋ML＋M＋N－1模块CReturn；(a)目标模块(b)装入模块在将这几个目标模块装配成一个装入模块时，须解决以下两个问题：(1)对相对地址进行修改。(2)变换外部调用符号。2.装入时动态链接(LoadtimeDynamicLinking)装入时动态链接方式有以下优点：(1)便于修改和更新。(2)便于实现对目标模块的共享。3.运行时动态链接(Run-timeDynamicLinking)近几年流行起来的运行时动态链接方式，是对上述在装入时链接方式的一种改进。这种链接方式是将对某些模块的链接推迟到执行时才执行，亦即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。4.3连续分配方式4.3.1单一连续分配这是最简单的一种存储管理方式，但只能用于单用户、单任务的操作系统中。采用这种存储管理方式时，可把内存分为系统区和用户区两部分，系统区仅提供给OS使用，通常是放在内存的低址部分；用户区是指除系统区以外的全部内存空间，提供给用户使用。4.3.2固定分区分配1.划分分区的方法(1)分区大小相等，即使所有的内存分区大小相等。(2)分区大小不等。2.内存分配图4-4固定分区使用表4.3.3动态分区分配1.分区分配中的数据结构(1)空闲分区表。(2)空闲分区链。图4-5空闲链结构前向指针N＋20N个字节可用后向指针N＋200K15K38K48K68K80K110K120K空闲区表已分配区表始址长度标志15K23K未分配48K20K未分配80K30K未分配空空始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ4空分区分配表：80K5KJ585K25K未分配85K85K13KJ698K12K未分配98K2.分区分配算法(1)首次适应算法FF(2)循环首次适应算法NFF该算法是由首次适应算法演变而成的。(3)最佳适应算法BF(4)最坏适应算法WF(5)快速适应算法QF,又称为分类搜索法0K15K38K48K68K80K110K120K空闲区表已分配区表始址长度标志15K23K未分配48K20K未分配80K30K未分配空空始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ4空分区分配表：15K5KJ520K18K未分配20K20K13KJ633K5K未分配33K首次适应算法FF0K15K38K48K68K80K110K120K空闲区表已分配区表始址长度标志15K23K未分配48K20K未分配80K30K未分配空空始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ4空分区分配表：15K5KJ520K18K未分配20K48K13KJ661K7K未分配61K循环首次适应算法NFF0K15K38K48K68K80K110K120K空闲区表已分配区表始址长度标志15K23K未分配48K20K未分配80K30K未分配空空始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ4空分区分配表：48K5KJ553K15K未分配53K53K13KJ666K2K未分配66K最佳适应算法BF3.分区分配操作1)分配内存从头开始查表检索完否？m.size＞u.size?m.size－u.size≤size?从该分区中划出u.size大小的分区将该分区分配给请求者修改有关数据结构返回返回继续检索下一个表项将该分区从链中移出YNNYYN内存分配流程2)回收内存图4-7内存回收时的情况4.3.61.图4-8紧凑的示意操作系统用户程序1用户程序310KB30KB用户程序614KB用户程序926KB操作系统用户程序1用户程序3用户程序6用户程序980KB(a)紧凑前(b)紧凑后2.图4-9动态重定位示意图LOAD1,25003650100250050002500相对地址10000重定位寄存器＋LOAD1,250036510000101001250015000作业J处理机一侧存储器一侧主存3.动态重定位分区分配算法图4-10动态分区分配算法流程图请求分配u.size分区检索空闲分区链(表)找到大于u.size的可用区否?按动态分区方式进行分配修改有关的数据结构返回分区号及首批空闲分区总和≥u.size?进行紧凑形成连续空闲区修改有关的数据结构否是无法分配返回否4.4对换(Swapping)1.对换的引入所谓“对换”，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据，调入内存。对换是提高内存利用率的有效措施。2.对换空间的管理为了能对对换区中的空闲盘块进行管理，在系统中应配置相应的数据结构，以记录外存的使用情况。其形式与内存在动态分区分配方式中所用数据结构相似，即同样可以用空闲分区表或空闲分区链。在空闲分区表中的每个表目中应包含两项，即对换区的首址及其大小，它们的单位是盘块号和盘块数。3.进程的换出与换入(1)进程的换出。每当一进程由于创建子进程而需要更多的内存空间，但又无足够的内存空间等情况发生时，系统应将某进程换出。其过程是：系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动盘块，将该进程的程序和数据传送到磁盘的对换区上。若传送过程未出现错误，便可回收该进程所占用的内存空间，并对该进程的进程控制块做相应的修改。(2)进程的换入。系统应定时地查看所有进程的状态，从中找出“就绪”状态但已换出的进程，将其中换出时间(换出到磁盘上)最久的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止。4.5基本分页存储管理方式4.5.1页面与页表1.页面1)分页存储管理，是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号，从0开始，如第0页、第1页等。相应地，也把内存空间分成与页面相同大小的若干个存储块，称为(物理)块或页框(frame)，也同样为它们加以编号，如0＃块、1＃块等等。在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”。2)在分页系统中的页面其大小应适中。页面若太小，一方面虽然可使内存碎片减小，从而减少了内存碎片的总空间，有利于提高内存利用率，但另一方面也会使每个进程占用较多的页面，从而导致进程的页表过长，占用大量内存；此外，还会降低页面换进换出的效率。然而，如果选择的页面较大，虽然可以减少页表的长度，提高页面换进换出的速度，但却又会使页内碎片增大。因此，页面的大小应选择得适中，且页面大小应是2的幂，通常为512B~8KB。分页管理中页与页框的对应关系示意图2.地址结构分页地址中的地址结构如下：页号P位移量W3112110对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得：MODLAdLAINTP][3.页表图4-11页表的作用用户程序0页1页2页3页4页5页…n页页表页号块号02132638495……内存0123456789104.5.2地址变换机构1.基本的地址变换机构图4-13分页系统的地址变换机构页表寄存器页表始址页表长度＞页号(3)页内地址＋逻辑地址L越界中断1块号b页表页号012物理地址3•例如指令LOAD1,2500的地址变换过程如下：•把虚拟地址2500转换成页号P=2，位移量W=452；•如果页号2大于页表大小，则中断；否则继续；•页号2与页表起址1000运算（1000+2*20，设页描述子大小为20）得到页描述子地址为1040；•从页描述子中读取块号8；•根据页描述子的“存取控制”判断该指令是否被允许访问内存，如果不允许，则中断；否则继续；•块号8与位移量452运算（8*1024+452=8644，1024为页面大小）得到物理地址8644；•把数字1写进内存地址8644单元中。2.图4-13具有快表的地址变换机构页表寄存器页表始址页表长度＞页号页内地址＋逻辑地址L越界中断块号b页表页号页号输入寄存器块号bb快表d物理地址4.5.3两级和多级页表现代的大多数计算机系统，都支持非常大的逻辑地址空间(232~264)。在这样的环境下，页表就变得非常大，要占用相当大的内存空间。例如，对于一个具有32位逻辑地址空间的分页系统，规定页面大小为4KB即212B，则在每个进程页表中的页表项可达1兆个之多。又因为每个页表项占用一个字节，故每个进程仅仅其页表就要占用1MB的内存空间，而且还要求是连续的。可以采用这样两个方法来解决这一问题：①采用离散分配方式来解决难以找到一块连续的大内存空间的问题：②只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。1.两级页表(Two-LevelPageTable)逻辑地址结构可描述如下：图4-14两级页表结构101110780121742n第0页页表146…012…1023第1页页表11411501…1023外部页表01234567……1141151468第n页页表146