《存储管理Av》PPT课件.ppt

第五章 存储管理,5.1 概述 5.2 存储管理基本技术 5.3 页式管理 5.4 段式管理 5.5 段页式管理 5.6 局部性原理和抖动性原理,存储器是计算机系统的重要资源之一。因为任何程序和数据以及各种控制用的数据结构都必须占用一定的存储空间，因此，存储管理直接影响系统性能。 存储器由内存(primary storage)和外存(secondary storage)组成。本章讨论的主要是内存管理问题，包括如下内容：,学习目标： 1.掌握：存储管理的功能、常用存储管理技术、虚拟存储器的概念，分页、分段的概念，以及页式、段式、段页式存储管理技术和虚存中的置换算法。 2.理解：存储器层次、存储分配。 3.了解：局部性原理和抖动问题。 学习要点： 本章涉及到的概念和管理技术较多，通过比较，理解如下概念：逻辑地址、物理地址、静态重定位、动态重定位、碎片、虚拟存储器；对于每一种存储管理技术应理解它解决什么问题，实现的思想，以及它带来的好处和存在的问题。,5.1 概 述,返回,1. 存储器的层次 2. 存储管理的功能 3. 存储分配的方式 4. 重定位 5. 内存信息的共享与保护 6. 虚拟存储器,内存储器（简称内存、主存、物理存储器） 处理机能直接访问的存储器。用来存放系统和用户的程序和数据，其特点是存取速度快，存储方式是以新换旧，断电信息丢失。,外存储器（简称外存、辅助存储器） 处理机不能直接访问的存储器。用来存放用户的各种信息，存取速度相对内存而言要慢得多，但它可用来长期保存用户信息。在文件系统中介绍。,1. 存储器的层次,快速缓存 Data Cache TLB(Translation Lookaside Buffer，变换索引缓冲区 ) 内存：DRAM, SDRAM等 外存：软盘、硬盘、光盘、磁带等,存储层次结构,当CPU存取内存数据时，并不是引用数据存储的物理地址（Physical Address），而是要通过指向物理地址映射的虚拟地址（Virtual Address）。而从虚拟地址到物理地址的映射结果就存放在TLB中。,内存的物理组织,物理地址： 把内存分成若干个大小相等的存储单元，每个单元给一个编号，这个编号称为内存地址（物理地址、绝对地址、实地址），存储单元占8位，称作字节（byte）。 物理地址空间： 物理地址的集合称为物理地址空间（主存地址空间），它是一个一维的线性空间。,程序的逻辑结构,程序地址：用户编程序时所用的地址（或称逻辑地址 、虚地址 ），基本单位可与内存的基本单位相同，也可以不相同。 程序地址空间（逻辑地址空间、虚地址空间）：用户的程序地址的集合称为逻辑地址空间，它的编址总是从0开始的，可以是一维线性空间，也可以是多维空间。,2. 存储器的功能, 存储分配和回收：按照一定的算法把某一空闲的主存区分配给作业或进程以及回收系统或用户释放的空间。 地址变换：将程序地址空间中使用的逻辑地址变换成主存中的地址的过程 程序加载(装入)时的重定位技术 可执行文件生成中的链接技术 进程运行时硬件和软件的地址变换技术和机构 存储共享和保护：保证用户程序(或进程映象)共享主存中的数据，并且在各自的存储区域内操作，互不干扰。 代码和数据共享 地址空间访问权限（读、写、执行） 存储器扩充：使用户程序的大小和结构不受主存容量和结构的限制。 由应用程序控制：覆盖； 由OS控制：交换（整个进程空间），虚拟存储的请求调入和预调入（部分进程空间）,3. 存储分配的方式, 直接分配方式：程序员在编写程序时，或编译程序对源程序进行编译时，所用的就是实际的存储地址。 前提：事先确定一个作业在主存中的位置； 缺点：存储空间的利用率不高，对用户使用不方便。 静态分配：在作业装入内存时才确定它们在内存中的位置，并在其整个运行期间不能在内存中移动，也不能再申请内存空间。 前提：一个作业装入内存时必须分配其要求的全部存储量，并且退出前不释放； 缺点：在多道程序系统中不能有效地共享存储器资源。 动态分配：在作业装入内存时才确定它们在内存中的位置，但在其整个运行期间可以再申请内存空间，也可在内存中移动。一个作业已占有的存储区不再需要时，可以归还给系统。,所谓存储分配，主要是讨论和解决多道作业之间共享主存的存储空间的问题。需要解决的问题：When，How，或是把一个作业的全部或是部分信息分配在主存中。 解决存储分配的问题，有三种方式：,目前绝大多数系统都采用的是静态或动态存储分配方式 分析用户程序的主要处理阶段： 编辑：形成源文件 编译：形成目标模块 链接：由多个目标模块或程序库生成可执行文件 装入：构造PCB，形成进程(使用物理地址) 运行：建立的进程在CPU在执行 装入阶段：程序必须装到内存才能运行，这需要装入程序根据内存的使用情况和分配策略，将上述装入模块放入分到的内存中。这时，可能要进行地址映射（重定位）,逻辑地址、物理地址和地址映射,逻辑地址（相对地址，虚地址）：用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式。 其首地址为0，其余指令中的地址都相对于首地址来编址。 不能用逻辑地址在内存中读取信息。 物理地址（绝对地址，实地址）：内存中存储单元的地址。物理地址可直接寻址。 地址映射：将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址。 当程序装入内存时, 操作系统要为该程序分配一个合适的内存空间，由于程序的逻辑地址与分配到内存物理地址不一致, 而CPU执行指令时，是按物理地址进行的，所以要进行地址转换。,4. 重定位,重定位（地址映射）：在可执行文件装入时需要解决可执行文件中地址（指令和数据）和内存地址的对应。由操作系统中的装入程序loader来完成。,重定位的概念,重定位方法：地址映射的功能就是要建立虚实地址的对应关系，实现地址映射有三种方式： 绝对装入：编程或编译时确定地址映射关系 可重定位装入（静态地址映射）：程序执行前，装入内存时一次性链接装入程序。 动态装入（动态地址映射）：处理机每次访问主存时，有动态地址变换机构（硬件）自动执行。,绝对装入,绝对装入：编程或编译时确定地址映射关系 编程时确定虚实地址的关系是指在用机器指令编程时，程序员直接按物理内存地址编程，这种程序在系统中是不能做任何移动的，否则就会出错。,优点：装入过程简单。 缺点：过于依赖于硬件结构，不适于多道程序系统。,可重定位装入,静态地址映射：在程序装入内存时完成从逻辑地址到物理地址的转换的。 在一些早期的系统中都有一个装入程序（加载程序），它负责将用户程序装入系统，并将用户程序中使用的访问内存的逻辑地址转换成物理地址。如下图所示。,优点：实现简单，不要硬件的支持。 缺点：一个程序通常需要占用连续的内存空间，程序装入内存后不能移动。不易实现共享。,动态装入,动态地址映射：动态地址映射是在程序执行时由系统硬件完成从逻辑地址到物理地址的转换的。,系统中设置了重定位寄存器：由操作系统用特权指令来设置，比较灵活。 动态地址映射是在执行时完成的，程序中不执行的程序就不做地址映射的工作，这样节省了CPU的时间 。 实现动态地址映射必须有硬件的支持。现代计算机系统中都采用动态地址映射技术。,5. 内存信息的共享和保护,在多道程序设计的环境下，系统中有系统程序和多个用户程序同时存在，用户程序间可以共享内存中的信息，但要保证用户程序不破坏系统程序，用户程序之间不相互干扰，这就是存储保护所要解决的问题。,存储保护的目的： 保护系统程序区不被用户侵犯（有意或无意的） 不允许用户程序读写不属于自己地址空间的数据（系统区地址空间，其他用户程序的地址空间）,存储保护类型 界限保护（上界寄存器/下界寄存器或基址寄存器/限长寄存器）：所有访问地址必须在上下界之间；每个进程都有自己独立的进程空间，如果一个进程在运行时所产生的地址在其地址空间之外，则发生地址越界。当程序要访问某个内存单元时，由硬件检查是否允许，如果允许则执行，否则产生地址越界中断，由操作系统进行相应处理。 访问方式保护（保护键）：通过保护键匹配来判断存储访问方式是否合法。对于允许多个进程共享的存储区域，每个进程都有自己的访问权限。如果一个进程对共享区域的访问违反了权限规定，则发生操作越权(即读写保护)。对每个内存区域指定一个键值和若干禁止的访问方式，进程中也指定键值，如果访问时键值不匹配而且是被禁止的访问方式，则出错。,上下界保护,下界寄存器：存放程序装入内存后的开始地址（首址） 上界寄存器： 存放程序装入内存后的末地址 判别式：下界寄存器 物理地址 上界寄存器,例：有一程序装入内存的首地址是500，末地址是1500，访问内存的逻辑地址是500、345、1200。 下界寄存器：500 上界寄存器：1500 逻辑地址装入内存的首地 物理地址 1、500500 1000 500 1000 1500 2、345500 845 500 845 1500 3、1200500 1700 500 1700 1500,基址、限长寄存器保护,例：有一程序装入内存的首地址是500，末地址是1500，访问内存的逻辑地址是500、345、1200。 基址寄存器：500 限长寄存器：1000 判别式：逻辑地址限长寄存器 1、 500 1000 2、 345 1000 3、 1200 1000 ,上下界保护和基址、限长寄存器 存储保护技术的区别,寄存器的设置不同； 判别式中用的判别条件不同 上下界寄存器保护法用的是物理地址 基址、限长寄存器保护法用的是程序的逻辑地址 对于合法的访问地址这两者的效率是相同的，对不合法的访问地址来说，上下界存储保护浪费的CPU时间相对来说要多些。,6. 虚拟存储器,问题的提出 物理存储器的结构是个一维的线性空间，容量是有限的。,用户程序结构： 一维空间： 一个用户程序就是一个程序，并且程序和数据是不分离的； 二维空间 程序由主程序和若干个子程序（或函数）组成，并且程序与数据是分离的； n维空间 即一个大型程序，由一个主模块和多个子模块组成，其中，各子模块又由主程序和子程序（或函数）组成。,用户程序的大小，可能比内存容量小，也可能比内存容量大，有时候要大得多。,如何将与物理内存结构不同，且大于物理内存容量的用户程序装入运行？这就是提出研究虚拟存储器的原因，或称为虚拟存储技术发展的原动力。,虚拟存储器概念,出发点：程序中往往含有不常被执行的代码，或者定义的数据结构大于实际需要。 虚拟存储器：为用户提供一种不受物理存储器结构和容量限制的存储器的技术称为虚拟存储器，或称虚拟存储技术。 它是用户编程时所使用的一种用户思维中的存储器，它可以是任何结构（一维线性空间、二维空间、乃至n维空间），并没有容量的限制。 现代计算机操作系统都采用了这种技术，使得用户编程序时不需要考虑物理内存的结构和容量，极大地方便了用户。,虚拟存储器的物资基础： 两级存储结构：内存和外存储器； 地址变换机构（DAT）：实现逻辑地址到物理地址的转换。,虚拟存储器的原理,在程序装入时，不必将其全部读入到内存，而只需将当前需要执行的部分页或段读入到内存，就可让程序开始执行。 在程序执行过程中，如果需执行的指令或访问的数据尚未在内存，则由处理器通知操作系统将相应的数据调入到内存，然后继续执行程序。 另一方面，操作系统将内存中暂时不使用的数据调出保存在外存上，从而腾出空间存放将要装入的程序以及将要调入的数据。只需程序的一部分在内存就可执行。,虚拟存储器的分类,根据地址空间结构的不同分为三类： 分页式虚拟存储器 分段式虚拟存储器 段页式虚拟存储器,虚拟存储器的特征,虚拟性 能从逻辑上扩充内存容量，是用户“看到”的内存容量远大于实际大小。 总容量不超过物理内存和外存交换区容量之和 离散分配 装入内存的作业不是连续分配的； 部分分配 一个作业被分成多次调入内存运行； 多次对换 允许在作业的运行过程中进行换进、换出；,虚拟存储器容量的限制,指令中表示地址的长度：机器指令中表示地址的二进制位数是有限的，如32位或64位，则用户的地址空间大小受到地址字长的限制。如：地址字长为32位，则地址空间最大是4G。 外存容量：一般硬盘作为外存，硬盘容量有限，所以用户的地址空间小于硬盘中作业的存放空间 总容量不超过物理内存和外存交换区容量之和,05年 简答题,虚拟存储管理中，作业地址空间大小的决定因素是什么？,5.2 存储管理基本技术,返回,1. 分 区 2. 覆 盖 3. 交 换,本节主要有如下内容:,1. 分区,分区存储管理是满足多道程序设计的最简单的一种存储管理方法，它允许多个用户程序同时存在系统内存中，即共享内存空间。,原理：把内存分为一些大小相等或不等的分区(partition)，除操作系统占用一个分区外，其余分区用来存放每个进程的程序和数据。 特点：适用于多道程序系统和分时系统 支持多个程序并发执行 难以进行内存分区的共享。 问题：可能存在内碎片和外碎片。 内碎片：占用分区之内未被利用的空间 外碎片：占用分区之间难以利用的空闲分区（通常是小空闲分区）。,按分区的时机，分区管理可以分为： 固定分区法：作业执行前把内存固定地划分区域； 动态分区法：在作业的处理过程中划分区域。,固定分区法,原理： 分区大小可以不相等 分区大小相等：适合于多个相同程序的并发执行。 分区大小不等：多个小分区、适量的中等分区、少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。 分区个数不变，大小不变 内存分配管理 数据结构：分区说明表（分区号、分区大小、起始地址、 分区状态） 由内存分配程序检索分区说明表，找到符合要求的分区。,固定分区(大小相同),固定分区(多种大小),固定式分区内存分配示意图（a） 固定式分区说明表（b）,固定分区分配,256K,512 K,5,未使用,124K,132 K,4,未使用,60K,64K,3,28K,32 K,2,20K,8 K,1,状态,位置,大小,区号,未使用,未使用,未使用,作业1：25k 作业2：150k 作业3：6k,存储保护与重定位（地址转换） 每个分区（一道程序）对应一对界地址寄存器：上/下限寄存器。 采用静态重定位方式，即由链接/装入程序完成。 优缺点 优点：简单，要求的硬件支持少； 缺点：存在大的碎片，主存利用率低。,动态分区法,思想 位置和大小都不固定，应作业的要求而设置。,数据结构的三种形式 空闲分区表(可用表) 空闲分区链(自由链) 请求表：描述请求内存资源的作业或进程号及所请求的内存大小,动态分区存储管理技术 系统生成后，操作系统占用内存的一部分，一般在物理内存的开始处，比如，一个操作系统占20KB，装入系统后占用020KB的内存空间，剩下的部分作为一个空闲区，当一个用户程序（作业、进程）调入内存时，把这个空闲区的低地址部分的区域分配给它，如图所示。,动态分区分配,Job1,Job2,Job3,Job4,Job5,Job6,Job7,Job7,Job6,分区的分配与回收,内存分配程序包括分配一个分区和释放一个分区两个函数，当进程需要一个大小为size的内存时，可以通过系统调用向系统申请。,申请一个分区 返回：成功为分区的首地址，失败为0,释放一个分区 返回：无,固定分区的分配与回收,分配算法见下页图 回收算法简单，只要将对应的分区状态置为未使用。,固定分区分配操作（分配算法流程）,动态分区时的分配与回收,动态分区的分配算法： 从可用表或自由链中找到一个足以容纳该作业的可用空白区； 若这个空白区比所需求大，则将它分成2个部分：一部分成为已分配区，剩下部分仍为空白区。 修改可用表或自由链，并回送一个所分配区的序号或该分区的始址。,动态分区分配算法的关键：,从空白区中寻找空闲空间是关键。 寻找空白区方法的不同：分区分配是对可用表（或自由链）数据结构进行操作，空闲区表的组织有两种方法： 按空闲区大小的升序（降序）组织； 按空闲区首址升序（降序）组织。 通常有3种寻找空白区的方法： 最先适应法 最佳适应法 最坏适应法,最先匹配法(first-fit)：按分区起始地址的递增次序，从头查找，找到符合要求的第一个分区。 该算法的分配和释放的时间性能较好，一旦找到大于或等于所要求内存长度的分区，则结束探索。 最佳匹配法(best-fit)：按分区大小的递增次序，查找，找到符合要求的第一个分区。 当申请空闲区时，存储管理程序从表头开始查找，当找到一个满足要求的空闲区时，停止查找，此时的空白区必定是最合适的，因为它是最接近于要求的大小。 最坏匹配法(worst-fit)：按分区大小的递减次序，从头查找，找到符合要求的第一个分区。 找到最大的空闲分区,最先适应算法流程,分配策略最先适应法,最先适应法（首次适应算法）：首次适应算法的表是按空闲区首址升序的（即空闲区表是按空闲区首址从小到大）方法组织的。,分配时从表首开始，以请求内存区的大小逐个与空闲区进行比较，找到第一个满足要求的空闲后，若空闲区大小与请求区的大小相等，则将该空闲区分配给请求者，并撤消该空闲区所在表目；若大于请求区，就将该空闲区的一部分分配给请求者，然后，修改空闲区的大小和首址。,切割空闲区有两种方法：从空闲区头开始 或从空闲区尾开始 空闲区大小50KB，首址156KB，申请34KB。,分配策略最佳适应法,最佳适应算法：空闲区表按空闲区大小升序方法组织。分配时，按申请的大小逐个与空闲区大小进行比较，找到一个满足要求的空闲区，就说明它是最适合的（即最佳的）。,分配策略最坏适应法,最坏适应算法的空闲区表是按空闲区大小降序的方法组织的（从大到小的顺序）。 分配时总是取表中的第一个表目，若不能满足申请者的要求，则表示系统中无满足要求的空闲区，分配失败；否则，将从该空闲区中分配给申请者，然后修改空闲区的大小，并将它插入到空闲区表的适当位置。,三种分配算法举例分析,这三种放置算法的优劣很难区分，要具体情况具体分析。 例如：某时刻系统中有三个空闲区其大小和首址为：(35KB，100KB) (12KB，156KB) (28KB，200KB) 有一作业系列：(JOB1，12KB) (JOB2，30KB) (JOB3，28KB),三种分配算法的比较,最先（首次）适应算法 实质是尽可能地利用低地址部分的空闲区，而尽量地保证高地址部分的大空闲区，使其不被切削成小的区，其目的是保证在以有有大的作业的到来有足够大的空闲区来满足请求者。 最佳适应算法 若存储空间中有正好等于所要求大小的空白区，则必然被选中。若不存在这样的空白区，也只对稍大的空白区划分，而绝不会支划分一个很大的空白区。 由于空白区一般不可能正好和要求的的相等，这往往使剩下的空白区都比较小，形成“碎片”。 寻找一个较大空白区时，要花费较多的时间；回收一个分区时，为了把它插入到空白区链中合适的位置上也要花费较大的代价。,最坏适应算法 克服了最佳适应算法把空闲区切割得太小的缺点，即每次分配时，总是将最大的空闲区切去一部分分配给请求者，其依据是当一个很大的空闲区被切割了一部分后可能仍是一个较大的空闲区。避免了空闲区越分越小的问题，所以很好地利用了碎片。,动态分区的回收算法,检查回收的分区是否与空白区邻接，如有则加以合并，使之成为一个连续的大空白区； 修改可用表或自由链。 空闲释放区与空闲区相邻有四种情况：,空闲区与回收区邻接的情况,上临空闲区：将r合并到f1，f1.addr；f1.size+r.size f.size 下临空闲区：将r合并到f2,，r.addr； r.size+r.size f2.size 上、下临空闲区：f1、r、f2 合并到f1， f1.addr； f1.size+r.size+f2.size f1.size 撤消f2空闲区 上、下都无空闲区： r作为一个空闲区，并插入到空闲区表的适当位置。,碎片和紧缩技术,碎片（零头）：内存中无法利用的小空闲区。有内、外零头之分。,内存紧缩(compaction)：将各个占用分区向内存一端移动。使各个空闲分区聚集在另一端，然后将各个空闲分区合并成为一个空闲分区。也称紧凑、拼接技术。 对占用分区进行内存数据搬移占用CPU时间 如果对占用分区中的程序进行“浮动“，则其重定位需要硬件支持。 紧缩时机：每个分区释放后，或内存分配找不到满足条件的空闲分区时。,思考题,1、固定分区和动态分区分别会出现怎样的碎片（零头）？,固定分区,动态分区,有关分区管理的其它问题讨论,(1) 关于虚拟存储器的实现 分区式管理无法实现那种用户进程所需要内存容量只受内存和外存容量之和限制的虚拟存储器。 如果不采用内存扩充技术，每个用户进程所需内存容量受分区大小限制。,(2) 关于内存扩充 分区式管理中，可以使用覆盖或交换技术来扩充内存。,(3) 关于地址变换和内存保护 静态地址重定位和动态地址重定位技术都可采用。 动态地址重定位时，每个分区需要硬件寄存器支持 保护键法和界限寄存器法都可用保护分区。,(4) 分区管理的主要优缺点 优点： 实现了多个作业或进程对内存的共享。 要求的硬件支持少，管理算法简单，实现容易。 缺点： 内存利用率不高，主要是存储器可能有未用过的信息和碎片问题。 作业的大小或进程大小受分区大小限制。 难以实现各分区间的信息共享。,2. 覆盖（overlay）,引入：其目标是在较小的可用内存中运行较大的程序。常用于多道程序系统，与分区存储管理配合使用。 原理：一个程序的几个代码段或数据段，按照时间先后来占用公共的内存空间。 将程序的必要部分（常用功能）的代码和数据常驻内存； 可选部分（不常用功能）在其他程序模块中实现，平时存放在外存中（覆盖文件），在需要用到时才装入到内存； 不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖。(即不同时用的模块可共用一个分区),注：另一种覆盖方法：(100K) A(20K)占一个分区：20K； B(50K)、D(20K)和E(40K)共用一个分区：50K； F(30K)和C(30K)共用一个分区：30K；,覆盖技术,3. 交换(swapping),引入：多个程序并发执行，可以将暂时不能执行的程序或就绪状态的进程送到外存中，从而获得空闲内存空间来装入新程序。交换单位为整个进程的地址空间。常用于多道程序系统或小型分时系统中，与分区存储管理配合使用。又称作“对换“或“滚进/滚出(roll-in/roll-out)“； 程序暂时不能执行的可能原因：处于阻塞状态，低优先级（确保高优先级程序执行）； 原理：暂停执行内存中的进程，将整个进程的地址空间保存到外存的交换区中（换出swap out），而将外存中由阻塞变为就绪的进程的地址空间读入到内存中，并将该进程送到就绪队列（换入swap in）。,思考题,1、覆盖和交换的区别？ 2、覆盖技术与虚拟存储技术有何本质不同？交换技术和虚存中使用的调入/调出有何相同和不同之处？,5.3 页式存储管理,问题的提出：分区存储管理的主要问题是碎片问题。 在采用分区存储管理的系统中，会形成一些非常小的分区，最终这些非常小的分区不能被系统中的任何用户（程序）利用而浪费。（举例：大礼堂听讲座分座位） 造成这样问题的主要原因是用户程序装入内存时是整体装入的，为解决这个问题，提出了分页存储管理技术（分为：基本分页即纯分页和支持虚存管理的请求分页管理。 ）。,1. 基本概念 2. 请求页式存储管理 3. 页的共享和保护 4.页式存储管理的优缺点,1.页式系统的基本概念,分页的概念 逻辑空间分页：程序地址空间分成大小相等的区域，称为页。每页都有一个编号，叫页号，从0开始编排。页面的大小是为2n ，通常为1KB，2KB，nKB等。 内存空间分块：把内存也分成与页面大小相等的区域，称为内存块或物理块，同样从0开始编排。 内存分配原则：当一个用户程序装入内存时，以块为单位进行分配，并且一个进程的若干页可分别装入物理上不相邻的内存块中。,页大小的例子,计算机系统名 页大小 Atlas 512个48位字 Honeywell-Multics 1024个36位字 IBM 370/XA和370/ESA 4KB VAX系列 512B IBM AS/400 512B DEC Alpha 8KB MIPS 4KB16MB UltraSPARC 8KB4MB Pentium 4KB4MB PowerPC 4KB,逻辑地址表示,在分页存储管理中，用户程序中的逻辑地址（虚地址）包括页号和页内地址（页内位移）。 页号 页内地址（位移量） 15 10 9 0,对于特定的机器来说，其地址结构是一定的，如果给定的逻辑地址是A，页面大小为L，则页号和页内位移可按下式计算： P=INT A/L d=A MOD L 例如，设某系统的页面大小为1KB，A=3456，则P=3，d=384。,？思考： 页面个数和页面大小与P和d的关系？,思考题,设有一页式存储管理系统，向用户提供的逻辑地址空间为16页，每页2048字节，内存总共有8个存储块，请问逻辑地址至少为多少位？内存空间有多大？,逻辑地址：15位 内存空间16K,页表,在分页系统中允许将作业或进程的各页离散地装入内存的任何空闲块中，这样一来就出现了作业的页号连续，而块号不连续的情况。 ？怎样找到每个页面在内存中的对应物理块呢？ 页表是页式存储管理的数据结构，它包括用户程序空间的页面与内存块的对应关系、页面的存储保护和存取控制方面的信息。 页表的结构：,页号 块号 存取控制,页表的作用：进行页号到块号的映射,页式地址映射,地址变换机构,页式地址映射举例,1、虚地址以十进制数给出 页号INT虚地址/页大小 位移量虚地址 mod 页大小 根据题意产生页表； 以页号查页表，得到对应页装入内存的块号 内存地址块号页大小位移量,页式地址映射举例,例2：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、10、5块，试将虚地址7145，3412转换成内存地址。,(1) 虚地址 3412 PINT 3412/2048 1 W 3412 mod 20481364 物理地址： 9*2048+1364=19796,页式地址映射举例,(2) 虚地址 7145 PINT 7145/2048 3 W7145 mod 20481001 物理地址: 5*2048+1001=11241,页式地址映射举例,2、虚地址（逻辑地址、程序地址）以十六进制、八进制、二进制的形式给出。 将虚地址转换成二进制的数； 按页的大小分离出页号和位移量（低位部分是位移量，高位部分是页号）； 根据题意产生页表； 将位移量直接复制到内存地址寄存器的低位部分； 以页号查页表，得到对应页装入内存的块号，并将块号转换成二进制数填入地址寄存器的高位部分，从而形成内存地址。,页式地址映射举例,例1：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、A、5块，试将虚地址0AFEH，1ADDH转换成内存地址。 (1)虚地址0AFEH 0000 1010 1111 1110 P：1 W：010 1111 1110 查页表0100 1010 1111 1110 物理地址：4AFEH,页式地址映射举例,(2)虚地址1ADDH 0001 1010 1101 1101 P：3=（011）2 W：010 1101 1101 查页表 0010 1010 1101 1101 物理地址：2ADDH,04年题,在一分页存储管理系统中，逻辑地址长度为16位，页面大小为4096字节，现有一逻辑地址为2F6AH，且第0、1、2页依次存放在物理块5、10、11中，问相应的物理地址多少？并请画出地址变换图。,逻辑地址2F6AH的二进制表示如下： P：0010 W：1111 0110 1010 由此可知逻辑地址2F6AH的页号为2，该页存放在第11物理块中，用十六进制表示为块号为B，所以物理地址为BF6AH。,联想存储器,在页式存储技术中，我们可看到每访问一次内存，就要做两次访问内存的工作，即，查页表时要作一次访问内存的工作，然后是访问程序要求访问的内存，这样，存取速度降低一倍，将会影响整个系统的使用效率。 采用相应技术加快页表的查询速度。在早期的计算机系统中为了加快查表的速度，增加一个具有并行查找能力的高速缓冲存储器联想存储器，将表放在这个高速缓冲存储器中快表。,采用相应技术加快页表的查询速度,具有快表的地址变换机构 联想寄存器并行查询； 空间大小： 几K到几百K ，部分表项（16512个）； 快表与页表同时访问； 地址映射过程如下：,05年题,在页式系统中，其页表存放在内存中。 (1)如果对内存的一次存取需要100微秒，试问实现一次页面访问至少需要的存取时间是多少？ (2)如果系统有快表，先访问快表在访问页表，快表的命中率为80%，当页表项在快表中时，其查询快表的时间可忽略不计，试问此时的存取时间为多少？ (3)采用快表后的存取时间比没有采用快表的存取时间下降了百分之几？,总结概念,逻辑空间分页，物理空间分块 页与块同样大，页连续块分散 用页号查块号，用硬件做转换 利用快表可加速地址转换,2. 请求页式存储管理,问题的提出 在纯页式存储管理提高了内存的利用效率，但并不为用户提供虚存，换句话说，当一个用户程序的页数大于当前总空闲内存块数时，系统就不能将该程序装入运行。即用户程序将受到物理内存大小的限制。为了解决这个问题，人们提出请求分页存储管理技术。,请求分页概念,请求分页的实现思想 和纯分页的相同点：逻辑空间分页，内存空间分块。 和纯分页的不同点：请求分页技术当一个用户程序要调入内存时，不是将该程序全部装入内存，而是只装入部分页到内存，就可启动程序运行，在运行的过程中，如果发现要运行的程序或要访问数据不在内存，则向系统发出缺页中断请求，系统在处理这个中断时，将在外存相应的页调入内存，该程序继续运行。,请求分页要解决的问题,采用这种技术要解决以下问题： (1) 如何发现执行的程序或访问的数据不在内存； (2) 程序或数据什么时候调入内存，调入策略； (3) 当一些页调入内存时，内存没有空闲内存时，将淘汰哪些页，淘汰策略。,数据结构 为了实现请求分页技术，页表应增加相应的内容，反映该页是否在内存，在外存的位置，在内存的时间的长短等。 中断位（状态位）：0 表示该页在内存；1表示该页不在内存。如果不在内存，给出在辅存的地址 引用位：0 表示最近没有进程访问；1表示最近有进程访问 修改位： 0 该页调入内存后没有修改；1表示该页调入内存后修改过,数据结构,调入策略 (1) 预调 系统根据作业（进程）运行的情况，预测哪些页将要运行，在其运行之前先行调入内存，这样在程序运行的过程中就不会出现缺页中断。这样方法从表面上看起来很好，但系统无法预计系统中作业的运行情况，难以实现。 (2) 请调 进程在执行的过程中，发现要执行的程序或处理的数据不在内存，向系统提出调入相应程序的请求，系统响应用户的请求。,淘汰策略 当要访问的页面不在内存时，就产生一个缺页中断信号，此时用户程序被中断，转OS的调页程序把该页调入到内存，如果此时内存无空闲块，必须把已在内存中的某一页淘汰掉。用来选择淘汰哪一页的规则叫置换算法。 刚被淘汰出去的页，过后不久又要访问，而调入不久又被淘汰，然后又要访问，又调入，如此反复，使得系统把大部分时间用在了页面的调进和调出上抖动、颠簸 好的页面置换算法能适当降低页面的更换频率，尽量避免系统“抖动”，评价指标缺页次数和缺页率,请求页式管理中的置换算法,目的：选出一个被淘汰的页面，该页应该是被访问概率最低的页。 常见的置换算法有4种： (1) 随机淘汰算法（Random Glongram） (2) 轮转法（Round Robin）和先进先出(FIFO) (3) 最近最久未使用页面置换算法（Least recent Used） (4) 理想型淘汰算法OPT（Optimal Replacement Algorithm）,(1) 随机淘汰算法,在系统设计人员无法确定哪些页被访问的概率较低时，明智的作法是随机地选择某个用户的页并将其换出。,(2) 轮转法和先进先出法,轮转法：循环换出内存可用区内一个可以被换出的页，无论该页是刚被换进或已换进内存很长时间。 FIFO法：总是选择在内存驻留时间最长的一页将其淘汰。,思想：先进入内存的页，先退出内存。 实质：淘汰在内存驻留时间最长的页。 理由：最早调入内存的页，不再被使用的可能性比近期调入内存的大。 FIFO算法简单，实现容易。,由实验和测试发现FIFO算法和RR算法的内存利用率不高。,FIFO和RR内存利用率低的原因,两种算法都是基于处理器按线性顺序访问地址空间这一假设。事实上，许多时候，处理器不是按线性顺序访问地址空间的。例如，执行循环结构的程序段。 使用FIFO算法时，在未给进程或作业分配足够它所需要的页面数时，有时会出现分配的页面数增，缺页次数反而增加的现象（Belady现象）。,FIFO的Belady现象,举例,例1：正常现象举例（1/2）,设进程P共有8页，且已在内存中分配有3个页面，程序访问内存的顺序为见下表，按FIFO法换页。,访问页数：17次 缺页次数：12次 缺页率=12/17=70.5%,例1：正常现象举例（2/2）,给进程P分配4个页页，访问页面情况如下表。,访问页数：17次 缺页次数：9次 缺页率=9/17=52.9%,例2：Belady现象举例（1/2）,给进程共分配4个页面，程序访问内存的顺序如前，按FIFO法换页。,访问页数：12次 缺页次数：9次 缺页率=9/12=75%,例2：Belady现象举例（2/2）,设进程P共有5，且已在内存中分配有4个页面，程序访问内存的顺序见下表。,访问页数：12次 缺页次数：10次 缺页率=10/12=83.3%,(3)最近最久未使用页面(LRU)置换算法,基本思想： 当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。即当需要淘汰一页时，选择最长时间未使用的页。 基于假设： 如果某页被访问，它可能马上还要被访问；相反，如果某页长时间未被访问，它可能最近也不可能被访问。 算法的实现（软件）： 为每页设置一个特定的单元，用于记录自上次访问以来所经历的时间t，当需要置换一页时，选择t最大的淘汰。,举例,例：LRU置换算法举例,设进程P共有8页，且已在内存中分配有3个页面，程序访问内存的顺序为见下表，按LRU法换页。,访问页数：17次 缺页次数：11次 缺页率=11/17=64.7%,LRU的近似算法,要完全实现LRU算法是一件十分困难的事件，在实际系统中往往使用LRU的近似算法。 比较常用的近似算法有： a)最不经常使用页面淘汰算法LFU（Least Frequently Used） b)最近没有使用页面淘汰算法NUR（Not Used Recently）,a)最不经常使用页面淘汰算法,基本思想：需要淘汰某一页时，首先淘汰到当前时间为止，被访问次数最少的那一页。 算法的实现：修改页表 在页表中给一页增设一个访问计数器，即可实现。每当该页被访问时，访问计数器加1。 发生缺页中断时，淘汰计数值最小的那一页，并将其计数器清0。,b)最近没有使用页面淘汰算法,基本思想：需要淘汰某一页时，从那些最近一个时期未被访问的页中任选一页淘汰。 算法的实现：修改页表 在页表中增设一个访问位，当某页被访问时，访问位置1；否则，访问位置0。系统周期性地对所有引用位清0。 当需要淘汰一页时，从那些访问位为0的页中选一页进行淘汰。,(4) 理想型淘汰算法（OPT，最佳置换算法）,基本思想：当要调入一新页而必须淘汰一旧页时，所淘汰的页是以后不再使用的，或者是以后相当长的时间内不会使用的。 这种算法无法实现，因为，它要求必须预先知道每一个进程的访问串。,思考题,在一个请求分页存储管理系统中，一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5当分配给该作业的内存块分别为3、4个时，试分别计算采用下述页面淘汰算法时的缺页率（假设最初主存中没有页面），并比较所得结果。,（1）OPT （2）FIFO （3）LRU,某程序在内存中分配三个页面，初始为空，页面走向为4，3，2，1，4，3，5，4，3，2，1，5。,3. 页的共享和保护,页式管理可以为内存提供2种方式的保护： 地址越界保护 若0页号用户程序的总页数，则访问合法，否则访问越界。 存储控制保护：在页表中增加存取控制位，表示该页的存取控制权限，如r表示可读，w表示可读可写，e表示可执行。当有一程序访问该页时，系统就按存取控制位设置的权限实施存取控制。,4. 页式管理的优缺点,优点： 它不要求连续存放，从而有效地解决了碎片问题。 支持虚存 缺点： 要求有相应的硬件支持：DAT，缺页中断的产生 增加了系统开销：处理缺页中断 请求调页的算法不当，可能产生抖动现象 存在“内碎片”问题：最后一页内总有部分空间得不到利用。 不利于程序和数据的共享,5.4 段式存储管理,问题的提出：前面介绍的几种存储管理技术中，提供给用户的逻辑地址空间是一维线形的，与内存的物理组织基本相同，但用户编写的程序逻辑结构却不是这样。 通常，编写的程序由若干程序模块和数据模块组成。 为了满足用户（程序员）在编程和使用等方面的需求，引入了分段存储管理技术,1. 基本概念 2. 分段存储管理的基本原理 3. 段的共享和保护 4. 段式存储管理的优缺点,1. 基本概念,(1) 段式管理的基本思想,段式管理是基于分区式管理和页式管理的缺陷和不足而提出的一种更复杂的内存管理方式： 分区式和页式管理时的进程地址空间结构是线性的。 不同作业或进程之间共享公用子程序和数据变得非常困难： 不能按名共享程序和数据； 一个页内不能保证是逻辑上完整的子程序或数据块 只能采用静态链接。,(2) 分段 一个用户程序往往由几个程序段（主程序、子程序和函数）所组成，把程序按内容或过程（函数）关系分段，每段有自己的名字（段号）。每个段都从0开始编址，采用一段连续的地址空间。各段的长度可以不等。,(3) 段式管理的程序地址结构 段式管理把二维虚拟地址空间设计成段号S与段内相对地址W。 段式虚拟地址空间包括： 段名 ：段内地址 段号之间无顺序关系，段长也不固定，每个段定义一组逻辑上完整的程序或数据。 根据需要，段长可动态增长。,(4) 段式管理的内存分配 段式管理以段为单位分配内存，然后再通过地址映射机构把段式虚拟地址转换成实际的内存物理地址。 只把那些经常访问的段驻留内存，而把那些将来一段时间内不被访问的段放入外存，等需要时自动调入内存中。,(5)段表和段表寄存器 段式管理程序在进行初始内存分配之前，根据用户要求的内存大小为一个作业或进程建立一个段表，以实现动态地址变换和缺段中断处理及存储保护等。 段表为每个逻辑段找出所对应的物理内存中块的位置 段表通常放在内存，为了方便找到运行进程的段表，系统还要建立一个段表地址寄存器：段表在内存的起始地址和段表的长度,段 表,段号：与段名一一对应 始址：该段在内存或外存的物理地址 长度：该段在内存或外存的实际长度 存取方式：存取保护用。如PSW控制位与其相同可访问 状态位：指出该段在内存或外存 访问位：淘汰算法需要而设，如本段在一段时间内被访问的次数。 修改位：本段进入内存后是否被修改过，如修改过，则本段被置换出内存时需写回外存。,(6)分页和分段的异同之处 相同点：在内存中都不是整体连续，均通过地址映射机构将逻辑地址映射到物理内存。,不同点： 页是信息的物理单位。用户不需要把程序分页，完全是系统管理的要求。 段是信息的逻辑单位。每一段在逻辑上是相对完整的一组信息。分段更好地满足了用户的需求。 页的大小是固定的，且在同一系统中大小相等。 段的大小因段而异，取决于用户编写的程序。 分页的作业地址空间是一维的。 分段的作业地址空间是二维的。,2. 分段存储管理的基本原理,(1) 段式管理的内存分配与释放 段式管理中以段为单位分配内存，每段分配一个连续的内存区，同一进程所包含的各段之间不要求连续。 内存分配与释放在作业或进程的执行过程中动态进行。 段式管理时的内存分配要分两种情况：有无足够空闲区满足需求。 段式管理中内存回收方法可以用动态分区管理时用的内存回收方法。,内存的申请分2种情况,进程要求调入某段时，内存中有足够的空闲区满足该段的内存要求：动态分区式管理时所用的分配算法都可用来作为段式管理时的内存分配，如：最先适应法、最佳适应法、最坏适应法。 内存中没有足够的空闲区满足该段的内存要求，此时根据给定的置换算法淘汰内存中一个或几个段，可以使用页式存储管理中的置换算法，如：FIFO置换算法、LRU算法及其近似算法。,除了段的初始分配之外，段的动态分配是在处理器所要访问的指令和数据不在内存时产生缺段中断的情况下发生的。段的淘汰或置换算法实际上是缺段中断处理过程的一部分。,缺段中断处理过程,需调入新段X,内存中有不小于X段长的空闲区吗？,内存中所有空闲区总和小于X段长吗？,按一定算法反复淘汰旧段，以形成一个长度不小于X段长的空闲区,合并空闲区以形成长度不小于X段长的空闲区,为X段分配内存空闲区,将X段调入内存并改写段表,返回,N,N,Y,Y,(2) 段式管理的地址变换,段管理程序进行地址变换的步骤: 把该进程的段表始址放入段表地址寄存器； 由虚地址中的段号比较段表地址寄存器中的段表长度，若0段号用户程序的总段数，则访问合法，否则访问越界。 由虚地址中的段号S为索引，查找段表； 若该段在内存，则判断其存取控制方式是否有错和段内位移是是否超过段长，若都正确，则从段表相应表目中查出该段在内存的起始地址，并将其和段内相对地址W相加，从而得到实际内存地址。 若该段不在内存，则产生缺段中断将处理器控制权交给内存分配程序。,段式存储管理的地址转换,段号 段始址 段长,内存,段内位移大于段长发生中断,段超长中断,8292,段式地址映射举例,例：有一系统采用段式存储管理，其段表如下，试将下述虚地址转换成内存地址。,(2)2,500： (3)3,400 ： (4)4,112： (5)5,32：,试将下述虚地址转换成内存地址:,段号 段始址 段长 210 500 1 2350 20 2 100 90 3 1350 590 4 1938 95,(1)0,430 物理地址： 210+430=640,(3) 段的共享与保护,段的共享,段是按逻辑意义来划分的，可以按段名访问，这极有利于段的共享。 如果进程或作业需要共享内存中的某程序段