操作系统-进程管理

1、程序
1.1 顺序程序
我们把一个具有独立功能的程序独占处理机直至最终结束的过程称为程序的顺序执行

特征：
– 顺序性：各条指令按照严格的顺序执行。
– 封闭性：程序执行得到的最终结果由给定的初始条
件决定，独占资源，不受外界影响。
– 可再现性：初始条件相同，则重复执行的结果相同
（与执行速度无关）。

1.2 并发程序
– 并发的目的：增强处理能力，提高资源利用率。
– 并发的含义：在一定时间内有多个程序同时处于运
行但尚未结束的状态，并且次序事先确定的

特征：
– 间断(异步)性：由于并发程序之间的制约，导致
“走走停停”，一个程序可能走到中途停下来；
– 失去封闭性：共享资源，受其他程序的影响。如：
一个程序写到存储器中的数据可能被另一个程序修改，
失去原有的不变特征。
– 失去可再现性：失去封闭性 －>失去可再现性；外
界环境在程序的两次执行期间发生变化，失去原有的可
重复特征。

2、进 程
2.1 定义：Process
程序在执行过程中分配和管理资源的基本单位
（这里的程序指的是一组操作序列，具有动态特性）。

2.2 程序与进程之间的区别：
– 程序是静态的，进程是动态的，强调执行过程
– 进程具有并行特征，即不考虑资源共享的情况下，
各个进程的执行是独立的，执行速度是异步的。而程序
不反映执行过程，不具有并行特征
– 进程是竞争系统资源的基本单位
– 不同的进程可以包含同一程序，只要对应的数据集
不同

2.3 进程的特征
（1）并发性。可以同其他进程一道向前推进。
（2）动态性。进程是程序的执行过程，动态产生，
动态消亡，状态变换。
（3）独立性。一个进程是一个相对完整的资源分配
单位。
（4）交往性。进程之间的相互作用。
（5）异步性。各个进程按照各自独立的、不可预知
的速度向前推进。

2.4 进 程 的 描 述
进程的静态描述由三部分组成：PCB，程序段，数据
集。
• PCB是系统感知进程的唯一实体；
• 程序描述进程所需要完成的功能；
• 而数据集是程序执行的对象

2.5 进程控制块(Process Control Block)
– 系统为了管理进程设置的一个专门的数据结构，用
它来记录进程的外部特征，描述进程的运动变化过程
– 系统利用PCB来控制和管理进程，所以PCB是系统感
知进程存在的唯一标志
– 进程与PCB是一一对应的

2.6 进 程 状 态 及 其 转 换
– 运行态（Running）：
进程占有CPU，并在CPU上运行
– 就绪态（Ready）：
一个进程已经具备运行条件，但由于无CPU暂
时不能运行的状态（当调度给其CPU时，立即可以
运行）
– 等待态（Waiting/Blocked）：
指进程因等待某种事件的发生而暂时不能运行
的状态（即使CPU空闲，该进程也不可运行）

1）三状态图：

2）五状态图：

3）七状态图：

3、线 程
进程：资源分配单位（存储器、文件）和CPU调度（分派）单位。
又称为”任务(task) “

线程：作为CPU调度单位，而进程作为其他资源分配单位。一个进
程内的基本调度单位。（轻权进程）

–线程：有时称轻量级进程
• 进程中的一个运行实体
• 是一个CPU调度单位
• 只拥有必不可少的资源，如：线程状态、寄存器上下文和栈
• 同样具有就绪、阻塞和执行三种基本状态

线程的优点：减小并发执行的时间和空间开销（线程的创建、退
出和调度），因此容许在系统中建立更多的线程来提高并发程度（进
程间的并发到进程内的并发）。提高系统执行效率，减少处理机空转
时间。
• 线程的创建时间比进程短；
• 线程的终止时间比进程短；
• 同进程内的线程切换时间比进程短；
• 由于同进程内线程间共享内存和文件资源，可直接进行不通过
内核的通信

4、进程与线程比较
– 进程：
• 资源分配的基本单位（PCB）；
• 抢占处理机的调度单位；
• 完整的虚拟地址空间；
• 由正文集，数据集和PCB组成；
• 进程切换时，涉及到有关资源信息的保存和地址空间的变化
• 进程调度与切换：操作系统内核完成；
– 线程：
• 与资源分配无关，与所属进程内的其他线程共享进程资源；
• 与所属进程内的其他线程共享同一地址空间；
• 由相关堆栈（系统栈或用户栈）寄存器和TCB组成，寄存器用来存放
存储在线程内的局部量；
• 线程切换时，不涉及到资源信息的保存和地址空间的变化，减少系统
的开销；
• 线程调度与切换：既可由操作系统内核完成，也可由用户程序进行；

