在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();
}
}
}
如果我让它运行足够长的时间,我会得到一个异常,因为即使队列为空,其中一个移除线程也会退出等待状态。有人知道我为什么会例外吗?
这个问题很奇怪,因为很明显你知道答案:你的第一句话回答了第二句话提出的问题您会得到异常,因为当队列为空时,移除线程会退出等待状态
要解决这个问题,您需要使用循环而不是"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);
}
语句,然后直接删除该项目。然后,Pulse
d线程醒来,并假设有一个项目仍然存在;但事实并非如此。
解决问题的方法,无论种族状况实际表现如何,正如埃里克所说。
同样,如果你阅读Monitor.Pulse
上的示例,你会看到与这里所做的设置类似的设置,但方式略有不同。