Grundlage von Betriebssystemen - FAU · 2015. 6. 30. · 1 1945 Röhre Stapelbetrieb 2 1955 Halbleiter, Gatter Echtzeitbetrieb 3 1965 MSI/LSI, WAN Mehrprogrammbetrieb 4 1975 VLSI,

SystemprogrammierungGrundlage von Betriebssystemen

Teil B – VII.1 Betriebsarten: Stapelverarbeitung

Wolfgang Schröder-Preikschat

1. Juli 2015

Agenda

Einführung

EinprogrammbetriebManuelle RechnerbestückungAutomatisierte RechnerbestückungSchutzvorkehrungenAufgabenverteilung

MehrprogrammbetriebMultiplexverfahrenSchutzvorkehrungenDynamisches LadenSimultanverarbeitung

Zusammenfassung

c©wosch SP (SS 2015, B – VII.1) 1. Einführung VII.1/2

Gliederung

Einführung



Zusammenfassung


Lehrstoff

Ziel ist es, „zwei Fliegen mit einer Klappe zu schlagen“, nämlich:i einen Einblick in Betriebssystemgeschichte zu geben undii damit gleichfalls Betriebsarten von Rechensystemen zu erklärenim Vordergrund stehen die Entwicklungsstufen im Stapelbetrieb

Adressraumschutz durch Abteilung, Eingrenzung und SegmentierungDurchsatz-/Leistungssteigerung durch abgesetzten Betrieb, überlappteund abgesetzte Ein-/Ausgabe und SimultanbetriebSpeicherminimierung durch Programmzerlegung und Überlagerungen

Viele dieser Techniken — wenn nicht sogar alle — sind auchheute noch in einem Universalbetriebssystem auffindbar.

kennzeichnend dabei ist, Programme interaktionslos auszuführenhierzu ist eine vollständige Auftragsbeschreibung erforderlichdie in einer speziellen „Skriptsprache“ ausformuliert wirdum das fertige „Skript“ von einem Interpretierer verarbeiten zu lassender anfangs als Monitor und später als Betriebssystem in Erscheinung tritt


Betriebssystemevolution

Wenn wir nicht absichtlich unsere Augen verschließen, sokönnen wir nach unseren jetzigen Kenntnissen annäherndunsere Abstammung erkennen, und dürfen uns derselben nichtschämen. (Charles Darwin)

c©wosch SP (SS 2015, B – VII.1) 1.1 Einführung –Präludium VII.1/5

Generationen von Hardware und Betriebssoftware

zeitliche Einordnung von Technologiemerkmalen„unscharf“, Übergänge fließend

Generation Epoche Hardware Rechnerbetriebsart1 1945 Röhre Stapelbetrieb2 1955 Halbleiter, Gatter Echtzeitbetrieb3 1965 MSI/LSI, WAN Mehrprogrammbetrieb4 1975 VLSI, LAN Mehrzugangsbetrieb5 1985 ULSI, RISC Massenparallelbetrieb? 1995 WLAN, RFID, SoC ?

Legende: MSI, LSI, VLSI, ULSI — medium, large, very large, ultra large scale integrationLAN — local area network (Ethernet)WAN — wide area network (Arpanet)WLAN — wireless LANRISC — reduced instruction set computerRFID — radio frequency identification (Funkerkennung)SoC — system on chip


Am Anfang war das Feuer. . .

ENIAC (electronic numerical integrator and computer), 1945 [18]

A small amount of time is required inpreparing the ENIAC for a problem bysuch steps as setting program switches,putting numbers into the functiontable memory by setting its switches, andestablishing connections between unitsof the ENIAC for the communication ofprogramming and numerical information.(Pressemitteilung, DoD, 1946)

elektronischer Allzweckrechner von 30 Tonnen Gewicht15m × 3m × 5m große Zentraleinheit, 30m lange Frontplattefür seinen Betrieb waren 18 000 Röhren zuständigdie elektrische Anschlussleistung belief sich auf etwa 174 000Watt


Gliederung

Einführung



Zusammenfassung

c©wosch SP (SS 2015, B – VII.1) 2. Einprogrammbetrieb VII.1/8

LochkartenverarbeitungHermann Holerith (1860–1929),Begründer der maschinellenDatenverarbeitung. IBM ließ sich1928 das Format patentieren: 80Spalten, 12 Zeilen und rechteckigeLöcher an den Schnittpunkten.

Ziffernlochkarte (numeric punch card)Datenaufzeichnung durch Lochung (Loch 7→ 1, kein Loch 7→ 0)

Dezimalzahlen werden mit einer Lochung dargestelltBuchstaben und Sonderzeichen mit zwei oder dreinegative Vorzeichen ggf. durch eine Lochung in Zeile 11

manuell ca. 15 000 Zeichen/h, maschinell 4 000–10 000 Karten/h

HinweisAlternativ kamen auch Lochstreifen (punched [paper] tape) zumEinsatz, mit ähnlichen Leistungsmerkmalen.c©wosch SP (SS 2015, B – VII.1) 2.1 Einprogrammbetrieb –Manuelle Rechnerbestückung VII.1/9

