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                                                                       
                   |---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
               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__|
                   _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:

                     ____|_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                                                                       
                   |---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
               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__|
                   _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:

                    ____|_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                                                                       
                  |---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
              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__|
                   _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:

                     ____|_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.
• Í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).