Samtidig datastruktur

Inom datavetenskap är en samtidig datastruktur ett speciellt sätt att lagra och organisera data för åtkomst av flera datortrådar ( eller processer ) på en dator.

Historiskt har sådana datastrukturer använts på uniprocessor -maskiner med operativsystem som stödde flera datortrådar (eller processer ). Termen concurrency fångade multiplexeringen /interfolieringen av trådarnas operationer på data av operativsystemet, även om processorerna aldrig utfärdade två operationer som fick åtkomst till data samtidigt.

Idag, när datorarkitekturer med flera processorer som tillhandahåller parallellitet blir den dominerande datorplattformen (genom spridningen av flerkärniga processorer), har termen kommit att stå huvudsakligen för datastrukturer som kan nås av flera trådar som faktiskt kan komma åt data samtidigt eftersom de körs på olika processorer som kommunicerar med varandra. Den samtidiga datastrukturen (ibland även kallad delad datastruktur ) anses vanligtvis ligga i en abstrakt lagringsmiljö som kallas delat minne , även om detta minne fysiskt kan implementeras som antingen en "tätt kopplad" eller en distribuerad samling av lagringsmoduler.

Grundläggande principer

Samtidiga datastrukturer, avsedda för användning i parallella eller distribuerade datormiljöer, skiljer sig från "sekventiella" datastrukturer, avsedda för användning på en uni-processor maskin, på flera sätt. Mest anmärkningsvärt är att man i en sekventiell miljö specificerar datastrukturens egenskaper och kontrollerar att de är korrekt implementerade genom att tillhandahålla säkerhetsegenskaper . I en samtidig miljö ska specifikationen även beskriva livskraftsegenskaper som en implementering måste ge. Säkerhetsegenskaper brukar säga att något dåligt aldrig händer, medan livlighetsegenskaper säger att något bra fortsätter att hända. Dessa egenskaper kan uttryckas, till exempel med hjälp av linjär temporär logik .

Typen av krav på livlighet tenderar att definiera datastrukturen. Metodanropen kan vara blockerande eller icke -blockerande . Datastrukturer är inte begränsade till den ena eller den andra typen och kan tillåta kombinationer där vissa metodanrop är blockerande och andra är icke-blockerande (exempel finns i Java samtidighetsprogramvarubibliotek ) .

Säkerhetsegenskaperna hos samtidiga datastrukturer måste fånga deras beteende med tanke på de många möjliga sammanflätningarna av metoder som anropas av olika trådar. Det är ganska intuitivt att specificera hur abstrakta datastrukturer beter sig i en sekventiell miljö där det inte finns några interfolieringar. Därför specificerar många vanliga tillvägagångssätt för att argumentera för säkerhetsegenskaperna för en samtidig datastruktur (såsom serialiserbarhet , linjärisering , sekventiell konsistens och vilande konsistens) strukturens egenskaper sekventiellt och mappar dess samtidiga exekveringar till en samling sekventiella.

För att garantera egenskaperna för säkerhet och livlighet måste samtidiga datastrukturer vanligtvis (men inte alltid) tillåta trådar att nå konsensus om resultaten av deras samtidiga dataåtkomst- och modifieringsförfrågningar. För att stödja en sådan överenskommelse implementeras samtidiga datastrukturer med hjälp av speciella primitiva synkroniseringsoperationer (se synkroniseringsprimitiver ) tillgängliga på moderna multiprocessormaskiner som tillåter flera trådar att nå konsensus. Denna konsensus kan uppnås på ett blockerande sätt genom att använda lås , eller utan lås, i vilket fall det är icke-blockerande . Det finns ett brett spektrum av teorier om design av samtidiga datastrukturer (se bibliografiska referenser).

Design och implementering

Samtidiga datastrukturer är betydligt svårare att designa och verifiera som korrekta än deras sekventiella motsvarigheter.

Den primära källan till denna ytterligare svårighet är samtidighet, som förvärras av det faktum att trådar måste ses som helt asynkrona: de är föremål för operativsystemförbud, sidfel, avbrott och så vidare.

På dagens maskiner påverkar layouten av processorer och minne, layouten av data i minnet, kommunikationsbelastningen på de olika elementen i multiprocessorarkitekturen alla prestanda. Dessutom finns det en spänning mellan korrekthet och prestanda: algoritmiska förbättringar som försöker förbättra prestanda gör det ofta svårare att designa och verifiera en korrekt datastrukturimplementering.

Ett nyckelmått för prestanda är skalbarhet, fångad av snabbheten i implementeringen. Speedup är ett mått på hur effektivt programmet använder maskinen den körs på. På en maskin med P-processorer är hastigheten förhållandet mellan strukturernas exekveringstid på en enskild processor och dess exekveringstid på P-processorer. Helst vill vi ha linjär speedup: vi skulle vilja uppnå en speedup på P när vi använder P-processorer. Datastrukturer vars hastighet ökar med P kallas skalbara . I vilken utsträckning man kan skala prestandan hos en samtidig datastruktur fångas av en formel känd som Amdahls lag och mer förfinade versioner av den som Gustafsons lag .

En nyckelfråga med prestandan för samtidiga datastrukturer är nivån på minneskonflikt: overheaden i trafik till och från minnet som ett resultat av att flera trådar samtidigt försöker komma åt samma platser i minnet. Det här problemet är mest akut med blockeringsimplementeringar där lås styr åtkomst till minne. För att skaffa ett lås måste en tråd upprepade gånger försöka ändra den platsen. På en cache-koherent multiprocessor (en där processorer har lokala cachar som uppdateras av hårdvara för att hålla dem konsekventa med de senaste lagrade värdena) resulterar detta i långa väntetider för varje försök att ändra platsen och förvärras av det extra minnet trafik i samband med misslyckade försök att skaffa låset.

Se även

Vidare läsning

  • Nancy Lynch "Distributed Computing"
  • Hagit Attiya och Jennifer Welch "Distributed Computing: Fundamentals, Simulations And Advanced Topics, 2nd Ed"
  • Doug Lea , "Samtidig programmering i Java: Designprinciper och mönster"
  • Maurice Herlihy och Nir Shavit , "Konsten att programmera flera processorer"
  • Mattson, Sanders och Massingil "Patterns for Parallel Programming"

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Concurrent_data_structure&oldid=1140645699 "