Skip to content

四火的唠叨

一个纯正程序员的啰嗦

Menu
  • 所有文章
  • About Me
  • 关于四火
  • 旅行映像
  • 独立游戏
  • 资源链接
Menu

杂记:Java 的无锁编程和锁优化

Posted on 08/07/201106/23/2019 by 四火

Peterson 算法(Dekker 算法的演化),这个算法设计得很巧妙,理解的核心就是搞清楚三个标志位是怎样控制两个方法对临界区的访问的:

volatile int flag1 = 0; //主观因素:flag1 表示方法 1 自身是否要求进入临界区   
volatile int flag2 = 0; //主观因素:flag2 表示方法 2 自身是否要求进入临界区   
volatile int turn = 1; //客观因素:turn 取 1 和 2 分别表示当前临界区针对方法 1 还是方法 2 开放  
  
void fun1(){   
  flag1 = 1;   
  turn = 2;   
  while( flag2==1 && turn==2 ){} //只有在方法 2 自身要求进入临界区且临界区针对方法 2 开放时,方法 1 才会阻塞   
  //Critical Section   
  ... //临界区内   
  flag1 = 0;   
}   
  
void fun2(){   
  flag2 = 1;   
  turn = 1;   
  while( flag1==1 && turn==1 ){} //只有在方法 1 自身要求进入临界区且临界区针对方法 1 开放时,方法 1 才会阻塞   
  //Critical Section   
  ... //临界区内   
  flag2 = 0;   
} 

ConcurrentHashMap,设计巧妙,用桶粒度的锁,避免了 put 和 get 中对整个 map 的锁定,尤其在 get 中,只对一个 HashEntry 做锁定操作,性能提升是显而易见的。

image
细节参见 http://www.iteye.com/topic/344876 ,有详细的讨论;而在 https://www.ibm.com/developerworks/java/library/j-jtp08223/ ,这里有关于 Java 内存模型结合 ConcurrentHashMap 的分析。

HashMap 不是线程安全的,错误的使用并发状况下可能出现 CPU100% 的状况:

/**  
* Transfers all entries from current table to newTable.  
*/   
void transfer(Entry[] newTable) {   
    Entry[] src = table;   
    int newCapacity = newTable.length;   
    for (int j = 0; j < src.length; j++) {   
        Entry e = src[j];   
        if (e != null) {   
            src[j] = null;   
            do {   
                Entry next = e.next;   
                int i = indexFor(e.hash, newCapacity);   
                e.next = newTable[i];   
                newTable[i] = e;   
                e = next;   
            } while (e != null);   
        }   
    }   
}  

问题最终就出现在 HashMap 中 transfer 方法的这个 while 循环上,这个方法在 HashMap 扩容时调用,详细分析见:

http://blog.sina.com.cn/s/blog_56146a210100owft.html

在 Lock-Free 世界里,最简单也最普遍的一个通用原语是CAS(Compare and Swap) 操作。支持并发的现代的处理器都提供了这个原语的硬件实现。CAS 原语负责比较某个内存地址处的内容与一个期望值,如果比较成功则将该内存地址处的内容替换为一个新值。这整个操作是原子的。

这里有对无锁并发编程的介绍:http://www.cnblogs.com/lucifer1982/archive/2008/04/16/1154727.html

如果站在语言层面之上,仅从设计的层面看,可以免锁的思路至少包括:

1、单线程来主导行为,多线程池化操作避开状态变量。

比如在一个 WEB 应用中,每一个 Action 都可以给相应的用户线程分配一个实例,线程之间互不干扰;但是到了业务逻辑 Service 内,避开 Service 状态变量的使用,减少了开发人员对并发编程的关注。

2、函数式编码。

函数式编码是最天然的和最高效的免锁方式,如果你对函数式编码还不了解,请参看这篇文章。

3、资源局部复制、异步处理。

总所周知对资源的争夺是造成锁的一个重要原因,在很多情况下,资源只能有一份,但是对使用资源的每个线程来说,都可以看到属于它自己的一份(这一份并非是真正的资源,很可能只是一个缓冲区,每个线程使用它自己的一个缓冲区,到一定程度时将缓冲区的数据处理到唯一资源中,这就减少了需要加锁对线程的影响),无需考虑并发地去使用。

