Planificador para niños

El planificador (en inglés, scheduler) es un componente funcional muy importante de los sistemas operativos multitarea y multiproceso, y es esencial en los sistemas operativos de tiempo real. Su función consiste en repartir el tiempo disponible de un microprocesador entre todos los procesos que están disponibles para su ejecución.

Motivación

Todo sistema operativo gestiona los programas mediante el concepto de proceso. En un instante dado, en el ordenador pueden existir diversos procesos listos para ser ejecutados. Sin embargo, solamente uno de ellos puede ser ejecutado (en cada microprocesador). De ahí la necesidad de que una parte del sistema operativo gestione, de una manera equitativa, qué proceso debe ejecutarse en cada momento para hacer un uso eficiente del procesador.

Cómo funciona

Supóngase un ordenador que contiene un único microprocesador. Dicho microprocesador solamente puede ejecutar un programa en cada instante de tiempo. Además, cuando un proceso está ejecutándose, nunca dejará de hacerlo por sí mismo. De manera que, en principio, cualquier proceso monopoliza el microprocesador impidiendo que otros procesos se ejecuten.

Por ello, la primera misión de un planificador es expulsar el programa en ejecución cuando decida que es pertinente. Esto se consigue de dos maneras, siempre con ayuda del propio hardware:

• Cuando expira un temporizador, que se activa a intervalos regulares de tiempo. En intervalos muy cortos, generalmente cada 250 milisegundos.
• Cuando el programa solicita una operación de entrada/salida. Dado que el programa no puede continuar hasta que termine dicha operación, es un buen momento para ejecutar otro programa.

En ambos casos, el control del microprocesador pasa a manos del planificador gracias a que el hardware genera una interrupción. En este proceso de expulsión, se guarda el estado de ejecución del programa (programa y su estado se denomina contexto).

A continuación, el planificador decide cuál será el siguiente proceso en ejecutarse. Naturalmente, solamente se escogen procesos que estén listos para hacerlo. Si un proceso sigue esperando por una operación de entrada/salida no será candidato a ejecutarse hasta que finalice tal operación.

La selección del proceso sigue alguna política de planificación (ver más adelante) preestablecida. Una vez seleccionado un proceso, se procede a ejecutarlo. Para ello, el planificador restaura su estado de ejecución (previamente salvado) y abandona el uso del microprocesador cediéndoselo a dicho proceso.

Nota: se dice que el planificador procede a ejecutarlo a modo ilustrativo, entrando un poco más en detalle el planificador envía su lista de procesos al 'dispatcher' (despachador) para que este adecue al proceso y su PCB para la inmediata ejecución. Todo esto apenas dura unos pocos milisegundos.

Gracias a que el tiempo del microprocesador se reparte entre todos los procesos a intervalos muy cortos, el ordenador ofrece la sensación de que todos los procesos están ejecutándose a la vez (ejecución concurrente).

Cuando un ordenador tiene varios microprocesadores (véase arquitectura NUMA y SMP), este esquema se repite para cada microprocesador.

Tiempo real

Un sistema operativo en tiempo real se caracteriza por garantizar que todo programa se ejecutará en un límite máximo de tiempo. El planificador debe comportarse de manera que esto sea cierto para cualquier proceso.

En estos casos, la finalidad del planificador es balancear o equilibrar la carga del procesador, impidiendo que un proceso monopolice el procesador o que sea privado de los recursos de la máquina. En entornos de tiempo real, como los dispositivos para el control automático en la industria (por ejemplo, robots), el planificador también impide que los procesos se paren o interrumpan a otros que esperan que se realicen ciertas acciones. Su labor resulta imprescindible para mantener el sistema estable y funcionando.

Niveles de planificación

Los niveles de planificación están basados en la frecuencia con la que se realiza cada uno.

En los sistemas operativos de propósito general, existen tres tipos de planificadores. El planificador a corto plazo es el que se ha descrito aquí, siendo también el más importante. En inglés, se denomina dispatcher o short term scheduler, también existe un planificador a medio plazo (en inglés, mid term scheduler) relacionado con aquellos procesos que no se encuentran en memoria principal (véase memoria virtual). Su misión es mover procesos entre memoria principal y disco (lo que se conoce como swapping) y por último existe el planificador a largo plazo (en inglés long term scheduler) es el encargado de ingresar nuevos procesos al sistema y de finalizarlos.

Políticas de planificación

A continuación se enumeran diversas políticas de planificación. Lo habitual es utilizar políticas mixtas. Generalmente, el planificador a corto plazo utiliza round-robin, mientras que el planificador a largo plazo utiliza varias colas FIFO (First In First Out). Cada una de estas colas corresponde a una prioridad diferente.

• Planificación Round-robin
• Round-robin con pesos.
• Prioridades monótonas en frecuencia (RMS (Rate-monotonic scheduling))
• Menor tiempo de respuesta primero (EDF (Earliest deadline first scheduling))
• FIFO - También conocido como FCFS "First Come, First Served".
• LIFO.
• SJF - Shortest Job First.
• CFS - Completely Fair Scheduler (ó Planificador Completamente Justo)
• SRT - Shortest Remaining Time
• SPT - Shortest Process Time

• Planificación mediante colas multinivel.

Tipos de algoritmos

Existen dos tipos de algoritmos de calendarización (políticas de planificación), expropiativos y no expropiativos. Los expropiativos asignan un tiempo de ejecución a cada proceso después del cual se calendariza otro proceso, hasta que cada proceso acabe su trabajo. También pueden expulsar a un proceso en ejecución si llega otro de mayor prioridad que necesita ejecutarse. Los no expropiativos permiten que se ejecute el proceso hasta que acabe su trabajo. Es decir, una vez les llega el turno de ejecutarse, no dejarán libre la CPU hasta que terminen o se bloqueen.

Véase también

En inglés: Scheduling (computing) Facts for Kids