Sistemas Operativos y Distribuidos Sincronización

Material Adicional (SOSD – Mod 4)

Concurrencia CONCURRENCIA
Exclusión mutua y sincronización

Slides de Samuel Oporto Díaz

2

Concurrencia Concurrencia
• La concurrencia es la simultaneidad de hechos. • Un programa concurrente está formado por una colección
• Un programa concurrente es aquel en el que ciertas de procesos secuenciales autónomos que se ejecutan
unidades de ejecución internamente secuenciales (aparentemente) en paralelo.
(procesos o threads), se ejecutan paralela o • Tres formas de ejecutar procesos concurrentes:
simultáneamente.
1. Los procesos multiplexan sus ejecuciones sobre un
único procesador (multiprogramación).
• Incluye los siguientes aspectos:
– comunicación entre procesos. 2. Los procesos multiplexan sus ejecuciones sobre un
– compartición y competencia por los recursos. sistema multiprocesador de memoria compartida
– sincronización de la ejecución de varios procesos. (multiproceso).
– asignación del tiempo de procesador a los procesos. 3. Los procesos multiplexan sus ejecuciones en varios
procesadores que no comparten memoria
• Surgen en entornos con un solo procesador, con (procesamiento distribuido).
multiprocesadores y proceso distribuido. • El término concurrencia indica paralelismo potencial.
3 4

Concurrencia Concurrencia
• En un sistema multiprogramado (1 µP), los procesos se
intercalan, para dar la apariencia de simultaneidad.
P1

P2

P3

• En un sistema con varios procesadores (n µP), los

procesos se superponen.
multiprogramación multiproceso Procesamiento P1
distribuido
P2

P3

5 6

Prof. Javier Echaiz 1

Sistemas Operativos y Distribuidos Sincronización

Dificultades con la Concurrencia Un ejemplo simple

• Los problemas generados por la multiprogramación
surgen por que no es posible predecir la velocidad
relativa de los procesos:

• La actividad de un proceso depende de la actividad de

los otros procesos y de la forma cómo el SO trata las chin
interrupciones y las políticas de planificación. chout

• Dificultades:
– Compartir recursos globales (variable global)
P1 P2
– Manejar la asignación de recursos
– Detectar un error es difícil, dado que es difícil
reproducir la situación..

7 8

un ejemplo simple un ejemplo simple

void echo() Process P1 Process P2
{ . .
char_in = getchar(); chin = getchar(); . chin = a
char_out = char_in; . chin = getchar(); chin = b
putchar(char_out); chout = chin; chout = chin;
} putchar(chout); .
. putchar(chout);
. .

Conclusiones:
Se asume que esta función es usada por muchos procesos en el SO y Proteger las variables compartidas.
dado que existe una sola pantalla y un solo teclado, todos los programas ¿cómo?
interactúan con este programa. Por lo que lo que es recomendable Evitando que otro proceso ejecute a echo hasta que el proceso actual termine.
tenerlo siempre en memoria Evitando que el proceso actual sea interrumpido hasta que termine

9 10

Tipos de proceso

INTERACCION ENTRE Independientes Cooperantes

Su estado no es compartido Su estado es compartido
PROCESOS Son deterministas Su funcionamiento no es
determinista
Son reproducibles Su funcionamiento puede ser
irreproducible
Ejemplo: Un programa que calcula Ejemplo: un proceso que escribe en
1000 cifras decimales de π el terminal la cadena “abc” y en otro
la cadena “cba”

11 12

Prof. Javier Echaiz 2

Sistemas Operativos y Distribuidos Sincronización

Interacción entre procesos Interacción entre procesos

• La concurrencia se presenta cuando existen: • Existen tres maneras en que los
– multiprogramación de aplicaciones independientes. procesos interactúan:
1 competencia por recursos escasos. •Interbloqueo
– Los procesos no conocen a los •Inanición
– aplicaciones con varios procesos. demás •Exclusión mutua

– el uso de las estructuras de datos del SO. 2 cooperación por compartición •Interbloqueo
– Los procesos conocen •Inanición
– el computador se dispone de varios procesadores. indirectamente a los demás •Exclusión mutua
•Coherencia de datos

3 cooperación por comunicación

(multiprogramación). – Los proceso conocen directamente a •Interbloqueo
(multiproceso). los otros. •Inanición
(procesamiento distribuido).

13 14

1 Competencia por recursos escasos Ejemplo

