Algoritm non-blocant - Non-blocking algorithm

Nu trebuie confundat cu I / O care nu blochează .

În informatică , un algoritm se numește neblocant dacă eșecul sau suspendarea oricărui fir nu poate provoca eșecul sau suspendarea unui alt fir; pentru unele operații, acești algoritmi oferă o alternativă utilă la implementările tradiționale de blocare . Un algoritm care nu blochează este blocat dacă există un progres garantat la nivelul întregului sistem și fără așteptare dacă există și un progres garantat pe fiecare fir. „Non-blocare” a fost utilizată ca sinonim pentru „fără blocare” în literatură până la introducerea libertății de obstrucție în 2003.

Cuvântul „fără blocare” a fost folosit în mod tradițional pentru a descrie rețelele de telecomunicații care ar putea direcționa o conexiune printr-un set de relee „fără a fi nevoie să reorganizeze apelurile existente” (vezi rețeaua Clos ). De asemenea, dacă centrala telefonică „nu este defectă, poate face întotdeauna conexiunea” (vezi comutatorul de întindere minimă care nu blochează ).

Motivație

Articol principal: Dezavantaje ale încuietorilor

Abordarea tradițională a programării multi-thread este de a utiliza blocaje pentru a sincroniza accesul la resursele partajate . Primitivele de sincronizare, cum ar fi mutele , semaforele și secțiunile critice, sunt toate mecanisme prin care un programator se poate asigura că anumite secțiuni de cod nu se execută simultan, dacă acest lucru ar corupe structurile de memorie partajate. Dacă un fir încearcă să obțină o blocare care este deja ținută de un alt fir, firul se va bloca până când blocarea este liberă.

Blocarea unui fir poate fi nedorită din mai multe motive. Un motiv evident este că, în timp ce firul este blocat, acesta nu poate realiza nimic: dacă firul blocat ar fi efectuat o sarcină cu prioritate ridicată sau în timp real , ar fi extrem de nedorit să-i oprim progresul.

Alte probleme sunt mai puțin evidente. De exemplu, anumite interacțiuni între blocări pot duce la condiții de eroare, cum ar fi blocarea , blocarea vieții și inversarea priorității . Utilizarea încuietorilor implică, de asemenea, un compromis între blocarea cu granulație grosieră, care poate reduce semnificativ oportunitățile de paralelism , și blocarea cu granulație fină, care necesită un design mai atent, crește blocarea aerului și este mai predispusă la erori.

Spre deosebire de algoritmii de blocare, algoritmii care nu blochează nu suferă de aceste dezavantaje și, în plus, sunt siguri pentru utilizare în handler-uri de întrerupere : chiar dacă firul preemptat nu poate fi reluat, progresul este încă posibil fără el. În schimb, structurile de date globale protejate prin excludere reciprocă nu pot fi accesate în siguranță într-un handler de întrerupere, deoarece firul prevenit poate fi cel care deține blocarea - dar acest lucru poate fi corectat cu ușurință prin mascarea cererii de întrerupere în timpul secțiunii critice.

O structură de date fără blocare poate fi utilizată pentru a îmbunătăți performanța. O structură de date fără blocare mărește timpul petrecut în executarea paralelă mai degrabă decât executarea în serie, îmbunătățind performanța pe un procesor multi-core , deoarece accesul la structura de date partajată nu trebuie să fie serializat pentru a rămâne coerent.

Implementare

Cu puține excepții, algoritmii care nu blochează folosesc primitive atomice de citire-modificare-scriere pe care hardware-ul trebuie să le furnizeze, dintre care cea mai notabilă este compare and swap (CAS) . Secțiunile critice sunt aproape întotdeauna implementate folosind interfețe standard peste aceste primitive (în cazul general, secțiunile critice vor fi blocate, chiar și atunci când sunt implementate cu aceste primitive). În anii 1990, toți algoritmii care nu blocează trebuiau să fie scrise „nativ” cu primitivele subiacente pentru a obține performanțe acceptabile. Cu toate acestea, câmpul emergent al memoriei tranzacționale software promite abstracții standard pentru scrierea unui cod eficient neblocant.

De asemenea, s-au făcut multe cercetări în furnizarea de structuri de date de bază , cum ar fi stive , cozi , seturi și tabele hash . Acestea permit programelor să schimbe cu ușurință date între fire asincron.

În plus, unele structuri de date care nu blochează sunt suficient de slabe pentru a fi implementate fără primitive atomice speciale. Aceste excepții includ:

  • un buffer inel cu un singur cititor FIFO , cu o dimensiune care împarte în mod uniform depășirea unuia dintre tipurile de numere întregi disponibile nesemnate, poate fi implementat necondiționat în condiții de siguranță folosind doar o barieră de memorie
  • Citiți-copiați-actualizați cu un singur scriitor și orice număr de cititori. (Cititorii sunt fără așteptare; scriitorul este de obicei blocat, până când trebuie să recupereze memoria).
  • Citiți-copiați-actualizați cu mai mulți scriitori și orice număr de cititori. (Cititorii sunt fără așteptare; mai mulți scriitori serializează în general cu o încuietoare și nu sunt liberi de obstrucții).

Mai multe biblioteci utilizează intern tehnici fără blocare, dar este dificil să scrieți cod fără blocare care este corect.

Așteptare-libertate

Libertatea de așteptare este cea mai puternică garanție non-blocantă a progresului, combinând debitul garantat la nivelul întregului sistem cu libertatea înfometării . Un algoritm este fără așteptare dacă fiecare operație are o legătură cu numărul de pași pe care algoritmul îi va face înainte ca operațiunea să se finalizeze. Această proprietate este esențială pentru sistemele în timp real și este întotdeauna plăcută să o aibă atâta timp cât costul de performanță nu este prea mare.

S-a arătat în anii 1980 că toți algoritmii pot fi implementați fără așteptare și s- au demonstrat multe transformări din codul serial, numite construcții universale . Cu toate acestea, performanța rezultată nu se potrivește, în general, nici cu designurile de blocare naive. Mai multe lucrări au îmbunătățit de atunci performanța construcțiilor universale, dar totuși, performanța lor este mult sub blocarea proiectelor.

Mai multe lucrări au investigat dificultatea creării algoritmilor fără așteptare. De exemplu, s-a arătat că primitivele condiționate atomice disponibile pe scară largă , CAS și LL / SC , nu pot furniza implementări fără înfometare ale multor structuri de date comune fără ca costurile de memorie să crească liniar în numărul de fire.

Dar, în practică, aceste limite inferioare nu prezintă o barieră reală, deoarece cheltuirea unei linii cache sau a unei granule de rezervare exclusive (până la 2 KB pe ARM) de stocare pe fir în memoria partajată nu este considerată prea costisitoare pentru sistemele practice (de obicei, cantitatea de stocare necesară în mod logic este un cuvânt, dar operațiile CAS din punct de vedere fizic pe aceeași linie cache se vor ciocni și operațiunile LL / SC din aceeași granulă de rezervare exclusivă vor colisiona, deci cantitatea de magazin necesară fizic este mai mare).

Algoritmii fără așteptare au fost rare până în 2011, atât în ​​cercetare, cât și în practică. Cu toate acestea, în 2011, Kogan și Petrank au prezentat o coadă fără așteptare construită pe primitivul CAS , disponibilă în general pe hardware-ul comun. Construcția lor a extins coada fără blocare a lui Michael și Scott, care este o coadă eficientă adesea utilizată în practică. O lucrare de urmărire a lui Kogan și Petrank a furnizat o metodă pentru a face rapid algoritmii fără așteptare și a folosit această metodă pentru a face coada fără așteptare practic la fel de rapidă ca și omologul său fără blocare. O lucrare ulterioară a lui Timnat și Petrank a furnizat un mecanism automat pentru generarea structurilor de date fără așteptare din cele fără blocare. Astfel, implementările fără așteptare sunt acum disponibile pentru multe structuri de date.

Libertate de blocare

Libertatea de blocare permite subiectelor individuale să moară de foame, dar garantează un debit la nivel de sistem. Un algoritm nu este blocat dacă, atunci când thread-urile programului sunt rulate pentru o perioadă suficient de lungă de timp, cel puțin unul dintre thread-uri progresează (pentru o definiție sensibilă a progresului). Toți algoritmii fără așteptare sunt fără blocare.

În special, dacă un fir este suspendat, atunci un algoritm fără blocare garantează că firele rămase pot continua să progreseze. Prin urmare, dacă două fire pot lupta pentru același blocaj mutex sau spinlock, atunci algoritmul nu este blocat. (Dacă suspendăm un fir care deține blocarea, atunci al doilea fir se va bloca.)

Un algoritm nu este blocat dacă operația infinit de des a unor procesoare va reuși într-un număr finit de pași. De exemplu, dacă N procesoare încearcă să execute o operație, unele dintre cele N procese vor reuși să termine operația într-un număr finit de pași, iar altele ar putea eșua și vor încerca din nou la eșec. Diferența dintre fără așteptare și fără blocare este că funcționarea fără așteptare a fiecărui proces este garantată pentru a avea succes într-un număr finit de pași, indiferent de ceilalți procesoare.

În general, un algoritm fără blocare poate rula în patru faze: finalizarea propriei operații, asistarea unei operații de obstrucționare, avortarea unei operații de blocare și așteptare. Finalizarea propriei operații este complicată de posibilitatea asistenței concomitente și a avortului, dar este invariabil calea cea mai rapidă către finalizare.

Decizia cu privire la momentul asistării, avortului sau așteptării când se întâlnește o obstrucție este responsabilitatea unui manager de conflict . Acest lucru poate fi foarte simplu (asistă operațiile cu prioritate mai mare, anulează cele cu prioritate mai mică) sau poate fi mai optimizat pentru a obține un randament mai bun sau pentru a reduce latența operațiunilor cu prioritate.

Asistența simultană corectă este de obicei cea mai complexă parte a unui algoritm fără blocare și deseori foarte costisitoare de executat: nu numai că firul de asistare încetinește, dar, datorită mecanicii memoriei partajate, firul asistat va fi și el încetinit , dacă încă rulează.

Obstrucție-libertate

Libertatea de obstrucție este cea mai slabă garanție naturală de progres, care nu blochează. Un algoritm este lipsit de obstrucții dacă în orice moment, un singur fir executat izolat (adică, cu toate firele de obstrucție suspendate) pentru un număr delimitat de pași își va finaliza operațiunea. Toți algoritmii fără blocare sunt fără obstrucții.

Libertatea de obstrucție cere doar ca orice operațiune finalizată parțial să poată fi anulată și modificările făcute să fie anulate. Eliminarea asistenței concomitente poate duce adesea la algoritmi mult mai simpli, care sunt mai ușor de validat. Prevenirea sistemului de blocare continuă activă este sarcina unui manager de conflict.

Unii algoritmi fără obstrucție utilizează o pereche de „markeri de consistență” în structura datelor. Procesele care citesc structura datelor citesc mai întâi un marker de consistență, apoi citesc datele relevante într-un tampon intern, apoi citiți celălalt marker și apoi comparați markerii. Datele sunt consistente dacă cei doi markeri sunt identici. Marcatorii pot fi neidentici atunci când citirea este întreruptă de un alt proces de actualizare a structurii datelor. Într-un astfel de caz, procesul elimină datele din buffer-ul intern și încearcă din nou.

Vezi si

Referințe

linkuri externe