第3章 操作系统基本原理

操作系统是计算机系统中最重要、最基本的系统软件，它位于硬件和用户之间，一方面能向用户提供接口，方便用户使用计算机；另一方面能管理计算机软硬件资源，以便合理充分地利用它们。从资源管理的角度来看，它是计算机系统中的资源管理器，负责对系统的软硬件资源实施有效的控制和管理，提高系统资源的利用率；从方便用户使用的角度来看，操作系统是一台虚拟机，它是计算机硬件的酋次扩充，隐藏了硬件操作细节，使用户与硬件细节隔离，从而方便了用户的使用。

3.1 操作系统概述

操作系统是控制和管理计算机软硬件资源，以尽可能合理、有效的方法组织多个用户共享多种资源的程序集合。它具有并发性、共享性、虚拟性和不确定性等特点，一般的操作系统都具有处理机管理、存储器管理、设备管理、文件管理和用户接口等5 种主要功能。
（1）处理机管理
（2）存储器管理
（3）设备管理
（4）文件管理
（5）用户接口

3.1.1 操作系统的类型

（1）单用户操作系统
单用户操作系统的基木特征是在一台处理机上只能支持一个用户程序的运行，系统的全部资源都提供给该用户使用。目前，多数微机上运行的操作系统都属于单用户操作系统。
（2）批处理系统
批处理系统也称为作业处理系统。在批处理系统中，作业成批地装入计算机中，由操作系统在计算机的输入井将其组织好，按一定的算法选择其中的一个或多个作业，将其调入内存并使其运行。运行结束后，把结果放入磁盘输出井，由计算机统一输出后交给用户。
（3）分时操作系统
为了解决批处理系统无法进行人机交互的问题，并使多个用户能同时通过自己的终端以交互方式使用计算机，共享主机中的资源，为此，系统中采用了分时技术，即把C P U的时间划分成很短的时间片，轮流地分配给各个终端作业使用。这种操作系统就称为分时操作系统，简称为分时系统。
（4）网络操作系统
网络操作系统是指在计算机网络环境下，具有网络功能的操作系统。计箅机网络是一个数据通信系统，它把地理上分散的计算机和终端设备连接起来，达到数据通信和资源共享的目的。网络操作系统最主要的特点是网络中各种资源的共享，以及各台计算机之间的通信。有关数据通信与计算机网络方面的详细知识，将在第 4 章中介绍。
（5）分布式操作系统
分布式系统是由多台计算机组成的系统，系统中若干台汁算机可以相互合作，共同完成同一个任务。在分布式系统中，任意两台计算机之间都p丨以利用通信来交换信息，系统中的资源为所有用户共亨。分布式系统的优点是各节点的自治性好、资源共亨的透明性强、各节点具有协同性，其主要缺点是系统状态不精确、控制机构复杂、通信开销会引起性能的下降。
（6）嵌入式操作系统
嵌入式操作系统运行在嵌入式智能芯片环境中，对整个智能芯片和它所操作、控制的各种部件装置等资源进行统一协调、处理、指挥和控制。嵌入式操作系统具有微型化、可定制、实时性、可靠性、易移植性等特点。嵌入式实时操作系统是指系统能及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。嵌入式实时操作系统的特点是及时性、支持多道程序设计、高可靠性和较强的过载防护能力。

3.1.2 操作系统的结构

1.整体结构

整休结构也称为模块组合结构或无序结构，是基于结构化程序设计的一种软件设计方法，其主要设计思想和步骤如下：
（1）把模块作为操作系统的基本单位，按照功能将整个系统分解为若干个模块，每个模块具有一定的独立功能，若干个关联模块协作完成某个功能；明确各个模块之间的接口关系，各个模块之间可以不加控制地自由调用（无序调用法)；模块之间需要传递参数或返回结果时，其个数和方式也可以根据需要随意约定。
（2）分别设计、编码、调试各个模块。
（3）将所有模块连结成一个完整的系统。
这种结构设计方法的主要优点体现在以下三个方面：
（1）结构紧密、组合方便，对不同环境和用户的不同需求，可以组合不同模块来予以满足，因此，灵活性大。
（2）针对某个功能可用最有效的算法和任意调用的其他模块中的过程来实现，因此，系统效率较高。
（3）由于划分模块和子模块，设计及编码可齐头并进，能加快操作系统研制过程。

2.层次结构

层次结构是将操作系统划分为内核和若干模块（或进程），这些模块按功能的调用次序排列成若干层次，各层之间只能是单向依赖或单向调用关系，即低层为髙层服务，高层可以调用低层的功能，反之则不能。这样，不但系统结构清晰，而且不构成循环调用。层次结构可以有全序和半序之分。如果每层中的各模块之间保持独立，互相没有联系，则这种层次结构就称为全序；如果某碑层内的模块之间允许有相互调用或通信的关系，则这种层次结构就称为半序。

在层次结构中，外层功能是内层功能的扩充或延伸，内层功能为外层提供了支撑和基础。因此，整个系统中的接口比其他结构方式的接口要少且简单。整个系统的正确性可通过各层的正确性来保证，从而使系统的正确性大大提高。层次结构的另一个优点是增加、修改或替换一个层次不会影响其他层次，有利于系统的维护和扩展。然而，层次结构是分层单向依赖的，必须要建立模块间的通信机制，系统花费在通信上的开销较大，系统效率有所降低。

3.客户/服务器结构

现代操作系统大多拥有两种工作状态，分别是核心态和用户态。一般应用程序工作在用户态，而内核模块和最基本的操作系统核心工作在核心态。

客户/服务器结构也称为微内核结构。操作系统的一个发展趋势是将传统的操作系统代码放置到更高层，从操作系统中去掉尽可能多的东西，而只留下一个最小的核心，称之为微内核。通常的方法是将大多数操作系统功能由在用户态运行的服务器进程来实现。为了获取某项服务，用户进程（客户进程）将请求发送给一个服务器进程，服务器进程完成此操作后，把结果返回给用户进程。这样，服务器以用户进程的形式运行，而不是运行在核心态。因此，它们不能直接访问硬件，某个服务器的崩溃不会导致整个系统的崩溃。客户/服务器结构的另一个优点是它更适用于分布式系统。

微内核技术的主要优点如下：
（1）统一的接口，在用户态和核心态之间无需进程识别
（2）可伸缩性好，能适应硬件更新和应用变化
（3）可移植性好，所有与具体及其特征相关的代码，全部隔离在微内核中，如果操作系统要移植到不同的硬件平台上，只需修改微内核中极少代码即可。
（4）实时性好，微内核可以方便地支持实时处理
（5）安全可靠性高，微内核将安全性作为系统内部特征来进行设计，对外仅使用少量应用编程接口
（6）支持分布式系统，支持多处理器的体系结构和高度并行的应用程序

4.面向对象结构

随着计算机的发展，面向对象技术得到了广泛的重视和应用， 由于其具有数据隐藏和消息激活对象等功能，被广泛应用于操作系统的设计和实现中， 特别是在网络操作系统和分布式操作系统中。面向对象的操作系统中的对象是操作系统管理的信息和资源的抽象， 可以被视为受保护的信息或资源的总称。它拥有自己的状态和存储空间， 而且其状态(也就是存储内容) 只能由事先定义好的操作来改变， 而改变这些对象状态的操作又需要其他对象发送相应的消息后才能被启动， 因此， 容易采取某种手段对其对象实施保护。例如， Windows Server中有执行体对象 (进程、线程、文件和令牌等) 和内核对象 (时钟、事件和信号等)。

3.2 进程管理

进程是一个具有独立功能的程序关于数据集合的一次可以并发执行的运行活动，是系统进行资源分配和调度的基本单位。相对于程序， 进程是动态的概念， 而程序是静态的概念， 是指令的集合。进程具有动态性和并发性， 需要一定的资源(例如， CPU时间、内存、文件和 I/O 设备等) 来完成其任务， 这些资源在创建进程或执行时被分配。在大多数操作系统中， 进程是进行资源分配和调度的基本单位。
一个进程是通过其物理实体被感知的， 进程的物理实体又称为进程的静态描述， 通常由三部分组成, 分别是程序、数据集合和进程控制块 (Process Control Block, PCB)。程序描述了进程所要完成的功能，数据集合描述了程序运行所需要的数据部分和工作区，PCB包括进程的描述信息、控制信息和资源信息， 是进程动态特性的集中反映。程序和数据集合是进程存在的物质基础， 是进程的实体； PCB是进程存在的标志， 进程与PCB是一对一的关系， 操作系统利用PCB对并发执行的进程进行控制和管理。

3.2.1 进程的状态

一个进程从创建而产生至撤销而消亡的整个生命期间， 有时占有处理器执行， 有时虽可运行但分不到处理器， 有时虽有空闲处理器但因等待某个事件的发生而无法执行，这一切都说明进程和程序不相同， 它是活动的且有状态变化的。

1. 三态模型

进程具有三种最基本的状态， 分别是运行、就绪和阻塞， 如图3-1所示。

2.五态模型

由于进程的不断创建， 系统资源特别是内存资源已不能满足所有进程运行的要求。这时就必须将某些进程挂起， 放到磁盘对换区， 暂时不参加调度， 以均衡负载。进程挂起的原因可能是系统出现故障， 或者是用户调试程序， 也可能是需要检查问题。图 3-2是具有挂起状态的进程状态及其转换。

3.2.2 信号量与PV操作

1.信号量

信号量是操作系统中的一种同步机制，用于控制和协调多个进程或线程之间的交互。它可以被看作是一个计数器，用来表示可用资源的数量。

信号量主要有两种操作：P操作（尝试获取资源）和V操作（归还资源）。当一个进程需要使用某个资源时，它会执行P操作，如果信号量的值大于零，那么这个进程就能获得资源，信号量的值减一。如果信号量的当前值为零，那么这个尝试就会失败，进程会被挂起，直到有其他进程执行V操作，将信号量的值加一，使得该进程能够继续执行。

2.实现互斥模型

互斥模型是操作系统中一种用于实现进程或线程互斥访问共享资源的模型。互斥是指在某段时间内只允许一个进程或线程访问共享资源，以避免两个或多个进程或同一个进程的不同线程同时对共享资源进行修改，从而保证数据的一致性和正确性。

互斥模型通常通过使用互斥量（Mutex）或信号量（Semaphore）等同步工具来实现。在互斥模型中，当一个进程或线程需要访问共享资源时，它首先会尝试获取互斥量。如果互斥量已经被其他进程或线程占用，那么这个进程或线程就会被挂起（也就是睡眠），等待其他进程或线程释放互斥量。一旦互斥量被释放，这个进程或线程即可访问共享资源，执行相关操作。在完成操作后，它会释放互斥量，以便其他进程或线程能够访问该资源。

互斥资源的方式可以有效地保护共享资源，避免出现数据竞争等问题，保证系统的稳定性和可靠性。

3.实现同步模型

实现同步模型的含义是指在计算机科学中，同步是指让多个线程或进程按照一定的顺序执行某些操作，以保证这些操作按照正确的顺序完成。同步模型可以确保多个线程或进程之间的协作和数据共享，从而提高程序的效率和可靠性。

同步模型通常涉及到一些同步工具，例如互斥锁（Mutex）、信号量（Semaphore）、条件变量（Condition Variable）等。这些同步工具可以帮助我们实现线程或进程之间的协调和同步，确保它们按照正确的顺序执行某些操作，从而避免数据竞争和其他并发问题。

在同步模型中，我们通常需要考虑以下几个方面：

1. 互斥：确保同一时刻只有一个线程或进程能够访问共享资源，以防止多个线程同时修改共享资源导致的数据竞争问题。
2. 同步：确保多个线程或进程按照正确的顺序执行某些操作，以保证这些操作最终按照正确的顺序完成。
3. 顺序：确保多个线程或进程的执行顺序遵循某些特定的顺序，以满足某些特定的业务需求。

总之，实现同步模型可以确保程序的正确性和效率，避免并发问题导致的程序崩溃或其他异常情况。

3.2.3 死锁问题

死锁问题是指两个或者多个进程在执行过程中意外陷入一种互相等待的状态，这种状态下，各个进程都持有对方所需资源，无法继续执行下去。如果没有外力介入，这些进程将一直处于等待状态，从而导致系统整体效率降低，甚至陷入死机。

死锁的必要条件包括以下四个条件：

1）互斥条件：指多个进程同时访问某一个共享资源时，只有一个进程能够访问，其他进程必须等待。
2）占有并等待条件：指进程已经获得某一个资源，但又请求获得另一个资源，而此时又有另一个进程占有该资源，请求释放的进程必须等待。同时，占有该资源的进程也无法继续执行下去，陷入了死锁状态。
3）不剥夺条件：指进程在执行过程中非经允许不能被剥夺已获得的资源。
4）循环等待条件：指系统中存在一个进程循环等待的资源链。

因此，为了避免死锁问题的发生，我们需要采取一些预防措施，例如避免进程占有所有资源、避免进程循环等待资源等。同时，我们也可以使用一些同步工具来实现进程间的协调和同步。

1.死锁预防

死锁预防是操作系统中防止死锁的一种策略，它的核心思想是破坏死锁的四个必要条件：互斥条件、占有并等待条件、不剥夺条件和环路等待条件。下面分别介绍如何破坏这四个条件。

