第二章：进程的描述与控制

一、进程与线程

1. 进程的概念和特征

（1）进程的概念

• 进程是程序的一次执行过程（进程与程序的关系）
• 进程实体由程序段、相关数据段和PCB（进程控制块）构成
• 创建和删除进程的本质是创建和删除PCB
• PCB是进程存在的唯一标志

（2）进程的特征

• 动态性
• 并发性
• 独立性
• 异步性

其中，动态性是进程最基本的特性

2. 进程的状态与转换

在操作系统中，挂起原语（Suspend）和激活原语（Activate）与挂起状态（Suspended State）的关系是管理进程生命周期的一部分。

挂起原语（Suspend）： 挂起原语是操作系统中用于将进程从运行状态或就绪状态转换到挂起状态的一个系统调用或操作。当一个进程被挂起时，它通常会释放所占用的资源，并且其状态会被设置为挂起状态。挂起状态意味着进程不会被操作系统调度执行，直到它被激活或者被终止。

激活原语（Activate）： 激活原语与挂起原语相反，它用于将处于挂起状态的进程恢复到就绪状态。当进程被激活时，它的状态会被设置为就绪，这意味着它可以被操作系统调度执行，只要它满足执行条件（如没有更高的优先级进程正在执行）。

挂起状态（Suspended State）： 挂起状态是进程可以进入的一种状态，当进程被挂起原语操作时，它就会进入这种状态。在挂起状态下，进程不会消耗CPU资源，也不会执行任何操作，直到它被激活。挂起状态通常用于暂停进程以便进行维护、调试或等待某些事件（如等待I/O操作完成）。

总结来说，挂起原语和激活原语是操作系统用来控制进程状态转换的工具，而挂起状态则是进程在这些转换中可能经历的一种状态。通过这些操作，操作系统能够灵活地管理进程，以满足用户和系统的需求。

3. 进程的组织

（1）进程控制块（PCB）

（2）程序段

• 能被进程调度到CPU执行的程序代码段（多个进程可以运行同一个程序）

（3）数据段

• 程序加工处理的原始数据或程序执行时产生的中间结果或最终结果

4. 进程控制

（1）进程的创建

①父子进程

• 父子进程之间代码共享，数据独有
• 关系
  • 一个进程创建另一个进程，创建者称为父进程，被创建者称为子进程
  • 撤销子进程时，资源要归还父进程；撤销父进程时，要同时撤销所有子进程
  • 子进程可以继承父进程所有资源
  • 父子进程可以共享一部分资源，子进程创建也会分配自己独有的资源（2020）
  • 父子进程不能共享虚拟地址空间（2020）

②引起进程创建的事件

• 用户登录、作业调度、系统提供提供服务、应用请求、启动程序执行（设备分配不会引起进程创建）（2010）

③进程创建过程

• 分配进程标识符并申请PCB–>分配资源–>初始化PCB–>插入就绪队列（2021）

（2）进程的终止

引起进程终止的事件：

• 正常结束：进程的任务已经完成并准备退出运行
• 异常结束：存储区越界、保护错、非法指令、特权指令错、运行超时、算术运算错、I/O故障等
• 外部干预：操作员或操作系统干预、父进程请求、父进程终止

（3）进程的阻塞和唤醒

• BLOCK原语是自我调用（自己阻塞自己），Wake up原语是被其它进程调用（其它进程唤醒）

5. 进程的通信

进程间的低级通信方式为PV操作，后面会细讲，这里先详细介绍一下高级通信方式

（1）共享存储

• 进程空间是独立的，一般不能被互相直接访问，所以需要一块共享空间作为中介
• 进程对共享空间的访问必须是互斥的
• 两个不同进程不能通过全局变量通信，全局变量是对同一进程而言的
• 分类
  • 低级方式：基于共享数据结构
  • 高级方式：基于共享存储区

（2）消息传递系统

• 将数据封装在消息中，使用发送和接收原语在进程间传递消息从而完成数据交换

分类：

（3）管道通信系统

6. 线程和多线程模型

（1）线程的基本概念

• 引入进程是为了多道程序并发执行；引入线程是未了减小程序切换的开销
• 线程组成：线程ID、程序计数器、寄存器集合、堆栈
• 同一进程中的线程切换不会引起进程切换；不同进程中的线程切换会引起进程切换
• 线程不拥有系统资源（仅有一点必不可少的资源）
• 同一进程的不同线程
  • 线程共享资源：地址空间（拥有相同的地址空间）、全局变量、打开的文件、子进程（2012）
  • 线程独享资源：程序计数器、寄存器、栈、状态字（2011）

（2）线程与进程的比较

（3）线程的状态与转换

• 执行态、就绪态、阻塞态（类比线程）

（4）线程的实现方式

①用户级线程

• 有关线程管理（创建、撤销和切换等）的所有工作都在用户空间完成
• 内核意识不到线程的存在，处理及调度仍以进程为单位
• 内核每次分配给一个进程一个CPU，因此进程中仅有一个线程能执行
• 可以在不支持线程的操作系统上实现（2019）

②内核级线程

• 有关线程管理的所有工作都在内核空间实现（2019）
• 处理机调度以线程为单位
• 内核能同时调度统一进程中的多个线程并行执行
• 内核级线程比用户级线程的切换效率低（2019）

③组合方式

（5）多线程模型

二、处理机调度

1. 调度的概念

2. 调度的目标

3. 调度的实现

（1）调度时机

不能进行进程调度与切换的情况

（2）进程调度方式

• 非抢占调度（非剥夺）
  • 不能用于分时系统和大多数实时系统
• 抢占式调度（剥夺）

（3）闲逛进程

• 进程切换时若没有其它进程就绪就执行闲逛进程
• 闲逛进程的优先级最低，只要有进程就绪就会立即让出处理机
• 闲逛进程不需要CPU之外的资源，因此不会被阻塞

4. 典型的调度算法

（1）先来先服务（FCFS）调度算法

• 对长作业有利；对短作业不利
• 有利于CPU繁忙型作业（一般是长作业）；不利于I/O繁忙型作业（一般是短作业）

（2）短作业优先（SJF）调度算法

• 对长作业不利；对短作业有利
• 分为抢占式短作业优先和非抢占式式短作业优先（都会造成饥饿现象）（2011、2014）
• 平均等待时间、平均周转时间最少

（3）优先级调度算法

（4）高响应比优先调度算法

• 综合考虑了每个进程的等待时间和执行时间（2009）

（5）时间片轮转调度算法

• 主要适用于分时系统
• 时钟中断发生后，系统会修改当前进程在时间片内的剩余时间（2017）
• 时间片太大将退化为先来先服务调度算法；时间片太小处理机频繁进行进程切换则开销增大（2017）

（6）多级反馈队列调度算法（2019、2020）

• 步骤
  • 设置多个队列，并为每个序列设置不同的优先级
  • 优先级越高的队列中时间片就越小，每个队列都采用FCFS算法
  • 进程进入内存后，先放入第1级队列的队尾，若未执行完，放入下一队列末尾
  • 只有当前面的队列执行完，才能执行后面的队列
  • 若有更高优先级的队列进入，当前进程放置所处队列的队尾，执行新来的进程
• 特点
  • 对很多作业都能较好处理；可能造成饥饿

5. 进程切换

（1）基本概念

• 上下文：某一时刻CPU寄存器和程序计数器的内容
• 上下文切换：CPU从一个进程切换到另一个进程保存当前进程状态并回复另一个进程状态的过程
• 进程切换要在内核支持下完成

（2）上下文切换流程

• 挂起一个进程，保存其CPU上下文，更新其PCB并移入相应的队列
• 选择新的进程，更新其PCB并转到程序计数器所指位置执行，恢复该进程的CPU上下文

（3）区分

三、同步与互斥

1. 同步与互斥的基本概念

（1）基本概念

（2）直接相互制约（同步）

• 进程为完成同一项任务而协调工作次序所产生的制约关系

（3）间接相互制约（互斥）

• 对临界资源只能互斥地访问

互斥机制应遵循的规则：

2. 实现临界区互斥的基本方法

（1）软件实现

（2）硬件实现

中断屏蔽方法: 进程在执行临界区代码时，通过关中断防止其它进程进入临界区

3. 互斥锁

• 进程在进入临界区时获得锁，在退出临界区时释放锁
• 函数acquire()获得锁，函数release()释放锁，两者执行必须是原子操作。因此互斥锁通常采用硬件机制实现
• 主要缺点：忙等待

4. 信号量

（1）特点

• 是低级进程通信，因为效率低、对用户不透明
• PV操作是原子操作不可被中断；PV操作不是系统调用
• V操作能让进程进入就绪状态；P操作能让进程进入阻塞状态
• value为正表示还有同类资源；value为-m表示有m个进程处于阻塞态等待使用资源（2010）
• P（S）和wait（S）等价；V（S）和signal（S）等价（2022）

（2）分类

（3）应用

5. 管程机制

（1）组成

• 管程的名称
• 局部于管程内部的共享数据结构说明
• 对该数据结构进行操作的一组过程（或函数）
• 对局部于管程内部的共享数据设置初始值的语句

（2）特点

• 由编译语言支持的进程同步机制（2016）
• 管程可以用于实现进程的同步或互斥（2016）
• 所有进程都只能用过管程访问临界资源，管程每次只允许一个进程进入（2016）

（3）条件变量

• 一种抽象数据类型，保存一个链表，用于记录因该条件变量而阻塞的所有进程
• x.wait：把进程挂在x对应的阻塞队列上；x.signal：唤醒x的阻塞队列上的一个进程（2018）
• 若没有等待进程，x.signal不会有任何操作，这与信号量中的signal不同（会修改信号量变量的值）

6. 经典同步问题

• 大题部分细讲

四、死锁

1. 死锁的定义

两个或两个以上进程因竞争资源而相互等待，若无外力作用这些进程都无法向前推进（2019）

2. 死锁产生的原因

（1）系统资源的竞争

• 竞争不可抢占性资源（磁带、打印机）

（2）进程推进顺序非法

3. 产生死锁的必要条件

4. 死锁的处理策略

（1）预防死锁

（2）避免死锁

原理

• 在资源动态分配过程中，防止系统进入不安全状态

银行家算法

• 可以求出安全队列；需要知道进程所需全部资源数
• 银行家算法只能避免死锁，不能检测死锁（2013、2019）
• n个进程，每个进程所需设备为x1,x2…xn，则保证不发生死锁的最小设备数为(x1-1)+(x2-1)+…(xn-1)+1（经常考）

不安全状态与死锁

• 死锁一定是不安全状态；不安全状态不一定是死锁（2013）

（3）检测死锁

• 资源分配图（有向图）
  • （学会简化资源分配图）
• 死锁定理：S为死锁状态的充分条件是：当且仅当S的资源分配图是不可完全简化的

（4）解除死锁