Mitä on rinnakkaisohjelmointi ja miten sitä hallitaan

Rinnakkaisohjelmoinnista on tullut keskeinen osa modernia ohjelmistokehitystä: käyttöjärjestelmät, web-palvelimet, mobiilisovellukset, videopelit, tietokannat… lähes kaikki päivittäin käyttämämme suorittaa useita tehtäviä samanaikaisesti, tai ainakin näyttää siltä. Vahva ymmärrys siitä, miten tämä ohjelmointitapa toimii, miten se eroaa rinnakkaisohjelmoinnista ja mitä haasteita se tuo mukanaan, on välttämätöntä vankan ja tehokkaan koodin kirjoittamiseksi.

Seuraavissa riveissä erittelemme tarkalleen, mitä samanaikaisuus on, miten sitä mallinnetaan prosessi- ja säiketasolla, mitä malleja on olemassa (säikeet, korutiinit, toimijat, tapahtumasilmukat jne.) , mitä tyypillisiä virheitä esiintyy (kilpailutilanteet, lukkiutumat, nälkiintyminen, väärä jakaminen jne.) ja mitä työkaluja meillä on samanaikaisten järjestelmien synkronointiin ja varmentamiseen. Huomaat, että teorian lisäksi kaikella tällä on erittäin käytännön sovellus todellisessa ohjelmistosuunnittelussa.

Mitä on rinnakkaisohjelmointi ja miten se eroaa rinnakkaisohjelmoinnista?

Kun puhumme samanaikaisuudesta, viittaamme järjestelmän kykyyn hallita useita tehtäviä, joiden elinkaaret menevät päällekkäin , joten niiden suoritusvaiheet limittyvät toisiinsa. Keskeinen käsite on looginen päällekkäisyys: ohjelmoijan näkökulmasta useat toiminnot ovat "suorassa" samanaikaisesti, vaikka fyysisesti yksi prosessori voi suorittaa vain yhden käskyn kerrallaan.

Suoritus on organisoitu lomitusprosessina : ajoittaja varaa pieniä osia suorittimen ajasta kullekin tehtävälle. Se suorittaa osan tehtävästä A, siirtyy sitten tehtävään B, sitten tehtävään C ja palaa myöhemmin tehtävään A, aina ottaen huomioon datariippuvuudet. Samanaikainen ohjelmointi on siis tapa jäsentää ohjelmia useiksi lähes itsenäisiksi aktiviteeteiksi , joten niiden lomitusjärjestys ei ole ehdottoman kiinteä.

Rinnakkaisuus on toinen juttu: tässä puhumme useista tehtävistä, jotka kirjaimellisesti suoritetaan samaan aikaan eri ytimillä tai prosessoreilla ( halliten suorittimen ytimiä ). Järjestelmä voi olla samanaikainen, mutta ei rinnakkainen (yksi ydin vaihtaa tehtäviä) tai sekä samanaikainen että rinnakkainen (useita ytimiä suorittamassa joitakin näistä samanaikaisista säikeistä tai prosesseista rinnakkain).

Käytännössä samanaikaisuus pyrkii mallintamaan ongelmia, joissa useita asioita tapahtuu samanaikaisesti (verkkopyynnöt, käyttäjien klikkaukset, levyn tai verkon I/O, anturit jne.), kun taas rinnakkaisuus keskittyy raskaiden laskelmien nopeuttamiseen jakamalla ne samanaikaisesti suoritettaviin aliohjelmiin. Yksittäinen samanaikainen suunnittelu voi toimia pelkästään lomitettuna tai hyödyntää todellista rinnakkaisuutta, jos laitteistossa on useita ytimiä.

Prosessit, säikeet ja suoritustilat

Käyttöjärjestelmässä samanaikaisuuden tukemisen peruskonsepti on prosessi . Prosessi ei ole vain levyllä oleva suoritettava tiedosto: se on aktiivinen yksikkö, jolla on oma suoritustila. Se sisältää ohjelmalaskurin (CPU-rekisteri, joka osoittaa seuraavaan suoritettavaan käskyyn), prosessipinon ( funktion parametrit, paluuosoitteet, paikalliset muuttujat jne.), dataosan (globaalit muuttujat, staattinen data) ja keon, johon dynaaminen muisti allokoidaan ajonaikana.

Levylle tallennettu binääritiedosto on vain passiivinen ohjelma , käskyjen ja datan sarja. Jotta ohjelma "herää eloon", käyttöjärjestelmän on luotava prosessi, alustettava sen konteksti (rekisterit, muisti, tiedostokuvaajat jne.) ja ajoitettava se vastaanottamaan suorittimen aikaa.

Prosessin tilat

Prosessi käy läpi erilaisia ​​suoritustiloja ollessaan olemassa , jotka ovat yleensä ainakin seuraavat:

• uusiJärjestelmä luo prosessin ja konfiguroi sen sisäisiä rakenteita.
• JuoksuProsessilla on CPU ja sen ohjeita suoritetaan.
• Estetty tai odotustilassaprosessi odottaa tapahtuman sattumista (syöttö/tulos, toiminnon loppu, viestin saapuminen…).
• Valmis tai valmisteltuSiinä on kaikki tarvittava toimiakseen, mutta se odottaa vuoroaan prosessorilla.
• päättynytSen suoritus on päättynyt ja järjestelmä vapauttaa resurssejaan.

Käyttöjärjestelmän ajoitusohjelma päättää näiden tilojen välisen vaihdon käytäntönsä (round robin, prioriteetit jne.) mukaisesti tasapainottaen suorittimen käyttöä, viivettä ja prosessien välistä oikeudenmukaisuutta.

Prosessinohjauslohko (PCB)

Kutakin prosessia edustaa ytimessä PCB:nä (Process Control Block) tunnettu tietorakenne . Tämä lohko on prosessin "tiedosto", ja se tallentaa kaikki tarvittavat tiedot sen pysäyttämiseksi ja jatkamiseksi menettämättä mitään.

Piirilevy tallentaa prosessin tilan (uusi, valmis, käynnissä, estetty jne.), nykyisen ohjelmalaskurin , suorittimen rekisterit (joiden lukumäärä ja tyyppi riippuvat arkkitehtuurista), ajoitustiedot (prioriteetti, osoittimet valmiusjonoihin, käyttötilastot ) ja muistinhallintatiedot (sivutaulukot, segmenttitaulukot jne.). Tämä mahdollistaa käyttöjärjestelmän suorittaa kontekstivaihtoja eli tallentaa yhden prosessin koko tilan ja palauttaa toisen tilan.

Säikeet ja monisäikeiset

Prosessien lisäksi monet käyttöjärjestelmät tarjoavat suoritussäikeitä . Säie on suorittimen käytön perusyksikkö: sillä on oma tunniste, ohjelmalaskuri, rekisterit ja pino, mutta se jakaa koodiosan, dataosan ja muita resursseja, kuten tiedostokuvauksia, saman prosessin muiden säikeiden kanssa.

Monisäikeisessä ohjelmassa useat säikeet voivat suorittaa saman koodin eri osia rinnakkain tai lomitettuina . Jokainen säike ylläpitää omaa pinoaan (paikallisine muuttujineen ja kutsukontekstineen), mutta kaikki näkevät saman prosessiosoiteavaruuden. Tämä helpottaa kommunikointia (jakamalla muistia) samanaikaisuusriskien, kuten kilpailutilanteiden, kustannuksella.

Tyypillisessä monisäikeisessä suunnittelussa prosessilla on yksi piirilevy ja yksi osoiteavaruus, kun taas jokainen säie lisää oman pino- ja rekisterikontekstinsa . Käyttöjärjestelmä (tai kielen ajonaikainen ympäristö) toteuttaa ennaltaehkäisevän mallin: se voi keskeyttää säikeen milloin tahansa ja antaa suorittimen toiselle, pakottaen ohjelmoimaan ymmärtäen, että säikeesi voidaan keskeyttää kahden näennäisesti "atomimaisen" käskyn väliin.

Moniohjelmointi, moniprosessointi ja hajautettu prosessointi

On hyödyllistä erottaa toisistaan ​​useita samanaikaisen suorituksen tasoja. Moniohjelmointi sallii useiden prosessien sijaita muistissa ja suorittaa vuorotellen yhden suorittimen prosessoria; ne eivät koskaan toimi aidosti rinnakkain, vaan pikemminkin lomitettuina.

Moniprosessointi (tai monisäikeistäminen ) käyttää kahta tai useampaa prosessoria tai ydintä samassa koneessa yhden tai useamman prosessin suorittamiseen, mikä saavuttaa todellisen rinnakkaisuuden. Jokainen ydin voi käsitellä eri säiettä samanaikaisesti, mikä moninkertaistaa suorituskyvyn useissa työkuormissa (katso Intelin ja AMD:n tärkeimmät uutiset suorittimista).

Hajautettu prosessointi vie tämän askeleen pidemmälle: yksi tai useampi prosessi suoritetaan eri tietokoneilla, jotka on yhdistetty verkkoon . Tämä tuo mukanaan lisäongelmia (latenssi, osittaiset viat, verkon osiointi), mutta käsitteellinen malli pysyy samanaikaisena: monia meneillään olevia toimintoja, jotka on koordinoitava.

Samanaikaiset ohjelmointimallit: säikeet, korutiinit, tapahtumasilmukat ja toimijat

Rinnakkaisuutta ei aina ohjelmoida samalla tavalla. On olemassa useita rinnakkaisohjelmointimalleja , joista jokainen tarjoaa erilaisia ​​abstraktioita ja tasapainottaa helppokäyttöisyyttä, suorituskykyä ja rinnakkaisuutta eri tavoin. Yleisimpiä ovat järjestelmäsäikeet, korutiinit, tapahtumasilmukat ja toimijamalli.

Korutiinit

Korutiini on eräänlainen yhteistyöhön perustuva samanaikaisuus käyttöjärjestelmän yksittäisessä säikeessä . Toisin kuin perinteisissä säikeissä, joissa käyttöjärjestelmän ajoitus päättää, milloin keskeytetään ja jatketaan, korutiinit luopuvat hallinnasta nimenomaisesti, kun ajoitus ilmoittaa niin (esimerkiksi odottaessaan I/O:ta tai kun osa tehtävästä on valmis).

Tätä mallia kutsutaan yhteistyömalliksi , koska jokainen korutiini on suunniteltava "käyttäytymään hyvin": sen on luovuttava suorituksesta sopivissa kohdissa välttääkseen muiden estämisen. Vastineeksi korutiinin konteksti on paljon kevyempi kuin säikeen: monet korutiinit voivat sijaita yhden järjestelmäsäikeen sisällä ja jakaa pinon tai käyttää hyvin pieniä pinoja.

Oletusarvoisesti korutiinit mallintavat samanaikaisuutta ilman rinnakkaisuutta : ne kaikki lomitetaan yhden säikeen sisällä. Monet nykyaikaiset ajonaikaiset ympäristöt kuitenkin mahdollistavat niiden yhdistämisen useisiin säikeisiin todellisen rinnakkaisuuden saavuttamiseksi tarvittaessa. Käsitteet, kuten promises/futures tai async/await, integroidaan usein luonnollisesti tähän malliin.

Tapahtumasilmukka

Toinen erittäin vaikuttava malli on tapahtumasilmukka . Tässä lähestymistavassa on yleensä yksi säie, joka ylläpitää keskitettyä silmukkaa, jossa tapahtumat (verkon datan saapuminen, ajastimet, käyttäjän syötteet jne.) käsitellään ja ennalta rekisteröidyt takaisinkutsut suoritetaan reagoimaan kuhunkin tapahtumatyyppiin.

Sitä kutsutaan viivästetyn eston malliksi , koska sen sijaan, että esto tapahtuisi I/O:ta odotettaessa, operaatiot rekisteröivät käsittelijän, joka suoritetaan, kun tapahtuma tapahtuu silmukkasyklin lopussa. Tämä mahdollistaa useiden samanaikaisten toimintojen kuvaamisen yhdessä säikeessä, välttäen säikeiden välisen synkronoinnin monimutkaisuuden ja tarjoten erittäin tehokkaan suorittimen käytön.

Oletusarvoisesti tämä malli tarjoaa samanaikaisuuden, mutta ei rinnakkaisuutta (kaikki tapahtuu samassa säikeessä), vaikka monet alustat sallivat skaalautumisen useisiin säikeisiin tai prosesseihin konepellin alla. Keskeinen näkökohta on, että paikallinen muisti ja muuttujien laajuus käyttäytyvät hyvin samalla tavalla kuin peräkkäinen ohjelma, mikä vähentää kilpailutilanteiden riskiä.

Tapahtumasilmukoihin perustuvien API-rajapintojen suunnittelussa käytetään usein sulkemisia tai takaisinkutsuja tarvittavan ympäristön kaappaamiseen. Tämä voi johtaa tunnettuun "tuomion pyramidi" -ongelmaan, jossa sisäkkäiset takaisinkutsut tekevät koodista vaikeasti luettavaa. Vaihtoehtoiset menetelmät, kuten promises/futures tai async/await-avainsanat, parantavat käytettävyyttä huomattavasti.

Näyttelijämalli

Toimijamallissa suorituksen perusyksikkö on toimija eli toimija, joka kapseloi oman tilansa ja käyttäytymisensä ja kommunikoi yksinomaan lähettämällä viestejä. Jokaisella toimijalla on viestijono, ja se käsittelee näitä viestejä peräkkäin yksi kerrallaan, jolloin vältetään muutettavan muistin suora jakaminen.

Toimijat ovat käsitteellisesti erittäin kevyitä prosesseja, joita hallitsee ajonaikainen ympäristö tai virtuaalikone, ei suoraan käyttöjärjestelmä. Tämä mahdollistaa tuhansien tai jopa miljoonien toimijoiden luomisen yhden todellisen prosessin sisällä, joilla jokaisella on oma viestiruutunsa, ilman, että toimijaa kohden syntyisi omaa käyttöjärjestelmäsäikettä.

Suoritus on tyypillisesti preemptiivistä: virtuaalikone päättää globaalien kriteerien perusteella, milloin keskeyttää yhden toimijan salliakseen toisen. Jos ympäristössä on useita ytimiä, ajonaikainen ympäristö voi jakaa toimijat säikeiden tai ytimien kesken suhteellisen läpinäkyvästi, mikä saavuttaa tehokkaan rinnakkaisuuden.

Tämän mallin tärkeä seuraus on, että toimijat eivät jaa muuttuvaa muistia ; kaikki kommunikaatio tapahtuu viestien (usein muuttumattomien) välittämisen kautta. Tämä edistää toiminnallista puhtautta: toimija "näkee" vain oman tilansa ja vastaanottamansa datan, mikä helpottaa käyttäytymisen päättelyä ja turvallisen rinnakkaisuuden hyödyntämistä. Lisäksi optimistinen lähestymistapa virheenkäsittelyyn on yleinen : jos toimija epäonnistuu ohimenevän tilanteen vuoksi, se käynnistyy uudelleen kaatamatta koko järjestelmää.

Mitkä ohjelman osat voivat toimia samanaikaisesti

Kaikkea koodia ei voida suorittaa rinnakkain tai samanaikaisesti. On fragmentteja, joissa suoritusjärjestys on kriittinen (esimerkiksi muuttujan alustaminen ennen sen käyttöä), ja toisia, joissa järjestyksellä ei ole merkitystä (kaksi erillistä laskutoimitusta eri tiedoilla).

