进程互斥与同步互斥.ppt

}
47
2. 用信号灯的P、V操作实现互斥
框图描述 设：mutex为互斥信号灯，初值为1。
进程 pa
进程 pb
p(mutex)
p(mutex)
进入临界区csa
进入临界区csb
v(mutex)
v(mutex)
48
程序描述
程序 task2 main( ) { int mutex=1； cobegin pa( )； pb( )； coend }
test： if (w为1) ∕* goto test； else w=1； ∕*
}
不断的测 试锁的状 态，耗费 *∕ CPU时间
*∕
42
开锁原语
算法 unlock 输入：锁变量w 输出：无 {
w=0；∕*开锁*∕ }
2. 信号灯和P、V操作 什么是信号灯 信号灯是一个确定的二元组(s，q)，s是一 个具有非负初值的整型变量，q是一个初始 状态为空的队列。操作系统利用信号灯的 状态对并发进程和共享资源进行控制和管 理。
46
程序描述 程序 task1 main( ) {
int w=1； ∕* 互斥锁 *∕ cobegin
pa( )； pb( )； coend }
47
程序描述 pa( ) {
lock(w)；
csa ； unlock(w)；
}
pb( ) {
lock(w)；
csb ； unlock(w)；

37
间接制约
由于共享某一公有资源而引起的在临界区 内不允许并发进程交叉执行的现象，称为 由共享公有资源而造成的对并发进程执行 速度的间接制约。 受间接制约的类中各程序段在执行顺序上 是任意的。 间接制约的几个进程是互斥关系
使用临界区应遵守的原则
各进程享有独立，平等的竞争共享资源的 权利。 某个进程不在临界区，不阻止其他进程进 入 排它性，只能有一个进程进入临界区 有限等待，某个进程申请使用临界区后， 必须在有限的时间内离开。
设x的初值为10，两种情况下的执行结果：
情况A： x = 10+2
情况B： x = 10+1
35
一次仅允许一个进程使用的资源称为临界资源。 硬件：如输入机、打印机、磁带机等 软件：如公用变量、数据、表格、队列等
每个进程中访问临界资源的那段程序称为临界区
进程A
csa { x := x+1;
cp
iop
A
缓冲区buf
DC BA
B
C
D
39
直接制约 一组在异步环境下的并发进程，各自 的执行结果互为对方的执行条件，从 而限制各进程的执行速度的过程称为 并发进程间的直接制约。 直接制约的进程之间是同步关系
10
4.5同步机构
操作系统提供的同步机构如下两种：
锁和上锁、开锁操作 信号灯和PV操作
1. 锁和上锁、开锁操作
44
P 操作的实现
入口
S-1 → S
≥0 S≥0 ?
0
返回
入信号灯等待队列
置“等待状态”
转进程调度
V 操作 V 操作的定义
对信号灯s的 v操作记为 v(s)。v(s)是 一个不可分割的原语操作，即取信号灯 值加1，若相加结果大于零，进程继续执 行，否则，要帮助唤醒在信号灯等待队 列上的一个进程。
45
V 操作的实现
入口
S+1 → S >0
S≤0 ?
从信号灯的等待队列中取出首元素
入就绪队列 置“就绪状态”
返回
PV操作是通过原语实现的
4.6 进程互斥的实现
1. 用上锁原语和开锁原语实现进程互斥
框图描述
进程 pa
进程 pb
上锁原语 进入临界区csa
开锁原语
上锁原语 进入临界区csb
开锁原语
34
例2：两个进程共享一个变量x
两个进程共享一个变量x时，两种可能的执行次序：
A：
p1： r1 := x；r1:= r1+1； x := r1 ；
p2：
r2:= x；r2 := r2+1； x := r2 ；
B：
p1： r1 := x；
r1:= r1+1； x := r1 ；
p2：
r2:= x；r2 := r2+1； x := r2 ；
进程B
csb { x := x+1;

36
互斥 在操作系统中，当某一进程正在访问某一存储区域时， 就不允许其他进程来读出或者修改存储区的内容，否则， 就会发生后果无法估计的错误。进程间的这种相互制约 关系称为互斥。
进程A
csa { x := x+1;
进程B
csb { x := x+1;
2. 进程同步的概念
什么是进程同步 并发进程在一些关键点上可能需要互相等待与互通消息， 这种相互制约的等待与互通消息称为进程同步。
进程同步的例 病员就诊
看病活动：
要病人去化验；
等化验结果；
继续诊病；
化验活动：
需要进行化验 ?
进行化验； 开出化验结果；

38
共享缓冲区的计算进程与打印进程的同步 计算进程 cp和打印进程 iop公用一个单缓冲
∕* 互斥信号灯 *∕
49
程序描述
pa( ) { p(mutex)； csa ； v(mutex)； }
pb( ) { p(mutex)； csb ； v(mutex)；
}
信号灯可能的取值
4.4 进程之间的约束关系
程序并发执行的相互制约
间接的相互制约关系 —— 资源共享（竞争资 源系统） 直接的相互制约关系 —— 公共变量（进程协 作）
1. 进程互斥的概念 临界资源 例1：x代表某航班机座号，p1和p2两个售票进 程，售票工作是对变量x加1。这两个进程在一 个处理机C上并发执行，分别具有内部寄存器 r1和r2。
什么是锁 用变量w代表某种资源的状态，w称为“锁” 。 上锁操作和开锁操作
检测w的值 (是0还是1)；
如果w的值为1，继续检测；
如果w的值为0，将锁位置1 (表示占用资源)，进入临
界区执行。
(此为上锁操作)
临界资源使用完毕，将锁位置0。 (此为开锁操作)
40
上锁原语Βιβλιοθήκη 算法 lock 输入：锁变量w 输出：无 {
43
信号灯
信号灯是整型变量。 变量值 ≥ 0 时，表示绿灯，进程执行； 变量值 0 时，表示红灯，进程停止执
行。 注意：创建信号灯时，应准确说明信号灯
s 的意义和初值 (这个初值 绝不能为负值)。
P 操作 P 操作的定义 对信号灯s的 p操作记为 p(s)。p(s)是一 个不可分割的原语操作，即取信号灯值 减1，若相减结果为负，则调用p(s)的进 程被阻，并插入到该信号灯的等待队列 中，否则可以继续执行。