Thread-safe shared_ptr , Реализация потоко-безопасного SharedPtr

[Олег М]

Цитата ЫукпШ @ 22.01.17, 22:07

Никакой потокобезопасностью даже не пахнет.
3 машинные команды, передача управления другому потоку может произойти между ними.

Всё правильно, операции ++, -- и т.д. не являются атомарными для базовых типов. Для этого следует использовать interlocked-функции. Либо класс std::atomic, как сделано у меня. Тогда всё будет хорошо. И не забывать про модификатор volatile

[Славян]

Цитата ЫукпШ @ 22.01.17, 22:07

Хотя казалось что будет что-то вроде (но увы..):

            inc DWORD PTR Count

Наверное, чуть правильнее так:

           lock inc DWORD PTR Count

[Олег М]

Сервер проработал несколько дней, поэтому можно сделать предварительный вывод, что код рабочий. Хотя 100-процентной уверенности так и нет. Жду, что кто-нибудь даст мне идеи, когда этот код не работает. Вообще, там есть есть две вещи, которые мне не нравились с самого начала:
- совершенно отвратительный статический CSharedPtrLock. Но ничего более умного я не смог придумать, чтоб ограничить доступ к указателю на счётчик;
- функция CSharedPtr::get(). Хотелось бы обращаться к указателю без использования atomic-операции.

[Cfon]

нашел статейку от Саттера:
https://www.infoq.com/news/2014/10/cpp-lock-free-programming
отсюда надо плясать?

Сообщение отредактировано: Cfon - 23.01.17, 17:12

[Олег М]

Не знаю даже, статей полно, причём конкретно эта мне кажется какой-то мутной. В частности реализация single-linked list при помощи shared_ptr.
Там одна операция auto p = make_shared<Node>(); уже не является lock-free

[Cfon]

Саттер налажал?

[Олег М]

Мне, кстати, вообще не даёт создать std::atomic<std::shared_ptr<std::string>>, говорит error: static assertion failed: std::atomic requires a trivially copyable type

[shm]

И не должен.

[Олег М]

Не знаю даже. Основная проблема при реализации single-linked - это то что ты не можешь поменять значение указателя при помощи compare_exchange. Нужно менять значение пары {счётчик, указател}. Соответственно head представляет из себя структуру {size_t, void *}. shared_ptr же - это два указателя, как им можно заменить счётчик, я не знаю.

[ЫукпШ]

Цитата Славян @ 23.01.17, 14:25

Цитата ЫукпШ @ 22.01.17, 22:07

Хотя казалось что будет что-то вроде (но увы..):

            inc DWORD PTR Count

Наверное, чуть правильнее так:

           lock inc DWORD PTR Count

Теоретически "да", но не факт.
Нужно точно знать аппаратое устройство машины, а арбитр шины
теперь наверняка внутри процессора.
"Lock" - это всего-лишь пин процессора, торчащий провод.
Сигнал принимает активное значение на время команды, снабжённой
одноимённым преффиксом.
Куда он запаян разработчиком заранее не всегда извесно.
Например, у IBMPC-AT он просто висел в воздухе.

Добавлено 23.01.17, 18:35

Цитата Олег М @ 23.01.17, 05:55

Для этого следует использовать interlocked-функции.

Тут есть рекомендации. Глава 8

Цитата

...
Применяйте эту методику с крайней осторожностью, потому что процессорное время
при спин-блокировке тратится впустую Процессору приходится постоянно сравнивать
два значения, пока одно из них не будет "волшебным образом» изменено другим потоком.
Учтите - этот код подразумевает, что все потоки, использующие спин блокировку,
имеют одинаковый уровень приоритета. К тому же. Вам, наверное, при дется отключить
динамическое повышение приоритета этих потоков (вызовом SetProcessPriorityBoost или SetThreadPriorityBoost).
...
Спин-блокировка предполагает, что защищенный ресурс не бывает занят надолго.
И тогда эффективнее делать так: выполнять цикл, переходить в режим ядра и ждать.
Многие разработчики повторяют цикл некоторое число раз (скажем, 4000) и, если ресурс к тому
времени не освободился, переводят поток в режим ядра, где он спит, ожидая освобождения ресурса
(и не расходуя процессорное время). По такой схеме реализуются критические секции (critical sections).
...

Сообщение отредактировано: ЫукпШ - 23.01.17, 18:36

[Олег М]

ЫукпШ Собственно, я её, методику, и применяю с крайней осторожность, ресурс вроде не блокируется надолго.

[Flex Ferrum]

Цитата Олег М @ 20.01.17, 17:46

А как цикл с compare_exchange может не учитывать особенности работы системы? Или учитывать?

Цикл с compare_exchange - это цикл, для которого компилятор сгенерирует какой-то код. А как долго допустимо его крутить? Может есть что-то специализированное типа futex'ов? Или ещё чего такое, предложенное вендорами компилятора или оси? Как-то так.

Цитата Олег М @ 21.01.17, 08:43

