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

Блокування черги на основі масиву (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(P2)}	_{my_ticket(P3)}	_{my_ticket(P4)}	Коментарі
спочатку	0	[1, 0, 0, 0]	0	0	0	початкове значення всіх змінних — 0
P1: fetch_and_inc	1	[1, 0, 0, 0]	0	0	0	P1 намагається і успішно отримує блокування
P2: fetch_and_inc	2	[1, 0, 0, 0]	1	0	0	P2 намагається придбати блокування
P3: fetch_and_inc	3	[1, 0, 0, 0]	1	2	0	P3 намагається придбати блокування
P4: fetch_and_inc	4	[1, 0, 0, 0]	1	2	3	P4 намагається придбати блокування
P1: can_serve[1] = 1; can_serve[0] = 0	4	[0, 1, 0, 0]	1	2	3	P1 звільняється від блокування, а P2 успішно отримує блок
P2: can_serve[2] = 1; can_serve[1] = 0	4	[0, 0, 1, 0]	1	2	3	P2 звільняється від блокування, а P3 успішно отримує блок
P3: can_serve[3] = 1; can_serve[2] = 0	4	[0, 0, 0, 1]	1	2	3	P3 звільняється від блокування, а P4 успішно отримує блок
P1: can_serve[3] = 0	4	[0, 0, 0, 0]	1	2	3	P4 отримує блок.

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

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

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

Переваги

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

Недоліки

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

Див. також

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

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

[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.

[1]

[2]

[3]