0

我试图证明以下生产者/消费者问题的解决方案不起作用，通过显示当消费者处于 M1 的开头时，有一种情况是它无法在有限范围内使项目出队时间，和/或存在一种情况，即生产者处于 L2 的开头，并且它无法在有限时间内将项目入队。我只是找不到任何例子来证明这一点。

该算法假设有 10 个生产者，10 个消费者，缓冲区大小为 10。

nf = 0; // counting semaphore, # of items in queue
bm = 1; // binary semaphore, ensures mutex

制片人

L1: Produce(item);
L2: P(bm);
If (queue_is_full) {
  V(bm);
  GoTo L2;
} else {
  Enqueue(item);
  V(bm);
  V(nf);
  GoTo L1;
}

消费者

M1: P(nf);
P(bm);
Dequeue(item);
V(bm);
Consume(item);
GoTo M1;
4

1 回答 1

0

如果我的理解是正确的，P(x) 将锁定直到 x != 0 并且 v(x) 总是执行 x++。

在上面的代码中，M1: P(nf);只有当队列中的项目可用时才会让消费者通过。然后它总是获取并释放 bm 上的锁。所以我很确定代码不会与其他消费者或生产者陷入僵局。

在生产者中它获取 bm 然后对列表进行操作。它不会在 v(bm) 之前获取任何其他锁，并且它在两个分支中都执行 v(bm)，因此它保证会发生。由于 v(bm) 最终会发生，因此消费者最终可以消费一件物品。在 v(bm) 之后，av(nf) 得到保证，因此当生产一件物品时，一个消费者将尝试最终消费它。

因此，除非有像 listcapacity == 0 这样愚蠢的东西，否则代码看起来不错。

如果消费者做了 P(bm)-> P(nf)-> V(bm) 会有问题，但上面的代码看起来不错

于 2013-04-18T03:33:43.667 回答