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

第四章 存储器管理,4.1 概述,存储体系,存储层次结构,依据访问速度的匹配关系、容量要求和价格，在存储技术和CPU寻址技术许可的范围内组织合理的存储结构。,存储管理的任务 存储分配和回收 地址变换(地址重定位) 存储共享和保护 存储器扩充,相关概念 逻辑地址： 物理地址： 地址空间： 存储空间： 地址重定位：,目标代码的相对编址,目标代码的绝对编址,目标代码用逻辑地址编址所限定的区域,内存若干存储单元用物理地址编址所限定的区域,当程序被装入内存时，程序的逻辑地址被转换成内存的物理地址的过程, 重定位的方式 静态重定位：目标代码装入内存时，一次性进行 地址转换。 动态重定位：目标代码装入内存时，先不进行地 址转换（即原代码装入），在执行 时，再实施地址转换。, 地址重定位过程 例：,0,0,4.2 程序的装入和链接,1）源程序转换成可执行程序过程 编译 链接 装入,2）程序的链接与装入 程序的链接（模块拼接） 静态链接：装入前先链接 动态链接：装入时（或执行时）才进行链接 程序的装入 绝对装入：目标代码与装入位置地址相一致 静态重定位装入：装入时实现地址转换 动态重定位装入：待执行时再进行地址转换 分配方式：连续分配或者离散分配,4.3 连续分配方式 单一连续区分配 固定分区分配 可变（动态）分区分配 可重定位分区分配 伙伴系统,1）单一连续分配 只能用于单用户、单任务的操作系统中。 系统区：仅提供给操作系统使用，OS通常驻留在 内存的低址部分； 用户区：指除系统区以外的全部内存空间提供给某 一用户使用。,2）固定分区分配 算法思想 内存可用区划分成若干个大小固定的分区，这些分区大小可以相同也可不同，每个分区分别装入一道作业的代码（数据）。 算法实现 建立一个分区说明表来登记和管理整个内存。在这个表中登记了每一个分区的大小，起始地址和分配状态。,分区说明表,已分配,260K,200KB,4,已分配,120K,40KB,2,未分配,160K,100KB,3,已分配,100K,20KB,1,分配状态,起始地址,大小,分区号,例：,分配：查分区说明表，找到一个 足够大的空闲分区分配之,回收：将回收分区对应的分区说明 表状态改为“空闲”。,特点,与单一连续分配相比，内存利用率提高，内存可同时装入多道作业代码，算法实现简单； 分区一次性全部分配出去存在浪费，产生内碎片（分区内不能被利用的小空间）。,3）可变分区分配 算法思想 按需分配：每次从空闲分区中按作业大小分配一块给该作业，然后将剩下的部分再作为空表块留在空闲分区中。(分区的大小和个数不固定) 算法实现 建立相关空闲分区表，用来记录每个空闲分区的大小、起始地址。空闲分区的管理常采用链表形式。,分区分配算法： 寻找某个空闲分区，其大小需大于或等于程序的要求。若是大于要求，则将该分区分割成两个分区，其中一个分区分配给用户，而另一个分区仍留在空闲分区链表中。 首次适应算法 循环首次适应算法 最佳适应算法 最差适应算法 快速适应算法,首次适应算法,算法思想：将所有的空闲分区按照地址递增的顺序排列,分配过程：每次分配时，从空闲分区链的链首开始查找， 找到符合要求的第一个分区，一分为二分配,特点：较大的空闲分区可以被保留在内存高地址空间； 但随着低端分区不断划分而产生较多小分区，每次 分配时从头开始查找，时间开销大。,循环首次适应算法,算法思想：将所有的空闲分区按照地址递增的顺序排列，从上次分配的分区的下一个空闲分区起查找，找到符合要求的第一个分区,分配过程：设置一个起始查找指针，指向上次分配的分区的下一个空闲分区，分配时总是从起始查找指针所指向的表项开始查找，找到第一个满足要求的空闲区时，一分为二分配,特点：该算法的分配和释放的时间性能较好； 但较大的空闲分区不易保留。,最佳适应算法,算法思想：将空闲分区按容量递增顺序排序，,分配过程：每次分配时，从空闲分区链的链首开始查找， 找到符合要求的第一个分区，一分为二分配,特点：较大的空闲分区可以被保留； 但容易形成很多外碎片（分区之间不能被利用的空间）,最坏适应算法,算法思想：将空闲分区按容量递减顺序排序,分配过程：只需查找空闲区链最前面的空闲块即可,特点：分配的时候，只需查找一次，分配的算法很快； 但较大的空闲分区不被保留。,分区回收算法 如果释放区与临近的空闲区相连接，要将它们合并成较大的空闲区，否则空闲区将被分割得越来越小，最终导致不能利用。 上邻接合并 下邻接合并 上、下邻接合并 不邻接处理,例：某系统内存使用情况如下图，若采用首次适应算法分配内存，分别给出为某作业分配50k空间和回收作业4后的空闲分区链,分配50k后,回收作业4后,初始时,4）可重定位分区分配 算法思想 在可变分区分配算法的基础上，采用动态重定位方式装入程序（数据）。当无足够大的分区供分配时，若总空闲存储容量够用，则将各分区中的内容向内存一端移动（紧凑），使另一端形成一个大的空闲分区，然后再分配。 算法流程（如下页图示）,与动态分区分配算法基本相同，差别仅在于增加了紧凑功能。,请求分配 u.size分区,检索空闲分区链(表),找到大于u.size 的可用区？,按动态分区方式 进行分配,修改有关的 数据结构,返回分区号 及首址,空闲分区总和 u.size?,进行紧凑形成连续 空闲区,修改有关数据结构,无法分配 返回,否,是,是,否,(图4-10 动态重定位分区分配算法流程图),例：前例若要为作业10分配120k的存储空间，因无足够大分区（总空闲容量290k），则先进行合并处理。,合并后空闲分区链为：,此时，就可以为作业10分配空间,算法实现 为每个作业（分区）分配一个重定位寄存器，用以存放对 应分区首地址，以便实现动态地址转换；移动后，只需修 改重定位寄存器的值为新地址即可 优、缺点,可实现动态（可变）分区分配，又适时解决碎片问题 但移动内存需增加系统开销，增加辅助空间,5）伙伴系统,算法思想：将所有的空闲分区按照容量大小进行分类，而且分区大小均为2的K次幂，对每一类具有相同大小的所有空闲分区均设立一个空闲分区双向链表。,分配过程：根据进程长度n找到能容纳它的最小空闲区链表，取下第一个分区进行分配。如果该分区容量比所需的要大，就将其进行平均分割，其中一个分区用于分配，另一个分区加入对应大小的空闲分区链中。如果分割后的分区仍比所需分区大的话，按前叙方法继续分割，直到满足要求为止。,特点：其分配和回收的时间性能取决于查找空闲分区的位置和 分割、合并空闲分区所花费的时间。,4.4 基本分页存储管理方式 1）算法思想和算法实现 算法思想 作业地址空间被分成大小相同的若干页（页面） 内存存储空间被分成大小与页相同的若干块（物理块） 将连续的页分配并存放到不连续的若干内存块中 建立页表，记录每一页对应的存储块的块号,算法实现 确定分页的页面大小 建立辅助数据结构 作业代码装入方式,页表：每个作业（进程）一张表 空闲块链表：记录所有未分配空闲块情况（供分配用） 存储分块表：记录内存每一块的使用情况,太大：存在页内碎片 太小：页表占用空间太多,采用动态重定位在执行时实现地址转换,2）地址变换过程和地址变换机构,地址的机构由两部分组成:P(页号)和D(页内偏移量)。,分页系统利用页表进行地址变换，由CPU中的内存管理单元 (MMU,Memory Management Unit)完成地址变换过程如下图所示:,分页存储管理逻辑地址转换成物理地址方法： 逻辑地址/页大小 取整页号 块号 逻辑地址/页大小 取余页内位移量 块号*页大小+页内位移量物理地址,查页表,地址变换实例： 设一个3页长的进程具有页号0，1，2，其对应的物理块号则为2，3，8，如果每个页面的长度为1KB，则逻辑地址2500所对应的物理地址为多少？,解答： 2500/1024=2页号 2页对应物理块号8 2500%1024=452页内偏移 物理地址为：81024+452=8644,为了缩短页表查找时间，可将当前访问的页表项装入到地址变换机构中的特殊高速缓冲寄存器，称为联想存储器或称快表,3）改进的地址变换机构,4）内存的分配与回收 计算作业（进程）所需的页面数查是否有足够空闲块数的内存供分配 查空闲块链表，分配内存块分配页表空间，建立页表修改空闲链表及空闲总块数等数据 根据页表，回收（释放）各内存块回收页表修改相关数据项,若 够,分配过程,回收过程,5）分页分配不足之处 碎片问题，虽然大部分的问题都解决了，但是每一个作业或者进程的最后一页基本都不能充分利用 分割分配并存放，使逻辑完整的模块物理上不完整，不利于内存信息（数据）共享,4.5 基本分段存储管理方式,1）算法思想 是根据程序的模块结构，把作业划分为大小不同段。每段有一个段名（通常用段号代替），段号(S)从0开始，每一段内也从0连续编址(偏移W) 采用可变分区分配算法为每一段分配分区空间，段与段之间不一定连续但段内地址是连续的 建立段表，记录每一段的段长及段在内存的起始地址,将程序的地址空间划分为若干个段，物理内存的管理 采用动态分区，这些段不必连续,0,1,2,2）地址结构和地址变换过程 地址结构 地址变换机构,二维地址,例：以下是基本分段存储管理中的地址变换机构， 1）说明分段存储管理方式的地址变换过程； 2）若逻辑地址中的段号S=0，段内相对地址为500，给出地址变换后对应的物理地址值。,解答： 1）地址变换过程：取逻辑 地址中的段号查段表，从 而得到对应段在内存的起始地址，再用此起始地址与逻辑地址中的段内相对地址相加，从而获得对应的物理地址； 2）指定的逻辑地址经地址 变换结构变换后的物理地 址是：4596,3）段式管理的数据结构,4）改进的地址变换机构 增设一个关联寄存器，用于保存最近常用的段表项。一般情 况下段比页大，因而段表项的数目比页表数目少，其所需的 关联寄存器也相对较小，可以显著地减少存取数据的时间。,进程段表：描述组成进程地址空间的各段，可以是指向系统段表中表项的索引。每段有段基址(base address) 系统段表：系统内所有占用段 空闲段表：内存中所有空闲段，可以结合到系统段表中。内存分配算法可以采用最先适应算法、最佳适应算法和最坏适应算法。,5）分段分配特点,分段共享：可以按段为单位来进行共享 分段保护：可以针对不同类型的段采取不同的保护 动态链接：通过动态链接进行代码共享 动态增长 没有内碎片，外碎片要通过内存紧缩来消除,采用离散分配，采用动态重定位实现地址转换 不同之处 分页 分段 地址空间划分 物理（大小固定） 逻辑（大小可变） 分配空间 不连续的块 不连续的分区 地址结构 一维 二维 地址变换 块号与页内位 段始地址与段内 移量拼接 相对地址相加 共享性 不利于共享 利于共享,6）分页与分段存储管理的比较,可重入代码：不允许任何进程对其修改的共享代码 分页共享 每个共享进程的页表项中记录共享代码的所有物理块号 分段共享 每个进程的段表中记录共享段的物理地址,7）信息的共享,4.6 段页式存储管理方式,引入： 分页存储管理能有效地提高内存的利用率，而分段存储管理则能很好地满足用户需要。将两种存储管理方式“各取所长”后，则可以将两者结合成一种新的存储管理方式 “段页式存储管理” 。 段页式存储管理既具有分段系统便于实现、分段可共享、易于保护、可动态链接等优点；又能像分页系统那样很好地解决内存的外碎片问题，以及为各个分段可不连续地分配内存等问题。,算法思想 作业地址空间先分段，每段再分页 内存存储空间按页的大小分块 为每段的若干页分配存储块空间，并分块存放 建立段表、页表记录作业段、页与内存块的对应信息 地址结构 地址结构由段号、段内页号和页内地址三部分组成,段页式存储管理的数据结构 段表：记录了每一段的页表起始地址和页表长度 页表：记录了每一个段所对应的逻辑页号与内存块号的对应关系，每一段有一个页表，而一个程序可能有多个页表 空闲内存页表：由于物理内存采用分页式的存储管理，所以它的结构同分页式存储管理 物理内存分配：同分页式存储管理,段表及其页表：,地址变换过程 在段页式存储管理中，为了实现从逻辑地址到物理地址的变换，系统中需要同时配置段表和页表。由于允许将一个段中的页进行不连续分配，因而使段表的内容有所变化：它不再是段内起始地址和段长，而是页表起始地址和页表长度。其变换过程如下图所示：,改进的地址变换 段页式存储管理中，为获得一条指令或数据需三次访问内存： 第一次访问内存中的段表，获得页表地址； 第二次访问内存中的页表，获得该页所在的物理块号，并将该块号与页内地址一起形成指令或数据的物理地址； 第三次访问才是真正根据所得的物理地址取出指令或者数据。 显然，速度下降很多，于是在地址变换机构中引入一个联想存储器（快表或高速缓冲寄存器），每次访问内存时，都是同时利用段号和页号进行检索。,存储分配与管理方式小结 连续分配：单一连续区分配 固定分区分配 可变分区分配 可重定位分区分配 离散分配：基本分页分配 基本分段分配 段页式分配 共同点：作业必须一次性全部装入内存,问题：容量超过内存总容量的作业无法运行， 多道作业总容量超过内存容量也无法运行。 解决：物理扩充存储器（容量） 逻辑扩充内存,虚拟存储器,4.7 虚拟存储器的基本概念与实现 1）虚拟存储器的引入 作业调度时，仅装入其代码的一部分到内存，待运行需要时再装入其余部分，同时还可将不再运行的部分调出内存 变相地扩充了内存容量,即实现了虚拟存储器,2）局部性问题 指程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域， 即不会涉及整个地址空间。局部性表现在以下两个方面： 时间局部性：即一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内。 空间局部性：即当前指令和邻近的几条指令，当前访问的数据和邻近的数据都集中在一个较小区域内。 即在一段时间间隔内，仅装入一部分代码,作业照样能正常运行,虚拟存储的基本原理 在程序装入时，只需将当前需要执行的部分页或段读入到内存，就可让程序开始执行(部分装入)。 在程序执行过程中，如果需执行的指令或访问的数据尚未在内存（称为缺页或缺段），则由处理器通知操作系统将相应的页或段调入到内存，然后继续执行程序（请求调入）。 另一方面，操作系统将内存中暂时不使用的页或段调出保存在外存上，从而腾出空间存放将要装入的程序以及将要调入的页或段（置换）,3）虚存的原理与定义,虚拟存储器的定义 是指具有请求调入功能和置换功能，能从逻辑上对内存加以扩充的一种存储器系统。 逻辑容量由机器位数决定，容量为物理内存和外存交换区容量之和，比实际容量大得多。 其运行速度接近内存速度 而每位的成本又接近外存。 引入虚拟存储技术的好处 可在较小的可用内存中执行较大的用户程序； 可在内存中容纳更多程序并发执行； 提供给用户可用的虚拟内存空间通常大于物理内存,覆盖 是一种解决小内存运行大作业的方法。一个作业通常由程序员事先组织好覆盖结构，若干程序段和数据段可以共享内存区域，不同时调入内存而是根据需要分别调入。覆盖发生在一个作业内。 交换 在内存空间紧张时，把内存中暂时不能运行的进程或者暂时不用的程序和数据调到外存上，再把已具备运行条件的进程或进程所需的程序和数据调入内存。根据对换的单位不同称为“进程对换”和“部分对换”。,4）虚存的实现,关键技术：覆盖与交换技术,实现方式： 请求分页存储管理-在基本分页系统的基础上增加请求调页和页面置换功能 请求分段存储管理-在基本分段系统的基础上增加请求调段和段置换功能。 5）虚存的特点 多次性 对换性 虚拟性,4.8 请求分页存储管理 1）算法思想与实现 算法思想 作业分页，内存分块，页与块的大小相等 先装入部分页到内存 待运行需要时再调入新的页，淘汰旧的页（交换） 算法实现 软、硬件支持：足够大的外存及内存，地址变换机构等相关管理软件 扩充页表功能（增加页表表项） 增加缺页中断及其处理功能,2)页表表项：增加换入换出所需的必要信息状态位： 存在位（present bit，内存页和外存页） 修改位(modified bit) 访问统计：在近期内被访问的次数，或最近一次访问到现在的时间间隔 外存地址(disk address),3）缺页中断及其处理过程,缺页中断 由CPU的地址变换机构产生缺页中断，然后调用操作系统 提供的中断处理程序。 缺页中断在指令执行期间产生和进行处理，而不是在一条指令执行完毕之后。所缺的页面调入之后，重新执行被中断的指令。 一条指令的执行可能产生多次缺页中断。,缺页中断的特殊性：,缺页中断请求,保留CPU现场,在外存中找该页,内存满,淘汰的页修改过,修改页写回外存,OS负责从外存读缺的页 启动I/O硬件 将页从外存调入,修改页表,指令重执行,恢复CPU现 场,选择一页换出,缺页中断处理过程,4）内存块的分配 固定分配：分配固定数目的内存块给作业，以后不再改变 可变分配：分配给作业的块数不固定，可动态改变 平均分配 按比例分配 根据优先权分配,最小物理块的确定,分配策略,分配方法,5）内存块的调页及置换策略 页的调进策略 决定什么时候将一个页从外存调入物理内存 请求调入 提前（预）调入 页的淘汰与调出 又称之为置换，在内存已满时决定将哪个虚页从内存中移出。该部分重点讨论的问题包括： 置换方式 置换的位置 置换的算法,页的置换方式： 固定分配，局部置换 可变分配，全局置换 可变分配，局部置换 置换页在外存的位置： 外存文件区 外存对换区,页面置换（淘汰）算法 基本原则： 常用算法 最佳算法 先进先出算法 最近最久未使用（LRU）算法 Clock算法及其改进算法,降低页面更换率，应把未来不再使用的或短 期内较少使用的页面调出，通常只能在局部 性原理指导下依据过去的统计数据进行预测； 相反会有“抖动”,最佳算法（Optimal） 思想：选择“未来不再使用的”或“在离当前最远位置上出现的”页面被置换。 特点：这是一种理想情况，是实际执行中无法预知的，因而不能实现，通常作为性能评价的依据。 例：假设某作业访问页面引用序列为： 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 采用固定分配，局部置换淘汰方式（分配三个内存块）,例1. 设M=3，页面走向如下图所示，采用FIFO。计算其缺页中断次数和缺页率。,由表可以算出缺页中断次数F=9，而缺页率：912=75%。,先进先出算法（FIFO） 思想：选择进入内存最早的页面被置换。,例2. 设M=4，采用FIFO，其余同例1。计算其缺页中断次数和缺页率。,由表可以算出缺页中断次数F=10，而缺页率：1012=83%。,特点：开销很低但性能较差。较早调入的页往往是经常被访问的页，这些页在FIFO算法下被反复调入和调出，产生Belady现象。 Belady现象：采用FIFO算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多，缺页率反而提高的异常现象。 Belady现象的原因：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。,最近最久未使用算法(LRU, Least Recently Used) 选择内存中最近最久未使用的页面被置换。这是局部性原理的合理近似，性能接近最佳算法。需要硬件机构来记录页面使用时间的先后关系，硬件机构可以为： 一个特殊的栈：把被访问的页面移到栈顶，于是栈底的是最久未使用页面。 每个页面设立移位寄存器（作为计数器）：被访问时左边最高位置1，定期右移并且最高位补0，于是寄存器数值最小的是最久未使用页面。,算出缺页中断次数F=10，缺页率f =1012=83。,例3. 设M=3，页面走向如下图所示，采用LRU。计算其缺页中断次数和缺页率。,由表可以算出缺页中断次数F=8，而缺页率：812=67%。,例4. 设M=4，页面走向如下图所示，采用LRU。计算其缺页中断次数和缺页率。,特点：性能接近最佳算法； 由于需要记录页面访问先后顺序，硬件开销太大。,也称最近未使用算法(NRU, Not Recently Used)或二次机会算法。 内存中所有页面链接成一个循环队列，每页有一个使用标志位，若该页被访问则置1，由硬件自动完成。 置换时，采用一个指针，从当前指针位置开始按照地址先后检查各页，寻找标志位为0的页面作为置换页。 指针经过标志位为1的页面，将其改为0。 最后指针停留在被置换页的下一页处。,Clock置换算法,改进型Clock置换算法,增加一个修改位M 由访问位A和修改位M可以组合成下面四种类型的页面： 1类(A=0, M=0): 表示该页最近既未被访问， 又未被修改， 是最佳淘汰页。 2类(A=0, M=1)：表示该页最近未被访问， 但已被修改， 并不是很好的淘汰页。 3类(A=1, M=0)：最近已被访问， 但未被修改， 该页有可 能再被访问。 4类(A=1, M=1): 最近已被访问且被修改， 该页可能再被访 问。,其执行过程可分成以下三步： (1) 从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。 (2) 如果第一步失败，即查找一轮后未遇到第一类页面， 则开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0。 (3) 如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。然后重复第一步，如果