c++ - tengo - ver memoria ram linux terminal

¿La asignación de memoria en Linux no es bloqueante?

Question

Tengo curiosidad por saber si la asignación de memoria mediante un nuevo operador predeterminado es una operación de no bloqueo.

p.ej

struct Node {
    int a,b;
};

...

Node foo = new Node();

Si varios subprocesos intentaron crear un nuevo Nodo y si uno de ellos fue suspendido por el sistema operativo en medio de la asignación, ¿bloquearía otros subprocesos el progreso?

La razón por la que pregunto es porque tenía una estructura de datos concurrente que creaba nuevos nodos. Luego modifiqué el algoritmo para reciclar los nodos. El rendimiento de rendimiento de los dos algoritmos fue prácticamente idéntico en una máquina de 24 núcleos. Sin embargo, luego creé un programa de interferencia que se ejecutaba en todos los núcleos del sistema para crear la mayor prioridad posible para el sistema operativo. El rendimiento del rendimiento del algoritmo que creó nuevos nodos disminuyó en un factor de 5 en relación con el algoritmo que recicló los nodos.

Tengo curiosidad por saber por qué sucedería esto.

Gracias.

* Edición: apuntar al código para el asignador de memoria c ++ para Linux también sería útil. Intenté mirar antes de publicar esta pregunta, pero tuve problemas para encontrarla.

Answer 1

En los sistemas multiproceso, malloc() y free() (y new / delete ) normalmente usan primitivos de sincronización para hacerlos seguros desde cualquier subproceso.

Esta sincronización también afecta el rendimiento de algunas aplicaciones, en particular las aplicaciones que hacen mucha asignación y desasignación en entornos altamente paralelos. Los asignadores de memoria multiproceso más eficientes son un campo de investigación activo; vea jemalloc y tcmalloc para dos conocidos.

Answer 2

Esta pregunta tiene varias respuestas correctas : en C / C ++ de multiproceso, malloc / new bloquea el montón cuando asigna memoria.

El consenso allí es que hay bloqueo. Por lo tanto, una asignación grande o una que requiera algún intercambio podría bloquear una asignación más pequeña en otro subproceso, incluso si la asignación más pequeña pudiera finalizar si no fuera por la asignación más grande en curso.

El nuevo gcc es seguro para subprocesos, si compilas con soporte para pthreads, pero eso no es realmente lo que estás preguntando.

Sé que en Windows puede crear su propio montón, que podría usarse para configurar la memoria al comienzo de su programa. No tengo conocimiento de ninguna llamada de Linux / Unix para hacer cosas similares.

Answer 3

Esto es realmente lo mismo que esta pregunta .

Básicamente, malloc no está definido como seguro para subprocesos, pero los implementadores son libres de agregar implementaciones para que sean seguros para subprocesos. Por su descripción, parece que su versión en particular es.

Para estar seguro, en palabras de Obi-Wan, "Usa la Fuente, Lucas". La fuente de malloc estará alrededor y generalmente es bastante sencillo de leer.

@Mark, puede obtener la fuente libc de GNU estándar de

$ git clone git://sourceware.org/git/glibc.git
$ cd glibc
$ git checkout --track -b glibc-2_11-branch origin/release/2.11/master

Véase también here . Recuerde que malloc encuentra en la sección 3 del manual; es una función de biblioteca, por lo que no estará en las fuentes de su núcleo. Sin embargo, es posible que deba leer en brk , sbrk , getrlimit y setrlimit y similares para descubrir qué hace el kernel.

Un enlace más: el proyecto GCC .

De acuerdo, uno más (puedo detenerme en cualquier momento): aquí hay una página desde la que puede descargar las fuentes. Descomprima el archivo y debería encontrarlo en ./malloc/malloc.c .

Answer 4

Me parece que si su aplicación de interferencia estaba usando new / delete (malloc / free), entonces la aplicación de interferencia interferiría más con la prueba de no reciclaje. Pero no sé cómo se implementa su prueba de interferencia.

Dependiendo de cómo recicle (es decir, si usa pthread mutexes god forbid), su código de reciclaje podría ser lento (las operaciones atómicas de GCC serían 40 veces más rápidas al implementar el reciclaje).

Malloc, en algunas variaciones durante mucho tiempo en al menos algunas plataformas, ha sido consciente de los hilos. Use los conmutadores del compilador en gcc para asegurarse de que lo obtenga. Los algoritmos más nuevos mantienen grupos de pequeños fragmentos de memoria para cada subproceso, por lo que hay poco o ningún bloqueo si el subproceso tiene el elemento pequeño disponible. He simplificado en exceso esto y depende de qué malloc esté usando su sistema. Además, si va y asigna millones de artículos para hacer una prueba ... bueno, entonces no verá ese efecto, porque los grupos de elementos pequeños tienen un tamaño limitado. O tal vez lo harás. No lo sé. Si liberó el artículo justo después de la asignación, es más probable que lo vea. Los artículos pequeños liberados regresan a las listas de artículos pequeños en lugar del montón compartido. Aunque "lo que sucede cuando el subproceso B libera un elemento asignado por el subproceso A" es un problema que puede tratarse o no en su versión de malloc y no puede tratarse de manera no bloqueante. Por supuesto, si no se liberó inmediatamente durante una prueba grande, entonces el hilo tendría que rellenar su pequeña lista de elementos muchas veces. Eso puede bloquearse si lo intenta más de un hilo. Finalmente, en algún punto, el montón de su proceso le pedirá al sistema la memoria del montón, que obviamente puede bloquear.

Entonces, ¿estás usando pequeños elementos de memoria? Para tu malloc no sé qué tan pequeño sería, pero si eres <1k, eso es seguro. ¿Está asignando y liberando uno tras otro, o asignando miles de nodos y luego liberando miles de nodos? ¿Estaba tu aplicación de interferencia asignada? Todas estas cosas afectarán los resultados.

Cómo reciclar con operaciones atómicas (CAS = comparar e intercambiar):

Primero agregue un pNextFreeNode a su objeto de nodo. Usé void *, puedes usar tu tipo. Este código es para punteros de 32 bits, pero también funciona para 64 bits. Luego haz una pila de reciclaje global.

void *_pRecycleHead; // global head of recycle list. 

Añadir a la pila de reciclaje:

void *Old;
while (1) { // concurrency loop
  Old = _pRecycleHead;  // copy the state of the world. We operate on the copy
  pFreedNode->pNextFreeNode = Old; // chain the new node to the current head of recycled items
  if (CAS(&_pRecycleHead, Old, pFreedNode))  // switch head of recycled items to new node
    break; // success
}

remover de la pila:

void *Old;
while (Old = _pRecycleHead) { // concurrency loop, only look for recycled items if the head aint null
  if (CAS(&_pRecycleHead, Old, Old->pNextFreeNode))  // switch head to head->next.
    break; // success
}
pNodeYoucanUseNow = Old;

El uso de CAS significa que la operación tendrá éxito solo si el elemento que está cambiando es el valor Antiguo que pasa. Si hay una carrera y otro hilo llegó primero, entonces el valor antiguo será diferente. En la vida real esta carrera pasa muy raramente. CAS es solo un poco más lento que el hecho de establecer un valor, por lo que, en comparación con los mutexes ... oscila.

La eliminación de la pila, arriba, tiene una condición de carrera si agrega y elimina el mismo elemento rápidamente. Resolvemos eso agregando una versión # a los datos de CAS''able. Si hace la versión # al mismo tiempo que el puntero a la cabeza de la pila de reciclaje, usted gana. Utilice una unión. No cuesta nada extra a CAS 64 bits.

union TRecycle {
  struct {
    int iVersion;
    void *pRecycleHead;
  } ;  // we can set these.  Note, i didn''t name this struct.  You may have to if you want ANSI
  unsigned long long n64;  // we cas this
}

Tenga en cuenta que tendrá que ir a la estructura de 128 bits para el sistema operativo de 64 bits. Así que la pila de reciclaje global se ve así ahora:

TRecycle _RecycleHead;

Añadir a la pila de reciclaje:

while (1) { // concurrency loop
  TRecycle New,Old;
  Old.n64 = _RecycleHead.n64;  // copy state
  New.n64 = Old.n64;  // new state starts as a copy
  pFreedNode->pNextFreeNode = Old.pRecycleHead;  // link item to be recycled into recycle pile
  New.pRecycleHead = pFreedNode;  // make the new state
  New.iVersion++;  // adding item to list increments the version.
  if (CAS(&_RecycleHead.n64, Old.n64, New.n64))  // now if version changed...we fail
    break; // success
}

remover de la pila:

while (1) { // concurrency loop
  TRecycle New,Old;
  Old.n64 = _RecycleHead.n64;  // copy state
  New.n64 = Old.n64;  // new state starts as a copy
  New.pRecycleHead = New.pRecycledHead.pNextFreeNode;  // new will skip over first item in recycle list so we can have that item.
  New.iVersion++;  // taking an item off the list increments the version.
  if (CAS(&_RecycleHead.n64, Old.n64, New.n64))  // we fail if version is different.
    break; // success
}
pNodeYouCanUseNow = Old.pRecycledHead;

Apuesto a que si reciclas de esta manera verás un aumento de rendimiento.

Answer 5

Respuesta corta: No.

Un hilo puede estar en medio de un new node() , y otro hilo también puede hacer un new node() . El primer hilo se puede suspender, y el segundo puede terminar primero. Está bien. (Suponiendo que nada en su constructor utiliza un mutex)

Respuesta más larga: el multihilo es una jungla. El código inseguro de subprocesos puede funcionar bien durante una década y luego fallar todos los días durante una semana. Las condiciones de la carrera pueden no provocar ningún problema en su máquina, pero explotar en la máquina de un cliente. Las aplicaciones de subprocesos múltiples introducen un nivel de incertidumbre, que requiere un esfuerzo adicional para escribir y comprender.

Entonces, ¿por qué estos dos programas se ejecutan casi idénticos un día y son enormemente diferentes con la disputa de la CPU? No lo sé. new no impide que otros subprocesos hagan new , así que no es eso. Sospecho que con la sobrecarga adicional de nuevo / eliminar, el sistema operativo tiene más oportunidades de anticiparse a su programa (y quizás incluso más posibilidades de hacerlo). Por lo tanto, cuando no hay interferencia, los dos programas obtienen la cpu todo lo que desean y funcionan bien, pero cuando la cpu es un recurso escaso, el programa nuevo / eliminar se golpea con más frecuencia que el reciclado. ¿Ver? Vale la pena reciclar ;-)