4、不变对象。

不妨参考 ConcurrentHashMap 的实现,其中的节点是不变的。对象不变性是保证线程安全的重要方式之一。

Java 的锁操作和锁优化:

锁自旋

线程要进入阻塞状态,肯定需要调用操作系统的函数来完成从用户态进入内核态的过程,这一步通常是性能低下的。

那么在遇到锁的争用时,或许等待线程可以不那么着急进入阻塞状态,而是等一等,看看锁是不是马上就释放了,这就是锁自旋。锁自旋在多处理器上有重要价值。

当然锁自旋也带来了一些问题,比如如何判断自旋周期,如何确定自旋锁的个数,如何处理线程优先级差异等。

锁偏向

锁偏向是 JDK1.6 引入的,主要为了解决在没有竞争情况下锁的性能问题。

锁都是可重入的,在已经获得锁的情况下,该线程可以多次锁住该对象,但是每次执行这样的操作会因为 CAS(CPU 的 Compare-And-Swap 指令)操作而造成一些开销,为了减少这种开销,这个锁会偏向于第一个获得它的线程,如果在接下来的执行过程中,该锁没有被其他的线程获取,则持有偏向锁的线程将永远不需要再进行同步。

锁消除

(JDK1.6)锁削除是指虚拟机即时编译器在运行时,对一些代码上要求同步,但是被检测到不可能存在共享数据竞争的锁进行削除。

锁膨胀

(JDK1.6)和数据库中的锁升级有些相似,多个或多次调用粒度太小的锁,进行加锁解锁的消耗,反而还不如一次大粒度的锁调用来得高效,因此 JVM 可将锁的范围优化到更大的区域。

轻量级锁

(JDK1.6)轻量级锁能提升程序同步性能的依据是 “对于绝大部分的锁,在整个同步周期内都是不存在竞争的”,这是一个经验数据。轻量级锁在当前线程的栈帧中建立一个名为锁记录的空间,用于存储锁对象目前的指向和状态。如果没有竞争,轻量级锁使用 CAS 操作避免了使用互斥量的开销,但如果存在锁竞争,除了互斥量的开销外,还额外发生了 CAS 操作,因此在有竞争的情况下,轻量级锁会比传统的重量级锁更慢。

———————————————————————————————————-

2012 年 11 月 16 日:

今天看到一个 C#实现的读共享写互斥的代码:

class ReaderAndWriter
{
       private static Mutex mut = new Mutex();//用于保护读者数量的互斥信号量
        private static Mutex rw = new Mutex();//保证读者写者互斥的信号量

        static int count = 0;//读者数量
                
        private static void Reader()
        {
            mut.WaitOne();
            if (count == 0)
            {
                rw.WaitOne();
            }
            count++;
            mut.ReleaseMutex();
            
            Thread.Sleep(new Random().Next(2000));//读取耗时 1S
            Console.WriteLine("读取完毕");
            
            mut.WaitOne();
            count--;
            mut.ReleaseMutex();
            if (count == 0)
            {
                rw.ReleaseMutex();
            }

        }
        private static void writer()
        {
            rw.WaitOne();
            Console.WriteLine("写入数据");
            rw.ReleaseMutex();
    
        }
}

这种方式是写线程的逻辑比较简单的一种实现,只管获取到 rw 锁(用于表示互斥锁),而读线程在每次进行读区域前,通过 mut 锁的机制保证至少有一个互斥锁被读线程所占据(这样写线程就没法并行操作了),然后再真正开始读的时候放开 mut 锁,让其它读线程可以并发地进行读操作。其中的 count 用于表示当前读者的个数,当 count 降为 0 的时候,进入的读线程必须去获取一个写锁,以保证有读者的时候,写锁一定被某个读者占有。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

×Scan to share with WeChat

你可能也喜欢看:

  1. java.util.concurrent 并发包诸类概览
  2. Java 多线程发展简史
  3. 从 DCL 的对象安全发布谈起
  4. 动手实现随机验证码
  5. 多重继承的演变

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

订阅·联系

四火,啰嗦的程序员一枚,现居西雅图

Amazon Google Groovy Hadoop Haskell Java JavaScript LeetCode Oracle Python Spark 互联网 前端 华为 历史 同步 团队 图解笔记 基础设施 工作 工作流 工具 工程师 应用系统 异步 微博 思考 技术 数据库 曼联 测试 生活 程序员 管理 系统设计 缓存 编码 编程范型 英语 西雅图 设计 评审 问题 面试 项目

分类

  • Algorithm and Data Structure (30)
  • Concurrency and Asynchronization (6)
  • System Architecture and Design (43)
  • Distributed System (18)
  • Tools Frameworks and Libs (13)
  • Storage and Data Access (8)
  • Front-end Development (33)
  • Programming Languages and Paradigms (55)
  • Testing and Quality Assurance (4)
  • Network and Communication (6)
  • Authentication and Authorization (6)
  • Automation and Operation Excellence (13)
  • Big Data and Machine Learning (5)
  • Product Design (7)
  • Hiring and Interviews (14)
  • Project and Team Management (14)
  • Engineering Culture (17)
  • Critical Thinking (25)
  • Career Growth (57)
  • Life Experience and Thoughts (45)

推荐文章

  • 谈谈分布式锁
  • 常见分布式系统设计图解(汇总)
  • 系统设计中的快速估算技巧
  • 从链表存在环的问题说起
  • 技术面试中,什么样的问题才是好问题?
  • 从物理时钟到逻辑时钟
  • 近期面试观摩的一些思考
  • RSA 背后的算法
  • 谈谈 Ops(汇总 + 最终篇):工具和实践
  • 不要让业务牵着鼻子走
  • 倔强的程序员
  • 谈谈微信的信息流
  • 评审的艺术——谈谈现实中的代码评审
  • Blog 安全问题小记
  • 求第 K 个数的问题
  • 一些前端框架的比较(下)——Ember.js 和 React
  • 一些前端框架的比较(上)——GWT、AngularJS 和 Backbone.js
  • 工作流系统的设计
  • Spark 的性能调优
  • “残酷” 的事实
  • 七年工作,几个故事
  • 从 Java 和 JavaScript 来学习 Haskell 和 Groovy(汇总)
  • 一道随机数题目的求解
  • 层次
  • Dynamo 的实现技术和去中心化
  • 也谈谈全栈工程师
  • 多重继承的演变
  • 编程范型:工具的选择
  • GWT 初体验
  • java.util.concurrent 并发包诸类概览
  • 从 DCL 的对象安全发布谈起
  • 不同团队的困惑
  • 不适合 Hadoop 解决的问题
  • 留心那些潜在的系统设计问题
  • 再谈大楼扔鸡蛋的问题
  • 几种华丽无比的开发方式
  • 我眼中的工程师文化
  • 观点的碰撞
  • 谈谈盗版软件问题
  • 对几个软件开发传统观点的质疑和反驳
  • MVC 框架的映射和解耦
  • 编程的未来
  • DAO 的演进
  • 致那些自嘲码农的苦逼程序员
  • Java 多线程发展简史
  • 珍爱生命,远离微博
  • 网站性能优化的三重境界
  • OSCache 框架源码解析
  • “ 你不适合做程序员”
  • 画圆画方的故事

近期评论

  • + 1.943624 BTC.NEXT - https://graph.org/Ticket--58146-05-02?hs=9a9c6f8dfe3cdbe0074006e3e640b19b& on 所有文章
  • Anonymous on 闲聊投资:亲自体验和护城河
  • 四火 on 关于近期求职的近况和思考
  • YC on 关于近期求职的近况和思考
  • mafulong on 常见分布式基础设施系统设计图解(四):分布式工作流系统
  • 四火 on 常见分布式基础设施系统设计图解(八):分布式键值存储系统
  • Anonymous on 我裸辞了
  • https://umlcn.com on 资源链接
  • Anonymous on 我裸辞了
  • Dylan on 我裸辞了
© 2025 四火的唠叨 | Powered by Minimalist Blog WordPress Theme