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


Глава із книги "Сучасне програмування на C++" називається "В сто перший раз про інтелектуальних покажчиках". Все б нічого, але книга була видана в 2001 році, так чи варто в черговий раз повертатися до цієї теми? Мені здається що якраз зараз і стоїть. За ці п'ятнадцять років змінилася сама точка зору, той кут під яким ми дивимося на проблему. У ті далекі часи тільки-тільки вийшла перша де-факто стандартна реалізація — boost::shared_ptr<>, до цього кожен писав собі реалізацію за потреби і як мінімум уявляв собі деталі, сильні і слабкі сторони свого коду. Всі книги з C++ в той час обов'язково описували одну з варіацій розумних покажчиків в найдрібніших деталях.
Зараз нам даний стандарт, і це добре. Але з іншого боку, вже не потрібно розуміти що там всередині, замість цього досить три рази повторити мантру "використовуйте розумні покажчики скрізь де ви б використовували звичайні покажчики", і це вже не так добре. Я підозрюю що далеко не всі віддають собі звіт що даний стандарт — лише один з можливих варіантів інтерфейсу, не кажучи вже про різницю між реалізаціями різних вендорів. При виборі стандарту був зроблений вибір між різними можливостями враховує різні фактори, але, оптимальний чи ні, цей вибір очевидно не один.
А ще на stackoverflow наприклад знову і знову задається питання — "потокобезопасны чи розумні покажчики із стандартної бібліотеки?". Відповіді даються зазвичай категоричні, але якісь мало інформативні. Якщо б я наприклад не знав про що йде мова, то напевно б не зрозумів. І до речі, все порівняно нові книги описують новий стандарт C++ цього питання теж приділяють мало уваги.
Так давайте ж спробуємо зірвати покриви і розберемося з деталями.
Відразу визначимося з термінологією, не йдеться про захист даних на які посилається вказівник, це може бути об'єкт довільної складності і багатопотоковий доступ до нього вимагає в загальному випадку окремої синхронізації. Під потокобезопасностью розумного покажчика ми маємо на увазі захищеність власне вказівника на дані і валідності внутрішнього лічильника посилань. Образно кажучи, якщо покажчики створюються через std::make_shared<>() то ніякі привласнення, передача в функції або інші потоки, свопи, знищення, не можуть привести його в невалидное стан. До тих пір поки ми не викликали reset() або get(), ми вправі очікувати, що покажчик посилається на деякий дійсний об'єкт, хоча і не обов'язково той, який ми маємо на увазі.
Один з популярних відповідей на питання заголовка: "It is only the control block itself which is thread-safe.". Ось ми і подивимося, що конкретно розуміється під control block під safe.
Для експериментів використовувався g++-5.4.0.
Почнемо з прикладу.
Нехай в поділюваної пам'яті знаходиться деяка інформація упакована в структуру і доступна через вказівник. Є один або безліч незалежних потоків, які повинні читати і використовувати ці дані без модифікації, як правило, виявляється, що для них критично важлива швидкість доступу. У той же час, нехай існує один або декілька потоків модифікуючих ці дані з порушенням цілісності, на практиці зазвичай виявляється що модифікації трапляються значно рідше і швидкість доступу там не настільки важлива. Тим не менш, залишаючись у рамках класичної (exclusive lock) синхронізації, ми змушені сериализации доступ на читання навіть якщо жодної зміни даних не відбулося. Природно, це відбивається на ефективності самим фатальним чином, і ця ситуація зустрічається настільки часто, можливо у дещо іншій версії, що я б її ризикнув назвати основним питанням багатопоточного програмування.
Звичайно існують стандартні рішення, boost::shared_mutex і його юний нащадок std::shared_mutex, що дозволяють два рівня доступу — розділяється на читання і винятковий на запис. Проте я, почувши що std::shared_ptr дає потокобезопасный доступ до контрольного блоку (і не дуже розуміючи що це означає), а так само що операції над ним реалізовані lock-free, хочу запропонувати своє витончене рішення:
// загальні дані
std::shared_ptr<SHARED_DATA> data;

reading_thread {
// створюємо резервну посилання на загальні дані
auto read_copy=data;
// читаємо дані, цілісність гарантована
...
// деструктор read_copy
}

