《存储器管理》 (2)

1、第四章存储器管理 4.1 存储器的层次结构 4.2程序的装入和链接 4.3连续分配方式4.4基本分页存储管理方式4.5基本分段存储管理方式4.6虚拟存储器的基本概念4.7请求分页存储管理方式4.8页面置换算法4.9请求分段存储管理方式 精选ppt 存储器是计算机系统的五大组成部分之一。随着计算机技术的发展，存储器容量一直在扩充，但仍不能满足现代软件和用户的需要，因此存储器仍是一种宝贵、紧俏的资源。对存储器加以有效管理，不仅直接影响存储器的利用率，而且对系统性能有重大影响。存储器管理的主要对象是内存，对外存的管理在文件管理中。精选ppt存储管理的主要功能有: 主存分配与回收 地址重定位(地址映射

2、) 存储保护 主存扩充(虚拟内存) 提高内存空间的利用率精选ppt4.1 存储器的层次结构 4.1.1 多级存储器结构在现代计算机系统中，存储器是信息外理的来源与归宿，占据重要位置。但是，在现有技术条件下，任何一种存储装置，都无法同时从速度与容量两方面，满足用户的需求。实际上它们组成了一个速度由快到慢，容量由小到大的存储装置层次。 对于通用计算机而言，存储层次至少应具有三级：最高层为CPU寄存器，中间为主存，最底层是辅存。在较高档的计算机中，还可以根据具体的功能分工细划为寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质等6层。精选ppt图4-1 计算机系统存储层次示意 精选ppt

3、4.1.2 主存储器与寄存器1主存储器主存储器(简称内存或主存)用于保存进程运行时的程序和数据，也称可执行存储器。其容量对于当前的微机系统和大中型机，可能一般为数十MB到数GB，而且容量还在不断增加，而嵌入式计算机系统一般仅有几十KB到几MB。CPU的控制部件只能从主存储器中取得指令和数据，数据能够从主存储器读取并将它们装入到寄存器中，或者从寄存器存入到主存储器。CPU与外围设备交换的信息一般也依托于主存储器地址空间。由于主存储器的访问速度远低于CPU执行指令的速度，为缓和这一矛盾，在计算机系统中引入了寄存器和高速缓存。 精选ppt2寄存器寄存器访问速度最快，完全能与CPU协调工作，但价格却十

4、分昂贵，因此容量不可能做得很大。寄存器的长度一般以字(word)为单位。寄存器的数目，对于当前的微机系统和大中型机，可能有几十个甚至上百个；而嵌入式计算机系统一般仅有几个到几十个。寄存器用于加速存储器的访问速度，如用寄存器存放操作数，或用作地址寄存器加快地址转换速度等。 精选ppt4.1.3 高速缓存和磁盘缓存1高速缓存高速缓存是现代计算机结构中的一个重要部件，其容量大于或远大于寄存器，而比内存约小两到三个数量级左右，从几十KB到几MB，访问速度快于主存储器。根据程序执行的局部性原理(即程序在执行时将呈现出局部性规律，在一较短的时间内，程序的执行仅局限于某个部分)，将主存中一些经常访问的信息存

5、放在高速缓存中，减少访问主存储器的次数，可大幅度提高程序执行速度。通常，进程的程序和数据时存放在主存储器中，每当使用时，被临时复制到一个速度较快的高速缓存中。精选ppt当CPU访问一组特定信息时，首先检查它是否在高速缓存中，如果已存在，可直接从中取出使用，以避免访问主存，否则，再从主存中读出信息。精选ppt2磁盘缓存由于目前磁盘的I/O速度远低于对主存的访问速度，因此将频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，可减少访问磁盘的次数。磁盘缓存本身并不是一种实际存在的存储介质，它利用主存中的存储空间，来暂存从磁盘中读出(或写入)的信息。主存也可以看做是辅存的高速缓存，因为，辅存中的数据

6、必须复制到主存方能使用；反之，数据也必须先存在主存中，才能输出到辅存。 精选ppt一个文件的数据可能出现在存储器层次的不同级别中，例如，一个文件数据通常被存储在辅存中(如硬盘)，当其需要运行或被访问时，就必须调入主存，也可以暂时存放在主存的磁盘高速缓存中。大容量的辅存常常使用磁盘，磁盘数据经常备份到磁带或可移动磁盘组上，以防止硬盘故障时丢失数据。有些系统自动地把老文件数据从辅存转储到海量存储器中，如磁带上，这样做还能降低存储价格。 精选ppt4.2 程序的装入和链接在多道程序环境下，程序要运行必须为之创建进程，而创建进程的第一件事，就是要将程序和数据装入内存。如何将一个用户源程序变为一个可在内

7、存中执行的程序，通常要经过以下几步：（1）编译。由编译程序（Compiler）将用户源代码编译成若干个目标模块（Object Module）；（2）链接。由链接程序（Linker）将编译后形成的目标模块以及它们所需要的库函数，链接在一起，形成一个装入模块（Load Module）；（3）装入。由装入程序（Loader）将装入模块装入内存。精选ppt图4-2对用户程序的处理步骤 库链接程序装入模块装入程序编译程序产生的目标模块第一步第二步第三步内存精选ppt0 目标模块100 0 100 作业J200 512K 地址空间符号指令 数据说明 I/O说明名空间(作业 J 的源程序)内存空间装入编译

8、关于三个空间的定义：逻辑地址或相对地址物理地址或绝对地址符号地址精选ppt4.2.1 程序的装入 先介绍一个无须进行链接的单个目标模块的装入过程。此时目标模块就是装入模块。将一个装入模块装入内存时，有三种方式：绝对装入方式可重定位装入方式动态运行时装入方式精选ppt 符号地址程 序JUMP iLOAD jDATAijab程 序JUMP 1424LOAD 2224DATA14242224绝对地址1024精选ppt365LOAD 1,2500365LOAD 1,2500 010002500500010000110001250015000作业地址空间内存空间精选pptLoad 1,2500 365L

9、oad 1,2500 3650100025005000010000作业地址空间存储空间重定位寄存器11000125002500 10000相对地址+由于这种地址变换是在作业执行期间随着每条指令的执行自动地、连续地进行，所以称之为动态重定位。精选ppt4.2.2 程序的链接 程序经过编译后得到一组目标模块，再利用链接程序将目标模块链接，形成装入模块。根据链接时间的不同，把链接分成三种：静态链接：在程序运行前，将目标模块及所需的库函数链接成一个完整的装配模块，以后不再拆开。装入时动态链接：指将用户源程序编译后所得的一组目标模块，在装入内存时，采用边装入边链接的链接方式。运行时动态链接：指对某些目标

10、模块的链接，是在程序执行中需要该目标模块时，才对它进行链接。精选ppt一、静态链接： (Static Linking) 事先将几个目标链接装配成一个装入模块，以后不再拆开的链接方式，称为静态链接方式。如右图： 模块ACALL B;Return;0L-1模块BCALL C;Return;0M-1模块C Return;0N-10L-1模块AJSR “L”Return;LL+M-1模块BJSR “L+M”;Return;模块C Return;L+ML+M+N-1精选pptSEQAMSUBR 1MAIN系统目标库当前生成的目 标 库私有目标库MAIN .call SEQAM.call SURB 1.

11、查找引用读入查找引用装入模块SEQAM RETURNSURB 1 RETURN精选ppt 如:主程序段ABif x0 then call A else call B 精选ppt静态链接精选ppt动态链接精选ppt4.2 连续分配方式 连续分配方式，是指为一个用户程序分配一个连续的内存空间。分类：单一连续分配固定分区分配动态分区分配动态重定位分区分配精选ppt4.2.1 单一连续分配 最简单的一种存储管理方式，但只能用于单用户、单任务的操作系统中。 采用这种存储管理方式时，可把内存分为系统区和用户区两部分，系统区仅提供给OS使用，通常放在内存低址部分，用户区是指除系统区以外的全部内存空间，提供给

12、用户使用。OS用户区精选ppt工作流程 单一连续区分配采用静态分配和静态重定位方式，亦即作业或进程一旦进入主存，就一直等到它运行结束后才能释放主存。如下图所示的主存分配与回收法。并且由装入程序检查其绝对地址是否超越，即可达到保护系统的目的。精选ppt工作流程(续)精选ppt4.2.2 固定分区分配将内存用户空间划分为若干个固定大小的区域，在每个分区中只装入一道作业，这样把用户空间划分为几个分区，便允许有几道作业并发执行。当有一空闲分区时，便可以再从外存的后备作业队列中，选择一个适当大小的作业装入该分区，当该作业结束时，可再从后备作业队列中找出另一作业调入该分区。精选ppt分区大小相等 分区大小

13、不相等精选ppt2. 内存分配为便于内存分配，通常将分区按大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态(是否已分配)。精选ppt未分配1281284已分配64643已分配32322已分配24121状态起址(K)大小(K)分区号分区说明表作业C作业B作业A操作系统 24K32K64K128K256K存储空间分配情况精选ppt固定分区分配算法流程图要求xK大小的分区取分区说明表的第一项该分区空闲吗？分区大小xK表结束吗？返回分区号状态位置1无法分配取下一项NYYYNN分区回收？精选ppt 采用这种技术，虽然可以使多个作业共享主存，但仍不能充分利用它。因为，一

14、个作业的大小，只有当作业调度程序在分析进程创建请求时才能确定；而分区的大小是在系统初启时划定的。由于作业的大小不可能刚好等于某个分区的大小，所以，在每个分配的分区中，通常都有一部分未被作业占用而浪费掉。这种分配给用户而未被利用的部分，称作存储器的“内零头”(InternaI Fragmentation)。 固定分区方式存储管理的优点是分区方法特别简单，实现起来也很容易；缺点是存储空间的利用率太低。现在的操作系统几乎不用它了。 精选ppt4.3.3 动态分区分配所谓动态式分区分配是指根据进程的实际需要，动态地为之分配连续的内存空间。这种存储管理的方法解决了固定分区严重浪费内存的问题。是一种较为实

15、用的存储管理方法。在实现过程中涉及三个问题：分区分配中的数据结构分区分配算法分区分配与回收操作精选ppt一、可变分区分配中的数据结构 常用的数据结构有： 1. 空闲分区表： 序号始址长度115K23K248K20K380K30K.2. 空闲分区链：N个字节可用（未分配）状态位 大小 指针 0 N+2 前向指针 0 N+2 后向 指针 精选ppt精选ppt2. 分区分配算法系统运行一段时间后，在整个存储空间内将出现许多大小不等的区域，有的仍被作业进程占用，有的则因作业已退出系统而成为可用于再分配的区域。现在假设有一个新的作业需调入主存，如何为其选择一个合适的区域？常用的分配算法：(1) 首次适应

