DE69522842T2 - Gleichzeitige Verarbeitung in parallelen und fast parallelen objektorientierten Systemen - Google Patents

Description

• Die vorliegende Erfindung betrifft einen Mechanismus zur Durchführung gleichzeitiger Operationen in parallelen und fast parallelen Datenverarbeitungssystemen, um die Kapazität eines Prozessors maximal nutzen zu können.
• In einem einfachen Computermodell (beispielsweise an einem einzelnen PC-Arbeitsplatz) arbeitet ein einzelnes Programm, das auf einem einzelnen Prozessor läuft, jede seiner Routinen in einer programmierten Reihenfolge ab, was die Tätigkeit des Prozessors bis zum Abschluß dieses Prozesses bestimmt. Das Aufrufen eines Unterprogramms (beispielsweise eines in einem bestimmten Speicherbereich abgelegten Programmoduls) führt dazu, daß der Prozessor während der Verarbeitung dieses Unterprogramms die Abarbeitung der Routinen im Hauptprogramm aussetzt oder blockiert. In diesem Szenario werden die Ressourcen des Prozessors vollständig genutzt (der Prozessor arbeitet zu keinem Zeitpunkt im Leerlaufbetrieb), und es ist kein anderes Programm gleichzeitig aktiviert, das ebenfalls Speicherressourcen beansprucht. Folglich stellt die Dominierung des Prozessors für die Zeit der Verarbeitung des Programms und seiner Routinen kein Problem dar.
• In einem verteilten Computersystem stehen mehrere Prozessoren mit entsprechendem Speicher zur Verfügung, und das Aufrufen eines Unterprogramms außerhalb des Hauptprogramms kann problemlos über ein Programmodul erfolgen, das auf einem anderen Prozessor als das Hauptprogramm abgelegt ist. Dieser entfernte Prozessor führt dann die Operationen des Unterprogramms aus und gibt die gewünschten Ergebnisse an das Hauptprogramm zurück.
• Miteinander verbundene Prozessoren und verteilte Systeme werden seit dem Aufkommen der verteilten Rechnerumgebung (DCE) der Open System Foundation (OSF) zunehmend populärer. Diese neue Technologie ermöglicht die Nutzung verteilter Rechner innerhalb heterogener Systeme.
• Bei einem normalen lokalen Prozeduraufruf gibt es eine eindeutige Schnittstelle zwischen dem Abrufprogramm und einem speziellen Unterprogramm, und mit dem lokalen Prozeduraufruf wird die gesamte, zur Betriebsfähigkeit notwendige Logik aufgerufen. Wenn das Unterprogramm auf einem anderen Rechner als das Abrufprogramm abgelegt ist, wie es beispielsweise in einem verteilten System der Fall ist, wird zum Abrufen eine Kommunikationslogik benötigt (die den Speicherort des Unterprogramms, erforderliche Datenumwandlungen usw. angibt), die in der Regel ein festcodierter Bestandteil des Abrufprogramms und/oder des aufgerufenen Programms sein muß. Diese Logik ist besonders komplex, wenn zwischen dem entfernten Prozessor und dem Abrufprogramm keine Homogenität oder Kompatibilität besteht.
• Im Gegensatz dazu gestattet eine DCE, die in jedes der Einzelsysteme integriert ist, über einen Mechanismus mit der Bezeichnung "Fern-Prozeduraufruf" (RPC) ein transparentes Zusammenwirken der Rechner in einem Netzwerk. Dieser RPC schließt in seinen Aufruf die gesamte verteilte Umgebung ein, insbesondere die heterogene Umgebung, das Konzept des lokalen Prozeduraufrufs.
• Folglich werden Fernaufrufe in einer für den Programmierer wie den Benutzer transparenten Art und Weise abgearbeitet, und der Programmierer ist nicht mehr gezwungen, für jeden Fernaufruf Supportcode zu schreiben.
• Sofern während der Programmierung nicht entsprechende Vorkehrungen getroffen werden, setzt das Hauptprogramm jedoch in einer verteilten Umgebung die Belegung des Prozessors fort, selbst wenn die Programmverarbeitung suspendiert oder blockiert ist und das Programm auf die Ergebnisse des Fernaufrufs wartet. Während dieser Suspendierungsphase befindet sich der Prozessor im Leerlaufbetrieb.
• Der Zeitraum, innerhalb dem das wartende Programm suspendiert ist, kann unter realen Bedingungen auf Bruchteile einer Sekunde beschränkt bleiben, sofern der entfernte Prozessor das Unterprogramm sofort abarbeiten kann. In komplexen verteilten Systemen kann es aufgrund einer Warteschlangenbildung am entfernten Prozessor zu erheblichen Verzögerungen kommen, und in dieser gesamten Zeit bleibt der wartende Prozessor im Leerlaufbetrieb.
• Ideal wäre eine Situation, in der die Operationen an jedem Prozessor gleichzeitig ablaufen, das heißt, jedem aktiven Objekt ein separater Thread zugeordnet ist, so daß während der Suspendierung oder des "Wartens" des einen Thread andere Threads am Prozessor verarbeitet werden könnten.
• Die DCE (und andere Systeme) beinhaltet Merkmale, die dem Programmierer das Anlegen und Verarbeiten mehrerer Threads in einem einzelnen Programm gestatten. In einer DCE-Umgebung ist diese Mehrpfadfunktion in der Form einer Schnittstelle für Anwendungsprogramme ausgeführt, die auf der "pthreads"- Schnittstelle basiert. Diese wurde von Posix in der Norm 1003.4a Standard (Draft 4): IEEE P1003.4a/D4 Draft Standard, Threads Extension for Portable Operating Systems, Technical Committee on Operating Systems of the Institute of Electrical and Electronic Engineers (IEEE) Computer Society, New York, U. S. A., August 10, 1990, beschrieben.
• DCE und andere Mehrpfadsysteme verlangen vom Programmierer jedoch die Strukturierung eines Programms mit mehreren Steuer- Threads, und das kann zu einer zunehmenden Komplexität beim Entwerfen des Programms führen. Die vielen Threads müssen in einer kontrollierten Art und Weise verwaltet, geplant und untereinander kommunikationsfähig gestaltet werden. In der Regel ist es schwierig, alle Fälle zu prognostizieren, in denen Gleichzeitigkeit angemessen wäre. Das gilt insbesondere, wenn bestimmte Faktoren an den entfernten Prozessoren während der Fernaufrufe lange Thread-Erweiterungen verursachen.
• Folglich können diese Mehrpfadfunktionen die Arbeit behindern, und damit verbundene Probleme sind schwierig vorherzusagen.
• Darüber hinaus sind mit der Vermittlung von Threads im Prozessor des wartenden Thread Kosten verbunden, die sich aus dem Speichern und Neuladen der Prozessorregister und der Ausführung der notwendigen Stapelkorrekturen für den neuen Thread ergeben. Folglich sollte die Anzahl der geplanten Steuerstellen zwischen den Threads in einem Prozessor eines traditionellen Mehrpfadsystems möglichst gering gehalten werden, um die wirtschaftlichen Vorteile einer gleichzeitigen Verarbeitung wirklich maximieren zu können.
• Für nicht objektorientierte und einige objektorientierte Systeme mit erweiterten Compilern wurde als Lösung ein Mechanismus mit der Bezeichnung "future result" vorgeschlagen. Ein Beispiel hierfür ist COOL (R. Chandra, A. Gupta und J. Hennessy, "COOL: A Language for Parallel Programming", Languages and Compilers for Parallel Computing, Editors D. Gelernter, A. Nicolau and D. Padua, MIT Press, 1990). Dabei wird bei der Ausgabe eines Fernaufrufs das Ergebnis des Aufrufens des Unterprogramms in einem Future-Objekt oder Typ gespeichert, das bzw. der an das Hauptprogramm in Reaktion auf einen künftigen Prozeduraufruf zurückzugeben ist. Auf diese Weise läuft das Programm auf "seinem" Prozessor weiter, während gleichzeitig oder synchron das Unterprogramm abläuft. Falls das Hauptprogramm den "Future"-Aufruf vor der Verfügbarkeit der zukünftigen Variablen generiert, wird das Programm an diesem Punkt einfach blockiert, bis das gewünschte Ergebnis verfügbar ist.
• In nicht objektorientierten Systemen unterscheidet sich die Nachricht mit der Mitteilung, daß der Benutzer einen synchronen Aufruf implementiert, von Sprache zu Sprache erheblich. Explizite Funktionen, beispielsweise das Aufrufen von "resolve" mit "future" als Argument; kann bei einigen Systemen notwendig sein, während bei anderen Systemen der Aufruf "future" automatisch verarbeitet wird.
• Objektorientierte Umgebungen scheinen besonders gut für die Arbeit mit Fernaufrufen und Fern-Prozeduraufrufen geeignet zu sein, denn aufgrund der Konzeption und Implementierung objektorientierter Sprachen stehen Werkzeuge und Möglichkeiten für eine modulare Programmierung durch Code-Teilung zur Verfügung.
• Die computersimulierten "Objekte" in objektorientierten Systemen werden unabhängig voneinander definiert und unterhalten. Die Definition eines Objekts beinhaltet dessen "Methoden" (das sind die Prozeduren und Operationen, die das Objekt ausführen kann) und dessen "Variablen" (das sind die Attribute, deren Werte sich im Laufe der Zeit ändern können). Objekte werden durch die Festlegung von Klassen definiert. Eine Klasse ist eine Template, welche die Methoden und Variablen definiert, die in einen bestimmten Objekttyp zu integrieren sind. Klassen können durch andere Klassen definiert werden, das heißt, die Merkmale (Methoden und/oder Variablen) einer Unterklasse können von einer übergeordneten, allgemeineren Grundklasse vererbt werden. Neben den Methoden und Variablen, die sie erben, definieren Unterklassen ihre eigenen Methoden und Variablen. Hierzu können beispielsweise Charakteristika gehören, die das Überschreiben vererbter Charakteristika gestatten, obwohl die Implementierung solcher abgeleiteter Klassen nur innerhalb der Klasse selbst sichtbar ist, um eine Kontaminierung anderer Klassenimplementierungen zu verhindern.
• Eine abstrakte Klasse ist eine Basisklasse ohne Objekte oder Instanzen. Ihr einziger Zweck besteht in der Organisation einer Klassenhierarchie bzw. in einer Suche nach Methoden oder Variablen, die auf eine vererbte Klasse einer niedrigeren Ebene anwendbar sind. Vererbte Methoden und Variablen können in einer abgeleiteten Klasse enger definiert oder sogar neu definiert werden, so daß durch diese Technologie hochspezialisierte Objekte definiert werden können, die in ein komplexes System miteinander zusammenhängender, nicht jedoch identischer Objekte passen. Klassenhierarchien können viele Ebenen umfassen. Durch die Objektorientiertheit wird eine Flexibilität ermöglicht, die durch die perspektivische Bandbreite, welche auf diese Weise verteilten Rechnerumgebungen erschlossen wird, mit Sicherheit attraktiv ist.
• Die populärste objektorientierte Sprache, C++, ist jedoch beispielsweise eine inhärent sequentielle Sprache, die keine Möglichkeit einer gleichzeitigen Verarbeitung bietet. Es ist eine Tatsache, daß die Implementierung gleichzeitig ablaufender Programmieroperationen in objektorientierten Paradigmen sich im allgemeinen schwierig gestaltete. Das war auf das Fehlen einer geeigneten Unterstützung für die Steuerung und Synchronisierung gleichzeitig ablaufender Prozesse sowie auf wechselseitige Ausschlüsse zurückzuführen.
• Future-Variablen werden in anderen objektorientierten Sprachen(beispielsweise LISP, Concurrent SmallTalk und COOL) verwendet. Alle bisherigen Versuche einer Implementierung in C++ erwiesen sich jedoch als syntaktisch schwerfällig. So war es beispielsweise erforderlich, daß eintProgrammierer das Programm um Prolog- und Epilog-Code ergänzt, um eine Verarbeitung von Future-Variablen zu ermöglichen, oder es war eine Erweiterung der Sprache bzw. eine vom Standard abweichende Compiler-Modifizierung erforderlich.
• Eine Vielzahl von Versuchen wurde unternommen, um C++ um die Möglichkeit der gleichzeitigen Verarbeitung zu ergänzen, wobei nach zwei unterschiedlichen Herangehensweisen gearbeitet wurde. Bei der ersten Herangehensweise wird die Sprache erweitert, und es werden neue Sprachenkonstrukte hinzugefügt, mit denen die Erstellung und Steuerung gleichzeitig ablaufender Prozesse bewältigt werden soll. Das heißt: Der Compiler wird so erweitert, daß er neue Sprachenkonstrukte erkennt. Eine gängige Methode, diese Sprachen um die Möglichkeit der gleichzeitigen Verarbeitung zu ergänzen, besteht darin, das Erstellen, Synchronisieren und gegenseitige Ausschließen der gleichzeitigen Verarbeitung auf Objektebene zu ermöglichen. Ein solches Objekt wird als "aktives" Objekt bezeichnet. Während solche nachträglich erweiterten Sprachen sich durch ein verbessertes Leistungsvermögen, die höhere Ebene der Konstrukte und Möglichkeiten zur Kontrolle der Kompilierungszeit auszeichnen, sind sie durch die fehlende Übertragbarkeit zwischen den Betriebssystemen eingeschränkt.
• Bei der zweiten Herangehensweise wird mit einer Bibliothek wiederverwendbarer Abstraktionen gearbeitet, welche die Gleichzeitigkeitsdetails der niedrigeren Ebene (beispielsweise die Architektur, Datenpartitionen, die Kommunikation und die Synchronisation) kapseln. Durch die Verwendung einer Bibliothek werden die Gleichzeitigkeitsmechanismen außerhalb der Sprache gehalten. Dies gestattet dem Programmierer die Verwendung ihm vertrauter Compiler und Tools, was wiederum eine höhere Portabilitätsebene unterstützt, gleichzeitig aber durch eine Vielzahl von Bibliotheken die Möglichkeit einer Unterstützung vieler Gleichzeitigkeitsmodelle bietet. Während die meisten für C++ entwickelten aktuellen Bibliotheken zur Unterstützung einer gleichzeitigen Verarbeitung versuchen, dieses Merkmal durch "aktive" Objekte zu erreichen, wird eine implizite Gleichzeitigkeit nicht geboten, und dem Benutzer werden starke Restriktionen auferlegt. Eine der ersten für C++ entwickelten Bibliotheken zur Ablaufsteuerung, die wirklich die Möglichkeit einer gleichzeitigen Verarbeitung bietet, ist beispielsweise die in T. W. Doeppner, Jr. et al. "C++ on a Parallel Machine", Report CS-87-26, Department of Computer Science, Brown University, November 1987, beschriebene Bibliothek. Dabei erfolgt die Thread-Verwaltung jedoch explizit (die ordnungsgemäße Verwaltung obliegt dem Programmierer), und es ist nur eine Ebene der Klassenunterteilung gestattet (was die Flexibilität aufgrund der verschiedenen Vererbungsebenen, die in objektorientierten Sprachen gebildet können, einschränkt). Diese Begrenzung der Vererbungsebenen auf eine einzige ähnelt der Herangehensweise, die von AT & T in C++ Language System Release 2.0, Product Reference Manual, 1989, Select Code 307-146 beschrieben wurde. Die von D. Grunwald in "A Users Guide to AWESIME: An Object Oriented Parallel Programming and Simulation Systems", Technical Report CU-CS-552-91, Department of Computer Science, University of Colorado at Boulder, beschriebene Bibliothek läßt benutzerdefinierte Unterklassifizierungen von der in der Bibliothek mit "thread" bezeichneten Aufgabenklasse zu, die Thread-Verwaltung unter Verwendung dieser Bibliothek ist jedoch wiederum explizit. Bei den vielen Versuchen einer Lösung des Problems der fehlenden Möglichkeit einer gleichzeitigen Verarbeitung in C++ durch eine Klassenbibliothek bleiben die Probleme der Objektverteilung über ein Netzwerk, des asynchronen Aufrufens und der künftigen Kommunikation weiter ungelöst.
• Im Protokoll zur International Conference on Computer Languages, Oakland, April 20-23, 1992, Conf. No. 4, April 20, 1992, Pages 331-340 legen Gungseelan et al Distributed Eiffel: a language for programming multi-granular distributed objects on the clouds operating system offen. Diese Sprache bietet einen Schnittstellenmechanismus mit einem ersten Verknüpfungselement zur Entgegennahme eines Prozeduraufrufs sowie ein Element zur Aktivierung einer Datenobjektfunktion für einen zweiten Verarbeitungsvorgang. Diese Sprache arbeitet jedoch in einer Umgebung, für die ein erweiterter objektorientierter Compiler benötigt wird.
• Das Ziel der vorliegenden Erfindung besteht folglich in der Vorstellung eines Mechanismus, der einen gleichzeitigen Ablauf von Operationen ermöglicht, um die Ausnutzung eines Prozessors in einer objektorientierten Rechnerumgebung zu maximieren, und der eine harmonische, implizite Integration von asynchronen Aufrufen und Future-Variablen in eine kompilierte, objektorientierte Sprache wie C++ ermöglicht, ohne daß hierfür Modifikationen am Compiler vorgenommen werden müssen oder eine spezielle Vor-Verarbeitung notwendig ist.
• Dementsprechend wird ein Schnittstellenmechanismus zur Generierung asynchroner Verarbeitungsoperationen vorgestellt, die in einer Rechnerumgebung mit einem licht erweiterten objektorientierten Compiler nach Anspruch 1 ablaufen können.
• Darüber hinaus kann der Schnittstellenmechanismus in einer parallelen Rechnerumgebung, wie in Anspruch 2 beschrieben, genutzt werden.
• In einem dritten Aspekt der Erfindung wird ein Verfahren zur Implementierung asynchroner Verarbeitungsoperationen in eine Rechnerumgebung vorgestellt, das durch mindestens ein erstes objektorientiertes Verarbeitungselement und mindestens zwei mit den separaten Verarbeitungsoperationen verbundene Speichereinrichtungen gekennzeichnet ist, wie in Anspruch 3 beschrieben.
• In einem abschließenden Aspekt der Erfindung wird ein Herstellungsartikel vorgestellt, der ein Element zur Implementierung solcher asynchroner Verarbeitungsoperationen nach Anspruch 4 beinhaltet.
• Nachfolgend werden Ausführungsformen der Erfindung detailliert unter Bezugnahme auf die beiliegenden Zeichnungen beschrieben, die folgendes darstellen:
• Die Fig. 1 und 3 sind Fließdarstellungen, auf denen die Schritte beim Auslösen gleichzeitig ablaufender Verarbeitungsprozesse dargestellt sind; und
• Fig. 2 ist eine schematische Darstellung einer Struktur sowie des funktionellen Betriebs eines Pointer-Mechanismus zum Aufrufen asynchroner Prozesse.
• Die Ausführungsformen der vorliegenden Erfindung wurden für parallele Verarbeitungssysteme, beispielsweise Mehrprozessorsysteme mit einem gemeinsamen oder einem verteilten Speicher, entwickelt. Es ist jedoch beabsichtigt, daß die Erfindung gleichermaßen auf heterogene verteilte Systeme, beispielsweise unter einer DCE-Umgebung, sowie in einer Ein-Prozessorumgebung mit simulierter Gleichzeitigkeit, beispielsweise in einem reaktiven oder interaktiven System, umsetzbar ist.
• Die hierin beschriebenen bevorzugten Ausführungsformen wurden über eine Klassenbibliothek für C++ implementiert. Unter Verwendung der Sprachoperatoren von Deklarationen des Typs "virtual" sowie von "overloading" (dem Mechanismus, mit dem in C++ residente Operatoren neu definiert werden, beispielsweise in einer abgeleiteten Klasse) wird in einen Prozeduraufruf, der von einem auf einem ersten Prozessor installierten Programm ausgeht und an ein Objekt gerichtet ist, dessen Methoden auf einem zweiten Prozessor aktiviert werden können oder müssen, eine Schnittstelle eingefügt. Dieser Schnittstellenmechanismus isoliert dann das Objekt von dem Abrufprogramm in der ersten Verarbeitungsumgebung und ermöglicht die Verarbeitung des Abrufprogramms sowie die gleichzeitige, unabhängige Verarbeitung der Methode des aktivierten Objekts in einer anderen Verarbeitungsumgebung.
• Weiterhin wird das Ergebnis des Aufrufs des Objekts von der zweiten Verarbeitungsumgebung an ein Register zurückgegeben, auf das direkt aus der ersten Verarbeitungsumgebung zugegriffen werden kann, so daß es damit direkt verfügbar ist, wenn es bei einem künftigen Punkt im Abrufprogramm benötigt wird. Wird es im ersten Abrufprogramm niemals benötigt, wird das Ergebnis schließlich aus diesem Register gelöscht.
• Der Prozeß zum Auslösen einer gleichzeitigen oder unabhängigen Verarbeitung ist in der Fließdarstellung von Fig. 1 abgebildet. Im Falle einer Mehrprozessorumgebung aktiviert ein Prozessor, der das Abrufprogramm (Block 10) verarbeitet, eine Methode in einer Klasse, deren Daten in einem entfernten Prozessor (Block 12) abgelegt sind. Dieser Aufruf führt zum Verweis auf einen "asynchronous" oder "smart" Pointer (Block 14), der wiederum die erfindungsgemäße Schnittstelle für Fernaufrufe (Block 16), wie detailliert weiter unten beschrieben, initiiert.
• Eine Template-Klasse in C++ wird zur Definition einer Klasse von "smart pointers" genutzt, die wiederum in einer bevorzugten Ausführungsform zur Aktivierung oder Implementierung eines asynchronen Aufrufs verwendet werden und folglich auch als asynchrone Pointer zu bezeichnen sind.
• (Obwohl die vorliegende Erfindung eine Implementierung der gleichzeitigen Verarbeitung zum Ziel hat, kann jede Verarbeitungsroutine während der freien Zeit mit den normalen Verarbeitungsoperationen fortfahren. Folglich wird jeder Verarbeitungs-Thread so behandelt, als sei er eine asynchrone Operation.)
• Der Begriff der "smart pointers" wurde zunächst in C++ als Speicherverwaltungsmodell eingeführt, das ein Löschen nicht mehr benötigter Datenobjekte aus dynamischen Speichern ermöglicht.
• In der Regel ist ein Pointer eine Variable, die von einem Programm zur Registrierung der Adresse oder des Speicherorts eines Datenfelds mit variablem Ablageort innerhalb eines dynamischen Speichers genutzt wird. Bei traditionellen Implementierungen verweisen "smart pointers" jedoch nicht auf den Speicherort eines tatsächlichen Objekts, sondern auf ein intervenierendes "virtuelles" Objekt, das einen Pointer auf das aktuelle Objekt enthält. Der "smart pointer" kann weitere Informationen enthalten, darunter die Angabe, wie viele andere Pointer auf das aktuelle Objekt verweisen. Diese Angaben sind · als "Schutzschild" gegen ein vorzeitiges Löschen des Objekts nutzbar. Ist die Anzahl der anderen Pointer, die auf das aktuelle Objekt verweisen, gleich Null, kann das Objekt sicher gelöscht werden.
• In der bevorzugten Ausführungsform der vorliegenden Erfindung wird der Template-Mechanismus von C++ zur Definition einer Klasse von "smart pointers" genutzt, darunter einer virtuellen Funktionstabelle, wie sie in Fig. 2 mit der Zahl 30 gekennzeichnet ist. Die in die bevorzugte Ausführungsform implementierte Template-Klasse "AsynCall" enthält eine Reihe virtueller Pointer mit der Bezeichnung "AsyncTask", die alle das Erstellen und Löschen einer Vielzahl unabhängiger oder asynchroner Threads mit eingebauten Sicherungen steuern könnten, um das weiter oben ausführlicher beschriebene vorzeitige Löschen von Threads zu vermeiden. Ein Teil der privaten und öffentlichen Deklarationen dieser AsynCall- Template ist wie folgt definiert:
• Entsprechend der Erfindung wird ein Prozedur- oder Methodenaufruf für einen asynchronen Aufruf von einem Smart Pointer 32 an ein "virtuelles" Objekt ausgegeben, wie dies bei der traditionellen Verwendung von Smart Pointers üblich ist. Der Smart Pointer gibt jedoch keinen Pointer 40 zurück, der auf das Zielobjekt des Aufrufs verweist, sondern ein für sich selbst typisches Objekt mit einem Pointer 31, der auf eine virtuelle Funktionstabelle 34 verweist, wo dieses Objekt die gewünschte Methode aus dem Zielobjekt, der virtuellen Funktionstabelle 36, dadurch aktiviert, daß eine Aufgabe ausgegeben wird, die auf den Pointer 42 der virtuellen Funktionstabelle verweist.
• In einer einzelnen Aufrufebene kann das durch den Pointer vom virtuellen Objekt aus angesprochene Objekt der Smart Pointer selbst sein. Wie in der Template AsynCall oben dargestellt, lassen sich innerhalb der Klasse bis zu 32 asynchrone Aufgaben definieren, die noch immer dem Bereich der anerkannten Parameter einer virtuellen Funktionstabelle zuzuordnen sind, die auch von dem nicht erweiterten Standard-Compiler in C++ genutzt werden kann. In der Fig. 2 repräsentiert der mit einer Klammer versehene Block 33 einer virtuellen Funktionstabelle 34 die einzigen virtuellen Funktionen, die für eine Korrespondenz mit der virtuellen Funktionstabelle 36, die dem Zielobjekt 38 verbunden ist, benötigt werden.
• Im Falle von Mehrfachaufrufen wird der Pointer zu einem Objekt mit einem Nest von Pointern zurückgeführt, wie nach dem Stand der Technik bekannt.
• Bei einem Aspekt der in Fig. 1 dargestellten, bevorzugten Ausführungsform der Erfindung verarbeitet die virtuelle Methode AsynCall den Aufruf am Zielobjekt (Block 18), gibt einen asynchronen Thread aus, damit die Verarbeitung an der aufgerufenen/aktivierten Methode begonnen wird (Block 20), und gibt die Adresse eines "Platzhalters" für das Abrufobjekt (Block 24) zurück. Der zurückgegebene Wert wird vom rufenden Objekt (Block 26) verworfen, und das Abrufprogramm sowie das gerufene Objekt fahren mit der Weiterverarbeitung gemeinsam fort (Blöcke 28 und 22).
• Diese Prozedur produziert deshalb einen "asynchronen" Aufruf, weil die Methoden des Smart Pointer unmittelbar zum Abrufobjekt zurückgeführt werden (Blöcke 18 und 24) und dem abgewickelten Thread die Weiterverarbeitung mit eigener Geschwindigkeit gestatten. Bei einem Parallelcomputer wird durch das Erstellen solcher Threads eine echte Parallelität geschaffen. Bei einigen parallelen Computersystemen wird jedoch durch das Erstellen von Threads keine Parallelität produziert. Statt dessen erfolgt dabei die Einreihung in einer Warteschlange anhängiger Ausgaben. Bei der Implementierung der vorliegenden Erfindung in solch ein System führt jede Methode des Smart Pointer zu der entsprechenden Warteschlangeneinreihung und wird danach sofort zurückgegeben, so daß die Abrufaufgabe weiterverarbeitet werden kann, während der asynchrone Aufruf weiter auf eine auszuführende Aufgabe wartet.
• Nachfolgend ein Beispiel für einen asynchronen Aufruf:
• Obwohl die Methode der asynchronen Aufrufe am nützlichsten bei wirklich parallelen Computern ist, sollte hier festgestellt werden, daß sie auch bei seriellen Computern nutzbringend eingesetzt werden kann. Bei einem seriellen Computer ist es möglich, solche Threads und/oder Tasks zu simulieren, so daß der Programmierer in Fällen, in denen dies sinnvoll ist, logische Parallelität (nicht jedoch echte-Parallelität) ausdrücken kann. Besonders nützlich kann dies in interaktiven oder reaktiven Systemen sein, wo die Fähigkeit des Ausdrückens oder Simulierens von Parallelität den Durchsatz und das wahrnehmbare Ansprechvermögen des Systems verbessern kann.
• Die vorliegende Erfindung gestattet darüber hinaus die Berechnung zukünftiger Werte gleichzeitig mit der Verarbeitung des Hauptprogramms. Dieser Sachverhalt wird in der Fließdarstellung von Fig. 3 illustriert.
• Wie oben erwähnt, wurden in C++ Future-Variablen eingeführt, jedoch nur durch die Verwendung eines Vor-Prozessors, der alle Benutzermethoden umbenennt, so daß der Methodenaufruf abgefangen werden kann. Entsprechend diesem Mechanismus können Future-Variablen nicht dazu genutzt werden, um Ergebnisse unter Anwendung gewöhnlicher Verfahren zu erhalten. Statt dessen muß der Programmierer alle Methoden neu schreiben (in der Regel in einer abgeleiteten Klasse), um zukünftige Referenzargumente erwarten oder künftige Ergebnisse zurückgeben zu können. Diese Implementierung von Future- Variablen ist sehr unbequem und in der Anwendung schwierig.
• Bei der vorliegenden Erfindung wurden Future-Variablen eingeführt, bei denen keine Notwendigkeit eines Vor-Prozessors oder eines erweiterten Compilers gegeben ist. Die oben in bezug auf Fig. 1 beschriebenen Schritte werden bis zu dem Punkt abgearbeitet, an dem ein Wert an das Abrufprogramm zurückgegeben wird, der eine Wiederaufnahme der Verarbeitung gestattet (Block 24 in Fig. 1). Statt der Rückgabe eines zu verwerfenden "Platzhalter"-Wertes gibt der asynchrone Pointer an das Abrufprogramm einen Wert zurück (Block 50 in Fig. 3), jedoch handelt es sich dabei nicht um den erhofften Wert, der aufgrund der Ausführung der Zielmethode am Zielobjekt erwartet wurde. Statt dessen handelt es sich dabei um einen Pointer auf den Thread (oder die Eingabe einer Aufgaben-Warteschlange), dessen Aufgabe die Berechnung dieses Ergebnisses ist.
• In der bevorzugten Ausführungsform der Erfindung wird der Rückgabetyp mit AsyncTask bezeichnet (das heißt, es handelt sich um einen Pointer für eine asynchrone Aufgabe), doch der spezielle Rückgabetyp hängt von dem parallelen Computersystem ab, in das die Future-Variablen implementiert sind. Diese AsyncTask-Pointer sind ein Schlüsselelement im System zur Implementierung von Future-Variablen in diese Art einer Ausführungsform, da der Pointer bei jeder Rückgabe an ein Abrufprogramm im wesentlichen als ein temporärer Platzhalter für jenen Wert dient, der schließlich von einer Zielmethode zurückgegeben wird. Falls das Abrufprogramm keinen Wert benötigt, der aus einer Zielmethode zurückzugeben ist, kann es den an ihn zurückgegebenen AsyncTask-Pointer verwerfen (wie in der Methode aus Fig. 1 vorgeschlagen). Wenn das Abrufprogramm diesen Wert jedoch benötigt, wird er in einem Future-Objekt gespeichert (Blöcke 52 bis 56), der mit einer Future-Template, wie nachfolgend beschrieben, erstellt wurde:
• Die Future-Klasse ist an dem Typ des Wertes parametrisiert, dessen Rückgabe von der Zielmethode erwartet wird, was zeigt, daß eine Future-Variable verwendet wird.
• Dann nutzt ein Verarbeitungsprogramm den von einer asynchron aktivierten Zielmethode zurückgegebenen Wert. Es nutzt den "overloaded" Operator "=", um in einem Future-Objekt jenen Wert zu speichern, der unmittelbar durch den Aufruf der asynchronen Methode zurückgegeben wurde. Der Compiler gestattet, daß das Future-Objekt als Ziel einer solchen Zuordnung verwendet wird, denn der "overloaded" Operator "=" wird eingegeben, um ein Argument desselben Typs zu erwarten, wenn die aufgerufene Methode eingegeben wird. Tatsächlich ist der zurückgegebene Wert jedoch dem Typ AsyncTask zuzuordnen, und im Prinzip wird der Compiler in bezug auf den Typ des vom asynchronen Aufruf zurückgegebenen Pointers getäuscht. Deshalb generiert der Compiler Code zur Aktivierung einer der virtuellen Methoden von AsynCall anstelle der Zielmethode. Wenn die von AsynCall aktivierte Methode anstelle einer Task (Block 64) eine AsynTask zurückgibt und der Future-Objekt- Operator "=" den Compiler dadurch täuscht, daß er ihm mitteilt, das erwartete Argument wäre dem Typ Task zuzuordnen, wenn der Typ des Arguments bekanntermaßen tatsächlich eine AsynCall-Aufgabe ist. Auf diese Art und Weise generiert nahezu jeder unveränderte, nicht erweiterte C++-Compiler Code, welcher Future-Variablen implementiert, der einer harmonisch integrierten Spracherweiterung ähnelt.
• In der bevorzugten Ausführungsform werden Future-Variablen speziell auf die folgende Art und Weise aufgerufen.
• Die erste vom Operator "=" nach dem Aufrufen unternommene Handlung besteht darin, den Typ des Arguments zu berichtigen (AsynTask-Block 52). In der Template-Klasse erfolgt diese Umwandlung mit einer einfachen, programmierbestimmten Datenkonvertierung, in der Praxis sind jedoch auch komplexere Umwandlungen möglich, beispielsweise das Extrahieren des ersten Wortes aus einem aus mehreren Wörtern bestehenden Rückgabewert. Eine solche Umwandlung kann auch in der Größe des zurückgegebenen Wertes verschlüsselt werden, indem man die C++-Größe des Operators auf eine Aufgabe in der Future- Template anwendet.
• Zweitens ordnet der Operator "=" sein konvertiertes Argument einer privaten Variablen zu (Block 54), so daß ein Datensatz erstellt wird, bei dem ein Berechnungsglied für das Generieren des erhofften Ist-Wertes verantwortlich ist, der schließlich aus der Ziel-Methode zurückgegeben wird. Schließlich kehrt der Operator "=" zum Abrufprogramm zurück, wo er eine Referenz auf sich selbst als seinen Rückgabewert gibt (Block 56).
• Nachdem der Operator "=" von seinem Aufruf an ein Future- Objekt zurückgegeben wurde, kann das Abrufprogramm unabhängig weiter ausgeführt werden, ohne auf das von der Zielmethode schließlich zu berechnende Ergebnis warten zu müssen (Block 58). Dieses Ergebnis wird in der Regel jedoch an einem bestimmten Punkt benötigt, und das Future-Objekt repräsentiert ein "Versprechen", es zu liefern. Das Versprechen wird von dem Umrechnungsoperator ("T") erfüllt (das heißt, die Future- Variable wird "gelöst"), wie in der Futures-Template dargestellt. Dieser Operator wird von C++ aufgerufen, wann immer bei Notwendigkeit einer Ablaufsteuerung eine Future- Instanz verwendet wird. Der Umrechnungsoperator führt mehr als eine simple Umrechnung aus; er prüft, ob die Future-Variable aufgelöst wurde (das heißt, der asynchrone Aufruf brachte das erwartete Ergebnis). Falls das Future-Objekt nicht aufgelöst wird, wartet der Umrechnungsoperator auf den Abschluß des asynchronen Aufrufs und veranlaßt gegebenenfalls ein Blockieren des Abrufprogramms (Block 60). Nachdem das Future- Objekt aufgelöst ist, gibt der Umrechnungsoperator den erwarteten Wert zurück (Blöcke 62, 64), und das Abrufobjekt fährt mit seiner Aktivität fort (Block 66).
• Nachfolgend wird die Verwendung von Future-Objekten demonstriert:
• In einem weiteren Aspekt der bevorzugten Ausführungsform wird die Ausgabe des Speichermanagements in seiner Beziehung zu asynchronen Ausgaben behandelt. C++ verfügt über keine eigentlichen Möglichkeiten zur Speicherbereinigung (dynamisches Datenstrukturmanagement). Folglich müssen C++- Programmierer dynamischen Speicher explizit mit den Operatoren "new" und "delete" versehen. In der bevorzugten Ausführungsform werden mit der Verwendung von Future-Variablen an deren Anwender keine speziellen Anforderungen an die Speicherverwaltung gestellt, doch AsynCall und Future- Templates selbst müssen so programmiert werden, daß sie mit Speicher sensibel umgehen. Anders ausgedrückt: Die AsynCall- Template, welche eine asynchrone Aufgabe, die einen asynchronen Methodenaufruf ausführen soll, dynamisch zuordnet, muß so eingerichtet sein, daß später freier Speicherplatz geschaffen werden kann.
• Bei einer Alternative wird die Löschfunktion vom AsynCall- Destruktor wahrgenommen. Der Destruktor wartet auf das Ende der asynchronen Aufgabe, ehe er sie löscht, doch das bedeutet, daß Future-Instanzen zusammen mit den zu ihrer Generierung verwendeten AsynCall-Instanzen gelöscht werden.
• Eine andere, in der Erfindung vorgeschlagene Alternative besteht darin, daß der AsynCall-Pointer die Löschfunktion an die Future-Instanz delegiert, der sein Ergebnis zugeordnet ist. Folglich beinhalten Future-Variablen, die solche Löschungen ausführen, ihre eigenen Destruktoren. Es muß jedoch vorsichtig gearbeitet werden, um die Möglichkeit der Zuordnung zu einer Future-Instanz zu vermeiden (das heißt, das Ergebnis wird verworfen).
• In der in Fig. 2 illustrierten bevorzugten Ausführungsform geben die AsynCall-Methoden einen Pointer 40 zurück, der auf ein Objekt verweist, welches wiederum den asynchronen Task- Pointer 42 enthält. Dieses Objekt könnte auch eine Ganzzahl enthalten, die von der Future-Instanz dazu genutzt wird, um die Übernahme der Löschfunktion anzugeben. Wenn danach der AsynCall-Destruktor aktiviert wird, prüft er zunächst, ob eine Future-Variable die Ausführung der Löschfunktion übernommen hat. Ist dies nicht der Fall, führt er die Löschoperation selbst aus.
• Wenn das Löschen an Future-Variablen delegiert wird, wird die Futures-Template so modifiziert, daß sie einen Kopier- Konstruktor (und möglicherweise weitere private Daten) enthält, um mehrere Kopien von Future-Variablen verwalten zu können. Das Kopieren einer Future-Variable kann entweder durch Zuordnung oder durch Parameterübertragung erfolgen und dürfte in C++ in der Regel kein Problem darstellen. Wenn jedoch das Kopieren gemeinsam mit dem Delegieren eines Löschvorgangs erfolgt, sind Standard-C++-Technologien (beispielsweise Referenzzählung) einzusetzen, so daß die zuletzt gelöschte Kopie einer Future-Variablen die einzige ist, die eine Löschoperation ausführen kann.
• Im Falle von Mehrfachaufrufen (das heißt, beim gleichzeitigen Ausführen mehrerer asynchroner Methodenaufrufe) an einem einzelnen Objekt tritt im Speichermanagement eine Komplikation auf, da viele bzw. alle Aufrufe von einem einzelnen AsynCall- Pointer generiert werden können. Wenn es in der Verantwortung des Pointer liegt, anderenfalls ungebundene Löschungen der Aufgabe vorzunehmen, die er generiert, muß er eine Liste (oder einen anderen Container) mit diesen Aufgaben unterhalten, die sein Destruktor wiederholt abarbeiten kann, um die Löschungen vorzunehmen.
• Die deckungsgleiche Klassenbibliothek der bevorzugten Ausführungsform dieser Erfindung ist derzeit in ein Netzwerk vor Prozessoren des Typs IBM Risse System/6000 integriert, die für die prozessorübergreifende Kommunikation das TCP/IP- Protokoll nutzen (IBM und Risc System/6000 sind Warenzeichen der International Business Machines Corporation). Diese Bibliothek ist mit Ausnahme der wenigen in Assemblersprache geschriebenen Codezeilen in C++ geschrieben. Es wird jedoch jedem Fachmann auf diesem Gebiet klar, daß die deckungsgleiche Klassenbibliothek auf andere Plattformen übertragen werden kann, darunter auch auf verteilte Mehrfach-Speicherprozessoren und Einfachprozessoren mit Funktionen zur Simulierung paralleler Verarbeitungsmöglichkeiten.

