第二章 进程管理
多道程序设计
进程
进程间的相互作用
进程间的通信
进程调度（ CPU调度）
死锁
线程
2.1 多道程序设计
顺序程序
并发程序
多道程序设计
2.1.1 顺序程序程序：
指令或语句序列,体现了某种算法,所有程序是顺序的顺序环境：
在计算机系统中只有一个程序在运行,这个程序独占系统中所有资源,其执行不受外界影响特征：
程序执行的顺序性
程序执行的封闭性独占资源,执行过程中不受外界影响
程序结果的可再现性程序运行结果与程序执行速度无关,
只要初始状态相同,结果应相同
2.1.2 并发程序并发环境：
在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态,并且次序不是事先确定的
A
B
A
B
B
A
A
B
特征：
（ 1） 程序结果的不可再现性并发程序执行的结果与其执行的相对速度有关,是不确定的
（ 2） 在并发环境下程序的执行是间断性的执行 —— 停 —— 执行
（ 3）资源共享系统中资源被多个进程使用
（ 4）独立性和制约性独立的相对速度、起始时间进程之间可相互作用（相互制约）
可分为直接作用和间接作用
（ 5）程序和计算不再一一对应
（计算：一个程序的执行）
2.1.2 并发程序引入并发的目的：
引入并发是为了提高资源利用率,从而提高系统效率 。
并发与并行概念的区别：
concurrency,parallel
在顺序环境下
CPU利用率 = 40/80 = 50%
DEV1利用率 = 18.75%
DEV2利用率 = 31.25%
C PU D E V 1 D E V 2 C PUC PU
A
10 15 20 30 40
t(s )
D E V 2C PUD E V 2 D E V 1 C PU
B
10 20 30 40
t(s )
25
例：
例：
在并发环境下 CPU利用 = 89%
DEV1并发环境下利用 = 33%
DEV2并发环境下利用 = 66%
0 1 0 2 0 3 0 3 5 4 5
CP U DEV 1 - - - C P U D EV 2 C P U
DEV 1 CP U DEV 2 CP U - - - - DEV 2
T ( s )
2.1.3 多道程序设计定义,Multiprogramming
多道程序设计是指允许多个程序同时进入内存并运行
（ 引入目的是为了提高系统效率 ）
与并发不完全是一个概念,但效果相似考虑因素：
在多道程序环境下如何向用户提供服务
在并发程序之间如何正确传递消息 （ 通讯 ）
如何对 CPU进行调度,保证每个用户相对公平地得到 CPU
（ CPU是一个只可调度,不可分配的资源 ）
如何管理其他资源当各用户对资源使用上发生冲突时,如何处理竞争对 CPU只能通过调度来解决竞争问题,而对于其他资源通过申请 — 分配 — 使用 — 回收的办法进行管理,当且仅当占有 CPU的时候才可以申请,否则要排队等候
2.1.4 与时间有关的错误一个飞机订票系统,两个终端,运行 T1,T2进程
T1,T2:
...,..
Read(x); Read(x);
if x>=1 then if x>=1 then
x:=x-1; x:=x-1;
write(x); write(x);
...,..
Cobegin
get;
copy;
put;
Coend
get copy put
f s t g
复制一个记录
f s t g
初始状态 3,4,...,m 2 2 (1,2)
g,c,p 4,5,...,m 3 3 (1,2,3)?
g,p,c 4,5,...,m 3 3 (1,2,2)?
c,g,p 4,5,...,m 3 2 (1,2,2)?
c,p,g 4,5,...,m 3 2 (1,2,2)?
p,c,g 4,5,...,m 3 2 (1,2,2)?
p,g,c 4,5,...,m 3 3 (1,2,2)?
设信息长度为 m,有多少种可能性？
c pc
g
p
c
g
p
g
并行环境下程序间的制约关系
2.2 进程
进程的概念
进程的状态及其转换
进程控制块 （ Process Control Block）
进程的特征
OS 对进程的要求
OS 必须交替执行多个进程,以便最大程度的使用 CPU,同时提供合理的响应时间
OS 必须将资源分配给进程,同时避免死锁
OS必须支持进程间通信以及用户进程创建
2.2.1 进程的概念定义,Process
进程是具有独立功能的程序关于某个数据集合上的一次运行活动,是系统进行资源分配和调度的独立单位进程何时创建?
提交一个批处理作业
用户登录
由 OS创建,用以向一用户提供服务 ( 如：打印文件 )
由已存在的一进程创建
– 一个用户程序可创建多个进程
批处理作业发出暂停 （ Halt） 指令
用户退出登录
进程执行一中止服务请求
出错及失败因素进程何时中止?
进程中止的原因
正常结束
给定时限到
缺少内存
存储器出界
保护性出错
– 例子,写只读文件
算术错
超出时间
– 进程等待超过对某事件的最大值进程中止的原因
I/O 失败
无效指令
– 如试图执行数据
特权指令
操作系统干预
– 如当死锁发生时
父进程请求中止某一子进程
父进程中止,所以子进程也中止程序与进程之间的区别：
进程更能真实地描述并发,而程序不能
进程是由程序和数据两部分组成的
程序是动态的,进程是动态的
进程有生命周期,有诞生有消亡,短暂的；
而程序是相对长久的
一个程序可对应多个进程,反之亦然
进程具有创建其他进程的功能,而程序没有进程的分类：
系统进程
用户进程
（ 系统进程优先于用户进程 ）
2.2.2 进程的基本状态及其转换进程的三种基本状态：
进程在生命消亡前处于且仅处于三种基本状态之一不同系统设置的进程状态数目不同
运行态 （ Running）,
进程占有 CPU,并在 CPU上运行
就绪态 （ Ready）,
一个进程已经具备运行条件,但由于无 CPU暂时不能运行的状态 （ 当调度给其 CPU时,立即可以运行 ）
等待态 （ Blocked）,阻塞态,挂起态,封锁态冻结态,睡眠态指进程因等待某种事件的发生而暂时不能运行的状态
（ 即使 CPU空闲,该进程也不可运行 ）
运行就绪 等待进程的状态及其转换
进程状态转换：
在进程运行过程中,由于进程自身进展情况及外界环境的变化,这三种基本状态可以依据一定的条件相互转换
就绪 — 运行
运行 — 就绪
运行 — 等待
等待 — 就绪进程转换
就绪 --> 运行
– 时间一到,调度程序选择一个新的进程运行
运行 --> 就绪
– 运行进程用完了时间片
– 运行进程被中断,因为一高优先级进程处于就绪状态
运行 --> 阻塞
– 当一进程所需的东西必须等待时
OS尚未完成服务
对一资源的访问尚不能进行
初始化 I/O 且必须等待结果
等待某一进程提供输入 (IPC)
阻塞 --> 运行
– 当所等待的事件发生时进程转换其他状态：
创建状态,终止状态
挂起状态
（ 调节负载,对换,父进程,操作系统,终端用户 ）
创建 (新 new)状态
– OS 已完成为创建一进程所必要的工作
已构造了进程标识符
已创建了管理进程所需的表格
– 但还没有允许执行该进程 (尚未同意 )
因为资源有限
终止 （ 退出 exit)状态
– 中止后进程移入该状态
– 它不再有执行资格
– 表格和其它信息暂时由辅助程序保留
例子,为处理用户帐单而累计资源使用情况的财务程序
当数据不再需要后,进程 (和它的表格 )被删除五状态进程模型准备退出：父进程可中止子进程新状态转换 (中期调度 )
阻塞 -->阻塞挂起
– 当所有进程都阻塞,OS会安排空间让一就绪进程进入内存
阻塞挂起 --> 就绪挂起
– 当等待的事件发生时 (状态信息已在 OS中 )
就绪挂起 -->就绪
– 当内存中没有就绪进程时
就绪 -->就绪挂起 (较少见 )
– 当没有被阻塞的进程,而为了性能上的考虑,
必须释放一些内存时七状态进程模型活动挂起事件发生事件发生 等待事件挂起调度超时释放活动挂起
2.2.3 进程控制块
（ Process Control Block）
概念：
系统为了管理进程设置的一个专门的数据结构,用它来记录进程的外部特征,描述进程的运动变化过程系统利用 PCB来控制和管理进程,所以 PCB
是系统感知进程存在的唯一标志进程与 PCB是一一对应的进程映象 (进程要素 )
用户程序
用户数据
栈
– 用于过程调用和参数传递
进程控制块 PCB (执行上下文 )
– 控制进程所需的数据 (进程属性 ),包括,
进程标识符信息
处理器状态信息
进程控制信息
PCB的内容：
调度信息：
进程名；进程的内部标识；用户名；进程状态；进程优先级；进程的存储信息 （ 起始地址,长度 ） ；进程资源清单；进程家族关系；进程的队列指针；进程的消息队列指针；进程当前打开的文件 …,..
现场信息：
记录了重要的寄存器； (虚 )时钟等内容进程标识符 (在 PCB中 )
可使用一些数字标识符
– 统一进程标识符 (必然的 )
索引至 (直接或间接 ) 主进程表
– 用户标识符
与某个作业对应的用户
– 创建本进程的某个进程的标识符处理器状态信息 (在 PCB中 )
处理器寄存器内容
– 用户可见寄存器
– 控制和状态寄存器
– 栈指针
程序状态字 (PSW)
– 包含状态信息
– 例子,在 Pentium机中的 EFLAGS寄存器进程控制信息 (在 PCB中 )
调度和状态信息
– 进程状态 (如,运行,就绪,阻塞,..)
– 进程优先级
– 该进程在等待的事件 (若被阻塞 )
数据结构信息
– 进程可能需要有指向其他 PCB的指针,父 -子进程关系及其它结构
进程间通信
– IPC可能需要标志和信号
进程特权
– 如,访问特定的内存地址,..
存储管理
– 指向赋予该进程的段 /页表的指针
所拥有的资源和使用情况
– 使用中的资源,打开的文件,I/O设备,..
– (CPU,I/O...)的时间使用史进程控制信息 (在 PCB中 )
执行的方式
为了提供对 PCB (和 OS其它数据 )的保护,
多数处理器支持至少两种执行方式,
– 特权方式 (又称作系统方式,内核方式,管理方式,控制方式 )
操作控制寄存器,基本 I/O指令,存储管理,..
– 用户方式
为此,CPU提供一个 (或一些 )方式位,
这些二进制位只能被中断,陷阱或 OS调用所设置
PCB表：
系统把所有 PCB组织在一起,并把它们放在内存的固定区域,就构成了 PCB表
PCB表的大小决定了系统中最多可同时存在的进程个数,称为系统的并发度
（ 注：多道程序中的多道与系统并发度不同 ）
进程控制块 （ Process Control Block）
PC B 1
PC B 2
PC B 3
PC B 4
PC B 5
PC B 6
PC B 7
PC B n
......
空 PCB
运行态就绪态等待 1
等待 2
6
7
5
10
15
PCB表组织方式：
常用索引方式,对具有相同状态的进程,
分别设置各自的 PCB索引表,表明 PCB在
PCB表中的地址
（ 其他方式：线性表或链表 ）
进程队列：不同状态进程分别组成队列运行队列,就绪队列,等待队列
2.2.4 进程控制创建,撤消进程以及完成进程各状态之间的转换 。 由具有特定功能的原语完成 。
进程创建原语进程撤消原语阻塞原语唤醒原语挂起原语激活 （ 解挂 ） 原语进程的创建
创建一个 PCB
赋予一个统一进程标识符
为进程映象分配空间
初始化进程控制块
– 许多默认值 (如,状态为 New,无 I/O设备或文件,..)
设置相应的链接
– 如,把新进程加到就绪队列的链表中进程撤消收回进程所占有的资源撤消该进程的 PCB
进程阻塞处于运行状态的进程,在其运行过程中期待某一事件发生,如等待键盘输入,
等待磁盘数据传输完成,等待其它进程发送消息,当被等待的事件未发生时,
由进程自己执行阻塞原语,使自己由运行态变为阻塞态进程唤醒
2.2.5 进程的特征
并发性任何进程都可以同其他进程一起向前推进
动态性进程对应程序的执行进程是动态产生,动态消亡的进程在其生命周期内,在三种基本状态之间转换
独立性进程是 CPU调度的一个独立单位
交互性指进程在执行过程中可能与其它进程产生直接或间接的关系
异步性每个进程都与其相对独立的不可预知的速度向前推进
结构性：
进程的组成：程序 +数据 +PCB
可再入程序：
可被多个进程同时调用的程序,具有下列性质：
它是纯代码的,即在执行过程中自身不改变,调用它的进程应该提供数据区
【 思考题 】,
1,如果系统中有 N个进程,运行的进程最多几个,
最少几个；就绪进程最多几个最少几个；等待进程最多几个,最少几个？
2,有没有这样的状态转换,为什么？
等待 — 运行； 就绪 — 等待
3,一个状态转换的发生,是否一定导致另一个转换发生,列出所有的可能
4,举 3个日常生活中类似进程的例子
2.3 进程间的相互作用
进程间的联系
进程的同步机制 ── 信号量及 P.V操作
（ 解决进程同步互斥问题 ）
2.3.1 进程间的联系相交进程与无关进程相交进程：指多个并发进程在逻辑上有某种联系无关进程 （ 不相交进程 ）,在逻辑上无任何联系的进程直接作用和间接作用直接作用：
进程间的相互联系是有意识的安排的,
直接作用只发生在相交进程间间接作用：
进程间要通过某种中介发生联系,是无意识安排的,可发生在相交进程之间,
也可发生在无关进程之间进程的同步（直接作用）
进程的同步,synchronism
指系统中一些进程需要相互合作,共同完成一项任务 。 具体说,一个进程运行到某一点时要求另一伙伴进程为它提供消息,在未获得消息之前,该进程处于等待状态,获得消息后被唤醒进入就绪态例,
司机 P1 售票员 P2
REPEAT REPEAT
启动 关门正常运行 售票到站停 开门
UNTIL FALSE UNTIL FALSE
进 程 的 互 斥 （ 间 接 作 用 ） mutual
exclusion
由于各进程要求共享资源,而有些资源需要互斥使用,因此各进程间竞争使用这些资源,进程的这种关系为进程的互斥临界资源,critical resource
系统中某些资源一次只允许一个进程使用,
称这样的资源为临界资源或互斥资源或共享变量临界区 （ 互斥区 ）,critical section
一个程序片段的集合,这些程序片段分散在不同的进程中,对某个共享的数据结构 （ 共享资源 ） 进行操作在进程中涉及到临界资源的程序段叫临界区
a,= a -1
print (a)
a,= a +1
print (a)
P1
互斥
P2
互斥
If a < 0
then
a,= a +1
else
a:= a-1
P3
互斥 进程的互斥（间接作用）
程序 段 1 程序 段 2 程序 段 n
共 享 变量进程的互斥（间接作用）
使用互斥区的原则：
有空让进,当无进程在互斥区时,任何有权使用互斥区的进程可进入无空等待,不允许两个以上的进程同时进入互斥区有限等待,任何进入互斥区的要求应在有限的时间内得到满足使用互斥区的原则：
前提：任何进程无权停止其它进程的运行进程之间相对运行速度无硬性规定解决方法：
硬件 （ 当一个进程进入临界区,就屏蔽所有中断,但成本高 ）
软件 （ 用编程解决,但常常忙等待 ）
软件解法 (1)
free,表示临界状态
true,无进程在临界区 (初值 )
false:有进程在临界区
....
L,if free then
begin
free:=false;
‘进入临界区 ’
end
else goto L;
free:=true
软件解法 (2)
turn,true P进入临界区
false Q 进 入 临 界 区
....
P,repeat until turn;
‘进入临界区 ’
turn:=flase;
Q,repeat until not turn;
‘ 进 入 临 界 区 ’
turn:=true;
软件解法,(3)
pturn,qturn,初值为 false
P进入临界区的条件,pturn∧ not qturn
Q进入临界区的条件,not pturn∧ qturn
P,..,Q,....
pturn:=true; qturn:=ture;
repeat until not qturn; repeat until not pturn
‘进入临界区 ’ ‘ 进入临界区 ’
pturn:=false; qturn:=false
...,..
软件解法 (4) Dekker算法,
在解法 (3)基础上引入 turn枚举类型 初值任意
P,Repeat
pturn:=true;
while qturn do
if turn=2 then begin
pturn:=false;
while turn=2 do；； pturn:=true
end;
'进入临界区 '
turn:=2;
pturn:=false;
.....
Until false
(4) Dekker算法,
Q,Repeat
qturn:=true;
while pturn do
if turn=1 then begin
qturn:=false;
while turn=1 do
qturn:=true
end;
' 进 入 临 界 区 '
turn:=1;
qturn:=false;
.....
Until false
软件解法的缺点：
1,忙等待
2,实现过于复杂,需要高的编程技巧硬件解法 (1)
,测试并建立”指令
Function Test_and_Set
(var target:boolean):boolean
begin
Test_and_Set:=target;
target:=true
end
硬件解法 (1)
Var lock:boolean;
进入临界区前执行：
While Test_and_Set(lock) do
skip;
离开临界区后执行：
lock:=false;
硬件解法 (2)
,交换”指令
Function Swap(var a,b:boolean)
Var temp:boolean;
begin
temp:=a;
a:=b;
b:=temp
end
每一组共享变量定义一个全局变量
Var lock:boolean;
每个进程定义一个局部变量
Var key:boolean;
进入临界区前执行：
key:=true;
repeat
swap(lock,key);
until key=false;
离开临界区后执行,lock:=false;
硬件解法 (3)
,开关中断”指令进入临界区前执行：
执行,关中断,指令离开临界区后执行：
执行,开中断,指令
2.3.2 进程的同步机制 ──
信号量及 P.V操作（解决进程同步）
同步机制：
信号量及 P,V操作；管程；条件临界域；路径表达式等 （ 用于集中式系统中 ）
会合；通信顺序进程；分布进程；远程过程调用等 （ 适用于分布式系统中 ）
同步机制应满足的基本要求：
* 描述能力
* 可以实现
* 效率高
* 使用方便信号量,semaphore
是一个数据结构,定义如下：
TYPE semaphore= RECORD
Value,integer
Queue,Pointer_PCB
END
信号量说明：
VAR,S,semaphore
P.V操作
P操作
P(s),
s,Value,= s,Value - 1;
IF s,Value < 0 then
将该进程状态置为等待状态然后将该进程的 PCB插入相应的等待队列末尾
P.V操作
V操作
V(s),
s,Value,= s,Value + 1;
IF s,Value < = 0 then
唤醒相应等待队列中等待的一个进程改变其状态为就绪态并将其插入就绪队列
P,V操作为原语操作原语,primitive or atomic action
是由若干多机器指令构成的完成某种特定功能的一段程序,具有不可分割性即原语的执行必须是连续的,在执行过程中不允许被中断实现：开关中断信号量的使用,
必须置一次且只能置一次初值初值不能为负数只能执行 P,V操作用 P.V操作解决进程间互斥问题
P(S)
V(S)
P(S)
V(S)
P(S)
V(S)
P1 P2 P2
互斥区经典的生产者 ─ 消费者问题消费者生产者缓冲区经典的生产者 ─ 消费者问题同步问题：
P进程不能往,满,的缓冲区中放产品,设置信号量为 S1
Q进程不能从,空,的缓冲区中取产品,设置信号量 S2
P,Q：
Repeat Repeat
生产一个产品； P(s2);
送产品到缓冲区； 从缓冲区取产品 ；
V(s2); V(s1);
P(s1) 消费产品
Until false; Until false;
S1初值为 0,S2初值为 0
P：
Repeat
P(s1);
生产一个产品；
送产品到缓冲区 ；
V(s2)
Until false;
S1初值为 1,S2初值为 0
【 思考题 】 要不要对缓冲区 （ 临界资源 ）
进行互斥操作？
.....
.
P Q
放消息 取消息
n
n 个缓冲区
(Buffer)
i
j
P,
I:= 0
REPEAT
生 产 产 品 ；
P(S1)
往 Buffer [I] 中 放 产 品 ；
V(S2)
I:=(I+1) mod n
UNTIL false
Q：
J:= 0
REPEAT
P(S2)
从 Buffer[J]取产品；
V(S1)
消费产品
J:=(J+1) mod n
UNTIL false
P.V操作讨论
1) 信号量的物理含义：
S>0表示有 S个资源可用
S=0表示无资源可用
S<0则 | S |表示 S等待队列中的进程个数
P(S):表示申请一个资源
V(S)表示释放一个资源 。 信号量的初值应该大于等于 0
2) P.V操作必须成对出现,有一个 P操作就一定有一个 V操作当为互斥操作时,它们同处于同一进程当为同步操作时,则不在同一进程中出现如果 P(S1)和 P(S2)两个操作在一起,那么 P
操作的顺序至关重要,一个同步 P操作与一个互斥 P操作在一起时同步 P操作在互斥 P操作前而两个 V操作无关紧要
3） P.V操作的优缺点优点：
简单,而且表达能力强 （ 用 P.V操作可解决任何同步互斥问题 ）
缺点：
不够安全； P.V操作使用不当会出现死锁；
遇到复杂同步互斥问题时实现复杂
【 作业 】
1.用 P.V操作解决下图之同步问题,
get copy put
f s t g
2.用 P.V操作解决司机与售票员的问题司机进程：
REPEAT
启动车辆正常驾驶到站停车
UNTIL …
售票员进程：
REPEAT
关门售票开门
UNTIL …
2.3.3 IPC经典问题
1.读者写者问题有两组并发进程,
读者和写者,共享一组数据区要求：
允许多个读者同时执行读操作不允许读者,写者同时操作不允许多个写者同时操作第一类：读者优先如果读者来：
1） 无读者,写者,新读者可以读
2） 有写者等,但有其它读者正在读,则新读者也可以读
3） 有写者写,新读者等如果写者来：
1） 无读者,新写者可以写
2） 有读者,新写者等待
3） 有其它写者,新写者等待读者与写者问题读者,Repeat
P(mutex);
readcount:=readcount+1;
if readcount=1
then P (w);
V(mutex);
读
P(mutex);
readcount:=readcount-1;
if readcount=0
then V(w);
V(mutex);
Until false
写者：
Repeat
P(w);
写
V(w);
Until false
2.哲学家就餐问题有五个哲学家围坐在一圆桌旁,桌中央有一盘通心粉,每人面前有一只空盘子,每两人之间放一只筷子每个哲学家的行为是思考,感到饥饿,然后吃通心粉为了吃通心粉,每个哲学家必须拿到两只筷子,并且每个人只能直接从自己的左边或右边去取筷子
Repeat
思考；
取 fork[i];取 fork[(i+1) mod 5]；
进食；
放 fork[i];放 fork[(i+1) mod 5]；
Until false;
为防止死锁发生可采取的措施：
最多允许 4个哲学家同时坐在桌子周围
仅当一个哲学家左右两边的筷子都可用时,
才允许他拿筷子 （?）
给所有哲学家编号,奇数号的哲学家必须首先拿左边的筷子,偶数号的哲学家则反之为了避免死锁,把哲学家分为三种状态,思考,饥饿,进食,并且一次拿到两只筷子,
否则不拿
state:array[0..4] of
(思考,饥饿,进食 ） ；
ph,array[0..4] of semaphore;
mutex:semaphore;
i:0..4;
Procedure test(i:=0…4);
begin
if (state[ i ] = 饥饿 ) And
(state[(i-1)mod5]<>进食 ) And
(state[(i+1)mod5]<>进食 )
then begin
state[ i ]=进食
V(ph[ i ])
end
end
Procedure philosopher(i,0～ 4)
Begin
Repeat
思考 ；
state[i ]:=饥饿 ；
P(mutex);
test(i);
V(mutex);
P(ph[ i ]);
拿左筷子；
拿右筷子；
进食；
放左筷子；
放右筷子 ；
P(mutex)
state[ i ]:=思考；
test([i-1]mod5);
tset([i+1]mod5);
V(mutex);
until fales
End
state[ I ]=思考
ph[ I ]=0
mutex=1
【 作业 】
1,推广例子中的消息缓冲问题。
消息缓冲区为 k个，有 m个发送进程，
n个接收进程，每个接收进程对发送来的消息都必须取一次
2.第二类读者写者问题：
写者优先条件：
1） 多个读者可以同时进行读
2） 写者必须互斥 （ 只允许一个写者写,也不能读者写者同时进行 ）
3） 写者优先于读者 （ 一旦有写者,则后续读者必须等待,唤醒时优先考虑写者 ）
3.有一个系统,定义 P,V操作如下：
P(s):
s:=s-1;
if s<0 then
将本进程插入相应队列末尾等待；
V(s)：
s:=s+1;
if s<=0 then
从相应等待队列队尾唤醒一个进程,将其插入就绪队列；
问题：
1） 这样定义 P,V操作是否有问题？
2） 用这样的 P,V操作实现 N个进程竞争使用某一共享变量的互斥机制 。
3） 对于 2） 的解法,有无效率更高的方法 。
如有,试问降低了多少复杂性？
4.理发师睡觉问题理发店里有一位理发师,一把理发椅和 N
把供等候理发的顾客坐的椅子如果没有顾客,则理发师便在理发椅上睡觉 。 当一个顾客到来时,他必须先唤醒理发师如果顾客到来时理发师正在理发,则如果有空椅子,可坐下来等；否则离开
2.3.2 进程的同步机制 ── 管程管程的提出采用 PV同步机制来编写并发程序,对于共享变量及信号量变量的操作将被分散于各个进程中缺点：
（ １ ） 易读性差,因为要了解对于一组共享变量及信号量的操作是否正确,则必须通读整个系统或者并发程序
（ ２ ） 不利于修改和维护,因为程序的局部性很差,所以任一组变量或一段代码的修改都可能影响全局
（ ３ ） 正确性难以保证,因为操作系统或并发程序通常很大,要保证这样一个复杂的系统没有逻辑错误是很难的管程：一种同步机制
(管程 -类程 -进程 )
管程定义,
指关于共享资源的数据及在其上操作的一组过程或共享数据结构及其规定的所有操作系统按资源管理的观点分解成若干模块,用数据表示抽象系统资源,同时分析了共享资源和专用资源在管理上的差别,按不同的管理方式定义模块的类型和结构,使同步操作相对集中,从而增加了模块的相对独立性管程：集中式同步机制,它的基本思想是将共享变量以及对共享变量能够进行的所有操作集中在一个模块中,一个操作系统或并发程序由若干个这样的模块所构成,由于一个模块通常较短,模块之间关系清晰,提高了可读性,便于修改和维护,正确性易于保证管程的形式
TYPE monitor_name = MONITOR;
共享变量说明
define 本管程内所定义,本管程外可调用的过程 （ 函数 ） 名字表
use 本管程外所定义,本管程内将调用的过程 （ 函数 ） 名字表
PROCEDURE 过程名 （ 形参表 ） ；
过程局部变量说明；
BEGIN
语句序列；
END;
......
FUNCTION 函数名 （ 形参表 ）,值类型；
函数局部变量说明；
BEGIN
语句序列；
END;
......
BEGIN
共享变量初始化语句序列；
END;
管程的三个主要的特性：
（ 一 ） 模块化,一个管程是一个基本程序单位,可以单独编译
（ 二 ） 抽象数据类型,管程是一种特殊的数据类型,其中不仅有数据,而且有对数据进行操作的代码
（ 三 ） 信息掩蔽,管程是半透明的,
管程中的外部过程 （ 函数 ） 实现了某些功能,管程中的外部过程 （ 函数 ） 实现了某些功能,至于这些功能是怎样实现的,在其外部则是不可见的管程有如下几个要素：
（ 一 ） 管程中的共享变量在管程外部是不可见的,外部只能通过调用管程中所说明的外部过程
（ 函数 ） 来间接地访问管程中的共享变量
（ 二 ） 为了保证管程共享变量的数据完整性,规定管程互斥进入
（ 三 ） 管程通常是用来管理资源的,因而在管程中应当设有进程等待队以及相应的等待及唤醒操作问题：多个进程出现在管程中当一个进入管程的进程执行等待操作时,它应当释放管程的互斥权；
当一个进入管程的进程执行唤醒操作时 （ 如Ｐ唤醒Ｑ ）,管程中便存在两个同时处于活动状态的进程处理方法有三种：
Ｐ等待Ｑ继续,直到Ｑ退出或等待?
Ｑ等待Ｐ继续,直到Ｐ等待或退出
规定唤醒为管程中最后一个可执行的操作因为管程是互斥进入的,所以当一个进程试图进入一个巳被占用的管程时它应当在管程的入口处等待,因而在管程的入口处应当有一个进程等待队列,称作入口等待队列如果进程Ｐ唤醒进程Ｑ,则Ｐ等待
Ｑ继续,如果进程Ｑ在执行又唤醒进程Ｒ,则Ｑ等待Ｒ继续,……,如此,
在管程内部,由于执行唤醒操作,可能会出现多个等待进程,因而还需要有一个进程等待队列,这个等待队列被称为紧急等待队列 。 它的优先级应当高于入口等待队列的优先级由于管程通常是用于管理资源的,
因而在管程内部,应当存在某种等待机制 。 当进入管程的进程因资源被占用等原因不能继续运行时使其等待 。
为此在管程内部可以说明和使用一种特殊类型的变量 。
称作条件变量：
VAR C:condition;
对于条件型变量,可以执行 wait和
signal操作：
wait（ c）,如果紧急等待队列非空,
则唤醒第一个等待者；否则释放管程的互斥权,执行此操作的进程的
PCB入 c链尾部
signal（ c）,如果 c链为空,
则相当于空操作,执行此操作的进程继续；否则唤醒第一个等待者,执行此操作的进程的
PCB入紧急等待队列的尾部管程的实现两个主要途径：
* 直接构造
* 间接构造,即用某种已经实现的同步机制去构造前者效率高例子：用 PV操作构造管程管程的四个组成部分：
名称
数据结构说明
对该数据结构进行操作的一组过程 /函数
初始化语句
TYPE one_instance=RECORD
mutex:semaphore;（ 初值 1）
urgent:semaphore;（ 初值 0）
urgent_count:integer;（ 初值 0）
END;
TYPE
monitor_elements=MODULE;
define enter,leave,wait,signal;
mutex（ 入口互斥队列 ）
urgent（ 紧急等待队列 ）
urgent_count（ 紧急等待计数 ）
PROCEDURE enter(VAR
instance:one_instance);
BEGIN
P(instance.mutex)
END;
PROCEDURE leave(VAR
instance:one_instance);
BEGIN
IF instance.urgent_count >0 THEN
BEGIN instance.urgent--;
V(instance.urgent)
END
ELSE
V(instance.mutex)
END;
PROCEDURE wait(VAR
instance:one_instance;VAR s:semephore;VAR
count:integer);
BEGIN
count++;
IF instance.urgent_count>0 THEN
BEGIN
instance.urgent_count--;
V(instance.urgent)
END
ELSE
V(instance.mutex);
P(s);
END;
PROCEDURE signal(VAR
instance:one_instance;VAR
s:semaphore;VARcount:integer);
BEGIN
IF count>0 THEN
BEGIN
count--;
instance.urgent_count++;
V(s);
P(instance.urgent)
END
END;
例子：一个信息缓冲区是一个共享资源抽象成一个数据结构：数组构造一些操作 （ 过程或函数 ）
发送：向缓冲区发消息接收：从缓冲区取消息隐藏了内部的数据结构和实现细节例子：读者 -写者问题
TYPEr_and_w=MODULE;
VAR instance:one_instance;
rq,wq:semaphore;
r_count,w_count:integer;
reading_count,write_count:integer;
define
start_r,finish_r,start_w,finish_w;
use monitor_elements.enter,
monitor_elements.leave,
monitor_elements.wait,
monitor_elements.signal;
PROCEDUREstart_r;
BEGIN
monitor_elements.enter(instance);
IF write_count>0THEN
monitor_elements.wait
(instance,rq,r_count);
reading_count++;
monitor_elements.signal
(instance,rq,r_count);
monitor_elements.leave(instance);
END;
PROCEDUREfinish_r;
BEGIN
monitor_elements.enter(instance);
reading_count--;
IF reading_count=0 THEN
monitor_elements.signal
(instance,wq,w_count);
monitor_elements.leave(instance);
END;
PROCEDUREstart_w;
BEGIN
monitor_elements.enter(instance);
write_count++;
IF (write_count>1)
OR(reading_count>0) THEN
monitor_elements.wait
(instance,wq,w_count);
monitor_elements.leave(instance);
END;
BEGIN
reading_count::=0;
write_count::=0;
r_count:=0;
w_count::=0;
END;
读者的活动：
r_and_w.start_r;
读操作；
r_and_w.finish_r;
写者的活动：
r_and_w.start_w;
写操作；
r_and_w.finish_w;
管程和进程的异同点：
（ 1） 设置进程和管程的目的不同
（ 2） 系统管理数据结构进程,PCB
管程：等待队列
（ 3） 管程被进程调用
（ 4） 管程是操作系统的固有成分,无创建和撤消
2.4 进程通信概述消息缓冲通信方式
2.4.1 概述
P.V操作实现的是进程之间的低级通讯,
所以 P.V为低级通讯原语 。 它只能传递简单的信号,不能传递交换大量信息如果要在进程间传递大量信息则要用
Send / Receive原语 （ 高级通讯原语 ）
2.4.1 概念进程通信的方式共享内存,
相互通信的进程间设有公共内存,一组进程向该公共内存中写,另一组进程从公共内存中读,通过这种方式实现两组进程间的信息交换这种通信模式需要解决两个问题？
进程通信的方式消息传递,
系统为进程提供了两个高级通讯原语 send
和 receive
send：
当要进行消息传递时执行 send
receive：
当接收者要接收消息时执行 receive
共享文件模式,
管道通信消息传递模式
消息缓冲在内存中开设缓冲区,发送进程将消息送入缓冲区,接收进程接收传递来的缓冲区
信箱通信直接方式：
发送进程发消息时要指定接收进程的名字,
反过来,接收时要指明发送进程的名字
Send(receiver,message)
Receiver(sender,message)
* 对称形式：一对一
* 非对称形式：多对一 （ 顾客 /服务员 ）
有缓冲 （ 有界,无界 ）,无缓冲间接方式：
发送进程发消息时不指定接收进程的名字,而是指定一个中间媒介,即信箱 。
进程间通过信箱实现通信发送原语,send(MB,Message)
接收原语,receive(MB,Message)
2.4.2 消息缓冲
（ 有界缓冲区原理 ）,
在操作系统空间设置一组缓冲区,当发送进程需要发送消息时,执行 send系统调用,产生自愿性中断,进入操作系统,操作系统为发送进程分配一个空缓冲区,并将所发送的消息从发送进程 copy到缓冲区中,然后将该载有消息的缓冲区连接到接收进程的消息链链尾,如此就完成了发送过程 。 发送进程返回到用户态继续执行
2.4.2 消息缓冲
（ 有界缓冲区原理 ）,
在以后某个时刻,当接收进程执行到 receive接收原语时,也产生自愿性中断进入操作系统,
由操作系统将载有消息的缓冲区从消息链中取出,并把消息内容 copy到接收进程空间,之后收回缓冲区,如此就完成了消息的接收,接收进程返回到用户态继续进行
PCB
......
Send(R,M)
......
SIZE:消息长度
TEXT:消息正文
......
消息链指针
......
......
Receive(pid,N)
......
SIZE:消息长度
TEXT:消息正文
......
M,N:
接受进程 R发送进程 S
消息消息消息
......
消息缓冲区结构：
消息长度消息正文发送者消息队列指针用 P.V操作来实现 Send原语,
Send（ R,M） P(m-mutex);
Begin 把缓冲区挂到接收进程根据 R找接收进程,的消息链链尾 ;
如果没找到出错返回 ; V(m-mutex);
申请空缓冲区 P（ s-b） ； V(s-m);
P(b-mutex); END
摘空缓冲区 ;
V(b-mutex);
把消息从 M处 copy到空缓冲区 ;
其中 s-b初值,n ;s-m初值,0
管道通信方式 Pipe
也称共享文件方式,基于文件系统,
利用一个打开的共享文件连接两个相互通信的进程,文件作为缓冲传输介质发送进程 接收进程字符流方式写入读出先进先出顺序
2.5 进程调度（ CPU调用）
要解决的问题
WHAT：按什么原则分配 CPU— 进程调度算法
WHEN：何时分配 CPU— 进程调度的时机
HOW,如何分配 CPU— CPU调度过程
（ 进程的上下文切换 ）
何时切换进程?
只要 OS取得对 CPU的控制,进程切换就可能发生,如,当,
– 超级用户调用
来自程序的显式请求 (如：打开文件 ),该进程多半会被阻塞
– 陷阱
最末一条指令导致出错,会引起进程移至退出状态
– 中断
外部因素影响当前指令的执行,控制被转移至 IH
（ 中断处理程序 ）
中断的例子
– 时钟
进程用完其时间片,被转换至就绪状态
– I/O
先前等待该事件的进程被转换为就绪 (或就绪挂起 )状态
然后重新运行该进程或选择一更高优先级的进程
– 存储器因素
内存地址是在虚拟存储器中,它必须把对应的存储块调入主存
于是相应的进程成为阻塞状态 (等待 I/O完成 )
方式切换
在中断没有引起进程切换时,方式切换可能发生
控制可只返回给中断程序
然后只有处理器状态信息需要保存在栈中
这称为方式切换 (当进入 IH时,用户方式转到内核方式 )
较少过载：不需要象进程切换那样更新
PCB
在进程（上下文）中切换的步骤
保存处理器的上下文,包括程序计数器和其它寄存器
用新状态和其它相关信息更新正在运行进程的 PCB
把移至合适的队列 -就绪,阻塞
选择另一个要执行的进程
更新被选中进程的 PCB
从被选中进程中重装入 CPU 上下文
2.5.1 进程调度算法
1,进程调度进程调度的任务是控制协调进程对 CPU的竞争即按一定的调度算法从就绪队列中选中一个进程,把 CPU的使用权交给被选中的进程
2．确定算法的原则
具有公平性
资源利用率高 （ 特别是 CPU利用率 ）
在交互式系统情况下要追求响应时间
（ 越短越好 ）
在批处理系统情况下要追求系统吞吐量
3．各种进程调度算法先进先出进程调度算法 （ FIFO）
按照进程就绪的先后次序来调度进程优点,实现简单缺点,没考虑进程的优先级基于优先数的调度
（ HPF— Highest Priority First）
优先选择就绪队列中优先级最高的进程投入运行优先级根据优先数来决定确定优先数的方法静态优先数法：
在进程创建时指定优先数,在进程运行时优先数不变动态优先数法：
在进程创建时创立一个优先数,但在其生命周期内优先数可以动态变化 。 如等待时间长优先数可改变两种占用 CPU的方式可剥夺式 （ 可抢占式 Preemptive）,
当有比正在运行的进程优先级更高的进程就绪时,系统可强行剥夺正在运行进程的 CPU，
提供给具有更高优先级的进程使用不可剥夺式 （ 不可抢占式 Nonpreemptive ）,
某一进程被调度运行后,除非由于它自身的原因不能运行,否则一直运行下去时间片轮转程序调度算法
(RR— Round Robin)
把 CPU划分成若干时间片,并且按顺序赋给就绪队列中的每一个进程,进程轮流占有 CPU,当时间片用完时,即使进程未执行完毕,系统也剥夺该进程的 CPU,将该进程排在就绪队列末尾 。 同时系统选择另一个进程运行分时系统中常用时间片轮转法时间片选择问题：
固定时间片可变时间片与时间片大小有关的因素：
系统响应时间就绪进程个数
CPU能力多队列反馈调度算法：
将就绪队列分为 N级,每个就绪队列分配给不同的时间片,队列级别越高,时间越长,级别越小,时间片越小,最后一级采用时间片轮转,其他队列采用先进先出； 系统从第一级调度,当第一级为空时,系统转向第二个队列,,....当运行进程用完一个时间片,放弃 CPU时,进入下一级队列；等待进程被唤醒时,进入原来的就绪队列；当进程第一次就绪时,进入第一级队列
* 首先系统中设置多个就绪队列
* 每个就绪队列分配给不同时间片,优先级高的为第一级队列,时间片最小,随着队列级别的降低,时间片加大
* 各个队列按照先进先出调度算法
* 一个新进程就绪后进入第一级队列
* 进程由于等待而放弃 CPU后,进入等待队列,一旦等待的事件发生,则回到原来的就绪队列
* 当有一个优先级更高的进程就绪时,可以抢占 CPU,被抢占进程回到原来一级就绪队列末尾
* 当第一级队列空时,就去调度第二级队列,如此类推
* 当时间片到后,进程放弃 CPU,回到下一级队列
2.5.2 进程调度的时机当一个进程运行完毕，或由于某种错误而终止运行当一个进程在运行中处于等待状态（等待
I/O）
分时系统中时间片到
2.5.2 进程调度的时机当有一个优先级更高的进程就绪 （ 可抢占式 ）,例如：新创建一个进程,一个等待进程变成就绪在进程通信中,执行中的进程执行了某种原语操作 （ P操作,阻塞原语,唤醒原语 ）
2.5.3 CPU调度过程
* 保存现场：顺序保存,最后一步保存 PSW
* 选择要运行的程序
（ 如果没有就绪进程,系统会安排一个闲逛进程 (idle),没有其他进程时该进程一直运行,在执行过程中可接收中断 ）
* 恢复现场：最后一步恢复选中进程的 PSW
2.6 系统核心系统核心：
向上提供多个无中断的虚拟机器在核心内不允许中断特点,* 为进程运行提供一个舞台
* 核心常驻内存
* 设计短小精焊
2.6.1 核心的组成中断处理进程管理,
调度 控制 通讯 互斥 同步等原语管理,
在核心中提供一系列原语,同步,通信,创建,撤消等队列管理,
队列数据结构,指向队首的表指针三个队列,运行,就绪,等待队列排队方式,排队首排队尾插 队出队方式,队首出队 /队中出队队列管理,中断之后,进程调度之前现场管理,
保存现场 ;注意顺序,中断之后第一步恢复现场,恢复时机,进程调度最后一步时钟管理,
以固定频率 +1 -1
用途,进入绝对时钟间隔时钟进行分析比较虚时钟,
每个进程分配给一个虚时钟来记录 CPU时间,这个时钟称为虚时钟虚时钟存放在 PCB中,属于现场的一部分,
进程运行时,将虚时钟放入内存开辟的专门单元,离开 CPU则放在 PCB中
2.6.2 核心处理流程进入核心的唯一入口,中断中断后进入核心,由硬件完成
2.6.3 内核的执行特点由中断驱动的,中断 → 内核 → 退出内核执行是连续的内核执行过程中在中断屏蔽状态下内核使用特权指令
2.7 死锁死锁的基本概念死锁的解决方案
（ 预防,避免,检测及解除 ）
资源分配图死锁的现象
2.7.1 死锁的基本概念死锁的定义,
一组进程中,每个进程都无限等待被该组进程中另一进程所占有的资源,因而永远无法得到的资源,这种现象称为进程死锁,这一组进程就称为死锁进程
2.7.1 死锁的基本概念死锁 （ Deadlock）
饥饿 （ Starvation）
关于死锁的一些结论：
参与死锁的进程最少是两个
（ 两个以上进程才会出现死锁 ）
参与死锁的进程至少有两个已经占有资源参与死锁的所有进程都在等待资源参与死锁的进程是当前系统中所有进程的子集注：
如果死锁发生,会浪费大量系统资源,
甚至导致系统崩溃
2.7.1 死锁的基本概念资源永久性资源,可以被多个进程多次使用
（ 可再用资源 ）
* 可抢占资源
* 不可抢占资源
2.7.1 死锁的基本概念资源临时性资源,只可使用一次的资源；如信号量,中断信号,同步信号等 （ 可消耗性资源 ）
,申请 --分配 --使用 --释放,模式
2.7.1 死锁的基本概念产生死锁的四个必要条件：
互斥使用 （ 资源独占 ）
不可强占 （ 不可剥夺 ）
请求和保持 （ 部分分配,占有申请 ）
循环等待
1) 互斥使用（资源独占）：
一个资源每次只能给一个进程使用
2) 不可强占（不可剥夺）：
资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放
3) 请求和保持：
（部分分配，占有申请）
一个进程在申请新的资源的同时保持对原有资源的占有 。
（ 只有这样才是动态申请,动态分配 ）
4) 循环等待：
存在一个进程等待队列
{P1,P2,…,Pn},
其中 P1等待 P2占有的资源,P2等待 P3占有的资源,…,Pn等待 P1占有的资源,
形成一个进程等待环路
2.7.2 死锁的解决方案
1,产生死锁的例子申请不同类型资源产生死锁
P1：
…
申请打印机申请扫描仪使用释放打印机释放扫描仪
…
P2：
…
申请扫描仪申请打印机使用释放打印机释放扫描仪
…
申请同类资源产生死锁 （如内存）
设有资源 R,R有 m个分配单位,由 n个进程 P1,P2,…,Pn（ n > m） 共享 。 假设每个进程对 R的申请和释放符合下列原则：
* 一次只能申请一个单位
* 满足总申请后才能使用
* 使用完后一次性释放申请同类资源产生死锁 （如内存）
m=2,n=3
资源分配不当导致死锁产生
2,解决死锁的方法不让死锁发生,
静态策略：设计合适的资源分配算法,
不让死锁发生动态策略：
让死锁发生,
2.7.3 死锁预防定义：
在系统设计时确定资源分配算法,保证不发生死锁 。 具体的做法是破坏产生死锁的四个必要条件之一
2.7.3 死锁预防破坏,不可剥夺,条件在允许进程动态申请资源前提下规定,
一个进程在申请新的资源不能立即得到满足而变为等待状态之前,必须释放已占有的全部资源,若需要再重新申请
2.7.3 死锁预防破坏,请求和保持,条件要求每个进程在运行前必须一次性申请它所要求的所有资源,且仅当该进程所要资源均可满足时才给予一次性分配
2.7.3 死锁预防破坏,循环等待,条件采用 资源有序分配法,
把系统中所有资源编号,进程在申请资源时必须严格按资源编号的递增次序进行,否则操作系统不予分配
2.7.3 死锁预防例如,1,2,3,…,10
P1：
申请 1
申请 3
申请 9
…
P2：
申请 1
申请 2
申请 5
…
P3 …… P10
2.7.4 死锁避免
A申请
B申请释放 A
释放 B
获得 A
获得 B
Q进程
P 和 Q
申请 A
死锁不可避免
P 和 Q
申请 B
P进程获得 A 获得 B 释放 A 释放 B
B申请
A申请
Q进程释放 A
释放 B
获得 A
获得 B
A申请
B申请
P 和 Q
申请 A
P 和 Q
申请 B
P进程获得 A 释放 A 获得 B 释放 B
A申请 B申请
2.7.4 死锁避免定义：
在系统运行过程中,对进程发出的每一个系统能够满足的资源申请进行动态检查,并根据检查结果决定是否分配资源,若分配后系统可能发生死锁,则不予分配,否则予以分配
2.7.4 死锁避免安全状态与不安全状态安全状态：
如果存在一个由系统中所有进程构成的安全序列 P1,… Pn，则系统处于安全状态
2.7.4 死锁避免安全序列：
一个进程序列 {P1,…,Pn}是安全的，如果对于每一个进程
Pi(1≤ i≤ n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程 Pj (j < i )当前占有资源量之和，系统处于安全状态。
(安全状态一定是没有死锁发生的 )
安全状态与不安全状态不安全状态,不存在一个安全序列,不安全状态一定导致死锁银行家算法
n：系统中进程的总数
m：资源类总数
Available:
ARRAY[1..m] of integer;
Max:
ARRAY[1..n,1..m] of integer;
银行家算法
Allocation:
ARRAY[1..n,1..m] of integer;
Need:
ARRAY[1..n,1..m] of integer;
Request:
ARRAY[1..n,1..m] of integer;
银行家算法简记符号：
Available
Max[i]
Allocation[i]
Need[i]
Request[i]
银行家算法当进程 pi提出资源申请时,系统执行下列步骤：
（ 1 ） 若 Request[i]≤Need[i],转
（ 2） ；
否则错误返回
（ 2） 若 Request[i]≤Available,
转 （ 3） ；否则进程等待
(3） 假设系统分配了资源,则有：
Available:=Available-Request[i];
Allocation[i]:=
Allocation[i]+Request[i];
Need[i]:=Need[i]-Request[i]
若系统新状态是安全的,则分配完成若系统新状态是不安全的,则恢复原状态,进程等待银行家算法为进行安全性检查,定义数据结构：
Work:ARRAY[1..m] of integer;
Finish:ARRAY[1..n] of Boolean;
银行家算法安全性检查的步骤：
(1) Work:=Available;
Finish:=false;
(2) 寻找满足条件的 i：
a.Finish[i]=false;
b.Need[i]≤Work ;
如果不存在,则转 (4)
银行家算法
(3) Work:=Work+Allocation[i];
Finish[i]:=true;
转 (1)
(4) 若对所有 i,Finish[i]=true,则系统处于安全状态,否则处于不安全状态银行家算法目前占有量 最大需求量 尚需要量
P1 1 4 3
P2 4 6 2
P3 5 8 3
系统剩余量 2
死锁检测：
允许死锁发生,操作系统不断监视系统进展情况,判断死锁是否发生一旦死锁发生则采取专门的措施,
解除死锁并以最小的代价恢复操作系统运行
2.7.5 死锁的检测与解除
2.7.5 死锁的检测与解除检测时机：
当进程等待时检测死锁
（ 其缺点是系统的开销大 ）
定时检测系统资源利用率下降时检测死锁
2.7.5 死锁的检测与解除死锁检测算法
* 每个进程和资源指定唯一编号
* 设置一张资源分配表记录各进程与其占用资源之间的关系
* 设置一张进程等待表记录各进程与要申请资源之间的关系
2.7.5 死锁的检测与解除死锁检测算法资源分配表 进程等待表
r1 p2 p1 r1
r2 p5 p2 r3
r3 p4 p4 r4
r4 p1
… … … …
死锁的解除：
重要的是以最小的代价恢复系统的运行 。 方法如下：
1） 重新启动
2） 撤消进程
3） 剥夺资源
4） 进程回退
2.7.6 资源分配图用有向图描述进程的死锁准确,形象系统由若干类资源构成,一类资源称为一个资源类；每个资源类中包含若干个同种资源,称为资源实例
2.7.6 资源分配图二元组 G=（ V,E）
V：结点集,分为 P,R两部分
P={p1,p2,…,pn}
R={r1,r2,…,rm}
E：边的集合,其元素为有序二元组
(pi,rj)或 (rj,pi)
2.7.6 资源分配图表示法资源类 （ 资源的不同类型 ）
用方框表示资源实例 （ 存在于每个资源中 ）
用方框中的黑圆点表示进程用圆圈中加进程名表示
2.7.6 资源分配图分配边：
资源实例?进程的一条有向边申请边：
进程?资源类的一条有向边有环有死锁有环无死锁
2.7.6 资源分配图死锁定理如果资源分配图中没有环路,则系统中没有死锁,如果图中存在环路则系统中可能存在死锁如果每个资源类中只包含一个资源实例,则环路是死锁存在的充分必要条件
2.7.6 资源分配图资源分配图化简：方法如下
1） 找一个非孤立点进程结点且只有分配边,去掉分配边,将其变为孤立结点
2） 再把相应的资源分配给一个等待该资源的进程,即将某进程的申请边变为分配边
【 作业,】
已分配的资源 最大需求量
A B C A B C
P10 1 0 7 5 3
P22 0 0 3 2 2
P33 0 2 9 0 2
P42 1 1 2 2 2
P50 0 2 4 3 3
剩余资源 A B C
3 3 2
问题,此状态是否为安全状态,如果是,则找出安全序列在此基础上
P2 申请 （ 1,0,2） 能否分配？ 为什么？
P5 申请 （ 3,3,0） 能否分配？ 为什么？
P1 申请 （ 0,2,0） 能否分配？ 为什么？
2.8 线程的基本概念线程的引入线程与进程的对比线程的实现线程的例子,Solaris
2.8.1 线程的引入进程的两个基本属性：
资源的拥有者：
给每个进程分配一虚拟地址空间,保存进程映像控制一些资源 （ 文件,I/O设备 ）
有状态,优先级,调度
2.8.1 线程的引入进程的两个基本属性：
调度单位：
进程是一个执行轨迹以上两个属性构成进程并发执行的基础
2.8.1 线程的引入系统必须完成的操作：
创建进程
撤消进程
进程切换缺点：时间空间开销大,限制并发度的提高
2.8.1 线程的引入线程,有时称轻量级进程进程中的一个实体是一个 CPU调度单位资源的拥有者还是进程或称任务将原来进程的两个属性分开处理
2.8.1 线程的引入线程：
有执行状态
不运行时保存上下文
有一个执行栈
有一些局部变量的静态存储
可存取所在进程的内存和其他资源
可以创建,撤消另一个线程线程和进程：
单进程,单线程单进程,多线程多进程,一个进程一个线程多进程,一个进程多个线程
P C B 用户栈单 线程进程模型用户地址空间核心栈线程控制块：
包含了寄存器映像，线程优先数和线程状态信息。
P C B
多线程进程模型用户地址空间用户栈核心栈线程控制块用户栈核心栈线程控制块用户栈核心栈线程控制块引入线程的好处：
两个线程的切换花费时间少
创建一个新线程花费时间少 （ 结束亦如此 ）
因为同一进程内的线程共享内存和文件,
因此它们之间相互通信无须调用内核例子 1：
因此有效的方法是：为每一个请求创建一个线程
LAN中的一个文件服务器,在一段时间内需要处理几个文件请求在一个 SMP机器上：多个线程可以同时在不同的处理器上运行例子 2：
一个线程显示菜单,并读入用户输入；
另一个线程执行用户命令考虑一个应用：由几个独立部分组成,这几个部分不需要顺序执行,则每个部分可以以线程方式实现当一个线程因 I/O阻塞时,可以切换到同一应用的另一个线程引入线程的好处：
两个线程的切换花费时间少
创建一个新线程花费时间少 （ 结束亦如此 ）
因为同一进程内的线程共享内存和文件,
因此它们之间相互通信无须调用内核
2.8.2 线程与进程的比较
调度
并发性
拥有资源
系统开销
2.8.3 线程的实现机制
用户级线程
核心级线程
两者结合方法用户级线程（ ULT）：
核心不知道线程的存在
由应用程序完成所有线程的管理通过线程库
线程切换不需要核心态特权
调度是应用特定的线程库：
在线程之间传递消息和数据
创建,撤消进程
调度线程执行
保护和恢复线程上下文对用户级线程的核心活动：
当线程调用系统调用时,整个进程阻塞
核心不知道线程的活动,但仍然管理线程的进程的活动
但对线程库来说,线程仍然是运行状态即线程状态是与进程状态独立的用户级线程的优点和缺点：
调度是应用程序特定的：可以选择最好的算法优点：
线程切换不调用核心
ULT可运行在任何操作系统上 （ 只需要线程库用户级线程的优点和缺点：
大多数系统调用是阻塞的,因此核心阻塞进程,故进程中所有线程将被阻塞缺点：
核心只将处理器分配给进程,同一进程中的两个线程不能同时运行于两个处理器上核心级线程（ KLT）：
没有线程库,但对核心线程工具提供 API
所有线程管理由核心完成
核心维护进程和线程的上下文
线程之间的切换需要核心支持
以线程为基础进行调度
例子,Windows NT,OS/2
核心级线程的优点和缺点：
阻塞是在线程一级完成优点：
对多处理器,核心可以同时调度同一进程的多个线程
核心例程是多线程的核心级线程的优点和缺点：
在同一进程内的线程切换调用内核,导致速度下降缺点：
两者分析：
系统调用
线程的调度和切换速度
线程执行时间
ULT和 KLT结合方法：
大量线程调度和同步在用户空间完成
线程创建在用户空间完成
程序员可以调整 KLT的数量
可以取两者中最好的
例子,Solaris
2.8.4 实例,Solaris
进程：
用户地址空间
用户栈
进程控制块
2.8.4 实例,Solaris
用户级线程 （ 线程库 ）,
可在应用进程中建立多个 ULT
每个 ULT需要：栈,程序计数器不受调度程序的调度,线程切换快对操作系统不可见提供应用程序并行性接口
2.8.4 实例,Solaris
核心级线程,
设置了大量 KLT
有一个小的数据结构和栈完成内核的所有工作调度处理器的单位,其结构由核心维护
2.8.4 实例,Solaris
轻型进程 （ LWP）,
每个 ULT利用 LWP与内核通信每个 LWP支持一个或多个用户级线程,并映射到一个核心级线程每个 LWP对应用程序可见,内核看到的是多个 LWP而看不到 ULT
Solaris：多功能性
如果逻辑并行性不需要硬件并行性的支持,则可使用 ULT
例子：多个窗口,任一时刻只有一个窗口是活跃的
如果线程可以被阻塞,则可以指定两个或多个 LWP,避免整个应用程序的阻塞
Solaris：
如果逻辑并行性不需要硬件并行性的支持,则可使用 ULT
例子：多个窗口,任一时刻只有一个窗口是活跃的
如果内核级线程可能被阻塞,则可以指定两个或多个 LWP,避免整个应用程序的阻塞分派唤醒继续抢占停止可运行睡眠睡眠停止停止停止用户级线程活跃连接在 LWP上分派 唤醒继续时间片或抢占停止运行阻塞系统调用停止停止轻型进程状态
LWP状态独立于状态 ULT
（受限制 ULT除外）
可运行阻塞唤醒进程 1 进程 2 进程 3 进程 4 进程 5
进程库用户内核硬件用户级进程 内核级进程 轻型线程 处理器
多道程序设计
进程
进程间的相互作用
进程间的通信
进程调度（ CPU调度）
死锁
线程
2.1 多道程序设计
顺序程序
并发程序
多道程序设计
2.1.1 顺序程序程序：
指令或语句序列,体现了某种算法,所有程序是顺序的顺序环境：
在计算机系统中只有一个程序在运行,这个程序独占系统中所有资源,其执行不受外界影响特征：
程序执行的顺序性
程序执行的封闭性独占资源,执行过程中不受外界影响
程序结果的可再现性程序运行结果与程序执行速度无关,
只要初始状态相同,结果应相同
2.1.2 并发程序并发环境：
在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态,并且次序不是事先确定的
A
B
A
B
B
A
A
B
特征：
（ 1） 程序结果的不可再现性并发程序执行的结果与其执行的相对速度有关,是不确定的
（ 2） 在并发环境下程序的执行是间断性的执行 —— 停 —— 执行
（ 3）资源共享系统中资源被多个进程使用
（ 4）独立性和制约性独立的相对速度、起始时间进程之间可相互作用（相互制约）
可分为直接作用和间接作用
（ 5）程序和计算不再一一对应
（计算：一个程序的执行）
2.1.2 并发程序引入并发的目的：
引入并发是为了提高资源利用率,从而提高系统效率 。
并发与并行概念的区别：
concurrency,parallel
在顺序环境下
CPU利用率 = 40/80 = 50%
DEV1利用率 = 18.75%
DEV2利用率 = 31.25%
C PU D E V 1 D E V 2 C PUC PU
A
10 15 20 30 40
t(s )
D E V 2C PUD E V 2 D E V 1 C PU
B
10 20 30 40
t(s )
25
例：
例：
在并发环境下 CPU利用 = 89%
DEV1并发环境下利用 = 33%
DEV2并发环境下利用 = 66%
0 1 0 2 0 3 0 3 5 4 5
CP U DEV 1 - - - C P U D EV 2 C P U
DEV 1 CP U DEV 2 CP U - - - - DEV 2
T ( s )
2.1.3 多道程序设计定义,Multiprogramming
多道程序设计是指允许多个程序同时进入内存并运行
（ 引入目的是为了提高系统效率 ）
与并发不完全是一个概念,但效果相似考虑因素：
在多道程序环境下如何向用户提供服务
在并发程序之间如何正确传递消息 （ 通讯 ）
如何对 CPU进行调度,保证每个用户相对公平地得到 CPU
（ CPU是一个只可调度,不可分配的资源 ）
如何管理其他资源当各用户对资源使用上发生冲突时,如何处理竞争对 CPU只能通过调度来解决竞争问题,而对于其他资源通过申请 — 分配 — 使用 — 回收的办法进行管理,当且仅当占有 CPU的时候才可以申请,否则要排队等候
2.1.4 与时间有关的错误一个飞机订票系统,两个终端,运行 T1,T2进程
T1,T2:
...,..
Read(x); Read(x);
if x>=1 then if x>=1 then
x:=x-1; x:=x-1;
write(x); write(x);
...,..
Cobegin
get;
copy;
put;
Coend
get copy put
f s t g
复制一个记录
f s t g
初始状态 3,4,...,m 2 2 (1,2)
g,c,p 4,5,...,m 3 3 (1,2,3)?
g,p,c 4,5,...,m 3 3 (1,2,2)?
c,g,p 4,5,...,m 3 2 (1,2,2)?
c,p,g 4,5,...,m 3 2 (1,2,2)?
p,c,g 4,5,...,m 3 2 (1,2,2)?
p,g,c 4,5,...,m 3 3 (1,2,2)?
设信息长度为 m,有多少种可能性？
c pc
g
p
c
g
p
g
并行环境下程序间的制约关系
2.2 进程
进程的概念
进程的状态及其转换
进程控制块 （ Process Control Block）
进程的特征
OS 对进程的要求
OS 必须交替执行多个进程,以便最大程度的使用 CPU,同时提供合理的响应时间
OS 必须将资源分配给进程,同时避免死锁
OS必须支持进程间通信以及用户进程创建
2.2.1 进程的概念定义,Process
进程是具有独立功能的程序关于某个数据集合上的一次运行活动,是系统进行资源分配和调度的独立单位进程何时创建?
提交一个批处理作业
用户登录
由 OS创建,用以向一用户提供服务 ( 如：打印文件 )
由已存在的一进程创建
– 一个用户程序可创建多个进程
批处理作业发出暂停 （ Halt） 指令
用户退出登录
进程执行一中止服务请求
出错及失败因素进程何时中止?
进程中止的原因
正常结束
给定时限到
缺少内存
存储器出界
保护性出错
– 例子,写只读文件
算术错
超出时间
– 进程等待超过对某事件的最大值进程中止的原因
I/O 失败
无效指令
– 如试图执行数据
特权指令
操作系统干预
– 如当死锁发生时
父进程请求中止某一子进程
父进程中止,所以子进程也中止程序与进程之间的区别：
进程更能真实地描述并发,而程序不能
进程是由程序和数据两部分组成的
程序是动态的,进程是动态的
进程有生命周期,有诞生有消亡,短暂的；
而程序是相对长久的
一个程序可对应多个进程,反之亦然
进程具有创建其他进程的功能,而程序没有进程的分类：
系统进程
用户进程
（ 系统进程优先于用户进程 ）
2.2.2 进程的基本状态及其转换进程的三种基本状态：
进程在生命消亡前处于且仅处于三种基本状态之一不同系统设置的进程状态数目不同
运行态 （ Running）,
进程占有 CPU,并在 CPU上运行
就绪态 （ Ready）,
一个进程已经具备运行条件,但由于无 CPU暂时不能运行的状态 （ 当调度给其 CPU时,立即可以运行 ）
等待态 （ Blocked）,阻塞态,挂起态,封锁态冻结态,睡眠态指进程因等待某种事件的发生而暂时不能运行的状态
（ 即使 CPU空闲,该进程也不可运行 ）
运行就绪 等待进程的状态及其转换
进程状态转换：
在进程运行过程中,由于进程自身进展情况及外界环境的变化,这三种基本状态可以依据一定的条件相互转换
就绪 — 运行
运行 — 就绪
运行 — 等待
等待 — 就绪进程转换
就绪 --> 运行
– 时间一到,调度程序选择一个新的进程运行
运行 --> 就绪
– 运行进程用完了时间片
– 运行进程被中断,因为一高优先级进程处于就绪状态
运行 --> 阻塞
– 当一进程所需的东西必须等待时
OS尚未完成服务
对一资源的访问尚不能进行
初始化 I/O 且必须等待结果
等待某一进程提供输入 (IPC)
阻塞 --> 运行
– 当所等待的事件发生时进程转换其他状态：
创建状态,终止状态
挂起状态
（ 调节负载,对换,父进程,操作系统,终端用户 ）
创建 (新 new)状态
– OS 已完成为创建一进程所必要的工作
已构造了进程标识符
已创建了管理进程所需的表格
– 但还没有允许执行该进程 (尚未同意 )
因为资源有限
终止 （ 退出 exit)状态
– 中止后进程移入该状态
– 它不再有执行资格
– 表格和其它信息暂时由辅助程序保留
例子,为处理用户帐单而累计资源使用情况的财务程序
当数据不再需要后,进程 (和它的表格 )被删除五状态进程模型准备退出：父进程可中止子进程新状态转换 (中期调度 )
阻塞 -->阻塞挂起
– 当所有进程都阻塞,OS会安排空间让一就绪进程进入内存
阻塞挂起 --> 就绪挂起
– 当等待的事件发生时 (状态信息已在 OS中 )
就绪挂起 -->就绪
– 当内存中没有就绪进程时
就绪 -->就绪挂起 (较少见 )
– 当没有被阻塞的进程,而为了性能上的考虑,
必须释放一些内存时七状态进程模型活动挂起事件发生事件发生 等待事件挂起调度超时释放活动挂起
2.2.3 进程控制块
（ Process Control Block）
概念：
系统为了管理进程设置的一个专门的数据结构,用它来记录进程的外部特征,描述进程的运动变化过程系统利用 PCB来控制和管理进程,所以 PCB
是系统感知进程存在的唯一标志进程与 PCB是一一对应的进程映象 (进程要素 )
用户程序
用户数据
栈
– 用于过程调用和参数传递
进程控制块 PCB (执行上下文 )
– 控制进程所需的数据 (进程属性 ),包括,
进程标识符信息
处理器状态信息
进程控制信息
PCB的内容：
调度信息：
进程名；进程的内部标识；用户名；进程状态；进程优先级；进程的存储信息 （ 起始地址,长度 ） ；进程资源清单；进程家族关系；进程的队列指针；进程的消息队列指针；进程当前打开的文件 …,..
现场信息：
记录了重要的寄存器； (虚 )时钟等内容进程标识符 (在 PCB中 )
可使用一些数字标识符
– 统一进程标识符 (必然的 )
索引至 (直接或间接 ) 主进程表
– 用户标识符
与某个作业对应的用户
– 创建本进程的某个进程的标识符处理器状态信息 (在 PCB中 )
处理器寄存器内容
– 用户可见寄存器
– 控制和状态寄存器
– 栈指针
程序状态字 (PSW)
– 包含状态信息
– 例子,在 Pentium机中的 EFLAGS寄存器进程控制信息 (在 PCB中 )
调度和状态信息
– 进程状态 (如,运行,就绪,阻塞,..)
– 进程优先级
– 该进程在等待的事件 (若被阻塞 )
数据结构信息
– 进程可能需要有指向其他 PCB的指针,父 -子进程关系及其它结构
进程间通信
– IPC可能需要标志和信号
进程特权
– 如,访问特定的内存地址,..
存储管理
– 指向赋予该进程的段 /页表的指针
所拥有的资源和使用情况
– 使用中的资源,打开的文件,I/O设备,..
– (CPU,I/O...)的时间使用史进程控制信息 (在 PCB中 )
执行的方式
为了提供对 PCB (和 OS其它数据 )的保护,
多数处理器支持至少两种执行方式,
– 特权方式 (又称作系统方式,内核方式,管理方式,控制方式 )
操作控制寄存器,基本 I/O指令,存储管理,..
– 用户方式
为此,CPU提供一个 (或一些 )方式位,
这些二进制位只能被中断,陷阱或 OS调用所设置
PCB表：
系统把所有 PCB组织在一起,并把它们放在内存的固定区域,就构成了 PCB表
PCB表的大小决定了系统中最多可同时存在的进程个数,称为系统的并发度
（ 注：多道程序中的多道与系统并发度不同 ）
进程控制块 （ Process Control Block）
PC B 1
PC B 2
PC B 3
PC B 4
PC B 5
PC B 6
PC B 7
PC B n
......
空 PCB
运行态就绪态等待 1
等待 2
6
7
5
10
15
PCB表组织方式：
常用索引方式,对具有相同状态的进程,
分别设置各自的 PCB索引表,表明 PCB在
PCB表中的地址
（ 其他方式：线性表或链表 ）
进程队列：不同状态进程分别组成队列运行队列,就绪队列,等待队列
2.2.4 进程控制创建,撤消进程以及完成进程各状态之间的转换 。 由具有特定功能的原语完成 。
进程创建原语进程撤消原语阻塞原语唤醒原语挂起原语激活 （ 解挂 ） 原语进程的创建
创建一个 PCB
赋予一个统一进程标识符
为进程映象分配空间
初始化进程控制块
– 许多默认值 (如,状态为 New,无 I/O设备或文件,..)
设置相应的链接
– 如,把新进程加到就绪队列的链表中进程撤消收回进程所占有的资源撤消该进程的 PCB
进程阻塞处于运行状态的进程,在其运行过程中期待某一事件发生,如等待键盘输入,
等待磁盘数据传输完成,等待其它进程发送消息,当被等待的事件未发生时,
由进程自己执行阻塞原语,使自己由运行态变为阻塞态进程唤醒
2.2.5 进程的特征
并发性任何进程都可以同其他进程一起向前推进
动态性进程对应程序的执行进程是动态产生,动态消亡的进程在其生命周期内,在三种基本状态之间转换
独立性进程是 CPU调度的一个独立单位
交互性指进程在执行过程中可能与其它进程产生直接或间接的关系
异步性每个进程都与其相对独立的不可预知的速度向前推进
结构性：
进程的组成：程序 +数据 +PCB
可再入程序：
可被多个进程同时调用的程序,具有下列性质：
它是纯代码的,即在执行过程中自身不改变,调用它的进程应该提供数据区
【 思考题 】,
1,如果系统中有 N个进程,运行的进程最多几个,
最少几个；就绪进程最多几个最少几个；等待进程最多几个,最少几个？
2,有没有这样的状态转换,为什么？
等待 — 运行； 就绪 — 等待
3,一个状态转换的发生,是否一定导致另一个转换发生,列出所有的可能
4,举 3个日常生活中类似进程的例子
2.3 进程间的相互作用
进程间的联系
进程的同步机制 ── 信号量及 P.V操作
（ 解决进程同步互斥问题 ）
2.3.1 进程间的联系相交进程与无关进程相交进程：指多个并发进程在逻辑上有某种联系无关进程 （ 不相交进程 ）,在逻辑上无任何联系的进程直接作用和间接作用直接作用：
进程间的相互联系是有意识的安排的,
直接作用只发生在相交进程间间接作用：
进程间要通过某种中介发生联系,是无意识安排的,可发生在相交进程之间,
也可发生在无关进程之间进程的同步（直接作用）
进程的同步,synchronism
指系统中一些进程需要相互合作,共同完成一项任务 。 具体说,一个进程运行到某一点时要求另一伙伴进程为它提供消息,在未获得消息之前,该进程处于等待状态,获得消息后被唤醒进入就绪态例,
司机 P1 售票员 P2
REPEAT REPEAT
启动 关门正常运行 售票到站停 开门
UNTIL FALSE UNTIL FALSE
进 程 的 互 斥 （ 间 接 作 用 ） mutual
exclusion
由于各进程要求共享资源,而有些资源需要互斥使用,因此各进程间竞争使用这些资源,进程的这种关系为进程的互斥临界资源,critical resource
系统中某些资源一次只允许一个进程使用,
称这样的资源为临界资源或互斥资源或共享变量临界区 （ 互斥区 ）,critical section
一个程序片段的集合,这些程序片段分散在不同的进程中,对某个共享的数据结构 （ 共享资源 ） 进行操作在进程中涉及到临界资源的程序段叫临界区
a,= a -1
print (a)
a,= a +1
print (a)
P1
互斥
P2
互斥
If a < 0
then
a,= a +1
else
a:= a-1
P3
互斥 进程的互斥（间接作用）
程序 段 1 程序 段 2 程序 段 n
共 享 变量进程的互斥（间接作用）
使用互斥区的原则：
有空让进,当无进程在互斥区时,任何有权使用互斥区的进程可进入无空等待,不允许两个以上的进程同时进入互斥区有限等待,任何进入互斥区的要求应在有限的时间内得到满足使用互斥区的原则：
前提：任何进程无权停止其它进程的运行进程之间相对运行速度无硬性规定解决方法：
硬件 （ 当一个进程进入临界区,就屏蔽所有中断,但成本高 ）
软件 （ 用编程解决,但常常忙等待 ）
软件解法 (1)
free,表示临界状态
true,无进程在临界区 (初值 )
false:有进程在临界区
....
L,if free then
begin
free:=false;
‘进入临界区 ’
end
else goto L;
free:=true
软件解法 (2)
turn,true P进入临界区
false Q 进 入 临 界 区
....
P,repeat until turn;
‘进入临界区 ’
turn:=flase;
Q,repeat until not turn;
‘ 进 入 临 界 区 ’
turn:=true;
软件解法,(3)
pturn,qturn,初值为 false
P进入临界区的条件,pturn∧ not qturn
Q进入临界区的条件,not pturn∧ qturn
P,..,Q,....
pturn:=true; qturn:=ture;
repeat until not qturn; repeat until not pturn
‘进入临界区 ’ ‘ 进入临界区 ’
pturn:=false; qturn:=false
...,..
软件解法 (4) Dekker算法,
在解法 (3)基础上引入 turn枚举类型 初值任意
P,Repeat
pturn:=true;
while qturn do
if turn=2 then begin
pturn:=false;
while turn=2 do；； pturn:=true
end;
'进入临界区 '
turn:=2;
pturn:=false;
.....
Until false
(4) Dekker算法,
Q,Repeat
qturn:=true;
while pturn do
if turn=1 then begin
qturn:=false;
while turn=1 do
qturn:=true
end;
' 进 入 临 界 区 '
turn:=1;
qturn:=false;
.....
Until false
软件解法的缺点：
1,忙等待
2,实现过于复杂,需要高的编程技巧硬件解法 (1)
,测试并建立”指令
Function Test_and_Set
(var target:boolean):boolean
begin
Test_and_Set:=target;
target:=true
end
硬件解法 (1)
Var lock:boolean;
进入临界区前执行：
While Test_and_Set(lock) do
skip;
离开临界区后执行：
lock:=false;
硬件解法 (2)
,交换”指令
Function Swap(var a,b:boolean)
Var temp:boolean;
begin
temp:=a;
a:=b;
b:=temp
end
每一组共享变量定义一个全局变量
Var lock:boolean;
每个进程定义一个局部变量
Var key:boolean;
进入临界区前执行：
key:=true;
repeat
swap(lock,key);
until key=false;
离开临界区后执行,lock:=false;
硬件解法 (3)
,开关中断”指令进入临界区前执行：
执行,关中断,指令离开临界区后执行：
执行,开中断,指令
2.3.2 进程的同步机制 ──
信号量及 P.V操作（解决进程同步）
同步机制：
信号量及 P,V操作；管程；条件临界域；路径表达式等 （ 用于集中式系统中 ）
会合；通信顺序进程；分布进程；远程过程调用等 （ 适用于分布式系统中 ）
同步机制应满足的基本要求：
* 描述能力
* 可以实现
* 效率高
* 使用方便信号量,semaphore
是一个数据结构,定义如下：
TYPE semaphore= RECORD
Value,integer
Queue,Pointer_PCB
END
信号量说明：
VAR,S,semaphore
P.V操作
P操作
P(s),
s,Value,= s,Value - 1;
IF s,Value < 0 then
将该进程状态置为等待状态然后将该进程的 PCB插入相应的等待队列末尾
P.V操作
V操作
V(s),
s,Value,= s,Value + 1;
IF s,Value < = 0 then
唤醒相应等待队列中等待的一个进程改变其状态为就绪态并将其插入就绪队列
P,V操作为原语操作原语,primitive or atomic action
是由若干多机器指令构成的完成某种特定功能的一段程序,具有不可分割性即原语的执行必须是连续的,在执行过程中不允许被中断实现：开关中断信号量的使用,
必须置一次且只能置一次初值初值不能为负数只能执行 P,V操作用 P.V操作解决进程间互斥问题
P(S)
V(S)
P(S)
V(S)
P(S)
V(S)
P1 P2 P2
互斥区经典的生产者 ─ 消费者问题消费者生产者缓冲区经典的生产者 ─ 消费者问题同步问题：
P进程不能往,满,的缓冲区中放产品,设置信号量为 S1
Q进程不能从,空,的缓冲区中取产品,设置信号量 S2
P,Q：
Repeat Repeat
生产一个产品； P(s2);
送产品到缓冲区； 从缓冲区取产品 ；
V(s2); V(s1);
P(s1) 消费产品
Until false; Until false;
S1初值为 0,S2初值为 0
P：
Repeat
P(s1);
生产一个产品；
送产品到缓冲区 ；
V(s2)
Until false;
S1初值为 1,S2初值为 0
【 思考题 】 要不要对缓冲区 （ 临界资源 ）
进行互斥操作？
.....
.
P Q
放消息 取消息
n
n 个缓冲区
(Buffer)
i
j
P,
I:= 0
REPEAT
生 产 产 品 ；
P(S1)
往 Buffer [I] 中 放 产 品 ；
V(S2)
I:=(I+1) mod n
UNTIL false
Q：
J:= 0
REPEAT
P(S2)
从 Buffer[J]取产品；
V(S1)
消费产品
J:=(J+1) mod n
UNTIL false
P.V操作讨论
1) 信号量的物理含义：
S>0表示有 S个资源可用
S=0表示无资源可用
S<0则 | S |表示 S等待队列中的进程个数
P(S):表示申请一个资源
V(S)表示释放一个资源 。 信号量的初值应该大于等于 0
2) P.V操作必须成对出现,有一个 P操作就一定有一个 V操作当为互斥操作时,它们同处于同一进程当为同步操作时,则不在同一进程中出现如果 P(S1)和 P(S2)两个操作在一起,那么 P
操作的顺序至关重要,一个同步 P操作与一个互斥 P操作在一起时同步 P操作在互斥 P操作前而两个 V操作无关紧要
3） P.V操作的优缺点优点：
简单,而且表达能力强 （ 用 P.V操作可解决任何同步互斥问题 ）
缺点：
不够安全； P.V操作使用不当会出现死锁；
遇到复杂同步互斥问题时实现复杂
【 作业 】
1.用 P.V操作解决下图之同步问题,
get copy put
f s t g
2.用 P.V操作解决司机与售票员的问题司机进程：
REPEAT
启动车辆正常驾驶到站停车
UNTIL …
售票员进程：
REPEAT
关门售票开门
UNTIL …
2.3.3 IPC经典问题
1.读者写者问题有两组并发进程,
读者和写者,共享一组数据区要求：
允许多个读者同时执行读操作不允许读者,写者同时操作不允许多个写者同时操作第一类：读者优先如果读者来：
1） 无读者,写者,新读者可以读
2） 有写者等,但有其它读者正在读,则新读者也可以读
3） 有写者写,新读者等如果写者来：
1） 无读者,新写者可以写
2） 有读者,新写者等待
3） 有其它写者,新写者等待读者与写者问题读者,Repeat
P(mutex);
readcount:=readcount+1;
if readcount=1
then P (w);
V(mutex);
读
P(mutex);
readcount:=readcount-1;
if readcount=0
then V(w);
V(mutex);
Until false
写者：
Repeat
P(w);
写
V(w);
Until false
2.哲学家就餐问题有五个哲学家围坐在一圆桌旁,桌中央有一盘通心粉,每人面前有一只空盘子,每两人之间放一只筷子每个哲学家的行为是思考,感到饥饿,然后吃通心粉为了吃通心粉,每个哲学家必须拿到两只筷子,并且每个人只能直接从自己的左边或右边去取筷子
Repeat
思考；
取 fork[i];取 fork[(i+1) mod 5]；
进食；
放 fork[i];放 fork[(i+1) mod 5]；
Until false;
为防止死锁发生可采取的措施：
最多允许 4个哲学家同时坐在桌子周围
仅当一个哲学家左右两边的筷子都可用时,
才允许他拿筷子 （?）
给所有哲学家编号,奇数号的哲学家必须首先拿左边的筷子,偶数号的哲学家则反之为了避免死锁,把哲学家分为三种状态,思考,饥饿,进食,并且一次拿到两只筷子,
否则不拿
state:array[0..4] of
(思考,饥饿,进食 ） ；
ph,array[0..4] of semaphore;
mutex:semaphore;
i:0..4;
Procedure test(i:=0…4);
begin
if (state[ i ] = 饥饿 ) And
(state[(i-1)mod5]<>进食 ) And
(state[(i+1)mod5]<>进食 )
then begin
state[ i ]=进食
V(ph[ i ])
end
end
Procedure philosopher(i,0～ 4)
Begin
Repeat
思考 ；
state[i ]:=饥饿 ；
P(mutex);
test(i);
V(mutex);
P(ph[ i ]);
拿左筷子；
拿右筷子；
进食；
放左筷子；
放右筷子 ；
P(mutex)
state[ i ]:=思考；
test([i-1]mod5);
tset([i+1]mod5);
V(mutex);
until fales
End
state[ I ]=思考
ph[ I ]=0
mutex=1
【 作业 】
1,推广例子中的消息缓冲问题。
消息缓冲区为 k个，有 m个发送进程，
n个接收进程，每个接收进程对发送来的消息都必须取一次
2.第二类读者写者问题：
写者优先条件：
1） 多个读者可以同时进行读
2） 写者必须互斥 （ 只允许一个写者写,也不能读者写者同时进行 ）
3） 写者优先于读者 （ 一旦有写者,则后续读者必须等待,唤醒时优先考虑写者 ）
3.有一个系统,定义 P,V操作如下：
P(s):
s:=s-1;
if s<0 then
将本进程插入相应队列末尾等待；
V(s)：
s:=s+1;
if s<=0 then
从相应等待队列队尾唤醒一个进程,将其插入就绪队列；
问题：
1） 这样定义 P,V操作是否有问题？
2） 用这样的 P,V操作实现 N个进程竞争使用某一共享变量的互斥机制 。
3） 对于 2） 的解法,有无效率更高的方法 。
如有,试问降低了多少复杂性？
4.理发师睡觉问题理发店里有一位理发师,一把理发椅和 N
把供等候理发的顾客坐的椅子如果没有顾客,则理发师便在理发椅上睡觉 。 当一个顾客到来时,他必须先唤醒理发师如果顾客到来时理发师正在理发,则如果有空椅子,可坐下来等；否则离开
2.3.2 进程的同步机制 ── 管程管程的提出采用 PV同步机制来编写并发程序,对于共享变量及信号量变量的操作将被分散于各个进程中缺点：
（ １ ） 易读性差,因为要了解对于一组共享变量及信号量的操作是否正确,则必须通读整个系统或者并发程序
（ ２ ） 不利于修改和维护,因为程序的局部性很差,所以任一组变量或一段代码的修改都可能影响全局
（ ３ ） 正确性难以保证,因为操作系统或并发程序通常很大,要保证这样一个复杂的系统没有逻辑错误是很难的管程：一种同步机制
(管程 -类程 -进程 )
管程定义,
指关于共享资源的数据及在其上操作的一组过程或共享数据结构及其规定的所有操作系统按资源管理的观点分解成若干模块,用数据表示抽象系统资源,同时分析了共享资源和专用资源在管理上的差别,按不同的管理方式定义模块的类型和结构,使同步操作相对集中,从而增加了模块的相对独立性管程：集中式同步机制,它的基本思想是将共享变量以及对共享变量能够进行的所有操作集中在一个模块中,一个操作系统或并发程序由若干个这样的模块所构成,由于一个模块通常较短,模块之间关系清晰,提高了可读性,便于修改和维护,正确性易于保证管程的形式
TYPE monitor_name = MONITOR;
共享变量说明
define 本管程内所定义,本管程外可调用的过程 （ 函数 ） 名字表
use 本管程外所定义,本管程内将调用的过程 （ 函数 ） 名字表
PROCEDURE 过程名 （ 形参表 ） ；
过程局部变量说明；
BEGIN
语句序列；
END;
......
FUNCTION 函数名 （ 形参表 ）,值类型；
函数局部变量说明；
BEGIN
语句序列；
END;
......
BEGIN
共享变量初始化语句序列；
END;
管程的三个主要的特性：
（ 一 ） 模块化,一个管程是一个基本程序单位,可以单独编译
（ 二 ） 抽象数据类型,管程是一种特殊的数据类型,其中不仅有数据,而且有对数据进行操作的代码
（ 三 ） 信息掩蔽,管程是半透明的,
管程中的外部过程 （ 函数 ） 实现了某些功能,管程中的外部过程 （ 函数 ） 实现了某些功能,至于这些功能是怎样实现的,在其外部则是不可见的管程有如下几个要素：
（ 一 ） 管程中的共享变量在管程外部是不可见的,外部只能通过调用管程中所说明的外部过程
（ 函数 ） 来间接地访问管程中的共享变量
（ 二 ） 为了保证管程共享变量的数据完整性,规定管程互斥进入
（ 三 ） 管程通常是用来管理资源的,因而在管程中应当设有进程等待队以及相应的等待及唤醒操作问题：多个进程出现在管程中当一个进入管程的进程执行等待操作时,它应当释放管程的互斥权；
当一个进入管程的进程执行唤醒操作时 （ 如Ｐ唤醒Ｑ ）,管程中便存在两个同时处于活动状态的进程处理方法有三种：
Ｐ等待Ｑ继续,直到Ｑ退出或等待?
Ｑ等待Ｐ继续,直到Ｐ等待或退出
规定唤醒为管程中最后一个可执行的操作因为管程是互斥进入的,所以当一个进程试图进入一个巳被占用的管程时它应当在管程的入口处等待,因而在管程的入口处应当有一个进程等待队列,称作入口等待队列如果进程Ｐ唤醒进程Ｑ,则Ｐ等待
Ｑ继续,如果进程Ｑ在执行又唤醒进程Ｒ,则Ｑ等待Ｒ继续,……,如此,
在管程内部,由于执行唤醒操作,可能会出现多个等待进程,因而还需要有一个进程等待队列,这个等待队列被称为紧急等待队列 。 它的优先级应当高于入口等待队列的优先级由于管程通常是用于管理资源的,
因而在管程内部,应当存在某种等待机制 。 当进入管程的进程因资源被占用等原因不能继续运行时使其等待 。
为此在管程内部可以说明和使用一种特殊类型的变量 。
称作条件变量：
VAR C:condition;
对于条件型变量,可以执行 wait和
signal操作：
wait（ c）,如果紧急等待队列非空,
则唤醒第一个等待者；否则释放管程的互斥权,执行此操作的进程的
PCB入 c链尾部
signal（ c）,如果 c链为空,
则相当于空操作,执行此操作的进程继续；否则唤醒第一个等待者,执行此操作的进程的
PCB入紧急等待队列的尾部管程的实现两个主要途径：
* 直接构造
* 间接构造,即用某种已经实现的同步机制去构造前者效率高例子：用 PV操作构造管程管程的四个组成部分：
名称
数据结构说明
对该数据结构进行操作的一组过程 /函数
初始化语句
TYPE one_instance=RECORD
mutex:semaphore;（ 初值 1）
urgent:semaphore;（ 初值 0）
urgent_count:integer;（ 初值 0）
END;
TYPE
monitor_elements=MODULE;
define enter,leave,wait,signal;
mutex（ 入口互斥队列 ）
urgent（ 紧急等待队列 ）
urgent_count（ 紧急等待计数 ）
PROCEDURE enter(VAR
instance:one_instance);
BEGIN
P(instance.mutex)
END;
PROCEDURE leave(VAR
instance:one_instance);
BEGIN
IF instance.urgent_count >0 THEN
BEGIN instance.urgent--;
V(instance.urgent)
END
ELSE
V(instance.mutex)
END;
PROCEDURE wait(VAR
instance:one_instance;VAR s:semephore;VAR
count:integer);
BEGIN
count++;
IF instance.urgent_count>0 THEN
BEGIN
instance.urgent_count--;
V(instance.urgent)
END
ELSE
V(instance.mutex);
P(s);
END;
PROCEDURE signal(VAR
instance:one_instance;VAR
s:semaphore;VARcount:integer);
BEGIN
IF count>0 THEN
BEGIN
count--;
instance.urgent_count++;
V(s);
P(instance.urgent)
END
END;
例子：一个信息缓冲区是一个共享资源抽象成一个数据结构：数组构造一些操作 （ 过程或函数 ）
发送：向缓冲区发消息接收：从缓冲区取消息隐藏了内部的数据结构和实现细节例子：读者 -写者问题
TYPEr_and_w=MODULE;
VAR instance:one_instance;
rq,wq:semaphore;
r_count,w_count:integer;
reading_count,write_count:integer;
define
start_r,finish_r,start_w,finish_w;
use monitor_elements.enter,
monitor_elements.leave,
monitor_elements.wait,
monitor_elements.signal;
PROCEDUREstart_r;
BEGIN
monitor_elements.enter(instance);
IF write_count>0THEN
monitor_elements.wait
(instance,rq,r_count);
reading_count++;
monitor_elements.signal
(instance,rq,r_count);
monitor_elements.leave(instance);
END;
PROCEDUREfinish_r;
BEGIN
monitor_elements.enter(instance);
reading_count--;
IF reading_count=0 THEN
monitor_elements.signal
(instance,wq,w_count);
monitor_elements.leave(instance);
END;
PROCEDUREstart_w;
BEGIN
monitor_elements.enter(instance);
write_count++;
IF (write_count>1)
OR(reading_count>0) THEN
monitor_elements.wait
(instance,wq,w_count);
monitor_elements.leave(instance);
END;
BEGIN
reading_count::=0;
write_count::=0;
r_count:=0;
w_count::=0;
END;
读者的活动：
r_and_w.start_r;
读操作；
r_and_w.finish_r;
写者的活动：
r_and_w.start_w;
写操作；
r_and_w.finish_w;
管程和进程的异同点：
（ 1） 设置进程和管程的目的不同
（ 2） 系统管理数据结构进程,PCB
管程：等待队列
（ 3） 管程被进程调用
（ 4） 管程是操作系统的固有成分,无创建和撤消
2.4 进程通信概述消息缓冲通信方式
2.4.1 概述
P.V操作实现的是进程之间的低级通讯,
所以 P.V为低级通讯原语 。 它只能传递简单的信号,不能传递交换大量信息如果要在进程间传递大量信息则要用
Send / Receive原语 （ 高级通讯原语 ）
2.4.1 概念进程通信的方式共享内存,
相互通信的进程间设有公共内存,一组进程向该公共内存中写,另一组进程从公共内存中读,通过这种方式实现两组进程间的信息交换这种通信模式需要解决两个问题？
进程通信的方式消息传递,
系统为进程提供了两个高级通讯原语 send
和 receive
send：
当要进行消息传递时执行 send
receive：
当接收者要接收消息时执行 receive
共享文件模式,
管道通信消息传递模式
消息缓冲在内存中开设缓冲区,发送进程将消息送入缓冲区,接收进程接收传递来的缓冲区
信箱通信直接方式：
发送进程发消息时要指定接收进程的名字,
反过来,接收时要指明发送进程的名字
Send(receiver,message)
Receiver(sender,message)
* 对称形式：一对一
* 非对称形式：多对一 （ 顾客 /服务员 ）
有缓冲 （ 有界,无界 ）,无缓冲间接方式：
发送进程发消息时不指定接收进程的名字,而是指定一个中间媒介,即信箱 。
进程间通过信箱实现通信发送原语,send(MB,Message)
接收原语,receive(MB,Message)
2.4.2 消息缓冲
（ 有界缓冲区原理 ）,
在操作系统空间设置一组缓冲区,当发送进程需要发送消息时,执行 send系统调用,产生自愿性中断,进入操作系统,操作系统为发送进程分配一个空缓冲区,并将所发送的消息从发送进程 copy到缓冲区中,然后将该载有消息的缓冲区连接到接收进程的消息链链尾,如此就完成了发送过程 。 发送进程返回到用户态继续执行
2.4.2 消息缓冲
（ 有界缓冲区原理 ）,
在以后某个时刻,当接收进程执行到 receive接收原语时,也产生自愿性中断进入操作系统,
由操作系统将载有消息的缓冲区从消息链中取出,并把消息内容 copy到接收进程空间,之后收回缓冲区,如此就完成了消息的接收,接收进程返回到用户态继续进行
PCB
......
Send(R,M)
......
SIZE:消息长度
TEXT:消息正文
......
消息链指针
......
......
Receive(pid,N)
......
SIZE:消息长度
TEXT:消息正文
......
M,N:
接受进程 R发送进程 S
消息消息消息
......
消息缓冲区结构：
消息长度消息正文发送者消息队列指针用 P.V操作来实现 Send原语,
Send（ R,M） P(m-mutex);
Begin 把缓冲区挂到接收进程根据 R找接收进程,的消息链链尾 ;
如果没找到出错返回 ; V(m-mutex);
申请空缓冲区 P（ s-b） ； V(s-m);
P(b-mutex); END
摘空缓冲区 ;
V(b-mutex);
把消息从 M处 copy到空缓冲区 ;
其中 s-b初值,n ;s-m初值,0
管道通信方式 Pipe
也称共享文件方式,基于文件系统,
利用一个打开的共享文件连接两个相互通信的进程,文件作为缓冲传输介质发送进程 接收进程字符流方式写入读出先进先出顺序
2.5 进程调度（ CPU调用）
要解决的问题
WHAT：按什么原则分配 CPU— 进程调度算法
WHEN：何时分配 CPU— 进程调度的时机
HOW,如何分配 CPU— CPU调度过程
（ 进程的上下文切换 ）
何时切换进程?
只要 OS取得对 CPU的控制,进程切换就可能发生,如,当,
– 超级用户调用
来自程序的显式请求 (如：打开文件 ),该进程多半会被阻塞
– 陷阱
最末一条指令导致出错,会引起进程移至退出状态
– 中断
外部因素影响当前指令的执行,控制被转移至 IH
（ 中断处理程序 ）
中断的例子
– 时钟
进程用完其时间片,被转换至就绪状态
– I/O
先前等待该事件的进程被转换为就绪 (或就绪挂起 )状态
然后重新运行该进程或选择一更高优先级的进程
– 存储器因素
内存地址是在虚拟存储器中,它必须把对应的存储块调入主存
于是相应的进程成为阻塞状态 (等待 I/O完成 )
方式切换
在中断没有引起进程切换时,方式切换可能发生
控制可只返回给中断程序
然后只有处理器状态信息需要保存在栈中
这称为方式切换 (当进入 IH时,用户方式转到内核方式 )
较少过载：不需要象进程切换那样更新
PCB
在进程（上下文）中切换的步骤
保存处理器的上下文,包括程序计数器和其它寄存器
用新状态和其它相关信息更新正在运行进程的 PCB
把移至合适的队列 -就绪,阻塞
选择另一个要执行的进程
更新被选中进程的 PCB
从被选中进程中重装入 CPU 上下文
2.5.1 进程调度算法
1,进程调度进程调度的任务是控制协调进程对 CPU的竞争即按一定的调度算法从就绪队列中选中一个进程,把 CPU的使用权交给被选中的进程
2．确定算法的原则
具有公平性
资源利用率高 （ 特别是 CPU利用率 ）
在交互式系统情况下要追求响应时间
（ 越短越好 ）
在批处理系统情况下要追求系统吞吐量
3．各种进程调度算法先进先出进程调度算法 （ FIFO）
按照进程就绪的先后次序来调度进程优点,实现简单缺点,没考虑进程的优先级基于优先数的调度
（ HPF— Highest Priority First）
优先选择就绪队列中优先级最高的进程投入运行优先级根据优先数来决定确定优先数的方法静态优先数法：
在进程创建时指定优先数,在进程运行时优先数不变动态优先数法：
在进程创建时创立一个优先数,但在其生命周期内优先数可以动态变化 。 如等待时间长优先数可改变两种占用 CPU的方式可剥夺式 （ 可抢占式 Preemptive）,
当有比正在运行的进程优先级更高的进程就绪时,系统可强行剥夺正在运行进程的 CPU，
提供给具有更高优先级的进程使用不可剥夺式 （ 不可抢占式 Nonpreemptive ）,
某一进程被调度运行后,除非由于它自身的原因不能运行,否则一直运行下去时间片轮转程序调度算法
(RR— Round Robin)
把 CPU划分成若干时间片,并且按顺序赋给就绪队列中的每一个进程,进程轮流占有 CPU,当时间片用完时,即使进程未执行完毕,系统也剥夺该进程的 CPU,将该进程排在就绪队列末尾 。 同时系统选择另一个进程运行分时系统中常用时间片轮转法时间片选择问题：
固定时间片可变时间片与时间片大小有关的因素：
系统响应时间就绪进程个数
CPU能力多队列反馈调度算法：
将就绪队列分为 N级,每个就绪队列分配给不同的时间片,队列级别越高,时间越长,级别越小,时间片越小,最后一级采用时间片轮转,其他队列采用先进先出； 系统从第一级调度,当第一级为空时,系统转向第二个队列,,....当运行进程用完一个时间片,放弃 CPU时,进入下一级队列；等待进程被唤醒时,进入原来的就绪队列；当进程第一次就绪时,进入第一级队列
* 首先系统中设置多个就绪队列
* 每个就绪队列分配给不同时间片,优先级高的为第一级队列,时间片最小,随着队列级别的降低,时间片加大
* 各个队列按照先进先出调度算法
* 一个新进程就绪后进入第一级队列
* 进程由于等待而放弃 CPU后,进入等待队列,一旦等待的事件发生,则回到原来的就绪队列
* 当有一个优先级更高的进程就绪时,可以抢占 CPU,被抢占进程回到原来一级就绪队列末尾
* 当第一级队列空时,就去调度第二级队列,如此类推
* 当时间片到后,进程放弃 CPU,回到下一级队列
2.5.2 进程调度的时机当一个进程运行完毕，或由于某种错误而终止运行当一个进程在运行中处于等待状态（等待
I/O）
分时系统中时间片到
2.5.2 进程调度的时机当有一个优先级更高的进程就绪 （ 可抢占式 ）,例如：新创建一个进程,一个等待进程变成就绪在进程通信中,执行中的进程执行了某种原语操作 （ P操作,阻塞原语,唤醒原语 ）
2.5.3 CPU调度过程
* 保存现场：顺序保存,最后一步保存 PSW
* 选择要运行的程序
（ 如果没有就绪进程,系统会安排一个闲逛进程 (idle),没有其他进程时该进程一直运行,在执行过程中可接收中断 ）
* 恢复现场：最后一步恢复选中进程的 PSW
2.6 系统核心系统核心：
向上提供多个无中断的虚拟机器在核心内不允许中断特点,* 为进程运行提供一个舞台
* 核心常驻内存
* 设计短小精焊
2.6.1 核心的组成中断处理进程管理,
调度 控制 通讯 互斥 同步等原语管理,
在核心中提供一系列原语,同步,通信,创建,撤消等队列管理,
队列数据结构,指向队首的表指针三个队列,运行,就绪,等待队列排队方式,排队首排队尾插 队出队方式,队首出队 /队中出队队列管理,中断之后,进程调度之前现场管理,
保存现场 ;注意顺序,中断之后第一步恢复现场,恢复时机,进程调度最后一步时钟管理,
以固定频率 +1 -1
用途,进入绝对时钟间隔时钟进行分析比较虚时钟,
每个进程分配给一个虚时钟来记录 CPU时间,这个时钟称为虚时钟虚时钟存放在 PCB中,属于现场的一部分,
进程运行时,将虚时钟放入内存开辟的专门单元,离开 CPU则放在 PCB中
2.6.2 核心处理流程进入核心的唯一入口,中断中断后进入核心,由硬件完成
2.6.3 内核的执行特点由中断驱动的,中断 → 内核 → 退出内核执行是连续的内核执行过程中在中断屏蔽状态下内核使用特权指令
2.7 死锁死锁的基本概念死锁的解决方案
（ 预防,避免,检测及解除 ）
资源分配图死锁的现象
2.7.1 死锁的基本概念死锁的定义,
一组进程中,每个进程都无限等待被该组进程中另一进程所占有的资源,因而永远无法得到的资源,这种现象称为进程死锁,这一组进程就称为死锁进程
2.7.1 死锁的基本概念死锁 （ Deadlock）
饥饿 （ Starvation）
关于死锁的一些结论：
参与死锁的进程最少是两个
（ 两个以上进程才会出现死锁 ）
参与死锁的进程至少有两个已经占有资源参与死锁的所有进程都在等待资源参与死锁的进程是当前系统中所有进程的子集注：
如果死锁发生,会浪费大量系统资源,
甚至导致系统崩溃
2.7.1 死锁的基本概念资源永久性资源,可以被多个进程多次使用
（ 可再用资源 ）
* 可抢占资源
* 不可抢占资源
2.7.1 死锁的基本概念资源临时性资源,只可使用一次的资源；如信号量,中断信号,同步信号等 （ 可消耗性资源 ）
,申请 --分配 --使用 --释放,模式
2.7.1 死锁的基本概念产生死锁的四个必要条件：
互斥使用 （ 资源独占 ）
不可强占 （ 不可剥夺 ）
请求和保持 （ 部分分配,占有申请 ）
循环等待
1) 互斥使用（资源独占）：
一个资源每次只能给一个进程使用
2) 不可强占（不可剥夺）：
资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放
3) 请求和保持：
（部分分配，占有申请）
一个进程在申请新的资源的同时保持对原有资源的占有 。
（ 只有这样才是动态申请,动态分配 ）
4) 循环等待：
存在一个进程等待队列
{P1,P2,…,Pn},
其中 P1等待 P2占有的资源,P2等待 P3占有的资源,…,Pn等待 P1占有的资源,
形成一个进程等待环路
2.7.2 死锁的解决方案
1,产生死锁的例子申请不同类型资源产生死锁
P1：
…
申请打印机申请扫描仪使用释放打印机释放扫描仪
…
P2：
…
申请扫描仪申请打印机使用释放打印机释放扫描仪
…
申请同类资源产生死锁 （如内存）
设有资源 R,R有 m个分配单位,由 n个进程 P1,P2,…,Pn（ n > m） 共享 。 假设每个进程对 R的申请和释放符合下列原则：
* 一次只能申请一个单位
* 满足总申请后才能使用
* 使用完后一次性释放申请同类资源产生死锁 （如内存）
m=2,n=3
资源分配不当导致死锁产生
2,解决死锁的方法不让死锁发生,
静态策略：设计合适的资源分配算法,
不让死锁发生动态策略：
让死锁发生,
2.7.3 死锁预防定义：
在系统设计时确定资源分配算法,保证不发生死锁 。 具体的做法是破坏产生死锁的四个必要条件之一
2.7.3 死锁预防破坏,不可剥夺,条件在允许进程动态申请资源前提下规定,
一个进程在申请新的资源不能立即得到满足而变为等待状态之前,必须释放已占有的全部资源,若需要再重新申请
2.7.3 死锁预防破坏,请求和保持,条件要求每个进程在运行前必须一次性申请它所要求的所有资源,且仅当该进程所要资源均可满足时才给予一次性分配
2.7.3 死锁预防破坏,循环等待,条件采用 资源有序分配法,
把系统中所有资源编号,进程在申请资源时必须严格按资源编号的递增次序进行,否则操作系统不予分配
2.7.3 死锁预防例如,1,2,3,…,10
P1：
申请 1
申请 3
申请 9
…
P2：
申请 1
申请 2
申请 5
…
P3 …… P10
2.7.4 死锁避免
A申请
B申请释放 A
释放 B
获得 A
获得 B
Q进程
P 和 Q
申请 A
死锁不可避免
P 和 Q
申请 B
P进程获得 A 获得 B 释放 A 释放 B
B申请
A申请
Q进程释放 A
释放 B
获得 A
获得 B
A申请
B申请
P 和 Q
申请 A
P 和 Q
申请 B
P进程获得 A 释放 A 获得 B 释放 B
A申请 B申请
2.7.4 死锁避免定义：
在系统运行过程中,对进程发出的每一个系统能够满足的资源申请进行动态检查,并根据检查结果决定是否分配资源,若分配后系统可能发生死锁,则不予分配,否则予以分配
2.7.4 死锁避免安全状态与不安全状态安全状态：
如果存在一个由系统中所有进程构成的安全序列 P1,… Pn，则系统处于安全状态
2.7.4 死锁避免安全序列：
一个进程序列 {P1,…,Pn}是安全的，如果对于每一个进程
Pi(1≤ i≤ n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程 Pj (j < i )当前占有资源量之和，系统处于安全状态。
(安全状态一定是没有死锁发生的 )
安全状态与不安全状态不安全状态,不存在一个安全序列,不安全状态一定导致死锁银行家算法
n：系统中进程的总数
m：资源类总数
Available:
ARRAY[1..m] of integer;
Max:
ARRAY[1..n,1..m] of integer;
银行家算法
Allocation:
ARRAY[1..n,1..m] of integer;
Need:
ARRAY[1..n,1..m] of integer;
Request:
ARRAY[1..n,1..m] of integer;
银行家算法简记符号：
Available
Max[i]
Allocation[i]
Need[i]
Request[i]
银行家算法当进程 pi提出资源申请时,系统执行下列步骤：
（ 1 ） 若 Request[i]≤Need[i],转
（ 2） ；
否则错误返回
（ 2） 若 Request[i]≤Available,
转 （ 3） ；否则进程等待
(3） 假设系统分配了资源,则有：
Available:=Available-Request[i];
Allocation[i]:=
Allocation[i]+Request[i];
Need[i]:=Need[i]-Request[i]
若系统新状态是安全的,则分配完成若系统新状态是不安全的,则恢复原状态,进程等待银行家算法为进行安全性检查,定义数据结构：
Work:ARRAY[1..m] of integer;
Finish:ARRAY[1..n] of Boolean;
银行家算法安全性检查的步骤：
(1) Work:=Available;
Finish:=false;
(2) 寻找满足条件的 i：
a.Finish[i]=false;
b.Need[i]≤Work ;
如果不存在,则转 (4)
银行家算法
(3) Work:=Work+Allocation[i];
Finish[i]:=true;
转 (1)
(4) 若对所有 i,Finish[i]=true,则系统处于安全状态,否则处于不安全状态银行家算法目前占有量 最大需求量 尚需要量
P1 1 4 3
P2 4 6 2
P3 5 8 3
系统剩余量 2
死锁检测：
允许死锁发生,操作系统不断监视系统进展情况,判断死锁是否发生一旦死锁发生则采取专门的措施,
解除死锁并以最小的代价恢复操作系统运行
2.7.5 死锁的检测与解除
2.7.5 死锁的检测与解除检测时机：
当进程等待时检测死锁
（ 其缺点是系统的开销大 ）
定时检测系统资源利用率下降时检测死锁
2.7.5 死锁的检测与解除死锁检测算法
* 每个进程和资源指定唯一编号
* 设置一张资源分配表记录各进程与其占用资源之间的关系
* 设置一张进程等待表记录各进程与要申请资源之间的关系
2.7.5 死锁的检测与解除死锁检测算法资源分配表 进程等待表
r1 p2 p1 r1
r2 p5 p2 r3
r3 p4 p4 r4
r4 p1
… … … …
死锁的解除：
重要的是以最小的代价恢复系统的运行 。 方法如下：
1） 重新启动
2） 撤消进程
3） 剥夺资源
4） 进程回退
2.7.6 资源分配图用有向图描述进程的死锁准确,形象系统由若干类资源构成,一类资源称为一个资源类；每个资源类中包含若干个同种资源,称为资源实例
2.7.6 资源分配图二元组 G=（ V,E）
V：结点集,分为 P,R两部分
P={p1,p2,…,pn}
R={r1,r2,…,rm}
E：边的集合,其元素为有序二元组
(pi,rj)或 (rj,pi)
2.7.6 资源分配图表示法资源类 （ 资源的不同类型 ）
用方框表示资源实例 （ 存在于每个资源中 ）
用方框中的黑圆点表示进程用圆圈中加进程名表示
2.7.6 资源分配图分配边：
资源实例?进程的一条有向边申请边：
进程?资源类的一条有向边有环有死锁有环无死锁
2.7.6 资源分配图死锁定理如果资源分配图中没有环路,则系统中没有死锁,如果图中存在环路则系统中可能存在死锁如果每个资源类中只包含一个资源实例,则环路是死锁存在的充分必要条件
2.7.6 资源分配图资源分配图化简：方法如下
1） 找一个非孤立点进程结点且只有分配边,去掉分配边,将其变为孤立结点
2） 再把相应的资源分配给一个等待该资源的进程,即将某进程的申请边变为分配边
【 作业,】
已分配的资源 最大需求量
A B C A B C
P10 1 0 7 5 3
P22 0 0 3 2 2
P33 0 2 9 0 2
P42 1 1 2 2 2
P50 0 2 4 3 3
剩余资源 A B C
3 3 2
问题,此状态是否为安全状态,如果是,则找出安全序列在此基础上
P2 申请 （ 1,0,2） 能否分配？ 为什么？
P5 申请 （ 3,3,0） 能否分配？ 为什么？
P1 申请 （ 0,2,0） 能否分配？ 为什么？
2.8 线程的基本概念线程的引入线程与进程的对比线程的实现线程的例子,Solaris
2.8.1 线程的引入进程的两个基本属性：
资源的拥有者：
给每个进程分配一虚拟地址空间,保存进程映像控制一些资源 （ 文件,I/O设备 ）
有状态,优先级,调度
2.8.1 线程的引入进程的两个基本属性：
调度单位：
进程是一个执行轨迹以上两个属性构成进程并发执行的基础
2.8.1 线程的引入系统必须完成的操作：
创建进程
撤消进程
进程切换缺点：时间空间开销大,限制并发度的提高
2.8.1 线程的引入线程,有时称轻量级进程进程中的一个实体是一个 CPU调度单位资源的拥有者还是进程或称任务将原来进程的两个属性分开处理
2.8.1 线程的引入线程：
有执行状态
不运行时保存上下文
有一个执行栈
有一些局部变量的静态存储
可存取所在进程的内存和其他资源
可以创建,撤消另一个线程线程和进程：
单进程,单线程单进程,多线程多进程,一个进程一个线程多进程,一个进程多个线程
P C B 用户栈单 线程进程模型用户地址空间核心栈线程控制块：
包含了寄存器映像，线程优先数和线程状态信息。
P C B
多线程进程模型用户地址空间用户栈核心栈线程控制块用户栈核心栈线程控制块用户栈核心栈线程控制块引入线程的好处：
两个线程的切换花费时间少
创建一个新线程花费时间少 （ 结束亦如此 ）
因为同一进程内的线程共享内存和文件,
因此它们之间相互通信无须调用内核例子 1：
因此有效的方法是：为每一个请求创建一个线程
LAN中的一个文件服务器,在一段时间内需要处理几个文件请求在一个 SMP机器上：多个线程可以同时在不同的处理器上运行例子 2：
一个线程显示菜单,并读入用户输入；
另一个线程执行用户命令考虑一个应用：由几个独立部分组成,这几个部分不需要顺序执行,则每个部分可以以线程方式实现当一个线程因 I/O阻塞时,可以切换到同一应用的另一个线程引入线程的好处：
两个线程的切换花费时间少
创建一个新线程花费时间少 （ 结束亦如此 ）
因为同一进程内的线程共享内存和文件,
因此它们之间相互通信无须调用内核
2.8.2 线程与进程的比较
调度
并发性
拥有资源
系统开销
2.8.3 线程的实现机制
用户级线程
核心级线程
两者结合方法用户级线程（ ULT）：
核心不知道线程的存在
由应用程序完成所有线程的管理通过线程库
线程切换不需要核心态特权
调度是应用特定的线程库：
在线程之间传递消息和数据
创建,撤消进程
调度线程执行
保护和恢复线程上下文对用户级线程的核心活动：
当线程调用系统调用时,整个进程阻塞
核心不知道线程的活动,但仍然管理线程的进程的活动
但对线程库来说,线程仍然是运行状态即线程状态是与进程状态独立的用户级线程的优点和缺点：
调度是应用程序特定的：可以选择最好的算法优点：
线程切换不调用核心
ULT可运行在任何操作系统上 （ 只需要线程库用户级线程的优点和缺点：
大多数系统调用是阻塞的,因此核心阻塞进程,故进程中所有线程将被阻塞缺点：
核心只将处理器分配给进程,同一进程中的两个线程不能同时运行于两个处理器上核心级线程（ KLT）：
没有线程库,但对核心线程工具提供 API
所有线程管理由核心完成
核心维护进程和线程的上下文
线程之间的切换需要核心支持
以线程为基础进行调度
例子,Windows NT,OS/2
核心级线程的优点和缺点：
阻塞是在线程一级完成优点：
对多处理器,核心可以同时调度同一进程的多个线程
核心例程是多线程的核心级线程的优点和缺点：
在同一进程内的线程切换调用内核,导致速度下降缺点：
两者分析：
系统调用
线程的调度和切换速度
线程执行时间
ULT和 KLT结合方法：
大量线程调度和同步在用户空间完成
线程创建在用户空间完成
程序员可以调整 KLT的数量
可以取两者中最好的
例子,Solaris
2.8.4 实例,Solaris
进程：
用户地址空间
用户栈
进程控制块
2.8.4 实例,Solaris
用户级线程 （ 线程库 ）,
可在应用进程中建立多个 ULT
每个 ULT需要：栈,程序计数器不受调度程序的调度,线程切换快对操作系统不可见提供应用程序并行性接口
2.8.4 实例,Solaris
核心级线程,
设置了大量 KLT
有一个小的数据结构和栈完成内核的所有工作调度处理器的单位,其结构由核心维护
2.8.4 实例,Solaris
轻型进程 （ LWP）,
每个 ULT利用 LWP与内核通信每个 LWP支持一个或多个用户级线程,并映射到一个核心级线程每个 LWP对应用程序可见,内核看到的是多个 LWP而看不到 ULT
Solaris：多功能性
如果逻辑并行性不需要硬件并行性的支持,则可使用 ULT
例子：多个窗口,任一时刻只有一个窗口是活跃的
如果线程可以被阻塞,则可以指定两个或多个 LWP,避免整个应用程序的阻塞
Solaris：
如果逻辑并行性不需要硬件并行性的支持,则可使用 ULT
例子：多个窗口,任一时刻只有一个窗口是活跃的
如果内核级线程可能被阻塞,则可以指定两个或多个 LWP,避免整个应用程序的阻塞分派唤醒继续抢占停止可运行睡眠睡眠停止停止停止用户级线程活跃连接在 LWP上分派 唤醒继续时间片或抢占停止运行阻塞系统调用停止停止轻型进程状态
LWP状态独立于状态 ULT
（受限制 ULT除外）
可运行阻塞唤醒进程 1 进程 2 进程 3 进程 4 进程 5
进程库用户内核硬件用户级进程 内核级进程 轻型线程 处理器