Recursos
• Los procesos compiten por recursos escasos. disponibles

• Si dos procesos compiten por un recurso

• el SO asigna el recurso a uno y el otro espera

• Problemas.
– Interbloqueo (estancamiento) P1 P2 P3 P1 P2 P3 P1 P2 P3 P1 P2 P3 P1 P2 P3
– Inanición Estado Estado Estado Estado Estado
– Exclusión mutua inicial seguro seguro inseguro inseguro

15 16

2 La cooperación por compartición Ejemplo

• Los procesos no se conocen. Ejecución consistente
• Los procesos cooperan para evitar inconsistencias P1: a = a + 1
• Recursos compartidos: b=b+1 a=a+1 b=b+1 b = 2 *b a = 2 *a
– variables compartidas P2: b = 2 * b
– ficheros
a = 2 *a
– bases de datos
• Problema
Ejecución concurrente
– Confianza
P1: a = a + 1
P2: b = b * 2
• Solución a=a+1 b=b*2 b=b+1 a = 2 *a
• La escritura debe ser mutuamente excluyente.
P1: b = b + 1
– Exclusión mutua

P2: a = 2 *a
– Sección crítica
• La lectura puede ser concurrente

17 18

Prof. Javier Echaiz 3

Sistemas Operativos y Distribuidos Sincronización

3
La cooperación para la comunicación
• Los procesos se conocen explícitamente.

• La comunicación se da con mensajes: send, receive.

PROBLEMAS POTENCIALES
• No se comparten recursos
no exclusión mutua.
A RESOLVER
• Problemas.
– Interbloqueo. Cada proceso espera un mensaje del otro proceso

– Inanición. Dos procesan envían sus mensaje mutuamente

mientras que esperan un mensaje del otro proceso

19 20

1. Exclusión mutua 2. Interbloqueo (deadlock)

• Es un mecanismo empleado en el diseño de los sistemas condiciones : P1 requiere R1 y R2
operativos para evitar los problemas de competencia por P2 requiere R1 y R2
recursos, se basa en definir una zona o región crítica la acciones:
cual está marcada por las instrucciones que hacen uso del
recurso en competencia (recurso crítico). 1. P1 obtiene R1
2. P2 obtiene R2
3. P1 Y P2 están bloqueados esperando cada uno al otro
R1 R1 R1

1 0 0

P1 P2 P1 P2 P1 P2

1 1 0
R2 R2 R2

21 22

3. Inanición
• Los procesos siempre están bloqueados y nunca acceden
a los recursos que necesitan

Sean 3 procesos. SECCION CRÍTICA

– P1 solicita recurso.
– P2 y P3 solicitan recursos
– P1 suelta el recurso
– Se asigna el recurso a P2
– P1 solicita el recurso
– P2 suelta el recurso
– Se asigna el recurso a P1

23 24

Prof. Javier Echaiz 4

Sistemas Operativos y Distribuidos Sincronización

Sección Crítica Requerimientos para exclusión mutua

• Es la parte del programa que accede a un 1. Exclusión mutua. Sólo un procese accede a la vez a su SC
recurso compartido Ejemplo:
• Solo un programa puede acceder a su solo un 2. Un proceso suspendido en su SC no debe estorbar a otros
sección crítica en un momento dado proceso en
cada
• NO se puede confiar simplemente en el SO momento 3. No inanición, no interbloqueo. Si un proceso solicita
para hacer cumplir esta restricción estará acceso a su SC no debe demorar su atención.
enviando
Se suspende la comandos
ejecución de la sección
crítica hasta que acabe
a la 4. Si ningún proceso está en su SC, no se puede evitar que
el anterior impresora otro proceso entre a su SC.

sección 5. No suponer la velocidad relativa de los procesos.

crítica

6. Se permanece en la SC por un tiempo finito.

25 26

Intento inicial
PROCESO_UNO PROCESO_DOS PROCESO_PRINCIPAL
procedure proceso_uno procedure proceso_dos begin
begin begin count = 0;
while TRUE do while TRUE do parbegin
begin begin proceso_uno;
obtener_entrada obtener_entrada proceso_dos;

SOLUCIONES DE SOFTWARE entrar_exclusion_mutua

count = count + 1
salir_exclusion_mutua
entrar_exclusion_mutua
count = count + 1
salir_exclusion_mutua
parend;
end.

procesar_entrada procesar_entrada
end end
end; end;

• parbegin, parend hacen que proceso_uno y proceso_dos operen concurrentemente.

• estos procesos se encuentran en un ciclo infinito de entrada/salida a sus secciones

criticas.

27 28

Primer intento Segundo intento

PROCESO_UNO PROCESO_DOS PROCESO_PRINCIPAL PROCESO_UNO PROCESO_DOS PROCESO_PRINCIPAL
procedure proceso_uno procedure proceso_dos begin procedure proceso_uno procedure proceso_dos begin
begin begin turno=1; begin begin p1entro = FALSE;
while TRUE do while TRUE do parbegin while TRUE do while TRUE do p2entro = FALSE;
begin begin proceso_uno; begin begin parbegin
while turno=2 do espera; while turno=1 do espera; proceso_dos; while p2entro do espera; while p1entro do espera; proceso_uno;
seccion_critica_uno; seccion_critica_dos; parend; p1entro = TRUE; p2entro = TRUE proceso_dos;
turno = 2; turno = 1; end. seccion_critica_uno; seccion_critica_dos; parend;
otras_tareas_dos; proceso_dos_proceso; p1entro = FALSE p2entro = FALSE end.
end end otras_tareas_dos; proceso_dos_proceso;
end; end; end end
end; end;

• Cada proceso puede ver el estado del otro pero no alterarlo.

• Los procesos entran a sus SC alternativamente, y el proceso 1 entra primero. • Si un proceso quiere entrar a su SC verifica el estado del otro (false) y luego
• Si uno de los procesos falla entonces el otro proceso quedará bloqueado pone su estatus en true. Al salir pone false en su estado.
indefinidamente.
pp: p1entro = FALSE;
• problemas: problema:
p2en tro = FALSE;
– supuesto de velocidad, prioridad. que P1 y P2 intenten entrar al mismo tiempo a su SC.
p1: while p2entro do;
– sincronización en tándem. (por dos lados). p2: while p1entro do;
El momento en que un proceso determina si puede entrar
a su sección critica y el momento en que informa que esta p1: p1entro = TRUE;
en exclusión mutua. puede ser usado por otro proceso p2: p2entro = TRUE;
para verificar si puede entrar.

29 30

Prof. Javier Echaiz 5

Sistemas Operativos y Distribuidos Sincronización

Tercer intento Cuarto intento

PROCESO_UNO PROCESO_DOS PROCESO_PRINCIPAL PROCESO_UNO PROCESO_DOS PROCESO_PRINCIPAL
procedure proceso_uno procedure proceso_dos begin procedure proceso_uno procedure proceso_uno begin
begin begin p1deseaentrar=FALSE; begin begin p1deseaentrar=FALSE;
while TRUE do while TRUE do p2deseaentrar=FALSE; while TRUE do while TRUE do p2deseaentrar=FALSE;
begin begin parbegin begin begin parbegin
p1deseaentrar = TRUE; p2deseaentrar = TRUE proceso_uno; p1deseaentrar = TRUE; p2deseaentrar = TRUE; proceso_uno;
while p2deseaentrar do espera; while p1deseaentrar do espera; proceso_dos; while p2deseaentrar do while p1deseaentrar do proceso_dos;
seccion_critica_uno; seccion_critica_dos; parend; begin begin parend;
p1deseaentrar = FALSE p2deseaentrar = FALSE end. p1deseaentrar = FALSE p2deseaentrar = FALSE end.
otras_tareas_dos; proceso_dos_proceso; espera de algunos ciclo espera de algunos ciclo
end end p1deseaentrar = TRUE p2deseaentrar = TRUE
end; end; end end
seccion_critica_uno; seccion_critica_uno;
p1deseaentrar = FALSE p2deseaentrar = FALSE
otras_tareas_uno; otras_tareas_dos;
Este algoritmo trata de asegurar que mientras un proceso pasa su verificación ningún otro end end
proceso puede pasar su verificación. end; end;

Se hace uso de las variables p1deseaentrar y p2deseaentrar.

El problema de los algoritmos anteriores es que los procesos podrían bloquearse durante
la verificación.
problema:
Este algoritmo asigna FALSE a su propio indicador durante cierto tiempo, si es que se
cada proceso puede asignar TRUE a su indicador antes de realizar la verificación y por lo
tanto ambos procesos se bloquearían uno al otro (interbloque). encuentra durante la verificación.
Esto permite que el otro proceso salga de la espera con TRUE en su indicador.
La exclusión mutua esta garantizada y no puede haber interbloqueo.

31 32

Cuarto intento Solución correcta

problema: PROCESO_UNO PROCESO_DOS PROCESO_PRINCIPAL

• Pero se puede dar el aplazamiento indefinido, dado que no se puede hacer ningún procedure proceso_uno procedure proceso_uno begin
begin begin p1deseaentrar = FALSE;
supuesto respecto a la velocidad de los procesos. while TRUE do while TRUE do p2deseaentrar = FALSE;
• Así, si los procesos se ejecutan en tándem (alternativamente), begin begin proceso_activo = UNO;
p1deseaentrar = TRUE; p2deseaentrar = TRUE; parbegin
• se puede dar la siguiente secuencia de instrucciones, en la cual ninguno de los procesos while p2deseaentrar do while p1deseaentrar do
proceso_uno;
begin begin
entra a su sección critica: if proceso_activo = DOS then if proceso_activo = UNO then
proceso_dos;
begin begin parend;
p1deseaentrar = FALSE; p2deseaentrar = FALSE; end.
Ciclo PROCESO_UNO PROCESO_DOS
reloj while proceso_activo=DOS do; while proceso_activo=UNO do;
p1deseaentrar = TRUE; p2deseaentrar = TRUE;
1 p1deseaentrar = TRUE end end
2 p2deseaentrar = TRUE end; end;
3 while p2deseaentrar do seccion_critica_uno; seccion_critica_dos;
4 p1deseaentrar = FALSE proceso_activo = DOS proceso_activo = UNO
5 : p1deseaentrar = FALSE p2deseaentrar = FALSE
6 p1deseaentrar = TRUE otras_tareas_uno; otras_tareas_dos;
end end
7 while p1deseaentrar do
end; end;
8 p2deseaentrar = FALSE
9 :
10 p2deseaentrar = TRUE • Cada proceso consigue una vuelta a la sección crítica
11 while p2deseaentrar do
12 p1deseaentrar = FALSE • Si un proceso quiere la sección crítica, pone su bandera y puede tener que
12 : esperar a su vuelta. No hay aplazamiento indefinido.
14 p1deseaentrar = TRUE
• Pero se puede presentar la posibilidad de que uno de los procesos sea
interrumpido luego de salir de su sección critica.
33 34

Algoritmo de Peterson
PROCESO_UNO PROCESO_DOS PROCESO_PRINCIPAL
procedure proceso_uno procedure proceso_dos begin
begin begin p1deseaentrar = FALSE;
while TRUE do while TRUE do p2deseaentrar = FALSE;
begin begin proceso_activo = UNO;
p1deseaentrar = TRUE;
proceso_activo = DOS
while p2deseaentrar and
p2deseaentrar = TRUE;
proceso_activo = UNO
while p2deseaentrar and
parbegin
proceso_uno;
proceso_dos;
SOLUCIONES DE HARDWARE
proceso_activo = DOS proceso_activo = UNO parend;
do espera; do espera; end.
seccion_critica_uno; seccion_critica_uno;
p1deseaentrar = FALSE p2deseaentrar = FALSE
otras_tareas_uno; otras_tareas_dos;
end end
end; end;

35 36

Prof. Javier Echaiz 6

Sistemas Operativos y Distribuidos Sincronización

Inhabilitación de interrupciones Instrucciones especiales de máquina

• Un proceso corre hasta que invoca un servicio del SO o • Ejecutó en un ciclo de instrucción sencillo
hasta que es interrumpido. • No sujeto a la interferencia de otras instrucciones
• Deshabilitar interrupciones garantiza la exclusión mutua.
• Leyendo y escribiendo
• Pero el µP es limitado en su habilidad para intercalar
programas • Leyendo y probando

• Multiproceso
– inhabilitar interrupciones puede no garantizar la
exclusión mutua • Instrucción comparar y fijar (test y set)
• Instrucción intercambiar

37 38

Instrucciones test y set Instrucción intercambiar

boolean testset (int i) { void exchange(int register,
if (i == 0) { int memory) {
i = 1;
return true;
int temp;
} temp = memory;
else { memory = register;
return false;
register = temp;
}
} }

39 40

Ventajas de soluciones con hardware Ventajas de soluciones con hardware

• Pertinente a muchos procesos en un procesador • Que espera ocupado consuma tiempo de unidad central de
sencillo o procesadores múltiples dividiendo la memorial proceso
principal • El hambre es posible cuando un proceso deja una sección
• Es simple y por lo tanto fácil de verificar crítica y más de un proceso están esperando.
• Puede estar acostumbrado a soportar secciones críticas • Estancamiento
múltiples – Si un bajo proceso de prioridad tiene la región crítica y
unas necesidades de proceso de prioridad más altas, el
proceso de prioridad más alto obtendrá el procesador
para esperar a la región crítica

41 42

Prof. Javier Echaiz 7

Sistemas Operativos y Distribuidos Sincronización

Semáforos
• La variable especial llamado un semáforo es usado para
comunicar
• Si un proceso está esperando para una señal, es
SEMAFOROS suspendido hasta esa señal se envía
• Espera y operaciones de señales no pueden ser
interrumpidas
• Forme fila están acostumbrado a tener los procesos
esperando en el semáforo

43 44

Semáforos Problema del Productor - Consumidor

• El semáforo es una variable que tiene un valor de entero, • Unos o más productores están generando datos y
número entero poniendo estos en un parachoques
– El mayo se inicializa a un número no negativo • un consumidor sencillo está tomando artículos fuera del
– La operación de espera decrementa el valor de semáforo parachoques un a ratos
– Los incrementos de operación de señales comunican por señales
• Sólo un productor o consumidor puede acceder el
valor
parachoques a cualquier un tiempo

45 46

Productor Consumidor
producer: consumer:
while (true) { while (true) {
/* produce item v */ while (in <= out)
b[in] = v; /*do nothing */;
w = b[out];
in++;
out++;
}
/* consume item w */
}

47 48

Prof. Javier Echaiz 8

Sistemas Operativos y Distribuidos Sincronización

El productor con Buffer Circular El consumidor con Circular Buffer

producer: consumer:
while (true) { while (true) {
/* produce item v */ while (in == out)
while ((in + 1) % n == out) /* do nothing /* do nothing */;
*/; w = b[out];
b[in] = v; out = (out + 1) % n;
/* consume item w */
in = (in + 1) % n
}
}

49 50

Buffer Circular Finito Parachoques infinito

51 52

Problema de barbería

MONITORES

53 54

Prof. Javier Echaiz 9

Sistemas Operativos y Distribuidos Sincronización

Estructura de
Monitores
un monitor
• El monitor es un módulo de software
• Características principales
– Las variables de datos locales son accesibles sólo por el monitor
– Procese entre monitor invocando unos de sus procedimientos
– Sólo un procese pueda estar ejecutando en el monitor a la vez

55

Paso de mensajes
• Imponga exclusión mutua
• Información de cambio

PASO DE MENSAJES envie ( destino, envie mensajes)

reciba ( fuente, envie mensajes)

57 58

Sincronización Sincronización
• Remitente y receptor no pueden o no pueden estar • El Nonblocking envia, bloqueando reciba
bloqueando ( esperando para mensaje) – El remitente continúa el proceso tales como mensajes de
• El entramado envia, bloqueando reciba transmisión tan pronto como sea posible
– El receptor es bloqueado hasta el mensaje pedido llegue
– Ambos remitente y receptor es bloqueado hasta el mensaje se
da • El Nonblocking envia, nonblocking reciba
– Llame una cita – Ni la fiesta se requiere para esperar

59 60

Prof. Javier Echaiz 10

Sistemas Operativos y Distribuidos Sincronización

Direccionamiento Direccionamiento
• Direccionamiento directo • Direccionamiento indirecto
– envie primitivo incluya un identificador específico del proceso de – los mensajes son enviados a una estructura de datos dividida
destino consistiendo de las colas
– reciba el primitivo pudo saber adelantado que procese un – las colas son llamados los buzones
mensaje es esperado – un proceso envia a un mensaje para el buzón y el otro proceso
– reciba el primitivo pudo usar parámetro de fuente para retornar romper y remover el mensaje del buzón
un valor cuando la operación de receive ha sido ejecutado

61 62

Comunicación de procesos indirectos Formato de mensaje

64

Problema de los lectores y escritores

• Muchos lectores pueden leer simultáneamente el archivo
• Sólo un escritor a la vez puede escribir al archivo
• Si un escritor está escribiendo al archivo, ningún lector
puede leerlo

65

Prof. Javier Echaiz 11