Почему очередь без блокировки использует тройной подсчет вместо двойного подсчета, используемого в стеке без блокировки? ⇐ C++

[Anonymous]

В параллелизме C ++ в действии очередь без блокировки реализована с тройным подсчетом. Основная структура его узлов заключается в следующем: < /p>

Код: Выделить всё

template  struct node;
template 
struct counted_node {
node *data;
long external_count;
};
template 
struct node {
struct compressed_counter {
unsigned long internal_counter : 62;
unsigned long head_tail_counter : 2;
};
std::atomic next;
std::atomic internal_counter;
std::atomic value;
};
< /code>
Структура двойного подсчета разработана как < /p>
template  struct node;
template 
struct counted_node {
node *data;
long external_count;
};
template 
struct node {
counted_node next;
std::atomic internal_count;
std::shared_ptr value;
};
< /code>
Очередь основана на односменном списке. Все узлы динамически распределяются, а значение node.data-> также динамически распределяется. Размер очереди не ограничен. Всегда есть пустой узел, служащий хвостом. При вставке нажмите сначала обновлять tail.data-> значение, затем выделяет новый узел без значения как hail.data-> Далее. При появлении сначала он проверяет, есть ли Head.data == tail.data; Если они равны, очередь считается пустой. В противном случае он удаляет первый узел. Чтобы избежать ситуации, когда толкание неоднократно встречается с хвостом, чьи хвост. Data-> Значение уже не пустое, когда операция CAS не удается, поток поможет другой потоке, выделяя новый хвостовой узел пустого значения, предотвращая ожидание занятости. < /P>
template 
class lock_free_queue {
private:
std::atomic head;
std::atomic tail;
public:
lock_free_queue() : head {new node {}}, tail {head} {
// if we implement it with triple counting, then
// this->head.data->internal_counter.head_tail_counter = 2;
// or if we implement with double counting
this->head.external_count = 2;
}
~lock_free_queue() noexcept {
while(this->pop());
}
void push(const T &t) {
auto value {std::make_unique(t)};
// increase external count of this->tail (old_tail)
// if (CAS) old_tail.data->value is nullptr, replace it by value.release()
// allocate a new node named new_tail
// if (CAS) old_tail.data->next is nullptr, replace it by new_tail
// free external count for old_tail (-2, tail part and push part)
}
std::unique_ptr pop() noexcept {
// increase external count of this->head (old_head)
// if old_head.data equals to this->tail.data, return nullptr
// if (CAS) old_head equals to this->head
// load the address of old_head.data->value
// making a object typed std::unique_ptr
// free external count for old_head (-1, head part)
// free external count for old_head (-1, pop part)
// return the result
}
};

Вы можете найти исходный код в https://github.com/anthonywilliams/ccia ... n/listings, listing_7.16.cpp to listing_7.22.cpp .

Код: Выделить всё

tail

счетчик внутри данных узла вместо непосредственного хранения его в External_count ? Однако в коде, показанном в книге, хвост только загружается и сравнивается; Я не вижу никакой фактической модификации данных узла хвоста (включая мелиорацию).

Подробнее здесь: https://stackoverflow.com/questions/797 ... nting-used