informati

GRAFOS DE PRECEDENCIA

Grafo acíclico orientado cuyos nodos corresponden a
sentencias individuales.

Un arco de un nodo Si al nodo Sj significa que la sentencia
Sj puede ejecutarse sólo cuando ha acabado Si.

Ejemplo:
S1

S3

S2

S4

S5

S6

S7

1.8. APÉNDICE: COMUNICACIÓN Y SINCRONIZACIÓN ENTRE PROCESOS

1

ESPECIFICACIÓN DE LA CONCURRENCIA
Los grafos no se puedenusar en programación.
Necesitamos otras herramientas:

FORK / JOIN

FORK L
Genera dos ejecuciones concurrentes en un programa:
1. Una se inicia en la instrucción siguiente a FORK
2. Otra empieza en la instrucción etiquetada L

JOIN
Permite recombinar varias ejecuciones paralelas en una
sola. La rama que ejecuta primero la instrucción JOIN
termina su ejecución.

Para saber el número deramas que se deben reunir se usa
un parámetro con JOIN (una variable entera no negativa
que se inicializa con el número de ejecuciones paralelas a
reunir).

1.8. APÉNDICE: COMUNICACIÓN Y SINCRONIZACIÓN ENTRE PROCESOS

2

La ejecución de una instrucción JOIN CONT tiene el
siguiente efecto:

CONT := CONT -1;
IF CONT ≠ 0 THEN ;

La instrucción JOIN tiene que ejecutarseindivisiblemente
es decir, la ejecución concurrente de dos instrucciones
JOIN es equivalente a la ejecución secuencial en un orden
indeterminado.

1.8. APÉNDICE: COMUNICACIÓN Y SINCRONIZACIÓN ENTRE PROCESOS

3

EJEMPLO:

S1

Implementar, usando

S2

FORK/JOIN, el grafo de

S4

precedencia de la figura.

S5

S3

S6

S7

S1;
CONT := 3;
FORK L1;
S2;
S4;
FORK L2;
S5;
GOTO L3;L2: S6;
GOTO L3;
L1: S3;
L3: JOIN CONT;
S7;

1.8. APÉNDICE: COMUNICACIÓN Y SINCRONIZACIÓN ENTRE PROCESOS

4

COBEGIN / COEND

Es de mayor nivel que la pareja FORK/JOIN y tiene la
forma siguiente:

COBEGIN

S0

S1;
S2;

S1

S2

...

Sn

...
Sn;
Sn+1

COEND;

Todas las instrucciones insertadas entre las palabras clave
COBEGIN y COEND se ejecutaránconcurrentemente.

1.8. APÉNDICE: COMUNICACIÓN Y SINCRONIZACIÓN ENTRE PROCESOS

5

EJEMPLO:

S1

Implementar, usando

S3

S2

COBEGIN/COEND,
S4

el grafo de precedencia
de la figura adjunta.

S5

S6

S7

S1;
COBEGIN
S3;
BEGIN
S2;
S4;
COBEGIN
S5;
S6;
COEND
END
COEND;
S7;

1.8. APÉNDICE: COMUNICACIÓN Y SINCRONIZACIÓN ENTRE PROCESOS

6

COMPARATIVA
• La instrucciónconcurrente (COBEGIN/COEND) se
añade fácilmente a un lenguaje de alto nivel.
• No es capaz de reflejar todos los grafos de precedencia.
S1
S3

S2

S4

S5

S6

S7

• Para modelar grafos, FORK/JOIN es más potente. Con
ella se puede simular COBEGIN/COEND.
• El inconveniente de FORK/JOIN es su estructura de
control difícil de usar (semejante a GOTO).
• Aunque la instrucciónconcurrente no basta por sí misma
para implementar todos los gráficos,
otros mecanismos para que así sea (

1.8. APÉNDICE: COMUNICACIÓN Y SINCRONIZACIÓN ENTRE PROCESOS

7

Implementación de COBEGIN/COEND con FORK/JOIN
COBEGIN
S1;
S2;
....
Sn;
COEND;

CONT := n;
FORK L2;
FORK L3;
...
FORK Ln;
S1;
GOTO L1;
L2: S2;
GOTO L1;
L3: S3;
GOTO L1;
...
Ln: Sn;
L1: JOIN CONT;
1.8.APÉNDICE: COMUNICACIÓN Y SINCRONIZACIÓN ENTRE PROCESOS

8

EJERCICIO:
Dada la expresión (A + B) * (C + D) - (E/F)
Establecer el grafo correspondiente que extraiga el
máximo grado de paralelismo e implementar dicho grafo
utilizando:

A) La pareja COBEGIN/COEND

B) La construcción FORK/JOIN

1.8. APÉNDICE: COMUNICACIÓN Y SINCRONIZACIÓN ENTRE PROCESOS

9

EL PROBLEMA DE LA SECCIÓNCRÍTICA

Problema de la exclusión mutua:
Acceso exclusivo a determinados recursos (físicos o
lógicos). Para garantizar el acceso exclusivo a un recurso
hay que garantizar el acceso exclusivo a las instrucciones
que lo manejan.

Existen trayectos en los que el resultado final de la
ejecución de los procesos puede ser distinto en función del
orden en que se lleven a cabo.

El problema de...