ALGORITMOS DE PLANIFICACION

Planificación de Plazo Fijo

 

 

 PLANIFICACION DE PLAZO FIJO

En la planificación de plazo fijo se programan ciertos trabajos para terminarse en un tiempo específico o plazo fijo. Estas tareas pueden tener un gran valor si se entregan a tiempo, y carecer de él si se entregan después del plazo. Esta planificación es compleja por varios motivos:

El usuario debe informar por adelantado de las necesidades precisas de recursos del proceso. Semejante información rara vez está disponible.

 El sistema debe ejecutar el proceso en un plazo fijo sin degradar demasiado el servicio a los otros usuarios y debe planificar cuidadosamente sus necesidades de recursos dentro del plazo. Esto puede ser difícil por la llegada de nuevos procesos que impongan demandas imprevistas al sistema.

 Si hay muchas tareas a plazo fijo activas al mismo tiempo, la planificación puede ser tan compleja que se necesiten métodos de optimización avanzados para cumplir los plazos.

 La administración intensiva de recursos requerida por la planificación de plazo fijo puede producir un gasto extra substancial.

Planificación Primero en Entrar-Primero en Salir (FIFO, First In First Out)

 

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

 

La ventaja de este algoritmo es su fácil implementación, sin embargo, no es válido para entornos interactivos ya que un proceso de mucho cálculo de CPU hace aumentar el tiempo de espera de los demás procesos . Para implementar el algoritmo (ver figura 2) sólo se necesita mantener una cola con los procesos listos ordenada por tiempo de llegada. Cuando un proceso pasa de bloqueado a listo se sitúa el último de la cola.

En a) el proceso P7 ocupa la CPU, los procesos P2, P4 y P8 se mantienen en la lista de preparados. En b) P7 se bloquea (ya sea al realizar una E/S, una operación WAIT sobre un semáforo a cero u otra causa) y P2 pasa a ocupar la CPU. En c) ocurre un evento (finalización de la operación de E/S, operación SIGNAL, …) que desbloquea a P7, esto lo vuelve listo, pasando al final de la cola de procesos listos.

 Algunas de las características de este algoritmo es que es no apropiativo y justo en el sentido formal, aunque injusto en el sentido de que: los trabajos largos hacen esperar a los cortos y los trabajos sin importancia hacen esperar a los importantes. Por otro lado es predecible pero no garantiza buenos tiempos de respuesta y por ello se emplea como esquema secundario.

Planficación por Turno Rotatorio (Round Robin).

 

Este es uno de los algoritmos más antiguos, sencillos y equitativos en el reparto de la CPU entre los procesos, muy válido para entornos de tiempo compartido. Cada proceso tiene asignado un intervalo de tiempo de ejecución, llamado cuantum o cuanto. Si el proceso agota su cuantum de tiempo, se elige a otro proceso para ocupar la CPU. Si el proceso se bloquea o termina antes de agotar su cuantum también se alterna el uso de la CPU. El round robin es muy fácil de implementar. Todo lo que necesita el planificador es mantener una lista de los procesos listos, como se muestra en la figura 6.2.

 

En esta figura en a) el proceso P7 ocupa la CPU. En b) P7 se bloquea pasando P2 a ocupar la CPU. En c) P2 agota su cuantum con lo que pasa al final de la lista y P4 ocupa la CPU. La figura 4 representa un ejemplo más largo de la ocupación de la CPU utilizando el algoritmo round robin.

 

Este algoritmo presupone la existencia de un reloj en el sistema. Un reloj es un dispositivo que genera periódicamente interrupciones. Esto es muy importante, pues garantiza que el sistema operativo (en concreto la rutina de servicio de interrupción del reloj) coge el mando de la CPU periódicamente. El cuantum de un proceso equivale a un número fijo de pulsos o ciclos de reloj. Al ocurrir una interrupción de reloj que coincide con la agtación del cuantum se llama al dispatcher.

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

 Planificación a la Tasa de Respuesta más Alta
Brinch Hansen desarrolló la estrategia de prioridad a la tasa de respueta más alta (HRN, highest-response-ratio-next) que corrige alguas 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 prioridades dinámicas en HRN se calculan de acuerdo con la siguiente expresión:
Al igual que en el algoritmo FIFO las ráfagas se ejecutan sin interrupción, por tanto, sólo es útil para entornos batch. Su característica es que cuando se activa el planificador, éste elige la ráfaga de menor duración. Es decir, introduce una noción de prioridad entre ráfagas. Hay que recordar que en los entornos batch se pueden hacer estimaciones del tiempo de ejecución de los procesos.
 

  La ventaja que presenta este algoritmo sobre el algoritmo FIFO es que minimiza el tiempo de finalización promedio, como puede verse en el siguiente ejemplo:

Ej
: Supongamos que en un momento dado existen tres ráfagas listos R1, R2 y R3, sus tiempos de ejecución respectivos son 24, 3 y 3 ms. El proceso al que pertenece la ráfaga R1 es la que lleva más tiempo ejecutable, seguido del proceso al que pertenece R2 y del de R3. Veamos el tiempo medio de finalización (F) de las ráfagas aplicando FIFO y SJF:
 

 

  FIFO F = (24 + 27 + 30) / 3 = 27 ms.

  SJF F = (3 + 6 + 30) / 3 = 13 ms.

 

Se puede demostrar que este algoritmo es el óptimo. Para ello, consideremos el caso de cuatro ráfagas, con tiempos de ejecución de a, b, c y d. La primera ráfaga termina en el tiempo a, la segunda termina en el tiempo a+b, etc. El tiempo promedio de finalización es (4a+3b+2c+d)/4. Es evidente que a contribuye más al promedio que los demás tiempos, por lo que debe ser la ráfaga más corta, b la siguiente, y así sucesivamente. El mismo razonamiento se aplica a un número arbitrario de ráfagas.

 No obstante, este algoritmo sólo es óptimo cuando se tienen simultáneamente todas las ráfagas. Como contraejemplo, considérense cinco ráfagas desde A hasta E, con tiempo se ejecución de 2, 4, 1, 1 y 1 respectivamente. Sus tiempos de llegada son 0, 0, 3, 3 y 3. Primero se dispone de A y B, puesto que las demás ráfagas no han llegado aún. Con el algoritmo SJF las ejecutaríamos en orden A, B, C, D, y E con un tiempo de finalización promedio de 4.6. Sin embargo, al ejecutarlas en orden B, C, D, E y A se tiene un promedio de finalización de 4.4.

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

Es similar al anterior, con la diferencia de que si un nuevo proceso pasa a listo se activa el dispatcher para ver si es más corto que lo que queda por ejecutar del proceso en ejecución. Si es así el proceso en ejecución pasa a listo y su tiempo de estimación se decrementa con el tiempo que ha estado ejecutándose.

 

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.

 

 

  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.

 

 3.6.8 Planificación por el Comportamieno
 
 

 

 

 

 

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.

 

En sistemas de tiempo real se puede adoptar una variante de este algoritmo en el que se otorgue mayor prioridad al proceso cuyo riesgo de no cumplir el plazo sea mayor.

 

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.

Procesos ligeros

Los procesos ligeros son programas en ejecución son básicamente procesos pero a diferencia de éstos últimos que solo tienen un hilo de ejecución los primeros tienen el hilo principal más hilos secundarios o hijos, en éste caso todos los procesos hijos comparten la información del hilo principal pero además puede cada hilo tener su información privada.

Dentro de la información propia tenemos:

  • Contador de programa
  • Pila
  • Registros.
  • Estado del proceso ligero.
  • Dentro de la información compartida tenemos:
  • Variables globales.
  • Archivos abiertos
  • Señales
  • Semáforos.
  • Contabilidad.
About these ads

Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

A %d blogueros les gusta esto: