PDF de programación - Administración de procesos: Primitivas de sincronización

Introducción a la concurrencia
Primitivas de sincronización
Patrones basados en semáforos
Problemas clásicos
El problema de inicio

Administración de procesos: Primitivas de

sincronización

Gunnar Wolf

Gunnar Wolf

Administración de procesos: Primitivas de sincronización

Introducción a la concurrencia
Primitivas de sincronización
Patrones basados en semáforos
Problemas clásicos
El problema de inicio

Índice

1

Introducción a la concurrencia

2 Primitivas de sincronización

3 Patrones basados en semáforos

4 Problemas clásicos

5 El problema de inicio

Gunnar Wolf

Administración de procesos: Primitivas de sincronización

Introducción a la concurrencia
Primitivas de sincronización
Patrones basados en semáforos
Problemas clásicos
El problema de inicio

Concurrencia

No tenemos que preocuparnos cuando todos los datos que
maneja un hilo son locales
Al utilizar variables globales o recursos externos, debemos
recordar que el planificador puede interrumpir el flujo en
cualquier momento
No tenemos garantía del ordenamiento que obtendremos

Gunnar Wolf

Administración de procesos: Primitivas de sincronización

Introducción a la concurrencia
Primitivas de sincronización
Patrones basados en semáforos
Problemas clásicos
El problema de inicio

Los problemas de la concurrencia (1)

class EjemploHilos

def initialize

@x = 0

end
def f1

sleep 0.1
print ’+’
@x += 3

end

def f2

sleep 0.1
print ’*’
@x *= 2

end
def run

t1 = Thread.new {f1}
t2 = Thread.new {f2}
sleep 0.1
print ’ %d ’ % @x

end

end

Gunnar Wolf

Administración de procesos: Primitivas de sincronización

Introducción a la concurrencia
Primitivas de sincronización
Patrones basados en semáforos
Problemas clásicos
El problema de inicio

Los problemas de la concurrencia (1)

class EjemploHilos

def initialize

@x = 0

end
def f1

sleep 0.1
print ’+’
@x += 3

end

def f2

sleep 0.1
print ’*’
@x *= 2

end
def run

t1 = Thread.new {f1}
t2 = Thread.new {f2}
sleep 0.1
print ’ %d ’ % @x

end

end

>> e = EjemploHilos.new;10.times{e.run}
0 *+3 *+9 *+21 +*48 *+99 +*204 *+411 +*828 *+1659

>> e = EjemploHilos.new;10.times{e.run}
+0 *+6 *+*18 42 +*+90 **186 +375 +**756 ++1515 *3036

Gunnar Wolf

Administración de procesos: Primitivas de sincronización

Introducción a la concurrencia
Primitivas de sincronización
Patrones basados en semáforos
Problemas clásicos
El problema de inicio

Los problemas de la concurrencia (2)

No son dos hilos compitiendo por el acceso a la variable

Son tres
El jefe también entra en la competencia a la hora de imprimir
A veces, el órden de la ejecución es (¿parece ser?) (@x *2)
+ 3, a veces (@x + 3) * 2

A veces la impresión ocurre en otro órden: +**756 o ++1515

Esto porque tenemos una condición de carrera en el acceso a
la variable compartida

Gunnar Wolf

Administración de procesos: Primitivas de sincronización

Introducción a la concurrencia
Primitivas de sincronización
Patrones basados en semáforos
Problemas clásicos
El problema de inicio

Condición de carrera (Race condition)

Error de programación
Implica a dos procesos (o hilos)
Fallan al comunicarse su estado mutuo
Lleva a resultados inconsistentes

Problema muy común
Difícil de depurar

Ocurre por no considerar la no atomicidad de una operación
Categoría importante de fallos de seguridad

Gunnar Wolf

Administración de procesos: Primitivas de sincronización

Introducción a la concurrencia
Primitivas de sincronización
Patrones basados en semáforos
Problemas clásicos
El problema de inicio

Operación atómica

Operación que tenemos la garantía que se ejecutará o no como
una sóla unidad de ejecución
No implica que el sistema no le retirará el flujo de ejecución

El efecto de que se le retire el flujo no llevará a
comportamiento inconsistente.
Requiere sincronización explícita entre los procesos que la
realicen

Gunnar Wolf

Administración de procesos: Primitivas de sincronización

Introducción a la concurrencia
Primitivas de sincronización
Patrones basados en semáforos
Problemas clásicos
El problema de inicio

Sección crítica

Es el área de código que:

Realiza el acceso (¿modificación? ¿lectura?) de datos
compartidos
Requiere ser protegida de accesos simultáneos
Dicha protección tiene que ser implementada siempre, y
manualmente por el programador

Identificarlas requiere inteligencia

Debe ser protegida empleando mecanismos atómicos

Si no, el problema podría aminorarse — Pero no prevenirse
¡Cuidado con los accesos casi-simultáneos!

Gunnar Wolf

Administración de procesos: Primitivas de sincronización

Introducción a la concurrencia
Primitivas de sincronización
Patrones basados en semáforos
Problemas clásicos
El problema de inicio

Sección crítica

Figura: Sincronización: La exclusión de una sección crítica común a varios
procesos se protege por medio de regiones de exclusión mutua

Gunnar Wolf

Administración de procesos: Primitivas de sincronización

