三、操作系统

（一）概述

操作系统是管理整个系统的软、硬件资源的系统，既是人和硬件之间的一种接口，也是应用软件与硬件之间的接口。

（二）进程管理

1.进程的状态

进程的状态是操作系统对进程进行管理的时候设置的几种状态，进程的状态有三种：

就绪：除了 CPU 资源，其它资源都已具备。
运行：具备所有资源，包含 CPU 资源。
等待：除了缺少 CPU 资源，还缺少其它起源。

2.前趋图

前趋图在考试中经常考到，往往和 PV 图结合起来考察。

3.进程的同步与互斥

进程的同步与互斥是进行 PV 操作的前提。注意：同步的反义词是异步，互斥的反义词是共享，所以同步与互斥并不是互为反义词。

进程的互斥：在同一时刻，只允许某一个进程使用该资源，即一个资源不能同时服务于多个进程。当一个进程占用了某个资源时，其它进程就不能使用该资源，就需要等待。
进程的同步：在多道程序环境下，进程是并发执行的，不同进程之间存在着不同的相互制约关系。

4.PV 操作

PV 操作是一种实现进程互斥与同步的有效方法。PV 操作与信号量的处理相关，P（Passeren）表示通过的意思，V（Vrijgeven）表示释放的意思。PV 操作是典型的同步机制之一。用一个信号量与一个消息联系起来，当信号量的值为 0 时，表示期望的消息尚未产生；当信号量的值非 0 时，表示期望的消息已经存在。用 PV 操作实现进程同步时，调用 P 操作测试消息是否到达，调用 V 操作发送消息。

PV 操作在整个操作系统中是最难的一部分。

从上图中可以看出，P 操作可以阻塞进程，而 V 操作可以激活进程。

下图中，系统里面有两个进程，一个是生产者，一个是消费者。生产者进程为负责生产产品并将产品送到缓冲区，消费者进程为负责从缓冲区中取出产品并将其消费掉。题目中提到的单缓冲区，即只有一个缓冲区（市场）。接下来分别分析没有 PV 操作和有 PV 操作的情况：

（1）假设没有 PV 操作，即没有 P(S1)、P(S2)、V(S2)、V(S1)这些操作。如果首先执行一次生产者进程，即生产一个产品并将产品送到单缓冲区，然后继续执行一次生产者进程，即又生产了一个产品并将产品送到单缓冲区，但是由于单缓冲区已经满了（已经装了上一次生产者进程生产的产品），所以如果继续将产品送到单缓冲区就会导致溢出错误。为了避免以上问题，所以需要 PV 操作。

（2）假设没有 PV 操作，如果首先执行一次消费者进程，即消费者从单缓冲区中取产品，但是此时单缓冲区中并没有任何产品，所以也会导致出错。所以不管是先执行生产者进程，还是先执行消费者进程，都有可能会导致错误。

（3）假设有 PV 操作，按原来的操作方式执行一遍。首先执行生产者进程，生产一个产品，然后执行 P(S1)操作，S1 的初值为 1，执行完 P(S1)操作后 S1=0，判断 S1<0 的结果为 False，所以继续往下执行，即将产品送到单缓冲区中。然后执行 V(S2) 操作，S2 的初值为 0，执行完 V(S2) 操作后 S2=1，判断 S2<=0 的结果为 False，所以继续执行下一步。如果下一步继续执行生产者进程，即生产一个产品，然后执行 P(S1)操作，S1 的值由 0 变成-1，判断 S1<0 的结果为 True，则当前的生产进程就会被放入进程等待队列，并且把当前的状态阻塞起来，所以第二次生产的产品在单缓冲区中的产品（第一次生产）还没有被消费掉之前，是不会再被送入单缓冲区的，就避免了溢出错误。由于生产进程被阻塞，所以现在来看消费者进程的执行情况。执行消费者进程，执行完 P(S2)后 S2 的值由 1 变成 0，判断 S2<0 的结果为 False，所以继续执行下一步，即消费者从单缓冲区中取出产品并消费掉，然后执行 V(S1)后 S1 的值由 -1 变成 0，判断 S1<=0 的结果为 True，则会从进程等待队列中找到一个进程并将其激活，这时候找到的队列就是最开始放入进程等待队列中的生产者进程，激活该进程后就会将生产的产品送到单缓冲区中，然后继续执行 V(S2)后 S2 的值由 0 变成 1，判断 S2<=0 的结果为 False，接着继续执行下一个进程，以此类推。

（4）假设有 PV 操作，如果先执行消费者进程，执行 P(S2)操作后 S2 的值由初值 0 变成-1，判断 S2<0 的结果为 True，所以该进程就会被放入进程等待队列中（即进程被阻塞，因为此时单缓冲区中是空的，没有产品可以被消费），所以也可以避免错误。

如下图所示的 PV 操作实例，解题的关键点是找出约束关系。

5.PV 操作与前趋图

前趋图主要用来表达需要进程的这些活动之间的依赖关系。接下来要将前趋图转为 PV 操作的形式，实际上是把前趋图的每一个活动都转成相应的进程，然后为了保证这些进程在并发执行的时候仍然按照前趋图规定的先后顺序执行。这种类型的题目经常考到，所以必须要掌握。

如下图所示，对于 A、B、C 而言，这三个都是一开始就可以执行，所以不受任何约束。对于 D，如果要执行 D，则必须先要执行完 A 或 B 或 C。对于 E，如果要执行 E，则必须先执行完 A 或 B 或 C，且执行完 D。

如下图所示，先在前趋图中按照从左到右、从上到下的规则依次将信号量 S1、S2、S3、S4 标注在连接线上。S1 所在的连接线的开始位置（P1 执行完）为 V(S1)，结束位置（P3 执行前）为 P(S1)。S2 所在的连接线的开始位置（P2 执行完）为 V(S2)，结束位置（P3 执行前）为 P(S2)。S3 所在的连接线的开始位置（P3 执行完）为 V(S3)，结束位置（P4 执行前）为 P(S3)。S4 所在的连接线的开始位置（P3 执行完）为 V(S4)，结束位置（P5 执行前）为 P(S4)。可以得出，a 就是 P1 执行完即 V(S1)，b 就是 P2 执行完即 V(S2)，c 就是 P3 执行前即 P(S1)和 P(S2)，d 就是 P3 执行完即 V(S3)和 V(S4)，e 就是 P4 执行前即 P(S3)，f 就是 P5 执行前即 P(S4)。

6.死锁问题

死锁是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。

6.1 不发生死锁的最少资源数

如下图所示，假设系统有 5 个资源，A 分配 2 个资源，B 分配 2 个资源，C 分配 1 个资源，肯定会导致出现死锁问题。假设系统有 10 个资源，A 分配 4 个资源，B 分配 4 个资源，C 分配 2 个资源，也会出现死锁问题。如果系统有 13 个资源，则先分别给 A、B、C 每个分配 4 个资源，此时系统还剩 1 个资源，可以分别给 A、B、C 使用，这样就不会导致死锁出现了。当需要求出系统最少需要多少个资源才不会导致死锁时，可以先用每个进程需要的资源数量-1，累加后再加 1 即可得到不发生死锁的最少资源数。例如有 k 个进程，每个进程需要的资源数为 n，则不发生死锁的最少资源数为：k x (n-1) + 1。

6.2 死锁的预防与避免

死锁有四大条件，这四大条件缺一个都不会导致死锁。死锁的四大条件如下：

**互斥条件：**指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直至占有资源的进程用完释放。
**请求和保持条件：**指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。
**不剥夺条件：**指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。
**环路等待条件：**指在发生死锁时，必然存在一个进程—资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0正在等待一个P1占用的资源，P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。

银行家算法是模拟银行房贷的思路，即银行在放贷前，先判断放贷对象是否有偿还能力。

7.存储管理

7.1 分区存储组织

7.2 段页式存储

段式存储

在程序中，是将函数分割成段的，比如将主函数作为一个段，将函数 1 作为一个段，将函数 2 作为另一个段，不同段的段长是可以不同的。

页式存储

在段页式存储中，需要掌握的是页式存储中逻辑地址与物理地址之间的转换。高级程序语言使用逻辑地址，而运行状态内存中使用的是物理地址。

段页式存储

段页式存储是先分段、再分页。

7.3 快表

快表是放在 Cache 中，而放在内存中的成为慢表。

7.4 页面置换算法

页面置换算法广泛应用于分层的存储体系之中。对于 Cache，由于 Cache 的容量有限，当 Cache 的块都被占用，要调入新的块进入 Cache 的时候，就会用到页面置换算法。在页面置换算法中，最常用的两种算法是先进先出（FIFO）算法、最近最少使用（LRU）算法。

8.文件管理

8.1 索引文件结构

标准的索引文件结构一般是有 13 个节点，编号是从 0 到 12。

8.2 文件和树型目录结构

主要考察相对路径和绝对路径的概念。不管是 DOS 系统，还是 Windows 系统、Linux 系统，其文件的目录结构都是树型结构。

8.3 空闲存储空间的管理

主要考察位示图法。位示图中的每一个 bit，对应磁盘上一个物理块的使用状态，取值 0 和 1 分别表示空闲和占用。

9.设备管理

9.1 数据传输控制方式

数据传输控制方式，主要是指内存和外设之间的数据传输控制问题，主要有以下几种方式：

程序控制方式：又称为程序查询方式，是 CPU 介入最多的方式。外设不会主动反馈信息，处于一种非常被动的状态。
程序中断方式：基本上和程序控制方式一样，不同之处在于外设的主动性要强些，当外设完成了数据传输时，会主动发送中断信息。
DMA 方式：又称为直接存储控制方式，有专门的 DMA 控制器。DMA 传输方式是让存储器与外设、或外设与外设之间直接交换数据，不需要经过 CPU 的介入，减少了中间环节，并且内存地址的修改、传送完毕后的结束报告都是由硬件电路实现，因此大大地提高了数据的传输速度。一个 DMA 传送只需要执行一个 DMA 周期，相当于一个总线读写周期。采用 DMA 方式传送数据时，每传送一个数据都需要占用一个总线周期。（2021 年上半年上午题）
通道：用专用计算机来进行控制，所以不在讨论范围内。
输入输出处理机：用专用计算机来进行控制，所以不在讨论范围内。

9.2 虚设备和 Spooling 技术

Spooling 技术的核心思想是在磁盘上设置了一个缓冲区，把要输出或输入的数据先缓存起来，这样就可以解决外设的低速与内设的高速之间的差异。

10.微内核操作系统

微内核由一群尽可能将数量最小化的软件程序组成，它们负责提供实现一个操作系统所需要的各种机制与功能，微内核操作系统就是一种基于微内核架构的操作系统。微内核（Micro kernel）是提供操作系统核心功能的内核的精简版本，它设计成在很小的内存空间内增加移植性，提供模块化设计，以使用户安装不同的接口，如DOS、Workplace OS、Workplace UNIX等。IBM、Microsoft、开放软件基金会(OSF)和UNIX系统实验室(USL)、鸿蒙OS等新操作系统都采用了这一研究成果的优点。