1. 破坏互斥条件：允许多个进程同时使用资源，只要资源总数足够多，这样就打破了互斥条件，从而避免死锁。
2. 破坏占有并等待：允许进程在获得某资源的同时，又去请求其他资源，从而打破占有并等待条件。
3. 破坏不剥夺条件：当进程请求的资源已被其他进程占有时，允许该进程强制剥夺占有该资源的其他进程的资源，从而打破不剥夺条件。这通常需要操作系统提供一个资源剥夺机制，以便在资源不足的情况下，剥夺占有资源的进程释放资源。
4. 破坏环路条件：通过设置资源的分配顺序，使得进程在分配资源时，总是按照一个确定的顺序来分配资源，从而打破环路等待条件，避免死锁。例如，可以将资源按照一个固定的顺序分配给进程，或者采用先来先服务（FCFS）的方式来分配资源。

需要注意的是，虽然通过破坏死锁的必要条件可以预防死锁，但这种预防方法也可能会带来其他问题，如资源竞争、系统效率下降等。因此，在实际应用中，需要根据具体情况来权衡使用。

2.死锁避免

死锁避免是一种用于预防死锁的策略。它通过设计系统的操作和资源分配方式，使系统在运行过程中不会发生死锁。

银行家算法是死锁避免的一种具体实现方法，它的核心思路是通过分配资源的方式来避免死锁。具体来说，银行家算法是在分配资源时对资源的需求进行估计，并根据估计的资源需求来决定是否分配资源。
银行家算法的基本思想可以总结为以下几点：

1. 系统中的资源必须足够多，以便在分配资源时不会出现系统资源不足的情况。
2. 在分配资源前，需要对资源的需求情况进行估计，并确定是否可以分配资源。
3. 如果分配资源后，系统中的资源不足，则需要重新分配资源。
4. 如果分配的资源超过了系统的资源需求，则需要重新调整资源分配，以避免系统资源浪费。

银行家具体的实现方法包括以下几个方面：

1. 在分配资源之前，需要对资源需求进行估计，以确定是否可以分配该资源。
2. 如果可以分配该资源，则需要对该资源进行标记，以便后续使用。
3. 在分配完资源后，需要对系统资源的使用情况进行监控，以确保系统资源的使用效率和安全性。
4. 如果发现系统资源使用效率低下或出现死锁等问题，则需要重新进行资源分配，并采取相应的措施来解决问题。

需要说明的是，银行家算法虽然可以有效地避免死锁，但它也有一些缺点和限制。例如，它需要预先分配大量的资源，可能会导致系统资源浪费；同时，它的效率也较低，可能会导致资源分配的效率降低。因此，在具体应用中需要根据实际情况来权衡使用银行家算法或其他资源管理策略。

3.死锁检测和解除

死锁检测是指通过一定的算法和机制，实时检测系统中是否存在死锁，并及时给出相应的处理方式，以避免死锁的发生和扩大。

死锁恢复方法：
资源剥夺法：当系统检测到处于死锁状态时，就剥夺部分资源，使被死锁的进程释放已获取的资源，并按照一定的顺序重新分配资源，从而解除死锁。
进程撤销法：当系统发现有死锁时，撤销部分进程，释放被占用的资源，然后按照一定的规则重新分配资源，以避免死结。
进程回退法：让被死锁的部分进程回滚，撤销已执行的操作，释放被占用资源，然后按照系统分配策略重新分配资源，使系统恢复到正常状态。

3.2.4 线程管理

1.线程的实现方式

线程基本上不拥有系统资源，只拥有在运行中必不可少的资源，例如，线程状态、 寄存器上下文和栈等，它可与同属一个进程的其他线程共享进程所拥有的全部资源。线 程也有就绪、阻塞和执行等基本状态，一个线程可以创建和撤销另一个线程；同一个进 程中的多个线程之间可以并发执行。由于线程之间的相互制约，致使线程在运行中也呈 现出间断性。

线程实现方式主要有以下三种：
（1）内核线程。内核线程依赖子操作系统内核，由内核的内部需求进行创建和撤销。一个线程发起系统调用而阻塞，不会影响其他线程。系统将C P U 时间片分配给各线程， 所以，多线程的进程可以获得更多的C P U 时间。
（2） 用户线程。用户线程不依赖于操作系统内核，进程利用线程库提供创建、同步、 调度和管理线程的函数来控制用户线程。调度由应用软件内部进行，通常采用非抢先式或更简单的规则，无需在用户态和核心态之间切换，因此，速度特别快。如果某个线程因系统调用而阻塞，则整个进程需要等待。系统将C P U 时间片分配给进程，所以，多线 程时每个线程就慢。
（3） 轻权进程。轻权进程是操作系统内核支持的用户线程。一个进程可有一个或多个轻权进程，每个轻权进程由一个单独的内核线程来支持。

2.与进程的比较

线程和进程是操作系统中两种不同的执行单元，它们之间存在一些区别和联系。

区别：

1. 创建和销毁：进程是一个独立的运行环境，每个进程都有自己的内存空间，可以被创建和销毁。而线程是进程中的一部分，它们共享进程的内存空间，因此线程之间的创建和销毁是相互独立的。
2. 资源占用：一个进程中可以包含多个不同的线程，这些线程可以共享资源，如文件、网络连接等。而每个进程只能拥有自己的内存空间和其他系统资源，因此进程之间是相互独立的。
3. 并发性：进程具有较高的并发性，可以同时执行多个任务。而线程是进程内的并发单元，它们之间的并发性相对较低。

联系：

1. 资源共享：线程共享进程的内存空间和其他系统资源，因此可以实现资源的共享和复用。
2. 调度和管理：操作系统对进程和线程的调度和管理是相似的，都需要考虑优先级、调度算法等因素。
3. 编程模型：线程和进程的编程模型相似，都涉及到线程的创建、调度、同步、异常处理等方面的知识。

总的来说，线程和进程都是操作系统中的执行单元，它们之间存在一定的联系和区别。在编写多线程程序时，需要充分考虑线程和进程的特性，合理选择线程或进程，以达到最佳的性能和资源利用率。

3.多线程模型

许多操作系统都提供用户和内核线程支持，从而有不同的多线程模型。
（1）多对一模型。多对一模型将多个用户线程映射到一个内核线程。 线程管理是在用户空间进行的，因此效率比较髙。但是，如果一个线程执行了阻塞系统 调用，那么整个进程就会阻塞。而且，因为任一时刻只有一个线程能够访问内核，多个线程不能并行运行在多处理器上。
（2）一对一模型。一对一模型将每个用户线程映射到一个内核线程。 该模型在一个线程执行阻塞系统调用时，能允许另一个线程继续执行，所以，它提供了比多对一模型更好的并发功能，它也允许多个线程能并行地运行在多处理器上。这种模型的主要缺点是每创建一个用户线程，都需要一个相应的内核线程。由于创建内核线程的幵销会影响到应用程序的性能，所以，这种模型的大多数实现限制了系统所支持的线程数量。
（3）多对多模型。多对多模型复用了许多用户线程到N 样数量或更小数量的内核线 程上。内核线程的数量可能与特定应用程序或特定机器有关，位于多处理器上的应用程序可比单处理器上的应用程序分配更多数景的内核线程。
虽然多对一模型允许开发人员随意创建任意多的用户线程，但是，由于内核只能一次调度一个线程，所以并不能增加并发性。一对一模型提供了更大的并发性，但是开发人员必须小心，不要在应用程序内创建太多的线程。多对多模型没有这两者的缺点，开 发人员可创建任意多的必要的用户线程，并且相应内核线程能在多处理器上并行执行。另外，当一个线程执行系统调用阻塞时，内核能调度另一个线程来执行。

