Scheduler (planificador)

Una parte importante de un sistema operativo multiprogramable es el planificador de procesos. Evidentemente en un SO monotarea sin concurrencia como MS-DOS no tendría ningún sentido, ya que la tarea que comienza a procesarse, sigue en la CPU hasta que termina.

Entonces se debe repartir el tiempo de ejecución entre los procesos que quieren ejecutarse en cada CPU (o core). Los dividimos en tres tipos

• Long-Term -> Inicia procesos. Realmente en los SO habituales sobre x86 no se efectua ya que son interactivos y es el usuario el que solicita de forma directa o indirecta el comienzo de los procesos.

• Mid-Term -> Decide que procesos es conveniente bloquear para dejar paso a otros en la CPU. También manda al disco procesos que van a tardar en usarse para dejar espacio en la memoria a otros. Además pone en la cola de "preparado" los procesos que ya han superado la causa de su bloqueo

• Short-Term -> El más importante y frecuente. Se llama Dispatcher y entra en acción cuando debe salir un proceso de la CPU porque se le acabó el tiempo (se hace varias veces por segundo según una interrupción hardware) o porque se tuvo que bloquear. También salta cuando llega la indicación de que a un proceso bloqueado se le acabó el bloqueo y puede entrar en la cola de los "ready". Genera el baile en la CPU (llamado context switch) :

  • Coge el proceso que se está ejecutando

    • Guarda su contexto (el estado de ejecución, registros de la CPU y demás) para cuando vuelva a ejecutarse

    • Lo detiene (lo pone en cola 'en espera')

  • Elige según una política de planificación uno de los procesos de la cola de 'en espera'

    • Recoge su contexto guardado

    • Lo escribe en la CPU. Con ello, escribirá en el registro Program Counter la dirección de la siguiente instrucción a ejecutar.

    • Cede el control de CPU al proceso

Para planificarlos se puede hacer de muchas formas. Primero hay que distinguir entre dos tipos de proceso. Los que se interrumpen muy frecuentemente y los que no. Si se interrumpen mucho, puede ser que sea porque está el usuario interactuando (moviendo el ratón, por ejemplo), con lo que tienden a ser respondidos antes que los procesos sin muchas interrupciones. Basándose en ésto y en otras cosas, se crean algoritmos de planificación. Veremos alguno.

• FCFS (First-Come First-Serve, también llamado FIFO). Se van poniendo a la cola los estados 'ready' y según se acaba la tarea de un proceso en la CPU, entra el primero de la cola y se ejecuta hasta el final. Si nos damos cuenta, se sobreentiende que los procesos son cooperativos y que no es necesario que existan interrupciones para sacar al proceso de la CPU.

• Round Robin (el corro de la patata). Parecido al anterior pero aquí si que hay interrupciones; no nos fiamos de lo cooperativos que puedan ser los procesos. Así que cada interrupción hace que se cambie el proceso, que si no ha acabado, se vuelve a poner al final de la cola.

• SJF (Shortest Job First). El dispatcher elige de entre los 'ready', el que parece que tiene el tiempo de ejecución más corto. Es para procesos cooperativos también

• Priority. Se otorga una prioridad a cada proceso y el dispatcher elige siempre ejecutar el más prioritario de los de la cola.

Hay un par de peligros en los algoritmos de planificación de la concurrencia.

• Deadlock (bloqueo). Cuando dos procesos poseen determinados recursos y los dos se quedan bloqueados, a la espera de alguno de los que tiene el otro.

• Starvation (inanición). El proceso no puede avanzar en su ejecución dado que necesita recursos que están (alternativamente) asignados a otros procesos.