DE69131500T2 - Regelgesteuertes Transaktionsverwaltungssystem und -verfahren - Google Patents

Description

• Die vorliegende Erfindung betrifft generell verteilte Datenbanksysteme und transaktionsbearbeitende Computersysteme und betrifft insbesondere Verfahren und Systeme, um Berechnungen in verteilten Computersystemen zu synchronisieren.
HINTERGRUND DER ERFINDUNG
• Unter Bezugnahme auf Fig. 1 betrifft die vorliegende Erfindung Wechselwirkungen und wechselseitige Abhängigkeiten von Agenten 102-1 bis 102-N, die in einem verteilt bearbeitenden Computersystem 100 zusammenwirken. Abhängig von dem verwendeten Betriebssystem kann jeder Agent eine Aufgabe oder ein Prozeß sein und ist somit eine Einheit, welche eine Berechnung oder ein Programm ausführt. Einige der Agenten 102-1 bis 102-N können an einer einzelnen gemeinsamen Datenverarbeitungseinheit ausgeführt werden, während andere an entfernten Orten oder anderen Datenverarbeitungseinheiten ausgeführt werden. Generell können Agenten in unterschiedlichen Computersystemen untergebracht sein, die unterschiedliche Betriebssysteme verwenden. Zum Zwecke der vorliegenden Abhandlung ist es ausreichend anzunehmen, daß ein Kommunikationspfad oder -bus 110 vorliegt, welcher sämtliche Agenten in dem System 100 miteinander verbindet.
• Bei einem typischen System 100 werden einige der Agenten Ressourcenmanager sein, wie z. B. ein Datenbankmanagementserver (DBMS), während andere Agenten Berechnungseinheiten sind, die unmittelbar unter den Befehlen von Benutzern des Systemes arbeiten. Für jene, die mit Transaktions(datenbank)-verarbeitwng nicht vertraut sind, ist ein DBMS ein Programm, welches alle Zugriffe auf eine spezifische Datenbank handhabt, wodurch Systembenutzer nicht mit solch komplizierten technischen Problemen befaßt werden, wie die effiziente Speicherung von Daten und das Teilen von Daten mit einer Gemeinschaft an Benutzern.
• In einem Transaktionsverarbeitungs- bzw. -bearbeitungssystem, wie z. B. einem Fluglinienreservierungssystem, werden Agenten dynamisch erzeugt, wenn Anfragen an den Reservierungsterminals erfolgen. Jeder Agent wird durch Teile des Systemes erzeugt, um verschiedene Gesichtspunkte der Arbeit handzuhaben, in Verbindung stehend mit einer spezifischen Anfrage oder Sätzen an Anfragen oder Updates, die durch ein spezifisches Reservierungsterminal gesendet werden.
• Die vorliegende Erfindung betrifft eine generelle Methode zum wechselseitigen Verbinden dieser Agenten 102, um somit Datenkonsistenz aufrechtzuerhalten und um wechselseitige Abhängigkeiten zwischen den Berechnungen zu definieren und zu verstärken, die durch verschiedene der Agenten durchgeführt werden. Beispielhaft kann ein Agent 102-1 eine Anfrage erzeugen, die in der Bildung von zwei abhängigen Agenten 102-2 und 102-3 resultiert, welche jeweils Datenbankschritte in unterschiedlichen Abschnitten der verteilten Datenbank handhaben. Zum Zeitpunkt, zu welchem die zwei abhängigen Agenten 102-2 und 102-3 erzeugt werden, definiert die vorliegende Erfindung exakt, wie diese zwei Agenten wechselseitig abhängig sind und stellt die nötigen Datenstrukturen auf, um diese wechselseitigen Abhängigkeiten anzugeben, wie es im größeren Detail folgend erläutert wird.
• Jeder Agent 102 stellt eine spezifische Berechnung als eine finite Zustandsvorrichtung dar, welche durch eine Folge von internen Zuständen schreitet. Komplexe Berechnungen werden durch deren Agenten in einfachere Sätze von Zuständen aufgeteilt, geeignet zur Synchronisierung mit anderen Berechnungen. Eine typische Folge von Zustands transitionen für einen Agenten ist in Fig. 2 gezeigt. In Fig. 2 gezeigte Definitionen der Zustände 121-127 sind in der Tabelle 1 aufgelistet. TABELLE 1
• Bei einem typischen Transaktionsverarbeitungssystem kann der in einem Agenten laufende Prozeß abgebrochen werden, bedingt durch einen internen Fehlerzustand, und zwar bei einer beliebigen Zeit, bis der Prozeß vorbereitet ist. Typische interne Fehlerbedingungen, welche einen Prozeßabbruch veranlassen können, umfassen "Teilen durch Null", einen Versuch, eine illegale Anweisung durchzuführen, bedingt durch einen Programmierfehler, einen nicht autorisierten Versuch, auf privilegierte Systemressourcen zuzugreifen oder die Nichtverfügbarkeit einer Ressource, die zur Beendigung der Berechnung erforderlich ist. Der Agent ist vorbereitet, dies bedeutet, daß der Agent sicherstellt, daß er die Ergebnisse seiner Berechnung in einer permanenten Weise sichern kann, wenn die verteilte Transaktion übertragen wird, und daß er die Ergebnisse der Transaktion rückabwickeln kann, um somit alles so zu belassen, wie es war, bevor die Transaktion begann, sollte die verteilte Transaktion nicht oder fehlerhaft übertragen werden.
• Die vorliegende Erfindung stellt ein sehr generelles und flexibles System und Verfahren bereit, um Zustandstransitionen in jedem Agenten von dem Zustand anderer Agenten abhängig zu gestalten, die in dem verteilten Prozeß wechselwirken bzw. zusammenwirken.
"STANDARD" ZWEI-PHASEN-ÜBERTRAGUNGSPROTOKOLLE
• Die prototypische Situation, wie in der "transaktionsverarbeitungs"-computertechnischen Literatur diskutiert wird, ist ein verteiltes Datenbankmanagementsystem. Insbesondere besteht ein bekanntes Protokoll, welches bei der Transaktionsverarbeitung verwendet wird, "Zwei-Phasen-Übertragung" genannt, häufig abgekürzt als 2PC. Es bestehen viele Variationen der 2PC, die in kommerziellen Systemen verwendet und/oder in der Literatur abgehandelt werden, wovon einige folgend im Detail diskutiert werden.
• Es ist wichtig zu erwähnen, daß die vorliegende Erfindung nicht lediglich ein Implementierungsverfahren des Zwei- Phasen-Übertragungsprotokolles ist. Ganz im Gegensatz stellt die vorliegende Erfindung ein Verfahren des Definierens und Verstärkens eines breiten Bereiches an wechselseitigen Abhängigkeiten bzw. Beziehungen zwischen zusammenwirkenden bzw. kooperierenden Agenten bereit. Andererseits ist es wichtig zu verstehen, wie zumindest ein Standard-Zwei-Phasen-Übertragungsprotokoll funktioniert.
• Unter Bezugnahme auf Fig. 3 funktioniert eine Standard- Zwei-Phasen-Übertragung wie folgt. Eine Transaktion T1 involviert zumindest zwei Datenverarbeitungseinheiten.
• Beispielhaft kann die Transaktion drei Agenten involvieren, im folgenden Agent A 130, Agent B 132 und Agent C 134 genannt. Unter der Annahme, daß während der Ausführung der Transaktion T1 nichts schiefgeht, führt jeder Agent die der Transaktion zugeordneten Berechnungen durch und speichert neue Werte, die während der Transaktion berechnet wurden, und zwar in solch einer Weise, daß die Transaktion nach wie vor rückgängig gemacht werden oder abgebrochen werden kann, wodurch die Datenbankunverändert verbleibt. Wie es der Fachmann verstehen wird, gibt es eine Vielzahl von unterschiedlichen Verfahren, solche "Rückabwicklungen" durchzuführen, wobei das spezifische Verfahren, welches zum Reversibelgestalten der Transaktionen verwendet wird, für die vorliegende Erfindung nicht von Bedeutung ist.
• Zu einem gewissen Zeitpunkt der Transaktion wird einem der Agenten, hier dem Agenten C, die Rolle des "Koordinators" des Zwei-Phasen-Übertragungsprotokolles zugeordnet. Der Koordinator sendet eine erste Nachricht, Vorbereitungsnachricht 140 genannt, welche alle an der verteilten Transaktion beteiligten Agenten benachrichtigt, daß die Transaktion nun zu beenden ist und hoffentlich übertragen wird. Jeder Agent der Transaktion versucht dann, sich selbst vorzubereiten. Im wesentlichen bedeutet dies, daß der Zustand der Datenbank vor der Transaktion und der Zustand der Datenbank nach der Transaktion in haltbarer Weise gespeichert sind. Der Agent prüft somit, daß einer dieser Zustände garantiert hergestellt werden kann, abhängig davon, ob die Transaktion übertragen bzw. ausgeführt oder abgebrochen wird.
• Jeder Agent wählt dann auf der Disposition der Transaktion aus, mittels Senden einer FERTIG- oder ABBRUCH- Nachricht 142 zurück zu dem Koordinator. Wenn der Versuch eines Agenten, sich vorzubereiten, fehlschlägt, oder wenn ein vorangegangener Schritt der Transaktion fehlschlägt, wählt der Agent ABBRECHEN. Wenn der Versuch, sich vorzubereiten, erfolgreich verläuft, so wählt der Agent FERTIG (d. h. fertig zur Übertragung). Jeder Agent, der FERTIG gewählt hat, wird als vorbereitet angenommen.
• Wenn der Koordinator die Auswahl von allen Agenten erhalten hat, die an der Transaktion beteiligt sind, ist ihm die Disposition der Transaktion bekannt. Der Koordinator ÜBERTRÄGT bzw. FÜHRT die Transaktion DURCH, wenn alle Agenten FERTIG gewählt haben. Wenn ein Agent ABBRUCH gewählt hat oder ein Agent nicht auf die Vorbereitungsnachricht in einer vorbestimmten Zeitperiode antwortet, so bricht der Koordinator die Transaktion ab. In beiden Fällen sendet der Koordinator eine Transaktionsdispositionsnachricht 144 (d. h. ÜBERTRAGEN oder ABBRECHEN) hin zu allen Agenten.
• Wenn ein Agent die Transaktionsdispositionsnachricht erhält, beendet er die Transaktion entsprechend seiner Anweisung. Wenn die Disposition AUSGEFÜHRT bzw. ÜBERTRAGEN wird, installiert der Agent Update-Datenwerte in der Datenbank. Wenn die Disposition ABBRECHEN ist, wird der Zustand der Datenbank vor der Transaktion wiederhergestellt. Die Agenten senden eine Bestätigungsnachricht 146 zurück zu dem Koordinator 134 nach dem stabilen Speichern der Transaktionsdisposition.
• Es sollte erwähnt werden, daß der Agent 134, welcher als Koordinator dient, dieselben Funktionen wie die anderen Agenten während des 2PC-Protokolls ausführt, mit der Ausnahme, daß er das 2PC-Protokoll startet und die FERTIG/ABBRUCH-Wahlen der anderen Agenten sammelt. Des weiteren tritt dieser Agent durch die Vorbereitungs- und Übertragungsphasen der Transaktion. In allen Fällen und für alle Zwecke kann der Koordinator als separate Einheit angedacht sein, obwohl er an dem Knoten des Systemes läuft, der von einem der Agenten besetzt ist.
ANDERE TYPEN VON PROTOKOLLEN UND INTER-AGENTABHÄNGIGKEITEN
• Es sollte erwähnt werden, daß eine Anzahl an Multi- Phasen-Übertragungsprotokollen bekannt sind. Es existiert ebenfalls eine Anzahl an unterschiedlichen Versionen des oben beschriebenen Zwei-Phasen-Übertragungsprotokolles.
• Eine Basiseinschränkung des 2PC-Protokolles, unabhängig von dem spezifischen Typ des verwendeten 2PC-Protokolles bei einem beliebigen System, ist die Tatsache, daß lediglich eine Art an wechselseitiger Abhängigkeit zwischen Agenten vorliegt, d. h. der einzige Typ an wechselseitiger Abhängigkeit in solch einem System ist die "2PC-Art" wechselseitiger Beziehung bzw. Abhängigkeit. Es liegen generell keine Vorkehrungen vor, mehrere Typen an wechselseitiger Abhängigkeit in einem einzelnen verteilten System vorzusehen, wobei ganz sicherlich keine Vorkehrungen getroffen sind, unterschiedliche Typen an Abhängigkeiten zwischen unterschiedlichen Agenten einer einzelnen Transaktion vorzusehen.
• Eine andere grundsätzliche Einschränkung in 2PC-Protokollen besteht darin, daß das 2PC-Protokoll generell angesehen wird als eine einzelne einheitliche Beziehung zwischen einem Satz an zusammenwirkenden Agenten definierend. Die Software zur Handhabung der 2PC-Software ist generell ein Programm der hartverdrahteten Art, welches keine Variation von einer Situation zu einer anderen ermöglicht. Dies gestaltet es eher schwierig, Kommunikationen zwischen zwei Computer- oder Transaktionsverarbeitungssystemen zu bilden, welche unterschiedliche 2PC-Protokolle verwenden.
• Es bestehen jedoch in dem Umfeld von Transaktionsverarbeitung und anderen verteilten Verfahren eine große Anzahl an unterschiedlichen Typen von Interagenten abhängigkeiten, die in unterschiedlichen Situationen verwendbar sind. Zum Beispiel kann es in einigen Fällen lediglich nötig sein, daß ein Agent seine Berechnung fertigstellt, bevor es einem anderen Agenten erlaubt wird, die Fertigstellung durchzuführen. In einem anderen Beispiel können Agenten in solch einer Weise "untergebracht" sein, daß die Art der Abhängigkeit von einem Agenten bezüglich eines zweiten Agenten davon abhängt, ob der zweite Agent seine Berechnung fertiggestellt hat oder seine Berechnung nicht fertiggestellt hat.
• Genereller gesprochen, wäre es unter der Annahme eines gegebenen Satzes an Zustandstransitionen, die für einen spezifischen Agenten definiert werden können, vorteilhaft, in der Lage zu sein, jede dieser Zustandstransitionen abhängig von dem Zustand eines oder mehrerer anderer Agenten zu gestalten. Des weiteren könnte der Satz an Abhängigkeiten zwischen jeder Paarung an Agenten abhängig sein (d. h. unterschiedlich abhängig) bezüglich der Rollen, die diese Agenten in einer spezifischen Transaktion spielen. 2PC stellt keine der erforderlichen Flexibilitäten bereit, um solch eine Vielzahl an unterschiedlichen Abhängigkeiten zu definieren und zu implementieren.
• Der Artikel von J. Eliot und B. Moss "Nested transactions", 1985, MIT Press, Seiten 68-89; "Transaction manager design" beschreibt einen Transaktionsmanagementalgorithmus, in welchem untergebrachte Transaktionen eine Default-Abhängigkeit zwischen Vater- und Kindagent aufweisen, entsprechend einer starken gegenseitigen Übertragungsabhängigkeit, wobei die Abhängigkeit zwischen einem Vater und einem spezifischen Kind in solch einer Weise aufgeweicht werden kann, daß der Vater lediglich überträgt, wenn das spezifische Kind fertiggestellt wird bzw. hat.
ZUSAMMENFASSUNG DER ERFINDUNG
• Zusammenfassend bildet die vorliegende Erfindung ein System und ein Verfahren zum Synchronisieren von Abschnitten einer verteilten Transaktion oder einer anderen verteilten Berechnung, wie definiert in den Ansprüchen 1 und 4. Während der Ver- bzw. Bearbeitung einer Transaktion wird eine Anzahl an Agenten zur Handhabung verschiedener Gesichtspunkte oder Abschnitte der durchzuführenden Berechnungen gebildet. Jeder Agent schreitet durch einen vorbestimmten Satz an Zustandstransitionen, die den Zustand des Agenten zu jedem Zeitpunkt definieren. Die vorliegende Erfindung stellt einen Mechanismus und eine Methode bereit, um die Zustandstransitionen in diesen Agenten von dem Zustand anderer der zusammenwirkenden bzw. kooperierenden Agenten abhängig zu gestalten.
• Das Berechnungsmanagementsystem der vorliegenden Erfindung definiert für jeden Agenten einen Satz von Abhängigkeiten, wobei jede Abhängigkeit einer oder mehrerer Zustandstransitionen entspricht, welche blockiert werden, bis eine entsprechende Zustandstransition in einem anderen spezifischen Agenten auftritt. Mittels Definieren ausgewählter Kombinationen an Abhängigkeiten für jeden Agenten kann eine Vielzahl von unterschiedlichen wechselseitigen Abhängigkeiten und kooperierenden bzw. zusammenwirkenden Protokollen implementiert werden. Das verteilte Bearbeitungsmanagementsystem kann sowohl verwendet werden zum Managen von Transaktionsverarbeitung als auch zum Synchronisieren von Ereignissen in anderen Arten von verteilten Berechnungen.
• Bei der bevorzugten Ausführungsform sind primäre Typen an Abhängigkeiten zwischen Berechnungsagenten: (1) Fertigstellungsabhängigkeit, wobei ein Agent nicht fertigstellen kann, bevor ein anderer spezifischer Agent fertiggestellt oder vor der Fertigstellung abgebrochen hat; (2) starke Übertragungsabhängigkeit, wobei ein Agent nicht übertragen kann, bis ein anderer spezifischer Agent übertragen hat oder zur Übertragung vorbereitet wurde bzw. ist; und (3) schwache Übertragungsabhängigkeit, wobei ein Agent fertigstellt, ein anderer spezifischer Agent nicht übertragen kann, bevor und bis der erste Agent übertragen hat oder zur Übertragung vorbereitet ist.
KURZE BESCHREIBUNG DER ZEICHNUNGEN
• Weitere Aufgaben und Merkmale der Erfindung werden deutlicher beim Lesen der folgenden detaillierten Beschreibung und der beigefügten Ansprüche, unter Bezugnahme auf die beigefügten Zeichnungen, in welchen gilt:
• Fig. 1 ist ein Blockdiagramm eines verteilten Datenverarbeitungssystemes mit einer Anzahl an wechselseitig abhängigen Agenten.
• Fig. 2 stellt schematisch einen Satz an Zustandstransitionen in einem Agenten dar.
• Fig. 3 stellt schematisch das Protokoll dar, welches als Zwei-Phasen-Übertragungsprotokoll bekannt ist.
• Fig. 4 ist ein Blockdiagramm der Komponenten eines Computersystemes, welches die vorliegende Erfindung inkorporiert.
• Fig. 5 stellt Datenstrukturen in einem Agentensteuerblock dar.
• Fig. 6 stellt eine Zustandstabelle dar, verwendet zum Handhaben der Verarbeitung von Nachrichten, die durch einen Agenten, der an einer verteilten Transaktion bei der bevorzugten Ausführungsform teilnimmt, empfangen werden.
• Fig. 7 ist ein Flußdiagramm des Verfahrens zur Handhabung des Empfangens einer Ereignisnachricht.
• Fig. 8 stellt die Symbole dar, die für drei Typen von Interagenten-Abhängigkeiten verwendet werden.
• Fig. 9 stellt ein ebenes Transaktionsmodell dar.
• Fig. 10A-10C stellen drei Typen von aufgenommenen bzw. verschachtelten Transaktionsmodellen dar.
• Fig. 11A und 11B stellen zwei offen verschachtelte untergebrachte Transaktionsmodelle dar.
• Fig. 12 stellt die Agenten einer Transaktion dar, unter Verwendung eines Gemisches aus ebenen und aufgenommenen Transaktionsmodellen.
• Fig. 13A und 13B stellen Agenten und deren wechselseitige Abhängigkeiten für eine Transaktion unter Verwendung eines Ressourcenservers in zwei unterschiedlichen Computereinstellungen dar.
• Fig. 14 stellt Agenten von distinkten Transaktionen dar, jeweils eine distinkte Ressourcenkonfliktauflösungsregel verwendend.
BESCHREIBUNG DER BEVORZUGTEN AUSFÜHRUNGSFORM
• Unter Bezugnahme auf die Fig. 4 und 5 stellt die vorliegende Erfindung ein System und ein Verfahren zum "Normalisieren" unterschiedlicher Anwendungen und anderer Programme bereit, so daß der Zustand von jeder solcher Anwendung und der Übergang der Anwendung durch verschiedene Meilensteine in dem Berechnungsprozeß steuerbar und einem zentralisierten Manager zugänglich ist. Eine andere Betrachtungsweise der Erfindung besteht darin, daß für jedes distinkte Programm oder für jede distinkte Ausführungsaufgabe die Erfindung einen Satz von Zuständen definiert, welcher den Zustand der durchgeführten Berechnung beziffert bzw. beschreibt. Dieser Satz an Zuständen ist typischerweise sehr einfach, da Zustände lediglich für jene Zustandstransitionen definiert sind, welche für den zentralisierten Manager relevant sind. Selbst für ein Datenbankmanagementsystem, welches eine virtuell unbegrenzte Anzahl an möglichen internen Zuständen aufweist, definiert die vorliegende Erfindung einen "Agenten", welcher lediglich eine Handvoll von "Zuständen" aufweist. Demzufolge werden in diesem Dokument die Begriffe "Zustand" und "Zustandstransitionen" bezüglich der vorliegenden Erfindung als Zustände und Zustandstransitionen eines Agenten verwendet, und nicht die internen Zustände und Zustandstransitionen des Anwendungsprogrammes des Agenten.
• Jeder Agent 200-204 besteht in der bevorzugten Ausführungsform aus einem Anwendungsprogramm 210 oder einem mit einem Anwendungsschnittstellenprogramm 214 gekoppelten Ressourcenmanagerprogramm 212, die Zustandsmaschine bzw. -vorrichtung für den Agenten implementierend. Jeder Agent weist ebenfalls einen Nachrichtenpuffer 220 auf, um Nachrichten zu empfangen.
• Eine Ereignissynchronisationseinrichtung 230 umfaßt eine zentrale Steuerung zum Koordinieren (Synchronisieren) von Zustandstransitionen unter den Agenten einer verteilten Berechnung oder Transaktion. Bei der bevorzugten Ausführungsform wird die Ereignissynchronisationseinrichtung 230 Transaktionsmanager genannt, da die Funktionen eines Transaktionsmanagers in dem Transaktionsverarbeitungssystem erfüllt werden. Für jeden Agenten 200 definiert und speichert der Transaktionsmanager 230 einen Steuerblock 232, und zwar in einem Feld von geteiltem Speicher 240. Jeder Steuerblock 232 umfaßt Schlitze 242-256 zum Angeben bzw. Beziffern der folgenden Informationen:
• - Schlitz 241 gibt die Agententransaktionsidentifizierung an, welche eine einzigartige Identifikation ist, dem Agenten zugeordnet bei Erzeugung des Agenten mittels des Transaktionsmanagers 230;
• - Schlitz 242 speichert den aktuellen Zustand des Agenten;
• - Schlitz 243 speichert einen Zeiger zu einer Ressourcenkonfliktlösungsroutine, welche folgend in dem Abschnitt dieses Dokumentes mit dem Titel "Ressourcenkonfliktlösung" abgehandelt wird;
• - Schlitz 244 ist ein Zeiger zu einer Warteliste, welche einen Satz an anderen Agenten darstellt, die auf den Agenten warten, der diesem Steuerblock entspricht;
• - Schlitz 246 ist ein Zeiger zu dem Nachrichtenpuffer 220 des Agenten, welcher es dem Agenten ermöglicht, Nachrichten aufzunehmen, die von dem Transaktionsmanager gesandt sind;
• - Schlitz 248 ist eine Liste sämtlicher Abhängigkeiten zwischen dem diesem Steuerblock entsprechenden Agenten und anderen Agenten;
• - Schlitz 250 ist eine Liste vor Vorbedingungen, die Prädikate sind, die erfüllt werden müssen, bevor eine spezifische Zustandstransition in dem Agenten zur Durchführung freigegeben wird;
• - Schlitz 252 ist eine Liste von Nachbedingungen, welche gepufferte Ereignisnachrichten sind, welche nicht verarbeitet werden konnten, zu dem Zeitpunkt, an dem sie empfangen wurden;
• - Schlitz 254 enthält binäre "Abhängigkeits"-Merker, welche ein schnelles Prüfen der Typen an Abhängigkeiten vereinfachen, welche in der Abhängigkeitsliste 246 vorliegen; und
• - Schlitz 256 ist ein Zeiger zu einer Zustandstransitionstabelle 260, welche wiederum die Unterroutinen 262 angibt, die zum Ansprechen auf jede Art von Nachricht, empfangen durch den Agenten, zu verwenden sind.
• Wenn zum Beispiel die Zustandstransition des Agenten A vom Zustand 1 zu Zustand 2 abhängig ist von dem Agenten B, der einen Zustand C erreicht hat, so wird diese Abhängigkeit in der Abhängigkeitsliste 248 des Agenten A angegeben, wobei die Abhängigkeitsliste des Agenten B einen Punkt enthält, welcher eine negative oder komplementäre Abhängigkeit enthält.
• Die Form der Abhängigkeitsliste 248 ist in Fig. 5 dargestellt. Jeder Gegenstand in der Abhängigkeitsliste 248 des Agenten wird als ein Abhängigkeitstyp und als Identifikation eines anderen Agenten angegeben. Der Abhängigkeitstyp gibt den Typ an Beziehung an zwischen den zwei Agenten, wie z. B. einen Typ an Zustandstransition in dem Agenten, welcher abhängig ist von (d. h. kann nicht verarbeitet werden bis) einer spezifischen Zustandstransition in dem anderen Agenten. Typischerweise wird jede Beziehung zwischen zwei Agenten durch komplementäre Einträge in den Abhängigkeitslisten der zwei Agenten angegeben.
• Jeder Abhängigkeitsgegenstand wird in eine oder mehrere Vorbedingungen übersetzt, wobei entsprechende Einträge in der Vorbedingungsliste 250 erfolgen. Vorbedingungen, die jeder Abhängigkeit entsprechen, sind in der Vorbedingungsliste 250 mittels Auflisten der Zustandstransition angegeben, für welche ein Prädikat definiert ist, der Identifikation des anderen Agenten, von welchem die Zustandstransition abhängt, und des Ereignisses in dem anderen Agenten, welches auftreten muß, bevor es der angegebenen Zustandstransition erlaubt wird, ausgeführt zu werden.
• Nach- bzw. Posttransitionsaktionen sind in den bevorzugten Ausführungsformen Anforderungen, daß der Agent eine Nachricht zu einem anderen Agenten sendet, wenn ein spezifisches Ereignis in dem Agenten auftritt. Bei jeder Zustandstransition untersucht die die Transition durchführende Zustandstransitionsroutine bzw. das die Transition durchführende Zustandstransitionsprogramm die Abhängigkeitsliste 248 und sendet Ereignisnachrichten zu jedem anderen Agenten, welcher abhängig von dieser Zustandstransition ist.
• Wenn eine Ereignisnachricht empfangen wird, bevor der Agent den Zustand erreicht, in welchem er diese Nachricht brauchen würde, wie beispielhaft Empfangen einer Übertragungsnachricht, während der Empfangsagent noch aktiv ist, so wird diese Nachricht als eine Postbedingung in der Postbedingungsliste 252 gespeichert. Jeder Postbedingungsgegenstand beziffert (1) den Zustand oder das Ereignis in dem Empfangsagenten, der erreicht werden muß, bevor die gespeicherte Nachricht verarbeitet werden kann, (2) die Identität des sendenden Agenten und (3) das Ereignis in dem sendenden Agenten. Sobald der empfangende Agent den angegebenen bzw. bezifferten Zustand erreicht, wird die Postbedingung in derselben Weise wie eine empfangene Nachricht verarbeitet (siehe Beschreibung von Fig. 7, weiter unten).
• Einige Abhängigkeitstypen generieren eine Vielzahl von Post- bzw. Nachbedingungseinträgen in der Postbedingungsliste, da der abhängige Agent nicht lediglich wissen muß, ob eine spezifische Normalzustandstransition aufgetreten ist, sondern ebenfalls informiert sein muß, ob ein abnormales Ende aufgetreten ist, was den ersten Agenten zu einem Abbruch veranlassen würde.
• Beispiele von Vor- bzw. Präbedingungen und Post- bzw. Nachbedingungen für spezifische Typen an Abhängigkeiten werden folgend angegeben.
• Der Steuerblock 232 wird für jeden Agenten sowohl durch das Schnittstellenprogramm 214 von jedem Agenten als auch durch den Transaktionsmanager 230 verwendet. Insbesondere untersucht das Schnittstellen- bzw. Interfaceprogramm vor jeder Zustandstransition den Steuerblock 232 des Agenten, um zu bestimmen, ob diese Zustandstransition von einem Ereignis abhängig ist, welches extern bezüglich des Agenten vorliegt (d. h. Abhängigkeit von dem Auftreten eines Ereignisses in einem anderen Agenten). Dies erfolgt einfach durch Abfragen des Steuerblockes, um zu erfassen, ob eine anstehende Vorbedingung vor dieser spezifischen Zustandstransition anliegt. Wenn dies der Fall ist, unterbricht das Schnittstellenprogramm das Anwendungsprogramm des Agenten bis zu solch einem Zeitpunkt, daß sämtliche Vorbedingungen für die Zustandstransition von dem Transaktionsmanager 230 entfernt sind.
• Des weiteren ist das Schnittstellenprogramm 214 von jedem Agenten ansprechend auf Nachrichten von dem Transaktionsmanager, um verschiedene Protokolle durchzuführen, wie z. B. Beginnen einer Berechnung, Abbrechen der Berechnung des Agenten und Beenden einer Transaktion.
• Der Transaktionsmanager 230 ist zum Verstärken von Abhängigkeiten zwischen Agenten verantwortlich, die an einer Transaktion teilnehmen, welche in den Steuerblöcken 232 dieser Agenten beziffert sind. Um dies zu erreichen, generiert der Transaktionsmanager 230 mehrere Fälle eines Transaktionsprozessors 270. Die Transaktionsprozessoren 270 halten die Steuerblöcke 232 der an der Transaktion teilnehmenden Agenten bei und handhaben den Fluß an Nachrichten zu und von den Agenten, wie erforderlich zur kontinuierlichen Verarbeitung der Transaktion.
• Nachrichten, die von jedem Agenten bezüglich Ereignissen in dem Agenten erzeugt werden, werden zu dem Transaktionsmanagernachrichtenpuffer 272 übertragen und dort temporär gespeichert. Wenn eine Transaktionsprozessorinstanz 270 eine Ereignisnachricht von diesem Nachrichtenpuffer 272 auswählt (Schritt 300 in Fig. 7), identifiziert der Transaktionsprozessor 270 den Agenten, an den die Nachricht gerichtet ist, insofern vorhanden (Schritt 302), im folgenden abhängiger Agent genannt. Der Prozessor wählt anschließend eine Transitionsfunktion 262 aus, basierend auf der Zustandstransitionstabelle 260 für den abhängigen Agenten und dem derzeitigen Zustand des Agenten (Schritt 304).
• Unter Bezugnahme auf Fig. 6 ist ein Beispiel einer Zustandstransitionstabelle 260 und ein entsprechender Satz an Transitionsfunktionen (d. h. Unterroutinen) gezeigt. Wie es zu erkennen ist, ist die Art, in welcher eine Nachricht verarbeitet wird, abhängig von dem aktuellen Zustand des abhängigen Agenten. Wenn z. B. ein erster Agent fertig abhängig von einem zweiten Agenten ist, sollte eine Fertignachricht von dem zweiten Agenten über den Transaktionsprozessor 270 empfangen werden, während der erste Agent entweder in dem aktiven oder fertigstellenden Zustand ist. Wenn die Fertignachricht empfangen wurde, während der erste Agent in einem anderen späteren Zustand ist, wird die Fertignachricht entweder einen Fehler darstellen oder eine Fertignachricht von einem ande ren Agenten sein, mit welchem der erste Agent eine unterschiedliche Art an Abhängigkeit aufweist. In beiden dieser Fälle sollte die Fertignachricht ignoriert werden (dies ist, was die TMCER1-Transitionsfunktion erfüllt).
• Unter Bezugnahme auf Fig. 7 führt jede Transaktionsfunktion 262, welche keine Fehlerbedingungsfunktion (fehlerhaft oder fehlerbehaftete Nachrichten handhabend) und keine Funktion ist, die Agenten erzeugt, oder welche die Abhängigkeitsliste in einem Steuerblock modifiziert, wenn von einem Transaktionsprozessor ausgeführt, die folgenden Funktionen aus. Wenn die Nachricht ein Ereignis betrifft, welches verfrüht bzw. vorangehend ist (Schritt 306), indem es erforderlich sein kann, Vorbedingungen bezüglich lediglich eines späteren Zustands zu erfüllen, so wird die Nachricht in der Postbedingungsliste 262 (Schritt 308) gespeichert oder gepuffert.
• Wenn die empfangene Nachricht einer, aktuellen Vorbedingung des empfangenden Agenten (Schritt 310) entspricht, entfernt der Prozessor diese Vorbedingung von der Vorbedingungsliste 260 (Schritt 312). Der Prozessor prüft anschließend, ob eine Zustandstransition vorliegt, die zum Auftreten bereit ist (Schritt 314). Wenn dies der Fall ist, prüft der Prozessor, ob sämtliche Vorbedingungen für diese wartende Zustandstransition erfüllt sind (Schritt 316) und führt die Zustandstransition (Schritt 318) durch, wenn sämtliche Vorbedingungen erfüllt sind. Die Zustandsveränderung erlaubt es dem Agenten, anschließend mit dem nächsten Abschnitt seiner Berechnung fortzuschreiten.
• Nach jeder Zustandstransition in einem Agenten 210 untersucht der Transaktionsmanagerprozessor die Abhängigkeitsliste des Agenten, um zu prüfen, ob eine Posttransitionshandlung durchzuführen ist. Wenn dies der Fall ist, werden Nachrichten zu identifizierten Agenten gesandt, bezüglich des Auftretens der Zustandstransition. Anders ausgedrückt, wenn einer oder mehrere Agenten vorliegen, welche Abhängigkeiten bezüglich der Tatsache aufweisen, daß die Zustandstransition im Schritt 318 stattgefunden hat, so werden Nachrichten zu diesem anderen Agenten im Schritt 320 gesendet. Bestimmte Typen von Zustandstransitionen, wie z. B. eine Transition zu dem Abbruchzustand in einem ersten Agenten A, veranlassen immer eine zu sendende Nachricht (über den Transaktionsmanager), und zwar zu sämtlichen Agenten, welche Abhängigkeiten bezüglich des Agenten A aufweisen.
• Schließlich untersucht der Prozessor die Post- bzw. Nachbedingungsliste 262, um zu bestimmen, ob eine Postbedingung wartend vorliegt für den aktuellen Zustand des Agenten (Schritt 322). Wenn dies der Fall ist, nimmt der Prozessor die älteste Nachricht (Schritt 324) und kehrt anschließend zum Schritt 310 zurück, um diese Nachricht zu verarbeiten.
• Einige Nachrichten sind nicht "Ereignis"-Nachrichten und werden somit anders gehandhabt als mittels des in Fig. 7 gezeigten Verfahrens. Beispielhaft veranlaßt eine ERZEUGEN-Nachricht, daß der Prozessor des Transaktionsmanagers die TMC_CRE-Routine bzw. -Programm ausführt, wodurch ein neuer Agent für die Anwendung erzeugt wird, die die ERZEUGEN-Nachricht erzeugt bzw. generiert hat. Eine FALLENLASSEN-Nachricht veranlaßt den Transaktions-manger, die TMC-DRP-Routine bzw. -Programm auszuführen, welche spezifische Abhängigkeiten von einem Agenten löscht. Eine VERÄNDERN-Nachricht veranlaßt den Transaktionsmanager, die TMC_MOD-Routine zu involvieren, welche Abhängigkeiten bezüglich eines Steuerblocks eines Agenten verändert oder neue Abhängigkeiten bezüglich eines Steuerblocks eines Agenten einführt.
• Die bei der bevorzugten Ausführungsform verwendeten Transaktionsfunktionen sind in Tabelle 2 dargestellt. TABELLE 2
• Die Einträge in der Zustandstransitionstabelle 260 können für jeden Agenten unterschiedlich sein, da die Transitionsunterprogramme bzw. -subroutinen, die von einem Agenten benötigt werden, von den Abhängigkeiten des Agenten abhängen. Anders ausgedrückt, wird ein Agent mit einer starken Übertragungsabhängigkeit von einem oder mehreren anderen Agenten eine unterschiedliche Zustandstransitionstabelle 260 aufweisen als ein Agent, welcher lediglich Fertigstellungsabhängigkeiten bezüglich anderer Agenten aufweist. Der beigefügte Anhang 1 zeigt einen Auszug von Zustandstransitionstabellen für verschiedene Kombinationen an Abhängigkeiten.
SPEZIFISCHE BEISPIELE VON ABHÄNGIGKEITEN
• Die wie oben beschriebene Erfindung kann auf eine beliebige verteilte Berechnung bzw. verteilte Verarbeitungssituation angewendet werden, in welcher ein Bedarf besteht, Zustandstransitionen unter den teilnehmenden Agenten zu koordinieren. Das Folgende ist eine Beschreibung eines Systemes, welches drei Typen an Abhängigkeiten verwendet, und der Möglichkeiten, wie diese Abhängigkeiten für ein Übertragungsprotokoll eines verteilten Transaktionsverarbeitungssystemes verwendet werden können.
• Bei der bevorzugten Ausführungsform ist jeder Agent einer Transaktion als eine finite Zustandsvorrichtung mit den in Fig. 2 dargestellten Zuständen ausgebildet. Des weiteren umfaßt der Satz an Nachrichten, den jeder Agent empfangen kann, und zwar entweder von dem Transaktionsmanager oder einem anderen Agenten, hier als Agent X beziffert:
NACHRICHTENTYP BESCHREIBUNG
• Anfrage erzeugen Fallenlassen Erzeugen einer Abhängigkeitsbeziehung Fallenlassen einer Abhängigkeitsbeziehung
• Fertigstellen Agent X hat fertiggestellt
• Anfrage vorbereiten Empfangender Agent wird zur Vorbereitung aufgefordert
• Vorbereiten Agent X ist vorbereitet
• Übertragung Agent X hat übertragen
• Vergessen Vergessen der Transaktion (nach der Übertragung oder dem Abbrechen)
• Abbrechen Abbrechen der Transaktion
• Versagen Versagen im Agenten X
• Zeitüberlauf Transaktion zeigt Zeitüberlauf
• Rückgängigmachen Rückgängigmachen bzw. Rückabwickeln von Ergebnissen der Berechnung des empfangenden Agenten
• Anfragekonflikt Nachricht von dem Ressourcemanager, die den Transaktionsmanager beauftragt, mögliche Konfliktanfragen bezüglich des Zugriffs auf eine Ressource zu lösen
• In der bevorzugten Ausführungsform wird eine "Vorbereitet"-Nachricht verwendet, um eine Zusage zu befördern: der eine "Vorbereitet"-Nachricht sendende Agent tätigt eine Zusage zur Übertragung, wenn der Empfänger der Vorbereitet-Nachricht überträgt (d. h. der die Vorbereitet- Nachricht sendende Agent ist vorbereitet zur Übertragung oder um abzubrechen). Diese "Vorbereitet"-Nachricht ist äquivalent zu der "Fertig"-Nachricht, die oben unter Bezugnahme auf Fig. 2 beschrieben wurde.
• Unter Bezugnahme auf die Fig. 8 bis 11 werden die drei Typen an Abhängigkeiten, die in der bevorzugten Ausführungsform verwendet werden, im folgenden genannt (1) starke Übertragungsabhängigkeit, symbolartig dargestellt durch einen durchgezogenen Pfeil, (2) schwache Übertragungsabhängigkeit, symbolartig angegeben durch einen gestrichelten Pfeil und (3) fertige bzw. fertiggestellte bzw. Fertig-Abhängigkeit, welche symbolartig angegeben wird durch einen durchgezogenen Pfeil mit einer diesbezüglich senkrecht verlaufenden Linie.
• Eine starke Übertragungsabhängigkeit (SCD) wird wie folgt definiert. Wenn der Agent A stark übertragungsabhängig von Agent B ist, so gilt:
• 1) Der Agent A kann nicht übertragen, bis entweder der Agent B bereits gesendet hat oder der Agent B eventuell überträgt,
• 2) wenn der Agent B abbricht, muß der Agent A abbrechen, und
• 3) wenn der Agent A abbricht, muß der Agent B nicht abbrechen, wenn nicht eine andere Abhängigkeitsbeziehung zwischen den Agenten A und B besteht, die dies erfordert.
• Eine schwache Übertragungsabhängigkeit (WCD) des Agenten A bezüglich des Agenten B erfordert:
• 1) Wenn der Agent B fertiggestellt hat, so wird der Agent A stark übertragungsabhängig von dem Agenten B,
• 2) nachdem der Agent B fertiggestellt hat, muß der Agent A abbrechen, wenn der Agent B abbricht,
• 3) bevor der Agent B fertigstellt, muß der Agent A nicht abbrechen, wenn der Agent B abbricht, und.
• 4) wenn der Agent A abbricht, muß der Agent B nicht abbrechen.
• Wenn der Agent A fertiggestellt-abhängig (FD) von dem Agenten B ist, bevor Agent A fertigstellen kann, muß der Agent B bereits fertiggestellt sein bzw. haben, oder es muß bekannt sein, daß der Agent B nie fertigstellen wird bzw. nie fertig wird.
Benachrichtigungsabhängigkeitstypen.
• Jede Abhängigkeit zwischen zwei Agenten erzeugt eine oder mehrere Vorbedingungen in zumindest einem der Agenten. Für jede solche Vorbedingung in einem Agenten besteht eine entsprechende Benachrichtigungsaktion in dem anderen Agenten. Die Benachrichtigungsaktion ist eine Anforderung, daß eine Nachricht zu senden ist, um eine spezifische Vorbedingung in einem spezifischen Agenten zu erfüllen. Somit erfordert eine Vorbedingung in Agent A, welcher abhängig ist von Agent B, eine Benachrichtigungsaktion in dem Agenten B. Diese Benachrichtigungsaktion, im folgenden eine Benachrichtigungsabhängigkeit genannt, ist involviert, wenn ein entsprechendes Ereignis (d. h. eine Zustandstransition) in dem Agenten B auftritt, wodurch der Agent B veranlaßt wird, eine Ereignisnachricht an den Agenten A zu senden. Wenn z. B. der Agent A fertig- bzw. fertiggestellt-abhängig von Agent B ist, so wird der Agent B eine Benachrichtigungsabhängigkeit von dem Agenten A aufweisen, so daß der Agent B veranlaßt wird, eine "Fertigereignisnachricht" zu dem Agenten A zu senden, wenn der Agent B den fertiggestellten Zustand erreicht. Ferner, wenn der Agent B vor dem Fertigstellen abbricht, wird er eine Abbruchnachricht an den Agenten A senden.
• Wenn der Agent A stark übertragungsabhängig (SCD) von dem Agenten B ist, so wird der Agent B als benachrichtigungsstarkübertragungsabhängig (NSCD) von dem Agenten A angenommen. Anders ausgedrückt, ist eine starke Übertragungsabhängigkeit von dem Agenten B in der Abhängigkeitsliste des Steuerblockes des Agenten A aufgeführt, wobei eine entsprechende benachrichtigungsstarke Übertragungsabhängigkeit von dem Agenten A in der Abhängigkeitsliste des Steuerblockes für den Agenten B aufgeführt ist. In ähnlicher Weise ist eine benachrichtigungsschwache Übertragungsabhängigkeit in dem Steuerblock des Agenten B aufgeführt, wenn ein anderer Agent schwachübertragungsabhängig von dem Agenten B ist, wobei eine Benachrichti gungsfertigabhängigkeit in dem Steuerblock des Agenten B aufgeführt ist, wenn ein anderer Agent fertig abhängig von Agent B ist.
• Diese "Benachrichtigungs"-Abhängigkeiten werden von dem Transaktionsmanager verwendet, um Nach- bzw. Posttransitionsaktionen zu generieren, welche die Übertragung von Nachrichten anfragen, erforderlich zur Implementierung der entsprechenden "positiven" Abhängigkeit. In anderen Worten veranlaßt die Post-Transitionsaktion, entsprechend seiner Benachrichtigungsabhängigkeit, daß eine Nachricht gesendet wird, welche eine Vorbedingung in einem anderen Agenten erfüllen wird. Wenn z. B. der Agent A fertig abhängig von Agent B ist, wird eine Benachrichtigungsfertigabhängigkeit in dem Steuerblock des Agenten B enthalten sein. Als ein Ergebnis, wenn der Agent B den fertiggestellten Zustand erreicht, wird dessen Anwendungsprogrammschnittstelle eine Nachricht übertragen, die das Auftreten des Ereignisses beschreibt bzw. beziffert, was wiederum die Vorbedingungsfertigabhängigkeit des Agenten A von dem Agenten B zufriedenstellen bzw. erfüllen wird.
Ebenes Transaktionsmodell.
• In einem verteilten Transaktionsverarbeitungssystem, welches ein ebenes bzw. flaches Transaktionsmodell verwendet, zeigen alle Agenten einer Transaktion eine wechselseitige bzw. gegenseitige starke Übertragungsabhängigkeit von zumindest einem anderen Agenten, was zu einem Satz an Abhängigkeitsbeziehungen führt, wie in Fig. 9 dargestellt. Dies ist äquivalent zu dem "Standard"-Zwei- Phasen-Übertragungsmodell, welches oben unter Bezugnahme auf Fig. 3 in dem Abschnitt "Hintergrund der Erfindung" beschrieben wurde. Das ebene Transaktionsmodell gestaltet die gesamte Transaktion zu einer atomaren Arbeitseinheit, und zwar sowohl von einem äußeren Gesichtspunkt als auch von einem internen Gesichtspunkt.
Aufgenommenes bzw. verschachteltes Transaktionsmodell.
• In einem Transaktionsbearbeitungssystem mit verschachtelten Agenten liegen Vateragenten und Kindagenten vor, wobei jeder Kindagent typischerweise durch oder für dessen Vateragenten erzeugt wurde. Alle der in den Fig. 10A, 10B und 10C gezeigten Modelle erfordern, daß die Kindagenten vor dem Vateragenten fertigstellen (d. h. daß der Vateragent fertig abhängig von dem Kind ist). Das Modell in Fig. 10A erfordert des weiteren, daß der Kindagent stark übertragungsabhängig von dem Vateragenten ist, und daß der Vateragent schwach übertragungsabhängig von dem Kindagenten ist. Das Ergebnis aller dieser Abhängigkeiten besteht darin, daß die Transaktion als eine atomare Arbeitseinheit von einem äußeren Gesichtspunkt erscheint, jedoch stellt die Transaktion intern keine atomare Einheit für kurze Zeitperioden bereit. Insbesondere, wenn ein Vateragent fertig abhängig und schwach übertragungsabhängig von einem Kindagenten ist und der Kindagent abbricht, muß der Vateragent nicht abbrechen. Die Anwendungssoftware des Vateragenten kann ausgelegt sein, um diese Situation zu handhaben, z. B. mittels Erzeugung eines neuen Kindagenten, oder durch Vornehmen anderer Ausnahmehandhabungsaktionen.
• Es sollte erwähnt werden, daß die Zustandstabelle 260 des Vateragenten, welcher schwachübertragungsabhängig von einem Kindagenten ist, sich während des Laufs einer Transaktion verändern kann. Anfänglich wird der Vateragent über eine Zustandstabelle verfügen, entsprechend einer Fertigabhängigkeit von dem Kindagenten. Zum Zeitpunkt und wenn der Kindagent fertigstellt und eine Fertigereignisnachricht zu dem Vater sendet, wird der Vater stark übertragungsabhängig von dem Kindagenten werden, eine Veränderung in dessen Zustandstabelle fordernd.
• Das verschachtelte Transaktionsmodell in Fig. 10B verfügt über eine Verschachtelung ohne teilweises Rück gängigmachen, was bedeutet, daß dieses Modell dem ebenen Transaktionsmodell entspricht, mit der Ausnahme der Fertigbefehlsanfrage. Schließlich ist das verschachtelte Transaktionsmodell, welches in Fig. 10C gezeigt ist, einfach eine Befehlsanfrage bzw. -anforderung ohne jegliche Übertragungsabhängigkeiten. Dieses letzte Modell wird primär zur Steuerung von Ressourcenaufteilung verwendet.
• Die in den Fig. 11A und 11B gezeigten Modelle sind offen verschachtelte Modelle, welche einen unterschiedlichen Typ an Rückgängigmach- bzw. Rückabwicklungsmechanismus aufweisen müssen als das verschachtelte Modell der Fig. 10A. Insbesondere kann ein Kindagent lange Zeit vor seinem Vater übertragen, was zu einer Transaktion führt, welche keine atomare Arbeitseinheit ist. Ferner können schwache Übertragungsabhängigkeiten verwendet werden, um es zu ermöglichen, daß Systemressourcen so bald wie möglich zur Verwendung für andere Transaktionen freigegeben werden, wobei es einer Vateranwendung ermöglicht ist, sich von einem Fehler zu erholen, der einen Kindagenten veranlaßt, abzubrechen. Gegenseitige bzw. wechselseitige starke Übertragungsabhängigkeiten neigen dazu, Ressourcen zu sperren, bis eine gesamte Transaktion fertiggestellt ist, während schwache Übertragungsabhängigkeiten eine frühere Neuzuordnung von Ressourcen ermöglichen.
• Fig. 12 stellt eine Transaktion dar, welche eine Mischung aus den Ebenen und verschachtelten Modellen verwendet. Dieser Typ an Transaktion kann entstehen, wenn zwei unterschiedliche Typen von Computersystemen, mit unterschiedlichen Transaktionsmodellen, an einer einzelnen Transaktion teilnehmen. Es kann ebenfalls in komplexen Transaktionen in einem einzelnen Computersystem entstehen. In beiden Fällen ermöglicht es die vorliegende Erfindung, daß Agenten, die unterschiedliche Typen an Transaktionsmodellen verwenden, an einer einzelnen Transaktion teilnehmen, und zwar ohne Neuprogrammierung der zugrunde liegenden Übertragungsprotokolle (im folgenden Abhängigkeitsbeziehungen).
• Fig. 13A und 13B stellen Beispiele der Agenten und ihrer wechselseitigen Abhängigkeiten für eine Transaktion dar, wobei ein Ressourcenserver verwendet wird. Jedes Anwendungsprogramm und Ressourcenprogramm verfügt über einen zugeordneten Agenten. Wenn sowohl das Anwendungsprogramm als auch der Ressourcenserver an demselben Knoten bzw. Noden eines Computernetzwerkes vorliegen, wird die in Fig. 13A gezeigte Konfiguration verwendet. Insbesondere, wenn das Anwendungsprogramm einen Ruf zu dem Ressourcenserver tätigt, so wird der XID1-Agent erzeugt, um die Koordinierung der Aktivitäten zwischen dem Anwendungsprogrammagenten und dem Ressourcenserveragenten handzuhaben.
• Wenn das Anwendungsprogramm und der Ressourcenserver an unterschiedlichen Knoten eines Computernetzwerkes vorliegen, wird die in Fig. 13B gezeigte Konfiguration verwendet. Insbesondere sind zwei Agenten XID1 und XID2 in diesem Beispiel erforderlich, um die Aktivitäten des Anwendungsprogrammagenten und des Ressourcenserveragenten zu koordinieren.
• Im folgenden werden Beispiele von Vorbedingungen und Posttransitionsaktionen für spezifische Typen an Abhängigkeiten angegeben.
• AGENT A: STARKE ÜBERTRAGUNGSABHÄNGIGKEIT VON AGENT B: VORBEDINGUNGEN IN DEM AGENTEN A
• Übertragung von A erfordert: Übertragung von Agent B
• POSTTRANSITIONSAKTIONEN VON AGENT B:
• Senden einer Übertragungsnachricht zu Agent B beim Übertragen
• Senden einer Abbruchnachricht zu Agent A beim Abbrechen
• AGENT A: SCHWACHE ÜBERTRAGUNGSABHÄNGIGKEIT VON AGENT B: VORBEDINGUNGEN IN AGENT A
• Übertragung durch Agent A erfordert:
• (Fertigstellung und Übertragung durch Agent B) ODER (Nichtfertigstellung und Abbrechen durch Agent B)
• POSTTRANSITIONSAKTIONEN DURCH AGENT B:
• Senden einer Fertig- bzw. Fertigstellungnachricht zu Agent A beim Fertigstellen
• Senden einer Übertragungsnachricht zu Agent A beim Übertragen bzw. nach Übertragung
• Senden einer Abbruchnachricht zu Agent A beim Abbrechen bzw. nach Abbruch
• AGENT A: FERTIG-ABHÄNGIGKEIT VON AGENT B:
• VORBEDINGUNGEN IN AGENT A
• Fertigstellung durch Agent A erfordert:
• Fertigstellung durch Agent B
• ODER (keine Fertigstellung und Abbruch durch Agent B)
• POSTTRANSITIONSAKTIONEN DURCH AGENT B:
• Senden einer Fertigstellungsnachricht zu Agent A beim Fertigstellen
• Senden einer Abbruchnachricht zu Agent A beim Abbrechen bzw. nach Abbruch
• AGENT A: WECHSELSEITIGE STARKE ÜBERTRAGUNGSABHÄNGIGKEIT MIT AGENT B:
• VORBEDINGUNGEN IN BEIDEN AGENTEN
• Vorbereitung durch diesen Agenten erfordert: (eine Vorbereitungsanfragenachricht von dem anderen Agenten)
• ODER (Transaktionskoordinator = dieser Agent)
• Übertragung durch diesen Agenten erfordert: Übertragung oder Vorbereitetsein durch den bzw. von dem anderen Agenten
• POSTTRANSITIONSAKTIONEN DURCH BEIDE AGENTEN
• - Beim Vorbereiten, wenn der Agent Transaktionskoordinator:
• Senden einer Vorbereitet-Anfragenachricht zu dem anderen Agenten
• Beim Vorbereitetsein, wenn der Agent nicht Transaktionskoordinator ist:
• Senden einer Vorbereitetnachricht zu dem anderen Agenten
• - Beim Übertragen, wenn dieser Agent Transaktionskoordinator ist:
• Senden einer Übertragungsnachricht zu dem anderen Agenten
• - Senden einer Abbruchnachricht zu dem anderen Agenten beim Abbrechen bzw. Abbruch (es ist zu erwähnen, daß Abbruch durch diesen Agenten, nachdem er vorbereitet wurde, nicht initiiert werden kann)
RESSOURCENKONFLIKTLÖSUNG.
• Zum Zwecke der Abhandlung soll unter "Ressource" ein beliebiger Abschnitt eines Computersystemes verstanden werden, welcher von einem Prozess verwendet werden kann. Für die meisten Zwecke kann jede distinkte Ressource erachtet werden als ein Satz von Speicheradressen bzw. Speicherorten, wie z. B. ein Eintrag in einer Datenbank, eine Seite eines Speichers, eine Datei oder eine beliebige andere Einheit, die nicht bezüglich zweier oder mehrerer Prozesse teilbar ist, welche diese Ressource teilen. Ein potentieller Ressourcenkonflikt tritt immer dann auf, wenn ein Agent (oder anderer Prozess) Zugriff auf eine Ressource anfragt, welche bereits durch einen anderen Agenten ver wendet wird. In einigen Fällen kann es akzeptiert werden, dem Agenten gleichzeitigen Zugriff auf eine Ressource zu gewähren, bedingt durch eine hergestellte Beziehung zwischen einem Satz von Agenten, in welchem Fall der potentielle Konflikt dadurch gelöst wird, daß dem Anfragenden erlaubt wird, auf die Ressource zuzugreifen, die von einem anderen Agenten gehalten bzw. gehandhabt wird. In anderen Fällen muß die Anfrage auf Zugriff verweigert werden, wobei der Anfragende auf eine Warteliste gesetzt wird, welche periodisch geprüft wird, um zu bestimmen, ob sich Bedingungen in dem System in solch einer Weise verändert haben, daß die von dem Anfragenden erforderliche Ressource für den Anfragenden zur Verfügung steht (z. B. wenn der Ressourcenhalter bzw. -inhaber die Ressource freigegeben hat und kein anderer Agent eine frühere Anfrage für einen Zugriff übermittelt hat).
• Ressourcenteilung unterliegt Vorbedingungen im wesentlichen in derselben Weise, wie Zustandstransitionen Vorbedingungen unterliegen. Wenn eine spezifische Ressource (z. B. ein Speicherblock bei einer spezifischen Adresse) durch den Agenten A verwendet wird, so ist es erforderlich, daß eine Regel oder ein Prädikat vorliegt, die bzw. das bestimmt, ob es einem anderen Agenten B erlaubt ist, einen Schreib- oder Lesezugriff auf denselben Speicherblock zu tätigen. Bei der bevorzugten Ausführungsform basieren die Vorbedingungen oder Prädikate für solch eine Ressourcenteilung auf dem Vorliegen oder Nichtvorliegen von Abhängigkeiten zwischen dem ersten Agenten, die Ressource zu verwenden, und dem anfragenden Agenten. Dies wird im größeren Detail folgend erläutert.
• Unter Bezugnahme auf Fig. 14 ist in der bevorzugten Ausführungsform jeder Transaktion eine von fünf vordefinierten Ressourcenkonfliktlösungsregeln 350 zugeordnet. In anderen Worten bestehen fünf distinkte Ressourcenkonfliktlösungsregeln 350, wovon jede zum Lösen bzw. Auflö sen eines potentiellen Ressourcenkonfliktes verwendet werden kann.
• Immer wenn ein Ressourcenmanager 204 (siehe Fig. 4) einen potentiellen Ressourcenkonflikt antrifft, sendet er eine Nachricht zu dem Transaktionsmanager 230, um den Transaktionsmanager 230 mit der Lösung des potentiellen Konfliktes zu beauftragen. Diese Nachricht spezifiziert die Transaktionsidentität des Agenten 102-1, welcher zuerst Zugriff auf die Ressource gewonnen bzw. getätigt hat, sowie die Transaktionsidentität des Agenten 102-2, welcher Zugriff auf dieselbe Ressource angefragt hat. Der Transaktionsmanager 230 bestimmt, ob und inwiefern eine der Regeln für diesen Konflikt anwendbar ist, wodurch bestimmt wird, ob Zugriff durch den anfragenden Agenten erlaubt wird, und sendet eine Nachricht zu dem Ressourcenmanager 204, welche angibt, wie der Konflikt zu lösen ist.
• In der bevorzugten Ausführungsform wird der Agent, welcher zuerst auf eine spezifische Ressource Zugriff getätigt hat, alternativ "aktiver Agent" oder "Ressourceninhaber" bzw. "Ressourcenhalter" genannt. Wenn der anfragende Agent ein Teil derselben Transaktion wie der aktive Agent ist, so wird die spezifische Ressourcenkonfliktlösungsregel für die Transaktion zum Einsatz kommen. Wenn der anfragende Agent nicht Teil derselben Transaktion wie der aktive Agent ist (welcher aktuell Zugriff auf die Ressource hat), so wird der Zugriff verneint bzw. abgelehnt und der anfragende Agent wird warten müssen.
• In anderen Ausführungsformen der Erfindung wäre es in einigen Fällen möglich, wenn die zwei Agenten nicht Mitglieder derselben Transaktion sind, daß der Transaktionsmanager eine neue Abhängigkeit zwischen den zwei Agenten erzeugt, wie z. B. eine starke Übertragungsabhängigkeit des anfragenden Agenten 102-2 von dem aktiven Agenten 102-1. Dies würde die Beziehung erstellen, die nötig ist, um einen geteilten bzw. gemeinsamen Zugriff auf eine Ressource zu erlauben. Selbstverständlich kann es erforderlich sein, Einschränkungen bezüglich des Zeitpunkts vorzusehen, an welchem solch eine neue Abhängig-keit von dem Transaktionsmanager generiert werden kann.
• Ein wichtiger Gesichtspunkt der Ressourcenteilung der vorliegenden Erfindung besteht darin, daß die Auswahl einer Konfliktlösungsregel unabhängig von den Prädikaten oder Protokollen ist, die zum Synchronisieren von Ereignissen von dem Ereignissynchronisationssystem verwendet werden. In Transaktionsverarbeitungssystemen bedeutet dies, daß eine Anzahl von unterschiedlichen Ressourcenteilungsanordnungen verwendet werden kann, unabhängig von dem spezifischen Übertragungsprotokoll, welches in einer spezifischen Transaktion verwendet wird, wodurch die Fähigkeit bereitgestellt wird, die Ressourcenteilungsregeln anzupassen, die für spezifische Typen oder Modelle von Transaktionen verwendet werden.
• Jede Regel 350 ist aktuell eine Routine bzw. ein Programm, verwendet von dem Transaktionsmanager, um eine Ressourcenteilungsentscheidung zu treffen. Die fünf Konfliktlösungsregeln, die bei der bevorzugten Ausführungsform bereitgestellt sind, sind wie folgt:
• REGEL 1: Geteilter bzw. gemeinsamer Zugriff durch distinkte Agenten wird nicht erlaubt, bis der aktive Agent überträgt bzw. übertragen hat.
• REGEL 2: Gemeinsamer bzw. geteilter Zugriff wird erlaubt, wenn und lediglich wenn der anfragende Agent stark übertragungsabhängig von dem aktiven Agenten ist.
• REGEL 3: Gemeinsamer bzw. geteilter Zugriff wird erlaubt, nachdem der aktive Agent fertigstellt bzw. fertiggestellt hat (und somit, bevor er überträgt bzw. übertragen hat), wenn und lediglich wenn der anfragende Agent stark übertragungsabhängig von dem aktiven Agenten ist oder eine Kette bzw. Folge von Starkübertragungsabhängigkeiten besteht, welche den anfragenden Agenten indirekt stark übertragungsabhängig von dem aktiven Agenten gestalten.
• REGEL 4: Gemeinsamer bzw. geteilter Zugriff wird zwischen punktweisen Agenten erlaubt, nachdem der aktive Agent fertigstellt bzw. fertig ist (und somit, bevor er überträgt), wenn und lediglich wenn (1) der anfragende Agent stark übertragungsabhängig von dem aktiven Agenten ist oder eine Kette bzw. Folge von Starkübertragungsabhängigkeiten vorliegt, welche den anfragenden Agenten indirekt stark übertragungsabhängig von dem aktiven Agenten gestalten, und (2) sämtliche Agenten, insofern vorliegend, in der Abhängigkeitskette zwischen dem anfragenden Agenten und dem aktiven Agenten fertig bzw. fertiggestellt sind.
• REGEL 5: Gemeinsamer bzw. geteilter Zugriff wird in einer verschachtelten Transaktion erlaubt, nachdem der Ressourcenhalter fertig ist bzw. fertigstellt, wenn und lediglich wenn (1) der anfragende Agent direkt oder indirekt stark übertragungsabhängig von dem Ressourcenhalter ist, und (2) sämtliche Agenten in der Kette an Abhängigkeiten zwischen dem Ressourcenhalter und dem letzten gemeinsamen Vorfahren des anfragenden und des Ressourcenhalters fertig bzw. fertiggestellt sind. In einer verschachtelten Transaktion mit einer Verzweigung von in Beziehung stehenden Agenten ist der "letzte gemeinsame Vorfahre" der zuletzt entfernte Agent, welcher ein Vater von beiden Agenten ist, und zwar direkt oder indirekt.
• Regel 1 ist die einschränkendste, indem sie grundsätzlich Ressourcenteilung bzw. einen gemeinsamen Ressourcenzugriff bis zur Übertragung verneint bzw. verbietet. Regel 2 entspricht generell den Ressourcenteilungsregeln, die in Transaktionsverarbeitungssystemen gemäß dem Stand der Technik, hergestellt von Digital Equipment Corporation und Tandem, verwendet werden. Regeln 3 und 4 sind Ressourcenteilungsregeln für ebene Transaktionsmodelle, welche ein "schnelles Übertragungs"-Protokoll verwenden. Regeln 5 und 6 sind geeignet für verschachtelte Transaktionsmodelle. Wie es der Fachmann erkennen wird, können andere Ausführungsformen der vorliegenden Erfindung eine Vielzahl von anderen Ressourcenkonfliktlösungsregeln verwenden.
ALTERNATIVE AUSFÜHRUNGSFORMEN
• Wie oben beschrieben, generiert jeder Agent in einer verteilten Berechnung "Ereignisse", wenn er durch eine Folge von Zustandstransitionen fortschreitet. Demzufolge werden die Begriffe "Ereignis" und "Zustandstransition" synonym verwendet. Ein verteiltes Berechnungssystem umfaßt einen finiten Satz von zwei oder mehr Agenten, die über ein Kommunikationsnetzwerk verbunden sind. Die aktuelle Bedeutung von Kommunikation zwischen Agenten wird sich zwischen einer Form an Umgebung und einer anderen verändern.
• Die Historie eines Systemes kann vollständig durch eine geordnete Liste an Ereignissen in den Agenten des Systemes beschrieben werden und ist somit ähnlich zu einer "Spur" bzw. einem "Ablaufprotokoll". Korrektheitskriterien für das gemeinsame Verhalten eines Systemes (d. h. einer Gruppe an Agenten) sind bei der vorliegenden Erfindung als Prädikate angegeben. Die Prädikate werden anschließend verwendet, um die nötigen Protokolle herzu leiten, welche von jedem Agenten zu befolgen sind. Generell ermöglichen es Protokolle, daß ein Agent in einen Zustand zu einer Vielzahl von anderen Zuständen übergeht, beschränkt jedoch den Satz an Zuständen, auf welchen der Agent übergehen kann. Die Protokolle oder Prädikate eines Systemes erlauben ein nicht-deterministi-sches Verhalten von Agenten, schränken jedoch dieses Verhalten in solch einer Weise ein, daß bestimmte spezifische Regeln erfüllt werden. Dementsprechend schränkt ein Systemprädikat den Satz an Systemhistorien ein, welcher auftreten kann, erfordert jedoch nicht spezifisch eine spezifische Reihenfolge an Ereignissen. Protokolle, wie z. B. (jedoch nicht diesbezüglich beschränkt) Übertragungsprotokolle, werden mittels Definieren des minimales Satzes an entsprechenden Prädikaten oder Abhängigkeiten zwischen Agenten implizit verstärkt. Bei alternativen Ausführungsformen der Erfindung können Prädikate als Einschränkungen bezüglich möglicher Historien eines Systemes durch die Spezifizierung von z. B. legalen Ereignispfaden oder Konditions/Aktionspaaren ausgedrückt werden.
• Während die vorliegende Erfindung unter Bezugnahme auf einige wenige spezifische Ausführungsformen beschrieben wurde, sollte die Beschreibung als rein illustrativ für die Erfindung angesehen werden und nicht als die Erfindung einschränkend. Verschiedene Modifikationen sind dem Fachmann offensichtlich, ohne daß von dem Umfang der Erfindung wie in den beigefügten Ansprüchen definiert abgewichen wird. APPENDIX I ZUSTANNDSTRANSITIONSTABELLE FÜR ABHÄNGIGKEITEN = NFD ZUSTANDSTRANSITIONSTABELLE FÜR ABHÄNGIGKEITEN = FD ZUSTANDSTRANSITIONSTABELLE FÜR ABHÄNGIGKEITEN = NFD, FD ZUSTANDSTRANSITIONSTABELLE FÜR ABHÄNGIGKEITEN = NSCD ZUSTANDSTRANSITIONSTABELLE FÜR ABHÄNGIGKEITEN = NFD, NSCD ZUSTANDSTRANSITIONSTABELLE FÜR ABHÄNGIGKEITEN = NFD, NSCD ZUSTANDSTRANSITIONSTABELLE FÜR ABHÄNGIGKEITEN = NFD, FD, NSCD ZUSTANDSTRANSITIONSTABELLE FÜR ABHÄNGIGKEITEN = SCD ZUSTANDSTRANSITIONSTABELLE FÜR ABHÄNGIGKEITEN = NFD, SCD ZUSTANDSTRANSITIONSTABELLE FÜR ABHÄNGIGKEITEN = FD, SCD ZUSTANDSTRANSITIONSTABELLE FÜR ABHÄNGIGKEITEN = NFD, FD, SCD
• ZUSTANDSTRANSITIONSTABELLE FÜR ABHÄNGIGKEITEN = Mutual SCD ZUSTANDSTRANSITIONSTABELLE FÜR ABHÄNGIGKEITEN = NFD, FD, NSCD, SCD, Mutual SCD

Claims (6)

1. Verfahren zum Durchführen verteilter Berechnungen in einem Computersystem, wobei die Schritte des von dem Computersystem durchgeführten Verfahrens umfassen:

Bereitstellen eines Satzes von zusammenwirkenden Berechnungsagenten (200, 202, 204), um jede verteilte Berechnung durchzuführen, wobei jeder Berechnungsagent programmiert ist, um durch eine Folge von Zustandstransitionen unter einem vorbestimmten Satz von Zuständen fortzuschreiten; und

Durchführen jeder verteilten Berechnung mittels des Satzes von Berechnungsagenten, die für diese verteilte Berechnung vorgesehen sind, enthaltend Blockieren von spezifischen Zustandstransitionen durch einige Agenten des Satzes von Berechnungsagenten, bis entsprechende Zustandstransitionen in anderen Agenten des Satzes von Berechnungsagenten durchgeführt sind;

gekennzeichnet durch:

Definieren einer Vielzahl von zumindest drei distinkten Prädikaten, die einigen der Berechnungsagenten zugeordnet werden können, wobei jedes distinkte Prädikat angibt (A) eine zugeordnete distinkte Zustandstransitionsabhängigkeit zwischen Zustandstransitionen von ersten und zweiten spezifizierten Berechnungsagenten, einschließlich (B) eine zugeordnete Prädikatsaktion, die durch den zweiten Berechnungsagenten durchgeführt werden muß, bevor eine spezifische Zustandstransition im ersten Berechnungsagenten entblockiert werden kann; und