Claims (4)

1. Schnittstellenmechanismus zum Generieren asynchroner Verarbeitungsoperationen, die in einer Rechnerumgebung mit einem nicht erweiterten, objektorientierten Compiler und mindestens zwei Speichereinrichtungen, denen separate Verarbeitungsoperationen zugeordnet sind, ausgeführt werden, wobei jede Speichereinrichtung an die Konstruktion von Objektklassen angepaßt wurde und der Mechanismus folgendes umfaßt:

ein erstes Verbindungselement zum Empfang eines Prozeduraufrufs von einer ersten Verarbeitungsoperation in Verbindung mit einer der Speichereinrichtungen sowie zur Ausgabe einer Antwort, mit der die Wiederaufnahme der ersten Verarbeitungsoperation veranlaßt wird, wobei das erste Verbindungselement mit einem Pointer-Mechanismus ausgestattet ist, der einen Platzhalterwert an die erste Verarbeitungsoperation zurückgeben kann, und wobei das erste Verbindungselement darüber hinaus in der ersten Verarbeitungsoperation über Mittel zum Löschen des Platzhalterwertes verfügt;

zumindest ein Register zum Aktivieren einer Datenobjektfunktion für eine zweite Verarbeitungsoperation, und zwar in Verbindung mit einer anderen Speichereinrichtung und neben der ersten Verarbeitungsoperation;

