Dekkerin algoritmi on ensimmäinen tunnettu oikea ratkaisu rinnakkaisohjelmoinnin keskinäisen poissulkemisen ongelmaan . Edsger Dijkstra viittaa hollantilainen matemaatikko T. Dekker tämän algoritmin laatijaksi työssään prosessien välisestä viestinnästä [1] . Sen avulla kaksi suoritussäiettä voivat jakaa jakamattoman resurssin ilman ristiriitoja käyttämällä vain jaettua muistia viestintään.
Jos kaksi prosessia yrittää päästä kriittiseen osaan samanaikaisesti, algoritmi sallii vain toisen niistä sen mukaan, kenen vuoro sillä hetkellä on. Jos yksi prosessi on jo siirtynyt kriittiseen osaan, toinen odottaa, kunnes ensimmäinen poistuu siitä. Tämä tehdään käyttämällä kahta lippua (ilmaisimet "aikomuksesta" päästä kriittiseen osioon) ja käännösmuuttujaa (osoittaa minkä prosessin käännös on kyseessä) .
| lippu[0] := false lippu[1] := false käännä := 0 // tai 1 | |
| p0: lippu[0] := tosi , kun lippu[1] = tosi { jos käännös = 1 { lippu[0] := false kun käännös = 1 {} lippu[0] := tosi } } // kriittinen osa ... käännä := 1 lippu[0] := false // kriittisen osan loppu ... | p1: lippu[1] := tosi , kun lippu[0] = tosi { jos käännös = 0 { lippu[1] := false kun käännös = 0 {} lippu[1] := tosi } } // kriittinen osa ... käännä := 0 lippu[1] := false // kriittisen osan loppu ... |
Prosessit ilmoittavat aikovansa siirtyä kriittiseen osaan; tämä tarkistetaan ulkoisella "while"-silmukalla. Jos mikään muu prosessi ei ole ilmoittanut tällaista aikomusta, kriittiselle osalle on turvallista mennä (riippumatta siitä, kenen vuoro on). Keskinäinen poissulkeminen on silti taattu, koska mikään prosessi ei pääse kriittiseen osioon ennen kuin tämä lippu on asetettu (olettaen, että ainakin yksi prosessi tulee while-silmukkaan). Se takaa myös edistymisen, koska ei tarvitse odottaa, että prosessi lähtee "aikomuksesta" siirtyä kriittiseen osioon. Muussa tapauksessa, jos toinen prosessimuuttuja on asetettu, syötä "while"-silmukka ja käännösmuuttuja osoittaa, kuka saa mennä kriittiseen osaan. Prosessi, jonka vuoro ei ole saapunut, jättää aikomuksen siirtyä kriittiseen osaan, kunnes sen vuoro saapuu (sisäinen "while" -silmukka). Prosessi, jonka vuoro on, poistuu while-silmukasta ja siirtyy kriittiseen osaan.
Dekkerin algoritmi takaa molemminpuolisen poissulkemisen , umpikujan tai katkeamisen mahdottomuuden. Katsotaanpa, miksi viimeinen ominaisuus on totta. Oletetaan, että p0 pysyy "while flag[1]" -silmukan sisällä ikuisesti. Koska lukkiutumista ei voi tapahtua, ennemmin tai myöhemmin p1 saavuttaa kriittisen osuutensa ja asettaa käännöksen = 0 ( käännöksen arvo pysyy vakiona, kunnes p0 etenee). p0 poistuu sisäisestä "when turn = 1" -silmukasta (jos se oli siellä). Sitten se asettaa lipun[0] arvoon tosi ja odottaa, että lippu[1] on epätosi (koska turn = 0, se ei koskaan suorita while-silmukkaa). Seuraavan kerran kun p1 yrittää päästä kriittiseen osioon, se pakotetaan suorittamaan "while flag[0]" -silmukan toiminnot. Tarkemmin sanottuna se asettaa lipun[1] arvoon false ja suorittaa "while turn = 0" -silmukan (koska käännös pysyy 0:na). Seuraavan kerran, kun ohjaus siirtyy p0:aan, se poistuu "while flag[1]" -silmukasta ja siirtyy kriittiseen osaan.
Jos algoritmia muutetaan niin, että "while flag[1]" -silmukan toiminnot suoritetaan tarkistamatta "turn = 0" -ehtoa, on mahdollisuus roikkumiseen ( englanniksi starvation ). Näin ollen kaikki algoritmin vaiheet ovat välttämättömiä.
Yksi algoritmin eduista on, että se ei vaadi erityisiä " verify-set " -komentoja – atomiluku- , päivitys- ja kirjoitustoimintoja – ja sen seurauksena se on helposti siirrettävissä eri ohjelmointikielille ja tietokonearkkitehtuureille. Haittoja ovat sen soveltuvuus vain kahden prosessin tapauksessa ja odotussilmukan käyttö prosessin keskeyttämisen sijaan odotussilmukan käyttö tarkoittaa, että prosessien tulisi viettää mahdollisimman vähän aikaa kriittisen osan sisällä.
Nykyaikaiset käyttöjärjestelmät tarjoavat synkronointiprimitiivit, jotka ovat yleisempiä ja joustavampia kuin Dekker-algoritmi. On kuitenkin huomattava, että todellisen samanaikaisuuden puuttuessa kahden prosessin välillä kriittisten osien sisään- ja poistumisoperaatiot ovat erittäin tehokkaita tätä algoritmia käytettäessä.
Monet nykyaikaiset mikroprosessorit suorittavat käskyjä epäjärjestyksessä, jopa muistin käyttöjärjestystä ei välttämättä noudateta (katso muistin käyttöjärjestys ). Algoritmi ei toimi tällaisilla prosessoreilla varustetuissa SMP -koneissa, ellei muistiesteitä käytetä .
Lisäksi optimoivat kääntäjät voivat tehdä ohjelmasta sellaisia muunnoksia, että annettu algoritmi lakkaa toimimasta laitteistoalustan ongelmista huolimatta. Tällainen kääntäjä saattaa havaita, että indikaattorimuuttujia lippu[0] ja lippu[1] ei lueta silmukan sisällä. Sitten prosessin avulla, jota kutsutaan invariantin poistamiseksi silmukasta , se poistaa näiden muuttujien kirjoitukset generoidusta operaatiokoodista, pitäen niitä redundantteina. Jos kääntäjä havaitsee, että käännösmuuttuja ei koskaan muutu sisäisessä silmukassa, se voi suorittaa samanlaisen muunnoksen, mikä johtaa mahdolliseen äärettömään silmukkaan . Jos jokin näistä muutoksista tehdään, algoritmi lakkaa toimimasta laitteistoarkkitehtuurista riippumatta. Ohjelmointikieli voi tarjota avainsanoja (ohjeita), jotka estävät kääntäjää suorittamasta kuvattuja optimointeja määritetylle muuttujalle.