计算机操作系统（第二版）课件：进程同步机制及应用

进程同步机制及应用

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

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

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

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

禁止中断

3.4进程同步3.4.2进程同步机制及应用1.利用硬件方法解决进程互斥问题禁止中断临界区开放中断剩余区缺点：可能增加系统风险只能用于单处理机系统CPU在两个进程之间切换必须在中断处理协助下才能实现为什么多处理机系统中这个方法不能实现互斥？openEuler中断控制arch_local_irq_disable()arch_local_irq_enable()arch/arm64/include/asm/irqflags.h

利用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;剩余区;}违背了让权等待原则利用swap指令实现互斥：交换两个字的内容

3.4进程同步3.4.2进程同步机制及应用1.利用硬件方法解决进程互斥问题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.利用软件方法实现互斥这个算法是否遵循了同步机制的4条准则？如果没有，违背了哪些准则？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进程同步违背了让权等待原则这个算法是否遵循了同步机制的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进程同步这个算法是否遵循了同步机制的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进程同步机制及应用3.利用锁机制实现互斥3.4进程同步3.4.2进程同步机制及应用4.信号量机制

整形信号量机制：3.4进程同步荷兰计算机科学家Dijkstra提出的。你还在哪里学习过Dijkstra的理论或观点呢？你还了解Dijkstra的哪些事迹呢？图灵奖计算机科学教育杰出贡献奖ACMPODC最具影响力论文奖结构程序之父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}违背了“让权等待”准则是否遵循了4个准则？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;如果现在value的值小于0，那么在执行减1操作前，value的最大值只可能是多少？如果用value的值表示可用资源数量，那么现在系统中是否还有空闲资源供分配呢？如果现在value的值小于等于0，那么在执行加1操作前，value的最大值只可能是多少？那么现在系统中是否有其他进程因为申请不到信号量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的阻塞队列中；}}使用时，有一个隐含条件：ti≥di3.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型信号量这个可以用在什么场合下呢？能实现什么功能呢？3.4.2进程同步机制及应用4.信号量机制

信号量集机制：一次可申请多类资源；每类资源可申请多个对信号量X执行P操作时，若（）则进程进入等待状态X-1＜0X-1≤0X-1＞0X-1≥0ABCD提交单选题10分若信号量S的初值为2，当前值为-2，则表示有（）等待进程。0234ABCD提交单选题10分3.4.2进程同步机制及应用

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

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

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

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

signal(basket);从出口离开超市；

}小组讨论分析思路semaphorebasket，mutex1，mutex2voidmain(){mutex1=mutex2=1，basket=200parbegin(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);}重点分析S2节点与S6节点的算法，为什么是这样写的？例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）确定进程：包括进程的数量