dynamisches Zuordnen eines Satzes von Prädikaten zu dem Satz von Berechnungsagenten, die jede verteilte Berechnung durchführen, um somit einen entsprechenden Satz an zustandstransitionswechselseitigen Abhängigkeiten zwischen dem Satz von Berechnungsagenten zu definieren, wobei jedes zugeordnete Prädikat aus der Vielzahl von Prädikaten ausgewählt ist, und wobei unterschiedliche Sätze von Prädikaten den Sätzen von Berechnungsagenten für unterschiedliche verteilte Berechnungen zugeordnet sind;

wobei der Durchführungsschritt das Blockieren von Zustandstransitionen von einigen Agenten des Satzes von Berechnungsagenten enthält, und zwar entsprechend den dem Satz von Berechnungsagenten zugeordneten Prädikaten, sowie das Erlauben des Fortschreitens jeder blockierten Zustandstransition, wenn die durch das entsprechende Prädikat angegebene Aktion durchgeführt ist;

wobei der dynamische Zuordnungsschritt umfaßt Speichern von Abhängigkeitsdaten für jeden Berechnungsagenten in zumindest einem Computerspeicher (240), angebend (A) einen ersten Satz von zu blockierenden Zustandstransitionen des Berechnungs-agenten, (B) Vorbedingungen, um es jeder des ersten Satzes von Zustandstransitionen zu ermöglichen, fortgeführt zu werden, (C) einen zweiten Satz an Zustandstransitionen des Berechnungsagenten, welche Vorbedingungen für Zustandstransitionen anderer Berechnungsagenten sind, und (D) die anderen Berechnungsagenten, für welche jede des zweiten Satzes von Zustandstransitionen Vorbedingungen sind;

