java - 在 Java 中使用 Thread 进行 ArrayList<object> 操作

Question

我试图在java中结合使用list.add和list.remove来解决有关list.add和list.remove的问题。 假设我们使用 Stack

这是我的堆栈定义类..

import java.util.ArrayList;

public class Stack {

    private int size;
    private int maxSize;

    private final ArrayList<Object> list;

    public Stack(int size) {
        this.size = 0;
        this.maxSize = size;
        this.list = new ArrayList<Object>(size);
    }

    public boolean push(Object o) {
        if (size >= maxSize) {
            return false;
        }

        this.list.add(0, o);
        this.size++;
        return true;
    }

    public Object pop() {
        Object o;
        if (this.size == 0) {
            return null;
        }

        o = this.list.remove(0);
        this.size--;
        return o;
    }

    public int size() {
        return this.size;
    }
}

这是我们如何在 Java 线程中使用堆栈

final Stack stack = new Stack(4);
for(int i = 0; i < 10000; i++) {
    final String data = "hello " + i;
    final int x = i;
    new Thread(new Runnable() {
        public void run() {
            if(x % 2 == 0) {
                System.out.println(stack.push(data));
            } else {
                System.out.println(stack.pop());
            }
        }
    }).start();
}

所以基本上我们只创建 10000 个线程来操作 Stack 对象。 stack.push 结果 True(如果堆栈尚未满)或 false(如果堆栈已满) 如果堆栈为空，stack.pop 结果为 null

问题是:上面的 Stack 实现有什么问题以及如何修复它？

到目前为止我的分析是线程如何在java中运行。线程并行运行而不是顺序运行。我尝试执行该程序，有时会弹出异常 IndexOutOfBounds 。如果我的分析是正确的(或接近的)，有没有办法避免异常？也许在 Stack 类中包含一些检查方法？

如果我的分析是错误的，那么上面的实现有什么问题呢？以及如何解决它？

Answer 1

Whats wrong with Stack implementation above

当只有一个线程可以访问堆栈对象时，您的实现效果很好。但如果至少有 2 个线程可以在同一个堆栈上执行弹出和推送操作 - data races可能会发生。 java多线程的主要描述见JSR-133 .

想象一下 pop 方法中的代码的情况:

if (this.size == 0) {
    return null;
}
o = this.list.remove(0);

1. 第一个线程执行 if 条件，大小为 1。

2. 第二个线程执行相同的 if 条件 - 大小仍为 1。

3. 第一个线程尝试从列表中删除索引为 0 的元素 - 成功，大小变为 0。

4. 当大小为 0 时，第二个线程尝试从列表中删除索引为 0 的元素 - 会引发异常。

您需要确保某些事件先于其他事件发生。其中一种方法是同步您的 pop 和 push 方法。通过在方法返回类型之前添加 synchronized 关键字可以轻松完成此操作。

public synchronized boolean push(Object o) {...}

public synchronized Object pop() { ...}

这里，两个方法在同一个对象 - this 上同步。因此，当一个线程通过执行 pop 或 push 获取 this 锁时，其他线程无法进入由同一线程锁定(同步)的代码块或方法这个对象。使用这些方法是完全线程安全的。

如果您使用一些同步集合而不是常规的 ArrayList，您仍然会遇到麻烦，因为您的逻辑取决于 size 变量，并且之前的错误情况仍然有效。如果您需要并发 Stack 实现，可以使用 java.util.concurrent 包中的 LinkedBlockingDeque 类。它还会更加高效，因为将元素添加到 ArrayList 开头的成本非常高。但如果您想自己实现它，只需向 pop 和 push 方法添加同步修饰符，并将列表更改为 LinkedList。