系统架构设计师-第2章-操作系统-526互联

第2章-操作系统

2.1. 操作系统的类型与结构

计算机系统由硬件和软件两部分组成。操作系统是计算机系统中最基本的系统软件，它既管理计算机系统的软、硬件资源，又控制程序的执行。操作系统随着计算机研究和应用的发展逐步形成并日趋成熟，它为用户使用计算机提供了一个良好的环境，从而使用户能充分利用计算机资源，提高系统的效率。操作系统的基本类型有：批处理操作系统、分时操作系统和实时操作系统。从资源管理的角度看，操作系统主要是对处理器、存储器、文件、设备
和作业进行管理。

2.1.1. 操作系统的定义

操作系统（Operating System ，OS）是计算机系统中的核心系统软件，负责管理和控制计算机系统中的硬件和软件资源，合理地组织计算机工作流程和有效地利用资源，在计算机与用户之间起接口的作用。操作系统为用户提供的接口表现形式一般为：命令、菜单、窗口之类的，而操作系统为应用程序提供的接口为API。操作系统与硬件/软件的关系如图2-1所示。

20240109181740

2.1.2. 操作系统分类

按照操作系统的功能划分，操作系统的基本类型有批处理操作系统、分时操作系统、实时操作系统、网络操作系统、分布式操作系统、嵌入式操作系统、微内核操作系统等。

2.2. 操作系统基本原理

操作系统的主要功能是进行处理机与进程管理、存储管理、设备管理、文件管理和作业管理的工作，本节讨论操作系统是如何完成这些功能的。

2.2.1. 进程管理

处理机是计算机系统的核心资源。操作系统的功能之一就是处理机管理。随着计算机的迅速发展，处理机管理显得更为重要，这主要由于计算机的速度越来越快，处理机的充分利用有利于系统效率的大大提高；处理机管理是整个操作系统的重心所在，其管理的好坏直接影响到整个系统的运行效率；而且操作系统中并发活动的管理和控制是在处理机管理下实现的，处理机管理集中了操作系统中最复杂的部分，它设计的好坏关系到整个系统的成败。

进程是处理机管理中最基本的、最重要的概念。进程是系统并发执行的体现。由于在多道程序系统中，众多的计算机用户都以各种各样的任务，随时随地争夺使用处理机。为了动态地看待操作系统，则以进程作为独立运行的基本单位，以进程作为分配资源的基本单位，从进程的角度来研究操作系统。因此，处理机管理也被称为进程管理。处理机管理的功能就是组织和协调用户对处理机的争夺使用，把处理机分配给进程，对进程进行管理和控制，最大限度也发挥处理机的作用。

进程的概念

用静态的观点看，操作系统是一组程序和表格的集合。用动态的观点看，操作系统是进程的动态和并发执行的。而进程的概念实际上是程序这一概念发展的产物。因此，可以从分析程序的基本特征入手，引出“进程”的概念。

顺序程序是指程序中若干操作必须按照某种先后次序来执行，并且每次操作前和操作后的数据、状态之间都有一定的关系。在早期的程序设计中，程序一般都是按顺序执行的。

在多道程序系统中，程序的运行环境发生了很大的变化。主要体现在：
- 资源共享。为了提高资源的利用率，计算机系统中的资源不再由一道程序专用，而是由多道程序共同使用。
- 程序的并发执行或并行执行。逻辑上讲允许多道不同用户的程序并行运行；允许一个用户程序内部完成不同操作的程序段之间并行运行；允许操作系统内部不同的程序之间并行运行。物理上讲：内存储器中保存多个程序，I/O设备被多个程序交替地共享使用；在多处理机系统的情形下，表现为多个程序在各自的处理机上运行，执行时间是重叠的。单处理机系统时，程序的执行表现为多道程序交替地在处理机上相互空插运行。
实际上，在多道程序系统中，程序的并行执行和资源共享之间是相辅相成的。一方面，只有允许程序并行执行，才可能存在资源共享的问题；另一方面，只有有效地实现资源共享，才可能使得程序并行执行。

这样，可增强计算机系统的处理能力和提高机器的利用率。并发操作实际上是这样的：大多数程序段只要求操作在时间上是有序的，也就是有些操作必须在其他操作之前，这是有序的，但其中有些操作却可以同时进行。
进程的状态转换

