多线程[公平]

在java中，进入同步块synchronized和调用对象的notifyAll()方法是没有顺序保证的，因此就存在线程饥饿的风险，即有的线程永远处于等待同步进入同步块或者等待被唤醒的状态。
可以看一个例子：

//1.0
public class Say{
    //打印线程ID
    public synchronized sayId(long id){
        System.out.println(id);
    }
}
public class MyRunnable implements Runnable {    
    private Say say;    
    public MyRunnable(Say say){
        this.say=say;    
    }
    @Override    
    public void run() {
        while(true)
          say.saySomething(Thread.currentThread().getId());
    }   
}
public class Main{
    public static void main(String args[]){
        Say say=new Say();
        for(int i=0;i<5;i++){
          new Thread(new MyRunnable(say).start();
        }
    }
}

在这个例子中，每个线程会循环调用say实例的打印方法，而该方法是一个同步方法，存在竞争关系。看一波运行结果：

synchronized

显然并非每个线程都公平的进入同步方法，那么我们需要通过锁的方式进行改进
我们先来看一下sum.misc下的Lock类：

public class Lock {    
    private boolean locked = false;    
    public Lock() {    }    
    public final synchronized void lock() throws InterruptedException {
        while(this.locked) {
            this.wait();        
        }
        this.locked = true;    
    }    
    public final synchronized void unlock() {
        this.locked = false;        
        this.notifyAll();    
    }
}

这是一个最简单的锁实现，locked防止信号丢失和假唤醒，如果基于这个锁对Say进行改造，那么结果并不会有任何改变，因为notify方法不保证唤醒顺序。

基于lock进行改进

可以看到，所有的线程均在lock对象上进行wait操作，因此lock在notify的时候不能保证唤醒的顺序，如果我们需要公平，那么所有的线程应该拥有独立的等待对象，那么lock就可以通过唤醒各线程的等待对象以保证公平。基于这种朴素的思想，考虑设置一个队列，将每个线程的等待对象存储起来：

public class FairLock{
    //锁是否被占用
    private boolean isLocked=false;
    //占用线程
    private Thread lockingThread=null;
    private List<WaitObject> queue=new ArrayList<WaitObject>();
    //这个lock不用同步，因为需要多个线程都能进入该方法
    public void lock(){
        WaitObject waitObject=new WaitObject();
        synchronized(this){
            queue.add(waitObject);
       }
        boolean isLockedForThisThread=true;
        //判断是否需要等待
        while(isLockedForThisThread){
            //判断条件，如果已经上锁，或者队首的等待对象不是自身的等待对象
             synchronized(this){
               isLockedForThisThread=isLocked||queue.get(0)!=waitObject;
                if(!isLockedForThisThread){
                //该线程无需等待，可以拥有锁
                    isLocked=true;
                    queue.remove(waitObject);
                    lockingThread=Thread.currentThread();
                    return;
                }
            }
            //否则，该线程需要等待
            try{
                waitObject.doWait();
            }catch(InterruptedException e){
                synchronized(this){
                    queue.remove(waitObject);
                }
            }
        }
    }

    public synchronized void unlock(){
        isLocked=false;
        lockingThread=null;
        if(queue.size()>0){
          //看是否还有线程在等待
          queue.get(0).doNotify();
        }
    } 
}

WaitObject其实与之前的Lock结构几乎一致，就不在给出。关于isLockedForThisThread的作用，我的理解是为了判断当前线程是否需要等待，此处用while循环的作用也是当该线程被唤醒的时候需要再次进入循环，删除掉当前的等待对象，并标记当前持有锁的线程。
下面给出运行结果图：

采用自定义的公平锁

当然，上述只是一个简单的小例子，关于java库中对公平锁的实现以及其他内容，以后的文章再探讨。

注：本文的fairlock代码参考Jakob Jenkov的Starvation and Fairness一节