Comparația cu schimb ( compara și setează , compară și schimbă, CAS ) este o instrucțiune atomică care compară valoarea din memorie cu unul dintre argumente și, dacă are succes, scrie al doilea argument în memorie. Acceptat pe x86 , Itanium , Sparc și alte familii de procesoare .
Ca și alte instrucțiuni atomice , este destinat sincronizării între agenți paraleli (pe procesoare diferite sau pe același, dar fără posibilitatea de captare exclusivă). Principala aplicație a comparației cu schimbul este implementarea unor algoritmi de blocare și neblocare .
Abordarea instrucțiunii atomice este opusă abordării „notație condiționată” ( load-link/store-conditional ) .
Instrucțiunea de comparare cu schimbul în procesoarele x86 se numește CMPXCHG și se execută după cum urmează:
Apoi, programatorul trebuie să codifice o verificare a steagului ZF pentru a afla dacă operațiunea a avut succes sau, în momentul în care a început, valoarea din memorie a fost înlocuită cu un alt agent.
Pentru SPARC , instrucțiunile pentru această operațiune se numesc CASA și CASXA.
S-ar părea că întreruperile pot fi dezactivate pe o mașină cu un singur procesor, iar apoi starea memoriei cu siguranță nu va schimba nimic. Dar aici sunt două probleme. Prima problemă - dezactivarea întreruperilor - este o procedură relativ costisitoare. A doua problemă este că dacă întreruperile sunt dezactivate și firul de execuție intră într-o buclă infinită, programul nu poate fi terminat fără a reporni computerul. Prin urmare, Linux necesită permisiuni mari pentru codul cu această instrucțiune, ceea ce poate cauza multe neplăceri utilizatorilor programului.
Pe o mașină multiprocesor, dezactivarea întreruperilor nu va ajuta deloc, deoarece într-o situație:
Primul procesor a verificat dacă memoria nu este blocată Al doilea procesor a verificat dacă memoria nu este blocată Primul procesor a blocat memorie Memorie blocată de al doilea procesor Primul procesor a schimbat memoria Al doilea procesor a schimbat memoria Primul procesor a deblocat memorie Memorie deblocată de al doilea procesormodificările primului procesor se vor pierde, iar programul va crede că totul este în regulă.
Avem n procesoare, fiecare dintre acestea dorește uneori să acceseze o resursă partajată. De exemplu, către un dispozitiv sau o locație de memorie partajată.
Înainte de a începe lucrarea principală, le vom atribui numere unice de la 0 la n-1.
Să selectăm o celulă de memorie care va indica ce procesor utilizează în prezent resursa. Valoarea -1 va indica faptul că resursa nu este ocupată de nimeni. Să punem -1 în el.
În timpul lucrării principale, fiecare procesor trebuie să verifice dacă celula conține -1 și, dacă da, apoi scrie numărul său în ea. Dacă celula este ocupată, procesorul trebuie să aștepte până când devine liberă (am convenit că va aștepta și nu vom scrie programe care nu îndeplinesc această cerință).
Deci programul ar putea arăta astfel:
; blocare m_wait: mută eax, -1 mov ecx, 5 ; numărul procesorului nostru este 5 cmpxchg 105BA9D2, ecx ; adresa celulei 105BA9D2 jnz m_wait ; dacă resursa este blocată ; lucrând cu o resursă comună ... ; deblocarea ...Comparația atomică cu instrucțiunile de schimb nu făcea parte din standardele limbajului C/C++, deci sunt fie implementate prin asamblare, fie prin extensii de limbaj non-standard. Standardul C++11 a introdus o bibliotecă de operații atomice care are o comparație cu un schimb [1] . Există, de asemenea, mai multe biblioteci cu implementări C/C++ de interfețe pentru astfel de instrucțiuni, de exemplu: Intel TBB, boost.atomic, Open Portable Atomics, Glib.
Comanda cmpxchg poate fi codificată direct folosind următorul asamblator inline al compilatorului GCC ( GCC Inline Assembly ):
uint32_t * ptr ; uint32_t ret_val , old_val , new_val ; asm volatil ( "blocare \n\t cmpxchgl %1,%2" : "=a" ( ret_val ) : "r" ( new_val ), "m" ( * ptr ), "0" ( old_val ) : "memorie" );sau pentru x86-64 :
uint64_t * ptr ; uint64_t ret_val , old_val , new_val ; asm volatil ( "blocare \n\t cmpxchgq %1,%2" : "=a" ( ret_val ) : "r" ( new_val ), "m" ( * ptr ), "0" ( old_val ) : "memorie" );Acordați o atenție deosebită utilizării asm volatile (nu doar asm ), care indică compilatorului de optimizare că această inserție de asamblare are efecte secundare și trebuie să fie localizată în bucla unde se află în cod. De asemenea, este obligatoriu să specificați „memorie” în lista de clobbering.
GCC și alți compilatoare acceptă extensii încorporate pentru a implementa această instrucțiune:
TYPE __sync_val_compare_and_swap(TYPE* ptr, TYPE oldval, TYPE newval);Este posibil ca această extensie să nu fie implementată pentru toate arhitecturile acceptate de gcc sau să nu fie implementată în toate versiunile de gcc. [2]
Funcții similare cu un nume diferit există în compilatoare pentru Windows și Mac OS X: InterlockedCompareExchange(), OSAtomicCompareAndSwapPtrBarrier().
Existența unei astfel de instrucțiuni deschide orizonturi vaste în îmbunătățirea performanței codului datorită posibilității de a evita complet blocările .
Luați în considerare această bucată de pseudocod :
citiți valoarea variabilei; facem niște procesări; scrieți noua valoare a variabilei;Cea mai obișnuită modalitate de a face acest cod threadable este introducerea primitivelor de sincronizare ( mutex -uri, spinlock -uri etc.) astfel:
facem blocare; citiți valoarea variabilei; facem niște procesări; scrieți noua valoare a variabilei; eliberați încuietoareaCu toate acestea, o metodă mai elegantă este adesea aplicabilă:
citiți valoarea variabilei; facem niște procesări; produce cmpxchg noua valoare a variabilei, presupunând că valoarea este încă egală cu cea veche; daca valoarea a fost schimbata de un alt thread, repetam procesarea;Luați în considerare un exemplu clasic de structură de date - o listă legată .
struct ll_node { intkey ; _ // o cheie int val ; // o structură de valoare ll_node * next ; // pointer către următorul };Funcția de inserat în lista legată a nodului new_node după nodul specificat este următoarea:
void ll_insert_after ( struct ll_node * nod , struct ll_node * new_node ) { new_node -> next = nod -> next ; nod -> următor = new_node ; // (!!!) - acordați atenție acestei linii }Evident, codul va funcționa corect doar în ipoteza că valoarea nod->next nu a fost modificată de un alt fir până în momentul în care rulează linia marcată „(!!!)”, altfel riscăm să pierdem modificările altor fire de execuție, noduri de generare care nu au legătură cu listă ( Memory Leak ).
Există 3 moduri principale de a face față acestui lucru:
1) Închideți întreaga listă legată cu un mutex . În ceea ce privește performanța, aceasta este cea mai proastă cale. În primul rând, un singur thread va funcționa cu lista legată la un moment dat, ceea ce în sine anulează toate avantajele multithreadingului . În al doilea rând, în practică, situația este mult mai gravă decât ne-am putea aștepta: munca simultană mai mult sau mai puțin intensivă cu o astfel de listă legată va genera schimbări de context uriașe (mii, zeci de mii și, în unele cazuri, mai ales intensive, chiar milioane) , care în sine. în sine, poate distruge performanța nu numai a aplicației în sine, ci și a sistemului în ansamblu (efectul „scăderii performanței” crește pătratic cu numărul de nuclee de calcul).
2) Un mod mai inteligent. Schimbați Mutex în spinlock . Câteva cicluri de așteptare ocupate inactiv sunt mult mai ieftine decât un apel de sistem și schimbarea contextului rezultată. Are un efect real asupra sistemelor SMP , dar pe sistemele cu un singur nucleu provoacă o ucidere a performanței „rară, dar bine direcționată”, din cauza timpilor lungi de inactivitate.
3) Algoritm fără blocare . Să rescriem funcția de inserare după cum urmează: explică ipoteza nod->next value. O vom verifica în mod explicit folosind comanda cmpxchg:
void ll_insert_after ( struct ll_node * nod , struct ll_node * new_node ) { struct ll_node * old_val = node -> next ; // amintiți-vă vechea valoare while ( 1 ) { new_node -> next = old_val ; old_val = cmpxchg ( & node -> următorul , old_val , new_node ); if ( old_val == new_node ) rupe ; // Alte fire nu s-au schimbat nodul->next. Succesul operației, ieșire. // În caz contrar, încercați din nou } }„Miezul” logicii neblocante a acestei funcții este instrucțiunea CMPXCHG. Verifică atomic dacă conținutul locației de memorie &node->next conține în continuare valoarea lui old_val, iar dacă o face (și probabilitatea acestui cel mai bun caz este extrem de mare), scrie valoarea pointerului new_node și iese din buclă. . În cazul unei coliziuni de partajare , obținem valoarea actualizată a lui old_val și introducem o nouă iterație a buclei.
În cazul listei legate de mai sus, probabilitatea unei coliziuni este extrem de mică. În mod formal, este egal cu P count =(n/N)*p funk , unde N este numărul de intrări din listă, n este numărul de fire simultane, p funk este raportul dintre timpul petrecut de fiecare fir în interiorul funcția de inserare la fluxul de timp total de lucru.
Principalul dezavantaj care împiedică utilizarea comenzii cmpxchg în algoritmii fără blocare este că comanda înlocuiește o singură valoare. În cazul în care este doar o valoare indicator sau o variabilă întreagă, acest lucru este suficient. Cu toate acestea, de foarte multe ori este necesar să se înlocuiască atomic condiționat două variabile legate . De exemplu: un pointer către un buffer și lungimea acestuia, un pointer către începutul și sfârșitul datelor etc. În aceste scopuri, comenzile CMPXCHG (32 de biți), CMPXCHG8B (64 de biți) și CMPXCHG16B ( x86 64 ) sunt introdus în procesoarele Intel. Apropo, cerința de a accepta comanda CMPXCHG16B de către procesor a apărut în MS Windows versiunea 8.1 x64.
În procesoarele SPARC, aceste funcții sunt îndeplinite de instrucțiunile CASA și CASXA.