第5章存储管理

1、第四章 存 储 器 管 理 第5章 存储管理5.1 存储管理概述5.2 分区存储管理5.3 覆盖与交换技术5.4 页式管理5.5 段式与段页式管理5.6 局部性原理和抖动问题第四章 存 储 器 管 理 存储器是计算机系统的重要资源之一。因为任何程序和数据以及各种控制用的数据结构都必须占用一定的存储空间，因此，存储管理直接影响系统性能。 具体地说，存储管理有下面几个方面的功能：l 主存储空间的分配和去配。l 地址转换和存储保护。l 主存储空间的共享。l 主存储空间的扩充。5.1 存储管理概述第四章 存 储 器 管 理 n 存储器层次 目前，计算机系统均采用层次结构的存储子系统，以便在容量大小、速

2、度快慢、价格高低诸因素中取得平衡点，获得较好的性能价格比。计算机系统的存储器可以分为寄存器（register）、高速缓存（cache）、主存储器（memory）、磁盘缓存（disk cache）、固定磁盘（disk）、可移动存储介质（CD、USB）等 来组成层次结构。5.1 存储管理概述第四章 存 储 器 管 理 n 存储器层次 5.1 存储管理概述第四章 存 储 器 管 理 n 存储器层次 寄存器是访问速度最快但最昂贵的存储器，它的容量小，一般以字（word）为单位。一个计算机系统可能包括几十个甚至上百个寄存器，用于加速存储访问速度，如用寄存器存放操作数，或用作地址寄存器加快地址转换速度。

3、高速缓存的容量稍大，其访问速度快于主存储器，利用它存放主存中一些经常访问的信息可以大幅度提高程序执行速度5.1 存储管理概述第四章 存 储 器 管 理 n 存储器层次 可执行的程序必须被保存在计算机的主存储器中，与外围设备交换信息也依托于主存储器地址空间。 由于处理器在执行指令时主存访问时间远大于其处理时间，寄存器和高速缓存被引入来加快指令的执行。 5.1 存储管理概述第四章 存 储 器 管 理 n 存储器层次 由于程序在执行和处理数据时往往存在着顺序性、局部性、循环性和排他性，因此，在程序执行时有时并不需要把程序和数据全部调入内存，而只需先调入一部分，待需要时逐步调入。 算题的程序和处理的数

4、据可以装入磁盘缓存，操作系统自动实现主存储器和磁盘缓存之间数据的调进调出，从而，向用户提供了比实际主存存储容量大得多的存储空间。5.1 存储管理概述第四章 存 储 器 管 理 n 地址变换 memory mapping（重定位） 目标程序中的地址是一个从0开始的地址，并不是内存的实际地址。 把用户目标程序使用的地址称为逻辑地址（相对地址）。 一个用户作业的目标程序的逻辑地址集合称为该作业的逻辑地址空间。 作业的逻辑地址空间可以是一维的，这时逻辑地址限制在从0 开始顺序排列的地址空间内；也可以是二维（多维）的。段式、页式段式、页式5.1 存储管理概述第四章 存 储 器 管 理 n 地址变换（重定

5、位） 我们把主存中的实际存储单元称为物理地址（绝对地址），物理地址的总体相应构成了用户程序实际运行的物理地址空间。 当程序运行时，被装入主存储器地址空间的某些部分，此时程序和数据的实际地址一般不可能同原来的逻辑地址一致。5.1 存储管理概述第四章 存 储 器 管 理 5.1 存储管理概述虚拟存储器源程序 目标代码 由链接程序链接不同的程序段 编译程序安排目标代码地址的方法：1）按照物理存储器中的位置赋予实际物理地址。（由编译程序完成） 存储空间是指主存中一系列存储信息的物理单元的集合，其中的地址称为物理地址或绝对地址。第四章 存 储 器 管 理 5.1 存储管理概述虚拟存储器2）把用户源程序编

6、译后链接到一个以0地址为始地址的线形或多维虚拟地址空间。 链接可以是静态链接也可以是动态链接。 每个指令或数据单元都在这个虚拟空间中拥有确定的地址，把这个地址称为虚拟地址。 进程在该空间的地址排列可以是非连续的，其实际物理地址由虚拟地址到实际物理地址的地址变换机构变换得到。第四章 存 储 器 管 理 5.1 存储管理概述虚拟存储器由源程序到实际存放该程序指令或数据的内存物理位置的变换图：将进程中的目标代码，数据等的虚拟地址组成的虚拟空间成为虚拟存储器。实际物理存储器只有一个，每个进程都拥有自己的虚拟存储器。虚拟存储器的容量是由计算机的地址结构和寻址方式确定的。即与处理机的位数有关。第四章 存

7、储 器 管 理 5.1 存储管理概述虚拟存储器：当一个作业的地址空间超过了内存的可用空间时，为使作业得以运行，可以将作业的一部分地址空间放在内存，而将其余部分放在外存。当所访问的信息不在内存时，由操作系统将所需要的部分调入内存。从效果上看，这样的计算机系统好象为用户提供了一个其存储容量比实际内存大得多的存储器，这个存储器称为虚拟存储器。之所以将其称为虚拟存储器，是因为这种存储器实际上并不存在，只是由于系统采用了部分装入程序并能根据程序运行的需要调入将使用的内容，并置换出不再使用或暂不使用的内容，给用户的感觉是好象存在一个能满足作业地址空间要求的内存。虚拟存储器的实质是让作业存在的地址空间和运行

