% file: threading_exs.mp % thread examples deadlock, and critcal resource input boxes %tracingall; %tracingmacros := 1; %tracingequations := 1; defaultfont := "cmtt8"; numeric u;u:=1cc; numeric Half_tunit; numeric Time_unit_size,No_time_units; numeric lt_hd,rt_hd,both_hd,no_hd,up_hd,dwn_hd,below,above; lt_hd:=0;rt_hd:=1;both_hd:=2;no_hd:=3;up_hd:=4;dwn_hd:=5; above:=6;below:=7; %How - l,r,b,n left head rt head both head no heads 0..3 numeric Outer_side_size,Time_side_size,Inner_side_size; numeric Outer_to_time_side_size,Time_to_inner_side_size; pair Sw_inner,Sw_time,Sw_outer; pair Mid_tunit; pair Time_lft_tpos,Inner_tpos,Time_rt_tpos,Bot_side_tpos,Top_side_tpos; pair Outer_lft_tpos,Outer_rt_tpos,obot_side_tpos,otop_side_tpos; def drw_obelisk(expr Time_units,Size_time_unit)= Time_unit_size := Size_time_unit; Half_tunit:=.5*Time_unit_size; No_time_units := Time_units; Outer_to_time_side_size:=2*Time_unit_size; Time_to_inner_side_size:=Time_unit_size; Inner_side_size:=No_time_units*Time_unit_size; Time_side_size:=Time_to_inner_side_size+Inner_side_size+Time_to_inner_side_size; Outer_side_size:=Outer_to_time_side_size+Time_side_size+Outer_to_time_side_size; Sw_outer:=(0,0); Sw_time:= Sw_outer shifted (Outer_to_time_side_size,Outer_to_time_side_size); Sw_inner:= Sw_time shifted (Time_to_inner_side_size,Time_to_inner_side_size); drw_box(Sw_outer,Outer_side_size,Outer_side_size); drw_box(Sw_time,Time_side_size,Time_side_size); drw_box(Sw_inner,Inner_side_size,Inner_side_size); drw_outer_mitre(Sw_outer,Outer_side_size,Outer_to_time_side_size); drw_mark_time(Sw_time); enddef; def drw_mark_time(expr Sw)= draw Sw -- Sw +(0,Time_to_inner_side_size) -- Sw +(Time_to_inner_side_size,Time_to_inner_side_size) -- Sw +(Time_to_inner_side_size,0); draw Sw shifted (0,Time_side_size) --Sw +(0,Time_to_inner_side_size) rotated -90 shifted (0,Time_side_size) -- Sw +(Time_to_inner_side_size,Time_to_inner_side_size) rotated -90 shifted (0,Time_side_size) -- Sw +(Time_to_inner_side_size,0) rotated -90 shifted (0,Time_side_size); draw Sw shifted (Time_side_size,Time_side_size) -- Sw +(0,Time_to_inner_side_size) rotated -180 shifted (Time_side_size,Time_side_size) -- Sw +(Time_to_inner_side_size,Time_to_inner_side_size) rotated -180 shifted (Time_side_size,Time_side_size) -- Sw +(Time_to_inner_side_size,0) rotated -180 shifted (Time_side_size,Time_side_size); draw Sw shifted (Time_side_size,0) -- Sw +(0,Time_to_inner_side_size) rotated -270 shifted (Time_side_size,0) -- Sw +(Time_to_inner_side_size,Time_to_inner_side_size) rotated -270 shifted (Time_side_size,0) -- Sw +(Time_to_inner_side_size,0) rotated -270 shifted (Time_side_size,0); % draw marks of twain defaultscale:=.6; string a; Time_lft_tpos := Sw shifted (0,Time_side_size-2*Time_to_inner_side_size); Inner_tpos := Time_lft_tpos shifted (Time_unit_size,0); Outer_lft_tpos := Time_lft_tpos shifted (-Outer_to_time_side_size,0); Time_rt_tpos := Time_lft_tpos shifted (Time_side_size,0); Outer_rt_tpos := Time_rt_tpos shifted (Outer_to_time_side_size,0); Bot_side_tpos := Sw shifted (Time_to_inner_side_size,0); Top_side_tpos := Bot_side_tpos shifted (0,Time_side_size - Time_to_inner_side_size); Mid_tunit := .5[(0,0),(Time_to_inner_side_size,0)]; numeric tunit; for i=0 upto No_time_units - 1: a:=decimal i; tunit := i*Time_to_inner_side_size; label.top(a,Mid_tunit shifted Bot_side_tpos + (tunit,0));%bottom time line label.top(a,Mid_tunit shifted Top_side_tpos + (tunit,0));%top time line label.top(a,Mid_tunit shifted Time_lft_tpos + (0,-tunit));%left side time line label.top(a,Mid_tunit shifted Time_rt_tpos + (-Time_to_inner_side_size,-tunit));%rt side time line endfor defaultscale:=1; enddef; def drw_outer_mitre(expr Pos,Side,Mitre_size)= draw Pos--Pos+(Mitre_size,Mitre_size); draw Pos shifted (Side,0)-- Pos+(Mitre_size,Mitre_size) rotated 90 shifted (Side,0); draw Pos shifted (Side,Side)-- Pos+(Mitre_size,Mitre_size) rotated 180 shifted (Side,Side); draw Pos shifted (0,Side)-- Pos+(Mitre_size,Mitre_size) rotated -90 shifted (0,Side); enddef; def drw_box(expr Pos,Side,Ht)= pair nw,ne,sw,se; sw:=Pos; se:=sw+(Side,0); nw:=sw+(0,Ht); ne:=nw+(Ht,0); draw sw--se--ne--nw--cycle; enddef; % % Lft_time_side_tpos inner point of 0 unit % def drw_lft_side_hz_vector(expr Tunit,How)= pair zr,zl; zr := Time_lft_tpos;% from anchor pt numeric row; row:= Time_unit_size*Tunit;%bot of time unit zr := zr shifted (0,-row);%row zr := zr shifted (0,Half_tunit);%put in middle of box zl := zr shifted (-Outer_to_time_side_size,0);% to anchor pt if(How = rt_hd): drawarrow zl .. zr ; else: if (How = lt_hd): drawarrow zr .. zl ; else: if (How = both_hd): drawdblarrow zr .. zl ; else: if (How = no_hd): draw zr -- zl; fi fi fi fi enddef; % % rt_side_tpos inner point of 0 unit % def drw_rt_side_hz_vector(expr Tunit,How)= pair zr,zl; zl := Time_rt_tpos;% from anchor pt numeric row; row:= Time_unit_size*Tunit;%bot of time unit zl := zl shifted (0,-row);%row zl := zl shifted (0,Half_tunit);%put in middle of box zr := zl shifted (Outer_to_time_side_size,0);% to anchor pt if(How = rt_hd): drawarrow zl .. zr ; else: if (How = lt_hd): drawarrow zr .. zl ; else: if (How = both_hd): drawdblarrow zr .. zl ; else: if (How = no_hd): draw zr -- zl; fi fi fi fi enddef; % Lft_time_side_tpos used % row the time unit to mark against % time unit start, stop %How - l,r,b,n left head rt head both head no heads 0..3 def drw_hz_inner_vector(expr Tunit_row,From_Tunit,To_Tunit,How)= pair f,t; f := Inner_tpos;% resource 0 time row numeric row; row:= Time_unit_size*Tunit_row; f:= f shifted (0,-row) + (0,Half_tunit); t := f; f:= f shifted (Time_unit_size*From_Tunit,0);% from col t:= t shifted (Time_unit_size*To_Tunit,0);% to col t:= t shifted (Time_unit_size,0);%rt boundary of time slot if(How = rt_hd): drawarrow f shifted ..t ; else: if (How = lt_hd): drawarrow t ..f ; else: if (How = both_hd): drawdblarrow f ..t ; else: if (How = no_hd): draw f -- t ; fi fi fi fi enddef; def drw_hz_inner_ownership(expr Tunit,Tunit_x,What)= numeric row; row:= Time_unit_size*Tunit;%bot of time unit pair f; f := Inner_tpos shifted (0,-row)+(0,Half_tunit);% from anchor pt f:= f shifted (Time_unit_size*Tunit_x,0); label.top(What,f); enddef; %How - l,r,b,n left head rt head both head no heads 0..3 def drw_vt_vector(expr Bot_line,Col,How)= pair base_line; numeric row,tu; row := Time_unit_size*Bot_line; tu := Time_to_inner_side_size; base_line := Inner_tpos shifted (0,-row)+(0,-tu); numeric dcol,dht; dcol:= Time_unit_size*Col; dht:= Outer_to_time_side_size; base_line := base_line shifted (dcol,0) + (Half_tunit,0); pair f,t; f := base_line;% from anchor pt t := base_line shifted (0,-dht);% from anchor pt if(How = up_hd): drawarrow t..f; else: if (How = dwn_hd): drawarrow f..t; else: drawdblarrow f..t; fi fi enddef; % Opos top outer corner lt or rt % Tunit the time unit 0..16 %Delta --- sixe of vector track + if lt, - if rt side %How - l,r,b,n left head rt head both head no heads 0..3 def drw_vt_dotted_vector(expr Bot_Tline,Tunit_x,Tunit_y,How)= pair base_line,t; base_line := Inner_tpos shifted (0,-Bot_Tline*Time_unit_size);%base part of line numeric xcol,y_ht; xcol := Time_unit_size*Tunit_x;%bot of time unit y_ht := Time_unit_size*Tunit_y; base_line := base_line shifted (xcol,0)+(Half_tunit,0); t:= Inner_tpos shifted (xcol,-y_ht)+(Half_tunit,Half_tunit); if(How = up_hd): drawarrow base_line..t dashed withdots; else: drawarrow t..base_line dashed evenly; fi enddef; def drw_x_deadlock(expr Tunit_x,Tunit_y)= pair base_line; base_line := Inner_tpos shifted (0,-Tunit_x*Time_unit_size);%base part of line numeric col; col:= Time_unit_size*Tunit_y; base_line := base_line shifted (col,0); draw base_line -- base_line shifted (Time_unit_size,Time_unit_size); draw base_line shifted (0,Time_unit_size) -- base_line shifted (Time_unit_size,0); enddef; def drw_lft_outer_hz_note(expr Tunit,Note)= pair f; f := Outer_lft_tpos shifted (0,Half_tunit);% from anchor pt numeric row; row:= Time_unit_size*Tunit; f := f shifted (0,-row); label.lft(Note,f); enddef; def drw_rt_outer_hz_note(expr Tunit,Note)= pair f; f := Outer_rt_tpos shifted (0,Half_tunit);% from anchor pt numeric row; row:= Time_unit_size*Tunit; f := f shifted (0,-row); label.rt(Note,f); enddef; def drw_hz_xy_inner_note(expr Tunit_x,Tunit_y,Note)= numeric row,col; row:= Time_unit_size*Tunit_x;%bot of time unit col:= Time_unit_size*Tunit_y;%interior of time unit pair f; f := Inner_tpos shifted (0,-row)+(col,0)+(0,Half_tunit); label.rt(Note,f); enddef; % Opos top outer corner lt or rt % Tunit the time unit 0..16 %Delta --- size of vector track + if lt, - if rt side def drw_vt_note(expr Opos,Tunit,Note)= pair zz; zz := Opos;% from anchor pt numeric time_delta; time_delta:= 1u*Tunit;%bot of time unit pair f,t; f:=zz+(time_delta,0)+(.5u,0); %f:=f + (0,1u);% align closer to outer box line numeric str_len; str_len := length(Note); t:=f; pair accum_letter_ht,letter_ht;letter_ht:=(0,0);accum_letter_ht:=(0,0); for i=0 upto str_len-1: t:=f - (0,ypart accum_letter_ht); string d; d:=substring(i,i+1) of Note; label.bot(d,t); picture letter; letter := d infont defaultfont scaled defaultscale; letter_ht := ulcorner letter - llcorner letter; accum_letter_ht:= accum_letter_ht + letter_ht+(0,bboxmargin); endfor enddef; def drw_vt_dashed_vector(expr Tunit_f,Tunit_t,Tunity)= numeric rowf,rowy; rowf:= Time_unit_size*Tunit_f;%bot of time unit rowy:= Time_unit_size*Tunit_t;%bot of time unit pair f,t; f:=Inner_tpos shifted (0,-rowf)+(Tunity*Time_unit_size,0)+(Time_unit_size,0); t:=Inner_tpos shifted (0,-rowy)+(Tunity*Time_unit_size,0)+(Time_unit_size,0); draw f shifted (0,Half_tunit)..t shifted (0,Half_tunit) dashed evenly; enddef; % % Yacco2 example % beginfig(1); drw_obelisk(26,.7u); % G space drw_rt_side_hz_vector(1,both_hd); drw_rt_outer_hz_note(1,"Acquire g"); drw_rt_outer_hz_note(2,"Launch threads"); drw_rt_side_hz_vector(3,both_hd); drw_rt_outer_hz_note(3,"Acquire x"); drw_rt_side_hz_vector(4,lt_hd); drw_rt_outer_hz_note(4,"Create A"); drw_lft_side_hz_vector(5,lt_hd); drw_lft_outer_hz_note(5,"Activated"); drw_lft_side_hz_vector(6,both_hd); drw_lft_outer_hz_note(6,"Acquire a"); drw_lft_side_hz_vector(7,rt_hd); drw_lft_outer_hz_note(7,"Acquire x"); drw_rt_side_hz_vector(8,rt_hd); drw_rt_outer_hz_note(8,"Re-activated"); drw_rt_outer_hz_note(9,"Setup: thread results"); drw_rt_side_hz_vector(10,lt_hd); drw_rt_outer_hz_note(10,"Release x"); drw_lft_side_hz_vector(11,lt_hd); drw_lft_outer_hz_note(11,"Wokeup with x"); drw_lft_outer_hz_note(12,"Make idle"); drw_lft_side_hz_vector(13,rt_hd); drw_lft_outer_hz_note(13,"Release x"); drw_rt_side_hz_vector(14,rt_hd); drw_rt_outer_hz_note(14,"Re-activated"); drw_rt_side_hz_vector(15,lt_hd); drw_rt_outer_hz_note(15,"Wait on event"); drw_rt_outer_hz_note(16,"release g"); drw_lft_side_hz_vector(16,lt_hd); drw_lft_outer_hz_note(16,"Re-activated"); drw_lft_side_hz_vector(17,both_hd); drw_lft_outer_hz_note(17,"Acquire g"); drw_lft_outer_hz_note(18,"Deposit data in G"); drw_lft_side_hz_vector(19,both_hd); drw_lft_outer_hz_note(19,"Release g"); drw_lft_side_hz_vector(20,both_hd); drw_lft_outer_hz_note(20,"Signal G"); drw_lft_side_hz_vector(21,rt_hd); drw_lft_outer_hz_note(21,"Wait on event"); drw_lft_outer_hz_note(22,"release a"); drw_rt_side_hz_vector(22,rt_hd); drw_rt_outer_hz_note(22,"Wokeup from event"); drw_rt_outer_hz_note(23,"Process data from A"); drw_rt_outer_hz_note(24,"Keep running until"); drw_rt_outer_hz_note(25,"launch of threads"); % inner space drw_hz_xy_inner_note(8,5,"Inner Space: Thread Manager"); drw_hz_xy_inner_note(0,0,"Running queue:"); drw_hz_xy_inner_note(1,0,"G"); drw_hz_xy_inner_note(2,0,"A"); drw_hz_xy_inner_note(5,0,"To Run queue:"); drw_hz_xy_inner_note(6,0,"G"); drw_hz_xy_inner_note(7,0,"A"); drw_hz_xy_inner_note(10,0,"Resources"); drw_hz_xy_inner_note(11,0,"g"); drw_hz_xy_inner_note(12,0,"x"); drw_hz_xy_inner_note(13,0,"a"); % G running drw_hz_inner_vector(1,1,4,no_hd); drw_hz_inner_vector(2,5,7,no_hd); drw_hz_inner_vector(1,8,10,no_hd); drw_hz_inner_vector(2,11,13,no_hd); drw_hz_inner_vector(1,14,15,no_hd); drw_hz_inner_vector(2,16,21,no_hd); drw_hz_inner_vector(1,22,25,no_hd); % draw continuity drw_vt_dashed_vector(1,2,4); drw_vt_dashed_vector(2,1,7); drw_vt_dashed_vector(1,2,10); drw_vt_dashed_vector(2,1,13); drw_vt_dashed_vector(1,2,15); drw_vt_dashed_vector(2,1,21); % G to run drw_hz_inner_vector(6,3,6,no_hd); drw_hz_inner_vector(6,9,13,no_hd); % A running drw_hz_inner_vector(7,7,11,no_hd); % resources % g drw_hz_inner_vector(11,1,15,no_hd); drw_hz_inner_vector(11,17,19,no_hd); drw_hz_inner_vector(11,22,25,no_hd); % x drw_hz_inner_vector(12,3,10,no_hd); drw_hz_inner_vector(12,11,13,no_hd); % a drw_hz_inner_vector(13,6,21,no_hd); % waiting on resource % label ownership drw_hz_inner_ownership(11,8,"G"); drw_hz_inner_ownership(11,19,"A"); drw_hz_inner_ownership(11,24,"G"); drw_hz_inner_ownership(12,9,"G"); drw_hz_inner_ownership(13,14,"A"); drw_vt_dotted_vector(25,7,12,up_hd); drw_vt_dotted_vector(25,11,12,dwn_hd); drw_vt_dotted_vector(25,15,11,up_hd); drw_vt_dotted_vector(25,22,11,dwn_hd); drw_vt_dotted_vector(25,21,13,up_hd); %space labels defaultscale:=1.5; label.lft(btex --- A Space --- etex,Sw_outer+(0,29*Time_unit_size)); label.rt(btex --- G Space --- etex,Sw_outer+(33*Time_unit_size,29*Time_unit_size)); endfig; % % Deadlock example % beginfig(2); drw_obelisk(17,1u); % A space drw_lft_side_hz_vector(3,lt_hd); drw_lft_outer_hz_note(3,"Activated"); drw_lft_side_hz_vector(4,both_hd); drw_lft_outer_hz_note(4,"Acquire a"); drw_lft_side_hz_vector(5,both_hd); drw_lft_outer_hz_note(5,"Acquire x"); drw_lft_side_hz_vector(6,rt_hd); drw_lft_outer_hz_note(6,"Release x"); drw_lft_side_hz_vector(12,lt_hd); drw_lft_outer_hz_note(12,"Re-activated"); drw_lft_side_hz_vector(13,rt_hd); drw_lft_outer_hz_note(13,"Acquire b"); % G space drw_rt_side_hz_vector(1,both_hd); drw_rt_outer_hz_note(1,"Acquire g"); drw_rt_side_hz_vector(2,lt_hd); drw_rt_outer_hz_note(2,"Create A"); drw_rt_side_hz_vector(7,rt_hd); drw_rt_outer_hz_note(7,"Re-activated"); drw_rt_side_hz_vector(8,lt_hd); drw_rt_outer_hz_note(8,"Create B"); drw_rt_side_hz_vector(14,rt_hd); drw_rt_outer_hz_note(14,"Re-activated"); drw_rt_side_hz_vector(15,lt_hd); drw_rt_outer_hz_note(15,"Wait on signal, rel. g"); drw_rt_outer_hz_note(16,"Deadlock"); % B space drw_vt_vector(16,9,dwn_hd); %%%% %drw_vt_note(bot_lt,9,"Activated"); drw_vt_vector(16,10,both_hd); %%%% %drw_vt_note(bot_lt,10,"Acquire b"); drw_vt_vector(16,11,up_hd); %%%% %drw_vt_note(bot_lt,11,"Acquire a"); pair odisp; odisp := (0,0) + (Time_unit_size*Outer_to_time_side_size,0) + (Time_unit_size*Time_to_inner_side_size,0); %label.lft(btex activated etex rotated 30,odisp shifted (10*Time_unit_size,-Time_unit_size)); label.lft(btex activated etex rotated 30,(0,0) + (13u,-u)); %label.lft(btex acquire b etex rotated 30,odisp shifted (11*Time_unit_size,-Time_unit_size)); label.lft(btex acquire b etex rotated 30,(0,0) + (14*Time_unit_size,-Time_unit_size)); %label.lft(btex acquire a etex rotated 30,odisp shifted (12*Time_unit_size,-Time_unit_size)); label.lft(btex acquire a etex rotated 30,(0,0) shifted (15*Time_unit_size,-Time_unit_size)); % inner space drw_hz_xy_inner_note(9,5,"Inner Space: Thread Manager"); drw_hz_xy_inner_note(0,0,"Running queue:"); drw_hz_xy_inner_note(1,0,"G"); drw_hz_xy_inner_note(2,0,"A"); drw_hz_xy_inner_note(3,0,"B"); drw_hz_xy_inner_note(5,0,"To Run queue:"); drw_hz_xy_inner_note(6,0,"G"); drw_hz_xy_inner_note(7,0,"A"); drw_hz_xy_inner_note(8,0,"B"); drw_hz_xy_inner_note(10,0,"Resources"); drw_hz_xy_inner_note(11,0,"g"); drw_hz_xy_inner_note(12,0,"x"); drw_hz_xy_inner_note(13,0,"a"); drw_hz_xy_inner_note(14,0,"b"); % G running drw_hz_inner_vector(1,1,2,no_hd); drw_hz_inner_vector(1,7,8,no_hd); drw_hz_inner_vector(1,14,15,no_hd); % A running drw_hz_inner_vector(2,3,6,no_hd); drw_hz_inner_vector(2,12,13,no_hd); % B running drw_hz_inner_vector(3,9,11,no_hd); % G to run drw_hz_inner_vector(6,3,6,no_hd); drw_hz_inner_vector(6,9,13,no_hd); % A running drw_hz_inner_vector(7,7,11,no_hd); % resources % g drw_hz_inner_vector(11,1,15,no_hd); % x drw_hz_inner_vector(12,5,6,no_hd); % a drw_hz_inner_vector(13,4,16,no_hd); % b drw_hz_inner_vector(14,10,16,no_hd); % waiting on resource drw_vt_dotted_vector(16,11,13,up_hd); drw_vt_dotted_vector(16,13,14,up_hd); drw_vt_dotted_vector(16,15,11,up_hd); % draw continuity drw_vt_dashed_vector(1,2,2); drw_vt_dashed_vector(2,1,6); drw_vt_dashed_vector(1,3,8); drw_vt_dashed_vector(3,2,11); drw_vt_dashed_vector(2,1,13); % label ownership drw_hz_inner_ownership(11,8,"G"); drw_hz_inner_ownership(12,6,"A"); drw_hz_inner_ownership(13,9,"A"); drw_hz_inner_ownership(14,14,"B"); % X where deadlock occurs %drw_vt_dotted_vector(16,11,13,hd_hd); drw_x_deadlock(16,16); %space labels defaultscale:=1.5; label.bot(btex -------- B Space -------- etex,Sw_outer+(10*Time_unit_size,-3*Time_unit_size)); label.lft(btex -- A Space -- etex,Sw_outer+(0,22*Time_unit_size)); label.rt(btex -- G Space -- etex,Sw_outer+(23*Time_unit_size,22*Time_unit_size)); endfig; end;