计算机存储和管理文件方法,计算机存储管理

用户作业要进入主存才能运行。由作业管理部分可知，用户作业被调度后以作业进程形式出现。作业进程“驻留主存”是指它的正文段、数据段等至少已有了部分主存空间，这段主存空间是作业控制进程为它申请的。作业运行时又可为自己申请附加主存空间或为子孙进程申请主存空间。因此，进程是向系统申请主存的基本单位。计算机系统的主存是一种有限资源，却能满足多道作业的众多进程对主存的要求，其关键在于有效的存储管理。

存储管理是指主存管理(外存管理见文件系统)，包括给进程分配主存片段，收回进程释放的主存片段，为分配出去的主存片段提供保护与共享，以及为作业提供一个虚拟的存储空间。

3.1 物理主存

物理主存简称主存，它是计算机系统中的存储装置。个人计算机上通常都配有8MB的RAM，大型计算机上的主存容量更大。8MB (或更大)

的主存除了操作系统代码占用一部分(Windows

95占用高地址段，而UNIX系统V占用低地址段)外，余者皆为用户区域，由用户进程瓜分。

3.2 虚拟概念与虚拟管理

虚拟存储器(虚存)是一个很重要的概念。众所周知，程序段经编译后形成一个以0地址开始的线性地址或多维地址(常见二维地址)序列。用户作业可能由若干个程序段组成，必须经过链接才能产生一个可执行文件。链接工作的实质是按照各个程序段之间的调用关系把各段的地址统一成从0开始的一维线性地址。链接既可在作业运行之前，也可在作业的程序段执行过程中依调用关系动态地进行。前者称为静态链接，由link程序完成；后者称为动态链接，由硬件与特定的软件协同完成。一个可执行文件，第1条指令的地址是0，第2条指令的地址是1，…，依此类推，每条指令所访问的“数据”的地址要么落在指令地址范围内，要么落在数据地址范围内。从0开始的指令地址和数据段地址组成作业的地址空间，它是逻辑上的，与主存地址毫不相干，因此称为虚拟空间或虚拟存储器。每个作业都拥有自己的虚拟存储器(虚存)。虚存的容量与主存大小无关，它是由计算机系统的地址结构和寻址方式确定的。例如，Windows

95提供了4GB的虚存(比8MB的物理主存大得多)，如下一页图(含OS/2的虚存)所示。

一个作业的地址空间等于它的各个进程空间之和，作业运行之前，它的各进程都存放在虚存中。

Windows 95提供了对虚存空间管理的API(Application Program

Interface)应用程序接口函数，这些API函数包括：

①支持私用堆。即应用程序可根据需要创建和使用尽可能多的私用堆；

②允许进程保留虚空间中的指定区域。这一区域一旦被保留，就不能将它用来满足其他进程的动态申请。在多线程(有关线程概念见第4章)环境下，指向这种保留区域的32位指针可使每个线程轻而易举地实现对同一物理主存区域的访问；

③通过存储映射文件支持共享虚存。

(a) OS/2的虚存　　　(b) Win 32的虚存

图 应用程序看到的虚存

Windows

API控制进程的虚拟地址空间，这就意味着进程发出的任何存储请求只会影响虚空间，对物理主存毫无影响。例如，进程请求100KB(每虚页为4KB)，那么系统会给该进程增加25个虚页，但不会对物理主存做任何事情。如果对25个虚页的某些页从未被引用，那么系统可能永远不会分配物理存储块(每块也是4KB)给它们。深入到Windows

