ch4计算机存储器管理.ppt

第四章 存储器管理,4.0 准备知识 4.1 程序的装入和链接 4.2 连续分配方式 4.3 基本分页存储管理方式 4.4 基本分段存储管理方式 4.5 虚拟存储器的基本概念 4.6 请求分页存储管理方式 4.7 页面置换算法 4.8 请求分段存储管理方式,近年来，微电子技术及大规模集成电路取得了长足的进步，以半导体芯片组成的存储器，其容量由过去的几百、几千字节扩大到几十兆字节，甚至更大容量的存储器已经问世。 随着计算机应用领域的拓宽，目前不少企事业部门要求应用计算机来实现管理现代化，建立综合的管理信息系统，其要求存储的数据量愈来愈大；另外软件资源也愈来愈丰富，系统软件和应用软件在种类、功能及其所需存储空间等都在急剧增加。 存储器作为计算机系统的重要组成部分，虽然其容量一直在不断的扩大，价格已相当便宜，但主存容量仍然是计算机硬件资源中最关键而又最紧张的“瓶颈”资源，仍然满足不了现代化软件发展的需要。,4.0 准备知识,因此，存储器仍然是计算机系统中宝贵且紧俏的资源。它们如何合理而有效地使用它，在很大程度上反映了 OS 的性能，并直接影响到整个计算机系统性能的发挥。所以，存储器管理仍是目前人们研究 OS 的中心问题之一，对主存的管理和有效使用仍然是今天OS 十分重要的内容。许多OS之间最明显的区别特征之一往往是所使用的存储管理方法不同。 如OS/360-MFT采用固定分区存储管理技术，OS/360-MTV是采用可变分区存储管理技术，OS/2，WindowsNT, 是采用虚拟存储管理技术。 由于对外存的管理与对内存的管理有许多相似之处，只是两者用途不同，加之外存主要用来存储文件，故对外存的管理放在文件管理一章中介绍，存储器管理讨论的对象是内存。,本章主要介绍各种实存储分配和管理方案，虚拟存储器的概念及实现不同虚拟存储器的技术的讨论。 操作系统之所以有那么多种类，甚至一种型号的计算机配置若干种操作系统，其主要原因之一是为了适应各种用途而采用了不同的存储器管理策略。 在介绍各种存储器管理技术方案之前，首先指出存储器管理的主要目的及其应提供的主要功能，并说明在存储器管理中几个十分重要的概念。例如：存储器的层次、存储分配、地址重定位等概念。,高速缓存Cache：K字节、高速、昂贵、易变的 内存RAM： M字节、中速、中等价格、易变的 磁盘：G或T字节、低速、价廉、不易变的,为能更多的存放并更快地处理用户信息，目前许多计算机把存储器分为三级。,4.0.1 存储器的层次结构,图中的三级存储器，从高速缓冲存储器(简称缓存)到外部存储器(以后简称外存)，其容量愈来愈大，而访问数据的速度则愈来愈慢，价格也愈来愈便宜。如现在的缓存的最大传输速度为几十分之一至几百分之一ns，主存的传输速度几ns级。 用户的程序在运行时应存放在主存中，以便处理机访问。其中直接存取要求内存速度尽量快到与CPU取指速度相匹配，大到能装下当前运行的程序与数据，否则CPU执行速度就会受到内存速度和容量的影响而得不到充分发挥。 但是由于主存容量和速度有限。所以把那些不马上使用的程序、数据放在外部存储器(又称辅存)中。当用到时再把它们读入主存。 由操作系统协调这些存储器的使用,4.0.1 存储器的层次结构,为了便于对主存储器进行有效的管理，我们把存储器分成若干个区域。即使在最简单的单用户系统中，至少也要把它分成两个区域：在一个存储区域内存放系统软件，如操作系统本身；而另一个存储区域则用于安置用户作业。显然，在多用户系统中，为了提高系统的利用率，需要将存储器划分成更多的区域，以便同时存放多个用户作业。这就引起了存储器分配问题及随之产生的其它问题。,4.0.2 存储器管理的目的和功能,存储器管理的主要目的和功能如下： 1.主存储器的分配和管理：按用户要求把适当的存储空间分配给相应的作业。一个有效的存储分配机制，应在用户请求时能作出快速的响应，分配相应的存储空间；在用户不再使用它时，应立即回收，以供其他用户使用。为此，这个存储分配机制应具有如下功能（3个）： (1)记住每个存储区域的状态：哪些是已分配的，哪些是可以用作分配的。 (2)实施分配：在系统程序或用户提出申请时，按所需的量给予分配；修改相应的分配记录表。 (3)接受系统或用户释放的存储区域：并相应地修改分配记录表。,4.0.2 存储器管理的目的和功能,2.提高主存储器的利用率：使多道程序能动态地共享主存，最好能共享主存中的信息。 3.“扩充”主存容量：这是借助于提供虚拟存储器或其它自动覆盖技术来达到的。即为用户提供比主存的存储空间还大的地址空间，之后，用户可以想象把他的程序或数据装入到这样的地址空间内。 4.存储保护：确保各道用户作业都在所分配的存储区内操作，互不干扰。即要防止一道作业由于发生错误而损害其它作业，特别需要防止破坏其中的系统程序。这个问题不能用特权指令来加以解决。而必须由硬件提供保护功能，并由软件配合实现。,4.0.2 存储器管理的目的和功能,所谓存储分配，主要是讨论和解决多道作业之间共享主存的存储空间问题。前面已讲到现代计算机系统都采用多级存储体系结构。因此，存储分配所要解决的问题是：要确定什么时候，以什么方式，或是把一个作业的全部信息还是把作业运行时首先需要的信息分配到主存中，并使这些问题对用户来说尽可能是“透明”的。 解决存储分配问题有三种方式： 1.直接指定方式：程序员在编程序时，或编译程序(汇编程序)对源程序进行编译(汇编)时，所用的是实际存储地址。 例如，在多道程序环境下，应保证各作业所用的地址互不重叠。,4.0.3 存储分配的三种方式,显然，采用直接指定方式分配的前提是：存储器的可用容量(空间)已经给定或可以指定，这对单用户计算机系统是不成问题的。 在多道程序发展的初期，通常把存储空间划分成若干个固定的不同大小分区，并对不同的作业指定相应的分区。因此，对算题人员或对编译程序而言，存储器的可用空间是可知的。 这种分配方式的实质是：由算题人员在编程序时，或由编译程序编译源程序时，对一个作业的所有信息确定了在主存存储空间中的位置。因此，这种直接指定方式的存储分配方案，不仅用户感到不便，而且存储空间的利用也不那么有效。（缺点）,4.0.3 存储分配的三种方式,2.静态分配(Static Allocation) 采用这种静态存储分配方案，用户在编程时，或由编译程序产生的目的程序，均可从其地址空间的零地址开始；它们是当装配程序对其进行连接装入时才确定它们在主存中的相应位置，从而生成可执行程序。也就是说，存储分配是在装入时实现的。 这种静态存储分配方式的特点是： (1)在一个作业装入时必须分配其要求的全部存储量； (2)如果没有足够的存储空间，就不能装入该作业； (3)一旦一个作业进入内存后，在其退出系统之前，它一直占用着分配给它的全部存储空间； (4)在作业的整个运行过程中不能在内存中“搬家”、也不能再申请存储量。 这种静态分配策略的存储管理很简单，但在多道程序系统中不能有效地共享存储器资源。,4.0.3 存储分配的三种方式,3.动态分配(Dynamic Allocation)：动态分配是一种更加有效的使用主存储器的方法。 这种动态存储分配方式的特点是： (1)作业在存储空间中的位置，也是在其装入时确定的； (2)在其执行过程中可根据需要申请附加的存储空间； (3)一个作业已占用的部分存储区域不再需要时，可以要求归还给系统。即：这种存储分配机制能接受不可预测的分配和释放存储区域的请求，实现个别存储区域的分配和回收； (4)存储区域的大小是可变的； 要求这个区域必须是单个连续的存储区域，以便和提出存储请求之作业的虚拟地址空间相对应。 (5)它允许作业在内存中“搬家”。 目前，绝大多数计算机系统都采用静态或动态存储分配策略，所以，在本章只讨论这两种存储分配的实现技术，重点放在各种动态存储分配技术的实现上。,4.0.3 存储分配的三种方式,我们首先要分清几个不同概念： 1.地址空间：是指由目标程序所限定的地址范围。即：地址空间仅仅是指程序用来访问信息所用的一系列地址单元的集合。这些单元的编号称为逻辑地址。 一个用高级语言编制的源程序，我们说它存在于由程序员建立的符号名字空间（简称名空间）。 通常，编译程序在对一个源程序编译时，总是从零号单元开始为其分配地址，其它所有地址都是从这个开始地址顺序排下来的，因此，地址空间中的所有地址都是相对于起始地址的，因而称它们为相对地址，所以，逻辑地址也就是相对地址。 2.存储空间：所谓存储空间是指主存中一系列存储信息的物理单元的集合。这些单元的编号称物理地址或绝对地址。因此，存储空间的大小是由主存的实际容量决定的。,4.0.4 几个基本概念,符号指令 数据说明 I/O说明,0 目标 程序 x,0 A 作业J A+x 512K,名空间,地址空间,(作业 J 的源程序),存储空间,装入,编译,简言之，地址空间是逻辑地址的集合；存储空间是物理地址的集合。一个是“虚”的概念，一个是“实”的物体。一个编译好的目标程序存在于它自己的地址空间中，当要它在计算机上运行时，才把它装入存储空间，上图说明一个作业在编译、装入前后存在于不同空间的情况。,关于三个空间的定义可以通过下面的图示来理解。,4.0.4 几个基本概念,4.1 程序的装入和链接,在多道程序环境下，程序要运行必须为之创建进程，而创建进程的第一件事情就是要把用户编写好的源程序和数据装入内存。如何将一个用户源程序变为一个可在内存中执行的程序，通常要经过下列几步： 编译(Compiler)：一般说来，源程序模块是用高级语言(如pascal、fortran、cobol)或汇编语言写的一组程序语句。计算机不能直接执行源语句，它们要首先被编译程序或解释程序翻译成机器级代码。编译程序接受完整的源一级的程序，并以类似于成批的方式生成完整的目标一级的模块。,链接(Linker)：目标模块是纯二进制的机器级代码。计算机可以执行目标级代码，但是典型的目标模块是不完备的，它包含对其它目标模块（诸如存取方法或子例程）的引用。因此，目标模块通常是不能装入计算机并执行的。所以，一些目标模块必须首先链接成一个装入模块，它是能被装入并执行的完备的机器级程序。这个使目标模块链接成装入模块的过程，在IBM系统中是由称为链接编辑程序的系统程序实现的。 装入(Loader)：由装入程序将装入模块装入内存并执行,图 4-1 对用户程序的处理步骤,应用程序,4.1.1 程序的装入,根据存储空间的分配方式，将一个装入模块装入内存时，可采用三种方式： 一、绝对装入方式(Absolute Loading Mode) ：程序员在编程序时，或编译程序（汇编程序）对源程序进行编译（汇编）时，如果知道程序将驻留在内存的具体位置，那么将产生的,是实际存储地址（绝对地址）。但在由程序员直接给出绝对地址时，不仅要求程序员熟悉内存的使用情况，而且一旦程序或数据被修改后，可能要改变程序中的所有地址。因此，通常是宁可在程序中采用符号地址，然后在编译或汇编时，再将这些符号地址转换为绝对地址。如右图所示：,二、可重定位装入方式(Relocation Loading Mode) ：在多道程序环境下，由于事先并不知晓目标程序在内存的具体位置，为了实现静态或动态存储分配策略，需要采用下述两个技术手段： （1）把逻辑地址和物理地址分开； （2）对逻辑地址实施地址重定位。,什么叫重定位：在一般情况下，一个作业在装入时分配到的存储空间和它的地址空间是不一致的。因此，作业在CPU 上运行时，其所要 访问的指令和数据 的实际地址与地址 空间中的相对地址 是不同的。如右图 所示：,显然，如果在作业装入时或在其执行时，不对有关的地址部分加以相应的修改，则将导致错误的结果。 这种由于把一个作业装入到与其地址空间不一致的存储空间所引起的对地址部分调整的过程，称为地址重定位。 实质上，地址重定位是一个地址变换过程，是把作业地址空间中使用的逻辑地址变换成内存空间中的物理地址的过程。这种地址变换就是前面所说的地址映射。 根据对地址变换进行的时间及采用技术手段的不同，把重定位分为静态重定位和动态重定位两类。可重定位装入方式采用的的是静态重定位技术。,静态重定位：是指作业在装入过程中由装配程序进行的地址变换方式。它要求程序本身是可重定位的，即要求编译程序对作业的目标程序中那些要修改的地址部分给出相应的标识。这种重定位之所以称为静态的，是因为地址变换只在作业执行前集中一次完成的。,主要优点：无需增加硬件地址变换机构，因而可在一般计算机上实现。 主要缺点：要求给每个作业分配一个连续的存储区域，且在其整个执行期间必须限定在这个区域内。也就是说，在作业执行期间不能把它移动，因而也就不能实现重新分配主存。这对提高主存的利用率是不利的。 用户必须事先确定所需的存储量，若所需的存储量超过可用存储空间时，用户必须考虑覆盖结构。 用户之间难以共享主存中的同一程序。若要共享一程序，则每个用户应各自使用一个分开的副本。,例：,LOAD 1, 2500 365,三、动态运行时装入方式(Denamle Run-time Loading) ： 采用的的是动态重定位技术。 动态重定位：是指在作业执行过程中，当访问指令或数据时，由附加的地址变换机构进行的地址变换方式。动态重定位是靠硬件地址变换机构实现的。 最简单的办法是利用一个重定位寄存器(RR)。该寄存器的值是由进程调度程序(或另派程序)根据作业分配到的存储空间起始地址来设定的。 在具有这种地址变换机构的计算机系统中，当执行作业时，不是根据CPU给出的有效地址去访问主存，而是将有效地址与重定位寄存器中的内容相加后得到的地址作为访问主存的地址。下图给出了地址变换过程。,0,3456,.,.,.,.,.,.,LOAD A 200,.,.,.,.,.,.,0,100,200,300,.,.,.,.,.,.,.,.,.,LOAD A 200,3456,逻辑地址空间,1100,1200,1300,物理地址空间,由于这种地址变换是在作业执行期间随着每条指令的数据自动地、连续地进行，所以称之为动态重定位。,采用动态重定位技术后，程序中所有指令和数据的实际地址是在运行过程中最后访问的时刻确定的。因此，计算机系统采用了动态存储分配策略。也就是说，在作业运行过程中临时申请分配附加的存储区域或释放已占用的部分存储空间是允许的。,主要优点：主存的使用更加灵活有效。这里，一个用户的作业不一定要分配在一个连续的存储区，因而可以使用较小的分配单位。而且，在作业开始之前也不一定把它的地址空间全部装入主存，而可以在作业执行期间响应请求动态地进行分配。 几个作业共享一程序段的单个副本比较容易。 有可能向用户提供一个比主存的存储空间大得多的地址空间。因而无需用户来考虑覆盖结构，而由系统来负责全部的存储管理。 主要缺点：需要附加硬件支持； 实现存储器管理的软件比较复杂。,4.1.2 程序的链接,链接程序的功能，是将经过编译或汇编后所得到的一组目标模块以及它们所需要的库函数，装配成一个完整的装入模块。实现链接的方法有三种：,一、静态链接： (Static Linking) 事先将几个目标 链接装配成一个装入 模块，以后不再拆开 的链接方式，称为静 态链接方式。如右图：,说明：将几个目标链接装配成一个装入模块时，需解决以下两个问题： 1. 将相对地址进行修改。即将除第一个模块外的相对地址修改成装入模块中的相应的相对地址。 2. 变换外部调用符号。即将每个模块中所用的外部调用符号，都变换为相对地址。 这种先进行链接所形成的一个完整的装入模块，又称为可执行文件。,二、装入时动态链接(Load-Time Dynamic Linking) 用户源程序经编译后所得到的目标模块，是在装入内存时，边装入边链接的。即在装入一个目标模块时，若发生一个外部模块调用，将引起装入程序去找出相应的外部目标模块，并将之装入内存。 装入时动态链接有如下优点： 1. 便于软件版本的修改和更新。只需修改各个目标模块，不必将装入模块拆开，非常方便。 2. 便于实现目标模块共享。即可以将一个目标模块链接到几个应用模块中，从而实现多个应用程序对该模块的共享。,SEQAM,SUBR 1,MAIN,系统目标库,当前生成的目 标 库,私有目标库,MAIN . call SEQAM . call SURB 1 .,查找,引用,读入,查找,引用,装入模块,SEQAM RETURN,SURB 1 RETURN,三、运行时动态链接(Run-Time Dynamic Linking) 采用装入时动态链接方式，虽然可将一个装入模块装入到内存的任何地方，但装入模块的结构是静态的，表现在：1. 进程（程序）在整个执行期间，装入模块是不改变的；2. 每次运行时的装入模块是相同的。并且事先无法知道本次要运行哪些模块，只能将所有可能要运行的模块在装入时全部链接在一起，而实际上往往有些目标模块根本不会运行。 采用运行时动态链接可将某些目标模块的链接推迟到执行时才进行，即在执行过程中，若发现一个被调用模块尚未装入内存时，由OS去找到该模块，将它装入内存，并链接到调用模块上。,4.2 连续分配方式,连续分配是指为 一个用户程序分配一个连续的内存空间。有两种方式： 1. 单一用户（连续区）存储管理： 单用户系统在一段时间内，只有一个进程在内存，故内存分配管理十分简单，内存利用率低。内存分为两个区域，一个供操作系统使用，一个供用户使用. 2. 分区式分配方式： 系统把内存用户区划分为若干分区，分区大小可以相等，也可以不等。一个进程占据一个分区。这是早期用于多道程序的一种较简单的存储管理方式。它又可以分为： 固定分区 动态（可变）分区,4.2.1 单一连续分配,这是最简单的存储器管理，因为操作系统只为一个用户服务。它将内存分为两个区域，即系统区与用户区。如下图所示：,驻留的OS既可放在存储器的低址部分，如图(a)；也可放在存储器的高址部分，如图(b)；甚至可以放在存储器的两端，如图(c)。,1.单道连续区管理,存储管理:连续分配,0000 20KB 100KB 256KB,OS,用户程序 需80KB存储空间,空闲区,一次只能装入一个作业,单一连续分配,（1）系统总是把整个用户区分配给一个用户使用。 （2）实际上，内存用户区又被分为“使用区”和“空闲区”。空闲区被成为”内存碎片“。 （3）由于任何时刻内存储器的用户区中只有一个作业运行，因此这种系统只适用于单用户的情况。,单一连续分区存储管理有如下缺点： （1）由于每次只能有一个作业进入内存，故它不适用于多道程序设计，整个系统的工作效率不高，资源利用率低下。 （2）只要作业比用户区小，那么在用户区里就会形成碎片，造成内存储器资源的浪费。如果用户作业很小，那么这种浪费是巨大的。 （3）若用户作业的相对地址空间比用户区大，那么该作业就无法运行。即大作业无法在小内存上运行。,存储分配只有在实施了存储保护后都有意义。 单用户系统中，存储保护只要求对操作系统区域加以保护。通常，要实施存储保护必须配置相应的硬件机构才可行。但单用户系统中并不配置这种硬件机构，其原因是这些单用户的存储保护问题并不严重，即使操作系统遭到破坏，受影响的只是单个用户所做的工作，而操作系统可以通过系统再启动重新把操作系统装入主存。所以，最多只是用户使用上的不便，却使硬件成本得到降低。 在大多数较新的系统结构中，存储保护是作为综合的地址变换机构的一部分而获得的。但在一些较老的系统中，一般采用简单的硬件以提供有限的保护。下面介绍其中的三种。,1.自动地址修改： 例：设存储器地址空间为12K，操作系统占4K。这样系统可以提供给用户8K(213)的地址空间。,+01000000000000 (4K),得实际要访问的存储地址,若OS占高址端的4K，则：,若OS占低址端的4K，则：,从而实现了对OS的保护。,2. 0页，1页寻址： 是自动地址修改的一种变异。假定操作系统与用户各占存储器的一半，它们的区分可以通过对每个用户生成的地址左端拼接上一位1来实现。如下图动画所示。,1,3. 界限寄存器： 上述两种技术都要求预先确定用户区与系统区的大小。这个条件可以通过使用一界限寄存器或隔离寄存器来消除。 这两个区域相对大小改变时，只要改变这个界限寄存器的值即可。如下图：,界限寄存器,显然，此方法增加了系统开销，因为用户每次存储访问都要作一次比较，而不是象前面那样直接快速的地址修改。,4.2.2 固定分区分配,实现多用户系统的存储器管理，一个最早的想法是：当系统初始化时，把存储空间划分成若干个任意大小的区域；然后，把这些区域分配给每个用户作业。由于这些存储区域是在系统启动时划定的，在用户作业装入及运行过程中，其区域的大小和边界是不能改变的。所以，称这种存储器的划分方式为固定式分区或静态存储区域定义。 固定式分区的划分方法有两种： (1)分区大小相等 (2)分区大小不等,2.多道固定分区管理,存储管理:连续分配,0000 20KB 28KB 44KB 76KB 140KB 256KB,OS,分区大小不等,分区大小相等,0000 20KB 40KB 60KB 80KB 100KB 120KB . 256KB,OS,16KB,8KB,作业1 需14KB,32KB,64KB,作业2 需60KB,116KB,为了实现这种固定分区的分配，系统需要建立一张分区说明表，如右图。这个分区说明表指出可用于分配的分区数以及每个的大小、起始地址及状态。,在调度时作业时，由存储管理根据所需量在分区说明表中找出一个足够大的未分配分区分配给它，然后用重定位装配程序装入之。如果找不到合适的分区，则通知作业调度模块，从作业后备队中另外选择一个作业来装入。,2.多道固定分区管理(续),存储管理:连续分配,需建立固定分区说明表,作业J1 需14KB,内零头(碎片)问题,作业J2 需60KB,作业J1 14KB,作业J2 60KB,作业J1 14KB,作业J2 60KB,物理内存,固定分区分配算法流程图,要求xK大小的分区,取分区说明表的 第一项,该分区空闲吗？,分区大小xK,表结束吗？,返回分区号,状态位置1,无法分配,取下一项,存储空间分配情况,采用这种技术，虽然可以使多个作业共享主存，但仍不能充分利用它。因为，一个作业的大小，只有当作业调度程序在分析进程创建请求时才能确定；而分区的大小是在系统初启时划定的。由于作业的大小不可能刚好等于某个分区的大小，所以，在每个分配的分区中，通常都有一部分未被作业占用而浪费掉。 这种分配给用户而未被利用的部分，称作存储器的“内零头”(InternaI Fragmentation)。 实际上，存储区域的内零头主要取决于采用哪一种分配策略，常用的有首次适应算法和最佳适应算法。这些算法将在下一小节中介绍。 固定分区方式存储管理的优点是分区方法特别简单，实现起来也很容易；缺点是存储空间的利用率太低。现在的操作系统几乎不用它了。,4.2.3 动态分区分配,为了减少存储区域的内零头，进一步提高主存的利用率，使存储空间的划分更加适应不同的作业组合，人们设计了动态（可变）式分区方案。 所谓动态式分区分配是指根据进程的实际需要，动态地为之分配连续的内存空间。即分区的边界可以移动，分区的大小是可变的。动态式分区又有两种不同选择，一种是分区的数目固定大小是可变的，而另一种则允许分区的数目和大小都是可变的。 为了说明它们之间的重要差异，我们考虑一个具有256K字节存储器的系统。,第一种方案：假定系统初始化时规定把存储空间划分为 8个分区。在下图(a)中用问号(?)来表示它们。在系统运行一段时间后，已有192K存储空间分配给7 个作业，剩下64K还未分配，如下图(b)所示。现在，又有两个作业 P和Q准备调入，它们每个需要32K存储空间。显然，我们有足够的存储空间。却没有足够数的存储区域(目前只有一个可用)。因此，只能允许一个作业(如：P)被调入，如下图(c)所示。,第二种方案(分区数可变的分配方案)：。为了便于比较，把相应情况的分配示于图(a)中。最初，没有建立任何分区，整个可用的存储空间用一个问号来表示；之后，发生上述所说在系统运行一段时间后，已有192K存储空间分配给7 个作业，剩下64K还未分配的情况，如图(b)；现在，我们在剩下的64K存储空间中，可以创建两个分区，分别装入作业P和Q，如图(c)。显然，此方案比第一个方案更灵活，内存利用率更高。,3.多道可变分区管理(概念),存储管理:连续分配,内存地址 0000 20KB 256KB,OS,J1 需14KB,J2 需30KB,空闲区,已分配区,J3 需60KB,区大小 14KB 30KB 60KB 132KB,J4 需60KB,J5 需20KB,J1 14KB J2 30KB J3 60KB J4 60KB J5 20KB,外零头(碎片),实现可变式分区分配存储管理，必须解决： 一、分区分配中数据结构 常用的数据结构有： 1. 空闲分区表：,2. 空闲分区链：,二、分区分配算法 系统运行一段时间后，在整个存储空间内将出现许多大小不等的区域，有的仍被作业进程占用，有的则因作业已退出系统而成为可用于再分配的区域。现在假设有一个新的作业需调入主存，如何为其选择一个合适的区域？在这种情况。有四种不同的分配算法，它们是： (1)最佳适应算法(Best Fit) (2)最坏适应算法(First Fit) (3)首次适应算法(Worst Fit) (4)循环首次（下次）适应算法(Next Fit),1.最佳适应算法(Best fit: BF) ：就是为一作业选择分区时总是寻找其大小最接近作业所要求的存储区域。即：把作业放入这样的分区后剩下的零头最小。 优点：如果存储空间中具有正好是所要求大小的存储空白区，则必然被选中；如果不存在这样的空白区，也只对比要求稍大的空白区进行划分，而绝不会去划分一个更大的空白区。因此，其后遇到大作业到来时，作业要求的存储区域就比较容易得到满足。 为了加快查找速度，应将存储空间中所有的空白区按其大小递增的顺序链接起来，组成一空白区链(Free List)。,指针,10k,60k,90k,20k,例：,有四块空白区(从低地址高地址)，来了一个作业需分配19k内存。,解：,缺点：采用最佳适应算法，在每次分配时，总是产生最小的空白区。因此，经过一段时期后，存储空间中可能留许多这样的空白区，由于其太小而无法使用。为了改善这种情况，在该算法中设置一参数G，用它来确定最小分区的大小。当选择一个分区时，如果选中的空白区与要求的大小之差小于G，则不再对它划分，而把整个这个空白区分配给申请的作业。 最佳适应算法的另一缺点是：在回收一个分区时，为了把它插入到空白区链中合适的位置上也颇为费时。所以，这种算法乍看起来是最佳的，其实则不然。,2.最坏适应算法(Worst fit: WF)：与最佳适应算法相反，它在为作业选择存储区域时，总是寻找最大的空白区。在划分后剩下的空白区也是最大的，因而对以后的分配很可能仍然是有用的，这是该算法的一个优点。但是，由于最大的空白块总是首先被分配而进行划分，当有大的作业时，其存储空间的申请往往得不到满足，这是该算法的一个缺点。,为了支持这个算法的实现，空白块应以大小递减的顺序链接起来。,3.首次适应算法(First Fit: FF) ：由上面讨论可见，BF和WF各有其利弊。首次适应算法是对它们进行折衷考虑后设计出来的。这里，每个空白区按其在存储空间中地址递增的顺序链在一起，即每个后继空白区的起始地址总是比前者的大。在为作业分配存储区域时，从这个空白区链的始端开始查找，选择第一个足以满足请求的空白块，而不管它究竟有多大。和上述算法一样，这个选择的空白区被分成两部分。一部分与请求的大小相等，分配给作业；剩下的部分留在空白区链中。显然，这个算法倾向于优先利用存储空间中低址部分的空白区。,例：,有四块空白区(从低地址高地址)，来了一个作业需分配19k内存。,解：,主要优点：算法简单，查找速度快；留在高址部分的大的空白区被划分的机会较少，因而在大作业到来时也比较容易得到满足。 主要缺点：这种算法常常利用一个大的空白区适应小作业的请求，从而留下一些较小的无法用的空白区，存储空间利用率不高；而且，由于所有的请求都是从空白区链的始端开始查找，因而这些小而无用的空白区集中在这个链的前端，相应地，一些较大空白区在链的尾端才能发现，这种情况将使找到合适空白区的速度降低。,4.下次适应算法(Next fit: NF) ：为了克服上述缺点，又设计了一种称为“下次”适应的算法，它实际上是首次适应算法的一种变形，故也被称为带旋转指针的首次适应算法(Next Fit with Roving Pointer)。 为此，我们把存储空间中空白区构成一个循环链。每次为存储请求查找合适的分区时，总是从上次查找结束的地方开始，只要找到一个足够大的空白区，就将它划分后分配出去。显然，采用这一策略后，存储空间的利用更加均衡，而不至于使小的空白区集中于存储器的一端。但是，在存储器的另一端也不可能保留大的空白块，因此，当需要获得相当大的空白区时，能满足的可能性减少了。,关于分配策略的选择：从上面对四种不同分配策略的讨论可知，每个算法各有其优缺点。那么，究竟如何来评价一个分配算法并作出最好的选择呢？ 对分配策略的一种有用的度量是，系统对选定的一组作业来运行，比较第一次发生不能满足存储请求所经历的时间。 然而，遗憾的是，系统开始运行时，对作业请求和释放存储区域的顺序是不知道的，而且，总是可以设计出一个序列，对这些策略中任何一个是最好的。再则，不管选择哪一种算法， 最终将几乎 不可避免地形成许多小的无用的分区，并导致某个作业因不能满足存储要求而被阻塞。,这里，我们把存储空间中这些小的无用的分区称为 “外零头” (Externa1 Fragmentation)。 有人对各种不同的分配策略，广泛地研究了实际系统的行为。 研究表明：就常规应用而言，首次适应算法及最佳适应算法在延缓阻塞方面有着相同的记录。由于首次适应算法实现起来最简单，因而多数系统选用它；但选用下次适应和最佳适应算法的存储管理系统也不少。,三、分区分配操作 涉及动态分区的主要操作有分配内存和回收内存。这些操作是在程序接口中通过系统调用发出的。 1. 分配内存：向操作系统提出一特定存储量的请求。通常，它并不要求这个分配的存储区域限于特定的位置，但是，这个区域必须是连续的。也就是说，操作系统必须确定一个适当的存储区域，使其在请求进程的地址空间中成为可用的，如果无适当的区域可用，进程必须等待，直到该请求能满足为止。,从头开始查表,检索完否？,m.sizeu.size?,m.size-u.sizesize?,从该分区中划出 u.size大小的分区,将该分区分配给请求者 修改有关的数据结构,返回,返回,继续检索下一个表项,将该分区从链中移出,2. 回收内存：回收内存是进程用于归还一个不再需用的存储区域。通常，一 个已分配的分区必须整个地归还。操作系统必须回收进程释放了的存储区域，并使它们在以后供有分配请求时使用。当一个作业终止时，必须回收其未释放的任何空间。 在回收一个分区时，一个回收的分区与空白区邻接的情况有四种，对这四种情况分别作如下处理：,(1)回收区仅与上面的空白区邻接，合并后仍为空白区F1，其起始地址不变，只需改变其大小，并按F1中末端的后向指针值设置在回收区MCB的后向指针域中，同时，修改它的状态位。如图(a),(4)回收区与上、下面的空白区均不邻接，在这种情况下，应为回收区单独建立一新表项，填写回收区的首址和大小，并根据首地址插入到空闲链中的适当位置。,顺序地检索可用资源表直至找到 某表目的m.addaa或m.size=0,不是第一个表目且 与前一可用区相邻？,与后一可 用区相邻？,返回,把所释放的可用区 与前一分区合并,与后一可用区相 邻且不为空表目？,与后一可用区合并,将该表目以上的所 有表目下移一格,所释的可用 区的size=0?,将该表目以上的所有 表目上移一格并插入 新释放的可用区表目,把所释放的可用区 与后一分区合并,4.2.4 可重定位分区分配,一、紧凑 从前面知，可变式分区分配策略是在装入作业时根据其要求量为其划定相应的区域。这种分配策略，消除了固定式分区分配造成的“内零头”，但不可避免地在存储空间中造成“外零头”，为了进一步提高存储器的利用率，必须设法减少由于外零头造成的浪费。 一个最简单而直观的解决零头问题的办法是，定时地或者在内存紧张时，把存储空间中的空白区合并为一个大的连续区。 实现方法是移动某些已分配区中的信息，使所有的作业位于存储器的一端，而把全部空白区留在另一端。这种技术称为存储器的“紧凑”。,把一个作业从一个存储区域移动到另一个存储区域所发生的问题，正如把一个作业装入到与它地址空间不 一致的存储空间所引起的问题一样，需要对作业中的某些地址部分和地址常数等进行调整。,一个较实用且可行的办法是采用动态重定位技术。 一个作业在主存中移动后，只要改变重定位寄存器中的内容即可。,二、动态重定位 （有关动态重定位知识在前面已作了介绍） 动态重定位分区分配策略是实现动态分配及动态存储管理的基础。它允许作业在运行过程中申请附加的存储区域，也可以将不再需要的部分归还给系统。,重定位寄存器 1K,三、动态重定位分区分配算法,请求分配一个大小为xk的分区,有大于xk的 空闲区吗？,空闲区的总和 xk吗？,紧缩存储并相应地修改诸表 (得到一个完整的空闲区xk),分配分区并 修改诸表,此刻已经 无法分配 一个分区,返回一个 分区号数,说明： 1. 动态重定位分区分配法是利用分区的“拼接”(对空白区而言)或“紧凑”(作业程序而言)技术解决“零头”。 2. 问题 拼凑时机的选择,(i)出现相邻空白区即拼接；(或某分区被释放后即紧缩)紧缩工作大，开销大，但管理简单,(ii)存贮不足(空白分区不够大)时进行拼接。紧缩次数少，但管理(算法)较复杂。,4.2.5 对换(Swapping),在早期，为了克服存储空间不足而采取的另一种措施，称为对换技术(Swapping，也称为交换)。广义地说，所谓对换就是把暂时不用的某个(或某些) 程序及其数据的部分或全部从主存移到辅存中去，以便腾出必要的存储空间；接着把指定的程序或数据从辅存读到相应的主存中，并将控制转给它，让其在系统上运行。 这种对换技术，最早用在分时系统UNIX中。在任何时刻，在该系统的主存中只保存一个完整的用户作业，当其运行一段时间后，或由于分配给它的时间片已用完，或由于需要其它资源而等待，系统就把它交换到辅存，同时把另一个作业调入主存让其运行。这样，可以在存储容量不大的小型机上实现分时系统。Microsoft公司的 Windows OS也采用这种对换技术。,如果对换是以整个进程为单位的，称为“整体对换”或“进程对换”，主要用于分时系统中，其目的是用以解决内存紧张问题，并可进一步提高内存利用率。 如果对换是以“页”或“段”为单位的，称为“页面对换”或“分段对换”，统称为“部分对换”。这种对换方法是实现请求式分页及请求式分段存储管理的基础。其目的是为了支持虚拟存储器管理系统。 本节简单介绍进程对换，有关分页对换和分段对换放在后面章节中介绍。 为了实现进程对换，系统需提供以下三个方面的功能： 1 对换空间的管理 2 进程的换出 3 进程的换入,1. 对换空间的管理,在具有对换功能的OS，通常把外存分为文件区和对换区。前者用于存放文件，由于通常的文件都是较长久地驻留在外存上，故对文件区管理的主要目标，是提高文件存储空间的利用率，为此，系统采取离散分配方式。后者则用于存放从内存换出的进程，由于这些进程在对换区中驻留的时间是短暂的，而对换操作又较频繁，故对对换空间管理的主要目标，则是提高进程的换入、换出速度，为此，所应采取的管理策略是用连续分配方式，较少考虑外存中的碎片问题,为了能对交换区中的空闲盘块进行管理，在系统中应配置相应的数据结构，以记录外存的使用情况。其形式与内存在动态分区分配方式中所用数据结构相似，即同样可以用空闲分区表或空闲分区链。在空闲分区表中的每个表目应包含两项，即对换分区首址和对换区长度，它们的基本单位都是盘块。 由于对对换区的分配，是采用连续分配方式，因而对对换区空间的分配与回收，与动态分区方式时内存的分配与回收方法雷同。其分配算法可以是首次适应算法、循环首次适应算法和最佳适应算法。对换区的回收操作也可分为四种情况(见教材P.148.)。对这几种情况的处理方法也与动态分区分配时的方法相同。,2. 进程的换出与换入,当内存执行某些操作而发现内存不足时，便调用对换程序或唤醒对换进程。它们的主要任务是实现进程的换入与换出。 1)进程的换出 在进程换出时，是将内存中的某些进程调至对换区，以腾出内存空间。换出过程分以下两步： a. 选出被换出的进程 首先选择处于阻塞或睡眠状态的进程，当有多个这样的进程时，应选择其优先级最低的进程换出。此外，还应考虑进程在内存的驻留时间。当内存中已无阻塞进程，而现在的空闲内存空间仍不足以满足需要时，便选择优先级最低的就绪进程换出。,2)进程的换入 当对换程序或对换进程去执行换入操作时，便去检查PCB集合中所有进程的状态。从中找出“就绪且换出”状态的进程。当有多个这样的进程时，首先把其中换出时间(必须大于规定时间，如2s)最久的进程作为换入进程，再根据进程的大小为其申请内存，此时可能： 申请成功，直接将进程换入； 申请失败，须先将内存中的某些进程换出，腾出足够的内存后，再将该进程换入。 在对换进程成功地换入一个进程后，若还有可换入的进程，则再继续执行上述的换入过程，将其余处于“就绪且换出”状态的进程陆续换入，直至所有“就绪且换出”状态的进程全部换入，或已无法获得足够大的内存来换入进程，此时对换程序或进程才停止换入工作。,4.3 基本分页存储管理方式,前面介绍的分区存储管理，一般都要求把一个作业的地址空间装入到连续的存储区域内。因此，在动态分区的存储空间中，常常由于存在着一些不足以装入任何作业的小的分区而浪费掉部分存储资源，这就是所谓存储器的零头问题。 尽管采用“紧凑”技术可以解决这个问题，但要为移动大量信息花去不少处理机时间，代价较高。如果我们能取消对其存储区域的连续性要求，必然会进一步提高主存空间的利用率，又无需为移动信息付出代价。存储器的离散分配就是在这个指导思想下设计出来的。根据分配时所用的基本单位的不同，它分为： 1. 分页式存储管理 2. 分段式存储管理 3. 段页式存储管理,4.3.1 页面与页表,一、页面和物理块（存储块） 在分页存储管理系统中，把每个进程的地址空间分成一些大小相等的片，并称之为页面或页(Page)。同样地，把主存的存储空间也分成与页相同大小的片，这些片称为存储块或称为页框(Page Frame)。在为进程分配存储空间时，总是以页框为单位。 例如：一个作业的地址空间有m页。那么，只要分配给它m个页框，每一页分别装入一个页框内即可。这里，并不要求这些页框是连续的。 说明： 从0开始编制页号，页内地址是相对于0编址； 在进程调度时，必须把它的所有页一次装入到主存的页框内；如果当时页框数不足，则该进程必须等待，系统再调度另外的进程。（纯分页方式）,二、页面大小 在分页系统中，页面大小是由机器的地址结构所决定的。对于某一机器只能采用一种大小的页面。 在确定地址结构时，对页面的大小应选择得适当。因为： 若选择的页面较小，一方面可使内存碎片小，并减少了内存碎片的总空间，有利于提高内存利用率；但另一方面，也会使每个进程要求较多的页面，从而导致页表过长，占用大量内存；还会降低页面换进换出的效率。 若选择的页面较大，虽然可减少页表长度，提高换进换出效率，但又会使页内碎片增大。 页面的大小通常在512B4KB选择，但总是2的幂。,三、 地址结构,这样，允许把虚地址(逻辑地址)划分为页号和位移量(页内相对地址)两部分。如图所示。,页号、位移量的划分是由系统自动完成的，对用户是透明的。,P=intA/L W=A mod L,给定一个逻辑地址A，页面大小L，其页号P和位移量W的计算公式如下：,(357101)8(011,101,111,001,000,001)2 (01,110,1111,001,000,001)2,例：设虚地址为(357101)8 每一块为1K字节,块（页）的大小：1K=210,1 6 7 1 1 0 1,位移量为(1101)8, 页号为(167)8,块号由页表指定，位移量在变换过程中不变,四、页表 在分页系统中，存储分配问题变得非常简单，作业的一页可以分配到存储空间中任何一个可用的页框。 现在的问题是：(1)系统怎么知道作业的哪一页分配在存储空间的哪一页框内？作业的地址空间本来是连续的，现在把它分页后并装入到不连续的页框内，如何保证它仍能正确地运行。也就是说，(2)如何实现以及何时实现把作业的逻辑地址变换为主存的物理地址。 一个可行的办法是采用动态重定位技术。在执行每条指令时进行这种地址变换。 现在是以页为单位分配的，故实现地址变换的机构要求为每页设置一个重定位寄存器。这些寄存器组成一个组，通常称为页表。,在实际系统中，为了减少硬件成本，将页表存在被保护的系统区内。在页表中每页有相应的表目，分别指出该页在主存中的页框号。这张页表是在进程装入主存时，由系统根据内存分配情况建立的。 在多道程序系统中，为便于管理和保护，系统为每个装入主存的进程建立一张相应的页表。它的起始地址及大小填入该进程的PCB中。一旦这个进程被调度执行，把它的页表始址及大小装入特定的页表寄存器中。此外，根据每页内容的不同，可以设置不同的存取限制。所以，在这页表的表目中除了包含指向所在页框的指针外，还包括一个存取控制手段，这个表目也称为页描述子。,图 4-11 页表的作用,例1：某采用分页存储管理的系统中，物理地址占20位，逻辑地址中页号占6位，页面大小为1KB，问： 该系统的内存空间大小为多少？每个存储块的大小为多少？逻辑地址共几位？每个作业的最大长度为多少？ 若第0、1、2页分别放在第3、7、9存储块中，则逻辑地址0420H对应的物理地址是多少？,在分页存储管理系统中，根据题意： 物理地址占20位，所以该系统的内存空间大小为：220=1MB 存储块的大小与页面大小相同，而页面大小为1KB，因此存储块的大小为：1KB 由于页面大小为1KB，占10位，而页号占6位， 因此逻辑地址共16位， 从而该系统中的每个作业大小为：216=64KB,法1（全部转换成10进制）： 逻辑地址：0420H=105