Sistemas operativos: octubre 2017

domingo, 1 de octubre de 2017

2.6 Técnicas de administración del planificador

En los siguientes subapartados vamos a estudiar ciertos algoritmos utilizados para planificar la CPU, la elección de uno (o de una mezcla de varios) depende de decisiones de diseño. Antes de exponer los algoritmos vamos a explicar ciertas medidas que se utilizan para evaluarlos.

Porcentaje de utilización de la CPU por procesos de usuario. La CPU es un recurso caro que necesita ser explotado, los valores reales suelen estar entre un 40% y un 90%.

Rendimiento (throughput) = nº de ráfagas por unidad de tiempo. Se define una ráfaga como el período de tiempo en que un proceso necesita la CPU; un proceso, durante su vida, alterna ráfagas con bloqueos. Por extensión, también se define como el nº de trabajos por unidad de tiempo.

Tiempo de espera (E) = tiempo que una ráfaga ha permanecido en estado listo.

Tiempo de finalización (F) = tiempo transcurrido desde que una ráfaga comienza a existir hasta que finaliza. F = E + t (t = tiempo de CPU de la ráfaga).

Penalización (P) = E + t / t = F / t, es una medida adimensional que se puede aplicar homogéneamente a las ráfagas independientemente de su longitud.

En general, hay que maximizar los dos primeros parámetros y minimizar los tres últimos. Sin embargo, estos objetivos son contradictorios, el dedicar más tiempo de CPU a los usuarios se hace a costa de llamar menos al algoritmo de planificación (menos cambios de proceso), y de simplificarlo. Esto provoca que la CPU se reparta menos equitativamente entre los procesos, en detrimento de los últimos tres parámetros.
Así pues, dependiendo de los objetivos se elegirá cierto algoritmo. En los sistemas por lotes suele primar el rendimiento del sistema, mientras que en los sistemas interactivos es preferible minimizar, por ejemplo, el tiempo de espera.TÉCNICAS O ALGORITMOS DE PLANIFICACIÓN

Planificación a plazo fijo.

En la planificación a plazo fijo, ciertos trabajos se planifican para ser terminados en un periodo específico. Estos trabajos tienen un alto valor si se entregan a tiempo y pueden carecer de valor si se entregan después del límite. La planificación a plazo fijo es compleja por muchas razones:

Los usuarios deben proporcionar por adelantado y en forma precisa las necesidades de recursos de su trabajo. Tal información rara vez está disponible.
El sistema debe ejecutar el programa de plazo fijo sin una severa degradación de servicio para los otros usuarios.
El sistema debe planificar cuidadosamente las necesidades de recursos permitiendo un libre tránsito del plazo fijo. Esto puede ser difícil debido a la llegada de programas nuevos con demandas impredecibles.
Si se activan muchos trabajos de plazo fijo, la planificación puede llegar a ser tan compleja que necesite métodos de optimización sofisticados para asegurar que el plazo fijo se cumpla.
El manejo intenso de recursos requeridos por la planificación de plazo fijo puede generar una sobrecarga sustancial.

Planificación Primero en llegar - Primero en Salir (FIFO).

Los procedimientos son despachados de acuerdo al orden de llegada a la cola de listos. Una vez que un proceso tiene el CPU, se ejecuta hasta su terminación. Esta planificación es No apropiativa; es justa en el sentido formal, pero algo injusta porque los grandes procesos hacen esperar a trabajos pequeños y, los trabajos sin importancia hacen esperar a los trabajos importantes.

La Planificación FIFO ofrece una varianza en tiempo de respuesta relativamente pequeña y es, por tanto, más predecible que otros esquemas; no es un esquema útil en la planificación de procesos interactivos porque no garantiza buenos tiempos de respuesta.También se puede implementar mediante la utilización de una lista. Se reemplazan las páginas de la cabeza y se agregan al final.

Una vez que el proceso obtiene la cpu, se ejecuta hasta terminar, ya que es una disciplina “no apropiativa”.
Puede ocasionar que procesos largos hagan esperar a procesos cortos y que procesos no importantes hagan esperar a procesos importantes.
Es más predecible que otros esquemas.
No puede garantizar buenos tiempos de respuesta interactivos.
Suele utilizarse integrado a otros esquemas, por ejemplo, de la siguiente manera:

Los procesos se despachan con algún esquema de prioridad.
Los procesos con igual prioridad se despachan “FIFO”.

**Planificación por Prioridad al más corto (SJF, Short Job First)**.

La disciplina del trabajo más corto primero es NO apropiativa y en ella el trabajo o proceso con tiempo estimado de ejecución hasta terminación más corto, es el siguiente en ser ejecutado. El SJF reduce el tiempo de espera de los procesos, sin embargo, tiene una varianza mayor (es decir, es menos predecible) que en FIFO, sobre todo para los trabajos largos.

SJF favorece a los procesos cortos a costa de los procesos largos. Además, selecciona los trabajos que serán atendidos y que dejarán el sistema lo antes posible. Esto último traduce en listas de espera cortas. El SJF es NO apropiativo por lo que resulta de poca utilidad en ambientes de tiempo compartido.

Es una disciplina no apropiativa y por lo tanto no recomendable en ambientes de tiempo compartido.
El proceso en espera con el menor tiempo estimado de ejecución hasta su terminación es el siguiente en ejecutarse.
Los tiempos promedio de espera son menores que con “FIFO”.
Los tiempos de espera son menos predecibles que en “FIFO”.
Favorece a los procesos cortos en detrimento de los largos.
Tiende a reducir el número de procesos en espera y el número de procesos que esperan detrás de procesos largos.
Requiere un conocimiento preciso del tiempo de ejecución de un proceso, lo que generalmente se desconoce.
Se pueden estimar los tiempos en base a series de valores anteriores.

**Planificación por Prioridad al Tiempo Restante más Corto (SRTF, Short Remaining Time First)**.

En la figura 6.5 tenemos un ejemplo de funcionamiento del algoritmo en el que se observa cómo se penalizan las ráfagas largas (como en SJF). Un punto débil de este algoritmo se evidencia cuando una ráfaga muy corta suspende a otra un poco más larga, siendo más largo la ejecución en este orden al ser preciso un cambio adicional de proceso y la ejecución del código del planificador.

Es la contraparte apropiativa del SJF.
Es útil en sistemas de tiempo compartido.
El proceso con el tiempo estimado de ejecución menor para …nalizar es el siguiente en ser ejecutado.

Un proceso en ejecución puede ser apropiado por un nuevo proceso con un tiempo estimado de ejecución menor.
Tiene mayor sobrecarga que la planificación SJF.
Debe mantener un registro del tiempo de servicio transcurrido del proceso en ejecución, lo que aumenta la sobrecarga.

Los trabajos largos tienen un promedio y una varianza de los tiempos de espera aún mayor que en SJF.
La apropiación de un proceso a punto de terminar por otro de menor duración recién llegado podría significar un mayor tiempo de cambio de contexto (administración del procesador) que el tiempo de finalización del primero.
Al diseñarse los Sistemas Operativos se debe considerar cuidadosamente la sobrecarga de los mecanismos de administración de recursos comparándola con los beneficios esperados.

Planificación el Siguiente con Relación de Respuesta Máxima (HRN)

Corrige algunas de las debilidades del SJF, tales como el exceso de perjuicio hacia los procesos (trabajos) largos y el exceso de favoritismo hacia los nuevos trabajos cortos.
Es una disciplina no apropiativa.
La prioridad de cada proceso está en función no sólo del tiempo de servicio del trabajo, sino que también influye la cantidad de tiempo que el trabajo ha estado esperando ser servido.
Cuando un proceso ha obtenido la cpu, corre hasta terminar.
Las prioridades, que son dinámicas, se calculan según la siguiente fórmula, donde p_res la “prioridad”, t_e es el “tiempo de espera” y t_s es el “tiempo de servicio”:

Planificación del tiempo restante más corto primero (SRT).

La SRT es apropiativa, en ella el proceso con el tiempo estimado de ejecución menor para llegar a su terminación es el siguiente en ser ejecutado, incluyendo las nuevas llegadas. En la disciplina SJF, una vez que el trabajo comienza su ejecución sigue hasta que termina. En SRT, un proceso en ejecución puede ser apropiado por un nuevo proceso con n tiempo estimado de ejecución menor.

La SRT tiene una sobrecarga mayor que la SJF. Debe mantener un registro del tiempo de servicio transcurrido del trabajo en ejecución y debe controlar las apropiaciones ocasionales.

Planificación el siguiente con relación de respuesta máxima (HRT).

Brinch Hansen (1971) desarrolló la estrategia el siguiente con relación de respuesta máxima (HRT), que corrige algunas de las debilidades de SJF, en especial el favoritismo por los tamaños pequeños. La HRT es una disciplina de planificación NO apropiativa en la cual la prioridad de cada trabajo está en función, no sólo del tiempo de servicio del trabajo, sino del tiempo que un proceso ha estado esperando a ser servido, Una vez que un trabajo obtiene el CPU, se ejecuta hasta su terminación. Las prioridades dinámicas en HRT se calculan según la fórmula

Planificación Round Robin (RR)

Los procesos son despachados en FIFO, pero, se les otorga una cantidad limitada de tiempo de CPU llamada división de tiempo (time - slice) o cuanto (quantum). Si un proceso no termina antes de que se termine su tiempo de CPU, el CPU es apropiado y asignado al siguiente proceso en espera. El proceso apropiado se coloca al final de la lista de listos.

Planeación round robin.

El esquema Round robin es efectivo en un ambiente de tiempo compartido en el cual el sistema necesita garantizar un tiempo de respuesta razonable para los usuarios interactivos. La sobre carga de la apropiación se mantiene baja mediante eficientes mecanismos de cambio de contexto y proporcionado suficiente memoria para que los procesos residan en ella al mismo tiempo.

Existe una variante de este esquema llamada selfish round robin (SRR). En este esquema los procesos que entran al sistema se colocan primero en una lista de espera hasta que su prioridad alcanza el nivel de proceso para la lista de activos. Mientras un proceso está en la lista de espera, su prioridad aumenta en una relación a; cuando un proceso entra a la lista de activos su prioridad se incrementa en una relación b.

Tamaño del cuanto.

La determinación del tamaño del cuanto es decisiva para la operación efectiva de un sistema computacional. ¿Debe ser pequeño o grande el cuanto? ¿Debe ser fijo o variable? ¿Debe ser el mismo para todos los usuarios, o debe ser diferente para cada grupo de usuarios?.

Cuando se tiene un cuanto grande cada proceso pude recibir todo el tiempo que necesita para su terminación, de manera que el esquema round robin se convierte en un FIFO. Cuando el cuanto es pequeño, la sobrecarga por el intercambio de contexto se convierte en un factor dominante y el rendimiento del sistema se degrada.

¿Cuál es el cuanto óptimo ? Es claro que cambia de un sistema a otro y que varia de acuerdo a la carga del sistema.

Tamaño del Cuanto o Quantum

La determinación del tamaño del cuanto es decisiva para la operación efectiva de un sistema computacional
Los interrogantes son: ¿cuanto pequeño o grande?, ¿cuanto fijo o variable? y ¿cuanto igual para todos los procesos de usuarios o determinado por separado para cada uno de ellos?.
Si el cuanto se hace muy grande, cada proceso recibe todo el tiempo necesario para llegar a su terminación, por lo cual la asignación en rueda (“RR”) degenera en “FIFO”.

Si el cuanto se hace muy pequeño, la sobrecarga del intercambio de contexto se convierte en un factor dominante y el rendimiento del sistema se degrada, puesto que la mayor parte del tiempo de cpu se invierte en el intercambio del procesador (cambio de contexto) y los procesos de usuario disponen de muy poco tiempo de cpu.

El cuanto debe ser lo suficientemente grande como para permitir que la gran mayoría de las peticiones interactivas requieran de menos tiempo que la duración del cuanto, es decir que el tiempo transcurrido desde el otorgamiento de la cpu a un proceso hasta que genera una petición de Entrada / Salida debe ser menor que el cuanto establecido, de esta forma, ocurrida la petición la cpu pasa a otro proceso y como el cuanto es mayor que el tiempo transcurrido hasta la petición de Entrada / Salida, los procesos trabajan al máximo de velocidad, se minimiza la sobrecarga de apropiación y se maximiza la utilización de la
Entrada / Salida. El cuanto óptimo varía de un sistema a otro y con la carga, siendo un valor de referencia 100 mseg (cien milisegundos)

Queves multi-level

Planificación de Dos Niveles
Los esquemas analizados hasta ahora suponen que todos los procesos ejecutables están en la memoria principal.
Si la memoria principal es insuficiente, ocurrirá lo siguiente

Habrá procesos ejecutables que se mantengan en disco.

Habrá importantes implicaciones para la planificación, tales como las siguientes:

El tiempo de alternancia entre procesos para traer y procesar un proceso del disco es considerablemente mayor que el tiempo para un proceso que ya está en la memoria principal.
Es más eficiente el intercambio de los procesos con un planificador de dos niveles.

El esquema operativo de un planificador de dos niveles es como sigue:

Se carga en la memoria principal cierto subconjunto de los procesos ejecutables.
El planificador se restringe a ellos durante cierto tiempo.
Periódicamente se llama a un planificador de nivel superior para efectuar las siguientes tareas:

Eliminar de la memoria los procesos que hayan permanecido en ella el tiempo suficiente.
Cargar a memoria los procesos que hayan estado en disco demasiado tiempo.

El planificador de nivel inferior se restringe de nuevo a los procesos ejecutables que se encuentren en la memoria.
El planificador de nivel superior se encarga de desplazar los procesos de memoria a disco y viceversa.

Los criterios que podría utilizar el planificador de nivel superior para tomar sus decisiones son los que se indican a continuación:

¿Cuánto tiempo ha transcurrido desde el último intercambio del proceso?.
¿Cuánto tiempo de cpu ha utilizado recientemente el proceso?.
¿Qué tan grande es el proceso? (generalmente los procesos pequeños no causan tantos problemas en este sentido).
¿Qué tan alta es la prioridad del proceso?.

