Algoritmos de Planificación

martes, 28 de agosto de 2012

Planificación por prioridad

En este algoritmo a cada proceso se le asocia un número entero de prioridad. Mientras menor sea este entero pues mayor prioridad tiene el proceso, por lo que la esencia del algoritmo es planificar la entrada de procesos a la CPU de acuerdo a la prioridad asociada de cada uno de ellos.

Un caso particular del algoritmo por prioridad es el SJF, donde el valor del próximo ciclo de CPU representa la prioridad. El algoritmo por prioridad corrige algunas deficiencias del SJF, particularmente el retraso excesivo de procesos largos y el favoritismo por procesos cortos.

Características.

Las ideas centrales son que cada proceso tiene asociada una prioridad y que el proceso ejecutable con máxima prioridad es el que tiene el permiso de ejecución.

Los procesos de alta prioridad podrían ejecutar indefinidamente, ya que el planificador del sistema puede disminuir la prioridad del proceso en ejecución en cada interrupción del reloj.

Las prioridades también pueden ser asignadas dinámicamente por el sistema para lograr ciertas metas relacionadas con el procesador o la Entrada / Salida.

Los procesos limitados por la Entrada / Salida (requerimientos intensivos de Entrada / Salida) ocupan mucho de su tiempo en espera de operaciones de Entrada / Salida, por lo tanto:

Deben tener prioridad para usar la cpu y efectuar la siguiente petición de Entrada / Salida, ya que se ejecutará (la operación de Entrada / Salida) en paralelo con otro proceso que utilice la cpu.

Si deben esperar mucho tiempo a la cpu estarán ocupando memoria por un tiempo innecesario.

En caso de empate se aplica el FIFO primero en llegar primero en salir.

Funcionamiento.

Un algoritmo sencillo consiste en establecer que la prioridad sea “1 / f”, donde “f” es la fracción del último cuanto utilizado por el proceso.

Un proceso que utilice 2 mseg (dos milisegundos) de su cuanto de 100 mseg (cien milisegundos) tendrá prioridad 50 (cincuenta).

Un proceso que se ejecutó 50 mseg antes del bloqueo tendrá prioridad 2.

Un proceso que utilizó todo el cuanto tendrá prioridad 1.

Frecuentemente los procesos se agrupan en “Clases de Prioridad”, en cuyo caso se utiliza la Planificación con Prioridades entre las clases y con Round Robin (RR) dentro de cada clase. Si las prioridades no se reajustan en algún momento, los procesos de las clases de prioridad mínima podrían demorarse indefinidamente.

Gabriel Renan Lasso Lara

ALGORITMOS DE PLANIFICACION ESTATICOS Y DINAMICOS

Algoritmos de Planiﬁcación estáticos y dinámicos

Los algoritmos de planiﬁcación pueden ser clasiﬁcados en estáticos y dinámicos . La planiﬁcación estática hace un cálculo previo del plan del sistema, requiere de conocimiento a-priori de las características de las tareas y tiene la ventaja de que se ejecuta con poca sobrecarga. La planiﬁcación dinámica, por otra parte, determina el plan en tiempo de ejecución permitiendo la implementación de sistemas más ﬂexibles que cuando se utiliza la planiﬁcación estática. La sobrecarga atribuible a la planiﬁcación dinámica es mayor pero consiguen una mayor utilización del procesador.

En un planiﬁcador estático todas las decisiones de planiﬁcación se llevan a cabo previo a la ejecución del sistema. Una tabla es generada con las decisiones de planiﬁcación que serán utilizadas durante la ejecución. Esta tabla contiene el plan estático que indica el instante de tiempo en que cada tarea debe ser ejecutada, de tal manera que el planiﬁcador sólo debe seguir las indicaciones de la tabla. Tan sólo es necesario almacenar las actividades del hiperperiodo del conjunto de tareas ya que estas se repetirán durante la ejecución del sistema. Como puede verse esta clase de algoritmos dependen del conocimiento a priori de las características y comportamiento de las tareas. La veriﬁcación de la planiﬁcabilidad utilizando planiﬁcación estática debe llevarse a cabo durante la construcción del plan. Por otra parte, este esquema funciona si todas las tareas son periódicas, por lo que no puede utilizarse para sistemas conformados con tareas esporádicas o aperiódicas.

El tamaño de la tabla es un inconveniente adicional ya que pudiera ser excesivamente grande. Además, están la escasa ﬂexibilidad y el que el problema deconstruir el plan estático sea NP-completo [46], lo que hace que la planiﬁcación estática muestre muchas desventajas a pesar de que algunos autores la consideren ventajosa.

Un planiﬁcador dinámico toma las decisiones durante la ejecución del sistema tomando en consideración las características de las tareas y el estado del sistema. Los planiﬁcadores dinámicos más utilizados son los basados en prioridades, mientras que las prioridades de las tareas a su vez pueden ser asignadas de manera ﬁja o dinámica. En la planiﬁcación dinámica se elige para ejecución a la tarea con función de prioridad mayor de entre las que estén activas. Cuando la prioridad es ﬁja, su valor se mantendrá igual con respecto al resto de tareas durante la vida del sistema. En el caso de las prioridades dinámica, el valor de la función de prioridad

Podrá variar en relación con el resto de tareas dependiendo de la carga del sistema en un instante determinado. La planiﬁcación dinámica ofrece muchas ventajas sobre la estática ya que es ﬂexible y permite la implementación de sistemas más complejos.

En el ámbito de la planiﬁcación dinámica con prioridades ﬁjas dos algoritmos tienen particular relevancia: prioridad a la tarea más frecuente (RM) y prioridad a la tarea más urgente (DM). El algoritmo RM asigna a cada tarea una prioridad inversamente proporcional a su periodo y asume que los plazos de las tareas son iguales a sus periodos. Para ejempliﬁcar el funcionamiento del algoritmo RM.se muestra el cronograma de ejecución de un sistema formado por tres tareas, utilizando el algoritmo de prioridad a la tarea más frecuente (RM). Las tareas tienen los siguientes parámetros:T1= (3, 1), T2= (5, 2) y T3= (8,1), en donde el primer parámetro de las tareas representa su periodo y el segúndo su tiempo de cómputo. Se supone que los plazos son iguales a los periodos y que todas las tareas son liberadas en el instante creo. De acuerdo a la política de planiﬁcación RM la tarea T1es la más prioritaria mientras que T3es la menos prioritaria. En el instante 5 es liberada la segunda instancia de T2 y al no existir alguna otra tarea activa en el sistema inicia su ejecución. Sin embargo, en el instante 6 la tarea T 1 es liberada y al tener una prioridad mayor que T 2 expulsa a esta del procesador T1 inicia su ejecución. Una vez que T1 concluye, T2 continúa su ejecución en el punto en la que fue suspendida.

Colas Multiples

Las colas múltiples son una solución a la prolemática que se presenta cuado en los sistemas operativos coexisten procesos con diferentes necesidades. Por ejemplo: pueden haber procesos interactivos, los cuales requieren una planificación de tiempo compartido adecuada, pero quizás haya que ejecutar también procesos de tiempo real, que no pueden estar sujetos a una expulsión por tiempo.

Por ello si fuera posible identificar en un sistema, clases diferenciadas de procesos (por ejemplo: tiempo real, interactivos, por lotes, …), se tendría interés en establecer una cola de listos para cada clase de procesos.

La política de planificación se basa en algún esquema predeterminado, que da un tratamiento especial a los trabajos de cada cola.

Para este algoritmo se requieren dos niveles de planificación:

Planificación dentro de cada cola: Cada cola puede utilizar su propia política de planificación, de acuerdo a la clase de procesos que acoge, la cual puede ser usando diferentes algoritmos (FCFS, Round Robin, etc.).
Planificación entre colas:

Se le asigna una prioridad (P) a cada cola.
Se le asigna un Quantum de CPU a cada cola, que se reparte entre los procesos de cada cola.

Ejemplo

El gráfico muestra las diferentes colas que pueden existir en "Colas Múltiples" (pueden haber menos colas o más colas), por ejemplo la cola para procesos del sistema tiene una prioridad (P) y un quantum de tiempo (Q) en la CPU diferente a las demás. Además las colas pueden estar implementadas con diferentes tipos de algoritmos ya sean con desalojo o sin desalojo. Es válido aclarar que las colas son atendidas en dependencia de su prioridad, por ejemplo:

Para la figura que se muestra, la primera cola en ser atendida es la cola de Procesos del Sistema, la cual tiene una prioridad (P) de 1, y solo después de haberse ejecutado todos los procesos de dicha cola, es que se atienden las próximas colas en dependencia de la prioridad, en caso de que lleguen nuevos procesos a la cola anteriormente atendida, esta vuelve a ser la de mayor prioridad y se deja de atender la cola presente para volver atender dicha cola.

Ilustracion Colas multiples administracion de procesos

Planificación Garantizada

Planificación Garantizada:

Una estrategia de planificación totalmente distinta consiste en hacer promesas reales al usuario en cuanto al rendimiento y después cumplirlas. Una promesa que es realista y fácil de cumplir es la siguiente: si hay n usuarios en sesión mientras usted está trabajando, usted recibirá aproximadamente 1/n de la capacidad de la CPU. De forma similar, en un sistema mono usuario con n procesos en ejecución, si todo lo demás es igual, cada uno deberá recibir un de los ciclos de CPU.

Para poder cumplir esta promesa, el sistema debe llevar la cuenta de cuánto tiempo de CPU ha tenido cada proceso desde su creación. A continuación, el sistema calculara el tiempo de CPU al que tenía derecho cada proceso, es decir, el tiempo desde la creación dividido entre n. puesto que también se conoce el tiempo de CPU del que cada proceso ha disfrutado realmente, es fácil calcular la relación entre el tiempo de CPU recibido y el tiempo al que se tenía derecho. Una relación de 0.5 implica que el proceso solo ha disfrutado de la mitad del tiempo al que tenía derecho, y una relación de 2.0 implica que un proceso ha tenido dos veces más tiempo del que debería haber tenido. El algoritmo consiste entonces en ejecutar el trabajo con la relación más baja hasta que su relación haya rebasado la de su competidor más cercano

Características:

· Se debe de conocer el % del CPU asignado a cada proceso

· Se debe contabilizar el tiempo consumido

· Se debe controlar el porcentaje del CPU requerido

· Se debe asignar un porcentaje del CPU equitativo a todos los procesos.

SRTF, Short Remaining Time First.

Rommel Rodriguez

SRTF, Short Remaining Time First.

Es similar al SJF, con la diferencia de que si un nuevo proceso pasa a listo se activa eldispatcher 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 decremento con el tiempo que ha estado ejecutándose.

En SRTF se penaliza a 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 larga la ejecución en este orden al ser preciso un cambio adicional de proceso y la ejecución del código del planificador. Trabajos cortos.

Características:
- De los procesos que están esperando para usar la CPU,SRTF lleva a ejecución el proceso al que le reste menos tiempo para terminar.
- Los empates se dirimen mediante FIFO / FCFS

Funcionamiento:
- Los procesos llegan a la cola y solicitan un intervalo de CPU
- Si dicho intervalo es inferior al que le falta al proceso en ejecución para abandonar la CPU, el nuevo proceso pasa a la CPU y el que se ejecutaba a la cola de preparados.

Inconvenientes:
- El intervalo de CPU es difícil de predecir
- Posibilidad de inanición: los trabajos largos no se ejecutarán mientras hayan trabajos cortos.

#include<iostream.h>
#include<stdio.h>
#include<conio.h>
#include<math.h>
void main()
{
float avg=0;
int i,j,n,temp1;
int tot=0,wt[10],pt[10];
char p[8][5],temp[6];
clrscr();
cout<<"please enter the no of processes:";
cin>>"%d",&n;
for(i=0;i<n;i++)
{
cout<<"enter process %d :\n",i+1;
cin>>"%s",&p[i];
cout<<"enter the process time";
cin>>"%d",&pt[i];
}
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(pt[i]>pt[j])
{
temp1=pt[i];
pt[i]=pt[j];
pt[j]=temp1;
strcpy(temp,p[i]);
strcpy(p[i],p[j]);
strcpy(p[j],temp);
}
}
}
wt[0]=0;
for(i=1;i<n;i++)
{
wt[i]=wt[i-1]+et[i-1];
tot=tot+wt[i];
}
avg=(float)tot/n;
cout<<"p_name\t P_time\t w_time\n";
for(i=0;i<n;i++)
cout<<"%s\t%d\t%d\n",p[i],et[i],wt[i];
cout<<"total waiting time=%d\n avg waiting time=%f",tot,avg;
getch();
}

lunes, 27 de agosto de 2012

Planificacion por Turno Rotatorio(ROUND-ROBIN)

Por: Carlos Gabriel Hurtado Castillo

Funcionamiento

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 robín es muy fácil de implementar. Todo lo que necesita el planificador es mantener una lista de los procesos listos.

Tamaño del Cuanto

La determinación del tamaño del cuanto es vital para la operación efectiva de un sistema de cómputo. Si el cuanto de tiempo es muy grande, cada proceso tendrá el tiempo necesario para terminar, de manera que el esquema de planificación por turno degenera en uno de primero-en-entrar-primero-en-salir. Si el cuanto es muy pequeño, el gasto extra por cambio de proceso se convierte en el factor dominante y el rendimiento del sistema se degradará hasta el punto en que la mayor parte del tiempo se invierte en la conmutación del procesador, con muy poco o ningún tiempo para ejecutar los programas de los usuarios.

El tamaño del cuanto debe fijarse en el tamaño lo bastante grande como para que la mayoría de las peticiones interactivas requieran menos tiempo que la duración del cuanto.

Por ejemplo, supongamos que el cambio de proceso tarda 5 mseg., y la duración del cuantum es de 20 mseg. Con estos parámetros, se utiliza un mínimo del 20% del tiempo de la CPU en la ejecución del sistema operativo. Para incrementar la utilización de la CPU por parte de los procesos de usuario podríamos establecer un cuantum de 500 mseg., el tiempo desperdiciado con este parámetro sería del 1%.

Pero consideremos lo que ocurriría si diez usuarios interactivos oprimieran la tecla enter casi al mismo tiempo. Diez procesos se colocarían en la lista de procesos listos. Si la CPU está inactiva, el primero de los procesos comenzaría de inmediato, el segundo comenzaría medio segundo después, etc. Partiendo de la hipótesis de que todos los procesos agoten su cuantum, el último proceso deberá de esperar 4’5 seg. para poder ejecutarse. Esperar 4’5 seg. para la ejecución de una orden sencilla como dir parece excesivo.

En conclusión, un cuantum corto disminuye el rendimiento de la CPU, mientras que un cuantum muy largo empobrece los tiempos de respuesta y degenera en el algoritmo FIFO. La solución es adoptar un término medio como 100 mseg.

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 agotación del cuantum se llama al dispatcher.

Caracteristica

Periódicamente, se genera una interrupción de reloj.
Cuando se genera la interrupción, el proceso que está en ejecución se sitúa en la cola de Listos y se selecciona el siguiente trabajo (apropiativo)
Se conoce también como fracciones de ti
Esta diseñado específicamente para sistemas de tiempo compartido. Se asigna un cuanto de tiempo (10-100ms.) de igual duración a todos los procesos listos para ser ejecutados. Entre ellos, la selección se realiza mediante una cola FIFO.
Parámetro critico: tamaño del cuanto. La efectividad depende del tamaño del el cuanto pero hay que tener en cuenta el tiempo dedicado al cambio de contexto