一道经典线程面试题的4种解法

http://www.iteye.com/topic/1117703

一道经典线程面试题的4种解法
一个关于线程的经典面试题，要求用三个线程，按顺序打印1,2,3,4,5.... 71,72,73,74, 75.
线程1先打印1,2,3,4,5, 然后是线程2打印6,7,8,9,10, 然后是线程3打印11,12,13,14,15. 接着再由线程1打印16,17,18,19,20....以此类推, 直到线程3打印到75。

简单的分析一下题目要求。从题目考察的角度看，题目考的是线程同步知识，既然是顺序打印，那么也就是在某一个时刻只有一个线程处于运行状态，其他两个线程必须出于等待状态。一个线程在一轮打印中，打印5个数字后，必须转为等待状态。另一个线程接着打印下5个数字，如此类推，直到75个数字全部打完。如何判断某一个线程应该打印，这里给每一个线程分配一个id号，0，1，2，如果需要打印的数字c / 5 %3 == id，表示当前线程需要打印一轮。每个线程都必须要判断15次，采用这种方法，算法的复杂度是15*3，共45个循环。这是打印程序中的基本逻辑，那怎么实现同步呢？请看下面的四种解法。

解法一

既然是同步的打印，很自然的想到synchronized关键字，那么只要把线程的run方法声明为synchronized的，就可以实现线程的同步。这是这个程序的基本解法。具体的代码如下：
Java代码 
public class NumberPrinter extends Thread { 
    static int c = 0; 
    private int id; 
 
    @Override 
    public synchronized void run() { 
        while (c < 75) { 
            if (c / 5 % 3 == id) { 
                for (int i = 0; i < 5; i++) { 
                    c++; 
                    System.out.format("Thread %d: %d %n", id, c); 
                } 
            } 
        } 
    } 
 
    public NumberPrinter(int id) { 
        super(); 
        this.id = id; 
    } 
 
    public static void main(String[] args) { 
// 启动3个带有id的线程，    
        for (int i = 0; i < 3; i++) { 
            new NumberPrinter(i).start(); 
        } 
    } 
} 
解法二

解法一中，线程的run方法基本全是对变量c进行操作的，因此，使用synchronized关键字声明方法同步，系统的开销是比较大的，因此我们可以选择volatile关键字对c变量进行声明，让变量c具有CompareAndSet的特性，也就是对变量的引用和操作是同步的。但是这个关键字在JDK5才被很好的支持，如果是JDK4，会出现意象不到的结果。具体的实现看下面的代码。
Java代码 
class VolatileNumberPrinter extends Thread { 
    volatile static int c = 0; 
    private int id; 
 
    @Override 
    public void run() { 
        while (c < 75) { 
            if (c / 5 % 3 == id) { 
                for (int i = 0; i < 5; i++) { 
                    c++; 
                    System.out.format("Thread %d: %d %n", id, c); 
                } 
            } 
        } 
    } 
 
    public VolatileNumberPrinter(int id) { 
        super(); 
        this.id = id; 
    } 
 
    public static void main(String[] args) { 
        for (int i = 0; i < 3; i++) { 
            new VolatileNumberPrinter(i).start(); 
        } 
    } 
} 
解法三

JDK5及以后的版本提供了并发锁的类，最常用的是ReentralLock，在多线程环境下可以保证被锁住的代码在某一个特定的运行时刻只有拿到锁的线程才可以运行该代码。锁的使用比synchronized关键要灵活，但必须保证该锁在需要的时候被释放。采用锁机制实现同步的代码如下。
Java代码 
class ReentrantLockNumberPrinter extends Thread { 
    static int c; 
    private int id; 
    private ReentrantLock lock = new ReentrantLock(); 
 
    public ReentrantLockNumberPrinter(int id) { 
        super(); 
        this.id = id; 
    } 
 
    @Override 
    public void run() { 
        try { 
            lock.lock();  // 拿到锁的线程在运行，没有拿到的线程在等待 
            while (c < 75) { 
                if (c / 5 % 3 == id) { 
                    for (int i = 0; i < 5; i++) { 
                        c++; 
                        System.out.format("Thread %d: %d %n", id, c); 
                    } 
                } 
            } 
        } finally {   //确保锁被释放 
            lock.unlock(); 
        } 
    } 
 
    public static void main(String[] args) { 
        for (int i = 0; i < 3; i++) { 
            new ReentrantLockNumberPrinter(i).start(); 
        } 
    } 
} 
解法四

JDK5的并发包除了提供锁机制的类外，还提供了用于原子操作的类，把需要打印的变量放入到一个原子类中去，调用该类的CompareAndSet操作是具有原子性的，那么在多线程的环境下，可以避免不一致的变量引用。

Java代码 
class AtomicIntegerNumberPrinter extends Thread { 
    private int id; 
    static AtomicInteger c = new AtomicInteger(0);   //声明一个原子整数，设置初始值为0 
 
    public AtomicIntegerNumberPrinter(int id) { 
        super(); 
        this.id = id; 
    } 
 
    public void run() { 
        while (c.get() < 75) { 
            if (c.get() / 5 % 3 == id) { 
                for (int i = 0; i < 5; i++) {                                                 
                                        c.getAndIncrement();  // 相当于 c++,但是具有原子性 
                                        System.out.format("Thread %d: %d %n", id, c.get()); 
                } 
            } 
        } 
    } 
 
    public static void main(String args[]) { 
        for (int i = 0; i < 3; i++) { 
            new AtomicIntegerNumberPrinter(i).start(); 
        } 
    } 
} 
本例中，AtomaticInteger.getAndIncrement()把原子整数中的变量加1，但是具有原子性，可以保证多线程下不会出现不一致的c变量引用。get方法不具有原子性，不过
Java代码 
c.get() / 5 % 3 == id 
这行代码能确保一个值是被期望的线程所打印。

从上面的四种解法重看，解法一把run方法声明为同步，其实是给该方法加了一把隐形的锁。解法三是采用并发锁的机制，本质上是和解法一是相同的，解法三需要JDK5及其以后的版本，解法一是最稳定的，适应性最广的，任何JDK版本都可以支持。解法二和解法四类似，但是volatile在jdk5后才被很好的支持，也只有jdk5及以后的版本才支持原子类。因此在实际的多线程编程中，首先还是synchronized关键字，wait()和notify()等传统的线程方法。

如果您发现有什么一些其它的方法，请分享出来，大家一起讨论，共同提高。

评论

1 楼 winston1991 2011-11-20