Розподілене виключне виконання

Розподілена система (англ. Distributed System, DS) - територіально роз'єднані групи користувачів, що виконують більшу частину необхідних операцій обробки прямо на місці, проте одночасно забезпечують доступ до великої центральної ЕОМ для виконання завдань, які вимагають наявності потужної універсальної ЕОМ. У цьому визначенні обмовляються два моменти. Перший відноситься до апаратури: всі машини автономні. Другий стосується програмного забезпечення: користувачі думають, що мають справу з єдиною системою. Важливі обидва моменти. Можливо, замість того щоб розглядати визначення, розумніше буде зосередитися на важливих характеристиках розподілених систем. Перша з таких характеристик полягає в тому, що від користувачів приховані відмінності між комп'ютерами і способи зв'язку між ними. Те ж саме відноситься і до зовнішньої організації розподілених систем. Іншою важливою характеристикою розподілених систем є спосіб, за допомогою якого користувачі і додатки одноманітно працюють в розподілених системах, незалежно від того, де і коли відбувається їх взаємодія.

Взаємне виключення у розподіленому середовищі

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

• на основі використання центрального фізичного годинника;
• на основі центрального координатора.

Розподілені алгоритми з використанням базованого на часі (time-based) впорядкування подій

• розподілений алгоритм Лампорта;
• децентралізований алгоритм на основі  часових поміток;
• алгоритм широкомовний маркерний.

Розподілені алгоритми з використанням передачі поміток

• алгоритм token-ring (логічне кільце);
• алгоритм логічного дерева.

Взаємне виключення у розподіленому середовищі – загальні вимоги

Якщо N процесів поділяють один ресурс та вимагають взаємно виключного доступу, то мають задовольнятися такі умови:

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

Припущення:

1. Повідомлення між двома процесами отримуються у порядку їх посилання;
2. Кожне повідомлення в кінцевому випадку отримується;
3. Кожен процес може надіслати повідомлення будь-якому іншому.

Центральний фізичний годинник

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

Рис.1. Приклад реалізації взаємного виключення у розподіленому середовищі; алгоритм з центральним координатором; CS (Critical Section) – критична секція.

Перевагою такого алгоритму є простота, але він має такі істотні недоліки:

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

Центральний координатор. Щоб увійти до критичної секції, процес посилає повідомлення - запит до центрального координатора та чекає на відповідь (див. Рис.1.) .

Розподілений алгоритм Лампорта (1978).

Кожен процес підтримує свою власну чергу запитів, впорядкованих за значеннями часових поміток. Запит до критичної секції (КС):

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

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

Звільнення критичної секції

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

   

   Рис.2. Приклад реалізації взаємного виключення у розподіленому середовищі; розподілений алгоритм Лемпорта.

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

На  Рис. 2. показано конкретний приклад дії даного алгоритму. Обидва процеси 0 та 2 посилають запити до КС. Кожен відповідає, процес 0 входить до КС, бо його запит був першим. Процес 0 звільняє КС, процес 2 входить до неї .

Децентралізований алгоритм на основі часових поміток

Алгоритм запропоновано в (Ricart&Agrawala) і є поліпшенням алгоритму, що запропонував Лампорт. Потрібно глобальне упорядкування всіх подій у системі за часом.

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

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

Вихід із критичної секції. Після виходу із секції він посилає повідомлення "OK" усім процесам, запитам які він запам'ятав, а потім стирає всі запам’ятовані запити.

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

Розширення для К спільних ресурсів

Процес може увійти до КС як тільки він отримає N-K повідомлень-відповідей. Алгоритм, загалом, такий самий як [Р&А (алгоритм Рікарта та Агравала)] з однією різницею: N-K повідомлень-відповідей надходять, коли процес чекає, щоб увійти до КС; нші К-1 повідомлень-відповідей можуть надходити, коли процес знаходиться у КС, після того, як він залишає КС або, коли він чекає, щоб увійти до КС знову. Необхідно зберігати у пам’яті системи кількість очікуючих процесів.

Алгоритм Token-Ring

Процеси розташовані у логічне кільце. На початку одному з процесів  надається маркер. Маркер циркулює по колу у визначеному напрямку за допомогою “двоточкових” (point-to-point) повідомлень. Коли процес має маркер, він має право увійти до КС. Після виходу з КС, він передає маркер далі.

Алгоритм широкомовний маркерний

Маркер містить чергу запитів та масив LN[1...N] з номерами останніх удоволених запитів.

Вхід у критичну секцію. Якщо процес Pk, що запитує критичну секцію, не має маркера, то він збільшує порядковий номер своїх запитів RNk[k] і посилає широкомовно повідомлення "ЗАПИТ", що містить номер процесу (k) і номер запиту (Sn=RNk[k]). Процес Pk виконує критичну секцію, якщо має (чи коли одержить) маркер.

Поводження процесу при прийомі запиту. Коли процес Pj одержить повідомлення-запит від процесу Pk, він установлює RNj[k]=max(RNj[k],Sn). Якщо Pj має вільний маркер, то він його посилає Pk тільки в тому випадку, коли RNj[k]=LN[k]+1 (запит не старий).

Вихід із критичної секції процесу Pk. Процес установлює LN[k] у маркері рівним RNk[k]. Для кожного Pj, для якого RNk[j]=LN[j]+1, він додає його ідентифікатор у маркерну чергу запитів. Якщо маркерна черга запитів не порожня, то з неї виділяється перший елемент, а маркер посилається відповідному процесу (запит якого був першим у черзі) .

Алгоритм деревоподібний маркерний

Усі процеси представлені у виді збалансованого двійкового дерева. Кожен процес має чергу запитів від себе і сусідніх процесів (1-го, 2-х чи 3-х) і покажчик у напрямку власника маркера.

Вхід у критичну секцію. Якщо є маркер, то процес виконує КС. Якщо немає маркера, то процес поміщає свій запит у чергу запитів та посилає повідомлення "ЗАПИТ" у напрямку власника маркера і чекає повідомлень.

Поводження процесу при прийомі повідомлень. Процес, що не знаходиться усередині КС повинен реагувати на повідомлення двох видів -"МАРКЕР" і "ЗАПИТ".

Якщо прийшло повідомлення "МАРКЕР" то:

1. Взяти 1-ий запит з черги і послати маркер його автору (концептуально можливо собі).
2. Поміняти значення покажчика убік маркера.
3. Виключити запит з черги.
4. Якщо в черзі залишилися запити, то послати повідомлення "ЗАПИТ" убік маркера.

Якщо прийшло повідомлення "ЗАПИТ", помістити запит у чергу. Якщо немає маркера, то послати повідомлення "ЗАПИТ" убік маркера, інакше (якщо є маркер) - перейти до обробки повідомлення "МАРКЕР".

Вихід із критичної секції. Якщо черга запитів порожня, то при виході нічого не робиться, інакше - перейти до обробки повідомлення "МАРКЕР".

Алгоритми вибору (Election Algorithms)

У розподілених системах багато алгоритмів вимагають наявності постійного або тимчасового лідера:

Розподілене взаємне виключення:

• Алгоритм центрального координатора  вимагає наявності координатора;
• Алгоритм token-ring, алгоритм Сузукі-Касамі та алгоритм дерева Реймонда вимагає наявності елементу, що на початку буде мати маркер (token);
• Розподілене виявлення тупиків (deadlock) – вимагає наявності утримувача (maintainer) глобального графа очікування (wait-for graph);
• Якщо лідер виходить з ладу, повинен бути обраний новий лідер;
• Алгоритми вибору припускають, що кожен потік має унікальний пріоритетний номер.

Мета: обрати лідером потік з найвищим пріоритетом, повідомити усім активним потокам.

Друга мета: дозволити поновленому лідеру відновити контроль (або, хоча б, розпізнати поточного лідера) .

Алгоритм Гарсіа-Моліна (Garcia-Molina’s)

У цьому алгоритмі є три типи повідомлень:

Рис.3. Алгоритм вибору координатора

1. вибір – анонсує про вибір;
2. відповідь – підтверджує прийом повідомлення про вибір;
3. координатор – анонсує про нового координатора.

Вибір: процес починає вибір якщо до нього надходить інформація, що координатор вийшов з ладу (див. Рис.3.). Щоб це зробити, він посилає вибір-повідомлення усім потокам з вищими пріоритетами. Потім він чекає на відповідь (від діючого потоку з вищим пріоритетом). Якщо повідомлень деякий час немає, він проголошує себе координатором та посилає повідомлення-координатор усім потокам з нижчими пріоритетами.

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

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

Участь у виборі: якщо процес отримує повідомлення - вибір, він посилає назад повідомлення – відповідь.

Пошкоджені процеси

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

Розрахунки: N-2 повідомлень у найкращому випадку O(N2) повідомлень у найгіршому випадку.

Алгоритм  кільця Чанга та Робертса (Chang, Roberts)

Рис.4. Вибір координатора на основі алгоритму «логічне кільце».

• Процеси розташовані у логічне кільце (див. Рис.4.).
• Кожен процес спочатку не-учасник (non-participant).
• Процес починає вибір тим, що помічає себе як учасника (participant).
• Посилає повідомлення - вибір, що містить його ідентифікатор, своїм сусідам.

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

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

Коли процес отримує вибране повідомлення, він помічає себе як не-учасника та передає повідомлення далі до свого сусіда.

Розрахунки: 3N-1 повідомлень у найгіршому випадку. N-1 повідомлень вибір, щоб досягти найближчого сусіда у неправильному напрямку, N повідомлень вибір, щоб вибрати його, потім N вибраних повідомлень, щоб проголосити про результат.

Джерела

1. Дорошенко А.Ю., Кислоокий В.М., Синявський О.Л. Архітектура і операційні середовища комп’ютерних систем.
2. Дорошенко А.Ю. Лекціі з паралельних обчислювальних систем. Київ: Видавничий дім “КМ Академія”, 2003. – 42 с.
3. В. Корнеев, Параллельные вычислительные системы.−М. Ноулидж. − 1999.
4. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления.– СПб.: БХВ-Петербург, 2002.–608 с.
5. Гергель В.П. Теория и практика параллельных вичислений / Гергель В.П. – Москва: Интернет-Университет, БИНОМ. Лаборатория знаний, 2007. – 314 с.
6. Agarwal V., Petrini F., Pasetto D., Bader D. Scalable graph exploration on multicore processors // Proceedings of the ACM/IEEE Supercomputing 2010 Conference. New Orleans, LA, November 13–19, 2010.
7. Buluc A., Madduri K.: Parallel breadth-first search on distributed memory systems // Proceedings of the ACM/IEEE Supercomputing 2011 Conference. November 2011.
8. Kang S., Bader D. Large scale complex network analysis using the hybrid combination of a MapReduce cluster and a highly multithreaded system // 4th 12 Workshop on Multithreaded Architectures and Applications (MTAAP), Atlanta, GA, April 23, 2010.