Atomiset operaatiot.

HepHep!

Sorsat saatavilla reposta
http://xp-dev.com/svn/MazBotV4/branches/oldprojects/atomic_example.tar.gz

Nyt mukaan pakettiin livautettu myös esimerkkisorsa, jossa käytetään ++ - operaatiota tavalliseen muuttujaan ja atomista operaatiota. Näitä muuttujia käsitellään esimerkissä 10 - säikeestä, ja ainakin minun koeajoissa nähtiin miten normaalin globaalin kasvattaminen ++-operaatiolla, ei ollut turvallinen monisäikeisessä ympäristössä.



Säikeistä (aiheen pohjustus)

Tunnen suurta syyllisyyttä siitä, että esittelin blogissani säikeet eli threadit. Ne ovat kuin Star Warsin "voiman", paha, "pimeä puoli". Niiden käyttöön on helppo lipsahtaa. Ne houkuttelevat siinä aivan käden ulottuvilla, tarjoten nerokkaalta tuntuvia ratkaisuja - ja kun kerran kokeilet, jäät helposti koukkuun.

No joo. Hieman karrikoitua, sitäpaitsi tälläkertaa en aikonut kirjoittaa säikeistä varsinaisesti, mutta kun kerran atomiset operaatiot liittyvät kiinteästi säikeisiin, kirjoitetaan nopeasti ylös muutamia asioita joita on hyvä pitää mielessä...

Säikeet siis tarjoavat tavan suorittaa näennäisen yhtäaikaisesti useampaa kohtaa ohjelmakoodissa. Toisinaan tämä auttaa yksinkertaistamaan asioita merkittävästi. Yhden säikeen voi esim. luoda odottamaan käyttäjältä syötettä, toisen säikeen suorittaessa taustalla jotain tarpeellista tehtävää. Miksi sitten avasin tekstini syyttämällä säikeitä maailman suurista onnettomuuksista?

Vaikka säikeet tuntuvat helpolta tavalta hanskata blokkaavat I/O kutsut ja tehdä monia yhdenaikaisia toimenpiteitä, on säikeissä omat nurjat puolensa.

Synkronointi.
Joskus asioita vaan tulee tehdä tietyssä järjestyksessä. Maitoa ei voi kaataa lasiin, ennen kuin purkki on avattu. Uunin peltejä ei voi laittaa kiinni, ennen kuin tuli on sammunut. Ja ehkä tyypillisimmillään ohjelmoinnissa, palvelua ei voida käyttää, ennen kuin se on alustettu (palautuu yleensä siihen seikkaan, että muistiin ei voi kirjoittaa ennen kuin se on varattu) jne. Käytettäessä useampia säikeitä, eri säikeiden suoritusjärjestys uskotaan schedulerin haltuun. Ts. suoritusjärjestys on jokseenkin epämääräinen, ja voi vaihdella ajokerrasta toiseen. Tyypillisesti tässä käytetään apuna semaforeja, mutexeja ja conditional variableja.

Yhteisten resurssien suojaus.
Eli mikäli useampi kuin yksi säie päivittää jotain yhteistä resurssia (esim, globaalia muuttujaa), voi tulla ongelmia jolloin säikeet ovat päivittämässä samaa paikkaa yhtäaikaa. Perusesimerkkinä globaalin muuttujan lisäys yhdellä - mutta aloitankin varsinaisen "atomic operation" matskun sillä, jahka sinne asti pääsen.

Ja viimeisenä, mutta ei varmastikkaan mitenkään vähäpätöisenä tulee

