A存储器的层次结构.ppt

1 学习重点和难点： u1 存储管理的基本概念 u2 各种存储管理的基本思想、实现方法和技术 u3 地址空间和物理空间的区别 u4 虚拟存储器的概念和方法 u5 请求分页/分段存储管理方式 u6页面置换算法 第四章 存储器管理 2 存储器是计算机系统的重要组成部分，虽然 内存容量在不断扩大，但内存仍是宝贵资源，如 何提高主存储器利用率，并扩充主存，对主存信 息实现有效保护是存储器管理主要任务，也是各 种不同存储管理方法的目标。 3 4.1 存储器的层次结构 寄存器 主存 辅存 计算机系统存储层次示意 容 量 速 度 / 价 格 4 4.1 存储器的层次结构 寄存器 高速缓存 主存 磁盘缓存 磁盘 可移动存储介质 计算机系统存储层次示意 CPU寄存器 主存 辅存 速度最快、价格昂贵，容量小 解决CPU与主存速度矛盾 CPU直接访问、可执行存储器 解决主存与辅存速度矛盾 5 物理地址和逻辑地址 主存的存储单元以字节为单位编址，每个存储单元都有一 个地址与其相对应。这些地址称为主存的物理地址(绝对地址/ 实地址)；由物理地址所对应的主存空间称为物理地址空间。 在多道程序设计系统中，主存中同时存放了多个用户作 业。每个用户不可能预先知道其作业存放在主存的具体位置。 因此，在用户程序中不能使用主存的物理地址。每个用户可以 认为自己作业的程序和数据存放在一组从0地址开始的连续空 间中。用户程序中所使用的地址称为逻辑地址(相对地址/虚地 址)。所对应的空间称为逻辑地址空间。 6 4.2 程序的装入和链接 源程序 编译 目标模块 库 链接 程序 装入模块 装入 程序 内存 7 将一个模块装入内存时，可采用三种方式： 绝对装入方式 可重定位装入方式（静态重定位 ） 动态运行时装入方式（动态重定位） 1.程序的装入 8 如果在编译时知道程序驻留在主存的具体位置，则编 译程序将产生物理地址的目标代码。模块装入后，由于程 序中的逻辑地址与实际主存的地址完全相同，故不需要对 程序和数据的地址进行修改。 指内存分配是在作业运行之前各目标模块连接后，把 整个作业一次性全部装入内存，并在作业的整个运行过程 中，不允许作业再申请其他内存，或在内存中移动位置。 也就是说，内存分配是在作业运行前一次性完成的。 绝对装入方式只能将目标模块装入到主存事先指定的 固定位置，只适用于单道程序环境。 1)绝对装入方式 9 Move AX,2500 54321 2000 2100 2500 3000 绝对装入方式 编译时产生的绝对地址 Move AX,2500 54321 2000 2100 2500 3000 0 内存空间 FFFF 10 将逻辑地址变换成物理地址的过程叫做地址重定位。 2)可重定位装入方式 在装入作业时,把该作业中的指令地址和数据地址一次性 全部转换成物理地址,在作业执行进程中无需再进行地址转换 工作。 由于这种地址变换通常是在装入时由装配程序一次性完成 的，以后不再改变，故称为静态重定位。 物理地址=逻辑地址+程序在内存的首地址 优点：无需硬件支持，容易实现。 缺点： 1.程序经地址重定位后不能再移动了； 2.程序在内存空间只能连续存储； 11 032 54321 0 8 32 124 132 54321 100 108 132 244 内存空间 FFFF + + 装入程序 静态重定位 逻辑地址空间 12 动态运行时装入是在程序执行期间由地址变换机构动态实现的 。 动态重定位由软件和硬件相互配合实现。硬件需要一个地址转 换机制，该机制由一个基址寄存器和一个地址转换线路组成。 物理地址= 逻辑地址+基址寄存器的内容 存储管理为作业分配存储区域后,装入程序把作业直接装入到 所分配的区域中,并把该主存区域的起始地址存入相应进程的PCB 中。当进程被调度占用CPU时,作业所占的主存区域的起始地址也 被存放到基址寄存器中。进程执行时，CPU每执行一条指令都会把 指令中的逻辑地址与基址寄存器中的值相加得到相应的物理地址, 然后按物理地址访问存储器。 3 动态运行时装入方式（动态重定位） 13 032 54321 0 8 32 124 032 54321 100 108 132 244 内存空间 FFFF 装入程序 作业的装入 CPU + 逻辑地址 032 100 基地址寄存器 物理地址 032 54321 100 108 132 244 内存空间 FFFF 地址转换 动态重定位 + + + 132 14 若改变了存储区域,作业仍能正确执行,则称程序是可 浮动的。采用动态重定位的系统支持程序浮动。而采用静 态重定位时,由于被装入主存中的作业信息都已转换为物 理地址,作业执行进程中,不再进行地址的转换,故作业执 行进程中是不能改变存放位置,即采用静态重定位的系统 不支持程序浮动. 优点： 1.用户程序在执行过程中在内存可以移动，有利于内存的充分 利用； 2.程序不必连续存放在内存中，可以放在不同的区域； 缺点： 需要附加硬件支持，实行存储管理的软件算法也比较复杂。 15 4.2.2 程序的链接 根据链接时间的不同，可把链接划分为三种方式： 静态链接 装入时动态链接 动态链接 运行时动态链接 16 1) 静态链接 静态链接：在程序运行之前，先将各个目标模块 及他们所需的库函数，链接成一个完整的装入模块(又 称为可执行文件)运行时直接装入内存。这种事先进行 链接，以后不再拆开的链接方式称之静态链接。 经过编译后得到目标模块,每个模块的起始地址都 为0。模块中的地址都是相对于起始地址计算的，在链 接成一个装入模块后，程序中被调用模块的起始地址 不再是0，此时必须修改被调用模块的逻辑地址，同时 每个模块中使用的外部调用符号也相应转变为逻辑地 址。 17 模块A CALL B; RETURN; 模块B CALL C; RETURN; 模块C RETURN; 0 L-1 0 M-1 0 N-1 模块A JSR “L”; RETURN; 模块C RETURN; 模块B JSR “L+M”; RETURN; 0 L-1 L L+M-1 L+M L+M+N-1 目标模块 装入模块 静态链接 18 2) 装入时动态链接 装入时动态链接：将用户源程序编译后所得到的一 组目标模块，在装入内存时，采用边装入边链接的链接方 式。 由于采用动态链接的各个目标模块是分开存放的，操 作系统可以方便地将一个目标模块链接到几个应用模块上 。 优点: (1) 便于修改和更新 (2) 便于对目标模块的共享 19 3) 运行时动态链接 运行时动态链接：对某些目标模块，当在程序执行 中需要该模块时，才对它进行的链接。亦即，在程序的执 行过程中，当发现一个被调用模块尚未装入内存时，立即 由操作系统去找到该模块并将之装入内存，把它链接到调 用者模块上。凡在执行过程中未被用到的目标模块，都不 会被调入内存和被链接到装入模块上，这样不仅加快了程 序的装入过程，而且可节省大量的内存空间。 20 4.3 连续分配方式 把主存中的用户区作为一个连续区域或者分成若干个连 续区域进行分配。 可分为单一连续分配、固定分区分配、 动态分区分配及动态重定位分区分配 。 1、单一连续分配管理 最简单的存储管理方式;操作系统占用一部分主存空间 ,其余的主存空间作为一个连续分区全部分配给一个作业使 用,即在任何时刻主存中最多只存有一个作业。 21 单一连续存储管理 0 a b c 作业2 作业1 装入程序 操作系统 空闲区 子程序集 CPU 界限寄存器 a 用户区 单一连续存储管理示意图 22 单一连续存储管理 操作系统 固定区 覆盖区 初始段处理段 输出段 可覆盖的段 (地址空间大于用户区的作业) 1 2 3 覆盖技术示意图 23 覆盖技术 所谓“覆盖”就是一个作业的若干个程序段，或几个作业的某 些部分共享同一内存空间。 覆盖技术的基本思想是把主存的同一区域分配给一道程序的 若干个子程序或数据段。开始时只有程序的一部分装入主存，在 其执行过程中根据请求动态的把其它部分装入到该程序原来已经 占用过的存储区域中。 优点：能更有效的利用内存。 缺点： 1.用户难以预知程序的覆盖情况； 2.各作业占用的分区存在碎片； 24 单一连续存储管理 特点: (1)不必考虑作业在主存中的移动问题 (2)存储保护比较简单 (3)可用于分时系统中 采用对(交)换技术实现 多个用户作业轮流进 入主存 操作系统 用户区 主存 作业1 作业2 磁盘 换出1 换入2 作业对换示意图 25 交换技术目的，一方面解决主存容量不够大的 矛盾，一方面使各分时用户能保证合理的响应时间 。所谓交换，就是系统根据需要把主存中暂时不运 行的某个(或某些)作业部分或全部移到外存，而把 外存中的某个(或某些)作业移到相应的主存区，并 使其投入运行。 交换的时机通常在以下情况发生： 进程用完时间片或等待输入输出； 作业要求扩充存储而得不到满足时。 交换技术 26 交换技术的关键是设法减少每次交换的信息量。为 此，常将作业的副本保留在外存，每次换出时，仅换出 那些修改过的信息即可。 交换技术也是利用外存来逻辑地扩充主存。它的主要 特点是打破了一个程序一旦进入主存便一直运行到结束 的限制。 思考题：覆盖和交换技术有何联系？ 1.覆盖技术和交换技术是两种扩充内存的技术。2.覆盖 技术主要用于早期的os中，而交换技术在现代os中仍有 较强的生命力。 3.覆盖技术要求程序员提供一个清晰的覆盖结构，即由 程序员来完成把一个程序划分为不同的程序段并规定好 执行及覆盖顺序；而交换技术完全由os来实现，整个过 程对程序员是透明的。 4.覆盖主要是在同一个作业或同一个进程内进行；而交 换是在进程或作业之间进行。 27 缺点: (1)CPU利用率比较低 (2)存储器得不到充分利用 (3)计算机的外围设备利用率不高 4.3.2 固定分区分配 固定分区法 固定分区预先把主存中的用户区分割成若 干个连续区域,每个连续区域称为一个分区,每个分 区大小可以相同也可以不同。 28 作 业 1 作 业 3 作 业 2 . 作业对列 操作系统 主存 分区1 分区2 分区3 0 d c b a CPU 当前运行作业所在分区2 b c 下限寄存器 上限寄存器 固定分区存储管理示意图 29 区号分区长度起始地址状态 18K20KJOB A 232K28KJOB B 364K60KJOB C 4132K124K 0 进程B（25K） 进程C（36K） 主存分配表 1.空间的分配和去配 作业B（20K ） 存储空间分配情况四个分区的主存分配表 20K 28K 60K 124K 256K OS 作业A（6K） 作业C（64K ） 作业B（20K ） 30 地址转换和存储保护 固定分区存储管理下,作业在执行过程中是不会被改变 存储区域的, 可采用静态重定位装入方式装入作业。 由装入程序把作业中的逻辑地址与分区的下限地址相 加,得到相应的物理地址。当一个已经被装入主存的作业占 有CPU运行时,进程调度程序将该作业所在分区的下限地址 和上限地址分别存储在CPU的下限寄存器和上限寄存器中 。 CPU执行该作业指令时必须判断: 下限地址=物理地址上限地址 31 主存空间的利用率 提高主存空间利用率的方法: (1)根据经常出现的作业的大小和频率划分分区,尽 可能提高各个分区的利用率。 (2)划分分区时按分区大小顺序排列。 (3)按作业对主存空间的需求量排成多个作业队列,规定每个 作业队列中的各作业只能依次装入对应的分区中; 分区2 0 a b c d 作业对列1 作业对列2 作业对列3 OS 分区1 分区3 L1 L2 L3 32 4.3.3 动态分区分配 1.动态分区分配的基本概念 因为固定分区主存利用率不高，使用起来不灵活，所以出 现了动态分区的管理技术。 动态分区原则：存储空间的划分是在装作业时进行的。从 可用的自由存储空间内，划出一个大小正好等于作业大小的存 储区，并分配给这一作业。 OS 进程A 进程B 进程C 进程D OS 进程A 进程B 进程C OS 进程A 进程B OS 进程A 进程 A（8K）进程 D（124K）进程 B（16K） 进程 C（64K） 33 1.) 空间的分配和去配 当有作业完成后释放所占用的存储区。 在系统运行的过 程中，系统中形成多个空闲的不连续的存储区，称主空闲。 34 采用动态分区存储管理方式管理存储空间时,主存中已占 用分区和空闲区的数目和大小都是可变的。为了实现可变分 区存储管理,系统必须设置相应的数据结构,用来描述空闲分 区和已分配分区的情况,为系统空间分配提供依据。常用的数 据结构有以下两种形式: (1)空闲分区表 (2)空闲分区链 35 (1)空闲分区表 系统设置空闲分区表和已分配分区表,用来描述空闲分区 和已分配分区的情况,为系统空间分配提供依据。 . 空 作业E14KB140KB 作业C10KB105KB 作业F32KB55KB 作业A15KB40 标志长度始址 已分配分区表 空 未分配102KB154KB 未分配25KB115KB 未分配18KB87 标志长度始址 空闲分区表 36 (2)空闲分区链 为了实现对空闲分区的分配和链接,在每个分区的起始 部分设置一些用于控制分区分配的信息以及用于链接前一个 分区的前向指针;在分区的尾部则设置一后向指针,通过前、 后向链接指针,可以将所有的空闲分区连接成一个双向链。 0 0 N+2N+2 后向 指针 N个字节可用 前向 指针 37 2 分区分配算法 分区分配和回收是对空闲区表（或空闲区队列）数据 结构进行操作，空闲区表的组织有两种方法： 1、按空闲区大小的升序（降序）组织； 2、按空闲区首地址升序（降序）组织。 根据空闲区表组织的方法的不同，有不同的放置策略 ，它们是首次适应算法、循环首次适应算法、最佳适应算 法、最坏适应算法和快速适应算法。 38 A 首次适应分配算法 首次适应分配算法的表是按空闲区首地址升序的 （即空闲区表是按空闲区首址从小到大）方法组织的。 39 从该空闲区中截取所需 大小，修改调整可用表 从空闲区表第一 表目顺序查找 从可用表中移去该 表目，调整可用表 取下一表项 无法分配 该 空闲区 长度SIZE？ 该 空闲区 长度=SIZE？ 表目查完？ 返回分配起始地址 否 否 否 是 是 是 首次适应分配算法 40 优点： 1.可以在释放分区时很容易合并相邻的空白区，从而 形成较大的空白区； 2.尽可能地利用存储器的低地址部分而保留高地址部 分。 缺点： 1、搜索次数较大，影响工作效率。 2、低地址部分不断被划分 B 循环首次适应算法 41 C 最佳(又称最优)适应分配算法 最佳适应分配算法是将申请者放入与其大小 最接近的空闲区中。切割后的空闲区最小，若系 统中有与申请区大小相等的空闲区，这种算法肯 定能将这种空闲区分配给申请者。（首次适应法 则不一定）。 42 最佳适应算法的空闲区表按空闲区容量大小升序方法组织 。 分配时，按申请的大小逐个与空闲区大小进行比较，找到 一个满足要求的空闲区，就说明它是最适合的（即最佳的）。 优点： 1.如果有一个空白区的容量正好满足要求，则它必被选中； 2.每次都是选择一个容量最接近的空白区，而使较大的空白区 保留。 缺点：产生非常小的空白区（碎片） 43 D 最坏(也称最差)适应分配算法 为了克服最佳适应分配算法把空闲区切割 得太小的缺点，人们提出了一种最坏适应分配 算法，即每次分配时，总是将最大的空闲区切 去一部分分配给请求者，其依据是当一个很大 的空闲区被切割了一部分后可能仍是一个较大 的空闲区。避免了空闲区越分越小的问题。 44 最坏适应算法的空闲区表是按空闲区大小降序的方法组织 的（从大到小的顺序）。 分配时总是取表中的第一个表目，若不能满足申请者的要 求，则表示系统中无满足要求的空闲区，分配失败；否则，将 从该空闲区中分配给申请者，然后修改空闲区的大小，并将它 插入到空闲区表的适当位置。 优点：产生的空白区可供以后使用。 缺点：工作一段时间后，不能满足对较大作业的分配要求。 45 首次适应算法、循环首次适应算法、最佳 适应算法和最坏适应算法称为顺序搜索法。 E 快速适应算法（分类搜索法） 将空闲分区根据其容量大小进行分类，对于每一 类具有相同容量的所有空间分区，单独设立一个空闲 分区链表。 优点： （1）查找效率高； （2）保留大的分区，不产生碎片； 缺点： （1）分区归还主存时算法复杂； （2）浪费严重； 46 总结： 1.固定式分区和可变式分区有如下三个优点： 1）有助于多道程序设计； 2）它不需过多的硬件支持，只需界限地址寄存器用于存储 保护； 3）所采用的算法大多比较简单，容易实现。 2.固定式分区和可变式分区有如下缺点： 1）产生碎片，因而降低了存储器的利用率； 2）无法扩充主存容量。 47 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空闲释放区与空闲区相邻有四种情况 48 碎片(零头)就是不能分配给用户进程的、无效的空闲内存 空间。 在什么情况下系统要紧凑： 1）当某个分区的作业一完成，就立即紧凑，内存仅保 留一个 空白区； 2）当为某个作业分配分区而内存又没有足够大的分区 ，但各空闲分区容量总和满足该作业的需求才进行紧凑。 优点：消除了碎片，提高了存储器的利用率。 缺点：需要硬件支持,增加计算机的成本，降低了计算机的速 度。 4.3.6 可重定位分区分配 可重定位分区分配是解决碎片问题的简单而有效的办 法。其基本思想是移动所有被分配了的分区，使之成为一 个连续的区域，而把碎片集中成一个较大的空白区。这个 移动的过程叫做“拼接”或“紧凑”。 49 采用移动技术时应该尽量减少移动的作业数和信息量 ,以降低系统的开销,提高系统的效率,改变作业装入主存 的方式减少移动的作业数和信息量。 移动技术为作业执行进程中扩充主存空间提供方便,一 道作业在执行中要求增加主存量时,只要适当移动邻近的作 业就可增加它所占的分区长度。 采用移动技术时必须注意以下几点: (1)移动会增加系统开销; (2)移动是有条件的; OS J1 J2 J3 J4 空闲区 OS J1 J3 空