java并发编程--一道经典多线程题的2种解法

coolxing

浏览: 870048 次
性别:
来自: 北京

最近访客更多访客>>

xiongc

beee

db6623919

hyzheng

博主相关

博客

微博

相册

留言

关于我

博客专栏

: Java Concurre...
浏览量：95950

文章分类

社区版块

存档分类

博客分类：

java并发

java 锁同步趣题 java多线程

coolxing按: 转载请注明作者和出处, 如有谬误, 欢迎在评论中指正.]

问题的描述

启动3个线程打印递增的数字, 线程1先打印1,2,3,4,5, 然后是线程2打印6,7,8,9,10, 然后是线程3打印11,12,13,14,15. 接着再由线程1打印16,17,18,19,20....以此类推, 直到打印到75. 程序的输出结果应该为:

线程1: 1

线程1: 2

线程1: 3

线程1: 4

线程1: 5

线程2: 6

线程2: 7

线程2: 8

线程2: 9

线程2: 10

...

线程3: 71

线程3: 72

线程3: 73

线程3: 74

线程3: 75

解法一: 采用原始的synchronized, wait(), notify(), notifyAll()等方式控制线程.

public class NumberPrintDemo {
	// n为即将打印的数字
	private static int n = 1;
	// state=1表示将由线程1打印数字, state=2表示将由线程2打印数字, state=3表示将由线程3打印数字
	private static int state = 1;

	public static void main(String[] args) {
		final NumberPrintDemo pn = new NumberPrintDemo();
		new Thread(new Runnable() {
			public void run() {
				// 3个线程打印75个数字, 单个线程每次打印5个连续数字, 因此每个线程只需执行5次打印任务. 3*5*5=75
				for (int i = 0; i < 5; i++) {
					// 3个线程都使用pn对象做锁, 以保证每个交替期间只有一个线程在打印
					synchronized (pn) {
						// 如果state!=1, 说明此时尚未轮到线程1打印, 线程1将调用pn的wait()方法, 直到下次被唤醒
						while (state != 1)
							try {
								pn.wait();
							} catch (InterruptedException e) {
								e.printStackTrace();
							}
						// 当state=1时, 轮到线程1打印5次数字
						for (int j = 0; j < 5; j++) {
							// 打印一次后n自增
							System.out.println(Thread.currentThread().getName()
									+ ": " + n++);
						}
						System.out.println();
						// 线程1打印完成后, 将state赋值为2, 表示接下来将轮到线程2打印
						state = 2;
						// notifyAll()方法唤醒在pn上wait的线程2和线程3, 同时线程1将退出同步代码块, 释放pn锁. 
						// 因此3个线程将再次竞争pn锁
						// 假如线程1或线程3竞争到资源, 由于state不为1或3, 线程1或线程3将很快再次wait, 释放出刚到手的pn锁. 
						// 只有线程2可以通过state判定, 所以线程2一定是执行下次打印任务的线程.
						// 对于线程2来说, 获得锁的道路也许是曲折的, 但前途一定是光明的.
						pn.notifyAll();
					}
				}
			}
		}, "线程1").start();

		new Thread(new Runnable() {
			public void run() {
				for (int i = 0; i < 5; i++) {
					synchronized (pn) {
						while (state != 2)
							try {
								pn.wait();
							} catch (InterruptedException e) {
								e.printStackTrace();
							}
						for (int j = 0; j < 5; j++) {
							System.out.println(Thread.currentThread().getName()
									+ ": " + n++);
						}
						System.out.println();
						state = 3;
						pn.notifyAll();
					}
				}
			}
		}, "线程2").start();

		new Thread(new Runnable() {
			public void run() {
				for (int i = 0; i < 5; i++) {
					synchronized (pn) {
						while (state != 3)
							try {
								pn.wait();
							} catch (InterruptedException e) {
								e.printStackTrace();
							}
						for (int j = 0; j < 5; j++) {
							System.out.println(Thread.currentThread().getName()
									+ ": " + n++);
						}
						System.out.println();
						state = 1;
						pn.notifyAll();
					}
				}
			}
		}, "线程3").start();
	}
}

解法二: 采用JDK1.5并发包提供的Lock, Condition等类的相关方法控制线程.

public class NumberPrint implements Runnable {
	private int state = 1;
	private int n = 1;
	// 使用lock做锁
	private ReentrantLock lock = new ReentrantLock();
	// 获得lock锁的3个分支条件
	private Condition c1 = lock.newCondition();
	private Condition c2 = lock.newCondition();
	private Condition c3 = lock.newCondition();

