DE2101949A1 - Verfahren zum Schutz von Datengruppen in einer Multiprocessing-Datenverarbeitungsanlage - Google Patents

Description

WESTERN ELECTRIC COMPANY Incorporated Martin, R. L.

New YoBk, N. Y., 10007, VStA

Verfahren zum Schutz, von Datengruppen in einer Multiprocessing-Datenverarbeitungsanlage

Die Erfindung betrifft ein Verfahren zur Verhinderung eines unerwünschten gleichzeitigen Zugriffs durch zwei oder mehrere Verarbeiter zu einem einzigen Datenblock, dem ein Sperrwort zugeordnet ist, in einer aufgabenorientierten Multiprocessing-Datenverarbeitungsanlage mit dem Verfahrensschritt: Prüfung von Sperrwörtern die Datenblöcken zugeordnet sind, zu welchen bei einer Aufgabe ein Zugriff erfolgen soll", darauf, auf ob Datenblöcke gesperrt oder entsperrt sind.

Bei der Lösung von komplizierten Problemen, insbesondere von Problemen, bei denen eine Realzeit-Verarbeitung erforderlich ist, werden in imm er größerem Umfang Multi -ζ. processing-Datenverarbeitungsanlagen benutzt. Wenn mehr als ein Verarbeiter in einer Datenverarbeitungsanlage zur Verfugung steht, so können mehrere Programme gleichzeitig laufen. Dies ermöglicht sowohl eine parallele als auch eine serielle Verarbeitung. Die parallele Verarbeitung

läßt eine gleichzeitige Ausführung mehrerer getrennter Funktionen zu. Die serielle Verarbeitung beinhaltet die Auftrennung einer einfeigen Punktion in bestimmte , "Aufgaben" ("tasks") genannte Teile, die gleichzeitig ausgeführt werden.

209846/0964"

Die in der Hauptsache zur Ausführung dieser beiden Verarbeitungstypen vorgesehene Bauteilkonfiguration ist so ausgelegt, daß jeder Verarbeiter Zugriff zu jeder Speichereinheit in der Anlage hat. Dadurch wird eine maximale Wechselwirkung zwischen den Verarbeitern ermöglicht und die Betriebsmöglichkeiten werden verbessert. Leider kann eine solche maxifc male Wechselwirkung auch sehr nachteilige Folgen

haben. Die meisten Realzeit-Funktionen lassen sich nicht auf sinnvolle Weise in unabhängige Aufgaben unterteilen. Dies bedeutet, daß eine beträchtliche Wechselwirkung zwischen Aufgaben wahrscheinlich ist, da beispielsweise mehrere Aufgaben häufig die gleichen Datenblöcke benutzen. Der Ausdruck "Datenblock" soll dabei benachbarte oder nicht benachbarte Folgen von gespeicherten Datenwörtern bedeuten, die den gleichen logischen Zusammenhang

haben. Eine Schwierigkeit kann dann auftreten,

wenn bei zwei oder mehreren Aufgaben gleichzeitig ein Zugriff zu einem Datenblock erfolgt. So kann ein D atenblock als Kette benutzt werden, die eine Liste von sequentiell auszuführenden Aufgaben enthält. Wenn zwei Verarbeiter gleichzeitig einen Zugriff zu dieser Kette vornehmen, dann kann es

geschehen, daß beide die gleiche Aufgabe aufnehmen. Wenn umgekehrt beide/¹ Verarbeiter gleichzeitig eine Eintragung zu der Kette hinzufügen,

209846/09 6 4

dann würde der eine Verarbeiter die Eintragung des anderen Verarbeiters zerstören. Eine Verwirrung kann auch dann auftreten, wenn Datenblöcke zur Speicherung von Rechenergebnissen benutzt werden, da die Möglichkeit besteht, daß bei einer Aufgabe ein Datenblock gelesen wird, während bei einer anderen Aufgabe der Datenblock auf den neuesten Stand gebracht wird.

Bekannte Lösungen dieser Probleme sehen die Verwendung von Programm-"Sperren" vor. Diese "Sperren" umfassen bestimmte Bits in einem bestimmten Wort jedes Datenblockes. Das Sperrwort jedes Datenblockes muß durch eine Aufgabe geprüft werden, bevor bei dieser Aufgabe ein Zugriff zu dem Datenblock erfolgt. Ein bestimmtes Bit-Muster, beispielsweise nur Null-Werte, in dem Sperrwort gibt an, daß im Augenblick kein Zugriff zu dem Datenblock erfolgt. Ein zweites Bitmuster, beispielsweise nur Eins-Werte, gibt an, daß im Augenblick durch eine andere Aufgabe Daten in den Datenblock eingeschrieben oder aus ihm gelesen werden.

Diese einfache Benutzung von Sperrwörtern stellt keine vollständige Lösung der Probleme bezüglich einer fehlerhaften Aufgab en Wechselwirkung in einem

209846/0964

Multiprocessing-System dar. Es besteht die Möglichkeit, daß während des Zeitraumes, den ein Verarbeiter benötigt, um ein Sperrwort zu prüfen, festzustellen, daß es nur Null-Werte enthält, und es auf nur Eins-Werte einzustellen, ein oder mehrere weitere Verarbeiter das Sperrwort ebenfalls prüfen und nur Null-Werte vorfinden, da der erste Verarbeiter die Sperre noch nicht gesetzt hat. In diesem Fall findet ein gleichzeitiger Zugriff durch mehrere Verarbeiter zu dem Datenblock statt, wobei jeder Verarbeiter glaubt, daß er die alleinige Steuerung besitzt.

Zur Beseitigung dieser Schwierigkeit sind in bekannter Weise besondere Befehle zur Prüfung von Sperrwörtern entwickelt worden. Diese speziellen Befehle lassen sich in zwei Kategorien unterteilen, nämlich Abrufbefehle und Speicherbefehle.

Ein spezieller, für die Sperrung von Daten geeigneter Abrufbefehl ist der Abruf- und Belegungsbefehl FBN Cfetch and_bias ^negative) . Wenn ein Verarbeiter den Befehl FBN interpretiert, wendet er einen Abrufbelegungsbefehl zu der jeweiligen Speichereinheit. Die Speichereinheit ruft dann in einem Betriebszyklus das Wort aus der adressierten Stelle ab, belegt es durch Einschreiben von Eins-Werten in seine Sperrbits mit Hilfe

209 8 46/0964

einer ODER-Funktion und gibt das möglicherweise geänderte Wort in den Speicher zurück. Das Wort wird so, wie es vor der Änderung war, zum Verarbeiter gegeben. Die Aufgabe muß dann die Sperr-Bits des empfangenen Wortes prüfen. Wenn die Sperr-Bits alle den Wert Eins haben, so zeigt dies, daß, falls kein Fehler vorliegt, eine andere Aufgabe diesen speziellen Datenblock benutzt. Wenn die Sperr-Bits alle den Wert Null haben, so zeigt dies, falls kein Fehler vorliegt, daß keine andere Aufgabe den Datenblock verwendet. Selbst wenn die Sperr-Bits des vom Verarbeiter empfangenen Wortes alle dem Wert Null haben, so ist der Datenblock im Augenblick ■gesperrt, da der Befehl FBN automatisch die Sperr-Bits beim Lesen des Wortes einstellt. Da diese automatische Sperrung innerhalb eines einzigen Speicherzyklus stattfindet, ist es nicht möglich, daß zwei oder mehrere Aufgaben gleichzeitig einen Datenblock sperren.

Ein spezieller, für die Sperrung von Daten geeigneter Speicherbefehl ist das bedingte Belegungsspeicherkomando BCS (biased conditional store). Dieses Kommando arbeit auf ähnliche Weise wie das Kommando FBN mit der Ausnahme, daß die Einspeicherung nur dann stattfindet, wenn die Sperr-Bits des Objektwortes nicht auf den Wert eins eingestellt sind. Es muß ein Abruf-

209846/0904

befehl nach dem Befehl BCS benützt werden, um sicherzustellen, daß die Einspeicherung stattgefunden hat. Das Kommando BCS gibt dem Programmierer die Möglichkeit, Informationen zu dem Zeitpunkt in das Sperr wort einzugeben, in welchem der Datenblock gesperrt wird. Dies ist insbesondere von Vorteil, wenn eine Unterbrechung gerade dann auftritt, wenn der Datenblock gesperrt wird.

Die beiden oben erläuterten Befehle stellen ein unzweideutiges Hilfsmittel zur Sperrung von Datenblöcken dar, bewirken jedoch leider von sich aus keine vollständige Lösung des Problems eine r gegenseitigen Störung von Aufgaben. Es besteht also weiterhin ein Problem darin, daß die Sperren in Wirklichkeit nur Anzeigen darstellen, die nicht unbedingt einen Zugriff zu einem Datenblock verhindern können. So besteht beispielsweise die Möglichkeit, daß andere Aufgaben die Sperr-Bits nicht beachten und einen Zugriff zu dem als gesperrt angenommenen Datenblock veranlassen.

Selbst wenn die Sperr-Bits beachtet werden, können sich Probleme dann ergeben, wenn die Datenblocksperre nicht zentral gesteuert wird. Es sei beispielsweise angenommen, daß die Aufgabe Pl den Datenblock Dl zum Zeitpunkt Tl sperrt und versucht, den Datenblock

209846/0984

eingegangen

D2 zu einem späteren Zeitpunkt zn sperren. Wenn eine Aufgabe P2 vorhanden ist, die dan Datenblock D2 zum Zeitpunkt Tl sperrt und versucht, den Datenblock Dl zu einem späteren Zeitpunkt zu sperren, dann kann eventuell eine Totalsperrung auftreten, bei der Tl auf die Entsperrung von D2 und P2 auf die Entsperrung von Dl wartet. Dann sind nicht nur Bl und P2 dauernd ausgesetzt, sondern es sind auch Dl und D2 dauernd gesperrt.

Ein Datenblock kann auch dadurch dauernd gesperrt werden, daß eine Aufgabe ihn nicht entsperrt. Dies kann aufgrund einer sorglosen Codierung geschehen, dadurch daß keine Entsperrangaben in den Unterbrechungsansprechcode eingegeben werden, oder durch eine nichtgeplante Aufgabenausführung, die durch einen Bauteil- oder Programmierter verursacht wird.

Die gegenseitige Störung von Aufgaben bringt auch das Problem mit sich, wie verfahr en»verden soll, wenn eine Aufgabe „ ; ' bei dem Versuch -einmDatmöodczu sperren?^*^ -bereits..gesperrt^vor-

die Aufgabe
n und oatfed

ie Aufgabe
und oatfernd ν ersuchen, den Datenblock zu

sperren, soll sie sich abwenden, irgendetwas anderes tun und dann einen erneuten Versuch vornehmen, oder

209846/0964

⁸ geändert eemSB Eingabe eingegangen aa ^--» -äs«.

soll sie einfach aufhören und die augenblickliche Arbeit fallenlassen?

Es dürfte demgemäß klar sein, daß die bekannten Lösungen nicht erfolgreich hinsichtlich eines unerwünschten gleichzeitigen Zugriffs zu einem einzigen Datenblock waren, ohne daß dabei die oben erläuterten weiteren Schwierigkeiten auftreten.

Die Erfindung hat sich demgemäß die Aufgabe gestellt, einen unerwünschten gleichzeitigen Zugriff zu einem einzigen Datenblock zu verhindern, ohne daß dadurch andere Probleme geschaffen und andere Hilfsmittel der Anlage in größerem Umfang benutzt werden, während gleichzeitig die für das Ausführungs- und Überwachungsverfahren benötigte Zeit minimal gehalten wird.

Zur Lösung diesem ae geht die Erfindung aus von dem Verfahren der eingangs genannten Art und ist gekennzeichnet durch die Verfahrensschritte: Sperren jedes Datenblockes, zum dem bei einer Aufgabe ein Zugriff erfolgen soll, unmittel vor und als Voraussetzung für die Ausführung der Aufgabe; Entsperren jedes Datenblockes, der vor Ausführung der Aufgabe gesperrt worden ist und nach Ausführung der Aufgabe gesperrt bleibt.

2098Λ6/096Λ

Auf diese Weise kann die Datenblock-Integrität in einer Multiprocessing-Datenverarbeitungsanlage sichergestellt werden, ohne daß irgendein Datenblock dauernd gesperrt oder, irgendeine Daten- · Verarbeitungsfunktion dauernd verhindert ist.

Nachfolgend wird die Erfindung anhand der Zeichnungen näher beschrieben, es zeigen:

Fig. 1 und 2 graphische Darstellungen von Datenblöcken, die bei dem erfindungsgemäßen

Verfahren benutzt werden; Fig. 3, 4, 5, 6A, 6B bildliche Darstellungen des

erfindungsgemäßen Verfahrens.

Die Erfindung ist in einem Multiprocessing-Planungsverfahren verwirklicht, das bestimmte Aufgaben einzelnen Verarbeitern zuordnet. Eine Aufgabe wird erst dann einem Verarbeiter zur Ausführung zugeordnet, wenn allen, der Ausführung vorangehenden Bedingungen genügt worden ist. Bei dem Planungsverfahren werden die Datenblock-Sperrerfordernisse für jede Aufgabe als ein Typ von vorher zu genügenden Bedingungen benutzt. Das Planungsverfahren stellt das einzige, dem Benutzer der Anlage zur Verfügung stehende Mittel zur Sperrung

9846/0964

und Entsperrung von Datenblöcken dar, und es wird entsprechend einer vorbestimmten Prioritätsrangfolge ausgeführt, wodurch die Möglichkeit einer Wechselwirkung zwischen Aufgaben durch eine Datenblocksperrung ausgeschaltet wird .

Das erfindungsgemäße Verfahren kann mit besonderem Vorteil in einer Datenverarbeitungsanlage entsprechend der eigenen älteren Patentanmeldung P 14 99 288. 2-53 (US-Patent 3 348 210) angewendet werden. Dieser Anlagentyp enthält eine Vielzahl von Verarbeitungseinheiten, besondere Abruf- und Speicherbefehle, die als Datensperrbefehle brauchbar sind, und Einrichtungen zur Durchführung einer Aufgabenzuordnung.

Die Einrichtungen zur Aufgabenzuordnung umfassen ein Aufgabenzuordnungs-Unterprogramm, bei dem Aufgabenzuordnungswörter benutzt werden, um sequentiell Aufgaben bestimmten Verarbeitern in der Reihenfolge zuzuteilen, in welcher die Verarbeiter ihre vorhergehenden Aufgaben beenden. Die Aufgabenzuordnungswörter enthalten in typischer Weise eine Vielzahl von bedingten Betätigungsbits und ein absolutes Betätigungsbit. Wenn eine gegebene Aufgabe als vor ihrer Ausführung zu erfüllende Bedingung die Verarbeitung einer oder mehrerer weiterer Aufgaben erfordert,

209846/0964

Einfügung I φΙΗ^αΐΚβη QIIlJt ²· "⁷^ ■'*

(Einzuschieben nach Zeile 13 auf 2101949 Seite 10 der ursprünglichen Beschreibung)

Anhand von Figur 7, die mit Figur 1 der älteren Patentanmeldung identisch ist, soll zur Erleichterung des Verständnisses eine solche Datenverarbeitungsanlage kurz erläutert werden. Es ist dort ein spezielles Ausführungsbeispiel einer digitalen Echtzeit-Datsnverarbeitungsanlage dargestellt, in der ein Festwertspeicher 10 für Programme und ein Speicher für Daten und Aufgabenanweisungsbefehle (Operand) vorgesehen sind, wobei beide Speicher je in eine Mehrzahl von Speichermodulen 11, bzw. 31 unterteilt sind. Zwei Schalteinheiten 40 dienen in der Anordnung zur jeweiligen Digitalinformationsübertragung zwischen den SpeichermodBlen 11 und 31 und N identischen Datenverarbeitungseinheiten 20^ bis 2OjJ. Jede Datenverarbeitungseinheit 20 enthält ihrerseits einen Digitalspeicher 21 mit relativ begrenzter Speicherkapazität, ferner einen Befehlsstellenzähler 22, eine aritmetische Einheit 23 und einen nicht synchronisierten Taktgeber 24. Demgemäß ist jede der Datenverarbeitungseinheiten 20 eine vollwirksame Recheneinheit, die in der Lage ist, auf gespeicherte Daten hin in einer Weise zu arbeiten, die durch die gespeicherten binären Befehle bestimmt ist.

Die binäre Information wird zwischen einer Informations-Eingangs- Ausgangseinheit 15 und dem Operandspeicher 30 auf dynamischer Echtzeit-Basis über die Schalteinheit 40p und eine Eingabe- Ausgabe-Steuereinheit 18 übertragen. Der Festwertspeicher 10 hat einen fixierten Programminhalt, der mit Hilfe einer

209846/0964

m> eingegangen am...„^^.ii;

Β« Programmeingabeeinheit über die Schalteinheit 40^ gesetzt

Schließlich ist in der Datenverarbeitungsanlage nach Figur 7 eine Ausschluß-Steuereinheit 50 vorgesehen, die eine Mehrzahl Ausschluß-Flip-Flops 51 aufweist. Die Ausschluß-Steuereinheit 50 soll verhindern, daß mehr als eine Datenverarbeitungseinheit 20 gleichzeitigen Zugriff zu ausgewählten kritischen Speicherstellen im Operand-Speicher 30 erhält. Im einzelnen wird jede Datenverarbeitungseinheit 20, die eine kritische Operand-Speicherstelle abzufragen sucht, durch eine interne Programmsteuerung angewiesen, zuerfet den Zustand eines bestimmten, der Flip-Flops 51, das dieser Speicherstelle in eindeutiger Weise zugeordnet ist, zu prüfen. Befindet sich dieses Flip-Flop in einem ersten, nicht gesperrten Zustand, so setzt die Verarbeitungseinheit 20 das Flip-Flop in den gesperrten Zustand und fragt gleichzeitig die gewünschte Speicheradresse ab. Alle übrigen Datenverarbeitungseinheiten 20 sind durch das gesetzte Flip-Flop 51 daran gehindert, gleichzeitig Zugriff zu der gespeicherten Digital-Information zu erhalten. Zu einem späteren Zeitpunkt stellt die erste Datenverarbeitungseinheit 20 das vorher gesperrte Flip-Flop 51 wieder zurück, so daß die gespeicherte Information wiederum auf Anforderung einer jeden der übrigen Datenverarbeitungseinhbiten 20 verfügbar ist.

2098Λ6/0964

eingegangen

Es sei bemerkt, daß jedes der vorstehend beschriebenen Schaltungselemente in Figur 7 allgemein bekannt ist und beispielsweise in "Handbook of Automation Computation and Control", Band 2, herausgegeben von E. M. Grabbe, Verlag John Wiley and Sons, Inc. New York 1959, beschrieben ist.

eingegangen

Auf diese Weise kann die Oatenblock» Integrität in einer Multiprocessing-Datenverarbeitungsanlage eichergestellt werden, ohne daß irgendein Datenblock dauernd gesperrt oder irgendeine Datenverarbeitungsfunktion dauernd verhindert ist.

Nachfolgend wird die Erfindung anhand der Zeichnungen näher beschrieben, es zeigen:

Fig. 1 und 2 graphische Darstellungen von Datenblöcken, die bei dem. erfindungsgemäßen

Verfahren benutzt werden; Fig. 3, 4, 5, 6Λ, 6B bildliche Darstellungen des

„ - „. erfindun<*sgeroäßen. Verfahrens. , . , Fig7:Eine Datenverarbeitungsanlage, bei der

das erfindungsgemäße Verfahren angewendet werden kann.

Die Erfindung ist in einem Multiprocessing-Planungsverfahren verwirklicht, das bestimmte Aufgaben einzelnen Verarbeitern zuordnet. Eine Aufgabe wird erst dann einem Verarbeiter zur Ausführung zugeordnet, wenn allen, der Ausführung vorangehenden Bedingungen genügt worden ist. Bei dem Planung s verfahr en werden die Datenblock-Sperrerfordemisce für jede Aufgabe ale ein Typ von vorher zu genügenden Bedingungen benutzt. Das Planungsverfahren stellt das einzige, dem Benutzer der Anlage zur Verfügung stehende Mittel zur Sperrung

bis eine binäre Eins festgestellt wird. Die dem auf diese Weise festgestellten Aufgabenzuordnungswort entsprechende Aufgabe wird dann durch den Verarbeiter ausgeführt.

Das erfindungsgemäße Verfahren wird besonders zweckmäßig bei einer Aufgabe verwirklicht, bei der die Sperrfunktion unmittelbar nach Ausführung des Aufgabenzuordnungs-Unterprogramms auftritt. Die absolute Betätigung einer Aufgabe durch das Aufgabenzuordnungs- unterprogramm bedeutet, daß alle Aufgaben und Eingangs/Ausgangsfunktionen, die der Ausführung dieser Aufgabe vorangehen, durchgeführt worden sind. Die Durchführung der Sperrfunktion für diese Aufgabe zu diesem Zeitpunkt statt zu einem vorhergehenden Zeitpunkt stellt sicher, daß Sperrungen nur während der tatsächlichen Ausführung der Aufgabe in Kraft sind, die die Sperrungen benötigt.

Das erfindungsgemäße Sperrverfahren wird im Anhang an diese Beschreibung durch ein als Beispiel gewähltes Programm für einen Digitalrechner erläutert. Dieses Programm kann in Verbindung mit einer Multiprocessin-Anlage benutzt werden, die ein Aufgabenzuordnungs-Unterprogramm enthält. Das Programm beschreibt diejenigen elektrischen Steuersig-

209846/0964

nale, die die Umordnung einer solchen Multiprocessing-Datenverarbeitungsanlage in eine heue Anlage bewirken, welche zur Durchführung des erfindungsgemäßen Verfahrens fähig.ist. Die durch diese neue Anlage aufgrund dieser elektrischen Steuersignale durchgeführten Verfahrensschritte stellt wohl die beste Art zur Ausführung der Erfindung dar.

Das mit vielen Erläuterungen versehene Programm im Anhang läßt sich leichter mit Hilfe der Tabellen in den Fig. 1 und 2 und der Flußdiagramme in den Fig. 3 bis 6B verstehen. Die Nummern der Programmschritte entsprechen im allgemeinen den Nummern der Kästchen in den Flußdiagrammen. Diese enthalten vier verschiedene Symbole. Die ovalen Symbole stellen Endanzeigen dar und bedeuten den Anfang oder das Ende einer bestimmten Programmfolge. Die "Operationsblöcke" genannten Rechtecke enthalten die Beschreibung eines bestimmten Operationsschrittes des Verfahrens. Die pastillenförmigen Symbole, die "bedingte Verzweigungspunkte" genannt werden, beschreiben eine von dem Rechner durchgeführte Prüfung zwecks Auswahl des nächsten auszuführenden Schrittes. Die Kreise stellen lediglich eine Zeichnungshilfe zur Vermeidung von sich überschneidenden Linien und zur Markierung von Anschlußpunkten dar.

209846/0964

eingegangen amiii

bis eine binäre Eins festgestellt wird. Die dem auf diese Weise festgestellten Aufgabenzuordnungswort entsprechende Aufgabe wird dann durch den Verarbeiter ausgeführt.

Das erfindungsgemäße Verfahren wird besonders zweckmäßig bei einer Aufgabe verwirklieht, bei der die Sperrfunktion unmittelbar nach Ausführung des Aufgabenzuordnungs-Unterprogramms auftritt. Die -absolute Betätigung einer Aufgabe durch das Aufgabenzuordnungsunterprogramm bedeutet, daß alle Aufgaben und Eingangs/A usgangsfunktionen, die der Ausführung dieser Aufgabe vorangehen, durchgeführt worden sind. Die Durchführung der Sperrfunktion für diese Aufgabe zu diesem Zeitpunkt statt zu einem vorhergehenden Zeitpunkt stellt sicher, daß Sperrungen nur während der tatsächlichen Ausführung der Aufgabe in Kraft sind, die die Sperrungen benötigt.

Das erfindungsgemäße Sperrverfahren wird im Anhang an diese Beschreibung durch ein als Beispiel gewähltes Programm für einen Digitalrechner erläutert. Dieses Programm kann in Verbindung mit einer Multiprocessing nlage benutzt werden, die ein Aufgabenzuordnungs-tJnterprogramm enthält. Das Programm beschreibt diejenigen elektrischen Steuersig-

* Eine solche Sperraufgabe wird von einem der Datenverarbeitungseinheiten 20^ bis 2O_n (Fig.7) auf die gleiche Weise wie andere Aufgaben ausgeführt.

eingegangen am

nale, die die Umordnung einer solchen Multiprocessing-Datenverarbeitungsanlage in eine heue Anlage bewirken, welche zur Durchführung des erfindungsgemäßen Verfahrens fähig ist. Die durch diese neue Anlage aufgrund dieser elektrischen Steuersignale durchgeführten Verfahreneschritte stellt wohl die beste Art zur Ausführung der Erfindung dar.

Das mit vielen Erläuterungen versehene Programm im Anhang läßt sich leichter mit Hilfe der Tabellen in den Fig. 1 und 2 und der Flußdiagramme in den Fig. 3 bis 6B verstehen. Die Nummern der Programmschritte entsprechen im allgemeinen den Nummern der Kästchen in den Flußdiagrammen. Diese enthalten vier verschiedene Symbole. Die ovalen Symbole stellen Endanzeigen dar und bedeuten den Anfang oder das Ende einer bestimmten Programmfolge. Die "Operationsblöcke¹¹ genannten Rechtecke enthalten die Beschreibung eines bestimmten Operationsschrittes des Verfahrens. Die pastillenför- \ migen Symbole, die "bedingte Verzweigungspunkte" genannt werden, beschreiben eine von dem Rechner durchgeführte Prüfung zwecks Auswahl des nächsten auszuführenden Schrittes. *Die Kreise stellen lediglich eine Zeichnungshilfe zur Vermeidung von sich überschneidenden Linien und zur Markierung von Anschlußpunkten dar.

* Die durch die Operationsblöcke und bedingten

Verzweigungsblöcke angegebenen Programmschritte werden durch die Datenverarbeitungseinheiten 2O₁ bis 20_M (Fig. 7) ausgeführt. '

209846/0984

>* eingegangen am.

*⁵

Das Programm, das das erfindungsgemäße Sperrverfahren verwirklicht, wird im folgenden mit "Datengruppen-Sperrorganisation¹¹ (DatajSet Lock Manager) oder DSLM bezeichnet. Das Programm DSLM verwendet zwei, in den Fig. 1 und 2 gezeigte Typen von Datenblöcken. Die dargestellten Datenblöcke enthalten eine Vielzahl von Digitalwörtern im

3OAF1B.7)
Speicher/Jedes Wort ist in eine Anzahl von Feldern unterteilt, die eine Vielzahl von Bits enthalten. Das Format dieser Datenfcäacke ist dem Fachmann bekannt.

Die in Fig. 1 gezeigte Datengruppen-Sperrtabelle (Data Set Lock Table) DSLT enthält alle Informationen, die zur Sperrung und Entsperrung eines bestimmten Datenblockcs erforderlich sind. Das Programm DSLM weist eine Sperrtabelle DSLT für jeden zu sperrenden Datenblock auf. Die Tabelle DSLT enthält Felder 10 und 20, die angeben, ob der Datenblock gesperrt ist. Das Feld 22 zeigt an, ob der Datenblock lesegesperrt oder schrcibgesperrt ist. Das Feld 12 enthält den Inhalt der Anlagenuhr zum Zeitpunkt, zu dem der Datenblock gesperrt worden ist. Die Felder 14 und IG beinhalten Steuerinformationen für den Fall von Sperrfehlern. Das Feld 24 stellt einen Zahler dar, wenn das Feld 22 angibt,

20984 6-/0964

daß der Datenblock lesegesperrt ist, und stellt einen . Zeiger (pointer) auf die Aufgabensperrliste (Task Lock List) da, wenn das Feld 22 angibt, daß der Datenblock schre'ibgesperrt ist. Die Felder 18 und 26 enthalten Zeiger auf die erste bzw. letzte Eintragung der Aufgabensperrliste entsprechend der Liste von Aufgaben, die darauf .warten, den Datenblock zu fc sperren. Eine Lesesperfung verhindert, daß ein

anderer Verarbeiter in einen Block von Daten einschreibt, gibt aber einem anderen Verarbeiter die Möglichkeit, den Datenblock zu lesen. Eine Schreibsperrung verhindert sowohl das Lesen aus als auch das Einschreiben in einen Datenblock. Die Benutzung der verschiedenen Felder wird in Verbindung mit den Flußdiagrammen in den Fig. 3 bis 6B im einzelnen erläutert.

Die in Fig. 2 gezeigte Aufgabensperrliste (Task Lock List) TLL enthält diejenigen Informationen, welche zur Sperrung aller derjenigen Datenblöcke erforderlich sind, die bei einer bestimmten Aufgabe gesperrt werden müssen. Jede Aufgabe, die einen Datenblock sperrt, weist eine zugeordnete Liste TLL auf. Die

Liste TLL beinhaltet eine Überschrift mit zwei Wörtern und ein Wort für jeden Datenblock, der durch die jeweilige Aufgabe gesperrt wird. Entsprechend

209846/0964

geändert gemäß Sngaöe eingegangen cm it.-..<L..3.£

Fig. 2 weist die Überschrift folgende Felder auf: ein Feld 40, das die Sperrbits enthält; ein Feld 44, das einen Zähler darstellt, der die Anzahl von Datenblöcken angibt, die durch die Aufgabe noch zu sperren sind; ein Feld 44, das den Wert darstellt, der jedesmal dann benutzt wird, wenn der Zähler des Feldes 44 gestartet wird; ein Feld 46, das einen Zeiger darstellt, der dann benutzt wird, wenn die Aufgabe auf einen Datenblock angewendet wird. Jede Datenbiockeintragung enthält ein Feld 50, nämlich eine Anzeige, ob eine Lese- oder Schreibsperrung erforderlich ist, ein Feld 52, nämlich eine (flag), <4ie angibt, ob die Aufgabe eine Sperrung für den Datenblock besitzt und ein Feld 54, nämlich einen Zeiger auf die Datengruppen-Sperrtabelle DSLT, die dem Programm DSLM sagt, welcher spezielle Datenblock zu sperren ist. Als wichtiger Punkt sei darauf hingewiesen, daß jede Aufgabensperrliste TLL die die DSLT-Zeiger enthaltenden Datenwörter in genau der gleichen Anordnung enthalten muß. Diese Anordnung vermeidet das oben erläuterte Problem, daß nämlich Aufgaben dauernd ausgesetzt und Datenblöcke dauernd gesperrt sind. Die genaue Verwendung der verschiedenen TLL-Felder wird nachfolgend genauer in Verbindung mit den Flußdiagrammen in den Fig.

3 bis 6B beschrieben.

209846/0964

Das spezielle Ausführungsbeispiel zur Durchführung des erfindungsgemäßen Verfahrens, das in den Flußdiagrammen der Fig. 3 bis 6B gezeigt ist, enthält vier Programme: LCKALL, das alle Datenblöcke für eine Aufgabe sperrt· LCKONE, das einen bestimmten Datenblock sperrt; UNLALL, das alle Datenblöcke für eine bestimmte Aufgabe

* entsperrt; UNLONE, das einen bestimmten Daten

block entsperrt.

Das in Fig. 3 dargestellte Programm LCKALL wird durch das Aufgabenzuordnungs-Unterprogramm aufgerufen, wenn alle vorhergehenden Aufgaben und Eingangs/Ausgang s funktionen für eine bestimmte Aufgabe durchgeführt worden sind. Zur einfacheren Beschreibung wird die im Augenblick durch das Programm DSLM bearbeitete Aufgabe mit "betätigte Aufgabe" bezeichnet. Jedesmal dann, wenn das Aufgabenzuordnungs-Unterprogramm das Programm LCKALL aufruft, weist es ihm einen Zeiger auf die TLL-Liste zu. Dieser Zeiger ermöglicht dem Programm LCKALL die Feststellung, welche Datenblöcke (die "Objekt"-Datenblöcke genannt werden)

für die betätigte Aufgabe gesperrt werden müssen, so wie welche Art von Sperrung auf jeden der Objekt-Datenblöcke anzuwenden ist.

209846/0964

In das Programm LCKALL wird zu Anfang von 100 aus eingetreten. Der Operationsblock 102 bewirkt unter Verwendung des oben erwähnten Ab ruf und Belegungsbefehls einen Zugriff zum ersten Wort der Überschrift der Liste TLL, die der betätigten Aufgabe zugeordnet ist. Die bedingte Verzweigung 104 bestimmt, ob die Sperrbits des in Fig. 1 gezeigten Feldes bereits vorher gesperrt worden sind. Wenn dies der Fall ist, liegt ein Fehlerzustand vor, da nur durch das Programm UNLALL ein Zugriff zur Überschrift erfolgen soll, und das Programm UNLALL die Überschrift entsperrt, bevor es auf das Aufgabenzuordnungs-Unterprogramm bei 128 zurückkehrt. Wenn also bei Erreichung der bedingten Verzweigung 104 die Überschrift gesperrt ist, so wird die Steuerung auf ein durch das Kästchen 106 dargestelltes Fehlerprogramm übertragen. Dieses Fehlerprogranam verwendet beispielsweise die symbolisch in Form des Feldes 16 in Fig. 1 dargestellten Informationen zur Einleitung von Vorgängen entsprechend den in der jeweiligen Anlage vorgesehenen Fehlerabhilfe verfahr en. Beispielsweise können in einer Anlage einfach nur alle Ketten, Aufgaben und Datenblöcke immer dann zurückgestellt werden, wenn ein Fehler auftritt. Andererseits kann die Funktion der Anlage von so

20984 6/0964

eingegangen arn.JU.4

Daß spezielle Ausführungsbeispiel zur Durchführung des erfindungsgernäßen Verfahrens, das in den FIußdiagraminen der Fig. 3 biü GB gezeigt ist, enthält vier Programme: LCKALL, das alle Datenblöcke für eine Aufgabe sperrt; LCKO]SfE, das einen bestimmten Datcnblock sperrt; UNLALL, das alle Datenblöcke für eine bestimmte Aufgabe enteperrt; UNLCNE, das einen bestimmten Datenblock entsperrt.

