linux内核 lock free

linux内核 lock free//同步问题:对共享数据的访问,需要同步,互斥。在中断,抢占,多CPU,多线程环境下尤其重要。 同步分为: 阻塞同步,非阻塞同步阻塞同步有许多实现方式了:mutex,semaphore.阻塞同步使用不当就可能造成死锁,活锁,优先级反转。非阻塞同步:(现在流行三种) waitfree 很难实现,思想是本线程有限步就完成,完全不用理其余线程。 lock

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

//

同步问题:

对共享数据的访问,需要同步,互斥。

在中断,抢占,多CPU,多线程 环境下尤其重要。

 

同步分为: 阻塞同步,非阻塞同步

阻塞同步有许多实现方式了:mutex, semaphore. 阻塞同步使用不当就可能造成死锁,活锁,优先级反转。

非阻塞同步:(现在流行三种)

wait free 很难实现,思想是本线程有限步就完成,完全不用理其余线程。

lock free 确保多个线程中,总有一个线程是运行着的。在全局上看就是这个模块一直运行中。

obstruction free 线程持续运行,当发现共享数据被改,回滚。

不难得出 Obstruction-free 是 Non-blocking synchronization 中性能最差的,而 Wait-free 性能是最好的,但实现难度也是最大的,因此 Lock-free 算法开始被重视,并广泛运用于当今正在运行的程序中,比如 linux 内核。

 

linux内核中就主要是实现了lock free

一般采用原子级的 read-modify-write 原语来实现 Lock-Free 算法,根据此理论,业界在原子操作的基础上提出了著名的 CAS(Compare – And – Swap)操作来实现 Lock-Free 算法,Intel 实现了一条类似该操作的指令:cmpxchg8。

 

//原语

CAS 原语负责将某处内存地址的值(1 个字节)与一个期望值进行比较,如果相等,则将该内存地址处的值替换为新值,CAS 操作伪码描述如下:

 

清单 1. CAS 伪码

 Bool CAS(T* addr, T expected, T newValue) 

 { 

      if( *addr == expected ) 

     { 

          *addr =  newValue; 

           return true; 

     } 

     else 

           return false; 

 } 

 

在实际开发过程中,利用 CAS 进行同步,代码如下所示:

 

清单 2. CAS 实际操作

 do{ 

        备份旧数据;

        基于旧数据构造新数据;

 }while(!CAS( 内存地址,备份的旧数据,新数据 )) 

 

就是指当两者进行比较时,如果相等,则证明共享数据没有被修改,替换成新值,然后继续往下运行;如果不相等,说明共享数据已经被修改,放弃已经所做的操作,然后重新执行刚才的操作。容易看出 CAS 操作是基于共享数据不会被修改的假设,采用了类似于数据库的 commit-retry 的模式。当同步冲突出现的机会很少时,这种假设能带来较大的性能提升

 

修改前总是判断是否已经被修改过了,若无,则可完成本次修改

 

 

//内核无锁

1: double-checking lock. 即双重检测。

if( X )

{

aa;

if( X )

doit;

}

2: 原子锁。

内核中的原子锁是主要针对 整数与位操作的。  通常用内联实现,同时是实现为 汇编代码

 

3:非阻塞锁,lock free

1: spin lock,  自旋, 如果同步操作总是能在数条指令内完成,那么使用 Spin Lock 会比传统的 mutex lock 快一个数量级。

由于获得自旋锁后,是不能睡的,关中断的,所以在单核中,spin lock只是一个关中断的操作,而在多核中才是互斥的作用。

2: seq lock,  顺序锁,针对    写操作是小概率事件,而读操作是经常发生的行为。

所以写优先,即写的时候要进行互斥操作,但只与写操作互斥,而读操作则是每次读的前后都 要查看对象状态,若不同,则说明对象已被改了,要重新读,所以读操作可能会读很多次才成功。   

linux中 seq lock 的实现原理依赖于一个序列计数器。

写者获得锁后, 要进行写前,会增加计数器 +1

而读者在读数据的前后,要读取序列的值,当前后不同,则要重新读。

缺点,seq lock 不能用于指针的数据,因读写同时发生时,可能出现无效的指针。

 

3: RCU,  read-copy-update

同样针对 多读少写的情况,但是只对指针型的数据有效。即只能保护指针。

linux内核 的实现,当写者要写时,会先申请新内存,复制数据,然后在这个副本上改,最后更新原来的指针。这样整个写操作就只有一个指针赋值要互斥。

4:免锁, 单读单写的循环数组。

 

 

http://www.ibm.com/developerworks/cn/linux/l-cn-lockfree/

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/161727.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • PHP Warning: Module ‘json’ already loaded in Unknown on line 0

    PHP Warning: Module ‘json’ already loaded in Unknown on line 0

    2021年10月21日
  • 时间轮在Kafka的实践「建议收藏」

    时间轮在Kafka的实践「建议收藏」桔妹导读:时间轮是一个应用场景很广的组件,在很多高性能中间件中都有它的身影,如Netty、Quartz、Akka,当然也包括Kafka,本文主要介绍时间轮在kafka的应用和实战,从核心…

  • google域名邮箱申请 gmail域名邮箱申请(企业应用套件)指南

    google域名邮箱申请 gmail域名邮箱申请(企业应用套件)指南

  • 测试用例模板案例

    测试用例模板案例qq账号:用例编号 所属模块 用例标题 优先级 前置条件 输入数据 操作步骤 预期结果 实际结果 是否通过 测试人员 测试时间 qq_dl_001 登录 账号为六位自然数组成 高 输入账号和密码点击登录 账号:123456密码:abcd12 1:输入账号 2:输入密码 3:点击”登录” 1:账号被填充 2:密码被填充 3:登录成功,跳转主界面 1:账号被填充

  • C语言的seekg函数,C++ seekg函数用法详解[通俗易懂]

    C语言的seekg函数,C++ seekg函数用法详解[通俗易懂]很多时候用户可能会这样操作,打开一个文件,处理其中的所有数据,然后将文件倒回到开头,再次对它进行处理,但是这可能有点不同。例如,用户可能会要求程序在数据库中搜索某种类型的所有记录,当这些记录被找到时,用户又可能希望在数据库中搜索其他类型的所有记录。文件流类提供了许多不同的成员函数,可以用来在文件中移动。其中的一个方法如下:seekg(offset,place);这个输入流类的成员函数的名字se…

  • java中采用dom4j解析xml文件「建议收藏」

    java中采用dom4j解析xml文件「建议收藏」一.前言在最近的开发中用到了dom4j来解析xml文件,以前听说过来解析xml文件的几种标准方式;但是从来的没有应用过来,所以可以在google中搜索dmo4j解析xml文件的方式,学习一下dom4j解析xml的具体操作。二.代码详情dom4j是一个第三方开发组开发出的插件,所以在我们使用dom4jf的时候我们要去下载一下dom4j对应版本的jar导入在我们项目中。1…

发表回复

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

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