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

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

За синхронизирање на логичките часовници, Лампорт дефинирал врска која што се нарекува “се случило пред”. Изразот 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)

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