PDF de programación - Concurrencia de Procesos: Exclusión Mutua y Sincronización

Sistemas Operativos

Concurrencia de Procesos: Exclusión Mutua y Sincronización

Eloy Anguiano Rey

[email protected]

Rosa M. Carro

[email protected]

Ana González

[email protected]

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Concurrencia de

Procesos:

Exclusión Mutua y

Sincronización

Introducción

Memoria
compartida en
UNIX

Sincronización

Exclusión mutua

Soluciones
software

Soluciones
hardware

Semáforos

Monitores

Mensajes

Introducción
Elementos a tener en cuenta

Afecta a ..

... la comunicación entre procesos.

... la compartición y competencia por los recursos.

... la sincronización de la ejecución de varios procesos.

... la asignación del tiempo de procesador a los procesos.

Presente en ...

... la ejecución de múltiples aplicaciones:

Multiprogramación

... las aplicaciones estructuradas:

Algunas aplicaciones pueden implementarse eficazmente como un conjunto de
procesos concurrentes.

... la estructura del sistema operativo:

Algunos sistemas operativos están implementados como un conjunto de
procesos o hilos.

Concurrencia de

Procesos:

Exclusión Mutua y

Sincronización

Introducción
Elementos a tener en
cuenta
Términos clave
Dificultades
Ejemplos de
problemas

Memoria
compartida en
UNIX

Sincronización

Exclusión mutua

Soluciones
software

Soluciones
hardware

Semáforos

Monitores

Introducción
Términos clave

Concurrencia de

Procesos:

Exclusión Mutua y

Sincronización

Introducción
Elementos a tener en
cuenta
Términos clave
Dificultades
Ejemplos de
problemas

Memoria
compartida en
UNIX

Sincronización

Exclusión mutua

Soluciones
software

Soluciones
hardware

Semáforos

Monitores

Sincronización: Los procesos coordinan sus actividades

Sección crítica: Región de código que sólo puede ser accedida por un proceso

simultáneamente (variables compartidas).

Exclusión mutua: Sólo un proceso puede estar en sección crítica accediendo a

recursos compartidos

Interbloqueo: Varios procesos, todos tienen algo que otros esperan, y a su vez

esperan algo de los otros.

Círculo vicioso: Procesos cambian continuamente de estado como respuesta a

cambios en otros procesos, sin que sea útil (ej: liberar recurso)

Condición de carrera: Varios hilos/procesos leen y escriben dato compartido. El

resultado final depende de coordinación.

Inanición: Proceso que está listo nunca se elige para ejecución

Introducción
Dificultades con la concurrencia

La ejecución intercalada de procesos mejora rendimiento, pero ... la velocidad
relativa de los procesos no puede predecirse puesto que depende de:

Actividades de otros procesos
Forma de tratar interrupciones
Políticas de planificación

Pero esto implica que surgen dificultades
Ejemplo

Hora Mi compañera

Yo

Sale hacia la tienda
Entra en la tienda
Compra leche
Sale de la tienda
Llega a casa y guarda la leche

3:00 Mira en la nevera No hay leche
3:05
3:10
3:15
3:20
3:25
3:30
3:35

Miro en la nevera No hay leche
Salgo hacia la tienda
Entro en la tienda
Compro leche
Salgo de la tienda
Llego a casa y guarda la leche OH OH!!!

Concurrencia de

Procesos:

Exclusión Mutua y

Sincronización

Introducción
Elementos a tener en
cuenta
Términos clave
Dificultades
Ejemplos de
problemas

Memoria
compartida en
UNIX

Sincronización

Exclusión mutua

Soluciones
software

Soluciones
hardware

Semáforos

Monitores

Introducción
Dificultades con la concurrencia

La imprevisibilidad de la velocidad relativa de los procesos implica que es
difícil ...

... compartir recursos. Ej: orden de lecturas y escrituras.

... gestionar la asignación óptima de recursos. Ej: recursos asignados a un
proceso y éste se bloquea, ¿recurso bloqueado? ⇒ posible interbloqueo
... detectar errores de programación (resultados no deterministas, no
reproducibles)

Concurrencia de

Procesos:

Exclusión Mutua y

Sincronización

Introducción
Elementos a tener en
cuenta
Términos clave
Dificultades
Ejemplos de
problemas

Memoria
compartida en
UNIX

Sincronización

Exclusión mutua

Soluciones
software

Soluciones
hardware

Semáforos

Monitores

Introducción
Ejemplos de problemas

Supóngase que se lanzan dos procesos idénticos con la siguiente estructura:

1
2
3
4
5
6

void echo()
{

ent = getchar();
sal = ent;
putchar(sal);

}

Cuando se ejecutan los dos simultáneamente la ejecución puede ser la
siguiente:

1
2
3
4
5
6

...
ent = getchar();
...
...
sal = ent;
putchar(sal);

1
2
3
4
5
6
7

...
...
ent = getchar();
sal = ent;
...
...
putchar(sal);

Concurrencia de

Procesos:

Exclusión Mutua y

Sincronización

Introducción
Elementos a tener en
cuenta
Términos clave
Dificultades
Ejemplos de
problemas

Memoria
compartida en
UNIX

Sincronización

Exclusión mutua

Soluciones
software

Soluciones
hardware

Semáforos

Monitores

Introducción
Ejemplos de problemas

Concurrencia de

Procesos:

Exclusión Mutua y

Sincronización

Introducción
Elementos a tener en
cuenta
Términos clave
Dificultades
Ejemplos de
problemas

Memoria
compartida en
UNIX

Sincronización

Exclusión mutua

Soluciones
software

Soluciones
hardware

Semáforos

Monitores

Supóngase la ejecución de estos dos procesos con variables compartidas
Proceso A

Proceso B

1
2
3

for(i=1 to 5) do {
}

x=x+1;

1
2
3

for(j=1 to 5) do {
}

x=x+1;

con las siguientes condiciones:

Valor inicial x=0.

Se comparten todas las variables.
La operación de incremento se realiza en tres instrucciones atómicas:

1 LD ACC, # (Carga el contenido de una dirección en el ACC).
2 ACC++ (Incrementa el acumulador).
3 SV ACC, # (Almacena el valor del acumulador en una dirección).
Ejercicio: calcula todos los valores posibles de salida para la variable x.

Introducción
Ejemplos de problemas

Caso mínimo

i

1

inst

BCPa

Acc

LD Acc

0

0
0

X

0
0

BCPb

inst

LD Acc

j

1

Concurrencia de

Procesos:

Exclusión Mutua y

Sincronización

Introducción
Elementos a tener en
cuenta
Términos clave
Dificultades
Ejemplos de
problemas

Memoria
compartida en
UNIX

Sincronización

Exclusión mutua

Soluciones
software

Soluciones
hardware

Semáforos

Monitores

Introducción
Ejemplos de problemas

Caso mínimo

i

1

inst

BCPa

Acc

X

BCPb

inst

LD Acc

0
0
0
0
0
0
0
0
0
0
0
0
Acc++ 0

0
0
1
1
1
2
2
2
3
3
3
4
4
1

0
0
0
1
1
1
2
2
2
3
3
3
4
4

4

LD Acc
Acc++
SV Acc
LD Acc
Acc++
SV Acc
LD Acc
Acc++
SV Acc
LD Acc
Acc++
SV Acc

j

1

2

3

4

Concurrencia de

Procesos:

Exclusión Mutua y

Sincronización

Introducción
Elementos a tener en
cuenta
Términos clave
Dificultades
Ejemplos de
problemas

Memoria
compartida en
UNIX

Sincronización

Exclusión mutua

Soluciones
software

Soluciones
hardware

Semáforos

Monitores

Introducción
Ejemplos de problemas

Caso mínimo

i

1

inst

BCPa

Acc

X

BCPb

inst

LD Acc

0
0
0
0
0
0
0
0
0
0
0
0
Acc++ 0
SV Acc
0

0
0
1
1
1
2
2
2
3
3
3
4
4
1
1

0
0
0
1
1
1
2
2
2
3
3
3
4
4
1

4
4

LD Acc
Acc++
SV Acc
LD Acc
Acc++
SV Acc
LD Acc
Acc++
SV Acc
LD Acc
Acc++
SV Acc

j

1

2

3

4

Concurrencia de

Procesos:

Exclusión Mutua y

Sincronización

Introducción
Elementos a tener en
cuenta
Términos clave
Dificultades
Ejemplos de
problemas

Memoria
compartida en
UNIX

