Criterios de planificación

De Wiki de Sistemas Operativos
Revisión del 22:48 21 mar 2011 de Pneira (discusión | contribuciones) (→‎Colas multinivel con realimentación (feedback): retirar planificador de Linux)
Saltar a: navegación, buscar

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 repetitividad 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 no 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__|

                       < = lanzamiento del proceso
                       > = 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 proceso por orden de llegada al sistema, cuando un proceso está preparado se añade al final de la cola y se ejecuta según el orden de incorporacion. Su principales ventajas son su facilidad de implementación, consume muy poco tiempo de procesador (casi ninguno) y su orden de complejidad, O(1). Su desventaja es que los procesos de corta duración pueden quedar a la espera de procesos muy prolongados, así que 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__|

                       < = lanzamiento del proceso
                       > = 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 de entre todos los que están listos para ejecutarse. Se necesita conocer con antelación el tiempo de ejecucion de cada proceso, algo que es muy dificil en muchas ocasiones. 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. Otro inconveniente es que todo trabajo corto que llegue cuando ya ha comenzado un trabajo largo tiene un gran retraso. 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__|

                      < = lanzamiento del proceso
                      > = finalización del proceso
                      x = indica que el proceso está asignado al procesador en ese momento
                      & = se ejecuta el planficador
        |---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
    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>
planif. &---|---|---&---|---&---|---|---|---|---&---|---|---|---|---&---|---|---|---|---|
   -----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> 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, P=T/t=(w+t)/t y elige el de mayor valor. Este método puede producir aplazamientos de ejecución de procesos,pero no son indefinidos. Su orden de complejidad es O(n). 

    Ejemplo:

                     ____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
          Datos del  _H0_|_0__|_1__|_2__|_7__|_6__|
           problema  _t__|_3__|_5__|_4__|_3__|_5__|

                       < = lanzamiento del proceso
                       > = finalización del proceso
                       x = indica que el proceso está asignado al procesador en ese momento
                       & = se ejecuta el planficador
       |---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
   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>---|---|---|
planif.&---|---|---&---|---|---|---|---&---|---|---|---&---|---|---|---|---&---|---|---|
       |___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|> 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_|
                   z(3)|_1__|_2/5|_0/4|____|____|
                   z(8)|_1__|_7/5|_5/4|_1/3|_2/5|
                  z(12)|_1__|_7/5|_9/4|_5/3|_6/5|      z = índice de penalización
                  z(17)|_1__|_7/5|_9/4|10/3|11/5|
                  z(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. Este metodo es necesario si existen procesos de alta prioridad.

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, sólo si el proceso nuevo necesita menos tiempo del que le falta al actual. Su orden de complejidad es O(n), pero, a diferencia del no apropiativo, cuando entra un proceso en la lista de procesos, se ejecuta código de planificador.Con este método los procesos más largos se ven perjudicados, pues se puede retrasar tanto su tiempo de inicio, como el de finalización. 

    Ejemplo:

                     ____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
          Datos del  _H0_|_0__|_1__|_4__|_6__|_12_|
           problema  _t__|_3__|_5__|_1__|_8__|_3__|

                       < = lanzamiento del proceso
                       > = finalización del proceso
                       x = indica que el proceso está asignado al procesador en ese momento
                       $ = indica la ejecución del planificador para retirar un
                           proceso y establecer otro según el criterio
                       & = se ejecuta el código del planificador
       |---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
   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>---|---|---|---|---|
Planif.|---&---|---&---&---&---&---|---|---&---|---|---&---|---|---&---|---|---|---|---|
    ---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> 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__|        z = índice de penalización
                   _z__|_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, aumentándola cuando un proceso está a la espera o disminuyendola cuando tiene adjudicado el procesador.

El método funciona de la siguiente manera: El planificador mantiene ordenada la cola de procesos preparados, según prioridades decrecientes. Si el proceso en ejecución se bloquea, el planificador selecciona el primero de la lista. Cuando un proceso pasa a la situación de preparado, comprueba si su prioridad es mayor que la del proceso activo. En tal caso, suspende la ejecución de éste, colocándolo al principio de la cola de preparados, y elige la recién llegado; si no, lo inserta en la cola según su prioridad. Cuando hay varios procesos con la misma prioridad se pueden aplicar diversos criterios, como seguir el orden de llegada a la cola de preparados, o el que necesite menos tiempo para acabar entre otros.


El orden es siempre O(n). 

   Ejemplo:
                                                                                        
                    ____|_Pa_|_Pb_|_Pc_|_Pd_|
         Datos del  _H0_|_0__|_1__|_2__|_3__|
          problema  _t__|_2__|_4__|_2__|_7__|    p = prioridad estática
                    _p__|_0__|-20_|_4__|_10_|
                                                      
                      < = lanzamiento del proceso
                      > = finalización del proceso
                      x = indica que el proceso está asignado al procesador en ese momento
                      $ = indica la ejecución del planificador para retirar un
                          proceso y establecer otro según el criterio
                      & = se ejecuta el código del planificador
        |---$---|---|---|---$---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
    Pa  <xxx|---|---|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|
    Pb  |---<xxx|xxx|xxx|xxx>---$---|---|---|---|---|---|---|---|---|---|---|---|---|---|
    Pc  |---|---<---|---|---|---|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
    Pd  |---|---|---<---|---|---|---|---|xxx|xxx|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|
Planif. |---&---&---&---|---&---&---|---&---|---|---|---|---|---|---|---|---|---|---|---|
 -------|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> 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_|
      Cálculos    _t__|_2__|_4__|_2__|_7__|
     de tiempos   _T__|_6__|_4__|_6__|_12_|        z = índice de penalización
                  _z__|_3__|_1__|_3__|12/7|

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 quantum 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 se le retira el procesador y se añade al final de la cola. Esto beneficia a los procesos cuyo comportamiento está limitado por el procesador, pues se pasan más tiempo asignados al 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. 

   Ejemplo:
                                                                                        
                    ____|_Pa_|_Pb_|_Pc_|_Pd_|
         Datos del  _H0_|_0__|_1__|_2__|_3__|
          problema  _t__|_2__|_4__|_2__|_7__|    quantum = 1 unidad de tiempo
                                                      
                      < = lanzamiento del proceso
                      > = finalización del proceso
                      x = indica que el proceso está asignado al procesador en ese momento
                      $ = indica la ejecución del planificador para retirar un
                          proceso y establecer otro según el criterio
       |---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
   Pa  <xxx|---|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
   Pb  |---<xxx|---|---|---|xxx|---|---|xxx|---|xxx>---|---|---|---|---|---|---|---|---|
   Pc  |---|---<xxx|---|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|
   Pd  |---|---|---<xxx|---|---|---|xxx|---|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_|
      Cálculos    _t__|_2__|_4__|_2__|_7__|
     de tiempos   _T__|_5__|_10_|_5__|_12_|        z = índice de penalización
                  _z__|_5/2|10/4|_5/2|12/7|

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 (dispondrá de otro quantum completo). Este tipo de criterio tiene un problema y es que se pueden posponer indefinidamente algunos procesos si hay varios procesos que bloqueen.

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.

Colas multinivel

En este tipo de criterio se mantienen múltiples colas con los procesos en estado preparado. Los procesos se clasifican en las colas según sus características, cada cola recibe un tratamiento distinto.

Un ejemplo sería el siguiente, compuesto de cuatro colas:

  1. Esta primera cola es para procesos que poseen mayor tiempo de ejecución, son los gestores de interrupción y los gestores de dispositivos (drivers). Hay que tomar los datos y almacenarlos en memoria lo antes posible para poder recoger más, aunque se posponga el procesamiento de dichos datos.
  2. En esta cola se almacenan los procesos del servidor, tales como : proceso administrador de memoria, administrador de ficheros, administrador de red, etc.
  3. Esta cola esta reservada a los procesos de usuario (procesos útiles para el usuario). Esta se divide a su vez en dos colas:
    1. Cola de procesos interactivos, limitados por E/S.
    2. Cola de procesos por lotes, limitados por el procesador.

Las colas tienen prioridad según su número, por ejemplo mientras que haya procesos preparados en la primera cola, no se mira la segunda. Esto puede dar lugar a que si hay muchos procesos de gestión de dispositivos se degrade la eficiencia del sistema.

La primera cola esta implementada con una FIFO(no apropiativo), mientras que las colas 2 y 3 se basan en un sistema de RR (turno rotatorio).

Colas multinivel con realimentación (feedback)

Estas son una variante de las colas multinivel en las que los procesos pueden ascender o descender de una cola a otra según su comportamiento, es decir si un proceso no utiliza completamente su ventana de tiempo se le ascenderá a una cola mas prioritaria, sin embargo si este proceso varia su comportamiento realizando tareas mas intensivas este descenderá a otra cola con menor prioridad. (Esto da prioridad a procesos limitados por E/S).

Obtenido de «https://1984.lsi.us.es/wiki-ssoo/index.php?title=Criterios_de_planificación&oldid=396»