第5章存储管理.ppt

2019/6/17,1,计算机组成 和 操作系统,第5章 存储管理,5.1 存储器概述,5.2 高速缓冲存储器,5.3 内存分配方式,5.1 存储器概述,5.1.1 存储器的分类 5.1.2 存储器的性能指标 5.1.3 存储器的组成与工作原理 5.1.4 存储器的层次结构,4,5.1.1 存储器分类,按存储器的器件和存储介质分类 按存取方式分类 按存储器在计算机中的作用分类,5,1. 按存储器的器件和存储介质分类,半导体存储器：由半导体器件组成 双极型存储器、MOS型半导体集成电路存储器 速度快、功耗低 磁存储器：由磁性材料做成 磁芯、磁带、磁盘等 容量大，速度慢、体积大 光存储器：用光学材料根据光学原理存储信息 CD-ROM、DVD-ROM 便于携带，廉价，易于保存,6,顺序存储器（SAM） 所存储的内容只能按某种顺序存取 存取所需时间与物理位置有关 顺序存储器的平均存取周期较长，一般用于辅存 随机存储器（RAM） 存储器中的任意存储单元都能随机存取 存取所需时间与物理位置无关 主存主要由RAM组成,2.按存取方式分类,7,直接存取存储器（DAM） 介于随机和顺序之间 随机定位信息块，但对信息块是顺序读写 只读存储器 (ROM) 存储器内容是预置的，固定的，无法改写 信息可长期保存,2.按存取方式分类（续）,8,主存储器 速度快，容量小，价格高 目前主要采用半导体存储器 辅助存储器 速度低，容量大，价格便宜 目前主要有磁盘、光盘、闪存、磁盘阵列 高速缓冲存储器 Cache 放置在两个访问速度不一样的存储部件之间，用来暂存信息和数据,3.按存储器在计算机中的作用分类,9,存储容量：一般以字节为单位。 存取速度：取数时间和存取周期。 价格：用单位存储空间的价格来衡量。 可靠性：用平均无故障时间来衡量。,5.1.2 主存储器的主要性能指标,10,5.1.3 存储器组成与工作原理,存储器的组成,存储单元及其编址,5.1.3 存储器组成与工作原理,主存的组成和工作原理,分析：速度越快，成本较高。 为了获得好的性能/价格比，计算机中各种存储器组成一个层状的塔式结构，取长补短，协调工作 工作过程： 1）CPU运行时，需要的操作数大部分来自寄存器 2）如需要从(向)存储器中取(存) 数据时，先访问cache，如在，取自cache 3）如操作数不在cache，则访问RAM，如在RAM中，则取自RAM 4）如操作数不在RAM，则访问硬盘，操作数从硬盘中读出RAM cache,5.1.4 存储器的层次结构,13,5.2 高速缓冲存储器,为什么需要高速缓存？ CPU与存储器之间的速度无法匹配 解决之道 采用高速器件提高速度 增加字长，在每个存储周期中存取多个字 增加cache,14,高速缓存的理论依据程序局部性原理 程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域，包括： 时间局部性 指令的执行和数据的访问集中在一个较短时期内 空间局部性 指令的执行和数据的访问集中在一个较小区域内。,15,程序局部性原理的具体体现： 程序在执行时，大部分是顺序执行的指令，少部分是转移和过程调用指令。 程序中存在相当多的循环结构，它们由少量指令组成，而被多次执行。 程序中存在相当多对一定数据结构的操作，如数组操作，往往局限在较小范围内。,5.2.1 Cache系统的基本结构,Cache系统组成 Cache 地址映像与变换机构 Cache替换策略和更新策略,16,17,5.2.2 cache系统的工作原理,5.2.2 cache系统的工作原理,1.直接映像（direct mapping）,主存和Cache 中字块的对应关系采用直接映像函数为： j=i mod 2c 其中，j 是Cache 的字块号，i是主存的字块号。在这种映像关系中，主存的第0块，第2c块，第2c+1块，只能映像到Cache的第0块，而主存的第1块，第2c+1块，第2c+1+1块，只能映像到Cache 的第1 块。,直接映像的优点是实现简单,直接映像方式的缺点是不够灵活,5.2.2 cache系统的工作原理,2全相联映像(fully associative mapping),主存地址分为两段：主存字段标记mtc 位、块内地址b 位 Cache 地址也分为两段：块地址c 位、块内地址b 位。 主存块内地址与Cache地址块内地址相同,全相联映像方式的优点是可以灵活地进行块的分配，块的冲突率低，Cache 的利用率高。但这是一个理想的方案。实际上由于它的成本太高而不能采用,5.2.2 cache系统的工作原理,3. 组相联映像（set associative mapping）,组相联映像方式是直接映像和全相联映像方式的一种折中方案。,组相联映像把主存地址划分成4 段 Cache 地址分为三段,5.3 内存分配方式,5.3.1 连续分配存储管理方式 5.3.2 分页式存储管理 5.3.3 段式存储管理 5.3.4 段页式存储管理 5.3.5 虚拟存储管理 5.3.6 各种存储分配策略的比较,21,22,补充:程序的装入与链接,编译 源代码目标代码 链接 目标代码+所需库函数=装入模块 装入 将装入模块装入内存，该过程也叫做地址重定位，也称地址映射,地址空间：源程序经编译后得到的目标程序，存在于它所限定的地址范围内，此范围称地址空间。地址空间是逻辑地址的集合。 存储空间：指主存中一系列存储信息的物理单元的集合，这些单元的编号称为物理地址。存储空间是物理地址的集合。,程序的装入方式,重定位（地址映射）： 把用户程序中的相对地址（逻辑地址）转换为主存中的绝对地址（物理地址）过程。 静态重定位： 编译时产生相对地址，装入程序确定要装入模块的地址，并在装入时进行重定位，程序运行中不允许在内存移动。 动态重定位 编译时产生相对地址，装入程序在把装入模块装入内存时，不立即把装入模块中的相对地址转换为绝对地址，而是推迟到程序要真正执行时才进行。,静态重定位示意图,动态重定位示意图,程序的链接方式,静态链接 对相对地址进行修改 变换外部调用符号 装入时动态链接 在装入内存时，边装入边链接 便于软件版本的修改和更新 便于实现目标模块共享 运行时动态链接 运行时，用到哪个模块，再链接哪个模块，用不到的模块可不装入内存。,程序的链接,28,连续分配是指为一个用户程序分配一个连续的内存空间。分为： 单一连续分配 固定分区 可变分区,5.3.1 连续分配存储管理,单一连续分配,应用范围：单用户、单任务操作系统。如：CP/M、DOS2.0以下。 操作系统的任务就是将系统程序和用户程序分开。 方法：用基址-限长寄存器。,固定分区存储管理,方法 分区在系统启动后划分好，以后不能改变。 应用范围： 多道程序设计系统最简单的一种方式。如：60年代的IBM360上的MFT。 划分分区方法 分区大小相等 分区大小不等 缺点 内存利用率低,可变分区存储管理,方法 分区的大小和个数随系统的运行而不断改变,可变分区分配数据结构 空闲分区表 空闲分区链 可变分区分配算法 首次适应法 下次适应法 最佳适应法 最坏适应法 可变分区的分配和回收操作,可变分区存储管理,条件 空闲分区链以存储空间地址递增的次序链接。 优点 释放时，因不改变该区在队列中的位置，因此速度快。 保证高地址有空闲空间，可留给大作业。 缺点 常用大空闲区适应小作业，从而留下小空闲区，且这些小空闲区在链表的前面，影响分配速度。,可变分区分配算法,最佳适应法,首次适应法,下次适应法,最坏适应法,条件 空闲分区链以存储空间地址递增的次序连接成循环链，为进程分配存储空间时，不是从队首开始找，而是从上次找到的空闲空间的下一个空闲分区开始找。 优点 存储空间利用均衡。 缺点 没有了较大空闲空间，使大作业无法运行。,条件 空闲分区链以存储空间大小递增的次序拉链。 优点 若存储空间中存在与申请大小相等的空闲区，则必然被选中，否则选一个稍大的空闲区，而避免毁掉更大的空闲区。 缺点 小碎片增加碎片问题严重。 回收时，将空闲区插入适当的位置费时。,条件 空闲分区链以存储空间大小递减的次序拉链。 优点 分配后，剩下的空闲区还好用。 申请时，查找容易，因此速度快。 缺点 当有大作业时，可能就没有空间可用了。,可变分区内存的回收,回收分区与前面一个（低地址）空闲分区F1相邻接，图（a） 回收分区与后面一个（高地址）空闲分区F2相邻接，图（b） 回收分区与前、后两个空闲分区F1和F2均相邻，图（c） 回收分区不与其它空闲分区相邻接,离散分配方式的引入,连续分配方式带来的问题是会在存储空间中产生许多“碎片”。 能否将进程分配到许多不相邻的分区中呢？由此产生离散分配方式。 分页存储管理方式 存储管理的需要 分段存储管理方式 用户编程的需要,基本原理 将进程的逻辑地址空间分成若干个大小相等的片，称为页面或页； 内存空间分成与页大小相等的若干个存储块，称为物理块或页框。 在为进程分配内存时，以块为单位，将进程中的若干页分别装入多个可以不相邻的块中。,5.3.2 分页式存储管理,页面的大小由机器的地址结构决定的。 页面的大小的权衡 页面较小-内存碎片小；页表过长，占用较大内存空间。 页面较大-页表短，占用较少内存；内存碎片大。 通常页面的大小要适中，在512KB4MB之间。,页面大小的选择,逻辑地址被分为两部分： 页号 页内位移 例如逻辑地址1500的二进制形式为0000 0101 1101 1100 由于页的大小为1024B，故页内位移占10位，剩下6位为页号 逻辑地址1500对应的页号为1（二进制为0000 01） 页内位移为476（二进制为01 1101 1100）,页式存储管理逻辑地址结构,页式存储管理地址变换机构,快表,由于页表放在内存，使得CPU存取一个数据时，要两次访问内存，为了提高速度，增设快表（高速缓存）。,方便编程 分段共享 分段保护 动态链接 动态增长,引入原因,5.3.3 段式存储管理,段式存储管理的基本原理,整个作业的地址空间被分成若干个段，每个段采用一段连续的地址空间，段的长度由相应的逻辑信息的长度决定。,段式存储管理地址变换机构,分页和分段的区别,分页和分段的目的 页是信息的物理单位，分页是系统管理的需要，而不是用户的需要。 段是信息的逻辑单位，它含一组意义完整的信息。分段是为了更好地满足用户的要求。 页和段长度 页的大小固定，由系统确定。 段的长度不固定，决定于用户所编写的程序。 地址空间 分页的作业地址空间是一维的，即单一的线性地址空间。 分段的作业地址空间是二维的，程序员在标识一个地址时，需给出段名和段内地址。,段的共享与保护,页共享与段共享的比较 由于段是信息的逻辑单位，用户易于实现对段的共享，也容易对段进行保护。 而页虽也可共享，但不方便。 举例 例如有一个多用户系统，可同时容纳40个用户，它们都执行一个文本编辑程序，该文本编辑程序含有160KB的代码和40KB的数据， 如不共享，共需160*40+40*40=8MB的内存空间来支持40个用户。 若代码是可重入的，则无论是分页系统还是分段系统都可以共享该代码段，因此内存只需留一个文本编辑程序，所需空间为160+40*40=1760KB。,页的共享,注意： 页的共享要求作业地址空间的共享页必须具有相同的页号。,使用分页系统，每个页面的大小是4KB，则代码段占160/4=40个页面，数据段占40/4=10个页面,段的共享,使用分段系统，不要求段号相同。,实现段的共享数据结构,共享进程计数：记录了共享某段的进程个数，设置整型变量count。 存取控制：对于一个共享，不同的进程可以有不同的存取控制权限。 段号：对于同一共享段，不同的进程可以使用不同的段号去共享该段。,分段的分配与回收,分配,回收,对第一个请求使用该共享段的进程，由系统为该共享段分配一物理区，再把共享段调入该区，同时将该区的始址填入该进程的段表的相应项中。 在共享段表中增加一表项，填写有关数据，置count=1；当其他进程要调用该共享段时，无需再分配内存，只需在调用进程的段表中增加一表项，在共享段表中，填加进程的名字等项目，令count加1。,当进程不使用某共享段时，删除共享段表中有关该进程的项目，令count减1，当count=0时，回收该共享段的物理内存，删除共享段表中对应项。,分页系统能有效地提高内存的利用率解决外部碎片问题。 分段系统则能更好地满足用户编程的需要解决段的共享、动态连接等问题。 将两者结合起来，汲取两着的优点，产生段页式存储管理。,5.3.4 段页式存储管理,段页式地址变换机构,页的大小：4KB 5*4KB+500B =20980,52,前面所介绍的各种存储器管理方式，都要求将一个作业全部装入内存方能运行，因而难以适应： 作业的尺寸大于实际内存的容量； 有大量的作业等待运行，但实际内存容量不足以使其全部装入； 为解决此类问题，引入了虚拟存储器，其理论依据是进程运行的局部性原理。,5.3.5 虚拟存储管理,53,1.虚拟存储技术 虚拟存储器是一种借助于外存空间，从而允许一个进程在其运行过程中部分地装入内存的技术。 2.虚拟存储的基本原理 程序部分装入 在程序执行过程中产生缺页或缺段，请求调入 将暂时不使用的页或段置换到到外存 3.虚拟存储器的实现方式 建立在离散分配存储管理方式的基础上。,54,基本分页系统+请求调页+页面置换页式虚拟存储器 硬件支持 请求分页的页表机制 缺页中断机构 地址变换机构 实现请求分页的软件,请求页式存储管理,55,请求分页存储管理需要为每个进程分配数量合适的物理块（帧），可采用： 固定分配、局部置换 可变分配、全局置换 可变分配、局部置换,请求页式存储管理,56,页面置换算法 最优算法 先进先出置换算法 最近最久未使用置换算法 LRU近似算法,请求页式存储管理,57,基本分段系统+请求调段+分段置换段式虚拟存储器 硬件支持 请求分段的段表 缺段中断 地址变换 实现请求分段的软件 请求分段可以实现动态链接，使得进入内存的断更有效，可以实现段共享。,请求分段系统,