Mir scheint, wenn Ihre Interferenz-App new/delete (malloc/free) verwenden würde, würden die Interferenz-Apps den Non-Recycle-Test stärker stören. Aber ich weiß nicht, wie Ihr Interferenztest implementiert ist.
Abhängig davon, wie Sie recyceln (dh ob Sie pthread Mutexe verwenden, Gott bewahre), könnte Ihr Recycling-Code langsam sein (gcc atomic ops wäre 40x schneller bei der Implementierung von Recycling).
Malloc, in einigen Variationen seit langem auf zumindest einigen Plattformen, ist sich der Threads bewusst. Verwenden Sie die Compiler-Schalter auf gcc, um sicherzustellen, dass Sie es bekommen. Neuere Algorithmen verwalten Pools kleiner Speicherblöcke für jeden Thread, sodass es keine oder nur eine geringe Blockierung gibt, wenn Ihr Thread den kleinen Artikel zur Verfügung hat. Ich habe dies zu stark vereinfacht und es hängt davon ab, welches Malloc Ihr System verwendet. Plus, wenn Sie gehen und Millionen von Gegenständen zuweisen, um einen Test durchzuführen ... nun, dann werden Sie diesen Effekt nicht sehen, weil die Größe der kleinen Gegenstandspools begrenzt ist. Oder vielleicht doch. Ich weiß nicht. Wenn Sie das Element direkt nach der Zuweisung freigeben, ist es wahrscheinlicher, dass Sie es sehen. Freigegebene kleine Gegenstände gehen zurück in die Liste der kleinen Gegenstände und nicht in den gemeinsam genutzten Haufen. Obwohl "was passiert, wenn Thread B ein von Thread A zugewiesenes Element freigibt" ein Problem ist, das möglicherweise in Ihrer Version von malloc behandelt wird oder nicht und möglicherweise nicht auf nicht blockierende Weise behandelt wird. Wenn Sie während eines großen Tests nicht sofort befreit haben, müsste der Thread seine kleine Artikelliste viele Male neu füllen. Das kann blockieren, wenn mehr als ein Thread es versucht. Schließlich wird der Heap Ihres Prozesses das System irgendwann nach Heap-Speicher fragen, der offensichtlich blockieren kann.
Verwenden Sie also kleine Speicherelemente? Für Ihren Malloc weiß ich nicht, was klein wäre, aber wenn Sie <1k sind, ist das sicher klein. Weisen Sie einen nach dem anderen zu und geben ihn frei, oder weisen Sie Tausende von Knoten zu und geben dann Tausende von Knoten frei? Hat Ihre Interferenz-App zugewiesen? All diese Dinge werden die Ergebnisse beeinflussen.
So recyceln Sie mit Atomic Ops (CAS =vergleichen und tauschen):
Fügen Sie Ihrem Node-Objekt zunächst einen pNextFreeNode hinzu. Ich habe void* verwendet, Sie können Ihren Typ verwenden. Dieser Code ist für 32-Bit-Zeiger, funktioniert aber auch für 64-Bit. Dann erstelle einen globalen Recycling-Haufen.
void *_pRecycleHead; // global head of recycle list.
Zum Papierkorb hinzufügen:
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
}
vom Stapel entfernen:
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;
Die Verwendung von CAS bedeutet, dass die Operation nur dann erfolgreich ist, wenn das Element, das Sie ändern, der alte Wert ist, den Sie übergeben. Wenn es ein Rennen gibt und ein anderer Thread zuerst dort angekommen ist, ist der alte Wert anders. Im wirklichen Leben kommt dieses Rennen sehr, sehr selten vor. CAS ist nur geringfügig langsamer als das eigentliche Setzen eines Wertes, also im Vergleich zu Mutexes .... es rockt.
Das Entfernen vom Stapel oben hat eine Race-Condition, wenn Sie dasselbe Element schnell hinzufügen und entfernen. Wir lösen das, indem wir den CAS-fähigen Daten eine Versionsnummer hinzufügen. Wenn Sie die Version # gleichzeitig mit dem Zeiger auf den Kopf des Papierkorbs machen, gewinnen Sie. Verwenden Sie eine Gewerkschaft. Kostet nichts extra zu CAS 64 Bit.
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
}
Beachten Sie, dass Sie für 64-Bit-Betriebssysteme zur 128-Bit-Struktur wechseln müssen. also sieht der globale Papierkorb jetzt so aus:
TRecycle _RecycleHead;
Zum Papierkorb hinzufügen:
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
}
vom Stapel entfernen:
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;
Ich wette, wenn Sie auf diese Weise recyceln, werden Sie eine Leistungssteigerung feststellen.
Auf diese Frage gibt es eine Reihe guter Antworten:In Multithread-C/C++ sperrt malloc/new den Heap, wenn Speicher zugewiesen wird.
Der Konsens besteht darin, dass es Sperren gibt. Eine große Zuweisung oder eine Zuweisung, die ein gewisses Austauschen erfordert, könnte also eine kleinere Zuweisung in einem anderen Thread blockieren, selbst wenn die kleinere beendet werden könnte, wenn nicht die größere Zuweisung im Gange wäre.
gcc's new ist Thread-sicher, wenn Sie mit pthreads-Unterstützung kompilieren, aber das ist nicht wirklich das, was Sie fragen.
Ich weiß, dass Sie in Windows Ihren eigenen Heap erstellen können, mit dem Sie am Anfang Ihres Programms Speicher einrichten können. Mir sind keine Linux/Unix-Aufrufe bekannt, um ähnliche Dinge zu tun.
Das ist wirklich so ziemlich dasselbe wie diese Frage.
Grundsätzlich malloc ist nicht als Thread-sicher definiert, aber Implementierer können Implementierungen hinzufügen, um sie Thread-sicher zu machen. Aus Ihrer Beschreibung geht hervor, dass Ihre spezielle Version dies ist.
Um sicher zu sein, mit den Worten von Obi-Wan:"Benutze die Quelle, Luke." Die malloc Source wird es geben und es ist im Allgemeinen ziemlich einfach zu lesen.
@Mark, du kannst den Standard-GNU-Libc-Quellcode von
erhalten$ git clone git://sourceware.org/git/glibc.git
$ cd glibc
$ git checkout --track -b glibc-2_11-branch origin/release/2.11/master
Siehe auch hier. Denken Sie daran, malloc befindet sich in Abschnitt 3 des Handbuchs -- es ist eine Bibliotheksfunktion, also wird es nicht in Ihren Kernelquellen sein. Möglicherweise müssen Sie jedoch in brk nachlesen ,sbrk , getrlimit und setrlimit und dergleichen, um herauszufinden, was der Kernel macht.
Noch ein Link:das GCC-Projekt.
Okay, noch eins (ich kann jederzeit aufhören):Hier ist eine Seite, von der Sie die Quellen herunterladen können. Entpacken Sie die Datei und Sie sollten sie unter ./malloc/malloc.c finden .
In Multithread-Systemen malloc() und free() (und new / delete ) verwenden normalerweise Synchronisierungsprimitive, um sicherzustellen, dass sie sicher von mehreren Threads aus aufgerufen werden können.
Diese Synchronisierung wirkt sich auch auf die Leistung einiger Anwendungen aus, insbesondere von Anwendungen, die in hochgradig parallelen Umgebungen viele Zuweisungen und Freigaben vornehmen. Effizientere Multithread-Speicherzuordner sind ein aktives Forschungsgebiet - siehe jemalloc und tcmalloc für zwei bekannte.