Index: doc/theses/colby_parsons_MMAth/Makefile =================================================================== --- doc/theses/colby_parsons_MMAth/Makefile (revision 3397eedebff24a28a10384d4f162bf850c321072) +++ doc/theses/colby_parsons_MMAth/Makefile (revision 4c2e561f46e37c956d59cd5054091612c978e9cd) @@ -23,4 +23,5 @@ text/channels \ text/waituntil \ + text/conclusion \ } Index: doc/theses/colby_parsons_MMAth/diagrams/steal.tikz =================================================================== --- doc/theses/colby_parsons_MMAth/diagrams/steal.tikz (revision 4c2e561f46e37c956d59cd5054091612c978e9cd) +++ doc/theses/colby_parsons_MMAth/diagrams/steal.tikz (revision 4c2e561f46e37c956d59cd5054091612c978e9cd) @@ -0,0 +1,212 @@ + + +\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt + +\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1] +%uncomment if require: \path (0,300); %set diagram left start at 0, and has height of 300 + +%Shape: Rectangle [id:dp1659927180988856] +\draw (106,21) -- (145.43,21) -- (145.43,61) -- (106,61) -- cycle ; +%Shape: Rectangle [id:dp60162597566272] +\draw (111.43,145) -- (111.43,203.29) -- (90.71,203.29) -- (90.71,145) -- cycle ; +%Shape: Rectangle [id:dp00028539200901533945] +\draw (142.71,144) -- (142.71,203.29) -- (121.71,203.29) -- (121.71,144) -- cycle ; +%Shape: Rectangle [id:dp019176495354326972] +\draw (174.43,184.26) -- (174.43,203.11) -- (153.14,203.11) -- (153.14,184.26) -- cycle ; +%Shape: Circle [id:dp7790209479077526] +\draw [fill={rgb, 255:red, 0; green, 0; blue, 0 } ,fill opacity=1 ] (276,170.71) .. controls (276,168.66) and (277.66,167) .. (279.71,167) .. controls (281.77,167) and (283.43,168.66) .. (283.43,170.71) .. controls (283.43,172.77) and (281.77,174.43) .. (279.71,174.43) .. controls (277.66,174.43) and (276,172.77) .. (276,170.71) -- cycle ; +%Shape: Circle [id:dp7009203011691245] +\draw [fill={rgb, 255:red, 0; green, 0; blue, 0 } ,fill opacity=1 ] (286.43,170.71) .. controls (286.43,168.66) and (288.09,167) .. (290.14,167) .. controls (292.19,167) and (293.86,168.66) .. (293.86,170.71) .. controls (293.86,172.77) and (292.19,174.43) .. (290.14,174.43) .. controls (288.09,174.43) and (286.43,172.77) .. (286.43,170.71) -- cycle ; +%Shape: Circle [id:dp13342086511975615] +\draw [fill={rgb, 255:red, 0; green, 0; blue, 0 } ,fill opacity=1 ] (296.86,170.71) .. controls (296.86,168.66) and (298.52,167) .. (300.57,167) .. controls (302.62,167) and (304.29,168.66) .. (304.29,170.71) .. controls (304.29,172.77) and (302.62,174.43) .. (300.57,174.43) .. controls (298.52,174.43) and (296.86,172.77) .. (296.86,170.71) -- cycle ; +%Shape: Rectangle [id:dp5447259154641135] +\draw (153.43,145.43) -- (174.43,145.43) -- (174.43,158.37) -- (153.43,158.37) -- cycle ; +%Shape: Rectangle [id:dp9780910526987703] +\draw (153.43,158.37) -- (174.43,158.37) -- (174.43,171.32) -- (153.43,171.32) -- cycle ; +%Shape: Rectangle [id:dp9823297574958101] +\draw (153.43,171.32) -- (174.43,171.32) -- (174.43,184.26) -- (153.43,184.26) -- cycle ; +%Shape: Rectangle [id:dp26427025317978536] +\draw (186,23) -- (225.43,23) -- (225.43,63) -- (186,63) -- cycle ; +%Shape: Rectangle [id:dp7685803476832467] +\draw (202.43,145) -- (202.43,203.29) -- (181.71,203.29) -- (181.71,145) -- cycle ; +%Shape: Rectangle [id:dp5393850523964543] +\draw (233.71,171.41) -- (233.71,203.29) -- (212.71,203.29) -- (212.71,171.41) -- cycle ; +%Shape: Rectangle [id:dp06125322053208593] +\draw (265.43,184.26) -- (265.43,203.11) -- (244.14,203.11) -- (244.14,184.26) -- cycle ; +%Shape: Rectangle [id:dp210427247172708] +\draw (244.43,145.43) -- (265.43,145.43) -- (265.43,158.37) -- (244.43,158.37) -- cycle ; +%Shape: Rectangle [id:dp4712939573626067] +\draw (244.43,158.37) -- (265.43,158.37) -- (265.43,171.32) -- (244.43,171.32) -- cycle ; +%Shape: Rectangle [id:dp9796535632094827] +\draw (244.43,171.32) -- (265.43,171.32) -- (265.43,184.26) -- (244.43,184.26) -- cycle ; +%Shape: Rectangle [id:dp6920491695751174] +\draw (212.71,145.52) -- (233.71,145.52) -- (233.71,158.46) -- (212.71,158.46) -- cycle ; +%Shape: Rectangle [id:dp9224042481550583] +\draw (212.71,158.46) -- (233.71,158.46) -- (233.71,171.41) -- (212.71,171.41) -- cycle ; +%Shape: Rectangle [id:dp12096171177736381] +\draw (93,82.86) -- (118.2,82.86) -- (118.2,104) -- (93,104) -- cycle ; +%Shape: Rectangle [id:dp298331898093555] +\draw (118.2,82.86) -- (143.4,82.86) -- (143.4,104) -- (118.2,104) -- cycle ; +%Shape: Rectangle [id:dp41953486075473] +\draw (143.4,82.86) -- (168.6,82.86) -- (168.6,104) -- (143.4,104) -- cycle ; +%Shape: Rectangle [id:dp7046873368993529] +\draw (168.6,82.86) -- (193.8,82.86) -- (193.8,104) -- (168.6,104) -- cycle ; +%Shape: Rectangle [id:dp6252678926497113] +\draw (193.8,82.86) -- (219,82.86) -- (219,104) -- (193.8,104) -- cycle ; +%Shape: Rectangle [id:dp4979567338840891] +\draw (219,82.86) -- (244.2,82.86) -- (244.2,104) -- (219,104) -- cycle ; +%Straight Lines [id:da6099834178635517] +\draw (104.2,99) -- (100.37,143.01) ; +\draw [shift={(100.2,145)}, rotate = 274.97] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ; +%Straight Lines [id:da6779754089981487] +\draw (135.2,98) -- (131.37,142.01) ; +\draw [shift={(131.2,144)}, rotate = 274.97] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ; +%Straight Lines [id:da6442265344724993] +\draw (156,93.43) -- (189.09,143.33) ; +\draw [shift={(190.2,145)}, rotate = 236.45] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ; +%Straight Lines [id:da006839088937779403] +\draw (178.43,99.43) -- (164.8,143.09) ; +\draw [shift={(164.2,145)}, rotate = 287.34] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ; +%Straight Lines [id:da0675200137451315] +\draw (206.71,99.52) -- (223.48,143.13) ; +\draw [shift={(224.2,145)}, rotate = 248.97] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ; +%Straight Lines [id:da4849729759948771] +\draw (231.6,93.43) -- (254.19,150.04) ; +\draw [shift={(254.93,151.9)}, rotate = 248.25] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ; +%Curve Lines [id:da03959106193360351] +\draw (93,82.86) .. controls (96.2,60.6) and (127.2,84.6) .. (126.2,60.6) ; +%Curve Lines [id:da6283016522283285] +\draw (168.6,82.86) .. controls (166.2,62.6) and (127.2,84.6) .. (126.2,60.6) ; +%Curve Lines [id:da1266417207786419] +\draw (168.6,82.86) .. controls (169.2,58.6) and (206.2,85.6) .. (205.2,63.6) ; +%Curve Lines [id:da007446453026779265] +\draw (244.2,82.86) .. controls (244.8,58.6) and (206.2,85.6) .. (205.2,63.6) ; +%Shape: Circle [id:dp2807401862026926] +\draw [fill={rgb, 255:red, 0; green, 0; blue, 0 } ,fill opacity=1 ] (253,93.71) .. controls (253,91.66) and (254.66,90) .. (256.71,90) .. controls (258.77,90) and (260.43,91.66) .. (260.43,93.71) .. controls (260.43,95.77) and (258.77,97.43) .. (256.71,97.43) .. controls (254.66,97.43) and (253,95.77) .. (253,93.71) -- cycle ; +%Shape: Circle [id:dp7342173238414365] +\draw [fill={rgb, 255:red, 0; green, 0; blue, 0 } ,fill opacity=1 ] (263.43,93.71) .. controls (263.43,91.66) and (265.09,90) .. (267.14,90) .. controls (269.19,90) and (270.86,91.66) .. (270.86,93.71) .. controls (270.86,95.77) and (269.19,97.43) .. (267.14,97.43) .. controls (265.09,97.43) and (263.43,95.77) .. (263.43,93.71) -- cycle ; +%Shape: Circle [id:dp5314606969014675] +\draw [fill={rgb, 255:red, 0; green, 0; blue, 0 } ,fill opacity=1 ] (273.86,93.71) .. controls (273.86,91.66) and (275.52,90) .. (277.57,90) .. controls (279.62,90) and (281.29,91.66) .. (281.29,93.71) .. controls (281.29,95.77) and (279.62,97.43) .. (277.57,97.43) .. controls (275.52,97.43) and (273.86,95.77) .. (273.86,93.71) -- cycle ; +%Shape: Circle [id:dp9220532132358463] +\draw [fill={rgb, 255:red, 0; green, 0; blue, 0 } ,fill opacity=1 ] (242,41.71) .. controls (242,39.66) and (243.66,38) .. (245.71,38) .. controls (247.77,38) and (249.43,39.66) .. (249.43,41.71) .. controls (249.43,43.77) and (247.77,45.43) .. (245.71,45.43) .. controls (243.66,45.43) and (242,43.77) .. (242,41.71) -- cycle ; +%Shape: Circle [id:dp8147273883297732] +\draw [fill={rgb, 255:red, 0; green, 0; blue, 0 } ,fill opacity=1 ] (252.43,41.71) .. controls (252.43,39.66) and (254.09,38) .. (256.14,38) .. controls (258.19,38) and (259.86,39.66) .. (259.86,41.71) .. controls (259.86,43.77) and (258.19,45.43) .. (256.14,45.43) .. controls (254.09,45.43) and (252.43,43.77) .. (252.43,41.71) -- cycle ; +%Shape: Circle [id:dp04583504383039805] +\draw [fill={rgb, 255:red, 0; green, 0; blue, 0 } ,fill opacity=1 ] (262.86,41.71) .. controls (262.86,39.66) and (264.52,38) .. (266.57,38) .. controls (268.62,38) and (270.29,39.66) .. (270.29,41.71) .. controls (270.29,43.77) and (268.62,45.43) .. (266.57,45.43) .. controls (264.52,45.43) and (262.86,43.77) .. (262.86,41.71) -- cycle ; +%Shape: Rectangle [id:dp26278935632752654] +\draw (456.8,22) -- (496.23,22) -- (496.23,62) -- (456.8,62) -- cycle ; +%Shape: Rectangle [id:dp5253832264115919] +\draw (462.23,146) -- (462.23,204.29) -- (441.51,204.29) -- (441.51,146) -- cycle ; +%Shape: Rectangle [id:dp19337284039858993] +\draw (494.51,145) -- (494.51,204.29) -- (473.51,204.29) -- (473.51,145) -- cycle ; +%Shape: Rectangle [id:dp12109801848615143] +\draw (504.23,146.43) -- (525.23,146.43) -- (525.23,159.37) -- (504.23,159.37) -- cycle ; +%Shape: Rectangle [id:dp029986139125434796] +\draw (504.23,159.37) -- (525.23,159.37) -- (525.23,172.32) -- (504.23,172.32) -- cycle ; +%Shape: Rectangle [id:dp5205073319604256] +\draw (504.23,172.32) -- (525.23,172.32) -- (525.23,204.5) -- (504.23,204.5) -- cycle ; +%Shape: Rectangle [id:dp5392153103190804] +\draw (536.8,24) -- (576.23,24) -- (576.23,64) -- (536.8,64) -- cycle ; +%Shape: Rectangle [id:dp20777203648986298] +\draw (553.23,146) -- (553.23,204.29) -- (532.51,204.29) -- (532.51,146) -- cycle ; +%Shape: Rectangle [id:dp9821766933114229] +\draw (584.51,172.41) -- (584.51,204.29) -- (563.51,204.29) -- (563.51,172.41) -- cycle ; +%Shape: Rectangle [id:dp26278037443005653] +\draw (616.23,185.26) -- (616.23,204.11) -- (594.94,204.11) -- (594.94,185.26) -- cycle ; +%Shape: Rectangle [id:dp7263888129359626] +\draw (595.23,146.43) -- (616.23,146.43) -- (616.23,159.37) -- (595.23,159.37) -- cycle ; +%Shape: Rectangle [id:dp39759929453499376] +\draw (595.23,159.37) -- (616.23,159.37) -- (616.23,172.32) -- (595.23,172.32) -- cycle ; +%Shape: Rectangle [id:dp4139225137390832] +\draw (595.23,172.32) -- (616.23,172.32) -- (616.23,185.26) -- (595.23,185.26) -- cycle ; +%Shape: Rectangle [id:dp5534530289312252] +\draw (563.51,146.52) -- (584.51,146.52) -- (584.51,159.46) -- (563.51,159.46) -- cycle ; +%Shape: Rectangle [id:dp15109524268989016] +\draw (563.51,159.46) -- (584.51,159.46) -- (584.51,172.41) -- (563.51,172.41) -- cycle ; +%Shape: Rectangle [id:dp3260024587356085] +\draw (443.8,83.86) -- (469,83.86) -- (469,105) -- (443.8,105) -- cycle ; +%Shape: Rectangle [id:dp771034531518882] +\draw (469,83.86) -- (494.2,83.86) -- (494.2,105) -- (469,105) -- cycle ; +%Shape: Rectangle [id:dp35395262229310664] +\draw (494.2,83.86) -- (519.4,83.86) -- (519.4,105) -- (494.2,105) -- cycle ; +%Shape: Rectangle [id:dp17684146143997692] +\draw (519.4,83.86) -- (544.6,83.86) -- (544.6,105) -- (519.4,105) -- cycle ; +%Shape: Rectangle [id:dp22681144521939345] +\draw (544.6,83.86) -- (569.8,83.86) -- (569.8,105) -- (544.6,105) -- cycle ; +%Shape: Rectangle [id:dp3401048482705622] +\draw (569.8,83.86) -- (595,83.86) -- (595,105) -- (569.8,105) -- cycle ; +%Straight Lines [id:da5134271301477562] +\draw (455,100) -- (451.17,144.01) ; +\draw [shift={(451,146)}, rotate = 274.97] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ; +%Straight Lines [id:da5852145262435737] +\draw (486,99) -- (482.17,143.01) ; +\draw [shift={(482,145)}, rotate = 274.97] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ; +%Straight Lines [id:da05316401791657244] +\draw [color={rgb, 255:red, 218; green, 15; blue, 15 } ,draw opacity=1 ] (506.8,94.43) -- (572.41,144.29) ; +\draw [shift={(574,145.5)}, rotate = 217.23] [color={rgb, 255:red, 218; green, 15; blue, 15 } ,draw opacity=1 ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ; +%Straight Lines [id:da7304314536476455] +\draw [color={rgb, 255:red, 0; green, 0; blue, 0 } ,draw opacity=1 ] (529.23,100.43) -- (515.6,144.09) ; +\draw [shift={(515,146)}, rotate = 287.34] [color={rgb, 255:red, 0; green, 0; blue, 0 } ,draw opacity=1 ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ; +%Straight Lines [id:da41418908415964717] +\draw [color={rgb, 255:red, 208; green, 2; blue, 27 } ,draw opacity=1 ] (557.51,100.52) -- (541.68,144.12) ; +\draw [shift={(541,146)}, rotate = 289.96] [color={rgb, 255:red, 208; green, 2; blue, 27 } ,draw opacity=1 ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ; +%Straight Lines [id:da0992928490139493] +\draw (582.4,94.43) -- (604.99,151.04) ; +\draw [shift={(605.73,152.9)}, rotate = 248.25] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ; +%Curve Lines [id:da30182495627256767] +\draw (443.8,83.86) .. controls (447,61.6) and (478,85.6) .. (477,61.6) ; +%Curve Lines [id:da2733079278124235] +\draw (519.4,83.86) .. controls (517,63.6) and (478,85.6) .. (477,61.6) ; +%Curve Lines [id:da8525590686816691] +\draw (519.4,83.86) .. controls (520,59.6) and (557,86.6) .. (556,64.6) ; +%Curve Lines [id:da11645227785870849] +\draw (595,83.86) .. controls (595.6,59.6) and (557,86.6) .. (556,64.6) ; +%Right Arrow [id:dp3848885793985928] +\draw (266,115) -- (364.4,115) -- (364.4,105) -- (430,125) -- (364.4,145) -- (364.4,135) -- (266,135) -- cycle ; +%Curve Lines [id:da5861404114416708] +\draw [color={rgb, 255:red, 208; green, 2; blue, 27 } ,draw opacity=1 ] (417,78) .. controls (411.24,116.88) and (503.17,114.75) .. (544.15,126.9) ; +\draw [shift={(549,128.5)}, rotate = 20.22] [color={rgb, 255:red, 208; green, 2; blue, 27 } ,draw opacity=1 ][line width=0.75] (0, 0) circle [x radius= 6.7, y radius= 6.7] ; + +% Text Node +\draw (102,4) node [anchor=north west][inner sep=0.75pt] [align=left] {{\footnotesize Worker 1}}; +% Text Node +\draw (30,166) node [anchor=north west][inner sep=0.75pt] [align=left] {{\footnotesize mailboxes}}; +% Text Node +\draw (96,206) node [anchor=north west][inner sep=0.75pt] [align=left] {{\footnotesize 0}}; +% Text Node +\draw (127,206) node [anchor=north west][inner sep=0.75pt] [align=left] {{\footnotesize 1}}; +% Text Node +\draw (160,206) node [anchor=north west][inner sep=0.75pt] [align=left] {{\footnotesize 2}}; +% Text Node +\draw (188.71,205.29) node [anchor=north west][inner sep=0.75pt] [align=left] {{\footnotesize 3}}; +% Text Node +\draw (220.71,206.29) node [anchor=north west][inner sep=0.75pt] [align=left] {{\footnotesize 4}}; +% Text Node +\draw (252.71,206.29) node [anchor=north west][inner sep=0.75pt] [align=left] {{\footnotesize 5}}; +% Text Node +\draw (6.2,85.86) node [anchor=north west][inner sep=0.75pt] [align=left] {{\footnotesize worker\_queues}}; +% Text Node +\draw (181,3) node [anchor=north west][inner sep=0.75pt] [align=left] {{\footnotesize Worker 2}}; +% Text Node +\draw (452.8,5) node [anchor=north west][inner sep=0.75pt] [align=left] {{\footnotesize Worker 1}}; +% Text Node +\draw (446.8,207) node [anchor=north west][inner sep=0.75pt] [align=left] {{\footnotesize 0}}; +% Text Node +\draw (477.8,207) node [anchor=north west][inner sep=0.75pt] [align=left] {{\footnotesize 1}}; +% Text Node +\draw (510.8,207) node [anchor=north west][inner sep=0.75pt] [align=left] {{\footnotesize 2}}; +% Text Node +\draw (539.51,206.29) node [anchor=north west][inner sep=0.75pt] [align=left] {{\footnotesize 3}}; +% Text Node +\draw (571.51,207.29) node [anchor=north west][inner sep=0.75pt] [align=left] {{\footnotesize 4}}; +% Text Node +\draw (603.51,207.29) node [anchor=north west][inner sep=0.75pt] [align=left] {{\footnotesize 5}}; +% Text Node +\draw (531.8,4) node [anchor=north west][inner sep=0.75pt] [align=left] {{\footnotesize Worker 2}}; +% Text Node +\draw (266,117) node [anchor=north west][inner sep=0.75pt] [align=left] {{\footnotesize worker 1 steals mailbox 4}}; +% Text Node +\draw (346,55) node [anchor=north west][inner sep=0.75pt] [align=left] {{\footnotesize \textcolor[rgb]{0.82,0.01,0.11}{pointers swapped}}\\{\footnotesize \textcolor[rgb]{0.82,0.01,0.11}{during steal}}}; + + +\end{tikzpicture} Index: doc/theses/colby_parsons_MMAth/local.bib =================================================================== --- doc/theses/colby_parsons_MMAth/local.bib (revision 3397eedebff24a28a10384d4f162bf850c321072) +++ doc/theses/colby_parsons_MMAth/local.bib (revision 4c2e561f46e37c956d59cd5054091612c978e9cd) @@ -168,11 +168,4 @@ } -@misc{openmp, - author = "OpenMP", - title = "OPENMP API Specification", - howpublished = {\href{https://www.openmp.org/spec-html/5.0/openmpch1.html}}, - note = "[Online; accessed 23-May-2023]" -} - @techreport{wilson94, title={The suif compiler system: a parallelizing and optimizing research compiler}, Index: doc/theses/colby_parsons_MMAth/text/channels.tex =================================================================== --- doc/theses/colby_parsons_MMAth/text/channels.tex (revision 3397eedebff24a28a10384d4f162bf850c321072) +++ doc/theses/colby_parsons_MMAth/text/channels.tex (revision 4c2e561f46e37c956d59cd5054091612c978e9cd) @@ -80,5 +80,5 @@ This approach is similar to wait morphing for locks~\cite[p.~82]{Butenhof97} and improves performance in a few ways. First, each thread interacting with the channel only acquires and releases the internal channel lock once. -As a result, contention on the internal lock is decreased, as only entering threads compete for the lock as unblocking threads do not reacquire the lock. +As a result, contention on the internal lock is decreased; only entering threads compete for the lock since unblocking threads do not reacquire the lock. The other advantage of Go's wait-morphing approach is that it eliminates the bottleneck of waiting for signalled threads to run. Note, the property of acquiring/releasing the lock only once can also be achieved with a different form of cooperation, called \Newterm{baton passing}. Index: doc/theses/colby_parsons_MMAth/text/conclusion.tex =================================================================== --- doc/theses/colby_parsons_MMAth/text/conclusion.tex (revision 3397eedebff24a28a10384d4f162bf850c321072) +++ doc/theses/colby_parsons_MMAth/text/conclusion.tex (revision 4c2e561f46e37c956d59cd5054091612c978e9cd) @@ -5,8 +5,8 @@ % ====================================================================== This thesis presented a suite of safe and efficient concurrency tools that provide users with the means to write scalable programs in \CFA through many avenues. -If users prefer the message passing paradigm of concurrency, \CFA now provides tools in the form of a performant actor system and channels. +If users prefer the message passing paradigm of concurrency, \CFA now provides message passing tools in the form of a performant actor system and channels. For shared memory concurrency the mutex statement provides a safe and easy-to-use interface for mutual exclusion. -The waituntil statement provided by this works aids in writing concurrent programs in both the message passing and shared memory worlds of concurrency. -Furthermore no other language provides a synchronous multiplexing tool polymorphic over resources like \CFA's waituntil. +The waituntil statement provided by this works aids in writing concurrent programs in both the message passing and shared memory paradigms of concurrency. +Furthermore, no other language provides a synchronous multiplexing tool polymorphic over resources like \CFA's waituntil. From the novel copy queue data structure in the actor system, to the plethora of user-supporting safety features, all these utilities build upon existing tools with value added. @@ -15,14 +15,13 @@ This thesis scratches the surface of implicit concurrency by providing an actor system. There is room for more implicit concurrency tools in \CFA. -User-defined implicit concurrency in the form of annotated loops or recursive functions exists in many other languages and libraries~\cite{uC++,openmp} and could be implemented and expanded on in \CFA. +User-defined implicit concurrency in the form of annotated loops or recursive functions exists in many other languages and libraries~\cite{uC++,OpenMP}. Similar implicit concurrency mechanisms could be implemented and expanded on in \CFA. Additionally, the problem of automatic parallelism of sequential programs via the compiler is an interesting research space that other languages have approached~\cite{wilson94,haskell:parallel} that could also be explored in \CFA. - - -\subsection{Synchronously Multiplexing System Calls} -There are many tools that try to sychronize on or asynchronously check I/O, since improvements in this area pay dividends in many areas of computer science~\cite{linux:select,linux:poll,linux:epoll,linux:iouring}. -Research on improving user-space tools to synchronize over I/O and other system calls is an interesting area to explore in the world of concurrent tooling. \subsection{Advanced Actor Stealing Heuristics} In this thesis, two basic victim selection heuristics were chosen when implementing the work stealing actor system. Good victim selection is an active area of work stealing research, especially when taking into account NUMA effects and cache locality~\cite{barghi18,wolke17}. The actor system in \CFA is modular and exploration of other victim selection heuristics for queue stealing in \CFA could constitute future work. The other question that arises with work stealing is: When should a worker thread steal? Work stealing systems can often be too aggressive when stealing, causing the cost of the steal to be higher than what is saved by sharing the work. In the presented actor system, a worker thread steals work after it checks all its work queues for work twice and sees them all empty. Given that thief threads often have cycles to spare, there is room for a more nuanced approach to choosing when to steal. + +\subsection{Synchronously Multiplexing System Calls} +There are many tools that try to sychronously wait for or asynchronously check I/O, since improvements in this area pay dividends in many areas of computer science~\cite{linux:select,linux:poll,linux:epoll,linux:iouring}. +Research on improving user-space tools to synchronize over I/O and other system calls is an interesting area to explore in the world of concurrent tooling. \subsection{Better Atomic Operations} @@ -34,3 +33,5 @@ The semantics and safety of these builtins require careful navigation since they require the user to have a nuanced understanding of concurrent memory ordering models to pass via flags. Furthermore, these atomics also often require a user to understand how to fence appropriately to ensure correctness. -All these problems and more could benefit from language support, and adding said language support in \CFA could constitute a great research contribution, and allow for easier writing of low-level safe concurrent code. +All these problems and more could benefit from language support in \CFA. +Adding good language support for atomics is a difficult and nuanced problem, which if solved well would allow for easier and safer writing of low-level concurrent code. + Index: doc/theses/colby_parsons_MMAth/text/intro.tex =================================================================== --- doc/theses/colby_parsons_MMAth/text/intro.tex (revision 3397eedebff24a28a10384d4f162bf850c321072) +++ doc/theses/colby_parsons_MMAth/text/intro.tex (revision 4c2e561f46e37c956d59cd5054091612c978e9cd) @@ -13,4 +13,4 @@ The groundwork for concurrent features in \CFA was implemented by Thierry Delisle~\cite{Delisle18}, who contributed the threading system, coroutines, monitors and other tools. This thesis builds on top of that foundation by providing a suite of high-level concurrent features. -The features include a @mutex@ statement, channels and a @waituntil@ statement, and an actor system. +The features include a @mutex@ statement, channels, a @waituntil@ statement, and an actor system. All of these features exist in other programming in some shape or form, however this thesis extends the original ideas by improving performance, productivity, and safety. Index: doc/theses/colby_parsons_MMAth/text/waituntil.tex =================================================================== --- doc/theses/colby_parsons_MMAth/text/waituntil.tex (revision 3397eedebff24a28a10384d4f162bf850c321072) +++ doc/theses/colby_parsons_MMAth/text/waituntil.tex (revision 4c2e561f46e37c956d59cd5054091612c978e9cd) @@ -5,25 +5,32 @@ % ====================================================================== -Consider the following motivational problem that we shall title the bathroom problem. +Consider the following motivating problem. There are @N@ stalls (resources) in a bathroom and there are @M@ people (threads). -Each stall has their own lock since only one person may occupy a stall at a time. -The standard way that humans solve this problem is that they check if the stalls are occupied and if they all are they queue and watch the stalls until one is free and then enter and lock the stall. -This solution is simple in real life, but can be difficult to implement in a concurrent context as it requires the threads to somehow wait on all the stalls at the same time. -The naive solution to this is for each thread to spin indefinitely continually checking the stalls until one is free. -This wastes cycles and also results in no fairness among threads waiting for stalls as a thread will jump in the first stall available without any regard to other waiting threads. -The ability to wait for the first stall available without spinning can be done with concurrent tools that provide \gls{synch_multiplex}, the ability to wait synchronously for a resource or set of resources. +Each stall has its own lock since only one person may occupy a stall at a time. +Humans tend to solve this problem in the following way. +They check if all of the stalls are occupied. +If not they enter and claim an available stall. +If they are all occupied, the people queue and watch the stalls until one is free and then enter and lock the stall. +This solution can be implemented on a computer easily if all threads are waiting on all stalls and agree to queue. +Now the problem is extended. +Some stalls are wheelchair accessible, some stalls are dirty and other stalls are clean. +Each person (thread) may choose some subset of dirty, clean and accessible stalls that they want to wait for. +Immediately the problem becomes much more difficult. +A single queue no longer fully solves the problem: What happens when there is a stall available that the person at the front of the queue will not choose? +The naive solution to this problem has each thread to spin indefinitely continually checking the stalls until an suitable one is free. +This is not good enough since this approach wastes cycles and results in no fairness among threads waiting for stalls as a thread will jump in the first stall available without any regard to other waiting threads. +Waiting for the first stall (resource) available without spinning is an example of \gls{synch_multiplex}, the ability to wait synchronously for a resource or set of resources. \section{History of Synchronous Multiplexing} There is a history of tools that provide \gls{synch_multiplex}. -Some of the most well known include the set of unix system utilities: select(2)\cite{linux:select}, poll(2)\cite{linux:poll}, and epoll(7)\cite{linux:epoll}, and the select statement provided by Go\cite{go:selectref}. - -Before one can examine the history of \gls{synch_multiplex} implementations in detail, the preceding theory must be discussed. -The theory surrounding this topic was largely introduced by Hoare in his 1985 CSP book \cite{Hoare85} and his later work with Roscoe on the theoretical language Occam\cite{Roscoe88}. -Both include guards for communication channels and the ability to wait for a single channel to be ready out of a set of channels. +Some well known \gls{synch_multiplex} tools include unix system utilities: select(2)\cite{linux:select}, poll(2)\cite{linux:poll}, and epoll(7)\cite{linux:epoll}, and the select statement provided by Go\cite{go:selectref}. + +The theory surrounding \gls{synch_multiplex} was largely introduced by Hoare in his 1985 CSP book \cite{Hoare85} and his later work with Roscoe on the theoretical language Occam\cite{Roscoe88}. The work on Occam in \cite{Roscoe88} calls their \gls{synch_multiplex} primitive ALT, which waits for one resource to be available and then executes a corresponding block of code. -Waiting for one resource out of a set of resources can be thought of as a logical exclusive or over the set of resources. +Waiting for one resource out of a set of resources can be thought of as a logical exclusive-or over the set of resources. +Both CSP and Occam include \Newterm{guards} for communication channels and the ability to wait for a single channel to be ready out of a set of channels. Guards are a conditional operator similar to an @if@, except they apply to the resource being waited on. If a guard is false then the resource it guards is considered to not be in the set of resources being waited on. -Guards can be simulated using if statements, but to do so requires \[2^N\] if cases, where @N@ is the number of guards. +Guards can be simulated using if statements, but to do so requires \[2^N\] if statements, where @N@ is the number of guards. The equivalence between guards and exponential if statements comes from an Occam ALT statement rule~\cite{Roscoe88}, which is presented in \CFA syntax in Figure~\ref{f:wu_if}. Providing guards allows for easy toggling of waituntil clauses without introducing repeated code. @@ -31,5 +38,6 @@ \begin{figure} \begin{cfa} -when( predicate ) waituntil( A ) {} +// CFA's guards use the keyword 'when' +when( predicate ) waituntil( A ) {} or waituntil( B ) {} // === @@ -45,24 +53,24 @@ \end{figure} -Switching to implementations, it is important to discuss the resources being multiplexed. -While the aforementioned theory discusses waiting on channels, the earliest known implementation of a synchronous multiplexing tool, Unix's select(2), is multiplexed over file descriptors. -The select(2) system call takes in sets of file descriptors to wait on as arguments and an optional timeout. -Select will block until either some subset of file descriptors are available or the timeout expires. -All file descriptors that are ready will be returned. -This early implementation differs from the theory as when the call from select returns it may provide more than one ready file descriptor. -As such select has a logical or multiplexing semantics, whereas the theory described exclusive-or semantics. +When discussing \gls{synch_multiplex} implementations, one must discuss the resources being multiplexed. +While the aforementioned theory waits on channels, the earliest known implementation of a synchronous multiplexing tool, Unix's select(2)\cite{linux:select}, is multiplexed over file descriptors. +The select(2) system call is passed three sets of file descriptors (read, write, exceptional) to wait on and an optional timeout. +Select(2) will block until either some subset of file descriptors are available or the timeout expires. +All file descriptors that are ready will be returned by modifying the argument sets to only contain the ready descriptors. +This early implementation differs from the theory presented in Occam and CSP; when the call from select(2) returns it may provide more than one ready file descriptor. +As such, select(2) has logical-or multiplexing semantics, whereas the theory described exclusive-or semantics. This is not a drawback. A user can easily achieve exclusive-or semantics with select by arbitrarily choosing only one of the returned descriptors to operate on. -Select was followed by poll(2), and later epoll(7), which both improved upon drawbacks in their predecessors. -The syscall poll(2) improved on select by allowing users to monitor descriptors with numbers higher than 1024 which was not supported by select. -Epoll then improved on poll to return the set of file descriptors since poll would only say that some descriptor from the set was ready but not return which ones were ready. +Select(2) was followed by poll(2), which was later followed by epoll(7), with each successor improving upon drawbacks in their predecessors. +The syscall poll(2) improved on select(2) by allowing users to monitor descriptors with numbers higher than 1024 which was not supported by select. +Epoll(7) then improved on poll(2) to return the set of file descriptors; when one or more descriptors became available poll(2) would return the number of availables descriptors, but would not indicate which descriptors were ready. It is worth noting these \gls{synch_multiplex} tools mentioned so far interact directly with the operating system and are often used to communicate between processes. -Later \gls{synch_multiplex} started to appear in user-space to support fast multiplexed concurrent communication between threads. +Later, \gls{synch_multiplex} started to appear in user-space to support fast multiplexed concurrent communication between threads. An early example of \gls{synch_multiplex} is the select statement in Ada~\cite[\S~9.7]{Ichbiah79}. The select statement in Ada allows a task to multiplex over some subset of its own methods that it would like to @accept@ calls to. -Tasks in Ada can be thought of as threads which are an object of a specific class, and as such have methods, fields, etc. -This statement has the same exclusive-or semantics as ALT from Occam, and supports guards as described in Occam, however it multiplexes over methods on rather than multiplexing over channels. -A code block is associated with each @accept@, and the method that is @accept@ed first has its corresponding code block run after the task unblocks. +Tasks in Ada are essentially objects that have their own thread, and as such have methods, fields, etc. +The Ada select statement has the same exclusive-or semantics and guards as ALT from Occam, however it multiplexes over methods on rather than multiplexing over channels. +A code block is associated with each @accept@, and the method that is accepted first has its corresponding code block run after the task unblocks. In this way the select statement in Ada provides rendezvous points for threads, rather than providing some resource through message passing. The select statement in Ada also supports an optional timeout with the same semantics as select(2), and provides an @else@. @@ -75,5 +83,5 @@ Go provides a timeout utility and also provides a @default@ clause which has the same semantics as Ada's @else@ clause. -\uC provides \gls{synch_multiplex} over futures with their @_Select@ statement and Ada-style \gls{synch_multiplex} over monitor methods with their @_Accept@ statement~\cite{uC++}. +\uC provides \gls{synch_multiplex} over futures with their @_Select@ statement and Ada-style \gls{synch_multiplex} over monitor and task methods with their @_Accept@ statement~\cite{uC++}. Their @_Accept@ statement builds upon the select statement offered by Ada, by offering both @and@ and @or@ semantics, which can be used together in the same statement. These semantics are also supported for \uC's @_Select@ statement. @@ -81,10 +89,10 @@ There are many other languages that provide \gls{synch_multiplex}, including Rust's @select!@ over futures~\cite{rust:select}, OCaml's @select@ over channels~\cite{ocaml:channel}, and C++14's @when_any@ over futures~\cite{cpp:whenany}. -Note that while C++14 and Rust provide \gls{synch_multiplex}, their implemetations leave much to be desired as they both rely on busy-waiting polling to wait on multiple resources. +Note that while C++14 and Rust provide \gls{synch_multiplex}, their implementations leave much to be desired as they both rely on busy-waiting polling to wait on multiple resources. \section{Other Approaches to Synchronous Multiplexing} To avoid the need for \gls{synch_multiplex}, all communication between threads/processes has to come from a single source. One key example is Erlang, in which each process has a single heterogenous mailbox that is the sole source of concurrent communication, removing the need for \gls{synch_multiplex} as there is only one place to wait on resources. -In a similar vein, actor systems circumvent the \gls{synch_multiplex} problem as actors are traditionally non-blocking, so they will only block when waiting for the next message. +In a similar vein, actor systems circumvent the \gls{synch_multiplex} problem as actors are traditionally non-blocking, so they will never block in a behaviour and only block when waiting for the next message. While these approaches solve the \gls{synch_multiplex} problem, they introduce other issues. Consider the case where a thread has a single source of communication (like erlang and actor systems) wants one of a set of @N@ resources. @@ -97,8 +105,7 @@ The new \CFA \gls{synch_multiplex} utility introduced in this work is the @waituntil@ statement. There is a @waitfor@ statement in \CFA that supports Ada-style \gls{synch_multiplex} over monitor methods, so this @waituntil@ focuses on synchronizing over other resources. -All of the \gls{synch_multiplex} features mentioned so far are monomorphic, only supporting one resource to wait on, select(2) supports file descriptors, Go's select supports channel operations, \uC's select supports futures, and Ada's select supports monitor method calls. +All of the \gls{synch_multiplex} features mentioned so far are monomorphic, only supporting one resource to wait on: select(2) supports file descriptors, Go's select supports channel operations, \uC's select supports futures, and Ada's select supports monitor method calls. The waituntil statement in \CFA is polymorphic and provides \gls{synch_multiplex} over any objects that satisfy the trait in Figure~\ref{f:wu_trait}. No other language provides a synchronous multiplexing tool polymorphic over resources like \CFA's waituntil. -All others them tie themselves to some specific type of resource. \begin{figure} @@ -121,5 +128,5 @@ Currently locks, channels, futures and timeouts are supported by the waituntil statement, but this will be expanded as other use cases arise. -The waituntil statement supports guarded clauses, like Ada, and Occam, supports both @or@, and @and@ semantics, like \uC, and provides an @else@ for asynchronous multiplexing. An example of \CFA waituntil usage is shown in Figure~\ref{f:wu_example}. In Figure~\ref{f:wu_example} the waituntil statement is waiting for either @Lock@ to be available or for a value to be read from @Channel@ into @i@ and for @Future@ to be fulfilled. The semantics of the waituntil statement will be discussed in detail in the next section. +The @waituntil@ statement supports guarded clauses, like Ada, and Occam, supports both @or@, and @and@ semantics, like \uC, and provides an @else@ for asynchronous multiplexing. An example of \CFA waituntil usage is shown in Figure~\ref{f:wu_example}. In Figure~\ref{f:wu_example} the waituntil statement is waiting for either @Lock@ to be available or for a value to be read from @Channel@ into @i@ and for @Future@ to be fulfilled. \begin{figure} @@ -140,10 +147,9 @@ \section{Waituntil Semantics} There are two parts of the waituntil semantics to discuss, the semantics of the statement itself, \ie @and@, @or@, @when@ guards, and @else@ semantics, and the semantics of how the waituntil interacts with types like channels, locks and futures. -To start, the semantics of the statement itself will be discussed. \subsection{Waituntil Statement Semantics} The @or@ semantics are the most straightforward and nearly match those laid out in the ALT statement from Occam, the clauses have an exclusive-or relationship where the first one to be available will be run and only one clause is run. \CFA's @or@ semantics differ from ALT semantics in one respect, instead of randomly picking a clause when multiple are available, the clause that appears first in the order of clauses will be picked. -\eg in the following example, if @foo@ and @bar@ are both available, @foo@ will always be selected since it comes first in the order of waituntil clauses. +\eg in the following example, if @foo@ and @bar@ are both available, @foo@ will always be selected since it comes first in the order of @waituntil@ clauses. \begin{cfa} future(int) bar; @@ -154,5 +160,5 @@ The @and@ semantics match the @and@ semantics used by \uC. -When multiple clauses are joined by @and@, the waituntil will make a thread wait for all to be available, but will run the corresponding code blocks \emph{as they become available}. +When multiple clauses are joined by @and@, the @waituntil@ will make a thread wait for all to be available, but will run the corresponding code blocks \emph{as they become available}. As @and@ clauses are made available, the thread will be woken to run those clauses' code blocks and then the thread will wait again until all clauses have been run. This allows work to be done in parallel while synchronizing over a set of resources, and furthermore gives a good reason to use the @and@ operator. @@ -168,8 +174,8 @@ The guards in the waituntil statement are called @when@ clauses. -The @when@ clause is passed a boolean expression. -All the @when@ boolean expressions are evaluated before the waituntil statement is run. +Each the boolean expression inside a @when@ is evaluated once before the waituntil statement is run. The guards in Occam's ALT effectively toggle clauses on and off, where a clause will only be evaluated and waited on if the corresponding guard is @true@. The guards in the waituntil statement operate the same way, but require some nuance since both @and@ and @or@ operators are supported. +This will be discussed further in Section~\ref{s:wu_guards}. When a guard is false and a clause is removed, it can be thought of as removing that clause and its preceding operator from the statement. \eg in the following example the two waituntil statements are semantically the same. @@ -190,5 +196,5 @@ The waituntil statement expects types to register and unregister themselves via calls to @register_select@ and @unregister_select@ respectively. When a resource becomes available, @on_selected@ is run. -Many types may not need @on_selected@, but it is provided since some types may need to check and set things before the resource can be accessed in the code block. +Many types do not need @on_selected@, but it is provided since some types may need to perform some work or checks before the resource can be accessed in the code block. The register/unregister routines in the trait return booleans. The return value of @register_select@ is @true@ if the resource is immediately available, and @false@ otherwise. @@ -200,22 +206,31 @@ The waituntil statement is not inherently complex, and can be described as a few steps. The complexity of the statement comes from the consideration of race conditions and synchronization needed when supporting various primitives. -The basic steps that the waituntil statement follows are the following. - +The basic steps of the waituntil statement are the following: + +\begin{enumerate}[topsep=5pt,itemsep=3pt,parsep=0pt] + +\item First the waituntil statement creates a @select_node@ per resource that is being waited on. The @select_node@ is an object that stores the waituntil data pertaining to one of the resources. + +\item Then, each @select_node@ is then registered with the corresponding resource. -The thread executing the waituntil then enters a loop that will loop until the entire waituntil statement being satisfied. + +\item +The thread executing the waituntil then enters a loop that will loop until the @waituntil@ statement's predicate is satisfied. In each iteration of the loop the thread attempts to block. If any clauses are satified the block will fail and the thread will proceed, otherwise the block succeeds. After proceeding past the block all clauses are checked for completion and the completed clauses have their code blocks run. +In the case where the block suceeds, the thread will be woken by the thread that marks one of the resources as available. + +\item Once the thread escapes the loop, the @select_nodes@ are unregistered from the resources. -In the case where the block suceeds, the thread will be woken by the thread that marks one of the resources as available. +\end{enumerate} Pseudocode detailing these steps is presented in the following code block. - \begin{cfa} select_nodes s[N]; // N select nodes for ( node in s ) register_select( resource, node ); -while( statement not satisfied ) { +while( statement predicate not satisfied ) { // try to block for ( resource in waituntil statement ) @@ -225,10 +240,9 @@ unregister_select( resource, node ); \end{cfa} - -These steps give a basic, but mildly inaccurate overview of how the statement works. -Digging into some parts of the implementation will shed light on more of the specifics and provide some accuracy. +These steps give a basic overview of how the statement works. +Digging into parts of the implementation will shed light on the specifics and provide more detail. \subsection{Locks} -Locks are one of the resources supported in the waituntil statement. +Locks are one of the resources supported by the @waituntil@ statement. When a thread waits on multiple locks via a waituntil, it enqueues a @select_node@ in each of the lock's waiting queues. When a @select_node@ reaches the front of the queue and gains ownership of a lock, the blocked thread is notified. @@ -248,19 +262,20 @@ \end{cfa} -The timeout implementation highlights a key part of the waituntil semantics, the expression is evaluated before the waituntil runs. -As such calls to @sleep@ and @timeout@ do not block, but instead return a type that supports the @is_selectable@ trait. -This mechanism is needed for types that want to support multiple operations such as channels that support reading and writing. +The timeout implementation highlights a key part of the waituntil semantics, the expression inside a @waituntil()@ is evaluated once at the start of the @waituntil@ algorithm. +As such, calls to these @sleep@ and @timeout@ routines do not block, but instead return a type that supports the @is_selectable@ trait. +This feature leverages \CFA's ability to overload on return type; a call to @sleep@ outside a waituntil will call a different @sleep@ that does not return a type, which will block for the appropriate duration. +This mechanism of returning a selectable type is needed for types that want to support multiple operations such as channels that allow both reading and writing. \subsection{Channels}\label{s:wu_chans} -To support both waiting on both reading and writing to channels, the opperators @?<>?@ are used to show reading and writing to a channel respectively, where the lefthand operand is the value and the righthand operand is the channel. -Channels require significant complexity to wait on for a few reasons. -The first reason is that reading or writing to a channel is a mutating operation. -What this means is that if a read or write to a channel occurs, the state of the channel has changed. -In comparison, for standard locks and futures, if a lock is acquired then released or a future is ready but not accessed, the states of the lock and the future are not modified. -In this way if a waituntil over locks or futures have some resources available that were not consumed, it is not an issue. +To support both waiting on both reading and writing to channels, the operators @?<>?@ are used read and write to a channel respectively, where the lefthand operand is the value being read into/written and the righthand operand is the channel. +Channels require significant complexity to synchronously multiplex on for a few reasons. +First, reading or writing to a channel is a mutating operation; +If a read or write to a channel occurs, the state of the channel has changed. +In comparison, for standard locks and futures, if a lock is acquired then released or a future is ready but not accessed, the state of the lock and the future is not permanently modified. +In this way, a waituntil over locks or futures that completes with resources available but not consumed is not an issue. However, if a thread modifies a channel on behalf of a thread blocked on a waituntil statement, it is important that the corresponding waituntil code block is run, otherwise there is a potentially erroneous mismatch between the channel state and associated side effects. As such, the @unregister_select@ routine has a boolean return that is used by channels to indicate when the operation was completed but the block was not run yet. -As such some channel code blocks may be run as part of the unregister. -Furthermore if there are both @and@ and @or@ operators, the @or@ operators stop behaving like exclusive-or semantics since this race between operations and unregisters exists. +When the return is @true@, the corresponding code block is run after the unregister. +Furthermore, if both @and@ and @or@ operators are used, the @or@ operators have to stop behaving like exclusive-or semantics due to the race between channel operations and unregisters. It was deemed important that exclusive-or semantics were maintained when only @or@ operators were used, so this situation has been special-cased, and is handled by having all clauses race to set a value \emph{before} operating on the channel. @@ -279,23 +294,22 @@ However, due to TOCTOU issues, one cannot know that all resources are available without acquiring all the internal locks of channels in the subtree. This is not a good solution for two reasons. -It is possible that once all the locks are acquired that the subtree is not satisfied and they must all be released. -This would incur high cost for signalling threads and also heavily increase contention on internal channel locks. -Furthermore, the waituntil statement is polymorphic and can support resources that do not have internal locks, which also makes this approach infeasible. +It is possible that once all the locks are acquired the subtree is not satisfied and the locks must all be released. +This would incur a high cost for signalling threads and heavily increase contention on internal channel locks. +Furthermore, the @waituntil@ statement is polymorphic and can support resources that do not have internal locks, which also makes this approach infeasible. As such, the exclusive-or semantics are lost when using both @and@ and @or@ operators since they can not be supported without significant complexity and hits to waituntil statement performance. -The mechanism by which the predicate of the waituntil is checked is discussed in more detail in Section~\ref{s:wu_guards}. - -Another consideration introduced by channels is that supporting both reading and writing to a channel in a waituntil means that one waituntil clause may be the notifier for another waituntil clause. -This becomes a problem when dealing with the special-cased @or@ where the clauses need to win a race to operate on a channel. -When you have both a special-case @or@ inserting on one thread and another special-case @or@ consuming is blocked on another thread there is not one but two races that need to be consolidated by the inserting thread. -(The race can occur in the opposite case with a blocked producer and signalling consumer too.) -For them to know that the insert succeeded, they need to win the race for their own waituntil and win the race for the other waituntil. +Channels introduce another interesting consideration in their implementation. +Supporting both reading and writing to a channel in A @waituntil@ means that one @waituntil@ clause may be the notifier for another @waituntil@ clause. +This poses a problem when dealing with the special-cased @or@ where the clauses need to win a race to operate on a channel. +When both a special-case @or@ is inserting to a channel on one thread and another thread is blocked in a special-case @or@ consuming from the same channel there is not one but two races that need to be consolidated by the inserting thread. +(This race can also occur in the mirrored case with a blocked producer and signalling consumer.) +For the producing thread to know that the insert succeeded, they need to win the race for their own waituntil and win the race for the other waituntil. + Go solves this problem in their select statement by acquiring the internal locks of all channels before registering the select on the channels. This eliminates the race since no other threads can operate on the blocked channel since its lock will be held. - This approach is not used in \CFA since the waituntil is polymorphic. Not all types in a waituntil have an internal lock, and when using non-channel types acquiring all the locks incurs extra uneeded overhead. Instead this race is consolidated in \CFA in two phases by having an intermediate pending status value for the race. -This case is detectable, and if detected the thread attempting to signal will first race to set the race flag to be pending. +This race case is detectable, and if detected the thread attempting to signal will first race to set the race flag to be pending. If it succeeds, it then attempts to set the consumer's race flag to its success value. If the producer successfully sets the consumer race flag, then the operation can proceed, if not the signalling thread will set its own race flag back to the initial value. @@ -311,18 +325,18 @@ In \uC and \CFA, their \gls{synch_multiplex} utilities involve both an @and@ and @or@ operator, which make the problem of checking for completion of the statement more difficult. -In the \uC @_Select@ statement, they solve this problem by constructing a tree of the resources, where the internal nodes are operators and the leafs are the resources. -The internal nodes also store the status of each of the subtrees beneath them. -When resources become available, their status is modified and the status of the leaf nodes percolate into the internal nodes update the state of the statement. +In the \uC @_Select@ statement, this problem is solved by constructing a tree of the resources, where the internal nodes are operators and the leaves are booleans storing the state of each resource. +The internal nodes also store the statuses of the two subtrees beneath them. +When resources become available, their corresponding leaf node status is modified and then percolates up into the internal nodes to update the state of the statement. Once the root of the tree has both subtrees marked as @true@ then the statement is complete. -As an optimization, when the internal nodes are updated, their subtrees marked as @true@ are effectively pruned and are not touched again. -To support \uC's @_Select@ statement guards, the tree prunes the branch if the guard is false. +As an optimization, when the internal nodes are updated, their subtrees marked as @true@ are pruned and are not touched again. +To support statement guards in \uC, the tree prunes a branch if the corresponding guard is false. The \CFA waituntil statement blocks a thread until a set of resources have become available that satisfy the underlying predicate. The waiting condition of the waituntil statement can be represented as a predicate over the resources, joined by the waituntil operators, where a resource is @true@ if it is available, and @false@ otherwise. In \CFA, this representation is used as the mechanism to check if a thread is done waiting on the waituntil. -Leveraging the compiler, a routine is generated per waituntil that is passed the statuses of the resources and returns a boolean that is @true@ when the waituntil is done, and false otherwise. -To support guards on the \CFA waituntil statement, the status of a resource disabled by a guard is set to ensure that the predicate function behaves as if that resource is no longer part of the predicate. - -In \uC's @_Select@, it supports operators both inside and outside the clauses of their statement. +Leveraging the compiler, a predicate routine is generated per waituntil that when passed the statuses of the resources, returns @true@ when the waituntil is done, and false otherwise. +To support guards on the \CFA waituntil statement, the status of a resource disabled by a guard is set to a boolean value that ensures that the predicate function behaves as if that resource is no longer part of the predicate. + +\uC's @_Select@, supports operators both inside and outside of the clauses. \eg in the following example the code blocks will run once their corresponding predicate inside the round braces is satisfied. @@ -335,6 +349,6 @@ This is more expressive that the waituntil statement in \CFA. -In \CFA, since the waituntil statement supports more resources than just futures, implmenting operators inside clauses was avoided for a few reasons. -As an example, suppose \CFA supported operators inside clauses and consider the code snippet in Figure~\ref{f:wu_inside_op}. +In \CFA, since the waituntil statement supports more resources than just futures, implementing operators inside clauses was avoided for a few reasons. +As a motivating example, suppose \CFA supported operators inside clauses and consider the code snippet in Figure~\ref{f:wu_inside_op}. \begin{figure} @@ -349,5 +363,5 @@ If the waituntil in Figure~\ref{f:wu_inside_op} works with the same semantics as described and acquires each lock as it becomes available, it opens itself up to possible deadlocks since it is now holding locks and waiting on other resources. -As such other semantics would be needed to ensure that this operation is safe. +Other semantics would be needed to ensure that this operation is safe. One possibility is to use \CC's @scoped_lock@ approach that was described in Section~\ref{s:DeadlockAvoidance}, however the potential for livelock leaves much to be desired. Another possibility would be to use resource ordering similar to \CFA's @mutex@ statement, but that alone is not sufficient if the resource ordering is not used everywhere. @@ -356,8 +370,8 @@ If all the locks are available, it becomes complex to both respect the ordering of the waituntil in Figure~\ref{f:wu_inside_op} when choosing which code block to run and also respect the lock ordering of @D@, @B@, @C@, @A@ at the same time. One other way this could be implemented is to wait until all resources for a given clause are available before proceeding to acquire them, but this also quickly becomes a poor approach. -This approach won't work due to TOCTOU issues, as it is not possible to ensure that the full set resources are available without holding them all first. +This approach won't work due to TOCTOU issues; it is not possible to ensure that the full set resources are available without holding them all first. Operators inside clauses in \CFA could potentially be implemented with careful circumvention of the problems involved, but it was not deemed an important feature when taking into account the runtime cost that would need to be paid to handle these situations. The problem of operators inside clauses also becomes a difficult issue to handle when supporting channels. -If internal operators were supported, it would require some way to ensure that channels with internal operators are modified on if and only if the corresponding code block is run, but that is not feasible due to reasons described in the exclusive-or portion of Section~\ref{s:wu_chans}. +If internal operators were supported, it would require some way to ensure that channels used with internal operators are modified on if and only if the corresponding code block is run, but that is not feasible due to reasons described in the exclusive-or portion of Section~\ref{s:wu_chans}. \section{Waituntil Performance} @@ -366,8 +380,8 @@ The similar utilities discussed at the start of this chapter in C, Ada, Rust, \CC, and OCaml are either not meaningful or feasible to benchmark against. The select(2) and related utilities in C are not comparable since they are system calls that go into the kernel and operate on file descriptors, whereas the waituntil exists solely in userspace. -Ada's @select@ only operates on methods, which is done in \CFA via the @waitfor@ utility so it is not feasible to benchmark against the @waituntil@, which cannot wait on the same resource. -Rust and \CC only offer a busy-wait based approach which is not meaningly comparable to a blocking approach. -OCaml's @select@ waits on channels that are not comparable with \CFA and Go channels, which makes the OCaml @select@ infeasible to compare it with Go's @select@ and \CFA's @waituntil@. -Given the differences in features, polymorphism, and expressibility between the waituntil and @select@, and @_Select@, the aim of the microbenchmarking in this chapter is to show that these implementations lie in the same realm of performance, not to pick a winner. +Ada's @select@ only operates on methods, which is done in \CFA via the @waitfor@ utility so it is not meaningful to benchmark against the @waituntil@, which cannot wait on the same resource. +Rust and \CC only offer a busy-wait based approach which is not comparable to a blocking approach. +OCaml's @select@ waits on channels that are not comparable with \CFA and Go channels, so OCaml @select@ is not benchmarked against Go's @select@ and \CFA's @waituntil@. +Given the differences in features, polymorphism, and expressibility between @waituntil@ and @select@, and @_Select@, the aim of the microbenchmarking in this chapter is to show that these implementations lie in the same realm of performance, not to pick a winner. \subsection{Channel Benchmark} Index: doc/theses/colby_parsons_MMAth/thesis.tex =================================================================== --- doc/theses/colby_parsons_MMAth/thesis.tex (revision 3397eedebff24a28a10384d4f162bf850c321072) +++ doc/theses/colby_parsons_MMAth/thesis.tex (revision 4c2e561f46e37c956d59cd5054091612c978e9cd) @@ -206,4 +206,6 @@ \input{waituntil} +\input{conclusion} + %---------------------------------------------------------------------- % END MATERIAL Index: src/Common/ScopedMap.h =================================================================== --- src/Common/ScopedMap.h (revision 3397eedebff24a28a10384d4f162bf850c321072) +++ src/Common/ScopedMap.h (revision 4c2e561f46e37c956d59cd5054091612c978e9cd) @@ -199,7 +199,6 @@ friend class ScopedMap; friend class const_iterator; - typedef typename ScopedMap::MapType::iterator wrapped_iterator; - typedef typename ScopedMap::ScopeList scope_list; - typedef typename scope_list::size_type size_type; + typedef typename MapType::iterator wrapped_iterator; + typedef typename ScopeList::size_type size_type; /// Checks if this iterator points to a valid item @@ -220,5 +219,5 @@ } - iterator(scope_list & _scopes, const wrapped_iterator & _it, size_type inLevel) + iterator(ScopeList & _scopes, const wrapped_iterator & _it, size_type inLevel) : scopes(&_scopes), it(_it), level(inLevel) {} public: @@ -266,5 +265,5 @@ private: - scope_list *scopes; + ScopeList *scopes; wrapped_iterator it; size_type level; Index: src/Concurrency/KeywordsNew.cpp =================================================================== --- src/Concurrency/KeywordsNew.cpp (revision 3397eedebff24a28a10384d4f162bf850c321072) +++ src/Concurrency/KeywordsNew.cpp (revision 4c2e561f46e37c956d59cd5054091612c978e9cd) @@ -534,8 +534,11 @@ void ConcurrentSueKeyword::addGetRoutines( const ast::ObjectDecl * field, const ast::FunctionDecl * forward ) { + // Clone the signature and then build the body. + ast::FunctionDecl * decl = ast::deepCopy( forward ); + // Say it is generated at the "same" places as the forward declaration. - const CodeLocation & location = forward->location; - - const ast::DeclWithType * param = forward->params.front(); + const CodeLocation & location = decl->location; + + const ast::DeclWithType * param = decl->params.front(); ast::Stmt * stmt = new ast::ReturnStmt( location, new ast::AddressExpr( location, @@ -551,5 +554,4 @@ ); - ast::FunctionDecl * decl = ast::deepCopy( forward ); decl->stmts = new ast::CompoundStmt( location, { stmt } ); declsToAddAfter.push_back( decl ); Index: src/GenPoly/ErasableScopedMap.h =================================================================== --- src/GenPoly/ErasableScopedMap.h (revision 3397eedebff24a28a10384d4f162bf850c321072) +++ src/GenPoly/ErasableScopedMap.h (revision 4c2e561f46e37c956d59cd5054091612c978e9cd) @@ -57,6 +57,5 @@ /// Starts a new scope void beginScope() { - Scope scope; - scopes.push_back(scope); + scopes.emplace_back(); } @@ -145,7 +144,6 @@ public std::iterator< std::bidirectional_iterator_tag, value_type > { friend class ErasableScopedMap; - typedef typename std::map< Key, Value >::iterator wrapped_iterator; - typedef typename std::vector< std::map< Key, Value > > scope_list; - typedef typename scope_list::size_type size_type; + typedef typename Scope::iterator wrapped_iterator; + typedef typename ScopeList::size_type size_type; /// Checks if this iterator points to a valid item Index: src/GenPoly/ScopedSet.h =================================================================== --- src/GenPoly/ScopedSet.h (revision 3397eedebff24a28a10384d4f162bf850c321072) +++ src/GenPoly/ScopedSet.h (revision 4c2e561f46e37c956d59cd5054091612c978e9cd) @@ -47,6 +47,5 @@ /// Starts a new scope void beginScope() { - Scope scope; - scopes.push_back(scope); + scopes.emplace_back(); } @@ -85,5 +84,5 @@ iterator findNext( const_iterator &it, const Value &key ) { if ( it.i == 0 ) return end(); - for ( size_type i = it.i - 1; ; --i ) { + for ( size_type i = it.i - 1; ; --i ) { typename Scope::iterator val = scopes[i].find( key ); if ( val != scopes[i].end() ) return iterator( scopes, val, i ); @@ -112,7 +111,6 @@ friend class ScopedSet; friend class const_iterator; - typedef typename std::set< Value >::iterator wrapped_iterator; - typedef typename std::vector< std::set< Value > > scope_list; - typedef typename scope_list::size_type size_type; + typedef typename Scope::iterator wrapped_iterator; + typedef typename ScopeList::size_type size_type; /// Checks if this iterator points to a valid item @@ -133,5 +131,5 @@ } - iterator(scope_list const &_scopes, const wrapped_iterator &_it, size_type _i) + iterator(ScopeList const &_scopes, const wrapped_iterator &_it, size_type _i) : scopes(&_scopes), it(_it), i(_i) {} public: @@ -176,5 +174,5 @@ private: - scope_list const *scopes; + ScopeList const *scopes; wrapped_iterator it; size_type i; @@ -185,8 +183,7 @@ public std::iterator< std::bidirectional_iterator_tag, value_type > { friend class ScopedSet; - typedef typename std::set< Value >::iterator wrapped_iterator; - typedef typename std::set< Value >::const_iterator wrapped_const_iterator; - typedef typename std::vector< std::set< Value > > scope_list; - typedef typename scope_list::size_type size_type; + typedef typename Scope::iterator wrapped_iterator; + typedef typename Scope::const_iterator wrapped_const_iterator; + typedef typename ScopeList::size_type size_type; /// Checks if this iterator points to a valid item @@ -207,5 +204,5 @@ } - const_iterator(scope_list const &_scopes, const wrapped_const_iterator &_it, size_type _i) + const_iterator(ScopeList const &_scopes, const wrapped_const_iterator &_it, size_type _i) : scopes(&_scopes), it(_it), i(_i) {} public: @@ -255,5 +252,5 @@ private: - scope_list const *scopes; + ScopeList const *scopes; wrapped_const_iterator it; size_type i; Index: src/SymTab/FixFunction.cc =================================================================== --- src/SymTab/FixFunction.cc (revision 3397eedebff24a28a10384d4f162bf850c321072) +++ src/SymTab/FixFunction.cc (revision 4c2e561f46e37c956d59cd5054091612c978e9cd) @@ -109,6 +109,8 @@ const ast::DeclWithType * postvisit( const ast::FunctionDecl * func ) { - return new ast::ObjectDecl{ - func->location, func->name, new ast::PointerType{ func->type }, nullptr, + // Cannot handle cases with asserions. + assert( func->assertions.empty() ); + return new ast::ObjectDecl{ + func->location, func->name, new ast::PointerType( func->type ), nullptr, func->storage, func->linkage, nullptr, copy( func->attributes ) }; } @@ -117,6 +119,6 @@ const ast::Type * postvisit( const ast::ArrayType * array ) { - return new ast::PointerType{ - array->base, array->dimension, array->isVarLen, array->isStatic, + return new ast::PointerType{ + array->base, array->dimension, array->isVarLen, array->isStatic, array->qualifiers }; }