《存储器管理》课件.ppt

1、1,第四章存储器管理,4.1 存储器的层次结构 4.2程序的装入和链接 4.3连续分配方式 4.4基本分页存储管理方式 4.5基本分段存储管理方式 4.6虚拟存储器的基本概念 4.7请求分页存储管理方式 4.8页面置换算法 4.9请求分段存储管理方式,2,4.1 存储器的层次结构,4.1.1 多级存储器结构 1. 存储器功能 合理、安全、有效地保存数据 2. 存储器发展方向 接口更新 以硬盘为例：ESDI ; IDE/EIDE ; ATA ; SATA/SATA2 ; SCSI ; IEEE1394 ; USB 高速性 以USB为例：USB1.1是12Mbps，USB2.0是480Mbps，U

2、SB3.0理论上是5Gbps 存储密度越来越高，体积越来越小 1.7Mb/平方英寸；20Mb/平方英寸；1.43Gb/平方英寸； 135Gb/平方英寸；620Gb/平方英寸；1Tb/平方英寸,3,4,容量越来越大，价格越来越低 以下是近年来关于硬盘价格的趣味数字 1995年 200MB400MB 大于4000元/GB 1996年 1.2GB2.1GB 1500元2000/GB 1998年 1.2GB2.1GB 200元250元/GB 2000年 4.3GB6.4GB 40元/GB 2002年 10GB20GB 20元/GB 2004年 40GB80GB 6.9元/GB 2005年 80GB16

3、0GB 4.5元/GB 2006年 80GB250GB 3.8元/GB 2008年 160GB1TB 1.6元/GB 2009年 500GB2TB 0.8元/GB 2010年 500GB2TB 0.6元/GB,5,3. 存储器层次结构,6,4. 存储管理功能 存储分配与回收 本章主要内容，讨论其算法和数据结构 地址变换 可执行文件生成中的链接技术；程序装入时的重定位技术；进程运行时的地址变换技术和机构(软件、硬件) 存储共享和保护 代码和数据共享；对地址空间的访问权限(读、写、执行) 存储器扩充 由用户应用程序控制：覆盖Overlay 由OS控制：交换Swapping；请求调入和预调入On D

4、emand & On Prefetch,7,4.1.2 主存储器与寄存器 1主存储器 主存储器(简称内存或主存)是计算机系统中一个主要部件，用于保存进程运行时的程序和数据，也称可执行存储器，材质以DRAM为主。由于主存储器的访问速度远低于CPU执行指令的速度，为缓和这一矛盾，在计算机系统中引入了寄存器和高速缓存。,8,2寄存器 寄存器访问速度最快，完全能与CPU协调工作，但价格却十分昂贵，因此容量不可能做得很大。寄存器的长度一般以字(word)为单位。寄存器的数目，对于当前的微机系统和大中型机，可能有几十个甚至上百个；而嵌入式计算机系统一般仅有几个到几十个。 寄存器通常用于加速存储器的访问速度

5、，如用寄存器存放操作数，或用作地址寄存器加快地址转换速度等。,9,4.1.3 高速缓存和磁盘缓存 1高速缓存 高速缓存是现代计算机结构中的一个重要部件，其容量大于或远大于寄存器，而比内存约小两到三个数量级左右，从几十KB到几MB，访问速度快于主存储器。 根据程序执行的局部性原理(即程序在执行时将呈现出局部性规律，在一较短的时间内，程序的执行仅局限于某个部分)，将主存中一些经常访问的信息存放在高速缓存中，减少访问主存储器的次数，可大幅度提高程序执行速度。,10,2磁盘缓存 由于目前磁盘的I/O速度远低于对主存的访问速度，因此将频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，可减少访问磁盘的

6、次数。,11,4.2程序的装入和链接,在多道程序环境下，要使程序运行，必须先为之创建进程。而创建进程的第一件事，便是将程序和数据装入内存。如何将一个用户源程序变为一个可在内存中执行的程序，通常都要经过以下几个步骤：首先是要编译，由编译程序(Compiler)将用户源代码编译成若干个目标模块(Object Module)；其次是链接，由链接程序(Linker)将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成一个完整的装入模块(Load Module)；最后是装入，由装入程序(Loader)将装入模块装入内存。图4-2示出了这样的三步过程。本节将扼要阐述程序(含数据)的链接和装入

7、过程。,12,图4-2对用户程序的处理步骤,编译 Compile,若干 目标 模块 .OBJ,源 程 序 .C,链接 Link,库函数 Lib,装入 模块 .EXE,装入 Load,CPU,13,4.2.1程序的链接 链接：若干目标模块 + 库函数 可装入模块 根据链接时间的不同，可把链接分成如下三种： (1) 静态链接。在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装配模块，以后不再拆开。我们把这种事先进行链接的方式称为静态链接方式。 (2) 装入时动态链接。这是指将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的链接方式。 (3) 运行时动态链接。

8、这是指对某些目标模块的链接，是在程序执行中需要该(目标)模块时，才对它进行的链接。,14,1静态链接方式(Static Linking) 在生成可装入模块时(也就是在程序装入运行前)完成的链接。见图4-4 特点： 一次链接，n次运行 得到完整的可装入模块，不可再拆 不灵活：不管有用与否的模块都将链接到装入模块，同时导致内存利用率较低 不利于模块的修改和升级,15,16,2装入时动态链接(Load-time Dynamic Linking) 用户源程序经编译后所得的目标模块，是在装入内存时边装入边链接的，即在装入一个目标模块时，若发生一个外部模块调用事件，将引起装入程序去找出相应的外部目标模块，

9、并将它装入内存，还要按照图4-4所示的方式来修改目标模块中的相对地址。,17,3运行时动态链接(Run-time Dynamic Linking) 装入时动态链接是将所有可能要运行到的模块都全部链接在一起并装入内存，显然这是低效的，因为往往会有些目标模块根本就不运行。比较典型的例子是作为错误处理用的目标模块，如果程序在整个运行过程中都不出现错误，则显然就不会用到该模块。 运行时动态链接方式是对装入时链接方式的一种改进。这种链接方式是将对某些模块的链接推迟到程序执行时才进行链接，亦即，在程序执行过程中，当发现一个被调用模块尚未装入内存时，才立即由OS去找到该模块并将之装入内存，把它链接到调用者模

10、块上。凡在本次执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。,18,4动态链接方式的优点 便于共享 多个进程可共用一个DLL模块，节省了内存。 为部分装入提供了条件(运行时动态链接) 一个进程可由若干DLL模块构成，按需装入。 便于模块的修改和升级 只要被修改模块的接口不变，则该模块的修改不会引发其它模块的重新编译。 改善了程序的可移植性 可面向不同的应用环境开发同一功能模块的不同版本，根据当前的环境载入匹配的模块版本。,19,5动态链接方式的缺点 增加了程序执行时的链接开销。(每次运行都需链接) 模块数量众多，增加

11、了模块的管理开销。,20,4.2.2程序的装入 装入：可装入模块(.EXE) 内存进程 1绝对装入方式(Absolute Loading Mode) 在编译后、装入前已产生了绝对地址（内存地址），装入时不再作地址重定位，即：装入内存前的虚拟地址 = 装入内存后的物理地址。 绝对地址的产生：（1）由编译器完成；（2）由程序员编程完成。 优点：装入过程简单，无需地址映射。 缺点：不适于多道程序系统；过于依赖硬件结构；不易修改、不灵活。,21,2可重定位装入方式(Relocation Loading Mode) 可装入模块在被装入到内存中时，由装入程序来完成程序虚拟地址 内存物理地址的变换,22,如

12、果不进行地址变换，那么这条指令将无法取到正确的数值“365”，所以该指令中的地址应该重定位为： LOAD 1 , 12500,静态地址重定位： 指令或数据的内存地址MA = 该指令或数据的虚拟地址VA + 该程序在内存中的首地址BA,23,可重定位装入的优缺点： 优点： 适用于多道程序系统，提高了内存利用率；由于地址映射规则简单，故在地址变换过程中无需硬件变换机构的支持。 缺点： 任何进程都要求连续的内存空间；必须将全部模块都装入且装入后不能再移动位置(因为无法实现动态重定位)；不支持虚拟存储器技术；不易实现共享。,24,3动态运行时装入方式(Dynamic Run-time Loading)

13、 出于实际情况，程序在运行过程中的内存位置可能经常要改变，此时就应采用动态运行时装入的方式。 程序装入内存后并不立即进行地址变换，而是等到真正要执行时才由硬件地址变换机构来完成地址变换，从而得到内存物理地址。,25,动态地址重定位： 指令或数据的内存地址MA = 该指令或数据的虚拟地址VA + 重定位基址寄存器BR,26,动态运行时装入的优缺点： 优点 OS可将一个进程的不同部分分散存放在不连续的内存空间；可移动进程在内存中的位置(由重定位基址寄存器反映移动情况)；提供了实现虚拟存储器技术的基础(可实现部分模块装入)；有利于实现模块共享。 缺点 动态重定位需要硬件变换机构的支持；实现较复杂。,

14、27,4.3连续分配方式,连续分配方式是指一个进程在内存中必须占用连续的存储空间。典型的连续分配方式主要有：单一连续分配、固定分区分配、动态分区分配、动态重定位分区分配等。 4.3.1单一连续分配 把内存分为系统区和用户区两部分，系统区仅提供给OS使用；用户区是指除系统区以外的全部内存空间，提供给用户使用。 优点：简单，易于管理 缺点：只能用于单用户单任务OS；内存利用率低，毫无共享性可言。早已淘汰。,28,引入：分区存储管理原理 将内存分为一些大小相等或不等的分区(Partition)，每个进程可占用一个分区。 适于多道程序系统，支持多个进程并发执行。 出现了碎片问题 内碎片：被占用分区的尾

15、部未被利用的空间。 外碎片：在两个被占用分区之间的难以利用的小空闲分区。 分区管理的数据结构：分区表或分区链表。 内存紧凑(Compaction)：将各个已占用分区向内存某端移动,从而使分散的各个小空闲分区能相邻,进而合并为一个稍大的空闲分区。,29,4.3.2固定分区分配 1把内存划分为若干个固定大小的分区，分区的总数以及各个分区的大小都是恒定值。 各分区大小相等 不灵活；对于小进程而言，内存利用率低，内碎片严重；对于大进程而言，分区大小可能无法满足需要，导致无法装入。 各分区大小不等 小分区、中等分区、大分区。适应性较强，可以有效提高内存利用率。,30,2固定分区的内存分配 为了便于内存分

16、配，通常将分区按大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态(是否已分配)，见图4-5(a)所示。 当有一用户程序要装入时，由内存分配程序检索该表，从中找出一个能满足要求的、尚未分配的分区，将之分配给该程序，然后将该表项中的状态置为“已分配”；若未找到大小足够的分区，则拒绝为该用户程序分配内存。存储空间分配情况如图4-5(b)所示。,31,32,3固定分区分配的优缺点 优点 由于各分区大小固定，故易于实现，管理开销小。 缺点 内碎片的问题不可避免，较大程序不易装入，故内存利用率较低；分区数目固定也限制了进程的并发度。,33,4.3.3动态分区分配 在动态

17、分区分配方式中，各个分区的大小会在OS的管理下发生改变，分区总数也会相应地发生变化。 1分区分配中的数据结构 (1) 空闲分区表：记录所有空闲分区情况的二维表,34,(2) 空闲分区链：将所有的空闲分区链接成一个双向链，如图4-6所示。,图4-6空闲链结构,35,2分区分配算法 1) 首次适应FF算法(First Fit) 空闲分区链以地址递增的次序链接。在每次分配时，都从链首开始顺序查找，直至找到第一个大小能满足要求的空闲分区为止；然后再按照程序的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则此次内存分配失败，返

18、回。 特点：简单；高址内存可保留较大的空闲分区；但低址内存会产生很多碎片分区；查找开销大。,36,2) 循环首次适应NF算法(Next Fit) 该算法是由首次适应FF算法演变而成的：分配空间不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，如果达到链尾则回到链首继续。 特点：查找开销小；空闲分区分布更均匀；但较大分区难以保留。,37,3) 最佳适应BF算法(Best Fit) 空闲分区链表以容量递增为序组织，每次分配时从链首查找，将第一个满足空间要求的分区分配出去。 特点：最接近按需分配原则；较大的分区容易保留；但会产生很多难以利用的小碎片分区。 4) 最坏适应W

19、F算法(Worst Fit) 空闲分区链表以容量递减为序组织，每次分配时从链首查找，将第一个满足空间要求的分区分配出去。 特点：小碎片分区的问题得到了有效的解决；但大分区也不易保留。 最坏适应算法与前面所述的首次适应、循环首次适应、最佳适应算法一起，统称为顺序搜索法。,38,5) 快速适应QF算法(Quick Fit) 该算法又称为分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，这样，系统中存在多个空闲分区链表，同时在内存中设立一张管理索引表，该表的每一个表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。空闲分区的

20、分类是根据进程常用的空间大小进行划分。 优点：查找效率高；不会对任何分区产生分割，所以能保留大的分区；也不会产生内存碎片。 缺点：分区归还主存的算法复杂，系统开销较大；多样化的链表造成管理开销大。,39,3分区分配操作 1) 分配内存 系统应利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。设请求的分区大小为u.size，表中每个空闲分区的大小可表示为m.size。若m.size-u.sizesize(size是事先规定的不再切割的剩余分区的大小)，说明多余部分太小，可不再切割，将整个分区分配给请求者；否则(即多余部分超过size)，从该分区中按请求的大小划分出一块内存空间分配出去，余

21、下的部分仍留在空闲分区链(表)中。然后，将分配区的首址返回给调用者。图4-7示出了分配流程。,40,41,2) 回收内存 (1) 回收区与插入点的前一个空闲分区F1相邻接，见图4-8(a)。此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区F1的大小。 (2) 回收分区与插入点的后一空闲分区F2相邻接，见图4-8(b)。此时也可将两分区合并，也不必分配新表项，用回收区的首址作为新空闲区的首址，大小为两者之和。 (3) 回收区同时与插入点的前、后两个分区邻接，见图4-8(c)。此时将三个分区合并，使用F1的表项，F1的首址不变，F1的大小为三者之和，删除F2的表

22、项。 (4) 回收区既不与F1邻接，又不与F2邻接，见图4-8(d)。这时应为回收区单独建立一新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。,42,合并， 改F1大小,合并， 改F1大小和首址,合并， 改F1大小，删除F2表项,建立一新表项,43,例：假设最佳适应法,如果改为首次适应算法？,44,4.3.4伙伴系统(自学内容) 固定分区和动态分区方式都有不足之处。固定分区方式限制了活动进程的数目，当进程大小与空闲分区大小不匹配时，内存空间利用率很低。动态分区方式算法复杂，回收空闲分区时需要进行分区合并等，系统开销较大。伙伴系统方式是对以上两种内存方式的一种折衷方案。 伙

23、伴系统规定，无论已分配分区或空闲分区，其大小均为2的k次幂，k为整数，lkm，其中：21表示分配的最小分区的大小，2m表示分配的最大分区的大小，通常2m是整个可分配内存的大小。,45,假设系统的可利用空间容量为2m个字，则系统开始运行时，整个内存区是一个大小为2m的空闲分区。在系统运行过程中，由于不断的划分，可能会形成若干个不连续的空闲分区，将这些空闲分区根据分区的大小进行分类，对于每一类具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表。这样，不同大小的空闲分区形成了k(0km)个空闲分区链表。,46,当需要为进程分配一个长度为n的存储空间时，首先计算一个i值，使2i-1n2i，然后在

