第四章—A存储器的层次结构

nullnull*学习重点和难点： 1 存储管理的基本概念 2 各种存储管理的基本思想、实现方法和技术 3 地址空间和物理空间的区别 4 虚拟存储器的概念和方法 5 请求分页/分段存储管理方式 6页面置换算法第四章 存储器管理null* 存储器是计算机系统的重要组成部分，虽然内存容量在不断扩大，但内存仍是宝贵资源，如何提高主存储器利用率，并扩充主存，对主存信息实现有效保护是存储器管理主要任务，也是各种不同存储管理方法的目标。 null*4.1 存储器的层次结构null*4.1 存储器的层次结构CPU寄存器主存辅存速度最快、价格昂贵，容量小解决CPU与主存速度矛盾CPU直接访问、可执行存储器解决主存与辅存速度矛盾null*物理地址和逻辑地址 主存的存储单元以字节为单位编址，每个存储单元都有一个地址与其相对应。这些地址称为主存的物理地址(绝对地址/实地址)；由物理地址所对应的主存空间称为物理地址空间。 在多道程序 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 系统中，主存中同时存放了多个用户作业。每个用户不可能预先知道其作业存放在主存的具体位置。因此，在用户程序中不能使用主存的物理地址。每个用户可以认为自己作业的程序和数据存放在一组从0地址开始的连续空间中。用户程序中所使用的地址称为逻辑地址(相对地址/虚地址)。所对应的空间称为逻辑地址空间。4.2 程序的装入和链接*4.2 程序的装入和链接null*将一个模块装入内存时，可采用三种方式： 绝对装入方式 可重定位装入方式（静态重定位 ） 动态运行时装入方式（动态重定位） 1.程序的装入null* 如果在编译时知道程序驻留在主存的具体位置，则编译程序将产生物理地址的目标代码。模块装入后，由于程序中的逻辑地址与实际主存的地址完全相同，故不需要对程序和数据的地址进行修改。 指内存分配是在作业运行之前各目标模块连接后，把整个作业一次性全部装入内存，并在作业的整个运行过程中，不允许作业再申请其他内存，或在内存中移动位置。也就是说，内存分配是在作业运行前一次性完成的。 绝对装入方式只能将目标模块装入到主存事先指定的固定位置，只适用于单道程序环境。 1)绝对装入方式null*绝对装入方式编译时产生的绝对地址null* 将逻辑地址变换成物理地址的过程叫做地址重定位。 2)可重定位装入方式 在装入作业时,把该作业中的指令地址和数据地址一次性全部转换成物理地址,在作业执行进程中无需再进行地址转换工作。 由于这种地址变换通常是在装入时由装配程序一次性完成的，以后不再改变，故称为静态重定位。 物理地址=逻辑地址+程序在内存的首地址 优点：无需硬件支持，容易实现。 缺点： 1.程序经地址重定位后不能再移动了； 2.程序在内存空间只能连续存储；null*++装入程序静态重定位逻辑地址空间null* 动态运行时装入是在程序执行期间由地址变换机构动态实现的。 动态重定位由软件和硬件相互配合实现。硬件需要一个地址转换机制，该机制由一个基址寄存器和一个地址转换线路组成。 物理地址= 逻辑地址+基址寄存器的内容 存储管理为作业分配存储区域后,装入程序把作业直接装入到所分配的区域中,并把该主存区域的起始地址存入相应进程的PCB中。当进程被调度占用CPU时,作业所占的主存区域的起始地址也被存放到基址寄存器中。进程执行时，CPU每执行一条指令都会把指令中的逻辑地址与基址寄存器中的值相加得到相应的物理地址,然后按物理地址访问存储器。 3 动态运行时装入方式（动态重定位）null*装入程序作业的装入地址转换动态重定位+++132null* 若改变了存储区域,作业仍能正确执行,则称程序是可浮动的。采用动态重定位的系统支持程序浮动。而采用静态重定位时,由于被装入主存中的作业信息都已转换为物理地址,作业执行进程中,不再进行地址的转换,故作业执行进程中是不能改变存放位置,即采用静态重定位的系统不支持程序浮动. 优点： 1.用户程序在执行过程中在内存可以移动，有利于内存的充分利用； 2.程序不必连续存放在内存中，可以放在不同的区域； 缺点： 需要附加硬件支持，实行存储管理的软件算法也比较复杂。 null*4.2.2 程序的链接根据链接时间的不同，可把链接划分为三种方式： 静态链接 装入时动态链接 动态链接 运行时动态链接 null*1) 静态链接 静态链接：在程序运行之前，先将各个目标模块及他们所需的库函数，链接成一个完整的装入模块(又称为可执行文件)运行时直接装入内存。这种事先进行链接，以后不再拆开的链接方式称之静态链接。 经过编译后得到目标模块,每个模块的起始地址都为0。模块中的地址都是相对于起始地址计算的，在链接成一个装入模块后，程序中被调用模块的起始地址不再是0，此时必须修改被调用模块的逻辑地址，同时每个模块中使用的外部调用符号也相应转变为逻辑地址。 null*模块A CALL B; RETURN;模块B CALL C; RETURN;模块C RETURN;0L-10M-10N-1模块A JSR “L”; RETURN;模块C RETURN;模块B JSR “L+M”; RETURN;0L-1LL+M-1L+ML+M+N-1目标模块装入模块静态链接null*2) 装入时动态链接 装入时动态链接：将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的链接方式。 由于采用动态链接的各个目标模块是分开存放的，操作系统可以方便地将一个目标模块链接到几个应用模块上。 优点: (1) 便于修改和更新 (2) 便于对目标模块的共享 null*3) 运行时动态链接 运行时动态链接：对某些目标模块，当在程序执行中需要该模块时，才对它进行的链接。亦即，在程序的执行过程中，当发现一个被调用模块尚未装入内存时，立即由操作系统去找到该模块并将之装入内存，把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅加快了程序的装入过程，而且可节省大量的内存空间。 null*4.3 连续分配方式 把主存中的用户区作为一个连续区域或者分成若干个连续区域进行分配。 可分为单一连续分配、固定分区分配、动态分区分配及动态重定位分区分配 。 1、单一连续分配管理 最简单的存储管理方式;操作系统占用一部分主存空间,其余的主存空间作为一个连续分区全部分配给一个作业使用,即在任何时刻主存中最多只存有一个作业。 null*单一连续存储管理0abc单一连续存储管理示意图null*单一连续存储管理覆盖技术示意图null*覆盖技术 所谓“覆盖”就是一个作业的若干个程序段，或几个作业的某些部分共享同一内存空间。 覆盖技术的基本思想是把主存的同一区域分配给一道程序的若干个子程序或数据段。开始时只有程序的一部分装入主存，在其执行过程中根据请求动态的把其它部分装入到该程序原来已经占用过的存储区域中。 优点：能更有效的利用内存。 缺点： 1.用户难以预知程序的覆盖情况； 2.各作业占用的分区存在碎片； null*单一连续存储管理特点: (1)不必考虑作业在主存中的移动问题 (2)存储保护比较简单 (3)可用于分时系统中 采用对(交)换技术实现 多个用户作业轮流进 入主存作业对换示意图null* 交换技术目的，一方面解决主存容量不够大的矛盾，一方面使各分时用户能保证合理的响应时间。所谓交换，就是系统根据需要把主存中暂时不运行的某个(或某些)作业部分或全部移到外存，而把外存中的某个(或某些)作业移到相应的主存区，并使其投入运行。 交换的时机通常在以下情况发生： ①进程用完时间片或等待输入输出； ②作业要求扩充存储而得不到满足时。交换技术null* 交换技术的关键是设法减少每次交换的信息量。为此，常将作业的副本保留在外存，每次换出时，仅换出那些修改过的信息即可。 交换技术也是利用外存来逻辑地扩充主存。它的主要特点是打破了一个程序一旦进入主存便一直运行到结束的限制。 思考题：覆盖和交换技术有何联系？1.覆盖技术和交换技术是两种扩充内存的技术。2.覆盖技术主要用于早期的os中，而交换技术在现代os中仍有较强的生命力。 3.覆盖技术要求程序员提供一个清晰的覆盖结构，即由程序员来完成把一个程序划分为不同的程序段并规定好执行及覆盖顺序；而交换技术完全由os来实现，整个过程对程序员是透明的。 4.覆盖主要是在同一个作业或同一个进程内进行；而交换是在进程或作业之间进行。 null*缺点: (1)CPU利用率比较低 (2)存储器得不到充分利用 (3)计算机的外围设备利用率不高4.3.2 固定分区分配固定分区法 固定分区——预先把主存中的用户区分割成若 干个连续区域,每个连续区域称为一个分区,每个分区大小可以相同也可以不同。null*上限寄存器固定分区存储管理示意图null*进程B（25K）进程C（36K）主存分配 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 1.空间的分配和去配作业B（20K）存储空间分配情况四个分区的主存分配表20K28K60K124K256KOS作业A（6K）作业C（64K）作业B（20K）null*地址转换和存储保护 固定分区存储管理下,作业在执行过程中是不会被改变存储区域的, 可采用静态重定位装入方式装入作业。 由装入程序把作业中的逻辑地址与分区的下限地址相加,得到相应的物理地址。当一个已经被装入主存的作业占有CPU运行时,进程调度程序将该作业所在分区的下限地址和上限地址分别存储在CPU的下限寄存器和上限寄存器中。 CPU执行该作业指令时必须判断: 下限地址<=物理地址<上限地址null*主存空间的利用率提高主存空间利用率的方法: (1)根据经常出现的作业的大小和频率划分分区,尽可能提高各个分区的利用率。 (2)划分分区时按分区大小顺序排列。 (3)按作业对主存空间的需求量排成多个作业队列,规定每个作业队列中的各作业只能依次装入对应的分区中;分区20abcd作业对列1作业对列2作业对列3OS分区1分区3L1L2L3null*4.3.3 动态分区分配 1.动态分区分配的基本概念 因为固定分区主存利用率不高，使用起来不灵活，所以出现了动态分区的管理技术。 动态分区原则：存储空间的划分是在装作业时进行的。从可用的自由存储空间内，划出一个大小正好等于作业大小的存储区，并分配给这一作业。OS进程A进程B进程C进程DOS进程A进程B进程COS进程A进程BOS进程Anull*1.) 空间的分配和去配 当有作业完成后释放所占用的存储区。 在系统运行的过程中，系统中形成多个空闲的不连续的存储区，称主空闲。null* 采用动态分区存储管理方式管理存储空间时,主存中已占用分区和空闲区的数目和大小都是可变的。为了实现可变分区存储管理,系统必须设置相应的数据结构,用来描述空闲分区和已分配分区的情况,为系统空间分配提供依据。常用的数据结构有以下两种形式: (1)空闲分区表 (2)空闲分区链 null*(1)空闲分区表 系统设置空闲分区表和已分配分区表,用来描述空闲分区和已分配分区的情况,为系统空间分配提供依据。null*(2)空闲分区链 为了实现对空闲分区的分配和链接,在每个分区的起始部分设置一些用于控制分区分配的信息以及用于链接前一个分区的前向指针;在分区的尾部则设置一后向指针,通过前、后向链接指针,可以将所有的空闲分区连接成一个双向链。null*2 分区分配算法 分区分配和回收是对空闲区表（或空闲区队列）数据结构进行操作，空闲区表的组织有两种方法： 1、按空闲区大小的升序（降序）组织； 2、按空闲区首地址升序（降序）组织。 根据空闲区表组织的方法的不同，有不同的放置策略，它们是首次适应算法、循环首次适应算法、最佳适应算法、最坏适应算法和快速适应算法。 null*A 首次适应分配算法 首次适应分配算法的表是按空闲区首地址升序的（即空闲区表是按空闲区首址从小到大）方法组织的。 null*从该空闲区中截取所需 大小，修改调整可用表从空闲区表第一 表目顺序查找从可用表中移去该 表目，调整可用表取下一表项无法分配该 空闲区 长度≥SIZE？ 该 空闲区 长度=SIZE？ 表目查完？返回分配起始地址否否否是是是首次适应分配算法null*优点： 1.可以在释放分区时很容易合并相邻的空白区，从而形成较大的空白区； 2.尽可能地利用存储器的低地址部分而保留高地址部分。 缺点： 1、搜索次数较大，影响工作效率。 2、低地址部分不断被划分 B 循环首次适应算法null*C 最佳(又称最优)适应分配算法 最佳适应分配算法是将申请者放入与其大小最接近的空闲区中。切割后的空闲区最小，若系统中有与申请区大小相等的空闲区，这种算法肯定能将这种空闲区分配给申请者。（首次适应法则不一定）。 null* 最佳适应算法的空闲区表按空闲区容量大小升序方法组织。 分配时，按申请的大小逐个与空闲区大小进行比较，找到一个满足要求的空闲区，就说明它是最适合的（即最佳的）。 优点： 1.如果有一个空白区的容量正好满足要求，则它必被选中； 2.每次都是选择一个容量最接近的空白区，而使较大的空白区保留。 缺点：产生非常小的空白区（碎片） null*D 最坏(也称最差)适应分配算法 为了克服最佳适应分配算法把空闲区切割得太小的缺点，人们提出了一种最坏适应分配算法，即每次分配时，总是将最大的空闲区切去一部分分配给请求者，其依据是当一个很大的空闲区被切割了一部分后可能仍是一个较大的空闲区。避免了空闲区越分越小的问题。null* 最坏适应算法的空闲区表是按空闲区大小降序的方法组织的（从大到小的顺序）。 分配时总是取表中的第一个表目，若不能满足申请者的要求，则表示系统中无满足要求的空闲区，分配失败；否则，将从该空闲区中分配给申请者，然后修改空闲区的大小，并将它插入到空闲区表的适当位置。 优点：产生的空白区可供以后使用。 缺点：工作一段时间后，不能满足对较大作业的分配要求。null* 首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法称为顺序搜索法。E 快速适应算法（分类搜索法） 将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空间分区，单独设立一个空闲分区链表。优点： （1）查找效率高； （2）保留大的分区，不产生碎片； 缺点： （1）分区归还主存时算法复杂； （2）浪费严重；null* 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf ： 1.固定式分区和可变式分区有如下三个优点： 1）有助于多道程序设计； 2）它不需过多的硬件支持，只需界限地址寄存器用于存储保护； 3）所采用的算法大多比较简单，容易实现。 2.固定式分区和可变式分区有如下缺点： 1）产生碎片，因而降低了存储器的利用率； 2）无法扩充主存容量。null*A、将R合并到f1，f1.addr; f1.size+r.size B、将R合并到f2, r.addr; r.size+f2.size C、f1、R、f2 合并到f1, f1.addr; f1.size+r.size+f2.size撤消f2空闲区 D、r作为一个空闲区，并插入到空闲区表的适当位置。3空闲释放区与空闲区相邻有四种情况null* 碎片(零头)就是不能分配给用户进程的、无效的空闲内存空间。 在什么情况下系统要紧凑： 1）当某个分区的作业一完成，就立即紧凑，内存仅保留一个 空白区； 2）当为某个作业分配分区而内存又没有足够大的分区，但各空闲分区容量总和满足该作业的需求才进行紧凑。 优点：消除了碎片，提高了存储器的利用率。 缺点：需要硬件支持,增加计算机的成本，降低了计算机的速度。4.3.6 可重定位分区分配 可重定位分区分配是解决碎片问题的简单而有效的办法。其基本思想是移动所有被分配了的分区，使之成为一个连续的区域，而把碎片集中成一个较大的空白区。这个移动的过程叫做“拼接”或“紧凑”。 null* 采用移动技术时应该尽量减少移动的作业数和信息量,以降低系统的开销,提高系统的效率,改变作业装入主存的方式减少移动的作业数和信息量。 移动技术为作业执行进程中扩充主存空间提供方便,一道作业在执行中要求增加主存量时,只要适当移动邻近的作业就可增加它所占的分区长度。 采用移动技术时必须注意以下几点: (1)移动会增加系统开销; (2)移动是有条件的; 1.最佳适应算法的空白区是（ ） A.按大小递减顺序排列 B.按大小递增顺序排列 C.按地址由小到大排列 D.按地址由大到小排列 2.存储管理 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 中，（ ）可采用覆盖技术。 A.单一连续区存储管理　　　B.可变分区存储管理 C.段式存储管理　　　　　　D.段页式存储管理 3.在可变式分区分配方案中,某一作业完成后,系统收回其主存空间并与相邻空闲去合并,为此需修改空闲区表,造成空闲区数减1的情况是（ ） A.无上邻空闲区也无下邻空闲区　B.有上邻空闲区但无下邻空闲区 C.有下邻空闲区但无上邻空闲区　D.有上邻空闲区也有下邻空闲区 4.在分区分配方案中，需要执行紧凑的操作是（ ） A.固定式分区 B.可变式分区 C.可再定位式分区 D.多重式分区 5.在分区分配算法中，首次适应算法倾向于优先利用内存中（ ）部分的空闲分区，从而保留了（ ）部分的大空闲区。*1.最佳适应算法的空白区是（ ） A.按大小递减顺序排列 B.按大小递增顺序排列 C.按地址由小到大排列 D.按地址由大到小排列 2.存储管理方案中，（ ）可采用覆盖技术。 A.单一连续区存储管理　　　B.可变分区存储管理 C.段式存储管理　　　　　　D.段页式存储管理 3.在可变式分区分配方案中,某一作业完成后,系统收回其主存空间并与相邻空闲去合并,为此需修改空闲区表,造成空闲区数减1的情况是（ ） A.无上邻空闲区也无下邻空闲区　B.有上邻空闲区但无下邻空闲区 C.有下邻空闲区但无上邻空闲区　D.有上邻空闲区也有下邻空闲区 4.在分区分配方案中，需要执行紧凑的操作是（ ） A.固定式分区 B.可变式分区 C.可再定位式分区 D.多重式分区 5.在分区分配算法中，首次适应算法倾向于优先利用内存中（ ）部分的空闲分区，从而保留了（ ）部分的大空闲区。BADC低地址高地址null*6.在存储管理中，采用覆盖与交换技术的目的是（ ） A.节省主存空间 B.物理上扩充主存容量 C.提高CPU效率 D.实现主存共享 7.动态重定位技术依赖于（ ） A.重定位装入程序 B.重定位寄存器 C.地址机构 D.目标程序 8.在下列存储管理方案中，不适应于多道程序设计的是（ ） A.单一连续区分配　　B.固定式分区分配 C.可变式分区分配　　D.段页式存储管理 9.在可变式分区存储管理中的拼接技术可以（ ） A.缩短访问周期 B.增加主存容量 C.加速地址变换 D.使空闲区集中 ABADnull* 10.某系统的空闲分区表如下所示，采用可变式分区管理策略，现 有如下作业序列：96KB、20KB、200KB。若用首次适应算法和 最佳适应算法来处理这些作业序列，则哪一种算法可满足该作业序 列请求，为什么？ 分区号 大小 起始地址 32KB 100KB 10KB 150KB 5KB 200KB 218KB 220KB 96KB 530KB 空间分配表