PDF de programación - Programación concurrente - Master de Computación - I Conceptos y recursos para la programación concurrente

Programación concurrente

Master de Computación

I Conceptos y recursos para la programación concurrente:
I.4 Patologías de las aplicaciones concurrentes.

J.M. Drake
M. Aldea

Patologías de los programas concurrentes

• Seguridad y vivacidad

•

Interbloqueos

ProCon’12: I.4- Patologías en aplicaciones concurrentes J.M. Drake, M. Aldea

2

Patologías de los programas concurrentes

• Las patologías características de los programas concurrentes

se pueden clasificar en uno de los dos tipos siguientes:
 Propiedades de seguridad: No se debe ejecutar algo que conduzca a

un error:

Entra en una sección crítica cuando está otro proceso.
Un proceso no respeta un punto de sincronismo.
Uno o varios procesos permanecen a la espera de un evento que nunca se

producirá (interbloqueo).

 Propiedades de vivacidad: Las sentencias que se ejecuten deben
contribuir a un avance constructivo hacia el objetivo del programa:

Bloqueos activos: Dos procesos ejecutan sentencias que no hacen avanzar

al programa.

Aplazamiento indefinido: Un programa se queda sin tiempo de

procesador para avanzar.

Interbloqueo (también se considera un fallo de vivacidad)

ProCon’12: I.4- Patologías en aplicaciones concurrentes J.M. Drake, M. Aldea

3

Características de las patologías

• Un programa concurrente correcto no debe presentar ninguna

patología.

• Las mejoras en seguridad y vivacidad suelen tener efectos

contrapuestos:
 La práctica de la ingeniería software pone énfasis en el diseño de la

seguridad. Se asegura que el código no hace nada imprevisto o
peligroso.

 El mayor tiempo en el diseño de una aplicación concurrente se emplea

en aspectos relacionados con la vivacidad. Evitar bloqueos,
incrementar el rendimientos, etc.

ProCon’12: I.4- Patologías en aplicaciones concurrentes J.M. Drake, M. Aldea

4

Seguridad en sistemas concurrentes

• Las prácticas seguras de programación concurrente son

generalizaciones de las reglas de programación secuencial segura.

• La seguridad en los programas concurrentes tiene un componente de

carrera temporal específico: Hay que garantizar que sólo se acceda a los
objetos cuando tienen un estado coherente (consistente):
 Un objeto es coherente si satisface todos los invariantes entre su atributos

que son inherentes a su naturaleza.

 En los programas concurrentes se deben especificar todos los invariantes
que caracterizan cada objeto. El diseño debe garantizar que se satisfacen
cuando se accede a ellos.

• Fallos de seguridad son los conflictos de lectura/escritura a bajo nivel:
 Conflicto de lectura/escritura: Un thread no puede escribir un nuevo valor

en un atributo, mientras otro thread lo está leyendo.

 Conflicto de escritura/escritura: Dos threads concurrentes no pueden

escribir un mismo atributo.

ProCon’12: I.4- Patologías en aplicaciones concurrentes J.M. Drake, M. Aldea

5

Vivacidad y sistemas concurrentes

• En un programa concurrente hay muchas causas (aceptables)

por las que un thread en estado activo, no se ejecuta:
 Bloqueo: La ejecución se suspende porque se requiere un recurso que

está siendo utilizado por otro thread.

 Espera: La ejecución se suspende a la espera de un evento, bien de

temporización o bien procedente de otro thread.

 Entrada: La ejecución se suspende en espera de un evento de entrada

o salida

 Expulsión: Se interrumpe la ejecución porque otro thread de mayor

prioridad pasa a ser ejecutando en el procesador.

 Fallo: Se suspende porque se ha producido una excepción en el propio

thread.

ProCon’12: I.4- Patologías en aplicaciones concurrentes J.M. Drake, M. Aldea

6

Fallos de vivacidad

• Una falta temporal de ejecución es normal y aceptable. Sin embargo una falta

permanente o ilimitada de ejecución es un fallo de vivacidad:
 Interbloqueo: Dependencia circular entre threads, en el que cada uno requiere

para ejecutarse un recurso que posee el otro.

 Perdida de señales: Un thread permanece inactivo porque comenzó a esperar a

un evento después de que el evento se haya producido.
 Fallo continuado: Una actividad falla repetidamente.
 Inanición: La CPU que tiene que ejecutar el thread está permanente ocupada por

la ejecución de otros threads con mayor prioridad de ejecución.

 Falta de recursos: El sistema no dispone de los recursos que necesitan los

threads para su ejecución.

 Fallo distribuido: El thread requiere para ejecutarse el acceso a una maquina

remota que no está accesible.

 Inversión de prioridad no acotada: Un thread de alta prioridad a la espera de
un recurso debe esperar por threads de prioridad menor que no utilizan el recurso

ProCon’12: I.4- Patologías en aplicaciones concurrentes J.M. Drake, M. Aldea

7

Interbloqueos

• Los interbloqueos están relacionados con la reserva no

ordenada de recursos a los que se accede en exclusión mutua.

• Ejemplo:

 Los procesos P1 y P2 utilizan los recursos RA y RB.
 El proceso P1 toma RA y es expulsado de la CPU por P2.
 El proceso P2 toma RB y queda a la espera de RA.
 El proceso P1 trata de tomar RA queda a la espera.
 Los procesos P1 y P2 permanecen indefinidamente bloqueados.

Proceso 1

?

?

Proceso 2

Recurso A

Recurso B

ProCon’12: I.4- Patologías en aplicaciones concurrentes J.M. Drake, M. Aldea

8

Condiciones bajo las que hay bloqueos.

• Para que un interbloqueo pueda ocurrir, se requiere que se

produzcan simultáneamente estas condiciones
 Los procesos utilizan recursos bajo régimen de exclusión mutua.
 Los procesos mantienen reservados los recursos tomados

mientras esperan los otros recursos que necesitan.

 No existe capacidad de despojar a los procesos de los recursos

ya tomados.

 Existe una cadena circular de requerimientos y reservas que

conducen al interbloqueo.

ProCon’12: I.4- Patologías en aplicaciones concurrentes J.M. Drake, M. Aldea

9

Condiciones con las que eludir los interbloqueos.

• Cuando las condiciones de interbloqueos se pueden presentar

los bloqueos se pueden eludir con la siguientes estrategias:
 Puede establecerse que si un thread se bloquea por falta de un
recurso, libere todos los que tenía tomados en espera del que
falta.

 Puede establecerse que los threads tomen en bloque todos los

recursos que necesitan.

 Se puede evitar que ejecute un thread que pudiera tomar un

recurso que pudiera conducir a un interbloqueo

 El controlador puede tener capacidad de retirar la cesión de los

recursos asignados a los procesos bloqueados.

 Puede establecerse un orden de reserva de recursos que haga

imposible las dependencias circulares.

ProCon’12: I.4- Patologías en aplicaciones concurrentes J.M. Drake, M. Aldea

10

Grafo de reserva de recursos

• Es un grafo orientado que representa el estado de asignación y

requerimiento de recursos por parte de los procesos de una aplicación:
 Nudos: Existe un nudo en el grafo por cada proceso y por cada recurso de

la aplicación.

 Arcos:

Cuando un recurso está asignado a un proceso se establece un arco (continuo)

del nudo que representa el recurso al nudo que representa al proceso.
Cuando un proceso tiene requerido un recurso se establece un arco

(discontinuo) del nudo que representa el proceso al nudo que representa el
recurso.

 Cuando un recurso tiene varias replicas, se introducen tantos puntos como
replicas tenga. Cada una de ellas puede ser asignada independientemente.

R1

P

R2

ProCon’12: I.4- Patologías en aplicaciones concurrentes J.M. Drake, M. Aldea

12

Métodos de detección de recursos.

Grafo de reserva de recursos.

R1 asignado a P1

P1

R1

P1 espera
acceder a R2

R2

P1 espera
acceder a R2

P2

R1 asignado a P1

ProCon’12: I.4- Patologías en aplicaciones concurrentes J.M. Drake, M. Aldea

13

Ejemplos de grafos de asignación de recursos

P1

P2

R3

R2

b) Situación de bloqueo

R2 es asignado

a P1

R1

R2 es asignado

a P2

R1

P1

P2

R3

R2

c) Situación de no bloqueo

P1

P2

R3

R2

R1

a) A la espera de asignación

ProCon’12: I.4- Patologías en aplicaciones concurrentes J.M. Drake, M. Aldea

14

Ejemplos con recursos con replicas

P1

P2

R3

R2

P3

R1

(aunque hay bucle, no hay bloqueo

P1

P2

R3

R2

R1

(Hay bucle, y hay bloqueo

ProCon’12: I.4- Patologías en aplicaciones concurrentes J.M. Drake, M. Aldea

15

Estructura de datos para la gestión de grafos de asignación.

R4

P1

P3

R3

R2

P2

R1

R

12112

R: Recursos del sistema

R

01101
00011
01000
00000

R

10010
10100
10000
10101

R

P

P

R5

P4

A: Matriz de asignación

B: Matriz de
requerimientos

10000

V: Recursos disponibles

ProCon’12: I.4- Patologías en aplicaciones concurrentes J.M. Drake, M. Aldea

16

Un algoritmo para detección de bloqueos.

• El objetivo del algoritmo es buscar los procesos que no son parte de un

bloqueo.

ProCon’12: I.4- Patologías en aplicaciones concurrentes J.M. Drake, M. Aldea

17

Un algoritmo para detección de bloqueos.

• Se marcan todas las filas de la matriz de asignación A nulas.

 obvio, puesto que un proceso que no tiene asignados recursos no puede

ser parte de un bloqueo.

• Se genera el vector de trabajo W y se inicializa al vector V de

recursos disponibles.

• Se busca un proceso i, que corresponda a una fila de A que no

este marcada, y que satisfaga que Bi<=W
 Si no existe tal proceso se termina la búsqueda.
 Si existe se marca la fila i de la matriz A y se revalua W=W+Ai

• Se vuelve al punto anterior
• Los bloqueos que existan corresponden a los procesos que

corresponden a las filas de la matriz A que no están marcadas

ProCon’12: I.4- Patologías en aplicaciones concurrentes J.M. Drake, M. Aldea

18

Criterios de arbitrar un bloqueo.

• Detectado un bloqueo:

 Abortar todos los procesos afectados por el bloqueo.
 Abortar de uno en uno, los procesos que intervienen en el