El planificador de nivel superior podría utilizar cualquiera de los métodos de planificación analizados.

Multi-level feedback queves.

Colas de Retroalimentación de Niveles Múltiples Cuando un proceso obtiene la CPU, sobre todo cuando todavía no ha tenido oportunidad de establecer un patrón de comportamiento, el planificador no tiene idea de la cantidad de tiempo de CPU que necesitará el proceso. Los procesos limitados por la E/S normalmente usan la CPU sólo un momento antes de generar una solicitud de E/S; los procesos limitados por la CPU pueden usar el procesador durante horas si está disponible en forma no apropiativa.
Un mecanismo de planificación debe:

Favorecer a los trabajos cortos.

Favorecer a los trabajos limitados por la E/S para lograr un mejor aprovechamiento de los dispositivos de E/S.

Determinar la naturaleza de un trabajo lo más pronto posible y planificarlo de acuerdo con su naturaleza.

Las colas de retroalimentación de niveles múltiples (figura 6.6) ofrecen una estructura que cumple con estos objetivos. Un proceso nuevo entra en la red de colas al final de la primera cola. Se desplaza en esa cola mediante Round Robin hasta que obtiene la CPU. Si el trabajo termina o cede la CPU para esperar la terminación de una operación de E/S o de algún evento, el trabajo abandona la red de colas. Si el cuanto expira antes de que el proceso ceda voluntariamente la CPU, el proceso se colocará al final de la cola del siguiente nivel. El proceso será atendido otra vez cuando llegue a la cabeza de esa cola si está vacía la primera. Mientras el proceso utilice todo el cuanto proporcionado en cada nivel, continuará desplazándose al final de la siguiente cola inferior. Por lo general, existe una cola en el nivel más bajo en la cual el proceso circula por turno rotatorio hasta que termina.
En muchos esquemas de retroalimentación de múltiples niveles, el cuanto asignado a un proceso cuando pasa a una cola de nivel inferior alcanza un valor mayor. De esta forma, cuanto más tiempo se encuentre un proceso en la red de colas más grande será el cuanto asignado cada vez que obtenga la CPU, pero tal vez no obtenga la CPU muy a menudo, porque los procesos de las colas de nivel superior tienen mayor prioridad. Un proceso situado en una cola no puede ejecutarse a menos que estén vacías las colas de nivel superior. Un proceso en ejecución será desposeído por un proceso que llegue a una cola superior.
Considérese ahora cómo responde un mecanismo de este tipo a diferentes tipos de procesos. El mecanismo debe favorecer a los procesos limitados por la E/S para lograr un buen aprovechamiento de los dispositivos y una respuesta buena para los usuarios interactivos; y de hecho lo hace porque los procesos limitados por la E/S entrarán en la red con prioridad alta y se les asignará rápidamente la CPU. El tamaño del cuanto de la primera cola se elegirá lo suficientemente grande para que la gran mayoría de los trabajos limitados por la E/S generen una petición de E/S antes de que expire el primer cuanto. Cuando el proceso solicita E/S, abandona la red y ha obtenido un tratamiento favorable, tal como se deseaba.
Ahora considérese una tarea limitada por la CPU que necesita mucho tiempo de procesador. Esa tarea entra en la cola más alta de la red con prioridad alta. Recibe rápidamente su primera asignación de la CPU, pero su cuanto expira y el proceso se coloca en la cola del siguiente nivel inferior. En ese momento, el proceso tiene una prioridad menor que la de los procesos que llegan al sistema, en particular los trabajos limitados por la E/S, que obtienen primero la CPU. El proceso limitado por la CPU acaba recibiendo ésta, obtiene un cuanto mayor que en la cola más alta y vuelve a utilizar la totalidad de su cuanto. Luego es situado al final de la siguiente cola inferior. El proceso sigue desplazándose a colas inferiores, espera más entre divisiones de tiempo y utiliza todo su cuanto cada vez que obtiene la CPU ( a menos que sea arrebatada por un proceso entrante). En algún momento, el proceso limitado por la CPU llega a la cola de nivel inferior, en donde entrará en una planificación por turno hasta terminar.
Las colas de retroalimentación de niveles múltiples son ideales para separar procesos en categorías basadas en su necesidad de la CPU. En un sistema de tiempo compartido, cada vez que un proceso abandona la red de colas puede "marcarse" con la identidad de la última cola en donde estuvo, y cuando el proceso entra de nuevo en la red de colas, puede enviarse directamente a la cola en la cual terminó su operación por última vez. En este caso, el planificador está usando un razonamiento heurístico, según el cual el comportamiento anterior del proceso es un buen indicador de su comportamiento en un futuro inmediato. De esta forma, un proceso limitado por la CPU que regresa a la red de colas no se coloca en las colas de nivel alto donde interferiría con el servicio a los procesos cortos de prioridad alta o con los limitados por la E/S.
Si los procesos se colocan siempre dentro de la red en la cola que ocuparon la última vez, será imposible que el sistema responda a cambios de un proceso, por ejemplo, de estar limitado por la CPU, a estar limitado por la E/S. El problema puede resolverse marcando al proceso también con su duración dentro de la red la última vez que estuvo en ella. Así, cuando el proceso entra de nuevo en la red puede colocarse en la cola correcta. Entonces, si el proceso entra en una fase nueva en la cual deja de estar limitado por la CPU y empieza a estar limitado por la E/S, el proceso experimentará en principio un tratamiento lento mientras el sistema determina que la naturaleza del proceso está cambiando. Pero el mecanismo de planificación responderá con rapidez a este cambio. Otra forma de hacer que el sistema responda a los cambios de comportamiento de los procesos es permitir que un proceso ascienda un nivel en la red de colas cada vez que abandona voluntariamente la CPU antes de que expire su cuanto.
El mecanismo de colas de retroalimentación de niveles múltiples es un buen ejemplo de mecanismo adaptativo, que responde a los cambios en el comportamiento del sistema que controla. Los mecanismos adaptativos implican, en general, una carga extra mayor que los no adaptativos, pero la sensibilidad ante los cambios en el sistema da como resultado una mejor capacidad de respuesta, y justifica el aumento en el gasto extra.
Una variante común del mecanismo de colas de retroalimentación de múltiples niveles consiste en hacer que un proceso circule por turno varias veces en cada cola antes de pasar a la siguiente cola inferior. El número de ciclos en cada cola crece por lo regular cuando el proceso pasa a la siguiente cola inferior.

Planificación a la Tasa de Respuesta mas Alta

Brinch Hansen desarrolló la estrategia de prioridad a la tasa de respueta más alta (HRN, highest-response-ratio-next) que corrige algunas deficiencias de SJF, particularmente el retraso excesivo de trabajos largos y el favoritismo excesivo para los trabajos cortos. HRN es un disciplina de planificación no apropiativa en la cual la prioridad de cada proceso no sólo se calcula en función del tiempo de servicio, sino también del tiempo que ha esperado para ser atendido. Cuando un trabajo obtiene el procesador, se ejecuta hasta terminar. Las priori
dades dinámicas en HRN se calculan de acuerdo con la siguiente expresión:

prioridad = (tiempo de espera + tiempo de servicio) / tiempo de servicio

Como el tiempo de servicio aparece en el denominador, los procesos cortos tendrán preferencia. Pero como el tiempo de espera aparece en el numerador, los procesos largos que han esperado también tendrán un trato favorable. Obsérvese que la suma tiempo de espera + tiempo de servicio es el tiempo de respuesta del sistema para el proceso si éste se inicia de inmediato.

Planificación por el Comportamiento

Con este tipo de planificación se pretende garantizar al usuario cierta prestación del sistema y tratar de cumplirla. Si en un sistema tenemos 'n' usuarios lo normal será garantizar a cada uno de ellos al menos 1/n de la potencia del procesador. Para ello necesitamos del tiempo consumido por el procesador y el tiempo que lleva el proceso en el sistema. La cantidad de procesador que tiene derecho a consumir el proceso será el cociente entre el tiempo que lleva en el sistema entre el número de procesos que hay en el sistema. A esa cantidad se le puede asociar una prioridad que vendrá dada como el cociente entre tiempo de procesador que ha consumido y el tiempo que se le prometió (el tiempo que tiene derecho a consumir). De tal modo que si esa proporción es de 0'5 significa que tan sólo ha consumido la mitad del tiempo prometido pero si es de 2 quiere decir que ha consumido más de lo debido, justamente el doble.

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 Medio 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.

Planificación Apropiativa y No apropiativa

Una disciplina de planificación es no apropiativa si una vez que la CPU ha sido asignada al proceso, ya no se le puede arrebatar. Y por el contrario, es apropiativa, si se le puede quitar la CPU.

La planificación apropiativa es útil en los sistemas en los cuales los procesos de alta prioridad requieren una atención rápida. En los de tiempo real, por ejemplo, las consecuencias de perder una interrupción pueden ser desastrosas. En los sistemas de tiempo compartido, la planificación apropiativa es importante para garantizar tiempos de respuesta aceptables.

La apropiación tiene un precio. El cambio de proceso implica gasto extra. Para que la técnica de apropiación sea efectiva deben mantenerse muchos procesos en memoria principal de manera que el siguiente proceso se encuentre listo cuando quede disponible la CPU. Conservar en memoria principal procesos que no están en ejecución implica gasto extra.

En los sistema no apropiativos, los trabajos largos retrasan a los cortos, pero el tratamiento para todos los procesos es más justo. Los tiempos de respuesta son más predecibles porque los trabajos nuevos de alta prioridad no pueden desplazar a los trabajos en espera.

Al diseñar mecanismos de planificación apropiativa no hay que perder de vista la arbitrariedad de casi todos los sistemas de prioridades. Se puede construir un mecanismo complejo para implantar fielmente un esquema de apropiación por prioridades sin que, de hecho, se hayan asignado prioridades de forma coherente.

El Reloj de Interrupciones

El sistema operativo gestiona un reloj de interrupciones que genera interrupciones cada cierto tiempo. Un proceso mantiene el control de la CPU hasta que la libera voluntariamente (acaba su ejecución, o se bloquea), hasta que el reloj interrumpe o hasta que alguna otra interrupción desvía la atención de la CPU. Si el usuario se encuentra en ejecución y el reloj interrumpe, el sistema operativo entra en ejecución para comprobar, por ejemplo, si ha pasado el cuanto de tiempo del proceso que estaba en ejecución.

El reloj de interrupciones asegura que ningún proceso acapare la utilización del procesador. El sistema operativo, apoyándose en él, intenta distribuir el tiempo de CPU entre los distintos procesos ya sean de E/S o de cálculo. Por tanto, ayuda a garantizar tiempos de respuesta para los usuarios interactivos, evitando que el sistema quede bloqueado en un ciclo infinito de algún usuario y permite que los procesos respondan a eventos dependientes de tiempo. Los procesos que deben ejecutarse periódicamente dependen del reloj de interrupciones.

No se debe confundir en ningún caso al reloj de interrupciones con el reloj de la máquina o reloj hardware. Veamos con un pequeño ejemplo como esto es imposible.
Como sabemos, todas las tareas de una computadora están sincronizadas por un reloj hardware. La velocidad de un procesador determina la rapidez con la que ejecuta un paso elemental o cambio en el sistema. Por ejemplo, si decimos de una máquina que tienen un microprocesador que va a una frecuencia de 100 MHz eso quiere decir que produce alrededor de 100 millones de pasos elementales o cambios en el sistema en un segundo. Pero una instrucción consume algunos de estos pasos mínimos.
Supongamos que en media una instrucción consume alrededor de 100 pasos elementales. No podemos interrumpir al procesador a la misma velocidad a la que opera porque entonces no se podría llegar nunca a ejecutar ninguna instrucción. Parece razonable que se elija una frecuencia menor para el reloj de interrupciones. Por ejemplo, se podría generar una interrupción cada 0'02 segundos (tener una frecuencia de 50 Hz) esto significa que se estaría interrumpiendo al procesador cada dos millones de ciclos. En ese tiempo bajo la suposición de que una instrucción consume 100 pasos se habría ejecutado unas 20000 instrucciones. Esto sí es mucho más razonable.
En resumen el reloj de interrupciones tiene una frecuencia inferior al reloj hardware y superior al cuanto de tiempo o intervalos de tiempo en que se quiera controlar en el sistema.

Uso de Prioridades

Las prioridades pueden ser asignadas de forma automática por el sistema, o bien se pueden asignar externamente. Pueden ganarse o comprarse. Pueden ser estáticas o dinámicas. Pueden asignarse de forma racional, o de manera arbitraria en situaciones en las que un mecanismo del sistema necesita distinguir entre procesos pero no le importa cuál de ellos es en verdad más importante.

Las prioridades estáticas no cambian. Los mecanismos de prioridad estática son fáciles de llevar a la práctica e implican un gasto extra relativamente bajo. Sin embargo, no responden a cambios en el entorno que podrían hacer necesario un ajuste de prioridades.

2.4 Concurrencia y secuenciabilidad

Concurrencia

Es la existencia de varias actividades ejecutándose simultáneamente, y necesitan sincronizarse para actuar conjuntamente. Se trata, en este caso, de un concepto lógico, ya que sólo hace referencia a las actividades, sin importar el número de procesadores presentes.

Para que dos actividades, sean concurrentes, es necesario que tengan relación entre sí, como puede ser la cooperación en un trabajo determinado o el uso de información compartida.

Los procesos son concurrentes si existen simultáneamente. Los procesos concurrentes pueden funcionar en forma totalmente independiente unos de otros, o pueden ser asíncronos, lo cual significa que en ocasiones requiere cierta sincronización y cooperación.

En un sistema monoprocesador, la existencia de multiprogramación es condición necesaria, pero no suficiente para que exista concurrencia, ya que los procesos pueden ejecutarse independientemente. Por ejemplo, un editor y un compilador pueden estar ejecutándose simultáneamente en una computadora sin que exista concurrencia entre ellos. Por otro lado si un programa se está ejecutando y se encuentra grabando datos en un archivo, y otro programa también en ejecución está leyendo datos de ese mismo archivo, sí existe concurrencia entre ellos, pues el funcionamiento de uno interfiere en el funcionamiento de otro.

