Одно слово КАС тегированный указатель для алгоритмов подвержены проблеме АБА


Я искал решение проблемы, абы за замок-бесплатная стека. Поиск в интернете показал, запатентованы и сложные указатели опасности и помечены указателями, используя двойное сравнение и замена (ДМАУ, сервер Cas2). Я бы довольствоваться ДМАУ, но она недоступна на некоторых старых процессорах AMD. Поэтому я придумал этот вспомогательный класс:

class TaggedPtrBase {
    typedef unsigned int tag_t;
    static const tag_t INVALIDATED = 1;
public:
    TaggedPtrBase() {
        tag.store(0, std::memory_order_relaxed);
        ptr = 0;
    }
    TaggedPtrBase & operator=(const TaggedPtrBase & other) {
        tag.store(other.tag.load(std::memory_order_acquire), std::memory_order_relaxed);
        ptr = other.ptr;
        return *this;
    }
    operator void *() const {
        return get();
    }
    void * get() const {
        return ptr;
    }
    bool compare_and_swap(const TaggedPtrBase & oldval, void * newptr) {
        uintptr_t old_tag = oldval.tag.load(std::memory_order_relaxed);
        if (old_tag & INVALIDATED) {
            return false;
        }
        if (tag.compare_exchange_strong(old_tag, old_tag | INVALIDATED, std::memory_order_acquire)) {
            ptr = newptr;
            tag.store(old_tag + 2, std::memory_order_release);
            return true;
        } else {
            return false;
        }
    }
private:
    std::atomic<tag_t> tag;
    void * ptr;
};
...
void push(Node * node) {
    void * newptr = reinterpret_cast<void *>(node);
    TaggedPtrBase old;
    do {
        old = ptr;
        node->next = static_cast<Node *>(old.get());
    } while (!ptr.compare_and_swap(old, newptr));
}

Это, кажется, работает, но его простота говорит о том, что я что-то упускаю. Поэтому я интересно, если это правильное решение, или это просто прославил спин-блокировки? Любые вопросы на платформах, отличных от х86?



940
4
задан 9 сентября 2011 в 12:09 Источник Поделиться
Комментарии
1 ответ

Это просто спин-блокировок. Если поток, который признан недействительным тега отстранили сразу после, никакой другой поток не может добиться прогресса, пока поток возобновляется и выпускает тег.

if (old_tag & INVALIDATED) {
return false; // no thread can go further if ...
}
if (tag.compare_exchange_strong(old_tag, old_tag | INVALIDATED,
std::memory_order_acquire)) {
ptr = newptr; // <-- ... a thread is preempted here
tag.store(old_tag + 2, std::memory_order_release);
return true;
}

Поэтому решение-это не блокировка-Free.

2
ответ дан 23 февраля 2012 в 09:02 Источник Поделиться