wobei die Vielzahl von zumindest drei distinkten Prädikaten aus den folgenden Typen ausgewählt ist:

ein gegenseitiges starkes Übertragungsabhängigkeitsprädikat, welches erfordert, daß die spezifischen ersten und zweiten Berechnungsagenten ein geteiltes Berechnungsergebnis nur dann übertragen, wenn die ersten und zweiten Berechnungsagenten gegenseitig übereinkommen, das verteilte Berechnungsergebnis zu übertragen, wobei es ansonsten erforderlich ist, daß die ersten und zweiten Berechnungsagenten das verteilte Berechnungsergebnis nicht übertragen;

ein Fertig-Abhängigkeitsprädikat, welches bestimmt, welcher der spezifischen ersten und zweiten Berechnungsagenten einen entsprechenden Abschnitt der verteilten Berechnung vor dem anderen der spezifischen ersten und zweiten Berechnungsagenten fertigstellen muß;

ein starkes Übertragungsabhängigkeitsprädikat, welches erfordert, daß der spezifische erste Berechnungsagent von dem ersten Berechnungsagenten berechnete Ergebnisse nur dann überträgt, wenn der spezifische zweite Berechnungsagent von dem zweiten Berechnungsagenten errechnete Ergebnisse überträgt; und

ein schwaches Übertragungsabhängigkeits-Prädikat, welches den spezifischen ersten Berechnungsagenten davon abhält, von dem ersten Berechnungsagenten berechnete Ergebnisse zu übertragen, wenn der zweite Berechnungsagent beim Fertigstellen eines Abschnitts der verteilten Berechnung, entsprechend dem zweiten Berechnungsagenten, nachfolgt, und zwar bis der zweite Berechnungsagent von dem zweiten Berechnungs-agenten berechnete Ergebnisse überträgt.

2. Verfahren zur Durchführung verteilter Berechnungen nach Anspruch 1, ferner umfassend:

den Durchführungsschritt, der umfaßt: bei jeder Zustandstransition in jedem der Berechnungsagenten, wenn die gespeicherten Abhängigkeitsdaten angeben, daß die Zustandstransition eine Vorbedingung für Zustandstransitionen von anderen spezifischen Berechnungsagenten ist, das Senden von Nachrichten zu den anderen spezifischen Berechnungsagenten, um mitzuteilen, daß die Zustandstransition stattgefunden hat;

Empfangen der Nachrichten von anderen Berechnungsagenten; und wenn eine Zustandstransition von einem der Berechnungsagenten blockiert ist, Warten auf das Empfangen von Nachrichten, entsprechend den Vorbedingungen, die durch die gespeicherten Abhängigkeitsdaten für die blockierte Zustandstransition angegeben sind, und Freigeben der blockierten Zustandstransition, wenn die Nachrichten, entsprechend den spezifischen Vorbedingungen, empfangen werden.

3. Verfahren zur Durchführung verteilter Berechnungen nach Anspruch 1 oder 2, ferner umfassend:

Bereitstellen von Ressourcen, auf die die Berechnungsagenten zugreifen können;

Bilden einer Vielzahl von distinkten Ressourcenkonfliktlösungsregeln (350), um zu bestimmen, ob spezifischen zwei der Berechnungsagenten es erlaubt werden kann, gemeinsam auf eine der Ressourcen zuzugreifen;

wobei jede der Vielzahl an Ressourcenkonfliktlösungsregeln umfaßt (A) distinkte Abhängigkeitskriterien, die vorbestimmte Zustandstransitionsabhängigkeiten zwischen Zustandstransitionen von beliebigen spezifischen zwei Berechnungsagenten als eine Vorbedingung erfordern, um es den zwei Berechnungsagenten zu ermöglichen, gemeinsam auf beliebige der Ressourcen zuzugreifen; wobei zumindest eine der Vielzahl an Ressourcenkonflikt-lösungsregeln umfaßt (B) Zeitgebungskriterien, um gemeinsamen bzw. geteilten Zugriff auf eine der Ressourcen lediglich dann zu ermöglichen, wenn spezifische Zustandstransitionen aufgetreten sind; und

wenn ein erster der Berechnungsagenten Zugriff auf eine der Ressourcen hat, und ein zweiter der Berechnungsagenten Zugriff auf dieselbe Ressource anfragt, Auswählen einer der Vielzahl an Ressourcenkonflikt-lösungsregeln, insoweit vorhanden, mit Abhängigkeitskriterien, die durch die ersten und zweiten Berechnungsagenten erfüllt sind, und es dem zweiten Berechnungsagenten erlauben, gemeinsam auf die Ressource mit dem ersten Berechnungsagenten zuzugreifen, entsprechend der ausgewählten Ressourcenlösungsregel.

4. Computersystem zur Durchführung verteilter Berechnungen, umfassend:

einen Satz von zusammenwirkenden Berechnungsagenten (200, 202, 204), um jede verteilte Berechnung durchzuführen, wobei jeder Berechnungsagent programmiert ist, um durch eine Folge von Zustandstransitionen unter einem vordefinierten Satz von Zuständen fortzuschreiten;

zumindest einen Computerspeicher (240); und

eine Einrichtung zur Durchführung jeder verteilten Berechnung mit dem Satz von Berechnungsagenten für diese verteilte Berechnung;

wobei der Satz von Berechnungsagenten für jede verteilte Berechnung eine Einrichtung enthält, um Zustandstransitionen durch den Satz von Berechnungsagenten solange zu blockieren, bis entsprechende Zustandstransitionen in anderen des Satzes von Berechnungsagenten durchgeführt sind;

dadurch gekennzeichnet, daß

eine Vielzahl von zumindest drei distinkten Prädikaten vorliegt, welche einigen der Berechnungsagenten zugeordnet werden können, wobei jedes distinkte Prädikat angibt (A) eine zugeordnete distinkte Zustandstransitionsabhängigkeit zwischen Zustandstransitionen von ersten und zweiten spezifischen Berechnungsagenten, enthaltend (B) eine zugeordnete Prädikataktion, welche von dem zweiten Berechnungsagenten durchgeführt werden muß, bevor eine spezifische Zustandstransition in dem ersten Berechnungsagenten entblockiert bzw. freigegeben werden kann; und

