自行车生产线上有一箱子.ppt

习题课,1.自行车生产线上有一箱子,其中有N个位置(N3),每个位置可放一个车轮或一个车架；又设有3个工人P1,P2,P3其活动分别为:,P1:P2;P3:加工一车架;加工一个车轮;箱中取1车架;将车架放入箱中;将车轮放入箱中;箱中取2车轮;组装为一辆车;,用PV操作实现三个工人的合作(不考虑死锁）,Semaphareempty=N,wheel=0,frame=0;P1:P2:P3:加工一车架;加工一车轮;p(frame);取一车架;P(empty);p(empty);v(empty);车架放入箱中;车轮放入箱中;p(wheel);P(wheel);取2个车轮；v(frame);v(wheel);v(empty);v(empty)组装一车子;,死锁分析,当1工人推进速度快，箱中有N个车架或有N-1个车架,且P3已拿到一个车架同时申请2个车轮时,出现死锁;同理当箱中有N个车轮,且P3尚未拿到车架时也出现死锁.,考虑死锁的算法,Semaphoreempty=N;frame=0;wheel=0;n1=N-2;n2=N-1;P1:P2:P3:加工一车架;加工一车轮;p(frame);P(n1);p(n2);取一车架;P(empty);p(empty);v(empty);车架放入箱中;车轮放入箱中;v(n1);V(frame);v(wheel);p(wheel);p(wheel);取2车轮;v(empty);v(empty)v(n2);v(n2)组装一个车子;,用管程实现三个工人的合作,TypeBox=monitor;enumitem=frame,wheel,nullVarbox:array0.Nofitem;count1,count2:integer;full,frameempty,wheelempty:condition;in,out:integer;Defineputin-frame,putin-wheel,takeout-frame,takeout-wheel,Produceputin-frame(x:frame)beginif(count1+count2)Nthenwait(full);ifcount1N-2thenwait(full);count1:=count1+1;fori=1toNifboxi=nullthenbreak;in:=i;boxin:=x;signal(frameempty);end,Produceputin-wheel(y:wheel)beginif(count1+count2)Nthenwait(full);ifcount2N-1thenwait(full);count2:=count2+1;fori=1toNifboxi=nullthenbreak;in:=i;boxin:=y;signal(wheelempty);end,Producetakeout-frame(x:frame)beginifcount1accepttakeframe(x:outframe);fori=1toNifboxi=bodythenbreakout:=i;x:=boxout;count1:=count1-1;end,orwhencount20=accepttakewheel(y:outwheel)dofori=1toNifboxi=capthenbreakout:=i;y:=boxout;count2:=count2-1;endendselectendloopendcase,hoare管程实现电梯算法,Typediskhead=MONITORVarbusy:boolean;headpos:0.199;direction:(up,down);cylinder:Array0.199Ofcondition;count:Array0.199Ofinteger;Definerequire,release;,Procedurerequire(dest:0.199);BeginIfbusyThenBegincountdest:=countdest+1;wait(cylinderdest)Endbusy:=true;IfdestheadposThendirection:=up;headpos:=destEnd;,Procedureupscan;VarI:0.200;flag:(false,true)BeginI:=headpos;flag:=false;While(I=0ThenBegincountI:=countI-1;signal(cylinderI);flag:=true;EndEnd;,Procedurerelease;Beginbusy:=false;Ifdirection=upThenBeginupscan;if(!flag)thendownscanEndElseBegindownscan;if(!flag)thenupscanEndEnd;,Procedureinitialize;VarI:0.199;Beginbusy:=false;headpos:=0;direction:=up;ForI:=0To199DocountI:=0EndBegininitializeEnd;,