domingo, 26 de octubre de 2008

INTRODUCCIÓN

En los sistemas operativos multiprogramados surge el concepto de proceso, asociado a la ejecución de un programa. En general, un proceso es un flujo de ejecución, representado básicamente por un contador de programa, y su contexto de ejecución, que puede ser más o menos amplio. Así, un proceso incluye en su contexto el estado de la pila, el estado de la memoria y el estado de la E/S, mientras que un thread típico tiene como contexto propio poco más que la pila. En algunos sistemas es posible determinar el contexto propio de un proceso en el momento de su creación, como ocurre con la llamada al sistema clone() de Linux. En adelante, sin perder generalidad, utilizaremos siempre el término proceso, independientemente de cuál sea su contexto.

Uno de los objetivos del sistema operativo es la representación de los procesos y el soporte de los cambios de contexto entre procesos, que posibilitan la compartición del recurso CPU. El acceso a otros recursos compartidos y la comunicación entre procesos relacionados (por ejemplo, de una misma aplicación) hacen necesaria la utilización de mecanismos de sincronización dentro del sistema operativo. Típicamente, un proceso requiere la CPU durante un periodo de tiempo, realiza alguna operación de E/S, y vuelve a requerir la CPU, repitiéndose este ciclo hasta la finalización del programa. El proceso pasa por diversos estados entre los que se definen transiciones, como representa, en su forma más sencilla.

Cada vez que un proceso pasa al estado preparado, está compitiendo por el recurso CPU. Un segundo objetivo del sistema operativo multiprogramado es la planificación del uso del (de los) recurso(s) de proceso. Los criterios que se siguen para la planificación y las políticas que se usan se estudiarán mas adelante en el desarrollo de la presente investigación.

Para realizar el estudio de dichas políticas se realiza una sintetizada referencia a la representación de los procesos, para luego definir hilos de ejecución o threads, estableciendo diferencias entre procesos y hilos de ejecución, sus ventajas desventajas, estados, sincronización y tipos, para luego empezar a estudiar el fenómeno de la sincronización de procesos, estableciendo su definición y características, se esboza la definición, modelo, propiedades de la sección critica, así como la descripción detallada de algunos de los principales modelos de sincronización tales como el de exclusión mutua (mutex), semáforos y monitores, el interbloqueo estableciendo su definición, características, condiciones necesarias y suficientes para su existencia, en cuanto a su detección y recuperación, finalmente se estudia las tecnicas de administración del planificador.
.

REFERENCIAS


- Andrew s. tanenbaum & Alvert s. woodhull (1998). Sistemas operativos Diseño e implementación. (2da. Ed).

- Deitel, H. M. (1993) Sistemas Operativos, 2ª Edición, Addison-Wesley.

- Milenkovic M. (1994). Sistemas Operativos. Conceptos y Diseño, 2ª Edición, McGraw-Hill.

- 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

- Stallings, W. (1993).Computer Organization and Architecture, 3ª Edición. New York: Macmillan.

- Silberschatz, A., Peterson, J., Galvin, P. (1994) Sistemas Operativos. Conceptos Fundamentales, 3ª Edición.

- 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

- Exclusión mutua (informática) (3 de mayo de 2008). Extraído el 24 de octubre de 2008 desde http://es.wikipedia.org/wiki/Exclusi%C3%B3n_mutua_%28inform%C3%A1tica%29

- HILOS (THREAD) (n.d.). Extraído el 24 de octubre de 2008 desde http://xue.unalmed.edu.co/~gsanchez/downloads/hilos.pdf

- Introducción a los sistemas operativos. Capitulo 4. Concurrencia: Exclusión mutua y sincronización (n.d). Extraido el 24 de octubre de 2008 desde http://www.hackinc2000.com/sistemasoperativos/Content/Cap04.html

- Instituto tecnológico de Celaya, Sistemas operativos unidad III, (n.d.). Extraído el 24 de octubre de 2008 desde http://sisinfo.itc.mx/ITC-APIRGG/Materias/Mat1/SistOp-I_Unid3.php#

- Monitores (Concurrencia) (30 de septiembre de 2008). Extraído el 24 de octubre de 2008 desde http://es.wikipedia.org/wiki/Monitor_(concurrencia)

- 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

- Sistemas operativos. (n.d.) Extraído el 24 de octubre de 2008 desde http://www.mitecnologico.com/Main/SistemasOperativos

- 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

- Universidad nacional del nordeste facultad de ciencias exactas y naturales y agrimensura. Magister David Ruiz de la Red Martinez. Sistemas operativos, Principios del interbloqueo. (Noviembre de 2001). Extraído el 24 de octubre de 2008 desde http://exa.unne.edu.ar/depar/areas/informatica/SistemasOperativos/MonogSO/CINTIN02.htm

2.6.5 Multi-Level Feedback Queves

En colas multinivel realimentadas los trabajos pueden moverse dentro de distintas colas. La idea es separar procesos con distintos tipos de interrupciones de la CPU. Si un trabajo consume mucho tiempo de CPU, será movido a una cola con menor prioridad.

En forma similar, si un proceso espera demasiado tiempo en una cola de baja prioridad, lo moveremos a una cola de mayor prioridad.

En general un planificador de este tipo esta definido por los siguientes parámetros:

1. El número de colas.

2. El tipo de algoritmo de planificación de cada cola.

