带信号量的优先图

Question

好吧，所以给出这个图必须用信号量的最小数字 实现，我想知道什么时候边被认为是多余的，应该是 删除，在我的例子中可以从边（2）到（5）被认为是多余的（为什么） 我还必须指定该图不是循环的，并且不能使用cobegin-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 考虑旗语原语信号（）和等待（），并考虑该曲线图（1） - S1 - >（2）因此，以到达（2）应该使用信号量“S1”从边缘（1）（2），您必须首先执行（1），这样的代码会是这样的

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

@让 - 伯纳德 我明白，如果我得到的概念正确，在这个例子中“虚线”边缘 将被考虑在相互排斥中（除了通常的信号量impl EMENT也是一个互斥体）

因此

我应该删除：

(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个信号灯做。
顶点应该是信号量对应于来自源的最长路径的结果。先决条件应该是最长路径的结果。

上述措辞令人困惑，但它意味着1-> 5被淘汰，因为该边缘是1级边缘（来自源），但5是2级节点（具有最大路径从源头到它的长度2）。同样的过程消除了3-> 6。

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

---

考虑你的图表与边缘从2-> 1加和6-> 3。 （这意味着您可以执行1次一次，然后在重复1之前需要发生2次，同样可以进行3次和6次。）

1，则出现作为第2级的结果，因为通向2的最长路径的长度是2：无需其他额外旗语为2-> 1
注：这并不意味着1个出现作为prereq为3级，这符合我给出的定义，但前面的示例具有匹配结果的先决条件，这只是巧合，所以我认为我会指出它。

现在你也有从6-> 1的路径来考虑。这条路径的长度为4，并且尚未探索。所以它需要一个额外的信号量，因为这意味着我们有一个第四级。这个第四级只是一个从6-> 1的信号量，因为那些是唯一未探测的长度4条路径。一旦遍历了一条边，就可以从该点开始忽略它。

因此，使图形循环并不会更难。事情仍然处于“水平”，不能作为结果或先决条件出现在多个层面上。我们需要考虑的唯一事情就是我们之前不需要考虑的是，一旦遍历了一条边，就会忽略它，这样就避免了带有循环图的无限循环，而且之前并不需要。

Answer 2

一些麻烦抓住你的确切含义，但我认为这是很大的一部分你要在这里是topological sorting。