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)


相关推荐

  • 合成控制法 (Synthetic Control Method) 及 Stata实现[通俗易懂]

    合成控制法 (Synthetic Control Method) 及 Stata实现[通俗易懂]作者:何庆红(北京大学中国卫生经济研究中心)连享会:(知乎|简书|码云|CSDN) 2019暑期“实证研究方法与经典论文”专题班-连玉君-江艇主讲 本推文介绍合成控制方法及其Stata的实现命令。合成控制方法(SyntheticControlMethod)由AbadieandGardeazabal(2003)提出。目前,该方法已被广泛使用。1.背景介绍…

  • MySql必知必会内容导图

    MySql必知必会思维导图1.DBMS分类(1)关系数据库系统(2)面向对象的数据库系统(3)对象关系数据库系统对象关系数据库系统是在传统的关系数据模型基础上提供元祖,数据,集合等更为丰富

    2021年12月28日
  • 粗斜体字母_LaTeX语法

    粗斜体字母_LaTeX语法写文章的小伙伴应该知道,在文章中,变量是需要斜体的,那么怎么才是斜体呢 首先,在LATEX中,强调可以以斜体形式展现出来。那么强调命令是如何体现的呢: 语法:\emph{内容} 打开Winedit:,输入以下命令: \documentclass{article}\begin{document}Smallisbeautiful.\emph{Smallisbeautiful.}\end{document} 保存为TEX文件..

    2022年10月25日
  • 关于包围神经猫的想法实现

    关于包围神经猫的想法实现

  • Linux stat函数_linux C编程视频

    Linux stat函数_linux C编程视频linuxC函数之stat函数1.函数功能:通过文件名filename获取文件信息,并保存在buf所指的结构体stat中2.函数原型1)函数头文件#include#include2)函数intstat(constchar*file_name,structstat*buf)3)返回返回值:     执行成功则返回0,失败返回-1,错误代码存于errno错误代码:ENOENT  

  • Generic Host Process for Win32 Services 解决之道[通俗易懂]

    Generic Host Process for Win32 Services 解决之道[通俗易懂]开机有时候会出现:GenericHostProcessforWin32Services遇到了一个问题,需要关闭。出现上面这个错误一般有三种情况。1.就是病毒。开机后会提示GenericHostProcessforWin32Services遇到问题需要关闭”“RemoteRrocedureCall(RPC)服务意外终止,然后就自动重起电脑。一般该病毒会在

    2022年10月12日

发表回复

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

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