• Author / Uploaded
• dinocrazy

Citation preview

CATEDRA SISTEMAS OPERATIVOS II INGENIERÍA EN INFORMÁTICA RUBEN CASTAÑO - CARLOS MANUEL TOLEDO [email protected] www.dachary.edu.ar

CONCURRENCIA

Introducción Dificultades Grados de interacción Problemas de la exclusión mutua (Interbloqueos, Inanición)

CATEDRA SISTEMAS OPERATIVOS II – AÑO 2006 CARLOS MANUEL TOLEDO

2

Intercalación Vs Superposición:

CATEDRA SISTEMAS OPERATIVOS II – AÑO 2006 CARLOS MANUEL TOLEDO

3

INTERPROCESS COMUNICATION

CATEDRA SISTEMAS OPERATIVOS II – AÑO 2006 CARLOS MANUEL TOLEDO

4

Algoritmo de la panadería Implementadas por el programador

Alternancia estricta Variable cerradura

Implementadas por el sistema operativo

Semáforos Colas de mensajes Inhabilitación de las interrupciones Evaluar y asignar (comparar y fijar) Intercambiar TSL (Test and Set Lock)

Implementadas por el hardware

Implementadas por el lenguaje de programación

Monitores

CATEDRA SISTEMAS OPERATIVOS II – AÑO 2006 CARLOS MANUEL TOLEDO

5

Soluciones para dos procesos

Variable cerradura Alternancia estricta Solución de Peterson

Algoritmo de la panadería Semáforos Monitores Soluciones para varios procesos

Mensajes TSL, evaluar y asignar, intercambiar

CATEDRA SISTEMAS OPERATIVOS II – AÑO 2006 CARLOS MANUEL TOLEDO

6

OTRAS HERRAMIENTAS DE COMUNICACIÓN

PIPES (Tuberías) MEMORIA COMPARTIDA Sólo sirve para comunicar datos, no para sincronizar, salvo si se ocupa en forma combinada con una herramienta de sincronización, por ejemplo, semáforos para la sincronización de procesos independientes, no hilos.

SEÑALES

Evento que debe ser procesado y que puede interrumpir el flujo normal de un programa. Una señal se pude capturar o ignorar. Alarma à Señal que es activada por los temporizadores del sistema.

CATEDRA SISTEMAS OPERATIVOS II – AÑO 2006 CARLOS MANUEL TOLEDO

7

CONDICIÓN DE COMPETENCIA Y EXCLUSION MUTUA

CATEDRA SISTEMAS OPERATIVOS II – AÑO 2006 CARLOS MANUEL TOLEDO

8

EJEMPLO: Spooler de una impresora

A

B OUT

IN

CATEDRA SISTEMAS OPERATIVOS II – AÑO 2006 CARLOS MANUEL TOLEDO

9

CONDICIÓN DE COMPETENCIA: En algunos SO los procesos que trabajan juntos comparten con frecuencia un espacio común para almacenamiento (MP, archivo, etc), en el que cada uno puede leer o escribir. La actualización sin restricciones de variables compartidas puede conducir a inconsistencias. Tales errores suelen ser dependiente de la temporización específica y del modo de entrelazarse las acciones de los procesos. Las situaciones como ésta en que dos o más procesos utilizan recursos compartidos y el resultado final depende de quién ejecuta qué y en qué momento, recibe el nombre de condición de competencia.

Los errores introducidos por la concurrencia pueden ser extremadamente difíciles de detectar, reproducir y depurar. CATEDRA SISTEMAS OPERATIVOS II – AÑO 2006 CARLOS MANUEL TOLEDO

10

SI ALGO PUEDE FALLAR FALLARÁ. LEY DE MURPHY

CATEDRA SISTEMAS OPERATIVOS II – AÑO 2006 CARLOS MANUEL TOLEDO

11

SOLO CUANDO EXISTEN OPERACIONES DE ESCRITURAS SE DEBE BRINDAR EXCLUSIÓN MUTUA

CATEDRA SISTEMAS OPERATIVOS II – AÑO 2006 CARLOS MANUEL TOLEDO

12

SECCIONES CRÍTICAS

CATEDRA SISTEMAS OPERATIVOS II – AÑO 2006 CARLOS MANUEL TOLEDO

13

SECCIÓN CRITICA: Considere un sistema compuesto por n procesos {P0, P1, ..., Pn-1}. Cada proceso tiene un segmento de código, llamado sección crítica, en la cual el proceso puede estar modificando variables comunes, actualizando una tabla, escribiendo un archivo, etc. La característica importante del sistema es que, cuando un proceso del conjunto se ejecuta en su sección crítica, no se permite que ningún otro proceso se ejecute en su sección. De esta manera, la ejecución de las secciones críticas de los proceso es mutuamente excluyentes en el tiempo.

CATEDRA SISTEMAS OPERATIVOS II – AÑO 2006 CARLOS MANUEL TOLEDO

14

P0

P1

A

CATEDRA SISTEMAS OPERATIVOS II – AÑO 2006 CARLOS MANUEL TOLEDO

15

CATEDRA SISTEMAS OPERATIVOS II – AÑO 2006 CARLOS MANUEL TOLEDO

16

Requisitos que debe cumplir una solución: EXCLUSIÓN MUTUA: Si un proceso P1 se está ejecutando en su sección crítica, entonces ningún otro proceso se puede estar ejecutando en la suya. PROGRESO: Si ningún proceso se está ejecutando en su SC y hay otros procesos que desean entrar en las suyas, entonces sólo aquellos procesos que no están se están ejecutando en su sección restante pueden participar de la decisión de cuál será el siguiente en entrar en la SC y esta selección no puede postergarse indefinidamente. ESPERA LIMITADA: Debe haber un límite en el número de veces que se permite que los demás proceso entren en su sección crítica después de que un proceso haya efectuado una solicitud para entrar en la suya y antes de que se conceda esa solicitud. CATEDRA SISTEMAS OPERATIVOS II – AÑO 2006 CARLOS MANUEL TOLEDO

17

AUNQUE SE CONSIDERA QUE LOS PROCESOS SE EJECUTAN A UNA VELOCIDAD NO NULA, NO SE PUEDEN HACER SUPOSICIONES ACERCA DE LA VELOCIDAD DE EJECUCIÓN

CATEDRA SISTEMAS OPERATIVOS II – AÑO 2006 CARLOS MANUEL TOLEDO

18

PROBLEMA DE LOS PRODUCTORES-CONSUMIDORES

CATEDRA SISTEMAS OPERATIVOS II – AÑO 2006 CARLOS MANUEL TOLEDO

19

CATEDRA SISTEMAS OPERATIVOS II – AÑO 2006 CARLOS MANUEL TOLEDO

20

#include “prototypes.h” #define TRUE -1 #define N 100 int count = 0; void producer(){ int item; while (TRUE){ produce_item(&item); if (count == N) sleep() enter_item(item); count++; if(count == 1) wakeup(consumer) } }

void consumer(){ int item; while (TRUE){ if(count == 0) sleep(); remove_item(&item); count++; if(count == (N-1)) wakeup(producer); consumer_item(item); } }

CATEDRA SISTEMAS OPERATIVOS II – AÑO 2006 CARLOS MANUEL TOLEDO

21

SOLUCIONES IMPLEMENTADAS POR EL PROGRAMADOR

CATEDRA SISTEMAS OPERATIVOS II – AÑO 2006 CARLOS MANUEL TOLEDO

22

SOLUCIONES PARA DOS PROCESOS: - Variable cerradura espero

¿sc == 0?

sc = 1 entro SC

- Alternancia estricta

i entra SC

sc = 0

¿turno == j?

j entra SC turno = i

turno = j CATEDRA SISTEMAS OPERATIVOS II – AÑO 2006 CARLOS MANUEL TOLEDO

23

- Variable cerradura

arreglo[i]=T; while(arreglo[j]; ; SECCION CRITICA arreglo[i]=F;

T0 à arreglo[i]=T; T1 à arreglo[j]=T;

CATEDRA SISTEMAS OPERATIVOS II – AÑO 2006 CARLOS MANUEL TOLEDO

24

- Solución de Peterson Primera solución T. Dekker (Matemático Holandes) Peterson (1981) Turnos + arreglo arreglo[i]=T; turno=j; while(arreglo[j] && turno==j); ; SECCION CRITICA arreglo[i]=F;

CATEDRA SISTEMAS OPERATIVOS II – AÑO 2006 CARLOS MANUEL TOLEDO

25

SOLUCION PARA VARIOS PROCESOS (ALGORITMO DE LA PANADERÍ PANADERÍA)

Estructuras compartidas: int elección[N]=F; int número[N]=0; Al principio a estas estructuras se le asigna un valor inicial FALSO y 0. (a,b) < (c,d) si a