En C/C++ puedo asignar memoria en un hilo y eliminarlo en otro hilo. Sin embargo, cada vez que se solicita memoria del montón, el asignador de montones debe recorrer el montón para encontrar un área libre de tamaño adecuado. ¿Cómo pueden dos subprocesos acceder al mismo montón de manera eficiente sin corromper el montón? (¿Esto se hace bloqueando el montón?)Gestión de montón multiproceso
En general, no necesita preocuparse por la seguridad del hilo de su asignador de memoria. Todos los asignadores de memoria estándar, es decir, aquellos enviados con MacOS, Windows, Linux, etc., son seguros para subprocesos. Los bloqueos son una forma estándar de proporcionar seguridad de subprocesos, aunque es posible escribir un asignador de memoria que solo utilice operaciones atómicas en lugar de bloqueos.
Ahora es una pregunta completamente diferente si los asignadores de memoria escala; es decir, ¿su rendimiento es independiente del número de subprocesos que realizan operaciones de memoria? En la mayoría de los casos, la respuesta es no; o ralentizan o pueden consumir mucho más memoria. El primer asignador escalable en ambas dimensiones (velocidad y espacio) es Hoard (que escribí); el asignador de Mac OS X está inspirado en él, y lo cita en la documentación, pero Hoard es más rápido. Hay otros, incluido el tcmalloc de Google.
¿Puede proporcionarnos alguna información sobre la estrategia general impuesta por Hoard? – doron
La memoria se gestiona en fragmentos llamados superbloques, que contienen objetos del mismo tamaño. Cada hilo obtiene un cierto número de estos (thread-local), lo que significa que no hay bloqueos ni contención. Los hilos se multiplexan en montones por CPU, que tienen superbloques. La asignación desde una supermanzana solo se realiza por un hilo a la vez, lo que limita el intercambio falso. Hoard limita el consumo de memoria al mover superbloques casi vacíos a un montón compartido a medida que los montones de CPU se vacían, lo que limita la contención y garantiza un consumo de memoria óptimo asintóticamente. Ver http://www.cs.umass.edu/~emery/hoard/asplos2000.pdf. – EmeryBerger
Sí, normalmente el acceso al montón debe bloquearse. Cada vez que tenga un recurso compartido, ese recurso debe estar protegido; la memoria es un recurso.
¿Incluso cuando cada hilo maneja su propia memoria? Eso suena terriblemente ineficiente. – doron
Recuerde, lo correcto es lo primero, la eficiencia después. –
@deus: No, pero esa no es la situación que describiste. Dijiste que los hilos están compartiendo memoria. (Eliminando en otro hilo) – GManNickG
Esto dependerá en gran medida de su plataforma/sistema operativo, pero creo que esto generalmente está bien en los principales sistemas. C/C++ no define subprocesos, por lo que de manera predeterminada creo que la respuesta es "el montón no está protegido", que debe tener algún tipo de protección multiproceso para su acceso al montón.
Sin embargo, al menos con Linux y gcc, creo que permite -pthread le dará esta protección de forma automática ...
Además, aquí hay otra pregunta relacionada:
Este es una pregunta de Sistemas Operativos, por lo que la respuesta va a depender del sistema operativo.
En Windows, cada proceso tiene su propio montón. Eso significa que múltiples hilos en el mismo proceso están compartiendo un montón (de forma predeterminada). Por lo tanto, el sistema operativo tiene que sincronizar sus llamadas de asignación y desasignación para evitar la corrupción del montón. Si no le gusta la idea de la posible controversia que pueda surgir, puede evitarla utilizando el Heap* routines. Incluso puede sobrecargar malloc (en C) y nuevo (en C++) para llamarlos.
Sí, una implementación de montón "normal" que admita código multiproceso incluirá necesariamente algún tipo de bloqueo para garantizar el funcionamiento correcto. Bajo condiciones bastante extremas (un lote de la actividad del montón) esto puede convertirse en un cuello de botella; se encuentran disponibles montones más especializados (que en general proporcionan algún tipo de pila local de subprocesos) que pueden ayudar en esta situación. He usado Intel TBB's "scalable allocator" a good effect. tcmalloc y jemalloc son otros ejemplos de mallocs implementados teniendo en cuenta la escala de subprocesos múltiples.
Algunas comparaciones de temporización comparaciones entre un solo hilo y mallocs multithread-aware here.
Recién salido de interés, ¿cuáles son las estrategias malloc para gcc y MSVC? – doron
Buena pregunta. No sé mucho sobre la CRT de MSVC, pero gcc generalmente se asocia con glibc que usa ptmalloc: http://en.wikipedia.org/wiki/Malloc#dlmalloc_.28the_glibc_allocator.29. El enlace de tiempos arriba muestra esta escala bastante bien, lo que explicaría por qué mis propios experimentos con el asignador de TBB a veces lo hacen mejor, a veces peor. – timday
@doron Windows Vista y versiones posteriores usan un Heap de baja fragmentación, lo que supuestamente hace que el malloc estándar funcione bien en programas multiproceso. –
Encontré this enlace.
Básicamente, el montón se puede dividir en arenas. Al solicitar memoria, cada arena se verifica por turno para ver si está bloqueada. Esto significa que diferentes subprocesos pueden acceder a diferentes partes del montón al mismo tiempo de forma segura. Los Frees son un poco más complicados porque cada free debe ser liberado de la arena desde la que fue asignado. Imagino que una buena implementación hará que los diferentes subprocesos pasen a diferentes arenas para intentar minimizar la contención.
Reetiquetado, ya que esto realmente no tiene nada que ver con ningún lenguaje de programación en particular. –
No del todo cierto. El SO está involucrado solo cuando crece el montón (lo que implica paginación en nuevas páginas de memoria). Depende de la implementación C/C++ de malloc/new, para administrar realmente el montón. – doron