DE69130392T2

DE69130392T2 - Hochgeschwindigkeitspufferverwaltung

Info

Publication number: DE69130392T2
Application number: DE69130392T
Authority: DE
Inventors: Marco Ch-8802 Kilchberg Heddes; Ronald P. Ch-8942 Oberrieden Luijten
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1991-07-10
Filing date: 1991-07-10
Publication date: 1999-06-02
Anticipated expiration: 2011-07-11
Also published as: DE69130392D1; JPH0812634B2; EP0522224A1; EP0522224B1; JPH06195256A; US5432908A

Description

TECHNISCHER BEREICH

Die vorliegende Erfindung bezieht sich auf die Verwaltung eines großen und schnellen Speichers, auf den viele Benutzer Zugriff haben. Der Speicher ist logisch, in mehrere kleinere Teile, die sogenannten Puffer, unterteilt. Es wird ein Puffersteuerungsspeicher benutzt, der so viele Sektionen für Puffersteuerungseinträge (BCRs) hat wie Puffer vorhanden sind, und ein Puffermanager organisiert und steuert diese Puffer, indem die entsprechenden BCRs in verknüpften Listen behalten werden. Die BCRs von freien Puffern werden in einer verknüpften Liste des freien Puffers behalten, und die BCRs der zugewiesenen Puffer in verknüpften Listen gemäß ihren Benutzern. Der Puffermanager gewährt die Zuweisung eines Puffers auf Anforderung eines Benutzers oder nicht, liefert die Adressen der Puffer an die Benutzer und behält die unterschiedlichen verknüpften Listen in dem Puffersteuerungsspeicher. Die Hochgeschwindigkeitspufferverwaltung wie angemeldet kann in einem Protokolladapter in einer Breitbandschaltung eines Kommunikationsnetzwerks oder in anderen Hochgeschwindigkeitsprotokollimplementierungen benutzt werden. Außerdem kann diese in anderen Bereichen benutzt werden, wo anstelle einer Pufferverwaltung eine Art von Hochgeschwindigkeitsbetriebsmittelverwaltung verlangt wird.

HINTERGRUND DER ERFINDUNG

Mit der ständigen Zunahme von zu verarbeitenden Informationen und zu übertragenden Daten wird das schnelle Schalten von Informationen in einem Kommunikationsnetzwerk zu einer wichtigen Aufgabe. Die Netzwerkknoten, in denen Leitungen oder Übertragungsabschnitte miteinander verbunden sind, so daß der Informationsaustausch zwischen ihnen möglich ist, sorgt oft für Verzö gerungen im Netzwerk. Es ist deshalb wünschenswert, über Schaltknoten zu verfügen, die schnell sind und praktisch nicht blockieren. Die Protokolladapter der Schaltknoten benötigen große und schnelle Speicher. Außerdem muß die Verwaltung von diesen Speichern schnell, flexibel und sehr wirksam sein, um eine Anpassung des Systems an die unterschiedlichen Lastbedingungen zu ermöglichen.
Die vorliegende Erfindung bezieht sich hauptsächlich auf Kommunikationsnetzwerke mit Schaltungsuntersystemen, die eine Hardwareimplementierung der Hochgeschwindigkeitspufferverwaltung gemäß dieser Erfindung enthalten. Die nachstehend beschriebenen Ausführungsbeispiele können als Teil einer Breitbandschaltung für Gigabit-LANs oder zur Verbindung von Spitzenrechnern benutzt werden.
Der Stand der Technik, der der Sache am nächsten kommt, wird in dem Artikel von A. P. Engbersen "Algorithm For Managing Multiple First-In, First-Out Queues From A Single Shared Random-Access Memory", IBM Technical Disclosure Bulletin, Vol. 32, No. 3B, pp. 488-492, August 1989, beschrieben. Eine Verwaltungstechnik für eine Vielzahl von Warteschlangen in einem einzelnen, gemeinsam benutzten Direktzugriffsspeicher (RAM) wird beschrieben, die den 'Speicherbereinigungs'-Betrieb bei der Neuorganisation des fragmentierten Speichers, der von bekannten Techniken verlangt wird, vermeidet. In dieser Beschreibung werden die Warteschlangenelemente in diesem RAM, dem sogenannten Daten-RAM gespeichert, und ein zweiter RAM, der sogenannte n_part RAM wird zur Speicherung eines Zeigers benutzt, der die Speicherstellen von Daten in einer Ausgangswarteschlange angibt. Das System arbeitet mittels eines Registers in jedem Ausgangsport, um die Adresse im Daten-RAM zu nennen, aus der die nächsten Daten auszulesen sind. Das Register wird aktualisiert, während die Daten übertragen werden, indem aus dem n_part RAM in der gleichen Adresse wie die Adresse, in der die Daten im Daten-RAM gespeichert wurden, die Adresse ausgelesen wird, in der die nächsten Daten in der Ausgangswarteschlange gespeichert werden. Die Hardwareimplementierung dieser Technik ist komplex und nicht so schnell wie die vorliegenden Hochgeschwindigkeitspufferverwaltungs-Implementierung, so daß weniger Taktzyklen notwendig sind.

ZUSAMMENFASSUNG DER ERFINDUNG

Es ist ein Gegenstand der vorliegenden Erfindung, eine Technik zur Pufferverwaltung bereitzustellen, bei der für die Neuorganisation kein 'Speicherbereinigungs'-Betrieb erforderlich ist.
Ein weiterer Gegenstand der vorliegenden Erfindung ist es, eine Technik zur Pufferverwaltung bereitzustellen, die bei hoher Geschwindigkeit implementiert werden kann.
Ein weiterer Gegenstand ist es, eine Hochgeschwindigkeitspufferverwaltung bereitzustellen, die für die Benutzung als Teil eines Protokolladapters in einem Hochgeschwindigkeitsnetzwerk entwickelt worden ist.
Es ist ein weiterer Gegenstand der Erfindung, eine Pufferverwaltung bereitzustellen, die sehr allgemein ist und einfach an die verschiedenen Anforderungen angepaßt werden kann.
Die Erfindung wie in den unabhängigen Ansprüchen 1 und 11 definiert, beabsichtigt, diese Ziele zu erfüllen und die restlichen Probleme und die Mangelhaftigkeit von bekannten Software- oder Hardwarelösungen zu beheben. In der Hochgeschwindigkeitspufferverwaltungstechnik der Erfindung wie angemeldet, wird dies dadurch erreicht, daß der gemeinsam benutzte große und schnelle Speicher, der logisch in mehrere Puffer unterteilt ist, von einem Puffermanager in Verbindung mit verknüpften Listen organisiert und gesteuert wird. Diese indirekte Adressierung durch die Benutzung von verknüpften Listen ermöglicht ein einfaches Schema und ist deshalb für Hochgeschwindigkeitsanwendungen geeignet. Die Puffer sind zuweisbar und auf Anforderung der Benutzer zugänglich, so daß Daten in diesen Puffern gespeichert bzw. aus diesen ausgelesen werden können. Der Zugriff auf die Puffer wird durch Regeln gesteuert, die in den Puffermanager implementiert werden.
Einige Vorteile der vorliegenden Erfindung sind nachstehend aufgeführt:
- Es können mehrere Pufferverwaltungsschemata implementiert werden, so daß verschiedene Strategien zur Gewährung einer Pufferanforderung durchgeführt werden können.
- Variable Puffergrößen sind möglich (auf einer pro-virtuellen Kanalbasis).
- Jede der Operationen: "request buffer", "put buffer into FIFO", "get buffer from FIFO" und "release buffer" können in vier Zyklen durchgeführt werden (verglichen mit fünf Zyklen bei der Implementierung, wie sie in dem Artikel von A. P. Engbersen in dem oben erwähnten IBM Technical Disclosure Bulletin beschrieben worden ist). Diese Operationen können gleichzeitig ausgeführt werden.
- Es kann nicht nur eine Mehrfach-FIFO-Warteschlange sondern auch eine Mehrfach-LIFO-Warteschlange (last-in/first-out) implementiert werden, indem der FIFO-Manager durch (einen anderen) Kellermanager ersetzt wird.
- Der Puffermanager der vorliegenden Erfindung ist während der Entwicklungszeit, der Initialisierung und der Durchlaufzeit parametrierbar.
- Es können Meldungen von variabler Größe (die als Anzahl von Paketen in einer Meldung definiert werden) unterstützt werden.

BESCHREIBUNG DER ZEICHNUNGEN

Die Erfindung wird nachstehend ausführlich mit Bezug auf die folgenden Zeichnungen beschrieben.
Fig. 1 zeigt ein globales Blockdiagramm eines Systems, das eine Hardwareimplementierung aus der vorliegenden Erfindung enthält.
Fig. 2 zeigt einen Puffermanager mit Keller- und FIFO-verknüpften Listen, die in einem BCR-Speicher gespeichert sind.
Fig. 3 zeigt den BCR-Speicher mit Puffersteuerungseinträgen (BCRs) und einem Datenspeicher mit Puffern.
Fig. 4 zeigt ein Blockdiagramm eines Anforderungsmanagers, der Teil des Puffermanagers aus der Erfindung ist.
Fig. 5 zeigt ein Blockdiagramm eines Kellermanagers, der Teil des Puffermanagers aus der Erfindung ist.
Fig. 6 zeigt ein Blockdiagramm eines FIFO-Managers, der Teil des Puffermanagers aus der Erfindung ist.
Fig. 7 ist ein Taktdiagramm für Anforderungs- und Freigabeoperationen von der Hardwareimplementierung aus der vorliegenden Erfindung.
Fig. 8 zeigt ein Blockdiagramm eines Mehrfach-Kellermanagers.
Fig. 9 zeigt ein Blockdiagramm eines Mehrfach-FIFO-Managers.

ALLGEMEINE BESCHREIBUNG

