Von-Neumann-Architektur und Grenzen der Automatisierung
Ein Verkehrsunternehmen in Köln wirbt für ein Prüfwerkzeug, das „garantiert jeden Fehler in der Fahrplansoftware findet“. Kann das stimmen? Um das zu beurteilen, müssen Sie zwei Dinge verstehen: Wie arbeitet ein Rechner im Innersten, und was kann man mit einem Rechner grundsätzlich nicht erreichen, egal wie schnell er ist?
Aufbau der Von-Neumann-Architektur
Fast jeder Rechner, vom Smartphone bis zum Server im Rechenzentrum in Düsseldorf, folgt demselben Grundplan. Er geht auf einen Entwurf von John von Neumann (1945) zurück.
Die Hauptkomponenten:
-
Steuerwerk: holt Befehle, entschlüsselt sie und steuert den Ablauf. Es enthält den Befehlszähler (Programmzähler), der die Adresse des nächsten Befehls speichert.
-
Rechenwerk (ALU): führt arithmetische und logische Operationen aus. Zwischenergebnisse stehen in Registern, z. B. im Akkumulator.
-
Speicher: besteht aus durchnummerierten Zellen. Jede Zelle hat eine Adresse und enthält ein Bitmuster.
-
Ein- und Ausgabe: Tastatur, Bildschirm, Netzwerk, Festplatte.
-
Bussystem: Verbindungsleitungen für Adressen, Daten und Steuersignale.
Das hat einen großen Vorteil: Ein Programm ist selbst nur Daten. Man kann es laden, austauschen oder von einem anderen Programm erzeugen lassen (Compiler). Der Rechner ist dadurch universell einsetzbar. Der Preis ist ein Risiko, auf das wir im nächsten Abschnitt zurückkommen.
a) Nennen Sie die Hauptkomponenten der Von-Neumann-Architektur. b) Erklären Sie, was „gemeinsamer Speicher für Programme und Daten“ bedeutet.
- a) Nennen Sie die Hauptkomponenten der Von-Neumann-Architektur.
- b) Erklären Sie, was „gemeinsamer Speicher für Programme und Daten“ bedeutet.
Fetch-Decode-Execute und Registermaschine
Der Prozessor arbeitet ein Programm in einem festen Takt ab, dem Fetch-Decode-Execute-Zyklus:
-
Fetch (Holen): Der Befehl wird aus der Speicherzelle geholt, auf die der Befehlszähler zeigt. Danach wird der Befehlszähler um 1 erhöht.
-
Decode (Entschlüsseln): Das Steuerwerk ermittelt, welche Operation gemeint ist und welche Adresse sie als Operand hat.
-
Execute (Ausführen): Die Operation wird ausgeführt, z. B. wird addiert, gespeichert oder der Befehlszähler neu gesetzt (Sprung).
Zur Veranschaulichung nutzen wir ein einfaches Modell, die Registermaschine mit einem Akkumulator (Akku):
| Befehl | Wirkung |
|---|---|
LOAD a |
Akku := Inhalt von Zelle a |
ADD a |
Akku := Akku + Inhalt von Zelle a |
SUB a |
Akku := Akku − Inhalt von Zelle a |
STORE a |
Zelle a := Akku |
JMP z |
Befehlszähler := z |
JMPZ z |
Befehlszähler := z, falls Akku = 0, sonst weiter mit dem nächsten Befehl |
HALT |
Programm endet |
Sprünge machen Schleifen möglich. Hier ein Programm mit Zellen 10 = 2 und 11 = 1:
0: LOAD 10, 1: SUB 11, 2: STORE 10, 3: JMPZ 5, 4: JMP 0, 5: HALT
| Durchlauf | BZ | Akku | Zelle 10 |
|---|---|---|---|
| 1 | 0 → 1 → 2 | LOAD: 2, SUB: 2 − 1 = 1, STORE | 1 |
| 1 | 3 | 1 (≠ 0, kein Sprung) | 1 |
| 1 | 4 | Sprung zu 0 | 1 |
| 2 | 0 → 1 → 2 | LOAD: 1, SUB: 1 − 1 = 0, STORE | 0 |
| 2 | 3 | 0 → Sprung zu 5 | 0 |
| – | 5 | HALT |
0 |
Das Programm zählt Zelle 10 in Einerschritten bis 0 herunter.
Risiko des gemeinsamen Speichers: Weil Daten und Befehle im selben Speicher stehen, kann ein Programm, das Daten schreibt, unabsichtlich oder absichtlich auch Befehle überschreiben. Beim Pufferüberlauf schreibt ein Programm mehr Daten in einen Bereich, als dort Platz haben. Die überschüssigen Daten landen in Nachbarzellen. Enthalten diese Befehle oder Rücksprungadressen, kann ein Angreifer eigenen Code einschleusen. Gegenmaßnahmen sind Grenzprüfungen und Speicherbereiche, die als „nicht ausführbar“ markiert sind.
Erklären Sie den Fetch-Decode-Execute-Zyklus in drei Schritten und nennen Sie die Rolle des Befehlszählers.
Erklären Sie den Fetch-Decode-Execute-Zyklus in drei Schritten und nennen Sie die Rolle des Befehlszählers.
Ein Registermaschinenprogramm hat die Befehle LOAD a, ADD b, STORE c, JMPZ z, HALT. Die Speicherzellen: a = 5, b = 7, c = 0. a) Schreiben Sie ein Programm, das a + b in…
Ein Registermaschinenprogramm hat die Befehle LOAD a, ADD b, STORE c, JMPZ z, HALT. Die Speicherzellen: a = 5, b = 7, c = 0.
- a) Schreiben Sie ein Programm, das a + b in c speichert.
- b) Verfolgen Sie Akkumulator und Speicher Schritt für Schritt.
Ein Von-Neumann-Rechner führt ein Programm im Speicher ab Adresse 0 aus. Befehle: 0: LOAD 10, 1: SUB 11, 2: JMPZ 5, 3: STORE 10, 4: JMP 0, 5: HALT. Anfangs gilt Zelle 10…
Ein Von-Neumann-Rechner führt ein Programm im Speicher ab Adresse 0 aus. Befehle: 0: LOAD 10, 1: SUB 11, 2: JMPZ 5, 3: STORE 10, 4: JMP 0, 5: HALT. Anfangs gilt Zelle 10 = 3 und Zelle 11 = 1.
- a) Verfolgen Sie Befehlszähler, Akkumulator und Zelle 10 bis zum Halt.
- b) Beschreiben Sie, was das Programm berechnet.
- c) Erläutern Sie, welches Risiko entsteht, weil Programm und Daten im selben Speicher liegen (z. B. Pufferüberlauf).
Praktisch nicht lösbar: wenn die Laufzeit explodiert
Ein Problem kann prinzipiell lösbar sein und trotzdem praktisch unlösbar, weil die Rechenzeit zu schnell wächst. Entscheidend ist, wie die Anzahl der Schritte mit der Eingabegröße $n$ wächst.
Die Kurve $n^2$ (polynomiell) wächst vergleichsweise langsam, während $2^n$ (exponentiell) bald davonläuft.
Noch schneller wächst die Fakultät $n! = n \cdot (n-1) \cdot \ldots \cdot 2 \cdot 1$. Sie tritt auf, wenn man alle Reihenfolgen durchprobiert, z. B. beim Problem des Handlungsreisenden: Ein Lieferwagen soll $n$ Orte genau einmal besuchen und zum Start zurückkehren. Bei festem Startort gibt es $(n-1)!$ Reihenfolgen.
Beispiel mit 10 Orten (z. B. Städte im Ruhrgebiet): $9! = 362\,880$ Rundreisen. Dabei zählt jede Richtung als eigene Rundreise (die Rückwärtsroute wird nicht durch 2 geteilt). Das ist noch harmlos. Bei 15 Orten sind es $14! \approx 8{,}7 \cdot 10^{10}$, bei 20 Orten schon $19! \approx 1{,}2 \cdot 10^{17}$.
Praktische Lösung: Heuristiken. Sie liefern schnell eine gute, aber nicht beweisbar beste Lösung. Man gibt also die Garantie der Optimalität auf und gewinnt dafür Rechenzeit.
Nennen Sie zwei Aufgaben, die ein Computer prinzipiell nicht oder nur eingeschränkt lösen kann (z. B. Halteproblem, unvertretbar lange Laufzeit), und erklären Sie kurz…
Nennen Sie zwei Aufgaben, die ein Computer prinzipiell nicht oder nur eingeschränkt lösen kann (z. B. Halteproblem, unvertretbar lange Laufzeit), und erklären Sie kurz je eine Ursache.
Ein Algorithmus benötigt für $n$ Eingaben $2^n$ Schritte, ein Rechner schafft $10^9$ Schritte pro Sekunde. a) Bestimmen Sie die Laufzeit für $n = 30$ und $n = 60$…
Ein Algorithmus benötigt für $n$ Eingaben $2^n$ Schritte, ein Rechner schafft $10^9$ Schritte pro Sekunde.
- a) Bestimmen Sie die Laufzeit für $n = 30$ und $n = 60$ (Größenordnung in Sekunden bzw. Jahren).
- b) Beurteilen Sie, ob ein 1000-mal schnellerer Rechner das Problem für $n = 60$ praktisch lösbar macht.
Eine Handelskette will 20 Filialen in Niedersachsen auf einer kürzesten Rundreise anfahren (Problem des Handlungsreisenden). a) Bestimmen Sie die Anzahl möglicher…
Eine Handelskette will 20 Filialen in Niedersachsen auf einer kürzesten Rundreise anfahren (Problem des Handlungsreisenden).
- a) Bestimmen Sie die Anzahl möglicher Rundreisen als Fakultät und schätzen Sie die Größenordnung. Begründen Sie dabei, ob die Startfiliale und die Fahrtrichtung für die Zählung eine Rolle spielen.
- b) Erklären Sie, warum man in der Praxis Heuristiken einsetzt und was dabei aufgegeben wird.
Prinzipiell nicht lösbar: das Halteproblem
Es gibt Probleme, die kein Programm für alle Eingaben lösen kann, auch nicht mit unbegrenzter Zeit. Das bekannteste ist das Halteproblem.
Der Beweis ist ein Widerspruchsbeweis. Wir nehmen an, es gäbe ein Programm haelt(P, x), das immer richtig wahr oder falsch liefert.
Folgerung für die Praxis: Es gibt keine Software, die für jedes Programm automatisch und fehlerfrei entscheidet, ob es hält. Mit ähnlichen Argumenten folgt, dass auch viele andere allgemeine Aussagen über Programmverhalten nicht automatisch prüfbar sind.
Das heißt nicht, dass man gar nichts prüfen kann:
-
Testen findet Fehler, kann aber keine Fehlerfreiheit beweisen. Es prüft nur endlich viele Eingaben.
-
Verifikation und statische Analyse beweisen Eigenschaften für Spezialfälle, z. B. für eingeschränkte Programmklassen oder bestimmte Eigenschaften wie „keine Division durch 0“.
Wichtig ist der Unterschied der beiden Grenzen: Beim Halteproblem ist die Aufgabe nicht berechenbar, unabhängig von der Rechenzeit. Beim Handlungsreisenden ist die exakte Optimierung berechenbar (man kann alle Rundreisen durchprobieren), aber praktisch nicht in akzeptabler Zeit lösbar.
Angenommen, es gäbe ein Programm haelt(P, x), das entscheidet, ob Programm $P$ bei Eingabe $x$ hält. Man konstruiert s(P): Wenn haelt(P, P) wahr ist, läuft s endlos,…
Angenommen, es gäbe ein Programm haelt(P, x), das entscheidet, ob Programm $P$ bei Eingabe $x$ hält. Man konstruiert s(P): Wenn haelt(P, P) wahr ist, läuft s endlos, sonst hält s.
- a) Beschreiben Sie, was
s(s)tut, und leiten Sie den Widerspruch her.
- b) Formulieren Sie die Schlussfolgerung für die Automatisierung der Programmprüfung.
- c) Nennen Sie ein praktisches Beispiel, in dem man trotzdem Teilaussagen prüfen kann (Testen, Verifikation für Spezialfälle).
Ein Unternehmen wirbt mit einer Software, die „jeden Fehler in jedem Programm automatisch findet“. a) Beurteilen Sie die Aussage mithilfe des Halteproblems. b) Erläutern…
Ein Unternehmen wirbt mit einer Software, die „jeden Fehler in jedem Programm automatisch findet“.
- a) Beurteilen Sie die Aussage mithilfe des Halteproblems.
- b) Erläutern Sie den Unterschied zwischen nicht berechenbar und praktisch nicht berechenbar (Laufzeit).
- c) Beschreiben Sie, was Testen leisten kann und was nicht.
Auf einen Blick
-
Von-Neumann-Architektur: Steuerwerk, Rechenwerk, gemeinsamer Speicher für Befehle und Daten, Ein- und Ausgabe, Bussystem. Risiko des gemeinsamen Speichers: z. B. Pufferüberlauf.
-
Fetch-Decode-Execute: Befehl holen (Befehlszähler erhöhen), entschlüsseln, ausführen. Der Befehlszähler bestimmt, welche Zelle als Nächstes als Befehl gilt.
-
Registermaschine: Programme mit
LOAD,ADD,STORE,JMP,JMPZ,HALTper Tabelle verfolgen. -
Praktisch nicht lösbar: exponentielles ($2^n$) und faktorielles ($n!$) Wachstum; schnellere Hardware hilft kaum, Heuristiken opfern die Optimalität.
-
Prinzipiell nicht lösbar: Halteproblem (Beweis durch Widerspruch). Testen findet Fehler, beweist aber keine Fehlerfreiheit.
-
Einordnung: Von-Neumann-Architektur, Halteproblem und die Grenzen der Automatisierung gehören zum Kernlehrplan. Dazu gehören auch die Beweisidee zum Halteproblem und die Laufzeitabschätzungen zum Handlungsreisenden als Beispiele für prinzipielle und praktische Grenzen.
-
Operatoren: nennen Sie Komponenten, erläutern Sie den Zyklus, verfolgen Sie Programmabläufe, beurteilen Sie Laufzeiten und Aussagen zur Automatisierung.