第四章-存储器管理1

第四章存储器管理2012年4月23日存储器管理存储器的层次结构程序的装入和链接连续分配方式基本分页存储管理方式基本分段存储管理方式虚拟存储器的基本概念请求分页存储管理方式页面置换算法请求分段存储管理方式存储器的层次结构多级存储结构主存储器与寄存器高速缓存和磁盘缓存图4-1对用户程序的处理步骤库链接程序装入模块装入程序编译程序产生的目标模块第一步第二步第三步内存…程序的装入和链接程序的装入绝对装入方式(AbsoluteLoadingMode)可重定位装入方式(RelocationLoadingMode)动态运行时装入方式(DenamleRun-timeLoading)绝对装入方式程序中所使用的绝对地址，既可在编译或汇编时给出，也可由程序员直接赋予。但在由程序员直接给出绝对地址时，不仅要求程序员熟悉内存的使用情况，而且一旦程序或数据被修改后，可能要改变程序中的所有地址。因此，通常是宁可在程序中采用符号地址，然后在编译或汇编时，再将这些符号地址转换为绝对地址。绝对装入方式特点只能将目标装入到内存中事先指定的地方。装入模块装入内存后，由于程序中的逻辑地址与实际地址完全相同，故不须对程序和数据的地址进行修改。多道程序环境下，编译程序不可能预知所编译的目标模块在内存的何处。因此，只适用于单道系统。问题：如果想把装入模块装入到内存的任何一个位置，应该怎么做？图4-2作业装入内存时的情况LOAD1,2500365LOAD1,2500365100001100012500150005000250010000作业地址空间内存空间可重定位装入方式可重定位装入方式特点：在装入时对目标程序中指令和数据的修改过程通常进行重定位。将装入模块装入到内存中任何允许的位置。不允许程序运行时在内存中移动位置。问题：但是，程序在内存中的位置可能经常改变，此时应采取什么措施？动态运行时装入方式动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址都仍是相对地址。程序的链接静态链接方式(StaticLinking)装入时动态链接(LoadtimeDynamicLinking)运行时动态链接(Run-timeDynamicLinking)静态链接方式模块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)装入模块静态链接方式在将这几个目标模块装配成一个装入模块时，须解决以下两个问题：对相对地址进行修改变换外部调用符号静态链接方式特点：事先进行连接，以后不再拆开目标模块。无法修改和更新目标模块。如果要修改或更新其中的某个目标模块，则要求重新打开装入模块。无法实现对目标模块的共享。装入时动态链接用户源程序经编译后所得的目标模块，是在装入时边装入边连接的。装入目标模块时，修改目标模块的相对地址。装入时动态链接特点：便于修改和更新各个模块是分开存放的。便于实现对目标模块的共享很容易将一个模块连接到多个模块。运行时动态链接这种链接方式是将对某些模块的链接推迟到执行时才执行。在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。运行时动态链接特点：容易实现程序局部性操作。提高内存的利用率。提高程序的执行效率。连续分配方式连续分配方式，是指为一个用户分配一个连续的内存空间。分类：单一连续分配固定分区分配动态分区分配可重定位分区分配对换(Swapping)单一连续分配这是最简单的一种存储管理方式。只能用于单用户、单任务的操作系统中。采用这种存储管理方式时，可把内存分为系统区和用户区两部分：系统区仅提供给OS使用，通常是放在内存的低地址部分；用户区是指除系统区以外的全部内存空间，提供给用户使用。单一连续分配特点：仅适用于单用户、单任务操作系统；内存空间连续分配机器由一个用户独占，不可能存在其他用户的干扰。固定分区分配固定分区分配是最简单的一种可运行多道程序的存储管理方式；将内存用户空间划分为若干个固定大小的区域，在每个区域中只装入一道作业，便允许有几道作业并发执行。当有一空闲分区时，便可以再从外存的后备作业队列中选择一个适当大小的作业装入该分区。固定分区分配划分分区的方法分区大小相等，即使所有的内存分区大小相等。缺点：缺乏灵活性。优点：用于利用一台计算机去控制多个相同对象的场合。分区大小不等。固定分区分配内存分配为了便于内存分配，通常将分区按大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态（已分配）。固定分区分配图4-4固定分区使用表固定分区分配特点：内存管理比较简单。满足少量的进程的需要。内存的利用率低。动态分区分配是根据进程的实际需要，动态地分配内存空间。分区分配时，应考虑：所采用的数据结构分区分配算法分区的分配与回收分区分配中的数据结构空闲分区表空闲分区链分区分配中的数据结构空闲分区表空闲分区序号分区始址/KB分区大小/KB1302025040…………………………n分区分配中的数据结构空闲分区链前向指针N＋20N个字节可用后向指针N＋20分区分配算法首次适应算法FF循环首次适应算法最佳适应算法最坏适应算法快速适应算法分区分配操作分配内存u.size:请求的分区大小m.size:每个空闲分区大小size:事先规定的不再切割的剩余分区的大小回收内存分配内存从头开始查表检索完否？m.size＞u.size?m.size－u.size≤size?从该分区中划出u.size大小的分区将该分区分配给请求者修改有关数据结构返回返回继续检索下一个表项将该分区从链中移出YNNYYN图4-6内存分配流程回收内存可重定位分区分配动态重定位的引入在连续分配方式中，必须把一个系统或用户程序装入一个连续的内存空间。如果出现以下情况，该怎么办？可重定位分区分配操作系统用户程序1用户程序310KB30KB用户程序614KB用户程序926KB操作系统用户程序1用户程序3用户程序6用户程序980KB(a)紧凑前(b)紧凑后可重定位分区分配动态重定位的实现LOAD1,25003650100250050002500相对地址10000重定位寄存器＋LOAD1,250036510000101001250015000作业J处理机一侧存储器一侧主存图4-9动态重定位示意图可重定位分区分配动态重定位分区分配算法算法与动态分区分配算法基本上相同。差别：在这种分配算法中，增加了紧凑的功能，通常，在找不到足够大的空间分区来满足需求时进行紧凑。具体操作如下：请求分配u.size分区检索空闲分区链(表)找到大于u.size的可用区否?按动态分区方式进行分配修改有关的数据结构返回分区号及首批空闲分区总和≥u.size?进行紧凑形成连续空闲区修改有关的数据结构否是无法分配返回否动态重定位分区分配算法图4-10动态分区分配算法流程图例题：某一存储器系统采用动态分区方案，设当前的空白区如下表所示：空白区号起始地址（KB）空白区容量（KB）状态15100可用212020可用3310256可用4102448可用例题：现有5个作业J1，J2，J3，J4，J5，他们分别需要20,42,120,130,18KB，若采用最先适应算法，以怎样的次序可以将这五个作业都装入主存，并给出空白区表。空白区号起始地址（KB）空白区容量（KB）状态15100可用212020可用3310256可用4102448可用例题2：在某系统中，采用固定分区存储管理方式，内存分区的情况如图所示。现有大小为15KB、53KB、110KB的多个作业要求进入内存。试画出它们进入内存后的空间分配情况，并说明主存浪费有多大？04070180512OS区域对换(Swapping)对换的引入对换空间的管理进程的换出与换入对换(Swapping)对换的引入所谓“对换”，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据，调入内存。对换是提高内存利用率的有效措施。对换(Swapping)对换空间的管理为了能对对换区中的空闲盘块进行管理，在系统中应配置相应的数据结构，以记录外存的使用情况。其形式与内存在动态分区分配方式中所用数据结构相似，即同样可以用空闲分区表或空闲分区链。在空闲分区表中的每个表目中应包含两项，即对换区的首址及其大小，它们的单位是盘块号和盘块数。对换(Swapping)进程的换出每当一进程由于创建子进程而需要更多的内存空间，但又无足够的内存空间等情况发生时，系统应将某进程换出。其过程是：系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动盘块，将该进程的程序和数据传送到磁盘的对换区上。若传送过程未出现错误，便可回收该进程所占用的内存空间，并对该进程的进程控制块做相应的修改。对换(Swapping)进程的换入系统应定时地查看所有进程的状态，从中找出“就绪”状态但已换出的进程，将其中换出时间(换出到磁盘上)最久的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止。连续分配方式特点:将把内存连续地分配，会形成许多“碎片”。虽然使用“紧凑”技术，对形成的“碎片”进行拼接，但须为之付出很大的开销。适用于比较简单的内存管理场合。问题：如果允许将一个进程直接分散地装入到许多不相邻的分区中，则无须再进行”紧凑”，那应该如何实现？离散分配方式分页存储管理方式分配的基本单位是页分段存储管理方式分配的基本单位是段段页式存储管理方式分配的基本单位是”段页“基本分页存储管理方式页面与页表地址变化机构*两级或多级页表页面与页表页面页面和物理块分页存储管理，是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号，从0开始，如第0页、第1页等。相应地，也把内存空间分成与页面相同大小的若干个存储块，称为(物理)块或页框(frame)，也同样为它们加以编号，如0＃块、1＃块等等。在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”。页面与页表页面在分页系统中的页面其大小应适中。页面若太小，一方面虽然可使内存碎片减小，从而减少了内存碎片的总空间，有利于提高内存利用率，但另一方面也会使每个进程占用较多的页面，从而导致进程的页表过长，占用大量内存；此外，还会降低页面换进换出的效率。然而，如果选择的页面较大，虽然可以减少页表的长度，提高页面换进换出的速度，但却又会使页内碎片增大。因此，页面的大小应选择得适中，且页面大小应是2的幂，通常为512B~8KB。页面与页表地址结构分页地址中的地址结构如下：页号P位移量W3112110对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得：MODLAdLAINTP][页面与页表地址计算公式：逻辑地址=p(页号).d(页内位移)物理地址=f(页帧号).d(页内位移)p=逻辑地址/页面大小d=逻辑地址-p*页面大小页面与页表页表用户程序0页1页2页3页4页5页…n页页表页号块号02132638495……内存012345678910地址变换机构为了能将用户地址空间