在C#中实现阻塞队列

本文关键字:队列 实现 | 更新日期: 2023-09-27 18:25:48

我使用以下代码来实现和测试阻塞队列。我通过启动5个并发线程(remover)从队列中提取项目来测试队列,如果队列是空的,则进行阻塞,并启动1个并行线程(adder)向队列中间歇性添加项目。但是,如果我让它运行足够长的时间,我会得到一个异常,因为即使队列为空,其中一个移除线程也会退出等待状态。

有人知道我为什么会例外吗?注意,我很想知道为什么这与一个有效的解决方案(因为我可以用谷歌搜索)相比不起作用。

我非常感谢你的帮助。

using System;
using System.Threading;
using System.Collections.Generic;
namespace Code
{
    class Queue<T>
    {
        private List<T> q = new List<T>();
        public void Add(T item)
        {
            lock (q)
            {
                q.Add(item);
                if (q.Count == 1)
                {
                    Monitor.Pulse(q);
                }
            }
        }
        public T Remove()
        {
            lock (q)
            {
                if (q.Count == 0)
                {
                    Monitor.Wait(q);
                }
                T item = q[q.Count - 1];
                q.RemoveAt(q.Count - 1);
                return item;
            }
        }
    }
    class Program
    {
        static Random r = new Random();
        static Queue<int> q = new Queue<int>();
        static int count = 1;
        static void Adder()
        {
            while (true)
            {
                Thread.Sleep(1000 * ((r.Next() % 5) + 1));
                Console.WriteLine("Will try to add");
                q.Add(count++);
            }
        }
        static void Remover()
        {
            while (true)
            {
                Thread.Sleep(1000 * ((r.Next() % 5) + 1));
                Console.WriteLine("Will try to remove");
                int item = q.Remove();
                Console.WriteLine("Removed " + item);
            }
        }
        static void Main(string[] args)
        {
            Console.WriteLine("Test");
            for (int i = 0; i < 5; i++)
            {
                Thread remover = new Thread(Remover);
                remover.Start();
            }
            Thread adder = new Thread(Adder);
            adder.Start();
        }
    }
}

在C#中实现阻塞队列

如果我让它运行足够长的时间,我会得到一个异常,因为即使队列为空,其中一个移除线程也会退出等待状态。有人知道我为什么会例外吗?

这个问题很奇怪,因为很明显你知道答案:你的第一句话回答了第二句话提出的问题您会得到异常,因为当队列为空时,移除线程会退出等待状态

要解决这个问题,您需要使用循环而不是"if"。正确的代码是:

while(q.Count == 0) Monitor.Wait(q);

不是

if(q.Count == 0) Monitor.Wait(q);

更新:

一位评论者指出,也许你的问题是"在什么情况下,当队列为空时,消费者线程可以获得监视器?"

好吧,你比我们更有能力回答这个问题,因为你是运行程序并查看输出的人。但就在我的脑海中,有一种可能发生的方式:

  • 消费者线程1:等待
  • 消费者线索2:准备就绪
  • Producer线程3:拥有监视器
  • 队列中有一个元素
  • 线程3脉冲
  • 线程1进入就绪状态
  • 线程3放弃监视器
  • 线程2进入监视器
  • 线程2消耗队列中的项目
  • 线程2放弃监视器
  • 线程1进入监视器

现在线程1在监视器中有一个空队列。

一般来说,当你对这类问题进行推理时,你应该把"脉冲"想象成一只鸽子,上面贴着一张纸条。一旦发布,它就与发送者没有联系,如果找不到家,它就会死在荒野中,消息也无法送达。当您Pulse时,您只知道如果有任何线程在等待,那么一个线程将在未来的某个时间移动到就绪状态;您对线程上操作的相对时间一无所知。

如果有1个使用者,您的代码就会工作,但当有更多使用者时,此机制会失败,应该是while(q.Count == 0) Monitor.Wait(q)

以下场景显示if(q.Count == 0) Monitor.Wait(q)何时会失败(与Eric的不同):

  • 消费者1正在等待
  • 生产商已经投入了一个项目并且正在脉动
  • 消费者1已准备就绪
  • 生产者正在解除锁定
  • 消费者2刚进入Remove,幸运并获得锁定
  • 消费者2看到1个商品,没有等待并取出商品
  • 耗电元件2释放锁定
  • 使用者1重新获取锁,但队列为空

正如文件所说的那样:

当调用Pulse的线程释放锁时,就绪队列中的下一个线程(不一定是被脉冲化的线程)将获取锁。

Eric当然是对的;事实是,尽管该准则似乎涵盖了所有的基础;发生异常的事实表明你没有。

竞争条件是在移除器上的Monitor.Wait和加法器上的Monitor.Pulse之间(这会释放锁;但不一定会立即触发等待唤醒并重新获取锁的线程);随后的移除线程可以获取锁并立即跳过

if (q.Count == 0) 
{ 
  Monitor.Wait(q); 
} 

语句,然后直接删除该项目。然后,Pulsed线程醒来,并假设有一个项目仍然存在;但事实并非如此。

解决问题的方法,无论种族状况实际表现如何,正如埃里克所说。

同样,如果你阅读Monitor.Pulse上的示例,你会看到与这里所做的设置类似的设置,但方式略有不同。