关于 lockfree 算法[通俗易懂]

关于 lockfree 算法[通俗易懂]lockfree的本质是乐观锁。也就是说,它假设多数情况下,别人不会改变。一个通用的lockfree算法可描述如下: lockfree_modify(DataT*data){   for(;;)   {       Saveoldstateofdatatoalocalvariable;       domodify;       lock{           

大家好,又见面了,我是你们的朋友全栈君。

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账号...

(0)


相关推荐

  • Android studio编译很久 Gradle Build Running特别慢问题解决

    Android studio编译很久 Gradle Build Running特别慢问题解决

  • mysql添加索引造成的影响

    mysql添加索引造成的影响尽管添加索引可以优化SQL语句的性能,但是添加索引的同时也会带来不小的开销。尤其是在有大量的索引的情况下。mysql添加索引造成的影响如下:1、DML(数据操作语言)影响,在表上添加缩影会直接影响写操作性能(因为添加记录的同时还有创建相应记录的索引,这也是要耗资源的。)。2、DDL(数据定义语言)影响,随着表大小的不断增加,对性能的影响也会不断增加。比如:ALTER语句会耗费更多的时间…

  • 世界名着100部简介

    世界名着100部简介01、傲慢与偏见      02、孤星血泪      03、雾都孤儿        04、唐·吉诃德  05、安娜·卡列尼娜      06、飘      07、简·爱       08、悲惨世界  09、茶花女      10、基督山恩仇记      11、童年         12、这里的黎明静悄悄  13、钢铁是怎样炼成的

  • pyside2界面美化_手机音量进度条 插件

    pyside2界面美化_手机音量进度条 插件前言在我们进行自动化测试的时候,用例往往是成百上千,执行的时间是几十分钟或者是小时级别。有时,我们在调试那么多用例的时候,不知道执行到什么程度了,而pytest-sugar插件能很好解决我们的痛点。

  • 安装 Prophet

    安装 Prophet本安装文档主要翻译整理自ProphetInstallation官方安装文档。在R上安装Prophet一、Windows系统安装Prophet前的准备工作如果是Windows系统,需要按照rstan提供的教程给R安装一个编译器。其中,最为关键的一步就是先安装Rtools。1.安装R和RStudio2.安装Rtools,确保其安装…

  • php调用第三方api接口_uniapp ios原生插件开发

    php调用第三方api接口_uniapp ios原生插件开发1)flyio是什么?2)flyio能干什么?3)flyio使用

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号