由进程运行的间断性，决定了进程至少具有以下三种状态：
- 就绪状态。当进程已分配了除CPU以外的所有必要的资源后，只要能再获得处理机，便能立即执行，把这时的进程状态称为就绪状态。在一个系统中，可以有多个进程同时处于就绪状态，通常把它们排成一个队列，称为就绪队列。
- 执行状态指进程已获得处理机，其程序正在执行。在单处理机系统中，只能有一个进程处于执行状态。
- 阻塞状态指进程因发生某事件（如请求I/O、申请缓冲空间等）而暂停执行时的状态，亦即进程的执行受到阻塞，故称这种暂停状态为阻塞状态，有时也称为“等待”状态，或“睡眠”状态。通常将处于阻塞状态的进程排成一个队列，称为阻塞队列。
进程的状态随着自身的推进和外界的变化而变化。例如，就绪状态的进程被进程调度程序选中进入执行状态；执行状态的进程因等待某一事件的发生转入等待状态；等待状态的进程所等待事件来到便进入就绪状态。进程的状态可以动态地相互转换，但阻塞状态的进程不能直接进入执行状态，就绪状态的进程不能直接进入阻塞状态。在任何时刻，任何进程都处于且只能处于这其中一种状态。进程状态的变化情况如下：
- 运行态→等待态：一个进程运行中启动了外围设备，它就变成等待外围设备传输信息的状态；进程运行中申请资源（主存储空间及外围设备因得不到满足）时，变成等待资源状态，进程在运行中出现了故障（程序出错或主存储器读写错误等），变成等待干预状态。
- 等待态→就绪态：外围设备工作结束后等待外围设备传输信息的进程结束等待；等待的资源能得到满足时（另一个进程归还了资源），则等待资源者就结束等待；故障排队后让等待干预的进程结束等待，任何一个结束等待的进程必须先变成就绪状态，待分配到处理器后才能运行。
- 运行态→就绪态：进程用完了一个使用处理器的时间后强迫该进程暂时让出处理器，当有更优先权的进程要运行时也迫使正在运行的进程让出处理器。由于自身或外界原因成为等待状态的进程让出处理器时，它的状态就变成就绪状态。
- 就绪态→运行态：等待分配处理器的进程，系统按一种选定的策略从处于就绪状态的进程中选择一个进程，让它占用处理器，那个被选中的进程就变成了运行态。
图2-2所示为进程的三种基本状态及各状态之间的转换。
关于挂起状态

在不少系统中，进程只有如图2-2所示的三种状态。但在另一些系统中，又增加了一些新状态，其中最重要的是挂起状态。引入挂起状态的原因有：
- 对换的需要。为了缓和内存紧张的情况，而将内存中处于阻塞状态的进程换至外存上，使进程又处于一种有别于阻塞状态的新状态。因为即使该进程所期待的事件发生，该进程仍不具备执行条件而不能进入就绪队列，称这种状态为挂起状态。
- 终端用户的请求。当终端用户在自己的程序运行期间，发现有可疑问题时，往往希望使自己的进程暂停下来。也就是说，使正在执行的进程暂停执行，若是就绪进程，则不接受调度以便研究其执行情况或对程序进行修改。把这种静止状态也称为挂起状态。
- 父进程请求。父进程常希望挂起自己的子进程，以便考查和修改子进程，或者协调各子进程间的活动。
- 负荷调节的需要。当实时系统中的工作负荷较重，有可能影响到对实时任务的控制时，可由系统把一些不重要的进程挂起，以保证系统正常运行。
- 操作系统的需要。操作系统希望挂起某些进程，以便检查运行中资源的使用情况及进行记账。
综上所述，不难了解挂起状态具有以下三个属性。
- 被挂起的进程，原来可能处于就绪状态，此时进程（被挂起）的状态称为挂起就绪；若被挂起的进程原来处于阻塞状态，此时的状态称为挂起阻塞。不论哪种状态，该进程都是不可能被调度而执行的。
- 处于挂起阻塞状态的进程，其阻塞条件与挂起条件无关；当进程所期待的事件出现后，进程虽不再被阻塞，但仍不能运行，这时，应将该进程从静止阻塞状态转换为挂起就绪状态。
- 进程可以由其自身挂起，也可由用户或操作系统等将之挂起。其目的都在于阻止进程继续运行，被挂起的进程只能用显式方式来激活，以便从挂起状态中解脱出来。
如图2-3所示为具有挂起操作的进程状态的演变情况。
进程互斥与同步

进程互斥定义为：一组并发进程中一个或多个程序段，因共享某一共有资源而导致必须以一个不允许交叉执行的单位执行。也就是说互斥是要保证临界资源在某一时刻只被一个进程访问。

进程同步定义为：把异步环境下的一组并发进程因直接制约而互相发送消息而进行互相合作、互相等待，使得各进程按一定的速度执行的过程称为进程同步。也就是说进程之间是异步执行的，同步即是使各进程按一定的制约顺序和速度执行。

系统中有些资源可以供多个进程同时使用，有些资源则一次仅允许一个进程使用，将一次仅允许一个进程使用的资源称为临界资源，很多物理设备如打印机、磁带机等都属于临界资源，某些软件的变量、数据、表格也不允许两个进程同时使用，所以也是临界资源。

进程在并发执行中可以共享系统中的资源。但是临界资源的访问则必须互斥进行，即各进程对临界资源进行操作的那段程序的执行也必须是互斥的，只有这样才能保证对临界资源的互斥访问。把一个进程访问临界资源的那段程序代码称为临界区，有了临界区的概念，进程间的互斥就可以描述为：禁止两个或两个以上的进程同时进入访问同一临界资源的临界区。

