實現只有n個線程訪問的隊列 - 休息應該排隊

Question

在最近的一次採訪中，我被要求實現一個Queue，它允許一次僅訪問四個線程。任何請求訪問的進一步線程都應該排隊，並且應該根據它們排隊的順序給予訪問優先級。我想出了以下Queue的實現，但是無法想出代碼的多線程部分。

public class Queue<Item> implements Iterable<Item> { 
    private int N;    // number of elements on queue 
    private Node<Item> first; // beginning of queue 
    private Node<Item> last;  // end of queue 

    private static class Node<Item> { 
     private Item item; 
     private Node<Item> next; 
    } 

    public Queue() { 
     first = null; 
     last = null; 
     N = 0; 
    } 

    public boolean isEmpty() { 
     return first == null; 
    } 

    public int size() { 
     return N;  
    } 

    public Item peek() { 
     if (isEmpty()) throw new NoSuchElementException("Queue underflow"); 
     return first.item; 
    } 

    public void enqueue(Item item) { 
     Node<Item> oldlast = last; 
     last = new Node<Item>(); 
     last.item = item; 
     last.next = null; 
     if (isEmpty()) first = last; 
     else   oldlast.next = last; 
     N++; 
    } 

    public Item dequeue() { 
     if (isEmpty()) throw new NoSuchElementException("Queue underflow"); 
     Item item = first.item; 
     first = first.next; 
     N--; 
     if (isEmpty()) last = null; 
     return item; 
    } 
} 

如何保證一次只能訪問隊列中的n線程？

此外，請建議一些好的讀取，它們有這些問題，以便我可以在Java的多線程部分工作。

Answer 1

使用信號量。您可以用號碼（許可證）n啓動信號量並獲取以訪問隊列。如果所有許可證都被佔用，獲取將會阻止。

http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/Semaphore.html

信號量限制線程獲取資源的數量。已經擁有資源的線程可以再次獲取它。因此信號量在內部維護線程標識。

在您的方案中，每個隊列方法都應獲取許可證並在方法結束時釋放它。

即使兩個流氓線程繞過它們之間的隊列對象，信號量通過跟蹤線程標識來幫助維護許可。

Answer 2

被某個線程調用意味着您通過Thread.currentThread()引用該線程。你永遠無法阻止線程調用你，但是你可以通過使用來阻止的線程，通過限制從這個調用返回的不同Thread對象的數量爲4，當然你需要一種線程安全的方式來檢查那。

這裏有一種方法：

private Set<Thread> threads = new HashSet<>(); 

private synchronized void checkOk() { 
    if (threads.size() < 4) { 
     threads.add(Thread.currentThread()); 
    } else { 
     if (!threads.contains(Thread.currentThread())) 
      throw new IllegalStateException(); 
    } 
} 

然後調用方法添加到每個公共方法是這樣的：

public Item peek() { 
    checkOk(); 
    if (isEmpty()) throw new NoSuchElementException("Queue underflow"); 
    return first.item; 
}