面试题:
有n张火车票,每张票都有一个编号,同时有10个窗口对外售票,请写一个模拟程序
Case1( 使用ArrayList:问题引入)
import java.util.ArrayList;
import java.util.List;
public class TicketSeller1 {
static List<String> tickets=new ArrayList<>();
static {
for (int i = 0; i < 10000; i++) {
tickets.add("票编号:"+i);
}
}
public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
new Thread(()->{
while (tickets.size()>0){
System.out.println(Thread.currentThread().getName()+"销售了--"+tickets.remove(0));
}
},"窗口"+i).start();
}
}
}
/*====================output========================
省略前面..........
窗口1销售了--票编号:9926
窗口6销售了--票编号:9999
窗口0销售了--票编号:9992
Exception in thread "窗口5" java.lang.ArrayIndexOutOfBoundsException: -1
at java.util.ArrayList.remove(ArrayList.java:501)
at TicketSeller.TicketSeller1.lambda$main$0(TicketSeller1.java:29)
at java.lang.Thread.run(Thread.java:745)
*/
上面的代码通过ArrayList实现票的add及remove。可以看到,执行结果出现了数组越界。因为上面的程序并未实现同步,会出现重复销售和超量销售。出现问题的关键语句在于tickets.size()>0和tickets.remove(0)不是原子性的。
Case2(使用Vector:问题引入):
package TicketSeller;
import java.util.ArrayList;
import java.util.List;
import java.util.Vector;
import java.util.concurrent.TimeUnit;
public class TicketSeller2 {
static Vector<String> tickets=new Vector<>();
static {
for (int i = 0; i < 1000; i++) {
tickets.add("票编号:"+i);
}
}
public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
new Thread(()->{
while (tickets.size()>0){
//打开try-catch可以看到这个问题
try {
TimeUnit.MILLISECONDS.sleep(10);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(Thread.currentThread().getName()+"销售了--"+tickets.remove(0));
}
},"窗口"+i).start();
}
}
}
/*====================output========================
省略前面。。。。。。。。。。。
窗口6销售了--票编号:994
窗口9销售了--票编号:998
窗口2销售了--票编号:999
Exception in thread "窗口3" Exception in thread "窗口0" Exception in thread "窗口4" Exception in thread "窗口7" Exception in thread "窗口5" Exception in thread "窗口1" Exception in thread "窗口8" Exception in thread "窗口6" java.lang.ArrayIndexOutOfBoundsException: Array index out of range: 0
at java.util.Vector.remove(Vector.java:831)
*/
在这个程序示例中,把Case1的ArrayList容器换成了Vector容器。不同点在于:ArrayList里面的remove方法都不是同步的,所以一定会出问题。Vector是一个同步容器,所有的方法都是加锁的。所以上面的代码并不会出错(注释掉try-catch的时候)。但是tickets.size()>0的判断和tickets.remove(0)是分离的。即:size()是原子性的,remove()是原子性的。但是中间的代码并不能保证不被打断,所以问题依旧。打开try-catch可以看到这个问题。
Case3(synchronized实现 ):
package TicketSeller;
import java.util.LinkedList;
import java.util.List;
import java.util.Vector;
import java.util.concurrent.TimeUnit;
public class TicketSeller3 {
static LinkedList<String> tickets=new LinkedList<>();
static {
for (int i = 0; i < 1000; i++) {
tickets.add("票编号:"+i);
}
}
public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
new Thread(()->{
while (tickets.size()>0){
//每次卖票的时候就锁定tickets对象
synchronized (tickets){
if (tickets.size()<=0){
break;
}
try {
TimeUnit.MILLISECONDS.sleep(10);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(Thread.currentThread().getName()+"销售了--"+tickets.remove(0));
}
}
},"窗口"+i).start();
}
}
}
这种实现方法比较传统,就是把对tickets.size()<=0的判断和执行remove一起使用synchronized 加锁,就不会出问题,但是效率太低。
Case4(并发容器实现):
package TicketSeller;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.TimeUnit;
public class TicketSeller4 {
//使用并发容器:链表实现的并发队列,里面是不能装空值的
static Queue<String> tickets=new ConcurrentLinkedQueue<>();
static {
for (int i = 0; i < 1000; i++) {
tickets.add("票编号:"+i);
}
}
public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
new Thread(()->{
while (true){
//往外拿,并且poll是一个同步反方法,拿不到返回空(null)
String s=tickets.poll();
if (s==null){
break;
}else{
System.out.println(Thread.currentThread().getName()+"销售了--"+s);
}
}
},"窗口"+i).start();
}
}
}
这种方式是使用并发容器ConcurrentLinkedQueue(链表实现的并发队列,里面是不能装空值)。上面的代码没有加锁,poll是原子性的,但是判断和操作一起时也不是原子性的,但是不会出问题,效率也比较高(poll底层实现不是加锁的实现),为什么呢?
原因是因为:这个判断并没有对容器里面的数据进行任何操作。只是在容器为null时跳出循环,不会影响容器里面的数据。真正的判断容器不会空并取出元素的操作由poll()直接完成,poll的作用是往外拿数据,并且poll是一个同步的方法,拿不到返回空(null)。更多的并发容器示例见这篇文章。
网友评论