2021-09-23 《计算机操作系统》（第四版）学习笔记：第二章（1）

第二章 进程的描述与控制 2.1 前趋图和程序执行 2.1.1 前趋图（DAG）

​ 前趋图是一个有向无循环图，用于描述进程之间执行的前后关系。

• 结点：描述一个程序段或进程
• 有向边：表示两个结点之间存在的偏序或前趋关系“->”
• 前趋关系： ( P i ,   P j ) ∈ → (P_{i},\ P_{j})\in\rightarrow (Pi​, Pj​)∈→ 或 P i → P j P_{i}\rightarrow P_{j} Pi​→Pj​，表示 P j P_{j} Pj​ 开始之前 P i P_{i} Pi​ 必须完成
• 初始结点：没有前趋的结点
• 终止结点：没有后继的结点

2.1.2 程序顺序执行

（1）顺序执行

​ 使用 I 代表输入操作，C 代表计算操作，P 代表打印操作，则程序的顺序执行可以用下图表示：

（2）特征

1. 顺序性： 处理机严格地进行顺序操作
2. 封闭性： 程序在封闭的环境下执行，独占全部资源
3. 可再现性： 只要执行时的环境和初始条件相同，则结果相同

2.1.3 程序并发执行

（1）并发执行

​ 只有不存在前趋关系的程序之间才有可能并发执行。

（2）特征

1. 间断性： 程序的运行会出现“执行—暂停—执行”的现象
2. 失去封闭性： 程序本身的执行环境要受到外界程序的影响
3. 不可再现性： 同样的初始条件，程序可以得到不同的结果

2.2 进程的描述 2.2.1 进程的定义和特征

（1）进程的定义

​ 进程实体（进程映像）由以下三部分组成：

• 进程控制块（PCB）： 描述程序的数据结构
• 程序段
• 数据段

​ 所谓创建 / 撤销进程，实质上就是创建 / 撤销进程实体中的 PCB。

​ 进程的定义：

1. 进程是程序的一次执行
2. 进程是一个程序及其数据在处理机上顺序执行时发生的活动
3. 进程是一个可拥有资源的独立实体，同时又是一个可以独立调度的基本单位
4. 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位

（2）进程的特征（与程序的区别）

1. 动态性： 进程的实质就是进程实体的执行过程，它可以被创建、调度、执行、撤销，具有一定的生命周期。

   程序只是一组有序指令的集合，存放于某种介质上，不具有活动的含义，是静态的。

2. 并发性： 多个进程实体可以同存于内存中，且能在一段时间内同时运行。

   程序（没有建立 PCB）不能参与并发执行。

3. 独立性： 进程实体是一个能够独立运行、独立分配资源和独立接收调度的基本单位。

   程序没有 PCB，不能作为一个独立的单位参与运行。

4. 异步性： 进程按异步方式运行，以独立的、不可预知的速度向前推进。

   程序没有异步的特性。

（3）进程与程序的对应

• 同一个程序的多次运行，将形成多个不同的进程
• 同一个程序的一次执行也可以产生多个进程（通过 fork 调用）
• 一个进程也可以执行多个程序（通过 exec 调用）

2.2.2 进程的基本状态及转换

（1）三种基本状态

​ 一般而言，每一个进程至少应该处于以下三种基本状态之一：

1. 就绪状态

   进程已处于准备好运行的状态，除了 CPU，其他资源都分配到了。只要再获得 CPU，便可以立即执行。通常会按一定的策略排列这些就绪进程，该队列称为就绪队列。

2. 执行状态

3. 阻塞状态

   正在执行的进程由于发生某些事件（I/O 请求、申请缓冲区失败等）暂时无法运行。根据阻塞原因的不同，也会设置多个阻塞队列。

（2）三种基本状态的转换

（3）创建状态和终止状态（五态）

1. 创建状态
   • 申请空白的 PCB，填写信息
   • 分配运行时必要的资源
   • 进入就绪状态，插入就绪队列中
2. 终止状态
   • 等待操作系统进行善后处理
   • 清除 PCB，返还其所占空间

2.2.3 挂起操作和进程状态的转换

​ 挂起操作： 进程处于静止状态。

​ 若进程正在执行，则暂停执行；

​ 若进程已经就绪，则暂时不接收调度。

（1）引入挂起操作的原因

1. 终端用户的需要
2. 父进程请求
3. 负荷调节
4. 操作系统的需要

（2）挂起原语与三个进程状态的转换

​ 挂起原语：Suspend 激活原语：Active

​ 就绪状态：Readya 静止就绪状态：Readys

​ 活动阻塞状态：Blockeda 静止阻塞状态：Blockeds

1. 活动就绪 ->静止就绪
2. 活动阻塞 ->静止阻塞
3. 静止就绪 ->活动就绪
4. 静止阻塞 ->活动阻塞

（3）挂起操作和五个进程状态的转换

1. NULL ->创建
2. 创建 ->活动就绪
3. 创建 ->静止就绪
4. 执行 ->终止

2.2.4 进程管理中的数据结构

（1）管理控制的数据结构

​ 在计算机系统中，对于每个资源和进程都设置了一个数据结构，用于表征其实体，称为资源信息表或进程信息表。一般分为以下四类：

• 内存表
• 设备表
• 文件表
• 进程表（PCB）

（2）PCB 的作用

​ PCB 的作用是使一个多道程序环境下不能独立运行的程序（含数据）成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。

1. 作为独立运行基本单位的标志
2. 实现间断性运行方式
3. 提供进程管理和调度所需要的信息
4. 实现与其它进程的同步与通信

（3）PCB 的信息

1. 进程描述信息
   • 进程标识符：通常为整数，唯一。
   • 进程名：通常基于可执行文件名，不唯一。
   • 用户标识符（user ID）：指示拥有该进程的用户
   • 家族关系（process group）：父、子进程标识
2. 处理机状态
   • 通用寄存器
   • 指令计数器 PC
   • 程序状态字 PSW
   • 用户栈指针
3. 进程调度信息
   • 进程状态
   • 进程优先级
   • 阻塞原因（事件）
   • 进程调度所需的其他信息
4. 进程控制信息
   • 程序和数据的地址
   • 进程同步和通信
   • 资源清单
   • 链接指针，给出所在队列下一个进程的 PCB 首地址

（4）PCB 的组织方式

1. 线性方式

2. 链接方式

3. 索引方式

2.3 进程控制

​ 进程控制是进程管理中最基本的功能，它用于创建和撤销进程，并对进程在整个生命周期中各种状态之间的转换进行有效控制。控制进程是操作系统的内核通过原语来实现的。

​ 原语： 由若干条指令组成、用来实现某个特定操作的一个过程。

​ 原语的执行具有原子性，即原语在执行的过程中不能被分割。OS 具有很多原语，他们运行在系统状态下。

2.3.1 操作系统内核

​ 现代操作系统一般将 OS 划分为若干层次，将不同功能分别设置在不同层次中。

​ 通常会将一些

• 与硬件相关的模块
• 常用设备的驱动程序
• 运行频率较高的模块

​ 安排在仅靠硬件的软件层次中，常驻内存，称为 OS 内核。

​ 同时，将处理机的执行状态分为两种：

1. 系统态

   具有较高的特权，能执行一切指令，访问所有寄存器和存储区。

2. 用户态

   特权较低，仅能执行规定的指令，访问指定的寄存器和存储区。通常用户程序只能在用户态下运行。

（1）OS 的支撑功能

​ 三种基本功能：

1. 中断处理

2. 时钟管理

3. 原语操作

   原语在执行过程中不允许被中断。

（2）OS 的资源管理功能

1. 进程管理
2. 存储器管理
3. 设备管理

2.3.2 进程的创建

（1）进程的层次结构

​ UNIX：

• 进程与其子孙进程共同组成一个进城家族
• 子进程可以继承父进程所拥有的资源
• 撤销子进程时，其所占资源将还给父进程
• 撤销父进程时，必须同时撤销其所有的子进程

​ Windows：

• 不存在任何进程层次结构的概念，所有的进程都具有相同的地位
• 进程创建其它进程时，可以获得句柄来控制其创建的进程
• 句柄具有传递性