writing thread {
// створюємо змінену копію даних 
auto update=std::make_shared<SHARED_DATA>(...args);
// атомарно(?) оновлюємо дані
data=update;
// посилання на старі дані втрачається, але об'єкт буде знищений 
// у пам'яті лише коли останній читач закінчить цикл читання
}

тут нам доводиться перестворювати структуру з даними кожен раз при кожному оновленні, однак це досить прийнятний випадок на практиці.
Ну так що, спрацює? Зрозуміло немає! чому саме?
Як воно влаштоване.
Якщо поглянути на саму структуру розділяється вказівника
/usr/include/c++/5/bits/shared_ptr_base.h: 1175
template < typename _Tp, _Lock_policy _Lp>
class __shared_ptr
{
...
private:
_Tp* _M_ptr; // Contained pointer.
__shared_count<_Lp> _M_refcount; // Reference counter.
};

видно, що вона складається з двох членів — покажчика на власне дані і того самого контрольного блоку. Але справа в тому, що не існує способу атомарно і без блокування поміняти, привласнити, перемістити і т. д. обидва елементи. Тобто поділювані покажчики потоко безпечними бути не можуть(.?) Крапка або знак питання? Ну начебто точка, але якась розпливчаста, не остаточна,-то це тривіально і занадто просто. Нам же було сказано, що "потоко безпечний доступ до контрольного блоку", а ми і не перевірили.
Давайте розбиратися, роєм глибше.
auto data=std::make_shared<int>(0);

void read_data() {
// імітація читання, створюється резервна копія даних
for(;;)
auto read_copy=data;
}

int main()
{
std::thread(read_data).detach();
// імітація запису, весь покажчик цілком замінюється іншим
for(;;)
data=std::make_shared<int>(0);
return 0;
}

Ось такий мінімалістський приклад реалізує запропоновану ідею і загалом виправдовує очікування — валиться з гуркотом ледь намотавши кілька сотень циклів. Однак зверніть увагу, до власне ми тут взагалі ні разу не звертаємося, вказівник не разыменовывается. Тобто щось недобре відбувається з контрольним блоком? Зате у нас тепер є код з яким можна працювати дебагером. Але спочатку кинемо погляд на інші можливі варіанти:
auto data=std::make_shared<int>(0);

void read_data() {
for(;;)
auto sp=std::atomic_load(&data);
}

int main(int argc, char**argv)
{
std::thread(read_data).detach();
for(;;) {
std::atomic_exchange(&data, std::make_shared<int>(0));
assert(std::atomic_is_lock_free(&data));
}
return 0;
}

тут все чудово роботаетло б якщо б не assert() у тілі циклу. Тобто атомарні операції над std::shared_ptr визначено, але вони блокують. Ну, це не наш шлях, на мьютексах я і сам можу. Ще один варіант:
std::shared_ptr<int> variant[]={
std::make_shared<int>(0),
std::make_shared<int>(0)
};
auto data=variant[0];

void read_data() {
for(;;)
auto sp=data;
}

int main()
{
std::thread(read_data).detach();
for(size_t n=0;; ++n) {
data=variant[n%2];
}

return 0;
}

майже ідентичний, але він чудово працює повністю завантажуючи два ядра під 100%. Різниця в тому, що тут один з потоків ніколи не викликає деструктор. Що ж, деструктори стандартних покажчиків небезпечні? Не вірю. Давайте повернемося до початкового варіанту і
копнемо ще глибше.
Розглянемо ближче читає потік:
auto sp=data;

Тут викликаються в циклі копіює конструктор і деструктор, і все.
ось вичавки з вихідного коду
//L1#shared_ptr_base.h : 662
__shared_count(const __shared_count& __r) noexcept
: _M_pi(__r._M_pi)
{
if (_M_pi != 0)
_M_pi->_M_add_ref_copy();
}
//L2#shared_ptr_base.h : 134
void
_M_add_ref_copy()
{ __gnu_cxx::__atomic_add_dispatch(&_M_use_count, 1); }

