第四章存储器的层次结构

第四章存储器的层次结构1第一页，共五十二页，2022年，8月28日

存储器是计算机系统的重要组成部分，虽然内存容量在不断扩大，但内存仍是宝贵资源，如何提高主存储器利用率，并扩充主存，对主存信息实现有效保护是存储器管理主要任务，也是各种不同存储管理方法的目标。2第二页，共五十二页，2022年，8月28日4.1存储器的层次结构寄存器主存辅存计算机系统存储层次示意容量速度/价格3第三页，共五十二页，2022年，8月28日4.1存储器的层次结构寄存器高速缓存主存磁盘缓存磁盘可移动存储介质计算机系统存储层次示意CPU寄存器主存辅存速度最快、价格昂贵，容量小解决CPU与主存速度矛盾CPU直接访问、可执行存储器解决主存与辅存速度矛盾4第四页，共五十二页，2022年，8月28日物理地址和逻辑地址

主存的存储单元以字节为单位编址，每个存储单元都有一个地址与其相对应。这些地址称为主存的物理地址(绝对地址/实地址)；由物理地址所对应的主存空间称为物理地址空间。在多道程序设计系统中，主存中同时存放了多个用户作业。每个用户不可能预先知道其作业存放在主存的具体位置。因此，在用户程序中不能使用主存的物理地址。每个用户可以认为自己作业的程序和数据存放在一组从0地址开始的连续空间中。用户程序中所使用的地址称为逻辑地址(相对地址/虚地址)。所对应的空间称为逻辑地址空间。5第五页，共五十二页，2022年，8月28日4.2程序的装入和链接源程序编译目标模块库…..链接程序装入模块装入程序内存6第六页，共五十二页，2022年，8月28日将一个模块装入内存时，可采用三种方式：

绝对装入方式

可重定位装入方式（静态重定位）

动态运行时装入方式（动态重定位）1.程序的装入7第七页，共五十二页，2022年，8月28日如果在编译时知道程序驻留在主存的具体位置，则编译程序将产生物理地址的目标代码。模块装入后，由于程序中的逻辑地址与实际主存的地址完全相同，故不需要对程序和数据的地址进行修改。指内存分配是在作业运行之前各目标模块连接后，把整个作业一次性全部装入内存，并在作业的整个运行过程中，不允许作业再申请其他内存，或在内存中移动位置。也就是说，内存分配是在作业运行前一次性完成的。绝对装入方式只能将目标模块装入到主存事先指定的固定位置，只适用于单道程序环境。1)绝对装入方式8第八页，共五十二页，2022年，8月28日MoveAX,[2500]543212000210025003000绝对装入方式编译时产生的绝对地址MoveAX,[2500]5432120002100250030000内存空间FFFF9第九页，共五十二页，2022年，8月28日

将逻辑地址变换成物理地址的过程叫做地址重定位。2)可重定位装入方式

在装入作业时,把该作业中的指令地址和数据地址一次性全部转换成物理地址,在作业执行进程中无需再进行地址转换工作。

由于这种地址变换通常是在装入时由装配程序一次性完成的，以后不再改变，故称为静态重定位。物理地址=逻辑地址+程序在内存的首地址优点：无需硬件支持，容易实现。缺点：

1.程序经地址重定位后不能再移动了；

2.程序在内存空间只能连续存储；10第十页，共五十二页，2022年，8月28日032543210832124

13254321100108132244内存空间FFFF++装入程序静态重定位逻辑地址空间11第十一页，共五十二页，2022年，8月28日动态运行时装入是在程序执行期间由地址变换机构动态实现的。动态重定位由软件和硬件相互配合实现。硬件需要一个地址转换机制，该机制由一个基址寄存器和一个地址转换线路组成。物理地址=

逻辑地址+基址寄存器的内容存储管理为作业分配存储区域后,装入程序把作业直接装入到所分配的区域中,并把该主存区域的起始地址存入相应进程的PCB中。当进程被调度占用CPU时,作业所占的主存区域的起始地址也被存放到基址寄存器中。进程执行时，CPU每执行一条指令都会把指令中的逻辑地址与基址寄存器中的值相加得到相应的物理地址,然后按物理地址访问存储器。

3动态运行时装入方式（动态重定位）12第十二页，共五十二页，2022年，8月28日032543210832124

03254321100108132244内存空间FFFF装入程序作业的装入CPU+逻辑地址032100基地址寄存器物理地址

03254321100108132244内存空间FFFF地址转换动态重定位+++13213第十三页，共五十二页，2022年，8月28日若改变了存储区域,作业仍能正确执行,则称程序是可浮动的。采用动态重定位的系统支持程序浮动。而采用静态重定位时,由于被装入主存中的作业信息都已转换为物理地址,作业执行进程中,不再进行地址的转换,故作业执行进程中是不能改变存放位置,即采用静态重定位的系统不支持程序浮动.优点：

1.用户程序在执行过程中在内存可以移动，有利于内存的充分利用；

2.程序不必连续存放在内存中，可以放在不同的区域；缺点：需要附加硬件支持，实行存储管理的软件算法也比较复杂。14第十四页，共五十二页，2022年，8月28日4.2.2程序的链接根据链接时间的不同，可把链接划分为三种方式：

静态链接

装入时动态链接

动态链接

运行时动态链接15第十五页，共五十二页，2022年，8月28日1)

静态链接

静态链接：在程序运行之前，先将各个目标模块及他们所需的库函数，链接成一个完整的装入模块(又称为可执行文件)运行时直接装入内存。这种事先进行链接，以后不再拆开的链接方式称之静态链接。经过编译后得到目标模块,每个模块的起始地址都为0。模块中的地址都是相对于起始地址计算的，在链接成一个装入模块后，程序中被调用模块的起始地址不再是0，此时必须修改被调用模块的逻辑地址，同时每个模块中使用的外部调用符号也相应转变为逻辑地址。

16第十六页，共五十二页，2022年，8月28日模块ACALLB;RETURN;模块BCALLC;RETURN;模块CRETURN;0L-10M-10N-1模块AJSR“L”;RETURN;模块CRETURN;模块BJSR“L+M”;RETURN;0L-1LL+M-1L+ML+M+N-1目标模块装入模块静态链接17第十七页，共五十二页，2022年，8月28日2)

装入时动态链接装入时动态链接：将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的链接方式。由于采用动态链接的各个目标模块是分开存放的，操作系统可以方便地将一个目标模块链接到几个应用模块上。优点:(1)便于修改和更新

(2)便于对目标模块的共享

18第十八页，共五十二页，2022年，8月28日3)

运行时动态链接运行时动态链接：对某些目标模块，当在程序执行中需要该模块时，才对它进行的链接。亦即，在程序的执行过程中，当发现一个被调用模块尚未装入内存时，立即由操作系统去找到该模块并将之装入内存，把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅加快了程序的装入过程，而且可节省大量的内存空间。

19第十九页，共五十二页，2022年，8月28日4.3连续分配方式

把主存中的用户区作为一个连续区域或者分成若干个连续区域进行分配。可分为单一连续分配、固定分区分配、动态分区分配及动态重定位分区分配

。1、单一连续分配管理

最简单的存储管理方式;操作系统占用一部分主存空间,其余的主存空间作为一个连续分区全部分配给一个作业使用,即在任何时刻主存中最多只存有一个作业。

20第二十页，共五十二页，2022年，8月28日单一连续存储管理0abc……作业2作业1装入程序操作系统空闲区子程序集CPU界限寄存器a用户区单一连续存储管理示意图21第二十一页，共五十二页，2022年，8月28日单一连续存储管理操作系统固定区覆盖区初始段处理段输出段可覆盖的段(地址空间大于用户区的作业)123覆盖技术示意图22第二十二页，共五十二页，2022年，8月28日覆盖技术所谓“覆盖”就是一个作业的若干个程序段，或几个作业的某些部分共享同一内存空间。覆盖技术的基本思想是把主存的同一区域分配给一道程序的若干个子程序或数据段。开始时只有程序的一部分装入主存，在其执行过程中根据请求动态的把其它部分装入到该程序原来已经占用过的存储区域中。优点：能更有效的利用内存。缺点：

