大家好,又见面了,我是你们的朋友全栈君。
lockfree的本质是乐观锁。也就是说,它假设多数情况下,别人不会改变。一个通用的lockfree算法可描述如下:
lockfree_modify(DataT* data)
{
for (;;)
{
Save old state of data to a local variable;
do modify;
lock {
if (current state == old state)
commit modify & return;
}
}
}
可以看出,lockfree也是锁,只是将锁限制在一个最小的范围内(通常是一个原子操作)。由于仍然有锁,lockfree在多核下并不会比普通的锁高明多少,它也不能随cpu个数增加而获得呈线性scale的性能提升。
不过,lockfree有个最大的好处,就是不可能有死锁。因为对上面算法分析你可以知道,在某个线程modify失败,总意味着有另一个人成功了,整个程序总在一步步前进,而不是出现相互等待而产生饥饿的状况。
我们以stack为例,展示下lockfree的stack是怎样的:
class stack
{
public:
struct Node
{
Node* prev;
};
private:
Node* m_head;
public:
stack()
: m_head(NULL)
{
}
void push(Node* val)
{
for (;;)
{
Node* head = m_head;
val->prev = head;
if (InterlockedCompareExchangePointer((PVOID*)&m_head, val, head) == head)
return;
}
}
Node* pop()
{
for (;;)
{
Node* head = m_head;
if (head == NULL)
return NULL;
if (InterlockedCompareExchangePointer((PVOID*)&m_head, head->prev, head) == head)
return head;
}
}
};
嗯,看起来挺不错,代码还算优雅。。。不过遗憾的是,严谨的说其实上面的lockfree算法是有问题的。问题在哪里?在pop算法上。我们看lock范围内的语义:
if (InterlockedCompareExchangePointer((PVOID*)&m_head, head->prev, head) == head)
return head;
这句话用伪代码描述是:
lock {
if (m_head == head) {
m_head = head->prev;
return head;
}
}
问题在于,m_head指针的值没有发生变化,和整个stack没有发生变化,这两者等价吗?
不等价。完全可以发生一种情况就是,另一个线程执行了这样一段代码:
v1 = pop(); // v1是m_head
v2 = pop();
push(v1);
此时,m_head没有变化,但是m_head->prev不再是v2,而是v2->prev了。
那么怎么办?在说解决方案前,我们先再聊下上例中的stack::push。既然stack::pop有问题,那么stack::push呢?我们说,push算法的并没有什么问题。尽管同样的,m_head指针的值没有发生变化,并不意味着整个stack没有发生变化。但是对于push来说,它只关心m_head,而不关心其他东西,所以stack是否发生变化对其并无影响。
那么,应该如何解决pop算法遇到的问题?一个比较通用的方法,就是版本号。lockfree算法中,有一个术语叫tagged_ptr,其实本质上就是一个打了版本号的pointer:
struct tagged_ptr
{
void* p;
size_t tag;
};
每次要对p进行修改,都++tag。这样,判断是不是modify,只需要判断tag是否变化即可。
lockfree小结:
- 优点:不发生死锁。性能通常比lock好一些。
- 缺点:仍然是锁。所以并不能随cpu个数增加而获得呈线性scale的性能提升。
- 缺点:lockfree算法的实现通常比较复杂,不利于推广到任意算法的lockfree改造。通常只有少量库代码使用lockfree。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/161719.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...