使用P_V操作解决经典进程同步问题

第21卷第2期

2005年4月商丘师范学院学报JOURNALOFSHANGQIUTEACHERSCOLLEGEVol.21No.2April,2005

使用P、V操作解决经典进程同步问题

朱敬鹏,乔丽,王铁柱112

(1.商丘师范学院计算机科学系,河南商丘476000;2.商丘市有线电视台,河南商丘476000)

　　摘　要:简要介绍P、V操作.通过对两个经典同步问题的描述,说明如何使用P、V操作解决实际问题,重点简述了使用信号量机制解决同步问题时容易产生死锁的原因以及解决死锁的方法.

关键词:信号量;同步;死锁;临界资源

中图分类号:TP316　　　　　文献标识码:A　　　　　文章编号:1672-3600(2005)02-0095-03

UsetheP.Voperationtosolveclassicalprocesssynchronizationproblem

ZHUJing-peng1;QIAOLi1;WANGTie-Zhu2

(1.Dept.ofComputer,ShangqiuTeachersCollege,Shangqiu476000,China;2.CAVofShangqiu,Shangqiu476000,China)Abstract:ThebriefintroductionoftheP.Voperationismadeasbelow.Byanalysingthetwoclassicalprocesssynchronization,howtosolvethepracticalproblemsbyapplyingP.Voperationisindicated,emphaticallyillustratingboththereasonofdeadlockeasilyoccurredwhenapplyingthesignalquantitysystemandtheapproachestocopewithdeadlockaswell.

Keywords:semaphores;synchronization;deadlock;criticalresource

在操作系统中引入进程后,由于进程的异步性,可能会有多个进程在同一个时间间隔内并发执行,尤其是并发进程竞争临界资源时,就可能会给系统造成混乱.当多个进程需要合作完成一项任务,又要求它们能正确地执行,不会出现死锁时,这种问题我们称之为进程同步问题.生产者-消费者问题,哲学家共进餐问题是典型的进程同步问题.在现代操作系统中,通常都采用P、V操作来解决进程同步问题.

1　P、V操作的描述

1965年,荷兰学者Dijkstra提出的信号量机制,这就是一种卓有成效的进程同步工具,可以有效地解决进程同步问题.该机制中,采用了记录型的数据结构,它所包含的两个数据项可以描述为:

typesemaphore=record

value:integer;

L:listofprocess;

End

相应地:P、V操作可以描述为:

P:procedurewait(S)　　　　　　　　　　　　V:proceduresignal(S)

　　　varS:semaphore;

　　　begin

　　　　S.value:=S.value-1;

　　　　ifS.value

　　　end　　　end

其中,S.value的初值表示系统中某类资源的数目,因而又称为资源信号量.对它每次执行P操作,意味着进程请求一个单位的某类资源,因此描述为S.value;=S.value-1;当S.value

96商丘师范学院学报　　　　　　　　　　　　　　　　　2005年　value+1;若执行S.value:=S.value+1操作后仍是S.value≤0,则表示在该信号量链表中,仍有等待该资源的进程被阻塞,故应调用wakeup原语将S.L中的第一个等待进程唤醒.

2　生产者-消费者问题

2.1　问题描述

有一批生产者进程在生产产品,并将这些产品提供给消费者进程消费.为使生产者进程和消费者进程能并发执行,在两者之间设置一个具有N个缓冲区的缓冲池,生产者进程将它生产的产品放入一个缓冲区中;消费者进程可以从一个缓冲区中取走产品去消费.它们之间必须保持同步,既不允许消费者进程到一个空缓冲区去取产品,也不允许生产者进程向一个已经装满产品且未被取走的缓冲区中投放产品.

可以利用一个数组来表示一个具有N个缓冲区的缓冲池.用一个输入指针in指示下一个可以投放产品的缓冲区,用一个输出指针out指示下一个可以从中获取产品的缓冲区.用一个整型变量count表示满缓冲区的个数.两个进程共享下列变量:

varn,integer;

typeitem=…;

varbuffer:array[0,1,…,n-1]ofitem;

in,out;0,1,…,n-1;

count:0,1,…,n;

假定在生产者和消费者之间的缓冲池中,具有N个缓冲区,可以利用一个互斥信号量mutex实现各进程对缓冲池的互斥使用;利用信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量.对生产者消费者问题可以描述如下:

varmutex,empty,full:semaphore:=1,n,0;

　buffer:array[0,…,n-1]ofitem;

　in,out:integer:=0,0;

　begin

　　生产者:begin

　repeat

　　…

　生产一个产品投入变量nextp;

　　…

　p(mutex);……………………(A)

　p(empty);……………………(B)

　buffer(in):=nextp;

　in:=(in+1)modn;

　v(full);…………………………(A)

　v(mutex);………………………(B)

　untilfalse;

end

　　消费者:begin

　repeat

　　p(mutex);…………………(A)

　　p(full);……………………(B)

　　nextc:=buffer(out);

　　out:=(out+1)modn;

　　v(empty);……………………(A)

　　v(mutex);……………………(B)

　　从nextc中取一个产品;

　　untilfalse;

end

　end

2.2　出现的问题以及解决方法:首先,和v(成对出现;,

和full的p、v操作同样必须成对出现,但他们分别处于不同的程序中.另外,虽然从表面上看,上述程序不仅可以使用信号量mutex实现生产者和消费者互斥地访问缓冲池,而且可以实现同步,但是却可能出现死锁如:当生产者申请mutex并成功,此时mutex的值将变为0,当生产者继续执行p(empty)时,如果此时缓冲池已满,则没有空缓冲区,此时生产者应阻塞,此时,消费者应可以取产品,但是由于生产者阻塞,且mutex已经为0,所以消费者也阻塞,双方都阻塞———死锁.解决方法是:将上述程序中的所有相邻(A)和(B)互换顺序.

3　哲学家进餐问题

3.1　问题描述

有5个哲学家共用一张圆桌,分别坐在周围的5张椅子上,在圆桌上有5个碗和5只筷子,他们的生活方式是交替地进行思考和吃饭.平时,一个哲学家进行思考,饥饿时便试图取用其左右最靠近他的筷子,只有在他拿到两只筷子时才能吃饭,吃完后放下筷子继续思考.

分析可知,筷子是临界资源,5个哲学家需要互斥地对其进行访问,即在同一时刻只允许一个哲学家使用,若用一个信号量表示一个筷子,则可以使用一个数组来描述这5只筷子:

　varchopstick:array[0,…,4]ofsemaphore;所有信号均被初始化为1,第i位哲学家的活动可描述为:

repeat

　　P(chopstick[i]);

　　P(chopstick[i+1]mod5);

　　　…

　　eat;

　　　…

　　V(chopstick[i]);

　　V(chopstick[i+1]mod5);

　　　…

　think;

　untilfalse;

3.2　出现的问题以及解决方法

从上面程序中可以看出,当哲学家饥饿时,总是先拿左边筷子(P(chopstick[i])),成功后才会去拿右边筷子P(chopstick[i+1]mod5),然后才吃饭.虽然该程序可以保证相邻两个哲学家不会同时吃饭,但可能引起死锁,假如5位哲学家同时拿起左手筷子,会使5个chopstick信号量全变为0;当他们试图去取右边筷子时,都因为拿不到而全部等待—死锁.对于这个死锁问题,可以采用下述方法解决:至多只允许4位哲学家同时进餐,这样便可以保证有一个哲学家能够进餐,并在进餐结束后释放他用过的筷子,从而使更多的哲学家可以进餐.具体实现时,可以在上述程序的基础上加以修改,增设一个信号量max,用于控制同时进餐的哲学家的个数,值为4,并将P(max)操作放在两个P操作之前,将(max)操作放在两个V操作之后即可.修改后的程序如下:

repeat

　　P(max);

　　P(chopstick[i]);

　　P(chopstick[i+1]mod5);

　　　…

　　eat:

　　　…

　　V(chopstick[i]);

　　V(chopstick[i+1]mod5);

　　V(max);

　　…

　　think;

untilfalse;

这样,既可以保证相邻两个哲学家不会同时吃饭,又可以保证不会产生死锁,因为不会出现5个哲学家同时吃饭.

(下转第109页)

催化剂的回收参照文献[7]的方法进行,将回收所得的催化剂经过适当的处理后,在上述考察所得的优化条件下重复实验,平均收率仍达到84%.

2.7　产品检测与分析

使用Nicolet公司70SXFT-IR型红外光谱仪对制备的乙酸环己酯产品进行了测定,特征峰分别为2940、2859cm(C—O—C对称伸缩振动),产品的折光率n20.4442(文献值为1.4440).D=1-1(—CH2—伸缩振动),1726cm-1(C=O),14452cm-1(—CH2—弯曲振动),1192cm-1(C—O—C不对称伸缩振动),1018cm-1

3　结论

(1)超声波振荡法制备Ti(OH)4并合成纳米固载型多酸催化剂HPA/TiO2-WO3,比已报道的合成该类型催化剂的周期明显缩短.

(2)催化剂对乙酸环己酯的合成具有较好的催化活性,其用量少,反应时间短,催化剂可以较好的回收与循环使用,是一种优良的催化剂.

(3)乙酸环己酯的合成以HPA/TiO2-WO3为适宜的催化剂,用量为反应物料总质量的1.0%,酸醇量比为1.5∶1.0,反应时间1.5h,反应温度104～120℃,酯收率可达77.4%.

(4)在优化条件下,所得产品为无色有水果香味的液体,其折光率及IR光谱图特征峰均与文献值较好吻合.

参考文献:

[1]　济南市轻工业研究所.合成食用香料手册[M].北京:中国轻工业出版社,1985.372-473.

[2]　AlbertodeAngelis,StefanoAmarilliect.Alkylationofbenzenecatalysedbysupportedheteropolyacids[J].JournalofMolecular

CatalysisA:Chemical,1999,146:37-44.

[3]　Billy.B.Bardin,Robert.J.Davis.Effectofwateronsilica-supportedphosphotungsticacidcatalystsfor1-butenedoublebond

shiftandalkaneskeletalisomerization[J].AppliedCatalysisA:General,2000,200:219-231.

[4]　余新武,赖国松.TiSiW12O40/TiO2催化合成丙酸异戊酯[J].化学研究与应用,2002,14(4):423-425.

(上接第97页)

4　结束语

信号量机制是一种卓有成效的进程同步工具.在长期而广泛地应用中,信号量机制得到了很大的发展.现在,信号量机制已经被广泛应用于单处理机和多处理机系统以及计算机网络中.但是,在使用P、V操作解决具体问题时,可能需要同时解决互斥与同步,使用多个信号量,比如在生产者-消费者问题中不仅有实现互斥的信号量mutex,也有资源信号量full和empty,并且执行了多次P、V操作.从本文列举的两个经典同步问题不难看出,应该对信号量的设置以及多个P、V操作之间的执行顺序等问题特别谨慎,如稍有不慎就可能导致执行错误,甚至造成死锁.

参考文献:

[1]　AndrewS.Tanenbaum.操作系统与实现(第2版)[M].北京:电子工业出版社,2001.

[2]　徐甲同.操作系统教程[M].西安:西安电子科技大学出版社,1999.

第21卷第2期

2005年4月商丘师范学院学报JOURNALOFSHANGQIUTEACHERSCOLLEGEVol.21No.2April,2005

使用P、V操作解决经典进程同步问题

朱敬鹏,乔丽,王铁柱112

(1.商丘师范学院计算机科学系,河南商丘476000;2.商丘市有线电视台,河南商丘476000)

　　摘　要:简要介绍P、V操作.通过对两个经典同步问题的描述,说明如何使用P、V操作解决实际问题,重点简述了使用信号量机制解决同步问题时容易产生死锁的原因以及解决死锁的方法.

关键词:信号量;同步;死锁;临界资源

中图分类号:TP316　　　　　文献标识码:A　　　　　文章编号:1672-3600(2005)02-0095-03

UsetheP.Voperationtosolveclassicalprocesssynchronizationproblem

ZHUJing-peng1;QIAOLi1;WANGTie-Zhu2

(1.Dept.ofComputer,ShangqiuTeachersCollege,Shangqiu476000,China;2.CAVofShangqiu,Shangqiu476000,China)Abstract:ThebriefintroductionoftheP.Voperationismadeasbelow.Byanalysingthetwoclassicalprocesssynchronization,howtosolvethepracticalproblemsbyapplyingP.Voperationisindicated,emphaticallyillustratingboththereasonofdeadlockeasilyoccurredwhenapplyingthesignalquantitysystemandtheapproachestocopewithdeadlockaswell.

Keywords:semaphores;synchronization;deadlock;criticalresource

在操作系统中引入进程后,由于进程的异步性,可能会有多个进程在同一个时间间隔内并发执行,尤其是并发进程竞争临界资源时,就可能会给系统造成混乱.当多个进程需要合作完成一项任务,又要求它们能正确地执行,不会出现死锁时,这种问题我们称之为进程同步问题.生产者-消费者问题,哲学家共进餐问题是典型的进程同步问题.在现代操作系统中,通常都采用P、V操作来解决进程同步问题.

1　P、V操作的描述

1965年,荷兰学者Dijkstra提出的信号量机制,这就是一种卓有成效的进程同步工具,可以有效地解决进程同步问题.该机制中,采用了记录型的数据结构,它所包含的两个数据项可以描述为:

typesemaphore=record

value:integer;

L:listofprocess;

End

相应地:P、V操作可以描述为:

P:procedurewait(S)　　　　　　　　　　　　V:proceduresignal(S)

　　　varS:semaphore;

　　　begin

　　　　S.value:=S.value-1;

　　　　ifS.value

　　　end　　　end

其中,S.value的初值表示系统中某类资源的数目,因而又称为资源信号量.对它每次执行P操作,意味着进程请求一个单位的某类资源,因此描述为S.value;=S.value-1;当S.value

96商丘师范学院学报　　　　　　　　　　　　　　　　　2005年　value+1;若执行S.value:=S.value+1操作后仍是S.value≤0,则表示在该信号量链表中,仍有等待该资源的进程被阻塞,故应调用wakeup原语将S.L中的第一个等待进程唤醒.

2　生产者-消费者问题

2.1　问题描述

有一批生产者进程在生产产品,并将这些产品提供给消费者进程消费.为使生产者进程和消费者进程能并发执行,在两者之间设置一个具有N个缓冲区的缓冲池,生产者进程将它生产的产品放入一个缓冲区中;消费者进程可以从一个缓冲区中取走产品去消费.它们之间必须保持同步,既不允许消费者进程到一个空缓冲区去取产品,也不允许生产者进程向一个已经装满产品且未被取走的缓冲区中投放产品.

可以利用一个数组来表示一个具有N个缓冲区的缓冲池.用一个输入指针in指示下一个可以投放产品的缓冲区,用一个输出指针out指示下一个可以从中获取产品的缓冲区.用一个整型变量count表示满缓冲区的个数.两个进程共享下列变量:

varn,integer;

typeitem=…;

varbuffer:array[0,1,…,n-1]ofitem;

in,out;0,1,…,n-1;

count:0,1,…,n;

假定在生产者和消费者之间的缓冲池中,具有N个缓冲区,可以利用一个互斥信号量mutex实现各进程对缓冲池的互斥使用;利用信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量.对生产者消费者问题可以描述如下:

varmutex,empty,full:semaphore:=1,n,0;

　buffer:array[0,…,n-1]ofitem;

　in,out:integer:=0,0;

　begin

　　生产者:begin

　repeat

　　…

　生产一个产品投入变量nextp;

　　…

　p(mutex);……………………(A)

　p(empty);……………………(B)

　buffer(in):=nextp;

　in:=(in+1)modn;

　v(full);…………………………(A)

　v(mutex);………………………(B)

　untilfalse;

end

　　消费者:begin

　repeat

　　p(mutex);…………………(A)

　　p(full);……………………(B)

　　nextc:=buffer(out);

　　out:=(out+1)modn;

　　v(empty);……………………(A)

　　v(mutex);……………………(B)

　　从nextc中取一个产品;

　　untilfalse;

end

　end

2.2　出现的问题以及解决方法:首先,和v(成对出现;,

和full的p、v操作同样必须成对出现,但他们分别处于不同的程序中.另外,虽然从表面上看,上述程序不仅可以使用信号量mutex实现生产者和消费者互斥地访问缓冲池,而且可以实现同步,但是却可能出现死锁如:当生产者申请mutex并成功,此时mutex的值将变为0,当生产者继续执行p(empty)时,如果此时缓冲池已满,则没有空缓冲区,此时生产者应阻塞,此时,消费者应可以取产品,但是由于生产者阻塞,且mutex已经为0,所以消费者也阻塞,双方都阻塞———死锁.解决方法是:将上述程序中的所有相邻(A)和(B)互换顺序.

3　哲学家进餐问题

3.1　问题描述

有5个哲学家共用一张圆桌,分别坐在周围的5张椅子上,在圆桌上有5个碗和5只筷子,他们的生活方式是交替地进行思考和吃饭.平时,一个哲学家进行思考,饥饿时便试图取用其左右最靠近他的筷子,只有在他拿到两只筷子时才能吃饭,吃完后放下筷子继续思考.

分析可知,筷子是临界资源,5个哲学家需要互斥地对其进行访问,即在同一时刻只允许一个哲学家使用,若用一个信号量表示一个筷子,则可以使用一个数组来描述这5只筷子:

　varchopstick:array[0,…,4]ofsemaphore;所有信号均被初始化为1,第i位哲学家的活动可描述为:

repeat

　　P(chopstick[i]);

　　P(chopstick[i+1]mod5);

　　　…

　　eat;

　　　…

　　V(chopstick[i]);

　　V(chopstick[i+1]mod5);

　　　…

　think;

　untilfalse;

3.2　出现的问题以及解决方法

从上面程序中可以看出,当哲学家饥饿时,总是先拿左边筷子(P(chopstick[i])),成功后才会去拿右边筷子P(chopstick[i+1]mod5),然后才吃饭.虽然该程序可以保证相邻两个哲学家不会同时吃饭,但可能引起死锁,假如5位哲学家同时拿起左手筷子,会使5个chopstick信号量全变为0;当他们试图去取右边筷子时,都因为拿不到而全部等待—死锁.对于这个死锁问题,可以采用下述方法解决:至多只允许4位哲学家同时进餐,这样便可以保证有一个哲学家能够进餐,并在进餐结束后释放他用过的筷子,从而使更多的哲学家可以进餐.具体实现时,可以在上述程序的基础上加以修改,增设一个信号量max,用于控制同时进餐的哲学家的个数,值为4,并将P(max)操作放在两个P操作之前,将(max)操作放在两个V操作之后即可.修改后的程序如下:

repeat

　　P(max);

　　P(chopstick[i]);

　　P(chopstick[i+1]mod5);

　　　…

　　eat:

　　　…

　　V(chopstick[i]);

　　V(chopstick[i+1]mod5);

　　V(max);

　　…

　　think;

untilfalse;

这样,既可以保证相邻两个哲学家不会同时吃饭,又可以保证不会产生死锁,因为不会出现5个哲学家同时吃饭.

(下转第109页)

催化剂的回收参照文献[7]的方法进行,将回收所得的催化剂经过适当的处理后,在上述考察所得的优化条件下重复实验,平均收率仍达到84%.

2.7　产品检测与分析

使用Nicolet公司70SXFT-IR型红外光谱仪对制备的乙酸环己酯产品进行了测定,特征峰分别为2940、2859cm(C—O—C对称伸缩振动),产品的折光率n20.4442(文献值为1.4440).D=1-1(—CH2—伸缩振动),1726cm-1(C=O),14452cm-1(—CH2—弯曲振动),1192cm-1(C—O—C不对称伸缩振动),1018cm-1

3　结论

(1)超声波振荡法制备Ti(OH)4并合成纳米固载型多酸催化剂HPA/TiO2-WO3,比已报道的合成该类型催化剂的周期明显缩短.

(2)催化剂对乙酸环己酯的合成具有较好的催化活性,其用量少,反应时间短,催化剂可以较好的回收与循环使用,是一种优良的催化剂.

(3)乙酸环己酯的合成以HPA/TiO2-WO3为适宜的催化剂,用量为反应物料总质量的1.0%,酸醇量比为1.5∶1.0,反应时间1.5h,反应温度104～120℃,酯收率可达77.4%.

(4)在优化条件下,所得产品为无色有水果香味的液体,其折光率及IR光谱图特征峰均与文献值较好吻合.

参考文献:

[1]　济南市轻工业研究所.合成食用香料手册[M].北京:中国轻工业出版社,1985.372-473.

[2]　AlbertodeAngelis,StefanoAmarilliect.Alkylationofbenzenecatalysedbysupportedheteropolyacids[J].JournalofMolecular

CatalysisA:Chemical,1999,146:37-44.

[3]　Billy.B.Bardin,Robert.J.Davis.Effectofwateronsilica-supportedphosphotungsticacidcatalystsfor1-butenedoublebond

shiftandalkaneskeletalisomerization[J].AppliedCatalysisA:General,2000,200:219-231.

[4]　余新武,赖国松.TiSiW12O40/TiO2催化合成丙酸异戊酯[J].化学研究与应用,2002,14(4):423-425.

(上接第97页)

4　结束语

信号量机制是一种卓有成效的进程同步工具.在长期而广泛地应用中,信号量机制得到了很大的发展.现在,信号量机制已经被广泛应用于单处理机和多处理机系统以及计算机网络中.但是,在使用P、V操作解决具体问题时,可能需要同时解决互斥与同步,使用多个信号量,比如在生产者-消费者问题中不仅有实现互斥的信号量mutex,也有资源信号量full和empty,并且执行了多次P、V操作.从本文列举的两个经典同步问题不难看出,应该对信号量的设置以及多个P、V操作之间的执行顺序等问题特别谨慎,如稍有不慎就可能导致执行错误,甚至造成死锁.

参考文献:

[1]　AndrewS.Tanenbaum.操作系统与实现(第2版)[M].北京:电子工业出版社,2001.

[2]　徐甲同.操作系统教程[M].西安:西安电子科技大学出版社,1999.