操作系统原理教程
第 2章 处理器管理
本章教学目标
? 了解线程的基本概念
? 熟悉进程描述, 进程通信和进程死锁
? 掌握进程控制, 进程同步与互斥, 进程
调度
本章主要内容
? 处理器管理概述
? 进程描述
? 进程控制
? 线程的基本概念
? 进程同步与互斥
? 进程通信
? 进程调度
? 进程死锁
处理器管理概述
? 处理器管理的功能
? 程序的执行
处理器管理的功能
? 处理器管理的主要任务
– 是对处理器进行分配，并对其运行进行有效
地控制和管理。
? 处理器管理的主要功能
– 进程控制
– 进程同步
– 进程通信
– 进程调度
程序的执行
? 程序执行的描述
– 前趋图
? 程序的顺序执行
? 程序的并发执行
前趋图
? 概念：
– 前趋图是一个有向无循环图。
? 要求
– 每个结点可用于表示一条语句、一个程序段等
– 结点间的有向边表示在两个结点之间存在的前趋关
系
? 例如：
– 图 2-1所示
程序的顺序执行
? 概念：
– 程序在执行时，必须按某种先后次序逐个执
行操作，只有当前一个操作执行完后，才能
执行后一个操作。
? 特征：
– 顺序性
– 封闭性
– 可再现性
程序的并发执行
? 概念：
– 是指在一个时间段内执行多个程序。
? 特征：
– 间断性
– 失去封闭性
– 不可再现性
? 程序并发执行的判断方法：
– Bernstein条件
– 利用前趋图
Bernstein条件
? 原理：
– 不同运算（或程序）的读集与写集的交集和写集与
写集的交集的并集为空集时，这几个运算（或程序）
可以并发执行。
? 解释：
– 运算的读集是指在运算执行期间引用的所有变量的
集合；
– 运算的写集是指在运算执行期间要改变的所有变量
的集合。
? 例子：
– 例 2-2
利用前趋图
? 原理：
– 画出程序执行的前趋图，根据该程序或运算在前趋
图中的位置关系，可以判断其能否并发执行。
? 解释：
– 在程序或运算的先后顺序上，只有前后相邻的的程
序或运算不能并发执行，其余程序和运算都可以并
发执行。
? 例子：
– 例 2-3
进程描述
? 进程的概念
? 进程的状态
? 进程的挂起状态
进程的概念
? 进程的定义
– 一个程序在一个数据集合上的一次运行过程。所以
一个程序在不同数据集合上运行，乃至一个程序在
同样数据集合上的多次运行都是不同的进程。
? 进程的特征
– 动态性
– 并发性
– 独立性
– 异步性
– 结构性
进程的状态
? 进程的三种基本状态
? 进程的其它两种状态
? 进程状态间的转换
进程的三种基本状态
? 就绪状态
– 当进程以分配到除处理器（ CPU）以外的所有必要
资源后，只要再获得处理器就可以立即执行，这时
进程的状态称为就绪状态。
? 执行状态
– 处于就绪状态的进程一旦获得了处理器，就可以运
行，进程状态也就处于执行状态。
? 阻塞状态
– 正在执行的进程因为发生某些事件（如请求输入 /输
出、申请额外空间等）而暂停运行，这种受阻暂停
的状态称为阻塞状态，也可以称为等待状态。
进程的其它两种状态
? 新状态
– 当一个新进程刚刚建立，还未将其放入就绪
队列时的状态，称为新状态。
? 终止状态
– 当一个进程已经正常结束或异常结束，操作
系统已将其从系统队列中移出，但尚未撤消，
这时称为终止状态。
进程状态间的转换
? 新状态 → 就绪状态
? 就绪状态 → 执行状态
? 执行状态 → 阻塞状态
? 执行状态 → 就绪状态
? 阻塞状态 → 就绪状态
? 执行状态 → 终止状态
? 如图 2-5所示
进程的挂起状态
? 引入挂起状态主要
原因：
– 用户的需求
– 父进程的需求
– 操作系统的需求
– 对换的需求
? 引入挂起状态后的进程
状态转换
– 执行状态 → 静止就绪
– 活动就绪 → 静止就绪
– 静止就绪 → 活动就绪
– 活动阻塞 → 静止阻塞
– 静止阻塞 → 活动阻塞
– 静止阻塞 → 静止就绪
进程控制
? 进程控制块 PCB
? 进程的创建与撤消
? 进程的阻塞与唤醒
进程控制块 PCB
? 进程控制块的作用
? 进程控制块的内容
? 进程控制块的组织方式
? 进程控制原语
进程控制块的作用
? 概念
– 进程控制块是进程实体的重要组成部分，是操作系
统中最重要的记录型数据，在进程控制块 PCB
（ Program Contral Block）中记录了操作系统所需要
的、用于描述进程情况及控制进程运行所需要的全
部信息
? 作用
– 通过 PCB，使得原来不能独立运行的程序（数据），
成为一个可以独立运行的基本单位，一个能够并发
执行的进程。进程控制块是进程存在的唯一标志。
进程控制块的内容
? 进程标识信息
– 进程标识符用于标识一个进程，一个进程通有外部标识符和
内部标识符两种
? 说明信息
– 说明信息是有关进程状态等一些与进程调度有关的信息。
? 现场信息
– 现场信息是用于保留进程存放在处理器中的各种信息，主要
由处理器内的各个寄存器的内容组成。
? 管理信息
– 管理信息包括进程资源、控制机制等一些进程执行所需要的
信息。
进程控制块的组织方式
? 链接方式
– 把具有相同状态的 PCB，用其中的链接指针
链接成队列。如图 2-7所示。
? 索引方式
– 系统根据所有进程的状态，建立几张索引表。
在每个索引表的表目中，记录着具有相同状
态的各个 PCB在表中的地址。如图 2-8所示。
进程控制原语
? 原语的概念
– 原语是指具有特定功能的不可被中断的过程。它主
要用于实现操作系统的一些专门控制操作。
? 原语的分类
– 创建原语：用于为一个进程分配工作区和建立 PCB，置该进程
为就绪状态。
– 撤消原语：用于一个进程工作完后，收回它的工作区和 PCB。
– 阻塞原语：用于进程在运行过程中发生等待事件时，把进程
的状态改为等待态。
– 唤醒原语,用于当进程等待的事件结束时，把进程的状态改
为就绪态。
进程的创建
? 引起进程创建的事件
– 用户登录
– 作业调度
– 提供服务
– 应用请求
? 进程创建的过程
– 为新进程分配唯一的进程标识符, 并从 PCB队列中申请一个空闲
PCB。
– 为新进程的程序和数据, 以及用户栈分配相应的主存空间及其它必
要分配资源 。
– 初始化 PCB中的相应信息, 如标识信息, 处理器信息, 进程控制信
息等 。
– 如果就绪队列可以接纳新进程，便将新进程加入到就绪队列中。
进程的撤消
? 引起进程撤消的事件
– 进程正常结束
– 在进程运行期间，由于出现某些错误和故障而使得进程被迫中止
– 进程应外界的请求而中止运行
? 进程撤消的过程
– 根据被终止进程的标识符, 从 PCB集合中检索该进程的 PCB,读
出进程状态 。
– 若该进程处于执行状态, 则立即终止该进程的执行 。
– 若该进程有子孙进程, 还要将其子孙进程终止 。
– 将该进程所占用的资源回收, 归还给其父进程或操作系统 。
– 将被终止进程的 PCB从所在队列中移出，并撤消该进程的 PCB。
进程的阻塞
? 引起进程阻塞的事件
– 请求系统服务
– 启动某种操作
– 新数据尚未到达
– 无新工作可做
? 进程阻塞的过程
– 立即停止执行该进程 。
– 修改进程控制块中的相关信息 。 把进程控制块中的运行状态由
,执行, 状态改为, 阻塞, 状态, 并填入等待的原因, 以及进
程的各种状态信息 。
– 把进程控制块插入到阻塞队列 。 根据阻塞队列的组织方式, 把
阻塞进程的进程控制块插入到阻塞队列中 。
– 转调度程序重新调度，运行就绪队列中的其他进程。
进程的唤醒
? 引起进程唤醒的事件
– 请求系统服务得到满足
– 启动某种操作完成
– 新数据已经到达
– 有新工作可做
? 进程唤醒的过程
– 从阻塞队列中找到该进程 。
– 修改该进程控制块的相关内容 。 把阻塞状态改为就绪状态,
删除等待原因等等 。
– 把进程控制块插入到就绪队列。按照就绪队列的组织方式，
把被唤醒的进程的进程控制块插入到就绪队列中。
线程的基本概念 1
? 线程的概念
– 线程是进程中的一个实体，是被系统独立调
度和执行的基本单位。
? 线程与进程的比较
– 调度单位不同
– 并发形式不同
– 拥有资源 不同
线程的基本概念 2
? 线程的类型
– 系统级线程：是依赖于系统控制的，即无论
是用户进程中的线程，还是系统进程中的线
程，它们的创建、撤消、切换都是由系统控
制实现的。
– 用户级线程,是由用户控制，对于用户级线
程的创建、撤消、切换，都与系统控制无关，
完全由用户自己管理。
超线程
? 超线程的概念
– 超线程技术就是利用特殊的硬件指令，在一颗实体处理器中放入两
个逻辑处理单元，从而模拟成两个工作环境，让单个处理器都能使
用线程级并行计算，同时处理多项任务，提升处理器资源的使用率。
? 超线程的工作
– 超线程处理器被视为两个分离的逻辑处理器，应用程序
不须修正就可使用这两个逻辑处理器。
– 每个逻辑处理器都可独立响应中断。第一个逻辑处理器
可追踪一个软件线程，而第二个逻辑处理器则可同时追
踪另一个软件线程。
– 由于两个线程共同使用同样的执行资源，因此不会产生
一个线程执行的同时，另一个线程闲置的状况。
进程同步与互斥
? 进程的并发性
? 进程的同步与互斥
? 利用 PV操作实现互斥与同步
? 管程的基本概念
进程的并发性
? 概念
– 在并发执行的系统中，若干个作业可以同时执行，
而每个作业又需要有多个进程协作完成。在这些同
时存在的进程间具有并发性
? 并发进程之间的关系
– 无关关系,这些进程间彼此毫无关系，互不影响
– 相关关系,这些进程间彼此往往相关，互相影响，
要进行合理的控制和协调才能正确执行
? 资源共享关系
? 相互合作关系
进程的同步与互斥
? 进程同步与互斥的概念
? 进程同步机制应遵循的原则
? 利用锁机制实现同步
进程同步与互斥的概念
? 临界资源
– 在系统中有许多硬件或软件资源，在一段时间内只允许一个进程访
问或使用，这种资源称为临界资源。
? 临界区
– 每个进程中访问临界资源的那段代码称为临界区
? 进程同步
– 进程同步是指多个相关进程在执行次序上的协调，这些进程相互合
作，在一些关键点上需要相互等待或相互通信。
? 进程互斥
– 进程互斥是指当一个进程进入临界区使用临界资源时，另一个进程
必须等待，当占用临界资源的进程退出临界区后，另一个进程才被
允许使用临界资源。
进程同步机制应遵循的原则
? 空闲让进
? 忙则等待
? 有限等待
? 让权等待
利用锁机制实现同步
? 锁的概念
– 在同步机构中，常用一个变量来代表临界资
源的状态，并称它为锁。通常用,0”表示资
源可用，用,1”表示资源已被占用。
? 锁的操作
– 关锁操作
– 解锁操作
利用 PV操作实现互斥与同步
? 整型信号量的概念
? 信号量的操作
? 利用 PV操作实现互斥
? 利用 PV操作实现同步
? 利用 PV操作实现进程的同步加互斥
整型信号量的概念
? 概念
– 信号量就是一种特殊变量，它用来表示系统中资源
的使用情况。而整型信号量就是一个整型变量。
? 说明：
– 当其值大于,0”时，表示系统中对应可用资源的数目；
– 当其值小于,0”时，其绝对值表示因该类资源而被阻
塞的进程的数目；
– 当其值等于,0”时，表示系统中对应资源已经都被占
用，并且没有因该类资源而被阻塞的进程。
信号量的操作
? （ 1） P操作：记为 P（ S）, 描述为：
– P（ S）
– { S=S-1；
– if （ S<0） W（ S） ；
– }
? （ 2） V操作：记为 V（ S）, 描述为：
– V（ S）
– { S=S+1；
– if （ S<=0） R（ S） ；
– }
利用 PV操作实现互斥
? 概念：
– 互斥信号量是根据临界资源的类型设置的。有几种
类型的临界资源就设置几个互斥信号量。它代表该
类临界资源的数量，或表示是否可用，其初值一般
为,1”。
? 例题
– 【 例 2-4】 在一个只允许单向行驶的十字路口，分别
有若干由东向西，由南向北的车辆在等待通过十字
路口。为了安全，每次只允许一辆车通过。当有车
辆通过时其它车辆必须等候，当无车辆在路口行驶
时则允许一辆车通过。请用 PV操作实现保证十字路
口安全行驶的自动管理系统。
– 【 例 2-5】 有 4位哲学家围着一个圆桌在思考和进餐，
每人思考时手中什么都不拿，当需要进餐时，每人需
要用刀和叉各一把，餐桌上的布置如图 2-12所示，共
有 2把刀和 2把叉，每把刀或叉供相邻的两个人使用。
请用信号量及 PV操作说明 4位哲学家的同步过程。
– 【 例 2-6】 在南开大学和天津大学之间有一条弯曲的
小路，其中从 S到 T有一段路每次只允许一辆自行车通
过，但其中有一个小的安全岛 M（同时允许两辆自行
车停留），可供两辆自行车错车时使用，如图 2-14所
示。试设计一个算法使来往自行车可以顺利通过。
利用 PV操作实现同步
? 概念
– 同步信号量是根据进程的数量设置的。一般情况下，
有几个进程就设置几个同步信号量，表示该进程是否
可以执行，或表示该进程是否执行结束。其初值一般
为,0”。
? 例子
– 【 例 2-7】 图 2-16给出了 4个进程合作完成某一任务的
前趋图，试说明这 4个进程间的同步关系，并用 PV操
作描述它们。
? 方法一：同步信号量用来表示该进程是否可以开始。
? 方法二：同步信号量用来表示该进程是否已经结束。
例子
? 【 例 2-8】 桌上有一个空盘子，只允许放一个水果。爸爸可以向盘
中放苹果，也可以向盘中放桔子，儿子专等吃盘中的桔子，女儿
专等吃盘中的苹果。规定当盘空时，一次只能放一只水果，请用
PV操作实现爸爸、儿子、女儿 3个并发进程的同步。
? 【 例 2-9】 有 3个进程 PA,PB,PC合作解决记录打印问题,PA将
记录从磁盘读入主存的缓冲区 1，每执行一次读一个记录； PB将
缓冲区 1的记录复制到缓冲区 2，每执行一次复制一个记录； PC将
缓冲区 2的记录打印出来，每执行一次打印一个记录；缓冲区的大
小等于一个记录的 PA,PB,PC大小。请用 PV操作来保证记录的
正确打印。
使用 PV操作实现进程的同步加互斥
? 概念
? 例子
– 【 例 2-10】 某数据库有一个写进程，多个读
进程，它们之间读、写操作的互斥要求是：
写进程运行时，其它读、写进程不能对数据
库操作，读进程之间不互斥，可以同时读数
据库。请用信号量及 PV操作描述这一组进
程的工作过程。
例题
? 【 例 2-11】 设有一个具有 N个信息元素的环形缓冲区,A
进程顺序地把信息写进缓冲区,B进程依次地从缓冲区
中读出信息，用 PV操作表示 A,B进程的同步算法。
? 【 例 2-12】 理发师理发问题。有一个理发师，一把理发
椅和 n把等候理发顾客坐的椅子。如果没有顾客，则理
发师在理发椅上睡觉；当一个顾客到来时，必须唤醒理
发师，进行理发；如果理发师正在理发，又有顾客来到
时，如果有空椅子可坐，他就坐下来等候，如果没有空
椅子，他就离开。请为理发师和顾客各编一个程序表述
他们的行为。
同步与互斥的解题思路
? ① 分清哪些是互斥问题 （ 互斥访问临界资源的 ）, 哪些是同步问题
（ 具有前后执行顺序要求的 ） 。
? ② 对互斥问题要设置互斥信号量, 不管有互斥关系的进程有几个或
几类, 通常只设置一个互斥信号量, 且初值为 1,代表一次只允许
一个进程对临界资源访问 。
? ③ 对同步问题要设置同步信号量, 通常同步信号量的个数与参与同
步的进程种类有关, 即同步关系涉及几类进程, 就有几个同步信号
量 。 同步信号量表示该进程是否可以开始或该进程是否已经结束 。
? ④在每个进程中用于实现互斥的 PV操作必须成对出现；用于实现
同步的 PV操作也必须成对出现，但可以分别出现在不同的进程中；
在某个进程中如果同时存在互斥与同步的 P操作，则其顺序不能颠
倒，必须先执行对同步信号量的 P操作，再执行对互斥信号量的 P操
作，但 V操作的顺序没有严格要求。
同步与互斥的解题步骤
? （ 1） 确定进程 。 包括进程的数量, 进程
的工作内容, 可以用流程图描述 。
? （ 2） 确定同步互斥关系 。 根据是否使用
的是临界资源, 还是处理的前后关系,
确定同步与互斥, 然后确定信号量的个
数, 含义, 以及对信号量的 P,V操作 。
? （ 3）用类 C语言描述同步或互斥算法。
管程的基本概念
? 概念
– 管程实际上是定义了一个数据结构和在该数
据结构上的能为并发进程所执行的一组操作，
这组操作能同步进程和改变管程中的数据。
? 说明：
– 管程由 3部分组成：局部于管程的共享变量
说明、对该数据结构进行操作的一组过程、
对局部于管程的数据设置初始值的语句。
– 每个管程都应该有唯一的名字来标识。
进程通信
? 概念
– 进程通信是指进程间的信息交换。
? 类型
– 共享存储器系统
– 消息传递系统
– 管道通信系统
共享存储器系统
? 概念
– 在共享存储器系统中，相互通信的进程共享某些数
据结构或共享存储区，进程之间能够通过它们进行
通信。
? 方式
– 共享数据结构方式
? 相互通信的诸进程公用某些数据结构，并通过这些数据交
换信息。
– 共享存储区方式
? 是在存储器中划出一块共享存储区，相互通信的诸进程可
以通过对共享存储区中的数据进行读或写来实现通信。
消息传递系统
? 概念
– 进程间的数据交换以消息为单位，用户直接利用系
统中提供的一组通信命令（原语）进行通信。
? 方式
– 直接通信方式
? 发送进程使用发送原语直接将消息发送给接收进程，并将
它挂在接收进程的消息缓冲队列上，接收进程使用接收原
语从消息缓冲队列中取出消息。
– 间接通信方式
? 发送进程使用发送原语直接将消息发送到某种中间实体中，
接收进程使用接收原语从该中间实体中取出消息。
管道通信系统
? 管道
– 管道是指连接读进程和写进程，以实现它们
之间通信的共享文件。
? 管道通信系统
– 向管道提供输入的发送进程（写进程），以
字符流形式将大量的数据送入管道，而接受
管道输出的接收进程（读进程），可以从管
道中接收数据。
进程调度
? 进程调度的类型
? 选择进程调度算法的原则
? 常用的进程调度算法
进程调度的类型
? 高级调度
? 低级调度
? 中级调度
高级调度
? 基本原理
– 高级调度又称为作业调度或长程调度，用于
决定把外存上处于后备队列中的哪些作业调
入主存，并为它们创建进程、分配必要的资
源，然后将新创建的进程排入就绪队列，准
备执行。
? 需要解决的问题
– 一是接纳多少个作业。
– 二是接纳哪些作业。
低级调度
? 基本原理
– 低级调度通常又称为进程调度或短程调度。它决定主存中的就绪队
列上的哪个进程（单处理器系统）将获得处理器，然后把处理器分
配给该进程，使其执行。
? 方式
– 非抢占方式
? 在某个进程正在占用处理器执行时，不允许其它任何进程抢占处
理器。
– 抢占方式
? 把处理器分配给某个进程后，在该进程尚未终止或阻塞时，允许
系统调度程序根据某种原则，暂停正在执行的进程，回收已经分
配的处理器，并将处理器重新分配给其它更为紧急的进程。
中级调度
? 基本原理
– 系统将那些暂时不能运行的进程从主存调到外存（仍
然保持进程状态）上的特定区域，这些在外存存放的
进程所处的状态称为就绪驻外状态或挂起状态。当这
些进程的运行条件具备，且主存又有空闲时，在中级
调度的控制下，再将处于外存上的那些重新具备运行
条件的就绪驻外进程调入主存，并将其状态修改为就
绪状态，放入就绪队列，等待进程调度。
? 目的
– 是为了进一步提高主存的利用率和系统的吞吐量。
选择进程调度算法的原则
? 面向用户的原则
– 周转时间短
– 响应时间快
– 截止时间有保证
– 优先权原则
? 面向系统的原则
– 系统吞吐量高
– 处理器利用率好
– 各类资源的平衡利用
常用的进程调度算法
? 先来先服务调度算法
? 短进程优先调度算法
? 时间片轮转调度算法
? 优先数调度算法
? 响应比高者优先调度算法
? 多级队列调度算法
先来先服务调度算法
? 原理
– 每次调度是从就绪队列中，选择一个最先进
入就绪队列的进程，把处理器分配给该进程，
使之得到执行。该进程一旦占有了处理器，
它就一直运行下去，直到该进程完成或因发
生事件而阻塞，才退出处理器。
? 特点
– 利于长进程，而不利于短进程。
短进程优先调度算法
? 原理
– 它是从就绪队列中选择一个估计运行时间最
短的进程，将处理器分配给该进程，使之占
有处理器并执行，直到该进程完成或因发生
事件而阻塞，然后退出处理器，再重新调度。
? 特点
– 照顾到了系统中占大部分的短进程，有效地
降低了进程的平均等待时间，提高了系统的
吞吐量，但对长进程不利。
时间片轮转调度算法
? 原理
– 系统将所有的就绪进程按进入就绪队列的先后次序
排列。每次调度时把 CPU分配给队首进程，让其执
行一个时间片，当时间片用完，由计时器发出时钟
中断，调度程序则暂停该进程的执行，使其退出处
理器，并将它送到就绪队列的末尾，等待下一轮调
度执行。
? 特点
– 为了保证人机交互的及时性，系统使每个进程依次
按时间片方式轮流地执行 。
优先数调度算法
? 原理
– 它是从就绪队列中选择一个优先权最高的进程，让其获得处理器并
执行。
? 方式
– 非抢占式优先数调度算法
? 系统一旦把处理器分配给就绪队列中优先权最高的进程后，该进程就占
有处理器一直运行下去，直到该进程完成或因发生事件而阻塞，才退出
处理器。
– 抢占式优先数调度算法
? 系统同样把处理器分配给当前就绪队列中优先权最高的进程，使之执行。
但在其执行期间，仍然会不断的有新的就绪进程进入就绪队列，如果出
现某个进程，其优先权比当前正在执行的进程的优先权还高时，进程调
度程序就会立即暂停当前进程的执行，而将处理器收回，并将处理器分
配给新出现的优先权更高的进程，让其执行。
响应比高者优先调度算法
? 原理
– 它是从就绪队列中选择一个响应比最高的进程，让
其获得处理器执行，直到该进程完成或因等待事件
而退出处理器为止。
? 特点
– 既照顾了短进程，又考虑了进程到达的先后次序，
也不会使长进程长期得不到服务，因此是一个比较
全面考虑的算法，但每次进行调度时，都需要对各
个进程计算响应比。所以系统开销很大，比较复杂。
多级队列调度算法
? 原理
– 是根据进程的类型或性质的不同，将就绪进
程分为若干个独立队列，不同类型或性质的
进程固定地分属于一个队列，每个队列可以
采用适合的调度算法，不同的队列可使用不
同的调度算法。
? 特点
– 同时具有多种操作方式 的进程调度
进程死锁
? 死锁的基本概念
? 死锁的预防
? 死锁的避免
? 死锁的检测与解除
死锁的基本概念
? 死锁的概念
– 是指多个进程因竞争资源而造成的一种僵局，若无外力的作
用，这些进程将都不能再继续执行。
? 产生死锁的原因
– 竞争资源
– 进程推进顺序非法
? 产生死锁的必要条件
– 互斥条件
– 请求和保持条件
– 不剥夺条件
– 环路等待条件
死锁的预防
? 原理
– 该方法是通过对资源分配的原则进行限制，
从而使产生死锁的四个必要条件中的第 2,3、
4个条件之一不能成立，来预防产生死锁。
? 方法
– 破坏“不剥夺”条件
– 破坏“请求和保持”条件
– 破坏“环路等待”条件
死锁的避免
? 原理
– 在死锁的避免中，所施加的限制较弱，将获得较好
一些的系统性能。该方法把系统状态分为安全状态
和不安全状态，只要能使系统始终处于安全状态，
便可以避免发生死锁。
? 安全状态
– 是指系统能按某种顺序为每个进程分配所需资源，
直到最大需求，使每一个进程都可以顺利完成。
? 利用银行家算法避免死锁
银行家算法的处理步骤
? 银行家算法的处理步骤为：
– （ 1） 列出某一时刻资源分配表, 格式如表 2-4所示 。
– （ 2） 拿可用资源量与每一个进程所需资源量进行比
较, 可用资源量不少于所需资源量时, 把资源分配给
该进程 。 新的可用资源量为原有可用资源量加上该进
程已分配资源量 。
– （ 3）重复（ 2），直到所有进程都执行完，即可判断
能否获得一个安全资源分配序列。
? 例题
– 【 例 2-18】
死锁的检测与解除
? 死锁的检测
– 利用死锁定理
? 死锁的解除
– 剥夺资源法
– 撤消进程法
本章小结
? 处理器管理的主要任务是分配处理器，
? 主要目的是提高处理器的使用效率。
? 它的主要功能有：进程控制、进程同步、进程通信和进程
调度。
? 熟悉和掌握以下基本概念：
– 进程、临界资源、同步、互斥、原语、线程、管程、管道、死锁
? 熟悉和掌握以下基本知识：
– 1．并发与并行。 2．进程描述与控制 。
– 3．同步控制机制 。 4．进程调度 。
– 5．进程通信 。 6．进程死锁 。
习 题
? 一、单项选择题
– 1-22题
? 二、判断题
– 1-10题
? 三、填空题
– 1-15题
? 四、区分下列概念
– 1-8题
? 五、简答题
– 1-7题
? 六、应用题
– 1-19题
第 2章 处理器管理
本章教学目标
? 了解线程的基本概念
? 熟悉进程描述, 进程通信和进程死锁
? 掌握进程控制, 进程同步与互斥, 进程
调度
本章主要内容
? 处理器管理概述
? 进程描述
? 进程控制
? 线程的基本概念
? 进程同步与互斥
? 进程通信
? 进程调度
? 进程死锁
处理器管理概述
? 处理器管理的功能
? 程序的执行
处理器管理的功能
? 处理器管理的主要任务
– 是对处理器进行分配，并对其运行进行有效
地控制和管理。
? 处理器管理的主要功能
– 进程控制
– 进程同步
– 进程通信
– 进程调度
程序的执行
? 程序执行的描述
– 前趋图
? 程序的顺序执行
? 程序的并发执行
前趋图
? 概念：
– 前趋图是一个有向无循环图。
? 要求
– 每个结点可用于表示一条语句、一个程序段等
– 结点间的有向边表示在两个结点之间存在的前趋关
系
? 例如：
– 图 2-1所示
程序的顺序执行
? 概念：
– 程序在执行时，必须按某种先后次序逐个执
行操作，只有当前一个操作执行完后，才能
执行后一个操作。
? 特征：
– 顺序性
– 封闭性
– 可再现性
程序的并发执行
? 概念：
– 是指在一个时间段内执行多个程序。
? 特征：
– 间断性
– 失去封闭性
– 不可再现性
? 程序并发执行的判断方法：
– Bernstein条件
– 利用前趋图
Bernstein条件
? 原理：
– 不同运算（或程序）的读集与写集的交集和写集与
写集的交集的并集为空集时，这几个运算（或程序）
可以并发执行。
? 解释：
– 运算的读集是指在运算执行期间引用的所有变量的
集合；
– 运算的写集是指在运算执行期间要改变的所有变量
的集合。
? 例子：
– 例 2-2
利用前趋图
? 原理：
– 画出程序执行的前趋图，根据该程序或运算在前趋
图中的位置关系，可以判断其能否并发执行。
? 解释：
– 在程序或运算的先后顺序上，只有前后相邻的的程
序或运算不能并发执行，其余程序和运算都可以并
发执行。
? 例子：
– 例 2-3
进程描述
? 进程的概念
? 进程的状态
? 进程的挂起状态
进程的概念
? 进程的定义
– 一个程序在一个数据集合上的一次运行过程。所以
一个程序在不同数据集合上运行，乃至一个程序在
同样数据集合上的多次运行都是不同的进程。
? 进程的特征
– 动态性
– 并发性
– 独立性
– 异步性
– 结构性
进程的状态
? 进程的三种基本状态
? 进程的其它两种状态
? 进程状态间的转换
进程的三种基本状态
? 就绪状态
– 当进程以分配到除处理器（ CPU）以外的所有必要
资源后，只要再获得处理器就可以立即执行，这时
进程的状态称为就绪状态。
? 执行状态
– 处于就绪状态的进程一旦获得了处理器，就可以运
行，进程状态也就处于执行状态。
? 阻塞状态
– 正在执行的进程因为发生某些事件（如请求输入 /输
出、申请额外空间等）而暂停运行，这种受阻暂停
的状态称为阻塞状态，也可以称为等待状态。
进程的其它两种状态
? 新状态
– 当一个新进程刚刚建立，还未将其放入就绪
队列时的状态，称为新状态。
? 终止状态
– 当一个进程已经正常结束或异常结束，操作
系统已将其从系统队列中移出，但尚未撤消，
这时称为终止状态。
进程状态间的转换
? 新状态 → 就绪状态
? 就绪状态 → 执行状态
? 执行状态 → 阻塞状态
? 执行状态 → 就绪状态
? 阻塞状态 → 就绪状态
? 执行状态 → 终止状态
? 如图 2-5所示
进程的挂起状态
? 引入挂起状态主要
原因：
– 用户的需求
– 父进程的需求
– 操作系统的需求
– 对换的需求
? 引入挂起状态后的进程
状态转换
– 执行状态 → 静止就绪
– 活动就绪 → 静止就绪
– 静止就绪 → 活动就绪
– 活动阻塞 → 静止阻塞
– 静止阻塞 → 活动阻塞
– 静止阻塞 → 静止就绪
进程控制
? 进程控制块 PCB
? 进程的创建与撤消
? 进程的阻塞与唤醒
进程控制块 PCB
? 进程控制块的作用
? 进程控制块的内容
? 进程控制块的组织方式
? 进程控制原语
进程控制块的作用
? 概念
– 进程控制块是进程实体的重要组成部分，是操作系
统中最重要的记录型数据，在进程控制块 PCB
（ Program Contral Block）中记录了操作系统所需要
的、用于描述进程情况及控制进程运行所需要的全
部信息
? 作用
– 通过 PCB，使得原来不能独立运行的程序（数据），
成为一个可以独立运行的基本单位，一个能够并发
执行的进程。进程控制块是进程存在的唯一标志。
进程控制块的内容
? 进程标识信息
– 进程标识符用于标识一个进程，一个进程通有外部标识符和
内部标识符两种
? 说明信息
– 说明信息是有关进程状态等一些与进程调度有关的信息。
? 现场信息
– 现场信息是用于保留进程存放在处理器中的各种信息，主要
由处理器内的各个寄存器的内容组成。
? 管理信息
– 管理信息包括进程资源、控制机制等一些进程执行所需要的
信息。
进程控制块的组织方式
? 链接方式
– 把具有相同状态的 PCB，用其中的链接指针
链接成队列。如图 2-7所示。
? 索引方式
– 系统根据所有进程的状态，建立几张索引表。
在每个索引表的表目中，记录着具有相同状
态的各个 PCB在表中的地址。如图 2-8所示。
进程控制原语
? 原语的概念
– 原语是指具有特定功能的不可被中断的过程。它主
要用于实现操作系统的一些专门控制操作。
? 原语的分类
– 创建原语：用于为一个进程分配工作区和建立 PCB，置该进程
为就绪状态。
– 撤消原语：用于一个进程工作完后，收回它的工作区和 PCB。
– 阻塞原语：用于进程在运行过程中发生等待事件时，把进程
的状态改为等待态。
– 唤醒原语,用于当进程等待的事件结束时，把进程的状态改
为就绪态。
进程的创建
? 引起进程创建的事件
– 用户登录
– 作业调度
– 提供服务
– 应用请求
? 进程创建的过程
– 为新进程分配唯一的进程标识符, 并从 PCB队列中申请一个空闲
PCB。
– 为新进程的程序和数据, 以及用户栈分配相应的主存空间及其它必
要分配资源 。
– 初始化 PCB中的相应信息, 如标识信息, 处理器信息, 进程控制信
息等 。
– 如果就绪队列可以接纳新进程，便将新进程加入到就绪队列中。
进程的撤消
? 引起进程撤消的事件
– 进程正常结束
– 在进程运行期间，由于出现某些错误和故障而使得进程被迫中止
– 进程应外界的请求而中止运行
? 进程撤消的过程
– 根据被终止进程的标识符, 从 PCB集合中检索该进程的 PCB,读
出进程状态 。
– 若该进程处于执行状态, 则立即终止该进程的执行 。
– 若该进程有子孙进程, 还要将其子孙进程终止 。
– 将该进程所占用的资源回收, 归还给其父进程或操作系统 。
– 将被终止进程的 PCB从所在队列中移出，并撤消该进程的 PCB。
进程的阻塞
? 引起进程阻塞的事件
– 请求系统服务
– 启动某种操作
– 新数据尚未到达
– 无新工作可做
? 进程阻塞的过程
– 立即停止执行该进程 。
– 修改进程控制块中的相关信息 。 把进程控制块中的运行状态由
,执行, 状态改为, 阻塞, 状态, 并填入等待的原因, 以及进
程的各种状态信息 。
– 把进程控制块插入到阻塞队列 。 根据阻塞队列的组织方式, 把
阻塞进程的进程控制块插入到阻塞队列中 。
– 转调度程序重新调度，运行就绪队列中的其他进程。
进程的唤醒
? 引起进程唤醒的事件
– 请求系统服务得到满足
– 启动某种操作完成
– 新数据已经到达
– 有新工作可做
? 进程唤醒的过程
– 从阻塞队列中找到该进程 。
– 修改该进程控制块的相关内容 。 把阻塞状态改为就绪状态,
删除等待原因等等 。
– 把进程控制块插入到就绪队列。按照就绪队列的组织方式，
把被唤醒的进程的进程控制块插入到就绪队列中。
线程的基本概念 1
? 线程的概念
– 线程是进程中的一个实体，是被系统独立调
度和执行的基本单位。
? 线程与进程的比较
– 调度单位不同
– 并发形式不同
– 拥有资源 不同
线程的基本概念 2
? 线程的类型
– 系统级线程：是依赖于系统控制的，即无论
是用户进程中的线程，还是系统进程中的线
程，它们的创建、撤消、切换都是由系统控
制实现的。
– 用户级线程,是由用户控制，对于用户级线
程的创建、撤消、切换，都与系统控制无关，
完全由用户自己管理。
超线程
? 超线程的概念
– 超线程技术就是利用特殊的硬件指令，在一颗实体处理器中放入两
个逻辑处理单元，从而模拟成两个工作环境，让单个处理器都能使
用线程级并行计算，同时处理多项任务，提升处理器资源的使用率。
? 超线程的工作
– 超线程处理器被视为两个分离的逻辑处理器，应用程序
不须修正就可使用这两个逻辑处理器。
– 每个逻辑处理器都可独立响应中断。第一个逻辑处理器
可追踪一个软件线程，而第二个逻辑处理器则可同时追
踪另一个软件线程。
– 由于两个线程共同使用同样的执行资源，因此不会产生
一个线程执行的同时，另一个线程闲置的状况。
进程同步与互斥
? 进程的并发性
? 进程的同步与互斥
? 利用 PV操作实现互斥与同步
? 管程的基本概念
进程的并发性
? 概念
– 在并发执行的系统中，若干个作业可以同时执行，
而每个作业又需要有多个进程协作完成。在这些同
时存在的进程间具有并发性
? 并发进程之间的关系
– 无关关系,这些进程间彼此毫无关系，互不影响
– 相关关系,这些进程间彼此往往相关，互相影响，
要进行合理的控制和协调才能正确执行
? 资源共享关系
? 相互合作关系
进程的同步与互斥
? 进程同步与互斥的概念
? 进程同步机制应遵循的原则
? 利用锁机制实现同步
进程同步与互斥的概念
? 临界资源
– 在系统中有许多硬件或软件资源，在一段时间内只允许一个进程访
问或使用，这种资源称为临界资源。
? 临界区
– 每个进程中访问临界资源的那段代码称为临界区
? 进程同步
– 进程同步是指多个相关进程在执行次序上的协调，这些进程相互合
作，在一些关键点上需要相互等待或相互通信。
? 进程互斥
– 进程互斥是指当一个进程进入临界区使用临界资源时，另一个进程
必须等待，当占用临界资源的进程退出临界区后，另一个进程才被
允许使用临界资源。
进程同步机制应遵循的原则
? 空闲让进
? 忙则等待
? 有限等待
? 让权等待
利用锁机制实现同步
? 锁的概念
– 在同步机构中，常用一个变量来代表临界资
源的状态，并称它为锁。通常用,0”表示资
源可用，用,1”表示资源已被占用。
? 锁的操作
– 关锁操作
– 解锁操作
利用 PV操作实现互斥与同步
? 整型信号量的概念
? 信号量的操作
? 利用 PV操作实现互斥
? 利用 PV操作实现同步
? 利用 PV操作实现进程的同步加互斥
整型信号量的概念
? 概念
– 信号量就是一种特殊变量，它用来表示系统中资源
的使用情况。而整型信号量就是一个整型变量。
? 说明：
– 当其值大于,0”时，表示系统中对应可用资源的数目；
– 当其值小于,0”时，其绝对值表示因该类资源而被阻
塞的进程的数目；
– 当其值等于,0”时，表示系统中对应资源已经都被占
用，并且没有因该类资源而被阻塞的进程。
信号量的操作
? （ 1） P操作：记为 P（ S）, 描述为：
– P（ S）
– { S=S-1；
– if （ S<0） W（ S） ；
– }
? （ 2） V操作：记为 V（ S）, 描述为：
– V（ S）
– { S=S+1；
– if （ S<=0） R（ S） ；
– }
利用 PV操作实现互斥
? 概念：
– 互斥信号量是根据临界资源的类型设置的。有几种
类型的临界资源就设置几个互斥信号量。它代表该
类临界资源的数量，或表示是否可用，其初值一般
为,1”。
? 例题
– 【 例 2-4】 在一个只允许单向行驶的十字路口，分别
有若干由东向西，由南向北的车辆在等待通过十字
路口。为了安全，每次只允许一辆车通过。当有车
辆通过时其它车辆必须等候，当无车辆在路口行驶
时则允许一辆车通过。请用 PV操作实现保证十字路
口安全行驶的自动管理系统。
– 【 例 2-5】 有 4位哲学家围着一个圆桌在思考和进餐，
每人思考时手中什么都不拿，当需要进餐时，每人需
要用刀和叉各一把，餐桌上的布置如图 2-12所示，共
有 2把刀和 2把叉，每把刀或叉供相邻的两个人使用。
请用信号量及 PV操作说明 4位哲学家的同步过程。
– 【 例 2-6】 在南开大学和天津大学之间有一条弯曲的
小路，其中从 S到 T有一段路每次只允许一辆自行车通
过，但其中有一个小的安全岛 M（同时允许两辆自行
车停留），可供两辆自行车错车时使用，如图 2-14所
示。试设计一个算法使来往自行车可以顺利通过。
利用 PV操作实现同步
? 概念
– 同步信号量是根据进程的数量设置的。一般情况下，
有几个进程就设置几个同步信号量，表示该进程是否
可以执行，或表示该进程是否执行结束。其初值一般
为,0”。
? 例子
– 【 例 2-7】 图 2-16给出了 4个进程合作完成某一任务的
前趋图，试说明这 4个进程间的同步关系，并用 PV操
作描述它们。
? 方法一：同步信号量用来表示该进程是否可以开始。
? 方法二：同步信号量用来表示该进程是否已经结束。
例子
? 【 例 2-8】 桌上有一个空盘子，只允许放一个水果。爸爸可以向盘
中放苹果，也可以向盘中放桔子，儿子专等吃盘中的桔子，女儿
专等吃盘中的苹果。规定当盘空时，一次只能放一只水果，请用
PV操作实现爸爸、儿子、女儿 3个并发进程的同步。
? 【 例 2-9】 有 3个进程 PA,PB,PC合作解决记录打印问题,PA将
记录从磁盘读入主存的缓冲区 1，每执行一次读一个记录； PB将
缓冲区 1的记录复制到缓冲区 2，每执行一次复制一个记录； PC将
缓冲区 2的记录打印出来，每执行一次打印一个记录；缓冲区的大
小等于一个记录的 PA,PB,PC大小。请用 PV操作来保证记录的
正确打印。
使用 PV操作实现进程的同步加互斥
? 概念
? 例子
– 【 例 2-10】 某数据库有一个写进程，多个读
进程，它们之间读、写操作的互斥要求是：
写进程运行时，其它读、写进程不能对数据
库操作，读进程之间不互斥，可以同时读数
据库。请用信号量及 PV操作描述这一组进
程的工作过程。
例题
? 【 例 2-11】 设有一个具有 N个信息元素的环形缓冲区,A
进程顺序地把信息写进缓冲区,B进程依次地从缓冲区
中读出信息，用 PV操作表示 A,B进程的同步算法。
? 【 例 2-12】 理发师理发问题。有一个理发师，一把理发
椅和 n把等候理发顾客坐的椅子。如果没有顾客，则理
发师在理发椅上睡觉；当一个顾客到来时，必须唤醒理
发师，进行理发；如果理发师正在理发，又有顾客来到
时，如果有空椅子可坐，他就坐下来等候，如果没有空
椅子，他就离开。请为理发师和顾客各编一个程序表述
他们的行为。
同步与互斥的解题思路
? ① 分清哪些是互斥问题 （ 互斥访问临界资源的 ）, 哪些是同步问题
（ 具有前后执行顺序要求的 ） 。
? ② 对互斥问题要设置互斥信号量, 不管有互斥关系的进程有几个或
几类, 通常只设置一个互斥信号量, 且初值为 1,代表一次只允许
一个进程对临界资源访问 。
? ③ 对同步问题要设置同步信号量, 通常同步信号量的个数与参与同
步的进程种类有关, 即同步关系涉及几类进程, 就有几个同步信号
量 。 同步信号量表示该进程是否可以开始或该进程是否已经结束 。
? ④在每个进程中用于实现互斥的 PV操作必须成对出现；用于实现
同步的 PV操作也必须成对出现，但可以分别出现在不同的进程中；
在某个进程中如果同时存在互斥与同步的 P操作，则其顺序不能颠
倒，必须先执行对同步信号量的 P操作，再执行对互斥信号量的 P操
作，但 V操作的顺序没有严格要求。
同步与互斥的解题步骤
? （ 1） 确定进程 。 包括进程的数量, 进程
的工作内容, 可以用流程图描述 。
? （ 2） 确定同步互斥关系 。 根据是否使用
的是临界资源, 还是处理的前后关系,
确定同步与互斥, 然后确定信号量的个
数, 含义, 以及对信号量的 P,V操作 。
? （ 3）用类 C语言描述同步或互斥算法。
管程的基本概念
? 概念
– 管程实际上是定义了一个数据结构和在该数
据结构上的能为并发进程所执行的一组操作，
这组操作能同步进程和改变管程中的数据。
? 说明：
– 管程由 3部分组成：局部于管程的共享变量
说明、对该数据结构进行操作的一组过程、
对局部于管程的数据设置初始值的语句。
– 每个管程都应该有唯一的名字来标识。
进程通信
? 概念
– 进程通信是指进程间的信息交换。
? 类型
– 共享存储器系统
– 消息传递系统
– 管道通信系统
共享存储器系统
? 概念
– 在共享存储器系统中，相互通信的进程共享某些数
据结构或共享存储区，进程之间能够通过它们进行
通信。
? 方式
– 共享数据结构方式
? 相互通信的诸进程公用某些数据结构，并通过这些数据交
换信息。
– 共享存储区方式
? 是在存储器中划出一块共享存储区，相互通信的诸进程可
以通过对共享存储区中的数据进行读或写来实现通信。
消息传递系统
? 概念
– 进程间的数据交换以消息为单位，用户直接利用系
统中提供的一组通信命令（原语）进行通信。
? 方式
– 直接通信方式
? 发送进程使用发送原语直接将消息发送给接收进程，并将
它挂在接收进程的消息缓冲队列上，接收进程使用接收原
语从消息缓冲队列中取出消息。
– 间接通信方式
? 发送进程使用发送原语直接将消息发送到某种中间实体中，
接收进程使用接收原语从该中间实体中取出消息。
管道通信系统
? 管道
– 管道是指连接读进程和写进程，以实现它们
之间通信的共享文件。
? 管道通信系统
– 向管道提供输入的发送进程（写进程），以
字符流形式将大量的数据送入管道，而接受
管道输出的接收进程（读进程），可以从管
道中接收数据。
进程调度
? 进程调度的类型
? 选择进程调度算法的原则
? 常用的进程调度算法
进程调度的类型
? 高级调度
? 低级调度
? 中级调度
高级调度
? 基本原理
– 高级调度又称为作业调度或长程调度，用于
决定把外存上处于后备队列中的哪些作业调
入主存，并为它们创建进程、分配必要的资
源，然后将新创建的进程排入就绪队列，准
备执行。
? 需要解决的问题
– 一是接纳多少个作业。
– 二是接纳哪些作业。
低级调度
? 基本原理
– 低级调度通常又称为进程调度或短程调度。它决定主存中的就绪队
列上的哪个进程（单处理器系统）将获得处理器，然后把处理器分
配给该进程，使其执行。
? 方式
– 非抢占方式
? 在某个进程正在占用处理器执行时，不允许其它任何进程抢占处
理器。
– 抢占方式
? 把处理器分配给某个进程后，在该进程尚未终止或阻塞时，允许
系统调度程序根据某种原则，暂停正在执行的进程，回收已经分
配的处理器，并将处理器重新分配给其它更为紧急的进程。
中级调度
? 基本原理
– 系统将那些暂时不能运行的进程从主存调到外存（仍
然保持进程状态）上的特定区域，这些在外存存放的
进程所处的状态称为就绪驻外状态或挂起状态。当这
些进程的运行条件具备，且主存又有空闲时，在中级
调度的控制下，再将处于外存上的那些重新具备运行
条件的就绪驻外进程调入主存，并将其状态修改为就
绪状态，放入就绪队列，等待进程调度。
? 目的
– 是为了进一步提高主存的利用率和系统的吞吐量。
选择进程调度算法的原则
? 面向用户的原则
– 周转时间短
– 响应时间快
– 截止时间有保证
– 优先权原则
? 面向系统的原则
– 系统吞吐量高
– 处理器利用率好
– 各类资源的平衡利用
常用的进程调度算法
? 先来先服务调度算法
? 短进程优先调度算法
? 时间片轮转调度算法
? 优先数调度算法
? 响应比高者优先调度算法
? 多级队列调度算法
先来先服务调度算法
? 原理
– 每次调度是从就绪队列中，选择一个最先进
入就绪队列的进程，把处理器分配给该进程，
使之得到执行。该进程一旦占有了处理器，
它就一直运行下去，直到该进程完成或因发
生事件而阻塞，才退出处理器。
? 特点
– 利于长进程，而不利于短进程。
短进程优先调度算法
? 原理
– 它是从就绪队列中选择一个估计运行时间最
短的进程，将处理器分配给该进程，使之占
有处理器并执行，直到该进程完成或因发生
事件而阻塞，然后退出处理器，再重新调度。
? 特点
– 照顾到了系统中占大部分的短进程，有效地
降低了进程的平均等待时间，提高了系统的
吞吐量，但对长进程不利。
时间片轮转调度算法
? 原理
– 系统将所有的就绪进程按进入就绪队列的先后次序
排列。每次调度时把 CPU分配给队首进程，让其执
行一个时间片，当时间片用完，由计时器发出时钟
中断，调度程序则暂停该进程的执行，使其退出处
理器，并将它送到就绪队列的末尾，等待下一轮调
度执行。
? 特点
– 为了保证人机交互的及时性，系统使每个进程依次
按时间片方式轮流地执行 。
优先数调度算法
? 原理
– 它是从就绪队列中选择一个优先权最高的进程，让其获得处理器并
执行。
? 方式
– 非抢占式优先数调度算法
? 系统一旦把处理器分配给就绪队列中优先权最高的进程后，该进程就占
有处理器一直运行下去，直到该进程完成或因发生事件而阻塞，才退出
处理器。
– 抢占式优先数调度算法
? 系统同样把处理器分配给当前就绪队列中优先权最高的进程，使之执行。
但在其执行期间，仍然会不断的有新的就绪进程进入就绪队列，如果出
现某个进程，其优先权比当前正在执行的进程的优先权还高时，进程调
度程序就会立即暂停当前进程的执行，而将处理器收回，并将处理器分
配给新出现的优先权更高的进程，让其执行。
响应比高者优先调度算法
? 原理
– 它是从就绪队列中选择一个响应比最高的进程，让
其获得处理器执行，直到该进程完成或因等待事件
而退出处理器为止。
? 特点
– 既照顾了短进程，又考虑了进程到达的先后次序，
也不会使长进程长期得不到服务，因此是一个比较
全面考虑的算法，但每次进行调度时，都需要对各
个进程计算响应比。所以系统开销很大，比较复杂。
多级队列调度算法
? 原理
– 是根据进程的类型或性质的不同，将就绪进
程分为若干个独立队列，不同类型或性质的
进程固定地分属于一个队列，每个队列可以
采用适合的调度算法，不同的队列可使用不
同的调度算法。
? 特点
– 同时具有多种操作方式 的进程调度
进程死锁
? 死锁的基本概念
? 死锁的预防
? 死锁的避免
? 死锁的检测与解除
死锁的基本概念
? 死锁的概念
– 是指多个进程因竞争资源而造成的一种僵局，若无外力的作
用，这些进程将都不能再继续执行。
? 产生死锁的原因
– 竞争资源
– 进程推进顺序非法
? 产生死锁的必要条件
– 互斥条件
– 请求和保持条件
– 不剥夺条件
– 环路等待条件
死锁的预防
? 原理
– 该方法是通过对资源分配的原则进行限制，
从而使产生死锁的四个必要条件中的第 2,3、
4个条件之一不能成立，来预防产生死锁。
? 方法
– 破坏“不剥夺”条件
– 破坏“请求和保持”条件
– 破坏“环路等待”条件
死锁的避免
? 原理
– 在死锁的避免中，所施加的限制较弱，将获得较好
一些的系统性能。该方法把系统状态分为安全状态
和不安全状态，只要能使系统始终处于安全状态，
便可以避免发生死锁。
? 安全状态
– 是指系统能按某种顺序为每个进程分配所需资源，
直到最大需求，使每一个进程都可以顺利完成。
? 利用银行家算法避免死锁
银行家算法的处理步骤
? 银行家算法的处理步骤为：
– （ 1） 列出某一时刻资源分配表, 格式如表 2-4所示 。
– （ 2） 拿可用资源量与每一个进程所需资源量进行比
较, 可用资源量不少于所需资源量时, 把资源分配给
该进程 。 新的可用资源量为原有可用资源量加上该进
程已分配资源量 。
– （ 3）重复（ 2），直到所有进程都执行完，即可判断
能否获得一个安全资源分配序列。
? 例题
– 【 例 2-18】
死锁的检测与解除
? 死锁的检测
– 利用死锁定理
? 死锁的解除
– 剥夺资源法
– 撤消进程法
本章小结
? 处理器管理的主要任务是分配处理器，
? 主要目的是提高处理器的使用效率。
? 它的主要功能有：进程控制、进程同步、进程通信和进程
调度。
? 熟悉和掌握以下基本概念：
– 进程、临界资源、同步、互斥、原语、线程、管程、管道、死锁
? 熟悉和掌握以下基本知识：
– 1．并发与并行。 2．进程描述与控制 。
– 3．同步控制机制 。 4．进程调度 。
– 5．进程通信 。 6．进程死锁 。
习 题
? 一、单项选择题
– 1-22题
? 二、判断题
– 1-10题
? 三、填空题
– 1-15题
? 四、区分下列概念
– 1-8题
? 五、简答题
– 1-7题
? 六、应用题
– 1-19题
