存储管理97课件

第五章存储管理5.1概述5.2存储管理基本技术5.3页式管理5.4段式管理5.5段页式管理

存储器是计算机系统的重要资源之一。因为任何程序和数据以及各种控制用的数据结构都必须占用一定的存储空间，因此，存储管理直接影响系统性能。存储器由内存(primarystorage)和外存(secondarystorage)组成。本章讨论的主要是内存管理问题，包括如下内容：学习目标：

1.掌握：存储管理的功能、常用存储管理技术、虚拟存储器的概念，分页、分段的概念，以及页式、段式、段页式存储管理技术和虚存中的置换算法。

2.理解：存储器层次、存储分配。3.了解：局部性原理和抖动问题。学习要点：

本章涉及到的概念和管理技术较多，通过比较，理解如下概念：逻辑地址、物理地址、静态重定位、动态重定位、碎片、虚拟存储器；对于每一种存储管理技术应理解它解决什么问题，实现的思想，以及它带来的好处和存在的问题。5.1概述返回1.存储器的层次2.存储管理的功能3.存储分配的方式4.重定位5.内存信息的共享与保护6.虚拟存储器内存储器（简称内存、主存、物理存储器）处理机能直接访问的存储器。用来存放系统和用户的程序和数据，其特点是存取速度快，存储方式是以新换旧，断电信息丢失。外存储器（简称外存、辅助存储器）处理机不能直接访问的存储器。用来存放用户的各种信息，存取速度相对内存而言要慢得多，但它可用来长期保存用户信息。在文件系统中介绍。内存的物理组织物理地址：把内存分成若干个大小相等的存储单元，每个单元给一个编号，这个编号称为内存地址（物理地址、绝对地址、实地址），存储单元占8位，称作字节（byte）。物理地址空间：物理地址的集合称为物理地址空间（主存地址空间），它是一个一维的线性空间。程序的逻辑结构程序地址：用户编程序时所用的地址（或称逻辑地址、虚地址），基本单位可与内存的基本单位相同，也可以不相同。程序地址空间（逻辑地址空间、虚地址空间）：用户的程序地址的集合称为逻辑地址空间，它的编址总是从0开始的，可以是一维线性空间，也可以是多维空间。2.存储器的功能①存储分配和回收：按照一定的算法把某一空闲的主存区分配给作业或进程以及回收系统或用户释放的空间。②地址变换：将程序地址空间中使用的逻辑地址变换成主存中的地址的过程程序加载(装入)时的重定位技术可执行文件生成中的链接技术进程运行时硬件和软件的地址变换技术和机构③存储共享和保护：保证用户程序(或进程映象)共享主存中的数据，并且在各自的存储区域内操作，互不干扰。代码和数据共享地址空间访问权限（读、写、执行）④存储器扩充：使用户程序的大小和结构不受主存容量和结构的限制。由应用程序控制：覆盖；由OS控制：交换（整个进程空间），虚拟存储的请求调入和预调入（部分进程空间）目前绝大多数系统都采用的是静态或动态存储分配方式分析用户程序的主要处理阶段：编辑：形成源文件编译：形成目标模块链接：由多个目标模块或程序库生成可执行文件装入：构造PCB，形成进程(使用物理地址)运行：建立的进程在CPU在执行装入阶段：程序必须装到内存才能运行，这需要装入程序根据内存的使用情况和分配策略，将上述装入模块放入分到的内存中。这时，可能要进行地址映射（重定位）逻辑地址、物理地址和地址映射逻辑地址（相对地址，虚地址）：用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式。其首地址为0，其余指令中的地址都相对于首地址来编址。不能用逻辑地址在内存中读取信息。物理地址（绝对地址，实地址）：内存中存储单元的地址。物理地址可直接寻址。地址映射：将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址。当程序装入内存时,操作系统要为该程序分配一个合适的内存空间，由于程序的逻辑地址与分配到内存物理地址不一致,而CPU执行指令时，是按物理地址进行的，所以要进行地址转换。4.重定位

重定位（地址映射）：在可执行文件装入时需要解决可执行文件中地址（指令和数据）和内存地址的对应。由操作系统中的装入程序loader来完成。重定位方法：地址映射的功能就是要建立虚实地址的对应关系，实现地址映射有三种方式：绝对装入：编程或编译时确定地址映射关系可重定位装入（静态地址映射）：程序执行前，装入内存时一次性链接装入程序。动态装入（动态地址映射）：处理机每次访问主存时，有动态地址变换机构（硬件）自动执行。绝对装入绝对装入：编程或编译时确定地址映射关系编程时确定虚－实地址的关系是指在用机器指令编程时，程序员直接按物理内存地址编程，这种程序在系统中是不能做任何移动的，否则就会出错。优点：装入过程简单。缺点：过于依赖于硬件结构，不适于多道程序系统。可重定位装入静态地址映射：在程序装入内存时完成从逻辑地址到物理地址的转换的。在一些早期的系统中都有一个装入程序（加载程序），它负责将用户程序装入系统，并将用户程序中使用的访问内存的逻辑地址转换成物理地址。如下图所示。优点：实现简单，不要硬件的支持。缺点：一个程序通常需要占用连续的内存空间，程序装入内存后不能移动。不易实现共享。5.内存信息的共享和保护

