Los procesos son concurrentes si existen simultáneamente. Cuando dos o más procesos llegan al mismo tiempo a ejecutarse, se dice que se ha presentado una concurrencia de procesos. Es importante mencionar que para que dos o más procesos sean concurrentes, es necesario que tengan alguna relación entre ellos
La concurrencia puede presentarse en tres contextos diferentes:
• Varias aplicaciones: La multiprogramación se creó para permitir que el tiempo de procesador de la máquina fuese compartido dinámicamente entre varios trabajos o aplicaciones activas.
• 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. Existen tres modelos de computadora en los que se pueden ejecutar procesos concurrentes:
• Multiprogramación con un único procesador. El sistema operativo se encarga de ir repartiendo el tiempo del procesador entre los distintos procesos, intercalando la ejecución de los mismos para dar así una apariencia de ejecución simultánea.
Angellen Barrios, Sandra Certain (2000 febrero 2002). Procesos ligeros Hilos y hebras. Recuperado 27 de Octubre de 2008 de http://www.monografias.com/trabajos19/sistemas-operativos/sistemas operativos.shtml#admin
Tipos de procesos concurrentes.
Los procesos que ejecutan de forma concurrente en un sistema se pueden clasificar como:
Proceso independiente: Es aquel que ejecuta sin requerir la ayuda o cooperación de otros procesos. Un claro ejemplo de procesos independientes son los diferentes shells que se ejecutan de forma simultánea en un sistema.
Procesos son cooperantes: Son aquellos que están diseñados para trabajar conjuntamente en alguna actividad, para lo que deben ser capaces de comunicarse e interactuar entre ellos. En ambos tipos de procesos (independientes y cooperantes), puede producirse una serie de interacciones entre ellos y pueden ser de dos tipos:
• Interacciones motivadas porque los procesos comparten o compiten por el acceso a recursos físicos o lógicos. Por ejemplo, dos procesos independientes compiten por el acceso a disco o para modificar una base de datos.
• Interacción motivada porque los procesos se comunican y sincronizan entre sí para alcanzar un objetivo común, Por ejemplo, un compilador que tiene varios procesos que trabajan conjuntamente para obtener un solo archivo de salida.
Elementos a gestionar y diseñar a causa de la concurrencia. Se pueden enumerar los siguientes:
1. El sistema operativo debe ser capaz de seguir la pista de los distintos procesos activos. Esto lo hace por medio de PBC’s (Bloque de Control de Procesos)
2. El sistema operativo debe asignar y quitar los distintos recursos a cada proceso activo.
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 relativa a la que se realiza la ejecución con respecto a otros procesos concurrentes.
Cuando dos o mas procesos llegan al mismo tiempo a ejecutarse, se dice que se ha presentado una concurrencia de procesos.
Es importante mencionar que para que dos o más procesos sean concurrentes, es necesario que tengan algunas relaciones entre ellos como puede ser la cooperación para un determinado trabajo o el uso de información y recursos compartidos.
Angellen Barrios, Sandra Certain (2000 febrero 2002). Procesos ligeros Hilos y hebras. Recuperado 27 de Octubre de 2008 de http://www.monografias.com/trabajos19/sistemas-operativos/sistemas operativos.shtml#admin
2.4.1 Exclusión Mutua Secciones Criticas
Los procesos concurrentes entran en conflicto cuando compiten por el uso del mismo recurso, es decir, quieren acceder a un recurso al mismo tiempo. Y la ejecución de un proceso puede influir en el comportamiento de los procesos que compiten y el sistema operativo le asignará el recurso a uno de ellos y el otro tendrá que esperar. Por lo que el proceso que quede esperando, se retrasará, se bloqueara y en el peor de los casos nunca se terminará con éxito.
El problema de la sección crítica es uno de los problemas que con mayor frecuencia aparece cuando se ejecutan procesos concurrentes. Para entender un poco mejor el concepto se presenta el siguiente ejemplo:
Se tiene un Sistema Operativo que debe asignar un identificador de proceso (PID) a dos procesos en un sistema multiprocesador. Cuando el SO realiza esta acción en dos procesadores de forma simultánea sin ningún tipo de control, se pueden producir errores, ya que se puede asignar el mismo PID a dos procesos distintos.
Solución a la sección crítica
Para resolver el problema de la sección crítica es necesario utilizar algún mecanismo de sincronización que permita a los procesos cooperar entre ellos sin problemas. Este mecanismo debe proteger el código de la sección crítica y su funcionamiento básico es el siguiente:
• Cada proceso debe solicitar permiso para entrar en la sección crítica, mediante algún fragmento de código que se denomina de forma genérica entrada en la sección crítica.
• Cuando un proceso sale de la sección critica debe indicarlo mediante otro fragmento de código que se denomina salida de la sección crítica. Este fragmento permitirá que otros procesos entren a ejecutar el código de la sección crítica.
Cualquier solución que se utilice para resolver este problema debe cumplir los requisitos siguientes:
• Exclusión mutua: Si un proceso está ejecutando código de la sección crítica, ningún otro proceso lo podrá hacer.
• Progreso: Si ningún proceso está ejecutando dentro de la sección crítica, la decisión de qué proceso entra en la sección se hará sobre los procesos que desean entrar.
Exclusión mutua
La exclusión mutua la podríamos definir como una operación de control que permite la coordinación de procesos concurrentes, y que tiene la capacidad de prohibir a los demás procesos realizar una acción cuando un proceso haya obtenido el permiso.
Hacer que se cumpla la exclusión mutua crea dos problemas de control adicionales.
• Interbloqueo. Si se tienen dos procesos P1 y P2 y dos recursos críticos, R1 y R2. Supóngase que cada proceso necesita acceder a ambos recursos para llevar a cabo una parte de su función. En tal caso, es posible que se presente la siguiente situación: el sistema operativo asigna R1 a P2 y R2 a P1. Cada proceso está esperando a uno de los dos recursos.
• Inanición. Supóngase que tres procesos, P1, P2 y P3, necesitan acceder periódicamente al recurso R. Considérese la situación en la que P1 está en posesión del recurso y tanto P2 como P3 están parados, esperando al recurso. Cuando P1 abandona su sección crítica, tanto P2 como P3 deben poder acceder a R.
Requisitos para la exclusión mutua.
1. Debe cumplirse la exclusión mutua: Solo un proceso, de entre todos los que poseen secciones críticas por el mismo recurso u objeto compartido, debe tener permiso para entrar en ella en un instante dado.
2. Un proceso que se interrumpe en una sección no crítica debe hacerlo sin estorbar a los otros procesos.
3. 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.
4. Cuando ningún proceso está en su sección crítica, cualquier proceso que solicite entrar en la suya debe poder hacerlo sin dilación.
Soluciones a la exclusión mutua
Hay varias formas de satisfacer los requisitos de exclusión mutua:
Soluciones por Software. Una manera es dejar la responsabilidad a los procesos que deseen ejecutar concurrentemente, de esta manera los procesos deben coordinarse unos con otros para cumplir la exclusión mutua sin ayuda alguna.
Soluciones por Hardware. Propone el uso de instrucciones de la máquina a tal efecto, estas tienen la ventaja de reducir la sobrecarga.
Angellen Barrios, Sandra Certain (2000 febrero 2002). Procesos ligeros Hilos y hebras. Recuperado 27 de Octubre de 2008 de http://www.monografias.com/trabajos19/sistemas-operativos/sistemas operativos.shtml#admin
2.4.2 Sincronización Procesos en SO
La sincronización es la transmisión y recepción de señales que tiene por objeto llevar a cabo el trabajo de un grupo de procesos cooperativos. Es la coordinación y cooperación de un conjunto de procesos para asegurar la comparación de recursos de cómputo. La sincronización entre procesos es necesaria para prevenir y/o corregir errores de sincronización debidos al acceso concurrente a recursos compartidos.
La sincronización permite intercambiar señales de tiempo (ARRANQUE/PARADA) entre procesos cooperantes para garantizar las relaciones específicas de precedencia impuestas por el problema que se resuelve. Para que los procesos puedan sincronizarse es necesario disponer de servicios que permitan bloquear o suspender bajo determinadas circunstancias la ejecución de un proceso.
• Si no hay ningún proceso con la tubería abierta para lectura, la operación devuelve el correspondiente error.
• Una operación de escritura sobre una tubería se realiza de forma atómica, es decir, si dos procesos intentan escribir de forma simultánea en una tubería, sólo uno de ellos lo hará. El otro se bloque á hasta que finalice la primera escritura. Lectura de una tubería Una operación de lectura de una tubería obtiene los datos almacenados en la misma.
• Al igual que las escrituras, las operaciones de lectura sobre una tubería son atómicas.
• Con nombre. Se puede utilizar para comunicar y sincronizar procesos independientes. Señales Las señales tienen frente al proceso el mismo comportamiento que las interrupciones tienen frente al procesador, por lo que se puede decir que una señal es una interrupción al proceso.
El proceso que recibe una señal se comporta de la siguiente manera:
• El proceso detiene su ejecución en la instrucción de máquina que está ejecutando.
• Bifurca a ejecutar una rutina de tratamiento de la señal, cuyo código ha de formar parte del propio proceso.
• Una vez ejecutada la rutina de tratamiento, sigue la ejecución del proceso en la instrucción en el que fue interrumpido. El origen de una señal puede ser un proceso a otro proceso o grupo de procesos con el mismo identificador de usuario o bien, el sistema operativo puede enviar señales a los procesos.
El empleo de señales, no es un mecanismo muy apropiado para sincronizar procesos debido a las siguientes razones:
• Las señales tienen un comportamiento asíncrono. Un proceso puede recibir una señal en cualquier punto de su ejecución, aunque no esté esperando su recepción.
2.4.2.1 Mecanismo de Semáforos
En 1965, E.W. Dijkstra sugirió el uso de una variable entera para contar el número de despertares almacenados para su uso posterior. En su propuesta se presentó un nuevo tipo de variable, llamada Semáforo. Un semáforo puede tener el valor 0, lo que indica que no existen despertares almacenados; o bien algún valor positivo si están pendientes uno o más despertares.
Dijkstra, propuso dos operaciones, DOWN y UP (generalizaciones de SLEEP y WAKEUP, respectivamente). La operación Down verifica si el valor de un semáforo es mayor que 0. En este caso, decremento el valor (es decir, utiliza un despertar almacenado) y continúa. Si el valor es cero, el proceso se va a dormir.
La verificación y modificación del valor, así como la posibilidad de irse a dormir se realiza en conjunto, como una sola e indivisible acción atómica. Se garantiza que al iniciar una operación con un semáforo, ningún otro proceso puede tener acceso a semáforo hasta que la operación termine o se bloquee. Esta atomicidad es absolutamente esencial para resolver los problemas de sincronización y evitar condiciones de competencia.
Un semáforo es una variable protegida, cuyo valor sólo puede ser leído y alterado mediante las operaciones P y V, y una operación de asignación de valores iniciales y (Inicia semáforo).
TIPOS DE SEMÁFOROS
SEMÁFOROS BINARIOS (VALORES DE 1,0) SEMÁFOROS CONTADORES (Valores enteros no negativos)
La exclusión mutua sobre el semáforo S se implanta dentro de P(S) y V(S). Si varios procesos desean ejecutar una operación P(S) de manera simultánea , sólo se podrá ejecutar uno de ellos, pero esto no quiere decir que se aplazarán en forma indefinida.
2.4.2.2 Mecanismo de Monitores
El interbloqueo se puede definir 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 gestión concurrente de procesos, no existe una solución eficiente para el caso general.
Todos los interbloqueos suponen necesidades contradictorias de recursos por parte de dos o más procesos.
EJEMPLOS DE INTERBLOQUEO
Ejemplo 1: Interbloqueo de tráfico
Cuatro coches llegan aproximadamente en el mismo instante a un cruce de cuatro caminos. Los cuatro cuadrantes de la intersección 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:
- 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.
La norma más habitual en la carretera es que un coche en un cruce de cuatro caminos debe ceder el paso al coche que está a su derecha. Esta norma funciona si solo hay dos o tres coches en el cruce. Por ejemplo, si solo llegan al cruce los coches del norte y del oeste, el coche del norte esperará hasta que el del oeste pase. Sin embargo, si los cuatro coches llegan al mismo tiempo cada uno se abstendrá de entrar en el cruce, provocando interbloqueo. Si todos los coches ignoran las normas y entran (con cuidado) en el cruce, cada coche obtendrá un recurso (un cuadrante) pero no podrá continuar porque el segundo recurso que necesita ya ha sido invadido por otro coche. De nuevo, se tiene interbloqueo.
RECURSOS
Un sistema se compone de un número finito de recursos que se distribuyen entre varios tipos:
- Físicos: Ciclo de cpu, espacio en memoria, dispositivos de e/s (impresoras, unidades de cinta, etc.)
- Lógicos: Ficheros, tablas del sistemas, semáforos.
Por lo general, una computadora tiene distintos recursos que pueden ser otorgados. Algunos recursos podrán tener varias instancias idénticas, 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. 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
Un recurso apropiable es aquel que se puede tomar del proceso que lo posee sin efectos dañinos. La memoria es un ejemplo de recurso apropiable.
Por el contrario, un recurso no apropiable, es aquel que no se puede tomar de su poseedor activo sin provocar un fallo de cálculo. 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.
El interbloque se puede definir entonces de la siguiente forma:
Un conjunto de procesos se encuentra en estado de interbloqueo cuando cada uno de ellos espera un suceso que solo puede originar otro proceso del mismo conjunto.
En la mayoría de los casos, el evento que espera cada proceso es la liberación de cierto recurso que posee por el momento otro miembro del conjunto.
En otras palabras, cada miembro del conjunto de procesos bloqueados espera un recurso poseído por un proceso bloqueado. Ninguno de los procesos puede continuar su ejecución, ni liberar recursos, y puede ser despertado.
Samuel Alexander Escoto (2001, marzo 15). Segmentación de sistemas operativos.recuperado 27 de Octubre de 2008 de http://www.monografias.com/trabajos15/sist-operativos/sist-operativos2.shtml
El interbloqueo puede definirse formalmente como sigue: Un conjunto de procesos está en interbloqueo si cada proceso del conjunto está esperando un evento que sólo otro proceso del conjunto puede causar. Puesto que todos los procesos están esperando, ninguno de ellos puede causar ninguno de los eventos que podrían despertar a cualquiera de los demás miembros del conjunto, y todos los procesos continúan esperando indefinidamente.
Tipos de recursos
Reutilizables: Un recurso reutilizable es aquél que puede ser usado con seguridad por un proceso y no se agota con el uso. Los procesos obtienen unidades de recursos que liberan posteriormente para que otros procesos las reutilicen. Como ejemplos de recursos reutilizables se tienen los procesadores, canales de E/S, memoria principal y secundaria, dispositivos y estructuras de datos tales como archivos, bases de datos y semáforos.
Consumibles: Un recurso consumible es aquél que puede ser creado (producido) y destruido (consumido). Normalmente, no hay límite en el número de recursos consumibles de un tipo en particular
Condiciones para el interbloqueo
Coffman (1971) demostró que deben cumplirse cuatro condiciones para que haya un bloqueo mutuo:
1. Condición de exclusión mutua. Cada recurso está asignado únicamente a un solo proceso o está disponible.
2. Condición de retener y esperar. Los procesos que actualmente tienen recursos que les fueron otorgados previamente pueden solicitar nuevos recursos.
3. Condición de no expropiación. No es posible quitarle por la fuerza a un proceso los recursos que le fueron otorgados previamente. El proceso que los tiene debe liberarlos explícitamente.
4. Condición de espera circular. Debe haber una cadena circular de dos o más procesos, cada uno de los cuales está esperando un recurso retenido por el siguiente miembro de la cadena.
Deben estar presentes estas cuatro condiciones para que ocurra un bloqueo mutuo. Si una o más de estas condiciones están ausentes, no puede haber bloqueo mutuo.
Prevención La estrategia de prevención del interbloqueo consiste, a grandes rasgos, en diseñar un sistema de manera que esté excluida, a priori, la posibilidad de interbloqueo. Los métodos para prevenir el interbloqueo son de dos tipos. Los métodos indirectos consisten en impedir la aparición de alguna de las tres condiciones necesarias, antes mencionadas (condiciones 1 a 3). Los métodos directos consisten en evitar la aparición del círculo vicioso de espera (condición 4).
Retención y Espera
La condición de retención y espera puede prevenirse exigiendo que todos los procesos soliciten todos los recursos que necesiten a un mismo tiempo y bloqueando el proceso hasta que todos los recursos puedan concederse simultáneamente. Esta solución resulta ineficiente por dos factores. En primer lugar, un proceso puede estar suspendido durante mucho tiempo, esperando que se concedan todas sus solicitudes de recursos, cuando de hecho podría haber avanzado con sólo algunos de los recursos.
2.4.3.1 Prevención Interbloqueo DeadLock
Los bloqueos mutuos pueden ser evitados si se sabe cierta información sobre los procesos antes de la asignación de recursos. Para cada petición de recursos, el sistema controla si satisfaciendo el pedido entra en un estado inseguro, donde puede producirse un bloqueo mutuo. Existen varios algoritmos para evitar bloqueos mutuos: Algoritmo del banquero, introducido por Dijkstra. Algoritmo de grafo de asignación de recursos. Algoritmo de Seguridad. Algoritmo de solicitud de recursos.
Prevención
Los bloqueos mutuos pueden prevenirse asegurando que no suceda alguna de las condiciones necesarias vistas anteriormente.
Eliminando la exclusión mutua: ningún proceso puede tener acceso exclusivo a un recurso. Esto es imposible para procesos que no pueden ser encolados (puestos en un spool), e incluso con colas también pueden ocurrir interbloqueos. La condición de retención y espera puede ser eliminada haciendo que los procesos pidan todos los recursos que van a necesitar antes de empezar. Este conocimiento por adelantado muchas veces es imposible nuevamente. Otra forma es requerir a los procesos liberar todos sus recursos antes de pedir todos los recursos que necesitan.
2.4.3.2 Detección Interbloqueo DeadLock
Las estrategias de prevención del interbloqueo son muy conservadoras; solucionan el problema del interbloqueo limitando el acceso a los recursos e imponiendo restricciones a los procesos. En el lado opuesto, las estrategias de detección del interbloqueo no limitan el acceso a los recursos ni restringen las acciones de los procesos.
Una vez detectado el interbloqueo, hace falta alguna estrategia de recuperación. Las técnicas siguientes son posibles enfoques, enumeradas en orden creciente de sofisticación:
1. Abandonar todos los procesos bloqueados. Esta es, se crea o no, una de las soluciones más comunes, si no la más común, de las adoptadas en un sistema operativo.
2. Retroceder cada proceso interbloqueado hasta algún punto de control definido previamente y volver a ejecutar todos los procesos. Es necesario que haya disponibles unos mecanismos de retroceso y reinicio en el sistema. El riesgo de esta solución radica en que puede repetirse el interbloqueo original.
3. Abandonar sucesivamente los procesos bloqueados hasta que deje de haber interbloqueo. El orden en el que se seleccionan los procesos a abandonar seguirá un criterio de mínimo coste.
4. Apropiarse de recursos sucesivamente hasta que deje de haber interbloqueo.
Para los puntos 3 y 4, el criterio de selección podría ser uno de los siguientes, consistentes en escoger el proceso con:
Algunas de estas cantidades son más fáciles de medir que otras. El tiempo restante estimado deja lugar a dudas, especialmente. Además, aparte de las medidas de prioridad, no existe otra indicación del “coste” para el usuario frente al coste para el sistema en conjunto.
2.4.3.3 Recuperación Interbloqueo DeadLock
Una vez que se ha detectado el interbloqueo se debe romper para que los recursos puedan finalizar su ejecución y liberar así los recursos. Para ruptura de la espera se pueden realizar varias opciones. Las idónea sería suspendiendo algunos de los procesos bloqueados para tomar sus recursos y reanudar sus ejecución una vez que se hubiera deshecho el interbloqueo. Esta solución solo puede resultar factible en casos muy particulares; no se podría suspender a un proceso de escribir de escribir en una impresora para pasarla a otro proceso y reanudar después la impresión, como tampoco se podría suspender indefinidamente un proceso de tiempo real.
Para aplicar la primera de las opciones se deben tener en cuenta una serie de factores con el fin de elegir aquellos procesos cuya reiniciación resulte menos traumática.
Entre los factores a tener en cuenta en cada proceso se tienen:
1. La prioridad del proceso.
2. El tiempo de procesamiento utilizado y el que le resta.
3. El tipoy numero de recursos que posee.
4. El numero de recursos que necesita para finalizar.
El procedimiento de la segunda opción consiste en ir expropiando recursos de algunos procesos de forma sucesiva hasta que se consiga salir del interbloqueo. La elección de los recursos que se expropian se basa en criterios similares a los expuestos en la reiniciación de los procesos.
Samuel Alexander Escoto (2001, marzo 15). Segmentación de sistemas operativos.recuperado 27 de Octubre de 2008 de http://www.monografias.com/trabajos15/sist-operativos/sist-operativos2.shtml
No hay comentarios:
Publicar un comentario