死锁——锁顺序死锁
两个线程试图以不同的顺序来获得相同的锁。如果按照相同的顺序来请求锁，那么就不会出现循环的加锁依赖，因此也就不会产生死锁。
public class LeftRightDeadlock {
private final Object left = new Object();
private final Object right = new Object();
public void leftRight(){
synchronized(left){
synchronized(right){
dosomething();
}
}
}
public void rightLeft(){
synchronized(right){
synchronized(left){
dosomething();
}
}
}
}
动态的锁顺序死锁
考虑资金转账问题，将资金从一个账户转入另一个账户。在开始转账之前，首先要获得这两个Account对象的锁，以确保通过原子的方式来更新两个账户中的余额。
/**
* 事实上锁的顺序取决于传递给transferMoney的参数顺序，而这些参数又取决于外部输入。
* 这种情况下，外部调用很容易发生死锁。
*/
public void transferMoney(Account fromAccount,Account toAccount.DollarAmount amount)
throws InsufficientFundsException{
synchronized(fromAccount){
synchronized(toAccount){
if(fromAccount.getBalance().compareTo(amount) < 0){
throw new InsufficientFundsException();
}else{
fromAccount.debit(amount);
toAccount.credit(amount);
}
}
}
}
private static final Object tieLock = new Object();
/**
* 在指定锁的顺序时，可以使用System.identityHashCode。
* 在极少数情况下，两个对象可能拥有相同的散列值，此时再在外面加一层锁，
* 保证每次只有一个线程以位置的顺序获得两个锁，从而消除死锁的可能性。
*
* 如果Account中包含一个唯一的、不可变的，并且具备可比性的键值，如账号
* 那么要制定锁的顺序就更加容易了，也就不需要再另外加锁了。
*/
public void transferMoney2(final Account fromAccount,final Account toAccount,final DollarAmount amount)
throws InsufficientFundsException{
class Helper{
public void transfer() throws InsufficientFundsException{
if(fromAccount.getBalance().compareTo(amount) < 0){
throw new InsufficientFundsException();
}else{
fromAccount.debit(amount);
toAccount.credit(amount);
}
}
}
int fromHash = System.identityHashCode(fromAccount);
int toHash = System.identityHashCode(toAccount);
if(fromHash < toHash){
synchronized(fromAccount){
synchronized(toAccount){
new Helper().transfer();
}
}
}else if(fromHash > toHash){
synchronized(toAccount){
synchronized(fromAccount){
new Helper().transfer();
}
}
}else{
synchronized(tieLock){
synchronized(fromAccount){
synchronized(toAccount){
new Helper().transfer();
}
}
}
}
}
如果在持有锁的情况下调用某个外部方法，那么就需要警惕死锁。
/**
* 尽管没有任何方法会显示地获取两个锁，但setLocation和getImage等方法的调用都会获得两个锁。
* 如果一个线程收到GPS接收器的更新事件时调用setLocation，那么它将首先更新出租车的位置，
* 然后判断它是否到达了目的地。如果已经到达，它会通知Dispatcher：它需要一个新的目的地。
* setLocation与norifyAvailable将先后获得Taxi和Dispatcher的锁
* 而getImage与getLocation将先后获得Dispatcher与Taxi的锁。
* 因此就可能产生死锁。
*/
class Taxi{
private Point location;
private Point destination;
private final Dispatcher dispather;
public Taxi(Dispatcher dispather){
this.dispather = dispather;
}
public synchronized Point getLocation(){
return location;
}
public synchronized void setLocation(Point destination){
this.location = location;
if(location.equals(destination)){
dispather.norifyAvailable(this);
}
}
}
class Dispatcher{
private final Set<Taxi> taxis;
private final Set<Taxi> availableTaxis;
public Dispatcher(){
taxis = new HashSet<Taxi>();
availableTaxis = new HashSet<Taxi>();
}
public synchronized void norifyAvailable(Taxi taxi){
availableTaxis.add(taxi);
}
public synchronized Image getImage(){
Image image = new Image();
for(Taxi t : taxis){
image.drawMarker(t.getLocation());
}
return image;
}
}
如果在调用某个方法时不需要持有锁，那么这种调用称为开发调用。
/**
* 将Taxi与Dispatcher修改为开放调用，从而消除发生死锁的风险。
* 使用同步代码块仅保护哪些设计共享状态的操作。在同步操作中不会去获得另外的锁。
*/
class Taxi1{
private Point location;
private Point destination;
private final Dispatcher1 dispather;
public synchronized Point getLocation(){
return location;
}
public void setLocation(Point location){
boolean reachedDestination;
synchronized(this){
this.location = location;
reachedDestination = location.equals(destination);
}
if(reachedDestination){
dispather.norifyAvailable(this);
}
}
}
class Dispatcher1{
private final Set<Taxi1> taxis;
private final Set<Taxi1> availableTaxis;
public synchronized void norifyAvailable(Taxi1 taxi){
availableTaxis.add(taxi);
}
public Image getImage(){
Set<Taxi1> copy;
synchronized(this){
copy = new HashSet<Taxi1>(taxis);
}
Image image = new Image();
for(Taxi1 t : copy){
image.drawMarker(t.getLocation());
}
return image;
}
}
活锁
线程不会阻塞，而是不断重复尝试相同的操作，但总是失败。
当多个相互协作的线程都对彼此进行响应从而修改各自的状态，并使得任何一个线程都无法继续执行时，就发生了活锁。
就像两个过于礼貌的人在半路上面对面地相遇，彼此为对方让路，然而又再次相遇，就这样反复的避让下去。
线程引入的开销
上下文切换
切换上下文需要一定的开销，而在线程调度过程中需要访问由操作系统和JVM共享的数据结构。应用程序、操作系统以及JVM都使用一组相同的CPU。在JVM和操作系统地代码中消耗越多的CPU时钟周期，应用程序的可用CPU时钟周期就越少。但上下文切换的开销并不是只包含JVM和操作系统地开销。当一个新的线程被切换进来时，它所需要的数据可能不在当前处理器的本地缓存中，因此上下文切换将导致一些缓存缺失。因而线程在首次调度运行时会更加缓慢。这就是为什么调度器会为每个可运行的线程分配一个最小执行时间，即使有许多其他的线程正在等待执行。它将上下文切换的开销反弹到更多不会中断的执行时间上，以损失响应性为代价而提高整体的吞吐量。
unix的vmstat命令和windows的perfmon工具都能报告上下文切换次数以及在内核中执行时间所占比例等信息。如果内核占用率超过10%,那么通常表示调度活动发生得很频繁，这可能使由I/O或竞争锁导致的阻塞引起的。
内存同步
同步操作的性能开销包括多个方面。在synchronized和volatitle提供的可见性保证中可能会使用一些特殊命令，即内存栅栏。内存栅栏可以刷新缓存，使缓存无效，刷新硬件的写缓冲，以及停止执行管道。内存栅栏可能同样会对性能带来间接的影响，因为它们将抑制一些编译器优化操作。在内存栅栏中，大多数操作都是不能重排序的。
减少锁的竞争
1.缩小锁的范围，即减少锁的持有时间
尽管缩小同步代码块能提高可伸缩性，但同步代码块也不能过小，当把一个同步代码块分解为多个同步代码块时反而会对性能产生负面影响
事实上，如果JVM执行锁粗化操作，那么可能会将分解的同步块又重新合并起来。
2.减小锁的粒度
为了降低线程请求锁的频率，可以通过锁分解技术来实现。
即采用多个相互独立的锁来保护独立的状态变量，从而改变这些变量之前由单个锁保护的情况，也就降低的锁的竞争。
3.锁分段
把一个竞争激烈的锁分解为两个锁时，这两个锁可能都存在着激烈的竞争。虽然采用两个线程并发执行能提高一部分可伸缩性，但在一个拥有多处理器的系统中，仍然无法给可伸缩性带来极大的提高。在某些情况下，可以将锁分解技术进一步扩展为对一组独立对象上的锁进行分解，这种情况称为锁分段。
例如，在ConcurrentHashMap的实现中默认使用了一个包含16个锁的数组，每个锁保护所有散列桶的1/16。
使得ConcurrentHashMap能够支持多达16个并发的写入器。
锁分段的劣势在于：与采用单个锁来实现独占访问相比，要获得多个锁来实现独占访问将更加困难并且开销更高。通常，在执行一个操作时最多只需获取一个锁，但在某些情况下需要加锁整个容器。
例如当ConcurrentHashMap需要扩展映射范围，以及重新计算键值的三列值要分布到更大的桶集合中时，就需要获取分段锁集合中所有的锁。
/**
* StripedMap中给出了基于散列的Map实现，其中使用了锁分段技术。
* 它拥有N_LOCKS个锁，并且每个锁保护散列桶的一个子集。
* 例如get都只需要获得一个锁，而有些方法则需要获得所有的锁，但并不要求同时获得，例如clear
*/
public class StripedMap {
private static final int N_LOCKS = 16;
private final Node[] buckets;
private final Object[] locks;
private static class Node{
}
public StripedMap(int numBuckets){
buckets = new Node[numBuckets];
locks = new Object[N_LOCKS];
for(int i = 0;i < N_LOCKS; i++){
locks[i] = new Object();
}
}
private final int hash(Object key){
return Math.abs(key.hashCode() % buckets.length);
}
public Object get(Object key){
int hash = hash(key);
synchronized(locks[hash % N_LOCKS]){
for(Node m = buckets[hash]; m != null; m = m.next()){
if(m.key.equals(key)){
return m.value;
}
}
}
return null;
}
public void clear(){
for(int i = 0; i < buckets.length; i++){
synchronized(locks[i % N_LOCKS]){
buckets[i] = null;
}
}
}
}
这种清除map的方式并不是原子操作，因此可能当StripedMap为空时其他的线程正在并发地向其中添加元素。如果要使该操作成为一个原子操作，那么需要同时获得所有的锁。然而，如果客户代码不加锁并发容器来实现独占访问，那么像size或isEmpty这样的方法的计算结果在返回时可能会变得无效，因此，尽管这种行为有些奇怪，但通常是可以接受的。
当每个操作都请求多个变量时，锁的粒度将很难降低。
当实现HashMap时，需要考虑如何在size方法中计算Map中的元素数量。最简单的方法就是，在每次调用时都统计一次元素的数量。一种常见的优化措施是，在插入和移除元素时更新一个计数器，虽然这在put和remove等方法中略微增加了一些开销，以确保计数器是最新的值，但这将把size方法的开销从O(n)降低到O(1)。
但是对计数器的访问需要进行同步，这又会重新到在使用独占锁时存在的问题。
为了避免这个问题，ConcurrentHashMap中的size将对每个分段进行枚举并将每个分段中的元素数量相加，而不是维护一个全局计数。为了避免枚举每个元素，ConcurrentHashMap为每个分段都维护了一个独立的计数，并通过每个分段的锁来维护这个值。
#笔记内容来自 《java并发编程实战》