Мне интересно, можно ли создать безблокирующий, потокобезопасный общий указатель для любой из «общих» архитектур, например x64 или ARMv7 / ARMv8.
В своем выступлении о программировании без блокировки на cppcon2014 Херб Саттер представил (частичный) реализация безблокирующего односвязного списка. Реализация выглядит довольно простой, но она основана на атомарной реализации shared_ptr, которой еще нет в стандартной библиотеке, или на использовании специализированных std::atomic... функций. Это особенно важно, поскольку одиночные вызовы push / pop потенциально вызывают несколько атомарных загрузок / хранилищ и compare_exchange операций.
Проблема, которую я вижу (и я думаю, что некоторые вопросы в докладе были в том же направлении), заключается в том, что для того, чтобы это была фактическая структура данных без блокировок, эти атомарные операции сами должны быть свободными от блокировок. Я не знаю какой-либо реализации стандартной библиотеки для std::atomic... функций без блокировки и - по крайней мере, с помощью короткого поиска в Google / SO - я также не нашел предложения, как реализовать безблокировочную специализацию для std::atomic<std::shared_ptr> .
Теперь, прежде чем я буду тратить на это время, я хотел спросить:
- Знаете ли вы, можно ли вообще написать безблокирующий атомарный общий указатель?
- Существуют ли уже какие-либо реализации, которые я упустил из виду и - в идеале - даже совместимы с тем, что вы ожидаете от
std::atomic<std::shared_ptr>? Для упомянутой очереди особенно потребуетсяCAS-операция. - Если нет возможности реализовать это на текущих архитектурах, видите ли вы какие-либо другие преимущества в реализации Herb по сравнению с «обычным» связанным списком, защищенным блокировкой?
Для справки, вот код от Herb Sutter (может содержать мои опечатки):
template<class T>
class slist {
struct Node { T t; std::shared_ptr<Node> next; };
std::atomic<std::shared_ptr<Node>> head;
public:
class reference{
std::shared_ptr<Node> p;
public:
reference(std::shared_ptr<Node> p_){}
T& operator*(){ return p->t; }
T* operator->(){ return &p->t; }
};
auto find(T t) const {
auto p = head.load();
while (p && p-> != t) {
p = p - next;
}
return reference(move(p));
}
void push_front(T t) {
auto p = std::make_shared<Node>();
p->t = t;
p->next = head;
while (!head.compare_exchange_weak(p->next, p)) {}
}
void pop_front() {
auto p = head.load();
while (p && !head.compare_exchange_weak(p, p - next)) { ; }
}
};
Обратите внимание, что в этой реализации к отдельным экземплярам shared_ptr можно получить доступ / изменить несколько разных потоков. Его можно прочитать / скопировать, сбросить и даже удалить (как часть узла). Таким образом, речь идет не о том, могут ли несколько разных shared_ptr объектов (которые управляют одним и тем же объектом) использоваться несколькими потоками без состояния гонки - это уже верно для текущих реализаций и требуется стандартом, - а о параллельном доступе к одному экземпляр указателя, который - для стандартных общих указателей - не более потокобезопасен, чем те же операции с необработанными указателями.
Чтобы объяснить мою мотивацию:
Это в основном академический вопрос. Я не собираюсь внедрять свой собственный список свободных блокировок в производственный код, но я считаю эту тему интересной, и на первый взгляд презентация Херба показалась мне хорошим введением. Однако, размышляя над этим вопросом и комментарием @sehe к моему ответу, я вспомнил этот разговор, у меня был еще один посмотрите на это и поймете, что не имеет большого смысла называть реализацию Herb без блокировки, если для ее примитивных операций требуются блокировки (что они сейчас и делают). Поэтому мне было интересно, является ли это просто ограничением текущих реализаций или фундаментальным недостатком в дизайне.
shared_ptrs через функции [util.smartptr.shared.atomic]. Они хэшируют адрес объектаshared_ptrи используют глобальную хеш-таблицу мьютексов фиксированного размера. - person dyp schedule 07.07.2015