ABA ongelma

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 14. huhtikuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 3 muokkausta .

Multitasking - laskennassa ABA-ongelma ilmenee synkronoinnin aikana , kun muistisolu luetaan kahdesti, sama arvo luetaan molemmilla kerroilla ja "arvo on sama" -merkki tulkitaan "mikään ei ole muuttunut". Toinen säie voi kuitenkin kulkea näiden kahden lukemisen välillä, muuttaa arvoa, tehdä jotain muuta ja palauttaa vanhan arvon. Näin ollen ensimmäinen säiettä petetään uskomaan, että mikään ei ole muuttunut, vaikka toinen lanka on jo tuhonnut tämän oletuksen.

ABA-ongelma ilmenee, kun useat säikeet (tai prosessit ) käyttävät jaettua muistia yksi kerrallaan . Tässä on esimerkki tapahtumasarjasta, joka johtaa ABA-ongelmaan:

Vaikka se saattaa jatkaa toimintaansa, on mahdollista, että sen käyttäytyminen on virheellinen muista piilotetuista jaetun muistin muutoksista (joita se ei ole seurannut).

Yleensä ABA-ongelma kohdataan toteutettaessa lukitsemattomia rakenteita ja algoritmeja. Jos poistat elementin luettelosta , tuhoat sen ja luot sitten uuden elementin ja lisäät sen takaisin luetteloon, on mahdollista, että uusi elementti sijoitetaan vanhan tilalle. Uuden elementin osoitin osuu yhteen vanhan osoittimen kanssa, mikä johtaa ongelmaan: merkkien yhtäläisyys ei ole tiedon tasa-arvoa kokonaisuutena.

Esimerkki

Harkitse lukitsematonta pinoa :

/* Naiivi toteutus lukitsemattomasta pinosta, joka kärsii ABA-ongelmasta. */ class Stack { haihtuva Obj * top_ptr ; // // Poistaa ylimmän elementin ja palauttaa osoittimen siihen. // Obj * Pop () { kun ( 1 ) { Obj * ret_ptr = top_ptr ; if ( ! ret_ptr ) return NULL ; Obj * next_ptr = ret_ptr -> next ; // Jos ylin elementti on edelleen ret, oletetaan, ettei kukaan ole muuttanut pinoa. // (Tämä väite ei aina pidä paikkaansa ABA-ongelman vuoksi) // Korvaa alkuun atomisesti seuraava. if ( CompareAndSwap ( top_ptr , ret_ptr , next_ptr )) { return ret_ptr ; } // Muussa tapauksessa pino muutettu, yritä uudelleen. } } // // Lisää obj_ptr pinon alkuun. // void Push ( Obj * obj_ptr ) { kun ( 1 ) { Obj * seuraava_ptr = top_ptr ; obj_ptr -> seuraava = seuraava_ptr ; // Jos ylin elementti on edelleen seuraava, oletetaan, ettei kukaan ole muuttanut pinoa. // (Tämä väite ei aina pidä paikkaansa ABA-ongelman vuoksi) // Korvaa alkuun atomisesti obj. if ( CompareAndSwap ( top_ptr , next_ptr , obj_ptr )) { paluu ; } // Muussa tapauksessa pino muutettu, yritä uudelleen. } } };

Tämä koodi voi yleensä estää samanaikaisuusongelmia, mutta se kärsii ABA-ongelmasta. Harkitse seuraavaa järjestystä:

Pino sisältää aluksi top → A → B → C

Säie 1 aloittaa pop:n suorittamisen:

ret = A; seuraava=B;

Säie 1 keskeytyy juuri ennen CompareAndSwap ...

{ // Säie 2 suorittaa pop: ret = A ; seuraava = B ; CompareAndSwap ( A , A , B ) // Onnea, top = B palauttaa A ; } // Nyt pinon päällä → B → C { // Lanka 2 ponnahtaa uudelleen: ret = B ; seuraava = C ; CompareAndSwap ( B , B , C ) // Onnea, top = C paluu B ; } // Nyt pinon päällä → C poista B ; { // Lanka 2 työntää A:n takaisin pinoon: A -> seuraava = C ; CompareAndSwap ( C , C , A ) // Onnea, top = A }

Pino sisältää nyt top → A → C

Lanka 1 jatkuu:

VertaaJaVaihda(A, A, B)

Tämä ohje onnistuu, koska top == ret (molemmat ovat yhtä suuria kuin A), se asettaa ylhäältä seuraavaan (joka on yhtä suuri kuin B). Mutta B tuhoutui! Tämä johtaa huonoihin tuloksiin...

.Net avulla voit toteuttaa CompareAndSwap (CAS) -toiminnon atomisesti Interlocked.CompareExchange()-menetelmän ansiosta.

yksityinen staattinen bool CAS ( viite Solmun < T > sijainti , solmun < T > uusi arvo , solmu < T > vertailu ) { // 1. jos vertailu ja sijainti ovat samat, toinen säie ei koskenut sijaintia // 2. sijainti määritetään uudelle arvolle // 3. Menetelmä palauttaa vanhan sijaintiarvon määrityksestä riippumatta // 4. copmarand vertaa vanhaan sijaintiarvoon (eli oldLocation) // 5. jos oldLocation(old, return) ei ole muutettu toisella säikeellä, CAS palauttaa true , koska se vastaa vertailua var oldLocation = Lukittu . VertaaVaihto < Solmu < T >>( viite sijainti , uusiArvo , vertailuarvo ); // tämä on atomioperaatio return comparand == oldLocation ; }

Esimerkki .Netin lukitsemattomasta pinosta atomic CAS -toiminnolla:

public class SimpleStack < T > { yksityinen luokka Solmu < V > { julkinen solmu < V > Seuraava ; julkinen V kohta ; } yksityinen solmu < T > head ; public SimpleStack () { head = new Node < T >(); } public void Push ( T item ) { Solmu < T > solmu = new Node < T >(); solmu . tuote = tuote ; do { node . seuraava = pää . seuraava ; } while ( CAS ( ref head . Next , node , node . Next ) == false ); // odota solmuun.Seuraava ja head.Next osoittaa samaan elementtiin. // Sitten voit vaihtaa osoittimia niin, että pää osoittaa solmuun. Tämän jälkeen poistu silmukasta. } public T Pop () { Solmu < T > solmu ; do { solmu = pää . seuraava ; if ( solmu == null ) palauttaa oletuksen ( T ); } while ( CAS ( ref head . Next , node . Next , node ) == false ); // 1. CAS:ssa ei ole ABA-ongelmaa. // 2. node.Next ei anna NullReferenceException-poikkeusta (node）!= null), // koska muistia hallitaan .Net return -solmussa . Tuote ; } }

Tämän .net- pinon toteutuksen ABA-ongelman tekee merkityksettömäksi roskakeräysympäristö: emme menetä tai käytä uudelleen (toisessa säikeessä) viittausta solmuun (käytettäessä solmua.Next CAS:ssa), jos säiettä #2 tulee ensin, kuin säie #1 suorittaa Pop()-toiminnon. Ympäristöissä, joissa ei ole muistinhallintaa, tämä ongelma on akuutti, eikä tämä ratkaisu ole sopiva.

Ratkaisut

Yleinen kiertotapa on lisätä ylimääräisiä "mark" -bittejä testattavaan arvoon. Esimerkiksi algoritmi, joka käyttää vertaa ja vaihtaa osoittimissa, voi käyttää osoitteen alempia bittejä tarkistaakseen, kuinka monta kertaa osoitinta on muutettu. Tämän vuoksi seuraava vertailu ja vaihto ei toimi, koska merkkibitit eivät täsmää. Tämä ei ratkaise ongelmaa täysin, koska tunnistebittien arvo voi käydä läpi nollakierroksen . Jotkut arkkitehtuurit tarjoavat kahden sanan vertaile ja vaihto -ominaisuuden , joka mahdollistaa suuremman tarran. Tätä kutsutaan yleensä nimellä ABA', koska A:n toinen arvo on hieman erilainen kuin ensimmäinen.

Oikea mutta kallis lähestymistapa on käyttää välisolmuja, jotka eivät ole käyttäjätietoja, mutta tarjoavat invarianssia lisäys- ja poistotoimintoihin. [Valois].

Toinen lähestymistapa on käyttää yhtä tai useampaa vaaraosoitinta ( hazard -indikaattoria) - osoittimia, jotka periaatteessa eivät voi esiintyä tietorakenteessa. Jokainen vaaraosoitin osoittaa rakenteen välitilaa muutosprosessissa; osoittimien saaminen vaatii lisäsynkronointia ( Dag Lee ).

Jotkut arkkitehtuurit tarjoavat "laajennettuja" atomioperaatioita, jolloin esimerkiksi on mahdollista atomisesti muuttaa molempia viitteitä kerralla, eteenpäin ja taaksepäin, kaksoislinkitetyssä luettelossa.

Jotkut arkkitehtuurit tarjoavat kuormitukseen linkitetyn tallennuksen ehdollisen käskyn , jossa soluun voidaan kirjoittaa vain, jos määritettyyn soluun ei ole kirjoitettu muita kirjoituksia. Tämä erottaa tehokkaasti "solu sisältää arvon" -ominaisuuden "solu on muutettu" -ominaisuudesta. Arkkitehtuuriesimerkkejä ovat ARM , DEC Alpha , PowerPC .

Kirjallisuus

  1. Damian Dechev, Peter Pirkelbauer ja Bjarne Stroustrup. Lukitsemattomat dynaamisesti kokoa muuttavat taulukot
  2. Julian M Bucknall, Lukitsemattomat tietorakenteet: pino. [yksi]

Linkit