Sen päättämiseksi, voidaanko kaksi käskylohkoa suorittaa samanaikaisesti, käytetään Bernsteinin ehtoja . Jokaiselle käskyjoukolle S_{_k} määrittelemme:

• L(Sk): joukko muuttujia, jotka luetaan S:n suorituksen aikana_k.
• E(Sk): joukko muuttujia, jotka kirjoitetaan (päivitetään) S:n suorituksen aikana_k.

Kaksi lohkoa Si _ja Sj _voidaan suorittaa samanaikaisesti, jos kolme ehtoa täyttyy: E(Si) ∩ L(Sj) = ∅ , L(Si) ∩ E(Sj) = ∅ ja E(Si) ∩ E(Sj) = ∅ . Eli kumpikaan lohko ei saa kirjoittaa muuttujaan, jota toinen lukee tai kirjoittaa. Jos jokin näistä ehdoista rikotaan, molempien lohkojen samanaikainen suorittaminen voi muuttaa ohjelman lopputulosta.

Rinnakkaisten ohjelmien tyypillisiä ongelmia

Rinnakkaisten ohjelmien suunnittelu on monimutkaista, koska toimintojen tarkka suoritusjärjestys ei ole täysin määritetty . Tämä epädeterminismi johtaa hienovaraisiin virheisiin, joita on joskus vaikea toistaa ja jotka ilmenevät vain tiettyjen käskyparien kohdalla. Tarkastellaan yleisimpiä.

Kilpailuolosuhteet ja kriittinen osuus

Kilpailutilanne syntyy , kun laskennan tulos riippuu siitä suhteellisesta järjestyksestä, jossa kaksi tai useampi säike käyttää jaettuja resursseja, eikä tätä järjestystä voida kontrolloida. Jos useat säikeet muokkaavat samaa muuttujaa koordinoimatta niitä, lopullinen arvo voi olla virheellinen.

Klassinen esimerkki on operaatio x = x + 1 jaetulle muuttujalle. Peräkkäisohjelmassa tämä on triviaalia, mutta monisäikeisessä ympäristössä jokainen lisäys koostuu useista käskyistä: lue x, lisää 1, kirjoita tulos. Jos kaksi säiettä lomittaa nämä käskyt ilman keskinäistä poissulkemista , molemmat voivat lukea saman alkuarvon ja korvata toisensa, jolloin lisäyksiä menetetään.

Javassa laskurin, jota kasvatetaan kahdella säikeellä puoli miljoonaa kertaa kutakin, pitäisi lopulta saavuttaa miljoona, mutta synkronoinnin puuttuessa jokaisella suorituksella havaitaan erilaisia ​​tuloksia. Tämä johtuu siitä, että operaatioilla ei ole absoluuttista järjestystä , vaan pikemminkin osittainen järjestys, joka riippuu ajoittimesta ja tietystä lajittelusta.

Näiden tilanteiden välttämiseksi kriittiset osiot tunnistetaan – koodin osat, jotka käyttävät jaettuja resursseja ja joita ei tulisi suorittaa useammassa kuin yhdessä säiässä kerrallaan. Synkronointimekanismit (lukot, semaforit, monitorit jne.) varmistavat, että vain yksi säie pääsee kriittiseen osioon, aivan kuten liikennevalot valvovat pääsyä kapeaan risteykseen.

Keskinäisen poissulkemisen rikkominen

Puhumme keskinäisestä poissulkemisesta, kun kaksi tai useampi säie pääsee samaan kriittiseen osioon samanaikaisesti . Tämä rikkoo yksinomaisen pääsyn jaettuun resurssiin takuun ja johtaa ei-toivottuihin tuloksiin, kuten siihen, että edellinen laskuri ei koskaan saavuta odotettua arvoa.

Tämän tyyppinen vika johtuu yleensä epätäydellisestä tai virheellisestä synkronoinnista : pääsyn suojaamisen unohtamisesta lukolla, ei-atomisten ohjeiden käytöstä tai useiden resurssien yhdistämisestä ilman selkeää lukon hankintapolitiikkaa.

Lukkiutuminen tai lukitus

Lukkiutumistila syntyy , kun yksi tai useampi prosessi odottaa loputtomiin tapahtumaa, jota ei koskaan tapahdu. Tyypillisesti jokainen syklin prosessi odottaa resurssia, joka on seuraavalla prosessilla, mikä luo kehämäisen riippuvuuden ilman ulospääsyä.

Jotta resurssijärjestelmässä voi syntyä lukkiutumistilanne, neljän samanaikaisen ehdon on täytyttävä:

• Keskinäinen poissulkeminenResurssit allokoidaan yksinomaan (ei jaeta).
• Säilytys ja odottaminenProsessit ylläpitävät jo olemassa olevia resursseja ja pyytävät samalla lisää.
• Ei pakkolunastustaResursseja ei voida väkisin poistaa prosessista; ne vapautetaan vain vapaaehtoisesti.
• Pyöreä odotusProsessien kehämäinen ketju, jossa jokainen odottaa seuraavan prosessien hallussa olevaa resurssia.

Tekniikat umpikujien välttämiseksi tai purkamiseksi perustuvat ainakin yhden näistä ehdoista kumoamiseen . Esimerkiksi resurssien globaali järjestäminen syklien välttämiseksi, tiettyjen pakkolunastusmuotojen salliminen tai havaitsemis- ja palautusalgoritmien käyttö. Dijkstran pankkiirin algoritmi on klassikko, kuten myös hänen esimerkkinsä "ruokailevista filosofeista".

Määrittelemätön lykkäys ja epäoikeudenmukaisuus

Määrittelemätön lykkäys ( nälkiintyminen) tapahtuu, kun prosessi, joka on valmis suoritettavaksi tai resurssin hankkimiseksi, viivästyy määräämättömäksi ajaksi, koska ajoituskäytäntö ei koskaan anna sille vuoroa. Se ei ole umpikujassa; sen edessä on aina muita prosesseja.

Tämä ilmiö liittyy läheisesti aikataulutusalgoritmien epäreiluuteen : jos järjestelmä suosii systemaattisesti tiettyjä prosesseja (prioriteetin, saapumisjärjestyksen jne. mukaan) kompensoimatta muiden kertyvää odotusaikaa, jotkut jäävät helposti "ilman kynttilää" ikuisiksi ajoiksi.

Tyypillisiä ratkaisuja ovat ikääntymismekanismien toteuttaminen (pidempään odottaneiden prioriteetin nostaminen) tai prosessien käsittely tiukasti odotusjärjestyksessä. Suunnittelutasolla tämä toimii ohjenuorana: rinnakkaista koodia kirjoitettaessa on otettava huomioon, takaako järjestelmä, että kaikki edentävät säikeet lopulta etenevät.

Kiireinen odotus

Toinen yleinen sudenkuoppa on odottaminen : prosessi joutuu silmukkaan, joka jatkuvasti tarkistaa ehtoa (esimerkiksi jaetun muuttujan arvoa) eikä tee sillä välin mitään hyödyllistä. Vaikka se ei ole toiminnallisesti virheellinen, se tuhlaa prosessoria ja voi estää muita prosesseja saamasta riittävästi aikaa.

Ihannetapauksessa, kun prosessi ei voi edetä, koska se odottaa tapahtumaa, se tulisi pysäyttää ja suoritin vapauttaa, kunnes tapahtuma tapahtuu. Tämä saavutetaan käyttämällä estoalgoritmeja, jotka laittavat säikeen nukkumaan (odotus, uni, semaforit, olosuhteiden valvonta jne.) sen sijaan, että annettaisiin sen suorittaa silmukka.

Väärä jakaminen

Nykyaikaisissa välimuistia käyttävissä arkkitehtuureissa voi ilmetä virheellisen jakamisen ongelma . Tämä tapahtuu, kun useat säikeet muokkaavat samalla välimuistirivillä sijaitsevia eri muuttujia . Vaikka teoriassa tiedot ovat toisistaan ​​riippumattomia, välimuisti mitätöi ja synkronoi koko rivin joka kerta, kun jokin säikeistä kirjoittaa, mikä aiheuttaa mitätöintien myrskyn, joka heikentää suorituskykyä.

Väärä jakaminen ei riko ohjelman oikeellisuutta, mutta se aiheuttaa merkittävän suorituskyvyn laskun , erityisesti intensiivisissä silmukoissa. Tämän lieventämiseksi käytetään tekniikoita, kuten muuttujien tasausta muistissa, täyttöä rakennekenttien välillä sekä kääntäjän ja ajonaikaisia ​​asetuksia eri säikeiden käyttämän datan erottamiseksi eri välimuistiriveille.

Turvallisuus- ja henkiominaisuudet rinnakkaisissa ohjelmissa

Sen määrittämiseksi, onko rinnakkainen ohjelma "hyvin tehty", erotetaan tyypillisesti kaksi pääominaisuusjoukkoa: turvallisuus ja elävyys . Molemmat ovat olennaisia ​​oikean toiminnan määrittelyssä.

Turvaominaisuudet

Turvallisuusominaisuudet osoittavat, mitä ohjelman ei tulisi koskaan tehdä . Ne muotoillaan yleensä invariantteina: ehtoina, joiden on aina pysyttävä tosina koko suorituksen ajan.

• Keskinäinen poissulkeminenKriittisessä osiossa ei tulisi koskaan olla kerrallaan käynnissä useampaa kuin yksi prosessi.
• Lukkiutumisen puuttuminenYhdenkään prosessin ei pitäisi jumiutua odottamaan tapahtumaa, jota ei koskaan tapahdu.
• Osittainen korjausJos ohjelma päättyy, saadun tulosteen on oltava jokin määrittelyn sallimista.

Nämä ominaisuudet todennetaan yleensä muodollisen päättelyn, systemaattisen testauksen tai automatisoitujen todennustyökalujen avulla järjestelmän yksinkertaistetuissa malleissa.

Elämän ominaisuudet

Toisaalta elävyysominaisuudet kuvaavat sitä, mitä ohjelman tulisi lopulta tehdä , eli että "jotain hyvää" tapahtuu lopulta, jos ulkoisia virheitä ei tapahdu.

• OikeudenmukaisuusJokainen prosessi, joka on toteutettavissa, saa lopulta tilaisuutensa.
• Luotettava viestintäJokainen lähetetty viesti päätyy vastaanottajan vastaanotetuksi (tai ainakin käsitellään virheprotokollan mukaisesti).
• Täysin oikeinJos ohjelma päättyy, se tekee niin oikealla tuloksella eikä jää jumiin kesken suorituksen.

Elinaikaisten ominaisuuksien varmistaminen on usein vaikeampaa, koska ne riippuvat sekä samanaikaisen algoritmin suunnittelusta että taustalla olevan järjestelmän ajoituskäytännöistä.

Klassisia samanaikaisuuden ongelmia: lukijat-kirjoittajat, tuottaja-kuluttaja ja filosofit

Rinnakkaisuusteoria nojaa usein kanonisiin ongelmiin , jotka toimivat synkronointitekniikoiden testikenttänä. Useista näistä on tullut todellisia klassikoita.

Lukija-kirjoittaja-ongelma

Tietokantojen, jaettujen tiedostojen tai muistirakenteiden kaltaisissa järjestelmissä on yleistä, että lukijoita ja kirjoittajia on useita . Lukijat vain lukevat; kirjoittajat muokkaavat. Niin kauan kuin kukaan ei kirjoita, lukijat voivat käyttää tietoja rinnakkain ongelmitta, mutta kirjoittajan ei voida antaa muokata tietoja samaan aikaan, kun muut lukevat tai kirjoittavat , jotta vältetään tietojen vioittuminen tai epäjohdonmukaiset lukutavat.

Tämä ongelma vaatii algoritmien suunnittelua, jotka myöntävät samanaikaisen lukuoikeuden , kun kirjoituksia ei ole käynnissä, ja yksinomaisen pääsyn kirjoittajille, kun heidän on päivitettävä. Ratkaisusta riippuen lukijat tai kirjoittajat voivat olla epäoikeudenmukaisesti suosiossa, joten on tarpeen ottaa huomioon myös elinkaaren ominaisuudet.

Tuottaja-kuluttaja-ongelma

Toinen klassinen skenaario sisältää tuottajien ja kuluttajien yhteisen puskurin (esineiden "varaston"). Tuottajat luovat esineitä ja tallentavat ne puskuriin; kuluttajat sitten ottavat nämä esineet käsittelyä varten. Haasteena on koordinoida molempia osapuolia niin, että tuottajat eivät ylitä puskuria ja kuluttajat eivät yritä ottaa esineitä tyhjästä puskurista.

Yksinkertainen ratkaisu on suojata puskuri keskinäisellä poissulkemisella (esim. binäärisemaforeilla) ja käyttää laskureita estämään tuottajat, kun puskuri on täynnä , ja kuluttajat, kun se on tyhjä. Tämä lähestymistapa, vaikka se onkin pätevä, voi muuttua hankalaksi, kun toimijoita on paljon tai työnkulusta tulee monimutkainen.

Rakenteellisempi vaihtoehto on kapseloida puskuri ja sen synkronointilogiikka monitoriin : monitoriin, joka tarjoaa atomisia toimintoja (lisääminen, purkaminen) ja hallitsee sisäisesti odotusjonoja välttäen synkronointikoodin päällekkäisyyden tuottajissa ja kuluttajissa.

Filosofien illallinen

Filosofien illallisongelma havainnollistaa täydellisesti umpikujia, rotuolosuhteita ja nälkäkuolemaa. Useat pöydän ääressä istuvat filosofit tarvitsevat kaksi haarukkaa syömiseen, mutta jokaisella parilla on vain yksi haarukka. Jos he kaikki yrittävät tarttua haarukoihin samaan aikaan, on mahdollista, että jokainen tarttuu eri haarukkaan ja he kaikki joutuvat odottamaan toista haarukkaa: oppikirjan mukainen umpikuja.

Jos algoritmia ei ole suunniteltu hyvin, voi myös käydä niin, että sama filosofi näkee aina nälkää, kun taas toiset onnistuvat hamstraamaan haarukoita toistuvasti, mikä on esimerkki epäoikeudenmukaisuudesta ja nälkäkuolemasta.

Ehdotetut ratkaisut vaihtelevat yksinkertaisesta vuorottelusta (vuorojärjestelmä, jossa syövät yksi kerrallaan) ajattelijoiden jonoihin, joissa se, joka ei saa toista haarukkaa, menee jonon loppuun, ja tuomarin käyttöönottoon, joka rajoittaa samanaikaisesti pöydässä istuvien filosofien määrää (esimerkiksi enintään n−1, jos haarukoita on n), jotta aina on ainakin yksi filosofi, joka voi syödä ja vapauttaa resursseja.

Prosessien ja säikeiden välinen synkronointi ja viestintämenetelmät

Kriittisten alueiden käytön hallinnan ja samanaikaisten tehtävien suorituksen koordinoimiseksi meillä on useita synkronointi- ja viestintäprimitiivejä . Käytännössä yleisimmin käytettyjä ovat semaforit, lukot, monitorit ja eksplisiittinen viestien välitys.

Liikennevalot

Semafori on suojattu kokonaislukumuuttuja, johon pääsee käsiksi vain kahdella atomisella operaatiolla: odota/alas (vähennä ja estä, jos arvo on nolla) ja signaali/ylös (lisää ja valinnaisesti herättää estetty prosessi). Käyttöjärjestelmä takaa, että nämä operaatiot ovat jakamattomia, joten niitä voidaan käyttää keskinäisen poissulkemisen ja muiden synkronointimallien toteuttamiseen.

Binäärisemafori (vain 0 tai 1) toimii lukkona; laskeva semafori sallii konfiguroitavan maksimimäärän säikeitä tietyssä osiossa. Vaikka semaforit ovat erittäin joustavia, niitä pidetään matalan tason abstraktioina : väärin käytettyinä ne ovat loputon virheiden lähde (lukkiutumat, signaalityhjiöt jne.) ja pakottavat synkronointilogiikan sekoittamiseen aluelogiikan kanssa.

Keskinäinen poissulkeminen lukkojen kautta

Keskinäinen poissulkeminen toteutetaan tyypillisesti lukkojen (keskinäisen poissulkemisen lukkojen tai mutexien) avulla. Prosessi, joka haluaa päästä kriittiseen osioon, yrittää saada lukon; jos se on vapaa, se menee sisään ja merkitsee sen varatuksi; muussa tapauksessa se on estetty, kunnes lukko vapautetaan.

Käsitteellisesti se on kuin resurssin lukko : vain avaimen omistaja voi käyttää kriittistä osaa. Tämä kaava on käytännössä hyvin yleinen, mutta se vaatii kurinalaisuutta: lukko on aina vapautettava, samaa hankintajärjestystä on käytettävä, kun resursseja on useita, ja liian pitkiä kriittisiä osia, jotka heikentävät rinnakkaisuutta, on vältettävä.

näytöt

Monitorit vievät keskinäisen poissulkemisen korkeammalle tasolle. Monitori on abstraktio , joka ryhmittelee jaettua dataa ja sille suoritettavia toimintoja varmistaen, että nämä toiminnot suoritetaan yksi kerrallaan, eivätkä koskaan rinnakkain monitorin sisällä.

Monitorissa, kun säie kutsuu jotakin metodiaan, se siirtyy automaattisesti suojatulle alueelle : jos toinen säie on jo sisällä, sen on odotettava vuoroaan. Lisäksi monitorit tarjoavat tyypillisesti ehtomuuttujia (wait/notify, wait/signal) säikeiden keskeyttämiseksi ja herättämiseksi tiettyjen sisäisten tilaehtojen perusteella, mikä yksinkertaistaa ongelmien, kuten tuottaja-kuluttaja-suhteiden, ratkaisemista.

Koska tällä tekniikalla on korkea abstraktiotaso , se on turvallisempi ja vähemmän virhealtis kuin semaforien tai koodiin hajallaan olevien lukkojen suora käyttö. Kielet, kuten Java, C# ja useat modernit suoritusympäristöt, tarjoavat natiivin tuen monitoreille ja ehdoille.

Viestintä viestien välityksen kautta

Toinen tekniikkaperhe luopuu jaetusta tilasta ja perustuu viestien vaihtamiseen prosessien tai säikeiden välillä. Jokaisella viestillä on tyypillisesti otsikko (lähettäjän ja vastaanottajan tunnisteet, viestityyppi, koko) ja runko, joka sisältää tarvittavat tiedot.

Osoitteita on useita: suorassa osoitteistossa lähettäjä ilmoittaa eksplisiittisesti kuka vastaanottaja on, ja molemmat tuntevat toisensa. Implisiittisessä osoitteistossa lähettäjä määrittää vastaanottajan, mutta vastaanottaja ei välttämättä tiedä kuka viestin lähettää. Lopuksi, epäsuorassa osoitteistossa viestit tallennetaan tiettyjen prosessien tai käyttöjärjestelmän hallinnoimiin postilaatikoihin; kiinnostuneet prosessit lukevat postilaatikosta selvittääkseen, voivatko ne käyttää tiettyä kriittistä osaa tai käsitellä tietyn tapahtuman.

Synkronointi voi olla estävää (lähettäjä odottaa vastaanottajan vastaanottavan viestin tai vastaanottaja odottaa viestiä) tai ei-estävää. Käytettävien yhdistelmien valinta on ratkaisevan tärkeää: huono valinta voi luoda uusia kilpailutilanteita tai umpikujia sen sijaan, että se ratkaisisi ne.

Prosessisuunnittelu ja kontekstin muutokset

Prosessien ajoitus on strategia, jolla käyttöjärjestelmä päättää, mikä prosessi tai säie on käynnissä milläkin hetkellä, jakaen suorittimen kaikkien muistissa olevien kesken. Se perustuu valmiiden prosessien jonojen hallintaan ja ajoitusalgoritmien soveltamiseen, joiden tavoitteita ovat esimerkiksi suorittimen käyttöasteen maksimointi ja viiveiden minimointi (katso uudet ytimen ominaisuudet ).

Aikataulutustasoja on yleensä kolme:

• Lyhytaikainen: päättää, mikä valmis prosessi saa seuraavaksi suorittimen käyttöön. Ohjaa suoraan suorittimen ajan välitöntä allokointia.
• Keskipitkällä aikavälilläCPU-ajoitusohjelma, jota kutsutaan myös CPU-ajoitukseksi tai -lähettäjäksi, päättää, mitkä prosessit tulisi pitää päämuistissa ja mitkä voidaan vaihtaa yleisen suorituskyvyn optimoimiseksi. lähetysviive Se on aika, joka järjestelmältä kuluu yhden prosessin pysäyttämiseen ja toisen käynnistämiseen.
• Pitkäaikainen: säätelee, mitkä prosessit hyväksytään järjestelmään ja mitkä poistetaan muistista, mikä vaikuttaa globaaliin moniohjelmointitasoon (kuinka monta prosessia on aktiivisia samanaikaisesti).

Klassisia ajoitusalgoritmeja ovat FCFS (First-Come, First-Served), SJF (Shortest-Job-First), prioriteettiajoitukset , Round Robin ja monitasoinen jonotus . Jokainen tarjoaa erilaisia ​​kompromisseja vasteajan, läpimenon, oikeudenmukaisuuden ja monimutkaisuuden suhteen.

Prosessien välillä vaihtamiseen tarvitaan kontekstikytkimiä : järjestelmä tallentaa lähtevän prosessin rekistereiden, pino-osoittimen ja ohjelmalaskurin sisällön piirilevylleen ja palauttaa saapuvan prosessin tiedot. Tämä mekanismi mahdollistaa prosessin jatkamisen täsmälleen siitä, mihin se jäi, ikään kuin mitään ei olisi tapahtunut välissä.

Samanaikaisten järjestelmien varmennustyökalut

Koska rinnakkaisen järjestelmän käyttäytyminen voi vaihdella suuresti tapahtumien järjestyksestä riippuen, on yleistä käyttää muodollisia malleja ja varmennustyökaluja umpikujien, kilpailutilanteiden ja muiden haluttujen ominaisuuksien rikkomusten havaitsemiseen ennen varsinaisen järjestelmän käyttöönottoa.

Petri-verkot

Petri-verkot ovat graafinen malli rinnakkaisten järjestelmien kuvaamiseen. Ne esitetään suunnattuna, kaksijakoisena graafina, jossa on kahdenlaisia ​​solmuja: paikkoja (ehtoja) ja siirtymiä (tapahtumia). Paikat sisältävät tokeneita, jotka osoittavat, mitkä ehdot täyttyvät tietyssä tilassa.

Siirtymä on käytössä , jos kaikilla sen sisääntulokohdilla on vähintään yksi merkki. Kun siirtymä laukaistaan, se kuluttaa yhden merkin jokaisesta sisääntulokohdasta ja lisää tokeneita poistumispaikkoihinsa. Alkumerkinnällä (merkkijakauma) aloittaen on mahdollista tutkia ominaisuuksia, kuten onko järjestelmä toiminnassa ( jokainen siirtymä voidaan lopulta laukaista) vai rajoitettu/turvallinen (merkit eivät kerry loputtomasti yhteen paikkaan).

CSP (peräkkäisten prosessien kommunikointi)

CSP on matemaattinen teoria, jolla määritellään ja perustellaan kanavien kautta kommunikoivien peräkkäisten prosessien muodostamia järjestelmiä. Sen muodollinen semantiikka mahdollistaa vuorovaikutusmallien kuvaamisen, lukkiutumien tai live-lukitusten havaitsemisen ja sen varmistamisen, että suunnittelu täyttää tietyt turvallisuus- ja elävyysominaisuudet.

CSP:ssä prosessit yhdistyvät yksisuuntaisten kanavien kautta ja synkronoituvat tapaamismekanismin avulla: viestin kirjoittaminen ja lukeminen kanavalla katsotaan yhteisiksi toiminnoiksi, jotka tapahtuvat samanaikaisesti, jolloin vältetään tietyt perinteiseen jaettuun tilaan liittyvät kilpailuolosuhteet.

FDR ja JCSP

FDR (Failures-Divergence Refinement) on CSP-pohjainen työkalu, joka tarkistaa automaattisesti, täyttääkö järjestelmämalli tietyt ominaisuudet, jotka ilmaistaan ​​myös CSP-prosesseina. Ajatuksena on varmistaa, onko varsinainen järjestelmä halutun abstraktin mallin tarkennus (ei tuo uusia vikoja tai poikkeamia), ja havaita esimerkiksi tietoturvarikkomukset tai mahdolliset lukkiutumat.

JCSP puolestaan ​​on Java-kirjasto, joka toteuttaa suoraan CSP-käsitteitä: prosesseja, kanavia, synkronointia jne. Se yksinkertaistaa samanaikaisten ohjelmien kirjoittamista Javassa turvautumatta lukkoihin ja suoraan muistin jakamiseen, luottaen turvallisiin ja hyvin määriteltyihin viestintäprimitiiveihin, kuten kanaviin, esteisiin, ajastimiin ja muihin korkean tason komponentteihin.

Yhdessä tämä koko mallien, klassisten ongelmien, synkronointiprimitiivien ja varmennustyökalujen ekosysteemi tarjoaa vankan kehyksen luotettavien, tehokkaiden ja skaalautuvien samanaikaisten ohjelmien suunnittelulle ja analysoinnille , jotka pystyvät hyödyntämään sekä tehtävien lomitusta että nykyaikaisen laitteiston tarjoamaa rinnakkaisuutta.