PatentDe  


Dokumentenidentifikation DE69715532T2 15.05.2003
EP-Veröffentlichungsnummer 0817044
Titel Speicherzuordnung in einer Mehrfachfädenumgebung
Anmelder Sun Microsystems, Inc., Mountain View, Calif., US
Erfinder Nakhimovsky, Gregory, Wakefield, Massachusetts 01880, US
Vertreter HOFFMANN · EITLE, 81925 München
DE-Aktenzeichen 69715532
Vertragsstaaten DE, FR, GB, NL, SE
Sprache des Dokument EN
EP-Anmeldetag 27.06.1997
EP-Aktenzeichen 973046535
EP-Offenlegungsdatum 07.01.1998
EP date of grant 18.09.2002
Veröffentlichungstag im Patentblatt 15.05.2003
IPC-Hauptklasse G06F 9/46

Beschreibung[de]

Die Erfindung betrifft Speicherallozierung und im Besonderen Speicherallozierung in einer Multithread- (parallelen) Umgebung.

Beim Zuweisen von Speicher für ein Computerprogramm erfordern die meisten älteren Sprachen (z. B. FORTRAN, COBOL), dass die Größe eines Arrays oder einer Information deklariert wird, bevor das Programm kompiliert wird. Darüber hinaus konnte die Größe des Arrays oder der Information nicht überschritten werden, wenn das Programm nicht geändert und rekompiliert wurde. Heute erlauben die meisten modernen Programmiersprachen, einschließlich C und C&spplus;&spplus;, dem Benutzer, zur Laufzeit Speicherblöcke aus dem Systemspeicher abzurufen und die Blöcke wieder zum Systemspeicher zurückzugeben, wenn das Programm die Blöcke nicht mehr braucht. Beispielsweise haben Datenelemente in diesen modernen Sprachen oft eine Datenstruktur mit einem Feld, das einen Zeiger auf ein nächstes Datenelement enthält. Eine Anzahl von Datenelementen können zur Laufzeit in einer verketteten Liste oder einer Arraystruktur alloziert werden.

Die Programmiersprache C stellt Speicherverwaltungsfähigkeit mit einem Satz von Bibliotheksfunktionen bereit, die als "Speicherallozierungs-"Routinen bekannt sind. Die einfachste Speicherallozierungsfunktion wird malloc genannt, die eine angeforderte Anzahl von Bytes alloziert und einen Zeiger zurücksendet, der die Startadresse des allozierten Speichers ist. Eine weitere als free bekannte Funktion gibt den zuvor mit malloc allozierten Speicher zurück, damit er zur Benutzung durch andere Routinen wieder alloziert werden kann.

In Anwendungen, in denen die Speicherallozierung parallel erfolgt, z. B. in einem Multithread-Prozess, müssen die Funktionen malloc und free "durch Code Locking für Exklusivzugriff nur eines Threads reserviert" werden. Code Locking bedeutet, dass der Bibliothekscode des Prozesses, der den Thread enthält, von einer globalen Sperre (Lock) geschützt wird. Das verhindert eine Datenverfälschung im Fall, dass ein Thread eine globale Struktur modifiziert, wenn ein anderer Thread sie zu lesen versucht. Code Locking lässt zu jedem beliebigen Zeitpunkt nur jeweils einen Thread eine der malloc- Funktionen (z. B. malloc, free, realloc) aufrufen, wobei andere Threads warten, bis der Thread mit seiner Speicherallozierung fertig ist. In einem Multithread-Prozess, bei dem häufig Speicherallozierungsfunktionen benutzt werden, ist die Geschwindigkeit des Systems daher stark beeinträchtigt.

Zusammenfassung der Erfindung

Im Allgemeinen ist die Erfindung in einem Aspekt ein Verfahren zum Allozieren von Speicher in einer Multithread- Computerumgebung, bei dem Threads, die innerhalb eines Prozesses parallel laufen, jeweils einen assoziierten Speicherpool in einem Systemspeicher haben. Das Verfahren weist die folgenden Schritte auf: Einrichten von Speicherpools im Systemspeicher, Abbilden jedes Threads auf einen der Speicherpools und für jeden Thread das dynamische Allozieren von Benutzerspeicherblöcken aus dem assoziierten Speicherpool. Jeder Thread verwendet Speicherallozierungsroutinen (z. B. malloc) zum Manipulieren seines eigenen Speicherpools, wodurch größere Speicherverwaltungseffizienz erreicht wird.

Die Erfindung konvertiert ein existierendes Speicherverwaltungs-malloc-Paket in eine Multithread-Version um, sodass Multithread-Prozesse effizienter ablaufen. Darüber hinaus ist die Erfindung auf jede Anwendung anwendbar, die parallele Speicherverwaltung erfordert; insbesondere die Anwendungen, die eine bedeutende parallele Speicherverwaltung erfordern. Ferner ist die Benutzung der Erfindung vom Standpunkt des Applikationsprogrammierers transparent, da die Benutzerschnittstelle die gleiche wie die der standardmäßigen Bibliothekspeicherverwaltungsfunktionen von C (d. h. malloc, free, realloc) ist.

In einer bevorzugten Ausgestaltung kann das Verfahren ferner den Schritt des Verhinderns von gleichzeitigem Zugriff auf einen Speicherpool durch verschiedene Threads aufweisen. Separate Speicherpools erlauben Code Locking (z. B. mutex (mutual exclusion lock - gegenseitig ausschließende Sperre/Schlossvariable)), um gleichzeitigen Zugriff auf die Speicherpools durch die verschiedenen Threads zu verhindern, wodurch die Möglichkeit einer Datenverfälschung ausgeschlossen wird. In für die parallele Ausführung geeigneten existierenden Standard-Speicherallozierungsroutinen gibt es nur ein einziges Code Lock. Somit kann jeweils nur ein einziger Thread einen Aufruf einer Speicherallozierungsroutine durchführen. Alle anderen im Prozess laufenden Threads müssen warten, bis der Thread seinen Speicherallozierungsvorgang beendet. In der Erfindung können Speicherallozierungsvorgänge dagegen, solange jeder Thread seinen eigenen Speicher manipuliert, parallel ohne Verzögerung durchgeführt werden. Das separate Code Locking-Merkmal wird nur dann wichtig, wenn ein Thread versucht, auf den Speicherpool eines anderen Threads zuzugreifen. Derartige Speicherallozierungen eines nicht mit diesem Thread assoziierten Speicherpools sind ziemlich ungewöhnlich. Somit erbringt die Erfindung eine Verbesserung der Leistung des Multithread-Prozesses, indem die mit Aufrufen von Speicherallozierungsroutinen assoziierten Verzögerungen bedeutend reduziert werden.

Bevorzugte Ausgestaltungen können eines oder mehrere der folgenden Leistungsmerkmale aufweisen. Der Schritt der dynamischen Allozierung von Speicherblöcken beinhaltet die Bezeichnung der Bytezahl in dem zu allozierenden Block. Beispielsweise wird durch Aufrufen der malloc-Funktion eine Anzahl erforderlicher Bytes bis zu einer maximalen Größe des Speicherpools alloziert. Der Schritt des Einrichtens eines Speicherpools für jeden Thread kann ferner das Allozieren eines Speicherpuffers einer vorausgewählten Größe (z. B. 64 Kilobytes) aufweisen. Im Fall, dass die Größe des Speicherpools erschöpft ist, kann die Größe des Speicherpools durch Allozieren von zusätzlichem Speicher aus dem Systemspeicher in der vorausgewählten Größe des Pufferspeichers gleichen Inkrementen dynamisch vergrößert werden. Darüber hinaus kann das Verfahren ferner beinhalten, dass einer der Threads Speicher aus dem Speicherpool eines anderen der Threads zu seinem Speicherpool übertragen darf.

Jeder Speicherpool kann als eine Speicherblock- Datenstruktur gehalten werden, z. B. ein Array statischer Variablen, die durch einen mit einem der Speicherpools assoziierten Thread-Index gekennzeichnet sind. Die Datenstruktur hat einen Anfangsblock, der die Größe des Speicherblocks und den Speicherpoolindex, mit dem er assoziiert ist, aufweist. Die Größe des Blocks und des Speicherpoolindexes kann beispielsweise jeweils vier Bytes betragen.

Das Verfahren kann ferner den Schritt beinhalten, dass jeder Thread einen Speicherblock zum Speicherpool deallozieren oder freigeben darf. Die Applikation kann erfordern, dass der Speicherblock von dem Thread, der den Speicherblock ursprünglich allozierte, freigegeben wird. Andere Applikationen können erlauben, dass der Speicherblock von einem Thread, der den Block nicht ursprünglich allozierte, freigegeben wird.

Zum Vereinigen kleinerer fragmentierter Blöcke kann ein Zusammenlegen oder Mischen deallozierter (oder freigegebener) Speicherblöcke durchgeführt werden. Das Verfahren verhindert aber das Zusammenlegen von Speicherblöcken aus verschiedenen Pools.

Im Fall, dass die Größe eines Speicherblocks vergrößert werden muss, um mehr Datenelemente zu speichern, kann die Größe eines allozierten Speicherblocks, der von einem Speicherpool alloziert wurde, mit Hilfe einer realloc-Routine geändert werden. Das Verfahren erfordert, dass realloc den ursprünglichen Speicherpool erhält.

In einem anderen Aspekt ist die Erfindung im Allgemeinen ein ein Computerprogramm zum Allozieren von Speicher in einer Multithread-Computerumgebung speicherndes, computerlesbares Speichermedium, bei dem Threads innerhalb eines Prozesses parallel laufen, wobei jeder Thread Zugriff auf einen Systemspeicher hat. Das gespeicherte Programm beinhaltet computerlesbare Anweisungen: (1) die im Systemspeicher eine Mehrzahl von Speicherpools einrichten, (2) die jeden Thread auf einen der genannten Mehrzahl von Speicherpools abbilden und (3) die für jeden Thread dynamisch Benutzerspeicherblöcke aus dem assoziierten Speicherpool allozieren. Ein computerlesbares Speichermedium schließt jedwede einer großen Vielfalt von Speichermedien, wie RAM- oder ROM-Speicher, sowie externe computerlesbare Medien, wie z. B. eine Diskette oder CD-ROM, ein. Ein Computerprogramm kann auch über ein Netzwerk in aktiven Zwischenspeicher (z. B. RAM, Ausgabepuffer) eines Computers heruntergeladen werden. Beispielsweise kann das oben beschriebene Computerprogramm über das Internet von einer Website in den Speicher eines Computers heruntergeladen werden. Es ist also vorgesehen, dass das computerlesbare Speichermedium der Erfindung den Speicher des Computers einschließt, der das oben beschriebene Computerprogramm, das aus einem Netzwerk heruntergeladen wird, speichert.

In einem weiteren Aspekt der Erfindung hat ein System Folgendes: Speicher, von dem ein Teil das oben beschriebene Computerprogramm speichert, einen Prozessor zum Ausführen der computerlesbaren Anweisungen des gespeicherten Computerprogramms und einen Bus, der den Speicher mit dem Prozessor verbindet.

Andere Vorteile und Merkmale gehen aus der folgenden Beschreibung der bevorzugten Ausgestaltung und aus den Ansprüchen hervor.

Kurze Beschreibung der Zeichnungen

Fig. 1 ist ein Blockdiagramm eines Computersystems mit Mehrprozessorbetrieb, das zur Verwendung mit der Erfindung geeignet ist.

Fig. 2 zeigt die Beziehung zwischen einer Multithread- Applikation und einem gemeinsamen Speicher.

Fig. 3 ist eine grafische Darstellung eines Datenobjekts im Speicher.

Fig. 4 illustriert die Beziehung zwischen einer Multithread-Applikation und einem gemeinsamen Speicher, bei der es mehr Threads als Speicherpools gibt.

Fig. 5 ist ein Beispiel einer Applikation, die Speicherverwaltungsfunktionen von innerhalb eines Prozesses laufenden Threads aus aufruft.

Beschreibung der bevorzugten Ausgestaltungen

In Fig. 1, auf die Bezug genommen wird, hat eine simplistische Darstellung eines Multiprozessornetzwerks 10 einzelne Prozessoren 12a-12n vergleichbarer Fähigkeiten, die über einen Systembus 16 mit einem Systemspeicher 14 verknüpft sind. Alle Prozessoren haben gemeinsamen Zugang zum Systemspeicher sowie zu anderen E/A-Kanälen und Peripheriegeräten (nicht abgebildet). Jeder Prozessor dient zum Ausführen eines oder mehrerer Prozesse, beispielsweise einer Applikation.

Eine Applikation 20, Bezug nehmend auf Fig. 2, die auf einem oder mehreren der Prozessoren 12a-12n (Fig. 1) laufen kann, wird gezeigt. Applikation 20 hat hier einen einzelnen Thread 22, der Zugriff auf einen Abschnitt 24 allozierten Speichers innerhalb des Systemspeichers 14 hat. Dieser Speicherabschnitt wird als ein Speicherpool bezeichnet. Die Applikation hat auch einen Multithread-Teil, der hier mit vier Threads 30-33 gezeigt wird. Obwohl vier Threads abgebildet sind, kann sich die Anzahl der Threads, die zu einem bestimmten Zeitpunkt laufen, jederzeit ändern, da während der Ausführung einer Applikation wiederholt neue Threads erstellt und alte Threads zerstört werden können. Jeder der Threads 30 -33 kann beispielsweise auf einem entsprechenden der Prozessoren 12a-12n laufen. In anderen Applikationen können alle oder mehrere Threads auf einem einzigen Prozessor laufen. Thread 30 gilt als der Hauptthread, der den von der Applikation allozierten Speicherabschnitt 24 weiterhin als einzelnen Thread benutzt. Zusätzliche Threads 31-33 allozieren aber ihre eigenen Speicherpools 38-40 aus dem Systemspeicher 14. Somit ist jeder Thread mit einem Speicherpool zur Verwendung beim Ausführen seiner Operationen assoziiert. Während der Ausführung der mit den Threads laufenden Applikation kann jeder Thread unter Verwendung von Speicherallozierungsfunktionen (d. h. malloc, free, realloc), die unten ausführlicher beschrieben werden, wiederholt Speicherblocks aus seinem assoziierten Speicherpool allozieren, freigeben und reallozieren. Darüber hinaus wird im Allgemeinen zwar ein Thread als Hauptthread bezeichnet, einige der übrigen Threads können aber für bestimmte Zwecke bezeichnet werden.

Einrichten von Speicherpools

Die Speicherpoolzahl (NUM_POOLS) ist fest. Der malloc- Paketprogrammierer kann zwar die Poolzahl ändern, das Paket muss anschließend aber neu aufgebaut werden.

Das Einrichten eines Speicherpools für jeden Thread beinhaltet das Allozieren eines Speicherpuffers einer vorausgewählten Größe (z. B. 64 Kilobytes). Im Fall, dass die Größe des Speicherpools aufgebraucht wurde, kann die Größe des Speicherpools durch Allozieren zusätzlichen Speichers aus dem Systemspeicher dynamisch vergrößert werden. Der zusätzliche Speicher kann z. B. mit Hilfe einer sbrk () genannten Unix- Systemroutine alloziert werden, die in dieser Implementierung intern aus malloc heraus aufgerufen wird und den zusätzlichen Speicher in der vorausgewählten Größe des Pufferspeichers entsprechenden Inkrementen alloziert. Allozieren von zusätzlichem Speicher erfordert, dass der Pool gesperrt wird, was das gleichzeitige Ausführen anderer Speicherfunktionen verhindert. Die Größe des Speicherpuffers wird daher so ausgewählt, dass sie im Verhältnis zu der mit malloc() angeforderten durchschnittlichen Speichermenge groß ist, damit Aufrufe für eine Vergrößerung der Größe des Pools selten sind.

Jeder Speicherpool kann als eine Binärbaumdatenstruktur eingerichtet werden, wobei der Pool einzelne Speicherblöcke umfasst. Der Binärbaum ist nach Größe geordnet, kann aber auch nach Adresse geordnet sein. Alternativ können andere Datenstrukturen (z. B. verkettete Listen) verwendet werden; eventuell wird aber eine Binärbaumstruktur wegen der größere Geschwindigkeit bevorzugt, die sie beim Suchen bietet. Darüber hinaus kann ein ausgleichender oder selbstabgleichender Algorithmus verwendet werden, um die Effizienz der Suche weiter zu verbessern.

Jeder Speicherblock 40, Bezug nehmend auf Fig. 3, ist durch ein Datenobjekt 40 gekennzeichnet, das einen Anfangsblock 42 mit einer Länge hat, die mit den Ausrichtungsbedingungen der jweiligen verwendeten Hardwarearchitektur übereinstimmt. Beispielsweise erfordern gewisse Hardwarekonfigurationen, die von Sun Microsystems Inc., Mountain View, California, USA, verwendet werden, dass der Anfangsblock eine Länge von acht Bytes hat, um eine mit einer SPARC-Architektur übereinstimmende Ausrichtungsgrenze bereitzustellen. Die ersten vier Bytes des Anfangsblocks geben die Größe des Blocks an, während die übrigen vier Bytes eine Poolnummer angeben.

Speicherverwaltungsfunktionen

Jeder Thread 20-23 alloziert Speicher für seinen Speicherpool mit Hilfe eines Satzes von Speicherallozierungsroutinen ähnlich denen aus einer Standard- C-Bibliothek. Die Grundfunktion für das Allozieren von Speicher wird malloc genannt und hat die folgende Syntax:

void * malloc (size)

wobei size (Größe) die angeforderte Bytezahl andeutet.

Eine weitere Speicherallozierungsroutine ist free, die einen allozierten Speicherblock wieder in den Pool freien Speichers freigibt und die folgende Syntax hat:

void * free (old)

wobei old (alt) der Zeiger auf den freizugebenden Speicherblock ist.

Noch eine weitere Speicherallozierungsroutine ist realloc, die die Größe des durch malloc allozierten Speicherblocks anpasst. Realloc hat die folgende Syntax:

void * realloc (old, size)

wobei:

old (alt) der Zeiger auf den Speicherblock ist, dessen Größe geändert wird, und

.size (Größe) die neue Größe des Blocks ist.

Konvertieren eines bestehenden malloc-Pakets in ein Multithread-malloc-Paket

Um ein existierendes Speicherverwaltungspaket, das eine einzelne Sperre (Lock) verwendet, in ein paralleles Speicherverwaltungspaket zu konvertieren, werden alle in den oben beschriebenen Speicherverwaltungsfunktionen verwendeten statischen Variablen in statische Arrays konvertiert.

Beispielsweise werden die mit den Speicherpools assoziierten Binärbaumstrukturen als ein statisches Array gespeichert. Jedes Element des statischen Arrays wird durch seinen Thread- Index gekennzeichnet und ist mit einem bestimmten Speicherpool assoziiert. In jedem Array gibt es ein separates statisches Array-Element für jeden Pool. Durchsuchen der speziellen Datenstruktur (z. B. Binärbaum) nach jedem Thread kann daher parallel durchgeführt werden.

Jeder Thread kann daher wiederholt jedwede der obigen Routinen ausführen, um die Speicherallozierung ihrer assoziierten Speicherpools zu verwalten. Beispielsweise kann Hauptthread 30, wieder Bezug nehmend auf Fig. 2, eine Prozedur ausführen, in der Speicherblöcke innerhalb Speicherpool 24 zahllose Male alloziert, freigegeben und erneut alloziert werden können. Gleichzeitig können Threads 31-33 Prozeduren ausführen, in denen Speicher für die betreffenden Speicherpools 38-40 alloziert und von ihnen freigesetzt wird.

Abbildung von Threads auf Speicherpools

Wenn eine Speicherallozierungsfunktion aufgerufen wird, wird eine Thread-Identifizierungsroutine innerhalb jeder dieser Funktionen zum Identifizieren des Threads verwendet, der die Speicherallozierungsanforderung macht. Die Thread- Identifizierungsroutine gibt den Thread-Index des Threads zurück, der die Anforderung gemacht hat. Beispielsweise verwendet das Solaris Betriebssystem (BS), ein Produkt der Sun Microsystems Inc., in einer Implementierung eine thr_self () genannte Funktion.

Ein weiterer Algorithmus wird dann zum Abbilden jedes Thread-Index auf eine Speicherpoolnummer verwendet.

Beispielsweise verwendet die beschriebene Ausgestaltung das folgende, als GET_THREAD_INDEX bekannte Makro, das den Thread- Index erhält und eine assoziierte Poolzahl zurückgibt:

# define GET_THREAD_INDEX(self)\ ((self) == 1 ? 0 : 1 + ((self)-4% (NUM_POOLS-1)

wobei:

self der Thread-Index ist und

NUM_POOLS die Speicherpoolzahl ist.

Wie oben erwähnt, wird ein Thread allgemein als Hauptthread bezeichnet, wobei die übrigen Threads für andere Zwecke bestimmt werden. Beispielsweise verwendet das SOLARIS BS ein Threadnummerierungssystem, das den ersten Thread als einen Hauptthread, den zweiten und dritten Thread als Systemthreads und folgende Threads als Benutzerthreads reserviert. Bei dem obigen Makro werden die Speicherpools 0 bis NUM_POOLS-1 nummeriert. Der erste Teil des obigen Makros (self == 1 ? 0) stellt sicher, dass der Hauptthread immer mit der ersten Poolnummer assoziiert wird. Wenn self also gleich 1 ist (d. h. es ist der Hauptthread), dann ist die Poolnummer 0.

Andernfalls wird, wie im restlichen Teil des Makros nach dem ":" gezeigt, der Rest des Verhältnisses des Thread-Indexes minus der Konstanten vier zu NUM_POOLS-1 dann zur Zahl 1 addiert, um bei der Poolnummer anzukommen. Wenn es zum Beispiel nur vier Speicherpools gibt (d. h. NUM_POOLS = 4) und der Thread-Index 4 ist, dann ist die vom Makro zurückgegebene assoziierte Poolnummer 1. Thread-Index 5 und Thread-Index 6 hätten mit 2 bzw. 3 nummerierte assoziierte Speicherpools.

In Applikationen, in denen die zu jedem beliebigen Zeitpunkt bestehende Anzahl von Threads die Anzahl eingerichteter Pools übersteigt, nutzen die zusätzlichen Threads Speicherpools gemeinsam mit einem anderen mit diesem Pool assoziierten Thread. In Fig. 4 wird zum Beispiel eine Applikation gezeigt, in der ein neuer fünfter Thread 34 erstellt wurde. Weil nur vier Speicherpools eingerichtet wurden, wird das oben erwähnte Makro zum Abbilden von Thread 34 auf den ersten Speicherpool 24, der ursprünglich nur mit Thread 30 assoziiert war, benutzt. In dieser Situation verhindert die mit Speicherpool 24 assoziierte mutex-Sperre Zugriff durch Thread 24 oder Thread 34, wenn der andere den Pool benutzt. Im Beispiel des vorangehenden Absatzes würde Makro GET_THREAD_INDEX Threads mit Thread-Index 4 und Thread- Index 7 auf Speicherpool Nr. 1 abbilden.

Code-Lacking von Speicherpools

Jeder Speicherpool 24 und 38-10 wird durch seine eigene gegenseitig ausschließende (mutex-)Sperre (Schlossvariable) geschützt. Wie die mit jedem Speicherpool assoziierten Datenstrukturen werden auch mutex-Sperren in einem statischen Array gespeichert. Jede mutex-Sperre verursacht in einem Thread, der einen oder mehr Speicherblöcke aus seinem eigenen Speicherpool alloziert, dealloziert oder realloziert, keine Verzögerung. Wenn aber ein Thread, der nicht mit einem bestimmten Speicherpool assoziiert ist, versucht, auf einen Speicherblock zuzugreifen, der von dem mit diesem Pool assoziierten Thread bereits alloziert wurde, hindert die mutex-Sperre den nicht assoziierten Thread am Deallozieren oder Reallozieren eines Speicherblocks aus diesem Pool. Die Sperre schützt somit die Speicherblöcke vor einer gleichzeitigen Aktualisierung oder Benutzung durch mehr als einen Thread, wodurch die Datenverfälschung im Speicherblock verhindert wird. Derartige Versuche zum Allozieren, Deallozieren oder Reallozieren von Speicherblöcken aus einem Speicherpool, der nicht mit einem Thread assoziiert ist, sind relativ selten. Dieses Leistungsmerkmal ergibt eine wesentliche Verbesserung der Geschwindigkeitsleistung des Systems gegenüber konventionellen Systemen, bei denen eine einzige mutex-Sperre für alle Speicherverwaltungsroutinen verwendet wird. Die Verwendung einer einzigen mutex-Sperre kann die Leistung einer Multithread-Applikation bedeutend verschlechtern. Bei diesem Ansatz müssen, sobald ein Thread eine Speicherverwaltungsfunktion aufruft (d. h. malloc, free oder realloc), alle anderen Threads warten, bis der Thread die Durchführung seiner Speicherverwaltungsfunktion beendet hat. Durch separate mutex-Sperren für jeden Speicherpool kann jeder Thread parallel seinen eigenen Speicher innerhalb seines eigenen Speicherpools allozieren und freigeben, während der Zugriff von nicht assoziierten Threads verhindert wird.

Da Speicherblöcke von einem Thread wiederholt alloziert, freigegeben und realloziert werden, kann es sein, dass der Speicherpool in immer kleinere Blöcke fragmentiert wird. In periodischen Abständen wird Zusammenlegen oder Mischen freigegebener benachbarter Speicherblöcke durchgeführt, um größere Speicherblöcke zu bilden, die vom Thread realloziert werden können. Bevor ein Speicherblock aber mit einem angrenzenden Speicherblock zusammengelegt werden kann, bestimmt die beschriebene Ausgestaltung aber erst, ob die Blöcke aus dem gleichen Pool sind. Wenn nicht, werden die Blöcke nicht zusammengelegt, wodurch die Möglichkeit einer Datenverfälschung vermieden wird.

Zusammenlegen von alloziertem Speicher (merge malloc pools)

In welchem Maße die einzelnen Threads Speicherverwaltung verwenden, kann sehr unterschiedlich sein. Beispielsweise können Threads 31-33, wobei wieder auf Fig. 2 Bezug genommen wird, ihre Aufgaben vor Abschluss der vom Hauptthread 30 durchgeführten Aufgaben beenden. In derartigen Situationen kann der Hauptthread eine optionale Schnittstellenfunktion aufrufen, den von Threads 31-33 allozierten Speicher auf den Hauptthread 30 überträgt. Mit anderen Worten heißt das, dass die Funktion vom Hauptthread am Ende des Multithread- Teils aufgerufen werden kann, um den zuvor von den anderen Threads allozierten Speicher mit dem Hauptthread zusammenzulegen. Die in dieser Ausgestaltung verwendete Routine hat den folgenden Prototyp:

void merge_malloc_pools (void);

Die Benutzung dieser Funktion wird in Applikationen, in denen mehrere Threads eine bedeutende Speicherverwaltung in der gesamten Applikation durchführen, eventuell nicht benötigt. In Fig. 5, auf die Bezug genommen wird, wird eine simplistische Darstellung einer Applikation gezeigt, die innerhalb Hauptthread 30 und Benutzerthread 31 läuft. Es wird hier vorausgesetzt, dass Speicherpools 24 und 38 (Fig. 2), die mit Thread 30 bzw. Thread 31 assoziiert sind, bereits eingerichtet wurden. Bezüglich dem Hauptthread 30 findet ein erster Aufruf der malloc-Routine 50 statt, der einen Speicherblock mit SIZE#1 Bytes anfordert. Später in der Applikation wird ein erster free-Routine-Aufruf 52 durchgeführt, um einen durch Zeiger OLD (Alt) identifizierten Speicherblock zurückzugeben. Zu diesem Zeitpunkt wird allgemein ein Zusammenlegen durchgeführt, um den zurückgegebenen Speicherblock mit einem angrenzenden Block zu vereinen, sofern sie beide aus dem gleichen Speicherpool sind. Noch später im Thread wird die malloc-Routine ein zweites Mal aufgerufen 54, wodurch ein Speicherblock mit SIZE#2 Bytes angefordert wird. Es folgt ein realloc-Aufruf 56, der fordert, dass die Größe eines vom Zeiger OLD identifizierten Speicherblocks wie folgt auf SIZE#3 Bytes geändert wird. Thread 31 wird beim Ausführen von Prozeduren gleichzeitig mit Thread 30 gezeigt. Beispielsweise findet ein erster Aufruf der malloc-Routine 60 statt, dem etwas später ein erster Aufruf der free-Routine 62 folgt. Schließlich wird in diesem Beispiel nach Abschluss des Multithread-Teils der Applikation eine merge_malloc_pools-Routine 64 aufgerufen, um von Thread 31 allozierte Speicherblöcke mit dem Hauptthread 30 zusammenzulegen.

Als Anhang ist Quellcodesoftware für eine Implementierung eines Verfahrens zum Konvertieren eines existierenden malloc- Pakets in eine Multithreading-Version eines malloc-Pakets angefügt. Der Quellcode stellt eine Version des Programms dar, die auf dem in The C programming language (Die Programmiersprache C), B. W. Kernighan und D. M. Richie, Prentice Hall (1988), beschriebenen Satz von Speicherallozierungsroutinen basiert.

Andere Ausgestaltungen liegen im Rahmen der folgenden Ansprüche.


Anspruch[de]

1. Verfahren zur Speicherallozierung in einer Multithreading-Computerumgebung, bei dem eine Mehrzahl von Threads innerhalb eines Prozesses parallel laufen, wobei jeder Thread Zugriff auf einen Systemspeicher hat, wobei das Verfahren Folgendes umfasst:

Einrichten einer Mehrzahl von Speicherpools im Systemspeicher;

Abbilden jedes Threads auf einen der genannten Mehrzahl von Speicherpools und

für jeden Thread das dynamische Allozieren von Benutzerspeicherblöcken von dem assoziierten Speicherpool.

2. Verfähren nach Anspruch 1, bei dem der Schritt des dynamischen Allozierens von Speicherblöcken das Bezeichnen der Anzahl von Bytes in dem Block aufweist, der alloziert werden soll.

3. Verfahren nach Anspruch 1, ferner umfassend den Schritt des Verhinderns von gleichzeitigem Zugriff auf einen Speicherpool durch verschiedene Threads.

4. Verfahren nach Anspruch 1, bei dem der Schritt des Einrichtens eines Speicherpools für jeden Thread ferner das Allozieren eines Speicherpuffers einer vorausgewählten Größe aufweist.

5. Verfahren nach Anspruch 4, ferner umfassend den Schritt des dynamischen Vergrößerns der Größe des Speicherpools durch Allozieren von zusätzlichem Speicher aus dem Systemspeicher in Schritten, die der vorausgewählten Größe des Pufferspeichers gleich sind.

