Page 47 - 《软件学报》2021年第12期
P. 47

张杨  等:基于下推自动机的细粒度锁自动重构方法                                                         3711


             锁是并发程序中用于保护程序状态和数据访问正确性的必备措施,然而锁竞争问题是目前多核/众核时代
         影响并发程序性能的主要问题之一.锁竞争是指当临界区被一个互斥锁保护时,如果一个线程获得了该锁,那么
         其他请求访问该临界区的线程都将被阻塞,直到持有该锁的线程释放该锁.锁竞争问题的存在,会严重降低程序
         并行度,损害程序的可伸缩性,降低多核/众核处理器的执行效率.
             不恰当的并发控制方式通常会进一步加剧锁竞争,程序开发人员有时习惯于使用粗粒度锁,例如在方法的
         修饰符中加入 synchronized 关键字,使整个方法处于锁的保护之中.这种加锁方式虽然可以降低程序开发的复
         杂性,然而由于粗粒度锁控制的临界区代码较长,导致其他想获取该锁的线程等待时间增加,往往会加剧锁竞
         争.许多开发人员尝试使用细粒度锁,相比于粗粒度锁,细粒度锁只对一小部分代码进行加锁,可以有效减少锁
         的持有时间和线程等待时间,减少锁竞争问题的影响.
             与粗粒度锁比较,使用细粒度锁并非一件容易的事.要想实现细粒度的加锁方式,通常可以采用升级锁、降
         级锁、优化读锁等加锁方式,也可以采用将粗粒度读写锁分解为细粒度读写锁的方式.程序开发人员不仅需要
         对代码模式进行分析以确定使用何种细粒度锁的加锁方式,而且还需要在同一种方式的不同实现机制之间进
         行选择,例如在 JDK 中,读写锁和邮戳锁分别提供了降级锁,这两种锁提供的降级锁的实现方法截然不同,程序
         开发人员需要在两种锁机制之间进行选择,增加了细粒度锁的使用难度.在传统的方法中,为了使用细粒度锁,
         开发人员通常需要手工地对并发程序中使用粗粒度锁的代码进行重构.然而这种重构方式既费时费力,还可能
         会给代码引入新的错误,因此迫切需要对面向细粒度锁的重构方法进行研究.
                                              [1]
             目前,针对锁重构的研究有很多:Tao 等人 提出了针对 Java 程序根据类属性域划分锁保护域的自动锁分
                          [2]
                                                                                [3]
         解重构方法;Yu 等人 在进行优化同步瓶颈的研究中提出了一种锁分解方式;Emmi 等人 提出了一种自动锁
                                                                          [4]
         分配技术,推断获取锁的位置并确保加锁的正确性,避免发生死锁;Kawachiya 等人 提出一种锁保留算法,该算
         法允许锁被线程保留;Schafer 等人          [5] 针对重入锁及读写锁提出了一种自动重构算法,并实现了重构工具
                                                                           [8]
                                                   [7]
                                          [6]
         Relocker; Zhang 等人提出了面向可定制锁 和邮戳锁 的自动重构方法;Arbel 等人 提出了并发数据结构的代
                                                                                         [9]
         码转换,他们的转换采用基于锁的代码,并用乐观同步替换其中的一些加锁代码以减少争用;Bavarsad 针对软
         件事务性内存,提出了一种读写锁分配技术来克服全局时钟的开销.在工业界,集成在 IntelliJ IDEA 上的重构插
         件 LockSmith [10] 和基于 Eclipse JDT 的并发重构插件  [11] 都可以实现锁重构.从目前国内外的研究现状来看,许多
         学者已经认识到锁竞争问题以及并发控制方式在程序设计中的重要性,并对锁粒度问题以及锁机制相关的问
         题进行了研究.但大部分研究是对锁进行消除和对同步锁进行分解,对细粒度锁的重构方法还有待深入研究.
             要想实现面向细粒度锁的自动重构,需要解决以下几个问题:(1)  代码分析时需要对临界区中的每一条语
                                         [5]
         句进行读写操作分析,而不能像 Relocker 工具那样将整个临界区代码作为一个整体进行分析;(2)  在获取读写
         模式分析后,需要研究如何对读写操作模式进行识别,进而推断出使用哪一种细粒度锁;(3)  需要研究如何构建
         由粗粒度锁到细粒度锁的重构代码.
             为了解决上述问题,本文提出基于下推自动机的细粒度锁自动重构方法,通过访问者模式分析、别名分析、
         锁集分析、负面效应分析等程序分析方法获取临界区代码的读写模式,然后使用下推自动机构建不同锁模式的
         识别方法,根据识别结果进行代码重构.基于此方法,在 Eclipse JDT 框架下,以插件的形式实现了一个自动重构
         工具 FLock.在实验中,从重构个数、改变的代码行数、重构时间、准确性和重构后程序性能等方面对 FLock
                                                   [7]
                                         [5]
         进行了评估,并与已有重构工具 Relocker 和 CLOCK 进行了对比,对 HSQLDB,Jenkins 和 Cassandra 等 11 个大
         型实际应用程序的重构结果表明:FLock 共重构了 1 757 个内置监视器对象,每个程序重构平均用时 17.5s.该重
         构工具可以有效实现粗粒度锁到细粒度锁的转换,与手动重构相比,有效提升了细粒度锁的重构效率.
             本文的主要贡献有 3 个方面.
             1)   提出了一种面向细粒度锁的自动重构方法;
             2)   以 Eclipse 插件的形式实现了自动重构工具 FLock,可以实现源码级别的重构,帮助开发者完成从粗粒
                 度锁到细粒度读写锁的自动转换;
             3)   使用 11 个大型实际应用程序对 FLock 进行了评估,并与现有工具 Relocker 和 CLOCK 进行了对比.
   42   43   44   45   46   47   48   49   50   51   52