为此，必须有专门的同步机构来协调它们，协调准则如下：
- 空闲让进：无进程处于临界区时，若有进程要求进入临界区则立即允许其进入；
- 忙则等待：当已有进程进入其临界区时，其他试图进入各自临界区的进程必须等待，以保证诸进程互斥地进入临界区；
- 有限等待：有若干进程要求进入临界区时，应在有限时间内使一进程进入临界区，即它们不应相互等待而谁也不进入临界区；
- 让权等待：对于等待进入临界区的进程必须释放其占有的CPU。信号量可以有效地实现进程的同步和互斥。在操作系统中，信号量是一个整数。当信号量大于等于0时，代表可供并发进程使用的资源实体数，当信号量小于零时则表示正在等待使用临界区的进程数。建立一个信号量必须说明所建信号量代表的意义和设置初值，以及建立相应的数据结构，以便指向那些等待使用该临界区的进程。
对信号量只能施加特殊的操作：P操作和V操作。P操作和V操作都是不可分割的原子操作，也称为原语。因此，P原语和V原语执行期间不允许中断发生。

P（sem）操作的过程是将信号量sem值减l，若sem的值成负数，则调用P操作的进程暂停执行，直到另一个进程对同一信号量做V操作。V（sem）操作的过程是将信号量sem值加1，若sem的值小于等于0，从相应队列（与sem有关的队列）中选一个进程，唤醒它。

一般P操作与V操作的定义如下所述。
```
P操作：
P（sem）{
sem = sem - 1;
if（sem < 0）进程进入等待状态；
else  继续进行； } V操作：
V（sem）{
sem = sem + 1;
if（sem≤ 0）唤醒队列中的一个等待进程；
else继续进行;}
```
为了保护共享资源（如公共变量），使它们不被多个进程同时访问，就要阻止这些进程同时执行访问这些资源（临界资源）的代码段（临界区）；进程互斥不允许两个以上共享临界资源的并发进程同时进入临界区。利用P、V原语和信号量可以方便地解决并发进程对临界区的进程互斥问题

设信号量mutex是用于互斥的信号量，初值为1,表示没有并发进程使用该临界区。
于是各并发进程的临界区可改写成下列形式的代码段：
```
    P（mutex）；
    临界区
    V（mutex）；
```
要用P，V操作实现进程同步，需要引进私用信号量。私用信号量只与制约进程和被制约进程有关，而不是与整组并发进程相关。与此相对，进程互斥使用的信号量为公用信号量。首先为各并发进程设置私用信号量，然后为私用信号量赋初值，最后利用P，V原语和私用信号量规定各进程的执行顺序。经典同步问题的例子是“生产者－消费者”问题。这要求存后再取，取后再存，即有两个制约关系，为此，需要两个信号量，表示缓冲区中的空单元数和非空单元数，记为Bufempty和Buffull，它们的初值分别是1和0，相应的程序段形式是：
```
生产者
loop
生产一产品 next；
P（Bufempty）；
next  产品存缓冲区；
V（Buffull）；
endloop
消费者
loop
P（Buffulll）；
V（Bufempty）；
从缓冲区中取产品；使用产品
endloop
```
前趋图

前趋图是一个由结点和有向边构成的有向无循环图。该图通常用于表现事务之间先后顺序的制约关系。图中的每个结点可以表示一个语句、一个程序段或是一个进程，结点间的有向边表示两个结点之间存在的前趋关系。

例：在计算机中，经常采用流水线方式执行指令，每一条指令都可以分解为取指、分析和执行三步。取指操作为Ai，分析操作为Bi和执行操作为 Ci(i=1,2,3)。如图2-4所示为三个任务各程序段并发执行的前驱图。

图中A1没有前趋结点，称为开始结点，它不受任何制约，可以直接执行；而B1与A2只能在A1执行完成之后才能开始，而B2必须在B1与A2完成之后才能开始C3 没有后继结点，称为终止结点。

在前趋图中，执行先后顺序的制约关系可分为两种：直接制约和间接制约。

直接制约通常是指一个操作中，多个步骤之间的制约关系，也可以说是“同步的进程之间的制约关系”。如图2-4所示，A1、B1、C1是一条指令的取指、分析、执行的三个步骤，所以它们之间的关系是直接制约。

间接制约通常是指多个操作之间相同步骤的制约关系，也可以说是“互斥的进程之间的制约关系”。如图2-4所示，A1、A2、A3之间就存在间接制约的关系。前趋图的应用广泛，在项目开发中，可用前趋图来分析哪些活动可以并行完成。同时项目管理工具：Pert图，单（双）代号网络图等都融入了前趋图的思想。
进程调度与死锁

进程调度即处理器调度（又称上下文转换），它的主要功能是确定在什么时候分配处理器，并确定分给哪一个进程，即让正在执行的进程改变状态并转入就绪队列的队尾，再由调度原语将就绪队列的队首进程取出，投入执行。
引起进程调度的原因有以下几类：
- 正在执行的进程执行完毕。
- 执行中的进程自己调用阻塞原语将自己阻塞起来进入睡眠状态。
- 执行中的进程调用了P原语操作，从而因资源不足而阻塞；或调用V原语操作激活了等待资源的进程队列。
- 在分时系统中，当一进程用完一个时间片。
- 就绪队列中某进程的优先级变得高于当前执行进程的优先级，也将引起进程调度。
进程调度的方式有两类：剥夺方式与非剥夺方式。所谓非剥夺方式是指，一旦某个作业或进程占用了处理器，别的进程就不能把处理器从这个进程手中夺走，直到该进程自己因调用原语操作而进入阻塞状态，或时间片用完而让出处理机；剥夺方式是指，当就绪队列中有进程的优先级高于当前执行进程的优先级时，便立即发生进程调度，转让处理机。

进程调度的算法是服务于系统目标的策略，对于不同的系统与系统目标，常采用不同的

调度算法：
- 先来先服务（First Come and First Serverd，FCFS）调度算法，又称先进先出（First Inand First Out ，FIFO）。就绪队列按先来后到原则排队。
- 优先数调度。优先数反映了进程优先级，就绪队列按优先数排队。有两种确定优先级的方法，即静态优先级和动态优先级。静态优先级是指进程的优先级在进程开始执行前确定，执行过程中不变，而动态优先级则可以在进程执行过程中改变。
- 轮转法（Round Robin）。就绪队列按FCFS方式排队。每个进程执行一次占有处理器时间都不超过规定的时间单位（时间片）若超过，则自行释放自己所占有的 CPU 而排到就绪队列的末尾，等待下一次调度。同时，进程调度程序又去调度当前就绪队列中的第一个进程。
进程管理是操作系统的核心，在进程管理的实现中，如果设计不当，会出现一种尴尬的局面——死锁。

当若干个进程互相竞争对方已占有的资源，无限期地等待，不能向前推进时会造成“死锁”。例如，P1进程占有资源R1，P2进程占有资源R2，这时，P1又需要资源R2，P2也需要资源R1，它们在等待对方占有的资源时，又不会释放自己占有的资源，因而使双方都进入了无限等待状态。

死锁是系统的一种出错状态，它不仅会浪费大量的系统资源，甚至还会导致整个系统的崩溃，所以死锁是应该尽量预防和避免的。
- 死锁条件。产生死锁的主要原因是供共享的系统资源不足，资源分配策略和进程的推进顺序不当。系统资源既可能是可重复使用的永久性资源，也可能是消耗性的临时资源。产生死锁的必要条件是：互斥条件、保持和等待条件、不剥夺条件和环路等待条件。
- 解决死锁的策略。处于死锁状态的进程不能继续执行但又占用了系统资源，从而阻碍其他作业的执行。
解决死锁有两种策略：一种是在死锁发生前采用的预防和避免策略；另一种是在死锁发生后采用的检测与恢复策略。

死锁的预防主要是通过打破死锁产生的 4 个必要条件之一来保证不会产生死锁。采用的死锁预防策略通常有资源的静态分配法或有序分配法，它们分别打破了资源动态分配条件和循环等待条件，因此不会发生死锁。但这样做会大大降低系统资源的利用率和进程之间的并行程度。

死锁避免策略，则是在系统进行资源分配时，先执行一个死锁避免算法（典型的如银行家算法），以保证本次分配不会导致死锁发生。由于资源分配很频繁，因此死锁避免策略要耗费大量的CPU和时间。

2.2.2. 存储管理

存储器是计算机系统中最重要的资源之一。因为任何程序和数据以及各种控制用的数据结构都必须占有一定的存储空间，因此，存储管理直接影响系统性能。

存储器由内存和外存组成。内存是由系统实际提供的存储单元（常指字节）组成的一个连续地址空间，处理器可直接存取。外存（辅存）是指软盘、硬盘、光盘和磁带等一些外部存储部件，常用来存放暂不执行的程序和数据。处理器不能直接访问外存，需通过启动 I/O （Input/Output，输入/输出）设备才能进行内存、外存交换，其访问速度慢，但价格便宜，常用作内存的后援设备。

内存大小由系统硬件决定，存储容量受到实际存储单元的限制。虚拟存储器（简称虚存）不考虑实际内存的大小和数据存取的实际地址，只考虑相互有关的数据之间的相对位置，其容量由计算机地址的位数决定。

系统中内存的使用一般分成两部分，一部分为系统空间，存放操作系统本身及相关的系统程序；另一部分为用户空间，存放用户的程序和数据。

存储管理主要是指对内存储器的管理，负责对内存的分配和回收、内存的保护和内存的扩充。存储管理的目的是尽量提高内存的使用效率。存储管理的机制经历了多次变迁，由以前的单一连续区管理到分区存储管理再发展为段页式管理。目前前两种技术已逐步被淘汰，下面我们将详细解读段页式存储管理。

页式存储管理

分页的基本思想是把程序的逻辑空间和内存的物理空间按照同样的大小划分成若干页面，并以页面为单位进行分配。在页式存储管理中，系统中虚地址是一个有序对（页号，位移）。系统为每一个进程建立一个页表，其内容包括进程的逻辑页号与物理页号的对应关系、状态等。

页式系统的动态地址转换是这样进行的：当进程运行时，其页表的首地址已在系统的动态地址转换机构中的基本地址寄存器中。执行的指令访问虚存地址（p，d）时，首先根据页号p查页表，由状态可知，这个页是否已经调入内存。若已调入内存，则得到该页的内存位置p'，然后，与页内相对位移d组合，得到物理地址r。如果该页尚未调入内存，则产生缺页中断，以装入所需的页，如图2-5所示。

页式虚拟存储管理是在页式存储管理的基础上实现虚拟存储器的。首先把作业信息作为副本存放在磁盘上，作业执行时，把作业信息的部分页面装入内存储器，作业执行时若所访问的页面已在内存中，则按页式存储管理方式进行地址转换，得到欲访问的内存绝对地址，若欲访问的页面不在内存中，则产生一个“缺页中断”，由操作系统把当前所需的页面装入内存储器中。

为此，在装入作业时，就应在该作业的页表中指出哪些页已在内存储器中，哪些页还没有装入内存。可用一个标志位指示对应页是否在内存储器，可假设标志位为1表示该页在内存，而标志位为0表示该页尚未装入内存。为了能方便地从磁盘上找到作业信息的副本，故在页表中还可指出每一页副本在磁盘上的位置。

当要装入一个当前需要的页面时，如果内存储器中无空闲块，则可选择一个已在内存储器中的页面，把它暂时调出内存。若在执行中该页面被修改过，则把该页信息重新写回到磁盘上，否则不必重新写回磁盘。当一页被暂时调出内存后，让出的内存空间用来存放当前需要使用的页面。以后再使用被调出的页面时，可用同样的方法调出另一个页面而将其再装入内存。页面被调出或装入之后都要对页表中的相应表目做修改。

当内存中无空闲块时，为了装入一个页面而必须按某种算法从已在内存的页中选择一页，将它暂时调出内存，让出内存空间以存放所需装入的页面，这个工作称为“页面调度”。如何选择调出的页面是很重要的，如果采用了一个不合适的算法，就会出现这样的现象：刚被调出的页面又立即要用，因而又要把它装入，而装入不久又被选中调出，调出不久又被装入，如此反复，使调度非常频繁。这种现象称为“抖动”。一个好的调度算法应减少或避免抖动现象。常用的页面调度算法有：
- 最优（OPT）算法。选择不再使用或最远的将来才被使用的页，这是理想的算法，但是难以实现，常用于淘汰算法的比较。
- 随机（RAND）算法。随机地选择被淘汰的页，开销小，但是可能选中立即就要访问的页。
- 先进先出算法。选择在内存驻留时间最长的页似乎合理，但可能淘汰掉频繁使用的页。另外，使用 FIFO算法时，在未给予进程分配足够的页面数时，有时会出现给予进程的页面数增多，缺页次数反而增加的异常现象。FIFO算法简单，易实现。可以把装入内存储器的那些页的页号按进入的先后顺序排成队列，每次总是调出队首的页，当装入一个新页后，把新页的页号排到队尾。
- 最近最少使用（Least Recently Used ，LRU）算法。选择离当前时间最近的一段时间内使用得最少的页。这个算法的主要出发点是，如果某个页被访问了，则它可能马上就要被访问；反之，如果某个页长时间未被访问，则它在最近一段时间也不会被访问。
段式存储管理

段式存储管理与页式存储管理相似。分段的基本思想是把用户作业按逻辑意义上有完整意义的段来划分，并以段为单位作为内外存交换的空间尺度。

一个作业是由若干个具有逻辑意义的段（如主程序、子程序、数据段等）组成。分段系统中，容许程序（作业）占据内存中许多分离的分区。每个分区存储一个程序分段。这样，每个作业需要几对界限地址寄存器，判定访问地址是否越界也就更困难了。在分段存储系统中常常利用存储保护键实现存储保护。分段系统中虚地址是一个有序对（段号，位移）。系统为每个作业建立一个段表，其内容包括段号、段长、内存起始地址和状态等。状态指出这个段是否已调入内存，即内存起始地址指出这个段，状态指出这个段的访问权限。

分段系统的动态地址转换是这样进行的：进程执行时，其段表的首地址已在基本地址寄存器中，执行的指令访问虚存（s ，d）（取指令或取操作数）时，首先根据段号s 查段表，若段已经调入内存，则得到该段的内存起始地址，然后与段内相对地址（段内偏移量 d）相加，得到实地址。如果该段尚未调入内存，则产生缺段中断，以装入所需要的段。段式存储与页式存储的地址转换方式类似，参看图1-6。段式虚拟存储管理仍然以段式存储管理为基础，为用户提供比内存实际容量大的虚拟空间。段式虚拟存储管理把作业中的各个分段信息都保留在磁盘上，当作业可以投入执行时，做如下操作：
- 首先把当前需要的一段或几段装入内存。
- 作业执行时，如果要访问的段已经在内存，则按照“段式存储管理”中的方式进行地址转换；如果要访问的段不在内存中，则产生一个“缺段中断”，由操作系统把当前需要的段装入内存。
因此，在段表中应增设段是否在内存的标志以及各段在磁盘上的位置，已在内存中的段仍要指出该段在内存中的起始地址和占用内存区长度。

作业执行要访问的段时，由硬件的地址转换机构查段表。若该段在内存中，则立即把逻辑地址转换成绝对地址；若该段不在内存中，则形成“缺段中断”，由操作系统处理这个中断。

处理的办法是，查内存分配表，找出一个足够大的连续区以容纳该分段，如果找不到足够大的连续区则检查空闲区的总和，若空闲区总和能满足该段要求，那么进行适当移动将分散的空闲区集中；若空闲区总和不能满足该段要求，可把内存中的一段或几段调出，然后把当前要访问的段装入内存中。段被移动、调出和装入后都要对段表中的相应表目做修改。新的段被装入后应让作业重新执行被中断的指令，这时就能找到要访问的段，也可以继续执行下去。
段页式存储管理

段页式管理是段式和页式两种管理方法结合的产物，综合了段式组织与页式组织的特点，根据程序模块分段，段内再分页，内存被分划成定长的页。段页式系统中虚地址形式是（段号、页号、页内偏移），如图2-6所示。系统为每个进程建立一个段表，为每个段建立一个页表。段页式管理采用段式分配、页式使用的方法，便于动态连接和存储的动态分配。这种存储管理能提高内存空间的利用率。

段式虚拟管理还是以段为单位分配内存空间，整段的调出、装入，有时还要移动，这些都增加了系统的开销。如果按段页式存储管理的方式，把每一段再分成若干页面，那么，每一段不必占用连续的存储空间；甚至当内存块不够时，可只将一段中的部分页面装入内存，这种管理方式称为“段页式虚拟存储管理”。

段页式虚拟存储管理为每一个装入内存的作业建立一张段表，还要为每一段建立页表。段表中指出该段的页表存放位置及长度，页表中应指出该段的各页在磁盘上的位置以及页是否在内存中，若在内存中则填上占用的内存块号。作业执行时按段号查段表，找到相应的页表再根据页号查页表，由标志位判定该页是否已在内存，若是，则进行地址转换；否则进行页面调度。地址转换过程如图2-7所示。

段页式虚拟存储管理结合了段式和页式的优点，但增加了设置表格（段表、页表）和查表等开销，段页式虚拟存储器一般只在大型计算机系统中使用。

2.2.3.设备管理

在计算机系统中，除了处理器和内存之外，其他的大部分硬设备称为外部设备。它包括输入/输出设备，辅存设备及终端设备等。这些设备种类繁多，特性各异，操作方式的差异很大，从而使操作系统的设备管理变得十分繁杂。在架构师考试中，设备管理需要掌握的知识内容较少，主要为两个方面：

数据传输控制方式

设备管理的主要任务之一是控制设备和内存或CPU之间的数据传送，本节介绍几种常用的数据传送控制方式。选择和衡量控制方式的原则如下：
- 数据传送速度足够高，能满足用户的需要但又不丢失数据。
- 系统开销小，所需的处理控制程序少。
- 能充分发挥硬件资源的能力，使得I/O设备尽量处于使用状态中，而CPU等待时间少。
外围设备和内存之间常用的数据传送控制方式主要有以下几种：
- 程序控制方式。处理器启动数据传输，然后等设备完成。
- 中断方式。程序控制方式不能实现并发。中断方式的数据传输过程是这样的，进程启动数据传输（如读）后,该进程放弃处理器，当数据传输完成，设备控制器产生中断请求，中断处理程序对数据传输工作处理之后，让相应进程成为就绪状态。以后，该进程就可以得到所需要的数据。
- 直接存储访问（Direct Memory Access ，DMA）方式。指外部设备和内存之间开辟直接的数据交换通路。除了控制状态寄存器和数据缓冲寄存器外，DMA控制器中还包括传输字节计数器、内存地址寄存器等。DMA方式采用窃取（或挪用）处理器的工作周期和控制总线而实现辅助存储器和内存之间的数据交换。有的DMA方式也采用总线浮起方式传输大批量数据。
- 通道方式。通道又称为输入/输出处理器（Input/Output Processor ，IOP），可以独立完成系统交付的输入/输出任务，通过执行自身的输入/输出专用程序（称通道程序）进行内存和外设之间的数据传输。主要有3种通道：字节多路通道、选择通道和成组多路通道。
虚设备与SPOOLING技术

采用假脱机技术，可以将低速的独占设备改造成一种可共享的设备，而且一台物理设备可以对应若干台虚拟的同类设备。假脱机（Simultaneous Peripheral Operation On Line,SPOOLING）的意思是外部设备同时联机操作，又称为假脱机输入/输出操作，采用一组程序或进程模拟一台输入/输出处理器。

SPOOLING系统的组成如图2-8所示。该技术利用了专门的外围控制机将低速I/O设备上的数据传送到高速设备上，或者相反。但是当引入多道程序后，完全可以利用其中的一道程序来模拟脱机输入时的外围控制机的功能，把低速的I/O设备上的数据传送到高速磁盘上；再利用另一道程序来模拟脱机输出时外围控制机的功能，把高速磁盘上的数据传送到低速的I/O设备上。这样便可以在主机的控制下实现脱机输入、输出的功能。此时的外围操作与CPU对数据的处理同时进行。

采用假脱机技术，可以将低速的独占设备改造成一种可共享的设备，而且一台物理设备可以对应若干台虚拟的同类设备。SPOOLING系统必须有高速、大容量并且可随机存取的外存（例如，磁盘或磁鼓）支持。

2.2.4.文件管理

操作系统对计算机的管理包括两个方面：硬件资源和软件资源。硬件资源的管理包括CPU的管理、存储器的管理、设备管理等，主要解决硬件资源的有效和合理利用问题。

软件资源包括各种系统程序、各种应用程序、各种用户程序，也包括大量的文档材料、库函数等。每一种软件资源本身都是具有一定逻辑意义的相关信息的集合，在操作系统中它们以文件形式存储。

计算机系统的重要作用之一是能快速处理大量信息，因此数据的组织、存取和保护成为一个极重要的内容。文件系统是操作系统中组织、存取和保护数据的一个重要部分。

文件管理的功能包括：建立、修改、删除文件；按文件名访问文件；决定文件信息的存放位置、存放形式及存取权限；管理文件间的联系及提供对文件的共享、保护和保密等。允许多个用户协同工作又不引起混乱。文件的共享是指一个文件可以让多个用户共同使用，它可以减少用户的重复性劳动，节省文件的存储空间，减少输入/输出文件的次数等。文件的保护主要是为防止由于错误操作而对文件造成的破坏。文件的保密是为了防止未经授权的用户对文件进行访问。

文件的保护、保密实际上是用户对文件的存取权限控制问题。一般为文件的存取设置两级控制：第1级是访问者的识别，即规定哪些人可以访问；第2级是存取权限的识别，即有权参与访问者可对文件执行何种操作。

文件的逻辑结构

文件的结构是指文件的组织形式，从用户角度所看到的文件组织形式，称为文件的逻辑结构。
文件的逻辑组织是为了方便用户使用。一般文件的逻辑结构可以分为两种：无结构的字符流文件和有结构的记录文件。记录文件由记录组成，即文件内的信息划分成多个记录，以记录为单位组织和使用信息。
记录文件有顺序文件、索引顺序文件、索引文件和直接文件。
文件的物理结构

文件的物理结构是指文件在存储设备上的存放方法。文件的物理结构侧重于提高存储器的利用效率和降低存取时间。文件的存储设备通常划分为大小相同的物理块，物理块是分配和传输信息的基本单位。文件的物理结构涉及文件存储设备的组块策略和文件分配策略，决定文件信息在存储设备上的存储位置。常用的文件分配策略有：
- 顺序分配（连续分配）。这是最简单的分配方法。在文件建立时预先分配一组连续的物理块，然后，按照逻辑文件中的信息（或记录）顺序，依次把信息（或记录）按顺序存储到物理块中。这样，只需知道文件在文件存储设备上的起始位置和文件长度，就能进行存取，这种分配方法适合于顺序存取，在连续存取相邻信息时，存取速度快。其缺点是在文件建立时必须指定文件的信息长度，以后不能动态增长，一般不宜用于需要经常修改的文件。
- 链接分配（串联分配）。这是按单个物理块逐个进行的。每个物理块中（一般是最后一个单元）设有一个指针，指向其后续连接的下一个物理块的地址，这样，所有的物理块都被链接起来，形成一个链接队列。在建立链接文件时，不需要指定文件的长度，在文件的说明信息中，只需指出该文件的第一个物理块块号，而且链接文件的文件长度可以动态地增长。只调整物理块间的指针就可以插入或删除一个信息块。链接分配的优点是可以解决存储器的碎片问题，提高存储空间利用率。由于链接文件只能按照队列中的链接指针顺序查找，因此搜索效率低，一般只适用于顺序访问，不适用于随机存取。
- 索引分配。这是另一种对文件存储不连续分配的方法。采用索引分配方法的系统，为每一个文件建立一张索引表，索引表中每一表项指出文件信息所在的逻辑块号和与之对应的物理块号。
索引分配既可以满足文件动态增长的要求，又可以方便而迅速地实现随机存取。对一些大的文件，当索引表的大小超过一个物理块时，会发生索引表的分配问题。一般采用多级（间接索引）技术，这时在由索引表指出的物理块中存放的不是文件存放处而是存放文件信息的物理块地址。这样，如果一个物理块能存储n个地址，则一级间接索引将使可寻址的文件长度变成n2块，对于更大的文件可以采用二级甚至三级间接索引（例如，UNIX操作系统采用三级索引结构，如图 2-9所示）。

索引文件的优点是既适用于顺序存取，又适用于随机存取。缺点是索引表增加了存储空间的开销。另外，在存取文件时需要访问两次磁盘，一次是访问索引表，另一次是根据索引表提供的物理块号访问文件信息。为了提高效率，一种改进的方法是，在对某个文件进行操作之前，预先把索引表调入内存。这样，文件的存取就能直接从内存的索引表中确定相应的物理块号，从而只需要访问一次磁盘。
文件存储设备管理

文件存储设备管理，就是操作系统要有效地进行存储空间的管理。由于文件存储设备是分成许多大小相同的物理块，并以块为单位交换信息，因此，文件存储设备的管理实质上是对空闲块的组织和管理问题。它包括空闲块的组织，空闲块的分配与空闲块的回收等问题。有3种不同的空闲块管理方法，它们分别是索引法、链接法和位示图法。
- 索引法：索引法把空闲块作为文件并采用索引技术。为了有效，索引对应于一个或由几个空闲块构成的空闲区。这样，磁盘上每一个空闲块区都对应于索引表中一个条目，这个方法能有效地支持每一种文件分配方法。
- 链接法：链接法使用链表把空闲块组织在一起，当申请者需要空闲块时，分配程序从链首开始摘取所需的空闲块。反之，管理程序把回收的空闲块逐个挂入队尾，这个方法适用于每一种文件分配方法。空闲块的链接方法可以按释放的先后顺序链接，也可以按空闲块区的大小顺序链接。后者有利于获得连续的空闲块的请求，但在分配请求和回收空闲块时系统开销多一点。
- 位示图法。该方法是在外存上建立一张位示图（Bitmap），记录文件存储器的使用情况。每一位仅对应文件存储器上的一个物理块，取值0和1分别表示空闲和占用。文件存储器上的物理块依次编号为：0、1、2、…。假如系统中字长为32位，有4096个物理块，那么在位示图中的第1个字对应文件存储器上的0、1、2、…、31号物理块；第2个字对应文件存储器上的32、33、34、…、63号物理块；第128字对应文件存储器上的4064、4065 、…、4095 号物理块。这样位示图的大小为32字。
位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况，如图2-10所示。当其值为“0”时，表示对应的盘块空闲；为“1”时表示已分配。由所有盘块对应的位构成一个集合，称为位示图。位示图也可描述为一个二维数组map：Varmap:array[1 ．…m,1 ．…n]ofbit;
树型目录结构

