首页 > 代码库 > Java 线程第三版 第六章 高级同步议题 读书笔记

Java 线程第三版 第六章 高级同步议题 读书笔记



    多线程数据同步错误比较难检测,因为通常是与事件的特定发生顺序有关。

一、同步术语
Barrier(屏障)
    barrier是多个Thread的集合点:所有的Thread都应该到齐在这个barrier之后才能允许它们继续下去。

Condition variable(条件变量)
    实际上不是变量,而是与某个lock有关联的变量。

Event variable(事件变量)
    条件变量的另一个名称。

Critical section(临界区)
    临界区是synchronized方法或者block。

Lock(锁)
    已经进入synchronized方法或者block的特定Thread所授予的访问权。

Mutex(互斥)
    lock的另一个名字。

Monitor(监视器)
    在某些系统中,一个monitor就是一个lock,其他系统中的monitor类似于等待与通知的机制。

Reader/writer lock(读/写锁)
    一种可以被多个Thread同时取得的锁,只要各Thread间都同意只从共享数据中做读的操作(或者写操作)。

Semaphore(信号量)
    在各系统间使用是不一致的。不能完全等同于lock方式使用。

二、J2SE 5.0中加入的同步Class
Semaphore
    Semaphore记录它可以发出的许可数目。
    Semaphore与Lock的区别,Semaphore构造器需要制定许可数目,方法可以返回许可的总数与可用数量。Semaphore没有关联的条件变量可用。
   
Barrier
    未广泛使用的原因是可以有两种替代方案:
    1. 要求Thread等待条件变量,最后达到Thread通过通知所有其他Thread来释放掉barrier。
    2. 通过join方法等待Thread终结,一旦所有的Thread已经被结合,就可以启动新的Thread进行程序的下一个阶段。

倒数的Latch
    类似与Barrier的同步功能。区别在于释放的条件不是等待所有thread满足条件。

Exchanger
    其结合barrier以及数据传递。能够让一对thread相互回合类似与barrier,这一对thread相遇时能够在分开前交换一组数据。

读/写锁
    有时候需要在可能会很长时间的操作下从对象中读取信息。

三、防止死锁
import javax.swing.*;
import java.awt.event.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.*;
import javathreads.examples.ch03.*;

public class ScoreLabel extends JLabel implements CharacterListener {
    
    private volatile int score = 0;
    private int char2type = -1;
    private CharacterSource generator = null, typist = null;
    private Lock adminLock = new ReentrantLock();
    private Lock charLock = new ReentrantLock();
    private Lock scoreLock = new ReentrantLock();


    public ScoreLabel (CharacterSource generator, CharacterSource typist) {
        this.generator = generator;
        this.typist = typist;

        if (generator != null)
            generator.addCharacterListener(this);
        if (typist != null)
             typist.addCharacterListener(this);       
    }

    public ScoreLabel () {
        this(null, null);
    }

    public void resetGenerator(CharacterSource newGenerator) {
        try {
            adminLock.lock();
            if (generator != null)
                generator.removeCharacterListener(this);

            generator = newGenerator;
            if (generator != null)
                generator.addCharacterListener(this);
        } finally {
            adminLock.unlock();
        }
    }

    public void resetTypist(CharacterSource newTypist) {
        try {
            adminLock.lock();
            if (typist != null)
                typist.removeCharacterListener(this);

            typist = newTypist;
            if (typist != null)
                typist.addCharacterListener(this);
        } finally {
            adminLock.unlock();
        }
    }

    public void resetScore() {
        try {
            charLock.lock();
            scoreLock.lock();
            score = 0;
            char2type = -1;
            setScore();
        } finally {
            charLock.unlock();
            scoreLock.unlock();
        }
    }

    private void setScore() {
        // This method will be explained later in chapter 7
        SwingUtilities.invokeLater(new Runnable() {
            public void run() {
                setText(Integer.toString(score));
            }
        });
    }