Das in Fig. 3 dargestellte Programm LCKALL wird durch das Aufgabenzuordnungs-Unterprogramm aufgerufen, wenn alle vorhergehenden Aufgaben * und L'ingangs/Ausgangsfunktionenlür eine bestimmte Aufgabe durchgeführt worden sind. Zur einfacheren Beschreibung wird die im Augenblick durch das Programm DSLM bearbeitete Aufgabe mit "betätigte Aufgabe" bezeichnet. Jedesmal dann, wenn das Aufgabenzuordnungs-Unterprogramm das Programm LCKALL aufruft, weist es ihm einen Zeiger auf die TLL-Liste zu. Dieser Zeiger ermöglicht dem Programm LCICALL die Feststellung, welche Datenblöcke (die "Objekt"-Datenblöcke genannt werden)

für die betätigte Aufgabe gesperrt werden müssen, so wie welche Art von Sperrung auf jeden der Objekt-Datenblöcke anzuwenden ict.

*(die durch die in Fig.7 gezeigten Dp.tenverarbeitungsejriaeiten 2O₁ bis 2O_n ausgeführt werden müssen.)

** (die durch die in Fig.7 gezeigte Eingabe/Ausgabe-Steuereinheit 18 ausgeführt worden müssen)

209846/0964

die Steuerung an das Programm LCKALL zurückgibt, muß entsprechend dem bedingten Verzweigung spankt 114 geprüft werden, ob er jeweilige Datenblock gesperrt worden ist. Wenn das Programm LCKONE nicht in der Lage war, den Datenblock zu sperren, hat es auf eine noch zu beschreibende Weise einen Zeiger auf die Aufgabe in einer Warteschlange eingegeben, bevor auf das Programm LCICALL zurückgegeben wird. Dieses Programm setzt dann zeitweilig seinen Versuch zur Sperrung der Datenblöcke für die betätigte Aufgabe aus. Der Programmschritt entsprechend dem Kästchen 116 entsperrt die TLL-Üb er schrift der betätigten Aufgabe, und entsprechend 1Φ8 wird die Steuerung auf das anfordernde Programm zurückgegeben. Wenn das Programm LCKONE in der Lage war, den Datenblock zu sperren, überträgt die bedingte Verzweigung die Steuerung auf den Programmschritt gemäß Kästchen 120, wobei C₁ um Eins weitergeschaltet wird. Die bedingte Verzweigung 122 prüft dann als nächstes den Zustand des Zählers C₁. Wenn dessen Zählwert kleiner als Null ist, liegt ein Fehler vor, und die Steuerung wird an 124 übertragen. Wenn C.

209846/096

el

immer noch größer als Null ist/ was bedeutet, daß noch weitere Datenblöcke zu sperren sind, so wird die Steuerung auf den Programmschritt entsprechend dem Kästchen 110 übertragen. Wenn C₁ gleich Null ist, was bedeutet, daß alle Datenblöcke gesperrt sind, die für die betätigte Aufgabe gesperrt werden müssen, so wird die Steuerung an das Kästchen 126 übergeben, das die TLL-Überschrift der betätigten Aufgabe entsperrt. Bei 128 wird dann die Steuerung auf das anfordernde Programm zurückgegeben.

Wenn am Endpunkt 118 des Programms LCKALL ausgetreten wird, was bedeutet, daß das Programm LCKONE nicht in der Lage ist, einen bestimmten Datenblock der Objekt-Datenblöcke der betätigten Aafgabe zu sperren, so wird das Programm LCKALL durch das Programm UNLONE aufgerufen, sobald die Eintragung der betätigten Aufgabe wieder an die Spitze der Warteschlange gelangt. Bei einem Aufruf durch das Programm UNLONE wird am Anfangspunkt 130 in das Programm LCKALL eingetreten, und der Drogrammschritt entsprechend dem Kästchen 132 ruft das erste Wort der Überschrift in der Aufgaben-

209846/0964

21Ü1949

.sperrliste TTL₁ die der betätigten Aufgabe zugeordnet ist, auf und belegt es. Wenn die Überschrift gesperrt ist, überträgt die bedingte Verzweigung 134 die Steuerung auf ein durch das Kästchen 136 dargestelltes Fehlerprogramm. Wenn die Überschrift nicht gesperrt ist, verringert der Programmschritt entsprechend dem Kästchen 120 den Inhalt des Zahlers C₁ und übergibt die Steuerung an die bedingte Verzweigung 120. Diese versucht dann die restlichen Objekt-Datenblöcke entsprechend der obigen Erläuterung zu sperren. J.

In das in Fig. 4 gezeigte Programm LCKONE wird am Anfangspunkt 200 eingetreten. Dessen erste Funktion besteht entsprechend dem Kästchen 202 darin, den Zähler C₀ einzustellen. Dieser Zähler gibt die Möglichkeit, die Schleife 204-210, die zur Gewinnung der DSLT-Eintragung für den Objekt-Datenblock dient, mehrfach zu durchlaufen, bevor ein Fehlerzustand gemeldet wird, um der Möglichkeit Rechnung zu tragen, daß eine andere Aufgabe versucht, einen Zugriff zu diesee DSLT-Eintragung zu gewinnen. Der Wert, der bei der Einstellung des symbolisch in Fig. 1 als Feld 14 dargestell-

209846/0964

2-3 Jtt

ten Schleifenzählers CL benutzt wird, hängt in bekannter Weise von Systemparametern ab, beispielsweise von der Anzahl und der Bearbeitungszeit der Verarbeiter, der Speicher-Zykluszeit, Eingangs-Ausgangswechselwirkungen und dem allgemeinen Systemaufbau. Für die meisten Anlagen sorgt eine Einstellung von C₀ auf den Wert 20 für eine ausreichend große Wartezeit.

Bei dem Programmschritt entsprechend dem Kästchen 204 wird das erste Wort der speziellen DSLT-Eintragung gewonnen und belegt, auf die die TLL-Eintragung hinweist, welche beim Aufruf des Programms LCKONE an dieses Programm übergeben worden ist. Wenn die Sperrbits dieses ersten Wortes angeben, daß die DSLT-Eintragung gesperrt ist, übergibt die bedingte Verzweigung 206 die Steuerung an den Programmschritt gemäß Kästchen 208, in welchem der Zähler C₀

Ci

um eins zurückgeschaltet wird. Die bedingte Verzweigung 210 prüft dann, ob der Inhalt des Zählers C null ist.

Ci

Falls dies nicht der Fall ist, gibt sie die Steuerung erneut an das Kästchen 204 zurück. Wenn C₀ null ist, wird

Ci

die Steuerung auf ein durch das Kästchen 212 dargestelltes Fehlerprogramm, übertragen.

209846/0964

Wenn die Sperr-Bits des ersten Wortes (Feld 10 in Fig. 1) der DSLT-Eintragung des Objekt-Datenblockes nicht gesperrt sind, überträgt die bedingte Verzweigung 106 die Steuerung auf die bedingte Verzweigung 214. Diese bestimmt unter Verwendung des in Fig. 2 gezeigten Feldes 50 der TLL-Eintragung für die betätigte Aufgabe, ob eine Lese- oder ein Schreibsperre gewünscht ist. Im Fall einer Lesesperre wird die Steuerung an die bedingte Verzweigung 216 übertragen Diese bestimmt unter Verwendung der in Fig. 1 gezeigten Felder 22 und 18 der DSLT-Eintragung für den Objekt-Datenblock, ob der Datenblock schreibgesperrt oder in einer Schlange gesperrt ist. Wenn keine dieser Bedingungen vorliegt, so werden bei dem Programmschritt entsprechend dem Kästchen 218 die entsprechenden Eintragungen in den Feldern 12, 20 und 22 der DSLT-Eintragung für den Objekt-Datenblock und in das Feld 52 der TLL-Eintragung, um eine Lesesperre anzuzeigen. Der Programms ehr itt 220 entsperrt dann die DSLT-Eintragung durch Rückstellung der Bits im Feld 10 (Fig. 1), und bei 222 wird die Steuerung auf das Programm LCKALL zurückgegeben.

209846/0964

Wenn die bedingte Verzweigung 216 feststellt, daß der Objekt-Datenblock im Augenblick entweder schreibgesperrt oder in einer Schlange gesperrt ist, gibt der Programmschritt entsprechend dem Kästchen 224 unter Verwendung des Inhaltes des in Fig. 1 gezeigten Feldes 26 einen in Fig. 2 als Feld 46 dargestellten TLL-Zeiger auf die jeweilige Aufgabe in die Schlange wartender Aufgaben. Dieser Zeiger bewirkt entsprechend der nachfolgenden Erläuterung in Verbindung mit Fig. 6, daß das Programm UNLONE den Objekt-Datenblock entsprechend der betätigten Aufgabe sperrt, sobald er frei wird. Der Programmschritt entsprechend dem Kästchen 220 entsperrt dann die DSLT-Eintragung durch Eingabe von Null-Werten in das Feld 10 (Fig. 1) und bei 222 wird die Steuerung auf das Programm LCKALL zurückgegeben.