24、空闲分区大小为2i的空闲分区链表中查找。若找到，即把该空闲分区分配给进程。否则，表明长度为2i的空闲分区已经耗尽，则在分区大小为2i+1的空闲分区链表中寻找。若存在2i+1的一个空闲分区，则把该空闲分区分为相等的两个分区，这两个分区称为一对伙伴，其中的一个分区用于分配，而把另一个加入分区大小为2i的空闲分区链表中。若大小为2i+1的空闲分区也不存在，则需要查找大小为2i+2的空闲分区，若找到则对其进行两次分割：第一次，将其分割为大小为2i+1的两个分区，一个用于分配，一个加入到大小为2i+1的空闲分区链表中；第二次，将第一次用于分配的空闲区分割为2i的两个分区，一个用于分配，一个加入到大小为2

25、i的空闲分区链表中。若仍然找不到，则继续查找大小为2i+3的空闲分区，以此类推。由此可见，在最坏的情况下，可能需要对2k的空闲分区进行k次分割才能得到所需分区。,47,与一次分配可能要进行多次分割一样，一次回收也可能要进行多次合并，如回收大小为2i的空闲分区时，若事先已存在2i的空闲分区时，则应将其与伙伴分区合并为大小为2i+1的空闲分区，若事先已存在2i+1的空闲分区时，又应继续与其伙伴分区合并为大小为2i+2的空闲分区，依此类推。 在伙伴系统中，其分配和回收的时间性能取决于查找空闲分区的位置和分割、合并空闲分区所花费的时间。与前面所述的多种方法相比较，由于该算法在回收空闲分区时，需要对空闲

26、分区进行合并，所以其时间性能比前面所述的分类搜索算法差，但比顺序搜索算法好，而其空间性能则远优于前面所述的分类搜索法，比顺序搜索法略差。,48,4.3.5 哈希算法 哈希算法就是利用哈希快速查找的优点，以及空闲分区在可利用空间表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，该表的每一个表项记录了一个对应的空闲分区链表表头指针。 当进行空闲分区分配时，根据所需空闲分区大小，通过哈希函数计算，即得到在哈希表中的位置，从中得到相应的空闲分区链表，实现最佳分配策略。,49,4.3.6可重定位分区分配 1动态重定位的引入 在连续分配方式中，必须把一个系统或用户程序装入一连续的内存空

27、间。如果在系统中只有若干个小的分区，即使它们容量的总和大于要装入的程序，但由于这些分区不相邻接，也无法把该程序装入内存。例如，图4-9(a)中示出了在内存中现有四个互不邻接的小分区，它们的容量分别为10 KB、30 KB、14 KB和26 KB，其总容量是80 KB。但如果现在有一程序到达，要求获得40 KB的内存空间，由于必须为它分配一连续空间，故此程序无法装入。这种不能被利用的小分区称为“零头”或“碎片”。,50,图4- 9 紧凑的示意,现在有4个空闲分区，如果有一个大小为40KB的程序要求进入内存，如何处理？,解决办法：紧凑,紧凑：通过移动一些内存分区，将原本离散的一些内存小碎片变得相邻

28、，进而可以合并为一个稍大的空闲分区的技术。,51,2动态重定位的实现 经过紧凑后，某些用户程序在内存中的位置发生了变化，此时若不对程序和数据的地址加以修改(变换)，则程序必将无法执行。为此，在每次“紧凑”后，都必须对移动了的程序或数据进行地址重定位。 增设“重定位寄存器”，每当系统对内存进行了“紧凑”而使若干程序从内存的某处移至另一处时，不需对程序做任何修改，只要实时更新“重定位寄存器”的值即可。,52,动态地址重定位： 指令或数据的内存地址MA = 该指令或数据的虚拟地址VA + 重定位基址寄存器BR,53,3动态重定位分区分配算法 动态重定位分区分配算法与动态分区分配算法基本上相同，差别仅

29、在于：在这种分配算法中，增加了紧凑的功能，通常，在找不到足够大的空闲分区来满足用户需求时进行紧凑。图4-11示出了动态重定位分区分配算法。,54,55,4.3.7有关分区管理的讨论 1. 分区存储管理的特点 优点：实现了多个进程对内存的共享，有助于多道程序系统；提高了资源利用率；要求的硬件支持少；管理简单，实现容易。 缺点：内存利用率仍然不高，小碎片多；进程大小受分区大小的限制；不能部分装入，难以实现各分区间的信息共享；无法实现虚存。,56,2. 关于虚存的实现 虚存：用户进程所需内存容量只受内存和外存容量之和的限制的存储器技术。单纯的分区管理是无法实现虚存的。 覆盖Overlay 由程序员提

30、供一个清晰的覆盖结构，从而实现进程内部不同模块之间的覆盖。 例：某进程由AF六段组成，如图：,覆盖 结构,Total:110K,缺点：编程复杂度过大，且进程模块大小仍 受限于分区大小。已淘汰！,57,对换Swapping 换出Swap_out：将内存中阻塞且优先级最低的进程(程序 + 数据)换到外存交换区，修改其PCB并回收相应内存。 换入Swap_in：将外存交换区中静止就绪且被换出时间最久的进程(程序 + 数据)换入内存并修改其PCB。 对换分类： 进程对换（整体对换） 部分对换（页面或分段对换）真正意义上实现虚存 对换的三个关键操作：换出、换入、对换空间（pagefile.sys）的管理

