lockfree的本質(zhì)是樂(lè)觀鎖。也就是說(shuō)，它假設(shè)多數(shù)情況下，別人不會(huì)改變。一個(gè)通用的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也是鎖，只是將鎖限制在一個(gè)最小的范圍內(nèi)（通常是一個(gè)原子操作）。由于仍然有鎖，lockfree在多核下并不會(huì)比普通的鎖高明多少，它也不能隨cpu個(gè)數(shù)增加而獲得呈線(xiàn)性scale的性能提升。
?
不過(guò)，lockfree有個(gè)最大的好處，就是不可能有死鎖。因?yàn)閷?duì)上面算法分析你可以知道，在某個(gè)線(xiàn)程modify失敗，總意味著有另一個(gè)人成功了，整個(gè)程序總在一步步前進(jìn)，而不是出現(xiàn)相互等待而產(chǎn)生饑餓的狀況。
?
我們以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;
?? }
?}
};
?
嗯，看起來(lái)挺不錯(cuò)，代碼還算優(yōu)雅。。。不過(guò)遺憾的是，嚴(yán)謹(jǐn)?shù)恼f(shuō)其實(shí)上面的lockfree算法是有問(wèn)題的。問(wèn)題在哪里？在pop算法上。我們看lock范圍內(nèi)的語(yǔ)義：
?
???? if (InterlockedCompareExchangePointer((PVOID*)&m_head, head->prev, head) == head)
???????? return head;
?
這句話(huà)用偽代碼描述是：
?
???? lock {
???????? if (m_head == head) {
????????????? m_head = head->prev;
????????????? return head;
???????? }
???? }
?
問(wèn)題在于，m_head指針的值沒(méi)有發(fā)生變化，和整個(gè)stack沒(méi)有發(fā)生變化，這兩者等價(jià)嗎？
?
不等價(jià)。完全可以發(fā)生一種情況就是，另一個(gè)線(xiàn)程執(zhí)行了這樣一段代碼：
?
??? v1 = pop();? // v1是m_head
??? v2 = pop();
??? push(v1);
?
此時(shí)，m_head沒(méi)有變化，但是m_head->prev不再是v2，而是v2->prev了。
?
那么怎么辦？在說(shuō)解決方案前，我們先再聊下上例中的stack::push。既然stack::pop有問(wèn)題，那么stack::push呢？我們說(shuō)，push算法的并沒(méi)有什么問(wèn)題。盡管同樣的，m_head指針的值沒(méi)有發(fā)生變化，并不意味著整個(gè)stack沒(méi)有發(fā)生變化。但是對(duì)于push來(lái)說(shuō)，它只關(guān)心m_head，而不關(guān)心其他東西，所以stack是否發(fā)生變化對(duì)其并無(wú)影響。
?
那么，應(yīng)該如何解決pop算法遇到的問(wèn)題？一個(gè)比較通用的方法，就是版本號(hào)。lockfree算法中，有一個(gè)術(shù)語(yǔ)叫tagged_ptr，其實(shí)本質(zhì)上就是一個(gè)打了版本號(hào)的pointer：
?
??? struct tagged_ptr
??? {
??????? void* p;
??????? size_t tag;
??? };
?
每次要對(duì)p進(jìn)行修改，都++tag。這樣，判斷是不是modify，只需要判斷tag是否變化即可。
?
lockfree小結(jié)：

• 優(yōu)點(diǎn)：不發(fā)生死鎖。性能通常比lock好一些。
• 缺點(diǎn)：仍然是鎖。所以并不能隨cpu個(gè)數(shù)增加而獲得呈線(xiàn)性scale的性能提升。
• 缺點(diǎn)：lockfree算法的實(shí)現(xiàn)通常比較復(fù)雜，不利于推廣到任意算法的lockfree改造。通常只有少量庫(kù)代碼使用lockfree。

轉(zhuǎn)載于:https://www.cnblogs.com/wuwuwu/archive/2009/05/02/6162381.html

總結(jié)

以上是生活随笔為你收集整理的关于 lockfree 算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。