DE69427174T2

DE69427174T2 - Dynamische Hochleistungsprogrammverknüpfung durch Cachespeicherung

Info

Publication number: DE69427174T2
Application number: DE69427174T
Authority: DE
Inventors: Graham Hamilton; Michael N. Nelson
Original assignee: Sun Microsystems Inc
Current assignee: Sun Microsystems Inc
Priority date: 1993-04-13
Filing date: 1994-03-14
Publication date: 2002-01-03
Anticipated expiration: 2014-03-15
Also published as: DE69427174D1; EP0620522A3; US5475840A; EP0620522B1; EP0620522A2; JPH07160483A

Description

HINTERGRUND DER ERFINDUNG

Gebiet der Erfindung

Die vorliegende Erfindung bezieht sich auf die Gebiete der verteilten Rechnersysteme, der Client-Server-Datenverarbeitung und der objekt-orientierten Programmierung.

HINTERGRUND

Ein Computerprogrammierer schreibt ein Programm, das Quellprogramm, in einer problemorientierten Sprache oder Sprache höheren Niveaus, welche üblicherweise Symbole für Adressen und spezielle Zeichen oder Akronyme für Operationscodes verwendet. Dieser Quellcode umfaßt einen Befehlssatz für den Computer und Daten, mit welchen oder an welchen die Befehle operieren sollen. Diese Befehle und Daten müssen in einen Speicher eines Computers an bestimmten Adressen geladen werden, damit der Computer den Programmprozeß ausführen kann. Damit dies geschehen kann, wird der Quellcode von einem Compiler verarbeitet, welcher binären Objektcode erzeugt, den ein Computer ausführen kann. Bevor der Computer dieses neu geschriebene Programm ausführen kann, muß das Programm durch verschiedene zusätzliche Schritte laufen, während welcher die Adressen in dem Programm auf verschiedene Weise dargestellt werden können. Der Compiler verbindet typischerweise die symbolischen Adressen des Quellcodes mit verschieblichen Adressen (wie beispielsweise 16 Bytes nach der Anfangsadresse des Programmes). Ein Verknüpfungseditor oder Lader verbindet wiederum diese verschieblichen Adressen mit absoluten Adressen (wie beispielsweise dem Speicherplatz 64216). Jede Verbindung oder Verknüpfung ist eine Abbildung aus einem Adreßraum in einen anderen. Diese Verbindung (binding) der Befehle und Daten mit Speicheradressen kann entweder zur Kompilationszeit, zur Ladezeit oder zur Programmausführungszeit ausgeführt werden.
Es wird auf Fig. 1 Bezug genommen, in der die verschiedenen oben beschriebenen Schritte veranschaulicht sind. Das Quellprogramm 1 wird von einem Compiler 2 verarbeitet, der ein Objektcodemodul 3 erzeugt. Dieses Objektcodemodul 3 wird, grundsätzlich zusammen mit weiteren zuvor kompilierten Objektmodulen 4, durch einen Verknüpfungseditor 5 verarbeitet, um ein Lademodul 6 zu erzeugen. Das Lademodul 6 und irgendwelche erforderlichen Systembibliotheken 7 werden von einem Lader 8 verarbeitet, der ein im Speicher befindliches binäres Abbild 10 des ursprünglichen Programms und seiner zugehörigen Module und Bibliotheken erzeugt. Dieses binäre Im-Speicher-Abbild 10 kann jetzt von dem Computer ausgeführt werden.
Es wird weiter auf Fig. 1 Bezug genommen; wenn es zur Kompilierzeit 12 bekannt ist, wo das Programm sich im Speicher aufhalten wird, werden diese Programme mit einem absoluten Code für die Adressen kompiliert. In den meisten Fällen ist es jedoch zur Kompilierzeit nicht bekannt, wo sich das Programm im Speicher aufhalten wird, und der Compiler muß einen verschieblichen Code für die Speicheradressen erzeugen. In diesem Fall werden die endgültigen Bindungen oder Verknüpfungen der Speicherplätze mit den Adressen entweder bis zur Ladezeit 13 oder bis zur Ausführungszeit 14 verzögert. Einige moderne Systeme verzögern diese Adreßverknüpfung bis zur Ausführungszeit 14, wenn das Programmabbild während seiner Ausführung aus einem Speichersegment zu einem anderen bewegt werden kann oder wenn die Programmstartkosten nicht sehr hoch sind, weil die Programmabbilder wenige verschiebliche Adressen enthalten, wie beispielsweise bei positionsunabhängigen Code (PIC; Position Independent Code). PIC ist ein von einigen Compilern erzeugter Code, welcher irgendwo im Speicher angeordnet werden kann, da sämtliche Speicherbezugnahmen relativ zu dem Befehlszähler gemacht werden.
Moderne Computerbetriebssysteme sind so ausgebildet, daß sie die Verwendung des Speicherraums optimieren und die Benutzerwartezeit minimieren. Bei dem Adreßverknüpfungs/Programmladeprozeß wird dies durch ein dynamisches Laden der Programmobjektmodule nur dann, wenn sie tatsächlich von einem anderen Modul aufgerufen werden, und durch dynamisches Verknüpfen eines Objektmoduls mit seinen Systembibliotheksroutinen nur dann, wenn sie erforderlich sind, ausgeführt. Bei diesen Fällen wird das Hauptprogramm in den Speicher geladen und ausgeführt, und unterstützende Objektmodule oder Systembibliotheken werden nicht geladen, bis sie von dem Hauptprogramm aufgerufen werden, wodurch Speicherraum und Ladezeit auf Kosten einer Programmstartzeit eingespart werden. Auch Systembibliotheken, welche sich voraussichtlich bereits im Speicher aufhalten, können dynamisch mit dem ausführenden Hauptprogramm verknüpft werden, wenn sie aufgerufen werden, wodurch es nicht erforderlich ist, daß eine Kopie der Systembibliotheken mit jedem Hauptprogramm zur Ladezeit verknüpft und geladen wird, was wiederum Speicherraum spart, allerdings auf Kosten einiger Programmstartzeit und einiger Ausführungszeit. Beim dynamischen Verknüpfen ist ein Stumpf (stub) in dem Abbild für jede Bibliotheksroutinenreferenz enthalten. Dieser Stumpf ist ein kleiner Teil des Codes, der anzeigt, wie die richtige speicherresidente Bibliotheksroutine lokalisiert werden soll. Wenn der Stumpf ausgeführt wird, ersetzt er sich selbst durch die Adresse der Routine und führt die Routine aus. Bei diesem Schema verwenden sämtliche Programme, die eine Bibliotheksroutine benutzen, die gleiche Kopie des Bibliothekscodes.
Um einen maximalen Vorteil aus der dynamischen Verknüpfung und dem dynamischen Laden zu ziehen, müssen Programmcompiler so ausgebildet sein, daß sie die erforderlichen verschieblichen Adreßreferenzen, den Subroutinenstumpfcode und effizienten PIC-Code erzeugen. Unglücklicherweise können vorhandene Compiler für objekt orientierte Programmmodule einen solchen Code nicht effizient erzeugen. Beispielsweise erzeugen der cfront 3.0-preprocessor und der G++-Compiler virtuelle Funktionstabellen als initialisierte Datenstrukturen, welche voll von Bezugnahmen (Referenzen) auf verschiebliche Symbole sind. So ist die Anzahl der verschieblichen Symbole bei objekt-orientierten Programmmodulen viel höher als bei herkömmlicheren Programmmodulen, und die zum dynamischen Verknüpfen dieser Module erforderliche Programmstartverzögerung kann auf ein nicht akzeptables Niveau infolge der Anzahl der Verschiebungen ansteigen. Folglich ist ein System erforderlich, das eine effiziente dynamische Verknüpfung von Programmmodulen bei einer großen Anzahl verschieblicher Symbole zur Verfügung stellt.
Außerdem offenbart das IBM Journal of Research and Development, Band 34, No. 1, 1. Januar 1990, Seiten 98-103, eine mögliche Programmbibliothek in einem Artikel mit dem Titel "Managing Programs and Library's in AIX Version 3 for RISC System/6000 Processors" von M. A. Auslander.
Die vorliegende Erfindung, wie sie in den anhängigen Ansprüchen definiert ist, schafft eine elegante Lösung für dieses Problem, indem verknüpfte Programmabbilder und darüber hinaus partiell verknüpfte Bibliotheksprogramme cachegespeichert werden.

ZUSAMMENFASSENDE DARSTELLUNG DER ERFINDUNG

Die vorliegende Erfindung füllt dieses Erfordernis einer Minimierung der von der Verknüpfung neuer objektorientierter Programme verursachten Systemverzögerung aus, indem sie ein elegantes und effizientes System der Cache-Speicherung vollständig verbundener Programmabbilder zusammen mit ihren Systembibliotheksmodulen einrichtet und indem sie eine zweite Ebene von Caches zum Cache-Speichern verschieblicher Systembibliotheksprogramme, deren Adressen provisorisch fixiert (zum Teil verknüpft) werden, einrichtet und indem sie diese Cache-Speicher verwendet, um vollständig verknüpfte oder partiell verknüpfte Module zu liefern, wenn ein Aufruf zu einem anderen Programm/einer anderen Routine gemacht wird. Somit überprüft das System, wenn eine neue Anwendung verknüpft werden soll, zunächst den Abbild-Cache um nachzusehen, ob das Programm vorher verknüpft worden ist, und, sofern dies der Fall ist, wird die verknüpfte Version des Programms zusammen mit seinen verknüpften Bibliotheksprogrammen ohne zusätzlichen Verarbeitungsmehraufwand verwendet. Sofern die neue Anwendung nicht in dem Abbild-Cache aufgefunden wird, so wird dann ein Versuch unternommen, den Mehraufwand zu minimieren, indem nachgesehen wird, ob einige oder sämtliche der zugehörigen Bibliotheksprogramme bereits provisorisch fixiert (teilweise verknüpft) worden sind, indem ein Bibliotheksprogramm-Cache überprüft wird. Nur dann, wenn ein Bibliotheksprogramm nicht in dem Bibliotheksprogramm-Cache aufgefunden wird, braucht das Verknüpfersystem eine vollständige Programmlade- und -verknüpfungsoperation auszuführen, womit der Verknüpfungsmehraufwand minimiert wird.
Es wird ein Verfahren offenbart für ein Verfahren zum dynamischen Verknüpfen eines neuen Programmabbilds und zugehöriger Bibliotheksprogramme zu einem ausführbaren Anwenderprogrammabbild. Das Verfahren sorgt für die Erzeugung einer verknüpften Liste der erforderlichen Programme, indem dem Verknüpfer ein Argument gegeben wird, daß das ausersehene Programmabbild repräsentiert und einen Benennungskontext, welcher Daten über die zugeordneten Bibliotheksprogramme, welche miteinander verknüpft werden sollen, enthält. Der Verknüpfer findet sämtliche erforderlichen Programme und verknüpft sie miteinander. Das Elternteil bildet die Programmabbilder in die vorgesehenen Adressen ab, wodurch die Verknüpfung des ausführbaren Anwendungsprogramms abgeschlossen wird. Beim Auffinden der erforderlichen Programme überprüft der Verknüpfer zunächst den Abbild-Cache, um nachzusehen, ob das neue Programm und seine zugehörigen Bibliotheksprogramme bereits verknüpft und cache-gespeichert sind, weil sie vorher ausgeführt worden sind. Wenn das neue Programm nicht in dem Abbild-Cache aufgefunden wird, überprüft dann das Verknüpfer-Objekt den Bibliotheksprogramm-Cache, um nachzusehen, ob die Bibliotheksprogramme in partiell verknüpfter Form cache-gespeichert sind, und verwendet von ihnen soviele, wie es auffinden kann. Bei irgendwelchen Bibliotheksprogrammen, die noch lokalisiert werden müssen, liest der Verknüpfer sie aus einem Datenspeicher und fährt dann damit fort, sämtliche Bibliotheksprogramme und das neue Programmabbild miteinander zu verknüpfen, um ein ausführbares Ganzes zu bilden. Dieser Prozeß des Cache-Speicherns neuer Programmabbilder mit ihren Bibliotheksprogrammen und des Cache-Speicherns partiell verknüpfter Bibliotheksprogramme garantiert individuell eine Prozedur, welche die Zeitverzögerung beim Programmstart minimiert, wenn ein neues Programm ausgeführt wird.

BESCHREIBUNG DER ZEICHNUNGEN

Die Aufgaben, Merkmale und Vorteile des erfindungsgemäßen Systems werden aus der folgenden Beschreibung deutlich, in Welcher:
Fig. 1 die typischen Schritte beim Kompilieren und Laden eines neuen Programms veranschaulicht (Stand der Technik).
Fig. 2 das SPRING-Betriebssystemkonzept eines Objekts veranschaulicht.
Fig. 3 ein Ablaufdiagramm der Erfindung auf einer höheren Ebene veranschaulicht.
Fig. 4 ein detailliertes Ablaufdiagramm der Erfindung veranschaulicht.
Fig. 5 ein nicht fixiertes Programm veranschaulicht.
Fig. 6 eine fixierte Version des in Fig. 5 veranschaulichten Programms veranschaulicht.
Fig. 7 ein Beispiel einer dynamischen SPRING-Verknüpfungsumgebung veranschaulicht

BEZEICHNUNGEN UND TERMINOLOGIE

Die folgenden detaillierten Beschreibungen können anhand von Programmprozeduren, die auf einem Computer oder einem Netzwerk von Computern ausgeführt werden, präsentiert werden. Diese prozeduralen Beschreibungen und Darstellungen sind diejenigen Mittel, die von Fachleuten verwendet werden, um das Wesen ihrer Arbeit anderen Fachleuten auf effektivste Weise zu übermitteln.
Unter einer Prozedur wird hier und im allgemeinen eine in sich konsistente Sequenz von Schritten verstanden, die zu einem gewünschten Ergebnis führt. Diese Schritte sind solche, die physikalische Bearbeitungen physikalischer Größen erfordern. Üblicherweise, jedoch nicht notwendigerweise, nehmen diese Größen die Form elektrischer oder magnetischer Signale an, die gespeichert, übertragen, kombiniert, verglichen und auf andere Weise manipuliert werden können. Gelegentlich hat es sich, hauptsächlich aus Gründen der allgemeinen Verwendung, als geeignet erwiesen, auf diese Signale als Bits, Werte, Elemente, Symbole, Zeichen, Terme, Zahlen oder dergleichen Bezug zu nehmen. Es sei jedoch angemerkt, daß all diese und ähnliche Bezeichnungen den richtigen physikalischen Größen zugeordnet sein sollen und bloß auf diese Größen angewendete geeignete Etiketten sind.
Darüber hinaus werden die ausgeführten Bearbeitungen oftmals mit Begriffen, wie beispielsweise Addieren und Vergleichen, bezeichnet, welche üblicherweise den von einem menschlichen Bediener ausgeführten geistigen Operationen zugeordnet werden. Keine derartige Fähigkeit eines menschlichen Bedieners ist bei irgendeiner der hier beschriebenen Operationen, welche Teil der vorliegenden Erfindung bilden, erforderlich und sie ist in den meisten Fällen auch nicht erwünscht; die Operationen sind Maschinenoperationen. Nützliche Maschinen zum Durchführen der Operationen gemäß der vorliegenden Erfindung umfassen digitale Mehrzweckcomputer oder ähnliche Geräte.
Die vorliegende Erfindung bezieht sich darüber hinaus auf eine Einrichtung zum Durchführen dieser Operationen. Diese Einrichtung kann für die erforderlichen Zwecke speziell konstruiert sein oder kann einen Mehrzweckcomputer umfassen, der selektiv von einem in dem Computer gespeicherten Computerprogramm aktiviert oder umkonfiguriert worden ist. Die hier angegebenen Prozeduren beziehen sich nicht zwangsläufig auf einen speziellen Computer oder eine andere spezielle Einrichtung. Verschiedene Mehrzweckmaschinen können mit gemäß den hier gegebenen Lehren geschriebenen Programmen verwendet werden oder es kann sich als geeigneter herausstellen, spezialisiertere Einrichtungen zu konstruieren, um die erforderlichen Verfahrensschritte auszuführen. Die erforderliche Struktur für eine Vielzahl dieser Maschinen wird aus der angegebenen Beschreibung deutlich.

BESCHREIBUNG DES BEVORZUGTEN AUSFÜHRUNGSBEISPIELS

In der folgenden Beschreibung werden aus Gründen der Erläuterung spezielle Daten und Konfigurationen angegeben, um ein besseres Verständnis der vorliegenden Erfindung zu erreichen. Das hier beschriebene bevorzugte Ausführungsbeispiel wird als Teil des von Sun Microsystems®, Inc. (Sun Microsystems ist eine eingetragene Marke der Sun Microsystems, Inc.) geschaffenen objekt-orientierten SPRING- Betriebssystems implementiert. Für einen Fachmann ist es jedoch klar, daß die vorliegende Erfindung auch ohne die speziellen Details ausgeführt werden kann und in verschiedenen Computersystemen und bei verschiedenen Konfigurationen oder Typen oder Modellen eng gekoppelter Prozessoren oder bei verschiedenen Konfigurationen lose gekoppelter Mehr-Prozessor-Systeme implementiert werden. Darüber hinaus ist es Fachleuten klar, daß die vorliegende Erfindung in einem nicht-objekt-orientierten Rechnersystem implementiert sein kann.
Eine SPRING-Domäne ist ein Adreßraum mit einer Sammlung von Threads. Eine gegebene Domäne kann als Server einiger Objekte und als Client anderer Objekte dienen. Der Implementierer oder Objektmanager und der Client können in derselben Domäne oder in verschiedenen Domänen sein.

Das Spring-Objektmodell

SPRING weist gegenüber anderen verteilten objektorientierten Systemen eine geringfügig abweichende Art der Betrachtung von Objekten auf, und es ist erforderlich, dies klarzustellen, bevor die Details der vorliegenden Erfindung erörtert werden.
Die meisten verteilten Systeme präsentieren ein Modell, bei dem sich die Objekte bei Server-Maschinen aufhalten und bei dem Client-Maschinen Objekt-Handles (Zugriffsmöglichkeiten) besitzen, die auf das Objekt beim Server verweisen (siehe Fig. 2a). Clients befassen sich (pass around) mit Objekt-Handles anstelle von Objekten.
SPRING präsentiert ein Modell, bei dem Clients direkt an Objekten und nicht an Objekt-Handles arbeiten (siehe Fig. 2b). Bei einigen dieser Objekte kann es passieren, daß ihre sämtlichen interessierenden Zustände an irgendeiner fernen Stelle gehalten werden, so daß ihr lokaler Zustand bloß aus einem Handle auf diesen fernen Zustand besteht. Ein Objekt kann nur jeweils an einem Ort existieren, so daß dann, wenn ein Objekt irgendwohin gesendet wird, der Sender des Objekts das Objekt nicht mehr besitzt. Jedoch kann das Objekt kopiert werden, bevor es gesendet wird, was so implementiert werden könnte, daß es jetzt zwei verschiedene Objekte gibt, die auf denselben fernen Zustand zeigen.
Während man somit bei Systemen, wie beispielsweise MACH, davon sprechen könnte, daß verschiedene Clients Objekt-Handles aufweisen, die auf irgendein fernes Objekt verweisen, würde man bei SPRING davon sprechen, daß verschiedene Clients Objekte aufweisen, die auf denselben fernen Zustand verweisen.

Dynamische Verknüpfung von Prozeßabbildern bei SPRING

Es wird jetzt auf Fig. 3 Bezug genommen, in der die Grundschritte der vorliegenden Erfindung kurz beschrieben sind. Wenn eine Client-Domäne in SPRING es wünscht, ein Programm zu starten, führt die Client-Domäne ein "Link(ImageMemoryObject, NamingContextObject)"-Kommando 20 an einem Verknüpferobjekt aus. Das Verknüpferobjekt überprüft zunächst seinen Abbild-Cache 22, indem es das Abbildspeicherobjekt nachschlägt, um nachzusehen, ob es eine vollständig verknüpfte Version des durch das Abbildspeicherobjekt repräsentierten Programms enthält und ob diese cachegespeicherte Version unter Verwendung der Bibliotheksprogramme in dem Benennungskontextobjekt verknüpft wurde. Wenn eine Übereinstimmung gefunden wird, 28, ist das Verknüpferobjekt im Grunde genommen mit seiner Arbeit am Ende und gibt bloß die cache-gespeicherte Liste der Speicherobjekte und zugehörigen Adressen aus, 38, welche dem gefundenen Abbildspeicherobjekt zugeordnet sind. Sofern die Überprüfung des Abbild-Cache keine Übereinstimmung erzeugt, 24, so findet dann das Verknüpferobjekt eine Liste von Namen von Bibliotheksprogrammen, die für das Abbildspeicherobjekt erforderlich sind, und gewinnt unter Verwendung des Benennungskontextobjekts für jedes Bibliotheksprogramm ein ihm zugeordnetes Speicherobjekt und fährt damit fort, den Bibliotheksprogramm-Cache hinsichtlich einer Übereinstimmung für jedes Bibliotheksprogramm zu überprüfen, 26. Wenn eine Übereinstimmung für ein Bibliotheksprogrammspeicherobjekt gefunden wird, 36, gewinnt das Verknüpferobjekt das Speicherobjekt, das die provisorisch fixierte Kopie des gefundenen Bibliotheksprogramms repräsentiert und die zugeordnete Adresse, bei welcher dieses Programm abgebildet werden soll. Sofern keine Übereinstimmung gefunden wird, 30, entscheidet das Verknüpferobjekt über eine Adresse, bei welcher das fragliche Bibliotheksprogramm abgebildet werden soll, erzeugt ein Speicherobjekt, das eine Kopiere-beim-Schreiben-Kopie des fraglichen Bibliotheksprogramms ist, und bildet dieses Speicherobjekt bei der Adresse ab, die es für es ausgewählt hat. Das Verknüpferobjekt fixiert ferner provisorisch diese neue Kopie des Programms und speichert das Speicherobjekt des Bibliotheksprogramms und die zugehörige Adresse in dem Bibliotheksprogramm-Cache, 32. Nach dem Auffinden eines Speicherobjekts für jedes erforderliche Bibliotheksprogramm, ob es nun in dem Bibliotheksprogramm-Cache gefunden wurde oder neue Kopien erzeugt wurden, löst das Verknüpferobjekt jetzt sämtliche nicht aufgelösten Symbolreferenzen in dem neuen Programmabbild und in sämtlichen dieser Bibliotheksprogramme auf und schreibt eine Kopie dieser vollständig verknüpften Version in den Abbild-Cache, 34. Schließlich gibt das Verknüpferobjekt an die Client-Domäne eine Liste der Speicherobjekte und zugehörigen Adressen für dieses vollständig verknüpfte neue Programmabbild und seine zugeordneten Bibliotheksprogramme zurück.
Die obige Beschreibung ist eine zusammengefaßte Beschreibung der vorliegenden Erfindung, welche unten detaillierter in dem in Fig. 4 gezeigten Ablaufdiagramm erläutert und bei Beispielen des Prozesses beschrieben wird. Fachleute erkennen, daß die Verwendung von Namen, wie beispielsweise Verknüpferobjekt, Client-Domäne, etc., zu Zwecken der Veranschaulichung dient und daß die Erfindung durch Programme ausgeführt werden kann, welche eine beliebige Namensart haben können.
Bevor damit fortgefahren wird, die Erfindung detaillierter zu erläutern, ist es nützlich, ein Beispiel eines "nicht fixierten Programms" zu beschreiben und zu beschreiben, was geschieht, wenn die Verschiebungen auftreten, um es zu einem "fixierten" oder ausführbaren Programmabbild zu machen. Es wird jetzt auf Fig. 5 Bezug genommen, in der ein nicht fixiertes Programm gezeigt ist. Die Datei "F" 40 enthält ein Programmabbild. Diese Datei hat vier Teile: einen Kopfteil (Header) 42, der die Adresse 44 zum Beginnen der Ausführung des Programms und die Liste der zu verwendenden geteilten Bibliotheksprogramme 46 enthält; den Code für das Programm 52; eine Symboltabelle 48, die sämtliche externen Symbole, die in dem Programm definiert sind, enthält; und eine Verschiebungstabelle 50, die eine Liste der zu verschiebenden Symbole enthält. Bei diesem Beispiel besagt der Programmkopfteil 42, daß das Programm die gemeinsame oder geteilte Bibliothek SL benötigt, 46. Die Verschiebungstabelle 50 zeigt, daß der Programmcode 52 einen Befehl an der Adresse A1 enthält, der auf ein externes Symbol foo 54 Bezug nimmt. Zusätzlich zeigt die Symboltabelle 48, daß das Programm die externe Funktion bar 56 an der Adresse A2 definiert. Außerdem ist in Fig. 5 die Datei F2 gezeigt, die die geteilte Bibliothek SL 60 enthält. Die Datei F2 weist die gleichen vier Teile wie die Datei F auf: einen Programmkopfteil 62, den Code für das Bibliotheksprogramm 72; eine Symboltabelle 68; und eine Verschiebungstabelle 70. Da diese geteilte Bibliothek nicht von irgendwelchen weiteren geteilten Bibliotheken abhängig ist, ist die Liste der geteilten Bibliotheken leer, 66. Die Verschiebungstabelle 70 zeigt, daß der Bibliothekscode einen Befehl an der Adresse B1 enthält, der auf das externe Symbol bar 64 Bezug nimmt. Zusätzlich zeigt die Symboltabelle 68, daß der Bibliothekscode die externe Funktion foo an der Adresse B2 definiert, 76. Fig. 6 zeigt eine "fixierte" Version desselben Programms und desselben Bibliotheksprogramms, die in Fig. 5 gezeigt sind.
Fig. 6 zeigt einen Adreßraum 80, der den fixierten Programmcode 82 und den fixierten Bibliothekscode 84 enthält. Der Code für das Programmabbild in Datei F (52 in Fig. 5) wird an der Adresse 86 abgebildet, die für sämtliche Programmabbilder fest ist. Der Wert dieser Adresse ist so gewählt, daß jede Codeadresse in dem Abbild (52 in Fig. 5) korrekt ist (beispielsweise der Code an Adresse A1 (58 in Fig. 5) wird an Adresse A1 im Adreßraum 86 abgebildet. Die geteilte Bibliothek FL auf der anderen Seite wird beginnend an der Adreßraumspeicherplatzadresse R1 abgebildet, und somit ist jede Bibliothekscodeadresse um R1 in dem Adreßraum 80 versetzt, 90. Die externe Referenz zu dem Symbol foo in dem Befehl A1, welche als an dem Befehl A1 befindlich in der Verschiebungstabelle der Datei F (54 in Fig. 5) gezeigt wurde, wird durch die geteilte Bibliothek befriedigt. Das Symbol foo wurde an der Adresse B2 in der geteilten Bibliothek (76 in Fig. 5) definiert, und, da die Adresse B2 auf die Adresse R1 + B2 im Adreßraum 80 abgebildet wurde, war die für foo in A1 gegebene aktuelle Adresse R1 + B2 88. Die externe Referenz auf das Symbol bar in dem Befehl B1, die von der Bibliotheksverschiebungstabelle (64 in Fig. 5) gezeigt wird, wurde durch den Programmcode erfüllt, welcher bar an der Adresse A2 in dem Programmabbild (56 in Fig. 5) definierte. Der Befehl an der Adresse B1 in der geteilten Bibliothek wird tatsächlich auf die Adresse R1 + B1 in dem Adreßraum 90 abgebildet, und somit ist die in dem Befehl bei R1 + B1 plazierte aktuelle Adresse gleich A2, 92.
Es wird jetzt auf Fig. 7 Bezug genommen, in der eine Umgebung bei einem beispielhaften objekt-orientierten SPRING-System gezeigt wird, mit welcher das bevorzugte Ausführungsbeispiel der Erfindung veranschaulicht werden soll. Gezeigt sind: ein Benennungsdienst 100, der einen Implementierer für das Kontextobjekt C 102 enthält; eine Domäne C 104, die einen Adreßraum 106 enthält; eine Client-Domäne 108, die eine Abbildungsliste 120 und Objekte C 109, L 110, M 112, AS 114, D 116 und DM 118 enthält; ein SPRING-Kernel 122, das einen Domänenmanager 124 enthält, welcher selbst einen Implementierer des Domänenobjekts D 126 enthält, welches als das Objekt AS 128 enthaltend gezeigt ist; einen virtuellen Speichermanager 130, der ebenfalls in dem SPRING- Kernel enthalten ist, welcher einen Adreßraumimplementierer für Objekte AS 132 enthält; eine Datei-Server-Domäne 152, die Implementierer für ein Speicherobjekt M 154, Speicherobjekt M 256, Speicherobjekt SL 158, Speicherobjekt SL 260 und Speicherobjekt SL 362 enthält; und schließlich eine Verknüpfer-Domäne 140, die einen Implementierer für das Verknüpferobjekt L 142, einen einen Beispiel-Cache-Eintrag 146 enthaltenden Abbild-Cache 144, welcher selbst eine Liste von Speicherobjekten und zugehörigen Adressen 172 und die Speicherobjekte C 164, M 166, M2 168 und SL3 170 enthält, und einen einen Beispiel-Cache-Eintrag 150 enthaltenden Bibliotheks- Cache 148, welcher selbst Speicherobjekte SL 172 und 5L2 174 und die cache-gespeicherte Programmstartadresse 176 enthält, enthält.
Es sei angemerkt, daß die folgenden Objekte äquivalent sind: M 112 und M 166; M2 175 und M2 168; 5L3 177 und 5L3 170; und C 109 und C 164. Für die Zwecke dieser Erfindung werden zwei Objekte als äquivalent angesehen, wenn sie auf den Quellzustand auf dem Server Bezug nehmen.
Bei den folgenden Beispielen wünscht eine Client-Domäne ein Programm mit dem Namen foo zu starten. Die Konfiguration, nachdem das Programm gestartet ist, ist in Fig. 7 gezeigt.
Das einfachste Beispiel besteht darin, daß es einen Cache-Treffer in dem Abbild-Cache gibt. In diesem Fall durchläuft das Starten der neuen Domäne die folgenden Schritte:
Die Client-Domäne schlägt foo über den SPRING-Benennungsdienst 100 nach und erhält ein Speicherobjekt M 112 zurück, daß das Programmabbild für foo speichert. Das in M gespeicherte Programmabbild benötigt die geteilte Bibliothek SL, um dynamisch verknüpft zu sein; die Namen der Bibliotheken, zu denen ein Abbild verknüpft sein soll, sind in dem Speicherobjekt M 112 gespeichert, dessen Implementierung auf Platte 154 ist.
Die Client-Domäne 108 schlägt ein Verknüpferobjekt L 110 nach, das durch eine Verknüpferdomäne 140 unter Verwendung des Benennungsdienstes 100 implementiert wird.
Die Client-Domäne 108 ruft eine Verknüpfungsmethode auf L 110 auf, wobei sie zwei Parameter hineinleitet: das Speicherobjekt M 112 und ein Kontextobjekt C 109, implementiert durch den Benennungsdienst 100.
Die Verknüpferdomäne 140 sucht in ihrem Cache unter Verwendung von M 112 und 109 als ihre Schlüssel und entdeckt, daß sie einen Eintrag mit dem Schlüssel M 166 und C 164 hat, der übereinstimmt (M 166 ist äquivalent zu M 112 und C 164 ist äquivalent zu C 109). Der Cache-Eintrag enthält eine cache-gespeicherte Kopie einer vollständig verknüpften Version von M 166, die unter Verwendung von C 164 verknüpft wurde. Die vollständig verknüpfte Version besteht aus den zwei Speicherobjekten: M2 168 und 5L3 170. M2 168 ist eine vollständig verknüpfte Kopie von M 166, verknüpft an der Adresse A1 (die Adresse zum Abbilden der Programmabbilder ist für sämtliche Programme auf den Wert A1 fixiert) und SL3 170 ist eine vollständig verknüpfte Kopie des Speicherobjekts für die geteilte Bibliothek SL 172, verknüpft an der Adresse A2 (die Liste der Speicherobjekte und zugehörigen verknüpften Adressen ist bei 173 gezeigt).
Die Verknüpferdomäne 140 gibt eine Liste von < Adresse zum Abbilden, Speicherobjektpaare> 173 an die Client-Domäne 108 zurück (diese Liste wird Abbildungsliste 120 in der Client-Domäne 108 genannt). Der erste Eintrag in der Liste 121 enthält die Adresse A1 und das Speicherobjekt M2. Der zweite Eintrag in der Liste 123 enthält die Adresse A2 und das Speicherobjekt SL3.
Die Client-Domäne 108 schlägt ein Domänenmanagerobjekt DM 118 unter Verwendung des Benennungsdienstes 100 nach.
Die Client-Domäne 108 ruft die create domain-Methode auf dem Objekt DM 118 auf und erhält ein neues Domänenobjekt D 116 zurück.
Die Client-Domäne 108 ruft die getaddress space- Methode auf D 116 auf und erhält ein Objekt AS 114 zurück, daß den Adreßraum von D 132 repräsentiert.
Die Client-Domäne 108 ruft die copy and map-Methode auf dem AS-Objekt 114 auf, um das Objekt M2 175 an der Adresse A1 und SL3 177 an der Adresse A2 durch Kopierenbeim-Schreiben abzubilden. (Man beachte, daß diese Information aus der Abbildungsliste 120 erlangt worden ist).
Die Client-Domäne 108 startet das Ablaufen der Domäne D 126 durch Aufrufen der enter-Methode auf dem Domänenobjekt D 116.
Man beachte, daß in Fig. 7 der Bibliothekscache 148 außerdem eine cache-gespeicherte Kopie der gemeinsamen Bibliothek SL 172 und eine provisorisch fixierte Version, welche in dem Speicherobjekt SL2 174 ist, aufweist. Da wir jedoch einen Treffer in dem Abbild-Cache 144 erhielten, brauchten wir nicht den Bibliothekscache 148 zu konsultieren.
Als zweites Beispiel sei betrachtet der Fall, wenn es keinen Abbild-Cache-Treffer aber einen Bibliothekscache- Treffer gibt. Für dieses Beispiels sei angenommen, daß der Abbild-Cache 144 in Fig. 7 leer ist, wenn die Client-Domäne 108 das Programmabbild zu verknüpfen versucht. Die Verknüpferdomäne 140 führt die Verknüpfung unter Verwendung der folgenden Schritte aus:
Die Verknüpferdomäne 140 schlägt M 112 und C 109 in ihrem Abbild-Cache 144 nach und findet keine Übereinstimmung.
Die Verknüpferdomäne 140 schlägt im Speicherobjekt M 112 nach und entdeckt, daß sie ein geteiltes Bibliotheksprogramm mit dem Namen SL zum Verknüpfen benötigt.
Die Verknüpferdomäne 140 schlägt den Namen SL unter Verwendung des Kontextobjekts C 109 nach. (Man beachte, daß dieser Schritt für jedes erforderliche Bibliotheksprogramm wiederholt würde). Das Ergebnis ist das Speicherobjekt SL 300 (dieses Speicherobjekt ist nicht in der Verknüpferdomäne 140 gezeigt), das den Inhalt des gemeinsamen Bibliotheksprogramms SL enthält.
Die Verknüpferdomäne 140 sieht in ihrem Bibliotheks-Cache 148 unter Verwendung des Speicherobjekt SL 300 als Argument nach und entdeckt, daß sie einen Eintrag mit dem Schlüssel SL 172 aufweist, der übereinstimmt (das heißt, SL 172 ist äquivalent zu SL 300). Der cache-gespeicherte Eintrag enthält eine Cache-Kopie einer provisorisch fixierten Version der gemeinsamen Bibliothek SL, welche das Speicherobjekt SL 274 ist.
Die Verknüpferdomäne 140 erzeugt ein Speicherobjekt M2 168, das eine Kopiere-beim-Schreiben-Kopie von M 112 ist, und erzeugt ein Speicherobjekt SL3 170, das eine Kopiere-beim-Schreiben-Kopie von SL2 174 ist.
Die Verknüpferdomäne 140 löst sämtliche nicht aufgelösten Referenzen in M2 168 unter Verwendung von SL3 170 auf und löst sämtliche nicht aufgelösten Referenzen in SL3 170 unter Verwendung von M2 168 auf. (Wie dies ausgeführt wird, wurde oben beschrieben und in dem Ablaufdiagramm gezeigt). Das Ergebnis besteht darin, daß M2 168 und SL3 170 eine vollständig verknüpfte Version des Programms foo umfassen. Wiederum sei angemerkt, daß dann, wenn es mehrere erforderliche Bibliotheksprogramme gäbe, dieselben Schritte für jedes wiederholt würden.
Die Verknüpferdomäne gibt M2 168 und SL3 170 in ihren Abbild-Cache 144 zusammen mit ihren zugehörigen Schlüsseln (Speicherobjekt C 164 und Speicherobjekt M 166) ein und gibt eine Liste von ≤ Adresse zum Abbilden, Speicherobjektpaare> 173 an die Client-Domäne 108 zurück (diese Liste ist als Abbildungsliste 120 in 108 bezeichnet). Der erste Eintrag in der Liste 121 enthält die Adresse A1 und das Speicherobjekt M2 und der zweite Eintrag in der Liste 123 enthält die Adresse A2 in das Speicherobjekt SL3.
Die Client-Domäne 108 verfolgt dann die gleichen Schritte wie bei dem ersten Beispiel zum Erzeugen der neuen Domäne.
Als letztes Beispiel sei der Fall genannt, wenn es keinen Abbild- oder Bibliotheks-Cache-Treffer gibt. Für dieses Beispiel sei angenommen, daß dann, wenn die Client-Domäne 108 versucht, das Programmabbild zu verknüpfen, der Abbild- Cache 144 und der Bibliotheks-Cache 148 leer sind. Die Verknüpferdomäne 140 führt die Verknüpfung unter Verwendung der folgenden Schritte aus:
Die Verknüpferdomäne 140 schlägt M 112 und C 109 in ihrem Abbild-Cache 144 nach und findet keine Übereinstimmung.
Die Verknüpferdomäne 140 findet das Speicherobjekt M 112 und bildet es in ihrem Adreßraum ab und entdeckt, daß M 112 eine Verknüpfung zu einer gemeinsamen Bibliothek mit dem Namen SL benötigt.
Die Verknüpferdomäne 140 schlägt den Namen SL unter Verwendung des Kontextobjekts C 109 nach. Das Ergebnis ist das Speicherobjekt SL 172, das den Inhalt des gemeinsamen Bibliotheksprogramms SL enthält.
Die Verknüpferdomäne 140 sieht in ihrem Bibliotheks-Cache 148 unter Verwendung des Speicherobjekts SL 172 als Argument nach und findet keine Übereinstimmung (es sei daran erinnert, daß wir bei diesem Beispiel annahmen, daß der Bibliotheks-Cache leer ist).
Die Verknüpferdomäne 140 entscheidet, daß das Speicherobjekt SL 172 bei einer verfügbaren Adresse in ihrem Adreßraum (nennen wir sie A2) fixiert werden muß.
Die Verknüpferdomäne 140 erzeugt ein Speicherobjekt SL 260, das eine Kopiere-beim-Schreiben-Kopie von SL 172 ist, und bildet SL2 in ihrem Adreßraum ab.
Die Verknüpferdomäne 140 fixiert provisorisch SL2 (siehe die Erörterung über Fixierungen oben und das detaillierte Ablaufdiagramm in Fig. 4 hinsichtlich der Details) und speichert SL2 174 in dem Bibliotheks-Cache 148 (zusammen mit seinem Schlüssel SL 172).
Die Verknüpferdomäne 140 erzeugt ein Speicherobjekt M2 168, das eine Kopiere-beim-Schreiben-Kopie von M 112 ist, und erzeugt ein Speicherobjekt SL3 170, das eine Kopiere-beim-Schreiben-Kopie von SL2 174 ist.
Die Verknüpferdomäne 140 löst sämtliche nicht aufgelösten Referenzen in M2 168 unter Verwendung von SL3 170 auf und löst sämtliche nicht aufgelösten Referenzen in SL3 170 unter Verwendung von M2 168 auf (wie dies ausgeführt wird, ist in der obigen Diskussion über Fixierungen und in dem detaillierten Ablaufdiagramm in Fig. 4 erläutert). Das Ergebnis besteht darin, daß M2 168 und SL3 170 eine vollständig verknüpfte Version des Programms foo sind.
Die Verknüpferdomäne 140 gibt M2 168 und SL3 170 in ihren Abbild-Cache 144 (zusammen mit ihrem Schlüssel, Speicherobjekt M 166 und ihrem Kontextobjekt C 164) ein und gibt eine Liste 172 von ≤ Adresse zum Abbilden, Speicherobjektpaare> an die Client-Domäne 108 zurück. Der erste Eintrag der Liste 121 enthält die Adresse A1 und das Speicherobjekt M2. Der zweite Eintrag in der Liste 123 enthält die Adresse A2 und das Speicherobjekt SL3.
Die Client-Domäne 108 folgt dann den gleichen Schritten wie oben bei dem ersten Beispiel, um die neue Domäne 104 zu erzeugen.
Ein alternatives Ausführungsbeispiel der Erfindung besteht darin, nur den Cache für gemeinsame Bibliotheksprogramme bei dem dynamischen Verknüpfersystem zu verwenden, wobei dieselben Schritte, wie oben ausgeführt, verfolgt werden, beginnend mit dem zweiten Beispiel.
Während die oben genannten Beispiele das gegenwärtig bevorzugte Ausführungsbeispiel beschreiben und spezielle Programmdomänen und eine bestimmte Sequenz von Schritten beschreiben, erkennen Fachleute, daß diese Spezifika für die Ausführung der Erfindung nicht wesentlich sind, wobei die Erfindung im wesentlichen die Verwendung von Caches für die Einbehaltung vollständig verknüpfter Abbilder von Programmen und ihre zugeordneten Bibliotheken sowie partiell fixierter Bibliotheksroutinen verkörpert, womit die gesamten dynamischen Verknüpfungsmehraufwandkosten minimiert werden.

Claims

1. Ein Verfahren zum effektiven Erzeugen eines vollständig verknüpften Programmabbilds eines bestimmten Programms und zugehöriger Bibliotheksprogramme unter Verwendung eines dynamischen Verknüpfungssystems, das einen Abbild-Cache umfaßt, wobei das Verfahren in einem Computersystem implementiert ist, wobei das Verfahren gekennzeichnet ist durch die Schritte:

Aufrufen des Verknüpfungssystems mit Parametern, die ein unverknüpftes Programmabbild des bestimmten Programms darstellen;

Durchsuchen (22) des Abbild-Caches nach dem vollständig verknüpften Programmabbild des bestimmten Programms und der zugehörigen Bibliotheksprogramme; und

wobei dann, wenn das vollständig verknüpfte Programmabbild in dem Abbild-Cache gefunden wird (28), das Verfahren ferner die Schritte umfaßt:

Wiedergewinnen (38) des vollständig verknüpften Programmabbilds mit einer Liste von Programmidentifizierern und zugehörigen Adressen für jedes der zugehörigen Bibliotheksprogramme aus dem Abbild-Cache; und

Abbilden (38) des vollständig verknüpften Programmabbilds des bestimmten Programms und jedes der zugehörigen Bibliotheksprogramme auf die Adressen aus der Liste von Programmidentifizierern.

2. Das Verfahren nach Anspruch 1, wobei dann, wenn das vollständig verknüpfte Programmabbild nicht in dem Abbild- Cache gefunden wird, das Verfahren ferner die Schritte umfaßt:

Erzeugen (26) einer unverknüpften Kopie des bestimmten Programms;

Durchsuchen (26) eines Bibliotheks-Cache des Verknüpfungssystems nach einer provisorisch festgelegten (fixed-up) Kopie der zugehörigen Bibliotheksprogramme; und

wobei dann, wenn die provisorisch festgelegten Bibliotheksprogramme in dem Bibliotheks-Cache gefunden werden, das Verfahren ferner die Schritte umfaßt:

Wiedergewinnen (34) der provisorisch festgelegten Bibliotheksprogramme aus dem Bibliotheks-Cache;

Verknüpfen (34) der provisorisch festgelegten Bibliotheksprogramme miteinander und mit dem unverknüpften bestimmten Programm, um das vollständig verknüpfte Programmabbild des bestimmten Programms und der zugehörigen Bibliotheksprogramme mit einer Liste von Programmidentifizierern und zugehörigen Adressen, die einen Identifizierer und eine zugehörige Adresse für das bestimmte Programm und für jedes der zugehörigen Bibliotheksprogramme enthält, zu erzeugen; und

Abbilden (38) des vollständig verknüpften Programmabbilds des bestimmten Programms und jedes der provisorisch festgelegten Bibliotheksprogramme auf die zugehörigen Adressen aus der Liste von Programmidentifizierern.

3. Das Verfahren nach Anspruch 2, wobei dann, wenn die provisorisch festgelegten Bibliotheksprogramme nicht in dem Bibliotheks-Cache gefunden werden, das Verfahren ferner die folgenden Schritte umfaßt:

Auswählen einer Adresse (32), mit welcher zugehörige Bibliotheksprogramme verknüpft werden sollen;

Erzeugen einer unverknüpften Kopie (32) der zugehörigen Bibliotheksprogramme;

provisorisches Festlegen (fixing-up) von Verschiebungssymbolen (32) in der Kopie der zugehörigen Bibliotheksprogramme;

Verknüpfen (32) der provisorisch festgelegten Bibliotheksprogramme miteinander und mit dem unverknüpften bestimmten Programm, um das vollständig verknüpfte Programmabbild des bestimmten Programms und der zugehörigen Bibliotheksprogramme mit einer Liste von Programmidentifizierern und zugehörigen Adressen, die einen Identifizierer und eine zugehörige Adresse für das bestimmte Programm und für jedes der zugehörigen Bibliotheksprogramme umfaßt, zu erzeugen;

Abbilden (32) des vollständig verknüpften Programmabbilds des bestimmten Programms und jedes der zugehörigen Bibliotheksprogramme auf die zugehörigen Adressen aus der Liste von Programmidentifizierern; und

Hinzufügen (34) der provisorisch festgelegten Bibliotheksprogramme zu dem Bibliotheks-Cache.

4. Das Verfahren nach Anspruch 3, wobei dann, wenn das Programmabbild nicht in dem Abbild-Cache gefunden wird, das Verfahren ferner die Schritte umfaßt:

Hinzufügen (34) des vollständig verknüpften Programmabbilds mit den provisorisch festgelegten Bibliotheksprogrammen und der Liste von Programmidentifizierern und zugehörigen Adressen zu dem Abbild-Cache für eine nachfolgende Wiedergewinnung durch das Verknüpfungssystem.

5. Das Verfahren nach Anspruch 4, wobei sämtliche Programme objekt orientierte Programme sind.

6. Das Verfahren nach Anspruch 1, wobei der Schritt des Durchsuchens des Abbild-Cache nach dem vollständig verknüpften Programmabbild den Schritt umfaßt:

Überprüfen des Abbild-Cache nach einem Schlüssel, welcher mit dem bestimmten Programm und den zugehörigen Bibliotheksprogrammen übereinstimmt.

7. Das Verfahren nach Anspruch 2, wobei der Schritt des Durchsuchens nach einer provisorisch festgelegten Kopie der zugehörigen Bibliotheksprogramme die zusätzlichen Schritte umfaßt

Erzeugen (308) einer ersten Namensliste, die Namen der Bibliotheksprogramme enthält, welche zu dem bestimmten Programm gehören; und

Auflösen (310) jedes der Namen der in der ersten Liste enthaltenen Bibliotheksprogramme in einen Bibliotheksprogrammidentifizierer und Hinzufügen jedes Bibliotheksprogrammidentifizierers zu einer zweiten Liste.

8. Das Verfahren nach Anspruch 7, wobei der Schritt des Wiedergewinnens der provisorisch festgelegten Bibliotheksprogramme die zusätzlichen Schritte umfaßt:

Überprüfen (316) des Bibliotheks-Cache hinsichtlich einer Übereinstimmung jedes Bibliotheksprogrammidentifizierers in der zweiten Liste;

Gewinnen (322) eines übereinstimmenden Bibliotheksprogramms aus dem Bibliotheks-Cache, sofern ein übereinstimmender Bibliotheksprogrammidentifizierer gefunden wird; und

Hinzufügen (336) des übereinstimmenden Bibliotheksprogrammidentifizierers aus dem Bibliotheks-Cache zu einer dritten Liste.

9. Das Verfahren nach Anspruch 8, umfassend die zusätzlichen Schritte:

Auswählen einer Adresse, mit welcher in der zweiten Liste identifizierte zugehörige Bibliotheksprogramme verknüpft werden sollen, sofern kein übereinstimmender Bibliotheksprogrammidentifizierer in dem Bibliotheks-Cache gefunden wird; Erzeugen (330) einer unverknüpften Kopie der zugehörigen Bibliotheksprogramme;

provisorisches Festlegen (332) von Verschiebungssymbolen in der Kopie der zugehörigen Bibliotheksprogramme;

Verknüpfen (332) der provisorisch festgelegten Bibliotheksprogramme miteinander und mit dem unverknüpften bestimmten Programm, um das vollständig verknüpfte Programmabbild des bestimmten Programms und der zugehörigen Bibliotheksprogramme mit einer Liste von Programmidentifizierern und zugehörigen Adressen, die einen Identifizierer und eine zugehörige Adresse für das bestimmte Programm und für jedes der zugehörigen Bibliotheksprogramme enthält, zu erzeugen;

Hinzufügen (334) der provisorisch festgelegten Bibliotheksprogramme zu dem Bibliotheks-Cache; und

Hinzufügen (336) der provisorisch festgelegten Bibliotheksprogrammidentifizierer zu der dritten Liste.

10. Das Verfahren nach Anspruch 9, umfassend die zusätzlichen Schritte:

Herstellen einer Kopie (342) des Programmabbilds und Hinzufügen eines Identifizierers der Kopie des Programmabbilds zu einer vierten Liste, wobei die Kopie des Programmabbilds eine Symboltabelle und eine Verschiebungstabelle aufweist; und Herstellen einer Kopie (344) jedes der Bibliotheksprogramme aus der dritten Liste und Hinzufügen eines Identifizierers der Kopie der Bibliotheksprogramme zu der vierten Liste, wobei jede der Kopien der Bibliotheksprogramme eine Symboltabelle und eine Verschiebungstabelle aufweist.

11. Das Verfahren nach Anspruch 10, umfassend die zusätzlichen Schritte:

Auffinden jedes zu verschiebenden Symbols (352) in der Kopie des Programmabbilds; und

Durchsuchen (336) sämtlicher der in der vierten Liste identifizierten Bibliotheksprogramme und, sofern eine erste Symboldefinition, welche mit dem zu verschiebenden Symbol übereinstimmt, gefunden wird, Verwenden einer Adresse der ersten Symboldefinition, welche mit dem zu verschiebenden Symbol übereinstimmt, um eine Verschiebung für das zu verschiebende Symbol durchzuführen.

12. Das Verfahren nach Anspruch 11, umfassend die zusätzlichen Schritte:

Verwenden der Symboltabelle (356) in jedem der in der vierten Liste identifizierten Bibliotheksprogramme, um der Reihe nach, beginnend mit einem ersten in der vierten Liste identifizierten Bibliotheksprogramm, jedes Symbol der Symboltabelle mit der Symboltabelle des Programmabbilds zu vergleichen und um ein Symbol in der Symboltabelle des Bibliotheksprogramms als überschrieben (overridden) zu markieren, sofern das Symbol mit einem Symbol in der Symboltabelle des Programmabbilds übereinstimmt;

Vergleichen jedes Symbols jeder der Symboltabellen mit sämtlichen Symboltabellen der in der vierten Liste identifizierten Bibliotheksprogramme, welche an einer höheren Stelle in der vierten Liste sind, als die Symboltabelle, welche überprüft wird, und welche als bereits überprüft markiert worden sind;

Markieren des Identifizierers eines in der vierten Liste identifizierten Bibliotheksprogramms bei Abschluß der Überprüfung der Symboltabelle des Bibliotheksprogramms der vierten Liste als einen, dessen Symboltabelle überprüft worden ist; und

Vergleichen der Symbole in den Symboltabellen in jedem der in der vierten Liste identifizierten Bibliotheksprogramme auf eine gleiche Weise, bis sämtliche Symboltabellen verglichen worden sind.

13. Das Verfahren nach Anspruch 12, umfassend die zusätzlichen Schritte:

Verwenden der Verschiebungstabelle (366) in jedem der in der vierten Liste identifizierten Programme, um nacheinander beginnend mit einem ersten in der vierten Liste identifizierten Programm jede der. Verschiebungstabellen zu durchsuchen, um ein undefiniertes Symbol aufzufinden;

sofern ein Symbol in einer der Verschiebungstabellen ein definiertes Symbol ist (370), Überprüfen des definierten Symbols, und sofern das definierte Symbol als überschrieben markiert worden ist, Rückgängigmachen einer Verschiebungsadresse für das definierte Symbol, welches als überschrieben markiert worden ist;

Verwenden jedes undefinierten Symbols (368) und jedes definierten Symbols, dessen Verschiebungsadresse rückgängig gemacht wurde, als Suchargument beim Überprüfen der Symboltabelle der Kopie des Programmabbilds und der Symboltabellen jeder der in der vierten Liste identifizierten Bibliotheksprogramme, um ein mit dem Suchargument übereinstimmendes Symbol aufzufinden, und, sofern das übereinstimmende Symbol gefunden ist, Verwenden der Adresse des übereinstimmenden Symbols, um die Adreßverschiebung für das Symbol durchzuführen, welches als Suchargument verwendet worden ist; und

Bereitstellen einer Ausnahmenachricht (372) für den Fall, daß herausgefunden wird, daß kein Symbol mit dem Suchargument übereinstimmt.

14. Das Verfahren nach Anspruch 13, umfassend die zusätzlichen Schritte:

Erzeugen einer cache-baren Liste (388) von Programmidentifizierern, die eine Kopie des bestimmten Programmabbilds und jedes der in der vierten Liste identifizierten Bibliotheksprogramme enthält;

Eingeben der cache-baren Liste (388) von Programmidentifizierern in den Abbild-Cache; und

Rückgeben der cache-baren Liste (390) von Programmidentifizierern in Erwiderung auf das Verknüpfungssystem.

15. Das Verfahren nach Anspruch 14, wobei die Programme Objekte sind und das Computersystem ein objekt-orientiertes System ist.

16. Das Verfahren nach Anspruch 15, wobei die Identifizierer und die Programmidentifizierer Speicherobjekte sind.

17. Das Verfahren nach Anspruch 1, wobei:

dann, wenn kein vollständig verknüpftes Programmabbild in dem Abbild-Cache gefunden wird (24), das Verfahren ferner die Schritte umfaßt:

Überprüfen eines Bibliotheks-Cache (26) hinsichtlich einer provisorisch festgelegten (fixed-up) Kopie der zugehörigen Bibliotheksprogramme und dann, wenn der Bibliotheks- Cache die provisorisch festgelegten zugehörigen Bibliotheksprogramme enthält, Wiedergewinnen der provisorisch festgelegten Bibliotheksprogramme; und

wobei dann, wenn die provisorisch festgelegten Bibliotheksprogramme in dem Bibliotheks-Cache nicht gefunden werden (30), das Verfahren ferner die Schritte umfaßt:

Erzeugen (32) einer Liste von Bibliotheksprogrammidentifizierern und zugehörigen Adressen aus dem Bibliotheks- Cache;

Verknüpfen (34) jedes der Bibliotheksprogramme miteinander und mit dem Programmabbild, um das vollständig verknüpfte Programmabbild zu erzeugen; und

Abbilden (38) des von den Programmidentifizieren identifizierten vollständig verknüpften Programmabbilds mit der zugehörigen Adresse aus der Liste von Programmidentifizierern.

18. Das Verfahren nach Anspruch 17, wobei der Schritt des Erzeugens einer Liste von Bibliotheksprogrammidentifizierern und zugehörigen Adressen aus dem Bibliotheksprogramm-Cache die zusätzlichen Schritte umfaßt:

Erzeugen (308) einer ersten Liste, die die Namen derjenigen Bibliotheksprogramme enthält, welche zu dem bestimmten Programm gehören;

Auflösen (310) jedes der Namen der Bibliotheksprogramme, die in der ersten Liste enthalten sind, in einen Bibliotheksprogrammidentifizierer und Hinzufügen jedes der Bibliotheksprogrammidentifizierer zu einer zweiten Liste;

Überprüfen (322) des Bibliotheks-Cache hinsichtlich einer Übereinstimmung für jeden Bibliotheksprogrammidentifizierer in der zweiten Liste;

Gewinnen (336) eines übereinstimmenden Bibliotheksprogramms aus dem Bibliotheks-Cache, sofern ein übereinstimmender Bibliotheksprogrammidentifizierer gefunden wird; und

19. Das Verfahren nach Anspruch 18, umfassend die zusätzlichen Schritte:

Auswählen (328) einer Adresse, mit welcher in der zweiten Liste identifizierte zugehörige Bibliotheksprogramme verknüpft werden sollen, sofern kein übereinstimmender Bibliotheksprogrammidentifizierer in dem Bibliotheks-Cache gefunden wird;

Erzeugen (330) einer unverknüpften Kopie der zugehörigen Bibliotheksprogramme;

provisorisches (332) Festlegen von Verschiebungssymbolen in der Kopie der zugehörigen Bibliotheksprogramme;

Hinzufügen (336) des provisorisch festgelegten Bibliotheksprogrammidentifizierers zu der dritten Liste.

20. Das Verfahren nach Anspruch 19, umfassend die zusätzlichen Schritte:

Herstellen (343) einer Kopie des Programmabbilds und Hinzufügen eines Identifizierers der Kopie des Programmabbilds zu einer vierten Liste, wobei die Kopie des Programmabbilds eine Symboltabelle und eine Verschiebungstabelle aufweist; und

Herstellen (342) einer Kopie jedes der Bibliotheksprogramme aus der dritten Liste und Hinzufügen eines Identifizierers der Kopie der Bibliotheksprogramme zu der vierten Liste, wobei jede der Kopien der Bibliotheksprogramme eine Symboltabelle und eine Verschiebungstabelle aufweist.

21. Das Verfahren nach Anspruch 20, umfassend die zusätzlichen Schritte:

Auffinden (352) jedes zu verschiebenden Symbols in der Kopie des Programmabbilds; und

Durchsuchen (356) sämtlicher in der vierten Liste identifizierter Bibliotheksprogramme und, sofern eine erste Symboldefinition, welche mit dem zu verschiebenden Symbol übereinstimmt, aufgefunden wird, Verwenden einer Adresse der ersten Symboldefinition, welche mit dem zu verschiebenden Symbol übereinstimmt, um eine Verschiebung des zu verschiebenden Symbols durchzuführen.

22. Das Verfahren nach Anspruch 21, umfassend die zusätzlichen Schritte:

Verwenden (358) der Symboltabelle in jedem der in der vierten Liste identifizierten Bibliotheksprogramme, um der Reihe nach beginnend mit einem ersten der in der vierten Liste identifizierten Bibliotheksprogramme jedes Symbol der Symboltabelle mit der Symboltabelle des Programmabbilds zu vergleichen und ein Symbol in der Symboltabelle des Bibliotheksprogramms als überschrieben zu markieren, sofern das Symbol mit einem Symbol in der Symboltabelle des Programmabbilds übereinstimmt;

Vergleichen jedes Symbols jeder der Symboltabellen mit sämtlichen Symboltabellen der in der vierten Liste identifizierten Bibliotheksprogramme, welche an einer höheren Stelle in der vierten Liste sind als die Symboltabelle, welche überprüft wird und welche als bereits überprüft markiert worden ist;

bei Abschluß der Überprüfung der Symboltabelle jedes der in der vierten Liste identifizierten Bibliotheksprogramme:

Markieren des Identifizierers des Bibliotheksprogramms in der vierten Liste als einen, dessen Symboltabelle überprüft worden ist; und

Vergleichen der Symbole in den Symboltabellen in jedem der in der vierten Liste identifizierten Bibliotheksprogramme in gleicher Weise, bis sämtliche Symboltabellen verglichen worden sind.

23. Das Verfahren nach Anspruch 22, umfassend die zusätzlichen Schritte:

Verwenden (366) der Verschiebungstabelle in jedem der in der vierten Liste identifizierten Programme, um nacheinander beginnend mit einem ersten der in der vierten Liste identifizierten Programme jede der Verschiebungstabellen zu durchsuchen, um ein undefiniertes Symbol aufzufinden;

dann, wenn ein Symbol in einer der Verschiebungstabellen ein definiertes Symbol ist, Überprüfen des definierten Symbols (378) ein zweites Mal und, sofern das definierte Symbol als überschrieben markiert worden ist, Rückgängig-Machen einer Verschiebungsadresse für das definierte Symbol, welches als überschrieben markiert worden ist;

Verwenden jedes undefinierten Symbols (368) und jedes definierten Symbols, dessen Verschiebungsadresse rückgängig gemacht wurde, als Suchargument, Überprüfen der Symboltabelle der Kopie des Programmabbilds und der Symboltabellen jeder der in der vierten Liste identifizierten Bibliotheksprogramme, um ein Symbol aufzufinden, das mit dem Suchargument übereinstimmt, und, sofern das übereinstimmende Symbol gefunden wird, Verwenden der Adresse des gefundenen Symbols, um die Adreßverschiebung für das Symbol, welches als das Suchargument verwendet worden ist, durchzuführen; und

Bereitstellen einer Ausnahmenachricht (372), sofern gefunden wird, daß kein Symbol mit dem Suchargument übereinstimmt.

24. Das Verfahren nach Anspruch 23, umfassend die zusätzlichen Schritte:

Erzeugen (388) einer cache-baren Liste von Programmidentifizierern, die eine Kopie des bestimmten Programmabbilds und jedes der in der vierten Liste identifizierten Bibliotheksprogramme enthält; und

Zurückgeben (390) der cache-baren Liste von Programmidentifizierern in Erwiderung auf das Verknüpfungssystem.

25. Das Verfahren nach Anspruch 24, wobei die Programme Objekte sind und das Computersystem ein objekt-orientiertes System ist.

26. Das Verfahren nach Anspruch 25, wobei die Identifizierer und die Programmidentifizierer Speicherobjekte sind.

27. Ein Abbild-Cache-System zum Bereitstellen eines vollständig verknüpften Programmabbilds eines bestimmten Programms und zugehöriger Bibliotheksprogramme für ein dynamisches Verknüpfungssystem, wobei das Cache-System in einem Computersystem implementiert ist, wobei das Abbild-Cache-System gekennzeichnet ist durch:

einen Abbild-Cache (144) zum Cache-Speichern des vollständig verknüpften Programmabbilds mit einer Liste von Programmidentifizierern und zugehörigen Adressen für jedes der zugehörigen Bibliotheksprogramme, wobei die Liste zum Abbilden des vollständig verknüpften Programmabbilds dient;

eine erste mit dem Abbild-Cache gekoppelte Sucheinrichtung (22) zum Durchsuchen des Abbild-Cache, um zu bestimmen, ob der Abbild-Cache das vollständig verknüpfte Programmabbild enthält, wobei die Suche in Beantwortung einer Anforderung zum Verknüpfen des bestimmten Programms durchgeführt wird; und

eine mit der ersten Sucheinrichtung gekoppelte erste Kommunikationseinrichtung (38) zum Antworten auf die Anforderung zum Verknüpfen des bestimmten Programms, wobei die Antwort die Liste von Programmidentifizierern und zu den Programmidentifiziererri gehörende Adressen enthält, die aus dem Abbild-Cache gewonnen wurden, sofern das vollständig verknüpfte Programmabbild in dem Abbild-Cache gefunden wird.

28. Das Abbild-Cache-System nach Anspruch 27, ferner aufweisend:

einen mit dem Abbild-Cache gekoppelten Bibliotheks-Cache (148) zum Speichern provisorisch festgelegter (fixed-up) Bibliotheksprogramme; und

eine mit dem Bibliotheks-Cache gekoppelte zweite Sucheinrichtung (263) zum Durchsuchen des Bibliotheks-Cache, um zu bestimmen, ob wenigstens eines der provisorisch festgelegten Bibliotheksprogramme mit wenigstens einem der zugehörigen Bibliotheksprogramme übereinstimmt.

29. Das Abbild-Cache-System nach Anspruch 28, wobei das Durchsuchen des Bibliotheks-Cache durchgeführt wird, wenn das vollständig verknüpfte Programmabbild nicht in dem Abbild-Cache, welcher mit dem bestimmten Programm übereinstimmt, gefunden wird, und wobei die erste Suchmöglichkeit eine unverknüpfte Kopie des bestimmten Programms gewinnt.

30. Das Abbild-Cache-System nach Anspruch 29, ferner aufweisend:

eine mit der zweiten Sucheinrichtung gekoppelte erste Verknüpfungseinrichtung (32) zum Verknüpfen eines gefundenen Bibliotheksprogramms mit dem unverknüpften Programmabbild, sofern wenigstens eines der provisorisch festgelegten Bibliotheksprogramme in dem Bibliotheks-Cache gefunden ist, welches mit wenigstens einem der zugehörigen Bibliotheksprogramme übereinstimmt.

31. Das Abbild-Cache-System nach Anspruch 30, ferner aufweisend:

eine mit der zweiten Sucheinrichtung gekoppelte dritte Sucheinrichtung (36) zum Auffinden unverknüpfter Bibliotheksprogramme, sofern kein Bibliotheksprogramm in dem Bibliotheks-Cache gefunden wird, das mit dem zugehörigen Bibliotheksprogramm übereinstimmt; und

eine mit der dritten Sucheinrichtung gekoppelte zweite Verknüpfungseinrichtung (32) zum Verknüpfen der unverknüpften Bibliotheksprogramme miteinander und mit den gefundenen Bibliotheksprogrammen und mit dem unverknüpften Programmabbild, wobei ein vollständig verknüpftes Programmabbild des bestimmten Programms mit zugehörigen Bibliotheksprogrammen erzeugt wird.

32. Das Abbild-Cache-System nach Anspruch 31, wobei:

eine zweite Verknüpfungseinrichtung (32) irgendwelche der unverknüpften Bibliotheksprogramme provisorisch festlegt (fixed-up) und die provisorisch festgelegten Bibliotheksprogramme in dem Bibliotheks-Cache speichert; und

die zweite Verknüpfungseinrichtung (32) das vollständig verknüpfte Programmabbild mit zugehörigen Bibliotheksprogrammen in dem Abbild-Cache (144) speichert.

33. Das Abbild-Cache-System nach Anspruch 22, wobei das bestimmte Programm und die Bibliotheksprogramme objektorientierte Programme sind.

34. Das Abbild-Cache-System nach Anspruch 28, wobei die zweite Sucheinrichtung (26) die Suche in Erwiderung einer Anforderung zum Verknüpfen des bestimmten Programms durchführt, sofern das vollständig verknüpfte Programmabbild des bestimmten Programms von dem dynamischen Verknüpfungssystem nicht aufgefunden wird; und

eine mit der zweiten Sucheinrichtung gekoppelte erste Verknüpfungseinrichtung (38) zum Verknüpfen eines aufgefundenen Bibliotheksprogramms mit dem bestimmten Programm, sofern das gefundene Bibliotheksprogramm in dem Bibliotheks- Cache gefunden wird.

35. Das Abbild-Cache-System nach Anspruch 34, wobei die erste Sucheinrichtung ferner aufweist:

eine mit dem Bibliotheks-Cache (148) gekoppelte zweite Sucheinrichtung (26) zum Durchsuchen des Bibliotheks-Cache, zum Bestimmen, ob der Bibliotheks-Cache ein unverknüpftes Bibliotheksprogramm enthält, das mit einem der zugehörigen Bibliotheksprogramme übereinstimmt.

36. Das Abbild-Cache-System nach Anspruch 34, ferner aufweisend:

eine mit dem Speicher des Computers gekoppelte zweite Sucheinrichtung (26) zum Auffinden der unverknüpften Bibliotheksprogramme, welche mit den zugehörigen Bibliotheksprogrammen übereinstimmen; und

eine mit der zweiten Sucheinrichtung gekoppelte zweite Verknüpfungseinrichtung (32) zum Verknüpfen der unverknüpften Bibliotheksprogramme miteinander und mit den aufgefundenen Bibliotheksprogrammen und mit der unverknüpften Kopie des bestimmten Programms, wobei ein vollständig verknüpftes Programmabbild des bestimmten Programms mit zugehörigen Bibliotheksprogrammen erzeugt wird.

37. Das Abbild-Cache-System nach Anspruch 36, wobei:

die zweite Verknüpfungseinrichtung (32) irgendwelche der unverknüpften Bibliotheksprogramme provisorisch festlegt (fixed-up) und die provisorisch festgelegten Bibliotheksprogramme in den Bibliotheks-Cache speichert.

38. Das dynamische Verknüpfungssystem nach Anspruch 37, wobei die Bibliotheksprogramme in dem Bibliotheksprogramm- Cache (148) partiell verknüpfte Bibliotheksprogramme sind.

39. Das dynamische Verknüpfungssystem nach Anspruch 38, wobei die Anwendungsprogramme und die Bibliotheksprogramme objekt orientierte Programme sind.