daß ein Verteiltberechnungskoordinator (230) vorgesehen ist, um dynamisch einen Satz von Prädikaten dem Satz von Berechnungsagenten zuzuordnen, jede verteilte Berechnung durchführend, um somit einen entsprechenden Satz von Zustandstransitionswechselseitenabhängigkeiten zwischen dem Satz von Berechnungsagenten zu definieren; wobei jedes zugeordnete Prädikat aus der Vielzahl von Prädikaten ausgewählt ist, und wobei unterschiedliche Sätze von Prädikaten den Sätzen von Berechnungsagenten für unterschiedliche verteilte Berechnungen zugeordnet werden;

der Satz von Berechnungsagenten für jede verteilte Berechnung eine Einrichtung (270) enthält, um Zustandstransitionen durch den Satz von Berechnungsagenten entsprechend den dem Satz von Berechnungsagenten zugeordneten Prädikaten zu blockieren;

der Verteiltberechnungskoordinator eine Einrichtung enthält, um es jeder der blockierten Zustandstransitionen zu ermöglichen, fortzuschreiten, wenn die durch das entsprechende Prädikat spezifizierte bzw. angegebene Aktion durchgeführt ist bzw. wird; und daß

der Verteiltberechnungskoordinator eine Einrichtung (250, 252) umfaßt, um in zumindest einem Computerspeicher Abhängigkeitsdaten für jeden Berechnungsagenten zu speichern, angebend (A) einen ersten Satz von Zustandstransitionen des Berechnungsagenten, welcher zu blockieren ist, (B) Vorbedingungen, um es jeder des ersten Satzes von Zustandstransitionen zu ermöglichen, fortzuschreiten, (C) einen zweiten Satz von Zustandstransitionen des Berechnungsagenten, welche Vorbedingungen für Zustandstransitionen von anderen der Berechnungsagenten sind, und (D) die anderen Berechnungsagenten, für welche jede Zustandstransition des zweiten Satzes Vorbedingungen sind;

wobei die Vielzahl von zumindest drei distinkten Prädikaten aus den folgenden Typen ausgewählt ist:

ein wechselseitiges Starkübertragungsabhängigkeitsprädikat, welches erfordert, daß die spezifischen ersten und zweiten Berechnungsagenten ein Ergebnis einer verteilten Berechnung lediglich dann übertragen, wenn die ersten und zweiten Berechnungsagenten wechselseitig der Übertragung der Ergebnisse der verteilten Berechnung zustimmen, wobei ansonsten die ersten und zweiten Berechnungsagenten veranlaßt werden, die Ergebnisse der verteilten Berechnung nicht zu übertragen;

ein Fertig-Abhängigkeitsprädikat, welches bestimmt, welcher der spezifischen ersten und zweiten Berechnungsagenten einen entsprechenden Abschnitt der verteilten Berechnung vor dem anderen der spezifischen ersten und zweiten Berechnungsagenten fertigstellen muß;

ein Starkübertragungsabhängigkeitsprädikat, welches erfordert, daß der spezifische erste Berechnungsagent von dem ersten Berechnungsagenten berechnete Ergebnisse lediglich dann überträgt, wenn der spezifische zweite Berechnungsagent von dem zweiten Berechnungsagenten berechnete Ergebnisse überträgt bzw. übertragen wird; und

ein Schwachübertragungsabhängigkeitsprädikat, welches den spezifischen ersten Berechnungsagenten von der Übertragung von durch den ersten Berechnungsagenten berechneten Ergebnissen abhält, wenn der zweite Berechnungsagent beim Fertigstellen eines Abschnittes der verteilten Berechnung, entsprechend dem zweiten Berechnungsagenten, nachfolgt, und zwar bis der zweite Berechnungsagent durch den zweiten Berechnungsagenten berechnete Ergebnisse überträgt.

5. Computersystem nach Anspruch 4, ferner umfassend:

den Verteiltberechnungskoordinator, welcher Mittel umfaßt, um auf jede Zustandstransition in jedem der Berechnungsagenten anzusprechen, wenn die gespeicherten Abhängigkeitsdaten angeben, daß die Zustandstransition eine Vorbedingung für Zustandstransitionen durch andere spezifische der Berechnungsagenten ist, und zwar mittels Senden von Nachrichten zu dem anderen spezifischen der Berechnungsagenten, diesen andeutend, daß die Zustandstransition stattgefunden hat;

wobei jeder der Berechnungsagenten Mittel enthält, um die Nachrichten von anderen der Berechnungsagenten zu empfangen, und um auf empfangene Nachrichten zu warten, entsprechend den Vorbedingungen, die durch die gespeicherten Abhängigkeitsdaten spezifiziert sind, wenn eine Zustandstransition durch den Berechnungsagenten blockiert ist, und um es der blockierten Zustandstransition zu ermöglichen, fortzuschreiten, wenn die Nachrichten, entsprechend den spezifischen Vorbedingungen, empfangen sind bzw. werden.

6. Computersystem nach Anspruch 4 oder 5, ferner umfassend:

Ressourcen, auf die die Berechnungsagenten zugreifen können; eine Vielzahl von distinkten Ressourcenkonfliktlösungsregeln (350), gespeichert in dem zumindest einen Computerspeicher, um zu bestimmen, ob es beliebigen zwei spezifischen Berechnungs-agenten erlaubt ist, gemeinsam auf eine der Ressourcen zuzugreifen;

wobei jede der Vielzahl an Ressourcenkonflikt-lösungsregeln (350) umfaßt (A) distinkte Abhängigkeitskriterien, die vorbestimmte Zustandstransitionsabhängigkeiten zwischen Zustandstransitionen von beliebigen spezifischen zwei Berechnungs-agenten als eine Vorbedingung erfordern, um es den zwei Berechnungsagenten zu ermöglichen, gemeinsam auf eine der Ressourcen zuzugreifen bzw. eine der Ressourcen zu teilen; wobei zumindest eine der Vielzahl an Ressourcenkonfliktlösungsregeln enthält (B) Zeitgebungskriterien, um gemeinsamen Zugriff auf eine der Ressourcen lediglich dann zu erlauben, wenn spezifische Zustandstransitionen auftreten bzw. aufgetreten sind; und

wobei der verteilte Berechnungskoordinator Ressourcenkonfliktlösungsmittel (204) umfaßt, wobei die Ressourcenkonfliktlösungsmittel eine der Vielzahl von Ressourcenkonfliktlösungsregeln, soweit vorhanden, auswählt, mit Abhängigkeitskriterien, die durch die ersten und zweiten Berechnungsagenten erfüllt werden, und dem zweiten Berechnungsagenten gemeinsamen Zugriff auf eine Ressource mit dem ersten Berechnungsagenten, entsprechend der ausgewählten Ressourcenlösungsregel, erlaubt bzw. gewährt, wenn der erste der Berechnungsagenten Zugriff auf eine der Ressourcen hat und der zweite der Berechnungsagenten Zugriff auf dieselbe Ressource anfragt.