Dekerov algoritam
Dekerov algoritam je prvo poznato tačno rešenje problema uzajamnog isključivanja u konkurentnom programiranju. Rešenje se pripisuje holandskim matematičarima Teodoru Dekeru (engl. Th. J. Dekker) i Dajkstri u neobjavljenom radu o opisivanju sekvencijalnih procesima.[1] i rukopisu o usklađivanju sekvencijalnih procesa.[2] Ovaj algoritam dozvoljava da dve niti dele resurse bez konflikata, koristeći samo deljenu memoriju za komunikaciju.
Ovaj algoritam izbegava striktnu zamenu kao u algoritmima gde se vrši samo preuzimanje svih resursa od strane procesa, i bio je jedan od prvih algoritama koji koriste uzajamno isključivanje procesa.
Uvod[уреди | уреди извор]
Ako dva procesa pokušavaju da uđu u kritičnu sekciju u isto vreme, u zavisnosti od toga čiji je red, algoritam će dozvoliti samo jednom procesu da prođe. Ako je jedan proces već u kritičnoj sekciji, druge proces će čekati dok prvi proces ne izađe iz kritične sekcije. Ovo se realizuje uz pomoć dve promeljive, dve zastave: zeli[0] i zeli[1], koje predstavljaju želju da odgovarajući proces uđe u kritičnu sekciju i promeni promenjivu red koja pokazuje koji od dva procesa ima prioritet.
Pseudokod[уреди | уреди извор]
// zeli[] predstavlja niz logičkih promenljivih koje predstavljaju želju da se uđe u kritičnu sekciju;
//red je promenljiva koja pokazuje ko je na redu od procesa
set zeli[0] to false
set zeli[1] to false
set red to 0 // or 1
| |
p0 - proces 0:
zeli[0] = true;
while (zeli[1]) {
if (red ≠ 0) {
zeli[0] = false;
while (red ≠ 0) {
// cekanje
}
zeli[0] = true;
}
}
// kriticna sekcija
...
red = 1;
zeli[0] = false
// ostatak sekcije
|
p1 - proces 1:
zeli[1] = true;
while (zeli[0]) {
if (red ≠ 1) {
zeli[1] = false;
while (red ≠ 1) {
// cekanje
}
zeli[1] = true;
}
}
// kriticna sekcija
...
red = 0;
zeli[1] = false;
// ostatak sekcije
|
Proces pokazuje nameru da uđe u kritičnu sekciju koja se testira u spoljašnjnoj while petlji. Ako drugi proces nije podigao zastavicu, u kritičnu sekciju može bezbedno da se uđe bez obzira na to čiji je red. Uzajamno isključivanje se garantuje zato što nijedan proces ne može da uđe u kritičnu sekciju a da prethodno ne postavi zastavicu (pretpostavljajući da će makar jedan ući u while petlju). Ovo takođe garantuje da procesi koji čekaju ne mogu da prestanu da čekaju. Alternativno, ako je promenljiva drugog procesa postavljena, ulazi se u while petlju i onda će promenljiva red odrediti ko sme da uđe u kritičnu sekciju. Procesi bez prioriteta će povući svoju nameru da uđu u kritičnu sekciju dok ne dobiju prioritet ponovo(unutrašnja while petlja). Proces sa prioritetom će izaći iz while petlje i ući u kritičnu sekciju.
Dekerov algoritam garantuje uzajamno isključivanje, i oslobođen je engl. deadlock-a i od pregladnjivanja(engl. recource starvation). Hajde da vidimo zašto je to tačno. Pretpostavimo da se p0 zaglavi unutrašnoj while(zeli[1]) zauvek. Tada može da se oslobodi deadlock-a, tako što će u jednom trenutku p1 da uđe u kritičnu sekciju i postavi red = 0 (vrednost promeljive red ostaje nepromenjena dok god p0 ne napreduje u izvršenju). Konačno p0 će izaći iz unutrašnje while(turn ≠ 0) (ako je ikad bila zaglavljena u njoj). Nakon toga će postaviti zeli[0] na true i ostatit da čeka zeli[1] da postane false(s obzirom na to da je promenljiva turn = 0, ono neće uticati na tu while petlju). Kada sledeći put p1 pokusa da uđe u kritičnu sekciju, biće primoran da izvrši akciju u svojoj while(zeli[0]) petlji. Tada će on da postavi zeli[1] na false i da se yaglavi u while(red ≠ 1) petlji dok red ostaje 0. Sledeći put p0 prolazi kroz kontrolu i izlazi iz petlje i ulazi u kritičnu sekciju. Analogno se dokazuje da ne može doći do deadlock-a drugog procesa.
Ako se algoritam modifikuje tako da izvršava akcije u while(zeli[1]) bez prethodne provere if(red = 0), onda postoji mogućnost od pregladnjivanja, stoga su svi ovi koraci u algoritmu neophodni.
C++ implementacija sa više niti[уреди | уреди извор]
C++ implementacija za više niti:
//BROJ_NITI predstavlja broj niti u procesu
// zeli[] predstavlja niz logičkih promenljivih koje predstavljaju želju da se uđe u kritičnu sekciju;
//red je promenljiva koja pokazuje ko je na redu od procesa
for (i = 0; i < BROJ_NITI; ++i) zeli[i] = false
turn = 0 // ili BROJ_NITI-1
|
Pi:
bool ne_ulazi = false;
zeli[i] = true;
for (unsigned int j = 0; j < BROJ_NITI; ++j)
if (j != i && zeli[j] == true) {
ne_ulazi = true;
break;
}
while (ne_ulazi || red != i) {
if (red != i) {
zeli[i] = false;
while (red != i) {
// cekanje
}
zeli[i] = true;
}
ne_ulazi = false;
for (unsigned int j = 0; j < BROJ_NITI; ++j)
if (j != i && zeli[j] == true) {
ne_ulazi = true;
break;
}
}
// kritična sekcija
...
red = (i+1) % BROJ_NITI;
zeli[i] = false;
// ostatak sekcije
|
Dodatak[уреди | уреди извор]
Jedna od prednosti ovog algoritma je to sto ne zahtegva nikakva specijalna uputstva i zato je veoma prenosiv između jezika i na različitim arhitekturama. Jedna mana je to sto je ograničen na dva procesa i to što koristi aktivno čekanje umesto suspenzije procesa.
Moderni operativni sistemi obezbeđuju mehanizme za uzajamno isključivanje koji su mnogo opštiji i fleksibilniji od Dekerovog algoritma. Međutim ako treba implementiran ekstremno efikasan ulaz i izlaz iz kritične sekcije i dalje se koristi Dekerov algoritam.
Mnogi moderni procesori izvršavaju instrukcije u neuređenom maniru; čak i pristup memoriji može biti neuređen. Ovaj algoritam neće raditi na simetrično multiprocesnim mašinama SMP opremljenim ovakvim procesorima bez upotrebe memorijske barijere.
Dodatno, mnogi optimizovani prevodioci programskih jezika će izvršititi transformacije koje će učiniti ovaj algoritam netačnim bez obzira na platformu na kojoj će biti korišćen. U mnogim jezicima dozvoljeno je da prevodilac detektuje indikatorske promenljive zeli[0] i zeli[1] i da nikada ne dozvoli da uđu u petlje. On može tako premestiti ove promenljive izvan petlje tako da kod bude semantički ekvivalentan(engl. Loop-invariant code motion). Takođe je moguće da mnogi prevodioci detektuju da se promenljiva red nikada ne menja od strane unutrašnjih petlji i stoga primeni sličnu transformaciju, rezultujući potencijalnom beskonačnom petljom. Ako se desi bilo koja od tih transformacija, algoritam neće biti tačan, bez obzira na arhitekturu.
Da bi se prevazišao ovaj problem ove promenljive bi trebalo da budu označene kao promenljive izvan trenutne oblasti izvršenja. Na primer, u jezicima C# i Java, može se označiti ove promenljive klučnom rečju 'volatile'. Treba skrenuti pažnju da u C/C++ 'volatile' atribut garantuje samo da prevodilac generiše kod koji ima odgovarajuće uređenje, ali da ne uključuje neophodnu memorijsku barijeru, koja bi garantovala ispravno izvršenje. C++11 standard predviđa atomične promenljive koje mogu biti korišćene tako da garantuju ispravno izvršenje, operacije na atomičnim promenljivim su sekvencijalno saglasne, tako da ako promenljive zeli i red jesu atomične, tako da i naivna implementacija algoritma radi.
Reference[уреди | уреди извор]
- ^ Dijkstra, Edsger W. Over de sequentialiteit van procesbeschrijvingen (EWD-35). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (original; transcription) (undated, 1962 or 1963); English translation About the sequentiality of process descriptions
- ^ Dijkstra, Edsger W. Cooperating sequential processes (EWD-123). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (original; transcription) (September 1965)