Es gibt zwei Datenstrukturen, die jedem Programmierer bekannt sind und die als Axiome angesehen werden, dass niemand zu analysieren versucht, ob sie benötigt werden, ob sie von Nutzen sind und ob dieser Schaden sie nicht überschreitet.
Warteschlange
Zunächst werden wir die Warteschlange diskutieren. Was bedeutet die Warteschlange? Eine Warteschlange ist ein Puffer. Und wann brauchen wir einen Puffer? Wenn wir keine Zeit haben, eingehende Ereignisse im Tempo ihrer Ankunft zu verarbeiten.
Im Zusammenhang mit dem Vorstehenden stellt sich eine einzige Frage: Warum? Die Antwort ist, dass wir hoffen, dass etwas passiert und das System es uns plötzlich ermöglicht, Ereignisse zu verarbeiten.
Lassen Sie uns zunächst den ersten Absatz behandeln. Was soll mit dem System passieren, dass es plötzlich nicht mehr bremst und schneller Daten verarbeitet? Höchstwahrscheinlich wird ein ressourcenintensiver Prozess einfach enden und Ressourcen freisetzen. Aber was ist, wenn dies nicht geschieht? Was tun mit den Daten? Es ist bekannt, dass: entweder wir sie einfach zurücksetzen oder das gesamte System nur an einem Mangel an Ressourcen hängt.
Ente, es gibt zwei Fragen:
- Und warum können Sie die Daten nicht sofort löschen, wenn wir wissen, dass wir keine Ressourcen haben, um sie zu verarbeiten? Deshalb ist es unmöglich, aus einem Element eine Warteschlange zu erstellen?
- Oder die umgekehrte Frage. Warum machen wir uns Illusionen und versorgen das System nicht mit der notwendigen Menge an Ressourcen, um die Daten mit der Empfangsrate zu verarbeiten?
Die Antworten auf diese Fragen liegen auf der Hand. Wir wissen einfach nicht, wie man Software- und Hardwaresysteme entwirft. Denn wenn wir wüssten, wie man sie entwirft, würden wir wissen, wie viele Eingabedaten wir haben, wie hoch ihre Empfangsrate ist, wie viel wir für ihre Verarbeitung benötigen und dementsprechend den tatsächlichen Ressourcenbedarf berechnen können. Der derzeitige Stand der IKT-Entwicklungsinstrumente und -methoden mit Ausnahme eines Teils der technologischen Systeme (und keineswegs aller) erlaubt es uns jedoch nicht, den Ressourcenbedarf objektiv zu berechnen.
Und wir schließen diese Mängel mit allen Arten von Puffern, insbesondere in Form von Warteschlangen. Infolgedessen haben wir sogar auf der Höhe der Grube eine Bombe in das Fundament des Gebäudes gelegt, da diese Krücken als Quelle für verschiedene verächtliche und schwer zu erfassende Probleme mit Zuverlässigkeit, Sicherheit und einfach der Qualität der Arbeit dienen.
Aber lassen Sie uns fortfahren, vor uns liegt meine „Lieblingsstruktur“ - der Stapel!
Stapel
Das ist sicher, wie Hoar einmal über Null sagte, dass dies ein Milliarden-Dollar-Fehler ist, also kann das gleiche über den Stapel gesagt werden.
Dies ist eine der problematischsten Strukturen, die in der IKT verwendet werden, und ihre maximale Vermeidung bei der Erstellung von Hardware und Software bis zur vollständigen Ausrottung ist äußerst wünschenswert.
Was genau ist das Stack-Problem? Ja, genau wie bei der Warteschlange. Stapel sind grundsätzlich nicht zu arrangieren. Sobald es eine Person gibt, die genau vorhersagt, wie viel Speicher der Stapel eines beliebigen Programms benötigt, werde ich mich persönlich entschuldigen und einen großen Artikel schreiben, in dem ich mich geirrt habe, und um Vergebung bitten.
Aber irgendetwas sagt mir, dass dies auf absehbare Zeit unwahrscheinlich ist.
Lassen Sie uns analysieren, warum wir Stapel brauchen. Ja, genau für das gleiche, für das die Warteschlange. Dies ist ein Puffer. Das heißt, dies sind Krücken für einen faulen Verstand, der Software- und Hardwaresysteme nicht richtig entwerfen möchte.
Die Lektion lautet also: Rekursionen sollten vermieden werden, wenn es eine offensichtliche iterative Lösung gibt. Dies bedeutet jedoch nicht, dass Rekursionen um jeden Preis entsorgt werden sollten. Es gibt viele gute Beispiele für die Verwendung von Rekursion, die wir in den folgenden Abschnitten und Kapiteln demonstrieren werden. Die Tatsache, dass es auf praktisch nicht rekursiven Maschinen Implementierungen von rekursiven Prozeduren gibt, zeigt, dass aus praktischen Gründen jedes rekursive Programm in ein rein iteratives umgewandelt werden kann. Dies erfordert jedoch eine explizite Arbeit mit dem Rekursionsstapel, und diese Aktionen verdecken häufig das Wesentliche des Programms, so dass es schwierig zu verstehen sein kann. Schlussfolgerung: Algorithmen, die rekursiver und nicht iterativer Natur sind, müssen als rekursive Prozeduren formuliert werden.
Nicklaus Wirth. Algorithmen und Datenstrukturen
Ich stimme dem Master über die Konvertierungsoptionen zu und stimme seinen weichen Ansätzen zur Verwendung des Stapels nicht zu.
Ich habe einen Satz aufgestellt: Jeder Stapelalgorithmus kann in eine Schleife konvertiert werden, und diejenigen, die nicht konvertiert werden können, sind schlecht.
Das Aufrufen von Unterprogrammen mit Übergeben von Parametern durch den Stapel sollte gestoppt werden, und eine Rekursion, die sich nicht in die Schleife ausdehnt, und andere weit verbreitete Verfahren sollten ebenfalls dorthin gehen.
Wir können den Stapel für die folgenden Fälle ersetzen:
- Rekursion, implementiert in Form der Erweiterung des Stapelalgorithmus in eine Schleife mit einem Datenblock, der während der Ausführung der Schleife geändert wird.
- Wenn Sie Parameter übertragen müssen, organisieren Sie ein Firmware-System mit Messaging. Und was das Versenden von Nachrichten betrifft, gehen wir zu den Zeilen, die im ersten Teil des Artikels beschrieben wurden. Wenn Sie wirklich einen Stapel wollen, sollten Sie natürlich nicht Dutzende und Hunderte von Kilobyte von Objekten dorthin verschieben, aber Sie müssen normalerweise Speicher dafür auf dem Heap zuweisen.
Gleichzeitig können Programmierer auf der obersten Ebene beliebige Datenstrukturen verwenden, und es liegt an den Compilern, diese zu transformieren, um die Verwendung des Stapels auszuschließen.
Natürlich werden einige der Möglichkeiten wahrscheinlich verloren gehen, aber dies ist, wenn es im Detail betrachtet wird, keine Tatsache.
Blockierung
1995 formulierte ich mit meinem Klassenkameraden die Prinzipien des Aufbaus eines Betriebssystems, das beide Paradigmen ausschloss.
Die Prinzipien waren wie folgt:
- Software - Netzwerke interagierender Prozesse.
- Das Zusammenspiel von Prozessen erfolgt durch den Austausch von Nachrichten.
- Das Netzwerk interagierender Prozesse ist wie folgt organisiert: Die Quellen für Primärnachrichten in einem solchen Netzwerk sind nur Ereignisse aus der Außenwelt, die von Geräten bereitgestellt werden. Die Endverbraucher von Nachrichten sind nur Geräte, die Aktionen in der Außenwelt ausführen. Das heißt, das Netzwerk beginnt in der realen Welt und endet darin.
- Prozesse können keine Prioritäten haben. Prioritäten können nur ein Netzwerk von Prozessen haben.
- Das Netzwerk puffert niemals Nachrichten. Der Hardware-Software-Komplex sollte so organisiert sein, dass Nachrichten im Tempo ihres Eingangs von außen verarbeitet werden können.
- Der Hardwarekomplex ist ein Netzwerk von Rechenknoten, die durch Kommunikationskanäle verbunden sind.
- Jeder Knoten hat "Kosten", abhängig von seiner Verarbeitungsleistung, Speichergröße, Last und Gewichtsfaktor, unter Berücksichtigung der Kosten für seine Erstellung und Wartung.
- Jeder Kommunikationskanal hat abhängig von seiner Bandbreite, Überlastung und seinem Gewichtskoeffizienten „Kosten“, wobei die Kosten für seine Erstellung und Wartung berücksichtigt werden.
- Das Betriebssystem bietet den Start von Prozessen als Reaktion auf eingehende Nachrichten und Nachrichtenrouting.
- Das Betriebssystem stellt die Verteilung von Prozessen und Nachrichten zwischen Rechenknoten sicher und optimiert die Funktion f (CPU, Mem) in der Netzwerktopologie unter Berücksichtigung der Kosten für die Übertragung des Prozesscodes und der Nachrichten an den Knoten.
- Aufgrund des Aufbaus des Systems können Sie die für den Prozess erforderliche Speichermenge immer genau berechnen. Die erforderliche Zählzeit kann basierend auf der Analyse des Algorithmus genau berechnet werden.
BIND-Prozessor
Im Rahmen seiner Lehrkarriere nahm er zusammen mit Studenten einmal am IEEE-CPU-Emulator-Wettbewerb teil. Ein stapelloser Allzweckprozessor mit Harvard-Architektur wurde unter Verwendung eines Befehlssystems ähnlich früheren ARMs entwickelt. Auch die vergessene Idee der Transporter wurde in die CPU integriert und der Prozessor mit 16 8-Bit-Empfangs-Sende-Kanälen ausgestattet.
Dementsprechend gab es im Prozessor keine Call / Return-Operationen. Es war nur ein bedingter / bedingungsloser Übergang möglich. Da derzeit fast niemand in Assembler schreibt, sollten alle Fragen zum Generieren eines Programms im Maschinencode dem Compiler zugewiesen werden.
Das Hauptziel dieses Prozessors war es, die Prinzipien des Blockout-Betriebssystems auf Hardwareebene nahtlos zu unterstützen, indem ein Netzwerk von Prozessoren im lokalen Rechenknoten erstellt wurde, die durch Kommunikationskanäle verbunden sind, über die Prozesse bereits verteilt werden.
Schlussfolgerungen
Der Text zeigt die schwerwiegenden Fehler der Warteschlangen- und Stapeldatenstrukturen. Die Prinzipien des Entwurfs von Software- und Hardwaresystemen, die es ermöglichen, diese Strukturen von der Anwendungspraxis auszuschließen, werden angegeben.
Dieser Text ist vielmehr eine Zusammenstellung von Gedanken, die im Laufe einer IT-Karriere entstanden sind, um sozusagen alles an einen Ort zu bringen.