DE69520765T2 - Bereitstellung von freigegebenem elektronischem Speicher - Google Patents

Description

• Diese Erfindung betrifft elektronisches Datenverarbeiten mit adressierbarem Speicher, der während des Betriebs zur Verwendung freigegeben wird, und spezieller eine Vorrichtung, die von einem solchen elektronischen Datenprozessor gesteuert wird, in dem ein solcher zurückgeführter Speicher zur Wiederverwendung angeordnet ist.
• Während einer normalen Verwendung einer elektronischen Datenverarbeitungsanlage wird elektronischer Speicher, der verwendet worden ist, zur Wiederverwendung freigegeben. Solche Speicherblöcke sind typischerweise von einer beträchtlichen Größenschwankung und in den unterschiedlichsten Stellen vorhanden. Obwohl Muster von Größen für solchen zurückgeführten Speicher und ihren Stellen für einzelne Anwendungen grob vorhergesagt werden können, ist diese Information weit davon entfernt, für eine direkte Verwendung ausreichend genau zu sein, um den zurückgeführten Speicher noch einmal zu verwenden.
• Vor dieser Erfindung ist solcher zurückgeführte Speicher nach einer gewissen Kategorie sortiert, wie z. B. nach Größe oder nach Reihenfolge von Adressen, und durch Durchsuchen einer solchen Sortierung zur Wiederverwendung angeordnet worden. Das US-Patent Nr. 5,109,336 an Guenther et al. offenbart eine solche Wiedergewinnung von Speicher. In diesem Patent werden Speicherblöcke von unterschiedlichen vorbestimmten Größen offenbart, wie sie von dem Programm, das ausgeführt wird, zugewiesen werden. Zurückgeführter Speicher von solchen Größen wird zu diesen Zuweisungen hinzugegeben. Wo der zugewiesene Speicher nicht verwendet wird, wird sämtlicher andere zurückgeführte Speicher in der Reihenfolge durchsucht, in der er sortiert worden ist. Diese Erfindung verwendet nicht solche zugewiesenen Speicherblöcke und beschränkt die Suche durch sortierten zurückgeführten Speicher auf eine unten zu beschreibende Weise.
• Diese Erfindung verwendet Adresszeiger, um eine verbesserte Wiedergewinnung von zurückgeführtem Speicher zu erzielen. Die Verwendung von solchen Zeigern ist an sich in breitem Umfang herkömmlich. Das US-Patent Nr. 4,807,120 an Courts offenbart die Verwendung von Zeigern in einem System, das dieser Erfindung nicht besonders ähnlich ist, außer dass es in Bezug zu zurückgeführtem Speicher zur Speicherverwaltung dient.
• Das IBM Technical Disclosure Bulletin, Band 18, Nr. 8, Seiten 2582-2583, Januar 1976, "Space Reclamation in Virtual Storage Systems " E. T. Boyle, K. D. Ryder & I. H. Schneider offenbart ein Verfahren zum Wiedergewinnen von fragmentiertem virtuellem Speicher, um vergeudeten Raum zu minimieren. Bei diesem Verfahren werden jegliche nicht verwendeten Speicherbereiche in einer von N der Größe nach geordneten Listen erfasst, wobei jede Liste Speicher in einem vorgegebenen Größenbereich enthält. Die geeignete Liste wird abgesucht, um den ersten freien Speicherbereich von passender Größe zu finden.
• Die bevorzugte Ausführungsform dieser Erfindung kategorisiert zurückgeführten Speicher gemäß Größen, die sich um eine einzige Ganzzahl von Potenzen von 2 unterscheiden. Der "gmalloc"-Code eines öffentlichen UNIX(Schutzmarke)-Quellprogrammprotokolls weist Speicher einem Block zu, der sich um solche Potenzen von 2 unterscheidet. Jedoch stehen diese Zuweisungen auf keinerlei dieser Erfindung ähnlichen Weise in Zusammenhang mit zurückgeführtem Speicher, da die Zuweisungen keinen nach den Zuweisungen zurückgeführten Speicher beinhalten.
• Moderne Computerentwicklung verwendet einen Arbeitsspeicherplatz, der im Allgemeinen als "Halde" oder "freier Speicher" bezeichnet wird. Der Speicherverwaltungsfunktion des Datenprozessors wird die Steuerung dieses typischerweise großen Speicherplatzes übergegeben, und sie spricht auf Programmanforderungen für Speicherblöcke an, indem ein geeigneter Block identifiziert oder erzeugt wird und indem dessen Steuerung dem Anforderer in einem Prozess übergegeben wird, der als Zuweisung bekannt ist. Nach Ausführen des Aktivprogramms mit einem gegebenen Speicherblock, ein Prozess, der als "Freigeben" bekannt ist, überlässt es dessen Steuerung dem Speicherverwalter. Der Speicherverwalter speichert dann den Block in einer gewissen Form, von der er zu einem späteren Zeitpunkt für eine andere Verwendung in demselben oder einem anderen Programm wiedergewonnen werden kann.
• Herkömmlicherweise müssen Speicherverwalter für Leistungsfähigkeit Speicherverwendungswirkungsgrad opfern. Da die Leistungskosten eines Sortierens von Speicherblöcken in diesen Systemen zu groß sind, sind umfassende Suchvorgänge oder intelligente Zuordnungsstrategien nicht praktikabel. In der Folge treffen ihre Suchvorgänge häufig auf zahlreiche Blöcke, die zu klein sind, um nützlich zu sein, wodurch der Programmentwerfer gezwungen ist, die gewünschte Größe entweder vom ersten freien Block, der angetroffen wird, abzutrennen, der groß genug ist, um die Anforderung zu erfüllen, oder eine begrenzte Anzahl von zulässigen Blockgrößen zu verwenden und den Unterschied zwischen der benötigten Größe und der bereitgestellten Größe zu vergeuden. Obwohl dieser Lösungsweg im Allgemeinen in Systemen mit einem kleinen bis mäßigen Speichernutzungsverhältnis erfolgreich ist, können sich Systeme, die eine höhere Speichernutzung erfordern, die Vergeudung nicht leisten. In diesen Umgebungen können solche Systeme eine signifikante Suchanstrengung aufwenden, und sie können unerwünschte Fragmentierungsmuster zeigen, die zu vorzeitigen "Speicher voll"-Bedingungen führen. Wenn die Fragmentierung schwerwiegend wird, ist es nicht ungewöhnlich, dass "nicht genug Speicher"-Fehler auftreten, obwohl das Zehnfache des angeforderten Speichers oder mehr zur Verfügung steht.
• Diese Erfindung erfordert mehr anfänglichen Computeroverhead als einfache ungeordnete Systeme, gleicht dieses Defizit aber bei Suchvorgängen schnell aus, die mehr als nur sehr wenige zurückgeführte Speicherblöcke beinhalten. Weiter ist ihr einzigartiger Lösungsweg so entworfen, dass sorgfältig ausgearbeitete Zuweisungsstrategien und andere Speicherverbesserungen ermöglicht werden, die in unter "Fragmentierung" leidenden Speichersystemen sonst leistungsverhindernd wären.
• Die Erfindung stellt eine Vorrichtung nach Anspruch 1 bereit.
• Gemäß zumindest den bevorzugten Ausführungsformen der Erfindung wird Speicher angefordert, indem ein einziges Wort adressiert wird, das Speicher von dem Größenbereich zugewiesen ist, der den gesuchten Speicher umfasst. Dieses einzige Wort umfasst einen Adresszeiger zu einer sortierten Liste von Speicherblöcken mit Größen im dieser Adresse zugewiesenen Größenbereich. Vorzugsweise ist die Liste der Größe nach vom Größten bis zum Kleinsten sortiert, und der einzige Adresszeiger ist die Adresse des größten Speicherblocks dieser sortierten Liste. Jeder Eintrag in der sortierten Liste enthält einen Zeiger zum nächsten Eintrag in der sortierten Liste sowie er Daten enthält, die die Speichergröße kennzeichnen, und andere solche Routinedaten, die diesen Datenblock beschreiben. Der der Speichergröße zugewiesene Zeiger wird als Adresse verwendet, um den ersten Speicherblock in der Liste zu prüfen, und dieser und die folgenden Speicherblöcke, auf die hingezeigt wird, werden geprüft, bis der Datenprozessor feststellt, dass ein adressierter Speicherblock Speicher von einer größeren (oder kleineren) Größe enthält als die, die gesucht wird, und der nächste adressierte Speicherblock Speicher einer kleineren (oder größeren) Größe enthält als die, die gesucht wird (Abwandlungen umfassen ein Anhalten bei Größen, die genauso groß sind, unter der Voraussetzung, dass der übrigbleibende Speicher, der davon genommen ist, wieder von demselben Programm, das ausgeführt wird, durchsucht wird; eine andere Abwandlung ist Sortieren nach Verwendungshäufigkeit). Zurückgeführter Speicher wird in die Liste für den Größenbereich dieses Speichers einsortiert. Vorzugsweise unterscheiden sich die Größenbereiche um ganzzahlige Potenzen von 2, und deshalb wird die Größenkategorie von zurückgeführtem Speicher festgelegt, indem einfach binäre Daten verschoben werden, die die Größe kennzeichnen, und die Verschiebungen gezählt werden, um eine numerische Null zu erreichen.
• Wenn während des Aktivprogramms Speicher benötigt wird, werden nur Speicherblöcke im vorbestimmten Bereich von dem, der benötigt wird, durchsucht. Außerdem werden keine Speicherblöcke von derselben Größe oder innerhalb von einem engen Größenbereich in die Sortierung eingeschlossen, sondern auf sie wird durch eine zweite Zeigeradresse innerhalb der einen von diesem Größenbereich, die durch Prüfen der Sortierung erreicht wird, hingezeigt. Wenn dieser Block verwendet wird, identifiziert der Zeiger in diesem Block einen nächsten Block, um den ersten Block in der sortierten Liste zu ersetzen. Demgemäß wird im typischen Suchvorgang nur ein Block von zurückgeführtem Speicher von in der Nähe von jeder Größe geprüft.
• Die Einzelheiten dieser Erfindung werden nur anhand eines Beispiels in Verbindung mit den beigefügten Zeichnungen beschrieben, bei denen Fig. 1 für die Vorrichtung veranschaulichend ist, die einen Drucker unterstützt, und Fig. 2 veranschaulichend für Daten ist, die eine Speichergrößenverteilung in logarithmischen Größenkategorien zeigen.
• Die Standardterminologie für einen Datenverarbeitungssteuercode, um eine begrenzte Wiederholungsfunktion auszuführen, ist eine Routine. Eine solche Terminologie wird hier verwendet, um einen Steuercode zu bezeichnen, um den Datenverarbeitungsprogrammschritt zu programmieren, um eine spezifizierte Funktion auszuführen. Routinen werden üblicherweise durch eine andere Routine, die den Anfangscode in der Routine adressiert, aktiviert (typische Terminologie: aufgerufen).
• In dieser Anmeldung sagt man, dass ein Zeiger eine andere Adresse erreicht, wenn er durch den Datenprozessor, der die Adresse adressiert, auf die hingezeigt wird, die erreichte Adresse findet oder er einen Zeiger findet, der zu der erreichten Adresse gehört oder zu einer Adresse mit einem Zeiger, der ähnlich entweder auf die erreichte Adresse hinzeigt, oder anderen Zeiger, der schließlich zur erreichten Adresse führt.
• Diese Ausführungsform verwendet Standarddatenverarbeitungsadressen, die in digitalen Codes vorliegen, und ein elektronisches Standardspeicheradressieren, das solche Adressen verwendet. Diese sind äußerst herkömmlich und werden deshalb nicht in weiterer Einzelheit beschrieben. Zeiger sind solche digitalen Codes, auf die als Adresse eingewirkt wird, um eine Momentadresse auf eine Adresse zu beziehen, die weit von der Zeigeradresse getrennt sein kann.
• Eine tatsächliche Implementierung arbeitet mit 32 Bit-Wörtern, was bedeutet, dass jede Adresse 32 Bit spezifiziert und ein Bezug auf die Speichergröße ziffernweise durch eine Anzahl von 32 Bit-Wörtern erfolgt. (Alternativ werden Wortgrößen, speziell 16-Bit-Wörter, ebenso bevorzugt.)
• Diese bevorzugte Implementierung ist so ausgelegt, dass sie auf drei Merkmale von Speicherverwendung eingeht, die besonders in Anwendungen, wie z. B. Druckern, gefunden werden: eine verhältnismäßig große Haufengröße; potenziell schwerwiegende Fragmentierungsauswirkungen; und signifikante Leistungs- und Betriebsmittelbegrenzungen.
• Wie in Fig. 1 dargestellt, ist ein erstes Element dieser Implementierung eine Tabelle oder Liste von Adressen 1, die darstellen, wo sich alle freien Speicherblöcke von der Größe 0 bis 7, 2 E n bis 2 E n + 1 befinden, wobei n aufeinanderfolgende Ganzzahlen zwischen 3 und 14 und gleich oder größer als 32768 sind. Jede Adresse in Tabelle 1 bildet einen Adresszeiger zum Einstieg zu einer sortierten Liste von Rückführspeicherblöcken in den Größenbereichen von 0 bis 7, 2 E n bis 2 E n + 1 und 32768 und größer. Folglich weist die Adresse 1a in Tabelle 1 einen Zeiger auf, der alle Speicherblöcke einer Größe 0 bis 7 erreicht; die Adresse 1b in Tabelle 1 weist einen Zeiger auf, der alle Speicherblöcke einer Größe 8 bis 15 erreicht; die Adresse 1c in Tabelle 1 weist einen Zeiger auf, der alle Speicherblöcke einer Größe 16 bis 31 erreicht; die Adresse 1d in Tabelle 1 weist einen Zeiger auf, der alle Speicherblöcke einer Größe 32 bis 63 erreicht; die Adresse 1e in Tabelle 1 weist einen Zeiger auf, der alle Speicherblöcke einer Größe 64 bis 127 erreicht; die Adresse 1f in Tabelle 1 weist einen Zeiger auf, der alle Speicherblöcke einer Größe 128 bis 255 erreicht; die Adresse 1g in Tabelle 1 weist einen Zeiger auf, der alle Speicherblöcke einer Größe 256 bis 511 erreicht; die Adresse 1h in Tabelle 1 weist einen Zeiger auf, der alle Speicherblöcke einer Größe 572 bis 1023 erreicht; die Adresse 1i weist einen Zeiger auf, der alle Speicherblöcke einer Größe 1023 bis 2047 erreicht; der Zeiger 1j weist einen Zeiger auf, der alle Speicherblöcke einer Größe 2048 bis 4095 erreicht; die Adresse 1k weist einen Zeiger auf, der alle Speicherblöcke einer Größe 4096 bis 8191 erreicht; die Adresse 1l weist einen Zeiger auf, der alle Speicherblöcke einer Größe 8192 bis 16383 erreicht; die Adresse 1m weist einen Zeiger auf, der alle Speicherblöcke einer Größe 16284 bis 32767 erreicht; die Adresse 1n weist einen Zeiger auf, der alle Speicherblöcke einer Größe 32768 und größer erreicht.
• Die Tabelle 1 mit ihren Zeigern, die auf Speicher von einer vorbestimmten Größe gerichtet sind, kann als eine Hash-Magazin-Struktur bezeichnet werden, wobei sich der Begriff "Magazin" auf die Trennung von Speicherblöcken in ein Kontinuum von unterschiedlichen Größenbereichen bezieht.
• Wie in Fig. 1 dargestellt, sind jede von den Adressen in Fig. 1 Zeiger, die einen Speicherblock 3 identifizieren. Folglich ist die Adresse 1f ein Zeiger zum Speicherblock 3a, der größenmäßig der größte Block von freiem Speicher zwischen 128 und 255 Wörtern ist. Wenn es kleinere Blöcke von freiem Speicher gibt, die größenmäßig größer als 128 sind, ist ein Zeiger am Speicherblock 3a eine Adresse zum Speicherblock von nächst kleinerer Größe 3b. Wenn es einen noch kleineren Speicherblock gibt, der größenmäßig größer als 128 ist, ist ein Zeiger am Speicherblock 3b eine Adresse zum Speicherblock von nächst kleinerer Größe 3c. In einer typischen Sachlage kann es Hunderte von freien Speicherblöcken in einem gegebenen Magazin geben. Der Endblock in einer Liste weist einen Null-Zeiger auf, der ganz aus Null-Bits bestehen kann, von dem es ersichtlich ist, dass er zu keinem anderen kleinen Block zeigt, sondern stattdessen das Ende der Liste signalisiert. Bestenfalls sämtliche Speicherblöcke 3 in einem gegebenen Magazin werden für einen Speicher der richtigen Größe durchsucht, während die anderen nicht durchsucht werden, wenn der Suchvorgang durch einen Datenprozessor 5 eingeleitet wird, der die Adresse in Tabelle 1 adressiert, die das Magazin für speicherenthaltende Blöcke 3, 7 in dem Bereich des Speichers bildet, der vom Datenprozessor 5 durchsucht wird. Wenn der Datenprozessor 5 einen freien Speicher von der Größe von 3000 Wörtern sucht, ist z. B. die Steuerroutine für eine Speicherauswahl die Datenprozessor 5-Adressen 1j in der Tabelle 1-Liste. Als Nächstes führt die Steuerroutine im Datenprozessor 5 als Adresse den Zeiger in 1j aus, um den größten Speicherblock 3f im Magazin von 1j zu erreichen. Nur ein paar zurückgeführte Speicher 3, 7 sind zur Veranschaulichung in Fig. 1 dargestellt. Jede Liste endet mit einem Speicherblock mit einem Null-Zeiger 3e, 3h und 3i, der für die Listen 1f, 1a und 1n veranschaulicht ist.
• Es versteht sich natürlich und ist in breitem Umfang herkömmlich, dass Befehle oder Daten, auf die der Reihe nach in Datenverarbeitungsroutinen zugegriffen wird, nicht notwendigerweise in einer solchen Reihenfolge im Speicher vorliegen mögen, solange wie der Programmcode, der ausgeführt wird, wirksam ist, um die Befehle und Daten in der erforderlichen Reihenfolge zu erreichen. Dies kann auch für Speicherblöcke zutreffen, da das Ende einer Ziffernfolge von Adressen zu freiem Speicher einen Verknüpfungsbefehl einer gewissen Art zu einem anderen Teil von freiem Speicher enthalten könnte. Typischerweise ist jedoch in dieser Ausführungsform ein Speicherblock derjenige Speicher, der zwischen zwei Datenverarbeitungsadressen und ihren dazwischenliegenden Ziffernadressen vorhanden ist und enthält jeder Block von zurückgeführtem Speicher Daten, die explizit seine Größe kennzeichnen.
• Ähnlich befindet sich eine Zeigeradresse nicht notwendigerweise körperlich in der Nähe des Speichers, den sie darstellt, da sie einer anderen Adresse zugeordnet sein kann, die zu dem tatsächlichen Speicherblock zeigt. Typischerweise belegt jedoch in dieser Anmeldung die Zeigeradresse für jeden Block von freiem Speicher 3 körperlich diesen Speicher, da er sonst ungenutzt ist. Die Größe dieses Speicherblocks 3 kennzeichnende Daten und andere Nebeninformation, einschließlich des unmittelbar unten zu beschreibenden "dritte Dimension"-Zeigers belegen ähnlich auch körperlich ihren Speicherblock 3, da er sonst ungenutzt ist. Für einen Betriebswirkungsgrad im Rückwärtssuchen tragen die Speicherblöcke 3 einen Zeiger zum vorhergehenden Speicherblock 3, wie es herkömmlich ist.
• Man kann Tabelle 1 als eine erste Dimension eines Suchvorgangs betrachten, und man kann die sortierten Speicherblöcke 3 von jedem Magazin von Tabelle 1 als zweite Dimension eines Suchvorgangs betrachten. Der Suchvorgang wird weiter dadurch begrenzt und wirkungsvoller gemacht, indem man mehr als einen Speicherblock 3 von derselben Größe aus der Sortierliste herausnimmt. Wie veranschaulichend in Fig. 1 als runde Punkte 7 dargestellt, sind folglich Speicherblöcke, die von derselben Größe sind, nicht Teil der Blöcke 3 in der Sortierliste. Stattdessen befindet sich nur einer in dieser Liste. Z. B. Block 3a, der mit zwei anderen Blöcken 7a und 7b dargestellt ist. Der Block 3a enthält einen zweiten Adresszeiger in einer vorbestimmten Stelle, von dem es ersichtlich ist, dass er signalisiert, dass ein Block 7a von derselben Größe wie Block 3a vorhanden ist. Wenn der Block 3a zur Verwendung gewählt wird, wird das Vorhandensein des zweiten Zeigers durch den Datenprozessor 5 festgestellt. Wenn der zweite Zeiger gefunden ist, kann der Sortierzeiger zum Block 3b an Block 7a angebracht werden, und der zweite Zeiger zum Block 7b wird nicht geändert, weil ein weiterer Block 7b vorhanden ist und ein weiterer Block mit derselben Größe ist wie die Blöcke 3a und 7a. Wenn kein Block von derselben Größe vorhanden ist, ist der zweite Zeiger ein Null-Zeiger, der ganz aus Nullen bestehen kann und von dem ersichtlich ist, dass er nicht zu einem anderen Speicherblock 7 zeigt. Solch ein Null-Zeiger wird in Fig. 1 durch einen gebogenen Pfeil angedeutet, der nach unten zeigt.
• Die Speicherblöcke 7 können in der Anzahl veränderlich sein, wie durch Block 7c und 7d und eine zusätzliche Anzahl im weggelassen Teil der Zeichnung, um Block 7e zu erreichen, veranschaulicht ist. Der letzte Block in der 1a-Liste zeigt zu Blöcken identischer Größe 7g und 7h, wobei der letzte 7h einen Null-Zeiger für diese Liste aufweist. Der für den Systemspeicher durch den Datenprozessor 5 verwendete erste Block ist der nächste Block 7, 7g in diesem Fall. Der übrigbleibende Block 7, wie z. B. ein 7h, wird dann verwendet. Der letzte Block, der verwendet wird, ist Block 3.
• Diese Verknüpfung von Speicherblöcken identischer Größe 7, während nur einer in der Sortierliste enthalten ist, kann zum Zusammengruppieren von Blöcken ausgeweitet werden, die größenmäßig nahe beieinanderliegen. Nichtsdestoweniger ist diese Technik besonders wirkungsvoll für kleine Größenbereiche, wie z. B. 64 bis 127, da sich alle Einträge in dieser Kategorie größenmäßig nicht mehr als um 63 Stellen unterscheiden können. Die größengleichen Listen können in diesem Größenbereich sehr groß sein.
• Wie es für das Aussortieren eines Elementes aus einer sortierten Liste standard ist, wandelt sich der Zeiger zum aussortierten Speicher 3 in einen Zeiger zum nächsten Block in der Liste um. Wo 3b zur Verwendung gewählt wird, geht folglich der Zeiger in 3a in einen Zeiger zu 3c über, wobei der Block 3 der nächst kleineren Größe übrigbleibt.
• Wo der Block 3c gewählt wird, der einen größengleichen Block 7 aufweist, wandelt sich der zweite Zeiger in 3c in einen Zeiger zu 7d um, und der Block 7c wird zur Verwendung freigegeben.
• Diese bevorzugte Implementierung ist ein Drucker 9. Dies wird durch den Ausstoß einer Druckseite Papier 11 durch Vorschubwalzen 13a, 13b auf eine Ausgangsablage 15 zur Verwendung als fertige Seite Text oder Grafik oder von beidem angedeutet. Zurückgeführter Speicher wird typischerweise durch die Seitenvorbereitungssoftware explizit gekennzeichnet. Folglich wird der Datenprozessor 5 typischerweise explizit informiert, dass ein bestimmter Speicherblock von einer bestimmten Größe an einer bestimmten Adresse nicht länger benötigt wird. Dies setzt eine Rückführung eines solchen Speichers zur Wiederverwendung fest.
• Andere Techniken, Speicher zurückzuführen, sind bekannt, wie z. B. Zählen der Aufrufe eines Speicherblocks und Einwirken auf den Block als einem zurückgeführten Block, wenn die Zählung Null erreicht. Faktisch ist jegliches Verfahren zum Kennzeichnen oder Anordnen von zurückgeführtem Speicher konsistent mit dieser Erfindung und bildet keinen Teil dieser Erfindung, da sich diese Erfindung auf das anschließende Anordnen solchen zurückgeführten Speichers mit hoher Geschwindigkeit und Datenverarbeitungswirkungsgrad bezieht.
• Zurückgeführter Speicher ist typischerweise mit einer Anfangs- und Endadresse gegeben. In dieser Ausführungsform ist, wie es üblich ist, die Größe explizit im Dateianfangsetikett des Speicherblocks als Binärzahl enthalten (das Dateianfangsetikett ist ein Teil der Speicherblöcke, das für zugehörige Daten reserviert ist). Diese Größenzahl wird dann in Richtung einer Teilung durch zwei verschoben, bis keine Zahlzeichnen mehr da sind. Die Anzahl von Verschiebungen kennzeichnet die untere Größe dieses Speicherblocks, und er kann nicht größer sein als zweimal diese Größe, da in dem natürlichen Binärsystem, das verwendet wird, jede Säule einen Stellenwert von zweimal demjenigen der vorhergehenden Säule darstellt. (Ähnlich kann man in einem exponenziellen Nummerierungssystem bloß den Exponenten verwenden, und die Magazine würden sich mit der Größe der ganzzahligen Potenzen dieser Basis ändern.)
• Wenn beim Durchsuchen der sortierten Liste nach einem Magazin der erste Block 3 zu klein ist, dann sind die übrigbleibenden Blöcke in der sortierten Liste zu klein. Eine Routine setzt dann den Suchvorgang durch das nächst größte nicht leere Magazin fort, wie beschrieben. Wenn ein Block 3 erreicht wird, der zu klein ist, oder das Ende der sortierten Liste eines Magazins erreicht wird, dann wird ein System angewandt, um unter den zuvor angetroffenen Blöcken 3 auszuwählen. In der bevorzugten Ausführungsform wird der nächst größere Block, der zu demjenigen, der gesucht wird, größenmäßig der am nächsten kommende verwendbare Speicher ist, verwendet, wenn er ein paar Wörter in der Nähe von demjenigen liegt, der größenmäßig gesucht wird. Dies bewahrt größere Blöcke. Da im Allgemeinen ein Aufteilen von Blöcken, um einen Block bei derselben Größenordnung übrig zu lassen, Blöcke einer nützlichen Größe dann erzeugt, wenn der ausreichend große Block 3 größenmäßig nicht in der Nähe liegt, wird ein Block verwendet, von dem dazwischen gefunden wurde, dass er zweimal so groß ist. Der Suchvorgang wird in den höheren nicht leeren Magazinen fortgesetzt, um einen Block zu finden, der doppelt so groß ist wie die gesuchte Größe, von dem ein Teil verwendet wird. Der Restteil dieses Blocks wird als zurückgeführter Speicher behandelt und in einem Speicher eingeschlossen, der durch die Sortierliste für das Magazin für einen Speicher angeordnet wird, der die Größe dieses unbenutzten Teils umfasst. Die Suchpreferenz der Reihe nach lautet: genaue Größe, ein paar Wörter größer, doppelt so groß, größer als doppelt und dann der erste Block, der angetroffen wurde, der größer war. (Die Adresse dieses ersten Blocks wird gespeichert, wenn er gefunden wurde, und die Adresse eines doppelt so großen Blocks wird gespeichert, während nach einem genau so großen und ein paar Wörter größeren Block gesucht wird.)
• Die Sortierroutine wird bei jeder Rückführung eines Speicherblocks durchgeführt. Die Magazinliste wird einfach von einem Ende durchsucht, wobei die Größe jedes Blocks 3, der angetroffenen wird, mit der Größe des gerade zurückgeführten Speicherblocks verglichen wird. Wenn sich der Vergleich von kleiner zu größer ändert, wird der Zeiger im größeren Block 3 geändert, so dass er zum gerade zurückgeführten Speicher zeigt, und der gerade zurückgeführte Speicher weist einen zu ihm hinzugefügten Zeiger auf, der zum kleineren Speicherblock 3 zeigt. Auch werden, wie erwähnt, die Rückwärtszeiger und die gleichgroßen Zeiger angebracht, wie erörtert. Wenn die neue Speichergröße dieselbe ist wie ein vorhandener Block 3, wird sie nicht zur Sortierliste hinzugefügt, sondern auf sie wird durch den vorherigen letzten Speicher in der gleichgroßen Liste hingezeigt.
• Obwohl diese Erfindung voraussichtlich die Leistungsfähigkeit in den verschiedensten Computeranlageumgebungen erhöht, ist sie besonders gut geeignet, einige der schlimmsten Computersystem-Speicherverwaltungs-Szenarios handzuhaben: regellos bemessene Speicherblöcke: weit sich unterscheidende Speicherlebensdauern; und einen verhältnismäßig großen Hauptspeicher, der dazu neigt, "voll zu laufen". Dies sind alles Eigenschaften von anspruchsvollen Anwendungen, wie z. B. Laserdrucker und mehrprogrammfähige Speicherverwendung. Die Stärken dieser Erfindung sind ihr sehr großer Suchwirkungsgrad, ihr geringer Speicheroverhead, die inhärente Verfügbarkeit von Blockgrößenalternativen, wenn keine genaue Übereinstimmung vorhanden ist, und das umfassende Ordnen von freien Speicherblöcken. Weiter ist diese Erfindung auf einen weiten Bereich von elektronischem Speicher anwendbar, einschließlich Magnetplattenspeicher.
• Um für Suchwirkungsgrad zu sorgen, wird die Anzahl von zu durchsuchenden Elementen verringert. Durch Gruppieren der Blöcke nach Größe wird der Suchvorgang durch die unmittelbare Beseitigung von allen Gruppen reduziert, die ungefähr eine Größenordnung kleiner und größer sind als die vom Datenprozessor 5 gesuchte Blockgröße (abgesehen von sehr kleinen und sehr großen Blöcken, die breiter gruppiert werden). Ein einfaches lineares Größengruppieren wird nicht bevorzugt, da für tatsächliche Anwendungen regellos bemessene Blockverteilungen die allgemeine Charakteristik der negativen Exponentialfunktion Konstante E minus x aufweisen, wobei x die Speichergröße ist. Aus diesem Grund werden die Blöcke dazu neigen, in dasselbe Magazin oder ein paar Magazine kategorisiert zu werden. Im Gegensatz dazu weist die exponenzielle Definition der Magazine der bevorzugten Ausführungsform die Ergebnisse eines "Flachmachens" der Blockverteilung über den Magazinbereich auf. Fig. 2 zeigt die durch Drucken einer Datei für einen PostScript(Schutzmarke)-Interpretierer erzeugten durchschnittlichen Listenlängen, die einige tausend Speicherzuweisungen erforderten, wobei die Zwischenmagazine als Potenzen von 2 exponenziell definiert sind, wie im Vorhergehenden als bevorzugte Ausführungsform beschrieben. Eine etwas abgeflachte Streuung der Inhalte der Magazine ist augenscheinlich. Da die großen Magazine Blöcke von großem Speicher enthalten und der Systemspeicher größenmäßig endlich ist, können sie keine große Anzahl von Blöcken 3 in ihrer Sortierliste aufweisen, da eine solche große Speicherkapazität einfach nicht zur Verfügung steht. Und die kleinen Magazine können nicht mehr Blöcke enthalten als ihr gesamter Bereich, der intrinsisch begrenzt ist.
• In einer Testanwendung für einen Drucker war der Großteil der Anforderungen für Speicherblöcke größenmäßig nicht größer als 512 Bytes, und 97,8% der angeforderten Speicherblöcke waren für Magazine mit einer Worst-Case-Suchlänge von zwischen 16 und 128 Elementen in der Sortierung.
• Natürlich sind tatsächliche Suchlängen viel kleiner als diese Höchstwerte. Und da die Listen geordnet sind, tendiert die Anzahl von erforderlichen Suchschritten statistisch in Richtung auf die halbe durchschnittliche Länge der Liste, die durchsucht wird. Ein Testdatensatz für einen komplizierten Drucker erzeugte eine durchschnittliche Suchtiefe von 3,86 Blöcken 3 pro Suchvorgang über den gesamten Job.
• Für Anwendungen, die bestimmte Speichergrößen begünstigen, brauchen alternativ die Listen der Blöcke 3 nicht größenweise sortiert zu sein, und sie werden zu Beginn überhaupt nicht sortiert. Stattdessen werden sie in der Reihenfolge der Rückführung gelistet, wie es für das Zugreifen auf Speicher vor dieser Erfindung bekannt ist. Jedesmal wenn nach einem Speicherblock von bestimmter Größe gesucht wird und er verwendet wird, werden folglich jegliche Blöcke, die doppelt so groß sind wie diejenigen, die verwendet werden, zur Front der Suchliste bewegt. Neu zurückgeführte Blöcke zusammen mit ihren Duplikaten, wenn irgendwelche vorhanden sind, werden vorne an der Suchliste eingefügt. Wenn Suchvorgänge durchgeführt werden, neigen Blöcke mit Größen, die häufiger verwendet werden, dazu, sich in die Nähe der Front der Liste zu bewegen.
• Als eine andere Alternative für großen Listen können Magazinadressen von Tabelle 1 eine zweite Tabelle adressieren, die größenweise in Intervalle unterteilt ist. Jedes Element dieser zweiten Tabelle würde die Adresse zu einer Liste von Blöcken 3 innerhalb der Größe dieses zweiten Tabellenelements aufweisen.
• Andere Abwandlungen können im Bereich dieser Erfindung im voraus erkannt werden, da sie nicht von der Art eines Adressierens von Speicher oder Feststellens des Vorhandenseins von freiem Speicher abgehängt und da weite Abwandlungen in der Art und Weise eines Listens und Sortierens von Speicherblöcken in den Listen zulässig sind. Ähnlich ist die exponentielle (d. h. logarithmische zur Basis 2, in der bevorzugten Ausführungsform) Verteilung von Magazinengrößen ein Vorteil aber nicht wesentlich, um andere Vorteile, wie von dieser Erfindung beschrieben, zu realisieren.

Claims (3)

1. Vorrichtung (9), umfassend:

eine elektronische Datenverarbeitungsvorrichtung (5);

wiederverwendbaren elektronischen Speicher (3, 7), der durch Adresscodes adressierbar ist;

eine Einrichtung zum Bereitstellen einer Liste von verschiedenen Zeigeradressen (1a-1n), wobei jede Adresse Speicherbereiche in einem bestimmten ersten vorbestimmten Größenbereich erreicht; und

eine Einrichtung (5) zum Feststellen, in welchem ersten vorbestimmten Größenbereich ein bestimmter Bereich von zurückgeführtem Speicher liegt;

eine Einrichtung zum Bereitstellen von ersten Adresszeigern, die Bereichen von zurückgeführtem Speicher in jedem ersten vorbestimmten Größenbereich zugeordnet sind, dadurch gekennzeichnet, dass jeder erste Adresszeiger einen Bereich von zurückgeführtem Speicher (3a-3i) von unterschiedlicher Größe in dem ersten vorbestimmten Größenbereich anzeigt; und dadurch, dass die Vorrichtung weiter umfasst:

eine Einrichtung zum Bereitstellen von zweiten Adresszeigern, die Bereichen von zurückgeführtem Speicher zugeordnet sind, wobei jeder zweite Adresszeiger Bereiche von zurückgeführtem Speicher (7a-7j) von derselben Größe oder in einem zweiten vorbestimmten Größenbereich anzeigt, der kleiner ist als ein bestimmter erster vorbestimmter Größenbereich und in ihm enthalten ist;

eine Einrichtung (5) zum Vergleichen der Größe des Bereichs von zurückgeführtem Speicher mit zuvor zurückgeführten Speicherbereichen, um in dem zweiten vorbestimmten Bereich einen Größenunterschied festzustellen; und

eine Einrichtung (5) zum Festsetzen von ersten und zweiten Adresszeigern, die den zurückgeführten Speicherbereichen zugeordnet sind, in den jeweiligen vorbestimmten Größenbereichen, entsprechend dem Vergleich.

2. Vorrichtung nach Anspruch 1, bei der sich die untere Grenze von jedem ersten vorbestimmten Größenbereich um einen Faktor zwei von denjenigen der benachbarten Bereiche unterscheidet.

3. Vorrichtung nach Anspruch 1 oder 2, bei der die Vorrichtung einen durch die Datenverarbeitungsvorrichtung (5) gesteuerten Drucker (9) umfasst.