Rechensysteme : Grundlagen der Modellbildung

Das Buch ist hervorgegangen aus Vorlesungen, die wir an der Universität Hamburg gehalten haben. Der Umstand, daß die übliche getrennte Darstellung der Gebiete "Betriebssysteme", "Rechnerorganisation" und "Verteilte Systeme" jede der Veran­ staltungen mit der Präsentation eines Instrumentariums von Verfahren belastet und dabei den Lernenden die Einheit der Gesichtspunkte leicht verborgen bleibt, führte dazu, daß das Lehrgebiet "Rechnerorganisation und Betriebssysteme" in eine Grundvorlesung "Rechensysteme" und darauf aufbauende - dank der bereits ge­ brachten Grundlagen - mehr implementationsorientierte Vorlesungen "Rechneror­ ganisation" , "Betriebssysteme", "Verteilte Systeme" gegliedert wurde. Die Vor­ lesung "Rechensysteme" hat Ansatz und Material zu diesem Buch geliefert. Das Buch eignet sich daher als Begleittext für Studenten der Informatik im Hauptstudium und für Nebenfachinformatiker mit Interesse für Rechensysteme, sowie als Grundlagentext für Programmierer und Systemanalytiker. Es ist als Lehrbuch für eigenständiges Lernen und als Nachschlagewerk für Praktiker geeig­ net, die Aufschluß über theoretische Modelle voraussetzende Fragen brauchen. Für vertiefende Studien werden zahlreiche Literaturhinweise gegeben. Wir danken Eike Best, Wilfried Brauer, Heino Carstensen, Hans-Jürgen Siegert und Bernd Wolfinger für viele wichtige Ratschläge, Werner Pohlmann und zahlreichen Studenten für Hinweise auf Fehler und Verständnisschwierigkeiten und den vielen, die mit Geduld und Verständnis Manuskript und druckfertigen Text hergestellt haben: Gabriele Diem, Ullrich Dillis, Heidrun Durry, Anita Graef, Monika Grimm und Anne Christi ne Hogrefe. München/Hamburg, Juni 1986 Jessen Eike Rüdiger Va1k Wer sich der Praxis hingibt ohne Wissenschaft ist wie der Steuennann, der ein Schiff ohne Ruder und Kompass besteigt und nie weiß, wohin er fährt.

0 Einleitung.- 1 Elementare Begriffe und Erscheinungen.- 1.1 Handlung und Auftrag.- Handlung, Netz, Vergröberung, Verfeinerung, Betriebsmittel, Funktionseinheit, Auftrag, Programmiersprache PROG.- 1.2 Präzedenzen.- Auftragssystem, Präzedenzrelation, Kausalnetz, Relationen lo un co, Linien und Schnitte.- 1.3 Zeitliche Ordnung und Prozesse.- S/T-Netz, B/E-Netz, Schaltregel, Ausführungsfolgen, asynchrone und synchrone Prozesse, komplementäre Stellen, Netzprogramme und ihre Prozesse.- 1.4 Aufträge an Funktionseinheiten.- S/T-Netz, B/E-Netz, Schaltregel, Ausführungsfolgen, asynchrone und synchrone Prozesse, komplementäre Stellen, Netzprogramme und ihre Prozesse.- 1.5 Kosten.- Kosten-Durchsatz-Verhältnis, mittlere Kosten je Auftrag, Gemeinkosten-Auftrag.- 1.6 Nutzen.- Nutzenfunktion.- 1.7 Einige Aspekte des Entwurfs von Rechensystemen: Strukturen, Strategien, Dimensionierung.- Bewertung, Dimensionierung, verteilte Systeme, Graph mit Kostenfunktion, Gerüst, Konzentratoren, optimale Verteilung von Funktionseinheiten auf Baueinheiten, Bindungsgraph, Fluß-Probleme.- 2 Nebenläufige Prozesse.- 2.1 Nebenläufigkeit in Rechensystemen.- Bedeutung von Nebenläufigkeit.- 2.2 Das Extensionalitäts-Prinzip.- Synchronisation, Fall/Transitions-System, schlichtes Netz, Extensionalitätsprinzip, kritischer Abschnitt.- 2.3 Unteilbarkeit von Handlungen.- 2.3.1 Einführende Beispiele.- Protokolle, Realisierung von kritischen Abschnitten, Lösung von Dekker/Peterson.- 2.3.2 Unteilbarkeit als programmier-methodologisches Konzept.- Unteilbare Anweisung, Prozeßsemantik von Unteilbarkeit.- 2.3.3 Realisierungen von Unteilbarkeit.- Semaphor, test-and-set-, region- und await-Anweisungen.- 2.3.4 Unteilbarkeit als Konsistenzkriterium.- Schematisches Auftragssystem, Interpretation, nutzlose und relevante Aufträge, Serialisierung, Serialisierbarkeit, virtuell serielles und zweiphasiges Transaktionensystem.- 2.3.5 Funktionalität.- Funktionales und spurfunktionales Auftragssystem, Störungs- und Verlustfreiheit, maximal nebenläufiges Auf tragssystem.- 2.3.6 Syntaktische Kriterien für Unteilbarkeit.- Strukturiertes Auftragssystem, Wohlstrukturiertheit, wohldefinierte Aufträge, Umgebungsunabhängigkeit.- 2.4 Synchronisation.- 2.4.1 Typen von Synchronisation.- Konsistenz- und Betriebsmittel-Synchronisation, Leser/Schreiber-Problem, Prioritäten, Betriebsmittel- Auftragssystem, LJ-Folge, Verklemmungsfreiheit und Sicherheit.- 2.4.2 Nachweis von Synchronisationsbedingungen.- S- und T-Invarianten, Wirkung einer Transition, Inzidenzmatrix.- 2.4.3 Verklemmungsfreiheit.- BM-Bedarfsnetz, Entdeckung, Ausschluß und Umgehung, Residuum, K-gesteuertes S/T-Netz, Bankiers-Problem.- 2.4.4 Lebendigkeit und Fairneß.- Lebendiges und T-fortsetzbares Netz, maximal lebendiges Teilverhalten, faires Verhalten, verschleppungsfreie und faire Schaltregel.- 2.2 Höhere programmsprachliche Synchronisationskonzepte.- 2.5.1 Speicher-Synchronisation.- Monitor, Concurrent PASCAL.- 2.5.2 Rendezvous-Synchronisation.- Rendezvous, CSP, ADA, V-System, Gruppen-Kommunikation.- 2.5.3 Datenflußprogramme und funktionale Programmierung.- Funktionale Sprachen, Datenflußgraphen und Pr/T-Netze.- 2.3 Kommunikation in verteilten Systemen.- Verteiltes System, Synchronisation in verteilten Systemen, Kommunikations-Protokolle, OSI-Schichtenmodell, Datenübermittlungs- und Transportprotokoll.- 3 Sicherheit und Korrektheit von Rechensystemen.- 3.1 Rechte und Schutzmechanismen.- Aktive und passive Rechte, Schutzspezifikationen.- 3.2 Rechtsbereiche.- Zugriffsmatrix, Zugriffsliste, Berechtigung, Schutzmechanismen, Modul, Unsicherheit.- 3.3 Korrektheit von Rechensystemen und Realisierung von 283 Schutzmechanismen.- Zuverlässigkeit, Abgrenzung und Abstraktion, Betriebssystem-Schichtenmodell, Kern, Sicherheits-Kern.- 4 Zuverlässigkeit: Stochastische Modelle.- 4.1 Begriffe und Erscheinungen.- Zuverlässigkeit, Fehler, Ausfall, Störung, Redundanz, Beanspruchung, Werte.- 4.2 Stochastische Modelle für Lebensdauer und für das Auftreten von Störungen und Ausfällen.- Stochastische und operationale Modelle, Ereignisrate, Poisson-Prozeß, Restzeit.- 4.3 Zuverlässigkeit von Strukturen ohne Fehlerbehebung.- ßberlebensfunktion, Serienstruktut, Parallelstruktur, k-aus-n-Struktur.- 4.4 Zuverlässigkeit von Strukturen mit Fehlerbehebung.- Verfügbarkeit, homogener zustandsdiskreter Markovscher Prozeß in kontinuierlicher Zeit, Beispiele.- 5 Auftragsverkehr.- 5.1 Littlesche Formeln.- Einfaches operationales Modell, stochastisches Modell.- 5.2 Elementare Wartesysteme.- Verlustsystem, Wartesystem, Wartepool, Bedienstation, Auftragsankunftsprozeß, Bedienstrategie, Syntax der elementaren Wartesysteme.- 5.3 Auftragsverkehr in allgemeinen Systemen.- 5.3.1 Ermittlung des Auftrags Verkehrs: Motive und Verfahren.- Prim–re und sekundäre Belastung, Overhead, Experiment und Rechnung, Modellierung, Validierung.- 5.3.2 System und Belastung.- Geschlossene und offene Systeme, Belastung.- 5.3.3 Durchsatzgesetze und die Auswirkung von Grenzdurchsätzen.- Allgemeines Durchsatzgesetz, Engpässe, Grenzdurchsatz eines Systems, Wegewahl, Klassen, Beispiel, Umlauf zeit.- 5.3.4 Verweilzeitgesetze.- 5.3.5 Grenzverhalten bei kleiner und großer Füllung.- 5.4 Wartenetze.- 5.4.1 Einführung.- 5.4.2 Das elementare Wartesystem M/M/m/k.- 5.4.3 Jackson-Netze.- 5.4.4 Gordon-Newell-Netze.- Definition, Faltungsverfahren, Vergleich mit offenem Netz.- 5.4.5 BCMP-Netze.- Definition, Knotentypen, Cox-Verteilung, Beispiel.- 5.5 Wechselwirkungen von Auftrags verkehr und Zuverlässigkeit.- Struktur der Wechselwirkungen, Fehlertypen, belastungsabhängige Störungen und störungsabhängige Belastung.- 5.6 Betriebsformen von Rechensystemen.- 5.6.1 Kategorien.- Externes Betriebsziel, innere Organisationsform, zeitliche Organisation.- 5.6.2 Konzentrierte Systeme.- Serieller Betrieb, Spooling, Teilnehmerbetrieb, Stapelbetrieb, Realzeitbetrieb.- 5.6.3 Verteilte Systeme.- Rechnernetz, Kommunikations verbünd, Lastverbund, Sicherheitsverbund, Funktionsverbund, Datenverbund.- 6 Ablaufplanung.- 6.1 Last.- Last, Freiphase, Beschäftigungsphase.- 6.2 Bedienstrategien: allgemeine Eigenschaften.- 6.3 Nichtverdrängende Bedienstrategien im Wartesystem M/G/l.- 6.3.1 FCFS, LCFS und andere Strategien mit bedienzeit unabhängiger Wartezeit.- Mittlere gewichtete Restbedienzeit, Pollaczek-Khinchin- sche Mittelwertformel, Einfluß des Variationskoeffizienten.- 6.3.2 Schranken und Invarianzen.- Untere und obere Wartezeitschranke, mittlere gewichtete Restbedienphase, Kleinrocks Erhaltungssatz.- 6.3.3 Prioritätsstrategien.- 6.3.4 Bedienzeitabhängige Strategien.- 6.3.5 Lastmindernde Strategien.- Trommel- und Festkopfplattenspeicher, Plattenspeicher mit beweglichen Köpfen, Restrotationszeit, SATF, SST, FSCAN, SCAN.- 6.4 Verdrängende Bedienstrategien im Wartesystem M/G/l.- 6.4.1 Würdigung verdrängender Strategien.- 6.4.2 Schranken für die mittlere Wartezeit.- Untere und obere Wartezeitschranke.- 6.4.3 Sonderfall: negativ-exponentiell bzw. entartet negativ exponentiell verteilte Bedienzeit.- LCFS-p, RR, SET, entartet negativ-exponentielle Verteilung, sofortige Bedienung des ankommenden Auftrags.- 6.4.4 Prioritätsstrategien.- 6.4.5 LCFS-p.- 6.4.6 Round Robin.- Grenzfall sehr kleiner Zeitscheiben, effektive Zeitscheiben, technische Zeitscheibengröße.- 6.4.7 SET.- 6.4.8 Bedienzeitabhängige Strategien.- Optimalstrategien bei entartet negativ-exponentiell verteilter Bedienzeit.- 6.5 Vergleich.- 7 Speicherverwaltung.- 7.1 Grundphänomene.- Speicher bei seriellem und simultanem Betrieb, virtuelle Speicherverwaltung.- 7.2 Totale Zuteilung von Hauptspeicher.- 7.2.1 Starre und veränderliche Aufteilung.- Region, Partition von Hauptspeicher, Mehrprogrammbetrieb mit fester und variabler Auftragszahl, interne und externe Speicherzerstückelung, First-Fit/Best-Fit- Strategie, 50% ― Regel.- 7.2.2 Verschiebbare Speicherbelegung.- Speicherverdichtung, Verschiebe-Durchsatz.- 7.2.3 Gestreute Anordnung von Speicher.- Segment, Segmenttabelle.- 7.3 Partielle Zuteilung von Hauptspeicher.- 7.3.1 Dynamischer Speicherbedarf, Überlagerung.- Verwaltung als Keller oder Halde, Overlay.- 7.3.2 Seitenersetzung mit fester Kachelzahl.- Seite, Kachel, Referenzwort, Seitenfehler, Seitenwechselalgorithmus, FIFO, LIFO, LRU, Bo, LFU, Kostenfunktion, Speicherhierarchie, Fehlerraten, Lokalität, Anomalien, Stack-Algorithmen.- 7.3.3 Seitenersetzung mit variabler Kachelzahl.- Seitenflattern, Transport/Rechenzeit-Verhältnis, Arbeitsmenge (working set), WS, PFF, schrittweise und zeitliche Speicherkosten, Anomalien, verallgemeinerte Stack-Algorithmen.- 7.4 Dateiverwaltung.- Datei, Zugriffsmechanismen, Dateiverzeichnis.- Stichwortverzeichnis.