DE3853574T2

DE3853574T2 - Steuerung von Benutzerantworten in einem Übertragungsbus.

Info

Publication number: DE3853574T2
Application number: DE3853574T
Authority: DE
Inventors: Michael J K Nielsen
Original assignee: Digital Equipment Corp
Current assignee: Digital Equipment Corp
Priority date: 1987-11-23
Filing date: 1988-11-21
Publication date: 1996-01-25
Anticipated expiration: 2008-11-22
Also published as: DE3853574D1; US4920486A; JPH061458B2; CA1324192C; EP0318221A3; EP0318221A2; EP0318221B1; JPH021037A

Description

Kurze Zusammenfassung der Erfindung

Computersysteme können mit mehreren Prozessoren aufgebaut sein, die konkurrierend parallel arbeiten. In derartigen Systemen arbeiten die verschiedenen Prozessoren praktisch unabhängig, müssen jedoch von Zeit zu Zeit Informationen zwischen Prozessoren oder zwischen einem Prozessor und anderen Systemkomponenten wie Eingabe/-Ausgabe-Vorrichtungen übertragen. Für die Durchführung dieser Informationsübertragungen ist ein Übertragungsbus vorgesehen, der an die Prozessoren und andere Systemkomponenten angeschlossen ist und Daten von jedem Benutzer zu einem beliebigen anderen übertragen kann. Ein derartiger Bus ist seinem Betrieb sehr flexibel, es ist jedoch notwendig, ein gewisses Verfahren einzusetzen, um eine geordnete Benutzung des Übertragungsbusses zu gewährleisten. Diese Erfindung betrifft die Steuerung des Zugangs zu einem von mehreren Benutzern gemeinsam genutzten Übertragungsbus, um eine geordnete Verwendung des Busses durch eine Vielzahl von Benutzern zu gewährleisten.
Die Erfindung betrifft gemäß den unabhängigen Ansprüchen einen Vielkanalarbitrationsbus, bei dem jeder Benutzer einem seiner verschiedenen Kanäle zugeordnet ist und eine Prioritätsliste oder Vorrangstufentabelle für jeden Benutzer vorgesehen ist, die die gegenwärtige Priorität des zugeordneten Benutzers gegenüber jedem anderen Benutzer anzeigt. Eine Wettbewerbszeitspanne (contention interval) und eine Benutzungssignalzeitspanne (use-signal interval) werden von einem Zustandsgerät bzw. einer Maschinenzustandseinrichtung (state machine) definiert, das bzw. die mit jedem Benutzer verbunden ist. Während der Wettbewerbszeitspanne fordert jeder Benutzer, der zu diesem Zeitpunkt um eine Benutzung des Übertragungsbusses nachsucht, durch Übertragen eines Bus-request-Signals dessen Benutzung an. Jeder Benutzer führt eine Analyse der Bus-request-Signale durch, um sicherzustellen, ob er eine vorherrschende Priorität zur Benutzung des Übertragungsbusses für eine Transaktion besitzt, und der Zugang wird entsprechend gewährt. Während der Benutzungssignalzeitspanne überträgt ein gerade den Übertragungsbus nutzender Benutzer ein In-Benutzung-Signal. Das In-Benutzung-Signal wird von jedem Benutzer verwendet, um seine Prioritätsliste mit der Wirkung zu aktualisieren, daß dem letzten Benutzer eine Priorität gegeben wird, die für die nächste Anforderung zum Einleiten einer Transaktion niedriger als alle anderen ist.
Ein ähnliches Bus-Arbiter-System ist in dem Dokument ELEKTRONIK, Band 29, Nr. 3, April 1980, G. Färber: "Ein dezentralisierter fairer Bus-Arbiter" offenbart. Die vorliegende Erfindung ist jedoch auf die folgende Situation ausgerichtet, die in dem vorstehend genannten Dokument nicht behandelt wurde.
Für Transaktionen, die eine Antwort von einem Systembenutzer erfordert, der nicht der die Transaktion einleitende ist, wird eine zweite Anforderungsrunde durchgeführt, um zu bestimmen, ob irgendein Benutzer qualifiziert ist zu antworten, und im positiven Fall, welcher in die Lage versetzt wird, dies zu tun. Wenn die Antwortanforderung keine Anforderer ergibt, leitet das System sofort die Anforderung für eine neue Transaktion ein; wenn es einen oder mehrere qualifizierte Antworter gibt, wird einer ausgewählt und in die Lage versetzt zu antworten.

Kurze Beschreibung der Zeichnungen

Es zeigen:
Figur 1 schematisch ein Zugangssteuerungssystem, das das Antworten einer Vielzahl von Busbenutzern eines Übertragungsbusses gemäß der Erfindung steuert,
Figur 2 als Blockdiagramm einen Zugangs-Controller, der in dem Antwortsteuerungssystem von Figur 1 verwendet wird,
Figur 3 Einzelheiten des Prioritätszustandsspeichers und der Arbitrationslogik, die in dem Zugangs-Controller von Figur 2 verwendet werden,
Figur 4 im Detail den Aufbau von Übergabeschlüsseln, die in dem Zugangssteuerungssystem von Figur 1 verwendet werden,
Figur 5 Timing- bzw. Taktsignale, die in dem Zugangssteuerungssystem von Figur 1 verwendet werden,
Figur 6 die Operationen eines in der Erfindung verwendeten Statusgeräts,
Figur 7 die Anschlüsse und Verbindungen der Aktualisierungsschaltung des Zugangs-Controllers von Figur 2 und
Figur 8 das Verbindungsschema der Übergabeschlüssel des Zugangssteuerungssystems von Figur 1.

Ausführliche Beschreibung

Wie aus den Figuren zu ersehen ist, steuert das Zugangssteuerungssystem 10 gemäß der Erfindung die Nutzung des Übertragungsbusses 14 durch Prozessorbenutzer 12, 13 und E/A-Vorrichtung 16. Information wird auf den Übertragungsbus in festgelegten zusammengehörigen sequentiellen oder parallelen Operationen übertragen, die als Transaktion bezeichnet werden. Es können verschiedene Arten von Transaktionen mit verschiedenen Operationen vorkommen, wie beispielsweise Lesen oder Schreiben in den Cache-Speicher eines anderen Prozessors, Bestätigung von Interrupts bzw. Unterbrechungen, Lesen von oder Schreiben in Ein4Ausgabevorrichtungen. Bestimmte Transaktionen, insbesondere die Interrupt-Bestätigung und das Speicherlesen, werden von einem Benutzer eingeleitet und erfordern eine Antwort von einem anderen Benutzer.
Das insbesondere in Figur 1 gezeigte Zugangssteuerungssystem 10 umfaßt einen Arbitrationsbus 21 mit n Kanälen, einen Steuerungsbus 22 und einen Bustaktgeber 23. Der Bustaktgeber erzeugt Taktsignale, die eindeutige Zeitinkremente definieren, welche das ganze Bussystem synchronisieren, und er leitet diese an alle Busbenutzer. Der Taktgeber leitet ein erstes periodisches Signal (den Takt A), dessen Anstiegsflanke den Beginn eines neuen Zeitinkrements definiert, an alle Busstationen. Der Taktgeber sendet auch ein zweites Signal aus (den Takt B), das gegenüber dem Takt A phasenverschoben ist und dessen Anstiegsflanke einen Zeitpunkt gegen Ende jedes Zeitinkrements definiert. Der Takt B wird im allgemeinen dazu verwendet, Signale in Latches einzuspeisen, nachdem die durch die Ausbreitung hervorgerufenen Einschwingvorgänge abgeklungen sind. Die Taktsignale sind in Figur 5 dargestellt.
Ein repräsentativer Benutzer 12 ist mit einem zugeordneten Zugangs-Controller 17 über die Bus-request-Leitung 19, über die Antwort-bereit-Leitung (response ready line) 50, über die Gewährungs- bzw. Zuteilungsleitung 20 und über die Antwortberechtigungsleitung (response enable line) 51 und mit dem Übertragungsbus 14, dem Steuerungsbus 22 und dem Bustaktgeber 23 verbunden. Der Zugangs-Controller 17 ist direkt mit dem Steuerungsbus 22 und dem Bustaktgeber 23 und über einen Übergabeschlüssel 24 mit dem Arbitrationsbus 21 verbunden. Der Benutzer 12 ist zusammen mit seinem Zugangs-Controller 17 mit dem Übergabeschlüssel 24, einem Initialisierungsschlüssel 38 und dem Übertragungsbus 14 über einen Standardport bzw. -anschluß 47 verbunden. Der Benutzer 13 und weitere Benutzer einschließlich der E/A-Vorrichtung 16 sind wie der Benutzer 12 angeschlossen.
Der Zugangs-Controller 17 umfaßt eine Übertragungsleitung 25, (n - 1) Überwachungsleitungen 26, eine Steuerungsschaltung 27, eine Treiberschaltung 28, einen Prioritätszustandsspeicher 29, eine Arbitrationslogik 30, eine Zugangszuteilungsschaltung 31 mit einem Zuteilungslatch 37, einer Aktualisierungsschaltung 32, einer Keine-Anforderung-Schaltung (no-bid circuitry) 33, einem Initialisierungsgatter 39 und einem Aktualisierungsgatter 34, die wie in Figur 2 gezeigt verbunden sind.
Weitere Einzelheiten des Prioritätszustandsspeichers 29 und der Arbitrationslogik 30 sind in Figur 3 gezeigt. Der Prioritätszustandsspeicher 29 umfaßt (n - 1) Speicherelemente 35 mit zwei Zuständen, vorteilhafterweise Flip-Flops. Von den Speicherelementen 35 gehen Ausgänge parallel zu (n-1) UND-Gliedern 36. Überwachungsleitungen 26 gehen ebenfalls parallel zu den UND-Gliedern 36. Ausgangssignale der UND-Glieder 36 werden mit dem Signal T auf der Übertragungsleitung 25 wie gezeigt kombiniert, um das Signal P zu erzeugen.
Die Aktualisierungsschaltung 32 wie sie insbesondere in Figur 7 gezeigt ist, verbindet die Übertragungsleitung 25 mit den Set-Eingängen jeder der Speicherelemente 35 mit zwei Zuständen und verbindet die Überwachungsleitungen 26 jeweils mit den Reset-Eingängen jedes der Speicherelemente 35. Diese Verbindungen erfolgen durch das Aktualisierungsgatter 34. Die Ausgangsleitungen 40 aus dem Initialisierungsschlüssel 38 sind durch das Initialisierungsgatter 39 mit den Set- und Reset-Eingängen der Speicherelemente 35 verbunden.
Die Steuerungsschaltung 27 enthält ein zyklisch durchlaufendes Zustandsgerät 46, das den Betrieb des Zugangs-Controllers 17 steuert und mitverfolgt, was in dem Übertragungsbus geschieht. Der Betrieb dieses Zustandsgeräts ist in Figur 6 diagrammartig dargestellt und wird in Zusammenhang mit dem Systembetrieb näher diskutiert.
Ein Zugangs-Controller 18 und weitere Zugangs-Controller sind identisch mit dem Zugangs-Controller 17.
Beim Betrieb des Systems führt ein Benutzer typischerweise quasi-unabhängig Verarbeitungsanweisungen unter Verwendung seines eigenen Cache-Speichers und mit seinem eigenen Synchronisationstakt durch, der nicht derjenige des Busses oder anderer Benutzer ist. Von Zeit zu Zeit führen die ausgeführten Berechnungen dazu, daß ein Informationsaustausch mit einer anderen Systemkomponente erforderlich wird. Typische Ereignisse, die einen Informationsaustausch erfordern, sind der Bedarf an Daten, die in dem Cache-Speicher eines anderen Benutzers gespeichert sind, das Erfordernis zum Aktualisieren von Daten, die im Speicher eines anderen Benutzers gespeichert sind, und das Erfordernis, Informationen von einer E/A-Vorrichtung zu erhalten, um eine Programmunterbrechung zu verarbeiten. Information wird über den Übertragungsbus in einer Transaktion ausgetauscht. Es können verschiedene Arten von Transaktionen auftreten, aber jede besitzt ein definiertes Format, das spezifiziert, was auf welcher Buskomponente und in welcher Reihenfolge übertragen wird. ln dem hier beschriebenen System ruft das Format den Transaktionstyp identifizierende Signale, die auf dem Steuerungsbus laufen, und ausführliche Informationen wie Adressen und Daten ab, die auf dem Übertragungsbus laufen. Wenn ein Benutzer über das Bussystem kommunizieren will bzw. muß, speichert er die Information zum Ausführen einer Transaktion in Ausgangspuffer und überträgt dann an seinen Zugangs-Controller 17 ein Bus-request-Signal R auf der Bus-request-Leitung 19, welches anzeigt, daß er den Übertragungsbus benutzen möchte und bereit zum Einleiten einer Transaktion ist. Wenn ein Zuteilungssignal G auf der Zuteilungsleitung 20 von dem Zugangs-Controller 17 empfangen wird, beginnt der Benutzer eine Bustransaktion.
Ein Benutzer überwacht auch fortlaufend die Busse, um Signale zu erfassen, die anzeigen, daß eine von einem anderen Benutzer eingeleitete Transaktion vom überwachenden Benutzer erfordert, eine Antwort zu geben. Wenn er ein derartiges Signal erfaßt, lädt er die Antwort in Ausgangspuffer, und wenn diese bereit sind, sendet er ein Antwort-fertig-Signal R' auf Leitung 50 zu seinem Controller 17. Wenn dann ein Antwortberechtigungssignal E auf Leitung 51 empfangen wird, beginnt er die Übertragung der Antwort.
Der Betrieb des Zugangs-Controllers 17 wird von der Steuerungsschaltung 27 organisiert, die unter Bezug auf ihr in Figur 6 diagrammartig dargestelltes Zustandsgerät erläutert ist. Dieses Zustandsgerät geht ohne besonderen Startpunkt über Schleifen von Zustand zu Zustand über. Es wechselt mit dem Beginn jedes von dem Takt A gegebenen Zeitinkrements von einem Zustand in den nächsten über.
Es ist zweckdienlich, dem Betrieb des Zustandsgeräts von einem Punkt aus zu folgen, wenn es gerade in den Zustand C an der Spitze des Diagramms eingetreten ist. Wenn sich das Zustandsgerät im Zustand C befindet, definiert dies eine Wettbewerbszeitspanne, und während dieser Zeitspanne sendet die Steuerungsschaltung 27 ein aktives C Signal aus, das wie in Figur 2 gezeigt zu der Treiberschaltung 28, der Zugangszuteilungsschaltung 31 und der Keine-Anforderung- Schaltung 33 geleitet wird. Am Ende des von dem Takt A gegebenen Zeitinkrements kehrt es, wenn die Steuerungsschaltung 27 ein aktives Keine-Anforderung- Signal X von der Keine-Anforderung-Schaltung 33 erhalten hat, wieder in den Zustand C zurück; wenn kein Keine-Anforderung-Signal vorhanden ist, schaltet es in den Zustand U um. Die C- und Taktgebersignale sind in Figur 5 gezeigt.
Wenn sich das Zustandsgerät im Zustand U befindet, definiert dies eine Benutzungssignalzeitspanne, und während dieser Zeitspanne sendet die Steuerungsschaltung 27 ein aktives Signal U wie in Figur 5 gezeigt aus. Das Signal U wird, wie in Figur 2 gezeigt. zu der Zugangszuteilungsschaltung 31 und zu dem Aktualisierungsgatter 34 geleitet. Während des Zeitinkrements, wenn sich das Zustandsgerät in dem Zustand U befindet, empfängt die Steuerungsschaltung von dem Steuerungsbus 22 Signale, die anzeigen, welche Art von Transaktion gerade von einem der Benutzer 12 eingeleitet wird. Je nach diesen empfangenen Signalen verzweigt das Zustandsgerät am Ende der Periode zu einem von Z genannten verschiedenen Zuständen zum Durchführen einer Transaktion, die jeweils einer der festgelegten Transaktionsarten entsprechen.
Die Transaktionsarten A, B stehen stellvertretend für ziemlich einfache Transaktionen, wie beispielsweise die Datenübertragung von dem einleitenden Benutzer zu einer Ein-/Ausgangs-Vorrichtung. Auch längere und kompliziertere Transaktionen können definiert und verwendet werden, wie durch Transaktionsart C dargestellt ist. Für alle Transaktionen fährt das Zustandsgerät über eine Kette von sukzessiven Zuständen zum Ausführen einer Transaktion fort, die benötigt werden können, um die spezielle Transaktionsart durchzuführen, die gerade ausgeführt wird. Wenn das Zustandsgerät das Ende einer beliebigen gerade ausgeführten Kette erreicht, kehrt es in den Zustand C zurück und beginnt eine weitere Wettbewerbszeitspanne.
Die Verzweigungskette vom Typ D ist von besonderer Wichtigkeit für die vorliegende Erfindung. Eine derartige Transaktion ist beispielsweise eine Transaktion zur Bestätigung einer Programmunterbrechung, die auftreten kann, wenn ein Prozessorbenutzer eine Programmunterbrechung durchführen möchte und eine Transaktionsart D einleitet, um benötigte Information zu erhalten. Bei der Verzweigung gemäß einer Transaktion vom Typ D tritt das Zustandsgerät in einen Zustand C' ein. Wenn sich das Zustandsgerät im Zustand C' befindet, definiert dies einen Zeitraum zum Anfordern für das Antwortgeben (response bid interval) und während dieses Zeitraumes sendet die Steuerungsschaltung 27 ein aktives Signal C' aus, das wie in Figur 2 gezeigt zu der Treiberschaltung 28, der Zugangszuteilungsschaltung 31 und der Keine-Anforderung-Schaltung 33 geleitet wird.
Am Ende des Zeitinkrements für das Verbleiben im Zustand C' (von dem Takt A gegeben) kehrt es, wenn die Steuerungsschaltung 27 ein aktives Keine-Anforderung-Signal X von der Keine-Anforderung-Schaltung 33 empfangen hat, in den Zustand C zurück; wenn kein Keine-Anforderung-Signal vorhanden ist, schaltet es in einen Zustand V um.
Wenn sich das Zustandsgerät in dem Zustand V befindet, definiert dies einen Antwortberechtigungszeitraum (response enabiement interval), und während dieses Zeitraumes sendet die Steuerungsschaltung 27 das Signal V aus, das wie in Figur 2 gezeigt zu der Zugangszuteilungsschaltung 31 geleitet wird.
Am Ende seiner Periode in dem Zustand V kehrt das Zustandsgerät in den oben in Figur 6 gezeigten Zustand C zurück.
Die Steuerungsschaltung 27 reagiert auch auf ein von dem Steuerungsbus während einem der Zustände empfangenen "Warte"-Signal und veranlaßt, daß das Zustandsgerät in einen Zustand zurückkehrt, anstatt zum nächsten Zustand weiter zu gehen. Diese Eigenschaft gestattet es jedem Benutzer, der noch nicht bereit ist, mit dem Standardtransaktionstempo mitzuhalten, das Voranschreiten von Zustandsgeräten in allen Controllern durch Übertragen des Wartesignals auf den Steuerungsbus zu verzögern.
Es kann angemerkt werden, daß, während der Betrieb des Zustandsgeräts abhängig von Signalen ist, die von dem Steuerungsbus empfangen werden, es gleichgültig ist, welche Benutzer diese Signale aussenden. Im Ergebnis sind die Zustandsgeräte der verschiedenen Zugangs-Controller beim Schritthalten unabhängig, haben jedoch identische Listen des Zustands des Übertragungsbusses.
Nun werden die Wechselwirkungen der von der Steuerungsschaltung ausgesendeten Signale mit anderen Elementen des Zugangs-Controllers betrachtet. Um diese Diskussion zu vereinfachen, werden die Signale auf den (n - 1 ) Überwachungsleitungen mit Mi bezeichnet, wobei i von (n - 1) läuft. Die Signale der Speicherelemente 35 werden mit Si bezeichnet, wobei der Index des Speicherelements demjenigen der Überwachungsleitung entspricht, die mit einem der UND- Glieder 36 gleicher Bezeichnung verbunden ist.
Wenn das von der Steuerungsschaltung während einer Wettbewerbszeitspanne ausgesendete Signal C zu der Treiberschaltung 28 geleitet wird, bewirkt es, wenn der Benutzer 12 auf Leitung 19 signalisiert hat, daß er den Übertragungsbus zu benutzen wünscht, die Übertragung eines Buswettbewerbssignals durch den Übergabeschlüssel 24 auf den Arbitrationsbuskanal, der dem Benutzer zugeordnet ist.
Auch während einer Wettbewerbszeitspanne werden alle auf den Arbitrationsbus übertragene Wettbewerbssignale an die Arbitrationslogik 30 angelegt, wo sie mit den Signalen aus dem Prioritätszustandsspeicher 29 logisch analysiert werden, um das Signal P zu erzeugen, das angibt, ob der Benutzer 12 eine vorherrschende Priorität besitzt. Wenn eine aktive Bedingung auf einem Arbitrationsbuskanal mit 1 und eine inaktive mit 0 bezeichnet wird, und wenn die zwei Zustände der Speicherelemente Si des Prioritätszustandsspeichers ähnlich bezeichnet werden, kann die logische Operation der Arbitrationslogik in Modulo-2-Arithmetik beschrieben werden als
P = T(M&sub1;S&sub1; + 1)(M&sub2;S&sub2; + 1)...(Mn-1Sn-1 + 1).
Das Signal C zusammen mit dem an die Zugangszuteilungsschaltung 31 angelegten Takt B bewirkt das Aufnehmen des Signals P in das Zuteilungslatch 37 während des späteren Teils der Wettbewerbszeitspanne. Die Wettbewerbssignale von dem Arbitrationsbus werden auch an die Keine-Anforderung-Schaltung 33 angelegt und darin logisch analysiert, wobei das Ergebnis als Signal X durch das Anlegen des Signals C und des Taktes B ausgesendet wird. Das Signal X versorgt die Steuerungsschaltung 27 mit dem Kriterium zum sofortigen Neustarten einer Wettbewerbszeitspanne.
Das von der Steuerungsschaltung während einer Benutzungssignalzeitspanne ausgesendete Signal U wird an die Zugangszuteilungsschaltung 31 angelegt, und wenn das Signal W aus dem Zuteilungslatch 37 abgegeben wird, bewirkt dies, daß das Signal G auf Leitung 20 an den Benutzer 12 gesendet wird. Das Signal G wiederum bewirkt die Aussendung des Signals T von der Treiberschaltung 28. Das Signal U wird zusammen mit dem Takt B auch an das Aktualisierungsgatter 34 angelegt, um die Aktualisierung der Prioritätsspeicherelemente während des späteren Teils der Benutzungssignalzeitspanne zu bewirken.
Die Steuerungsschaltung 27 reagiert auch auf ein auf dem Steuerungsbus empfangenes Initialisierungssignal, um die Übertragung von Signalen von dem Initialisierungsschlüssel 38 durch das lnitialisierungsgatter 39 zu dem Prioritätszustandsspeicher 29 zu ermöglichen.
Wenn das von der Steuerungsschaltung während eines Zeitraumes zum Anfordern für das Antwortgeben ausgesendete Signal C' an die Treiberschaltung 28 angelegt wird, bewirkt es, wenn der Benutzer 12 ein Antwort-fertig-Signal R' auf Leitung 50 signalisiert hat, das anzeigt, daß er bereit ist, auf dem Übertragungsbus zu antworten, die Übertragung eines Signals zum Anfordern für das Antwortgeben durch den Übergabeschlüssel 24 in den Arbitrationsbuskanal, der mit dem Benutzer verbunden ist.
Auch während eines Zeitraumes zum Anfordern für das Antwortgeben werden alle auf den Arbitrationsbus übertragenen Signale zum Anfordern für das Antwortgeben an die Arbitrationslogik 30 angelegt, wo sie mit den Signalen aus dem Prioritätszustandsspeicher logisch analysiert werden, um das Signal P zu erzeugen, das anzeigt, ob der Benutzer 12 eine vorherrschende Priorität besitzt, wobei die Analyse so ist, wie in Verbindung mit der Wettbewerbszeitspanne beschrieben wurde.
Das von der Steuerungsschaltung während eines Antwortberechtigungszeitraumes ausgesendete Signal V wird an die Zugangszuteilungsschaltung 31 angelegt, und wenn das Signal W aus dem Zuteilungslatch zu diesem Zeitpunkt abgegeben wird, bewirkt dies, daß das Signal E auf Leitung 51 an den Benutzer 12 gesendet wird.
Nun wird die globale Organisation betrachtet, durch die die verschiedenen Zugangs-Controller miteinander wechselwirken. Es sollte angemerkt werden, daß die verschiedenen Controller alle identisch im Aufbau und im Betrieb sind. Die einzigen Unterschiede zwischen einem Controller und einem anderen liegen in den Übergabeschlüsseln, durch die die Controller mit dem Arbitrationsbus verbunden sind, in dem Informationsinhalt der Prioritätszustandsspeicher und in den Initialisierungsschlüsseln, die Anfangswerte in den Prioritätszustandsspeichern einstellen.
Die Übergabeschlüssel 24 verbinden den Arbitrationsbus 21 mit den Zugangs- Controllern 17, wie insbesondere in Figur 4 gezeigt ist. Im Gegensatz zu den Controllern 17, die alle gleich sind, sind die Übergabeschlüssel und die Initialisierungsschlüssel verschieden und entsprechend einem Schema auf globaler Basis organisiert. Jeder Schlüssel weist auf seiner Busseite n Verbindungen auf, die mit den n Arbitrationsbuskanälen (die mit A&sub1;, A&sub2;,...An bezeichnet sind) verbunden sind. Jeder Übergabeschlüssel ist an seiner Controllerseite mit der Übertragungsleitung 25 (Signal T) und den (n - 1) Überwachungsleitungen 26 (Signale Mi) seiner zugeordneten Controller verbunden. Ein erster Übergabeschlüssel (mit K&sub1; bezeichnet) weist interne Verbindungen auf, die A&sub1; mit seiner Übertragungsleitung und die (n - 1) Buskanäle mit Ausnahme von A&sub1; mit den (n - 1) Überwachungsleitungen seines Controllers verbindet; ein zweiter Übergabeschlüssel K&sub2; weist interne Verbindungen auf, die A&sub2; mit der Übertragungsleitung und die (n - 1) Buskanäle mit Ausnahme von A&sub2; mit den (n - 1) Überwachungsleitungen seines Controllers verbindet, und so weiter bei allen Übergabeschlüsseln. Insbesondere ist die Übertragungsleitung jedes Controllers über die Schlüssel Ki mit einem unterschiedlichen Buskanal Ai verbunden. Das Schaltungsschema ist in Figur 8 dargestellt.
Die Initialisierungsschlüssel 38, die insbesondere in Figur 4 gezeigt sind, erzeugen Signale aus der Spannungsversorgung (0 und +), die in direkter oder invertierter Reihenfolge durch das Initialisierungsgatter 39 auf die Set- und Reset-Eingänge der Speicherelemente 35 der Prioritätszustandsspeicher 29 angelegt werden.
In dem ersten Initialisierungsschlüssel I&sub1;, (mit dem Zugangs-Controller 1 und dem Übergabeschlüssel K&sub1; verbunden) sind die Verbindungen derart, daß die +- Spannung an die Set-Eingänge von keinem und die Reset-Eingänge von allen der Speicherelemente angelegt ist, so daß, wenn das Initialisierungsgatter 39 des Zugangs-Controllers 1 diese Signale abgibt, alle seine Speicherelemente auf 0 zurückgesetzt werden.
In dem zweiten Initialisierungsschlüssel I&sub2; sind die Verbindungen derart, daß die +-Spannung an den Set-Eingang des ersten Speicherelements und die Reset- Eingänge aller Speicherelemente mit höheren lndex angelegt wird, so daß, wenn das Initialisierungsgatter 39 des Zugangs-Controllers 2 diese Signale abgibt, das erste seiner Speicherelemente auf 1 gesetzt und die Speicherelemente mit höherem Index auf 0 zurückgesetzt werden. (Die Indizierung der Speicherelemente ist die gleiche wie bei der zugeordneten Überwachungsleitung und dem Überwachungssignal, wie sie in der Diskussion der Übergabeschlüssel angegeben sind.)
In dem dritten Initialisierungsschlüssel I&sub3; sind die Verbindungen derart, daß die +- Spannung an den Set-Eingang des ersten und zweiten Speicherelements und die Reset-Eingänge aller Speicherelemente mit höherem Index angelegt ist, so daß, wenn das Initialisierungsgatter 39 des Zugangs-Controllers 3 diese Signale abgibt, das erste und zweite seiner Speicherelemente auf 1 gesetzt und die Speicherelemente mit höherem Index auf 0 zurückgesetzt werden.
Das Anschlußschema geht in dieser Weise für die Initialisierungsschlüssel mit höherem Index weiter, wobei die Umschaltstellung, unterhalb der die +-Spannung an den Set-Eingang angelegt wird, für die Initialisierungsschlüssel mit höherem Index nach und nach zunimmt. Bei dem n-ten Initialisierungsschlüssel ist die Umschaltpositon über dem Speicherelement mit dem höchsten Index, mit dem Ergebnis, daß alle seine Speicherelemente gesetzt werden. Das allgemeine Schema ist in der folgenden Tabelle dargestellt: Initialisierungsschlüssel Umschaltstellung zwischen Speicherelementen
Für die Zwecke einer Diskussion der allgemeinen Aspekte der Verwirklichung der Erfindung ist es zweckmäßig, eine andere Konvention zur Identifizierung der Signale der Speicherelemente des Prioritätszustandsspeichers 29 als diejenige zu verwenden, die bei der Diskussion des internen Betriebs eines einzelnen Controllers verwendet wurde. Die Speicherelementsignale werden bezüglich ihrer Verbindungen mit dem Arbitrationsbus bezeichnet. Jedes Speicherelement ist (auf verschiedene Weise) mit zwei unterschiedlichen Buskanälen verbunden. Ein Speicherelementsignal wird mit Sij bezeichnet, mit der Bedeutung, daß es sich in dem Zugangs-Controller befindet, dessen T-Leitung über seinen Übergabeschlüssel mit dem Buskanal Ai verbunden ist, und daß es mit dem Kanal Aj durch Verbindung mit dem gleichen UND-Glied 36 wie Kanal Aj verbunden ist. Da die UND-Glieder 36 niemals mit dem gleichen Buskanal wie T verbunden sind, besteht eine zwingende Voraussetzung für die Sij darin, daß i nicht gleich j ist.
Die in dem Prioritätszustandsspeicher jedes Controllers gespeicherten Signale geben im wesentlichen die gegenwärtige Priorität des Controllers gegenüber jedem anderen Controller an. Das bedeutet, wenn Si 3 gleich 1 ist, gibt es dem Controller 1 an, daß Controller 3 eine vorherrschende Priorität besitzt. Während jede Kombination von Werten in den (n - 1) Speicherelementen eines einzelnen Controllers auftreten kann, sind nicht alle allgemeinen Kombinationen von Werten der n(n - 1) Systemelemente kompatibel mit einer geordneten Prioritätsreihenfolge der Controller. Die allgemeinen Bedingungen, die von den Speichern eingehalten werden müssen, um eine geordnete Prioritätsreihenfolge der Controller widerzuspiegeln, sind, daß Sie nicht gleich Sji ist und daß die Anzahl von Einsen in jedem Controllerspeicher sich von derjenigen in einem anderen unterscheidet. Die Organisation der Initialisierungsschlüssel gewährleistet, daß diese Bedingungen am Beginn von Operationen erfüllt sind, und die Organisation der Übergabeschlüssel gewährieistet, daß alle Aktualisierungsänderungen die erforderlichen Bedingungen aufrecht erhalten.
Vom Systemstandpunkt aus gesehen hält sich jeder Controller in seinem Prioritätszustandsspeicher über seinen Prioritätszustand gegenüber jedem anderen Controller auf dem Laufenden. Dann gibt jeder Controller am Beginn der Wettbewerbszeitspanne, wenn er wünscht, eine Transaktion auf dem Übertragungsbus einzuleiten, eine Anforderung an alle anderen durch Übertragung auf seinem eigenen Arbitrationskanal (das ist derjenige, mit dem er als einziger über seinen Verbindungsschlüssel verbunden ist) bekannt. Gegen Ende der Wettbewerbszeitspanne analysiert jeder Controller durch seine Arbitrationslogik die Anforderungssignale, um zu bestimmen, welchem Controller Zugang zu dem Übertragungsbus zuzuteilen ist. In dem nachfolgenden Benutzungssignalzeitraum ermöglicht es der anfordernde Controller, dem Zugang zugeteilt worden ist, seinem Benutzer, eine Transaktion auf dem Übertragungsbus einzuleiten, und er gibt diese Benutzung allen anderen Controllern durch Aussenden des Signals T auf seinem eigenen Kanal bekannt. Gegen Ende des Benutzungssignalzeitraumes (zur Zeit des Taktes B) werden die Signale auf dem Arbitrationsbus, die anzeigen, welcher Controller den Übertragungsbus benutzt hat, durch die Aktualisierungsgatter geleitet und dazu verwendet, die Prioritätsliste zu aktualisieren. Der benutzende Controller ändert seine Liste, um zu zeigen, daß jeder andere Controller nunmehr ihm gegenüber bevorrechtigt ist; jeder nicht benutzende Controller registriert, daß der benutzende Controller nun ihm selbst untergeordnet ist. Das Ergebnis dieser Anpassungen besteht darin, den letzten benutzenden Controller von seiner vorigen Stellung an das Ende der Prioritätsreihenfolge zu bringen, während die restliche Prioritätsreihenfolge unverändert bleibt.
Der Systembetrieb verfolgt somit eine Strategie, den letzten Einleiter einer Transaktion an das Ende der Prioritätsliste zu setzen.
Bei der Behandlung bestimmter Transaktionen, die eine Antwort erfordern, seien dies einer, mehrere oder n qualifizierte Antworter, tritt ein Zeitraum zum Anfordern für das Antwortgeben auf, in dem jeder qualifizierte Antworter anzeigt, daß er bereit ist, durch Übertragung eines Signals zum Anfordern für das Antwortgeben auf seinem eigenen Arbitrationskanal zu antworten. Diese auf den Arbitrationsbus während des Zeitraumes zum Anfordern für das Antwortgeben gegebenen Signale werden analysiert um zu bestimmen, ob es einen anfordernden Antworter gibt, und im positiven Fall, welcher die Priorität besitzt. Wenn es keinen qualifizierten Antworter gibt, beginnt das System erneut ohne Verzögerung den Wettbewerb für eine neue Transaktion; wenn es einen oder mehrere qualifizierte Antworter gibt, wird einer davon berechtigt, die Antwort zu geben. Der Betrieb während des Zeitraumes zum Anfordern für das Antwortgeben folgt dem Schema des Betriebs während der Wettbewerbszeitspanne und verwendet mit wirtschaftlichen Vorteilen die gleiche Zugangs-Controller-Schaltung. Durch sofortiges neuerliches Starten des ersten Wettbewerbs für eine neue Transaktion, wenn es keine Anforderung für eine Antwort gibt, vermeidet es das System, die Busse zu blockieren, die auf eine Antwort warten, die niemals kommt.
Die Operation zum Anfordern für das Antwortgeben führt keine Änderung der Prioritätsspeicherinformation aus und greift somit nicht in die Prioritätsstrategie ein, dem am längsten wartenden Benutzer Priorität zum Einleiten einer Transaktion zuzuerkennen. In der vorstehenden Diskussion wurde größtenteils angenommen, daß ein voller Satz von Benutzern die Benutzung des Übertragungsbusses anforderte - d. h., daß n aktiv fordernde Benutzer für ein System mit n Arbitrationskanälen vorhanden sind. Das System arbeitet gleich gut, wenn es weniger als n Benutzer gibt, oder wenn einige Benutzer passiv sind, an Transaktionen teilnehmen, jedoch nie welche einleiten. In diesen Fällen steigt die nominelle Priorität der passiven oder nicht existierenden Benutzer bis zu den Spitzenpositionen an, aber da diese Benutzer den Übertragungsbus nie anfordern, geht die Buszuteilung immer an den am höchsten eingestüften anfordernden Benutzer.
Das beschriebene System erleichtert die Austauschbarkeit von Betriebsbenutzern eines Übertragungsbusses, da die Controller identisch sind. Somit kann ein Übertragungsbus geschaffen werden, dessen jeweils gleiche Übergabe- und Initialisierungsschlüssel mit Standardports verbunden sind, an die ein Controller und ein Benutzer angeschlossen werden kann. Benutzer mit verschiedenen Funktionen können dann unterschiedslos an jedem Port angebracht werden.

Claims

1. Dezentralisierte Busarbitrationsvorrichtung in einem Computersystem mit einer Vielzahl von an einen gemeinsamen Bus (14) angeschlossenen Teileinheiten (12), mit:

einem Arbitrationsbus (21) mit Einrichtungen zum Führen einer Vielzahl von im wesentlichen gleichzeitigen Bus-request-Signalen; und

einer Vielzahl von Arbitrationseinrichtungen (17), die alle mit dem gemeinsamen Bus, dem Arbitrationsbus und jeweils einer entsprechenden Untereinheit verbunden sind, zum Bestimmen der relativen Prioritäten, mit denen die Untereinheiten Zugang zu dem gemeinsamen Bus bekommen sollen, wobei die Arbitrationseinrichtungen nur bestimmen, ob der mit der Arbitrationseinrichtung verbundenen Untereinheit Zugang zu dem gemeinsamen Bus zugeteilt werden soll;

wobei jede der Arbitrationseinrichtungen umfaßt:

Zustandseinrichtungen (29) zum Speichern von Zustandsmeldungen, die angeben, welche der Untereinheiten eine höhere Priorität als die der Arbitrationseinrichtung entsprechende Untereinheit haben;

eine Bus-request-Einrichtung (28), die mit dem Arbitrationsbus verbunden ist, zum Geben eines Bus-request-Signals auf den Arbitrationsbus; und

eine Zugangssteuereinrichtung (30), die mit dem Arbitrationsbus und der Zustandseinrichtung verbunden ist, zum Empfangen von auf den Arbitrationsbus gegebenen Bus-request-Signalen und zum Zuteilen von Zugang zu dem gemeinsamen Bus für die entsprechende Untereinheit nur dann, wenn die Bus-request- Einrichtung ein Bus-request-Signal gegeben hat und keines der empfangenen Bus-request-Signale von der Arbitrationseinrichtung von Untereinheiten gegeben wurde, denen von der Zustandseinrichtung eine höhere Priorität als der entsprechenden Untereinheit zugeordnet wurde;

dadurch gekennzeichnet, daß

mehrere der Untereinheiten (12) Einrichtungen zum Einleiten von Transaktionen enthalten, die eine Antwort von einer der anderen Untereinheiten benötigt;

die Bus-request-Einrichtungen (28) in mehreren der Arbitrationseinrichtungen eine Einrichtung zum Geben eines Bus-request-Signals als Antwort auf das Einleiten einer der Transaktionen durch eine der Untereinheiten enthalten;

wobei die mehreren Arbitrationseinrichtungen des weiteren aufweisen:

mit den Bus-request-Einrichtungen, mit den Zugangssteuerungsvorrichtungen, mit dem gemeinsamen Bus und dem Arbitrationsbus verbundene Maschinenzustandseinrichtungen (46) zum Steuern des Betriebs der Arbitrationseinrichtungen, die Einrichtungen für die Erfassung aufweisen, wenn eine der Untereinheiten eine Transaktion einleitet, die eine Antwort von einer der anderen Untereinheiten erfordert, zum Überwachen des Arbitrationsbusses auf Bus-request-Signale und zum Abbrechen der Transaktionen, wenn am Ende eines Zeitraumes zum Anfordern für das Antwortgeben keine Bus-request-Signale von der Überwachungseinrichtung festgestellt wurden.

2. Dezentralisierte Busarbitrationsvorrichtung nach Anspruch 1, dadurch gekennzeichnet, daß die Maschinenzustandseinrichtung (46) eine Zustandsanzeigeeinrichtung zum Anzeigen eines ersten Zustandes, während dessen die Bus-request- Einrichtung ein Bus-request-Signal geben kann, eines zweiten Zustandes, während dessen die Zugangssteuerungsvorrichtung Zugang zu dem gemeinsamen Bus zuteilen kann, eines dritten Zustandes, der die Einleitung einer Transaktion durch eine der Untereinheiten anzeigt, welche Transaktion eine Antwort von einer der anderen Untereinheiten erfordert, eines vierten Zustandes, während dessen die Bus-request-Einrichtung ein Bus-request-Signal als Antwort auf die Einleitung einer Transaktion durch eine der Untereinheiten geben kann, und eines fünften Zustandes umfaßt, während dessen die Transaktion stattfindet, wobei die Maschinenzustandseinrichtung des weiteren eine Einrichtung zum Überwachen des Arbitrationsbusses auf Bus-request-Signale und zum Zurückkehren aus dem vierten Zustand in den ersten Zustand enthält, wenn von der Überwachungseinrichtung keine Bus-request-Signale erfaßt werden.

3. Dezentralisierte Busarbitrationsvorrichtung nach Anspruch 1, dadurch gekennzeichnet, daß die Arbitrationseinrichtungen des weiteren aufweisen:

eine mit dem Arbitrationsbus verbundene Benutzungsanzeigeeinrichtung (31) zum Geben eines Benutzungssignals an den Arbitrationsbus, wenn die Zugangssteuerungseinrichtung der entsprechenden Untereinheit Zugang zuteilt; und

eine mit der Zustandseinrichtung verbundene Zustandsaktualisierungseinrichtung (27, 34) zum Speichern eines Zustandssignals, das eine niedrige Priorität für jede Untereinheit anzeigt, der Zugang zu dem gemeinsamen Bus zugeteilt wurde, und zum Zurücksetzen der Zustandssignale auf einen festgelegten Zustand, wenn der entsprechenden Untereinheit Zugang zu dem gemeinsamen Bus zugeteilt wird; wobei die Vielzahl von Arbitrationseinrichtungen verschiedene, jedoch konsistente Zustandssignale in ihren jeweiligen Zustandseinrichtungen aufrecht erhalten.

4. Dezentralisierte Busarbitrationsvorrichtung nach Anspruch 1, dadurch gekennzeichnet, daß die Arbitrationseinrichtungen des weiteren aufweisen:

eine mit der Zustandseinrichtung verbundene Zustandsaktualisierungseinrichtung (27,34) zum Speichern eines Zustandssignals, das eine niedrige Priorität für jede Untereinheit anzeigt, der Zugang zu dem gemeinsamen Bus zugeteilt wurde und zum Speichern von Zustandssignalen von hoher Priorität für alle anderen Untereinheiten, wenn der entsprechenden Untereinheit Zugang zu dem gemeinsamen Bus zugeteilt wird.

