Concurrencia

Equipo: Sal Alberto Robles Gaytn Cecilia M. Ocampo Luis Ovidio Navarro Hector Mauricio Molina Lizeth Rodrguez Murgua

Principios generales de la concurrencia

En un sistema multiprogramado con un nico procesador, los procesos se intercalan en el tiempo aparentando una ejecucin simultnea. Aunque no se logra un procesamiento paralelo y produce una sobrecarga en los intercambios de procesos, la ejecucin intercalada produce beneficios en la eficiencia del procesamiento y en la estructuracin de los programas.

La intercalacin y la superposicin pueden contemplarse como ejemplos de procesamiento concurrente en un sistema monoprocesador, los problemas son consecuencia de la velocidad de ejecucin de los procesos que no pueden predecirse y depende de las actividades de otros procesos, de la forma en que el sistema operativo trata las interrupciones surgen las siguientes dificultades:

Compartir recursos globales es riesgoso Para el sistema operativo es difcil gestionar la asignacin ptima de recursos.

Labores del Sistema Operativo

Elementos de gestin y diseo que surgen por causa de la concurrencia: 1) El sistema operativo debe seguir a los distintos procesos activos 2) El sistema operativo debe asignar y retirar los distintos recursos a cada proceso activo, entre estos se incluyen: Tiempo de procesador Memoria Archivos Dispositivos de E/S

3) El sistema operativo debe proteger los datos y los recursos fsicos de cada proceso contra injerencias no intencionadas de otros procesos. 4) Los resultados de un proceso deben ser independientes de la velocidad a la que se realiza la ejecucin de otros procesos concurrentes.

Interaccin entre los procesos

Se puede clasificar los en que interactan los procesos en funcin del nivel de conocimiento que cada proceso tiene de la existencia de los dems. Existen tres niveles de conocimiento: 1) Los procesos no tienen conocimiento de los dems: son procesos independientes que no operan juntos. Ej: la multiprogramacin de procesos independientes. Aunque los procesos no trabajen juntos, el sistema operativo se encarga de la "competencia" por los recursos.

2) Los procesos tienen un conocimiento indirecto de los otros: los procesos no conocen a los otros por sus identificadores de procesos.
3) Los procesos tienen conocimiento directo de los otros: los procesos se comunican por el identificador de proceso y pueden trabajar conjuntamente.

Competencia entre procesos por los recursos

Los procesos concurrentes entran en conflicto cuando compiten por el uso del mismo recurso; dos o ms procesos necesitan acceder a un recurso durante su ejecucin .Cada proceso debe dejar tal y como est el estado del recurso que utilice.
La ejecucin de un proceso puede influir en el comportamiento de los procesos que compiten. Por Ej. Si dos procesos desean acceder a un recurso, el sistema operativo le asignar el recurso a uno y el otro tendr que esperar.

El control de competencia involucra al sistema operativo, porque es el que asigna los recursos. Cooperacin entre procesos de compartimiento Comprende los procesos que interactan con otros sin tener conocimiento explcito de ellos. Ej. : Varios procesos pueden tener acceso a variables compartidas.

Cooperacin entre procesos por comunicacin Comprende los procesos que interactan con otros sin tener conocimiento explcito de ellos. Ej. : Varios procesos pueden tener acceso a variables compartidas.

Requisitos para la exclusin mutua

1. Slo un proceso, de todos los que poseen secciones crticas por el mismo recurso compartido, debe tener permiso para entrar en ella en un momento dado. 2. Un proceso que se interrumpe en una seccin no crtica debe hacerlo sin interferir con los otros procesos. 3. Un proceso no debe poder solicitar acceso a una seccin crtica para despus ser demorado indefinidamente, no puede permitirse el interbloqueo o la inanicin.

4. Si ningn proceso est en su seccin crtica, cualquier proceso que solicite entrar en la suya debe poder hacerlo sin demora.
5. No se debe suponer sobre la velocidad relativa de los procesos o el nmero de procesadores. 6. Un proceso permanece en su seccin crtica por un tiempo finito.

Exclusin Mutua Soluciones SW y HW