在计算机的文件系统中，一般采用树型目录结构。在树型目录结构中，树的根结点为根目录，数据文件作为树叶，其他所有目录均作为树的结点。

根目录隐含于一个硬盘的一个分区中，根目录在最顶层。它包含的子目录是一级子目录。每一个一级子目录又可以包含若干二级子目录，…，这样的组织结构就叫作目录树。

当前盘和当前目录是系统默认的操作对象。如果用户没有指明操作对象，系统就将用户命令指向当前盘和当前目录。

路径是指从根目录或者当前目录开始到访问对象（目录或者文件），在目录树中路经的所有目录的序列。例如“c:\dos\lmouse\mouse”就是Windows系统中的一条路径。在树型目录结构中，从根目录到任何数据文件之间，只有一条唯一的通路，从树根开始，把全部目录文件名与数据文件名，依次用“/”（UNIX/Linux系统）或“\”（Windows系统）连接起来，构成该数据文件的路径名，且每个数据文件的路径名是唯一的。这样，便可以解决文件重名问题。

从树根开始的路径为绝对路径，如果文件系统有很多级时，使用不是很方便，所以引入相对路径，即从当前目录开始，再逐级通过中间的目录文件，最后到达所要访问的数据文件。

绝对路径给出文件或目录位置的完全描述，通常由层次结构的顶端开始（根目录），通常第一个字符是“/”（UNIX/Linux系统）或者是盘符（Windows系统）。相对路径通常由目录结构中的当前位置开始，一般都比绝对路径要短。

父目录是指当前路径的上一层目录。每个目录下都有代表当前目录的“.”文件和代表当前目录父目录的“..”文件，相对路径名一般就是从“..”开始的。

2.2.5.作业管理

从用户的角度看，作业是系统为完成一个用户的计算任务（或一次事务处理）所做的工作总和。例如，对于用户编制的源程序，需经过对源程序的编译、连接编辑或连接装入及运行产生计算结果。这其中的每一个步骤，常称为作业步，作业步的顺序执行即完成了一个作业。

从系统的角度看，作业则是一个比程序更广的概念。它由程序、数据和作业说明书组成。系统通过作业说明书控制文件形式的程序和数据，使之执行和操作。而且，在批处理系统中，作业是占据内存的基本单位。

用户的作业可以通过直接的方式，由用户自己按照作业步顺序操作；也可以通过间接的方式，由用户率先编写的作业步依次执行的说明，一次交给操作系统，由系统按照说明依次处理。前者称为联机方式，后者称为脱机方式。

作业状态及其转换

一个作业从交给计算机系统到执行结束退出系统，一般都要经历提交、后备、执行和完成4个状态。其状态转换如图2-11所示。
- 提交状态。作业由输入设备进入外存储器（也称输入井）的过程称为提交状态。处于提交状态的作业，其信息正在进入系统。
- 后备状态。当作业的全部信息进入外存后，系统就为该作业建立一个作业控制块（Job Control Block，JCB）。系统通过JCB感知作业的存在。JCB主要内容包括作业名、作业状态、资源要求、作业控制方式、作业类型及作业优先权等。
- 执行状态。一个后备作业被作业调度程序选中而分配了必要的资源并进入了内存，作业调度程序同时为其建立了相应的进程后，该作业就由后备状态变成了执行状态。
- 完成状态。当作业正常运行结束，它所占用的资源尚未全部被系统回收时的状态为完成状态。
用户接口

用户接口也称为用户界面，其含义有两种，一种是指用户与操作系统交互的途径和通道，即操作系统的接口；另一种是指这种交互环境的控制方式，即操作环境。
- 操作系统的接口。操作系统的接口又可分成命令接口和程序接口。命令接口包含键盘命令和作业控制命令；程序接口又称为编程接口或系统调用，程序经编程接口请求系统服务，即通过系统调用程序与操作系统通信。系统调用是操作系统提供给编程人员的唯一接口。系统调用对用户屏蔽了操作系统的具体动作而只提供有关功能。系统调用大致分为设备管理、文件管理、进程控制、进程通信和存储管理等。
- 操作环境。操作环境支持命令接口和程序接口，提供友好的、易用的操作平台。操作系统的交互界面已经从早期的命令驱动方式，发展到菜单驱动方式、图符驱动方式和视窗操作环境。

代码匠心