Att test-och-set protokoll för lås överträffa köning protokoll vid låg tvist, medan motsatsen är sant vid hög tvist. I detta dokument undersöks reaktiva synkroniseringsalgoritmer som dynamiskt väljer protokoll som svar på tvistenivån. Vi beskriver reaktiva algoritmer för spinnlås och hämtning-och-op som väljer bland flera delade minnes- och meddelandepasseringsprotokoll. Dynamiskt välja protokoll innebär en utmaning: en reaktiv algoritm måste välja och ändra protokoll effektivt, och måste möjliggöra möjligheten att flera processer kan köra olika protokoll samtidigt. Vi beskriver begreppet konsensusobjekt som de reaktiva algoritmerna använder för att bevara korrektheten inför dynamiska protokolländringar. Experimentella mätningar visar att reaktiva algoritmer utför nära det bästa statiska valet av protokoll på alla stridsnivåer. Med blandade stridsnivåer överträffar dessutom reaktiva algoritmer passiva algoritmer med fasta protokoll, förutsatt att stridsnivåer inte ändras alltför ofta. Mätningar av flera parallella applikationer visar att reaktiva algoritmer resulterar i blygsamma prestandavinster för spinnlås och betydande vinster för hämta-och-op. Delade-minnesmultiprocessorer ger vanligtvis läs-modifiera-skriva hårdvara primitiver för processsynkronisering, vilket lämnar syntesen av högre nivå synkronisering operationer till programvara synkronisering algoritmer. Men synkroniseringsalgoritmer som är effektiva över ett brett spektrum av applikationer är svåra att designa eftersom deras prestanda beror på run-time faktorer som är svåra att förutsäga, såsom tviste- och väntetider. I synnerhet har en synkroniseringsalgoritm ett val av protokoll för att genomföra synkroniseringen operation, och ett val av tillstånd att co y utan avgift hela eller en del av detta material [beviljas t på kopiorna inte görs eller distribueras för direkta kommersiella fördelar, ACM copyright meddelande och titeln på publikationen och dess datum visas, och meddelande ges att kopiering är genom tillstånd av Association of Computing Machinery. För att kopiera på annat sätt, eller för att återpublicera, krävs en avgift och/eller ett särskilt tillstånd. Väntar mekanismer för att vänta på synkronisering förseningar. Till exempel, kandidatprotokoll för lås inkluderar test-och-set och köning protokoll, och väntemekanismer inkluderar spinning och blockering. Ofta beror det bästa protokollet på tvistenivån, medan den bästa väntemekanismen beror på väntetiden. För robust prestanda väljer en reaktiv synkroniseringsalgoritm dynamiskt protokoll och väntemekanismer som svar på run-time-faktorer. Figur 1 visar komponenterna i en reaktiv synkroniseringsalgoritm. Det bryts ner i en protokollvalsalgoritm och väntar på algoritm. Valalgoritmen för protokollet är ansvarig för att välja ett protokoll för att genomföra synkroniseringsoperationen, medan den väntande algoritmen är ansvarig för att välja väntande mekanismer för att vänta på synkronisering latenser. Detta dokument fokuserar på reaktiv synkronisering algoritmer som väljer protokoll dynamiskt, men som antar spin väntar som en fast väntemekanism. Tidigare forskning [9, 14] har redan visat nyttan av att dynamiskt välja väntemekanismer. Men så vitt vi vet har det inte gjorts någon experimentell forskning om genomförbarheten och prestandafördelarna med att dynamiskt välja synkroniseringsprotokoll. Vi lämnar en utredning av samtidigt välja protokoll och vänta algoritmer som framtida arbete. Som ett exempel på den potentiella nyttan av att dynamiskt välja protokoll, överväga avvägningen mellan test-and-set och köa protokoll för spin lås. Test-and-set protokollet förvärvar ett lås med en test-and-set instruktion och släpper låset med en butik instruktion. Även om det är ett enkelt och effektivt protokoll i avsaknad av tvist, dess prestanda försämras drastiskt under hög strid. Ett botemedel är ett köprotokoll som konstruerar en programvara kö av servitörer för att minska tvistefrågan. Köandet kommer dock till priset av en högre latens i avsaknad av tvist [2, 16]. Det rätta valet mellan de två protokollen beror på vilken grad av tvist som låset upplever.
Reactive Lock REF är ett biblioteksbaserat adaptivt tillvägagångssätt som väljer den bästa synkroniseringsalgoritmen under olika stridsnivåer.
Reactive synchronization algorithms for multiprocessors
{'venue': 'ASPLOS VI', 'journal': None, 'mag_field_of_study': ['Computer Science']}