95系统内部便可发现许多存储管理原语，有些原语供设备驱动程序使用，另一些供那些有时处理虚存并且有时强迫系统保存物理主存块的系统组件使用。但是，这些原语是操作系统内核所特有的。无论应用程序还是Windows子系统都不知道或不关心物理主存。进程只有实际使用主存时才能迫使系统分配物理主存。Windows把存储器分成虚存和物理主存是其系统的主要特征。应用程序使用API而Windows子系统解释与加工指定的API，操作系统内核则处理虚存到物理主存之间的变换。例如，用C语言作为编程语言来扫描一遍二维数据数组将导致从低到高的虚拟地址都被访问，因为C语言是按照行优先顺序来保存二维数组的。随着扫描的进行，一次1个字节的访问会导致系统每隔4096个引用就会再分配1个新的物理主存块。其它语言，例如FORTRAN，是采用列优先顺序来保存二维数组的，一行行的引用数组数据会导致出现大范围的地址跨越，从而迫使物理主存块的分配频率增高导致应用程序的性能变差。因此，尽管程序员不必为虚存到主存的映射担心，但了解一些系统原语和硬件的工作过程是大有好处的。

3.3 地址变换

物理主存空间地址是一维线性排列的，不妨记作

M={0,1,2,…,2m-1},

表示主存容量为2m。例如，当m=23时，主存的容量为8MB。虚存的一维线性空间和二维线性空间分别记为：

V1={0,1,2,…,2v-1}

V2={0段{0,1,2,…,n0},1段{0,1,2,…,n1},…，s段{0,1,2,…,ns}}。

显然，V1的容量为2v，例如当v=32时，虚存的容量达最大4GB，它限定每个用户作业的进程空间都不得超过4GB。支持V1系统的地址结构寄存器的长度为v位，它存放虚地址(俗称CPU的有效地址)。V2的容量是各段容量之和，对于V2可经静态链接转化成V1，也可采用动态链接。每个用户作业都有一个虚存V(虚地址都从0开始递增)导致虚存的个数多于实际物理主存的个数

(通常计算机只有一个主存M)。所谓地址变换(又称地址映射)就是把多个V空间映射到M空间上去，或者说是把虚存地址变换成物理主存地址。有人不明白为什么要进行地址变换。在多道环境下，一道作业的进程空间所在主存中的位置要依据当时主存的状况而定。因此，尽管它们有永不改变的虚地址却常常有不同的主存地址，不进行地址变换是不行的。

3.4 进程全部驻留主存

全部进程都能进驻主存，其管理方法主要有固定分区、可变分区、页式、段式。

3.4.1

固定分区　　固定分区原理比较简单，本节仅以举例方式说明其原理(如下图)。主存(指用户区域，下同)被分成8KB、32KB、64KB三个分区(在不产生混淆的情况下，KB,

MB, GB简称为K, M,

G，下同)，这种划分在系统整个运行期间是固定不变的。装入模块是作业调度程序的一个子模块，它把多个进程空间按其大小装入到合适的分区内。例如装入模块可把PS1、PS2、PS3分派到分区2、分区1、分区3。尽管分区2有12K空闲，分区3有31K空闲，却不能把后继的PS4(10K)装入主存。于是形成了2个大的“区内零头”。这是固定分区分配的最大缺点。它的主要优点是简单，特别对于进程空间大小可事先知道的专用系统，比较实用。

由于进程空间(PS)的虚地址是从0开始递增编址的，因此装入模块在把它装入到分区时，必须把所有虚地址变换成从分区始址为起点的物理地址，其变换公式是：

物理地址=虚地址+分区的始址

图 固定分区原理图

1、静态重定位(static address relocation)

在进程执行之前完成的地址变换为静态重定位(static address

relocation)，它不需要硬件支持。应该注意到，当PS作为一个整体占用连续的主存空间时，采用静态重定位比较恰当。当某个PS从主存的一个区域移动到另一个区域时，原先计算的物理地址不再有效，应当再次进行地址变换，其变换公式是

新物理地址=原区物理地址-原区始址+新区始址

虽然这是从物理地址到新物理地址的变换，仍然称为静态重定位。

2、动态重定位(dynamic address relocation)