16、算法FF(2) 循环首次适应算法(3) 最佳适应算法(4)最坏适应算法(5) 快速适应算法(quick fit)精选ppt(1) 首次适应算法FFFF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；然后按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。若从头到尾不存在满足要求的分区，则分配失败。优点：算法简单，查找速度快；优先利用内存低址部分的空闲分区,留在高址部分的大的空白区被划分的机会较少，因而在大作业到来时也比较容易得到满足。缺点：低址部分不断划分，产生小碎片；每次查找从低址部分开始，

17、增加了查找的开销要求:空闲区表或空闲区链按地址从低到高排列.精选ppt例：指针10k60k90k20k有四块空白区(从低地址高地址)，来了一个作业需分配19k内存。指针10k60k90k20k41k解：精选ppt(2) 循环首次适应算法（下次适应算法 next fit NF） 在分配内存空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。为实现算法，需要：设置一起始查寻指针采用循环查找方式优点：使内存中空闲分区分布均匀，减少查找的开销缺点：缺乏大的空闲分区要求:空闲区表或空闲区链按地址从低到高排列.精选ppt(

18、3) 最佳适应算法(Best fit: BF) 所谓“最佳”是指每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。要求:空闲分区表或空闲分区链按其容量从小到大排列。优点：如果存储空间中具有正好是所要求大小的存储空白区，则必然被选中；如果不存在这样的空白区，也只对比要求稍大的空白区进行划分，而绝不会去划分一个更大的空白区。因此，其后遇到大作业到来时，作业要求的存储区域就比较容易得到满足。缺点：产生许多难以利用的小空闲区；在回收一个分区时，为了把它插入到空白区链中合适的位置上也颇为费时。所以，这种算法乍看起来是最佳的，其实则不然。精选ppt指针10k60k90

19、k20k例：有四块空白区(从小容量大容量)，来了一个作业需分配19k内存。指针10k20k60k90k1k解：再排序精选ppt练习： 某基于动态分区存储管理的计算机，其主存容量为55MB（初始为空闲），采用最佳适配（Best Fit）算法，分配和释放的顺序为：分配15MB、分配30MB、释放15MB、分配8MB、分配6MB，此时主存中最大空闲分区的大小是（ ）。 【联考2010】 A.7 MB B.9 MB C.10 MB D.15 MB精选ppt (4) 最坏(差)适应算法(Worst fit: WF)所谓“最坏”是指每次为作业分配内存时，总是把能满足要求、又是最大的空闲分区分配给作业。要求

20、:空闲分区表或空闲分区链按其容量从大到小排列。指针90k60k20k10k71k再排序指针90k20k10k60k例：有四块空闲区，来了一个作业需分配19k内存。精选ppt优点：在划分后剩下的空白区也是最大的，产生碎片几率最小，有利于中小作业；查找效率很高。缺点：大的空闲区不容易保留，当有大的作业时，其存储空间的申请往往得不到满足。 精选ppt外零头:把存储空间中这些小的无用的分区称为 “外零头” (Externa1 Fragmentation)。内零头:分配给用户而未被利用的部分，称作存储器的“内零头”(InternaI Fragmentation)。什么样的分配方式产生外零头？什么样的分配

21、方式产生内零头？精选ppt四种策略比较上述四种分配策略各有利弊，到底哪种最好不能一概而论，而应针对具体作业序列来分析。对于某一作业序列来说，某种算法能将该作业序列中所有作业安置完毕，那么我们说该算法对这一作业序列是合适的。对于某一算法而言，如它不能立即满足某一要求，而其它算法却可以满足此要求，则这一算法对该作业序列是不合适的。对分配策略的一种有用的度量是，系统对选定的一组作业来运行，比较第一次发生不能满足存储请求所经历的时间。精选ppt举例：有作业序列：作业A要求18K；作业B要求25K，作业C要求30K。系统中空闲区按三种算法组成的空闲区队列经分析可知：最佳适应法对这个作业序列是合适的，而其

22、它两种对该作业序列是不合适的。精选pptOS30K使用20K使用5K使用46K020K100K160K210K255K分区号大小起始地址130K20K220K100K35K160K446K210K首次适应算法空闲分区表分区号大小起始地址15K160K220K100K330K20K446K210K最佳适应算法空闲分区表分区号大小起始地址146K210K230K20K320K100K45K160K最坏适应算法空闲分区表OS30K使用20K使用5K使用46K020K100K160K210K255K作业A18K作业序列作业A18KOS30K使用20K使用5K使用46K020K100K160K210K2

23、55K作业序列255KOS30K使用20K使用5K使用46K020K100K160K210K作业A18K作业序列12K 38K2K 118K28K 228K2 30K 20K 1 28K 228K 2 2K 118K 1 5K 160K 例子精选ppt练习有作业序列：作业A要求21K；作业B要求30K，作业C要求25K。精选ppt5) 快速适应算法(quick fit)该算法又称为分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，这样，系统中存在多个空闲分区链表，同时在内存中设立一张管理索引表，该表的每一个表项对应了一种空闲分区类型

