PDF de programación - GRAFOS DE PRECEDENCIA

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 pueden usar 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 de ramas 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 <TERMINAR RAMA>;

La instrucción JOIN tiene que ejecutarse indivisiblemente
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

S1

S3

S2

S4

S5

S6

S7

EJEMPLO:
Implementar, usando
FORK/JOIN, el grafo de
precedencia de la figura.

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

S1;
S2;
...
Sn;
COEND;

S0

S1

S2

...

Sn

Sn+1

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

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

5

S1

S3

S2

S4

S5

S6

S7

EJEMPLO:
Implementar, usando
COBEGIN/COEND,
el grafo de precedencia
de la figura adjunta.

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ón concurrente (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ón concurrente 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ÓN CRÍ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 la sección crítica está en diseñar un
protocolo que pueda ser usado por los procesos para
cooperar entre sí y que garantice la exclusión mutua de sus
secciones críticas:

SOLICITAR_ACCESO (SECCIÓN_CRÍTICA);

LIBERAR (SECCIÓN_CRÍTICA);

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

10

REQUISITOS DE LAS SOLUCIONES
Una solución al problema de la sección crítica debe
cumplir los tres requisitos siguientes:



1. Exclusión mutua.
Si un proceso Pi se está ejecutando en su sección
crítica, entonces ningún otro proceso se puede estar
ejecutando en la suya.

2. Progresión.
Ningún proceso suspendido fuera de su sección

crítica debe impedir progresar a otros procesos.

3. Espera limitada.
Si un proceso ha solicitado entrar en su SC, debe
haber un límite al número de veces que otros
procesos entren en sus respectivas SC, antes de que
el primero lo consiga.

Se supone que cada proceso se ejecuta a una velocidad no
nula, aunque no se puede asegurar nada sobre las
velocidades relativas de los procesos.

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

11

Al presentar los algoritmos se definen sólo las variables
utilizadas para sincronización.

Cada proceso tendrá la siguiente estructura:

Pi: repeat
...
CÓDIGO DE ENTRADA

SECCIÓN CRÍTICA

CÓDIGO DE SALIDA

SECCIÓN RESIDUAL

until false;

Lo que cambiará de una solución a otra es la forma de
llevar a cabo los recuadros marcados.

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

12

SOLUCIONES PARA DOS PROCESOS

Algoritmo 1

var turno: 0..1;

Pi: repeat

while turno „

i do no-op;

SECCIÓN CRÍTICA

turno := j;

SECCIÓN RESIDUAL

until false;

C Se garantiza la exclusión mutua
D No se garantiza la progresión
D Hay espera improductiva

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

13

Algoritmo 2

var indicador: array [0..1] of boolean;

Pi: repeat

indicador[i] := true;
while indicador[j] do no-op;

SECCIÓN CRÍTICA

indicador[i] := false;

SECCIÓN RESIDUAL

until false;

C Se garantiza la exclusión mutua
D No se garantiza la progresión
D Hay espera improductiva

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

14

Algoritmo 2 (variante)

var indicador: array [0..1] of boolean;

Pi: repeat

while indicador[j] do no-op;
indicador[i] := true;

SECCIÓN CRÍTICA

indicador[i] := false;

SECCIÓN RESIDUAL

until false;

C No se garantiza la exclusión mutua
D Se garantiza la progresión
D Hay espera improductiva

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

15

Algoritmo 3 (Peterson)

var indicador: array [0..1] of boolean;

turno: 0..1;

Pi: repeat

indicador[i] := true;
turno := j;
while (indicador[j] and turno=j) do no-op;

SECCIÓN CRÍTICA

indicador[i] = false;

SECCIÓN RESIDUAL

until false;

C Se garantiza exclusión mutua (ver)
C Se garantiza la progresión
C Se garantiza la espera limitada
D Hay espera improductiva

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

16

SOPORTE HARDWARE PARA SINCRONIZACIÓN

La solución más simple es INHABILITAR/HABILITAR
interrupciones.

Inconvenientes:

• Peligroso en manos del usuario.
• No sirve si se tienen dos o más CPUs.

Existen otras soluciones (software) que requieren algo de
ayuda del hardware. Instrucciones especiales:

• Test-and-Set
• Swap

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

17

Test-and-Set (Evaluar-y-asignar)

Puede definirse (de forma algorítmica) como una función:

function TAS (var objetivo: boolean): boolean;

begin

TAS := objetivo;
objetivo := true;

end;

La característica esencial es que la instrucción se ejecuta
, es decir, como una unidad ininterrumpible

(en un sólo ciclo de memoria).
Si se ejecutan dos TAS simultáneamente
siguiendo algún orden arbitrario.

lo harán

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

18

Solución con Test-and-Set

var cerradura: boolean (:= false);

Pi: repeat

while TAS(cerradura) do no-op;

SECCIÓN CRÍTICA

cerradura := false;

SECCIÓN RESIDUAL

until false;

C Se garantiza la exclusión mutua
C Se garantiza la progresión
D No se garantiza la espera limitada
D Hay espera improductiva

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

19

Swap (Intercambiar)

Puede definirse algorítmicamente como un procedimiento:

procedure SWAP (var a, b: boolean);

var temp: boolean;

begin

temp := a;
a := b;
b := temp;

end;

Como en el caso de la instrucción TAS, la característica
esencial es que la instrucción se ejecuta

.

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

20

Solución con Swap

var cerradura: boolean (:= false);

Pi: var clave: boolean;

repeat

llave := true;

repeat

SWAP(cerradura, llave);

until llave = false;

SECCIÓN CRÍTICA

cerradura := false;

SECCIÓN RESIDUAL

until false;

C Se garantiza la exclusión mutua
C Se garantiza la progresión
D No se garantiza la espera limitada
D Hay espera improductiva

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

21

Algoritmo de Burns (para n procesos)

var esperando: array[0..n-1] of boolean (:= false);

cerradura: boolean (:= false);

Pi: var j: 0..n-1;

llave: boolean;

repeat

esperando[i] := true;
llave := true;
while (esperando[i] and llave) do

llave := TAS(cerradura);

esperando[i] := false;

SECCIÓN CRÍTICA

j := i +1 mod n;
while (j„ i) and (not esperando[j]) do

j := j+1 mod n;

if j=i then cerradura := false

else esperando[j] := false;
SECCIÓN RESIDUAL

until false;

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

22

SEMÁFOROS

Un semáforo es una variable entera protegida que, aparte
de la inicialización, sólo puede ser accedida por medio de
dos operaciones indivisibles estándar:

• P(s)
• V(s)

WAIT(s)

ESPERA(s)

SIGNAL(s)

SEÑAL(s)

Las definiciones clásicas de estas operaciones son:

• WAIT(s):

0 do no-operación;

while s £
s := s - 1;

• SIGNAL(s):

s := s + 1;

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

23

”
”
”
”
USO DE SEMÁFOROS PARA EXCLUSIÓN MUTUA