《计算机操作系统 》课件-3.4进程同步

3.4进程同步本节主要内容：进程同步的基本概念进程同步机制及应用经典进程同步问题管程机制Linux同步机制解析3.4进程同步3.4.1进程同步的基本概念

并发进程间的制约关系

进程同步与互斥的概念

临界资源、临界区的概念

同步机制应遵循的原则3.4进程同步3.4.1进程同步的基本概念1.并发进程间的间接制约关系与进程互斥：

间接制约关系：相互竞争资源

临界资源

一次仅允许一个进程使用的资源称为临界资源。硬件：如输入机、打印机、磁带机等软件：如公用变量、数据、表格、队列等

例1：两个进程共享一个变量x，设x的初值为10P1和P2两个进程都对共享变量x执行加1的操作：p1：r1:=x；r1:=r1+1；x:=r1

；p2：r2:=x；r2:=r2+1；x:=r2

；33

两种可能的执行次序：x=10A次序：

p1：r1:=x；r1:=r1+1；x:=r1；

p2：r2:=x；r2:=r2+1；x:=r2

；执行结果：

x=11B次序：

p1：r1:=x；r1:=r1+1；x:=r1

；

p2：r2:=x；r2:=r2+1；x:=r2

；执行结果：

x=121、并发进程间的间接制约关系与进程互斥

临界资源共享变量的修改冲突

例2：民航售票系统，n个售票处

/*ProcessPi,i=1,2,...,n*/…../*按订票要求找到数据库中的共享数据x[k]*//*x[k]存放某月某日某次航班的现有票数*/R=x[k];/*现有票数*/

if(R>=1){R--;

x[k]=R;

输出一张机票；

}else

显示“票已售完”；互斥：对某个临界资源，一个进程正在使用它，另外一个想用它的进程就必须等待，而不能同时使用；

x

:=x+1;

进程P1进程P2

x

:=x+1;

3.4.1进程同步的概念1.并发进程间的间接制约关系与进程互斥

临界区：进程中访问临界资源的一段代码。

临界区的互斥访问过程：

x

:=x+1;

