DE3855200T2

DE3855200T2 - Cache/plattenspeichersystem mit auf plattenzugriffszeit basierender befehlsauswahl

Info

Publication number: DE3855200T2
Application number: DE3855200T
Authority: DE
Inventors: Robert Swenson
Original assignee: Unisys Corp
Current assignee: Unisys Corp
Priority date: 1987-09-30
Filing date: 1988-09-23
Publication date: 1997-01-09
Anticipated expiration: 2008-09-24
Also published as: KR920010185B1; EP0354931A1; KR890702130A; DE3855200D1; EP0354931B1; JPH02501776A; WO1989003089A2; WO1989003089A3

Description

Die Erfindung betrifft ein Cache/Platten-Untersystem, das auf Befehle von einem Host-Prozessor reagiert, und die Anordnung umfaßt: eine Plattenlaufwerkseinrichtung zum Speichern von Daten, wobei die Plattenlaufwerkseinrichtung wenigstens eine Platte und einen damit zusammenwirkenden, radial positionierbaren Wandler zum Zugreifen auf den Plattenplatz beinhaltet; einen Cache-Speicher; und eine Steuerungseinrichtung zum Steuern der Übertragung von Daten zwischen dem Host-Prozessor, dem Cache-Speicher und der Plattenlaufwerkseinrichtung; wobei die Steuerungseinrichtung veranlaßt, daß auf der Platte gespeicherte Daten, welche wahrscheinlich beim Ausführen von Host-Prozessorbefehlen verwendet werden, in dem Cache-Speicher gespeichert werden, einen Host-Prozessorbefehl, der in dem Cache-Speicher gespeicherte Daten verwendet, ohne auf den Zugriff auf die Plattenlaufwerkseinrichtung warten zu müssen, ausführt, den Wandler zum Zugriff auf einen bestimmten Plattenplatz auf der Plattenlaufwerkseinrichtung als Reaktion auf einen Befehl, der einen Plattenzugriff erfordert, steuert, und eine Befehlswarteschlange beinhaltet, um darin mehrere Host-Prozessorbefehle zu speichern, die einen Plattenzugriff erfordern, aber noch nicht ausgeführt werden, wobei jeder dieser Befehle mit einem bestimmten Plattenplatz auf der Plattenlaufwerkseinrichtung korrespondiert; wobei die Steuerungseinrichtung, bevor eine Suche ausgelöst wird, die Positionsbeziehungen zwischen den Warteschlangenanforderungen prüft und einen Planungsalgorhithmus zum Bedienen des Anforderungssatzes anwendet, wobei die Anforderungen ohne Rücksicht darauf, in welcher Richtung der Zugriffsarm sich bewegen muß, bedient werden. Ein solches System ist aus einem Artikel "Intelligent Controllers use Cache to Reduce Seek-Time and Latency" in Computer Technology Review, Vol 4 Nr.1, Februar 1984, S.277-286, bekannt.
Wenn ein oder mehrere Host-Prozessoren durch eine oder mehrere Speichersteuerungseinheiten (SCU) an einen Cache-Speicher und mehrere Plattenlaufwerke angeschlossen sind, werden die Inhalte des Cache-Speichers so gesteuert, daß er kontinuierlich Daten enthält, die den Plattenplätzen entsprechen, auf welche wahrscheinlich als Reaktion auf einen durch einen Host-Prozessor ausgegebenen Plattenbefehl zugegriffen wird. Da auf den Cache-Speicher in einem kleinen Bruchteil der Zeit zugegriffen werden kann, den ein Plattenzugriff erfordert, wird eine signifikante Geschwindigkeitsverbesserung verwirklicht.
Bei bekannten Systemen werden Daten in dem Cache-Speicher in mehreren Segmenten gespeichert. Ein Befehl (Lesen oder Schreiben) von einem Host- Prozessor wird durch die Speichersteuerungseinheit interpretiert, welche zuerst eine Segmentdeskriptorentabelle (SDT) prüft, um zu bestimmen, ob eine Kopie der an dem angegebenen Plattenplatz gespeicherten Daten in dem Cache-Speicher vorhanden ist. Die SDT weist darin einen Eintrag für jedes Datensegment in dem Cache-Speicher auf. Wenn die SCU erkennt, daß eine Kopie des angegebenen Plattenplatzes indem Cache-Speicher vorhanden ist (ein "Treffer"), steuert die SCU die Übertragung der Daten von/zu dem Host-Prozessor zu/von dem Cache-Speicher. Wenn die Übertragung von dem Host-Prozessor zu dem Cache-Speicher (schreiben) verläuft, stellt die SCU ein "geschrieben zu" (WT-Bit) in dem SDT-Eintrag oder den Einträgen entsprechend dem Segment oder den Segmenten, in welche die Daten geschrieben sind. Das WT-Bit zeigt, wenn es eingestellt ist, daß die Daten in dem entsprechenden Segment im Cache-Speicher nicht an ihren angegebenen Plattenplatz geschrieben sind.
Wenn die SCU einen Host-Prozessorbefehl interpretiert und feststellt, daß alle erforderlichen Segmente der Daten von dem angegebenen Plattenplatz nicht in dem Cache-Speicher vorhanden sind (ein "Verfehlen"), werden, wenn das den angegebenen Plattenplatz enthaltende Plattenlaufwerk nicht belegt ist, die erforderlichen Segmente darauf angesprochen und in dem Cache-Speicher gespeichert. Wenn jedoch das den angegebenen Plattenplatz beinhaltende Plattenlaufwerk belegt ist, bildet die SCU einen Befehl und plaziert ihn in einer Befehlswarteschlange für jedes Plattenlaufwerk und jede Warteschlange speichert die Befehle, die darauf warten, durch ihre zugeordnete Platte ausgeführt zu werden. Diese Warteschlangen können ebenfalls "Einzel"-Befehle speichern, welche während Leerlaufzeiten der SCU zur Verwendung in Uveinzelnen auszuführendenuv "schreibe zu"-(WT)-Segmenten in dem Cache-Speicher auf ihre angegebenen Plattenplätze verwendet werden. Wenn ein Befehl in einer Warteschlange der Befehl mit der höchsten Priorität in seiner Warteschlange wird, wird er aus der Warteschlange entfernt und ausgeführt. Wenn mehrere in einer Warteschlange wartende Befehle auf der höchsten Prioritätsebene sind, dann wird derjenige, der sich am längsten in der Warteschlange befindet, zur Ausführung selektiert.
Das oben beschriebene Platten/Cache-Untersystem bietet eine signifikante Verbesserung der Ausführungsgeschwindigkeit einer Datenübertragung zwischen einem Plattenlaufwerk und einem Host-Prozessor. Dieser Geschwindigkeitsvorteil kann jedoch bei Prozessor/Plattenlaufwerks-Datenübertragungssituationen nachteilig beeinflußt werden, welche eine relativ hohe Anzahl von Befehlen auslösen, die einen Plattenzugriff erfordern, die in einer oder mehreren Warteschlangen zu speichern sind, um auf ihre Ausführung zu warten. In einem solchen Fall kann die Ausführung dieser Befehle in der Warteschlange dazu führen, daß signifikante Zeit beim Zugreifen auf die angegebenen Plattenplätze auf den Plattenlaufwerken aufgewendet wird, wodurch die Gesamt-Übertragungsgeschwindigkeit verringert wird. Dies wird erkennbar durch Erkennen, daß für jeden Zugriff auf einen selektierten Plattenplatz eine Lese/Schreib-Operation nicht nur warten muß, bis der Kopf auf dem selektierten Zylinder positioniert ist (Suchoperation), sondern auch warten muß, bis der selektierte Plattenplatz unter den Kopf dreht (Rotationsverzögerung).
In dem System, wie es in dem bereits erwähnten Artikel "Intelligent Controllers Use Cache to Reduce Seek-Time and Latency", erwähnt ist, wird bereits erwähnt, daß die Neupositionierung des Schwenkarms eines Plattenspeichers typisch im größten Teil der Plattenbedienungszeit darstellt, und daher ist es ein aktiver Gegenstand des technischen Interesses, an der Verringerung der durchschnittlichen Suchzeit zu arbeiten. Es wird weiterhin erwähnt, daß eine Lösung entweder der Restruktunerungsansatz oder der Planungsansatz sein kann. Es wird erwähnt, daß bei einem Planungsansatz Anforderungen entsprechend ihrer Nachbarschaft zu der zuletzt bedienten Anforderung bedient werden, ohne die Richtung zu berücksichtigen, in welche der Schwenkarrn zu bewegen ist. Es ist evident, daß die kürzeste Suchzeit zu bestimmen ist, bevor die Suche selbst ausgelöst wird. Es wird weiter dargelegt, daß die Verzögerung bei mehreren Plattenlaufwerkssteuerungen verringert wird, indem eine Übertragung auf der Platte gestartet wird, deren Suche beendet ist und deren Rotationsposition nahe dem gewünschten Anfangssektor ist.
Es ist eine Aufgabe der vorliegenden Erfindung, die Zugriffszeit in solch einem Cache/Platten-Untersystem der in dem Oberbegriff von Anspruch 1 beschriebenen Art weiter zu verringern. Erfindungsgemäß ist ein solches System dadurch gekennzeichnet, daß die Steuerungseinrichtung die gegenwärtige Zylinder- und Winkelposition bestimmt, eine anstehende Anforderung in der Befehlswarteschlange durch Berechnen der Suchzeit S und der Rotationswartezeit L zum Bestimmen der Gesamtpositionierungszeit S + L, die für die anstehende Anforderung erforderlich ist, unter Berücksichtigung der gegenwärtigen Zylinder- und Winkelposition, testet, wodurch bestimmt ist, welche der anstehenden Anforderungen von den bisher getesteten Anforderungen die schnellste ist, und nach jedem Test die Adresse und die entsprechende Gesamtzeit der schnellsten der bis dahin getesteten anstehenden Anforderungen speichert und den Test fortsetzt, bis das Ende der Befehlswarteschlange erreicht ist, wonach die beste anstehende Anforderung zum Zugreifen auf den Plattenplatz selektiert ist.
Bevorzugte Ausführungsformen sind in den Unteransprüchen beschrieben.

KURZBESCHREIBUNG DER ZEICHNUNGEN

Fig. 1 ist ein Blockschaltbild eines Cache/Platten-Systems;
Fig. 2 zeigt das Format eines Segmentdeskriptorentabelleneintrages;
Fig. 3 zeigt eine Befehlswarteschlange;
Fig. 4 zeigt das Format von Einträgen in einer Zeitmarkentabelle;
Fig. 5 ist ein Flußdiagramm, das die Leerlaufroutine darstellt;
Fig. 6 ist ein Flußdiagramm, das die Servicebefehlswarteschlangenroutine darstellt;
Fig. 7 ist ein Diagramm, das die Cache-Durchbruchs-Routine darstellt;
Fig. 8A und 8B umfassen ein Flußdiagramm, das die Einzelausführungs-Start- Routine darstellt;
Fig. 9 zeigt das Format eines Rolltabelleneintrages;
Fig. 10A und 10B umfassen ein Flußdiagramm, das die Einzelausführungs-Routine darstellt;
Fig. 11A bis 11I umfassen ein Flußdiagramm, das die Einzelausführungs-Prüf- Unterroutine darstellt;
Fig. 12A bis 12D umfassen ein Flußdiagramm, das die Befehlswarteschlangenprüfunterroutine darstellt;
Fig. 13A und 13B umfassen ein Flußdiagramm, das die Finde-Befehlswarteschlangen Eintrag-Unterroutine darstellt;
Fig. 14A bis 14F umfassen ein Flußdiagramm, daß die Aktualisierungs-TACK/WT- Unterroutine darstellt;
Fig. 15A bis 15E umfassen ein Flußdiagramm, das die Zeitmarken-Hinzufügen/Entfernen-Unterroutine darstellt;
Fig. 16A und 16B umfassen ein Flußdiagramm, das die Einzelbefehls-Prioritäts- Bestimmungs-Unterroutine darstellt;
Fig. 17 ist ein Flußdiagramm, welches die Lese-Dienstroutine darstellt.

DETAILLIERTE BESCHREIBUNG

