生产者 - 消费者线程问题 [英] Producer-consumer threading problem
问题描述
我想要一些关于生产者 -
消费者问题的变体解决方案的反馈。我的前几次尝试偶尔会陷入僵局
;到目前为止，这个似乎没有死锁但是我不能告诉他们这是否可以证明是否正确，如果是，那么它是否可以简化
。
具有无限缓冲容量的通用生产者 - 消费者情况
在 http://docs.python.org/lib/condition-objects.html 。
那种方法假设生产者将无限期地继续生产物品
，否则消费者将永远等待。对于我正在考虑的问题的
扩展要求消费者不仅在有新产品时通知
，而且当
$ b $时b不会有新项目，所以它停止等待。更多
具体来说，我想要一个生成器（或迭代器类）和
遵循通用签名：
def iter_consumed（items ，生产，消费）：
'''''在消费的物品上返回一个迭代器。
：param items：一个可迭代的对象`produce`（）d和
`consage`（）d。
：param产生：一个可调用的`f（item）`产生一个item;
返回
值被忽略。什么生产确切意味着应用 -
具体。
：param消耗：一个可调用的`f（）`消耗之前的
生产物品
并返回消耗的物品。什么是消费确切意味着
特定于应用程序。唯一的假设是，如果`产生'
被称为
`N`次，那么接下来的'N`调用'消耗'将会是
（最终，虽然
不一定立即）返回，即他们不会无限期地阻止
。
'''''' br />
一个简单的方法是序列化问题：首先
产生所有的'N`项，然后正好调用消耗（）N次。
虽然这使解决方案变得微不足道，但至少存在两个
缺点。首先，客户可能需要等待太长时间才能到达第一项
。其次，每次调用生产（）通常需要资源来生成任务，因此随着N的增加，最大资源要求可以任意高。因此，
produce（）和consume（）应该同时运行，使用不变的
，消耗的调用不会超过生成的调用。另外，在'N`调用生产和消费之后，
，也不应该留下
等待。
我粘贴了我的电流 http://codepad.org/FXF2SWmg 上的解决方案。任何
反馈，特别是如果它与证明或反驳其
正确性有关，将不胜感激。
George
I''d like some feedback on a solution to a variant of the producer-
consumer problem. My first few attempts turned out to deadlock
occasionally; this one seems to be deadlock-free so far but I can''t
tell if it''s provably correct, and if so, whether it can be
simplified.
The generic producer-consumer situation with unlimited buffer capacity
is illustrated at http://docs.python.org/lib/condition-objects.html.
That approach assumes that the producer will keep producing items
indefinitely, otherwise the consumer ends up waiting forever. The
extension to the problem I am considering requires the consumer to be
notified not only when there is a new produced item, but also when
there is not going to be a new item so that it stops waiting. More
specifically, I want a generator (or iterator class) with the
following generic signature:
def iter_consumed(items, produce, consume):
''''''Return an iterator over the consumed items.
:param items: An iterable of objects to be `produce`()d and
`consume`()d.
:param produce: A callable `f(item)` that produces a single item;
the return
value is ignored. What "produce" exactly means is application-
specific.
:param consume: A callable `f()` that consumes a previously
produced item
and returns the consumed item. What "consume" exactly means is
application-specific. The only assumption is that if `produce`
is called
`N` times, then the next `N` calls to `consume` will
(eventually, though
not necessarily immediatelly) return, i.e they will not block
indefinitely.
''''''
One straightforward approach would be to serialize the problem: first
produce all `N` items and then call consume() exactly N times.
Although this makes the solution trivial, there are at least two
shortcomings. First, the client may have to wait too long for the
first item to arrive. Second, each call to produce() typically
requires resources for the produced task, so the maximum resource
requirement can be arbitrarily high as `N` increases. Therefore
produce() and consume() should run concurrently, with the invariant
that the calls to consume are no more than the calls to produce. Also,
after `N` calls to produce and consume, neither should be left
waiting.
I pasted my current solution at http://codepad.org/FXF2SWmg. Any
feedback, especially if it has to do with proving or disproving its
correctness, will be appreciated.
George
推荐答案
George Sakkis写道：
George Sakkis wrote:
我想要一些关于解决方案的反馈意见生产者的变种 -
消费者问题。我的前几次尝试偶尔会陷入僵局
;到目前为止，这个似乎没有死锁但是我不能告诉他们这是否可以证明是否正确，如果是，那么它是否可以简化
。
具有无限缓冲容量的通用生产者 - 消费者情况
在 http://docs.python.org/lib/condition-objects.html 。
那种方法假设生产者将无限期地继续生产物品
，否则消费者将永远等待。对于我正在考虑的问题的
扩展要求消费者不仅在有新产品时通知
，而且当
$ b $时b不会有新项目，所以它停止等待。更多
具体来说，我想要一个生成器（或迭代器类）和
遵循通用签名：
def iter_consumed（items ，生产，消费）：
'''''在消费的物品上返回一个迭代器。
：param items：一个可迭代的对象`produce`（）d和
`consage`（）d。
：param产生：一个可调用的`f（item）`产生一个item;
返回
值被忽略。什么生产确切意味着应用 -
具体。
：param消耗：一个可调用的`f（）`消耗之前的
生产物品
并返回消耗的物品。什么是消费确切意味着
特定于应用程序。唯一的假设是，如果`产生'
被称为
`N`次，那么接下来的'N`调用'消耗'将会是
（最终，虽然
不一定立即）返回，即他们不会无限期地阻止
。
'''''' br />
一个简单的方法是序列化问题：首先
产生所有的'N`项，然后正好调用消耗（）N次。
虽然这使解决方案变得微不足道，但至少存在两个
缺点。首先，客户可能需要等待太长时间才能到达第一项
。其次，每次调用生产（）通常需要资源来生成任务，因此随着N的增加，最大资源要求可以任意高。因此，
produce（）和consume（）应该同时运行，使用不变的
，消耗的调用不会超过生成的调用。另外，在'N`调用生产和消费之后，
，也不应该留下
等待。
我粘贴了我的电流 http://codepad.org/FXF2SWmg 上的解决方案。任何
反馈，特别是如果它与证明或反驳其
正确性有关，将不胜感激。
George
I''d like some feedback on a solution to a variant of the producer-
consumer problem. My first few attempts turned out to deadlock
occasionally; this one seems to be deadlock-free so far but I can''t
tell if it''s provably correct, and if so, whether it can be
simplified.
The generic producer-consumer situation with unlimited buffer capacity
is illustrated at http://docs.python.org/lib/condition-objects.html.
That approach assumes that the producer will keep producing items
indefinitely, otherwise the consumer ends up waiting forever. The
extension to the problem I am considering requires the consumer to be
notified not only when there is a new produced item, but also when
there is not going to be a new item so that it stops waiting. More
specifically, I want a generator (or iterator class) with the
following generic signature:
def iter_consumed(items, produce, consume):
''''''Return an iterator over the consumed items.
:param items: An iterable of objects to be `produce`()d and
`consume`()d.
:param produce: A callable `f(item)` that produces a single item;
the return
value is ignored. What "produce" exactly means is application-
specific.
:param consume: A callable `f()` that consumes a previously
produced item
and returns the consumed item. What "consume" exactly means is
application-specific. The only assumption is that if `produce`
is called
`N` times, then the next `N` calls to `consume` will
(eventually, though
not necessarily immediatelly) return, i.e they will not block
indefinitely.
''''''
One straightforward approach would be to serialize the problem: first
produce all `N` items and then call consume() exactly N times.
Although this makes the solution trivial, there are at least two
shortcomings. First, the client may have to wait too long for the
first item to arrive. Second, each call to produce() typically
requires resources for the produced task, so the maximum resource
requirement can be arbitrarily high as `N` increases. Therefore
produce() and consume() should run concurrently, with the invariant
that the calls to consume are no more than the calls to produce. Also,
after `N` calls to produce and consume, neither should be left
waiting.
I pasted my current solution at http://codepad.org/FXF2SWmg. Any
feedback, especially if it has to do with proving or disproving its
correctness, will be appreciated.
George
我很难理解你究竟是什么问题
试图解决但我很确定你可以用以下两种方法之一来做：
1）使用yield方法将生产者写为生成器，每次调用时都会产生结果
（某事物）像os.walk一样）。我想你可以屈服
如果没有任何消耗可以防止阻塞，那就没有了。
2）Usw想像Twisted insted那样使用回调代替处理
多个异步调用来生成。如果没有什么可以消耗的话，你可能会有回调没有做任何事情（我猜的是一些空对象）。
我不喜欢知道其中任何一个是否有帮助。
-Larry
I had a little trouble understanding what exact problem it is that you are
trying to solve but I''m pretty sure that you can do it with one of two methods:
1) Write the producer as a generator using yield method that yields a result
every time it is called (something like os.walk does). I guess you could yield
None if there wasn''t anything to consume to prevent blocking.
2) Usw somethink like Twisted insted that uses callbacks instead to handle
multiple asynchronous calls to produce. You could have callbacks that don''t do
anything if there is nothing to consume (sort of null objects I guess).
I don''t know if either of these help or not.
-Larry
6月10日，11：47 * pm，Larry Bates< larry.ba ... @ websafe.com`wrote：
On Jun 10, 11:47*pm, Larry Bates <larry.ba...@websafe.com`wrote:
>
我有点理解究竟是什么问题是你想要解决但是我很确定你可以用两种方法中的一种来做到这一点：$ b $ b
>
I had a little trouble understanding what exact problem it is that you are
trying to solve but I''m pretty sure that you can do it with one of two methods:
好吧，让我再试一次不同的例子：我想做的事情可以使用Queue.task_done（）/ Queue.join（）
$ b轻松完成2.5个队列。 $ b（参见 http://docs.python.org/lib上的示例/QueueObjects.html），但是
而不是必须先放置所有项目，然后等到所有项目都是
do ne，一旦完成就得到每个项目。
Ok, let me try again with a different example: I want to do what can
be easily done with 2.5 Queues using Queue.task_done()/Queue.join()
(see example at http://docs.python.org/lib/QueueObjects.html), but
instead of having to first put all items and then wait until all are
done, get each item as soon as it is done.
1）使用yield方法将生产者写为生成器，产生结果
每次调用它（像os.walk那样）。 *我想你可以屈服
如果没有任何东西要消耗以防止阻塞，则无。
1) Write the producer as a generator using yield method that yields a result
every time it is called (something like os.walk does). *I guess you could yield
None if there wasn''t anything to consume to prevent blocking.
实际上，项目的生成方式不是问题的一部分;它可以将
抽象为任意可迭代输入。与所有
iterables一样，没有更多项目。简单地通过
StopIteration进行沟通。
Actually the way items are generated is not part of the problem; it
can be abstracted away as an arbitrary iterable input. As with all
iterables, "there are no more items" is communicated simply by a
StopIteration.
2）像Twisted insted那样使用回调来代替处理
生成多个异步调用。 *如果没有什么可以消费的话，你可能会有回调没有做任何事情（我想是一些空对象）。
2) Usw somethink like Twisted insted that uses callbacks instead to handle
multiple asynchronous calls to produce. *You could have callbacks that don''t do
anything if there is nothing to consume (sort of null objects I guess).
扭曲是有趣且非常强大但需要不同的方式
思考问题并设计解决方案。回到
点，回调通常提供的灵活性和简单的API不如产生结果（消耗的项目）的
迭代器。例如，假设您希望将结果存储到字典中。使用回调，你必须明确地同步每个字典访问
，因为它们可以独立激发。根据定义OTOH和迭代器
按顺序产生项目，因此客户端不必费心同意
。请注意，使用客户端我的意思是API /
框架/库的用户;库本身的实现可能会使用引擎回调（例如将传入的结果放到
队列中），但是将API公开为一个简单的迭代器。 br />
乔治
Twisted is interesting and very powerful but requires a different way
of thinking about the problem and designing a solution. More to the
point, callbacks often provide a less flexible and simple API than an
iterator that yields results (consumed items). For example, say that
you want to store the results to a dictionary. Using callbacks, you
would have to explicitly synchronize each access to the dictionary
since they may fire independently. OTOH an iterator by definition
yields items sequentially, so the client doesn''t have to bother with
synchronization. Note that with "client" I mean the user of an API/
framework/library; the implementation of the library itself may of
course use callbacks under the hood (e.g. to put incoming results to a
Queue) but expose the API as a simple iterator.
George
为什么不使用普通的队列，把虚拟值（如无）放入
你的制作人已经完成了，让主线程在你所有的子线程上使用正常的
Thread.join（）方法？
Why not use a normal Queue, put a dummy value (such as None) in when
you''re producer has finished, and have the main thread use the normal
Thread.join() method on all your child threads?
这篇关于生产者 - 消费者线程问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