//L1#shared_ptr_base.h : 658
~__shared_count() noexcept
{
if (_M_pi != nullptr)
_M_pi->_M_release();
}
//L2#shared_ptr_base.h : 147
if (__gnu_cxx::__exchange_and_add_dispatch(&_M_use_count, -1) == 1)
{
_GLIBCXX_SYNCHRONIZATION_HAPPENS_AFTER(&_M_use_count);
_M_dispose();
}


що, якщо відкинути все зайве, зводяться до
// copy ctor
__gnu_cxx::__atomic_add_dispatch(&_M_use_count, 1);
// old instance dtor
if (__gnu_cxx::__exchange_and_add_dispatch(&_M_use_count, -1) == 1)
_M_dispose();

або, якщо перейти до псевдокоду
++_M_pi->_M_use_count;
if(--_M_pi->_M_use_count == 0)
dispose();

Тут оператори инкремента і декремента маються на увазі атомарними, а функція dispose() очищає пам'ять і зокрема инвалидирует сам вказівник на лічильник посилань _M_pi. Треба сказати, що для звиклого багатопоточності вираз
if(--cnt == 0)
do_something();
виглядає як граната з висмикнутою чекою, між цими двома рядками може статися, і обов'язково відбувається, буквально що завгодно. Єдине від чого така конструкція надійно захищає — це від аналогічного виклику в іншому потоці — скільки б разів не був викликаний атомарний оператор декремента, тільки в одному з них лічильник обнулиться.
Тим не менш, що в цей час відбувається в іншому, що пише, потоці?
  • викликається конструктор нового об'єкта. Це абсолютно незалежний об'єкт, тому нас ніяк не стосується.
  • створюється ще один вироджений покажчик
  • над цими трьома покажчиками викликається класичний циклічний swap()
  • викликається деструктор тимчасового покажчика містить тепер оригінальні дані)
  • викликається деструктор виродженого покажчика, нам це теж нічим не загрожує
