Planificación por prioridades en Minix

De eso se trató el TP2 de DISO (Diseño e implementación de Sistemas Operativos). Al terminar de implementar una idea de cómo hacerlo, debíamos correr un programa dos veces, cambiarle la prioridad a uno de los dos, y verificar que uno imprimía más veces su pid que el otro.

El enunciado era claro, y guiaba bastante en cómo hacerlo. Además ya habíamos asistido a una clase de práctica, por lo que no deberían haber aparecido complicaciones mayores. Aunque en realidad no terminó siendo así.

Estaría muy bueno saber cómo hace la gente del kernel Linux para debuggearlo. Pablo Pessolani, el profesor de teoría y titular de DISO, nos explicaba que la técnica consiste en usar la muy conocida función printf, así de simple. Luego de reflexionarlo un poco, la verdad es que no parece haber otra alternativa. Siguiendo la misma estrategia, así fue como testeamos el código modificado de Minix 2.0.2 para completar el trabajo práctico 2.

Sin embargo me quedó la pica de cómo hacen los hackers de Linux para testear sus modificaciones. Pensaba que quizá tengan alguna forma más cómoda y adecuada. Entonces averigué qué técnicas utilizan, por simple curiosidad, y me sorprendió un poco el descubrimiento.

Pablo nos contó que él programó driveres para Linux. Si él dice que se usa la función printf, hay que creerle. Y así es. Se depura con trazas, o por lo menos es una de las formas más sencillas de hacerlo. Como el kernel Linux no enlaza con la librería C estándar, glibc, utiliza su propia función para el mismo fin, llamada printfk. Se la puede utilizar casi en cualquier parte del mismo, menos en el proceso de arranque, ya que la consola debe estar inicializada.

A esta información la saqué de éste artículo. Me encanta a la conclusión que llega el mencionado texto:

Como conclusión hacer mención a una sugerente reflexión que Robert Love hace en su excelente libro: cuando empecemos a hackear el kernel, con frecuencia usaremos la función printf() en vez de printk(), no podremos evitar la tendencia natural de muchos años de uso de esa función, en nuestros programas de espacio de usuario. Pero algún día, escribiendo un simple programa de usuario cometeremos el error contrario, usaremos printk() en vez de printf(). Cuando ese día llegue, podremos decir que somos unos verdaderos kernel hacker.

kernel-labs.org es un sitio muy recomendado para buscar información, en castellano, del kernel Linux.

Volviendo, y recordando esa limitación de uso del printfk en Linux, quizá en Minix haya algo parecido. Recuerdo cuando toqué una parte del Memory Manager, agregando un printf, y el kernel directamente no booteaba. Necesitaba ver la lista de procesos listos (rdy_head[USER_Q]), ya que no entendía por qué no funcionaba algo. Entonces lo que hice fue, en el código para visualizar dicha lista, llamar a la función printf sólo cuando el proceso sh estaba corriendo. Funcionó.

Minix posee una cola de procesos listos, como dije antes. La estructura de información de cada proceso posee un puntero al siguiente proceso listo. Así, dicha cola es accesible desde un array, rdy_head[USER_Q] (cabeza de la cola). rdy_head[SERVER_Q], por ejemplo, es un puntero al primer servidor (Memory Manager, File System Manager, etc) listo. Lo mismo con rdy_head[TASK_Q], pero para las tareas. En realidad Minix sí usa prioridadades a nivel global, digamos, porque primero se fija si hay tareas listas, si no es así, ejecuta los servidores listos. Si no hay servers listos, entonces recién pasa a los programas de usuario. Es allí donde teníamos que implementar un planificador por prioridades, ya que lo que hace Minix es, simplemente, luego de finalizado el timeslice del proceso que se estaba ejecutando, ponerlo al final de la cola, y ejecutar el siguiente.

El enunciado del TP nos indicaba agregar, en la estructura de procesos, una campo, priority, para almacenar la prioridad de cada proceso, que luego iba poder ser modificada a traves de una llamada al sistema. ¿Cómo implementarían dicha funcionalidad sin matar por inanición a los demás procesos? Es decir, que todos reciban por lo menos algo de CPU, a pesar de existir procesos con mayor prioridad, pero haciendo valer el derecho de algunos a ejecutarse una mayor cantidad de tiempo.

El profesor nos indicó que, para nuestra idea, con un sólo campo (priority) no era suficiente. Entonces agregamos otro, llamado penalty. Se nos ocurrió penalizar a los procesos de la siguiente forma: Inicializar todos los procesos, incluso aquellos forkeados desde procesos con mucha prioridad, con el campo priority en 15 (la menor prioridad), y el campo penalty en cero. Cuando a un proceso se le termina su timeslice, se le suma al campo penalty su prioridad, y se reubica en la lista de procesos listos, ordenados por ambos valores: priority y penalty. Es decir, un proceso con prioridad 10 y penalidad 0, al terminar de ejecutarse, tendría una penalización de 10, se reubicaría en la lista, en caso de seguir siendo el de mayor prioridad (recordar que se ubican por el resultado de priority + penalty) continua teniendo la CPU, y al vencer nuevamente su cuanto tendría en su campo penalty un valor de 20. De esta forma, en algún momento iba a tener un valor priority + penalty mayor a su siguiente proceso listo, lo que efectivamente probocaría un cambio en el siguiente proceso a ejecutarse. Esta idea inicial iba a funcionar, pero no sin algunos retoques.

Un problema que puede surgir es que el campo penalty llegue al límite del tipo de datos long. En ese caso, si no me equivoco, la penalidad pasaría a tener el valor más pequeño (que es negativo), y el proceso se ubicaría siempre al principio de la cola, monopolizando el procesador por un tiempo muy largo. Podríamos haber utilizado un tipo unsigned long para el campo penalty, aunque tampoco funcionaría, por la misma razón.

Otra cosa: ¿qué pasa si el campo penalty va por el valor, en promedio, 10000, y se crea un nuevo proceso? La respuesta es que el nuevo proceso (con penalidad igual a cero) tendría la CPU hasta que la suma de su prioridad base más la penalización superen el valor de 10000. En algún momento el efecto acabaría, pero es molesto, obviamente. La solución (hay otras, pero ésta es la que elegimos) es volver a cero todos los campos penalty de todos los procesos, dadas ciertas condiciones. Esto no se puede hacer aleatoriamente, ya que si la lista consta de procesos con las siguientes prioridades: 1 – 1 – 5 – 15 – 1, y todas las penalizaciones se vuelven a cero, ese último proceso de prioridad 1 no estaría utilizando la CPU como le corresponde.

La condición suficiente (las pruebas parecían indicar que no estabamos equivocados en esto), es la siguiente: si un proceso, al acabarse su timeslice, se ubica al final de la cola, y el proceso siguiente a éste posee una prioridad menor, entonces todos los campos penalty se setean a cero.

En definitiva, hay muchos incovenientes, y cosas para pensar. Quizá se nos escapó algún caso que provoca un error, pero nuestra implementación, al momento de entrega del TP, parecía funcionar.

Pueden bajarse el código fuente de los archivos modificados, más el documento que entregamos, desde la página de apUnTN (un proyecto de unos compañeros de la facu, en la que pueden encontrar varios tps, de varias materias), en éste link.

Publicado por

miltondp

Soy Ingeniero en Sistemas de Información y actualmente vivo en la ciudad de Santa Fe (Capital), Argentina. Estoy haciendo un Doctorado en Ingeniería, y me gusta mucho leer, y de vez en cuando escribir.