Citire-copiere-actualizare

Citire-Copiere-Actualizare, RCU (Citire-Modificare-Scriere[ clarify ] , read-copy-update, read-copy-update [1] , Read-Copy-Update [2] ) este un mecanism de sincronizare în sistemele cu mai multe fire . Implementează sincronizarea fără blocare pentru toți cititorii structurii de date. Scrierile pot fi paralele cu citirile, dar numai un scriitor poate fi activ la un moment dat.

Descriere

Ideea de bază este că, în loc să schimbe datele existente, scriitorul creează o copie a acestora, o modifică și apoi actualizează atomic indicatorul către structura datelor. În același timp, toți cititorii care au accesat structura înainte de actualizare păstrează accesul la copia lor învechită a datelor, care va rămâne neschimbată. Cu toate acestea, noii cititori vor avea acces la structura deja actualizată. Citirea în acest caz este o secțiune critică care permite citirea simultană de mai multe fire, dar nu permite întreruperea firului în proces.

Schimbarea unui element dintr-o listă

Luați în considerare, de exemplu, cum să schimbați un element dintr-o listă legată individual folosind acest mecanism de sincronizare.

Rolul indicatorului global va fi îndeplinit în acest caz de către indicatorul la primul element. Când scrieți, va trebui să creați o copie a întregii liste, să actualizați elementul de interes pentru acesta și apoi să actualizați atomic indicatorul global, astfel încât să indice primul element al noii liste. Toate operațiunile de citire care au accesat lista înainte de a fi actualizată vor primi copia veche, care va rămâne neschimbată; după actualizare, noua copie va fi citită.

Această metodă nu poate fi numită eficientă din cauza necesității de a copia întreaga listă. Cu toate acestea, dacă se poate garanta că doar un element al listei poate fi citit și blocarea este actualizată atunci când treceți la următorul , atunci când scrieți, puteți lăsa nevoia de a copia și modifica doar un element, după care actualizați atomic indicatorul către elementul anterior al listei (sau indicatorul către primul element).

Adăugarea unui articol la o listă este foarte asemănătoare cu schimbarea, dar deoarece nu există date de accesat atunci când este creat noul articol, nu este nevoie să fiți atenți când să ștergeți copia veche a datelor.

Eliberarea memoriei

După ce un element nou este creat și indicatorul este actualizat, vechea copie a elementului rămâne în memorie și nu poate fi ștearsă până când toate firele de execuție care au acces la el nu o deblochează. Pentru a face acest lucru, puteți utiliza mecanisme de sincronizare de blocare. O alternativă este să luați în considerare faptul că lectura este o secțiune critică. Apoi firul de scriere se programează pe rând după fiecare dintre firele de citire cu un apel de sistem. În acest caz, toate firele de citire sunt garantate să treacă printr-o schimbare de context și, prin urmare, ajung să utilizeze o referință la o versiune învechită a structurii de date.

Citirea în regiunea critică

Când se utilizează algoritmul de citire-modificare-scriere, nu se pot face ipoteze despre ce se va întâmpla cu structura de date pentru fiecare fir care citește date. Aceasta înseamnă că stocarea unui pointer de structură și utilizarea acestuia în afara unei secțiuni critice și chiar și atunci când introduceți o nouă secțiune critică citită poate duce la o eroare. Tot accesul la structura de date ar trebui efectuat numai în secțiunea critică, iar firul de citire, dacă este necesar, poate copia datele în sine în această perioadă, după care poate lucra cu copia sa locală, eliberând blocarea și fără a risca să încerce. accesați un fir deja la distanță, deschis anterior pentru scriere.

Citire-modificare-scriere în Linux

Suportul RCU a fost prezent în sistemul de operare Linux începând cu versiunea 2.5 de kernel [3] . Funcțiile principale ale RCU API:

1. rcu_read_lock()  - anunță că un flux a intrat în secțiunea critică pentru citire;
2. rcu_read_unlock()  - anunță ieșirea firului de citire din secțiunea critică;
3. synchronize_rcu()  - Prin apelarea acestei funcții, un fir deschis pentru scriere așteaptă până când toate operațiunile de citire care aveau acces la versiunea veche a structurii de date s-au terminat. După aceea, un flux care poate fi scris este liber pentru a șterge copia învechită.

De asemenea, pentru a proteja împotriva optimizărilor compilatorului care modifică secvența de execuție a instrucțiunilor, macrocomenzile sunt definite pentru obținerea și actualizarea în siguranță a unui pointer către structura de date rcu_dereference() și , respectiv, rcu_assign_pointer() .

Acțiuni înainte și după înregistrare

Mai întâi, trebuie să citiți structura de date, apoi să modificați copia acesteia și apoi să scrieți atomic indicatorul către structura de date actualizată .

Alternative

Pe unele platforme (de exemplu RISC ) această instrucțiune nu este disponibilă. Rezultate echivalente pot fi obținute folosind instrucțiunile:

1. încărcarea cu un marcaj (LL - load linked);
2. încercare de scriere (SC - stocare condiționată).

Vezi și

• blocare
• Sincronizare

Note

1. ↑ https://books.google.ru/books?id=zA7ECwAAQBAJ&pg=PA177&lpg=PA177&dq= „Citește-Copie-Actualizează”+citește+copie
2. ↑ LDD
3. ↑ Copie arhivată . Consultat la 24 februarie 2017. Arhivat din original la 11 ianuarie 2017. (nedefinit)

Literatură

• Paul E. McKenney, John D. Slingwine. Read-Copy_update: utilizarea istoricului de execuție pentru a rezolva problemele de concurență . (nedefinit)
• Ce este RCU? . (nedefinit)
• Paul E. McKenney, Jonathan Walpole. Ce este RCU fundamental? . (nedefinit)

Link -uri