操作系统（2025年春季）

第一章操作系统概论

1.1 绪论

操作系统是伴随着计算机系统的发展，逐步形成、发展和成熟起来的。

1.1.1 操作系统的概念

计算机系统由硬件和软件两部分组成。

硬件

计算机系统中由电子、机械、电气、光学和磁学等元器件构成的各种部件和设备。CPU、存储器及设备都是硬件。

软件

完成一定任务的程序及其数据。包括系统软件及应用软件。系统软件有操作系统、编译程序、编辑程序、数据库管理系统等；应用软件是为各种应用目的而编制的程序。

1.1.2 计算机系统的层次关系

计算机硬件和软件以及软件的各部分之间形成了一种层次结构的关系。
操作系统是配置在计算机硬件上的第一层软件，是对硬件的首次扩充。它位于硬件与其它软件之间，是所有其他软件运行的基础。

1.6.1 命令接口

命令接口进行作业控制的主要方式包括：

脱机控制方式
联机控制方式

无论在哪里，**“机”**指的都是主机

联机命令接口

提供了一组命令供用户请求计算机系统服务。

键盘命令可分为：

内部命令：功能简单程序短小使用频繁常驻内存（初始启动时就被引导）

外部命令：功能复杂程序较长独立驻留磁盘（需要时再从磁盘调入内存）

脱机命令接口

由一组作业控制命令组成。

1.6.2 程序接口

程序接口由一组系统调用命令组成。有时也称为系统调用接口；用户通过在程序中使用这些系统调用命令来请求操作系统提供的服务。

系统调用

由若干条指令构成的过程，用以实现特定的操作系统服务功能。

系统调用分类

系统调用处理程序执行过程

系统调用与过程调用的区别

1.6.3 图形用户接口

图形用户接口是通过对出现在屏幕上的对象直接进行操作，以控制和操纵程序的运行。

1.7 操作系统运行环境和内核结构

1.7.1 操作系统的运行环境

计算机硬件所提供的支持，构成了现代操作系统的运行环境。包括：

处理机
存储器
设备
时钟
中断

1.7.2 操作系统的内核结构

操作系统是一个大型系统软件，其内核结构主要有三种：

模块结构 module
层次结构 layer
微内核结构 microkernel

模块结构

将操作系统内核按照功能划分为一个个独立的模块，模块之间相对独立，只能通过事先规定好的接口方式来调用。

模块结构效率高但访问控制困难结构不清晰

如：Linux

层次结构

将操作系统内核按照一定的规则划分为一系列相互依赖的层次，每个层次也可以分解为一系列更小的模块。

调用关系变得有序可以换掉某层，便于移植和扩充牺牲一定的灵活性

微内核结构

将操作系统中的内存管理、设备管理、文件管理等高级服务功能尽可能从内核分离出来，变成几个独立的非内核模块

降低了开发难度较好的扩展性及移植性效率较低

如：现在的Windows

第二章进程和线程

**进程（process）**是资源分配的基本单位，也是独立运行的基本单位。

2.1 进程的引入

为了描述并发程序执行时的特征，引入了进程。

2.1.1 前驱图

前趋图是一个有向无循环图，用于描述程序、程序段或语句执行的先后次序。

图中的每个结点可以表示一条语句、一个程序段或一个进程，结点间的有向边表示两个结点之间存在的前趋关系“→”：

$→={(Pi，Pj)│Pi必须在Pj开始执行之前完成}$

如果$(Pi，Pj)∈→$，可以写成$Pi→Pj$，则称$Pi$是$Pj$的直接前趋，$Pj$是$Pi$的直接后继。
若存在一个序列$Pi→Pj→…→Pk$，则称$Pi$是$Pk$的前趋。
在前趋图中，没有前趋的结点称为初始结点，没有后继的结点称为终止结点。

2.1.2 程序的顺序执行

一个程序通常由若干个程序段所组成，它们必须按照某种先后次序来执行，仅

当前一个操作执行完后才能执行后继操作，这类计算过程就是程序的顺序执行过程。

先输入→再计算→最后输出，即：$I→C →P$。

程序顺序执行时的特征

顺序性：处理机的操作严格按照程序所规定的顺序执行，即每一个操作必须在下一个操作开始之前结束。
封闭性：程序一旦开始运行，其执行结果不受外界因素影响。
可再现性：只要程序执行时的初始条件和执行环境相同，当程序重复执行时，都将获得相同的结果。

2.1.3 程序的并发执行及特点

程序的并发执行是指若干个程序（或程序段）同时在系统中运行，这些程序（或程序段）的执行在时间上是重叠的，一个程序（或程序段）的执行尚未结束，另一个程序（或程序段）的执行已经开始。

重叠—可以不是同时

进程1、2、3并发执行。对每个进程而言，其输入、计算和输出这三个操作必须顺序执行。它们之间存在如下先后关系：，$I_2$和$C_1$，$I_3、C_2$和$P_1$可以并发。

并发执行的特征

间断性：并发程序具有*“执行—暂停—-执行”*这种间断性的活动规律。
失去封闭性：多个程序共享系统中的资源，这些资源的状态将由多个程序来改变，致使程序之间相互影响。
不可再现性：在初始条件相同的情况下，程序的执行结果依赖于执行的次序。

与时间有关的错误例：

程序并发执行时可能出现与时间有关的错误，如：

进程1： r1=x； 进程2： r2=x；

r1++； r2++；

x=r1； x=r2；

设在两进程运行之前，x的值为0。则两进程运行结束后，x值可为：1或2

并发执行的条件

**读集：**语句执行期间要引用的变量集合，记为$R（Si）={a1，…，am}$
**写集：**语句执行期间要改变的变量集合，记为$W（Si）={b1，…，bn}$
$R (S_i) ∩ W (S_j) ={ }$ ——不同时读写，保证两次读之间数据不变
$R (S_j) ∩ W (S_i) ={ }$ ——同上
$W (S_i) ∩ W (S_j) ={ }$ ——保证写操作结果不丢失

2.2 进程的定义

为了描述并发执行程序的动态特性，人们引入了一个新的概念——进程（process）。

CALLBACK：为了描述并发程序执行时的特征，引入了进程。

2.2.1 进程许多等价的定义

进程有多种定义，下面列举一些有代表性的定义：

进程是程序在处理器上的一次执行过程。

进程是可以和别的计算并行执行的计算。

进程是程序在一个数据集合上运行的过程，是系统进行资源分配和调度的一个独立单位。

进程是一个具有一定功能的程序关于某个数据集合的一次运行活动。

KEYWORD:执行、运行、活动

[!NOTE]

进程是系统资源分配和调度的一个独立单位。

2.2.2 进程的特征

动态性：进程是程序的一次执行过程。动态性还表现为它因创建而产生，因调度而执行，因无资源而暂停，因撤消而消亡。

而程序是静态实体。
并发性：多个进程实体同时存在于内存中，能在一段时间内同时运行。
独立性：在传统OS中，进程是独立运行的基本单位，也是系统分配资源和调度的基本单位。
异步性：也叫制约性，进程以各自独立的不可预知的速度**向前推进。
结构性：进程实体由程序段、数据段及进程控制块组成，又称为进程映像。**

进程由：1.程序段 2.数据段 3.进程控制块（PCB）组成

2.2.3 进程与程序的关系

进程是动态概念，程序是静态概念；进程是程序在处理机上的一次执行过程，而程序是指令的集合。

*进程是暂时的，程序是永久的。*进程是一个状态变化的过程；程序可以长久保存。
进程与程序的组成不同。进程的组成包括程序（段）、数据和进程控制块。
进程与程序是密切相关的。一个程序可以对应多个进程；一个进程可以包括多个程序。
进程可以创建新进程，而程序不能形成新程序。

2.2.4 进程控制块

PCB （Process control block）是描述和管理进程的数据结构。它是进程实体的一部分，操作系统通过PCB感知进程的存在，PCB是进程存在的唯一标志。

不同操作系统中进程控制块的结构不同，但通常包括下面所列出的内容：

唯一标识进程的一个标识符或整数。
进程当前状态：说明进程当前所处状态。
进程队列指针：用于记录PCB队列中下一个PCB的地址。
程序和数据地址：进程的程序和数据在内存或外存中的存放地址。
进程优先级：反映进程获得CPU的优先级别。
CPU现场保护区：CPU现场信息的存放区域，包括：通用寄存器、程序计数器、程序状态字等。
通信信息：进程与其他进程所发生的信息交换。
家族关系：指明本进程与家族的关系，如父子进程标识。
资源清单：列出进程所需资源及当前已分配资源。

2.3 进程的状态及转换

为了刻画进程的动态特征，可以将进程的生命期划分为一组状态，用这些状态来描述进程的活动过程。

2.3.1 进程的三种基本状态

就绪状态：“万事俱备，只欠CPU”。进程已获得除处理机以外的所有资源，一旦分配了处理机就可以立即执行。
执行状态：又称运行状态。一个进程获得必要的资源并正在处理机上执行。
阻塞状态：又称等待状态、睡眠状态。正在执行的进程，由于发生某事件而暂时无法执行下去（如等待输入/输出完成）。这时即使把处理机分配给该进程，它也无法运行。

[!NOTE]

