1. No category

Introducción Problemas Señales
Sincronización
Gustavo Romero López
Arquitectura y Tecnologı́a de Computadores
15 de mayo de 2015
Gustavo Romero López
Sincronización
1 / 79
Introducción Problemas Señales
Índice
1
Introducción
2
Problemas
3
Señales
Definición
Ası́ncronas
Sı́ncronas
Semáforos
UNIX
Gustavo Romero López
Sincronización
2 / 79
Introducción Problemas Señales
Lecturas recomendadas
J. Bacon
Operating Systems (9, 10, 11)
A. Silberschatz
Fundamentos de Sistemas Operativos (4, 6, 7)
W. Stallings
Sistemas Operativos (5, 6)
A. Tanuenbaum
Sistemas Operativos Modernos (2)
Gustavo Romero López
Sincronización
3 / 79
Introducción Problemas Señales
Introducción
Gustavo Romero López
Sincronización
4 / 79
Introducción Problemas Señales
Concurrencia (1)
Niveles:
Multiprogramación: gestión de multiples procesos.
Multiprocesamiento: gestión de múltiples hebras dentro de
un proceso.
Procesamiento distribuido: gestión de múltiples procesos
sobre múltiples máquinas (sin memoria compartida).
Contexto:
Entre aplicaciones: originalmente ideada con este fin.
Dentro de una aplicación: conveniente en ciertos tipos de
aplicaciones.
Sistema operativo: las mismas ventajas que aporta a las
aplicaciones son deseables aquı́.
Tipos:
Monoprocesador: los procesos se entrelazan en el tiempo
para ofrecer la apariencia de ejecución simultánea.
Multiprocesador: la ejecución de múltiples procesos se solapa
en el tiempo.
Gustavo Romero López
Sincronización
5 / 79
Introducción Problemas Señales
Concurrencia (2)
No puede predecirse la velocidad relativa de ejecución:
Eventos.
Polı́ticas del sistema operativo.
Problemas:
La compartición de recursos está plagada de peligros.
La gestión óptima de los recursos es complicada.
La localización de errores de programación es muy complicada
debido a su naturaleza no determinista y no reproducible.
Todos los sistemas comparten este tipo de problemas
aunque algunos pueden verse agravados en máquinas con
más de un procesador.
Gustavo Romero López
Sincronización
6 / 79
Introducción Problemas Señales
Conceptos importantes
Condición de carrera: situación en la que el resultado de una
operación depende de la velocidad relativa de ejecución entre
varias hebras.
Sección crı́tica: sección de código que no pueden ejecutar
varias hebras de forma concurrente.
Exclusión mutua: requisito de acceso exclusivo a recursos
durante la ejecución de una sección crı́tica.
Interbloqueo (“deadlock”): situación en la que varias hebras
son incapaces de avanzar porque todas ellas están esperando
que alguna de las otras haga algo.
Inanición: situación en la que una hebra preparada es
mantenida en dicho estado indefinidamente.
Circulo vicioso (“livelock”): situación en la que varias hebras
cambian su estado pero sin llegar a realizar trabajo útil.
Gustavo Romero López
Sincronización
7 / 79
Introducción Problemas Señales
¿Por qué sincronizar?
Las hebras cooperan porque...
Necesitan coordinar su ejecución.
El botón de detener del navegador cancela la descarga de una
página web.
La hebra del interfaz del navegador necesita avisar a la hebra
encargada de descargar la página web.
Necesitan acceder a recursos compartidos.
Varias hebras de un servidor web pueden acceder a una
caché común en memoria para ahorrar espacio y tiempo.
Gustavo Romero López
Sincronización
8 / 79
Introducción Problemas Señales
Coordinación
b2 tiene que esperar hasta
que a1 haya completado su
ejecución
ejemplos:
Navegador: ai descarga,
bi renderiza.
Servidor web: ai rellena
caché, bi responde
petición.
Gustavo Romero López
Sincronización
9 / 79
Introducción Problemas Señales
Recursos compartidos
Problema básico:
2 hebras acceden a una variable compartida.
Si la variable compartida es leida y escrita por ambas hebras
tendremos que coordinar el acceso.
En los próximos 2 temas estudiaremos...
Mecanismos para controlar el acceso a recursos compartidos:
Bajo nivel: cerrojos.
Alto nivel: semáforos, monitores, variables condición.
Protocolos para coordinar el acceso a recursos compartidos.
La gestión de la concurrencia es complicada y propensa a
errores.
En Informática se dedica una asignatura completa a su estudio.
Incluso las soluciones de algunos libros de texto son erróneas.
Gustavo Romero López
Sincronización
10 / 79
Introducción Problemas Señales
Ejemplo: cuenta bancaria (1)
procedimiento para retirar fondos de una cuenta bancaria
int retirar(CCC_t cuenta, int cantidad)
{
int saldo = conseguir_saldo(cuenta);
saldo = saldo - cantidad;
almacenar_saldo(cuenta, saldo);
return saldo;
}
procedimiento para ingresar fondos en una cuenta bancaria
int ingresar(CCC_t cuenta, int cantidad)
{
int saldo = conseguir_saldo(cuenta);
saldo = saldo + cantidad;
almacenar_saldo(cuenta, saldo);
return saldo;
}
Gustavo Romero López
Sincronización
11 / 79
Introducción Problemas Señales
Ejemplo: cuenta bancaria (2)
Supongamos un saldo inicial de 1.000e.
Estudiaremos el caso en que dos personas intentan retirar
100e a la vez de la misma cuenta desde dos cajeros
automáticos.
Imaginemos que cada procedimiento se ejecuta como una
hebra diferente.
La ejecución de las 2 hebras podrı́a entrelazarse debido a
la planificación del sistema operativo.
¿Existe algún problema?
¿Cuál será el saldo de la cuenta tras retirar fondos?
Gustavo Romero López
Sincronización
12 / 79
Introducción Problemas Señales
Ejemplo: cuenta bancaria (3)
hebra 1
saldo = conseguir saldo(cuenta);
saldo = saldo - cantidad;
almacenar saldo(cuenta, saldo);
return saldo;
hebra 2
saldo = conseguir saldo(cuenta);
saldo = saldo - cantidad;
almacenar saldo(cuenta, saldo);
return saldo;
saldo final: 800e
Gustavo Romero López
Sincronización
13 / 79
Introducción Problemas Señales
Ejemplo: cuenta bancaria (4)
hebra 1
saldo = conseguir saldo(cuenta);
saldo = saldo - cantidad;
hebra 2
saldo = conseguir saldo(cuenta);
saldo = saldo - cantidad;
almacenar saldo(cuenta, saldo);
return saldo;
almacenar saldo(cuenta, saldo);
return saldo;
saldo final: 900e
Gustavo Romero López
Sincronización
14 / 79
Introducción Problemas Señales
Condiciones de carrera
El problema ocurre porque dos hebras acceden a un recurso
compartido sin sincronizar su uso.
Las condiciones de carrera producen resultados
impredecibles.
Dependen de cuándo se ejecutan las hebras, durante
cuánto tiempo y de cuándo se produce el cambio entre
ellas, y por supuesto, de lo que estén haciendo.
El acceso concurrente a recursos compartidos debe ser
controlado.
Es la única forma de que podamos comprender el
comportamiento de los programas.
Necesitamos reintroducir el determinismo y la
reproducibilidad.
Gustavo Romero López
Sincronización
15 / 79
Introducción Problemas Señales
Operaciones atómicas
Para comprender un programa concurrente debemos conocer
qué operaciones deberı́an ser indivisibles.
Operación atómica: una operación que siempre se ejecuta
hasta completarse o que por el contrario no inicia su
ejecución.
Indivisible: no puede ser detenida a mitad y luego continuar.
Son la base fundamental sobre la que se crean programas
multihebra y sin las que no habrı́a forma de hacer que
funcionasen de manera correcta.
En la mayorı́a de los procesadores las operaciones de lectura y
escritura de una palabra de memoria son atómicas.
Sin embargo existen muchas instrucciones que no son
atómicas:
El almacenamiento de reales grandes puede no serlo.
Las instrucciones de sobre cadenas y vectores.
Gustavo Romero López
Sincronización
16 / 79
Introducción Problemas Señales
¿Qué recursos son compartidos?
Las variables locales de los procedimientos
no son compartidas.
Existen en la pila.
La pila es privada para cada hebra.
No podemos pasar un puntero a una
variable local a otra hebra ¿Por qué?
Las variables globales si son compartidas.
Se almacenan en la zona de datos estáticos.
Son accesibles por todas las hebras.
Los datos alojados dinámicamente si son
compartidos:
Se almacenan en el cima/montón (“heap”).
Son accesibles por todas las hebras.
¿Hay algún problema en utilizar punteros a
objetos compartidos? ↔ ¿dónde se
almacenan? ↔ ¿cuál es su tiempo de vida?
Gustavo Romero López
Sincronización
17 / 79
Introducción Problemas Señales
Ejemplo: recursos compartidos
¿Qué pasará al ejecutar este código en dos hebras?
void* saludo(void*)
{
while(true)
cout << ‘‘hola, soy ‘‘ << pthread self() << endl;
return NULL;
}
esto...
hola, soy 918374512
hola, soy 649128354
o esto...
hola, soy hola, soy 918374512
649128354
Condición de carrera: ambas hebras acceden al terminal que
es un recurso compartido.
Gustavo Romero López
Sincronización
18 / 79
Introducción Problemas Señales
Ejemplo: datos compartidos (1)
int a = 0, b = 0; // variables compartidas
void *suma(void*)
{
while(true)
{
a = a + 1;
b = b + 1;
}
return NULL;
}
void *resta(void*)
{
while(true)
{
a = a - 1;
b = b - 1;
}
return NULL;
}
Tras un tiempo... ¿seguirán a y b siendo iguales?
Gustavo Romero López
Sincronización
19 / 79
Introducción Problemas Señales
Ejemplo: datos compartidos (2)
int a = 0, b = 0; // variables compartidas
void *suma(void*)
{
while(true)
{
a = a + 1;
b = b + 1;
}
return NULL;
}
void *resta(void*)
{
while(true)
{
a = a - 1;
b = b - 1;
}
return NULL;
}
El código que accede a variables compartidas son secciones
crı́ticas → tras cierto tiempo a 6= b
Compartir datos y recursos induce problemas similares.
Problemas: ¿optimización? ¿volatile? ¿atomic? ¿mutex?
Gustavo Romero López
Sincronización
20 / 79
Introducción Problemas Señales
Exclusión mutua
Debemos utilizar exclusión mutua para sincronizar el acceso
a los recursos compartidos, por ejemplo, serializando el
acceso.
Cualquier código que utilice exclusión mutua para sincronizar
su ejecución es denominado sección crı́tica.
Sólo una hebra puede ejecutar su sección crı́tica.
El resto de hebras son forzadas a esperar a la entrada.
Cuando una hebra abandona su sección crı́tica otra puede
entrar.
Gustavo Romero López
Sincronización
21 / 79
Introducción Problemas Señales
Interacción entre hebras
percepción
relación
se desconocen
competencia
percepción
indirecta
(recursos
compartidos)
cooperación
por compartición
percepción directa (comunicación)
cooperación
por
comunicación
Gustavo Romero López
influencia
resultados independientes,
temporización
afectable
resultados
dependientes,
temporización
afectable
resultados
dependientes,
temporización
afectable
Sincronización
problemas
interbloqueo,
inanición
exclusión mutua,
interbloqueo,
inanición,
coherencia de datos
interbloqueo,
inanición
22 / 79
Introducción Problemas Señales
Problemas
Gustavo Romero López
Sincronización
23 / 79
Introducción Problemas Señales
Productor/consumidor con buffer ilimitado
Dos procesos repiten indefinidamente su trabajo: el productor
genera datos que introduce en un buffer. El consumidor
recuperar los datos y hace algo con ellos.
¿Hay un problema de concurrencia? =⇒ si, el consumidor no
puede consumir desde un buffer vacio.
Gustavo Romero López
Sincronización
24 / 79
Introducción Problemas Señales
Productor/consumidor con buffer limitado
¿Aparecen nuevos problemas si el buffer no es infinito? =⇒ si, el
productor no puede introducir datos en un buffer lleno.
Si hay más de un productor y/o consumidor =⇒ Deben competir
por el uso del buffer con sus iguales.
Gustavo Romero López
Sincronización
25 / 79
Introducción Problemas Señales
El problema del barbero durmiente
En una barberı́a trabaja un
barbero que tiene un único
sillón de trabajo y varias sillas
para esperar. Cuando no hay
clientes, el barbero se sienta
en una silla y se duerme.
Cuando llega un nuevo
cliente, éste o bien despierta
al barbero o, si el barbero
está afeitando a otro cliente,
se sienta en una silla. Si todas
las sillas están ocupadas por
clientes esperando se va.
Gustavo Romero López
Sincronización
26 / 79
Introducción Problemas Señales
El problema de los lectores/escritores
Cierto número de hebras acceden a memoria, unas para leer y otras
para escribir. Mientras una escriba ninguna otra podrá acceder.
Sı́ se permite a varias hebras leer simultáneamente.
¿Problemas? → Inconsistencia y competición.
3 versiones: prioridad lectores, prioridad escritores y justa.
Gustavo Romero López
Sincronización
27 / 79
Introducción Problemas Señales
El problema de la cena de los filósofos
Vida de un filósofo
while(true)
{
pensar();
coger_tenedores();
comer();
}
Requisitos:
Evitar el
intebloqueo.
Evitar la inanición.
Gustavo Romero López
Sincronización
28 / 79
Introducción Problemas Señales
Niveles de sincronización
programas
API de alto
nivel
hardware
procesos/hebras cooperativos
cerrojos, semáforos, monitores, paso de mensajes
load&store, deshabilitar interrupciones, test&set,
compare&swap
A continuación veremos cómo implementar varias primitivas de
sincronización de alto nivel:
Si las únicas operaciones atómicas disponibles son la carga y
el almacenamiento será más complicado.
Necesitamos primitivas útiles a nivel de usuario.
Gustavo Romero López
Sincronización
29 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Señales
Gustavo Romero López
Sincronización
30 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Primero las señales, después la exclusión mutua
Los dos mecanismos se diferencian sólo ligeramente.
Debemos intentar no mezclarlos.
El uso habitual de las señales es...
Una hebra desea informar a...
otra hebra
cualquier hebra
conjunto de ellas
de que ha alcanzado cierto punto de su código (IP = valor).
Ejemplo: un jefe de estación tocando el silbato.
Gustavo Romero López
Sincronización
31 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Señales
Definición: mensaje entre hebras que puede provocar la ejecución
de un procedimiento en el receptor.
Tipos:
Bandera:
Valor binario: 0/1, si/no,...
El significado de la bandera debe ser acordado entre las hebras
en comunicación.
Contador:
Cada valor puede tener un significado diferente o reflejar el
número de señales pendientes.
¿Cúando es una bandera suficiente? ¿Cuándo necesitamos un
contador? =⇒ Depende de para que usemos la bandera.
Gustavo Romero López
Sincronización
32 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Relación de precedencia (1)
hebra 1
...
sección a1
{
...
}
sección a2
{
...
}
...
hebra 2
...
sección b1
{
...
}
sección b2
{
...
}
...
¿Cómo asegurar que la sección a1 se ejecuta antes que b2? → la
sección b2 debe esperar hasta que a1 se haya ejecutado.
Gustavo Romero López
Sincronización
33 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Relación de precedencia (2)
hebra 1
...
sección a1
{
...
}
s.señalar()
sección a2
{
...
}
...
hebra 2
...
sección b1
{
...
}
s.esperar()
sección b2
{
...
}
...
¿Cómo implementar este objeto señal 1:1 (emisor/receptor)?
Gustavo Romero López
Sincronización
34 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Tipos de soluciones
Soluciones a nivel de aplicación:
No requiere instrucciones especiales del procesador ni servicios
del núcleo.
Implementado como funciones de biblioteca o dentro de la
propia aplicación.
Soluciones a nivel del núcleo:
Proporcionar llamadas al sistema que cumplan estas funciones.
Soluciones hardware:
Instrucciones especiales del procesador.
Garantizan la ejecución atómica.
La mayorı́a de los sistemas permiten usar varias de estas
soluciones.
Gustavo Romero López
Sincronización
35 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Señales en el problema productor/consumidor
Problemas que podremos resolver empleando señales:
El productor debe avisar al consumidor para que pueda
utilizar el objeto que acaba de introducir en el buffer.
El consumidor debe avisar al productor de que ha
consumido un objeto del buffer y por lo tanto ha quedado
un hueco libre.
El productor debe esperar cuando el buffer está lleno.
El consumidor debe esperar cuando el buffer está vacı́o.
Gustavo Romero López
Sincronización
36 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Solución al problema productor/consumidor (v1)
const int N = 10; // tama~
no del buffer
int buffer[N];
// almacén de datos
int contador = 0; // posición a producir/consumir
void* productor(void*)
{
while (true)
{
while (contador == N);
buffer[contador] = producir();
contador = contador + 1;
}
}
void* consumidor(void*)
{
while (true)
{
while (contador == 0);
contador = contador - 1;
consumir(buffer[contador]);
}
}
¿Funciona? → No, condición de carrera en la variable
compartida contador.
Gustavo Romero López
Sincronización
37 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Solución al problema productor/consumidor (v2)
const int N = 10;
int buffer[N];
int entra = 0;
int sale = 0;
//
//
//
//
número de elementos
almacén de datos
posición para introducir
posición para sacar
void* productor(void*)
{
while (true)
{
while ((entra + 1) % N == sale);
buffer[entra] = producir();
entra = (entra + 1) % N;
}
}
void* consumidor(void*)
{
while (true)
{
while (entra == sale);
consumir(buffer[sale]);
sale = (sale + 1) % N;
}
}
¿Funciona? ¿es eficiente? ¿es escalable?
¿Podemos utilizar todos los elementos del buffer? → No, sólo N − 1.
Gustavo Romero López
Sincronización
38 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Escalabilidad
¿Cuándo se dice que una solución del problema
productor/consumidor es escalable?
Cuando funciona de forma efectiva para:
p ≥ 1 productores.
c ≥ 1 consumidores.
un buffer de 0 < N < MAXINT elementos.
La solución anterior no es escalable porque...
Sólo parcialmente correcto para p = 1 y c = 1.
Incorrecto para N = 1.
Gustavo Romero López
Sincronización
39 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Eficiencia
¿Cuándo se dice que una solución del problema
productor/consumidor es eficiente?
Cuando funciona de forma rápida y con poca sobrecarga.
La solución anterior no es eficiente porque...
La sincronización mediante espera ocupada desperdicia el
tiempo del procesador.
El planificador puede prevenir la ineficiente espera ocupada.
Sólo es útil si conocemos que la espera ocupada va a ser corta.
¿Cómo mejorar esta solución?
Utilizar la API del núcleo para evitar la espera ocupada.
Gustavo Romero López
Sincronización
40 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Interfaz del núcleo para evitar la espera ocupada
block()
sleep() → bloquear/dormir de UNIX.
unblock()
wakeup() → desbloquear/despertar de UNIX.
yield()
pthread yield() → ceder el procesador entre hebras.
sched yield() → ceder el procesador entre procesos UNIX.
Gustavo Romero López
Sincronización
41 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
block() → bloquear() del núcleo
bloquear(hebra_actual)
{
hebra_actual.estado = bloqueado ;
siguiente_hebra = planificador();
hebra_actual = cambio_de_hebra(siguiente_hebra);
hebra_actual.estado = ejecutando ;
}
desbloquear(una_hebra)
{
if (una_hebra.estado == bloqueado )
una_hebra.estado = preparado ;
}
Solución para el modelo de 3 estados.
¿Cómo implementarı́a yield? −→ modificando bloquear...
Gustavo Romero López
Sincronización
42 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
API del núcleo aplicada al problema productor/consumidor
const int N = 100; // tama~
no del buffer
int buffer[N];
// almacén
int contador = 0; // número de elementos en el buffer
void* productor(void*)
void* consumidor(void*)
{
{
while (true)
while (true)
{
{
if (contador == N)
if (contador == 0)
bloquear(productor);
bloquear(consumidor);
buffer[contador++] = producir();
consumir(buffer[--contador]);
desbloquear(productor);
desbloquear(consumidor);
}
}
}
}
Mejora la eficiencia: deja de utilizar espera ocupada, pero...
Problemas: condición de carrera (contador) e interbloqueo 1 .
1
contador == 0 + if del consumidor + N ejecuciones de productor
Gustavo Romero López
Sincronización
43 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
En resumen... la API del núcleo puede ser insuficiente
El uso del API del núcleo puede ser peligroso.
Ver la condición de carrera del ejemplo anterior.
Serı́a mejor utilizar objetos señal u objetos
sincronización con métodos apropiados.
Hasta ahora hemos intentado enviar señales sin
éxito mediante...
espera ocupada a nivel de usuario.
bloqueo a nivel del núcleo.
Gustavo Romero López
Sincronización
44 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Objeto señal
implementación a nivel de usuario
Implementación que emplea una
variable lógica s compartida
entre hebras.
¿Qué
podrı́a
suceder
si
o.se~
nalar() es invocado varias
veces antes que o.esperar()?
→ se pierden señales.
¿Qué
podrı́a
suceder
si
o.esperar()
es
invocado
antes que o.se~
nalar()?
→ espera ocupada, se deberı́a
dejar libre el procesador.
¿Funcionarı́a en cualquier tipo
de sistema? → no, exige
memoria compartida.
¿Es eficiente y escalable?
Gustavo Romero López
Sincronización
45 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Objeto señal: implementación a nivel usuario (v1)
class se~
nal
{
public:
se~
nal(): activa(false) {}
¿Pierde señales?
¿Eficiente?
¿Escalable?
void se~
nalar() { activa = true; }
void esperar()
{
while (activa == false);
activa = false;
}
private:
bool activa;
};
Gustavo Romero López
Sincronización
46 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Objeto señal: implementación a nivel usuario (v2)
class se~
nal
{
public:
se~
nal(): activa(false) {} // inicialización
¿Pierde señales?
¿Eficiente?
¿Escalable?
Parecido a la espera
ocupada.
void se~
nalar()
{
activa = true;
yield();
}
// exige cooperación
void esperar()
{
while (activa == false)
yield();
// evita espera ocupada
activa = false;
}
private:
bool activa;
};
Gustavo Romero López
Sincronización
47 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
¿Son escalables estas soluciones? (1)
¿Puede más de una hebra se~
nalar y/o
esperar?
No, de otra forma ya no serı́a un objeto señal 1:1 sino n:m con
n > 1, m > 1 o ambos.
Múltiples usos de un mismo objeto señal dentro
del un mismo par de hebras.
No es efectivo ni eficiente.
Multiples objetos señal dentro del un mismo par
de hebras.
No es eficiente.
Gustavo Romero López
Sincronización
48 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
¿Son escalables estas soluciones? (2)
Múltiples usos de un mismo objeto señal dentro del un
mismo par de hebras.
No es efectivo ni eficiente ↔ ¿por qué?2
2
solución: o1, o2 y o3.
Gustavo Romero López
Sincronización
49 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Objeto señal: implementación a nivel del núcleo (v3)
class se~
nal
{
public:
se~
nal(): bloqueada(ninguna) {}
¿Pierde señales?
void se~
nalar()
{
desbloquear(bloqueada);
}
¿Eficiente?
¿Escalable?
void esperar()
{
bloqueada = esta;
bloquear(bloqueada);
bloqueada = ninguna; // ¿necesario?
}
private:
hebra bloqueada;
};
Gustavo Romero López
Sincronización
50 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Objeto señal: implementación a nivel del núcleo (v4)
class se~
nal
{
private:
bool activa;
hebra bloqueada;
public:
se~
nal():
activa(false),
bloqueada(ninguna) {}
void se~
nalar()
{
activa = true;
if (bloqueada != ninguna)
desbloquear(bloqueada);
2 }
void esperar()
{
while(activa == false)
{
1
bloqueada = esta;
3
bloquear(esta);
}
activa = false;
}
};
¿Pierde señales?
¡Eficiente!
¡Escalable!
¡Condición de carrera!
Gustavo Romero López
Sincronización
51 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Resumen
Problemas aún sin resolver:
Las operaciones se~
nalar() y esperar() deberı́an ser
atómicas.
Evitar la espera ocupada a nivel de usuario.
Sobre las soluciones vistas...
Todas pueden perder señales.
Repetidas operaciones se~
nalar() pueden sobreescribir señales
todavı́a no consumidas.
La operación se~
nalar() es ası́ncrona (no bloqueante) en
caso de que no haya otra hebra bloqueada mediante
esperar().
Existe el peligro de desbordar a otra hebra (servidor).
Gustavo Romero López
Sincronización
52 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Reconocimiento para evitar el desbordamiento
Observaciones:
se~
nalar() es ası́ncrono.
¿Hay alguna solución más obvia? −→ sincronı́a.
¿Protege frente a clientes maliciosos? −→ no.
Gustavo Romero López
Sincronización
53 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Objeto señal sı́ncrona
class se~
nal_sı́ncrona
{
public:
se~
nal_sı́ncrona():
activa(false),
se~
naladora(ninguna),
esperadora(ninguna) {}
void se~
nalar()
{
activa = true;
if (esperadora != ninguna)
desbloquear(esperadora);
else
{
se~
naladora = esta;
2
bloquear(se~
naladora);
se~
naladora = ninguna;
}
Gustavo Romero López
}
void esperar()
{
while(activa == false)
{
1
esperadora = esta;
3
bloquear(esperadora);
esperadora = ninguna;
}
activa = false;
desbloquear(se~
naladora)
}
private:
bool activa;
hebra se~
naladora;
hebra esperadora;
};
Sincronización
54 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
¿Son las banderas superfluas?
... dado que existen soluciones más potentes
No.
Casi todos los sistemas utilizan banderas.
Ejemplo: varias interrupciones sucesivas podrı́a provocar varios
cambios de hebra sucesivos.
Supongamos un sistema en que las interrupciones se producen
con mucha frecuencia y las prioridades pueden anidarse →
¿Cómo puede ser beneficioso utilizar banderas?
Gustavo Romero López
Sincronización
55 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Ejemplo de uso de banderas
Planificación perezosa y cambio de hebra: esperar hasta que
haya que volver al espacio de usuario.
Cada manejador de interrupción en el que pueda ser necesario
planificar activa la bandera de planificación.
Gustavo Romero López
Sincronización
56 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Relación de precedencia mútua (1)
hebra 1
...
sección a1
{
...
}
sección a2
{
...
}
...
hebra 2
...
sección b1
{
...
}
sección b2
{
...
}
...
¿Cómo conseguir que a1 <* b2 y que b1 <* a2?
Gustavo Romero López
Sincronización
57 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Relación de precedencia mútua (2)
hebra 1
...
sección a1
{
...
}
s1.señalar()
hebra 2
...
sección b1
{
...
}
s2.señalar()
s2.esperar()
sección a2
{
...
}
...
s1.esperar()
sección b2
{
...
}
...
¿Funciona? ¿Puede hacerse mucho mejor?
Gustavo Romero López
Sincronización
58 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Relación de precedencia mútua (3)
Ventajas:
Inconvenientes:
No necesitamos nuevos
mecanismos para un
problema parecido.
Complicado e ineficiente
=⇒ no es escalable.
Es muy fácil olvidar la
sincronización con una
nueva hebra =⇒ engorroso
y propenso a errores.
Pobre rendimiento debido
a que podrı́amos ahorrar
llamadas al sistema =⇒
no es eficiente.
Conclusión: necesitamos un mecanismo más efectivo.
Gustavo Romero López
Sincronización
59 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Sincronización “pura”
hebra 1
...
sección a1
{
...
}
s.sincronizar()
sección a2
{
...
}
...
hebra 2
...
sección b1
{
...
}
s.sincronizar()
sección b2
{
...
}
...
Problema: ¿Cómo implementar la sincronización de dos hebras?
Gustavo Romero López
Sincronización
60 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Objeto sincronización para 2 hebras
void sincronizar()
{
if (!activo)
{
activo = true;
bloqueada = actual;
bloquear(actual);
class sincronización
{
private:
bool activo;
hebra bloqueada;
// soy el primero
// esperar a la otra
}
else
// soy el segundo
{
activo = false;
// reinicializar
desbloquear(bloqueada); // liberar a la otra
public:
sincronización():
activo(false),
bloqueada(ninguna)
{
}
}
}
};
¿Es reutilizable?
¿Puede generalizase para más de dos hebras?
Gustavo Romero López
Sincronización
61 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Ejemplo de sincronización entre n hebras (barrera)
// problema numérico resuelto
// mediante ecuaciones diferenciales
sincronización s;
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
{
temp[i, j] = matriz[i - 1, j] + matriz[i + 1, j];
}
s.sincronizar();
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
{
matriz[i, j] = temp[i, j];
}
s.sincronizar();
Gustavo Romero López
Sincronización
62 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Barrera
Barrier
B
C
A
B
B
C
Barrier
Process
A
Barrier
A
D
D
Time
D
Time
(a)
C
Time
(b)
(c)
Uso de una barrera:
(a) Las hebras se aproximan a la barrera.
(b) Al llegar a la barrera las hebras se bloquean.
(c) La última hebra llega y provoca el desbloqueo de todas.
Gustavo Romero López
Sincronización
63 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Patrones de señalización: muchos a uno
Significado: la hebra azul sólo puede puede continuar tras un
punto de espera si las tres hebras verdes han alcanzado
cierto punto especı́fico de su código.
Gustavo Romero López
Sincronización
64 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Patrones de señalización: uno a muchos
Significado: las hebras azules sólo puede puede continuar si
la hebra verde han alcanzado cierto punto de su código.
Gustavo Romero López
Sincronización
65 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Patrones de señalización: muchos a muchos
Gustavo Romero López
Sincronización
66 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Otros patrones de señalización
La hebra azul sólo puede continuar si alguna de las dos
hebras verdes alcanza cierto punto de su código.
Problema: ¿Cómo y dónde almacenar temporalmente las
señales?
Gustavo Romero López
Sincronización
67 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Almacenamiento temporal de señales
Una nueva señal sobreescribe a las anteriores: banderas o
semáforos binarios.
Ventaja: se reacciona sólo a la señal más nueva.
Inconveniente: podrı́amos perder señales necesarias.
Cada nueva señal es almacenada temporalmente hasta que
pueda ser consumida: semáforos con contador.
Ventaja: se reacciona a toda señal.
Inconveniente:
una fuente de señales deficiente podrı́a desbordar el sistema.
Gustavo Romero López
Sincronización
68 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Semáforos con contador (Dijkstra)
objetos señal del núcleo
Definición: un semáforo es una variable entera, que aparte de
la inicialización, sólo puede ser modificada mediante dos
operaciones atómicas y mutuamente excluyentes.
p() / decrementar() / esperar()
Operación que decrementa el valor del semáforo.
v() / incrementar() / señalar()
Operación que incrementa el valor del semáforo.
Gustavo Romero López
Sincronización
69 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Semáforos con contador
¿Cómo diseñar e implementar los semáforos con
contador?
Para evitar la espera ocupada...
Cuando una hebra debe esperar ante un
semáforo =⇒ poner a la hebra llamadora en una
cola de bloqueados en espera de un evento.
La ocurrencia de un evento puede comunicarse
mediante el incremento del valor del semáforo.
Gustavo Romero López
Sincronización
70 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Semáforos con contador
Significado de los semáforos con contador:
Un valor positivo indica el número señales
emitidas.
Un valor negativo indica el número de hebras
que esperan por una señal −→ longitud de la
cola de hebras bloqueadas en espera de una
señal.
Si el contador es cero ni hay señales emitidas ni
hay hebras esperando que se produzca una señal.
Gustavo Romero López
Sincronización
71 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Semáforos con contador
class semáforo
{
public:
semáforo(int _valor = 0):
valor(_valor),
bloq(vacia) {}
void p() // esperar()
{
valor = valor - 1;
if (valor < 0)
{
bloq.a~
nadir(esta);
bloquear(esta);
}
Gustavo Romero López
}
void v() // se~
nalar()
{
hebra h;
valor = valor + 1;
h = bloq.borrar primero();
desbloquear(h);
}
private:
int valor;
cola<hebra> bloq;
};
Sincronización
72 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Señales UNIX
Pueden lanzarse mediante la orden kill del intérprete de
órdenes y la llamada al sistema kill().
No tienen un significado ni un interfaz común.
Hay cuatro versiones diferentes:
System V unreliable
BSD
System V reliable
POSIX
El uso de las señales puede conducir a condiciones de carrera.
La programación con señales es engorrosa.
Gustavo Romero López
Sincronización
73 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Lista de señales UNIX (POSIX.1)
Signal
Value
Action Comment (Value = alpha/sparc,i386/ppc/sh,mips)
------------------------------------------------------------------------SIGHUP
1
Term
Hangup detected on controlling terminal
or death of controlling process
SIGINT
2
Term
Interrupt from keyboard
SIGQUIT
3
Core
Quit from keyboard
SIGILL
4
Core
Illegal Instruction
SIGABRT
6
Core
Abort signal from abort(3)
SIGFPE
8
Core
Floating point exception
SIGKILL
9
Term
Kill signal
SIGSEGV
11
Core
Invalid memory reference
SIGPIPE
13
Term
Broken pipe: write to pipe with no readers
SIGALRM
14
Term
Timer signal from alarm(2)
SIGTERM
15
Term
Termination signal
SIGUSR1 30,10,16 Term
User-defined signal 1
SIGUSR2 31,12,17 Term
User-defined signal 2
SIGCHLD 20,17,18 Ign
Child stopped or terminated
SIGCONT 19,18,25
Continue if stopped
SIGSTOP 17,19,23 Stop
Stop process
SIGTSTP 18,20,24 Stop
Stop typed at tty
SIGTTIN 21,21,26 Stop
tty input for background process
SIGTTOU 22,22,27 Stop
tty output for background process
Gustavo Romero López
Sincronización
74 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Reparto de señales en UNIX
Gustavo Romero López
Sincronización
75 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Tipos de señales UNIX
Las señales UNIX pueden recibirse...
sı́ncrona
o
ası́ncronamente
Las señales sı́ncronas suelen enviarlas la propia hebra/proceso:
violación del espacio de direcciones.
excepción de división entre cero.
reservadas al usuario.
Las señales ası́ncronas suele enviarlas otras hebras/procesos:
órden kill
llamada al sistema kill()
CTRL+C: SIGINT −→ terminar proceso
CTRL+Z: SIGSTOP −→ suspender proceso
expira el tiempo del temporizador
Gustavo Romero López
Sincronización
76 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
API de las señales UNIX
#include
#include
#include
#include
<sys/types.h>
<pthread.h>
<unistd.h>
<signal.h>
//
//
//
//
pid_t
pthread_t
getpid
kill pthread_kill raise signal
// instala la función ‘‘manejador’’ como manejador
// de se~
nal para la se~
nal ‘‘signum’’
typedef void (*sighandler_t)(int);
sighandler_t signal(int signum, sighandler_t manejador);
// envia la se~
nal ‘‘signum’’ a el proceso ‘‘pid’’
int kill(pid_t pid, int signum);
// envı́a la se~
nal ‘‘signum’’ a el proceso actual
// equivalente a kill(getpid(), signum)
int raise(int signum);
// envı́a la se~
nal ‘‘signum’’ a la hebra ‘‘hebra’’
int pthread_kill(pthread_t hebra, int signum);
Gustavo Romero López
Sincronización
77 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
Manejadores de señal UNIX
El manejador por defecto, ¿se ejecuta en modo
usuario o modo núcleo? → depende de quien
maneje el evento.
Manejadores definidos por el usuario:
Implemente manejadores de señal cortos.
Tenga mucho cuidado al utilizar señales.
Muchos sistemas UNIX exigen reinstalar el manejador de señal
para poder volver a utilizarlo por segunda vez.
¿Detecta una posible condición de carrera?
Gustavo Romero López
Sincronización
78 / 79
Introducción Problemas Señales
Definición Ası́ncronas Sı́ncronas Semáforos UNIX
alarma.c
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int F R E C U E NCI A_A LARM A = 1; // segundos
void a trapar_alarma ( int ) ; // d e c l a r a c i ó n a n t i c i p a d a
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - void in s talar_alarma () // i n s t a l a d o r del m a n e j a d o r de se ~
n al y alarma
{
signal ( SIGALRM , atrapar_alarma ) ; // e s t a b l e c e r m a n e j a d o r de la se ~
n al
alarm ( F R ECU ENC IA_ ALA RMA ) ;
// e s t a b l e c e r alarma
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - void a trapar_alarma ( int i ) // m a n e j a d o r de se ~
n al
{
i ns ta la r_alarma () ; // r e i n s t a l a r tras cada alarma
printf ( " ¡ ¡ ¡ ALARMA !!!\ n " ) ;
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - int main ()
{
i ns ta la r_alarma () ; // instalar alarma por primera vez
for (;;) ;
// bucle infinito
}
Gustavo Romero López
Sincronización
79 / 79