阻塞队列实现

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 --它不是线程安全的。因此，即使获得了适当的许可证，remove()对LinkedList的操作也会(而且会)造成麻烦。这里有一个简单的“测试用例”来显示这种行为：

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());
    });

输出将类似于(您将看到由于null方法上的NoSuchElementExceptions而产生的remove s)：

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

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