31、。 对换缺点：换入换出开销大。,58,关于地址变换和内存保护 地址变换：不实现紧凑时可采用“静态可重定位装入”方式，实现紧凑时必须采用“运行时动态可重定位装入”方式。 内存保护： 硬件法：为每个进程设置一对上、下界寄存器，或利用分区的基址寄存器和限长寄存器。若越界则产生地址保护中断并转错误处理。 软件法(保护键法)：为被保护分区设置保护键开关字段，针对不同的进程赋予不同的开关代码，通过检查两者是否匹配来实现读、写保护。 软硬结合法。,59,4.4基本(静态)分页存储管理方式,4.4.1页式管理的基本原理 回顾分区分配法：碎片问题严重，内存利用率不高；由于要求连续存放，导致进程的大小仍受分区大小

32、和内存可用空间的限制；不利于共享；无法实现虚存。 引入页式管理的目的：为了减少碎片，为了实现换入/换出而采用离散存储，提高内存利用率。 分页存储管理：将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号，从0开始，如第0页、第1页等。相应地，也把内存空间分成与页面相同大小的若干个存储块，称为(物理)块或页框(frame)，也同样为它们加以编号，如0#块、1#块等等。在为进程分配内存时以块为单位，将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”。,60,1. 页面 一个进程的虚拟空间被划分

33、为若干个长度相等的页面(page)，通常几KB几十KB为一页，故进程的虚地址(逻辑地址)可由页号P与页内地址W所组成。,假设这是某系统的分页地址结构，则该系统页长为210 = 1024B即1KB/页，一个进程最长允许有214 = 16384页即16384KB,61,与进程逻辑空间的分页结构类似，物理内存空间也被划分为与页面相等大小的若干物理块。 在为进程分配内存时，将进程的N个页面(必定连续) 装入到N个内存物理块(不一定连续)。即：连续的N个页面对应装入不连续的N个物理块。 页式管理特点：无外碎片的概念；且内碎片必定小于一个物理块；实现了非连续(离散)方式存储，为虚存的实现提供了基础；但管理

34、开销增大。 关键问题：如何将页面逻辑地址变换为内存物理地址？ 页表 + 硬件地址变换机构,62,2页表(Page Mapping Table) 由于在分页系统中，允许将进程的n个连续页离散地存储在内存不连续的n个物理块中，为此，系统又为每个进程建立了一张页面映像表，简称页表。在进程地址空间内的所有页(0n)，依次在页表中有一页表项，其中记录了相应页在内存中对应的物理块号，见图4-12的中间部分。在配置了页表后，进程执行时，通过查找该表，即可找到每页在内存中的物理块号。可见，页表的作用是实现从页号到物理块号的地址映射。,63,说明： 页表负责记录逻辑页面与内存物理块的一一对应关系 每个进程都有自

35、己的一张页表 页表的长度由进程大小和页面大小共同决定：比如一进程为4765B，若页面大小为1KB/页，则该进程包含5页(第0页第4页)，即该进程的页表包含5个表项,64,思考几个问题 页面大小一般为2n字节，但具体n有多大？过小怎样？过大怎样？ 过小：则页表过长，换入/换出效率低，使用和维护的开销大。 过长：页内碎片大。 已知逻辑地址和页面大小，如何计算页号及页内地址？ 页号 = 逻辑地址 / 页面大小 （整除运算） 页内地址 = 逻辑地址 % 页面大小 （求余运算） 例：已知页面大小为1KB/页，现有一数据的逻辑地址为2148，问：该数据在哪页的哪个位置？ 页号 = 2148 / 1024

36、= 2，页内地址 = 2148 % 1024 = 100，即：该数据在该进程的第2页的相对地址100处。,65,3静态页式管理(基本页式管理) 必须将一个进程的所有页面全部装入到内存物理块，无法实现虚存。 4动态页式管理 允许将一个进程的一部分页面装入到内存物理块。 采用“请求调页”或“预调页”技术实现了内外存存储器的统一管理即对换技术。 内存中只存放那些经常被执行或将要被执行的页面，而不常被执行或近期内不会执行的页面则存放在外存，待需要时再按请求式调入。 5分页管理的重点 逻辑地址 物理地址的地址变换(页表 + 硬件地址变换机构) 页面的动态置换技术,66,4.4.2地址变换机构 1基本的地

37、址变换机构 地址映射：连续的N个页面对应于不连续的N个物理块 逻辑页号 物理块号：查页表 页内地址 块内地址：两者相等 从成本和容量上来考虑，采用寄存器来存储页表是不现实的。因此，页表大多驻留在内存中，而在系统中只设置一个页表寄存器PTR(Page-Table Register)，在其中存放该进程的页表在内存的始址和页表的长度。平时，进程未执行时，页表的始址和页表长度存放在本进程的PCB中。当调度程序调度到某进程时，才将这两个数据装入页表寄存器中。因此，在单处理机环境下，虽然系统中可以运行多个进程，但只需一个页表寄存器。,67,地址变换算法 当某进程被调度执行时，将其PCB中记录的页表始址S和

38、页表长度L取出来放到“页表寄存器”中；同时，分页地址变换机构会自动将逻辑地址划分为页号P和页内地址W，然后用页号P与页表长度L比较：若PL则越界中断，否则合法，再以页号P去检索页表，查得该页P对应的物理块号，进而算得该块在内存的起始地址B，最后B与页内地址W(即块内地址)相加就得到了要访问的物理地址。这样便完成了从逻辑地址到物理地址的变换。图4-13示出了分页系统的地址变换机构。,68,69,例：已知页面长度为1KB/页，某进程的页表如图所示。现有逻辑地址为100的一条指令LOAD R1 , 2500。问： 试说明该指令的取指过程？ 试说明该指令的取数过程？,70,逻辑地址为100的指令的取指

39、过程： 页号 = 逻辑地址 / 页长 = 100 / 1024 = 0 页内地址 = 逻辑地址 % 页长 = 100 % 1024 = 100 物理地址 = 物理块号 * 块长 + 块内地址 = 2 * 1024 + 100 = 2148,71,逻辑地址为100的指令的取数过程(该数的逻辑地址为2500)： 页号 = 逻辑地址 / 页长 = 2500 / 1024 = 2 页内地址 = 逻辑地址 % 页长 = 2500 % 1024 = 452 物理地址 = 物理块号 * 块长 + 块内地址 = 8 * 1024 + 452 = 8644,72,2具有“快表”的地址变换机构 引入“快表”前：完

40、成一次取指或取数操作都至少要访问2次内存：第1次是通过访问内存页表，计算并获得指令或数据的物理地址；第2次是根据该物理地址去访问内存并取得想要的指令或数据。 如何加快访问速度？解决方法： 方法一：将进程的整张页表放在大量寄存器阵列中而不是放在内存中。该方法成本过于昂贵，不可取。 方法二：在地址变换机构中加入一个高速联想存储器，俗称快表。,73,引入“快表”后：快表中始终存放最近访问过或访问频率最高的若干页表项。在进行取指或取数操作时，地址变换机构先将页号拿到快表中检索：若找到对应物理块号则立即结合块内地址形成物理地址(此为命中Cache)；若未找到才去访问内存中完整的页表从而得到物理块号(此为

41、未命中Cache)，与此同时将该页表项从内存更新至快表。 命中Cache的情况下：取指或取数只需访问一次内存。 未命中Cache的情况下：取指或取数仍需访问二次内存。,74,图4-14具有快表的地址变换机构,75,例：已知检索一次快表的时间为20ns，访问一次内存的时间为100ns，问，在分页式系统中： (1) 若不使用快表机制，存取一个数据需多少时间？ (2) 若使用快表机制，再假定快表命中率分别为0%，50%，80%，90%，98%时，存取一个数据各需要多少时间？ 解： 若不使用快表，则存取一个数据需200ns 若使用快表，则存取一个数据需要的时间T： T = 命中率(1次访问快表+1次访

42、存) + (1 命中率) (1次访问快表+2次访存) = 命中率(20 + 100) + (1-命中率)(20 + 100 + 100),思考，从本例来看： 能否画出命中率和存取时间之间的曲线关系？ 能否推测出Cache容量和命中率之间的曲线关系？,76,4.4.3两级和多级页表 现代的大多数计算机系统，都支持非常大的逻辑地址空间(232264)。在这样的环境下，页表就变得非常大，要占用相当大的内存空间。例如，对于一个具有32位逻辑地址空间的分页系统，规定页面大小为4 KB即212 B，则在每个进程页表中的页表项可达1兆个(220)之多。又因为每个页表项占用一个字节，故每个进程仅仅其页表就要占

43、用1 MB的内存空间，而且还要求是连续的。显然这是不现实的，我们可以采用下述两个方法来解决这一问题： (1) 两级页表：采用离散分配方式来存储页表，即对页表进行分页。见下页图：先查外层页表得知内层页表地址，再根据内层页表找到块号。 (2) 请求调页表/预调页表：只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。,77,图4-15两级页表结构,78,图4-16具有两级页表的地址变换机构,79,2多级页表 对于32位的机器，采用两级页表结构是合适的；但对于64位的机器，采用两级页表是否仍可适用的问题，须做以下简单分析。如果页面大小仍采用4 KB即212 B，那么还剩下52

44、位，假定仍按物理块的大小(212位)来划分页表，则将余下的42位用于外层页号。此时在外层页表中可能有4096 G个页表项，要占用16384 GB的连续内存空间。这样的结果显然是不能令人接受的，因此必须采用多级页表，将外层页表再进行分页，也就是将各分页离散地装入到不相邻接的物理块中，再利用第2级的外层页表来映射它们之间的关系。,80,4.5基本分段存储管理方式,段式管理的基本思想： 把一个程序按功能或过程函数关系划分成若干个段(Segment)，每个段都有自己的名字且大小不等。段式存储管理以段为单位分配内存，一个段装入一个内存分区，同一程序的N个段对应的N个分区可以不连续，然后通过段表和硬件地址

45、映射机构把段式二维虚拟地址转换成实际的内存物理地址。,81,4.5.1引入分段存储管理方式的原因 方便编程和编译 程序是按照逻辑功能来划分段，每个段的虚拟地址都是从0开始 有利于信息共享 页无独立功能和逻辑意义，不便共享；段则相反。 有利于信息保护 同上 适于动态增长 页长固定不变，不利于动态增长；而段长可变。 适于动态链接 分段管理更适合于请求调入和预调入机制。,82,4.5.2静态分段系统的基本原理 1. 分段 一个程序的地址空间按逻辑功能被划分为N个段(有大有小)，分别载入N个内存分区中，段内的数据连续，不同段之间的数据离散。 例如，有主程序段MAIN、子程序段X、数据段D及栈段S等，如

46、图4-17所示。每个段都有自己的名字。为了实现简单起见，通常可用一个段号来代替段名，每个段都从0开始编址，并采用一段连续的地址空间。逻辑地址由段号(段名)和段内地址所组成。,在左图的地址结构中，每个程序最多被分为215即32K个段，每个段最长为217即128KB,83,？ 如何才能完成逻辑地址到物理地址的地址变换 ？,84,2段表 请回顾页式管理中“页表”的作用。 在段式管理中，系统中为每个进程建立一张段映射表(Segment Mapping Table)，简称“段表”。每个段在段表中占有一个表项，其中记录了该段在内存中的起始地址(又称为“基址”)和段的长度。,请尝试画出该进程的内存分布示意图

47、,85,图4-17利用段表实现地址映射,86,3地址变换机构 当某进程被调度执行时，将其PCB中记录的段表始址和段表长度取出来放到“段表寄存器”中；当进行地址变换时，系统将逻辑地址中的段号与段表长度比较：若段号段表长度则越界中断，否则合法，再以段号去检索段表，查得该段在内存中的起始地址和段长，然后，再比较段内地址与段长，如果段内地址段长则越界，否则合法，最后将该段起始地址与段内地址相加，即可得到最终要访问的内存物理地址。这样便完成了从逻辑地址到物理地址的变换。,87,88,例：已知某进程的段表如图所示。现有段号为2，段内地址为128的一条指令。请说明该指令的取指过程。,89,段号为2，段内地址

48、为128的指令的取指过程： 物理地址 = 段基址 + 段内地址 = 8192 + 128 = 8320,90,4. 添加“快表” 存放最近访问过或访问频率最高的若干段表项，其原理与页式管理中的快表相同。 由于段表的规模通常远小于页表，所以在段式管理中采用快表的效果要优于页式管理。,91,5静态分页与静态分段的比较 相同点：都是采用离散存储方式；都需硬件地址变换机构；都需整体装入，提供了实现虚存的部分基础。 不同点： 页以定长划分(系统需要)，段不定长且以逻辑功能划分(用户和程序员需要)。 段具备逻辑意义，更适于共享和动态链接。 页式管理中的逻辑地址是一维的，段式管理中的逻辑地址是二维的。 通常

49、段长比页长大，故段表比页表短，可缩短查找时间，提高访问速度。 页式管理的碎片问题轻于段式管理。,92,4.5.3信息共享 分段系统相比分页系统的优点之一是共享性。 例：一个多用户系统，最多同时接纳40个用户，每个用户都会用到一个文本编辑程序(Text Editor)，它分为160 KB的代码段和40 KB的数据段。问最多需要多少内存空间？ 不考虑共享：40(160 + 40)KB = 8000KB 段式共享：160KB + 4040KB = 1760KB 如果采用页式管理，假设页长为4KB/页：,93,图4-19分页系统中共享editor的示意图,94,图 4-20分段系统中共享editor的

50、示意图,95,可重入代码(纯代码Pure Code)：允许多个进程同时访问(读、执行) ，但不允许任何进程修改的内存共享代码段。最常见的是DLL模块，一般来说，DLL 是一种磁盘文件，以.dll、.drv、.fon、.sys 和许多以 .exe为扩展名的系统文件都可以是 DLL。 操作：c:windowssystem32tasklist /m,96,4.5.4段页式存储管理方式 1基本原理 页式：碎片少，内存利用率高 段式：面向用户，更利于共享和保护，可动态链接，可动态增长。 段页结合式：将程序划分成若干个段，再把每段分成若干个页。思考：段页结合式的逻辑地址应该是什么样的？,97,图4-22利

51、用段表和页表实现地址映射,98,2地址变换过程 在段页式系统中，为了便于实现地址变换，须配置一个段表寄存器，其中存放段表始址和段表长TL。进行地址变换时，首先利用段号S，将它与段表长TL进行比较。若STL，表示未越界，于是基于段表始址用段号去查段表，从而得到该段的页表始址，并利用逻辑地址中的段内页号P去查该段的页表，从中读出该页所在的物理块号b，再利用块号b和页内地址（即块内地址）来构成物理地址。图4-23示出了段页式系统中的地址变换机构。,99,图4-23段页式系统中的地址变换机构,100,思考：在段页式系统中，完成一次取指或取数操作需要访问几次内存？ 答案：3次！ 第1次：根据段号去访问段

52、表，得到页表始址 第2次：根据段内页号去访问页表，获得物理块号后再结合页内地址计算出物理地址 第3次：根据物理地址去访问内存，完成取指或取数操作 结论：更应该采用“快表”来提高内存访问效率,101,4.6虚拟存储器的基本概念,背景： 静态分页和静态分段都要求将程序的整体载入内存后才能运行。这将导致大程序无法运行或大量程序无法载入内存的情况。如何解决？ 从物理上扩充内存：需要￥，不在OS的讨论范畴。 从逻辑上扩充内存：虚拟存储器技术的作用。,102,4.6.1虚拟存储器的引入 1常规存储器管理方式的特征 (1) 一次性：程序必须一次性整体装入内存 (2) 驻留性：程序必须一次性整体卸出内存(程序

53、在执行中途不会部分撤出内存),想想，对于程序执行来说，这两个特征是必需的吗？,这两个特征的存在使得内存利用率很低，导致系统吞吐量变小,103,2局部性原理 在一小段时间内，程序的执行仅局限于某个段落，且它所访问的存储空间也局限于某个区域。 时间局部性：刚访问过的马上会再度被访问。(递归调用、循环结构) 空间局部性：刚访问过某处，马上会访问邻近的区域。(顺序存储结构),104,3虚拟存储器的定义 指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统，其逻辑容量由内存容量和外存容量之和决定，其运行速度慢于内存，而单位成本又接近于外存。 由此可见：虚拟存储器技术是一种以时间来换

