2.4 Prioritäts-Warteschlangen Viele Anwendungen erfordern, dass wir Elemente mit Schlüssel in Reihenfolge, aber nicht unbedingt in voller Reihenfolge sortiert und nicht unbedingt alle auf einmal. Oft sammeln wir einen Satz von Elementen, dann verarbeiten die mit dem größten Schlüssel, dann vielleicht sammeln mehr Elemente, dann verarbeiten die mit dem aktuellen größten Schlüssel, und so weiter. Ein geeigneter Datentyp in einer solchen Umgebung unterstützt zwei Vorgänge: das Maximum entfernen und einfügen. Ein solcher Datentyp wird als Prioritätswarteschlange bezeichnet. Prioritätswarteschlangen sind durch das Entfernen der Maximal - und Einfügeoperationen gekennzeichnet. Durch die Konvention werden wir die Schlüssel nur mit einer less () Methode vergleichen, wie wir es für die Sortierung getan haben. Wenn also Datensätze doppelte Schlüssel haben können, bedeutet maximum einen Datensatz mit dem größten Schlüsselwert. Um die API zu vervollständigen, müssen wir auch Konstruktoren und einen Test hinzufügen, wenn leere Operation. Für die Flexibilität verwenden wir eine generische Implementierung mit einem generischen Typ Key, der Comparable implementiert. Programm TopM. java ist ein Prioritätswarteschlangen-Client, der ein Befehlszeilenargument M aufnimmt. Liest Transaktionen von der Standard-Eingabe und druckt die M größten Transaktionen aus. Elementare Implementierungen. Die grundlegenden Datenstrukturen, die wir in Abschnitt 1.3 besprochen haben, bieten uns vier unmittelbare Ausgangspunkte für die Implementierung von Prioritätsschlangen. Array-Darstellung (ungeordnet). Vielleicht basiert die einfachste Prioritätswarteschlangenimplementierung auf unserem Code für Pushdown-Stacks. Der Code für das Einfügen in die Prioritätswarteschlange ist derselbe wie für den Push im Stack. Um zu implementieren, entfernen Sie die maximale. Können wir Code wie die innere Schleife der Auswahlart hinzufügen, um das maximale Element mit dem Element am Ende auszutauschen und dann zu löschen, wie wir es mit pop () für Stacks getan haben. Programm UnorderedArrayMaxPQ. java implementiert eine Prioritätswarteschlange mit diesem Ansatz. Array-Darstellung (geordnet). Ein anderer Ansatz besteht darin, Code für insert hinzuzufügen, um größere Einträge um eine Position nach rechts zu verschieben, wodurch die Einträge im Array in der Reihenfolge (wie beim Einfügen von Sortierungen) beibehalten werden. Somit ist das größte Element immer am Ende, und der Code zum Entfernen des Maximums in der Prioritätswarteschlange ist das gleiche wie für den Pop in dem Stapel. Das Programm OrderedArrayMaxPQ. java implementiert mit diesem Ansatz eine Prioritätswarteschlange. Verknüpfte Darstellungen (ungeordnete und umgekehrte Reihenfolge). Ähnlich können wir mit dem Linklistencode für Pushdown-Stacks beginnen, indem wir entweder den Code für pop () ändern, um das Maximum oder den Code für push () zu finden und zurückzusetzen, um Gegenstände in umgekehrter Reihenfolge und den Code für pop () zu halten Unlink und geben Sie das erste (maximale) Element in der Liste zurück. Alle gerade diskutierten elementaren Implementierungen haben die Eigenschaft, daß entweder die Einfügung oder die Entfernen der maximalen Operation im schlimmsten Fall eine lineare Zeitdauer annimmt. Die Suche nach einer Implementierung, bei der beide Operationen garantiert schnell sind, ist eine interessantere Aufgabe, und sie ist das Hauptthema dieses Abschnitts. Heap-Definitionen. Der binäre Heap ist eine Datenstruktur, die die grundlegenden Prioritäts-Warteschlangenoperationen effizient unterstützen kann. In einem binären Heap werden die Elemente in einem Array gespeichert, so dass sichergestellt ist, dass jede Taste größer als (oder gleich) der Tasten an zwei anderen spezifischen Positionen ist. Im Gegenzug muss jeder dieser Schlüssel größer sein als zwei weitere Tasten und so weiter. Diese Reihenfolge ist leicht zu sehen, wenn wir die Schlüssel als in einer binären Baumstruktur mit Kanten von jeder Taste zu den beiden Schlüsseln, die bekannter kleiner zu sein. Definition. Ein binärer Baum ist heap-ordered, wenn der Schlüssel in jedem Knoten größer als (oder gleich) ist die Schlüssel in diesem Knoten zwei Kinder (falls vorhanden). Aussage. Der größte Schlüssel eines heapgeordneten Binärbaums befindet sich im Stammverzeichnis. Wir können die heap-ordering Einschränkung für jeden binären Baum. Es ist jedoch besonders bequem, einen vollständigen Binärbaum zu verwenden, wie der untenstehende. Wir stellen vollständige Binärbäume sequentiell innerhalb eines Arrays dar, indem wir die Knoten mit der ebenen Ordnung setzen. Mit der Wurzel an Position 1, ihre Kinder an den Positionen 2 und 3, ihre Kinder in den Positionen 4, 5, 6 und 7, und so weiter. Definition. Ein binärer Heap ist ein Satz von Knoten mit Schlüsseln, die in einem vollständigen Heap-geordneten Binärbaum angeordnet sind und in einer Reihenfolge in einem Array (nicht unter Verwendung des ersten Eintrags) dargestellt sind. In einem Haufen befindet sich das Elternteil des Knotens in der Position k in der Position k2, und umgekehrt befinden sich die beiden Kinder des Knotens in der Position k in den Positionen 2k und 2k1. Wir können auf und ab reisen, indem wir einfache Arithmetik auf Array-Indizes durchführen : Um den Baum von ak zu bewegen, setzen wir k auf k2, um den Baum zu senken, den wir k auf 2k oder 2k1 setzen. Algorithmen auf Haufen. Wir stellen einen Haufen der Größe N im privaten Array pq der Länge N1 dar, wobei pq0 unbenutzt ist und der Haufen in pq1 bis pqN. Wir greifen auf Schlüssel nur über private Helferfunktionen less () und exch () zu. Die Heap-Operationen, die wir betrachten, indem wir zuerst eine einfache Modifikation durchführen, die die Heap-Bedingung verletzen könnte, und dann durch den Heap reisen, wobei der Heap modifiziert wird, um sicherzustellen, daß die Heap-Bedingung überall erfüllt ist. Wir bezeichnen diesen Prozess als Wiedererwärmung. Oder Wiederherstellen der Heap-Reihenfolge. Bottom-up reheapify (schwimmen). Wenn der Heap-Befehl verletzt wird, weil ein Knoten-Schlüssel größer als der Knoten-Schlüssel ist, dann können wir Fortschritte in Richtung Festlegung der Verletzung durch den Austausch des Knotens mit seinem Elternteil machen. Nach dem Austausch ist der Knoten größer als seine beiden Kinder (einer ist der alte Elternteil und der andere ist kleiner als der alte Elternteil, weil er ein Kind dieses Knotens war), aber der Knoten kann immer noch größer als sein Elternteil sein. Wir können diese Verletzung in der gleichen Weise beheben, und so weiter, bewegen Sie den Haufen, bis wir einen Knoten mit einem größeren Schlüssel oder der Wurzel erreichen. Top-down heapify (Waschbecken). Wenn der Heap-Befehl verletzt wird, weil eine Knotetaste kleiner als eine oder beide Knöpfe der Knotenskinder wird, können wir Fortschritte in Richtung der Festsetzung des Verstoßes durch Austauschen des Knotens mit dem größeren seiner beiden Kinder machen. Dieser Schalter kann zu einer Verletzung des Kindes führen wir diesen Verstoß auf die gleiche Weise und so weiter, bewegen sich den Haufen, bis wir einen Knoten mit beiden Kindern kleiner oder der Unterseite erreichen. Heap-basierte Prioritätswarteschlange. Diese sink () - und swim () - Operationen bilden die Grundlage für die effiziente Implementierung der API für die Prioritätswarteschlange, wie unten dargestellt und in MaxPQ. java und MinPQ. java implementiert. Einfügen. Wir addieren das neue Element am Ende des Arrays, erhöhen die Größe des Heaps und schwimmen dann durch den Heap mit diesem Item, um die Heap-Bedingung wiederherzustellen. Entfernen Sie das Maximum. Wir nehmen das größte Element von der Spitze, legen Sie das Element vom Ende des Haufens an der Spitze, dekrementieren die Größe des Haufens, und dann sinken Sie durch den Haufen mit diesem Element, um die Heap-Zustand wiederherzustellen. Aussage. In einer N-Item-Prioritätswarteschlange benötigen die Heap-Algorithmen nicht mehr als 1 lg N für einen Vergleich und nicht mehr als 2 lg N zum Vergleichen des Maximums. Praktische Überlegungen. Wir schließen unsere Studie der Heap-Priorität Warteschlange API mit ein paar praktische Überlegungen. Mehrfachhaufen. Es ist nicht schwierig, unseren Code zu modifizieren, um Haufen zu erstellen, basierend auf einer Array-Repräsentation von kompletten, heapgeordneten ternären oder d-armen Bäumen. Es gibt einen Kompromiß zwischen den niedrigeren Kosten von der reduzierten Baumhöhe und den höheren Kosten für das Finden der größten der drei oder d Kinder an jedem Knoten. Größenänderung des Arrays. Wir können einen no-Argument-Konstruktor, Code für die Arrayverdopplung in insert () hinzufügen. Und Code für die Array-Halbierung in delMax (). Genauso wie bei den Stapeln in Abschnitt 1.3. Die logarithmischen Zeitgrenzen werden amortisiert, wenn die Größe der Prioritätswarteschlange beliebig ist und die Arrays die Größe ändern. Unveränderlichkeit der Tasten. Die Prioritätswarteschlange enthält Objekte, die von Clients erstellt werden, setzt aber voraus, dass der Clientcode die Schlüssel nicht ändert (was die Heap-Invarianten ungültig machen könnte). Index-Prioritätswarteschlange. In vielen Anwendungen ist es sinnvoll, Clients auf Elemente zu verweisen, die sich bereits auf der Prioritätswarteschlange befinden. Eine einfache Möglichkeit, dies zu tun, ist die Zuordnung eines eindeutigen Integer-Index mit jedem Element. IndexMinPQ. java ist eine Heap-basierte Implementierung dieser API IndexMaxPQ. java ist ähnlich, aber für maximal orientierte Priorität Warteschlangen. Multiway. java ist ein Client, der mehrere sortierte Eingangsströme in einen sortierten Ausgangsstrom zusammenführt. Wir können jede Prioritätswarteschlange verwenden, um eine Sortiermethode zu entwickeln. Wir setzen alle Schlüssel ein, die in eine minimal orientierte Prioritätswarteschlange zu sortieren sind, und dann wiederholt das Minimum entfernen, um sie alle in der Reihenfolge zu entfernen. Wenn Sie einen Heap für die Prioritätswarteschlange verwenden, erhalten wir heapsort. Wenn wir uns auf die Aufgabe der Sortierung konzentrieren, verlassen wir die Vorstellung, die Heap-Darstellung der Prioritätswarteschlange zu verstecken und benutzen Sie swim () und sink () direkt. Auf diese Weise können wir ein Array sortieren, ohne dass zusätzlicher Speicherplatz benötigt wird, indem der Heap innerhalb des zu sortierenden Arrays beibehalten wird. Heapsort bricht in zwei Phasen ein: Haufenbau. Wo wir das ursprüngliche Array zu einem Heap reorganisieren und die Sortierung. Wo wir die Elemente aus dem Haufen in absteigender Reihenfolge ziehen, um das sortierte Ergebnis zu erstellen. Haufenbau. Wir können diese Aufgabe in Zeit proportional zu N lg N, indem wir von links nach rechts durch das Array, mit swim (), um sicherzustellen, dass die Einträge auf der linken Seite des Scan-Zeiger einen heap-geordneten kompletten Baum, wie sukzessive Prioritätswarteschlangeneinfügungen. Eine clevere Methode, die viel effizienter ist, von rechts nach links, mit sink (), um Unterhaufen zu machen, wie wir gehen. Jede Position im Array ist die Wurzel eines kleinen Subheap-Sink () funktioniert oder solche Subheaps, wie gut. Wenn die beiden Kinder eines Knotens Haufen sind, macht das Aufrufen von sink () auf diesem Knoten den Teilbaum, der dort einen Haufen verwurzelt hat. Sortierung. Der Großteil der Arbeit während der Heapsort wird während der zweiten Phase durchgeführt, wo wir die größten verbleibenden Elemente aus dem Haufen entfernen und sie in die Array-Position leeren, wenn der Haufen schrumpft. Heap. java ist eine vollständige Implementierung von heapsort. Unten ist eine Spur des Inhalts des Arrays nach jeder Senke. Aussage. Senken-basierte Heap-Konstruktion ist lineare Zeit. Aussage. Heapsort-Benutzer weniger als 2n lg n vergleichen und tauschen zu sort n Elemente. Die meisten Gegenstände reinsert in den Heap während der Sortierung gehen den ganzen Weg nach unten. Wir können dadurch Zeit sparen, indem wir die Überprüfung vermeiden, ob das Element seine Position erreicht hat, indem wir einfach das größere der beiden Kinder fördern, bis der Boden erreicht ist, und dann den Haufen wieder in die richtige Position bringen. Diese Idee schneidet die Zahl der Vergleiche um den Faktor 2 zu Lasten der zusätzlichen Buchhaltung. Angenommen, die Sequenz (wobei ein Buchstabe bedeutet einfügen und ein Sternchen das Maximum entfernen) wird auf eine anfänglich leere Prioritätswarteschlange angewendet. Geben Sie die Sequenz der zurückgegebenen Werte an, indem Sie die maximalen Operationen entfernen. Lösung. R............................................................. Lösung. Muss den maximalen Wert von scratch nach einem Remove-the-Maximum-Vorgang aktualisieren. Bereitstellen von Prioritätswarteschlangenimplementierungen, die das Einfügen unterstützen und das Maximum entfernen. Eine für jede der folgenden zugrunde liegenden Datenstrukturen: ungeordnetes Array, geordnetes Array, ungeordnete verkettete Liste und geordnete verkettete Liste. Geben Sie für jede der vier Implementierungen aus der vorherigen Übung eine Tabelle der Worst-Case-Schranken für jede Operation an. Teilweise Lösung. OrderedArrayMaxPQ. java und UnorderedArrayMaxPQ. java Ist ein Array, das in absteigender Reihenfolge ein max-orientiertes Heap sortiert wird. Antworten. Ja. Angenommen, Ihre Anwendung wird eine große Anzahl von Insert-Operationen haben, aber nur wenige entfernen Sie die maximale Operationen. Welche Prioritäts-Warteschlangen-Implementierung meinst du, wäre am effektivsten: heap, ungeordnetes Array, geordnetes Array Antwort. Ungeordnetes Array. Insert ist konstante Zeit. Angenommen, Ihre Anwendung wird eine große Anzahl von finden die maximale Operationen haben, aber eine relativ kleine Anzahl von Insert und entfernen Sie die maximale Operationen. Welche Prioritätswarteschlangen-Implementierung meinst du, wäre am effektivsten: heap, ungeordnetes Array, geordnetes Array Antwort. Sortiertes Array. Das Maximum ist die konstante Zeit. Was ist die minimale Anzahl von Elementen, die ausgetauscht werden müssen während eines Entfernens die maximale Operation in einem Haufen der Größe N ohne doppelte Schlüssel Geben Sie einen Haufen der Größe 15, für die das Minimum erreicht wird. Beantworten Sie die gleiche Frage für zwei und drei sukzessive entfernen Sie die maximale Operationen. Teilweise Antwort. (A) 2. Entwerfen Sie einen Linearzeit-Zertifizierungsalgorithmus, um zu überprüfen, ob ein Array pq ein min-orientierter Heap ist. Lösung. Siehe die Methode isMinHeap () in MinPQ. java. Beweisen, dass Senken-basierte Heap-Konstruktion verwendet höchstens 2 n vergleicht und am meisten n Austäusche. Lösung. Es genügt, zu beweisen, dass Senken-basierte Heap-Konstruktion weniger als n Austäusche verwendet, da die Anzahl der Vergleiche höchstens das Zweifache der Anzahl von Austäuschen beträgt. Der Einfachheit halber sei angenommen, daß der binäre Haufen vollkommen ist (d. h. ein binärer Baum, in dem jede Ebene abgeschlossen ist) und die Höhe h hat. Wir definieren die Höhe eines Knotens in einem Baum als Höhe des Teilbaums, der an diesem Knoten verwurzelt ist. Ein Schlüssel in der Höhe k kann mit höchstens k Schlüsseln unter ihm ausgetauscht werden, wenn er versenkt wird. Da es 2 h minus k Knoten in der Höhe k gibt. Die Gesamtzahl der Austausche ist höchstens: Die erste Gleichheit ist für eine nichtstandardisierte Summe, aber es ist einfach zu überprüfen, ob die Formel über die mathematische Induktion gilt. Die zweite Gleichheit gilt, weil ein perfekter binärer Baum der Höhe h 2 h 1 minus 1 Knoten hat. Der Nachweis, dass das Ergebnis gilt, wenn der binäre Baum nicht perfekt ist erfordert ein bisschen mehr Pflege. Sie können dies mit der Tatsache, dass die Anzahl der Knoten in der Höhe k in einem binären Heap auf n Knoten ist höchstens ceil (n 2 k 1). Alternative Lösung. Wiederum der Einfachheit halber sei angenommen, daß der binäre Haufen perfekt ist (d. h. ein binärer Baum, in dem jede Ebene abgeschlossen ist). Wir definieren die Höhe eines Knotens in einem Baum als Höhe des Teilbaums, der an diesem Knoten verwurzelt ist. Zuerst beobachte, dass ein binärer Heap auf n Knoten n minus 1 Links hat (weil jede Verknüpfung das übergeordnete Element eines Knotens ist und jeder Knoten eine übergeordnete Verknüpfung außer dem Stammverzeichnis hat). Sinking einen Knoten der Höhe k erfordert höchstens k Austäusche. Wir werden k Verbindungen zu jedem Knoten in der Höhe k aufladen. Aber nicht notwendigerweise die Verbindungen auf dem Weg, der genommen wird, wenn der Knoten versenkt wird. Stattdessen laden wir den Knoten auf, der die k-Verknüpfungen entlang des Pfads von dem Knoten, der links-rechts-rechts-rechts-verläuft, verknüpfen. Zum Beispiel, in dem Diagramm unten, wird der Wurzelknoten die vier roten Verbindungen aufgeladen, wobei der blaue Knoten die 3 blauen Verbindungen und so weiter aufgeladen wird. Beachten Sie, dass keine Verbindung zu mehr als einem Knoten geladen wird. (In der Tat gibt es zwei Links, die nicht zu einem Knoten geladen werden: die rechte Verbindung von der Wurzel und der übergeordneten Verknüpfung von dem unteren rechten Knoten.) Somit ist die Gesamtzahl der Vermittlungen höchstens n. Da es höchstens 2 Vergleiche pro Austausch gibt, beträgt die Anzahl der Vergleiche höchstens 2 n. Kreative Probleme Rechnerische Zahlentheorie. Schreiben Sie ein Programm CubeSum. java, das alle ganzen Zahlen des Formulars a 3 b 3 ausgibt, wobei a und b ganze Zahlen zwischen 0 und N in sortierter Reihenfolge sind, ohne übermäßigen Speicherplatz zu verwenden. Das heißt, anstatt ein Array der N 2 Summen zu berechnen und zu sortieren, baut man eine minimal orientierte Prioritätswarteschlange, die anfänglich (0 3 0, 0), (1 3 1, 0), (2 3 2 , 0). (N & sub3; N, 0). Wenn die Prioritätswarteschlange nicht leer ist, entfernen Sie das kleinste Element (i 3 j 3 i, j), drucken Sie es aus, und dann, wenn j 3 (j1) 3. i, j1). Verwenden Sie dieses Programm, um alle verschiedenen ganzen Zahlen a, b, c und d zwischen 0 und 106 zu finden, so dass ein 3 b 3 c 3 d 3 z. 1729 93 103 13 123. Finden Sie das Minimum. Fügen Sie eine min () - Methode zu MaxPQ. java hinzu. Ihre Umsetzung sollte mit konstanter Zeit und konstanten zusätzlichen Platz. Lösung. Fügen Sie eine zusätzliche Instanzvariable hinzu, die auf die minimale Position verweist. Aktualisieren Sie es nach jedem Aufruf von insert (). Setzen Sie es auf Null zurück, wenn die Prioritätswarteschlange leer wird. Dynamisch-medianer Befund. Entwerfen Sie einen Datentyp, der das Einfügen in logarithmischer Zeit unterstützt, den Median in konstanter Zeit finden und den Median in logarithmischer Zeit entfernen. Lösung. Halten Sie den Medianschlüssel in v einen max-orientierten Heap für Schlüssel kleiner als der Schlüssel von v verwenden ein min-orientierte Heap für Schlüssel größer als der Schlüssel von v. Um einzufügen, fügen Sie den neuen Schlüssel in den entsprechenden Heap, ersetzen v mit Wobei der Schlüssel aus diesem Haufen extrahiert wird. Untergrenze. Beweisen, dass es unmöglich ist, eine Implementierung der MinPQ-API zu entwickeln, so dass beide einfügen und löschen die Mindestgarantie für die Verwendung von N log log N vergleicht. Lösung. Dies würde zu einem N log log N Vergleichsbasierten Sortieralgorithmus führen (die N Elemente einfügen, dann das Minimum wiederholt entfernen), wodurch der Satz von Abschnitt 2.3 verletzt wird. Index-Prioritäts-Warteschlangen-Implementierung. Implementieren Sie IndexMaxPQ. java durch Ändern von MaxPQ. java wie folgt: Ändern Sie pq, um Indizes zu halten, fügen Sie eine Array-Schlüssel, um die Schlüsselwerte zu halten, und fügen Sie ein Array qp, das die Umkehrung von pq mdash qpi gibt die Position von i in pq (die So daß pqj i ist). Ändern Sie dann den Code, um diese Datenstrukturen zu pflegen. Verwenden Sie die Konvention, dass qpi -1 ist, wenn i nicht in der Warteschlange ist, und enthalten eine Methode contains (), die diese Bedingung testet. Sie müssen die Hilfsmethoden exch () und less (), aber nicht sink () oder swim () ändern. Web-Übungen Beste, durchschnittliche und schlimmsten Fall von heapsort. Was ist der beste Fall, der durchschnittliche Fall und der ungünstigste Fall der Anzahl der Vergleiche für heapsorting ein Array der Länge N Lösung. Wenn wir Duplikate zulassen, ist der beste Fall lineare Zeit (N gleiche Schlüssel), wenn wir Duplikate nicht zulassen, der beste Fall ist N lg N vergleicht (aber die beste Eingabe ist nicht trivial). Die durchschnittliche und schlechteste Fallzahl von Vergleichen ist 2 N lg N verglichen. Details finden Sie unter Die Analyse von Heapsort. Beste und schlechteste Fall von heapify. Was ist die geringste und die meisten Zahl der Vergleichsexchanges, die benötigt werden, um ein Array von N Elementen zu heapisieren. Das Heapen eines Arrays von N Elementen in absteigender Reihenfolge erfordert 0 Austäusche und N - 1 vergleicht. Heaping ein Array von N Elemente in aufsteigender Reihenfolge erfordert N Börsen und 2N vergleicht. Steuernummern. Finden Sie die kleinsten ganzen Zahlen, die als Summe von Cubes von Ganzzahlen auf zwei verschiedene Arten ausgedrückt werden können (1.729), drei verschiedene Arten (87.539.319), vier verschiedene Wege (6.963.472, 309.248), fünf verschiedene Wege (48.988.659.276.962.496) und sechs verschiedene Wege (24.153.319.581.254.312.065.344 ). Solche Ganzzahlen werden nach der berühmten Ramanujan-Geschichte Taxicab-Nummern genannt. Die kleinsten ganzen Zahlen, die als Summe von Würfeln von ganzen Zahlen auf sieben verschiedenen Wegen ausgedrückt werden können, ist derzeit unbekannt. Schreiben Sie ein Programm Taxicab. java, das in einem Befehlszeilenparameter N liest und alle nicht trivialen Lösungen eines 3 b 3 c 3 d 3 ausgibt, so dass a, b, c und d kleiner oder gleich N sind Zahlentheorie. Finden Sie alle Lösungen für die Gleichung a 2b 2 3c 3 4d 4, für die a, b, c und d kleiner als 100.000 sind. Hinweis. Verwenden Sie einen minimalen Haufen und einen maximalen Haufen. Interruptbehandlung. Bei der Programmierung eines Echtzeitsystems, das unterbrochen werden kann (z. B. durch einen Mausklick oder eine drahtlose Verbindung), ist es notwendig, sofort auf die Interrupts zu achten, bevor die laufende Aktivität fortgesetzt wird. Wenn die Interrupts in derselben Reihenfolge behandelt werden sollen, in der sie ankommen, dann ist eine FIFO-Warteschlange die geeignete Datenstruktur. Wenn jedoch unterschiedliche Interrupts unterschiedliche Prioritäten (z. B.) haben, dann benötigen wir eine Prioritätswarteschlange. Simulation von Warteschlangennetzwerken. MM1-Warteschlange für doppelte parallele Warteschlangen usw. Schwierig, komplexe Warteschlangen-Netzwerke mathematisch zu analysieren. Verwenden Sie stattdessen Simulation, um die Verteilung von Wartezeiten usw. zu verteilen. Benötigen Sie eine Prioritätswarteschlange, um zu bestimmen, welches Ereignis als nächstes zu verarbeiten ist. Zipf Verteilung. Verwenden Sie das Ergebnis der vorhergehenden Übung (en), um aus der Zipfian-Verteilung mit den Parametern s und N abzutasten. Die Verteilung kann ganzzahlige Werte von 1 bis N annehmen und nimmt den Wert k mit der Wahrscheinlichkeit 1ks sum (i 1 bis N) 1is an . Beispiel: Wörter in Shakespeares spielen Hamlet mit s etwa gleich 1. Random-Prozess. Beginnen Sie mit N Bins, jeweils bestehend aus einer Kugel. Wählen Sie nach dem Zufallsprinzip eine der N Kugeln aus und bewegen Sie den Ball so zufällig in einen Behälter, dass die Wahrscheinlichkeit, dass eine Kugel in einen Behälter mit m Kugeln gelegt wird, mN ist. Was ist die Verteilung der Kugeln, die nach vielen Iterationen resultiert Verwenden Sie die zufällige Stichprobenmethode, die oben beschrieben wurde, um die Simulation effizient zu machen. Nächste Nachbarn. Gegebene N Vektoren x 1. X 2. X N der Länge M und einem anderen Vektor x der gleichen Länge, finden Sie die 20 Vektoren, die am nächsten zu x sind. Kreis auf einem Stück Papier gezeichnet. Schreiben Sie ein Programm, um den Radius eines Kreises zu finden, zentriert auf dem Ursprung, der 32 Punkte mit ganzzahligen x - und y-Koordinaten berührt. Hinweis: Suchen Sie nach einer Zahl, die sich als Summe aus zwei Quadraten auf verschiedene Weise ausdrücken lässt. Antwort: Es gibt zwei pythagoreische Tripel mit Hypotenuse 25: 152 202 252, 72 242 252 mit 20 solcher Gitterpunkte gibt es 22 verschiedene Pythagoreische Tripel mit Hypotenuse 5,525, was zu 180 Gitterpunkten führt. 27.625 ist der kleinste Radius, der mehr als 64 berührt. 154.136.450 hat 35 pythagoreische Tripel. Vollkommene Kräfte. Schreiben Sie ein Programm PerfectPower. java, um alle perfekten Potenzen auszudrucken, die als 64-Bit lange Integer dargestellt werden können: 4, 8, 9, 16, 25, 27. Eine perfekte Power ist eine Zahl, die als ab für ganze Zahlen geschrieben werden kann Und b ge 2. Gleitpunktzusätze. Addieren Sie N Gleitkommazahlen, vermeiden Sie Rundungsfehler. Löschen Sie kleinste zwei: addieren Sie zwei gegenseitig und reinsert. First-fit für Abfalleimer. 1710 OPT 2, 119 OPT 4 (abnehmend). Verwenden Sie max Turnierbaum, in dem Spieler sind N Bins und Wert verfügbar Kapazität. Stapel mit minmax. Entwerfen Sie einen Datentyp, der push, pop, size, min und max unterstützt (wobei min und max die minimalen und maximalen Elemente auf dem Stack sind). Alle Operationen sollten im schlimmsten Fall eine konstante Zeit in Anspruch nehmen. Hinweis: Ordnen Sie jedem Stapeleintrag die minimalen und maximalen Gegenstände zu, die sich aktuell auf dem Stapel befinden. Warteschlange mit minmax. Entwerfen Sie einen Datentyp, der enqueue, dequeue, size, min und max unterstützt (wobei min und max die minimalen und maximalen Elemente in der Warteschlange sind). Alle Operationen sollten eine konstante Amortisationszeit einnehmen. Hinweis: führen Sie die vorherige Übung durch und simulieren Sie eine Warteschlange mit zwei Stapeln. 2i 5j. Nummern der Form 2i 5j in aufsteigender Reihenfolge ausgeben. Min-Max-Heap. Entwerfen Sie eine Datenstruktur, die min und max in konstanter Zeit unterstützt, einfügen, löschen min und löschen Sie max in logarithmischer Zeit, indem Sie die Elemente in ein einzelnes Array der Größe N mit den folgenden Eigenschaften setzen: Das Array stellt einen vollständigen binären Baum dar. Der Schlüssel in einem Knoten auf einer ebenen Ebene ist kleiner als (oder gleich) der Schlüssel in seinem Teilbaum der Schlüssel in einem Knoten auf einer ungeraden Ebene ist größer als (oder gleich) die Tasten in seinem Teilbaum. Beachten Sie, dass der Maximalwert an der Wurzel gespeichert wird und der Minimalwert in einem der Wurzelkinder gespeichert wird. Min-Max Heaps und Generalized Priority Queues Bereich Mindest-Abfrage. Bei einer Sequenz von N Elementen ist eine Bereichsminimalabfrage von Index i bis j der Index der minimalen Position zwischen i und j. Entwerfen einer Datenstruktur, die die Folge von N Elementen in linearer Zeit vorverarbeitet, um Bereichsminimalabfragen in logarithmischer Zeit zu unterstützen. Beweisen Sie, dass ein vollständiger Binärbaum mit N Knoten genau N2-Blattknoten (Knoten ohne Kinder) hat. Maximale Prioritätswarteschlange mit min. Was ist die Reihenfolge des Wachstums der Laufzeit, um einen minimalen Schlüssel in einem maximal-orientierten binären Heap zu finden. Lösung. Linearmdasht der minimale Schlüssel in irgendeinem der Decke (N2) Blattknoten sein könnte. Maximale Prioritätswarteschlange mit min. Entwerfen Sie einen Datentyp, der insert und remove-the-maximum in logarithmischer Zeit zusammen mit sowohl max als auch min in konstanter Zeit unterstützt. Lösung. Erstellen Sie einen max-orientierten Binärhaufen und speichern Sie den minimalen Schlüssel, der so weit eingefügt wird (der nie erhöht wird, wenn dieser Heap leer wird). Kth größten Element größer als x. Wenn ein maximal orientierter binärer Haufen gegeben ist, entwerfe einen Algorithmus, um zu bestimmen, ob das kth größte Element größer als oder gleich x ist. Ihr Algorithmus sollte in der Zeit proportional zu k laufen. Lösung. Wenn der Schlüssel im Knoten größer oder gleich x ist, rekursiv sowohl den linken Teilbaum als auch den rechten Teilbaum durchsuchen. Stopp, wenn die Anzahl der untersuchten Knoten gleich k ist (die Antwort ist ja) oder es gibt keine weiteren Knoten zu erforschen (nein). Kth kleinste Element in einem min-orientierten binären Heap. Entwerfen Sie einen k-log-k-Algorithmus, um das k-kleinste Element in einem min-orientierten binären Haufen H zu finden, der N Elemente enthält. Lösung. Erstellen Sie einen neuen min-orientierten Haufen H. Wir werden H nicht modifizieren. Fügen Sie die Wurzel von H in H zusammen mit seinem Heap-Index 1 ein. Lösen Sie nun wiederholt das minimale Element x in H und legen Sie in H die beiden Kinder von x aus H ein Das aus H gelöste k-te Element ist das k-kleinste Element in H. Randomisierte Warteschlange. Implementieren Sie eine RandomQueue, so dass jede Operation garantiert maximal logarithmische Zeit zu nehmen. Hinweis. Kann nicht verdoppeln Anordnung. Keine einfache Möglichkeit, mit verknüpften Listen zu lokalisieren ein zufälliges Element in O (1) Zeit. Verwenden Sie stattdessen einen vollständigen Binärbaum mit expliziten Verknüpfungen. FIFO-Warteschlange mit zufälliger Löschung. Implementieren Sie einen Datentyp, der die folgenden Operationen unterstützt: fügen Sie ein Element ein. Löschen Sie das Element, das zuletzt hinzugefügt wurde. Und löschen Sie ein zufälliges Element. Jede Operation sollte (höchstens) logarithmische Zeit im schlimmsten Fall. Lösung. Verwenden Sie einen vollständigen Binärbaum mit expliziten Verknüpfungen, weisen Sie die lange Integer-Priorität i dem i-ten Element zu, das der Datenstruktur hinzugefügt wird. Top k Summen von zwei sortierten Arrays. Gegeben sind zwei sortierte Arrays a und b, jede der Länge N, die größten k Summen der Form ai bj. Hinweis. Mit einer Prioritätswarteschlange (ähnlich dem Taxicab-Problem) können Sie einen O (k log N) - Algorithmus erreichen. Überraschenderweise ist es möglich, dies in O (k) Zeit zu tun, aber der Algorithmus ist kompliziert. Empirische Analyse des Haufenbaus. Empirisch vergleichen Sie die linear-time-bottom-up Heap-Konstruktion gegenüber der naiven linearithmischen Zeit-Top-down-Heap-Konstruktion. Seien Sie sicher, dass es über eine Reihe von Werten von N. LaMarca und Ladner berichten, dass aufgrund der Cache-Lokalität, kann der naive Algorithmus in der Praxis besser als die klügeren Ansatz für große Werte von N (wenn der Haufen nicht mehr passt in der Cache), obwohl letztere viel weniger Vergleiche und Austausch durchführt. Empirische Analyse von Mehrfachhaufen. Empirisch vergleichen Sie die Leistung von 2- 4- und 8-Wege-Haufen. LaMarca und Ladner schlagen mehrere Optimierungen vor, unter Berücksichtigung von Caching-Effekten. Empirische Analyse der Heapsort. Empirisch vergleichen Sie die Leistung von 2- 4- und 8-Wege-Heapsort. LaMarca und Ladner schlagen mehrere Optimierungen vor, unter Berücksichtigung von Caching-Effekten. Ihre Daten zeigen, dass eine optimierte (und abgestimmte) 8-Wege-Heapsort doppelt so schnell sein kann wie die klassische Heapsort. Heapify durch Einfügungen. Nehmen Sie an, dass Sie ein Binärhaufen auf N Tasten durch wiederholtes Einfügen der nächsten Taste in den binären Heap. Zeigen Sie, dass die Gesamtzahl der Vergleiche höchstens die Antwort ist. Die Anzahl der Vergleiche beträgt höchstens lg 1 lg 2. Lg N lg (N) N lg N. Untere Schranke heapify. (Gonnet und Munro) Zeigen Sie, dass jeder vergleichbasierte Algorithmus für den Aufbau eines binären Heaps auf N Schlüssel mindestens 1,3644 N im schlimmsten Fall benötigt. Antworten . Verwenden Sie ein informationstheoretisches Argument, ala Sortierung untere Schranke. Es gibt N mögliche Haufen (Permutation der N ganzen Zahlen) auf N verschiedenen Schlüsseln, aber es gibt viele Haufen, die der gleichen Anordnung entsprechen. Beispielsweise gibt es zwei Haufen (cab und cba), die den 3 Elementen entsprechen. Der Zweck dieses Dokuments ist es, zu beschreiben, wie IOs den Plattengerätetreiber und den Adaptergerätetreiber SDD und SDDPCM in die Warteschlange gestellt werden und wie diese beschrieben werden können Um die Leistung zu steigern. Dazu gehört auch der Einsatz von VIO. Diese Information ist auch nützlich für AIX-LPARs, die auch einen anderen Mehrwegcode verwenden. LVM-Gerätetreiber (optional) SDD oder SDDPCM oder ein anderer Multipfad-Treiber (falls verwendet) hdisk-Gerätetreiber-Adaptergerät Treiber-Verbindung zur Festplatte Disk Subsystem Disk Beachten Sie, dass, obwohl die Festplatte an den Adapter angeschlossen ist, wird der hdisk Treiber-Code vor dem Adapter Treiber-Code verwendet. Somit repräsentiert dieser Stapel die Auftragsoftware, die im Laufe der Zeit ins Spiel kommt, während der IO den Stapel durchquert. Warum müssen wir gleichzeitig mehrere IOs auf eine Festplatte übertragen? Das verbessert die Performance. Und dies wäre eine Leistung aus einer Anwendung Sicht. Dies ist besonders wichtig bei Platten-Subsystemen, bei denen eine virtuelle Festplatte (oder LUN) durch mehrere physische Festplatten unterstützt wird. In solch einer Situation, wenn wir nur ein einzelnes IO auf einmal einreichen konnten, finden wir gute IO Service-Zeiten, aber sehr schlechte thruput. Wenn mehrere IOs auf eine physikalische Festplatte übertragen werden, kann die Festplatte die Aktuatorbewegung (mit Hilfe eines Aufzugalgorithmus) minimieren und mehr IOPS erhalten, als dies möglich ist, indem ein IO zu einem Zeitpunkt gesendet wird. Die Aufzugs-Analogie ist angemessen. Wie lange würden die Leute warten, um einen Aufzug zu bedienen, wenn nur eine Person zu einem Zeitpunkt könnte auf sie zu bekommen In einer solchen Situation erwarten, dass die Menschen eine ganze Weile warten, um den Aufzug (Wartezeit), aber sobald sie auf , Theyd zu ihrem Bestimmungsort schnell (Servicezeit) erhalten. So senden Sie mehrere In-Flight-IOs auf einem Festplatten-Subsystem ermöglicht es, herauszufinden, wie die meisten thruput und schnellste IO-Service-Zeit zu bekommen. Theoretisch ist die IOPS für eine Festplatte durch eine Warteschlangenebene (durchschnittliche IO-Dienstzeit) begrenzt. Unter der Annahme einer Queue-Tiefe von 3 und einer mittleren IO-Servicezeit von 10 ms ergibt sich ein maximaler Thut von 300 IOPS für die hdisk. Und für viele Anwendungen kann dies nicht genug thruput. Wo werden IOs in die Warteschlange gestellt Wenn IOs den IO-Stack durchlaufen, muss AIX diese auf jeder Ebene verfolgen. So IOs sind in der Warteschlange auf jeder Ebene. Im Allgemeinen kann eine Anzahl von Flug-IOs an jeder Schicht ausgegeben werden, und wenn die Anzahl von IO-Anforderungen diese Zahl übersteigt, befinden sie sich in einer Warteschlange, bis die benötigte Ressource verfügbar ist. So gibt es im Wesentlichen eine in Prozess-Warteschlange und eine Warteschlange an jeder Schicht (SDD und SDDPCM sind ein wenig komplizierter). Auf Dateisystemebene beschränken Dateisystempuffer die maximale Anzahl von IOs für jedes Dateisystem. Auf der LVM-Gerätetreiber-Ebene beschränken hdisk-Puffer die Anzahl der Flug-IOs. Auf der SDD-Ebene werden IOs in die Warteschlange gestellt, wenn das dpo-Geräteattribut qdepthenable auf yes gesetzt ist (was es standardmäßig ist). Einige Releases von SDD nicht in der Warteschlange IOs so hängt es von der Freisetzung von SDD. SDDPCM auf der anderen Seite nicht IOs Warteschlange, bevor sie an den Datenträger-Gerätetreiber senden. Die hdisks haben eine maximale Anzahl von IOs, die durch ihr queuedepth-Attribut angegeben werden. Und FC-Adapter haben auch eine maximale Anzahl von Flug-IOs durch numcmdelems angegeben. Die Platten-Subsysteme selbst stellen Warteschlangen-IOs her, und einzelne physikalische Platten können mehrere IO-Anfragen akzeptieren, aber nur einen Service zu einem Zeitpunkt. Hier sind ein ESS hdisks Attribute: lsattr - El hdisk33 PRkeyvalue keine Reserve Key wahre Lage Location Label-Wahr lunid 0x5515000000000000 Logical Unit Number ID Wahr lunresetspt ja Unterstützung SCSI LUN zurückgesetzt Wahr MaxTransfer 0x40000 NA Wahr nodename 0x5005076300c096ab FC Knotenname Falsch pvid keine Physikalische Datenträger-ID Falsch QTYPE TYPE einfache Queuing Wahr qfulldly 20 Verzögerung in Sekunden für SCSI-TASK SET FULL Wahr queuedepth 20 Queue-Tiefe Wahre reservepolicy Singlepath Reserve-Politik Wahre rwtimeout 60 READWRITE Zeit scbsydly 20 Verzögerung Wahrer Wert in Sekunden für SCSI-BUSY Wahr scsiid 0x620713 SCSI-ID Wahr starttimeout 180 START Zeitüberschreitung Wert True wwname 0x5005076300cd96ab FC World Wide Name False Die Standard-Warteschlange ist 20, kann aber für ESS, DS6000 und DS8000 auf bis zu 256 geändert werden. Man kann mit zulässigen Werte angezeigt werden: lsattr - rl hdisk33 - a queuedepth 1. 256 (1) kann den Wert, der angibt überall von 1 bis 256 in Schritten von 1 Man kann diesen Befehl verwenden, jede zulässige Wert für Attribute, um zu sehen, die sein kann, geändert (zeigt den Wert True im letzten Feld von lsattr - El ltdevicegt für das Gerät mit: lsattr - rl ltdevicegt - a ltattributegt Heres ein FC-Adapter-Attribute: lsattr - El fcs0 busintrlvl 65703 Bus Interrupt-Ebene Falsch busioaddr 0xdec00 Bus IO-Adresse Falsch busmemaddr 0xe8040000 Bus Speicheradresse falsch initlink al INIT Link-Flags Wahr intrpriority 3 Interrupt Priorität Falsch lgtermdma 0x800000 Langzeit DMA Wahr maxxfersize 0x100000 Maximum Transfer Größe Wahr numcmdelems 200 Maximale Anzahl von Befehlen an den Adapter Wahre prefalpa 0x1 Bevorzugte ALPA Wahre swfcclass 2 FC Klasse in die Warteschlange . für Fabric True der Standardwarteschlangentiefe (numcmdelems) für FC-Adapter 200 ist, aber für die meisten Adapter auf 2048 erhöht werden Heres die DPO-Geräte-Attribute für eine Freisetzung von SDD: lsattr - El DPO Enterprmaxlun 600 Maximale LUNS für Enterprise-Produkte Wahr erlaubt Virtualmaxlun 512 Maximale LUNS erlaubt für Virtualisierungsprodukte Falsch persistentresv ja Subsystem unterstützt Persistent Reserve-Befehl falsch qdepthenable ja Queue Depth Control wahr, wenn qdepthenableyes, SDD nur einreichen queuedepth IOs einem zugrunde liegenden hdisk (wo queuedepth hier ist der Wert für das Attribut zugrunde liegenden hdisks queuedepth) . Wenn qdepthenableno, SDD nur die IOs direkt an den hdisk-Treiber weitergibt. So ist der Unterschied, wenn qdepthenableyes (Standardeinstellung), IOs die queuedepth überschreiten, werden bei SDD Warteschlange, und wenn qdepthenableno, dann IOs überschreiten die queuedepth Warteschlange wird in die hdisks Warteschlange warten. Mit anderen Worten, SDD mit qdepthenableno und SDDPCM nicht Warteschlangen IOs und stattdessen übergeben sie an die hdisk-Treiber. Beachten Sie, dass bei SDD 1.6 seine bevorzugte Verwendung des Befehls "datapath" verwendet wird, um qdepthenable zu ändern, anstatt chdev zu verwenden, da dann seine dynamische Änderung, z. B. Wird der Datapath-Satz qdepth disable auf nein gesetzt. Einige Versionen von SDD enthalten keine SDD-Warteschlangen, und einige tun, und einige Releases zeigen nicht das Attribut qdepthenable. Überprüfen Sie entweder das Handbuch für Ihre Version von SDD oder versuchen Sie den Datapath-Befehl zu sehen, ob es das Ausschalten dieser Funktion unterstützt. Wenn Sie SDD und SDDPCM verwendet haben, erinnern Sie sich, dass bei SDD jede LUN einen entsprechenden vpath und eine hdisk für jeden Pfad zu vpath oder LUN hat. Und mit SDDPCM, Sie haben nur eine hdisk pro LUN. So kann man mit SDD queuedepth x Pfade zu einer LUN, während mit SDDPCM, kann man nur queuedepth IOs an die LUN. Wenn Sie von SDD mit 4 Pfaden auf SDDPCM umschalten, dann möchten Sie die SDDPCM hdisks auf 4x setzen, die von SDD hdisks für eine äquivalente effektive Queue Tiefe. Und die Migration zu SDDPCM wird als seine strategischer als SDD empfohlen. Sowohl der hdisk als auch der Adapter-Treiber haben eine in Prozess-und Warteschlangen. Sobald die Warteschlangengrenze erreicht ist, warten die IOs, bis ein IO abgeschlossen ist, wodurch ein Steckplatz in der Warteschlange freigegeben wird. Die In-Prozess-Warteschlange wird auch manchmal als Service-Warteschlange bezeichnet. Erwähnenswert, dass viele Anwendungen nicht viele Flug-IOs generieren werden, vor allem einzelne Thread-Anwendungen, die nicht asynchrone IO verwenden. Anwendungen, die asynchrone IO verwenden, sind wahrscheinlich, mehr im Flug IOs zu erzeugen. Welche Tools für die Überwachung der Warteschlangen zur Verfügung stehen Für AIX kann iostat (bei AIX 5.3 oder höher) und sar (5.1 oder höher) verwendet werden, um die Warteschlangen des hdisk-Treibers zu überwachen. Der iostat - D Befehl erzeugt Ausgangs wie: hdisk6 xfer: tmact bps tps Brot bwrtn 4.7 2,2M 19.0 0.0 2.2M lesen: rps avgserv minserv maxserv Timeouts versagt 0,0 0,0 0,0 0,0 0 0 schreiben: wps avgserv minserv maxserv Timeouts fehl 19.0 38.9 1.1 190,2 0 0 Warteschlange: avgtime mintime maxtime avgwqsz avgsqsz sqfull 15,0 0,0 83,7 0,0 0,0 136 Hier ist die avgwqsz die durchschnittliche Wartewarteschlangengröße und avgsqsz ist die durchschnittliche Größe der Warteschlange. Die durchschnittliche Zeit in der Warteschlange verbraucht wird Avgtime. Der sqfull-Wert hat sich von anfänglich ein Zählimpuls der Zeiten geändert, die ein IO zu einer vollen Warteschlange eingereicht hat, bis jetzt, wo seine Rate der IOs pro Sekunde einer vollen Warteschlange unterworfen ist. Der Beispielbericht zeigt den vorherigen Fall (eine Anzahl von IOs, die einer vollständigen Warteschlange übergeben wurden), während neuere Releases typischerweise Dezimal-Fraktionen anzeigen, die eine Rate angeben. Es ist schön, dass iostat - D trennt und liest und schreibt, wie wir erwarten würden, dass die IO-Service-Zeiten anders sein, wenn wir ein Disk-Subsystem mit Cache haben. Der nützlichste Bericht für das Tuning ist nur das Ausführen von iostat - D, das Statistiken seit dem Systemstart anzeigt, vorausgesetzt, dass das System so konfiguriert ist, dass es den Laufwerk-IO-Verlauf kontinuierlich beibehält (führen Sie lsattr - El sys0 oder smitty chgsys aus, um zu sehen, ob das iostat-Attribut auf true gesetzt ist ). Und die Favoriten-iostat-Befehlsflags des Autors sind iostat - RDTl ltintervalgt ltintervalsgt. Aus Sicht der Anwendungen ist die Zeitspanne, in der ein IO ausgeführt wird, seine Dienstzeit plus die Zeit, die er in der hdisk-Warteschlange wartet. Der Befehl sar - d änderte sich bei AIX 5.3 und erzeugt Ausgabe wie: 16:50:59 Gerät beschäftigt avque rws Kbss avwaerv avserv 16:51:00 hdisk1 0 0.0 0 0 0.0 0.0 hdisk0 0 0.0 0 0 0.0 0.0 Die avwait und Avserv sind die durchschnittlichen Zeiten in der Warteschlange bzw. Warteschlange. Und avserv hier entspricht avgserv in der iostat-Ausgabe. Der avque-Wert änderte sich bei AIX 5.3, er repräsentiert die durchschnittliche Anzahl von IOs in der Warteschlange und vor 5.3 stellt er die durchschnittliche Anzahl von IOs in der Warteschlange dar. SDDPCM stellt die Befehle pcmpath query devstats und pcmpath query adaptstats zur Verfügung, um Hdisk - und Adapter-Warteschlangenstatistiken anzuzeigen. SDD hat in ähnlicher Weise Datapath-Abfrage-Devstate und Datenpfad-Abfrage-Adaptstats. Die Syntax, Optionen und Erläuterungen aller Felder finden Sie im SDDSDDPCM-Handbuch. Heres einige devstats Ausgabe für eine einzelne LUN: Gerät: 0 Summe Lesen Insgesamt Schreiben Aktiv Lesen Aktiv Schreiben Maximal IO: 29007501 3037679 1 0 40 SEKTOR: 696124015 110460560 8 0 20480 Transfer Größe: lt 512 lt 4k lt 16K lt 64K gt 64K 21499 10987037 18892010 1335598 809036 und heres einige adaptstats Ausgang: Adapter: 0 Gesamt Lesen Insgesamt Schreiben Aktiv Lesen Aktiv Schreiben Maximum IO: 439690333 24726251 7 0 258 SEKTOR: 109851534 960137182 608 0 108625 Hier waren vor allem das Maximum-Feld interessiert, die die maximale Anzahl von IOs, die seit dem Systemstart an das Gerät gesendet werden. Für SDD wird das Maximum für devstats nicht größer als die queuedepth x Pfade, wenn qdepthenableyes. Aber Maximum für adaptstats kann numcmdelems übersteigen, da es die maximale Anzahl von IOs darstellt, die an den Adaptertreiber übermittelt werden und IOs für die Dienst - und Warteschlangen enthält. Wenn wir in diesem Fall zwei Pfade haben und die Standard-Warteschlange von 20 verwenden, zeigt 40 an, dass die Warteschlange mindestens einmal gefüllt ist, und die Erhöhung der Warteschlange kann die Leistung verbessern. Für SDDPCM, wenn der Maximalwert gleich der hdisks queuedepth ist, wurde die hdisk-Treiberwarteschlange während des Intervalls gefüllt, und die Erhöhung der Warteschlangenepth ist normalerweise angemessen. Man kann ähnlich beobachten Adapter IOPS mit iostat - at ltintervalgt lt von Intervalsgt und für Adapter-Warteschlange Informationen, führen Sie iostat - aD. Wahlweise mit einem Intervall und einer Anzahl von Intervallen. Bei FC-Adaptern enthält der Befehl fcstat Informationen über die Adapterwarteschlange und die Ressourcennutzung und kann uns sagen, ob wir die Warteschlangengrößen erhöhen müssen. Für Adapter-Warteschlangen wird der Befehl fcstat verwendet und wird unten erläutert. Erstens sollte man diese Werte nicht wahllos erhöhen. Es ist möglich, das Disk-Subsystem zu überladen oder Probleme mit der Gerätekonfiguration beim Start zu verursachen. So ist der Ansatz der Addition der hdisks queuedepths und die Verwendung, dass die numcmdelems ist nicht notwendigerweise der beste Ansatz. Stattdessen ist es besser, die maximale Anzahl der übermittelten IOs für jedes Gerät zum Tuning zu verwenden. Wenn Sie die Warteschlangenebenen und die Anzahl der eingehenden IOs, die an das Festplattensubsystem gesendet werden, erhöhen, steigen die IO-Dienstzeiten wahrscheinlich, aber der Durchsatz wird ebenfalls zunehmen. Wenn IO-Dienstzeiten beginnen, sich dem Datenträger-Timeout-Wert zu nähern, übergeben Sie dann mehr IOs, als das Plattensubsystem verarbeiten kann. Wenn Sie IO-Timeouts und Fehler im Fehlerprotokoll sehen, die auf Probleme hinweisen, die IOs abschließen, dann ist dies die Zeit, nach Hardwareproblemen zu suchen oder die Pipe kleiner zu machen. Eine gute allgemeine Regel für das Abstimmen von queuedepths ist, dass man die Warteschlangenee erhöhen kann, bis IO Service-Zeiten mehr als 15 ms für kleine zufällige Lese - oder Schreibvorgänge überschreiten oder eine nicht die Warteschlangen füllt. Sobald IO Service-Zeiten beginnen zu erhöhen, weve drückte den Engpass aus der AIX-Festplatte und Adapter-Warteschlangen auf das Festplatten-Subsystem. Zwei Ansätze zur Abstimmung der Warteschlangen-Tiefe sind 1) Basis der Warteschlangen-Tiefen auf den tatsächlichen IO-Anforderungen Ihrer Anwendung zu generieren oder 2) verwenden Sie ein Test-Tool, um zu sehen, was das Festplatten-Subsystem behandeln und tune die Warteschlangen auf das, was das Festplatten-Subsystem verarbeiten kann. Das ndisk-Tool (Teil des nstress-Pakets im Internet unter www-941.ibmcollaborationwikidisplayWikiPtypenstress) kann verwendet werden, um das Disk-Subsystem zu betonen, um zu sehen, was es behandeln kann. Die Autoren bevorzugen die Abstimmung basierend auf Ihren Anwendungs-IO-Anforderungen, insbesondere wenn der Datenträger mit anderen Servern gemeinsam genutzt wird. Für das Tuning können wir die Situation in vier Kategorien kategorisieren: Wäre das Füllen der Warteschlangen und IOs warten in der hdisk oder Adapter-Treiber Wurden nicht füllen Sie die Warteschlangen und IO Service-Zeiten sind gut Füllen Sie nicht die Warteschlangen und IO-Service Zeiten sind schlecht Wäre nicht füllen Sie die Warteschlangen, und schickten IOs an den Speicher schneller als es zu behandeln und es verliert die IOs Wir wollen die Warteschlangen in beiden Situation 2 oder 3. Wenn in Situation 3, das bedeutet, stimmen Ein Engpass jenseits der hdisk-Treiber, die in der Regel in der Festplatte Subsystem selbst sein, könnte aber auch in den Adapter-Treiber oder SAN-fabric. Situation 4 ist etwas, was wir vermeiden wollen. Alle Platten und Platten-Subsysteme haben Grenzen hinsichtlich der Anzahl von In-Flight-IOs, die sie behandeln können, hauptsächlich aufgrund von Speicherbeschränkungen, um die IO-Anforderung und Daten zu halten. Wenn der Speicher verliert IOs, wird die IO schließlich Time-out auf dem Host, Recovery-Code verwendet werden und erneut einreichen IO, aber in der Zwischenzeit Transaktionen warten, dass IO wird gestoppt werden. Dies ist keine wünschenswerte Situation, da die CPU beendet, mehr Arbeit zu behandeln IOs als notwendig. Wenn die IO schließlich scheitert, dann kann dies zu einer Anwendung abstürzen oder schlimmer führen. Achten Sie also darauf, Ihre Speicherdokumentation zu überprüfen, um ihre Grenzen zu verstehen. Dann nach dem Ausführen Ihrer Anwendung während Peak IO-Perioden Blick auf die Statistiken und Melodie wieder. Was den qdepthenable Parameter für SDD anbetrifft, ist die Rückstellung ja, die im Wesentlichen SDD hat, die die IOs über queuedepth hinaus für die zugrunde liegenden hdisks handhabt. Setzen Sie es auf keine Ergebnisse in den hdisk Gerätetreiber, der sie in seiner Warteschlange behandelt. In anderen Worten, mit qdepthenableyes behandelt SDD die Warteschlange, andernfalls behandelt der hdisk-Gerätetreiber die Warteschlange. Es gibt Fehlerbehandlungsvorteile, damit SDD diese IOs handhaben kann, z. B. Wenn mit LVM-Spiegelung über zwei ESSs. Mit schweren IO-Lasten und einer Menge von Warteschlangen in SDD (wenn qdepthenableyes) seine effizienter zu ermöglichen, dass die hdisk Gerätetreiber verarbeiten relativ kürzere Warteschlangen anstatt SDD Behandlung eine sehr lange Warteschlange durch Festlegen von qdepthenableno. Mit anderen Worten, SDDs Warteschlange Behandlung ist single threaded, wo jeder hdisk-Treiber hat einen eigenen Thread. Wenn also die Fehlerbehandlung von primärer Bedeutung ist (z. B. wenn LVM-Spiegelung über Platten-Subsysteme) dann qdepthenableyes verlassen. Andernfalls verarbeitet qdepthenableno effizienter die Warteschlangen, wenn sie lang sind. Beachten Sie, dass der qdepthenable-Parameter über den Datenpfadbefehl als seine dynamische Änderung auf diese Weise festgelegt werden sollte (wobei chdev für diesen Parameter nicht dynamisch ist). Wenn die Fehlerbehandlung von Bedeutung ist, dann ist es auch ratsam, unter der Annahme, dass der Datenträger mit dem SAN-Switch verbunden ist, das fscsi-Geräteattribut fcerrrecov auf "fastfail" und nicht auf den Standard von delayedfail setzen und auch das dyntrk-Attribut fscsi auf yes umstellen Von Nr. Diese Attribute setzen einen SAN-Switch voraus, der diese Funktion unterstützt. Was sind vernünftige durchschnittliche IO-Servicezeiten Was gut oder vernünftig ist, ist ein gewisser Faktor der Technologie der Speicher - und Speicher-Cache-Größen. Unter der Annahme, dass keine IOs auf einen Datenträger gelegt werden, wird ein typischer Lesevorgang etwa 0 bis 15 ms dauern, je nachdem, wie weit der Aktor reisen muss (Suchzeit), wie lange es dauert, bis sich die Festplatte nach rechts bewegt (Umdrehungszeit) und wie lange es dauert, die Daten zu lesen (Übertragungszeit). Dann müssen die Daten vom Speicher zum Host wechseln. Typischerweise wird die Zeit durch die Suchzeit-Rotationszeit dominiert, obwohl für große IOs auch die Übertragungszeit signifikant sein kann. Manchmal befinden sich die Daten im Disk-Subsystem-Lese-Cache, wobei die IO-Dienstzeit etwa 1 ms beträgt. In der Regel für große Festplatten-Subsysteme, die arent überladen, IO-Service-Zeiten werden durchschnittlich 5-10 ms. Wenn kleine zufällige Lesevorgänge eine Mittelwertbildung von mehr als 15 ms beginnen, zeigt dies an, dass der Speicher besetzt ist. Schreibt typischerweise, um einen Cache zu schreiben (vorausgesetzt, er existiert) und dann diese durchschnittlich weniger als ungefähr 2,5 ms. Aber es gibt Ausnahmen. Wenn der Speicher die Daten synchron zu einem entfernten Standort synchronisiert, können Schreibvorgänge viel länger dauern. Und wenn das IO groß ist (z. B. 64 KB oder größer), dann wird die Übertragungszeit bedeutsamer und die durchschnittliche Zeit ist etwas schlechter. Wenn theres kein Cache, dann schreibt etwa das gleiche wie liest. Wenn der IO-Block sequentiell groß ist, dann erwarten wir neben der erhöhten Übertragungszeit, dass IOs auf der physischen Festplatte anstehen und IO-Dienstzeiten im Durchschnitt wesentlich länger sind. Z. B. Wenn eine Anwendung 50 IOs abgibt (z. B. 50 64 KB IOs, die eine Datei sequentiell lesen), dann haben die ersten IOs recht gute IO-Servicezeiten, während der letzte IO auf die anderen 49 warten musste, um zuerst zu beenden und haben Eine sehr lange IO-Dienstzeit. IOs zu SSDs sind typischerweise weniger als 1 ms und für SSDs in Plattensubsystemen typischerweise weniger als 2 ms und gelegentlich höher. Einstellen des FC-Adapters numcmdelems Der fcstat-Befehl ist vielleicht das einfachste Werkzeug, um blockierte IOs in den Adapter-Warteschlangen zu suchen, z. B. FASERKANAL STATISTIKBERICHT: fcs0. FC SCSI Adapter Treiber-Informationen Keine DMA-Ressourcenanzahl: 0 Keine Adapter-Elementeanzahl: 104848 Keine Befehlsressourcenanzahl: 13915968. Die Werte für No Adapter Elements Count und No Command Resource Count sind die Anzahl der Male seit dem Booten, dass ein IO vorübergehend blockiert wurde aufgrund eines unzureichenden numcmdelems Attributwert. Nicht-Null-Werte zeigen, dass zunehmende numcmdelems dazu beitragen können, IO-Service-Zeiten zu verbessern. Natürlich, wenn der Wert langsam ansteigt, dann kann die Verbesserung sehr klein sein, während schnell inkrementierende Werte bedeutet, dass das Tuning eher eine messbare Leistungsverbesserung aufweist. Das Ändern des Wertes numcmdelems erfordert, wie das Attribut hdisk queuedepth, das Stoppen der Ressourcen oder einen Neustart. Queue-Tiefen mit VSCSI VIO Bei der Verwendung von VIO konfiguriert man VSCSI-Adapter (für jeden virtuellen Adapter in einem VIOS, bekannt als VHost-Gerät, gibt es einen passenden VSCSI-Adapter in einem VIOC). Diese Adapter haben eine feste Warteschlangen-Tiefe, die abhängig davon variiert, wie viele VSCSI-LUNs für den Adapter konfiguriert sind. Es gibt 512 Befehlselemente, von denen 2 vom Adapter verwendet werden, 3 für jede VSCSI-LUN für die Fehlerbehebung reserviert sind und der Rest für IO-Requests verwendet wird. Mit der Standard-Warteschlange von 3 für VSCSI-LUNs können somit bis zu 85 LUNs einen Adapter verwenden: (512 - 2) (3 3) 85 Abrunden. Wenn wir also höhere Warteschlangentiefen für die Geräte benötigen, wird die Anzahl der LUNs pro Adapter reduziert. Z. B. Wenn wir eine queuedepth von 25 verwenden möchten, die 51028 18 LUNs erlaubt. Wir können mehrere VSCSI-Adapter für viele LUNs mit hohen Warteschlangentiefen konfigurieren. Die jeweils einen zusätzlichen Speicher benötigen. Möglicherweise haben Sie mehr als einen VSCSI-Adapter auf einem VIOC, das mit demselben VIOS verbunden ist, wenn Sie mehr Bandbreite benötigen. Außerdem sollte man das queuedepth-Attribut auf die VIOCs-hdisk setzen, damit es mit dem der abgebildeten hdisks queuedepth auf dem VIOS übereinstimmt. Für eine Formel ist die maximale Anzahl von LUNs pro virtuellem SCSI-Adapter (vhost auf dem VIOS oder vscsi auf dem VIOC) INT (510 (Q3)), wobei Q die Warteschlangenlänge aller LUNs ist (vorausgesetzt sie sind alle gleich). Man beachte, dass die queuedepth auf einem hdisk am VIOS zu ändern erfordert, dass wir die Diskette aus dem VIOC unmap und Neuzuordnung es zurück, oder ein einfacher Ansatz ist es, die Werte in der ODM zu ändern (zB chdev - l hdisk30 - a queuedepth20 - P) Dann das VIOS neu starten. Für LV-VSCSI-hdisks, bei denen mehrere VIOC-hdisks aus einer einzigen VIOS-hdisk erstellt werden, kann man eine dedizierte Ressource, eine freigegebene Ressource oder eine zwischen den VIOS-hdisk-Warteschlangen-Slots angeordnete Schnittstelle verwenden. Siehe den folgenden Abschnitt mit dem Titel Weitere theoretische Gedanken über gemeinsame und dedizierte Ressourcen. Queue-Tiefen mit NPIV VIO Bei der Verwendung von NPIV haben wir virtuelle FC-Adapter (vFC) und echte FC-Adapter und haben oft mehrere vFCs, die an einen einzelnen Real-FC-Adapter gebunden sind. Wenn Sie numcmdelems auf dem virtuellen FC (vFC) Adapter erhöhen, sollten Sie auch die Einstellung auf dem realen FC Adapter erhöhen. Sie können den Befehl fcstat sowohl für den virtuellen Adapter als auch den echten Adapter für Abstimmzwecke verwenden. Eine spezielle Notiz auf dem FC-Adapter maxxsize-Attribut Dieses Attribut für das fscsi-Gerät, das die maximale IO-Größe steuert, die der Adaptergerätetreiber behandelt, steuert auch einen Speicherbereich, der von dem Adapter für Datenübertragungen verwendet wird. Wenn der Standardwert verwendet wird (maxxfersize0x100000), ist der Speicherbereich 16 MB groß. Wenn Sie dieses Attribut auf einen anderen zulässigen Wert (zB 0x200000) setzen, dann ist der Speicherbereich 128 MB groß. Bei AIX 6.1 TL2 oder höher wurde eine Änderung für virtuelle FC-Adapter vorgenommen, so dass der DMA-Speicherbereich immer 128 MB beträgt, auch wenn die Standard-Maximalgröße gilt. Dieser Speicherbereich ist ein DMA-Speicherbereich, aber er ist anders als der DMA-Speicherbereich, der durch das lgtermdma-Attribut (das für die IO-Steuerung verwendet wird) gesteuert wird. Der Standardwert für lgtermdma von 0x800000 ist normalerweise ausreichend. Also für schwere IO und vor allem für große IOs (wie für Backups) ist es empfehlenswert, maxxfersize0x200000 setzen. Der Befehl fcstat kann auch verwendet werden, um zu untersuchen, ob die Erhöhung von numcmdelems oder maxxfersize die Leistung fcstat fcs0 erhöhen könnte. FC SCSI-Adapter Treiberinformationen Keine DMA-Ressourcenzahl: 0 Nein Anzahl der Adapterelemente: 0 Nein Befehlsressourcenanzahl: 0 Dies zeigt ein Beispiel für einen Adapter mit ausreichenden Werten für numcmdelems und maxxsize. Nicht-Null-Wert würde eine Situation anzeigen, in der IOs an dem Adapter wegen fehlender Ressourcen anstehen, und zunehmende numcmdelems und maxxfersize angemessen sein würden. Beachten Sie, dass das Ändern von Maximalwerte Speicher in den PCI-Host-Bridge-Chips verwendet, die an den PCI-Steckplätzen befestigt sind. Der Vertriebspartner hinsichtlich des Dual-Port-4-Gbit / s-PCI-X-FC-Adapters besagt, dass der AIX-Wert der Maximalgröße, wenn er in einem PCI-X-Steckplatz platziert ist, der als SDR-kompatibel ist und eine Steckplatzgeschwindigkeit von 133 MHz aufweist, in der Standardeinstellung beibehalten werden muss Von 0x100000 (1 Megabyte), wenn beide Ports verwendet werden. Die Architektur des DMA-Puffers für diese Steckplätze bietet keine größeren Maximierungseinstellungen. Wenn zu viele FC-Adapter und zu viele LUNs am Adapter angeschlossen sind, führt dies zu Problemen beim Konfigurieren der LUNs. Fehler werden wie folgt aussehen: LABEL: DMAERR IDENTIFIER: 00530EA6 Datetime: Mo 3. März 10.48.09 EST 2008 Sequenznummer: 863-Maschine-ID: 00C3BCB04C00 Node Id: p595back Klasse: H Typ: UNKN Resource Name: PCIDMA Ressourcenklasse: KEINE Ressourcen Typ: Keine Standort: Beschreibung UNDETERMINED ERROR Mögliche Ursachen SYSTEM IO-Bus Software PROGRAM ADAPTER DEVICE Empfohlene Aktionen PERFORM Fehlerbestimmungs - VERFAHREN Detaildaten Busnummer FFFF FFFF 9000 00E4 Kanalzug ADDRESS 0000 0000 0000 018B ERROR CODE 0000 0000 1000 0003 Also, wenn Sie diese Fehler erhalten , Müssen Sie die maxxfersize wieder auf den Standardwert ändern. Beachten Sie auch, dass, wenn Sie von SAN booten, wenn Sie diesen Fehler auftreten, werden Sie nicht in der Lage zu booten, so sicher sein, einen Back-out-Plan haben, wenn Sie planen, dies zu ändern und booten von SAN. Weitere theoretische Gedanken zu gemeinsam genutzten und dedizierten Ressourcen Der schlaue Leser wird die Tatsache in Betracht gezogen haben, dass typischerweise viele hdisk-Treiber mehrere Adapter und Adapter-Treiber gemeinsam nutzen, so dass die FC-Warteschlangen-Slots eine gemeinsame Ressource für die hdisk-Treiber sind um sicherzustellen, dass wir die Adapter Warteschlangen nie füllen, durch SUM machen (hdisk0 queuedepth, hdisk1 queuedepth. hdiskM queuedepth) lt SUM (fcs0 numcmdelems, FCS1 numcmdelems. fcsN numcmdelems). Dies setzt voraus, dass IO gleichmäßig über die Adapter verteilt sind. Und die meisten Multi-Weg-Code Gleichgewicht IOs über die Adapter (oder zumindest kann). Obwohl oft, Umgebungen haben viele mehr hdisks als FC-Ports, und sicherzustellen, dass wir nicht füllen die Adapter-Treiber können zu kleinen Werten für queuedepth und volle Warteschlangen auf den hdisk-Treiber führen. So gibt es die dedizierte Ressource-Ansatz, der gemeinsame Ressourcen-Ansatz, und zwischen gewidmet und geteilt. Dieses einfache Beispiel, in dem Q die Warteschlangen-Tiefe für den Gerätetreiber repräsentiert: Dies würde ein dedizierter Ressourcenansatz sein, wobei 10 der Adaptertreiber-Warteschlangen-Slots jedem hdisk-Treiber zugeordnet sind. Hier wissen wir auch, niemals eine IO an eine vollständige Warteschlange auf dem Adapter-Treiber senden. Dies wäre ein gemeinsamer Ressourcenansatz, bei dem die 10 Adapter-Warteschlangen-Slots von einem einzigen hdisk-Treiber aufgefüllt werden könnten. Und hier ein Beispiel für etwas dazwischen: Hier werden immer mindestens 5 Warteschlangen-Slots im Adapter-Treiber für den hdisk-Treiber verfügbar sein. Es gibt Vor-und Nachteile für jeden Ansatz. Der Vorteil der dedizierten Ressource-Ansatz ist, dass die Ressourcen zugewiesen werden immer verfügbar sein, aber in der Regel wird es weniger Ressourcen für jeden Benutzer der Ressource zur Verfügung (hier die Ressource waren die Adapter-Warteschlange Slots, und die Benutzer der Ressource sind die Hdisk Treiber). Der Vorteil der Shared Resource-Ansatz ist, dass auch mehr Ressourcen für einen einzelnen Benutzer der Ressource, wenn sie es braucht und es wird in der Lage, mehr thruput als in der dedizierten Ressource-Ansatz zu bekommen. Der Autor bevorzugt in der Regel eine gemeinsame Ressourcen-Ansatz, wie in der Regel bietet die besten thruput und Preis Leistung. Beachten Sie, dass diese Situation der freigegebenen Ressourcen auf mehreren möglichen Weisen jenseits der hdisk-Treiber unter Verwendung von Adapter-Treibern auftritt. Es ist auch beteiligt, wenn: mehrere LV VSCSI-hdisks für eine einzelne hdisk auf einem VIOS mehrere vFC-Adapter mit einem einzigen Real-FC-Adapter Mehrere LPARs mit dem gleichen Plattensubsystem
No comments:
Post a Comment