4

我在一次采访中被问到以下问题：

有一个固定大小的任务队列。线程想要将任务排入队列。如果队列已满，他们应该等待。线程顺序应该保持：如果thread1与task1一起出现，并且在thread2与task2一起出现之后，task1应该在task2之前进入队列。

其他线程想要使任务出列并执行它。如果队列是空的，他们应该等待，并且他们的顺序应该保持：如果 t3 在 t4 之前，t3 应该在 t4 之前入队。

如何实现这一点（在伪代码中）？

4

3 回答 3

0
  1. 简单的解决方案在 .NET 4.0 中引入了 namespace System.Collections.Concurrent，其中的类工作得很好——我无法从它们那里得到一些错误。
    ConcurrentQueue和BlockingQueue是您开始研究的地方。但我认为你的问题与标准解决方案无关——这在面试中回答不好，所以：

  2. 基于Jeffrey Richter 书籍资料的解决方案：
    基础代码（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类使用，并为您的线程提供检查以成为下一个排队项目。这可以通过在私有字段中维护当前加法器的数量 和当前队列长度来完成。您应该将此字段设置为volatile。
    您应该使用Interlocked.Exchange获取您当前的加法器并使用Interlocked.Read获取您当前的队列长度。
    之后，您的线程具有唯一编号 -当前长度 + 当前加法器。使用SpinWait类旋转，而当前长度将不等于您的数字，在该入队项之后，并离开入队方法。

我强烈建议你学习这本书关于多线程和锁的章节——你会在你的生活中为这类问题做好准备。也尝试在这里搜索类似的问题。例如：

在 .NET 中创建阻塞队列<T>？

于 2012-11-08T13:21:14.793 回答
0

要同步对有限数量资源的访问，您通常使用信号量。谷歌让它得到你自己的想法。

困难的部分是保持阻塞线程的顺序。

FifoSemaphore我发现这个项目在 C#中包含一个：http: //dcutilities.codeplex.com

于 2012-11-08T10:09:14.253 回答
0

如果生产者线程正在等待numEmptySpaces信号量以访问队列，那么这种行为可能无论如何都会发生，因为信号量等待队列在 FIFO 以外的任何东西中实现是不合理的，但在大多数信号量实现中并不能保证。

保证这种行为非常尴尬，因为很难定义“线程顺序”的要求：

你如何定义哪个线程先到达？

如果“第一个线程”获得某种阻止其他线程继续执行的锁定，则后续线程“立即”聚集，因此受操作系统提供的任何锁定队列顺序的约束。

我唯一能想到的就是强制每个生产者线程在尝试锁定/排队任何东西之前获取一个无锁时间戳或序列号。这可以通过“正常”原子增量指令来完成。当生产者随后通过获取“numEmptySpaces”单元“进入”并锁定队列时，它可以按序列号顺序将自己排入队列。

我不确定是否BlockingCollection可以为此使用标准。您可能可以按序列号对条目进行“排序”，但我不确定此操作是否会锁定队列 - 它应该这样做，但是.. 此外，必须将 sequenceNo 作为私有成员添加到 BlockingCollection后代和原子增量结果维护为每个任务的状态 - 您必须将其添加到Task成员中。

我很想通过自己的BlockingQueue类构建一个“普通”队列、几个信号量和一个互斥体来实现这一点，一旦获得了 numEmptySpaces 单元和队列互斥体，就将新任务按序列号顺序插入队列中。然后可以将原子增量结果组装到堆栈/自动变量中。

这可能是一个面试问题，但我必须受到解雇的威胁才能在生产代码中实际实现它。很难想到它可能是必要的情况。在我能想到的所有事情中，额外开销和争用的负面影响都超过了可疑的好处。

对于尝试在出队/执行端显式维护任何类型的排序，我有类似的保留意见。尝试确保以序列号顺序到达出队任务中的​​某些“检查点”会很麻烦。它需要来自任务的合作，这需要一个私有同步对象成员在它到达其检查点时发出信号。永远不要尝试:)

于 2012-11-08T10:17:25.263 回答