2.6 Concurrencia Exclusion Mutua Y Sincronizacion
Concurrencia: exclusión mutua y sincronización
Los temas fundamentales del diseño de sistemas operativos están relacionados con la gestión de procesos e hilos:
• Multiprogramación: consiste en la gestión de varios procesos dentro de un sistema mono-procesador.
• Multiprocesamiento: consiste en la gestión de varios procesos, dentro de un sistema multiprocesador.
• Procesamiento distribuido: consiste en la gestión de varios procesos, ejecutándose en sistemas de computadores múltiples y distribuidos. La reciente proliferación de las agrupaciones es el principal ejemplo de este tipo de sistemas.
La concurrencia es fundamental en todas estas áreas y para el diseño sistemas operativos. La concurrencia comprende un gran número de cuestiones de diseño, incluida la comunicación entre procesos, compartición y competencia por los recursos, sincronización de la ejecución de varios procesos y asignación del tiempo de procesador a los procesos. Se verá que estas cuestiones no solo surgen en entornos de multiprocesadores y proceso distribuido, sino incluso en sistemas multiprogramados con un solo procesador.
La concurrencia puede presentarse en tres contextos diferentes:
• Múltiples aplicaciones: la multiprogramación se creó para permitir que el tiempo de procesador de la máquina fuese compartido dinámicamente entre varias aplicaciones activas.
• Aplicaciones estructuradas: como ampliación de los principios del diseño modular y la programación estructurada, algunas aplicaciones pueden implementarse eficazmente como un conjunto de procesos concurrentes.
• Estructura del sistema operativo: las mismas ventajas de estructuración son aplicables a los programadores de sistemas y se ha comprobado que algunos sistemas operativos están implementados como un conjunto de procesos o hilos.
PRINCIPIOS GENERALES DE LA CONCURRENCIA
En un sistema multiprogramado con un único procesador, los procesos se intercalan en el tiempo aparentando una ejecución simultánea. Aunque no se logra un procesamiento paralelo y produce una sobrecarga en los intercambios de procesos, la ejecución intercalada produce beneficios en la eficiencia del procesamiento y en la estructuración de los programas.
La intercalación y la superposición pueden contemplarse como ejemplos de procesamiento concurrente en un sistema monoprocesador, los problemas son consecuencia de la velocidad de ejecución 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 difícil gestionar la asignación óptima de recursos. Las dificultades anteriores también se presentan en los sistemas multiprocesador.
El hecho de compartir recursos ocasiona problemas, por esto es necesario proteger a dichos recursos.
Los problemas de concurrencia se producen incluso cuando hay un único procesado
LABORES DEL SISTEMA OPERATIVO
Elementos de gestión y diseño 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 físicos 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 ejecución de otros procesos concurrentes.
Para abordar la independencia de la velocidad debemos ver las formas en las que los procesos interactúan.
INTERACCIÓN ENTRE PROCESOS
Se puede clasificar los en que interactúan los procesos en función del nivel de conocimiento que cada proceso tiene de la existencia de los demás. Existen tres niveles de conocimiento:
1) Los procesos no tienen conocimiento de los demás: son procesos independientes que no operan juntos. Ej: la multiprogramación 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 proceso, pero muestran cooperación el objeto común.
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 más procesos necesitan acceder a un recurso durante su ejecución .Cada proceso debe dejar tal y como esté el estado del recurso que utilice.
La ejecución 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.
Cuando hay procesos en competencia, se deben solucionar tres problemas de control: la necesidad de exclusión mutua. Suponiendo que dos procesos quieren acceder a un recurso no compartible. A estos recursos se les llama “recursos críticos” y la parte del programa que los utiliza es la “sección crítica” del programa. Es importante que sólo un programa pueda acceder a su sección crítica en un momento dado.
Hacer que se cumpla la exclusión mutua provoca un interbloqueo.
Otro problema es la inanición si tres procesos necesitan acceder a un recurso, P1 posee al recurso, luego lo abandona y le concede el acceso al siguiente proceso P2, P1 solicita acceso de nuevo y el sistema operativo concede el acceso a P1 YP2 alternativamente, se puede negar indefinidamente a P3 el acceso al recurso.
El control de competencia involucra al sistema operativo, porque es el que asigna los recursos.
Cooperación entre procesos por compartimiento Comprende los procesos que interactúan con otros sin tener conocimiento explícito de ellos. Ej. : Varios procesos pueden tener acceso a variables compartidas.
Los procesos deben cooperar para asegurar que los datos que se comparten se gestionan correctamente. Los mecanismos de control deben garantizar la integridad de los datos compartidos.
Cooperación entre procesos por comunicación Los distintos procesos participan en una labor común que une a todos los procesos.
La comunicación sincroniza o coordina las distintas actividades, está formada por mensajes de algún tipo. Las primitivas para enviar y recibir mensajes, vienen dadas como parte del lenguaje de programación o por el núcleo del sistema operativo
REQUISITOS PARA LA EXCLUSIÓN MUTUA
Sólo un proceso, de todos los que poseen secciones críticas por el mismo recurso compartido, debe tener permiso para entrar en ella en un momento dado. Un proceso que se interrumpe en una sección no crítica debe hacerlo sin interferir con los otros procesos. Un proceso no debe poder solicitar acceso a una sección crítica para después ser demorado indefinidamente, no puede permitirse el interbloqueo o la inanición. Si ningún proceso está en su sección crítica, cualquier proceso que solicite entrar en la suya debe poder hacerlo sin demora. No se debe suponer sobre la velocidad relativa de los procesos o el número de procesadores. Un proceso permanece en su sección crítica por un tiempo finito. Una manera de satisfacer los requisitos de exclusión mutua es dejar la responsabilidad a los procesos que deseen ejecutar concurrentemente. Tanto si son programas del sistema como de aplicación, los procesos deben coordinarse unos con otros para cumplir la exclusión mutua, sin ayuda del lenguaje de programación o del sistema operativo. Estos métodos se conocen como soluciones por software.
EXCLUSIÓN MUTUA: SOLUCIONES POR SOFTWARE
Pueden implementarse soluciones de software para los procesos concurrentes que se ejecuten en máquinas monoprocesador o multiprocesador con memoria principal compartida.
ALGORITMO DE DEKKER
La solución se desarrolla por etapas. Este método ilustra la mayoría de los errores habituales que se producen en la construcción de programas concurrentes.
Primer intento
Cualquier intento de exclusión mutua debe depender de algunos mecanismos básicos de exclusión en el hardware. El más habitual es que sólo se puede acceder a una posición de memoria en cada instante, teniendo en cuenta esto se reserva una posición de memoria global llamada turno. Un proceso que desea ejecutar su sección crítica primero evalúa el contenido de turno. Si el valor de turno es igual al número del proceso, el proceso puede continuar con su sección crítica. En otro caso el proceso debe esperar. El proceso en espera, lee repetitivamente el valor de turno hasta que puede entrar en su sección crítica. Este procedimiento se llama espera activa.
Después de que un proceso accede a su sección crítica y termina con ella, debe actualizar el valor de turno para el otro proceso.
Segundo intento:
Cada proceso debe tener su propia llave de la sección crítica para que, si uno de ellos falla, pueda seguir accediendo a su sección crítica; para esto se define un vector booleano señal. Cada proceso puede evaluar el valor de señal del otro, pero no modificarlo. Cuando un proceso desea entrar en su sección crítica, comprueba la variable señal del otro hasta que tiene el valor falso (indica que el otro proceso no está en su sección crítica). Asigna a su propia señal el valor cierto y entra en su sección crítica. Cuando deja su sección crítica asigna falso a su señal.
Si uno de los procesos falla fuera de la sección crítica, incluso el código para dar valor a las variables señal, el otro proceso no se queda bloqueado. El otro proceso puede entrar en su sección crítica tantas veces como quiera, porque la variable señal del otro proceso está siempre en falso. Pero si un proceso falla en su sección crítica o después de haber asignado cierto a su señal, el otro proceso estará bloqueado permanentemente.
Tercer intento
El segundo intento falla porque un proceso puede cambiar su estado después de que el otro proceso lo ha comprobado pero antes de que pueda entrar en su sección crítica.
Si un proceso falla dentro de su sección crítica, incluso el código que da valor a la variable señal que controla el acceso a la sección crítica, el otro proceso se bloquea y si un proceso falla fuera de su sección crítica, el otro proceso no se bloquea.
Si ambos procesos ponen sus variables señal a cierto antes de que ambos hayan ejecutado una sentencia, cada uno pensará que el otro ha entrado en su sección crítica, generando así un interbloqueo.
Cuarto intento
En el tercer intento, un proceso fijaba su estado sin conocer el estado del otro. Se puede arreglar esto haciendo que los procesos activen su señal para indicar que desean entrar en la sección crítica pero deben estar listos para desactivar la variable señal y ceder la preferencia al otro proceso.
Existe una situación llamada bloqueo vital, esto no es un interbloqueo, porque cualquier cambio en la velocidad relativa de los procesos rompería este ciclo y permitiría a uno entrar en la sección crítica. Recordando que el interbloqueo se produce cuando un conjunto de procesos desean entrar en sus secciones críticas, pero ninguno lo consigue. Con el bloqueo vital hay posibles secuencias de ejecución con éxito.
Una solución correcta
Hay que observar el estado de ambos procesos, que está dado por la variable señal, pero es necesario imponer orden en la actividad de los procesos para evitar el problema de “cortesía mutua”. La variable turno del primer intento puede usarse en esta labor, indicando que proceso tiene prioridad para exigir la entrada a su sección crítica.
ALGORITMO DE PETERSON
El algoritmo de Deker resuelve el problema de la exclusión mutua pero mediante un programa complejo, difícil de seguir y cuya corrección es difícil de demostrar. Peterson ha desarrollado una solución simple y elegante. Como antes, la variable global señal indica la posición de cada proceso con respecto a la exclusión mutua y la variable global turno resuelve los conflictos de simultaneidad.
Considérese el proceso P0. Una vez que ha puesto señal[0] a cierto, P1 no puede entrar en su sección crítica. Si P1 esta aun en su sección crítica, entonces señal[1] = cierto y P0 está bloqueado en su bucle while. Esto significa que señal[1] es cierto y turno = 1. P0 puede entrar en su sección crítica cuando señal[1] se ponga a falso o cuando turno se ponga a 0. Considérense ahora los siguientes casos exhaustivos:
P1 no está interesado en entrar en su sección crítica. Este caso es imposible porque implica que señal[1] = falso. P1 está esperando entrar en su sección crítica. Este caso es también imposible porque si turno = 1, P1 podría entrar en su sección crítica. P1 entra en su sección crítica varias veces y monopoliza el acceso a ella. Esto no puede pasar porque P1 está obligado a dar a P0 una oportunidad poniendo turno a 0 antes de cada intento de entrar en su sección crítica. Así pues, se tiene una solución posible al problema de la exclusión mutua para dos procesos. Es más, el algoritmo de Peterson se puede generalizar fácilmente al caso de n procesos.
Disciplina de cola
La disciplina de cola mas simple es la de primero en llegar/ primero en salir, pero ésta puede no ser suficiente si algunos mensajes son mas urgentes que otros. Una alternativa es permitir la especificación de prioridades de los mensajes, en función del tipo de mensaje o por designación del emisor. Otra alternativa es permitir al receptor examinar la cola de mensajes y seleccionar el mensaje a recibir a continuación.
Exclusión mutua
Supóngase que se usan primitivas receive bloqueantes y send no bloqueantes. Un conjunto de procesos concurrentes comparten un buzón, exmut, que puede ser usado por todos los procesos para enviar y recibir. El buzón contiene inicialmente un único mensaje, de contenido nulo. Un proceso que desea entrar en su sección crítica intenta primero recibir el mensaje. Si el buzón está vacío, el proceso se bloquea. Una vez que un proceso ha conseguido el mensaje, ejecuta su sección crítica y, después, devuelve el mensaje al buzón. De este modo, el mensaje funciona como testigo que se pasa de un proceso a otro.
Esta técnica supone que si hay más de un proceso ejecutando la acción receive concurrentemente, entonces:
Si hay un mensaje, se entrega sólo a uno de los procesos y los otros se bloquean. Si el buzón está vacío, todos los procesos se bloquean; cuando haya un mensaje disponible, sólo se activará y tomará el mensaje uno de los procesos bloqueados.
EXCLUSIÓN MUTUA: SOLUCIONES POR HARDWARE