CH4-存储器管理1

null第四章 存储器管理第四章 存储器管理存储管理是指存储器资源（主要指内存并涉及外存）的管理。 存储器资源的组织（如内存的组织方式） 地址变换（逻辑地址与物理地址的对应关系维护） 虚拟存储的调度算法null本章的目的是了解各种存储器管理的方式和它们的实现方法。 本章学习重点： 1.两种具体的存储管理方式：动态重定位的可变分区管理和虚拟分页存储管理。 2.两类主要的算法：内存分配算法和页面淘汰算法 3.三对概念的区别：实存与虚存，分页与分段，连续分配与离散分配 第四章 存储管理第四章 存储管理 4.1 存储器的层次结构 4.2　程序的装入和链接 4.3　连续分配方式 4.4　基本分页存储管理方式 4.5　基本分段存储管理方式 4.6　虚拟存储器的基本概念 4.7　请求分页存储管理方式 4.8　页面置换算法 4.9　请求分段存储管理方式 null一.存储器 存储器主存(内部存储器，磁芯存储器）辅存 （外存）磁盘、 磁带、软盘高速缓冲存储器 主存 系统区 （存放OS程序和数据） 用户区 （存放用户程序、数据）由于系统开工期间，OS程序与其他程序一起共享主存，为安全起见，多道程序系统常由OS把内存初始化为：null高速缓存器内 存外 存存储器容量 减少每位存储器 成本增加存储器存取 速度增加存储器存取 时间减少程序和数据 可以被CPU 直接存取程序和数据必 须先移到内存， 才能被CPU访问 三级存储器结构 返回null4.1.1 多级存储器结构容量愈来愈大 访问数据的速度愈来愈慢 价格愈来愈便宜null 4.2 程序的装入和链接4.2 程序的装入和链接4.2 程序的装入和链接 在多道程序环境下，要使程序运行，必须创建进程，而创建进程第一件事就是将程序和数据装入内存。 一个用户源程序 要变为在内存中可执行的程序，通常要进行以下处理：（1）编译：由编译程序 将用户源程序编译成若干 个目标模块； （2）链接：由链接程序将 目标模块和相应的库函数 链接成装入模块； （3）装入：由装入程序 将装入模块装入内存。1. 绝对装入方式1. 绝对装入方式如果在编译时，事先知用户程序在内存的驻留位置，则编译程序在编译时就产生绝对地址的目标代码。装入程序就直接把装入模块中的程序和数据装入到指定的位置，（不需进行地址转换）。 程序中所使用的绝对地址，既可在编译或汇编时给出， 也可由程序员直接赋予。 但在由程序员直接给出绝对地址时， 不仅要求程序员熟悉内存的使用情况，而且一旦程序或数据被修改后，可能要改变程序中的所有地址。因此，通常是宁可在程序中采用符号地址，然后在编译或汇编时，再将这些符号地址转换为绝对地址。 4.2.1 程序的装入null1.名空间、地址空间和存储空间在我们用汇编语言或高级语言编写程序时，总是通过符号名来访问某一单元。我们把程序中由符号名组成的空间称为名空间。 源程序经过汇编或编译形成的程序，通常是以0为基址进行顺序编址，这样的地址表示形式称为相对地址,也叫做逻辑地址或虚地址，把该程序逻辑地址组成的集合叫做程序的逻辑地址空间(简称地址空间)。 存储器中每个具体存储单元都有不同的编号，每个编号就是一个物理地址，整个程序在内存中存储后所占用的物理地址的集合形成程序的物理地址空间(简称存储空间)。2. 重定位（地址映射）装入方式null可重定位装入方式 把在装入时对目标程序中指令和数据的修改过程称为重定位，又因为地址变换通常是在装入时一次完成的，以后不再改变，故称为静态重定位。优缺点优缺点优点：不需要硬件的支持。 缺点：程序必须占用连续的内存空间；一旦程序装入后不能移动。 静态重定位null3. 动态运行时装入方式 动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此， 装入内存后的所有地址都仍是相对地址。 映射方法映射方法最简单的硬件机构是重定位寄存器。 在地址重定位机构中，有一个基地址寄存器BR和一个程序地址寄存器VR，一个内存地址寄存器MR。 动态重定位null4.2.2 程序的链接4.2.2 程序的链接 一种事先链接方式，即在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装入模块(执行文件)，以后不再拆开。 实现静态链接应解决: 1）相对地址的修改 2）变换外部调用符号 存在问题： 1）不便于对目标模块 的修改和更新。 2）无法实现对目标模 块的共享。 1. 静态链接方式null 指将一组目标模块在装入内存时，边装入边链接的方式。具有便于修改和更新、便于实现对目标模块的共享。 存在问题： 由于程序运行所有可能用的目标模块在装入时均全部链 接在一起，所以将会把一些不会运行的目标模块也链接 进去。如程序中的错误处理模块。2. 装入时动态链接方式 在程序运行中需要某些目标模块时，才对它们进行链接的方式。具有高效且节省内存空间的优点。3. 运行时动态链接方式null 单一用户(连续)分配是一种简单的存储分配 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ，主要用于单用户单任务操作系统。它的实现方案如下： (1) 内存分配：整个内存划分为系统区和用户区。系统区 是操作系统专用区，不允许用户程序直接访问，一道 用户程序独占用户区. 4.3.1 单一用户存储管理方案注意: 我们所涉及的内存分配 与回收一般都指用户区 的分配与回收。进程1OS系统区用户区4.3 连续分配方式 浪费啊！ 有木有！null (3) 内存保护：通过基址寄存器保证用户程序不会从系统区 开始；另外系统需要一个界限寄存器，里边存储程序逻 辑地址范围，若需要进行映射的逻辑地址超过了界限寄 存器中的值，则产生一个越界中断信号。(2) 地址映射：物理地址=用户区基地址+逻辑地址。 单一连续分配方案的优点是方法简单，易于实现；缺点是它仅适用于单道程序，因而不能使处理机和内存得到充分利用。例：例：一个容量为256KB的内存，操作系统占用32KB，剩下224KB全部分配给用户作业，如果一个作业仅需64KB，那么就有160KB的存储空间被浪费。0KB 32KB 96KB 256KB-1分配给用户的空间§ 4.3.2-4 分区存储管理§ 4.3.2-4 分区存储管理 分区存储管理是把主存储器中的用户区作为一个连续区或分成若干个连续区进行管理，每个连续区中可装入一个作业。 多道程序系统一般都采用多个分区的存储管理，具体可分为固定分区和可变分区两种方式。 null1、固定分区存储管理OS0abcd空 job2 把主存中可分配的用户区域预先划分成若干个连续的分区，每个连续区的大小可以相同，也可以不同。但是，一旦划分好分区之后，主存中分区的个数就固定了，且每个分区的大小也固定不变。这是一种静态分区法。 null80K操作系统作业1作业2作业3020K45K130K200K分区1分区2分区3分区4 （未分配）固定分区分区说明表在固定分区方式管理下，每个分区用来装入一个作业。由于主存中有多个分区，就可同时在每个分区中装入一个作业。所以，这种存储管理方式适用于多道程序系统。 在固定分区方式管理下，每个分区用来装入一个作业。由于主存中有多个分区，就可同时在每个分区中装入一个作业。所以，这种存储管理方式适用于多道程序系统。 等待进入主存的作业排成一个作业队列。当主存中有空闲的分区时，依次从作业队列中选择一个能装入该分区的作业。当所有的分区都已装有作业，则其他的作业暂时不能再装入，绝对不允许在同一分区中同时装入两个或两个以上的作业。已经装入主存的作业在获得处理机运行时，要限定它只能在所占的分区中执行。 null2．内存空间的分配与释放 2．内存空间的分配与释放 为了管理主存空间的使用，必须设置一张“主存分配表”，以说明各分区的分配情况。主存分配表中应指出各分区的起始地址和长度，并为每个分区设一个标志位。当标志位为“0”时，表示对应的分区是空闲分区，当标志位为非“0”时，表示对应的分区已被某作业占用。空闲分区可以用来装作业。区号 分区大小 起始地址 标志位0 32k 0k 1 1 8k 32k 1 2 16k 40k 0 3 32k 56k 1 4 64k 88k 0OS作业A(6k)作业B(28k)0 32k 40k 56k 88k当作业队列中有作业要装入主存时，存储管理可采用“顺序分配算法”进行主存空间的分配。 当作业队列中有作业要装入主存时，存储管理可采用“顺序分配算法”进行主存空间的分配。 顺序查看主存分配表，找到一个标志为“0”的并且长度大于或等于欲装入作业的地址空间长度的分区，则把此分区分配给该作业，相应表目的标志位改成作业名的标识；若找不到一个这样的空闲分区，则该作业暂时不能装入主存。 主存空间的释放很简单。某作业执行结束后必须归还所占的分区，这时存储管理根据作业名查看主存分配表，找到相应的表目后，把其中的标志位重新置成“0”即可。 null内存空间利用率低，如图。5道进程大小总和为250 KB，但是所占5个分区总容量却达到1000 KB，内存空间利用率仅达到25%。解决办法： 采用可变分区存储管理null4.3.2 固定分区分配总结 作业装入之前，内存就被划分成若干个分区。 划分工作可以由系统管理员完成或由操作系统实现。 一旦划分完成，在系统运行期间不再重新划分，即分区的个数不可变，分区的大小不可变，且每个分区装一个且只能装一个作业。 可将内存的用户区域划分成大小相等或不等的分区。 分区大小相等：只适合于多个相同程序的并发执行（处理多个类型相同的对象）。 分区大小不等：多个小分区、适量的中等分区、少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。 系统有一张分区说明表，每个表目说明一个分区的大小、起始地址和是否已分配的使用标志。null内存管理的可变分区模式，又称变长分区模式。 与固定分区的区别就是：动态的划分分区。 克服固定分区管理的“内碎片”问题。4.3.3 动态（可变）分区分配null作业装入内存时，从可用的内存中划出一块连续的区域分配给它，且分区大小正好等于该作业的大小。 可变式分区中分区的大小和分区的个数都是可变的，而且是根据作业的大小和多少动态地划分。 在分配时，首先找到一个足够大的空闲分区，即这个空闲区的大小比作业要求的要大，系统则将这个空闲分区分成两部分：一部分成为已分配的分区，剩余的部分仍作为空闲区。 在回收撤除作业所占领的分区时，要检查回收的分区是否与前后空闲的分区相领接，若是，则加以合并，使之成为一个连续的大空间。 常用的数据结构有内存分配表（由已分配区表和空闲区表组成）和空闲分区链两种。null内存初始情况和作业队列1主存空间的分配与释放nullnullnullP4例子：一计算机系统有2560KB内存，采用某种模式管理，OS占低地址的400KB空间，用户内存为2160KB。P1P2P3P2null分区分配算法：寻找某个空闲分区，其大小需大于或等于程序的要求。若是大于要求，则将该分区分割成两个分区，其中一个分区为要求的大小并标记为“占用”，而另一个分区为余下部分并标记为“空闲”。分区的先后次序通常是从内存低端到高端。2 动态分区分配算法null目前常用分配算法有： 首次适应算法 循环首次适应算法 最佳适应算法 最坏适应算法 快速适应法①首次适应算法（最先适应算法）①首次适应算法（最先适应算法）=>1.空闲分区表的表目按相应分区的地址大小以递增顺序排列。 =>2.顺序查找各个空闲区，把第一个找到能容纳申请要求的内存区分配给申请者.（若空闲区比作业长度大，则分割该空闲区。一部分分配给作业一部分空闲。若等大？） =>3.调整相应的空闲表和已分配表。null空闲分区表解：按首次适应算法， 申请作业100k，分配3号分区，剩下分区为20k，起始地址160K ； 申请作业30k，分配1号分区，剩下分区为2k，起始地址50K ； 申请作业7k，分配2号分区，剩下分区为1k，起始地址59K ； 其内存分配图及分配后空闲分区表如下：例 ：系统中的空闲分区表如下，现有三个作业分配申请内存空间100K、30K及7K。给出按首次适应算法的内存分配情况及分配后空闲分区表。null(2)该算法分配后的空闲分区表首次适应算法的特点 优先利用内存低地址部分的空闲分区,从而保留了高地址部分的大空闲区。但由于低地址部分不断被划分,致使低地址端留下许多难以利用的很小的空闲分区(碎片或零头),而每次查找又都是从低地址部分开始,这无疑增加了查找可用空闲分区的开销。②循环首次适应算法②循环首次适应算法算法要求 又称为下次适应算法，由首次适应算法演变而来。在为作业分配内存空间时,不再每次从空闲分区表/链首开始查找,而是从上次找到的空闲分区的下一个空闲分区开始查找,直到找到第一个能满足其大小要求的空闲分区为止。然后，再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲分区表/链中。null空闲分区表解：按循环首次适应算法， 申请作业100k，分配3号分区，剩下分区为20k,起始地址160K； 申请作业30k，分配4号分区，剩下分区为301k，起始地址210K ； 申请作业7k，分配1号分区，剩下分区为25k，起始地址27K ； 其内存分配图及分配后空闲分区表如下:例 ：系统中的空闲分区表如下，现有三个作业分配申请内存空间100K、30K及7K。给出按循环首次适应算法的内存分配情况及分配后空闲分区表。null(2)该算法分配后的空闲分区表算法特点 使存储空间的利用更加均衡，不致使小的空闲区集中在存储区的一端，但这会导致缺乏大的空闲分区。③最佳适应算法：③最佳适应算法： 搜索整个空闲区以找出满足要求的最小空闲区。 思想： 1.空闲分区表的表目按相应分区的大小以递增顺序排列。 2.在进行内存分配时，从空闲分区表/链的首开始顺序查找，直到找到第一个满足其大小要求的空闲分区为止。 先使用小的空闲区，将大的空闲区留给大作业，所以它总是试图找出最接近实际需要的空闲区。null例 ：系统中的空闲分区表如下，现有三个作业分配申请内存空间100K、30K及7K。给出按最佳适应算法的内存分配情况及分配后空闲分区表。分配前的空闲分区表内存分区null解：按最佳适应算法，分配前的空闲分区表如上表。 申请作业100k，分配3号分区，剩下分区为20k,起始地址160K； 申请作业30k， 分配2号分区，剩下分区为2k，起始地址50K ； 申请作业7k， 分配1号分区，剩下分区为1k，起始地址59K ； 其内存分配图及分配后空闲分区表如下：作业100K分配后的空闲分区表作业30K分配后的空闲分区表作业7K分配后的空闲分区表null(2)该算法分配后的空闲分区表算法特点 若存在与作业大小一致的空闲分区,则它必然被选中，若不存在与作业大小一致的空闲分区，则只划分比作业稍大的空闲分区，,从而保留了大的空闲分区,但空闲区一般不可能正好和它申请的内存空间大小一样,因而将其分割成两部分时,往往使剩下的空闲区非常小,从而在存储器中留下许多难以利用的小空闲区（碎片或零头）。④最坏适应算法④最坏适应算法1.空闲分区表的表目按相应分区的大小以递减顺序排列。 2.总是搜索整个链表以找到够用的最大的空闲区，使分裂出来的小空闲区比较大，因而可以继续使用。 null空闲分区表例 ：系统中的空闲分区表如下，现有三个作业分配申请内存空间100K、30K及7K。给出按最坏适应算法的内存分配情况及分配后空闲分区表。null作业100K分配后的空闲分区表作业30K分配后的空闲分区表 解：按最坏适应算法，分配前的空闲分区表如上表。 申请作业100k，分配1号分区，剩下分区为231k,起始地址280K； 申请作业30k，分配1号分区，剩下分区为201k，起始地址310K ； 申请作业7k，分配1号分区，剩下分区为194k，起始地址317K ； 其内存分配图及分配后空闲分区表如下：null(2)该算法分配后的空闲分区表3 0k 20k 52k 60k 180k 511k(1)内存分配图20K 52K 60K 280K 310K 317K 算法特点 总是挑选满足作业要求的最大的分区分配给作业。这样使分给作业后剩下的空闲分区也较大，可装下其它作业。但由于最大的空闲分区总是因首先分配而划分，当有大作业到来时，其存储空间的申请往往会得不到满足。⑤快速适应算法（分类搜索法）⑤快速适应算法（分类搜索法）算法要求 将空闲分区根据其容量大小进行分类，每一类相同容量的所有空闲分区，单独设立一个空闲分区链表，同时在内存中设立一张管理索引表，每一表项对应了一种空闲分区类型，并 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 头指针。进程根据自己的长度，寻找能容纳它的最小空闲区链表，取下第一块进行分配即可。 null最先适应法：按分区的先后次序，从头查找，找到符合要求的第一个分区 该算法的分配和释放的时间性能较好，空闲较大的分区可以被保留在内存高端。 但随着低端分区不断划分而产生较多小分区，每次分配时查找时间开销会增大。 最佳适应法：找到其大小与要求相差最小的空闲分区 从个别来看，外碎片较小，但从整体来看，会形成较多外碎片。较大的空闲分区可以被保留。 最坏适应法：找到最大的空闲分区 基本不留小空闲分区，但较大的空闲分区不被保留。几种分配算法的比较例题：分区存储管理算法题例题：分区存储管理算法题假定主存中按地址顺序依次有五个空闲区。空闲区大小依次为：32k,10k,15k,228k,100k.现有五个作业J1,J2,J3,J4,J5。他们各需要主存1k,10k,128k,28k,115k。 判断用最先适应分配算法，最坏适应分配算法，最佳分配适应算法能否将这五个作业顺序装入？null示意图：null 起始地址 长度 标志位 30K 70K ZS已分配区表空闲区表null最先适应分配算法 (空闲区按地址递增顺序排列)作业依次请求空间1k,10k,128k,28k,115k。(1)作业J1请求1K空间(2)作业J2请求10K空间(3)作业J3请求128K空间(4)作业J4请求28K空间(5)作业J5请求115K空间所有空间均不能满足作业J5请求null最坏适应分配算法 (空闲区按长度递减顺序排列)作业依次请求空间1k,10k,128k,28k,115k。(1)作业J1请求1K空间(2)作业J2请求10K空间(3)作业J3请求128K空间(4)作业J4请求28K空间(5)作业J5请求115K空间所有空间均不能满足作业J5请求null最优适应分配算法 (空闲区按长度递增顺序排列)作业依次请求空间1k,10k,128k,28k,115k。(1)作业J1请求1K空间(2)作业J2请求10K空间(3)作业J3请求128K空间(4)作业J4请求28K空间(5)作业J5请求115K空间所有空间均不能满足作业J5请求（2）回收内存（2）回收内存 当作业执行结束时，应回收已使用完毕的分区。系统根据回收分区的大小及首地址，在空闲分区表中检查是否有邻接的空闲分区，如有，则合成为一个大的空闲分区，然后修改有关的分区状态信息。 回收分区与已有空闲分区的相邻情况有以下四种： 1）回收分区上邻接一个空闲分区,合并后首地址为空闲分区的首地址,大小为二者之和。 2）回收分区下邻接一个空闲分区,合并后首地址为回收分区的首地址,大小为二者之和。 3）回收分区上下邻接空闲分区,合并后首地址为上空闲分区的首地址,大小为三者之和。 4）回收分区不邻接空闲分区，这时在空闲分区表中新建一表项，并填写分区大小等信息。null(a) M1、M2都非空(b) M1为空、M2非空(c) M1为非空、M2空(d) M1、M2都为空回收内存空间，关键是修改两个表。null在动态分区分配中，消除了固定分区管理造成的“内碎片”，但是不可避免的在内存空间造成“外碎片”。多个无法利用的小分区所形成的“碎片”是一种很大的资源浪费。 如图（a）所示，空闲分区之和为10 KB，但是无法装入一个8 KB的程序。 内存扩充内存扩充消除了固定分区管理造成的“内碎片”，但是不可避免的在内存空间造成“外碎片”。 采用移动（紧缩）技术。定时的或在内存紧张时，将内存中所有作业移到内存的一端，使其相邻。null经过紧缩后的进程在内存中的位置发生了变化，若不对程序和数据的地址进行修改，在进程就无法运行。 要使其运行，必须进行“动态重定位”4.3.6 可重定位分区分配4.3.6 可重定位分区分配 1. 动态重定位的引入 在分区存储管理方式中，必须把作业装入到一片连续的内存空间。如果系统中有若干个小的分区，其总容量大于要装入的作业，但由于它们不相邻接，也将致使作业不能装入内存。 例 ：如图所示系统中有四个小空闲分区，不相邻，但总容量为90KB，如果现有一作业要求分配40KB的内存空间，由于系统中所有空闲分区的容量均小于40KB，故此作业无法装入内存。 这种内存中无法被利用的存储空间称为“零头”或“碎片”。根据碎片出现的情况分为以下两种：系统中的碎片系统中的碎片内部碎片外部碎片内部碎片：指分配给作业的存储空间中未被利用的部分。如固定分区中存在的碎片。 外部碎片：指系统中无法利用的小的空闲分区。 如动态分区中存在的碎片。碎片问题的解决方法碎片问题的解决方法拼接或紧凑或紧缩技术 将内存中所有作业移到内存一端（作业在内存中的位置发生了变化，这就必须对其地址加以修改或变换即称为重定位），使本来分散的多个小空闲分区连成一个大的空闲区。如图所示。这种通过移动作业从把多个分散的小分区拼接成一个大分区的方法称为拼接或紧凑或紧缩。 拼接时机：分区回收时；当找不到足够大的空闲分区且总空闲分区容量可以满足作业要求时。2. 动态重定位的实现2. 动态重定位的实现 动态重定位可使程序不加任何修改就装入内存，但是它需要硬件—重定位寄存器的支持。对每一个有效地址都要加上重定位寄存器中的 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 ，以形成绝对地址。null动态重定位分区分配算法 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 图3. 动态重定位分区分配算法 在动态分区分配算法中增加拼接功能，在找不到足够大的空闲分区来满足作业要求，而系统中总空闲分区容量可以满足作业要求时，进行拼接。null可重定位分区分配方式主要特点 可以充分利用存储区中的“零头/碎片”，提高主存的利用率。 但若 “零头/碎片”过多，则拼接频率过高会使系统开销加大。null4.3.7 覆盖技术与交换技术1.覆盖技术引入：其目标是在较小的可用内存中运行较大的程序。常用于多道程序系统，与分区存储管理配合使用。 原理：一个程序的几个代码段或数据段，按照时间先后来占用公共的内存空间。 将程序的必要部分（常用功能）的代码和数据常驻内存； 可选部分（不常用功能）在其他程序模块中实现，平时存放在外存中（覆盖文件），在需要用到时才装入到内存； 不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖。(即不同时用的模块可共用一个分区) 缺点： 编程时必须划分程序模块和确定程序模块之间的覆盖关系，增加编程复杂度。 从外存装入覆盖文件，以时间延长来换取空间节省。 nullA 20KD 20KE 40KC 30KB 50KF 30K作业X的调用结构作业X的常驻区 A（20K）覆盖区0 （50K）覆盖区1 （40K） BC D E F注：另一种覆盖方法：(100K) A(20K)占一个分区：20K； B(50K)、D(20K)和E(40K)共用一个分区：50K； F(30K)和C(30K)共用一个分区：30K；Total:190KTotal:110Knull2. 交换技术引入：多个程序并发执行，可以将暂时不能执行的程序送到外存中，从而获得空闲内存空间来装入新程序，或读入保存在外存中而目前到达就绪状态的进程。交换单位为整个进程的地址空间。常用于多道程序系统或小型分时系统中，与分区存储管理配合使用。又称作"对换"或"滚进/滚出(roll-in/roll-out)"； 程序暂时不能执行的可能原因：处于阻塞状态，低优先级（确保高优先级程序执行）； 原理：暂停执行内存中的进程，将整个进程的地址空间保存到外存的交换区中（换出swap out），而将外存中由阻塞变为就绪的进程的地址空间读入到内存中，并将该进程送到就绪队列（换入swap in）。返回null优点：增加并发运行的程序数目，并且给用户提供适当的响应时间；编写程序时不影响程序结构 缺点：对换入和换出的控制增加处理机开销；程序整个地址空间都进行传送，没有考虑执行过程中地址访问的统计特性。 考虑的问题： 程序换入时的重定位； 减少交换中传送的信息量，特别是对大程序； 对外存交换区空间的管理：如动态分区方法；null 4.4 基本分页存储管理方式 分页存储管理是解决存储零头的一种方法。 动态重定位是解决存储器零头问题的一种途径，但要移动大量信息花去不少处理机时间,代价比较高,这是因为这种分配要求把作业必须安置在一连续存储区内的缘故,而分页存储管理正是要避开这种连续性要求。 分为：实分页存储管理和虚分页存储管理一、分页式存储管理 －实存模式下的页式存储管理一、分页式存储管理 －实存模式下的页式存储管理1.基本原理 假设一个大型饭店，所有的客房都是标准的双人间，部分客房已经住进客人，现在又有一个旅游团要求入住。接待员统计了一下，对旅游团领队说：“贵团全体成员都能住下，两人一个房间，但是不能住在同一楼层了，因为每层空着的客房不够，更没有几个挨着的。请原谅！”。对于这样的安排，一般人不会感到奇怪。因为旅游团本来就是由一位位个人或夫妻等组成的，而饭店的客房本来也是两人一间的，两人一组正好可住在一个客房里；另外，饭店几乎每天都有入住的和退房的客人，想在同一楼层找几间挨着的客房实在不容易。 null满满满满满1楼2楼满满满满满满满满满满基本思想基本思想①将整个系统的内存空间划分成一系列大小相等的块，每一块称为一个物理块、物理页或实页，页架或页帧（frame），可简称为块（block）。所有的块按物理地址递增顺序连续编号为0、1、2、……。 这里的块相当于饭店的客房，系统对内存分块相当于饭店把大楼所有的客房都设计成标准的双人间。 null②每个作业的地址空间也划分成一系列与内存块一样大小的块，每一块称为一个逻辑页或虚页，也有人叫页面，可简称为页（page）。所有的页按照逻辑地址递增顺序连续编号为0、1、2、……。 这里，对作业地址空间分页就相当于把旅游团成员分成两人一组。 null③一个作业，只要它的总页数不大于内存中的可用块数，系统就可以对它实施分配。系统装入作业时，以页为单位分配内存，一页分配一个块，作业所有的页所占的块可以不连续。系统同时为这个作业建立一个页号与块号的对照表，称为页表。 这好象饭店有个记录客户入住情况的客户登记表一样。另外，饭店安排客户入住是要查看全部客房的使用情况一览表，相应地系统给作业分配内存时要查看主存分配表或者内存块说明表。 null④每个块的大小是固定的，一般是个1/2KB～8KB之间的数值（请读者思考：块尺寸为什么太大或太小都不好），而且必须是个2的幂次。 对块尺寸这样规定相当于饭店规定客房是双人间。可以设想一下，如果上例中饭店所有的客房都是十人间的话，效益肯定不如全是双人间的好 null 页面(或块)的大小由系统硬件地址结构规定，通常是2的幂，例如1 KB、2 KB、4 KB等。这样的规定可以使地址映射容易实现，后面的例子可以帮助我们理解这个问题。页面不能过大，也不能过小。过小会造成页面过多，页表过长，页表又会占用较大的内存空间，而且在虚拟存储中增加了页面换入换出次数，增加了系统开销；过大又会造成页内碎片太大，内存利用率不高。早期的页面大小一般都在512 B～4 KB，随着计算机性能的提高，现在一般在2 KB～8 KB，甚至有的系统支持多种页面大小，比如Solaris就有4 KB和8 KB两种页面。null满满满满满1楼2楼满满满满满满满满满满概括：实模式下分页存储管理的基本原理：概括：实模式下分页存储管理的基本原理：系统自动地将作业的地址空间分页，将系统的主存空间分块，页与块等大小，在作业运行时，一次性把作业的全部页面装入内存，各个页所占的内存块可以不连续。 这实际是个把作业从地址空间映射到存储空间的过程 2.地址结构2.地址结构页面的划分完全是一种系统硬件的行为，一个逻辑地址放到这种地址结构，自然就分成了页号和页内单元号两部分。31 12 11 0页面大小为：4KB012345作业1地址结构及页面大小设置地址结构及页面大小设置页面的划分完全是一种系统硬件的行为。 地址结构如下：若给定某一个逻辑地址（或相对地址），通过下面式子可以得出页号和页内偏移量： 页号=逻辑地址 DIV 页面大小 页内偏移量=逻辑地址 MOD 页面大小逻辑地址=逻辑页首址+页内地址（页内偏移量） =逻辑页号*4K+页内地址（页内偏移量） null 例如页面大小为4 KB的系统中，若逻辑地址为28024由上式求得28024 div 4096=6（页号） 28024 mod 4096=3448（页内偏移量）3、页表3、页表若把他分页后装入到不相邻的物理块中，要保证系统仍能正确运行，就要实现从进程的逻辑地址变换为内存的物理地址。 所以，系统为每个进程建立一张页面映射表，简称页表。满满满满满满满满满满null0页 1页 2页 3页 4页 … N页页表用户程序内存通过页表实现页面映射0124、地址映射4、地址映射在系统中设置地址变换机构，能将用户进程地址空间中的逻辑地址变为内存空间中的物理地址。 由于页面和物理块的大小相等，页内偏移地址和块内偏移地址是相同的。无须进行从页内地址到块内地址的转换。 地址变换机构的任务，关键是将逻辑地址中的页号转换为内存中的物理块号。物理块号内的偏移地址就是页内偏移地址。 页表的作用就是从页号到物理块号的转换，所以地址变换的任务借助于页表来完成的。null通过页表实现地址映射， 设页长为P若逻辑地址为A，则有： A所对应的物理地址=块号M*页长P+页内地址D地址映射：地址映射：由于页面和物理块的大小相等，故页内偏移地址和块内偏移地址是相同的。将逻辑地址中的页号转换为内存中的物理块号可通过查表完成。举例 设页长 为4096块号20 块内地址3448即将逻辑地址中页号替换为块号。【例4-1】【例4-1】考虑一个由8个页面，每页1K字节组成的逻辑空间，把它映射到由32个物理块组成的存储器，试问逻辑地址和物理地址各有多少位？ 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 ：解此题的关键是要知道在分页管理中，“页”（Page）和“块”（Block）是一样大小的，这样才知道物理存储器是32K。 答案：逻辑地址有13位，物理地址有15位。 【例4-2】【例4-2】在例1的基础上，若其页表如右图所示，求逻辑地址0A6D(16)，06637(8)的物理地址分别为多少（用十六进制表示）？ 分页管理下的地址转换方法（即块号取代页号，页内地址直接复制） 页号 块号null分页系统地址转换过程null图4-13 分页式地址变换过程5.内存的分配与回收5.内存的分配与回收在页式存储方式中，由于内存块等长，故常用三种方式记录内存物理页面空闲情况。 ⑴ 位示图 用一个二进制位（bit）表示内存中一个物理页面的状态。规定其值为0时，表示该物理块空闲；其值为1时，表示该块被占用。所有位组成字位映像图，见图。并设置一个计数器以记录系统当前的空闲块数。15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0n块号=字号*字长+位号null⑵ 空闲页面表 系统将连续的若干空闲页面作为一组登记在空闲页面表中，如图。当作业申请x个内存页时，可查找空闲页面表，从第一表项开始查找，同时累计空闲块数满x时分配给作业，这样可以让作业在内存中尽量占据连续的空间。回收时，系统将归还的空闲块按空闲块的编号插入到空闲页面表中，若有相邻的空闲块还要合并，类似于可变分区方式下的空闲区管理。null⑶ 空闲页面链表 将所有空闲页面组成一个链表，每一个空闲页面设有指向下一个页面的指针，系统保留空闲链表的头指针。作业请求分配时，系统就从空闲链表头开始依次摘取若干页面给用户进程，回收时，将归还的空闲块插入到表头即可。null图4-13 分页式地址变换过程null二、 快表 因为页表是存放在内存中的CPU要存取一个数据，需访问主存两次。 第一次：访内存中的页表，找到该页的的物理块号，将此块号与页内地址拼结形成物理地址； 第二次：真正访问该物理地址，存取其中的内容。 这样就把程序的执行速度降低一倍。 为了提高存取速度，在地址变换机构中增设一组寄存器，用来存放访问的那些页表。 把存放在高速缓冲寄存器中的页表叫快表，这个高速缓冲寄存器又叫联想存贮器。null联想存贮器的存取速度比主存高，但造价也高。因此只能采用少量，整个系统通常只要用8~16个寄存器即可使程序执行速度大大提高。快表的格式见下图。 null其中，“页号”是程序访问过的地址空间的页号，“块号”是该页所对应的主存块号；访问位指示该页最近是否被访问过。“0”表示没有被访问，“1”表示访问过 ；“状态”位指示该寄存器是否被占用。通常“0”表示空闲，“1”表示占用。 为了保证快表中的内容为现正运行程序的页表内容，在每个程序被选中时，由恢复现场程序把快表的所有状态位清“0”，或恢复已保存的快表内容。null2. 具有快表的地址变换机构 图 4-13 具有快表的地址变换机构 4.4.3 多级页表问题 若逻辑地址空间很大，则划分的页就很多，页表就很大，其占用的存储空间（要求连续）就大，实现较难。 解决问题的方法 1、只将当前需用的部分页表项调入内存，其余的需用时再调入。 2、多级页表 二级页表 (1)将页表再进行分页，并离散地将各个页表页面存放在不同的物理块中，同时也再建立一张页表（外层页表）用以记录页表页面对应的物理块号。 4.4.3 多级页表null两级页表null(2)逻辑地址： (3)地址转换null多级页表 将外层页表再进行分页，也将各外层页表页面离散地存放在不同的物理块中，再利用第2级的外层页表来记录它们之间的对应的关系。 逻辑地址：null优点： 没有外碎片，每个内碎片不超过页大小。 一个程序不必连续存放。 便于改变程序占用空间的大小。即随着程序运行而动态生成的数据增多，地址空间可相应增长。 缺点：程序全部装入内存。分页存储管理null1．把作业地址空间中使用的逻辑地址变成内存中物理地址 称为（ ）。 A. 加载 B. 重定位 C. 物理化 D. 逻辑化3．在内存分配的“最佳适应法”中，空闲块是按（ ）。 A.始地址从小到大排序 B.始地址从大到小排序 C.块的大小从小到大排序 D.块的大小从大到小排序 4．分区管理和分页管理的主要区别是（ ）。 A.分区管理中的块比分页管理中的页要小 B.分页管理有地址映射而分区管理没有 C.分页管理有存储保护而分区管理没有 D.分区管理要求一道程序存放在连续的空间内而分页管理 没有这种要求。 2．在可变分区存储管理中的紧凑技术可以( )。 A. 集中空闲区 B. 增加主存容量 C. 缩短访问时间 D. 加速地址转换BACDnull5．设内存的分配情况如下图所示。若要申请一块40K 字节的内存空间，若采用最佳适应算法，则所得到 的分区首址为（ ）。 A. 100K B. 190K C. 330K D. 410K 000K 100K 180K 190K 280K 330K 390K 410K 512K-1 Cnullnull一个用户作业的程序按其逻辑结构可划分为若干段，例如主程序段、子程序段、数据段、堆栈段等。这些段中的每一段在逻辑上都是完整的，因此每一段都是一组逻辑信息，有自己的名字，且都有一段连续的地址空间。 在分段式存储管理中，段名用段号代替，段地址从0开始编址，因为各段的逻辑信息内容不同，所以段长度不同。这样用段号和段内地址构成用户程序的逻辑地址。 当一个用户程序装入内存时，系统为每个段分配一个连续的内存区域，而各个段之间可以离散存放。 4.5.2 分段系统的基本原理4.5 基本分段存储管理方式null地址映射机构段 表null分段式地址变换过程例：给定逻辑地址中段号为3，段内地址为723null分页和分段的主要区别分页是出于系统管理的需要，分段是出于用户应用的需要。页是信息的物理单位，段则是信息的逻辑单位。 一条指令或一个操作数可能会跨越两个页的分界处，而不会跨越两个段的分界处。 页大小是系统固定的，而段大小则通常不固定。 逻辑地址表示： 分页是一维的，各个模块在链接时必须组织成同一个地址空间； 分段是二维的，各个模块在链接时可以每个段组织成一个地址空间。 通常段比页大，因而段表比页表短，可以缩短查找时间，提高访问速度。返回null4.5.3 信息共享 分页系统中共享editor的示意图例:一个多用户系统可同时容纳40个用户，都执行一个文本编辑程序（160KB代码和40KB数据区），代码是可重入的假定页面大小为4KB。null分段系统中共享editor的示意图 null 方便了用户编程。多个逻辑段形成作业这种组织方式，使用户可以清晰地设计和了解程序的结构。 便于实现程序和数据的共享与保护。 程序的动态链接实现方便。通常一个源程序经过编译后所形成的若干个目标程序，还需再经过链接，形成可执行代码后才能运行，这种在装入时进行的链接称为静态链接。动态链接是指在作业运行之前，并不把几个目标程序段都链接起来，而是先将主程序对应的目标程序装入内存并启动运行，当运行过程中又需要调用某段时，再将该段（目标程序）调入内存并链接起来。所以，动态链接是以段为基础的。 应用中会发生数据动态增长的情况，而且这种增长是无法预知的，采用分段管理可以很好地解决这个问题。分段存储管理的优缺点优点：缺点：有外碎片问题。null4.5.4 段页式存储管理方式 在段页式存储管理系统中，处理机给出的有效地址被划分为三部分：段号、段内页号和页内地址。 段页式存储管理中，记录逻辑地址到物理地址的映射表包括段表和页表。它们的结构和映射功能如图所示。 null例:给定某个逻辑地址中，段号为2，段内地址为6015，若系统规定块大小为1 KB，则采用段页式管理，该逻辑地址表示：段号为2，段内页号为5，页内地址为895。其地址变换过程如图所示。null ① 段号2与段表寄存器中存放的段表长度比较以判断是否越界，如果越界，则转错误中断处理，否则转②； ② 段表始地址+段号×段表项长度，就得到属于该段的页表始地址和页表长度； ③ 页号与页表长度进行越界检查，页表始地址+页号×页表项长度，就得到内存页表中记录的该页对应的物理块号16； ④ 16(块号)×1024(块大小)+895(页内地址)=17279(一个物理地址号)； ⑤ 访问内存17 279单元，得到需要的数据365。null 采用段页式存储管理，从逻辑地址到物理地址的变换过程中要三次访问内存，一次是访问段表，一次是访问页表，再一次是访问内存物理地址。这就是说，当访问内存中的一条指令或数据时，至少要访问内存三次，这将使程序的执行速度大大降低。为此，可以像在分页存储管理中那样，使用联想存储器的方法来加快查表速度。4.6 虚拟存储器的基本概念4.6 虚拟存储器的基本概念常规存储管理方式的共同点： 要求一个作业全部装入内存后方能运行。 问题： (1)有的作业很大,所需内存空间大于内存总容量,使作业无法运行。 (2)有大量作业要求运行，但内存容量不足以容纳下所有作业，只能让一部分先运行，其它在外存等待。 解决方法 （1）增加内存容量。 （2）从逻辑上扩充内存容量 ----覆盖 ----对换 ----虚拟存储器4.6.1 虚拟存储器的引入4.6.1 虚拟存储器的引入常规存储器管理方式的特征 （1）一次性：作业在运行前需一次性地全部装入内存。将导致上述两问题。 （2）驻留性：作业装入内存后，便一直驻留内存，直至作业运行结束。 局部性原理 指程序在执行时呈现出局部性规律，即在一较短时间内，程序的执行仅限于某个部分，相应地，它所访问的存储空间也局限于某个区域。 局部性又表现为时间局部性(由于大量的循环操作，某指令或数据被访问后，则不久可能会被再次访问)和空间局部性（如顺序执行，指程序在一段时间内访问的地址，可能集中在一定的范围之内）。虚拟存储器的概念虚拟存储器的概念基于局部性原理，程序在运行之前，没有必要全部装入内存，仅须将当前要运行的页（段）装入内存即可。 运行时，如访问的页（段）在内存中，则继续执行，如访问的页未在内存中（缺页或缺段），则利用OS的请求调页（段）功能，将该页（段）调入内存。 如内存已满，则利用OS的页（段）置换功能，按某种置换算法将内存中的某页（段）调至外存，从而调入需访问的页。 虚拟存储器是指仅把作业的一部分装入内存便可运行作业的存储管理系统，它具有请求页调入功能和页置换功能，能从逻辑上对内存容量进行扩充，其逻辑容量由外存容量和内存容量之和决定，其运行速度接近于内存，成本接近于外存。 4.6.2 虚拟存储器的实现方法4.6.2 虚拟存储器的实现方法1、分页请求系统 在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页式虚拟存储器系统。 它允许只装入若干页的用户程序和数据，便可启动运行，以后在硬件支持下通过调页功能和置换页功能，陆续将要运行的页面调入内存，同时把暂不运行的页面换到外存上，置换时以页面为单位。 系统须设置相应的硬件支持和软件： （1）硬件支持：请求分页的页表机制、缺页中断机构和地址变换机构。 （2）软件：请求调页功能和页置换功能的软件。null 2、分段请求系统 在分段系统的基础上，增加了请求调段功能及分段置换功能，所形成的段式虚拟存储器系统。 它允许只装入若干段的用户程序和数据，便可启动运行，以后在硬件支持下通过请求调段功能和分段置换功能，陆续将要运行的段调入内存，同时把暂不运行的段换到外存上，置换时以段为单位。 系统须设置相应的硬件支持和软件： （1）硬件支持：请求分段的段表机制、缺段中断机构和地址变换机构 （2）软件：请求调段功能和段置换功能的软件4.6.3 虚拟存储器的特征4.6.3 虚拟存储器的特征1、多次性 多次是虚拟存储器最重要的特征。指一个作业被分成多次调入内存运行。 2、对换性 对换性指允许在作业运行过程中进行换进、换出。换进、换出可提高内存利用率。 3、虚拟性 虚拟性是指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。虚拟性是虚拟存储器所表现出来的最重要的特征，也是实现虚拟存储器最重要的目标。 注：虚拟性以多次性和对换性为基础，而多次性和对换性又是离散分配为基础。null4.7 请求分页存储管理方式 在简单页式存储管理的基础上，增加请求调页和页面置换功能。1. 对页表的修改状态位（中断位）：表示该页是在内存还是在外存 访问位：根据访问位来决定淘汰哪页（由不同的算法决定） 修改位：表示该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一份副本，因此，若未被修改，在置换该页时就不需将该页写回到外存上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新副本null 在请求分页系统中，每当所要访问的页面不在内存时，便要产生一缺页中断，请求OS将所缺页调入内存。 2．缺页中断机构与一般中断的主要区别在于： 缺页中断在指令执行期间产生和处理中断信号，而一般中断在一条指令执行完后检查和处理中断信号。 缺页中断返回到该指令的开始重新执行该指令，而一般中断返回到该指令的下一条指令执行。 一条指令在执行期间，可能产生多次缺页中断。3.地址变换机构3.地址变换机构4.7.2 内存分配策略和分配算法4.7.2 内存分配策略和分配算法 在请求分页系统中，为进程分配内存时，将涉及以下三个问题： 1、最小物理块数的确定 最小物理块数指能保证进程正常运行所需的最小的物理块数，与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。 2、物理块的分配策略 （1）固定分配局部置换：为每个进程分配固定数目n的物理块，在整个运行中都不改变。如出现缺页，则从中置换一页。 （2）可变分配全局置换：分配固定数目的物理块，但OS自留一空闲块队列，若发现缺页，则从空闲块队列中分配一空闲块与该进程，并调入缺页于其中。当空闲块队列用完时，OS才从内存中任