在多道程序设计的环境下，系统中有系统程序和多个用户程序同时存在，用户程序间可以共享内存中的信息，但要保证用户程序不破坏系统程序，用户程序之间不相互干扰，这就是存储保护所要解决的问题。存储保护的目的：保护系统程序区不被用户侵犯（有意或无意的）不允许用户程序读写不属于自己地址空间的数据（系统区地址空间，其他用户程序的地址空间）存储保护类型界限保护（上界寄存器/下界寄存器或基址寄存器/限长寄存器）：所有访问地址必须在上下界之间；每个进程都有自己独立的进程空间，如果一个进程在运行时所产生的地址在其地址空间之外，则发生地址越界。当程序要访问某个内存单元时，由硬件检查是否允许，如果允许则执行，否则产生地址越界中断，由操作系统进行相应处理。访问方式保护（保护键）：通过保护键匹配来判断存储访问方式是否合法。对于允许多个进程共享的存储区域，每个进程都有自己的访问权限。如果一个进程对共享区域的访问违反了权限规定，则发生操作越权(即读写保护)。对每个内存区域指定一个键值和若干禁止的访问方式，进程中也指定键值，如果访问时键值不匹配而且是被禁止的访问方式，则出错。上下界保护下界寄存器：存放程序装入内存后的开始地址（首址）上界寄存器：存放程序装入内存后的末地址判别式：下界寄存器≤物理地址≤上界寄存器基址、限长寄存器保护例：有一程序装入内存的首地址是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）固定分区分配…………256K512K5未使用124K132K4未使用60K64K328K32K220K8K1状态位置大小区号系统区分区1分区4分区5分区2分区3系统区作业3分区4作业2作业1分区3…………正使用256K512K5未使用124K132K4未使用60K64K3正使用28K32K2正使用20K8K1状态位置大小区号未使用未使用未使用作业1：25k作业2：150k作业3：6k存储保护与重定位（地址转换）每个分区（一道程序）对应一对界地址寄存器：上/下限寄存器。采用静态重定位方式，即由链接/装入程序完成。优缺点优点：简单，要求的硬件支持少；缺点：存在大的碎片，主存利用率低。动态分区法思想位置和大小都不固定，应作业的要求而设置。数据结构的三种形式空闲分区表(可用表)空闲分区链(自由链)请求表：描述请求内存资源的作业或进程号及所请求的内存大小动态分区存储管理技术系统生成后，操作系统占用内存的一部分，一般在物理内存的开始处，比如，一个操作系统占20KB，装入系统后占用0～20KB的内存空间，剩下的部分作为一个空闲区，当一个用户程序（作业、进程）调入内存时，把这个空闲区的低地址部分的区域分配给它，如图所示。动态分区分配OS区Job1Job2Job3Job4Job5Job6Job7OS区Job1Job2Job3Job4Job5自由链头指针Job7Job6分区的分配与回收

内存分配程序包括分配一个分区和释放一个分区两个函数，当进程需要一个大小为size的内存时，可以通过系统调用向系统申请。申请一个分区返回：成功为分区的首地址，失败为0释放一个分区返回：无固定分区的分配与回收分配算法见下页图回收算法简单，只要将对应的分区状态置为未使用。固定分区分配操作（分配算法流程）查找分区说明表第一项表结束否？该分区空闲吗？X≦分区长度?修改状态位为正在使用返回分区号继续检索下一个表项YYNNNY请求X大小分区无法分配

动态分区时的分配与回收动态分区的分配算法：从可用表或自由链中找到一个足以容纳该作业的可用空白区；若这个空白区比所需求大，则将它分成2个部分：一部分成为已分配区，剩下部分仍为空白区。修改可用表或自由链，并回送一个所分配区的序号或该分区的始址。动态分区分配算法的关键：从空白区中寻找空闲空间是关键。寻找空白区方法的不同：分区分配是对可用表（或自由链）数据结构进行操作，空闲区表的组织有两种方法：按空闲区大小的升序（降序）组织；按空闲区首址升序（降序）组织。通常有3种寻找空白区的方法：最先适应法最佳适应法最坏适应法最先匹配法(first-fit)：按分区起始地址的递增次序，从头查找，找到符合要求的第一个分区。该算法的分配和释放的时间性能较好，一旦找到大于或等于所要求内存长度的分区，则结束探索。最佳匹配法(best-fit)：按分区大小的递增次序，查找，找到符合要求的第一个分区。当申请空闲区时，存储管理程序从表头开始查找，当找到一个满足要求的空闲区时，停止查找，此时的空白区必定是最合适的，因为它是最接近于要求的大小。最坏匹配法(worst-fit)：按分区大小的递减次序，从头查找，找到符合要求的第一个分区。找到最大的空闲分区查找空闲分区链表第一项检索完否？分区大小>=size?分区大小=size?划出size大小的分区修改有关的数据结构返回将该分区从链表中移出继续检索下一个表项YYYNNN最先适应算法流程分配策略——最先适应法最先适应法（首次适应算法）：首次适应算法的表是按空闲区首址升序的（即空闲区表是按空闲区首址从小到大）方法组织的。

分配时从表首开始，以请求内存区的大小逐个与空闲区进行比较，找到第一个满足要求的空闲后，若空闲区大小与请求区的大小相等，则将该空闲区分配给请求者，并撤消该空闲区所在表目；若大于请求区，就将该空闲区的一部分分配给请求者，然后，修改空闲区的大小和首址。

切割空闲区有两种方法：从空闲区头开始或从空闲区尾开始空闲区大小50KB，首址156KB，申请34KB。分配策略——最佳适应法最佳适应算法：空闲区表按空闲区大小升序方法组织。分配时，按申请的大小逐个与空闲区大小进行比较，找到一个满足要求的空闲区，就说明它是最适合的（即最佳的）。分配策略——最坏适应法

最坏适应算法的空闲区表是按空闲区大小降序的方法组织的（从大到小的顺序）。分配时总是取表中的第一个表目，若不能满足申请者的要求，则表示系统中无满足要求的空闲区，分配失败；否则，将从该空闲区中分配给申请者，然后修改空闲区的大小，并将它插入到空闲区表的适当位置。三种分配算法举例分析这三种放置算法的优劣很难区分，要具体情况具体分析。例如：某时刻系统中有三个空闲区其大小和首址为：(35KB，100KB)(12KB，156KB)(28KB，200KB)有一作业系列：(JOB1，12KB)(JOB2，30KB)(JOB3，28KB)三种分配算法的比较最先（首次）适应算法实质是尽可能地利用低地址部分的空闲区，而尽量地保证高地址部分的大空闲区，使其不被切削成小的区，其目的是保证在以有有大的作业的到来有足够大的空闲区来满足请求者。最佳适应算法若存储空间中有正好等于所要求大小的空白区，则必然被选中。若不存在这样的空白区，也只对稍大的空白区划分，而绝不会支划分一个很大的空白区。由于空白区一般不可能正好和要求的的相等，这往往使剩下的空白区都比较小，形成“碎片”。寻找一个较大空白区时，要花费较多的时间；回收一个分区时，为了把它插入到空白区链中合适的位置上也要花费较大的代价。最坏适应算法克服了最佳适应算法把空闲区切割得太小的缺点，即每次分配时，总是将最大的空闲区切去一部分分配给请求者，其依据是当一个很大的空闲区被切割了一部分后可能仍是一个较大的空闲区。避免了空闲区越分越小的问题，所以很好地利用了碎片。动态分区的回收算法检查回收的分区是否与空白区邻接，如有则加以合并，使之成为一个连续的大空白区；修改可用表或自由链。空闲释放区与空闲区相邻有四种情况：空闲区与回收区邻接的情况上空闲区f1回收区r下空闲区f2上空闲区f1回收区r回收区r下空闲区f2回收区r上临空闲区：将r合并到f1，f1.addr；f1.size+r.sizef.size下临空闲区：将r合并到f2,，r.addr；r.size+r.sizef2.size上、下临空闲区：f1、r、f2合并到f1，f1.addr；f1.size+r.size+f2.sizef1.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.交换(s)引入：多个程序并发执行，可以将暂时不能执行的程序或就绪状态的进程送到外存中，从而获得空闲内存空间来装入新程序。交换单位为整个进程的地址空间。常用于多道程序系统或小型分时系统中，与分区存储管理配合使用。又称作"对换"或"滚进/滚出(roll-in/roll-out)"；程序暂时不能执行的可能原因：处于阻塞状态，低优先级（确保高优先级程序执行）；原理：暂停执行内存中的进程，将整个进程的地址空间保存到外存的交换区中（换出s），而将外存中由阻塞变为就绪的进程的地址空间读入到内存中，并将该进程送到就绪队列（换入s）。思考题1、覆盖和交换的区别？2、覆盖技术与虚拟存储技术有何本质不同？交换技术和虚存中使用的调入/调出有何相同和不同之处？5.3页式存储管理问题的提出：分区存储管理的主要问题是碎片问题。在采用分区存储管理的系统中，会形成一些非常小的分区，最终这些非常小的分区不能被系统中的任何用户（程序）利用而浪费。（举例：大礼堂听讲座分座位）

造成这样问题的主要原因是用户程序装入内存时是整体装入的，为解决这个问题，提出了分页存储管理技术（分为：基本分页即纯分页和支持虚存管理的请求分页管理。）。1.基本概念2.请求页式存储管理3.页的共享和保护4.页式存储管理的优缺点1.页式系统的基本概念分页的概念逻辑空间分页：程序地址空间分成大小相等的区域，称为页。每页都有一个编号，叫页号，从0开始编排。页面的大小是为2n，通常为1KB，2KB，nKB等。内存空间分块：把内存也分成与页面大小相等的区域，称为内存块或物理块，同样从0开始编排。内存分配原则：当一个用户程序装入内存时，以块为单位进行分配，并且一个进程的若干页可分别装入物理上不相邻的内存块中。页大小的例子计算机系统名 页大小Atlas 512个48位字Honeywell-Multics 1024个36位字IBM370/XA和370/ESA 4KBVAX系列 512BIBMAS/400 512BDECAlpha 8KBMIPS 4KB~16MBUltraSPARC 8KB~4MBPentium 4KB~4MBPowerPC 4KB逻辑地址表示在分页存储管理中，用户程序中的逻辑地址（虚地址）包括页号和页内地址（页内位移）。

页号页内地址（位移量）151090页号P页内位移d对于特定的机器来说，其地址结构是一定的，如果给定的逻辑地址是A，页面大小为L，则页号和页内位移可按下式计算：

P=INT[A/L]d=AMODL

例如，设某系统的页面大小为1KB，A=3456，则P=3，d=384。？？？思考：页面个数和页面大小与P和d的关系？思考题设有一页式存储管理系统，向用户提供的逻辑地址空间为16页，每页2048字节，内存总共有8个存储块，请问逻辑地址至少为多少位？内存空间有多大？逻辑地址：15位内存空间16K页表

在分页系统中允许将作业或进程的各页离散地装入内存的任何空闲块中，这样一来就出现了作业的页号连续，而块号不连续的情况。？？？怎样找到每个页面在内存中的对应物理块呢？页表是页式存储管理的数据结构，它包括用户程序空间的页面与内存块的对应关系、页面的存储保护和存取控制方面的信息。页表的结构：页号块号存取控制页表的作用：进行页号到块号的映射页式地址映射页表始址页表长度页表寄存器<页表块号页号538271208452物理地址2452逻辑地址越界中断内存8644地址变换机构页式地址映射举例1、虚地址以十进制数给出页号＝INT[虚地址/页大小]位移量＝虚地址mod页大小根据题意产生页表；以页号查页表，得到对应页装入内存的块号内存地址＝块号×页大小＋位移量页式地址映射举例

例2：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、10、5块，试将虚地址7145，3412转换成内存地址。(1)虚地址3412P＝INT[3412/2048]＝1W＝3412mod2048＝1364物理地址：9*2048+1364=19796页式地址映射举例(2)虚地址7145

P＝INT[7145/2048]＝3W＝7145mod2048＝1001物理地址:5*2048+1001=11241页式地址映射举例2、虚地址（逻辑地址、程序地址）以十六进制、八进制、二进制的形式给出。将虚地址转换成二进制的数；按页的大小分离出页号和位移量（低位部分是位移量，高位部分是页号）；根据题意产生页表；将位移量直接复制到内存地址寄存器的低位部分；以页号查页表，得到对应页装入内存的块号，并将块号转换成二进制数填入地址寄存器的高位部分，从而形成内存地址。页式地址映射举例例1：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、A、5块，试将虚地址0AFEH，1ADDH转换成内存地址。(1)虚地址0AFEH

00001010

11111110P：1W：01011111110查页表0100

101011111110物理地址：4AFEH页式地址映射举例(2)虚地址1ADDH00011010

11011101P：3=（011）2W：01011011101查页表00101010

11011101物理地址：2ADDH04年题在一分页存储管理系统中，逻辑地址长度为16位，页面大小为4096字节，现有一逻辑地址为2F6AH，且第0、1、2页依次存放在物理块5、10、11中，问相应的物理地址多少？并请画出地址变换图。逻辑地址2F6AH的二进制表示如下：P：0010W：111101101010

由此可知逻辑地址2F6AH的页号为2，该页存放在第11物理块中，用十六进制表示为块号为B，所以物理地址为BF6AH。联想存储器

在页式存储技术中，我们可看到每访问一次内存，就要做两次访问内存的工作，即，查页表时要作一次访问内存的工作，然后是访问程序要求访问的内存，这样，存取速度降低一倍，将会影响整个系统的使用效率。采用相应技术加快页表的查询速度。在早期的计算机系统中为了加快查表的速度，增加一个具有并行查找能力的高速缓冲存储器——联想存储器，将表放在这个高速缓冲存储器中——快表。

采用相应技术加快页表的查询速度

具有快表的地址变换机构联想寄存器——并行查询；空间大小：几K到几百K，部分表项（16~512个）；快表与页表同时访问；地址映射过程如下：页表始址页表长度页表寄存器﹥页表块号页号5332712031250物理地址21250逻辑地址越界中断快表块号页号2051145320联想寄存器05年题在页式系统中，其页表存放在内存中。(1)如果对内存的一次存取需要100微秒，试问实现一次页面访问至少需要的存取时间是多少？(2)如果系统有快表，先访问快表在访问页表，快表的命中率为80%，当页表项在快表中时，其查询快表的时间可忽略不计，试问此时的存取时间为多少？(3)采用快表后的存取时间比没有采用快表的存取时间下降了百分之几？

总结概念逻辑空间分页，物理空间分块页与块同样大，页连续块分散用页号查块号，用硬件做转换利用快表可加速地址转换2.请求页式存储管理

问题的提出

在纯页式存储管理提高了内存的利用效率，但并不为用户提供虚存，换句话说，当一个用户程序的页数大于当前总空闲内存块数时，系统就不能将该程序装入运行。即用户程序将受到物理内存大小的限制。为了解决这个问题，人们提出请求分页存储管理技术。请求分页概念请求分页的实现思想和纯分页的相同点：逻辑空间分页，内存空间分块。和纯分页的不同点：请求分页技术当一个用户程序要调入内存时，不是将该程序全部装入内存，而是只装入部分页到内存，就可启动程序运行，在运行的过程中，如果发现要运行的程序或要访问数据不在内存，则向系统发出缺页中断请求，系统在处理这个中断时，将在外存相应的页调入内存，该程序继续运行。请求分页要解决的问题采用这种技术要解决以下问题：

(1)如何发现执行的程序或访问的数据不在内存；

(2)程序或数据什么时候调入内存，调入策略；

(3)当一些页调入内存时，内存没有空闲内存时，将淘汰哪些页，淘汰策略。

数据结构

为了实现请求分页技术，页表应增加相应的内容，反映该页是否在内存，在外存的位置，在内存的时间的长短等。中断位（状态位）：0表示该页在内存；1表示该页不在内存。如果不在内存，给出在辅存的地址引用位：0表示最近没有进程访问；1表示最近有进程访问修改位：0该页调入内存后没有修改；1表示该页调入内存后修改过数据结构调入策略

(1)预调系统根据作业（进程）运行的情况，预测哪些页将要运行，在其运行之前先行调入内存，这样在程序运行的过程中就不会出现缺页中断。这样方法从表面上看起来很好，但系统无法预计系统中作业的运行情况，难以实现。(2)请调进程在执行的过程中，发现要执行的程序或处理的数据不在内存，向系统提出调入相应程序的请求，系统响应用户的请求。淘汰策略当要访问的页面不在内存时，就产生一个缺页中断信号，此时用户程序被中断，转OS的调页程序把该页调入到内存，如果此时内存无空闲块，必须把已在内存中的某一页淘汰掉。用来选择淘汰哪一页的规则叫置换算法。

刚被淘汰出去的页，过后不久又要访问，而调入不久又被淘汰，然后又要访问，又调入，如此反复，使得系统把大部分时间用在了页面的调进和调出上——抖动、颠簸

好的页面置换算法能适当降低页面的更换频率，尽量避免系统“抖动”，评价指标——缺页次数和缺页率请求页式管理中的置换算法目的：选出一个被淘汰的页面，该页应该是被访问概率最低的页。常见的置换算法有4种：(1)

随机淘汰算法（RandomGlongram）(2)

轮转法（RoundRobin）和先进先出(FIFO)(3)

最近最久未使用页面置换算法（LeastrecentUsed）(4)

理想型淘汰算法OPT（OptimalReplacementAlgorithm）(1)随机淘汰算法在系统设计人员无法确定哪些页被访问的概率较低时，明智的作法是随机地选择某个用户的页并将其换出。(2)轮转法和先进先出法轮转法：循环换出内存可用区内一个可以被换出的页，无论该页是刚被换进或已换进内存很长时间。FIFO法：总是选择在内存驻留时间最长的一页将其淘汰。思想：先进入内存的页，先退出内存。实质：淘汰在内存驻留时间最长的页。理由：最早调入内存的页，不再被使用的可能性比近期调入内存的大。FIFO算法简单，实现容易。由实验和测试发现FIFO算法和RR算法的内存利用率不高。FIFO和RR内存利用率低的原因两种算法都是基于处理器按线性顺序访问地址空间这一假设。事实上，许多时候，处理器不是按线性顺序访问地址空间的。例如，执行循环结构的程序段。使用FIFO算法时，在未给进程或作业分配足够它所需要的页面数时，有时会出现分配的页面数增，缺页次数反而增加的现象（Belady现象）。FIFO的Belady现象0m分配页面数缺页次数(a)正常情况0m分配页面数缺页次数(b)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（LeastFrequentlyUsed）b)最近没有使用页面淘汰算法NUR（NotUsedRecently）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开始编址，采用一段连续的地址空间。各段的长度可以不等。

……CALL[X]|<Y>……LOAD1,[A]|<D>……STORE1,[B]|<C>……01K

……Y：……0500分段X（子程序）

……D：……0300分段A（数组）

……C：……0200分段B（工作区）(3)段式管理的程序地址结构段式管理把二维虚拟地址空间设计成段号S与段内相对地址W。段式虚拟地址空间包括：

