Ikke-blokerende synkronisering er en tilgang i parallel programmering på symmetriske multiprocessorsystemer, der bryder væk fra traditionelle blokerende primitiver såsom semaforer , mutexes og begivenheder . Deling af adgang mellem tråde sker på bekostning af atomariske operationer og specielle låsemekanismer udviklet til en specifik opgave.
Fordelen ved ikke-blokerende algoritmer er bedre skalerbarhed i forhold til antallet af processorer. Derudover, hvis OS afbryder en af trådene med en baggrundsopgave, vil resten udføre deres arbejde uden tomgang eller endda overtage det fremragende arbejde.
Fra svageste til stærkeste:
Uden forhindringer ( eng. obstruktionsfri ) Den svageste af garantier. En tråd gør fremskridt, hvis den ikke støder på forhindringer fra andre tråde. Algoritmen fungerer uden forhindringer, hvis en tråd, der kører på et hvilket som helst tidspunkt (forudsat at alle hindrende tråde er suspenderet) fuldfører sit arbejde i et deterministisk antal trin. Synkronisering med mutex'er opfylder ikke engang dette krav: hvis en tråd stopper efter at have erhvervet mutex'en, vil andre tråde, der har brug for mutex'en, være inaktive. Uden låse ( eng. låsefri ) For låsefri algoritmer er systemets fremskridt for mindst én tråd garanteret. For eksempel kan en tråd, der udfører en " sammenlign med swap "-operation i en loop, teoretisk køre på ubestemt tid, men hver iteration af den betyder, at en anden tråd har gjort fremskridt, hvilket betyder, at systemet som helhed gør fremskridt. Uden forventninger ( eng. ventefri ) Den stærkeste garanti for fremskridt. Algoritmen fungerer uden at vente, hvis hver operation udføres i et bestemt antal trin, uafhængigt af andre tråde.Når du opretter multitrådede applikationer, er det ofte nødvendigt at dele adgang til en delt ressource. Den traditionelle tilgang giver dig mulighed for at give sekventiel adgang ved hjælp af en synkroniseringsmekanisme såsom låse . Synkroniseringsprimitiver, såsom mutexes , semaforer og kritiske sektioner , giver dig mulighed for at skrive et stykke kode, der med garanti ikke vil blive eksekveret samtidigt, når det tilgås fra parallelle tråde - samtidig adgang til et stykke delt hukommelse kan føre til indholdskorruption. Et forsøg fra en af trådene på at opnå en lås, der allerede holdes af et andet gevind, bevirker, at udførelsen af det første gevind suspenderes, indtil låsen frigøres i det andet gevind.
Den enkleste mutex [1] er implementeret ved hjælp af den såkaldte spinlock 'a - en tom cyklus med atomariske operationer. De mere komplekse kø-primitiver udføres med en kostbar operation kaldet en " kontekstswitch " og den samme spinlock i kernen ( KiDispatcherLockpå Windows ), som sikrer prioritetskøen . Når belastningen på synkroniseringsprimitiverne er lav (brugergrænsefladen udskriver den generelle fremgang for en anden tråd; en tråd giver opgaver, der skal downloades gennem netværket, den anden downloader ...), er overheaden fra tomme sløjfer og switches lille.
Hvis de behandler en stor mængde data på en multi-core processor, og interaktionen mellem tråde bliver større. Almindelige datastrukturer, såsom et søgetræ , kan kun indhegnes med en mutex i sin helhed, og hvis tråde konstant får adgang til det, bliver arbejdet næsten sekventielt. Derudover udfører en almindelig personlig computer med et generelt OS andre opgaver - for eksempel en bruger, der venter på udførelse, åbner en browser - og en del af processortiden gives til ham, og beregningstråde suspenderes på tilfældige tidspunkter . Ikke-blokerende algoritmer garanterer, at sådanne stop af en af trådene ikke vil føre til inaktiv tid for de andre. Fraværet af ledig tid er især vigtigt, hvis en af trådene udfører en opgave med høj prioritet eller en opgave i realtid .
Ikke-blokerende synkronisering giver dig mulighed for helt at slippe af med deadlocks . Ikke-blokerende algoritmer har dog deres egne fejl - looping ( livelock ) og " races ".
Ikke-blokerende algoritmer er bygget på atomoperationer , for eksempel læs-modificere-skriv , og den mest betydningsfulde af dem er sammenligning med udveksling (CAS). Implementeringen af en kritisk sektion er normalt baseret på brugen af en af primitiverne. Indtil for nylig skulle alle implementeringer af ikke-blokerende algoritmer udføres på et "lavt" niveau af hardware for at sikre acceptabel ydeevne. Udviklingen af transaktionshukommelsesmekanismer giver imidlertid standardabstraktioner til skrivning af effektiv ikke-blokerende kode.
Grundlæggende datastrukturer såsom stakken , køen , sæt- og hashtabellen er også blevet udviklet . Sådanne strukturer gør det muligt at forenkle asynkron dataudveksling mellem programtråde. Nogle datastrukturer er ret enkle og kan bruges uden specielle atomlåse, for eksempel: