PDF de programación - Sistemas Operativos I - Tema 4 - Comunicación y sincronización de procesos

Sistemas Operativos I

Tema 4

Comunicación y

sincronización de procesos

Equipo de Sistemas Operativos DISCA / DSIC

UPV

Comunicación y sincronización de procesos
 Objetivos

 Presentar dos alternativas básicas para comunicación entre procesos


Memoria común

Mensajes

 Analizar las condiciones de carrera y estudiar el concepto de seriabilidad.
 Estudiar, en el caso de memoria común, el problema de la sección critica.
 Presentar los criterios de corrección al problema de la sección critica y

sus posibles soluciones de una forma estructurada:


Soluciones hardware

Semáforos

Realización de semáforos mediante soluciones hardware.

 Adquirir destreza en la resolución de problemas de sincronización a través
de problemas clásicos (productores y consumidores, lectores y escritores,
cinco filósofos, etc.)

Sistemas Operativos I (00-01)

Comunicación y sincronización de Procesos

2

1

Comunicación y sincronización de procesos
 Contenido

 Bibliografia

 A. Silberschatz, J. Peterson , P.
Galvin.
Operativos.
Conceptos Fundamentales. 5ª ed.
Capítulo 6.

Sistemas

 A. Tanenbaum. Modern Operating

Systems. Capítulos 2,11 y 12

1.- Introducción
2.- Comunicación por memoria común
3.- El problema de la sección crítica
4.- Soluciones hardware
5.- Semáforos
6.- Problemas clásicos de

programación concurrente

7.- Construcciones lingüísticas
8.- Sincronización en POSIX
9.- Comunicación por mensajes

Sistemas Operativos I (00-01)

Comunicación y sincronización de Procesos

3

Comunicación y sincronización de procesos

 Contenido

1.- Introducción
2.- Comunicación por memoria común
3.- El problema de la sección crítica
4.- Soluciones hardware
5.- Semáforos
6.- Problemas clásicos de programación concurrente
7.- Construcciones lingüísticas
8.- Sincronización en POSIX
9.- Comunicación por mensajes

Sistemas Operativos I (00-01)

Comunicación y sincronización de Procesos

4

2

1.Introducción
 Existe la necesidad de comunicación entre procesos.
 Los procesos requieren con frecuencia comunicación entre ellos

(ejemplo: tubos).

 La comunicación entre procesos puede seguir dos esquemas

básicos:

 Comunicación por memoria común

 Comunicación por mensajes

Sistemas Operativos I (00-01)

Comunicación y sincronización de Procesos

5

1.Introducción

 Comunicación por memoria común

 La comunicación por memoria
los

común se puede dar en
siguientes casos:


Espacio de direcciones único: es el

caso de los hilos de ejecución


El s.o. crea una zona de memoria

accesible a un grupo de procesos

 Problema de la sección crítica:
en un sistema con procesos
concurrentes que se comunican
compartiendo datos comunes es
necesario sincronizar el acceso
(lectura, escritura) a
los datos
compartidos para asegurar
la
consistencia de los mismos.

P1

Hilo 1

Hilo 2

Datos

compartidos

Sistemas Operativos I (00-01)

Comunicación y sincronización de Procesos

6

3

1.Introducción
 Comunicación por mensajes

 La comunicación por mensajes se da “normalmente” en el siguiente caso:


Espacio de direcciones independentes

 Sincronización en la comunicación por mensajes: Cuando dos procesos
se comunican vía mensajes se necesitan mecanismos para que el
proceso receptor espere (se suspenda hasta) a que el proceso emisor
envíe el mensaje y éste esté disponible.

 No aparece el problema de la sección crítica.

P1

P2

mensaje

Sistemas Operativos I (00-01)

Comunicación y sincronización de Procesos

7

Comunicación y sincronización de procesos

 Contenido

1.- Introducción
2.- Comunicación por memoria común
3.- El problema de la sección crítica
4.- Soluciones hardware
5.- Semáforos
6.- Problemas clásicos de programación concurrente
7.- Construcciones lingüísticas
8.- Sincronización en POSIX
9.- Comunicación por mensajes

Sistemas Operativos I (00-01)

Comunicación y sincronización de Procesos

8

4

2.Comunicación por memoria común
 El problema de los productores y consumidores con buffer acotado

 Productor: proceso que produce elementos (a una cierta velocidad) y los
deposita en un buffer.
 Consumidor: proceso que toma elementos del buffer y los consume (a
una velocidad probablemente diferente a la del productor)
 Buffer: Estructura de datos que sirve para intercambiar información entre
los procesos productores y consumidores. Actúa a modo de depósito para
absorber la diferencia de velocidad entre productores y consumidores

 Ejemplo: buffer de impresora.

Sistemas Operativos I (00-01)

Comunicación y sincronización de Procesos

9

2.Comunicación por memoria común
 El problema de los productores y consumidores con buffer acotado

C1

C2

Consumidores

salida

buffer

contador

entrada

Productores

P1

P2

Sistemas Operativos I (00-01)

Comunicación y sincronización de Procesos

10

5

2.Comunicación por memoria común
 Productores y consumidores con buffer acotado
Variables compartidas:
Variables compartidas:

var buffer: array[0..n-1]
var buffer: array[0..n-1]

proceso consumidor:
proceso consumidor:
task consumidor;
task consumidor;

of elemento;
of elemento;

entrada:=0, salida:=0 : 0..n-1;
entrada:=0, salida:=0 : 0..n-1;
contador:= 0 : 0..n;
contador:= 0 : 0..n;

proceso productor:
proceso productor:
task productor;
task productor;

var item: elemento;
var item: elemento;
repeat
repeat
item := producir();
item := producir();
while contador= n do no-op;
while contador= n do no-op;
buffer[entrada] := item;
buffer[entrada] := item;
entrada := (entrada +1) mod n;
entrada := (entrada +1) mod n;
contador:=contador+1;
contador:=contador+1;
until false
until false
end productor;
end productor;

var item: elemento;
var item: elemento;
repeat
repeat
while contador= 0 do no-op;
while contador= 0 do no-op;
item := buffer[salida]
item := buffer[salida]
salida := (salida +1) mod n;
salida := (salida +1) mod n;
contador:=contador-1;
contador:=contador-1;
consumir(item);
consumir(item);
until false
until false

end consumidor;
end consumidor;

Sistemas Operativos I (00-01)

Comunicación y sincronización de Procesos

11

2.Comunicación por memoria común
 Condiciones de carrera

 Corrección en programes secuenciales: el programa cumple con sus
especificaciones (responde a unos invariantes o reglas de corrección).
Corrección secuencial no implica corrección concurrente: Un
programa que tiene una implementación “secuencialmente correcta”
(correcta con un sólo hilo de ejecución) puede presentar problemas
cuando se intenta introducir concurrencia en forma de hilos de ejecución.
 Condición de carrera: la ejecución de un conjunto de operaciones
concurrentes sobre una variable compartida, deja la variable en un estado
inconsistente con las especificaciones de corrección. Además, el
resultado de la variable depende de la velocidad relativa en que se
ejecutan las operaciones.
 Peligro potencial: Las condiciones de carrera pueden presentarse en
algún escenario, pero no tienen por qué observarse en todas las posibles
trazas de la ejecución del programa.

Sistemas Operativos I (00-01)

Comunicación y sincronización de Procesos

12

6

2.Comunicación por memoria común
 Ejemplo de un escenario de condición de carrera

Productor:
contador:= contador+1;
mov reg1, contador;
mov reg1, contador;
inc reg1;
inc reg1;
mov contador, reg1;
mov contador, reg1;

Inicialmente:
contador =5



inc reg1

T Proceso Operación
0
1
2
3
4
5

Prod. mov contador, reg1
Prod.
Cons. mov contador, reg2
Cons. dec reg2
Cons. mov reg2, contador
Prod mov reg1, contador

Consumidor:
contador:= contador-1;
mov reg2, contador;
mov reg2, contador;
dec reg2;
dec reg2;
mov contador, reg2;
mov contador, reg2;

reg1 reg2
?
?
5
4
4
?

5
6
?
?
?
6

contador

5
5
5
5
4
6

incorrecto

Sistemas Operativos I (00-01)

Comunicación y sincronización de Procesos

13

2.Comunicación por memoria común
 Criterio de corrección en programas concurrentes
El criterio de corrección/consistencia más usual para programas concurrentes
es:

 Seriabilidad (consistencia secuencial): El resultado de la ejecución
concurrente de un conjunto de operaciones ha de ser equivalente al
resultado de ejecutar secuencialmente cada una de las operaciones, en
alguno de los ordenes secuenciales posibles.

Condición de carrera = no seriabilidad: no hay ninguna posible
ejecución secuencial de un conjunto de operaciones que de el mismo
resultado que la ejecución concurrente.

Sistemas Operativos I (00-01)

Comunicación y sincronización de Procesos

14

7

2.Comunicación por memoria común
 Ejemplo de seriabilidad

La ejecución concurrente de op1, op2 y op3 :

op1 || op2 || op3

se considera correcta si el estado final de los datos compartidos es igual al
estado en que quedarían después de alguna de las siguientes ejecuciones
secuenciales:

op1 ; op3 ; op2 o
op1 ; op2 ; op3 o
op2 ; op1 ; op3 o
op2 ; op3 ; op1 o
op3 ; op1 ; op2 o op3 ; op2 ; op1 .

 Ejemplo numérico: sea una variable x con valor inicial 3 sobre la que se

pueden realizar dos operaciones:


op1: incremento de 8

op2: multiplicación por 5

 Resultados correctos de op1 || op2 : 55 y 23

Sistemas Operativos I (00-01)

Comunicación y sincronización de Procesos

15

Comunicación y sincronización de procesos

 Contenido

1.- Introducción
2.- Comunicación por memoria común
3.- El problema de la sección crítica
4.- Soluciones hardware
5.- Semáforos
6.- Problemas clásicos de programación concurrente
7.- Construcciones lingüísticas
8.- Sincronización en POSIX
9.- Comunicación por mensajes

Sistemas Operativos I (00-01)

Comunicación y sincronización de Procesos

16

8

3.El problema de la sección crítica
 Concepto de sección crítica
Una sección crítica es una zona de código en la que se accede a variables
compartidas por varios procesos