Diferencia entre revisiones de «Criterios de planificación»
De Wiki de Sistemas Operativos
(Introducción de ejemplo) |
(Introducción de ejemplo) |
||
| Línea 123: | Línea 123: | ||
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. | 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: | ||
| + | < = 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_| ____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_| | ||
| + | Datos del _H0_|_0__|_1__|_4__|_6__|_12_| Cálculos _t__|_3__|_5__|_1__|_8__|_3__| | ||
| + | problema _t__|_3__|_5__|_1__|_8__|_3__| de tiempos _T__|_3__|_8__|_1__|_14_|_3__| | ||
| + | _x__|_1__|_8/5|_1__|14/8|_1__| | ||
== Por prioridades == | == Por prioridades == | ||
Revisión del 17:13 8 mar 2011
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 un procesos. No cumple varios aspectos de diseño de un buen planificador, como repetitibilidad o predecibilidad. Su uso es establecer una cota inferior a la hora de diseñar un planificador: Si éste presenta peores resultados que el método estocástico, significa que estará mal diseñado.
Ejemplo:
< = 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
-------------------------------------------------------------------------------------------------------------------------
____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_| ____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_2__|_6__|_10_| Cálculos _t__|_3__|_5__|_4__|_3__|_5__|
problema _t__|_3__|_5__|_4__|_3__|_5__| de tiempos _T__|_3__|_19_|_5__|_4__|_5__|
_x__|_1__|19/5|_5/4|_4/3|_1__|
Como podemos observar, este método puede provocar grandes retrasos en algunos procesos debido a su carácter aleatorio.
Con conocimiento del futuro
En base al conocimiento del futuro se asignan los procesos. Representa una cota superior, es decir, mientras un planificador tenga un comportamiento más parecido a este método, mejor diseñado estará.
Ejemplo:
< = 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>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
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_| ____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_6__|_7__| Cálculos _t__|_3__|_5__|_2__|_3__|_1__|
problema _t__|_3__|_5__|_2__|_3__|_1__| de tiempos _T__|_3__|_9__|_2__|_8__|_4__|
_x__|_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:
< = 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>---|---|---|---|---|---|---|---|---|---|
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_| ____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_9__|_12_| Cálculos _t__|_3__|_5__|_2__|_5__|_5__|
problema _t__|_3__|_5__|_2__|_5__|_5__| de tiempos _T__|_3__|_7__|_7__|_6__|_8__|
_x__|_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:
< = 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>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
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_| ____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_9__|_12_| Cálculos _t__|_3__|_5__|_2__|_5__|_5__|
problema _t__|_3__|_5__|_2__|_5__|_5__| de tiempos _T__|_3__|_9__|_2__|_6__|_8__|
_x__|_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:
< = 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
-------------------------------------------------------------------------------------------------------------------------
____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_| ____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_2__|_7__|_6__| Cálculos _t__|_3__|_5__|_4__|_3__|_5__|
problema _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:
< = 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_| ____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_4__|_6__|_12_| Cálculos _t__|_3__|_5__|_1__|_8__|_3__|
problema _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.
- Índice dinámico: Establecido por el planificador, inicialmente basado en el índice estático.
En el caso de Linux, como sucede con otros sistemas tipo-Unix, se dispone de una índice denominado nice value cuyos valores están entre -20 (máxima prioridad) y 19 (mínima prioridad).
