进程同步与互斥

有______个等待进程。 ▪ 6. __________是一种只能进行P操作和V操作的特殊变量。 ▪ A 调度 B 进程 C 同步 D 信号量 ▪ 7.有m个进程共享同一临界资源，若使用信号量机制实现
对资源的互斥访问，则信号量值的变化范围是 ________________。
课堂练习
▪ 8.某车站售票厅，任何时刻最多可容纳 20 名购票者进入，当售票厅中少于 20 名购票 者时，则厅外的购票者可立即进入，否则 需在外面等待。若把一个购票者看作一个 进程，请回答下列问题：
};
正确
P.V操作讨论
1) 信号量的物理含义： S>0表示有S个资源可用 S=0表示无资源可用 S<0则| S |表示S等待队列中的进程个数
P(S):表示申请一个资源 V(S)表示释放一个资源。信号量的初值应
该大于等于0
2) P.V操作必须成对出现，有一个P操作就 一定有一个V操作
当为互斥操作时，它们同处于同一进程 当为同步操作时，则不在同一进程中出 现.
用P、V操作解决进程间互斥问题
P1
P(mutex) V(mutex) 互斥区
P2
P(mutex) V(mutex)
P3 P(mutex) V(mutex)
互斥例子
三个进程共用两个I/O缓冲区。 解：设用信号量S表示共享资源，S初始值为
2
例：用信号量及P、V原语实现两个并发进程Pa和Pb互 斥。两进程都想进入临界区S。
如果P(S1)和P(S2)两个操作在一起，那 么P操作的顺序至关重要,一个同步P操作 与一个互斥P操作在一起时同步P操作在 互斥P操作前 而两个V操作无关紧要
3）P.V操作的优缺点 优点：
简单，而且表达能力强（用P.V操作可解决 任何同步互斥问题）
缺点：
不够安全；P.V操作使用不当会出现死锁； 遇到复杂同步互斥问题时实现复杂
间接作用：
进程间要通过某种中介发生联系，是无 意识安排的，可发生在相交进程之间， 也可发生在无关进程之间
进程的同步（直接作用）
进程的同步：synchronism 指系统中多个进程中发生的事件存在某 种时序关系，需要相互合作，共同完成 一项任务。具体说，一个进程运行到某 一点时要求另一伙伴进程为它提供消息， 在未获得消息之前，该进程处于等待状 态，获得消息后被唤醒进入就绪态。
进程之间相对运行速度无硬性规定 进程互斥的解决有两种做法:
• 由竞争各方平等协商 • 引入进程管理者，由管理者来协调竞争各方
对互斥资源的使用
具体方法： 硬件（当一个进程进入临界区,就屏蔽所有
中断，但成本高） 软件（用编程解决，但常常忙等待 ）
进程互斥的软件方法
通过平等协商方式实现进程互斥的最初 方法是软件方法 。其基本思路是在进入区 检查和设置一些标志，如果已有进程在临 界区，则在进入区通过循环检查进行等待； 在退出区修改标志。 其中的主要问题是设 置什么标志和如何检查标志。
P： i = 0; while (true) { 生产产品; P(S1); 往Buffer [i]放产品; V(S2); i = (i+1) % n;
};
Q： j = 0; while (true) { P(S2); 从Buffer[j]取产品; V(S1); 消费产品; j = (j+1) % n; };
下列活动属于哪种制约关系
(1) 若干同学去图书馆借书 (2) 两队进行篮球比赛 (3) 流水线生产的各道工序 (4) 商品生产和社会消费
习题
▪ 某仓库有两名发货员，一名审核员。当顾 客提货时，只要发货员空闲，允许顾客进 入仓库提货，顾客离开时，审核员检验顾 客提货是否正确。其工作流程如下图所示。 为了利用PV操作正确地协调他们之间的工 作，设置了两个信号量S1和S2，初值分别 位2，1。图中的a，b，c，d应分别填（）。
错误
n个缓冲区、m个生产者和k个消费者
P： i = 0; while (true) { 生产产品; P(S1); P(mutex);
往Buffer [i]放产品;
i = (i+1) % n;
V(mutex); V(S2); };
Q： j = 0; while (true) { P(S2); P(mutex); 从Buffer[j]取产品; j = (j+1) % n; V(mutex); V(S1); 消费产品;
} }
P、V操作为原语操作
原语：primitive or atomic action 是由若干多机器指令构成的完成某种特定功 能的一段程序，具有不可分割性
即原语的执行必须是连续的，在执行过程中 不允许被中断 实现：开关中断
信号量的使用：
必须置一次且只能置一次初值 初值不能为负数
只能执行P、V操作
课堂练习
▪ 1.若进程信号量S的初值为2,当前值为-1,则表示有 _________个等待进程.
▪ A 0 B1 C2 D3 ▪ 2.用P、V操作管理临界区时，信号量的初值应定义为
_______ ▪ A -1 B 0 C 1 D任意值 ▪ 3.对于两个并发进程，设互斥信号量为mutex，若mutex=0，
使用互斥区的原则：
空闲让进：当无进程在互斥区时，任何有 权使用互斥区的进程可进入
忙则等待：不允许两个以上的进程同时进 入互斥区
有限等待：任何进入互斥区的要求应在有 限的时间内得到满足
让权等待：处于等待状态的进程应放弃占 用CPU，以使其他进程有机会得到CPU的使 用权
使用互斥区的原则： 前提：任何进程无权停止其它进程的运行
有错误？若颠倒两个P操作的顺 序？
▪ P： i = 0; while (true) { 生产产品; P(mutex); P(S1);
▪ 往Buffer [i]放产品;
▪ V(mutex); V(S2); i = (i+1) % n;
▪ };
Q： j = 0; while (true) { P(mutex); P(S2); 从Buffer[j]取产品; V(mutex); V(S1); 消费产品; j = (j+1) % n; };
P： i = 0; while (true) { 生产产品; P(S1); P(mutex);
往Buffer [i]放产品;
V(mutex); V(S2); i = (i+1) % n;
};
Q： j = 0; while (true) { P(S2); P(mutex); 从Buffer[j]取产品; V(mutex); V(S1); 消费产品; j = (j+1) % n; };
则________ ▪ A 表示没有进程进入临界区 ▪ B 表示有一个进程进入临界区 ▪ C表示有一个进程进入临界区，另一个进程等待进入 ▪ D 表示有两个进程进入临界区
课堂练习
▪ 4.在多进程的系统中,为了保证公共变量的完整性,各进程 应互斥进入临界区.所谓临界区是指_________
▪ A 一个缓冲区 B 一段数据区 C 同步机制 D 一段程序 ▪ 5.如果信号量的当前值为-4，则表示系统中在该信号量上
顾客进程 （i =1，2，…，n） a
在仓库提货程和P2进程共享一台打印机，用信号量和P、V 操作实现它们的互斥。
▪ 例2 矩阵A+B=矩阵和，用信号量和P、V原语操作实现它 们的同步。A用甲进程表示，B用乙进程表示。
▪ 例3 矩阵A+B= C，用信号量和P、V原语操作实现它们的 同步。A用甲进程表示，B用乙进程表示，C用丙进程表 示。
解：
1）设sem为互斥信号量，表示临界区是否可进入
2）设sem的初始值为1，表示临界区可用
3）描述：
Pa：
Pb:
P(sem)
P(sem)
<S>
<S>
V(sem)
V(sem)
……
……
例：大学校门处要求来客登记，只有一张登记表，登 记表同时只能由一个人使用，用P、V原语描述一个 校外人员进入大学的过程。
解：
1）设互斥信号量mutex，表示登记表是否正在使用
2）设mutex初始值为1，表示登记表没有人使用
3）描述：
Enter:
P(mutex)
//申请登记表
登记
V(mutex)
//释放登记表
同步例子
▪ 有A、B两进程，A进程从卡片机读信 息入缓冲区，B进程负责加工读进缓冲 区的卡片
▪ 解：设信号量S1：缓冲区中有否可供 加工的信息，初始值为0；信号量S2： 缓冲区是否为空，初始值为1。
执行getspace就是获取一 个空数据
release(ad) { toptop+1 ； stack[top]ad ； }
release(ad)就是释放一 个地址为ad的数据块
信号量：semaphore
▪ 是一个数据结构 ▪ 定义如下：
struct semaphore { int value; pointer_PCB queue; }
设有两个计算进程PA、PB共享内存MS。 其中MS分为三个领域，即系统区、进程 工作区和数据区。这里数据区被划分大 小相等的块，每个块中既可能放有数据， 也有可能未放有数据。系统区主要是堆 栈S，其中存放那些空数据块的地址。
如图所示：
getspace（） { int g;
gstack[top]; toptop-1; }
P： while (true) {
生产一个产品; P(s1) ; 送产品到缓冲区; V(s2); };
Q： while (true) { P(s2); 从缓冲区取产品; V(s1); 消费产品; };
S1初值为1，S2初值为0
放消息
P
取消息
Q