Synkronointi (ohjelmointi)

Kohteesta Wikipedia
Siirry navigaatioon Siirry hakuun
Tämä artikkeli käsittelee tietotekniikan ja ohjelmoinnin käsitettä synkronoinnista. Tietoliikenteen ja signaalikäsittelyn synkronointi on eri käsitteet.

Synkronointi (engl. synchronization) tietokoneen ohjelmoinnissa tarkoittaa hallittua synkronointimekanismia rinnakkaisten ohjelmien välisen tiedon käsittelyyn.

Synkronointia tarvitaan, jotta kahden rinnakkain samanaikaisesti tapahtuvan muutoksen välillä ei synny kilpatilannetta (engl. race condition), jolloin ohjelmat voivat päivittää yhtä aikaa samaa muuttujaa tai tietorakennetta, mikä yleensä johtaa virheeseen. Tämän takia käyttöjärjestelmä tarjoaa mekanismeja resurssien hallittuun synkronointiin (engl. synchronization).

Kilpatilanne voi syntyä myös yhden suorittimen järjestelmässä riippuen säikeiden ja prosessien vuoronnuksesta (context switch) sekä laitteistokeskeytyksien käsittelystä.[1][2]

Nykyisin käytettävät lukottomat synkronointimekanismit välttävät suuren osan aiemmin tunnetuista ongelmista. Lukottomia menetelmiä ovat atomiset operaatiot sekä Read-Copy-Update (RCU) mekanismi.

Synkronointimekanismit[muokkaa | muokkaa wikitekstiä]

Kolme prosessia käyttämässä jaettua resurssia samanaikaisesti (kriittinen alue).
Prosessi käyttämässä jaettua resurssia sen ollessa saatavilla synkronointimekanismin avulla.

Synkronointimekanismit tai synkronointiprimitiivit[3][4][5][6][7][8][9][10][11][12][13] ovat sopimuspohjaisia siten, että ohjelmakoodia tehtäessä on tunnistettava mitä muuttujia ei saa muokata lukituksen ollessa voimassa. Lukituksen käsittely tarvitaan sekä lukevalle että kirjoittavalle puolelle jotta molemmilla on käsitys milloin lukitus on voimassa.

Synkronointiin käytettäviä mekanismeja ovat spinlock, barrier, semaforit, (engl. semaphore) poissulkeminen (engl. mutual exclusion) ja kriittinen alue (engl. critical section, critical region), joilla varmistetaan, että vain yksi säie tai prosessi voi kerrallaan käsitellä yhteisiä muuttujia.

Eri mekanismeilla voi olla suorituskyvyn kannalta merkitystä lukituksen haastamisen (engl. contention) kannalta.[14]

Spinlock[muokkaa | muokkaa wikitekstiä]

Spinlock nimensä mukaisesti tarkastelee lukitusmuuttujaa kunnes se voi varata lukituksen. Tästä voi aiheutua busy-wait tilanne, mutta menetelmää yhä käytetään sen yksinkertaisuuden vuoksi.[15] Sekventiaaliset lukitukset (Seqlocks) ovat spinlockien variaatio, joka huomioi erikseen kirjoituksen ja lukituksen antaen kirjoitukselle korkeamman prioriteetin.[16]

Barrier[muokkaa | muokkaa wikitekstiä]

Barrier on esto, joka rajaa mm. kääntäjän tai suorittimen tekemän uudelleenjärjestelyn[17] varmistaen että tietty ohjelmakoodi suoritetaan sitä ennen.[17][18] Tähän voidaan liittää myös välimuistin tyhjentäminen keskusmuistiin (ks. välimuistin yhtenäisyys) ja muita toimintoja. Etenkin moniprosessointi voi vaatia mekanismia.[19]

Semafori[muokkaa | muokkaa wikitekstiä]

Semafori on kahden "suunnan" menettely, jossa lasketaan lukituksen ottaneet ja lukituksen vapauttaneet: kun lukituksen ottaneita on enemmän kuin lukituksen vapauttaneita muutoksia ei saa tehdä synkronoitavaan tietoon.[18] Linuxin toteutus laskee sekä lukituksen ottaneet että odottajat.[18][16]

Turnstile[muokkaa | muokkaa wikitekstiä]

Turnstile tai kääntöportti on Solaris käyttöjärjestelmän toteuttama synkronointimenetelmä.[20]

Poissulkeminen[muokkaa | muokkaa wikitekstiä]

Poissulkeminen on yleinen prosessien välillä käytetty synkronointi. Monet menetelmät toimivat vain säikeiden välillä nopeusedun vuoksi, mutta yleiset tietokoneresurssit kuten sarjaportti voivat vaatia varmistuksen että muiden prosessien säikeet eivät myöskään pääse käsittelemään samaa resurssia samaan aikaan.[1] Linux toteuttaa mutex tyypin lisäksi futex poissulkemisen, joka on nopeampi mutta kernelin sisäisiin toimintoihin rajoitettu.[18]

Poissulkeminen voi olla verrattain raskas ja hidas operaatio ja ohjelman sisäiseen synkronointiin käytetään tyypillisesti muita menetelmiä kuten kriittisiä alueita.[21][22]

Kriittinen alue[muokkaa | muokkaa wikitekstiä]

Kriittinen alue (engl. Critical Section) on ohjelmalohko, joka on suoritettava sen loppuun asti ennen luovuttamista toiselle suorittajalle.[16][23]

Prosessin sisäisen suorituksen synkronointiin kriittinen alue voi olla tehokkaampi vaihtoehto kuin poissulkeva mutex.[22]

Termiä käytetään synkronointiprimitiivin[23] lisäksi myös synkronoinnilla suojatusta ohjelmalohkosta.[24]

Atomisuus[muokkaa | muokkaa wikitekstiä]

Atomisilla operaatioilla voidaan tehdä ohjelmointikielen (ja laitteiston) tukemana automaattisesti suojattuja (synkronoituja) tai lukottomia muuttujia, joilla voidaan välttää kilpatilanteita.[18][25][1]

Muun muassa C++11 lisää ohjelmointikieleen tuen atomisille operaatioille (ISO/IEC 14882:2011). Atomisilla operaatioilla voidaan toteuttaa korkeamman tason synkronointitoimintoja.[26]

Atomiset operaatiot voivat parantaa suorituskykyä huomattavasti verrattuna perinteisiin synkronointimenetelmiin.[27]

Microsoft on käyttänyt atomisista toiminnoista nimitystä lomittuvat toiminnot (engl. interlocked operations).[28]

Atomisuutta käytetään synkronointiprimitiivien lisäksi myös muualla kuten tietokantojen ACID-periaatteessa sekä tiedostojärjestelmän toimintaperiaatteiden kuvauksissa, jotka ovat eri tason käsitteitä.

ReaderWriterLock[muokkaa | muokkaa wikitekstiä]

ReaderWriterLock on Microsoftin synkronointiprivimitiivi, joka sallii useamman lukevan säikeen mutta vaatii kirjoittavan säikeen odottavan poissulkevaa lukitusta.[3][29]

Read-Copy-Update[muokkaa | muokkaa wikitekstiä]

Read-Copy-Update (RCU) mekanismi on Linuxissa käytetty skaalautuva mekanismi.[30] RCU:n etu on äärimmäisen nopea lukeminen harvoin päivitettäville tiedoille.[30]

RCU on immuuni deadlock tilanteelle ja se on lähtöisin Sequentin DYNIX/ptx ytimestä, jossa RCU:n käytöllä vähennettiin huomattavasti deadlockin välttämiseen tarkoitettua ohjelmakoodia.[31] Mekanismia on käytetty myös IBM:n tutkimusalustassa K42.[32]

Mekanismi käyttää elävän (luettavissa olevan) ja kuolleen (muokattavissa olevan) muuttujan periaatetta.[33]