Manuelle Bestückung des Rechnersvollständige Kontrolle beim Programmier- oder Bedienpersonal11. Programme mit Lochkartenstanzer (card puncher) ablochen2. Übersetzerkarten in den Lochkartenleser (card reader) geben3. Lochkartenleser durch Knopfdruck starten4. Programmkarten (zur Übersetzung) in den Kartenleser einlegen5. Eingabekarten in den Kartenleser einlegen6. Leere Lochkarten für die Ausgabe in den Kartenstanzer einlegen7. Ausgabekarten in den Kartenleser des Druckers einlegen8. Ergebnisse der Programmausführung vom Drucker abholen

Problem:Urlader (z.B. Lochkartenleseprogramm) in den Rechner einspeisen

HinweisWenigstens einen großen Vorteil hätte diese Betriebsart auch heutenoch: man überlegt sich Programme sorgfältig und interpretiert sieselbst, bevor ihre Eingabe in den Rechner erfolgt.

1„Operator“: ein Berufsbild, dass es in der Form heute nicht mehr gibt.c©wosch SP (SS 2015, B – VII.1) 2.1 Einprogrammbetrieb –Manuelle Rechnerbestückung VII.1/10

Lochkartenleseprogramm Urlader (bootstrap loader)

Rechnersystem durch Ureingabe (bootstrap) laden:1. Bitmuster einer Speicherwortadresse über Schalter einstellen

die Adresse der nächsten zu beschreibenden Stelle im Hauptspeicher2. den eingestellten Adresswert in den PC der CPU laden3. Bitmuster für den Speicherwortinhalt über Schalter einstellen

ein Befehl, ein Direktwert oder eine Operandenadresse des Programms4. den eingestellten Datenwert an die adressierte Stelle laden

Problem:Bedienung, Mensch, Permanenz

HinweisHeute liegen Urlader nicht-flüchtig im Speicher (ROM/EPROM bzw.flash). Sie starten automatisch, wenn der Rechner angeschaltet undhochgefahren oder, während des Betriebs, manuell oder automatischzum Neustart (restart) bzw. Zurücksetzen (reset) gezwungen wird.

c©wosch SP (SS 2015, B – VII.1) 2.1 Einprogrammbetrieb –Manuelle Rechnerbestückung VII.1/11

Automatisierte Bestückung des Rechners

Dienstprogramme sind abrufbereit im Rechnersystem gespeichert:Systembibliothek, „Datenbank“ (Dateiverwaltung)

Anwendungsprogramme fordern Dienstprogramme explizit an:spezielle Steuerkarten sind dem Lochkartenstapel hinzugefügt

Systemkommandos, die auf eigenen Lochkarten kodiert sindAnforderungen betreffen auch Betriebsmittel (z.B. Speicher, Drucker)

der erweiterte Lochkartenstapel bildet einen Auftrag (job)an einen Kommandointerpretierer (command interpreter)formuliert als Auftragssteuersprache (job control language, JCL)

die Programmausführung erfolgt ohne weitere Interaktion

Problem:vollständige Auftragsbeschreibung (inkl. Betriebsmittelbedarf)

HinweisEignet sich (nach wie vor) zur Bewältigung von „Routineaufgaben“.

c©wosch SP (SS 2015, B – VII.1) 2.2 Einprogrammbetrieb –Automatisierte Rechnerbestückung VII.1/12

Auftragssteuersprache

FORTRAN Monitoring System, FMS [9], um 1957wird zuweilen auch als „erstes Betriebssystem“ bezeichnet

*JOB, 42, ARTHUR DENT*XEQ*FORTRAN