Fig. 1 ist ein Blockschaltbild eines Cache/Platten-Systems des in der am 14. November 1980 eingereichten U.S.-Patentanmeldung Nr. 207,152 beschriebenen Typs. Das System, wie in Fig. 1 dargestellt, beinhaltet eine Speichersteuerungseinheit 100 zum Anschließen mehrerer Host-Prozessoren oder Kanäle 102 an einen Cache-Speicher 106 und einen Massenspeicher, der als Mehrzahl von Plattenlaufwerken 104 dargestellt ist. Fig. 1 soll nicht das Cache/Platten-System vollständig darstellen, sondern ist vorgesehen, damit der Leser den nachfolgend beschriebenen Programmen leichter folgen kann. Es ist anzumerken, daß ein vollständiges System eine zusätzliche Speichersteuerungseinheit aufweisen kann, die zusätzliche Host-Prozessoren bedient, wobei die Speichersteuerungseinheiten ein vollständiges Komplement von Registern aufweisen, wie in der Anmeldung 207,152 gezeigt.
Die Speichersteuerungseinheit (SCU) 100 beinhaltet Kanalanschlußschaltungen 108, Geräteanschlußschaltungen 110 und Steuerungsanschlußschaltungen 112 zum Anschließen der SCU an den Host-Prozessor (Hosts), die Plattenlaufwerke und den Cache-Speicher. Ein BD-Bus 114 ist der primäre Datenübertragungsbus, der zum Übertragen von Information zwischen den Hosts 102, den Plattenlaufwerken 104 und dem Cache-Speicher 106 über die Kanalanschlußschaltungen 108, die Geräteanschlußschaltungen 110 und die Steuerungsanschlußschaltungen 11 2 verwendet wird.
Die SCU ist mit einem Steuerungsspeicher (CS) 116 zum Speichern des Mikroprogramms für die SCU ebenso wie einige der Variablen und Konstanten vorgesehen, die verwendet werden, wenn das Programm ausgeführt wird. Der Steuerungsspeicher 116 wird durch die Adressierungsschaltungen 118 unter der Steuerung eines Programmzählregisters PC und eines Indexregisters IX adressiert. Zusätzlich ist ein Keller-Datenstapel DS vorgesehen zum Speichern der Rücksprungadressen der aufrufenden Routinen während der Ausführung von Unterroutinen.
Die Adressierungsschaltungen 118 adressieren den Steuerungsspeicher 116 zum Auslesen der Befehle in eine Befehlsdekodierungs- und Steuerungsschaltung 120. Die Schaltung 120 dekodiert die Befehle, die sie empfängt, selektiert die Quelle oder die Quellen der Daten, die zu verarbeiten sind, das Ziel des Ergebnisses, steuert Verzweigungsoperationen und gibt allgemein an die verschiedenen Elemente der Speichersteuerungseinheit die Signale aus, die zum Ausführen eines gegebenen Befehls erforderlich sind.
Die SCU beinhaltet mehrere, mit GA-GG, OP, ST, BX und HR bezeichnete, adressierbare Register, die alle an einen Quellbus angeschlossen sind, der als der erweiterte A-Bus bezeichnet ist, und an einen Zielbus, bezeichnet als der D-Bus.
Das Register HR ist ein Register doppelter Breite mit zwei separat adressierbaren Registern einfacher Länge HL und HH. HR ist das primäre Arbeitsregister für die SCU und alle aus dem Steuerungsspeicher 116 geholten Daten durchlaufen HR. Daten können natürlich von dem Steuerungsspeicher 116 zu anderen an den BD- Bus angeschlossenen Elementen übertragen werden.
Die Register GA-GG sind allgemeine Register, welche als eine Informationsquelle, ein Ziel oder beides dienen können. Das heißt, ein Wert in einem der Register GA- GG kann in eine arithmethische Logikeinheit (ALU) 122 ausgelesen werden, darin durch Daten modifiziert werden, die von dem erweiteren A-Bus durch einen Byte- Tauscher 124 an die ALU angelegt werden, und das Ergebnis kann an das gleiche Register oder ein anderes Register durch eine Rechts-Verschiebe-Schaltung 126 und den D-Bus zurückgegeben werden.
Der Byte-Tauscher 124 wird selektiv durch den Befehlsdekodierer 120 gesteuert, um die zwei untergeordneten Bytes eines von dem erweiterten A-Bus empfangenen Wortes zu den übergeordneten Bytepositionen zu verschieben und umgekehrt. Die Rechts-Verschiebe-Schaltung 126 unterliegt ebenfalls der Steuerung des Befehlsdekodierers 120 und kann Daten von der ALU zu dem D-Bus ohne Verschieben oder mit einem Verschieben um 1 Bit nach rechts durchleiten.
Das OP-Register ist ein Bit-Test-Register, während das ST-Register das Statusregister ist.
Das BX-Register ist ein Adressierungsregister, das zum Adressieren eines Stufenpuffers (SB, Staging Buffer) 128 verwendet wird. Der Stufenpuffer 128 umfaßt momentan zwei 8k-Stufenpuffer zum Halten von Datensegmenten ebenso wie Kopien bestimmter Variablen, die aus dem Cache-Speicher gelesen wurden und während verschiedener Operationen verwendet werden.
Der Cache-Speicher 106 weist eine Sektion zum Speichern von Datensegmenten (1792 Worte pro Segment) und eine Sektion wahlfreien Zugriffspeichers (RAM) zum Speichern einer Segment-Deskriptoren-Tabelle und verschiedener anderer globaler Variablen auf. Die SDT und die globalen Variablen müssen in dem Speicher 106 erhalten werden, da der Speicher an eine andere Speichersteuerungseinheit wie die SCU 100 angeschlossen sein kann und diese zusätzliche Speichersteuerungseinheit ebenfalls an weitere Host-Prozessoren und Plattenlaufwerke angeschlossen ist. Der Cache-Speicher ist aus MOSFET-Geräten aufgebaut und mit einer Batterie oder einer unterbrechungsfreien Stromversorgung versehen, welche den Cache-Speicher für eine vorbestimmte Zeit, z.B. 15 Minuten, im Fall des Versagens der Wechselspannungsquelle für den Cache-Speicher, im Betrieb hält.
Die Segmentdeskriptorentabelle (SDT) beinhaltet einen Eintrag für jedes Segment der in dem Cache-Speicher 106 residenten Daten. Wenn ein Host 102 Daten von einem der Plattenlaufwerke 104 zu erhalten wünscht, sendet er einen Befehl an die SCU 100. Die SCU 100 bringt die SDT vom Cache 106 zu dem Stufenpuffer 128 und bestimmt, ob die gewünschten Daten in dem Cache-Speicher vorhanden sind. Wenn dies der Fall ist, werden die Daten von dem Cache-Speicher 106 unter der Steuerung der Speichersteuerungseinheit 100 zu dem anfordernden Host 102 gesendet.
Wenn die angeforderten Daten nicht in dem Cache vorhanden sind, müssen sie von einem der Plattenlaufwerke 104 erhalten werden. Die SCU 100 trifft eine Festlegung, ob das Plattenlaufwerk (nachfolgend als Laufwerk bezeichnet) erreichbar und nicht belegt ist oder nicht. Wenn das Laufwerk erreichbar und nicht belegt ist, steuert die SCU 100 die Übertragung des Segments oder der Segmente, die die gewünschten Daten enthalten, von dem Laufwerk zu dem Cache-Speicher 106 und sendet die gewünschten Daten zu dem anfordernden Host 102.
Wenn das die gewünschten Daten haltende Laufwerk belegt ist, bildet die SCU einen Befehlswarteschlangeneintrag und trägt diesen in eine Befehlswarteschlange in dem Stufenpuffer 128 ein. Dort ist eine Befehlswarteschlange für jedes Laufwerk 104 vorhanden. Die akualisierte Befehlswarteschlange wird zu dem RAM-Teil des Cache-Speichers 106 zurückgegeben und der Host wird informiert, daß er die Daten zu einem späteren Zeitpunkt nochmal ansprechen muß.
Wenn das Laufwerk 104 den Auftrag beendet, an dem es arbeitet, benachrichtigt es die SCU und die SCU überträgt wieder die Befehlswarteschlange von dem Cache-Speicher 106 zu dem Stufenpuffer, wo sie bestimmt, welcher Befehl in der Befehlswarteschlange für das Laufwerk die höchste Priorität hat und steuert die Ausführung dieses Befehls. Schließlich wird der Befehl, der in der Befehlswarteschlange gespeichert ist, ausgeführt und die Daten werden von dem Laufwerk 104 zu dem Cache-Speicher 106 weitergegeben. Später, wenn der Host 102 seinen Befehl für die Daten erneut ausgibt, bestimmt die Speichersteuerungseinheit, daß diese in dem Cache-Speicher vorhanden sind und sendet die Daten von dem Cache-Speicher zu dem anfordernden Host über den BD-Bus und die Kanal-Anschlußschaltungen 108.
Ein ähnliches Verfahren wird angewendet, wenn einer der Hosts 102 Daten auf eines der Laufwerke 104 schreiben möchte. Wenn die zu schreibenden Adressen in den im Cache 106 gespeicherten Segmenten enthalten sind, werden die Daten von dem Host in den Cache-Speicher und nicht auf das Laufwerk 104 geschrieben. Ein Zeiger wird in dem SDT-Eintrag oder den Einträgen, die dem zu schreibenden Segment oder den Segmenten entsprechen und den von dem Cache-Speicher auf das Laufwerk 104 geschriebenen Segmenten zu einem späteren, für die SCU 100 besser geeigneten Zeitpunkt gesetzt.
Wenn das zu schreibende Segment oder die Segmente nicht in dem Cache-Speicher vorhanden sind und das Laufwerk belegt ist, wird der Befehl in die Befehlswarteschlange für das Geräte eingereiht und zu einem späteren Zeitpunkt, der durch seine Priorität bestimmt wird, ausgeführt, um die gewünschten Segmente von dem Plattenlaufwerk 104 zu dem Cache 106 zu bringen. Später, nachdem der eingereihte Befehl ausgeführt ist und das Plattenlaufwerk anzeigt, daß es eine Suchoperation beendet hat, möchte der Host 102 die Schreiboperation ausführen und gibt wieder den Schreibbefehl aus und zu diesem Zeitpunkt bringt die Speichersteuerungseinheit das Segment oder die Segmente in den Stufenpuffer 120, überlagert sie mit den Daten von dem Host und gibt das modifizierte Segment oder die Segmente an den Cache-Speicher 106 zurück.
Wie bei den zuvor erwähnten Anmeldungen mit den Nummer 207,097 und 207,152 erläutert, müssen, wenn ein neues Segment oder Segmente von einem Laufwerk 104 in den Cache-Speicher 106 zu bringen sind, und dort keine freien Segmente in dem Cache-Speicher 106 vorhanden sind, einige der in dem Cache- Speicher 106 vorhandenen Segmente gelöscht oder daraus entfernt werden, um Raum für neue Segmente zu schaffen. Um dies zu verwirklichen, ist jeder Segmentdeskriptorentabelleneintrag mit einer rückwärtigen relativen Altersverbindungsadresse und einer relativen Vorwärts-Altersverbindungsadresse versehen, so daß die Segmentdeskriptorentabelleneinträge von dem am längsten nicht verwendeten Eintrag (LRU, Least Recently Used) zu dem zuletzt verwendeten (MRU, Most Recently Used) Eintrag verbunden sind. Das am längsten nicht verwendete Segment oder die Segmente werden von der SDT bestimmt. Das neue Segment oder die Segmente werden von den Laufwerken 104 zu dem Cache- Speicher 106 verschoben, um die darin enthaltenen LRU-Segmente zu überschreiben. Dies schafft kein Problem, wenn ein überschriebenes Segment nicht beschrieben wurde, während es in dem Cache-Speicher vorhanden war, da bereits eine Kopie des Segments auf einer der Platten vorhanden ist. Wenn jedoch ein LRU- Segment durch einen Host-Prozessor beschrieben ist, während es in dem Cache- Speicher vorhanden war, muß dieses Segment zu einem der Plattenlaufwerke 104 zurückverschoben werden, bevor sein Segment-Platz in dem Cache-Speicher durch das neue Segment überschrieben werden kann.
Wie weiterhin in den vorerwähnten Anmeldungen erläutert, kann die SCU 100, wenn sie nichts anderes zu tun hat, die SDT durchsuchen, um Segmente zu finden, welche beschrieben wurden, und diese Segmente einzeln zu den Laufwerken 104 übertragen, um somit Platz in dem Cache 106 für zusätzliche Segmente verfügbar zu machen. Dieses einzelne Schreiben von geschriebenen Segmenten findet auf der gleichen Basis statt wie ein Segmentersatz, d.h., die am längsten nicht verwendeten Segmente werden zuerst einzeln geschrieben, wobei das am längsten nicht verwendete von den Vorwärts- und Rückwärts-Altersverknüpfungen in jedem SDT-Eintrag bestimmt wird.
Fig. 2 zeigt die Segmentendeskriptortabelle (SDT). Jeder SDT-Eintrag umfaßt vier Worte. Es gibt einen Eintrag in der SDT-Tabelle für jedes in dem Cache-Speicher 106 vorhandene Segment. Das GFTR- und LFTR-Bit ist gesetzt, wenn das entsprechende Segment ein globales oder ein lokales "schwimmendes" Segment ist, d.h. eines, welches nicht auf ein Plattenlaufwerk geschrieben werden kann, da das Laufwerk eine defekte Platte aufweist. Diese Unterschiede sind jedoch für die vorliegende Erfindung nicht relevant.
Die Mnemonics links von den Wortformaten in Fig. 2 bezeichnen das SDT-Wort und seinen Ort im Stufenpuffer 128, wenn die SDT dorthin verschoben ist. Bei SBSDT1 bezeichnet das Host-ID-Feld den Host, der zuletzt einen Befehl an das zugeordnete Cache-Segment ausgegeben hat. Das Laufwerksnummer-Feld bezeichnet eines der Plattenlaufwerke 104 und das relative Segmentlaufwerkadreßfeld ist eine Zahl, welche den Segment-Offset (die relative Anzahl vom ersten Segment) von Daten auf einer Platte darstellt. In SBSDT2 ist das Bit 0 das DATEN-GÜLTIG-Bit, welches anzeigt, ob das im Cache diesem SDT-Eintrag zugeordnete Segment gültige Daten enthält oder nicht. Das TACK-Bit beinhaltet, ob der zugeordnete Cache-Segment- Platz in dem Cache-Speicher 106 für die Daten reserviert ist, die dadurch entweder von dem Host oder von einer Platte übertragen werden. Bit 2 von SBSDT2 ist die UV Schreibe zu"-Anzeige, welche anzeigt, ob das zugeordnete Cache-Segment durch den Host beschrieben und das beschriebene Segment bisher noch nicht zu der Platte zurückverschoben ist oder nicht. Die anderen Felder von SBSDT2 sind für die vorliegende Erfindung nicht relevant.
In SBSDT3 ist Bit 0 das letzte Rückwärts-Altersverknüpfungs-Bit (LBAL, Last Backward Agelink) und zeigt an, wenn es gesetzt ist, daß dieser SDT-Eintrag der letzte in der Rückwärts-Altersverknüpfung ist. Die relative Rückwärts-Altersverknüpfungsadresse zeigt auf den nächsten SDT-Eintrag, wobei die relative Rückwärts-Altersverknüpfungsadresse alle Segmente von dem zuletzt verwendeten zu dem am längsten nicht verwendeten verknüpft. Bit 16 ist das letzte Vorwärts- Altersverknüpfungs-Bit (LFAL), und zeigt, wenn es gesetzt ist, daß dieser Eintrag der letzte Eintrag in der Vorwärts-Altersverknüpfung ist. Das relative Vorwärts- Altersverknüpfungs-Adreßfeld ist die relative Adresse des nächsten Eintrages in der Vorwärts-Altersverknüpfung. Das relative Vorwärts-Altersverknüpfungs-Adreßfeld in allen SDT-Einträgen verknüpft alle Segmente vom am längsten nicht verwendeten zum zuletzt verwendeten. In einem typischen System kann der Cache-Speicher 106 in der Lage sein, 8k Datensegmente zu speichern; dann sind 8k SDT-Einträge mit jeweils vier Worten vorhanden, wie in Fig. 2 gezeigt.
Fig. 3 zeigt eine Befehlswarteschlange. Für jedes der Laufwerke 104 ist eine Befehlswarteschlange vorhanden. Jede Befehlswarteschlange beinhaltet zwei Kopfworte und bis zu sieben Einträge, wobei jeder Eintrag drei Worte aufweist.
Das erste Wort des Befehlswarteschlangenkopfes (SBCMDQ), sofern sie in dem Stufenpuffer angeordnet ist, behinhaltet die Felder DB, NCQ, Laufwerksnummer und nächste Folgenummer. DB ist ein Anzeigebit, welches gesetzt ist, wenn das dieser Befehlswarteschlange zugeordnete Laufwerk belegt ist. NCQ zeigt die Anzahl der momentan in dieser Warteschlange eingereihten Befehle an. Die Laufwerksnummer bezeichnet das Laufwerk 104, welchem diese Befehlswarteschlange zugeordnet ist. Das nächste Folgenummernfeld enthält die Folgenummer, die in dem nächsten in der Warteschlange vorgenommenen Befehlseintrag einzufügen ist. Diese Nummer beginnt bei Null und wird erhöht, bis sie 255 erreicht und springt dann zurück auf Null.
Das zweite Wort des Befehlswarteschlangenkopfes (SBCMQH) weist ein aktives Befehlsanforderungsnummernfeld auf, welches die Anforderungsnummer des Befehls darstellt, der momentan ausgeführt wird. Das Nummernfeld der momentan ausgeführten Suchanforderung wird in Verbindung mit dem Eintrag-Ungültig-Bit (IV) verwendet. Wenn IV = 1 ist, zeigt dies, daß keine Suche ausgeführt wird. Wenn IV = 0 ist, ist die Anforderungsnummer die Nummer des Befehls mit einer momentan ablaufenden Suche. Für jede Anforderungsnummer ist ein Befehlswarteschlangenplatz reserviert. Jeder Platz speichert einen Dreiwort-Befehlswarteschlangeneintrag. Das erste Wort eines Befehlswarteschlangeneintrages (SBCMQ 1) weist ein Host-ID-Feld auf, das den Host bezeichnet, der den Befehl ausgegeben hat, ein Voll-Bit (FL), das anzeigt, ob der Platz einen Befehl enthält oder nicht, ein Prioritätsfeld und ein Folgenummernfeld, das die relative Folge anzeigt, in welcher der Befehl von dem Host empfangen wurde. Ein Prioritätswert von zeigt die höchste Priorität und der Wert 7 stellt die niedrigste Priorität dar. Wie in den zuvor erwähnten Patenten und der Anmeldung wird eine Vorbereitung getroffen zum Selektieren eines Befehls zur Ausführung, basierend auf seiner Priorität und der Folgenummer. Erfindungsgemäß wird ebenfalls eine Vorbereitung getroffen zum Selektieren eines Befehls auf einer anderen Basis wie derjenigen, wenn bestimmte Umstände vorhanden sind, Plattenzugriffszeiten werden beim Ausführen der Selektion berücksichtigt. Das SCQ-Bit zeigt an, daß der Befehl durch die Leerlaufschleifen-(Servicebefehlswarteschlangen)-Routine eingereiht und zur Ausführung selektiert wurde. Das Alles-Treffer-Bit (AHT, All Hits Bit) zeigt an, daß alle für die Ausführung dieses Befehls erforderlichen Daten in dem Cache-Speicher vorhanden sind. Das Einzelausführungs-Bit (TRK) kennzeichnet einen Befehl als einen Einzelausführungs-Befehl. Die anderen Felder von SBCMQ1 sind zum Verständnis der vorliegenden Erfindung nicht relevant.
Das zweite Wort eines Befehlswarteschlangeneintrages (SBCQT2) weist ein NSEG- Feld auf, das die Anzahl der Segmente, die für diesen Befehl zu übertragen sind, und ein relatives Segmentlaufwerksadreßfeld (SDRA) darstellt. Das SDRA-Feld bezeichnet die Startsegmentadresse des ersten Wortes einer Übertragung. Diese Adresse wird abgeleitet von dem relativen Wortadreßfeld, das in einem Befehl von dem Host vorgesehen ist.
Das dritte Wort eines Befehlswarteschlangeneintrages (SBCFQ3) beinhaltet ein Anwender-Dateinummernfeld, welches in der vorliegenden Erfindung nicht verwendet wird.
Ein Host 102 gibt einen Lese- oder einen Schreib-Befehl aus, welcher fünf Worte umfaßt. Das fünfte Wort ist ein 32-Bit-Wort mit einer Zeitmarke, die den Zeitpunkt anzeigt, in welchem der Befehl ausgegeben wurde. Gemäß einem Aspekt der bevorzugten Ausführungsforrn wird diese Zeitmarke verwendet, um in der Befehlswarteschlange eingereihten Einzelbefehlen zunehmend höhere Priorität zuzuordnen, um dadurch die Zeit, die ein Segment im Cache verbleibt, nachdem es geschrieben wurde, zu verringern. Gemäß einem anderen Aspekt dieser Ausführungsforrn wird die Zeitmarke für das älteste beschriebene Segment (TOLDEST) stets an einem bestimmten Ort in dem RAM gesichert. Er wird periodisch durch einen Lesebefehl von dem Hostprozessor abgetastet, so daß der Hostprozessor jederzeit eine vollständig aktuelle Anzeige hat, welche Segmente in dem Cache-Speicher geschrieben, aber nicht zu den Platten zurückverschoben sind. Wenn ein Fehler in dem Cache- Speicher auftritt, kann der Host-Prozessor von seinem letzten Lesen von TOLDEST exakt bestimmen, welche Prozeduren verwendet werden müssen, um den Fehler auszugleichen.
Da jeder Befehl von einem Host-Prozessor durch die SCU empfangen wird, wird seine Zeitmarke an einer Stelle gespeichert, die für die momentane Zeitmarke (TCURRENT) vorbehalten ist und ersetzt dort jede Zeitmarke. Zusätzlich wird eine Zeitmarkentabelle gepflegt, wobei diese Tabelle einen Eintrag entsprechend jedem Eintrag in der SDT aufweist. Wenn ein Segment erstmalig beschrieben wird, wird die mit dem Host-Schreibbefehl übergebene Zeitmarke in der Zeitmarkentabelle gesichert. Nachfolgendes Schreiben in ein beschriebenes Segment verändert die Zeitmarke in der Tabelle nicht. Wenn ein Segment einzeln ausgeführt wird, wird sein Zeitmarkeneintrag in der Zeitmarkentabelle gelöscht. Somit wird jedes beschriebene Cache-Segment mit einer Zeitmarke mit der Zeit des ersten Beschreibens seit dem letzten Schreiben auf die Platte versehen. Wie hier nachfolgend benutzt, ist ein beschriebenes Segment per Definition ein Segment, das durch einen Host-Prozessor beschrieben, aber nicht an seine Platte zurückgegeben wurde, seit die Schreiboperation stattgefunden hat.
Fig. 4 stellt die Zeitmarkentabelle dar. Die Zeitmarkentabelle hat einen jedem Segment in dem Cache-Speicher entsprechenden Platz. Ein Eintrag an einem Platz wird beim ersten Beschreiben des Segments als Reaktion auf einen Schreibbefehl von dem Host-Prozessor vorgenommen. Jeder Eintrag in dieser Tabelle umfaßt zwei Worte, von denen die Einzelheiten von zwei Einträgen in Fig. 4 gezeigt sind. Das erste Wort jedes Eintrages in der Zeitmarkentabelle ist dieZeitmarke. Diese wird von dem durch den Host ausgegebenen Schreibbefehl erhalten. Die Einträge in der Zeitmarkentabelle sind in einer FIFO-Liste verknüpft. Wort 2 jedes Eintrages beinhaltet eine Rückwärtsverküpfungsadresse und eine Vorwärtsverknüpfungsadresse zum Verknüpfen der Einträge vom ältesten Geschriebenen zum neuesten Geschriebenen. Bit 0 ist gesetzt, wenn der Eintrag der letzte hintere Eintrag in der Liste (der älteste beschriebene) ist, während Bit 16 gesetzt ist, wenn der Eintrag der vorderste (d.h. der zuletzt geschriebene) Eintrag in der Liste ist. Die WS- und BT- Bits werden in der vorliegenden Erfindung nicht verwendet.
Die Zeitmarkentabelle wird normalerweise in dem RAM-Teil des Cache-Speichers 106 gespeichert und selektiert Einträge aus der Tabelle, die zur Verwendung in den Stufenpuffer 128 gebracht werden. Die Einträge, welche zu dem Stufenpuffer gebracht werden, können der momentane Eintrag entsprechend dem beschriebenen Segment oder der gelöschte Eintrag sein, da das entsprechende Segment in dem Cache-Speicher ersetzt wurde. Der momentane Eintrag oder der Löscheintrag wird in dem Stufenpuffer 120 an den Positionen SBTS1 und SBTS2 gespeichert. In einigen Fällen kann es ebenfalls erforderlich sein, den nächsten Eintrag oder den vorherigen Eintrag (relativ zu dem momentanen oder Löscheintrag) in den Stufenpuffer zu bringen, und wenn der vorherige Eintrag oder der momentane Eintrag in den Stufenpuffer gebracht ist, werden sie an den Orten SBTS3 und SBTS4 plaziert.
Es versteht sich, daß die SDT in Fig. 2 und die Befehlswarteschlangen, von denen eine in Fig. 3 dargestellt ist, ebenfalls normalerweise in dem RAM-Teil des Cache Speichers 106 gespeichert sind und zur Benutzung in den Stufenpuffer 128 gebracht werden. Die in den Figuren 2 und 3 links wiedergebenen Mnemonics sind diejenigen, die zugeordnet sind, wenn die zugehörigen Worte in dem Stufenpuffer vorhanden sind. Von dem Stufenpuffer können einzelne Worte in das HR-Register zur Verwendung oder Modifikation geholt werden. In dem Steuerspeicher 116 gespeicherte Variablen können ebenso zur Verwendung und Modifikation in HR geholt werden. In der folgenden Programmbeschreibung wird, wo der Begriff "holen" verwendet wird und die geholte Variable ein mit SB beginnendes Mnemonic aufweist, wie z.B. SBCMDQ, es so verstanden, daß die Variable von dem Stufenpuffer geholt wird. Wenn das Mnemonic nicht mit dem Buchstaben SB beginnt, dann wird die Holoperation von dem Steuerspeicher 116 ausgeführt.

LEERLAUFSCHLEIFE

Wenn die SCU 100 in Fig. 1 eine Operation beendet, kehrt sie in eine Leerlaufschleife zurück, wie in Fig. 5 dargestellt, wo sie auf die nächste auszuführende Operation wartet. Wie allgemein in Schritt 500 gezeigt, prüft die SCU die Kanalschnittstellenschaltungen 108, um zu erkennen, ob ein Host einen Befehl ausgibt und prüft dann die Laufwerksschnittstellenschaltungen 110, um zu erkennen, ob eines der Laufwerke 104 eine Suchoperation beendet hat und zur Datenübertragung an die SCU bereit ist. Wenn eine von diesen Operationen auszuführen ist, wird eine Verzweigung von der Leerlaufschleife in Schritt 500 verwendet, um die geforderte Operation auszuführen. Nachdem die Operation beendet ist, kehrt das Programm zum Anfang der Leerlaufschleife zurück und bewegt sich wieder zu Schritt 500. Wenn das Programm in Schritt 500 nicht erkennt, daß ein Host oder ein Laufwerk mit der SCU kommunizieren, läuft es weiter zu Schritt 502, wo eine Prüfbefehlswarteschlangen-Unterroutine (Figuren 12A-12D) aufgerufen wird. Wie nachfolgend erläutert, liest die Prüfbefehlswarteschlangen-Unterroutine sequentiell das erste Wort jedes Warteschlangenkopfes, beginnend mit dem prioritätsnächsten, bis es ein nicht belegtes Laufwerk mit einem dafür eingereihten Befehl findet. Wenn die Unterroutine in einer der Warteschlangen einen auszuführenden Befehl findet, kehrt sie zurück in die Leerlaufschleife mit dem Wert 8000 in GA und der Befehlswarteschlange in dem Stufenpuffer. Wenn keine eingereihten Befehle für eines der Laufwerke vorhanden sind, kehrt die Prüfbefehlswarteschlangen-Unterroutine mit dem Wert 0 in GA zu der Leerlaufschleife zurück. In Schritt 504 wird GA getestet und wenn es den Wert 8000 enthält, verzweigt die Leerlaufschleife zu der in Fig. 6 gezeigten Servicebefehlswarteschlangenroutine. Alle 4-Stellen-Werte, die in dieser Beschreibung verwendet werden, sind hexadezimale Werte, so lange nichts anderes angegeben wird.
Wenn die Prüfung von GA in Schritt 504 anzeigt, daß keine Befehle eingereiht sind, prüft das Programm wieder die Schnittstellen (nicht dargestellte Schritte), um zu erkennen, ob ein Host oder ein Laufwerk mit der SCU kommunizieren möchte. Wenn dies der Fall ist, verzweigt die Leerlaufschleife, um die geforderte Operation in der gleichen Weise wie für Schritt 500 auszuführen. Wenn dort noch nichts zu tun ist, läuft die Leerlaufschleife weiter zu Schritt 506, wo sie eine Einzelausführungs-Prüf-Unterroutine aufruft. Diese in den Figuren 11A bis 11I dargestellte Unterroutine sucht nach anstehenden Einzelausführungsbefehlen oder Segmenten, die beschrieben wurden, während sie sich im Cache befinden, durch Folgen der Zeitmarkenverknüpfungen (Fig. 4), beginnend mit dem ältesten der Segmente. Wenn ein anstehender Einzelausführungsbefehl gefunden wird, wird ein Einzelausführungseintrag gebildet und in die Befehlswarteschlange für das entsprechende Laufwerk eingefügt und die Befehlswarteschlange an das RAM zurückgegeben. Nachdem dies ausgeführt ist, kehrt die Unterroutine zu der Leerlaufschleife zurück, und da dies die letzte in der Leerlaufschleife ausgeführte Operation ist, wird ein Rücksprung zum Anfang der Leerlaufschleife ausgeführt. Während der Ausführung der Einzelausführungs-Prüf-Unterroutine können mehr als ein Einzelausführungsbefehl gebildet werden, aber für jede gegebene Befehlswarteschlange wird immer nur ein Einzelausführungsbefehl erzeugt.
Es ist anzumerken, daß die Einzelausführungs-Prüf-Unterroutine den erzeugten Einzelausführungsbefehl höchstens in der Befehlswarteschlange für das zugeordnete Laufwerk 104 plaziert. Sie führt den Befehl nicht aus. Schließlich wird sie, wenn die Leerlaufschleife ausgeführt wird, diesen Einzelausführungsbefehl in der Befehlswarteschlange finden und zu diesem Zeitpunkt damit fortfahren, ihn auszuführen.
Wenn die Prüfung von GA in Schritt 504 anzeigt, daß die Befehls-Warteschlangen- Prüf-Unterroutine einen eingereihten Befehl gefunden hat, der darauf wartet, ausgeführt zu werden, entweder einen Einzelausführungsbefehl oder einen Befehl, der als Ergebnis eines Lese- oder Schreib-Befehls von einem Hostprozessor in die Warteschlange eingetragen ist, verzweigt die Leerlaufschleife zu der Service- Befehls-Warteschlangen-Routine.

SERVICE-BEFEHLS-WARTESCHLANGE

Kurz gesagt ruft die Service-Befehls-Warteschlangenroutine (Fig. 6) eine Befehlswarteschlangeneintragsfinde-Unterroutine auf, um den nächsten auszuführenden Befehlswarteschlangeneintrag von der Befehlswarteschlange in dem Stufenpuffer zu erhalten. Diese Befehlswarteschlange ist die eine in dem Stufenpuffer von der Prüfbefehlswarteschlangen-Unterroutine in Schritt 502 ausgelassene. Die Befehlswartschlangeneintragsfinde-Unterroutine selektiert die Platte und überträgt die Steuerung an die Cache-Durchbruchroutine.
Wie in Fig. 6 dargestellt, beginnt die Servicebefehlswarteschlangenroutine durch Ausführen einer Unterroutine zum Erhalten globaler Variablen, um die globalen Variablen von dem RAM-Teil des Cache-Speichers zu dem Stufenpuffer zu bringen. Die globalen Variablen beinhalten Werte wie die Adressen der am längsten nicht verwendeten und der zuletzt verwendeten Segmente, die Adressen der neuesten und der ältesten Zeitmarkeneinträge in der Zeitmarkentabelle, ein Maskierungswort mit einem Anzeigebit für jedes Laufwerk, das anzeigt, ob ein Einzelausführungsbefehl für das Laufwerk ansteht oder nicht, und viele andere Variablen, wie nachfolgend beschrieben.
Nach der Rückkehr von der Unterroutine zum Erhalten von globalen Variablen wird Schritt 602 ausgeführt, um einen Flag-Wert in GA zu laden. Dieser Flag-Wert wird verwendet, um der aufzurufenden Befehlswarteschlangeneintragsfinde-Unterroutine mitzuteilen, daß die Unterroutine den nächsten auszuführenden Befehl in der Befehlswarteschlange finden soll. Die Befehlswarteschlangeneintragsfinde- Unterroutine (Figuren 13A - 13B) wird in Schritt 604 ausgeführt und diese Unterroutine kehrt, wie nachfolgend beschrieben, zu der aufrufenden Routine mit einer Anzeige in GA zurück, ob sie einen auszuführenden Befehl gefunden hat oder nicht. Der Wert von GA wird in Schritt 606 geprüft und wenn ein auszuführender Befehl nicht gefunden wurde, geht das Programm weiter zu Schritt 608, wo eine Unterroutine ausgeführt wird, um die SDT freizugeben. Dann wird ein Rücksprung zu der Leerlaufschleife ausgeführt.
Wenn die Prüfung in Schritt 606 anzeigt, daß die Befehlswarteschlangeneintragsfinde-Unterroutine einen Befehl zum Ausführen gefunden hat, läuft das Programm weiter zu Schritt 610, wo die Laufwerksadresse in STSXDA geholt wird. Diese Laufwerksadresse wird während der Ausführung der Prüfbefehlswarteschlangen- Unterroutine in Schritt 502 in dem Steuerspeicher 116 plaziert. Als nächstes wird PERMOO, die Basisadresse eines Permanentspeicherbereiches für die Laufwerke, geholt und in GB geladen. Dieser Permanentspeicherbereich beinhaltet für jedes Laufwerk die physikalische Identifikation der logischen Laufwerksadresse, die momentane Suchadresse und andere Informationen, die für die vorliegende Erfindung nicht relevant sind. Als eine letzte Operation wird in Schritt 610 die Basisadresse (ADRCNV) einer Adreßumwandlungstabelle in das IX-Register eingetragen.
In Schritt 612 wird die Laufwerksadresse zu ADRCNV hinzugefügt, um sie in der Tabelle zu indexieren und eine bitsignifikante Laufwerksadresse zu erhalten, d.h. eine Adresse mit einem einzelnen 1-Bit darin, wobei die Position des Bits in dem Wort die Adresse des Laufwerks bezeichnet. Die von der Tabelle erhaltene bitsignifikante Laufwerksadresse (BSDA) wird in Schritt 614 verwendet, um den permanenten Zeiger auf das Laufwerk einzustellen und das Ergebnis wird an dem Ort BSDA in dem Steuerspeicher gespeichert. Die Service-Befehlswartesch- Iangenroutine läuft dann zu der Cache-Durchbruchsroutine weiter.