Wenn die bedingte Verzweigung 214 feststellt, daß eine Schreibsperre gewünscht wird, so wird die Steuerung auf die bedingte Verzweigung 226 übertragen. Diese stellt unter Verwendung des Feldes 10 der DSLT-Eintragung des Objekt-Datenblockes fest, ob der Datenblock im Augenblick lese- oder schreibgesperrt ist. Wenn der Datenblock gesperrt ist, so wird die

209846/0964

. Steuerung auf den Programmschritt entsprechend dem Kästchen 224 übertragen, der dann auf die oben erläuterte Weise fortfährt. Wenn der Datenblock im Augenblick nicht gesperrt ist, so wird die Steuerung auf den Programmschritt 228 übertragen. Dieser füllt die Felder 12, 20 und 22 (Fig. 1) der DSLT-Eintragung für den Objekt-Datenblock sowie das in Fig. 2 gezeigte Feld 52 der TLL-Eintragung für die betätigte Aufgabe und überträgt die Steuerung auf den Programmschritt entsprechend dem Kästchen 220, der die DSLT-Eintragung entsperrt. Bei 222 wird dann die Steuerung auf das Programm LCKALL zurückgegeben.

Wenn die Ausführung der betätigten Aufgabe beendet ist, muß das Programm DSLM alle Datenblöcke entsperren, die bei Ausführung der Aufgabe gesperrt geblieben sind. Es besteht die Möglichkeit, daß nicht alle Datenblöcke, die ursprünglich für die Aufgabe vor ihrer Ausführung gesperrt worden sind, gesperrt geblieben sind, da eine Aufgabe einen Datenblock durch Aufruf des Programms UNLONE während ihrer Ausführung zur Entsperrung gestimmter Datenblöcke

209846/0964

entsperren kann. Zur Durchführung der restlichen . Entsperrung ruft das Programm DSLM das Programm UNIlALL auf und übergibt diesem einen Zeiger auf die Liste TLL der betätigten Aufgabe.

Gemäß Fig. 5 wird in das Programm UNLALL bei 300 eingetreten. Der Programmschritt entsprechend dem Kästchen 302 ruft das erste Wort der TLL-Überschrift für die betätigte Aufgabe ab und belegt es. Wenn das in Fig. 2 gezeigte Feld 40 dieser Überschrift gesperrt ist, überträgt die bedingte Verzweigung 304 die Steuerung auf ein Fehlerprogramm 306 auf eine Weise, die dem Programmschritt 104 des Programms LCKALL entspricht. Wenn die Überschrift nicht gesperrt ist, wird die Steuerung ' auf den Programmschritt entsprechend dem Kästchen

308 übertragen, bei dem der Zähler CL mit einem

Wert in Gang gesetzt wird, der gleich der Anzahl von zu entsperrenden Blöcken ist. Der Programm.-schritt 310 gewinnt dann die TLL-Eintragung, auf die die Überschrift und der Zähler CL hinweist. Die bedingte Verzweigung 312 erreicht dann unter Verwendung des DSLT-Zeigers dieser TLL-Eintragung

20 9846/0964

»5

den ersten Datenblock und bestimmt, ob er gesperrt ist oder nicht. Wenn der Datenblock gesperrt ist, ruft der Programmschritt entsprechend dem Kästchen 314 das Programm ICJNLONE zur Entsperrung des Datenblockes auf.

Wenn der Datenblock nicht gesperrt ist, wird die Steuerung direkt auf den Programmschritt entsprechend dem Kästchen 316 übertragen. Das Erreichen des Kästchen 316 auf einem der angegebenen Wege zeigt also an, daß der fragliche Datenblock entsperrt worden ist. Der Zähler C wird dann um eins zurückgeschaltet, und die bedingte Verzweigung 318 prüft den Zustand des Zähler C . Wenn sein Zählwert kleiner als null ist, wird die Steuerung auf ein durch das Kästchen 320 dargestelltes Fehlerprogramm übertragen. Wenn der Zählwert größer als null ist, wird die Steuerung auf das Kästchen 310 übertragen, und es findet ein erneuter Durchlauf der Schleife 310-318 statt. Wenn der Zählwert gleich null ist, entsperrt der Programmschritt entsprechend dem Kästchen 322 die TLL-Überschrift, und bei 324 wird die Steuerung

209846/0964

auf das anfordernde Programm zurückgegeben.

In das Programm UNLONE (Fig. 6A und 6B) wird am Anfangspunkt 400 (Fig. 6A) eingetreten. Der Programmschritt entsprechend dem Kästchen 402 setzt den Zähler C. auf ähnliche Weise wie bei dem Zähler C₀ entsprechend dem Kästchen 202 in Fig.

Cx

in Gang. Bei dem Programmschritt entsprechend dem Kästchen 404 wird die DSLT-Eintragung für den Objekt-Datenblock abgerufen und belegt. Die bedingte Verzweigung 406 prüft das Feld 10 (Fig. 1) der DSLT-Eintragung für den Objekt-Datenblock, um festzustellen, ob er gesperrt ist. Wenn dies der Fall ist, wird entsprechend dem Kästchen 408 der Zähler C. zurückgeschaltet, und die bedingte Verzweigung 410 bestimmt, ob der Inhalt des Zählers C. null ist. Trifft dies zu, so wird die Steuerung auf ein durch das Kästchen 412 dargestelltes Fehlerprogramm übergeben. Wenn der Zählwert nicht null ist, so wird die Steuerung erneut auf das Kästchen übertragen. Wenn die bedingte Verzweigung 406 feststellt, daß die Sperr-Bits der DSLT-Eintragung nicht gesperrt sind, so wird die Steuerung auf die bedingte

209846/0964

Verzweigung 414 übertragen, um die Art der Augenblicklichen Sperrung für den Objekt-Datenblock zu bestimmen. Wenn der Datenblock als entsperrt festgestellt wird, so wird die Steuerung auf ein Fehlerprogramm entsprechend dem Kästchen 416 übertragen. Wenn der Datenblock schreibgesperrt ist, so wird die Steuerung unmittelbar auf die b edingte Verzweigung 428 übertragen. Wenn der Datenblock lesegesperrt ist, wird die Steuerung auf das Kästchen 418 übertragen, das ddn als Feld 24 in Fig. 1 dargestellten Lesesperrzähler zurückschaltet. Die bedingte Verzweigung 420 prüft den Zustand dieses Zählers. Wenn sein Zählwert kleiner als null ist, so wird die Steuerung auf ein durch das Kästchen 422 dargestelltes.Fehlerprogramm übertragen. Wenn der Zählwert größer als null ist, wodurch angezeigt wird, daß andere Aufgaben den Datenblock zu diesem Zeitpunkt lesegesperrt haben, so entsperrt der Programmschritt entsprechend dem Kästchen 424 das Feld 10, nnd bei 426 wird die Steuerung an das anfordernde Programm zurückgegeben. Wenn der Zählwert des Lesesperrzählers gleich null ist, stellt die bedingte Verzweigung 428 fest, ob betätigte Aufgaben vorhanden sind, die darauf warten,

209846/0984

den Objekt-Datenblock zu sperren. Wenn dies der Fall ist, wird die Steuerung auf das Kästchen 424 übertragen. Im anderen Fall geht die Steuerung auf das Kästchen 430 über.

Bei dem Programmschritt entsprechend dem in Fig. 6B gezeigten Kästchen 430 Wird der Zeiger im Feld 18 dieser DSLT-Eintragung (Fig. 1) benutzt, um die erste betätigte Aufgabe in der Warte schlange von Aufgaben zu gewinnen. Die bedingte Verzweigung stellt fest, ob die wartende Aufgabe eine Lese- oder eine Schreibsperre für den Objekt-Datenblock verlangt.

Wenn eine Schreibsperre gewünscht ist, gibt der Programmschritt entsprechend dem Kästchen 434 den augenblicklichen Wert der Systemzeit in das Feld 12 (Fig. 1) der DSLT-Eintragung für den Objekt-Datenblock, bringt den TLL-Zeiger im Feld 18 auf den neuesten Stand, gibt eine Schreibsperranzeige in das Feld 22 ein und stellt die Sperr-Bits im Feld ein. Der Verfahrensschritt 436 entsperrt dann die DSLT-Eintragung durch Rückstellung des Feldes 10.

209846/0964

3«

Beim Verfahrens schritt 438 wird das Programm LCKALL, ihm der im Feld 46 (Fig. 2) dargestellte Zeiger auf die eingereihte Aufgabe zugeführt und die Steuerung auf den Verfahr ens schritt 130 (Fig. 3) übertragen. Das Programm LCKALL benutzt dann den Zeiger zur Sperrung der restlichen Datenblöcke der in der Schlage befindlichen Aufgabe auf die in Verbindung mit Fig. 3 besprochene Weise. Wenn das Programm LCKALL die Steuerung auf das Programm UNLONE zurückgibt, überträgt der Verfahrensschritt 440 die Steuerung wieder auf das Programm UNLALL.

Wenn die bedingte Verzweigung 432 feststellt, daß die in der Schlange befindliche Aufgabe eine Lesesperre für den Objekt-Date nblock wünscht, gibt sie die Steuerung an den dem Kästchen 442 entsprechenden Verfahrensschritt. Dieser vergrößert den Wert des Feldes 24 (Fig. 1) der DSLT-Eintragung für den Objekt-Datenblock und gibt den augenblicklichen Wert der Anlagenuhr in das Feld 12 ein. Der Verfahrenes ehr itt entsprechend dem Kästchen 444 ruft dann das Programm LCKALL auf die oben

2098A6/0964

in Verbindung mit dem Kästchen ,438 beschriebene Weise auf. Wenn das Programm LCKALL die Steuerung zurückgibt, bestimmt die bedingte Verzweigung 426 unter Verwendung des in Fig. 2 dargestellten Feldes 46, ob weitere Aufgaben in der Schlange warten. Wenn dies nicht der Fall ist, wird die Steuerung auf das Kästchen 454 übertragen, das Feld 10 (Fig. 1) der DSLT-Eintragung für den Objekt-Datenblock wird entsperrt und der Verfahrens schritt 440 gibt die Steuerung auf das Programm yt/A¹ UNLALL. zurück.

Wenn Aufgaben in der Schlange verblieben sind, gewinnt der dem Kästchen 448 entsprechende Verfahrensschritt unter Verwendung des im Feld 46 (Fig. 2) dargestellten Zeigers die nächste betätigte Aufgabe. Wenn diese neue Aufgabe eine Lesesperre des Objektdatenblockes wünscht, überträgt die bedingte Verzweigung 450 die Steuerung auf den dem Kästchen 442 entsprechenden Verfahrensschritt, um die Lesesperre vorzunehmen. Dies ist zulässig, da gleichzeitige Lesesperren für einen einzigen Datenblock keine gegenseitige Störung verursachen. Wenn eine Schreibsperre des Objekt-Datenblocks gewünscht wird, gibt der dem Kästchen 452 entsprechende Verfahrens-209846/0964

S3

schritt die Aufgabe in die Warteschlange zurück, in dem er den Zeiger im Feld 46 der Liste TTL für die betätigten Aufgaben zurückstellt, und die Steuerung wird auf das Kästchen 454 übertragen. Die Rückgabe der Aufgabe in die Warteschlange erfolgt deswegen, weil eine Lesesperre und eine Schreibsperre gleichzeitig nicht zulässig sind. Dies stellt nämlich genau dasjenige Problem dar, welches vermieden werden soll. Dies ist der Grund dafür, daß der Zweig 434-440 keine Prüfung auf weitere Eintragungen in der Schlange für wartende Aufgaben enthält. Wenn solche Aufgaben vorhanden sind, müssen sie warten, da eine einzelne Schreibsperre für einen Objekt-Datenblock alle anderen Sperren ausschließt. Auf entsprechende Weise enthält der Zweig 424-426 keine Prüfugg auf weitere Eintragungen in der Schlange, da vorhergehende Durchläufe des Zweiges 440-454 sichergestellt haben, daß die nächste Eintragung dieser Art, falls eine solche vorhanden ist, eine Anforderung für eine Schreibsperre des Objekt-Datenblockes ist.

Die oben beschriebene Anordnung stellt nur ein Aus-209846/0964

Ho

führungsbeispiel der Erfindung dar. So lassen sich beispielsweise die handelsüblichen Multiprocess ing.-Datenverarbeitungssysteme IBM 9020, General Electric 645 und Univac 1108 so programmieren, daß die Erfindung mit Vorteil benutzt werden kann.

209846/096A

ANHANG (Programmiersprache ALGOL)

10 BEGIN INTEGER Cl, C2, C3, C4, C5, C6, Cl₃ ENP₁ TASK, DS INTEGER ARRAY DSLT40, DSLT42, DSLT44, DSLT46, DSLT48 (0:10), DSLT50 DSLT52, DSLT54(0:10), 0:10), TLLlO, TLLl2, TLL14, TLLl6, TLLl8, TLL20, TLL22, TLL24, TLL26(0;20);

100 PROCEDURE LCKALL (TASK, ENP);

101 IP ENP=2 THEN GO TO Bl 30,·

102 IF TLLlO(TASK)=I THEN GO TO ERROR ELSE

TLL10(TASK)=l·

103 (COMMENT: LOCK THE TLL ENTRY = BEM. : SPERREN DER TEL -EINTRAGUNG);

104 GO TO Bl 08;

106 ERROR: GO TO STOP;

108 B1O8;C1:=TLL42(TASK):=TLL44(TASK);

109 (COMMENT: INITIALIZE THE COUNTER =

BEM: STARTEN DES ZÄHLERS);

110 (COMMENT: PASS TASK NUMBER (TASK) AND DATA

SET POINTER (Cl) TO LCKONE = BEM: WEITERGEBEN AUFGABENNUMMER (TASK) UND

DATENEINSTELLZEIGER (Cl) ZU LCKONE); 112 Bl 12: LCKONE (TASK, C;);

209846/0964

Hl

^ eingegangen αια_ΐ£»£

führungsbeißpiel der Erfindung dar. So lassen sich beispielsweise*die handelsüblichen Multiprocessing-DatenverarbeitungBsysteme IBM 9020, General Electric 645 und Univac 1108 so programmieren, daß die Erfindung mit Vorteil benutzt werden kann.

W * neben einer Anlage (Fig.7) nach der oben

erwähnten älteren Anmeldung.

209846/0 9-6

200 B200: (COMMENT: START OF LCKONE CODE-PROCEDURE LCKONE (TASK, Cl) = BEM: START DES LCKONE-CODE-UNTERPROGRAMM LCKONE (TASK, Cl));

202 C2:=20;

203 DS:TLL54(TASK, Cl);

204 B204; IF DSLTlO(DS)=D THEN BEGIN;

DSLZlO(DA):=!;

205 GO TO B124J

206 (COMMENT: IT' S LOCKED SO TRY AGAIN =

BEM: WENN GESPERRT, NEUER VERSUCH); 208 C2:=C2-1;

210 IF C2 <Ö THEN GO TO ERROR/ELSE GO TO B204;'

211 (COMMENT: SHOULDN' T BE LOCKED THAT LONG =

BEM: DARF NICHT SO LANGE GESPERRT SEM);

212 (COMMENT: ALL ERROR HANDLING IS AT ERROR=

BEM: GESAMTE FEHLERBEARBEITUNG IST FEHLERHAFT);

214 IF TLL50(TASK, Cl)=O THEN GO TO B226;

215 (COMMENT: IF WRITE LOCK GO TO 226 =

BEM: WENN SCHREIBSPERRE, ZU 226 GEHEN);

216 IF DSLT22(DS)=0 OR DSLT18(DS)/=O THEN GO TO B224J

217 (COMMENT: CHECK FOR WRITE LOCK OR LOCK QUEUED =

BEM: PRÜFEN, OB SCHREIBSPERRE ODER EMGEREIHTE SPERRE);

209846/0964

218 DSLT24(DS):=DSLT24(DS)+1;

219 (COMMENT: DUMP LOCK COUNTER =

BEM: ENTLEEREN SPERRZÄHLER),·

220 B220:TLL52(C2)=l; DSLTl0(TLL54(TASK, Cl)) =D;

221 (COMMENT: SET FLAGS = BEM: EINSTELLEN FAHNEN);

222 GO TO B229;

224 B224 IF DSLT18(DS)=0 THEN DSLT18(18):=TASK;

DSLT26(DS):=TLL46(DSLT26(DS)):=TASK;GO TO B22

225 (COMMENT: QUEUE TASK = BEM: AUFGABE EINREIHEN);

226 . B226: IF DSLT20(DS)=l THEN GO TO B224;

227 (COMMENT: WRITE LOCK THE DS =

BEM: SCHREIBSPERREN DER DS);

228 DSLT18(DS):=TASKJDSLT22(DS)=O;TLL2O(TASK):=1;

229 (COMMENT: SET WRITE LOCK FLAGS =

BEM: EINSTELLEN SCHREIBSPERREN-FAHNEN);

230 B229: END LCKONE;

300 PROCEDURE UNLALL (TASK);

302 IF TLL40(TASK)=I THEN GO TO ERROR

304 TLL40(TASK)=l;

305 (COMMENT: LOCK TLL ENTRY =

BEM: SPERREN TLL-EINTRAGUNG),·

306 (COMMENT: ALL ERRORS ARE HANDLED BY ERROR = BEM:ALLE FEHLER DURCH ERROR BEARBEITET);

209846/0964

308 C3i=TLL44(TASK)·

310 B310 (COMMENT: TEST TO SEE IF DS IS LOCKED =

BEM: PRÜFEN, OB DS GESPERRT 1ST);

312 IF TLL52(TASK, C3)=0 GO TO B316;

314 UNLONE (TASK, C3);

316 B316: C3=:=C3-1;

318 IF C3=0 THEN GO TO B322;

319 (COMMENT: SEE IF ALL DS ARE UNLOCKED =

BEM: FESTSTELLEN, OB ALLE DS ENTSPERRT SIND);

320 IF C3<0 THEN GO TO ERROR; GO TO B310,·

322 B322: TLL40(TASK):=0,·

323 (COMMENTrSETUNLOCKEDFLAG =

BEM: EINSTELLEN ENTSPERRTE FAHNE);

324 END UNLALL;

400 PROCEDURE UNLONE (TASK, C3);

402 C4:=20;

403 C5:=TLL (TASK, C3);

(COMMENT:C5=DATA SET TO BE UNLOCKED = BEM:C5 IST ZU ENTSPERRENDE DATENGRUPPE)·

404 B404: IFDSLT10(C5)=l THEN GO TO B408; 406 DSLT1O(C5):=1; GO TO B414;

408 C4:=C4-1;

409 (COMMENT: STILL LOCKED TRY AGAIN UNLESS C4^)/) = BEM:WENN NOCH GESPERRT, ERNEUT VERSUCH SN, wenn nicht, C4

209846/0964

410 IF C4 0 THEN GO TO B404; · 412 GO TO ERROR;

414 IF DSLT20(C5)=0 THEN GO TO ERROR;

415 (COMMENT: GO TO ERROR IF DS IS UNLOCKED = BEM: ZU ERROR GEHEN, WENN DS ENTSPERRT IST),·

416 IF DSLT22(C5)=0 THEN GO TO B228;

417 (COMMENT: GO TO 228 IF WRITE LOCK = BEM: ZU 228 GEHEN, WENN SCHREIBSPERRE);

418 DSLT24(C5):=DSLT24(C5)-1;

42Q IF DSLT(24)=0 THEN GO TO B228;

421 (COMMENT: IF NO MORE READ LOCKS THEN GO TO 228 = BEM:WENN KEINE WEITEREN LESESPERREN, DANN ZU GEHEN);

422 IF DSLT(24) <0 THEN GO TO ERROR;

423 (COMMENT: IF NEGATIVE READ LOCKS THEN QUIT = BEM:WENN NEGATIV, LESESPERREN, DANN QUIT);

424 B424: DSLT1O(C5):=O;

425 (COMMENT: UNLOCK THE HEADER AND QUIT = BEM: ENTSPERREN DER ÜBERSCHRIFT UND QUIT);

426 GO TO B456;

428 IF DSLT18(C5)=0 THEN GO TO B424· (COMMENT: IF NO ONE IS WAITING QUIT = BEM: WENN KEINE AUFGABE WARTET, QUTT);

209846/0964

42

429 C6:=TASK- COMENT SAVE TASK POINTER FOR UNLOCKING;

430 TASK:= DSLTl 6(C5);

431 (COMMENT: GET WAITING TASK =

BEM: HOLEN DER WARTENDEN AUFGABE);

432 IF TLL 50(TASK)=I THEN GO TO B442;

434 DSLT 24(C5):= TASK; DSLT22(C5):=0; DSLT20(C5):=l,· TLL52(TASK):=lj .

435 (COMMENT: SET DS WRITE LOCKED = BEM: SCHREIBSPERREN DS );

436 DSLT1O(C5)=O;

437 ENP=2;

438 LCKALL (TASK, ENP);

439 (COMMENT: TRY TO LOCK REST OF DATA SETS =

BEM: VERSUCHEN, REST DER DATENGRUPPEN ZU SPERREN);

440 B440: GO TO B456;

442 B442: DSLT24(C5):=DSLT24(C5)+1; (COMMENT: BUMP READ COUNT = BEM:' ENTLEEREN LESEZÄHLER);

443 ENP:=2

(COMMENT:SET FLAG AND GO FOR REMAINING LOCKS = BEM:EMSTELLEN FAHNE UND WEITERLAUF FÜR RESTLICHE SPERREN);

444 LCKALL (TASK, ENP);

209846/0964

446 TASK:=DSLT18(C5):=TLL46(DSLT18(C5));

. IF DSLTl8(C5)=0 THEN GO TO 440; 448 (COMMENT: IF NO MORE READ LOCKS QUIT =

BEMrWENN KEINE WEITEREN LESESPERREN, QUIT); 450IF TLL50 (TASK)=I THEN GO TO B442;

451 (COMMENTrIF NEXT TASK REQUIRE READ LOCK THEN B442 = BEM: WENN NÄCHSTE AUFGABE LESESPERRE FORDERT, DANN B442);

452 (COMMENT: DONE = BEM: DONE);

453 TASKr =C6·

454 DSLT1O(C5):=O,· GO TO 440;

455 (COMMENT: UNLOCK HEADER = BEM:ENTSPERREN ÜBERSCHRIFT);

456 B456: END UNLOME; 458 STOP END;

209846/096A

Claims (3)

4* PATENTANSPRÜCHE

1. Verfahren zur Verhinderung eines unerwünschten

gleichze itigen Zugriffs durch zwei oder mehrere Verarbeiter zu einem einzigen Datenblock, dem ein Sperrwort zugeordnet ist, in einer aufgabenorientierten Multiprocessing-Datenverarbeitungsanlage mit dem Verfahrensschritt

(1) Prüfung von Sperrwörtern, die Datenblöcken zugeordnet sind, zu welchen bei einer Aufgabe ein Zugriff erfolgen soll, darauf, ob Datenblöcke gesperrt oder entsperrt sind, gekennzeichnet durch die Verfahrens schritte:

(2) Sperren jedes Datenblockes , zu dem bei einer Aufgabe ein Zugriff erfolgen soll, unmittelbar vor und als Voraussetzung für die Ausführung der Aufgabe (Fig. 4)j

(3) Entsperren jedes Datenblockes, der vor Ausführung der Aufgabe gesperrt worden ist und nach Ausführung der Aufgabe gesperrt bleibt (Fig. 6A und 6B).

2. Verfahren nach Anspruch 1, dadurch gekennzeichnet,

daß der Verfahrens schritt des Sperrens folgende Verfahrensschritte umfaßt:

209846/0964

(1) Lesesperren jedes im Augenblick nicht schreibgesperrten oder in einer Schlage gesperrten Datenblockes, zu dem während der Ausführung der Aufgabe ein Zugriff erfolgt;

(2) Schreibsperren jedes im Augenblick nicht gesperrten Datenblockes, der während der Ausführung der Aufgabe abgeändert wird;

(3) Eingabe eines Zeigers auf die Aufgabe in eine Schlange, wenn das Lesesperren oder das Schreibsperren nicht durchgeführt worden ist.

3. Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet, daß der Verfahrens schritt des Entsperrens jedes Datenblockes folgende Verfahrensschritte umfaßt:

(1) Bestimmung der Art der augenblicklich für den gesperrten Datenblock bestehenden Sperre und, faUsjes sich

um eine Lesesperre handelt, Beendigung des Entsperr Verfahrens schrittes, wenn weitere Aufgaben den Datenblock im Augenblick mit einer Lesesperre belegt haben;

(2) Feststellen, ob weitere Aufgaben im Augenblick darauf warten, den Datenblock zu sperren oder nicht;

(3) Falls nicht, Entsperr en des Datenblockes und Beendigung des Entsperrverfahrens;

209846/0964

(4) Wenn weitere Aufgaben vorhanden sind,

(a) Gesperrthalten des Datenblockes entsprechend den Anforderungen durch die erste der weiteren Aufgaben,

(b) Beendigung des Entsperr-Verfahrensschrittes, wenn der Verfahrens schritt (4)(a) zu einer Schreibsperre des Datenblockes führt,

(c) Wiederholen der Verfahrens schritte (4)(a) bis (4)(c) bis der Entsperr-Verfahrensschritt beendet ist.

209846/0964

Si

Leerseite