3. Un método de determinación de cuando mover un trabajo a una cola de mayor prioridad.

4. Un método de determinación de cuando mover un trabajo a una cola de menor prioridad.

5. Un método de determinación de a qué cola se enviará un trabajo cuando necesita servicio. [15-E]
_________________________
[15-E] Sistemas operativos. (n.d.) Extraído el 24 de octubre de 2008 desde http://www.mitecnologico.com/Main/SistemasOperativos

2.6.4 Queves Multi-level

Un algoritmo de planificación multinivel particiona la cola de listos en colas separadas. Se asignan en forma permanente los trabajos a una cola, generalmente, basándose en alguna propiedad del mismo (requerimientos de memoria, tipo de trabajo), teniendo cada cola su propio algoritmo. Por ejemplo, la cola interactiva podría planificarse usando RR y la batch FIFO.

Ningún trabajo en una cola de baja prioridad puede ejecutarse si las colas con mayor prioridad no están vacías. Si algún trabajo entra en una cola de mayor prioridad, el trabajo de otras colas es interrumpido. [15-D]

________________________
[15-D] Sistemas operativos. (n.d.) Extraído el 24 de octubre de 2008 desde http://www.mitecnologico.com/Main/SistemasOperativos


2.6.3 RR

Cada proceso tiene asignado un intervalo de tiempo de ejecución, llamado cuantum o cuanto. Si el proceso agota su cuantum de tiempo, se elige a otro proceso para ocupar la CPU. Si el proceso se bloquea o termina antes de agotar su cuantum también se alterna el uso de la CPU.

El round robin es muy fácil de implementar. Todo lo que necesita el planificador es mantener una lista de los procesos listos. [15-C]
_______________________
[15-C] Sistemas operativos. (n.d.) Extraído el 24 de octubre de 2008 desde http://www.mitecnologico.com/Main/SistemasOperativos

2.6.2 SJF

Al igual que en el algoritmo FIFO las ráfagas se ejecutan sin interrupción, por tanto, sólo es útil para entornos batch. Su característica es que cuando se activa el planificador, éste elige la ráfaga de menor duración. Es decir, introduce una noción de prioridad entre ráfagas.

Hay que recordar que en los entornos batch se pueden hacer estimaciones del tiempo de ejecución de los procesos. La ventaja que presenta este algoritmo sobre el algoritmo FIFO es que minimiza el tiempo de finalización promedio, como puede verse en el siguiente ejemplo:

Supongamos que en un momento dado existen tres ráfagas listos R1, R2 y R3, sus tiempos de ejecución respectivos son 24, 3 y 3 ms. El proceso al que pertenece la ráfaga R1 es la que lleva más tiempo ejecutable, seguido del proceso al que pertenece R2 y del de R3.

• FIFO F = (24 + 27 + 30) / 3 = 27 ms.
• SJF F = (3 + 6 + 30) / 3 = 13 ms. [15-B]
_________________________
[15-B] Sistemas operativos. (n.d.) Extraído el 24 de octubre de 2008 desde http://www.mitecnologico.com/Main/SistemasOperativos

2.6.1. FIFO


FIFO: First In First Out

Mecanismo de scheduling en el cual los procesos se ordenan en una fila, en la cual se ejecutan cada uno de los procesos hasta su finalización secuencialmente. Es tremendamente ineficiente.

Cuando se tiene que elegir a qué proceso asignar la CPU se escoge al que llevara más tiempo listo. El proceso se mantiene en la CPU hasta que se bloquea voluntariamente.

Para implementar el algoritmo sólo se necesita mantener una cola con los procesos listos ordenada por tiempo de llegada. Cuando un proceso pasa de bloqueado a listo se sitúa el último de la cola.

FIFO

FIFO es el acrónimo inglés de First In, First Out (primero en entrar, primero en salir). Un sinónimo de FIFO es FCFS, acrónimo inglés de First Come First Served ( primero en llegar, primero en ser servido). Es un método utilizado en estructuras de datos, contabilidad de costes y teoría de colas. Guarda analogía con las personas que esperan en una cola y van siendo atendidas en el orden en que llegaron, es decir, que la primera persona que entra es la primera persona que sale.
Esquema de funcionamiento de una cola FIFO.FIFO se utiliza en estructuras de datos para implementar colas. La implementación puede efectuarse con ayuda de arrays o vectores, o bien mediante el uso de punteros y asignación dinámica de memoria.

Si se implementa mediante vectores el número máximo de elementos que puede almacenar está limitado al que se haya establecido en el código del programa antes de la compilación (cola estática) o durante su ejecución (cola pseudoestática). Sea cual sea la opción elegida, el número de elementos que podrá almacenar la cola quedará determinado durante toda la ejecución del programa.

El sistema debe reservar el tamaño de memoria necesario para acoger todos los datos, sea cual sea el número de elementos usados, lo que en algunas aplicaciones supone un despilfarro de la memoria. Sin embargo, si se usan punteros, el número máximo no está declarado sino que se hace un uso dinámico de la memoria, adaptándose al tamaño necesario en cada momento en función de los elementos que hay en la cola. Uno de los usos de las colas es la exploración “en anchura” de un árbol de búsqueda. Otro uso típico de las colas, es la gestión de descargas de una aplicación p2p.

Los FIFOs se usan comúnmente en circuitos de electrónica para almacenaje y hacer control de flujo. Hablando de hardware form un FIFO consiste básicamente en una conjunto de punteros de lectura/escritura, almacenamiento y lógica de control. El almacenamiento puede ser SRAM, flip-flops, latches o cualquier otra forma adecuada de almacenamiento. Para FIFOs de un tamaño importante se usa usualmente una SRAM de doble puerto, donde uno de los puertos se usa para la escritura y el otro par a la lectura.

Un FIFO sincrónico maneja el mismo reloj (clock) tanto para las lecturas como para las escrituras. Una asicrónico es aquel que utiliza diferentes relojes (clocks) una para lectura y otro para la escritura. Cuando se habla de FIFOs asincrónicos se introduce el tema de la meta-estabilidad. Una implementación común de un FIFO asincrónico usa un Gray code ( o cualquier código de unidad de distancia) para los punteros de lectura y escritura de modo de asegurarse una generación de banderas (flags) segura/estable. Otra nota adicional respecto de la generación de banderas es que uno debe necesariamente usar punteros aritméticos para generar banderas para implementaciones asincrónicas de FIFO. Por otro lado, uno puede usar tanto un acercamiento “leaky bucket” o punteros aritméticos para generar banderas en una implementación FIFO sincrónica.

Como ejemplo de banderas de estado FIFO, se pueden enumerar: full (lleno), empty (vacio), almost full (casi lleno) o almost empty (casi vacio).

FIFO FULL (LLENO)/EMPTY (VACIO) [editar]En el hardware FIFO se usa para propósitos de sincronización. Comportándose como una cola circular . Tiene dos punteros:

1. Puntero de Lectura/Registro de Dirección de Lectura
2. Puntero de Escritura/Registro de Dirección de Escritura

Las direcciones de lectura y escritura están ambas inicialmente en la primer ubicación de la memoria y la cola FIFO está Vacía.

FIFO Vacía: Cuando registro de dirección de lectura alcanza al registro de dirección de escritura, la cola FIFO dispara la señal Vacio.

FIFO Llena: Cuando el registro de dirección de escritura alcanza al registro de dirección de lectura, la cola FIFO dispara la señal LLENO. [15-A]

_____________________________
[15-A] Sistemas operativos. (n.d.) Extraído el 24 de octubre de 2008 desde http://www.mitecnologico.com/Main/SistemasOperativos


2.6 TÉCNICAS DE ADMINISTRACIÓN DEL PLANIFICADOR

Las disciplinas de planificación pueden ser:

• Expropiativas
• No expropiativas

Se denomina planificador al software del sistema operativo encargado de asignar los recursos de un sistema entre los procesos que los solicitan. Siempre que haya tomar una decisión, el planificador debe decidir cuál de los procesos que compiten por la posesión de un determinado recursos lo recibirá.

Los algoritmos (técnicas) tienen distintas propiedades según los criterios en los que se basen para su construcción, lo cual se refleja en qué tipo de procesos se puede ver favorecido frente a otro en la disputa del procesador. Antes de realizar la elección de un algoritmo se debe considerar las propiedades de estos frente al criterio de diseño elegido. Algunos de estos son:

a) Eficacia: Se expresa como un porcentaje del tiempo medio de utilización. Aunque puede parecer lógico intentar mantener este parámetro próximo al 100%, con un valor tan elevado otros aspectos importante de medida del comportamiento del sistema pueden verse deteriorados, como por ejemplo el tiempo medio de espera.

b) Rendimiento: Es una medida del numero de procesos completados por unidad de tiempo. Por ejemplo 10 procesos por segundo.

c) Tiempo de retorno o regreso: Es el intervalo de tiempo que transcurre desde que un proceso se crea o presenta hasta que completa por el sistema.

d) Tiempo de espera: Es el tiempo que el proceso espera hasta que se le concede el procesador. Puede resultar una medida mas adecuada de la eficiencia del sistema, ya que se elimina de la media el tiempo que tarda en ejecutarse el mismo.

e) Tiempo de respuesta a un evento: Se denomina así el intervalo de tiempo que transcurre desde que se señala un evento hasta que se ejecuta la primera instrucción de la rutina de servicio de dicho evento. El criterio de selección de un algoritmo se suele basar en la maximización o minimización de una función de los parámetros anteriores. [15]
____________________________
[15] Sistemas operativos. (n.d.) Extraído el 24 de octubre de 2008 desde http://www.mitecnologico.com/Main/SistemasOperativos

2.5 NIVELES, OBJETIVOS Y CRITERIOS DE PLANIFICACIÓN

NIVELES DE PLANIFICACIÓN
.
La planificación es el proceso por el cual el sistema operativo selecciona que proceso ejecutar. La selección del proceso se basa en alguno de los algoritmos de planificación.

La planificación de la CPU, en el sentido de conmutarla entre los distintos procesos, es una de las funciones del sistema operativo. Este despacho es llevado a cabo por un pequeño programa llamado planificador a corto plazo o dispatcher (despachador). La misión del dispatcher consiste en asignar la CPU a uno de los procesos ejecutables del sistema, para ello sigue un determinado algoritmo.