    public void newCharacter(CharacterEvent ce) {
        try {
            scoreLock.lock();
            charLock.lock();
            // Previous character not typed correctly - 1 point penalty
            if (ce.source == generator) {
                if (char2type != -1) {
                    score--;
                    setScore();
                }
                char2type = ce.character;
            }

            // If character is extraneous - 1 point penalty
            // If character does not match - 1 point penalty
            else {
                if (char2type != ce.character) {
                    score--;
                } else {
                    score++;
                    char2type = -1;
                }
                setScore();
            }
        } finally {
            scoreLock.unlock();
            charLock.unlock();
        }
    } 
}


    避免死锁最简单的方法就是当持有一个锁的时候,绝对不再调用任何需要其他锁的方法。

import javax.swing.*;
import java.awt.event.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.*;
import javathreads.examples.ch03.*;

public class ScoreLabel extends JLabel implements CharacterListener {
    
    private volatile int score = 0;
    private int char2type = -1;
    private CharacterSource generator = null, typist = null;
    private Lock adminLock = new ReentrantLock();
    private Lock charLock = new ReentrantLock();
    private Lock scoreLock = new ReentrantLock();


    public ScoreLabel (CharacterSource generator, CharacterSource typist) {
        this.generator = generator;
        this.typist = typist;

        if (generator != null)
            generator.addCharacterListener(this);
        if (typist != null)
             typist.addCharacterListener(this);       
    }

    public ScoreLabel () {
        this(null, null);
    }

    public void resetGenerator(CharacterSource newGenerator) {
        try {
            adminLock.lock();
            if (generator != null)
                generator.removeCharacterListener(this);

            generator = newGenerator;
            if (generator != null)
                generator.addCharacterListener(this);
        } finally {
            adminLock.unlock();
        }
    }

    public void resetTypist(CharacterSource newTypist) {
        try {
            adminLock.lock();
            if (typist != null)
                typist.removeCharacterListener(this);

            typist = newTypist;
            if (typist != null)
                typist.addCharacterListener(this);
        } finally {
            adminLock.unlock();
        }
    }

    public void resetScore() {
        try {
            scoreLock.lock();
            charLock.lock();
            score = 0;
            char2type = -1;
            setScore();
        } finally {
            charLock.unlock();
            scoreLock.unlock();
        }
    }

    private void setScore() {
        // This method will be explained later in chapter 7
        SwingUtilities.invokeLater(new Runnable() {
            public void run() {
                setText(Integer.toString(score));
            }
        });
    }

    public void newCharacter(CharacterEvent ce) {
        try {
            scoreLock.lock();
            charLock.lock();
            // Previous character not typed correctly - 1 point penalty
            if (ce.source == generator) {
                if (char2type != -1) {
                    score--;
                    setScore();
                }
                char2type = ce.character;
            }

            // If character is extraneous - 1 point penalty
            // If character does not match - 1 point penalty
            else {
                if (char2type != ce.character) {
                    score--;
                } else {
                    score++;
                    char2type = -1;
                }
                setScore();
            }
        } finally {
            scoreLock.unlock();
            charLock.unlock();
        }
    } 
}



死锁与自动释放的Lock
    Lock Interface锁不会自动释放,即使异常退出程序。而synchronized关键字异常情况下依然会释放。
    一种避免这种情况发生的办法就是把unLock放置到finally子句中。
    synchronized在异常情况下都能释放锁并不一定在所有场景下都是优点,有可能当前方法执行一部分异常退出,其他线程再执行有可能获取到的并不是正确数据。

使用时限来防止死锁
    通过在lock上设定期限,使用tryLock()在算法中提供替代方案。

四、死锁检测
    死锁的问题在于它会导致程序无止境地等待。

支持检测死锁的Lock类,用于演示分析死锁过程:
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.*;

//
// This is a very very slow implementation of a ReentrantLock class and is not for
//   everyday usage. The purpose of this class is to test for deadlocks. The lock()
//   method now throws a DeadlockDetectedException, if a deadlock occurs.
//
public class DeadlockDetectingLock extends ReentrantLock {
    // List of deadlock detecting locks.
    // This array is not thread safe, and must be externally synchronized
    //    by the class lock. Hence, it should only be called by static
    //    methods.
    private static List deadlockLocksRegistry = new ArrayList();