Die folgende Beschreibung bezieht sich hauptsächlich auf einen Protokolladapter, der Teil eines schaltenden Untersystems von einem Netzwerk ist. Der Adapter ist ein Sender-Empfänger, der auf der Benutzerseite mit einem großen und schnellen, gemeinsam benutzten Speicher arbeitet, und Pakete auf der Schaltseite sendet und empfängt. Der große und schnelle Speicher ist logisch in kleinere Einheiten aufgeteilt, nachstehend Puffer genannt, die zuweisbar sind und für viele Benutzer zugänglich sind. Wenn der Speicher von diesen Benutzern gemeinsam benutzt wird, müssen Regeln für die Zuweisung von Puffern an Benutzer implementiert werden, um Probleme zu verhindern und um die gegebene Speicherkapazität sehr effizient nutzen zu können.
Das erste Ausführungsbeispiel ist eine Hardwareimplementierung der Hochgeschwindigkeitspufferverwaltung aus der Erfindung, wobei das Ausführungsbeispiel Teil eines Protokolladapters von einem Netzwerk ist. Das Ausführungsbeispiel enthält drei Hauptteile, einen großen Datenspeicher 10, einen Puffersteuerungsspeicher (BCR-Speicher) 11 und einen Puffermanager 12 wie in Fig. 1 abgebildet. Die beiden Speicher 10 und 11 sind Direktzugriffsspeicher (RAMs). Der BCR-Speicher 11 ist in so viele Puffersteuerungseinträge (BCRs) unterteilt wie Puffer im Datenspeicher 10 vorhanden sind, so daß jeder Puffer einen entsprechenden Puffersteuerungseintrag (BCR) hat. Die BCRs werden in verschiedenen verknüpften Listen in diesem BCR-Speicher 11 gespeichert und von dem Puffermanager 12 gesteuert und organisiert. Viele Benutzer (virtuelle Kanäle) sind über einen Bus 14 mit einem Empfänger/Sender 13 verbunden. Beim Empfang von Daten von einem Benutzer wird ein Puffer oder werden mehr Puffer angefordert, was von dem für die Daten benötigten Platz abhängt. Wenn es genug freie Puffer gibt, die verfügbar sind, und wenn die Regeln, die im Puffermanager 12 implementiert sind, erfüllt sind, wird die Anforderung von dem Manager 12 bewilligt. Die angeforderten freien Puffer werden über eine verknüpfte Liste in einem freien Puffer, die im BCR-Speicher 11 gespeichert ist, ausgespeichert, und die Adressen von den Puffern werden dem Puffermanager 12 und dem Empfänger 13 zur Verfügung gestellt. Mit diesen Adressen, nachstehend UserData genannt, werden die Puffer im Direktzugriffsspeicher 10 zugewiesen, und der Empfänger 13 und daher der Benutzer selbst hat Zugriff zu dem Datenspeicher 10.
Der Puffermanager 12 aus dem ersten Ausführungsbeispiel besteht aus drei Bausteinen, einem Anforderungsmanager 20, einem Kellerspeichermanager 21 und einem First-In/First-Out Manager 22 (FIFO-Manager) wie in Fig. 2 abgebildet. Basierend auf einigen Regeln, die später beschrieben werden, gewährt der Anforderungsmanager 20 die Anforderungen von Puffern oder nicht. Wenn eine Anforderung von dem Anforderungsmanager 20 gewährt wird, wird der BCR, der dem angeforderten freien Puffer entspricht, aus der verknüpften Liste des freien Puffers im BCR-Speicher 11 ausgespeichert, die von dem Kellerspeicher behalten und gesteuert wird. Die BCRs der freien Puffer werden in einem Kellerspeicher 23.1 behalten. Die UserData der Puffer, die aus dem Kellerspeicher 23.1 ausgespeichert werden, werden bereitgestellt, so daß auf die entsprechenden Puffer zugegriffen werden kann. Zugewiesene Puffer werden in verschiedenen logischen Warteschlangen behalten, eine für jeden Benutzer, indem ihre BCRs in First-In/First-Out-verknüpften Listen 23.1-23.n. behalten werden. Mit einem FIFO-Manager 22 werden diese FIFOs 23.2- 23.n gesteuert und verarbeitet. Die Puffer werden regeneriert, indem diese mittels der FIFOs 23.2-23.n und dem Kellerspeicher 23.1 verarbeitet werden.
Die Organisation der verschiedenen verknüpften Listen im BCR- Speicher 11 und den Puffern im Datenspeicher 10 ist in Fig. 3 abgebildet. In diesem Beispiel hatten zwei Benutzer, die virtuellen Kanäle (VC0, VC1), Zugriff auf den Datenspeicher 10. Die Daten aus dem ersten virtuellen Kanal sind als Großbuchstaben (ABCD ... H) abgebildet, und die Daten aus dem zweiten virtuellen Kanal sind als Kleinbuchstaben (abcd ... h) abgebildet.
Wie Fig. 3 zeigt, enthalten die Puffer 30.3, 30.5, 30.13 und 30.10 Daten aus dem virtuellen Kanal VC0, die Puffer 30.8 und 30.1 enthalten Daten aus VC1 und die restlichen Puffer sind frei. Die entsprechenden BCRs, die im BCR-Speicher 11 gespeichert sind, haben zwei Felder. Das erste ist das UserData Feld, das in diesem Beispiel die Adresse des entsprechenden Puffers im Datenspeicher 10 enthält, und das zweite Feld ist ein Zeiger, genannt next, auf einen anderen BCR. Die BCRs der freien Puffer 30.2, 30.4, 30.6, 30.7, 30.9, 30.11, 30.12 und 30.14 werden in einer verknüpften Liste des freien Puffers im BCR- Speicher 11 behalten. Diese verknüpfte Liste beginnt mit BCR 31.2 und wird durch Zeiger auf die folgenden BCRs verknüpft. Das Zeigerfeld enthält die Adresse des nächsten BCRs, das schematisch mit hellgrauen Pfeilen von einem BCR zum anderen dargestellt ist. Die verknüpfte Liste des freien Puffers benimmt sich wie ein Kellerspeicher 23.1, der in Fig. 2 abgebildet ist und hat einen Zeiger top, der das erste UserData Feld des Kellerspeichers markiert. Bei einem Kellerspeicher ist kein Zeiger an seinem Ende erforderlich, so daß der letzte BCR 31.14 des Kellerspeichers mit einem nil Feld endet.
Die BCRs der Puffer, die von VC0 und VC1 zugewiesen werden, werden in zwei FIFO-verknüpften Listen behalten. Die erste beginnt mit einem front(0) Zeiger, siehe BCR 31.3, und die zweite endet im BCR 31.10 mit einem back(0) Zeiger. Die nächsten Felder der BCRs, die den zugewiesenen Puffern entsprechen, enthalten die Adressen der folgenden BCRs, so daß die Listen von VC0 und VC1 sich wie FIFO-Listen benehmen. Die Reihenfolge der Nachfolge innerhalb dieser FIFOs ist durch Pfeile gekennzeichnet.
Die Benutzung der drei Komponenten 20-22 des Puffermanagers 12 wird anhand des folgenden Beispiels erklärt, wobei das System aus der Erfindung Teil einer Hochgeschwindigkeitsschaltung oder eines Hochgeschwindigkeits-LAN-Adapters ist. Wir berücksichtigen eine Protokollmaschine, die aus einem Empfänger- und einem Senderteil 13 besteht.
Der Empfänger führt die unten beschriebenen Aktionen nach Empfang eines Datenblocks aus. Der Termblock, auf den hier Bezug genommen wird, wird benutzt, um Dateneinheiten anzugeben, die aus der Literatur als Rahmen, Paket oder Zelle bekannt sind. Er bestimmt den Verbindungskennzeichner (ID), den sogenannten virtual channel identifier (VCID), und fordert einen Puffer an. Der Anforderungsmanager 20 bestimmt, ob die Anforderung gewährt wird, was als 'grant request' in Fig. 2 symbolisiert ist, und erlaubt dem Kellerspeichermanager 21 einen freien Puffer aus dem Kellerspeicher 23.1 auszuspeichern. Somit werden ein Zeiger auf diesen freien Puffer sowie ein Zeiger auf den entsprechenden BCR von dem Kellerspeichermanager 21 zurückgeschickt. Der Zeiger auf den freien Puffer ist seine Adresse, so daß die empfangenen Daten in diesem Puffer gespeichert werden können. Dann wird der Empfänger diesen Puffer und seinen BCR in dem FIFO ablegen, der dem virtuellen Kanal entspricht. Dies geschieht, indem eine PUT-Operation im FIFO-Manager 22 durchgeführt wird, wobei die Parameter der VCID- und BCR-Zeiger sind. Der Puffer, der aus der verknüpften Liste des freien Puffers entfernt wurde, wurde in der FIFO-verknüpften Liste des virtuellen Kanals hinzugefügt. Falls große Datenpakete empfangen werden müssen, wird der Prozeß zur Anforderung eines Puffers usw. wiederholt durchgeführt. Es könnten spezielle Regeln implementiert werden, um diese Funktion wirksam zu unterstützen.
Der Sender führt die folgenden Aktionen durch. Wenn genug Daten von einem virtuellen Kanal (VC0) empfangen wurden (wenn z. B. eine Meldung, die aus mehreren Datenblöcken besteht, ergänzt worden ist) liest der Sender den entsprechenden FIFO aus. Der erste BCR 31.3 von diesem FIFO, auf den von front(0) gezeigt wird, und die UserData des entsprechenden Puffers 30.3 werden von dem FIFO-Manager 22 zurückgeschickt. Die Adresse des Puffers 30.3 wird von den UserData angegeben, und die im Puffer gespeicherten Daten können gelesen und übertragen werden, möglicherweise mit einem vorangestellten Anfangsetikett, das von dem Sender erstellt wurde. Nachdem das Lesen der Daten abgeschlossen worden ist, muß der Puffer als frei markiert werden. Dies geschieht mit einer RELEASE-Operation im Anforderungsmanager 20 und indem der Puffer (der durch UserData gekennzeichnet ist) in den Kellerspeicher 23.1 eingespeichert wird (PUSH). Der Sender kann mit dem Lesen fortfahren, bis alle gespeicherten Bytes übertragen wurden. Die Anzahl der freien Puffer steigt mit jedem freigegebenen Puffer.
Die notwendigen Synchronisierungsmechanismen, die von dem gesamten System abhängen und nicht von der Pufferverwaltung aus der Erfindung beeinflußt werden, werden nicht beschrieben. Der Anforderungsmanager 20 aus dem ersten Ausführungsbeispiel und die möglichen Regeln, die implementiert werden können, sind nachstehend beschrieben.

1) Anforderungsmanager

Eine maximale Anzahl von Puffern (locMax[i]) wird jedem virtuellen Kanal [i] zugewiesen, so daß die maximale Anzahl von Puffern, die von dem virtuellen Kanal [i] zugewiesen werden kann von locMax[i] begrenzt wird. Dadurch soll verhindert werden, daß einige Benutzer (VCs) alle verfügbaren freien Puffer verbrauchen. Außerdem wird eine Anzahl privater Puffer (privMin[i]) jedem Benutzer zugewiesen, so daß diese Puffer dem entsprechenden Benutzer vorbehalten sind. Diese Puffer können von anderen Benutzern nicht zugewiesen werden. So lange wie ein Benutzer nicht alle seine privaten Puffer verbraucht hat, wird eine Pufferanforderung des Benutzers stets gewährt werden.
Basierend auf diesen Regeln und den oben definierten Variablen sind die folgenden Pufferverwaltungsschemata möglich:
- Festes Schema: Der Datenspeicher 10 ist in feste Teile partitioniert, jeder Private für einen VC. privMin[i] = locMax[i] oder privMin[i] und SUM locMax[i] = "Gesamtanzahl verfügbarer Puffer" werden beispielsweise nicht benutzt.
- Gemeinsam benutztes Schema: Der Datenspeicher 10 wird komplett von allen Kanälen gemeinsam benutzt. Es ist kein Anforderungsmanager notwendig sondern nur ein Kellerspeicher mit freien Puffern.
- Gemeinsame Benutzung mit Max-Schema: Wie vor, jedoch mit einer Begrenzung der Anzahl von offenen Puffern pro VC (privMin[i] wird beispielsweise nicht benutzt).
- Gemeinsame Benutzung mit privatem Schema: Wie gemeinsam benutztes Schema, jedoch mit einer reservierten Anzahl von privaten Puffern pro VC (locMax[i] wird beispielsweise nicht benutzt).
- Kombiniertes Schema: Ist eine Kombination aus den beiden letztgenannten Schemata.
Das kombinierte Schema ist das allgemeinste und komplexeste und wird in dem ersten Ausführungsbeispiel implementiert.
Eine Hardwareimplementierung des Anforderungsmanagers (20) ist in Fig. 4 abgebildet. Der Anforderungsmanager 20 verwaltet die Anforderung und Freigabe von Puffern durch die Benutzung der implementierten Regeln - wie oben beschrieben wurde - und indem lokale und globale Variablen (lokal in den virtuellen Kanälen) benutzt werden. Wenn der Anforderungsmanager 20 eine Anforderung gewährt, dann ist es die Aufgabe der Benutzer, den Puffer wirklich zu bekommen, indem er aus dem Kellerspeicher 23.1 mit den freien Puffern ausgespeichert (POP) wird. Nach Benutzung eines Puffers muß dieser freigegeben werden. Dies erfordert einen RELEASE-Befehl an den Anforderungsmanager 20 sowie einen PUSH-Befehl, so daß der Puffer in den Kellerspeicher 23.1 eingespeichert wird.
Nachstehend wird eine Implementierung des oben erwähnten kombinierten Schemas beschrieben. Im Fall von anderen Schemata kann die Hardware vereinfacht werden.
Die unten angegebenen Statusvariablen werden für die Implementierung der Pufferverwaltungsregeln benutzt.
- used[i]: Dieser Parameter (local to VC(i)) bezeichnet die Anzahl von Puffern, die aktuell von VC(i) benutzt werden. Durch eine bewilligte Anforderung wird dieser Parameter inkrementiert und durch eine Freigabe dekrementiert.
- locMax[i]: Die maximale Anzahl von Puffern, die von VC(i) benutzt werden können. Es ist für den Anforderungsmanager eine Konstante, obwohl sie beispielsweise von einem Steuerungsprozessor geändert werden kann.
- privMin[i]: Die Anzahl von Puffern, die für die private Benutzung des VC(i) reserviert sind. Es ist für den Anforderungsmanager 20 auch eine Konstante und kann wie locMax[i] geändert werden.
- NotReserved: Wenn FreeBuffers die Gesamtanzahl an freien Puffern bezeichnet, und ResBuffers die Gesamtanzahl von reser vierten Puffern (d. h. noch nicht angeforderte private Puffer), dann wird NotReserved definiert, um die Anzahl von freien Puffern zu bezeichnen, die nicht reserviert sind, wie dies durch die Gleichung angegeben wird:
NotReserved = FreeBuffers - ResBuffers (1)
Weitere Einzelheiten sind in den nachfolgenden Aufstellungen enthalten.
Die Operationen des Anforderungsmanagers 20, die mit diesen Variablen durchzuführen sind, sind in den folgenden Aufstellungen, die mit der "Pseudo Pascal" Syntax geschrieben wurden, dargestellt. Initialisierung Funktionsanforderung Funktionsfreigabe
Ein Anforderungsmanager 20, der auf den angegebenen Regeln und Aufstellungen basiert, kann mit dem in Fig. 4 abgebildeten Blockdiagramm wirksam implementiert werden. Das Blockdiagramm besteht aus den folgenden Teilen wie dem WriteBackRegister 40 (WriteBackReg), den Variablen 41, dem WorkRegister 42 und dem Server 43. Die lokalen Variablen used[i], locMax[i] und privMin[i] (lokal mit Bezug auf einen virtuellen Kanal) werden in einem RAM 44 gespeichert. Die lokalen Variablen von VC0 werden in der oberen Zeile von diesem RAM 44 gespeichert, und die Variablen der folgenden Benutzer, VC(i) mit i > 0, werden in den folgenden Zeilen gespeichert. Die globale Variable NotReserved wird in einem Register 45 gespeichert, das Teil des Variablenblocks 41 ist. Es werden drei Register 46.1-46.3 benutzt, um die lokalen Variablen eines VC zu speichern, wie diese nach Anforderung von diesem VC aus dem RAM 44 ausgelesen worden sind. Der Server 43 prüft, ob eine Anforderung bewilligt werden kann, indem die im WorkRegister 42 gespeicherten Variablen benutzt werden. Die Prüfung basiert auf den implementierten Regeln. Die verschieden Prüfungen sind in den Aufstellungen angegeben, da es Funktionsanforderung und Funktionsfreigabe gibt. Die lokalen Variablen und die globale Variable werden dem Anforderungs-/Freigabe-Server 47 zugeführt, der die einzelnen, in den Aufstellungen dargestellten Schritte ausführt. Die Variablen werden addiert oder subtrahiert, ggf. mit dem Addierer/Subtrahierer 48 und 49. Diese Addierer/Subtrahierer sind mit dem Anforderungs-/Freigabe-Server 47 verbunden und werden von diesem gesteuert. Das benutzte WriteBackReg 40 enthält ein Register 50, das die geänderte Variable used[i] speichert, bevor sie in den RAM 41 zurückgeschrieben wird. Eine zusätzliche Finite-State-Maschine (ohne Abbildung) steuert die Operation der letztgenannten vier Teile 40-43.
Die Operation des Anforderungsmanagers 20, wie in Fig. 4 dargestellt, ist jetzt klar. Nach Anforderung eines virtuellen Kanals, z. B. VC0, wird der Kennzeichner des virtuellen Kanals (VCID) als Adresse der lokalen Variablen im RAM 44 genutzt. Durch Benutzung dieser Adresse werden die lokalen Variablen des virtuellen Kanals aus dem RAM 44 in die Register 46.1-46.3 gelesen. Der Server 43 bestimmt, ob die Anforderung bewilligt werden kann und ändert dementsprechend die lokalen und globalen Variablen mittels der Algorithmen, die in der Aufstellung dargestellt sind. Wenn eine Anforderung bewilligt wird, wird die Variable used[i] mit dem Addierer/Subtrahierer wie folgt inkrementiert:
used[i]: = used[i] + 1. (2)
Die Variable NotReserved wird dekrementiert, wie dies in der Gleichung (3) angegeben ist, wenn die Puffer verfügbar sind, die nicht reserviert sind, used[i] ≥ privMin[i] und used[i] < locMax[i].
NotReserved: = NotReserved - 1. (3)
Die Freigabe von zugewiesenen Puffern funktioniert auf eine ähnliche Art und Weise, und die lokale Variable used[i] wird mit jedem Puffer des virtuellen Kanals, der freigegeben wird, dekrementiert, was durch
used[i]: = used[i] - 1 w (4)
angegeben wird.
Die globale Variable NotReserved wird - falls erforderlich (siehe Aufstellung) - inkrementiert, was durch
NotReserved: = NotReserved + 1 (5)
gegeben wird.
Ein Steuerungsprozessor benötigt Zugang zu den Variablen, er muß diese zumindest initialisieren können. Die Variablen können außerdem von diesem Prozessor dynamisch geändert werden (z. B. basierend auf den erwarteten Verkehrsanforderungen). Die Änderungen sind jedoch nicht unbedeutend und sollten sorgfältig ausgeführt werden. Durch die Änderung der Variablen ist es beispielsweise möglich, den großen und schnellen Datenspeicher neu zu organisieren, wenn einer der Benutzer aufgrund von Problemen abschaltet, so daß die Puffer, die nicht länger von diesem Kanal benutzt werden, für andere Benutzer bereitgestellt werden. Es ist möglich, die Ausführungsgeschwindigkeit des Servers zu erhöhen, indem zusätzliche Variablen im RAM 44 gespeichert werden. Diese Variablen sind Ergebnisse aus Vergleichsoperationen (z. B. used[i] < locMax[i]). Der Server kann somit die Variablen sofort entsprechend inkrementieren/dekrementieren, während Vergleiche für die nächste Anforderung parallel zum Inkrementieren/Dekrementieren ausgeführt werden. Die Ergebnisse aus den Vergleichen werden dann im RAM gespeichert und sind somit für die nächste Anforderung verfügbar.

2) Der Kellerspeichermanager

In diesem Abschnitt wird eine Hardwareimplementierung des Kellerspeichermanagers 21 beschrieben. Sein Blockdiagramm ist in Fig. 5 abgebildet. Der Kellerspeichermanager 21 besteht aus einer Variablen 51 und einem Serverblock 52. Drei Register, top 54.1, userDataCopy 54.2 und next 54.3, sind Teil des Variablenblocks 51. Der Serverblock 52 enthält einen Kellerspeicher-Server 53, der mit dem BCR-Speicher 11 und den Registern des Variablenblocks 51 verbunden ist. Die verknüpfte Liste des freien Puffers, der von dem Kellerspeichermanager 21 gesteuert und verwaltet wird und im BCR-Speicher 11 gespeichert ist, benimmt sich wie ein Kellerspeicher (Kellerspeicher 23.1, Fig. 2). Jeder BCR des Kellerspeichers 23.1 enthält UserData (d. h. die physische Adresse des entsprechenden Puffers) und einen zusätzlichen Zeiger, hier als next bezeichnet, der eine Adresse im BCR-Speicher 11 ist, auf das nächste Element (BCR) in der Liste.
Wenn eine Anforderung bewilligt wird, muß ein freier Puffer aus dem Kellerspeicher 23.1 ausgespeichert (POP) werden. Der Anforderungsmanager 20 ermöglicht es, einen freien Puffer über die POPenabled Leitung 55 aus der Liste herauszunehmen. Ein POP-Befehl entfernt das erste Element aus der verknüpften Liste des freien Puffers, schickt einen Zeiger auf dieses Element zurück (wird später für PUT, GET und PUSH benutzt) und schickt auch die UserData des entsprechenden Puffers in den Datenspeicher 10 zurück. Zur Freigabe eines Puffers müssen diese vorne im Kellerspeicher 23.1 mit einem PUSH-Befehl eingefügt werden. Es wird angenommen, daß die UserData konstant sind. Ihre Werte werden während der Initialisierung von einem Steuerungsprozessor angegeben.
Um eine effiziente Listenverwaltung durchzuführen, werden die folgenden drei Statusvariablen benutzt. Die Statusvariablen werden so ausgewählt, daß alle Kellerspeicheroperationen nur einen Zugriff auf den BCR-Speicher 11 erfordern.
- top: Dies ist ein Zeiger im oberen Teil des Kellerspeichers 23.1 (siehe Fig. 3). Der Zeiger ist im Register 54.1 gespeichert.
- UserDataCopy: Eine Kopie der UserData von dem oberen Kellerspeicherelement wird als UserDataCopy bezeichnet. Die Kopie wird im Register 54.2. aufbewahrt.
- next: Dies ist ein Zeiger auf das nächste Element im Kellerspeicher 23.1. Er wird im Register 54.3 gespeichert.
Ein einzelner Kellerspeicher 23.1 kann - wie Fig. 5 zeigt - implementiert werden. Die Implementierung erfolgt nach dem gleichen Konzept wie die Implementierung des Anforderungsmanagers, die im Abschnitt 1) Anforderungsmanager beschrieben worden ist. Der Kellerspeichermanager 21 benötigt nur globale Variablen, so daß RAM, WorkRegister und WriteBackReg des Anforderungsmanagers 20 weggelassen werden können. Der Kellerspeicher- Server 53 wird hauptsächlich für die Listenverwaltung benutzt. Er wird von einer State-Maschine (ohne Abbildung) ausgeführt, und seine Funktionsbeschreibung ist in den folgenden Aufstellungen enthalten. Initialisierung POP-Prozedur(var theBCRPtr, theUserData) PUSH-Prozedur(theBCRPtr)
Es ist zu beachten, daß die Größe eines Puffers bei der Initialisierungszeit des Systems bestimmt wird, wenn nämlich der BCR- Speicher 11 initialisiert wird. Dazu gehört ein Anfangs-Setup der verknüpften Liste des freien Puffers aber auch der UserData, die in den meisten Fällen nur aus der physischen Adresse des Puffers bestehen.