就绪态不能转换为阻塞态： 因为阻塞态是处于运行态的进程在运行时主动执行造成阻塞的代码而导致的：

在程序执行阻塞I/O中的read、recv等系统调用时，进程将会一直处于阻塞直到数据到来或者到达设定的超时时间。处于就绪态的进程无法执行任何造成其阻塞的代码，故无法转换为阻塞态。

阻塞态不能转换为运行态： 只有被调度的进程才会转入运行态，而只有处于就绪态的进程才会被调度，因此阻塞态必须经过就绪态后才能转换为运行态。

2.3.2 新建状态和终止状态

在许多系统中又增加了两种状态：

新建状态（new）：进程刚刚建立，但还未进入就绪队列。又称创建状态。
终止状态（terminated）：当一个进程正常或异常结束，操作系统已释放它所占用的资源，但尚未将它撤消时的状态，又称退出状态。

其中的阻塞与等待是一个概念。

[!NOTE]

大多数状态不可逆转，如等待不能转换为运行。

状态转换大多为被动进行，但运行→等待是主动的。

一个进程在一个时刻只能处于上述状态之一。

2.3.3 进程的挂起状态

在某些系统中，希望人为将进程挂起使之处于静止状态，进程挂起的原因有：

**系统故障或功能受到破坏：**先挂起，故障消除后再恢复。
**检查中间结果：**挂起进程以便检查。

**资源不足：**挂起进程以腾出资源。
**内存不足：**在外存挂起。

[!NOTE]

挂起与阻塞的区别：

挂起是一种主动行为，因此恢复也应该要主动完成。而阻塞是一种被动行为，是在等待事件或者资源任务的表现，你不知道它什么时候被阻塞，也不清楚它什么时候会恢复阻塞。

阻塞（pend）就是任务释放CPU，其他任务可以运行，一般在等待某种资源或者信号量的时候出现。挂起（suspend）不释放CPU，如果任务优先级高，就永远轮不到其他任务运行。一般挂起用于程序调试中的条件中断，当出现某个条件的情况下挂起，然后进行单步调试。

因果变迁

如果一个状态变化A的发生，会引起另一个状态变化B的发生，则称A、B之间是因果变迁。

$2\rightarrow4$是因果变迁。

2.4 进程控制

进程控制的职能是对系统中的所有进程实施有效的管理，常见的进程控制功能有进程创建、撤消、阻塞与唤醒等。这些功能一般由操作系统内核原语来实现。

2.4.1 操作系统内核

在操作系统设计中，往往把一些与硬件紧密相关的模块、运行频率较高的模块及公用的一些基本操作安排在靠近硬件的软件层次中，使它们常驻内存，以提高操作系统的运行效率，通常把这部分软件称为操作系统内核。

内核（kernel）主要包括：

中断
时钟管理

进程管理

存储器管理

设备管理

2.4.2 原语(primitive)

原语是由若干条机器指令构成的，用以完成特定功能的一段程序，这段程序在执行期间不可分割。

2.4.3 计算机系统的两种运行状态

核心态(kernel mode)

又称管态、系统态，是操作系统管理程序执行时机器所处的状态。这种状态具有较高的特权，能执行一切指令，访问所有的寄存器和存储区。

用户态(user mode)

又称目态，是用户程序执行时机器所处的状态。这种状态具有较低特权，只能执行规定的指令，访问指定的寄存器和存储区。

2.4.4 进程创建

为描述进程之间的创建关系，引入了进程图。

进程图又称进程树（tree of process）或进程家族树，是描述进程家族关系的一棵有向树。

图中的结点表示进程，若进程A创建了进程B，则从结点A有一条边指向结点B，说明进程A是进程B的父进程，进程B是进程A的子进程。

进程创建原语

导致进程创建的原因有：

**用户登录：**用户登录后，若合法则为用户创建一个进程。

**作业调度：**为调度到的作业分配资源并创建进程。
**OS服务：**创建服务进程。
**应用需要：**应用程序根据需要创建子进程。

设备分配：为已分配的设备分配资源

启动设备：会创建进程

进程创建原语的功能是创建一个新进程，其主要操作过程如下：

向系统申请一个空闲PCB。

为新进程分配资源。如分配内存空间。
初始化新进程的PCB。在其PCB中填入进程名、家族信息、程序和数据地址、进程优先级、资源清单及进程状态等。
将新进程的PCB插入就绪队列。

2.4.5 进程撤销

引起进程撤销的原因有：

正常结束

**异常结束：**超时、内存不足、地址越界、算术错、I/O故障、非法指令等。
**外界干预：**包括操作员或系统干预，父进程请求。

撤消原语采用的两种策略：

撤消指定标识符的进程
撤消指定进程及其所有子孙进程

下面给出后一种撤消策略的功能描述。

撤消原语的功能是撤消一个进程，其主要操作过程如下：

从系统的PCB表中找到被撤消进程的PCB。
检查被撤消进程的状态是否为执行状态，若是则立即停止该进程的执行，设置重新调度标志。
检查被撤消进程是否有子孙进程，若有子孙进程还应撤消该进程的子孙进程。
回收该进程占有的全部资源并回收其PCB。

2.4.6 进程阻塞与唤醒

引起进程阻塞及唤醒的事件：

请求系统服务。

如请求分配打印机，但无空闲打印机则进程阻塞；当打印机重又空闲时应唤醒进程。
启动某种操作并等待操作完成。

如启动I/O操作，进程阻塞；I/O完成则唤醒进程。
等待合作进程的协同配合。

如计算进程尚未将数据送到缓冲区，则打印进程阻塞；当缓冲区中有数据时应唤醒进程。
系统进程无新工作可做。

如没有信息可供发送，则发送请求阻塞；当收到新的发送请求时，应将阻塞进程唤醒。

阻塞原语的主要功能是将进程由执行状态转为阻塞状态。其主要操作过程如下：

停止当前进程的执行；
保存该进程的CPU现场信息；
将进程状态改为阻塞，并插入到相应事件的等待队列中；
转进程调度程序，从就绪队列中选择一个新的进程投入运行。

唤醒原语的主要功能是将进程唤醒，其主要操作过程如下：

当进程等待的事件发生时，由发现者进程将其唤醒。

将被唤醒进程从相应的等待队列中移出；
将进程状态改为就绪，并将该进程插入就绪队列；
转进程调度或返回。

[!NOTE]

阻塞与唤醒的关系：

一个进程由执行状态转变为阻塞状态，是这个进程自己调用阻塞原语去完成的。

进程由阻塞状态转变为就绪状态，是另一个发现者进程调用唤醒原语实现的。

一般发现者进程与被唤醒进程是合作的并发进程。

2.4.7 进程的挂起与激活

挂起原语和激活原语都有多种实现方式，如：

把发出挂起原语的进程自身挂起
挂起具有指定标识符的进程
把某进程及其子孙进程挂起
激活一个具有指定标识名的进程
激活某进程及其子孙进程

下面以挂起或激活具有指定标识符的进程为例，说明这两种原语的主要功能。

挂起原语的主要功能是将指定进程挂起，算法思想如下：

到PCB表中查找该进程的PCB；
检查该进程的状态，若为执行则停止执行并保护CPU现场信息，将该进程状态改为挂起就绪；
若为活动阻塞，则将该进程状态改为挂起阻塞；
若为活动就绪，则将该进程状态改为挂起就绪；
若进程挂起前为执行状态，则转进程调度，从就绪队列中选择一个进程投入运行。

激活原语的主要功能是将指定进程激活。其算法思想如下：

到PCB表中查找该进程的PCB。
检查该进程的状态。若状态为挂起阻塞，则将该进程状态改为活动阻塞。
若状态为挂起就绪，则将该进程状态改为活动就绪。
若进程激活后为活动就绪状态，可能需要转进程调度。

2.5 进程组织

系统中有许多进程，为了能对它们进行有效的管理，应将PCB组织起来。常用的组织方式有：线性方式、链表方式、索引方式。

2.5.1 线性方式

将PCB顺序存放在一片连续内存中。

2.5.2 链接方式

将同一状态的PCB组成一个链表。

2.5.3 索引方式

将同一状态的进程归入一个索引表，再由索引指向相应的PCB

2.6 线程

在操作系统中引入进程的目的是使多道程序能并发执行，以改善资源利用率及提高系统吞吐量；在操作系统中再引入线程，则是为了减少程序并发执行所付出的时空开销，使操作系统具有更好的并发性。

CALLBACK：为了描述并发执行程序的动态特性，人们引入了一个新的概念——进程（process）。

[!NOTE]

**ANYWAY，**进程具有两个属性：

拥有资源的独立单位

调度和分派的基本单位

为使进程并发执行，则必须进行诸如创建、撤消、切换等一系列操作，这些操作涉及到资源管理，所花费的时空开销较大，为此引入了线程。

线程的定义情况与进程类似，存在多种不同的提法。下面列出一些较权威的定义：

线程是进程内的一个执行单元。
线程是进程内的一个可调度实体。
线程是程序（或进程）中相对独立的一个控制流序列。
线程是执行的上下文，其含义是执行的现场数据和其他调度所需的信息（这种观点来自Linux系统）。
线程是进程内一个相对独立的、可调度的执行单元。

KEYWORD：进程内、执行

[!NOTE]

线程自己基本上不拥有资源，只拥有一点在运行时必不可少的资源（如程序计数器、一组寄存器和栈），但它可以与同属一个进程的其他线程共享进程拥有的全部资源。

2.6.1线程的控制

和进程类似，线程也有运行、就绪、阻塞等状态。

**创建：**当创建一个新进程时，也为该进程创建了一个线程。线程还可以创建新线程。
**就绪：**线程已获得除处理机外的所有资源。
**运行：**线程正在处理机上执行。
**阻塞：**线程因等待某事件而暂停运行。
**终止：**一个线程已完成。

线程的同步与通信与进程类似。进程的挂起及终止将影响到其中的所有线程，进程中的线程具有：

执行状态
线程上下文
执行栈
线程静态存储局部变量
寄存器及对所属进程资源的访问

2.6.2 多线程

指一个进程中有多个线程，这些线程共享该进程的状态和资源，它们驻留在同一地址空间，并且可以访问到相同的数据。

2.6.3 线程的实现

操作系统中有多种方式实现对线程的支持。

内核级线程

内核级线程是指依赖于内核，由操作系统内核完成创建和撤消工作的线程，在支持内核级线程的OS中，内核维护进程和线程的上下文信息并完成线程切换。一个内核级线程阻塞时不会影响其他线程的运行。处理机时间分配的对象是线程，所以有多个线程的进程将获得更多处理机时间。

用户级线程

用户级线程是指不依赖于操作系统核心，由应用进程利用线程库提供创建、同步、调度和管理线程的函数来控制的线程。其维护由应用进程完成，可以用于不支持内核级线程的操作系统当一个线程阻塞时，整个进程都必须等待，处理机时间是分配给进程的，进程内有多个线程时，每个线程的执行时间相对少一些。

[!NOTE]

在有些系统中，提供了上述两种方法的组合实现。在这种系统中，内核支持多线程的建立、调度与管理；同时，系统中又提供使用线程库的便利，允许用户应用程序建立、调度和管理用户级的线程。因此可以很好地将内核级线程和用户级线程的优点结合起来。由此产生了不同的多线程模型。

一对一模型

每个用户级线程映射到一个内核级线程上。

多对一模型

多个用户级线程映射到一个内核级线程上

多对多模型

多个用户级线程映射到较少或相等个数的内核级线程上。

2.6.4 进程与线程的比较

**调度：在传统OS中，**进程是调度和分配资源的基本单位；引入线程后，线程是调度和分派的基本单位，进程是拥有资源的基本单位。
**拥有资源：**进程是拥有资源的基本单位，由一个或多个线程及相关资源构成。
**并发性：**进程之间可以并发执行，同一进程中的各线程之间也可以并发执行。
系统开销：进程创建、撤销及切换的开销大于线程。而同一进程的线程间同步与通信开销小。

[!CAUTION]

两个基本单位：线程是调度和分派的基本单位，进程是拥有资源的基本单位。

第三章进程的同步与通信

在多道程序系统中，进程之间的相互制约关系体现在如下两个方面：

**直接制约关系：**合作进程之间产生的制约关系。

**间接制约关系：**共享资源产生的制约关系。

3.1 同步与互斥的概念

3.1.1 临界资源与临界区

临界资源：一段时间内仅允许一个进程使用的资源称为临界资源。如：打印机、共享变量。

临界区（critical section）：进程中访问临界资源的那段代码称为临界区，又称临界段。

同类临界区：所有与同一临界资源相关联的临界区。

[!NOTE]

访问临界资源应遵循的原则:

空闲让进：若无进程处于临界区时，应允许一个进程进入临界区。

忙则等待：当已有进程进入临界区，其他进程必须等待。

有限等待：应保证要求进入临界区的进程在有限时间内进入临界区。

让权等待：当进程不能进入自己的临界区时，应释放处理机。

[!NOTE]

临界资源访问过程

进入区

临界区

退出区

剩余区

3.1.2 同步与互斥

同步（Synchronization）：多个相互合作的进程在一些关键点上可能需要互相等待或互相交换信息，这种相互制约关系称为进程同步。

计算进程与打印进程共享一个单缓冲区。

**互斥（ Mutual Exclusion）：**当一个进程正在使用某资源时，其他希望使用该资源的进程必须等待，当该进程用完资源并释放后，才允许其他进程去访问此资源，我们称进程之间的这种相互制约关系为互斥。

3.2 互斥的实现方法

互斥的实现既有硬件方法也有软件方法，下面将对进程互斥的一些实现方法进行介绍。

3.2.1 互斥算法

有两个进程P0和P1互斥地共享某个临界资源。

