Atomic operations
Стало цікаво, як саме досягається атомарність операцій. Кому цікаво — ласкаво просимо під кат.
Атомарні операції - операції, що виконуються як єдине ціле або не виконуються зовсім. Т. е. це операція, під час виконання якої дані, що читаються/змінюються цією операцією, не можуть бути змінені іншою операцією. Є спеціальні асемблерні команди, які вказують процесору, що операція буде атомарною. Є кілька типів команд, за допомогою яких можна досягти атомарності: load-link and store-conditional (LL/SC), compare-and-swap (CAS) та інші.
Приклади команд LL/SC: ldl_l/stl_c та ldq_l/stq_c (Alpha), lwarx/stwcx (PowerPC), ll/sc (MIPS) та ldrex/strex (ARM version 6 and above). Команди дано парами, тому що перша завантажує поточне значення операнда в регістр або інше контрольоване місце, друга зберігає нове значення в операнд, якщо операнд за проміжок між 1 і 2 не змінився. Разом вони гарантують, що всі команди між ними працюють із однією версією операнда, яка була завантажена за допомогою LL. Наприклад візьмемо пару lwarx/stwcx (PowerPC):
Код взято звідси. У 6-й регістр завантажуються дані з операнда і він(операнд) резервується. Потім у 6-му регістрі отримуємо суму операнда та incr. Наприкінці вивантажуємо з регістра отриману суму операнд і відпускаємо його. Якщо в проміжок між резервуванням і звільненням операнда його значення буде змінено десь ще окрім поточної операції (навіть якщо було надано те саме значення, яке вже зберігалося в операнді), то ми отримаємо помилку. Це перевіряє 5-й рядок, що запускає операцію знову у разі помилки.
Принцип роботи простий - дивимося, яке значення зберігається в операнді. Якщо воно те, яке ми очікуємо, то міняємо його нанове. Алгоритм:
Розширення CAS - Double Compare And Swap (CAS2). Даються покажчики на дві незалежні змінні замість однієї відповідно два очікуваних значення і два нових значення для кожної змінної відповідно. Але ця група команд більш «слабка», ніж LL/SC, тому що можлива ситуація: початкові умови: compare_and_swap(reg, 5, 7) і *reg = 5; 1) int old_reg_val = * reg; (old_reg_val = 5) 2) інша операція робить * reg = 42; funny_stuff; * Reg = 5; 3) if (old_reg_val == oldval) - твердження вірне, хоча відбулося дві зміни значення змінної. Т. е. відбулася зміна, але наша операція про це не знає. Ця ситуація називається ABA проблемою. Є багато методів обходу цієї проблеми. Мені здався цікавим метод із використанням Double-Word Compare-And-Swap (часто плутається з Double Compare And Swap). Приклад:
Код взято звідси. Префікс «lock;» означає, що шина доступу до пам'яті може бути використана тільки наступною за нею командою. У слові, що передається, міститься покажчик на пам'ять з необхідним значенням і ABA номер, який змінюється з кожною операцією (побачив це в одному з патентів).
3. Прості атомарні операції.
Зазвичай це додавання чи інкрементація. Приклади команд: addl(i386), xaddl(x86). Ось реалізація атомарного додавання з вікіпедії:
На деяких архітектурах префікс "lock;" не потрібна. Приклад - інкрементування на Ітаніумі (взято звідси):
До речі, інкремент, декремент, +=, -= С++ атомарні (принаймні на х86 і х86_64). Префікса "lock;" ні, тож атомарності теж немає. Атомарні операції виникли в С++11.
Для декременту буде subl.
Висновок
Q: Це відомо кожному школяру! Навіщо про це писати? A: Мені було цікаво, як жевоно працює. Уявляв лише, що там є якісь lock'и. Сподіваюся, це було цікаво ще комусь.
Q: У статті купа помилок та неточностей. A: Пишіть, з радістю виправлю.
Хардкорна конфа за С++. Ми запрошуємо лише профі.
Читають зараз
Налаштування Atom від GitHub для роботи з PHP, Python та деякими іншими мовами програмування
Коли Atom швидше ніж Core?
ASUS Eee Box на Atom. Характеристики
Коментарі 33
> До речі, інкремент, декремент, +=, -= С++ атомарні (принаймні на х86 і х86_64).
Ні. Оскільки «одна асемблерна команда»! = «одна операція».
> Шину доступу до пам'яті
Та ні вже в сучасних процесорах та материнських платах жодних шин із загальним доступом! Там скрізь виділені point-to-point лінки: QPI, PCI Express - все це виділені point-to-point лінки, на кожному з яких рівно два пристрої, що обмінюються даними. Блокувати такі лінки від доступу кимось ще немає сенсу, тому що там більше нікого і немає.
Цілком можливо зробити одночасно кілька LL.
1. По-перше, імхо, читачам стане набагато зрозуміліше, якщо сказати, що «Атомарні Операції» можна поділити на два з половиною види:
1) Засоби, що дають потоку механізм для виявлення факту модифікації даних іншим потоком. 2) Кошти, що дають можливість «монопольного захоплення» осередку пам'яті в момент модифікації. 3) Неявні кошти
Операції одного виду є на всіх сучасних архітектурах, що передбачають «багатоядерність». Це LL/SC в RISC і CMPXCHG в X86.
Операції 2-го виду є ТІЛЬКИ в таких архітектурах (як X86), яким «як спадщину» дісталося розмаїття команд Читання-Модифікація-Запис у системі команд.(Тобто наявність memory-операнда призначення в арифметико-логічних операціях.) В архітектурах типу ARM таких команд просто немає (там тільки вважав у регістр – щось зробив – записав).
Операція 3-го виду - це операція обміну регістр осередок. Такі так, у тих архітектурах, де така «ассемблерова інструкція» має місце бути присутнім, процесор зазвичай «прозоро» вживає «заходи» (або ж явно пропонує кошти) для того, щоб в самий момент обміну не втрутився інший процесор.
2. Програмістів, які вирішили застосувати «Атомарні Операції», чекає кілька «пасток» з боку оптимізованого компілятора.
Пастка #1) Приклади асемблерних вставок вище, у яких відсутня asm(.«memory») - це потенційне джерело бага. Як ви думаєте, що буде, що «може спасти в голову компілятору» якщо ви не тільки «в тупу» «інкрементуєте/декрементуєте» комірку, але й «прочитали» до чи після цього значення з цієї комірки? Добра порада (щодо «memory»): А взагалі — якщо ви з асемблерної вставки вирішили «насрати» кудись у таємниці від компілятора, чи то регістр чи пам'ять — готуйтеся до неприємностей!
Пастка #2) Непрямо пов'язана з першим пунктом. А саме, якщо ви «Атомарні Операції» намагаєтеся використовувати, наприклад, для того, щоб змінити якийсь покажчик у структурі зробити потокобезпечною. Атомарні операції звичайно добре працюють з «пам'яттю» чи то ram-пам'ять, чи синхронізована багаторівнева система кешів у smp-системі, але вони не відносяться до РЕГІСТРІВ CPU. А саме в регістр cpu «покладе» компілятор значення вашого покажчика і як значення регістру він буде використовуватися. Тому, по-перше, не забуваємо про «volatile», а по-друге краще, щоб подібні значення поверталися з асемблерних вставок.
3.Атомарні операції, звичайно, добре. Однак далеко не завжди вони у чистому вигляді панацея. Готуйтеся до того, щоб грамотно розставити бар'єри читання/запису.
Потрібно ще згадати, що налагодження помилок виду «перегони сигналів» — найскладніше, що є взагалі у програмуванні. Тому вивчити асемблерні примітиви звичайно пізнавально, але в реальних проектах використовуйте тільки штатні механізми мови або ОС:)
Наш Кеп щойно забув згадати, що саме у «реальних helloworldhighload-проектах» і можна легко отримати десь так 1000. 1000000 кратний «профіт у перфомансі», при заміні оверхеда непотрібного перемикання завдань (що виникає, наприклад, коли кілька потоків «жопами штовхаються» на одному бездумно поставленому мутексі) на копійчану атомарну операцію «весь оверхед» якої кілька наносекунд (десяток машинних тактів у гіршому випадку).
Так, нічого не дається безкоштовно, а «знання особливо».
У реальних системах, про які я говорю, по-перше оптимізуються тільки _реально_ вузькі місця (про принцип Парето 20/80 ви напевно чули), і непомірний перфекціонізм зазвичай має правильну тенденцію жорстко припинятися (перевірені шматки коду працюють за принципом «працює-не чіпай» поки на них або на той шматок що формує для них дані явно не вкаже профайлер). Про те, що всі ті енхансменти, які прямо чи опосередковано можуть щось обрушити, проходять дуже жорсткі тести перед викатом на продакшен.
По-друге, щодо «тисяч мільйонів» якими ви мене намагаєтеся «налякати» — якщо у вас в системі «серйозного бізнесу», що претендує на роль, все «навалено в купу» без жорсткого поділу по серверах і зонах відповідальності (фінансова частина, платіжна, управлінська) , інтерфейсна, масивна обробка даних,контрольна, секуріті-частина, частина зовнішньої автоматичної взаємодії і т.д.) то це хронова архітектура інформсистеми (і в даному випадку в такій хроновій неізольованій архітектурі, «сотні тисяч мільйонів» збитку легко викличе і криворукий програміст-стажер, наприклад, «впиливающий» кнопочку «у форму» але помилився в назві методу). У хроновій архітектурі (наприклад «стрімкі» фінансові проводки «на тисячі мільйонів» не відловлюються відразу при виникненні і не вирушають «на розбір польотів» у СБ) можна втратити і «100%» записів і без будь-яких перегонів!
Тому мені будь ласка не треба, розповідати «жахливі історії», я вам сам можу за бажання розповісти багато чого… «Мавпа з гранатою» у вигляді програміста, який взагалі не має уявлення про «мультипотокові системи», при цьому не хоче навіть мати уявлення ( вважаючи, наприклад, що "про все подумає розумний компілятор") це, повірте, набагато гірше. До речі, як показує моя практика, ті програмісти, які не розуміють і не прагнуть розуміти «атомарні примітиви», вони… раптово точно також не вміють і не хочуть розуміти розуміти також і «штатні механізми мови чи ОС», на яких ви так наполягаєте! (Той, що занурює систему мутекс заради самого мутексу, або нічого і не від чого не захищає семафор заради семафору - ось весь продукт, за який я багаторазово особисто «бив по руках»). І ще один зворотний парадокс — ті програмісти, які зрозуміли «низький рівень» — вони якраз (як і я сам) без особливої необхідності «в нижні світи» не лазять, а в разі можливості використовують якраз «штатні кошти», але якщо вже "припрет" - так принаймні точно не обрушать систему "атоміком".
По-перше, якщо ви помітили, я ні кого не закликав "весь код переписувати на інлайн-асмі". До речі, я особисто жодного разу не бачив жодноготакого диво-програміста, який би на інлайн-асі «фігачив все».
По-друге, з чим я відразу не погодився — так це з вашою тезою «синхронізація — це занадто складно, а синхронізація за допомогою атомарних примітивів — ще складніше, тому не просто суйтеся туди» (адже я правильно зрозумів вашу Тезу, поправте якщо ні ).
По-третє, власне моя антитеза — нормальний програміст повинен знати як «синхронізація багатопоточки» влаштована всередині і причому добре знати. Знати, навіть якщо йому самому не доведеться «розрулювати дідлоки на асмі». Причому я стверджую, що програміст, який не знає «матчастину» як і чому виникають «перегони» у багатопотокових системах, просто не здатний правильно використовувати і «високрівневі речі». Щоб від чогось захиститься треба знати від чого захищатися.
По-четверте, щодо «профіту» та «ризиків». Я недаремно згадав про «принцип Парето». Якщо профайлер показує, що 98% часу потоки проводять "нариваючи" один мутекс, погодьтеся ігнорувати цей факт просто нерозумно. Так, я згоден, це «знання для просунутих», але в даному випадку… «бидлокодери» можуть навіть не знати про існування такого інструменту як «профайлер»;)
Ну, а по-п'яте, я особисто вважаю, що тема досить серйозна і важлива, щоб від неї просто «відмахуватися», посилаючись на «складність». Якщо "відкинути весь туман", то якраз все розкладається по поличках.
По-шосте, до речі «велосипедів» про які ви говорите — якраз і немає ніяких. Всі «типові операції» при застосуванні «атоміків» вже успішно відкатані в найбільш високонавантажених місцях нашої планети, всі їхні плюси та мінуси вивчені вздовж і впоперек, а ще їх можна чи не на пальцях перерахувати… але при цьому, на превеликий жаль «з -за туману» який наганяє «складність теми» це всене є надбанням широкого загалу. Багато хто «чув дзвін», але не знає де він! А результат, вибачте, плачевний — при «мільйонах» читачів англійської вікіпедії, жодна, вибачте, не звернула увагу на те, що в прикладах у лістингу є потенційний баг!
Власне, так, тема "не з легких", але це не привід її "замовчувати".