计算机操作系统（五） 前趋图和程序执行与进程的描述（附带图谱表格更好对比理解））

---

前言

• 在上一篇博客中，我们深入探讨了操作系统的结构与系统调用，了解了操作系统不同结构的特点、优缺点以及系统调用的基本概念和类型。
• 了解这些知识后，我们对操作系统的内部机制和应用程序与操作系统的交互方式有了更全面的认识。
• 本篇博客将继续深入操作系统的世界，聚焦于前趋图和程序执行以及进程的描述这两个重要方面。
• 通过学习这些内容，你会对操作系统中程序的执行方式以及进程的相关概念有更清晰的理解，为后续深入学习操作系统的进程管理等知识打下坚实基础。

我的个人主页，欢迎来阅读我的其他文章
https://blog.csdn.net/2402_83322742?spm=1011.2415.3001.5343
我的操作系统博客专栏
https://blog.csdn.net/2402_83322742/category_12916780.html?spm=1001.2014.3001.5482

---

一、前趋图和程序执行

1.1前趋图

前趋图（Precedence Graph）是一个有向无环图（DAG, Directed Acyclic Graph），用于描述程序中各个操作之间的先后顺序关系。图中的每个节点代表一个操作（可以是一条语句、一个程序段或进程等），有向边（箭头）表示操作之间的前趋关系，即箭头指向的操作必须在箭头出发的操作完成之后才能开始执行。

例如，假设有四个操作 $S_1$、$S_2$、$S_3$、$S_4$，它们之间的关系为：$S_1$ 执行完后 $S_2$ 和 $S_3$ 才能执行，$S_2$ 和 $S_3$ 都执行完后 $S_4$ 才能执行。用前趋图表示如下：

      S1/  \S2    S3\  /S4

前趋图的作用在于清晰地展示操作之间的依赖关系，帮助我们分析程序的执行顺序，尤其是在程序并发执行时，确定哪些操作可以并行执行，哪些操作需要顺序执行，从而更好地进行程序的设计和优化。

1.2程序的顺序执行

程序的顺序执行是指程序中的操作按照它们在代码中出现的先后顺序依次执行，前一个操作执行完成后，才会执行下一个操作。在顺序执行的情况下，程序具有以下特征：

1. 顺序性：操作严格按照顺序依次执行，不会出现交叉或并发执行的情况。
2. 封闭性：程序在执行过程中，其执行结果只取决于程序本身，不受外界因素的干扰，并且相同的输入会得到相同的输出。
3. 可再现性：只要初始条件相同，程序无论执行多少次，结果都是一样的。

例如，下面是一个简单的 C 语言程序顺序执行的示例：

#include <stdio.h>int main() {int a = 5;int b = 3;int c = a + b;printf("The result is: %d\n", c);return 0;
}

在这个程序中，先定义变量 a 和 b，然后计算它们的和并赋值给 c，最后输出结果。每个操作都是顺序执行的，前一个操作完成后才会进行下一个操作。

1.3程序的并发执行

随着计算机硬件技术的发展，为了提高系统的资源利用率和执行效率，程序的并发执行变得越来越常见。程序的并发执行是指多个程序或程序的多个部分在同一时间间隔内同时执行。

例如，在一个多任务操作系统中，我们可以同时运行文本编辑器进行文字编辑，同时运行音乐播放器播放音乐。这两个程序的执行就是并发执行的。

与顺序执行相比，并发执行具有以下特点：

1. 间断性：由于多个程序共享系统资源（如 CPU、内存等），它们的执行过程可能会被中断和切换，导致执行过程具有间断性。
2. 失去封闭性：并发执行的程序可能会相互影响，一个程序的执行结果可能会受到其他程序的干扰，不再像顺序执行那样具有封闭性。
3. 不可再现性：由于并发执行的不确定性，即使初始条件相同，每次执行的结果也可能不同。

例如，假设有两个进程 P1 和 P2，它们都要对共享变量 x 进行操作。P1 要将 x 的值加 1，P2 要将 x 的值减 1。如果它们并发执行，由于执行顺序的不确定性，最终 x 的值可能不是初始值，这就体现了并发执行的不可再现性。

二、进程的描述

2.1进程的定义与特征

进程（Process）是操作系统中最基本、最重要的概念之一。进程可以定义为程序的一次执行过程，它是系统进行资源分配和调度的基本单位。

进程具有以下特征：

1. 动态性：进程是程序的执行过程，它有一定的生命周期，从创建、运行到终止，是一个动态的过程。
2. 并发性：多个进程可以在同一时间间隔内同时运行，它们可以并发执行，提高系统的资源利用率。
3. 独立性：进程是独立运行的实体，每个进程都有自己独立的地址空间、资源和执行上下文，进程之间相互独立，互不干扰。
4. 异步性：由于进程的执行受到系统调度的影响，它们的执行速度是不确定的，具有异步性。

• 例如，我们打开一个浏览器，浏览器就是一个进程，它在运行过程中可以同时加载多个网页，每个网页的加载可以看作是浏览器进程中的一个子任务，这些子任务并发执行，体现了进程的并发性和动态性。