    private static synchronized void registerLock(DeadlockDetectingLock ddl) {
        if (!deadlockLocksRegistry.contains(ddl))
             deadlockLocksRegistry.add(ddl);
    }

    private static synchronized void unregisterLock(DeadlockDetectingLock ddl) {
        if (deadlockLocksRegistry.contains(ddl))
             deadlockLocksRegistry.remove(ddl);
    }

    // List of threads hard waiting for this lock.
    // This array is not thread safe, and must be externally synchronized
    //    by the class lock. Hence, it should only be called by static
    //    methods.
    private List hardwaitingThreads = new ArrayList();

    private static synchronized void markAsHardwait(List l, Thread t) {
        if (!l.contains(t)) l.add(t);
    }

    private static synchronized void freeIfHardwait(List l, Thread t) {
        if (l.contains(t)) l.remove(t);
    }

    //
    // Deadlock checking methods
    //
    // Given a thread, return all locks that are already owned
    // Must own class lock prior to calling this method
    private static Iterator getAllLocksOwned(Thread t) {
        DeadlockDetectingLock current;
        ArrayList results = new ArrayList();

        Iterator itr = deadlockLocksRegistry.iterator();
        while (itr.hasNext()) {
            current = (DeadlockDetectingLock) itr.next();
            if (current.getOwner() == t) results.add(current);
        }
        return results.iterator(); 
    }

    // Given a lock, return all threads that are hard waiting for the lock
    // Must own class lock prior to calling this method
    private static Iterator getAllThreadsHardwaiting(DeadlockDetectingLock l) {
        return l.hardwaitingThreads.iterator();
    }

    // Check to see if a thread can perform a hard wait on a lock
    private static synchronized
             boolean canThreadWaitOnLock(Thread t, DeadlockDetectingLock l) {
        Iterator locksOwned = getAllLocksOwned(t);
        while (locksOwned.hasNext()) {
            DeadlockDetectingLock current = (DeadlockDetectingLock) locksOwned.next();

            // Thread can't wait if lock is already owned. This is the end condition
            //      for the recursive algorithm -- as the initial condition should be
            //      already tested for.
            if (current == l) return false;

            Iterator waitingThreads = getAllThreadsHardwaiting(current);
            while (waitingThreads.hasNext()) {
                Thread otherthread = (Thread) waitingThreads.next();

                // In order for the thread to safely wait on the lock, it can't
                //   own any locks that have waiting threads that already owns
                //   lock. etc. etc. etc. recursively etc.
                if (!canThreadWaitOnLock(otherthread, l)) {
                    return false;
                }
            }
        }
        return true;
    }

    //
    // Core Constructors
    //
    public DeadlockDetectingLock() {
        this(false, false);
    }

    public DeadlockDetectingLock(boolean fair) {
        this(fair, false);
    }

    private boolean debugging;
    public DeadlockDetectingLock(boolean fair, boolean debug) {
        super(fair);
        debugging = debug;
        registerLock(this);
    }

    //
    // Core Methods
    //
    public void lock() {
        // Note: Owner can't change if current thread is owner. It is
        //       not guaranteed otherwise. Other owners can change due to
        //       condition variables.
        if (isHeldByCurrentThread()) {
            if (debugging) System.out.println("Already Own Lock");
            super.lock();
            freeIfHardwait(hardwaitingThreads, Thread.currentThread());
            return;
        }

        // Note: The wait list must be marked before it is tested because
        //       there is a race condition between lock() method calls.
        markAsHardwait(hardwaitingThreads, Thread.currentThread());
        if (canThreadWaitOnLock(Thread.currentThread(), this)) {
            if (debugging) System.out.println("Waiting For Lock");
            super.lock();
            freeIfHardwait(hardwaitingThreads, Thread.currentThread());
            if (debugging) System.out.println("Got New Lock");
        } else {
            throw new DeadlockDetectedException("DEADLOCK");
        }
    }

