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

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:

<!--[if !supportLists]-->·         <!--[endif]-->Se debe de conocer el % del CPU asignado a cada proceso

<!--[if !supportLists]-->·         <!--[endif]-->Se debe contabilizar el tiempo consumido

<!--[if !supportLists]-->·         <!--[endif]-->Se debe controlar el porcentaje del CPU requerido

<!--[if !supportLists]-->·         <!--[endif]-->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();
}

Planificación por sorteo (lotería)

Planificación por sorteo (lotería)

La idea básica consiste en dar a los procesos boletos de lotería para los diversos recursos del sistema, como el tiempo de CPU: Cada vez que se hace necesario tomar una decisión de planificación, se escoge al azar un boleto de lotería, y el proceso poseedor de este boleto obtiene el recurso.

Características:

[1] Es de carácter aleatorio.

[2] Cada vez que aparezca un proceso nuevo, se le conceden boletos, con lo que ya tendrá una probabilidad de ganar proporcional al número de boletos recibidos.

[3] Este esquema de planificación es de resultados comparativamente rápidos en relación a lo pretendido con las reparticiones de boletos, pues tarda solamente hasta el próximo sorteo.

[4] Se pueden dar más boletos a los procesos más importantes, a fin de aumentar sus posibilidades de ganar.

[5] En procesos cooperativos pueden intercambiar boletos entre sí como en servicios cliente-servidor donde el cliente puede prestarle temporalmente al servidor sus boletos para una mayor posibilidad de ganar tiempos.

[6] En este tipo de planificación, la prioridad queda determinada por la cantidad de boletos asignados a un proceso, que influirán estadísticamente de acuerdo a dicha proporción.

Ejemplo:

Si hay 3 procesos preparados P1, P2 y P3, que cuentan respectivamente con 3, 1 y 5 papeletas, estarán ordenados en la cola como P3, P1 yP2. Cuando hay que elegir un nuevo proceso a planificar, el sistema realiza un sorteo generando un número aleatorio entre 1 y el número total de papeletas repartidas.

Tras el sorteo, encontraremos al ganador si contamos papeletas desde el principio dela cola de preparados. Por ejemplo, si sale ganadora la papeleta séptima, el ganador será el proceso P1.

El proceso ganador tomará control de la CPU hasta que se bloquee voluntariamente o el sistema le expulse porque haya consumido una porción de tiempo prestablecida.  El sorteo se repite siempre que haya que elegir un nuevo proceso a planificar, teniendo en cuenta que, en cada sorteo, el número de procesos preparados puede ser distinto y por tanto, el número total de papeletas a considerar también.

Código:

Referencias:

*  Documento proyecto planificación por lotería, Universidad Nacional de san Antonio Abad,   2008.  http://es.scribd.com/doc/40765110/Documentacion-Planificacion-por-loteria

*  Sistemas Operativos Diseño e Implementación, Andrew S. Tanenbaum, Prentice Hall

*  Documento Sistemas Operativos I,  E. U. de Informática, 10  diciembre 2003.

Diana Camila Sepulveda 

Planificación por reparto equitativo

Planificación por reparto equitativo

Se usa en los sistemas multiusuario.
Cada usuario tiene asignado algún tipo de ponderación, que indica la parte de los recursos del sistema para el usuario como una fracción de la utilización total de dichos recursos. En particular, cada usuario dispone de una parte del procesador. Este esquema debe funcionar de una forma más o menos lineal, por lo que si un usuario A tiene un peso dos veces mayor que el de un usuario B, entonces, a la larga, el usuario A debe poder hacer el doble de trabajo que B. El objetivo de un planificador por reparto equitativo es supervisar el uso, de forma que se asignen menos recursos a los usuarios que han consumido más de lo que les corresponde y más recursos a los que han consumido menos de lo que le corresponde.

En un sistema multiusuario, si las aplicaciones o los trabajos de los usuarios pueden organizarse en forma de varios procesos (o hilos), se dispone de una estructura para el conjunto de procesos que no se identifica con ningún planificador tradicional. Desde el punto de vista del usuario, el interés no está en cómo se comporta un proceso en particular, sino en cómo se comporta el conjunto de procesos de usuario que constituyen una aplicación. Así pues, sería interesante poder tomar decisiones de planificación en función de estos grupos de procesos. Este enfoque se conoce generalmente como planificación por reparto equitativo.

La planificación se lleva a cabo por prioridades, teniendo en cuenta la prioridad básica del proceso, su utilización reciente de la CPU y la utilización reciente de la CPU por parte del grupo al que pertenece. Cuanto mayor es el valor numérico de la prioridad, menor es ésta. Las fórmulas siguientes se aplican al proceso j del grupo k.

CPUj(i) = CPUj(i - 1) / 2

GCPUk(i) = GCPUk(i - 1) / 2

Pj(i) = Basej + CPUj(i - 1) / 2 + GCPUk(i - 1) / (4 x Wk)

Donde:

CPUj(i) = Media ponderada de la utilización de la CPU del proceso j en el intervalo i.

GCPUk(i) = Media ponderada de la utilización de la CPU del grupo k en el intervalo i.

Pj(i) = Prioridad del proceso j al principio del intervalo i; los valores más bajos indican prioridades más altas.

Basej = Prioridad de base del proceso j.

Wk = Peso asignado al grupo k, con la restricción de 0 <= Wk <= 1 y S Wk = 1.

Cada proceso tiene asignada una prioridad de base. Esta prioridad desciende a medida que el proceso y el grupo al que pertenece utilizan la CPU. En el caso de la utilización del grupo, la media se normaliza dividiendo por el peso del grupo. Cuanto mayor es el peso asignado al grupo, menos afecta su utilización a la prioridad.

Implementación de acciones:

Cada segundo t1: programación a nivel de usuario

para cada usuario

Cada uso y actualización de los costos incurridos en los últimos segundos t1

Usado por usuario = usageuser × K1 + chargesuser

Restablecer recuento del costo

chargesuser = 0

Cada segundo T2: decaimiento de las prioridades del proceso

para cada proceso

priorityprocess priorityprocess = K2 × × (niceprocess + K3)

Cada segundo t3: ajuste de prioridad

prioritycurrent_process = prioritycurrent_process +

usagecurrent_user × active_processescurrent_user acciones 2

current_user

En cada evento de programación: el proceso de selección actual

chargescurrent_user = costo + chargescurrent_user + costo  del evento

ejecutar el proceso con prioridad más baja

Prioridad de normalización:

max_priorida = 0

for each process

if

max_priorida < priorityprocess ≤ priority_bound

then

max_priorida= priorityprocess

for each process

Scale priority to appropriate range

if

priorityprocess ≤ max_priorida

then

normalised_priorityprocess = (K4 − 1) ×

priorityprocess

max_priorida

else

normalised_priorityprocess = K4

Ajustando grupos:

for each group (descend hierarchy)

if

actual_machine_proportiongroup <  K6 ×  machine_proportion_duegroup

entonces

for each user in the group (descend hierarchy)

chargesuser = chargesuser  × actual_machine_proportiongroup K6 × machine_proportion_duegroup

Web Grafía  :

http://www.cs.cornell.edu/courses/cs614/2003sp/papers/KL89.pdf

http://www.monografias.com/trabajos16/procesadores/procesadores.shtml