第七章lock_义齿
8731 ワード
queueに関連する2つの操作がhead tailポインタに対応するため、以前の参照カウントを使用してstackを実装したのとは異なります.
だから簡単に前の技術を使ってlockを設計すればfreeアルゴリズムは適切ではありません.このような状況が発生する可能性があります.
tailポインタが指向するノードを離れた後、他のスレッドはこのノードを解放したが、headポインタはまだこのノードにアクセスしていないので、後でpopを呼び出す人がいたら.そうすれば
だから1つの__を設定すべきですm_external_count
これは_Nodeノードでは2に初期化され、tail headがアクセスしたときにのみ減算され、それぞれ対応する関数_free_external_count
具体的に理解するには、本章のstackの実现を読んでください.あなたは私の意味を理解することができます(以上は本人の心得で、同じ初心者で、理解にずれがあるかもしれませんが、具体的な読者はこの本の内容を参考にすることができます.
質問があればメールアドレスもご利用いただけます[email protected])
だから簡単に前の技術を使ってlockを設計すればfreeアルゴリズムは適切ではありません.このような状況が発生する可能性があります.
tailポインタが指向するノードを離れた後、他のスレッドはこのノードを解放したが、headポインタはまだこのノードにアクセスしていないので、後でpopを呼び出す人がいたら.そうすれば
だから1つの__を設定すべきですm_external_count
これは_Nodeノードでは2に初期化され、tail headがアクセスしたときにのみ減算され、それぞれ対応する関数_free_external_count
具体的に理解するには、本章のstackの実现を読んでください.あなたは私の意味を理解することができます(以上は本人の心得で、同じ初心者で、理解にずれがあるかもしれませんが、具体的な読者はこの本の内容を参考にすることができます.
質問があればメールアドレスもご利用いただけます[email protected])
#include <iostream>
#include <atomic>
#include <memory>
#include <thread>
#include <future>
#if defined _DEBUG
#include <crtdbg.h>
#define __MEMORY__LEAK__CHECK__ _CrtSetDbgFlag( \
_CrtSetDbgFlag(_CRTDBG_REPORT_FLAG) | \
_CRTDBG_LEAK_CHECK_DF);
#define __leak__check__ __MEMORY__LEAK__CHECK__
#endif
namespace stc{
template <typename _Ty>
struct __node;
template <typename _Ty>
struct __count_node{
typedef typename __node<_Ty>* __node_pointer;
int __m_external_count;
__node_pointer __m_src;
/**data member*/
/**the consructor*/
__count_node() :__m_external_count(0),
__m_src(NULL){}
};
/**
* stack ， queue head tail
* ， ：
* tail ， ， head ，
* , pop。 undefined behavior
* __m_external_count
* __node 2， tail head ， __free_external_count
* ， stack ，
*/
struct __inside_counter{
int __m_internal_count : 30;
unsigned int __m_external_count : 2;
};/**the inside counter */
template <typename _Ty>
struct __node{
typedef _Ty* __pointer;
typedef _Ty& __reference;
typedef typename std::atomic<__pointer> __atomic_data_type;
typedef typename std::atomic<__count_node<_Ty>> __atomic_link_type;
typedef typename std::atomic<__inside_counter> __atomic_count_type;
__atomic_data_type __m_data;
__atomic_count_type __m_counter;
__atomic_link_type __m_next;
__node() :__m_data(NULL){
__inside_counter __counter_init;
__counter_init.__m_external_count = 2;
__counter_init.__m_internal_count = 0;
__m_counter.store(__counter_init, std::memory_order_release);
}
void __release_reference();
};
template <typename _Ty>
void __node<_Ty>::__release_reference(){
__inside_counter __o_count = __m_counter.load(std::memory_order_relaxed);
__inside_counter __n_count;
do{
__n_count = __o_count;
--__n_count.__m_internal_count;
} while (!__m_counter.compare_exchange_strong(__o_count, __n_count,
std::memory_order_acquire, std::memory_order_relaxed));
if (!__n_count.__m_external_count &&
!__n_count.__m_internal_count){
delete this;
}
}
template <typename _Ty>
class lk_free_que_s{
typedef typename __count_node<_Ty> __count_node_type;
typedef typename std::atomic<__count_node_type> __atomic_count_node_type;
public:
lk_free_que_s();
~lk_free_que_s();
std::unique_ptr<_Ty> pop();
void push(const _Ty&);
private:
static void __increase_external_count(__atomic_count_node_type&, __count_node_type&);
static void __free_external_count(__count_node_type&);
void __set_tail(__count_node_type&, __count_node_type);
void __init();
void __destroy();
void __clear();
void __reset();
__count_node_type __allocate_count_node();
private:
__atomic_count_node_type __m_head;
__atomic_count_node_type __m_tail;
};
template <typename _Ty>
lk_free_que_s<_Ty>::lk_free_que_s(){
this->__init();
}
template <typename _Ty>
lk_free_que_s<_Ty>::~lk_free_que_s(){
this->__destroy();
}
template <typename _Ty>
void lk_free_que_s<_Ty>::__init(){
__count_node_type nil = __allocate_count_node();
try{
__m_head.store(nil, std::memory_order_release);
__m_tail.store(nil, std::memory_order_release);
}catch (...){
delete nil.__m_src;
throw;
}
}
template <typename _Ty>
void lk_free_que_s<_Ty>::__destroy(){
try{
while (pop());
delete __m_tail.load().__m_src;
} catch (...){}
}
template <typename _Ty>
typename lk_free_que_s<_Ty>::__count_node_type
lk_free_que_s<_Ty>::__allocate_count_node(){
try{
std::unique_ptr<__node<_Ty>> __src(new __node<_Ty>);
__count_node_type __res;
__res.__m_external_count = 1;
__res.__m_src = __src.get();
__src.release();
return __res;
}
catch (...){ throw; }
}
/**
*
*/
template <typename _Ty>
void lk_free_que_s<_Ty>::__increase_external_count(
__atomic_count_node_type& __head, __count_node_type& __o_counter){
__count_node_type __n_counter;
do{
__n_counter = __o_counter;
++__n_counter.__m_external_count;
} while (!__head.compare_exchange_strong(__o_counter,__n_counter,
std::memory_order_acquire,std::memory_order_relaxed));
__o_counter.__m_external_count = __n_counter.__m_external_count;
}
template <typename _Ty>
void lk_free_que_s<_Ty>::__free_external_count(__count_node_type& __o_counter){
__node<_Ty>* __src = __o_counter.__m_src;
assert(__src != NULL);
const int __count_result = __o_counter.__m_external_count - 2;
__inside_counter __o_inside_counter = __src->__m_counter.load(std::memory_order_relaxed);
__inside_counter __n_inside_counter;
do{
__n_inside_counter = __o_inside_counter;
--__n_inside_counter.__m_external_count;
__n_inside_counter.__m_internal_count += __count_result;
} while (!__src->__m_counter.compare_exchange_strong(__o_inside_counter,__n_inside_counter,
std::memory_order_acquire,std::memory_order_relaxed));
if (!__n_inside_counter.__m_external_count &&
!__n_inside_counter.__m_internal_count){
delete __src;
}
}
template <typename _Ty>
std::unique_ptr<_Ty> lk_free_que_s<_Ty>::pop(){
__count_node_type __o_head = __m_head.load(std::memory_order_relaxed);//
while (true){//increase count reference
__increase_external_count(__m_head, __o_head);
__node<_Ty>* __src = __o_head.__m_src;
if (__src == __m_tail.load().__m_src){// __m_head __m_tail
__src->__release_reference();//decrease count reference
return std::unique_ptr<_Ty>();//return null pointer
}
__count_node_type __next = __src->__m_next.load();//get the next node
if (__m_head.compare_exchange_strong(__o_head, __next)){//if the head is't changed than the value of head will be the next node
std::unique_ptr<_Ty> __res(__src->__m_data.exchange(NULL));
__free_external_count(__o_head);//decrease count reference
return __res;//return the result
}
__src->__release_reference();//decrease count reference
}
}
template <typename _Ty>
void lk_free_que_s<_Ty>::push(const _Ty& __data){
std::unique_ptr<_Ty> __src(new _Ty(__data));
_Ty* __o_data = NULL;
__count_node_type __n_next = __allocate_count_node();//
__count_node_type __o_tail = __m_tail.load();//
while (true){
__increase_external_count(__m_tail, __o_tail);
__o_data = NULL;// ， __m_tail
if (__o_tail.__m_src->__m_data.compare_exchange_strong(__o_data, __src.get())){
__count_node_type __o_next;//
// next __count_node_type object
if (!__o_tail.__m_src->__m_next.compare_exchange_strong(__o_next, __n_next)){
delete __n_next.__m_src;// __m_tail， __node
__n_next = __o_next;//
}
__set_tail(__o_tail, __n_next);// ， __free_external_count
__src.release();// __release_reference
return;// ，
}else{// ，
__count_node_type __o_next;
if (__o_tail.__m_src->__m_next.compare_exchange_strong(__o_next, __n_next)){
__o_next = __n_next;//
__n_next.__m_src = new __node<_Ty>;// __n_next __data push
}// ， __m_src
__set_tail(__o_tail, __o_next);
}
}
}
template <typename _Ty>
void lk_free_que_s<_Ty>::__set_tail(__count_node_type& __o_tail, __count_node_type __next){
__node<_Ty>* __src = __o_tail.__m_src;// __src
__m_tail.compare_exchange_strong(__o_tail, __next);// ， __free_external_count
if (__o_tail.__m_src == __src)// __release_reference
__free_external_count(__o_tail);
else __src->__release_reference();
}
}