第二章 进程 管理 (2)
第二章 进程管理 ( 2 )
2.4 进程同步
2.5 管程机制
2.6 进程通信
2.4 进程的同步
在多道程序系统中，由于资源共享或进程合作，使进程间形成间接相互制约和直接相互制约关系，这需要用进程互斥与同步机制来协调两种制约关系。
进程同步的主要任务是使并发执行的进程间有效的共享资源和相互合作，
进程的同步机制 ── 信号量及 P.V操作
（解决进程同步互斥问题）
直接作用 (相互合作）：
进程间的相互联系是有意识的安排的，
直接作用只发生在相交进程间间接作用 （资源共享）：
进程间要通过某种中介发生联系，是无意识安排的，可发生在相交进程之间，也可发生在无关进程之间
1,进程间的关系相互感知程度 交互关系 一个进程对其他进程 的影响相互不感知 (完全不了解其它进程的存在 )
竞争 (competition) 一个进程的操作对其他进程的结果无影响间接感知 (双方都与第三方交互，如共享资源 )
通过共享进行协作 一个进程的结果依赖于从其他进程获得的信息直接感知 (双方直接交互，如通信 )
通过通信进行协作 一个进程的结果依赖于从其他进程获得的信息
2,进程的同步（直接作用）
指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。 具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪状态由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥。
临界资源,
系统中某些资源一次只允许一个进程使用，
称这样的资源为临界资源或互斥资源或共享变量
3,进程的互斥（间接作用）
4,基本概念
进程互斥,指在多道程序环境下,每次只允许一个进程对临界资源进行访问 。
进程同步,指多个相关进程在执行次序上的协调 。
临界资源,一次仅供一个进程使用的资源。
在进程中涉及到临界资源的程序段叫 临界区
多个进程的临界区称为 相关临界区程序 段 1 程序 段 2 程序 段 n
共 享 变量
5.使用互斥区的原则
空闲让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入
忙则等待：不允许两个以上的进程同时进入互斥区
有限等待：任何进入互斥区的要求应在有限的时间内得到满足
让权等待：处于等待状态的进程应放弃占用 CPU，以使其他进程有机会得到 CPU
的使用权使用互斥区的原则：
前提：任何进程无权停止其它进程的运行进程之间相对运行速度无硬性规定进程互斥的解决有两种做法,
由竞争各方平等协商
引入进程管理者，由管理者来协调竞争各方对互斥资源的使用具体方法：
硬件（当一个进程进入临界区,就屏蔽所有中断，但成本高）
软件（用编程解决，但常常忙等待）
6.进程互斥的软件方法
通过平等协商方式实现进程互斥的最初方法是软件方法
其基本思路是在进入区检查和设置一些标志，如果已有进程在临界区，则在进入区通过循环检查进行等待；在退出区修改标志
其中的主要问题是设置什么标志和如何检查标志软件解法的缺点：
1,忙等待
2,实现过于复杂
3,需要高的编程技巧软件解法 (1)
free,表示临界区标志
true,有进程在临界区
false:无进程在临界区 (初值 )
....
while (free);
free = false;
临界区
free = true;
软件解法 (2)
turn,true P进入临界区
false Q进入临界区
....
P,while (not turn);
临界区
turn = false;
Q,while (turn);
临界区
turn = true;
软件解法 (3)
pturn,qturn,初值为 false
P进入临界区的条件,pturn∧ not qturn
Q进入临界区的条件,not pturn∧ qturn
P,..,Q,....
pturn = true; pturn = true;
while (qturn); while (pturn);
临界区 临界区
pturn = false; qturn = false;
...,..
硬件解法 (1)
,测试并设置”指令
boolean TS (boolean
*lock)
{
boolean old;
old = *lock;
*lock = true;
}
while TS(&lock);
临界区
lock＝ false;
硬件解法 (2)
,交换”指令
void SWAP(int *a,int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
key = true;
do
{
SWAP(&lock,key);
}while(key);
临界区
lock:=false;
硬件解法 (3)
,开关中断”指令进入临界区前执行：
执行“关中断”指令离开临界区后执行：
执行“开中断”指令
7 进程的同步机制 ──
信号量及 P.V操作（解决进程同步）
同步机制：
信号量及 P,V操作；管程；条件临界域；路径表达式等（用于集中式系统中）
会合；通信顺序进程；分布进程；远程过程调用等（适用于分布式系统中）
描述能力
可以实现
效 率 高
使用方便
1) 同步机制应满足的基本要求
2)解决互斥的锁机制
实现互斥的一种软件方法是采用 锁机制,即提供一对上锁 (Lock)和开锁 (UnLock)原语,以及一个锁变量 W。
进程进入临界区前,通过锁变量来判断临界资源是否被占用 。
3) 信号量机制
信号量机制是一种卓有成效的进程同步工具,被广泛应用于单处理机和多处理机系统,以及计算机网络中 。
锁机制仅能表示,开,与,关,两种状态；
开,关锁原语必须作为原子操作来进行；
关锁原语言中反复测试Ｗ状态,浪费了处理机的时间；锁机制只能解决互斥,不能用于同步 。 信号量同步机制能完满地解决上述问题 。
信号量,semaphore
是一个数据结构
定义如下：
struc semaphore
{
int value;
pointer_PCB queue;
}
信号量说明：
semaphore s;
P操作
P(s)
{
s.value = s.value --;
if (s.value < 0)
{
该进程状态置为等待状态将该进程的 PCB插入相应的等待队列末尾
s.queue;
}
}
Ｐ操作
意味着请求分配一个单位资源
V操作
V(s)
{
s.value = s.value ++;
if (s.value < = 0)
{
唤醒相应等待队列 s.queue中等待的一个进程改变其状态为就绪态并将其插入就绪队列
}
}
Ｖ操作
意味着释放一个单位资源
P,V操作为原语操作原语,是由若干多机器指令构成的完成某种特定功能的一段程序，具有不可分割性。即原语的执行必须是连续的，在执行过程中不允许被中断实现：开关中断信号量的使用,
必须置一次且只能置一次初值初值不能为负数只能执行 P,V操作用 P,V操作解决进程间互斥问题
P(mutex)
V(mutex)
P1 P2 P3
互斥区
P(mutex)
P(mutex)
V(mutex)
V(mutex)
互斥例子
三个进程共用两个 I/O缓冲区 。
解：设用信号量 S表示共享资源,S
初始值为 2
同步例子
有 A,B两进程,A进程从卡片机读信息入缓冲区,B进程负责加工读进缓冲区的卡片
解：设信号量 S1：缓冲区中有否可供加工的信息,初始值为 0；信号量 S2：缓冲区是否为空,初始值为 1。
同步例子（续）
在输入进程 A中,可以把 P(S2)调到
V(S1)后面,而把信号量 S2的初始值设为 0。
用 P-V操作描述前趋关系的例子
信号量还可以描述程序或语句之间的前趋关系 。
用 P-V操作描述前趋关系（续）
描述如下：
Var a,b,c,d,e,f,g,semaphore,=0,0,0,0,0，
0,0；
begin
parbegin
begin S1； V(a)； V(b)； end；
begin P(a)； S2； V(c)； V(d)； end；
begin P(b)； S3； V(e)； end；
begin P(c)； S4； V(f)； end；
begin P(d)； S5； V(g)； end；
begin P(e)； P(f)； P(g)； S6； end；
parend
end
经典的生产者 ─ 消费者问题消费者生产者经典的生产者 ─ 消费者问题同步问题：
P进程不能往,满,的缓冲区中放产品，设置信号量为 S1
Q进程不能从,空,的缓冲区中取产品，设置信号量 S2
S1初值为 1,S2初值为 0
P,Q：
while (true) { while (true) {
生产一个产品 ; P(s2);
P(s1) ; 从缓冲区取产品 ;
送产品到缓冲区 ; V(s1);
V(s2); 消费产品 ;
}; };
...
...
P Q
放消息 取消息
n
n 个缓冲区
(Buffer)
i
j
生产者 -消费者问题
生产者－消费者 (Producer-Consumer)问题是著名的进程同步问题 。 它描述一组生产者向一组消费者提供消息,它们共享一个有界缓冲池,生产者向其中投放消息,消费者从中取得消息 。 以下用信号量解决生产者－消费者问题 。
假设缓冲池中有 n个缓冲区,每个缓冲区存放一个消息,可利用互斥信号量 mutex使诸进程对缓冲池实现互斥访问；利用 empty和 full计数信号量分别表示空缓冲及满缓冲的数量 。 又假定这些生产者和消费者互相等效,只要缓冲池未满,生产者可将消息送入缓冲池；只要缓冲池未空,消费者可从缓冲池取走一个消息 。
生产者 -消费者问题（续）
其中,mutex,empty,full的初始值分别为 1,n,0；
P操作的顺序可换吗？
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操作无关紧要
P.V操作的优缺点
P.V操作优点：
简单，而且表达能力强 （用 P.V操作可解决任何同步互斥问题）
缺点：
“不够安全； P.V操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂
8.信号量集 —— AND型信号量集
AND型信号量集是指同时需要多种资源且每种占用一个时的信号量操作
AND型信号量集的基本思想,在一个原语中申请整段代码需要的多个临界资源，
要么全部分配给它，要么一个都不分配
AND型信号量集 P原语为 Swait
AND型信号量集 V原语为 Ssignal
Swait(S1,S2,…,Sn) //P原语；
{
while (TRUE) {
if (S1 >=1 && S2 >= 1 && … && Sn >= 1)
{ //满足资源要求时的处理；
for (i = 1; i <= n; ++i) -–Si;
//注：与 P的处理不同，这里是在确信可满足
// 资源要求时，才进行减 1操作；
break;
}
else { //某些资源不够时的处理；
调用进程进入第一个小于 1信号量的等待队列
Sj.queue;
阻塞调用进程 ;
}
Ssignal(S1,S2,…,Sn)
{
for (i = 1; i <= n; ++i)
{
++Si; //释放占用的资源；
for (在 Si.queue中等待的每一个进程 P)
//检查每种资源的等待队列的所有进程；
{
从等待队列 Si.queue中取出进程 P;
if (判断进程 P是否通过 Swait中的测试 )
//注：与 signal不同，这里要进行重新判断；
{//通过检查（资源够用）时的处理；
进程 P进入就绪队列 ;
}
else
{//未通过检查（资源不够用）时的处理；
进程 P进入某等待队列；
}
}
}
}
9,一般,信号量集,
一般信号量集是指同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的信号量处理
一般信号量集的基本思路就是在
AND型信号量集的基础上进行扩充，
在一次原语操作中完成所有的资源申请。
进程对信号量 Si的测试值为 ti（表示信号量的判断条件，要求
Si >= ti；即当资源数量低于 ti时，便不予分配）
占用值为 di（表示资源的申请量，即 Si = Si
- di）
对应的 P,V原语格式为：
–Swait(S1,t1,d1;,..; Sn,tn,dn);
–Ssignal(S1,d1;,..; Sn,dn);
一般“信号量集”可以用于各种情况的资源分配和释放，几种特殊情况：
Swait(S,d,d)表示每次申请 d个资源，当少于 d个时，便不分配
Swait(S,1,1)表示互斥信号量
Swait(S,1,0)可作为一个可控开关（当
S?1时，允许多个进程进入临界区；当
S=0时，禁止任何进程进入临界区）
【 思考题 】
1.用 P.V操作解决下图之同步问题,
get copy put
f s t g
用 P.V操作解决司机与售票员的问题司机进程：
while
(true){
启动车辆正常驾驶到站停车
}…
售票员进程：
while
(true){
关门售票开门
}…
10,经典问题
1)读者写者问题有两组并发进程,
读者和写者,共享一组数据区要求：
允许多个读者同时执行读操作不允许读者、写者同时操作不允许多个写者同时操作第一类：读者优先如果读者来：
1）无读者、写者，新读者可以读
2）有写者等，但有其它读者正在读，则新读者也可以读
3）有写者写，新读者等如果写者来：
1）无读者，新写者可以写
2）有读者，新写者等待
3）有其它写者，新写者等待第一类读者写者问题的解法读者：
while (true) {
P(mutex);
readcount ++;
if (readcount==1)
P (w);
V(mutex);
读
P(mutex);
readcount --;
if (readcount==0)
V(w);
V(mutex);
};
写者：
while (true) {
P(w);
写
V(w);
};
第一类读者写者问题的解法
（一般信号量集）
读者：
swait(wmutex,1,1;
rcount,R,0);
写；
ssignal(wmutex,1);
写者：
swait(rcount,1,1;
wmutex,1,0);
写；
ssignal(rcount,1);
2)哲学家就餐问题有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子每个哲学家的行为是思考，感到饥饿，
然后吃通心粉为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子
#define N 5
void philosopher (int i) {
while (true) {
思考；
取 fork[i]; 取 fork[(i+1) % 5]；
进食；
放 fork[i]; 放 fork[(i+1) % 5]；
}
}
为防止死锁发生可采取的措施：
最多允许 4个哲学家同时坐在桌子周围
仅当一个哲学家左右两边的筷子都可用时，
才允许他拿筷子（?）
给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之为了避免死锁，把哲学家分为三种状态，思考，饥饿，进食，并且一次拿到两只筷子，
否则不拿
3)第二类读者写者问题：
写者优先条件：
1）多个读者可以同时进行读
2）写者必须互斥（只允许一个写者写，也不能读者写者同时进行）
3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）
第二章 进程管理
2.5 管程机制
1,管程的提出采用 P-V同步机制来编写并发程序，对于共享变量及信号量变量的操作将被分散于各个进程中缺点：
（１）易读性差，因为要了解对于一组共享变量及信号量的操作是否正确，则必须通读整个系统或者并发程序
（２）不利于修改和维护，因为程序的局部性很差，
所以任一组变量或一段代码的修改都可能影响全局
（３）正确性难以保证，因为操作系统或并发程序通常很大，要保证这样一个复杂的系统没有逻辑错误是很难的
2.管程概念
概念：指关于共享资源的数据及在其上操作的一组过程或共享数据结构及其规定的所有操作 。
系统按资源管理的观点分解成若干模块,用数据表示抽象系统资源,同时分析了共享资源和专用资源在管理上的差别,按不同的管理方式定义模块的类型和结构,使同步操作相对集中,
从而增加了模块的相对独立性 。
3.管程的组成管程的四个组成部分：
名称
数据结构说明
对该数据结构进行操作的一组过程 /函数
初始化语句局部于管程的数据结构,仅被局部于管程的过程访问 。 局部于管程的过程,也仅能访问管程内的数据结构 。
管程 （ 相当于围墙 ） 把共享变量和对它进行操作的若干过程围起来 。
管程：一种同步机制系统按资源管理的观点分解成若干模块，用数据表示抽象系统资源，
同时分析了共享资源和专用资源在管理上的差别，按不同的管理方式定义模块的类型和结构，使同步操作相对集中，从而增加了模块的相对独立性管程的形式
TYPE monitor_name = MONITOR;
共享变量说明
define 本管程内所定义、本管程外可调用的过程
（函数）名字表
use 本管程外所定义、本管程内将调用的过程（函数）名字表
PROCEDURE 过程名（形参表）；
过程局部变量说明；
BEGIN
语句序列；
END;
......
FUNCTION 函数名（形参表）：值类型；
函数局部变量说明；
BEGIN
语句序列；
END;
......
BEGIN
共享变量初始化语句序列；
END;
模块化,一个管程是一个基本程序单位，可以单独编译
抽象数据类型,管程是一种特殊的数据类型，其中不仅有数据，而且有对数据进行操作的代码
信息掩蔽,管程是半透明的，管程中的外部过程（函数）实现了某些功能，
管程中的外部过程（函数）实现了某些功能，至于这些功能是怎样实现的，在其外部则是不可见的
4.管程的三个主要的特性
管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的外部过程（函数）来间接地访问管程中的共享变量
为了保证管程共享变量的数据完整性，规定管程互斥进入
管程通常是用来管理资源的，因而在管程中应当设有进程等待队以及相应的等待及唤醒操作
5.管程的要素问题：多个进程出现在管程中当一个进入管程的进程执行等待操作时，
它应当释放管程的互斥权；当一个进入管程的进程执行唤醒操作时（如Ｐ唤醒Ｑ），管程中便存在两个同时处于活动状态的进程处理方法有三种：
Ｐ等待Ｑ继续，直到Ｑ退出或等待
Ｑ等待Ｐ继续，直到Ｐ等待或退出
规定唤醒为管程中最后一个可执行的操作因为管程是互斥进入的，所以当一个进程试图进入一个巳被占用的管程时它应当在管程的入口处等待，因而在管程的入口处应当有一个进程等待队列，称作入口等待队列如果进程Ｐ唤醒进程Ｑ，则Ｐ等待Ｑ继续，如果进程Ｑ在执行又唤醒进程Ｒ，则Ｑ
等待Ｒ继续,……,如此，在管程内部，由于执行唤醒操作，可能会出现多个等待进程，
因而还需要有一个进程等待队列，这个等待队列被称为紧急等待队列。它的优先级应当高于入口等待队列的优先级由于管程通常是用于管理资源的，因而在管程内部，应当存在某种等待机制。当进入管程的进程因资源被占用等原因不能继续运行时使其等待。为此在管程内部可以说明和使用一种特殊类型的变量，称作条件变量：
VAR C:condition;
对于条件型变量，可以执行 wait和 signal操作：
wait（ c）：如果紧急等待队列非空，则唤醒第一个等待者；否则释放管程的互斥权，执行此操作的进程的 PCB入 c链尾部
signal（ c）：如果 c链为空，则相当于空操作，
执行此操作的进程继续；否则唤醒第一个等待者，执行此操作的进程的 PCB入紧急等待队列的尾部两个主要途径：
直接构造 (效率高 )
间接构造，即用某种已经实现的同步机制去构造例子：用 P-V操作构造管程
6,管程的实现
(1）设置进程和管程的目的不同
（ 2）系统管理数据结构进程,PCB
管程：等待队列
（ 3）管程被进程调用
（ 4）管程是操作系统的固有成分，
无创建和撤消
7.管程和进程的异同点第二章 进程管理
2.6 进程通信
1.进程通信概述
P.V操作实现的是进程之间的低级通讯，所以 P.V为低级通讯原语。它只能传递简单的信号，不能传递交换大量信息
如果要在进程间传递大量信息则要用
Send / Receive原语（高级通讯原语）
2.实现进程通信的方式
共享存储器方式：相互通信的进程通过共享某些数据结构或存储区来进行通信,可分为共享数据结构方式,共享存储区方式；
消息通信方式：进程间的消息交换以消息或报文为单位,程序员利用一组通信命令
(原语 )来实现通信,可分为直接,间接通信方式；
共享文件方式：利用共享文件来实现进程间的通信 。
3.管道 通信
在 UNIX系统中,利用一个打开的共享文件来连接两个相互通信的进程,
该共享文件称为管道 (Pipe),因而该方式又称为管道通信 。
为了协调双方通信,管道通信必须提供三方面的协调能力：互斥,同步,对方是否存在 。
4.消息传递模式系统为进程提供了两个高级通讯原语 send和 receive。要进行消息传递时执行 send,当接收者要接收消息时执行
receive
消息缓冲：在内存中开设缓冲区，发送进程将消息送入缓冲区，接收进程接收传递来的缓冲区
信箱通信
5.直接方式共享文件模式：管道通信发送进程发消息时要指定接收进程的名字，
反过来，接收时要指明发送进程的名字
Send(receiver,message)
Receiver(sender,message)
对称形式：一对一
非对称形式：多对一 （顾客 /服务员）
有缓冲（有界，无界），无缓冲直接通信方式直接通信方式模型
6.消息缓冲（ 有界缓冲区）
在操作系统空间设置一组缓冲区，当发送进程需要发送消息时，执行 send系统调用，产生自愿性中断，
进入操作系统，操作系统为发送进程分配一个空缓冲区，并将所发送的消息从发送进程 copy到缓冲区中，
然后将该载有消息的缓冲区连接到接收进程的消息链链尾，如此就完成了发送过程。发送进程返回到用户态继续执行。
在以后某个时刻，当接收进程执行到 receive接收原语时，也产生自愿性中断进入操作系统，由操作系统将载有消息的缓冲区从消息链中取出，并把消息内容 copy到接收进程空间，之后收回缓冲区，如此就完成了消息的接收，接收进程返回到用户态继续进行。
直接通信方式实例－消息缓冲通信
消息缓冲数据结构 （ 下图 ）
此外,进程的 PCB块中增加一些数据项以支持消息缓冲区的通信机制实现；如,mq，
消息链首指针； mutex,消息链互斥信号量； Sm,消息链同步计数信号量 。
sender 消息发送者
size 消息长度
text 消息正文
next 指向下一个消息缓冲区的指针两个进程利用消息缓冲区通信过程发送原语接收原语
7.间接方式发送进程发消息时不指定接收进程的名字，而是指定一个中间媒介，即信箱。进程间通过信箱实现通信发送原语,send(MB,Message)
接收原语,receive(MB,Message)
信箱通信
信箱组成信箱说明 与 信箱体可存放信件数，已存放信件数，指针
信箱使用规则
1）若发送信件时信箱已满，则发送进程被置为“等信箱”状态，直到信箱有空时才被释放
2）若取信件时信箱中无信，则接收进程被置为“等信件”状态，直到有信件时才被释放
send（ N,M）：把信件 M送到指定的信箱 N中
receive（ N,X）：从指定信箱 N中取出一封信，存放到指定的地址 X中
8.管道通信方式 Pipe
也称共享文件方式，基于文件系统，利用一个打开的共享文件连接两个相互通信的进程，
文件作为缓冲传输介质发送进程 接收进程字符流方式写入读出先进先出顺序综合实例
设某台机挂有两个 I/O通道：分别挂一台输入机和一台打印机 。 卡片机上有一叠数据卡片,现在要把这些数据逐一输入到缓冲区 B1,然后再复制到缓冲区 B2,并在打印机上打印出来 。
问,系统可设哪些进程来完成这个任务？
用 P-V原语写这些进程的同步算法 。
综合实例（续）
解：由上图可见,系统可设 3个进程：输入进程,
复制进程,打印进程；分别用进程 R,进程 C,进程 P来表示 。
这些进程之间的相互制约关系：
R受 C的约束； C受 R,P的约束； P受 C的约束 。
设 4个信号量,S1=1,S2=0,S3=1,S4=0
同步算法如下：
第二章 进程管理 ( 2 )
2.4 进程同步
2.5 管程机制
2.6 进程通信
2.4 进程的同步
在多道程序系统中，由于资源共享或进程合作，使进程间形成间接相互制约和直接相互制约关系，这需要用进程互斥与同步机制来协调两种制约关系。
进程同步的主要任务是使并发执行的进程间有效的共享资源和相互合作，
进程的同步机制 ── 信号量及 P.V操作
（解决进程同步互斥问题）
直接作用 (相互合作）：
进程间的相互联系是有意识的安排的，
直接作用只发生在相交进程间间接作用 （资源共享）：
进程间要通过某种中介发生联系，是无意识安排的，可发生在相交进程之间，也可发生在无关进程之间
1,进程间的关系相互感知程度 交互关系 一个进程对其他进程 的影响相互不感知 (完全不了解其它进程的存在 )
竞争 (competition) 一个进程的操作对其他进程的结果无影响间接感知 (双方都与第三方交互，如共享资源 )
通过共享进行协作 一个进程的结果依赖于从其他进程获得的信息直接感知 (双方直接交互，如通信 )
通过通信进行协作 一个进程的结果依赖于从其他进程获得的信息
2,进程的同步（直接作用）
指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。 具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪状态由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥。
临界资源,
系统中某些资源一次只允许一个进程使用，
称这样的资源为临界资源或互斥资源或共享变量
3,进程的互斥（间接作用）
4,基本概念
进程互斥,指在多道程序环境下,每次只允许一个进程对临界资源进行访问 。
进程同步,指多个相关进程在执行次序上的协调 。
临界资源,一次仅供一个进程使用的资源。
在进程中涉及到临界资源的程序段叫 临界区
多个进程的临界区称为 相关临界区程序 段 1 程序 段 2 程序 段 n
共 享 变量
5.使用互斥区的原则
空闲让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入
忙则等待：不允许两个以上的进程同时进入互斥区
有限等待：任何进入互斥区的要求应在有限的时间内得到满足
让权等待：处于等待状态的进程应放弃占用 CPU，以使其他进程有机会得到 CPU
的使用权使用互斥区的原则：
前提：任何进程无权停止其它进程的运行进程之间相对运行速度无硬性规定进程互斥的解决有两种做法,
由竞争各方平等协商
引入进程管理者，由管理者来协调竞争各方对互斥资源的使用具体方法：
硬件（当一个进程进入临界区,就屏蔽所有中断，但成本高）
软件（用编程解决，但常常忙等待）
6.进程互斥的软件方法
通过平等协商方式实现进程互斥的最初方法是软件方法
其基本思路是在进入区检查和设置一些标志，如果已有进程在临界区，则在进入区通过循环检查进行等待；在退出区修改标志
其中的主要问题是设置什么标志和如何检查标志软件解法的缺点：
1,忙等待
2,实现过于复杂
3,需要高的编程技巧软件解法 (1)
free,表示临界区标志
true,有进程在临界区
false:无进程在临界区 (初值 )
....
while (free);
free = false;
临界区
free = true;
软件解法 (2)
turn,true P进入临界区
false Q进入临界区
....
P,while (not turn);
临界区
turn = false;
Q,while (turn);
临界区
turn = true;
软件解法 (3)
pturn,qturn,初值为 false
P进入临界区的条件,pturn∧ not qturn
Q进入临界区的条件,not pturn∧ qturn
P,..,Q,....
pturn = true; pturn = true;
while (qturn); while (pturn);
临界区 临界区
pturn = false; qturn = false;
...,..
硬件解法 (1)
,测试并设置”指令
boolean TS (boolean
*lock)
{
boolean old;
old = *lock;
*lock = true;
}
while TS(&lock);
临界区
lock＝ false;
硬件解法 (2)
,交换”指令
void SWAP(int *a,int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
key = true;
do
{
SWAP(&lock,key);
}while(key);
临界区
lock:=false;
硬件解法 (3)
,开关中断”指令进入临界区前执行：
执行“关中断”指令离开临界区后执行：
执行“开中断”指令
7 进程的同步机制 ──
信号量及 P.V操作（解决进程同步）
同步机制：
信号量及 P,V操作；管程；条件临界域；路径表达式等（用于集中式系统中）
会合；通信顺序进程；分布进程；远程过程调用等（适用于分布式系统中）
描述能力
可以实现
效 率 高
使用方便
1) 同步机制应满足的基本要求
2)解决互斥的锁机制
实现互斥的一种软件方法是采用 锁机制,即提供一对上锁 (Lock)和开锁 (UnLock)原语,以及一个锁变量 W。
进程进入临界区前,通过锁变量来判断临界资源是否被占用 。
3) 信号量机制
信号量机制是一种卓有成效的进程同步工具,被广泛应用于单处理机和多处理机系统,以及计算机网络中 。
锁机制仅能表示,开,与,关,两种状态；
开,关锁原语必须作为原子操作来进行；
关锁原语言中反复测试Ｗ状态,浪费了处理机的时间；锁机制只能解决互斥,不能用于同步 。 信号量同步机制能完满地解决上述问题 。
信号量,semaphore
是一个数据结构
定义如下：
struc semaphore
{
int value;
pointer_PCB queue;
}
信号量说明：
semaphore s;
P操作
P(s)
{
s.value = s.value --;
if (s.value < 0)
{
该进程状态置为等待状态将该进程的 PCB插入相应的等待队列末尾
s.queue;
}
}
Ｐ操作
意味着请求分配一个单位资源
V操作
V(s)
{
s.value = s.value ++;
if (s.value < = 0)
{
唤醒相应等待队列 s.queue中等待的一个进程改变其状态为就绪态并将其插入就绪队列
}
}
Ｖ操作
意味着释放一个单位资源
P,V操作为原语操作原语,是由若干多机器指令构成的完成某种特定功能的一段程序，具有不可分割性。即原语的执行必须是连续的，在执行过程中不允许被中断实现：开关中断信号量的使用,
必须置一次且只能置一次初值初值不能为负数只能执行 P,V操作用 P,V操作解决进程间互斥问题
P(mutex)
V(mutex)
P1 P2 P3
互斥区
P(mutex)
P(mutex)
V(mutex)
V(mutex)
互斥例子
三个进程共用两个 I/O缓冲区 。
解：设用信号量 S表示共享资源,S
初始值为 2
同步例子
有 A,B两进程,A进程从卡片机读信息入缓冲区,B进程负责加工读进缓冲区的卡片
解：设信号量 S1：缓冲区中有否可供加工的信息,初始值为 0；信号量 S2：缓冲区是否为空,初始值为 1。
同步例子（续）
在输入进程 A中,可以把 P(S2)调到
V(S1)后面,而把信号量 S2的初始值设为 0。
用 P-V操作描述前趋关系的例子
信号量还可以描述程序或语句之间的前趋关系 。
用 P-V操作描述前趋关系（续）
描述如下：
Var a,b,c,d,e,f,g,semaphore,=0,0,0,0,0，
0,0；
begin
parbegin
begin S1； V(a)； V(b)； end；
begin P(a)； S2； V(c)； V(d)； end；
begin P(b)； S3； V(e)； end；
begin P(c)； S4； V(f)； end；
begin P(d)； S5； V(g)； end；
begin P(e)； P(f)； P(g)； S6； end；
parend
end
经典的生产者 ─ 消费者问题消费者生产者经典的生产者 ─ 消费者问题同步问题：
P进程不能往,满,的缓冲区中放产品，设置信号量为 S1
Q进程不能从,空,的缓冲区中取产品，设置信号量 S2
S1初值为 1,S2初值为 0
P,Q：
while (true) { while (true) {
生产一个产品 ; P(s2);
P(s1) ; 从缓冲区取产品 ;
送产品到缓冲区 ; V(s1);
V(s2); 消费产品 ;
}; };
...
...
P Q
放消息 取消息
n
n 个缓冲区
(Buffer)
i
j
生产者 -消费者问题
生产者－消费者 (Producer-Consumer)问题是著名的进程同步问题 。 它描述一组生产者向一组消费者提供消息,它们共享一个有界缓冲池,生产者向其中投放消息,消费者从中取得消息 。 以下用信号量解决生产者－消费者问题 。
假设缓冲池中有 n个缓冲区,每个缓冲区存放一个消息,可利用互斥信号量 mutex使诸进程对缓冲池实现互斥访问；利用 empty和 full计数信号量分别表示空缓冲及满缓冲的数量 。 又假定这些生产者和消费者互相等效,只要缓冲池未满,生产者可将消息送入缓冲池；只要缓冲池未空,消费者可从缓冲池取走一个消息 。
生产者 -消费者问题（续）
其中,mutex,empty,full的初始值分别为 1,n,0；
P操作的顺序可换吗？
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操作无关紧要
P.V操作的优缺点
P.V操作优点：
简单，而且表达能力强 （用 P.V操作可解决任何同步互斥问题）
缺点：
“不够安全； P.V操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂
8.信号量集 —— AND型信号量集
AND型信号量集是指同时需要多种资源且每种占用一个时的信号量操作
AND型信号量集的基本思想,在一个原语中申请整段代码需要的多个临界资源，
要么全部分配给它，要么一个都不分配
AND型信号量集 P原语为 Swait
AND型信号量集 V原语为 Ssignal
Swait(S1,S2,…,Sn) //P原语；
{
while (TRUE) {
if (S1 >=1 && S2 >= 1 && … && Sn >= 1)
{ //满足资源要求时的处理；
for (i = 1; i <= n; ++i) -–Si;
//注：与 P的处理不同，这里是在确信可满足
// 资源要求时，才进行减 1操作；
break;
}
else { //某些资源不够时的处理；
调用进程进入第一个小于 1信号量的等待队列
Sj.queue;
阻塞调用进程 ;
}
Ssignal(S1,S2,…,Sn)
{
for (i = 1; i <= n; ++i)
{
++Si; //释放占用的资源；
for (在 Si.queue中等待的每一个进程 P)
//检查每种资源的等待队列的所有进程；
{
从等待队列 Si.queue中取出进程 P;
if (判断进程 P是否通过 Swait中的测试 )
//注：与 signal不同，这里要进行重新判断；
{//通过检查（资源够用）时的处理；
进程 P进入就绪队列 ;
}
else
{//未通过检查（资源不够用）时的处理；
进程 P进入某等待队列；
}
}
}
}
9,一般,信号量集,
一般信号量集是指同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的信号量处理
一般信号量集的基本思路就是在
AND型信号量集的基础上进行扩充，
在一次原语操作中完成所有的资源申请。
进程对信号量 Si的测试值为 ti（表示信号量的判断条件，要求
Si >= ti；即当资源数量低于 ti时，便不予分配）
占用值为 di（表示资源的申请量，即 Si = Si
- di）
对应的 P,V原语格式为：
–Swait(S1,t1,d1;,..; Sn,tn,dn);
–Ssignal(S1,d1;,..; Sn,dn);
一般“信号量集”可以用于各种情况的资源分配和释放，几种特殊情况：
Swait(S,d,d)表示每次申请 d个资源，当少于 d个时，便不分配
Swait(S,1,1)表示互斥信号量
Swait(S,1,0)可作为一个可控开关（当
S?1时，允许多个进程进入临界区；当
S=0时，禁止任何进程进入临界区）
【 思考题 】
1.用 P.V操作解决下图之同步问题,
get copy put
f s t g
用 P.V操作解决司机与售票员的问题司机进程：
while
(true){
启动车辆正常驾驶到站停车
}…
售票员进程：
while
(true){
关门售票开门
}…
10,经典问题
1)读者写者问题有两组并发进程,
读者和写者,共享一组数据区要求：
允许多个读者同时执行读操作不允许读者、写者同时操作不允许多个写者同时操作第一类：读者优先如果读者来：
1）无读者、写者，新读者可以读
2）有写者等，但有其它读者正在读，则新读者也可以读
3）有写者写，新读者等如果写者来：
1）无读者，新写者可以写
2）有读者，新写者等待
3）有其它写者，新写者等待第一类读者写者问题的解法读者：
while (true) {
P(mutex);
readcount ++;
if (readcount==1)
P (w);
V(mutex);
读
P(mutex);
readcount --;
if (readcount==0)
V(w);
V(mutex);
};
写者：
while (true) {
P(w);
写
V(w);
};
第一类读者写者问题的解法
（一般信号量集）
读者：
swait(wmutex,1,1;
rcount,R,0);
写；
ssignal(wmutex,1);
写者：
swait(rcount,1,1;
wmutex,1,0);
写；
ssignal(rcount,1);
2)哲学家就餐问题有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子每个哲学家的行为是思考，感到饥饿，
然后吃通心粉为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子
#define N 5
void philosopher (int i) {
while (true) {
思考；
取 fork[i]; 取 fork[(i+1) % 5]；
进食；
放 fork[i]; 放 fork[(i+1) % 5]；
}
}
为防止死锁发生可采取的措施：
最多允许 4个哲学家同时坐在桌子周围
仅当一个哲学家左右两边的筷子都可用时，
才允许他拿筷子（?）
给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之为了避免死锁，把哲学家分为三种状态，思考，饥饿，进食，并且一次拿到两只筷子，
否则不拿
3)第二类读者写者问题：
写者优先条件：
1）多个读者可以同时进行读
2）写者必须互斥（只允许一个写者写，也不能读者写者同时进行）
3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）
第二章 进程管理
2.5 管程机制
1,管程的提出采用 P-V同步机制来编写并发程序，对于共享变量及信号量变量的操作将被分散于各个进程中缺点：
（１）易读性差，因为要了解对于一组共享变量及信号量的操作是否正确，则必须通读整个系统或者并发程序
（２）不利于修改和维护，因为程序的局部性很差，
所以任一组变量或一段代码的修改都可能影响全局
（３）正确性难以保证，因为操作系统或并发程序通常很大，要保证这样一个复杂的系统没有逻辑错误是很难的
2.管程概念
概念：指关于共享资源的数据及在其上操作的一组过程或共享数据结构及其规定的所有操作 。
系统按资源管理的观点分解成若干模块,用数据表示抽象系统资源,同时分析了共享资源和专用资源在管理上的差别,按不同的管理方式定义模块的类型和结构,使同步操作相对集中,
从而增加了模块的相对独立性 。
3.管程的组成管程的四个组成部分：
名称
数据结构说明
对该数据结构进行操作的一组过程 /函数
初始化语句局部于管程的数据结构,仅被局部于管程的过程访问 。 局部于管程的过程,也仅能访问管程内的数据结构 。
管程 （ 相当于围墙 ） 把共享变量和对它进行操作的若干过程围起来 。
管程：一种同步机制系统按资源管理的观点分解成若干模块，用数据表示抽象系统资源，
同时分析了共享资源和专用资源在管理上的差别，按不同的管理方式定义模块的类型和结构，使同步操作相对集中，从而增加了模块的相对独立性管程的形式
TYPE monitor_name = MONITOR;
共享变量说明
define 本管程内所定义、本管程外可调用的过程
（函数）名字表
use 本管程外所定义、本管程内将调用的过程（函数）名字表
PROCEDURE 过程名（形参表）；
过程局部变量说明；
BEGIN
语句序列；
END;
......
FUNCTION 函数名（形参表）：值类型；
函数局部变量说明；
BEGIN
语句序列；
END;
......
BEGIN
共享变量初始化语句序列；
END;
模块化,一个管程是一个基本程序单位，可以单独编译
抽象数据类型,管程是一种特殊的数据类型，其中不仅有数据，而且有对数据进行操作的代码
信息掩蔽,管程是半透明的，管程中的外部过程（函数）实现了某些功能，
管程中的外部过程（函数）实现了某些功能，至于这些功能是怎样实现的，在其外部则是不可见的
4.管程的三个主要的特性
管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的外部过程（函数）来间接地访问管程中的共享变量
为了保证管程共享变量的数据完整性，规定管程互斥进入
管程通常是用来管理资源的，因而在管程中应当设有进程等待队以及相应的等待及唤醒操作
5.管程的要素问题：多个进程出现在管程中当一个进入管程的进程执行等待操作时，
它应当释放管程的互斥权；当一个进入管程的进程执行唤醒操作时（如Ｐ唤醒Ｑ），管程中便存在两个同时处于活动状态的进程处理方法有三种：
Ｐ等待Ｑ继续，直到Ｑ退出或等待
Ｑ等待Ｐ继续，直到Ｐ等待或退出
规定唤醒为管程中最后一个可执行的操作因为管程是互斥进入的，所以当一个进程试图进入一个巳被占用的管程时它应当在管程的入口处等待，因而在管程的入口处应当有一个进程等待队列，称作入口等待队列如果进程Ｐ唤醒进程Ｑ，则Ｐ等待Ｑ继续，如果进程Ｑ在执行又唤醒进程Ｒ，则Ｑ
等待Ｒ继续,……,如此，在管程内部，由于执行唤醒操作，可能会出现多个等待进程，
因而还需要有一个进程等待队列，这个等待队列被称为紧急等待队列。它的优先级应当高于入口等待队列的优先级由于管程通常是用于管理资源的，因而在管程内部，应当存在某种等待机制。当进入管程的进程因资源被占用等原因不能继续运行时使其等待。为此在管程内部可以说明和使用一种特殊类型的变量，称作条件变量：
VAR C:condition;
对于条件型变量，可以执行 wait和 signal操作：
wait（ c）：如果紧急等待队列非空，则唤醒第一个等待者；否则释放管程的互斥权，执行此操作的进程的 PCB入 c链尾部
signal（ c）：如果 c链为空，则相当于空操作，
执行此操作的进程继续；否则唤醒第一个等待者，执行此操作的进程的 PCB入紧急等待队列的尾部两个主要途径：
直接构造 (效率高 )
间接构造，即用某种已经实现的同步机制去构造例子：用 P-V操作构造管程
6,管程的实现
(1）设置进程和管程的目的不同
（ 2）系统管理数据结构进程,PCB
管程：等待队列
（ 3）管程被进程调用
（ 4）管程是操作系统的固有成分，
无创建和撤消
7.管程和进程的异同点第二章 进程管理
2.6 进程通信
1.进程通信概述
P.V操作实现的是进程之间的低级通讯，所以 P.V为低级通讯原语。它只能传递简单的信号，不能传递交换大量信息
如果要在进程间传递大量信息则要用
Send / Receive原语（高级通讯原语）
2.实现进程通信的方式
共享存储器方式：相互通信的进程通过共享某些数据结构或存储区来进行通信,可分为共享数据结构方式,共享存储区方式；
消息通信方式：进程间的消息交换以消息或报文为单位,程序员利用一组通信命令
(原语 )来实现通信,可分为直接,间接通信方式；
共享文件方式：利用共享文件来实现进程间的通信 。
3.管道 通信
在 UNIX系统中,利用一个打开的共享文件来连接两个相互通信的进程,
该共享文件称为管道 (Pipe),因而该方式又称为管道通信 。
为了协调双方通信,管道通信必须提供三方面的协调能力：互斥,同步,对方是否存在 。
4.消息传递模式系统为进程提供了两个高级通讯原语 send和 receive。要进行消息传递时执行 send,当接收者要接收消息时执行
receive
消息缓冲：在内存中开设缓冲区，发送进程将消息送入缓冲区，接收进程接收传递来的缓冲区
信箱通信
5.直接方式共享文件模式：管道通信发送进程发消息时要指定接收进程的名字，
反过来，接收时要指明发送进程的名字
Send(receiver,message)
Receiver(sender,message)
对称形式：一对一
非对称形式：多对一 （顾客 /服务员）
有缓冲（有界，无界），无缓冲直接通信方式直接通信方式模型
6.消息缓冲（ 有界缓冲区）
在操作系统空间设置一组缓冲区，当发送进程需要发送消息时，执行 send系统调用，产生自愿性中断，
进入操作系统，操作系统为发送进程分配一个空缓冲区，并将所发送的消息从发送进程 copy到缓冲区中，
然后将该载有消息的缓冲区连接到接收进程的消息链链尾，如此就完成了发送过程。发送进程返回到用户态继续执行。
在以后某个时刻，当接收进程执行到 receive接收原语时，也产生自愿性中断进入操作系统，由操作系统将载有消息的缓冲区从消息链中取出，并把消息内容 copy到接收进程空间，之后收回缓冲区，如此就完成了消息的接收，接收进程返回到用户态继续进行。
直接通信方式实例－消息缓冲通信
消息缓冲数据结构 （ 下图 ）
此外,进程的 PCB块中增加一些数据项以支持消息缓冲区的通信机制实现；如,mq，
消息链首指针； mutex,消息链互斥信号量； Sm,消息链同步计数信号量 。
sender 消息发送者
size 消息长度
text 消息正文
next 指向下一个消息缓冲区的指针两个进程利用消息缓冲区通信过程发送原语接收原语
7.间接方式发送进程发消息时不指定接收进程的名字，而是指定一个中间媒介，即信箱。进程间通过信箱实现通信发送原语,send(MB,Message)
接收原语,receive(MB,Message)
信箱通信
信箱组成信箱说明 与 信箱体可存放信件数，已存放信件数，指针
信箱使用规则
1）若发送信件时信箱已满，则发送进程被置为“等信箱”状态，直到信箱有空时才被释放
2）若取信件时信箱中无信，则接收进程被置为“等信件”状态，直到有信件时才被释放
send（ N,M）：把信件 M送到指定的信箱 N中
receive（ N,X）：从指定信箱 N中取出一封信，存放到指定的地址 X中
8.管道通信方式 Pipe
也称共享文件方式，基于文件系统，利用一个打开的共享文件连接两个相互通信的进程，
文件作为缓冲传输介质发送进程 接收进程字符流方式写入读出先进先出顺序综合实例
设某台机挂有两个 I/O通道：分别挂一台输入机和一台打印机 。 卡片机上有一叠数据卡片,现在要把这些数据逐一输入到缓冲区 B1,然后再复制到缓冲区 B2,并在打印机上打印出来 。
问,系统可设哪些进程来完成这个任务？
用 P-V原语写这些进程的同步算法 。
综合实例（续）
解：由上图可见,系统可设 3个进程：输入进程,
复制进程,打印进程；分别用进程 R,进程 C,进程 P来表示 。
这些进程之间的相互制约关系：
R受 C的约束； C受 R,P的约束； P受 C的约束 。
设 4个信号量,S1=1,S2=0,S3=1,S4=0
同步算法如下：
