存储器管理

nullnull第四章　存储器管理 4.1 存储器的层次结构 4.2　程序的装入和链接 4.3　连续分配方式 4.4　基本分页存储管理方式 4.5　基本分段存储管理方式 4.6　虚拟存储器的基本概念 4.7　请求分页存储管理方式 4.8　页面置换算法 4.9　请求分段存储管理方式 null 存储器是计算机系统的五大组成部分之一。随着计算机技术的发展，存储器容量一直在扩充，但仍不能满足现代软件和用户的需要，因此存储器仍是一种宝贵、紧俏的资源。对存储器加以有效管理，不仅直接影响存储器的利用率，而且对系统性能有重大影响。 存储器管理的主要对象是内存，对外存的管理在文件管理中。null存储管理的主要功能有: 主存分配与回收 地址重定位(地址映射) 存储保护 主存扩充(虚拟内存) 提高内存空间的利用率 null4.1 存储器的层次结构 4.1.1 多级存储器结构 在现代计算机系统中，存储器是信息外理的来源与归宿，占据重要位置。但是，在现有技术条件下，任何一种存储装置，都无法同时从速度与容量两方面，满足用户的需求。实际上它们组成了一个速度由快到慢，容量由小到大的存储装置层次。 对于通用计算机而言，存储层次至少应具有三级：最高层为CPU寄存器，中间为主存，最底层是辅存。 在较高档的计算机中，还可以根据具体的功能分工细划为寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质等6层。null图4-1 计算机系统存储层次示意 null4.1.2 主存储器与寄存器 1．主存储器 主存储器(简称内存或主存)用于保存进程运行时的程序和数据，也称可执行存储器。 其容量对于当前的微机系统和大中型机，可能一般为数十MB到数GB，而且容量还在不断增加，而嵌入式计算机系统一般仅有几十KB到几MB。 CPU的控制部件只能从主存储器中取得指令和数据，数据能够从主存储器读取并将它们装入到寄存器中，或者从寄存器存入到主存储器。 CPU与外围设备交换的信息一般也依托于主存储器地址空间。 由于主存储器的访问速度远低于CPU执行指令的速度，为缓和这一矛盾，在计算机系统中引入了寄存器和高速缓存。 null2．寄存器 寄存器访问速度最快，完全能与CPU协调工作，但价格却十分昂贵，因此容量不可能做得很大。 寄存器的长度一般以字(word)为单位。寄存器的数目，对于当前的微机系统和大中型机，可能有几十个甚至上百个；而嵌入式计算机系统一般仅有几个到几十个。 寄存器用于加速存储器的访问速度，如用寄存器存放操作数，或用作地址寄存器加快地址转换速度等。 null4.1.3 高速缓存和磁盘缓存 　　1．高速缓存 　　高速缓存是现代计算机结构中的一个重要部件，其容量大于或远大于寄存器，而比内存约小两到三个数量级左右，从几十KB到几MB，访问速度快于主存储器。 　　根据程序执行的局部性原理(即程序在执行时将呈现出局部性规律，在一较短的时间内，程序的执行仅局限于某个部分)，将主存中一些经常访问的信息存放在高速缓存中，减少访问主存储器的次数，可大幅度提高程序执行速度。通常，进程的程序和数据时存放在主存储器中，每当使用时，被临时复制到一个速度较快的高速缓存中。null当CPU访问一组特定信息时，首先检查它是否在高速缓存中，如果已存在，可直接从中取出使用，以避免访问主存，否则，再从主存中读出信息。null2．磁盘缓存 由于目前磁盘的I/O速度远低于对主存的访问速度，因此将频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，可减少访问磁盘的次数。 磁盘缓存本身并不是一种实际存在的存储介质，它利用主存中的存储空间，来暂存从磁盘中读出(或写入)的信息。 主存也可以看做是辅存的高速缓存，因为，辅存中的数据必须复制到主存方能使用；反之，数据也必须先存在主存中，才能输出到辅存。 null　　一个文件的数据可能出现在存储器层次的不同级别中，例如，一个文件数据通常被存储在辅存中(如硬盘)，当其需要运行或被访问时，就必须调入主存，也可以暂时存放在主存的磁盘高速缓存中。 大容量的辅存常常使用磁盘，磁盘数据经常备份到磁带或可移动磁盘组上，以防止硬盘故障时丢失数据。有些系统自动地把老文件数据从辅存转储到海量存储器中，如磁带上，这样做还能降低存储价格。 4.2 程序的装入和链接4.2 程序的装入和链接在多道程序环境下，程序要运行必须为之创建进程，而创建进程的第一件事，就是要将程序和数据装入内存。如何将一个用户源程序变为一个可在内存中执行的程序，通常要经过以下几步： （1）编译。由编译程序（Compiler）将用户源代码编译成若干个目标模块（Object Module）； （2）链接。由链接程序（Linker）将编译后形成的目标模块以及它们所需要的库函数，链接在一起，形成一个装入模块（Load Module）； （3）装入。由装入程序（Loader）将装入模块装入内存。null图4-2　对用户程序的处理步骤 null 0 目标 模块 100 0 100 作业J 200 512K 地址空间内存空间装入 关于三个空间的定义：逻辑地址 或 相对地址物理地址 或 绝对地址符号地址null4.2.1 程序的装入 先介绍一个无须进行链接的单个目标模块的装入过程。此时目标模块就是装入模块。 将一个装入模块装入内存时，有三种方式： 绝对装入方式 可重定位装入方式 动态运行时装入方式nullnullnull由于这种地址变换是在作业执行期间随着每条指令的执行自动地、连续地进行，所以称之为动态重定位。null4.2.2 程序的链接 程序经过编译后得到一组目标模块，再利用链接程序将目标模块链接，形成装入模块。根据链接时间的不同，把链接分成三种： 静态链接：在程序运行前，将目标模块及所需的库函数链接成一个完整的装配模块，以后不再拆开。 装入时动态链接：指将用户源程序编译后所得的一组目标模块，在装入内存时，采用边装入边链接的链接方式。 运行时动态链接：指对某些目标模块的链接，是在程序执行中需要该目标模块时，才对它进行链接。null一、静态链接： (Static Linking) 事先将几个目标链接装配成一个装入模块，以后不再拆开的链接方式，称为静态链接方式。如右图： nullSEQAMSUBR 1MAIN系统目标库当前生成的目 标 库私有目标库MAIN …... call SEQAM …... call SURB 1 …... 查找引用读入查找引用装入模块SEQAM …… RETURNSURB 1 …… RETURNnull 如:主程序段 ABif x>0 then call A else call B null静态链接null动态链接4.2 连续分配方式4.2 连续分配方式 连续分配方式，是指为一个用户程序分配一个连续的内存空间。 分类： 单一连续分配 固定分区分配 动态分区分配 动态重定位分区分配null4.2.1 单一连续分配 最简单的一种存储管理方式，但只能用于单用户、单任务的操作系统中。 采用这种存储管理方式时，可把内存分为系统区和用户区两部分，系统区仅提供给OS使用，通常放在内存低址部分，用户区是指除系统区以外的全部内存空间，提供给用户使用。 工作 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 工作流程 单一连续区分配采用静态分配和静态重定位方式，亦即作业或进程一旦进入主存，就一直等到它运行结束后才能释放主存。如下图所示的主存分配与回收法。并且由装入程序检查其绝对地址是否超越，即可达到保护系统的目的。 工作流程(续) 工作流程(续) null4.2.2 固定分区分配 将内存用户空间划分为若干个固定大小的区域，在每个分区中只装入一道作业，这样把用户空间划分为几个分区，便允许有几道作业并发执行。 当有一空闲分区时，便可以再从外存的后备作业队列中，选择一个适当大小的作业装入该分区，当该作业结束时，可再从后备作业队列中找出另一作业调入该分区。null分区大小相等 分区大小不相等null2. 内存分配 为便于内存分配，通常将分区按大小进行排队，并为之建立一张分区使用 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf ，其中各表项包括每个分区的起始地址、大小及状态(是否已分配)。 nullnull固定分区分配算法流程图要求xK大小的分区取分区 说明 关于失联党员情况说明岗位说明总经理岗位说明书会计岗位说明书行政主管岗位说明书 表的 第一项该分区空闲吗？分区大小xK表结束吗？返回分区号状态位置1无法分配取下一项分区回收？null 采用这种技术，虽然可以使多个作业共享主存，但仍不能充分利用它。因为，一个作业的大小，只有当作业调度程序在分析进程创建请求时才能确定；而分区的大小是在系统初启时划定的。由于作业的大小不可能刚好等于某个分区的大小，所以，在每个分配的分区中，通常都有一部分未被作业占用而浪费掉。 这种分配给用户而未被利用的部分，称作存储器的“内零头”(InternaI Fragmentation)。 固定分区方式存储管理的优点是分区 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 特别简单，实现起来也很容易；缺点是存储空间的利用率太低。现在的操作系统几乎不用它了。 null4.3.3 动态分区分配 所谓动态式分区分配是指根据进程的实际需要，动态地为之分配连续的内存空间。这种存储管理的方法解决了固定分区严重浪费内存的问题。是一种较为实用的存储管理方法。 在实现过程中涉及三个问题： 分区分配中的数据结构 分区分配算法 分区分配与回收操作null一、可变分区分配中的数据结构 常用的数据结构有： 1. 空闲分区表： 2. 空闲分区链：nullnull2. 分区分配算法 系统运行一段时间后，在整个存储空间内将出现许多大小不等的区域，有的仍被作业进程占用，有的则因作业已退出系统而成为可用于再分配的区域。现在假设有一个新的作业需调入主存，如何为其选择一个合适的区域？ 常用的分配算法： (1) 首次适应算法FF (2) 循环首次适应算法 (3) 最佳适应算法 (4)最坏适应算法 (5) 快速适应算法(quick fit)null(1) 首次适应算法FF FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；然后按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。若从头到尾不存在满足要求的分区，则分配失败。 优点：算法简单，查找速度快；优先利用内存低址部分的空闲分区,留在高址部分的大的空白区被划分的机会较少，因而在大作业到来时也比较容易得到满足。 缺点：低址部分不断划分，产生小碎片；每次查找从低址部分开始，增加了查找的开销 要求:空闲区表或空闲区链按地址从低到高排列.null例：有四块空白区(从低地址→高地址)，来了一个作业需分配19k内存。解：null(2) 循环首次适应算法（下次适应算法 next fit NF） 在分配内存空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。 为实现算法，需要： 设置一起始查寻指针 采用循环查找方式 优点：使内存中空闲分区分布均匀，减少查找的开销 缺点：缺乏大的空闲分区 要求:空闲区表或空闲区链按地址从低到高排列.null(3) 最佳适应算法(Best fit: BF) 所谓“最佳”是指每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。 要求:空闲分区表或空闲分区链按其容量从小到大排列。 优点：如果存储空间中具有正好是所要求大小的存储空白区，则必然被选中；如果不存在这样的空白区，也只对比要求稍大的空白区进行划分，而绝不会去划分一个更大的空白区。因此，其后遇到大作业到来时，作业要求的存储区域就比较容易得到满足。 缺点：产生许多难以利用的小空闲区；在回收一个分区时，为了把它插入到空白区链中合适的位置上也颇为费时。所以，这种算法乍看起来是最佳的，其实则不然。null指针10k60k90k20k例：有四块空白区(从小容量→大容量)，来了一个作业需分配19k内存。解：再排序练习：练习： 某基于动态分区存储管理的计算机，其主存容量为55MB（初始为空闲），采用最佳适配（Best Fit）算法，分配和释放的顺序为：分配15MB、分配30MB、释放15MB、分配8MB、分配6MB，此时主存中最大空闲分区的大小是（ ）。 【联考2010】 A.7 MB B.9 MB C.10 MB D.15 MBnull (4) 最坏(差)适应算法(Worst fit: WF) 所谓“最坏”是指每次为作业分配内存时，总是把能满足要求、又是最大的空闲分区分配给作业。 要求:空闲分区表或空闲分区链按其容量从大到小排列。再排序指针90k20k10k60k例：有四块空闲区，来了一个作业需分配19k内存。null优点：在划分后剩下的空白区也是最大的，产生碎片几率最小，有利于中小作业；查找效率很高。 缺点：大的空闲区不容易保留，当有大的作业时，其存储空间的申请往往得不到满足。 null外零头:把存储空间中这些小的无用的分区称为 “外零头” (Externa1 Fragmentation)。 内零头:分配给用户而未被利用的部分，称作存储器的“内零头”(InternaI Fragmentation)。什么样的分配方式产生外零头？ 什么样的分配方式产生内零头？四种策略比较四种策略比较上述四种分配策略各有利弊，到底哪种最好不能一概而论，而应针对具体作业序列来分析。 对于某一作业序列来说，某种算法能将该作业序列中所有作业安置完毕，那么我们说该算法对这一作业序列是合适的。 对于某一算法而言，如它不能立即满足某一要求，而其它算法却可以满足此要求，则这一算法对该作业序列是不合适的。 对分配策略的一种有用的度量是，系统对选定的一组作业来运行，比较第一次发生不能满足存储请求所经历的时间。举例：举例：有作业序列：作业A要求18K；作业B要求25K，作业C要求30K。系统中空闲区按三种算法组成的空闲区队列 经分析可知：最佳适应法对这个作业序列是合适的，而其它两种对该作业序列是不合适的。null首次适应算法空闲分区表最佳适应算法空闲分区表最坏适应算法空闲分区表12K 38K2K 118K28K 228K2 30K 20K 1 28K 228K 2 2K 118K 1 5K 160K 例子练习练习有作业序列：作业A要求21K；作业B要求30K，作业C要求25K。null　　5) 快速适应算法(quick fit) 　　该算法又称为分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，这样，系统中存在多个空闲分区链表，同时在内存中设立一张管理索引表，该表的每一个表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。 空闲分区的分类是根据进程常用的空间大小进行划分，如2 KB、4 KB、8 KB等，对于其它大小的分区，如7 KB这样的空闲区，既可以放在8 KB的链表中，也可以放在一个特殊的空闲区链表中。 null　　优点：查找效率高，仅需要根据进程的长度，寻找到能容纳它的最小空闲区链表，并取下第一块进行分配即可。另外该算法在进行空闲分区分配时，不会对任何分区产生分割，所以能保留大的分区，满足对大空间的需求，也不会产生内存碎片。 　　缺点：在分区归还主存时算法复杂，系统开销较大。此外，该算法在分配空闲分区时是以进程为单位，一个分区只属于一个进程，因此在为进程所分配的一个分区中，或多或少地存在一定的浪费。null3. 分区分配操作 分配内存 利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。 设请求的分区大小为u.size，表中每个空闲分区的大小表示为m.size，若m.size- u.sizesize(规定的不再切割的分区大小)，将整个分区分配给请求者，否则从分区中按请求的大小划出一块内存空间分配出去，余下部分留在空闲链中，将分配区首址返回给调用者。null从头开始查表检索完否？m.size>u.size?m.size-u.size≤size?从该分区中划出 u.size大小的分区将该分区分配给请求者 修改有关的数据结构返回返回继续检索下一个表项将该分区从链中移出null回收内存 当进程运行完毕释放内存时，系统根据回收区首址，在空闲分区链(表)中找到相应插入点，此时可能有四种情况： (1) 回收区与插入点的前一个分区F1邻接 (2) 回收区与插入点的后一个分区F2邻接 (3) 回收区与插入点的前后两个分区F1、F2邻接 (4) 回收区既不与F1邻接，又不与F2邻接 null作业：某操作系统采用可变分区分配存储管理方法，用户区为512K，始址为0，用空闲分区表管理空闲分区。若分配时采用分配空闲区低地址部分的 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ，且初始时用户区的512K空间空闲，对下述申请序列： 申请300K，申请100K，释放300K，申请150K，申请30K，申请40K，申请60K，释放30K 回答以下问题： （1）采用首次适应算法，空闲分区有哪些空块（给出始址、大小）？ （2）采用最佳适应算法，空闲分区有哪些空块（给出始址、大小）？ （3）如再申请100K，针对（1）和（2）各有什么结果？4.3.6 可重定位分区分配4.3.6 可重定位分区分配1.动态重定位的引入 随着系统接收的作业的增加，内存中连续的大块分区将不存在，产生了大量的“碎片”。 问题:新的作业无法装入到每个“碎片”小分区上运行，但所有碎片的空间总和可能大于需求。 解决方案:通过移动内存中作业的位置，把原来多个分散的小分区“拼接”成一个大分区的方法，称为“拼接”或“紧凑” /“紧缩”/“澄清”。 缺点：用户程序在内存中的地址发生变化，必须重定位。null2.动态重定位的实现2.动态重定位的实现动态重定位概念: 作业被装入到内存中的相对地址要转换为物理地址，被推迟到程序指令真正要执行的时候进行。null重定位寄存器 1K 实现： （1）必须由硬件地址变换机构重定位寄存器支持：存放程序的起始地址; （2）真正访问的内存物理地址=相对地址+重定位寄存器中地址，当系统对内存进行了“紧凑”，并不需要对程序作修改。null优点： 消除“碎片”，提高了内存利用率，同时提高了系统效率。 缺点： （1）需要动态重定位“硬件”机构支持，增加了系统成本； （2）轻度降低了程序执行速度； （3）“紧凑”处理增加了系统开销。null三、动态重定位分区分配算法请求分配一个大小为xk的分区有大于xk的 空闲区吗？空闲区的总和 xk吗？紧缩存储并相应地修改诸表 (得到一个完整的空闲区xk)分配分区并 修改诸表此刻已经 无法分配 一个分区返回一个 分区号数null说明： 1. 动态重定位分区分配法是利用分区的“拼接”(对空白区而言)或“紧凑”(作业程序而言)技术解决“零头”。 2. 问题— 拼凑时机的选择 (i)出现相邻空白区即拼接；(或某分区被释放后即紧缩)紧缩工作大，开销大，但管理简单 (ii)存贮不足(空白分区不够大)时进行拼接。紧缩次数少，但管理(算法)较复杂。null4.3.7对换 1. 对换（Swapping）的引入 多道程序环境下存在的问题： 阻塞进程占据大量内存空间 许多作业在外存而不能进入内存运行 所谓“对换”，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程和进程所需要的程序和数据，调入内存。null分类： 整体对换(或进程对换)：以整个进程为单位 页面对换或分段对换：以页或段为单位 实现进程对换，系统必须具备的功能： 对换空间的管理 进程的换出 进程的换入null2. 对换空间的管理为了能对交换区中的空闲盘块进行管理，在系统中设置相应的数据结构以记录外存的使用情况（空闲分区表或空闲分区链） 对换空间的分配与回收，与动态分区方式时的内存分配与回收雷同。null3、进程的换入和换出 a.进程的换出： 条件:创建进程需更多的内存空间时, 或内存空间不够用时; 过程:选择阻塞、优先级最低的进程作为换出进程——启动盘块—将进程的程序和数据传送到磁盘的对换区上。 b.进程的换入： 条件:当内存空间稍有空闲时; 过程:找出就绪、但已经换出（到磁盘上）的进程——将其中换出时间最久的进程——将其换出,直至已经无可以换入的进程或或已无法获得足够大的内存来换入进程为止。4.4 基本分页存储管理方式4.4 基本分页存储管理方式 连续分配方式会形成“碎片”，虽然可以通过“紧凑”解决，但开销大。如果允许将一个进程直接分散地装入许多不相邻的分区中，则无需“紧凑”，由此产生离散分配方式。 分类： 分页存储管理方式：离散分配的基本单位是页 （1）基本分页（纯分页）管理： 不具备页面置换功能； 不具备支持实现虚拟存储器的功能； 要求把每个作业全部装入内存后才能运行。 （2）支持虚存管理的请求分页管理。 分段存储管理方式：离散分配的基本单位是段null4.4.1 页面与页表 1. 页面 页面和物理块 分页存储管理是将一个进程的逻辑地址空间分成若干个大小相等的片称为页面或页，并为各页加以编号，从0开始。 同时把内存空间分成与页面相同大小的若干个存储块，称为（物理）块或页框。顺序编号（也从0开始）。nullnull在为进程分配内存时，以块为单位将进程的若干个页分别装入到多个可以不相邻的物理块中。 例如：一个作业的地址空间有m页。那么，只要分配给它m个页框，每一页分别装入一个页框内即可。这里，并不要求这些页框是连续的。 说明： （1）在进程调度时，必须把它的所有页一次装入到主存的页框内；如果当时页框数不足，则该进程必须等待，系统再调度另外的进程。（纯分页方式） （2）进程的最后一页经常装不满而形成“页内碎片”。即存在内零头。null...0块1块2块3块4块5块6块null二、页面大小 在分页系统中对页面的大小应选择得适当。因为： ①若选择的页面较小，一方面可使内存碎片小，并减少了内存碎片的总空间，有利于提高内存利用率；但另一方面，也会使每个进程要求较多的页面，从而导致页表过长，占用大量内存；还会降低页面换进换出的效率。 ②若选择的页面较大，虽然可减少页表长度，提高换进换出效率，但又会使页内碎片增大。 页面的大小通常在512B～8KB选择，但总是2的幂。2.地址结构2.地址结构 逻辑地址 n-1 k k-1 0线性的逻辑地址长度为n位, 包括两部分： 页号P：n-k位,即:地址空间最多允许有2n-k页； 位移量W（页内位移量，即页内地址）：k位,页内地址大小=2kB 若给定一个逻辑地址空间中的地址为A，页面大小为L，则可以由公式求出： 页号P=INT[A/L]，页内地址d=[A] mod L 例如：系统的页面大小L为1KB，A=2170B， 求出P=2,d=122 null逻辑地址 31 12 11 0页号P：12~31共20位 地址空间最多允许有220=1M页，即每个进程占用1M个页。 位移量W：0~11共12位 页内地址大小（即每页的大小）为212B=4KB。 例：现代的大多数计算机系统的逻辑地址空间都支持很大的逻辑地址空间（232——264）B，如下逻辑地址长度为32位，包括两部分：null(357101)8＝(011,101,111,001,000,001)2 ＝(01,110,1111,001,000,001)2例：设虚地址为(357101)8 每一块为1K字节块（页）的大小：1K=2101 6 7 1 1 0 1位移量为(1101)8, 页号为(167)8null3.页表 在分页系统中，存储分配问题变得非常简单，作业的一页可以分配到存储空间中任何一个可用的页框。 问题： (1)系统怎么知道作业的哪一页分配在存储空间的哪一页框内？ (2)如何实现以及何时实现把作业的逻辑地址变换为主存的物理地址。 null页表： 系统为每一个进程建立的，在内存中找到每个页面所对应的物理块号的一张页面映像表。 一个进程占用多少页，就在页表中有多少页表项。 页表的作用：实现从页号到物理块号的地址映射。 数据结构： 页号、块号、存取控制字段（控制存储块中的内容是允许读/写、只读、只执行）。 根据每页内容的不同，可以设置不同的存取限制。所以，在页表的表目中除了包含指向所在页框的指针外，还包括一个存取控制字段，这个表目也称为页描述子。null内存图4-12页表的作用4.4.2 地址变换机构4.4.2 地址变换机构地址映射——从逻辑地址到物理地址的变换过程。 将用户地址空间中的逻辑地址变换为内存空间中的物理地址，系统设置了地址变换机构。 由于页内地址和物理地址一一对应，所以地址变换机构只是将逻辑地址中的页号，转换为内存中的物理地址的物理块号。借助页表完成。逻辑地址 物理地址1.基本的地址变换机构1.基本的地址变换机构在实际系统中，为了减少硬件成本，将页表存放在被保护的系统区内的一个连续空间中。 这张页表是在进程装入主存时，由系统根据内存分配情况建立的。null分页地址变换机构变换过程： （1）进程执行之前：PCB（内存中的页表始址+页表长度） （2）进程调度后：页表寄存器PTR （内存中的页表始址+页表长度） （3）检索页表： 条件：页表长度>逻辑地址中的页号 不成立：所访问的地址越界，产生一地址越界中断； 成立：未地址越界，则： 由“页表始址+页号x页表项长度”找到该页号在页表中的位置。 null关于分页的地址变换计算--- 页式地址映射关于分页的地址变换计算--- 页式地址映射设页面大小为2KBnull例1：某采用分页存储管理的系统中，物理地址占20位，逻辑地址中页号占6位，页面大小为1KB，问： ⑴该系统的内存空间大小为多少？每个存储块的大小为多少？逻辑地址共几位？每个作业的最大长度为多少？ ⑵若第0、1、2页分别放在第3、7、9存储块中，则逻辑地址0420H对应的物理地址是多少？null 解： ⑴物理地址占20位，所以该系统的内存空间大小为：220=1MB 存储块的大小与页面大小相同，而页面大小为1KB，因此存储块的大小为：1KB 由于页面大小为1KB，占10位，而页号占6位，因此逻辑地址共16位。 逻辑地址共16位，从而该系统中的每个作业大小为：216=64KBnull ⑵逻辑地址到物理地址转换的计算方法 ： 分页系统中基本的地址变换：有两种方式，一种是十进制计算方法，另一种是二进制计算方法。 十进制计算方法：设页号为P、页内位移为W、逻辑地址为A、物理地址为M、页面大小为L。 第一步，根据公式计算页号和位移量: 页号：P=int(A/L)，位移量：W=A mod L 第二步，查找页表，确定第一步中计算得到的页号所对应的块号。 第三步，计算物理地址，M=块号*L+Wnull十进制计算方法 第一步： 将逻辑地址转换成10进制：0420H=1056 页号：P=int(A/L)=int（1056/1024）=1 位移量：W=A mod L=1056 mod 1024=32 第二步： 查页表，1号页面对应7号物理块，每个物理块大小为1K。 第三步： 物理地址为：7×1K+32=7200。 null ⑵逻辑地址到物理地址转换的计算方法 ： 二进制计算方法： 第一步，将逻辑地址以二进制形式表示。 第二步，根据页面大小，计算位移量所占二进制位数，并将逻辑地址划分为页号和页内位移量两部分。 第三步，把第二步中划分得到的页号部分转换为十进制，查找页表，确定所对应的块号。 第四步，将第三步中得到的块号转换为二进制，并与第二步中划分得到的页内位移量拼接（页内位移量作为低地址部分），至此物理地址计算完毕。也可以将物理地址转换为十六进制表示方式。 说明：一定要能够根据页面大小确定位移量所占二进制位数。常见页面大小为1K、2K、4K和8K，所需二进制位数依次为10、11、12和13。null二进制计算方法： 第一步，将逻辑地址转换为二进制： 0420H=0000 0100 0010 0000 第二步，页面大小为1K，所以位移量占10个二进制位，将逻辑地址划分为页号和页内位移量两部分： 0000 0100 0010 0000 第三步，把页号部分转换为十进制，查找页表，确定所对应的块号： (0000 01)2=1，1号页对应7号物理块。 第四步，将第三步中得到的块号转换为二进制，并与第二步中划分得到的页内位移量拼接，即得物理地址: 0001 1100 0010 0000 也可以转换为十六进制：1C20H。null练习：在分页存储系统中地址结构的长度为20位，页面大小为2K，作业地址空间为8K，该作业各页依次存放在1，3，6，7号物理块中，相对地址4000处有一条指令 Store l，2500，请给出该作业的页表，并分别指出该指令所在页号和对应的物理单元及数据存放所在的页号和物理单元。 null 由题意，页面大小为2K，该作业的地址 空间为8K，因此该作业有4页，其页表为： 计算相对地址4000的物理地址 页号：P=int(A/L)=int（4000/2048）=1 位移量：W=A mod L=4000 mod 2048=1952 物理地址为：3*2048+1952=8096 计算相对地址2500的物理地址 页号：P=int(A/L)=int（2500/2048）=1 位移量：W=A mod L=2500 mod 2048=452 物理地址为：3*2048+452=6596null作业1：某虚拟存储器的用户空间共有32个页面，每页1KB，主存16KB。试问： （1）逻辑地址的有效位是多少？ （2）物理地址需要多少位？ （3）假定某时刻系统用户的第0，1，2，3页分别分配的物理块号为5，10，4，7，试将虚地址0A5C和093C变换为物理地址。 作业2：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、10、5块，试将虚地址7145，3412转换成内存地址。2.具有快表的地址变换机构2.具有快表的地址变换机构提出改进的原因： 计算机CPU存取数据需要访问内存两次，处理速度降低为1/2。 改进方法： 利用联想寄存器（快表）——并行查询； 空间大小： 几K到几百K ，存放16~512个页表项；null实现原理： 快表与页表同时访问： （1）在快表中找到相匹配的页号—— 直接从快表中读出对应物理块号； （2）在快表中没有找到相匹配的页号—— 还须找页表，再从页表中对出物理块号； 再将此页表项存入快表中，重新更新快表。 优点：加快了地址变换的速度。null页表始址页表长度页表寄存器﹥页表51250物理地址页号（3）页内地址（1250）逻辑地址越界中断输入寄存器图4-14 具有快表的地址变换机构null 当调度合理时，命中率可以达到90％以上。考虑到快表的速度是内存速度的数倍或数十倍，那么相对于内存速度，访问页表的时间可以忽略不计。也就是说页地址变换不会造成进程运行速度下降多少。null例：设访问主存时间为200ns,访问联想存贮器为40ns，命中率为90％，则平均存取时间为多少？查页表两次访存：平均为200＋200＝400ns查快表，平均为： (200+40)×90％＋(200+200+40)×10％ ＝260ns解：方法1：方法2：null4.3.3 两级和多级页表 现代计算机系统都支持非常大的逻辑地址空间(232264)，页表就非常大，需占用较大的地址空间。 例如：一个具有32位逻辑地址空间的分页系统，规定页面大小为4KB即212B，则每个进程页表的页表项可达1M个，若每个页表项占用一个字节，则每个进程的页表就要占据1MB的内存空间，而且要求连续存放。 解决方法： 采用离散方式 只将当前所需页表项调入内存null1. 两级页表 将页表分页，并离散地将各个页面分别存放在不同的物理块中，同时为离散分配的页表再建立一张页表，称为外层页表，其每个页表项记录了页表页面的物理块号。null例如： 32位逻辑地址空间，页面大小为4KB(即12位)，每个页表项占4个字节，若采用一级页表机构，应有20位页号，即页表项应有1M个；在采用两级页表机构时，再对页表进行分页，使每页包含210(即1024)个页表项，最多允许有210个页表分页。即null页表页目录表nullnull 上述方法用离散分配空间解决了大页表无需大片存储空间的问题，但并未减少页表所占的内存空间。 解决方法是把当前需要的一批页表项调入内存，以后再根据需要陆续调入。null2. 多级页表 两级页表对32位机器适用，64位呢？ 页面大小为4KB即212B，还剩52位，按物理块大小212B来划分页表，则剩余42位用于外层页号，此时外层页表可能有4096G个页表项，要占用16384GB的连续存储空间 解决方法：采用多级页表，将外层页表再进行分页。将各个分页离散地装入到不相邻接的物理块中，再利用第2级的外层来映射它们之间的关系。 逻辑地址映射到物理地址的方法和二级页表相同。null 练习：某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为210字节，页表项大小为2字节，逻辑地址结构为： ，逻辑地址空间大小为216页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是（ ）。【联考 2010】 A.64 B.128 C.256 D.512 【分析】本题目关键是确定页目录号占用多少位。已知页大小为210字节，页表项大小为2字节，因此，每页可以包含29个页表项，即页号部分占用9位；又已知逻辑地址空间大小为216页，即页目录号和页号总共占用16位，因此，页目录号占用7位，所以应该选择B。例：一个由四个页面（页号为0―3），每页由1024个字节组成的程序，把它装入由8个物理块（块号为0―7）组成的存储器中，装入情况如下表所示。已知下面的逻辑地址（其中方括号中的第一个元素为页号，第二个元素为页内地址）， 请按页表求出对应的物理地址。 （1）[0，100]； （2）[1，179]； （3）[2，785]；例：一个由四个页面（页号为0―3），每页由1024个字节组成的程序，把它装入由8个物理块（块号为0―7）组成的存储器中，装入情况如下表所示。已知下面的逻辑地址（其中方括号中的第一个元素为页号，第二个元素为页内地址）， 请按页表求出对应的物理地址。 （1）[0，100]； （2）[1，179]； （3）[2，785]；解答：因为每页有1024B，所以内存中 每块也有1024B。 物理地址 ＝ 块号×块长 + 页内地址， 得到：（1）的物理地址为：3×1024+100=3072+100=3172 （2）的物理地址为：5×1024+179=5120+179=5299 （3）的物理地址为：6×1024+785=6144+785=6929 null作业：已知某系统页面长4KB，每个页表项为4B，采用多层分页策略映射64位的用户地址空间。若限定最高层页表只占1页，则它可采用几层分页策略？4.5 基本分段存储管理方式4.5 基本分段存储管理方式提出分段管理的目的除了可以提高内存空间的利用率外，主要是为了更好地实现程序的共享和动态链接，并方便用户编程。 页式管理是把内存视为一维线性空间；而段式管理是把内存视为二维空间，与进程逻辑相一致。 null4.5.1 分段存储管理方式的引入 主要是为了满足用户的下述一系列要求： 1.方便编程。一个段可定义为一组逻辑信息，如子程序，数组或工作区，(分段是程序中自然划分的一组逻辑意义完整的信息集合，它是用户在编程时决定的)。因此，每个作业的地址空间是由一些分段构成的，每段都有自己的名字，且都是一段连续的地址空间。可见，整个作业的地址空间是二维的。null2.信息共享。一般实现程序和数据共享时都是以信息的逻辑单位为基础的。在分页系统中的每一页都只是存放信息的物理单位，其本身并无完整意义，因而不便于实现信息共享，而段却是信息的逻辑单位，通常是可以表达某种意义的，采用分段存储管理，更便于实现程序和数据的共享。 3.信息保护。对内存中的信息的保护，同样也是对信息的逻辑单位进行保护。采用分段存储管理，对实现信息保护，将是更有效和方便。 4.动态增长。在实际使用中，往往有些段，特别是数据段会随着程序的运行不断增大，而这种增长事先并不知晓会增长到多大，采用其它存储管理方式是难以应付的，而分段存储管理却能较好的解决这一问题。 5.动态链接。前面已谈到，采用动态链接能更有效提高存储空间的利用率。由于每个程序模块构成独立的分段，并有自己的段名，因而实现动态链接是比较容易的。 null4.5.2 分段系统的基本原理 1、分段 在分段管理系统中，对所有地址空间的访问均要求两个成分： (1)段的名字； (2)段内地址。 例如，可按下述调用： CALL [X]| 转移到子程序X中的入口点Y LOAD 1, [A]| 将数组A的D单元的值读入寄存器1 STORE 1,[B]| 将寄存器1的内容存入分段B的C单元中 这些符号程序经汇编和装配后，指令和数据的单元地址均由两部分构成：一是表示段名的段号S；一是位移量W，即段内地址。所以，在分段系统中的地址结构有如下形式：null 一旦段号字段和位移量字段的长度确定后，一个作业地址空间中允许的最多段数及段的长度也就限定了。上述地址结构表明，该系统可允许一个作业有256段，最大段长为64K字节。null所谓分段管理，就是管理由若干分段组成的作业，且按分段来进行存储分配。实现分段管理的关键在于，如何保证分段(二维)地址空间中的一个作业在线性(一维)的存储空间中正确运行。 分段式存储管理的实现是基于动态分区存储管理的原理。系统为每个分段分配一个连续的分区，而进程中的各个段可以离散地移入内存中不同的分区中。 基本分段存储管理方式中，进程运行时，其各段必须全部装入内存。null2. 段表 为使程序正常运行，须在系统中为每个进程建立一张段映射表，简称“段表”。每个段在表中占有一个表项，其中记录了该段在内存中的起始地址(段基址)和段的长度。 段表可以存放在寄存器中，但更多的是存放在内存中。 段表可以实现从逻辑地址到内存物理地址的映射。nullnull3. 地址变换机构 在系统中设置段表寄存器，用于存放段表始址和段表长度，以实现从进程的逻辑地址到物理地址的变换。 段表寄存器和段表还有存储保护的功能nullnull 问题：当段表存放在内存中时，每访问一个数据，都需两次访问内存，降低了计算机的速率。 解决方法：设置联想寄存器（快表），用于保存最近常用的段表项。这样,比起没有地址变换的常规存储器的存取速度来仅慢约10%～15%.地址映射 Cl Cb+段号S 段内地址d比较比较b + d 段表S>= Cl快表物理地址段表始址寄存器段表长度寄存器逻辑地址lb...Slb地址越界d>=1d>=1地址映射地址越界地址越界比较null4. 分页和分段的主要区别 相似点： 采用离散分配方式，通过地址映射机构实现地址变换 不同点： 页是信息的物理单位，分页是为了满足系统的需要,提高内存利用率；段是信息的逻辑单位，含有一组意义相对完整的信息，分段是为了满足用户的需要。 页的大小固定且由系统确定，由系统把逻辑地址分为页号和页内地址，由机器硬件实现；段的长度不固定，取决于用户程序，编译程序对源程序编译时根据信息的性质划分。 分页的作业地址空间是一维的；分段的作业地址空间是二维的。null4.5.3 信息共享 分段系统的一个突出优点是易于实现段的共享，允许若干个进程共享一个或多个分段，且对段的保护十分简单易行。 分页系统中虽然也能实现程序和数据的共享，但远不如分段系统方便。 看下面的一个例子：一个多用户系统可接纳40个用户，他们都执行一个文本编辑程序ED，ED代码共160K，每个用户还有40K的数据区null 如果不采用信息共享，每个用户有160KB的代码和40KB的数据区，40个用户共需8000KB内存。 40×(160+40)=8000K 对ED代码共享，所需的内存空间为1760KB。 160+40×40=1760K 假定在分页系统中，每个页面大小为4KB，160KB的代码将占用40个页面，数据区占10个页面。为了实现代码的共享，每个进程的页表中都建立50个页表项。比较浪费空间。null 利用分页共享原理上述多用户系统的存储分配如下：（假定页面大小为4K，两个用户）null 段式的共享：在分段系统中，实现共享十分容易，只需在每个进程的段表中为共享代码段设置一个段表项。null可重入代码又称为纯代码，是一种允许多个进程同时访问的代码，可重入代码不允许任何进程对它进行修改。 所以在每个进程中都配备局部数据区，把在执行中可能改变的部分拷贝到该数据区。 －在程序执行时，只修改该进程私有的数据区内容，而不去修改多进程所共享的可重入代码。 null4.5.4 段页式存储管理方式 分段和分页存储管理方式各有优缺点 把两者结合成一种新的存储管理方式——段页式存储管理方式，具有两者的长处。 这种技术的基本思想是，用分段方法来分配和管理虚拟地址空间，而用分页方法来分配和管理实存储器(即主存)。 1. 基本原理 先将用户程序分成若干段，并为每个段赋予一个段名，再把每个段分成若干页个固定大小的页面。 每个进程有一张段表,每个段有一张页表。 在段页式系统中，地址结构由段号、段内页号和页内地址三部分所组成。 null和分页系统一样，这些未写满的页，在装入主存空间后，依然存在内零头问题。null用户程序划分 按段式划分（对用户来讲，按段的逻辑关系进行划分；对系统讲，按页划分每一段）。 逻辑地址 内存划分 按页式存储管理方案 内存分配 以页为单位进行分配null处理机给出的有效地址长度确定了一个进程可用地址空间范围。而这个具体的地址结构，确定了一个进程最多能有多少段，每段多少页，以及页面的大小。上述可允许有256段，每段16页、页面的大小为4K字节。 再次强调，程序的分段可以由程序员或编译程序根据信息的逻辑结构来划分；而分页则与程序员无关，是由系统自动进行的。这就是说，程序员使用的编址方式或编译程序给出的目标程序的地址形式仍然是二维的，即段号S和段内相对地址W’；而只是由地址变换机构把W’的高四位解释为页号P，把低十二位解释为页内相对地址(位移量)W。 null利用段表和页表实现地址映射null2. 地址变换机构 在段页式系统中，为了实现地址变换，增加一个段表寄存器，用来存放段表始址和段长。nullnull在段页式系统中，为了获得一条指令或数据，需要访问三次内存： 第一次：访问内存中的段表，取得页表始址 第二次：访问内存中的页表，取得该页所在的物理块号，将块号与页内地址形成物理地址 第三次：访问第二次所得的地址，取出指令或数据 缺点：访内存次数增加两倍 解决方法：增设高速缓冲寄存器（快表）null补充题：某用户进程分了3个逻辑段，段表内容如下表。求与下面逻辑地址相对应的物理地址 1|100K，0|15K，2|150K，3|20K 思考： 1、段式存储管理与可变分区存储管理方案的相同点与不同点？ 2、在具有快表的段页式存储管理方案中，如何实现地址变换？null引入：其目标是在较小的可用内存中运行较大的程序。常用于多道程序系统，与分区存储管理配合使用。 基本思想:覆盖技术是将内存的同一区域按照使用的先后顺序，分配给几个不同进程或一个进程的几个程序段或数据段，即允许进程运行时，可以不用把它的所有程序段都调入内存，当进程处理需要某程序段时将它装入到原来已经占用的某分区中，原来存储在这个分区中的程序就被“覆盖”了。 优点：解决小主存容量与大作业之间的矛盾。覆盖(overlay)null采用覆盖技术后，进程可以分为常驻内存部分和覆盖部分，常驻内存部分是指进程处理过程中始终需要的程序段，而覆盖部分是进程处理过程中动态调入内存的程序段。 当进程要求运行时，系统根据其覆盖结构，给它分配一段存储空间，其大小等于常驻部分和覆盖区之和。覆盖区长度由相应覆盖段中最大程序段的长度确定。处理过程是先把常驻内存部分调入，然后将首先需要的可覆盖程序段由辅存调入，随着进程执行，再将其它存放在辅存的覆盖部分陆续调入。null注：另一种覆盖方法：(100K) A(20K)占一个分区：20K； B(50K)、D(20K)和E(40K)共用一个分区：50K； F(30K)和C(30K)共用一个分区：30K；覆盖技术不存在调用关系的模块不必同时装入到内存，从而可以相互覆