Gráfico de precedencia en el sistema operativo

Requisito previo: el gráfico de precedencia de sincronización de procesos es un gráfico acíclico dirigido que se utiliza para mostrar el nivel de ejecución de varios procesos en el sistema operativo. Se compone de Nodes y aristas. Los Nodes representan los procesos y los bordes representan el flujo de ejecución.

Propiedades del gráfico de precedencia:
Las siguientes son las propiedades del gráfico de precedencia:

• Es un grafo dirigido.
• Es un grafo acíclico.
• Los Nodes del gráfico corresponden a declaraciones individuales del código del programa.
• El borde entre dos Nodes representa el orden de ejecución.
• Un borde dirigido del Node A al Node B muestra que la declaración A se ejecuta primero y luego se ejecuta la declaración B.

Considere el siguiente código:

S1 : a = x + y;
S2 : b = z + 1;
S3 : c = a - b;
S4 : w = c + 1;

Si el código anterior se ejecuta simultáneamente, existen las siguientes relaciones de precedencia:

• c = a – b no se puede ejecutar antes de que se hayan asignado valores a a y b.
• w = c + 1 no se puede ejecutar antes de que se hayan calculado los nuevos valores de c.
• Las declaraciones a = x + y y b = z + 1 podrían ejecutarse simultáneamente.

Ejemplo:
considere las siguientes relaciones de precedencia de un programa:

1. S2 y S3 se pueden ejecutar después de que se complete S1.
2. S4 se puede ejecutar después de que se complete S2.
3. S5 y S6 se pueden ejecutar después de que se complete S4.
4. S7 se puede ejecutar después de que se completen S5, S6 y S3.

Solución: