Cómo hacer que el núcleo compacte memoria fragmentada

Estoy funcionando Fedora 26.

Esto es para una tarea muy extraña dada por mi profesor de algoritmos. La tarea dice:

Fragmentación de memoria en C:
diseñe, implemente y ejecute un programa en C que haga lo siguiente: asigna memoria para una secuencia de 3mmatrices de 800,000 elementos cada una; luego desasigna explícitamente todas las matrices pares y asigna una secuencia de mmatrices de 900,000 elementos de tamaño cada una. Mida la cantidad de tiempo que su programa requiere para la asignación de la primera secuencia y para la segunda secuencia. Elija magotar casi toda la memoria principal disponible para su programa ".

El objetivo general de esto es fragmentar la memoria y luego solicitar un poco más de lo que está disponible como un fragmento contiguo, lo que obliga al sistema operativo a compactar o desfragmentar la memoria.

En clase, pregunté cómo deberíamos hacer esto, ya que la memoria se visualiza y no es realmente contigua, a lo que él respondió: "Bueno, tendrás que apagar [la memoria virtual]". Otros estudiantes preguntaron en clase cómo deberíamos saber cuándo llegamos a esta "recolección de basura", y él dijo que: "El tiempo para la segunda asignación debe ser mayor que el primero debido al tiempo que lleva la recolección de basura".

Después de buscar un poco, lo más cercano que pude encontrar a deshabilitar la memoria virtual fue deshabilitar la memoria de intercambio swapoff -a. Inhabilité mi entorno de escritorio y compilé y ejecuté mi programa desde el terminal nativo (para evitar posibles interferencias de otros procesos, especialmente uno pesado como el entorno de escritorio). Hice esto y ejecuté mi programa aumentando mhasta llegar a un punto en el que el tiempo para la segunda asignación fue mayor que el primero.

Ejecuté el programa cada vez más my finalmente encontré un punto donde el tiempo para la segunda asignación era más que el tiempo para la primera asignación. En el camino, sin embargo, llegué a un punto en el que el proceso finalizó antes de la segunda asignación. Lo comprobé dmesgy vi que fue asesinado por oom-killer. Encontré y leí varios artículos sobre oom-killer y descubrí que podía deshabilitar la asignación excesiva de memoria por parte del núcleo.

Hice esto y ejecuté mi programa nuevamente, solo que esta vez no pude encontrar un mtal que el momento del segundo fuera más alto que el primero. Eventualmente, con m cada vez más grande (aunque mucho más pequeño que cuando se habilitó la sobreasignación), malloc fallaría y mi programa terminaría.

Tengo tres preguntas, la primera de las cuales no es realmente tan importante:

1. ¿Es la recolección de basura el término correcto para esto? Mi profesor es muy firme al decir que se trata de recolección de basura, pero yo asumía que la recolección de basura era algo que se hacía mediante lenguajes de programación y que esto se consideraría más desfragmentado.

2. ¿Es posible la compactación como él quiere en un sistema Linux?

3. ¿Por qué pude llegar a un punto en el que el tiempo para la segunda asignación fue mayor que el primero cuando desactivé el intercambio pero todavía tenía habilitada la sobreasignación de memoria? ¿Realmente tuvo lugar la compactación? Si es así, ¿por qué no pude alcanzar un punto en el que ocurrió la compactación después de deshabilitar la sobreasignación de memoria?

Felicitaciones por su investigación hasta ahora, este es de hecho un conjunto interesante de preguntas.

Hay un aspecto importante a considerar aquí en general: la asignación de memoria es en parte responsabilidad del sistema operativo y en parte la responsabilidad de cada proceso en ejecución (ignorar los sistemas antiguos sin protección de memoria y espacios de direcciones virtuales). El sistema operativo se encarga de proporcionar a cada proceso su propio espacio de direcciones y de asignar memoria física a los procesos cuando sea necesario. Cada proceso se encarga de dividir su espacio de direcciones (hasta cierto punto) y garantizar que se use adecuadamente. Tenga en cuenta que la responsabilidad de un proceso será en gran medida invisible para los programadores, ya que el entorno de ejecución se encarga de la mayoría de las cosas.

Ahora, para responder a sus preguntas ...

1. En mi opinión, la recolección de basura está a un paso de lo que estás haciendo aquí. Me imagino que estás escribiendo en C, usando malloc()y free(). La recolección de basura , donde es compatible con el lenguaje de programación y el entorno de tiempo de ejecución, se encarga de la última parte: identifica los bloques de memoria que se asignaron previamente pero que ya no están en uso (y, lo que es más importante, nunca se pueden volver a usar), y los devuelve al asignador La pregunta vinculada en el comentario de JdeBP proporciona algunos antecedentes, pero me parece sobre todo interesante porque demuestra que diferentes personas tienen opiniones muy diferentes sobre la recolección de basura, e incluso lo que constituye la recolección de basura.

   En el contexto que nos interesa, usaría "compactación de memoria" para hablar sobre el proceso en discusión.

2. Desde una perspectiva de programación del espacio de usuario, lo que su profesor está pidiendo no es posible, en C, bajo Linux, por una simple razón: lo que nos importa aquí no es la fragmentación de la memoria física, es la fragmentación del espacio de direcciones. Cuando asigna sus muchos bloques de 800,000 bytes, terminará con la misma cantidad de punteros a cada bloque. En Linux, en este punto, el sistema operativo en sí no ha hecho mucho, y no necesariamente tiene memoria física que respalde cada asignación (como un aparte, con asignaciones más pequeñas, el sistema operativo no estaría involucrado en absoluto, solo su Asignador de la biblioteca C; pero las asignaciones aquí son lo suficientemente grandes como para que la biblioteca C utilicemmap, que es manejado por el núcleo). Cuando libera los bloques impares, recupera esos bloques de espacio de direcciones, pero no puede cambiar los punteros que tiene a los otros bloques. Si imprime los punteros a medida que avanza, verá que la diferencia entre ellos no es mucho más que la solicitud de asignación (802,816 bytes en mi sistema); no hay espacio entre dos punteros para un bloque de 900,000 bytes. Debido a que su programa tiene punteros reales para cada bloque, en lugar de un valor más abstracto (en otros contextos, un identificador), el entorno de tiempo de ejecución no puede hacer nada al respecto y, por lo tanto, no puede compactar su memoria para unir bloques libres.

   Si usa un lenguaje de programación donde los punteros no son un concepto visible para el programador, entonces la compactación de memoria es posible, bajo Linux. Otra posibilidad sería utilizar una API de asignación de memoria donde los valores devueltos no sean punteros; consulte, por ejemplo, las funciones de asignación de almacenamiento dinámico basadas en identificadores en Windows (donde los punteros solo son válidos cuando un identificador está bloqueado).

3. El ejercicio de su profesor mide efectivamente el rendimiento de mmap, que incluye su algoritmo de caminar en bloque libre. Primero asigna 3 × m bloques, luego libera la mitad de ellos y luego comienza a asignar m bloques nuevamente; Al liberar todos esos bloques, se descarga una gran cantidad de bloques libres en el asignador del núcleo, que debe realizar un seguimiento (y el tiempo que tardan las freellamadas muestra que no se está optimizando en este momento). Si realiza un seguimiento de los tiempos de asignación de cada bloque individual, verá que la primera asignación de 900k toma mucho, muchomás largo que los otros (tres órdenes de magnitud en mi sistema), el segundo es mucho más rápido pero aún toma mucho más tiempo (dos órdenes de magnitud), y la tercera asignación vuelve a los niveles de rendimiento típicos. Entonces, algo está sucediendo, pero los punteros devueltos muestran que no fue compactación de memoria, al menos no compactación de bloque asignada (que, como se explicó anteriormente, es imposible), presumiblemente el tiempo corresponde al procesamiento de tiempo de las estructuras de datos que el núcleo utiliza para Realice un seguimiento del espacio de direcciones disponible en el proceso (estoy comprobando esto y lo actualizaré más adelante). Estas asignaciones largas pueden crecer para eclipsar las secuencias de asignación generales que está midiendo, que es cuando las asignaciones de 900k terminan tomando más tiempo en general que las asignaciones de 800k.

   La razón por la que el exceso de compromiso cambia el comportamiento que ve es que cambia el ejercicio de la simple manipulación del espacio de direcciones a la asignación de memoria y, por lo tanto, reduce el tamaño de su área de juegos. Cuando puede comprometerse en exceso, el núcleo solo está limitado por el espacio de direcciones de su proceso, por lo que puede asignar muchos más bloques y ejercer mucha más presión sobre el asignador. Cuando deshabilita el exceso de compromiso, el núcleo está limitado por la memoria disponible, lo que reduce el valor que puede tener mhasta niveles en los que el asignador no está lo suficientemente estresado como para que los tiempos de asignación exploten.