Los algoritmos de exclusin mutua (comnmente abreviada como mutex por mutual exclusion) se usan en programacin concurrentepara evitar el ingreso a sus secciones crticas por mas de un proceso a la vez. Cuando un proceso est accediendo a datos compartidos se dice que el proceso se encuentra en seccin critica.

Mientras un proceso se encuentra en su seccin crtica, los dems procesos pueden continuar su ejecucin fuera de sus secciones crticas, cuando un proceso abandona su seccin crtica, entonces debe permitrseles proceder a otro proceso que espera entrar en su propia seccin crtica (s hubiera un proceso en espera). Estar dentro de una seccin crtica es un estado muy especial asignado a un proceso. El proceso tiene acceso exclusivo a los datos compartidos y todos los dems procesos que necesitan acceder a esos datos permanecen en espera. Por tanto las secciones crticas deben ser ejecutadas lo ms rpido posible, un programa no debe bloquearse dentro de su seccin crtica, y las secciones crticas deben ser codificadas con todo cuidado. Si un proceso dentro de una seccin critica termina, tanto de forma voluntaria como involuntaria, entonces al realizar su limpieza de terminacin, el S.O debe liberar la exclusin mutua para que otros procesos puedan entrar en sus secciones crticas. Proceso lineal: se ejecuto el proceso, termina y empieza otro.

La mayor parte de estos recursos son las seales, contadores, colas y otros datos que se emplean en la comunicacin entre el cdigo que se ejecuta cuando se da servicio a una interrupcin y el cdigo que se ejecuta el resto del tiempo. Se trata de un problema de vital importancia porque, si no se toman las precauciones debidas, una interrupcin puede ocurrir entre dos instrucciones cualesquiera del cdigo normal y esto puede provocar graves fallos

La tcnica que se emplea por lo comn para conseguir la exclusin mutua es inhabilitar las interrupciones durante el conjunto de instrucciones ms pequeo que impedir la corrupcin de la estructura compartida (la seccin crtica). Esto impide que el cdigo de la interrupcin se ejecute en mitad de la seccin crtica.

Algoritmo de Peterson

El algoritmo de Peterson, tambin conocido como solucin de Peterson, es un algoritmo de programacin concurrente para exclusin mutua, que permite a dos o ms procesos o hilos de ejecucin compartir un recurso sin conflictos, utilizando slo memoria compartida para la comunicacin. Peterson desarroll el primer algoritmo (1981) para dos procesos que fue una simplificacin del algoritmo de Dekker para dos procesos. Posteriormente este algoritmo fue generalizado para N procesos.

Algoritmo para dos procesos

Los procesos p0 y p1 no pueden estar en la seccin crtica al mismo tiempo: si p0 est en la seccin crtica, entonces bandera[0] = 1, y ocurre que bandera[1] = 0, con lo que p1 ha terminado la seccin crtica, o que la variable compartida turno = 0, con lo que p1 est esperando para entrar a la seccin crtica. En ambos casos, p1 no puede estar en la seccin crtica..

Algoritmo para N procesos (pseudo-codigo)

EXCLUSIN MUTUA: SOLUCIONES POR HARDWARE

INHABILITACIN DE INTERRUPCIONES En una mquina monoprocesador, la ejecucin de procesos concurrentes no puede superponerse; los procesos solo pueden intercalarse. Es ms, un proceso continuar ejecutndose hasta que solicite un servicio el sistema operativo o hasta que sea interrumpido. Por lo tanto, para garantizar la exclusin mutua, es suficiente con impedir que un proceso sea interrumpido. Esta capacidad puede ofrecerse en forma de primitivas definidas por el ncleo del sistema para habilitar o inhabilitar las interrupciones.

SEMFOROS
Para solucionar problemas de procesos concurrentes, se diseo un S.O. como un conjunto de procesos secuenciales, eficiente y fiable para dar soporte a la cooperacin. Los procesos de usuario podran utilizar estos mecanismos si el procesador y el S.O. los hacan disponible.

El principio fundamental es el siguiente, 20+ procesos pueden cooperar por medio de simples seales, de manera que se pueda obligar a un proceso a detener en una posicin determinada hasta que reciba una seal especfica. Para la sealizacin se usan variables especiales llamadas semforos "S", los procesos ejecutan las primitivas wait(s) si la seal aun no se transmiti, el proceso se suspende hasta que tiene lugar la transmisin.

A los semforos se los contemplan como variables que tienen un N entero sobre el que se definen las siguientes operaciones:

un semforo puede iniciarse con un valor negativo

la operacin wait disminuye el valor del semforo. Si el valor no es positivo el proceso que ejecuta wait se bloquea. las operaciones signal incrementa el N del semforo. Si el valor es positivo se desbloquea el proceso bloqueado por una operacin wait.

MONITORES
Los monitores son estructuras de un lenguaje de programacin que ofrecen una funcionalidad equivalente a las de los semforos pero son ms fciles de controlar. El concepto de monitor fue definido por primera vez en [HOAR 74] . La estructura de monitor se ha implementado en varios lenguajes de programacin como: Pascal concurrente, Modulo-2, Java, etc

PASO DE MENSAJES
Son 2 los requisitos bsicos que deben satisfacerse cuando los procesos interactan entre si.

DIRECCIONAMIENTO
Es necesario disponer de alguna forma de especificar en la primitiva send que proceso va a recibir el mensaje. La mayora de las implementaciones permiten a los procesos receptores indicar el origen del mensaje que se va a recibir. Los distintos esquemas para hacer referencia a los procesos en las primitivas send y receive se encuadran dentro de 2 categoras:

Direccionamiento directo: la primitiva send incluye una identificacin especfica del proceso de destino. Direccionamiento indirecto: los mensajes no se envan directamente del emisor al receptor, sino a una estructura de datos compartidos formada por colas, que pueden guardar los mensajes temporalmente, que se denominan BUZONES (mailboxes). Para que 2 procesos se comuniquen, uno enva mensajes al buzn apropiado y el otro los retira. Una ventaja de este tipo de direccionamiento es que se desacopla a emisor y receptor, asegurando mayor flexibilidad en el uso de mensajes.

Semforos

Semforos

Un semforo es una estructura diseada para sincronizar dos o ms threads o procesos, de modo que su ejecucin se realice de forma ordenada y sin conflictos entre ellos.

Semforos

Son una solucin, del tipo soporte al sistema operativo para garantizar la exclusin mutua
Un semforo nos sirve para poder permitir o restringir a los procesos o hilos el acceso a algn recurso compartido

Operaciones Bsicas

Los semforos cuentan con operaciones bsicas, una de ellas es para reservarlo y la otra para liberarlo, wait(espera) y signal(seal) respectivamente, equivalente down y up.

Operaciones Bsicas

Existe una tercera operacin que consiste en inicializar el semforo.

Existen algunos semforos que manejan una cola de espera.

Wait, Top, Down o Espera

Decremento en una unidad el semforo

Bloquea hilo/proceso si el semforo es menor que cero, sino entonces permite a hilo/proceso continuar
Llamada W(semforo) o down(semforo)

Signal, Up o Seal

Incrementa semforo en uno y si hay algn proceso esperando lo despierta

Existe un valor mximo para incrementar el semforo, este no se va a infinito Llamada S(semforo) o up(semforo

Inicializador

Los semforos pueden ser de 2 tipos: Binarios o Generales(Contadores). La operacin de inicializador definir si el semforo ser binario o no, es decir, si se inicializa con 1, el semforo ser binario ya que solo podr manejar un recurso compartido, en caso de tener N recursos compartidos se inicializara con N.

Inicializador

Si tenemos N procesos inicializamos un semforo para que solo N procesos acceda a un recurso compartido.

Semforos con Manejo de Cola

Existen semforos que tienen la operacin de manejar una cola del tipo FIFO (PEPS)para llevar el control de los procesos que estn solicitando los recursos, as cuando se liberen los recursos estos puedan asignarle dicho recurso al primer proceso que lo solicito

Semforos con Manejo de Cola

Desventajas

No se puede imponer el uso correcto de los Down y Up No existe una asociacin entre el semforo y el recurso Entre Down y Up el usuario puede realizar cualquier operacin con el recurso.

Principios de Interbloqueo

Qu es el Interbloqueo?

El interbloqueo es el bloqueo permanente de un conjunto de procesos que compiten por los recursos del sistema o bien se comunican unos con otros.

Qu es el Interbloqueo?

A diferencia de otros problemas de la gestin concurrente de procesos, no existe una solucin eficiente para el caso general. Todos los interbloqueos suponen necesidades contradictorias de recursos por parte de dos o ms procesos.

Ejemplo de Interbloqueo

Cuatro coches llegan aproximadamente en el mismo instante a un cruce de cuatro caminos. Los cuatro cuadrantes de la interseccin son los recursos compartidos sobre los que se demanda control; por tanto, si los coches desean atravesar el cruce, las necesidades de recursos son las siguientes:

Ejemplo de Interbloqueo

El coche que va hacia el norte necesita los cuadrantes 1 y 2. El coche que va hacia el oeste necesita los cuadrantes 2 y 3. El coche que va hacia el sur necesita los cuadrantes 3 y 4. El coche que va hacia el este necesita los cuadrantes 4 y 1.

Recursos
Un sistema se compone de un numero finito de recursos que se distribuyen entre varios tipos:

Fsicos: Ciclo de cpu, espacio en memoria, dispositivos de e/s (impresoras, unidades de cinta, etc.) Lgicos: Ficheros, tablas del sistemas, semforos.

Recursos

Por lo general, una computadora tiene distintos recursos que pueden ser otorgados. Algunos recursos podrn tener varias instancias idnticas, como es el caso de tres unidades de cinta. Si se tienen disponibles varias copias de un recurso, cualquiera de ellas se pude utilizar para satisfacer cualquier solicitud del recurso.

Recursos

Un recurso es cualquier cosa que solo puede ser utilizada por un nico proceso en un instante dado.
Los recursos son de dos tipos:

Apropiable No apropiables

Recursos

Recurso apropiable es aquel que se puede tomar del proceso que lo posee sin efectos dainos. La memoria es un ejemplo de recurso apropiable.

Recursos

Por el contrario, un recurso no apropiable, es aquel que no se puede tomar de su poseedor activo sin provocar un fallo de calculo. Si un proceso comienza a imprimir una salida, se toma la impresora y se le da a otro proceso, el resultado ser una salida incomprensible. Las impresoras no son apropiables.

Recursos

Los interbloqueos se relacionan con los recursos no apropiables. Lo usual es que los bloqueos asociados a recursos apropiables se pueden resolver, mediante la reasignacin de recursos de un proceso a otro.

Recursos

La secuencia de eventos necesaria para utilizar un recurso es:

Solicitar el recurso Utilizar el recurso Liberar el recurso

Prevencin de Interbloqueo

Interbloqueo

El interbloqueo se define como el bloqueo permanente de un conjunto de procesos que compiten por los recursos del sistema o bien se comunican unos con otros. A diferencia de otros problemas de la gestin concurrente de procesos, para el caso general no existe una solucin eficiente. No hay ninguna estrategia sencilla que pueda solucionar todas las clases de interbloqueo.

Condiciones del Interbloqueo

Deben darse tres condiciones para que pueda producirse un interbloqueo:
Exclusin mutua: Slo un proceso puede usar un recurso cada vez. Retencin y espera: Un proceso puede retener recursos asignados mientras espera que se le asignen otros que le hacen falta.

Condiciones del Interbloqueo

No apropiacin: Ningn proceso puede ser forzado a abandonar un recurso retenido (incluso aunque se le deniegue una nueva solicitud de un recurso). Crculo vicioso de espera: existe una cadena cerrada de procesos y cada uno retiene un recurso que necesita otro.

Crculo Vicioso de Espera

Mecanismos Para Evitar el Interbloqueo

Mtodo de la prevencin.
Mtodo de la deteccin. Mtodo de evitacin o prediccin.

Mtodo de la Prevencin
Consiste en disear un sistema de manera que est excluida, a priori, la posibilidad de interbloqueo.

Mtodo de la Prevencin
Los mtodos para prevenir el interbloqueo son de dos tipos.
Los mtodos indirectos consisten en impedir la aparicin de alguna de las tres primeras condiciones antes mencionadas . Los mtodos directos consisten en evitar la aparicin del crculo vicioso de espera.

Mtodo de la Prevencin
1) Prevencin de la exclusin mutua
Significara hacer compartirse. que un recurso pueda

