Логички часовници

Од Википедија — слободната енциклопедија

ЛОГИЧКИ ЧАСОВНИЦИ

Логички часовник е дел од компјутерски систем кој ги означува неговите единствени ознаки на редот со кој тие се случиле, со кој се постигнува хронолошко уредување и лесно утврдување на нивниот редослед. Целта на ова да се оствари лесно пратење на настаните и нивна синхронизација на системско ниво. Оваа задача е едноставна ако системот извршува само еден процес. Од друга страна, ако надгледуваните настани припаѓаат на десетици или стотина одвоени процеси, проблемот се усложнува и тука се јавува потреба од тој механизам. За разлика од вистински часовник кој го мери времето во вообичаениот начин, за логичкиот часовник е важно само настаните да означуваат монотоно зголемување на вредностите, така што редоследот на тие настани да биде индетификуван. За многу цели, од големо значење е сите машини да се прилагодат на исто време. Не е неопходно ова време да се поклопува со реалното време. Важно е сите машини да се синхронизираат на 10:00 иако реалното време е 10:02. Така што за одредена класа на алгоритми се зема предвид внатрешната синхронизација без разлика дали се блиску до реалното време. За овие алгоритми кога зборуваме за часовници велиме дека се логички часовници.

Лампорт во 1978 година ни покажа дека иако синхронизацијата е можна, нема потреба таа да биде апсолутна. Доколку два процеса не соработуваат, нема потреба од синхронизација на нивните часовници, бидејќи секако нема да предизвикаат некои проблеми. Понатаму, тој покажа дека не е многу важно сите процеси да се согласат колку е точното време, туку да се согласат на редоследот на извршување на настаните. Ќе го претставиме алгоритмот на Лампорт којшто ги синхронизира логичките часовници како и неговиот пристап којшто се нарекува векторски временски формат. Потоа ќе ги претставиме и matrix временските ознаки.

Временски часовници

За синхронизирање на логичките часовници, Лампорт дефинирал врска која што се нарекува “се случило пред”. Изразот a→b се чита како “a се случило пред b” и значи дека сите процеси се согласуваат дека прво се случил настанот a, па потоа настанот b. Оваа врска може да се разгледа директно во две ситуации:

  • Доколку a и b се настани на еден ист процес и a се случи пред b, тогаш a→b е точно.
  • Доколку a е настан на порака пратена од еден процес, и b е настан на примање на таа порака од некој друг процес, тогаш a→b е исто така точно. Една порака не може да се прими пред таа да биде пратена, или пак во истото време кога е пратена, затоа што таа зазема временски простор, којшто не може да има вредност нула.

“Се случило пред” е преодна врска, така што доколку a→b и b→c, тогаш a→c. Доколку се случат два настани x и y во различни процеси коишто не пренесуваат пораки (ниту индиректно), тогаш x→y не е точно, но ни y→x. За овие настани се вели дека се истовремени, што значи дека нема што да се каже за тоа кога се случиле или кој настан се случил прв.

На нас ни треба начин на мерење на времето за секој настан како a, да му назначиме временска вредност C(a) со која ќе се согласат сите процеси. Овие временски вредности мора да ги имаат атрибутите ако a→b, тогаш C(a) < C(b). Според ова, доколку a и b се два настани на истиот процес и a се случи пред b, тогаш C(a) < C(b). Доколку a е испраќачот на пораката од еден процес, а b е примачот на таа порака од друг процес, тогаш C(a) и C(b) мора да бидат назначени на начин на кој сите ќе се согласат на вредностите на C(a) и C(b) со C(a) < C(b). Времето на часовникот C, мора секогаш да се зголемува и никогаш да не се намалува. Исправки на времето може да се направат со додавање на позитивна вредност, но никогаш со одземање.

На Слика 1 е прикажан алгоритмот предложен од Лампорт за доделување на време на настани. Да ги земеме предвид трите процеси на Слика 1а. Процесите се одвиваат на различни машини, секоја со свој часовник којшто работи на своја брзина. Кога часовникот ќе отчука 6 пати во процесот 1, отчукува 8 пати во процесот 2 и 10 пати во процесот 3. Секој часовник работи на константно стапка, но стапките се различни поради разликите во кристалите.

На времето 6, процесот 1 испраќа порака A до процесот 2. Времето на пристигање на пораката зависи на кој часовник ќе веруваме. Во било кој настан, часовникот во процесот 2 отчитува 16 кога ќе пристигне. Доколку пораката го носи времето на поаѓање (6), процесот 2 ќе заклучи дека биле потребни 10 отчукувања за да се отствари патувањето. Оваа вредност е можна и според оваа логика пораката B од 2 до 3 зазема 16 отчукувања.

Пораката C од 3 до 2 поаѓа од 60 а пристига на 56. Слично на ова, пораката D од 2 до 1 поаѓа во 64 и пристига во 54. Јасно е дека овие вредности се невозможни и оваа ситуација мора да се спречи.

Решението на Лампорт доаѓа директно од врската “се случило пред”. Бидејќи C заминала на 60, мора да пристигне на 61 или подоцна. Оттука, секоја порака со себе го носи времето на испраќање според часовникот на испраќачот. Кога таа порака ќе пристигне и часовникот на примачот ќе покаже вредност според која пораката е испратена, примачот брзо го прилагодува неговиот часовник да биде едно отчукување повеќе од времето на испраќање. На Слика 1б гледаме дека C сега пристигнува на 61, додека пак D на 70.

Со мало надополнување, овој алгоритам ги задоволува нашите потреби за глобално време. Надополнувањето е дека помеѓу секои два настани, часовникот мора да отчука барем еднаш. Доколку еден процес прати или прими две пораки на брз начин, мора да го прилагоди неговиот часовник за барем едно отчукување помеѓу нив.

Во некои ситуации, дополнителни услови се пожелни како на пример два настани никогаш не се одвиваат во точно исто време. За да се постигне ова, може да го прикачиме бројот на процесот во којшто се одвива настанот на крајот на времето, одделено со децимална запирка. Така што, доколку еден настан се случи во процесите 2 и 3, и двата во време 40, првиот ќе биде 40.1 и подоцниот 40.2.

Со употреба на овој метод сега имаме начин да назначиме време на сите настани во дистрибуиран систем според следниве услови:

  • Доколку a се случи пред b во истиот процес, C(a) < C(b)
  • Доколку a и b го прикажуваат праќањето и примањето на една порака, односно, C(a)< C(b)
  • За сите карактеристични настани a и b, C(a) ≠ C(b)

Овој алгоритам ни дава начин да обезбедиме редослед на сите настани во системот.

Векторски временски часовници

Доколку два настани се последователно поврзани и настанатот е се случил пред настанот е’, тогаш нивните временски часовници ќе ја имаат релацијата L(e)<L(e’). Доколку временските ознаки на Лампорт ја имаат релацијата L(e)<L(e’), тогаш не може да се заклучи дека e→e’. Причината е што нема индикација дали некои два настани се последователно поврзани или не. Решение за проблемот е концептот за векторски временски часовници.

Векторските временски часовници се конструирани така што секој процес Pi да одржува вектор Vi со следниве одлики:

  • Vi[i] е бројот на настани коишто се случиле во врска со процесот Pi.
  • Доколку Vi[j]=k тогаш Pi знае дека k настани се случиле во врска со процесот Pj.

Првата одлика се одржува преку зголемување на Vi[i] со појавата на секој нов настан што ќе се случи на процесот Pi. Втората одлика се одржува со вектори коишто се праќаат заедно со пораките. Кога Pi ќе испрати порака го испраќа и моменталниот вектор како временска ознака. На овој начин приемникот е информиран за бројот на настани коишто се случиле кај Pi. Уште поважно е дека на приемникот му е кажано колку настани кај други процеси заземале место пред Pi да ја прати пораката. Со други зборови, временската ознака на пораката кажува на приемникот колку настани во други процеси претходеле на пораката и од која порака можеби зависат. Кога процесот Pj ја прима пораката го прилагодува својот вектор со ставање на секој влез Vj[k] на max{Vj[k], vt[k]}. Векторот сега го отсликува бројот на пораки што Pj мора да ги прими барем да ги види истите пораки што го спровеле праќањето на пораката. После ова влезот Vj[j] се зголемува за 1 што го претставува примањето на наредната порака.

Со мало прилагодување векторските временски часовници можат да се користат за гарантирање на последователното примање на пораките. Да претпоставиме дека Vi[i] се зголемува само кога процесот Pi праќа порака. Да го земеме предвид примерот со електронса огласна табла (electronic bulletin board). Кога процесот Pi ќе постави статија, ја праќа таа статија како порака a со временска ознака vt(a) која што се става да биде еднаква на Vi. Сега да претпоставиме дека Pj ќе постави реакција на таа статија. Ова го прави со праќање на порака r со временска ознака vt(r) која што се става да биде еднаква на Vj. Да забележиме дека vt(r)[j] > vt(a)[j]. Доколку комуникацијата е сигурна и двете пораки, a која што ја содржи статијата, и пораката r која што ја содржи реакцијата најверојатно ќе пристигнат на друг процес Pk. Бидејќи не претпоставуваме ништо во врска со редот на пораките, пораката r може да пристигне кај Pk пред пораката a. Кога ќе ја прими r, Pk ја проверува временската ознака vt(r) и ќе одлучи да го одложи испраќањето сè додека сите пораки коишто претходат на r не бидат примени. Пораката r ќе биде пратена само ако се постигнати следниве услови:

  • Vt(r)[j] = Vk[j]+1
  • Vt(r)[i] ≤ Vk[i] for all i ≠ j

Првиот услов наведува дека r е следната порака што Pk ја очекувал од процесот Pj. Вториот услов пак наведува дека Pk не видел пораки коишто не биле видени од Pj кога тој ја пратил пораката r. Ова значи дека Pk веќе ја има видено пораката a.

Интересен изоморфизам[уреди | уреди извор]

Ќе ги дефинираме следниве тестови на векторите:

vh ≤ vk ↔ vh < ∀x ∶ vh[x] ≤ vk[x]

vh < vk ↔ vh < vk and ∃x ∶ vh[x] < vk[x]

vh ∥ vk ↔ not (vh < vk)andnot (vk<vh)

Ако го земеме предвид делумниот редослед од “→” сет на настани, кои се произведени од дистрибуирани пресметки и временско форматирани од векторскиот систем ги имаме следниве особини. Нека два настани x и y се усогласат временски со vh и vk, па имаме:

x→y ↔ vh < vк

x∥y ↔ vh ∥ vк

Со други зборови, постои изоморфизам помеѓу сет на делумно наредени настани создадени од страна на дистрибуираната пресметка и нивниот временски формат. Ако ја земеме предвид појавата на настаните, тесто може да се поедностави.Значи ако z и y се временски форматирани од (vh,i) и (vk,j) ќе имаме:

x→y ↔ vh[i] < vк[i]

x∥y ↔ vh[i]> vк[i] и vh[j]<vk[j]

Векторски часовник за броење на настаните[уреди | уреди извор]

Ако ви правилото RI назначивме дека d=I тогаш го добиваме следниов резултат : vti[i] ги брои настаните кои се создадени од Si. Па ако земеме предвид еден настан e временски форматиран во vh тогаш имаме:

Vh[j] =број на настани произведени од Si кои причински претходат на е

∑vh[j] – 1 =вкупен број на настани кои причински претходат на е. Го дефинираме овој број да биде тежината на причинскиот конус на настанот е.

Тежината на конус(е) е минималниот број на настани кои мора да се случат пред е.

Matrix временски часовници

Во овој случај глобалното логичко време е претставено со матрица n x n. За секој настан постои матрица mti[q… n, 1… n] чиишто ентитети ги имаат следниве одлики:

  • mti[i, i] е логичкиот часовник на Pi, што се зголемува пропорционално на пресметките на процесот Pi
  • mti[k, l] го претставува погледот или пак знаењето што процесот Pi го има за знаењето на Pk за логичкиот часовник на Sl. Целата матрица mti го претставува локалниот поглед на Pi за логичкото глобално време

Всушност редот mti[i, .] е векторскиот часовник vti[.] што значи дека овој ред ги наследува одликите од системот за векторски временски часовник. Има две правила коишто се применуваат:

  • Пред да се случи еден настан:

mti[i, i] := mti[i,i] + d (d > 0)

  • Секоја порака m враќа време матрица mt. Кога ќе прими таква порака (m, mt) од процес Pj, процесот Pj извршува (пред првото правило):

1 ≤ k ≤ n : mti[i, k] := max (mti[i, k], mt[j, k])

1 ≤ k, l ≤ n : mti[k, l] := max (mti[k, l], mt[k, l])

Ваков систем е претставен во 1984 година од страна на Wuu и Bernstein кој припиен на log систем, ни дозволува да ги одбиеме застарените информации.

Имплементирање на логичките часовници[уреди | уреди извор]

За оваа задача, ќе го имплементираме Лампорт логичкиот часовник со користење на MPI. Ке имплементираме сет од примитиви за да ја одржиме состојббата на логичките часовници. За да се покаже дека логичкиот часовник работи правилно, програмата треба да работи во сет од симулациски параметри а потоа да ги испечати сите логички часовници поврзани со секој настан. Препорачливо е да бидат имплементирани еден процес за менаџирање и сет од работни процеси. Процесот за менаџирање ќе управува со симулацијата, а работните процеси ќе разменуваат пораки и ќе ги имплементираат логичките часовници.