	@Override
	public void run() {
		new Thread(new Runnable() {
			public void run() {
				for (int i = 0; i < 5; i++) {
					try {
						// 线程1获得lock锁后, 其他线程将无法进入需要lock锁的代码块.
						// 在lock.lock()和lock.unlock()之间的代码相当于使用了synchronized(lock){}
						lock.lock();
						while (state != 1)
							try {
								// 线程1竞争到了lock, 但是发现state不为1, 说明此时还未轮到线程1打印. 
								// 因此线程1将在c1上wait
								// 与解法一不同的是, 三个线程并非在同一个对象上wait, 也不由同一个对象唤醒
								c1.await();
							} catch (InterruptedException e) {
								e.printStackTrace();
							}
						// 如果线程1竞争到了lock, 也通过了state判定, 将执行打印任务
						for (int j = 0; j < 5; j++) {
							System.out.println(Thread.currentThread().getName()
									+ ": " + n++);
						}
						System.out.println();
						// 打印完成后将state赋值为2, 表示下一次的打印任务将由线程2执行
						state = 2;
						// 唤醒在c2分支上wait的线程2
						c2.signal();
					} finally {
						// 打印任务执行完成后需要确保锁被释放, 因此将释放锁的代码放在finally中
						lock.unlock();
					}
				}
			}
		}, "线程1").start();

		new Thread(new Runnable() {
			public void run() {
				for (int i = 0; i < 5; i++) {
					try {
						lock.lock();
						while (state != 2)
							try {
								c2.await();
							} catch (InterruptedException e) {
								e.printStackTrace();
							}
						for (int j = 0; j < 5; j++) {
							System.out.println(Thread.currentThread().getName()
									+ ": " + n++);
						}
						System.out.println();
						state = 3;
						c3.signal();
					} finally {
						lock.unlock();
					}
				}
			}
		}, "线程2").start();

		new Thread(new Runnable() {
			public void run() {
				for (int i = 0; i < 5; i++) {
					try {

						lock.lock();
						while (state != 3)
							try {
								c3.await();
							} catch (InterruptedException e) {
								e.printStackTrace();
							}
						for (int j = 0; j < 5; j++) {
							System.out.println(Thread.currentThread().getName()
									+ ": " + n++);
						}
						System.out.println();
						state = 1;
						c1.signal();
					} finally {
						lock.unlock();
					}
				}
			}
		}, "线程3").start();
	}
	
	public static void main(String[] args) {
		new NumberPrint().run();
	}
}

总结: 对比解法一和解法二, 显然解法二是更好的解决方案. 解法一的问题在于无法进行精确唤醒, 比如线程1执行完打印任务并调用pn.notifyAll()方法后, 3个线程将再次竞争锁, 而不是精确唤醒线程2. 虽然线程2最终将赢得锁, 下一次的打印任务也肯定会由线程2执行, 但是竞争的持续时间是不可预知的, 只能看线程2的人品.

最糟糕的情形可以是: 线程3竞争到了锁, 紧接着wait. 接下来线程1也竞争到了锁, 然后线程1也wait. 此时就再也没有其他线程跟线程2竞争了, 线程2终于艰难的赢得了锁...

留下3个问题供有兴趣的朋友思考:

1. 解法一和解法二中的while (state != xx)是否可以换成if(state != xx), 为什么?

2. 解法一的中的pn.notifyAll()是否可以换成pn.notify(), 为什么?

3. 是否可以用wait(), notify(), notifyAll()等方法完成类似解法二的精确唤醒, 请给出方案或代码.--这个问题我思考了很久, 却没有头绪. 关键的困难在于必须调用pn的wait()方法和notifyAll()方法, 而不能是其他对象的wait()和notifyAll()方法. 如果你有思路, 还望在博客中留言, 不甚感激!

7
顶

3
踩

分享到：

java并发编程--互斥锁, 读写锁及条件 | java并发编程--线程池初步

2011-11-06 14:10
浏览 25755
评论(18)
分类:编程语言
查看更多

18 楼 yuanliangding 2016-08-02

第二题，解法二，是可以换成if的吧。
因为休眠了，没有人唤醒是不会起来的。
这里又是精确唤醒。上一家只有自己的完全搞定了才会来唤醒。

17 楼 u014087707 2016-02-20

16 楼 zhutulang 2014-12-28

Mojarra 写道

搂主的第二种思路具有很高的研究价值

对于第一种方法，我这里有个思路要简单些，这个题目其实是3个运行中的线程，在某一个时刻只有一是可以打印数字的，其他2个都必须是等待状态。给每一个线程一个id，state表示打印序列，75/5/3，可以得出来共有15个打印序列，如果state%3==id,表示当前线程可以打印，否则必须等到一个可打印的序列完成才可以进行下一轮循环。那么可以在方法级上用synchronized关键字声明。虽然有线程竞争的情形出现，但不会出现思锁。


class NumberPrinter extends Thread {
	static int c = 0;
	static int state = 0;
	private int id;

	@Override
	public synchronized void run() {
		while (state < 15) {
			if (state % 3 == id) {
				for (int j = 0; j < 5; j++) {
					c++;
					System.out.format("Thread %d: %d %n", id, c);
				}
				state++;
			}
		}
	}

	public NumberPrinter(int id) {
		this.id = id;
	}

	public static void main(String[] args) {
		for (int i = 0; i < 3; i++) {
			new NumberPrinter(i).start();
		}
	}
}

这段代码有问题，会产生死循环。可以把state 变量改为 volatile state

15 楼 zhubinhua 2013-06-05

coolxing 写道

Mojarra 写道


class NumberPrinter extends Thread {
	static int c = 0;
	static int state = 0;
	private int id;

	@Override
	public synchronized void run() {
		while (state < 15) {
			if (state % 3 == id) {
				for (int j = 0; j < 5; j++) {
					c++;
					System.out.format("Thread %d: %d %n", id, c);
				}
				state++;
			}
		}
	}

	public NumberPrinter(int id) {
		this.id = id;
	}

	public static void main(String[] args) {
		for (int i = 0; i < 3; i++) {
			new NumberPrinter(i).start();
		}
	}
}

Mojarra兄，感谢你的思路。没想到还有这样简单的解法。
这道题是我和同学研究新浪面试题的时候发现的，我为此思考了好多个小时才想出解法一，郁闷的是我们老师几天之后讲解了这道题，他初始的解法和我的思考结果不谋而合。
至于解法二，则完全是老师的功劳，他用解法二向我们简单了介绍了一下JDK1.5中的并发访问控制。 JDK1.5的Lock和Condition结合可以做到精确唤醒waitset中的一个线程，这确实挺让人兴奋的。这几天我终于下定了决心好好学习一下java并发，所以才把这道题发出来的。
希望以后能多与你交流。

run为什么要synchronized的呢？这三个线程产生竞争的。

14 楼 lyx2007825 2012-12-10

我用Java内置的同步工具CyclicBarrier也解决了这个问题，看我的博客：
http://blog.csdn.net/lyx2007825/article/details/7767408

13 楼 lyx2007825 2012-12-09

package net.liuyx.test;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class Test {
	private static int num = 0;
	private static int flag = 0;
	private static Lock lock = new ReentrantLock();
	private static Condition c1 = lock.newCondition();
	private static Condition c2 = lock.newCondition();
	private static Condition c3 = lock.newCondition();
	private static List<Condition> list = new ArrayList<Condition>();
	private static ExecutorService exec = Executors.newFixedThreadPool(4);
	static {
		list.add(c1);
		list.add(c2);
		list.add(c3);
	}

	private static void crit() {
		if (num >= 75) {
			System.exit(1);
		}
	}

	private static void print() {
		crit();
		System.out.print(Thread.currentThread());
		for (int i = 0; i < 5; i++) {
			System.out.format("%-2d ", ++num);
		}
		System.out.println();
	}

	private static void work(int i) {
			while (!Thread.interrupted()) {
				try{
					lock.lock();
					if(flag == i){
						crit();
						print();
						flag = (i + 1) % list.size();
						list.get((i+1)%list.size()).signal();
					}else{
						try {
							list.get(i%4).await();
						} catch (InterruptedException e) {
							e.printStackTrace();
						}
					}
				}finally{
					lock.unlock();
				}
			}
	}

	private static class Task implements Runnable {
		private final int i;

		public Task(int i) {
			this.i = i;
		}

		@Override
		public void run() {
			work(i);
		}

	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		for (int i = 0; i < list.size(); i++)
			exec.execute(new Task(i));
	}

}

看看这样可以不，正常输出：
[img]

[/img]

12 楼 hustguojiecheng 2012-08-24

解法2 好像是可以把while换成if的

11 楼 hustguojiecheng 2012-08-24

关于问题1，考虑以下场景，即abc顺序步骤。
a、1处于synchronized，2处于waiting，3抢到锁后notifyAll结束5轮打印，剩下1和2竞争锁；
b、2抢到锁继续执行，执行后state变为3并notifyAll；
c、2在notifyAll后1还没来得及抢到锁，2就执行到了synchronized，并又再次获取了锁，由于state=3，2就waiting，这个时候处于synchronized的1抢到锁，由于state=3，1也waiting。
c也可以换为：1抢到了锁，由于state=3，1就waiting，这个时候处于synchronized的2抢到锁，由于state=3，2也waiting。

10 楼 hustguojiecheng 2012-08-24

1. 解法一和解法二中的while (state != xx)是否可以换成if(state != xx), 为什么?
   不能。若换成if，会有以下情况：
    1、不是按照线程123依次打印的顺序；
    2、有可能线程3在线程1和线程2之前5轮打印完毕，1,2来互相竞争，如果2抢到锁，state变为3，这个时候就悲剧了，线程1和线程2永远就waiting吧！
2. 解法一的中的pn.notifyAll()是否可以换成pn.notify(), 为什么?
    不能。因为换成pn.notify()，理论上会出现某个线程永远抢不到锁导致饿死。
3. 暂时没考虑。

9 楼 coolxing 2012-04-12

jingshuai1029 写道

兄弟，这个写法扩展性不好，如果不是三个线程而是X个线程，每次打钱y个数，直到打印到Z，你的程序怎么办.

你说的对, 扩展性确实不好, 当时写这个程序的时候没有想这么多...
不过做一个简单的重构就可以, 多谢建议

8 楼 jingshuai1029 2012-04-12

兄弟，这个写法扩展性不好，如果不是三个线程而是X个线程，每次打钱y个数，直到打印到Z，你的程序怎么办.

7 楼 coolxing 2011-11-08

Mojarra 写道

原描述有误！
我在运行程序的时候发现3个线程有“竞争”情况，让线程打印一轮后休眠500ms，则可以避免“竞争”。大概的思想是既然不唤醒其他的线程，自己休眠，避免在变量state，c上的竞争。

这个题目很有意思，我还研究出一些其它的解法。等把java5的那个concurrent用法一起，总结出一篇小搏客

嗯, 到时一定拜读

6 楼 Mojarra 2011-11-08

5 楼 coolxing 2011-11-07

Mojarra 写道


class NumberPrinter extends Thread {
	static int c = 0;
	static int state = 0;
	private int id;

	@Override
	public synchronized void run() {
		while (state < 15) {
			if (state % 3 == id) {
				for (int j = 0; j < 5; j++) {
					c++;
					System.out.format("Thread %d: %d %n", id, c);
				}
				state++;
			}
		}
	}

	public NumberPrinter(int id) {
		this.id = id;
	}

	public static void main(String[] args) {
		for (int i = 0; i < 3; i++) {
			new NumberPrinter(i).start();
		}
	}
}

4 楼 coolxing 2011-11-07

Mojarra 写道

ps，如果在一个打印序列完成后，让线程休眠500ms，则不会避免竞争情况

“不会避免竞争情况”这句话是不是表述有误？而且一个打印序列完成后让线程sleep 500ms有什么意义呢--sleep的时间内并不释放锁，这只能徒增系统资源的消耗罢了。

3 楼 Mojarra 2011-11-07

ps，如果在一个打印序列完成后，让线程休眠500ms，则不会避免竞争情况

2 楼 Mojarra 2011-11-07


class NumberPrinter extends Thread {
	static int c = 0;
	static int state = 0;
	private int id;

	@Override
	public synchronized void run() {
		while (state < 15) {
			if (state % 3 == id) {
				for (int j = 0; j < 5; j++) {
					c++;
					System.out.format("Thread %d: %d %n", id, c);
				}
				state++;
			}
		}
	}

	public NumberPrinter(int id) {
		this.id = id;
	}

	public static void main(String[] args) {
		for (int i = 0; i < 3; i++) {
			new NumberPrinter(i).start();
		}
	}
}

1 楼 Technoboy 2011-11-07

1.会产生死锁
2.与对象进入waitset"队列"后被唤醒的执行点有关
3.如果用wait,notify这种方式，是根本无法达到精确的控制唤醒。

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

博客专栏

文章分类

社区版块

存档分类

最新评论