Problema: hay recursos que necesariamente requieren la exclusin mutua, no existe ninguna alternativa y no puede llegar a anularse.
Archivos con permiso de escritura La memoria compartida

Mtodo de la Prevencin
2) Prevencin de la situacin de Retencin y Espera
Antes de comenzar el proceso declaramos los recursos que ste necesita y esperamos a que estn todos disponibles para entrar en ejecucin. Problemas:
Un proceso puede estar suspendido durante mucho tiempo. Los recursos asignados a un proceso pueden permanecer sin usarse durante periodos considerables.

Mtodo de la Prevencin
3) Prevencin de la no apropiacin
Si a un proceso que retiene recursos se le deniega una nueva solicitud, el proceso deber liberar recursos y volver a solicitarlos junto con el recurso adicional. Si un proceso solicita un recurso que posee otro proceso, el S.O. puede expulsar al segundo y exigirle que libere todos sus recursos. Problema: esta tcnica es prctica slo cuando se aplica a recursos cuyo estado puede salvarse y restaurarse ms tarde de una forma fcil.

Mtodo de la Prevencin
4) Prevencin del crculo vicioso de espera.
Sincronizar los avances de los procesos en el mismo sentido y tratar que a los recursos se les asigne un nmero en un determinado orden, de manera que estn en el sentido de avance de ejecucin de los procesos. Problema:
Con nmero alto de recursos, difcil disear un orden que satisfaga a todos los procesos. Ineficiente (retardo de procesos y denegacin de accesos a recursos que pueden ser innecesarias).

Mtodo de Deteccin

No establece medidas de prevencin, solo toma medidas si hay un interbloqueo. Lanza a ejecutar un proceso que contiene un algoritmo para ver si se ha producido un interbloqueo (carga aadida).

Mtodo de Deteccin

Las medidas que se toman pueden ser:

1. Eliminar los procesos bloqueados. 2. Tomar todos los procesos en interbloqueo y situarlos en su ltimo checkpoint volvindolos a lanzar a ejecucin.

Mtodo de Deteccin
3. Eliminar procesos y volver a comprobar por fases si hay interbloqueo. 4. Apropiarse de recursos para ir cedindolos de un proceso a otro hasta que deje de haber interbloqueo.

Mtodo de Deteccin
Para los puntos 3 y 4, el criterio de seleccin podra ser uno de los siguientes, consistentes en escoger el proceso con:
La menor cantidad de tiempo de procesador consumido hasta ahora . El menor nmero de producidas hasta ahora lneas de salida

Mtodo de Deteccin
El mayor tiempo restante estimado
El menor nmero total de recursos asignados hasta ahora La prioridad ms baja

Mtodo de Evitacin o Prediccin

Se considera el ms adecuado, pero para llevarlo a cabo el sistema operativo debe saber cules son las necesidades mximas del proceso desde el principio.

Mtodo de Evitacin o Prediccin

Consiste en hacer comprobaciones a los procesos antes de que entren a ejecutarse o cuando soliciten otro recurso para verificar en qu situacin o estado quedara el sistema.

Mtodo de Evitacin o Prediccin

El sistema puede quedar en dos posibles estados:

Estado seguro: hay al menos una combinacin que permite que ese proceso se pueda ejecutar y terminar, y el resto de procesos tambin. Si se encuentran en estado seguro se le concedern las peticiones al proceso.

Mtodo de Evitacin o Prediccin

Estado no seguro: es lo contrario de lo anterior. En este estado no se lanzar el nuevo proceso a ejecucin (si se trata de un nuevo proceso) o no se concedern las peticiones y ste solicitar los recursos en otro momento (si es un proceso que ha solicitado un nuevo recurso).

Mtodo de Evitacin o Prediccin

La prediccin, por tanto, permite ms concurrencia que la prevencin. Con prediccin del interbloqueo, se decide dinmicamente si la peticin actual de asignacin de un recurso podra, de concederse, llevar potencialmente a un interbloqueo. La prediccin del interbloqueo necesita, por tanto, conocer las peticiones futuras de recursos.