Синхронізація в розподілених системах

До питань зв'язку процесів, що реалізується шляхом передачі повідомлень чи викликів RPC, тісно примикають і питання синхронізації процесів. Синхронізація необхідна процесів для організації спільного використання ресурсів, таких як файли або пристрої, а також для обміну даними.

У однопроцесорних системах рішення задач взаємного виключення, критичних областей та інших проблем синхронізації здійснювалося з використанням загальних методів, таких як семафори та монітори. Однак ці методи не зовсім підходять для розподілених систем, тому що всі вони базуються на використанні розділяється оперативної пам'яті. Наприклад, два процеси, які взаємодіють, використовуючи семафор, повинні мати доступ до нього. Якщо обидва процесу виконуються на одній і тій же машині, вони можуть мати спільний доступ до семафору, що зберігається, наприклад, в ядрі, роблячи системні виклики. Однак, якщо процеси виконуються на різних машинах, то цей метод не застосовний, для розподілених систем потрібні нові підходи. Алгоритм синхронізації логічних годин

У централізованої однопроцесорній системі, як правило, важливо тільки відносний час і не важлива точність годин. У розподіленої системі, де кожен процесор має власні годинники зі своєю точністю ходу, ситуація різко змінюється: програми, що використовують час (наприклад, програми, подібні команді make в UNIX, які використовують час створення файлів, або програми, для яких важливо час прибуття повідомлень і т.п.) стають залежними від того, годинами якого комп'ютера вони користуються. У розподілених системах синхронізація фізичних годин (що показують реальний час) є складною проблемою, але з іншого боку дуже часто в цьому немає ніякої необхідності: тобто процесам не потрібно, щоб у всіх машинах було правильне час, для них важливо, щоб воно було скрізь однакова, більше того, для деяких процесів важливий тільки правильний порядок подій. У цьому випадку ми маємо справу з логічними годинами.

Введемо для двох довільних подій ставлення "сталося до". Вираз a ® b читається "a сталося до b" і означає, що всі процеси в системі вважають, що спочатку відбулася подія a, а потім - подія b. Відношення "сталося до" має властивість транзитивності: якщо вираження a ® b і b ® c істинні, то справедливо і вираз a ® c. Для двох подій одного й того ж процесу завжди можна встановити відношення "сталося до", аналогічно може бути встановлено це відношення і для подій надіслати повідомлення одним процесом і прийомом його іншим, так як прийом не може відбутися раніше відправки. Проте, якщо два довільних події сталися в різних процесах на різних машинах, і ці процеси не мають між собою ніякого зв'язку (навіть непрямої через треті процеси), то не можна сказати з повною визначеністю, яка з подій відбулася раніше, а яке пізніше.

Ставиться завдання створення такого механізму ведення часу, який би для кожної події а міг вказати значення часу Т (а), з яким би були згодні всі процеси в системі. При цьому має виконуватися умова: якщо а ® b, то Т (а) <Т (b). Крім того, час може тільки збільшуватися і, отже, будь-які коригування часу можуть виконуватися тільки шляхом додавання позитивних значень, і ніколи - шляхом вирахування.

Розглянемо алгоритм вирішення цієї задачі, який запропонував Lamport. Для відміток часу в ньому використовуються події. На малюнку 3.6 показані три процесу, що виконуються на різних машинах, кожна з яких має свій годинник, що йдуть зі своєю швидкістю. Як видно з малюнка, коли годинник процесу 0 показали час 6, в процесі 1 годинник показував 8, а в процесі 2 - 10. Передбачається, що всі ці години йдуть з постійною для себе швидкістю.

У момент часу 6 процес 0 посилає повідомлення А процесу 1. Це повідомлення приходить до процесу 1 в момент часу 16 за його щогодини. У логічному сенсі це цілком можливо, так як 6