Алгоритм розподіленого взаємного виключення Лампорта

Алгоритм розподіленого взаємного виключення Лємпорта - це алгоритм на основі конкуренції взаємного виключення в розподіленої системі .

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

Алгоритм

Вузлові властивості

Алгоритм дозволяє дозволяє розглядати таку чергу у вигляді окремого об'єкта, яке поділяється між усіма процесами, а не знаходиться під управлінням одного єдиного процесу (координатора). Кожен процес підтримує чергу очікують запитів для входу в критичний розділ по порядку. Черги впорядковані по віртуальним мітках часу, отриманим з міток часу Лампорта.

Алгоритм

Процес запиту

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

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

Правила алгоритму

Позначимо через Qi локальну чергу процесу Pi, в яку поміщаються всі запити для доступу до КС разом з їх відмітками часу.

1. Запит на вхід в КС.Коли процесу Рi потрібен доступ до КС, він розсилає повідомлення REQUEST (Li, i) зі значенням свого логічного часу (Li, i) всім іншим процесам і, крім того, поміщає цей запит в свою чергу Qi. Кожна така розсилка є одною атомарною подією процесу Рi. Коли процес Pj отримує запит REQUEST (Li, i) від процесу Рi, він поміщає його в свою чергу Qj і відправляє процесу Рi відповідь REPLY (Lj, j) зі значенням свого логічного часу (Lj, j).
2. Вхід в КС. Процес Рi може увійти в КС, якщо одночасно виконуються дві умови. Запит REQUEST (Li, i) процесу Рi володіє найменшим значенням позначки часу серед всіх запитів, які перебувають у його власній черзі Qi.Процес Рi отримав повідомлення від усіх інших процесів в системі з відміткою часу більшою, ніж (Li, i). За умови того, що канали зв'язку мають властивість FIFO, дотримання цього правила гарантує, що процесу Рi відомо про всі запитах, що передують його поточним запитом.
3. Виход з КС. При виході з КС процес Рi видаляє свій запит з власної черги Qi і розсилає всім іншим процесам повідомлення RELEASE (Li, i) з відміткою свого логічного часу. Як і раніше кожна така розсилка є одним атомарному подія процесу Рi. Отримавши повідомлення RELEASE (Li, i), процес Pj видаляє запит процесу Рi зі своєї черги Qj. Після видалення процесом Pj запиту процесу Рi з Qj відмітка часу його власного запиту може виявитися меншою в Qj, і Pj зможе розраховувати на вхід в КС.

Складність повідомлення

Цей алгоритм створює 3 (N - 1) повідомлення на запит або (N - 1) повідомлень і 2 широкомовних повідомлення. 3 (N - 1) повідомлення на запит включають в себе:

1. (N - 1) загальна кількість запитів
3. (N - 1) загальна кількість відповідей
5. (N - 1) загальна кількість випусків

Переваги

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

Недоліки

• Це досить ненадійно, так як збій будь-якого з процесів зупинить прогрес.
• Він має високу складність повідомлень - 3 (N - 1) повідомлення на вхід / вихід в критичну секцію.