Interrumpible en el lugar algoritmo de ordenación

Question

Tengo que escribir un programa de clasificación en C y que sería bueno si el archivo podría ser clasificado en el lugar para ahorrar espacio en disco. El dato es valioso, por lo que necesito para asegurar que si el proceso se interrumpe (Ctrl-C) el archivo no está dañado. Puedo garantizar que el cable de alimentación de la máquina no se tiró.

Detalles adicionales: archivo es de ~ 40 GB, los registros se 128 bits, la máquina es de 64 bits, OS es POSIX

¿Alguna pista sobre el cumplimiento de esta, o notas en general?

Gracias!

Para aclarar: espero que el usuario querrá ctrl-c el proceso. En este caso, quiero salir con gracia y asegurarse de que los datos están a salvo. Así que esta pregunta es acerca de cómo tratar las alarmas y la elección de un algoritmo de ordenación que puede terminar rápidamente si así lo solicita.

En seguimiento (2 años más tarde): Sólo para la posteridad, he instalado el controlador de SIGINT y funcionó muy bien. Esto no me protege contra fallos de energía, sino que es un riesgo que pueda manejar. Código en https://code.google.com/p/ pawnsbfs / fuente / browse / trunk / hsort.c y https://code.google.com/p/pawnsbfs/source/browse/trunk/qsort.c

Answer 1

Instalar un controlador para SIGINT que simplemente establece un "proceso debe salir pronto" bandera.

En su tipo, compruebe el indicador después de cada intercambio de dos registros (o después de cada N permutas). Si el indicador está establecido, rescatar.

Answer 2

derecho de Jerry, si es sólo Ctrl-C te preocupa, puede ignorar SIGINT por períodos a la vez. Si quieres estar a prueba de muerte proceso en general, se necesita algún tipo de journalling mínima. Con el fin de intercambiar dos elementos:

1) Añadir un registro a una estructura de control al final del archivo o en un archivo separado, indicando la que dos elementos del archivo que se va a intercambio, A y B.

2) Copia A al espacio cero, constancia de que lo haya hecho, al ras.

3) Copia de B en A, entonces grabar en el espacio de desecho que se ha hecho, al ras

4) Copiar en el espacio cero sobre B.

5) Retire el registro.

Este es O (1) espacio adicional para todos los propósitos prácticos, por lo que todavía cuenta como en el lugar bajo la mayoría de las definiciones. En la grabación un índice teoría es O (log n) si n puede ser arbitrariamente grande:. En realidad es una muy pequeña log n, y hardware razonable / tiempo de funcionamiento límites por encima de a 64

En todos los casos, cuando digo "flush", me refiero a confirmar los cambios "suficientemente lejos". A veces, su funcionamiento básico ras sólo se vuelca buffers dentro del proceso, pero no es así en realidad sincronización del medio físico, ya que no hace tampones ras todo el camino a través de los niveles de OS / controlador de dispositivo / hardware. Eso es suficiente cuando lo único que te preocupa es la muerte proceso, pero si usted está preocupado acerca de los medios de comunicación se desmonta abruptos, entonces tendríamos que ras más allá del conductor. Si estaban preocupados por falta de energía eléctrica, que lo tienes que sincronizar el hardware, pero no lo eres. Con un UPS o si cree que los cortes de energía son tan raras que no le importe la pérdida de datos, que está muy bien.

En el arranque, comprobar el espacio reservado para los registros de intercambio "en progreso". Si encuentra uno, el trabajo fuera de lo lejos que tienes y completar el canje de allí para obtener la parte posterior de datos en un estado de sonido. A continuación, iniciar su clase de nuevo.

Es evidente que hay un problema de rendimiento aquí, ya que está haciendo el doble de la escritura de los registros como antes, y rubores / sincroniza pueden ser sorprendentemente caro. En la práctica de su tipo en el lugar podría tener algunas operaciones compuesto móvil de cosas, la participación de muchos intercambios, pero que se puede optimizar para evitar golpear a todos los elementos del espacio de desecho. Sólo hay que asegurarse de que antes de sobrescribir los datos, usted tiene una copia del mismo en un lugar seguro y un registro de dónde esa copia debe ir con el fin de conseguir su regreso archivo a un estado en el que contiene exactamente una copia de cada elemento.

Jerry también justo que la verdadera clasificación en el lugar es demasiado difícil y lenta para la mayoría de los propósitos prácticos. Si puede prescindir de alguna fracción lineal del tamaño del archivo original como espacio de uso temporal, tendrá un tiempo mucho mejor de ella con una especie de mezcla.

En función de su aclaración, que no necesitaría ningún operaciones de vaciado, incluso con un tipo en el lugar. Usted necesita rasca espacio en la memoria que funciona de la misma manera, y que su SIGINT acceso manejador de lata con el fin de obtener el seguro de datos antes de salir, en lugar de restaurar en el arranque después una salida anormal, y que necesita para el acceso que la memoria de una manera segura de señal (que técnicamente significa utilizar un sig_atomic_t a la bandera de los cuales se han hecho cambios). Aun así, es probable que mejor con un mergesort que un cierto tipo en el lugar.

Answer 3

La parte para la protección contra ctrl-c es bastante fácil:. signal(SIGINT, SIG_IGN);

En cuanto a la clasificación en sí ocurre, una combinación de tipo general, funciona bien para la clasificación externa. La idea básica es leer tantos registros en la memoria como se puede, más o menos, entonces escribirlas de vuelta al disco. Con mucho, la forma más fácil de manejar esto es para escribir cada ejecución en un archivo separado en el disco. A continuación, se fusionan los de nuevo juntos - leer el primer registro de cada ejecución en la memoria, y escribir el más pequeño de los que fuera en el archivo original; leer otro registro de la ejecución que suministra ese registro, y repita hasta que esté hecho. La última fase es la única vez que se está modificando el archivo original, por lo que es la única vez que realmente necesita para asegurar contra las interrupciones y tal.

Otra posibilidad es utilizar una especie de selección. El punto negativo es que la clasificación en sí es bastante lento. Lo bueno es que es bastante fácil de escribir para sobrevivir casi cualquier cosa, sin necesidad de utilizar mucho espacio extra. La idea general es bastante simple: encontrar el registro más pequeño del archivo y de intercambio que en el primer lugar. A continuación, busque el registro más pequeño de lo que queda, y de intercambio que en el segundo lugar, y así sucesivamente hasta que esté hecho. El punto de esto es que buena diario es trivial: antes de hacer un intercambio, graba los valores de los dos registros que vas a intercambio. Dado que las ordenaciones del primer registro a la última, la única otra cosa que necesita pista es el número de registros ya están ordenados en un momento dado.

Answer 4

Uso pila de clasificación, y evitar interrupciones (por ejemplo, señales de bloque) durante cada operación de intercambio.

Answer 5

Copia de seguridad de todo lo que va a cambiar. El puso una bandera que marca una especie exitosa. Si todo está en orden y luego mantener el resultado, de lo contrario restaurar la copia de seguridad.

Answer 6

Suponiendo un sistema operativo de 64 bits (se dice que es una máquina de 64 bits, pero todavía podría estar en ejecución del sistema operativo de 32 bits), se puede utilizar mmap para mapear el archivo en una matriz a continuación, utilizar qsort en la matriz.

Añadir un controlador para SIGINT a msync llamada y munmap para permitir la aplicación para responder a Ctrl-C sin pérdida de datos.