CACHE-DURCHBRUCH

Die Cache-Durchbruchsroutine (Fig. 7) beginnt bei Schritt 700 mit dem Holen der Anforderungsnummer des Befehls, welcher in dem Steuerspeicher bei STSXRN gespeichert ist. Diese Anforderungsnummer wird von dem Wort 1 des in Schritt 604 gefundenen Befehlswarteschlangeneintrags abgeleitet. Die Anforderungsnummer wird mit 3 multipliziert, um den Offset in der Befehlswarteschlange für den momentanen Eintrag zu erhalten. Dieser Wert wird dann zu der Basisadresse der Befehslwarteschlange addiert und das Ergebnis wird gesichert. In Schritt 702 wird CMDQ1 aus dem Steuerspeicher geholt. CMDQ1 ist eine Steuerspeicherkopie des ersten Wortes eines Befehslwarteschlangeneintrages und wird während der Ausführung der Befehlswarteschlangeneintragsfinde-Unterroutine in Schritt 604 in dem Steuerspeicher plaziert.
In Schritt 704 wird das SCQ-Bit von CMDQ1 geprüft, um zu erkennen, ob der in Schritt 604 gefundene Befehlswarteschlangeneintrag ein Einzelausführungsbefehl ist. Wenn dies der Fall ist, wird eine Verzweigung zum Beginnen der nachfolgend beschriebenen Einzelausführungsbefehlsroutine verwendet.
Wenn die Cache-Durchbruchsroutine von einer anderen als der Service-Befehlswarteschlangenroutine aufgerufen wird, oder wenn der in Schritt 604 gefundene Befehlswarteschlangeneintrag nicht ein Einzelausführungsbefehl ist, führt die Prüfung in Schritt 704 zu einem unwahren Ergebnis. In Schritt 706 werden die globalen Variablen vom Cache zu dem Stufenpuffer gebracht und in Schritt 708 wird die CEF5 des Steuerspeichers gespeicherte Kanalbefehlszeitmarke geholt in GA und GB gespeichert. Die momentane Zeitmarke SBGTSC wird von dem Stufenpuffer geholt und die Kanalbefehlszeitmarke wird davon subtrahiert. Wenn SBGTSC größer ist als die in CEF5 gespeicherte Zeitmarke, wird diese Bedingung in Schritt 712 erfaßt und Schritt 714 wird umgangen. Wenn andererseits die Kanalbefehlszeitmarke größer als SBGTSC ist, wird die Kanalbefehlszeitmarke die aktuelle Zeitmarke und wird in SBGTSC gespeichert.
Nachdem Schritt 714 ausgeführt ist, untersucht die Cache-Durchbruchsroutine den momentanen Befehl und bestimmt, welche Operationen ausgeführt werden sollen, um den Befehl auszuführen. Nachdem diese Operationen beendet sind, kehrt das Programm zum Anfang der Leerlaufschleife in Fig. 5 zurück. Die an Schritt 714 anschließenden Operationen sind für die vorliegende Erfindung nicht relevant.
Wenn die Prüfung des SCQ in Schritt 704 zeigt, daß dieses Bit gesetzt ist, bedeutet das, daß dieser Befehl als Ergebnis der Einzelbefehls-Prüf-Unterroutine (Schritt 506), die ein einzeln auszuführendes Segment gefunden hat, in die Befehlswarteschlange eingefügt ist. In diesem Fall wird in Schritt 704 zu der Einzelausführungs-Anfangs- Routine verzweigt.

BEGINNE EINZELAUSFÜHRUNG

Die Einzelausführungs-Anfangs-Routine (Figuren 8A und 8B) wird nur ausgeführt, wenn die Cache-Durchbruchsroutine erkennt, daß ein Einzelausführungsbefehl der Befehl mit der höchsten Priorität in der Befehlswarteschlange ist. Sie bildet einen Rolltabelleneintrag för die Operation, selektiert das Platten laufwerk und startet eine Suchoperation. Für ein Plattenlaufwerk mit einem festen Kopf wird ein Verlassen zu der Einzelausführungsschreibroutine verwendet, um das aktuelle Abarbeiten eines Datensegments von dem Cache-Speicher 106 zu dem angegebenen Laufwerk 104 zu verwirklichen. Wenn der Einzelausführungsbefehl für ein Plattenlaufwerk mit einem beweglichen Kopf vorgesehen ist, werden die globalen Variablen an den Cache-Speicher 106 zurückgegeben, CMDQ1 wird in dem Steuerspeicher gelöscht und ein Rücksprung zu der Leerlaufschleife wird ausgeführt zum Warten auf mehr auszuführende Aufgaben, während das Laufwerk mit dem bewegbaren Kopf die Suchoperation ausführt.
Die Einzelausführungsbefehlsanfangsroutine beginnt in Schritt 800 durch Holen der Laufwerksadresse STSXDA und der Basisadresse SBTSKA einer Tabelle der anstehenden Einzelausführungsbefehle. Diese Tabelle weist einen Eintrag für jedes Laufwerk auf, wobei der Eintrag die SDT-Adresse des Segmentes enthält, das darauf wartet, an das bestimmte Laufwerk ausgegeben zu werden. Die Einträge werden in der Tabelle während der Ausführung der Einzelausführungsbefehlsprüf- Unterroutine in Schritt 506 erzeugt.
Die Laufwerksadresse wird zu der Tabellenbasisadresse und der in Schritt 802 angesprochenen Tabelle hinzugefügt, um die SDT-Adresse des SDT-Eintrags zu erhalten, der dem zu bearbeitenden Segment zugeordnet ist. Diese SDT-Adresse wird in das HR-Register geholt und ebenso an einem geeigneten Ort in dem Steuerspeicher 116 gesichert.
In Schritt 804 wird ein Rolltabelleneintrag, wie der in Fig. 9 gezeigte, unter Verwendung der von der Tabelle erhaltenen SDT-Adresse gebildet. Die GÜLTIG- und BELEGT-Bits werden gesetzt und der so gebildete Rolltabelleneintrag wird in dem Steuerspeicher 116 bei ROLTAB, der Basisadresse der Rolltabelle, gespeichert. Der nächste Eintrag in der Rolltabelle wird gelöscht, um das Ende der Tabelle anzuzeigen und der Wert 1 wird in ROLLNR in dem Steuerspeicher 116 gesetzt, um anzuzeigen, daß nur ein Segment von dem Cache zu dem Laufwerk 104 auszugeben ist. Die Verwendung von ROLLNR und ein Rolltabelleneintrag zum Steuern der Übertragung von einem oder mehreren Segmenten von dem Cache-Speicher zu einem Plattenlaufwerk wird in den Anmeldungen mit den Seriennummern 207,097 und 207,152 erläutert und bildet per se nicht einen Teil der vorliegenden Erfindung.
In Schritt 806 wird das zweite Wort des Befehlswarteschlangeneintrages geholt, um die relative Segmentlaufwerksadresse zu erhalten, welche dann bei FMSDRA in dem Steuerspeicher gespeichert wird.
Die in dem Steuerspeicher in Schritt 614 gespeicherte BSDA wird in Schritt 808 geholt und mit einem SDT-Wiederherstellungs-Fiag-Byte ODER-verknüpft. Dies ergibt eine Anzeige für ein Wiederherstellungsmodul, daß die Rolltabelle gebildet und ein SDT-Eintrag verändert wurde. Das Ergebnis wird zu dem Stufenpuffer an dem Ort zurückgegeben, der für das SDT-Wiederherstellungs-Flag-Byte SBRSDT reserviert ist.
An diesem Punkt ist die Speichersteuerungseinheit bereit, um die Übertragungs- Operation zu beginnnen. In Schritt 812 wird die Laufwerksadresse von STSXDA geholt und ein Aufruf für eine Unterroutine bei 814 ausgeführt, um das durch die Laufwerksadresse angezeigte Laufwerk zu selektieren. Als nächstes wird ein Aufruf zum Starten einer Such-Unterroutine 816 ausgeführt, um eine Suchoperation für das selektierte Laufwerk auszulösen Bei 818 wird eine Unterroutine aufgerufen, um die Rolltabelle in dem Stufenpuffer zurück in den RAM-Teil des Cache-Speichers 106 zu bringen. Bei Schritt 820 wird ein Wiederherstellungsstatuswort RECVST von dem Steuerspeicher geholt und akutalisiert, um anzuzeigen, daß die Rolltabelle an das RAM zurückgegeben wurde. In Schritt 822 wird eine Unterroutine aufgerufen, um die Befehlswarteschlange in dem Stufenpuffer zurück in das RAM zu bringen.
Die nächste Operation ist bestimmt durch Bit 5 des ST-Registers. Wenn Bit 5 gesetzt ist, bedeutet dies, daß das Plattenlaufwerk ein Laufwerk mit einem festen Kopf ist. In diesem Fall ist es nicht erforderlich, darauf zu warten, daß das Laufwerk den gewünschten Ort für die Datenübertragung sucht. Daher wird die Prüfung in Schritt 824 wahr und das Programm verzweigt zu der Einzelschreibroutine.
Wenn die Prüfung in Schritt 824 zeigt, daß das Laufwerk vom Typ mit bewegbaren Köpfen ist, läuft die SCU mit anderer Arbeit weiter, während der Kopf positioniert wird. In Schritt 826 werden die globalen Variablen in dem Stufenpuffer zu dem RAM-Teil des Cache-Speichers 106 zurückgegeben und in Schritt 828 wird die Kopie des ersten Wortes des Befehlswarteschlangeneintrages in dem Steuerspeicher (CMDQ1) gelöscht. Das Programm kehrt dann zu der Leerlaufschleife in Fig. 5 zurück, um auf mehr auszuführende Aufgaben zu warten. Schließlich lokalisiert das Plattenlaufwerk die gewünschten Daten und sendet einen Interrupt an die SCU. Das Interruptverarbeitungsmodul (nicht dargestellt) bestimmt, daß der Interrupt für die Ausführung eines Einzelbefehls vorgesehen ist und verzweigt nach Plazieren der zugeordneten Befehlswarteschlange in dem Stufenpuffer und der Laufwerksnummer in SCSXDA zu der Einzelschreibroutine.

EINZELSCHREIBEN

Wie in den Figuren 10A und 10B dargestellt, beginnt die Einzelschreibroutine durch Holen der ersten zwei Worte des Befehlswarteschlangeneintrages von dem Stufenpuffer und Speichern in dem Steuerspeicher bei CMDQ1 und CMDQ2. Das EF2-Bit in dem ersten Wort wird gesetzt, bevor das Wort in CMDQ1 gespeichert wird. In Schritt 1002 wird eine Unterroutine aufgerufen, um die Rolltabelle von dem RAM in den Stufenpuffer zu bringen. Als nächstes wird eine Unterroutine aufgerufen, um die globalen Variablen von dem Stufenpuffer zurück in das RAM einzutragen.
Die Speichersteuerungseinheit ist jetzt bereit zum Übertragen eines Datensegmentes vom Cache zu dem selektierten Plattenlaufwerk. Eine Cache-zu-Platte-Unterroutine wird in Schritt 1006 aufgerufen, um die aktuelle Übertragung zu verwirklichen. Nachdem die Übertragung beendet ist, wird eine Steuerungseinheitslaufwerksschnittstellen-(CUDI)-Unterroutine in Schritt 1008 aufgerufen, um das Plattenlaufwerk freizugeben, welches das Datensegment empfangen hat. In Schritt 1010 werden die globalen Variablen wieder von dem RAM in den Stufenpuffer gebracht. In Schritt 1012 wird die Nummer des an der Übertragung beteiligten Laufwerks von dem Steuerspeicher geholt und in GD eingetragen. Dann wird eine Unterroutine aufgerufen, um die Befehlswarteschlange in dem RAM zu nehmen und sie in den Stufenpuffer zu bringen. In Schritt 1016 wird der Wert 4000 in GA als Eingabeparameter für eine Unterroutine eingegeben, welche die SDT aktualisiert. Die SDT-Aktualisierungs-Unterroutine 1018 wird dann ausgeführt, und aufgrund des Wertes in GA wird diese Unterroutine das WT-Bit in Wort 2 des SDT-Eintrages, der dem gerade übertragenen Segment zugeordnet ist, zurücksetzen. Der Zeitmarkeneintrag wird gelöscht, wenn WT gelöscht ist.
In Schritt 1020 wird eine Befehlswarteschlangenlösch-Unterroutine aufgerufen, um den gerade ausgeführten Einzelausführungsbefehl aus der Befehlswarteschlange zu löschen. Das erste Kopfwort der Befehlswarteschlange wird in Schritt 1024 geholt und das erste Laufwer-Beleg-Bit zurückgesetzt. Das Kopfwort wird dann an seinen Ort in dem Stuffenpuffer zurückgegeben.
Als nächstes wird eine Befehlswarteschlangenablege-Unterroutine aufgerufen, um die Befehlswarteschlange in dem Stufenpuffer zurück in das RAM abzulegen. In Schritt 1026 wird die binäre signifikante Laufwerksadresse geholt, invertiert und in GA gespeichert.
SBRSDT ist ein Wort mit einem Flag für jedes Laufwerk, das anzeigt, ob die SDT wiederhergestellt werden soll oder nicht. In Schritt 1028 wird SBRSDT UNDverknüpft mit dem Wert in GA und das Ergebnis wird zu dem Stufenpuffer an dem für SBRSDT reservierten Ort zurückgegeben.
SBGTCQ ist eine binäre signifikante Laufwerksadressenmaske der Befehlswarteschlangen mit anstehenden Einzeiausführungsbefehlen. In Schritt 1030 wird sie von dem Stufenpuffer geholt, mit GA UND-verknüpft, um das Flag für das gerade in der Einzelausführungsoperation verwendete Laufwerk zurückzusetzen und das aktualisierte Wort wird an den Stufenpuffer zurückgegeben.
Als nächstes soll das Einzelausführung-Übersprungen-Flag zurückgesetzt werden, wenn SBGSAT auf den gerade einzeln ausgeführten Eintrag zeigt. In Schritt 1032 werden die Laufwerksadresse (STSXDA) und die Basisadresse (SBTKSA) der Tabelle der SDT-Adressen für Segmente, die auf eine Einzelausführung warten, geholt und die Tabelle wird für den Eintrag angesprochen, der dem Laufwerk entspricht, das gerade in der Einzelausführungsoperation verwendet wurde. Die so von der Tabelle erhaltene Adresse wird nach rechts verschoben, um die entsprechende Zeitmarken-Tabelleneintragsadresse zu erhalten und diese wird in GB gespeichert. Die einzelne SDT-Adresse von der Tabelle wird dann geleert (auflauter Einsen gesetzt) und das Ergebnis wird an die Tabelle zurückgegeben.
In Schritt 1036 wird die für die Einzelausführungsoperation (SBGSAT) verwendete SDT-Adresse geholt und mit der Zeitmarken-Tabelleneintragsadresse in GB verglichen. Wenn sie nicht gleich sind, verzweigt das Programm von Schritt 1038 direkt zu Schritt 1042. Wenn sie gleich sind, wird SBGTSK, die relative SDT- Adresse des ersten beschriebenen Segmentes, übersprungen durch die Einzelausführungsprüf-Unterroutine, da ein Einzelausführungsbefehl nicht dafür gebildet werden kann, geholt, zurückgesetzt und dann in dem Stufenpuffer wiederhergestellt. Das Programm verzweigt dann zu Schritt 1042, wo eine Unterroutine aufgerufen wird, um die globalen Variablen zurück in das RAM abzulegen. CMDQ1 wird dann gelöscht, bevor die Einzelschreibroutine zu der Leerlaufschleife verzweigt.

EINZELAUSFÜHRUNG PRÜFEN

Die Einzelausführungsprüf-Unterroutine sucht anstehende Einzelausführungen, das sind Segmente, welche beschrieben wurden, während sie im Cache vorhanden waren. Diese Segmente sind gekennzeichnet durch das gesetzte WT-Bit in dem zweiten Wort des entsprechenden SDT-Eintrags. Die Suche wird ausgeführt durch Verfolgen der Zeitmarkenverknüpfung, beginnend mit dem ältesten Segment in der Verknüpfung. Wenn eine anstehende Einzelausführung gefunden ist, wird ein Einzelausführungsbefehl in der Befehlswarteschlange für das entsprechende Laufwerk gebildet. Die Unterroutine kann mehr als einen Einzelausführungsbefehl in jedem Aufrufzeitpunkt bilden, sie wird jedoch keinen Einzelausführungsbefehl für jede Befehlswarteschlange bilden, in welcher bereits ein Einzelausführungsbefehl ansteht.
Die Unterroutine wird fortgesetzt, bis eine der folgenden Bedingungen auftritt:
1) alle ansprechbaren Laufwerke haben einen Einzelausführungsbefehl in ihrer Befehlswarteschlange.
2) ein Laufwerk oder ein Host geben eine Anzeige an die SCU ab, daß sie Unterstützung benötigen.
Beim Suchen nach anstehenden Einzelausführungen werden die SDT-Einträge, deren TACK-Bit in Wort 2 gesetzt ist, als Kandidaten für die Einzelausführung übergangen, auch obwohl das WT-Bit gesetzt sein kann. Weiterhin wird jeder SDT-Eintrag für ein Gerät, welches bereits einen Einzelausführungsbefehl in seiner Befehlswarteschlange aufweist, nicht als zur Einzelausführung anstehend betrachtet. In all den obigen Fällen wird der nächste Einzelausführungs-Startadreßglobalbereich (SBGSAT) aktualisiert, so daß, wenn die Einzelausführungsprüfung das nächste Mal aufgerufen wird, die Suche an diesem Punkt beginnt.
Nachdem die Einzelausführungsprüfungs-Unterroutine begonnen hat, wird die Einzelausführungsprüfungs-Unterroutine beendet, wenn erkannt wird, daß das Einzelausführungsuntersagungs-Flag in den Untersystemzustandsbit SBGSTA gesetzt ist, oder alle ansprechbaren Laufwerke einen anstehenden Einzelausführungsbefehl aufweisen oder die Anzahl der beschriebenen Segmente im Cache Null ist.
Wie in Fig. 11A dargestellt, beginnt die Einzelausführungsprüfungs-Unterroutine in Schritt 1100 durch Übertragen der globalen Variablen von dem RAM in den Stufenpuffer. Dann wird eine Prüfung ausgeführt, um zu erkennen, ob Laufwerks- Interrupts vorhanden sind und ob Unterroutinen zum Ausführen des Interrupts beendet werden. Wenn keine Interrupts anstehen, werden in Schritt 1106 die Untersystem-Zustandsbits geprüft, um zu erkennen, ob das Einzelausführungsuntersagungsbit gesetzt ist. Wenn dies der Fall ist, verzweigt die Unterroutine zu Fig. 11G, wo das RAM-Statuswort RAMST aus dem Steuerspeicher geholt wird, aktualisiert wird, um anzuzeigen, daß die globalen Variablen im RAM sind und bei RAMST in dem Steuerspeicher wiederhergestellt. In Schritt 1110 wird eine Unterroutine zum Freigeben des SDT/Cache aufgerufen. Wenn diese Unterroutine beendet ist, kehrt die Einzelausführungsprüfungs-Unterroutine zu der Leerlaufschleife in Fig. 5 zurück.
Wenn die Prüfung in Schritt 1108 anzeigt, daß das Einzelausführungsuntersagungsbit nicht gesetzt ist, verzweigt das Programm in Fig. 11A zu Schritt 1111, wo es SBGWTS von dem Stufenpuffer holt. Dieses Wort zeigt die Anzahl der beschriebenen Segmente im Cache an. Es wird in Schritt 1112 geprüft, und wenn keine beschriebenen Segmente in dem Cache vorhanden sind, verzweigt das Programm zur Fig. 11G und kehrt dann zu der Leerlaufschleife zurück, wie vorstehend beschrieben.
Wenn die Prüfung in Schritt 1112 anzeigt, daß wenigstens ein beschriebenes Segment in dem Cache vorhanden ist, verzweigt das Programm zu Schritt 1113, wo es SBGTCQ holt. Dieses Wort enthält ein Bit für jedes Laufwerk und das Bit ist gesetzt, wenn die Befehlswarteschlange für das entsprechende Laufwerk einen anstehenden Einzelausführungsbefehl aufweist. Dann wird SBGONL geholt. Dieses Wort beinhaltet ein Bit für jedes Laufwerk und ein Bit ist gesetzt, wenn das entsprechende Laufwerk ansprechbar ist. In Schritt 1114 wird SBGONL mit SBGTCQ verglichen, um zu erkennen, ob alle Befehlswarteschlangen wenigstens einen anstehenden Einzelausführungsbefehl aufweisen. Wenn dies der Fall ist, wird zu Fig. 11G verzweigt und eine Rückkehr zur Leerlaufschleife wird ausgeführt, wie vorstehend beschrieben.
Wenn die Prüfung in Schritt 1114 anzeigt, daß wenigstens ein erreichbares Laufwerk vorhanden ist, welches keinen in seiner Befehlswarteschlange anstehenden Einzelausführungsbefehl aufweist, verzweigt das Programm zu Schritt 1115, wo SBGTSK geholt wird. Dieses Wort ist die relative SDT-Adresse des ersten beschriebenen Segmentes, das vorher während der vorherigen Ausführung der Einzelausführungsprüfungs-Unterroutine übersprungen wurde, da das Laufwerk belegt war oder nicht bedient werden konnte. In Schritt 1116 wird SBGTSK mit dem Wert 8000 UND-verknüpft, um zu erkennen, ob das Übersprungen-Flag in der übergeordneten Position von SBGTSK gesetzt ist. Wenn das Übersprungen-Flag nicht gesetzt ist, wird die Suche beginnend mit dem ältesten Zeitmarkeneintrag begonnen. Eine Verzweigung zu Schritt 1117 wird vorgenommen, wo SBLRTS von dem Stufenpuffer geholt wird. Wenn das Übersprungen-Flag in Schritt 1116 nicht aus ist, wird die Suche bei SBGSAT gestartet. Dies ist die SDT-Adresse, die für die Einzelausführung verwendet wird. In Schritt 1118 wird das Übersprungen-Flag zurückgesetzt und SBGSAT wird aus dem Stufenpuffer geholt.
In Schritt 1119 wird entweder SBGSAT aus Schritt 1118 oder SBLRTS aus Schritt 1117 in dem Steuerspeicher als Einzelausführungssuchanfangsadresse gesichert.
In Fig. 11B wird die Einzelausführungssuchanfangsadresse geholt und mit dem Wert 8000 in Schritt 1121 UND-verknüpft, um zu erkennen, ob die letzte Vorwärtsverküpfung oder der Eintrag in der Zeitmarken-Tabelle (Fig. 4) erreicht wurde. Wennn LFL gesetzt ist, wurde die jüngste Eintragsverknüpfung in der Zeitmarkentabelle erreicht und eine weitere Suche ist nicht erforderlich. Eine Verzweigung zu Schritt 1122 wird vorgenommen, wo das Einzelausführung-Übersprungen-Flag in SBGTSK zurückgesetzt wird. Das Programm verzweigt dann zu Fig. 11F, wo eine Unterroutine ausgeführt wird, um die globalen Variablen in dem Stufenpuffer zurück in das RAM abzulegen. Dann wird eine Rückkehr zu der Leerlaufschleife ausgeführt.
Wenn die Prüfung in Schritt 1121, wiederum in Fig. 11B, anzeigt, daß die letzte Vorwärtsverknüpfung nicht erreicht wurde, wird die in Schritt 1120 geholte Anfangsadresse maskiert, um die Vorwärtsverknüpfungsadresse zu erhalten, welche dann in GE als relative Zeitmarkenandresse gespeichert wird. Die Basisadresse der Zeitmarkentabelle in dem Stufenpuffer wird in GB geladen und eine Übertragungslänge von 2 wird in GC geladen. Die Basisadresse der Zeitmarken- Tabelle in dem RAM wird aus dem Steuerspeicher geholt und die relative Zeitmarken-Adresse wird zu ihr hinzugefügt. Das Ergebnis wird in GE zur Verwendung als die Anfangsadresse in einer Operation zum Übertragen von zwei Worten der Zeitmarken-Tabelle von dem RAM in dem Stufenpuffer eingetragen. In Schritt 1125 wird die LESE-RAM-Unterroutine aufgerufen, um zwei Worte mit dem Zeitmarkeneintrag von dem RAM in den Stufenpuffer zu übertragen.
In Schritt 1126 wird die in Schritt 1119 gesicherte Anfangsadresse wiederum geholt und die zwei übergeordneten Bits zum Erhalten der relativen Zeitmarkenadresse werden entfernt. Die Adresse des neuesten Zeitmarkeneintrags (SBMRTS) wird von dem Stufenpuffer geholt und in Schritt 1127 wird SBMRTS mit der relativen Zeitmarkenadresse verglichen, um zu erkennen, ob der neueste Eintrag erreicht wurde. Wenn dies der Fall ist, verzweigt das Programm zu Schritt 1128, wo SBTS1 geholt und geprüft wird (Schritt 1129), um zu erkennen, ob es ein Nullwert ist. Wenn dies der Fall ist, wurde der neueste Eintrag bereits einzeln ausgeführt. Das Programm verzweigt zu Fig. 11F, wo eine Unterroutine ausgeführt wird, um die globalen Variablen zurück in das RAM abzulegen. Dann wird eine Rückkehr zu der Leerlaufschleife ausgeführt.
Wenn die Prüfung in Schritt 1127 anzeigt, daß der jüngste Eintrag in der Zeitmarken-Tabelle noch nicht erreicht wurde, oder wenn die Prüfung in Schritt 1129 anzeigt, daß das Segment entsprechend dem neuesten Eintrag in der Zeitmarken- Tabelle noch nicht einzeln verarbeitet wurde, verzweigt das Programm zu Schritt 1130, wo es die relative SDT-Adresse berechnet und sichert. Da zwei Worte pro Eintrag in der Zeitmarken-Tabelle und vier Worte pro Eintrag in der SDT-Tabelle vorhanden sind, wird die relative SDT-Adresse erhalten durch Multiplizieren der relativen Zeitmarken-Eintragsadresse mit 2. Diese relative Adresse wird dann zu der Basisadresse von SDT addiert, um die absolute Adresse des entsprechenden SDT- Eintrags in dem Stufenpuffer zu erhalten. Der Wert 4 wird in GC eingegeben, um eine Übertragungslänge zu bestimmen und die Basisadresse der SDT in dem RAM wird von dem Steuerspeicher geholt und in GE geladen. In Schritt 1131 wird die LESE-RAM-Unterroutine ausgeführt, um den Vier-Wort-SDT-Eintrag von dem RAM in den Stufenpuffer zu übertragen.
Als nächstes wird in Schritt 1136 Wort 2 des SDT-Eintrages geholt. In den Schritten 1144 und 1145 wird Wort 2 des SDT-Eintrages geprüft, um zu sehen, ob das TACK-Bit oder das Beschrieben-Bit gesetzt ist. Wenn keines der Bits gesetzt ist, ist ein Fehlerzustand vorhanden und die SCU hält an. Wenn das TACK-Bit gesetzt ist, verzweigt das Programm von Schritt 1144 zu Fig. 11H, um das Einzelausführung-Übersprungen-Flag zu prüfen und aktualisiert die nächste Einzelausführungsanfangsadresse. In Schritt 1146 wird das Einzelausführung-Übersprungen- Flag geholt und das Flag wird in Schritt 1147 geprüft. Wenn es gesetzt ist, wird eine Verzweigung zu Fig. 11F ausgeführt, wo die globalen Variablen an das RAM zurückgegeben werden, bevor eine Rückkehr zu der Leerlaufschleife ausgeführt wird.
Wenn das Einzelausführung-Übersprungen-Flag in Schritt 1147 nicht gesetzt ist, wird in Schritt 1148 das Flag gesetzt und in Stufenpuffer zurückgeschrieben. In Schritt 1149 wird die Zeitmarken-Eintrags-Vorwärtsverknüpfung von SBTS2 geholt und in SBGSAT, der für die Einzelausführung verwendeten Adresse, gespeichert. Die Vorwärtsverknüpfung wird ebenfalls in dem nächsten Einzelausführungssicherungsbereich in dem Steuerspeicher gesichert. Zu diesem Zeitpunkt kehrt das Programm zu Fig. 11F zurück, wo die globalen Variablen von dem Stufenpuffer zu dem RAM-Speicher gesendet werden und eine Rückkehr zu der Leerlaufschleife wird ausgeführt.
Wiederum in Fig. 11B verzweigt das Programm zu Schritt 1151 (Fig. 11C), wo das erste Wort des SDT-Eintrages von dem Stufenpuffer geholt und in dem Steuerspeicher gesichert wird, wenn die Prüfung in den Schritten 1144 und 1145 zeigt, daß der SDT-Eintrag nicht "getacked" und das Beschrieben-Bit gesetzt ist. Weiterhin wird die Laufwerksnummer vom SDT-Eintrag zu ADRCNV addiert, der Anfangsadresse der Adreßkonvertierungstabelle. Die Tabelle ist indiziert, um die bitsignifikante Laufwerksadresse vom Steuerspeicher zu holen.
In Schritt 1152 wird SBGTCQ, das Wort, bei dem für jedes Laufwerk mit einem in seiner Befehlswarteschlange eingereihten Einzelausführungsbefehl ein Bit gesetzt ist, von dem Stufenpuffer geholt. In Schritt 1153 wird SBGTCQ mit der bitsignifikanten Laufwerksadresse UND-verknüpft, um zu erkennen, ob bereits ein Einzelausführungsbefehl für dieses Laufwerk eingereiht ist. Die Prüfung wird in Schritt 1153 ausgeführt und wenn bereits ein Einzelausführungsbefehl für dieses Laufwerk eingereiht ist, verzweigt das Programm zu Fig. 111, wo in Schritt 1154 eine Unterroutine ausgeführt wird, um die Befehlswarteschlange aus dem RAM in den Stufenpuffer zu holen. Als nächstes wird eine Prüfung ausgeführt, um zu erkennen, ob SDRA des in der Warteschlange anstehenden Einzelausführungsbefehls mit dem SDRA von dem SDT-Eintrag übereinstimmt. In Schritt 1155 wird das zweite Wort des Befehlswarteschlangeneintrages geholt und das SDRA isoliert. In Schritt 1156 wird das erste Wort des entsprechenden SDT-Eintrages geholt und das SDRA in diesem Wort wird isoliert. In Schritt 1157 werden die zwei SDRA's verglichen. Wenn keine Übereinstimmung besteht, wird SBGTSK geholt und das übergeordnete Bit geprüft, um zu erkennen, ob das Einzelausführung-Übersprungen- Flag an ist. Wenn dies der Fall ist, verzweigt das Programm zu Fig. 11F. Wenn das Einzelausführung-Übersprungen-Flag nicht an ist, wird es in Schritt 1160 gesetzt und SBGTSK zu dem Stufenpuffer zurückgegeben. In Schritt 1161 wird der momentane TS-Eintrag in dem Sicherungsbereich in die Einzelausführungsanfangsadresse SBGSAT geladen, wonach das Programm zu Fig. 11F verzweigt. Ob das Einzelausführung-Übersprungen-Flag an oder aus ist; in Fig. 11F werden die globalen Variablen an das RAM zurückgegeben, wonach die Unterroutine zu der Leerlaufschleife zurückkehrt
In Schritt 1157 verzweigt die Unterroutine zu Fig. 11E, wenn die zwei SDRA's gleich sind, wo in Schritt 1162 das zweite Wort des Zeitmarkeneintrages geholt wird und die Vorwärtsverknüpfung in dem Steuerspeicher gesichert wird, um als nächste Einzelausführungssuchadresse verwendet zu werden. An diesem Punkt prüft die Routine, um zu erkennen, ob noch mehr wichtige Aufgaben durch die SCU auszuführen ist. In Schritt 1161 wird eine Platten-Interrupt-Prüf-Unterroutine ausgeführt, um herauszufinden, ob Platteninterrupts vorhanden sind. Der Rückgabecode für die Platteninterrupt-Unterroutine wird in Schritt 1164 geprüft und in Schritt 1165 wird ein Befehl ausgeführt, um zu erkennen, ob ein EF (Befehl vom Host) ansteht. Wenn kein Interrupt oder EF ansteht, werden in Schritt 1166 SBGTCQ und SBGONL geholt und verglichen. In Schritt 1167 wird das Ergebnis geprüft, um zu erkennen, ob in allen Befehlswarteschlangen Einzelausführungsbefehle anstehen. Wenn wenigstens eine Befehlswarteschlange vorhanden ist, in der kein Einzelausführungsbefehl ansteht, dann wird in Schritt 1168 SBGWTS geholt und in Schritt 1169 wird eine Prüfung ausgeführt, um zu erkennen, ob noch beschriebene Segmente in dem Cache-Speicher vorhanden sind. Wenn dies der Fall ist, verzweigt das Programm zu Fig. 11F, Schritt 1170, wo der neueste Zeitmarken- Eintrag geholt und gesichert wird. In Schritt 1171 wird das Einzelausführungssuchargument aus dem Steuerspeicher geholt, das LFL-Bit wird dem askiert und das Einzelausführungssuchargument mit dem neuesten Zeitmarken-Eintrag verglichen. In Schritt 1172 wird das Ergebnis des Vergleichs geprüft und wenn die zweit Werte gleich sind, wurde der letzte Eintrag in der Zeitmarken-Tabelle geprüft. Das Programm verzweigt zu Schritt 1139, wo das Einzelausführung-Übersprungen-Flag SBTSK geholt wird. In Schritt 1140 wird es geprüft, um zu erkennen, ob es an ist. Wenn dies der Fall ist, verzweigt das Programm zu Schritt 1123, legt die globalen Variablen zurück im RAM ab und kehrt zu der Leerlaufschleife zurück. Wenn das Übersprungen-Flag nicht an ist, verzweigt das Programm von Schritt 1140 zu Schritt 1141, wo das Übersprungen-Flag gesetzt wird und SBGTSK zu dem Stufenpuffer zurückkehrt In Schritt 1142 wird das zweite Wort des Zeitmarken- Eintrages geholt und die Vorwärtsverknüpfungsadresse an einem geeigneten Ort in dem Steuerspeicher gesichert. In Schritt 1143 wird die Vorwärtsverbindungsadresse in dem Stufenpuffer bei SBGSAT gespeichert. Die Unterroutine wird dann aufgerufen, um die globalen Variablen zurück in das RAM zu legen und nachdem dies verwirklicht ist, wird eine Rückkehr zur Leerlaufschleife ausgeführt.
Wenn die Prüfung in Schritt 1172 anzeigt, daß der letzte Eintrag nicht geprüft wurde, verzweigt das Programm zurück zu Schritt 1120 in Fig. 11B, um den nächsten Eintrag zu prüfen.
Wenn die Prüfung in Schritt 1164 anzeigt, daß ein Interrupt ansteht, die Prüfung in Schritt 1165 anzeigt, daß ein EF ansteht, die Prüfung in Schritt 1167 anzeigt, daß in allen Befehlswarteschlangen ein Einzelausführungsbefehl ansteht, oder die Prüfung in Schritt 1169 anzeigt, daß keine geschriebenen Segmente in dem Cache Speicher vorhanden sind, verzweigt das Programm zu Schritt 1139 in Fig. 11F und läuft weiter, wie vorstehend beschrieben.
Zurück in Fig. 11C, wenn die Prüfung in Schritt 1153 anzeigt, daß ein Einzelausführungsbefehl für dieses Laufwerk noch nicht eingereiht ist, verzweigt das Programm zu Schritt 1173, wo SBSDT 2 geholt wird und das lokale Fließbit geprüft wird, um zu erkennen, ob es gesetzt ist. Wenn dies der Fall ist, muß der Eintrag übergangen werden, da das Laufwerk, zu welchem das Segment übertragen werden soll, nicht in Betrieb ist. Das Programm verzweigt zu Schritt 1162 in Fig. 11E und läuft weiter, wie bereits beschrieben. Wenn die Prüfung in Schritt 1173 zeigt, daß das lokale Fließbit in dem SDT-Eintrag nicht gesetzt ist, verzweigt das Programm zu Schritt 1174, wo es prüft, um zu erkennen, ob das Plattenfehler-Bit in Wort 2 des SDT-Eintrages für die SCU zum Ausführen der Einzelausführungsprüfung gesetzt ist. Wenn das Plattenfehlerbit gesetzt ist, muß die Einzelausführung übergangen werden und das Programm verzweigt von Schritt 1174 zu Fig. 11I, wo es weiterläuft, wie bereits beschrieben.
Wenn das Plattenfehlerbit nicht gesetzt ist, wird in Schritt 1175 Wort 2 des Eintrages in der Zeitmarkentabelle geholt und in Schritt 1176 (Fig. 11D) wird ein Test ausgeführt, um zu erkennen, ob die Speichersteuerungseinheit oder das Untersystem im Leerlaufzustand ist. Wenn dies der Fal ist, verzweigt das Programm sofort zu Schritt 1179. Wenn das Untersystem in seinem Leerlaufzustand ist, werden der bei SBGAGE gespeicherte AGEOLD-Wert und der bei SBGTLD gespeicherte TDELTA-Wert geholt.
AGEOLD ist ein Systemparameter, welcher während der Parametrisierung in das System geladen werden kann. Er repräsentiert ein Intervall von Zeit, die verstreicht, nachdem ein Segment das erste Mal durch einen Hostprozessor geschrieben ist, nach welcher das Segment für eine Einzelausführung ansteht. Anders ausgedrückt, Segmente mit einem Alter von weniger als AGEOLD seit ihrem ersten Schreiben werden nicht einzeln ausgeführt. Die Ausnahme davon tritt auf, wenn die Speichersteuerungseinheit im Leerlaufzustand ist, d.h., wenn sie keine anderen Aufgaben zu erledigen hat. In diesem Fall kann ein Segment einzeln ausgeführt werden, auch wenn sein Alter seit dem ersten Schreiben nicht so groß ist wie AGEOLD. TDELTA ist ein Wert, der die Differenz zwischen dem momentanen Zeitmarkenwert und dem ältesten Zeitmarkenwert aller Einträge in der Zeitmarkentabelle darstellt.
Allgemein ausgedrückt ist es erwünscht, beschriebene Segmente nicht einzeln von dem Cache-Speicher zu den Plattenlaufwerken zu übertragen, wenn andere Aufgaben zu erfüllen sind. Einzelausführung während Zeitabschnitten, in denen andere Aufgaben zu erfüllen sind, verringert die Leistung des Systems. Andererseits ist es erwünscht, ein beschriebenes Segment nicht für eine zu lange Periode, nachdem es zuerst beschrieben wurde, in dem Cache-Speicher zu halten, da im Fall eines Cache-Fehlers das Verfahren des Wiederherstellens verlorener Daten zeitaufwendiger werden kann. Die Schritte 1176-1178 umfassen eine Einrichtung zum Ausgleichen dieser zwei Wünsche. Wenn das Untersystem nicht leerläuft und das Alter nach dem ersten Schreiben des ältesten geschriebenen Segmentes (TDELTA) nicht gleich oder größer als AGEOLD ist, prüft das Programm nicht auf anstehende Einzelausführungen, sondern verzweigt von Schritt 1178 zu Fig. 11H und fährt fort, wie bereits beschrieben. Wenn das Untersystem leerläuft (d.h. keine Aktivität über die Host-SCU-Schnittstelle für ein vorgegebenes Intervall von z.B. 200 ms), wird dies in Schritt 1176 erfaßt und das Programm verzweigt zu Schritt 1179 zum Beginnen der Prüfung auf anstehende Einzelausführungen. Wenn das System nicht im Leerlauf ist, wird eine Prüfung in Schritt 1178 ausgeführt, um zu erkennen, ob das älteste beschriebene Segment in dem Cache-Speicher für ein Zeitintervall gleich oder größer als AGEOLD war. Wenn dies der Fall ist, verzweigt das Programm zu Schritt 1179, um auf anstehende Einzelausführungen zu prüfen.
Es wird jetzt angenommen, daß die Prüfung in Schritt 1176 wahr ist, oder daß die Prüfung in Schritt 1176 unwahr ist, aber die Prüfung in Schritt 1178 wahr ist. Das Programm verzweigt zu Schritt 1179, wo SBGTCQ geholt wird, das dieser Befehlswarteschlange entsprechende Bit gesetzt ist und das aktualisierte Wort an den Stufenpuffer zurückgegeben wird. In Schritt 1180 wird die relative SDT-Adresse für den Eintrag aus dem Sicherungsbereich des Steuerspeichers und die Basisadresse SBTSKA der Tabelle der SDT-Adressen für zur Einzelausführung eingereihte Segmente von dem Stufenpuffer geholt. Die in Schritt 1151 gesicherte Laufwerksnummer wird zu SBTSKA addiert, um die Tabelle zu indizieren und den Eintrag zu erhalten. Die relative SDT-Adresse wird eingegeben und der Eintrag wird an seinen Platz in SBTSKA zurückgegeben.
Die Unterroutine ist jetzt bereit, einen Einzelausführungsbefehl zu bilden und ihn in die Befehlswarteschlange einzufügen. In Schritt 1182 wird eine Unterroutine ausgeführt, um die Befehlswarteschlange von dem RAM in den Stufenpuffer zu bringen. Die Einzelausführungspriorität (SBTPRI) wird aus dem Stufenpuffer geholt. Die Einzelausführungspriorität wird durch die Einzeiausführungsprioritätsbestimmungs-Unterroutine der Figuren 16A und 16B berechnet und in Schritt 1642 in SBTPRI eingefügt. Das erste Wort des SDT-Eintrages wird aus dem Steuerspeichersicherungsbereich geholt, wo es in Schritt 1151 gesichert wurde. In Schritt 1184 wird die Host-ID isoliert und mit der Einzelausführungspriorität ODER- verknüft. Das Einzelausführungsbit wird gesetzt und das resultierende Wort wird in dem Steuerspeicher bei CMDQ1 gespeichert.
In Schritt 1186 wird das erste Wort des SDT-Eintrages wiederum aus dem Sicherungsbereich geholt. Die vier übergeordneten SDRA-Bits werden isoliert und ein Wert von 1 wird in das NSEG-Feld eingegeben. Dieses Wort wird dann in dem Steuerspeicher bei CMDQ2 gespeichert.
Die Bildung des dritten Wortes des Befehlswarteschlangeneintrages wird in Schritt 1188 dargestellt und betrifft nur das Holen des vierten Wortes des SDT-Eintrages und sein Speichern an der Position CMDQ3 in dem Steuerspeicher.
Die den Einzelausführungsbefehl umfassenden drei Worte sind jetzt in dem Steuerspeicher vorhanden und in Schritt 1189 wird eine Unterroutine aufgerufen, um den Einzelausführungsbefehl zu der Befehlswarteschlange hinzuzufügen. Nachdem der Einzelausführungsbefehl zu der Befehlswarteschlange hinzugefügt ist, wird eine Unterroutine aufgerufen, um die Befehlswarteschlange zurück in das RAM abzulegen. njDies beendet die Erzeugung und Einfügung eines Einzelausführungsbefehls in eine Befehlswarteschlange. Das Programm verzweigt dann zu Schritt 1162 und läuft weiter, wie bereits beschrieben.
Es ist anzumerken, daß die Folge von Schritten, beginnend mit Schritt 1120 (Fig. 11B) und Fortsetzen infolge durch die Figuren 11B, 11C, 11D und 11E zu Schritt 1172 eine geschlossene Schleife bildet. Die Schleife kann bis zu 16 mal wiederholt werden, wenn 16 Laufwerke und somit 16 Befehlswarteschlangen vorhanden sind. Somit ist es während eines Aufrufes der Einzelausführungs-Prüf-Unterroutine möglich (aber nicht wahrscheinlich), daß 16 Einzelausführungsbefehle, einer für jede Befehlswarteschlange, gebildet werden können.