десь ось так
//L1#shared_ptr.h : 291
shared_ptr&
operator=(shared_ptr&& __r) noexcept
{
this->__shared_ptr<_Tp>::operator=(std::move(__r));
//L2#shared_ptr_base.h : 997
__shared_ptr&
operator=(__shared_ptr&& __r) noexcept
{
__shared_ptr(std::move(__r)).swap(*this);
//L#3shared_ptr_base.h : 932
__shared_ptr(__shared_ptr&& __r) noexcept
: _M_ptr(__r._M_ptr), _M_refcount()
{
_M_refcount._M_swap(__r._M_refcount);
//L#4shared_ptr_base.h : 684
void _M_swap(__shared_count& __r) noexcept
{
_Sp_counted_base<_Lp>* __tmp = __r._M_pi;
__r._M_pi = _M_pi;
_M_pi = __tmp;
}
//L2#shared_ptr_base.h : 1073
void
swap(__shared_ptr<_Tp, _Lp>& __other) noexcept
{
std::swap(_M_ptr, __other._M_ptr);
_M_refcount._M_swap(__other._M_refcount);
}
//L3#shared_ptr_base.h : 684
void
_M_swap(__shared_count& __r) noexcept
{
_Sp_counted_base<_Lp>* __tmp = __r._M_pi;
__r._M_pi = _M_pi;
_M_pi = __tmp;
}
//L2#shared_ptr_base.h : 658
~__shared_count() noexcept
{
if (_M_pi != nullptr)
_M_pi->_M_release();
}
//L3#shared_ptr_base.h : 142
void
_M_release() noexcept
{
// Be race-detector-friendly. For more info see bits/c++config.
_GLIBCXX_SYNCHRONIZATION_HAPPENS_BEFORE(&_M_use_count);
if (__gnu_cxx::__exchange_and_add_dispatch(&_M_use_count, -1) == 1)
{
_GLIBCXX_SYNCHRONIZATION_HAPPENS_AFTER(&_M_use_count);
_M_dispose();
//L1#shared_ptr.h : 93 (destructor)
//L2#shared_ptr_base.h : 658
~__shared_count() noexcept
{
if (_M_pi != nullptr) //_M_pi == nullptr - true here
_M_pi->_M_release();
}

якщо відкинути все зайве залишаться приблизно такі фрагменти коду:
_Sp_counted_base<_Lp>* __tmp = __r._M_pi;
__r._M_pi = _M_pi;
_M_pi = __tmp;
if (__gnu_cxx::__exchange_and_add_dispatch(&_M_use_count, -1) == 1)
_M_dispose();

знову ж таки, перші три рядки (swap()) виглядають надзвичайно підозрілими, однак при ретельному аналізі вони виявляються абсолютно безпечними (природно, тільки в даному контексті) і все що нам залишається (псевдокод)
if(--_M_pi->_M_use_count == 0)
dispose();

той самий вираз, що ми трохи вище визнали безпечним. Ось тут настає момент істини:
// assert(_M_use_count == 1);







// writing thread // reading thread if(--_M_pi->_M_use_count == 0) //true . . ++_M_pi->_M_use_count; // count=1 . if(--_M_pi->_M_use_count == 0) //true dispose(); // я перший! BANG!! dispose(); // ні я! BANG!!
Ось так комбінація атомарного инкремента і атомарного декремента призводить до перегонах між потоками і std::shared_ptr<> не є потокобезопасным, навіть на рівні контрольного блоку. Ось тепер дійсно точка.
Трохи пізніше я знайшов афористично короткий виклад цього принципу у документації до boost::shared_ptr<>. Звучить приблизно так: "Покажчики безпечні або тільки на запис або тільки на читання, і небезпечні при конкурентному читанні/запису." Трохи розвинувши цю думку і зрозумівши що гола запис без читання даних практично безглузда, ми бачимо що стандартні розумні покажчики безпечні на читання, тобто настільки ж наскільки безпечні звичайні константные покажчики. Тобто, вся ця складна внутрішня машинерія створена для того щоб досягти рівня звичайних покажчиків, але не більше, жирна крапка.
Замість висновку. Від аналізу до синтезу.
Хотілося б закінчити на світлій ноті, тобто запропонувати, хоча б на рівні концепції, алгоритм не використовує блокуючих м'ютексів і дозволяє безпечні операції з розділяються покажчиками з різних потоків. Однак я не впорався, більше того, у мене склалося переконання, що на основі існуючих елементарних неблокирующих примітив це просто неможливо. Зрозуміло достатньо просто написати варіант заснований на spinlock, однак це було б неспортивно, я не відношу такі алгоритми до істинно неблокирующим. Можна взяти за основу будь-яку існуючу багатопотокову блокує реалізацію і замінити кожен м'ютекс на відповідний spinlock, тобто алгоритмічно звести задачу до вибору більш ефективного типу м'ютексу. Очевидно це не наш шлях.
Чого ж нам не вистачає для повноцінного неблокірующіх реалізації? Існує дуже невелика кількість неблокирующих примітив працюють тільки з вбудованими типами:
  • додавання цілої константи (постфиксное або префиксное) — atomic_fetch_and_add і його варіації
  • обмін двох значень (насправді несиметричний, тільки один із операндів змінюється атомарно) — atomic_swap
  • умовний обмін або привласнення з перевіркою на рівність — atomic_compare_and_swap
Враховуючи безумовний заборона на оператор if() неблокирующих алгоритмах, тільки останній підходить на роль оператора розгалуження, але його серйозне обмеження в тому, що він дозволяє перевірку і привласнення виключно однієї і тієї ж змінної. Взагалі легко помітити щось загальне у всіх трьох примітивах — вони атомарно працюють з однією і тільки однією областю пам'яті розміром з машинне слово, причини я думаю очевидні. Придивившись до узагальненій структурі розділяється покажчика, ми бачимо що він зобов'язаний містити усередині себе як мінімум один покажчик на загальні дані (включають контрольний блок), де цього блоку повинен знаходитися лічильник посилань. При будь-яких операціях з власне покажчиком, наприклад присвоєння, ми повинні атомарно перевіряти лічильник і одночасно змінювати вказівник на контрольний блок, що неможливо використовуючи існуючі атомарні примітиви. Звідси випливає, що створення повноцінного неблокірующіх розділяється покажчика неможливо в принципі.
Насправді я був би радий помилитися, можливо є щось, що я не знаю чи неправильно розумію? Всіх бажаючих оскаржити чекаю в коментарях.
Джерело: Хабрахабр

0 коментарів

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