装入模块在把某个PS装入到分区时，也可不做静态重定位，推迟到进程执行时再做虚地址到物理地址的变换，这叫做动态重定位(dynamic

address

relocation)，其过程如下图。当执行虚址100号指令时，CPU给出的有效地址先保存在地址寄存器VR中，其值500，然后加上基址寄存器BR的1000得物理地址MA=1500，最后从主存的1500号地址中取到数据送入1号累加器。由此可得到地址变换公式为

MA=(VR)+(BR)

图 动态重定位过程示意图

上述地址变换公式的计算需要硬件支持，增加了硬件费用。动态重定位花在地址变换上的时间比静态重定位少得多。进程空间在主存内移动时，对动态重定位不增加任何时间开销，而且对于不被访问的虚地址不花费地址变换时间。

3、固定分区的保护

固定分区的保护是指各进程空间在主存内运行时保证其每个物理地址都不超越自己的上下界限。2种保护法(见右图)。

对上下界保护法满足

(UR)≤物理地址

对基址/限长保护法满足

(BR)≤物理地址

计算机硬件负责核查上述限制。如果满足则属合法访问；否则属非法访问。硬件捕获到非法访问后产生越界中断。这是一种高优先级的中断，操作系统的中断处理程序立即强制该进程停止执行并报告有关信息。显然，即使有非法访问出现，也绝不会破坏其它分区。

3.4.2.可变分区　　可变分区管理不是事先把主存空间一次划定，而是在系统运行过程中，根据进程空间的实际大小按需分配主存空间。当进程释放其所占用的空间时，尽可能将那些较小的自由空间合并成较大的空间。在这种管理方法下，主存分区的个数，各区域的大小，在主存内活动的进程个数等都是随时间而变化的。所以，可变分区又称为动态分区。

1、数据结构

有2种数据结构，即自由区表FBT(Free Block Table)和自由区链FBC(Free Block

Chain)供可变分区管理选用。例如设主存空间有如上图2(d)所示的分配现状，则可用FBT或FBC描述之(如右图)。

FBT相当简单，每个表目记录自由区的大小及其起始地址。由于自由区的个数是动态改变的，因此FBT表目的最大个数难以确定：太小了会担心产生表目溢出，太大了会产生表目空间的浪费。不过此表目所占bit位不多，浪费不算严重。FBC的特点是，从自由区本身的首尾分别取出一个字用于成链。首字的两个字段分别记录本自由区的长度和下一自由区的始址，尾字的一个字段记录前一自由区的始址，这样构成了双向链表。链中的第1个自由区的始址和最末自由区的始址分别由FREE结点的始端指针和尾端指针给出。FREE的当前指针指向即将被查找的、循环链中的自由区。FBC的设计技巧在于，它利用自由区本身的空间记录自由区的大小及前后自由区的位置。当分配一自由区时，用于成链的首尾两字也一起连同分配，这样就不再需用额外的存储空间来记录自由区现状。

2、分区分配方法　　FBT和FBC是等价的，下面以FBC为基础，介绍分区分配算法。在FBC上，有3种分区分配算法：

(1)首次适应法(First Fit)

每次分配时总是顺自由区查找，找到第1个能满足长度要求的自由区，从中截取所需空间，剩下的部分留在自由区中。这种算法通常要求自由区链按自由区始址从小到大的顺序排序，分配空间时尽量利用低地址部分的存储区域，而使高地址部分保持较大的自由区，有利于大进程空间的装入。

(2)最佳适应法(Best Fit)

是从自由区链中挑选能满足申请长度的最小自由区。这样可保证不去分割一个更大的自由区，以便当申请大的进程空间时比较容易得到满足。采用这种分配算法时须把自由区按其长度从小到大排序，查找时总是从最小的自由区开始，直到找到满足要求的自由区为止。如果找出的自由区长度恰好等于申请的长度则是最合适的了，如果比申请的长度略大则分割后剩下的自由区就很小，以致不但不能被再度使用，而且还白白占用自由区链表的一个结点。当FBC中小自由区结点过多时，本算法的性能急剧下降。

(3)最坏适应法(Worst Fit)

