计算机存储管理软件论文.docVIP

浙江工业大学浙西分校信电系毕业设计(论文) 提 要本论文是关于计算机存储管理分区的分配算法及其实现。首先介绍了该项目的背景和意义，以及项目中作者使用的原理技术,包括存储管理的原理，分区的分配技术、回收技术。然后详细的分析了对操作系统的存储器的分配的简单算法，以及对其的一个实现，主要是实现可变分区的存储管理的分配、回收技术。可变分区管理通常采用的方法有多种，本设计分别采用最先适应算法和最优适应算法实现。接着是系统的测试运行结果及其优缺点。整个存储管理分区的分配算法及其实现完全是按照操作系统对内存的管理和有效使用进行的,本项目的实现有一定的经济价值和技术价值。关键字： 存储管理；分配；回收- 2 - SUMMARYThe present paper is saves the management district about the computer the assignment algorithm and the realization. First introduced this project background and the significance, as well as in the project the author uses principle technology, Including memory management principle, district assignment technology, recycling technology. Then the detailed analysis to the operating system memory assignment simple algorithm, as well as to an its realization, mainly was the realization invariable district memory management assignment, the recycling technology. The invariable district management usually uses the method has many kinds of, this design uses separately adapts the algorithm and the optimal-adaptive algorithm realization first. Then is the systematic test analysis and its the good and bad points. Entire algorithm and realization of the memory management partition allocation is that defers to that the memory management in the operating system and the valid use completely. This project realization has the certain economic value and the technical value.Key words: Memory Management; Allocation; Recycling目 录提 要- 1 -SUMMARY- 2 -第一章 绪 论- 1 -1.1目的来源及意义- 1 -1.2项目开发的重要环节- 1 -1.3作者的主要工作- 2 -第二章 存储管理的概述- 3 -2.1基本概念- 3 -2.2存储器的层次- 3 -2.3存储管理- 4 -2.3.1存储器管理的主要任务- 4 -2.3.2存储器管理的主要功能- 4 -2.4程序的装入与链接- 4 -2.5存储管理的成就- 8 -2.6固定分区存储管理方式- 9 -2.6.1基本原理- 9 -2.6.2主存空间的分配和回收- 9 -2.6.3地址转换与存储保护- 11 -2.6.5对固定分区存储管理方式的改进- 12 -2.7可变分区存储管理方式- 12 -2.7.1基本原理- 12 -2.7.2主存空间的分配与回收- 12 -2.7.3地址转换与存储保护- 15 -2.7.4管理特点- 16 -2.7.5采用技术- 16 -第三章 存储管理分区分配算法- 18 -3.1程序设计功能- 18 -3.2程序整体设计- 18 -第四章 系统的详细设计- 21 -4.1 acceptment1()最先适应策略的回收算法- 21 -4.2 acceptment1()最优适应策略的回收算法- 23 -4.3 assignment()分配算法- 25 -4.4 backcheck()检查块函数- 27 -4.5 print()输出可利用空间- 29 -第五章 系统测试- 30 -5.1程序的运行结果- 30 -5.2程序的优、缺点- 32 -参考文献- 33 -致 谢- 34 - 第一章 绪 论a) 1.1目的来源及意义冯诺依曼的存储机制要求任何一个程序必须装入内存才能执行，现代计算机系统就是基于这种机制的。在计算机系统中，内存管理在很大程度上影响着这个系统的性能，这使得存储管理成为人们研究操作系统的中心问题之一。现代计算机系统中的存储器通常由内存（Primary Storage）和外存（Secondary Storage）组成。CPU直接存取内存中的指令和数据，内存的访问速度快，但容量小、价格贵；外存不与CPU直接交互，用来存放暂不执行的程序和数据，但可以通过启动相应的I/O设备进行内、外存信息的交换，其访问速度慢，但容量大大超过内存的容量，价格便宜。虽然随着硬件技术和生产水平的迅速发展，内存的成本急速下降，但是，内存容量仍是计算机资源中最为关键且最紧张的资源。因此，对内存的有效管理仍是现代操作系统中十分重要的问题。许多操作系统之间最明显的区别特征之一是所使用的存储管理方法不同。b) 1.2项目开发的重要环节系统中内存的使用一般分为两部分：一部分为系统空间，存放操作系统本身及其相关的系统数据；另一部分为用户空间，存放用户的程序和数据。在单道程序系统中，内存一次只调入一个用户进程，并且该进程可以使用除操作系统占用外的所有内存空间，存储管理就是分配和回收内存区。在多道程序系统中，多个作业可以同时装入内存，因此对存储管理提出了一系列要求：如何有效地将内存分配给多个作业，如何共享和保护内存等，存储管理既要提高存储资源的利用效率，同时又要方便用户使用，因此要求存储管理具有内存空间管理、地址转换、内存扩充、内存共享和保护等功能。1内存空间管理内存空间管理负责记录每个内存单元的使用状态，负责内存的分配和回收。内存分配有静态分配和动态分配两种方式。静态分配不允许作业在运行时再申请内存空间，在目标模块装入内存时就一次性地分配所需的所有空间；而动态分配允许作业在运行时再请求分配加空间，在目标模块装入内存时只分配了作业所需的基本内存空间。采用动态分配方法的系统中，常使用合并自由区的方法，使一个空间尽可能地大。2地址转换程序在装入内存执行时对应一个内存地址，而用户不必关心程序在内存中的实际位置。用户程序一旦编译之后每个目标模块都以0为基地址进行编址，这种地址称为相对地址或逻辑地址，而内存中各个物理存储单元的地址是从统一的基地址顺序编址，次地址又称为绝对地址或物理地址。当内存分配确定后，需要将逻辑地址转换为物理地址，这种转换过程称为地址转换，也叫重定位。3内存扩充内存的容量是受实际存储单元限制的，而运行的程序又不受内存大小的限制，这就需要有效的存储管理技术来实现内存的逻辑扩充。这种扩充不是增加实际的存储单元，而是要通过虚拟存储、覆盖、交换等技术来实现的。内存扩充后，就可执行比内存容量大的多的程序。存储扩充需要考虑放置策略、调入策略和淘汰策略。4内存的共享和保护为了更有效地使用内存空间，要求共享内存。共享是指共享内存中的程序或数量。例如，当两个进程都要调用C编译程序时，操作系统只把一个C编译程序装入内存，让两个进程共享内存中的C编译程序，这样可以减少内存空间占有，提高内存的利用率。再者，内存共享可实现两个同步进程访问内存区。由于多道程序共享内存，每个程度都应有它单独的存储区域，各自运行，互不干扰。当多道程序共享内存空间时，就需要对内存信息进行保护，以保证每个程序在各自的内存空间正常运行；当信息共享时，也要对共享区进行保护，防止任何进程去破坏共享区中的信息。常用的内存保护方法有硬件方法、软件方法和软硬件结合方法。硬件方法包括界地址保护法和存储访问键方法。界地址保护法是为每个进程设置上下界地址。存储访问键法为每一个受保护的存储块分配一个保护键，不同的进程有不同的权限代码，仅当权限代码和存储保护键匹配时才允许访问。c) 1.3作者的主要工作参加此项目计算机存储管理分区的分配算法及其实现的过程中，作者的研发进程是按照设计流程进行的。作者的工作主要是熟悉数据结构、C/C+开发环境、操作系统等，对操作系统的存储管理的分配的简单算法，以及对其的一个实现，最主要是实现可变分区的存储管理的分配和回收技术。- 2 - 第二章 存储管理的概述a) 2.1基本概念CPU能直接存储指令和数据的存储器是内存,也称主存、实存,它的结构和实现方法将很大程度地决定整个计算机系统的性能.内存的大小由系统硬件决定,是实实在在的存储,它的存储容量受到实际存储单元的限制。它是现代计算机系统操作的中心。如图2.1所示，CPU和I/O系统都要和内存打交道。图2.1内存在计算机系统中的地位内存用来存放内核、程序指令和数据，计算机当前要用到的每一项都存放在内存的特定单元中。内存是一个由字或字节构成的大型一维数组，每一个单元都有自己的地址，通过对指定地址单元进行读/写操作来实现对内存的访问。b) 2.2存储器的层次尽管内存的访问速度大大高于外存，但还是不能与高速的CPU相匹配，从而影响了整个系统得处理数度。为此，往往把存储器分为3级，采用高速缓存器来存放CPU近期要用的程序和数据,如图2.2所示。高速缓存器由硬件寄存器构成，其存取速度比内存快，但成本远远高于内存，因此，在一个实际系统中的高速缓存器的容量不会很大。往往把某段程序或数据预先从内存调入高速缓存，CPU直接访问高速缓存，从而减少CPU访问内存的次数，提高系统处理速度。图2.2 3级存储器结构在图2.2所示的3级环存储器结构中，从高速缓存到外存，其容量愈来愈大，如缓存的容量为128KB-256KB，而内存可达到256MB；访问数据的速度则愈来愈慢，价格也愈来愈便宜，如IBM缓存的最大传输速度为每字120ns-225ns，内存的传输速度为每字1us。由于本章主要介绍内存管理，因此，不对缓存作详细介绍。c) 2.3存储管理存储器管理讨论的主要对象是主存，主存是计算机系统的重要资源之一，因为任何程序和数据，以及各种供控制使用的数据结构，都必须占用一定的存储空间，所以，存储器是一种宝贵且紧俏的资源。如何对它们施行有效的管理，不仅直接影响到存储器的利用率，而且对系统性能也有重大影响。i. 2.3.1存储器管理的主要任务存储管理的主要任务是尽可能方便用户和提高主存储器的使用效率，使主存储器在成本、速度和规模之间获得较好的权衡。ii. 2.3.2存储器管理的主要功能1主存空间的分配和回收在多道程序设计环境下，往往有多个程序同时存放在主存中，所以，主存分配的主要任务是采用一定的数据结构，按照一定的算法为每一道程序分配主存空间，使它们“各得其所”，并记录主存空间的使用情况和作业分配情况。主存空间的回收是指当一个作业运行结束后，必须归还所占用的主存空间，即在记录主存空间使用情况的数据结构中进行修改，并且把记录作业分配情况的数据结构删除。2地址转换将用户程序的逻辑地址换为运行时能由机器直接寻址的物理地址的过程称为地址转换，也称为地址映射（即程序装入）。3主存空间的共享保护在多道程序设计的系统中，同时进入主存储器执行的作业可能需要调用相同的程序或数据，这就是主存的共享。在主存的分配和共享时，必须解决各存储区内的信息如何保护的问题。存储保护的工作一般由硬件和软件配合实现。4主存空间的扩充提供虚拟存储器，使用户编写程序时不必考虑主存储器的实际容量，使计算机系统似乎有一个比实际主存储器容量大得多的主存空间。 d) 2.4程序的装入与链接1 源程序的执行过程在多道程序环境下，程序要运行必须为之创建进程，而创建进程的第一件事，就是要将程序和数据装入主存。如何将一个用户源程序变为一个可在主存中执行的程序，通常要经过编译、链接和装入等几个步骤，其控制示意图如下图2.3所示。图2.3 源程序的执行过程 编译：由编译程序将用户源代码编译成若干个目标模块。 链接：由链接程序将编译后形成的目标模块以及它们所需要的库函数链接在一起，形成一个装入模块。 装入：由装入程序将装入模块装入主存。由源程序经过编译、链接产生装入程序代码的工作是由语言编译程序完成的，把装入程序装入主存是由操作系统的装入控制程序完成的。2 程序的链接链接程序的功能是将经过编译或汇编所得到的一组目标模块以及它们所需要的库函数装配成一个完整的装入模块。实现链接的方法有3种：静态链接、装入时动态链接和运动时动态链接。 静态链接。假如有3个经编译后所得到的目标模块A，B，C，它们的长度分别为L，M和N。在模块A中，有一条语句CALL B，用于调用模块B。模块B 中，有一条语句CALL C，用于调用模块C。B和C都属于外部调用符号，在将这几个目标模块链接装配成一个装入模块时，需要解决以下两个问题： 对相应地址进行修改，通常由编译程序产生的所有目标模块，其开始地址都为0，每个模块中地址都是相对于0的。在链接成一个装入程序后，模块B和C的起始址不再是0，而是L和L+M，此时须修改B和C中的相对地址，即模块B中的所有相对地址加上L，模块C中的相对地址都加上L+M。 变换外部调用符号。即将每个模块中所用的外部调用符号都变换为相对地址。例如把B的起始址变换为L；C的起始址变换为L+M，这种先进行链接所形成的一个完整的装入模块，又称为可执行文件。通常都不再拆开它，要运行时刻直接将它装入主存。这种事先进行链接，以后不再拆开的链接方式，称为静态链接方式。 装入时动态链接。用户源程序经编译后所得到的目标模块，是在装入主存时，边装入边链接的。即在装入一个目标模块时，若发生一个外部模块调用，将引起装入程序去找相应的外部目标模块，并将它装入主存，且修改目标模块中的相对地址。装入时动态链接方式有以下优点： 便于软件版本的修改和更新。采用装入时动态链接方式要修改或更新各个目标模块是非常容易的，但对于静态链接已装入模块，如果要修改或更新其中的某个膜表模块时，则要求重新打开装入模块，这不仅是低效的，而且有时是不吭能的。 便于实现目标模块共享。若采用装入时动态链接的方式，操作系统能够将一个目标模块链接到几个应用模块，即实现多个应用程序对该模块的共享，然而，采用静态链接方式时，每个应用模块都必须含有该目标模块的拷贝，而无法实现共享。 运行时动态链接。虽然目前所介绍的动态链接装入方式，可将一个装入模块装入到主存的任何地方，但装入模块的结构式静态的，它主要表现在两个方面：一是在进程(程序)的整个执行期间，装入模块式不改变的；二是每次运行时装入模块都是相同的。实际上，在许多情况下，每次要运行的模块可能是不相同的，但由于事先无法知道本次要运行哪些模块，故只能是将所有可能要运行到的模块，在装入时全部链接在一起，使每次执行时的装入模块是相同的，虽然这是低效的。因为这样，在装入模块的运行过程中，往往会有某些目标模块根本就不运行。比较典型的例子是错误处理模块，如果程序在整个运行过程中，都不出现错误，便不会用到该模块。能有效地改变这种情况的链接方式，是近几年流行起来的运行时动态链接方式。这种链接方式，可将某些目标模块的链接推迟到执行时才进行。即在执行过程中，若发现一个被调用模块尚未装入主存时，又操作系统去找到该模块，将它装入主存，并把它链接到调用者模块上。3 程序的装入将一个装入模块装入主存时，可采用3种方式：绝对装入方式。绝对装入方式是由装入程序根据装入模块中的地址将程序和数据装入主存。在编译时，如果知道程序将驻留在主存的什么位置，那么编译程序将产生绝对地址的目标代码。例如，事先已经知道用户程序(进程)驻留在从R位置开始处，则编译程序所产生的目标代码，便从R开始向上扩展。在此条件下可以采用绝对装入方式。绝对装入程序按照装入模块中的地址，将程序和数据装入主存。装入模块被装入主存后，不须对程序和数据的地址进行修改，程序中所使用的绝对地址，即可在编译或汇编时给出，也可由程序员直接赋予。但由程序员直接给出绝对地址，不仅要求程序员熟悉主存的使用情况，而且一旦程序或数据被修改后(如插入新的或删除老的程序或数据)，可能要改变程序中的所有地址。因此，通常是在程序中采用符号地址，然后再编译或汇编时，将这些符号地址再转换位绝对地址。可重定位方式。可重定位方式是由装入程序根据主存当前的实际使用情况，将装入模块装入到主存适当的地方。在多道程序环境下，由于编译程序不能预知所编译的目标模块在主存的位置，因此，目标模块的起始址通常都是从0开始，程序中的所有其他地址，也都是相对于起始址计算的。因此，不可能再用绝对装入方式，而应该用可重定位装入方式，把装入模块装入主存。可重定位装入程序，根据主存当前的使用情况，将装入模块装入到主存的某个位置。我们向大家介绍一种重定位方式，即静态重定位。它是指用户程序执行之前由重定位装配程序集中一次完成地址映射工作。例如，在确定了相对目标程序装入到以1000开始的主存区域之后，装配程序要把相对目标程序中的所有地址都加上 1000。我们把在装入时对目标程序中的指令和数据地址的修改过程称为重定位。又因为地址交换只是在装入时一次完成，以后不再改变，故称为静态重定位。静态重定位后的程序在其执行过程中是不能随便在主存中移动的。静态重定位有两个主要优点，一是无需增加硬件地址变换机构，二是利用重定位装配程序可对由若干程序段组成的作业进行静态链接，且实现简单。当然，它也存在下面几个缺点，一是由于程序在重定位之后不能在主存中移动了，因此不能根据主存占用情况的变化，调整程序在主存的位置，即不能实现虚拟存储器。(一次性装入，不能改变，若用户所需存储空间超过实际的主存空间，则要考虑覆盖技术)。二是程序的存储空间要求连续，不能把程序分布在若干个不连续的区域内。三是多个用户很难共享主存中的同一程序副本。所以，静态重定位技术只用于要求不高的场合 。如图2.4所示，在用户程序的1000号单元处有一条指令LOAD A， 2500，该指令的功能是将2500号单元中的整数365取至寄存器1。但若将该用户程序装入到主存的10000-15000号单元而不进行地址变换，则在执行1100号单元中的上述指令时，它将仍从2500号单元中把数据取至寄存器1，导致数据出错。由图2.4可看出，正确的方法应该是该指令从12500号单元中取出数据。为此，应将取数指令中的地址2500修改成12500，即把有效地址(相对地址)与本程序在主存中的起始址相加，才得到正确的物理地址。故除了数据地址应该修改之外，指令地址同样也需要修改。图2.4 作业装入主存时的情况动态运行时装入方式。绝对装入方式只能将装入模块装入到主存事先指定的位置。在多道程序环境下，不可能事先知道每一道程序在主存中的位置。因此，这种装入方式只能用于单道程序。可重定位装入方式，可将装入模块装入到主存中任何允许的位置，故可用于多道程序环境；然而，它不允许运行中的程序在主存中移动位置。因为，程序在主存中移动，意味着它们的物理地址都要发生变化，因此，必须对程序和数据的地址(是绝对地址)进行修改，才能正常运行。然而，实际情况是程序在主存中的位置，可能经常要改变，例如，在具有对换功能的系统中，一个进程有可能被多次换出，又多次被换入，每次换入后的位置与换出前的位置通常是不相同的，在这种情况下，就应该采用运行时的装入方式。动态运行时的装入程序，在把装入模块装入主存后，并不立即把装入模块中的相应地址转换为绝对地址，而是把这种地址转换推迟到程序要真正执行时才进行。因此，装入主存后的所有地址都仍是相对地址，为使地址转换不影响指令的执行速度，这种方式需要一定特殊硬件的支持，我们称之为动态重定位。即，在程序执行过程中，在CPU访问贮存之前将被访问的程序和数据地址转换成主存地址。动态重定位依靠硬件地址变换机构完成。动态重定位也有很多明显的特点，其优点：一是，可以对主存进行非连续分配。从原理上讲，只需增加几个基本地址寄存器，每个及地址寄存器对应一段程序即可。这样一来主存使用更加灵活、有效。二是，提供了实现虚拟存储器的基础。因为动态重定位可部分地、动态地分配主存，所以它可以在执行期间采用请求方式为那些不在主存中的程序段分配主存，以达到主存扩充的目的，即为用户提供一个比主存的存储空间大得多的虚拟空间。三是，有利于程序段的共享。其缺点：一是，动态重定位技术所付出的代价是需要硬件支持，增加成本。二是，实现存储管理的软件算法比较复杂。e) 2.5存储管理的成就用户需要一个计算环境，以支持组件编译和灵活使用数据。系统管理员需要高效率和有序地存储分配控制机制。为了满足这些要求，操作系统有如下5条存储管理原则： 进程隔离。操作系统必须防止独立进程之间的相互干扰。 自动分配和管理。程序应该能够在动态条件下分配到所要求的存储区。这个过程对程序员是透明的。这样，程序员就不必关心存储区的限制，由操作系统根据任务的需求分配存储器，其效率也随之得到提高。 支持组件编程。存储器共享使得一个程序具有对另一程序的存储空间进行寻址的潜在可能性。有时这是需要的，有时这对绝大多数程序甚至操作系统本身构成极大威胁。 长时间存储。很多用户和应用程序要求长时间存储信息。 保护和存取空间。通常，操作系统用虚拟存储器(Virtual Memory)和文件系统来满足这些需要。虚拟存储器允许程序以逻辑方法来寻址，而不用考虑物理上可获得的内存大小。当一个程序执行时，事实上，只有一部分程序和数据可以保存在内存中，其他部分则存储在磁盘上。这种将存储空间分为物理空间和逻辑空间的方法，在存储数据方面为操作系统提供了强大的支持。文件系统将信息存储在称为文件的一个命名的对象中，实现长期存储。文件是一格对程序员很方便的概念，对操作系统而言文件又是存取控制和保护的单元。图2.5描述了对存储系统的两种看法。从用户的角度出发，处理器同操作系统一起为用户提供了一个“虚拟处理器(Virtual Processor)”，它访问虚拟存储空间。这种存储可以使线性地址空间或以各段的集合(段式可用长度的连续地址块)。不论是哪种情况，编程指令都可以对虚拟内存中的程序和数据进行访问。进程分隔可以通过给每个进程一个惟一的、不可重叠的虚拟内存空间来实现。进程共享则可以通过将两个虚拟存储空间重叠来获得。文件存储在存储介质上，而且可以被复制到虚拟内存中。从设计者的角度来看存储器，存储器由可直接寻址内存和通过将数据块加载到内存来间接访问的辅存组成。地址转换硬件映射器(Mapper)位于处理器和存储器之间。程序用虚拟地址进行访问，虚拟地址映射到实际的内存地址。如果一个访问并不在实际内存中，那么实际内存中的一块内容就会被交换到辅存，从而可将一个需要的数据块交换进内存。在这个进程中，产生这个地址访问的进程将被挂起。(a) 用户观点(b) 操作系统设计者观点图2.5 看待存储系统的两种不同观点f) 2.6固定分区存储管理方式当主存较大且作业较小时，但用户存储管理方式对主存空间的浪费太大。那么如何让主存可以同时装入多个作业呢？这就产生了两种可用于多道程序的存储管理方式。即固定分区存储管理方式和可变分区存储管理方式。本节主要介绍固定分区存储管理方式的基本原理、主存的分配与回收、地址转换与存储保护，以及它的管理特点。i. 2.6.1基本原理固定分区存储管理方式是最早使用的一种可运行多道程序的存储管理方式。它要求把作业全部装入主存，且装入一个连续的主存空间。在这种管理方式下，把主存中可分配的用户区域先划分成若干个固定大小的区域，每一个区域成为一个分区，每个分区中可以装入一个作业，一个作业也只能装入一个分区中，这样可以装入多个作业，使它们并发执行。当有一个空闲分区时，便可从外存的后备队列中，选择一个适当大小的作业装入该分区；当该作业运行完时，又可以从后备队列中选择另一格作业转入该分区。可用下述两种方法将主存空间划分为若干个固定大小的分区。 分区大小相等。使所有的主存分区都大小相等，其缺点是明显的。即，当程序太小时，会造成主存空间的浪费；当程序太大时，可能因分区的大小不足以装入该程序，而使该程序无法运行。尽管如此，这种令所有分区大小都相等的划分方式仍被采用，它主要用于一台计算机控制多个相同对象的场合，因为这些对象所需的主存空间是大小相等的。例如，炉温控制系统是利用一台计算机去控制多台相同的冶炼炉。 分区大小不等。为了克服分区大小相等分配方法的缺点，可在主存中划分出多个较大的分区，适量的中等分区及少量的大分区。对于小程序，可为之分配小分区；这样，当大、中程序到来时，就可以找到大的分区，将程序装入主存并运行。ii. 2.6.2主存空间的分配和回收1 采用的数据结构在固定分区存储管理方式下，为了记录各个分区的基本情况和使用情况，方便主存空间的分配和回收操作，设置了一张分区分配表。分区分配表的内容包括分区序号、起始址、大小、状态。状态栏的值为“0”表示分区空闲，可以装入作业；当装入作业后，其值改为作业名，表示这个分区被该作业占有。如表2.1所示，第0分区已被作业J1占用，第1分区空闲。表2.1 分区分配表序号始址大小状态010001000J1120005000因为在作业装入之前，主存中的分区大小和个数已经确定，也就是说分区分配表的记录个数是确定的，所以，分区分配表一般采用顺序存储方式，即用数组存储。2 主存空间的分配在作业分配之前，根据主存分区的划分情况，在分区分配表中填入每个分区的始址、大小，在状态中一律填入“0”，表示该分区可用，当作业装入时，填入作业名。当有作业申请主存空间时，主存空间的分配步骤为：从作业队列中取出队首作业，检查分区分配表，选择状态标志为“0”的分区，并将作业地址空间的大小与状态标志为“0”的分区的大小进行比较，但所有分区长度都不能容纳该作业时，则该作业暂时不能装入，显示主存不足的信息。当某一个分区长度能容纳该作业时，则把作业装入该分区，且把作业名填到该分区的状态栏里，然后，主存分配下一个作业。主存分配流程如图2.6所示。图2.6 固定分区存储管理的主存分配流程图3 主存空间的回收当作业运行结束时，根据作业名到分区分配表中进行检查，从状态栏的记录可知该作业占用的分区，把该分区的状态标志置成“0”，表示该分区空闲，可以用来装入新的作业。iii. 2.6.3地址转换与存储保护1 地址转换由于作业在执行时不会改变分区的个数和大小，所以地址转换采用静态重定位方式，即在作业被装入主存时。一次性地完成地址转换。采用这种管理方式时，处理器设置两个寄存器：下限寄存器和上限寄存器。下限寄存器用来存放分区的低地址，即起始址；上限寄存器用来存放分区的高地址，即末地址。一般情况下这两个寄存器的内容是随着处理作业的不同而改变的，它们从分区分配表中获取该分区的起始址和末地址(等于起始址+分区大小-1)。地址转换过程是：CPU获得的逻辑地址首先与下限寄存器的值相加，产生物理地址；然后与上限寄存器的值比较，若大于上限寄存器的值，产生“地址越界”中断信号，由相应的中断处理程序处理；若不大于界寄存器的值，则该物理地址就是合法地址，它对应于主存中的一个存储单元。地址转换过程如图2.7所示。图2.7 固定分区的地址转换2 存储保护系统设置了一对寄存器，称为“下限寄存器”和“上限寄存器”记录当前在CPU中运行的作业在主存存储器中的下限和上限地址。当处理机执行该作业的指令时必须核对表达式“下限地址=绝对地址=上限地址”是否成立。若成立，就执行该指令，否则就产生“地址越界”中断信号，停止执行该指令。运行的作业在让出处理器时，调度程序选择另一个可运行的作业，同时修改当前运行作业的分区号和下限、上限寄存器的内容，以保证处理器能控制作业在所在的分区内正常运行。2.6.4管理特点采用固定分区存储管理方式有以下特点： 一个作业只能装入一个分区，不能装入两个或多个相邻的分区。一个分区只能装入一个作业，当分区大小不能满足作业的要求时，该作业暂时不能装入。 通过对“分区分配表”的改写，来实现主存的分配与回收。作业在执行时，不会改变存储区域，所以采用静态地址重定位方式易于实现，且系统开销小。 当分区较大作业较小时，仍然浪费许多主存空间，并且分区总数固定，限制了并发执行的作业数目。iv. 2.6.5对固定分区存储管理方式的改进一个分区只能装入一个作业，分区的其他部分闲置不用，降低了主存的利用率。可采用下列算法提高主存的利用率： 根据经常出现的作业的大小和数量来划分分区，尽可能地使各个分区充分利用。 划分分区时按分区的大小顺序排列，低地址部分是较小的分区，高地址部分是较大的分区。各分区按从小到大的顺序登记在分区表中。 按作业对主存的需求量排成多个作业队列，一个作业队列对应一个分区互不借用。g) 2.7可变分区存储管理方式由于固定分区存储管理方式的分区大小是固定的，对于作业容易造成许多主存空间的浪费。为了让分区的大小与作业的大小相一致，可以采用可变分区存储管理方式。可变分区存储管理方式又称为动态分区存储管理方式，它是根据用户作业的大小，动态地对主存进行划分。可变分区存储管理方式较之固定分区存储管理方式显著地提高了主存空间的利用率。本节主要介绍的是可变分区存储管理方式的基本原理、主存空间的分配与回收、地址转换与存储保护，以及它的管理特点。i. 2.7.1基本原理可变分区存储管理方式是在作业要求装入主存时，根据作业的大小动态地划分分区，使分区的大小正好适合作业的要求。各分区的大小是不定的，主存中分区的数目也是不定的。可变分区存储管理方式必须解决3个问题：一是分区分配中所用的数据结构，二是分区的分配算法，三是分区的分配和回收。ii. 2.7.2主存空间的分配与回收1 采用的数据结构为了实现分区分配，系统中必须配置相应的数据结构，用来记录主存的使用情况，包括空闲分区的情况和使用分区的情况，为作业分配主存空间提供依据。为此，设置了两个表，即已分分区表和空闲分区表，如表2.2和表2.3所示。表2.2 已分分区表 表2.3 空闲分区表 已分分区表。记录主存中已经分配作业分区的情况，包括分区序号、起始址、大小和状态(作业名)。 空闲分区表。记录主存中空闲分区的情况，包括空闲分区序号、起始址和大小。为了便于处理，一般情况下空闲分区表中的空闲分区记录以地址递增的顺序排列。因为已分分区表和空闲分区表中记录的个数是随着主存的分配和回收而变化的，所以这两个表一般采用链表的形式存储，链表中的数据域记录相关的信息。2 主存空间的分配采用可变分区存储管理方式分配主存时，先从小地址分配，再分配大地址。空闲分区表中记录的排列也是从小地址向大地址排列的。首次分配时，只有一个空闲区。分配的区被收回后，还可以分给其他作业。分给其他作业时。该分区被分成两部分，一部分被作业占据，另一部分又成为一个较小的分区。当小到一定程度时，全部分给该作业。主存的分配过程如下：首先初始化已分分区表(0个记录)和空闲分区表(1个记录)，整个用户区为一个空闲区，在空闲分区表中填入用户区的始址和大小。其次，从作业队列中取出队首作业，在空闲分区表中找一个不小于作业的空闲区，装入作业，在已分分区表中增加一个记录，填上作业所占分区的序号、始址、大小、作业名，并修改空闲分区表相应记录的始址和大小；若找不到一个空闲区，则显示主存不足的信息，删除该作业或把作业放到队尾，等待大的空闲区。然后，再分配下一个作业，直到所有作业分配完毕。主存空间的分配流程如图2.8所示。3 常用的主存分配算法 最先适应分配算法(FF)。最先适应分配算法对空闲分区表记录的要求是按地址递增的顺序排列的，每次分配时，总是从第1条记录开始顺序查找空闲分区表，找到第一个能满足作业长度要求的空闲区，分割这个空闲区，一部分分配给作业，另一部分仍为空闲区。它的特点：一是分配算法简单；二是容易产生多的小地址碎片；三是降低了主存空间利用率。我们还可以对此算法进行修改，采用循环最先适应算法。循环最先适应算法对空闲分区表记录的要求仍然是按地址递增的顺序排列。每次分配时是从上次分配的空闲区的下一条记录开始顺序查找空闲区表，最后一条记录不能满足要求时，再从第1条记录开始比较，找到第一个能满足作业长度要求的空闲区，分割这个空闲区，装入作业。否则，作业不能装入。 最优适应分配算法(BF)。最优适应分配算法是按作业要求从所有的空闲分区中挑选一个能满足作业要求的最小空闲区，这样可保证不去分割一个更大的区域，使装入大作业时比较容易等到满足。为实现这种算法，把空闲区按长度递增次序登记在空闲区表中，分配时，顺序查找。它的特点：一是解决了大作业的分配问题；二是容易产生不可利用的空闲区，降低了主存空间的利用率；三是收回主存时，要按长度递增顺序插入到空闲区表中。图2.8 可变分区管理的主存分配流程图 最坏适应分配算法(WF)。最坏适应分配算法每次分配主存时总是挑选一个最大的空闲区，分割一部分给作业使用，使剩下的部分不至于太小，仍可供使用。为实现这种算法，把空闲区按长度递减次序登记在空闲区表中，分配时，顺序查找。它的特点：一是不会产生过多的碎片；二是影响大作业的分配；三是收回主存时，要按长度递减的顺序插入到空闲区表中。从搜索速度和回收过程上看：最先适应分配算法(FF)具有最佳性能；在空间利用上，最先适应分配算法(FF)比最优适应分配算法(BF)好，最优使用分配算法(BF)又比最坏适应分配算法(WF)好；最优适应分配算法(BF)找到的空闲区是最佳的，但在某些情况下，不一定能提高主存的利用率。最先适应分配算法(FF