Огляд примітивів синхронізації — спинлоки і таємниці ядра процесора

Остання стаття про класичні примітиви синхронізації.

(Напевно, потім напишу ще одну про зовсім вже нетипову задачу, але це потім.)

Сьогодні ми трошки заглянемо в процесор. Трохи.

По суті, ми будемо говорити про єдиний примітив, який принципово відрізняється від інших: спинлок. Spinlock.

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

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

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

Справа в тому, що всередині ядра м'ютекс реалізований з допомогою спинлоков, а ось спинлоки реалізовані самі по собі, автономно. Вони — дійсно базовий примітив. Нижче — тільки сам процесор.

Є і ще одне, семантичне розходження. М'ютекс допускає і передбачає зняття нитки з процесора, довгу зупинку викликає нитки. Мьютексом можна замкнути об'єкт на годину або добу, це прийнятно і нормально. Спинлок принципово розрахований тільки на найкоротші призупинення, це завжди робота з неатомарным стейтом об'єкта. Присвоювання групи змінних, невеликий цикл — це максимум того, що можна зробити під спинлоком.

Отже, ієрархія реалізації така: mutex/cond/sema зроблені на базі спинлоков, спинлоки — на базі атомарних операцій, що надаються процесором. Ми в них трохи заглянемо сьогодні.

Як влаштований спинлок?

Принцип неймовірно простий. Спинлок — це просто змінна, яка містить нуль або одиницю (бувають варіанти).

Якщо нуль — спинлок вільний, і його можна захопити. Якщо не нуль — спинлок замкнений, та нитка, яка прагне його захопити, буде чекати, крутячись (spin — обертання) у невеличкому циклі безперервної перевірки звільнення спинлока. Ось, власне, реалізація:

while( ! _spin_try_lock( &(sl->lock) ) )
while( sl->lock )
;


Операція _spin_try_lock — атомарна, реалізована на асемблері відповідного процесора. Намагаємося замкнути спинлок, якщо не вдалося — крутимося в циклі, поки він замкнений, потім знову намагаємося.

Ось і все, що в цілому.

Тепер деталі. Операція _spin_try_lock теж дуже проста:

#define _spin_try_lock(p)\
(!({ register int _r__; \
__asm__ volatile("movl $1, %0; \n\
xchgl %0, %1" \
: "=&r" (_r__), "=m" (*(p)) ); \
_r__; }))


Справа в тому, що інструкція xchgl процесора Інтел атомарно обмінює місцями регістр і змінну в пам'яті. Атомарно з урахуванням можливої роботи інших процесорів, тобто в середовищі SMP.

Що відбувається? Ми міняємо місцями значення sl->lock і регістр, в якому лежить одиниця. Якщо спинлок не був замкнений (sl->lock був рівний нулю), він стане дорівнює одиниці і _spin_try_lock поверне нуль — ми успішно замкнули спинлок. Якщо sl->lock був дорівнює одиниці, то в підсумку sl->lock після обміну знову буде дорівнює одиниці, але і результатом _spin_try_lock буде лічений попереднє значення sl->lock — одиниця, що означає неуспіх захоплення спинлока.

Взагалі проблема з атомарними операціями на рівні процесора дуже велика. Поки в системі один процесор, цієї проблеми немає. Але й такої ситуації реально теж давно вже немає. Навіть у дешевих машинах вже кілька процесорів, або один багатоядерний, та/або гипертредный.

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

Цікаво, що є зовсім інша схема роботи з атомарними об'єктами. Процесори mips не мають інструкції виду «атомарно щось зробити з коміркою пам'яті». Замість цього у MIPS є цікава зв'язана пара інструкцій:

LL - load linked
 
SC - store conditional
 


Перша інструкція — load linked — просто читає значення з пам'яті. Але при цьому в процесорі зводиться тригер, який «стежить» за зчитаної осередком — не було в неї запису.

Друга — store conditional — зберігає значення в пам'ять. Але! Якщо з часу виконання load linked в клітинку хтось вже записав нове значення, store conditional поверне ознака неуспіху (і, звичайно, нічого в комірку пам'яті записувати не буде).

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


На відміну від Интеловского xchg така пара дозволяє робити не тільки спинлоки, але і реалізовувати більш складні алгоритми. Повернемося до розмови про семафорах:

rpos = atomic_add( &read_pos, 1 );
ret = buf[rpos];
read_pos %= sizeof(buf);


Всі проблеми з цим кодом на процесорі MIPS можна вирішити досить просто:

do 
{
rpos = load_linked( &read_pos )
ret = buf[rpos++];
rpos %= sizeof(buf);
} while( !store_conditional( &read_pos, rpos ) );


На жаль, такий код буде нестерпний. Хоча і досить ефективний. Втім, для реально критичних ділянок можна виконати і процессоро-залежну оптимізацію.

Що ще важливо знати про спинлоки в середовищі ядра ОС (або при програмуванні для мікроконтролерів, де, як правило, немає режиму користувача): при захопленні спинлока переривання повинні бути заборонені.

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

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

Повертаючись до питання про мьютексах і спинлоках: всередині спинлока багато чого не можна. Не можна спати — нас чекають, не можна перемикати контекст (віддавати процесор) — це загрожує дедлоком аналогічно ситуації з перериваннями. Не можна викликати функції, які мають шанс виконати вищезазначене. Наприклад, в ядрі або код мікроконтролера може бути неможливо викликати malloc — як правило, він сам синхронізований і може при нестачі пам'яті очікувати її звільнення. Ну і, наприклад, можуть бути під забороною функції запису в лог — особливо якщо вони намагаються відправити дані на сервер логування через syslog over UDP.

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

На цьому вважатимемо огляд традиційних примітивів синхронізації завершеним. Через тиждень я постараюся повернутися до теми і остаточно підірвати вам мозок статтею про проблеми реалізації примітивів синхронізації в середовищі персистентной віртуальної пам'яті. :)

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.