Diferencia entre revisiones de «Criterios de planificación»

De Wiki de Sistemas Operativos
Saltar a: navegación, buscar
(→‎Con conocimiento del futuro)
(→‎Planificación apropiativa y no apropiativa)
 
(No se muestran 144 ediciones intermedias de 30 usuarios)
Línea 1: Línea 1:
−
= Métodos no apropiativos =
+
= Planificación apropiativa y no apropiativa =
  
−
El procesador es asignado al proceso hasta fin de ejecución. Suele darse en sistemas operativos monoprogramables y sistemas de tiempo real.
+
Un planificador no apropiativo carece de transición de activo a preparado en el diagrama de estado de un proceso.
  
−
== Estocástico ==
+
Un planificador cualquiera, ya sea apropiativo o no, decide qué proceso se asigna al procesador si:
  
−
Se selecciona aleatoriamente el proceso a ser asignado al procesador. No cumple varios [[Planificación de procesos#Aspectos para diseñar un buen planificador|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.
+
* El proceso activo pasa a estado bloqueado.
 +
* El proceso activo termina su ejecución.
  
−
No se ofrece un ejemplo, puesto que para un conjunto de procesos existen tantas trazas de ejecución como posible combinaciones aleatorias.
+
Un planificador apropiativo, además, se ejecuta si:
  
−
== Con conocimiento del futuro ==
+
* Se lanza un nuevo proceso (véase ''prioridades'').
 +
* El proceso activo agota el tiempo máximo de asignación del procesador (véase ''Turno Rotatorio'').
  
−
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.
+
== Planificación por prioridades ==
  
−
    Ejemplo:
+
Se establecen índices de prioridad a cada proceso:
−
+
 
−
                      ____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
+
* '''Índice estático''': Establecido por el usuario por medio de una llamada al sistema (ver sys_nice() y sys_setschedprio()). En el caso de sistemas operativos tipo Unix, se dispone de un índice denominado ''nice value'' cuyos valores están entre -20 (máxima prioridad) y 19 (mínima prioridad).
−
          Datos del  _H0_|_0__|_1__|_3__|_6__|_7__|
+
* '''Í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 disminuyéndola cuando tiene adjudicado el procesador.
−
            problema  _t__|_3__|_5__|_2__|_3__|_1__|
+
 
−
+
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 al recién llegado; si no, lo inserta en la cola según su prioridad.
−
                        < = indica que el proceso se encuentra en modo preparado
+
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.
−
                        > = indica la finalización del proceso                                                                      
+
 
−
                    |---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
+
 
−
                Pa  <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
+
El orden es siempre O(n).
−
                Pb  |---<---|---|---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|
+
 
−
                Pc  |---|---|---<xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
+
    Ejemplo:
−
                Pd  |---|---|---|---|---|---<---|---|---|---|---|xxx|xxx|xxx>---|---|---|---|---|---|
+
                                                                                       
−
                Pe  |---|---|---|---|---|---|---<---|---|---|xxx>---|---|---|---|---|---|---|---|---|
+
                    ____|_Pa_|_Pb_|_Pc_|_Pd_|
−
              -----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
+
          Datos del  _H0_|_0__|_1__|_2__|_3__|
−
                    0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20
+
          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|
  
−
                    ____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
+
== Turno rotatorio ==
−
        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.
+
=== Turno rotatorio estricto (Round Robin: RR) ===
  
−
== Por orden de llegada (First In, First Out: FIFO) ==
+
En este criterio, todo proceso es asignado al procesador durante un tiempo máximo denominado ''quantum'', tras el cual se le retira el procesador y se asigna a otro proceso de la cola de preparados. De esta manera, los procesos acceden al procesador por turnos, en base al orden de procesos que hay en la cola de preparados.
  
−
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.
+
El tamaño del ''quantum'' es fundamental para determinar el comportamiento de este criterio de planificación.  Si el ''quantum'' empleado es muy pequeño, por ejemplo, de 1000 ciclos, suponiendo que la conmutación de procesos requiere 1000 ciclos, el procesador empleará el 50% del tiempo en ejecutar el codigo del planificador de procesos del sistemas operativo. Sin embargo, si el ''quantum'' empleado es grande, por ejemplo, de 1 millon de ciclos, suponiendo una cola de procesos suficientemente grande y N procesos en la cola de preparados, el proceso que está al final de la cola no tendra oportunidad de ejecucion hasta pasados N * 1 millon de ciclos, degradando la experiencia del usuario que notará como sus procesos progresan ''a saltos''.
  
−
    Ejemplo:
+
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 por lotes, cuyo comportamiento está limitado por el procesador, pues se pasan más tiempo asignados al procesador.
−
 
−
                      ____|_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) ==
+
Los procesos recién lanzados y los que pasan de estado bloqueado a preparado se insertan siempre al final de la cola.
  
−
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).
+
Este criterio se puede implementar con una cola, de manera que el orden de complejidad en la selección del proceso que pasa a estado activo es <math>O(1)</math> puesto que siempre se toma el primero proceso de la cola. Nótese que, a mayor número de procesos preparados, mayor tiempo tardará un proceso al final de la cola en volver a pasar a estado activo.
  
 
     Ejemplo:
 
     Ejemplo:
−
+
                                                                                       
−
                     ____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
+
                     ____|_Pa_|_Pb_|_Pc_|_Pd_|
−
           Datos del  _H0_|_0__|_1__|_3__|_9__|_12_|
+
           Datos del  _H0_|_0__|_1__|_2__|_3__|
−
           problema  _t__|_3__|_5__|_2__|_5__|_5__|
+
           problema  _t__|_2__|_4__|_2__|_7__|   quantum = 1 unidad de tiempo
−
+
                                                     
−
                       < = indica que el proceso se encuentra en modo preparado
+
                       < = lanzamiento del proceso
−
                       > = indica la finalización del proceso                                                                      
+
                      > = finalización del proceso
−
                  |---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
+
                      x = indica que el proceso está asignado al procesador en ese momento
−
              Pa  <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
+
                       $ = indica la ejecución del planificador para retirar un
−
              Pb  |---<---|---|---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|
+
                          proceso y establecer otro según el criterio
−
              Pc  |---|---|---<xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
+
        |---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
−
              Pd  |---|---|---|---|---|---|---|---|---<---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|
+
    Pa  <xxx|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
−
              Pe  |---|---|---|---|---|---|---|---|---|---|---|---<---|---|---|xxx|xxx|xxx|xxx|xxx>
+
    Pb  |---<xxx|---|---|xxx|---|---|xxx|---|xxx>---|---|---|---|---|---|---|---|---|
−
              -----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
+
    Pc  |---|---<---|xxx|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
−
                  0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20
+
    Pd  |---|---|---<---|---|xxx|---|---|xxx|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|
−
     -------------------------------------------------------------------------------------------------------------------------
+
    $  $---$---$---$---$---$---$---$---$---$---$---$---$---$---$---$---|---|---|---|---|
−
                    ____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
+
  -----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
−
        Cálculos    _t__|_3__|_5__|_2__|_5__|_5__|
+
        0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20
−
      de tiempos  _T__|_3__|_9__|_2__|_6__|_8__|
+
                                                                                                 
−
                    _x__|_1__|_9/5|_1__|_6/5|_8/5|
+
                  ____|_Pa_|_Pb_|_Pc_|_Pd_|
 +
      Cálculos    _t__|_2__|_4__|_2__|_7__|
 +
      de tiempos  _T__|_3__|_9__|_5__|_12_|        I = índice de penalización
 +
                  _I__|_3/2| 9/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, 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.
 +
 
 +
Hay que tener en cuenta que:
 +
* Cuando un proceso consume su quantum pasa al final de la cola de preparados.
 +
* Un proceso en estado bloqueado se inserta en la cola de preparados una vez que pasa el tiempo de bloqueo.
 +
 
 +
        Ejemplo:
 +
                                                                                       
 +
                    ____|_Pa_|_Pb_|_Pc_|_Pd_|    Pa y Pc bloquean cada 1 unidad de tiempo
 +
          Datos del  _H0_|_0__|_1__|_2__|_3__|    El bloqueo se resuelve tras 2 unidades de tiempo
 +
          problema  _t__|_2__|_4__|_2__|_7__|    quantum = 2 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  |---<xxxxxxx|---|---|---|---|---|xxx|xxx>---|---|---|---|---|---|---|---|---|---|
 +
    Pc  |---|---<---|xxx|---|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
 +
    Pd  |---|---|---<---|xxx|xxx|---|---|---|---|xxxxxxxxxxxxxxxxxxx>---|---|---|---|---|
 +
     $  $---$---|---$---$---$---|---$---$---|---$---|---$---|---$---$---|---|---|---|---|
 +
  -----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> 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__|_7__|_9__|_6__|_12_|       z = índice de penalización
 +
                  _z__|_7/2|_9/4|_6/2|12/7|
 +
 
 +
=== 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.
  
−
== Basado en índice de penalización ==
+
Un ejemplo sería el siguiente, compuesto de cuatro colas:
  
−
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.
+
# Esta primera cola es para procesos que poseen menor 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.
 +
# En esta cola se almacenan los procesos del servidor, tales como: proceso administrador de memoria, administrador de ficheros, administrador de red, etc.
 +
# Esta cola está reservada a los procesos de usuario (procesos útiles para el usuario). Esta se divide a su vez en dos colas:
 +
## Cola de procesos interactivos, limitados por E/S.
 +
## Cola de procesos por lotes, limitados por el procesador.
  
−
    Ejemplo:
+
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.
−
 
−
                      ____|_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 =
+
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).
  
−
El planificador puede retirar el procesador en cualquier momento al proceso activo. Suele darse en sistemas operativos [[Multiprogramación|multiprogramables]].
+
=== Colas multinivel con realimentación (feedback)===
  
−
== El siguiente, el más corto (Shortest Job First: SJF) ==
+
Es una variante de las colas multinivel en las que los procesos pasan de una cola a otra según su comportamiento, de manera que:
  
−
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.
+
* Los procesos interactivos tienen más oportunidades de emplear el procesador.
 +
* Los procesos por lotes disponen del procesador durante más tiempo.
  
−
    Ejemplo:
+
Los procesos se asignan al procesador por turnos rotatorios, empleando un ''quantum'' dependiente de la cola en la que se encuentren. Los procesos que consumen el ''quantum'' asignado completamente un número determinado de veces pasan a colas en las que se asignan ''quantum'' mayores. Nótese que los procesos que no consumen su ''quantum'' muestran un comportamiento interactivo. Para no discriminar a los procesos que se encuentran en las colas con ''quantum'' menores, se les dan más oportunidades de ejecución.
−
 
−
                      ____|_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 ==
+
Por ejemplo, en un sencillo planificador de colas multinivel con realimentación compuesto por dos colas:
  
−
Se establecen índices de prioridad a cada proceso:
+
* En la primera cola se le asignan un ''quantum'' de 2 unidades de tiempo a los procesos.
 +
* En la segunda cola se le asignan un ''quantum'' de 1 unidad de tiempo a los procesos.
 +
 
 +
Si un proceso no consume el ''quantum'' asignado dos veces, pasa a la cola en la que en la se le asignan ''quantum'' de 1 unidad de tiempo.
 +
 
 +
Para que los procesos interactivos no salgan perjudicados, en aras de hacer un reparto del procesador más equitativo, se le dan dos oportunidades de ejecución a los procesos situados en la cola con ''quantum'' de 1 unidad de tiempo. De esta manera, los procesos de la primera cola reciben una oportunidad de ejecución con un ''quantum'' de 2 unidades de tiempo y los de la segunda reciben dos oportunidades de ejecución con un ''quantum'' de 1 unidad de tiempo.
  
−
* Índice estático: Establecido por el usuario.
+
Ejemplo:
−
* Índice dinámico: Establecido por el planificador, inicialmente basado en el índice estático.
+
Pa y Pc bloquean cada 1 unidad de tiempo
 +
El bloqueo se resuelve tras 2 unidades de tiempo
 +
Colas multinivel:  1. Procesos interactivos (quantum = 1 unidad de tiempo)
 +
                    2. Procesos por lotes    (quantum = 2 unidad de tiempo)   
 +
Inicialmente todos los procesos van a la cola 2
 +
Los procesos que no consuman su quantum al menos una vez pasan a la cola 1
 +
Las colas implementan turno rotatorio estricto.
 +
Siempre que haya procesos en la cola 1, debe ser atendidos de manera preferente frente a la cola 2.
 +
                                                                                       
 +
                    ____|_Pa_|_Pb_|_Pc_|_Pd_| 
 +
          Datos del  _H0_|_0__|_1__|_2__|_3__| 
 +
          problema  _t__|_2__|_4__|_2__|_7__|                     
 +
                                             
 +
                                                     
 +
                      < = 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  |---<xxxxxxx|---|---|---|---|---|xxxxxxx>---|---|---|---|---|---|---|---|---|---|
 +
    Pc  |---|---<---|---|xxx|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
 +
    Pd  |---|---|---<---|---|xxxxxxx|---|---|---|xxxxxxxxxxxxxxxxxxx>---|---|---|---|---|
 +
    $  $---$---|---$---$---$---|---$---$---|---$---|---$---|---$---$---|---|---|---|---|
 +
  -----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> 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__|_4__|_9__|_6__|_12_|        z = índice de penalización
 +
                  _z__|_4/2|_9/4|_6/2|12/7|
  
−
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).
 
  
−
== Turno rotatorio (Round Robin: RR) ==
 
  
−
== Colas multinivel ==
+
4.4. [[Planificadores_de_sistemas_operativos_existentes | Planificadores de sistemas operativos existentes]]

Revisión actual del 17:13 2 abr 2020

Planificación apropiativa y no apropiativa

Un planificador no apropiativo carece de transición de activo a preparado en el diagrama de estado de un proceso.

Un planificador cualquiera, ya sea apropiativo o no, decide qué proceso se asigna al procesador si:

  • El proceso activo pasa a estado bloqueado.
  • El proceso activo termina su ejecución.

Un planificador apropiativo, además, se ejecuta si:

  • Se lanza un nuevo proceso (véase prioridades).
  • El proceso activo agota el tiempo máximo de asignación del procesador (véase Turno Rotatorio).

Planificación por prioridades

Se establecen índices de prioridad a cada proceso:

  • Índice estático: Establecido por el usuario por medio de una llamada al sistema (ver sys_nice() y sys_setschedprio()). En el caso de sistemas operativos tipo Unix, se dispone de un í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 disminuyéndola 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 al 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

Turno rotatorio estricto (Round Robin: RR)

En este criterio, todo proceso es asignado al procesador durante un tiempo máximo denominado quantum, tras el cual se le retira el procesador y se asigna a otro proceso de la cola de preparados. De esta manera, los procesos acceden al procesador por turnos, en base al orden de procesos que hay en la cola de preparados.

El tamaño del quantum es fundamental para determinar el comportamiento de este criterio de planificación. Si el quantum empleado es muy pequeño, por ejemplo, de 1000 ciclos, suponiendo que la conmutación de procesos requiere 1000 ciclos, el procesador empleará el 50% del tiempo en ejecutar el codigo del planificador de procesos del sistemas operativo. Sin embargo, si el quantum empleado es grande, por ejemplo, de 1 millon de ciclos, suponiendo una cola de procesos suficientemente grande y N procesos en la cola de preparados, el proceso que está al final de la cola no tendra oportunidad de ejecucion hasta pasados N * 1 millon de ciclos, degradando la experiencia del usuario que notará como sus procesos progresan a saltos.

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 por lotes, cuyo comportamiento está limitado por el procesador, pues se pasan más tiempo asignados al procesador.

Los procesos recién lanzados y los que pasan de estado bloqueado a preparado se insertan siempre al final de la cola.

Este criterio se puede implementar con una cola, de manera que el orden de complejidad en la selección del proceso que pasa a estado activo es <math>O(1)</math> puesto que siempre se toma el primero proceso de la cola. Nótese que, a mayor número de procesos preparados, mayor tiempo tardará un proceso al final de la cola 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__|_3__|_9__|_5__|_12_|        I = índice de penalización
                  _I__|_3/2| 9/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, 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.

Hay que tener en cuenta que:

  • Cuando un proceso consume su quantum pasa al final de la cola de preparados.
  • Un proceso en estado bloqueado se inserta en la cola de preparados una vez que pasa el tiempo de bloqueo.
       Ejemplo:
                                                                                        
                    ____|_Pa_|_Pb_|_Pc_|_Pd_|    Pa y Pc bloquean cada 1 unidad de tiempo
         Datos del  _H0_|_0__|_1__|_2__|_3__|    El bloqueo se resuelve tras 2 unidades de tiempo
          problema  _t__|_2__|_4__|_2__|_7__|    quantum = 2 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  |---<xxxxxxx|---|---|---|---|---|xxx|xxx>---|---|---|---|---|---|---|---|---|---|
   Pc  |---|---<---|xxx|---|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
   Pd  |---|---|---<---|xxx|xxx|---|---|---|---|xxxxxxxxxxxxxxxxxxx>---|---|---|---|---|
    $  $---$---|---$---$---$---|---$---$---|---$---|---$---|---$---$---|---|---|---|---|
  -----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> 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__|_7__|_9__|_6__|_12_|        z = índice de penalización
                  _z__|_7/2|_9/4|_6/2|12/7|

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 menor 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 está 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)

Es una variante de las colas multinivel en las que los procesos pasan de una cola a otra según su comportamiento, de manera que:

  • Los procesos interactivos tienen más oportunidades de emplear el procesador.
  • Los procesos por lotes disponen del procesador durante más tiempo.

Los procesos se asignan al procesador por turnos rotatorios, empleando un quantum dependiente de la cola en la que se encuentren. Los procesos que consumen el quantum asignado completamente un número determinado de veces pasan a colas en las que se asignan quantum mayores. Nótese que los procesos que no consumen su quantum muestran un comportamiento interactivo. Para no discriminar a los procesos que se encuentran en las colas con quantum menores, se les dan más oportunidades de ejecución.

Por ejemplo, en un sencillo planificador de colas multinivel con realimentación compuesto por dos colas:

  • En la primera cola se le asignan un quantum de 2 unidades de tiempo a los procesos.
  • En la segunda cola se le asignan un quantum de 1 unidad de tiempo a los procesos.

Si un proceso no consume el quantum asignado dos veces, pasa a la cola en la que en la se le asignan quantum de 1 unidad de tiempo.

Para que los procesos interactivos no salgan perjudicados, en aras de hacer un reparto del procesador más equitativo, se le dan dos oportunidades de ejecución a los procesos situados en la cola con quantum de 1 unidad de tiempo. De esta manera, los procesos de la primera cola reciben una oportunidad de ejecución con un quantum de 2 unidades de tiempo y los de la segunda reciben dos oportunidades de ejecución con un quantum de 1 unidad de tiempo. 

Ejemplo:
Pa y Pc bloquean cada 1 unidad de tiempo
El bloqueo se resuelve tras 2 unidades de tiempo
Colas multinivel:  1. Procesos interactivos (quantum = 1 unidad de tiempo)
                   2. Procesos por lotes    (quantum = 2 unidad de tiempo)    
Inicialmente todos los procesos van a la cola 2
Los procesos que no consuman su quantum al menos una vez pasan a la cola 1
Las colas implementan turno rotatorio estricto.
Siempre que haya procesos en la cola 1, debe ser atendidos de manera preferente frente a la cola 2.
                                                                                        
                    ____|_Pa_|_Pb_|_Pc_|_Pd_|   
         Datos del  _H0_|_0__|_1__|_2__|_3__|   
          problema  _t__|_2__|_4__|_2__|_7__|                      
                                              
                                                      
                      < = 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  |---<xxxxxxx|---|---|---|---|---|xxxxxxx>---|---|---|---|---|---|---|---|---|---|
   Pc  |---|---<---|---|xxx|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
   Pd  |---|---|---<---|---|xxxxxxx|---|---|---|xxxxxxxxxxxxxxxxxxx>---|---|---|---|---|
    $  $---$---|---$---$---$---|---$---$---|---$---|---$---|---$---$---|---|---|---|---|
  -----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> 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__|_4__|_9__|_6__|_12_|        z = índice de penalización
                  _z__|_4/2|_9/4|_6/2|12/7|


4.4. Planificadores de sistemas operativos existentes

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