Блокування черги на основі масиву

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

Огляд

[ред. | ред. код]

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

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

Блокування черги на основі масиву також гарантує справедливість отримання блокування, використовуючи механізм, заснований на черзі « перший прийшов, перший пішов» (FIFO). Крім того, кількість анулювань значно менша, ніж реалізація блокування на основі квитків, оскільки лише один процесор має помилку кешу при випуску блокування.

Впровадження

[ред. | ред. код]

Найголовніша вимога реалізації ABQL полягає в тому, щоб усі потоки оберталися в унікальних локаціях в пам'яті. Це досягається масивом у довжину, рівним кількості потоків, які є суперечливими для блокування. Усі елементи масиву позначаются за 0, за винятком першого елемента, який приймає значення 1, забезпечуючи тим самим успішне отримання блокування першим потоком у черзі. Після реалізації блокування утримування передається наступному потоку в черзі, встановлюючи наступний елемент масиву віному 1. Запити надаються потоками в порядку впровадження методуFIFO.

Приклад псевдокоду наведений нижче.[3]

ABQL_init(int *next_ticket, int *can_serve)
{
 *next_ticket = 0;
 for (int i = 1; i < MAXSIZE; i++)
  can_serve[i] = 0;
 can_serve[0] = 1; 
}

ABQL_acquire(int *next_ticket, int *can_serve)
{
 *my_ticket = fetch_and_inc(next_ticket);
 while (can_serve [*my_ticket] != 1) ; 
}

ABQL_release (int *can_serve)
{
 can_serve[*my_ticket + 1] = 1;
 can_serve[*my_ticket] = 0; // prepare for next time
}

Для реалізації блокування черги на основі масиву (ABQL) в псевдокоді, наведеному вище, додаються 3 змінних, а саме: can_serve, next_ticket і my_ticket. Ролі кожної з них описані нижче:

  • Масив can_serve представляє унікальні місця пам'яті, у яких обертаються потоки, які чекають у черзі для придбання блокування.
  • next_ticket представляє наступний доступний номер квитка, який присвоєний новому потоку.
  • my_ticket являє собою поток квитка кожного унікального потоку в черзі.

У методі ініціалізації (ABQL_init) змінна next_ticket позначається до 0. Усі елементи масиву can_serve, крім першого, іпозначаються до 0. Ініціалізація першого елемента масиву can_serve до 1, забезпечує успішне отримання блокування першим потоком у черзі.

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

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

Робота ABQL може бути зображена у таблиці нижче, припускаючи, що 4 процесори сперечаються за вхід у критичну секцію з припущенням, що потік входить у цю критичну секцію лише один раз.

Етапи виконання next_ticket can_serve my_ticket(P1) my_ticket(P2) my_ticket(P3) my_ticket(P4) Коментарі
спочатку 0 [1, 0, 0, 0] 0 0 0 0 початкове значення всіх змінних — 0
P1: fetch_and_inc 1 [1, 0, 0, 0] 0 0 0 0 P1 намагається і успішно отримує блокування
P2: fetch_and_inc 2 [1, 0, 0, 0] 0 1 0 0 P2 намагається придбати блокування
P3: fetch_and_inc 3 [1, 0, 0, 0] 0 1 2 0 P3 намагається придбати блокування
P4: fetch_and_inc 4 [1, 0, 0, 0] 0 1 2 3 P4 намагається придбати блокування
P1: can_serve[1] = 1;

can_serve[0] = 0

4 [0, 1, 0, 0] 0 1 2 3 P1 звільняється від блокування, а P2 успішно отримує блок
P2: can_serve[2] = 1;

can_serve[1] = 0

4 [0, 0, 1, 0] 0 1 2 3 P2 звільняється від блокування, а P3 успішно отримує блок
P3: can_serve[3] = 1;

can_serve[2] = 0

4 [0, 0, 0, 1] 0 1 2 3 P3 звільняється від блокування, а P4 успішно отримує блок
P1: can_serve[3] = 0 4 [0, 0, 0, 0] 0 1 2 3 P4 отримує блок.

Показники ефективності

[ред. | ред. код]

Для аналізу реалізації блокування можна використовувати такі реалізації:

  • Безперервна затримка придбання блокування — визначається як час, який потрібен потоку для придбання блокування, коли між потоками немає суперечок . Через відносно більшої кількості інструкцій, які виконуються на відміну від інших реалізацій, затримка незавдовільного замовлення для ABQL висока.
  • Трафік — він визначається як кількість генерованих транзакцій на шині, яка залежить від кількості потоків, які вступають в суперечку за блок. При отриманні блокування недійсний лише 1 блок кешу, що призводить до одного пропуску кешу. Це призводить до значно меншого пропуску шин.
  • Справедливість — всі процесори, які чекають на отримання блокування, зможуть зробити це в тому порядку, в якому отримуються їх запити. Завдяки потокам, які чекають у черзі, щоб отримати блокування із кожним потоком, що обертається в окремому місці пам'яті.
  • Зберігання — об'єм пам'яті, необхідний для обробки механізму блокування. Шкала вимоги до зберігання масштабується з кількістю потоків за рахунок збільшення розміру масиву can_serve.

Переваги

[ред. | ред. код]
  • ABQL пропонує покращену масштабованість, оскільки кожне придбання запускає лише 1 пропуск до кешу, що призводить лише до блокування цього кешу, який страждає від пропуску кешу, щоб перезавантажити блок.
  • Справедливість придбання блокування забезпечується завдяки використанню черги, яка забезпечує успішне отримання блокування в тому порядку, в якому видано їх потоки.

Недоліки

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

Див. також

[ред. | ред. код]

Список літератури

[ред. | ред. код]
  1. Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors. Архів оригіналу за 2 лютого 2021.
  2. Архівована копія (PDF). Архів оригіналу (PDF) за 27 жовтня 2020. Процитовано 12 грудня 2019.{{cite web}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title (посилання)
  3. Solihin, Yan (2009). Fundamentals of parallel computer architecture : multichip and multicore systems. с. 265—267. ISBN 978-0-9841630-0-7.