P .... pturn = true; while (qturn);
临界区 pturn = false;
...
Q .....
qturn = true;
while (pturn);
临界区
qturn = false; ...
.
18
软件解法(4):Dekker算法（1/2）
在解法(3)基础上引入turn枚举类型 P : while (true) { pturn = true; while (qturn) { if (turn==2) { pturn = false; while (turn==2)； pturn = true; }
buy bread } remove note B
.
15
软件解法 (1)
free: 表示临界区标志 true: 有进程在临界区 false:无进程在临界区(初值) ....
while (free); free = true;
临界区
free = false;
.
16
软件解法 (2)
turn: true
间接作用：
进程间要通过某种中介发生联系，是无意识安 排的，可发生在两个有联系的进程之间，也可 发生在无关进程之间
.
4
进程的同步（直接作用）
进程的同步：synchronism 指系统中多个进程中发生的事件存在某种 时序关系，需要相互合作，共同完成一项 任务。具体说，一个进程运行到某一点时 要求另一伙伴进程为它提供消息，在未获 得消息之前，该进程处于等待状态，获得 消息后被唤醒进入就绪态
.
9
P1 互斥
a := a +1 print (a)
P2 互斥
a := a -1 print (a)
P3 互斥
If a < 0 then a := a +1 else a:= a-1
进程的互斥
.
（间接作用）10
使用互斥区的原则
有空让进：当无进程在互斥区时，任何有权使用 互斥区的进程可进入
无空等待：不允许两个以上的进程同时进入互斥区 多中择一：当没有进程在临界区，而同时有多个进
.
14
谁买面包？——解法3
• 进程A
• 进程B
leave note A; while (Note B) ——X
do nothing; if (noBread) buy bread; }
remove note A
leave note B; If (noNote A) { —Y
do nothing; if (noBread)
•甲
5:00 查看冰箱，面包没了 5:05 去超市 5:10 到达超市 5:15 买好面包 5:20 回家,把面包放入冰箱 5:25 5:30
•乙
查看冰箱，面包没了 去超市 到达超市 买好面包 回家,把面包放入冰箱 噢,Too Much
.
3
1.进程间的联系
直接作用和间接作用
直接作用：
进程间的相互联系是有意识的安排的，直接作 用只发生在相交进程间
系统中某些资源一次只允许一个进程使用， 称这样的资源为临界资源或互斥资源或共享变 量
.
7
【思考题】
• 例举两个现实生活中需要同步与互斥的 例子
.
8
临界区（互斥区）：critical section
一个程序片段的集合，这些程序片段分 散在不同的进程中，对某个共享的数据 结构（共享资源）进行操作
临界区:在进程中涉及到临界资源的程序段 相关临界区:多个进程的临界区
程要求进入临界区，只能让其中之一进 入临界区，其他进程必须等待 有限等待：任何进入互斥区的要求应在有限的时间 内得到满足 让权等待：处于等待状态的进程应放弃占用CPU， 以使其他进程有机会得到CPU的使用权
.
11
使用互斥区的原则（续）
前提：任何进程无权停止其它进程的运行 进程之间相对运行速度无硬性规定
P进入临界区
false
Q进入临界区
....
P: while (not turn);
临界区
turn = false;
Q: while (turn);
临界区
turn = true;
.
17
软件解法(3)
pturn,qturn: 初值为false P进入临界区的条件: pturn∧ not qturn Q进入临界区的条件: not pturn∧ qturn
初值任意
} 临界区
turn = 2;
pturn = false;
..... }
.
19
软件解法(4)（2/2）
Q : while (true) { qturn = true; while (pturn) { if (turn==1) { qturn = false; while (turn==1)； qturn = true; }
.
5
例子
司机 P1 while (true)
{ 启动车辆； 正常运行； 到站停车；
}
售票员 P2 while (true) {
关门； 售票； 开门； }
.Leabharlann 6进程的互斥（间接作用）
由于各进程要求共享资源，而有些资源需要互斥 使用，因此各进程间竞争使用这些资源，进程 的这种关系为进程的互斥
临界资源：critical resource
.
13
谁买面包？——解法2
• 进程A
• 进程B
leave note A; If (noNote B) {
if (noBread) buy bread
} remove note A
leave note B; If (noNote A) {
if (noBread) buy bread
} remove note B
}
临界区
turn = 1;
第四章 进程管理
• 多道程序设计
• 进程
• 线程
• 进程（线程）调度（CPU调度）
• 进程间的同步与互斥
• 进程间的通信
• 管程
.
1
五、进程的同步机制
• 进程的同步与互斥 • 临界区的概念及使用原则 • 信号量及PV操作 • 生产者消费者问题 • 读者写者问题 • 哲学家就餐问题
.
2
（同步问题）例子：谁买面包？
进程互斥的解决有两种做法: ➢ 由竞争各方平等协商 ➢ 引入进程管理者，由管理者来协调竞争各方对 互斥资源的使用
具体方法： • 硬件 • 软件
.
12
谁买面包？——解法1
• 基本思想
–留言（锁） – 取消留言（解锁） – 如果看到留言，就不
买（等待）
• 解法1 if (nobread) { if (noNote) { leave Note; buy bread; remove Note; } }