Вікіпедія

Алгоритм пекарні Лампорта

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

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

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

Алгоритм

ред.

Аналогія

ред.

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

За аналогією, "клієнти" є потоки, які отримали номер i з глобальної змінної.

Через обмеження комп'ютерної архітектури, деякі частини аналогії Лампорта потребують невеликої модифікації. Цілком можливо, що більш ніж один потік отримає таке ж число n, коли вони просять його; це не може бути попереджено. Таким чином, передбачається, що ідентифікатор потоку також є пріоритетом. Менше значення I означає більш високий пріоритет, і потоки з більш високим пріоритетом будуть входити в критичну секцію перші.

Критичний сектор

ред.

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

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

У псевдокоді ці порівняння між потоками А і В можуть бути записані у вигляді: 

(na, ia) < (nb, ib)

що еквівалентно: 

(na < nb) or ((na == nb) and (ia < ib))

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

Некритичний сектор

ред.

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

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

Реалізація алгоритму

ред.

Визначення

ред.

В оригінальній статті Лампорта, змінна виступає як вибір, і виконуються наступні умови:

  • Слова, які вибирають [I] і число [I] знаходяться в пам'яті процесу I, і ініціалізуються з нуля.
  • Діапазон значень числа [i] необмежена.
  • Процес може потерпіти невдачу в будь-який час. Ми припускаємо, що, коли він виходить з ладу, він відразу переходить до некретичної секції і зупиняється. Може бути період, коли читання з пам'яті дає довільні значення. Зрештою, будь-що, що зчитує дані з пам'яті повинно дати значення, рівне нулю. 

Приклади коду

ред.

Псевдокод

ред.

У цьому прикладі всі потоки виконуються ту ж "main" функцію,. У реальних додатках, різні потоки часто мають різні "main" функції.

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

  // declaration and initial values of global variables
  Entering: array [1..NUM_THREADS] of bool = {false};
  Number: array [1..NUM_THREADS] of integer = {0};

  lock(integer i) {
      Entering[i] = true;
      Number[i] = 1 + max(Number[1], ..., Number[NUM_THREADS]);
      Entering[i] = false;
      for (integer j = 1; j <= NUM_THREADS; j++) {
          // Wait until thread j receives its number:
          while (Entering[j]) { /* nothing */ }
          // Wait until all threads with smaller numbers or with the same
          // number, but with higher priority, finish their work:
          while ((Number[j] != 0) && ((Number[j], j) < (Number[i], i))) { /* nothing */ }
      }
  }
  
  unlock(integer i) {
      Number[i] = 0;
  }

  Thread(integer i) {
      while (true) {
          lock(i);
          // The critical section goes here...
          unlock(i);
          // non-critical section...
      }
  }

PlusCal код

ред.

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

CONSTANT N
ASSUME N \in Nat

Визначимо Р як безліч {1, 2, ..., N} процесів. 

P == 1..N

Змінні num і прапор оголошені як глобальні.

--algorithm AtomicBakery {
variable num = [i \in P |-> 0], flag = [i \in P |-> FALSE];

Нижче йде опис LL (J, I), щоб бути вірним, якщо << Num [J], J >> менше або дорівнює << Num [I], I >> в звичайне лексикографічне впорядкування. 

define { LL(j, i) == \/ num[j] < num[i]
                     \/ /\ num[i] = num[j]
                        /\ j =< i
       }

Для кожного елемента в Р існує процес з локальними непрочитаними зміними, макс.і наст. Кроки між послідовними мітками p1, ..., Р7, CS вважаються автономні. Оператор  (х \ in S) {} тіла встановлює ідентифікатор до недетермінірованного вибраного елемента S, а потім виконує тіло. Крок, який містить пріоритет чекає умови, крок може бути виконаний лише тоді, коли значення умови TRUE. 

process (p \in P)
  variables unread \in SUBSET P, 
            max \in Nat, 
            nxt \in P;
{
p1: while (TRUE) {
      unread := P \ {self} ;
      max := 0;
      flag[self] := TRUE;
p2:   while (unread # {}) {
        with (i \in unread) { unread := unread \ {i};
                              if (num[i] > max) { max := num[i]; }
         }
       };
p3:   num[self] := max + 1;
p4:   flag[self] := FALSE;
      unread := P \ {self} ;
p5:   while (unread # {}) {
        with (i \in unread) { nxt := i ; };
        await ~ flag[nxt];
p6:     await \/ num[nxt] = 0
              \/ LL(self, nxt) ;
        unread := unread \ {nxt};
        } ;
cs:   skip ;  \* the critical section;
p7:   num[self] := 0;
 }}
}

Java код

ред. 
 ArrayList<Integer> ticket = new ArrayList<>(threads); // ticket for threads in line, n - number of threads
 // Java initializes each element of 'ticket' to 0
 
 ArrayList<Boolean> entering = new ArrayList<>(threads); // 1 when thread entering in line
 // Java initializes each element of 'entering' to 0
 
 public void lock(int pid) // thread ID
 {
     entering.set(pid, true);
     int max = 0;
     for (int i = 0; i < threads; i++)
     {
         int current = ticket.get(i);
         if (current > max)
         {
             max = current;
         }
     }
     ticket.set(pid, 1 + max); 
     entering.set(pid, false);
     for (int i = 0; i < ticket.length(); ++i)
     {
         if (i != pid)
         {
             while (entering.get(i) == 1) { Thread.yield(); } // wait while other thread picks a ticket
             while (ticket.get(i) != 0 && ( ticket.get(pid) > ticket.get(i)  ||
                     (ticket.get(pid) == ticket.get(i) && pid > i)))
             { Thread.yield(); }
         }
     }
     // The critical section goes here...
 }

 public void unlock(int pid)
 {
   ticket.set(pid, 0);
 }

Обговорення

ред.

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

Необхідність змінної, яка входить може бути не очевидна, так як немає "закриття" навколо лінії 7 до 13. Проте, припустимо, що змінна була видалена, і два процеси обчислюється так само Number[i]. Якщо процес з більш високим пріоритетом був витіснений перед встановленнямNumber[i], процес з низьким пріоритетом буде бачити, що інший процес має значення нуля, і увійде в критичний сектор; пізніше, процес з високим пріоритетом буде ігнорувати рівній Number[i] для більш низького пріоритету процесів, а також увійде в критичний сектор. В результаті, два процеси можуть увійти в критичний сектор одночасно. Алгоритм пекарня використовує змінну введення, щоб робить призначення на лінії 6 як неподільними; В процесі I ніколи не  побачити число, рівне нулю для процесу J, який збирається вибрати таку ж кількість, як і I.

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

Алгоритм пекарні Лампорта передбачає послідовну модель узгодженості пам'яті. Мало хто, якщо такі є, мови або багатоядерні процесори можуть реалізувати таку модель пам'яті. Тому правильна реалізація алгоритму зазвичай вимагає вставки модифікацій для скасування перепризначення. [1]

Див. також

ред.

Посилання

ред.
  1. ↑ Chinmay Narayan, Shibashis Guha, S.Arun-Kumar Inferring Fences in a Concurrent Program Using SC proof of Correctness [Архівовано 4 листопада 2016 у Wayback Machine.]

Зовнішні посилання

ред.
Отримано з https://uk.wikipedia.org/wiki/Алгоритм_пекарні_Лампорта