2.6.5 Multi-level feedback queves.

Colas de Retroalimentación de Niveles Múltiples
Proporcionan una estructura para lograr los siguientes objetivos:

• Favorecer trabajos cortos.
• Favorecer trabajos limitados por la Entrada / Salida para optimizar el uso de los dispositivos de Entrada / Salida.
• Determinar la naturaleza de un trabajo lo más rápido posible y planificar el trabajo (proceso) en consecuencia.

Un nuevo proceso entra en la red de línea de espera al final de la cola superior.

Se mueve por esta cola “FIFO” hasta obtener la cpu.
Si el trabajo termina o abandona la cpu para esperar por la terminación de una operación de Entrada / Salida o la terminación de algún otro suceso, el trabajo abandona la red de línea de espera.
Si su cuanto expira antes de abandonar la cpu voluntariamente, el proceso se coloca en la parte trasera de la cola del siguiente nivel inferior.
El trabajo recibe servicio al llegar a la cabeza de esta cola si la primera está vacía.
Mientras el proceso continúe consumiendo totalmente su cuanto en cada nivel, continuará moviéndose hacia el final de las colas inferiores.
Generalmente hay una cola en la parte más profunda a través de la cual el proceso circula en asignación de rueda hasta que termina.
Existen esquemas en los que el cuanto otorgado al proceso aumenta a medida que el proceso se mueve hacia las colas de los niveles inferiores, en tal caso, cuanto más tiempo haya estado el proceso en la red de línea de espera, mayor será su cuanto cada vez que obtiene la cpu y no podrá obtener la cpu muy a menudo debido a la mayor prioridad de los procesos de las colas superiores.
Un proceso situado en una cola dada no podrá ser ejecutado hasta que las colas de los niveles superiores estén vacías.
Un proceso en ejecución es apropiado por un proceso que llegue a una cola superior.
Es un mecanismo adaptable, es decir que se adapta a cargas variables.
A los efectos de una revisión gráfica de lo enunciado precedentemente.

2.6.4 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:

1. Se carga en la memoria principal cierto subconjunto de los procesos ejecutables.
2. El planificador se restringe a ellos durante cierto tiempo.
3. Periódicamente se llama a un planificador de nivel superior para efectuar las siguientes tareas:
1. Eliminar de la memoria los procesos que hayan permanecido en ella el tiempo suficiente.
2. Cargar a memoria los procesos que hayan estado en disco demasiado tiempo.
4. El planificador de nivel inferior se restringe de nuevo a los procesos ejecutables que se encuentren en la memoria.
5. 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.

2.6.3 RR

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.

SCHED_RR: Planificación circular (Round Robin).

SCHED_RR es una mejora simple de SCHED_FIFO. Todo lo descrito arriba para SCHED_FIFO se aplica también a SCHED_RR, excepto que a cada proceso sólo se le permite ejecutarse durante un cuanto de tiempo máximo. Si un proceso SCHED_RR ha estado ejecutándose durante un periodo de tiempo igual o mayor que el cuanto de tiempo, será puesto al final de la lista para su prioridad. Un proceso SCHED_RR que ha sido apropiado por un proceso de más alta prioridad y subsecuentemente reanuda su ejecución como un proceso en ejecución, completará la porción no expirada de su cuanto de tiempo de asignación en rueda. La cantidad del cuanto de tiempo puede ser obtenida con sched_rr_get_interval.

Planificación de Asignación en Rueda (RR: Round Robin)
Los procesos se despachan en “FIFO” y disponen de una cantidad limitada de tiempo de cpu, llamada “división de tiempo” o “cuanto”.
Si un proceso no termina antes de expirar su tiempo de cpu ocurren las siguientes acciones:

1. La cpu es apropiada.
2. La cpu es otorgada al siguiente proceso en espera.
3. El proceso apropiado es situado al final de la lista de listos.

Es efectiva en ambientes de tiempo compartido.

La sobrecarga de la apropiación se mantiene baja mediante mecanismos eficientes de intercambio de contexto y con suficiente memoria principal para los procesos.
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 [7, Deitel].
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).

2.6.2 SJF

Planificación del trabajo más corto (SJF).

            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.

Planificación del Trabajo Más Corto Primero (SJF)
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 del Tiempo Restante Más Corto (SRT)
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_r es 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

Tiempo de espera  +  Tiempo de servicio

        Prioridad  = 

Tiempo de servicio

2.6.1 FIFO

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.

Planificación primero en llegar primero en salir.

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.

FIFO (Firs In First Out).-
Asocia a cada página el tiempo en que fue cargada en memoria. Cuando debe reemplazar una página, se selecciona la que hace mas tiempo que esta en memoria. 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.
Planificación del Primero en Entrar Primero en Salir (FIFO)
Es muy simple, los procesos se despachan de acuerdo con su tiempo de llegada a la cola de listos.
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”.

SCHED_FIFO: Planificación FIFO (1º en entrar, 1º en salir).

SCHED_FIFO sólo puede emplearse con prioridades estáticas mayores que 0, lo que significa que cuando un proceso SCHED_FIFO se convierte en ejecutable, siempre prevalecerá inmediatamente sobre cualquier otro proceso normal SCHED_OTHER ejecutándose. SCHED_FIFO es un simple algoritmo de planificación sin rodajas de tiempo. Para procesos planificados bajo la política SCHED_FIFO, se aplican las siguientes reglas: Un proceso SCHED_FIFO que ha sido apropiado por otro proceso de mayor prioridad permanecerá en la cabeza de la lista para su prioridad y reanudará su ejecución tan pronto como todos los procesos de prioridad más alta se bloqueen de nuevo. Cuando un proceso SCHED_FIFO llegue a ser ejecutable, se insertará al final de la lista para su prioridad. Una llamada a sched_setscheduler o a sched_setparam pondrá el proceso SCHED_FIFO identificado por pid al final de la lista si era ejecutable. Un proceso que llame a sched_yield será colocado al final de la lista. Ningún otro suceso moverá un proceso planificado bajo la política SCHED_FIFO en la lista de espera de procesos ejecutables con igual prioridad estática. Un proceso SCHED_FIFO se ejecuta hasta que es bloqueado por una petición de E/S, hasta que sea apropiado por un proceso de más alta prioridad, o hasta que llame a sched_yield.

2.6 Técnicas de administración del planificador

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.

2.5 Niveles, objetivos y criterios de planificación

Uno de los módulos más importantes de un sistema operativo es la de administrar los procesos y tareas del sistema de cómputo. En esta sección se revisarán dos temas que componen o conciernen a este módulo: la planificación del procesador y los problemas de concurrencia.
Planificación del procesador
La planificación del procesador se refiere a la manera o técnicas que se usan para decidir cuánto tiempo de ejecución y cuando se le asignan a cada proceso del sistema. Obviamente, si el sistema es monousuario y monotarea nohay mucho que decidir, pero en el resto de los sistemas esto es crucial para el buen funcionamiento del sistema.
Niveles de planificación
En los sistemas de planificación generalmente se identifican tres niveles: el alto, em medio y el bajo. El nivel alto decide que trabajos (conjunto de procesos) son candidatos a convertirse en procesos compitiendo por los recursos del sistema; el nivel intermedio decide que procesos se suspenden o reanudan para lograr ciertas metas de rendimiento mientras que el planificador de bajo nivel es el que decide que proceso, de los que ya están listos (y que en algún momento paso por los otros dos planificadores) es al que le toca ahora estar ejecutándose en la unidad central de procesamiento. En este trabajo se revisaran principalmente los planificadores de bajo nivel porque son los que finalmente eligen al proceso en ejecución.
Objetivos de la planificación
Una estrategia de planificación debe buscar que los procesos obtengan sus turnos de ejecución apropiadamente, conjuntamente con un buen rendimiento y minimización de la sobrecarga (overhead) del planificador mismo. En general, se buscan cinco objetivos principales:

·         Justicia o Imparcialidad: Todos los procesos son tratados de la misma forma, y en algún momento obtienen su turno de ejecución o intervalos de tiempo de ejecución hasta su terminación exitosa.

·         Maximizar la Producción: El sistema debe de finalizar el mayor numero de procesos en por unidad de tiempo.

·         Maximizar el Tiempo de Respuesta: Cada usuario o proceso debe observar que el sistema les responde consistentemente a sus requerimientos.

·         Evitar el aplazamiento indefinido: Los procesos deben terminar en un plazo finito de tiempo.

·         El sistema debe ser predecible: Ante cargas de trabajo ligeras el sistema debe responder rápido y con cargas pesadas debe ir degradándose paulatinamente. Otro punto de vista de esto es que si se ejecuta el mismo proceso en cargas similares de todo el sistema, la respuesta en todos los casos debe ser similar.

Características a considerar de los procesos

·         No todos los equipos de cómputo procesan el mismo tipo de trabajos, y un algoritmo de planificación que en un sistema funciona excelente puede dar un rendimiento pésimo en otro cuyos procesos tienen características diferentes. Estas características pueden ser:

·         Cantidad de Entrada/Salida: Existen procesos que realizan una gran cantidad de operaciones de entrada y salida (aplicaciones de bases de datos, por ejemplo).

·         Cantidad de Uso de CPU: Existen procesos que no realizan muchas operaciones de entrada y salida, sino que usan intensivamente la unidad central de procesamiento. Por ejemplo, operaciones con matrices.

·         Procesos de Lote o Interactivos: Un proceso de lote es más eficiente en cuanto a la lectura de datos, ya que generalmente lo hace de archivos, mientras que un programa interactivo espera mucho tiempo (no es lo mismo el tiempo de lectura de un archivo que la velocidad en que una persona teclea datos) por las respuestas de los usuarios.

·         Procesos en Tiempo Real: Si los procesos deben dar respuesta en tiempo real se requiere que tengan prioridad para los turnos de ejecución.

·         Longevidad de los Procesos: Existen procesos que tipicamente requeriran varias horas para finalizar su labor, mientras que existen otros que solonecesitan algunos segundos.

Planificación apropiativa o no apropiativa (preemptive or not preemptive)
La planificación apropiativa es aquella en la cual, una vez que a un proceso le toca su turno de ejecución ya no puede ser suspendido, ya no se le puede arrebatar la unidad central de procesamiento. Este esquema puede ser peligroso, ya que si el proceso contiene accidental o deliberadamente ciclos infinitos, el resto de los procesos pueden quedar aplazados indefinidamente. Una planificación no apropiativa es aquella en que existe un reloj que lanza interrupciones periodicas en las cuales el planificador toma el control y se decide si el mismo proceso seguirá ejecutándose o se le da su turno a otro proceso. Este mismo reloj puede servir para lanzar procesos manejados por el reloj del sistema. Por ejemplo en los sistemas UNIX existen los 'cronjobs' y 'atjobs', los cuales se programan en base a la hora, minuto, día del mes, día de la semana y día del año.

En una planificación no apropiativa, un trabajo muy grande aplaza mucho a uno pequeño, y si entra un proceso de alta prioridad esté también debe esperar a que termine el proceso actual en ejecución.

Planificación de procesos
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 que se describen más abajo.
Expulsión
Es la característica por el cual el sistema operativo puede o no expulsar del estado de ejecución a un proceso dado. En este sentido entonces tenemos la planificación apropiativa en la cual el sistema operativo puede cortar en cualquier momento la ejecución de un proceso y la planificación no apropiativa en la cual una vez que el proceso esta en ejecución el sistema operativo no puede sacarlo de ese estado.
Objetivos de la planificación
Los objetivos de la planificación de proceso son:

·         Equidad, todos los procesos deben poder ejecutarse

·         Eficacia, mantener ocupada la CPU un 100% del tiempo

·         Tiempo de respuesta, minimizar el tiempo de respuesta al usuario

·         Tiempo de regreso, minimizar el tiempo que deben esperar los usuarios por lotes para obtener sus resultados

·         Rendimiento, maximizar el número de tareas procesadas por hora.

Algoritmos de planificación
Los algoritmos de planificación son los que definen que política se va a seguir para que un proceso pase al estado de ejecución.
Planificación Round-Robin
En este tipo de planificación cada proceso tiene asignado un quantum de tiempo para ejecutarse y en el caso de que no pueda terminar la ejecución en su quantum el proceso pasa de nuevo a la cola de procesos para ser ejecutado por otro quantum luego de recorrer la cola para asegurarse que todos los procesos reciban ese quantum de procesamiento.
Planificación por prioridad
En la planificación round-robin todos los procesos son tratados con la misma prioridad. Para el caso de este tipo de planificación a cada proceso se le asigna una prioridad y los mismos son ejecutados
Colas múltiples
Las colas múltiples están basadas en una pila que sirve como índice de una lista de procesos que se tienen que ejecutar.
Primero el trabajo más corto
Este tipo de algoritmo de planificación se usa para trabajos en batch o de procesamiento or lotes en los cuales se puede saber cual es el tiempo de duración de la ejecución de cada proceso y entonces se puede seleccionar primero el trabajo más corto. El problema que se presenta con éste algoritmo es que los grandes procesos podrían sufrir de inanición dado que cualquier proceso pequeño se "cuela" sobre uno de mayor tamaño y como resultado final se podría dar el caso que el proceso grande nunca obtenga procesamiento.
Planificación garantizada
En este modelo de planificación se tiene en cuenta la cantidad de usuarios en el sistema y se le asigna a cada uno el tiempo de ejecución de 1/n (siendo n la cantidad total de usuarios) de esa forma el planificador tiene que llevar cuenta del tiempo de ejecución de los procesos y balancear el tiempo que están utilizando el procesador para cumplir con la ecuación previa.

Conceptos de planificación.

            El objetivo de la multiprogramación es que en todo momento se ejecute un proceso para maximizar la utilización del CPU. En un sistema monoprocesador nunca habrá  más de un proceso en ejecución. Si hay más procesos tendrán que esperar a que el CPU  esté libre y pueda volver a planificarse.

            El concepto de multiprogramación es muy sencillo: un proceso se ejecuta hasta que tenga que esperar, generalmente a que termine una solicitud de E/S. En un sistema de computo sencillo, el CPU permanecerá inactivo; todo este tiempo de espera se desperdicia sin efectuar una actividad útil. Con la multiprogramación tratamos de emplear productivamente este tiempo. Varios procesos se conservan en la memoria a la vez, y cuando uno de ellos tiene que esperar, el sistema operativo le quita el CPU al proceso y se lo da a otro; este modelo continúa, Cada vez que un proceso tiene que esperar, otro  pueda utilizar el CPU.

            Los beneficios de la multiprogramación son un aumento de la utilización del CPU y una mayor productividad.

Planificación del CPU

            La planificación es una función fundamental del sistema operativo. Casi todos los recursos de una computadora se planifican antes de usarse. Por supuesto, el CPU es una de los principales

            Recursos de la computadora, de modo que su planificación es parte modular del diseño de los sistemas operativos.

- Ciclo de ráfaga del CPU y de E/S.

            El éxito de la planificación del CPU depende de la siguiente prioridad observada de los procesos: la ejecución de un proceso consiste en un ciclo de ejecucióndel CPU y de E/S, y los procesos se alternan entre estos dos estados. La ejecución del proceso se inicia con una rafaga de CPU;  a ésta le siguen una ráfaga de E/S, otra ráfaga de CPU, una más de E/S, etc. Finalmente, la última ráfaga de CPU terminará con una solicitud al sistema para que concluya la ejecución, en vez de otra ráfaga de E/S.

            Las duraciones de estas ráfagas de CPU se han medido, y, aunque varían considerablemente de un proceso a otro y entre computadoras, Generalmente la curva se caracteriza como exponencial o hiperhexponencial. Hay un gran número de ráfagas de CPU de corta duración y un pequeño número de larga duración.

- Planificador del CPU.

            Siempre que el CPU queda inactivo, el sistema operativo debe seleccionar para su ejecución uno de sus procesos de la cola de procesos listos. El proceso de selección es revisado por el planificador a corto plazo. (o planificador del CPU). El planificador selecciona uno de los procesos en memoria que están listos para ejecución y le asigna el CPU.

- Estructura de planificación.

            Las decisiones de planificación del CPU pueden efectuarse en una de las cuatro circunstancias siguientes:

1.         Cuando un proceso cambia del estado de ejecución a estado de espera (por ejemplo, solicitud de E/S petición de esperar la terminación de uno de los procesos hijo).

2.         Cuando un proceso cambia del estado de ejecución al estado listo (por ejemplo, cuando ocurre una interrupción)

3.         Cuando un proceso cambia del estado de espera al estado listo (por ejemplo, al completarse la E/S).

4.         Cuando termina un proceso.

2.4.3 Interbloqueo (DeadLock)

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

1. EXCLUSION MUTUA: Por lo menos un proceso que tenga otorgado un recurso en forma exclusiva.
2. 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.
3. 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.
4. 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, sis 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 [Deitel93] 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.

Deadlock

• Un S.O. tiene un número limitado de recursos y procesos que solicitan los recursos.
• ¶Como diseñador de un sistema operativo, ¿cuál es el problema para ti si algunos procesos un tu sistema están en deadlock esperando recursos?
• Los recursos retenidos por los procesos en deadlock no están disponibles para otros procesos, y los procesos en deadlock no pueden avanzar (es mal para los dueños de los procesos).
• Muchos SS.OO. modernos no tienen apoyo especial para prevenir deadlock (porque cuesta), pero es común en programación de sistemas en general (e.g., en programación distribuida).

Características de deadlock

• El sistema tiene recursos de varios tipos: memoria, archivos, grabadores, impresoras, etc. Podemos tener más de un ejemplar de un tipo de recurso (e.g., tres impresoras). Cada uno de los ejemplares pueden satisfacer un solicitud de un proceso para el recurso.
• Los recursos son compartibles y permiten acceso a muchos procesos (e.g., los archivos de sólo lectura) o no compartibles (e.g., un grabador).
• Ejemplo: Tres procesos en un sistema con tres grabadores, cada proceso tiene un grabador y cada uno necesita uno más.
• Condiciones necesarias de deadlock:
• ¶ Exclusión mutua. Por lo menos un recurso debe retenerse no compartido. ¿Por qué?
• Retención y espera. Debe haber un proceso que retenga por lo menos un recurso y espere adquirir más recursos retenidos por otros.
• No apropiación. Los recursos no se pueden expropiar. Los procesos liberan recursos sólo voluntariamente.
• Espera circular. Debe haber un conjunto {P₀, P₁, ..., P_n} de procesos en espera tales que P₀ espere un recurso de P₁, P₁ un recurso de P₂, ..., y P_n un recurso de P₀.
• Podemos usar un grafo de asignación de recursos para describir deadlock. Tenemos procesos (círculos), recursos (rectángulos con un punto para cada ejemplar), aristas de solicitud y de asignación (cambio instantáneamente).
• Un grafo sin ciclos implica que no hay deadlock. Si hay un ciclo, es posible que exista deadlock. Un ciclo es una condición necesaria pero no suficiente para deadlock.

Análisis.

            Definición. Abraso Mortal (Dead lock) o también llamado ínter bloqueo. En un contexto de procesos concurrentes, si el análisis de recursos a compartir no se hace cuidadosamente, se puede tener el riesgo de que dos o más procesos acaparen algún recurso y que se pongan en espera de que otro u otros liberen los recursos para poder continuar su ejecución, de tal manera que cada proceso permanecerá en una espera indefinida (infinita), observe el ejemplo de la figura # 23 Ejemplo: Se tienen 2 procesos P1 y P2. Se tiene 2 recursos Impresora y Unidad de disco:

   Dead Lock.

            Cuando un proceso espera un evento que nunca se va a dar y el otro también lo espera Dead lock de un recurso simple.

            Muchos de los dead lock se deben a que un proceso retiene un recurso que debe ser usado en forma exclusiva. Es decir, el proceso tiene un recurso que sólo puede ser usado por un usuario a la vez. A estos recursos se les conoce como reutilizables en serie.

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 UCP, 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.