Post on 08-Aug-2020
transcript
Sistemas operativos: una visión aplicada
Capítulo 5 Comunicación y sincronización
de procesos
Sistemas operativos: una visión aplicada 1 © J. Carretero, F. García, P. de Miguel, F. Pérez
Sistema multiprogramado con un una CPU
Tiempo
Proceso A
Proceso B
Proceso C
Sistemas operativos: una visión aplicada 2 © J. Carretero, F. García, P. de Miguel, F. Pérez
Ejecución en un sistema multiprocesador
Tiempo
Proceso B
Proceso A
Proceso C
Proceso D
CPU 1
CPU 2
Sistemas operativos: una visión aplicada 3 © J. Carretero, F. García, P. de Miguel, F. Pérez
Problemas clásicos de comunicación y sincronización
• El problema de la sección crítica• El problema del productor-consumidor• El problema de los lectores-escritores• Comunicación cliente-servidor
Sistemas operativos: una visión aplicada 4 © J. Carretero, F. García, P. de Miguel, F. Pérez
Ejemplo 1
S1 = 1 +...+ 50
ni = 1nf = 50
ni =51nf = 100
S2 = 51 +....+ 100
Proceso ligeroprincipal
suma_total = S1 + S2
Sistemas operativos: una visión aplicada 5 © J. Carretero, F. García, P. de Miguel, F. Pérez
Ejemplo 1
• Calcula la suma de los N primeros números utilizando procesos ligeros.int suma_total = 0;
void suma_parcial(int ni, int nf) {
int j = 0;
int suma_parcial = 0;
for (j = ni; j <= nf; j++)suma_parcial = suma_parcial + j;
suma_total = suma_total + suma_parcial;pthread_exit(0);
}
• Si varios procesos ejecutan concurrentemente este código se puede obtener un resultado incorrecto.
• Solución: secciones críticas
Sistemas operativos: una visión aplicada 6 © J. Carretero, F. García, P. de Miguel, F. Pérez
Ejemplo con sección crítica
void suma_parcial(int ni, int nf) {
int j = 0;
int suma_parcial = 0;
for (j = ni; j <= nf; j++)
suma_parcial = suma_parcial + j;
<Entrada en la sección crítica>
suma_total = suma_total + suma_parcial;<Salida de la sección crítica>
pthread_exit(0);
}
Sistemas operativos: una visión aplicada 7 © J. Carretero, F. García, P. de Miguel, F. Pérez
Ejemplo 2
void ingresar(char *cuenta, int cantidad) {
i nt saldo, fd;
fd = open(cuenta, O_RDWR);
read(fd, &saldo, sizeof(int));
saldo = saldo + cantidad;
lseek(fd, 0, SEEK_SET);
write(fd, &saldo, sizeof(int));
close(fd);
return;}
• Si dos procesos ejecutan concurrentemente este código se puede perder algún ingreso.
• Solución: secciones críticas
Sistemas operativos: una visión aplicada 8 © J. Carretero, F. García, P. de Miguel, F. Pérez
Ejemplo 2 con sección crítica
void ingresar(char *cuenta, int cantidad) {
int saldo, fd;
fd = open(cuenta, O_RDWR);
<Entrada en la sección crítica >
read(fd, &saldo, sizeof(int));
saldo = saldo + cantidad;
lseek(fd, 0, SEEK_SET);
write(fd, &saldo, sizeof(int));
<Salida de la sección crítica >
close(fd);
return;}
Sistemas operativos: una visión aplicada 9 © J. Carretero, F. García, P. de Miguel, F. Pérez
Ejemplo 3
Procesador 1 Procesador 2
PID = 500
PID = 501
PID = 501
PID = 500
Lee PID
Escribe PID
Escribe PID
Incrementa yasigna PID
Incrementa yasigna PID
PID = 500
Registro o posición de memoria
PID = 501
PID = 501
Lee PID
Sistemas operativos: una visión aplicada 10 © J. Carretero, F. García, P. de Miguel, F. Pérez
Problema del productor-consumidor
ProcesoProductor
ProcesoConsumidor
Mecanismo de comunicación
Flujo de datos
Sistemas operativos: una visión aplicada 11 © J. Carretero, F. García, P. de Miguel, F. Pérez
El problema de los lectores-escritores
EscritorLector Lector Escritor Lector
Recurso
Sistemas operativos: una visión aplicada 12 © J. Carretero, F. García, P. de Miguel, F. Pérez
Comunicación cliente-servidor
Computador Computador
Procesocliente
S.O.
Petición
Respuesta
Procesoservidor
Sistemas operativos: una visión aplicada 13 © J. Carretero, F. García, P. de Miguel, F. Pérez
Contenido
• Procesos concurrentes. • Problemas clásicos de comunicación y sincronización.
• Mecanismos de comunicación y sincronización.
• Paso de mensajes.• Aspectos de implementación• Interbloqueos. • Servicios POSIX• Servicios Win32
Sistemas operativos: una visión aplicada 14 © J. Carretero, F. García, P. de Miguel, F. Pérez
Mecanismos de comunicación
• Archivos• Tuberías (pipes, FIFOS)• Variables en memoria compartida • Paso de mensajes
Sistemas operativos: una visión aplicada 15 © J. Carretero, F. García, P. de Miguel, F. Pérez
Mecanismos de Sincronización
• Construcciones de los lenguajes concurrentes (procesos ligeros) • Servicios del sistema operativo:
– Señales (asincronismo) – Tuberías (pipes, FIFOS)– Semáforos – Mutex y variables condicionales – Paso de mensajes
• Las operaciones de sincronización deben ser atómicas
Sistemas operativos: una visión aplicada 16 © J. Carretero, F. García, P. de Miguel, F. Pérez
Comunicación unidireccional con tuberías
Procesode Usuario
Procesode Usuario
pipe
SO
write read
Flujo de datos
Sistemas operativos: una visión aplicada 17 © J. Carretero, F. García, P. de Miguel, F. Pérez
Comunicación bidireccional con tuberías
Procesode Usuario
Procesode Usuario
SO
write write readread
Flujo de datos
Flujo de datos
pipe
pipe
Sistemas operativos: una visión aplicada 18 © J. Carretero, F. García, P. de Miguel, F. Pérez
Ejecución de mandatos con tuberías (III)
•Proceso
•STDIN•STDOUT
•pipe(fd) •fork()
•Proceso
•STDIN•STDOUT•fd[0]•fd[1]
•pipe
•redirección
•Proceso hijo
•STDIN•STDOUT•fd[0]•fd[1]
•Proceso
•STDIN•STDOUT•fd[0]•fd[1]
•pipe
•exec
•Proceso hijo
•STDIN
•STDOUT
•Proceso
•STDIN
•STDOUT•pipe
•Proceso hijo
•STDIN
•STDOUT
•Proceso
•ls •wc
•STDIN
•STDOUT•pipe
Sistemas operativos: una visión aplicada 19 © J. Carretero, F. García, P. de Miguel, F. Pérez
Semáforos
• Mecanismo de sincronización • Misma máquina • Objeto con un valor entero • Dos operaciones atómicas
– wait– signal
Sistemas operativos: una visión aplicada 20 © J. Carretero, F. García, P. de Miguel, F. Pérez
Secciones críticas con semáforos
wait(s); /* entrada en la seccion critica */
< seccion critica >
signal(s); /* salida de la seccion critica */
• El semáforo debe tener valor inicial 1 P0
Valor delsemáforo (s)
wait(s)
signal(s)
signal(s)
signal(s)
wait(s)
desbloquea
desbloquea
wait(s)
1
1
0-1
-2
-1
0
P1 P2
Ejecutando código de la sección crítica
Proceso bloqueado en el semáforo
Sistemas operativos: una visión aplicada 21 © J. Carretero, F. García, P. de Miguel, F. Pérez
Productor-consumidor con semáforos(buffer acotado y circular)
Consumidor
Productor
Sistemas operativos: una visión aplicada 22 © J. Carretero, F. García, P. de Miguel, F. Pérez
Memoria compartida
• Declaración independiente de variables
Datos
Texto
Proceso A Proceso B
Pila
TextoDatos
PilaSegmento de memoriacompartida
var1
2
var2
Sistemas operativos: una visión aplicada 23 © J. Carretero, F. García, P. de Miguel, F. Pérez
Productor-consumidor con memoria compartida
• Productor: – Crea los semáforos (shm_open )– Crea la zona de memoria compartida utilizando un archivo proyectado en
memoria (open ) – Le asigna espacio (ftruncate ) – Proyecta el archivo en su espacio de direcciones (mmap) – Utiliza la zona de memoria compartida – Desproyecta la zona de memoria compartida – Cierra y borra el archivo.
• Consumidor: – Abre los semáforos (shm_open )– Debe esperar a que archivo esté creado para abrirlo (open )– Proyecta el archivo en su espacio de direcciones (mmap) – Utiliza la zona de memoria compartida – Cierra el archivo.
Sistemas operativos: una visión aplicada 24 © J. Carretero, F. García, P. de Miguel, F. Pérez
Mutex y variables condicionales
• Un mutex es un mecanismo de sincronización indicado para procesos ligeros.
• Es un semáforo binario con dos operaciones atómicas: – lock(m) Intenta bloquear el mutex, si el mutex ya está
bloqueado el proceso se suspende. – unlock(m) Desbloquea el mutex, si existen procesos
bloqueados en el mutex se desbloquea a uno.
Sistemas operativos: una visión aplicada 25 © J. Carretero, F. García, P. de Miguel, F. Pérez
Secciones críticas con mutex
lock(m); /* entrada en la seccion critica */
< seccion critica >
unlock(s); /* salida de la seccion critica */
• La operación unlock debe realizarla el proceso ligero que ejecutólock
Proceso ligero A
lock mutex
Seccióncrítica
Proceso ligero B
lock mutex
unlock mutex obtiene mutex Proceso ligero ejecutando
Proceso ligero bloqueado
Punto de sincronización
Sistemas operativos: una visión aplicada 26 © J. Carretero, F. García, P. de Miguel, F. Pérez
Variables condicionales
• Variables de sincronización asociadas a un mutex • Conveniente ejecutarlas entre lock y unlock
• Dos operaciones atómicas: – wait Bloquea al proceso ligero que la ejecuta y le expulsa del mutex– signal Desbloquea a uno o varios procesos suspendidos en la variable
condicional. El proceso que se despierta compite de nuevo por el mutex
Sistemas operativos: una visión aplicada 27 © J. Carretero, F. García, P. de Miguel, F. Pérez
Variables condicionales (II)
Proceso ligero B
Proceso ligero A
waitunlock mutex
Adquiere el mutex
Adquiere el mutex
Se compite por el mutex
locklock
unlock
Proceso ligero bloqueado esperando signal
Proceso ligero bloqueado esperando unlock
signal
Sistemas operativos: una visión aplicada 28 © J. Carretero, F. García, P. de Miguel, F. Pérez
Uso de mutex y variables condicionales
• Proceso ligero A lock(mutex); /* acceso al recurso */
comprobar las estructuras de datos;
while (recurso ocupado)
wait(condition, mutex);
marcar el recurso como ocupado;
unlock(mutex);
• Proceso ligero B lock(mutex); /* acceso al recurso */
marcar el recurso como libre;
signal(condition, mutex);
unlock(mutex);
• Importante utilizar while
Sistemas operativos: una visión aplicada 29 © J. Carretero, F. García, P. de Miguel, F. Pérez
Contenido
• Procesos concurrentes. • Problemas clásicos de comunicación y sincronización. • Mecanismos de comunicación y sincronización.
• Paso de mensajes.• Aspectos de implementación• Interbloqueos. • Servicios POSIX• Servicios Win32
Sistemas operativos: una visión aplicada 30 © J. Carretero, F. García, P. de Miguel, F. Pérez
Paso de mensajes• Permite resolver:
– Exclusión mutua – Sincronizar entre un proceso que recibe un mensaje y otro que lo envía – Comunicación de datos entre espacios de memoria diferentes (mismo
computador, diferentes computadores)
• Primitivas básicas: – send(destino, mensaje)envía un mensaje al proceso destino – receive(destino, mensaje)recibe un mensaje del proceso destino
• Múltiples soluciones • Aspectos de diseño
– Tamaño del mensaje– Flujo de datos (unidireccional, bidireccional)– Nombrado
• Directo• Indirecto (puertos, colas)
– Sincronización (síncrono, asíncrono)– Almacenamiento
Sistemas operativos: una visión aplicada 31 © J. Carretero, F. García, P. de Miguel, F. Pérez
Uso de colas y puertos
Comunicación con puertosComunicación con colas de mensajes
Proceso cliente Proceso clientesend
mensaje
receive
Cola de mensajes
Proceso cliente Proceso cliente
mensaje
Puertosend
Sistemas operativos: una visión aplicada 32 © J. Carretero, F. García, P. de Miguel, F. Pérez
Servidor multithread con colas de mensajes
Proceso cliente
Cola del cliente
Proceso cliente
Cola del cliente
Cola del servidor
Proceso servidor
petición
petición
respuestarespuesta
Creación delthread
Creación delthread
Thread quesirve la petición
Thread quesirve la petición
Sistemas operativos: una visión aplicada 33 © J. Carretero, F. García, P. de Miguel, F. Pérez
Contenido
• Procesos concurrentes. • Problemas clásicos de comunicación y sincronización. • Mecanismos de comunicación y sincronización.• Paso de mensajes.
• Aspectos de implementación• Interbloqueos. • Servicios POSIX• Servicios Win32
Sistemas operativos: una visión aplicada 34 © J. Carretero, F. García, P. de Miguel, F. Pérez
Implementación de mecanismos de sincronización
• Espera activa:wait(s) {
s = s – 1;while (s < 0)
;
signal(s) {s = s + 1;
• Espera pasivawait(s) {
s = s – 1;if (s < 0)
Bloquear al proceso;
signal(s) {s = s + 1;if (s <= 0)
Desbloquear a un proceso bloqueado en la operación wait;}
Sistemas operativos: una visión aplicada 35 © J. Carretero, F. García, P. de Miguel, F. Pérez
Implementación de la espera pasiva
• Operaciones para bloquear a un proceso en un semáforo
(a)
Tabla de procesos
BCP1 BCP7BCP2 BCP8BCP3 BCP9BCP4 BCP10BCP5 BCP11BCP6 BCP12
1 90 56 11 87 0
Cola asociada al semáforo 7
(b)
Tabla de procesos
BCP1 BCP7BCP2 BCP8BCP3 BCP9BCP4 BCP10BCP5 BCP11BCP6 BCP12
1 90 56 11 87Bloq.
Bloq. Ejec.EstadoPID
EstadoPID
Bloq. Bloq.0
Cola asociada al semáforo
7 11
Sistemas operativos: una visión aplicada 36 © J. Carretero, F. García, P. de Miguel, F. Pérez
Implementación de la espera pasiva
• Operaciones para desbloquear a un proceso bloqueado en un semáforo
(a)
(b)
Tabla de procesos
BCP1 BCP7BCP2 BCP8BCP3 BCP9BCP4 BCP10BCP5 BCP11BCP6 BCP12
1 90 56 11 87ListoEstado
PIDBloq. Bloq.
0
Cola asociada al semáforo 11
Tabla de procesos
BCP1 BCP7BCP2 BCP8BCP3 BCP9BCP4 BCP10BCP5 BCP11BCP6 BCP12
1 90 56 11 87Bloq.Estado
PIDBloq. Bloq.
0
Cola asociada al semáforo
7 11
Sistemas operativos: una visión aplicada 37 © J. Carretero, F. García, P. de Miguel, F. Pérez
Contenido
• Procesos concurrentes. • Problemas clásicos de comunicación y sincronización. • Mecanismos de comunicación y sincronización.• Paso de mensajes.• Aspectos de implementación
• Interbloqueos. • Servicios POSIX• Servicios Win32
Sistemas operativos: una visión aplicada 38 © J. Carretero, F. García, P. de Miguel, F. Pérez
Interbloqueos
• Bloqueo permanente de un conjunto de procesos que compiten por los recursos del sistema o se comunican entre sí.
• Ejemplo: Si P y Qcon semáforos con valor inicial 1
P1 P2wait(P) wait(Q)wait(Q) wait(P)
... ...signal(P) signal(Q)signal(Q) siangl(P)
Sistemas operativos: una visión aplicada 39 © J. Carretero, F. García, P. de Miguel, F. Pérez
Ejemplo de interbloqueo
Q
P
BA
Sistemas operativos: una visión aplicada 40 © J. Carretero, F. García, P. de Miguel, F. Pérez
Interbloqueos II
• Ejemplo: Si C1 y C2 son dos colas de mensajes:
P1 P2receive(P2, M) receive(P1, N)
... ...send(P2, M) send(P1, N)
• Condiciones del interbloqueo: – Exclusión mutua – Retención y espera – No apropiación – Espera circular