段名：段内地址段号之间无顺序关系，段长也不固定，每个段定义一组逻辑上完整的程序或数据。根据需要，段长可动态增长。(4)段式管理的内存分配段式管理以段为单位分配内存，然后再通过地址映射机构把段式虚拟地址转换成实际的内存物理地址。只把那些经常访问的段驻留内存，而把那些将来一段时间内不被访问的段放入外存，等需要时自动调入内存中。(5)段表和段表寄存器段式管理程序在进行初始内存分配之前，根据用户要求的内存大小为一个作业或进程建立一个段表，以实现动态地址变换和缺段中断处理及存储保护等。段表为每个逻辑段找出所对应的物理内存中块的位置段表通常放在内存，为了方便找到运行进程的段表，系统还要建立一个段表地址寄存器：段表在内存的起始地址和段表的长度段表段号：与段名一一对应始址：该段在内存或外存的物理地址长度：该段在内存或外存的实际长度存取方式：存取保护用。如PSW控制位与其相同可访问状态位：指出该段在内存或外存访问位：淘汰算法需要而设，如本段在一段时间内被访问的次数。修改位：本段进入内存后是否被修改过，如修改过，则本段被置换出内存时需写回外存。(6)分页和分段的异同之处相同点：在内存中都不是整体连续，均通过地址映射机构将逻辑地址映射到物理内存。不同点：页是信息的物理单位。用户不需要把程序分页，完全是系统管理的要求。段是信息的逻辑单位。每一段在逻辑上是相对完整的一组信息。分段更好地满足了用户的需求。页的大小是固定的，且在同一系统中大小相等。段的大小因段而异，取决于用户编写的程序。分页的作业地址空间是一维的。分段的作业地址空间是二维的。2.分段存储管理的基本原理(1)段式管理的内存分配与释放段式管理中以段为单位分配内存，每段分配一个连续的内存区，同一进程所包含的各段之间不要求连续。内存分配与释放在作业或进程的执行过程中动态进行。段式管理时的内存分配要分两种情况：有无足够空闲区满足需求。段式管理中内存回收方法可以用动态分区管理时用的内存回收方法。内存的申请分2种情况进程要求调入某段时，内存中有足够的空闲区满足该段的内存要求：动态分区式管理时所用的分配算法都可用来作为段式管理时的内存分配，如：最先适应法、最佳适应法、最坏适应法。内存中没有足够的空闲区满足该段的内存要求，此时根据给定的置换算法淘汰内存中一个或几个段，可以使用页式存储管理中的置换算法，如：FIFO置换算法、LRU算法及其近似算法。除了段的初始分配之外，段的动态分配是在处理器所要访问的指令和数据不在内存时产生缺段中断的情况下发生的。段的淘汰或置换算法实际上是缺段中断处理过程的一部分。缺段中断处理过程需调入新段X内存中有不小于X段长的空闲区吗？内存中所有空闲区总和小于X段长吗？按一定算法反复淘汰旧段，以形成一个长度不小于X段长的空闲区合并空闲区以形成长度不小于X段长的空闲区为X段分配内存空闲区将X段调入内存并改写段表返回NNYY(2)段式管理的地址变换段管理程序进行地址变换的步骤:把该进程的段表始址放入段表地址寄存器；由虚地址中的段号比较段表地址寄存器中的段表长度，若0≤段号＜用户程序的总段数，则访问合法，否则访问越界。由虚地址中的段号S为索引，查找段表；若该段在内存，则判断其存取控制方式是否有错和段内位移是是否超过段长，若都正确，则从段表相应表目中查出该段在内存的起始地址，并将其和段内相对地址W相加，从而得到实际内存地址。若该段不在内存，则产生缺段中断将处理器控制权交给内存分配程序。段式存储管理的地址转换

段表始址段表长度

段号２段内位移１００段表控制寄存器Ｙ段表

＜＜段号段始址段长０１Ｋ６Ｋ８００４Ｋ６００８Ｋ３００１０Ｋ内存段内位移大于段长发生中断段超长中断Ｙ8292段式地址映射举例

例：有一系统采用段式存储管理，其段表如下，试将下述虚地址转换成内存地址。(2)[2,500]：(3)[3,400]：(4)[4,112]：

(5)[5,32]：试将下述虚地址转换成内存地址:段号段始址段长

０2105001235020210090313505904193895(1)[0,430]物理地址：210+430=640(3)段的共享与保护段的共享段是按逻辑意义来划分的，可以按段名访问，这极有利于段的共享。如果进程或作业需要共享内存中的某程序段或数据段，只要使用相同的段名，在段表中填入已在内存中的段的起始地址，并置以适当的读写控制权，就可以共享一个逻辑上完整的内存段信息。分段共享举例[MAIN1][DATA1][SIN][COS]1346作业1的地址空间[MAIN2][DATA2][SORT][COS]1563作业2的地址空间01234567作业1段表01234567作业2段表OS[MAIN1][DATA1][SIN][C[COS]OS][MAIN1][DATA2][SQRT]内存132段的保护措施：利用段表和段长来实现段的保护存权的控制。在段表的“存取方式”工项设置权限，如R、W、E等。上述保护措施可提供一个多级的存储保护体系。4.段式管理的优缺点优点：段式管理提供内外存统一管理的虚拟存储。段长可根据需要动态增加，这对那些需要增加或吸收新数据的来说，将是非常有好处的。便于具有完整逻辑功能的信息段进行共享。便于实现动态链接。缺点：处理机要为地址变换花费时间；要为表格提供附加的存储空间；为满足分段的动态增长和减少外零头，要采用拼接手段；分段的最大尺寸受到主存可用空间的限制。思考题分段技术比分页更容易实现程序或数据的共享和保护？

分段技术中，每一段在逻辑上是相对完整的一组信息，其共享是在段一级出现，这样，任何共享的信息就可单独成一段。同样，段中所有内容就可以用相同的方式进行使用，从而规定相同的保护权限。

分页技术中，页是信息的物理单位，在一页中可能存在逻辑上相互独立的两组或多组信息，各有不同的使用方式和存取权限，因而，分页难于进行共享和保护。5.5段页式存储管理

