El planificador con trastorno obsesivo-compulsivo

Sin ánimo de entrar en un debate sobre machismo, un procesador (CPU para los amantes de las siglas) es como todo hombre que se precie, sólo puede trabajar en una única tarea al mismo tiempo. Excluyendo los “modernos” procesadores de varios núcleos, un procesador ejecuta una línea de código, luego otra, luego otra... Vamos, que sólo puede ejecutar instrucciones de una en una, así que para que el usuario pueda hacer más de una cosa al mismo tiempo, o mejor dicho, le parezca que hace más de una cosa al mismo tiempo, tiene que emplear ciertos trucos.

El truco del almendruco, Licencia CC de Wikimedia Commons

Uno de los trucos más básicos, que es de lo primero que se suele explicar cuando se habla de procesadores, es parar lo que sea que el procesador esté haciendo a intervalos regulares de tiempo, mirar si hay algo más que deba ser atendido y, si es necesario, pasar a ejecutar otra tarea.

Por ejemplo, imagina que una tarea muy larga, como calcular de manera ineficiente la serie de números de Fibonacci, está siendo ejecutada. Cada 10 milisegundos (por decir un número, el intervalo de tiempo puede cambiar mucho de un sistema a otro pero suele ser bastante menor en ordenadores domésticos) el planificador interrumpe al procesador y le comunica si hay alguna tarea pendiente de ejecución. En caso afirmativo, cambiará de tarea; si no, seguirá ejecutando la tarea de antes. 

Divide y vencerás es el concepto básico de las tareas. Licencia CC Wikimedia Commons

Imagina que el usuario ha movido el ratón o pulsado una tecla mientras la tarea se está ejecutando, por ejemplo, en el milisegundo 99. El procesador, al que le comunican las tareas pendientes cada 10 milisegundos, llega al milisegundo 100 y su jefe el planificador le dice que el usuario ha pulsado una tecla, que vaya a mirar qué narices quiere el humanoide ahora. Suponiendo que esa planificación y cambio de tarea son instantáneos (mentira cochina, cambiar de tarea siempre tiene un coste por pequeño que sea, pero a efectos prácticos a veces ese coste se ignora), en el mismo milisegundo 100 el procesador deja de calcular números de Fibonacci y ejecuta la subrutina correspondiente a la pulsación de la tecla; pero hay un problema, esa subrutina es demasiado rápida y termina en 4 ms. Entonces estamos en el milisegundo 104, lo que sea que hiciera la tecla ya ha terminado, ¡y el procesador no sabe que hacer! Así que se tumba a la bartola hasta que el pesado del planificador le diga algo. Llega el milisegundo 110 y el planificador le dice que menudo vago esta hecho, pues todavía tiene la secuencia de Fibonacci pendiente por terminar y está inactivo, haciendo nada.

Entonces, en el milisegundo 110, el procesador vuelve a la tarea de antes y continúa lo que estaba haciendo. Cada 10 milisegundos le sigue interrumpiendo el planificador para decirle que su próxima tarea es... la misma tarea que estaba haciendo (como el típico jefe de oficina que no aporta nada, simplemente te dice que hagas lo que ya sabías que tenías que hacer), hasta que llega el milisegundo 250. Resulta que el humanoide ha decidido que es una idea estupenda cerrar una ventana en el escritorio, menudo genio el tío que, mientras el procesador está ocupado haciendo importantes operaciones matemáticas, cree oportuno cerrar una estúpida ventana.

Cerrar una ventana debe ser cosa fina para el procesador porque, pasados 10 ms, todavía no había terminado la tarea. Al planificador le da igual, lo importante es tener sus informes preparados al final del intervalo de tiempo, así que llegado el milisegundo 260, aún con la ventana sin cerrar, le comunica al procesador las malas noticias, y aquí viene lo gracioso. El idiota humanoide no sólo quería cerrar una ventana, ¡sino que ahora quiere abrir otra! Leñe, para eso haz lo que tengas que hacer en una misma ventana, pero no me andes abriendo y cerrando ventanas (en palabras del procesador). Así que el planificador le dice al procesador que abra la dichosa ventana, pero para cuando alcanzamos el milisegundo 270 todavía no está abierta, de hecho, apenas le ha dado tiempo al procesador a calcular el tamaño y posición que tendrá la ventana. No importa, el procesador no puede estar centrado en una misma cosa mucho rato, ahí viene el planificador otra vez a decirle lo qué tiene que hacer.

Este diagrama explica por qué la implementación recursiva de la secuencia de Fibonacci es completamente ineficiente. Licencia CC, Wikimedia Commons.

Llegados a este punto, estamos en el milisegundo 270 y hay 3 tareas pendientes de ejecución: la operación matemática (1), cerrar ventana (2), y abrir ventana (3). El planificador, muy estalinista, le dice al procesador que las tareas tienen todas la misma prioridad y debe dedicar la misma proporción de tiempo a cada una de ellas, así que cada 10 ms va cambiando de tarea hasta que termina con todas. Una vez termina una tarea, la elimina y el intervalo de tiempo será asignado a la tarea que le toque, siempre que esté preparada. Si una tarea no esta preparada porque depende de algún evento externo, sencillamente se salta su turno y se le da el intervalo de tiempo a la siguiente tarea preparada. A continuación un video demostrativo con hasta 4 tareas ejecutándose de manera “simultánea”:

En un diseño convencional una tarea puede tener uno de los siguientes estados:

1. Ejecutándose: Cuando la tarea está siendo ejecutada por el procesador.
2. Preparada: Cuando la tarea podría ser ejecutada en cualquier momento.
3. Bloqueada: Cuando la tarea debe esperar algún otro evento antes de poder ser ejecutada.

Si una tarea ha terminado, simplemente se elimina. Como la tarea ya no existe, no puede tener ninguno de los estados, por eso no hay un estado específico para tareas terminadas. Cabe mencionar que algunas implementaciones sí que poseen estados para ciertas tareas que han terminado su ejecución, pero no suele tener efecto en la planificación de nuevas tareas.

El anterior era un ejemplo de una planificación Round-robin sin prioridades, en otras palabras, es un reparto equitativo de los intervalos de tiempo entre las tareas ejecutándose. Para hacerlo con prioridades, una posible implementación sería incluir diferentes proporciones en la asignación del intervalo de tiempo, al que también se le llama quantum. Si una tarea tiene mayor prioridad que otras, le daríamos un intervalo de tiempo para su ejecución más a menudo, pero mantendremos el intervalo de tiempo igual de largo. En una entrada próxima, la lectura será algo más técnica pero también más interesante, pues hablaremos de interrupciones y sistemas operativos de tiempo real.