Introducción a la concurrencia
Primitivas de sincronización
Patrones basados en semáforos
Problemas clásicos
El problema de inicio

Bloqueo mutuo

Algunos autores lo presentan como interbloqueo.

En inglés, deadlock

Dos o más procesos poseen determinados recursos
Cada uno de ellos queda detenido esperando a alguno de los
que tiene otro

Gunnar Wolf

Administración de procesos: Primitivas de sincronización

Introducción a la concurrencia
Primitivas de sincronización
Patrones basados en semáforos
Problemas clásicos
El problema de inicio

Bloqueo mutuo

Figura: Esquema clásico de un bloqueo mutuo simple: Los procesos A y B
esperan mutuamente para el acceso a las unidades 1 y 2.

Gunnar Wolf

Administración de procesos: Primitivas de sincronización

Introducción a la concurrencia
Primitivas de sincronización
Patrones basados en semáforos
Problemas clásicos
El problema de inicio

Bloqueo mutuo

El sistema operativo puede seguir procesando normalmente

Pero ninguno de los procesos involucrados puede avanzar
¿Única salida? Que el administrador del sistema interrumpa a
alguno de los procesos

. . . Implica probable pérdida de información

Gunnar Wolf

Administración de procesos: Primitivas de sincronización

Introducción a la concurrencia
Primitivas de sincronización
Patrones basados en semáforos
Problemas clásicos
El problema de inicio

Inanición

En inglés, resource starvation

Situación en que uno o más procesos están atravesando
exitosamente una sección crítica

Pero el flujo no permite que otro proceso, posiblemente de
otra clase, entre a dicha sección

El sistema continúa siendo productivo, pero uno o más de los
procesos puede estar detenido por un tiempo arbitrariamente
largo.

Gunnar Wolf

Administración de procesos: Primitivas de sincronización

Introducción a la concurrencia
Primitivas de sincronización
Patrones basados en semáforos
Problemas clásicos
El problema de inicio

Primer acercamiento: Reservas de autobús

¡Inseguro! ¿Qué hizo el programador bien? ¿qué hizo mal?

use threads::shared;
my ($proximo_asiento :shared, $capacidad :shared, $bloq

:shared);

$capacidad = 40;
sub asigna_asiento {

while ($bloq) { sleep 0.1; }
$bloq = 1;
if ($proximo_asiento < $capacidad) {

$asignado = $proximo_asiento;
$proximo_asiento += 1;
print "Asiento asignado: $asignado\n";

} else {

print "No hay asientos disponibles\n";
$bloq = 0; return 1; # Indicando error / falla

}
$bloq = 0; return 0;

}

Gunnar Wolf

Administración de procesos: Primitivas de sincronización

Introducción a la concurrencia
Primitivas de sincronización
Patrones basados en semáforos
Problemas clásicos
El problema de inicio

¿Por qué es inseguro el ejemplo anterior?

Líneas 5 y 6:

Espera activa (spinlock): Desperdicio de recursos

Aunque esta espera activa lleva dentro un sleep, sigue siendo
espera activa.
Eso hace que el código sea poco considerado — No que sea
inseguro

¿Quién protege a $bloq de modificaciones no-atómicas?

Gunnar Wolf

Administración de procesos: Primitivas de sincronización

Introducción a la concurrencia
Primitivas de sincronización
Patrones basados en semáforos
Problemas clásicos
El problema de inicio

Las secciones críticas deben protegerse a otro nivel

Las primitivas que empleemos para sincronización deben ser
atómicas
La única forma de asegurar su atomicidad es implementándolas
a un nivel más bajo que el del código que deben proteger

(Al menos) el proceso debe implementar la protección entre
hilos
(Al menos) el sistema operativo debe implementar la
protección entre procesos

Gunnar Wolf

Administración de procesos: Primitivas de sincronización

Introducción a la concurrencia
Primitivas de sincronización
Patrones basados en semáforos
Problemas clásicos
El problema de inicio

Mismo ejemplo, empleando un candado (mutex)

use threads::shared;
my ($proximo_asiento :shared, $capacidad :shared);
$capacidad = 40;
sub asigna_asiento {

lock($proximo_asiento);
if ($proximo_asiento < $capacidad) {

$asignado = $proximo_asiento;
$proximo_asiento += 1;
print "Asiento asignado: $asignado\n";

} else {

print "No hay asientos disponibles\n";
return 1;

}
return 0;

}

La implementación comunicación entre hilos en Perl implementa un

mutex a través de la función lock(), como atributo sobre una

variable, con ámbito léxico

Gunnar Wolf

Administración de procesos: Primitivas de sincronización

Introducción a la concurrencia
Primitivas de sincronización
Patrones basados en semáforos
Problemas clásicos
El problema de inicio

Índice

1

Introducción a la concurrencia

2 Primitivas de sincronización

3 Patrones basados en semáforos

4 Problemas clásicos

5 El problema de inicio

Gunnar Wolf

Administración de procesos: Primitivas de sincronización

Introducción a la concurrencia
Primitivas de sincronización
Patrones basados en semáforos
Problemas clásicos
El problema de inicio

Requisitos para las primitivas

Implementadas a un nivel más bajo que el código que protegen

Desde el sistema operativo
Desde bibliotecas de sistema
Desde la máquina virtual (p.ej. JVM)

¡No las implementes tú mismo!

Parecen conceptos simples. . . Pero no lo son
Utilicemos el con