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

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

К питанням зв’язку процесів, реалізованої через передачу повідомлень чи викликів RPC, тісно прилягають і питання синхронізації процесів. Синхронізація необхідна процесам в організацію спільного використання ресурсів, як-от файли чи устрою, і навіть обмінюватись даними.

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

Алгоритм синхронізації логічних годин

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

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

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

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

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