граф приоритетов с семафорами

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 рассмотрим примитивы семафораsignal () и wait () и рассмотрим этот график (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)

@ Жан-Бернар. Я понимаю, поэтому, если я правильно понял концепцию в этом примере, где должны рассматриваться «пунктирные» ребраво взаимном исключениито есть обычный семафор реализует также мьютекс)

поэтому

я должен удалить:

(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 один раз, затем 2 должно произойти, прежде чем вы сможете повторить 1, также для 3 и 6.)

1, затем появляется как результат на уровне 2, потому что самый длинный путь, ведущий к 2, имеет длину 2: не требуется дополнительного семафора для 2-> 1
примечание: это не означает, что 1 появляется как предварительное условие для уровня 3, это соответствует определениям, которые я дал, но предыдущий пример имел соответствие предварительных требований с результатами, что было просто совпадением, поэтому я подумал: Я бы указал на это.

Теперь у вас также есть путь из 6-> 1 для рассмотрения. Этот путь имеет длину 4 от источника и еще не исследован. Поэтому ему нужен дополнительный семафор, так как это означает, что у нас есть 4-й уровень. Этот 4-й уровень - просто семафор из 6-> 1, потому что это единственные неисследованные 4 пути длины. Как только край пройден, вы можете игнорировать его с этого момента.

Так что создание циклического графа не делает его намного сложнее. Вещи все еще находятся на «уровнях» и не могут появиться в результате или требовать более одного уровня. Единственное, что нам нужно принять во внимание, что раньше нам не нужно, это то, что после прохождения ребра вы игнорируете его, это позволяет избежать бесконечных циклов с циклическим графом, и это просто не было необходимо ранее.

Answer 2

У меня возникли проблемы с уловкой вашего точного значения, но я думаю, что большая часть того, что вы хотите здесь, это топологическая сортировка .