P0和P1是循环进程，它们执行一个无限循环程序，每次使用该资源一个有限的时间间隔。

算法1

设置一个公用整型变量turn，用来指示允许进入临界区的进程标识。
若turn为0，则允许进程P0进入临界区；否则循环检查该变量，直到turn变为本进程标识；
在退出区，修改允许进入进程的标识为1。进程P1的算法与此类似。

int turn＝0；
P0：{ 
         do {
                  while （turn!=0）；
                  进程P0的临界区代码CS0 ；
                  turn＝1 ；
                  进程P0的其他代码；
              } while (true)
       }
P1：{ 
         do {
                  while （turn!=1）；
                  进程P1的临界区代码CS1 ；
                  turn＝0 ；
                  进程P1的其他代码；
              } while (true)
       }

[!WARNING]

此算法可以保证互斥访问临界资源，但两个进程必须以交替次序进入临界区。

不能保证实现空闲让进准则。

算法2

设置**标志数组flag[ ]**表示进程是否在临界区中执行，初值均为假。
在每个进程访问临界资源之前，先检查另一个进程是否在临界区中，若不在则修改本进程的临界区标志为真并进入临界区，
在退出临界区时修改本进程临界区标志为假。

enum  boolean {false，true}；
boolean  flag［2］＝{false，false}；
P0：{
          do  {
                   while  （flag[1]）；
                   flag[0]＝true；
                   进程P0的临界区代码CS0 ；
                   flag[0]＝false ；
                   进程P0的其他代码；}
          while(true)    }
P1：{
          do  {
                   while （ flag[0]）；
                   flag[1]＝true；
                   进程P1的临界区代码CS1 ；
                   flag[1]＝false ；
                   进程P1的其他代码；}
          while(true)    }

[!WARNING]

此算法解决了空闲让进的问题，但有可能两个进程同时进入临界区。

当两个进程都未进入临界区时，它们各自的访问标志值都为false，若此时刚好两个进程同时都想进入临界区，并且都发现对方标志值为false，于是两个进程同时进入了各自的临界区，这就违背了临界区的访问原则忙则等待。

算法3

本算法仍然设置标志数组flag[ ]，但标志用来表示进程是否希望进入临界区。
在每个进程访问临界资源之前，先将自己的标志设置为真，表示进程希望进入临界区，然后**再检查另一个进程的标志。**若另一个进程的标志为真，则进程等待；否则进入临界区。

enum  boolean {false，true}；
boolean  flag［2］＝{false，false}；
P0：{
          do {             
                  flag[0]＝true；
                  while  （flag[1]）；
                  进程P0的临界区代码CS0 ；
                  flag[0]＝false；
                  进程P0的其他代码；}
           while(true)   }
P1：{
          do {             
                  flag[1]＝true；
                  while  （flag[0]）；
                  进程P1的临界区代码CS1 ；
                  flag[1]＝false；
                  进程P1的其他代码；}
           while(true)   }

[!WARNING]

[!WARNING]

该算法可以有效地防止两个进程同时进入临界区，但存在两个进程都进不了临界区的问题。

当两个进程同时想进入临界区时，它们分别将自己的标志位设置为true，并且同时去检查对方的状态，发现对方也要进入临界区，于是双方互相谦让，结果谁也进不了临界区。

算法4

本算法的基本思想是算法3和算法1的结合。
**标志数组flag[ ]**表示进程是否希望进入临界区 或 是否正在临界区中执行。
还设置了一个turn变量，用于指示允许进入临界区的进程标识。

enum  boolean {false，true}；
boolean  flag［2］ ＝{false，false}；   int turn；
P0：{ 
         do  {                 
                  flag[0]＝true；        turn＝1；
                  while  （flag[1] && turn = = 1）；
                  进程P0的临界区代码CS0 ；
                  flag[0]＝false ；
                  进程P0的其他代码；}
          while (true)     }
P1：{ 
         do  {                 
                  flag[1]＝true；        turn＝0；
                  while  （flag[0] && turn = = 0）；
                  进程P1的临界区代码CS1 ；
                  flag[1]＝false ；
                  进程P1的其他代码；}
          while (true)     }

[!NOTE]

以上算法中，只有此算法是一个正确的算法。

硬件方法

用硬件方法实现互斥的主要思想是保证检查操作与修改操作不被打断。

禁止中断方法

当进程执行临界区代码时，要防止其他进程进入其临界区访问，最简单的方法是禁止中断。
禁止中断能保证当前运行进程将临界区代码顺利执行完，从而保证了互斥的正确实现，然后再允许中断。

[!WARNING]

开关中断方法的不足：

