Атомный обмен двумя std :: atomic & lt; T * & gt; объекты без блокировки в C ++ 11?

Question

Атомный обмен двумя std :: atomic & lt; T * & gt; объекты без блокировки в C ++ 11?

Следующий код представляет собой скелет класса атомарного указателя, взятого из приложения с имитацией отжига в Пакет тестов PARSEC для мультипроцессоров с разделяемой памятью.

В этом приложении центральной структурой данных является граф (точнее, список цепей интегральных схем). Каждый узел в графе имеет атрибут, указывающий его физическое местоположение. Алгоритм порождает много потоков, и каждый поток многократно и случайным образом выбирает два узла и обменивается их физическими местоположениями, если это приводит к лучшей стоимости маршрутизации для чипа.

Поскольку граф огромен и любая пара может выбрать любую пару узлов, единственное работоспособное решение — параллельная структура данных без блокировки (CDS). Вот почему следующее AtomicPtr Класс имеет решающее значение (он используется для атомного обмена указателями на два объекта физического местоположения без блокировки).
Функция atomic_load_acq_ptr() является определенным в ассемблерном коде и близко соответствует std::atomic<T*>::load(memory_order_acquire),

Я хочу реализовать этот CDS, используя атомарность C ++ 11.

template <typename T>
class AtomicPtr {
private:
typedef long unsigned int ATOMIC_TYPE;
T *p __attribute__ ((aligned (8)));
static const T *ATOMIC_NULL;
inline T *Get() const {
T *val;
do {
val = (T *)atomic_load_acq_ptr((ATOMIC_TYPE *)&p);
} while(val == ATOMIC_NULL);
return val;
}
inline void Swap(AtomicPtr<T> &X) {
// Define partial order in which to acquire elements to prevent deadlocks
AtomicPtr<T> *first;
AtomicPtr<T> *last;
// Always process elements from lower to higher memory addresses
if (this < &X) {
first = this;
last  = &X;
} else {
first = &X;
last  = this;
}
// Acquire and update elements in correct order
T *valFirst = first->Checkout(); // This sets p to ATOMIC_NULL so all Get() calls will spin.
T *valLast  =  last->PrivateSet(valFirst);
first->Checkin(valLast); // This restores p to valLast
}
};

std::atomic<T*>::exchange() метод может быть использован только для обмена голым T* указатель с std::atomic<T*> объект. Как сделать обмен двух std::atomic<T*> объекты без блокировки?

Что я могу думать о том, что AtomicPtr Класс ниже может быть основан на std::atomic<T*> объявив:

std::atomic<T*> p;

и заменить все atomic_load_acq_ptr() звонки по std::atomic<T*>::load(memory_order_acquire) и заменить все atomic_store_rel_ptr() звонки по std::atomic<T*>::store(memory_order_release), Но моя первая мысль была, что std::atomic<T*> следует заменить AtomicPtr сам и там может быть умный способ обмена std::atomic<T*> объекты напрямую. Какие-нибудь мысли?

9

atomic atomicity c++c++11

Решение

Другие решения

Самое близкое, что вы можете прийти без спин-блокировки:

std::atomic<T> a;
std::atomic<T> b;
a = b.exchange(a);

Какой поток безопасен для b,

a не могут быть одновременно доступны.

2

Вы проверили операцию CAS (сравнить и поменять местами)?

   std::atomic<T*> v;

while(!v.compare_exchange_weak(old_value,new_value, std::memory_order_release, memory_order_relaxed))

0

Источник

Accepted Answer

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

Проблема в том, что нет возможности получить элементарные операции над двумя атомными объектами, поэтому вы должны выполнить процедуру:

заказать атомику (чтобы избежать тупиков)
«заблокировать» все, кроме последнего (в порядке возрастания)
выполнить операцию атомарно на последнем
выполнить операцию и «разблокировать» остальных по очереди (в порядке убывания)

Это, конечно, довольно несовершенно

не атомарный: пока вы заняты блокировкой переменной, любой из еще не заблокированных может изменить состояние
не препятствует освобождению: если по какой-то причине поток заблокирован, хотя заблокирована переменная, все остальные ожидающие потоки также блокируются; будьте осторожны, чтобы избежать взаимных блокировок (если у вас есть другие блокировки)
хрупкий: сбой после блокировки переменной оставляет вас в затруднительном положении, избегайте операций, которые могут вызвать бросок, и / или используйте RAII для «блокировки»

Однако на практике это должно работать относительно хорошо в случае только двух объектов (и, следовательно, одного для блокировки).

Наконец, у меня есть два замечания:

для того, чтобы заблокировать вам нужно иметь возможность определить значение дозорного, 0x01 обычно хорошо работает для указателей.
Стандарт C ++ не гарантирует, что std::atomic<T*> быть свободным от блокировки, вы можете проверить это для вашей конкретной реализации и платформы с std::atomic<T*>::is_lock_free(),

5