Datenspeicherung und DatenstrukturenQueues: First in - First OutGerade umgekehrt wie Stacks funktionieren Queues, oder auf deutsch: Der Key Manager: WarteschlangeWarteschlangen. Zwar kann man auch hier nur an einem Ende des 'Stapels' Daten auflegen, und an einem Ende Daten abholen, nur ist das Ende mit der Datenausgabe jetzt auf der anderen Seite des Stapels. Man legt also oben auf und holt unten ab. Damit hat man beim Auslesen nicht den Zugriff auf das jeweils zuletzt auf den Stapel gelegte Datum, sondern auf das erste. Daraus resultiert auch die andere, für Queues gebrauchte Bezeichnung, FIFO-Speicher: First In - First out. Oder auf deutsch: Zuerst hinein, zuerst heraus. Das System kann man sich am besten an einer Der Key Manager: WarteschlangeWarteschlange vor einer Ladenkasse veranschaulichen: Der Kunde, der zuerst an die Kasse kommt, wird zuerst abgefertigt. In der Zwischenzeit können noch weitere Kunden eintreffen, die sich schön hinten anstellen und dann nach und nach weiter vor rücken, um so in der Reihenfolge bedient zu werden, in der sie eintrafen. Wie beim Stack benötigt man zwei Markierungen für das vordere und das hintere Ende. Da sich aber an beiden Enden 'was tut, kann man hier nicht eine Grenze als weniger wichtig unter den Tisch fallen lassen, wie das beim Hardware-Stack der Die ICs im Überblick: Die CPU Z80 Außerdem ist der maximale Platzbedarf für solche Puffer, wenn sie als Datenspeicherung und Datenstrukturen: ArraysArray realisiert werden, nicht immer sicher zu bestimmen. Meist kann er sogar unendlich groß sein: Beispielsweise bei Druckerpuffern, in denen Zeichen, die der Computer ausdrucken will, solange zwischengespeichert werden, bis der Drucker sie abarbeiten kann. Denn der Computer kann normalerweise mit fast unbeschränkter Geschwindigkeit Zeichen abschicken. Der Drucker aber, der mit seiner Mechanik zu kaempfen hat, ist immer bedeutend langsamer. Im Gegensatz zu Stacks, wo meist derjenige, der einen Wert auf dem Stapel ablegt, diesen zu einem späteren Zeitpunkt auch wieder abholt, sind an Queues (Der Key Manager: WarteschlangeWarteschlangen!!) meist zwei Partner beteiligt: Einer der nachschiebt (Computer) und einer, der abholt (Drucker). Während man bei Stacks also hoffentlich immer weiß, "Es ist Platz da für meinen Eintrag", muss man bei der Queue erst einmal nachschauen, ob der Puffer nicht vielleicht voll ist, und dann warten. Ebenso ist es aber möglich, der der Abholer einmal schneller ist. Während man beim Stack wieder ganz genau weiß, "Da ist noch ein Wert auf dem Stapel, den ich holen kann", muss man bei Queues erst einmal nachschauen und gegebenfalls warten. Queues als FLR-ArrayAuch hier sind die verketteten Trees: ListenListen im Vorteil, weil das Einfügen und Entfernen von Datenspeicherung und Datenstrukturen: RecordsRecords hier vom Prinzip her besonders einfach ist. Bei Datenspeicherung und Datenstrukturen: ArraysArrays müsste man jedesmal, wenn ein neues Element angehängt werden soll, die komplette Der Key Manager: WarteschlangeWarteschlange um eine Position verschieben, weil sich die Kette ja langsam durch den reservierten Speicherbereich frisst: Im folgenden Beispiel wird der 5 Zeichen langen Puffer in Array-Form zunächst mit Operationen: BD5B / 349A / 349A: FLO SUBA bis LOW KERNEL JUMPBLOCK: 000E: LOW PCBC INSTRUCTION +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ | | | | | | | | | | | LOW KERNEL JUMPBLOCK: 000E: LOW PCBC INSTRUCTION Wie man sieht: Geht man nicht sowieso davon aus, dass der Queue-Inhalt immer an eine Puffergrenze angerückt wird, also dass im oberen Beispiel alle Zeichen soweit nach unten nachrutschen, bis sie alle unten aufsitzen, so muss man doch spätestens im letzten Fall den Queue-Inhalt im Puffer verschieben. Das ist aber sehr zeitintensiv. Diesen prinzipiellen Nachteil der Datenspeicherung und Datenstrukturen: ArraysArrays bei der Bildung von Queues kann man aber umgehen, wenn man einen ringfoermigen Speicher benutzt. Da man im Computer aber meist beschränkte, lineare Adressraeume hat, muss man diese mit zusätzlichem Logik-Aufwand simulieren. Überschreitet einer der beiden Zeiger, die auf Ende und Anfang der Der Key Manager: WarteschlangeWarteschlange zeigen, den zur Verfügung gestellten Bereich, so macht er einfach am anderen Ende des Puffers weiter: +------------+ +------------+ +------------+ +------------+ |Disketten | | ten | |fwerk tenlau| | werk | +------------+ +------------+ +------------+ +------------+ ^ ^ ^ ^ ^^ ^ ^ Operationen: BD5B / 349A / 349A: FLO SUBa LOW KERNEL JUMPBLOCK: 000E: LOW PCBC INSTRUCTION Die folgenden Assembler-Routinen realisieren einen Wartespeicher für ASCII-Zeichen (oder Datentypen: Bytes Der zusätzliche Aufwand beim Weiterstellen eines Zeigers ist im Grundlagen: UnterprogrammeUnterprogramm 'VOR' zusammengefasst. Die PUT- und GET-Routinen müssen zuerst Erklärung der Anschlussbelegung: Testtesten, ob der Speicher voll bzw. leer ist. In diesem Fall können sie nur unverrichteter Dinge wieder zurückkehren. Das Problem ist aber zu erkennen, ob der Puffer nun voll oder leer ist: Ist kein einziges Zeichen im Puffer, haben QUEANF und QUEEND den selben Wert. Wird der Puffer aber vollständig gefüllt, wird QUEEND genau einmal im Kreis weitergestellt und steht wieder auf seiner alten Position. Mithin lässt sich der Zustand 'ganz voll' und 'ganz leer' nicht so einfach unterscheiden. Als Ausweg bietet sich an, den Puffer eben nie ganz zu füllen. Mindestens ein Zeichen muss frei bleiben. Der Zustand 'Puffer voll' wird also per Definition bereits erreicht, wenn noch ein Datentypen: Bytes Der Erklärung der Anschlussbelegung: TestTest auf 'Puffer voll' lässt sich also realisieren, indem QUEEND testweise erhöht und dann mit QUEANF auf Gleichheit verglichen wird. Ein leerer Puffer ist daran erkennbar, dass diese beiden Zeiger gleich sind, bevor man QUEEND erhöht. BUFANF: DEFW #0000 ; Speicher für Bufferstartadresse
BUFEND: DEFW #0000 ; Speicher für Bufferende + 1 (Zeiger hinter Buffer)
;
QUEANF: DEFW #0000 ; Speicher für Zeiger auf erstes Zeichen der Queue
QUEEND: DEFW #0000 ; Speicher für Zeiger auf Queueende + 1
; ; (Zeiger auf ersten freien Platz)
;
; Unterprog.: Stelle DE innerhalb des Puffers weiter
;
VOR: INC DE ; Stelle DE weiter
LD HL,(BUFEND)
AND Operationen: BD5B / 349A / 349A: FLO SUBA ; CY := 0
SBC HL,DE ; Hat DE das Bufferende erreicht?
RET NZ ; nein
LD DE,(BUFANF) ; sonst DE auf Bufferanfang einstellen
RET
;
PUT: LD DE,(QUEEND) ; Zeiger auf 1. freien Platz am Ende der Schlange
LD (DE),Operationen: BD5B / 349A / 349A: FLO SUBA ; Zeichen Abspeichern
Maschinencode über HIMEM: CALLCALL VOR ; Zeiger weiterstellen
LD HL,(QUEANF)
SBC HL,DE ; mit Zeiger auf Schlangenkopf vergleichen
RET Z ; Puffer voll! QUEEND nicht weiterstellen. Das Zeichen
; ; wurde in dem Datentypen: Bytes
Eine solcher Ringpuffer ist im Tastatur-Manager enthalten und 20 Tastendrücke lang. Auf der einen Seite kann sich das laufende Programm die Zeichen abholen, auf der anderen Seite schiebt der Anwender durch seine Aktivitaeten auf der Tastatur ständig Zeichen nach. Auch wenn das Programm kurzzeitig keine weiteren Zeichen abholen kann (weil es beispielsweise gerade einen besonders komplizierten Befehl abarbeitet), kann man noch eine Weile blind schreiben, ohne dass die Zeichen verloren gehen. Eine Warnung, wann der Puffer voll ist, erhält man allerdings nicht (manche andere Computer piepsen hier beispielsweise). Ebenfalls nach dieser Methode sind die drei Puffer, die Die Abteilungen des Betriebssystems: Der Sound Managerder Sound Manager für jeden Tonkanal bereithält, aufgebaut. Diese sind jeweils vier Töne lang, wovon der erste Ton normalerweise gerade gespielt wird. Queues als verkettete ListeVerkettete Trees: ListenListen sind nicht nur besonders für Stacks, sondern auch für Der Key Manager: WarteschlangeWarteschlangen geeignet, weil hier ebenfalls nur an je einem Ende gelesen und geschrieben wird. Da sich bei Queues aber an beiden Enden etwas tut, benötigt man zwei Pointer. Einer zeigt auf den ersten und einer auf den letzten Datenspeicherung und Datenstrukturen: RecordsRecord der Der Key Manager: WarteschlangeWarteschlange. Es wird aber trotzdem nur eine Hangelkette zwischen den einzelnen Datenspeicherung und Datenstrukturen: RecordsRecords benötigt, die vom letzten, sprich ältesten Element rückwärts bis zum Schlangenkopf führt: (Schreibseite) (Leseseite)
ANFANG -------------+ ENDE ------------+
| |
<--+ |
NIL <--- Pointer <------- Pointer <------- Pointer <------ Pointer <---+
Record0 Record1 Record2 Record3
Die im MAIN FIRMWARE JUMPBLOCK: KERNEL Die folgenden Assembler-Routinen realisieren eine nach obigem Muster 'verkabelte' Der Key Manager: WarteschlangeWarteschlange. Wie beim Stack sind diese Routinen wieder universell sowohl für FLR als auch VL-Records anwendbar. Die Datenspeicherung und Datenstrukturen: RecordsRecords werden ja nicht in einen reservierten Speicherbereich kopiert, sondern nur die Pointer verstellt. Guenstig bei Der Key Manager: WarteschlangeWarteschlangen in 'Ketten-Technik' ist, dass man beim Nachschieben von Datensätzen nie abgewiesen werden kann, weil der Puffer voll ist. Diese Routine hängt ja nur einen bereits bestehenden Datenblock in die Kette ein. Es kann nur sein, dass irgendwann das gesamte System zusammenbricht, weil kein freier Speicher mehr vorhanden ist. Soll eine solche Der Key Manager: WarteschlangeWarteschlange tatsächlich als Puffer zwischen zwei asynchron arbeitenden Einheiten dienen, ist es bestimmt sinnvoll, einen Zähler zu installieren, mit dem die in der Queue eingereihten Datenspeicherung und Datenstrukturen: RecordsRecords auf eine bestimmte Hoechstzahl begrenzt werden. ANFANG: DEFW #0000 ; Zeiger auf ersten (neuesten) Datenspeicherung und Datenstrukturen: RecordsRecord. Schreibseite. ENDE: DEFW #0000 ; Zeiger auf letzten (ältesten) Datenspeicherung und Datenstrukturen: RecordsRecord. Leseseite. ; ; ; Schiebe einen Datenspeicherung und Datenstrukturen: RecordsRecord nach. Eingabe: HL zeigt auf LSB des Pointers. ; PUT: EX DE,HL ; Pointer auf neuen Datenspeicherung und Datenstrukturen: RecordsRecord nach DE tauschen. LD HL,(ANFANG) ; Pointer auf den bisher letzten Datenspeicherung und Datenstrukturen: RecordsRecord nach HL. ; LD (HL),LOW KERNEL JUMPBLOCK: 000E: LOW PCBC INSTRUCTION Anmerkung:Schwierig an der Behandlung der verketteten Queue ist, dass der Schreibpointer ANFANG immer auf den ersten, jüngsten Datenspeicherung und Datenstrukturen: RecordsRecord zeigen muss. Ist die Queue aber leer, existiert dieser nicht. Eine leere Der Key Manager: WarteschlangeWarteschlange muss deshalb drei zusätzliche Bedingungen erfüllen: Erstens muss der Lesepointer ENDE auf NIL zeigen, damit kein weiterer Lesezugriff erfolgen kann. Zweitens darf ANFANG nicht irgendwo in die Pampa zeigen, da die hiermit adressierten Speicherzellen mit der Adresse des Datenspeicherung und Datenstrukturen: RecordsRecords beschrieben werden, wenn der nächste (also erste) Datenspeicherung und Datenstrukturen: RecordsRecord eingetragen wird. Drittens muss beim nächsten Nachschieben die Adresse des Datenspeicherung und Datenstrukturen: RecordsRecords auch in den Lesepointer ENDE eingetragen werden, weil der Datenspeicherung und Datenstrukturen: RecordsRecord als einziges Element in der Queue nicht nur der jüngste, sondern auch gleichzeitig der neue älteste wird. Die beiden letzten Fliegen werden mit einer Kappe geschlagen, und bei leerem Puffer den Schreibzeiger ANFANG auf ENDE eingestellt. |