`
- 浏览:
244278 次
- 性别:
- 来自:
LA
-
算法描述
Lock-free 算法的基础是 CAS (Compareand-Swap) 原子操作。当某个地址的原始值等于某个比较值时,把值改成新值,无论有否修改,返回这个地址的原始值。目前的cpu 支持最多64位的CAS。并且指针 p 必须对齐。
注:原子操作指一个cpu时钟周期内就可以完成的操作,不会被其他线程干扰。
一般的 CAS 使用方式是:
假设有指针 p, 它指向一个 32 位或者64位数,
复制p 的内容(*p)到比较量 cmp (原子操作)
基于这个比较量计算一个新值 xchg (非原子操作)
调用 CAS 比较当前 *p 和 cmp, 如果相等把 *p 替换成 xchg (原子操作)
如果成功退出,否则回到第一步重新进行
第3步的 CAS 操作保证了写入的同时 p 没有被其他线程更改。如果*p已经被其他线程更改,那么第2步计算新值所使用的值(cmp)已经过期了,因此这个整个过程失败,重新来过。多线程环境下,由于 3 是一个原子操作,那么起码有一个线程(最快执行到3)的CAS 操作可以成功,这样整体上看,就保证了所有的线程上在“前进”,而不需要使用效率低下的锁来协调线程,更不会导致死锁之类的麻烦。
ABA 问题
当 A 线程执行2的时候,被B 线程更改了 *p为x, 而 C 线程又把它改回了原始值,这时回到A 线程,A线程无法监测到原始值已经被更改过了,CAS 操作会成功(实际上应该失败)。ABA 大部分情况下会造成一些问题,因为 p 的内容一般不可能是独立的,其他内容已经更改,而A线程认为它没有更改就会带来不可预知的结果。
ABA 问题的解决一般是扩展 *p 的位数(比如从32扩展到64),使用多余的位来保存一个版本号,每次更改都修改版本号,从而保证这个线程能正确的监测到值的更改。
扩展
一个 32 位数无法携带太多信息,但是32位的C++ 环境中,这样的一个数已经可以代表很多东西了,比如——指针。
我们刚才保证了我们的线程可以安全读写一个 32 位的数,如果这个数是一个指针,指向了我们真实使用的对象。那么我们就可以创建了一个无锁而线程安全的对象。基本思想就是每次修改对象前,复制整个对象,然后更改完成以后用上面的算法使用新对象来替换旧对象(更改p的指向),当然,这个对象不能太大,否则lock-free的速度优势,就被复制操作消耗殆尽。
这里有个很大的问题,在于老的对象何时销毁。P 指向新的对象了,以后的操作都将会访问新的对象,但是老的对象还可能正被其他线程访问中。遗憾的是,我们还没有垃圾收集器,所以需要设计一个引用计数之类的策略来保护这个对象。
分享到:
Global site tag (gtag.js) - Google Analytics
相关推荐
在IT行业中,"LockFree"是一种并发编程技术,它的核心思想是避免在多线程环境下使用锁来同步对共享资源的访问。LockFree技术在C# .NET框架中也有广泛的应用,可以显著提高多线程环境下的程序性能,降低死锁和竞态...
无锁队列(Lockfree Queue)是一种在多线程编程中用于实现高效并发的数据结构,它的设计目标是提高系统的并行性能,同时避免了锁的使用,从而减少了因线程竞争导致的性能瓶颈。在标题中提到的"lockfree queue"就是指...
### Lock Free技术详解 #### 一、背景与概念 随着多核处理器的普及和技术的发展,多线程编程已经成为提升程序性能的重要手段之一。在多线程环境中,如何有效地管理资源和保证数据一致性变得尤为重要。传统的锁机制...
"lockfree-shm-ipc.sln"和"lockfree-shm-ipc.vcproj"是Visual Studio的项目文件,表明这个库可能是在Windows平台上开发的,并且可以使用Visual Studio进行编译和调试。"version"文件可能包含了项目的版本信息,"bin...
LockFreeList,正如其名,是一种无锁的列表实现,它避免了传统锁机制带来的性能瓶颈和死锁风险。本文将深入探讨LockFreeList的概念、原理以及在Java中的实现。 首先,我们需要理解什么是无锁编程。无锁编程是一种...
skip lists,binary search trees, and red-black trees
无锁编程(Lock-free Programming)是一种并发控制技术,它通过避免使用锁来实现线程间的同步,从而提高多核处理器系统中的性能。在标题提到的"Lock free 论文集合"中,我们可以期待找到一系列关于无锁数据结构设计...
这个压缩包“LockFree论文集合,若干无锁数据结构实现的经典论文,500多页.zip”包含了一系列关于无锁数据结构实现的论文,对于深入理解并发编程的高级概念和技术具有重要价值。 无锁编程的核心思想是通过原子操作...
lockfree-object-pool = " 0.1 " extern crate lockfree_object_pool; 例子 一般的池创建看起来像这样 let pool = LinearObjectPool :: < u32> :: new ( || Default :: default (), | v | { * v = 0 ; }); 并...
无锁队列的C实现方法;作为备份;希望对别人有帮助
标题中的"lockfree-list"指的是无锁(Lock-Free)数据结构中的无锁链表,这是一种在多线程环境下实现高效并发访问的数据结构。无锁数据结构利用原子操作避免了锁的使用,从而减少了线程之间的竞争条件,提升了系统的...
上述技术可用于实现完全无锁的基于数组的队列: lockfree queue primitivestypedef struct _queue_t *queue_t;queue_t queue_create(size_t);void *queue_dequeue(queue_t);int queue_enqueue(queue_t, void *);...
【自扩充的Lock-Free并发环形队列算法】 在并发编程中,环形队列是一种常用的结构,尤其在多线程环境和实时系统中。它允许高效的数据传递,因为其首尾指针间的循环特性避免了数组类型的越界问题。然而,固定大小的...
rs-lockfree Concurrently R/W Shared Object是高性能并发程序中最频繁的操作之一。 有多种方法可以实现它,例如R/W Lock , Reference Counting , Hazard Pointers , Epoch Based Reclamation , Quiescent ...
这是对malloc / free的直接替代,它是从头开始设计用于可伸缩服务器软件的。 为什么要使用另一个内存分配器? 这是分配器的优点: 它是线程友好的。 它支持几乎无限数量的并发线程,而不会导致锁定或性能下降。 ...
无锁无锁并发数据结构用法使用 crates.io 存储库; 将其与其余依赖Cargo.toml一起添加到Cargo.toml : [ dependencies ]lockfree = " * "作者是 lockfree 的主要作者和维护者。执照麻省理工学院
本资源集合"awesome-lockfree"专注于这一领域的知识和工具,旨在帮助开发者理解和实践这类技术。 无锁编程是指在多线程环境下,通过避免使用传统的锁机制来实现共享数据的并发访问。它通过原子操作(Atomic ...