Algoritmo de planificación de procesos similar al de Linux

Práctica de carácter optativo. El desarrollo satisfactorio de la misma puede proporcionar un punto más en la nota total. Sólo se podrá realizar esta práctica una vez que se ha completado satisfactoriamente la práctica obligatoria. La funcionalidad que se plantea en esta práctica se puede incluir en la versión obligatoria de la práctica o, si ya se ha desarrollado otra práctica optativa, puede juntarse con esta, aunque no obligatoriamente. Idealmente, un alumno podría desarrollar una única versión de la práctica que incluyera toda la funcionalidad planteada en los distintos enunciados.

Descripción de la funcionalidad pedida

El objetivo de esta práctica es enfrentar al alumno con un algoritmo de planificación basado en uno real, concretamente el de Linux (en su versión 2.4), para que, así, el alumno puede apreciar la complejidad de los algoritmos reales. Este algoritmo tiene las siguientes características:

  • Es un esquema de prioridades dinámicas de carácter expulsivo.
  • Cada proceso tiene una prioridad base de carácter estático, que corresponde con un valor entero entre 10 (mínima) y 50 (máxima).
  • La prioridad efectiva de un proceso se calcula a partir de su prioridad estática y su perfil de ejecución. Esta prioridad efectiva es la que se usa a la hora de determinar qué proceso debe ejecutar.
  • Cada proceso inicialmente tiene asociada una prioridad estática heredada del padre.
  • La prioridad efectiva inicial de un proceso es igual a su prioridad estática.
  • El proceso “init” tiene inicialmente la prioridad mínima.
  • En este esquema existen rodajas de tiempo pero su tamaño es proporcional a la prioridad efectiva del proceso (por ejemplo, si un proceso tiene una prioridad efectiva de 40, su rodaja corresponde con 40 interrupciones de reloj).
  • En cada interrupción de reloj se decrementa la prioridad efectiva del proceso actual. Si llega a cero, el proceso en ejecución deja el procesador y se selecciona el proceso con mayor prioridad efectiva.
  • Cuando la prioridad efectiva de todos los procesos listos para ejecutar sea igual a cero, se realiza un reajuste de las prioridades de todos los procesos mediante la siguiente fórmula: prioridad efectiva = prioridad efectiva / 2 + prioridad estática
  • Siempre que se despierta un proceso hay que comparar su prioridad efectiva con la del actual y activar una interrupción software de planificación en caso de que sea mayor.
  • Un proceso puede cambiar su prioridad mediante la llamada: “int fijar_prio(unsigned int prio)”
  • La llamada “fijar_prio” reajustará ambas prioridades del proceso. Por lo que se refiere a la prioridad estática, simplemente se le asigna el valor especificado como parámetro de la llamada. El cálculo de la nueva prioridad efectiva necesita, sin embargo, una pequeña explicación. Puesto que este valor refleja una mezcla de dos aspectos, por un lado la prioridad estática del proceso y por otro su perfil de ejecución (mayor uso del procesador implica menor prioridad efectiva), se debe calcular la nueva prioridad efectiva teniendo en cuenta el cambio de la prioridad estática de manera que se mantenga la proporción existente previamente entre ambas.
  • Nótese que la llamada al sistema “fijar_prio”, en el caso de que el proceso en ejecución baje su prioridad, lo que afectará tanto a la prioridad estática como a la efectiva, puede requerir un cambio de contexto involuntario si hay un proceso listo con más prioridad efectiva.
  • La prioridad no sólo se usará como criterio de reparto del procesador, sino que también se deberá aplicar cuando varios procesos compiten por un recurso de uso exclusivo. Si hay varios procesos bloqueados esperando para usar un determinado recurso, cuando éste quede libre, deberá obtenerlo el proceso más prioritario.
  • En resumen, se podrá producir un cambio de contexto involuntario cuando se termina la rodaja del proceso actual, cuando se desbloquea un proceso con mayor prioridad efectiva que el que está ejecutando, ya sea como consecuencia de una interrupción o de una llamada, o al bajar la prioridad llamando a “fijar_prio”. Puesto que en el minikernel, al ser un núcleo no expulsivo, no se permiten los cambios de contexto involuntarios mientras el proceso está ejecutando en modo sistema, cuando se despierte un proceso que tenga mayor prioridad efectiva que el actual, se activará una interrupción software de planificación.

Si se pretende incluir esta funcionalidad sobre una versión con threads, toda la estrategia de planificación planteada se aplicará en el nivel de threads (así, cada thread tendrá su propia prioridad base y efectiva, la prioridad base de un thread la heredará del thread que lo crea, que podrá pertenecer al mismo proceso o al proceso padre, en el caso de la creación del thread inicial de un proceso).

Código fuente de apoyo

Para la realización de esta práctica se tomará como base el código desarrollado en la práctica obligatoria del minikernel (o de forma acumulada en el código de alguna(s) de las prácticas optativas). Para poder trabajar en esta práctica sin afectar al código de la parte obligatoria y poderla entregar de manera independiente, se debe copiar a un nuevo directorio denominado “minikernel_planif.2023”. Desde el directorio base del usuario, se pueden ejecutar los siguientes mandatos para realizar esta copia:

$ mkdir DATSI/SOA/minikernel_planif.2023
$ cp -R DATSI/SOA/minikernel.2023/* DATSI/SOA/minikernel_planif.2023

Documentación que se debe entregar

El mandato a ejecutar en la máquina <tt>triqui.fi.upm.es</tt> es:

entrega.soa minikernel_planif.2023

Este mandato realizará la recolección de los mismos ficheros que en la práctica obligatoria del minikernel.

No existe un corrector automático para esta práctica. El alumno deberá usar sus propios programas de prueba.

Las prácticas entregadas serán corregidas una vez terminado el plazo de entrega, que es el mismo de las prácticas obligatorias.

 
docencia/asignaturas/soa/practicas/minikernel_planificacion.txt · Última modificación: 2023/01/30 22:53 por fperez
 
Recent changes RSS feed Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki