%!PS-Adobe-2.0 %%Creator: dvips by Radical Eye Software %%Pages: 11 1 %%BoundingBox: 0 0 612 792 %%EndComments %%BeginDocument: tex.pro /TeXDict 200 dict def TeXDict begin /bdf{bind def}def /bop-aux{}bdf /@rigin{ /@page-height exch def /@page-width exch def 72 Resolution div dup neg scale translate}bdf /@letter{Resolution dup -10 mul 8.5 11 @rigin}bdf /@landscape{[ 0 1 -1 0 0 0]concat Resolution dup 8.5 11 @rigin}bdf /@a4{Resolution dup -10.6929133858 mul 21 2.54 div 29.7 2.54 div @rigin}bdf /@legal{Resolution dup -13 mul 8.5 14 @rigin}bdf /@11x17{statusdict /11x17tray known{statusdict begin 11x17tray end}if Resolution dup -16 mul 11 17 @rigin}bdf /@manualfeed{ statusdict /manualfeed true put}bdf /@copies{/#copies exch def}bdf /@draft{ /bop-aux{gsave initmatrix 72 dup scale @page-width 2 div @page-height 2 div translate @page-height @page-width atan rotate /Helvetica-Bold findfont 2 scalefont setfont(DRAFT)dup stringwidth pop 2 div neg -1 moveto .95 setgray show grestore}bdf}bdf /@FontMatrix[1 0 0 -1 0 0]def /@FontBBox[0 0 0 0]def /dmystr(ZZf@@@)def /newname{dmystr cvn}bdf /df{/fontname exch def dmystr 2 fontname cvx(@@@@)cvs putinterval newname 7 dict def newname load begin /FontType 3 def /FontMatrix @FontMatrix def /FontBBox @FontBBox def /BitMaps 256 array def /BuildChar{CharBuilder}def /Encoding IdentityEncoding def end fontname{/foo setfont}2 array copy cvx def fontname load 0 dmystr 6 string copy cvn cvx put}bdf /dfe{newname dup load definefont setfont}bdf /ch-image{ ch-data 0 get}bdf /ch-width{ch-data 1 get}bdf /ch-height{ch-data 2 get}bdf /ch-xoff{ch-data 3 get}bdf /ch-yoff{ch-data 4 get}bdf /ch-dx{ch-data 5 get} bdf /CharBuilder{save 3 1 roll exch /BitMaps get exch get /ch-data exch def ch-data null ne{ch-dx 0 ch-xoff ch-yoff neg ch-xoff ch-width add ch-height ch-yoff sub setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-height ch-yoff sub .1 add]{ch-image}imagemask}if restore}bdf /dc{/ch-code exch def /ch-data exch def newname load /BitMaps get ch-code ch-data put}bdf /bop{gsave /SaveImage save def /bop-aux load exec 0 0 moveto}bdf /eop{clear SaveImage restore showpage grestore}bdf /@start{/Resolution exch def /IdentityEncoding 256 array def 0 1 255{IdentityEncoding exch 1 string dup 0 3 index put cvn put}for}bdf /p{show}bdf /RuleMatrix[1 0 0 -1 -.1 -.1]def /BlackDots 8 string def /v{gsave currentpoint translate false RuleMatrix{ BlackDots}imagemask grestore}bdf /a{moveto}bdf /delta 0 def /tail{dup /delta exch def 0 rmoveto}bdf /b{exch show tail}bdf /c{show delta 4 sub tail}bdf /d{ show delta 3 sub tail}bdf /e{show delta 2 sub tail}bdf /f{show delta 1 sub tail}bdf /g{show delta 0 rmoveto}bdf /h{show delta 1 add tail}bdf /i{show delta 2 add tail}bdf /j{show delta 3 add tail}bdf /k{show delta 4 add tail} bdf /l{show -4 0 rmoveto}bdf /m{show -3 0 rmoveto}bdf /n{show -2 0 rmoveto} bdf /o{show -1 0 rmoveto}bdf /q{show 1 0 rmoveto}bdf /r{show 2 0 rmoveto}bdf /s{show 3 0 rmoveto}bdf /t{show 4 0 rmoveto}bdf /w{0 rmoveto}bdf /x{0 exch rmoveto}bdf /y{3 2 roll show moveto}bdf /bos{/section save def}bdf /eos{clear section restore}bdf end %%EndDocument TeXDict begin 300 @start /fa df[<183C3C1C08080810204080>6 11 8 -15 12]39 dc[< 000400180030006000C0008001800300030006000E000C001C0018001800380030003000700070 00600060006000E000E000E000C000C000C000C000C0006000600060002000300010000800>14 38 5 10 16]40 dc[<004000600020003000100018001800180018001800180018001800180018 0018003800380030003000700070006000E000C000C001C0018003800300060006000C00180010 00200040008000>13 38 1 10 16]41 dc[9 3 3 -6 14]45 dc[<007C000186 000303000603000C03801C03801C0380380380380380380380700700700700700700700700E00E 00E00E00E00E00E01C00E01C00E01800E0300060600030C0001F0000>17 24 4 0 20]48 dc[< 000800180030007001F00E7000E000E000E000E001C001C001C001C00380038003800380070007 00070007000F00FFF0>13 24 4 0 20]49 dc[<007C0001860002030004038004838008838010 83801083801083801107001207000C0E00001C000030000060000180000200000C000010010020 01003C060067FE00C1FC0080F000>17 24 3 0 20]50 dc[<003E0000C3000101800201800481 C00441C0088380048380070300000600000C0001F000001800000C00000C00000E00000E00600E 00E01C00E01C0080380040300020E0001F8000>18 24 3 0 20]51 dc[<000300000380000700 000700000700000E00000E00000E00001C00001C0000180000300000300000600000C00000C600 018E00030E00021C00041C00081C00101C007FB800807F80003800003800007000007000007000 007000006000>17 31 1 7 20]52 dc[<001F000060800180800303800603800E00001C000018 000038000039F000721800740C00780E00700E00F00E00E00E00E00E00E00E00E01C00E01C0060 380060700030C0001F8000>17 24 4 0 20]54 dc[<003E0000C1000100800200C00600C00600 C00E018007030007860003CC0001F00001F800067C000C3E00180E00300700600700600700C006 00C00600600C006018003070000FC000>18 24 3 0 20]56 dc[<007C000186000703000E0300 0C03801C0380380380380380380380380780380700380F001817000C270007CE00000E00000C00 001C00001800E03000E0600080C000C380003E0000>17 24 4 0 20]57 dc[<060F1E0C000000 00000000003078F060>8 16 4 0 12]58 dc[<0000200000600000600000E00001E00001E00002 7000027000047000087000087000107000107000207000207000407000807000FFF00100380100 380200380400380400380C00381C0038FF01FF>24 26 2 0 29]65 dc[<000F8200706200C016 03801E07000C0E000C1C000C18000C380008300008700000700000E00000E00000E00000E00000 E00020E00020E00020E000406000406000803001001006000C180003E000>23 26 6 0 27]67 dc[<03FFFF00700700700300700100E00100E00100E00100E00101C08001C08001C08001C18003 FF000381000381000381000702000700040700040700080E00080E00180E00100E00301C00E0FF FFE0>24 26 3 0 26]69 dc[<03FFFF00700700700300700100E00100E00100E00100E00101C0 8001C08001C08001C18003FF000381000381000381000702000700000700000700000E00000E00 000E00000E00001E0000FFE000>24 26 3 0 25]70 dc[<01FF80003800003800003800007000 00700000700000700000E00000E00000E00000E00001C00001C00001C00001C000038000038000 0380000380000700000700000700000700000E0000FFE000>17 26 2 0 15]73 dc[<03FF8000 700000700000700000E00000E00000E00000E00001C00001C00001C00001C00003800003800003 80000380000700000700100700100700200E00200E00600E00400E00C01C0380FFFF80>20 26 3 0 24]76 dc[<03F8001FC00078003C000078003C000078005C0000B800B80000B800B800009C01 3800009C013800011C027000011C027000011C047000011C087000021C08E000021C10E000021C 10E000021C20E000041C41C000041C41C000041C81C000041C81C000080F038000080F03800008 0E038000180C038000380C070000FF083FF000>34 26 3 0 34]77 dc[<03F007F8007801C000 78008000780080009C0100009C0100009C0100008E0100010E0200010602000107020001070200 0203840002038400020384000201C4000401C8000401C8000400E8000400E8000800F000080070 00080070001800700038002000FF002000>29 26 3 0 29]78 dc[<001F8000706001C0300300 1806001C0E000C1C000C18000E38000E30000E70000E70000EE0001CE0001CE0001CE00038E000 38E00030E00070E000E0E000C06001807003003806001C1C0007E000>23 26 6 0 29]79 dc[< 03FFF800701C00700600700700E00700E00700E00700E00701C00E01C00E01C01C01C038038070 03FF800380000380000700000700000700000700000E00000E00000E00000E00001C0000FFC000 >24 26 3 0 26]80 dc[<03FFF000701C00700E00700700E00700E00700E00700E00701C00E01 C01C01C03801C0E003FF800380C00380600380700700700700700700700700700E00E00E00E00E 00E10E00E21C0062FFC03C>24 26 3 0 28]82 dc[<003F100060900180700100700300200600 2006002006002006000007000007C00003F80001FE00007F00000F800003800001800001802001 80200180600300600300600600700C00C8180087E000>20 26 3 0 22]83 dc[<3FFFFC381C0C 201C04401C0440380480380480380480380400700000700000700000700000E00000E00000E000 00E00001C00001C00001C00001C000038000038000038000038000078000FFF800>22 26 7 0 27]84 dc[<7FE0FF0E00380E00100E00101C00201C00201C00201C002038004038004038004038 0040700080700080700080700080E00100E00100E00100E00200E00200E0040060080060100038 60000F8000>24 26 8 0 29]85 dc[25 26 8 0 29]86 dc[34 26 8 0 38]87 dc[<01 FF07F8003C01C000380100003C0200001C0600001C0C00001E0800000E1000000E200000074000 000780000007800000038000000780000007C0000009C0000011C0000020E0000040E0000080E0 00018070000100700002007800040038001C007800FF01FF00>29 26 2 0 29]88 dc[<03CC0E 2E181C381C301C701CE038E038E038E038C072C072C07260F261341E18>15 16 4 0 20]97 dc[ <7E000E000E000E001C001C001C001C00380038003BC03C307830701870187018E038E038E038 E038C070C060C0E060C063801E00>13 26 4 0 18]98 dc[<01F006080C181838301070006000 E000E000E000E000E008E010602030C01F00>13 16 4 0 18]99 dc[<001F8000038000038000 0380000700000700000700000700000E00000E0003CE000E2E00181C00381C00301C00701C00E0 3800E03800E03800E03800C07200C07200C0720060F2006134001E1800>17 26 4 0 20]100 dc [<01E006181C08380870087010FFE0E000E000E000E000E0086010602030C01F00>13 16 4 0 18]101 dc[<000700001980001B80003B0000300000300000700000700000700000700007FF00 00E00000E00000E00000E00000E00001C00001C00001C00001C00001C000038000038000038000 038000038000070000070000070000660000E40000CC0000700000>17 33 -1 7 12]102 dc[< 00F300038B800607000E07000C07001C0700380E00380E00380E00380E00301C00301C00301C00 183C0018780007B800003800003800007000607000E0E000C1C0007F0000>17 23 2 7 18]103 dc[<1F80000380000380000380000700000700000700000700000E00000E00000E7C000F86001E 07001E07001C07001C0700380E00380E00380E00381C00701C80701C80703880703900E0190060 0E00>17 26 2 0 20]104 dc[<030706000000000000384C4E8E9C9C1C3838707272E2E46438> 8 25 4 0 12]105 dc[<000C000E000C00000000000000000000000000E0013002380438043804 38007000700070007000E000E000E000E001C001C001C001C003806380E700CE007800>15 32 -1 7 12]106 dc[<1F8003800380038007000700070007000E000E000E0E0E131C271C431C801F 003C003F8039C038E070E270E270E270E4E0646038>16 26 2 0 18]107 dc[<3F0707070E0E0E 0E1C1C1C1C3838383870707070E4E4E4E46830>8 26 3 0 10]108 dc[<307C1E00598663009E 0783809E0703809C0703809C070380380E0700380E0700380E0700380E0E00701C0E40701C0E40 701C1C40701C1C80E0380C8060180700>26 16 4 0 31]109 dc[<307C005986009E07009E0700 9C07009C0700380E00380E00380E00381C00701C80701C80703880703900E01900600E00>17 16 4 0 22]110 dc[<01F006180C0C180E300E700E600EE00EE00EE00CE01CE018E030606030C01F 00>15 16 4 0 20]111 dc[<030F000590C009E0C009C06009C06009C0600380E00380E00380E0 0380E00701C00701800703800703000E8E000E78000E00000E00001C00001C00001C00001C0000 FF0000>19 23 0 7 20]112 dc[<03C20E2E181C381C301C701CE038E038E038E038C070C070C0 7060F061E01EE000E000E001C001C001C001C01FF0>15 23 4 7 18]113 dc[<30F059189E389C 189C009C0038003800380038007000700070007000E0006000>13 16 4 0 16]114 dc[<03E004 300830187018601C001F801FC00FE000E00060E060E06080C041803E00>12 16 3 0 16]115 dc [<06000E000E000E000E001C001C00FFC01C0038003800380038007000700070007000E100E100 E100E20064003800>10 23 4 0 13]116 dc[<38064C074E0E8E0E9C0E9C0E1C1C381C381C381C 7039703970393079389A0F0C>16 16 4 0 21]117 dc[<380C304C0E384E1C388E1C189C1C189C 1C181C381038381038381038381070702070702070704030704018B8800F0F00>21 16 4 0 25] 119 dc[<078F0008D18010F38020E18020E00020E00001C00001C00001C00001C0000382000382 00C38200E78400C5880078F000>17 16 2 0 18]120 dc[<38064C074E0E8E0E9C0E9C0E1C1C38 1C381C381C703870387038307838F00F700070006060E0E1C0C18047003C00>16 23 4 7 19] 121 dc[<038207C40FFC10081010002000400180030004000808100820187FF043E081C0>15 16 2 0 16]122 dc dfe /fb df[<00FC7C0183C607078E0607040E07000E07000E07000E07000E07 000E0700FFFFF00E07000E07000E07000E07000E07000E07000E07000E07000E07000E07000E07 000E07000E07000E07007F0FF0>23 26 0 0 22]11 dc[<00FF000387000707000607000E0700 0E07000E07000E07000E07000E0700FFFF000E07000E07000E07000E07000E07000E07000E0700 0E07000E07000E07000E07000E07000E07000E07007F9FE0>19 26 0 0 21]13 dc[<60C0F1E0 F9F068D0081008100810102010202040C180>12 11 1 -15 19]34 dc[<000C0600000C060000 0C060000180C0000180C0000180C0000180C000030180000301800003018000030180000603000 FFFFFFE0FFFFFFE000C0600000C0600000C060000180C0000180C0000180C000FFFFFFE0FFFFFF E0030180000301800006030000060300000603000006030000060300000C0600000C0600000C06 00000C060000>27 33 2 7 32]35 dc[<01C0000003200000061000000E1000000E1000000E10 00000E1000000E2000000E4000000E40000007807F8007001E0007000800078010000B80100013 C0200031C0200060E04000E0F08000E0788000E0390000E01E0080E00E0080700F01003873C300 0F807C00>25 26 2 0 30]38 dc[<60F0F868080808101020C0>5 11 3 -15 11]39 dc[<0080 0100020004000C00080018003000300030006000600060006000E000E000E000E000E000E000E0 00E000E000E0006000600060006000300030003000180008000C000400020001000080>9 38 3 10 15]40 dc[<8000400020001000180008000C00060006000600030003000300030003800380 0380038003800380038003800380038003000300030003000600060006000C0008001800100020 0040008000>9 38 2 10 15]41 dc[<60F0F07010101020204080>4 11 3 7 11]44 dc[10 2 0 -7 13]45 dc[<60F0F060>4 4 3 0 11]46 dc[<0004000C001800180018003000 30003000600060006000C000C000C00180018001800300030003000600060006000C000C000C00 180018001800300030003000600060006000C000C000>14 37 2 9 19]47 dc[<078018603030 303060186018E01CE01CE01CE01CE01CE01CE01CE01CE01CE01CE01CE01C601860187038303018 600780>14 24 2 0 19]48 dc[<03000700FF0007000700070007000700070007000700070007 000700070007000700070007000700070007000700FFF0>12 24 3 0 19]49 dc[<0F80106020 304038803CC01CE01C401C003C003800380070006000C001800100020004040804100430083FF8 7FF8FFF8>14 24 2 0 19]50 dc[<0F8010E02070607870382038007800700070006000C00F80 00E000700038003C003CE03CE03CC03C4038407030E00F80>14 24 2 0 19]51 dc[<00300030 007000F000F001700370027004700C7008701070307020704070C070FFFF007000700070007000 70007007FF>16 24 1 0 19]52 dc[<30183FF03FE03FC02000200020002000200027C0386020 3000380018001C001C401CE01CE01C80184038403030E00F80>14 24 2 0 19]53 dc[<01E006 100C1818383038300070006000E000E7C0E860F030F018E018E01CE01CE01C601C601C70183018 3030186007C0>14 24 2 0 19]54 dc[<40007FFE7FFC7FFC4008801080108020004000400080 01800180010003000300030003000700070007000700070007000200>15 25 2 0 19]55 dc[< 078018603030201860186018601870103C303E600F8007C019F030F86038401CC00CC00CC00CC0 0C6008201018600FC0>14 24 2 0 19]56 dc[<07801860303070306018E018E018E01CE01CE0 1C601C603C303C185C0F9C001C00180018003870307060604021801F00>14 24 2 0 19]57 dc[ <60F0F060000000000000000060F0F060>4 16 3 0 11]58 dc[<000C0000000C0000000C0000 001E0000001E0000003F000000270000002700000043800000438000004380000081C0000081C0 000081C0000100E0000100E00001FFE00002007000020070000600780004003800040038000800 1C0008001C001C001E00FF00FFC0>26 26 1 0 29]65 dc[22 26 2 0 27]66 dc[<003F02 01C0C603002E0E001E1C000E1C0006380006780002700002700002F00000F00000F00000F00000 F00000F000007000027000027800023800041C00041C00080E000803003001C0C0003F00>23 26 2 0 28]67 dc[24 26 2 0 29]68 dc[22 26 2 0 26]69 dc[20 26 2 0 25]70 dc[ <003F020001C0C60003002E000E001E001C000E001C0006003800060078000200700002007000 0200F0000000F0000000F0000000F0000000F0000000F001FFC070000E0070000E0078000E0038 000E001C000E001C000E000E000E000300160001C06600003F8200>26 26 2 0 30]71 dc[ 24 26 2 0 29]72 dc[11 26 1 0 14]73 dc[<1FFC00E000 E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E040E0E0E0 E0E041C061801E00>14 26 3 0 20]74 dc[25 26 2 0 30]75 dc[19 26 2 0 24]76 dc[30 26 2 0 35]77 dc[24 26 2 0 29]78 dc[<007F 000001C1C000070070000E0038001C001C003C001E0038000E0078000F0070000700F0000780F0 000780F0000780F0000780F0000780F0000780F0000780F000078078000F0078000F0038000E00 3C001E001C001C000E0038000700700001C1C000007F0000>25 26 2 0 30]79 dc[21 26 2 0 26]80 dc[25 26 2 0 28] 82 dc[<0FC21836200E6006C006C002C002C002E00070007E003FE01FF807FC003E000E000700 03800380038003C002C006E004D81887E0>16 26 2 0 21]83 dc[<7FFFFF00701C0700401C01 00401C0100C01C0180801C0080801C0080801C0080001C0000001C0000001C0000001C0000001C 0000001C0000001C0000001C0000001C0000001C0000001C0000001C0000001C0000001C000000 1C0000001C0000001C000003FFE000>25 26 1 0 28]84 dc[24 26 2 0 29]85 dc[26 26 1 0 29]86 dc[36 26 1 0 39]87 dc[<7FC0FF000F003C000700300007802000038060 0001C0400001E0800000E1800000710000007A0000003C0000001C0000001E0000001E00000017 000000278000004380000041C0000081E0000100E0000100700002007800040038000C001C001E 003E00FF80FFC0>26 26 1 0 29]88 dc[27 26 1 0 29]89 dc[<7FFFC0780380700380600700400700400E00401C00401C 0000380000380000700000E00000E00001C00001C0000380000700400700400E00400E00401C00 C0380080380180700380700780FFFF80>18 26 2 0 23]90 dc[7 37 3 9 11]91 dc[<18302040 40804080810081008100B160F9F078F03060>12 11 5 -15 19]92 dc[7 37 0 9 11]93 dc[<3F 8070C070E020700070007007F01C7030707070E070E071E071E0F171FB1E3C>16 16 2 0 19] 97 dc[18 26 1 0 21]98 dc[<07F80C1C381C30087000E000E000E000E000E000E0007000 300438080C1807E0>14 16 1 0 17]99 dc[<007E00000E00000E00000E00000E00000E00000E 00000E00000E00000E0003CE000C3E00380E00300E00700E00E00E00E00E00E00E00E00E00E00E 00E00E00600E00700E00381E001C2E0007CFC0>18 26 1 0 21]100 dc[<07C01C303018701860 0CE00CFFFCE000E000E000E0006000300438080C1807E0>14 16 1 0 17]101 dc[<01F0031807 380E100E000E000E000E000E000E00FFC00E000E000E000E000E000E000E000E000E000E000E00 0E000E000E007FE0>13 26 0 0 12]102 dc[<0FCE187330307038703870387038303018602FC0 2000600070003FF03FFC1FFE600FC003C003C003C0036006381C07E0>16 24 1 8 19]103 dc[< FC00001C00001C00001C00001C00001C00001C00001C00001C00001C00001CF8001D0C001E0E00 1E0E001C0E001C0E001C0E001C0E001C0E001C0E001C0E001C0E001C0E001C0E001C0E00FF9FC0 >18 26 1 0 21]104 dc[<18003C003C001800000000000000000000000000FC001C001C001C00 1C001C001C001C001C001C001C001C001C001C001C00FF80>9 26 0 0 10]105 dc[<018003C0 03C001800000000000000000000000000FC001C001C001C001C001C001C001C001C001C001C001 C001C001C001C001C001C001C001C041C0E180E3007E00>10 33 -2 7 12]106 dc[18 26 1 0 20]107 dc[9 26 0 0 10]108 dc[29 16 1 0 32]109 dc[18 16 1 0 21]110 dc[<07E01C38300C700E6006E007E007E007E007E007E0076006700E381C1C38 07E0>16 16 1 0 19]111 dc[18 23 1 7 21]112 dc[<03C2000C2600381E00300E00700E00E00E00E00E00E00E00 E00E00E00E00E00E00700E00700E00381E001C2E0007CE00000E00000E00000E00000E00000E00 000E00007FC0>18 23 1 7 20]113 dc[12 16 1 0 15]114 dc[<1F2060E04020C020C020F0007F003FC01FE0 00F080708030C030C020F0408F80>12 16 1 0 15]115 dc[<0400040004000C000C001C003C00 FFC01C001C001C001C001C001C001C001C001C201C201C201C201C200E400380>11 23 1 0 15] 116 dc[18 16 1 0 21]117 dc[17 16 1 0 20]118 dc[25 16 1 0 28] 119 dc[18 16 1 0 20]120 dc[17 23 1 7 20]121 dc[<7FF86070407040E041C041C003 80070007000E081C081C08381070107030FFF0>13 16 1 0 17]122 dc[18 1 0 -9 19]123 dc dfe /fc df[<00200000700000700000700000B80000B80000B800011C00011C0001 1C00020E00020E0004070004070007FF000803800803800803801801C03803C0FE0FF8>21 21 1 0 25]97 dc dfe /fd df[<0C003C00CC000C000C000C000C000C000C000C000C000C000C000C 000C00FF80>9 16 2 0 15]49 dc dfe /fe df[<0C001C00EC000C000C000C000C000C000C00 0C000C000C000C000C000C000C000C000C00FFC0>10 19 3 0 17]49 dc dfe /ff df[<001FE0 2000FFF8E003F80FE007C003E00F8001E01F0000E03E0000E03E0000607E0000607C000060FC00 0000FC000000FC000000FC000000FC000000FC000000FC000000FC0000007C0000607E0000603E 0000603E0000C01F0000C00F80018007C0030003F80E0000FFFC00001FE000>27 28 3 0 34] 67 dc[ 31 28 2 0 37]68 dc[<0FF8001C1E003E0F803E07803E07C01C07C00007C0007FC007E7C01F07 C03C07C07C07C0F807C0F807C0F807C0780BC03E13F80FE1F8>21 18 1 0 23]97 dc[<03FC00 0E0E001C1F003C1F00781F00780E00F80000F80000F80000F80000F80000F80000780000780180 3C01801C03000E0E0003F800>17 18 2 0 21]99 dc[<000FF0000FF00001F00001F00001F000 01F00001F00001F00001F00001F00001F001F9F00F07F01C03F03C01F07801F07801F0F801F0F8 01F0F801F0F801F0F801F0F801F07801F07801F03C01F01C03F00F0FFE03F9FE>23 29 2 0 27] 100 dc[<01FC000F07001C03803C01C07801C07801E0F801E0F801E0FFFFE0F80000F80000F800 007800007C00603C00601E00C00F038001FC00>19 18 1 0 22]101 dc[<007F0001E38003C7C0 0787C00F87C00F83800F80000F80000F80000F80000F8000FFF800FFF8000F80000F80000F8000 0F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80007FF8007FF800 >18 29 0 0 15]102 dc[<03F8F00E0F381E0F381C07303C07803C07803C07803C07801C07001E 0F000E0E001BF8001000001800001800001FFF001FFFC00FFFE01FFFF07801F8F00078F00078F0 00787000707800F01E03C007FF00>21 27 1 9 24]103 dc[<1E003F003F003F003F001E000000 00000000000000000000FF00FF001F001F001F001F001F001F001F001F001F001F001F001F001F 001F00FFE0FFE0>11 30 1 0 14]105 dc[11 29 1 0 14]108 dc[24 18 1 0 27]110 dc[<01FC000F 07801C01C03C01E07800F07800F0F800F8F800F8F800F8F800F8F800F8F800F87800F07800F03C 01E01E03C00F078001FC00>21 18 1 0 24]111 dc[23 26 1 8 27]112 dc[<03F0600F0CE0 1E07E03C03E07C03E07803E0F803E0F803E0F803E0F803E0F803E0F803E07803E07C03E03C03E0 1C07E00E0FE003F3E00003E00003E00003E00003E00003E00003E0001FFC001FFC>22 26 2 8 25]113 dc[17 18 1 0 20]114 dc[<1FD830786018E0 18E018F000FF807FE07FF01FF807FC007CC01CC01CE01CE018F830CFC0>14 18 2 0 19]115 dc [<0300030003000300070007000F000F003FFCFFFC1F001F001F001F001F001F001F001F001F00 1F0C1F0C1F0C1F0C0F08079803F0>14 26 1 0 19]116 dc[24 18 1 0 27]117 dc[22 18 1 0 25]118 dc[22 18 1 0 25]120 dc dfe /fg df[<071C00071C00071C 00071C00071C007FFF00FFFF80FFFF800E38000E38000E38000E38000E38000E38000E3800FFFF 80FFFF807FFF001C70001C70001C70001C70001C7000>17 23 1 0 20]35 dc[<60F0F8781818 18303060C080>5 12 8 -11 20]39 dc[<00C001C0030006000C001C0038003000700070006000 E000E000E000E000E000E000E000600070007000300038001C000C000600030001C000C0>10 29 6 3 20]40 dc[<8000C0006000300018001C000E00060007000700030003800380038003800380 0380038003000700070006000E001C00180030006000C0008000>9 29 4 3 20]41 dc[<70F8FC FC7C0C1830E0C0>6 10 7 5 20]44 dc[15 3 2 -10 20]45 dc[<70F8F8F870 >5 5 7 0 20]46 dc[<07C00FE01C7038383018701C701CE00EE00EE00EE00EE00EE00EE00EE0 0EE00E701C701C383838381C700FE007C0>15 23 2 0 20]48 dc[<0300030007000F003F00F7 004700070007000700070007000700070007000700070007000700070007007FF07FF0>12 23 4 0 20]49 dc[<0FC01FF03838701CE00EE00EE00E400E000E001C001C00380030007000E001C003 0006000C00180E300E7FFE7FFE>15 23 2 0 20]50 dc[<0FC01FF03838701C701C201C001C00 1C0038007007E007F00038001C000E000E400EE00EE00E701C78383FF00FC0>15 23 2 0 20] 51 dc[<00780000F80001B80001B8000338000338000638000E38000C38001C38003838003038 00703800E03800FFFF80FFFF8000380000380000380000380000380001FF0001FF00>17 23 1 0 20]52 dc[<3FFC7FFC700070007000700070007000700077C07FF07838201C000C000E000E400E E00EE01C601C78783FF00FC0>15 23 2 0 20]53 dc[<01F007F80E1C1C1C381C300070007000 E000E7C0EFF0F838F01CF00CE00EE00E600E700E700C381C1C380FF007C0>15 23 2 0 20]54 dc[15 24 2 0 20]55 dc[<0FE03FF8783C701CE00EE00EE00EE00E70 1C1EF003801FF03838701CE00EE00EE00EE00EF01E701C38381FF007C0>15 23 2 0 20]56 dc[ <07C01FE038307038601CE01CE00CE00EE00E601E701E383E1FEE07CE000E001C001C001C7038 707070E03FC01F00>15 23 2 0 20]57 dc[<70F8F8F87000000000000070F8F8F870>5 16 7 0 20]58 dc[<70F8F8F87000000000000060F0F8F878183070E080>5 21 7 5 20]59 dc[<000E00 3E007C00F003E007C01F003E00F800F000F8003E001F0007C003E000F0007C003E000E>15 19 2 -2 20]60 dc[17 9 1 -7 20]61 dc[<4000E000F8007C001E000F8007C001F000F8003E001E003E00F801F007C00F801E00 7C00F800E0004000>15 21 2 -1 20]62 dc[<01C00003E00003E0000360000360000770000770 000770000770000630000E38000E38000E38000E38000E38001FFC001FFC001C1C001C1C003C1E 00380E00FE3F80FE3F80>17 23 1 0 20]65 dc[16 23 1 0 20]66 dc[< 03C60FFE1C3E181E381E700E700E600EE000E000E000E000E000E000E000600E700E700E380C18 1C1C380FF003C0>15 23 2 0 20]67 dc[17 23 1 0 20]68 dc[17 23 1 0 20]69 dc[<03C60FFE1C3E181E381E700E700E600EE0 00E000E000E000E07FE07FE00E600E700E700E381E181E1C3E0FFE03CE>16 23 1 0 20]71 dc[ 17 23 1 0 20] 72 dc[13 23 3 0 20]73 dc[16 23 2 0 20]76 dc[ 19 23 0 0 20] 77 dc[17 23 1 0 20]78 dc[<1FF07FFC783C701CE00EE00EE00EE00EE00EE00EE00EE00EE00EE00EE00EE00EE00E E00EE00E701C783C7FFC1FF0>15 23 2 0 20]79 dc[<1FF07FFC783C701CE00EE00EE00EE00E E00EE00EE00EE00EE00EE00EE00EE00EE00EE38EE1CE71DC78FC7FFC1FF000780038003C001C00 1E>15 28 2 5 20]81 dc[18 23 1 0 20]82 dc[<0FCC1FFC307C603CE01CE01CE01CE00070007E003FE00FF001 F8001C001E000E600EE00EE00EF01CF838FFF0C7E0>15 23 2 0 20]83 dc[<7FFF80FFFF80E1 C380E1C380E1C380E1C38001C00001C00001C00001C00001C00001C00001C00001C00001C00001 C00001C00001C00001C00001C00001C0000FF8000FF800>17 23 1 0 20]84 dc[19 23 0 0 20]85 dc[11 29 7 3 20]91 dc[11 29 1 3 20]93 dc[<1FC0007FF000707800201800001C00001C0007FC00 1FFC003C1C00701C00E01C00E01C00E01C00707C003FFF800F8F80>17 16 2 0 20]97 dc[18 23 0 0 20]98 dc[ <03F80FFC1C1C380870006000E000E000E000E00060007000380E1C1E0FFC03F0>15 16 2 0 20 ]99 dc[<007E00007E00000E00000E00000E00000E00000E0007CE000FFE001C3E00301E00700E 00E00E00E00E00E00E00E00E00E00E00E00E00700E00301E00383E001FEFC007CFC0>18 23 1 0 20]100 dc[<07E00FF01C38301C700CE00EE00EFFFEFFFEE00060007000380E1C1E0FFC03F0> 15 16 2 0 20]101 dc[<007C00FE01CE03840380038003807FFEFFFE03800380038003800380 03800380038003800380038003807FFC7FFC>15 23 1 0 20]102 dc[<07CF001FFF80383B8030 1800701C00701C00701C003018003838003FF00037C0007000007000003FF8001FFC003FFE0070 0F00E00380E00380E00380E003807007003C1E001FFC0007F000>17 25 1 9 20]103 dc[19 23 0 0 20]104 dc[< 030007800780030000000000000000007F807F8003800380038003800380038003800380038003 8003800380FFFCFFFC>14 24 3 0 20]105 dc[<006000F000F0006000000000000000001FF01F F000700070007000700070007000700070007000700070007000700070007000700070007040E0 E0C07F803F00>12 32 2 8 20]106 dc[17 23 1 0 20]107 dc[15 23 2 0 20]108 dc[19 16 0 0 20]109 dc[19 16 0 0 20]110 dc[<07 C01FF03C78701C701CE00EE00EE00EE00EE00EE00E701C783C3C781FF007C0>15 16 2 0 20] 111 dc[18 24 0 8 20]112 dc[<03CE000FFE001C3E00301E00700E00E00E00E00E00E00E00E00E00E00E00 E00E00700E00301E001C3E000FEE0007CE00000E00000E00000E00000E00000E00000E00007FC0 007FC0>18 24 1 8 20]113 dc[17 16 1 0 20]114 dc[<0FD83FF860 38C038C038F0007F803FF007F8001C6006E006F006F81CFFF8CFE0>15 16 2 0 20]115 dc[<03 0007000700070007007FFCFFFC07000700070007000700070007000700070E070E070E070C03FC 00F0>15 21 1 0 20]116 dc[19 16 0 0 20]117 dc[17 16 1 0 20]118 dc[17 16 1 0 20]119 dc[<7E3F007E3F 001E38000E780007700007E00003E00001C00003C00003E0000770000E78000E38001C1C00FE3F 80FE3F80>17 16 1 0 20]120 dc[17 24 1 8 20]121 dc[<003E00FE01E003800380038003800380038003 800380038003807F00FE007F00038003800380038003800380038003800380038001E000FE003E >15 29 2 3 20]123 dc[<7800FE000F00038003800380038003800380038003800380038001FC 00FE01FC03800380038003800380038003800380038003800F00FE007800>15 29 2 3 20]125 dc dfe /fh df[17 3 2 -11 22]45 dc[<03E0000FF8001FFC001E3C 00380E00780F00700700700700E00380E00380E00380E00380E00380E00380E00380E00380F007 80700700700700780F003C1E001E3C001FFC000FF80003E000>17 25 2 0 22]48 dc[<00E000 01F00001F00001B00001B00003B80003B80003B800031800071C00071C00071C00071C00071C00 0E0E000E0E000FFE000FFE001FFF001C07001C07001C07007F1FC0FF1FE07F1FC0>19 25 1 0 22]65 dc[19 25 1 0 22]77 dc[<07E3001FFF003FFF00781F00F00700E00700E00700E00000F000 007800003F80001FF00007FC0000FE00000F00000700000380000380600380E00380E00700F80F 00FFFE00FFFC00C7F000>17 25 2 0 22]83 dc[<7FFFE0FFFFE0FFFFE0E0E0E0E0E0E0E0E0E0 E0E0E000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E000 00E00000E00000E00007FC000FFE0007FC00>19 25 1 0 22]84 dc[<1FE0003FF0007FF80078 3C00300E00000E00000E0003FE001FFE003E0E00700E00E00E00E00E00E00E00783E007FFFE03F E7E00F83E0>19 18 2 0 22]97 dc[<03F80FFC1FFE3C1E780C7000E000E000E000E000E000F0 00700778073E0E1FFC0FF803F0>16 18 3 0 22]99 dc[<003F00007F00003F00000700000700 00070000070003C7000FF7001FFF003C1F00780F00700700E00700E00700E00700E00700E00700 E00700700F00700F003C1F001FFFE00FE7F007C7E0>20 25 1 0 22]100 dc[<03E00FF81FFC3C 1E780E7007E007FFFFFFFFFFFFE000E000700778073C0F1FFE0FFC03F0>16 18 3 0 22]101 dc [<018003C003C0018000000000000000007FC07FC07FC001C001C001C001C001C001C001C001C0 01C001C001C001C07FFFFFFF7FFF>16 26 3 0 22]105 dc[17 25 2 0 22]108 dc[21 18 0 0 22]109 dc[<7E3C00FEFE007FFF000F87800F03800E03800E 03800E03800E03800E03800E03800E03800E03800E03800E03807FC7F0FFE7F87FC7F0>21 18 0 0 22]110 dc[<03E0000FF8001FFC003C1E00780F00700700E00380E00380E00380E00380E003 80F00780700700780F003C1E001FFC000FF80003E000>17 18 2 0 22]111 dc[<07C7000FE700 1FF7003C1F00700F00700F00E00700E00700E00700E00700E00700E00700700F00700F003C3F00 3FF7001FE70007C700000700000700000700000700000700000700003FE0007FF0003FE0>20 27 2 9 22]113 dc[19 18 1 0 22]114 dc[<0FEC3FFC7F FCF03CE01CE01C70007F801FF007F8003C600EE00EF00EF81EFFFCFFF8C7E0>15 18 3 0 22] 115 dc[<0300000700000700000700000700007FFF00FFFF00FFFF000700000700000700000700 0007000007000007000007010007038007038007038007870003FE0001FC0000F800>17 23 1 0 22]116 dc[<7E1F80FE3F807E1F800E03800E03800E03800E03800E03800E03800E03800E0380 0E03800E03800E03800E0F800FFFF007FBF803E3F0>21 18 0 0 22]117 dc[<7F1FC0FF1FE07F 1FC01C07001E0F000E0E000E0E000E0E00071C00071C00071C00071C0003B80003B80003B80001 F00001F00000E000>19 18 1 0 22]118 dc[19 18 1 0 22]119 dc dfe /fi df[25 2 3 -9 32]0 dc[<400020C000606000C030 01801803000C0600060C0003180001B00000E00000E00001B000031800060C000C060018030030 01806000C0C00060400020>19 20 6 0 32]2 dc[<03C00FF01FF83FFC7FFE7FFEFFFFFFFFFFFF FFFF7FFE7FFE3FFC1FF80FF003C0>16 16 2 -2 21]15 dc dfe /fj df[<0180300380700380 700380700700E00700E00700E00700E00E01C00E01C00E01C00E01C01C03881C03881C03881E07 883E19903BE0E0380000380000700000700000700000700000E00000E00000C00000>21 27 1 9 25]22 dc[<60F0F060>4 4 4 0 12]58 dc[<0003F800000E0E000038038000E001C001C001C0 038000E0070000E00F0000F01E0000F01C0000F03C0000F03C0000F0780000F0780000F0780000 F0F00001E0F00001E0F00001E0F00003C0F00003C0F0000780F0000780F0000F0070000E007000 1C00380038003C0070001C01C0000707800001FC0000>28 30 2 1 32]79 dc[<3F0007000700 0E000E000E000E001C001C001C001C0039E03A303C1838187018701C701C701CE038E038E038E0 30E070E060E0C061C023001E00>14 29 2 0 18]98 dc[<01C003C003C0018000000000000000 00000000001C00270047004700870087000E000E001C001C001C00380038803880708071003200 1C00>10 28 2 0 14]105 dc[<1F800380038007000700070007000E000E000E000E001C001C00 1C001C0038003800380038007000700070007000E400E400E400E40064003800>9 29 2 0 12] 108 dc[<381F004E61804681C04701C08F01C08E01C00E01C00E01C01C03801C03801C03801C07 00380710380710380E10380E20700640300380>20 18 2 0 25]110 dc[<07078009C86008D030 08E03011C03011C03801C03801C0380380700380700380700380600700E00700C0070180078300 0E86000E78000E00000E00001C00001C00001C00001C00003C0000FF8000>21 26 -1 8 21] 112 dc[<07878008C84010F0C020F1E020E3C040E18000E00000E00001C00001C00001C00001C0 00638080F38080F38100E5810084C600787800>19 18 2 0 24]120 dc[<1C00C02701C04701C0 4701C08703808703800E03800E03801C07001C07001C07001C0700180E00180E00180E001C1E00 0C3C0007DC00001C00001800603800F03000F06000E0C0004180003E0000>18 26 2 8 20]121 dc dfe /fk df[14 4 1 -9 19]45 dc[<387CFEFEFE7C38>7 7 4 0 16] 46 dc[<00180000780001F800FFF800FFF80001F80001F80001F80001F80001F80001F80001F8 0001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F8 0001F80001F80001F80001F80001F8007FFFE07FFFE0>19 32 4 0 28]49 dc[<03FC000FFF00 3C1FC07007E07C07F0FE03F0FE03F8FE03F8FE01F87C01F83803F80003F80003F00003F00007E0 0007C0000F80001F00003E0000380000700000E01801C0180380180700180E00380FFFF01FFFF0 3FFFF07FFFF0FFFFF0FFFFF0>21 32 3 0 28]50 dc[<00FE0007FFC00F07E01E03F03F03F03F 81F83F81F83F81F81F03F81F03F00003F00003E00007C0001F8001FE0001FF000007C00001F000 01F80000FC0000FC3C00FE7E00FEFF00FEFF00FEFF00FEFF00FC7E01FC7801F81E07F00FFFC001 FE00>23 32 2 0 28]51 dc[<0000E00001E00003E00003E00007E0000FE0001FE0001FE00037 E00077E000E7E001C7E00187E00307E00707E00E07E00C07E01807E03807E07007E0E007E0FFFF FEFFFFFE0007E00007E00007E00007E00007E00007E00007E000FFFE00FFFE>23 32 2 0 28] 52 dc[<1000201E01E01FFFC01FFF801FFF001FFE001FF8001BC0001800001800001800001800 0019FC001FFF001E0FC01807E01803E00003F00003F00003F80003F83803F87C03F8FE03F8FE03 F8FC03F0FC03F07007E03007C01C1F800FFF0003F800>21 32 3 0 28]53 dc[<000070000000 007000000000F800000000F800000000F800000001FC00000001FC00000003FE00000003FE0000 0003FE00000006FF000000067F0000000E7F8000000C3F8000000C3F800000183FC00000181FC0 0000381FE00000300FE00000300FE00000600FF000006007F00000E007F80000FFFFF80000FFFF F800018001FC00018001FC00038001FE00030000FE00030000FE000600007F000600007F00FFE0 0FFFF8FFE00FFFF8>37 34 2 0 42]65 dc[<0003FE0080001FFF818000FF01E38001F8003F80 03E0001F8007C0000F800F800007801F800007803F000003803F000003807F000001807E000001 807E00000180FE00000000FE00000000FE00000000FE00000000FE00000000FE00000000FE0000 0000FE000000007E000000007E000001807F000001803F000001803F000003801F800003000F80 00030007C000060003F0000C0001F800380000FF00F000001FFFC0000003FE0000>33 34 3 0 40]67 dc[37 34 2 0 43]68 dc[32 34 2 0 37]69 dc[38 34 2 0 44]75 dc[48 34 2 0 53]77 dc[32 34 2 0 38]80 dc[39 34 2 0 42] 82 dc[<01FC0407FF8C1F03FC3C007C7C003C78001C78001CF8000CF8000CFC000CFC0000FF00 00FFE0007FFF007FFFC03FFFF01FFFF80FFFFC03FFFE003FFE0003FF00007F00003F00003FC000 1FC0001FC0001FE0001EE0001EF0003CFC003CFF00F8C7FFE080FF80>24 34 3 0 31]83 dc[< 7FFFFFFF807FFFFFFF807E03F80F807803F807807003F803806003F80180E003F801C0E003F801 C0C003F800C0C003F800C0C003F800C0C003F800C00003F800000003F800000003F800000003F8 00000003F800000003F800000003F800000003F800000003F800000003F800000003F800000003 F800000003F800000003F800000003F800000003F800000003F800000003F800000003F8000000 03F8000003FFFFF80003FFFFF800>34 34 2 0 39]84 dc[<07FC001FFF803F07C03F03E03F01 E03F01F01E01F00001F00001F0003FF003FDF01FC1F03F01F07E01F0FC01F0FC01F0FC01F0FC01 F07E02F07E0CF81FF87F07E03F>24 22 2 0 27]97 dc[26 35 2 0 31]98 dc[<00FF8007FFE00F83F01F03F03E03F07E03F07C01 E07C0000FC0000FC0000FC0000FC0000FC0000FC00007C00007E00007E00003E00301F00600FC0 E007FF8000FE00>20 22 2 0 25]99 dc[<0001FE000001FE0000003E0000003E0000003E0000 003E0000003E0000003E0000003E0000003E0000003E0000003E0000003E0001FC3E0007FFBE00 0F81FE001F007E003E003E007E003E007C003E00FC003E00FC003E00FC003E00FC003E00FC003E 00FC003E00FC003E00FC003E007C003E007C003E003E007E001E00FE000F83BE0007FF3FC001FC 3FC0>26 35 2 0 31]100 dc[<00FE0007FF800F87C01E01E03E01F07C00F07C00F8FC00F8FC00 F8FFFFF8FFFFF8FC0000FC0000FC00007C00007C00007E00003E00181F00300FC07003FFC000FF 00>21 22 2 0 26]101 dc[<003F8000FFC001E3E003C7E007C7E00F87E00F83C00F80000F8000 0F80000F80000F80000F8000FFFC00FFFC000F80000F80000F80000F80000F80000F80000F8000 0F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80007FF8007FF800 >19 35 1 0 17]102 dc[<03FC1E0FFF7F1F0F8F3E07CF3C03C07C03E07C03E07C03E07C03E07C 03E03C03C03E07C01F0F801FFF0013FC003000003000003800003FFF801FFFF00FFFF81FFFFC38 00FC70003EF0001EF0001EF0001EF0001E78003C7C007C3F01F80FFFE001FF00>24 33 2 11 28 ]103 dc[26 35 2 0 31]104 dc[< 1C003F007F007F007F003F001C000000000000000000000000000000FF00FF001F001F001F001F 001F001F001F001F001F001F001F001F001F001F001F001F001F001F00FFE0FFE0>11 36 2 0 16]105 dc[26 35 2 0 30]107 dc [11 35 2 0 16] 108 dc[43 22 2 0 48]109 dc[26 22 2 0 31]110 dc[<00FE0007FFC00F83E01E00F03E00F87C007C7C007C7C007CFC007E FC007EFC007EFC007EFC007EFC007EFC007E7C007C7C007C3E00F81F01F00F83E007FFC000FE00 >23 22 2 0 28]111 dc[26 32 2 10 31]112 dc[<00FE030007 FF87000FC1C7001F006F003F003F007E003F007E001F007C001F00FC001F00FC001F00FC001F00 FC001F00FC001F00FC001F00FC001F007E001F007E001F003E003F001F007F000FC1DF0007FF9F 0001FC1F0000001F0000001F0000001F0000001F0000001F0000001F0000001F0000001F000000 FFE00000FFE0>27 32 2 10 30]113 dc[19 22 2 0 23]114 dc[<0FF3003FFF00781F00600700E00300E00300F00300FC 00007FE0007FF8003FFE000FFF0001FF00000F80C00780C00380E00380E00380F00700FC0E00EF FC00C7F000>17 22 2 0 22]115 dc[<0180000180000180000180000380000380000780000780 000F80003F8000FFFF00FFFF000F80000F80000F80000F80000F80000F80000F80000F80000F80 000F80000F80000F81800F81800F81800F81800F81800F830007C30003FE0000F800>17 32 1 0 22]116 dc[26 22 2 0 31]117 dc[27 22 1 0 30]118 dc[37 22 1 0 40]119 dc[27 22 1 0 30]120 dc[27 32 1 10 30]121 dc dfe /fl df[<00FC7E000703C1000E0783801C070380 1C0701001C0700001C0700001C0700001C070000FFFFFF801C0703801C0703801C0703801C0703 801C0703801C0703801C0703801C0703801C0703801C0703801C0703801C070380FF1FCFF0>28 23 0 0 29]14 dc[<60C0F1E0F1E070E0102010202040204040804080>11 10 1 -13 18]34 dc [<0102040C1818303070606060E0E0E0E0E0E0E0E0E0E060606070303018180C040201>8 34 3 9 14]40 dc[<8040203018180C0C0E060606070707070707070707070606060E0C0C1818302040 80>8 34 2 9 14]41 dc[<60F0F070101020204040>4 10 3 6 10]44 dc[9 2 0 -6 12]45 dc[<60F0F060>4 4 3 0 10]46 dc[<0008001800300030003000600060006000C000 C000C0018001800180030003000600060006000C000C000C001800180018003000300030006000 60006000C000C000>13 33 2 8 18]47 dc[<07C018303018701C600C600CE00EE00EE00EE00E E00EE00EE00EE00EE00E600C600C701C30181C7007C0>15 21 1 0 18]48 dc[<0F8030E04070 8030C038E0384038003800700070006000C00180030006000C08080810183FF07FF0FFF0>13 21 2 0 18]50 dc[<0FE030306018701C701C001C00180038006007E000300018000C000E000EE00E E00EC00C401830300FE0>15 21 1 0 18]51 dc[<20303FE03FC0240020002000200020002F80 30E020700030003800384038E038E0388030406020C01F00>13 21 2 0 18]53 dc[<40007FFE 7FFC7FF8C008801080200040008000800100010003000200060006000E000E000E000E000E0004 00>15 22 2 0 18]55 dc[<07C0183030186018E00CE00CE00EE00EE00E601E301E186E0F8E00 0E000C001C70187018603020C01F80>15 21 1 0 18]57 dc[<00100000380000380000380000 5C00005C00005C00008E00008E00008E0001070001070003078002038002038007FFC00401C004 01C00800E00800E01800E03800F0FE03FE>23 23 1 0 26]65 dc[21 23 1 0 25]66 dc[<00FC100383300E00B0 1C0070380030300030700010600010E00010E00000E00000E00000E00000E00000E00010600010 7000103000203800201C00400E008003830000FC00>20 23 2 0 25]67 dc[23 23 1 0 27]68 dc[21 23 1 0 24]69 dc[20 23 1 0 23]70 dc[11 23 1 0 13]73 dc[29 23 1 0 32] 77 dc[23 23 1 0 26]78 dc[<00FC000303000E01C01C00E0380070300030700038600018E0001CE0001CE0001CE0 001CE0001CE0001CE0001C7000387000383000303800701C00E00E01C003030000FC00>22 23 2 0 27]79 dc[20 23 1 0 24]80 dc[24 23 1 0 26]82 dc[<0FC4302C601C400CC004C004C004E00070007F003FE00FF801FC001C000E 0006800680068006C004E008D81087E0>15 23 2 0 20]83 dc[<7FFFF8603818403808403808 803804803804803804003800003800003800003800003800003800003800003800003800003800 00380000380000380000380000380007FFC0>22 23 1 0 25]84 dc[23 23 1 0 26]85 dc[33 23 1 0 36]87 dc[ 25 23 0 0 26]89 dc[<204020404080408081008100E1 C0F1E0F1E060C0>11 10 5 -13 18]92 dc[<1FC0386038301038003803F81E3830387038E039 E039E07970FF1F1E>16 14 1 0 18]97 dc[18 23 0 0 20]98 dc[<07F01838303870106000E000E000E000E000 600070083008183007C0>13 14 1 0 16]99 dc[<007E00000E00000E00000E00000E00000E00 000E00000E00000E0007CE001C3E00300E00700E00600E00E00E00E00E00E00E00E00E00600E00 700E00301E00182E0007CFC0>18 23 1 0 20]100 dc[<0FC0186030307038E018FFF8E000E000 E000600070083010183007C0>13 14 1 0 16]101 dc[<03E006700E701C201C001C001C001C00 1C00FF801C001C001C001C001C001C001C001C001C001C001C001C00FF80>12 23 0 0 11]102 dc[<0F9E18E33060707070707070306018C02F80200060003FE03FF83FFC600EC006C006C00660 0C38380FE0>16 21 1 7 18]103 dc[19 23 0 0 20]104 dc[<183C3C1800000000007C1C1C1C1C1C1C1C1C1C1C1C 1CFF>8 23 0 0 10]105 dc[<0300078007800300000000000000000000001F80038003800380 0380038003800380038003800380038003800380038003804380E300E7007C00>9 29 -2 6 11] 106 dc[18 23 0 0 19]107 dc[9 23 0 0 10]108 dc[29 14 0 0 30]109 dc[19 14 0 0 20]110 dc[<07C018303018600C600CE00E E00EE00EE00EE00E701C3018183007C0>15 14 1 0 18]111 dc[18 20 0 6 20]112 dc[<07C2001C2600381E00700E00600E00E00E00E0 0E00E00E00E00E00600E00700E00301E001C2E0007CE00000E00000E00000E00000E00000E0000 7FC0>18 20 1 6 19]113 dc[13 14 0 0 14]114 dc[<1F4060C0C040C040E000FF007F801FC001E080608060C060E0C0 9F00>11 14 1 0 14]115 dc[<080008000800180018003800FF80380038003800380038003800 380038403840384038401C800F00>10 20 1 0 14]116 dc[19 14 0 0 20]117 dc[< FE1F3C0E3C0C1C081C080E100E100720072003C003C003C001800180>16 14 1 0 19]118 dc[< FCFE7C3838383838101C3C201C3C201C4C200E4E400E4E400E8640078780078780070380030300 030300>22 14 1 0 25]119 dc[16 14 1 0 19]120 dc[16 20 1 6 19]121 dc[13 14 1 0 16]122 dc dfe /fm df[<0001FC00070300 0C03001C07001C0300180000380000380000380000380000700007FFFC00701C00701C00701C00 E03800E03800E03800E03800E07001C07001C07001C07001C0E201C0E201C0E20380E403806403 8038038000030000070000060000C60000E40000CC0000700000>24 37 -1 8 23]12 dc[<1838 78380808101020404080>5 12 3 8 13]44 dc[10 3 3 -7 15]45 dc[<3078 F060>5 4 4 0 13]46 dc[<00000200000600000600000C00000C000018000030000030000060 0000600000C00000C0000180000180000300000600000600000C00000C00001800001800003000 00300000600000C00000C0000180000180000300000300000600000C00000C0000180000180000 300000300000600000600000C00000800000>23 41 1 10 21]47 dc[<003C0000C60001830003 03000603000603800E03800C03801C03801C0300380700380700380700380700700E00700E0070 0E00700E00E01C00E01C00E01C00E03800E03800E03000C06000E0600060C0007180001E0000> 17 29 5 1 21]48 dc[<00020006000C001C007C039C0038003800380038007000700070007000 E000E000E000E001C001C001C001C003800380038003800780FFF0>15 28 4 0 21]49 dc[<00 01800001C0000380000380000380000300000700000700000600000E00000C00001C0000180000 180000300000300000600000400000C600018E00010E00020E00061C000C1C00181C003F1C0040 F800803F0000380000380000700000700000700000700000E000006000>18 36 2 8 21]52 dc[ <000F0000308000C0800183800383800300000600000E00000C00001C00001CF0003B18003C0C 00380C00780C00700E00700E00700E00601C00E01C00E01C00E01C00E03800E03800E070006060 0060C0002180001E0000>17 29 5 1 21]54 dc[<000018000000180000003800000038000000 7800000078000000B8000001B800000138000002380000023C0000041C0000041C0000081C0000 181C0000101C0000201C0000201C00007FFC0000401C0000801C0001801C0001001C0002001C00 02001C0004000E000C000E001C001E00FF00FFC0>26 29 2 0 31]65 dc[<0003F020001E0C60 003002E000E003C001C001C0038001C0070000C00E0000801E0000801C0000803C0000803C0000 00780000007800000078000000F0000000F0000000F0000000F0000000F0000400F0000400F000 0400F0000800700008007000100038002000180040000C0180000706000001F80000>27 30 6 1 30]67 dc[<01FFFFE0003C00E00038006000380040003800400038004000700040007000400070 20400070200000E0400000E0400000E0C00000FFC00001C0800001C0800001C0800001C0800003 810100038001000380020003800200070004000700040007000C00070018000E007800FFFFF000 >27 28 3 0 28]69 dc[<01FFFFC0003C01C0003800C000380080003800800038008000700080 00700080007020800070200000E0400000E0400000E0C00000FFC00001C0800001C0800001C080 0001C0800003810000038000000380000003800000070000000700000007000000070000000F00 0000FFF00000>26 28 3 0 27]70 dc[<01FFE0003C0000380000380000380000380000700000 700000700000700000E00000E00000E00000E00001C00001C00001C00001C00003800803800803 80080380100700100700300700600700E00E03C0FFFFC0>21 28 3 0 26]76 dc[<01FE0007F8 003E000780002E000F00002E001700002E001700002E002700004E002E00004E004E00004E004E 00004E008E00008E011C00008E011C00008E021C00008E021C0001070438000107043800010708 380001071038000207107000020720700002072070000207407000040740E000040780E0000407 00E0000C0700E0001C0601E000FF861FFC00>37 28 3 0 37]77 dc[<01FFFC00003C07000038 0380003801C0003801C0003801C0007003C0007003C0007003C00070038000E0078000E0070000 E00E0000E0380001FFE00001C0000001C0000001C0000003800000038000000380000003800000 070000000700000007000000070000000F000000FFE00000>26 28 3 0 28]80 dc[<01FFF800 003C0E000038070000380380003803800038038000700780007007800070078000700F0000E00E 0000E01C0000E0700000FFC00001C0C00001C0600001C0700001C0700003807000038070000380 7000038070000700F0000700F0400700F0400700F0800F007880FFE0790000001E00>26 29 3 1 30]82 dc[<000F8400304C00403C00801801001803001803001806001006001006000007000007 000003E00003FC0001FF00007F800007C00001C00001C00000C00000C02000C02000C060018060 0180600300600200F00400CC180083E000>22 30 3 1 23]83 dc[<1FFFFFC01C0701C0300E00 C0200E0080600E0080400E0080401C0080801C0080801C0080001C000000380000003800000038 0000003800000070000000700000007000000070000000E0000000E0000000E0000000E0000001 C0000001C0000001C0000001C0000003C000007FFE0000>26 28 7 0 30]84 dc[26 29 9 1 31]86 dc[<03CC063C0C3C181C3838303870387038E070E070E070E070E0E2C0E2C0E261E46264 3C38>15 18 5 0 21]97 dc[<3F00070007000E000E000E000E001C001C001C001C0039C03E60 383038307038703870387038E070E070E070E060E0E0C0C0C1C0618063003C00>13 29 5 0 19] 98 dc[<01F007080C08181C3838300070007000E000E000E000E000E000E008E010602030C01F 00>14 18 5 0 19]99 dc[<001F80000380000380000700000700000700000700000E00000E00 000E00000E0003DC00063C000C3C00181C00383800303800703800703800E07000E07000E07000 E07000E0E200C0E200C0E20061E4006264003C3800>17 29 5 0 21]100 dc[<01E007100C1018 083810701070607F80E000E000E000E000E000E0086010602030C01F00>13 18 5 0 19]101 dc [<0003C0000670000C70001C60001C00001C0000380000380000380000380000380003FF800070 0000700000700000700000700000E00000E00000E00000E00000E00001C00001C00001C00001C0 0001C000038000038000038000030000030000070000C60000E60000CC0000780000>20 37 -1 8 13]102 dc[<00F3018F030F06070E0E0C0E1C0E1C0E381C381C381C381C3838303830381878 18F00F700070007000E000E0C0C0E1C0C3007E00>16 26 3 8 19]103 dc[<0FC00001C00001C0 000380000380000380000380000700000700000700000700000E78000E8C000F0E000E0E001C0E 001C0E001C0E001C0E00381C00381C00381C00383800703880703880707080707100E03200601C 00>17 29 3 0 21]104 dc[<01800380010000000000000000000000000000001C002600470047 008E008E000E001C001C001C0038003800710071007100720072003C00>9 28 4 0 13]105 dc[ <0FC00001C00001C0000380000380000380000380000700000700000700000700000E0F000E11 000E23800E43801C83001C80001D00001E00003F800039C00038E00038E00070E20070E20070E2 0070E400E06400603800>17 29 3 0 19]107 dc[<1F800380038007000700070007000E000E00 0E000E001C001C001C001C0038003800380038007000700070007000E400E400E400E400680038 00>9 29 4 0 11]108 dc[<3C1E0780266318C04683A0E04703C0E08E0380E08E0380E00E0380 E00E0380E01C0701C01C0701C01C0701C01C070380380E0388380E0388380E0708380E0710701C 0320300C01C0>29 18 4 0 34]109 dc[<3C3C002646004687004707008E07008E07000E07000E 07001C0E001C0E001C0E001C1C00381C40381C40383840383880701900300E00>18 18 4 0 23] 110 dc[<01E007180C0C180C380C300E700E700EE01CE01CE01CE018E038E030E06060C031801E 00>15 18 5 0 21]111 dc[<07870004D98008E0C008E0C011C0E011C0E001C0E001C0E00381C0 0381C00381C00381800703800703000707000706000E8C000E70000E00000E00001C00001C0000 1C00001C00003C0000FF8000>19 26 1 8 21]112 dc[<03C4062C0C3C181C3838303870387038 E070E070E070E070E0E0C0E0C0E061E063C03DC001C001C0038003800380038007803FF0>14 26 5 8 19]113 dc[<3C3C26C2468747078E068E000E000E001C001C001C001C0038003800380038 0070003000>16 18 4 0 18]114 dc[<01F006080C080C1C18181C001F001FC00FF007F0007800 386030E030C030806060C01F00>14 18 3 0 17]115 dc[<00C001C001C001C003800380038003 80FFE00700070007000E000E000E000E001C001C001C001C00384038403840388019000E00>11 26 3 0 14]116 dc[<1E0300270700470700470700870E00870E000E0E000E0E001C1C001C1C00 1C1C001C1C003838803838801838801839001C5900078E00>17 18 4 0 22]117 dc[<070E0019 910010E38020E38041C30041C00001C00001C000038000038000038000038000070200670200E7 0400CB04008B080070F000>17 18 3 0 19]120 dc[<1E03270747074707870E870E0E0E0E0E1C 1C1C1C1C1C1C1C38383838183818381C7007F00070007000E0E0C0E1C0818047003C00>16 26 4 8 20]121 dc dfe /fn df[17 6 1 -11 23]45 dc[<1C003E007F00FF80FF80FF807F003E001C00>9 9 5 0 19]46 dc[<000E00001E00007E00 07FE00FFFE00FFFE00F8FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE00 00FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE00 00FE0000FE0000FE0000FE0000FE0000FE0000FE007FFFFE7FFFFE7FFFFE>23 39 5 0 34]49 dc[<00FF800003FFF0000FFFFC001F03FE003800FF007C007F80FE003FC0FF003FC0FF003FE0FF 001FE0FF001FE07E001FE03C003FE000003FE000003FC000003FC000007F8000007F000000FE00 0000FC000001F8000003F0000003E00000078000000F0000001E0000003C00E0007000E000E000 E001C001C0038001C0070001C00FFFFFC01FFFFFC03FFFFFC07FFFFFC0FFFFFF80FFFFFF80FFFF FF80>27 39 3 0 34]50 dc[<007F800003FFF00007FFFC000F81FE001F00FF003F80FF003F80 7F803F807F803F807F801F807F800F007F800000FF000000FF000000FE000001FC000001F80000 07F00000FFC00000FFF0000001FC0000007E0000007F0000007F8000003FC000003FC000003FE0 00003FE03C003FE07E003FE0FF003FE0FF003FE0FF003FC0FF007FC07E007F807C007F003F01FE 001FFFFC0007FFF00000FF8000>27 39 3 0 34]51 dc[<00000E0000001E0000003E0000007E 000000FE000000FE000001FE000003FE0000077E00000E7E00000E7E00001C7E0000387E000070 7E0000E07E0000E07E0001C07E0003807E0007007E000E007E000E007E001C007E0038007E0070 007E00E0007E00FFFFFFF8FFFFFFF8FFFFFFF80000FE000000FE000000FE000000FE000000FE00 0000FE000000FE000000FE00007FFFF8007FFFF8007FFFF8>29 39 2 0 34]52 dc[<0C000300 0F803F000FFFFE000FFFFC000FFFF8000FFFF0000FFFE0000FFFC0000FFE00000E0000000E0000 000E0000000E0000000E0000000E0000000E7FC0000FFFF8000F80FC000E003E000C003F000000 1F8000001FC000001FC000001FE000001FE018001FE07C001FE0FE001FE0FE001FE0FE001FE0FE 001FC0FC001FC078003F8078003F803C007F001F01FE000FFFF80003FFF00000FF8000>27 39 3 0 34]53 dc[<0007F000003FFC0000FFFE0001FC0F0003F01F8007E03F800FC03F801FC03F801F 803F803F801F003F8000007F0000007F0000007F000000FF000000FF0FC000FF3FF800FF707C00 FFC03E00FFC03F00FF801F80FF801FC0FF001FC0FF001FE0FF001FE0FF001FE07F001FE07F001F E07F001FE07F001FE03F001FE03F001FC01F801FC01F803F800FC03F0007E07E0003FFFC0000FF F000003FC000>27 39 3 0 34]54 dc[<380000003E0000003FFFFFF03FFFFFF03FFFFFF07FFF FFE07FFFFFC07FFFFF807FFFFF0070000E0070000E0070001C00E0003800E0007000E000E00000 00E0000001C000000380000007800000078000000F0000000F0000001F0000001F0000003F0000 003E0000003E0000007E0000007E0000007E0000007E000000FE000000FE000000FE000000FE00 0000FE000000FE000000FE000000FE0000007C000000380000>28 41 4 0 34]55 dc[<003FC0 0001FFF00003FFFC0007C07E000F003F001E001F001E000F803E000F803E000F803F000F803F00 0F803FC00F003FF01F001FFC1E001FFE3C000FFFF80007FFE00003FFF80001FFFC0001FFFE0007 FFFF000F0FFF801E03FFC03C01FFC07C007FE078001FE0F80007E0F80007E0F80003E0F80003E0 F80003E0F80003C07C0003C07C0007803F000F001FC03E000FFFFC0003FFF800007FC000>27 39 3 0 34]56 dc[<000003800000000007C00000000007C0000000000FE0000000000FE000000000 0FE0000000001FF0000000001FF0000000003FF8000000003FF8000000003FF80000000073FC00 00000073FC00000000F3FE00000000E1FE00000000E1FE00000001C0FF00000001C0FF00000003 C0FF80000003807F80000007807FC0000007003FC0000007003FC000000E003FE000000E001FE0 00001E001FF000001C000FF000001FFFFFF000003FFFFFF800003FFFFFF80000780007FC000070 0003FC0000700003FC0000E00001FE0000E00001FE0001E00001FF0001C00000FF0001C00000FF 00FFFE001FFFFEFFFE001FFFFEFFFE001FFFFE>47 41 2 0 52]65 dc[<00003FF001800003FF FE0380000FFFFF8780003FF007DF8000FF8001FF8001FE00007F8003FC00003F8007F000001F80 0FF000000F801FE0000007801FE0000007803FC0000007803FC0000003807FC0000003807F8000 0003807F8000000000FF8000000000FF8000000000FF8000000000FF8000000000FF8000000000 FF8000000000FF8000000000FF8000000000FF80000000007F80000000007F80000000007FC000 0003803FC0000003803FC0000003801FE0000003801FE0000007000FF00000070007F000000E00 03FC00001E0001FE00003C0000FF8000F800003FF007E000000FFFFFC0000003FFFF000000003F F80000>41 41 4 0 50]67 dc[22 41 2 0 26]73 dc[47 41 3 0 54]75 dc[48 41 3 0 52]82 dc[<00 7F806003FFF0E007FFF9E00F807FE01F001FE03E0007E07C0003E07C0001E0FC0001E0FC0001E0 FC0000E0FE0000E0FE0000E0FF000000FFC000007FFE00007FFFE0003FFFFC001FFFFE000FFFFF 8007FFFFC003FFFFE000FFFFE00007FFF000007FF000000FF8000007F8000003F8600001F8E000 01F8E00001F8E00001F8F00001F0F00001F0F80003F0FC0003E0FF0007C0FFE01F80F3FFFF00E0 FFFE00C01FF000>29 41 4 0 38]83 dc[<7FFFFFFFFFC07FFFFFFFFFC07FFFFFFFFFC07F803F C03FC07E003FC007C078003FC003C078003FC003C070003FC001C0F0003FC001E0F0003FC001E0 E0003FC000E0E0003FC000E0E0003FC000E0E0003FC000E0E0003FC000E000003FC0000000003F C0000000003FC0000000003FC0000000003FC0000000003FC0000000003FC0000000003FC00000 00003FC0000000003FC0000000003FC0000000003FC0000000003FC0000000003FC0000000003F C0000000003FC0000000003FC0000000003FC0000000003FC0000000003FC0000000003FC00000 00003FC00000007FFFFFE000007FFFFFE000007FFFFFE000>43 40 2 0 48]84 dc[<01FF8000 07FFF0000F81F8001FC07E001FC07E001FC03F000F803F8007003F8000003F8000003F8000003F 80000FFF8000FFFF8007FC3F800FE03F803F803F803F003F807F003F80FE003F80FE003F80FE00 3F80FE003F807E007F807F00DF803F839FFC0FFF0FFC01FC03FC>30 27 2 0 33]97 dc[33 42 2 0 38]98 dc[<001FF80000FFFE0003F01F0007E03F 800FC03F801F803F803F801F007F800E007F0000007F000000FF000000FF000000FF000000FF00 0000FF000000FF000000FF0000007F0000007F0000007F8000003F8001C01F8001C00FC0038007 E0070003F01E0000FFFC00001FE000>26 27 2 0 31]99 dc[<00003FF80000003FF80000003F F800000003F800000003F800000003F800000003F800000003F800000003F800000003F8000000 03F800000003F800000003F800000003F800000003F800001FE3F80000FFFBF80003F03FF80007 E00FF8000FC007F8001F8003F8003F8003F8007F0003F8007F0003F8007F0003F800FF0003F800 FF0003F800FF0003F800FF0003F800FF0003F800FF0003F800FF0003F8007F0003F8007F0003F8 007F0003F8003F8003F8001F8003F8000F8007F80007C00FF80003F03BFF8000FFF3FF80003FC3 FF80>33 42 2 0 38]100 dc[<003FE00001FFF80003F07E0007C01F000F801F801F800F803F80 0FC07F000FC07F0007C07F0007E0FF0007E0FF0007E0FFFFFFE0FFFFFFE0FF000000FF000000FF 0000007F0000007F0000007F0000003F8000E01F8000E00FC001C007E0038003F81F0000FFFE00 001FF000>27 27 2 0 32]101 dc[<0007F0003FFC00FE3E01F87F03F87F03F07F07F07F07F03E 07F00007F00007F00007F00007F00007F00007F000FFFFC0FFFFC0FFFFC007F00007F00007F000 07F00007F00007F00007F00007F00007F00007F00007F00007F00007F00007F00007F00007F000 07F00007F00007F00007F00007F0007FFF807FFF807FFF80>24 42 2 0 21]102 dc[<00FF81F0 03FFE7F80FC1FE7C1F80FC7C1F007C383F007E107F007F007F007F007F007F007F007F007F007F 007F007F003F007E001F007C001F80FC000FC1F8001FFFE00018FF800038000000380000003C00 00003E0000003FFFF8001FFFFF001FFFFF800FFFFFC007FFFFE01FFFFFF03E0007F07C0001F8F8 0000F8F80000F8F80000F8F80000F87C0001F03C0001E01F0007C00FC01F8003FFFE00007FF000 >30 40 2 13 34]103 dc[33 42 3 0 38]104 dc[<07 000FC01FE03FE03FE03FE01FE00FC007000000000000000000000000000000FFE0FFE0FFE00FE0 0FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00F E0FFFEFFFEFFFE>15 43 3 0 20]105 dc[31 42 2 0 36]107 dc[15 42 3 0 20]108 dc[53 27 3 0 58]109 dc[33 27 3 0 38]110 dc[<003FE00001FFFC0003F07E000FC01F801F800FC03F800FE03F 0007E07F0007F07F0007F07F0007F0FF0007F8FF0007F8FF0007F8FF0007F8FF0007F8FF0007F8 FF0007F8FF0007F87F0007F07F0007F03F800FE03F800FE01F800FC00FC01F8007F07F0001FFFC 00003FE000>29 27 2 0 34]111 dc[33 39 2 12 38]112 dc[<001FC0380000FFF0780003 F838F80007E00DF8000FC007F8001FC007F8003F8003F8007F8003F8007F8003F8007F0003F800 FF0003F800FF0003F800FF0003F800FF0003F800FF0003F800FF0003F800FF0003F8007F0003F8 007F0003F8007F8003F8003F8003F8001F8007F8000FC007F80007E01FF80003F07BF80000FFF3 F800003FC3F800000003F800000003F800000003F800000003F800000003F800000003F8000000 03F800000003F800000003F80000003FFF8000003FFF8000003FFF80>33 39 2 12 36]113 dc[ 24 27 2 0 28]114 dc[<03FE300FFFF01E03F03800F0700070F00070F00070F80070 FC0000FFE0007FFE007FFF803FFFE01FFFF007FFF800FFF80003FC0000FC60007CE0003CF0003C F00038F80038FC0070FF01E0F7FFC0C1FF00>22 27 2 0 27]115 dc[<00700000700000700000 700000F00000F00000F00001F00003F00003F00007F0001FFFF0FFFFF0FFFFF007F00007F00007 F00007F00007F00007F00007F00007F00007F00007F00007F00007F00007F00007F03807F03807 F03807F03807F03807F03803F03803F87001F86000FFC0001F80>21 38 1 0 27]116 dc[33 27 3 0 38]117 dc[33 27 1 0 36]118 dc[47 27 1 0 50]119 dc[33 27 1 0 36]120 dc dfe /fo df[<70F8F8F870>5 5 4 0 14]46 dc[29 34 2 0 35]66 dc[31 34 2 0 37]68 dc[29 34 2 0 33]69 dc[<03FFF0001F00000F00000F00000F00000F00000F0000 0F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F0000 0F00000F00000F00000F00000F00000F00700F00F80F00F80F00F80E00F01E00401C0020380018 700007C000>20 35 2 1 25]74 dc[32 34 2 0 37]78 dc[33 35 2 1 36]82 dc[<0FE000 1838003C0C003C0E0018070000070000070000070000FF0007C7001E07003C0700780700700700 F00708F00708F00708F00F087817083C23900FC1E0>21 21 2 0 24]97 dc[<0000E0000FE000 01E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E001F8E007 04E00C02E01C01E03800E07800E07000E0F000E0F000E0F000E0F000E0F000E0F000E0F000E070 00E07800E03800E01801E00C02E0070CF001F0FE>23 35 2 0 27]100 dc[<01FC000707000C03 801C01C03801C07801E07000E0F000E0FFFFE0F00000F00000F00000F00000F000007000007800 203800201C00400E008007030000FC00>19 21 1 0 22]101 dc[<0E0000FE00001E00000E0000 0E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E1F800E60C00E80E0 0F00700F00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E0070 0E00700E00700E00700E0070FFE7FF>24 35 1 0 27]104 dc[<1C001E003E001E001C00000000 000000000000000000000000000E00FE001E000E000E000E000E000E000E000E000E000E000E00 0E000E000E000E000E000E000E00FFC0>10 34 1 0 14]105 dc[<0E00FE001E000E000E000E00 0E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E 000E000E000E000E000E000E000E000E00FFE0>11 35 1 0 14]108 dc[<0E1F80FE60C01E80E0 0F00700F00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E0070 0E00700E00700E00700E0070FFE7FF>24 21 1 0 27]110 dc[<01FC000707000C01801800C038 00E0700070700070F00078F00078F00078F00078F00078F00078F000787000707800F03800E01C 01C00E038007070001FC00>21 21 1 0 24]111 dc[<0E3CFE461E8F0F0F0F060F000E000E000E 000E000E000E000E000E000E000E000E000E000E000F00FFF0>16 21 1 0 19]114 dc[<0F8830 786018C018C008C008E008F0007F803FE00FF001F8003C801C800C800CC00CC008E018D0308FC0 >14 21 2 0 19]115 dc[23 21 1 0 26]118 dc dfe /fp df[49 49 2 0 54]69 dc[46 49 2 0 52]70 dc[73 49 2 0 78]77 dc[ 58 49 2 0 63]85 dc[<007FF8000003FFFF000007FFFFC0000FE01FE0001FF007F000 1FF003F8001FF003FC001FF001FE000FE001FE0007C001FE00010001FE00000001FE00000001FE 000001FFFE00003FFFFE0001FFF1FE0007FE01FE000FF001FE001FC001FE003F8001FE007F8001 FE00FF0001FE00FF0001FE00FF0001FE00FF0001FE00FF0003FE007F8003FE007FC00EFE003FF0 3CFF000FFFF87FF807FFF03FF800FF800FF8>37 32 2 0 40]97 dc[<0007FF00007FFFE000FF FFF003FC03F807F007FC0FE007FC1FE007FC3FC007FC3FC003F87FC001F07F8000407F800000FF 800000FF800000FF800000FF800000FF800000FF800000FF800000FF8000007F8000007FC00000 7FC000003FC0000E3FE0000E1FE0001C0FF0001C07F8007803FF01F000FFFFE0007FFF800007FC 00>31 32 3 0 37]99 dc[<0007FC0000003FFF800000FFFFE00003FC07F00007F801F8000FE0 00FC001FE0007E003FC0007E003FC0003F007FC0003F007F80003F007F80003F80FF80003F80FF 80003F80FFFFFFFF80FFFFFFFF80FFFFFFFF80FF80000000FF80000000FF800000007F80000000 7F800000003FC00000003FC00003801FC00003801FE00007800FF0000F0007F8001E0003FE00FC 0000FFFFF800003FFFE0000003FF0000>33 32 2 0 38]101 dc[<0000FF000007FFC0001FFFE0 003FC7F0007F0FF800FE0FF801FE0FF801FC0FF803FC07F003FC03E003FC01C003FC000003FC00 0003FC000003FC000003FC000003FC000003FC0000FFFFF800FFFFF800FFFFF80003FC000003FC 000003FC000003FC000003FC000003FC000003FC000003FC000003FC000003FC000003FC000003 FC000003FC000003FC000003FC000003FC000003FC000003FC000003FC000003FC000003FC0000 03FC000003FC000003FC000003FC000003FC00007FFFF0007FFFF0007FFFF000>29 50 2 0 25] 102 dc[<03C0000FF0000FF0001FF8001FF8001FFC001FF8001FF8000FF0000FF00003C0000000 0000000000000000000000000000000000000000000001F800FFF800FFF800FFF8000FF80007F8 0007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F8 0007F80007F80007F80007F80007F80007F80007F80007F80007F80007F800FFFF80FFFF80FFFF 80>17 51 3 0 23]105 dc[<01F800FFF800FFF800FFF8000FF80007F80007F80007F80007F800 07F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F800 07F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F800 07F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F800FFFFC0 FFFFC0FFFFC0>18 50 3 0 23]108 dc[<03F007F80000FFF03FFF0000FFF07FFF8000FFF0F03F C0000FF1C01FE00007F3000FE00007F6000FF00007FE000FF00007FC000FF00007FC000FF00007 F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000F F00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007 F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF000FFFFC1FF FF80FFFFC1FFFF80FFFFC1FFFF80>41 32 3 0 46]110 dc[<0007FE0000003FFFC00000FFFFF0 0003FC03FC0007F000FE000FE0007F001FC0003F803FC0003FC03FC0003FC07F80001FE07F8000 1FE07F80001FE0FF80001FF0FF80001FF0FF80001FF0FF80001FF0FF80001FF0FF80001FF0FF80 001FF0FF80001FF07F80001FE07F80001FE07F80001FE03FC0003FC03FC0003FC01FE0007F800F E0007F0007F801FE0003FE07FC0001FFFFF800003FFFC0000007FE0000>36 32 2 0 41]111 dc [<01F80FF000FFF87FFE00FFF9FFFF80FFFFE07FC00FFF001FE007FE000FF007F80007F807F800 07FC07F80003FC07F80003FE07F80003FE07F80001FE07F80001FF07F80001FF07F80001FF07F8 0001FF07F80001FF07F80001FF07F80001FF07F80001FF07F80001FE07F80003FE07F80003FE07 F80003FC07F80007FC07FC0007F807FE000FF007FF001FE007FBE07FC007F9FFFF0007F87FFE00 07F81FE00007F800000007F800000007F800000007F800000007F800000007F800000007F80000 0007F800000007F800000007F800000007F8000000FFFFC00000FFFFC00000FFFFC00000>40 46 2 14 46]112 dc[<03F03F00FFF07FC0FFF1FFE0FFF3C7F00FF38FF807F70FF807F60FF807FE0F F807FC07F007FC03E007FC008007F8000007F8000007F8000007F8000007F8000007F8000007F8 000007F8000007F8000007F8000007F8000007F8000007F8000007F8000007F8000007F8000007 F8000007F80000FFFFE000FFFFE000FFFFE000>29 32 2 0 34]114 dc[<00FF870007FFEF001F FFFF003F007F003C001F0078000F00F8000700F8000700F8000700FC000700FF000000FFF80000 7FFFC0003FFFF0003FFFFC000FFFFE0007FFFF0001FFFF80001FFF800000FFC000001FC060000F C0E00007C0E00007C0F00007C0F8000780F8000F80FE000F00FF803E00FFFFFC00F3FFF800C07F C000>26 32 3 0 33]115 dc[<00380000380000380000380000380000780000780000780000F8 0000F80001F80003F80007F8001FF800FFFFFEFFFFFEFFFFFE07F80007F80007F80007F80007F8 0007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80707F8 0707F80707F80707F80707F80707F80703F80E03FC0E01FE1C00FFF8007FF0000FE0>24 46 2 0 32]116 dc[<01F80003F000FFF801FFF000FFF801FFF000FFF801FFF0000FF8001FF00007F800 0FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF000 07F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007F800 0FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8001FF000 07F8001FF00003F8003FF00003F8006FF00001FE03CFF80000FFFF8FFF80007FFF0FFF80000FFC 0FFF80>41 32 3 0 46]117 dc[39 32 2 0 44]120 dc dfe /fq df[<04081030 206040C0C0C0C0C0C0C0C040602030100804>6 22 3 6 11]40 dc[<804020301018080C0C0C0C 0C0C0C0C08181030204080>6 22 2 6 11]41 dc[<40E040>3 3 3 0 8]46 dc[<18F818181818 181818181818FF>8 13 3 0 14]49 dc[<3E00418080C0C0C000C000C001800300040008403040 7F80FF80>10 13 2 0 14]50 dc[<1E006100C080C0C0C0C0C0C061C01EC000C0008061806300 3C00>10 13 2 0 14]57 dc[<0180018002C002C002C004600460083008301FF810181018300C F83F>16 14 2 0 20]65 dc[14 14 2 0 18]70 dc[13 14 2 0 17]76 dc[<07F0001C1C00300600600300400100C00180C00180C00180C001 806003006003003006001C1C0007F000>17 14 2 0 21]79 dc[15 14 2 0 19]80 dc[<1FA060608020802080007000 3F8003C00020001080108010C060BF80>12 14 2 0 16]83 dc[16 14 2 0 20]86 dc[<3C00620003001F006300C300 C320C3203FC0>11 9 2 0 14]97 dc[12 14 2 0 16]98 dc[<1F0021804000C000C000C000400020801F00>9 9 2 0 13 ]99 dc[<03C000C000C000C000C01EC021C040C0C0C0C0C0C0C040C021C01EF0>12 14 2 0 16] 100 dc[<1E0061004180FF80C000C000400020801F00>9 9 2 0 13]101 dc[<060B181818FE18 1818181818187E>8 14 1 0 9]102 dc[<1DE022206300630022003C0060003F003F8040C0C0C0 C0C061803F00>11 14 2 5 14]103 dc[12 14 2 0 16]104 dc[<307030000000F030303030303030FC>6 15 1 0 8] 105 dc[6 14 1 0 8]108 dc[20 9 2 0 24]109 dc[12 9 2 0 16]110 dc[<1E0061804080C0C0C0C0C0C0408061801E00>10 9 2 0 14]111 dc[12 13 2 4 16] 112 dc[8 9 2 0 11]114 dc[<7C8484F03C0682C2BC>7 9 2 0 11] 115 dc[<08081838FE181818181919190E>8 13 1 0 11]116 dc[12 9 2 0 16]117 dc[11 9 2 0 15]118 dc[16 9 2 0 20]119 dc[11 13 2 4 15]121 dc dfe /fr df[< 007E1F0001C1B1800303E3C00703C3C00E03C1800E01C0000E01C0000E01C0000E01C0000E01C0 000E01C000FFFFFC000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01 C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0007F87FC00> 26 29 0 0 24]11 dc[<007E0001C1800301800703C00E03C00E01800E00000E00000E00000E00 000E0000FFFFC00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01 C00E01C00E01C00E01C00E01C00E01C07F87F8>21 29 0 0 23]12 dc[<007FC001C1C00303C0 0703C00E01C00E01C00E01C00E01C00E01C00E01C00E01C0FFFFC00E01C00E01C00E01C00E01C0 0E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C07FCFF8 >21 29 0 0 23]13 dc[<003F07E00001C09C18000380F018000701F03C000E01E03C000E00E0 18000E00E000000E00E000000E00E000000E00E000000E00E00000FFFFFFFC000E00E01C000E00 E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E 00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C007FC7FCFF80 >33 29 0 0 35]14 dc[<6060F0F0F8F8686808080808080810101010202040408080>13 12 1 -17 21]34 dc[<0F0000C0188000C030600380703807006027FB00E0100600E0100C00E0100C00 E0101800E0101800E0103000E0106000602060007020C00030418000188180000F0303C0000606 2000060C10000C1C08001818080018380400303804006038040060380400C0380400C038040180 38040300180803001C0806000C100C000620040003C0>30 33 2 2 35]37 dc[<00E000000190 000003080000030800000708000007080000070800000708000007100000071000000720000007 40000003C03FE003800F00038006000380040005C0040009C0080010E0100030E0100060702000 60702000E0384000E03C4000E01C8000E00F0020E0070020700780403009C0401830E18007C03E 00>27 31 2 1 32]38 dc[<60F0F8680808081010204080>5 12 4 -17 12]39 dc[<00400080 0100020006000C000C0018001800300030007000600060006000E000E000E000E000E000E000E0 00E000E000E000E000E000600060006000700030003000180018000C000C000600020001000080 0040>10 42 3 11 16]40 dc[<800040002000100018000C000C00060006000300030003800180 0180018001C001C001C001C001C001C001C001C001C001C001C001C00180018001800380030003 00060006000C000C0018001000200040008000>10 42 2 11 16]41 dc[<000600000006000000 060000000600000006000000060000000600000006000000060000000600000006000000060000 00060000FFFFFFE0FFFFFFE0000600000006000000060000000600000006000000060000000600 00000600000006000000060000000600000006000000060000>27 28 2 4 32]43 dc[<60F0F0 701010101020204080>4 12 4 8 12]44 dc[11 2 0 -8 14]45 dc[<60F0F060>4 4 4 0 12]46 dc[<00010003000600060006000C000C000C001800180018003000300030006000 6000C000C000C0018001800180030003000300060006000C000C000C0018001800180030003000 3000600060006000C000C000>16 41 2 10 21]47 dc[<03C00C301818300C300C700E60066006 E007E007E007E007E007E007E007E007E007E007E007E007E00760066006700E300C300C18180C 3007E0>16 29 2 1 21]48 dc[<030007003F00C7000700070007000700070007000700070007 0007000700070007000700070007000700070007000700070007000F80FFF8>13 28 4 0 21] 49 dc[<07C01830201C400C400EF00FF80FF807F8077007000F000E000E001C001C0038007000 6000C00180030006010C01180110023FFE7FFEFFFE>16 28 2 0 21]50 dc[<07E01830201C20 1C781E780E781E381E001C001C00180030006007E00030001C001C000E000F000F700FF80FF80F F80FF00E401C201C183007E0>16 29 2 1 21]51 dc[<000C00000C00001C00003C00003C0000 5C0000DC00009C00011C00031C00021C00041C000C1C00081C00101C00301C00201C00401C00C0 1C00FFFFC0001C00001C00001C00001C00001C00001C00001C0001FFC0>18 28 1 0 21]52 dc[ <300C3FF83FF03FC020002000200020002000200023E024302818301C200E000E000F000F000F 600FF00FF00FF00F800E401E401C2038187007C0>16 29 2 1 21]53 dc[<00F0030C06040C0E 181E301E300C700070006000E3E0E430E818F00CF00EE006E007E007E007E007E0076007600770 06300E300C18180C3003E0>16 29 2 1 21]54 dc[<4000007FFF807FFF007FFF004002008004 0080040080080000100000100000200000600000400000C00000C00001C0000180000180000380 00038000038000038000078000078000078000078000078000078000030000>17 29 2 1 21] 55 dc[<03E00C301008200C20066006600660067006780C3E083FB01FE007F007F818FC307E60 1E600FC007C003C003C003C00360026004300C1C1007E0>16 29 2 1 21]56 dc[<03C00C3018 18300C700C600EE006E006E007E007E007E007E0076007700F300F18170C2707C700060006000E 300C780C78187010203030C00F80>16 29 2 1 21]57 dc[<60F0F06000000000000000000000 60F0F060>4 18 4 0 12]58 dc[<60F0F0600000000000000000000060F0F07010101010202040 80>4 26 4 8 12]59 dc[<0FE03038401CE00EF00EF00EF00E000C001C0030006000C000800180 010001000100010001000100000000000000000000000300078007800300>15 29 2 0 20]63 dc[<000600000006000000060000000F0000000F0000000F000000178000001780000017800000 23C0000023C0000023C0000041E0000041E0000041E0000080F0000080F0000180F80001007800 01FFF80003007C0002003C0002003C0006003E0004001E0004001E000C001F001E001F00FF80FF F0>28 29 1 0 31]65 dc[24 28 2 0 29]66 dc[<001F808000E061800180 1980070007800E0003801C0003801C00018038000180780000807800008070000080F0000000F0 000000F0000000F0000000F0000000F0000000F0000000F0000000700000807800008078000080 380000801C0001001C0001000E000200070004000180080000E03000001FC000>25 30 2 1 30] 67 dc[ 27 28 2 0 32]68 dc[24 28 2 0 28]69 dc[22 28 2 0 27]70 dc[<001F808000E0618001801980070007800E0003801C0003801C000180380001807800 00807800008070000080F0000000F0000000F0000000F0000000F0000000F0000000F000FFF0F0 000F80700007807800078078000780380007801C0007801C0007800E00078007000B8001801180 00E06080001F8000>28 30 2 1 33]71 dc[26 28 2 0 31]72 dc[12 28 1 0 15]73 dc[<1FFF00F8007800780078007800780078007800780078007800 78007800780078007800780078007800787078F878F878F878F0F040E021C01F00>16 29 1 1 21]74 dc[28 28 2 0 32]75 dc[21 28 2 0 26]76 dc[33 28 2 0 38]77 dc[26 28 2 0 31]78 dc[<003F800000E0E0000380 380007001C000E000E001C0007003C00078038000380780003C0780003C0700001C0F00001E0F0 0001E0F00001E0F00001E0F00001E0F00001E0F00001E0F00001E0700001C0780003C0780003C0 380003803C0007801C0007000E000E0007001C000380380000E0E000003F8000>27 30 2 1 32] 79 dc[23 28 2 0 28]80 dc[28 29 2 1 31]82 dc[<07E0801C19803005 80700380600180E00180E00080E00080E00080F00000F800007C00007FC0003FF8001FFE0007FF 0000FF80000F800007C00003C00001C08001C08001C08001C0C00180C00180E00300D00200CC0C 0083F800>18 30 2 1 23]83 dc[<7FFFFFC0700F01C0600F00C0400F0040400F0040C00F0020 800F0020800F0020800F0020000F0000000F0000000F0000000F0000000F0000000F0000000F00 00000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F 0000001F800003FFFC00>27 28 1 0 30]84 dc[26 29 2 1 31]85 dc[28 29 1 1 31]86 dc[40 29 1 1 43]87 dc[<7FF0FFC00FC03E000780180003C0180003E0100001E0200001F0600000F040000078800000 7D8000003D0000001E0000001F0000000F0000000F8000000F80000013C0000023E0000021E000 0041F00000C0F8000080780001007C0003003C0002001E0006001F001F003F80FFC0FFF0>28 28 1 0 31]88 dc[7 41 4 10 12]91 dc[<08081010202040404040808080808080B0B0F8 F878783030>13 12 6 -17 21]92 dc[7 41 0 10 12]93 dc[<1FC000307000783800 781C00301C00001C00001C0001FC000F1C00381C00701C00601C00E01C40E01C40E01C40603C40 304E801F8700>18 18 2 0 21]97 dc[19 29 1 0 23]98 dc[<07E0 0C301878307870306000E000E000E000E000E000E00060007004300418080C3007C0>14 18 2 0 18]99 dc[<003F0000070000070000070000070000070000070000070000070000070000070003 E7000C1700180F00300700700700600700E00700E00700E00700E00700E00700E0070060070070 0700300700180F000C370007C7E0>19 29 2 0 23]100 dc[<03E00C301818300C700E6006E006 FFFEE000E000E000E00060007002300218040C1803E0>15 18 1 0 18]101 dc[<00F8018C071E 061E0E0C0E000E000E000E000E000E00FFE00E000E000E000E000E000E000E000E000E000E000E 000E000E000E000E000E007FE0>15 29 0 0 13]102 dc[<00038003C4C00C38C01C3880181800 381C00381C00381C00381C001818001C38000C300013C0001000003000001800001FF8001FFF00 1FFF803003806001C0C000C0C000C0C000C06001803003001C0E0007F800>18 28 1 9 21]103 dc[20 29 1 0 23]104 dc[<18003C003C001800000000000000000000 0000000000FC001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C00 FF80>9 29 1 0 12]105 dc[<00C001E001E000C000000000000000000000000000000FE000E0 00E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E060 E0F0C0F1C061803E00>11 37 -3 8 13]106 dc[19 29 1 0 22]107 dc[9 29 1 0 12]108 dc[33 18 1 0 36]109 dc[20 18 1 0 23] 110 dc[<03F0000E1C00180600300300700380600180E001C0E001C0E001C0E001C0E001C0E001 C06001807003803003001806000E1C0003F000>18 18 1 0 21]111 dc[19 26 1 8 23]112 dc[<03C1000C3300180B00300F00700700700700E00700E00700E00700E00700E00700E0070060 0700700700300F00180F000C370007C70000070000070000070000070000070000070000070000 3FE0>19 26 2 8 22]113 dc[13 18 1 0 16]114 dc[<1F9030704030C010C010E010F8007F803FE0 0FF000F880388018C018C018E010D0608FC0>13 18 1 0 16]115 dc[<04000400040004000C00 0C001C003C00FFE01C001C001C001C001C001C001C001C001C001C101C101C101C101C100C100E 2003C0>12 26 1 0 16]116 dc[20 18 1 0 23]117 dc [19 18 1 0 22]118 dc[27 18 1 0 30]119 dc[<7F8FF00F03800F 030007020003840001C80001D80000F00000700000780000F800009C00010E00020E0006070004 03801E07C0FF0FF8>21 18 0 0 22]120 dc[19 26 1 8 22]121 dc[<7FFC70386038407040 F040E041C003C0038007000F040E041C043C0C380870087038FFF8>14 18 1 0 18]122 dc[20 1 0 -11 21]123 dc dfe end TeXDict begin @letter %%EndProlog %%Page: 2 1 bop -75 -59 a fq(A)10 b(v)o(ersion)f(of)h(this)g(paper)f(will)h(appear)f(in) h(the)e(Fifth)i(Symp)n(osium)f(on)g(Arc)o(hitectural)h(Supp)o(ort)g(for)f(Pro\ gramming)f(Languages)h(and)f(Op)q(erating)i(Systems)e(\(ASPLOS)h(V\).)h(Octob) q(er)f(1992.)226 33 y fp(F)-7 b(ast)27 b(Mutual)h(Exclusion)e(for)i(Unipro)s (cessors)776 139 y fo(Brian)16 b(N.)f(Bershad)710 220 y fr(Sc)o(ho)q(ol)e(of) h(Computer)f(Science)715 266 y(Carnegie)h(Mellon)f(Univ)o(ersit)o(y)781 311 y (5000)g(F)l(orb)r(es)h(Av)o(enue)766 356 y(Pittsburgh,)g(P)m(A)g(15213)596 491 y fo(David)h(D.)h(Redell)f(and)i(John)g(R.)f(Ellis)677 572 y fr(Digital)c(Equ\ ipmen)n(t)i(Corp)q(oration)735 617 y(Systems)f(Research)h(Center)789 663 y (130)f(Lytton)h(Av)o(en)o(ue)774 708 y(P)o(alo)f(Alto,)g(CA)h(94301)-75 910 y fn(Abstract)-75 996 y fr(In)e(this)g(pap)q(er)h(w)o(e)f(describ)s(e)g(restart\ able)h(atomic)d(sequences,)-75 1041 y(an)31 b fm(optimistic)f fr(mec)o(hanism) f(for)i(implemen)l(ting)g(simple)-75 1087 y(atomic)12 b(op)q(erations)i(\(suc\ h)g(as)f fm(T)m(est-A)n(nd-Set)p fr(\))i(on)e(a)h(unipro-)-75 1132 y(cessor.) 19 b(A)12 b(thread)h(that)f(is)f(susp)r(ended)i(within)f(a)f(restartable)-75 1177 y(atomic)25 b(sequence)k(is)e(resumed)g(b)o(y)g(the)g(op)q(erating)g(sys\ -)-75 1223 y(tem)c(at)h(the)g(b)r(eginning)f(of)g(the)i(sequence,)j(rather)c (than)-75 1268 y(at)18 b(the)g(p)q(oin)n(t)g(of)f(susp)r(ension.)30 b(This)18 b(guaran)n(tees)h(that)f(the)-75 1313 y(thread)d(ev)o(entually)e(executes)j (the)f(sequence)h fm(atomic)n(al)r(ly.)j fr(A)-75 1359 y(restartable)c(atomic) e(sequence)j(has)f(signi\014can)n(tly)f(less)h(o)n(v)o(er-)-75 1404 y(head)f (than)g(other)h(soft)o(w)n(are-based)g(synchronization)e(mec)o(h-)-75 1449 y (anisms,)k(suc)o(h)h(as)g(k)o(ernel)g(em)n(ulation)e(or)i(soft)o(w)n(are)h (reserv)o(a-)-75 1495 y(tion.)29 b(Consequen)o(tly)m(,)18 b(it)f(is)g(an)h (attractiv)n(e)g(alternativ)o(e)g(for)-75 1540 y(use)h(on)f(unipro)q(cessors) i(that)e(do)g(not)g(supp)r(ort)g(atomic)f(op-)-75 1585 y(erations.)29 b(Ev)o (en)18 b(on)f(pro)q(cessors)i(that)f(do)f(supp)r(ort)g(atomic)-75 1631 y(op)q (erations)i(in)g(hardw)o(are,)h(restartable)g(atomic)d(sequences)-75 1676 y (can)d(ha)o(v)o(e)g(lo)n(w)o(er)g(o)o(v)o(erhead.)-33 1721 y(W)l(e)f(describ) s(e)g(di\013erent)h(implem)o(en)m(tations)f(of)f(restartable)-75 1767 y(atomi\ c)g(sequences)k(for)d(the)i(Mac)o(h)e(3.0)g(and)h(T)l(aos)g(op)q(erating)-75 1812 y(systems.)k(These)e(systems')d(thread)i(managemen)l(t)f(pack)m(ages)-75 1843 y 396 2 v -11 1916 a fl(This)j(researc)o(h)d(w)o(as)k(sp)q(onsored)c(in) j(part)f(b)o(y)g(The)h(Defense)f(Ad-)-75 1951 y(v)n(anced)7 b(Researc)o(h)g (Pro)q(jects)h(Agency)m(,)g(Information)e(Science)g(and)i(T)m(ec)o(h-)-75 1987 y(nology)g(O\016ce,)i(under)f(the)g(title)f(\\Researc)o(h)g(on)h(P)o(arallel) g(Computing",)-75 2023 y(ARP)m(A)h(Order)f(No.)15 b(7330,)8 b(issued)g(b)o (y)g(D)o(ARP)m(A/CMO)k(under)7 b(Con)o(tract)-75 2059 y(MD)o(A972-90-C-0035,) 13 b(b)o(y)h(the)g(Op)q(en)g(Soft)o(w)o(are)f(F)m(oundation)f(\(OSF\),)-75 2095 y(and)e(b)o(y)g(a)h(gran)o(t)e(from)h(the)g(Digital)f(Equipmen)o(t)g(Cor\ p)q(oration)f(\(DEC\).)-75 2131 y(Bershad)15 b(w)o(as)i(partially)d(supp)q (orted)g(b)o(y)i(a)h(National)e(Science)g(F)m(oun-)-75 2167 y(dation)e(Presid\ en)o(tial)f(Y)m(oung)i(In)o(v)o(estigator)d(Aw)o(ard.)25 b(The)15 b(views)g (and)-75 2203 y(conclusions)9 b(con)o(tained)g(in)j(this)f(do)q(cumen)o(t)e (are)i(those)g(of)g(the)h(authors)-75 2239 y(and)c(should)g(not)g(b)q(e)h(in) o(terpreted)c(as)k(represen)o(ting)d(the)i(o\016cial)h(p)q(olicies,)-75 2274 y (either)g(expressed)g(or)h(implied,)f(of)h(D)o(ARP)m(A,)h(OSF,)g(DEC,)g(the)f (NSF,)h(or)-75 2310 y(the)g(U.S.)g(go)o(v)o(ernmen)o(t.)1013 897 y fr(rely)22 b(on)f(atomic)f(op)q(erations)i(to)g(implemen)l(t)g(higher-lev)o(el)1013 942 y (m)m(utual)d(exclusion)g(facilities.)33 b(W)l(e)19 b(sho)o(w)g(that)h(impro)m (ving)1013 988 y(the)h(p)r(erformance)f(of)h(lo)n(w-lev)o(el)g(atomic)e(op)q (erations,)k(and)1013 1033 y(therefore)c(m)m(utual)e(exclusion)h(mec)n(hanism\ s,)f(impro)m(v)o(es)h(ap-)1013 1078 y(plication)12 b(p)q(erformance.)1013 1214 y fn(1)69 b(In)n(tro)r(duction)1013 1302 y fr(In)12 b(this)g(pap)q(er)g(w)o (e)h(describ)r(e)f(restartable)i(atomic)c(sequences,)1013 1347 y(an)15 b fm (optimistic)f fr(mec)n(hanism)g(for)h(implemen)l(ting)g(atomic)e(op-)1013 1393 y(erations)e(on)g(a)g(unipro)q(cessor.)19 b(Our)11 b(approac)o(h)h(assumes)f (that)1013 1438 y(short,)22 b(atomic)c(sequences)23 b(are)e(rarely)g(in)n(ter\ rupted.)40 b(If)20 b(a)1013 1483 y(thread)g(is)f(in)o(terrupted)i(during)e (an)g(atomic)f(sequence,)23 b(w)o(e)1013 1529 y(rely)f(on)g(a)g(recov)o(ery)g (mec)o(hanism)e(pro)o(vided)j(b)o(y)f(the)h(k)n(er-)1013 1574 y(nel)c(that)h (resumes)h(the)f(thread)h(at)e(the)i(b)q(eginning)e(of)g(the)1013 1619 y(sequ\ ence.)44 b(W)l(e)23 b(ha)o(v)n(e)g(implemen)l(ted)g(restartable)g(atomic)1013 1665 y(sequences)h(in)e(the)h(Mac)o(h)f(3.0)f([Accetta)i(et)g(al.)42 b(86])21 b(and)1013 1710 y(T)l(aos)12 b([Thac)o(k)n(er)h(et)g(al.)j(88])11 b(op)q(erat\ ing)h(systems,)g(using)g(a)g(dif-)1013 1755 y(feren)o(t)e(method)f(in)g(each.) 16 b(W)m(e)9 b(sho)o(w)h(that)f(restartable)i(atomic)1013 1801 y(sequences)24 b(are)f(signi\014can)o(tly)f(more)f(e\016cien)o(t)i(than)f(other)1013 1846 y (soft)n(w)o(are)d(techniques.)31 b(W)l(e)19 b(ha)o(v)n(e)g(measured)f(p)q(erf\ ormance)1013 1891 y(impro)m(v)n(emen)o(ts)10 b(of)f(up)g(to)h(50%)e(for)i(som\ e)e(applications)h(on)g(the)1013 1937 y(MIPS)21 b(R3000-based)e([Kane)i(87])f (DECstation)g(5000/200,)1013 1982 y(whic)n(h)c(do)q(es)g(not)g(ha)o(v)o(e)g (hardw)o(are)g(supp)q(ort)g(for)f(atomic)f(op-)1013 2027 y(erations.)19 b(In) 14 b(addition,)f(w)o(e)i(sho)o(w)f(that)g(restartable)i(atomic)1013 2073 y (sequences)d(outp)q(erform)d(hardw)o(are)i(mec)n(hanisms)e(on)h(pro)q(ces-) 1013 2118 y(sors)j(that)f(do)g(pro)o(vide)g(explicit)g(supp)r(ort)g(for)g(ato\ mic)f(op)q(era-)1013 2163 y(tions.)1013 2279 y fk(1.1)55 b(Motiv)l(ation)1013 2353 y fr(Multithreaded)13 b(programs)f(use)i(m)m(utual)e(exclusion)i(to)e (guar-)1013 2398 y(an)n(tee)f(consistency)h(of)d(shared)i(data)f(structures.) 19 b(Mutual)10 b(ex-)1013 2444 y(clusion)h(mec)n(hanisms)f(such)h(as)h fm(P,) h(V)e fr([Dijkstra)f(68a])h(and)g fm(ac-)1013 2489 y(quir)m(e)s 13 2 v 12 w (mutex,)i(r)m(ele)n(ase)s 13 2 v 12 w(mutex)e fr([Birrell)f(91])f(are)i(imple\ men)l(ted)1013 2534 y(using)j(lo)n(w)o(er-lev)o(el)g(op)q(erations)h(such)f (as)h fm(T)l(est-A)o(nd-Set)g fr(that)1013 2580 y(gran)n(t)h(one)g(of)f(sever\ al)g(threads)i(m)m(utually)e(exclusiv)o(e)h(access)1013 2625 y(to)9 b(some)g (data)g(structure.)19 b(Ev)o(en)10 b(on)f(a)h(uniprocessor,)i(m)m(utual)p eop %%Page: 3 2 bop -75 -46 a fr(exclusion)19 b(is)g(necessary)h(to)f(protect)h(shared)g(dat\ a)e(against)-75 -1 y(an)i(in)n(terleav)n(ed)h(thread)g(sc)o(hedule.)37 b(In)o (terleaving)19 b(can)h(o)q(c-)-75 44 y(cur)15 b(when)h(a)e(thread)i(is)e fm (susp)o(ende)n(d)h fr(\(due)g(to)g(a)g(sync)o(hronous)-75 90 y(fault)9 b(or)g (an)h(async)o(hronous)g(preemption\),)g(or)f(when)h(a)g(thread)-75 135 y fm (blo)n(cks)15 b fr(\(due)h(to)f(the)h(thread)f(v)o(olun)n(tarily)g(relinquish\ ing)f(the)-75 180 y(pro)q(cessor\).)-33 230 y(E\016cien)o(t)e(m)n(utual)f(exc\ lusion)i(mec)n(hanisms)e(are)i(b)q(ecoming)-75 275 y(increasingly)20 b(import\ an)n(t)h(on)f(unipro)q(cessors)j(for)d(t)o(w)o(o)g(rea-)-75 320 y(sons.)25 b (First,)17 b(mo)o(dern)g(applications)f(use)h(m)m(ultiple)e(threads)-75 366 y (as)j(a)g(program)f(structuring)i(device,)h(as)e(a)g(mec)n(hanism)f(for)-75 411 y(p)q(ortabilit)n(y)g(to)h(m)n(ultiprocessors,)i(and)e(as)g(a)f(w)o(a)o (y)h(to)f(man-)-75 456 y(age)22 b(I/O)g(and)g(server)g(concurrency)j(ev)o(en) d(when)h(no)f(true)-75 502 y(CPU)15 b(parallelism)e(is)i(a)n(v)n(ailable.)20 b (Second,)15 b(man)n(y)g(op)q(erating)-75 547 y(systems)j(to)q(da)o(y)g(are)g (built)f(on)h(top)g(of)f(a)g(microk)n(ernel)h(that)-75 592 y(supp)r(orts)23 b (relativ)n(ely)f(few)h(services;)28 b(for)22 b(example)f(thread)-75 638 y(sch\ eduling,)e(virtual)f(memory)e(and)i(in)o(terpro)r(cess)i(comm)m(u-)-75 683 y (nication)11 b([Mullender)g(et)i(al.)j(90,)11 b(Cheriton)g(88,)g(Rozier)h(et) g(al.)-75 728 y(88,)e(Accetta)j(et)f(al.)k(86,)10 b(Thac)o(k)o(er)i(et)g(al.) k(88].)g(Other)d(services)-75 774 y(such)d(as)h(the)g(\014le)f(system)h(and)f (net)o(w)o(orking)g(are)h(implem)o(en)m(ted)-75 819 y(as)19 b(m)n(ultithreade\ d)h(user-lev)o(el)g(applications.)33 b(The)20 b(micro-)-75 864 y(k)o(ernel)13 b(approac)o(h)g(exp)r(oses)h(the)g(p)q(erformance)f(of)f(a)h(system's)-75 910 y(m)m(utual)i(exclusion)f(primitiv)m(es;)h(ev)o(en)g(single)g(threaded)h(pro-) -75 955 y(grams)d(rely)h(on)g(basic)g(op)q(erating)g(system)g(services)i(that) e(are)-75 1000 y(implemen)l(ted)f(outside)f(the)h(k)o(ernel)f(using)g(m)n(ult\ iple)f(threads.)-75 1046 y(The)20 b(p)q(erformance)f(of)f(all)g(applications) h(is)g(therefore)h(ulti-)-75 1091 y(mately)9 b(in\015uenced)j(b)o(y)e(the)h (p)q(erformance)g(of)f(the)h(underlying)-75 1136 y(m)m(utual)j(exclusion)g (mec)n(hanisms.)-33 1186 y(The)i(mec)n(hanisms)e(that)i(ha)o(v)n(e)g(b)r(een) g(used)h(to)e(implemen)l(t)-75 1231 y(atomic)20 b(op)q(erations)j(on)f(a)g (unipro)q(cessor)h(\(i.e.,)g(those)g(de-)-75 1276 y(scrib)r(ed)12 b(in)f(ev)o (ery)h(undergraduate)g(op)q(erating)f(systems)h(text-)-75 1322 y(b)q(o)q(ok\)) 21 b(can)h(b)q(e)f(characterized)h(as)g fm(p)n(essimistic)p fr(.)39 b(That)21 b(is,)-75 1367 y(their)f(design)f(assumes)g(that)g(atomicit)m(y)g(ma)m(y)h (b)q(e)f(violated)-75 1412 y(at)13 b(an)o(y)g(momen)m(t)g(\(e.g.,)g(with)g (an)h(in)n(terrupt\),)h(and)e(therefore)-75 1458 y(guards)k(against)f(this)h (p)r(oten)o(tial)f(violation)f(ev)o(ery)i(time)f(the)-75 1503 y(atomic)e(op)q (eration)h(is)g(executed.)25 b(This)16 b(approac)o(h,)f(though,)-75 1548 y (can)e(incur)g(a)g(high)f(o)o(v)n(erhead)i(that)f(a\013ects)h(the)g(p)q(erfor\ mance)-75 1594 y(of)i(applications)f(relying)g(on)h(m)n(utual)g(exclusion,)g (either)h(di-)-75 1639 y(rectly)e(or)e(indirectly)m(.)-33 1688 y(In)18 b(con) o(trast,)h(the)f(optimistic)e(mec)o(hanism)g(describ)r(ed)j(in)-75 1734 y(thi\ s)h(pap)q(er)h(assumes)e(that)h(atomic)f(sequences)j(are)e(rarely)-75 1779 y (in)n(terrupted,)13 b(and)d(adopts)h(an)f(inexp)q(ensive)h(solution)e(for)h (this)-75 1824 y(assumed)k(common)d(case.)19 b(W)l(e)c(sho)o(w)f(that)g(this) g(assumption)-75 1870 y(is)d(b)q(oth)g(accurate,)i(and)e(e\013ective)g(at)h (reducing)f(the)h(o)o(v)n(erhead)-75 1915 y(of)h(m)n(utual)g(exclusion.)-75 2047 y fk(1.2)56 b(The)18 b(rest)g(of)h(this)f(pap)r(er)-75 2126 y fr(In)e (the)h(next)g(section)g(w)o(e)f(describ)r(e)h(restartable)g(atomic)e(se-)-75 2172 y(quences)k(after)e(reviewing)g(several)g(p)q(essimistic)f(techniques) -75 2217 y(for)j(ensuring)h(m)n(utual)f(exclusion)h(on)f(a)h(uniprocessor.)37 b(In)-75 2262 y(Section)23 b(3)g(w)o(e)g(discuss)h(implemen)l(tations)f(of)f (restartable)-75 2308 y(atomic)10 b(sequences)k(for)e(the)g(Mac)o(h)g(and)f (T)m(aos)g(op)q(erating)h(sys-)-75 2353 y(tems.)28 b(In)17 b(Section)h(4)f (w)n(e)h(discuss)h(some)d(of)h(the)g(k)o(ernel)h(de-)-75 2398 y(sign)i(issues) h(that)f(arise)h(when)g(implem)o(en)m(ting)e(restartable)-75 2444 y(atomic)f (sequences.)38 b(In)20 b(Section)g(5)f(w)o(e)h(sho)o(w)g(the)g(p)q(erfor-)-75 2489 y(mance)13 b(impact)f(of)h(using)g(restartable)i(atomic)d(sequences)k (in)-75 2534 y(the)e(Mac)o(h)f(op)q(erating)g(system.)k(In)c(Section)h(6)e (w)o(e)h(sho)o(w)g(that)-75 2580 y(restartable)19 b(atomic)e(sequences)k(ha)n (v)o(e)e(less)g(o)n(v)o(erhead)g(than)-75 2625 y(equiv)n(alen)n(t)f(hardw)o (are)g(mec)n(hanisms)e(on)i(sev)o(eral)g(pro)q(cessor)1013 -46 y(arc)o(hitect\ ures.)i(In)14 b(Section)g(7)g(w)n(e)h(discuss)g(related)f(w)o(ork.)k(In)1013 -1 y(Section)c(8)f(w)o(e)h(presen)q(t)g(our)g(conclusions.)1013 147 y fn(2)69 b(Implemen)n(ti)o(ng)37 b(m)n(utual)i(exclu-)1116 215 y(sion)22 b(on)i(a)f (unipro)r(cessor)1013 308 y fr(This)10 b(section)h(describ)r(es)g(four)g(tech\ niques)f(for)g(implemen)m(ting)1013 353 y(atomic)i(primitiv)m(es)j(suitable)f (for)g(use)h(b)o(y)g(m)m(utual)f(exclusion)1013 398 y(mec)n(hanisms)f(on)g (a)h(unipro)q(cessor.)20 b(W)l(e)15 b(concentrate)g(on)e(the)1013 444 y(sp)q (eci\014c)i(atomic)d(primitiv)m(e)i fm(T)m(est-A)n(nd-Set)p fr(,)g(although)f (other)1013 489 y(primitiv)l(es,)f(such)g(as)f fm(F)m(etch-A)o(nd-A)n(dd)p fr (,)h fm(L)n(o)n(ad-Linke)o(d/Stor)n(e-)1013 534 y(Conditional)p fr(,)k(and)g fm(Memory-R)n(e)n(gister-Exchange)h fr(could)f(b)r(e)1013 580 y(similarly)h (constructed.)41 b(Eac)o(h)21 b(of)f(these)i(primitiv)m(es)f(p)q(er-)1013 625 y(forms)d(an)i(atomic)e(read-modify-write)i(of)f(a)h(single)g(mem-)1013 670 y (ory)c(lo)q(cation.)27 b(Three)18 b(of)f(the)h(tec)o(hniques,)g(memory)d(in)n (ter-)1013 716 y(loc)o(k)o(ed)c(instructions,)g(soft)o(w)o(are)f(reservation) f(and)h(k)o(ernel)h(em-)1013 761 y(ulation,)f(are)i(p)q(essimistic.)17 b(The) 12 b(fourth,)f(restartable)i(atomic)1013 806 y(sequences,)i(is)f(based)h(on)e (the)i(optimistic)d(approac)o(h.)1013 935 y fk(2.1)55 b(Memory-in)l(terloc)o (k)n(ed)18 b(instructions)1013 1013 y fr(Memory-in)m(terlo)q(c)o(k)o(ed)30 b (instructions)g(\(or)f(instruction)g(se-)1013 1058 y(quences\))24 b(require)g (sp)q(ecial)f(hardw)o(are)g(supp)r(ort)f(from)f(the)1013 1104 y(pro)q(cessor) 14 b(and)f(bus)g(to)f(ensure)j(that)e(a)f(giv)n(en)h(memory)e(loca-)1013 1149 y(tion)k(can)h(b)r(e)g(read,)h(mo)o(di\014ed)g(and)e(written)i(without)f(in)n (ter-)1013 1194 y(ruption.)g(Memory-in)m(terlo)r(c)o(k)o(ed)10 b(instructions) g(are)h(primarily)1013 1240 y(in)n(tended)17 b(to)g(supp)q(ort)g(m)m(ultipro) q(cessing,)g(but)g(can)f(b)q(e)h(used)1013 1285 y(on)i(unipro)q(cessor)i(syst\ ems)g(as)e(w)o(ell.)36 b(Unfortunately)l(,)21 b(not)1013 1330 y(all)8 b(pro)q (cessors)k(supp)r(ort)d(memory-in)l(terlo)r(c)o(k)o(ed)h(instructions,)1013 1376 y(and)g(man)m(y)h(that)g(do,)g(do)g(so)g(reluctan)o(tly;)g(i.e.,)f(the)i (cycle)f(time)1013 1421 y(for)16 b(an)g(in)n(terlo)r(c)o(k)o(ed)h(access)h (is)e(several)g(times)g(greater)h(than)1013 1466 y(that)e(for)g(a)h(non-in)n (terlo)q(ck)n(ed)g(access.)25 b(The)16 b(reasons)h(for)e(the)1013 1512 y(high\ er)i(cost)g(are)h(increased)g(complexit)m(y)f([In)o(tel860)f(89],)g(an)1013 1557 y(o)n(v)o(erly)j(ric)o(h)g(set)h(of)f(atomic)e(op)q(erations)i([Leonard) g(87,)f(In-)1013 1602 y(tel386)12 b(90],)g(supp)q(ort)i(for)e(atomic)f(up)r (dates)j(on)e(arbitrary)h(bit)1013 1648 y(b)q(oundaries)i([Leonard)f(87],)g (and)g(the)i(fact)f(that)f(atomic)f(op-)1013 1693 y(erations)e(ma)m(y)h(b)o (ypass)g(the)g(on-c)o(hip)f(cac)o(he)h([Motorola)e(88100)1013 1738 y(88].)16 b (A)e(goo)q(d)g(surv)o(ey)g(of)e(memory-in)l(terlo)q(ck)n(ed)i(instructions) 1013 1784 y(and)19 b(their)i(implem)o(en)m(tations)e(can)h(b)r(e)g(found)f (in)h([Glew)f(&)1013 1829 y(Hwu)14 b(91].)1013 1957 y fk(2.2)55 b(Soft)o(w)o (are)18 b(reserv)-5 b(ation)1013 2036 y fr(A)n(tomic)15 b(op)q(erations)h(can) f(also)h(b)q(e)g(constructed)i(using)d(soft-)1013 2081 y(w)n(are)e(reserv)o (ation)e(algorithms,)f(such)i(as)g(Dekk)o(er's)g([Dijkstra)1013 2126 y(68b],) k(P)o(eterson's)i([P)o(eterson)g(81])e(or)g(Lamport's)h([Lamp)o(ort)1013 2172 y(87].)g(Roughly)12 b(sp)r(eaking,)h(with)h(soft)o(w)n(are)h(reserv)o(ation)e (algo-)1013 2217 y(rithms,)f(a)h(thread)i(m)m(ust)f(register)h(its)f(in)n(ten\ t)g(to)f(p)q(erform)g(an)1013 2262 y(atomic)h(op)q(eration)i(and)g(then)h(w)o (ait)e(un)o(til)h(no)f(other)i(thread)1013 2308 y(has)f(registered)j(a)e(simi\ lar)d(in)n(tent)j(b)q(efore)g(pro)r(ceeding.)27 b(W)m(e)1013 2353 y(use)13 b (Lamport's)f(fast)h(m)m(utual)f(exclusion)h(algorithm)d(to)j(ev)n(al-)1013 2398 y(uate)23 b(soft)n(w)o(are)g(reservation)f(sc)o(hemes)h(since)h(it)e(has) h(b)q(een)1013 2444 y(pro)n(v)o(en)14 b(correct)h(and)e(sho)o(wn)h(to)f(b)q (e)h(optimal.)h(If)e(one)g(is)h(will-)1013 2489 y(ing)e(to)i(put)f(an)g(upp)r (er)h(b)q(ound)g(on)f(the)h(duration)f(of)g(the)h(crit-)1013 2534 y(ical)f (section,)i(then)g(it)f(is)g(p)q(ossible)h(to)f(implemen)l(t)g(m)n(ultipro-) 1013 2580 y(cessor)21 b(m)m(utual)e(exclusion)h(with)f(few)o(er)i(instruction\ s)f(than)1013 2625 y(required)f(b)o(y)g(Lamp)o(ort's)g(algorithm.)29 b(Such) 19 b(a)f(limitatio)o(n,)p eop %%Page: 4 3 bop -75 -46 a fr(though,)18 b(is)g(generally)g(not)g(feasible)g(on)g(a)f(m)n (ultiprocessor,)-75 -1 y(and)d(w)o(ould)f(b)q(e)h(nearly)g(imp)o(ossible)g (on)g(a)g(uniprocessor.)-33 46 y(In)22 b(Lamp)o(ort's)h(algorithm,)e(sho)o (wn)h(in)g(Figure)g(1,)i(eac)o(h)-75 91 y(thread)16 b(has)f(a)g(unique)g(iden) o(ti\014er)h fj(i)f fr(whic)o(h)g(is)g(used)h(to)f(place)-75 137 y(reserv)o (ations)i(in)n(to)g(the)h(v)m(ariable)f fj(x)p fr(,)g(and)f(to)h(indicate)g (o)o(wn-)-75 182 y(ership)j(of)e(the)i(lo)q(c)o(k)f(via)f(the)i(v)n(ariable)e fj(y)r fr(.)34 b(In)19 b(the)h(normal)-75 227 y(case)13 b(\(no)g(con)o(ten)o (tion,)f(no)g(collision\),)f(Lamport's)h(algorithm)-75 273 y(requires)19 b (t)o(w)o(o)e(loads)h(and)f(\014v)o(e)h(stores,)i(executing)e(in)g(order)-75 318 y(the)f(lines)f([1,2,3,9,10,)o(19,)o(21,)o(22])o(.)23 b(If)16 b(a)g(threa\ d)h(reaches)g(line)-75 363 y(3,)g(though,)h(and)e(\014nds)i(that)f(the)h(lo)q (c)o(k)f(is)g(held)g(b)o(y)g(another)-75 408 y(thread,)g(there)g(is)f fm(c)n (ontention)p fr(,)h(and)f(the)h(thread)g(m)n(ust)f(w)o(ait)-75 454 y(un)o(til) 11 b(the)i(lock)f(is)g(released.)18 b(The)13 b(arra)o(y)f fj(b)g fr(is)g(used) h(to)f(resolv)o(e)-75 499 y fm(c)n(ol)r(lisions)p fr(,)k(whic)o(h)g(o)q(ccur) h(whenever)g(t)o(w)o(o)f(or)g(more)f(threads)-75 544 y(\014nd)e(that)g(the)h (loc)o(k)f(is)g(free)h(at)f(line)f(3)h(and)g(pro)q(ceed)h(to)f(line)g(9)-75 590 y(sim)m(ultaneously)i(\(or)g(through)g(an)g(in)n(terlea)o(v)o(ed)h(sc)o (hedule)g(on)-75 635 y(a)i(uniprocessor\).)32 b(A)18 b(collision)e(b)o(y)i fj (n)f fr(threads)i(will)e(b)q(e)h(de-)-75 680 y(tected)13 b(at)f(line)f(10)g (b)o(y)g fj(n)5 b fi(\000)g fr(1)12 b(of)f(them;)g(those)h fj(n)5 b fi(\000)g fr(1)11 b(will)f(enter)-75 726 y(the)19 b(loop)f(at)g(line)g(12)f(and)h(w)o (ait)g(un)o(til)f(the)i(collisions)e(ha)n(v)o(e)-75 771 y(settled)h(out)e(\(l\ ines)h(12)f(through)h(15\).)25 b(The)18 b fh(await)d fr(used)j(at)-75 816 y (lines)12 b(5,)g(12)g(and)g(14)g(is)g(necessary)j(when)d(there)i(is)e(conten) o(tion)-75 862 y(or)h(collision,)d(and)j(can)g(b)q(e)g(implemen)l(ted)g(on)g (a)f(unipro)q(cessor)-75 907 y(b)o(y)f(ha)o(ving)g(the)h(a)o(w)o(aiting)e(thr\ ead)i(yield)f(its)h(pro)q(cessor)h(to)f(the)-75 952 y(scheduler.)-75 1067 y fg (start:)-55 1109 y(1)38 b(b[i])19 b(:=)f(true;)-55 1150 y(2)38 b(x)20 b(:=)f (i;)-55 1192 y(3)38 b(if)h(y)19 b(<>)g(0)39 b(then)116 b({)19 b(Contention)d (})-55 1233 y(4)78 b(b[i])18 b(:=)h(false;)-55 1275 y(5)78 b(await)17 b(\(y)i (=)g(0\);)-55 1317 y(6)78 b(goto)18 b(start;)-55 1358 y(7)38 b(end;)-55 1400 y (8)-55 1441 y(9)g(y)20 b(:=)f(i;)-75 1483 y(10)38 b(if)19 b(x)h(<>)e(i)i(then) 116 b({)19 b(Collision)d(})-75 1524 y(11)78 b(b[i])18 b(:=)h(false;)-75 1566 y (12)78 b(for)18 b(j)h(:=)g(1)g(to)g(N)h(await)d(\(b[j])h(=)h(false\);)-75 1607 y(13)78 b(if)19 b(y)g(<>)g(i)38 b(then)-75 1649 y(14)156 b(await)18 b(\(y)h (=)g(0\);)-75 1690 y(15)156 b(goto)18 b(start;)-75 1732 y(16)78 b(end;)-75 1774 y(17)38 b(end;)-75 1815 y(18)-75 1857 y(19)g(CRITICAL)17 b(SECTION)-75 1898 y(20)-75 1940 y(21)38 b(y)20 b(:=)f(0;)-75 1981 y(22)38 b(b[i])19 b(:=)f (false;)-66 2110 y fr(Figure)c(1:)k(Lamport's)c(fast)f(m)n(utual)g(exclusion) h(algorithm.)-33 2216 y(Although)d(reservation-based)g(algorithms)f(such)i (as)g(Lam-)-75 2261 y(p)q(ort's)i(are)h(correct)h(in)e(principle,)f(they)i (are)g(in)e(practice)j(un-)-75 2306 y(wieldy)l(,)e(ha)n(ving)f(storage)i(requ\ iremen)o(ts)f(that)g(are)h fj(O)q fr(\()p fj(n)9 b fi(\002)h fj(l)q fr(\),) -75 2352 y(where)16 b fj(n)f fr(is)g(the)h(maxim)-5 b(um)13 b(n)o(um)n(b)q (er)j(of)e(threads)i(that)f(ma)n(y)-75 2397 y(b)q(e)h(sim)m(ultaneously)f(act\ iv)o(e,)g(and)g fj(l)h fr(is)f(the)h(maxim)-5 b(um)14 b(n)o(um-)-75 2442 y (b)q(er)h(of)e(synchronization)g(ob)r(jects.)-33 2489 y(The)h(space)g(require\ men)o(t)g(can)f(b)r(e)h(reduced)h(to)e fj(O)q fr(\()p fj(n)p fr(\))h(with)-75 2534 y(a)g(single)f(\\meta-atomi)o(c)f(ob)r(ject")i(whic)o(h)g(is)f(used)i (to)f(con)o(trol)-75 2580 y(access)22 b(to)e(all)f(\\regular)h(atomic)e(ob)r (jects.")38 b(In)20 b(this)g(case,)-75 2625 y(the)g(critical)f(section)h(at)g (line)e(19)h(in)g(Figure)h(1)f(b)q(ecomes)h(a)1013 -8 y fg(function)c(Meta-At\ omi)o(c-)o(Tes)o(t-)o(And)o(-Se)o(t\()o(var)g(p:)j(integer\))1169 34 y(:integ\ er;)1013 76 y(var)f(result:)f(integer;)1013 117 y(begin)1071 159 y([)j(lines) d(1-18)h(from)g(Lamport's)f(algorith)o(m)g(])1071 200 y(if)i(\(p)g(=)g(0\))39 b(then)1130 242 y(result)17 b(:=)i(0;)1130 283 y(p)g(=)h(1;)1071 325 y(else) 1130 366 y(result)d(:=)i(1;)1071 408 y(end;)1071 450 y([)h(lines)d(21-22)h (from)g(Lamport's)e(algorithm)g(])1052 491 y(return)h(result;)1013 533 y(end) h(Meta-Atom)o(ic-)o(Tes)o(t-)o(And)o(-S)o(et;)1013 616 y(procedur)o(e)f(Atomi\ cCle)o(ar)o(\(va)o(r)f(p:)j(integer\))1013 657 y(begin)1071 699 y(p)h(:=)e (0;)1013 740 y(end)g(AtomicCle)o(ar;)1013 869 y fr(Figure)12 b(2:)18 b(Bundle\ d)13 b fm(T)m(est-A)n(nd-Set)g fr(using)g(Lamport's)f(algo-)1013 914 y(rithm.) 1013 1052 y(co)q(de)19 b(sequence)i(to)e(access)h(the)f(\\regular)g(atomic)e (ob)r(ject.")1013 1098 y(F)l(or)e(example,)f(w)n(e)i(can)f(bundle)g(the)h(res\ erv)o(ation)f(algorithm)1013 1143 y(inside)e(a)h fm(T)l(est-A)o(nd-Set)g fr (pro)r(cedure)h(\(see)g(Figure)f(2\).)1054 1201 y(Ev)o(en)d(though)g(bundling) f(reduces)j(the)e(space)h(requiremen)o(t)1013 1247 y(for)k(an)g(atomic)e fm (T)m(est-A)n(nd-Set)j fr(v)n(ariable)f(to)g(one)h(bit)f(\(space)1013 1292 y (for)h(the)h(meta)f(v)m(ariables)h fj(x)p fr(,)f fj(y)r fr(,)h(and)g fj(b)f fr (can)h(b)q(e)g(counted)g(as)1013 1337 y(constan)o(t)d(system)g(o)o(v)o(erhead\ \),)h(it)f(increases)i(the)f(n)o(um)m(b)r(er)g(of)1013 1383 y(memory)i(access\ es)23 b(to)e(en)o(ter)g(and)g(exit)g(a)f(critical)g(section)1013 1428 y(to)15 b(at)g(least)h(three)h(loads)e(and)h(sev)o(en)g(stores.)25 b(Additionally)-6 b (,)1013 1473 y(bundling)20 b(serializes)h(all)f(atomic)g(op)q(erations,)i(eve\ n)f(those)1013 1519 y(for)12 b(unrelated)i(sync)o(hronization)e(ob)s(jects.) 18 b(On)13 b(a)g(unipro)q(ces-)1013 1564 y(sor,)h(for)g(example,)g(a)g(thread) h(preempted)g(during)g(the)g(func-)1013 1609 y(tion)e fh(Meta-Atomic-Test-An) o(d-Se)o(t)f fr(w)n(ould)i(preven)o(t)g(other)1013 1655 y(threads)g(from)f (executing)h fm(any)h fr(atomic)d(op)q(eration.)1013 1835 y fk(2.3)55 b(Kerne\ l)17 b(em)m(ulation)1013 1932 y fr(Memory-in)m(terlo)q(c)o(k)o(ed)e(instructi\ ons)h(and)e(soft)o(w)o(are)h(reserv)o(a-)1013 1977 y(tion)h(proto)q(cols)h (w)o(ork)f(on)h(b)q(oth)g(unipro)q(cessors)i(and)d(m)n(ulti-)1013 2023 y(pro) q(cessors.)i(A)11 b(strictly)f(unipro)q(cessor)i(solution)d(has)h(the)h(k)n (er-)1013 2068 y(nel)16 b(exp)q(ort)h(its)f(abilit)n(y)g(to)g(p)r(erform)f (atomic)f(op)q(erations)j(to)1013 2113 y(applications)h(b)o(y)h(means)g(of)g (a)g(system)g(call)g(that)g(do)q(es)h(an)1013 2159 y(atomic)11 b(read-modify-\ write)i(on)g(a)h(memory)d(location)i(in)g(the)1013 2204 y(caller's)k(address) i(space.)32 b(In)18 b(the)g(k)o(ernel,)h(pro)q(cessor)h(in)n(ter-)1013 2249 y (rupts)d(are)f(disabled)g(during)g(the)h(execution)g(of)f(the)h(atomic)1013 2295 y(operation.)1054 2353 y(Although)d(k)o(ernel)h(em)n(ulation)e(requires) i(no)f(sp)r(ecial)g(hard-)1013 2398 y(w)n(are,)23 b(its)d(runtime)f(cost)i (is)g(high.)37 b(The)22 b(k)n(ernel)g(m)m(ust)f(b)r(e)1013 2444 y(in)n(v)o (ok)n(ed)c(on)f(ev)o(ery)h(sync)o(hronization)f(op)q(eration,)g(requiring) 1013 2489 y(that)e(a)g(trap)h(b)q(e)g(\014elded)h(and)e(dispatc)o(hed,)h(stat\ e)g(sa)o(v)o(ed)g(and)1013 2534 y(restored,)d(and)f(argumen)n(ts)g(chec)o(k)o (ed.)18 b(On)11 b(the)h(MIPS)f(R3000,)1013 2580 y(for)i(example,)f(building)g (a)h fm(T)m(est-A)n(nd-Set)i fr(with)e(k)o(ernel)h(em)n(u-)1013 2625 y(lation) e(tak)o(es)i(ab)q(out)g(100)f(instructions.)p eop %%Page: 5 4 bop -75 -8 a fg(function)17 b(Test-And)o(-Se)o(t\(v)o(ar)f(p:)j(integer\):)d (integer;)-16 34 y(var)i(result:)f(integer;)-16 76 y(begin)-75 117 y(1)78 b (result)17 b(:=)i(1;)-75 159 y(2)78 b(BEGIN)18 b(RESTARTAB)o(LE)e(ATOMIC)h (SEQUENCE)-75 200 y(3)78 b(if)19 b(p)g(=)g(1)h(then)-75 242 y(4)137 b(result) 17 b(:=)i(0;)-75 283 y(5)78 b(else)-75 325 y(6)137 b(p)19 b(:=)g(1;)-75 366 y (7)78 b(end;)-75 408 y(8)g(END)19 b(RESTARTA)o(BLE)d(ATOMIC)h(SEQUENCE)-75 450 y(9)78 b(return)17 b(result;)-16 491 y(end)h(Test-And-S)o(et;)-75 619 y fr (Figure)23 b(3:)37 b(Generic)24 b fm(T)m(est-A)n(nd-Set)g fr(using)f(a)g(rest\ artable)-75 665 y(atomic)12 b(sequence.)-75 868 y fk(2.4)56 b(Restartable)17 b (atomic)g(sequences)-75 1013 y fr(The)c(three)h(mec)o(hanisms)d(describ)s(ed) i(so)g(far)f(are)h(p)r(essimistic.)-75 1058 y(A)i(memory-i)o(n)l(terlo)r(c)o (k)o(ed)g(instruction)f(implicitly)e(dela)n(ys)j(in-)-75 1103 y(terrupts)25 b (un)o(til)e(the)h(instruction)g(completes;)j(a)c(soft)o(w)o(are)-75 1149 y (reserv)o(ation)g(algorithm)d(explicitly)i(guards)h(against)f(arbi-)-75 1194 y (trary)16 b(in)o(terlea)o(ving;)g(k)n(ernel)h(em)n(ulation)d(explicitly)h(dis\ ables)-75 1239 y(in)n(terrupts)h(during)e(op)q(erations)h(that)f(m)n(ust)h (execute)h(atomi-)-75 1285 y(cally)l(.)-33 1369 y(On)e(a)g(unipro)q(cessor,)i (an)e(atomic)e(read-modify-write)i(op-)-75 1414 y(eration)f(can)h(b)q(e)g(p)q (erformed)f(optimistically)-7 b(.)18 b(Instead)c(of)f(us-)-75 1459 y(ing)d (a)h(mec)n(hanism)e(that)i(guards)g(against)f(in)o(terrupts,)i(w)o(e)f(can) -75 1505 y(instead)f(recognize)i(when)e(an)g(in)o(terrupt)h(o)q(ccurs)h(and)e (recov)n(er.)-75 1550 y(F)m(or)k(an)o(y)g(read-modify-write)g(sequence,)j(the) e(recov)n(ery)h(pro-)-75 1595 y(cess)21 b(is)d(straigh)o(tforw)o(ard:)28 b fm (r)n(estart)19 b(the)g(se)n(quenc)o(e)p fr(.)33 b(In)19 b(this)-75 1641 y(w)o (a)n(y)m(,)g(when)h(the)f(sequence)i(ev)o(entually)c(completes,)j(it)e(will) -75 1686 y(ha)o(v)n(e)d(completed)e(without)h(in)n(terruption,)g(i.e.,)e(atom\ ically)-6 b(.)-33 1770 y(An)16 b(atomic)f fm(T)l(est-A)o(nd-Set)i fr(operatio\ n)g(is)f(sho)o(wn)g(in)g(Fig-)-75 1816 y(ure)d(3.)k(As)c(long)e(as)i(statemen) o(ts)f(3)g(through)h(7)f(execute)i(with-)-75 1861 y(out)d(in)n(terruption)h (on)f(a)g(unipro)q(cessor,)i(this)e(co)q(de)h(will)d(atom-)-75 1906 y(ically) j(read)h(and)g(write)g(the)h(v)m(ariable)f fj(p)p fr(.)k(If)c(an)g(in)n(terru\ pt)h(o)q(c-)-75 1952 y(curs)g(that)g(w)n(ould)f(allo)m(w)h(another)f(thread)h (to)f(p)q(ossibly)g(mod-)-75 1997 y(ify)19 b(the)i(v)m(ariable)e fj(p)p fr (,)i(then)g(the)g(in)n(terrupted)h(thread)e(m)n(ust)-75 2042 y(resume)d(execu\ tion)h(at)e(line)h(3)g(when)g(it)f(is)h(next)h(sc)o(heduled.)-75 2088 y(The) 12 b(corresp)s(onding)e(clear)i(op)q(eration)g(can)f(store)i(a)e(zero)h(in)o (to)-75 2133 y fj(p)e fr(as)g(long)g(as)g(single-w)n(ord)h(memory)c(accesses) 13 b(execute)f(atom-)-75 2178 y(ically)-5 b(.)-33 2262 y(Restartable)14 b(ato\ mic)f(sequences)j(are)f(attractiv)o(e)g(b)q(ecause)-75 2308 y(they)d(do)g(not) f(not)h(require)g(hardw)o(are)h(supp)q(ort,)f(ha)o(v)n(e)h(a)e(short)-75 2353 y(co)q(de)h(path)g(with)f(one)g(load)g(and)g(one)h(store)g(p)q(er)h(atomic)c (read-)-75 2398 y(modify-write)i(\(in)g(the)i(common)c(case)j(of)g(no)f(in)o (terruptions\),)-75 2444 y(and)17 b(do)f(not)h(in)n(v)o(olv)n(e)g(the)g(k)o (ernel)g(on)g(ev)o(ery)g(atomic)e(op)q(era-)-75 2489 y(tion.)i(Only)c(when)h (an)f(atomic)e(instruction)i(sequence)j(migh)l(t)-75 2534 y(not)c(ha)n(v)o (e)h(executed)g(atomically)c(is)j(it)g(necessary)i(to)d(p)r(erform)-75 2580 y (a)j(recov)n(ery)h(action)f(to)g(ensure)i(atomicit)m(y)l(.)j(In)c(the)g(next) f(sec-)-75 2625 y(tion)f(w)o(e)h(describ)s(e)g(t)o(w)o(o)f(recov)o(ery)h(stra\ tegies.)1013 -33 y fn(3)69 b(Implemen)n(ti)o(ng)143 b(restartable)1116 35 y (atomic)21 b(sequences)1013 145 y fr(Restartable)12 b(atomic)e(sequences)15 b (require)e(k)n(ernel)g(supp)r(ort)f(to)1013 191 y(ensure)17 b(that)f(a)g(susp) r(ended)h(thread)f(is)g(resumed)g(at)g(the)g(b)r(e-)1013 236 y(ginning)j(of)g (the)j(sequence.)39 b(This)21 b(section)g(describ)r(es)g(t)o(w)o(o)1013 281 y (strategies)d(for)f(implemen)l(ting)g(that)g(k)o(ernel)h(supp)q(ort.)29 b(The) 1013 327 y(\014rst)c(strategy)m(,)h(used)f(b)o(y)f(the)h(Mac)o(h)f(3.0)g(k)n (ernel,)j(places)1013 372 y(a)22 b(restartable)j(atomic)c(sequence)k(at)e(a)g (designated)h(co)q(de)1013 417 y(range)c(within)g(a)g(program.)36 b(The)21 b (second)g(strategy)n(,)g(used)1013 463 y(b)n(y)e(the)g(T)m(aos)g(k)n(ernel,)i (constructs)f(restartable)g(atomic)d(se-)1013 508 y(quences)f(out)f(of)f(uniq\ ue)h(co)r(de)g(fragmen)n(ts)g(against)f(whic)o(h)h(a)1013 553 y(susp)r(ended) h(thread's)g(current)g(instruction)f(stream)g(is)g(com-)1013 599 y(pared.)22 b (Both)15 b(strategies)i(ha)n(v)o(e)f(b)q(een)g(implemen)l(ted)g(in)f(v)n(er-) 1013 644 y(sions)j(of)h(the)g(op)q(erating)g(systems)g(running)g(on)f(the)i (MIPS)1013 689 y(R3000-based)12 b(DECstation)i(5000/200.)1013 870 y fk(3.1)55 b(Explicit)17 b(registration)g(in)h(Mac)o(h)1013 967 y fr(The)25 b(Mac)o(h)f (op)q(erating)h(system)g(implem)o(en)m(ts)g(a)f(strategy)1013 1012 y(based)16 b(on)g(explicit)g(registration.)24 b(The)17 b(k)o(ernel)f(k)o(eeps)i(trac)o (k)1013 1057 y(of)13 b(eac)o(h)h(address)i(space's)f(restartable)g(atomic)d (sequence.)20 b(If)1013 1103 y(a)e(thread)i(is)e(susp)r(ended)i(within)e(that) h(sequence,)j(it)d(is)f(re-)1013 1148 y(sumed)e(at)g(the)i(b)q(eginning.)26 b (An)17 b(application)e(registers)j(the)1013 1193 y(starting)g(address)h(and)f (length)h(of)e(the)i(sequence)h(with)e(the)1013 1239 y(k)n(ernel.)27 b(The)18 b(registration)e(is)h(done)g(automatically)c(during)1013 1284 y(program)d(ini\ tialization)g(b)o(y)i(C-Threads)h([Coop)q(er)g(&)g(Dra)n(v)o(es)1013 1329 y (88],)f(Mac)o(h's)i(thread)g(managemen)m(t)g(pac)o(k)m(age.)1054 1388 y(An)j (address)h(space)g(ma)m(y)f(register)h(only)e(one)h(restartable)1013 1433 y (atomic)d(sequence)19 b(at)d(a)h(time.)25 b(This)16 b(restriction)h(simpli\ \014es)1013 1479 y(the)e(k)o(ernel's)h(task)f(of)f(determining)g(if)g(a)h(sus\ p)r(ended)h(thread)1013 1524 y(w)n(as)21 b(executing)h(within)e(a)h(restartab\ le)h(sequence.)41 b(When)1013 1569 y(the)21 b(thread)h(managemen)m(t)f(system) g(attempts)g(to)g(register)1013 1615 y(a)15 b(restartable)i(atomic)d(sequence) k(with)e(a)g(k)o(ernel)g(that)g(do)q(es)1013 1660 y(not)h(supp)r(ort)g(such)g (sequences,)k(the)d(registration)f(fails.)28 b(In)1013 1705 y(resp)r(onse)20 b (to)g(the)h(failure,)f(the)g(thread)h(managemen)l(t)g(sys-)1013 1751 y(tem)e (o)o(v)n(erwrites)j(the)f(restartable)h(atomic)d(sequence)j(with)1013 1796 y (co)q(de)d(that)f(uses)h(a)f(conv)n(entional)f(mec)n(hanism.)30 b(Ov)o(erwrit\ -)1013 1841 y(ing)20 b(ensures)i(binary)f(p)q(ortabilit)m(y)g(b)q(etw)n(een)h (unipro)q(cessors)1013 1887 y(and)i(m)m(ultipro)q(cessors,)29 b(and)c(binary) f(compatibilit)l(y)g(with)1013 1932 y(older)19 b(k)o(ernels)i(that)e(do)h(not) f(supp)r(ort)h(restartable)h(atomic)1013 1977 y(sequences.)1054 2036 y(A)i (registered)h fm(T)m(est-A)n(nd-Set)g fr(function)e(can)i(b)q(e)f(imple-)1013 2081 y(men)m(ted)f(with)f(a)g(single)f(four-w)o(ord)h(\(and)g(four)f(cycle\)) i(se-)1013 2126 y(quence)17 b(on)e(a)h(load/store)g(RISC)f(arc)o(hitecture.) 26 b(F)m(or)15 b(exam-)1013 2172 y(ple,)21 b(the)h(assem)n(bly)e(co)r(de)h (for)f(this)h(function)g(on)f(a)h(MIPS)1013 2217 y(R3000)14 b(is)i(sho)o(wn)g (in)g(Figure)g(4.)25 b(Line)16 b(1)g(loads)g(the)g(curren)q(t)1013 2262 y(v)m (alue)i(of)f(the)h fm(T)m(est-A)n(nd-Set)g fr(lo)q(cation,)g(passed)g(in)g (register)1013 2308 y fh(a0)p fr(,)f(in)n(to)g(the)h(return)g(v)n(alue)f(regi\ ster,)i fh(v0)p fr(.)27 b(Line)18 b(2)f(loads)f(a)1013 2353 y(temporary)j(reg\ ister)i(with)e(the)h(v)n(alue)f(1.)35 b(Line)19 b(3)g(returns)1013 2398 y(con) o(trol)e(bac)o(k)h(to)g(the)g(caller.)30 b(Line)18 b(4,)g(whic)o(h)g(executes) i(in)1013 2444 y(the)e(branc)o(h)g(dela)n(y)g(slot)f(follo)m(wing)g(the)h(ret\ urn,)h(stores)g(a)e(1)1013 2489 y(in)n(to)k(the)h fm(T)m(est-A)n(nd-Set)g fr (location.)41 b(Lines)21 b(1{4)g(form)e(the)1013 2534 y(restartable)14 b(atom\ ic)d(sequence:)20 b(when)14 b(the)f(store)h fm(\014nal)s(ly)f fr(o)q(c-)1013 2580 y(curs)21 b(at)f(the)g(end)h(of)f(line)f(4,)i(no)f(other)h(thread)f(will) f(ha)o(v)o(e)1013 2625 y(executed)c(since)g(the)g(thread's)f(most)f(recent)h (load)f(at)h(line)f(1.)p eop %%Page: 6 5 bop -75 -11 a fg(#)19 b(Test-And-S)o(et)d(procedure.)-75 31 y(Test-And-S)o (et)o(:)-75 72 y(1)58 b(lw)39 b(v0,)18 b(\(a0\))38 b(#v0)19 b(=)g(contents)d (of)j(a0)-75 114 y(2)58 b(li)39 b(t0,)18 b(1)98 b(#temporary)16 b(t0)j(gets)f (1)-75 156 y(3)58 b(j)h(ra)156 b(#return)17 b(to)i(caller,)e(result)g(in)i (v0)-75 197 y(4)58 b(sw)39 b(t0,)18 b(\(a0\))38 b(#store)17 b(1)j(in)e(Test-A\ nd-Se)o(t)278 239 y(#location)-75 367 y fr(Figure)10 b(4:)16 b(Restartable)10 b fm(T)m(est-A)n(nd-Set)h fr(pro)q(cedure)h(using)d(ex-)-75 412 y(plicit)k (registration)h(in)f(Mac)o(h)h(3.0.)-75 535 y ff(Costs)h(of)h(explicit)d(regi\ stration)-75 611 y fr(There)20 b(are)g(t)o(w)o(o)f(run)o(time)f(costs)j(asso) q(ciated)f(with)f(explicit)-75 656 y(registration.)31 b(Because)20 b(the)e (k)o(ernel)h(iden)o(ti\014es)f(restartable)-75 701 y(atomic)i(sequences)k(b)o (y)e(a)g(single)f(PC)h(range)g(p)r(er)g(address)-75 747 y(space,)c(they)f(can\ not)g(b)q(e)g(inlined.)26 b(The)17 b(inabilit)m(y)g(to)f(inline)-75 792 y(sli\ gh)n(tly)11 b(increases)i(the)f(o)n(v)o(erhead)g(of)f(atomic)e(op)q(erations) j(b)q(e-)-75 837 y(cause)j(of)e(the)i(cost)f(of)g(subroutine)g(link)m(age.) -33 884 y(The)g(second)i(cost)f(comes)f(from)f(ha)n(ving)h(to)g(check)g(the)h (re-)-75 930 y(turn)20 b(PC)f(whenever)h(a)f(thread)h(is)f(susp)r(ended.)35 b (Although)-75 975 y(this)12 b(test)g(adds)g(a)g(few)f(tens)i(of)e(cycles)i (to)e(the)i(k)n(ernel's)g(thread)-75 1020 y(susp)r(ension)i(path)g(\(whic)o (h)g(is)g(already)g(sev)o(eral)g(h)o(undred)h(cy-)-75 1066 y(cles)e(long\),)f (thread)h(susp)r(ensions)g(o)q(ccur)h(far)e(less)h(often)f(than)-75 1111 y (atomic)19 b(op)q(erations,)j(making)d(the)i(additional)e(scheduling)-75 1156 y(o)o(v)n(erhead)c(w)o(orth)o(while.)-75 1276 y fk(3.2)56 b(Designated)17 b (sequences)h(in)g(T)-5 b(aos)-75 1351 y fr(T)m(aos)11 b(uses)j(designated)e (co)r(de)g(sequences)j(to)d(recognize)h(when)-75 1396 y(a)23 b(thread)i(has)f (b)q(een)h(susp)r(ended)f(within)f(an)h(atomic)e(se-)-75 1442 y(quence.)35 b (The)19 b(k)o(ernel)g(compares)g(the)h(instruction)f(stream)-75 1487 y(of)d (a)h(susp)r(ended)h(thread)g(against)e(a)h(designated)h(sequence.)-75 1532 y (The)13 b(comparison)e(allo)m(ws)i(restartable)g(atomic)e(sequences)k(to)-75 1578 y(o)q(ccur)22 b(an)n(ywhere)g(in)e(a)g(program,)g(enabling)g(inlining)f (and)-75 1623 y(eliminating)7 b(the)j(branch)f(o)o(v)o(erhead)h(of)g(explicit) f(registration.)-33 1670 y(The)14 b(k)o(ernel's)h(comparison)d(m)n(ust)i(reco\ gnize)h(every)f(in)o(ter-)-75 1715 y(rupted)20 b(sequence)g(and)f(reject)h (an)n(y)f(other)g(similar)d(looking)-75 1760 y(sequence)j(since)f(mistak)m (enly)f(c)o(hanging)f(the)i(PC)f(in)g(such)g(a)-75 1806 y(situation)f(could)h (cause)i(co)q(de)e(to)g(malfunction.)26 b(T)l(aos)17 b(uses)-75 1851 y(a)g (t)o(w)n(o-stage)g(chec)o(k)g(to)g(unam)m(biguously)f(recognize)i(atomic)-75 1896 y(sequences.)-33 1943 y(The)f(\014rst)h(stage)g(is)f(a)g(fast)g(test)h (whic)o(h)f(rejects)i(most)d(in-)-75 1989 y(terrupted)e(co)r(de)f(sequences)i (that)d(are)h(not)f(restartable.)19 b(The)-75 2034 y(op)q(co)q(de)e(of)g(the) g(susp)r(ended)h(instruction)f(is)f(used)i(as)f(an)f(in-)-75 2079 y(dex)c(in) o(to)g(a)g(hash)g(table)g(con)o(taining)f(instructions)i(eligible)e(to)-75 2125 y(app)q(ear)j(in)f(a)g(restartable)h(atomic)e(sequence.)20 b(If)13 b(the) h(op)q(co)q(de)-75 2170 y(matc)n(hes)e(the)g(con)o(ten)o(ts)g(of)f(the)h(inde\ xed)g(en)o(try)m(,)f(the)h(test)h(pro-)-75 2215 y(ceeds)i(to)e(the)h(second)g (stage.)19 b(The)13 b(\014rst)h(chec)o(k)g(is)f(quite)g(fast,)-75 2261 y(y)o (et)k(succeeds)j(in)d(rejecting)h(a)f(large)g(majorit)n(y)g(of)g(the)h(non-) -75 2306 y(atomic)9 b(cases)j(and)e(none)h(of)f(the)h(atomic)d(ones.)18 b(The) 11 b(few)f(that)-75 2351 y(pass)i(this)g(check,)f(comprising)g(all)f(of)i(the) g(susp)r(ended)h(atomic)-75 2397 y(sequences,)18 b(plus)e(a)f(m)m(uch)g(large\ r)h(n)o(um)m(b)q(er)g(of)f(false)h(alarms,)-75 2442 y(mo)m(v)o(e)e(on)g(to)g (the)g(second)h(stage)f(of)g(the)g(c)o(heck.)-33 2489 y(The)i(second)h(stage) g(uses)g(another)f(table,)g(again)f(indexed)-75 2534 y(b)o(y)i(op)q(co)q(de,) g(to)g(determine)g(the)g(exp)r(ected)h(o\013set)g(from)d(the)-75 2580 y(susp) r(ended)23 b(instruction)f(to)f(a)h(\\landmark")d(no-op.)41 b(The)-75 2625 y (landmark)15 b(no-op)h(is)h(nev)o(er)h(emitted)f(b)n(y)g(the)h(compiler)e(un-) 1013 -46 y(der)g(normal)d(circumstances,)j(but)g(is)f(presen)q(t)g(within)g (ev)o(ery)1013 -1 y(restartable)h(atomic)d(sequence.)25 b(On)15 b(the)h(R3000\ ,)e(the)i(land-)1013 44 y(mark)h(no-op)h(is)h(a)g(non-destructive)g(register) i(mo)m(v)o(e)e(whic)o(h)1013 90 y(\014lls)14 b(an)h(otherwise)h(useless)h(bra\ nch)e(dela)n(y)g(slot.)22 b(If)15 b(the)h(sec-)1013 135 y(ond)d(stage)h(\014n\ ds)f(the)h(landmark)e(in)h(the)h(exp)q(ected)h(p)q(osition,)1013 180 y(it)k (recognizes)j(the)e(sequence)j(as)d(atomic)e(and)i(restarts)i(it.)1013 226 y (Otherwise,)14 b(the)h(sequence)h(is)e(rejected)h(as)f(a)g(false)g(alarm.) 1054 271 y(The)21 b(designated)h(sequence)h(for)e(acquiring)f(a)h(m)n(utex)g (is)1013 316 y(sho)o(wn)16 b(in)g(Figure)g(5.)25 b(The)17 b(sequence)h(is)e (optimistic)f(in)g(t)o(w)o(o)1013 362 y(distinct)g(senses:)22 b(it)14 b(assum\ es)h(b)q(oth)g(that)g(it)g(will)e(not)i(b)q(e)h(in-)1013 407 y(terrupted,)22 b (and)e(that)g(it)g(will)e(\014nd)i(the)g(m)n(utex)g(unlo)q(c)o(k)o(ed.)1013 452 y(Both)15 b(assumptions)g(model)g(the)h(frequent)g(case,)g(but)g(either) 1013 498 y(or)k(b)q(oth)g(can)h(fail)d(indep)r(endently)l(.)37 b(The)21 b(seq\ uence)h(is)e(es-)1013 543 y(sen)o(tially)c(a)g fm(T)m(est-A)n(nd-Set)i fr(of) e(an)h(entire)g(w)o(ord,)g(where)h(the)1013 588 y(unloc)o(k)o(ed)f(v)m(alue)f (of)f(the)i(m)m(utex)g(is)f(0,)g(and)f(the)i(lock)o(ed-but-)1013 634 y(no-w)n (aiters)10 b(v)n(alue)g(is)g(0x80000000.)k(T)o(ypically)-5 b(,)10 b(the)h(seq\ uence)1013 679 y(\014nds)16 b(that)g(the)g(m)m(utex)h(has)f(the)g(former)f (v)m(alue)h(and)f(atomi-)1013 724 y(cally)8 b(sets)j(it)f(to)f(the)i(latter.) 16 b(The)11 b(infrequen)o(t)f(case)g(is)g(handled)1013 770 y(with)16 b(an)h (out-of-line)f(k)o(ernel)h(call)g(via)f fh(SlowAcquire)p fr(.)26 b(The)1013 815 y(sequence)14 b(for)f(m)m(utex)h(release)g(\()p fm(T)l(est-A)o(nd-Cle)n (ar)p fr(\))e(is)h(similar.)1013 937 y fg(1)38 b(lw)58 b(v0,)19 b(\(a0\))155 b (#get)18 b(value)g(of)h(mutex)1013 979 y(2)38 b(lui)g(t0,)19 b(8000H)135 b (#temporary)16 b(t0=0x80000)o(00)o(0)1013 1020 y(3)38 b(bne)g(v0,)19 b(SlowAc\ qui)o(re)d(#branch)h(if)i(not)f(common)g(case)1013 1062 y(4)38 b(no-op)312 b (#special)17 b(landmark)f(value)1013 1103 y(5)38 b(sw)58 b(t0,)19 b(\(a0\)) 155 b(#store)18 b(locked)f(value)1013 1232 y fr(Figure)d(5:)k(A)c(restartable) h(atomic)e(sequence)j(for)e(m)m(utex)h(ac-)1013 1277 y(quisition)d(using)i (an)g(inlined)f(designated)h(sequence.)1013 1420 y ff(Costs)h(of)g(designated) e(sequences)1013 1492 y fr(Designated)i(sequences)k(ha)n(v)o(e)d(several)f (costs.)25 b(There)17 b(is)e(the)1013 1537 y(measurable)c(cost)i(of)e(the)i (t)o(w)n(o-stage)g(c)o(heck)f(on)f(every)h(thread)1013 1582 y(switc)o(h.)30 b (The)18 b(check)f(is)h(curren)q(tly)f(implemen)l(ted)i(in)e(Mo)q(d-)1013 1628 y(ula2+,)e(the)i(language)f(in)g(whic)n(h)h(the)g(op)q(erating)f(system)g(is) 1013 1673 y(written)c([Ro)m(vner)g(et)g(al.)17 b(85].)f(As)c(with)f(Mac)o(h's) h(explicit)f(reg-)1013 1718 y(istration,)k(the)i(chec)o(k)f(adds)h(a)f(few)g (tens)h(of)f(instructions)h(to)1013 1764 y(the)c(k)o(ernel's)h(con)o(text)g (switc)o(h)f(path)g(\(counting)f(instructions)1013 1809 y(in)g(the)h(generate\ d)h(co)q(de)g(sho)o(ws)f(that)f(the)i(c)o(heck)e(adds)h(ab)q(out)1013 1854 y (2)g fj(\026)p fr(secs)j(on)d(a)h(MIPS)g(R3000)e(in)i(the)g(common)d(case\).) 1054 1900 y(Unlik)n(e)16 b(explicit)g(registration,)f(whic)o(h)h(uses)h(only) e(one)h(se-)1013 1945 y(quence)11 b(that)f(can)g(b)r(e)g(o)o(v)n(erwritten)i (at)e(run)o(time)f(if)g(restartable)1013 1990 y(atomic)h(sequences)15 b(are)e (not)g(supp)r(orted)g(on)f(a)h(giv)n(en)g(system,)1013 2036 y(designated)g (sequences)j(are)d(not)g(p)q(ortable)g(b)q(etw)o(een)g(unipro-)1013 2081 y (cessors)h(and)f(m)m(ultipro)q(cessors.)19 b(The)13 b(compiler)f(m)m(ust)h (gener-)1013 2126 y(ate)h(a)f(di\013erent)h(co)q(de)h(sequence)h(for)d(each.) 1054 2172 y(More)24 b(generally)l(,)h(the)e(use)h(of)e(a)h(designated)h(seque\ nce)1013 2217 y(requires)e(a)g(strong)f(alliance)g(b)q(etw)n(een)i(the)f(comp\ iler)e(and)1013 2262 y(the)g(op)q(erating)f(system,)h(since)h(c)o(hanges)f (in)f(the)h(w)o(a)o(y)f(that)1013 2308 y(one)13 b(handles)g(atomic)e(op)q(era\ tions)i(m)n(ust)g(b)q(e)h(re\015ected)h(in)d(the)1013 2353 y(other.)25 b(The) 17 b(global)d(design)j(prop)q(erties)g(of)f(the)h(T)l(aos)f(op)q(er-)1013 2398 y(ating)e(system)h(mak)m(e)g(this)g(link)m(age)g(feasible,)g(ho)n(w)o(ev)o (er.)23 b(The)1013 2444 y(crucial)c(prop)q(erty)g(of)g(T)l(aos)g(is)h(that)f (b)q(oth)g(the)h(k)o(ernel)g(and)1013 2489 y(its)13 b(m)m(ultithreaded)h(clie\ n)o(ts)g(are)g(written)g(in)f(Mo)q(dula-2+.)k(In)1013 2534 y(this)11 b(con)o (text,)i(the)f(k)o(ernel)g(and)f(the)i(compiler)d(can)i(co)q(op)q(erate)1013 2580 y(closely)19 b(to)g(supp)r(ort)g(fast)g(m)n(utual)g(exclusion)g(using)g (desig-)1013 2625 y(nated)10 b(inlined)f(sequences.)20 b(In)10 b(con)o(trast,) h(for)f(Mac)o(h,)g(whic)o(h)g(is)p eop %%Page: 7 6 bop -75 -46 a fr(not)11 b(in)o(tended)h(to)g(b)q(e)g(used)g(with)f(an)o(y)g (one)h(language)f(and)g(an)o(y)-75 -1 y(one)f(compiler,)f(such)g(a)h(close)g (alliance)f(b)q(etw)o(een)h(the)h(compiler)-75 44 y(and)j(the)g(op)q(erating) g(system)g(k)n(ernel)h(is)f(not)g(feasible.)-75 187 y fn(4)69 b(Kernel)22 b (design)g(considerations)-75 278 y fr(Section)13 b(3)f(describ)s(ed)h(t)o(w)o (o)f(k)o(ernel)h(techniques)g(that)g(supp)q(ort)-75 323 y(fast)d(m)n(utual)g (exclusion)g(with)h(restartable)g(atomic)e(sequence.)-75 368 y(The)i(implicat\ ions)c(of)j(these)h(techniques)g(for)f(the)g(inner)h(w)o(ork-)-75 414 y(ings) j(of)h(the)g(k)o(ernel)g(dep)r(end)g(b)q(oth)g(on)g(the)g(exact)h(tec)o(hniqu\ e)-75 459 y(c)o(hosen)h(\(explicit)f(registration,)h(or)f(designated)h(sequen\ ces\))-75 504 y(and)11 b(on)g(the)g(design)g(details)g(of)g(the)g(sp)r(eci\ \014c)h(k)o(ernel)f(in)o(v)n(olv)n(ed.)-75 550 y(In)j(this)g(section)g(w)o (e)h(discuss)g(some)e(of)g(these)i(implications.)-75 673 y fk(4.1)56 b(Placem\ en)l(t)19 b(of)f(the)h(PC)g(c)n(hec)n(k)-75 749 y fr(The)f(most)f(ob)o(vious) g(question)h(ab)q(out)g(k)o(ernel)g(structure)i(is:)-75 794 y(when)c(should)f (the)i(k)n(ernel)f(check/adjust)f(the)h(PC)g(of)f(a)g(sus-)-75 840 y(p)q(ende\ d)c(thread?)17 b(The)11 b(t)o(w)n(o)f(p)q(oin)n(ts)g(at)g(whic)o(h)g(the)g (thread)g(can)-75 885 y(b)q(e)15 b(c)o(heck)o(ed)g(are)f(when)h(it)f(is)h(\ \014rst)g(susp)r(ended,)g(and)f(when)h(it)-75 930 y(is)e(ab)q(out)g(to)g(b)q (e)h(resumed.)k(One)c(could)f(consider)h(in)n(termedi-)-75 976 y(ate)i(p)q (oin)n(ts,)g(but)f(they)h(are)g(less)g(natural)f(than)g(either)h(p)q(oin)n (t)-75 1021 y(where)f(the)g(k)n(ernel)g(already)e(has)h(the)h(thread)g(in)e (hand.)-33 1069 y(When)j(using)g(designated)h(sequences,)i(c)o(hecking)c(the) i(PC)-75 1114 y(can)10 b(cause)h(a)e(page)h(fault)f(since)h(it)f(in)o(v)o(olv) n(es)h(reading)g(arbitrary)-75 1159 y(user)16 b(memory)-6 b(.)20 b(If)15 b (the)g(k)o(ernel)g(path)g(leading)f(to)g(susp)r(ension)-75 1205 y(is)h(restri\ cted)i(in)d(its)h(abilit)n(y)g(to)g(incur)g(additional)e(faults,)h(as)-75 1250 y(it)j(is)h(in)f(T)l(aos)h(and)f(man)n(y)g(other)h(systems,)h(early)e(c)o(hec\ king)-75 1295 y(of)e(the)i(PC)e(with)h(designated)g(sequences)j(can)d(b)q(e)g (problem-)-75 1341 y(atic.)26 b(Checking)15 b(the)j(PC)e(late)h(solv)n(es)h (this)e(problem,)g(since)-75 1386 y(there)i(are)f(generally)f(few)o(er)h(rest\ rictions)h(on)e(k)o(ernel)h(excep-)-75 1431 y(tions)d(when)g(coming)e(out)i (of)f(a)h(con)o(text)g(switch.)-33 1479 y(In)g(Mach,)g(the)i(PC)f(is)f(check) n(ed)i(when)f(the)h(thread)f(is)g(sus-)-75 1524 y(p)q(ended)e(rather)g(than)g (when)f(it)g(returns)i(to)e(user)h(lev)o(el.)k(Since)-75 1570 y(only)c(the)i (PC,)f(but)g(not)g(its)g(conten)o(ts,)g(are)h(insp)q(ected,)g(there)-75 1615 y (is)e(no)g(concern)i(ab)q(out)e(touching)f(user)j(memory)c(at)i(inopp)q(or-) -75 1660 y(tune)g(times.)k(The)c(c)o(heck)f(is)g(done)h(early)f(b)q(ecause)i (the)f(return)-75 1706 y(PC)d(and)f(reason)i(for)e(en)o(try)h(in)o(to)f(the)h (k)o(ernel)h(are)f(con)o(v)o(enien)o(tly)-75 1751 y(a)o(v)m(ailable)j(at)g (that)h(p)r(oin)n(t.)-75 1866 y ff(Detection)f(at)j(user)f(lev)n(el)-75 1943 y fr(Explicit)22 b(registration)h(and)f(designated)h(sequences)i(place)-75 1988 y(with)11 b(the)h(k)o(ernel)g(the)g(resp)r(onsibilit)m(y)g(for)f(detecting)h (and)f(cor-)-75 2033 y(recting)17 b(atomicit)m(y)g(violations.)25 b(An)17 b (alternativ)n(e)g(approac)o(h)-75 2079 y(places)k(that)g(resp)s(onsibilit)m (y)g(with)f(the)i(application)d(itself:)-75 2124 y(whenever)12 b(a)g(susp)r (ended)h(thread)g(is)f(resumed)g(b)o(y)g(the)g(k)o(ernel,)-75 2169 y(it)f(ret\ urns)h(to)f(a)g(\014xed)g(user-level)g(sequence)i(that)e(determines)-75 2215 y (if)f(the)h(thread)g(w)o(as)g(susp)r(ended)g(within)f(a)h(restartable)g(atomi\ c)-75 2260 y(sequence.)28 b(If)16 b(so,)h(the)g(user-level)f(recov)o(ery)h (co)q(de)g(branches)-75 2305 y(to)12 b(the)h(b)r(eginning)e(of)h(the)h(sequen\ ce,)i(otherwise)e(it)f(branches)-75 2351 y(to)i(the)g(susp)r(ended)h(instruct\ ion.)-33 2398 y(User-lev)o(el)h(detection)h(is)f(attractiv)o(e)g(b)q(ecause)i (the)e(k)o(ernel)-75 2444 y(pro)o(vides)e(only)f(the)h(mec)o(hanism)e(to)h (ensure)j(atomicit)m(y)l(.)i(The)-75 2489 y(p)q(olicy)13 b(lies)g(with)f(the) i(application.)i(Since)e(the)g(k)o(ernel)g(is)f(not)-75 2534 y(in)n(v)o(olv)n (ed)20 b(in)f(either)i(detection)f(or)g(correction,)h(those)g(pro-)-75 2580 y (cesses)d(can)f(b)q(e)f(made)f(as)h(ric)o(h)g(as)g(necessary)i(to)e(satisfy)g (the)-75 2625 y(atomicit)m(y)c(constraints)h(of)f fm(any)h fr(instruction)g (sequence,)i(suc)o(h)1013 -44 y(as)9 b(those)i(that)f(manipulate)d(w)o(ait-fr\ ee)j(data)f(structures)k([Her-)1013 1 y(lih)m(y)f(91],)e(as)h(w)o(ell)g(as)g (the)h(more)f(con)o(v)n(entional)f fm(T)l(est-A)o(nd-Set)p fr(.)1054 48 y(The) 23 b(user-level)g(approac)o(h)g(is)g(not)g(without)f(problems,)1013 93 y(ho)n (w)o(ev)o(er.)35 b(T)l(ransferring)20 b(\014rst)g(to)f(a)f(\014xed)i(instruct\ ion)f(se-)1013 138 y(quence,)13 b(and)f(then)h(to)g(the)g(susp)r(ended)g(inst\ ruction)g(in)n(v)o(olv)n(es)1013 184 y(more)j(complexit)m(y)h(and)g(o)o(v)n (erhead)h(than)g(the)f(simple)f(c)o(heck)1013 229 y(made)g(b)o(y)h(the)h(k)o (ernel)g(in)f(either)i(of)e(the)h(other)g(t)o(w)o(o)f(strate-)1013 274 y(gies\ .)31 b(There)19 b(is)f(a)g(lev)o(el)g(of)f(con)o(trol)h(indirection)g(requiri\ ng)1013 320 y(that)d(the)i(real)f(return)h(address)g(b)q(e)g(sa)o(v)n(ed)g (and)f(restored)h(on)1013 365 y(the)h(thread's)h(user-level)f(stack)g(at)g (each)g(susp)r(ension.)31 b(Be-)1013 410 y(cause)13 b(of)e(these)j(problems,) d(and)g(b)r(ecause)i(there)h(is)d(little)h(mo-)1013 456 y(tiv)m(ation)f(to)i (create)h(a)e(clean)h(p)q(olicy/mec)m(hanism)e(separation)1013 501 y(when)16 b (there)i(is)e(only)g(one)g(p)q(olicy)l(,)h(neither)g(T)l(aos)f(nor)h(Mac)o (h)1013 546 y(pro)n(vide)d(for)g(user-lev)o(el)g(detection.)1583 531 y fe(1) 1013 662 y fk(4.2)55 b(Mutual)19 b(exclusion)e(in)h(the)h(k)n(ernel)1013 735 y fr(The)12 b(k)n(ernel)h(is)f(itself)f(a)h(clien)n(t)g(of)g(thread)g(managemen) l(t)g(facil-)1013 781 y(ities)j(in)f(b)r(oth)h(Mac)o(h)g(and)g(T)m(aos.)21 b (It)16 b(is)f(tempting)e(to)i(regard)1013 826 y(the)g(k)o(ernel's)h(abilit)m (y)f(to)g(disable)f(in)o(terrupts)j(as)e(a)f(sweeping)1013 871 y(solution)f (to)h(the)h(m)m(utual)f(exclusion)g(problem)f(on)h(a)g(unipro-)1013 917 y(ces\ sor.)k(Mac)o(h)9 b(implicitly)e(adopts)i(this)h(approac)o(h)f(as)h(the)g(k)n (er-)1013 962 y(nel)g(is)g(non-preemptiv)n(e,)g(but)h(is)f(compiled)e(for)i (unipro)q(cessors)1013 1007 y(with)k(all)f(lo)n(w-lev)o(el)i(sync)o(hronizati\ on)f(op)q(erations)h(remo)n(v)o(ed.)1013 1053 y(The)e(T)l(aos)g(k)o(ernel,)g (ho)o(w)n(ever,)g(is)f(preemptiv)o(e,)h(and)f(uses)i(des-)1013 1098 y(ignated) j(sequences)k(just)e(as)f(applications)f(do.)31 b(There)20 b(are)1013 1143 y (t)n(w)o(o)15 b(reasons)h(for)f(this.)21 b(The)16 b(\014rst)f(is)g(a)g(minor) e(p)q(erformance)1013 1189 y(gain,)18 b(since)i(explicit)e(disabling)g(and)h (reenabling)g(of)f(in)n(ter-)1013 1234 y(rupts)13 b(w)o(ould)g(more)f(than)h (double)g(the)g(cost)h(of)f(sync)o(hroniza-)1013 1279 y(tion)j(op)q(erations.) 27 b(The)18 b(second)g(reason)f(is)g(a)f(desire)i(to)f(use)1013 1325 y(the)e (same)f(Mo)q(dula-2+)h(compiler)e(for)i(all)f(co)q(de,)i(whether)g(it)1013 1370 y(b)q(e)e(user)h(co)q(de)g(or)f(k)n(ernel)h(co)q(de.)1054 1416 y(The)e (use)g(of)f(restartable)i(atomic)d(sequences)k(in)d(b)q(oth)h(user)1013 1462 y (programs)g(and)i(the)h(k)o(ernel)g(raises)g(the)f(question)h(of)e(system) 1013 1507 y(structuring)j(due)g(to)f(p)q(otential)f(recursion.)27 b(Tw)o(o)16 b(ev)o(en)o(ts,)h(a)1013 1552 y(page)11 b(fault)h(or)g(a)f(thread)i(preemptio\ n,)e(can)h(trigger)h(a)e(thread)1013 1598 y(switc)o(h)k(in)f(the)i(middle)d (of)h(a)h(restartable)h(atomic)d(sequence.)1013 1643 y(Since)e(the)g(sequence) i(ma)m(y)e(b)q(e)h(in)e(either)i(user)g(or)e(k)o(ernel)i(co)q(de,)1013 1688 y (there)17 b(are)f(then)h(four)e(even)o(ts)h(that)h(m)m(ust)f(b)r(e)g(consider\ ed)h(in)1013 1734 y(the)i(ligh)n(t)g(of)g(recursion:)30 b(user)20 b(page)g (fault,)f(user)h(preemp-)1013 1779 y(tion,)f(k)o(ernel)h(page)g(fault,)f(and) h(k)n(ernel)g(preemption.)35 b(The)1013 1824 y(k)n(ernel)17 b(uses)g(m)m(utex\ es)g(while)e(handling)g(these)i(ev)o(en)o(ts,)g(so)e(it)1013 1870 y(is)f(impo\ rtan)o(t)h(to)g(ensure)h(that)f(recursion)i(do)q(es)e(not)g(lead)g(to)1013 1915 y(deadlock.)35 b(F)m(or)19 b(example,)h(a)f(thread)i(could)e(incur)h(a)g (user)1013 1960 y(page)14 b(fault,)g(b)r(e)h(preempted)h(while)e(handling)g (it)h(in)f(the)i(k)n(er-)1013 2006 y(nel,)g(and)g(up)q(on)g(resuming)f(from)f (the)j(preemption,)f(incur)g(a)1013 2051 y(second)h(page)g(fault)f(when)h(try\ ing)f(to)h(do)f(its)h(PC)g(c)o(heck.)26 b(If)1013 2096 y(the)17 b(preemption) g(happ)q(ened)h(while)f(holding)f(a)h(loc)o(k)h(in)e(the)1013 2142 y(virtual) f(memory)e(system,)j(the)g(recursion)i(could)d(cause)i(the)1013 2187 y(thread) d(to)g(deadlo)q(c)o(k)g(with)f(itself.)1054 2233 y(The)22 b(problem)e(here)i (is)f(that)g(careless)i(ordering)f(of)e(the)1013 2278 y(PC)c(c)o(heck)g(could) g(lead)g(to)g(m)m(utual)g(recursion)h(b)q(etw)n(een)g(the)1013 2324 y(thread) 12 b(scheduler)h(and)e(the)i(virtual)e(memory)e(system.)18 b(Suc)o(h)1013 2373 y 396 2 v 1059 2434 a fd(1)1076 2446 y fl(A)o(t)10 b(CMU,)h(w)o(e)f(rely)e (on)h(user-lev)o(el)e(restart)h(in)h(a)h(preemptiv)n(e)d(corou-)1013 2481 y (tine)i(pac)o(k)n(age)g(for)h(Unix)h(systems)e(that)h(is)h(used)f(in)g(teac)o (hing)f(an)h(under-)1013 2517 y(graduate)e(op)q(erating)h(systems)g(course.) 14 b(W)m(e)d(examine)e(the)h(in)o(terrupted)1013 2553 y(PC)i(within)f(the)f (Unix)i(signal)e(handler,)f(and)i(roll)g(it)g(bac)o(k)f(if)i(necessary)m(.) 1013 2589 y(With)g(this,)h(w)o(e)g(a)o(v)o(oid)f(disabling)f(and)h(enabling)f (Unix)h(signals)g(during)1013 2625 y(ev)o(ery)e(sync)o(hroniza)o(tio)o(n)f (op)q(eration.)p eop %%Page: 8 7 bop -75 -46 a fr(problems)20 b(are)g(a)o(v)o(oided)g(in)g(T)m(aos)g(b)q(ecau\ se)i(the)f(system)g(is)-75 -1 y(structured)12 b(to)d(impose)h(a)f(strict)i (ordering)e(on)h(the)g(four)f(even)o(ts)-75 44 y(listed)k(abo)o(v)o(e.)18 b (The)13 b(handling)e(of)h(an)o(y)g(ev)o(en)o(t)h(can)g(cause)g(only)-75 90 y (lo)n(w)o(er-lev)o(el)k(ev)o(en)o(ts.)26 b(A)16 b(user)i(page)e(fault)g(can)g (incur)h(k)o(ernel)-75 135 y(page)g(faults)f(and)g(k)o(ernel)h(preemptions,)g (but)g(a)f(k)o(ernel)h(pre-)-75 180 y(emption)g(\(including)h(the)h(PC)g(chec) o(k)g(at)f(restart\))j(can)e(not)-75 226 y(incur)g(k)o(ernel)g(page)g(faults.) 32 b(Resuming)17 b(from)g(a)h(user)i(pre-)-75 271 y(emption,)c(b)o(y)i(con)o (trast,)g(is)g(allo)m(w)o(ed)g(to)f(incur)h(page)f(faults.)-75 316 y(By)h(con\ sisten)q(tly)f(ordering)i(the)f(PC)h(c)o(hecks,)g(T)m(aos)f(is)g(able)-75 362 y(to)d(use)h(restartable)g(atomic)d(sequences)k(at)e(all)f(lev)n(els)i(of)e (the)-75 407 y(system)g(without)f(risk)h(of)f(deadlo)q(c)o(k)h(or)g(endless)h (recursion.)-75 538 y fn(5)69 b(The)60 b(p)r(erformance)g(of)h(three)28 606 y (soft)n(w)n(are)41 b(tec)n(hniques)e(for)i(m)n(u-)28 674 y(tual)22 b(exclusio\ n)-75 761 y fr(In)35 b(this)g(section)g(w)o(e)h(compare)e(the)h(p)q(erformanc\ e)g(of)-75 806 y(restartable)27 b(atomic)d(sequences,)31 b(k)o(ernel)26 b(em) n(ulation)f(and)-75 851 y(soft)o(w)o(are)30 b(reserv)o(ation)f(on)h(a)f(RISC-\ based)h(DECstation)-75 897 y(5000/200)11 b(running)i(the)h(Mac)o(h)f(3.0)f (k)o(ernel)i(\(v)o(ersion)g(MK42\))-75 942 y(and)j(CMU's)g(Unix)g(serv)o(er)h (\(v)o(ersion)g(UX23\))f([Golub)e(et)j(al.)-75 987 y(90].)32 b(The)19 b(DECst\ ation)g(5000/200)e(has)i(a)f(25)h(Mhz)g(MIPS)-75 1033 y(R3000)14 b(pro)q(cess\ or)j(whic)o(h)f(do)q(es)g(not)f(supp)r(ort)g(atomic)f(read-)-75 1078 y(modify\ -write)f(memory)e(accesses)17 b(in)c(hardw)o(are.)-33 1123 y(W)l(e)20 b(discu\ ss)h(p)q(erformance)f(at)f(three)i(lev)o(els.)36 b(First,)21 b(w)o(e)-75 1169 y(examine)11 b(the)i(basic)f(o)n(v)o(erhead)h(of)f(the)g(v)n(arious)g(mec)n (hanisms.)-75 1214 y(Next,)20 b(w)o(e)g(examine)d(their)j(e\013ect)h(on)d(the) i(p)q(erformance)f(of)-75 1259 y(common)d(thread)j(managemen)l(t)f(op)q(erati\ ons.)32 b(Finally)-5 b(,)19 b(w)o(e)-75 1305 y(tak)o(e)e(a)f(system-wide)h (p)q(ersp)r(ective)g(and)g(look)g(at)f(the)i(e\013ect)-75 1350 y(that)11 b (m)m(utual)f(exclusion)h(o)n(v)o(erhead)g(has)g(on)f(the)i(p)q(erformance)-75 1395 y(of)h(several)h(applications.)j(In)d(brief,)f(w)o(e)h(sho)o(w)g(that:) -33 1483 y fi(\017)20 b fr(Using)30 b(restartable)h(atomic)d(sequences)k(inst\ ead)e(of)8 1528 y(k)o(ernel-em)n(ulation,)46 b(the)41 b(p)q(erformance)f(of)g (m)m(ulti-)8 1573 y(threaded)22 b(applications)e(can)h(b)q(e)h(impro)m(v)n (ed)g(substan-)8 1619 y(tially)-5 b(.)-33 1698 y fi(\017)20 b fr(Ev)o(en)h (single)g(threaded)h(applications,)f(b)r(ecause)h(they)8 1743 y(deal)13 b(wit\ h)g(m)m(ultithreaded)h(op)q(erating)f(system)g(servers,)8 1788 y(can)g(b)q (ene\014t)g(indirectly)f(from)f(inexp)q(ensiv)o(e)i(m)m(utual)f(ex-)8 1834 y (clusion.)-33 1912 y fi(\017)20 b fr(Thread)25 b(susp)r(ensions)h(o)q(ccur)g (m)m(uch)f(less)g(frequently)8 1958 y(than)35 b(atomic)d(op)q(erations,)40 b (justifying)33 b(the)j(small)8 2003 y(amoun)m(t)17 b(of)g(extra)g(w)o(ork)g (done)g(during)f(thread)i(switc)o(h)8 2048 y(in)12 b(order)h(to)g(impro)m(v)o (e)g(the)g(p)q(erformance)f(of)g(atomic)f(op-)8 2094 y(erations.)-33 2173 y fi (\017)20 b fr(Restartable)14 b(atomic)d(sequences)16 b(are)e(almost)d(nev)o (er)j(in-)8 2218 y(terrupted,)h(v)n(alidating)d(the)i(optimistic)e(approac)o (h.)-75 2305 y(Although)17 b(w)o(e)h(ha)o(v)o(e)g(not)f(collected)i(detailed) f(p)q(erformance)-75 2351 y(information)12 b(in)i(T)l(aos,)h(w)n(e)h(b)q(elie\ v)n(e)g(that)e(the)h(results)h(w)o(ould)-75 2396 y(b)q(e)f(similar.)-75 2507 y fk(5.1)56 b(Microb)q(enc)n(hmarks)-75 2580 y fr(W)l(e)22 b(compare)f(the)h (p)q(erformance)g(of)f(the)h(three)h(soft)n(w)o(are-)-75 2625 y(based)d(m)m (utual)f(exclusion)g(mec)n(hanisms)f(with)h(a)f(test)i(that)1013 -46 y(en)o (ters)d(a)e(critical)h(section)g(using)f(a)h fm(T)l(est-A)o(nd-Set)g fr(lo)q (c)o(k,)g(in-)1013 -1 y(cremen)o(ts)h(a)g(coun)o(ter,)i(and)e(lea)n(v)o(es)h (the)g(critical)e(section)i(b)o(y)1013 44 y(clearing)13 b(the)i fm(T)l(est-A) o(nd-Set)g fr(loc)o(k.)k(The)14 b(test)h(uses)g(only)f(one)1013 90 y(thread,) 19 b(so)f(the)h fm(T)l(est-A)o(nd-Set)f fr(alw)n(a)o(ys)g(succeeds.)34 b(Cons\ e-)1013 135 y(quen)o(tly)l(,)16 b(w)n(e)g(are)g(not)g(measuring)f(the)h(p)q (erformance)f(of)g(the)1013 180 y(thread)20 b(managemen)l(t)h(system)e(itself) h(\(con)o(text)h(switc)o(hing,)1013 226 y(sc)o(heduling,)c(etc.\),)h(but)f (rather)h(that)f(of)g(the)g(basic)h(pro)q(ces-)1013 271 y(sor)13 b(arc)o(hite\ cture,)h(memory)d(system)h(and)h(m)m(utual)g(exclusion)1013 316 y(mec)n(hanis\ m.)22 b(The)16 b(up)q(date)g(to)g(the)g(coun)o(ter)g(is)g(included)g(so)1013 362 y(as)11 b(to)h(mo)o(del)g(a)f(real)h(critical)f(section:)18 b(in)n(teract\ ions)13 b(b)q(et)o(w)o(een)1013 407 y(the)k(atomic)d(op)q(eration,)j(the)g (co)q(de)g(in)f(the)i(critical)e(section,)1013 452 y(and)21 b(the)h(memory)c (system)k(should)f(b)q(e)h(considered)g(when)1013 498 y(ev)n(aluating)14 b (a)j(m)m(utual)f(exclusion)g(mec)o(hanism.)23 b(F)m(or)16 b(exam-)1013 543 y (ple,)11 b(a)f(scheme)g(requiring)h(sev)o(eral)g(writes)h(will)d(not)i(w)o (ork)g(w)n(ell)1013 588 y(on)h(a)h(memory)e(system)i(with)f(a)h(write-through) g(cache)g(and)g(a)1013 634 y(shallo)m(w)h(write-bu\013er)h([Bershad)g(et)f (al.)k(92].)1054 679 y(The)h(elapsed)f(times)f(to)h(execute)i(the)f(v)m(ariou\ s)f(soft)o(w)o(are-)1013 724 y(based)i(m)m(utual)g(exclusion)g(algorithms)d (are)k(sho)o(wn)e(in)h(T)l(a-)1013 770 y(ble)15 b(1.)21 b(The)15 b(v)n(alues) g(in)f(the)i(table)f(w)o(ere)h(determined)f(b)o(y)g(ex-)1013 815 y(ecuting)h (the)h(test)h(in)e(a)g(tigh)o(t)g(lo)q(op)g(1,000,000)e(times,)h(com-)1013 860 y(puting)h(the)h(a)o(v)n(erage)h(elapsed)f(time)e(of)h(each)h(pass)g(through) 1013 906 y(the)c(lo)q(op,)g(and)g(subtracting)h(o\013)f(the)h(loop)g(o)n(v)o (erhead.)19 b(There)1013 951 y(w)n(as)14 b(only)e(negligible)g(v)n(ariation)g (in)h(times)f(o)o(v)n(er)i(several)f(runs)1013 996 y(of)g(the)h(b)q(enchmarks) f(on)h(an)f(unloaded)h(system.)1059 1082 y(Soft)o(w)n(are)h(Mechanism)1802 1096 y 2 46 v 1844 1082 a(Time)1802 1141 y 2 46 v 1827 1127 a(\()p fj(\026)p fr(secs\))1034 1143 y 946 2 v 1059 1174 a(Restartable)f(A)o(tomic)f(Sequences) j(\(branc)o(h\))1802 1188 y 2 46 v 1864 1174 a(.64)1059 1220 y(Restartable)e (A)o(tomic)f(Sequences)j(\(inline\))1802 1233 y 2 46 v 1864 1220 a(.51)1059 1265 y(Kernel)f(Em)n(ulation)1802 1279 y 2 46 v 1854 1265 a(4.15)1059 1310 y (Soft)o(w)n(are-reservation)e(\(a\))1802 1324 y 2 46 v 1854 1310 a(1.51)1059 1356 y(Soft)o(w)n(are-reservation)g(\(b\))1802 1369 y 2 46 v 1854 1356 a(1.16) 1013 1444 y(T)l(able)k(1:)24 b(Microb)r(enc)o(hmark)16 b(results)j(for)d(the) i(DECstation)1013 1489 y(5000/200.)1054 1582 y(Restartable)k(atomic)e(sequenc\ es)k(w)o(ere)f(measured)e(with)1013 1628 y(branc)o(hes)15 b(to)g(an)f(explici\ tly)g(registered)i(sequence,)g(and)f(also)1013 1673 y(with)c(inlined)h(co)q (de.)18 b(The)13 b(p)q(erformance)f(di\013erence)i(b)q(et)o(w)o(een)1013 1718 y(the)20 b(t)o(w)o(o)g(approac)o(hes)h(is)f(due)h(to)f(the)h(subroutine)g(lin\ k)m(age)1013 1764 y(o)n(v)o(erhead)j(on)f(the)g(MIPS.)g(Kernel)h(em)n(ulation) e(and)h(b)q(oth)1013 1809 y(reserv)o(ation)15 b(schemes)h(use)h(out-of-line)e (calls)h(to)g(implem)o(en)m(t)1013 1854 y(the)11 b(atomic)e(op)q(erations.)17 b(F)l(or)11 b(these)h(mec)n(hanisms,)e(the)h(o)o(v)n(er-)1013 1900 y(head)h (is)h(su\016cien)o(tly)f(high)g(that)g(there)i(is)e(little)g(to)g(b)r(e)g(gai\ ned)1013 1945 y(b)n(y)h(inlining.)j(Soft)o(w)n(are-reservation)c(proto)q(col) h(\(a\))g(is)g(an)g(im-)1013 1990 y(plemen)m(tation)21 b(of)g(Lamp)o(ort's)g (fast)g(m)n(utual)g(exclusion)g(al-)1013 2036 y(gorithm)c(in)i(whic)o(h)g(eac) o(h)h(lock)f(is)g(represen)q(ted)h(b)o(y)f(a)g(data)1013 2081 y(structure)g (con)o(taining)e(an)h(o)n(wner)h(and)e(a)h(reserv)o(ation)f(\014eld)1013 2126 y(\(one)e(w)o(ord)g(eac)o(h\),)g(and)g(an)g(arra)o(y)f(of)h(b)q(o)q(oleans)g (indexed)g(b)o(y)1013 2172 y(a)9 b(thread)i(iden)o(ti\014er.)17 b(It)10 b(is) g(the)h(most)e(direct)h(implemen)m(tation)1013 2217 y(of)k(the)i(algorithm,)c (but)j(su\013ers)i(from)c(the)j(high)e(storage)h(re-)1013 2262 y(quiremen)n (ts)f(describ)s(ed)h(in)f(Section)g(2.2.)19 b(Proto)q(col)14 b(\(b\))h(uses) 1013 2308 y(Lamp)o(ort's)f(algorithm)d(to)i(implemen)m(t)g(the)i(\\meta")d (m)m(utual)1013 2353 y(exclusion)g(function)f(sho)o(wn)h(in)g(Figure)g(2.)17 b (Proto)r(col)11 b(\(b\),)i(de-)1013 2398 y(spite)d(an)f(increase)i(in)f(the)g (n)o(um)m(b)r(er)g(of)f(memory)f(accesses)k(o)o(v)n(er)1013 2444 y(Proto)q (col)f(\(a\),)h(executes)i(more)d(quic)o(kly)g(on)h(the)g(DECstation)1013 2489 y(5000/200)j(b)q(ecause)k(of)d(the)i(cost)g(of)e(ha)o(ving)h(to)g(compute)f (a)1013 2534 y(thread's)d(unique)f(iden)o(ti\014er)h(and)f(the)h(address)h (of)e(its)g(\\busy")1013 2580 y(bit.)17 b(With)12 b(proto)q(col)g(\(a\),)g (these)i(m)n(ust)f(b)q(e)g(computed)f(on)h(en-)1013 2625 y(try)f fm(and)h fr (exit)f(to)g(a)g(critical)f(section,)i(whereas)g(with)f(proto)q(col)p eop %%Page: 9 8 bop -75 -44 a fr(\(b\),)21 b(they)f(need)h(only)e(b)q(e)h(computed)f(on)g (entry)m(.)35 b(A)20 b(dedi-)-75 1 y(cated)e(p)q(er-thread)g(hardw)o(are)f (register)h(w)o(ould)e(rev)o(erse)i(this)-75 47 y(disparit)o(y)l(.)-33 93 y (The)d(table)h(sho)o(ws)f(that)h(k)n(ernel)g(em)n(ulation)f(is)g(b)o(y)g(far) g(the)-75 139 y(most)g(exp)q(ensive)h(approac)o(h;)h(the)g(trap)f(and)g(excep\ tion)h(dis-)-75 184 y(patc)o(h)g(in)f(the)h(k)o(ernel)g(are)g(the)h(main)c (sources)19 b(of)d(o)n(v)o(erhead.)-75 229 y(Both)c(soft)o(w)o(are)g(reservat\ ions)f(schemes)g(are)i(faster)f(than)g(k)o(er-)-75 275 y(nel)f(em)n(ulation,) e(but)i(m)n(uc)o(h)g(slo)n(w)o(er)h(than)e(restartable)i(atomic)-75 320 y(seq\ uences)j(due)f(to)f(the)g(n)o(um)n(b)q(er)g(of)g(instructions)g(and)g(mem-) -75 365 y(ory)24 b(accesses)j(required.)51 b(Despite)25 b(their)g(b)q(etter)h (p)q(erfor-)-75 411 y(mance,)11 b(b)q(oth)i(reserv)o(ation)e(strategies)j(ha) n(v)o(e)f(practical)f(prob-)-75 456 y(lems)h(that)i(mak)m(e)g(them)f(di\016cu\ lt)f(to)i(use)g(\(see)h(Section)f(2.2\).)-75 501 y(Consequently)l(,)c(in)g (the)i(rest)f(of)f(this)h(section,)g(w)o(e)f(restrict)i(our)-75 547 y(compari\ sons)j(to)h(systems)g(using)f(only)g(restartable)i(atomic)-75 592 y(sequences) e(and)e(k)o(ernel)g(em)n(ulation.)-75 710 y fk(5.2)56 b(Thread)18 b(managemen) l(t)g(o)o(v)n(erhead)-75 784 y fr(Mac)o(h's)32 b(user-level)g(thread)i(manage\ m)o(en)m(t)e(system,)37 b(C-)-75 830 y(Threads,)15 b(lik)n(e)g(other)h(thread) f(managemen)l(t)g(pac)o(k)n(ages)g([An-)-75 875 y(derson)i(et)f(al.)23 b(89,) 14 b(Bershad)j(et)g(al.)22 b(88,)15 b(W)l(eiser)i(et)f(al.)23 b(89],)-75 920 y (relies)11 b(hea)o(vily)e(on)h(simple)e(atomic)h(op)q(erations)h(to)g(impleme\ n)l(t)-75 966 y(higher)15 b(lev)n(el)g(facilities)e(such)i(as)f(threads,)i (locks)e(and)h(condi-)-75 1011 y(tion)20 b(v)n(ariables.)37 b(W)l(e)21 b(look) o(ed)g(at)f(several)g(b)q(enchmarks)g(to)-75 1056 y(understand)e(the)f(in\015\ uence)h(that)f(atomic)e(op)q(erations)i(ha)n(v)o(e)-75 1102 y(on)12 b(the)h (p)r(erformance)f(of)g(these)i(higher)e(lev)o(el)g(facilities)g(using)-75 1147 y(t)o(w)o(o)18 b(di\013erent)h(v)n(ersions)h(of)e(C-Threads.)33 b(One)19 b (v)o(ersion)g(re-)-75 1192 y(lies)12 b(on)f(k)o(ernel)h(em)n(ulation)f(for)g (synchronization.)17 b(The)12 b(other)-75 1238 y(uses)21 b(restartable)f(atom\ ic)e(sequences.)37 b(The)20 b(b)q(enchmarks,)-75 1283 y(whic)o(h)d(con)o(tain) f(the)h(kinds)g(of)f(op)q(erations)h(t)o(ypically)f(found)-75 1328 y(in)d(m)n (ultithreaded)h(programs,)e(are:)-33 1420 y fi(\017)20 b fm(Spinlo)n(ck.)k fr (One)16 b(thread)g(rep)r(eatedly)g(acquires)h(and)e(re-)8 1466 y(leases)22 b (a)f(spinlo)q(c)o(k.)40 b(The)22 b(spinloc)o(k)g(is)f(implem)o(en)m(ted)8 1511 y(with)14 b(a)f fm(T)m(est-A)n(nd-Set)i fr(sequence.)-33 1595 y fi(\017)20 b fm(Mutexlo)n(ck.)38 b fr(One)21 b(thread)g(rep)r(eatedly)g(acquires)g(and)8 1640 y(releases)c(a)d(relinquishing)g(m)n(utex.)21 b(Unlik)n(e)16 b(a)e(spinl\ o)q(c)o(k,)8 1686 y(if)g(a)i(thread)g(tries)g(to)f(acquire)g(a)g(held)h(m)m (utex,)g(it)f(relin-)8 1731 y(quishes)g(the)h(pro)q(cessor.)22 b(The)15 b(m)m (utex)g(is)g(implem)o(en)m(ted)8 1776 y(using)f(a)f(spinlo)q(c)o(k)h(and)f (a)h(queue)h(of)e(w)o(aiting)g(threads.)-33 1860 y fi(\017)20 b fm(F)m(orktes\ t.)51 b fr(Threads)17 b(are)f(recursiv)q(ely)g(fork)n(ed)h(in)f(suc-)8 1905 y (cession;)21 b(i.e.,)c(thread)i(1)e(forks)h(thread)h(2)f(whic)o(h)g(forks)8 1951 y(thread)12 b(3,)f(etc..)17 b(After)12 b(forking,)e(a)h(thread)h(immedia) o(tely)8 1996 y(terminates.)-33 2080 y fi(\017)20 b fm(Pingp)n(ong.)56 b fr (Tw)o(o)16 b(threads)i(\\pingp)q(ong")e(o\013)h(one)g(an-)8 2125 y(other)d (in)e(a)h(tigh)n(t)g(lo)q(op,)f(using)h(a)f(m)n(utex)h(and)g(condition)8 2170 y(v)n(ariable)g(to)h(execute)h(alternately)m(.)-33 2262 y(The)g(p)q(erformanc\ e)g(of)f(these)i(b)r(enc)o(hmarks)e(running)h(on)g(a)-75 2308 y(DECstation)f (5000/200)e(is)i(sho)o(wn)g(in)f(T)m(able)g(2.)19 b(Eac)o(h)14 b(en)o(try)-75 2353 y(in)h(the)h(table)g(represen)q(ts)g(the)g(elapsed)g(time)e(p)q(er)j(op) q(eration)-75 2398 y(\(i.e,)f(one)h(spinlo)q(c)o(k)f(acquire)h(and)g(release,) h(one)e(m)n(utex)h(lock)-75 2444 y(and)11 b(unloc)o(k,)g(one)g(fork)g(and)f (exit,)h(one)g(ping)f(and)h(p)q(ong\).)17 b(The)-75 2489 y(table)i(sho)o(ws)g (that)g(the)h(p)q(erformance)e(of)h(thread)g(manage-)-75 2534 y(men)n(t)14 b (op)q(erations)h(dep)q(ends)g(up)r(on)f(the)g(p)r(erformance)f(of)h(the)-75 2580 y(underlying)20 b(synchronization)f(mec)o(hanism.)35 b(When)21 b(using) -75 2625 y(k)o(ernel)12 b(em)n(ulation)d(for)i fm(T)m(est-A)n(nd-Set)p fr(,)h (thread)g(managemen)l(t)1013 -46 y(functions)k(sp)q(end)h(the)f(ma)q(jorit)n (y)g(of)f(their)i(time)e(in)g(the)i(k)n(er-)1013 -1 y(nel)g(executing)h(synch\ ronization)f(co)q(de.)29 b(With)17 b(restartable)1013 44 y(atomic)h(sequences\ ,)25 b(synchronization)20 b(o)n(v)o(erhead)i(b)q(ecomes)1013 90 y(negligible.) 16 b(Ev)o(en)d fm(PingPong)p fr(,)g(with)g(its)f(pro\015igate)g(synchro-)1013 135 y(nization)g(\(26)g fm(T)m(est-A)n(nd-Set)p fr(s)i(p)q(er)g(cycle\),)f (sp)r(ends)g(less)h(than)1013 180 y(10%)i(of)h(its)h(time)e(synchronizing)h (when)h(using)g(restartable)1013 226 y(atomic)12 b(sequences.)1197 319 y(Benc\ hmark)1426 332 y 2 46 v 1451 319 a(Em)n(ulation)53 b(R.A.S.)1426 378 y 2 46 v 1482 364 a(\()p fj(\026)p fr(secs\))83 b(\()p fj(\026)p fr(secs\))1172 379 y 670 2 v 1197 411 a(Spinloc)o(k)1426 425 y 2 46 v 1519 411 a(4.3)154 b(.58) 1197 457 y(MutexLo)q(ck)1426 470 y 2 46 v 1519 457 a(4.6)g(.91)1197 502 y(F)l (orkT)m(est)1426 515 y 2 46 v 1509 502 a(43.7)132 b(23.8)1197 547 y(PingP)o (ong)1426 561 y 2 46 v 1498 547 a(230.8)112 b(115.2)1013 635 y(T)l(able)14 b (2:)k(The)d(e\013ect)g(of)f(synchronization)f(on)h(thread)h(man-)1013 681 y (agemen)m(t)21 b(o)n(v)o(erhead)g(under)h(Mac)o(h)e(3.0)f(on)h(a)g(DECstation) 1013 726 y(5000/200.)1013 900 y fk(5.3)55 b(Application)18 b(p)r(erformance) 1013 975 y fr(The)13 b(microbenchmarks)f(and)h(thread)h(managem)o(en)m(t)f (b)q(ench-)1013 1021 y(marks)j(indicate)i(that)g(restartable)h(atomic)c(seque\ nces)21 b(can)1013 1066 y(ha)n(v)o(e)10 b(a)g(large)f(e\013ect)j(on)d(individ\ ual)f(op)q(erations.)17 b(Ultimately)-6 b(,)1013 1111 y(though,)21 b(w)o(e)g (are)g(concerned)i(with)d(p)q(erformance)g(system-)1013 1157 y(wide.)36 b(In) 20 b(this)g(subsection)h(w)o(e)f(examine)f(the)h(e\013ect)i(that)1013 1202 y (restartable)16 b(atomic)d(sequences)18 b(ha)n(v)o(e)e(on)e(the)i(p)q(erforma\ nce)1013 1247 y(of)f(several)h(applications)f(running)h(on)g(Mac)o(h)g(3.0.) 24 b(The)16 b(ap-)1013 1293 y(plications)d(are:)1054 1376 y fi(\017)21 b fm (text-format.)g fr(F)m(ormat)13 b(a)i(v)o(ersion)g(of)g(this)g(pap)q(er)h(usi\ ng)1096 1422 y(L)1107 1417 y fc(a)1126 1422 y fr(T)1149 1434 y(E)1172 1422 y (X.)1054 1507 y fi(\017)21 b fm(afs-b)m(ench.)36 b fr(A)20 b(script)g(of)f (\014le)g(system)g(in)o(tensiv)o(e)h(pro-)1096 1553 y(grams)26 b(suc)o(h)i (as)f(cop)o(y)m(,)j(compile)c(and)h(search)h(that)1096 1598 y(execute)23 b (out)f(of)f(the)i(Andrew)g(File)e(System)g([Sat)o(y)n(a-)1096 1643 y(naran)n (y)o(an)o(y)n(an)14 b(et)h(al.)i(85].)1054 1729 y fi(\017)k fm(p)n(arthenon-) p fj(n)p fm(.)32 b fr(A)18 b(resolution-based)h(theorem)f(pro)o(v)n(er)1096 1774 y(that)13 b(uses)h fj(n)f fr(threads)i(to)e(exploit)f(or-parallelism)e ([Bose)1096 1819 y(et)k(al.)j(89].)1054 1905 y fi(\017)k fm(pr)m(o)n(c)n(on-6\ 4.)42 b fr(A)22 b(pro)q(ducer-consumer)h(application)d(in)1096 1950 y(whic)n (h)d(one)g(consumer)g(thread)g(co)q(ordinates)g(with)g(one)1096 1996 y(pro)q (ducer)d(thread)f(to)g(read)g(data)g(from)e(a)h(large)h(\014le)g(in)n(to)1096 2041 y(a)g(64)g(b)o(yte)i(bu\013er.)1054 2125 y(T)m(able)d(3)h(sho)o(ws)h(the) f(b)r(eha)o(vior)f(of)h(the)g(applications)f(when)1013 2170 y(run)k(under)i (t)o(w)o(o)e(di\013erent)h(v)n(ersions)h(of)e(the)h(op)q(erating)g(sys-)1013 2215 y(tem.)29 b(The)18 b(columns)f(lab)q(eled)h(\\Em)n(ul")f(re\015ect)j(run\ s)e(using)1013 2261 y(k)n(ernel)k(em)n(ulation)e(for)i(the)g(application)e (and)h(for)g(Mac)o(h's)1013 2306 y(user-lev)o(el)16 b(Unix)g(server.)25 b(The) 17 b(columns)e(lab)q(eled)h(\\R.A.S.")1013 2351 y(re\015ect)g(runs)g(using)f (restartable)h(atomic)e(sequences)k(for)c(the)1013 2397 y(applications)k(and) h(for)g(the)h(Unix)e(server.)35 b(Eac)o(h)20 b(program)1013 2442 y(w)n(as)15 b (run)h(sev)o(eral)f(times)f(and)h(the)g(a)o(v)o(erage)g(v)n(alues)g(for)f(mea\ -)1013 2487 y(suremen)o(ts)e(tak)o(en)h(during)f(the)g(runs)h(are)g(giv)n(en) g(in)f(the)h(table.)1054 2534 y(Restartable)19 b(atomic)f(sequences)j(ha)o (v)o(e)e(the)h(greatest)g(ef-)1013 2580 y(fect)13 b(on)g(applications)f(that) g(use)i(threads)g(explicitly)l(,)e(such)h(as)1013 2625 y fm(p)n(arthenon)k fr (with)g(1)g(or)g(10)f(threads,)j(and)e fm(pr)m(o)n(c)n(on-64)h fr(whic)o(h)p eop %%Page: 10 9 bop 288 -43 a fr(Program)552 -30 y 2 46 v 646 -43 a(Elapsed)118 b(Em)n(ulati\ on)48 b(Restarts)132 b(Thread)552 16 y 2 46 v 611 2 a(Time)13 b(\(secs\))128 b (T)l(raps)333 b(Susp)q(ensions)552 61 y 2 46 v 578 47 a(Em)n(ul.)49 b(R.A.S.) 495 b(Em)n(ul.)57 b(R.A.S.)263 63 y 1400 2 v 288 94 a(text-format)552 108 y 2 46 v 595 94 a(10.1)99 b(9.8)124 b(57305)156 b(0)146 b(295)109 b(317)288 140 y (afs-b)q(ench)552 153 y 2 46 v 585 140 a(239.4)67 b(231.1)82 b(2191276)125 b (42)g(8856)88 b(9876)288 185 y(parthenon-1)552 199 y 2 46 v 595 185 a(25.8)g (18.5)93 b(1395534)135 b(4)146 b(412)109 b(354)288 230 y(parthenon-10)552 244 y 2 46 v 595 230 a(26.1)88 b(18.6)93 b(1576714)135 b(7)146 b(610)109 b(499) 288 276 y(pro)r(con-64)552 289 y 2 46 v 595 276 a(30.4)88 b(15.7)93 b(2738168) 135 b(4)115 b(106969)56 b(91494)307 364 y(T)m(able)14 b(3:)j(E\013ect)f(of)d (synchronization)g(o)n(v)o(erhead)i(on)f(application)e(p)q(erformance.)-75 486 y(impro)m(v)o(e)18 b(b)o(y)f(ab)q(out)g(30%)g(and)g(50%)g(resp)r(ectiv)o(ely) m(.)28 b(Single-)-75 531 y(threaded)22 b(\\v)m(anilla)d(Unix")h(applications) f(also)h(b)q(ene\014t)i(in-)-75 577 y(directly)e(through)f(the)h(impro)m(v)o (ed)g(p)q(erformance)f(of)g(m)m(ulti-)-75 622 y(threaded)e(user-lev)o(el)f (op)q(erating)f(system)h(services.)24 b(F)m(or)15 b(ex-)-75 667 y(ample,)g (the)h(p)q(erformance)g(of)g(the)g(text-formatter)g(and)g(the)-75 713 y(\014l\ e)21 b(system)g(b)q(enchmarks,)g(whic)o(h)g(are)h(themselv)n(es)g(single)-75 758 y(threaded)f(but)f(rely)f(on)h(the)g(m)m(ultithreaded)g(Unix)f(server,) -75 803 y(impro)m(v)o(es)14 b(b)o(y)g(ab)q(out)g(3%.)-33 851 y(The)i(column)f (lab)q(eled)i(\\Em)m(ulation)e(T)m(raps")h(re\015ects)j(the)-75 896 y(n)o(um) m(b)r(er)12 b(of)f(sync)o(hronizations)g(that)h(o)q(ccurred)h(when)f(atomic) -75 941 y(op)q(erations)18 b(w)o(ere)h(implemen)l(ted)g(in)e(the)i(k)o(ernel.) 31 b(The)18 b(col-)-75 987 y(umn)e(labeled)i(\\Restarts")f(sho)o(ws)g(the)h (a)n(v)o(erage)g(n)o(um)m(b)q(er)g(of)-75 1032 y(atomic)k(sequence)j(restarts) g(that)f(had)f(to)h(b)q(e)g(p)q(erformed)-75 1077 y(when)13 b fm(T)m(est-A)n (nd-Set)h fr(w)o(as)f(implem)o(en)m(ted)g(with)g(explicit)f(reg-)-75 1123 y (istration.)17 b(The)11 b(restart)h(coun)o(t)f(demonstrates)g(that)g(the)g (lik)n(e-)-75 1168 y(lihoo)q(d)g(of)f(a)h(thread)g(b)r(eing)f(susp)r(ended)i (during)f(a)f(restartable)-75 1213 y(atomic)i(sequence)k(is)e(extremely)f(sma\ ll.)-33 1261 y(The)f(last)g(t)o(w)o(o)f(columns)g(sho)o(w)h(the)h(n)o(um)m (b)q(er)g(of)e(times)g(that)-75 1306 y(the)k(k)o(ernel)h(susp)r(ended)f(a)g (thread.)21 b(F)m(or)14 b(restartable)i(atomic)-75 1352 y(sequences,)i(it)e (indicates)g(ho)n(w)g(man)m(y)g(times)f(a)g(thread's)h(ex-)-75 1397 y(ecution) f(state)h(had)f(to)f(b)r(e)h(c)o(heck)o(ed)g(to)g(ensure)h(that)f(atomic)-75 1442 y(op)q(erations)j(ev)o(entually)e(execute)k(atomically)-6 b(.)30 b(Compa\ ring)-75 1488 y(this)14 b(column)d(to)j(the)g(n)o(um)m(b)r(er)g(of)f(em)n(ula\ tion)f(faults)h(justi\014es)-75 1533 y(the)g(small)e(amoun)m(t)h(of)g(extra)i (w)n(ork)f(required)g(b)o(y)g(the)g(restart)-75 1578 y(strategies)i(whenever) f(a)f(thread)i(is)e(resc)q(heduled.)18 b(The)c(more)-75 1624 y(compelling)h (justi\014cation,)g(of)g(course,)i(is)f(the)g(reduced)i(exe-)-75 1669 y(cutio\ n)c(time)e(for)i(the)g(applications.)-33 1716 y(The)35 b(n)o(um)n(b)q(er)h (of)f(em)n(ulation)f(traps)i(can)g(b)q(e)g(used)-75 1762 y(to)27 b(accoun)o (t)h(for)e(the)i(p)q(erformance)f(di\013erence)i(b)q(etw)o(een)-75 1807 y(the) 34 b(t)o(w)o(o)f(v)n(ersions)h(of)f(the)h(system.)75 b(F)m(or)33 b(example,) -75 1852 y fm(p)n(arthenon-10)p fr(,)18 b(with)f(its)g(1.57)e(million)f(k)n (ernel)k(em)n(ulations,)-75 1898 y(should)25 b(impro)m(v)o(e)g(b)o(y)g(ab)q (out)g(1.57)e(million)f fi(\002)j fr(3)p fj(:)p fr(7)f fj(\026)p fr(secs)-75 1943 y(\(4.3)13 b fj(\026)p fr(secs)p fi(\000)p fr(.58)i fj(\026)p fr(secs\)) r(,)9 b(or)h(ab)q(out)f(5.8)f(seconds.)18 b(The)10 b(actual)-75 1988 y(impro) m(v)o(emen)n(t)17 b(is)f(sligh)o(tly)g(greater)h(than)g(this)g(for)f(t)o(w)o (o)g(rea-)-75 2034 y(sons.)26 b(First,)17 b(the)g(correlation)f(b)q(etw)n(een) i(elapsed)f(time)e(and)-75 2079 y(n)o(um)m(b)r(er)i(of)e(em)n(ulation)g(traps) i(is)f(neither)h(strictly)g(negativ)n(e)-75 2124 y(nor)f(strictly)g(p)q(ositi\ v)o(e.)24 b(Hence,)18 b(the)e(n)o(um)n(b)q(er)g(of)g(em)n(ulation)-75 2170 y (traps)i(is)e(only)h(a)f(go)q(o)q(d,)h(but)h(not)e(exact,)i(predictor)g(of)f (p)q(er-)-75 2215 y(formance)d(impro)m(v)o(emen)n(t.)23 b(Second,)16 b(some)e (of)h(the)g(impro)m(v)o(e-)-75 2260 y(men)n(t)20 b(is)f(due)h(to)g(the)g(redu\ ction)g(in)f(scheduling)g(o)o(v)n(erhead)-75 2306 y(that)f(comes)g(with)g(a)h (decrease)h(in)e(critical)g(section)h(service)-75 2351 y(time.)-33 2398 y(F)l (or)i(ev)o(en)g(v)o(ery)g(short)g(critical)f(sections)i(\(10)e(to)h(20)f(in-) -75 2444 y(structions\))d(restartable)h(atomic)c(sequences)19 b(add)d(little) f(ex-)-75 2489 y(tra)f(o)o(v)n(erhead,)h(and)e(m)n(uc)o(h)h(of)f(that)h(o)o (v)n(erhead)h(comes)f(b)q(efore)-75 2534 y(the)j(critical)f(section)i(has)f (actually)e(b)r(een)i(en)o(tered.)28 b(Conse-)-75 2580 y(quen)o(tly)l(,)14 b (a)g(short)h(critical)f(section)g(remains)g(short,)g(and)g(the)-75 2625 y(lik) n(elihoo)q(d)c(of)e(the)i(critical)f(section)h(itself)f(b)q(eing)g(susp)r(end\ ed)i(is)1013 484 y(small.)17 b(With)c(k)o(ernel)i(em)n(ulation,)e(though,)h (eac)o(h)h fm(T)l(est-A)o(nd-)1013 529 y(Set)e fr(tak)n(es)h(ab)q(out)f(100)f (instructions,)h(and)g(nearly)g(all)e(are)j(ex-)1013 574 y(ecuted)j(with)e (pro)q(cessor)i(in)n(terrupts)h(disabled.)k(When)16 b(con-)1013 620 y(trol)e (returns)i(out)e(of)g(the)h(k)o(ernel,)f(in)o(terrupts)i(are)f(reenabled)1013 665 y(and)j(an)o(y)g(p)r(ending)g(in)o(terrupts)i(are)g(deliv)n(ered.)34 b (If)18 b(the)i(de-)1013 710 y(liv)m(ered)c(in)n(terrupt)f(causes)h(a)e(preemp\ tion,)f(then)i(the)f(thread)1013 756 y(that)k(just)g(p)q(erformed)g(the)h(ato\ mic)d(op)q(eration)i(will)f(b)q(e)i(de-)1013 801 y(sc)o(heduled)d(and)g(anoth\ er)f(thread)i(will)d(run.)23 b(If)15 b(that)g(thread)1013 846 y(attempts)e (to)i(en)o(ter)g(the)g(same)e(critical)h(section,)h(it)f(will)f(\014nd)1013 892 y(the)21 b fm(T)l(est-A)o(nd-Set)g fr(v)m(ariable)f(already)g(set)h(and)f (will)f(relin-)1013 937 y(quish)13 b(its)h(pro)q(cessor)i(to)e(the)g(schedule\ r.)1054 987 y(W)l(e)d(lo)q(ok)n(ed)g(more)e(closely)i(at)f fm(p)n(arthenon-10) i fr(to)e(determine)1013 1032 y(the)20 b(in\015uence)h(of)f(in\015ated)g(crit\ ical)g(sections)h(on)f(program)1013 1078 y(b)q(eha)o(vior.)28 b(The)18 b(prog\ ram)e(synchronizes)i(often,)g(but)g(most)1013 1123 y(sync)o(hronization)10 b (op)q(erations)h(guard)g(short)g(critical)g(sections)1013 1168 y(that)17 b (simply)e(incremen)o(t)i(a)g(counter,)h(or)f(dequeue)i(an)e(item)1013 1214 y (from)10 b(a)j(link)m(ed)g(list.)18 b(In)12 b(running)g(the)i(program,)c(w)o (e)j(coun)o(ted)1013 1259 y(the)k(n)o(um)n(b)q(er)h(of)e(times)g(that)h(a)g (thread)h(w)o(as)f(unable)g(to)g(en-)1013 1304 y(ter)e(a)f(critical)f(section) j(b)q(ecause)g(of)d(a)h(lo)q(c)o(k)g(held)g(b)o(y)h(another)1013 1350 y(\(sus\ p)r(ended\))j(thread.)30 b(When)18 b(using)f(k)o(ernel)h(em)n(ulation)e(in) 1013 1395 y fm(p)n(arthenon-10)p fr(,)d(a)g(thread)h(found)f(a)g fm(T)m(est-A) n(nd-Set)h fr(lock)f(held)1013 1440 y(about)23 b(t)o(wice)g(as)f(often)h(as)f (with)g(restartable)i(atomic)c(se-)1013 1486 y(quences.)1013 1641 y fn(6)69 b (Soft)n(w)n(are)35 b(vs.)68 b(hardw)n(are)37 b(sup-)1116 1709 y(p)r(ort)23 b (for)h(m)n(utual)e(exclusion)1013 1804 y fr(The)12 b(lac)o(k)g(of)f(hardw)o (are)i(supp)r(ort)f(for)g(atomic)e(op)q(erations)j(of-)1013 1850 y(fered)h (the)f(initial)f(motiv)-5 b(ation)13 b(to)g(in)n(v)o(estigate)h(e\016cien)o (t)f(soft-)1013 1895 y(w)n(are)k(solutions)f([Anderson)g(et)h(al.)24 b(91].)g (Most)16 b(pro)q(cessors,)1013 1940 y(ho)n(w)o(ev)o(er,)e(do)e(supp)r(ort)h (some)f(t)o(yp)q(e)i(of)e(atomic)f(read-modify-)1013 1986 y(write)h(instructi\ on.)18 b(In)12 b(this)g(section)g(w)o(e)g(ev)o(aluate)f(the)i(use)g(of)1013 2031 y(restartable)i(atomic)d(sequences)k(on)e(suc)o(h)g(pro)r(cessors.)1054 2081 y(W)l(e)21 b(measured)g(the)h(o)n(v)o(erhead)g(to)f(acquire)g(and)g(rele\ ase)1013 2126 y(a)13 b fm(T)l(est-A)o(nd-Set)h fr(lock)f(using)g(memory-in)l (terlo)q(ck)n(ed)h(instruc-)1013 2172 y(tions)d(and)h(restartable)g(atomic)e (sequences)15 b(on)c(eigh)o(t)h(pro)q(ces-)1013 2217 y(sor)19 b(arc)o(hitectu\ res.)36 b(The)19 b(results)h(are)g(sho)o(wn)f(in)f(T)m(able)h(4.)1013 2262 y (F)l(or)13 b(the)h(in)o(terlo)q(c)o(k)o(ed)g(cases,)g(the)g(times)e(do)h(not) g(include)g(an)o(y)1013 2308 y(link)l(age)j(o)n(v)o(erhead,)h(as)e(the)i fm (T)l(est-A)o(nd-Set)f fr(and)f(subsequen)q(t)1013 2353 y(release)d(instructio\ ns)g(can)f(b)r(e)g(executed)i(inline.)k(In)11 b(the)h(cases)1013 2398 y(of)f (explicit)h(registration,)h(link)l(age)g(o)n(v)o(erhead)g(is)g(included)f(for) 1013 2444 y(the)19 b fm(T)m(est-A)n(nd-Set)p fr(,)i(but)e(not)g(for)f(the)i (release,)h(whic)o(h)e(can)1013 2489 y(b)q(e)g(inlined.)31 b(The)18 b(fourth) h(column)e(of)h(T)l(able)g(4)h(sho)o(ws)f(the)1013 2534 y(call)13 b(link)l (age)h(o)o(v)o(erhead.)19 b(Ev)o(en)14 b(with)g(the)g(link)m(age)g(o)o(v)n (erhead,)1013 2580 y(restartable)22 b(atomic)e(sequences)k(are)e(more)f(e\016\ cien)o(t)h(than)1013 2625 y(memory-i)o(n)l(terlo)r(c)o(k)o(ed)d(instructions) h(on)g(the)f(DEC)h(CV)-5 b(AX,)p eop %%Page: 11 10 bop 664 -30 a 2 46 v 690 -43 a fr(In)o(terlo)q(ck)n(ed)91 b(Explicit)105 b (Link)m(age)67 b(Designated)290 2 y(Pro)q(cessor)664 16 y 2 46 v 691 2 a(Inst\ ruction)51 b(Registration)e(Ov)o(erhead)68 b(Sequence)664 61 y 2 46 v 727 47 a (\()p fj(\026)p fr(secs\))136 b(\()p fj(\026)p fr(secs\))123 b(\()p fj(\026)p fr(secs\))111 b(\()p fj(\026)p fr(secs\))265 63 y 1396 2 v 290 94 a(DEC)14 b (CV)-5 b(AX)664 108 y 2 46 v 764 94 a(2.8)207 b(2.2)d(.6)193 b(1.6)290 140 y (Motorola)13 b(68030)664 153 y 2 46 v 764 140 a(1.1)207 b(2.0)d(.8)193 b(1.2) 290 185 y(In)o(tel)14 b(386)664 199 y 2 46 v 764 185 a(1.0)207 b(1.6)d(.7)g (.9)290 230 y(In)o(tel)14 b(486)664 244 y 2 46 v 774 230 a(.7)229 b(.6)214 b (.3)204 b(.3)290 276 y(In)o(tel)14 b(860)664 289 y 2 46 v 774 276 a(.3)229 b (.4)214 b(.2)204 b(.2)290 321 y(Motorola)13 b(88000)664 335 y 2 46 v 774 321 a (.9)229 b(.3)214 b(.1)204 b(.2)290 366 y(Sun)14 b(SP)m(AR)n(C)664 380 y 2 46 v 774 366 a(.8)218 b(1.0)204 b(.3)g(.7)290 412 y(HP)14 b(9000)f(Series)i(700) 664 425 y 2 46 v 764 412 a(.94)207 b(.17)194 b(.08)182 b(.09)44 500 y(T)m(abl\ e)13 b(4:)18 b(Hardw)o(are)c(and)g(soft)o(w)o(are)g(o)o(v)n(erheads)i(of)d fm (T)l(est-A)o(nd-Set)h fr(using)g(di\013erent)g(implemen)l(tation)f(strategies\ .)-75 620 y(the)21 b(In)o(tel)g(486,)h(the)f(Motorola)f(88000,)h(and)f(the)i (Hewlett)-75 665 y(P)o(ac)o(k)n(ard)14 b(9000)f(\(P)l(A-RISC\))h(Series)h(700\ .)-33 712 y(Using)j(designated)h(sequences,)j(the)e(soft)o(w)n(are)f(approac) o(h)-75 758 y(outp)q(erforms)i(the)h(hardw)o(are)g(in)g(all)e(cases)j(\(subtr\ act)g(the)-75 803 y(o)o(v)n(erhead)13 b(of)d(link)m(age)h(from)f(that)h(of)g (an)g(explicitly)f(registered)-75 848 y(sequence\).)20 b(As)13 b(pro)q(cessor) i(sp)q(eeds)f(increase)g(relativ)n(e)f(to)g(bus)-75 894 y(and)g(memory)f(sp)q (eeds,)j(w)n(e)f(exp)r(ect)h(the)f(optimistic)d(soft)o(w)o(are)-75 939 y(solu\ tion)i(to)g(contin)n(ue)h(its)g(dominance.)j(F)l(or)d(in)o(terlo)q(c)o(k)o (ed)g(in-)-75 984 y(structions)d(to)g(outp)q(erform)e(optimistic)g(soft)o(w)n (are)i(techniques)-75 1030 y(on)19 b(unipro)q(cessors,)j(they)d(m)n(ust)h(b)q (e)f(implemen)l(ted)h(so)f(that)-75 1075 y(they)14 b(exploit)g(the)g(simpler) f(single)g(pro)r(cessor)i(case.)-33 1122 y(The)i(table)g(demonstrates)h(that) f(one)h(should)f(not)g(neces-)-75 1167 y(sarily)g(rely)i(on)e(an)h(architectu\ re)h(and)f(memory)e(system)i(to)-75 1213 y(pro)o(vide)e(functions)g(that)g (ma)m(y)g(b)q(e)h(pro)n(vided)f(more)f(cheaply)-75 1258 y(with)e(a)f(com)n (bination)g(of)g(op)q(erating)h(system,)f(compiler,)g(and)-75 1303 y(run)o (time)h(supp)q(ort.)-75 1444 y fn(7)69 b(Related)21 b(w)n(ork)-75 1533 y fr (The)29 b(T)m(rellis/Owl)f(ob)r(ject-orien)o(ted)i(language)d([Moss)i(&)-75 1579 y(Kohler)16 b(87])f(used)i(optimistic)c(synchronization)i(techniques)-75 1624 y(similar)20 b(to)j(those)g(describ)r(ed)h(in)e(this)h(pap)q(er.)45 b (The)23 b(Owl)-75 1669 y(run)o(time)d(system)h(pro)o(vided)g(concurrency)i (among)c(several)-75 1715 y(threads)f(sharing)f(a)g(single)g(VMS)g(pro)q(cess\ ,)j(and)d(used)h(soft-)-75 1760 y(w)o(are)13 b(in)o(terrupts)h(from)e(VMS)h (to)g(driv)n(e)h(its)f(m)m(ultiplexing.)j(It)-75 1805 y(pro)o(vided)e(atomici\ t)m(y)g(for)f(its)h(o)o(wn)g(needs)h(and)f(those)h(of)e(user)-75 1851 y(progr\ ams)g(b)o(y)i(bac)o(king)f(out)g(of)g(certain)h(registered)i(run)o(time)-75 1896 y(routines,)12 b(and)f(b)o(y)g(em)n(ulating)f(forw)o(ard)h(through)h(des\ ignated)-75 1941 y(sequences.)19 b(The)11 b(most)e(importan)n(t)i(di\013erenc\ e)h(b)q(etw)n(een)g(Owl)-75 1987 y(and)h(the)g(w)o(ork)g(describ)s(ed)g(in)g (this)g(pap)q(er)g(is)g(our)g(in)o(tegration)-75 2032 y(of)f(restartable)h (atomic)d(sequences)15 b(with)d(the)h(op)q(erating)f(sys-)-75 2077 y(tem)h (k)o(ernel.)-33 2125 y(User-lev)o(el)i(detection)g(and)f(restart)i(is)e(simil\ ar)e(to)i(the)h(ap-)-75 2170 y(proac)o(h)h(tak)o(en)g(in)g([Anderson)h(et)g (al.)24 b(92])15 b(to)h(supp)q(ort)h(user-)-75 2215 y(lev)o(el)c(thread)i(man\ agemen)l(t)f(on)g(shared)h(memory)c(m)m(ultipro-)-75 2261 y(cessors.)31 b(In) 17 b(that)h(system,)f(when)h(a)g(thread)g(is)f(preempted)-75 2306 y(inside)d (a)g(critical)g(section,)h(it)f(is)g(immediately)d(resumed)k(not)-75 2351 y (where)g(it)f(left)g(o\013,)f(but)i(within)e(co)q(de)i(that)f(giv)n(es)h(the) g(thread)-75 2397 y(managemen)l(t)k(system)g(the)g(opp)q(ortunit)o(y)g(to)f (recov)o(er)h(from)-75 2442 y(the)13 b(preemption.)k(This)c(mac)n(hinery)g (is)g(su\016cien)o(t)g(for)f(imple-)-75 2487 y(men)n(ting)k(restartable)i(ato\ mic)d(sequences)k(on)e(a)g(uniproces-)-75 2533 y(sor.)-33 2580 y(The)c(In)o (tel)h(i860)e(pro)q(cessor)j([In)o(tel860)d(89])h(pro)o(vides)h(hard-)-75 2625 y(w)o(are)j(supp)r(ort)g(for)g(restartable)h(sequences.)29 b(A)17 b(thread)h (b)q(e-)1013 620 y(gins)12 b(a)g(m)m(ulti-instruction)g(atomic)f(sequence)j (with)f(a)f(sp)q(ecial)1013 665 y(instruction)g(that)g(sets)h(a)f(bit)g(in)f (the)i(pro)q(cessor)h(status)f(w)n(ord,)1013 710 y(disables)c(in)n(terrupts,) j(and)d(locks)g(the)h(bus.)17 b(The)10 b(bit)f(is)g(cleared)1013 756 y(and)14 b(the)h(bus)f(lo)q(c)o(k)g(is)h(automatically)c(released)k(on)f(the)h(next) 1013 801 y(write)f(to)f(memory)-5 b(,)13 b(after)h(32)f(cycles,)i(or)f(on)f (a)h(pro)q(cessor)i(ex-)1013 846 y(ception.)k(The)c(release)g(on)e(write)h (co)o(v)o(ers)h(the)f(common)d(case)1013 892 y(of)g(a)i(successful)h(read-mod\ ify-write)e(sequence.)20 b(The)13 b(k)o(ernel)1013 937 y(m)m(ust)19 b(c)o(hec\ k)f(the)h(bit)e(on)h(every)g(transfer)h(from)e(the)h(k)o(ernel)1013 982 y(to) g(user)i(lev)o(el.)32 b(If)18 b(the)i(bit)e(is)h(set,)h(the)f(k)o(ernel)g(m)n (ust)g(bac)o(k)1013 1028 y(the)e(thread)h(up)g(to)f(the)h(sp)r(ecial)f(instru\ ction.)28 b(Despite)18 b(the)1013 1073 y(i860's)13 b(hardw)o(are)i(supp)q(ort) g(for)f(restartable)i(sequences)h(\(the)1013 1118 y(bit)i(in)g(the)h(pro)r (cessor)h(status)f(w)o(ord)g(eliminates)e(the)i(need)1013 1164 y(to)e(p)q(erf\ orm)g(explicit)g(registration)h(or)f(instruction)h(stream)1013 1209 y(insp)q (ection)h(after)g(ev)o(ery)h(con)o(text)f(switc)o(h\),)h(it)f(o\013ers)h(litt\ le)1013 1254 y(p)q(erformance)c(adv)m(an)o(tage)g(o)o(v)o(er)h(soft)o(w)n(are) g(techniques)g(on)f(a)1013 1300 y(uniprocessor)f(\(see)f(T)m(able)e(4\).)1013 1492 y fn(8)69 b(Conclusions)1013 1600 y fr(Restartable)25 b(atomic)e(sequenc\ es)k(represen)q(t)e(a)g(\\common)1013 1645 y(case")14 b(approac)o(h)g(to)g (m)m(utual)g(exclusion)g(on)f(a)h(unipro)q(cessor.)1013 1690 y(In)j(the)i(com\ mon)c(case,)k(an)f(atomic)e(op)q(eration)i(runs)g(unin-)1013 1736 y(terrupted\ .)26 b(The)16 b(uncommon)e(case)j(can)f(b)q(e)h(detected)h(after)1013 1781 y (it)13 b(o)q(ccurs)j(and)e(can)h(b)q(e)f(handled)h(b)o(y)f(means)f(of)h(a)g (simple)e(re-)1013 1826 y(co)o(v)n(ery)k(pro)r(cess.)24 b(As)16 b(such,)f(res\ tartable)i(atomic)c(sequences)1013 1872 y(are)j(appropriate)g(for)g(uniproces\ sors)i(that)e(do)g(not)g(supp)r(ort)1013 1917 y(memory-i)o(n)l(terlo)r(c)o (k)o(ed)e(atomic)e(instructions.)19 b(Moreo)o(v)o(er,)14 b(on)1013 1962 y(pro) q(cessors)26 b(that)f(do)f(ha)n(v)o(e)h(hardw)o(are)g(supp)q(ort)g(for)f(syn-) 1013 2008 y(c)o(hronization,)12 b(b)q(etter)j(p)q(erformance)e(ma)m(y)g(b)q (e)h(p)q(ossible)f(with)1013 2053 y(restartable)i(atomic)d(sequences.)1013 2245 y fn(Ac)n(kno)n(wledgemen)n(ts)1013 2353 y fr(Ric)n(hard)g(Dra)n(v)o(es,) g(Hank)g(Levy)m(,)f(Chris)h(Maeda,)g(Dan)f(Sto)q(dol-)1013 2398 y(sky)18 b (and)h(T)m(erri)g(W)l(atson)g(pro)o(vided)f(v)n(aluable)g(feedback)g(on)1013 2444 y(earlier)k(drafts)g(of)g(this)g(pap)q(er.)44 b(The)22 b(use)h(of)f(rest\ artable)1013 2489 y(atomic)16 b(sequences)21 b(in)d(T)m(aos)g(b)q(ene\014tted) i(from)d(discussions)1013 2534 y(with)e(Butler)h(Lampson)e(and)h(Mik)n(e)h (Burrows.)22 b(The)16 b(system)1013 2580 y(structuring)d(ideas)g(in)g(Section) g(4)g(w)o(ere)h(clari\014ed)f(during)f(dis-)1013 2625 y(cussions)i(with)g(Jer\ ry)h(Saltzer.)p eop %%Page: 12 11 bop -75 -33 a fn(References)-75 45 y fb([Accetta)13 b(et)f(al.)i(86])20 b (Accetta,)d(M.)f(J.,)g(Baron,)i(R.)e(V.,)g(Bolosky)o(,)117 87 y(W.,)d(Golub,) h(D.)f(B.,)g(Rashid,)h(R.)f(F.,)f(T)m(ev)n(anian,)i(Jr.,)117 128 y(A.,)j(and) g(Y)m(oung,)h(M.)f(W.)29 b(Mac)o(h:)c(A)16 b(New)g(Kernel)117 170 y(F)m(ounda\ tion)d(for)e(UNIX)f(Developmen)q(t.)j(In)e fa(Pr)n(o)n(c)n(e)m(e)n(d-)117 211 y(ings)i(of)h(the)g(Summer)g(1986)g(USENIX)e(Confer)m(enc)m(e)p fb(,)117 253 y (pages)i(93{113,)f(July)h(1986.)-75 309 y([Anderson)g(et)f(al.)g(89])21 b(And\ erson,)11 b(T.,)e(Lazowsk)n(a,)h(E.,)g(and)g(Levy)n(,)117 350 y(H.)40 b(The) 20 b(P)o(erformance)i(Implications)h(of)e(Thread)117 392 y(Managemen)q(t)g (Alternativ)q(es)g(for)h(Shared-Memory)117 433 y(Multipro)s(cessors.)30 b fa (IEEE)18 b(T)m(r)o(ansaction)o(s)d(on)h(Com-)117 475 y(puters)p fb(,)11 b(38\ \(12\):1631{1644,)k(Decem)o(b)q(er)e(1989.)-75 530 y([Anderson)h(et)f(al.)g (91])21 b(Anderson,)c(T.,)f(Levy)n(,)g(H.,)g(Bershad,)i(B.,)117 572 y(and)d (Lazowsk)n(a,)f(E.)22 b(The)15 b(In)o(teraction)g(of)g(Arc)o(hitec-)117 614 y (ture)e(and)g(Op)r(erating)g(System)h(Design.)k(In)12 b fa(Pr)n(o)n(c)n(e)m (e)n(d-)117 655 y(ings)i(of)i(the)e(F)m(ourth)h(Symp)m(osium)g(on)g(A)n(r)n (chite)m(ctur)m(al)117 697 y(Supp)l(ort)f(for)g(Pr)n(o)n(gr)m(amming)g(L)n (anguages)d(and)i(Op)n(er-)117 738 y(ating)f(Systems)g(\(ASPLOS\))p fb(,)f (April)j(1991.)-75 794 y([Anderson)g(et)f(al.)g(92])21 b(Anderson,)16 b(T.)e (E.,)h(Bershad,)h(B.)f(N.,)g(La-)117 835 y(zo)o(wsk)n(a,)d(E.)g(D.,)g(and)h (Levy)n(,)f(H.)f(M.)16 b(Sc)o(heduler)e(Acti-)117 877 y(v)n(ations:)20 b(E\ \013ectiv)q(e)14 b(Kernel)h(Supp)r(ort)f(for)g(the)g(User-)117 919 y(Lev)o (el)g(Management)f(of)f(P)o(arallelism.)19 b fa(A)o(CM)14 b(T)n(r)n(ans-)117 960 y(actions)j(on)h(Computer)g(Systems)p fb(,)g(9\(1\),)i(F)m(ebruary)117 1002 y(1992.)-75 1057 y([Bershad)14 b(et)f(al.)g(88])21 b(Bershad,)e(B.)e(N.,) g(Lazowsk)n(a,)h(E.)f(D.,)h(and)117 1099 y(Levy)m(,)g(H.)e(M.)28 b(PRESTO:)17 b(A)g(System)g(for)g(Ob)r(ject-)117 1141 y(Oriented)30 b(P)o(arallel)j(Progra\ mming.)70 b fa(Softwar)m(e:)117 1182 y(Pr)n(actic)m(e)11 b(and)g(Exp)m(erienc) m(e)p fb(,)f(18\(8\):713{732,)j(August)117 1224 y(1988.)-75 1279 y([Bershad)h (et)f(al.)g(92])21 b(Bershad,)28 b(B.)c(N.,)i(Dra)o(v)o(es,)h(R.)d(P)m(.,)j (and)117 1321 y(F)m(orin,)c(A.)40 b(Using)21 b(Microb)s(enc)o(hmarks)h(to)e (Ev)o(alu-)117 1362 y(ate)15 b(System)g(P)o(erformance.)23 b(In)14 b fa(Pr)o (o)m(c)n(e)n(e)m(dings)g(of)h(the)117 1404 y(Thir)n(d)d(Workshop)e(on)h(Works\ tation)e(Op)n(er)n(ating)h(Sys-)117 1446 y(tems)p fb(,)i(April)i(1992.)-75 1501 y([Birrell)h(91])21 b(Birrell,)j(A.)39 b fa(A)n(n)20 b(Intr)n(o)m(ductio\ n)e(to)i(Pr)o(o)m(gr)n(amming)117 1543 y(with)13 b(Thr)o(e)m(ads)p fb(.)j(Pre\ n)o(tice)e(Hall,)g(1991.)-75 1599 y([Bose)f(et)g(al.)g(89])21 b(Bose,)36 b (S.,)f(Clarke,)g(E.,)g(Long,)h(D.,)f(and)117 1640 y(Micha)o(ylov,)16 b(S.)24 b (P)o(arthenon:)f(A)15 b(P)o(arallel)j(Theorem)117 1682 y(Pro)o(ver)12 b(for)g (Non-Horn)h(Clauses.)k(In)c fa(Pr)n(o)n(c)m(e)n(e)n(dings)e(of)117 1723 y(the) f(F)m(ourth)f(A)n(nnual)g(Symp)m(osium)h(on)f(L)n(o)n(gic)h(in)f(Com-)117 1765 y(puter)k(Scienc)-5 b(e)p fb(,)13 b(1989.)-75 1820 y([Cheriton)h(88])21 b(Che\ riton,)k(D.)c(R.)44 b(The)22 b(V)f(Distributed)k(Sys-)117 1862 y(tem.)e fa (Communic)m(ations)14 b(of)h(the)g(A)n(CM)p fb(,)h(31\(3\):314{)117 1904 y (333,)d(March)g(1988.)-75 1959 y([Co)q(op)q(er)g(&)g(Dra)o(v)o(es)h(88])20 b (Co)q(op)r(er,)k(E.)e(C.)g(and)h(Dra)o(v)o(es,)i(R.)d(P)m(.)117 2001 y(C)d (threads.)36 b(T)m(ec)o(hnical)21 b(Rep)r(ort)e(CMU-CS-88-54,)117 2042 y(Sc)o (ho)r(ol)g(of)g(Computer)g(Science,)i(Carnegie)f(Mellon)117 2084 y(University) m(,)12 b(F)m(ebruary)i(1988.)-75 2140 y([Dijkstra)g(68a])21 b(Dijkstra,)12 b (E.)e(W.)j(The)e(Structure)g(of)g(the)f(\\THE")117 2181 y(Multiprogrammi)q (ng)k(System.)g fa(Communic)m(ations)c(of)117 2223 y(the)j(A)n(CM)p fb(,)h (11\(5\),)f(Ma)o(y)g(1968.)-75 2278 y([Dijkstra)h(68b])21 b(Dijkstra,)13 b (E.)e(W.)16 b fa(Co)n(op)m(er)n(ating)11 b(Se)m(quential)f(Pr)n(o-)117 2320 y (c)n(esses)p fb(,)22 b(pages)g(43{112.)44 b(Academic)23 b(Press,)h(New)117 2362 y(Y)m(ork,)13 b(1968.)-75 2417 y([Glew)g(&)g(Hwu)f(91])21 b(Glew,)15 b (A.)f(and)h(Hwu,)f(W.)22 b(A)14 b(F)m(eature)h(T)l(ax-)117 2459 y(onomy)20 b (and)i(Survey)e(of)h(Synchronization)i(Primi-)117 2500 y(tive)14 b(Implementa\ tions.)21 b(T)m(ec)o(hnical)16 b(Rep)q(ort)e(UILU-)117 2542 y(ENG-91-2211,)25 b(Cen)o(ter)d(for)g(Reliable)j(and)e(High-)117 2583 y(P)o(erformance)c(Comput\ ing,)h(University)e(of)g(Illinois)117 2625 y(at)13 b(Urbana-Champaign,)i(F)m (ebruary)f(1991.)1013 -47 y([Golub)g(et)e(al.)i(90])21 b(Golub,)30 b(D.,)e (Dean,)h(R.,)g(F)m(orin,)g(A.,)f(and)1205 -5 y(Rashid,)13 b(R.)i(Unix)e(as)f (an)g(Application)i(Program.)i(In)1205 36 y fa(Pr)n(o)m(c)n(e)n(e)n(dings)11 b (of)h(the)f(Summer)i(1990)e(USENIX)g(Con-)1205 78 y(fer)m(enc)m(e)p fb(,)h (pages)i(87{95,)f(June)h(1990.)1013 136 y([Herlihy)f(91])21 b(Herlihy)m(,)41 b (M.)85 b(W)m(ait-free)36 b(Synchronization.)1205 177 y fa(A)n(CM)12 b(T)n(r)n (ansactions)c(on)j(Pr)n(o)n(gr)m(amming)g(L)n(anguages)p fb(,)1205 219 y(13\(\ 1\),)i(Jan)o(uary)g(1991.)1013 277 y([In)n(tel386)h(90])21 b fa(386)c(Pr)n (o)n(gr)n(ammer's)g(R)n(efer)n(enc)m(e)g(Manual)p fb(.)30 b(In)o(tel,)1205 319 y(Mt.)12 b(Prosp)r(ect,)h(IL,)f(1990.)1013 377 y([In)n(tel860)i(89])21 b fa (i860)10 b(64-bit)e(Micr)n(opr)n(o)m(c)n(essor)i(Pr)n(o)n(gr)m(ammer's)h(R)n (ef-)1205 418 y(er)m(enc)m(e)j(Manual)p fb(.)h(1989.)1013 477 y([Kane)d(87]) 33 b(Kane,)27 b(G.)50 b fa(MIPS)24 b(R2000)e(RISC)i(A)o(r)n(chite)m(ctur)m (e)p fb(.)1205 518 y(Pren)o(tice)14 b(Hall,)f(Englewo)r(o)q(d)g(Cli\013s,)h (N.J.,)e(1987.)1013 576 y([Lamp)q(ort)h(87])21 b(Lamp)q(ort,)e(L.)30 b(A)18 b (F)l(ast)g(Mutual)h(Exclusion)i(Al-)1205 618 y(gorithm.)e fa(A)n(CM)c(T)m(r)o (ansaction)o(s)c(on)i(Computer)g(Sys-)1205 659 y(tems)p fb(,)e(5\(1\):1{11,)j (F)m(ebruary)g(1987.)1013 717 y([Leonard)f(87])21 b(Leonard,)28 b(T.)52 b fa (V)-5 b(AX)24 b(A)n(r)n(chite)m(ctur)m(e)g(R)n(efer)m(enc)m(e)1205 759 y(Manu\ al)p fb(.)15 b(Digital)g(Equipmen)q(t)e(Corp)q(oration,)h(1987.)1013 817 y ([Moss)f(&)f(Kohler)i(87])21 b(Moss,)13 b(J.)f(and)i(Kohler,)g(W.)j(Concurren\ cy)1205 859 y(F)l(eatures)f(for)f(the)g(T)m(rellis/Owl)i(Language.)25 b(In)15 b fa(Eu-)1205 900 y(r)n(op)m(e)n(an)10 b(Confer)m(enc)m(e)h(on)f(Obje)n(ct-Or\ iente)l(d)h(Pr)n(o)m(gr)n(am-)1205 942 y(ming)p fb(,)i(June)i(1987.)22 b(App) r(ears)14 b(in)i(Springer-V)n(erlag's)1205 983 y(Lecture)d(Notes)g(in)h(Compu\ ter)f(Science)h(#276.)1013 1042 y([Motorola)g(88100)f(88])21 b fa(MCS)38 b (88100)d(RISC)h(Micr)n(opr)n(o)n(c)m(essor)1205 1083 y(User's)12 b(Manual)p fb (.)j(Pho)r(enix,)f(AZ,)e(1988.)1013 1141 y([Mullender)j(et)d(al.)i(90])21 b (Mullender,)27 b(S.)c(J.,)i(v)n(an)e(Rossum,)k(G.,)1205 1183 y(T)l(anenbaum,) 21 b(A.)d(S.,)i(v)n(an)f(Renesse,)i(R.,)f(and)f(v)n(an)1205 1224 y(Sta)o(v)o (eren,)12 b(H.)h(Amo)q(eba:)j(A)11 b(Distributed)i(Op)r(erating)1205 1266 y (System)k(for)f(the)h(1990s.)28 b fa(IEEE)17 b(Computer)f(Maga-)1205 1307 y (zine)p fb(,)11 b(23\(5\):44{54,)i(May)g(1990.)1013 1366 y([P)n(eterson)h(81]) 21 b(P)o(eterson,)10 b(G.)g(Myths)g(Ab)q(out)g(the)f(Mutual)i(Exclu-)1205 1407 y(sion)17 b(Problem.)29 b fa(Information)15 b(Pr)n(o)n(c)n(essing)g(L)n(etter\ s)p fb(,)1205 1449 y(12\(1\),)e(June)g(1981.)1013 1507 y([Ro)o(vner)g(et)g (al.)g(85])21 b(Ro)o(vner,)15 b(P)m(.,)f(Levin,)i(R.,)e(and)h(Wick,)f(J.)21 b (On)1205 1548 y(Extending)f(Mo)q(dula-2)g(for)e(Building)k(Large,)d(In)o(te-) 1205 1590 y(grated)f(Systems.)33 b(T)m(ec)o(hnical)20 b(Rep)r(ort)e(#)g(3,)h (Digi-)1205 1632 y(tal)14 b(Equipmen)q(t)f(Corp)q(oration's)i(Systems)f(Resea\ rch)1205 1673 y(Cen)o(ter,)e(P)o(alo)i(Alto,)f(California,)i(Jan)o(uary)f(198\ 5.)1013 1731 y([Rozier)f(et)g(al.)g(88])21 b(Rozier,)14 b(M.,)e(Abrossimo)q (v,)h(V.,)e(Armand,)j(F.,)1205 1773 y(Boule,)27 b(I.,)f(Giend,)i(M.,)e(Guille\ mon)r(t,)g(M.,)g(Her-)1205 1814 y(rmann,)31 b(F.,)f(Leonard,)h(P)m(.,)f(Langl\ ois,)j(S.,)d(and)1205 1856 y(Neuhauser,)16 b(W.)24 b(The)15 b(Chorus)h(Distri\ buted)i(Op)q(er-)1205 1897 y(ating)c(System.)j fa(Computing)12 b(Systems)p fb (,)f(1\(4\),)i(1988.)1013 1956 y([Sat)o(y)o(anarany)o(any)o(an)g(et)g(al.)g (85])21 b(Saty)o(anarany)o(any)o(an,)1205 1997 y(M.,)d(Ho)o(w)o(ard,)i(J.,)e (Nichols,)i(D.,)f(Sideb)s(otham,)g(R.,)1205 2039 y(and)14 b(Sp)q(ector,)g(A.) j(The)c(ITC)g(Distributed)j(File)e(Sys-)1205 2080 y(tem:)22 b(Principles)d (and)e(Design.)28 b(In)16 b fa(Pr)n(o)n(c)m(e)n(e)n(dings)f(of)1205 2122 y (the)9 b(10th)f(A)o(CM)j(Symp)m(osium)e(on)g(Op)n(er)n(ating)g(Systems)1205 2163 y(Principles)p fb(,)h(pages)j(35{50,)h(Decem)o(b)r(er)f(1985.)1013 2222 y ([Thac)n(ker)g(et)f(al.)i(88])20 b(Thack)o(er,)11 b(C.)g(P)m(.,)f(Stew)o(art,) i(L.)e(C.,)h(and)h(Sat-)1205 2263 y(terth)o(w)n(aite,)i(Jr.,)e(E.)g(H.)17 b (Fire\015y:)h(A)13 b(Multipro)s(cessor)1205 2305 y(W)m(orkstation.)f fa(IEEE) d(T)n(r)n(ansactions)d(on)j(Computers)p fb(,)1205 2346 y(37\(8\):909{920,)14 b (August)f(1988.)1013 2404 y([W)l(eiser)h(et)f(al.)g(89])21 b(W)m(eiser,)c(M.,) e(Demers,)h(A.,)f(and)h(Hauser,)g(C.)1205 2446 y(The)j(P)o(ortable)h(Common)g (Runtime)g(Approac)o(h)g(to)1205 2487 y(In)o(terop)q(erabilit)r(y.)50 b(In)23 b fa(Pr)o(o)m(c)n(e)n(e)m(dings)f(of)i(the)e(12th)1205 2529 y(A)n(CM)e(Symp)m (osium)d(on)h(Op)n(er)n(ating)f(Systems)g(Prin-)1205 2571 y(ciples)p fb(,)10 b (pages)k(114{122,)g(Decem)o(b)r(er)f(1989.)p eop %%Trailer end %%EOF