ohjelman vikojen korjaus ja ylläpito.
Totuushan on, että virheetöntä koodia ei ole, käytettiin säikeitä tai ei. Mutta se mikä monisäikeisessä ohjelmassa saa hiukset nousemaan pystyyn, ja naaman kalpenemaan, on "viuhupointterin" löytämisen hankaluus. Verrattaessa useassa säikeessä ajettavaa ohjelmaa, esim. useassa prosessissa ajettavaan, huomataan yleensä ensimmäisenä se, että saman prosessin kaikilla säikeillä on pääsy kaikkien säikeiden osoiteavaruuteen. Prosesseillahan tuo osoiteavaruus on suojattu. Eli sen lisäksi että globaalit muuttujat on käytössä kaikissa säikeissä, voidaan osoittimilla sohia sujuvasti toisten säikeiden pinoihin (ja luonnollisesti sinne yhteiseen kekoon). Datan jakaminen on siis helppoa, mutta myös koodiin lipsahtanut viuhupointteri saattaa sujuvasti muuttaa dataa toisen threadin tontilta, saaden aikaan merkillisiä vikoja jossain ihan muualla kuin siellä missä viuhupointteri on. Hankalampaa kuin prosessien kanssa sanon minä, sillä mikäli viuhupointteri osoittaisi toisen prosessin osoiteavaruuteen, saataisiin välittömästi generoitua SIGSEGV eli segmentation faultti (tai access violation wintoosalla).

No niin... Siinäpä sitä säieasiaa jo tulikin, kirjoitukseen jonka ei ollut tarkoitus käsitellä säikeitä...

Miksi atomisuus??

Aiemmin mainitsin ongelman, jossa kaksi säiettä yrittää yhtä aikaa kasvattaa globaalia muuttujaa yhdellä. Siis kumpikin säie ajaa koodia

globaali++;

Mietitäänpä hetki. Mitä globaali++; oikeastaan tekee? Se:

1. lukee globaali muuttujan arvon muistista.
2. kasvattaa arvoa yhdellä.
3. kirjoittaa tuloksen takaisin globaali muuttujaan.

Jos kaksi säiettä nyt tekee tätä yhtäaikaa, voi lopputulos olla seuraava:

Säie1 aloittaa. Se:

lukee globaalin arvon
laskee globaali+1

ja nyt scheduleri päättääkin antaa säikeelle 2 vuoron edetä, ja pysäyttää säikeen 1.

säie 2 lukee globaali muuttujan arvon (joka siis on vielä sama minkä säie 1 luki)
säie 2 laskee globaali+1
ja kirjoittaa tuloksen muuttujaan globaali.

tovin päästä scheduleri antaa säikeelle 1 luvan jatkaa, ja se kirjoittaa edellä tekemänsä laskutoimituksen summan muuttujaan globaali, onnellisen tietämättömänä siitä, että säie 2 on kasvattanut globaalia välillä. Lopputulos siis uhmaa koulumatematiikkaa, ja jos oletetaan globaalin olleen alussa voikka 534, laskutoimituksen päättyessä, 534+1+1 = 535. Ja kun lisätään soppaan se, että tämä voi todellakin tapahtua vasta kun globaalia on päivitetty 534 kertaa onnistuneesti (mahdollisesti tuntien toiminnan jälkeen), ja se, että ohjelma ei välttämättä kaadu virheeseen.. Voihan olla että joka viidessadas pankkiautomaatilla laskuja maksava asiakas aikaansaa yhden sentin virheen pankin kirjanpidossa... ... ... ... Koetan vain sanoa, että vika on usein äärimmäisen vaikeaa paikantaa.

Edellinen esimerkki oli vieläpä äärimmäisen yksinkertainen. Todelliset ongelmat ovat usein paljon monimutkaisempia operaatioita, jota ei suotaisi katkaistavan.

Tässävaiheessa sivistyneempi teistä kahdesta lukijastani (se et edelleenkään ole sinä Vesa) lienee huomannut yhtäläisyyden kuvaamani ongelman ja sanan atominen kanssa. Atominen (atomic) tarkoittaa jakamatonta. Ja atominen operaatio siis operaatiota, jota ei voi jakaa... Eli, jos lue, lisää, kirjoita olisikin käsky, joka tapahtuisi "jakamattomasti" siten, että välissä ei voida tehdä muuta, olisimme autettuja.

Atomisuuden vaihtoehdot

Lääkettä vaivaan sanoi entinen mies kun loippaa otti. Ongelmaan onkin tarjolla useita ratkaisuja.

Keskeytysten disablointi.
Koodarinplanttu voi vetää scheduleria nenästä disabloimalla keskeytykset, jolloin scheduleri ei pääse scheduloimaan muita säikeitä / prosesseja ajoon. Kuulostaa hyvältä. Ikävä kyllä, keskeytysten disabloinnilla on sivuvaikutuksensa. Masiina nimittäin käyttää keskeytyksiä paljon muuhunkin, muunmuassa kommunikointiin raudan ja käyttöjärjestelmän välillä. Lisäksi monet operaatiot ovat riippuvaisia prosesseista, jotka ovat taustalla ajossa. Lisäksi voi koneessa pyöriä prosesseja, joiden on päästävä ajoon... Siis keskeytysten disabloinnin tulisi aina olla äärimmäisen lyhytkestoista, ja tällä välin ohjelmalla on rajoitettu määrä operaatioita käytettävissään... Ja... Vesakin varmaan tietää, että nykyään useissa koneissa on enemmän kuin yksi prosessori. Siis vaikka toisella prosessorilla scheduleri lukittaisiin, toisella prosessorilla voi ajoon päästä jotain, joka sotkee aristoteleen ympyrät...

Mutexit ja semaforit.
Niistä olenkin kertonut jo aiemmassa blogitekstissäni. Ja ne ovat nerokkaita viritelmiä - jotka useimmiten perustuvat atomisiin operaatioihin. Mutta mitä pidempään mutexi on yhdellä säikeellä lukossa, sitä kauemmin muut säikeet joutuvat odottelemaan. Puhumattakaan vaaroista kuten deadlockit ja starvation.

Atomiset operaatiot (Joo, nyt pääsin ihan oikeasti asiaan)

Onneksemme (oh, ylistäkäämme insinöörien nerokkuutta [minähän en muuten siihen sakkiin kuulu, toisin kuin Vesa]) suurin osa prosessoreista tukee muutamia ihan perustavanlaatuisia atomisia käskyjä, jotka voidaan asm:lla koodailla C-koodin joukkoon. (Eli useisiin prosessoreihin on rakennettu ihan "rautatuki" takaamaan tiettyjen yksinkertaisten operaatioiden keskeyttämättömyys). Ja kun muutama tällainen peruspalikka on käytössä, pystyy koodari kikkailemaan lisää käskyjä, jotka ulospäin näyttävät atomisilta.

Kaikki lhtee yleensä liikkeelle 32 bittisen (int) luvun kirjoittamisesta / lukemisesta muistiin/muistista. Onko siis luku / kirjoitus atominen? Savolainen osaisi varmasti sanoa tähän jotain näppärää ja tulkitsematonta, mutta minä sensijaan sanon, että: "Se vähän riippuu siitä, mistä se roikkuu."

Ok. Helpotetaan hiukan. Nykykoneilla joissa väylät ovat yleensä vähintään 32 bittisiä, luku ja kirjoitus on yleensä atomisia. Vanhemmilla/erikoisemmilla koneilla ei välttämättä. Pitempien lukujen kohdalla taas 32 bittiset koneet usein lukevat/kirjoitttavat kahdessa osassa, ja tällaisen luvun / kirjoituksen sekaan sössiminen usealla säikeellä, saa aikaan lukuja joissa on puolet yhtä, ja toinen puoli toista, eli jotka siis ovat ihan mitä sattuu. Ja 32 bittisiäkin lukuja jäsiteltäessä on hyvä muistaa, että kääntäjä saattaa optimoida koodia siten, että lukuja käytetäänkin rekistereistä tai cachesta... Tällaisten sekaannuksien välttämiseksi, atomisiin operaatioihin tarkoitetut muuttujat on hyvä höystää "volatile" avainsanalla, joka kertoo kääntäjälle, että olisi hyvin suotavaa, mikäli tämä luku pidettäisiin aina muistissa, eikä sitä optimoitaisi rekistereihin jne.

No niin Vesa, lopetappa se volatilen viljely, ja ota kääntäjän manuska karvaiseen kouraasi.

Volatile (ja register) sanoja kun käytetään oikeastaan vaan vihjeenä kääntäjälle. Osa kääntäjistä hoitaa homman kotiin, osa antaa palttua koodarin toiveille, ja osa jotain siltä väliltä. Kannattaa siis katsoa, ennen kuin katuu.

Compare and Swap

Oikeastaan tässä alkaa olla jo tarinaa joka vinkkaa oikeaan suuntaan, mutta paukutetaan vielä pari juttua. En nimittäin malta olla esittelemättä parasta kaveriani, atomista "CMS" eli "CompareAndSwap" käskyä. Joo Vesa, komealtahan se nimi kuulostaa, mutta se ei ollut syy miksi haluan esitellä juuri compare and swapin. Syy on se, että kun olet toteuttanut atomisen compare and swap käskyn, voit rakentaa sen avulla kokonaisen ison liudan muita atomisia käskyjä.

Compare and swap siis tekee seuraavan tempun. Se ottaa käyttäjältä parametreinaan muistiosoitteen, ja kaksi lukua. Se tarkistaa muistiosoitteen sisällön, vertaa sitä annettuun lukuun, ja mikäli sisältö on sama kuin annettu luku, se vaihtaa muistiosoitteen sisällön toiseen annettuun lukuun. Lopuksi se palauttaa arvon, joka kertoo tehtiinkö swap vai ei. Ja kaiken tämän vieläpä atomisesti. Paluuarvona on tyypillisesti joko true/false tai arvo joka muistipaikasta luettin. (Siis, jos muistipaikan sisältö oli sama kuin annettu vertailumuuttuja => uusi arvo kirjoitettiin => vertailumuuttujaa vastaava arvo palautetaan. Muuten palautettava arvo on eri kuin vertailuarvo).

Todennäköisesti lähes kaikki nykyiset prosessorit tukevat atomista CMS käskyä. Ainakin x86, AMD ja ne PPC prosessorit joihin olen törmännyt.

Uusien atomisten käskyjen rakentelu

No niin. Mainitsinkin jo, että CMS käskyn avulla voidaan toteutta useita hienoja atomisia operaatioita. Vesakin voi lopettaa nauramisen, se ei ollut vitsi. Atomisuus on siis käsite, joka toteuttaa seuraavat ehdot.

Jokin sarja operaatioita voidaan suorittaa siten, että ympäröivä maailma ei tiedä muutoksista joita se aiheuttaa ennen kuin se on kokonaisuudessaan päättynyt.
Ja jos jossakin operaation vaiheessa sössitään, koko operaatio epäonnistuu jälkiä jättämättä.

CMS:ää hyödyntäen voidaan nyt seuraavalla kaavalla toteutta iso joukko erilaisia:
"vertaa/manipuloi muistipaikassa olevaa dataa, ja kirjoita tulos takaisin muistiin"
operaatioita, jotka ovat ulospäin atomisia.

1. lue muistipaikan alkuperäinen arvo, ja talleta se väliaikaiseen muuttujaan.
2. vertaile / manipuloi dataa (toisessa väliaikaisessa muuttujassa)
3. Tee compareAndSwap, josa vertaat muistipaikassa tällähetkellä olevaa arvoa arvoon, joka siellä oli atomista funktiotasi kutsuttaessa. Laita swapattawaksi arvoksi manipulointisi tulos.
Toista loopissa kunnes swap onnistuu.

Eli, mikäli jokin muu säie pääsi muuttamaán muistipaikassa olevaa arvoa manipuloinnin/vertailun aikana, compare and swap funktiossa alkuperäinen, talletettu arvo ja manipuloinnin jälkeinen arvo eivät täsmää (operaatio ei ollut atominen) => swap ei onnistu. => uusi yritys.

Jos taas swap onnistuu, se tarkoitta, että kukaan ei kesken operaation käpistellyt muistipaikan sisältämää dataa, ja operaatio oli siis atominen.


Ja tässä vielä loppuhöysteenä tuo paljon hypettämäni compare and swap, ix86 prosessorille. (muistakaa, että intti jonka osoite funktiolle annetaan TÄYTYY olle volatile).

int __INLINE__ atominenCAS( int *ptr, int cmp, int new)
{
unsigned char ret;

__asm__ __volatile__ (
" lock\n"
" cmpxchgl %2,%1\n"
" sete %0\n"
: "=q" (ret), "=m" (*ptr)
: "r" (new), "m" (*ptr), "a" (cmp)
: "memory");

return ret;

}