( mediante procesos de ejecución concurrente )
Planteamiento:
NOMBRE:
ordena
- ordena fichero de enteros
SINOPSIS:
ordena
nombre_de_fichero
DESCRIPCION:
Programa
que ordena números enteros de un fichero por el
método del QUICKSORT. El resultado de la ordenación se vuelca
sobre el mismo
fichero a continuación de los datos sin ordenar. Se vale de procesos
de ejecución
en forma concurrente.
Como
mejora del programa se ha buscado el tamaño óptimo de
partición para el cual ya no es rentable generar procesos y lo mejor
es continuar
con una ejecución en forma secuencial.
DIAGNOSTICOS:
Tenemos
varias condiciones de error en el programa. Al darse alguna
de ellas, el programa abortará y dará un mensaje de error
por la salida estándar 'stderr'.
Este mensaje proporciona una breve explicación de por qué
ha ocurrido el fallo en el
programa.
BUGS:
El
'vi' no soporta ficheros de tamaño "medianamente grande",
de más
de 200 elementos ( aprox.), con los que podemos tener algún problema,
tanto a la hora de
crearlos, como a la hora de volcar el resultado sobre el fichero.
AUTORES:
Montserrat
Encinas Villota
Antº
Manuel Herrera Fernández
"Sistemas Operativos" - 3º Diplomatura en Estadística.
Facultad de Ciencias (Valladolid), Junio 1998.
Solución:
Como
solución al problema antes planteado se propone un programa que
se ajuste a nuestras necesidades, como es ordena.c
En
ordena.c, además de dar respuesta a la ordenación por el
método de
'quicksort' de forma concurrente, se ha buscado el tamaño óptimo
de partición a partir del
cual sigamos ordenando de forma secuencial y disminuya el tiempo de ejecución
del programa.
No merece la pena generar procesos cuando el tamaño del array a
ordenar, o de la partición
que tengamos, sea lo suficientemente pequeño.
Típicamente
tenemos buenos resultados si dicho tamaño es menor que
[nelm/10]+1, cuando el fichero es de menos de 100 elementos ( nelem es
el nº de elementos
a ordenar ); si el fichero contiene más de 100 números, se
ordena de forma secuencial a partir
de particiones de menos de 10 elementos.
Si
tomamos un fichero ejemplo de tamaño 60, se puede comprobar que
el tamaño de partición a partir del cual lo mejor es seguir
ordenando secuencialmente
es de 6 elementos:
Tamaño partición |
TReal |
TUser |
TSys |
2 |
0.28 |
0.01 |
0.01 |
3 |
0.26 |
0.01 |
0.01 |
4 |
0.26 |
0.01 |
0.01 |
5 |
0.24 |
0.01 |
0.01 |
6 |
0.23 |
0.01 |
0.01 |
7 |
0.25 |
0.01 |
0.01 |
8 |
0.30 |
0.01 |
0.02 |