java - 阻塞队列的实现

Question

我刚刚实现了一个带有信号量的自定义阻塞队列。

由于我找不到的原因，当我的队列为空时，我的队列不会被信号量阻塞。

这是我的实现:

package poolThread;

import java.util.LinkedList;
import java.util.Queue;
import java.util.concurrent.Semaphore;

public class MyQueue<E> {
Semaphore s = new Semaphore(0, true);
private Queue<E> queue = new LinkedList<E>(); 


public boolean isEmpty(){
    return this.queue.isEmpty();
}
public void enqueue(E e){
    queue.add(e);
    s.release();
}
public E dequeue(){
    E e = null;
    try {
        s.acquire();
    } catch (InterruptedException e1) {
        // TODO Auto-generated catch block
        e1.printStackTrace();
    }
    e = queue.remove();
    return e;

}

}

你能帮我找出代码中的错误吗？

Answer 1

这里的问题是 LinkedList - 它不是线程安全的。因此，即使正确获取了许可，LinkedList 上的 remove() 操作也可能(并且将会)引起麻烦。这是一个简单的“测试用例”来显示行为:

MyQueue<String> x = new MyQueue<>();

ExecutorService es = Executors.newFixedThreadPool(2);
for (int j = 0; j < 2; j++)
    es.submit(() -> {
        String tn = Thread.currentThread().getName();
        for (int i = 0; i < 2; i++)
            x.enqueue("v" + i);

        for (int i = 0; i < 2; i++) 
            System.out.println(tn + " deq: " + x.dequeue());
    });

输出将类似于(由于 remove 方法上的 NoSuchElementException，您将看到 null):

pool-1-thread-2 deq: v0
pool-1-thread-1 deq: null

最简单的解决方案是将您的 LinkedList 替换为 java.util.concurrent.ConcurrentLinkedQueue。