54、取空间的技术。,105,4引入虚存技术的好处 可在较小的可用内存中执行较大的用户程序 可在内存中容纳更多的程序来实现并发执行 不必影响编程时的程序结构 提供给用户可用的虚拟内存空间大于实际物理内存容量,106,4.6.2虚拟存储器的实现方法 1分页请求系统 在静态分页系统的基础上，增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。它允许只装入少数页面的程序及数据，便启动运行。以后，再通过调页功能及页面置换功能，陆续地把暂不运行的页面换出到外存上，同时把即将要运行的页面调入内存。置换是以页为单位进行的。 为了实现请求调页和置换功能所必需的硬件和软件支持： 1) 硬件支持：缺页中断机构；地

55、址变换机构。 2) 软件支持：请求分页的页表机制；实现请求分页和页面置换的软件。,107,2请求分段系统 在静态分段系统的基础上，增加了请求调段及分段置换功能后所形成的段式虚拟存储系统。它允许只装入少数段(而非所有的段)的用户程序和数据，即可启动运行。以后再通过调段功能和段的置换功能将暂不运行的段调出，同时调入即将运行的段。置换是以段为单位进行的。 为了实现请求分段所必需的硬件和软件支持： 1) 硬件支持：缺段中断机构；地址变换机构。 2) 软件支持：请求分段的段表机制；实现请求分段和段置换的软件。,108,4.6.3虚拟存储器的特征 1离散性 一个进程在内存中非连续存放，是下面2、3、4的基

56、础 2多次性 一个程序被分成多次调入内存运行 3对换性 同一进程的不同部分之间换入换出频繁 4虚拟性 用户感觉的内存容量远大于物理内存容量,109,4.6.4虚拟存储器的种类 动态（请求）页式管理 动态（请求）段式管理 动态（请求）段页式管理,110,4.7请求分页存储管理方式,请求分页存储管理(动态分页式管理)：部分装入 + 动态置换 4.7.1请求分页中的硬件支持 1页表机制 在请求分页系统中所需要的主要数据结构是页表。其基本作用仍然是将用户地址空间中的逻辑地址变换为内存空间中的物理地址。由于只将应用程序的一部分调入内存，还有一部分仍在盘上，故须在页表中再增加若干项，供程序(数据)在换进、

57、换出时参考。在请求分页系统中的每个页表项如下页所示：,111,记录该页是否已在内存中,记录该页已被访问次数的计数器或未被访问时间的计时器,记录该页在内存中是否被修改过。以决定该页被换出时是否需要重写回外存,记录该页在外存对应的物理块号,思考：在上面6个字段中，哪些是所有页都有的？哪些是内存页才会有的？,所有页都有的字段 内存页才有的字段,112,2缺页中断机构 缺页：在指令执行期间，一旦发现要访问的页面当前不在内存，则称为一次缺页，必将引发一次缺页中断。缺页中断机构用于确保缺页中断及时、有效、安全地进行。(注意区别“缺页”与“置换”的概念) 缺页中断作为中断，它们同样需要经历诸如保护CPU环境

58、、分析中断原因、转入缺页中断处理程序进行处理、恢复CPU环境等几个步骤。但缺页中断又是一种特殊的中断，它与一般的中断相比，有着明显的区别： (1) 缺页中断是在指令执行期间产生和处理的。 (2) 一条指令在执行期间可能产生多次缺页中断。 3地址变换机构,113,图 4-25请求分页中的地址变换过程,114,4.7.2内存分配策略和分配算法 1最小物理块数的确定 这里所说的最小物理块数，是指能保证进程正常运行所需的最少物理块数。,115,2物理块的分配策略 1) 固定分配，局部置换(Fixed Allocation，Local Replacement) 为各进程分配固定不变的物理块数，缺页时只能

59、选择本进程的某页来置换。 分析：这种方式难以准确确定一个进程所需的物理块数。分配太少会导致频繁缺页，降低吞吐量；分配太多则限制了系统并发度，使资源利用率降低。,116,2) 可变分配，全局置换(Variable Allocation，Global Replacement) 为各进程分配若干物理块数，OS自身设置一个公共空闲物理块队列。某进程缺页时就从公共空闲物理块队列中选择一个物理块以调入缺页。若公共队列的空闲块用完则由OS选择任一进程的某页调出，从而腾出一个空闲块以载入缺页。,117,3) 可变分配，局部置换(Variable Allocation，Local Replacement) 为各进程分配一定数额的物理块数，缺页时只能选择本进程的某页来置换。但若系统发现某进程的缺页中断过于频繁，则由系统为该进程一次性再追加若干物理块以缓解缺页率；若系统发现某进程的缺页中断过于稀少，则由系统从该进程一次性回收若干物理块。,118,3物理块