Отношения предшествования между процессами и развитие процесса в системе.

Состояние системы определяется действиями производимыми процессами, которые могут затребовать захватить и освободить ресурсы. При минимальном аппаратном параллелизме часто полезно рассматривать процессы как протекающие параллельно. Тогда типы отношения предшествования, которые могут возникнуть между процессами, можно представить следующим образом:

Отношения предшествования обозначаются направленной дугой графа. Каждая дуга представляет трассу развития по времени наборов процессов и связано описывает отношение представления процесса. Эти графы обычно называют- графы развития процессов.

Пусть S(a;b) означает последовательную связь процессов a и b, а P(a;b) параллельную связь процессов a и b. Тогда граф развития процесса является правильно вложенным, если он может быть описан средствами S , P или только композицией этих функций. Тогда первые три графа могут быть описаны так:

S (P1, S (P2, S (P3, P4)))-последовательный

P (P1, P (P2, P (P3, P4)))-параллельный

S(P1 , S(P(P2,P(S,(P3,P(P4,P5))P6))P7,P8)))

Общий граф предшествования не является правильно вложенным, так как любое описание сделанное с помощью функциональной композиции должно включать на самом внутреннем уровне выражение в виде S(P_i, P_j) P(P_i,P_j) P_ij = {P_k / n=1,2,3…8}. Связь P не может появиться, так как этот граф не содержит не одного подграфа в этой форме. Все последовательно связанные p_i p_j имеют ещё один процесс P_k который начинается или заканчивается между P_i и P_j но становится недоступным для дальнейшего использования если появляется связь от P_i к P_j, так как тогда связь процесса P_k не может быть описана. Таким образом, S(P_i,P_j) не может быть использована и описание правильно вложенного графа не возможно.