BEFEHLSWARTESCHLANGENPRÜFUNG

Die Befehlswarteschlangenprüf-Unterroutine wird durch die Leerlaufschleife aufgerufen und liest die Befehlswarteschlangen sequentiell, beginnend mit der prioritätsnächsten, bis sie ein nicht belegtes Laufwerk mit etwas dafür Eingereihtem findet. Wenn sie kein Laufwerk findet, daß diese Anforderungen erfüllt, kehrt sie zu dem Aufrufer mit einem Rückkehrcode von Null in GA zurück. Wenn sie erfolgreich ein Laufwerk findet, das diese Anforderungen erfüllt, verläßt sie die Finde-Warteschlange in dem Stufenpuffer und kehrt mit einem von Null abweichenden Wert in GA zurück.
Wie in Fig. 12A dargestellt, beginnt die Befehlswarteschlangeprüfungs-Unterroutine mit Holen von SDTINF von dem Steuerspeicher. Dieses Wort stellt Informationen über den Ort der SDT in dem Cache bereit. Eine SDT-Selektions-Unterroutine wird dann aufgerufen, um einen Zugriff auf die SDT in dem Cache-Speicher zu selektieren und bereit zu halten. In Schritt 1204 werden die Parameter zum Übertragen des Befehlswarteschlangenkopfes für das Laufwerk mit der nächsten Priorität vom RAM und Plazieren an den Orten SBCMDQ und SBCMQH des Stufenpuffers eingestellt. Es werden nur zwei Worte übertragen, wobei das erste Wort der RAM-Ort ist, der durch CDGPRI festgelegt ist, welches die RAM- Anfangsadresse für den Befehlswarteschlangenkopf ist, der dem Laufwerk mit der höchsten Priorität entspricht. Nachdem diese Parameter eingestellt sind, wird eine Lese-RAM-Unterroutine ausgeführt, um die zwei Kopfworte in den Stufenpuffer zu holen.
In Schritt 1208 wird das erste Kopfwort aus dem Stufenpuffer geholt, maskiert und die Laufwerksnummer in GB gesichert. GC wird verwendet als Schleifeniterationszähler zum Bestimmen, wann alle Befehlswarteschlangen auf einen eingereihten Befehl geprüft wurden.
Die Schleife beginnt bei 1210, wo die momentane Laufwerksnummer in HL eingetragen wird, die Zählung in GC in HH eingetragen wird und das Ergebnis in dem Steuerspeicher bei CDCPRI gespeichert wird.
In Schritt 1212 wird das erreichbare Maskierungswort SBGONL geholt und in GD gesichert. In Schritt 1214 wird die Basisadresse ADRCNV der Adreßkonversionstabelle zu der Laufwerksnummer addiert und die bitsignifikante Laufwerksadresse für das Laufwerk wird aus dem Steuerspeicher geholt. Die bitsignifikante Laufwerksadresse wird dann in Schritt 1216 mit dem erreichbaren Maskierungswort verglichen, um zu erkennen, ob das Laufwerk erreichbar ist. Angenommen, für den Moment ist das nicht der Fall, dann verzweigt das Programm zu Schritt 1218, wo GC um eine Position nach rechts verschoben wird. Eine Prüfung wird dann in Schritt 1218 ausgeführt, um zu erkennen. ob GC auf Null verringert ist. Da dies nicht auftritt, bis 16 Laufwerke geprüft wurden, verzweigt das Programm zu Schritt 1222, wo die Laufwerksnummer in GB erhöht wird. Eine Prüfung wird dann in Schritt 1224 ausgeführt, um zu erkennen, ob GB = 16. Wenn GB nicht gleich 16 ist, läuft das Programm zurück zu Schritt 1210. Wenn jedoch GB = 16, dann wird in Schritt 1226 GB auf Null gesetzt und das Programm kehrt zu Schritt 1210 zurück. Der Grund dafür ist, daß alle 16 Befehlswarteschlangenköpfe entsprechend den 16 Laufwerken geprüft werden müssen, die momentane Prüfoperation jedoch mit dem Laufwerk mit der nächsthöchsten Priorität beginnt, wie durch CDCPRI bestimmt. Die Schritte 1224 und 1222 stellen daher sicher, daß, wenn z.B. CDCPRI anfangs 14 ist und dadurch Laufwerk 14 bestimmt, Laufwerk 15 geprüft wird und dann die Laufwerke 0,1--13 in Folge.
Die Schleife, die die Schritte 1210-1226 umfaßt, wird wiederholt und aktualisiert jedes Mal CDCPRI, spricht die Adreßkonversionstabelle an, um die bitsignifikante Laufwerksadresse zu erhalten und vergleicht sie mit dem erreichbaren Maskierungswort, um zu erkennen, ob das entsprechende Laufwerk erreichbar ist. Angenommen, kein Laufwerk ist erreichbar, dann wird nach der 16. Ausführung der Schleife GC = 0 in Schritt 1220 gefunden. Das Programm verzweigt zu Fig. 12D, wo der nicht gefundene Anzeiger in GA gespeichert wird. Dann wird eine Unterroutine ausgeführt, um die SDT freizugeben, nach welcher Null in ein Register eingegeben wird, das mit CT bezeichnet ist, welches der Cache-Schnittstellensteuerung 112 zugeordnet ist. Dann wird eine Rückkehr zu der Leerlaufschleife mit einer Anzeige in GA, daß keine Befehlswarteschlangen mit einem eingereihten Befehl für sie gefunden wurde, ausgeführt.
Zurück zu Schritt 1216, verzweigt das Programm zu Schritt 1234 in Fig. 12B, wo CDCPRI geholt wird, wenn die Prüfung zeigt, daß das Laufwerk, das geprüft wird, erreichbar ist. Zu diesem Zeitpunkt enthalten die oberen Stellen von CDCPRI den in GC gespeicherten Zählerstand in Schritt 1210 und die unteren Stellen enthalten die Laufwerksnummer, die ebenfalls in Schritt 1210 dort eingetragen wird.
Die Basisadresse der Befehlswarteschlangenübersetzungstabelle CQRTXL wird geholt und zu der Laufwerksnummer in CDCPRI addiert. Das Ergebnis wird verwendet, um auf die Tabelle zuzugreifen und die Adresse der Befehlswarteschlange für das erreichbare Gerät zu holen. In Schritt 1238 werden Vorbereitungen zum Übertragen des Befehlswarteschlangenkopfes für das erreichbare Gerät von dem RAM zu dem Stufenpuffer ausgeführt. Eine Null wird in GD eingetragen, um anzuzeigen, daß die aufzurufende Routine diejenige zum Holen von Information ist und der Wert 2 wird in GC eingetragen, um anzuzeigen, daß zwei Worte zu übertragen sind. Die in Schritt 1236 erhaltene Adresse wird in GE plaziert, um die Anfangsadresse im RAM für die Übertragung festzulegen und die Adresse von SBCMDQ wird in GB plaziert, um die Anfangsposition in dem Stufenpuffer zum Empfangen der Datenübertragung festzulegen. Nachdem diese Operationen ausgeführt sind, wird die Lese-RAM-Unterroutine aufgerufen, um die Befehlswarteschlange für das erreichbare Laufwerk in den Stufenpuffer zu holen.
Nachdem der Befehlswarteschlangenkopf für das erreichbare Laufwerk in den Stufenpuffer eingetragen ist, wird das erste Kopfwort geholt und in Schritt 1244 wird das NCQ-Feld geprüft, um zu erkennen, ob Befehle in dieser Warteschlange vorhanden sind. Wenn dies der Fall ist, wird in Schritt 1246 eine Prüfung ausgeführt, um zu erkennen, ob das von dieser Befehlswarteschlange bediente Laufwerk belegt ist. Wenn keine eingereihten Befehle vorhanden sind oder wenn das zugeordnete Laufwerk belegt ist, gibt es, bezogen auf dieses Laufwerk, keine Aufgabe, die ausgeführt werden kann. Daher soll die Suche durch die Schleife 1210 bis 1226 wieder aufgenommen werden. Bevor diese Suche jedoch wieder aufgenommen wird, verzweigt das Programm zu Fig. 12C, wo eine Interrupt-Prüf- Unterroutine in Schritt 1248 aufgerufen wird. In Schritt 1250 wird eine Prüfung ausgeführt, um zu erkennen, ob ein EF von einem Host vorhanden ist, und in Schritt 1252 wird eine Prüfung ausgeführt, um zu erkennen, ob die Unterroutine in Schritt 1248 irgendwelche Interrupts lokalisiert hat, die eine Verarbeitung erfordern. Wenn ein EF oder anstehender Interrupt vorhanden sind, verzweigt die Unterroutine von Schritt 1250 oder 1252 zu Fig. 12D, wo sie die SDT freigibt, das CT-Register löscht und zu der Leerlaufschleife zurückkehrt, wo sie die besondere Operation, welche auszuführen ist, findet.
Wenn keine EFS oder anstehenden Interrupts vorhanden sind, dann wird in Schritt 1254 CDCPRI geholt, seine Laufwerksnummer wird in GB eingetragen und sein Zähler wird in GC eingetragen. Das Programm kehrt dann zu Schritt 1218 zurück und fährt mit dem aufeinanderfolgenden Prüfen der Laufwerke für ein erreichbares Laufwerk fort. Wie vorher wird, wenn ein erreichbares Laufwerk gefunden ist, in Schritt 1216 eine Verzweigung zu Schritt 1234 ausgeführt, um zu erkennen, ob das Laufwerk nicht belegt ist und ob ein Befehl dafür eingereiht ist.
Wenn ein erreichbares Laufwerk gefunden ist, welches nicht belegt ist, aber für das ein Befehl eingereiht ist, verzweigt das Programm von Schritt 1246 zu Schritt 1256, wo es vorbereitet, die gesamte Befehlswarteschlange für das nicht belegte Laufwerk zu erhalten. CDCPRI wird geholt und bei STSXDA als die momentane Laufwerksnummer gespeichert. Die Laufwerksnummer in HL wird in GD eingetragen und eine Lese-Befehlswarteschlangen-Unterroutine wird aufgerufen, um die Befehlswarteschlange für das nicht belegte Laufwerk aus dem RAM für den Stufenpuffer zu holen.
Die Operationen in Schritt 1260 holen CDCPRI von dem Steuerspeicher und erhöhen es um 1, um die nächste Laufwerkspriorität einzustellen. Die Laufwerksnummer wird demaskiert und als die erste Adresse in dem Stufenpuffer gesichert. In Schritt 1262 werden Vorbereitungen zur Übertragung von zwei Worten von dem Stufenpuffer, beginnend an der Position Null, zu dem RAM, beginnend an der Adresse CDGPRI, getroffen. Die Schreib-RAM-Unterroutine wird dann aufgerufen, um die Übertragung auszuführen. In Schritt 1266 wird der Wert 8000 in GA geladen, um der aufrufenden Routine anzuzeigen, daß die Befehlswarteschlangenprüf-Unterroutine einen auszuführenden Befehl gefunden hat. Eine Rückkehr zu der Leerlaufschleife wird dann ausgeführt und in Schritt 504 veranlaßt die Anzeige in GA die Leerlaufschleife, zu der Servicebefehlswarteschlangenroutine zu verzweigen.

FINDE BEFEHLSWARTESCHLANGENEINTRAG

Die Figuren 13A und 13B umfassen ein Flußdiagramm, das die Befehlswartesch- Iangeneintragsfinde-Unterroutine darstellt. Diese Unterroutine wird aufgerufen durch die Cache-Durchbruchsroutine, um einen momentanen Befehl zu finden, oder wird aufgerufen durch die Servicebefehlswarteschlangenroutine, um den nächsten Befehl in der Befehlswarteschlange zur Ausführung zu bestimmen. Die Figuren 13A und 13B stellen nur die Operationen der Unterroutine dar, die ausgeführt werden, wenn die Unterroutine durch die Service-Befehlswarteschlangen-Routine aufgerufen wird.
Zu dem Zeitpunkt, in dem die Unterroutine aufgerufen wird, befinden sich CMDQI und CMDQ2 in dem Steuerspeicher und eine Kopie der Befehlswarteschlange befindet sich in dem Stufenpuffer, beginnend an der Position SBCMDQ. Die Routine beginnt in Schritt 1302 mit dem Holen des ersten Kopfwortes für die Befehlswarteschlange und Prüfen von NCQ, um zu erkennen, ob Befehle für dieses Laufwerk eingereiht sind. Wenn NCQ = 0 ist, sind keine eingereihten Befehle für dieses Laufwerk vorhanden und das Programm verzweigt in Schritt 1304 zu Schritt 1306, wo der Wert 1 in GA eingetragen wird. Dies ist ein Rückkehrcode für die aufrufende Routine, um die aufrufende Routine zu informieren, daß die Unterroutine beim Finden eines Eintrages erfolglos war. Nachdem GA gesetzt ist, kehrt die Unterroutine zu der aufrufenden Routine zurück.
Wenn die Befehlswarteschlange nicht leer ist, verzweigt das Programm von Schritt 1304 zu Schritt 1308, wo der durch die aufrufende Routine in GA vorgesehene Anforderungscode geprüft wird, um zu erkennen, ob die aufrufende Routine die Unterroutine zum Finden des aktuellen oder des Eintrags mit der nächsthöchsten Priorität aufrufen will. Wenn der aktuelle Eintrag (EF2) gesucht wird, verzweigt das Programm zu einer Folge von Schritten (nicht dargestellt), um den aktuellen Eintrag zu finden. Diese Schritte sind für die vorliegende Erfindung nicht relevant.
Wenn die Prüfung in Schritt 1308 anzeigt, daß der nächste auszuführende Befehl gefunden ist, verzweigt das Programm zu Fig. 138, wo Schritt 1310 den Wert 8000 in GA lädt, wonach die Unterroutine zum Bestimmen der Einzelausführungspriorität aufgerufen wird. Der in GA geladene Wert teilt der Unterroutine zum Bestimmen der Einzelausführungspriorität mit, daß sie die Priorität des Einzelausführungsbefehls in der Befehlswarteschlange zu aktualisieren hat, nachdem die Priorität bestimmt wurde.
Nachdem die Einzelausführungspriorität bestimmt und der Befehl in Schritt 1312 aktualisiert wurde, verzweigt das Programm zu Schritt 1315, wo eine Prüfung ausgeführt wird, um zu erkennen, ob vier oder mehr Befehle ihre Ausführung in der Befehlswarteschlange erwarten. Wenn nicht, verzweigt das Programm zu den Schritten 1317 und 1318, um den Befehlseintrag mit der höchsten Priorität und der niedrigsten Folgenummer zu finden, gefolgt von Sichern der Befehlsadresse in GD. Die Einzelheiten einer bevorzugten Weise zum Ausführen der Schritte 1317 und 1318 sind in der zuvor erwähnten US-Patent-Nr. 4,523,206 beschrieben. Nach Schritt 1318 verzweigt das Programm zu Fig. 13A.
Wenn vier oder mehr Befehle ihre Ausführung erwarten, verzweigt das Programm statt dessen zu Schritt 1319, wo die momentanen Zylinder- und Winkelpositionen des entsprechenden Plattenlaufwerkes bestimmt werden. Diese Bestimmung kann basierend auf Positionsdaten ausgeführt werden, die durch das Plattenlaufwerk oder Verwenden der SDRA- und NSEG-Werte (Fig. 3) eines Befehlseintrages ausgeführt werden, dessen Ausführung gerade beendet wurde. Das Programm verzweigt dann zu Schritt 1321, wo ein erster anstehender Befehlseintrag geholt und dann in Schritt 1323 geprüft wird, um zu bestimmen, ob er eine Priorität aufweist, welche höher als eine vorbestimmte Priorität ist. Wenn dies der Fall ist, wird der Befehl zur sofortigen Ausführung selektiert und das Programm verzweigt über Schritt 1318 zu Fig. 13A. Wenn dies nicht der Fall ist, wird eine andere Prüfung in Schritt 1325 ausgeführt, um zu bestimmen, ob der bestehende Befehlseintrag 16 mal bei der Ausführung unberücksichtigt geblieben ist (d.h. nicht selektiert wurde). Wenn dies der Fall ist, wird er zur sofortigen Ausführung selektiert und das Programm verzweigt über Schritt 1318 zu Fig. 13A.
Somit verzweigt das Programm zu Schritt 1327, wenn der anstehende Befehl nicht eine Priorität hat, welche höher als der zugeordnete vorbestimmte Prioritätspegel ist und ebenfalls bei der Ausführung nicht 16 mal unberücksichtigt geblieben ist. In Schritt 1327 wird die Anfangsaufzeichnungsposition des anstehenden Befehls (das ist der Plattenzylinder und die Winkelposition seiner ersten Aufzeichnung) aus dem zweiten Wort des Befehlseintrages (Fig. 3) bestimmt. Diese werden dann verwendet, um die zum Erreichen dieses Ortes erforderliche Gesamtzeit zu berechnen (wobei der Mikroprozessor-Overhead, die Kopfsuchzeit und die Rotationsverzögerungszeit berücksichtigt werden), unter Verwendung der vorher in Schritt 1319 bestimmten momentanen Zylinder- und Winkelposition. Diese berechnete Gesamtzeit wird in Schritt 1329 geprüft (gegen den vorhandenen Gesamtzeitwert in GB), um zu bestimmen, ob es der beste (schnellste) der bis dahin geprüften anstehenden Befehle ist. Wenn dies der Fall ist, verzweigt das Programm zu Schritt 1331, in welchem die Adesse dieses besten anstehenden Befehls in GD gesichert wird und die entsprechende Gesamtzeit in GB gesichert wird, wonach das Programm zu Schritt 1331 verzweigt. Wenn die Gesamtzeit nicht die bisher beste ist, verzweigt das Programm direkt zu Schritt 1331. In Schritt 1331 wird eine Prüfung ausgeführt, um zu bestimmten, ob das Ende der Befehlswarteschlange erreicht wurde. Wenn dies nicht der Fall ist, verzweigt das Programm zurück zu Schritt 1321, um den nächsten anstehenden Befehl zu holen. Wenn dies der Fall ist, verzweigt das Programm zu Fig. 13A.
Um ein besseres Verständnis der in Schritt 1327 in Fig. 13B auftretenden Operationen zu erreichen, wird Bezug genommen auf verschiedene Zeitfaktoren, die beim Bestimmen, welcher von zwei anstehenden Befehlen für die Ausführung selektiert werden sollte, betroffen sind, basierend darauf, welcher in der Lage ist, seinen Anfangsplattenplatz in der kürzesten Zeit anzusprechen.
Die Zeit T1 stellt die Zeit dar, in welcher der momentane Zylinder und die Winkelposition in Schritt 1319 in Fig. 13B bestimmt sind, während M den Mikroprozessor- Overhead (eine bekannte Konstante) darstellt. Zwei mögliche anstehende Befehle sind mit Kandidat 1 und Kandidat 2 bezeichnet. Die Kandidatenanfangsaufzeichnung (bekannt aus dem Kandidatenbefehlseintrag der Befehlswarteschlange) erscheint einmal pro Umdrehung und wird angezeigt durch R1 für Kandidat 1 und R2 für Kandidat 2. Die Suchzeiten für die Kandidaten 1 und 2 (in Schritt 1327 in Fig. 13B bestimmt) werden jeweils durch S1 und S2 angezeigt und die Rotationsverzögerungszeiten (ebenfalls in Schritt 1327 bestimmt) werden jeweils durch L1 und L2 angezeigt. Die für die Kandidaten 1 und 2 erforderlichen Gesamtpositionierungszeiten TT1 und TT2 sind daher entsprechend TT1 = S1 + L1 und TT2 = S2 + L2. Angenommen, S2 > S1 und L2 < L1. Es ist erkennbar, daß Kandidat 2 vor Kandidat 1 zur Ausführung selektiert wird, wenn seine Gesamtpositionierungszeit TT2 kürzer als TT1 von Kandidat list. Obwohl Kandidat 2 eine längere Suchzeit S2 im Vergleich zu der für Kandidat 1 erforderlichen Suchzeit S1 benötigt, weist Kandidat 2 eine deutlich kürzere Verzögerungszeit L2 als L1 von Kandidat 1 auf, darin resultierend, daß Kandidat 2 die schnellste Gesamtpositionierungszeit TT2 aufweist.
Wenn das Programm Schritt 1334 in Fig. 13A erreicht (nach Verlassen von Fig. 13B auf den bereits beschriebenen verschiedenen Wegen) enthält GD die relative Adresse des selektierten Eintrags in der Befehlswarteschlange. Aus der vorstehenden Beschreibung von Fig. 13B ergibt sich, daß, wenn weniger als vier Befehle die Ausführung in der Befehlswarteschlange abwarten, der selektierte Eintrag derjenige mit der höchsten Priorität und der niedrigsten Folgenummer sein wird. Wenn vier oder mehr Befehle ihre Ausführung in der Befehlswarteschlange abwarten und keiner eine Priorität unterhalb eines vorbestimmten Prioritätspegels aufweist und keiner bei der Selektion mehr als 16 mal übergangen wurde, dann wird der selektierte Eintrag derjenige mit der schnellsten erforderlichen Positionierungszeit auf dem entsprechenden Plattenplatz unter Berücksichtigung der Mikroprozessor-Overheadzeit, der Suchzeit und der Rotationsverzögerung sein. Falls, wenn mehr als vier Befehle ihre Ausführung abwarten, wenigstens einer eine Priorität oberhalb einer vorbestimmten Prionätsebene aufweist oder bei der Selektion 16 mal übergangen wurde, dann wird der selektierte Eintrag der erste dieser Zusammentreffen beim Ausführen des Flußdiagramms in Fig. 13B sein.
In Schritt 1334 in Fig. 13A wird der Wert in GB verglichen mit dem Wert FFFF, welcher vor dem Holen eines Befehlseintrages in Fig. 13B in GB plaziert ist.
Wenn GB = FFFF ist, bedeutet dies, daß alle Plätze in der Befehlswarteschlange leer sind oder jeder belegte Platz einen Befehl enthält, der durch die andere SCU ausgeführt wird. Daher hat die Unterroutine keinen Eintrag für die Ausführung gefunden. Eine Verzweigung wird zu Schritt 1306 ausgeführt, wo GA gesetzt wird, um die "nicht gefunden"-Bedingung der aufrufenden Routine anzuzeigen. Dann wird eine Rückkehr zu der aufrufenden Routine ausgeführt.
Wenn GB in Schritt 1334 nicht gleich FFFF ist, bedeutet dies, daß die Unterroutine einen auszuführenden Befehl gefunden hat. In Schritt 1336 wird die Adresse dieses selektierten Befehls von GD zu dem Stufenpufferadreßregister BX übertragen. In Schritt 1338 werden die drei Worte, die den selektierten Befehlswarteschlangeneintrag umfassen, von dem Stufenpuffer angesprochen und zu den Positionen CMDQ1, CMDQ2 und CMDQ3 in den Steuerspeicher verschoben. In Schritt 1340 wird die Anforderungsnummer von CMDQ1 in SBCMQH in dem aktiven Befehlsanforderungsnummernfeld eingetragen. In Schritt 1342 wird die Anforderungsnummer von CMDQ1 verwendet, um die Anforderungsnummerposition STSXRN in dem Steuerspeicher zu aktualisieren. In Schritt 1344 wird GA gelöscht, um der aufrufenden Routine anzuzeigen, daß ein Befehl zur Ausführung gefunden wurde und nachdem GA aktualisiert ist, wird eine Rückkehr zu der aufrufenden Routine ausgeführt.