Si un sistema es multiprocesador, también pueden presentarse situaciones de concurrencia siempre y cuando las actividades necesiten actuar entre sí, bien por utilizar información común, o por cualquier otra causa.

Los procesos del sistema pueden ejecutarse concurrentemente, puede haber múltiples tareas en el CPU con varios procesos. Existen varias razones para permitir la ejecución concurrente:

Compartir recursos físicos: Ya que los recursos del hardware de la computadora son limitados, nos podemos ver obligados a compartirlos en un entorno multiusuario.

Compartir recursos lógicos: Puesto que varios usuarios pueden interesarse en el mismo elemento de información (por ejemplo un archivo compartido), debemos proporcionar un entorno que permita el acceso concurrente a estos tipos de recursos.

Acelerar los cálculos: Si queremos que una tarea se ejecute con mayor rapidez, debemos dividirla en subtareas, cada una de las cuales se ejecutara, en paralelo con las demás.

Modularidad: Podremos construir el sistema en forma modular, dividiendo las funciones del sistema en procesos separados.

Comodidad: Un usuario puede tener que ejecutar varias tareas a la vez, por ejemplo puede editar, imprimir y compilar en paralelo.

La ejecución concurrente que requiere la cooperación entre procesos necesita un mecanismo para la sincronización y comunicación de procesos, exclusión mutua y sincronización.

PROBLEMAS DE CONCURRENCIA
En los sistemas de tiempo compartido (aquellos con varios usuarios, procesos, tareas, trabajos que reparten el uso de CPU entre estos) se presentan muchos problemas debido a que los procesos compiten por los recursos del sistema. Imagine que un proceso está escribiendo en la unidad de cinta y se le termina su turno de ejecución e inmediatamente después el proceso elegido para ejecutarse comienza a escribir sobre la misma cinta. El resultado es una cinta cuyo contenido es un desastre de datos mezclados. Así como la cinta, existen una multitud de recursos cuyo acceso debe der controlado para evitar los problemas de la concurrencia.

El sistema operativo debe ofrecer mecanismos para sincronizar la ejecución de procesos: semáforos, envío de mensajes, 'pipes', etc. Los semáforos son rutinas de software (que en su nivel más interno se auxilian del hardware) para lograr exclusión mutua en el uso de recursos. Para entender este y otros mecanismos es importante entender los problemas generales de concurrencia, los cuales se describen enseguida.

Condiciones de Carrera o Competencia: La condición de carrera (race condition) ocurre cuando dos o más procesos accesan un recurso compartido sin control, de manera que el resultado combinado de este acceso depende del orden de llegada. Suponga, por ejemplo, que dos clientes de un banco realizan cada uno una operación en cajeros diferentes al mismo tiempo.

El usuario A quiere hacer un depósito. El B un retiro. El usuario A comienza la transacción y lee su saldo que es 1000. En ese momento pierde su turno de ejecución (y su saldo queda como 1000) y el usuario B inicia el retiro: lee el saldo que es 1000, retira 200 y almacena el nuevo saldo que es 800 y termina. El turno de ejecución regresa al usuario A el cual hace su depósito de 100, quedando saldo = saldo + 100 = 1000 + 100 = 1100. Como se ve, el retiro se perdió y eso le encanta al usuario A y B, pero al banquero no le convino esta transacción. El error pudo ser al revés, quedando el saldo final en 800.

Postergación o Aplazamiento Indefinido(a): Esto se mencionó en el apartado anterior y consiste en el hecho de que uno o varios procesos nunca reciban el suficiente tiempo de ejecución para terminar su tarea. Por ejemplo, que un proceso ocupe un recurso y lo marque como 'ocupado' y que termine sin marcarlo como 'desocupado'. Si algún otro proceso pide ese recurso, lo verá 'ocupado' y esperará indefinidamente a que se 'desocupe'.

Condición de Espera Circular: Esto ocurre cuando dos o más procesos forman una cadena de espera que los involucra a todos. Por ejemplo, suponga que el proceso A tiene asignado el recurso 'cinta' y el proceso B tiene asignado el recurso 'disco'. En ese momento al proceso A se le ocurre pedir el recurso 'disco' y al proceso B el recurso 'cinta'. Ahi se forma una espera circular entre esos dos procesos que se puede evitar quitándole a la fuerza un recurso a cualquiera de los dos procesos.

Condición de No Apropiación: Esta condición no resulta precisamente de la concurrencia, pero juega un papel importante en este ambiente. Esta condición especifica que si un proceso tiene asignado un recurso, dicho recurso no puede arrebatársele por ningún motivo, y estará disponible hasta que el proceso lo 'suelte' por su voluntad.

Condición de Espera Ocupada: Esta condición consiste en que un proceso pide un recurso que ya está asignado a otro proceso y la condición de no apropiación se debe cumplir. Entonces el proceso estará gastando el resto de su time slice checando si el recurso fue liberado. Es decir, desperdicia su tiempo de ejecución en esperar. La solución más común a este problema consiste en que el sistema operativo se dé cuenta de esta situación y mande a una cola de espera al proceso, otorgándole inmediatamente el turno de ejecución a otro proceso.

Condición de Exclusión Mutua: Cuando un proceso usa un recurso del sistema realiza una serie de operaciones sobre el recurso y después lo deja de usar. A la sección de código que usa ese recurso se le llama 'región crítica'. La condición de exclusión mutua establece que solamente se permite a un proceso estar dentro de la misma región crítica. Esto es, que en cualquier momento solamente un proceso puede usar un recurso a la vez. Para lograr la exclusión mutua se ideo también el concepto de 'región crítica'. Para logar la exclusión mutua generalmente se usan algunas técnicas para lograr entrar a la región crítica: semáforos, monitores, el algoritmo de Dekker y Peterson, los 'candados'. Para ver una descripción de estos algoritmos consulte

Condición de Ocupar y Esperar un Recurso: Consiste en que un proceso pide un recurso y se le asigna. Antes de soltarlo, pide otro recurso que otro proceso ya tiene asignado.

Los problemas descritos son todos importantes para el sistema operativo, ya que debe ser capaz de prevenir o corregirlos. Tal vez el problema más serio que se puede presentar en un ambiente de concurrencia es el 'abrazo mortal', también llamado 'trabazón' y en inglés deadlock. El deadlock es una condición que ningún sistema o conjunto de procesos quisiera exhibir, ya que consiste en que se presentan al mismo tiempo cuatro condiciones necesarias: La condición de no apropiación, la condición de espera circular, la condición de exclusión mutua y la condición de ocupar y esperar un recurso. Ante esto, si el deadlock involucra a todos los procesos del sistema, el sistema ya no podrá hacer algo productivo. Si el deadlock involucra algunos procesos, éstos quedarán congelados para siempre.

Exclusión mutua de secciones criticas

Forma de asegurar que si un proceso está usando una variable o archivo compartido, los otros procesos quedarán excluidos de hacer lo mismo.
Los procesos pueden tener en su código secciones en que realizan cálculos internos y operaciones que no dan lugar a condiciones de competencia. Sin embargo existen secciones de programa en que el proceso está accediendo a recursos compartidos que pueden dar pié a condiciones de competencia.

La parte del programa en que se accede a un recurso compartido se denomina sección o región crítica (requisito necesario, pero no suficiente). Los requisitos para que procesos paralelos cooperen de manera correcta usando datos compartidos son los siguientes:

Dos procesos nunca pueden estar simultáneamente dentro de sus regiones críticas.
No se puede suponer nada acerca de las velocidades de ejecución de los procesos o el número de las CPU.
Ningún proceso que se ejecute fuera de su región crítica puede bloquear a otros procesos.
Ningún proceso deberá tener una espera indefinida para entrar en su región crítica.

La exclusión mutua debe ponerse en práctica sólo cuando los procesos obtienen acceso a datos compartidos modificables; cuando los procesos realizan operaciones que no entran en conflicto con otras, deben permitirse que procedan concurrentemente. Cuando un proceso obtiene acceso a datos compartidos modificables, se dice que se encuentra en una sección crítica. Es evidente que, para evitar la clase de problemas observados en la sección anterior, debe asegurarse que cuando un proceso se encuentre en una sección crítica, los demás procesos (o al menos los que tengan acceso a los datos compartidos) no pueden entrar a sus propias secciones críticas.

Mientras un proceso se encuentra en su sección crítica, otros procesos pueden, claro está, seguir ejecutándose fuera de sus secciones críticas. Cuando un proceso abandona su región crítica, otro proceso que espera entrar en su propia sección crítica (si existe algún proceso en espera). Lograr que se cumpla la exclusión mutua es uno de los problemas fundamentales de la programación concurrente. Se han propuesto muchas soluciones, algunas de software y otras de hardware, algunas sencillas y otras complejas, y algunas que requieren la cooperación voluntaria de los procesos y otras que exigen un escrito ajuste a rígidos protocolos.

Encontrarse dentro de una región crítica es un estado especial concedido a un proceso. El proceso tiene acceso exclusivo a los datos compartidos y los demás procesos que requieran acceso a los datos en ese momento deben esperar. Así pues, las secciones críticas deben ejecutarse tan rápido como sea posible; un proceso no se debe bloquear dentro de su propia sección crítica y las secciones críticas deben codificarse con mucho cuidado (para evitar, por ejemplo, la posibilidad de ciclos infinitos).

Si un proceso de una sección crítica termina, ya sea voluntaria o involuntariamente, el sistema operativo, al realizar su mantenimiento de terminaciones, debe liberar la exclusión mutua de manera que otros procesos puedan entrar en sus regiones críticas.

En el momento de un cambio de proceso del uno al otro se pueden producir las siguientes situaciones:

Sin sincronización entre procesos: Puede darse el caso de que ESCRIBIR esté actualizando un registro y se quede a medías, sorprendiéndole el cambio de proceso, por tanto, terminará de escribirlo cuando vuelva a hacer uso del procesador. Con el cambio le tocará el turno al proceso LEER, que accederá a dicho registro pudiendo leerlo completamente. Es evidente que los datos leídos serán inconsistentes.

Con sincronización entre procesos: Supongamos algún mecanismo que prohíba la lectura (bloqueo de registros) a cualquier proceso, mientras el proceso ESCRIBIR esté realizando alguna operación. En este caso, LEER, al hacer uso del procesador que se encuentra bloqueado, quedaría en espera de que el registro quede totalmente escrito y se proceda a su desbloqueo, LEER pasaría a estado bloqueado, ESCRIBIR terminaría su trabajo sobre el registro y en el siguiente cambio LEER procedería a hacer el suyo.

Esta sincronización por la cual una actividad impide que otras puedan tener acceso a un dato mientras se encuentra realizando una operación sobre el mismo es lo que se conoce como exclusión mutua.

La zona de código de un proceso que no puede ser interrumpida por otro, por los motivos expuestos anteriormente se le llama Región Crítica.

Regiones críticas

Es el conjunto de actividades elementales cuya ejecución exige el monopolio de recursos. Por ejemplo, para indicar que alguna acción se realizará con acceso exclusivo a ciertos datos compartidos.

Región datos - compartidos do acción

¿Como evitar la región critica?. La clave para prevenir el problema aquí y en muchas otras situaciones en que interviene la memoria compartida, archivos compartidos y todo lo que se comparte, consiste en determinar alguna manera de prohibir que un proceso lea y escriba los datos compartidos al mismo tiempo.

De otra manera lo que se necesita es la sincronización. Una manera de asegurar de que si un proceso ésta utilizando una variable o archivo compartido, es que los otros procesos no pueden hacer lo mismo.

Para tener una solución adecuada a la región crítica se necesita que se cumplan cuatro condiciones.

Nunca dos procesos pueden encontrarse simultáneamente dentro de sus regiones críticas.
No se hacen suposiciones acerca de las velocidades relativas de los procesos o del Número de CPU.
Ningún proceso suspendido fuera de la región crítica debe bloquear a otros procesos.
Nunca un proceso debe querer entrar en forma arbitraria en su región crítica.

Representación de regiones criticas

Cuando se diseña un proceso que debe contener una o varias regiones críticas se deben de tomar en cuenta las siguientes consideraciones:

La región crítica debe ser ejecutada lo más rápido posible.
Un programa no debe ínter bloquearse en una región crítica.
Las regiones críticas deben ser programadas con mucho cuidado (no se permiten Ciclos indefinidos).
Mientras un proceso está en su región crítica otros procesos pueden continuar
Ejecutándose fuera de las regiones críticas.
Cuando se tienen procesos que comparten datos, si un proceso deja la región
Crítica otro de los procesos que espera a entrar en su región crítica puede proceder.

Cuando el proceso termina, voluntaria o involuntariamente, el sistema operativo debe de realizar la limpieza propia de fin de proceso y liberar la exclusión mutua de otros procesos.

El problema de la Sección Crítica

En procesos compitiendo para utilizar algún dato compartido.
Cada proceso tiene un segmento de código, llamado sección crítica, en el que se accede al dato compartido.
Problema – asegurarse de que cuando un proceso esta ejecutándose en su sección crítica, a ningún otro proceso se le permite ejecutar la suya.
Estructura del proceso Pi

repeat
entry section
sección crítica
exit section
sección restante
until false;

Solución al problema de la Sección Crítica

Una solución al problema de la sección crítica debe satisfacer los siguientes tres requerimientos:

Exclusión Mútua. Si un proceso Pi esta ejecutandose en su sección crítica, entonces ninguno de los otros procesos puede estar en su sección crítica
Progreso. Si ningún proceso esta ejecutándose en su sección crítica y existen procesos que quieren entrar en su sección crítica, entonces la selección del próximo proceso que entrará a la sección crítica no puede ser pospuesta indefinidamente.
Espera limitada. Debe existir un límite del número de veces que se les permite a otros procesos entrar en sus secciones críticas en el intervalo entre que un proceso ha hecho un requerimiento para entrar en su sección crítica y que se le concede el permiso.

Se supone que cada proceso se ejecuta a velocidad distinta de cero.
Ninguna suposición respecto a la velocidad relativa de los n procesos.

Intentos iniciales para resolver el problema

Inhibir las interrupciones.
Solo dos procesos, P0 and P1
Estructura general del proceso Pi

repeat
entry section
sección crítica
exit section
sección restante
until false;

Los procesos pueden compartir algunas variables comunes para sincronizar sus acciones.

Algoritmo 1

Variables compartidas:
– var turn: (0..1);
inicialmente turn = 0
– turn = i ? Pi puede entrar en su sección crítica
Proceso Pi
repeat
while turn ? i do no-op;
sección crítica
turn := j;
sección restante
until false;
Satisface la condición de exclusión mútua, pero no la de progreso (si turn=0 y P1 esta listo para entrar en su sección crítica, P1 no puede hacerlo, incluso aunque P0 este en la sección restante)

Algoritmo 2

Variables compartidas
– var flag: array [0..1] of boolean;
inicialmente flag [0] = flag [1] = false.
– flag [i] = true ? Pi listo para entrar en su sección crítica
Proceso Pi
repeat
flag[i] := true;
while flag[j] do no-op;
sección crítica
flag [i] := false;
sección restante
until false;

Satisface la exclusión mútua, pero no el requerimiento de progreso. (P0 pone flag[0 ] =true y P1 pone flag[1 ] =true; cada uno esperando al otro indefinidamente)

Algoritmo 3

- Combinación de las variables compartidas de los algoritmos 1 y 2.
- Proceso Pi

repeat
flag [i] := true;
turn := j;
while (flag [j] and turn = j) do no-op;
sección crítica
flag [i] := false;
sección restante
until false;

- Cumple los tres requerimientos; resuelve el problema de la sección crítica para dos procesos.

Algoritmo del panadero

Antes de entrar a su sección crítica, los procesos reciben un número. El que posea el número menor entra en la sección crítica.
Si los procesos Pi y Pj reciben el mismo número, si i < j, entonces Pi es servido primero; si no lo es Pj .
El esquema de numeración siempre genera números en orden creciente; por ejemplo 1,2,3,3,3,3,4,5...

Sincronización de procesos en Sección Crítica

En procesos concurrentes, la ejecución de un proceso se desarrolla en forma asíncrona respecto a los otros. Sin embargo cuando dos, o más procesos necesitan entrar en región crítica, es necesario que exista una sincronización entre ellos a fin de garantizar que al menos uno y solo un proceso entrará en región crítica.

Si una actividad desea impedir que otra acceda a ciertos datos compartidos, mientras no se cumpla una determinada condición, debemos sincronizar las actividades con dicha condición. Por tanto, la sincronización es un elemento necesario para asegurar la exclusión mutua.

Existen tres algoritmos diseñados para este fin, son los siguientes:

Espera Activa.

Espera no Activa

Mecanismos de Hardware.

Algoritmo de Espera activa.

Estos algoritmos establecen la espera de entrada a la región crítica con un bucle que será roto en el momento en que se cumpla una determinada condición. Se, les llama así por que el proceso no queda bloqueado en su ejecución, sino que constantemente compite por el procesador. Entre los distintos algoritmos de este tipo existentes podemos citar:

Espera con mutex: Algoritmo que utiliza un switch (MUTEX) a través del cual se produce la sincronización.

Alternancia: Ligeramente mejor que el anterior, utiliza también una variable turno para realizar el sincronismo entre los Procesos.

Algoritmo de DEKKER: Resuelve el problema mediante la solución propuesta por DEKKER, basando su funcionamiento en una Tabla unidimensional de dos elementos lógicos (Switches).

Algoritmo de Espera no activa: Son los algoritmos que establecen la espera para entrar en la región crítica bloqueando, el proceso, haciendo que deje de competir por el procesador hasta que se cumpla la condición de desbloqueo

Entre estos algoritmos existen los siguientes:

Semáforos: Para eliminar los problemas que se producen con los algoritmos de espera activa, fundamentalmente los referidos a la sobrecarga que producen en el sistema, Dijkstra(1965) diseño un mecanismo basado en una variable entera utilizada como contador de peticiones de entrada a una sección crítica. Esta variable es compartida por todos los procesos del sistema. Este nuevo tipo de variable se denominó semáforo, por su capacidad de gestionar el tráfico de los proceso que desean acceder a datos compartidos. Con este sistema, cuando un proceso intente entrar en una región crítica mientras otro está accediendo a los datos compartidos, se bloqueará de igual manera que cuando un proceso accede a un recurso que está ocupado.

Un semáforo se define como una variable entera que puede inicializarse y su valor no debe ser negativo y solo puede ser manipulada por las operaciones P y V.

Operaciones P y V: Estas operaciones son indivisibles, es decir que cuando un proceso ejecuta una de ellas no puede ser interrumpida.

Operación V: Esta operación consiste en incrementar en uno el valor del semáforo sobre el que actúa, también es conocida como signal. Es una operación de liberación.

Así, si se tiene un semáforo S, V de S V(S) o signal(S) causara S=S+1. V(MUTEX) - libera

Operación P: Bloqueo, decrementa en uno el valor del semáforo sobre el que actúa siempre y cuando el valor del semáforo es >=0 (positivo) también se le conoce en la literatura inglesa como Wait. Por ejemplo si tenemos P(S), Wait(S) si S=S-1. P(MUTEX) - Espera el proceso.

De las definiciones anteriores se puede observar que el valor de un semáforo esta relacionado con el número de veces que se ejecutan, dichas operaciones es decir, el valor del semáforo S es igual a su valor inicial más número de operaciones V menos número de operaciones P realizadas por ese semáforo.

VAL(S) = C(S) + NV(S) - NP(S) NP( ) <= NV( ) +1

VALOR VALOR INICIAL

Por definición se tiene que el valor del semáforo debe ser mayor que cero, VAL(S)>0. En el caso cuando el valor del semáforo es cero que relación nos queda:

NP(S) = C(S) + NV(S)

Es importante señalar que la relación anterior será siempre valida independientemente del número de operaciones P y V ejecutadas sobre el semáforo.

Regiones críticas: Son sistemas que permiten establecer protecciones contra una mala utilización de los usuarios. Para ello sólo permiten que los datos compartidos se puedan acceder desde determinadas regiones quedando transparentes desde el resto. Tiene inconvenientes relacionados con la sincronización y no permite que varias actividades puedan realizar operaciones de lectura simultánea.

Regiones criticas condicionales: Es una mejora del método anterior tratando de resolver algunos problemas de sincronización que se presentan.

Monitores: Uno de los problemas en los mecanismos anteriores es que el programador tiene que proporcionar de forma explícita el modo de sincronización. Para evitarlo B. Hansen y C.A.R. Hoare desarrollarón un nuevo mecanismo denominado Monitor que debe ser soportado por el lenguaje correspondiente.

Un monitor permite compartir, segura y eficientemente, datos entre varias actividades, garantizando la exclusión mutua, sin necesidad de que el programador tenga que suministrarla explícitamente.

Se basa en dos premisas: la primera es la abstracción de datos consistente en una técnica capaz de separar las operaciones a ejecutar sobre los datos, de los detalles de diseño propio de los mismos (los lenguajes Modula y Ada soportan este tipo de estructuras). La segunda es que realizan la exclusión mutua de forma implícita.

La finalidad más útil de los monitores es reunir todas las funciones que operan sobre un conjunto de datos compartidos en un sólo módulo, de manera que todos los accesos a esos datos estarán forzados a utilizar dichas funciones.

Contadores de eventos:Es un mecanismo para sincronizar actividades sin que sea necesario forzar la exclusión mutua, ya sea por que no deseamos limitar la concurrencia de las actividades, o simplemente porque no lo necesitamos. Se basa en una variable entera que cuenta determinadas operaciones.

Mensajes: Mecanismo que permite intercambiar información necesaria durante el desarrollo normal de un proceso en ejecución. Es más un mecanismo de cooperación que de sincronización.

Existen dos tipos de comunicación entre procesos:

Directa: Envió y recepción de mensajes entre si; de manera que se asocia un enlace vi direccional único entre cada dos procesos.

Indirecta: Mensajes enviados y recibidos a través de mail boxees o buzones de correo. Con este método cada proceso puede estar relacionado con tantos buzones como desee consiguiendo comunicarse con tantos procesos como sea necesario.

Mecanismos de Hardware

Son instrucciones hardware que aseguran la exclusión mutua. Entre las más utilizadas son las siguientes:

Deshabilitar interrupciones: Se puede forzar la exclusión mutua deshabilitando las interrupciones mientras haya alguna actividad en la región crítica. De este modo, dicha actividad no podrá ser interrumpida y, por tanto, no se podrá producir ningún cambio de proceso. La habilitación y deshabilitación se realiza con una instrucción máquina, es una operación rápida.

Instrucción TEST-AND-SET: Forza la exclusión mutua. La ventaja es que no puede ser interrumpida por que no muchas computadoras la poseen.

Lock: Se basa en la instrucción anterior y permite el acceso a la región crítica a un proceso en caso de no existir otra actividad dentro de su región crítica, no permitiendo en caso contrario.

¿Como resolver la exclusión mutua usando semáforos?.

Para resolver el problema de debe hacer lo siguiente:

1.- Identificar todas las regiones críticas.

2.- Definir tantos semáforos como regiones críticas se tengan, dichos semáforos se inicializarán con 1

3.- C/U de las regiones críticas será antecedida por la operación P y precedida por la

operación V.

Ejemplo: MUTEX es el semáforo

Región crítica.

Con lo anterior solo un proceso podrá entrar a la región crítica con lo que se esta asegurando la exclusión mutua.

MUTEX = 1

* Que pasa si se tiene:

A) P(MUTEX) Entra el proceso, se decrementa en uno el semáforo pero no libera, por lo tanto hay un dead lock, no hay sincronización entre procesos

SECCION CRITICA ni exclusión mutua

P(MUTEX)

B) V(MUTEX) Sale el proceso se incrementa en uno el semáforo libera el proceso, por lo tanto no hay dead lock, no origina proceso de exclusión mutua

SECCION CRITICA

V(MUTEX) .

C) V(MUTEX) Sale el proceso se incrementa en uno el semáforo pero no libera, por lo tanto no hay dead lock.

SECCION CRITICA

P(MUTEX)

D) P(MUTEX) Entra el proceso consume y libera, por lo tanto no hay dead lock, y da solución a la exclusión mutua y a la sincronización.

SECCION CRITICA

V(MUTEX)

Pregunta. * Varios procesos actualizan en forma concurrente a una lista ligada.

a) Que problema se puede producir.

R.- Se puede producir un problema de sincronización y no hay exclusión mutua.

b) Es un problema de exclusión mutua.

R.- Exclusión mutua.

c) Como resolver el problema.

R.- Dando solución a la exclusión mutua.

* Si las operaciones P y V no fueran atómicas, la exclusión mutua seria violada.

R.- Si por que los procesos pueden tomar el mismo valor y no se incrementa dos veces sino solo una.

PROBLEMAS CLASICOS DE SINCRONIZACIÓN

Este tipo de problemas constituyen ejemplos de una amplia clase de problemas de control de concurrencia. Estos problemas se utilizan para probar casi todos los esquemas de sincronización propuestos. En las soluciones se emplean semáforos para la solución.

El problema de buffer limitado

Supongamos que el depósito consiste en n buffers, cada uno capaz de almacenar un elemento. El semáforo MUTEX proporciona la exclusión mutua para los accesos al depósito de buffers y se le asigna un valor inicial de 1. Los semáforos vacíos y llenos cuentan el número de buffers vacíos y llenos, respectivamente. El semáforo vacío recibe 1 un valor inicial n; al semáforo lleno se le asigna el valor inicial 0.

El problema de los lectores y escritores.

Un objeto de datos (como un archivo o un registro) va a ser compartido por varios procesos concurrentes. Algunos de estos procesos sólo quieren leer el contenido del objeto compartido, mientras que otros quieren actualizarlos (o sea, leerlo y escribirlo), hacemos una distinción entre estos dos tipos de procesos refiriéndonos a los procesos interesados sólo en leer como lectores y escritores y a los demás como escritores. Obviamente, el que dos lectores tengan acceso simultáneo al objeto de datos compartido no tendrá ningún efecto adverso; sin embargo, si un escritor y otro proceso (ya sea lector o escritor) tiene acceso simultáneo al objeto compartido, puede surgir el caos.

Para asegurar que no surjan estas dificultades, es necesario que los escritores tengan acceso exclusivo al objeto compartido. A este problema de sincronización se le conoce como problema de los lectores y escritores, el cual es ha utilizado para probar casi todas las nuevas primitivas de sincronización.

El problema de los filósofos comensales

Cinco filósofos pasan su vida comiendo u pensando. Los filósofos comparten una mesa circular rodeada por cinco sillas, una para cada uno de ellos. En el centro de la mesa se encuentra una fuente de arroz, y también sobre la mesa hay cinco palillos chinos. Cuando un filósofo piensa, no interactúa con sus colegas. Ocasionalmente, un filósofo tiene hambre y trata de coger los dos palillos que están más cerca de él (los palillos colocados entre él y sus vecinos de la derecha y de la izquierda). Un filósofo sólo puede coger un palillo a la vez y, obviamente, no puede ser el que esta en la mano de un vecino. Cuando un filósofo ambiento tiene sus dos palillos al mismo tiempo come sin soltarlos. Cuando termina de comer, coloca ambos palillos sobre la mesa y comienza a pensar otra vez.

Problema del productor consumidor

En un contexto de procesos concurrentes, se tiene un conjunto de procesos productores de mensajes y otro conjunto de procesos consumidores de mensajes. La zona donde se depositarán y recogerán los mensajes es un buffer de tamaño n (n localidades).

Tanto productores como consumidores ejecutaran cíclicamente los siguientes algoritmos.

Productor consumidor.

El recurso que se va a compartir es el buffer por lo tanto la sección critica será el acceso y manipulación de dicho buffer.

Para resolver el problema de exclusión mutua será necesario definir un semáforo para controlar el acceso al buffer,

Definición de un semáforo para controlar el accedo a buffer.
Cuando el consumidor se apodera del buffer P ( ) !Sorpresa esta vacío ¡

Productor gana

se apodera del buffer

¡¡¡sorpresa el buffer esta lleno!!!

no va a poder depositar

y por lo tanto va a liberar el buffer

nunca hace V( ).

Productor consumidor utilizando espera activa, figura # 22.

Productor Consumidor

Produce msg. Lock (existe msg.)

Lock (espacio disponible) Lock (acceso a buffer)

Lock (acceso a buffer) extrae msg.

Deposita msg. Unlock (acceso a buffer)

Unlock (acceso a buffer) Unlock (espacio disponible)

Unlock (existe msg.) Consume msg.

Problema de sincronización. La sincronización entre productor y consumidor es necesaria debido a lo siguiente: Los productores no deben depositar mensajes si el buffer se encuentra lleno y los consumidores no deben accesar el buffer cuando este se encuentre vació.

Para resolver el problema de definirá un semáforo que defina el espacio disponible y será inicializado con un valor igual a n y un semáforo que defina la existencia de mensaje el cual será inicializado con un 0.

Productor Consumidor

produce msg. P (existe msg.)

X P (espacio disponible) P (acceso s buffer)

P (acceso a buffer) extrae msg.

* deposita msg V (acceso a buffer)

V (acceso a buffer) V (espacio disponible)

X V (existe msg) Consume msg.

Solución a la exclusión mutua X –

Solución de la sincronización

Buffer lleno Espacio disponible=N, existe msg=0.

Casos críticos

Buffer vacío

Mecanismo de semáforos

Un semáforo es un tipo de datos abstracto que permite el uso de un recurso de manera exclusiva cuando varios procesos están compitiendo.

El tipo de datos abstracto cumple la siguiente semántica:

El estado interno del semáforo cuenta cuantos procesos todavía pueden utilizar el recurso. Se puede realizar, por ejemplo, con un número entero que nunca llega a ser negativo.
Exiten tres operaciones con un semáforo: init(), wait(), y signal() que realizan lo siguiente:

init()

Inicializa el semáforo antes de que cualquier proceso haya ejecutado ni una operación wait() ni una operación signal() al límite de número de procesos que tengan derecho a acceder el recurso. Si se inicializa con 1, se ha contruido un semáforo binario.

wait()

Si el estado indica cero, el proceso se queda atrapado en el semáforo hasta que sea despertado por otro proceso. Si el estado indica que un proceso más puede acceder el recurso se decrementa el contador y la operación termina con exito.

La operación wait() tiene que estár implementada como una instrucción atómica. Sin embargo, en muchas implementaciones la operación wait() puede ser interrumpida. Normalmente existe una forma de comprobar si la salida del wait() es debido a una interrupción o porque se ha dado acceso al semáforo.

signal()

Una vez se ha terminado el uso del recurso, el proceso lo señaliza al semáforo. Si queda algún proceso bloqueado en el semáforo uno de ellos sea despertado, sino se incrementa el contador.

La operación signal() también tiene que estár implementada como instrucción atómica. En algunás implementaciones es posible comprobar si se haya despertado un proceso con exito en caso que hubiera alguno bloqueado.

Para despertar los procesos se puede implementar varias formas que se destinguen en sus grados de justicia, por ejemplo con un simple sistema tipo FIFO.

El acceso mutuo a regiones críticas se arregla con un semáforo que permita el acceso a un sólo proceso

S.init(1)

P1                         P2

a: loop                        loop

b:   S.wait()                    S.wait()

c:   critical region             critical region

d:   S.signal()                  S.signal()

e:   non-critical region         non-critical region

f: endloop                     endloop

Observamos los siguiente detalles:

Si algún proceso no libera el semáforo, se puede provocar un bloqueo.
No hace falta que un proceso libere su propio recurso, es decir, la operación signal() puede sea ejecutada por otro proceso.
Con simples semáforos no se puede imponer un orden en los procesos accediendo a diferentes recursos.

Si existen en un entorno solamente semáforos binarios, se puede simular un semáforo general usando dos semáforos binarios y un contador, por ejemplo, con las variables delay, mutex y count.
La operación init() inicializa el contador al número máximo permitido. El semáforo mutex asegura acceso mutuamente exclusivo al contador. El semáforo delay atrapa a los procesos que superan el número máximo permitido.
La operación wait() se implementa de la siguiente manera:

  delay.wait()

  mutex.wait()

  decrement count

  if count greater 0 then delay.signal()

  mutex.signal()

y la operación signal() se implementa de la siguiente manera:

  mutex.wait()

  increment count

  if count equal 1 then delay.signal()

  mutex.signal()

Unas principales desventajas de semáforos son:

no se puede imponer el uso correcto de los wait()s y signal()s
no existe una asociación entre el semáforo y el recurso
entre wait() y signal() el usuario puede realizar cualquier operación con el recurso

Mecanismo de Monitores

Todas las estructuras que hemos visto hasta ahora siguen provocando problemas para el programador:

El control sobre los recursos está distribuido por varios puntos de un programa
No hay protección de las variables de control que siempre fueron globales

Por eso se usa el concepto de monitores que implementan un nivel aún más alto de abstracción facilitando el acceso a recursos compartidos.

Un monitor es un tipo de datos abstracto que contiene:

un conjunto de procedimientos de control de los cuales solamente un subconjunto es visible desde fuera
un conjunto de datos privados, es decir, no visibles desde fuera

El acceso al monitor está permitido solamente a través de los procedimientos públicos y el compilador garantiza exclusión mutua para todos los procedimientos. La implementación del monitor controla la exclusión mutua con colas de entrada que contengan todos los procesos bloqueados. Pueden existir varias colas y el controlador del monitor elige de cual cola se va a escoger el siguiente proceso para actuar sobre los datos. Un monitor no tiene acceso a variables exteriores con el resultado de que su comportamiento no puede depender de ellos.

Una desventaja de los monitores es la exclusividad de su uso, es decir, la concurrencia está limitada si muchos procesos hacen uso del mismo monitor.
Un aspecto que se encuentra en muchas implementaciones de monitores es la sincronización condicional, es decir, mientras un proceso está ejecutando un procedimiento del monitor (con exclusión mutua) puede dar paso a otro proceso liberando el cerrojo. Estas operaciones se suele llamar wait() o delay(). El proceso que ha liberado el cerrojo se queda bloqueado hasta que otro proceso le despierta de nuevo. Este bloqueo temporal está realizado dentro del monitor (dicha técnica se refleja en Java con wait() y notify()).

La técnica permite la sincronización entre procesos porque actuando sobre el mismo recurso los procesos pueden cambiar el estado del recurso y pasar así información de un proceso al otro.
Lenguajes de alto nivel que facilitan la programación concurrente suelen tener monitores implementados dentro del lenguaje (por ejemplo refJavaMonitoresJava usa el concepto de monitores para realizar el acceso mutuamente exclusivo a sus objetos).
El uso de monitores es bastante costoso, porque se pierde eficiencia por tanto bloqueo de los prosesos. Por eso se intenta aprovechar de primitivas más potentes para aliviar este problema, como vemos en la siguiente sección.

Interbloqueo (DeadLock)

Si un conjunto de procesos esta en estado de espera por recursos y nunca cambia de estado porque los recursos por los que espera están siendo utilizados por otros procesos en estado de espera tenemos un DEADLOCK. Los recursos son la memoria, dispositivos de E/S, semáforos, archivos, etc. La forma en que un proceso hace uso de un recurso es:

Solicitud: si el recurso esta disponible se le otorga, si no el proceso pasa a estado de espera.
Uso: El proceso utiliza el recurso
Liberación: el proceso debe liberar el recurso.

Condiciones Necesarias para que se produzca DEADLOCK

Si se presentan simultáneamente las cuatro siguientes condiciones el sistema esta en DEADLOCK.

EXCLUSION MUTUA: Por lo menos un proceso que tenga otorgado un recurso en forma exclusiva.
USO Y ESPERA: Debe existir al menos un proceso que este haciendo uso de un recurso y que este esperando por otros recursos asignados a otros procesos.
NO INTERRUPCION: Los recursos no pueden ser retirados al proceso. Si un proceso hace uso de un recurso no le podrá ser retirado hasta que voluntariamente el proceso lo libere.
ESPERA CIRCULAR: Debe existir un conjunto de procesos {P1.....Pn} tal que P1 espera por un recurso utilizado por P2,......,Pn espera por un recurso utilizado por P1.

Resourse Allocation Graph(Grafo de utilizacion de recursos)
Conjunto de Vértices: U =P U R
P={P1,P2,....,Pn}
R={R1,R2,...,Rn}

Conjunto de Aristas

Una arista de un proceso Pi a un Recurso Rj significa que el proceso i esta haciendo una solicitud por el recurso Rj.
Una arista del recurso Rj al proceso Pi, significa que el recurso esta asignado al proceso.
Si un RAG no tiene ciclos el sistema no esta en DEADLOCK, si los tiene no se puede afirmar nada.

Mecanismos para tratar con Deadlocks

Evasion de Deadlocks

Si se tiene cuidado al en la forma de asignar los recursos se pueden evitar situaciones de Deadlock. Supongamos un ambiente en el que todos los procesos declaren a priori la cantidad máxima de recursos que habá de usar.

Estado Seguro

Un estado es seguro si se pueden asignar recursos a cada proceso (hasta su máximo) en algún orden sin que se genere Deadlock. El estado es seguro si existe un ordenamiento de un conjunto de procesos {P1...Pn} tal que para cada Pi los recursos que Pi podrá utilizar pueden ser otorgados por los recursos disponibles mas los recursos utilizados por los procesos Pj,j<i. Si los recursos solicitados por Pi no pueden ser otorgados, Pi espera a que todos los procesos Pj hayan terminado.

Algoritmo del banquero de Dijkstra

Asigna peticiones de recursos siempre que las mismas den como resultado estados seguros. Solicitudes que den como resultado estados inseguros serán negadas hasta que puedan ser satisfechas. Este algoritmos evita situaciones de Deadlock asignando los recursos en forma correcta.
Las debilidades del algoritmo son: que requiere que la cantidad de recursos del sistema sea constante, requiere una cantidad de procesos constante y requiere que los procesos garanticen que los recursos van a ser devueltos en un intervalo finito de tiempo.

En el área de la informática, el problema del deadlock ha provocado y producido una serie de estudios y técnicas muy útiles, ya que éste puede surgir en una sola máquina o como consecuencia de compartir recursos en una red.
En el área de las bases de datos y sistemas distribuidos han surgido técnicas como el 'two phase locking' y el 'two phase commit' que van más allá de este trabajo. Sin embargo, el interés principal sobre este problema se centra en generar técnicas para detectar, prevenir o corregir el deadlock.

Las técnicas para prevenir el deadlock consisten en proveer mecanismos para evitar que se presente una o varias de las cuatro condiciones necesarias del deadlock. Algunas de ellas son:

Asignar recursos en orden lineal: Esto significa que todos los recursos están etiquetados con un valor diferente y los procesos solo pueden hacer peticiones de recursos 'hacia adelante'. Esto es, que si un proceso tiene el recurso con etiqueta '5' no puede pedir recursos cuya etiqueta sea menor que '5'. Con esto se evita la condición de ocupar y esperar un recurso.

Asignar todo o nada: Este mecanismo consiste en que el proceso pida todos los recursos que va a necesitar de una vez y el sistema se los da solamente si puede dárselos todos, si no, no le da nada y lo bloquea.

Algoritmo del banquero: Este algoritmo usa una tabla de recursos para saber cuántos recursos tiene de todo tipo. También requiere que los procesos informen del máximo de recursos que va a usar de cada tipo. Cuando un proceso pide un recurso, el algoritmo verifica si asignándole ese recurso todavía le quedan otros del mismo tipo para que alguno de los procesos en el sistema todavía se le pueda dar hasta su máximo. Si la respuesta es afirmativa, el sistema se dice que está en 'estado seguro' y se otorga el recurso. Si la respuesta es negativa, se dice que el sistema está en estado inseguro y se hace esperar a ese proceso.

Para detectar un deadlock, se puede usar el mismo algoritmo del banquero, que aunque no dice que hay un deadlock, sí dice cuándo se está en estado inseguro que es la antesala del deadlock. Sin embargo, para detectar el deadlock se pueden usar las 'gráficas de recursos'. En ellas se pueden usar cuadrados para indicar procesos y círculos para los recursos, y flechas para indicar si un recurso ya está asignado a un proceso o si un proceso está esperando un recurso. El deadlock es detectado cuando se puede hacer un viaje de ida y vuelta desde un proceso o recurso. Por ejemplo, suponga los siguientes eventos:

evento 1: Proceso A pide recurso 1 y se le asigna.
evento 2: Proceso A termina su time slice.
evento 3: Proceso B pide recurso 2 y se le asigna.
evento 4: Proceso B termina su time slice.
evento 5: Proceso C pide recurso 3 y se le asigna.
evento 6: Proceso C pide recurso 1 y como lo está ocupando el proceso A, espera.
evento 7: Proceso B pide recurso 3 y se bloquea porque lo ocupa el proceso C.
evento 8: Proceso A pide recurso 2 y se bloquea porque lo ocupa el proceso B.

En la figura 5.1 se observa como el 'resource graph' fue evolucionando hasta que se presentó el deadlock, el cual significa que se puede viajar por las flechas desde un proceso o recurso hasta regresar al punto de partida. En el deadlock están involucrados los procesos A,B y C.

Una vez que un deadlock se detecta, es obvio que el sistema está en problemas y lo único que resta por hacer es una de dos cosas: tener algún mecanismo de suspensión o reanudación que permita copiar todo el contexto de un proceso incluyendo valores de memoria y aspecto de los periféricos que esté usando para reanudarlo otro día, o simplemente eliminar un proceso o arrebatarle el recurso, causando para ese proceso la pérdida de datos y tiempo.

Dead lock en sistemas de spool.

Los sistemas de spool suelen ser los más propensos al dead lock. Varios trabajos parcialmente complejos que generan líneas de impresión a un archivo de spool pueden interbloquearse si el espacio disponible para trabajar se llena antes de completarse alguno de esos trabajos. La solución más común es limitar los spoolers de entrada de modo que no se lean más archivos cuando se llega al límite de su capacidad.

Postergación indefinida.

