Cada proceso se ejecuta asíncronamente con respecto a otro (son impredecibles las frecuencias de reloj asociadas).
En algunos instantes, los procesos deben sincronizar sus actividades; por ejemplo, en el caso de que un proceso no pueda progresar hasta que otro haya terminado algún tipo de actividad.[1]
Un sistema operativo multiprogramado es un caso particular de sistema concurrente donde los procesos compiten por el acceso a los recursos compartidos o cooperan dentro de una misma aplicación para comunicar información. Ambas situaciones son tratadas por el sistema operativo mediante mecanismos de sincronización que permiten el acceso exclusivo de forma coordinada a los recursos y a los elementos de comunicación compartidos.
Según el modelo de sistema operativo descrito anteriormente, basado en colas de procesos y transiciones de estados, los procesos abandonan la CPU para pasar a estado bloqueado cuando requieren el acceso a algún dispositivo, generalmente en una operación de E/S, pasando a estado preparado cuando la operación ha concluido y eventualmente volver a ejecución. La gestión de estos cambios de estado, es decir, los cambios de contexto, es un ejemplo de sección crítica de código dentro del sistema operativo que debe ser ejecutada por éste en exclusión mutua. Otros ejemplos de código que debe protegerse como sección crítica incluyen la programación de los dispositivos de E/S y el acceso a estructuras de datos y buffers compartidos.
El concepto de comunicación es algo más general y supone la existencia de algún mecanismo de sincronización subyacente. Dentro del sistema operativo, el espacio de direcciones es único, por lo que la comunicación se puede resolver mediante el uso de variables en memoria compartida. Como contrapartida a la agilidad de este esquema, es necesario utilizar mecanismos de sincronización explícitos para garantizar acceso exclusivo a las variables compartidas y evitar condiciones de carrera. Puede producirse una condición de carrera sobre una variable cuando varios procesos acceden concurrentemente a la variable para actualizarla.[2]
El SO ofrece mecanismos básicos de comunicación, que permiten transferir cadenas de bytes. Deben ser los procesos que se comunican quienes interpreten el significado de las cadenas transferidas para su labor coordinada.
Los mecanismos de comunicación y sincronización son dinámicos. Es decir, cuando se necesita un mecanismo de este estilo, se crea, usa y destruye, de forma que no se establezca de forma definitiva ningún mecanismo de comunicación, ya que ellos podrían producir efectos indeseados. Es decir, la comunicación es algo puntual.
Los servicios básicos de comunicación son:
a. crear: el proceso solicita la creación del mecanismo
b. enviar o escribir: el proceso emisor envía información al proceso receptor
c. recibir o leer: el proceso receptor recibe información
d. destruir: el proceso solicita la destrucción del mecanismo de comunicación
La comunicación puede ser sincrona y asíncrona:
a. síncrona: los dos procesos han de ejecutar servicios de forma simultánea. El emisor ha de ejecutar el servicio enviar mientras el receptor ejecuta recibir.
b. asíncrona: el emisor hace el envío y prosigue su ejecución. El SO ofrece un almacenamiento intermedio para guardar la información enviada, hasta que el receptor la solicite.
Dentro del núcleo del sistema operativo, el espacio de direcciones es único, por lo que la comunicación se resuelve mediante el uso de variables de memoria compartida. Como contrapartida a la agilidad de este esquema, es necesario utilizar mecanismos explícitos de sincronización para garantizar acceso exclusivo a las variables compartidas. Si se definen buffers o colas compartidas a las que se proporciona acceso exclusivo, se pueden utilizar esquemas de comunicación más elaborados, como es el caso del productor-consumidor. El esquema cliente-servidor es un caso particular del productor-consumidor donde los clientes producen peticiones que son consumidas por el servidor de un determinado recurso. Un sistema operativo con estructura cliente-servidor resulta atractivo por la claridad de su diseño. Cuando los procesos que se comunican mediante estos esquemas no comparten el espacio de direcciones, lo que sucede en particular en sistemas basados en micro núcleo, se requieren primitivas de comunicación por paso de mensajes, que, al gestionar implícitamente la sincronización, simplifican la programación de la comunicación.[3]
[1] Procesos e hilos: concurrencia, sincronización y comunicación. (n.d.) Extraído el 24 de octubre de 2008 desde http://www.ual.es/~rguirado/so/tema2.pdf
[2] Control de procesos y sincronización. (n.d) Extraído el 24 de octubre de 2008 desde http://www.sc.ehu.es/acwlaroa/SO2/Apuntes/Cap2.pdf
[3] Miguel pita, Sincronización entre procesos. (n.d.) Extraído el 24 de octubre de 2008 desde http://www.monografias.com/trabajos51/sincro-comunicacion/sincro-comunicacion2.shtml
lunes, 27 de octubre de 2008
2.4.2.1 MECANISMO DE SEMÁFOROS.
Un semáforo es un mecanismo de comunicación con el cual no se mueven datos, puesto que solo se puede consultar y modificar su valor al tener un carácter puramente informativo.
Dijkstra define un semáforo como una variable entera positiva o nula sobre la que sólo se pueden realizar dos operaciones: wait (también denominada P) y signal (también denominada V). La operación wait decrementa el valor del semáforo siempre que éste tenga un valor mayor que 0; por lo tanto esta operación se utiliza para adquirir el semáforo o para bloquearlo en el caso de que valga 0. La operación signal incrementa el valor del semáforo y por tanto se utiliza para liberarlo o inicializarlo.
Ambas operaciones deben ser atómicas para que funcionen correctamente; es decir que una operación wait no puede ser interrumpida por otra operación wait o signal sobre el mismo semáforo, y lo mismo ocurre para la operación signal. Este hecho garantiza que cuando varios procesos compitan por la adquisición de un semáforo, sólo uno de ellos va a poder realizar la operación.
Además, se ha de indicar que este mecanismo memoriza las peticiones de operaciones wait no satisfechas y despierta por tanto a los procesos en espera.
Es una solución sencilla y elegante del problema de la exclusión mutua. Esta técnica permite solucionar la mayoría de los problemas de sincronización entre procesos. Un semáforo binario es un indicador de condición (s) que registra si un registro está disponible o no. Un semáforo sólo puede tomar dos valores; 0 y 1. Si para un semáforo, S=1 el recurso está disponible y la tarea lo puede utilizar; si S=0 el recurso no está disponible y el proceso debe esperar.
Los semáforos se implementan mediante una cola de tareas a la que se añaden los procesos que están en espera del recurso. Solo se permiten tres operaciones sobre un semáforo:
1. Inicializa (s: Semáforo_Binario; v: integer) -- > poner el valor del semáforo s al valor de v (0,1).
2. Espera (wait)(s) if s = 1 then s: = 0 else Suspender la tarea que hace la llamada y ponerla en la cola de tareas.
3. Señal (signal)(s) if cola de tareas vacía then s : = 1 else Reanudar la primera tarea de la cola tareas.
Estas operaciones son procedimientos que se implementan como acciones indivisibles. En sistemas con un único procesador bastará simplemente con inhibir las interrupciones durante la ejecución de las operaciones del semáforo. Al introducir el semáforo se crea un nuevo estado en el diagrama de transiciones, el de espera.
Figura 5 Operaciones sobre un semáforo
Exclusión mutua con semáforos
La exclusión mutua se realiza fácilmente usando semáforos. La operación de espera se usará como procedimiento de bloqueo antes de acceder a una sección crítica y la operación señal como procedimiento de desbloqueo. Se emplean tantos semáforos como clases de secciones críticas se establecen.
Sincronización
Las operaciones espera y señal no se utilizan dentro de un mismo proceso sino que sedan en dos procesos separados, el que ejecuta espera queda bloqueado hasta que el otro ejecuta señal.
Versión general de los semáforos
El semáforo binario resulta adecuado cuando hay que proteger un recurso que pueden compartir varios procesos, pero cuando lo que hay que proteger es un conjunto de recursos similares, se puede usar una versión más general del concepto de semáforo que lleve la cuenta del número de recursos disponibles. En este caso el semáforo se inicializa con el número total de recursos disponibles (n) y las operaciones de espera y señal se diseñan de modo que se impida el acceso al recurso protegido por el semáforo cuando el valor de éste es menor o igual que cero.
Cada vez que se solicita y obtiene un recurso, el semáforo se decrementa y se incrementa cuando se libera uno de ellos.
Si la operación de espera se ejecuta cuando el semáforo tiene un valor menor que 1, el proceso debe quedar en espera de que la ejecución de una operación señal libere alguno de los recursos.[1]
Dijkstra define un semáforo como una variable entera positiva o nula sobre la que sólo se pueden realizar dos operaciones: wait (también denominada P) y signal (también denominada V). La operación wait decrementa el valor del semáforo siempre que éste tenga un valor mayor que 0; por lo tanto esta operación se utiliza para adquirir el semáforo o para bloquearlo en el caso de que valga 0. La operación signal incrementa el valor del semáforo y por tanto se utiliza para liberarlo o inicializarlo.
Ambas operaciones deben ser atómicas para que funcionen correctamente; es decir que una operación wait no puede ser interrumpida por otra operación wait o signal sobre el mismo semáforo, y lo mismo ocurre para la operación signal. Este hecho garantiza que cuando varios procesos compitan por la adquisición de un semáforo, sólo uno de ellos va a poder realizar la operación.
Además, se ha de indicar que este mecanismo memoriza las peticiones de operaciones wait no satisfechas y despierta por tanto a los procesos en espera.
Es una solución sencilla y elegante del problema de la exclusión mutua. Esta técnica permite solucionar la mayoría de los problemas de sincronización entre procesos. Un semáforo binario es un indicador de condición (s) que registra si un registro está disponible o no. Un semáforo sólo puede tomar dos valores; 0 y 1. Si para un semáforo, S=1 el recurso está disponible y la tarea lo puede utilizar; si S=0 el recurso no está disponible y el proceso debe esperar.
Los semáforos se implementan mediante una cola de tareas a la que se añaden los procesos que están en espera del recurso. Solo se permiten tres operaciones sobre un semáforo:
1. Inicializa (s: Semáforo_Binario; v: integer) -- > poner el valor del semáforo s al valor de v (0,1).
2. Espera (wait)(s) if s = 1 then s: = 0 else Suspender la tarea que hace la llamada y ponerla en la cola de tareas.
3. Señal (signal)(s) if cola de tareas vacía then s : = 1 else Reanudar la primera tarea de la cola tareas.
Estas operaciones son procedimientos que se implementan como acciones indivisibles. En sistemas con un único procesador bastará simplemente con inhibir las interrupciones durante la ejecución de las operaciones del semáforo. Al introducir el semáforo se crea un nuevo estado en el diagrama de transiciones, el de espera.
Figura 5 Operaciones sobre un semáforo
Exclusión mutua con semáforos
La exclusión mutua se realiza fácilmente usando semáforos. La operación de espera se usará como procedimiento de bloqueo antes de acceder a una sección crítica y la operación señal como procedimiento de desbloqueo. Se emplean tantos semáforos como clases de secciones críticas se establecen.
Sincronización
Las operaciones espera y señal no se utilizan dentro de un mismo proceso sino que sedan en dos procesos separados, el que ejecuta espera queda bloqueado hasta que el otro ejecuta señal.
Versión general de los semáforos
El semáforo binario resulta adecuado cuando hay que proteger un recurso que pueden compartir varios procesos, pero cuando lo que hay que proteger es un conjunto de recursos similares, se puede usar una versión más general del concepto de semáforo que lleve la cuenta del número de recursos disponibles. En este caso el semáforo se inicializa con el número total de recursos disponibles (n) y las operaciones de espera y señal se diseñan de modo que se impida el acceso al recurso protegido por el semáforo cuando el valor de éste es menor o igual que cero.
Cada vez que se solicita y obtiene un recurso, el semáforo se decrementa y se incrementa cuando se libera uno de ellos.
Si la operación de espera se ejecuta cuando el semáforo tiene un valor menor que 1, el proceso debe quedar en espera de que la ejecución de una operación señal libere alguno de los recursos.[1]
[1] Universidad Nacional de Educación a Distancia (UNED)/Ingeniería Técnica en Informática (Gestión/Sistemas).Sistemas Operativos I Tema-III/I-Sincronización y comunicación de procesos/I (n.d). Extraído el 24 de octubre de 2008 desde http://www.erubio.es/files/SO1_Tema3_1.pdf
2.4.2.2 MECANISMO DE MONITORES.
Los monitores son estructuras de datos utilizadas en lenguajes de programación para sincronizar dos o más procesos o hilos de ejecución que usan recursos compartidos.
En el estudio y uso de los semáforos se puede ver que las llamadas a las funciones necesarias para utilizarlos quedan repartidas en el código del programa, haciendo difícil corregir errores y asegurar el buen funcionamiento de los algoritmos. Para evitar estos inconvenientes se desarrollaron los monitores. El concepto de monitor fue definido por primera vez por Charles Antony Richard Hoare en un artículo del año 1974. La estructura de los monitores se ha implementado en varios lenguajes de programación, incluido Pascal concurrente, Modula-2, Modula-3 y Java, y como biblioteca de programas.
Componentes
Un monitor tiene cuatro componentes: inicialización, datos privados, procedimientos del monitor y cola de entrada.
Inicialización: contiene el código a ser ejecutado cuando el monitor es creado
Datos privados: contiene los procedimientos privados, que sólo pueden ser usados desde dentro del monitor y no son visibles desde fuera
Procedimientos del monitor: son los procedimientos que pueden ser llamados desde fuera del monitor.
Cola de entrada: contiene a los threads que han llamado a algún procedimiento del monitor pero no han podido adquirir permiso para ejecutarlos aún.
Exclusión mutua en un monitor
Los monitores están pensados para ser usados en entornos multiproceso o multihilo, y por lo tanto muchos procesos o threads pueden llamar a la vez a un procedimiento del monitor. Los monitores garantizan que en cualquier momento, a lo sumo un thread puede estar ejecutando dentro de un monitor. Ejecutar dentro de un monitor significa que sólo un thread estará en estado de ejecución mientras dura la llamada a un procedimiento del monitor. El problema de que dos threads ejecuten un mismo procedimiento dentro del monitor es que se pueden dar condiciones de carrera, perjudicando el resultado de los cálculos. Para evitar esto y garantizar la integridad de los datos privados, el monitor hace cumplir la exclusión mutua implícitamente, de modo que sólo un procedimiento esté siendo ejecutado a la vez. De esta forma, si un thread llama a un procedimiento mientras otro thread está dentro del monitor, se bloqueará y esperará en la cola de entrada hasta que el monitor quede nuevamente libre. Aunque se la llama cola de entrada, no debería suponerse ninguna política de encolado.
Para que resulten útiles en un entorno de concurrencia, los monitores deben incluir algún tipo de forma de sincronización. Por ejemplo, supóngase un thread que está dentro del monitor y necesita que se cumpla una condición para poder continuar la ejecución. En ese caso, se debe contar con un mecanismo de bloqueo del thread, a la vez que se debe liberar el monitor para ser usado por otro hilo. Más tarde, cuando la condición permita al thread bloqueado continuar ejecutando, debe poder ingresar en el monitor en el mismo lugar donde fue suspendido. Para esto los monitores poseen variables de condición que son accesibles sólo desde adentro. Existen dos funciones para operar con las variables de condición:
cond_wait(c): suspende la ejecución del proceso que la llama con la condición c. El monitor se convierte en el dueño del lock y queda disponible para que otro proceso pueda entrar
cond_signal(c): reanuda la ejecución de algún proceso suspendido con cond_wait bajo la misma condición. Si hay varios procesos con esas características elige uno. Si no hay ninguno, no hace nada.
Nótese que, al contrario que los semáforos, la llamada a cond_signal(c) se pierde si no hay tareas esperando en la variable de condición c.
Las variables de condición indican eventos, y no poseen ningún valor. Si un thread tiene que esperar que ocurra un evento, se dice espera por (o en) la variable de condición correspondiente. Si otro thread provoca un evento, simplemente utiliza la función cond_signal con esa condición como parámetro. De este modo, cada variable de condición tiene una cola asociada para los threads que están esperando que ocurra el evento correspondiente. Las colas se ubican en el sector de datos privados visto anteriormente.
La política de inserción de procesos en las colas de las variables condición es la FIFO, ya que asegura que ningún proceso caiga en la espera indefinida, cosa que sí ocurre con la política LIFO (puede que los procesos de la base de la pila nunca sean despertados) o con una política en la que se desbloquea a un proceso aleatorio.
Características:
• Es un proceso que se encarga de verificar el funcionamiento de algún recurso garantizando la exclusión mutua (mutex).
• En un monitor los procesos se bloquean y desbloquean.
• Pueden existir diversas implementaciones no estandarizadas de un monitor.
• En Java los monitores están implementados de manera nativa con el modificador de los métodos syncronized.
• El monitor es el mecanismo que nos permite controlar el acceso a una región crítica, en este caso un método. También se puede utilizar semáforos como objetos mutex disponibles en el paquete java.util.concurrent.*;[1]
[1] Monitores (Concurrencia) (30 de septiembre de 2008). Extraído el 24 de octubre de 2008 desde http://es.wikipedia.org/wiki/Monitor_(concurrencia)
En el estudio y uso de los semáforos se puede ver que las llamadas a las funciones necesarias para utilizarlos quedan repartidas en el código del programa, haciendo difícil corregir errores y asegurar el buen funcionamiento de los algoritmos. Para evitar estos inconvenientes se desarrollaron los monitores. El concepto de monitor fue definido por primera vez por Charles Antony Richard Hoare en un artículo del año 1974. La estructura de los monitores se ha implementado en varios lenguajes de programación, incluido Pascal concurrente, Modula-2, Modula-3 y Java, y como biblioteca de programas.
Componentes
Un monitor tiene cuatro componentes: inicialización, datos privados, procedimientos del monitor y cola de entrada.
Inicialización: contiene el código a ser ejecutado cuando el monitor es creado
Datos privados: contiene los procedimientos privados, que sólo pueden ser usados desde dentro del monitor y no son visibles desde fuera
Procedimientos del monitor: son los procedimientos que pueden ser llamados desde fuera del monitor.
Cola de entrada: contiene a los threads que han llamado a algún procedimiento del monitor pero no han podido adquirir permiso para ejecutarlos aún.
Exclusión mutua en un monitor
Los monitores están pensados para ser usados en entornos multiproceso o multihilo, y por lo tanto muchos procesos o threads pueden llamar a la vez a un procedimiento del monitor. Los monitores garantizan que en cualquier momento, a lo sumo un thread puede estar ejecutando dentro de un monitor. Ejecutar dentro de un monitor significa que sólo un thread estará en estado de ejecución mientras dura la llamada a un procedimiento del monitor. El problema de que dos threads ejecuten un mismo procedimiento dentro del monitor es que se pueden dar condiciones de carrera, perjudicando el resultado de los cálculos. Para evitar esto y garantizar la integridad de los datos privados, el monitor hace cumplir la exclusión mutua implícitamente, de modo que sólo un procedimiento esté siendo ejecutado a la vez. De esta forma, si un thread llama a un procedimiento mientras otro thread está dentro del monitor, se bloqueará y esperará en la cola de entrada hasta que el monitor quede nuevamente libre. Aunque se la llama cola de entrada, no debería suponerse ninguna política de encolado.
Para que resulten útiles en un entorno de concurrencia, los monitores deben incluir algún tipo de forma de sincronización. Por ejemplo, supóngase un thread que está dentro del monitor y necesita que se cumpla una condición para poder continuar la ejecución. En ese caso, se debe contar con un mecanismo de bloqueo del thread, a la vez que se debe liberar el monitor para ser usado por otro hilo. Más tarde, cuando la condición permita al thread bloqueado continuar ejecutando, debe poder ingresar en el monitor en el mismo lugar donde fue suspendido. Para esto los monitores poseen variables de condición que son accesibles sólo desde adentro. Existen dos funciones para operar con las variables de condición:
cond_wait(c): suspende la ejecución del proceso que la llama con la condición c. El monitor se convierte en el dueño del lock y queda disponible para que otro proceso pueda entrar
cond_signal(c): reanuda la ejecución de algún proceso suspendido con cond_wait bajo la misma condición. Si hay varios procesos con esas características elige uno. Si no hay ninguno, no hace nada.
Nótese que, al contrario que los semáforos, la llamada a cond_signal(c) se pierde si no hay tareas esperando en la variable de condición c.
Las variables de condición indican eventos, y no poseen ningún valor. Si un thread tiene que esperar que ocurra un evento, se dice espera por (o en) la variable de condición correspondiente. Si otro thread provoca un evento, simplemente utiliza la función cond_signal con esa condición como parámetro. De este modo, cada variable de condición tiene una cola asociada para los threads que están esperando que ocurra el evento correspondiente. Las colas se ubican en el sector de datos privados visto anteriormente.
La política de inserción de procesos en las colas de las variables condición es la FIFO, ya que asegura que ningún proceso caiga en la espera indefinida, cosa que sí ocurre con la política LIFO (puede que los procesos de la base de la pila nunca sean despertados) o con una política en la que se desbloquea a un proceso aleatorio.
Características:
• Es un proceso que se encarga de verificar el funcionamiento de algún recurso garantizando la exclusión mutua (mutex).
• En un monitor los procesos se bloquean y desbloquean.
• Pueden existir diversas implementaciones no estandarizadas de un monitor.
• En Java los monitores están implementados de manera nativa con el modificador de los métodos syncronized.
• El monitor es el mecanismo que nos permite controlar el acceso a una región crítica, en este caso un método. También se puede utilizar semáforos como objetos mutex disponibles en el paquete java.util.concurrent.*;[1]
[1] Monitores (Concurrencia) (30 de septiembre de 2008). Extraído el 24 de octubre de 2008 desde http://es.wikipedia.org/wiki/Monitor_(concurrencia)
2.4.3.- INTERBLOQUEO (DEADLOCK)
Definición
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.
Ejemplo de interbloqueos
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.
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.
Ejemplo de interbloqueos
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 numero 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, etc.
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.
Los interbloqueos se relacionan con los recursos no apropiables. Lo usual es que los bloqueos asociados a recursos apropiables se pueden resolver, mediante la reasignación de recursos de un proceso a otro.
La secuencia de eventos necesaria para utilizar un recurso es:
- Solicitar el recurso
- Utilizar el recurso
- Liberar el recurso
Si el recurso no está disponible cuando se le solicita, el proceso solicitante debe esperar. En algunos sistemas operativos, el proceso se bloquea de manera automática al fallar una solicitud de un recurso y se despierta cuando dicho recurso está disponible. En otros sistemas la solicitud falla con un código de error y el proceso solicitante debe esperar un poco e intentar de nuevo.
Un proceso cuya solicitud de un recurso ha sido denegada entra por lo general en un ciclo, en el cual solicita el recurso, duerme e intenta de nuevo.
Aunque este proceso no está bloqueado, para todos los efectos esta como bloqueado, puesto que no puede hacer ninguna labor útil.
CONDICIONES PARA PRODUCIR INTERBLOQUEO
En la política del sistema operativo, deben darse tres condiciones para que pueda producirse un interbloqueo:
1- Condición de exclusión mutua: Cada recurso está asignado a un único proceso o está disponible.
2- Condición de posesión y espera: Los procesos que tienen, en un momento dado, recursos asignados con anterioridad, pueden solicitar nuevos recursos.
3- Condición de no apropiación: Los recursos otorgados con anterioridad no pueden ser forzados a dejar un proceso. El proceso que los posee debe liberarlos en forma explícita.
En la mayoría de los casos, estas condiciones son bastantes necesarias. La exclusión mutua hace falta para asegurar la consistencia de resultados y la integridad de la base de datos. De forma similar, la apropiación no se puede aplicar arbitrariamente y, cuando se encuentran involucrados recursos de datos, debe estar acompañada de un mecanismo de recuperación y reanudación, que devuelva un proceso y sus recursos a un estado previo adecuado, desde el que el proceso puede finalmente repetir sus acciones.
Puede no existir interbloqueo con solo estas tres condiciones. Para que se produzca interbloqueo, se necesita una cuarta condición:
4- Condición de espera circular (o círculo vicioso de espera): Debe existir una cadena circular de dos o más procesos, cada uno de los cuales espera un recurso poseído por el siguiente miembro de la cadena.
Las tres primeras condiciones son necesarias, pero no suficientes, para que exista interbloqueo. La cuarta condición es, en realidad, una consecuencia potencial de las tres primeras. Es decir, dado que se producen las tres primeras condiciones, puede ocurrir una secuencia de eventos que desemboque en un círculo vicioso de espera irresoluble. El círculo de espera de la condición 4 es irresoluble porque se mantienen las tres primeras condiciones. Las cuatro condiciones en conjunto constituyen una condición necesaria y suficiente para el interbloqueo.
2.4.3.1.-PREVENCION DE UN INTERBLOEQEO
La estrategia básica de la prevención del interbloqueo consiste, a grandes rasgos, en diseñar su 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 que consisten en impedir la aparición de alguna de las tres condiciones necesarias para que se del interbloqueo.
- Los métodos directos que consisten en evitar la aparición del círculo vicioso de espera.
Exclusión mutua
Si ningún recurso se puede asignar de forma exclusiva, no se producirá interbloqueo. Sin embargo, existen recursos para los que no es posible negar la condición de exclusión mutua. No obstante, es posible eliminar esta condición en algunos procesos. Por ejemplo, una impresora es un recurso no compatible pues si se permite que dos procesos escriban en la impresora al mismo tiempo, la salida resulta caótica. Pero con el spooling (en cola) de salida varios procesos pueden generar salida al mismo tiempo. Puesto que el spooler nunca solicita otros recursos, se elimina el bloqueo originado por la impresora.
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 concedan todas sus solicitudes de recursos, cuando de hecho podría haber avanzado con solo algunos de los recursos.
- Y en segundo lugar, los recursos asignados a un proceso pueden permanecer sin usarse durante periodos considerables, tiempo durante el cual se priva del acceso a otros procesos.
No apropiación
La condición de no apropiación puede prevenirse de varias formas. Primero, si a un proceso que retiene ciertos recursos se le deniega una nueva solicitud, dicho proceso deberá liberar sus recursos anteriores y solicitarlos de nuevo, cuando sea necesario, junto con el recurso adicional. Por otra parte, si un proceso solicita un recurso que actualmente está retenido por otro proceso, el sistema operativo debe expulsar al segundo proceso y exigirle que libere sus recursos. Este último esquema evitará el interbloqueo sólo si no hay dos procesos que posean la misma prioridad.
Esta técnica es práctica sólo cuando se aplica a recursos cuyo estado puede salvarse y restaurarse más tarde de una forma fácil, como es el caso de un procesador.
Circulo vicioso de espera
La condición del círculo vicioso de espera puede prevenirse definiendo una ordenación lineal de los tipos de recursos. Si a un proceso se le han asignado recursos de tipo R, entonces sólo podrá realizar peticiones posteriores sobre los recursos de los tipos siguientes a R en la ordenación.
Para comprobar el funcionamiento de esta estrategia, se asocia un índice a cada tipo de recurso.
Como en la retención y espera, la prevención del círculo vicioso de espera puede ser ineficiente, retardando procesos y denegando accesos a recursos innecesariamente.
Los métodos para prevenir el interbloqueo son de dos tipos:
- Los métodos indirectos que consisten en impedir la aparición de alguna de las tres condiciones necesarias para que se del interbloqueo.
- Los métodos directos que consisten en evitar la aparición del círculo vicioso de espera.
Exclusión mutua
Si ningún recurso se puede asignar de forma exclusiva, no se producirá interbloqueo. Sin embargo, existen recursos para los que no es posible negar la condición de exclusión mutua. No obstante, es posible eliminar esta condición en algunos procesos. Por ejemplo, una impresora es un recurso no compatible pues si se permite que dos procesos escriban en la impresora al mismo tiempo, la salida resulta caótica. Pero con el spooling (en cola) de salida varios procesos pueden generar salida al mismo tiempo. Puesto que el spooler nunca solicita otros recursos, se elimina el bloqueo originado por la impresora.
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 concedan todas sus solicitudes de recursos, cuando de hecho podría haber avanzado con solo algunos de los recursos.
- Y en segundo lugar, los recursos asignados a un proceso pueden permanecer sin usarse durante periodos considerables, tiempo durante el cual se priva del acceso a otros procesos.
No apropiación
La condición de no apropiación puede prevenirse de varias formas. Primero, si a un proceso que retiene ciertos recursos se le deniega una nueva solicitud, dicho proceso deberá liberar sus recursos anteriores y solicitarlos de nuevo, cuando sea necesario, junto con el recurso adicional. Por otra parte, si un proceso solicita un recurso que actualmente está retenido por otro proceso, el sistema operativo debe expulsar al segundo proceso y exigirle que libere sus recursos. Este último esquema evitará el interbloqueo sólo si no hay dos procesos que posean la misma prioridad.
Esta técnica es práctica sólo cuando se aplica a recursos cuyo estado puede salvarse y restaurarse más tarde de una forma fácil, como es el caso de un procesador.
Circulo vicioso de espera
La condición del círculo vicioso de espera puede prevenirse definiendo una ordenación lineal de los tipos de recursos. Si a un proceso se le han asignado recursos de tipo R, entonces sólo podrá realizar peticiones posteriores sobre los recursos de los tipos siguientes a R en la ordenación.
Para comprobar el funcionamiento de esta estrategia, se asocia un índice a cada tipo de recurso.
Como en la retención y espera, la prevención del círculo vicioso de espera puede ser ineficiente, retardando procesos y denegando accesos a recursos innecesariamente.
Suscribirse a:
Entradas (Atom)
