Java Concurrent Programming (2)

2 线程死锁
  死锁（dead lock）是指两个或多个线程都有权限访问两个或多个对象，并且每个线程都在已经获得某个对象锁的情况下等待其它线程已经得到的锁。假设线程A持有对象X的锁，并且正在试图获得对象Y的锁，同时，线程B已经拥有对象Y的锁，并在试图获得对象X的锁。此时因为线程互相等待释放锁而彼此都无法继续操作，死锁就产生了。以下是个死锁的例子：

public class Dummy {
	//
	private long value;
	
	public Dummy(long value){
		this.value = value;
	}
	
	public synchronized long getValue(){
		return this.value;
	}
	
	public synchronized void setValue(long value){
		this.value = value;
	}
	
	public synchronized void swap(Dummy other){
		long t = this.getValue();
		long v = other.getValue();
		this.setValue(v);
		other.setValue(t);
	}
	
	public static void main(String[] args) throws Exception{
		
		final Dummy d1 = new Dummy(100);
		final Dummy d2 = new Dummy(200);
		
		Thread t1 = new Thread(){
			public void run(){
				long count = 0;
				try {
					while(true){
						d1.swap(d2);
						count++;
						if(count % 100 == 0){
							System.out.println("current thread " + Thread.currentThread().getName() + " process " + count);
						}
					}
				} catch (Exception e) {
					e.printStackTrace();
				}
			}
		};
		t1.setName("thread1");
		
		Thread t2 = new Thread(){
			public void run(){
				long count = 0;
				try {
					while(true){
						d2.swap(d1);
						count++;
						if(count % 100 == 0){
							System.out.println("current thread " + Thread.currentThread().getName() + " process " + count);
						}
					}
				} catch (Exception e) {
					e.printStackTrace();
				}
			}
		};
		t2.setName("thread2");
		
		//
		t1.start();
		t2.start();
		
		// wait thread to die
		t1.join();
		t2.join();
	}
}

  以上程序按照下面的时序执行，就会产生死锁：

线程A	线程B
进入d1.swap(d2)时获得d1的锁
在执行t = this.getValue()时，顺利获得d1的锁（因为已经持有）	进入d2.swap(d1)时获得d2的锁
执行v = other.getValue()时，由于需要d2的锁而处于等待的状态	在执行t = this.getValue()时，顺利获得d2的锁
	执行v = other.getValue()时，由于需要d1的锁而处于等待状态

  上面程序，执行一段时间后，就会发生死锁。
  为了避免死锁的发生，在一个被同步的区域内，不要调用一个可被改写的共有的或受保护的方法。
  另外一种比较简单的避免死锁的独占技术是顺序化资源。它的思想就是把一个嵌套的synchronized方法或块中使用的对象和一个数字标签关联起来。如果同步操作是根据对象标签的最小优先（least first）的原则，那么刚才介绍的例子的情况就不会发生。也就是说，如果线程A和线程B都按照相同的顺序获得锁，就可以避免死锁的发生。对于数字标签的选择，可以使用System.identityHashCode的返回值，尽管没有什么机制可以保证identityHashCode的惟一性，但是在实际运行的系统中，这个方法的惟一性在很大程度上得到了保证。swap的一个更好的实现如下：

public void swap(Dummy other) {
    if(this == other) return; // Alias check
    else if(System.identityHashCode(this){
        this.doSwap(other);
    } else {
        other.doSwap(this);
    }
}

private synchronized void doSwap(Dummy Other) {
    long t = getValue();
    long v = other.getValue();
    setValue(v);
    other.setValue(t);
}

2.1 生产者和消费者
  生产者与消费者模型中，要保证以下几点：
   1) 同一时间内只能有一个生产者生产
   2) 同一时间内只能有一个消费者消费
   3) 生产者生产的同时消费者不能消费
   4) 消息队列满时生产者不能继续生产
   5) 消息队列空时消费者不能继续消费
以下是一个经典的生产者消费者例子：

class Producer implements Runnable{
	//
	private Message msg = null;
	
	public Producer(Message msg){
		this.msg = msg;
	}
	
	public void run(){
		for (int x = 0; x < 100; x++) {
			this.msg.set("message " + x);
		}
	}
}

class Consumer implements Runnable{
	//
	private Message msg = null;
	
	public Consumer(Message msg){
		this.msg = msg;
	}
	
	public void run(){
		for (int x = 0; x < 100; x++) {
			this.msg.get();
		}
	}
}

class Message {
	//
	private String message = "unknow";

	private boolean flag = false; // if false get, true set

	public synchronized void get() {
		if (flag == true) {
			try {
				wait();
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
		}
		System.out.println("message is " + this.message);
		flag = true;
		notify();
	}

	public synchronized void set(String message) {
		if (flag == false) {
			try {
				wait();
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
		}
		this.message = message;
		flag = false;
		notify();
	}
}

public class Test {
	
	public static void main(String[] args) {
		Message msg = new Message();
		Producer p = new Producer(msg);
		Consumer c = new Consumer(msg);
		
		new Thread(p).start();
		new Thread(c).start();
	}
}

2.2 synchronized关键字与volatile关键字
  把代码块声明为 synchronized，通常是指该代码具有原子性（atomicity）和可见性（visibility）。原子性，即锁的互斥性，意味着一个线程一次只能执行由一个指定监控对象（lock）保护的代码，从而防止多个线程在更新共享状态时相互冲突。可见性指某一线程对变量所做的更新，当进入由同一监控器（lock）保护的另一个 synchronized 块时，将立刻可以看到这些对变量所做的更新。
  volatile 变量具有 synchronized 的可见性特性，但是不具备原子特性。这就是说线程能够自动发现 volatile 变量的最新值。volatile变量可以被看作是一种“轻量级的synchronized“，与synchronized块相比，volatile所需的编码较少，并且运行时的开销也小，但是其所能实现的功能仅是synchronized的一部分。volatile变量可用于提供线程安全,但是必须同时满足下面两个条件：
  1)对变量的写操作不依赖于当前值。
  2)该变量没有包含在具有其他变量的不变式中。
然而，大多数编程情形都会与这两个条件的其中之一冲突，使得 volatile 变量不能像 synchronized 那样普遍适用于实现线程安全。

2.3 Java内存模型
  Java Memory Model分为主内存(main memory)和工作内存(working memory)。Java中所有变量都保存在主内存中，供所有线程共享。每个线程都有自己的工作内存，工作内存中保存的是主内存中某些变量的拷贝。线程对所有变量的操作都是在工作内存中进行，线程之间无法相互直接访问，变量传递均需要通过主存完成。内存模型有两个特征：
  1)可见性
  2)有序性
  在JMM中，可见性：通过并发线程修改变量值, 必须将线程变量同步回主存后, 其他线程才能访问到.
  在JMM中，有序性：通过Java提供的同步机制或volatile关键字, 来保证内存的访问顺序.
  对synchronized:
当线程要进入synchronized时，如果工作存储器在有未映像到主存储器的工作拷贝，该内容就会被强制写入主存储器，因此之前的计算结果就会被全部的写入主存储器内，成为其他线程可以看得见(visible)的状态。当线程欲退出synchronized时，会执行相同与进入synchronized时强制写入主内存储器的处理。
  对volatile：
  当线程欲引用volatile字段的值时，通常都会发生从主存储器到工作存储器的拷贝操作，而相反，将值指定给写着volatile的字段后，工作存储器的内容通常便会映像到主存储器。