操作系统之进程管理

操作系统的主要功能包括：进程管理，存储管理，文件管理，作业管理以及设备管理。

进程管理重点需要研究进程之间的并发特征，以及进程之间相互合作和资源竞争产生的问题。

进程的状态

基本的三态模型：主要是指运行、就绪和阻塞。

与上面组成五态模型：运行、就绪、阻塞、新建和终止。

与下面组成具有挂起状态的五态模型：运行、就绪、阻塞、挂起等待和挂起就绪

就绪和阻塞的区别：就绪就是除了 CPU 之外的其他资源均已获得，阻塞就是缺少 CPU 和其他资源。

同步与互斥

进程间的同步是指进程间完成一项任务时直接发生相互作用的关系。

进程间的互斥是指系统中个进程互斥使用临界资源。

临界资源（Critical Resource，CR）：只能供一个进程使用的资源。

临界区（Critical Section，CS）：是进程中对临界资源实施操作的那段程序。

PV 操作和信号量

信号量

信号量：信号量是一个整型变量，根据控制对象的不同被赋予不同的值。

信号量分为两类：

1. 公用信号量。实现进程间的互斥，初值为 1 或资源的数目。
2. 私有信号量。实现进程间的同步，初值为 0 或某个正整数。

信号量 S 的物理意义：S ≥ 0 表示某资源的可用数，若 S < 0，则其绝对值表示阻塞队列中等待该资源的进程数。

PV 操作

PV 操作是实现进程同步与互斥的常用方法。P 操作表示申请一个资源，V 操作表示释放一个资源。

P 操作的定义：S:=S-1，若 S ≥ 0，则执行 P 操作继续执行；若 S < 0，则置该进程为阻塞状态，并将其插入阻塞队列。

V 操作的定义：S:=S+1，若 S > 0，则执行 V 操作继续执行；若 S ≤ 0，则从阻塞队列唤醒一个进程，将其插入就绪队列，然后执行 V 操作的进程继续。

死锁

死锁：是指两个以上的进程互相都要求对方已经占有的资源导致无法继续运行下去的现象。

产生死锁的 4 个必要条件是：互斥，请求保持，不可剥夺和环路。

死锁的处理主要有 4 种：死锁的预防和死锁的避免。

死锁的预防主要有两种策略：

1. 预先静态分配法。破坏了“不可剥夺条件”，预先分配所需资源，保证不等待资源。
2. 资源有序分配法。破坏了“环路条件”，把资源分配按顺序排列，保证不形成环路。

死锁的避免最著名的银行家算法。银行家算法的原则：

• 当一个进程对资源的最大需求量不超过系统中的资源数时可以接纳该进程。
• 进程可以分期请求资源，但请求的总数不能超过最大需求量。
• 当系统现有的资源不能满足进程尚需资源时，对进程的请求可以推迟分配。但总能使进程在有限的时间内得到资源。

资源分配图

资源分配图（Resource Allocation Graph），用有向图描述资源和进程的状态。

系统由若干资源构成，一类资源称为一个资源类；每个资源类中包含若干个同种资源，称为资源实例。所以表示方式：

• 资源类：用方框表示
• 资源实例：用方框中的黑圆点表示

• 进程：用圆圈中加进程名表示

• 分配边：资源实例 -> 进程
• 申请边：进程 -> 资源类

• 如果资源分配图中没有环路，则系统中没有死锁，如果图中存在环路则系统中可能存在死锁
• 如果每个资源类中只包含一个资源实例，则环路是死锁存在的充分必要条件

资源分配图化简

化简步骤：

1. 找一个非孤立、且只有分配边的进程的结点。 去掉分配边，将其变为孤立结点。
2. 再把相应的资源分配给一个等待该资源的进程。即将该进程的申请边变为分配边。
3. 重复步骤 1、步骤 2

参考链接

• 《软件设计师教程（第 4 版）》
• wikipedia: Process State
• Coursera: 资源分配图