ein Element zum Empfangen und Speichern einer aus der zweiten Verarbeitungsoperation resultierenden Variablen; und

ein zweites Verbindungselement zum Übertragen der resultierenden Variablen an eine der Speichereinrichtungen, die mit der ersten Verarbeitungsoperation verbunden ist, wobei das zweite Verbindungselement folgendes umfaßt:

einen Konverter zum Umwandeln der Antwort des ersten Verbindungselements in eine Future-Wertvariable innerhalb der ersten Verarbeitungsoperation; und

ein Element zum Ersetzen der Future-Wertvariable durch die resultierende Variable aus der ersten Verarbeitungsoperation.

2. Schnittstellenmechanismus nach Anspruch 1 zum Generieren paralleler Verarbeitungsoperationen innerhalb eines einzelnen objektorientierten Programms, das in einer parallelen Rechnerumgebung läuft und mindestens ein erstes und ein zweites Verarbeitungselement, einen nicht erweiterten, objektorientierten Compiler und einen dynamischen Speicher zur Konstruktion von Objektklassen, die mit dem ersten Verarbeitungselement verbunden sind, umfaßt.

3. Verfahren zum Implementieren asynchroner Verarbeitungsoperationen, die in einer Rechnerumgebung ausgeführt werden, welche mit mindestens einem ersten objektorientierten Verarbeitungselement und mindestens zwei Speichereinrichtungen, denen separate Värarbeitungsoperationen zugeordnet sind, ausgestattet ist, wobei das Verfahren folgende rechnerimplementierte Schritte umfaßt:

Empfang eines Prozeduraufrufs von einer ersten Verarbeitungsoperation in Verbindung mit einer der Speichereinrichtungen und Ausgabe einer Antwort, mit der die Wiederaufnahme der ersten Verarbeitungsoperation veranlaßt wird, und zwar durch die Nutzung eines ersten Verbindungselements, wobei dieses erste Verbindungselement einen Pointer-Mechanismus umfaßt, der so eingerichtet ist, daß er einen Platzhalterwert an die erste Verarbeitungsoperation ausgibt, und das darüber hinaus in der ersten Verarbeitungsoperation ein Mittel zum Löschen des Platzhalterwertes umfaßt;

Aktivieren einer Datenobjektfunktion für eine zweite Verarbeitungsoperation in Verbindung mit einer anderen Speichereinrichtung neben der ersten Verarbeitungsoperation durch den Einsatz eines Registers;

Empfang und Speicherung einer resultierenden Variablen aus der zweiten Verarbeitungsoperation;

Übertragung der resultierenden Variablen an die mit der ersten Verarbeitungsoperation verbundene eine Speichereinrichtung durch Einsatz eines zweiten Verbindungselements, wobei dieses zweite Verbindungselement folgendes umfaßt:

einen Konverter zum Umwandeln der Antwort des ersten Verbindungselements in eine Future-Wertvariable innerhalb der ersten Verarbeitungsoperation; und