3) FIFO-Manager

Diese Auswahl bezieht sich auf die Implementierung des FIFO-Managers 22, der Teil des ersten Ausführungsbeispiels ist. Ein Blockdiagramm des FIFO-Managers 22 ist in Fig. 6 abgebildet. Diese Implementierung ist fast die gleiche wie die des Kellerspeichermanagers 21. Alle FIFO-Elemente (BCRs) werden in verknüpften Listen im BCR-Speicher 11 gespeichert. Der Variablenblock 60 des FIFO-Managers 22 enthält zwei Register, das erste 63.1, das als Frontregister 63.1 bezeichnet wird, und das zweite, das sogenannte Backregister 63.2. Der Server 61 besteht aus einem FIFO-Server 62, der eine effiziente Listenverwaltung durchführt. Die folgenden Statusvariablen werden in der vorliegenden Implementierung benutzt:
- front(i): Dies ist ein Zeiger auf das erste FIFO-Element (BCR) von der verknüpften Liste des Benutzers (i). Das Frontregister 63.1 wird zur Speicherung während der Operation benutzt.
- back(i): Dies ist ein Zeiger auf das zuletzt eingefügte Element der verknüpften Liste. Das Backregister 63.2 wird als Register für diesen Zeiger benutzt.
Wenn eine Anforderung bewilligt wurde, und ein freier Puffer aus dem Kellerspeicher der freien Puffer 23.1 ausgelesen worden ist, muß er am Ende der Liste des Benutzers eingefügt werden. Zum Einfügen wird ein PUT-Befehl benutzt. Die PUT-Prozedur - wie im FIFO-Server 62 implementiert - folgt nachstehend (siehe Aufstellung). Beim Entfernen von Daten aus dem Datenspeicher 10 entfernt ein GET-Befehl das erste Element aus der Liste, schickt einen Zeiger auf dieses Element zurück und schickt ebenfalls die UserData zurück. Die Einzelheiten sind der nachstehend aufgeführten GET-Prozedur zu entnehmen. Initialisierung PUT-Prozedur(theBCRPtr) GET-Prozedur(var theBCRPtr, theUserData)
Nach der Beschreibung der drei Komponenten des Puffermanagers 12 wird ihre Leistung erörtert. Eine Anforderung besteht aus den folgenden vier Zyklen (siehe Fig. 7).
1. Während des ersten Zyklus 70.1 werden die lokalen Variablen used[i], IocMax[i] und privMin[i], die im RAM 44 gespeichert sind, gelesen. Der VCID (VCID von VC0 in Fig. 7) des anfordernden Benutzers wird auf den RAM 44 angewendet, und die Variablen werden im WorkRegister 42 getaktet.
2. Der Anforderungs-/Freigabe-Server bestimmt, ob eine Anforderung bewilligt werden kann und ändert die Variablen (vars) während des Zyklus 70.2. Am Ende des zweiten Zyklus 70.2 ist somit bekannt - und wird von der POPenabled Ausgabe des Anforderungsmanagers 20 angegeben - ob die Anforderung bewilligt wird oder nicht.
3. Während des dritten Zyklus 70.3 werden die geänderten Variablen (vars ') im WriteBackReg 40 getaktet.
4. Während des vierten Zyklus 70.4 werden die Inhalte des WriteBackReg 40 unter seiner Ursprungsadresse in den RAM 44 zurückgeschrieben.
Auf die gleiche Art und Weise kann gezeigt werden, daß eine Freigabe ebenfalls vier Zyklen 70.3-70.6 benötigt. Die Lese- und Schreiboperationen, die in Fig. 7 abgebildet sind, werden benutzt, um Variablen aus dem RAM 44 zu lesen bzw. in diesen zu schreiben. Das Lesen und Schreiben von Daten ist in der Figur nicht abgebildet. Eine Anforderung und eine Freigabe können überlappt werden, was in der Fähigkeit resultiert, sowohl eine Anforderung als auch eine Freigabe (oder 2 Anforderungen oder Freigaben) in vier Zyklen durchführen zu können.
Da der FIFO-Manager 22 auf die gleiche Art und Weise wie der Anforderungsmanager 20 implementiert werden kann (siehe Fig. 6) kann eine GET- und PUT-Operation ebenfalls in vier Zyklen durchgeführt werden. Bei GET und PUT ist jeweils nur ein Zugriff auf den BCR-Speicher 11 (RAM 44) erforderlich.
Das gleiche Prinzip wird auf den Kellerspeichermanager 21 angewendet. Sowohl eine POP- als auch eine PUSH-Operation können in zwei Zyklen durchgeführt werden, und bei POP und PUSH ist jeweils nur ein Zugriff auf den BCR-Speicher erforderlich.
Im Anforderungs-/Freigabe-Server 47 des Anforderungsmanagers 20 kann ein Engpaß auftreten, da ein Vergleich vor einer Inkrementierung oder Dekrementierung durchgeführt werden muß. Um die höchste Leistung zu erreichen, können Vergleichs- und Inkrementierungs-/Dekrementierungsoperationen parallel durchgeführt werden, wobei der Vergleich sein Ergebnis für die nächste Anforderung/Freigabe berechnet. Dieses Ergebnis muß natürlich gespeichert werden, wobei eine Erweiterung der Statusvariablen mit Aussagelogik erforderlich ist, welche die Ergebnisse der Vergleiche enthält, wie dies zuvor beschrieben worden ist. Weitere Ausführungsbeispiele sind vorstellbar, indem die unterschiedlichen Schemata, wie diese im Kontext mit dem ersten Ausführungsbeispiel beschrieben worden sind, implementiert werden. Diese Ausführungsbeispiele können auf dem einen basieren, das zuvor beschrieben worden ist. Die Hardware kann reduziert werden, was von dem jeweiligen implementierten Schema abhängt. Bei einer Hardwareimplementierung des gemeinsam benutzten Schemas, oder wenn keine Regeln für die Anforderung erforderlich sind, kann der Anforderungsmanager weggelassen werden. Für die Implementierung der gemeinsamen Benutzung mit Max-Schema, wobei die Variablen privMin[i] nicht benutzt werden, kann die privMin[i]- Spalte von dem RAM 44 des Anforderungsmanagers 20 weggelassen werden, wie dies in Fig. 4 dargestellt ist. Es können zusätzlich weitere Funktionen und Prozeduren als die implementiert werden, die in den Aufstellungen aufgeführt sind. Anstelle eines Kellerspeichers und Kellerspeichermanagers für die freien Puffer können diese Puffer in einem FIFO organisiert werden, der natürlich einen FIFO-Manager zur Verwaltung der freien Puffer erfordert. In dem ersten Ausführungsbeispiel wurde erwähnt, daß ein BCR aus zwei Feldern besteht, dem UserData und dem next Feld. In manchen Fällen, wenn beispielsweise der Zeiger auf den BCR direkt auf der physischen Adresse des entsprechenden Puffers abgebildet werden kann, kann das UserData Feld weggelassen werden.
Das zweite Ausführungsbeispiel der vorliegenden Erfindung bezieht sich auf ein System, das einen Puffermanager 83 und einen Datenspeicher hat, der in Puffer von unterschiedlicher Größe unterteilt ist. Deshalb müssen der Kellerspeichermanager und die verknüpfte Liste des freien Puffers geändert werden. Für jede Puffergröße wird ein entsprechender Keller benutzt, so daß es relativ einfach ist, Puffer verschiedener Größe zu unterstützen. Die Implementierung mit Mehrfach-n-Kellern (n ist die Anzahl der Keller) basiert auf der Einzelkellerimplementierung, die in 2) Kellerspeichermanager beschrieben worden ist. Da es jetzt n-Keller gibt, sollte es im Prinzip auch n-Register geben, welche die erforderlichen Parameter enthalten (top, UserDataCopy und next, siehe Fig. 5). Anstelle von n-Registern können die erforderlichen Parameter auch in einem RAM 80 gespeichert werden, siehe Fig. 8. Dieser RAM 80, der Teil des Variablenblocks 85 ist, hat n-Zeilen mit drei Feldern für die Parameter top, UserDataCopy und next. Ähnlich wie bei dem Anforderungsmanager 20 - siehe Fig. 4 - werden die zusätzlichen Blöcke, WriteBackReg 81 und WorkReg 82, benutzt, um die Parameter aus dem RAM 80 zu lesen und sie zurückzuschreiben. Der Kellerspeicher-Server 84 ist mit dem Kellerspeicher-Server 53 der Einzelkellerspeicherimplementierung vergleichbar. Die auf den RAM 80 angewendete Adresse bestimmt, in welchem der n-Keller die POP- oder PUSH-Operation durchgeführt wird. Welche Puffergröße aus einem der n-Keller auszulesen ist, ist von dem Benutzer festzulegen. Außerdem wird der einzelne FIFO auf einen Mehrfach-n-FIFO erweitert, was auf die gleiche Art und Weise geschieht wie bei der Erweiterung des Einzelkellers. Das Blockdiagramm des Mehrfach-FIFO-Managers 90 ist in Fig. 9 abgebildet. Zur Speicherung der Parameter front(i) und back(i) wird ein RAM 91 benutzt. Ein WorkReg-Block 92 und ein WriteBackReg- Block 93 werden für die zu bearbeitenden Parameter benutzt. Jeder dieser Blöcke enthält zwei Register 94.1-94.4. Der FIFO- Server 95 ist mit dem Server 62 der Einzel-FIFO-Implementierung vergleichbar. Die verschiedenen Regeln und Schemata, die im Kontext mit dem ersten Ausführungsbeispiel beschrieben worden sind, können benutzt werden.
Basierend auf diesen Ausführungsbeispielen können verschiedene Hardwareimplementierungen durch Anpassung an eine gegebene Umgebung durchgeführt werden.

