Я реализую потокобезопасный «ленивый синхронизированный» набор в виде связанного списка узлов, связанных с shared_ptr.Алгоритм из "Искусство многопроцессорного программирования".Я добавляю функцию is_empty(), которая должна быть линеаризуемой с существующими функциями: contains(), add(), remove().В приведенном ниже коде вы можете увидеть remove двухэтапный процесс.Сначала он «ленивый» помечает узел, устанавливая marked = nullptr, затем он физически перемещает связанный список next указатели.
Измененные классы для поддержки is_empty ()
template <class T>
class LazySet : public Set<T> {
public:
LazySet ();
bool contains (const T&) const;
bool is_empty () const;
bool add (const T&);
bool remove (const T&);
private:
bool validate(const std::shared_ptr<Node>&, const std::shared_ptr<Node>&);
class Node;
std::shared_ptr<Node> head;
std::shared_ptr<bool> counter; //note: type is unimportant, will never change true/fase
};
template <class T>
class LazySet<T>::Node {
public:
Node ();
Node (const T&);
T key;
std::shared_ptr<bool> marked; //assume initialized to = LazySet.counter
// nullptr means it's marked; otherwise unmarked
std::shared_ptr<Node> next;
std::mutex mtx;
};
Соответствующие измененныеметоды для поддержки is_empty
template <class T>
bool LazySet<T>::remove(const T& k) {
std::shared_ptr<Node> pred;
std::shared_ptr<Node> curr;
while (true) {
pred = head;
curr = atomic_load(&(head->next));
//Find window where key should be in sorted list
while ((curr) && (curr->key < k)) {
pred = atomic_load(&curr);
curr = atomic_load(&(curr->next));
}
//Aquire locks on the window, left to right locking prevents deadlock
(pred->mtx).lock();
if (curr) { //only lock if not nullptr
(curr->mtx).lock();
}
//Ensure window didn't change before locking, and then remove
if (validate(pred, curr)) {
if (!curr) { //key doesn't exist, do nothing
//## unimportant ##
} else { //key exists, remove it
atomic_store(&(curr->marked), nullptr); //logical "lazy" remove
atomic_store(&(pred->next), curr->next) //physically remove
(curr->mtx).unlock();
(pred->mtx).unlock();
return true;
}
} else {
//## unlock and loop again ##
}
}
}
template <class T>
bool LazySet<T>::contains(const T& k) const {
std::shared_ptr<Node> curr;
curr = atomic_load(&(head->next));
//Find window where key should be in sorted list
while ((curr) && (curr->key < k)) {
curr = atomic_load(&(curr->next));
}
//Check if key exists in window
if (curr) {
if (curr->key == k) { //key exists, unless marked
return (atomic_load(&(curr->marked)) != nullptr);
} else { //doesn't exist
return false;
}
} else { //doesn't exist
return false;
}
}
Node.marked изначально были простым булом, а LazySet.counter не существовало.Выбор сделать их shared_ptr должен был иметь возможность атомарно изменять как счетчик количества узлов, так и ленивую метку удаления на узлах.Модификация обоих одновременно в remove() необходима для того, чтобы is_empty() был линеаризуемым с contains().(Это не может быть отдельная метка bool и счетчик int без CAS двойной ширины или чего-то в этом роде.) Я надеюсь реализовать счетчик с помощью функции use_count() shared_ptr, но в многопоточных контекстах это только приблизительное значение из-за relaxed_memory_order.
Я знаю, что автономные заборы обычно являются плохой практикой, и я не слишком знаком с их использованием. Но если бы я реализовал is_empty, как показано ниже, ограждения гарантировали бы, что это уже не приближение, а точное значение для надежного счетчика?
template <class T>
bool LazySet<T>::is_empty() const {
// ## SOME FULL MEMORY BARRIER
if (counter.use_count() == 1) {
// ## SOME FULL MEMORY BARRIER
return true
}
// ## SOME FULL MEMORY BARRIER
return false
}
Я спрашиваю только потому, что LWG Issue 2776 гласит:
Мы не можем сделать use_count() надежным, не добавив значительно больше ограждений.