Algoritmos de planificación

Existen distintos algoritmos empleados para realizar la planificación. El más sencillo de ellos es el PESP (Primero en Entrar, Primero en Salir o FIFO en inglés, First Input First Output), en el cual no se libera la CPU hasta que no termina el proceso en ejecución y los tiempos de respuesta varían fuertemente de un momento a otro, según el orden de llegada a la CPU de los procesos.

           EJEMPLO 1.1

          Tenemos tres procesos con distintos tiempos de procesamiento:

          Proceso 1: 18 Unidades

          Proceso 2: 6 Unidades

          Proceso 3: 6 Unidades

          Los ejecutamos atendiendo al algoritmo FIFO y (no estamos teniendo en cuenta la prioridad de los procesos).

          En el primer caso:

                     PROCESO 1 ------------ PROCESO 2 ------------ PROCESO 3

          Estudiando el tiempo medio de retorno, es decir, el tiempo medio que se tarda en finalizar un proceso, tendremos: (18+24+30)/3=24

          En el segundo caso, el orden de llegada de los procesos es otro:

          PROCESO 2 ------------ PROCESO 3 ------------ PROCESO 1

          El tiempo medio de retorno en este caso será: (6+12+30)/3=16. Al hacer la media se aprecia que los procesos están menos tiempo esperando.

          Se observa que, empleado el algoritmo FIFO, si apareciera una tarea crítica que requiriese atención inmediata, ésta debería esperar a la finalización de las tareas en cola.

----------------------------------------------------------------------------------------------

          Otro tipo de algoritmo de planificación es el SJF (Shortest Job First), es decir, el trabajo más corto se ejecuta primero. Este algoritmo asigna la CPU al trabajo que requiere menor tiempo de proceso.

          La dificultad reside en saber cual de los procesos en esperar de ser ejecutados tendrá menor tiempo de proceso, para ello se emplean algoritmos de predicción que calculan el siguiente tiempo de ejecución de un proceso como una media exponencial de los tiempos de las últimas ejecuciones de esa parte de código.

         El problema que puede presentarse es que vayan entrando a la cola de espera de ejecución los procesos cortos y, los procesos largos que estén esperando, no se ejecuten nunca. Para evitar esto, se emplean técnicas de envejecimiento de procesos, aumentando la prioridad de los procesos que llevan mucho tiempo inactivo.

Figura 1.2. Planificación Round Robin

Uno de los algoritmos más sencillos, justo y de uno más amplio es el Round  Robin. En su utilización no se establecen  prioridades, cada proceso tiene asignado un tiempo de ejecución denominado quantum; si se cumple ese tiempo y la tarea no ha concluido, se da paso al siguiente proceso y el proceso no finalizado pasa al final de la lista de proceso en espera.