En los sistemas que mantienen procesos en espera mientras realizan la asignación de recursos y/o procesan la planificación de decisiones, es posible que un proceso sea postergado de manera indefinida mientras otro reciben la atención del sistema. A esta situación se le conoce como postergación indefinida, es diferente del dead lock pero sus consecuencias son igual de negativas.

En algunos sistemas la postergación indefinida se evita aumentando la prioridad de un proceso mientras espera por un recurso, a esto se le llama envejecimiento.

Conceptos sobre recursos.

Un sistema operativo es sobre todo un administrador de recursos, existen básicamente dos tipos de recursos:

* Recursos no apropiativos. Un recurso que no se puede liberar antes de completar su actividad sin perder la validez del proceso que lo usa, se dice que un recurso no apropiativo. Una impresora o una unidad de cinta no pueden ser liberados hasta que no termine su trabajo.

* Recursos apropiativos. Un recurso que puede ser usado temporalmente por varios procesos sin comprometer el correcto funcionamiento de dichos procesos se dice que es un recurso apropiativo. El CPU y la memoria principal (mediante las técnicas de paginación) son recursos que pueden ser asignados temporalmente por varios procesos. La apropiatividad de recursos es extremadamente importante en los sistemas de multiprogramación.

Los datos y los programas son recursos que tienen características especiales. En un sistema multiusuario donde se pueden compartir editores, compiladores y programas en general, es ineficiente cargar una copia de ellos para cada usuario que lo solicite. En lugar de ello se carga una sola vez a la memoria y se hacen varias copias de los datos, una por cada usuario.

El código que no cambia mientras está en uso se llama código reéntrate. El código que puede ser cambiado pero que se inicializa cada vez que se usa se llama reutilizable en serie. El código reéntrate puede ser compartido simultáneamente por varios procesos mientras que el reutilizable en serie sólo puede ser usado por un proceso a la vez.

Métodos para manejar los Dead Lock,

- Prevención

- No permitirlos

- Evitarlos

- Difícil y caro

- Permitirlos y recuperarlos

- Por perdida de información

Figura # 24. Prevención de Dead Lock.

En principio existen cuatro áreas importantes en la investigación del dead lock, a saber:

1) Prevención:

En las técnicas de prevención el interés se centra en condicionar un sistema para que elimine toda probabilidad de que ocurra un dead lock (normalmente a costa de recursos).

2) Evitación:

En las técnicas para evitar, la idea es poner condiciones menos estrictas que la prevención, para lograr una mejor utilización de los recursos, pero procurando no caer en un dead lock.

3) Detección:

Los métodos de detección se usan en sistemas que permiten la ocurrencia de un dead lock de forma voluntaria o involuntaria.

4) Recuperación:

Los métodos de recuperación se usan para romper los dead lock en un sistema, para poder liberarlo de ellos y los procesos estancados pueden continuar y llegar a su fin

Modelo del sistema.

Un sistema se compone de un número finito de recursos que se distribuyen entre varios procesos que compiten por ellos. Los recursos se dividen en varios tipos, cada uno de los cuales consiste en varios ejemplares idénticos. Los ciclos del CPU, el espacio de memoria, los archivos y los dispositivos de E/S (como impresoras y unidades de cinta) son ejemplos de tipos de recursos.

Un proceso debe solicitar un recurso antes de usarlo, y liberarlo al terminar su uso. Un proceso puede solicitar cuantos recursos quiera para llevar a cabo su tarea. Obviamente, el número no puede exceder del total de recursos disponibles del sistema. En otras palabras, un proceso no puede solicitar tres impresoras si el sistema solo dispone de dos.

En el modo de operación normal, un proceso solo puede utilizar un recurso en la secuencia siguiente:

1. Solicitud. Si la solicitud no puede atenderse de inmediato (por ejemplo, otro proceso está utilizando ese recurso), entonces el proceso solicitante debe esperar hasta que pueda adquirir el recurso.

2. Utilización. El proceso puede trabajar con el recurso (por ejemplo, si el recurso es una impresora, el proceso puede imprimir en ella).

3. Liberación. El proceso libera el recurso.

La solicitud y liberación de recursos son llamadas al sistema. Algunos ejemplos son las llamadas Solicitar y Liberar dispositivos, Abrir y Cerrar archivos, y Asignar y Liberar memoria. La solicitud y liberación de otros recursos puede lograrse atreves de las operaciones espera (P) y señal (V) sobre semáforos. Además la utilización de recursos solo puede conseguirse mediante llamadas al sistema (por ejemplo, para leer o escribir en un archivo o dispositivo de E/S), de modo que para cada utilización, el sistema operativo verifica que el proceso que dispone del recurso ya lo había solicitado y ya se le había asignado. Una tabla del sistema registra si cada uno de los recursos está libre o asignado y, de estar asignado, a qué proceso. Si un proceso solicita un recurso que se encuentra asignado a otro, puede añadirse a la cola de procesos que esperan tal recurso.

Un conjunto de procesos se encuentra en estado de bloqueo mutuo cuando cada uno de ellos espera un suceso que sólo puede originar otro proceso del mismo conjunto.

Caracterización.

Debe ser obvio que los bloqueos mutuos son indeseables, pues cuando se dan, los procesos nunca terminan su ejecución y los recursos del sistema se paralizan, impidiendo que se inicien otros procesos. Antes de analizar los distintos métodos para tratar el problema del bloqueo mutuo se describirán las circunstancias que los caracterizan.

Condiciones necesarias para que ocurra un Dead Lock.

Coffman, Elphick y Shoshani. Establecieron las cuatro condiciones necesarias para que se produzca un dead lock.

1.- Los procesos reclaman control exclusivo de los recursos que solicitan (exclusión mutua).

2.- Los procesos mantienen los recursos que se les han asignado mientras esperan por recursos adicionales (condición de espera).

3.- No se pueden tomar los recursos que los procesos tienen hasta su completa utilización (condición de no apropiatividad).

4.- Existe una cadena circular de procesos en la cual cada uno de ellos mantiene uno o más recursos que son requeridos por el siguiente proceso de la cadena (condición de espera circular).

Se deben presentar las cuatro condiciones para que puede aparecer un Dead Lock. La condición de espera circular implica la condición de retención y espera, por lo que las cuatro condiciones no son completamente independientes.

Prevención

En las estrategias de prevención de dead Locks, los recursos son otorgados a los procesos solicitados, de tal manera que la solicitud de un recurso nunca llega a un Dead Lock. Esta estrategia se cerciora de que cuando menos una de cuatro condiciones de Dead Lock nunca llegue a ocurrir.

* Exclusión mutua.

La condición de exclusión mutua debe conservarse para recursos no compartibles. Los recursos compartibles, no requieren acceso mutuamente excluyente y, por tanto, no pueden participar en un dead lock. Los archivos de sólo lectura son un buen ejemplo de recursos compartibles. Si varios procesos tratan de abrir al mismo tiempo un archivo de sólo lectura, se les puede otorgar accesos simultáneos al archivo, por lo general no es posible evitar dead lock`s negando la condición de exclusión mutua. Por su naturaleza algunos recursos no pueden compartirse.

* Negación de la condición de "espera por".

La primera estrategia de Havender requiere que todos los recursos que va a necesitar un proceso sean pedidos de una sola vez. El sistema deberá asignarlos según el principio "todo o nada". Si el conjunto de recursos que necesita un proceso está disponible se le asigna (todo) y se le permite entrar en ejecución. Si no es así, el proceso deberá esperar hasta que su conjunto de recursos esté disponible. Mientras un proceso espera. No podrá tener ningún recurso.

Esta estrategia presenta las siguientes desventajas:

Puede llevar a la postergación indefinida, ya que quizá todos los recursos requeridos estén disponibles al mismo tiempo (costos de operación altos).

Puede llevar un serio desperdicio de recursos, se requiere tener una gran cantidad de recursos para poder responder a cumplir petición.

Es ineficiente por que decrementa la concurrencia del sistemas

Una variante consiste en dividir el programa en bloques que puedan ser ejecutados con relativa independencia uno del otro. Esto reduce el desperdicio, pero implica un trabajo extra en el diseño de las aplicaciones.

Negación de la condición de "no apropiatividad

Cuando un sistema cuenta con los recursos suficientes para que los procesos puedan funcionar sin problemas (bloqueos). Cuando el sistema permite compartir los recursos y los procesos mantienen los que otros necesitan sucede un dead lock.

La segunda estrategia sugiere que cuando a un proceso que mantiene recursos se le niegue una petición de recursos adicionales deberá liberar sus recursos y, si es necesario, pedirlos de nuevo, junto con los adicionales.

Al retirar los recursos a un proceso que no puede avanzar se niega la condición de "no apropiatividad". Un problema de esta política es la postergación indefinida.

Negación de la condición de "espera circular"

Si se da a los recursos una manera exclusiva y se obliga a los procesos a pedirlos en forma ascendente es imposible que ocurra una espera circular. Esta propuesta considera:

Los recursos deben ser numerados reflejando el orden en el cual la mayoría de los trabajos los usan.
Los procesos deben pedir los recursos en forma ascendente.
Para los procesos que requieren de los recursos en un orden diferente, los recursos deberán ser tomados y retenidos mucho antes de su utilización. (Implica el desperdicio de los recursos mantenidos pero no usados).

Ordenamiento lineal del recurso.

El ordenamiento lineal elimina la posibilidad de la espera circular, pero, obliga al diseñador a trabajar más con sus códigos. Además, los números de recursos son asignados por la instalación y hay que vivir con ellos durante largos periodos (meses o años). Si los números cambian se tienen que rescribir los programas y los sistemas existentes.

La forma más simple de prevenir un Dead Lock es obteniendo todos los recursos necesarios antes que el proceso continué y así se elimine la "condición de espera".

En otro método de prevención de dead lock, un proceso bloqueado devuelve los recursos solicitados por un proceso activo, al igual que elimina la condición de "no apropiatividad"

Rosenkrantz et al Ha propuesto la siguiente optimización de este método. Todos los procesos son asignados a prioridades únicas que pueden ser totalmente ordenadas. Un proceso de retención cede el derecho de prioridad a otro proceso que sostiene el recurso necesario solo si el proceso de retención tiene el recurso necesario solo si el proceso de retención tiene mayor prioridad.

Este método reduce los derechos de prioridad al 50% al igual que previene los dead locks. En el ordenamiento de Havender's todos los recursos son ordenados de manera única y todos los procesos solicitan los recursos de manera ascendente.

Únicamente eliminando la condición de "espera circular". Si un proceso ya sostiene algunos recursos, entonces puede pedir solo aquellos acomodos en un rango superior en el orden. Obteniendo recursos, de ésta forma, previene la formación de un ciclo o de un "knot".

Prevenir

Se puede prevenir el bloqueo siempre y cuando se consiga que alguna de las condiciones necesarias para la existencia de un bloqueo no se produzca.

los procesos tienen que compartir recursos con exclusión mutua:

No se de a un proceso directamente acceso exclusivo al recurso, si no se usa otro proceso que realiza el trabajo de todos los demás manejando una cola de tareas (por ejemplo, un demonio para imprimir con su cola de documentos por imprimir).

los procesos quieren acceder a un recurso más mientras ya tienen acceso exclusivo a otro:

Se exige que un proceso pida todos los recursos que va a utilizar al comienzo de su trabajo

los recursos no permiten ser usados por más de un proceso al mismo tiempo:

Se permite que un proceso aborte a otro proceso con el fin de obtener acceso exclusivo al recurso. Hay que tener cuidado de no caer en livelock

Existe una cadena circular entre peticiones de procesos y locación de recursos:

Se ordenan los recursos linealmente y se fuerza a los procesos que accedan a los recursos en el orden impuesto. Así es imposible que se produzca un ciclo.

En las prácticas aplicamos dicho método para prevenir bloqueos en la lista concurrente.

Prevención de Deadlocks

La estrategia consiste en anular alguna de las cuatro condiciones necesarias para que se produzca un Deadlock.

No puede ser anulada porque existen recursos que deben ser usados en modalidad exclusiva.
La alternativa sería hacer que todos los procesos solicitaran todos los recursos que habrán de utilizar antes de utilizarlos al momento de su ejecución lo cual sería muy ineficiente.
Para anular esta condición cuando un proceso solicita un recurso y este es negado el proceso deberá liberar sus recursos y solicitarlos nuevamente con los recursos adicionales. El problema es que hay recursos que no pueden ser interrumpidos.
Espera Circular: esta estrategia consiste en que el sistema operativo numere en forma exclusiva los recursos y obligue a los procesos a solicitar recursos en forma ascendente. El problema de esto es que quita posibilidades a la aplicación.

Deadlock no puede ocurrir a menos que tenemos todas las cuatro condiciones. Si aseguramos que no puede ocurrir por lo menos una de las condiciones, no podemos tener deadlock.

Exclusión mutua. En general, no podemos eliminar esta condición. Hay recursos como impresoras que no son compatibles.
Retención y espera. Para no ocurrir esta condición, cuando un proceso solicita recursos, no puede retener otros. Protocolos:

Un proceso puede solicitar recursos solamente si no tiene ningunos.
Un proceso tiene que solicitar todos los recursos antes de la ejecución.

Problemas:

La utilización de recursos puede ser baja.
Starvation (bloqueo indefinido) si se necesitan algunos recursos populares.

No apropiación. Si un proceso retiene varios recursos y solicita otro que no está disponible, se le expropian todos los recursos que retiene. El proceso tiene que recuperar todos los recursos antes de ejecutar otra vez.

Pero en general no podemos expropiar recursos como impresoras y grabadores.

Espera circular. Hacemos una ordenación de los tipos de recursos en el sistema (R₁, R₂, ...). Un proceso tiene que solicitar sus recursos en orden (y todos los ejemplares de un tipo al mismo tiempo). Si necesita un tipo de recurso más baja en la ordenación, tiene que liberar los otros que retiene.
Problemas con la prevención de deadlock: Utilización baja de recursos y reducción de la productividad del sistema.

Evitar

El sistema no da permiso de acceso a recursos si es posible que el proceso se bloquee en el futuro. Un método es el algoritmo del banquero (Dijkstra) que es un algoritmo centralizado y por eso posiblemente no muy practicable en muchas situaciones.
Se garantiza que todos los procesos actúan de la siguiente manera en dos fases:

Primero se obtiene todos los cerrojos necesarios para realizar una tarea, eso se realiza solamente si se puede obtener todos a la vez,
Después se realiza la tarea durante la cual posiblemente se liberan recursos que no son necesarias.

Ejemplo:
Asumimos que tengamos 3 procesos que actúan con varios recursos. El sistema dispone de 12 recursos.

proceso	recursos pedidos	recursos reservados
A	4	1
B	6	4
C	8	5
suma	18	10

es decir, de los 12 recursos disponibles ya 10 están ocupados. La única forma que se puede proceder es dar el acceso a los restantes 2 recursos al proceso B. Cuando B haya terminado va a liberar sus 6 recursos que incluso pueden estar distribuidos entre A y C, así que ambos también pueden realizar su trabajo.
Con un argumento de inducción se verifica fácilmente que nunca se llega a ningún bloqueo.

Evitación

Un método para evitar los Dead Lock`s consiste en requerir información adicional sobre cómo se solicitarán los recursos. Por ejemplo en un sistema con una unidad de cinta y una impresora, podríamos saber que el proceso P solicitará primero la unidad de cinta y luego la impresora, antes de liberar ambos recursos. El proceso Q, por otra parte, solicitará primero la impresora y después la unidad de cinta. Con este conocimiento de la secuencia completa de la solicitud y liberación para cada proceso para cada solicitud requiere que el sistema considera los recursos disponibles en ese momento, los actualmente asignados a cada proceso y las futuras solicitudes y liberaciones de cada proceso para decidir si puede satisfacer la solicitud presente o debe esperar para evitar un posible dead lock futuro.

Los diversos algoritmos difieren en la cantidad y tipo de información que requieren.

El modelo más sencillo y útil requiere que cada proceso declare el número máximo de recursos de cada tipo que puede necesitar. Con información a priori para cada proceso es posible construir un algoritmo que asegure que el sistema nunca entrará en estado de dead lock. Este algoritmo define la estrategia de evitación de dead lock`s.

El estado de asignación de recursos viene definido por el número de recursos disponibles y asignados, y por la demanda máxima de los procesos. Un estado es seguro si el sistema puede asignar recursos a cada proceso (hasta el máximo) siguiendo algún orden u aun así evitar el dead lock.

Más formalmente, un sistema se encuentra en estado seguro sólo si existe una secuencia segura. Si no existe esta secuencia, se dice que el estado del sistema es inseguro.

Un estado seguro no es un estado de dead lock, y un estado de dead lock es un estado inseguro; pero no todos los estados inseguros son dead lock`s.

Detección

Se implementa un proceso adicional que vigila si los demás forman una cadena circular.
Más preciso, se define el grafo de asignación de recursos:

Los procesos y los recursos representan los nodos de un grafo.
Se añade cada vez una arista entre un nodo tipo recurso y un nodo tipo proceso cuando el proceso ha obtenido acceso exclusivo al recurso.
Se añade cada vez una arista entre un nodo tipo recurso y un nodo tipo proceso cuando el proceso está pidiendo acceso exclusivo al recurso.
Se eliminan las aristas entre proceso y recurso y al revés cuando el proceso ya no usa el recurso.

Cuando se detecta en el grafo resultante un ciclo, es decir, cuando ya no forma un grafo acíclico, se ha producido una posible situación de un bloqueo.
Se puede reaccionar de dos maneras si se ha encontrado un ciclo:

No se da permiso al último proceso de obtener el recurso.
Sí se da permiso, pero una vez detectado el ciclo se aborta todos o algunos de los procesos involucrados.

Sin embargo, las técnicas pueden dar como resultado que el programa no avance, incluso, el programa se puede quedar atrapado haciendo trabajo inútil: crear situaciones de bloqueo y abortar procesos continuamente.

Detección y Recuperación de Deadlocks

Cuando hay una única ocurrencia de cada recurso. (variante del grafo de "wait for graph"). Consiste en reducir el grafo, retirando las aristas que van de recursos a procesos y de procesos a recursos, colocando nuevas aristas que reflejan la situación de espera entre procesos. Si el grafo reducido tiene ciclos el sistema esta en Deadlock. Orden de operaciones = n^2 , n = cantidad de aristas.
Cuando hay múltiples ocurrencias de cada recurso

Procedure detecta_deadlock
var Disponible:array[1..n] of integer //# de recursos
Usados:array[1..n] of integer
Solicitados:array[1..n] of integer
Finalizado:array[1..n] of boolean
Begin
Work:=Disponibles;

For i:=1..n do if(usados[i]≠0) then finish[i]:=false

Else finish[i]:=true;

While(encontrar_indice_i = true) do {

Work:=work + usados[i];

Finish[i]:=true; }

If ((finish[i] = false) para algun i), 1≤i≤n then à El sistema esta en Deadlock.

End

Function encontrar_indice_i : Boolean

Begin

If (existe i tal que (Finish[i]=false && solicitados[i] ≤ work)

Then -> true

Else -> false

End

La evitacíon de deadlock tiene un costo porque todos los estados inseguros no son estados de deadlock. Esto implica que hay tiempos cuando algunos procesos tienen que esperar y recursos están desocupados sin que es necesario.

El sistema operativo puede chequear de vez en cuando si hay un deadlock. ¿Cuán frecuentemente debieramos chequear si hay deadlock?

El costo de algoritmo vs. el número de procesos en deadlock.
Saber quien creó el deadlock.
Cuando la utilización de la CPU es baja.

Tenemos que eliminar los deadlocks que encontramos. Posibilidades:

Abortar todos los procesos en deadlock. ¡Esto es un método común!
Abortar procesos uno a la vez hasta que no haya deadlock.
Retroceder los procesos a algún punto y reiniciar. El deadlock puede reocurrir.
Expropiar recursos de procesos hasta que no haya deadlock. Retrocedemos los procesos expropiados.

Tenemos que seleccionar un proceso para abortar o retroceder.
Factores:

La prioridad
El tiempo que el proceso ha corrido
El número y tipo de los recursos adquiridos
La clase de proceso (batch o interactiva)

La starvation es un problema.

Detección y Recuperación

Es el hecho de determinar si existe o no un Dead Lock, e identificar cuales son los procesos y recursos implicados en él. El uso de algoritmos de detección de interbloqueo implica una sobrecarga en el tiempo de ejecución. Para ser correcto, un algoritmo de detección de interbloqueo debe de cumplir dos criterios:

1) Debe detectar todos los dead lock´s existentes en un tiempo finito.

2) No debe reportar "falsos" Dead Lock's.

Grafo de asignación de recursos.

Los Dead Lock pueden describirse con mayor precisión en función de un grafo dirigido llamado grafo de asignación de recursos, que consiste en un conjunto de vértices V y aristas A. El conjunto de vértices V se divide en dos tipos, P = {P1,P2, ... , Pn}, el conjunto formado por todos los procesos del sistema, y R ={R1,R2, ... ,Rn}, el conjunto integrado por todos los tipos de recursos del sistema.

Representación mediante grafos del estado del sistema.

El estado de un sistema es dinámico; esto es, los procesos del sistema toman y liberan recursos continuamente. La representación del dead lock requiere la representación del estado de la interacción procesos - recursos, la representación se hace mediante un grafo dirigido que se conoce como gráfica de asignación de recursos .

En los sistemas de bases de datos distribuidos (DDBS) está representación se conoce como gráfica de espera de transacción (Transaction Wait-For TWF).