24、，并记录了该类型空闲分区链表表头的指针。 空闲分区的分类是根据进程常用的空间大小进行划分，如2 KB、4 KB、8 KB等，对于其它大小的分区，如7 KB这样的空闲区，既可以放在8 KB的链表中，也可以放在一个特殊的空闲区链表中。 精选ppt优点：查找效率高，仅需要根据进程的长度，寻找到能容纳它的最小空闲区链表，并取下第一块进行分配即可。另外该算法在进行空闲分区分配时，不会对任何分区产生分割，所以能保留大的分区，满足对大空间的需求，也不会产生内存碎片。缺点：在分区归还主存时算法复杂，系统开销较大。此外，该算法在分配空闲分区时是以进程为单位，一个分区只属于一个进程，因此在为进程所分配的一个分区中

25、，或多或少地存在一定的浪费。精选ppt3. 分区分配操作分配内存利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。设请求的分区大小为u.size，表中每个空闲分区的大小表示为m.size，若m.size- u.sizesize(规定的不再切割的分区大小)，将整个分区分配给请求者，否则从分区中按请求的大小划出一块内存空间分配出去，余下部分留在空闲链中，将分配区首址返回给调用者。精选ppt从头开始查表检索完否？m.sizeu.size?m.size-u.sizesize?从该分区中划出u.size大小的分区将该分区分配给请求者修改有关的数据结构返回返回继续检索下一个表项将该分区从链中移出Y

26、YYNNN精选ppt回收内存 当进程运行完毕释放内存时，系统根据回收区首址，在空闲分区链(表)中找到相应插入点，此时可能有四种情况：(1) 回收区与插入点的前一个分区F1邻接(2) 回收区与插入点的后一个分区F2邻接(3) 回收区与插入点的前后两个分区F1、F2邻接(4) 回收区既不与F1邻接，又不与F2邻接精选ppt作业：某操作系统采用可变分区分配存储管理方法，用户区为512K，始址为0，用空闲分区表管理空闲分区。若分配时采用分配空闲区低地址部分的方案，且初始时用户区的512K空间空闲，对下述申请序列：申请300K，申请100K，释放300K，申请150K，申请30K，申请40K，申请60K

27、，释放30K回答以下问题：（1）采用首次适应算法，空闲分区有哪些空块（给出始址、大小）？（2）采用最佳适应算法，空闲分区有哪些空块（给出始址、大小）？（3）如再申请100K，针对（1）和（2）各有什么结果？精选ppt4.3.6 可重定位分区分配1.动态重定位的引入随着系统接收的作业的增加，内存中连续的大块分区将不存在，产生了大量的“碎片”。问题:新的作业无法装入到每个“碎片”小分区上运行，但所有碎片的空间总和可能大于需求。解决方案:通过移动内存中作业的位置，把原来多个分散的小分区“拼接”成一个大分区的方法，称为“拼接”或“紧凑” /“紧缩”/“澄清”。缺点：用户程序在内存中的地址发生变化，必须

28、重定位。精选pptOS区Job2Job4Job3Job1Job5Job6Job7OS区Job2Job4Job3Job1Job5Job6Job7OS区Job2Job4Job3Job1Job5Job6Job7“零头”碎片图4-8 紧凑的示意精选ppt2.动态重定位的实现动态重定位概念: 作业被装入到内存中的相对地址要转换为物理地址，被推迟到程序指令真正要执行的时候进行。精选ppt 地址空间 0 100 Load 1,500 500 Y 1K 存储空间 0 1K1124 Load 1,5001524 Y 2K 512K 有效地址 500重定位寄存器1K处理机一侧存储器一侧实现：（1）必须由硬件地址变

29、换机构重定位寄存器支持：存放程序的起始地址;（2）真正访问的内存物理地址=相对地址+重定位寄存器中地址，当系统对内存进行了“紧凑”，并不需要对程序作修改。精选ppt优点：消除“碎片”，提高了内存利用率，同时提高了系统效率。缺点：（1）需要动态重定位“硬件”机构支持，增加了系统成本；（2）轻度降低了程序执行速度；（3）“紧凑”处理增加了系统开销。精选ppt三、动态重定位分区分配算法请求分配一个大小为xk的分区有大于xk的空闲区吗？空闲区的总和xk吗？紧缩存储并相应地修改诸表(得到一个完整的空闲区xk)分配分区并修改诸表此刻已经无法分配一个分区返回一个分区号数是是否否精选ppt说明：1. 动态重定

30、位分区分配法是利用分区的“拼接”(对空白区而言)或“紧凑”(作业程序而言)技术解决“零头”。2. 问题 拼凑时机的选择 (i)出现相邻空白区即拼接；(或某分区被释放后即紧缩)紧缩工作大，开销大，但管理简单 (ii)存贮不足(空白分区不够大)时进行拼接。紧缩次数少，但管理(算法)较复杂。精选ppt4.3.7对换1. 对换（Swapping）的引入多道程序环境下存在的问题：阻塞进程占据大量内存空间许多作业在外存而不能进入内存运行所谓“对换”，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程和进程所需要的程序和数据，调入内存。精选p

31、pt分类：整体对换(或进程对换)：以整个进程为单位页面对换或分段对换：以页或段为单位实现进程对换，系统必须具备的功能：对换空间的管理进程的换出进程的换入精选ppt2. 对换空间的管理外存存储内容驻留时间主要目标分配方式文件区文件较长久提高文件存储空间的利用率离散对换区从内存换出的进程短暂提高进程换入和换出的速度连续为了能对交换区中的空闲盘块进行管理，在系统中设置相应的数据结构以记录外存的使用情况（空闲分区表或空闲分区链）对换空间的分配与回收，与动态分区方式时的内存分配与回收雷同。精选ppt3、进程的换入和换出 a.进程的换出：条件:创建进程需更多的内存空间时, 或内存空间不够用时;过程:选择阻

32、塞、优先级最低的进程作为换出进程启动盘块将进程的程序和数据传送到磁盘的对换区上。 b.进程的换入：条件:当内存空间稍有空闲时;过程:找出就绪、但已经换出（到磁盘上）的进程将其中换出时间最久的进程将其换出,直至已经无可以换入的进程或或已无法获得足够大的内存来换入进程为止。精选ppt4.4 基本分页存储管理方式 连续分配方式会形成“碎片”，虽然可以通过“紧凑”解决，但开销大。如果允许将一个进程直接分散地装入许多不相邻的分区中，则无需“紧凑”，由此产生离散分配方式。 分类：分页存储管理方式：离散分配的基本单位是页 （1）基本分页（纯分页）管理：不具备页面置换功能；不具备支持实现虚拟存储器的功能；要求

33、把每个作业全部装入内存后才能运行。 （2）支持虚存管理的请求分页管理。分段存储管理方式：离散分配的基本单位是段精选ppt4.4.1 页面与页表1. 页面页面和物理块分页存储管理是将一个进程的逻辑地址空间分成若干个大小相等的片称为页面或页，并为各页加以编号，从0开始。同时把内存空间分成与页面相同大小的若干个存储块，称为（物理）块或页框。顺序编号（也从0开始）。精选ppt01234567891110内存第0页第1页第2页第3页第4页第5页第6页用户作业02K-1第2页（页长2K）02K-14号页框（页长2K）精选ppt在为进程分配内存时，以块为单位将进程的若干个页分别装入到多个可以不相邻的物理块中

34、。例如：一个作业的地址空间有m页。那么，只要分配给它m个页框，每一页分别装入一个页框内即可。这里，并不要求这些页框是连续的。说明：（1）在进程调度时，必须把它的所有页一次装入到主存的页框内；如果当时页框数不足，则该进程必须等待，系统再调度另外的进程。（纯分页方式）（2）进程的最后一页经常装不满而形成“页内碎片”。即存在内零头。精选ppt.0块1块2块3块4块5块6块0页1页2页3页4页作业的地址空间页框（物理块）内存精选ppt二、页面大小在分页系统中对页面的大小应选择得适当。因为：若选择的页面较小，一方面可使内存碎片小，并减少了内存碎片的总空间，有利于提高内存利用率；但另一方面，也会使每个进程

35、要求较多的页面，从而导致页表过长，占用大量内存；还会降低页面换进换出的效率。若选择的页面较大，虽然可减少页表长度，提高换进换出效率，但又会使页内碎片增大。页面的大小通常在512B8KB选择，但总是2的幂。精选ppt2.地址结构 逻辑地址n-1 k k-1 0页号P位移量W线性的逻辑地址长度为n位, 包括两部分：页号P：n-k位,即:地址空间最多允许有2n-k页；位移量W（页内位移量，即页内地址）：k位,页内地址大小=2kB 若给定一个逻辑地址空间中的地址为A，页面大小为L，则可以由公式求出： 页号P=INTA/L，页内地址d=A mod L 例如：系统的页面大小L为1KB，A=2170B， 求