csa{进程P1进程P2

x

:=x+1;

csb{entrysection进入区exitsection退出区

criticalsection(临界区）

remaindersection（剩余区）进程代码3.4.1进程同步的基本概念1、并发进程间的间接制约关系与进程互斥：3.4进程同步3.4.1进程同步的基本概念1.并发进程间的间接制约关系与进程互斥：同步机制应遵循的原则空闲让进：其他进程均不处于临界区；忙则等待：已有进程处于其临界区；

有限等待：等待进入临界区的进程不能"死等"；

让权等待：不能进入临界区的进程，应释放CPU（如转换到阻塞状态）3.4.1进程同步的基本概念2.并发进程间的直接制约关系与进程同步：相互协作，保证先后顺序例1：病人就诊：医生看病活动：初步诊断开出化验单；

依据化验结果继续诊病；化验员化验活动：进行化验；

开出化验结果；3.4进程同步例2：共享缓冲区的计算进程与打印进程的相互协作

计算进程cp和打印进程op公用一个单缓冲

单缓冲opcpABCDABCD3.4进程同步3.4.1进程同步的基本概念2.并发进程间的直接制约关系与进程同步：相互协作进程同步概念：并发进程在一些关键点上可能需要互相等待或互通消息，这种相互制约的等待或互通消息称为进程同步。

3.4进程同步3.4.2进程同步机制及应用

利用硬件方法解决进程互斥问题

禁止中断，TSL指令，swap指令

利用软件方法解决进程互斥问题

不正确的算法，Peterson算法，面包店算法

利用锁机制解决进程互斥问题

利用信号量机制解决进程同步与互斥问题

整形信号量、记录型信号量、信号量集机制

禁止中断

3.4进程同步3.4.2进程同步机制及应用1.利用硬件方法解决进程互斥问题禁止中断临界区开放中断剩余区缺点：可能增加系统风险只能用于单处理机系统

利用TSL指令实现互斥

检测并上锁指令3.4进程同步3.4.2进程同步机制及应用1.利用硬件方法解决进程互斥问题booleanTSL(boolean*lock){

booleanold;

old=*lock;*lock=TRUE;

returnold;}booleanlock=FALSE；Pi：{while(TSL(&lock))

;//donothing临界区

lock=FALSE;剩余区;}利用swap指令实现互斥：交换两个字的内容

3.4进程同步3.4.2进程同步机制及应用1.利用硬件方法解决进程互斥问题voidSwap(boolean*a,boolean*b){

booleantemp;

temp=*a;*a=*b;*b=temp;}booleanlock=FALSE；Pi：{booleankey=TRUE;

while(key==TRUE)

Swap(&lock,&key)；临界区

lock=FALSE;剩余区;}3.4进程同步3.4.2进程同步机制及应用2.利用软件方法实现互斥算法1：两个进程P0,P1共享某临界资源：设立一个公用整型变量turn，描述允许进入临界区的进程标识，假设初始化turn=0，表示首先轮到P0访问临界资源P0的代码：while(turn!=0);

临界区turn=1;

剩余区P1的代码：while(turn!=1);

临界区turn=0;剩余区违背了空闲让进、让权等待算法2：两个进程P0,P1共享某临界资源：设立一个标志数组flag[2]：描述进程是否已在临界区，初值均为0(FALSE)，表示进程都不在临界区。违背了忙则等待、让权等待P0:while(flag[1]);flag[0]=1;

临界区

flag[0]=0;

剩余区P1:while(flag[0]);flag[1]=1;

临界区

flag[1]=0;

剩余区3.4进程同步3.4.2进程同步机制及应用2.利用软件方法实现互斥3.4.2进程同步机制及应用2.利用软件算法实现互斥：

算法3：Peterson算法，两个进程P0,P1共享某临界资源

设立一个标志数组flag[2]：描述进程是否希望进入临界区，初值均为0(FALSE)，表示进程都不希望进入临界区。intturn=0,表示首先轮到P0进入临界区。P0:

flag[0]=1;turn=1;while(flag[1]&&turn==1);临界区

flag[0]=0;

剩余区P1:flag[1]=1;turn=0;while(flag[0]&&turn==0);临界区

flag[1]=0;

剩余区3.4进程同步如何实现n个进程间的互斥呢？3.4.2进程同步机制及应用2.利用软件算法实现互斥：

算法4：面包店算法

该算法由美国数学家LeslieLamport提出

面包店排队原则：按所取号码由小到大原则排队；号码相同时，按顾客名字的字典顺序排队。

每个进程设置一个唯一的编号Pi（i=0‥n-1）booleanchoosing[n]：表示进程是否正在取号，初值为Falseintnumber[n]：记录每个进程取到的号码，初值为03.4进程同步voidPi()（i=0‥n-1）{

while(true){

choosing[i]=True;//pi正在取号

number[i]=1+max(Number[1],...,Number[N]);//Pi取到的号码

choosing[i]=False;

for(j=0;j＜N;++j){

while(choosing[j]!=0);

while((number[j]!=0)&&

((number[j]＜number[i])||((number[j]=number[i])&&(j＜i)));//当多个进程取到同号时，保证编号小的进程优先进入临界区

}

临界区number[i]=0;

剩余区}}

算法4：面包店算法3.4.2进程同步机制及应用2.利用软件方法实现互斥

算法5：两个进程P0,P1共享某临界资源：设立一个标志数组flag[2]：描述进程是否希望进入临界区，初值均为0(FALSE)，表示进程都不希望进入临界区违背了空闲让进、有限等待、让权等待P0:flag[0]=1;while(flag[1]);临界区

flag[0]=0;

剩余区P1:flag[1]=1;while(flag[0]);临界区

flag[1]=0;

剩余区3.4进程同步分组讨论3.4.2进程同步机制及应用3.利用锁机制实现互斥什么是锁

用变量w代表某种资源的状态，w称为“锁”

。加锁原语和开锁原语3.4进程同步加锁原语

lock()

{test：if(w为1)gototest；

elsew=1；}∕*上锁*∕

开锁原语

unlock()

{w=0；}∕*开锁*∕使用方法intw=0;Pi(){while(True){lock(w);

临界区

unlock(w)

剩余区}3.4.2进程同步机制及应用4.信号量机制

整形信号量机制：

初始化操作：非负整数P原语操作：down()或wait()V原语操作：up()或signal()3.4进程同步wait(S){while(S≤0);//donothingS--;//S值减1}signal(S){S++;//S值加1}违背了“让权等待”准则3.4.2进程同步机制及应用4.信号量机制

记录型信号量机制：3.4进程同步typedefstruct{intvalue;/*信号量的值*/PCB*L;/*进程等待队列队首指针*/}semaphore;value:初始化为一个非负整数值，表示空闲资源总数－－若为非负值表示当前的空闲资源数，若为负值其绝对值表示当前等待临界资源的进程个数。L：初值为空3.4.2进程同步机制及应用4.信号量机制：

记录型信号量

3.4进程同步wait(S){S->value--;if(S->value<0)thensleep(S->L);}

signal(S){S->value++;if(S->value≤0)thenwakeup(S->L);}semaphore*S;3.4.2进程同步机制及应用4.信号量机制

信号量集机制：一次可申请多类资源；每类资源可申请多个3.4进程同步Swait(S1,t1,d1,S2,t2,d2,…,Sn,tn,dn){if(S1>=t1&&…&&Sn>=tn){for(i=1;i<=n;i++){Si=Si–di;}}else{

将当前进程阻塞到第一个Si<ti的信号量Si的阻塞队列中；}}3.4.2进程同步机制及应用4.信号量机制

信号量集机制：一次可申请多类资源；每类资源可申请多个3.4进程同步Ssignal(S1,d1,S2,d2,…,Sn,dn){for(i=1;i<=n;i++){Si=Si+di;

唤醒所有因S1～Sn而阻塞的进程，插入就绪队列；}}Swait(S，d，d)：表示每次申请d个资源Swait(S，1，1)：表示记录型信号量Swait(S，1，0)：可作为一个可控开关Swait(S1,1,1,S2,1,1,…,Sn,1,1)：表示AND型信号量二.进程同步机制及应用

4.信号量机制

利用信号量机制实现互斥：为临界资源设置一个互斥信号量mutex，初值为1：

semaphore

mutex=1在每个进程中将临界区代码置于wait(mutex)和signal(mutex)原语之间：

wait（mutex）临界区signal（mutex）剩余区3.4进程同步必须成对出现4.信号量机制

利用信号量机制实现进程互斥算法描述：3.4.2进程同步机制及应用semaphoremutex；voidmain(){mutex=1；∕*互斥信号量*∕parbegin(pa(),

pb());}

pa(){…wait(mutex)；csa

；signal(mutex)；

…}

pb(){…wait(mutex)；csb

；signal(mutex)；

…}

利用信号量机制实现互斥：

例1：两个进程共享一台打印机

semaphoremutex;main(){mutex=1；

parbegin(pa(),

pb();)}

pa(){

wait(mutex)；csa

；signal(mutex)；

}pb(){

wait(mutex)；csb；signal(mutex)；

}

4.信号量机制mutex=0mutex=-1Pb等待mutex=0唤醒Pbmutex=1打印机空闲3.4.2进程同步机制及应用wait(S){S->value--;if(S->value<0)thensleep(S->L);}Signal(S){S->value++;if(S->value≤0)thenwakeup(S->L);}例2：民航售票系统，n个售票处同时运行下面程序段进行售票parbeginprogrampi{

…R=x[k];/*现有票数*/

if(R>=1){R--;

x[k]=R;

输出一张机票；

}

else{显示“票已售完”；

}}4.信号量机制

利用信号量机制实现互斥：

semaphoremutex={1,NULL};

semaphoremutex={1,NULL};

parbeginprogrampi{

…

wait(mutex)；

R=x[k];/*现有票数*/

if(R>=1){R--;x[k]=R;

signal(mutex)；输出一张机票；

}

else{

显示“票已售完”；

}}

利用信号量机制实现互斥例2：民航售票系统，n个售票处同时运行下面程序段进行售票

算法1：

semaphoremutex={1,NULL};

parbeginprogrampi{………

wait(mutex)；

R=x[k];/*现有票数*/

if(R>=1){R--;x[k]=R;

signal(mutex)；输出一张机票；

}

else{

signal(mutex)；

显示“票已售完”；

}

}例2：民航售票系统，n个售票处同时运行下面程序段进行售票

算法2：

利用信号量机制实现互斥小组讨论：某超级市场，可容纳多人同时购物。入口处有足够的篮子，每个购物者可拿一只篮子入内购物。出口处结帐，并归还篮子（出、入口禁止多人同时通过）。出入口不在同一处。试用信号量机制实现购物者的同步算法。4.信号量机制简答思路：①所用信号量设置如下：2）互斥信号量mutex1，初值为1，用以保证同时只能有一个购物者进程进入入口拿起篮子3）互斥信号量mutex2，初值为1，用以保证同时只能有一个购物者进程进入出口结账归还篮子

利用信号量机制实现互斥Pi(){wait（mutex1）；从入口处进超市，并取一只篮子signal（mutex1）；

进超市内选购商品；wait（mutex2）；

到出口结帐，并归还篮子；signal（mutex2）；

从出口离开超市；

}②算法描述：

利用信号量机制实现互斥semaphoremutex1，mutex2；；∕*互斥信号量*∕voidmain(){mutex1=mutex2=1parbegin(pi());}

实现进程间相互合作的前驱后继关系思路描述：为一个同步关系设置一个同步信号量S，其初值为0：

semaphore

S=0

——表示消息前驱进程完成操作后执行signal(S)：表示发送消息后继进程开始操作前执行wait(S)：表示等待消息到达

3.4进程同步3.4.2进程同步机制及应用

4.信号量机制

利用信号量机制实现同步算法描述：Pa→Pb

semaphoreS；

main(){

S=0；

parbegin(pa(),pb())；}pa(){

完成前驱工作；signal(S)；

}

pb(){

wait(S)；执行后继工作

}

3.4进程同步3.4.2进程同步机制及应用

4.信号量机制

利用信号量机制实现同步例1：

I→C→PsemaphoreS1；semaphoreS2;main(){S1=0；

S2=0；

Parbegin(I(),

C(),P());

}I(){

完成输入；signal(S1)；}

C(){wait(S1)；完成计算；signal(S2)；

}

P()

{wait(S2)；完成打印；

}

3.4.2进程同步机制及应用

4.信号量机制

利用信号量机制实现同步wait(S){S->value--;if(S->value<0)thensleep(S->L);}Signal(S){S->value++;if(S->value≤0)thenwakeup(S->L);}例2：前驱图a,b,c,d,e,f,g:semaphore=0,0,0,0,0,0,0Parbegin(s1,s2,s3,s4,s5,s6);

s1:{s1;signal(a);signal(b);}

s2:{wait(a);s2;signal(c);signal(d);}

s3:{wait(b);s3;signal(e);}

s4:{wait(c);s4;signal(f);}

s5:{wait(d);s5;signal(g);}

s6:{wait(e);wait(f);wait(g);s6;}

3.4.2进程同步机制及应用

4.信号量机制

利用信号量机制实现同步abcdefgS1S2S3S4S5S6例3：一辆公共汽车上，司机和售票员进程的同步

program司机{启动车辆;正常行车；

到站停车；}program售票员{关闭车门;售票

打开车门;}

分析：同步关系：（1）售票员关闭车门→司机启动车辆（2）司机到站停车→售票员打开车门

信号量设置：semaphoredrive_sem={0,NULL};semaphoreconductor_sem={0,NULL};3.4.2进程同步机制及应用

4.信号量机制

利用信号量机制实现同步例3算法实现：

利用信号量机制实现同步semaphoredrive_sem={0,NULL};关闭车门→启动车辆semaphoreconductor_sem={0,NULL};到站停车→打开车门program司机{while(1){

wait(drive_sem)；等待关门

启动车辆;

正常行车；到站停车;

signal(conductor_sem)；

唤醒开门}}

program售票员{while(1){关闭车门;signal(drive_sem)；唤醒司机开车售票；

wait(conductor_sem)；

等待停车打开车门;}}（1）确定进程：包括进程的数量、进程的工作内容。（2）确定进程同步互斥关系：根据进程间是竞争临界资源还是相互合作处理上的前后关系，来确定进程间是互斥还是同步。（3）确定信号量：根据进程间的同步互斥关系确定信号量个数、含义、初始值，各进程需要对信号量进行的wait()/signal()操作。（4）用类程序语言描述算法。3.4进程同步3.4.2进程同步机制及应用

4.信号量机制

利用信号量机制解决进程同步与互斥问题的步骤：课堂分组讨论：计算进程cp和打印进程op公用一个单缓冲（一次只能放一个数据），cp不断的计算并将结果放入单缓冲中，op则不断从单缓冲中取出结果并打印。为了完成正确的计算与打印，试用信号量机制实现这两个进程的同步。

单缓冲区bufopcp3.4进程同步3.4.2进程同步机制及应用

4.信号量机制55程序main(){intsa=0；∕*表示buf中有无信息*∕

intsb=1；∕*表示buf中有无空位置*∕

parbegin(cp(),iop())；}cp()op(){

{while(计算未完成)

while(打印工作未完成){

{

得到一个计算结果；

wait(sa)；wait(sb)；

从缓冲区中取一数；将数送到缓冲区中；

signal(sb)；signal(sa)；从打印机上输出；

}

}}

}

单缓冲区bufiopcp生产者-消费者问题哲学家进餐问题读者-写者问题理发师问题3.4进程同步3.4.3经典进程同步问题1.生产者－消费者问题(theproducer-consumerproblem)问题描述：若干进程通过有限的共享缓冲区交换数据。其中，"生产者"进程不断写入，而"消费者"进程不断读出；共享缓冲区共有K个；任何时刻只能有一个进程可对共享缓冲区进行操作。0123…4K-13.4进程同步inout3.4.3经典进程同步问题1.生产者－消费者问题分析：确定进程：进程数量及工作内容；确定进程间的关系：

互斥：多个进程间互斥使用同一个缓冲池；

同步：当缓冲池空时，消费者必须阻塞等待；当缓冲池满时，生产者必须阻塞等待。设置信号量：Mutex：用于访问缓冲池时的互斥，初值是1Full：“满缓冲”数目，初值为0；Empty：“空缓冲"数目，初值为K。full+empty=K3.4.3经典进程同步问题＃defineK100

＃defineMAXLEN80typedefstruct{intnum;chararray[MAXLEN];}Message;semaphoremutex;semaphoreempty;

semaphorefull;Messagebuffers[K];

intin,out;

1.生产者－消费者问题算法描述：三.经典进程同步问题

voidmain(){mutex={1,NULL};empty={K,NULL};

full={0,NULL};

Messagebuffers[K];in=0;out=0;

parbegin(produceri,consumerj)}

生产者－消费者问题programproduceri{Messagep_puf;while(1){produceamessageinp_buf;

wait(empty)；

wait(mutex)；buffers[in]=p_bufin=(in+1)%K;

signal(mutex)；

signal(full)；}}3.4.3经典进程同步问题1.生产者－消费者问题programconsumerj{

Messagec_buf;while(1){

wait(full)；

wait(mutex)；

c_buf=buffers[out]；

out=(out+1)%K;

signal(mutex)；

signal(empty)；

consumethemessageinc_buf;}

}三.经典进程同步问题1.生产者－消费者问题

如果将消费者的两个wait()操作对调？生产者i

消费者j生产出一产品；

wait（full）；wait（empty

）；

wait（mutex）；wait（mutex

）

；从缓冲区取出一产品；将该产品放入缓冲区；

signal（mutex）；signal（mutex

）；

signal（empty）；

signal（full

）

；消费该产品；状态：mutex=1,full=0,empty=n

先执行消费者进程wait（mutex）;wait（full）；如果将消费者的两个signal()操作对调？生产者i

消费者j生产出一产品；wait（full）；wait（empty）；wait（mutex）；wait（mutex）；从缓冲区取出一产品；将该产品放入缓冲区；signal（mutex）；signal（mutex）；signal（empty）；

signal（full）；消费该产品；signal(empty);Signal(mutex);1.生产者－消费者问题思考：请举出一个计算机系统中可以用生产者-消费者问题描述的实际例子2.哲学家进餐问题问题描述：有五个哲学家坐在一张圆桌旁，在圆桌上有五个盘子有五只筷子，他们的生活方式就是交替地进行思考和进餐。平时，一个哲学家进行思考，饥饿时取其左右两只筷子，只有拿到这两只筷子时才能进餐；进餐完毕，放下筷子继续思考。筷0筷1筷4筷2筷3制约关系：只有拿到两只筷子时,哲学家才能吃饭。

如果筷子已被别人拿走,则必须等别人吃完之后才能拿到筷子。3.4.3经典进程同步问题

programphilosopher（i）{thinking…

wait(chopstick[i])；

wait(chopstick[(i+1)mod5]);eating;

signal(chopstick[i])；

signal(chopstick[(i+1)mod5]);

}

2.哲学家进餐问题算法描述1：

semaphorechopstick[0…4];筷0筷1筷4筷2筷3voidmain(){chopstick[0…4]={1,NULL};parbegin(philosopher(i));}programphilosopher(i){wait(sm)；

wait(chopstick[i])；

wait(chopstick[(i+1)mod5]);eating;

signal(chopstick[i])；

signal(chopstick[(i+1)mod5]);

signal(sm)；}算法描述2：筷筷筷筷筷semaphorechopstick[0…4];

semaphoresm;voidmain(){chopstick[0…4]={1,NULL};

sm={4,NULL};parbegin(philosopher(i));}2.哲学家进餐问题思考：请举出一个计算机系统中可以用哲学家进程问题描述的实际例子3.读者-写者问题(thereaders-writersproblem)问题描述：

有多个读者进程和多个写者进程共享一数据。要求多进程对共享数据进行读写操作时，任一时刻“写者”最多只允许一个，而“读者”则允许多个，即：当有写者在写数据时，其他写者和读者必须等待；

当有读者在读数据时，其他写者必须等待；但其他读者可以同时读数据。

3.4进程同步3.4.3经典进程同步问题3.读者－写者问题(thereaders-writersproblem)问题分析及信号量设置：信号量wmutex表示“允许写”，写者与其他进程互斥使用数据公共整形变量Readcount表示“正在读”的读者数信号量Rmutex：实现多个读者对Readcount的互斥操作

wmutex:semaphore=1//读者与写者之间、写者与写者之间互斥使用共享数据readcount:int=0;//当前正在读的读者数量

rmutex:semaphore=1//多个读者互斥使用readcount3.4.3经典进程同步问题3.读者－写者问题算法描述：semaphorewmutex,rmutex;intreadcount;voidmain(){wmutex=1;rmutex=1;readcount=0;

parbegin(writeri,readerj);}voidwriteri{while(1){

writing…

}}wait(wmutex);signal(wmutex);voidreaderj{while(1){

wait(rmutex)ifreadcount=0thenwait

(wmutex);readcount++;

signal(rmutex);

reading…

wait

(rmutex);readcount--;ifreadcount=0thensignal(wmutex);

signal(rmutex);}}3.读者－写者问题读者优先的读者-写者算法：3.读者－写者问题共享数据R1W1R2R3写者优先的读者-写者算法：写进程与其他所有进程互斥允许多个读者同时读

写者优先于读者（一旦有写者，则后续读者必须等待；若同时有读者和写者在等待，唤醒时优先考虑写者）

semaphore

wmutex=1//读者与写者之间、写者与写者之间互斥使用共享数据SemaphoreS=1//当至少有一个写者准备访问共享数据时，它可使后续的读者等待写完成SemaphoreS2＝1//阻塞第二个以后的等待读者intReadcount,writecount=0,0;//当前读者数量、写者数量Semaphoremutex1=1//多个读者互斥使用readcountSemaphoremutex2=1//多个写者互斥使用writecount算法描述：写者优先的读者－写者问题算法Reader(){while(1){

wait(S2);

wait(S);wait(mutex1)

ifreadcount=0thenwait(wmutex);readcount++;

signal(mutex1);signal(S);signal(S2);

reading…

wait(mutex1);

readcount--;

ifreadcount=0thensignal(wmutex);

signal(mutex1);

}}写者优先的读者－写者问题算法算法描述：voidwriter(){while(1)wait(mutex2);ifwritecount=0thenwait(S);writecount++;signal（mutex2）;wait(wmutex);writing…signal(wmutex);wait(mutex2);writecount--;ifwritecount=0thensignal(S);signal（mutex2）;}}写者优先的读者－写者问题算法5.理发师问题问题描述：

理发店里有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子（等候椅）。如果没有顾客，理发师便在理发椅上睡觉；第一个顾客到来时，他必须叫醒理发师；若理发师正在理发时又有顾客到达，则如果有空等候椅，顾客就坐下来等待，如果满座了就离开理发店。理发店问题经常被用来模拟各种排队情形。3.4进程同步3.4.3经典进程同步问题5.理发师问题算法描述：intwaiting;semaphorecust_ready,finished,mutex,chair;voidmain(){waiting=0;cust_ready=finished=0;mutex=chair=1;

parbegin(barber,customer-i);}

3.4.3经典进程同步问题Cust_ready:理发椅上的顾客数Finished:顾客是否已完成理发mutex:互斥访问waitingchair:空闲的理发椅数量表示坐在等候椅上的顾客数5.理发师问题voidbarber(){do{wait(cust_ready);cut_hair;signal（finished);}while(1);}3.4.3经典进程同步问题voidcustomer-i(){wait(mutex)；if(waiting<n){waiting=waiting+1;signal(mutex);}}else{signal(mutex)；

离开理发店；return;}wait(chair);sit_in_chair;wait(mutex)；waiting=waiting-1;signal(mutex);signal(cust_ready);get-haircut;wait(finished);stand_from_chair;signal(chair);}例1：

桌上有个只能盛得下一个水果的空盘子。爸爸可向盘中放苹果或桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定：当盘子空时，一次只能放入一个水果供吃者取用。试用信号量的PV操作实现爸爸、儿子和女儿这三个循环进程之间的同步。

所用信号量设置如下：

Ⅰ）同步信号量empty，初值为1，表示盘子是空的，即儿子或女儿已把盘中的水果取走。

Ⅱ）同步信号量orange，初值为0，表示爸爸尚未把桔子放入盘中。

Ⅲ）同步信号量apple，初值为0，表示爸爸尚未把苹果放入盘中。3.4进程同步3.4.3经典进程同步问题

算法同步描述：

爸爸进程（P）：

儿子进程（C1）：

女儿进程（C2）：P（empty）；

P（orange）；

P（apple）；将水果放入盘中；

从盘中取出桔子；

从盘中取出苹果；若放入的是桔子，

V（empty）；

V（empty）；则V（orange）；吃桔子；

吃苹果；否则，V（apple）；3.4经典进程同步问题：小组讨论：桌子上有一个空盘子，最多允许存放两只水果，但一次只能一个人操作盘子（往盘子中放水果或从盘子中取水果），爸爸可以向盘中放苹果，妈妈向盘子中放橘子，女儿专门吃盘子中的苹果，儿子专门吃盘子中的橘子。请用信号量实现他们之间的同步与互斥关系。S:semaphore=2;盘子开始可以放两只水果Mutex:semaphore=1;互斥使用盘子S1:semaphore=0;是否有苹果S2:semaphore=0;是否有橘子3.4经典进程同步问题：ProcessFather:Begin:

L1:P(S);

P（mutex）

PutApple;

V(mutex);

V(S1)；

GOTOL1；

End；ProcessMother:Begin:L2:P(S);P（mutex）

PutOrange;

V(S2)；

V(mutex);

GOTOL2；End；ProcessSon:

Begin:

L3:P(S2);P（mutex）

GetOrange;V(mutex);

V(S)；

GOTOL1；

End；ProcessDaughter:Begin:L4:P(S1);P（mutex）GetApple;V(mutex);V(S)；GOTOL4；End；锁机制、专用指令等存在“忙等”现象由用户编写同步控制代码：加重了用户负担！各同步原语操作分散在用户程序中，系统无法有效地控制和管理；

用户编程时若使用wait()/signal()操作不当，后果严重（死锁）基于以上情况，1971年DIjkstra提出了“秘书进程”思想。1973年Hansan和Hoare又将“秘书进程”思想发展为“管程”概念，把并发进程间的同步操作分别集中在相应的管程中。3.4进程同步3.4.4管程机制1.管程的引人：前述互斥手段的不足：一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据3.4.4管程机制2.管程的定义：管程组成：管程名字局部于管程的共享变量的说明；对该数据结构进行操作的一组过程；初始化局部变量的语句。局部数据条件变量过程1过程n出口变量初始化代码管程入口等待调用进程队列3.4.4管程机制2.管程的定义管程特性：信息隐蔽性

任一时刻，管程中只能有一个活跃进程3.条件变量每个独立的条件变量是和进程需要等待的某种原因（或说条件）相联系的，当定义一个条件变量时，系统就建立一个相应的等待队列。关于条件变量的操作：C.wait:阻塞调用进程，并使管程可用；C.signal:唤醒相应条件变量上的等待进程。Java:wait(),notify()C#:monitor.wait(),monitor.pulse()3.条件变量引入条件变量后的一个可能问题：进程Q执行C.wait()阻塞；进程P执行C.signal()唤醒进程Q后，管程中有两个活跃进程问题：解决方法：P等待，直到Q退出管程或等待另一个条件Q等待，直到P退出管程或等待另一个条件Hanson采用了折中的方法:规定C.signal()为过程体最后一个操作，当进程P执行完毕后，P退出管程，另一个进程Q执行。typePC=monitor in,out,count:int;

buffer[N]:item; notfull,notempty:condition; procedureput(item)

procedureget(item){

{if(count==N)then

if(count=0)then

notfull.wait();notempty.wait();buffer(in)=item;

nextc=buffer(out);in=(in+1)modN;out=(out+1)modN;count=count+1;

count=count-1;

notempty.signal();notfull.signal();}

}Beginin=out=count=0;end3.4.4管程机制5.利用管程解决生产者--消费者问题

PC管程定义：procedureproducer

procedureconsumer{

{while(true)

while(true){

{produceranitem;

PC.get(item);PC.put(item);

consumetheitem;}

}}

}

monitor.enter;PC.put(item);monitor.leave;3.4.4管程机制5.利用管程解决生产者--消费者问题生产者及消费者算法描述：3.4.4管程机制思考题：3.4进程同步3.4.5Linux同步机制解析内核程序使用的同步机制原子操作

自旋锁

读-写自旋锁

内核信号量

读-写信号量用户程序使用的同步机制IPC信号量（system信号量）POSIX信号量

有名信号量，无名信号量原子整数操作：主要用于实现计数器

原子操作可以保证指令以原子的方式被执行，两个原子操作绝对不可能同时访问同一个变量。

typedefstruct{

volatileintcounter; }atomic_t;3.4进程同步3.4.5Linux同步机制解析1.原子操作volatile提醒编译器它所定义的变量随时都有可能改变，因此编译后的程序每次需要访问该变量时，都会直接从变量地址中读取数据，而不是从寄存器中。1.原子操作原子整数操作操作功能说明ATOMIC_INIT(i）声明一个atomic_t变量，并初始化为iatomic_read(&v)返回v的值atomic_set(&v,i)把v置为iatomic_add(i,&v)把v增加iatomic_sub(i,&v)对v减iatomic_sub_and_test(i,&v)对v减i，如果结果为0则返回1；否则返回0atomic_inc(&v)对v加1atomic_dec(&v)对v减1atomic_dec_and_test(&v)对v减1，如果结果为0则返回1；否则返回0atomic_inc_and_test(&v)对v加1，如果结果为0则返回1；否则返回03.4.5Linux同步机制解析原子位操作：

include/asm-x86/bitops_32.h针对“位”这一级数据的一组原子操作接口。格式如：set_bit(intnr,void*addr)3.4进程同步3.4.5Linux同步机制解析1.原子操作要操作的位号指向要操作的数据的指针概念：自旋锁最多只能被一个内核任务持有；在短期间内进行轻量级的锁定；自旋锁不允许任务睡眠；自旋锁是专为防止多处理器并发而引入的一种锁3.4进程同步3.4.5Linux同步机制解析2.自旋锁定义：typedefstruct{volatile

unsigned

int

lock;}spinlock_t;3.4进程同步3.4.5Linux同步机制解析2.自旋锁操作函数：操作接口功能描述DEFINE_SPINLOCK(lock)申明一个自旋锁lock，并置为开锁状态spin_lock_init(spinlock_t*)初始化指定的自旋锁，置为开锁状态spin_lock(spinlock_t*)获取指定的自旋锁spin_unlock(spinlock_t*)释放已获得的指定自旋锁spin_lock_irq(spinlock_t*)