AKTUALISIERE TACK/WT

Die Figuren 14A-14F zeigen die Aktualisiere-TACK/WT-Unterroutine. Diese Unterroutine wird zum Aktualisieren der TACK und Beschrieben-(WT)-Bits in dem zweiten Wort eines SDT-Eintrages aufgerufen. Zwei laufende Zähler werden unterstützt, wobei ein Zähler die Anzahl der beschriebenen Segmente im Cache anzeigt und der andere die Anzahl der leeren Segmente im Cache anzeigt. Die Unterroutine inkrementiert oder dekrementiert einen oder beide Zähler abhängig davon, welche Operation zur Ausführung aufgerufen wird. Nachdem die Zähler aktualisiert sind, ruft die Unterroutine die Zeitmarken-Additions/Lösch-Unterroutine zum Aktualisieren der Zeitmarkentabelle auf. Nach der Rückkehr von der Zeitmarkentabelle kehrt die Aktualisiere-TACK/WT-Unterroutine zu der aufrufenden Routine zurück.
Die Aktualisiere-TACK/WT-Unterroutine wird jedes Mal aufgerufen, wenn eine Änderung in den Segmentdeskriptortabelleneinträgen vorgenommen wird. Somit kann es vorkommen, wenn ein SDT-Eintrag gebildet wird, wenn ein SDT-Eintrag gelöscht wird oder wenn die SDT aktualisiert wird. Die aufrufende Routine übergibt einen Parameter an die Aktualisiere-TACK/WT-Unterroutine in GA, der anzeigt, ob das TACK-Bit gesetzt oder zurückgesetzt werden soll, das WT-Bit gesetzt oder zurückgesetzt werden soll, oder das TACK-Bit gesetzt und der SDT-Eintrag in dem RAM aktualisiert werden soll. Zum Aktualisieren des RAM plaziert die aufrufende Routine den relativen SDT-Eintrags-Zeiger in GB vor dem Aufrufen der Aktualisiere- TACK/WT-Unterroutine.
In Fig. 14A beginnt die Aktualisiere-TACK/WT-Unterroutine mit Holen des zweiten Wortes des SDT-Eintrages von dem Stufenpuffer und Plazieren der oberen Hälfte des Wortes in GE. Als nächstes wird die Zählung der Anzahl der beschriebenen Segmente SBGWTS von dem Stufenpuffer geholt und in GD plaziert. Die Zählung der Anzahl der leeren Segmente SBGMTS wird von dem Stufenpuffer geholt und in HL gehalten.
In den Schritten 1404, 1406, 1408, 1410 und 1412 wird der Wert in GA geprüft, um zu erkennen, ob die aufrufende Routine angeordnet hat, daß das TACK-Bit zurückgesetzt wird, das WT-Bit zurückgesetzt wird, das TACK-Bit gesetzt wird, das WT-Bit gesetzt wird oder das TACK-Bit gesetzt und der SDT-Eintrag in dem RAM aktualisiert wird. Wenn der Wert in dem GA-Register keine dieser Operationen aufruft, wird in Schritt 1412 eine Verzweigung aufgerufen und ein STOP-Befehl wird ausgeführt, um die SCU aufgrund des Eingabeparameterfehlers anzuhalten.
In Schritt 1404 wird, wenn die Prüfung zeigt, daß die Unterroutine zum Zurücksetzen des TACK-Bits aufgerufen wurde, eine Verzweigung zu Schritt 1414 vorgenommen, um zu erkennnen, ob das TACK-Bit an ist. Wenn dies der Fall ist, wird das TACK-Bit in der GE enthaltenen oberen Hälfte des SDT-Eintragswortes zwei zurückgesetzt.
Beim Zählen der Anzahl der leeren Segmente im Cache werden die Segmente, die "ungetacked" sind, oder beschrieben sind, wie durch Wort zwei des entsprechenden SDT-Eintrags angezeigt, von der Zählung ausgenommen. Da ein TACK-Bit in Schritt 1415 zurückgesetzt wurde, wird die Anzahl der leeren Segmente nur erhöht, wenn nicht das WT-Bit des unmarkierten Segments an ist. Eine Prüfung wird in Schritt 1416 ausgeführt, und wenn das WT-Bit an ist, wird die Zählung der Anzahl der leeren Segmente in HL in Schritt 1418 inkrementiert. Das Programm verzweigt dann zu Fig. 14E, wo die Anzahl der leeren Segmente in HL in dem Stufenpuffer bei SBGMTS gespeichert wird. Die Anzahl der beschriebenen Elemente in GD ist unverändert geblieben und dieser Wert wird zu SBGWTS zurückgegeben. Das zweite Wort des SDT-Eintrages wird geholt und das halbe Wort in der oberen Hälfte mit dem Inhalt von GE aktualisiert, wobei das Ergebnis zu SBSDT2 zurückgegeben wird.
In Schritt 1476 wird Bit 7 des ST-Registers geprüft, um zu erkennen, ob es gesetzt ist. Dieses Bit wurde in Schritt 1402 zurückgesetzt und ist unverändert geblieben. Daher kehrt das Programm von Schritt 1476 zu der aufrufenden Routine zurück. Diese umgeht die Zeitmarken-Hinzufüge/Lösch-Unterroutine, da keine Veränderung in der Anzahl der beschriebenen Segmente aufgetreten ist.
Wenn Schritt 1414 erkennt, daß das TACK-Bit nicht an ist, oder wenn es an ist, Schritt 1416 findet, daß das WT-Bit an ist, wird keine Änderung in der Zählung der Anzahl der leeren Segmente vorgenommen. Das Programm verzweigt direkt von Schritt 1414 oder 1416 zu Fig. 14E, wo die gleichen Operationen ausgeführt werden, wie bereits beschrieben. In diesem Fall wurde jedoch die Zählung der Anzahl der leeren Segmente in HL nicht inkrementiert, womit die aus SBGMTS, SBGWTS und SBSDT2 in Schritt 1402 gelesenen gleichen Werte in Schritt 1474 zu dem Stufenpuffer zurückgegeben werden.
Wenn die aufrufende Routine einen Parameter in GA übergeben hat, der anzeigt, daß das TACK-Bit gesetzt sein soll, wird dies in Schritt 1408 erfaßt. Das Programm verzweigt zu Fig. 14C, wo das TACK-Bit geprüft wird, und zu Schritt 1438, um zu erkennen, ob es an ist. Wenn dies der Fall ist, verzweigt das Programm sofort zu Fig. 14E. Wenn das TACK-Bit nicht an ist, wird dies in GE in Schritt 1440 gesetzt und in Schritt 1442 wird ein Test ausgeführt, um zu erkennen, ob das WT-Bit an ist. Wenn dies der Fall ist, verzweigt das Programm zu Fig. 14E. Wenn das WT-Bit nicht an ist, wird die Einstellung des TACK-Bit in Schritt 1440 um Eins in der Segmente in HL um eins verringert und das Programm verzweigt zu Fig. 14E.
Wenn die aufrufende Routine eine Anzeige in GA gesetzt hat, um anzuzeigen, daß das WT-Bit zurückgesetzt werden soll, wird diese Bedingung in Schritt 1406 erfaßt und das Programm verzweigt zu Fig. 14B. In Schritt 1420 wird das Beschrieben-Bit geprüft und wenn es nicht an ist, verzweigt das Programm zu Schritt 14E. Wenn das WT-Bit an ist, wird es zurückgesetzt in Schritt 1421. In Schritt 1422 wird die Laufwerksadresse STSXDA geholt und in GA gesichert und SBTKSA die Basisadresse der BSDA-Einzelausführungs-Tabelle wird geholt. Die zwei Werte werden addiert und verwendet, um die Tabelle zu indexieren. Der davon in Schritt 1423 gelesene Wert wird dekrementiert und in Schritt 1424 an die Tabelle zurückgegeben.
In Schritt 1425 wird die Anzahl der beschriebenen Segmente in GD dekrementiert, ST7 wird gesetzt und der Wert 4000 wird in GA als Parameter für die Zeitmarken- Hinzufüge/Lösch-Unterroutine eingetragen, welche aufgerufen wird. In Schritt 1426 wird das TACK-Bit geprüft und wenn es nicht an ist, wird die Zählung der Anzahl der leeren Segmente inkrementiert. Wenn das TACK-Bit an ist, wird das Inkrementieren der Anzahl der leeren Segmente umgangen.
In jedem Fall verzweigt das Programm zu Fig. 14E, wo SBGMTS, SBGWTS und SBSDT2 akutualisiert werden. In Schritt 1476 wird gefunden, daß Bit 7 des ST- Registers gesetzt ist. Die Zeitmarken-Hinzufüge/Lösch-Unterroutine wird in Schritt 1478 aufgerufen und nach Beendigung dieser Unterroutine wird eine Rückkehr von der Aktualisiere-TACK/WT-Unterroutine zu ihrer aufrufenden Routine ausgeführt. Der in GA in Schritt 1425 eingetragene Wert 4000 teilt der Zeitmarken-Hinzufüge/- Lösch-Unterroutine mit, daß sie einen Zeitmarkeneintrag aus der Zeitmarkentabelle löschen soll.
Wenn die Routine, welche die Aktualisiere-TACK/WT-Unterroutine aufruft, einen Anzeiger in GA gesetzt hat, um anzuzeigen, daß das WT-Bit gesetzt werden soll, wird diese Bedingung in Schritt 1410 erfaßt und das Programm verzweigt zu Fig. 14D. Eine Prüfung wird ausgeführt, um zu erkennen, ob WT an ist, und wenn dies der Fall ist, verzweigt das Programm zu Fig. 14E, aktualisiert SGBMTS, SBGWTS und SBSDT2 und kehrt dann unter Umgehung der Zeitmarken-Hinzufüge/Lösch- Unterroutine zu der aufrufenden Routine zurück.
Wenn die Prüfung in Schritt 1430 anzeigt, daß das WT-Bit an ist, wird es in 1431 zunickgesetzt. Die Schritte 1432, 1433 und 1434 holen STSXTA und SBTKSA, addieren die zwei, indexieren die Tabelle der SDT-Adressen von Segmenten, die auf eine Einzelausführung warten, inkrementieren die Zählung der oberen Worthälften der indexierten Einträge und schreiben den Eintrag zurück. In Schritt 1435 wird die Anzahl der beschriebenen Segmente inkrementiert, Bit 7 in dem ST-Register gesetzt und der Wert 8000 in GA eingetragen.
In Schritt 1436 wird das TACK-Bit geprüft, und wenn es an ist, verzweigt das Programm zu Fig. 14E. Wenn das TACK-Bit nicht an ist, wird die Anzahl der leeren Segmente dekrementiert und das Programm verzweigt zu Fig. 14E. In Fig. 14E werden SBGMTS, SBGWTS und SBSDT2 aktualisiert. In Schritt 1476 zeigt die Prüfung, daß ST7 gesetzt ist, so daß die Zeitmarken-Hinzufüge/Lösch-Unterroutine aufgerufen wird. Da GA den Wert 8000 enthält, wird die Zeitmarken-Hinzufüge/- Lösch-Unterroutine einen Eintrag zu der Zeitmarkentabelle hinzufügen. Nachdem die Zeitmarken-Hinzufüge/ Lösch-Unterroutine beendet ist, wird eine Rückkehr zu der Aktualisiere-TACK/WT-Unterroutine ausgeführt und von ihr wird eine Rückkehr zu der Routine ausgeführt. welche die Aktualisiere-TACK/WT-Unterroutine aufgerufen hat.
Wenn die Routine, welche die Aktualisiere-TACK/WT-Unterroutine aufruft, einen Wert in GA eingetragen hat, der das TACK-Bit gesetzt erfordert und den SDT- Eintrag in dem RAM aktualisiert, wird diese Bedingung in Schritt 1412 erfaßt und das Programm verzweigt zu Fig. 14F. Das TACK-Bit wird in Schritt 1450 geprüft, und wenn es bereits an ist, verzweigt das Programm zu Schritt 1470, wo die Basisadresse der SDT-Tabelle im RAM (CDCSDT) geholt wird und zu dem relativen SDT-Eintrags-Zeiger addiert wird, welcher durch den Aufrufer in Register GB an die Aktualisiere-TACK/WT-Unterroutine übergeben wurde. Das Ergebnis ist die absolute Adresse des SDT-Eintrages in dem RAM.
Vorbereitungen zum Übertragen des SDT-Eintrages zum RAM werden getroffen. Diese Vorbereitungen beinhalten ein Laden der Anfangsposition des SDT in dem Stufenpuffer in GB, Einstellen des Wertes in GC als Länge der Übertragung, die statttfinden soll und Einstellen des Bit F des ST-Registers zum Anzeigen, daß die Routine, die aufzurufen ist, Daten in dem RAM ablegen soll. In Schritt 1472 wird die Schreibe-RAM-Unterroutine aufgerufen, um die Übertragung des Vier-Wort-SDT- Eintrages zu der SDT in dem RAM zu verwirklichen. Nach der Beendigung der Unterroutine wird eine Rückkehr ausgeführt zu der Aktualisiere-TACK/WT- Unterroutine und dann wird eine Rückkehr ausgeführt zu der Routine, welche die Aktualisiere-TACK/WT-Unterroutine aufgerufen hat.

ZEITMARKE HINZUFÜGEN/LÖSCHEN