线 程 的 分 类：
– 基本类型
• 用户级线程
• 系统级线程（核心级、内核级

4、进 程 控 制
– 所谓进程控制，就是系统使用一些具有特定功能的程序段来创建、撤销进程以及完成进程各状态间的转换，从而达到多进程高效率并发执行和协调，实现资源共享的目的。

– 原语：把系统下执行的某些具有特定功能的程序段称为原语，原语是不能被中断的。用于进程控制的原语有创建原语、撤销原语、阻塞原语、唤醒原语等等。

– 临界区：把系统中不允许同时多个进程访问的资源称为临界资源，而在进程中访问临界资源的那段程序称为临界区
注意：临界区不是资源，而是程序段

– 互斥：把不允许两个以上的共享某公有资源的并发进程同时进入临界区称为互斥
互斥的原则：
（1）空闲让进
（2）忙则等待
（3）有限等待
（4）让权等待

5、信 号量 和 P,V原 语
信号量（Semaphore）：信号量是一种特殊的变量，它的表面形式是一个整数附加一个队列。
信号量用于管理临界区的公有资源，信号量sem是一个整数
• sem大于等于0时代表可供并发进程使用的资源实体数
• sem小于0时则表示正在等待使用临界区的进程数。

P 原 语：(堵塞条件：s.value < 0)

semaphore s;
P(s)
{
封锁中断；//该原语执行过程中不允许中断
s.value = s.value – 1；
if (s.value < 0)
{
保护当前进程CPU现场；
该进程状态置为等待状态；
将该进程的PCB插入相应的等待队列末尾s.queue；
转进程调度；
}
开中断；
}

V 原 语:(唤醒条件：s.value <= 0)

semaphore s;
V(s)
{
封锁中断；
s.value = s.value + 1；
if (s.value < = 0)
{
唤醒相应等待队列s.queue中的一个等待进程；
改变其状态为就绪态；
并将其插入就绪队列；
转进程调度；
}
开中断；
}

6、进 程 同 步
进程同步：把一组并发进程，因直接制约而相互发送消息进行互相合作，互相等待，使得各进程按一定的速度执行的过程称为进程间的同步
私 用 信 号 量：一般来说，也可以把各进程之间发送的消息作为信号量看待。与进程互斥时不同的是，这里的信号量只与制约进程及被制约进程有关，而不是与整组并发进程有关。因此，该信号量为私用信号量。
互斥时使用的信号量为公用信号量，同步时使用的信号量为私用信号量。

举例：司 机 — 售 票 员 问 题

7、管 程
定义：指关于共享资源的数据及在其上操作的一组过程或共享数据结构及其规定的所有操作

管程有如下几个要素：
（一）管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的外部过程（函数）来间接地访问管程中的共享变量
（二）为了保证管程共享变量的数据完整性，规定管程互斥进入
（三）管程通常是用来管理资源的，因而在管程中应当设有进程等待队列以及相应的等待及唤醒操作

8、进 程 通 信
进程通信：进程之间互相交换信息的工作称之为进程通信IPC(InterProcess Communication)。
8.1 进程间通信的类型
– 低级通信：只能传递状态和整数值（控制信息），包括进程互斥和同步所采用的信号量机制。
– 高级通信：能够传送任意数量的数据，包括三类：共享存储区、管道、消息。
– 直接通信：信息直接传递给接收方，如管道。
间接通信：借助于收发双方进程之外的共享数据结构作为通信中转，如消息队列。

8.2 共享存储区通信机制
内存中开辟一个共享存储区，诸进程通过该区实现通信,这是进程通信中最快的方法。

8.3 管 道 通 信 机 制
管道(pipe)是连接读写进程的一个特殊文件，允许进程按先进先出方式传送数据。发送进程以字符流形式
把大量数据送入管道，接收进程从管道中接收数据，所以，也叫管道通信

8.4 消息传递机制
1）直接通信方式
在直接通信方式下，企图发送或接收消息的每个进程必须指出信件发给谁或从谁那里接收消息，可用send原语和receive原语为实现进程之间的通信
2）间接通信方式
采用间接通信方式时，进程间发送或接收消息通过一个信箱来进行，消息可以被理解成信件，每个信箱有一个唯一的标识符。

9、死锁
现象：

定义：一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到资源，这种现象称为进程死锁，这一组进程就称为死锁进程
– 参与死锁的进程最少是两个（两个以上进程才会出现死锁）
– 参与死锁的进程至少有两个已经占有资源
– 参与死锁的所有进程都在等待资源
– 参与死锁的进程是当前系统中所有进程的子集

