Month: December 2009

1. (Kernel Lista) Modifica la cabecera “include/linux/list.h” del kernel para que se pueda

utilizar en un programa de usuario. Escribe un programa que utiliza las funciones de listas enlazadas dentro de list.h para:

• insertar números aleatorios.
• recorrer la lista imprimiendo los valores.
• eliminar un nodo de la lista (utilizando un menú de selección).

2. (Simulador de Procesos) En este problema, queremos estudiar el efecto de diferentes
parámetros relacionado con “timeslice” a diferentes algoritmos de planificación. Escribe un
programa que es simula el comportamiento del gestor de planificación con diferentes valores
de timeslice y para diferentes cargas de cambio de contexto de procesos. Para ello debe
seguir los siguientes pasos:
a) Utilizando su libraría de funciones que ha creado en practicas anteriores, genera los
siguientes datos para procesos que van a querer utilizar el CPU: (i) el PID de cada
procesos, un número aleatorios que representa el tiempo de llegada, y un numero
aleatorio que representa el tiempo total que va a ejecutar en el CPU. Como ejemplo,
los números puede ser como las siguientes:
PID T_llegada            T_total
1        30      0.783560
2         54     17.282004
3         97     32.814522
Que significa que el primer proceso llega a 30 segundos y quiere 0.783560 segundos para ejecutar, el segundo proceso llega a t=54 segundos y necesita 17.28 segundos para ejecutar, ect.
b) Escribe un función que dado los valores generado, es capaz de contar el timeslice y
utilizar planificación de “preemption”, si necesario, para intercambiar procesos cuando
el timeslice de un proceso se agota.
c) Escribe un algoritmo de político “Round Robin”.
d) Escribe un función que calcula el tiempo media de espera y el tiempo media de la tasa de terminar para todos los procesos.
e) Ejecuta su simulación para tiempos de sobrecargo de cambio de contexto de 0, 5, 10, 15, 20 y 25 milisegundos; y por valores de timeslice de: 50, 100, 250, y 500
milisegundos. Hacer gráficos (plots) de lo que encuentras.

Lo primero que tenemos que hacer es copiar la libreria list.h a un archivo nuevo (el kernel de linux no esta en C estándar) y compilar para ver si lo acepta.

Al primer intento nos va a decir que no por las librerías así que tendremos que borrarlas del código

//#include <linux/poison.h>
//#include <linux/prefetch.h>
//#include <asm/system.h>

Volvemos a compilar y tenemos problemas con las variables LIST_POISON esto se produce en las siguientes dos funciones:

• funcion1

static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
//entry->next = LIST_POISON1;
//entry->prev = LIST_POISON2;
}

• funcion2

static inline void hlist_del(struct hlist_node *n)
{
__hlist_del(n);
//n->next = LIST_POISON1;
//n->pprev = LIST_POISON2;
}

Así  ya nos compila el código.

El uso de las listas del kernel difiere del uso clásico que tenemos en mente.

aquí tenemos el esquema de uso de una kernel list

la principal diferencia es que los enlaces de la lista son una estructura dentro de nuestra estructura, por lo tanto no nos movemos a través de nuestra lista sino que vamos accediendo a partes internas de la lista. El principal problema de utilizar este método es acceder a la estructura que contiene los enlaces, esto se realiza mediante el calculo del offset de un puntero.

/*
* getCustomListPointer — gets the customlist memory address from a listPointer calculating the offsett
* listPointer — a pointer that point a list element
*/
struct customList *getCustomListPointer(struct list_head *listPointer)//DONE
{
void * toret=NULL;
toret=listPointer;
//We use a void pointer because i can’t sobrem problems with pointers aritmetic
toret= (toret – ((unsigned long) &((struct customList *)0)->list));
return toret;
}

Toret es un puntero a  void para evitar problemas en la aritmética de punteros, si este fuera un char puntero -1 seria iguar a puntero -1(tamaño char) por lo que tendríamos problemas de fallo de segmento.

La estructura del código se puede observar en el siguiente esquema:

Existen unos pequeños bugs y características no implementadas en la aplicación

• El iterador usa variable global que puede sufrir efectos laterales (las funciones copyCustomList tiene el problema arreglado al ser recursivas y utilizar un registro como indicador de fin de recursividad)
• Habría que mirar el tamaño de una variable void* (si es >1 produce segmentation fault por mal calculo de offset)
• Añadir elemento y otras funciones no esta implementado solo seria añadir una sucesión de printf y scanf en el código.
• No esta implementado el paso de parámetros como por ejemplo establecer el numero de procesos que se simularan (cambiar 15000, por una variable en linea 113 de main.c)

Funcionamiento:

La ejecución muestra por pantalla los datos de cada proceso, timeslice y contextChangue según termina cada proceso,  se ha definido un conjunto de 15000 procesos para sacar estadísticas.

Los ejecución recomendada es ./ejecutable> salida.cvs siendo salida.cvs un archivo comma separated values que se importara a mysql para realizar calculos de forma mas sencilla. La definición de la tabla que se usara esta en el siguiente enlace (Database struct Definitión)

Una vez obtenida la salida la importación a MySql se realiza ejecutando un orden similar a esta.

LOAD DATA LOCAL INFILE’/home/luzem/NetBeansProjects/Practica3/dist/Debug/GNU-Linux-x86/salida.csv’
INTO TABLE roundrobin
FIELDS TERMINATED BY ‘,’
LINES TERMINATED BY ‘\n’

Con esto y un conjunto de consultas SQL podemos obtener los datos para procesar en GNUPLOT.

Gráficas

En  la anterior gráfica podremos ver los efectos del incremento del contextChangue sobre el tiempo medio de espera, observando como el impacto es independiente del timeslice.

El tiempo medio de espera de cada proceso aumenta en función de timeslice y dada que la diferencia entre timeslice y contextchangue es muy alta es el aumento del timeslice quien castiga mas a los tiempos de espera.

En cambio si tenemos en cuenta la media del tiempo total de espera para los conjuntos de timeslice y contextchangue obtenemos la siguiente media

Cuando el timeslice es muy pequeño el numero de cambios de contexto aumenta penaliza el tiempo total de espera de una forma mas que considerable.

Si extraemos el 15% inicial y el 15% final y calculamos las medias para cada segmento obtenemos las siguiente grafica

En la anterior gráfica observamos que el impacto sobre la media de tiempo de espera, afecta mayormente a la parte central del conjunto de procesos.

Mejoras:

Utilizar varias listas round robin con diferente timeslice  y mover los elementos customList en función del contador de paradas (timeslice grande para procesos largos y timeslice pequeño para procesos cortos)