5. Verfahren zur Arbitration des Zuganges einer Vielzahl von Untereinheiten (12) in einem Computersystem zu einem gemeinsamen Bus (14), die durch einen Arbitrationsbus (21) mit Einrichtungen zum Führen einer Vielzahl von im wesentlichen gleichzeitigen Bus-request-Signalen verbunden sind, dessen Verfahrensschritte umfassen:

Speichern eines für jede Untereinheit (12) unterschiedlichen Satzes von Zustandssignalen, der angibt, welche der Untereinheiten eine höhere Priorität besitzen als die betreffende Untereinheit;

Geben eines separaten Bus-request-Signales auf den Arbitrationsbus (21) für jede jener Untereinheiten, die einen Zugang zu dem gemeinsamen Bus benötigen; und

im wesentlichen gleichzeitiges Vergleichen bei jedem der Untereinheiten, die ein Bus-request-Signal abgegeben haben, der auf den Arbitrationsbus abgegebenen Bus-request-Signale mit den für die Untereinheit gespeicherten Zustandssignalen und Zuteilen von Zugang zu dem gemeinsamen Bus für die Untereinheit nur dann, wenn keines der Bus-request-Signale Untereinheiten zugeordnet ist, von denen durch die gespeicherten Zustandssignale angezeigt wird, daß sie eine höhere Priorität als die Untereinheit aufweisen;

gekennzeichnet durch die im wesentlichen gleichzeitig bei jeder der Untereinheiten ausgeführten Schritte:

Erfassen, wenn eine der Untereinheiten eine Transaktion einleitet, die eine Antwort von einer der anderen Untereinheiten erfordert;

Geben eines Bus-request-Signals auf den Arbitrationsbus für jede Untereinheit, die auf die Einleitung der Transaktion antwortet;

Überwachen des Arbitrationsbusses auf Bus-request-Signale und anschließend Abbrechen der Transaktion, wenn am Ende eines festgelegten Zeitraumes zum Anfordern für das Antwortgeben von dem Überwachungsschritt keine Bus-request-Signale erfaßt worden sind.

6. Busarbitrationsverfahren nach Anspruch 5,

dadurch gekennzeichnet,

daß der Erfassungsschritt die Schritte des Anzeigens eines ersten Zustandes während Zeitintervallen, in denen ein Bus-request-Signal abgegeben werden kann, des Anzeigens eines zweiten Zustandes während Zeitintervallen, in denen der Zugang zu dem gemeinsamen Bus zugeteilt werden kann, des Anzeigens eines dritten Zustandes, wenn eine der Untereinheiten eine Transaktion einleitet, die eine Antwort von einer anderen der Untereinheiten erfordert, des Anzeigens eines vierten Zustandes während Zeitintervallen, in denen ein Bus-request-Signal als Antwort auf die Einleitung einer Transaktion von einer der anderen Untereinheiten abgegeben werden kann, und des Anzeigens eines fünften Zustandes, während dessen die Transaktion stattfindet, umfaßt,

und daß der Schritt des Abbrechens die Anzeige des ersten Zustandes umfaßt, wenn keine Bus-request-Signale von dem Überwachungsschritt erfaßt werden, während der vierte Zustand angezeigt wird.

7. Busarbitrationsverfahren nach Anspruch 5,

dadurch gekennzeichnet,

daß der Schritt des Zuteilens des weiteren den Schritt umfaßt, ein Benutzungssignal auf den Arbitrationsbus zu geben, wenn der Untereinheit Zugang zu dem gemeinsamen Bus zugeteilt worden ist,

und daß der Schritt der Speicherung des weiteren die Schritte des Speicherns eines Zustandssignals, das eine niedrige Priorität für jede Untereinheit anzeigt, der Zugang zu dem gemeinsamen Bus zugeteilt wird, und des Speicherns von Zustandssignalen hoher Priorität für alle anderen Untereinheiten umfaßt, wenn der entsprechenden Untereinheit Zugang zu dem gemeinsamen Bus zugeteilt wird.