2.6.5 MultiLevel Feedback Queves

De acuerdo con Silbertschatz C. (1999) , el algoritmo de planificación mediante colas multinivel realimentadas permite mover un proceso de una cola a otra. La idea es separar los procesos en función de las características de sus ráfagas de CPU. Si un proceso utiliza demasiado tiempo de CPU, se pasa a una a de prioridad más baja. Este esquema deja los procesos limitados por E/S y los procesos interactivos en las colas de prioridad más alta. Además, un proceso que esté esperando demasiado tiempo en una cola de baja prioridad puede pasarse a una cola de prioridad más alta. Este mecanismo de envejecimiento evita el bloqueo indefinido.

En el ejemplo que nos da Silbertschatz C. (1999), se considera un planificador de colas multinivel realimentadas con tres colas, numeradas de 0 a 2 (Figura 5.7). En primer lugar, el planificador ejecuta todos los procesos de la cola 0. Solo cuando la cola 0 este vacia ejecutara procesos de la cola 1. De forma similar, los procesos de la cola 2 solo se ejecutaran si las colas 0 y 1 estan vacias. Un proceso que llegue a la cola 1 desalojara a un proceso de la cola 2 y ese proceso de la cola 1 sera, a su vez, desalojado por un proceso que llegue a la cola 0.

Silbertschatz, C. (1999). Sistemas operativos (5ta ed.) (pp. 139-140) México: Pearson

2.6.4 QuevesMultilevel

En el concepto que nos da Silbertschatz C. (1999), un algoritmo de planificacion mediante colas multinivel divide la cola de procesos preparados en varias colas distintas . Los procesos se asignan permanentemente a una cola, generalmente en función de alguna propiedad del proceso, como por ejemplo el tamaño memoria, la prioridad del proceso o el tipo de proceso. Cada cola tiene su propio algoritmo de planificación. Por ejemplo, pueden emplearse colas distintas para los procesos de primer plano y de segundo plano. La cola de primer plano puede planificarse mediante un algoritmo por turnos, mientras que para la cola de segundo plano puede emplearse un algoritmo FCFS.

Silbertschatz, C. (1999). Sistemas operativos (5ta ed.) (pp. 138-139) México: Pearson

2.6.3 Rr

De acuerdo a Silbertschatz C. (1999), los procesos se despachan en “FIFO” y disponen de una cantidad limitada de tiempo de cpu, llamada “división de tiempo” o “cuanto”.

Según Silbertschatz C. (1999), cada proceso recibe una fracción de tiempo de procesamiento o quanto para su ejecución, de manera que cuando se está ejecutando y excede el tiempo que se le ha concedido, se genera una interrupción de reloj, mediante la cual la ejecución del proceso se detiene y se coloca al proceso al final de la cola de procesos ‘listos’ para su posterior ejecución, seleccionándose a continuación un nuevo proceso de la cola para su ejecución. Si un proceso finaliza su ejecución antes de que termine el tiempo que se le ha asignado, este cede el control, seleccionándose un nuevo proceso de la cola para su ejecución.

Silbertschatz, C. (1999). Sistemas operativos (5ta ed.) (pp. 135-138) México: Pearson

2.6.2 Sjf

Otro metodo de planificacion de la CPU es el algoritmo de planificacion con seleccion del trabajo mas corto (SJF, shortest job-first). Este algoritmo asocia con cada proceso la duracion de la siguiente ráfaga de CPU del proceso. Cuando la CPU esta disponible, se asigna al proceso que tiene la siguiente rafaga de CPU mas corta. Si las siguientes rafagas de CPU de dos procesos son iguales, se usa la planificación FCFS para romper el empate. Observe que un termino mas apropiado para este método de planificación seria el de algoritmo de la siguiente rafaga de CPU mas corta, ya que la planificacion depende de la duracion de la siguiente rafaga de CPU de un proceso, en lugar de depender de su duracion total. Usamos el termino SJF porque casi todo el mundo y gran parte de los libros de texto emplean este termino para referirse a este tipo de planificacion.

Silbertschatz, C. (1999). Sistemas operativos (5ta ed.) (pp. 130-133) México: Pearson

2.6.1 Fifo