Claims

1. Ein Speichersystem in einem bestimmten Speichersystem als Teil eines Protokolladapters bestehend aus einem gemeinsamen Speicher (10), der in eine Vielzahl von Puffern unterteilt ist, einem Puffersteuerungsspeicher (11), der für Puffersteuerungseinträge (BCRs) in soviele Sektionen unterteilt ist wie Puffer vorhanden sind, und einem Puffermanager (12), wobei der Puffermanager (12) einen freien Puffermanager (21; 83) enthält, um alle diese Puffer zu steuern und zu organisieren, der frei ist, indem die entsprechenden BCRs in wenigstens einer verknüpften Liste im freien Puffer (23.1) behalten werden, und ein zugewiesener Puffermanager (22; 90), um alle diese Puffer, die bereits zugewiesen wurden, zu steuern und zu organisieren, indem die entsprechenden BCRs in den verknüpften Listen(23.2-23.n) des zugewiesenen Puffers erhalten bleiben, wobei eine verknüpfte Liste (23.2- 23.n) des zugewiesenen Puffers für jeden Benutzer benutzt wird, und die verknüpften Listen (23.1, 23.2-23.n) in diesem Puffersteuerungsspeicher (11) in verschachtelter Form vereint werden, dadurch gekennzeichnet, daß der Puffermanager (12) außerdem einen Anforderungsmanager (20) enthält, um einem Benutzer eine Anforderung zu gewähren oder nicht zu gewähren, wobei die Anforderung auf Regeln basiert, die in diesem Anforderungsmanager (20) implementiert wurden, wobei der Anforderungsmanager benutzerdefinierte Variablen und Systemstatusvariablen enthält, und verschiedene Benutzer Daten in die Puffer des gemeinsamen Speichers (10) eingeben bzw. von den Puffern erhalten können, wobei die benutzerdefinierten Variablen eine Variable für die maximale Anzahl von Puffern (locMax[i]) enthält, die jedem Benutzer zugewiesen werden und/oder eine Variable für die Anzahl von privaten Puffern (privMin[i]), die einem Benutzer i zugewiesen werden.

2. Das Speichersystem aus Anspruch 1, wobei der Anforderungsmanager (20) einen Speicher (41) enthält, in dem die benutzerdefinierten Variablen und die Systemstatusvariablen gespeichert sind, einen Server (43), der bestimmt, ob eine Anforderung gewährt wird oder nicht, indem die Regeln und Variablen benutzt werden.

3. Das Speichersystem aus Anspruch 1 oder 2, wobei die verknüpfte Liste (23.1) des freien Puffers so organisiert ist, daß die freien Puffer erscheinen, um in einem Kellerspeicher gespeichert zu werden.

4. Das Speichersystem aus Anspruch 3, wobei der freie Puffermanager (21) einen Server (52) und Register (54.1, 54.2, 54.3) enthält, so daß ein Zeiger auf dem ersten BCR (31.2) der verknüpften Liste (23.1) des freien Puffers und ein Zeiger auf dem entsprechenden Puffer (30.2) in diesen Registern (54.1, 54.2) behalten werden.

5. Das Speichersystem aus Anspruch 4, wobei die Puffer, die zugewiesen wurden, so organisiert sind, daß sie erscheinen, um in der First-in/First-out (FIFO) Warteschlange gespeichert zu werden, indem die entsprechenden BCRs demgemäß behalten werden, wobei ein Zeiger auf den Anfang einer verknüpften Liste (23.2) des zugewiesenen Puffers und ein Zeiger auf das Ende dieser Liste (23.2) in diesem Speicher (60; 91) behalten werden.

6. Das Speichersystem aus Anspruch 5, wobei der freie Puffermanager (83) einen Direktzugriffsspeicher (RAM) (80) enthält, der Zeiger in der verknüpften Liste des freien Puffers enthält.

7. Das Speichersystem aus Anspruch 1, wobei der freie Puffermanager (21; 83) und der zugewiesene Puffermanager (22; 90) einen Server (52, 61; 84, 96) und einen Speicher (56, 60; 85, 91) enthalten.

8. Das Speichersystem aus Anspruch 1, wobei der gemeinsame Speicher (10) in eine Vielzahl von Puffern unterschiedlicher Größe unterteilt ist, und wobei der freie Puffermanager (83) soviel verknüpfte Listen des freien Puffers steuert und organisiert, wie Puffer unterschiedlicher Größe vorhanden sind.

9. Das Speichersystem aus Anspruch 1 oder 2, wobei ein BCR (31.2) ein Feld (UserData) für die physische Adresse des entsprechenden Puffers (30.2) und ein Feld (next) für einen Zeiger auf einen anderen BCR (31.4) oder ein Feld (nil) für einen Flag enthält, der das Ende einer verknüpften Liste markiert.

10. Das Speichersystem aus Anspruch 1 oder 2, wobei ein BCR entweder ein Feld (next) für einen Zeiger auf einen anderen BCR oder ein Feld (nil) für einen Flag enthält, der das Ende einer verknüpften Liste markiert, und wobei der BCR direkt in einem entsprechenden Puffer dargestellt ist, so daß kein zusätzliches Feld für die Pufferadresse notwendig ist.

11. Verfahren zur Verwaltung des Zugriffs von verschiedenen Benutzern auf einen gemeinsamen Speicher (10), der in eine Vielzahl von Puffern unterteilt ist und Teil eines Speichersystems ist, das außerdem einen Puffersteuerungsspeicher (11) enthält, der für Puffersteuerungseinträge (BCRs) in soviel Sektionen unterteilt ist wie Puffer vorhanden sind, und einen Puffermanager (12), wobei alle freien Puffer des gemeinsamen Speichers (10) als mindestens eine verkettete Warteschlange mit freien Puffern organisiert sind, indem die entsprechenden BCRs in wenigstens einer verknüpften Liste (23.1) des freien Puffers behalten wer den, und alle zugewiesenen Puffer des gemeinsamen Speichers (10) als verkettete Warteschlangen von zugewiesenen Puffern organisiert sind, und zwar eine Warteschlange für jeden der Benutzer, indem die entsprechenden BCRs in soviel verknüpfte Listen (23.2-23.n) des zugewiesenen Puffers behalten werden wie Warteschlangen vorhanden sind, wobei jedesmal, wenn ein Puffer einem Benutzer zugewiesen wird, dieser aus dieser verketteten Warteschlange mit freien Puffern herausgenommen wird und mit der Warteschlange des Benutzers verknüpft wird, wenn diese noch vorhanden ist und andernfalls mit einer neuen Warteschlange verknüpft wird, indem ihr BCR aus dieser verknüpften Liste (23.1) des freien Puffers herausgenommen wird und in diese verknüpfte Liste (23.2-23.n) des zugewiesenen Puffers der Warteschlange eingefügt wird, wobei jedesmal, wenn ein Puffer aus der Warteschlange eines Benutzers ausgelöst wird, diese in diese verkettete Warteschlange mit freien Puffern eingefügt wird, indem ihr BCR aus der verknüpften Liste (23.2-23.n) des Benutzers herausgenommen wird und in die verknüpfte Liste (23.1) des freien Puffers eingefügt wird, dadurch gekennzeichnet, daß jede Anforderung eines Benutzers für die Zuweisung eines Puffers von diesem Puffermanager (12) bearbeitet wird, der diese Anforderung entweder gewährt oder nicht gewährt, was von den Regeln abhängig ist, die in dem Puffermanager (12) implementiert wurden, wobei der Puffermanager (12) Variablen und Systemstatusvariablen enthält, und die benutzerdefinierten Variablen eine maximale Anzahl Puffer (locMax[i]) enthält, die jedem Benutzer zugewiesen werden, und/oder eine Anzahl von privaten Puffern (privMin[i]), die einem Benutzer i zugeordnet werden.

12. Das Verfahren aus Anspruch 11, wobei ein BCR (31.2) ein erstes Feld (UserData) für die physische Adresse des entsprechenden Puffers (30.2) enthält, und ein zweites Feld (next) für einen Zeiger auf einen anderen BCR (31.4) oder einen Flag (nil), der das Ende einer verknüpften Liste markiert.

13. Das Verfahren aus Anspruch 11 oder 12, wobei die Systemstatusvariablen die Anzahl von Puffern enthält, die von dem Benutzer i als benutzte Variable [i] zugewiesen werden, und wobei die Systemstatusvariablen und die benutzerdefinierten Variablen von dem Puffermanager (12) benutzt werden, so daß eine Anforderung eines Benutzers [i] gewährt wird, wenn entweder das benutzte [i] kleiner als privMin[i] ist, oder wenn freie Puffer, die von anderen Benutzern nicht reserviert oder zugewiesen wurden, verfügbar sind, und wenn das benutzte [i] kleiner als locMax [i], und die benutzte Variable [i] erhöht wird, nachdem die Anforderung gewährt wurde, und die benutzte Variable [i] reduziert wird, nachdem ein Puffer freigegeben worden ist.

14. Das Verfahren aus Anspruch 13, wobei die freien Puffer organisiert werden, so daß die Puffer erscheinen, um in einem Kellerspeicher gespeichert zu werden, indem die entsprechenden BCRs in dieser verknüpften Liste des freien Puffers behalten werden, und wobei ein Zeiger (top) auf den BCR oben in der verknüpften Liste des zugewiesenen Puffers zeigt, und ein Flag (nil) ihr Ende anzeigt.

15. Das Verfahren aus Anspruch 14, wobei ein freier Puffer aus diesem Kellerspeicher ausgespeichert wird, indem die physische Adresse des freien Puffers, der dem BCR entspricht und auf den der Zeiger (top) gerichtet ist, dem Benutzer zur Verfügung steht, und indem dieser Zeiger (top) geändert wird, so daß er auf den nächsten BCR der verknüpften Liste des freien Puffers zeigt, indem die Adresse des nächsten BCR kopiert wird, indem diese in dem zweiten Feld des BCR in dem Zeiger (top) gespeichert wird.