36、出P=2,d=122 精选ppt逻辑地址31 12 11 0位移量W 页号P 页号P：1231共20位 地址空间最多允许有220=1M页，即每个进程占用1M个页。位移量W：011共12位 页内地址大小（即每页的大小）为212B=4KB。 例：现代的大多数计算机系统的逻辑地址空间都支持很大的逻辑地址空间（232264）B，如下逻辑地址长度为32位，包括两部分：精选ppt(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位

37、移量为(1101)8, 页号为(167)8精选ppt3.页表 在分页系统中，存储分配问题变得非常简单，作业的一页可以分配到存储空间中任何一个可用的页框。 问题： (1)系统怎么知道作业的哪一页分配在存储空间的哪一页框内？ (2)如何实现以及何时实现把作业的逻辑地址变换为主存的物理地址。 精选ppt页表： 系统为每一个进程建立的，在内存中找到每个页面所对应的物理块号的一张页面映像表。 一个进程占用多少页，就在页表中有多少页表项。 页表的作用：实现从页号到物理块号的地址映射。数据结构： 页号、块号、存取控制字段（控制存储块中的内容是允许读/写、只读、只执行）。根据每页内容的不同，可以设置不同的存取

38、限制。所以，在页表的表目中除了包含指向所在页框的指针外，还包括一个存取控制字段，这个表目也称为页描述子。精选ppt01234567891110内存第0页第1页第2页第3页第4页第5页第6页用户作业块号页号1051169453327120页表第0页第1页第2页第3页第4页第5页第6页图4-12页表的作用精选ppt4.4.2 地址变换机构地址映射从逻辑地址到物理地址的变换过程。将用户地址空间中的逻辑地址变换为内存空间中的物理地址，系统设置了地址变换机构。 由于页内地址和物理地址一一对应，所以地址变换机构只是将逻辑地址中的页号，转换为内存中的物理地址的物理块号。借助页表完成。逻辑地址 物理地址物理块

39、号P页内地址d页号P位移量W精选ppt1.基本的地址变换机构在实际系统中，为了减少硬件成本，将页表存放在被保护的系统区内的一个连续空间中。这张页表是在进程装入主存时，由系统根据内存分配情况建立的。精选ppt分页地址变换机构变换过程：（1）进程执行之前：PCB（内存中的页表始址+页表长度）（2）进程调度后：页表寄存器PTR （内存中的页表始址+页表长度）（3）检索页表： 条件：页表长度逻辑地址中的页号不成立：所访问的地址越界，产生一地址越界中断；成立：未地址越界，则：由“页表始址+页号x页表项长度”找到该页号在页表中的位置。精选ppt图4-13 分页系统的地址变换机构页表始址页表长度页表寄存器页

40、表块号页号5332712052018物理地址页号（3）页内地址2018逻辑地址越界中断精选ppt关于分页的地址变换计算 页式地址映射设页面大小为2KB精选ppt例1：某采用分页存储管理的系统中，物理地址占20位，逻辑地址中页号占6位，页面大小为1KB，问： 该系统的内存空间大小为多少？每个存储块的大小为多少？逻辑地址共几位？每个作业的最大长度为多少？ 若第0、1、2页分别放在第3、7、9存储块中，则逻辑地址0420H对应的物理地址是多少？精选ppt 解： 物理地址占20位，所以该系统的内存空间大小为：220=1MB 存储块的大小与页面大小相同，而页面大小为1KB，因此存储块的大小为：1KB 由

41、于页面大小为1KB，占10位，而页号占6位，因此逻辑地址共16位。 逻辑地址共16位，从而该系统中的每个作业大小为：216=64KB精选ppt 逻辑地址到物理地址转换的计算方法 ： 分页系统中基本的地址变换：有两种方式，一种是十进制计算方法，另一种是二进制计算方法。 十进制计算方法：设页号为P、页内位移为W、逻辑地址为A、物理地址为M、页面大小为L。 第一步，根据公式计算页号和位移量: 页号：P=int(A/L)，位移量：W=A mod L 第二步，查找页表，确定第一步中计算得到的页号所对应的块号。 第三步，计算物理地址，M=块号*L+W精选ppt十进制计算方法第一步： 将逻辑地址转换成10进

42、制：0420H=1056 页号：P=int(A/L)=int（1056/1024）=1 位移量：W=A mod L=1056 mod 1024=32 第二步： 查页表，1号页面对应7号物理块，每个物理块大小为1K。第三步： 物理地址为：71K+32=7200。 精选ppt 逻辑地址到物理地址转换的计算方法 ：二进制计算方法： 第一步，将逻辑地址以二进制形式表示。 第二步，根据页面大小，计算位移量所占二进制位数，并将逻辑地址划分为页号和页内位移量两部分。 第三步，把第二步中划分得到的页号部分转换为十进制，查找页表，确定所对应的块号。 第四步，将第三步中得到的块号转换为二进制，并与第二步中划分得到

43、的页内位移量拼接（页内位移量作为低地址部分），至此物理地址计算完毕。也可以将物理地址转换为十六进制表示方式。 说明：一定要能够根据页面大小确定位移量所占二进制位数。常见页面大小为1K、2K、4K和8K，所需二进制位数依次为10、11、12和13。精选ppt二进制计算方法：第一步，将逻辑地址转换为二进制： 0420H=0000 0100 0010 0000第二步，页面大小为1K，所以位移量占10个二进制位，将逻辑地址划分为页号和页内位移量两部分： 0000 0100 0010 0000第三步，把页号部分转换为十进制，查找页表，确定所对应的块号： (0000 01)2=1，1号页对应7号物理块。第

44、四步，将第三步中得到的块号转换为二进制，并与第二步中划分得到的页内位移量拼接，即得物理地址: 0001 1100 0010 0000 也可以转换为十六进制：1C20H。精选ppt练习：在分页存储系统中地址结构的长度为20位，页面大小为2K，作业地址空间为8K，该作业各页依次存放在1，3，6，7号物理块中，相对地址4000处有一条指令 Store l，2500，请给出该作业的页表，并分别指出该指令所在页号和对应的物理单元及数据存放所在的页号和物理单元。 精选ppt 由题意，页面大小为2K，该作业的地址空间为8K，因此该作业有4页，其页表为： 01132637计算相对地址4000的物理地址 页号：

45、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=6596精选ppt作业1：某虚拟存储器的用户空间共有32个页面，每页1KB，主存16KB。试问：（1）逻辑地址的有效位是多少？（2）物理地址需要多少位？（3）假定某时刻系统用户的第0，1，2，3页分别分配的物理块号为5，10，4，7，试将虚地

46、址0A5C和093C变换为物理地址。作业2：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、10、5块，试将虚地址7145，3412转换成内存地址。精选ppt提出改进的原因： 计算机CPU存取数据需要访问内存两次，处理速度降低为1/2。改进方法： 利用联想寄存器（快表）并行查询； 空间大小： 几K到几百K ，存放16512个页表项；2.具有快表的地址变换机构精选ppt实现原理： 快表与页表同时访问：（1）在快表中找到相匹配的页号 直接从快表中读出对应物理块号；（2）在快表中没有找到相匹配的页号 还须找页表，再从页表中对出物理块号； 再将此页表项存入快表中

47、，重新更新快表。优点：加快了地址变换的速度。精选ppt页表始址页表长度页表寄存器页表块号页号5332712051250物理地址页号（3）页内地址（1250）逻辑地址越界中断快表块号页号2051145320输入寄存器图4-14 具有快表的地址变换机构精选ppt 当调度合理时，命中率可以达到90以上。考虑到快表的速度是内存速度的数倍或数十倍，那么相对于内存速度，访问页表的时间可以忽略不计。也就是说页地址变换不会造成进程运行速度下降多少。精选ppt例：设访问主存时间为200ns,访问联想存贮器为40ns，命中率为90，则平均存取时间为多少？查页表两次访存：平均为200200400ns查快表，平均为：

48、 (200+40)90(200+200+40)10260ns解：方法1：方法2：精选ppt4.3.3 两级和多级页表 现代计算机系统都支持非常大的逻辑地址空间(232264)，页表就非常大，需占用较大的地址空间。例如：一个具有32位逻辑地址空间的分页系统，规定页面大小为4KB即212B，则每个进程页表的页表项可达1M个，若每个页表项占用一个字节，则每个进程的页表就要占据1MB的内存空间，而且要求连续存放。解决方法：采用离散方式只将当前所需页表项调入内存精选ppt1. 两级页表 将页表分页，并离散地将各个页面分别存放在不同的物理块中，同时为离散分配的页表再建立一张页表，称为外层页表，其每个页表项

49、记录了页表页面的物理块号。精选ppt例如： 32位逻辑地址空间，页面大小为4KB(即12位)，每个页表项占4个字节，若采用一级页表机构，应有20位页号，即页表项应有1M个；在采用两级页表机构时，再对页表进行分页，使每页包含210(即1024)个页表项，最多允许有210个页表分页。即页内地址外层页内地址外层页号dp2p1 31 22 21 12 11 0 精选ppt012345671141151468内存空间641第0页页表0121023115114第1页页表01210231468第n页页表0121023174210781011012n外部页表两级分页结构页表页目录表精选ppt外部页表外层页表始

50、址d物理地址外部页号P1外部页内地址P2逻辑地址页内地址db页表图4-16 具有两级页表的地址变换机构外部页表寄存器（包含页表分页始址）（包含该页中的物理块号b） 精选ppt 上述方法用离散分配空间解决了大页表无需大片存储空间的问题，但并未减少页表所占的内存空间。 解决方法是把当前需要的一批页表项调入内存，以后再根据需要陆续调入。精选ppt2. 多级页表两级页表对32位机器适用，64位呢？页面大小为4KB即212B，还剩52位，按物理块大小212B来划分页表，则剩余42位用于外层页号，此时外层页表可能有4096G个页表项，要占用16384GB的连续存储空间解决方法：采用多级页表，将外层页表再进

51、行分页。将各个分页离散地装入到不相邻接的物理块中，再利用第2级的外层来映射它们之间的关系。逻辑地址映射到物理地址的方法和二级页表相同。精选ppt 练习：某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为210字节，页表项大小为2字节，逻辑地址结构为： ，逻辑地址空间大小为216页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是（ ）。【联考 2010】 A.64 B.128 C.256 D.512 【分析】本题目关键是确定页目录号占用多少位。已知页大小为210字节，页表项大小为2字节，因此，每页可以包含29个页表项，即页号部分占用9位；又已知逻辑地址空间大小为216页，即页目

52、录号和页号总共占用16位，因此，页目录号占用7位，所以应该选择B。精选ppt例：一个由四个页面（页号为03），每页由1024个字节组成的程序，把它装入由8个物理块（块号为07）组成的存储器中，装入情况如下表所示。已知下面的逻辑地址（其中方括号中的第一个元素为页号，第二个元素为页内地址），请按页表求出对应的物理地址。（1）0，100； （2）1，179； （3）2，785；逻辑页号内存块号03152632解答：因为每页有1024B，所以内存中每块也有1024B。物理地址 块号块长 + 页内地址，得到：（1）的物理地址为：31024+100=3072+100=3172 （2）的物理地址为：5102

53、4+179=5120+179=5299（3）的物理地址为：61024+785=6144+785=6929 精选ppt作业：已知某系统页面长4KB，每个页表项为4B，采用多层分页策略映射64位的用户地址空间。若限定最高层页表只占1页，则它可采用几层分页策略？精选ppt4.5 基本分段存储管理方式提出分段管理的目的除了可以提高内存空间的利用率外，主要是为了更好地实现程序的共享和动态链接，并方便用户编程。页式管理是把内存视为一维线性空间；而段式管理是把内存视为二维空间，与进程逻辑相一致。精选ppt4.5.1 分段存储管理方式的引入 主要是为了满足用户的下述一系列要求：1.方便编程。一个段可定义为一组

54、逻辑信息，如子程序，数组或工作区，(分段是程序中自然划分的一组逻辑意义完整的信息集合，它是用户在编程时决定的)。因此，每个作业的地址空间是由一些分段构成的，每段都有自己的名字，且都是一段连续的地址空间。可见，整个作业的地址空间是二维的。CALL X|LOAD 1,A|STORE 1,B|分段MAIN(主程序) 01KY：分段X(子程序) 0640D：分段A (数组) 0500C：分段B(工作区) 0300精选ppt2.信息共享。一般实现程序和数据共享时都是以信息的逻辑单位为基础的。在分页系统中的每一页都只是存放信息的物理单位，其本身并无完整意义，因而不便于实现信息共享，而段却是信息的逻辑单位，

55、通常是可以表达某种意义的，采用分段存储管理，更便于实现程序和数据的共享。3.信息保护。对内存中的信息的保护，同样也是对信息的逻辑单位进行保护。采用分段存储管理，对实现信息保护，将是更有效和方便。 4.动态增长。在实际使用中，往往有些段，特别是数据段会随着程序的运行不断增大，而这种增长事先并不知晓会增长到多大，采用其它存储管理方式是难以应付的，而分段存储管理却能较好的解决这一问题。5.动态链接。前面已谈到，采用动态链接能更有效提高存储空间的利用率。由于每个程序模块构成独立的分段，并有自己的段名，因而实现动态链接是比较容易的。 精选ppt4.5.2 分段系统的基本原理 1、分段 在分段管理系统中，

56、对所有地址空间的访问均要求两个成分： (1)段的名字； (2)段内地址。例如，可按下述调用：CALL X| 转移到子程序X中的入口点YLOAD 1, A| 将数组A的D单元的值读入寄存器1STORE 1,B| 将寄存器1的内容存入分段B的C单元中这些符号程序经汇编和装配后，指令和数据的单元地址均由两部分构成：一是表示段名的段号S；一是位移量W，即段内地址。所以，在分段系统中的地址结构有如下形式：段号S 位移量W 逻辑地址23 1615 0精选ppt 一旦段号字段和位移量字段的长度确定后，一个作业地址空间中允许的最多段数及段的长度也就限定了。上述地址结构表明，该系统可允许一个作业有256段，最大

57、段长为64K字节。段号S 位移量W 逻辑地址23 1615 0精选ppt所谓分段管理，就是管理由若干分段组成的作业，且按分段来进行存储分配。实现分段管理的关键在于，如何保证分段(二维)地址空间中的一个作业在线性(一维)的存储空间中正确运行。分段式存储管理的实现是基于动态分区存储管理的原理。系统为每个分段分配一个连续的分区，而进程中的各个段可以离散地移入内存中不同的分区中。基本分段存储管理方式中，进程运行时，其各段必须全部装入内存。精选ppt2. 段表 为使程序正常运行，须在系统中为每个进程建立一张段映射表，简称“段表”。每个段在表中占有一个表项，其中记录了该段在内存中的起始地址(段基址)和段的

58、长度。 段表可以存放在寄存器中，但更多的是存放在内存中。 段表可以实现从逻辑地址到内存物理地址的映射。段号012段首址段长度58K20K100K110K260K140K精选ppt作业空间(MAIN)=0030K(X)=1020K(D)=2015K(S)=3010K150K10K120K15K80K20K40K30K0123段号段长基址段表(S)=310K(D)=215K(X)=120K(MAIN)=030K内存空间040K80K120K150K利用段表实现地址映射:精选ppt3. 地址变换机构 在系统中设置段表寄存器，用于存放段表始址和段表长度，以实现从进程的逻辑地址到物理地址的变换。 段表寄

59、存器和段表还有存储保护的功能精选ppt段表长度段表始址段表寄存器物理地址+越界中断分段系统的地址变换机构1002段号S位移量W段表92002008K5004K6006K1K段长基址段号0123+82928K82928692主存精选ppt 问题：当段表存放在内存中时，每访问一个数据，都需两次访问内存，降低了计算机的速率。 解决方法：设置联想寄存器（快表），用于保存最近常用的段表项。这样,比起没有地址变换的常规存储器的存取速度来仅慢约10%15%.精选ppt Cl Cb+段号S 段内地址d比较比较b + d段表S= Cl快表物理地址段表始址寄存器段表长度寄存器逻辑地址lb.Slb地址越界d=1d=

60、1地址映射地址越界地址越界比较精选ppt4. 分页和分段的主要区别相似点：采用离散分配方式，通过地址映射机构实现地址变换不同点：页是信息的物理单位，分页是为了满足系统的需要,提高内存利用率；段是信息的逻辑单位，含有一组意义相对完整的信息，分段是为了满足用户的需要。页的大小固定且由系统确定，由系统把逻辑地址分为页号和页内地址，由机器硬件实现；段的长度不固定，取决于用户程序，编译程序对源程序编译时根据信息的性质划分。分页的作业地址空间是一维的；分段的作业地址空间是二维的。精选ppt4.5.3 信息共享 分段系统的一个突出优点是易于实现段的共享，允许若干个进程共享一个或多个分段，且对段的保护十分简单