DE68916167T2

DE68916167T2 - Adressenspeichersperrung mit priorität für einen gemeinsamen speicher.

Info

Publication number: DE68916167T2
Application number: DE68916167T
Authority: DE
Inventors: Clarence Dekarske; Lawrence Fontaine; Glen Kregness
Original assignee: Unisys Corp
Current assignee: Unisys Corp
Priority date: 1988-04-27
Filing date: 1989-04-24
Publication date: 1994-09-22
Anticipated expiration: 2009-04-25
Also published as: DE68916167D1; EP0365674B1; US4984153A; EP0365674A1; WO1989010592A1; JPH04500570A; CA1323705C

Description

Anweisungen zur Speichersperre oder Speicherverriegelung werden in Mehrprozessorsystemen verwendet, um Prozesse zu synchronisieren und um sicherzustellen, daß ein Speicherbereich oder eine Datei zu einer gegebenen Zeit nur einem Prozessor zur Verfügung steht, auch wenn mehr als ein Prozessor Zugang zu diesem Speicherbereich angefordert haben.
Die Anweisungen zur Implementierung dieser Speichersperre oder Speicherverriegelung können viele Formen haben; alle bauen jedoch darauf auf, daß ein Steuerwort so geprüft und geändert wird, daß, wenn ein Prozessor Zugriff zu einem Speicherblock hat und ein weiterer Prozessor versucht, Zugriff zu einem Speicherblock zu erlangen, dem das Steuerwort zugeordnet ist (beispielsweise ein Block von 4 bis 16 Wörtern), er die Kontrolle nicht übernehmen kann. Einige der für diese Anweisungen verwendeten Begriffe sind "biased-fetch", prüfen-und-setzen, inkrementieren-und-prüfen oder bedingter Ersatz. Allen gemeinsam ist, daß sie ein Wort eingeben, das Wort prüfen und nach erfolgreicher Prüfung das Wort so ändern, daß ein nachfolgender Prozessor, der die gleiche Prüfung versucht, die Kontrolle nicht übernehmen kann.
Um dies zu erreichen, müssen Zugang zur Prüfung und Änderung des Steuerwortes anderen Benutzern als unteilbarer Arbeitsvorgang erscheinen. Das heißt, einem zweiten Prozessor darf es nicht gelingen, ein Steuerwort zur Prüfung einzugeben, bevor nicht der erste Prozessor das Wort geändert hat. Bei älteren Geräten wurde dies häufig dadurch erreicht, daß ein Wort in einem Speicherzyklus eingegeben und geändert wurde ein Arbeitsvorgang von lesen-ändern-schreiben), oder daß die Speichereinheit für die Dauer von zwei oder mehr Zyklen gesperrt wurde, was verhinderte, daß andere Prozessoren Zugriff zu der Einheit erhielten, bevor die Prüf- und Modifikationssequenz beendet war.
Bei modernen Systemen sind häufig Cache-Speicher zusätzlich zum gemeinsam genutzten Speicher vorgesehen. Diese Cache-Speicher sind einem einzigen Prozessor zugeordnet, stehen anderen Prozessoren also nicht zur Verfügung. Bei einem solchen System sind Anweisungen zum Sperren zunehmend schwieriger mit den Anforderungen an eine angemessene Leistungsfähigkeit zu vereinbaren. Dies rührt daher, daß auf die Referenzsteuerzelle im gemeinsamen Speicher des Systems zugegriffen und diese modifiziert wird, um Zugriff, Prüfung und Modifikation als unteilbar erscheinen zu lassen. Obgleich in verschiedenen Prozessoren eines Mehr-Prozessorensystems verschiedene Prozesse ablaufen können und jeder dieser Prozessoren einen ihm allein zugehörigen Cache-Speicher besitzen kann, der eine Kopie der Steuerzelle beinhaltet, müssen einige Arbeitsvorgänge im Hauptspeicher ablaufen, der allen Prozessoren gemeinsam zugeordnet ist. Während die Leistungsfähigkeit von Prozessoren sich stark erhöht hat, sind die Zugriffzeiten zum Hauptspeichersystem verhältnismäßig konstant geblieben. Dadurch erscheinen Sperranweisungen, die den langsameren Speichern zugeordnet sind, wesentlich langsamer als andere Anweisungen, die aus den zugeordneten Cache-Speichern ohne Rücksicht auf andere Prozessoren ausgeführt werden können. Die längere Ausführungszeit dieser Anweisungen gegenüber nicht mit einer Sperre verbundenen Anweisungen dominiert in zunehmendem Maße Programmausführungszeiten.
In dem US-Patent Nr. 4 070 706, erteilt am 24. Juni 1978 an James Scheuneman und übertragen an Unisys Corporation, "Parallel Requestor Priority Determination und Requestor Address Matching in a Cache Memory System" wird eine Technik zum Steuern des Zugriffs auf adressierte Orte einer Hauptspeichereinheit durch eine Mehrzahl von Prozessoren beschrieben, die alle über einen eigenen Cache-Speicher verfügen. Jeder Prozessor koppelt seine Adressenzugriffanforderung an ein individuelles Register und sein individuelles Prioritätsanforderungssignal an eine Prioritätenwahlvorrichtung. Diese Prioritätsanforderungen wählen Prozessoren in einer vorherbestimmten Weise aus. Ist ein Prozessor ausgewählt, so vergleicht er die in seinem Register gespeicherte Adresse mit in seinem Cache-Speicher gespeicherten Adressen. Wird eine Entsprechung gefunden, werden Daten aus einem über das Inhaltsverzeichnis adressierbaren Ort im Cache-Speicher ausgelesen. Gibt es keine Entsprechung, werden die Daten aus der zugeordneten Adresse der Hauptspeichereinheit zurückgeholt.
Gemäß dem Scheuneman-Patent hat jeder Prozessor nur während seiner eigenen Prioritätperiode Zugriff zur Hauptspeichereinheit und muß auf diesen Zugriff warten, bis die Prioritätenwahlvorrichtung signalisiert, daß höhere Prioritätseinrichtungen ihren Zugriff beendet haben, Im Gegensatz zu älteren Einrichtungen ist jedoch die Entsprechungsbestimmung bei der Scheuneman-Vorrichtung vollständig und, falls erforderlich, ist die Adreßanforderung zur Übertragung an die Hauptspeichereinheit bereit, wenn die Prioritätsbestimmung abgeschlossen ist.
Der "Memory Block Protection Apparatus" des U.S.-Patentes 4 099 243, das am 4 Juli 1978 Benedict Palumbo erteilt wurde, beschreibt einen Blockschutz eines adressierten Abschnitts eines Speichers, der eine Sperre des adressierten Abschnittes ermöglicht, während nachfolgende Befehle zum gleichzeitigen Zugriff auf andere Adreßbereiche des Speichers erlaubt werden.
Im U.S.-Patent 3 735 360 "High Speed Buffer Operation in a Multi-Processing System", das am 22. Mai 1973 David Anderson et al erteilt wurde, wird ein System beschrieben, bei dem Adresseninformation von jedem Prozessor an die anderen Prozessoren allgemein adressiert wird, um Daten in den individuellen Speichern der Prozessoren ungültig zu machen und sicherzustellen, daß die von einem Prozessor des gemeinsamen Speichers erhaltenen Daten den neuesten Wert haben.
Patent Abstracts of Japan, Band 6, Nr. 100 (P-121)(978), vom 9.6.1982, und JP-A-57 33471 (Fujitsu K. K.) vom 23.2.1982 beschreiben ein System, bei dem ein Prozessor einen Blockbereich sperrt und eine Speicherzugriffanforderung, die von einem anderen Prozessor für einen anderen Speicherbereich abgegeben wird, zuläßt.
Die oben gewürdigten Schriften beschreiben keine auf Adressenbasis wirkende Sperre und keine Prioritätsschaltkreise der vorliegenden Erfindung zum Ausschluß nur eines spezifizierten Abschnittes des gemeinsamen Speichers, während gleichzeitiger Zugriff zu anderen Bereichen zugelassen wird.

Kurzbeschreibung der Zeichnungen

Die vorliegende Erfindung wird unter Hinweis auf die Zeichnungen beschrieben. Darin zeigt
Figur 1 ein Gesamtblockschaltbild eines gemeinsamen Speichers, auf den eine Mehrzahl von Speicherprozessoren gemäß der vorliegenden Erfindung Zugriff hat,
Figur 2 ein Blockdiagramm der auf Adressenbasis wirkenden Sperre und Prioritätsschaltkreise nach Figur 1,
Figur 3 eine Zeitablaufdarstellung für den Betrieb des Schaltkreises nach Figur 2 und
Figur 4 eine schematische Darstellung einer als Beispiel gewählten Prioritätszuordnungssequenz für den Schaltkreis nach Figur 2.

Technische Beschreibung der Erfindung

Die beanspruchte Erfindung, wie sie in Anspruch 1 definiert ist, bezieht sich auf eine Schaltung zur Errichtung einer Speichersperre, die den Sperrvorgang beschleunigt, ohne eine Speicherbank über mehrere Zyklen zu blockieren oder andere Prozessoren zu verlangsamen, die nicht einmal auf das gleiche Wort zugreifen. Nach der Erfindung ist es möglich, eine Sperrprüfung vollständig von einem zugeordneten Cache- Speicher durchführen zu lassen; diesen Cache-Speicher besitzt der die Sperre anfordernde Prozessor.
Sperranweisungen werden in zwei funktionelle Teile geteilt: (1) Es wird eine Sperre an der geprüften Adresse angelegt, so daß nur ein Prozessor die Kontrolle über die Speicheradresse bekommen kann, und (2) das tatsächliche Zugreifen auf und Prüfen der Steuerzelle und ihre nachfolgende Modifikation. Bei der bevorzugten Ausführungsform wird eine Sperre an einer spezifischen Adresse von dem Hauptspeicher-Untersystem durch Fernbedienung eingerichtet; andere Benutzer des Speichers werden also nicht daran gehindert auf das Hauptspeichersystem zuzugreifen. Lediglich der die Sperre anfordernde Prozessor wird durch die Zeitspanne beeinträchtigt, die nötig ist, um Kontrolle über die Testadresse zu erlangen.
Die Forderung, die Abänderung der Steuerzelle in einem einzigen unteilbaren Zyklus zu erreichen, entfällt ebenfalls, weil der Prozessor, der die Kontrolle über die Testzelle erreicht, diese behält, bis der ganze Arbeitsvorgang abgeschlossen ist. Versucht ein anderer Prozessor, dieselbe Adresse zu sperren, dann erfährt er, daß sie bereits gesperrt ist. Der neue Prozessor muß darum bis zur Aufhebung der Sperre durch den ersten Prozessor warten, was nur nach Abschluß des mit der Sperranweisung verbundenen Arbeitsvorganges geschieht.
Eine Prämisse der bevorzugten Ausführungsform ist, daß die Speichersperranweisungen den Zweck haben, das Problem gleichzeitiger oder fast gleichzeitiger Zugriffe auf dieselbe Steuerzelle zu lösen, dieser Vorgang jedoch verhältnismäßig selten auftritt. Es ist darum nicht kritisch, wenn die Dauer der Sperre sehr kurz gehalten wird. Die einzigen Verzögerungen für einen anderen Prozessor treten auf, wenn ein Prozessor mit einer früheren Anforderung die Kontrolle über die Zelle hat, für den der andere Prozessor eine Sperre anfordert.
Ist eine Sperre einmal eingerichtet und der Zugriff erteilt, dann kann der die Kontrolle ausübende Prozessor beginnen, die Zelle zu prüfen und möglicherweise zu modifizieren, ohne an die Hauptspeichereinheit zu gehen, wenn die Zelle bereits in seinem eigenen Cache-Speicher vorhanden ist. Wenn die Cache-Speicher als "Durchspeicher"-Einhejten ausgelegt sind, bei denen Daten im Hauptspeicher und im Cache-Speicher gespeichert sind, und der "Speicher"-Vorgang durch Rundspruch eine Ungültigmachung bewirkt, braucht sich der Prozessor auch nicht darum zu kümmern, daß möglicherweise das gleiche adressierte Wort im Cache-Speicher eines weiteren Prozessors vorhanden ist. Die Ausführung einer Sperranweisung kann dann auf die gleiche Weise fortschreiten wie jede andere Anweisung und sollte im wesentlichen die gleiche Cache-Speicher "Trefferquote" erzielen wie jede andere Anweisung, ohne auf andere Prozessoren einzuwirken, die nicht versuchen, Zugriff auf die gesperrte Zelle zu erlangen.
Die bevorzugte Ausführungsform befaßt sich mit der Einrichtung der Sperre an der Testzelle und nicht mit der Ausführung der Anweisung nach der Zulassung des Zugriffs auf die Zelle. Das bringt den Vorteil mit sich, daß die eigentlichen Ausführungsmittel nicht mehr in einen rigiden, unteilbaren Arbeitsvorgang eingebunden sind und daß die Ausführung der Anweisung als natürlicher Vorgang ablaufen kann.
Bei der beschriebenen Ausführungsform kann die Hardware entweder zentral zwischen der Mehrzahl von anfordernden Einrichtungen oder in den anfordernden Einrichtungen selbst dezentral angeordnet sein. Die Modifikationen, die erforderlich sind, um von einer Ausführung zur anderen zu gelangen, sind Fachleuten bekannt. Die beschriebene Ausführungsform dieser Erfindung ist als dezentralisierte Ausführung angelegt. Ein wichtiger Vorteil einer dezentralisiert angeordneten Sperrlogik besteht darin, daß lediglich eine Kabeltransitzeit zur Erlangung der Kontrolle erforderlich ist. Ist die Logik zentral vorgesehen, dann muß die Auswahl-Logik an den Prozessor ein Sperr-Erlaubnissignal geben, bevor die Kontrolle übernommen werden kann, was eine zweite Kabeltransitzeit erfordert. Bei einem zentralisierten Aufbau sollte weniger Logik genügen.
Nach dem hier erfindungsgemäß angewendeten Prinzip der Durchführung einer Sperrung einer Adresse, ist es erforderlich, daß Adressen zwischen Prozessoren übertragen werden, die Sperrvorgänge anfordern können, und daß die beschriebene Auswahllogik eingesetzt wird, um festzulegen, welcher der Prozessoren eine spezifische Adresse dann kontrolliert, wenn ein Konflikt auftritt zwischen zwei oder mehr Prozessoren, die Kontrolle über dieselbe Adresse anfordern.
Bei der beschriebenen Ausführungsform werden Kabel, die dazu dienen, ungültig zu machende Cache-Speicheradressen durch Rundspruch zwischen den Prozessoren zu verbreiten, ebenfalls dazu eingesetzt, die Adresse durch Rundspruch zu verbreiten, für die eine Sperre angefordert wird. Das Interface ist so synchronisiert, daß alle Prozessoren Adressen zur selben Zeit durch Rundspruch verbreiten. Da die Transitzeit der durch Rundspruch verbreiteten Adressen bekannt ist, ist es möglich, das Prüfen von Adressen so zu synchronisieren, daß alle Prozessoren ihre Adressen mit jenen vergleichen können, die von anderen Prozessoren zur selben Zeit durch Rundspruch verbreitet werden, wenn ein oder mehrere Prozessoren gleichzeitig eine Adressensperrung versucht haben.
Einem Prozessor, der früher als ein anderer Prozessor seine Sperranforderung durch Rundspruch verbreitet, wird Priorität eingeräumt, weil seine Anforderung zeitlich vor dem Anforderungs-Rundspruch eines anderen Prozessors lag. Die Auswahl, welcher Prozessor die Kontrolle erlangt, ist ein zweistufiger Vorgang; dabei wird die Kontrolle zuerst jenen Prozessoren gegeben, die zuerst übertragen, oder es wird bei gleichzeitiger Anforderung ein Prozessor über Auswahlvorschriften ausgewählt.
Die Auswahl kann einfach in form der Zuordnung von Nummern für jeden Prozessor geschehen, wobei nach der niedrigsten (oder höchsten) Nummer ausgewählt wird, wenn dieselbe Adresse angefordert wird. Es können auch Prioritätszuordnungen eingesetzt werden, die auf einer festgelegten Basis rotieren oder die abhängig von Betriebsbedingungen variabel gestaltet sind, wie dies aus dem Stand der Technik bekannt ist.
Ein Prozessor erlangt Kontrolle, wenn die Adresse, die er zu sperren versucht, keiner der Adressen von anderen Prozessoren zum Zeitpunkt des Rundspruches entspricht, oder wenn nach Ablauf der Transitzeit seiner Anforderung nicht eine weitere Anforderung für dieselbe Adresse gleichzeitig von einem Prozessor mit höherer Priorität durch Rundspruch verbreitet wurde. Wird eine Sperre nicht erzielt, muß der anfordernde Prozessor auf eine Sperrfreigabe durch den Prozessor warten, dem die Kontrolle über die Adresse zugeteilt wurde, bevor er Kontrolle über die Adresse erlangen und eine Operation an dem adressierten Wort durchführen kann.
Nachdem der anfordernde Prozessor Kontrolle über die Sperrzelle erlangt hat, hat er Zugriff zu dem Wort, kann die erforderliche Prüfung durchführen und, wenn erfolgreich, das Wort ändern, wodurch das Wort im Speicher auf den neuesten Stand gebracht und alle Kopien in anderen Cache-Speichern ungültig gemacht werden, Die Kontrolle über die gesperrte Adresse wird dann aufgehoben, so daß ein anderer Prozessor Kontrolle erlangen und seine Prüfung durchführen kann. Die Zeitgabe für die Aufhebung der Sperre muß so angelegt sein, daß sie die Modifikation, die das Steuerwort im gemeinsamen Speicher auf den neuesten Stand bringt, und nötigenfalls das Ungültigmachen derjenigen Adresse in den Cache-Speichern anderer Prozessoren begleitet, so daß diese Prozessoren bei Erlangung der Kontrolle immer das Steuerwort sehen, das auf dem neuesten Stand ist.
Es wird darauf hingewiesen, daß eine Modifikation des Wortes durch den die Kontrolle ausübenden Prozessor von dem Erfolg der Prüfbedingung abhängt. Ist die Prüfung erfolglos (z.B. zeigt eine Software-Flag an, daß ein anderer Prozessor Kontrolle über die Anordnung hat, die von dem Steuerwort geschützt ist), so bleibt das Steuerwort unverändert und eine Aufhebung der Sperre wird ausgegeben; andere Cache-Speicher werden jedoch nicht ungültig gemacht, da an dem adressierten Wort keine Veränderung durchgeführt wurde.
Die vorliegende Erfindung wird anhand des Gesamt-Blockdiagramms der Figur 1 dargestellt, worin die Sperrschaltungen nach der Erfindung mit 10A, 10B, 10C und 10D bezeichnet und den Prozessoren A, B, C und D zugeordnet sind, denen jeweils individuelle, für schnellen Zugriff ausgelegte Cache-Speichereinheiten 12A, 12B, 12C bzw. 12D assoziiert sind. Für alle Prozessoren gemeinsam ist eine gemeinsame Hauptspeichereinheit 18 vorgesehen; ein System-Taktgeber 15 treibt alle Elemente des Systems.
Daten und Adressen werden zwischen den Cache-Speichereinheiten und der gemeinsamen Hauptspeichereinheit in Bussen 20A, 20B, 20C und 20D übermittelt. Auf den Verbindungsbussen 30 - 52 zwischen den Sperrschaltungen werden verschiedene Signale transportiert, die von dem Sperrsystem benötigt werden. Die Pfeil spitzen am Ende der die Busse darstellenden Linien zeigen die Richtung des Informationsflusses an. Steuersignale werden zusammen mit Daten und Adressen zwischen Hauptspeichereinheit und Cache-Speichern auf den Leitungen 20A, 20B, 20C und 20D gesendet. Das Signal "Sperre genehmigt" wird für jeden der Prozessoren auf den Bussen 30 - 52 gesendet. Adressen, die von den zugeordneten Prozessoren an besondere Sperrschaltungen gesendet werden, werden ebenfalls an alle anderen Sperrschaltungen als "Sperr-Rundspruch"-Signale auf den Bussen 30 - 52 übertragen. Diese Busse können auch eingesetzt werden, um Adressen durch Rundspruch zu verbreiten oder Daten, die in jedem Cache-Speicher gespeichert sind, ungültig zu machen oder auf den neuesten Stand zu bringen, und um sicherzustellen, daß die Informationswiedergewinnung in der Hauptspeichereinheit auf dem laufenden gehalten wird. Ebenso werden "Sperrfreigabe"-Signale nach Beendigung eines gesperrten Arbeitsvorganges auf den Bussen 30 - 52 übertragen.
In Figur 2 ist ein Basisblockdiagramm einer der Sperrschaltungen 10A, 10B, 10C und 10D nach Figur 1 gezeigt, die eingesetzt wird, um den Sperrvorgang für den Prozessor 16A durchzuführen. Bei der Durchführung der Sperrung nach der vorliegenden Erfindung ist es erforderlich, daß die zu sperrende Adresse den anderen Prozessoren des Systems, die ebenfalls eine Sperr-Fähigkeit besitzen, über Rundspruch bekanntgegeben wird. Die Schnittstelle zwischen den Prozessoren hängt von der Adresse ab, die für eine Sperre geprüft wird (z.B. die Adresse im Primär-Sperr-Register 50A in Figur 2). Es wird darauf hingewiesen, daß es nicht absolut erforderlich ist, nur eine spezifische Adresse zu sperren. Im Rahmen dieser Erfindung kann ein Block oder eine Gruppe von Adressen gesperrt werden, indem ein Abschnitt des Adressencodes decodiert wird, um den Block zu bezeichnen.
Die in jedem der Primär-Sperr-Register, wie z.B. dem Sperr-Register 50A, gespeicherten Sperradressen liefern Sperr-Rundspruch-Signale an die anderen Sperrschaltkreise 10B, 10C und 10D, so daß die von den anderen Prozessoren empfangenen Adressen mit seiner Adresse in den Komparatoren 52A, 52B und 52C verglichen werden können. Eine Form dieser Komparatoren können inhaltsorientiert adressierbare Speicher sein, obgleich auch andere, Fachleuten bekannte Komparatoren eingesetzt werden können. Wird eine angeforderte Adresse von einem anderen als dem Prozessor 16A empfangen, so wird diese Adresse eingefangen und in dem jeweiligen Register 50A, 50C oder 50D festgehalten, bis von einer gemeinsamen Speichereinheit 18 ein Sperrfreigabesignal empfangen wird.
Die Register 50B, 50C und 50D speichern diese Adressen vom Empfangszeitpunkt der Anforderung bis zum Empfangszeitpunkt der Freigabe. Es sollten N-1 dieser Register vorgesehen sein, wobei N die Anzahl der anfordernden Prozessoren des Systems ist. Bei diesem Beispiel sind drei Register dargestellt, die ein System aus vier Prozessoren unterstützen. Wie Fachleuten bekannt ist, kann mehr als ein Register pro anforderndem Prozessor eingesetzt werden.
In der Schaltung werden zwei Prüfungen durchgeführt, bei denen die Komparatoren verwendet werden: eine Prüfung unmittelbar nach der Übertragung der Anforderung und eine zweite nach der Übertragungszeit der Anforderung zwischen den Prozessoren. Diese Zeit wird von dem physischen Aufbau des eingesetzten Systems bestimmt, wobei die Länge von Leitungen und die Schaltungsgeschwindigkeit sowie andere faktoren, die die Signalübertragungszeiten beeinflussen können, zu berücksichtigen sind.
Bei einer ersten Prüfung werden alle Komparatoren (d.h. 52A, 52B und 52C) geprüft, denn sie wird während der Übertragungszeit durchgeführt. Es werden jene Adressen geprüft, die zur Zeit der Prüfung bereits von einem anderen Prozessor gesperrt wurden. Ein gleicher Zustand in einem der Komparatoren zeigt an, daß die an andere Prozessoren durch Rundspruch verbreitete Adresse bereits gesperrt ist.
Wird bei der ersten Prüfung keine Entsprechung gefunden, dann ist noch eine zweite Prüfung erforderlich, um die Konflikte zu lösen, die auftreten können, wenn zwei oder mehr Prozessoren gleichzeitig versuchen, dieselbe Adresse zu sperren. Diese Prüfung wird unmittelbar nach der Übertragungszeit des Sperr-Rundspruch-Signals durchgeführt. Hätte ein weiterer Prozessor eine Adresse zur selben Zeit durch Rundspruch verbreitet, dann wäre diese Adresse zu dieser Zeit in dem zugeordneten Sperr-Register vorhanden und könnte geprüft werden. In diesem besonderen Fall würden die beiden Prozessoren das Sperr-Rundspruch-Signal des jeweils anderen Prozessors zur selben Zeit empfangen. Darum ist ein Auswahlmittel erforderlich, das festlegt, welcher Prozessor Vorrang hat und welcher zu warten hat. Die Lösung hierfür ist einfach, indem eine beliebige Prioritätszuordnung über Prozessornummern vorgenommen wird.
In Figur 2 ist die Logik für eine Prioritätswahl als eine Serie von "ODER"-Gattern und "UND"-Gattern, denen Abtastzeitgeberimpulse nach Figur 3 zugeführt werden. Taktgebersignale werden den Sperrsteuereinheiten über Leitungen 17 zugeführt, den Prozessoren über Leitungen 19, den Cache-Speichern über Leitungen 21 und der Hauptspeichereinheit über Leitung 23.
Das Zeitgebersignal T2 folgt unmittelbar auf den Rundspruch der angeforderten Adresse und dann wieder einen Zyklus später auf die Übertragungszeit der Adresse von einem Prozessor zum anderen. Das mit T1 bezeichnete Signal, das den "ODER"-Schaltungen 54A, 54B, 54C zugeführt wird, ist die erste Zeitabtastung, die eine Gleichheitsüberprüfung aller Komparatoren 52A, 52B, 52C erzwingt. Während der zweiten Abtastung T2 werden nur solche Komparatoren auf Gleichheit geprüft, die eine Freigabe für die Eingangsleitungen 56A, 56B, 56C haben.
Die Leitungen 56A, 56B und 56C sind mit Schaltbrücken versehen oder werden auf einem definierten "0"- oder "1"-Logikpegel gehalten, um die gewünschte Priorität bei gleichzeitigen Anforderungen herzustellen. Figur 4 ist eine schematische Darstellung eines Systems, bei dem eine Prozessorpriorität derart vorgesehen ist, daß die Prozessoren eine Prioritätsfolge von 16A, 16B, 16C, 16D haben.
Wird während einer der beiden Abtastzeiten T1 oder T2 eine Entsprechung gefunden, dann muß der Prozessor, dessen angeforderte Adresse in einem Sperr-Register 50B, 50C oder 50D ist, warten, bis die zugeordnete Sperrfreigabe empfangen wird, bevor er mit der Sperranweisung fortfahren kann. Dies wird über Signale erreicht, die über die UND- Gatter 58A, 58B, 58C gekuppelt sind. Die UND-Gatter sind über den Setz- oder 5-Eingang mit Verriegelungselementen 60A, 60B und 60C verbunden, um den Zustand der Komparatoren zu den beiden Abtastzeiten festzuhalten. Ausgefüllte Pfeil spitzen bei den Eingängen in Figur 2 zeigen ein Gatter an, das durch "hohe" logische Signalpegel aktiviert wird, während unausgefüllte Pfeil spitzen an den Eingängen ein Gatter bezeichnen, das durch "niedrige" logische Signalpegel aktiviert wird. Tritt ein Konflikt ein zwischen der im Register 50A gespeicherten Adresse und einem der Register 50B, 50C, 50D, dann werden die zugeordneten Verriegelungselemente als Anzeige dafür gesetzt, daß Anforderungen mit höherer Priorität unerledigt sind.
Wenn das zugeordnete Sperrfreigabesignal von der Hauptspeichereinheit am Rückstell- oder R-Signaleingang der entsprechenden Verriegelungselemente empfangen wird, werden diese freigegeben und die Bearbeitung kann beginnen. Das einzelne UND-Gatter 62 an der Spitze stellt fest, daß alle Verriegelungselemente freigegeben sind und erzeugt ein Sperrgenehmigungssignal, was eine Ausführung der angeforderten Anweisungen unter Verwendung der an der angeforderten Adresse vorhandenen Daten ermöglicht und dieses Register von weiteren Prüfungen ausschließt, bis eine weitere Sperranforderung empfangen wird.
In Figur 4 ist ein repräsentatives Prioritätsschema dargestellt, das sich darauf bezieht, daß die Prozessoren eine Prioritätsfolge von 16A, 16B, 16C, 16D haben, wobei Prozessor 16A die höchste und Prozessor 16D die niedrigste Priorität hat. Sektion I stellt die Schaltung für Prozessor 16A dar (dargestellt durch den Buchstaben A) und entspricht Figur 2. Prioritätsverbindungsleitungen 56A, 56B und 56C sind ebenfalls für die Sperrschaltungen (nicht dargestellt) dargestellt, die den Prozessoren 16B, 16C, 16D zugeordnet sind. Wenn unter diesen Leitungen eine "0" angegeben ist, zeigt dies an, daß sie sich auf einem niedrigen logischen Pegel befinden; ist eine "1" unter diesen Leitungen angegeben, so sind sie auf einem "hohen" logischen Pegel. In Sektionen II, III und IV der Figur 4 ist die Durchführung der Priorität für die Prozessoren 16B, 16C bzw. 16D dargestellt. Dabei stellt Sektion II den Prozessor 16B, Sektion III den Prozessor 16C und Sektion IV den Prozessor 16D dar. An den Leitungen 56A, 56B, 56C zu den ODER- Gattern der mit jedem der Prozessoren assoziierten Schaltungen wird der der Durchführung des gewünschten Prioritätsschemas zugeordnete logische Pegel angegeben. Da bei der vorliegenden Erfindung eine einfache Prioritätssteuertechnik angewendet werden kann, kann das Prioritätsschema schnell, sogar von einem Zyklus zum nächsten, geändert werden, indem lediglich die logischen Pegel an den zwölf Leitungen (bei einer Vier-Prozessor-Anlage) geändert werden, die den in Aussicht genommenen ODER-Gattern zugeführt werden.

Claims

1. Sperrsteuerschaltung (Figur 2) für einen anfordernden Prozessor (16A), der sich ein gemeinsam adressierbares Speichermittel (18) mit anderen Prozessoren (16B, 16C, 16D) eines Datenverarbeitungssystems teilt, mit

- einer Mehrzahl von mit dem anfordernden Prozessor gekoppelten Speichermitteln zum Speichern eines Anforderungsadressencodes, der einen Abschnitt des adressierbaren Speichermittels darstellt, für den der anfordernde Prozessor eine Sperre (50A) anfordert, und zum Empfang und Speichern von Anforderungsadressencodes, die Abschnitte des adressierbaren Speichermittels darstellen, für den einer der anderen Prozessoren eine Sperre (50B, 50C, 50D) angefordert haben,

- Signalmitteln (Figur 3) zur Erzeugung eines ersten Zeitgebersignals (T1), das im wesentlichen unmittelbar auf die Übertragung eines Anforderungsadressencodes durch den anfordernden Prozessor folgt, und eines zweiten Zeitgebersignals (T2), das zuerst im wesentlichen unmittelbar auf die Übertragung der Anforderungsadressencodes von den anderen Prozessoren folgt und noch einmal später im wesentlichen unmittelbar auf die Übertragungszeit der übertragenen Anforderungsadressencodes von den anderen Prozessoren an den anfordernden Prozessor folgt, und zur Erzeugung einer Mehrzahl von dritten Signalen (56A, 56B, 56C), die jeweils einen ersten und einen zweiten Binärpegelzustand haben und von denen jedes einem der anderen Prozessoren zugeordnet ist, wobei jedes der dritten Signale eine höhere Prioritätsstufe für einen zugeordneten der anderen Prozessoren gegenüber dem anfordernden Prozessor darstellt, wenn das zugeordnete dritte Signal einen ersten Binärpegel hat und eine niedrigere Prioritätsstufe, wenn das zugeordnete dritte Signal einen zweiten Binärpegel hat (Figur 4),

- Vergleichsmitteln (52A, 52B, 52C; 54A, 54B, 54C; 58A, 58B, 58C), die verbunden sind mit der Mehrzahl von Speichermitteln und den Signalmitteln für den Empfang der Anforderungsadressencodes und der ersten, zweiten und dritten Signale und zum individuellen Vergleichen des Anforderungsadressencodes des anfordernden Prozessors mit jedem der Anforderungsadressencodes der anderen Prozessoren zu dem ersten Zeitpunkt, wenn sowohl das erste als auch das zweite Signal vorhanden sind, um einen ersten Vergleich durchzuführen, und beim Auftreten des zweiten Signals zu einem späteren Zeitpunkt zur Prüfung, ob eines der dritten Signale ebenfalls vorhanden ist und sich in einem ersten Binärpegel befindet, um einen zweiten Vergleich durchzuführen; zur Erzeugung von Vergleichssignalen, die Indikatoren des ersten und zweiten Vergleiches sind, und

- Sperrgenehmigungsmitteln (60A, 60B, 60C; 62), die mit den Vergleichsmitteln verbunden sind für den Empfang der Vergleichssignale und zur Erzeugung eines Sperrgenehmigungssignals an den Prozessor, das diesem ermöglicht, für die gewünschten Abschnitte des gemeinsam adressierbaren Speichermittels nur dann eine Sperre zu erlangen, wenn die Vergleichssignale anzeigen, daß weder beim ersten noch beim zweiten Vergleich eine Entsprechung aufgetreten ist.

2. Sperrsteuerschaltung nach Anspruch 1, dadurch gekennzeichnet, daß jedes der Speichermittel einen getrennten Registerspeicher (50A, 50B, 50C, 50D) zum Empfang und Speichern jedes der Anforderungsadressencodes für jeden der Prozessoren enthält.

3. Sperrsteuerschaltung nach Anspruch 2, dadurch gekennzeichnet, daß das Vergleichsmittel eine Mehrzahl von Vergleichselementen (52A, 52B, 52C) enthält, die je erste und zweite Sätze von Ein- und Ausgängen aufweisen, deren Zahl gleich der Anzahl der für die anderen Prozessoren vorgesehenen Registerspeicher ist, wobei der erste Eingangssatz jedes Vergleichselementes mit einem dem anfordernden Prozessor zugeordneten Registerspeicher verbunden ist und sein zweiter Eingangssatz mit den anderen Prozessoren zugeordneten Registerspeichern verbunden ist zum Vergleich der Sperranforderungsadressencodes des anfordernden Prozessors mit den Anforderungsadressencodes der anderen Prozessoren und zum Erlangen der Sperre für gemeinsame Adressenspeichermittel.

4. Sperrsteuerschaltung nach Anspruch 3, dadurch gekennzeichnet, daß das Vergleichsmittel Sperrgattermittel mit Sperrgatterelementen (54A, 54B, 54C, 58A, 58B, 58C) aufweist, deren Zahl der Anzahl von Vergleichselementen entspricht, und daß die Sperrgattermittel mit dem Ausgang eines der Vergleichselemente zum Empfang seines Ausgangssignals und mit den Signalmitteln zum Empfang des ersten und des zweiten Zeitgebersignals und desjenigen der Mehrzahl von dritten Signalen verbunden ist, das ein Indikator für die Prioritätsstufe des anderen anfordernden Prozessors ist.

5. Sperrsteuerschaltung nach Anspruch 4, dadurch gekennzeichnet, daß das Vergleichsmittel Verriegelungsmittel enthält, die Verriegelungselemente (60A, 60B, 60C) aufweisen, deren Zahl der Anzahl der Sperrgattermittel entspricht und von denen jedes mit einem der Sperrgattermittel (58A, 58B, 58C) zum Empfang seines Sperrsignals verbunden ist und zur Anzeige der Sperrbelegung eines Abschnittes des adressierbaren Speichermittels durch einen anderen der zugeordneten Prozessoren bis zu dem Zeitpunkt, wo ein Sperrfreigabesignal (Sperrfreigabe B,C, D) dem zugeordneten Verriegelungselement durch den anderen der zugeordneten Prozessoren, der mit den Sperrgattermitteln verbunden ist, zugeführt wird.