资源：
– 永久性资源：可以被多个进程多次使用（可重用资
源）
• 可抢占资源
• 不可抢占资源
– 临时性资源：只可使用一次的资源；如信号量,中断
信号，同步信号等（可消耗性资源）
• “申请–分配–使用–释放”模式

例 子：

10、产生死锁的四个必要条件

互斥使用（资源独占）
不可强占（不可剥夺）
请求和保持（部分分配，占有已分配）
循环等待（环路等待）

解决死锁的方法:

1) 不考虑此问题（鸵鸟政策）
2) 预防死锁（破坏死锁条件）
3) 避免死锁（分配过程中采用策略）
4) 检测死锁（允许发生死锁）
5) 解除死锁（与检测死锁配套）

1）鸵鸟政策
最简单的方法是象鸵鸟一样对死锁视而不见。

2) 死锁预防（破坏死锁条件）
在系统设计时确定资源分配算法，限制进程对资源的申请，从而保证不发生死锁。
具体的办法是破坏产生死锁的必要条件：
（1）破坏“不可剥夺”条件
一个进程在申请新资源的要求不能立即得到满足时，便处于等待状态。而一个处于等待状态的进程的全部资源可以被剥夺。该进程重新获得它原有的资源以及得到新申请的资源时，才能重新启动执行。

（2）破坏“请求和保持”条件
方法一：采用静态分配策略
每个进程在开始执行前就申请他所需要的所有资源，只有当系统能够把资源一次性分配，该进程才能执行。
缺点：资源浪费严重。
方法二：
如果进程已经占用资源同时再去申请资源，则它应该首先释放已占有的资源再重新申请新资源

（3）破坏“循环等待”条件
采用资源有序分配法：
把系统中所有资源编号，进程在申请资源时必须严格按资源编号的递增次序进行，否则操作系统不予分配；释放资源时，应按编号递减次序进行。

3) 死锁避免（分配过程中采用策略）
在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配

与死锁预防的区别：
死锁预防是设法破坏产生死锁的必要条件，严格防止死锁的发生。而死锁避免则没有这么严格，它是一种动态策略

安全状态：
如果存在一个由系统中所有进程构成的安全序列P1，„Pn，则系统处于安全状态。
一个进程序列{P1，„，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和，系统处于安全状态，不会发生死锁。

不安全状态:
不存在一个安全序列，不安全状态不一定导致死锁

银行家算法：
银行家算法的基本思想是：
在安全状态下系统收到一个进程的资源请求后,先把资源试探性分配给它。在进程集合中找到剩余资源能满足最大需求量的进程,从而保证这个进程运行完毕并归还全部资源。这时,把这个进程从集合中去掉, 系统的剩余资源更多了,再反复执行上述步骤。
最后,检查进程集合,若为空表明本次申请可行,系统处于安全状态,可真正实施本次分配;否则,有进程执行不完，系统处于不安全状态,本次资源分配暂不实施,让申请进程等待。

银行家例子：第一次分配后的系统状态

新 的 系 统 状 态：

4）死锁检测
允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生。
最常用的检测死锁的方法就是对资源分配图进行化简。
①在图中找一个请求边均能立即满足的一个进程顶点Pi；
②若找到了这样的Pi，则将与Pi相连的边全部删去，转①

如果化简后所有的进程顶点都成了孤立点，则称该图可完全化简，否则不可完全化简(是产生死锁的充分必要条件，非孤立点的进程处于死锁状态。

5）死锁解除
一般通过破坏循环等待条件
从死锁进程集合中选择一个或多个进程予以删除，并剥夺它们的资源给其它的进程使用。选择要删除的进程时，一般从优先级、已运行时间及已用多少资源等几个方面去考虑，使系统损失最小

6）死锁的综合处理
一般来说，无论哪种方法都无法适用于每类资源，可以把系统中的全部资源分成几大类，整体上采用有序资源分配法，再对每类资源根据其特点选择最合适的方法。
例如，系统中有以下几类资源：
①主存；
②作业资源(打印机、磁带驱动器、文件等)；
③辅存。
将①②③类资源编号为1、2、3，按有序资源申请。对第①类
采用剥夺法；
对第②类采用死锁避免法；
对第③类采用静态资源分配法；

11、资 源 分 配 图
资源类（资源的不同类型）
-用方框表示
资源实例（存在于每个资源中）
-用方框中的黑圆点表示
进程
-用圆圈中加进程名表示
分配边：
资源实例→进程的一条有向边
申请边：
进程→资源类的一条有向边

11.1 有环有死锁

11.2 有环无死锁

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