8、时用于存放作业的存储空间区分开。第四章 存 储 器 管 理 n 地址变换 为了保证程序的正确运行，必须把程序和数据的逻辑地址转换为物理地址，这一工作称为地址转换或重定位。l 静态重定位：发生在作业执行前一次完成，多由软件独立完成；l 动态重定位：发生在程序执行过程中，通常借助于地址转换机构硬件与软件共同实现。5.1 存储管理概述第四章 存 储 器 管 理 地址变换1、静态地址重定位是在虚拟空间程序执行之前由装配程序完成地址映射工作。程序一旦装入内存之后就不能在移动，并且必须在程序执行之前将有关部分全部装入。对于虚拟空间内的指令或数据来说，静态地址重定位只完成一个首地址不同的连续地址变换，要求所

9、有待执行的程序必须在执行之前完成它们之间的链接，否则将无法得到正确的内存地址和内存空间。 优点：不需要硬件支持。 缺点：无法实现虚拟存储器。必须占用连续的内存空间，难以作到程序和数据的共享。5.1 存储管理概述第四章 存 储 器 管 理 地址变换2、动态地址重定位是在程序执行过程中，在CPU访问内存之前，将要访问的程序或数据地址转换成内存地址。依靠硬件地址变换机构完成。 需要一个（或多个）基地址寄存器BR和一个（或多个）程序虚拟地址寄存器VR。指令或数据的内存地址MA与虚拟地址的关系为 MA=(BR)+(VR)优点：1）可以对内存进行非连续的分配。 2）动态重定位提供了实现虚拟存储器的基础。

10、3）有利于程序段的共享。 5.1 存储管理概述第四章 存 储 器 管 理 5.1 存储管理概述逻辑地址空间逻辑地址空间物理地址空间物理地址空间03456.LOAD A 200.0100200300.LOAD A 2003456110012001300200VR+1000BR第四章 存 储 器 管 理 内外存数据传输的控制1）由用户程序自己控制。 例子是覆盖技术，要求用户了解程序的结构，并指定各程序段调入内存的先后次序。程序段的最大长度受内存容量的限制，不能实现虚拟存储器。5.1 存储管理概述第四章 存 储 器 管 理 5.1 存储管理概述内外存数据传输的控制2）操作系统控制。 一种是交换方式，

11、即把内存中处于等待状态的进程换出内存，而把那些处于就绪态的进程换入内存。 不进行部分交换，每次交换都交换进程，即使部分交换，也不是根据执行的需要交换程序段，而是把受资源限制，暂时不能执行的程度段换出内存。因此，虽然能完成内存扩充，但不能实现虚拟存储器。 （自动覆盖、内存和外存统一管理、进程大小不受内存容量限制）第四章 存 储 器 管 理 内外存数据传输的控制 另一种请求调入方式和预调入方式。请求调入方式是在程序执行时，如果所要访问的程序段或数据段不在内存中，则操作系统自动的从外存将有关的程序段和数据段调入内存。预调入方式是由操作系统预测在不远的将来会访问到的那些程序段和数据段部分，并在它们被访

12、问之前系统选择适当的时机将它们调入内存的一种方式。 能实现虚拟存储器。5.1 存储管理概述第四章 存 储 器 管 理 n 内存的分配与回收 为了有效合理地利用内存，设计内存分配和回收方法时，必须考虑以下几个方面：l 分配结构：登记内存使用情况，供分配程序使用的表格与链表。例如内存空闲区表、空闲区队列等。 l 放置策略：确定调入内存的程序和数据在内存中的位置。这是一种选择内存空闲区的策略。5.1 存储管理概述第四章 存 储 器 管 理 n 内存的分配与回收 (3) 交换策略：在需要将某个程序段和数据调入内存时，如果没有足够空闲区，由交换策略来确定把哪些程序段和数据段调出内存。 (4) 调入策略：

13、外存中的程序段和数据段什么时间按什么样的控制方式进入内存。 (5) 回收策略：回收策略主要是对所回收的内存空闲区和已存在的内存空闲区的调整。5.1 存储管理概述第四章 存 储 器 管 理 n 内存信息的共享与保护 在多道程序设计环境下，内存中的许多用户或系统程序和数据段可供不同的用户进程共享。这种资源共享将会提高内存的利用率。 但是，反过来说，除了被允许共享的部分之外，又要限制各进程只在自己的存储区活动，各进程不能对别的进程的程序和数据段产生干扰和破坏，因此须对内存中的程序和数据段采取保护措施。5.1 存储管理概述第四章 存 储 器 管 理 n 内存信息的共享与保护l 上下界保护法 系统置一对

14、上下界寄存器，保存有正在执行的程序和数据段的起始地址和终止地址。 在程序执行过程中,在对内存进行访问操作时首先进行访址合法性检查,即检查经过重定位后的内存地址是否在上、下界寄存器所规定的范围之内。 若在规定的范围之内，则访问是合法的；否则是非法的，并产生访址越界中断。5.1 存储管理概述第四章 存 储 器 管 理 图5.4 上、下界寄存器保护法5.1 存储管理概述第四章 存 储 器 管 理 n 内存信息的共享与保护l 保护键法 保护键法为每一个被保护存储块分配一个单独的保护键。在程序状态字中则设置相应的保护键开关字段，对不同的进程赋予不同的开关代码和与被保护的存储块中的保护键匹配。 保护键可设

15、置成对读写同时保护的或只对读，写进行单项保护的。5.1 存储管理概述第四章 存 储 器 管 理 图5.5 保护键保护法5.1 存储管理概述第四章 存 储 器 管 理 n 内存信息的共享与保护l 界限寄存器与CPU状态结合法 在这种保护模式下，用户态进程只能访问那些在界限寄存器所规定范围内的内存部分，而核心态进程则可以访问整个内存地址空间。 UNIX系统就是采用的这种内存保护方式。5.1 存储管理概述第四章 存 储 器 管 理 n 基本思想 也称单用户分区，适用于单道系统的情况。 系统将主存空间分为系统区和用户区，系统区存放操作系统常驻代码和数据，用户区全部归一个用户作业所占用。 在这种管理方式

16、下，任一时刻主存储器中最多只有一道程序。 优缺点：管理方案简单；但仅适合于单道系统！内存利用率低！5.2 单一连续分区管理第四章 存 储 器 管 理 n 分配与回收 把用户区整个分配给一个作业，直至该专业执行完成，回收，并分配给另一个作业。 一般无需特别的数据结构来实现分配与去配操作。 5.2 单一连续分区管理第四章 存 储 器 管 理 n 地址转换 多采用静态重定位，由装入程序完成。 系统设置1个栅栏寄存器（fence register）用来指出用户区的起始地址S，地址转换公式为： 物理地址=逻辑地址+S 也可以采用动态重定位。n 访问保护 由装入程序检查其计算得到的绝对地址是否超过栅栏地址

17、。满足则装入，否则产生错误不装入。5.2 单一连续分区管理第四章 存 储 器 管 理 n 基本思想 系统将用户区域固定划分成若干个大小不等或相等的区域，一个分区可装入一个作业，实现多道程序设计技术。 在执行中，分区个数和大小不发生变化。 优缺点：适合于多道系统，支持多进程并发执行；但内存利用率不高。5.3 固定分区管理第四章 存 储 器 管 理 n 分配与回收 系统通过分区说明表管理内存，分区说明表主要包括分区号、分区大小、起始地址和是否是空闲区。 5.3 固定分区管理第四章 存 储 器 管 理 n 分配与回收分配：顺序查找一个满足要求的空闲分区，修改占用标志，并将专业装入该分区。回收：查找对

18、应作业所占分区，修改其标志即可完成。 5.3 固定分区管理第四章 存 储 器 管 理 n 地址转换 也多采用静态重定位，也是由装入程序完成。 物理地址=逻辑地址+分区起始地址 也可以采用动态定位方式。 系统设置一对上限/下限寄存器，也称基址/限长寄存器，分别保存正在运行的进程所在分区的起始地址、末址或分区长度。 硬件的地址转换机构实现地址转换： 物理地址=逻辑地址+下限寄存器地址 5.3 固定分区管理第四章 存 储 器 管 理 n 访问保护 硬件的地址转换机构同时把绝对地址和上限/下限寄存器中保存的相应地址进行比较，而实现存储保护。 系统通过分区说明表管理内存，分区说明表主要包括分区号、分区大

19、小、起始地址和是否是空闲区。5.3 固定分区管理第四章 存 储 器 管 理 n 基本思想 也称动态分区法，在系统初启时，除了操作系统中常驻内存部分之外，只有一个用户空闲分区。随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。具有以下特征: l 内存不是预先划分好的；l 作业装入时，根据作业的需求和内存空间的使用情况来决定是否分配；l 若有足够的空间，则按需要分割一部分分区给该进程；否则令其等待内存空间；5.4 可变分区管理第四章 存 储 器 管 理 n 分配与回收 系统设置空闲区表、已分配区表来记录分配与去配情况。分配：查找一个满足的分区，分割作业大小的分

20、区分配给申请作业，其余空闲部分形成另一个空闲分区；并修改空闲区表和已分配区表。回收：从已分配区表中找到对应栏，修改标志，并将空闲区信息登记到空闲区表中。 具体实例见下页：5.4 可变分区管理第四章 存 储 器 管 理 0K15K38K48K68K80K110K120K空闲区表空闲区表已分配区表已分配区表始址长度标志15K23K未分配48K20K未分配80K30K未分配空空始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ4空空第四章 存 储 器 管 理 0K15K38K48K68K80K110K120K空闲区表空闲区表已分配区表已分配区表始址长度标志15K23K未分配4

21、8K20K未分配98K12K未分配空空始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ480K5KJ585K13KJ685K98K第四章 存 储 器 管 理 n 分配与回收 由于分区的个数不定，采用空闲区链表是较好的另一种空闲区管理方法。 每个内存空闲区的开头单元存放本空闲区长度及下一个空闲区的起始地址指针，于是所有的空闲区都被链接起来，系统设置一个第一块空闲区地址指针，让它指向第一块空闲区的地址。 分配时，沿链查找并摘下一个长度能满足申请要求的空闲区交给进程，再修改链表；归还时，把空闲区链入空闲区链表即可。 5.4 可变分区管理第四章 存 储 器 管 理 n 分配与

22、回收 空闲区链表管理比空闲区表格管理较为复杂，但其优点是链表自身不占用存储单元。5.4 可变分区管理第四章 存 储 器 管 理 n 分配与回收 动态分区时的分配方法从可用表或自由链中寻找空闲区的常用方法有三种。 它们是最先适应法(first fit algorithm),最佳适应法(best fit algorithm)和最坏适应法(worst fit algoriathm)。这三种方法要求可用表或自由链按不同的方式排列。5.4 可变分区管理第四章 存 储 器 管 理 n 分配与回收 (1) 最先适应法 最先适应法要求可用表或自由链按起始地址递增的次序排列。 该算法的最大特点是一旦找到大于或等

23、于所要求内存长度的分区，则结束探索。 即找到第一个满足要求的低地址空闲区，分割分配。5.4 可变分区管理第四章 存 储 器 管 理 图5.11 最先适应算法5.4 可变分区管理第四章 存 储 器 管 理 n 分配与回收 (2) 最佳适应算法 最佳适应算法按照空间从小到大的次序组成空闲区可用表或自由链。 当用户作业或进程申请一个空闲区时，存储管理程序从表头开始查找，当找到第一个满足要求的空闲区时，停止查找。 即找到那个满足大小且是最小的空闲区，分割分配。5.4 可变分区管理第四章 存 储 器 管 理 n 分配与回收(3) 最坏适应算法 最坏适应算法要求空闲区按其空间大小递减的顺序组成空闲区可用表

24、或自由链。 当用户作业或进程申请一个空闲区时，顺序查找到第一个满足要求的空闲区用来分配。 即找到那个满足大小且是最大的空闲区，分割分配。5.4 可变分区管理第四章 存 储 器 管 理 n 分配与回收 在回收时，可能遇到4种情况： a) 该空闲区的上下两相邻分区都是空闲区； b) 该空闲区的上相邻区是空闲区； c) 该空闲区的下相邻区是空闲区； d) 两相邻区都不是空闲区。5.4 可变分区管理第四章 存 储 器 管 理 图5.12 空闲区的合并5.4 可变分区管理第四章 存 储 器 管 理 n 分配与回收 对上述4种情况，如果释放区与上下两空闲区相邻，则将三个空闲区合并为一个空闲区。 新空闲区的

25、起始地址为上空闲区的起始地址，大小为三个空闲区之和。 空闲区合并后，取消可用表或自由链中下空闲区的表目项或链指针，修改上空闲区的对应项。5.4 可变分区管理第四章 存 储 器 管 理 n 分配与回收 如果释放区只与上空闲区相邻，则将释放区与上空闲区合并为一个空闲区，其起始地址为上空闲区的起始地址，大小为上空闲区与释放区之和。合并后，修改上空闲区对应的可用表的表目项或自由链指针。5.4 可变分区管理第四章 存 储 器 管 理 n 分配与回收如果释放区与下空闲区相邻，则将释放区与下空闲区合并，并将释放区的起始地址作为合并区的起始地址。合并区的长度为释放区与下空闲区之和。合并后修改可用表或自由链中相

26、应的表目项或链指针。 如果释放区不与任何空闲区相邻，则释放区作为一个新可用区插入可用表或自由链。5.4 可变分区管理第四章 存 储 器 管 理 n 分配与回收 几种分配算法的比较 下面从查找速度、释放速度及空闲区的利用等三个方面对上述三种算法进行比较。 首先，从搜索速度上看，最先适应算法具有最佳性能。尽管最佳适应算法或最坏适应算法看上去能很快地找到一个最适合的或最大的空闲区。5.4 可变分区管理第四章 存 储 器 管 理 n 分配与回收几种分配算法的比较 再者，从回收过程来看，最先适应算法也是最佳的。因为使用最先适应算法回收某一空闲区时，无论被释放区是否与空闲区相邻，都不用改变该区在可用表或自

27、由链中的位置，只需修改其大小或起始地址。5.4 可变分区管理第四章 存 储 器 管 理 n 分配与回收最先适应算法的另一个优点就是尽可能地利用了低地址空间，从而保证高地址有较大的空闲区来放置要求内存较多的进程或作业。 最佳适应法找到的空闲区是最佳的。不过, 在某些情况下并不一定提高内存的利用率。 最坏适应算法正是基于不留下碎片空闲区这一出发点的。它选择最大的空闲区来满足用户要求，以期分配后的剩余部分仍能进行再分配。 总之，上述三种算法各有特长，针对不同的请求队列，效率和功能是不一样的。5.4 可变分区管理第四章 存 储 器 管 理 例：某操作系统采用可变分区分配存储管理方法，用户区为512K,

28、且始址为0，用空闲分区表管理空闲分区。初始时用户区的512K空间空闲，对下述申请序列：申请300K,申请100K,释放300K，申请150K,申请30K,申请40K,申请60K,释放30K.1)采用首次适应算法，空闲分区有那些块？2）采用最佳适应算法，空闲分区有那些块？3）如再申请100K,针对1）和2）有什么结果？第四章 存 储 器 管 理 1） 2)150K作业40K作业60K作业100K作业0150K180K220K280K300K400K512K-1150k作业60K作业100K作业40K作业0150K210K300K400K430K470K512K-1第四章 存 储 器 管 理 在可

29、变分区管理中，经过一段时间的分配回收后，内存中存在很多很小的空闲块。它们每一个都很小，不足以满足分配要求；但其总和满足分配要求。这些空闲块被称为碎片。 也就是说：不能被再次直接分配的小空闲区称为碎片。 碎片会造成存储资源的浪费！ 碎片问题第四章 存 储 器 管 理 “碎片”问题解决 紧凑技术：通过在内存移动程序，将所有小的空闲区域合并为大的空闲区域 （又称：紧缩技术，紧致技术，浮动技术，搬家技术） 问题：开销 大 移动时机 ？碎片问题第四章 存 储 器 管 理 有关分区管理其他问题的讨论1、关于虚存的实现也存在虚拟空间，但不存在虚拟存储器。如果不采用内存扩充技术，每个进程所需内存容量受到分区大

30、小限制。2、关于内存扩充使用覆盖或交换技术来扩充内存。第四章 存 储 器 管 理 3、关于地址变换和内存保护静态地址重定位和动态地址重定位都可以完成分区式内存管理的地址变换。但静态地址重定位的方法不能完成动态分区时的地址变换。在进行动态地址重定位时，每个分区需要一对硬件寄存器，即基地址寄存器和限长寄存器，分别用来存放作业或进程在内存分区的起始地址和长度。既能完成地址重定位，还能保护内存中的数据和程序。第四章 存 储 器 管 理 4、分区存储管理的主要优缺点优点：1）实现了多个作业或进程对内存的共享。2）要求的硬件少，算法简单，实现容易。缺点：1）内存利用率仍不高。可能有从未用过的信息或不能利用

31、的碎小空间。2）作业或进程的大小受分区大小控制。3）难以实现各分区间的信息共享。第四章 存 储 器 管 理 覆盖与交换技术是在多道环境下用来扩充内存的两种方法。 覆盖技术主要用在早期的操作系统中，而交换技术则在现代操作系统中仍具有较强的生命力。覆盖与交换技术第四章 存 储 器 管 理 n 覆盖技术 覆盖技术是把程序划分为若干个程序段，让不同时执行的多个程序段共享同一块内存区。 通常，这些程序段都被保存在外存中，运行中根据需要，把不同程序段调入内存，覆盖原有程序段。 用户看来，好像内存扩大了，从而达到了内存扩充的目的。 但是：要求程序员给出各程序段！覆盖与交换技术第四章 存 储 器 管 理 n

32、交换技术 多道程序环境或分时系统中，如果让这些等待中的进程继续驻留内存，将会造成存储空间的浪费。因此，应该把处于等待状态的进程换出内存。 交换是先将内存中某程序或数据写入外存交换区，再从外存交换区中调入指定程序或数据。 交换通常是在进程或作业之间进行，而覆盖则在同一个作业或进程内进行。 交换技术应用广泛。覆盖与交换技术第四章 存 储 器 管 理 n 引入原因 程序大于内存； 程序暂时不执行或运行完是否还要占用内存；n 基本原理 系统把程序当前使用部分保留在内存，而把其它部分保存在磁盘上，在需要时在内存和磁盘之间动态交换。n 虚拟存储器：把内存与外存有机的结合起来使用，从而得到一个容量很大的“内

33、存”，这就是虚存。虚拟存储技术第四章 存 储 器 管 理 n 实现思想 当进程运行时，先将一部分程序装入内存，另一部分暂时留在外存，当要执行的指令不在内存时，由系统自动完成将它们从外存调入内存工作。n 实现目的 提高内存利用率不足：以时间换空间！虚拟存储技术第四章 存 储 器 管 理 n 引入原因 分区式管理属于连续管理方式，尽管方式简单，但存在着严重的碎片问题，使得内存的利用率不高。 页式管理正是为了减少碎片而提出的一种非连续的内存管理方案，应用广泛。 l 页较小，每个作业产生的碎片小于1个页面。l 非连续方式不用移动即可实现大作业的装入，增加作业装入数量。静态页式管理第四章 存 储 器 管

34、 理 n 基本原理 首先将作业逻辑空间划分成若干个长度相等的区域，称为页(page)。 一般，页大小为1-4K，经过页划分之后，进程中连续的逻辑地址即由页号与页内地址两部分构成。页号页内地址静态页式管理第四章 存 储 器 管 理 例如：有8页的逻辑空间，每页有1024字节，逻辑地址的有效位是多少位。 静态页式管理第四章 存 储 器 管 理 n 基本原理 其次，把内存空间按页大小划分为片、块或页面(page frame)。 分配时，作业中的每个页被分配装入内存中的一个页面。 分配的对应关系保存在页表中，供动态重定位时使用。静态页式管理第四章 存 储 器 管 理 n 相关数据结构 (1) 页表：由

35、页号、页面号组成，保存在内存中的指定区域。 页表的大小由作业的长度决定，每个作业有1个对应页表。静态页式管理页 号页面号第四章 存 储 器 管 理 n 相关数据结构 (2) 请求表（作业表）：表示系统中每个作业的页表保存信息，包括作业的请求页面数、页表起始地址、页表长度，整个系统1张请求表。静态页式管理第四章 存 储 器 管 理 n 相关数据结构 (3) 存储页面表：表示物理内存的分配情况，包括空闲块位置、空闲块总数等，整个系统1张存储页面表。 常见的有位示图和空闲链表。 位示图：包含若干个字，每个字包含若干位，每位对应1个页面。1分配，0空闲。静态页式管理第四章 存 储 器 管 理 静态页式

36、管理第四章 存 储 器 管 理 n 相关数据结构 (3) 存储页面表： 另一种是采用空闲页面链，在空闲页面链中，队首页面的第一个单元和第二个单元分别放入空闲页面总数与指向下一个空闲页面的指针。其他页面的第一个单元中则分别放入指向下一个页面的指针。 空闲页面链的方法由于使用了空闲页面本身的单元存放指针，因此不占据额外内存空间。静态页式管理第四章 存 储 器 管 理 n 内存页面分配与回收 1. 分配算法 【1】由作业大小计算页面数，填入请求表中。 【2】检查存储页面表是否剩余足够空闲页面数，有则分配页表空间，并将页表信息填入请求表的相应表项；否则等待。 【3】按一定算法，依次检索得到空闲页面号，

37、并与页号一一对应填入指定的页表，建立页表。修改空闲页面总数。 【4】将作业装入对应的内存页面中。静态页式管理第四章 存 储 器 管 理 n 内存页面分配与回收 2. 回收算法 当进程执行完成后，由请求表得到其页表地址，由页表中的页面号计算得到其在存储页面表中的位置，修改位示图或加入空闲链表中，并更改空闲页面总数。静态页式管理第四章 存 储 器 管 理 n 地址变换 【1】系统把所调度执行的进程页表始址和长度从请求表中取出置入控制寄存器中。 【2】由控制寄存器的页表始址，可以找到页表所在位置。静态页式管理页号页面号021328第四章 存 储 器 管 理 n 地址变换【3】将逻辑地址通过地址变换机

38、构转换为页号与页内地址的地址形式。【4】查找页表，得到该页号所对应的页面号。 【5】将得到的页面号与页内地址，一起送到地址变换机构，计算后得到物理内存。 物理地址=页面号*页长+页内地址静态页式管理第四章 存 储 器 管 理 静态页式管理地址转换机构地址转换机构页大小为页大小为2KB?第四章 存 储 器 管 理 例：在采用页式存储管理的系统中，某作业J的逻辑地址空间为4页（每页2048字节），且已知该作业的页表如下： 求出有效逻辑地址4865所 对应的物理地址页号 页面号02142638第四章 存 储 器 管 理 解：逻辑地址4865的页号以及页内地址为 页号 4865/2048=2 页内地址

39、 4865-2048*2=769 通过页表，第2页对应页面为6 所以物理地址为： 6*2048+769=13057第四章 存 储 器 管 理 n 地址变换 另外，由于页表在内存中，因此，取一个数据或指令至少要访问内存两次以上。一次访问页表以确定所取数据或指令的物理地址，另一次是根据地址取数据或指令。 提高查找速度一种办法是在地址变换机构中加入一个高速联想存储器，构成一张快表。在快表中，存入那些当前页表中最常用部分页号与所对应的页面号，从而以提高查找速度。静态页式管理第四章 存 储 器 管 理 静态页式管理p页表页表地址越界地址越界 l比较比较P=1pp. . .快表快表 b+页号页号 页内地址

40、页内地址Pd物理地址物理地址页表地址寄存器页表地址寄存器页表长度寄存器页表长度寄存器逻辑地址逻辑地址带有快表的地址映射机制第四章 存 储 器 管 理 n 优缺点分析 优点：每个作业的碎片小于1个页面大小，内存利用率较高，不连续分配，有利于多道程序设计。 缺点：静态页式管理同以前所有管理方式一样，仍然要求作业在执行前全部装入内存，因此作业大小一样受到实际内存大小限制！静态页式管理第四章 存 储 器 管 理 n 多级页表结构 现代计算机可以支持232264 的逻辑地址空间，采用页式存储管理时，页表会相当大。 以Windows 2000/XP 为例，使用232 逻辑地址空间的分页系统，页面4KB（2

41、12）时，那么，4GB虚地址空间有1 兆（220）个页组成，若以每个页表项占用4 B计算，则需要占用4MB连续内存空间存放页表，这是1个进程的虚地址表示。 可见，实际系统中的存储页表也要分页面，即形成多级结构。静态页式管理第四章 存 储 器 管 理 n 多级页表结构 多级页表结构的本质是多级不连续导致了多级索引。以二级页表结构为例，用户程序的页面不连续存放，需要有页面地址索引，该索引就是进程页表；而由于进程页表又是不连续存放的多个页表页，故这些页表页也需要页表页地址索引，该索引就是页目录。 这就形成了二级索引，页目录项是页表页的索引，而页表页项是进程程序的页面索引。静态页式管理第四章 存 储

42、器 管 理 静态页式管理第四章 存 储 器 管 理 静态页式管理页目录地址页目录地址目录位移目录位移 页表位移页表位移 页位移页位移虚地址虚地址页表地址页表地址.页目录页目录块号块号.页表页表代码或数据代码或数据.内存块内存块二级页表结构及地址映射二级页表结构及地址映射+第四章 存 储 器 管 理 动态页式管理是一种采用了虚拟存储的页式管理。 n 基本思想 在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面。 执行过程中，会发生缺页中断，由中断处理程序负责页

43、面申请、页面调度、交换调度、装入页面等任务。动态页式管理第四章 存 储 器 管 理 n 页表 新增加：外存地址、驻留位（中断位）、改变位、访问位等。 驻留位（中断位）：该页是在内存还是在外存； 访问位：是否访问、访问时间或次数等； 修改位：是否被修改过；/换出时回写外存动态页式管理页号页号中断位中断位页面号页面号外存地址外存地址访问位访问位 修改位修改位第四章 存 储 器 管 理 n 缺页中断（Page Fault）处理 在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断，执行缺页中断处理程序，根据外存地址将该页调入内存。 如果内存中有空闲块，则分配1页，将新调入页装入内存，并

44、修改页表中相应页表项目的驻留位及相应的内存块号； 若此时内存中没有空闲块，则要淘汰某页，若该页在内存期间被修改过，则要将其写回外存。动态页式管理第四章 存 储 器 管 理 n 页面置换算法（页面调度） 置换算法在内存中没有空闲页面时被调用。它的目的是选出一个被淘汰的页面。（1）先进先出算法（FIFO） 选择在内存中驻留时间最长的页并淘汰之，访问位保存页面装入的时间。简单，效率低（2）最佳页面算法（OPT） 淘汰以后不再需要的或最远的将来才会用到的页面， 也称Belady 算法。无法实现动态页式管理第四章 存 储 器 管 理 n 页面置换算法（页面调度）（3）最近最久未用算法（LRU） 选择最后

45、一次访问时间距离当前时间最长的一页并淘汰之，即淘汰没有使用的时间最长的页。 访问位保存最近访问的时间。局部原理（4）最近最不常用算法（LFU） 选择访问次数最少的页面淘汰之； 访问位保存页面访问次数；软件复用 LRU与LFU算法实现有难度。动态页式管理第四章 存 储 器 管 理 例1：某程序在内存中分配三个页面，初始为空，页面走向为4，3，2，1，4，3，5，4，3，2，1，5，计算缺页次数页面淘汰算法-实例分析第四章 存 储 器 管 理 FIFO 4 3 2 1 4 3 5 4 3 2 1 5页1 4 4 4 1 1 1 5 5 5 5 5 5 页2 3 3 3 4 4 4 4 4 2 2

46、2页3 2 2 2 3 3 3 3 3 1 1 x x x x x x x x x 共缺页中断9次页面淘汰算法-实例分析第四章 存 储 器 管 理 LRU 4 3 2 1 4 3 5 4 3 2 1 5页1 4 4 4 1 1 1 5 5 5 2 2 2页2 3 3 3 4 4 4 4 4 4 1 1 页3 2 2 2 3 3 3 3 3 3 5 x x x x x x x x x x共缺页中断10次页面淘汰算法-实例分析第四章 存 储 器 管 理 例2：某程序在内存中分配m页初始为空，页面走向为1，2，3，4，1，2，5，1，2，3，4，5。当m=3，m=4时缺页中断分别为多少？用FIFO算

47、法计算缺页次数页面淘汰算法-实例分析第四章 存 储 器 管 理 m=3时，缺页中断9次m=4时，缺页中断10次注：FIFO页面淘汰算法会产生异常现象（Belady现象），即：当分配给进程的物理页面数增加时，缺页次数反而增加页面淘汰算法-实例分析第四章 存 储 器 管 理 (1) 分配给进程的物理页面数(2) 选择的页面大小(3) 程序的编制方法(4) 页面淘汰算法影响缺页次数的因素第四章 存 储 器 管 理 颠簸（抖动）： 在虚拟存储系统中，由于过量的页面调度，系统处于难以做有效工作的状态，使得系统效率急剧下降，该现象称为颠簸或抖动（Thrashing）。原因： 页面淘汰算法不合理； 分配给进

48、程的物理页面数太少；抖动现象第四章 存 储 器 管 理 n 存储保护 页式管理可以为内存提供两种方式的保护。l 地址越界保护：由地址变换机构中的控制寄存器的值页表长度和所要访问的虚地址相比较来完成。l 页表存取控制：在页表中增加相应的保护位即可。读、写等动态页式管理第四章 存 储 器 管 理 n 页式管理的优缺点 具有如下优点: (1) 作业可以不连续连续存放，解决了碎片问题。 (2) 动态页式管理采用虚存方式，扩大了存储空间。既提高了主存利用率，又有利于组织多道程序执行。 动态页式管理第四章 存 储 器 管 理 n 页式管理的优缺点 主要缺点: (1) 要求有相应的硬件支持。如地址变换机构等

49、； (2) 增加了系统开销，如缺页中断处理、页面调度算法等； (3) 页面算法不当，可能产生抖动现象。 (4) 每个作业的最后一页内总有部分空间属于碎片，如果页面较大 ，则会浪费内存.动态页式管理第四章 存 储 器 管 理 n 地址映射 基本同静态页式管理。 地址转换由称为主存管理单元MMU（Memory Management Unit），通常由一个或一组芯片组成，接受虚拟地址作为输入，物理地址作为输出，直接送到总线上，对内存单元进行寻址。动态页式管理第四章 存 储 器 管 理 动态页式管理第四章 存 储 器 管 理 在一个请求页式存储管理系统中，进程P共有5页，访问串为3，2，1，0，3，2

50、，4，3，2，1，0，4时，试用LRU置换算法和LFU置换算法，计算当分配给该进程的页面数分别为3和4时，访问过程中发生的缺页次数和缺页率，比较所得的结果，浅析原因。 课堂练习题第四章 存 储 器 管 理 n 引入原因 分区式管理和页式管理时的进程地址空间结构都是线性的，这要求对源程序进行编译、链接时，把源程序中的主程序、子程序、数据区等按线性空间的一维地址顺序排列起来。 这使得不同作业或进程之间共享公用子程序和数据变得非常困难。 另外，页式管理的页大小和页的划分由OS自动完成，用户无权干预。段式管理第四章 存 储 器 管 理 n 基本思想 用户把程序按内容或过程(函数)关系分成段，每段有自己

51、的名字。 一个作业或进程所包含的段对应于一个二维线性虚拟空间。 段式管理程序以段为单位分配内存，然后通过地址映射机构把段式虚拟地址转换成实际的内存物理地址。 和页式管理时一样，段式管理可以采用虚拟存储器。段式管理第四章 存 储 器 管 理 n 段式虚存空间 段式管理把一个进程的虚地址空间设计成二维结构，即段号s 与段内相对地址w。 段式管理中的段号与段号之间无顺序关系。段的划分长度是不固定的。每个段定义一组逻辑上完整的程序或数据。 例如，一个进程中的程序和数据可被划分为主程序段、子程序段、数据段与工作区段。段式管理第四章 存 储 器 管 理 n 段式虚存空间 每个段是一个首地址为零的、连续的一

52、维线性空间。 根据需要，段长可动态增长。 对段式虚地址空间的访问包括两个部分: 段名和段内地址。 实质上，段式管理就是可变分区的一种变形，用户将作业划分为若干段，即可分配若干不连续的分区中。段式管理第四章 存 储 器 管 理 n 内存分配与释放 段式管理中以段为单位分配内存，每段分配一个连续的内存区。同一进程所包含的各段之间不要求连续。 段式管理的内存分配与释放在作业或进程的执行过程中动态进行。 分配与释放内存的策略基本同可变分区管理。段式管理第四章 存 储 器 管 理 n 段式管理的地址变换 (1) 段表(segment mapping table) 和页式管理方案类似，段式管理程序在进行初

53、始内存分配之前，首先根据用户要求的内存大小为一个作业或进程建立一个段表，以实现动态地址变换和缺段中断处理及存储保护等。段式管理第四章 存 储 器 管 理 段式管理段段 表表第四章 存 储 器 管 理 段式管理作业表作业表第四章 存 储 器 管 理 段式地址变换过程段式管理第四章 存 储 器 管 理 n 段式管理的优缺点 （1）段式管理为用户提供了一个二维的虚地址空间，反映了程序的逻辑结构，有利于段的动态增长以及共享和内存保护等，这大大地方便了用户。（2）和页式管理一样，段式管理也可以采用内外存统一管理的虚存实现。（3）在段式管理中，段长可根据需要动态增长。段式管理第四章 存 储 器 管 理 n

54、 段式管理的优缺点 但是，段式管理要求更多的硬件支持，提高了机器成本。 另外，该管理方式与可变分区式相同，易产生碎片问题； 再者，允许段的动态增长也会给系统管理带来一定的难度和开销。 段式管理第四章 存 储 器 管 理 例：某段表的内容如下：一逻辑地址为（2154），它对应的物理地址为段号段首址段长度0120k40k1760k30k2480k20k3370k20k第四章 存 储 器 管 理 n 引入原因 段式具有逻辑结构，便于用户使用，但碎片问题严重；而分页系统则有效地克服了碎片，提高了存储器的利用率。于是，段页式管理方式便被提了出来。 不过，段页式管理的开销会更大。因此，段页式管理方式一般只

55、用在大型机系统中。近年来由于硬件发展很快，段页式管理的开销在工作站等机型上已变得可以容忍了。段页式管理第四章 存 储 器 管 理 n 基本思想 综合段式和页式两种方式的优点，先将作业按照用户逻辑分段，再将每个段进行页式划分，形成两级划分。段大小不固定，但页大小是固定的。 这样，既保留用户逻辑结构，又提高内存利用率。段页式管理第四章 存 储 器 管 理 n 虚地址的构成 首先，一个进程中所包含的具有独立逻辑功能的程序或数据仍被划分为段，并有各自的段号s。这反映和继承了段式管理的特征。 其次，对于段s中的程序或数据，则按照一定的大小将其划分为不同的页。 从而，虚拟地址由三部分组成: 即段号s，页号p和页内相对地址d。如下所示:段页式管理第四章 存 储 器 管 理 对于这个由三部分组成的虚拟地址来说，程序员可见的仍是段号s和段内相对地址w。p和d 是由地址变换机构把w的高几位解释成