总是挑选最大的自由区分割给申请者，这样可使剩下的区域不致太小，还可供下次使用。由于过多的分割大的自由区，当遇到较大空间申请时，无法满足其申请的可能性较大。本算法对中、小作业比较有利。为了节省在自由区链表上的查找时间，通常把自由区按其长度从大到小排序，每次查找从链头开始。

评价一个分配算法的良优看其时间、空间复杂性。就算法本身来说，它们的复杂性由排序(按地址大小或按自由区的大小)和查找(查找所需要的自由区)两项决定。上述3种算法都要求排序，这一点总是相同的，所以它们的差别仅在查找上。显然，最坏适应法查找最快，因为它只要在大的方向上考查第1个自由区便可知道此次是否可分配。首次适应算法查找速度比最佳适应法快。3种算法的空间复杂性方面，根据D.E.knuth的仿真实验表明，首次适应算法第一，最佳法算法第二，最坏适应算法第三。因此在实际系统中，首次适应算法的改进型(循环首次适应算法，即每次查找都从FREE的当前指针开始，如前述FBC结构)用得较多。最坏适应算法也常见(Hewlett

Packard 3000/MPE IV操作系统)。

3、分配/回收程序与优先级考虑　　PROCEDURE get_block(x, p);

BEGIN

i:=1;

WHILE (FBC[i].size<>0) AND

(FBC[i].size

i:=i+1;

IF FBC[i].size=0 THEN p:=0

ELSE BEGIN

p:=FBC[i].adder;

y:=FBC[i].size-x;

IF y>=d THEN BEGIN

FBC[i].size:=y;

FBC[i].adder:=FBC[i].adder+x:

END

END

END

回收过程(free_block)是分配过程(get_block)的逆操作。在回收时要考虑回收的自由区是否与原自由区邻接。邻接有4种情况，如下图所示，除(a)外，在其他3种情况下都应把回收区与原自由区合并构成一个更大的自由区。回收后要调整FBC。

上述程序中x是所申请自由区的长度，p作为向申请者返回的、所分得自由区的始址(指针)。若p为空，说明该次申请失败。程序中的d为一个是否要构成新自由区的参量。若剩余量大于d，则剩余部分构成一个新自由区并登记在FBC中，否则剩余部分作为原自由区的一部分一并分配给申请者。这种做法保证自由区链中最小自由区长度不小于d。

以首次适应算法和FBC结构为例，请求大小为x的自由存储区分配程序如下：

(a)不邻接 (b)上邻 (c)下邻接 (d)上下邻接

图 自由区邻接情况

get_block和free_block执行时的优先级不同。进程使用get_block时总是希望立即得到所需存储空间(延迟分配将迫使申请进程挂起)，因此，get_block算法越快，系统的性能越好。这一点提醒用户，应当在使用自由区之前早一点安排get_block请求；提醒操作系统设计者要研制快速get_block算法并且给予它以高的优先级以便尽快得到CPU响应。free_block执行得慢一点对调用进程的继续运行来说并无大碍，所以它常以较低的优先级运行，甚至可以拖延到CPU有空闲时才执行回收操作。Hewlett_Packard的MPE

IV操作系统在最佳适应算法中就是这么做的。不过这样做时要注意一种情况，即当用户进程是多CPU(cpu-bound)时，因free_block执行的机会过少而导致自由区链中的自由区紧缺，应采取措施“特提”free_block的优先级一段时间以便充实自由区链表。

如果get_block申请失败，一种办法是移动(又称紧凑)已在主存中的信息从而使分散的小自由区(碎片)汇集成大块的自由区。移动虽可汇集主存碎片，但时间开销很大，而且不是任何时候都可对主存信息进行移动的(例如，当正与外设交换数据的进程空间是不能移动的)。另一种办法是系统把申请进程挂起等待一段时间后再说。在等待期间申请者不消耗任何系统资源且系统可以做其他工作或许能回收大量自由区。显然，后一种方法较好。

4、地址变换与保护　　可变分区管理采用动态重定位完成虚地址到物理地址的变换；基址/限长保护法(如下图)保证：当有越界事件产生时，当前指令不会去访问本分区之外的主存。

图 地址变换

5、分区共享　　只要2个进程空间包含相同的虚地址(如Windows

95)，物理主存分区即被2进程所共享。同理，允许多进程共享分区。

3.4.3.页式管理　　固定分区管理存在“区内零头”，可变分区管理存在一些难以使用的小自由区(移动的代价太大)，被称为“外零头”。由于内外零头的存在，主存的利用率不高。其根本原因是它们都把进程空间作为不可分割的整体申请一个整区的主存空间，固定分区是“整体”小于固定长度的“整区”而产生内零头，可变分区是

“整区”大于“整体”而产生外零头。既然“整”字作怪，为何不“化整为零”呢？也就是说，把进程空间划分成较小的片段(称为页面)，把主存也划分成较小的片段(称为块)，使页长等于块长，恰好1页能占用主存的1块。申请者申请若干页，分配者分给等量的块，纵然有零头，也不过平均浪费半块而已。这就是页式管理的基本想法。如下图，进程空间被分成3个页面，主存分成8块。进程空间分得的主存块可以是不连续的，但一页必须整个地装入一个整块。当进程空间的最后页面不满时(图中的第2页只有半页)仍分配1整块，其不满部分构成“页内零头”。在页式管理下，作业的进程空间必须在作业运行前一次性全部装入主存块中。

1、数据结构　　实施页式管理要建立以下表格：

①虚空间表,记录系统中进程空间的情况，全系统仅此1张；

②页表(PT)，记录进程空间页面与主存块的对应关系以及有关该页的其他属性；

③空闲块表，记录主存当前的空闲块，整个系统1张。下图给出虚空间表与各进程页表的关系。虚空间表的长度为系统最大进程数的个数，若某个进程被终止，则空出1个表目，由状态位表示为未分配。图中打勾表示已分配，–表示空表目。页表中的块号字段指明该页被分配的主存块号。页号是连续的，它所占有的块号未必连续。全部页表集中存放在主存的系统专用区中，只有系统有权访问页表，以保证安全。

虚空间表与各页表的关系

下图给出主存空闲块表的3种数据结构，主存分块表(MBT)共有n个表项，每个表项记录主存块的当前情况(设主存共分成N块)，状态位为0表示该块空闲(未分)，为1表示该块已分给某进程(由进程号指明)的某页面(由页号指明)，为打勾表示该块处于等待传输完成状态。附在MBT后面的变量n记录当前空闲块的总数，初启时，等于N。位示图表示当前主存中空闲块的情况：1个bit位对应1个主存块，主存共有N块，故有N个bit位。如果该块已分配则bit位置1，未分配则置0，没有第3种状态标记。空闲块链是单向链，利用空闲块本身的单元记录链长(空闲块总块数)和下一个空闲块的主存地址。这种数据结构同分区管理中的自由区链是类似的。可通过头指针head从链上顺次摘下若干空闲块，所以空闲块的分配算法不耗查找时间。回收时把空闲块插入head之后即可。3种数据结构中，空闲块链用得最多。MBT记录的信息多，在页面置换时有用。位示图用得少。

主存空闲块表的数据结构

2、主存块的分配与回收　　在页式管理中，主存空间的分配与回收比分区管理中的更简单。下面给出MBT数据结构上的分配算法。

PROCEDURE cmalloc(x, p);

BEGIN

K:=éx/Block_sizeù;

IF N>=K THEN

BEGIN

p:=get a PT; // 申请一个页表区

FOR i=1 TO K DO PT[i]:=get a free block

END // 申请一个空闲块，把块号添入页表

ELSE p:=0 // 分配失败，返回零

END.

其中x为进程所申请的主存空间大小，p为指向页表的指针。回收算法留给读者。

3、地址变换和保护措施

地址变换　　在页式管理下，CPU给出的有效地址(虚地址)被分成2部分，即页号p和页内位移量w。由p值找到本进程页表的表项序号，从该序号中取出主存块号B，然后把B和w拼成物理地址如图。图中，控制寄存器总是保存现行进程的页表始址与页表长度。每当进程切换时更新控制寄存器，每个进程的页表始址和页表长度由虚空间表提供。有效地址寄存器的内容是CPU给出的虚地址，页号p所占的比特位数可以与物理地址中表示块号B所占的比特位数不等，但虚地址中页内位移w所占的比特位数必然等于物理地址中的块内位移所占的比特位数，因为页长等于块长。请注意，尽管CPU给出的有效地址被分成p和w，但对用户、对CPU本身来说都是透明的。因此，虚地址是一维的，不要误认为二维。

图 页式地址变换

机器

地址位数

页号位数

页内位移数

IBMB70

24

13或12

11或12

Windows95

32

20(含页表目录位)

12

OS/2

32

20(含页表目录位)

12

UNIX系统V

32

32

9

图 若干机器虚地址划分的例子

保护措施　　页表长度:

作用是防止页号p越界。若p值不大于“页表长度”是合法的，否则越界中断，这是最常用的页面保护措施。在页表中增设页面访问权限字段也是一种好的保护措施，请求页式中有详细介绍。

存储保护键:　　给每个存储块都分配一个单独的保护健(相当于一把锁)，并在程序状态字(PSW)中设置保护健字段，对不同的作业赋予不同的代码(相当于一把钥匙)

当钥匙和锁相配时，读、写均允许；当钥匙和锁不配时，则由存取控制决定是否允许访问。

当作业运行过程中产生不正确的访问时，系统将发出保护性中断讯号。

由于I/O通道访问主存不经过页表，所以存储建保护对I/O通道是十分有用的。

图 存储键保护法

4、性能研究　　在页式管理下，每次访问主存都要增加1次访问页表的操作，显然，指令执行的时间拖长。为了克服这一缺点，通常在CPU和主存之间增设高速小型的联想寄存器组，称之为“快表”，用它存放现行进程页表中最近常用的部分表目。这样，在地址变换时本来要访问主存中的页表变为绝大多数情况下访问快表。由于快表的读写速度高，且是关联查找，所以通常能在机器时钟的一个节拍内按页号找到块号。快表是硬件对页式管理最有力的支持，其结构如图所示。设置快表后访问主存的流程如下：

① CPU给出虚地址

② 按p值联查快表，若找到块号B则转④否则转③

③ 按p值找页表得号B，把p指向的页表表目读入快表，置换“旧表目”

④ 由B、w形成物理地址

⑤ 访问主存

⑥ 结束本次访问

图 快表的使用

从上面的步骤③可以看出页表表目是在访问主存的过程中按需要动态地被装入快表的。当进程交替时，快表旧内容被清除并把新现行进程的当前页面所对应的块号装入块表，然后，在访问主存的过程中逐步地将现行进程的页表表目装入快表。

快表的使用要说明的是快表应有几个表目？试验表明，快表的表目个数为8～16即可；各有如下的命中率(指一次主存访问先在快表中找到块号的概率)：

快表表目数

命中率

8

85%

12

93%

16

97%

5、页面共享　　同分区管理类似，只要2个以上(含2个，下同)的进程空间包括相同的虚地址(OS/2，Windows

95的虚存管理API都能做到这一点)，就能实现对该虚地址上的页面共享。应当特别注意的是，这里指的“2个以上进程”可能是同一作业的，也可能不是同一作业的。对于前者，指定相同的虚空间比较容易；对于后者，通常指多个作业共享系统的例程，操作系统负责把被共享例程的各个页面附接到各共享进程空间的初始部分如下图所示，其实就是使各共享进程包含相同的虚地址。之所以这么做是由于页式管理要求虚空间必须连续(静态链接的结果)。

图 共享例程的页面