Programmkarten{

*DATA

Datenkarten

*END

c©wosch SP (SS 2015, B – VII.1) 2.2 Einprogrammbetrieb –Automatisierte Rechnerbestückung VII.1/13

Residentes Steuerprogramm resident monitor

hauptspeicherresidente Systemsoftware, zur Auftragssteuerung:Kommandointerpreter, Lochkartenleseprogramm, E/A-ProzedurenSystemprogramme, die ein „embryonales Betriebssystem“ bilden

Solitär: einzelstehende und getrennt übersetzte Programmeinheit, dieverschiedenartig vom Anwendungsprogramm entkoppelt ist

Einsprungtabelle (jump table)partielle Interpretation von Monitoraufrufengetrennte/partitionierte reale Adressräume (Schutzgatter)Arbeitsmodi (System-/Benutzermodus, privilegiert/unprivilegiert)

Problem:Arbeitsgeschwindigkeit der Peripherie, sequentielle Ein-/Ausgabe

HinweisHeute ist diese Funktionseinheit noch in dem „basic input/outputsystem“ (BIOS) präsent, mit dem nahezu jeder Rechner ausgestattetist und das nach wie vor grundlegende Aufgaben, die nicht nur zumUrladezeitpunkt anfallen, übernimmt.c©wosch SP (SS 2015, B – VII.1) 2.2 Einprogrammbetrieb –Automatisierte Rechnerbestückung VII.1/14

Adressraumschutz durch Abteilung fencing

ein Schutzgatter (fence) trennt den vom residenten Steuerprogrammund vom transienten Programm belegten Hauptspeicherbereich

Anwendungsprogramme werden komplett, d.h. statisch gebundendas Schutzgatter entspricht einer unveränderlichen, realen SpeicheradresseRelokationskonstante beim Binden, Ladeadresse für die Programme

ggf. ist gewisse Flexibilität durch ein Schutzgatterregister gegebenveränderliche, reale Speicheradresse; programmierbarer WertRelokationsvariable beim Binden, (zur Basis 0) relative Programmadressenein verschiebender Lader platziert das Programm im Hauptspeicher

innerhalb der (Anwendungs-) Partition, die am Schutzgatter startetoder endet, ist dynamischer Speicher begrenzt zuteilbar

d.h., in der oberen oder unteren Hälfte des Hauptspeichersder Monitor selbst betreibt jedoch nur statische Speicherverwaltung

Problem:übergroße und statisch gebundene (vollständige) Anwendungsprogramme

HinweisGeschützt wird der Monitor, nicht jedoch das Anwendungsprogramm.c©wosch SP (SS 2015, B – VII.1) 2.3 Einprogrammbetrieb – Schutzvorkehrungen VII.1/15

Schutzgatterregister I fence register

Kontrollprogramm(Monitor)

CPU0000

Hauptspeicher

1FFF

0300

02FF

Schutzgatter

Schutzgatterregister

0300

unbelegt

Anwendungs−programm

Arbeitsmodinur im unprivilegierten Modus istdas Schutzgatter aktivnur im privilegierten Modus sindÄnderungen am Inhalt desSchutzgatterregisters erlaubt

HinweisEs erfolgt die Partitionierung des realen Adressraums. Läuft jedochdie CPU im privilegierten Modus, umfasst der Monditoradressraumden Adressraum des Anwendungsprogramms. Ein ähnliches Modelldes virtuellen Adressraums verfolgen heute Linux und Windows.c©wosch SP (SS 2015, B – VII.1) 2.3 Einprogrammbetrieb – Schutzvorkehrungen VII.1/16

Schutzgatterregister II Operationsprinzip

reale Adresse<

Grenzwert

nein

ja

Schutzgatter

reale Adresse

Zugriffsfehler

ein Zugriffsfehler führt zum Abbruch der Programmausführungsynchrone Programmunterbrechung, Trap

Problem:„interne Fragmentierung“: Zugriff auf unbelegten Bereich (false positive)

HinweisDieses Zugriffsproblem ist Merkmal einer jeden seitennummeriertenTechnik in Bezug auf den vom Programm unbelegten Bereich einerSeite, der jedoch im Adressraum gültig ist.c©wosch SP (SS 2015, B – VII.1) 2.3 Einprogrammbetrieb – Schutzvorkehrungen VII.1/17

Abgesetzter Betrieb I

Berechnung erfolgt getrennt von Ein-/Ausgabe (off-line)Satellitenrechner zur Ein-/Ausgabe mit „langsamer Peripherie“

Kartenleser, Kartenstanzer, DruckerEin-/Ausgabedaten werden über Magnetbänder transferiert

Hauptrechner zur Berechnung mit „schneller Peripherie“Be-/Entsorgung des Hauptspeichers auf Basis von Bandmaschinendadurch erheblich verkürzte Wartezeiten bei der Ein-/Ausgabe

Problem:sequentieller Bandzugriff, feste Auftragsreihenfolge

HinweisHeute finden zusätzlich Wechselplatten Verwendung. Auch die Idee,die Ausführung von Systemfunktionen auf eigens dafür bereitgestellteRecheneinheiten auszulagern, hat durch Multiprozessoren und insb.auch mehrkernige Prozessoren eine Erneuerung erfahren [2, 19].

c©wosch SP (SS 2015, B – VII.1) 2.4 Einprogrammbetrieb –Aufgabenverteilung VII.1/18

Abgesetzter Betrieb IIdedizierte Rechner/Geräte für verschiedene Arbeitsphasen:

Phase Medium Rechner

Text/Daten ⇒ LochkartenEingabe Lochkarten ⇒ Magnetband Satellitenrechner

↓ ↓Magnetband ⇒ HauptspeicherVerarbeitung Hauptspeicher ⇒ Magnetband Hauptrechner

↓ ↓Magnetband ⇒ LochkartenAusgabe Daten ⇒ Drucker Satellitenrechner

Problem:programmierte Ein-/Ausgabe: bei Satelliten-und Hauptrechner

Hinweis (Programmierte E/A)Ein-/Ausgabe, die ausschließlich durch prozessorseitige Aktionenvorangetrieben wird und damit eine CPU voll in Anspruch nimmt.c©wosch SP (SS 2015, B – VII.1) 2.4 Einprogrammbetrieb –Aufgabenverteilung VII.1/19

Überlappte Ein-/Ausgabe

durch asynchrone Programmunterbrechungen [8, S. 225–227] dietechnische Voraussetzung für gleichzeitige Pozesse schaffen [1, 17]

die E/A-Geräte fordern der CPU weitere E/A-Aufträge ab, plötzlichE/A und Berechnung desselben Programms überlappen sich

Speicherdirektzugriff (direct memory access, DMA, [10]) ersetzt diebislang gebräuchliche programmierte Ein-/AusgabeE/A-Kanäle, die unabhängig von der CPU arbeiten

d.h., Zugriffskanäle zwischen einem E/A-Gerät und dem HauptspeicherDatentransfer erfolgt durch ein Kanalprogramm (cycle stealing, [7, 5])

ermöglicht nebenläufige Ausführung von Gerätetreiberprogrammenund dem (einen) Hauptprogramm

Kooperation und Konkurrenz gleichzeitiger Prozesse sind zu koordinierend.h., Erfordernis zur Synchronisation [4, S. 28–33]

Problem:Leerlauf beim Auftragswechsel


Überlappte Auftragsverarbeitung single-stream batch monitor

Grundlage ist ein als Verarbeitungsstrom ausgelegter Stapel (batch)sequentiell auszuführender Programme/Aufträge

während Ausführung eines Auftrags wird der nachfolgende Auftrag bereitsin den Hauptspeicher eingelesen (Zwischenpuffern)Programme werden im Vorgriffsverfahren (prefetching) abgearbeitet

Auftragseinplanung (job scheduling) geschieht im Hintergrund, abermitlaufend (on-line) zur gegenwärtigen Programmausführung

statische (off-line) Einplanung nach unterschiedlichsten KriterienAnkunftszeit, erwartete Laufzeit, erwarteter Betriebsmittelbedarf

die Aufträge werden dazu im Hintergrundspeicher zusammengestelltwahlfreier Zugriff (z.B. Plattenspeicher [6]) beschleunigt die Vorgriffe

Problem:Hauptspeicher, Monopolisierung der CPU, Leerlauf bei Ein-/Ausgabe

Hinweis (Monopolisierung)Jedes Programm bekommt die CPU exklusiv zugewiesen und gibt sieerst bei vollendeter Ausführung freiwillig ab („run to completion“).c©wosch SP (SS 2015, B – VII.1) 2.4 Einprogrammbetrieb –Aufgabenverteilung VII.1/21

Abgesetzte Ein-/Ausgabe IProgrammausführung ist eine periodische Abfolge von zwei Phasen:CPU-Stoß Aktionen mit ausschließlich Berechnungen („CPU burst“)

jede einzelne Aktion verläuft vergleichsweise schnellE/A-Stoß Aktionen mit ausschließlich Ein-/Ausgabe („I/O burst“)

jede einzelne Aktion verläuft vergleichsweise langsamCPU- und E/A-Stoß lassen sich durch Puffer zeitlich entkoppeln [14]

ein CPU-Stoß endet mit der Pufferung das Auftrags für einen E/A-Stoß,er setzt nur einen E/A-Auftrag ab und dann seine Ausführung fortein E/A-Stoß läuft im Hintergrund der Ausführung des CPU-Stoßes ab,indem ein gepufferter E/A-Auftrag zur Ausführung gebracht wird

Problem:Leerlauf im Wartezustand: konsumier-/wiederverwendbare Betriebsmittel

Hinweis (Spooling (simultaneous peripheral operations online))Bewerkstelligt durch Systemprogramme einerseits zum Absetzen undandererseits zur Überwachung/Steuerung der Verarbeitung von Ein-oder Ausgabeaufträgen (in UNIX: lpr(1) bzw. lpd(8)).c©wosch SP (SS 2015, B – VII.1) 2.4 Einprogrammbetrieb –Aufgabenverteilung VII.1/22

Abgesetzte Ein-/Ausgabe IIüberlappte E/A befüllt/entleert Datenpuffer, 1./2. DMA zwischen:

Puffer im Vordergrundspeicher (primary/main store) undPuffer im Hintergrundspeicher (secondary/backing store)

effektive E/A in Bezug auf die Endgeräte operiert dann mit den imHintergrundspeicher gepufferten Daten, 2. und 3. DMA

beansprucht dazu jedoch die CPU und nutzt wiederum überlappte E/A

(Hauptspeicher)

Puffer Puffer

Puffer E/A−Gerät

(Zwischenlager)

Hintergrundspeicher

2. DMA

Vordergrundspeicher

Peripherie

CPU

1. DMA

3. DMA

Hinweis (Abgesetzter Betrieb)Hier sind die im Hauptspeicher liegenden Puffer dem Haupt- (oben)und Satellitenrechner (unten) zugeordnet.


Gliederung

Einführung



Zusammenfassung

c©wosch SP (SS 2015, B – VII.1) 3.Mehrprogrammbetrieb VII.1/24

Maßnahmen zur Leistungssteigerungin Raum vermöge Mehrprogrammbetrieb (multi-programming) undZeit mittels Simultanverarbeitung (multiprocessing)

Multiplexen der CPU zwischen mehreren Programmen2Nebenläufigkeit (concurrency)

Abschottung der sich in Ausführung befindlichen ProgrammeAdressraumschutz (address space protection)

Überlagerung unabhängiger ProgrammteileSegmentierung (segmentation, [15]) — im Sinne von „Aufteilung“

beides auch Maßnahmen eines Betriebssystems zur Unterstützung derbesseren Strukturierung von Programmen:

If we believe in data structures, we must believe inindependent (hence simultaneous) processing.For why else would we collect items within a structure?Why do we tolerate languages that give us the one withoutthe other? (Alan Perlis [16, Epigram 68])

2Zunächst als „befremdliches Ergebnis“ von Interrupts angesehen [12, S. 43].c©wosch SP (SS 2015, B – VII.1) 3.1Mehrprogrammbetrieb –Multiplexverfahren VII.1/25

Aktives Warten Leerlauf (idle state)

überlappte Ein-/Ausgabe bedeutet die parallele Ausführung von CPU-und E/A-Stößen, im Einprogrammbetrieb jedoch nicht immer:

idle

Programm

CPU

E/A

EreignisverlaufStoß

Z4.

3.1.2. 5.

1. Programm Z löst einen zum CPU-Stoß nebenläufigen E/A-Stoß aus2. die Beendigung des E/A-Stoßes wird durch eine Unterbrechung angezeigt3. der Unterbrechungshandhaber3 löst einen weiteren E/A-Stoß aus4. Z muss auf E/A warten, dem logischen Verlauf nach endet der CPU-Stoß5. die CPU ist untätig (idle) bis der E/A-Stoß endet, ein CPU-Stoß beginntProblem:

Durchsatz, Auslastung (CPU, E/A-Geräte)3interrupt handler

c©wosch SP (SS 2015, B – VII.1) 3.1Mehrprogrammbetrieb –Multiplexverfahren VII.1/26

Multiplexen des Prozessorsdie Auslastung der CPU steigt, wenn die Wartezeit eines Programmsals Laufzeit eines anderen Programms nutzbar ist

aktives Warten (busy waiting) ist grundsätzlich unproduktiv und beschertder CPU nur kostbare Leerlaufzeit (idle time)im Falle eines alternativen Ausführungsstrangs ist eine solche Wartephaseallerdings als Produktivzeit nutzbardazu ist die CPU zur Aufnahme eines solchen Ausführungsstrangs (einesanderen Programms) umzuschalten ; „passives Warten“

der Umschaltmechanismus selbst ist unabhängig von den konkretauszuführenden Programmen, er ist generisch auslegbar

dazu wird von dem „Programm in Ausführung“ abstrahiert, der Prozesseingeführt, dessen Inkarnation einen eigenen Prozessorzustand besitztUmschalten der CPU bedeutet dann lediglich, den Prozessorzustand einesanderen Prozesses zu aktivieren

Hinweis (Leerlaufzeit)Es gibt jedoch Fälle, wo aktives Warten auf einen Ereigniseintritt dieeffiziente Alternative darstellt: Umschaltzeit > erwartete Wartezeit.c©wosch SP (SS 2015, B – VII.1) 3.1Mehrprogrammbetrieb –Multiplexverfahren VII.1/27

Passives Warten IProgrammverarbeitung im Mehrprozessbetrieb:

Prozess

CPU

Stoß Ereignisverlauf

3.

4. 6.

5.

X

Y

E/A

CPU

E/A

Umschaltzeiten

1.

2.

Prozesse X und Y als Produkte desselben nichtsequentiellen Programmsoder verschiedener sequentieller Programmeder CPU-Stoß von Prozess Y wird durch Beendigung des E/A-Stoßes vonProzess X unterbrochen und umgekehrtsolche Unterbrechungsszenarien rufen unvorhersehbare Interferenz hevor,die für zeitabhängige Prozesse kritisch sein kann


Passives Warten II

Ablauf der umseitig (auf S. 28) dargestellten Programmverarbeitungim Prozessormultiplexverfahren:1. Prozess X löst einen E/A-Stoß und beendet seinen CPU-Stoß2. Prozess Y wird eingelastet und beginnt seinen CPU-Stoß3. Beendigung des E/A-Stoßes von Prozess X unterbricht Prozess Y

die Unterbrechungsbehandlung überlappt sich mit Prozess Y4. Prozess Y löst einen E/A-Stoß und beendet seinen CPU-Stoß5. Prozess X wird eingelastet und beginnt seinen CPU-Stoß6. Beendigung des E/A-Stoßes von Prozess Y unterbricht Prozess X

die Unterbrechungsbehandlung überlappt sich mit Prozess XEinlastung (dispatching) eines Prozesses ist der Moment, in dem dieCPU umgeschaltet wird

den Prozessorzustand des die CPU abgebenden Prozesses sichern und desdie CPU erhaltenden Prozesses (wieder) herstellendas Betriebssystem vollzieht genau damit den Prozesswechsel

Problem:Interferenz, Adressraumschutz, Koordination


Adressraumschutz Abschottung von Programmen

bei mehr als einem Programm, das neben dem residenten Monitor imHauptspeicher liegen muss, reichen Schutzgatter nicht

jedes einzelne Programm ist von anderen Programmen zu isolierender Bindungszeitpunkt, zu dem Namen mit Speicherorten verknüpftwerden, begründet verschiedene Schutztechniken:vor Laufzeit ; Schutz durch Eingrenzung

Programme laufen (weiterhin) im realen Adressraumein verschiebender Lader besorgt die Bindung zur Ladezeitdie CPU (bzw. MPU) überprüft die realen Adressen zur Ausführungszeit

zur Laufzeit ; Schutz durch Segmentierung [3]jedes Programm läuft in seinem eigenen logischen Adressraumder Lader bestimmt die Bindungsparameter (reale Basisadresse)die CPU (bzw. MMU) besorgt die Bindung zur Ausführungszeitdynamische Programmumlagerung (program relocation, [13])

HinweisIn beiden Fällen ist der Namensraum eines Programms relativ zu derlogischen Anfangsadresse 0 ausgerichtet.c©wosch SP (SS 2015, B – VII.1) 3.2Mehrprogrammbetrieb – Schutzvorkehrungen VII.1/30

Adressraumschutz durch Eingrenzung

Begrenzungsregister (bounds register) legen die Unter-/Obergrenzeeines Programms im realen Adressraum fest

jedem Programm wird ein solches Wertepaar spätestens zur Ladezeit festzugeordnet und seiner Prozessinkarnation zur „Einzäunung“ mitgegeben

die Softwareprototypen dieser Register der Adressüberprüfungshardwareverwaltet als Attribute des Prozesskontrollblocks

bei Prozesseinlastung werden die Hardwareprototypen dieser Register mitden in den Softwareprototypen vermerkten Werten definiert

wodurch der Hauptspeicherbereich des Prozesses „freigeschaltet“ wirdzu einem Zeitpunkt ist damit immer nur ein solcher Bereich freigegeben

innerhalb des durch die Begrenzungsregister festgelegten Bereichs istdynamischer Speicher bedingt zuteilbar

der Bedarf dafür muss jedoch spätestens zum Ladezeitpunkt bekannt seindas Betriebssystem kann nur statische Speicherverwaltung betreiben

Problem:Fragmentierung, Verdichtung

c©wosch SP (SS 2015, B – VII.1) 3.2Mehrprogrammbetrieb – Schutzvorkehrungen VII.1/31

Begrenzungsregister I bounds register

BFFF 6000

Begrenzungs−adressen

FFFF

Anwendungsprogramm 3


freigeschaltet

FFFF D000

3FFF 0000 0000

5FFF 4000

BFFF 6000Betriebssystem


unbelegt

HauptspeicherCPU

Begrenzungsregister

konsequente Umsetzung des Modells ist es, Anwendungsprogrammeauch vor direkten Zugriffen durch das Betriebssystem zu schützen

in dem Fall verfügt jeder Arbeitsmodus über eigene Begrenzungsregisterein Arbeitsmoduswechsel aktiviert das jeweilige Registerpaar implizit

HinweisHeute in Form einer „memory protection unit“ (MPU) gebräuchlich.c©wosch SP (SS 2015, B – VII.1) 3.2Mehrprogrammbetrieb – Schutzvorkehrungen VII.1/32

Begrenzungsregister II Operationsprinzip

Untergrenze Obergrenze

nein nein

ja ja

Begrenzungsregister

Zugriffsfehler

< >reale Adresse reale Adresse


Problem wie beim Schutzgatterkonzept (vgl. S. 17), zusätzlich:„externe Fragmentierung“, d.h., unbelegte Hauptspeicherbereiche

Hinweis (Externe Fragmentierung)Freie Speicherbereiche sind jeder für sich zu klein, insgesamt jedochgroß genug für ein Programm. Sie bleiben dennoch nutzlos, da sie imrealen Adressraum nicht linear zusammenhängend angeordnet sind.c©wosch SP (SS 2015, B – VII.1) 3.2Mehrprogrammbetrieb – Schutzvorkehrungen VII.1/33

Adressraumschutz durch SegmentierungBasis-/Längenregister (base/limit register) legen Segmentort sowie-größe eines Programms im realen Adressraum fest

jedem Programm wird ein solches Wertepaar zur Ladezeit zugeordnet undseiner Prozessinkarnation mitgegeben

die Softwareprototpypen dieser Register der Adressverschiebungshardwareverwaltet als Attribute des Prozesskontrollblocks

bei Prozesseinlastung werden die Hardwareprototypen dieser Register mitden in den Softwareprototypen vermerkten Werten definiert

wodurch der Hauptspeicherbereich des Prozesses „aktiviert“ wirdzu einem Zeitpunkt ist damit immer nur ein solches Segment freigegeben

innerhalb des durch die Basis-/Längenregister definierten Bereichs istdynamischer Speicher bedingt zuteilbar

der Bedarf dafür braucht erst zur Ausführungszeitpunkt bekannt zu seinist die maximale Größe nicht erreicht, kann das Segment expandiert werdenverhindert dies ein angrenzendes Segment, wird das Programm umgelagertggf. wird der Hauptspeicher für einen passenden Bereich verdichtet

das Betriebssystem kann dynamische Speicherverwaltung betreibenProblem:

externe Fragmentierung, Hauptspeichergrößec©wosch SP (SS 2015, B – VII.1) 3.2Mehrprogrammbetrieb – Schutzvorkehrungen VII.1/34

Basis-/Längenregister I base/limit register

D000

16384 0000


aktiv

CPU

6000

Basisadresse

24576

Länge

Basis−/Längenregister

FFFF

0000

8192 4000

24576 6000Betriebssystem


unbelegt

Hauptspeicher


12288

das Betriebssystem ist in einem eigenen Segment gekapselt, durchBasis-/Längenregister für den privilegierten ArbeitsmodusHinweis (Segmentierende MMU)Kennzeichnend für eine „memory management unit“ (MMU), aberwie hier gezeigt nur zur heute eher unüblichen Isolation eines ganzenausführbaren Programms durch ein einzelnes Segment.c©wosch SP (SS 2015, B – VII.1) 3.2Mehrprogrammbetrieb – Schutzvorkehrungen VII.1/35

Basis-/Längenregister II Operationsprinzip

Länge Basisadresse

nein

Basis−/Längenregister

Zugriffsfehler

ja+<logische Adresse reale Adresse

Relokation


Problem:Unisegmentansatz, d.h., pro Programm nur ein Segment

Hinweis (Relokation)Die MMU verschiebt die bei Programmausführung erzeugte effektivelogische Adresse um die Segmentbasisadresse (Relokationskonstante).Der Basisregisterinhalt ist zwischen den einzelnen Ausführungsphasenveränderlich, das Programm kann somit umgelagert werden.c©wosch SP (SS 2015, B – VII.1) 3.2Mehrprogrammbetrieb – Schutzvorkehrungen VII.1/36

Überlagerungstechnik I overlay [15]

ein einzelnes Programm ausführen zu können, obwohl es in seinerGesamtheit nicht in den Hauptspeicher passt:i es ist überhaupt zu groß für den Hauptspeicher, auch falls es als einzigesAnwendungsprogramm zur Ausführung kommen soll, oder

ii es ist größer als die einem Anwendungsprogramm statisch zur Verfügungstehende Hauptspeicherpartition

dazu wird das Programm in hinreichend kleine Teile zergliedert, dienicht ständig im Hauptspeicher vorhanden sein müssen

dies betrifft sowohl den Text- als auch den Datenbereichnicht benötigte Teile liegen abrufbereit im Hintergrundspeichersie werden bei Bedarf nachgeladen, überlagern nicht mehr benötigte Teile

das Nachladen ist programmiert, d.h., in dem Programm festgelegt,die Entscheidung dazu fällt zur Programmlaufzeit

ein Programm löst dynamisches Laden von Überlagerungen aus

Problem:„optimale“ Überlagerungsstruktur, manueller Ansatz

c©wosch SP (SS 2015, B – VII.1) 3.3Mehrprogrammbetrieb –Dynamisches Laden VII.1/37

Überlagerungstechnik IIHauptspeicherbedarf für ein unzerteiltes Programm:statisch

A B D E F G H IC

Einsparung von Hauptspeicher zur Programmlaufzeit:dynamisch eingelagert

A B E

F

C

D G

ABE

ABF

AC

ADGH

ADI

H

I

nicht alle Bestandteile (A – I) eines Programms müssen gleichzeitig imHauptspeicher vorliegen, damit das Programm auch ausführbar istwann welches Programmteil zur Ausführung gelangt, legt der dynamischeAblauf des Programms selbst fest


Überlagerungsstruktur eines ProgrammsProgramme, die Überlagerungen enthalten, sind (grob) dreigeteilt:i ein hauptspeicherresidenter Programmteil (root program), repräsentiertdas Überlagerungen aufrufende Hauptprogramm

ii mehrere in Überlagerungen zusammengefasste Unterprogramme, dieihrerseits Überlagerungen aufrufen können

iii ein gemeinsamer Datenbereich (common section), zur Speicherungüberlagerungsübergreifender Information

Überlagerungen sind das Ergebnis einer Programmzerlegung zurProgrammier-, Übersetzungs- und/oder Bindezeit

manuelle bzw. automatisierte Abhängigkeitsanalyse des ProgrammsAnzahl und Größe von Überlagerungen werden statisch festgelegtlediglich aktivieren (d.h. laden) von Überlagerungen ist dynamisch

HinweisÜberlagerungen sind Teile eines Programms und keine Elemente einermehreren Programmen gemeinsamen Bibliothek (shared library) oderDLL (dynamic link library).c©wosch SP (SS 2015, B – VII.1) 3.3Mehrprogrammbetrieb –Dynamisches Laden VII.1/39

Programm-/Adressraumstruktur

Organisation des Prozessadressraums im Hauptspeicher:

Hintergrundspeicher

Verschnitt

Ver

schn

itt

shared

Hauptprogramm

gemeinsame Daten

Überlagerungsbereich

Überlagerungen

root

overlay overlay overlay

Vordergrundspeicher

Problem:Verkettungstechnik, kein Zurückschreiben von Überlagerungen


Multistapelbetrieb

Simultanverarbeitung (multiprocessing) mehrerer Auftragsströmedas Betriebssytem als „multi-stream batch monitor“

echt/quasi parallele Verarbeitung von Auftragsströmen sequentiellerProgramme, gleichzeitig, im Multiplexverfahren

sequentielle Ausführung der Programme desselben Auftragstapels„wer [innerhalb des Stapels] zuerst kommt, mahlt zuerst“. . .

nichtsequentielle Ausführung der Programme verschiedener Auftragstapeldie Stapelwechsel kommen kooperativ (cooperative), verdrängend(preemptive) oder als Kombination von beiden zustande

kooperativ bei (programmierter) Ein-/Ausgabe, also bei Beendigung desCPU-Stoßes eines Prozesses, und am Programmendeverdrängend bei Ablauf einer Frist (time limit), innerhalb welcher dieAusführung eines jeweiligen Programms abgeschlossen sein muss

Problem:interaktionsloser Betrieb, Mensch/Maschine-Schnittstelle

c©wosch SP (SS 2015, B – VII.1) 3.4Mehrprogrammbetrieb – Simultanverarbeitung VII.1/41

Gliederung

Einführung



Zusammenfassung

c©wosch SP (SS 2015, B – VII.1) 4. Zusammenfassung VII.1/42

Resümee . . . immer nach dem gleichen Schema zu verrichtende Arbeit

Stapelbetrieb meint die sequentielle Abwicklung von Aufgabenanfangs manuelle Bestückung des Rechners durch Programmierpersonalspäter automatisierte Bestückung mittels Kommandointerpreter

Programmierer organisier(t)en ihren Auftragsstapel mittels SteuerkartenOperateure übern{a,e}hmen die manuelle Bestückung des Rechners

Aufgabenverteilung dehnt(e) sich auch auf systeminterne Abläufe ausabgesetzter Betrieb, überlappte Ein-/Ausgabeüberlappte Auftragsverarbeitung, abgesetzte Ein-/Ausgabe

Mehrprogrammbetrieb hält mehrere Programme im HauptspeicherHauptspeicherknappheit wird durch dynamisches Laden begegnetder Prozessor wird im Multiplexverfahren betrieben: ProzesseSchutzvorkehrungen schotten Prozessadressräume voneinander abum das Rechensystem damit sicher in Simultanbetrieb fahren zu können

nach wie vor bestens für Routinearbeit geeignet, wobei:nur Operateure interaktiven Zugang zum Rechensystem bek{a,om}mendie Anwender mit dem Rechensystem jedoch interaktionslos arbeit(et)en

c©wosch SP (SS 2015, B – VII.1) 4. Zusammenfassung VII.1/43

Literaturverzeichnis I

[1] Bell, C. G. ; Newell, A. :Computer Structures: Readings and Examples.New York, NY, USA : McGraw-Hill Inc., 1971. –668 S.

[2] Brüning, U. ; Giloi, W. K. ; Schröder-Preikschat, W. :Latency Hiding in Message-Passing Architectures.In: Siegel, H. J. (Hrsg.): Proceedings of the 8th International Symposium onParallel Processing, April 26–29, 1994, Cancún, Mexico.Washington, DC, USA : IEEE Computer Society, 1994. –ISBN 0–8186–5602–6, S. 704–709

[3] Dennis, J. B.:Segmentation and the Design of Multiprogrammed Computer Systems.In: Journal of the ACM 12 (1965), Okt., Nr. 4, S. 589–602

[4] Dijkstra, E. W.:Communication with an Automatic Computer, Universiteit van Amsterdam, Diss.,Okt. 1959

[5] IBM:Data Processing Machine Including Program Interrupt Feature.U.S. Pat. No. 3,319,230 (1967), 1956

c©wosch SP (SS 2015, B – VII.1) 4.1 Zusammenfassung –Bibliographie VII.1/44

Literaturverzeichnis II

[6] IBM:IBM 503 RAMAC.http://www-03.ibm.com/ibm/history/exhibits/storage/storage_PH0305.html, 1956

[7] IBM:709 Data Processing System.http://www-03.ibm.com/ibm/history/exhibits/mainframe/mainframe_PP709.html,Jan. 1957

[8] Knuth, D. E.:The Art of Computer Programming. Bd. 1: Fundamental Algorithms.Reading, MA, USA : Addison-Wesley, 1973

[9] Larner, R. A.:FMS: The FORTRAN Monitor System.In: Butler, M. K. (Hrsg.) ; Brown, J. M. (Hrsg.) ; American Federation ofInformation Processing Societies, Inc. (Veranst.): 1987 Proceedings of the NationalComputer Conference, June 15–18, 1987, Chicago, Illinois, USA Bd. 56 AmericanFederation of Information Processing Societies, Inc., AFIPS Press, 1987, S. 815–820


Literaturverzeichnis III

[10] Leiner, A. L.:System Specifications for the DYSEAC.In: Journal of the ACM 1 (1954), Apr., Nr. 2, S. 57–81

[11] Leiner, A. L. ; Alexander, S. N.:System Organization of DYSEAC.In: IRE Transactions on Electronic Computers EC-3 (1954), März, Nr. 1, S. 1–10

[12] Loopstra, B. J.:The X-1 Computer.In: The Computer Journal 2 (1959), Nr. 1, S. 39–43

[13] McGee, W. C.:On Dynamic Program Relocation.In: IBM Systems Journal 4 (1965), Sept., Nr. 3, S. 184–199

[14] Mock, O. ; Swift, C. J.:The Share 709 System: Programmed Input-Output Buffering.In: Journal of the ACM 6 (1959), Apr., Nr. 2, S. 145–151

[15] Pankhurst, R. J.:Operating Systems: Program Overlay Techniques.In: Communications of the ACM 11 (1968), Febr., Nr. 2, S. 119–125


Literaturverzeichnis IV

[16] Perlis, A. J.:Epigrams on Programming.In: SIGPLAN Notices 17 (1982), Nr. 9, S. 7–13

[17] Smotherman, M. :Interrupts.http://www.cs.clemson.edu/~mark/interrupts.html, Jul. 2008

[18] US War Department, Bureau of Public Relations:For Radio Broadcast: Physical Aspect, Operation of ENIAC are Described.http://americanhistory.si.edu/collections/comphist/pr4.pdf, Febr. 1946

[19] Wentzlaff, D. ; Agarwal, A. :Factored Operating Systems (fos): The Case for a Scalable Operating System forMulticores.In: ACM SIGOPS Operating Systems Review 43 (2009), Apr., Nr. 2, S. 76–85


Rechnerbetrieb am RRZE um 1973 4

4http://www.rrze.uni-erlangen.de/wir-ueber-uns/publikationen/das-rrze-der-film.shtml

c©wosch SP (SS 2015, B – VII.1) 5.1 Anhang –Das RRZE — Der Film VII.1/48

Documents

Grundlage von Betriebssystemen - FAU · 2015. 6. 30. · 1 1945 Röhre Stapelbetrieb 2 1955 Halbleiter, Gatter Echtzeitbetrieb 3 1965 MSI/LSI, WAN Mehrprogrammbetrieb 4 1975 VLSI,