Koska menetelmä käyttää eri operaatioita lukevalle ja kirjoittavalle puolelle tähän viitataan myös reader-writer locking konseptina, mutta sillä korvataan Linuxissa käytettyä read-write lock mekanismia (rwlock).[34]

RCU:sta on tehty esitys C++:n ISO-standardointiin liittyen.[35]

Keskeytyskäsittely[muokkaa | muokkaa wikitekstiä]

Laitteistokeskeytyksien pysäyttäminen kriittisen alueen ajaksi on yksi reaaliaikajärjestelmien käyttämä menetelmä.[36]

Synkronointivirheet[muokkaa | muokkaa wikitekstiä]

Rinnakkaiset ohjelmat voivat joutua myös odottamaan toisiaan jolloin säikeet estävät toisiaan (engl. block).

Väärin tehty ohjelma voi lukkiutua (engl. deadlock). Lukkiutumistilanteessa prosessit odottavat tosiaan, eikä yksikään niistä pääse etenemään.[1]

Nälkiintyminen tai nääntyminen (engl. starvation) on tilanne, jossa ainakin yksi prosessi jatkuvasti jää ilman suoritinaikaa, vaikka varsinaista lukkiutumista ei esiinnykään – järjestelmä siis ainakin osittain toimii kuten pitääkin.

Priority inversion tilanne on ongelmallinen vuoronnetuissa järjestelmissä, joissa korkean prioriteetin säie voi joutua odottamaan matalan prioriteetin säiettä vapauttamaan varatun resurssin, mutta matalan prioriteetin säie ei saa riittävästi ajoaikaa.[36]

Käytetystä synkronointimenetelmästä riippuen järjestelmä voi olla myös herkkä busy-wait tilanteelle, jossa suoritinaikaa käytetään paljon odotettavan lukituksen tilan tarkisteluun. Etenkin spinlock synkronointi voi aiheuttaa tämän tilanteen.[15]

Synkronointituki[muokkaa | muokkaa wikitekstiä]

Itse alustakohtaisen tuen lisäksi eräissä ohjelmointikielissä on niiden standardikirjastossa toteutus alustakohtaiselle synkronointimekanismille, joka käyttää samaa rajapintaa eri alustoilla.

Esimerkiksi C++11 lisäsi std::mutex toteutuksen kielen standardikirjastoon. C11 lisäsi säikeistyksen tuen mukaan lukien synkronointituen.

Käyttö[muokkaa | muokkaa wikitekstiä]

Esimerkki synkronoinnin käyttötapauksesta:

Sync valuelock;
int myValue;

void write_value(int scalarvalue)
{
   valuelock->lock();
   myValue = scalarvalue;
   valuelock->release();
}

int read_value()
{
   int current_value;

   valuelock->lock();
   current_value = myValue;
   valuelock->release();

   return current_value;
}

Huomaa, että tämä esimerkki olettaa synkronointiprimitiivin odottavan kunnes lukitus onnistuu ja voi pysäyttää säikeen suorituksen pitkäksi aikaa.

Esimerkki demonstroi miten lukittavan arvon käsittely on oltava sekä luku- että kirjoituspuolella sopimuskäytännön mukaisesti.

Katso myös[muokkaa | muokkaa wikitekstiä]

Lähteet[muokkaa | muokkaa wikitekstiä]

  1. a b c d Jones, M. Tim: Anatomy of Linux synchronization methods IBM. Viitattu 21.2.2017.
  2. Kernel Synchronization cs.utexas.edu. Viitattu 21.2.2017.
  3. a b Overview of Synchronization Primitives Microsoft. Viitattu 2.3.2017.
  4. Schulzrinne, Henning: Synchronization primitives cs.columbia.edu. Viitattu 2.3.2017.
  5. Synchronization primitives in the Linux kernel. 0xax.gitbooks.io. Viitattu 2.3.2017.
  6. Synchronization Primitives: Implementation and Examples inst.eecs.berkeley.edu. Viitattu 2.3.2017.
  7. Lecture 4: Synchronization Primitives cs.brown.edu. Viitattu 2.3.2017.
  8. 18.5.7. Synchronization primitives docs.python.org. Viitattu 2.3.2017.
  9. Choosing Between Synchronization Primitives Intel. Viitattu 2.3.2017.
  10. Synchronization primitives qnx.com. Viitattu 2.3.2017.
  11. Synchronization Primitives Apple. Viitattu 2.3.2017.
  12. ARM® Synchronization Primitives Development Article ARM. Viitattu 2.3.2017.
  13. Synchronization primitives IBM. Viitattu 2.3.2017.
  14. Dillon, Matt: Multi-Processing Basics for a *real* multi-processing system. groups.google.com. Viitattu 2.3.2017.
  15. a b Blieberger, Johann & Burgstaller, Bernd & Scholz, Bernhard: Busy Wait Analysis complang.tuwien.ac.at. Viitattu 21.2.2017.
  16. a b c Chapter 5. Kernel Synchronization linux.linti.unlp.edu.ar. Viitattu 21.2.2017.
  17. a b McKenney, Paul E.: Memory Ordering in Modern Microprocessors rdrop.com. Viitattu 21.2.2017.
  18. a b c d e Yang, Junfeng: W4118 Operating Systems cs.columbia.edu. Viitattu 21.2.2017.
  19. McKenney, Paul E.: Memory Barriers: a Hardware View for Software Hackers 7.6.2010. Viitattu 2.3.2017.
  20. Turnstiles and priority inheritance sunsite.uakom.sk. Viitattu 21.2.2017.
  21. MSVC mutex is slower than you might expect stoyannk.wordpress.com. Viitattu 2.3.2017.
  22. a b Always Use a Lightweight Mutex preshing.com. Viitattu 2.3.2017.
  23. a b Critical Section Objects Microsoft. Viitattu 2.3.2017.
  24. Arpaci-Dusseau, Remzi H. & Arpaci-Dusseau, Andrea C.: Concurrency: An Introduction pages.cs.wisc.edu. Viitattu 2.3.2017.
  25. Atomic Operations Intel. Viitattu 2.3.2017.
  26. *Stroustrup, Bjarne: The C++ Programming Language, 4th ed.. Addison-Wesley, 2015. ISBN 0-321-56384-0.
  27. Comparison: Lockless programming with atomics in C++ 11 vs. mutex and RW-locks arangodb.com. Viitattu 9.2.2017.
  28. Interlocked Operations Microsoft. Viitattu 2.3.2017.
  29. Reader-Writer Locks Microsoft. Viitattu 2.3.2017.
  30. a b McKenney, Paul: What is RCU, Fundamentally? LWN. Viitattu 21.2.2017.
  31. McKenney, Paul E. & Boyd-Wickizer, Silas & Walpole, Jonathan: RCU Usage In the Linux Kernel: One Decade Later eecg.toronto.edu. Viitattu 2.3.2017.
  32. Notes on Read-Copy Update read.seas.harvard.edu. Viitattu 2.3.2017.
  33. McKenney, Paul E. & Sarma, Dipankar & Arcangeli, Andrea & Kleen, Andi & Krieger, Orran & Russell, Rusty: Read Copy Update kernel.org. Viitattu 2.3.2017.
  34. McKenney, Paul: What is RCU? Part 2: Usage LWN. Viitattu 2.3.2017.
  35. McKenney, Paul E.: Read-Copy Update (RCU) for C++ open-std.org. Viitattu 2.3.2017.
  36. a b Khushu, Sanjeev & Simmons, Johnathan: Scheduling and Synchronization in Embedded Real-Time Operating Systems cseweb.ucsd.edu. Viitattu 20.2.2017.

Aiheesta muualla[muokkaa | muokkaa wikitekstiä]

Käännös suomeksi
Tämä artikkeli tai sen osa on käännetty tai siihen on haettu tietoja muunkielisen Wikipedian artikkelista.
Alkuperäiset artikkelit: en:Synchronization (computer science) & en:Lock (computer science)