4

インタビューで次の質問がありました。

タスクの固定サイズのキューがあります。スレッドはタスクをエンキューしたいと考えています。キューがいっぱいの場合は、待機する必要があります。スレッドの順序はそのままにしておく必要があります。thread1がtask1に付属し、その後thread2がtask2に付属した場合、task1はtask2の前にキューに入る必要があります。

他のスレッドは、タスクをデキューして実行したいと考えています。キューが空の場合、待機し、順序も維持する必要があります。t3がt4の前に来た場合、t3はt4の前にタスクをエンキューする必要があります。

これを（擬似コードで）達成する方法は？

4

3 に答える 3

0
  1. 簡単な解決策.NET4.0で名前空間が導入されSystem.Collections.Concurrent、そこからのクラスは完全に機能しています-私はそれらからいくつかのエラーを達成できませんでした。
    ConcurrentQueueとBlockingQueueは、調査を開始する場所です。しかし、あなたの質問は標準的な解決策についてではないと思います-それはインタビューでの悪い答えです、それで：

  2. ジェフリー・リッチターの本の情報に基づく解決策：
    ベースコード（C＃）： 

    internal sealed class SynchronizedQueue<T> {
    private readonly Object m_lock = new Object();
    private readonly Queue<T> m_queue = new Queue<T>();

    public void Enqueue(T item) {
        Monitor.Enter(m_lock);
        // After enqueuing an item, wake up any/all waiters
        m_queue.Enqueue(item);
        Monitor.PulseAll(m_lock);
        Monitor.Exit(m_lock);
    }

    public T Dequeue() {
        Monitor.Enter(m_lock);
        // Loop while the queue is empty (the condition)
        while (m_queue.Count == 0)
            Monitor.Wait(m_lock);
        // Dequeue an item from the queue and return it for processing
        T item = m_queue.Dequeue();
        Monitor.Exit(m_lock);
        return item;
    }
}

    このクラスはスレッドセーフですが、それでも順序をチェックしません-そしてこれを実装する多くの方法があります。同じ本から：

    ConcurrentQueueロックConcurrentStackフリーです。Interlockedこれらは両方とも、コレクションを操作するために 内部的 にメソッドを使用します。

    したがって、Monitorクラスの使用法を削除し、アイテムをエンキューする次のスレッドになるようにスレッドをチェックする必要があります。これは、現在の加算器の数 と現在のキューの長さをプライベートフィールドに保持することで実行できます。このフィールドを揮発性にする必要があります。Interlocked.Exchange
    を 使用して現在の加算器を取得し、Interlocked.Readを使用して現在のキューの長さを取得する必要があります。 その後、スレッドに一意の番号（現在の長さ+現在の加算器）があります。SpinWaitを使用する
    現在の長さがあなたの数と等しくならない間にスピンするクラス、そのエンキューアイテムの後、Enqueueメソッドを終了します。

マルチスレッドとロックに関するこの本の章を勉強することを強くお勧めします-あなたはあなたの人生でこのタイプの質問に対してはるかに準備ができているでしょう。また、ここで同様の質問を検索してみてください。例えば：

.NETでブロッキングQueue<T>を作成しますか？

于 2012-11-08T13:21:14.793 に答える
0

有限数のリソースへのアクセスを同期するには、通常、セマフォを使用します。あなた自身のアイデアを得るためにそれのためのグーグル。

難しいのは、ブロッキングスレッドの順序を維持することです。

FifoSemaphore私はC＃に含まれているこのプロジェクトを見つけました：http： //dcutilities.codeplex.com

于 2012-11-08T10:09:14.253 に答える
0

プロデューサースレッドがnumEmptySpacesキューへのアクセスをセマフォで待機している場合、セマフォ待機キューをFIFO以外に実装するのは不合理であるため、この動作はおそらく発生しますが、ほとんどのセマフォ実装では保証されません。

「スレッドの順序」の要件を定義するのは難しいため、この種の動作を保証することは非常に厄介です。

どのスレッドが最初に到着したかをどのように定義できますか？

「最初のスレッド」が他のスレッドの進行を妨げる何らかのロックを取得した場合、後続のスレッドは「すぐに」群れになるため、OSによって提供されるロックキューの順序に従います。

私が考えることができる唯一のことは、何かをロック/キューに入れる前に、すべてのプロデューサースレッドにロックフリーのタイムスタンプまたはシーケンス番号を取得させることです。これは、「通常の」アトミックインクリメント命令で実行できます。その後、プロデューサーが「numEmptySpaces」ユニットを取得して「入り」、キューをロックすると、プロデューサーはシーケンス番号順に自分自身をキューにエンキューできます。

これに標準BlockingCollectionを使用できるかどうかはわかりません。シーケンス番号でエントリを「OrderBy」できる場合がありますが、この操作でキューがロックされるかどうかはわかりません。ロックする必要がありますが、..さらに、sequenceNoをBlockingCollectionのプライベートメンバーとして追加する必要があります。子孫とアトミックインクリメントの結果は、各タスクの状態として維持されますTask。メンバーに追加する必要があります。

BlockingQueuenumEmptySpacesユニットとキューミューテックスが取得されたら、「通常の」キューを使用して独自のクラスでビルドし、セマフォとミューテックスを組み合わせてこれを実装し、新しいタスクをシーケンス番号順にキューに挿入したいと思います。次に、アトミックインクリメントの結果をスタック/自動変数にアセンブルできます。

これはインタビューの質問として正当化されるかもしれませんが、実際に本番コードに実装するには、解雇の脅威にさらされる必要があります。それが不可欠かもしれない状況を考えるのは非常に難しいです。余分なオーバーヘッドと競合の欠点は、私が考えることができるすべての点で疑わしい利点を上回ります。

デキュー/実行の最後に、あらゆる種類の順序を明示的に維持しようとすることについて、同様の予約があります。デキューされたタスクのいくつかの「チェックポイント」がシーケンス番号順に到達したことを確認するのは面倒です。タスクからの協力が必要であり、チェックポイントに到達したときに信号を送るためにプライベートシンクロオブジェクトメンバーが必要になります。絶対に試さないでください:)

于 2012-11-08T10:17:25.263 に答える