Los acontecimientos que pueden provocar la llamada al dispatcher dependen del sistema (son un subconjunto de las interrupciones), pero son alguno de estos:

  • El proceso en ejecución acaba su ejecución o no puede seguir ejecutándose (por una E/S, operación WAIT, etc).
  • Un elemento del sistema operativo ordena el bloqueo del proceso en ejecución
    El proceso en ejecución agota su cuantum o cuanto de estancia en la CPU.
  • Un proceso pasa a estado listo.
Hay que destacar el hecho de que cuanto menos se llame al dispatcher menos tiempo ocupa la CPU un programa del sistema operativo, y, por tanto, se dedica más tiempo a los procesos del usuario (un cambio de proceso lleva bastante tiempo).
.
Así, si sólo se activa el dispatcher como consecuencia de los 2 primeros acontecimientos se estará haciendo un buen uso del procesador. Este criterio es acertado en sistemas por lotes en los que los programas no son interactivos. Sin embargo, en un sistema de tiempo compartido no es adecuado, pues un proceso que se dedicara a realizar cálculos, y no realizara E/S, monopolizaría el uso de la CPU. En estos sistemas hay que tener en cuenta el conjunto de todos los procesos, activándose el dispatcher con la circunstancia tercera y, posiblemente, la cuarta. Los sistema operativos en que las dos siguientes circunstancias no provocan la activación del dispatcher muestran preferencia por el proceso en ejecución, si no ocurre esto se tiene más en cuenta el conjunto de todos los procesos.

Se puede definir el scheduling -algunas veces traducido como -planificación- como el conjunto de políticas y mecanismos construidos dentro del sistema operativo que gobiernan la forma de conseguir que los procesos a ejecutar lleguen a ejecutarse.

El scheduling está asociado a las cuestiones de:
  • Cuándo introducir un nuevo proceso en el Sistema.
  • Determinar el orden de ejecución de los procesos del sistema.

El scheduling está muy relacionado con la gestión de los recursos. Existen tres niveles de scheduling, estos niveles son:

  • Planificador de la CPU o a corto plazo.
  • Planificador a medio plazo.
  • Planificador a largo plazo.

En la planificación de procesos se suelen incluir varios niveles, en función del periodo temporal que cubren:


- PLANIFICACIÓN A LARGO PLAZO

Este planificador está presente en algunos sistemas que admiten además de procesos interactivos trabajos por lotes. Usualmente, se les asigna una prioridad baja a los trabajos por lotes, utilizándose estos para mantener ocupados a los recursos del sistema durante períodos de baja actividad de los procesos interactivos. Normalmente, los trabajos por lotes realizan tareas rutinarias como el cálculo de nóminas; en este tipo de tareas el programador puede estimar su gasto en recursos, indicándoselo al sistema. Esto facilita el funcionamiento del planificador a largo plazo.

El objetivo primordial del planificador a largo plazo es el de dar al planificador de la CPU una mezcla equilibrada de trabajos, tales como los limitados por la CPU (utilizan mucho la CPU) o la E/S. Así, por ejemplo, cuando la utilización de la CPU es baja, el planificador puede admitir más trabajos para aumentar el número de procesos listos y, con ello, la probabilidad de tener algún trabajo útil en espera de que se le asigne la CPU. A la inversa, cuando la utilización de la CPU llega a ser alta, y el tiempo de respuesta comienza a reflejarlo, el planificador a largo plazo puede optar por reducir la frecuencia de admisión de trabajos.

Normalmente, se invoca al planificador a largo plazo siempre que un proceso termina. La frecuencia de invocación depende, pues, de la carga del sistema, pero generalmente es mucho menor que la de los otros dos planificadores. Esta baja frecuencia de uso hace que este planificador pueda permitirse utilizar algoritmos complejos, basados en las estimaciones de los nuevos trabajos.

- PLANIFICACIÓN A MEDIANO PLAZO

En los sistemas de multiprogramación y tiempo compartido varios procesos residen en la memoria principal. El tamaño limitado de ésta hace que el número de procesos que residen en ella sea finito. Puede ocurrir que todos los procesos en memoria estén bloqueados, desperdiciándose así la CPU. En algunos sistemas se intercambian procesos enteros (swap) entre memoria principal y memoria secundaria (normalmente discos), con esto se aumenta el número de procesos, y, por tanto, la probabilidad de una mayor utilización de la CPU.

El planificador a medio plazo es el encargado de regir las transiciones de procesos entre memoria principal y secundaria, actúa intentando maximizar la utilización de los recursos. Por ejemplo, transfiriendo siempre a memoria secundaria procesos bloqueados, o transfiriendo a memoria principal procesos bloqueados únicamente por no tener memoria.

- PLANIFICACIÓN A CORTO PLAZO

Qué proceso será el que se ejecutará en el procesador en el instante siguiente.

Expulsión denota si un proceso acapara el procesador cuando está ejecutándose. Existen sistemas con y sin expulsión:

a) Sin expulsión: un proceso conserva el uso del procesador mientras lo desee; es decir, mientras no solicite del SO un servicio que lo bloquee. Ventajas: minimiza tiempo de planificación. Inconvenientes: un proceso podría monopolizar el uso del procesador.

b) Con expulsión: el SO puede desalojar a un proceso del uso del procesador (sin que el proceso lo haya solicitado). Ventaja: control sobre el tiempo de ejecución de cada proceso. Inconveniente: gasto de tiempo.

OBJETIVOS Y CRITERIOS DE PLANIFICACIÓN

Los objetivos del planificador se resumen en:

a) Reparto equitativo del tiempo de procesador
b) Eficiencia en el uso del procesador
c) Menor tiempo de respuesta en uso interactivo
d) Cumplir plazos de ejecución de los sistemas de tiempo real

El principal objetivo de la planificación a corto plazo es repartir el tiempo del procesador de forma que se optimicen algunos puntos del comportamiento del sistema. Generalmente se fija un conjunto de criterios con los que evaluar las diversas estrategias de planificación. El criterio más empleado establece dos clasificaciones. En primer lugar, se puede hacer una distinción entre los criterios orientados a los usuarios y los orientados al sistema. Los criterios orientados al usuario se refieren al comportamiento del sistema tal y como lo perciben los usuarios o los procesos.

Uno de los parámetros es el tiempo de respuesta. El tiempo de respuesta es el periodo de tiempo transcurrido desde que se emite una solicitud hasta que la respuesta aparece en la salida. Sería conveniente disponer de una política de planificación que ofrezca un buen servicio a diversos usuarios.

Otros criterios están orientados al sistema, esto es, se centran en el uso efectivo y eficiente del procesador. Un ejemplo puede ser la productividad, es decir, el ritmo con el que los procesos terminan. La productividad es una medida muy válida del rendimiento de un sistema y que sería deseable maximizar.

Otra forma de clasificación es considerar los criterios relativos al rendimiento del sistema y los que no lo son. Los criterios relativos al rendimiento son cuantitativos y, en general, pueden evaluarse o ser analizados fácilmente. Algunos ejemplos son el tiempo de respuesta y la productividad.

Los criterios no relativos al rendimiento son, en cambio cualitativos y no pueden ser evaluados fácilmente. Un ejemplo de estos criterios es la previsibilidad. Sería conveniente que el servicio ofrecido a los usuarios tenga las mismas características en todo momento, independientemente de la existencia de otros trabajos ejecutados por el sistema.

En particular, una disciplina de planificación debe:

Ser equitativa: debe intentar hacer una planificación justa, esto es, se debe tratar a todos los procesos de la misma forma y no aplazar indefinidamente ningún proceso. La mejor forma de evitarlo es emplear alguna técnica de envejecimiento; es decir, mientras un proceso espera un recurso, su prioridad debe crecer.

Ser eficiente: debe maximizar el uso de los recursos tales como intentar que la ocupación de la CPU sea máxima. Al mismo tiempo se debe intentar reducir el gasto extra por considerar que es trabajo no productivo. Normalmente el idear algoritmos eficientes supone invertir recursos en gestión del propio sistema.

Lograr un tiempo bueno de respuesta, es decir, que los usuarios interactivos reciban respuesta en tiempos aceptables.

Lograr un tiempo de proceso global predecible. Esto quiere decir que un proceso debe ejecutarse aproximadamente en el mismo tiempo y casi al mismo costo con independencia de la carga del sistema.

Elevar al máximo la productividad o el rendimiento, esto es, maximizar el número de trabajos procesados por unidad de tiempo. Eso supone, por un lado, dar preferencia a los procesos que ocupan recursos decisivos y, por otro, favorecer a los procesos que muestran un comportamiento deseable. En el primer caso conseguimos liberar el recurso cuanto antes para que esté disponible para un proceso de mayor prioridad. Con el segundo criterio escogemos a los procesos que no consumen muchos recursos dejándole al sistema mayor capacidad de actuación.

Estos criterios son dependientes entre sí y es imposible optimizar todos de forma simultánea. Por ejemplo, obtener un buen tiempo de respuesta puede exigir un algoritmo de planificación que alterne entre los procesos con frecuencia, lo que incrementa la sobrecarga del sistema y reduce la productividad. Por tanto, en el diseño de una política de planificación entran en juego compromisos entre requisitos opuestos; el peso relativo que reciben los distintos requisitos dependerá de la naturaleza y empleo del sistema.[14]

_______________________________
[14] Deitel, H. M. (1993) Sistemas Operativos, 2ª Edición, Addison-Wesley.
Milenkovic M. (1994). Sistemas Operativos. Conceptos y Diseño, 2ª Edición, McGraw-Hill.
Silberschatz, A., Peterson, J., Galvin, P. (1994) Sistemas Operativos. Conceptos Fundamentales, 3ª Edición.

Stallings, W. (1993).Computer Organization and Architecture,3ª Edición. New York: Macmillan.

2.4.3.3.- RECUPERACIÓN DE INTERBLOQUEO

Cuando se ha detectado que existe un interbloqueo, podemos actuar de varias formas. Una posibilidad es informar al operador que ha ocurrido un interbloqueo y dejar que el operador se ocupe de él manualmente. La otra posibilidad es dejar que el sistema se recupere automáticamente del interbloqueo. Dentro de esta recuperación automática tenemos dos opciones para romper el interbloqueo: Una consiste en abortar uno o más procesos hasta romper la espera circular, y la segunda es apropiar algunos recursos de uno o más de los procesos bloqueados.

La recuperación después de un interbloqueo se complica porque puede no estar claro que el sistema se haya bloqueado. Las mayorías de los Sistemas Operativos no tienen los medios suficientes para suspender un proceso, eliminarlo del sistema y reanudarlo más tarde.