    //
    // Note: It is debatable whether this is a hard or soft wait. Even if
    //       interruption is common, we don't know if the interrupting thread
    //       is also involved in the deadlock. As a compromise, we'll just
    //       not allow interrupts. This method is disabled.
    public void lockInterruptibly() throws InterruptedException {
        lock();
    }

    //
    // Note: It is not necessary to override the tryLock() methods. These
    //     methods perform a soft wait -- there is a limit to the wait. It
    //     not possible to deadlock when locks are not waiting indefinitely.
    //

    // Note 1: Deadlocks are possible with any hard wait -- this includes
    //      the reacquitition of the lock upon return from an await() method.
    //      As such, condition variables will mark for the future hard
    //      wait, prior to releasing the lock.
    // Note 2: There is no need to check for deadlock on this end because
    //      a deadlock can be created whether the condition variable owns the
    //      lock or is reacquiring it. Since we are marking *before* giving
    //      up ownership, the deadlock will be detected on the lock() side
    //      first. It is not possible to create a new deadlock just by releasing
    //      locks.
    public class DeadlockDetectingCondition implements Condition {
	Condition embedded;
        protected DeadlockDetectingCondition(ReentrantLock lock, Condition embedded) {
	    this.embedded = embedded;
        }

        // Note: The algorithm can detect a deadlock condition if the thead is
        //    either waiting for or already owns the lock, or both. This is why
        //    we have to mark for waiting *before* giving up the lock.
        public void await() throws InterruptedException {
            try {
                markAsHardwait(hardwaitingThreads, Thread.currentThread());
                embedded.await();
            } finally {
                freeIfHardwait(hardwaitingThreads, Thread.currentThread());
            }
        }

        public void awaitUninterruptibly() {
            markAsHardwait(hardwaitingThreads, Thread.currentThread());
            embedded.awaitUninterruptibly();
            freeIfHardwait(hardwaitingThreads, Thread.currentThread());
        }

        public long awaitNanos(long nanosTimeout) throws InterruptedException {
            try {
                markAsHardwait(hardwaitingThreads, Thread.currentThread());
                return embedded.awaitNanos(nanosTimeout);
            } finally {
                freeIfHardwait(hardwaitingThreads, Thread.currentThread());
            }
        }

        public boolean await(long time, TimeUnit unit) throws InterruptedException {
            try {
                markAsHardwait(hardwaitingThreads, Thread.currentThread());
                return embedded.await(time, unit);
            } finally {
                freeIfHardwait(hardwaitingThreads, Thread.currentThread());
            }
        }

        public boolean awaitUntil(Date deadline) throws InterruptedException {
            try {
                markAsHardwait(hardwaitingThreads, Thread.currentThread());
                return embedded.awaitUntil(deadline);
            } finally {
                freeIfHardwait(hardwaitingThreads, Thread.currentThread());
            }
        }

	public void signal() {
	    embedded.signal();
	}

	public void signalAll() {
	    embedded.signalAll();
	}
    }

    // Return a condition variable that support detection of deadlocks
    public Condition newCondition() {
        return new DeadlockDetectingCondition(this, super.newCondition());
    }

    //
    // Testing routines here
    //
    // These are very simple tests -- more tests will have to be written
    private static Lock a = new DeadlockDetectingLock(false, true);
    private static Lock b = new DeadlockDetectingLock(false, true);
    private static Lock c = new DeadlockDetectingLock(false, true);
    private static Condition wa = a.newCondition();
    private static Condition wb = b.newCondition();
    private static Condition wc = c.newCondition();

    private static void delaySeconds(int seconds) {
        try {
             Thread.sleep(seconds * 1000);
        } catch (InterruptedException ex) {
        }
    }

    private static void awaitSeconds(Condition c, int seconds) {
        try {
             c.await(seconds, TimeUnit.SECONDS);
        } catch (InterruptedException ex) {
        }
    }