Los dead lock`s pueden describirse con mayor precisión en función de un grafo dirigido llamado grafo de asignación de recursos.

La simbologia es la siguiente . a, b, c y d.

GRÁFICA DE PETICIÓN Y ASIGNACIÓN DE RECURSOS

La técnica para la reducción de gráficas implica las consideraciones siguientes:

Si las peticiones de recursos de un proceso piden ser concedidas, entonces la gráfica puede ser reducida.
La reducción de una gráfica consiste en retirar las flechas que van de los recursos a los procesos y retirar las flechas que van del proceso al recurso.
Si una gráfica puede ser reducida para todos sus procesos entonces no hay dead lock.
Si una gráfica no puede ser reducida para todos sus procesos, entonces los procesos irreducibles constituyen la serie de procesos interbloqueados de la gráfica.
Detección de interbloqueo mediante grafos.

Un grafo G consiste de un conjunto finito no vacío.

V = C(G) de: P puntos (vértices) conjunto X de q parejas desordenadas de puntos de V(aristas).

cada par X = {U,V} de puntos en X y una línea de G por lo tanto X = UV.

Un grafo de p puntos y q líneas se denomina un grafo (p,q), el grafo (1,0) es trivial.

Petición = Proceso - Recurso

Rx Ry El proceso Pi tiene el recurso Rx y solicita el recurso Ry.

Para determinar si existe un ciclo en un grafo se puede usar la representación matricial del grafo dirigido. Dado que se tienen parejas ordenadas {Rx, Ry}, la matriz se construye colocando un 1 en la diagonal en (x,x) y (y,y) y un 1 en la posición (x,y) de la matriz. .

Reducción de la matriz del grafo.

Reducción de la matriz de un grafo correspondiente. No existen vértices terminales; los vértices 1 y 2 son iniciales y pueden ser eliminados; existe un Inter bloqueo.

Representación vectorial

Un vértice terminal sólo aparece en la columna requiere y un vértice inicial sólo aparece en la columna Tiene. Para reducir esta representación se recorren de arriba a abajo los vectores y se buscan los vértices terminales e iniciales y se elimina su renglón.

El proceso se repite hasta:

1) No existen renglones o

2) No se pueden eliminar renglones.

Si no se pueden eliminar renglones las transiciones producen un Dead Lock.

Para el grafo de la en el primer paso se eliminan los procesos P1 (vértice inicial), P2 y P3 (vértice terminal). En el segundo paso se elimina el proceso P4 (vértice terminal), inicial.

Para el grafo de la el primero se eliminan los procesos P1,P2,P3 (vértices iniciales), P4(vértice inicial al eliminar el proceso P1), Los procesos restantes no pueden ser eliminados, por lo tanto existe un dead lock. El resultado de la reducción

Recuperación

Recuperación ante Deadlocks

Cancelación de procesos

Cancelación de todos los procesos involucrados. Esto resuelve la situación de Deadlock pero tiene un costo muy alto de reprocesamiento.
Cancelacion de un proceso por vez hasta resolver la situación de Deadlock. La ventaja de esto es que el costo de reprosesamiento de la información es menor pero cada vez que se cancela un proceso debe ejecutarse el algoritmo de detección de deadlock. Los criterios para elegir el candidato a ser cancelado son: por prioridad, por tiempo de uso de CPU, por cantidad de recursos utilizados y por cuantos recursos adicionales habrá de utilizar.

Obtención de recursos (resourse Preemption). El sistema operativo selecciona un proceso y le quita los recursos otorgados. Los criterios para seleccionar el candidato son los mismos que para la cancelación. El proceso seleccionado se le quitan los recursos y se le lleva a un estado consistente (Rollback).

Recuperación de un Dead Lock.

La única forma en que el sistema operativo puede recuperarse de un interbloqueo es retirando uno o más procesos y reclamar sus recursos para que otros procesos puedan terminar. Normalmente varios procesos perderán una parte o la totalidad del trabajo realizado hasta ese momento. Este puede parecer un precio pequeño comparado con dejar que el interbloqueo se complique por varios factores.

En primer lugar, puede no estar claro que el sistema este bloqueado o no.
Muchos sistemas tienen medios pobres para suspender un proceso por tiempo indefinido y reanudarlo más tarde.
Aún cuando existan medios efectivos de suspensión /reanudación, con toda seguridad, estos implicarán una sobrecarga, considerable y pueden requerir la atención de un operador altamente calificado. No siempre se dispone de tales operadores.
Recuperarse de un interbloqueo de proporciones modestas puede suponer una cantidad razonable de trabajo.

Una forma de elegir los procesos que pueden ser retirados es de acuerdo a las prioridades de los procesos. Pero esto también tiene sus dificultades.

Las prioridades de los procesos bloqueados pueden no existir, así que el operador deberá tomar una decisión arbitraria.
Las prioridades pueden ser incorrectas, o un poco confusas debido a consideraciones especiales.
La decisión óptima de cuáles procesos retirar pueden requerir de un esfuerzo considerable para determinarla.

El enfoque más deseable a la recuperación del Dead Lock están un mecanismo efectivo de

Suspensión / reanudación. Esto permitirá detener temporalmente los procesos y después reanudarlos sin pérdida del trabajo.

MECANISMOS PARA EVITARLOS.

Havender llegó a la conclusión de que si no se cumple una de las cuatro condiciones necesarias para el interbloqueo es posible que éste ocurra.

Para evitarlo sugirió:

Cada proceso deberá pedir todos los recursos requeridos de una sola vez y no podrá proceder hasta que le hayan sido asignados todos.
Si un proceso que mantiene ciertos recursos se le niega una nueva petición, este proceso deberá liberar sus recursos originales y en caso necesario pedirlos de nuevo con los recursos adicionales.
Se impondrá la ordenación lineal de los tipos de recursos en todos los procesos, es decir, si a un proceso le han sido asignados recursos de un tipo dado, en lo sucesivo sólo podrá pedir aquellos recursos de los tipos que siguen en el ordenamiento.

Otra alternativa, para manejar los dead lock, es tener información acerca de como los recursos se van a requerir, el modelo más simple y más útil requiere que en cada proceso declare el máximo número de recursos que van a requerir con lo cual es posible construir un algoritmo que asegure que el sistema no entrara en dead lock.

Un estado es seguro si el sistema puede asignar recursos a cada proceso en algún orden evitando el dead lock.

Formalmente un sistema esta en estado seguro solamente si existe una secuencia segura. Una secuencia de procesos < P1, P2, ... Pn> esta en secuencia segura si para cada Pi, los recursos que Pi pueda requerir pueden ser satisfechos por los recursos disponibles más los recursos que tuvieron los Pj donde j < i. Si no se puede satisfacer Pi entonces Pi espera hasta que los Pj terminen.

Cuando Pi termine Pi+1 puede obtener sus recursos y así sucesivamente.

Se tienen 12 unidades de cinta se tiene 3 procesos ¿Ese sistema esta en estado seguro o no?.

Requerimiento procesos - recursos.

Requerimiento máximo - Necesidad actual = Necesidad más (Disponible).

Se tiene 12 recursos por lo tanto 12-9 = 3, entonces la secuencia es segura.

La secuencia segura es < P1,P0,P2>

Haga una situación en la cual el sistema estaría es estado inseguro.

Un estado seguro esta libre de dead lock y un estado de dead lock, es un estado inseguro pero no todos los estados inseguros producen dead lock.

Si se esta en un estado seguro se puede pasar a un estado inseguro.

Estrategias para evitarlos

Evitación del interbloqueo y el algoritmo de Dijkstra. Si las condiciones necesarias para que tenga lugar un interbloqueo están en su lugar, aún es posible evitar el interbloqueo teniendo cuidado al asignar los recursos.

El algoritmo de planificación que pueda evitar los interbloqueos fue ideado por Dijkstra (1965) y se le conoce como algoritmo del banquero. En ese algoritmo se modela la forma en que un banquero puede tratar a un grupo de clientes a quienes les ha otorgado líneas de crédito. en la (figura # 36 (a)) se observan cuatro clientes, a cada uno de los cuales se le ha otorgado cierto número de unidades de crédito. El banquero sabe que los clientes no necesitan su límite de crédito máximo de inmediato, de manera que sólo ha reservado 10 unidades en lugar de 22 para darles servicio.

Los clientes emprenden sus respectivos negocios, haciendo solicitudes de préstamo de cuando en cuando. En cierto momento). A una lista de clientes que muestra el dinero que ya se presentó y el máximo del crédito disponible se le llama estado del sistema.

Tres estados de asignación de recursos

(a) Seguro. (b) Seguro. (c) Inseguro.

Un estado es seguro si existe una secuencia de estados que lleva a todos los clientes que obtienen préstamos hasta sus límites de crédito. es seguro por que con las dos restantes, el banquero puede demorar cualquier solicitud salvo la de Carlos, con lo que permite que termine y devuelva sus cuatro recursos. Con cuatro unidades, el banquero puede permitir que David o Bárbara tengan las unidades que necesitan para terminar y así sucesivamente.

Si estando en el estado de la se le otorga una unidad más a Bárbara,

el banquero no podrá completar ninguna de la línea de crédito de su clientes. Un estado inseguro no tiene que conducir a un interbloqueo, ya que un cliente podría no necesitar su línea de crédito disponible, pero el banquero no puede confiar en ese comportamiento.

Haciendo una analogía con un Sistema Operativo tenemos: El estado actual del sistema se denomina seguro, Si el Sistema Operativo puede permitir a los usuarios actuales completar sus trabajos en un intervalo de tiempo finito. De lo contrario se le denomina inseguro. En otras palabras: Un estado seguro es aquel en el cual la asignación de recursos es tal que los usuarios pueden llegar a terminar. Un estado seguro es aquel que puede llegar a terminar. Un estado inseguro es aquel que puede llegar a un dead lock, (nunca termina).

La asignación de recursos por el algoritmo del banquero es la siguiente:

Se permite todas las condiciones de exclusión mutua, espera por y no apropiatividad.
Se permite a los procesos mantener sus recursos mientras esperan por otros.
El sistema sólo concede peticiones que den como resultado estados seguros.

El algoritmo del banquero para n recursos (de Dijkstra).

Sea n un número de proceso y m un número de recurso y sea disponible un vector de longitud m que indica el número de recursos disponibles y sea máxima una matriz de ( n x m) que define la máxima demanda de cada proceso así por ejemplo si tuviéramos máxima ( i,j ) = k define los recursos asignados a cada proceso, por ejemplo la asignación ( i , j ) = k quiere decir que el proceso i tiene asignado K instancias del recurso j necesidades ( n * m ), que indica los recursos que requieren los procesos. Necesidades ( i , j ) = Máxima ( i , j ) - Asignación ( i , j ).

Se puede considera cada renglón de las matrices asignación y necesidades como vectores y referirnos como asignación de i y necesidades de i.

Algoritmo:

Sea requerimiento de i un vector de requerimientos de proceso i.

Cuando un requerimiento de un recurso es hecho por el proceso i se realizaran las siguientes acciones:

1).- Si Requerimiento de i <= Necesidades de i ir al segundo paso. Sino error.
2).- Si requerimiento de i <= disponible ir al tercer paso. Si no recurso no disponible Pi debe esperar.

3).-
Hacer Disponible = Disponible - Requerimiento,

Asignación = Asignación + Requerimiento,

Necesidades = Necesidades - Requerimiento.

Si el estado es seguro se completa la transacción de lo contrario el proceso debe esperar y el estado anterior es restablecido.

Algoritmo para ver si el estado es seguro.

Sea trabajo (m) y final (n) vectores de longitud m y n respectivamente, hacer Trabajo = Disponible y final ( i ) = falso para i = 1,...n

1).- Encuentre una i tal que final ( i ) de i = falso y Necesidades ( i ) <= Trabajo si no existe ir al punto tres.

2).- Trabajo = Trabajo + Asignación ( i ), Final ( i ) = verdad ir al paso uno.

3).- Si final ( i) = verdad para toda i entonces el sistema esta en estado seguro de lo contrario esta en estado inseguro.

Secuenciabilidad

Los archivos secuenciales son un tipo de archivo en los que la información puede leerse y escribirse empezando desde el principio del archivo.
Debemos tomar en consideración algunas características que deben tener los archivos secuenciales:

1. La escritura de nuevos datos siempre se hace al final del archivo.

2. Para leer una zona concreta del archivo hay que avanzar siempre, si la zona está antes de la zona actual de lectura, será necesario "rebobinar" el archivo.

3. Los ficheros sólo se pueden abrir para lectura o para escritura, nunca de los dos modos a la vez.

Archivos Secuenciales

Se refiere al procesamiento de los registros, no importa el orden en que se haga, para eso los registros están organizados en forma de una lista y recuperarlos y procesarlos uno por uno de principio a fin.

Rendimientos de los archivos Secuenciales; dependiendo del dispositivo de almacenamiento utilizado el archivo se puede mostrar el usuario como si fuera un sistema secuencial.

Al finalizar un archivo secuencial se denota con una marca de fin de archivo. (End end-of-file)

Seriabilidad: Cuando hablamos de seriabilidad nos referimos a la capacidad de reproducir un producto x en número limitado de veces.

TEORÍA DE SERIABILIDAD

Una forma de evitar los problemas de interferencia es no permitir que las transacciones se intercalen. Una ejecución en la cual ninguna de dos transacciones se intercala se conoce como serial. Para ser más precisos, una ejecución se dice que es serial si, para todo par de transacciones, todas las operaciones de una transacción se ejecutan antes de cualquier operación de la otra transacción. Desde el punto de vista del usuario, en una ejecución serial se ve como si las transacciones fueran operaciones que el DBS procesa atómicamente. Las transacciones seriales son correctas dado que cada transacción es correcta individualmente, y las transacciones que se ejecutan serialmente no pueden interferir con otra.

Si el DBS procesara transacciones serialmente, significaría que no podría ejecutar transacciones concurrentemente, si entendemos concurrencia como ejecuciones intercaladas. Sin dicha concurrencia, el sistema usaría sus recursos en un nivel relativamente pobre y podría ser sumamente ineficiente.

Una solución puede ser ampliar el rango de ejecuciones permisibles para incluir aquellas que tienen los mismos efectos que las seriales. Dichas ejecuciones se conocen como serializables. Entonces, una ejecución es serializable si produce el mismo resultado y tiene el mismo efecto sobre la base de datos que alguna ejecución serial de las mismas transacciones. Puesto que las transacciones seriales son correctas, y dado que cada ejecución serializable tiene el mismo efecto que una ejecución serial, las ejecuciones serializables también son correctas.

Las ejecuciones que ilustran la actualización perdida y el análisis inconsistente no son serializables. Por ejemplo, ejecutando las dos transacciones de Depositar serialmente, en cualquier orden, da un resultado diferente al de la ejecución intercalada que pierde una actualización, por lo tanto, la ejecución intercalada no es serializable. Similarmente, la ejecución intercalada de Transferir e Imprimir Suma tiene un efecto diferente a los de cada ejecución serial de las dos transacciones, y por ello no es serializable.

Aunque éstas dos ejecuciones intercaladas no son serializables, muchas otras sí lo son. Por ejemplo, consideremos la siguiente ejecución intercalada de Transferir e Imprimir Suma. Esta ejecución tiene el mismo efecto que la ejecución serial de Transferir seguida de Imprimir Suma por lo tanto es serializable.

Leer₄ (Cuentas [8])    devuelve el valor de US$200
Escribir₄ (Cuentas [8], US$100)
Leer₃ (Cuentas [8])    devuelve el valor de US$100
Leer₄ (Cuentas [9])    devuelve el valor de US$200$
Escribir₄ (Cuentas [9], US$300)
Commit₄
Leer₃ (Cuentas [9])    devuelve el valor de US$300
Commit₃

La teoría de seriabilidad es una herramienta matemática que permite probar si un sincronizador trabaja o no correctamente. Desde el punto de vista de la teoría de seriabilidad, una transacción es una representación de una ejecución de operaciones de lectura y escritura y que indica el orden en el que se deben ejecutar estas operaciones. Además, la transacción contiene un Commit o un Abort como la última operación para indicar si la ejecución que representa terminó con éxito o no. Por ejemplo, la ejecución del siguiente programa.

Procedure P

begin

Start;
temp := Leer(x);
temp := temp + 1;
Escribir(x, temp);
Commit;

end

Puede ser presentado como r₁[x] -› w₁[x] -› c₁. Los subíndices identifican esta transacción particular y la distinguen de cualquier otra transacción que acceda al mismo dato. En general, usaremos r₁[x] (o w₁[x] para denotar la ejecución de Leer (o Escribir) ejecutado por la transacción T₁ sobre el dato x.

Cuando se ejecuta concurrentemente un conjunto de transacciones, sus operaciones deben estar intercaladas. La manera de modelar esto es usando una estructura llamada historia. Una historia indica el orden en el que se deben ejecutar las operaciones de las transacciones en relación a otras. Si una transacción T_iespecifica el orden de dos de sus operaciones, estas dos operaciones deben aparecer en ese mismo orden en cualquier historia que incluya a T_i. Además, es necesario que una historia especifique el orden de todas las operaciones conflictivas que aparezcan en ella.

Se dice que dos operaciones están en conflicto si ambas operan sobre el mismo dato y al menos una de ellas es una operación de escritura (Escribir). Por lo tanto, Leer(x) está en conflicto con Escribir(x), mientras que Escribir(x) está en conflicto tanto con Leer(x) como con Escribir(x). Si dos operaciones están en conflicto, es muy importante su orden de ejecución. Consideremos las siguientes transacciones

T₁ = r₁[x] -› w₁[x] -› c₁
T₃ = r₃[x] -› w₃[y] -› w₃[x] -› c₃
T₄ = r₄[y] -› w₄[x] -› w₄[y] -› w₄[z] -› c₄

Una historia completa sobre T₁, T₃, T₄ es

H₁ = r₄[y] r₁[x] w₁[x] c₁ w₄[x] r₃[x] w₄[y] w₃[y] w₄[z] w₃[x] c₄ c₃

Pages

Sistemas operativos

domingo, 1 de octubre de 2017

2.6 Técnicas de administración del planificador

Planificación a plazo fijo.

Planificación Primero en llegar - Primero en Salir (FIFO).

**Planificación por Prioridad al más corto (SJF, Short Job First)**.

**Planificación por Prioridad al Tiempo Restante más Corto (SRTF, Short Remaining Time First)**.

Planificación el Siguiente con Relación de Respuesta Máxima (HRN)

Planificación del tiempo restante más corto primero (SRT).

Planificación el siguiente con relación de respuesta máxima (HRT).

Planificación Round Robin (RR)

Tamaño del Cuanto o Quantum

Queves multi-level

Multi-level feedback queves.

Planificación a la Tasa de Respuesta mas Alta

Planificación por el Comportamiento

2.5 Niveles, objetivos y criterios de planificación

2.4 Concurrencia y secuenciabilidad

Exclusión mutua de secciones criticas

Sincronización de procesos en Sección Crítica

Mecanismo de semáforos

Mecanismo de Monitores

Interbloqueo (DeadLock)

Prevención

Detección

Recuperación

Secuenciabilidad

Temas

Entradas populares

Blog Archive

Followers

Denunciar abuso

Datos personales

Pages

Sistemas operativos

domingo, 1 de octubre de 2017

2.6 Técnicas de administración del planificador

Planificación a plazo fijo.

Planificación Primero en llegar - Primero en Salir (FIFO).

Planificación por Prioridad al más corto (SJF, Short Job First).

Planificación por Prioridad al Tiempo Restante más Corto (SRTF, Short Remaining Time First).

Planificación el Siguiente con Relación de Respuesta Máxima (HRN)

Planificación del tiempo restante más corto primero (SRT).

Planificación el siguiente con relación de respuesta máxima (HRT).

Planificación Round Robin (RR)

Tamaño del Cuanto o Quantum

Queves multi-level

Multi-level feedback queves.

Planificación a la Tasa de Respuesta mas Alta

Planificación por el Comportamiento

2.5 Niveles, objetivos y criterios de planificación

2.4 Concurrencia y secuenciabilidad

Exclusión mutua de secciones criticas

Sincronización de procesos en Sección Crítica

Mecanismo de semáforos

Mecanismo de Monitores

Interbloqueo (DeadLock)

Prevención

Detección

Recuperación

Secuenciabilidad

Temas

Entradas populares

Blog Archive

Followers

Denunciar abuso

Datos personales

**Planificación por Prioridad al más corto (SJF, Short Job First)**.

**Planificación por Prioridad al Tiempo Restante más Corto (SRTF, Short Remaining Time First)**.