1.用户难以预知程序的覆盖情况；

2.各作业占用的分区存在碎片；

23第二十三页，共五十二页，2022年，8月28日单一连续存储管理特点:(1)不必考虑作业在主存中的移动问题(2)存储保护比较简单(3)可用于分时系统中采用对(交)换技术实现多个用户作业轮流进入主存操作系统用户区主存作业1作业2磁盘换出1换入2作业对换示意图24第二十四页，共五十二页，2022年，8月28日

交换技术目的，一方面解决主存容量不够大的矛盾，一方面使各分时用户能保证合理的响应时间。所谓交换，就是系统根据需要把主存中暂时不运行的某个(或某些)作业部分或全部移到外存，而把外存中的某个(或某些)作业移到相应的主存区，并使其投入运行。交换的时机通常在以下情况发生：①进程用完时间片或等待输入输出；②作业要求扩充存储而得不到满足时。交换技术25第二十五页，共五十二页，2022年，8月28日

交换技术的关键是设法减少每次交换的信息量。为此，常将作业的副本保留在外存，每次换出时，仅换出那些修改过的信息即可。交换技术也是利用外存来逻辑地扩充主存。它的主要特点是打破了一个程序一旦进入主存便一直运行到结束的限制。思考题：覆盖和交换技术有何联系？1.覆盖技术和交换技术是两种扩充内存的技术。2.覆盖技术主要用于早期的os中，而交换技术在现代os中仍有较强的生命力。3.覆盖技术要求程序员提供一个清晰的覆盖结构，即由程序员来完成把一个程序划分为不同的程序段并规定好执行及覆盖顺序；而交换技术完全由os来实现，整个过程对程序员是透明的。4.覆盖主要是在同一个作业或同一个进程内进行；而交换是在进程或作业之间进行。26第二十六页，共五十二页，2022年，8月28日缺点:(1)CPU利用率比较低(2)存储器得不到充分利用(3)计算机的外围设备利用率不高4.3.2固定分区分配固定分区法

固定分区——预先把主存中的用户区分割成若干个连续区域,每个连续区域称为一个分区,每个分区大小可以相同也可以不同。27第二十七页，共五十二页，2022年，8月28日作业1作业3作业2…….作业对列操作系统主存分区1分区2分区30dcbaCPU当前运行作业所在分区2bc下限寄存器上限寄存器固定分区存储管理示意图28第二十八页，共五十二页，2022年，8月28日区号分区长度起始地址状态18K20KJOBA232K28KJOBB364K60KJOBC4132K124K

0进程B（25K）进程C（36K）主存分配表1.空间的分配和去配作业B（20K）存储空间分配情况四个分区的主存分配表20K28K60K124K256KOS作业A（6K）作业C（64K）作业B（20K）29第二十九页，共五十二页，2022年，8月28日地址转换和存储保护

固定分区存储管理下,作业在执行过程中是不会被改变存储区域的,可采用静态重定位装入方式装入作业。由装入程序把作业中的逻辑地址与分区的下限地址相加,得到相应的物理地址。当一个已经被装入主存的作业占有CPU运行时,进程调度程序将该作业所在分区的下限地址和上限地址分别存储在CPU的下限寄存器和上限寄存器中。CPU执行该作业指令时必须判断:

下限地址<=物理地址<上限地址30第三十页，共五十二页，2022年，8月28日主存空间的利用率提高主存空间利用率的方法:(1)根据经常出现的作业的大小和频率划分分区,尽可能提高各个分区的利用率。(2)划分分区时按分区大小顺序排列。(3)按作业对主存空间的需求量排成多个作业队列,规定每个作业队列中的各作业只能依次装入对应的分区中;分区20abcd……..作业对列1……..……..作业对列2作业对列3OS分区1分区3L1L2L331第三十一页，共五十二页，2022年，8月28日4.3.3动态分区分配

1.动态分区分配的基本概念

因为固定分区主存利用率不高，使用起来不灵活，所以出现了动态分区的管理技术。动态分区原则：存储空间的划分是在装作业时进行的。从可用的自由存储空间内，划出一个大小正好等于作业大小的存储区，并分配给这一作业。OS进程A进程B进程C进程DOS进程A进程B进程COS进程A进程BOS进程A进程A（8K）进程D（124K）进程B（16K）进程C（64K）…32第三十二页，共五十二页，2022年，8月28日1.)空间的分配和去配当有作业完成后释放所占用的存储区。在系统运行的过程中，系统中形成多个空闲的不连续的存储区，称主空闲。33第三十三页，共五十二页，2022年，8月28日

采用动态分区存储管理方式管理存储空间时,主存中已占用分区和空闲区的数目和大小都是可变的。为了实现可变分区存储管理,系统必须设置相应的数据结构,用来描述空闲分区和已分配分区的情况,为系统空间分配提供依据。常用的数据结构有以下两种形式:(1)空闲分区表

(2)空闲分区链34第三十四页，共五十二页，2022年，8月28日(1)空闲分区表

系统设置空闲分区表和已分配分区表,用来描述空闲分区和已分配分区的情况,为系统空间分配提供依据。…….空作业E14KB140KB作业C10KB105KB作业F32KB55KB作业A15KB40标志长度始址已分配分区表……空未分配102KB154KB未分配25KB115KB未分配18KB87标志长度始址空闲分区表35第三十五页，共五十二页，2022年，8月28日(2)空闲分区链

为了实现对空闲分区的分配和链接,在每个分区的起始部分设置一些用于控制分区分配的信息以及用于链接前一个分区的前向指针;在分区的尾部则设置一后向指针,通过前、后向链接指针,可以将所有的空闲分区连接成一个双向链。

0

0N+2N+2后向指针N个字节可用前向指针36第三十六页，共五十二页，2022年，8月28日2分区分配算法分区分配和回收是对空闲区表（或空闲区队列）数据结构进行操作，空闲区表的组织有两种方法：1、按空闲区大小的升序（降序）组织；2、按空闲区首地址升序（降序）组织。根据空闲区表组织的方法的不同，有不同的放置策略，它们是首次适应算法、循环首次适应算法、最佳适应算法、最坏适应算法和快速适应算法。37第三十七页，共五十二页，2022年，8月28日A首次适应分配算法首次适应分配算法的表是按空闲区首地址升序的（即空闲区表是按空闲区首址从小到大）方法组织的。38第三十八页，共五十二页，2022年，8月28日从该空闲区中截取所需大小，修改调整可用表从空闲区表第一表目顺序查找从可用表中移去该表目，调整可用表取下一表项无法分配该空闲区长度≥SIZE？该空闲区长度=SIZE？表目查完？返回分配起始地址否否否是是是首次适应分配算法39第三十九页，共五十二页，2022年，8月28日优点：

1.可以在释放分区时很容易合并相邻的空白区，从而形成较大的空白区；

2.尽可能地利用存储器的低地址部分而保留高地址部分。缺点：

1、搜索次数较大，影响工作效率。

2、低地址部分不断被划分B循环首次适应算法40第四十页，共五十二页，2022年，8月28日C最佳(又称最优)适应分配算法最佳适应分配算法是将申请者放入与其大小最接近的空闲区中。切割后的空闲区最小，若系统中有与申请区大小相等的空闲区，这种算法肯定能将这种空闲区分配给申请者。（首次适应法则不一定）。41第四十一页，共五十二页，2022年，8月28日最佳适应算法的空闲区表按空闲区容量大小升序方法组织。分配时，按申请的大小逐个与空闲区大小进行比较，找到一个满足要求的空闲区，就说明它是最适合的（即最佳的）。优点：1.如果有一个空白区的容量正好满足要求，则它必被选中；2.每次都是选择一个容量最接近的空白区，而使较大的空白区保留。缺点：产生非常小的空白区（碎片）42第四十二页，共五十二页，2022年，8月28日D最坏(也称最差)适应分配算法为了克服最佳适应分配算法把空闲区切割得太小的缺点，人们提出了一种最坏适应分配算法，即每次分配时，总是将最大的空闲区切去一部分分配给请求者，其依据是当一个很大的空闲区被切割了一部分后可能仍是一个较大的空闲区。避免了空闲区越分越小的问题。43第四十三页，共五十二页，2022年，8月28日最坏适应算法的空闲区表是按空闲区大小降序的方法组织的（从大到小的顺序）。分配时总是取表中的第一个表目，若不能满足申请者的要求，则表示系统中无满足要求的空闲区，分配失败；否则，将从该空闲区中分配给申请者，然后修改空闲区的大小，并将它插入到空闲区表的适当位置。优点：产生的空白区可供以后使用。缺点：工作一段时间后，不能满足对较大作业的分配要求。44第四十四页，共五十二页，2022年，8月28日

首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法称为顺序搜索法。E快速适应算法（分类搜索法）

将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空间分区，单独设立一个空闲分区链表。优点：

（1）查找效率高；（2）保留大的分区，不产生碎片；缺点：（1）分区归还主存时算法复杂；（2）浪费严重；45第四十五页，共五十二页，2022年，8月28日总结：1.固定式分区和可变式分区有如下三个优点：1）有助于多道程序设计；2）它不需过多的硬件支持，只需界限地址寄存器用于存储保护；3）所采用的算法大多比较简单，容易实现。2.固定式分区和可变式分区有如下缺点：1）产生碎片，因而降低了存储器的利用率；2）无法扩充主存容量。46第四十六页，共五十二页，2022年，8月28日A、将R合并到f1，f1.addr;f1.size+r.sizeB、将R合并到f2,r.addr;r.size+f2.sizeC、f1、R、f2合并到f1,f1.addr;

f1.size+r.size+f2.size撤消f2空闲区D、r作为一个空闲区，并插入到空闲区表的适当位置。3空闲释放区与空闲区相邻有四种情况47第四十七页，共五十二页，2022年，8月28日碎片(零头)就是不能分配给用户进程的、无效的空闲内存空间。在什么情况下系统要紧凑：

1）当某个分区的作业一完成，就立即紧凑，内存仅保留一个空白区；

2）当为某个作业分配分区而内存又没有足够大的分区，但各空闲分区容量总和满足该作业的需求才进行紧凑。优点：消除了碎片，提高了存储器的利用率。缺点：需要硬件支持,增加计算机的成本，降低了计算机的速度。4.3.6可重定位分区分配可重定位分区分配是解决碎片问题的简单而有效的办法。其基本思想是移动所有被分配了的分区，使之成为一个连续的区域，而把碎片集中成一个较大的空白区。这个移动的过程叫做“拼接”或“紧凑”。48第四十八页，共五十二页，2022年，8月28日采用移动技术时应该尽量减少移动的作业数和信息量,以降低系统的开销,提高系统的效率,改变作业装入主存的方式减少移动的作业数和信息量。

移动技术为作业执行进程中扩充主存空间提供方便,一道作业在执行中要求增加主存量时,只要适当移动邻近的作业就可增加它所占的分区长度。采用移动技术时必须注意以下几点:(1)移动会增加系统开销;(2)移动是有条件的;

OSJ1J2J3J4空闲区OSJ1J3空闲区J4J249第四十九页，共五十二页，2022年，8月28日1.最佳适应算法的空白区是（）

A.按大小递减顺序排列B.按大小递增顺序排列

C.按地址由小到大排列D.按地址由大到小排列

2.存储管理方案中，（）可采用覆盖技术。

A.单一连续区存储管理B.可变分区存储管理

C.段式存储管理D.段页式存储管理

3.在可变式分区分配方案中,某一作业完成后,系统收回其主存空间并与相邻空闲去合并,为此需修改空闲区表,造成空闲区数减1的情况是（）

A.无上邻空闲区也无下邻空闲区B.有上邻空闲区但无下邻空闲区

C.有下邻空闲区但无上邻空闲区D.有上邻