En los sistemas GNU/Linux existen una gran variedad de comandos básicos de monitorización tales como: time, vmstat, iostat, gcov, gprof, top y otros. A continuación se desarrolla una experiencia del uso de dichos comandos para monitorizar distintos algoritmos de ordenamiento desarrollados en C, tales como: Bublesort, Quicksort y Mergesort. Estos algoritmos se prueban en base a un archivo de aproximadamente 20 MBytes que contiene numeros al azar linea a linea. El objetivo de cada ordenador es recibir este archivo y generar un nuevo archivo con los numeros ordenados. Finalmente, en base a los resultados arrojados por los diferentes comandos de monitorización, se comparan los 3 algoritmos concluyendo cual resulta ser más eficiente.
Se desarrollan 2 experiencias distintas con los 3 algoritmos: la monitorizacion ordenando el archivo de 20mb desde un disco interno a un disco externo, y la monitorización ordenando el archivo en el mismo disco interno.
A continuación se presentan los videos correspondientes a cada experiencia:
I) Ordenamiento desde un Disco Interno a un Disco Externo.
B.- Quicksort.
C.- Mergesort.
II) Ordenamiento en el mismo Disco Interno.
Resultados de la Monitorización.
A.- Bublesort.
- Tiempo de ejecución usando time:
16 horas y más (no se conocio el limite durante esta experiencia). - Estadisticas de tiempo usando gprof:
Por la larga duración del programa no fue posible generarlas. - Graficas hechas con gnuplot utilizando los datos recopilados con iostat y vmstat:
- Lectura y Escritura en Kb/s en el disco interno durante el tiempo que duro la experiencia.
- Lectura y Escritura en Kb/s en el disco externo durante el tiempo que duro la experiencia.
- Uso de CPU durante el tiempo que duro la experiencia.
B.- Quicksort.
- Tiempo de ejecución usando time:
real 34m11.146s
user 1m17.861s
sys 20m39.873s - Estadisticas de tiempo usando gprof:
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
99.88 29.99 29.99 1 29.99 30.03 quicksort
0.12 30.02 0.04 25819006 0.00 0.00 swap
0.03 30.03 0.01 6000001 0.00 0.00 escribirUnNumero
0.03 30.04 0.01 5999000 0.00 0.00 choose_pivot
0.03 30.05 0.01 1 0.01 30.05 ordenarArchivo - Graficas hechas con gnuplot utilizando los datos recopilados con iostat y vmstat:
- Lectura y Escritura en Kb/s en el disco interno durante el tiempo que duro la experiencia.
- Lectura y Escritura en Kb/s en el disco externo durante el tiempo que duro la experiencia.
- Uso de CPU durante el tiempo que duro la experiencia.
C.- Mergesort.
- Tiempo de ejecución usando time:
real 32m35.778s
user 0m2.812s
sys 20m58.487s - Estadisticas de tiempo usando gprof:
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ms/call ms/call name
55.99 0.33 0.33 5999999 0.00 0.00 mezclar
39.02 0.56 0.23 1 230.23 560.55 mezcla
3.39 0.58 0.02 1 20.02 590.58 ordenarArchivo
1.70 0.59 0.01 6000001 0.00 0.00 escribirUnNumero - Graficas hechas con gnuplot utilizando los datos recopilados con iostat y vmstat:
- Lectura y Escritura en Kb/s en el disco interno durante el tiempo que duro la experiencia.
- Lectura y Escritura en Kb/s en el disco externo durante el tiempo que duro la experiencia.
- Uso de CPU durante el tiempo que duro la experiencia.
II) Ordenamiento en el mismo Disco Interno.
A.- Bublesort.
- Tiempo de ejecución usando time:16 horas y más (no se conocio el limite durante esta experiencia).
- Estadisticas de tiempo usando gprof:
Por la larga duración del programa no fue posible generarlas. - Graficas hechas con gnuplot utilizando los datos recopilados con iostat y vmstat:
- Lectura y Escritura en Kb/s en el disco interno durante el tiempo que duro la experiencia.
- Lectura y Escritura en Kb/s en el disco externo durante el tiempo que duro la experiencia.
- Uso de CPU durante el tiempo que duro la experiencia.
B.- Quicksort.
- Tiempo de ejecución usando time:real 1m29.388s
user 0m41.251s
sys 0m47.659s
- Estadisticas de tiempo usando gprof:
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
98.17 29.78 29.78 1 29.78 29.89 quicksort
1.15 30.14 0.35 6000001 0.00 0.00 escribirUnNumero
0.43 30.27 0.13 1 0.13 30.37 ordenarArchivo
0.30 30.36 0.09 25819006 0.00 0.00 swap
0.05 30.37 0.02 5999000 0.00 0.00 choose_pivot - Graficas hechas con gnuplot utilizando los datos recopilados con iostat y vmstat:
- Lectura y Escritura en Kb/s en el disco interno durante el tiempo que duro la experiencia.
- Lectura y Escritura en Kb/s en el disco externo durante el tiempo que duro la experiencia.
- Uso de CPU durante el tiempo que duro la experiencia.
C.- Mergesort.
- Tiempo de ejecución usando time:real 0m58.518s
user 0m12.069s
sys 0m46.267s
- Estadisticas de tiempo usando gprof:
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
42.51 0.62 0.62 5999999 0.00 0.00 mezclar
28.80 1.04 0.42 6000001 0.00 0.00 escribirUnNumero
21.25 1.35 0.31 1 0.31 0.93 mezcla
7.54 1.46 0.11 1 0.11 1.46 ordenarArchivo - Graficas hechas con gnuplot utilizando los datos recopilados con iostat y vmstat:
- Lectura y Escritura en Kb/s en el disco interno durante el tiempo que duro la experiencia.
- Lectura y Escritura en Kb/s en el disco externo durante el tiempo que duro la experiencia.
- Uso de CPU durante el tiempo que duro la experiencia.
Conclusiones.
- Considerando que el algoritmo de ordenamiento BubleSort es de orden n^2, el ordenamiento de un archivo que cuenta con alrededor de 6 millones de datos, se podria decir que su tiempo de ejecución podria extenderse por años.
- Comparando el uso de la CPU de Bublesort con los otros 2 algoritmos, se puede ver claramente que fue más extenso el uso del BubleSort que el QuickSort y el MergeSort.
- En cuanto a la lectura y escritura ejecutando el programa con BubleSort de un disco interno a un disco externo o en el mismo disco se puede ver que: cuando se lleva a cabo el ordenamiento, se puede observar en las graficas correspondiente, que la lectura y escritura de datos se hace mayor cantidad de veces para el caso del disco externo.
- En cuanto a los algoritmos QuickSort y MergeSort, en tiempo de ejecución son similares, pero con algunas diferencias en la lectura y escritura de datos, ya que su implementación es distinta, pero a lo que se refiere a procesos del sistema, sus tiempos son parecidos. El comportamiento con la CPU y dispositivos I/O son similares.
- Viendo las graficas, se puede ver que para el caso del disco externo hubo mayor proceso de lectura y escritura que para el caso del mismo disco interno.
Fuentes:
