Dentro del núcleo Linux 2.4 - Planificador Linux

El trabajo de un planificador es decidir el acceso a la actual CPU entre múltiples procesos. El planificador está implementado en el 'archivo principal del núcleo' kernel/sched.c. El archivo de cabeceras correspondiente include/linux/sched.h está incluido virtualmente (explícita o implicitamente) en todos los archivos de código fuente del núcleo.

Los campos de una estructura de tareas relevante a planificar incluyen:

• p->need_resched: este campo es establecido si schedule() debería de ser llamado en la 'siguiente oportunidad'.
• p->counter: número de ticks de reloj que quedan en esta porción de tiempo del planificador, decrementada por un cronómetro. Cuando este campo se convierte a un valor menor o igual a cero, es reinicializado a 0 y p->need_resched es establecido. Esto también es llamado a veces 'prioridad dinámica' de un proceso porque puede cambiarse a si mismo.
• p->priority: la prioridad estática del proceso, sólo cambiada a través de bien conocidas llamadas al sistema como nice(2), POSIX.1b sched_setparam(2) o 4.4BSD/SVR4 setpriority(2).
• p->rt_priority: prioridad en tiempo real.
• p->policy: la política de planificación, específica a la clase de planificación que pertenece la tarea. Las tareas pueden cambiar su clase de planificación usando la llamada al sistema sched_setscheduler(2). Los valores válidos son SCHED_OTHER (proceso UNIX tradicional), SCHED_FIFO (proceso FIFO en tiempo real POSIX.1b) y SCHED_RR (proceso en tiempo real round-robin POSIX). Uno puede también SCHED_YIELD a alguno de esos valores para significar que el proceso decidió dejar la CPU, por ejemplo llamando a la llamada al sistema sched_yield(2). Un proceso FIFO en tiempo real funcionará hasta que: a) se bloquee en una E/S, b) explícitamente deje la CPU, o c) es predesocupado por otro proceso de tiempo real con un valor más alto de p->rt_priority. SCHED_RR es el mismo que SCHED_FIFO, excepto que cuando su porción de tiempo acaba vuelve al final de la cola de ejecutables.

EL algoritmo de planificación es simple, olvídate de la gran complejidad aparente de la función schedule(). La función es compleja porque implementa tres algoritmos de planificación en uno y también porque disimula los específicos de SMP.

Las aparentemente 'inservibles' etiquetas (gotos) en schedule() están allí con el propósito de generar el mejor código optimizado (para i386). También, destacar que el planificador (como la mayoría del núcleo) fue totalmente reescrito para el 2.4, entonces la discusión de más abajo no se aplica a los núcleos 2.2 o anteriores.

Déjanos mirar la función en detalle:

1. Si current->active_mm

   NULL entonces algo está mal. El actual proceso, incluso un hilo del núcleo (current->mm

   NULL) debe de tener un p->active_mm válido durante todo el tiempo.
2. Si hay algo que hacer en la cola de tareas tq_scheduler, entonces se procesa ahora. La cola de tareas suministra al núcleo un mecanismo para planificar la ejecución de las funciones más tarde. Lo miraremos en detalle en otra parte.
3. Se inicializan las variables locales prev y this_cpu a las tareas y CPUs actuales, respectivamente.
4. Se chequea si schedule() fue llamada desde el controlador de interrupciones (debido a un fallo) y provoca un pánico si ha sido así.
5. Se quita el cierre global del núcleo.
6. Si hay algún trabajo que hacer a través del mecanismo de softirq, se hace ahora.
7. Se inicializa el puntero local struct schedule_data *sched_data para que apunte a cada CPU (alineado de la linea de antememoria para prevenir que la linea de antememoria salte) planificando el área de datos, el cual contiene el valor TSC de last_schedule y el puntero a la última estructura planificada (POR HACER: sched_data es usada sólo en SMP, ¿pero porqué inicializa también init_idle() en UP (monoprocesadores)?
8. Es tomado el spinlock runqueue_lock. Destacar que usamos spin_lock_irq() porque en schedule() garantizamos que las interrupciones están habilitadas. Por esto, cuando abrimos runqueue_lock, podemos rehabilitarlas en vez de salvar/restaurar las eflags (variante spin_lock_irqsave/restore).
9. Estado de tareas de la máquina: si la tarea está en el estado TASK_RUNNING entonces se deja sólo, si está en el estado TASK_INTERRUPTIBLE y hay una señal pendiente, es movido al estado TASK_RUNNING. En todos los otros casos es borrado de la cola de ejecución.
10. next (mejor candidato para ser planificado) es establecido a la tarea vacía de esta CPU. En todo caso, la virtud de este candidato es establecida a un valor muy bajo (-1000), con la esperanza de que haya otro mejor que él.
11. Si la tarea prev (actual) está en el estado TASK_RUNNING entonces la actual virtud es establecida a su virtud y es marcado como mejor candidato para ser planificado que la tarea vacía.
12. Ahora la cola de ejecución es examinada y una virtud de cada proceso que puede ser planificado en esta CPU es comparado con el actual valor; el proceso con la virtud más alta gana. Ahora el concepto de "puede ser planificado en esta CPU" debe de ser clarificado: en UP, todos los procesos en la cola de ejecución son elegibles para ser planificados; en SMP, sólo los procesos que no estean corriendo en otra CPU son elegibles para ser planificados en esta CPU. La virtud es calculada por una función llamada goodness(), la cual trata los procesos en tiempo real haciendo sus virtudes muy altas (1000 + p->rt_priority), siendo mayor que 1000 se garantiza que no puede ganar otro proceso SCHED_OTHER; por lo tanto sólo compiten con los otros procesos en tiempo real que quizás tengan un mayor p->rt_priority. La función virtud devuelve 0 si la porción de tiempo del proceso (p->counter) se acabó. Para procesos que no son en tiempo real, el valor inicial de la virtud es establecido a p->counter - por este camino, el proceso tiene menos posibilidades para alcanzar la CPU si ya la tuvo por algún tiempo, esto es, los procesos interactivos son favorecidos más que el límite de impulsos de la CPU. La constante específica de la arquitectura PROC_CHANGE_PENALTY intenta implementar la "afinidad de cpu" (esto es, dar ventaja a un proceso en la misma CPU). También da una ligera ventaja a los procesos con mm apuntando al actual active_mm o a procesos sin espacio de direcciones (de usuario), esto es, hilos del núcleo.
13. si el actual valor de la virtud es 0 entonces la lista entera de los procesos (¡no sólo los de la lista de ejecutables!) es examinada y sus prioridades dinámicas son recalculadas usando el simple algoritmo:

---

recalculate:
{
struct task_struct *p;
spin_unlock_irq(&runqueue_lock);
read_lock(&tasklist_lock);
for_each_task(p)
p->counter = (p->counter >> 1) + p->priority;
read_unlock(&tasklist_lock);
spin_lock_irq(&runqueue_lock);
}

---

Destacar que tiramos el runqueue_lock antes de recalcular. El motivo para esto es que vamos a través del conjunto entero de procesos; esto puede llevar un gran tiempo, durante el cual el schedule() puede ser llamado por otra CPU y seleccionar un proceso con la suficiente virtud para esta CPU, mientras que nosotros en esta CPU seremos obligados a recalcular. Muy bien, admitamos que esto es algo inconsistente porque mientras que nosotros (en esta CPU) estamos seleccionando un proceso con la mejor virtud, schedule() corriendo en otra CPU podría estar recalculando las prioridades dinámicas.

1. Desde este punto, es cierto que next apunta a la tarea a ser planificada, por lo tanto debemos de inicializar next->has_cpu a 1 y next->processor a this_cpu. La runqueue_lock puede ahora ser abierta.
2. Si estamos volviendo a la misma tarea (next

   prev) entonces podemos simplemente readquirir un cierre global del núcleo y volver, esto es, saltar todos los niveles hardware (registros, pila, etc.) y el grupo relacionado con la VM (Memoria Virtual) (cambiar la página del directorio, recalcular active_mm etc.)

3. La macro switch_to() es específica de la arquitectura. En i386, es concerniente con: a) manejo de la FPU (Unidad de Punto Flotante), b) manejo de la LDT, c) recargar los registros de segmento, d) manejo de TSS y e) recarga de los registros de depuración.