Samtidighet (datavetenskap)

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 24 juli 2022; kontroller kräver 2 redigeringar .

Inom datavetenskap är parallellism en egenskap hos system där flera beräkningar utförs samtidigt, och därigenom eventuellt interagerar med varandra. Beräkningar kan köras på flera kärnor på samma chip med förebyggande tidsdelningstrådar på samma processor, eller köras på fysiskt separata processorer . Ett antal matematiska modeller har utvecklats för att utföra parallella beräkningar, inklusive Petri-nät , processkalkyl , parallella slumpmässiga beräkningsmodeller och aktörsmodeller .

Notera  - I ryskspråkig litteratur blandas termerna "parallellism" och "konkurrenskraft" ofta ihop. . Både termerna betyder samtidighet av processer, men den första är på den fysiska nivån (parallell exekvering av flera processer, som endast syftar till att öka exekveringshastigheten genom användning av lämpligt hårdvarustöd), och den andra den ena är på den logiska nivån ( systemdesignparadigm som identifierar processer som oberoende, vilket bland annat gör att de kan köras fysiskt parallellt, men som främst syftar till att förenkla skrivandet av flertrådade program och öka deras stabilitet).

Problem

Eftersom beräkningar i parallella system interagerar med varandra kan antalet möjliga exekveringsvägar vara extremt stort, och det resulterande resultatet kan bli icke-deterministiskt (obestämt). Samtidig användning av delade resurser kan vara en källa till icke-determinism, vilket leder till problem som dödläge eller resurssvält. [ett]

Att bygga parallella system kräver att man hittar tillförlitliga metoder för att koordinera pågående processer, kommunicera, allokera minne och schemalägga för att minimera svarstiden och öka genomströmningen.

Teori

Teorin om parallell beräkning är ett aktivt forskningsområde inom teoretisk datavetenskap . Ett av de första förslagen i denna riktning var Carl Adam Petris framstående arbete om Petri - nät i början av 1960-talet. Under de efterföljande åren utvecklades ett brett utbud av formalismer för att modellera och beskriva parallella system.

Modeller

Ett stort antal formella metoder har redan utvecklats för att modellera och förstå hur parallella system fungerar, inklusive: [2]

Vissa av dessa samtidighetsmodeller är främst avsedda för slutlednings- och specifikationsbeskrivningar, medan andra kan användas under hela utvecklingscykeln, inklusive design, implementering, bevis på resultat, testning och simulering av parallella system.

Utbredningen av olika samtidighetsmodeller har fått en del forskare att utveckla sätt att kombinera dessa teoretiska modeller. Till exempel har Lee och Sangiovanni-Vincentelli visat att den så kallade "märkta signaler"-modellen kan användas för att tillhandahålla ett gemensamt ramverk för att beskriva denotationssemantiken för olika samtidighetsmodeller, [4] och Nielsen, Sassoon och Winskle har visat den kategoriteorin kan användas för att ge en gemensam förståelse för de olika modellerna. [5]

Teoremet om samtidig representation från aktörsmodellen ger ett ganska generellt sätt att beskriva samtidiga system som är stängda i den meningen att de inte får några meddelanden utifrån. Andra metoder för att beskriva samtidighet, såsom processkalkyl , kan beskrivas i termer av aktörsmodellen med hjälp av tvåfas commit-protokollet. [6] Den matematiska notationen som används för att beskriva ett slutet system S ger en bättre approximation om det är byggt från ett initialt beteende, betecknat med ⊥ S , med hjälp av en approximerande funktionsförlopp S . [7] Sedan är notationen för S konstruerad enligt följande:

Beteckna S ≡ ⊔ i∈ω progression S i (⊥ S )

Således kan S uttryckas matematiskt i termer av alla dess möjliga beteenden.

Logik

För att ge logiska resonemang om parallella system kan olika typer av temporal logik användas [8] . Vissa av dem, såsom linjär temporal logik eller beräkningsträdlogik, tillåter att uttalanden görs om sekvensen av tillstånd som ett parallellt system kan gå igenom. Andra, som t.ex. beräkningsträdaktionslogik, Hennessy-Milner-logik eller Lamports tidsmässiga aktionslogik, bygger sina uttalanden från en sekvens av åtgärder (tillståndsändringar). Den huvudsakliga användningen av dessa logiker är att skriva specifikationer för parallella system. [ett]

Öva

I det här avsnittet kommer vi att använda två föreställningar om parallellism som är vanliga i engelsk litteratur, eftersom vi kommer att prata om att jämföra dem med varandra. Termen Samtidighet kommer att översättas med "samtidighet", och termen Parallellism kommer att översättas med "parallellism".

Simultan programmering inkluderar programmeringsspråk och algoritmer som används för att implementera simultana system. Simultan programmering anses generellt vara mer generell än parallell programmering eftersom det kan involvera godtyckliga dynamiska kommunikations- och interaktionsmönster, medan parallella system oftast implementerar fördefinierade och välstrukturerade kommunikationsmönster. Huvudmålen med samtidig programmering är korrekthet , effektivitet , stabilitet . Samtidigt system, som operativsystem och databashanteringssystem, är främst designade för att fungera under osäkra förhållanden, inklusive automatisk återställning efter ett fel, de bör inte sluta fungera oväntat. Vissa samtidiga system fungerar i en form av transparent simultanitet, där samtidiga beräkningsenheter kan konkurrera om användningen av samma resurs, men kärnan i denna konkurrens är dold för programmeraren.

Eftersom samtidiga system delar resurser kräver de vanligtvis någon form av medlare inbyggd i deras implementering (ofta den underliggande hårdvaran) för att kontrollera åtkomsten till dessa resurser. Användningen av arbiters skapar möjlighet till osäkerhet vid samtidiga beräkningar, vilket är av stor betydelse för praktiken, inklusive för att säkerställa korrekthet och effektivitet. Till exempel utesluter inte arbitrage obegränsad indeterminism, som är förknippad med modellkontrollproblemet , som är orsaken till tillståndsrummets explosiva karaktär och till och med kan leda till bildandet av en modell med ett oändligt antal tillstånd.

Vissa samtidiga programmeringsmodeller inkluderar skapandet av samprocesser och deterministisk simultanitet . I dessa modeller ger processkontrolltrådar uttryckligen sina tidsdelar till antingen systemet eller en annan process.

Se även

Anteckningar

  1. ↑ 1 2 Cleaveland, Rance; Scott Smolka. Strategiska riktningar i samtidighetsforskning  //  ACM Computing Surveys : journal. - 1996. - December ( vol. 28 , nr 4 ). — S. 607 . - doi : 10.1145/242223.242252 .
  2. ↑ Filman, Robert; Daniel Friedman. Koordinerad beräkning - Verktyg och tekniker för distribuerad  programvara . - McGraw-Hill Education , 1984. - ISBN 0-07-022439-0 . Arkiverad kopia (inte tillgänglig länk) . Hämtad 5 oktober 2011. Arkiverad från originalet 16 maj 2007. 
  3. ↑ Keller, George; Christoph Kessler, Jesper Träff. Praktisk PRAM-programmering  (neopr.) . — John Wiley and Sons , 2001.
  4. ↑ Lee, Edward; Alberto Sangiovanni-Vincentelli. Ett ramverk för jämförelse av beräkningsmodeller  // IEEE-transaktioner på  CAD : journal. - 1998. - December ( vol. 17 , nr 12 ). - P. 1217-1229 . - doi : 10.1109/43.736561 .
  5. ↑ Mogens Nielsen; Vladimiro Sassone och Glynn Winskel (1993). "Relationer mellan modeller av samtidighet" . REX skola/symposium . Arkiverad från originalet 2009-02-26 . Hämtad 2011-10-05 . Utfasad parameter används |deadlink=( hjälp )
  6. ↑ Frederick Knabe. Ett distribuerat protokoll för kanalbaserad kommunikation med valmöjligheter PARLE 1992.
  7. ↑ William Clinger. Grunderna för skådespelarsemantik  (neopr.) . - MIT, 1981. - Juni ( vol. Mathematics Doctoral Dissertation ).
  8. ↑ Roscoe, Colin. Modala och tidsmässiga egenskaper hos  processer . - Springer, 2001. - ISBN 0-387-98717-7 .

Länkar

  Gå till Wikidata-objektet  Ordböcker och uppslagsverk