限制了处理机交替执行程序的能力，因此执行的效率将会明显降低；

将关中断的权力交给用户进程则很不明智，若一个进程关中断之后不再开中断，则系统可能会因此终止。

硬件指令方法

许多计算机中提供了专门的硬件指令，实现对字节内容的检查和修改或交换两个字节内容的功能，使用这样的硬件指令就可以解决临界区互斥的问题。

TS（TEST-and-Set指令）

boolean  TS(boolean *1ock)
    {
        boolean old；
        old=*lock；
        *lock=true；
        return old；
    }

为每个临界资源设置一个共享布尔变量lock表示资源的两种状态：true表示正被占用，false表示空闲。算法如下：

Swap指令（或Exchange指令）

    Swap(boolean *a，boolean *b)
    {
       boolean  temp；
       temp=*a；
       *a=*b；
       *b=temp；
    }

为每个临界资源设置一个共享布尔变量lock表示临界资源状态；再设置一个**局部布尔变量key用于与lock交换信息。**算法如下：

3.2.3 锁机制

锁是一个代表资源状态的变量，通常用0表示资源可用（开锁），用1表示资源已被占用（关锁）。
在使用临界资源前需先考察锁变量的值，如果值为0则将锁设置为1（关锁），如果值为1则回到第一步重新考察锁变量的值。当进程使用完资源后，应将锁设置为0（开锁）。

上锁原语

lock（w）
 {
    while（w==1）；
    w = 1；
 }

开锁原语

unlock（w）
 { 
     w = 0；
 }

用锁机制实现互斥

[!NOTE]

上述锁机制也称为自旋锁，可以用于中断处理程序，因为中断处理程序中不允许睡眠。

持有自旋锁的时间最好小于两次上下文切换的时间。持有自旋锁时不允许睡眠。

读/写自旋锁：允许多个进程同时读一个共享对象，但进程写共享对象时需要先获得写锁，写锁只允许独立访问该对象。

[!CAUTION]

前述实现方法不能实现让权等待！即存在忙等待

3.3 信号量

信号量是由荷兰科学家Dijkstra提出的，是一种卓有成效的进程同步机制。

3.3.1 信号量的定义

信号量S由两个成员**（c，q）组成，其中c是一个具有非负初值的整型变量，q是一个初始状态为空的队列。又称信号灯。**

除信号量的初值外，信号量的值仅能由P操作（又称为wait操作）和V操作（又称为signal操作）改变。

P、V来自荷兰语Proberen和Vershogen，分别表示探查和增加

也称为记录型信号量

信号量物理含义

信号量中的整型变量c表示系统中某类资源的数目。

当其值大于0时，表示系统中当前可用资源的数目；
当其值小于0时，其绝对值表示系统中因请求该类资源而被阻塞的进程数目。

P操作

设S为一个信号量，P（S）执行时主要完成下述动作：

S.c＝S.c－1；

if（S.c＜ 0） { 设置进程状态为等待；

             将进程放入信号量等待队列；

             转调度程序；}

V操作

V(S)执行时主要完成下述动作：

S.c＝S.c＋1；
if（S.c≤0）{将信号量等待队列中的第一个进程移出；
                     设置其状态为就绪状态并插入就绪队列；
                      然后再返回原进程继续执行；}

[!CAUTION]

S小于零才会有阻塞操作。

P操作可能阻塞执行进程，而V操作可以唤醒其他进程。

P、V操作在封锁中断的情况下执行，即一个进程在信号量上操作时，**不会有别的进程同时修改该信号量。**也就是说P、V操作是原语。

信号量比自旋锁有更好的处理器利用率，但开销比自旋锁大，信号量更适合锁会长时间持有的情况。

3.3.2 利用信号量实现互斥

设S为两个进程P1、P2实现互斥的信号量，S的初值应为1（即可用资源数目为1）。
只需把临界区置于P（S）和V（S）之间，即可实现两进程的互斥。

semaphore s=1;
main()
{   cobegin 
      P1();
      P2();   coend      }
   P1()                       
  {   P1剩余区；
      P(S);                          
        P1的临界区；  
      V(S)；            
     P1剩余区； }    
 P2()
  {  P2剩余区；
      P(S);         
        P2的临界区；
      V(S)；
      P2剩余区；}

若2个进程共享一个临界资源，信号量的取值范围是：

若没有进程使用临界资源若只有1个进程使用临界资源**—— 1**

若只有1个进程使用临界资源**—— 0**

若1个进程使用临界资源，另1个进程等待使用临界资源**—— -1**

取值范围：-（N-1）～1

3.3.3 利用信号量实现前驱关系

P1、P2、P3、P4、P5、P6为一组合作进程，其前驱图如下所示