В смысле, ты имеешь ввиду, почему я не делаю AddRef () {return ++m_cnt != 1;}? Потому что так нельзя. Если счётчик равен нулю, то его нельзя увеличивать, иначе когда несколько потоков будут одновременно вызывать AddRef(), только одному вернётся false, остальным - true и указатель на объект который был удалён.

Ещё раз повторюсь: я первый раз вижу такую логику работы со счетчиками ссылок. Конечно, эта логика обусловлена особенностями дизайна твоего класса, но вопрос в том: а насколько верный дизайн, что приходится прибегать к таким вот костылям? Как по мне, так хороший вопрос.

Цитата Олег М @ 22.01.17, 07:13

Итак - зачем мне это нужно?
1. Тренировка мозгов. Когда работаешь с потоками ошибку сделать легко, но найти её можно только путём пристального разглядывания и анализа исходного кода. Для этого нужно всегда быть в форме и помнить о нюансах и правилах. Lock-free алгоритмы - хорошая тренировка.

Тренировка мозгов - это, конечно, хорошо. Но на изначальный вопрос это не отвечает: в каких именно сценариях (реальных сценариях) планируется использовать такие указатели? Увы...

Цитата Олег М @ 22.01.17, 07:13

2. Повторное использования кода. Когда тебе постоянно приходится блокировать экземпляр какого-то класса, придумывать названия для мьютексов, следить, чтобы они блокировались-разблокировались вовремя и тд и тп, поневоле задумаешься - а не сделать ли этот класс потоко-безопасным? Потратить один раз время и забыть об этих проблемах. C классами типа контейнеров, строк и т.д. это делать тяжеловато, да и особо не нужно - они блокируются относительно редко и по-разному. Но указатели - другое дело, они простые, и они используются часто.

Ну... Как сказать... Повторное использование кода - это, конечно, хорошо. Но... Самый хороший многопоточный код - это такой, который не шарит ресурсы между потоками. Вот вообще. То есть когда потоки друг другу не мешают. Когда же появляются разделяемые ресурсы - доступ к ним приходится синхронизировать, да. И потоко-безопасные классы - это не панацея. Совсем не панацея. Именно поэтому я в n-ый раз прошу сценарий. Какая задача решается? Для каких гвоздей нужен этот микроскоп? Ведь, возможно, для такой задачи существует традиционное, давно зарекомендовавшее себя решение.

Цитата Олег М @ 22.01.17, 07:13

3. Минимизация времени блокировки. Не думаю (вернее, не знаю как), что можно заблокировать shared_ptr на меньшее время, причём независимо от других указателей. Например есть большое количество объектов, которые создаются/удаляются в одних потоках, обрабатываются в других. Для решения этой задачи я пользуюсь следующим методом:
- В обработчике хранится список list<weak_ptr> и мьютекс
- Когда мне надо что-то с ним сделать, я блокирую этот мьютекс, переношу список в локальную переменную при помощи move-конструктора, разблокирую
- Пробегаюсь по локальному списку, если weak_ptr::lock возвращает null, удаляю из локального списка, иначе вызываю какую-нибудь функцию
- Снова блокирую список, делаю list::splice, т.е. возвращаю не удалённые объекты обратно
Все операции копеечные и никаких дедлоков

Вот это похоже на более-менее реальный кейс, похожий на что-то типа паттерна producer/consumer или publisher/subscriber. Причём тут ты написал вполне себе адекватную реализацию с помощью "внешнего" мьютекса, который синхронизирует доступ к разделяемому ресурсу (некоему списку). Осталось только понять - что там с shared_ptr'ами, на которые ты weak_ptr'ы хранишь, происходит. И почему тебе нужна грануляция уровня одного объекта, а не коллекций. И почему ты не можешь работать с копиями shared_ptr'ов.

[Олег М]

Цитата Flex Ferrum @ 23.01.17, 22:32

Цикл с compare_exchange - это цикл, для которого компилятор сгенерирует какой-то код. А как долго допустимо его крутить? Может есть что-то специализированное типа futex'ов?

Как и любой другой цикл, пока не выполнится условие выхода. Lock-free алгоритмы как правило сходятся, т.е. не приводят к бесконечным циклам.

Цитата Flex Ferrum @ 23.01.17, 22:32

Ещё раз повторюсь: я первый раз вижу такую логику работы со счетчиками ссылок. Конечно, эта логика обусловлена особенностями дизайна твоего класса, но вопрос в том: а насколько верный дизайн, что приходится прибегать к таким вот костылям? Как по мне, так хороший вопрос.

Я не знаю, что ты называешь костылями, сам стараюсь не пользоваться этим термином. Если ты знаешь какую-то другую реализацию такого счётчика, просто покажи и всё. Лично я только с такой и знаком.

Цитата Flex Ferrum @ 23.01.17, 22:32

Самый хороший многопоточный код - это такой, который не шарит ресурсы между потоками. Вот вообще.

Не факт, что хороший. Ты наверное хотел сказать - легче всего писать.

Добавлено 24.01.17, 06:03

Цитата Flex Ferrum @ 23.01.17, 22:32

. Осталось только понять - что там с shared_ptr'ами, на которые ты weak_ptr'ы хранишь, происходит. И почему тебе нужна грануляция уровня одного объекта, а не коллекций. И почему ты не можешь работать с копиями shared_ptr'ов.

Потому что shared_ptr - это тоже блокировки, только блокирует она не доступ к объекту, а время жизни объекта. Здесь тоже желательно соблюдать правило минимизации - объект должен жить ровно столько сколько требуется, не больше, не меньше.
Когда ты хранишь где-то список shared_ptr, это значит, что ты должен управлять временем жизни объектов. Для этого тебе придётся написать функцию для удаления объектов из этого списка и гарантировать, что она вызывается везде, где это нужно (причём в деструкторе объекта не получится) и хранить какую-то ссылку на этот список. Ещё и придётся отказаться от списка и использовать map. Всё это, скорее всего, придётся реализовывать каждый раз заново и потом поддерживать, до кучи ещё с дедлоками воевать.
Всё это можно свести к вызовам weak_ptr::lock и shared_ptr::reset. Конечно есть свои нюансы и накладные расходы, но в целом код упрощается в разы и работает надёжнее.

Добавлено 24.01.17, 06:19
Пример такой:
Есть сервер, который генерирует события, и есть обработчики этих событий. Время жизни, создание/удаление, обработчика никак не зависит от этого сервера, и единственное что ему, обработчику, нужно - зарегистрировать себя на сервере, всё. Даже ссылку на сервер хранить не обязательно.
С помощью shared_ptr/weak_ptr эта задача решается легко и красиво. Нет никаких лишних зависимостей, никаких лишних блокировок, лишнего кода и проблем.

Сообщение отредактировано: Олег М - 24.01.17, 06:20

[Flex Ferrum]

Ага. Значит таки имеет место реализация паттерна pub-sub. Ну, тогда у меня две новости: одна плохая, другая - тоже плохая. Первая: этот паттерн прекрасно реализуется на стандартных смарт-указателях. Вторая: твои экзерсизы с потокобезопасными указателями не избавляют код от одной довольно неприятной гонки (ну, если я правильно понимаю, как там у тебя всё устроено).
Как этот паттерн обычно реализуются у меня. Есть список (вектор, лист, мама - не суть) shared_ptr-ов на дескрипторы подписчиков. В каждом дпскрипторе содержится: указатель (голый) на подписчика, мьютекс и признак того, что подписчик вообще жив. Ну и ещё один мьютекс на весь список. Дальше, реализуются следующие сценарии:
1. Подписка. Создаётся (через make_shared) дескриптор, заполняются поля и под глобальным мьютексом кладется в таблицу.
2. Оповещение подписчиков. Под глобальным мьютексом снимается копия списка. Дальше - обход. Для каждого элемента уже под его лочкой проверяется - жив ли он (в смысле, не случилась ли отписка) и, если жив, под этой же лочкой делается вызов.
3. Отписка. Под глобальной лочкой в списке ищется нужный дескриптор, извлекается в локальную переменную. Не под глобальной, но под локальной лочкой, ей сбрасывается признак "живости" и указатель на клиента, потом делается выход.

Почему это именно так, и почему это работает:
1. Подписчикам (при регистрации) нет необходимости передавать смарт-указатели на себе. Они подписываются и всё. Как хотят - так и подписываются.
2. Указатель на дескриптор клиента умирает тогда, когда умирает последняя копия указателя на него. Тут shared_ptr-используются по прямому назначению.
3. (важно!) обеспечивается синхронизация между отпиской клиента и его нотификацией. Если этой синхронизации не будет, то клиент (каждый!) должен будет работать из расчёта на то, что отписка ничего не гарантирует. И после отписки ему всё равно могут придти вызовы. Клиентов обычно очень расстраивает этот факт.
4. Такая реализация заточена на то, что подписка/отписка - гораздо более редкие операции, чем нотификация. Поэтому лочки мьютексами почти не влияют на производительность.

Не знаю, насколько п.4 для тебя верен, но п.3 твой код точно не реализует за счёт этой вот предварительной оптимизации с атомиками и lock-free.

[Олег М]

Ну да, схема тут, незамысловатая. Я, кстати, тоже обычно не передаю указатель на себя. Передаю ссылку на функцию и параметры, если нужно.
Я примерно так и делал, пока не обратил внимания, что такой дескриптор, собственно, дублирует функционал shared_ptr/weak_ptr. Только +мютекс, +флаг и +shared_ptr. Решил, что это как-то накладно.

Цитата Flex Ferrum @ 24.01.17, 07:27

3. (важно!) обеспечивается синхронизация между отпиской клиента и его нотификацией. Если этой синхронизации не будет, то клиент (каждый!) должен будет работать из расчёта на то, что отписка ничего не гарантирует. И после отписки ему всё равно могут придти вызовы. Клиентов обычно очень расстраивает этот факт.

Согласен, в моём случае это действительно проблема. Приходится о ней помнить.
В твоём случае вызов делается под блокировкой и под той же блокировкой происходит отписка. Здесь возможен дедлок, об этом тоже надо постоянно помнить.