Sil*_*ler 28 c++ smart-pointers atomic c++11
通常,C++中引用计数智能ptr类的最广为人知的实现,包括标准std::shared_ptr,使用原子引用计数,但不提供对同一智能ptr实例的原子访问.换句话说,多个线程可以安全地在shared_ptr指向同一共享对象的单独实例上操作,但是多个线程不能安全地读取/写入同一shared_ptr实例的实例而不提供某种同步,例如互斥或其他.
已经提出了shared_ptr被称为" atomic_shared_ptr" 的原子版本,并且已经存在初步实现.据推测,可以使用自旋锁或互斥锁轻松实现,但也可以实现无锁实现.atomic_shared_ptr
在研究了其中一些实现后,有一件事是显而易见的:实现无锁std::shared_ptr是非常困难的,并且似乎需要这么多compare_and_exchange操作才能让我质疑简单的自旋锁是否会实现更好的性能.
实现无锁引用计数指针如此困难的主要原因是因为在读取共享控制块(或共享对象本身,如果我们讨论的是侵入式共享指针)之间总是存在竞争,并修改引用计数.
换句话说,您甚至无法安全地读取引用计数,因为您永远不知道其他某个线程何时释放了引用计数所在的内存.
因此,通常,采用各种复杂策略来创建无锁版本.这里的实现看起来像是使用双引用计数策略,其中有"本地"引用计算并发访问shared_ptr实例的线程数,然后是"共享"或"全局"引用,它们计算指向shared_ptr实例的数量到共享对象.
考虑到所有这些复杂性,我真的很惊讶地找到了Dobbs博士的文章,从2004年开始,(在C++ 11原子之前的方式)似乎无情地解决了整个问题:
http://www.drdobbs.com/atomic-reference-counting-pointers/184401888
看起来作者声称能够以某种方式:
"... [读取]指向计数器的指针,递增计数器,并以这样的方式返回指针 - 所有其他线程都不会导致错误的结果"
但我真的不明白他实际实现这一点的方式.他正在使用(非便携式)PowerPC指令(LL/SC原语lwarx和stwcx)将其关闭.
执行此操作的相关代码是他所谓的aIandF"(原子增量和提取)",他将其定义为:
addr aIandF(addr r1){
addr tmp;int c;
do{
do{
tmp = *r1;
if(!tmp)break;
c = lwarx(tmp);
}while(tmp != *r1);
}while(tmp && !stwcx(tmp,c+1));
return tmp;
};
显然,addr是指向拥有引用计数变量的共享对象的指针类型.
我的问题是:这只能与支持LL/SC操作的架构有关吗？这似乎是不可能的cmpxchg.其次,这究竟是如何运作的？我现在已经阅读过几次这段代码了,我真的不明白发生了什么.我理解LL/SC原语的作用,我对代码没有任何意义.
我可以理解的最好的是,addr r1是指针到共享对象的地址,并且也指针引用计数(我想的地址装置的引用计数变量必须的第一构件struct,其限定所述共享宾语).然后他解除引用addr(获取共享对象的实际地址).然后,他链接加载存储在地址中的值tmp,并将结果存储在中c.这是计数器值.然后他有条件地将该值递增(如果tmp已经改变则会失败)tmp.
我不明白的是这是如何工作的.共享对象的地址可能永远不会改变,LL/SC可能会成功 - 但如果另一个线程同时取消分配共享对象,这对我们有何帮助？
addr aIandF(addr r1) {
addr tmp;
int c;
do {
do {
// r1 holds the address of the address
// of the refcount
tmp = *r1; // grab the address of the refcount
if (!tmp) break; // if it's null, bail
// read current refcount
// and acquire reservation
c = lwarx(tmp);
// now we hold the reservation,
// check to see if another thread
// has changed the shared block address
} while (tmp != *r1); // if so, start over
// if the store succeeds we know we held
// the reservation throughout
} while (tmp && !stwcx(tmp, c+1));
return tmp;
};
请注意,aIandF在构造现有共享指针的副本时,特别使用它,声明副本的引用.
Dobbs博士的文章描述了释放引用的操作,首先在源共享指针对象中原子地交换共享计数器的地址,并使用函数本地的空指针; 然后原子地递减计数器; 然后测试以查看减量的结果是否为零.这个操作顺序很重要:你说,"共享对象的地址可能永远不会改变,LL/SC可能会成功 - 但如果另一个线程同时解除了共享对象的分配,这对我们有什么帮助呢？" - 但这永远不会发生,因为如果没有首先发生交换,对象将永远不会被释放,这为我们提供了一种观察地址变化的方法.
aIandF 计数器地址的测试在进入时为空.
它可以发现地址变为空,如果它发生在之前lwarx,因为它一旦有了预留就明确地测试了它.
如果递减线程中的交换发生在lwarx之后我们实际上并不关心:如果stwcxin aIandF成功,我们知道递减线程将看到新引用计数而不是破坏对象,我们可以继续知道我们声明了对它; 而如果另一个线程首先成功递减计数器,我们将失去保留,商店将失败,我们将在下一次循环迭代中检测到对象的破坏.
该算法假设一个强一致的内存模型(所有线程总是看到彼此按程序顺序读取和写入的效果) - 即使在那些支持ll/sc的现代架构中也不一定如此.
编辑:思考,该算法也显然会假定它始终是安全的,这是一次有效的内存地址读取(例如,没有MMU /保护;或者,该算法被破解):
if (!tmp) break;
// another thread could, at this point, do its swap,
// decrement *and* destroy the object tmp points to
// before we get to do anything else
c = lwarx(tmp);
// if that happened, we'll detect this fact and do nothing with c
// but ONLY if the lwarx doesn't trap
// (due to the memory tmp points to
// getting unmapped when the other thread frees the object)