    private static void testOne() {
         new Thread(new Runnable() {
             public void run() {
                 System.out.println("thread one grab a");
                 a.lock();
                 delaySeconds(2);
                 System.out.println("thread one grab b");
                 b.lock();
                 delaySeconds(2);
                 a.unlock(); b.unlock();
             }
         }).start();

         new Thread(new Runnable() {
             public void run() {
                 System.out.println("thread two grab b");
                 b.lock();
                 delaySeconds(2);
                 System.out.println("thread two grab a");
                 a.lock();
                 delaySeconds(2);
                 a.unlock(); b.unlock();
             }
         }).start();
    }

    private static void testTwo() {
         new Thread(new Runnable() {
             public void run() {
                 System.out.println("thread one grab a");
                 a.lock();
                 delaySeconds(2);
                 System.out.println("thread one grab b");
                 b.lock();
                 delaySeconds(10);
                 a.unlock(); b.unlock();
             }
         }).start();

         new Thread(new Runnable() {
             public void run() {
                 System.out.println("thread two grab b");
                 b.lock();
                 delaySeconds(2);
                 System.out.println("thread two grab c");
                 c.lock();
                 delaySeconds(10);
                 b.unlock(); c.unlock();
             }
         }).start();

         new Thread(new Runnable() {
             public void run() {
                 System.out.println("thread three grab c");
                 c.lock();
                 delaySeconds(4);
                 System.out.println("thread three grab a");
                 a.lock();
                 delaySeconds(10);
                 c.unlock(); a.unlock();
             }
         }).start();
    }
 
    private static void testThree() {
         new Thread(new Runnable() {
             public void run() {
                 System.out.println("thread one grab b");
                 b.lock();
                 System.out.println("thread one grab a");
                 a.lock();
                 delaySeconds(2);
                 System.out.println("thread one waits on b");
                 awaitSeconds(wb, 10);                 
                 a.unlock(); b.unlock();
             }
         }).start();

         new Thread(new Runnable() {
             public void run() {
                 delaySeconds(1);
                 System.out.println("thread two grab b");
                 b.lock();
                 System.out.println("thread two grab a");
                 a.lock();
                 delaySeconds(10);
                 b.unlock(); c.unlock();
             }
         }).start();

    }

    public static void main(String args[]) {
        int test = 1;
	if (args.length > 0)
	    test = Integer.parseInt(args[0]);
	switch(test) {
	    case 1:
                testOne();    // 2 threads deadlocking on grabbing 2 locks
		break;
	    case 2:
        	testTwo();    // 3 threads deadlocking on grabbing 2 out of 3 locks
		break;
	    case 3:
                testThree();  // 2 threads deadlocking on 2 locks with CV wait 
		break;
	    default:
	        System.err.println("usage: java DeadlockDetectingLock [ test# ]");
	}
        delaySeconds(60);
        System.out.println("--- End Program ---");
        System.exit(0);
    }
}



    此实现继承Lock Interface,所以可以用在任何需要Lock对象的地方。
    在所有需要检测死锁的地方都已此类取代,甚至包括synchronized关键字锁提供的锁。
    在检测到死锁时会立即抛出DeadlockDetectedException。 但是这个类未考虑性能问题,所以尽量不要在真实环境中使用。

    两个集合
    lock通过使用registerLock、unregisterLock方法来进行添加与删除注册监听。
    getAllLocksOwned、getAllThreadsHardwaiting用来取得之前所提过的两种等待子树。
    canThreadWaitOnLock用来遍历等待树,检查某特定lock是否已经出现在树上。检测潜在死锁的主要方法。
    覆写lock方法
        如果当前thread已经持有此lock,没有理由检查死锁。仅需要调用super.lock()即可。
        通过canThreadWaitOnLock判断是否死锁。如果死锁抛出异常,反之此Thread就会被添加到lock的hard wait列表中,并调用super.lock()方法。


五、Lock饥饿
    每当有多个Thread争夺稀少的资源时,就会有饥饿的危机Thread会存在永远拿不到资源的状况。
    例如:某个Thread获得锁之后永远不释放。

public ReentrantLock(boolean fair)
     创建一个具有给定公平策略的 ReentrantLock。

    这是一种非常接近先到先服务原则来授出Lock,不管Thread有多少或者是怎么写的,都不可能有任何Thread会因为Lock而挨饿。