Sincronizarea fără blocare este o abordare în programarea paralelă pe sisteme multiprocesoare simetrice care se desparte de primitivele tradiționale de blocare , cum ar fi semaforele , mutexurile și evenimentele . Partajarea accesului între fire se face în detrimentul operațiilor atomice și al mecanismelor speciale de blocare dezvoltate pentru o anumită sarcină.
Avantajul algoritmilor neblocatori este o scalabilitate mai bună în ceea ce privește numărul de procesoare. În plus, dacă sistemul de operare întrerupe unul dintre firele de execuție cu o sarcină de fundal, restul își va face treaba fără timp inactiv sau chiar va prelua munca remarcabilă.
De la cel mai slab la cel mai puternic:
Fără obstacole ( de exemplu, fără obstacole ) Cea mai slabă dintre garanții. Un thread progresează dacă nu întâlnește obstacole de la alte fire. Algoritmul funcționează fără obstacole dacă un fir care rulează în orice moment (presupunând că toate firele obstructive sunt suspendate) își finalizează munca într-un număr determinist de pași. Sincronizarea cu mutex -uri nici măcar nu îndeplinește această cerință: dacă un thread se oprește după achiziționarea mutex-ului, alte fire care au nevoie de mutex vor fi inactive. Fără încuietori ( ing. fără încuietori ) Pentru algoritmii fără blocare, progresul sistemului a cel puțin unui fir este garantat. De exemplu, un fir de execuție care efectuează o operație de „ comparare cu swap ” într-o buclă ar putea, teoretic, să ruleze pe termen nelimitat, dar fiecare iterație a acestuia înseamnă că un alt fir de execuție a progresat, ceea ce înseamnă că sistemul în ansamblu face progrese. Fără așteptări ( ing. fără așteptare ) Cea mai puternică garanție a progresului. Algoritmul funcționează fără așteptare dacă fiecare operație este efectuată într-un anumit număr de pași, independent de celelalte fire.Când creați aplicații cu mai multe fire, este adesea necesar să partajați accesul la o resursă partajată. Abordarea tradițională vă permite să acordați acces secvențial utilizând un mecanism de sincronizare, cum ar fi blocările . Primitivele de sincronizare, cum ar fi mutexurile , semaforele și secțiunile critice , vă permit să scrieți o bucată de cod care este garantat că nu va fi executată simultan atunci când este accesată din fire paralele - accesul simultan la o bucată de memorie partajată poate duce la coruperea conținutului. O încercare a unuia dintre fire de a obține o blocare care este deja ținută de un alt fir face ca execuția primului thread să fie suspendată până când blocarea este eliberată în al doilea fir.
Cel mai simplu mutex [1] este implementat folosind așa-numitul spinlock 'a - un ciclu gol cu operații atomice. Primitivele de așteptare mai complexe sunt realizate cu o operațiune costisitoare numită „ comutație de context ” și același spinlock în kernel ( KiDispatcherLockpe Windows ) care securizează coada de prioritate . Când încărcarea primitivelor de sincronizare este scăzută (interfața de utilizator imprimă progresul general al unui alt fir; un fir oferă sarcini de descărcat prin rețea, al doilea descarcă ...), supraîncărcarea de la buclele și comutatoarele goale este mică.
Dacă procesează o cantitate mare de date pe un procesor multi-core, iar interacțiunea dintre fire devine mai mare. Structurile obișnuite de date, cum ar fi un arbore de căutare , pot fi îngrădite doar cu un mutex în întregime, iar dacă firele de execuție îl accesează în mod constant, munca devine aproape secvențială. În plus, un computer personal obișnuit cu un sistem de operare general îndeplinește alte sarcini - de exemplu, un utilizator, așteaptă execuția, deschide un browser - și o parte din timpul procesorului îi este acordată, iar firele de calcul sunt suspendate în momente aleatorii . Algoritmii neblocatori garantează că astfel de opriri ale unuia dintre firele de execuție nu vor duce la timp inactiv pentru celelalte. Absența timpului de inactivitate este deosebit de importantă dacă unul dintre firele de execuție realizează o sarcină cu prioritate ridicată sau o sarcină în timp real .
Sincronizarea fără blocare vă permite să scăpați complet de blocaje . Cu toate acestea, algoritmii care nu blochează au propriile erori - looping ( livelock ) și „ curse ”.
Algoritmii non-blocante sunt construiți pe operații atomice , de exemplu, citire-modificare-scriere , iar cea mai semnificativă dintre ele este compararea cu schimbul (CAS). Implementarea unei secțiuni critice se bazează de obicei pe utilizarea uneia dintre primitive. Până de curând, toate implementările de algoritmi neblocatori trebuiau făcute la un nivel „scăzut” de hardware pentru a asigura performanțe acceptabile. Cu toate acestea, dezvoltarea mecanismelor de memorie tranzacțională oferă abstracții standard pentru scrierea unui cod eficient neblocant.
Au fost dezvoltate, de asemenea, structuri de date de bază , cum ar fi stiva , coada , set și tabelul hash . Astfel de structuri fac posibilă simplificarea schimbului de date asincron între firele de execuție a programului. Unele structuri de date sunt destul de simple și pot fi utilizate fără blocări atomice speciale, de exemplu: