并发专题----使用开源软件Amino构建并发应用程序/多线程运行时分析工具MTRAT

使用开源软件构建并发应用程序
----------------------------------

1 开源软件Amino介绍

Amino是Apache旗下的开源软件。读者可以访问http://amino-cbbs.sourceforge.net/得到其
最新版本。

Amino Java 类库将提供优化后的并发线程组件，适用于JDK6.0 及其以后的版本。

Amino Java 类库将涉及下面四个方面的内容：
1） 数据结构
该组件将提供一套免锁的集合类。因为这些数据结构采用免锁的运算法则来生成，所
以，它们将拥有基本的免锁组件的特性，如可以避免不同类型的死锁，不同类型的线程初始
化顺序等。
2） 并行模式
Amino 将为应用程序提供一个或几个大家熟知的并行计算模式。采用这些并行模式可
以使开发者起到事半功倍的效果，这些模式包括 Master-Worker、Map-reduce、Divide and
conquer, Pipeline 等，线程调度程序可以与这些模式类协同工作，提供了开发效率。
3） 并行计算中的一般功能
Amino 将为应用程序提供并行计算中常用的方法，例如：
a. String、Sequence  和Array  的处理方面。如Sort、Search、Merge、Rank、Compare、
Reverse、 Shuffle、Rotate 和Median 等
4）原子和STM（软件事务内存模型）

--------------------------------
在Amino 类库中，主要算法将使用锁无关的（Lock-Free）的数据结构。

原语Compare-and-swap（CAS）  是实现锁无关数据结构的通用原语。CAS  可以原子
地比较一个内存位置的内容及一个期望值，如果两者相同，则用一个指定值取替这个内存位
罝里的内容，并且提供结果指示这个操作是否成功。

CAS 操作过程是：当处理器要更新一个内存位置的值的时候，它首
先将目前内存位置的值与它所知道的修改前的值进行对比（要知道在多处理的时候，你要更
新的内存位置上的值有可能被其他处理更新过，而你全然不知），如果内存位置目前的值与
期望的原值相同（说明没有被其他处理更新过），那么就将新的值写入内存位置；而如果不
同（说明有其他处理在我不知情的情况下改过这的值咯），那么就什么也不做，不写入新的
值（现在最新的做法是定义内存值的版本号，根据版本号的改变来判断内存值是否被修改，
一般情况下，比较内存值的做法已经满足要求了）。CAS 的价值所在就在于它是在硬件级别
实现的，速度那是相当的快。
========================================================================================
IBM 提供的MTRAT 工具  可以收集程序的运行时信息，实时分析程序中所有可能的并行程序错误(如死锁、数据冲突)。

多线程运行时分析工具（Multi-ThreadRun-timeAnalysisTool，MTRAT）是由 IBM 开发的一个即高效又准确的动态分析工具，它可以查找出多线程程序中的潜在的数据竞争和死锁。该工具通过修改程序的字节码，来收集为了检查死锁和数据竞争的程序的运行时信息。被修改过的程序在执行的过程中，会产生一些事件，这些事件会被MTRAT 精巧设计的数据竞争检测和死锁检测算法分析。
MTRAT 把不同的技术集成到了一个单一的开发工具中，避免了用户使用的复杂性，使得MTRAT 方便使用。MTRAT 主要由以下部分组成：
-- 简单的命令行界面和Eclipse 插件。输出MTRAT 检查到的并行错误。
-- 动态的Java 字节码修改引擎。可以在Java 类文件被Java 虚拟机加载的时候，修改Java 类。
-- 程序运行时信息收集器。收集程序的动态信息，比如内存访问，线程同步，创建和结束。
-- 高效的运行时分析引擎。收集到的运行时信息会被在线分析，如果发现潜在的并行错误，将会通过界面报告给用户。

1 锁与数据冲突
synchronized & Lock

2 采用原子性操作避免数据冲突
java.util.concurrent.atomic  包中提供了原子变量的 9  种风格（ AtomicInteger； AtomicLong；
AtomicReference； AtomicBoolean；原子整型；长型；引用；及原子标记引用和戳记引用类
的数组形式；其原子地更新一对值）。

3 采用Volatile避免数据冲突
volatile 变量可以被看作是一种“程度较轻的synchronized”；
与synchronized 块相比，volatile 变量所需的编码较少，并且运行时开销也较少，但是它所能实现的功能也仅是 synchronized 的一部分.
锁提供了两种主要特性：互斥（mutualexclusion）和可见性（visibility）。互斥即一次只允许一个线程持有某个特定的锁，因此可使用该特性实现对共享数据的协调访问协议，这样，一次就只有一个线程能够使用该共享数据。可见性要更加复杂一些，它必须确保释放锁之前对共享数据做出的更改对于随后获得该锁的另一个线程是可见的——如果没有同步机制提供的这种可见性保证，线程看到的共享变量可能是修改前的值或不一致的值，这将引发许多严重问题。

Volatile 变量具有 synchronized 的可见性特性，但是不具备原子特性。这就是说线程能够自动发现volatile 变量的最新值。Volatile 变量可用于提供线程安全，但是只能应用于非常有限的一组用例：多个变量之间或者某个变量的当前值与修改后值之间没有约束。因此，单独使用 volatile 还不足以实现计数器、互斥锁或任何具有与多个变量相关的不变式
（Invariants）的类。
在有限的一些情形下可以使用 volatile 变量替代锁。要使 volatile 变量提供理想的线程安全，必须同时满足下面两个条件：
1）对变量的写操作不依赖于当前值。
2）该变量没有包含在具有其他变量的不变式中
这些条件表明，可以被写入volatile 变量的这些有效值独立于任何程序的状态，包括变量的当前状态。
第一个条件的限制使 volatile 变量不能用作线程安全计数器。虽然增量操作（x++）看上去类似一个单独操作，实际上它是一个由读取－修改－写入操作序列组成的组合操作，必须以原子方式执行，而volatile 不能提供必须的原子特性。实现正确的操作需要使x 的值在操作期间保持不变，而volatile 变量无法实现这点。

volatile 操作不会像锁一样造成阻塞，因此，在能够安全使用volatile 的情况下，volatile可以提供一些优于锁的可伸缩特性。如果读操作的次数要远远超过写操作，与锁相比，volatile变量通常能够减少同步的性能开销。
可结合使用volatile 和synchronized 实现“开销较低的读－写锁” 。

4 ThreadLocal
其实，ThreadLocal
并不是一个Thread，而是Thread 的局部变量。当使用ThreadLocal 维护变量时，ThreadLocal为每个使用该变量的线程提供独立的变量副本，所以每一个线程都可以独立地改变自己的副本，而不会影响其它线程所对应的副本。

在同步机制中，通过对象的锁机制保证同一时间只有一个线程访问变量。而ThreadLocal 则从另一个角度来解决多线程的并发访问。ThreadLocal 会为每一个线程提供一个独立的变量副本，从而隔离了多个线程对数据的访问冲突。因为每一个线程都拥有自己的变量副本，从而也就没有必要对该变量进行同步了。ThreadLocal 提供了线程安全的共享对象，在编写多线程代码时，可以把不安全的变量封装进ThreadLocal。
===================================================
使用阻塞队列的生产者-消费者模式 （线程间协作）
---------------------------------------
在实际应用中，多个线程之间不仅需要互斥机制来保证对共享数据的完整性，而且有时需要多个线程之间互相协作，按照某种既定的步骤来共同完成任务。一个典型的应用是称之为生产-消费者模型。