Actualmente, la recuperación se suele realizar eliminando un proceso y quitándole sus recursos. El proceso eliminado se pierde, pero gracias a esto ahora es posible terminar. Algunas veces es necesario, eliminar varios procesos hasta que se hayan liberado los recursos necesarios para que terminen los procesos restantes.

Los procesos pueden eliminarse de acuerdo con algún orden de prioridad, aunque es posible que no existan prioridades entre los procesos bloqueados, de modo que el operador necesita tomar una decisión arbitraria para decidir que procesos se eliminarán.

RECUPERACIÓN MANUAL

Está forma de recuperación consiste en avisarle al administrador o al operador del sistema que se ha presentado un interbloqueo, y será el administrador el que solucione dicho problema de la manera más conveniente posible, de modo que su decisión no afecte demasiado a al usuario del proceso en conflicto, y sobre todo que no afecte a los demás usuarios del sistema.

ABORTAR LOS PROCESOS

Para eliminar interbloqueos abortando un proceso, tenemos dos métodos; en ambos, el sistema recupera todos los recursos asignados a los procesos terminados.

1) Abortar todos los procesos interbloqueados. Esta es una de las soluciones más comunes, adoptada por Sistemas Operativos. Este método romperá definitivamente el ciclo de interbloqueo pero con un costo muy elevado, ya que estos procesos efectuaron cálculos durante mucho tiempo y habrá que descartar los resultados de estos cálculos parciales, para quizá tener que volver a calcularlos más tarde.

2) Abortar un proceso en cada ocasión hasta eliminar el ciclo de interbloqueo. El orden en que se seleccionan los procesos para abortarlos debe basarse en algún criterio de costo mínimo. Después de cada aborto, debe solicitarse de nuevo el algoritmo de detección, para ver si todavía existe el interbloqueo. Este método cae en mucho tiempo de procesamiento adicional.

Quizá no sea fácil abortar un proceso. Si éste se encuentra actualizando un archivo, cortarlo a la mitad de la operación puede ocasionar que el archivo quede en un mal estado.

Si se utiliza el método de terminación parcial, entonces, dado un conjunto de procesos bloqueados, debemos determinar cuál proceso o procesos debe terminarse para intentar romper el interbloqueo. Se trata sobre todo de una cuestión económica, debemos abortar los procesos que nos representen el menor costo posible. Existen muchos factores que determinan el proceso que se seleccionará, siendo los principales los siguientes:
  • La prioridad del proceso. Se elimina el proceso de menor prioridad.
  • Tiempo de procesador usado. Se abortará aquel proceso que haya utilizado menos tiempo el procesador, ya que se pierde menos trabajo y será más fácil recuperarlo más tarde.
  • Tipos de recursos utilizados. Si los recursos son muy necesarios y escasos será preferible liberarlos cuanto antes.
  • Cuántos recursos más necesita el proceso. Es conveniente eliminar a aquellos procesos que necesitan un gran número de recursos.
  • Facilidad de suspensión / reanudación. Se eliminarán aquellos procesos cuyo trabajo perdido sea más fácil de recuperar.

APROPIACIÓN DE RECURSOS

Para eliminar interbloqueos utilizando la apropiación de recursos, vamos quitando sucesivamente recursos de los procesos y los asignamos a otros hasta romper el ciclo de interbloqueo.

Si se utiliza la apropiación de recursos para tratar los interbloqueos, hay que considerar tres aspectos:

- Selección de la víctima
- Retroceso
- Bloqueo indefinido

La detección y recuperación es la estrategia que a menudo se utiliza en grandes computadoras, especialmente sistemas por lote en los que la eliminación de un proceso y después su reiniciación suele aceptarse.[13-C]

______________________________
[13-C] Universidad nacional del nordeste facultad de ciencias exactas y naturales y agrimensura. Magíster David Ruiz de la Red Martínez. Sistemas operativos, Principios del interbloqueo. (Noviembre de 2001). Extraído el 24 de octubre de 2008 desde http://exa.unne.edu.ar/depar/areas/informatica/SistemasOperativos/MonogSO/CINTIN02.htm


2.4.3-2.- DETECCIÓN DEL INTERBLOQUEO

Las estrategias de prevención de interbloqueo son muy conservadoras; resuelven el problema limitando el acceso a recursos e imponiendo restricciones sobre los procesos. En cambio, las estrategias de detección de interbloqueo, no limitan el acceso a recursos ni restringen las acciones del proceso. Con la detección del interbloqueo, se concederán los recursos que los procesos necesiten siempre que sea posible. Periódicamente, el S. O. ejecuta un algoritmo que permite detectar la condición de circulo vicioso de espera.

La detección del interbloqueo es el proceso de determinar si realmente existe un interbloqueo e identificar los procesos y recursos implicados en él. Una posibilidad detectar un interbloqueo es monitorear cada cierto tiempo el estado de los recursos. Cada vez que se solicita o se devuelve un recurso, se actualiza el estado de los recursos y se hace una verificación para observar si existe algún ciclo.

Este método está basado en suponer que un interbloqueo no se presente y que los recursos del sistema que han sido asignados, se liberarán en el momento que otro proceso lo requiera.

ALGORITMO DE DETECCIÓN DE INTERBLOQUEO

Una comprobación para interbloqueo puede hacerse con igual o menor frecuencia que cada solicitud de recursos, dependiendo de qué tan probable es que ocurra un interbloqueo. Comprobar cada solicitud de recursos tiene dos ventajas: Conduce a la detección temprana y el algoritmo es simple, de manera relativa porque se basa en cambios crecientes al estado del sistema. Además, las comprobaciones frecuentes consumen un tiempo considerable de procesador.

Los algoritmos de detección de bloqueos implican cierta sobrecarga en tiempo de ejecución:

El empleo de algoritmos de detección de interbloqueo implica cierto gasto extra durante la ejecución. Así pues, se presenta de nuevo la cuestión de coste-habilidad, tan habitual en los sistemas operativos. Los algoritmos de detección de interbloqueo determinan por lo general si existe una espera circular.[13-B]
________________________________
[13-B] Universidad nacional del nordeste facultad de ciencias exactas y naturales y agrimensura. Magíster David Ruiz de la Red Martínez. Sistemas operativos, Principios del interbloqueo. (Noviembre de 2001). Extraído el 24 de octubre de 2008 desde http://exa.unne.edu.ar/depar/areas/informatica/SistemasOperativos/MonogSO/CINTIN02.htm

2.4.3.1.-PREVENCION DE UN INTERBLOQUEO

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.[13-A]
_______________________
[13-A] Universidad nacional del nordeste facultad de ciencias exactas y naturales y agrimensura. Magíster David Ruiz de la Red Martínez. Sistemas operativos, Principios del interbloqueo. (Noviembre de 2001). Extraído el 24 de octubre de 2008 desde http://exa.unne.edu.ar/depar/areas/informatica/SistemasOperativos/MonogSO/CINTIN02.htm

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.



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.[13]

______________________________
[13] Universidad nacional del nordeste facultad de ciencias exactas y naturales y agrimensura. Magíster David Ruiz de la Red Martínez. Sistemas operativos, Principios del interbloqueo. (Noviembre de 2001). Extraído el 24 de octubre de 2008 desde http://exa.unne.edu.ar/depar/areas/informatica/SistemasOperativos/MonogSO/CINTIN02.htm

sábado, 25 de octubre de 2008

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.
.
CARACTERISTICAS
.
• 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.*;[12]
_______________________________
[12] 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.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.



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.[11]
___________________
[11] 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 SINCRONIZACIÓN DE PROCESOS EN S.C.

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.
[8]
.
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.[9]
.
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.[10]
___________________________
[8] 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
.
[9] 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
.
[10] 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

2.4.1 EXCLUSIÓN MUTUA DE SECCIONES CRÍTICAS.

El método más sencillo de comunicación entre los procesos de un programa concurrente es el uso común de unas variables de datos. El problema de este sistema es que la acción de un proceso interfiere en las acciones de otro de una forma no adecuada. Para evitar este tipo de errores se pueden identificar aquellas regiones de los procesos que acceden a variables compartidas y dotarlas de la posibilidad de ejecución como si fueran una única instrucción. Se denomina sección crítica a aquellas partes de los procesos concurrentes que no pueden ejecutarse de forma concurrente o, que desde otro proceso se ven como si fueran una única instrucción. Esto quiere decir que si un proceso entra a ejecutar una sección crítica en la que accede a unas variables compartidas, entonces otro proceso no puede entrar a ejecutar una región crítica en la que se modifique las variables compartidas con el anterior. Las secciones críticas se pueden agrupar en clases, siendo mutuamente exclusivas las secciones críticas de cada una. Para conseguir dicha exclusión se deben implementar protocolos software que impidan o bloqueen el acceso a una sección crítica mientras está siendo utilizada por un proceso.[5]
.
Los algoritmos de exclusión mutua (comúnmente abreviada como mutex por mutual exclusion) se usan en programación concurrente para evitar que fragmentos de código conocidos como secciones críticas accedan al mismo tiempo a recursos que no deben ser compartidos.

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

La técnica que se emplea por lo común para conseguir la exclusión mutua es inhabilitar las interrupciones durante el conjunto de instrucciones más pequeño que impedirá la corrupción de la estructura compartida (la sección crítica). Esto impide que el código de la interrupción se ejecute en mitad de la sección crítica.

En un sistema multiprocesador de memoria compartida, se usa la operación indivisible test-and-set sobre una bandera, para esperar hasta que el otro procesador la despeje. La operación test-and-set realiza ambas operaciones sin liberar el bus de memoria a otro procesador. Así, cuando el código deja la sección crítica, se despeja la bandera. Esto se conoce como espera activa.
Algunos sistemas tienen instrucciones multioperación indivisibles similares a las anteriormente descritas para manipular las listas enlazadas que se utilizan para las colas de eventos y otras estructuras de datos que los sistemas operativos usan comúnmente.

La mayoría de los métodos de exclusión mutua clásicos intentan reducir la latencia y espera activa mediante las colas y cambios de contexto. Algunos investigadores afirman que las pruebas indican que estos algoritmos especiales pierden más tiempo del que ahorran.
.
A pesar de todo lo dicho, muchas técnicas de exclusión mutua tienen efectos colaterales. Por ejemplo, los semáforos permiten interbloqueos (deadlocks) en los que un proceso obtiene un semáforo, otro proceso obtiene el semáforo y ambos se quedan a la espera de que el otro proceso libere el semáforo. Otros efectos comunes incluyen la inanición, en el cual un proceso esencial no se ejecuta durante el tiempo deseado, y la inversión de prioridades, en el que una tarea de prioridad elevada espera por otra tarea de menor prioridad, así como la latencia alta en la que la respuesta a las interrupciones no es inmediata.
.
La mayor parte de la investigación actual en este campo, pretende eliminar los efectos anteriormente descritos. Si bien no hay un esquema perfecto conocido, hay un interesante esquema no clásico de envío de mensajes entre fragmentos de código que, aunque permite inversiones de prioridad y produce una mayor latencia, impide los interbloqueos.
.
Algunos ejemplos de algoritmos clásicos de exclusión mutua son:
  • El algoritmo de Dekker.
  • El algoritmo de Peterson. [6]