解法1

设七个同步信号量a、b、c、d、e、f、g分别表示进程之间的前驱关系，如图所示，其初值均为0。这六个进程的同步描述如下：

P1（）
{      
     执行P1的代码；
      v(a)；
      v(b)；
 }

P2（）
{
     p(a)；
     执行P2的代码；
     v(c)；
     v(d)；
 }

P3（）
{
    p(b)；
    执行P3的代码；
    v(e)； 
 }

P4（）
{
    p(c)；
    执行P4的代码；
    v(f)；
}

P5（）
{
    p(d)；
   执行P5的代码；
    v(g)；
}

P6（）
{
     p(e)；
     p(f)；
     p(g)；
    执行P6的代码；
}

解法2

设五个同步信号量f1、f2、f3、f4、f5分别表示进程P1、P2、P3、P4、P5是否执行完成，其初值均为0。这六个进程的同步描述如下:

P1（）
{      
    执行P1的代码；
    v(f1)；
    v(f1)；
 }

P2（）
{
     p(f1)；
    执行P2的代码；
     v(f2)；
     v(f2)；
 }

P3（）
{
    p(f1)；
   执行P3的代码；
    v(f3)； 
 }

P4（）
{
    p(f2)；
   执行P4的代码；
    v(f4)；
}

P5（）
{
     p(f2)；
    执行P5的代码；
     v(f5)；
}

P6（）
{
    p(f3)；
    p(f4)；
    p(f5)；
    执行P6的代码；
}

3.3.4 经典进程同步问题

多道程序环境中的进程同步是一个非常有趣的问题，吸引了很多学者研究，从而产生了一系列经典进程同步问题。

生产者—消费者问题

它描述了一组生产者进程向一组消费者进程提供产品，它们共享一个有界缓冲池。缓冲池中的每个缓冲区可以存放一个产品，生产者进程不断生产产品并将产品放入缓冲池中，消费者进程不断从缓冲池内取出产品并消费。

操作系统（2025年春季）#

第一章 操作系统概论#

1.1 绪论#

1.1.1 操作系统的概念#

1.1.2 计算机系统的层次关系#

1.6.1 命令接口#

联机命令接口#

脱机命令接口#

1.6.2 程序接口#

系统调用#

系统调用分类#

系统调用处理程序执行过程#

系统调用与过程调用的区别#

1.6.3 图形用户接口#

1.7 操作系统运行环境和内核结构#

1.7.1 操作系统的运行环境#

1.7.2 操作系统的内核结构#

模块结构#

层次结构#

微内核结构#

第二章 进程和线程#

2.1 进程的引入#

2.1.1 前驱图#

2.1.2 程序的顺序执行#

程序顺序执行时的特征#

2.1.3 程序的并发执行及特点#

并发执行的特征#

与时间有关的错误例：#

并发执行的条件#

2.2 进程的定义#

2.2.1 进程许多等价的定义#

2.2.2 进程的特征#

2.2.3 进程与程序的关系#

2.2.4 进程控制块#

2.3 进程的状态及转换#

2.3.1 进程的三种基本状态#

2.3.2 新建状态和终止状态#

2.3.3 进程的挂起状态#

因果变迁#

2.4 进程控制#

2.4.1 操作系统内核#

2.4.2 原语(primitive)#

2.4.3 计算机系统的两种运行状态#

核心态(kernel mode)#

用户态(user mode)#

2.4.4 进程创建#

进程创建原语#

导致进程创建的原因有：#

进程创建原语的功能是创建一个新进程，其主要操作过程如下：#

2.4.5 进程撤销#

引起进程撤销的原因有：#

撤消原语采用的两种策略：#

撤消原语的功能是撤消一个进程，其主要操作过程如下：#

2.4.6 进程阻塞与唤醒#

唤醒原语的主要功能是将进程唤醒，其主要操作过程如下：#

2.4.7 进程的挂起与激活#

挂起原语的主要功能是将指定进程挂起，算法思想如下：#

激活原语的主要功能是将指定进程激活。其算法思想如下：#

2.5 进程组织#

2.5.1 线性方式#

2.5.2 链接方式#

2.5.3 索引方式#

2.6 线程#

2.6.1线程的控制#

2.6.2 多线程#

2.6.3 线程的实现#

内核级线程#

用户级线程#

一对一模型#

多对一模型#

多对多模型#

2.6.4 进程与线程的比较#

第三章 进程的同步与通信#

3.1 同步与互斥的概念#

3.1.1 临界资源与临界区#

访问临界资源应遵循的原则:#

临界资源访问过程#

3.1.2 同步与互斥#

3.2 互斥的实现方法#

3.2.1 互斥算法#