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

До питань зв'язку процесів, що реалізується шляхом передачі повідомлень чи викликів 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 <16. Аналогічно, повідомлення В, надіслане процесом 1 процесу 2 прийшло до останнього в момент часу 40, тобто його передача зайняла 16 одиниць часу, що також є ймовірним.

Рис. 3.6. Синхронізація логічних годин
а - три процеси, кожен зі своїми власними годинами;
б - алгоритм синхронізації логічних годин

Ну а далі починаються досить дивні речі. Повідомлення С від процесу 2 до процесу 1 було відправлено в момент часу 64, а надійшло до місця призначення в момент часу 54. Очевидно, що це неможливо. Такі ситуації необхідно запобігати. Рішення Lamport'а випливає безпосередньо з відносин "сталося до". Так як С було відправлено у момент 60, то воно повинно дійти в момент 61 або пізніше. Отже, кожне повідомлення має нести з собою час свого відправлення по годинах машини-відправника. Якщо в машині, яка отримала повідомлення, годинник показує час, який менше часу відправлення, то ці години переводяться вперед, так, щоб вони показали час, більше часу відправлення повідомлення. На малюнку 3.6, б видно, що С надійшло в момент 61, а повідомлення D - в 70.

Цей алгоритм задовольняє сформульованим вище вимогам. Алгоритми взаємного виключення

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

Централізований алгоритм

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

Розподілене алгоритм

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

Процес може увійти в критичну секцію тільки в тому випадку, якщо він отримав у відповідь повідомлення-дозволи від усіх інших процесів. Коли процес залишає критичну секцію, він посилає дозвіл всіх процесів з своєї черги і виключає їх з черги.

Алгоритм Token Ring

Зовсім інший підхід до досягнення взаємного виключення в розподілених системах ілюструється малюнком 3.7. Всі процеси системи утворюють логічне кільце, тобто кожен процес знає номер своєї позиції в кільці, а також номер найближчого до нього наступного процесу. Коли кільце ініціалізується, процесу 0 передається так званий токен. Токен циркулює по кільцю. Він переходить від процесу n до процесу n +1 шляхом передачі повідомлення по типу "точка-точка". Коли процес отримує токен від свого сусіда, він аналізує, не потрібна чи йому самому увійти в критичну секцію. Якщо так, то процес входить в критичну секцію. Після того, як процес вийде з критичної секції, він передає токен далі по кільцю. Якщо ж процес, який прийняв токен від свого сусіда, не зацікавлений у входженні в критичну секцію, то він відразу відправляє токен в кільце. Отже, якщо жоден з процесів не бажає входити в критичну секцію, то в цьому випадку токен просто циркулює по кільцю з високою швидкістю.

Порівняємо ці три алгоритму взаємного виключення. Централізований алгоритм є найбільш простим і найбільш ефективним. При його використанні потрібно тільки три повідомлення для того, щоб процес увійшов і покинув критичну секцію: запит і повідомлення-дозвіл для входу і повідомлення про звільнення ресурсу при виході. При використанні розподіленого алгоритму для одного використання критичної секції потрібно послати (n-1) повідомлень-запитів (де n - число процесів) - по одному на кожен процес і отримати (n-1) повідомлень-дозволів, тобто всього необхідно 2 (n-1) повідомлень. В алгоритмі Token Ring число повідомлень змінно: від 1 у випадку, якщо кожен процес входив у критичну секцію, до безмежно великого числа, при циркуляції токена по кільцю, в якому жоден процес не входив у критичну секцію.

На жаль всі ці три алгоритму погано захищені від відмов. У першому випадку до краху призводить відмова координатора, у другому - відмова будь-якого процесу (парадоксально, але розподілений алгоритм виявляється менш відмовостійкості, ніж централізований), а в третьому - втрата токена або відмова процесу.

Рис. 3.7. Кошти взаємного виключення в розподілених системах
а - неупорядкована група процесів у мережі;
б - логічне кільце, утворене програмним забезпеченням Неподільні транзакції