Die Zeitmarke-Hinzufüge/Lösch-Unterroutine fügt einen Zeitmarken-Eintrag zu der im Cache-Speicher positionierten Zeitmarken-Tabelle hinzu oder entfernt ihn daraus. Die aufrufende Routine plaziert den Wert 8000 in GA, wenn die Zeitmarken- Hinzufüge/Lösch-Unterroutine einen Zeitmarkeneintrag hinzufügen soll und plaziert den Wert 4000 in GA, wenn die Unterroutine einen Zeitmarkeneintrag löschen soll. Die aufrufende Routine übergibt ebenfalls die SDT-Adresse des zu verarbeitenden Eintrags in GE. Die Zeitmarken-Hinzufüge/Lösch-Unterroutine erzeugt zuerst die Adresse des Eintrages in der Zeitmarken-Tabelle aus der SDT-Adresse und prüft dann GA, um zu erkennen, ob eine Hinzufüge- oder Lösch-Operation auszuführen ist.
Für eine Hinzufüge-Operation wird der neue Eintrag mit der vom Host gesendeten Zeitmarke geladen, das LFL-Bit in Wort 2 des Eintrages wird gesetzt und alle Bits der Vorwärtsverknüpfung werden gesetzt. Wenn ein vorheriger Eintrag existiert, wird die Rückwärtsverknüpfung des neuen Eintrages mit der Adresse des vorherigen Eintrages geladen und LBL des neuen Eintrages wird zurückgesetzt, der neueste Eintragszeiger mit der neuen Eintragsadresse geladen, LFL des vorherigen Eintrags wird zurückgesetzt und die Vorwärtsverknüpfung des vorherigen Eintrages wird mit der Adresse des neuen Eintrages geladen.
Wenn der neue Eintrag der einzige Eintrag in der Zeitmarken-Tabelle ist, werden LBL und BL des neuen Eintrages auf Einsen gesetzt, der Zeiger auf der neuesten Eintrag und der Zeiger auf den ältesten Eintrag werden mit der Adresse des neuen Eintrags geladen und TOLDEST wird mit der Zeitmarke des neuen Eintrags geladen.
Für eine Löschoperation werden die Zeitmarke, LBL und LFL zurückgesetzt, während BL und FL beide auf Einsen gesetzt werden. Wenn der Eintrag der letzte gültige Eintrag in der Zeitmarken-Tabelle ist, wird TOLDEST zurückgesetzt, während der Zeiger auf den neuesten Eintrag und der Zeiger auf den ältesten Eintrag zurückgesetzt werden. Wenn der Eintrag der neueste Eintrag ist, werden LFL und FL des vorherigen Eintrages gesetzt und der Zeiger auf den neuesten Eintrag aktualisiert, damit er auf den vorherigen Eintrag zeigt. Wenn der Eintrag der älteste Eintrag ist, werden LBL und BL des nächsten Eintrags gesetzt, der Zeiger auf den neuesten wird aktualisiert, um auf den nächsten Eintrag zu zeigen, und TOLDEST wird mit der Zeitmarke des nächsten Eintrages geladen. Wenn der gelöschte Eintrag der einzige Eintrag ist, werden der Zeiger auf den neuesten Eintrag und der Zeiger auf den ältesten Eintrag gesetzt und TOLDEST wird zurückgesetzt.
Die Zeitmarken-Hinzufüge/Lösch-Unterroutine beginnt in Fig. 15A mit Dividieren der relativen SDT-Adresse durch zwei, um die relative Zeitmarken-Tabellen-Adresse zu erhalten. Der Grund dafür ist, daß vier Worte pro SDT-Eintrag vorhanden sind, aber nur zwei Worte pro Zeitmarken-Tabelleneintrag. Die relative Zeitmarken-Tabellen- Adresse wird dann zu der Basisadresse der Zeitmarken-Tabelle addiert, um die absolute Tabellenadresse des Zeitmarken-Eintrages zu erhalten.
In Schritt 1502 wird der Eingabeparameter in GA geprüft, um zu erkennen, ob er eine Löschoperation aufruft. Angenommen, er tut das nicht, dann wird der Eingabeparameter in GA geprüft, um zu erkennen, ob er eine Hinzufügeoperation aufruft. Wenn er dies nicht tut, führt das Programm einen STOP-Befehl aus, da der Eingabeparameter nicht gültig ist.
Wenn die Prüfung in Schritt 1504 anzeigt, daß eine Hinzufügeoperation auszuführen ist, dann wird ein Eintrag in der Zeitmarkentabelle vorgenommen. Die exakten Operationen, die ausgeführt werden, um einen Eintrag hinzuzufügen, hängen davon ab, ob der neue Eintrag der einzige Eintrag in der Zeitmarkentabelle ist oder nicht oder ob bereits ein vorheriger Eintrag in der Zeitmarkentabelle vorhanden ist. Wenn kein vorheriger Eintrag in der Zeitmarkentabelle vorhanden ist, weist SBMRTS (der Zeitmarkenzeiger des neuesten Zeitmarkentabelleneintrages) lauter Einsen auf. SBMRTS wird in Schritt 1506 geprüft.
Angenommen, daß kein vorheriger Eintrag in der Zeitmarkentabelle vorhanden ist, dann verzweigt das Programm zu Schritt 1508, wo ein Wort gebildet wird, in welchem das letzte Rückwärtsverknüpfungsanzeigebit (LBL) auf Eins gesetzt wird (siehe Fig. 4) und setzt die Rückwärtsverknüpfung auflauter Einsen. Das Programm verzweigt dann zu Schritt 1510, wo der Rest des Zeitmarkeneintragswortes gebildet wird. LFL wird auf Eins gesetzt und die Vorwärtsverknüpfung wird auf lauter Einsen gesetzt. Das durch die Schritte 1508 und 1510 erzeugte Wort wird dann in dem Stufenpuffer bei SBSTS2 gespeichert, welches der Ort des zweiten Wortes des momentanen (neuen) Zeitmarkentabelleneintrags ist. In Schritt 1512 wird die relative Zeitmarkentabellenadresse des neuen Eintrages bei SBMRTS als der neue Zeiger auf den neuesten Eintrag gespeichert.
In Schritt 1514 wird eine andere Prüfung ausgeführt, um zu erkennen, ob ein vorheriger Eintrag vorhanden ist und wenn dies nicht der Fall ist, wird die neue relative Eintragsadresse in dem Stufenpuffer an der Position SBLRTS gespeichert, welche den Zeiger auf den ältesten Zeitmarkentabelleneintrag enthält.
In Schritt 1518 wird die Kanalzeitmarke (CEF5) von dem Steuerspeicher geholt und in SBTS1 eingetragen, welches das erste Wort des neuen Eintrags in dem Stufenpuffer ist.
In Schritt 1520 wird eine andere Prüfung ausgeführt, um zu erkennen, ob ein vorheriger Eintrag vorhanden war, und wenn dies nicht der Fall ist, verzweigt das Programm zu Schritt 1522, wo die Kanalzeitmarke in SBGTSO eingetragen wird, die Position in dem Stufenpuffer, die für die älteste Zeitmarke TOLDEST reserviert ist.
Eine Prüfung wird wiederum in Schritt 1524 ausgeführt, um zu erkennen, ob ein vorheriger Eintrag vorhanden war, und wenn wiederum angenommen wird, daß dies nicht der Fall ist, verzweigt das Programm zu Schritt 1526, wo der neu ausgebildete Zeitmarkentabelleneintrag in SBT1 und SBT2 in der Zeitmarkentabelle in dem RAM an der absoluten Tabellenadresse gespeichert ist, die in Schritt 1500 abgeleitet wird. Die Zeitmarken-Hinzufüge/Lösch-Unterroutine kehrt dann zu der Aktualisiere-TACK/WT-Unterroutine zurück, welche sie aufgerufen hat.
Wenn ein vorheriger Eintrag in der Zeitmarkentabelle vorhanden ist, wenn die Zeitmarken-Hinzufüge/Lösch-Unterroutine aufgerufen wird, um einen neuen Eintrag hinzuzufügen, müssen die Vorwärtsverknüpfung und das LFL-Bit des vorherigen Eintrages eingestellt werden und der neue Eintrag muß mit einem Rückwärtsverknüpfungszeiger auf den vorherigen Eintrag versehen werden.
Wenn die Prüfung in Schritt 1506 anzeigt, daß ein vorheriger Eintrag in der Zeitmarkentabelle vorhanden ist, verzweigt das Programm zu Schritt 1528, wo der neueste Zeitmarkenzeiger (SBMRTS) zu der Basisadresse der Zeitmarkentabelle hinzugefügt wird, um die absolute Adresse des vorherigen Eintrags zu erhalten. Diese Adresse wird dann verwendet, um das RAM anzusprechen und den vorherigen Eintrag aus dem RAM in den Stufenpuffer an die Positionen SBTS3 und SBTS4 zu verschieben.
In Schritt 1532 wird der vorherige Eintrag von SBTS4 zum Zweck des Bildens eines Wortes zum Aktualisieren von SBTS4 geholt. Die absolute Zeitmarken-Tabellenadresse des neuen Eintrages wird als Vorwärtsverknüpfung eingefügt und das LBL- Bit wird gelöscht. Das resultierende Wort wird dann zu dem Stufenpuffer an die Position SBTS4 zurückgegeben.
Die Verknüpfungen des neuen Eintrages werden jetzt gebildet. Der neueste Zeitmarkenzeiger SBMRTS wird geholt und zur Rückwärtsverknüpfung des neuen Eintrages gemacht. In Schritt 1510 wird LFL gesetzt und alle Einsen in das Wort als Vorwärtsverknüpfung eingefügt. Das resultierende Wort wird bei SBTS2 als Wort 2 des neuen Zeitmarkentabelleneintrages gespeichert.
Es ist jetzt erforderlich, die globalen Variablen zu aktualisieren und die Zeitmarke in Wort 1 des neuen Eintrages zu laden. In Schritt 1512 wird die relative Tabellenadresse des neuen Eintrages bei SBMRTS als der neueste Zeitmarkeneintrag gespeichert. Die Prüfung bei 1514 wird wahr und daher verzweigt das Programm zu Schritt 1518, wo die Kanalzeitmarke CEF5 in den Steuerspeicher als Zeitmarke in Wort 1 von SBTS1 eingefügt wird.
Die Prüfungen in den Schritten 1520 und 1524 zeigen beide einen vorherigen Eintrag und in Schritt 1536 wird eine Routine zum Ablegen des vorherigen Eintrages in dem RAM von dem Stufenpuffer aufgerufen. In Schritt 1526 wird der neu ausgebildete Eintrag von dem Stufenpuffer zu der Zeitmarkentabelle in dem RAM übertragen. Eine Rückkehr zu der aufrufenden Routine wird dann ausgeführt.
Um einen Eintrag aus der Zeitmarkentabelle zu löschen, arbeitet die Zeitmarken- Hinzufüge/Lösch-Unterroutine wie folgt. In Schritt 1502 zeigt die Prüfung des durch die aufrufende Routine übergebenen Parameters, daß die aufrufende Routine einen Eintrag aus der Zeitmarkentabelle gelöscht haben möchte. Eine Verzweigung wird vorgenommen zu Fig. 15C, wo die relative Zeitmarkentabellenadresse des zu löschenden Eintrages in eine relative SDT-Adresse konvertiert wird, indem sie mit 2 multipliziert wird. Die relative SDT-Adresse kann wie nachfolgend beschrieben verwendet werden oder nicht. CMDQ1, das erste Wort des Cache-Befehls, wird, wie in dem Steuerspeicher gespeichert, geholt und geprüft, um zu erkennen, ob ein WEITER-SPEICHERN-Befehl ausgeführt wird. Wenn dies der Fall ist, findet eine Verzweigung statt von Schritt 1540 zu Schritt 1544. Wenn die Prüfung in Schritt 1540 anzeigt, daß der WEITER-SPEICHERN-Befehl nicht ausgeführt wird, dann ist es erforderlich, eine Prüf- und Lösch-Einzelausführungs-Unterroutine aufzurufen. Diese Routine wird aufgerufen, wann immer ein Segment sein WT-Bit in dem SDT- Eintrag zurückgesetzt hat oder ein Segment von dem SDT gelöscht ist. Wenn eine Einzelausführung in der Befehlswarteschlange des zugeordneten Laufwerks ansteht und die gleiche relative Segmentlaufwerksadresse aufweist, wird der Einzelausführungseintrag in der Befehlswarteschlange gelöscht und das Einzelausführung- Übersprungen-Flag in SBGTSK wird zurückgesetzt. Der Zweck der Prüf- und Lösch- Einzelausführungs-Unterroutine ist es, zu vermeiden, daß eine Einzelausführung eines Segments versucht wird, welches gelöscht wurde oder dessen WT-Bit in dem SDT-Eintrag nicht länger gesetzt ist. Da die Prüf- und Lösch-Einzelausführungs- Unterroutine zum Verstehen der vorliegenden Erfindung nicht relevant ist, wird sie nicht weiter beschrieben.
In Schritt 1544 wird die absolute Tabellenadresse des Löscheintrags (d.h. des zu löschenden Eintrags) geholt und die Parameter werden für eine Zweiwortübertragung eingestellt, welche den Löscheintrag von der Zeitmarkentabelle in dem RAM an die Positionen SBTS1 und SBTS2 in dem Stufenpuffer überträgt. Dann wird SBTS2 von dem Stufe npuffer geholt und das LBL-Bit wird geprüft. Für den Moment angenommen, daß es gesetzt ist, verzweigt das Programm von Schritt 1548 zu Fig. 15D, wo in Schritt 1566 SBTS2 erneut geholt wird. Das LFL-Bit wird in Schritt 1568 geprüft. Wenn es ebenfalls gesetzt ist, bedeutet das, daß der zu löschende Eintrag der einzige Eintrag in der Zeitmarkentabelle ist. Das Programm verzweigt von Schritt 1568 zu Fig. 15E. In Schritt 1588 wird SBSTS2 wiederum geholt und in Schritt 1590 werden die LBL- und LFL-Bits geprüft, um zu erkennen, ob sie beide Eins sind. Unter den angenommenen Umständen sind sie dies und das Programm verzweigt zu Schritt 1591, wo SBMRTS, SBLRTS und SBGTSO auflauter Einsen gesetzt werden.
In Schritt 1592 wird eine Null in SBTS1 eingetragen, um dadurch eine Null- Zeitmarke in dem gelöschten Eintrag vorzusehen. Ein Wort wird gebildet und in SBTS2 eingefügt, wobei dieses Wort lauter Einsen in den Vorwärts- und Rückwärts- Verknüpfungen bei zurückgesetztem LFL und LBL aufweist. Das Programm kehrt dann zu Fig. 15B zurück, wo in Schritt 1526 der neue Eintrag, d.h. der gelöschte Eintrag von SBTS1 und SBTS2 indem Stufenpuffer zu seiner vorgesehenen Position in der in dem RAM enthaltenen Zeitmarkentabelle übertragen wird. Die Unterroutine kehrt dann zu der aufrufenden Routine zurück.
Wenn der gelöschte Eintrag nicht der einzige Eintrag in der Zeitmarkentabelle ist, ist eine Einstellung entweder in der Vorwärtsverknüpfungsadresse des vorherigen Eintrags in der Kette, der Rückwärtsverknüpfung des nächsten Eintrags in der Kette oder in der Vorwärtsverknüpfung des vorigen Eintrags und der Rückwärtsverknüpfung des nächsten Eintrages vorzunehmen, abhängig davon, ob der zu löschende Eintrag der neueste Eintrag, der älteste Eintrag oder ein Eintrag zwischen dem neuesten Eintrag und dem ältesten Eintrag ist.
Angenommen, der zu löschende Eintrag ist der älteste Eintrag. Wenn SBTS2 geholt wird und LBL in Schritt 1548 geprüft wird, wird es gesetzt gefunden. Das Programm verzweigt zu Fig. 15D, holt in Schritt 1566 erneut SBTS2 und prüft LFL in Schritt 1568. Wenn der Eintrag nicht der neueste Eintrag ist, verzweigt das Programm von Schritt 1568 zu Schritt 1570. Die Vorwärtsverknüpfung des gelöschten Eintrages wird zu der Basisadresse der Zeitmarkentabelle addiert, um die RAM-Adresse des nächsten Eintrages zu erhalten. Der nächste Zwei-Wort-Eintrag wird aus den RAM zu den Positionen SBTS3 und SBTS4 in dem Stufenpuffer verschoben.
In Schritt 1574 wird SBTS2 geholt und die Vorwärts- und Rückwärtsverknüpfungen des gelöschten Eintrags gesichert, LBL wird geprüft, um eine Anzeige zu setzen und unter den angenommenen Bedingungen wird diese Anzeige gesetzt. In Schritt 1576 wird das zweite Wort des nächsten Zeitmarkentabelleneintrages geholt. In Schritt 1578 wird die in Schritt 1574 gesetzte Anzeige geprüft und da sie unter den angenommenen Bedingungen gesetzt wurde, verzweigt das Programm zu Schritt 1579, wo die Rückwärtsverknüpfung auflauter Einsen gesetzt wird und LBL auf 1 gesetzt wird. Das in den Schritten 1576 und 1579 gebildete Wort wird dann als das zweite Wort des nächsten Zeitmarkentabelleneintrags gespeichert.
Wenn der gelöschte Eintrag der älteste Eintrag in der Zeitmarkentabelle ist, werden somit die Rückwärtsverknüpfung und das LBL-Bit des nächsten Eintrages auf Einsen gesetzt. Die Vorwärtsverknüpfung und LFL des nächsten Eintrages bleiben unverändert.
Von dem Schritt 1580 verzweigt das Programm zu Fig. 15E, wo es die globalen Variablen Einstellt. In Schritt 1582 wird eine Prüfung ausgeführt, um zu erkennen, ob die Anzeige in Schritt 1574 gesetzt wurde. Unter den angenommenen Bedingungen ist die Anzeige gesetzt und das Programm verzweigt zu Schritt 1583, wo die Vorwärtsverknüpfung des Löscheintrages in den Stufenpuffer bei SBLRTS eingetragen wird. Da die Vorwärtsverknüpfung die Adresse des nächsten Eintrages angibt, wird die Adresse des nächsten Eintrages die Adresse des ältesten Zeitmarkentabelleneintrages.
In Schritt 1584 wird die Zeitmarke des nächsten Eintrages als älteste Zeitmarke in der Zeitmarkentabelle von SBTS3 zu der Position SBGTSO in dem Stufenpuffer übertragen. In Schritt 1586 werden die den nächsten Eintrag umfassenden zwei Worte von dem Stufenpuffer zu der Zeitmarkentabelle in dem RAM übertragen.
In Schritt 1588 wird das zweite Wort des gelöschten Eintrages geholt und geprüft, um zu erkennen, ob LBL und LFL beide 1 sind. Unter den angenommenen Bedingungen sind sie es nicht, so daß das Programm zu Schritt 1592 verzweigt, wo es die Zeitmarke auf Null setzt, FL und BL auflauter Einsen setzt und LFL und LBL für den gelöschten Eintrag zunicksetzt. Dann kehrt das Programm zu Fig. 15B, Schritt 1526 zurück, wo der gelöschte Eintrag von dem Stufenpuffer zu der Zeitmarkentabelle in dem RAM übertragen wird. Das Programm kehrt dann zu der aufgerufenen Routine zurück.
Es wird jetzt angenommen, daß die Zeitmarken-Hinzufüge/Lösch-Unterroutine aufgerufen wird, um einen Eintrag zu löschen, welcher der neueste Eintrag in der Zeitmarkentabelle ist. In Fig. 15A werden die Schritte 1500 und 1502 ausgeführt und eine Verzweigung zu Fig. 15C wird vorgenommen, wo die bereits beschriebenen Schritte bis zu Schritt 1548 ausgeführt werden. An diesem Punkt erkennt die Prüfung, daß das LBL-Bit nicht gesetzt ist und das Programm verzweigt zu Schritt 1550, wo die Rückwärtsverknüpfung des Löscheintrages mit der Zeitmarkentabellenbasisadresse kombiniert wird, um die Tabellenadresse des vorherigen Eintrags zu erhalten. Die so abgeleitete Adresse wird in Schritt 1552 verwendet, um den vorherigen Eintrag von der Zeitmarkentabelle zu den Positionen SBTS3 und SBTS4 in dem Stufenpuffer zu verschieben.
In Schritt 1554 wird Wort 2 des gelöschten Eintrages geholt und die Vorwärtsverknüpfungs- und Rückwärtsverknüpfungs-Adressen werden gesichert. Eine Anzeige wird dann gesetzt, wenn LFL des Löscheintrages eine 1 ist. Unter den angenommenen Bedingungen ist dies wahr.
In Schritt 1556 wird das zweite Wort des vorherigen Eintrages zum Zweck des Bildens eines neuen Wortes für diesen Eintrag geholt. In Schritt 1558 wird eine Prüfung ausgeführt, um zu erkennen, ob die Anzeige in Schritt 1554 gesetzt wurde. Da dies der Fall war, wird die Vorwärtsverknüpfung des gebildeten Wortes auf lauter Einsen gesetzt und das LFL-Bit wird gesetzt. Das resultierende Wort wird in SBTS4 gespeichert. Das reine Ergebnis der Schritte 1556 und 1559 ist, daß die Vorwärtsverknüpfung des vorherigen Eintrages auflauter Einsen gesetzt ist und sein LFL-Bit gesetzt ist, um anzuzeigen, daß der Eintrag jetzt der letzte oder neueste Eintrag in der Zeitmarkenkette ist.
Von Schritt 1560 verzweigt das Programm zu Fig. 15D, wo eine andere Prüfung in Schritt 1562 ausgeführt wird, um zu erkennen, ob die Anzeige in Schritt 1554 gesetzt wurde. Unter den angenommenen Bedingungen war dies der Fall und das Programm verzweigt zu Schritt 1563, wo die Rückwärtsverknüpfung des Löscheintrages zu dem Stufenpuffer gesendet und bei SBMRTS gespeichert wird. Da die Rückwärtsverknüpfung des Löscheintrages die Adresse des vorherigen Eintrages ist, wird der vorherige Eintrag der neueste Eintrag in der Zeitmarkentabel le.
In Schritt 1564 wird der aktualisierte vorherige Eintrag von dem Stufenpuffer zu seiner Position in der Zeitmarkentabelle in dem RAM übertragen.
In Schritt 1566 wird der Löscheintrag geholt und sein LFL-Bit geprüft. Da angenommen wird, daß der Löscheintrag der letzte Eintrag in der Tabelle ist, verzweigt das Programm zu Fig. 15E, wo der gelöschte Eintrag wiederum in Schritt 1588 geholt und in Schritt 1590 geprüft wird, um zu erkennen, ob LBL und LFL gesetzt sind. Da angenommen wird, daß der gelöschte Eintrag nicht der einzige Eintrag in der Zeitmarkentabelle war, verzweigt das Programm zu Schritt 1592, wo die Zeitmarke in Wort 1 des Löscheintrages auf Null gesetzt wird, die Vorwärtsverknüpfung und Rückwärtsverknüpfung in Wort 2 beide auflauter Einsen gesetzt werden und die LFL- und LBL-Bits in Wort 2 auf Null gesetzt werden. Das Programm verzweigt dann zu Schritt 1526 in Fig. 15B, wo der aktualisierte Löscheintrag von dem Stufenpuffer zu seiner Position in der Zeitmarkentabelle in dem RAM übertragen wird.
Jetzt wird angenommen, daß der zu löschende Eintrag weder der erste noch der letzte Eintrag in einer Zeitmarkentabelle ist. In diesem Fall ist es erforderlich, die Vorwärtsverknüpfung des vorherigen Eintrages zum Zeigen auf den nächsten Eintrag einzustellen und die Rückwärtsverknüpfung des nächsten Eintrages zum Zeigen auf den vorherigen Eintrag einzustellen, um dadurch den gelöschten Eintrag aus der Kette zu entfernen. In Fig. 15A verzweigt das Programm zu dem Entscheidungspunkt 1502, verzweigt zu Fig. 15C und führt die Schritte 1538 bis 1552 in der oben beschriebenen Weise für die Bedingung aus, in welcher der Löscheintrag der neueste, aber nicht der einzige Eintrag in der Tabelle ist.
In Schritt 1554 wird der Löscheintrag geholt und die Rückwärts- und Vorwärts- Verknüpfungen werden gesichert. Da LFL nicht gleich list, ist die Anzeige nicht gesetzt. In Schritt 1556 wird Wort 2 des vorherigen Eintrages zum Bilden eines neuen Wortes 2 für den vorherigen Eintrag geholt. Die Vorwärtsverknüpfung des Löscheintrages wird die Vorwärtsverknüpfung des vorherigen Eintrages. Die Rückwärtsverknüpfung des vorherigen Eintrages und LBL bleiben unverändert. In Schritt 1558 wird die Prüfung zeigen, daß die Anzeige nicht gesetzt ist, und so verzweigt das Programm zu Schritt 1560, wo das in Schritt 1556 erzeugte Wort in SBTS4 als der aktualisierte vorherige Eintrag geladen wird. Das LFL-Bit wird in dem aktualisierten vorherigen Eintrag Null.
Dann verzweigt das Programm zu Fig. 15D, wo die Prüfung in Schritt 1562 unter den angenommenen Bedingungen zeigt, daß die Anzeige nicht eingestellt ist. Daher wird LBM RT nicht aktualisiert und das Programm verzweigt zu Schritt 1564, wo der aktualisierte vorherige Eintrag von dem Stufenpuffer zu der Zeitmarkentabelle in dem RAM übertragen wird.
In Schritt 1566 wird der Löscheintrag geholt und das LFL-Bit geprüft. Unter den angenommenen Bedingungen ist LFL nicht gesetzt, und das Programm verzweigt zu Schritt 1570, wo die Vorwärtsverknüpfung des Löscheintrages zu der Basisadresse der Zeitmarkentabelle addiert wird, um die absolute Tabellenadresse des nächsten Eintrages zu erhalten. In Schritt 1572 werden die den nächsten Eintrag umfassenden zwei Worte von dem RAM zu dem Stufenpuffer an die Positionen SBTS3 und SBTS4 übertragen.
In Schritt 1574 wird das zweite Wort des gelöschten Eintrages geholt, und die Vorwärts- und Rückwärts-Verknüpfungen werden gesichert. Unter den angenommenen Bedingungen ist die Anzeige nicht gesetzt, um zu zeigen, daß LBL gleich 1 ist. In Schritt 1576 wird das zweite Wort des nächsten Eintrages geholt. Die Rückwärtsverknüpfung des Löscheintrages wird die Rückwärtsverknüpfung des nächsten Eintrages. Die Vorwärtsverknüpfung des nächsten Eintrages bleibt unverändert.
In Schritt 1578 zeigt die Prüfung, daß die Anzeige in Schritt 1574 nicht gesetzt wurde und das Programm verzweigt von Schritt 1578 zu Schritt 1580, wo das in Schritt 1576 gebildete Wort bei SBTS4 gespeichert wird.
Als ein Ergebnis der Operationen in Schritt 1576 wird ein Wort zum Aktualisieren des zweiten Wortes den nächsten Eintrages gebildet, wobei das gebildete Wort die Vorwärtsverknüpfung des nächsten Eintrages und die Rückwärtsverknüpfung des Löscheintrages aufweist.
Von Schritt 1580 verzweigt das Programm zu Fig. 15E, wo die Prüfung in Schritt 1582 jetzt zeigt, daß die Anzeige in Schritt 1574 nicht gesetzt wurde. Somit werden SBLRTS und SBGTSQ nicht aktualisiert und das Programm verzweigt zu Schritt 1586.
In Schritt 1586 wird der aktualisierte nächste Eintrag von dem Stufenpuffer zu seiner Zeitmarkentabellenposition in dem RAM zurückgegeben.
In Schritt 1588 wird der gelöschte Eintrag geholt und LBL und LFL werden geprüft, um zu erkennen, ob sie beide Einsen sind. Unter den angenommenen Bedingungen sind sie dies nicht und das Programm verzweigt zu Schritt 1592, wo die Zeitmarke in Wort 1 des Löscheintrages auf Null gesetzt wird, die Vorwärts- und Rückwärts- Verknüpfungen in Wort 2 des Eintrages auflauter Einsen gesetzt und die LBL- und LFL-Bits zurückgesetzt werden. Das Programm verzweigt dann zu Fig. 15B, wo Schritt 1526 ausgeführt wird, um den aktualisierten Löscheintrag von dem Stufenpuffer zu der Zeitmarkentabelle in dem RAM zu übertragen. Das Programm kehrt dann zu der aufrufenden Routine zurück.

EINZELAUSFÜHRUNGSPRIORITÄT BESTIMMEN

Die Fig. 16A und 16B umfassen ein Flußdiagramm, das die Operationen darstellt, die für die Bestimmung der Einzelausführungspriorität ausgeführt werden. Gemäß dem erfindungsgemäßen Grundgedanken wird die Einzelausführungspriorität anhand zweier unterschiedlicher Kriterien berechnet, die Prioritäten der zwei Kriterien werden verglichen und die höchste Priorität wird als Einzelausführungspriorität verwendet.
Gemäß einem Kriterium wird die Priorität berechnet, wie in Tabelle 1 dargestellt. Gemäß diesem Kriterium basiert die Priorität darauf, wie lange es seit dem ersten Schreiben in das älteste beschriebene Segment im Cache gedauert hat. In Tabelle I stellt TDELTA die Differenz zwischen der momentanen Zeitmarke und der ältesten Zeitmarke dar. AGEOLD ist ein System parameter, welcher während der Systemparam etriesierung geladen wird und die Länge der Zeit darstellt, die ein beschriebenes Segment in dem Cache bleiben kann, bevor es als alt betrachtet wird. Wenn TDELTA kleiner als zweimal AGEOLD ist, dann ist die gemäß dem ersten Kriterium zugeordnete Priorität 7. Wenn TDELTA zwischen zwei- und viermal AGEOLD ist, dann wird eine Priorität von 5 zugeordnet. Wenn TDELTA zwischen vier- und achtmal AGEOLD ist, dann wird eine Priorität von 3 zugeordnet und wenn TDELTA gleich oder größer als achtmal AGEOLD ist, dann wird 1 als Priorität zugeordnet. 1 stellt die höchste Priorität dar, während 7 die niedrigste Priorität darstellt. Tabelle 1 Tabelle 2
In Fig. 16A bezeichnen die Bezugszeichen 1602-1618 die ausgeführten Schritte, um die Priorität basierend auf der Zeit (Alter) seit dem ersten Schreiben des ältesten beschriebenen Segmentes zu berechnen. Wenn die Unterroutine aufgerufen wird, wird ein durch die aufrufende Routine bereitgestellter Eingangsparameter in GA gesichert. Wenn dieser Parameter den Wert 8000 aufweist, bedeutet dies, daß die Einzelausführungs-Prioritäts-Bestimmungs-Unterroutine ebenfalls die Priorität des Einzelausführungsbefehls in der Befehlswarteschlange nach Berechnen der Priorität aktualisieren soll. Wenn er den Wert 0000 aufweist, dann wird die Einzelausführungspriorität berechnet, aber der Befehlswarteschlangeneintrag wird nicht aktualisiert.
AGEOLD wird von seiner Position SBGAGE in dem Stufenpuffer nach GF verschoben. Als nächstes wird die mit dem letzten Lese- oder Schreibbefehl von einem Host-Prozessor (TCURRENT) bereitgestellte momentane Zeitmarke von SBGTSC geholt und die Zeitmarke des ältesten beschriebenen Segments (TOLDEST) wird von SBGTSO geholt. TOLDEST wird dann von TCURRENT subtrahiert, um TDELTA zu erhalten, ein Wert, der das Alter seit dem ersten Schreiben des ältesten beschriebenen Segmentes darstellt. TDELTA wird in SB an der Position SBGTLD gespeichert.
Sobald TDELTA berechnet wurde, wird der Wert 7, der die niedrigste mögliche Priorität darstellt, in GA eingetragen. AGEOLD, momentan in GF gehalten, wird mit 2 multipliziert und das Ergebnis zu GF zurückgegeben. In Schritt 1612 wird eine Prüfung ausgeführt, um zu erkennen, ob TDELTA gleich oder größer als GF ist. Wenn dies nicht der Fall ist, ist TDELTA kleiner als 2 X AGEOLD und die zugeordnete Priorität soll 7 sein. Der Wert 7 wurde in Schritt 1608 in GA eingegeben und in Schritt 1618 wird dieser Wert an einer geeigneten Position in dem Steuerspeicher gesichert.
In Schritt 1612 wird, wenn TDELTA gleich oder größer als GF ist, der Wert 2 von GA subtrahiert und das Ergebnis an GA als ein neuer möglicher Prioritätswert zurückgegeben. Dieser Wert wird geprüft, um zu erkennen, ob er gleich 1 ist und wenn dies nicht der Fall ist, verzweigt das Programm zurück zu Schritt 1610, wo der Inhalt von GF wiederum mit 2 multipliziert und GF zurückgegeben wird. Dies plaziert einen Wert von 4 X AGEOLD in GF. In Schritt 1612 wird ein anderer Test ausgeführt, diesmal, um zu erkennen, ob TDELTA gleich oder größer als 4 X AGE- OLD ist. Wenn dies nicht der Fall ist, springt das Programm zu Schritt 1618 und der Wert in GA, nun 5, wird als die Priorität in dem Steuerspeicher gespeichert.
Die die Schritte 1610, 1612, 1614 und 1616 umfassende Schleife kann bis zu dreimal wiederholt werden mit dem Wert in GA, der bei jeder Schleifenausführung um 2 verringert wird. Somit wird, wenn im letzten Lauf durch die Schleife die Prüfung in Schritt 1612 immer noch findet, daß TDELTA gleich oder größer als GF ist, der Wert 2 wiederum von GA subrahiert, was den Prioritätswert darin auf 1 verringert. Diese Bedingung wird dann in Schritt 1616 erfaßt und das Programm verzweigt von Schritt 1616 zu Schritt 1618, wo der Prioritätswert von 1 an der geeigneten Position in dem Steuerspeicher gesichert wird. Dies beendet die Berechnung eines Prioritätswertes basierend auf dem Alter seit dem ersten Schreiben des ältesten beschriebenen Segments im Cache.
Das zweite Kriterium zur Qualitätszuordnung basiert auf der Anzahl der beschriebenen Segmente im Cache. Wie in Tabelle 2 gezeigt, wird eine Priorität von 7 zugeordnet, wenn die Anzahl der beschriebenen Segmente kleiner als 25% der Gesamtanzahl der Segmente im Cache ist. Wenn zwischen 25 und 50% der Segmente im Cache beschrieben wurden, beträgt der zugeordnete Prioritätswert 5. Wenn zwischen 50 und 75% der Segmente beschrieben wurden, wird der Priorität ein Wert von 3 zugeordnet und wenn über 75% der Segmente beschrieben wurden, wird eine Priorität von 1 zugeordnet.
Die in den Fig. 16A und 16B dargestellten Schritte 1620-1636 berechnen eine Priorität basierend auf dem zweiten Kriterium. In Schritt 1620 wird SBGCAP geholt und durch 2 dividiert. SBGCAP ist ein fester Wert, der die maximal mögliche Anzahl von Segmenten in dem Cache-Speicher darstellt. Das durch Dividieren von SBGCAP durch 2 erhaltene Resultat wird in GE gespeichert. Zusätzlich wird dieser Wert durch 2 dividiert, um einen Wert zu erhalten, welcher in GB gespeichert wird, wobei dieser Wert 25% der Gesamtzahl der Segmente in dem Cache-Speicher darstellt. GB und GE werden addiert, um einen Wert zu erhalten, der 75% der Cache- Segmente darstellt und dieser Wert wird in GC gespeichert.
In Schritt 1622 wird SBGWTS von dem Stufenpuffer geholt und in GF gespeichert. SBGWTS stellt einen Zählwert der Anzahl der Segmente in dem Cache-Speicher dar, die nicht zu einem Plattenlaufwerk zurückgegeben wurden, seit sie das letzternal beschrieben wurden. In Schritt 1624 wird SBGWTS mit dem 75%-Wert verglichen, der in Schritt 1620 erhalten wurde, und wenn SBGWTS größer als der Wert ist, wird 1 in GT als ein Prioritätswert geladen.
Wenn SBGWTS nicht größer als der 75%-Wert ist, dann wird er in Schritt 1628 mit dem in Schritt 1620 erhaltenen 50%-Wert verglichen. Wenn SBGWTS größer als der 50%-Wert ist, dann wird der Wert 3 in GT als ein Prioritätswert eingetragen. Schließlich, wenn SBGWTS nicht größer als der 50%-Wert ist, wird er verglichen mit dem in Schritt 1620 erhaltenen 25%-Wert. Wenn SBGWTS größer als der 25%- Wert ist, dann wird der Wert 5 in GT eingetragen. Wenn die Prüfung in Schritt 1632 zeigt, daß SBGWTS nicht größer als der 25%-Wert ist, dann wird eine 7 in GD als der Prioritätswert eingetragen.
An diesem Punkt hat die Unterroutine ihre Berechnung des Prioritätswertes basierend auf dem zweiten Kriterium beendet und dieser Wert ist in GT enthalten, wobei er in einem der Schritte 1626, 1630, 1634 oder 1636 darin plaziert wurde.
In Schritt 1638 vergleicht die Unterroutine die in Schritt 1618 gesicherte AGEOLD- Priorität mit der in einem der Schritt 1626, 1630, 1634 oder 1636 in GD eingetragenen Beschrieben-Priorität. Wenn die AGEOLD-Priorität größer als die Beschrieben-Priorität ist, verzweigt das Programm von Schritt 1638 zu Schritt 1640, wo die AGEOLD-Priorität bei SBTPRI als die Einzelausführungspriorität gespeichert wird. Wenn andererseits die Prüfung in Schritt 1638 anzeigt, daß die Beschrieben-Priorität höher als die AGEOLD-Priorität ist, dann wird in Schritt 1642 die Beschrieben-Priorität als die Einzelausführungspriorität zu SBTPRI gesendet.
Als nächstes wird in Schritt 1644 GA geprüft, und wenn der erste Befehl in der Befehlswarteschlange (SBCMQ1) nicht zu aktualisieren ist, kehrt das Programm zu dem Aufrufer zurück.
Wenn die Prüfung in Schritt 1644 anzeigt, daß SBCMQ1 aktualisiert werden soll, werden SBTPR1 und SBCMQ1 von dem Stufenpuffer geholt. In Schritt 1648 wird das Voll-Bit (Bit 4) von SBCMQ1 geprüft, um zu erkennen, ob der erste Befehlswarteschlangeneintrag voll ist. Wenn dies nicht der Fall ist, wird die neue Priorität nicht eingefügt und das Programm kehrt zu der aufrufenden Routine zurück. Wenn die Prüfung in Schritt 1648 anzeigt, daß das FL-Bit des ersten Eintrags in der Befehlswarteschlange gesetzt ist, wird die neue Priorität SBTPRI eingefügt und die so modifizierte SBCMQI wird zu dem Stufenpuffer zurückgegeben. Das Programm kehrt dann zu der aufrufenden Routine zurück.

LESEHILFSPROGRAMM

Wenn ein Cache-Speicherfehler auftritt, ist es erwünscht, daß ein Hostprozessor in der Lage ist, alle Daten, welche verlorengegangen sein können, wiederherzustellen und in der Lage ist, dies in der geringstmöglichen Zeit zu tun. Was der Hostprozessor in diesem Fall im wesentlichen wissen muß, ist (1), welche der in dem Cache-Speicher vorhandenen Segmente durch den Host beschrieben aber im Fehlerzeitpunkt noch nicht auf die Platte geschrieben wurden und (2), wann das älteste der beschriebenen Segmente zuerst beschrieben wurde. Wie sich aus der vorstehenden Beschreibung ergibt, ergibt das Bereitstellen einer Zeitmarke in jedem Eintrag der Zeitmarkentabelle einen Hinweis darauf, wann jedes Segment zuerst beschrieben wurde, wenn es noch nicht zurückgegeben wurde. Weiterhin unterstützt aus dieser Tabelle die SCU kontinuierlich den Parameter TOLDEST und aktualisiert diesen Parameter jedesmal, wenn ein Segment beschrieben oder ein beschriebenes Segment zu einer Platte zurückgegeben wird, in Übereinstimmung mit den in der Zeitmarkentabelle unterstützten Zeitmarken.
Da ein Cache-Speicherfehler den Inhalt der Zeitmarkentabelle zerstören kann, ermittelt ein Host-Prozessor durch Voraussehen der Möglichkeit eines solchen Fehlers periodisch TOLDEST und sichert ihn mit anderen Datei-Wiederherstellungssynchronisationsinformationen z.B. in einem System-Revisions-Anhang. Im Fall eines Cache-Speicherfehlers kann der Host die letzte ermittelte TOLDEST verwenden, um den Fehler zu beseitigen.
Der Host-Prozessor gibt periodisch einen LESE-HILFSPROGRAMM-Befehl an die Speichersteuerungseinheit 100 aus und die Speichersteuerungseinheit ermittelt TOLDEST aus dem RAM und sendet es zu dem Host-Prozessor. Jedesmal, wenn TOLDEST zu dem Host-Prozessor gesendet wird, ersetzt es den als Reaktion auf den letzten vorausgehenden LESE-HILFSPROGRAMM-Befehl gelesenen TOLDEST- Wert. Somit kann ein Host-Prozessor durch Einstreuen von LESE-HILFSPRO- GRAMM-Befehlen unter die anderen an die Speichersteuereinheit gesendeten Befehle stets eine ziemlich genaue Anzeige haben, wie weit zurück er in der Zeit (d.h. in seinem Programm) in seiner Wiederherstellungsprozedur gehen muß, um die durch den Cache-Speicherfehler verlorenen Daten wiederzugewinnen.
Die als Reaktion auf den Lese-Hilfsprogramm-Befehl von dem Host ausgeführte Routine ist in Fig. 17 dargestellt. Tatsächlich kann der LESE-HILFSPROGRAMM- Befehl verschiedene Parameter aus dem Untersystem in Übereinstimmung mit einem Unterbefehlsfeld lesen, wie vollständig in der Anmeldung mit der Seriennummer 207,152 erläutert. Lediglich der Teil der Lese-Hilfsprogramm-Routine ist gezeigt, welcher ausgeführt wird, wenn der Lese-Hilfsprogramm-Befehl ein Unterbefehlsfeld aufweist, welches festlegt, daß der älteste Zeitmarkenwert gelesen werden soll.
Wenn der Lese-Hilfsprogramm-Befehl durch den Host ausgegeben und von der SCU 100 angenommen wird, wird er in den Steuerspeicher 116 geladen und dekodiert, um herauszufinden, welcher Unterbefehl genau auszuführen ist. Wenn festgelegt ist, daß der Unterbefehl bestimmt, daß der älteste Zeitmarkenwert zu lesen ist, wird die Basisadresse der SDT in dem Cache-Speicher 106 eingestellt und ein Aufruf wird in Schritt 1702 ausgeführt, um die SDT zu selektieren. Dies hält die SDT in dem Cache-Speicher für die Verwendung der SCU 100 bereit, welche die Anforderung ausgibt. In Schritt 1704 werden die Parameter als Vorbereitung zum Aufrufen einer Lese-RAM-Unterroutine eingestellt. Die Parameter werden so gewählt, daß nur ein Wort übertragen wird, wobei dieses Wort von der Position CDGTSO in dem RAM zu der Adresse 0 im Stufenpuffer übertragen wird. CDGTSO ist die Position von TOLDEST im RAM und ist die Position, an welche SBGTSO von dem Stufenpuffer übertragen wird, wenn globale Variablen an das RAM zurückgegeben werden.
Nachdem TOLDEST in den Stufenpuffer gebracht ist, wird es geholt und geprüft, um zu erkennen, ob es Null ist. Wenn dies nicht der Fall ist, wird in Schritt 1710 eine Puffer-zu-Host-Übertragung ausgelöst, um die Zeitmarke von der Positon Null in dem Stufenpuffer über den Bus BD durch die Kanal-Schnittstellenschaltung 108 zu dem anfordernden Host 102 zu übertragen.
Wenn die Prüfung in Schritt 1708 anzeigt, daß die Zeitmarke gleich Null ist, dann wird der Zeitmarkenwert in dem Stufenpuffer auflauter 1 gesetzt, bevor die Pufferzu-Host-Übertragung ausgelöst wird.
Nachdem die Puffer-zu-Host-Übertragung beendet ist, wird in Schritt 1714 eine Unterroutine zum Freigeben der SDT aufgerufen. Die SDT wird deselektiert und die Statusmaßnahme 06 wird in dem Steuerspeicher 116 in einer Position STSXSA gespeichert. Die Lese-Hilfsprogramm-Routine verzweigt dann zu einer Cache-Status- Routine, welche ein Statuswort bildet und es zurück zu dem Host sendet. Die SCU kehrt zu der Leerlaufschleife zurück, nachdem das Statuswort zu dem Host gesendet wurde.

UNTERSYSTEM-LEERLAUF BESTIMMEN

In Fig. 11D wird in Schritt 1176 eine Prüfung ausgeführt, um zu erkennen, ob das Untersystem im Leerlauf ist. Das Untersystem ist im Leerlaufzustand, wenn für ein vorbestimmtes Intervall, z.B. 200 ms, kein Befehl von einem Host-Prozessor empfangen wurde. Diese Bedingung wird durch einen Einzelausführungs-Timer erfaßt, welcher wie folgt arbeitet. Der Timer ist lediglich eine bestimmte Position TRKTMR in dem Steuerspeicher 116. Jedesmal, wenn die Speichersteuerungseinheit 100 eine Leerlaufschleife ausführt, wird TRKTMR geholt und inkrementiert. Das Inkrementieren kann z.B. als erster Schritt (nicht dargestellt) der in Fig. 5 der vorliegenden Erfindung dargestellten Leerlaufroutine stattfinden. Jedesmal, wenn ein Befehl (EF) durch den Host-Prozessor an die Speichersteuerungseinheit 100 gesendet wird und durch die Speichersteuerungseinheit erkannt wird, wird TRKTMR geholt und zurückgesetzt. Diese Operation kann als letzter Schritt der in der Anmeldung mit der Seriennummer 207,152 in Fig. 68 illustrierten Initialselektionsroutine stattfinden. Die Untersystemleerlaufprüfung in Schritt 1176 der vorliegenden Erfindung betrifft lediglich das Prüfen der hohen Stellen von TRKTMR. Wenn diese gesetzt sind, weist der Timer einen Einzelausführungsbefehl auf, der sich mit anderen Befehlen, wie den als Ergebnis eines Hostprozessor-Lese- oder Schreib-Befehls in der gleichen Warteschlange plazieren um das Recht zur Ausführung durch die Speichersteuerungseinheit bewirbt. Dies findet während der Ausführung der Befehlswarteschlangeneintragsfinde-Unterroutine (Schritt 604) nach der Befehlswarteschlangenprüfunterroutine (Schritt 502) statt, wobei erstere bestimmt, welche einem nicht belegten Laufwerk zugeordnete Befehlswarteschlange einen Befehl in ihrer Warteschlange aufweist.
Einzelausführungsbefehlen wird eine Priorität durch die Einzelausführungsprioritätsbestimmungsunterroutine zugeordnet, welche durch die Befehlswarteschlangeneintragsfinde-Unterroutine in Schritt 604 aufgerufen wird. Die Priorität eines Einzelausführungsbefehls wird bestimmt durch Berechnen einer ersten Priorität gemäß dem Alter seit dem ersten Schreiben des ältesten beschriebenen Segmentes in dem Cache-Speicher und Berechnen einer zweiten Priorität basierend auf dem Prozentsatz der Segmente im Cache-Speicher, die beschrieben sind.
Die älteste Zeitmarke in der Zeitmarkentabelle wird in dem Cache-Speicher gesichert und aktualisiert als beschriebenes Segment, das einzeln zu dem Plattenlaufwerk übertragen wird. Der Host-Prozessor liest periodisch die älteste Zeitmarke, welche durch den Host-Prozessor gesichert ist, bevorzugt auf einem permanenten Speichermedium wie einem Magnetband oder einer Platte, so daß sie bei einem Spannungsverlust, welcher auch einen Cache-Fehler auslöst, nicht verlorengeht. Im Fall eines Cache-Fehlers kann der Host-Prozessor den zuletzt gelesenen ältesten Zeitmarkenwert verwenden, um zu bestimmen, welche Wiederherstellungsverfahren erforderlich sind.

Claims

1. In einem Cache/Plattenuntersystem, das auf Befehle von einem Host-Prozessor (102) reagiert, umfaßt die Anordnung:

a) eine Plattenlaufwerkseinrichtung (104) zum Speichern von Daten, wobei die Plattenlaufwerkseinrichtung (104) wenigstens eine Platte und einen damit zusammenwirkenden radial positionierbaren Wandler zum Zugreifen auf den Plattenplatz beinhaltet;

b) einen Cache-Speicher (106); und

c) eine Steuerungseinrichtung (100) zum Steuern der Übertragung von Daten zwischen dem Host-Prozessor (102), dem Cache-Speicher (106) und der Plattenlaufwerkseinrichtung (104);

d) wobei die Steuerungseinrichtung (100)

- veranlaßt, daß auf der Platte (104) gespeicherte Daten, welche wahrscheinlich beim Ausführen von Host-Prozessorbefehlen verwendet werden, in dem Cache-Speicher (106) gespeichert werden,

- einen Host-Prozessorbefehl, der in dem Cache-Speicher (106) gespeicherte Daten verwendet, ohne auf den Zugriff auf die Plattenlaufwerkseinrichtung (104) warten zu müssen, ausführt,

- den Wandler zum Zugriff auf einen bestimmten Plattenplatz auf der Plattenlaufwerkseinrichtung (104) als Reaktion auf einen Befehl, der einen Plattenzugriff erfordert, steuert, und

- eine Befehlswarteschlange (128) beinhaltet, um darin mehrere Host- Prozessorbefehle zu speichern, die einen Plattenzugriff erfordern, aber noch nicht ausgeführt werden, wobei jeder dieser Befehle mit einem bestimmten Plattenplatz auf der Plattenlaufwerkseinrichtung korrespondiert;

e) wobei die Steuerungseinrichtung (100), bevor eine Suche ausgelöst wird, die Positionsbeziehungen zwischen den Warteschlangenanforderungen prüft und einen Planungsalgorithmus zum Bedienen des Anforderungssatzes anwendet, wobei die Anforderungen ohne Rücksicht darauf, in welcher Richtung der Zugriffsarrn sich bewegen muß, bedient werden;

dadurch gekennzeichnet, daß

f) die Steuerungseinrichtung (100)

- die gegenwärtige Zylinder- und Winkelposition bestimmt,

- eine anstehende Anforderung in der Befehlswarteschlange durch Berechnen der Suchzeit S und der Rotationswartezeit L zum Bestimmen der Gesamtpositionierungszeit S + L, die für die anstehende Anforderung erforderlich ist, unter Berücksichtigung der gegenwärtigen Zylinder- und Winkelposition, testet, wodurch bestimmt ist, welche der anstehenden Anforderungen von den bisher getesteten Anforderungen die schnellste ist, und

- nach jedem Test die Adresse und die entsprechende Gesamtzeit der schnellsten der bis dahin getesteten anstehenden Anforderungen speichert und den Test fortsetzt, bis das Ende der Befehlswarteschlange erreicht ist, wonach die beste anstehende Anforderung zum Zugreifen auf den Plattenplatz selektiert ist.

2. System nach Anspruch 1, bei welchem der Cache-Speicher (106) eine Datenanforderungsübertragung zu der Plattenlaufwerkseinrichtung (104) beinhaltet und wobei die Steuerungseinrichtung (100) einen Befehl zum Leiten der Übertragung der Daten zu ihrem bestimmten Plattenplatz auf der Plattenlaufwerkseinrichtung (104) bildet und diesen gebildeten Befehl in der Befehlswarteschlange (128) speichert.

3. System nach Anspruch 1 oder 2, bei welchem die in der Befehlswarteschlange (128) gespeicherten Befehle eine zugeordnete Priorität aufweisen und wobei die Steuerungseinrichtung (100) aus mehreren in der Befehlswarteschlange (128) gespeicherten Befehlen abhängig von der Befehlspriorität einen nächsten auszuführenden Befehl selektiert.

4. System nach Anspruch 3, bei welchem die Steuerungseinrichtung (100) die Zeit, die ein Befehl in der Befehlsspeichereinrichtung (128) gespeichert ist, beim Selektieren des nächsten auszuführenden Befehls berücksichtigt.

5. System nach Anspruch 3, bei welchem die Steuerungseinrichtung (100) die Anzahl der Befehle, welche in der Befehlswarteschlange (128) auf die Ausführung warten, beim Bestimmen, welche Basis für die nächste Befehlsselektion verwendet wird, berücksichtigt.

6. System nach Anspruch 5, bei welchem die Steuerungseinrichtung (100) die Verwendung der Plattenzugriffsbasis zum Selektieren des nächsten auszuführenden Befehls nicht erlaubt, wenn weniger als eine vorbestimmte Befehlsanzahl auf ihre Ausführung in der Befehlswarteschlange (128) warten.

7. System nach Anspruch 6, bei welchem die Steuerungseinrichtung (100) derart wirkt, daß beim Bestimmen eines zur Ausführung zu selektierenden nächsten Befehls unter Verwendung der Plattenzugriffsbasis das Hinzukommen eines Befehls mit einer größeren als einer vorbestimmten Prioritätsebene die Steuerungseinrichtung (100) veranlaßt, diesen Befehl als den nächsten auszuführenden Befehl zu selektieren.

8. System nach Anspruch 6, bei welchem die Steuerungseinrichtung (100) derart wirkt, daß beim Bestimmen eines nächsten zur Ausführung zu selektierenden Befehls unter Verwendung der Plattenzugriffsbasis das Auftreten eines Befehls, welcher eine vorbestimmte Anzahl von Malen unselektiert geblieben ist, die Steuerungseinrichtung (100) veranlaßt, diesen Befehl als nächsten auszuführenden Befehl selektieren.

9. System nach Anspruch 1 oder Anspruch 2, bei welchem die Plattenlaufwerkseinrichtung (104) mehrere Plattenlaufwerke beinhaltet, und wobei eine gleiche Befehlswarteschlange (128) für jedes Plattenlaufwerk (104) vorgesehen ist.