第四章 存储器管理,山东交通学院 沈祥玖 中国水利水电出版社,第四章 存储器管理,4.1 程序的装入和链接 4.2 连续分配方式 4.3 基本分页存储管理方式 4.4 基本分段存储管理方式 4.5 虚拟存储器的基本概念 4.6 请求分页存储管理方式 4.7 页面置换算法 4.8 请求分段存储管理方式,主存管理的功能,地址映射 主存分配 存储保护 主存扩充(虚拟内存),一.地址映射(地址重定位),内存的每个存储单元都有一个编号，这种编号称为内存地址（或称为物理地址，绝对地址）。 内存地址的集合称为内存空间（或物理地址空间）。,要求用户用内存地址编程是非常困难的，尤其是在多道程序设计的环境中。 用户编程所用的地址称为逻辑地址（或程序地址，或虚地址），由逻辑地址组成的空间称为逻辑地址空间（或程序地址空间）。,地址映射的方式,我们把用户程序装入内存时对有关指令的地址部分的修改定义为从程序地址到内存地址的地址映射，或称为地址重定位。 地址映射的方式： 1、静态地址映射 2、动态地址映射,1、静态地址映射,程序被装入内存时由操作系统的连接装入程序完成程序的逻辑地址到内存地址的转换。,映射方法,假定程序装入内存的首地址为BR，程序地址为VR，内存地址为MR，则地址映射按下式进行：MR=BR+VR 。 例如，程序装入内存的首地址为1000，则装配程序就按MR=1000+VR对程序中所有地址部分进行修改，修改后指令Load A，200就变为Load A，1200,优缺点,优点：不需要硬件的支持。 缺点：程序必须占用连续的内存空间；一旦程序装入后不能移动。,2、动态地址映射,动态地址重定位是在程序执行的过程中，每次访问内存之前，将要访问的程序地址转换为内存地址。一般来说这种转换是由专门的硬件机构来完成的。,映射方法,最简单的硬件机构是重定位寄存器。 在地址重定位机构中，有一个基地址寄存器BR和一个程序地址寄存器VR，一个内存地址寄存器MR。,地址映射的具体过程,程序装入内存后，它所占用的内存区的首地址由系统送入基地址寄存器BR中。 在程序执行的过程中，若要访问内存，将访问的逻辑地址送入VR中。 地址转换机构把VR和BR中的内容相加，并将结果送入MR中，作为实际访问的地址。,动态地址映射的优缺点,优点： 程序占用的内存空间是动态可变的，当程序从某个存储区移到另一个区域时，只需要修改相应的寄存器BR的内容即可。 一个程序不一定要求占用一个连续的内存空间。 可以部分地装入程序运行。 便于多个进程共享同一个程序的代码。 动态地址重定位的代价： 需要硬件的支持。 实现存储管理的软件算法较为复杂。,二. 主存分配与回收,要完成内存的分配和回收工作，要求设计者选择和确定以下几种策略和结构： 调入策略 放置策略 置换策略 分配结构,调入策略,用户程序在何时调入内存的策略。 目前有请调和预调两种,放置策略,用户程序调入内存时，确定将其放置在何处的策略。,置换策略,当需要将某个用户程序调入内存而内存空间又不够时，就要确定哪个或哪些程序可以从内存中移走。,分配结构,分配结构是用来登记内存使用情况的数据结构。如空闲区表、空闲区队列等。,引起内存分配和回收的原因,进程的开始和结束。 进程运行的过程中，它所占用的内存也可能发生变化。如栈的变化。 进程映像在内存和外存之间传递。由于内存有限，系统中不可能容纳所有进程，有些进程的映像可以存放在外存，当要运行这些进程时，必须把它们调入内存。 系统为了充分利用内存空间，有时可能对内存空间进行调整。,三.存储保护,保证在内存中的多道程序只能在给定的存储区域内活动并互不产生干扰。 包括： 防止地址越界 防止越权(对共享区有访问权),存储保护的硬件支持,界地址寄存器（界限寄存器）,界地址寄存器（界限寄存器）,界地址寄存器被广泛使用的一种存储保护技术 机制比较简单，易于实现,实现方法,在CPU中设置一对下限寄存器和上限寄存器存放用户作业在主存中的下限和上限地址 也可将一个寄存器作为基址寄存器，另一寄存器作为限长寄存器（指示存储区长度） 每当CPU要访问主存，硬件自动将被访问的主存地址与界限寄存器的内容进行比较，以判断是否越界 如果未越界，则按此地址访问主存，否则将产生程序中断越界中断（存储保护中断）,图示,四.主存扩充(虚拟内存),为了使程序员在编程时不受内存的结构和容量的限制，系统为用户构造一种存储器，其结构可能与内存结构不同，容量可能远远超过内存的实际容量。这种面向编程的存储器称为虚拟存储器。由虚存构成的存储空间称为虚存空间。或称虚地址空间。,实现虚拟内存的基本原理,将程序正在使用的部分内容放在内存，而暂时不用的部分放在外存，在需要时由系统调入内存，并将不需要（或暂不需要）的部分调出内存。 由于程序在执行时，在一段时间内一般仅使用它的程序的一部分（或一小部分），所以程序仅有部分装入内存完全能够正确执行。 要由操作系统结合相关硬件来完成上述工件，这样计算机好象为用户提供了一个容量远大于内存的存储器，这个存储器称为虚拟存储器。,4.1 程序的装入和链接,图 4-1 对用户程序的处理步骤,4.1.1 程序的装入,1. 绝对装入方式(Absolute Loading Mode),程序中所使用的绝对地址，既可在编译或汇编时给出， 也可由程序员直接赋予。 但在由程序员直接给出绝对地址时， 不仅要求程序员熟悉内存的使用情况，而且一旦程序或数据被修改后，可能要改变程序中的所有地址。因此，通常是宁可在程序中采用符号地址，然后在编译或汇编时，再将这些符号地址转换为绝对地址。,2. 可重定位装入方式(Relocation Loading Mode),图 4-2 作业装入内存时的情况,3. 动态运行时装入方式(Denamle Run-time Loading),动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此， 装入内存后的所有地址都仍是相对地址。,4.1.2 程序的链接,1. 静态链接方式(Static Linking),图 4-3 程序链接示意图,在将这几个目标模块装配成一个装入模块时，须解决以下两个问题： (1) 对相对地址进行修改。 (2) 变换外部调用符号。,2. 装入时动态链接(Loadtime Dynamic Linking),装入时动态链接方式有以下优点： 便于修改和更新。 (2) 便于实现对目标模块的共享。,3. 运行时动态链接(Run-time Dynamic Linking),近几年流行起来的运行时动态链接方式，是对上述在装入时链接方式的一种改进。这种链接方式是将对某些模块的链接推迟到执行时才执行，亦即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存， 把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。,4.2 连续分配方式,4.2.1 单一连续分配,这是最简单的一种存储管理方式，但只能用于单用户、单任务的操作系统中。采用这种存储管理方式时，可把内存分为系统区和用户区两部分，系统区仅提供给OS使用，通常是放在内存的低址部分；用户区是指除系统区以外的全部内存空间， 提供给用户使用。,4.2.2 固定分区分配,1. 划分分区的方法,分区大小相等， 即使所有的内存分区大小相等。 (2) 分区大小不等。,2. 内存分配,图 4-4 固定分区使用表,4.2.3 动态分区分配,1. 分区分配中的数据结构,空闲分区表。 (2) 空闲分区链。,图 4-5 空闲链结构,2. 分区分配算法,首次适应算法FF。 (2) 循环首次适应算法，该算法是由首次适应算法演变而成的。 (3) 最佳适应算法。 (4) 最坏适应算法 。,3. 分区分配操作,1) 分配内存,图 4-6 内存分配流程,2) 回收内存,图 4-7 内存回收时的情况,4.2.4 可重定位分区分配,1. 动态重定位的引入,图 4-8 紧凑的示意,2. 动态重定位的实现,图 4-9 动态重定位示意图,3. 动态重定位分区分配算法,图 4-10 动态分区分配算法流程图,首次适应法,要求空闲区按首址递增的次序组织空闲区表（队列）。,分配：当进程申请大小为SIZE的内存时，系统从空闲区表的第一个表目开始查询，直到首次找到等于或大于SIZE的空闲区。从该区中划出大小为SIZE的分区分配给进程，余下的部分仍作为一个空闲区留在空闲区表中，但要修改其首址和大小。,回收：按释放区的首址，查询空闲区表，若有与释放区相邻的空闲区，则合并到相邻的空闲区中，并修改该区的大小和首址，否则，把释放区作为一个空闲区，将其大小和首址按照首地址大小递增的顺序插入到空闲区表的适当位置。,分析,注意：每次分配和回收后空闲区表或空闲区队列都要按首址递增的次序排序。 首次适应法的优点： 释放某一存储区时，若与空闲区相邻则合并到相邻空闲分区中去，这种情况并不改变该区在表中的位置，只要修改其大小或首址。 这种算法是尽可能地利用低地址空间，从而保证高地址空间有较大的空闲区。,最佳适应法,要求按空闲区大小从小到大的次序组成空闲区表（队列）。,分配：当进程申请一个存储区时，系统从表头开始查找，当找到第一个满足要求的空闲区时，停止查找，并且这个空闲区是最佳的空闲区。 所谓最佳即选中的空闲区是满足要求的最小空闲区。,回收：按释放区的首址，查询空闲区表（队列） ，若有与释放区相邻的空闲区，则合并到相邻的空闲区中，并修改该区的大小和首址，否则，把释放区作为一个空闲区插入空闲区表（队列） 。 分配和回收后要对空闲区表（队列）重新排序。,分析,优点： 在系统中若存在一个与申请分区大小相等的空闲区，必定会被选中，而首次适应法则不一定。 若系统中不存在与申请分区大小相等的空闲区，则选中的空闲区是满足要求的最小空闲区，而不致于毁掉较大的空闲区。 缺点： 空闲区的大小一般与申请分区大小不相等，因此将其一分为二，留下来的空闲区一般情况下是很小的，以致无法使用。随着时间的推移，系统中的小空闲区会越来越多，从而造成存储区的大量浪费。,最坏适应法,要求空闲区按大小递减的顺序组织空闲区表（或队列）。,分配：进程申请一个大小为SIZE的存储区时，总是检查空闲区表的第一个空闲区的大小是否大于或等于SIZE。若空闲区小于SIZE，则分配失败；否则从空闲区中分配SIZE的存储区给用户，然后修改和调整空闲区表。,回收：按释放区的首址，查询空闲区表（队列） ，若有与释放区相邻的空闲区，则合并到相邻的空闲区中，并修改该区的大小和首址，否则，把释放区作为一个空闲区插入空闲区表（队列） 。 分配和回收后要对空闲区表（队列）重新排序。,分析,最坏适应法看起来公似乎有些荒唐，但在更加严密地考察后，还是有它的优点： 当程序装入内存中最大的空闲区后，剩下的空闲区还可能相当大，还能装下较大的程序。 另一方面每次仅作一次查询工作。,三种策略比较,上述三种放置策略各有利弊，到底哪种最好不能一概而论，而应针对具体作业序列来分析。 对于某一作业序列来说，某种算法能将该作业序列中所有作业安置完毕，那么我们说该算法对这一作业序列是合适的。 对于某一算法而言，如它不能立即满足某一要求，而其它算法却可以满足此要求，则这一算法对该作业序列是不合适的。,举例,例1：有作业序列：作业A要求18K；作业B要求25K，作业C要求30K。系统中空闲区按三种算法组成的空闲区队列 经分析可知：最佳适应法对这个作业序列是合适的，而其它两种对该作业序列是不合适的。,练习,有作业序列：作业A要求21K；作业B要求30K，作业C要求25K。,思考,用可变分区(动态重定位)方式管理主存时,假定主存中按地址顺序依次有5个空闲区,空闲区的大小依次为32K,10K,5K,228K和100K,现有5个作业A,B,C,D,E.它们各需主存1K,10K,108K,28K