Criterios de planificación
Métodos no apropiativos
El procesador es asignado al proceso hasta fin de ejecución. Suele darse en sistemas operativos monoprogramables y sistemas de tiempo real.
Estocástico
Se selecciona aleatoriamente el proceso a ser asignado al procesador. No cumple varios aspectos de diseño de un buen planificador, como repetitibilidad o predecibilidad. Es un criterio de planificación teórico que sirve de referencia, si se emplea un criterio de planificación que ofrece resultados peores que la planificación de procesos estocástica, entonces es que se trata de un buen criterio de planificación.
No se ofrece un ejemplo, puesto que para un conjunto de procesos existen tantas trazas de ejecución como posible combinaciones aleatorias.
Con conocimiento del futuro
En base al conocimiento del futuro se asignan los procesos. Se trata también de un criterio de planificación teórico. Si un criterio de planificación se acerca al criterio de planificación con conocimiento de futuro, entonces es que se trata de un buen planificador.
Ejemplo:
____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_6__|_7__|
problema _t__|_3__|_5__|_2__|_3__|_1__|
< = indica que el proceso se encuentra en modo preparado
> = indica la finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---<xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---<---|---|---|---|---|xxx|xxx|xxx>---|---|---|---|---|---|
Pe |---|---|---|---|---|---|---<---|---|---|xxx>---|---|---|---|---|---|---|---|---|
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_2__|_3__|_1__|
de tiempos _T__|_3__|_9__|_2__|_8__|_4__| z = índice de penalización
_z__|_1__|_9/5|_1__|_8/3|_4/1|
En este ejemplo, al conocer los tiempos en los que llegará cada proceso, y el tiempo de proceso, podemos buscar la forma de asignarlos de forma que, por ejemplo, consigamos la mínima penalización.
Por orden de llegada (First In, First Out: FIFO)
Se selecciona el procesa por orden de lanzamiento. Su principales ventajas son su facilidad de implementación, y su orden de complejidad, O(1). Su desventaja es que los procesos de corta duración presentarán un alto índice de penalización.
Ejemplo:
____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_9__|_12_|
problema _t__|_3__|_5__|_2__|_5__|_5__|
< = indica que el proceso se encuentra en modo preparado
> = indica la finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---<---|---|---|---|---|xxx|xxx>---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---|---|---|---<---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|
Pe |---|---|---|---|---|---|---|---|---|---|---|---<---|---|---|xxx|xxx|xxx|xxx|xxx>
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_2__|_5__|_5__|
de tiempos _T__|_3__|_7__|_7__|_6__|_8__| z = índice de penalización
_z__|_1__|_7/5|_7/2|_6/5|_8/5|
El siguiente, el más corto (Shortest Job First: SJF)
Se selecciona el proceso que requiera menos tiempo de ejecución. Para procesos largos puede presentar un índice de penalización elevado: Si se tienen muchos procesos cortos, el de mayor duración puede quedar en espera indefinidamente. Su orden de complejidad es O(n).
Ejemplo:
____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_9__|_12_|
problema _t__|_3__|_5__|_2__|_5__|_5__|
< = indica que el proceso se encuentra en modo preparado
> = indica la finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---<xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---|---|---|---<---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|
Pe |---|---|---|---|---|---|---|---|---|---|---|---<---|---|---|xxx|xxx|xxx|xxx|xxx>
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_2__|_5__|_5__|
de tiempos _T__|_3__|_9__|_2__|_6__|_8__| z = índice de penalización
_z__|_1__|_9/5|_1__|_6/5|_8/5|
Basado en índice de penalización
Se selecciona el proceso que lleva más tiempo en estado preparado, sin estar en estado activo. Estima los índices de penalización y elige el de mayor valor.
Ejemplo:
____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_2__|_7__|_6__|
problema _t__|_3__|_5__|_4__|_3__|_5__|
< = indica que el proceso se encuentra en modo preparado
> = indica la finalización del proceso
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---<---|---|---|---|---|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---|---<---|---|---|---|---|---|---|---|---|---|xxx|xxx|xxx>
Pe |---|---|---|---|---|---<---|---|---|---|---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Cálculos _t__|_3__|_5__|_4__|_3__|_5__|
de tiempos _T__|_3__|_7__|_9__|_13_|_11_|
x(3)|_1__|_2/5|_0/4|____|____|
x(8)|_1__|_7/5|_5/4|_1/3|_2/5|
x(12)|_1__|_7/5|_9/4|_5/3|_6/5|
x(17)|_1__|_7/5|_9/4|10/3|11/5|
x(20)|_1__|_7/5|_9/4|13/3|11/5|
Métodos apropiativos
El planificador puede retirar el procesador en cualquier momento al proceso activo. Suele darse en sistemas operativos multiprogramables.
El siguiente, el más corto (Shortest Job First: SJF)
Se selecciona el proceso que requiera menos tiempo de ejecución. Si hay un proceso en estado preparado que requiere menos tiempo de ejecución, se le asigna el procesador.
Ejemplo:
____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_4__|_6__|_12_|
problema _t__|_3__|_5__|_1__|_8__|_3__|
< = indica que el proceso se encuentra en modo preparado
> = indica la finalización del proceso
$ = indica la ejecución del planificador para retirar un
proceso y establecer otro según el criterio
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---$---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|xxx|---|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---|---<xxx>---|---|---|---|---|---|---$---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---<---|---|---|xxx|xxx|xxx|---|---|---|xxx|xxx|xxx|xxx|xxx>
Pe |---|---|---|---|---|---|---|---|---|---|---|---<xxx|xxx|xxx>---|---|---|---|---|
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_1__|_8__|_3__|
de tiempos _T__|_3__|_8__|_1__|_14_|_3__|
_x__|_1__|_8/5|_1__|14/8|_1__|
Por prioridades
Se establecen índices de prioridad a cada proceso:
- Índice estático: Establecido por el usuario. En el caso de sistemas operativos tipo Unix, se dispone de una índice denominado nice value cuyos valores están entre -20 (máxima prioridad) y 19 (mínima prioridad).
- Índice dinámico: Establecido por el planificador, inicialmente basado en el índice estático, después se va recalculando en base a las observaciones que realiza el planificador sobre el comportamiento de los procesos.
Turno rotatorio estricto (Round Robin: RR)
En este criterio, todo proceso es asignado al procesador durante un tiempo establecido denominado quantum, tras el cual se le retira y se asigna a otro proceso rotatoriamente. De esta manera, los procesos acceden al procesador por turnos.
El tamaño del quantum es fundamental para determinar el comportamiento de este criterio de planificación. Si el quantum empleado es pequeño, por ejemplo de 10 ms, suponiendo que la conmutación de procesos requiere 10ms, el 50% del tiempo se empleará el procesador para ejecutar el código que permite conmutar entre procesos. Sin embargo, Si el quantuam empleado es grande, por ejemplo de 5 s, la latencia será mayor, degradando la experiencia del usuario que notará como sus procesos progresan a saltos, puesto que, en el peor de los casos, hasta pasados 5 s no se le asignará el procesador a otro proceso .
Si un proceso bloquea antes de consumir su quantum, como sucede con proceso cuyo comportamiento está limitado por operaciones de entrada/salida, se añade al final de la cola. Esto beneficia a los procesos cuyo comportamiento está limitado por el procesador.
Este criterio se puede implementar con una cola, de manera que la complejidad de la selección de un proceso es O(1). Nótese que a mayor número de procesos preparados, mayor tiempo tardará un proceso en volver a pasar a estado activo.
Turno rotatorio con compensación
Es una variante del anterior. Para no perjudicar a los procesos cuyo comportamiento está limitado por operaciones de entrada/salida, se reinsertan en la cola en proporción al tiempo consumido. Es decir, que si un cierto proceso ha consumido el 25% de su quantum, se reinserta en el 25% de la cola, contando desde el principio.
Turno rotatorio con quantum dependiente del número de procesos
Otra variante se trata de emplear un quantum proporcional al número de procesos que haya en estado preparado. De esta forma se obtiene una progresión más uniforme, y por tanto una mejor experiencia para el usuario. Sin embargo, esto aumenta el número de conmutaciones entre procesos. Para evitar la degradación del rendimiento por un exceso de conmutaciones, se establece un mínimo de manera que el quantum no puede ser menor a éste.