3.3 内存管理

由于任何程序和数据都必须占用内存空间后才能执行，因此，内存管理的优劣直接影响系统的性能。尽管现代计算机中内存容量不断增大，但仍不能保证有足够的空间来支持大型应用程序和数据的使用，因此，操作系统的任务之一是尽吋能地方便用户使用和提高内存的利用效率。此外，有效的内存管理也是多道程序设计系统的关键支撑。具体来说，内存管理的功能主要包括以下几个方面：
（1）内存空间的分配与回收。
（2）配合硬件进行地址转换工作，把用户使用的逻辑地址转换成处理器能访问的物 理地址。
（3）内存空间的共享与保护，使得若干个进程能够同时访问公共程序所占的内存区， 同时，能够防止多个程序在执行中互相千扰，并保护区域内的信息不被破坏。
（4）当内存容M 不足时，操作系统要采取某种措施，在不改变实际内存容量的前提下，借助于大弈量的外存来解决内存不够用的问题。

3.3.1 地址变换

用户作业的程序通常用高级语言编写，称为源程序。但源程序是不能被计算机直接执行的，需要通过编译程序或汇编程序编译获得目标程序。H 标程序的地址不是内存的实际地址，一般将用户目标程序使用的地址单元称为逻辑地址（也称为相对地址或虚拟地址)，逻辑地址-?般以0 为基地址进行编址，是程序经过编译或汇编后形成的目标模块或装配连接程序的地址编码。一个用户作业的目标程序的逻辑地址集合称为该作业的逻辑地址空间。作业的逻辑地址空间可以是一维的，这时逻辑地址限制在从0 开始顺序排列的地址空间内；也可以是二维的，这时整个用户作业被分成若干段，每段有不同的段号，段内地址从0 开始。

当程序运行时，它将被装入内存地址空间的某些部分，此时程序和数据的实际地址一般不可能与原来的逻辑地址一致，将内存中的实际存储单元称为物理地址（也称为绝对地址或实际地址）。物理地址的总体构成了用户程序实际运行的物理地址空间（也称为存储空间），它是由存储器地址总线扫描出来的空间，其大小取决于实际安装的内存容量 。

为了保证程序的正确运行，必须将程序和数据的逻辑地址转换为物理地址，这一工作称为地址转换或重定位。一般情况下，一个作业在装入内存时分配到的存储空间和它的地址空间是不一致的。在装入作业或执行时，若不对有关地址加以修改，将导致错误的结果。因此，需要将程序中的地址调整成与所装入的内存空间相一致，有关地址部分 的调整过程就是地址重定位的过程。重定位公式表示为：

物理地址 = 起始的物理地址+逻辑地址

例如，一个作业被装入到从1000开始的内存区域中，则该作业的物理地址为其逻辑地址值加上1000。

地址转换通常有两种方式，分别是静态重定位和动态重定位。
静态重定位是指在作业装入时由作业装入程序（装配程序）实现地址转换。这种方式要求目标程序使用相对地址，地址变换在作业执行前一次性完成。静态重定位的特点是容易实现，无需增加硬件地址变换机构，当操作系统为程序分配一个内存区域后，只需将程序中的指令或操作数的逻辑地址加上分配内存区的起始地址就得到了物理地址。但它要求为每个程序分配一个连续的存储区，在程序执行期间不能移动，且难以做到程序和数据的共享，其内存利用率低。
动态重定位是指在程序执行过程中，C P U 访问程序和数据之前实现地址转换。在多道程序系统中，可用的内存空间常常被许多进程共享，程序员编程时事先不可能知道程序执行时的驻留位置，而且必须允许程序因对换或空间收集而被移动，这些现象都需要程序的动态重定位。动态重定位必须借助于硬件的地址转换机构来实现，最简单的方式是利用一个重定位寄存器。当某个作业开始执行时，操作系统负责将该作业在内存中的起始地址送入重定位寄存器中。之后，在作业的整个执行过程中，每当访问内存时，重定位寄存器的内容将被自动地加到逻辑地址送入内存地址寄存器中去，从而得到与该逻辑地址对应的物理地址，用内存地址寄存器的内容访问数据。动态重定位的优点是程序可在内存中移动，当程序移动后，只要将新的内存区域的首地址放进基址寄存器就可以了。而且，动态重定位方式容易实现程序的共享，有可能提供虚拟存储空间。

3.3.2 分区存储管理

存储器的管理方式随着操作系统的发展而发展，早期存储管理方式发展的推动力，主要来自于“千方百计地提高存储器的利用率”。这样，由固定式分区存储分配方式演变为分页式存储管理方式，此时，存储器利用率已达到较为令人满意的程度，而后存储器管理继续发展的动力，则主要来自于更好地满足用户的需要，这样，又产生了分段式存储管理方式和虚拟存储器。
在存储管理系统中，最简单的方法就是单一连续管理，即将内存空间分成两个存储区域，一个区域用来存储操作系统程序，另一个区域归用户使用，称为用户内存区。该管理方式的主要特点是管理简单，不需要太多的软硬件支持。但由于内存中只允许存放 一个作业，系统的资源利用率不高，一般只能用于单用户、单任务的操作系统中。分区管理是支持多道程序运行的最简单的一种内存管理方式，主要有固定分区、可变分区、可重定位分区和多重分区4 种方式。

1.固定分区

固定分区也称为静态分区，是在作业装入之前，内存就被划分为若干个分区。划分工作可以由系统管理员完成，也可以由操作系统实现。一旦划分完成，在系统运行期间不再重新划分，即分区个数不可变，分区大小不可变。这种分区方式一般将内存的用户区域划分成大小不等的分区，以适应不同大小的作业的需要。系统有一张分区说明表，每个表目说明一个分区的大小、起始地址和是否己分配的标志。固定分区的主要优点是实现技术简单，适用于作业的大小和多少事先都比较淸楚的系统中；其主要缺点是由于每个分区只能存放一个作业，所以内存的利用率不高，内部碎片较多。

2.可变分区

可变分区也称为动态分区，是指在作业装入内存时，从可用的内存中划出一块连续的区域分配给它，形成一个新的分区，且分区大小正好等于该作业的大小。可变分区中分区的大小和分区的个数都是可变的，而且是根据作业的大小和多少动态地划分的。这种内存管理技术是固定分区的改进，既可以获得较大的灵活性，又能提高内存的利用率。可变分区在分配时，首先找到一个足够大的空闲分区（自由分区），即这个空闲区的大小比作业要求的要大，系统则将这个空闲分区分成两个部分，一部分成为己分配的分区，剩余的部分仍作为空闲区。在回收撤除作业所占领的分区时，要检查回收的分区是否与前后空闲的分区相邻接，若是则加以合并，使之成为一个连续的人空间。在选择空闲分区时，可变分区分配策略主要采用以下几种算法：
（1）首次适应算法。从空闲区表（空闲区链）的第-个表目起查找该表，把最先能够满足要求的空闲冈分配给作业，这种方法的目的在于减少查找时间。为适应这种算法，空闲区表中的空闲区要地址由低到高进行排序。该算法的特点是，如果找出的空闲区长度恰好等于申请的长度则是最合适的：如果比申请的长度略大，则分割后剩下的空闲区就很小，这种空闲K 不但不能被再度使用，而旦还占用空闲区表的一个节点。当空闲区表中的小空闲区节点过多时，本算法的性能急剧下降。
（2） 最佳适应算法。它从全部空闲区中找出能满足作业要求的、且最小的空闲区， 这种方法能使碎片尽量小。为适应这种算法，空闲K 表中的空闲区要按大小从小到大进行排序，自表头开始查找到第一个满足要求的空闲分区分配。最佳适应算法的特点是，分配空间时尽量利用低地址部分的存储区域，而使高地址部分保持较大的空闲区，有利 于大进程空间的装入。
（3） 最坏适应算法。从所有未分配的分区中挑选最大的且大于和等于作业大小的分区分给要求的作业；空闲区按由大到小排序，每次查找从链头开始。最坏适应算法的特点是，由于过多地分割大的空闲当遇到较大空间申请时，可能无法满足其中请。该算法对中、小作业比较有利。
实践表明，在针对存储空间利用情况的三种策略中，首次适应算法可能比最佳适应 算法好，而首次适应算法和最佳适应算法一定比最坏适应算法好。

3.可重定位分区

可重定位分区分配是解决存储器碎片问题的简单而有效的方法。其基本思想是在适当的时候，把零散的空白区合并为一个大的空白空间，称为拼接。实现方式是移动某些已分配区域中的信息，使所有的分配都紧挨着存储器的一端，而空白区在另一端。

4.多重分区

多重分区的基本思想是为一个作业分配一个以上的分区，允许一个作业在其运行过程中动态地申请附加存储空间，该空间不必和己有的作业分区相连接。多重分区的优点是便于使用共亨子程序或数据，其缺点是需要较多的硬件支持，因为该分K 方式一定要有动态重定位结构来支持，管理也较复杂。

5.存储器保护

分区方式允许多道程序在内存中同时运行，因此，必须解决存储器保护问题。常用的方法有界地址保护和设置存储键保护。

界地址保护又称为界限寄存器保护，分为界限寄存器、基址和限长寄存器两种保护方式。其中界限寄存器方式是指下界寄存器存放作业分区的起始地址，上界寄存器存放下一个分区的起始地址。每次寻址和汸问时，先与这两个寄存器的内容进行比较，以实现对分区的保护；基址和限长寄存器方式是指基址寄存器存放作业分区的起始地址，限长寄存器存放作业的最大偏移暈（长度）。在作业运行过程中，在访问存储器时所计算出的存储地址如果超过限长，则发出越界中断信号。

存储键保护的基本思想是系统对每个作业或进程进行内存分配时，对同一作业的各页面所对应的内存块都要指定一个相同的、不与其他作业相重的键（代码），这个键保存于快速寄存器和该作业的程序状态字中。当程序要访问某一块时，将程序状态字中的键与被访问块的键进行比较，若相符，则表明允许本次访问，否则就发出越界中断，请求系统处理。为使系统能访问内存的任何块，其程序状态字的键为“0”，此时，不必进行键的比较工作。

3.3.3 段页式存储管理

分区存储管理存在产生存储碎片和空间管理较复杂的问题，其原因在于，这种管理方式要求把作业放在内存的一片连续区域中。为了避免这种连续性要求，可以将作业的逻辑地址空间分成若干个长度相等的区域（称为页），内存空间也划分成若千个与页长度相等的区域（称为页帧或块），程序装入时，每页对应一个页帧，这就是分页存储管理的思想。

1.页式存储管理

在分页存储管理中，页帧可以是连续的，也可以是不连续的。系统为每道作业建立一张页面映射表（称为页表)，记录相应页在内存中对应的页帧号。这种管理方式消除了可变分区中紧致存储空间所带来的开销，同时，又能实现内存信息共享和虚拟存储技术。

在分页存储管理中，地址结构由两部分组成，分别是页号和页内位移（页内地址)。地址变换机构的基本任务是利用页表把用户程序中的逻辑地址变换成内存中的物理地址，为了实现地址变换功能，在系统中设置页表寄存器，用来存放页表的起始地址和页表的长度。在进程未执行时，每个进程对应的页表的起始地址和长度存放在进程的PCB中，当该进程被调度时，就将它们装入页表寄存器。在进行地址变换时，系统将页号与页表长度进行比较，如果页号大于页表寄存器中的页表长度，则访问越界，产生越界中断。如未出现越界，则根据页表寄存器中的页表起始地址和页号计算出该页在页表项中的位置，得到该页的物理块号，并将此物理块号装入物理地址寄存器中。与此同时，将有效地址寄存器中的页内地址直接装入物理地址寄存器的块内地址字段中，这样，便完成了从逻辑地址到物理地址的变换。

如果页表存放在内存中，则每次访问内存时，都要先访问内存中的页表，然后根据所形成的物理地址再访问内存。这样，CPU 保存一个数据必须访问两次内存，降低了计算机的处理速度。为了提高地址变换的速度，可以在地址变换机构中增设一个具有并行査询功能的特殊高速缓冲存储器（称为联想存储器或快表），用以存放当前访问的那些页表项。

2.段式存储管理

段式存储管理按用户作业中的自然段来划分逻辑空间，每段占用连续的地址空间，其逻辑地址是二维的，由段号和段内地址组成。系统为每个作业建立一张段表，记录该段在内存中的起始地址和段长，各段可以存放在内存不同的分K 中，段的分配与回收与可变分区存储管理相同。段式存储管理的地址转换采用动态重定位方式，地址转换机构取出逻辑地址的段号和段内地址，根据段号检索段表，找到该段对应的表目，将该段的起始地址与段内地址相加得到绝对地址。段式存储管理也存在二次访存问题，可以通过增设快表来解决。

段式存储管理可以采用地址转换机制进行越界保护和在段表中增设一些标志位，进行存取控制保护。由于用户对信息的共享要求是以段为单位的，因此共享易于实现，若多个作业段表中的某一项指向内存的同一个地址，则内存中以该地址为起始地址的那一段便被共享了。虽然段存储式管理方便用户编程，便于共享与保护，支持动态链接和动态增长，但它对内#的管理与可变分区存储管理是类似的，也存在存储管理复杂，空间利用差的缺点。

段式存储管理和分页存储管理有许多相似之处，例如，都采用离散分配方式来提高内存利用率，都要通过地址变换机构来实现地址变换。但在概念上两者是完全不同的，它们的主要区别表现在以下三个方面：
（1）分页是一个单一的线性地址空间，分段作业地址空间是二维的。
（2） 页是信息的物理单位，大小固定，分页活动是用户看不见的，分页的目的是为了提高内存的利用率；段是信息的逻辑单位，其长度不定，分段是用户可见的活动，分段的目的是为了更好地满足用户的需要。
（3）分页存储管理实现单段式虚拟存储系统， 而段式存储管理实现多段式虚拟存储系统。

3.段页式存储管理

段页式存储管理的基本思想是将段式存储管理与分页存储管理结合起来，正好克服了各自存在的一些问题。段页式存储管理将作业分成若干段，每个段分成若千页，每段赋了一个段名，为了实现地址转换，必须为每个作业配置一张段表和若干张页表。内存的分配与回收以页为单位进行。作业的逻辑地址是二维的，包括段号和段内地址，其中段内地址又包含页号和页内地址两部分。

段页式存储管理的地址转换的具体步骤为：地址转换机构取出逻辑地址，并根据页的大小将段内地址再细分为页号和页内地址。根据段号检索段表，找到该段的页表存放地址；根据页号査页表，取出相应的页帧号；把页帧号和页内地址合并，得到物理地址，执行访存操作。由此吋知，为了获得一条指令或数据，需要三次访问内存，这使得系统执行指令的速度更慢。这个问题同样可通过快表来解决，快表中存放当前使用的段号、页号、页帧号和页内地址等表目。段页式存储管理的保护方法与段式存储管理相同，共享则从页表幵始。

3.3.4 虚拟存储管理

3.3.2节 和 3.3.3节介绍的各种存储管理方式中，必须为作处分配足够的存储空间，以装入有关作业的全部信息，作业的大小不能超出内存的可用空间，否则，这个作业是无法运行的。但当有关作业的全部信息都装入内存后，作业执行时实际上不是同时使用全部信息的，有些部分运行一遍便不再使用，甚至有些部分在作业执行的整个过程中都不会被使用（例如，错误处理部分等）。这种情况的出现，是对宝贵的内存资源的一种浪费，大大降低了内存利用率。

虚拟存储管理的提出就是为了解决这一问题，应用程序在运行之前并不必全部装入内存，仅需将当前运行到的那部分程序和数据装入内存便可启动程序的运行，其余部分仍驻留在外存上。当要执行的指令或访问的数据不在内存时，再由操作系统通过请求调入功能将它们调入内存，以使程序能继续执行。如果此时内存已满，则还需通过置换功能，将内存中暂时不用的程序或数据调至外存上，腾出足够的内存空间后，再将要访问的程序或数据调入内存，使程序继续执行。这样，便可使一个大的用户程序能在较小的内存空间中运行，也可在内存中同时装入更多的进程使它们并发执行。从用户的角度看，该系统具有的内存容M 比实际的内存容量大得多。将这种具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的存储器系统称为虚拟存储系统。

1.局部性原理

虚拟存储管理能够在作业信息不全部装入内存的情况下保证作业正确运行，是利用了程序执行时的局部性原理。局部性原理是指程序在执行时呈现出局部性规律，即在一较短的时间内，程序的执行仅局限于某个部分。相应地，它所访问的存储空间也仅局限于某个区域。程序局部性包括时间局部性和空间局部性，时间局部性是指程序中的某条指令一旦执行，不久以后该指令可能再次执行。产生时间局部性的典型原因是由于程序中存在着大量的循环操作；空间局部性是指一旦程序访问了某个存储单元，不久以后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址可能集中在一定的范围内，其典型情况是程序顺序执行。

2.工作集

在虚拟存储管理中，可能会出现这种情况，即对于刚被替换出去的页，立即又要被访问，需要将它调入，因无空闲内存又要替换另一页，而后者是即将被访问的页，于是造成了系统需花费大量的时间忙于进行这种频繁的页面交换，致使系统的实际效率很低，严重时导致系统瘫痪，这种现象称为抖动现象。防止抖动现象有多种办法，例如，采取局部替换策略、引入工作集算法和挂起若干进程等。工作集是指在某段时间间隔内，进程实际要访问的页面的集合。引入虚k 内存后，程序只需有少量的内存就可运行，但为了使程序有效地运行，较少产生缺页，必须使程序的工作集全部在内存中。

3.页面置换算法

当内存中没有空闲页面，而又有程序和数据需要从外存中装入内存运行时，就需要从内存中选出一个或多个页面淘汰出去，以便新的程序和数据装入运行，良好的页面置换算法应该淘汰那些被访问概率最低的页，并将它们移出内存。
（1）随机淘汰算法。无法确定哪些页被访问的概率较低时，随机地选择某个页面，并将其换出。
（2）轮转算法。按照内存页面的编号，循环地换出内存中一个可以被换出的页，无论该页是刚换进来的还是已驻留内存很长时间的。
（3）先进先出算法（First In First O u t , FIFO )。FIFO 算法总是选择在内存驻留时间最长的一页将其淘汰。实 现 FIFO 算法需要把各个己分配页面按页面分配时间顺序链接起来，组 成 FIFO 队列，并设置一置换指针，指 向 FIFO 队列的队首页面。FIFO 算法忽略了一种现象的存在，那就是在内存中停留时间最长的页往往也是经常要访问的页。将这些页淘汰，很可能刚置换出去，又请求调用该页，致使缺页中断太频繁，严重降低内存的利用率。
FIFO 的另一个缺点是它可能会产生一种异常现象。一 般来说，对于任一作业或进程, 如果给它分配的内存页面数越接近于它所要求的页面数，则发生缺页的次数会越少。但使用FIFO 算法时，有时会出现分配的页面数增多，缺页次数反而增加的现象，称为belady现象。
（4）最近最久未使用算法（Least Recently U s e d，LRU )。为需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。例如，考虑一个仅460个字节的程序的内存访问序列（10, 11, 104, 170, 73, 309, 185, 245, 246, 434, 458, 364)，页面的大小为100个字节，则 4 6 0个字节应占5 页，编号为 0? 4 , 第 0 页字节为 0? 9 9 , 第 1 页 为 100? 1 9 9 ,依次类推。得到页面的访问序列是（0, 0, 1, 1, 0, 3, 1, 2, 2, 4, 4, 3 ) , 可简化为（0, 1, 0, 3，1, 2, 4, 3)。如果内存中有2 0 0个字节可供程序使用，则内存提供2 个页帧供程序使用。按照F I F O 算法，共产生 6 次缺页中断，如下表所示。

按照LRU 算法，共产生 7 次缺页中断，如下表所示。