REGIÓN CRITICA. PROTOCOLO DE SINCRONIZACIÓN

Los puntos de entrada de un recurso indican la cantidad de procesos que pueden utilizar simultáneamente al mismo. Si un recurso tiene sólo un punto de entrada, se lo denomina recurso crítico o recurso no compartible.

Región crítica de un proceso es la fase o etapa en la vida de ese proceso concurrente en la cual accede a un recurso crítico para modificarlo o alterarlo. El uso adecuado de la concurrencia entre procesos exige la capacidad de definir secciones críticas y hacer cumplir la exclusión mutua. Cualquier servicio o capacidad que dé soporte para la exclusión mutua debe cumplir con un protocolo de sincronización, que tiene los requisitos siguientes:

1. Debe cumplirse la exclusión mutua: sólo 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. Es decir que si se cuelga un proceso que está usando un recurso, los demás procesos que esperan deben poder acceder al recurso de todas formas (el S.O. mata al proceso que se colgó y así libera al recurso).

3. No se puede demorar indefinidamente la entrada de un proceso a un cierto recurso; no debe permitirse el interbloqueo y la inanición. Todos los procesos deben poder acceder al recurso que solicitan, sino se van a morir sin usarlo y no es justo.

4. Cuando ningún proceso está en su sección crítica, cualquier proceso que solicite entrar en la suya debe poder hacerlo sin dilatación. Es decir, si nadie está usando un cierto recurso, entonces se le otorga al primer proceso que lo solicite.

5. No se pueden hacer suposiciones sobre la velocidad relativa de los procesos o su número (cantidad de procesadores). Nunca se puede saber a priori si a un proceso le falta mucho o poco para terminar.

6. Un proceso permanece en su sección crítica sólo por un tiempo finito. Esto sirve para evitar que un proceso se quede con un recurso por mucho tiempo y para que un recurso no se quede trabado sin sentido.
[7]

_________________________
[5] 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
.
[6] Exclusión mutua (informática) (3 de mayo de 2008). Extraído el 24 de octubre de 2008 desde http://es.wikipedia.org/wiki/Exclusi%C3%B3n_mutua_%28inform%C3%A1tica%29
.
[7] Introducción a los sistemas operativos. Capitulo 4. Concurrencia: Exclusión mutua y sincronización (n.d). Extraído el 24 de octubre de 2008 desde http://www.hackinc2000.com/sistemasoperativos/Content/Cap04.html

2.4 CONCURRENCIA Y SECUENCIABILIDAD.

La concurrencia comprende un gran número de cuestiones de diseño, incluyendo la comunicación entre procesos, comparició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 y es fundamental para que existan diseños como Multiprogramación, Multiproceso y Proceso distribuido

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.

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.


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.
.
Multiprocesador. Es una maquina formada por un conjunto de procesadores que comparten memoria principal. En este tipo de arquitecturas, los procesos concurrentes no sólo pueden intercalar su ejecución sino también superponerla.• Multicomputadora. Es una maquina de memoria distribuida, que está formada por una serie de computadoras. En este tipo de arquitecturas también es posible la ejecución simultánea de los procesos sobre los diferentes procesadores.
En general, la concurrencia será aparente siempre que el número de procesos sea mayor que el de procesadores disponibles, es decir, cuando haya más de un proceso por procesador. La concurrencia será real cuando haya un proceso por procesador. Aunque puede parecer que la intercalación y la superposición de la ejecución de procesos presentan formas de ejecución distintas, se verá que ambas pueden contemplase como ejemplos de procesos concurrentes.

Existen diversas razones que motivan la ejecución de procesos concurrentes en un sistema:
.
• Acelera los cálculos. Si se quiere que una tarea se ejecute con mayor rapidez, lo que se puede hacer es dividirla en procesos, cada uno de los cuales se ejecuta en paralelo con los demás.

• Posibilita el uso interactivo a múltiples usuarios que trabajan de forma simultánea.
.
• Permite un mejor aprovechamiento de los recursos, en especial de la CPU, ya que pueden aprovechar las fases de entrada-salida de unos procesos para realizar las fases de procesamiento de otros.

Así como existen las razones que motivan la ejecución de procesos concurrentes, también existen sus contras:

• Inanición e interrupción de procesos
• Ocurrencia de bloqueos
• Que dos o más procesos requieran el mismo recurso (No apropiativo).
.
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 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. Entre estos recursos se incluyen:

• Tiempo de procesador: Es función de la planificación.
• 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 relativa a la que se realiza la ejecución con respecto a otros procesos concurrentes.[4]
_____________________________
[4] Instituto tecnológico de Celaya, Sistemas operativos unidad III, (n.d.). Extraído el 24 de octubre de 2008 desde: