《Lamport面包店算法详解(转侵删)》由会员分享,可在线阅读,更多相关《Lamport面包店算法详解(转侵删)(2页珍藏版)》请在金锄头文库上搜索。
1、Lamport面包店算法详解(转侵删)范例1:booleanchoosingn;表示进程是否在取号intnumbern;记录每个进程取到的号码这些数据结构分别初始化为false和0,为了方便,定义如下符号:若ac或a=c和bd同时成立,(a,b)(c,d)dochoosingi=true;numberi=maxnumber0,number1,numbern-1+1;/选号码choosingi=false;for(j=0;jn;j+)while(choosingj);while(numberj!=0)&(numberj,j)(numberi,i);/临界区numberi=0;其余部分while(
2、1);理解:第一个试图进入临界区的进程Pi在没有其它进程竞争时顺利进入其临界区。满足了有空就进的要求。当有竞争者Pk(ik),且选的号码相同时,比较进程的名称,通过语句while(numberj!=0)&(numberjj)(numberi,i);来选择进入的进程。在Pi进程中j=i时,numberj=numberi,且j=i所以(numberj,j)i所以(numberj,j)(numberi,i)不成立,退出while语句。对与其它非i和k的j值,numberj!=0不成立,退出while语句。在pk进程中j=i时,numberjnumberk,jk,所以(numberjj)(number
3、i,i)成立,故进程Pk陷在该语句中,直到Pi退出临界区执行语句numberi=0时才允许Pk进程进入其临界区。所以满足了互斥和有限等待的要求。范例2:在文献中的几种互斥算法中,所谓的Lamport面包店算法可以有效地用于多个相互竞争的控制线程,该算法中线程之间的通信只能在共享内存中进行(即,不需要诸如信号量、原子性的set-and-test之类的专门机制)。该算法的基本思想源于面包店,因为面包店需要先取号然后等候叫号。下面给出了该算法的框架,该算法可以使各线程进出临界区而不产生冲突。Enter,Number:array1.Nofinteger=0;/logicusedbyeachthread
4、-/where(a,b)(c,d)/means(ac)or(a=c)and(bd)Thread(i)while(true)Enteri=1;Numberi=1+max(Number1,NumberN);Enteri=0;for(j=1;j=N;+j)while(Enterj!=0)/waituntilthreadjreceivesitsnumberwhile(Numberj!=0)&(Numberj,j)(Numberi,i)/waituntilthreadswithsmallernumbers/orwiththesamenumber,butwithhigher/priority,finishtheirwork/criticalsectionNumberi=0;/non-criticalsection