Влез[уреди | уреди извор]

Влезот ќе биде во следниов формат:

<number of processes N>

<event type> <pid1>

<event type> <pid1> <pid2> <msg>

...

End

Процесните ID во влезната податотека ќе се движат од 1 до N. Ќе има точно еден влезен настан во линија. Постојат два вида на настани кои можат да се појават при внесувањето : извршување и праќање. Настанот на извршување нема втор аргумент, и укажува дека еден настан на извршување заземал место во процесот pid2. Пораката ќе биде стринг од ASCII карактери ограничени со наводници. Наводниците не треба да се чуваат како дел од стрингот.

Пример

3

exec 1

send 1 2 "silly message"

end

Излез[уреди | уреди извор]

На почетокот на симулацијата, излезот на бројот на процеси ќе биде прикажан сп следнава линија:

printf ( "There are %d processes in the system\n", N);

За секој настан, треба да се користи еквивалентност на следниве printf() изрази:

printf( "Execution event in process %d\n", pid );

printf( "Message sent from process %d to process %d: %s\n", pid1, pid2, msg );

printf( "Message received from process %d by process %d: %s\n", pid1, pid2, msg );

За било кој испечатен логички часовник, ќе го користиме следниов израз (или сличен):

printf( "Logical time at process %d is %d\n", pid, logical_time );

После секој настан, треба да се на излез да се добие било кој логички часовник надграден од настанот. За испраќање/примање настаните, испечатете го времето на праќачот , а потоа времето на примачот. На крајот на извршувањето, ќе се испечатат сите логички времиња за сите часовници и ќе се испринтаат во растечки редослед по ID. Можеме да го вклучиме излезот за дебагирање во нашот тест, но не и изразот за дебагирање во програмата која ја вклучиваме.

Важно[уреди | уреди извор]

• Стартувајте ги сите часовници на време 0.

• Часовникот делта, d, ќе биде 1 за сите обработувачи.

• Нашиот MPI програм ќе чита од станардниот влез и ќе запишува во стандардниот излез

• Единствените MPI функции кои можеме да ги користиме се MPI_Init(), MPI_Finalize(), MPI_Comm_rank(), MPI_Comm_size(), MPI_Send(), и MPI_Recv().

• Можеме да користиме потврдна порака за да се осигураме дека тековната акција (пример пораката се праќа помеѓу роб процесите) се извршила пред господарот да ја прочита следната акција

• Името на програмот и изворниот код мораат да видат lamport.c или lamport.cpp.

Други системи за временски часовници

Концептот на синхронизатор ни дозволува работење на синхронизиран дистрибуиран алгоритам на несинхронизиран дистрибуиран систем. Синхронизаторот е преведувач за синхронизирани дистрибуирани програми. Под синхронизирани се мисли дека дистрибуираниот програм се одвива логички чекор по чекор и се потпира на претпоставка на глобално време. Од точка на гледиште на синхронизираните дистрибуирани програми такво глобално време постои и учествува во нивната семантика.

Во дистрибуирани дискретни настани постои симулација на виртуелно време и семантиката на програмата за симулација се потпира на тоа време. Дизајнирањето на дистрибуирано симулационо време на работа се состои во обезбедувањето на прогресот на виртуелното време на таков начин што поледователните релации на програмата за симулација никогаш не се загрозени. Логичкото време изградено од синхронизер или од дистрибуирано симулационо време на работа го придвижува синхрониот или симулациониот програм. Не треба да се меша со логичките временските часовници коишто ги спомнавме претходно. Со претходно спомнатите логички часовници (linear, vector и matrix) целта е да можеме временски да ги означиме доследните настани за да се обезбедат некои одлики како животност и доследност. Од друга страна пак, времето обезбедено со синхронизатор или дистрибуирано симулационо време на работа припаѓа на семантиката на “underlying” програмата. Ова друго логично време е логичкиот колега на физичкото време кое што е понудено од околината и употребено од апликации кои се одвиваат во реално време.

Наводи:

[1] Andrew S. Tanenbaum, Maarten Van Steen, Distributed Systems Principles and Paradigms

[2] Colin J. Fidge, Timestamps in Message-Passing System That Preserve the Partial Ordering

[3] Leslie Lamport, Time, clocks and the ordering of events in a distributed system

[4] Michel Raynal, About logical clocks for distributed systems