Sincronización

Exclusión mutua

Soluciones
software

Soluciones
hardware

Semáforos

Monitores

Introducción
Ejemplos de problemas

Caso mínimo

i

1

inst

BCPa

Acc

LD Acc

0

0
0

X

0
0

BCPb

inst

LD Acc

j

1

Concurrencia de

Procesos:

Exclusión Mutua y

Sincronización

Introducción
Elementos a tener en
cuenta
Términos clave
Dificultades
Ejemplos de
problemas

Memoria
compartida en
UNIX

Sincronización

Exclusión mutua

Soluciones
software

Soluciones
hardware

Semáforos

Monitores

Introducción
Ejemplos de problemas

Caso mínimo

j

5

i

2

3

4

5

inst

BCPa

Acc

X

BCPb

inst

1
LD Acc
1
Acc++ 1
1
SV Acc
LD Acc
1
Acc++ 1
SV Acc
1
LD Acc
1
Acc++ 1
1
SV Acc
LD Acc
1
Acc++ 1
1
SV Acc

1
1
2
2
2
3
3
3
4
4
4
5
5
2

4
1
1
1
1
1
1
1
1
1
1
1
1

1
1
1
2
2
2
3
3
3
4
4
4
5
5

LD Acc

Acc++

Concurrencia de

Procesos:

Exclusión Mutua y

Sincronización

Introducción
Elementos a tener en
cuenta
Términos clave
Dificultades
Ejemplos de
problemas

Memoria
compartida en
UNIX

Sincronización

Exclusión mutua

Soluciones
software

Soluciones
hardware

Semáforos

Monitores

Introducción
Ejemplos de problemas

Caso mínimo

j

5

i

2

3

4

5

inst

BCPa

Acc

X

BCPb

inst

1
1
LD Acc
Acc++ 1
1
SV Acc
LD Acc
1
Acc++ 1
SV Acc
1
LD Acc
1
Acc++ 1
1
SV Acc
LD Acc
1
Acc++ 1
SV Acc
1

1
1
2
2
2
3
3
3
4
4
4
5
5
2
2

4
1
1
1
1
1
1
1
1
1
1
1
1

1
1
1
2
2
2
3
3
3
4
4
4
5
5
2

X=2

LD Acc

Acc++
SV Acc

Concurrencia de

Procesos:

Exclusión Mutua y

Sincronización

Introducción
Elementos a tener en
cuenta
Términos clave
Dificultades
Ejemplos de
problemas

Memoria
compartida en
UNIX

Sincronización

Exclusión mutua

Soluciones
software

Soluciones
hardware

Semáforos

Monitores

Introducción
Ejemplos de problemas

Caso máximo

i

inst

BCPa

Acc

X

BCPb

inst

0
1
1
1
2
2
2
3
3
3
4
4
4
5
5

0
0
1
1
1
2
2
2
3
3
3
4
4
4
5

LD Acc
Acc++
SV Acc
LD Acc
Acc++
SV Acc
LD Acc
Acc++
SV Acc
LD Acc
Acc++
SV Acc
LD Acc
Acc++
SV Acc

j

1

2

3

4

5

Concurrencia de

Procesos:

Exclusión Mutua y

Sincronización

Introducción
Elementos a tener en
cuenta
Términos clave
Dificultades
Ejemplos de
problemas

Memoria
compartida en
UNIX

Sincronización

Exclusión mutua

Soluciones
software

Soluciones
hardware

Semáforos

Monitores

Introducción
Ejemplos de problemas

Caso máximo

BCPb

inst

j

i

1

2

3

4

5

inst

BCPa

Acc

LD Acc
Acc++
SV Acc
LD Acc
Acc++
SV Acc
LD Acc
Acc++
SV Acc
LD Acc
Acc++
SV Acc
LD Acc
Acc++
SV Acc

5
6
6
6
7
7
7
8
8
8
9
9
9
10
10

X

5
5
6
6
6
7
7
7
8
8
8
9
9
9
10

X=10

Concurrencia de

Procesos:

Exclusión Mutua y

Sincronización

Introducción
Elementos a tener en
cuenta
Términos clave
Dificultades
Ejemplos de
problemas

Memoria
compartida en
UNIX

Sincronización

Exclusión mutua

Soluciones
software

Soluciones
hardwa