6. Verfahren nach Anspruch 4, bei dem die vorausgewählte Größe des Pufferspeichers 64 Kilobytes beträgt.

7. Verfahren nach Anspruch 1, ferner umfassend den Schritt des Übertragens von Speicher durch einen der Threads aus dem Speicherpool eines anderen der Threads zu seinem Speicherpool.

8. Verfahren nach Anspruch 1, bei dem jeder Speicherpool von einem Array statischer Variablen definiert wird, die durch einen mit einem Speicherpool assoziierten Thread-Index gekennzeichnet sind.

9. Verfahren nach Anspruch 8, bei dem jeder Speicherpool als eine Datenstruktur von Speicherblöcken gepflegt wird.

10. Verfahren nach Anspruch 9, bei dem jeder Speicherblock einen Anfangsblock mit der Größe des Speicherblocks und dem Speicherpoolindex, mit dem er assoziiert ist, aufweist.

11. Verfahren nach Anspruch 10, bei dem die Größe des Blocks und des Speicherpoolindexes jeweils vier Bytes beträgt.

12. Verfahren nach Anspruch 1, umfassend den Schritt der Deallozierung eines Speicherblocks zum Speicherpool durch jeden Thread.

13. Verfahren nach Anspruch 12, bei dem der Thread, der den Speicherblock ursprünglich alloziert hat, ihn zu seinem assoziierten Speicherpool dealloziert.

14. Verfahren nach Anspruch 12, ferner umfassend den Schritt des Mischens deallozierter Speicherblöcke und Verhindern des Mischens von Speicherblöcken aus verschiedenen Pools.

15. Verfahren nach Anspruch 1, ferner umfassend den folgenden Schritt: Ändern der Größe eines allozierten Blocks von von einem Speicherpool alloziertem Speicher.

16. Computerlesbares Speichermedium, das ein auf einem Computer mit einem Speicher ausführbares Computerprogramm zum Allozieren von Speicher in einer Multithreading- Computerumgebung speichert, wobei eine Mehrzahl von Threads innerhalb eines Prozesses parallel laufen, wobei jeder Thread Zugriff auf einen Systemspeicher hat, wobei das gespeicherte Programm Folgendes umfasst:

computerlesbare Anweisungen, die im Systemspeicher eine Mehrzahl von Speicherpools einrichten;

computerlesbare Anweisungen, die jeden. Thread auf einen der genannten Mehrzahl von Speicherpools abbilden, und

computerlesbare Anweisungen, die für jeden Thread dynamisch Benutzerspeicherblöcke aus dem assoziierten Speicherpool allozieren.

17. Computerlesbares Speichermedium nach Anspruch 16, bei dem das gespeicherte Programm ferner Computeranweisungen aufweist, die gleichzeitigen Zugriff auf einen Speicherpool durch verschiedene Threads verhindern.

18. Computerlesbares Speichermedium nach Anspruch 16, bei dem das gespeicherte Programm ferner Computeranweisungen aufweist, die veranlassen, dass einer der Threads Speicher aus dem Speicherpool eines anderen Threads zu seinem Speicherpool überträgt.

19. Computerlesbares Speichermedium nach Anspruch 16, bei dem jeder Speicherpool von einem Array statischer Variablen definiert wird, die durch einen mit einem Speicherpool assoziierten Thread-Index gekennzeichnet sind.

20. Computerlesbares Speichermedium nach Anspruch 16, bei dem das gespeicherte Programm ferner Computeranweisungen aufweist, die deallozierte Speicherblöcke mischen und das Mischen von Speicherblöcken aus verschiedenen Pools verhindern.

21. System, umfassend:

Speicher, wobei ein Teil des genannten Speichers ein Computerprogramm zum Allozieren von Speicher in einer Multithreading-Computerumgebung speichert, bei dem eine Mehrzahl von Threads innerhalb eines Prozesses parallel laufen, wobei jeder Thread Zugriff auf den Speicher hat, wobei das gespeicherte Programm Folgendes umfasst:

computerlesbare Anweisungen, die im Speicher eine Mehrzahl von Speicherpools einrichten;

computerlesbare Anweisungen, die jeden Thread auf einen der genannten Mehrzahl von Speicherpools abbilden, und

computerlesbare Anweisungen, die für jeden Thread dynamisch Benutzerspeicherblöcke aus dem assoziierten Speicherpool allozieren;

einen Prozessor zum Ausführen der genannten computerlesbaren Anweisungen; und

einen Bus, der den Speicher mit dem Prozessor verbindet.







IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

Patent Zeichnungen (PDF)

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com