带信号量的优先图

Question

好的，考虑到这个图必须用最少的信号量来实现，我想知道什么时候一条边被认为是冗余的，应该被移除，在我的例子中，从(2)到(5)的边是否可以被认为是冗余的(为什么)我还必须指定这个图不是循环的，并且不能使用construct coend结构

所以我的困境围绕着冗余边，因为它修改了我的解决方案，直到现在我认为(2)-(5)可以保留，我将按以下顺序划分信号量：

s1 (from 1 to 2 , 3 and 5)
s2 (from 2 and 3 to 4)
s3 (from 1 , 2 and 3 to 5)
s4 (from 3 , 4 and 5 to 6)

​

​

@karmastan考虑信号量原语signal()和wait()，并考虑这个图(1)--s1-->(2)，因此要到达(2)，您应该在从(1)到(2)的边缘使用信号量"s1“，并且必须首先执行(1)，因此代码将类似于

1 :                                          2:
do (1)                                       wait(s1)   //waits for the signal from 1
signal(s1)//1 has finished                   do (2)

@Jean-Bernard我理解，所以如果我在这个例子中得到了正确的概念，其中“点”边将在互斥中被考虑(除了通常的信号量实现也是一个互斥)

​

​

因此

我应该删除：

(1)---->(6) //because it's a "cross" edge
(3)---->(6) // also because it's a "cross" and excludes (3)--->(5)

然后我将有6个信号量和一个互斥锁

s1 (from 1 to 2)
s2 (from 1 to 3)
s3 (from 1 to 4)

s4 (from 2 and 3 to 5)
s5 (from 4 and 5 to 6)
s6 (from 6 to 1)

mutex(between 2 and 4) 

Answer 1

1个-> 2和3

2和3 -> 4和5

4和5 -> 6

最长的路径是3，所以它应该可以用3个信号量来实现。

顶点应该是信号量的结果，对应于从源到源的最长路径。并且prereqs应该是从可用的最长路径中引出结果的边。

上面的措辞令人困惑，但它的意思是1->5被消除了，因为该边是1级边(来自源)，但5是2级节点(从源到它的最大路径长度为2)。同样的过程消除了3->6。

您不能消除2->5，因为它是通向2级节点的2级路径。如果它是1级路径，或者5是3级节点，那么您可以这样做，因为其他一些信号量已经处理了5的先决条件。

考虑添加了2->1和6->3的边的图。(这意味着您可以执行1一次，然后需要执行2，然后才能重复1，3和6也是如此。)

1，然后作为结果出现在级别2上，因为通向2的最长路径的长度为2:对于2->1不需要额外的信号量

注意：这并不意味着1作为第3级的前提条件出现，这符合我给出的定义，但前面的例子有匹配的前提条件和结果，这只是巧合，所以我想我应该指出它。

现在，您还需要考虑从6到>1的路径。此路径的长度为从源代码算起的长度为4，并且尚未探索。所以它需要一个额外的信号量，因为它意味着我们有一个第四级。这第四层仅仅是6->1的信号量，因为这些是唯一未探索的长度为4的路径。一旦遍历了一条边，您就可以从该点开始忽略它。

因此，创建一个循环图并不会让它变得更难。事情仍然在“级别”上，并且不能作为结果或先决条件出现在超过一个级别。我们需要考虑的唯一一件事是，一旦遍历了一条边，你就会忽略它，这就避免了循环图的无限循环，这在以前是不必要的。

Answer 2

我在理解您的确切含义时遇到了一些困难，但我认为您在这里想要的很大一部分是topological sorting。