ein Element zum Ersetzen der Future-Wertvariable durch die resultierende Variable aus der ersten Verarbeitungsoperation.

4. Herstellungsartikel für den Einsatz in einem Computersystem, das zum Implementieren asynchroner Verarbeitungsoperationen dient, die in einer Rechnerumgebung ausgeführt werden, welche mit mindestens einem ersten objektorientierten Verarbeitungselement und mindestens zwei Speichereinrichtungen, denen separate Verarbeitungsoperationen zugeordnet sind, ausgestattet ist, wobei der besagte Herstellungsartikel ein computerlesbares Speichermedium mit einem darauf installierten Computerprogramm umfaßt, das am Computersystem folgendes veranlaßt:

Empfang eines Prozeduraufrufs Von einer ersten Verarbeitungsoperation in Verbindung mit einer der Speichereinrichtungen und Ausgabe einer Antwort, mit der die Wiederaufnahme der ersten Verarbeitungsoperation veranlaßt wird, und zwar durch die Nutzung eines ersten Verbindungselements, wobei dieses erste Verbindungselement einen Pointer-Mechanismus umfaßt, der so eingerichtet ist, daß er einen Platzhalterwert an die erste Verarbeitungsoperation ausgibt, und das darüber hinaus in der ersten Verarbeitungsoperation ein Mittel zum Löschen des Platzhalterwertes umfaßt;

Aktivieren einer Datenobjektfunktion für eine zweite Verarbeitungsoperation in Verbindung mit einer anderen Speichereinrichtung neben der ersten Verarbeitungsoperation durch den Einsatz eines Registers;

Empfang und Speicherung einer resultierenden Variablen aus der zweiten Verarbeitungsoperation;

Übertragung der resultierenden Variablen an die mit der ersten Verarbeitungsoperation verbundene eine Speichereinrichtung durch Einsatz eines zweiten Verbindungselements, wobei dieses zweite Verbindungselement folgendes umfaßt:

einen Konverter zum Umwandeln der Antwort des ersten Verbindungselements in eine Future-Wertvariable innerhalb der ersten Verarbeitungsoperation; und

ein Element zum Ersetzen der Future-Wertvariable durch die resultierende Variable aus der ersten Verarbeitungsoperation.