2.2进程的基本状态与转换

进程在其生命周期中会处于不同的状态，常见的基本状态有以下三种：

1. 就绪状态（Ready）：进程已经准备好运行，只等待 CPU 资源分配。在就绪队列中等待的进程处于就绪状态。
2. 运行状态（Running）：进程正在 CPU 上运行。在单 CPU 系统中，同一时刻只有一个进程处于运行状态。
3. 阻塞状态（Blocked）：进程由于等待某一事件（如 I/O 操作完成、等待信号量等）而暂时无法运行，此时进程会进入阻塞状态，直到所等待的事件发生。

进程的状态可以在一定条件下相互转换，具体的转换关系如下：

1. 就绪 -> 运行：当 CPU 空闲时，操作系统会从就绪队列中选择一个进程，将其状态转换为运行状态，这个过程称为进程调度。
2. 运行 -> 就绪：当运行进程的时间片用完，或者有更高优先级的进程进入就绪队列时，当前运行进程会被暂停，状态转换为就绪状态，等待下一次被调度。
3. 运行 -> 阻塞：当运行进程需要等待某一事件发生（如读取文件数据）时，它会主动放弃 CPU，进入阻塞状态，等待事件完成。
4. 阻塞 -> 就绪：当进程所等待的事件发生后（如文件数据读取完成），进程会从阻塞状态转换为就绪状态，进入就绪队列等待调度。

2.3挂起的操作系统和进程的转换

在操作系统中，除了上述三种基本状态外，还有一种挂起状态（Suspended）。挂起状态是为了满足系统管理和资源调度的需要而引入的。

挂起状态分为两种：

1. 就绪挂起（Ready Suspended）：进程处于就绪状态，但被挂起，此时进程被放到外存（如硬盘）上，而不是内存中。当系统需要调度该进程时，需要先将其从外存调入内存。
2. 阻塞挂起（Blocked Suspended）：进程处于阻塞状态，并且被挂起，同样被放到外存上。当所等待的事件发生后，进程会先转换为就绪挂起状态，然后再根据需要调入内存转换为就绪状态。

进程在挂起状态和其他状态之间的转换关系如下：

1. 就绪 -> 就绪挂起：当系统内存资源紧张时，操作系统可能会将一些就绪进程挂起，将其状态转换为就绪挂起，以释放内存资源。
2. 就绪挂起 -> 就绪：当系统内存资源充足时，或者有其他进程结束运行释放了内存，操作系统可以将就绪挂起的进程调入内存，将其状态转换为就绪状态。
3. 阻塞 -> 阻塞挂起：类似地，当系统需要释放内存资源时，可能会将一些阻塞进程挂起，转换为阻塞挂起状态。
4. 阻塞挂起 -> 就绪挂起：当阻塞挂起的进程所等待的事件发生后，进程会转换为就绪挂起状态。
5. 运行 -> 就绪挂起：在某些情况下，如系统需要进行内存整理或有更高优先级的进程需要运行，正在运行的进程可能会被直接挂起，转换为就绪挂起状态。

2.4进程管理中的数据结构

为了有效地管理进程，操作系统需要使用一些数据结构来记录进程的相关信息。常见的进程管理数据结构有：

1. 进程控制块（PCB, Process Control Block）：是操作系统中最重要的数据结构之一，它记录了进程的所有信息，包括进程标识符、进程状态、优先级、程序计数器、寄存器值、内存指针、I/O 状态信息、父子进程关系等。每个进程都有一个唯一的 PCB，操作系统通过 PCB 来管理和控制进程的运行。
2. 就绪队列：用于存储处于就绪状态的进程。当 CPU 空闲时，操作系统会从就绪队列中选择一个进程进行调度。
3. 阻塞队列：用于存储处于阻塞状态的进程。当进程所等待的事件发生时，操作系统会从阻塞队列中找到相应的进程，并将其状态转换为就绪状态。

例如，在 Linux 操作系统中，进程控制块是一个名为 task_struct 的结构体，它包含了大量的成员变量来描述进程的各种信息。操作系统通过操作 task_struct 结构体来实现对进程的创建、调度、终止等管理操作。

总结（核心概念速记）：

核心概念速记
操作系统之程序执行与进程描述 = 前趋图指引程序执行 + 进程概念及状态转换 + 数据结构支撑进程管理

• 前趋图与程序执行：
  • 前趋图为有向无环图，展示操作先后顺序，助于分析程序执行，确定并行与顺序操作。
  • 程序顺序执行具顺序性、封闭性、可再现性；并发执行具间断性、失封闭性、不可再现性，能提高资源利用率。
• 进程相关概念：
  • 进程是程序执行过程，是资源分配和调度基本单位，具动态性、并发性、独立性、异步性。
  • 基本状态：就绪（等 CPU）、运行（占 CPU）、阻塞（等事件），状态可依条件转换，如时间片用完、事件发生等。
  • 挂起状态分就绪挂起和阻塞挂起，因内存管理等需求引入，状态转换与内存资源及事件相关。
• 进程管理数据结构：
  • 进程控制块（PCB）记录进程全面信息，是管理控制进程关键。
  • 就绪队列存就绪进程，阻塞队列存阻塞进程，为进程调度提供数据支持。

程序执行方式对比

执行方式	特点	优点	缺点	适用场景
顺序执行	操作按序依次执行，结果确定	逻辑简单，易理解调试，结果可再现	资源利用率低，执行效率低	简单任务，对结果确定性要求高场景
并发执行	多程序或部分同时执行，结果不确定	提高资源利用率和系统效率，可同时处理多任务	执行逻辑复杂，结果不可再现，易相互干扰	多任务处理，对资源利用率要求高场景

进程状态及转换关系

状态转换 → 条件 → 说明  ↓          ↓           ↓  就绪 -> 运行 → CPU 空闲调度 → 进程获 CPU 资源开始运行  运行 -> 就绪 → 时间片用完或高优先级进程就绪 → 进程暂停等待下次调度  运行 -> 阻塞 → 等待事件发生 → 进程因事件暂停运行  阻塞 -> 就绪 → 事件发生 → 进程恢复可运行状态  就绪 -> 就绪挂起 → 内存紧张 → 进程被移至外存释放内存  就绪挂起 -> 就绪 → 内存充足 → 进程调回内存准备运行  阻塞 -> 阻塞挂起 → 内存紧张 → 阻塞进程被挂起  阻塞挂起 -> 就绪挂起 → 事件发生 → 挂起阻塞进程转就绪挂起  运行 -> 就绪挂起 → 内存整理或高优先级进程需求 → 运行进程被挂起  

知识图谱

计算机操作系统（五） 前趋图和程序执行与进程的描述  
├─ 前趋图和程序执行  
│  ├─ 前趋图（有向无环图，表操作顺序）  
│  ├─ 程序顺序执行（三特性：顺序、封闭、可再现）  
│  └─ 程序并发执行（三特性：间断、失封闭、不可再现）  
├─ 进程的描述  
│  ├─ 进程定义与特征（动态、并发、独立、异步）  
│  ├─ 进程基本状态与转换（就绪、运行、阻塞及转换）  
│  ├─ 挂起状态及转换（就绪挂起、阻塞挂起及转换）  
│  └─ 进程管理数据结构（PCB、就绪队列、阻塞队列）  
├─ 关键术语  
│  ├─ 前趋图、顺序执行、并发执行  
│  ├─ 进程、就绪、运行、阻塞、挂起  
│  ├─ 进程控制块（PCB）、就绪队列、阻塞队列  
└─ 应用与理解  ├─ 前趋图对程序设计优化作用  ├─ 进程状态转换对资源调度影响  └─ 数据结构在进程管理中意义  

重点提炼

1. 程序执行要点：

   • 前趋图是分析程序执行顺序的有效工具，尤其在并发场景中。
   • 理解顺序执行和并发执行特点，根据任务需求合理选择执行方式，平衡效率与结果确定性。

2. 进程概念核心：

   • 进程是操作系统核心概念，掌握其定义和特征是理解操作系统运行机制基础。
   • 熟悉进程状态及转换条件，有助于理解系统资源调度和管理策略。
   • 挂起状态是内存管理和进程调度重要补充，了解其转换关系可更好理解系统内存资源分配。

3. 进程管理关键：

   • 进程控制块是进程管理关键数据结构，操作系统通过它实现对进程全方位控制。
   • 就绪队列和阻塞队列是进程调度基础，合理维护和操作队列可提高系统性能。

4. 技术应用拓展：

   • 在程序开发中，利用前趋图规划任务顺序，提高程序执行效率和稳定性。
   • 在系统设计中，依据进程状态转换和管理数据结构，优化资源分配和调度算法。

进程管理数据结构对比表

数据结构	作用	关键信息	与进程状态关系
进程控制块（PCB）	记录进程所有信息，用于管理控制进程	进程标识符、状态、优先级等	每种状态进程都有对应 PCB，依状态更新信息
就绪队列	存储就绪状态进程	进程指针等	存放就绪进程 PCB 指针，供 CPU 调度选取
阻塞队列	存储阻塞状态进程	进程指针、等待事件等	存放阻塞进程 PCB 指针，事件发生时唤醒转换状态

操作系统中程序执行与进程管理演进脉络

技术演进 —— 顺序执行（早期简单任务） → 并发执行（多任务需求） → 进程概念引入（资源管理调度） → 挂起状态及数据结构完善（内存管理优化）  ↓         ↓               ↓               ↓  
应用升级 —— 单一任务处理 → 多任务并行处理 → 复杂系统资源分配调度 → 高效内存管理与进程调度  

---

以上就是对本次关于操作系统博客内容的总结，后续我们将深入探讨操作系统更多知识。

我的个人主页，欢迎来阅读我的其他文章
https://blog.csdn.net/2402_83322742?spm=1011.2415.3001.5343
我的操作系统博客专栏
https://blog.csdn.net/2402_83322742/category_12916780.html?spm=1001.2014.3001.5482

非常感谢您的阅读，喜欢的话记得三连哦