Декеров алгоритам
Декеров алгоритам је прво познато тачно решење проблема узајамног искључивања у конкурентном програмирању. Решење се приписује холандским математичарима Теодору Декеру (енгл. Th. J. Dekker) и Дајкстри у необјављеном раду о описивању секвенцијалних процесима.[1] и рукопису о усклађивању секвенцијалних процеса.[2] Овај алгоритам дозвољава да две нити деле ресурсе без конфликата, користећи само дељену меморију за комуникацију.
Овај алгоритам избегава стриктну замену као у алгоритмима где се врши само преузимање свих ресурса од стране процеса, и био је један од првих алгоритама који користе узајамно искључивање процеса.
Увод
уредиАко два процеса покушавају да уђу у критичну секцију у исто време, у зависности од тога чији је ред, алгоритам ће дозволити само једном процесу да прође. Ако је један процес већ у критичној секцији, друге процес ће чекати док први процес не изађе из критичне секције. Ово се реализује уз помоћ две промељиве, две заставе: зели[0] и зели[1], које представљају жељу да одговарајући процес уђе у критичну секцију и промени промењиву ред која показује који од два процеса има приоритет.
Псеудокод
уреди
// 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
|
Процес показује намеру да уђе у критичну секцију која се тестира у спољашњној wхиле петљи. Ако други процес није подигао заставицу, у критичну секцију може безбедно да се уђе без обзира на то чији је ред. Узајамно искључивање се гарантује зато што ниједан процес не може да уђе у критичну секцију а да претходно не постави заставицу (претпостављајући да ће макар један ући у wхиле петљу). Ово такође гарантује да процеси који чекају не могу да престану да чекају. Алтернативно, ако је променљива другог процеса постављена, улази се у wхиле петљу и онда ће променљива ред одредити ко сме да уђе у критичну секцију. Процеси без приоритета ће повући своју намеру да уђу у критичну секцију док не добију приоритет поново(унутрашња wхиле петља). Процес са приоритетом ће изаћи из wхиле петље и ући у критичну секцију.
Декеров алгоритам гарантује узајамно искључивање, и ослобођен је енгл. deadlock-а и од прегладњивања(енгл. recource starvation). Хајде да видимо зашто је то тачно. Претпоставимо да се п0 заглави унутрашној wхиле(зели[1]) заувек. Тада може да се ослободи деадлоцк-а, тако што ће у једном тренутку п1 да уђе у критичну секцију и постави ред = 0 (вредност промељиве ред остаје непромењена док год п0 не напредује у извршењу). Коначно п0 ће изаћи из унутрашње wхиле(турн ≠ 0) (ако је икад била заглављена у њој). Након тога ће поставити зели[0] на труе и остатит да чека зели[1] да постане фалсе(с обзиром на то да је променљива турн = 0, оно неће утицати на ту wхиле петљу). Када следећи пут п1 покуса да уђе у критичну секцију, биће приморан да изврши акцију у својој wхиле(зели[0]) петљи. Тада ће он да постави зели[1] на фалсе и да се yаглави у wхиле(ред ≠ 1) петљи док ред остаје 0. Следећи пут п0 пролази кроз контролу и излази из петље и улази у критичну секцију. Аналогно се доказује да не може доћи до деадлоцк-а другог процеса.
Ако се алгоритам модификује тако да извршава акције у wхиле(зели[1]) без претходне провере иф(ред = 0), онда постоји могућност од прегладњивања, стога су сви ови кораци у алгоритму неопходни.
C++ имплементација са више нити
уредиC++ имплементација за више нити:
//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
|
Додатак
уредиЈедна од предности овог алгоритма је то сто не захтегва никаква специјална упутства и зато је веома преносив између језика и на различитим архитектурама. Једна мана је то сто је ограничен на два процеса и то што користи активно чекање уместо суспензије процеса.
Модерни оперативни системи обезбеђују механизме за узајамно искључивање који су много општији и флексибилнији од Декеровог алгоритма. Међутим ако треба имплементиран екстремно ефикасан улаз и излаз из критичне секције и даље се користи Декеров алгоритам.
Многи модерни процесори извршавају инструкције у неуређеном маниру; чак и приступ меморији може бити неуређен. Овај алгоритам неће радити на симетрично мултипроцесним машинама СМП опремљеним оваквим процесорима без употребе меморијске баријере.
Додатно, многи оптимизовани преводиоци програмских језика ће извршитити трансформације које ће учинити овај алгоритам нетачним без обзира на платформу на којој ће бити коришћен. У многим језицима дозвољено је да преводилац детектује индикаторске променљиве зели[0] и зели[1] и да никада не дозволи да уђу у петље. Он може тако преместити ове променљиве изван петље тако да код буде семантички еквивалентан(енгл. Loop-invariant code motion). Такође је могуће да многи преводиоци детектују да се променљива ред никада не мења од стране унутрашњих петљи и стога примени сличну трансформацију, резултујући потенцијалном бесконачном петљом. Ако се деси било која од тих трансформација, алгоритам неће бити тачан, без обзира на архитектуру.
Да би се превазишао овај проблем ове променљиве би требало да буду означене као променљиве изван тренутне области извршења. На пример, у језицима C# и Јава, може се означити ове променљиве клучном речју 'волатиле'. Треба скренути пажњу да у C/C++ 'волатиле' атрибут гарантује само да преводилац генерише код који има одговарајуће уређење, али да не укључује неопходну меморијску баријеру, која би гарантовала исправно извршење. C++11 стандард предвиђа атомичне променљиве које могу бити коришћене тако да гарантују исправно извршење, операције на атомичним променљивим су секвенцијално сагласне, тако да ако променљиве зели и ред јесу атомичне, тако да и наивна имплементација алгоритма ради.
Референце
уреди- ^ Дијкстра, Едсгер W. Овер де сеqуентиалитеит ван процесбесцхријвинген (ЕWД-35). Е.W. Дијкстра Арцхиве. Центер фор Америцан Хисторy, Университy оф Теxас ат Аустин. (оригинал; трансцриптион) (ундатед, 1962 ор 1963); Енглисх транслатион Абоут тхе сеqуентиалитy оф процесс десцриптионс
- ^ Дијкстра, Едсгер W. Цооператинг сеqуентиал процессес (ЕWД-123). Е.W. Дијкстра Арцхиве. Центер фор Америцан Хисторy, Университy оф Теxас ат Аустин. (оригинал; трансцриптион) (Септембер 1965)