问题的提出：为了获取分段在逻辑上的优点和分页在管理存储空间方面的优点，兼用分段和分页两种方法，即段页式存储管理。1.基本概念2.段页式管理的地址变换1.基本概念(1)段页式管理的基本思想用分段方法来分配和管理虚拟存储器，而用分页方法来分配和管理主存（实存储器）一方面，可以保持分段地址空间所带来的优点，如允许分段动态扩展，可实现分段的动态链接，分段的共享，实施段保护措施等等。另一方面利用页式管理解决主存分区的拼接，辅存的管理以及对分段大小限制等问题。(2)等分内存把整个内存分成大小相等的内存块，内存块从0开始依次编号。(3)地址空间分段把用户程序分成若干段，每段有个段名。(4)段内分页页面的大小与内存块相同，每段的各个页面都分别从0开始依次编号。虚空间的最小单位是页而不是段，内存就被划分成为若干个页，且每段所拥有的程序和数据在内存中可以分开存放，分段大小也不再受内存可用区的限制。(5)逻辑地址的构成逻辑地址由三分部构成：V=（S，P，d）段号S 段内页号P页内位移d(6)内存分配以块为单位进行分配(7)段表、页表和段表寄存器为了实现从逻辑地址到物理地址的转换：为每个作业或进程建立一张段表段表中的段长页表长度段表中的段内存始址页表地址每个段拥有一张页表：段内的页号映射为内存中的物理块号。。

段表寄存器：作业段的长度和段表起始地址。段页式管理中段表、页表与内存的关系段表长度段表始址段表地址寄存器段表第0段页表第2段页表……内存段页式存储管理的地址转换

段表控制寄存器段表始址段表长度段号s页号p位移d越界中断块号位移段表页表

<越界中断p>页表长度YN段号页表长度页表始址页号块号地址变换过程在段页式管理系统系统中，要对内存中指令或数据进行1次访问的话，至少需要访问3次以上的内存：第1次，由段表地址寄存器得段表始址后访问段表；第2次，访问页表得到所要访问的物理地址；第3次，访问段表和页表之后，本次访问真正需要访问的物理单元。快表或联想寄存器在联想寄存器中，存放当前最常用的段号S、页号P和对应的内存页面与其它控制栏目。一个在联想寄存器中装有1/10左右的段号，页号及页面的段号式管理，可以通过快速联想寄存器找到90%以上的所要访问的内存地址。查询快表和段表的工作是同时开始的，当发现快表匹配时，段表的查找立即停止；如不匹配，查找段表、页表的过程继续。利用快表的段页式地址变换…………S段表…………页面S段的页表…………SPP'联想存储器SPd虚拟地址段表长度段表始址段表地址寄存器物理地址P‘P‘+d5.6局部性原理和抖动问题局部性原理实验发现，在几乎所有的程序的执行中，在一段时间内，CPU总是集中地访问程序中的饿某一个部分而不是随机地对程序所有部分具有平均访问概率。是虚拟存储管理系统的基础抖动（颠簸）

在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃，这种现象称为颠簸或抖动。抖动的原因：页面淘汰算法不合理分配给进程的物理页面数太少抖动的对策：进程执行过程中缺页率或缺段率过高，势必会造成对I/Ｏ设备的巨大压力和使得机器的主要开销大多用在反复调入调出操作上，从而无法完成用户所要求的工作。段式、页式和段页式虚存实现方法都要求在内存中存放一个不小于最低限度的程序段或数据段，而且它们必须是那些正在被访问，以及那些即将被访问的部分，这就使得内外存之间的数据交换减少到最低限度。试验表明：任何程序在局部性放入时都有一个临界值要求。当内存分配小于这个临界值时，内外存之间的交换频率将会急剧增加，而内存分配大于这个临界值时，再增加内存分配也不会显著减少交换次数。这个内存要求的临界值称为工作集。进程分配的内存小于所要求的工作集时，可能造成系统抖动（thrashing）。本章小结本章介绍各种常用的内存管理办法，它们是分区式管理、页式管理、段式管理和段页式管理。内存管理的核心问题是如何解决内存和外存的统一，以及它们之间的数据交换问题。内存和外存的统一管理使得内存的利用率得到提高，用户程序不再受内存可用区大小的限制。与此相关联，内存管理要解决内存扩充、内存的分配与释放、虚拟地址到内存物理地址的变换、内存保护与共享、内外存之间数据交换的控制等问题。

本章熟练掌握1、动态分区管理原理。

2、页式管理原理，特点，地址映射机构及越界保护，缺页中断及其处理过程。

3、段式管理原理，特点，地址映射机构及越界保护，缺段中断及其处理过程。

4、段页式管理原理，特点，地址映射机构及越界保护。

6、覆盖与交换概念。

7、页面置换算法FIFO异常现象。nYq$t*w-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9LcOfRjUmXp!s&w)z0C4F7IaMdPhSkVnZq$t*x-A1D5G8KbNeQiTlWo#r%v(y+B3E6H9LcOgRjUmYp!s&w)z1C4F7JaMdPhSkWnZq$u*x-A2D5H8KbNfQiTlXo#s%v(y0B3E6I9LdOgRjVmYp!t&w)z1C4G7JaMePhSkWnZr$u*x+A2D5H8KcNfQiUlXo#s%v)y0B3F6I9LdOgSjVmYq!t&w-z1D4G7JbMePhTkWoZr$u(x+A2E5H8KcNfRiUlXp#s%v)y0C3F6IaLdOgSjVnYq!t*w-z1D4G8JbMeQhTkWoZr%u(x+B2E5H9KcOfRiUmXp#s&v)z0C3F7IaLdPgSjVnYq$t*w-A1D4G8JbNeQhTlWoZr%u(y+B2E6H9KcOfRjUmXp!s&v)z0C4F7IaMdPgSkVnZq$t*x-A1D5G8KbNeQiTlWo#r%v(y+B3E6H9LcOfRjUmYp!s&w)z0C4F7JaMdPhSkVnZq$u*x-A2D5G8KbNfQiTlXo#r%v(y0B3E6I9LcOgRjVmYp!t&w)z1C4G7JaMePhSkWnZq$u*x+A2D5H8KbNfQiUlXo#s%v(y0B3F6I9LdOgRjVmYq!t&w-z1C4G7JbMePhTkWnZr$u(x+A2E5H8KcNfRiUlXp#s%v)y0B3F6IaLdOgSjVmYq!t*w-z1D4G7JbMeQhTkWoZr$u(x+B2E5H9KcNfRiUmXp#s&v)y0C3F7IaLdPgSjVnYq$t*w-A1D4G8JbNeQhTlWoZr%u(x+B2E6H9KcOfRiUmXp!s&v)z0C3F7IaMdPgSkVnYq$t*x-A1D5G8JbNeQiTlWo#r%u(y+B3E6H9LcOfRjUmYp!s&w)z0C4F7IaMdPhSkVnZq$t*x-A2D5G8KbNeQiTlXo#r%v(y+B3E6I9LcOgRjUmYp!t&w)z1C4F7JaMePhSkWnZq$u*x+A2D5H8KbNfQiUlXo#s%v(y0B3E6I9LdOgRjVmYp!t&w-z1C4G7JaMePhTkWnZr$u*x+A2E5H8KcNfQiUlXp#s%v)y0B3F6IaLdOgSjVmYq!t*w-z1D4G7JbMePhTkWoZr$u(x+A2E5H9KcNfRiUlXp#s&v)y0C3F6IaLdPgSjVnYq!t*w-A1D4G8JbMeQhTlWoZr%u(x+B2E6H9KcOfRiUmXp#s&v)z0C3F7IaLdPgSkVnYq$t*w-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9LcOfRjUmXp!s&w)z0C4F7IaMdPhSkVnZq$t*x-A2D5G8KbNeQiTlWo#r%v(y+B3E6H9LcOgRjUmYp!s&w)z1C4F7JaMdPhSkWnZq$u*x-A2D5H8KbNfQiTlXo#s%v(y0B3E6I9LdOgRjVmYp!t&w)zG8KbNeQiTlWo#r%v(y+B3E6H9LcOgRjUmYp!s&w)z1C4F7JaMdPhSkWnZq$u*x-A2D5H8KbNfQiTlXo#s%v(y0B3E6I9LcOgRjVmYp!t&w)z1C4G7JaMePhSkWnZr$u*x+A2D5H8KcNfQiUlXo#s%v)y0B3F6I9LdOgSjVmYq!t&w-z1D4G7JbMePhTkWnZr$u(x+A2E5H8KcNfRiUlXp#s%v)y0C3F6IaLdOgSjVnYq!t*w-z1D4G8JbMeQhTkWoZr%u(x+B2E5H9KcOfRiUmXp#s&v)y0C3F7IaLdPgSjVnYq$t*w-A1D4G8JbNeQhTlWoZr%u(y+B2E6H9KcOfRjUmXp!s&v)z0C4F7IaMdPgSkVnZq$t*x-A1D5G8KbNeQiTlWo#r%u(y+B3E6H9LcOfRjUmYp!s&w)z0C4F7JaMdPhSkVnZq$u*x-A2D5G8KbNfQiTlXo#r%v(y0B3E6I9LcOgRjVmYp!t&w)z1C4F7JaMePhSkWnZq$u*x+A2D5H8KbNfQiUlXo#s%v(y0B3F6I9LdOgRjVmYq!t&w-z1C4G7JbMePhTkWnZr$u(x+A2E5H8KcNfRiUlXp#s%v)y0B3F6IaLdOgSjVmYq!t*w-z1D4G7JbMeQhTkWoZr$u(x+B2E5H9KcNfRiUmXp#s&v)y0C3F7IaLdPgSjVnYq$t*w-A1D4G8JbMeQhTlWoZr%u(x+B2E6H9KcOfRiUmXp!s&v)z0C3F7IaMdPgSkVnYq$t*x-A1D5G8JbNeQiTlWo#r%u(y+B3E6H9LcOfRjUmXp!s&w)z0C4F7IaMdPhSkVnZq$t*x-A2D5G8KbNeQiTlXo#r%v(y+B3E6I9LcOgRjUmYp!t&w)z1C4F7JaMePhSkWnZq$u*x+A2D5H8KbNfQiTlXo#