Всі засоби синхронізації, які були розглянуті раніше, відносяться до нижнього рівня, наприклад, семафори. Вони вимагають від програміста детального знання алгоритмів взаємного виключення, управління критичними секціями, вміння запобігати клінчі (взаємні блокування), а також володіння засобами відновлення після краху. Однак існують засоби синхронізації більш високого рівня, які звільняють програміста від необхідності вникати в всі ці подробиці і дозволяють йому сконцентрувати свою увагу на логіці алгоритмів та організації паралельних обчислень. Таким засобом є неподільна транзакція.

Модель неподільної транзакції прийшла з бізнесу. Уявіть собі переговорний процес двох фірм про продаж-купівлі певного товару. У процесі переговорів умови договору можуть багаторазово змінюватися, уточнюватися. Поки договір ще не підписаний обома сторонами, кожна з них може від нього відмовитися. Але після підписання контракту угода (transaction) повинна бути виконана.

Комп'ютерна транзакція повністю аналогічна. Один процес оголошує, що він хоче почати транзакцію з одним або більше процесами. Вони можуть деякий час створювати і знищувати різні об'єкти, виконувати будь-які операції. Потім ініціатор оголошує, що він хоче завершити транзакцію. Якщо все з ним погоджуються, то результат фіксується. Якщо один або більше процесів відмовляються (чи вони зазнали краху ще до вироблення згоди), тоді змінені об'єкти повертається точно до того стану, в якому вони перебували до початку виконання транзакції. Таку властивість "все-або-нічого" полегшує роботу програміста.

Для програмування з використанням транзакцій потрібно деякий набір примітивів, які повинні бути надані програмісту або операційної системою, або мовою програмування. Приклади примітивів такого роду:        BEGIN_TRANSACTION      команди, які йдуть за цим примітивом, формують транзакцію.             END_TRANSACTION      завершує транзакцію і намагається зафіксувати її.             ABORT_TRANSACTION      перериває транзакцію, відновлює попередні значення.             READ      читає дані з файлу (або іншого об'єкта)             WRITE      пише дані в файл (або інший об'єкт).     

Перші два примітиву використовуються для визначення меж транзакції. Операції між ними являють собою тіло транзакції. Або всі вони повинні бути виконані, або ні одна з них. Це може бути системний виклик, бібліотечна процедура або група операторів мови програмування, укладена в дужки.

Транзакції володіють наступними властивостями: упорядочіваемостью, неподільність, постійністю.

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

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

Сталість означає, що після фіксації транзакції ніякої збій не може скасувати результатів її виконання.

Якщо програмне забезпечення гарантує перераховані вище властивості, то це означає, що в системі підтримується механізм транзакцій.

Розглянемо деякі підходи до реалізації механізму транзакцій.

Згідно з першим підходом, коли процес починає транзакцію, то він працює в індивідуальному робочому просторі, що містить всі файли та інші об'єкти, до яких він має доступ. Поки транзакція не зафіксується або не перерветься, всі зміни даних відбуваються в цьому робочому просторі, а не в "реальному", під яким ми розуміємо звичайну файлову систему. Головна проблема цього підходу полягає у великих накладних витратах з копіювання великий обсяг даних в індивідуальне робочий простір, хоча і є декілька прийомів зменшення цих витрат.

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

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

Суть цього протоколу полягає в наступному. Один з процесів виконує функції координатора (малюнок 3.8). Координатор починає транзакцію, роблячи з?? пись про це у своєму журналі реєстрації, потім він посилає всім підлеглим процесів, також виконує цю дію, повідомлення "підготуватися до фіксації ". Коли підлеглі процеси отримують це повідомлення, то вони перевіряють, чи готові вони до фіксації, роблять запис у своєму журналі і посилають координатору повідомлення-відповідь "готовий до фіксації". Після цього підлеглі процеси залишаються в стані готовності і чекають від координатора команду фіксації. Якщо хоча б один з підлеглих процесів не відгукнувся, то координатор відкочується підлеглі транзакції, включаючи і ті, які підготувалися до фіксації.

Виконання другої фази полягає в тому, що координатор посилає команду "фіксувати" (commit) всім підлеглим процесам. Виконуючи цю команду, останні фіксують зміни і завершують підлеглі транзакції. У результаті гарантується одночасне синхронне завершення (вдале або невдале) розподіленої транзакції.

Рис. 3.8. Двофазний протокол фіксації транзакції