De acuerdo a la definicion de Silbertschatz C. (1999). FIFO Guarda analogía con las personas que esperan en una cola y van siendo atendidas en el orden en que llegaron, es decir, que la primera persona que entra es la primera persona que sale.
Los procesos se despachan de acuerdo con su tiempo de llegada a la cola de procesos listos. Cuando un proceso tiene la CPU, se ejecuta hasta terminar. Es junto en el sentido formal, pero algo injusta en cuanto a que los trabajos largos hacen esperar a los cortos y los trabajos sin importancia hacen esperar a los importantes. Este es un algoritmo que no usa apropiación, y que consiste en atender a los procesos por estricto orden de llegada a la lista de procesos listos.

Las características principales de este algoritmo son las siguientes:

• No es apropiativa.

• Es justa, aunque los procesos largos hacen esperar mucho a los cortos.

• Es una politica predecible.

• El tiempo promedio de servicio es muy variable ya que esta en funcion del numero de procesos y la duracion promedio que tenga.

Silbertschatz, C. (1999). Sistemas operativos (5ta ed.) (pp. 129-130) México: Pearson

2.6 Técnicas Administración del Planificador

Según la definición de Silbertschatz C. (1999), el planificador es un componente funcional muy importante de los sistemas operativos multitarea y multiproceso, y es esencial en los sistemas operativos de tiempo real. Su función consiste en repartir el tiempo disponible de un microprocesador entre todos los procesos que están disponibles para su ejecución.

Silbertschatz, C. (1999). Sistemas operativos (5ta ed.) (pp. 129) México: Pearson

2.5 Niveles Objetivos Criterios Planificación

Basandonos en el concepto de Silbertschatz C. (1999), La planificación hace referencia a un conjunto de políticas y mecanismos incorporados al sistema operativo que gobiernan el orden en que se ejecutan los trabajos que deben ser cumplimentados por el sistema informático. Se consideran tres niveles importantes de planificación, los que se detallan a continuación:

• Planificación de alto nivel: Se encarga de llevar procesos de disco a memoria y viceversa. Seleccionando los trabajos que deben admitirse en el sistema.

• Planificación de nivel intermedio: En algunos casos, en especial cuando el sistema está sobrecargado, el planificador de nivel medio encuentra ventajoso retirar trabajos activos de la memoria para reducir el grado de multiprogramación, y por lo tanto, permitir que los trabajos se completen mas aprisa.

• Planificación de bajo nivel: Se encarga de pasar de un proceso a otro en memoria principal. Determinando a cuál proceso listo se le asignará el CPU cuando éste se encuentra disponible. O Determina a qué proceso listo se le asigna la CPU cuando esta queda disponible y asigna la cpu al mismo, es decir que “despacha” la CPU al proceso.

Objetivo de la Planificacion
Según Silbertschatz C. (1999), el objetivo principal de la planificacion es optimizar el rendimiento del sistema y proporcionar un buen servicio a todos los procesos que se encuentren en el. En general, la planificacion trata de cubrir los siguientes objetivos:

• Justicia. La planificacion debe ser lo mas justa posible con todos los procesos, sin favorecer a unos y perjudicar a otros.

• Maxima capacidad de ejecucion. Debe dar un servicio eficiente para que todos los trabajos se realicen lo mas rapidamente posible. Esto se puede lograr disminuyendo el numero de cambios de proceso.

• Maximo numero de usuarios interactivos. En los sistemas de tiempo compartido se tratara de que puedan estar trabajando el mayor numero de usuarios al mismo tiempo.

• Predecibilidad. La planificación debe realizarse de tal forma que en todo momento pueda saberse como será su ejecución.

• Minimización de la sobrecarga. La computadora debe tener poca sobrecarga ya que esta afecta directamente al rendimiento final del sistema: a menor sobrecarga mayor velocidad de proceso.

• Equilibrio en el uso de recursos. Para obtener un mayor rendimiento en el uso de los recursos y que estos estén ocupados equitativamente el mayor tiempo posible.

• Seguridad de las prioridades. Si un proceso tiene mayor prioridad que otro, este debe ejecutarse mas rápidamente.

• Evitar la postergación indefinida. Esto se logra aumentando la prioridad de un proceso mientras espere por un recurso. La prioridad llegara a ser tan alta que al proceso le será asignado el recurso que pidió.

Criterios de la planeación del procesador

• Equidad

• Eficacia

• Tiempo de respuesta

• Tiempo de regreso

• Rendimiento

Silbertschatz, C. (1999). Sistemas operativos (5ta ed.) (pp. 125-128) México: Pearson

2.4.3.3 Recuperacion Interbloqueo DeadLock

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

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

Milenkovic, M. (1994). Sistemas operativos. Concepto y diseño (2a ed.) (pp. 191-195) México: Mc Graw Hill

2.4.3.2 Deteccion Interbloqueo DeadLock

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

Algoritmo de detección del interbloqueo

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

Milenkovic, M. (1994). Sistemas operativos. Concepto y diseño (2a ed.) (pp. 187-191) México: Mc Graw Hill

2.4.3.1 Prevencion Interbloqueo DeadLock

De acuerdo Milenkovic, M. (1994), la estrategia básica de la prevención del interbloqueo consiste, a grandes rasgos, en diseñar su sistema de manera que esté excluida, a priori, la posibilidad de interbloqueo.

Milenkovic, M. (1994). menciona 2 tipos de métodos para prevenir el interbloqueo Los métodos indirectos que consisten en impedir la aparición de alguna de las tres condiciones necesarias para que se de el interbloqueo.

• Los métodos directos que consisten en evitar la aparición del círculo vicioso de espera.
  

Milenkovic, M. (1994) define la Exclusión mutua cuando: ningún recurso se puede asignar de forma exclusiva, no se producirá interbloqueo. Sin embargo, existen recursos para los que no es posible negar la condición de exclusión mutua. No obstante, es posible eliminar esta condición en algunos procesos.

Según Milenkovic, M. (1994), la retención y espera se orgina puede prevenirse exigiendo que todos los procesos soliciten todos los recursos que necesiten a un mismo tiempo y bloqueando el proceso hasta que todos los recursos puedan concederse simultáneamente

Milenkovic, M. (1994) escribe que la condición de no apropiación puede prevenirse de varias formas. Primero, si a un proceso que retiene ciertos recursos se le deniega una nueva solicitud, dicho proceso deberá liberar sus recursos anteriores y solicitarlos de nuevo, cuando sea necesario, junto con el recurso adicional. Por otra parte, si un proceso solicita un recurso que actualmente está retenido por otro proceso, el sistema operativo debe expulsar al segundo proceso y exigirle que libere sus recursos.

Milenkovic, M. (1994). Sistemas operativos. Concepto y diseño (2a ed.) (pp. 184-185) México: Mc Graw Hill

2.4.3 Interbloqueo DeadLock

De acuerdo al concepto de Milenkovic, M. (1994), un interbloqueo se produce cuando dos o más tareas se bloquean entre sí permanentemente teniendo cada tarea un bloqueo en un recurso que las otras tareas intentan bloquear.

Milenkovic, M. (1994), define el estancamiento como: "Un conjunto de procesos se estancan si cada proceso del conjunto está esperando un evento que solo otro proceso del conjunto puede provocar". Puesto que todos los procesos están en espera, ninguno de ellos podrá ocasionar nuca ninguno de los eventos que podrían desbloquear a algunos de los otros miembros del conjunto y todos los procesos seguirán esperando indefinidamente.

Milenkovic, M. (1994). Sistemas operativos. Concepto y diseño (2a ed.) (pp. 180-183) México: Mc Graw Hill

2.4.2.2 Mecanismo de Monitores

De acuerdo a Tanenbaum A. (1998), monitor es un proceso que se encarga de verificar el funcionamiento de algún recurso garantizando la exclusión mutua) (mutex). En un monitor los procesos se bloquean y desbloquean.

Tanenbaum, A. (1998). Sistemas operativos. Diseño e Implementación (1a ed.) (pp.67-70)
México: Pretince-Hall

2.4.2.1 Mecanismo de Semáforos

En 1965, E.W. Dijkstra sugirió el uso de una variable entera para contar el número de despertares almacenados para su uso posterior.

En su propuesta se presentó un nuevo tipo de variable, llamada Semáforo. Un semáforo puede tener el valor 0, lo que indica que no existen despertares almacenados; o bien algún valor positivo si están pendientes uno o más despertares.

Dijkstra, propuso dos operaciones, DOWN y UP (generalizaciones de SLEEP y WAKEUP, respectivamente). La operación Down verifica si el valor de un semáforo es mayor que 0. En este caso, decrementa el valor (es decir, utiliza un despertar almacenado) y continúa. Si el valor es cero, el proceso se va a dormir. La verificación y modificación del valor, así como la posibilidad de irse a dormir se realiza en conjunto, como una sola e indivisible acción atómica. Se garantiza que al iniciar una operación con un semáforo, ningún otro proceso puede tener acceso a semáforo hasta que la operación termine o se bloquee. Esta atomicidad es absolutamente esencial para resolver los problemas de sincronización y evitar condiciones de competencia.

2.4.2 Sincronización de Procesos en SO

Milenkovic, M. (1994) menciona que en muchos casos, los procesos se reúnen para realizar tareas en conjunto, a este tipo de relación se le llama procesos cooperativos. Para lograr la comunicación, los procesos deben sincronizarse, de no ser así pueden ocurrir problemas no deseados. La sincronización es la coordinación y cooperación de un conjunto de procesos para asegurar la comparación de recursos de cómputo. La sincronización entre procesos también permite intercambiar señales de tiempo (ARRANQUE/PARADA) entre procesos cooperantes para garantizar las relaciones específicas de precedencia impuestas por el problema que se resuelve.

Milenkovic, M. (1994) sugiere que para que los procesos puedan sincronizarse es necesario disponer de servicios que permitan bloquear o suspender bajo determinadas circunstancias la ejecución de un proceso. Los principales mecanismos de sincronización que ofrecen los sistemas operativos son:

• Señales

• Tuberías

• Semáforos

• Mutex y variables condicionales

• Paso de mensajes

Milenkovic, M. (1994). Sistemas operativos. Concepto y diseño (2a ed.) (pp. 39-40) México: Mc Graw Hill

2.4.1 Exclusión Mutua Secciones Criticas

Segun la descripcion de Tanenbaum, A. (1998) , secciones críticas son a aquellas partes de los procesos concurrentes que no pueden ejecutarse de forma concurrente o, también, que desde otro proceso se ven como si fueran una única instrucción. Las secciones críticas se pueden agrupar en clases, siendo mutuamente exclusivas las secciones criticas de cada clase. Para conseguir dicha exclusión se deben implementar protocolos software que impidan o bloqueen (lock) el acceso a una sección critica mientras está siendo utilizada por un proceso.

Tanenbaum, A. (1998). Sistemas operativos. Diseño e Implementación (1a ed.) (pp. 56-62) México: Pretince-Hall

2.4 Concurrencia y Secuenciabilidad

Basandonos en la investigacion de Tanenbaum, A. (1998) los procesos son concurrentes si existen simultáneamente. Cuando dos o más procesos llegan al mismo tiempo a ejecutarse, se dice que se ha presentado una concurrencia de procesos. Es importante mencionar que para que dos o más procesos sean concurrentes, es necesario que tengan alguna relación entre ellos.

Tanenbaum, A. (1998) plantea que existen tres formas modelos de computadora en los que se puede pueden ejecutar procesos concurrentes:

Multiprogramación con un único procesador: En este modelo todos los procesos concurrentes ejecutan sobre un único procesador. El sistema operativo se encarga de ir repartiendo el tiempo del procesador entre los distintos procesos, intercalando la ejecución de los mismos para dar así una apariencia de ejecución simultanea.

Multiprocesador:Un multiprocesador es una maquina formada por un conjunto de procesadores que comparten memoria principal. En este caso si existe una verdadera ejecución simultanea de procesos, al coincidir las fases de procesamiento de distintos procesos. En un instante dado se pueden ejecutar de forma simultánea tantos procesos como procesadores haya.

Tanenbaum, A. (1998). Sistemas operativos. Diseño e Implementación (1a ed.) (pp. 54-55) México: Pretince-Hall

2.3 Procesos Ligeros Hilos o hebras

Silbertschatz, C. (1999) menciona que un thread (Hilo) es un flujo de control perteneciente a un proceso (a veces se habla de tareas con threads). Es la unidad básica de ejecución de OS/2. Cualquier programa que se ejecute consta de, al menos, un thread. Se les suele denominar también procesos ligeros, hebras, hilos, etc.

Características:

• La sobrecarga debida a su creación y comunicación es menor que en los procesos pesados

• Cada hilo pertenece a un proceso pesado

• Todos los hilos comparten su espacio de direccionamiento

• Cada hilo dispone de su propia política de planificación, pila y contador de programa

Silbertschatz, C. (1999). Sistemas operativos (5ta ed.) (pp. 102-106) México: Pearson

2.2 Estados y Transiciones de procesos

Segun Silbertschatz, C. (1999), "el estado de un proceso define su actividad actual. Durante su existencia, un proceso pasa por una serie de estados discretos. Estos estados son se muestran en el siguiente diagrama":

Nuevo: Se dice que un proceso está en estado de nuevo cuando apenas se encuentra en proceso de crearse.

Listo: Un proceso está en estado de listo, cuando podría usar una CPU, si hubiera una disponible.

En ejecución: Se dice que un proceso está estado de ejecución, si en ese momento tiene esta ocupando la CPU.

Bloqueado: Se dice que un proceso está en estado de bloqueado, si espera que ocurra algo, como por ejemplo, la terminación de una E/S, para así poder ponerse en marcha.

Terminado: Cuando un proceso se ha completado su ejecución pasa a ser un proceso terminado.

De acuerdo a Silbertschatz, C. (1999) "cuando un trabajo es admitido se crea un proceso equivalente, y es insertado en la última parte de la cola de listos (ésta se tratara más adelante). Cuando un proceso pasa de un estado a otro se dice que hace una transición de estado, estas transiciones se describen a continuación".

Admitido(Proceso):Nuevo Listo: Cuando un proceso se ha creado y se le es permito para competir por la CPU.

Despacho(Proceso):Listo En ejecución: La asignación de la CPU al primer proceso de la lista de listos es llamado despacho y es ejecutado por la entidad de sistema llamada despachador. Mientras que el proceso tenga la CPU se dice que esta en ejecución.

Tiempo excedido(Proceso):En ejecución Listo: El S.O , cuando un proceso se le expira el intervalo de tiempo asignado para estar en ejecución (CUANTO), hace que este proceso que se hallaba en estado de ejecución pase al estado de listo y inmediatamente el despachador hace que el primer proceso de la lista pase a estado de ejecución.

Bloqueo(Proceso):En ejecución Bloqueado: Si un proceso que se encuentra en estado de ejecución inicia una operación de E/s antes que termine su cuanto, el proceso voluntariamente abandona la CPU, es decir, el proceso se bloquea a sí mismo.

Despertar(Proceso):Bloqueo Listo: La única transición posible en nuestro modelo básico ocurre cuando acaba una operación de E/S (o alguna otra causa por la que esté esperando el proceso), y esta termina pasa a el estado de listo.

Salir(Proceso):En ejecución Terminado: Esta transición ocurre cuando el proceso se ha terminado de ejecutarse, y pasa a un estado de terminado.

Silbertschatz, C. (1999). Sistemas operativos (5ta ed.) (pp. 91-92) México: Pearson

2.1 Concepto de Proceso

Silbertschatz, C. (1999) dijo que "Un proceso es un programa en ejecución, que se ejecuta secuencialmente (no más de una instrucción a la vez)".

Segun con Silbertschatz, C. (1999), un programa es una secuencia de instrucciones escrita en un lenguaje dado. Un proceso es una instancia de ejecución de un programa, caracterizado por su contador de programa, su palabra de estado, sus registros del procesador, su segmento de texto, pila y datos, etc. Un programa es un concepto estático, mientras que un proceso es un concepto dinámico. Es posible que un programa sea ejecutado por varios usuarios en un sistema multiusuario, por cada una de estas ejecuciones existirá un proceso, con su contador de programa, registros, etc.

Silbertschatz, C. (1999). Sistemas operativos (5ta ed.) (pp. 89-90) México: Pearson