（2）进程图

（3）引起创建进程的事件

1. 用户登录
2. 作业调度
3. 提供服务
4. 应用请求

（4）进程的创建

​ 使用创建原语 Creat：

1. 申请空白 PCB。若 PCB 链表已满，则创建失败
2. 分配资源
3. 初始化 PCB
4. 进入就绪队列

2.3.3 进程的终止

（1）引起进程终止的事件

1. 正常结束
2. 异常结束
3. 外界干预

（2）进程的终止过程

1. 检索进程的 PCB，读出进程状态
2. 若进程正在执行，则立即终止，并置其调度标志为真
3. 若进程拥有子进程，终止其所有子进程
4. 释放资源，归还其父进程或 OS
5. 从所在队列中移除，等待其他程序来搜集信息

2.3.4 进程的阻塞与唤醒

（1）引起进程阻塞和唤醒的事件

1. 向系统请求共享资源失败
2. 等待某种操作的完成
3. 新数据尚未到达
4. 等待新任务的到达

（2）进程阻塞过程

​ 调用阻塞原语 bolck：

1. 停止执行
2. 修改进程 PCB 状态为阻塞
3. 将 PCB 插入阻塞队列
4. 保留阻塞进程的处理机状态
5. 设置新进程的 CPU 环境

（3）进程唤醒过程

​ 调用唤醒原语 wakeup：

1. 将阻塞进程移出阻塞队列
2. 将其 PCB 状态改为就绪
3. 插入就绪队列

2.3.5 进程的挂起与激活

（1）进程的挂起

​ 使用挂起原语 suspend：

1. 检查进程状态
2. 将活动就绪改为静止就绪
3. 将活动阻塞改为静止阻塞
4. 将执行态改为静止就绪，并转进程调度

（2）进程的激活

​ 使用激活原语 active：

1. 从外存调入内存，检查其现行状态
2. 将静止就绪改为活动就绪
3. 将静止阻塞改为活动阻塞
4. 比较现行进程与激活后处于活动就绪的进程的优先级，决定哪个进程继续运行

2.4 进程同步 2.4.1 进程同步的基本概念

​ 进程同步的主要任务：

​ 对多个相关进程在执行次序上进行协调，使系统中诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。

（1）两种形式的制约关系

1. 间接相互制约关系

   多个程序并发执行，抢占共享资源而形成的制约关系。

   例如，打印机资源、共享变量等。

2. 直接制约相互关系

   进程之间为完成同一项任务而相互合作，其所用资源的访问将被制约。

（2）临界区

​ 临界资源： 一次只允许一个进程使用的资源。（包括硬件资源和软件资源，如打印机、共享变量等）

• 临界区：访问临界资源的一段代码
• 进入区：临界区前面增加的一段用于检查访问权限的代码
• 退出区：临界区后面恢复访问区访问标记的代码
• 剩余区：进程中的其他代码

while (true)
{
    进入区
    临界区
    退出区
    剩余区
}

（3）同步机制应遵循的规则

1. 空闲让进

   临界资源空闲时，应允许一个请求进入临界区的进程立即进入自己的临界区，以便有效的利用资源

2. 忙则等待

   当临界区正被访问时，其他要求进入临界区的进程必须等待，以保证对临界资源的互斥使用

3. 有限等待

   任何要求访问临界资源的进程应能在有限的时间内进入自己的临界区，以免“死等”

4. 让权等待

   不能进入临界区的进程应立即释放 CPU，以免“忙等”

2.4.2 信号量机制

（1）整型信号量

​ 由 Dijkstra 提出。

• 整型量 S：表示资源数目，仅在初始化时能赋值，是共享变量

• 两个原子操作

  • P 操作：wait(S)

    wait(S) {
        while (S  value--;                           // 使用资源
        if (S -> value  list);   // 如果资源不足，则将进程插入阻塞链表
    }
    

  • V 操作：signal(S)

    signal(semaphore *S) {
        S -> value++;                           // 释放资源
        if (S -> value  list); // 如果 S = 1 && S2 >= 1 && ... && Sn >= 1) {
                for (i = 1; i