（5） 最近没有使用页面責换算法（N o U s e d Recently, NUR )。在需要置换某一页时，从那些最近的一个时期内未被访问的页任选一页置换。只要在页表中增设一个访问位即可实现。当某页被访问时，访问位置为 1，否则访问位置为0。系统周期性地对所有引用位清零。当需淘汰一页时，从那些访问位为零的页中选一页进行淘汰。
（6） 最优置换算法。选择那些永久不使用的，或者在最长时间内不再被访问的页面置换出去。因为要确定哪个页面是未来最长时间内不再被访问的，目前来说很难估计，所以，该算法通常用来评价其他算法。
（7） 时钟页面替换算法（C l o c k )。使用页表中的引用位，将作业己调入内存的页面链成循环队列，用一个指针指向循环队列中的下一个将被替换的页面。其实现方法如下：一个页面首次装入内存时，其引用位置 1 ; 在内存中的任何一个页面被访问时，其引用位置1 ; 淘汰页面时，存储管理从指针当前指向的页面开始扫描循环队列，把所遇到的引用位是 1 的页面的引用位清0 , 并跳过这个页面；把所遇到的引用位是0 的页面淘汰掉，指针推进一步；扫描循环队列时，如果遇到的所有页面的引用位均为1，则指针就会绕整个循环队列一圈，将碰到的所有页面的引用位清0 ; 指针停在起始位置，并淘汰掉这一页，然后指针推进一步。

3.4 文件系统

文件是操作系统进行信息管理的基本单位，对软件资源的管理是通过文件系统来实现的。为了实现这些功能，操作系统必须考虑文件0 录的建立和维护、存储空间的分配和回收、信息的编址方法和存储次序，以及如何检索用户信息等问题。

3.4.1 文件的组织结构

文件的组织结构是指文件的构造方式，通常可以从两个不同的角度来对它进行考察。其中，从用户角度看到的文件称为文件的逻辑组织，从系统角度看到的文件称为文件的物理组织。

1.逻辑结构

文件的逻辑结构（逻辑文件）是指用户概念中的文件，它独立于物理存储。逻辑文件有两种形式，分别是无结构的流式文件和有结构的记录式文件。
（1）流式文件。流式文件是相关信息项的集合，基本单位是字节（或字），它的管理比较简单，用户可以很方便地对其进行操作。因此，那些对基本信息单位操作不多的文件较适用于采用流式文件结构，例如，源程序文件、目标代码文件等。在 U N I X 系统中，所有的文件都被看成是流式文件，系统不对文件进行格式处理。
（2）记录式文件。记录式文件是数据记录的集合，其基本单位是逻辑记录，记录的长度有等长或变长之分。对记录式文件，所有记录描述一个实体集，有相同或不同数目的数据项。流式文件也可视为记录式文件的特例，即每个记录只有1 个 字 节 （或字）。记录式文件的逻辑组织有三种形式，一种是顺序存储方式，即记录按序排列；一种是直接存储方式，即用户对记录的存储是不按顺序的，可以指定某一记录进行存储；还有一种是按键存取方式，即用户对文件内容的访问不是根据记录的编号或地址，而是根据记录的某项内容（关键字）来进行的。

2.物理结构

文件物理结构（物理文件）是指文件在存储介质上的组织方式，它依赖于物理的存储设备和存储空间，可以看作是相关物理块的集合。由于物理结构决定了信息在存储设备上的存放位置和方式，W 此，信息的逻辑位置到物理位賈的映射关系也是由物理结构决定的。常用的文件物理结构有顺序结构、链接结构和索引结构。
（1）顺序结构（连续结构）。逻辑上连续的记录构成的文件分配到连续的物理块中。这种方式管理简单，存储速度快，空间利用率低，但文件记录插入或删除操作不方便， 只能在文件末尾进行。
（2）链接结构（串联结构）。将信息存放在非连续的物理块中，每个物理块均设有一个指针，指向其后续的物理块，从而使得存放同一文件的物理块链接成一个串联队列。链接方式又分为显式链接和隐式链接。显式链接的链接指针在专门的链接表中，隐式链接的指针在存放信息的物理块中。链接结构空间利用率高，且易于文件扩充，但查找效率比较低。
（3）索 引 结 构 （随机结构）。为每个文件建立一个索引表，其中每个表项指出信息所在的物理块号，表目按逻辑记录编写顺序或按记录内某一关键字顺序排列。对于大文件，为检索方便，可以建立多级索引，还可以将文件索引表也作为一个文件（称为索引表文件)。该方式可以满足文件动态增长的要求且存取方便，但建立索引表增加了存储空间的开销，对于多级索引，访问时间开销较大。

例如，在 U N I X 系统中，文件的物理结构采用直接、一级、二级和三级间接索引技术，假如索引节点有1 3个地址项，并且规定地址项0? 9 采用直接寻址方法，地址项10采用一级间接寻址，地址项 11采用二级间接寻址，地址项 1 2采用三级间接寻址。每个盘块的大小为1KB ，每个盘块号占4B , 那么，对于访问文件的第356 168B 处的数据来说；先进行简黾换算356 168/1024& 348KB , 由于地址项0? 9 可直接寻址10个物理盘块，每个物理块大小为1KB , 所以访问文件的前10K B 范围的数据时是直接寻址。地址项 1 0釆用一次间接寻址，即地址项10里存放的是一级索引表的地址，因为每个盘块号占 4B , 该索引表可存放1024/4=256个物理块的地址，所以当访问文件为10? 266K B 之间的数据时是一次间接寻址。由于要访问的数据是348KB , 所以还有 348-266=82KB 。显然地址项11足够存取这些数据，因此，最多就在地址项11而无须存取地址项1 2 , 即只需要二级间接寻址。

3.树形文件结构

文件控制块的集合称为文件目录，文件目录也被组织成文件，常称为目录文件。文件管理的一个重要方面是对文件B 录进行组织和管理。文件系统一般采用一级目录结构、二级目录结构和多级目录结构，例如，U N I X 和 W i n d o w s 系统都采用了多级树形目录结构。

主文件目录称为根目录，根目录下的子目录称为中间节点，子目录下的文件称为叶节点。从根目录出发到某文件的通路上所有各级子目录名和该文件名的顺序组合称为文件的路径名。每个文件都有一个唯一的路径名。为操作方便，减少访问时间，系统给用户指定一个当前目录，若用户欲访问某文件，就不用给出全部路径，只需给出从当前目录到欲査找文件之间的相对路径名。树形目录结构的特点是层次清楚，解决了文件重名问题，提高了查找的效率，同时也方便用户共享文件。

3.4.2 存储空间管理

一个大容量的文件存储器为系统本身和许多用户所共享。为方便用户“按名存取” 所需文件，系统应能自动为用户分配并管理系统和用户的存储空间。为此，必须解决以下三个问题：登记空闲区的分布情况、按需要给一个文件分配存储空间，以及收回不再保留的文件所占的存储空间。以上问题都可以归结为磁盘空闲区的管理问题，常用的磁盘空闲区管理方法有空闲文件目录、空闲块链、位示图和成组链接法。

1.空闲文件目录

磁盘空间上一个连续的未分配区域成为空闲文件。系统为所有这些空闲文件单独建立一个目录。对每个空闲文件，在这个目录中建立一个表目。表目的内容包括第一个空闲块地址（物理块号）和空闲块个数等。在进行存储空间的分配时，也可采用首次适应和最佳适应等算法，而冋收时，同样要进行空闲区的合并。这种方法的优点是空闲区的分配和回收都相当容易，伹用来管理空闲K 的空闲表需要占用大量的存储空间。

2.空闲块链

空闲块链是将所有空闲块用链接指针或索引结构组成一个空闲文件。释放和分配空闲块都可以在链首进行，只需要修改几个有关的链接字。该方法只要求在内存中保存一个指针，令它指向第一个空闲块，其优点是实现简单，但工作效率低，因为每当在链上增加或移去空闲块时，都需要对空闲块做较大的调整，从而会有较大的系统开销。一种改进方法是将空闲块分成若干组，再用指针将组与组链接起来，这种管理空闲块的方法称为成组链接法，它在进行空闲块的分配与回收时要比空闲块链法节省时间。

3.位示图法

位示图是利用二进制的1位来表示文件存储空间中的1个块的使用情况。一个m 行、 n 列的位示图，可 用 来 描 述 块 的 文 件 存 储 空 间 ，当行号、列号和块号都是从0开始编号时，第i行、第j列的二进制位对应的物理块号为i*n+j。如 果 “0”表示对应块空闲，“1”表示对应块已分配，则在进行存储空间的分配时，可顺序扫描位示图，从中找出一个或一组值为“0”的二进制位，将对应的块分配出去，并将这些位置“1”；而在回收某个块时，只需找到对应的位，并将其值清零即可。位示图法适合于所有的分配方式，它简单易行，而且，位示图通常较小，故吋将其读入内存，从而进一步加快文件存储空间分配和回收的速度。

4.成组链接法

成组链接法是对空闲块链法的一种改进，它将一个文件卷的所有空闲盘块按同定大小 （例如，每组m 块）分成若干组，并将每一组的盘块数和该组所有的盘块记入前一组的最后一个盘块中，第一组的盘块数和该组的所有盘块号则记入超级块的空闲盘块中。当系统要为用户分配文件所需的盘块时，若第一组不只一块，则将超级块中的空闲盘块数减1 , 并将空闲盘块栈顶的盘块分配出去；若第一组只剩一块且栈顶的盘块号不是结束 标 记 “0”，则先将该块的内容（记录有下一组的盘块数和盘块号）读到超级块中，然后再将该块分配出去；否则，若栈顶的盘块号为结束标记“0”，则表示该磁盘上已无空闲盘块可供分配。

在系统回收空闲盘块时，若第一组不满w 块，则只需将冋收块的块号填入超级块的空闲盘栈顶，并将其中的空闲盘块数加1 ; 若第一组己有m 块，则必须先将超级块中的空闲盘块数和空闲盘块号写入回收块中，然后将盘块数和回收块的块号记入超级块中。

值得注意的是，超级块中的空闲盘块栈是临界资源，对该栈的操作必须互斥地进行。系统需要为空闲盘块设置一把“锁”，并通过上锁和解锁来实现对空闲盘块栈的操作。成组链接法除了第一组空闲盘块外，其余空闲盘块的登记不占额外的存储空间，而超级块(即文件卷的第一块）已在安装磁盘时拷入内存，因此，绝大部分的分配和回收工作可在内存中进行，从而使之具有较高的效率。

3.4.3 分布式文件系统

在计算机网络中，每个节点运行一个包括自己的文件系统的本地操作系统，称为本地文件系统（Local File S y s t e m , L F S )。L F S 负责将磁盘块分配给文件，并维护文件分配表等信息，提供诸如新建文件、读文件、写文件和删除文件等+同的服务。它为所有本地 S 录和文件维护目录结构，允许用户更改自己的工作目录，列出本地0 录中的所有文件，以及实现对本地文件和目录的访问控制。

当用户想要对远程文件执行所有这些功能时，就会出现问题，分布式文件系统(Distributed File S y s t e m , D F S ) 正好可以提供这种功能。D F S 是分布式系统的重要组成部分，它允许通过网络来互连，使不同机器上的用户共享文件的一种文件系统。D F S 不是一个分布式操作系统，而是一个相对独立的软件系统，被集成到分布式操作系统中，并为其提供远程访问服务。

1.DFS 的特点

D F S 具有网络透明性和位置透明性。网络透明性是指用户访问文件服务器上的文件的操作如同访问L F S 的操作一样；位置透明性是指用户通过文件名访问文件，但并不知道该文件在网络中的位置，文件的物理位置改变了，但只要文件的名字不变，用户仍可进行访问。

在分布式系统中，区分文件服务和文件服务器的概念是非常重要的。文件服务是文件系统为其用户提供的各种功能描述，例如，可用的原语，以及它们所带的参数和执行的动作等。对于用户来说，文件服务精确地定义了它们所期望的服务，而不涉及实现方面的细节。实际上，文件服务提供了文件系统与用户之间的接口；文件服务器是运行在网络中某台机器上的一个实现文件服务的进程，一个系统可以有一个或多个文件服务器，但用户并不知道有多个文件服务器及它们的位置和功能。用户所知道的只是当调用文件服务中某个具体过程时，所要求的工作以某种方式执行，并返回所要求的结果。

2.DFS的组成

D F S 为系统中的客户机提供共享的文件系统，为分布式操作系统提供远程文件访问服务。分布式操作系统通常在系统中的每个机器上都有一个副本，但 D F S 并不一样，它由两部分组成，分别是运行在服务器上的D F S 软件和运行在每个客户机上的D F S 软件。这两部分程序代码在运行中都要与本机操作系统的文件系统紧密结合，共同起作用。现代操作系统都支持多种类型的文件系统，D F S 将通过虚拟文件系统和虚拟节点与L F S 交互作用。

3.DFS的架构

D F S 目前大多采用客户/服务器架构，客户是要访问文件的计算机，服务器是存储文件并且允许用户访问这些文件的计算机。D F S 中需要解决的一个问题是命名的透明性，通常有三种解决方式，第一种方式是通过机器名加路径名来访问文件；第二种方式是将远程文件系统安装到本机文件目录上，这样，用户就可以自己定制文件名；第三种方式是让所有机器上看起来有相同的单一名字空间，这种方式实现难度较大。

在客户/服务器架构中，客户使用远程方法访问文件，服务器则响应客户的请求。有些系统中的服务器能提供更多的服务，它不仅响应客户的请求，还对客户机中的高速缓存的一致性作出预测，一旦客户数据变为无效时便通知客户。