8
Betriebssysteme, Prof. Dr. Odej Kao, Zusammenfassung von Florian Schoppmann Das Copyright f¨ ur die dieser Zusammenfassung zugrunde liegenden Vorlesungsunterlagen (Skripte, Folien, etc.) liegt beim Dozenten. Dar¨ uber hinaus bin ich, Florian Schoppmann, alleiniger Autor dieses Dokuments und der genannte Dozent ist in keiner Weise verantwortlich. Etwaige Inkorrektheiten sind mit sehr großer Wahrscheinlichkeit erst durch meine Zusammenfassung/Interpretation entstanden. Zusammenfassung Betriebssysteme 1. Einf¨ uhrung 1.1 Aufgabenbereiche eines Betriebssys- tems Grobe Aufteilung: Bereitstellung von Hilfsmitteln f¨ ur Benutzer- programme Vernachl¨ assigung der genauen Benutzerkennt- nis von HWEigenschaften und spezieller SW- Komponenten, wie z.B. Ger¨ atetreiber Koordination und Vergabe der zur Verf¨ ugung stehenden Betriebsmittel an mehrere, gleich- zeitig arbeitende Benutzer Einzelaufgaben: Unterbrechungsverarbeitung, Ver- teilung (Prozessumschaltung), Betriebsmittelver- waltung, Programmallokation, Dateiverwaltung, Auftragsteuerung (Scheduling), Zuverl¨ assigkeit 1.2 Geschichte der Betriebssysteme Schl¨ usseltechniken: Multiprogramming (mehrere Applikationen im Speicher), Hardwarespeicherschutz Time Sharing (1962, MIT) Spooling (Simultaneous Peripheral Operation On Line) Virtualisierung 1.3 Unterschiedliche Arten von Betriebs- systemen Eigenschaft Netz- werk-BS Verteil- tes BS Multi- prozes- sor Verhalten wie eine virtuelle CPU? Nein Ja Ja Gleiches BS ur alle Knoten? Nein Ja Ja Anzahl Kopien des BS n n 1 Realisierung der Kommuni- kation? Gemein- same Dateien Nach- richten Gemein- samer Speicher Gemeinsame Netzwerkpro- tokolle Ja Ja Nein Nur eine Prozesswarte- schlange? Nein Nein Ja Verteilte Betriebssysteme: Netzwerk von Rechnern, bleiben dem Benutzer verborgen, Betriebssystem bestimmt, wo Programme ausgef¨ uhrt werden und wo die ben¨ otigten Daten liegen, Benutzer hat den Eindruck einer einheitlichen Computerressource Anwendungsgebiete: PCs, Echtzeit-Systeme, einge- bettete Systeme und PDAs, Chipkarten 1.4 Strukturen der Betriebssysteme Monolithische Systeme Alle Funktionen werden zu einem Objektcode kompiliert, jede Funktion kann jede andere Funktion aufrufen Geschichtete Systeme Verallgemeinerung des Strukturmodells ur monolithische BS, nur Funktionen der n¨ achsth¨ oheren Schicht aufruf- bar Virtuelle Maschinen Tats¨ achliche Ausf¨ uhrung von Systemaufrufen auf der realen HW durch Mo- nitor auf HW-Ebene Exokern Jeder Benutzer bekommt eine Kopie des darunter liegenden Computers, aber mit je- weils einem (statisch festgelegten) Teil der Ressourcen Client-Server-Systeme mit Mikrokern Kommunikation zwischen Funktionen im Kern und Benutzerraum nach Client-Server- Modell durch Nachrichten Mechanismus: Wie wird eine Aufgabe prinzipiell gel¨ ost? Policy: Was wird dabei konkret realisiert? unschenswert: Genereller Mechanismus, so dass eine Ver¨ anderung der Policies durch Anpassung von Parametern umgesetzt werden kann 1

Zusammenfassung Betriebssysteme

Embed Size (px)

Citation preview

Betriebssysteme, Prof. Dr. Odej Kao, Zusammenfassung von Florian SchoppmannDas Copyright fur die dieser Zusammenfassung zugrunde liegenden Vorlesungsunterlagen (Skripte, Folien, etc.) liegt beim Dozenten.Daruber hinaus bin ich, Florian Schoppmann, alleiniger Autor dieses Dokuments und der genannte Dozent ist in keiner Weise verantwortlich.Etwaige Inkorrektheiten sind mit sehr großer Wahrscheinlichkeit erst durch meine Zusammenfassung/Interpretation entstanden.

ZusammenfassungBetriebssysteme

1. Einfuhrung

1.1 Aufgabenbereiche eines Betriebssys-tems

Grobe Aufteilung:� Bereitstellung von Hilfsmitteln fur Benutzer-

programme� Vernachlassigung der genauen Benutzerkennt-

nis von HWEigenschaften und spezieller SW-Komponenten, wie z.B. Geratetreiber

� Koordination und Vergabe der zur Verfugungstehenden Betriebsmittel an mehrere, gleich-zeitig arbeitende Benutzer

Einzelaufgaben: Unterbrechungsverarbeitung, Ver-teilung (Prozessumschaltung), Betriebsmittelver-waltung, Programmallokation, Dateiverwaltung,Auftragsteuerung (Scheduling), Zuverlassigkeit

1.2 Geschichte der Betriebssysteme

Schlusseltechniken:� Multiprogramming (mehrere Applikationen im

Speicher), Hardwarespeicherschutz� Time Sharing (1962, MIT)� Spooling (Simultaneous Peripheral Operation

On Line)� Virtualisierung

1.3 Unterschiedliche Arten von Betriebs-systemen

Eigenschaft Netz-werk-BS

Verteil-tes BS

Multi-prozes-sor

Verhalten wieeine virtuelleCPU?

Nein Ja Ja

Gleiches BSfur alleKnoten?

Nein Ja Ja

Anzahl Kopiendes BS

n n 1

Realisierungder Kommuni-kation?

Gemein-sameDateien

Nach-richten

Gemein-samerSpeicher

GemeinsameNetzwerkpro-tokolle

Ja Ja Nein

Nur eineProzesswarte-schlange?

Nein Nein Ja

Verteilte Betriebssysteme: Netzwerk von Rechnern,bleiben dem Benutzer verborgen, Betriebssystembestimmt, wo Programme ausgefuhrt werden undwo die benotigten Daten liegen, Benutzer hat denEindruck einer einheitlichen Computerressource

Anwendungsgebiete: PCs, Echtzeit-Systeme, einge-bettete Systeme und PDAs, Chipkarten

1.4 Strukturen der Betriebssysteme

Monolithische Systeme Alle Funktionen werden zueinem Objektcode kompiliert, jede Funktionkann jede andere Funktion aufrufen

Geschichtete Systeme Verallgemeinerung desStrukturmodells fur monolithische BS, nurFunktionen der nachsthoheren Schicht aufruf-bar

Virtuelle Maschinen Tatsachliche Ausfuhrung vonSystemaufrufen auf der realen HW durch Mo-nitor auf HW-Ebene

Exokern Jeder Benutzer bekommt eine Kopie desdarunter liegenden Computers, aber mit je-weils einem (statisch festgelegten) Teil derRessourcen

Client-Server-Systeme mit MikrokernKommunikation zwischen Funktionen imKern und Benutzerraum nach Client-Server-Modell durch Nachrichten

Mechanismus: Wie wird eine Aufgabe prinzipiellgelost?

Policy: Was wird dabei konkret realisiert?Wunschenswert: Genereller Mechanismus, so dasseine Veranderung der Policies durch Anpassung vonParametern umgesetzt werden kann

1

Betriebssysteme, Prof. Dr. Odej Kao, Zusammenfassung von Florian SchoppmannDas Copyright fur die dieser Zusammenfassung zugrunde liegenden Vorlesungsunterlagen (Skripte, Folien, etc.) liegt beim Dozenten.Daruber hinaus bin ich, Florian Schoppmann, alleiniger Autor dieses Dokuments und der genannte Dozent ist in keiner Weise verantwortlich.Etwaige Inkorrektheiten sind mit sehr großer Wahrscheinlichkeit erst durch meine Zusammenfassung/Interpretation entstanden.

1.5 Fallstudie: Aufbau von WindowsNT/2000

verwendete Modelle:� (halbwegs) Client/Server Modell fur die Be-

reitstellung verschiedener Betriebssystemum-gebungen und Anwendungsprogramme

� Objektmodell fur Resourcen (Zugriff uberHandles)

� Symmetrisches Multiprocessingmit gemeinsa-mem Speicherzugriff

1.6 Fallstudie: Aufbau von Linux

� Schichtenbasiertes System� Monolithischer Kern mit Modulen� Kernaufgaben: Prozessverwaltung, Speicher-

verwaltung, Dateisystem, Ein-und Ausgabe,Systemaufrufschnittstelle, . . .

2. Prozesse

2.1 Prozesse als zentrales Konzept

Definiert durch Adressraum, Programm, ”Akti-vitatstrager“ (bspw. Thread)

Dispatcher: BS-Komponente zur Verwaltung desrealen Prozessors, verdrangt Prozesse und ladt neu-erZusammenarbeit mit dem Scheduler, der fur dieAuswahl des nachsten Prozesses zustandig ist

Prozesskontrollblock: (PCB), Datenstruktur,enthalt: PID, Zustandsinformationen (Regis-terwerte, Befehlszahler, Programmstatuswort),Kontrollinformationen (laufend, blockiert, . . . ,Eltern-Kind-Relationen, . . . )

Effiziente Organisation: Aufspaltung in Teil- (ver-kettete) Listen mit identischen Attributen (z. B.laufend, blockiert)

2.2 Ausfuhrung von Prozessen

Multiprogrammierung: Annahme: Ein Prozess ver-bringt Anteil p seiner Zeit mit Warten auf E/A-Operationen.Wkt., dass n Prozesse gleichzeitig am Warten aufE/A-Operationen sindWenn Ausnutzung der CPU 1− pn, dann ist n derGrad der Multiprogrammierung

O. Kao Betriebssysteme 2-15

Erweitertes Zustandsmodell• Swapping: Auslagerung ganzer Adressräume ! dem Prozess

fehlt auch das Betriebsmittel Arbeitsspeicher• Modellierung

! Zusätzliche Zustände " Bereit suspendiert: Der Prozess hat alle Betriebsmittel außer

CPU und Hauptspeicher " Blockiert suspendiert: Dem Prozess fehlt die CPU,

Hauptsspeicher und wartet auf das Ende mindestens einer blockierenden Operation

! Zusätzliche Übergänge" Swap-Out: der Prozess (blockiert, bereit) wird ausgelagert

bzw. Hauptspeicher wird erst gar nicht zugeteilt" Swap-In: Der Prozess wird aus dem sekundären Speicher in

den Hauptspeicher übertragen

O. Kao Betriebssysteme 2-16

Erweitertes Zustandsmodell (Grafische Darstellung)

Blockiert

Bereit Laufend

Beendet

Ready

Retire

Bloc

k

Assign

ResignAdd

Initiiert

BlockiertSuspendiert

Swap-inSwap-outBereit

Suspendiert

Swap-inSwap-out

Prozess Erzeugen

Prozess Umschalten

Prozess Beenden

2.3 Grundoperationen mit Prozessen

Prozesserzeugung unter UNIX: Systemaufruf istfork(), Kindprozess ruft execve() auf, um dasSpeicherabbild zu wechseln˜ unter Windows : Systemaufruf istCreateProcess()

Vaterprozess und Kindprozesse bilden unter UNIXeine Familie, d. h. Signale werden an alle Prozessein der Familie verteilt und jeder Prozess entscheidetuber Annahme und Verwertung

Prozessumschaltung: Sicherung des alten Kontex-tes, Aktualisierung des PCBs und Einordnung inWarteschlange, Laden des Kontextes des neuenProzesses, Aktualisierung des PCBs und der Spei-cherinformationen, Aktualisierung des Kontextesdurch Anpassung aller Verknupfungen

Umschalttechniken: direkter Sprung (Einprogram-mierung im Quellcode, z. B. bei Echtzeitsystemen),automatisches Umschalten

Leerlaufprozess zur einfachen behandlung des Falls,in dem alle Prozesse im ready-Zustand sind

O. Kao Betriebssysteme 2-29

Moduswechsel (Mode Switching)

• Die meisten Prozessoren unterscheiden aus Sicherheitsgründen zwischen ! Systemmodus (Kernmodus): Das BS besitzt die CPU und hat

uneingeschränkten Zugriff auf alle Ressourcen! Benutzermodus: Prozessor ist einer Anwendung zugeordnet,

kritische Zugriffe können gesteuert/gesperrt werden! Aktueller Modus wird im Programmstatuswort festgehalten

O. Kao Betriebssysteme 2-30

Moduswechsel (Mode Switching)

• Übergang Benutzermodus →Systemmodus z.B. durch Unterbrechung! Sicherung des Kontextes des

laufenden Prozesses, vor allem der Informationen, die durch eine Unterbrechungs-behandlung verändert werden können

! Sprung zum Anfang der Unterbrechungsbehandlungs-routine

! Änderung des Systemmodus

! Nach Behandlung der Unterbrechung wird unter Umständen wieder der alte Prozess ausgeführt (Bei Prozesswechsel kommt immer ein neuer Prozess zur Ausführung!)

2

Betriebssysteme, Prof. Dr. Odej Kao, Zusammenfassung von Florian SchoppmannDas Copyright fur die dieser Zusammenfassung zugrunde liegenden Vorlesungsunterlagen (Skripte, Folien, etc.) liegt beim Dozenten.Daruber hinaus bin ich, Florian Schoppmann, alleiniger Autor dieses Dokuments und der genannte Dozent ist in keiner Weise verantwortlich.Etwaige Inkorrektheiten sind mit sehr großer Wahrscheinlichkeit erst durch meine Zusammenfassung/Interpretation entstanden.

Systemmodus ↔ Benutzermodus, Speicherung imProgrammstatuswort

2.4 Thread-Modell

Thread: Keine vollstandige Prozesstabelle, selbervirtuelle und reale Adressraum wie der Prozess,entspricht einem separaten Kontrollfluss

Threadtabelle: enthalt: separaten Befehlszahler, ei-genen Code-und Datenteil, Register und Stapel(vollstandige Verknupfungsumgebung), Zustand

Ubersicht Prozessmodelle:

O. Kao Betriebssysteme 2-35

Single- vs. Multi-ThreadedProzessmodell

• Zur Prozessausführung benötigte Daten

Programm StatischeDaten

DynamischeDaten

Laufzeit-keller

Niedrige Adresse Hohe Adresse

Programm StatischeDaten

DynamischeDaten

Stapeln

Stapel1

Single Threaded

MultiThreaded

• Komponenten

Adress-raum

PCB

Stapel

Single Threaded

Adress-raum

PCB Stapel

Multi Threaded

Thread CB

Thread

Stapel

Thread CB

Thread

O. Kao Betriebssysteme 2-36

Realisierung von Multithreading

• Verarbeitung startet üblicherweise mit einem einzigen Thread! Thread_create(): dynamische Erzeugung weiterer Threads

" Funktionsparameter: auszuführende Prozedur und Startparameter" Rückgabewert: Threadidentifikator

! Thread_yield(): Freiwillige Abgabe der CPU

" Kein Uhr-Interrupt vorhanden ! Für die Aufteilung der Rechenzeit zwischen der Threads ist der Entwickler zuständig

! Synchronisationsaufrufe wie thread_wait() legen eine Ausführungs-reihenfolge fest

! Thread_exit() beendet einzelne Threads

• Wichtig! Threads operieren im selben Adressraum ! kein Schutz durch das BS! Konzepte wie fork() oder der Umgang mit gemeinsamen

Datenstrukturen können zu Problemen führen ! Sorgfältiges und durchdachtes Design notwendig

O. Kao Betriebssysteme 2-35

Single- vs. Multi-ThreadedProzessmodell

• Zur Prozessausführung benötigte Daten

Programm StatischeDaten

DynamischeDaten

Laufzeit-keller

Niedrige Adresse Hohe Adresse

Programm StatischeDaten

DynamischeDaten

Stapeln

Stapel1

Single Threaded

MultiThreaded

• Komponenten

Adress-raum

PCB

Stapel

Single Threaded

Adress-raum

PCB Stapel

Multi Threaded

Thread CB

Thread

Stapel

Thread CB

Thread

O. Kao Betriebssysteme 2-36

Realisierung von Multithreading

• Verarbeitung startet üblicherweise mit einem einzigen Thread! Thread_create(): dynamische Erzeugung weiterer Threads

" Funktionsparameter: auszuführende Prozedur und Startparameter" Rückgabewert: Threadidentifikator

! Thread_yield(): Freiwillige Abgabe der CPU

" Kein Uhr-Interrupt vorhanden ! Für die Aufteilung der Rechenzeit zwischen der Threads ist der Entwickler zuständig

! Synchronisationsaufrufe wie thread_wait() legen eine Ausführungs-reihenfolge fest

! Thread_exit() beendet einzelne Threads

• Wichtig! Threads operieren im selben Adressraum ! kein Schutz durch das BS! Konzepte wie fork() oder der Umgang mit gemeinsamen

Datenstrukturen können zu Problemen führen ! Sorgfältiges und durchdachtes Design notwendig

Vorteile durch Threads: Besseres Antwortverhalten(insb. bei GUIs), effiziente Betriebsmittelteilung,Thread- gunstiger als Prozesserzeugung, Paralle-litat

Kernel-Level-Threads ↔ User-Level-Threads

Umschaltung bei User-Level-Threads: ohne Pro-zesskontextwechsel, keine Leerung des Caches,effizient, eigenes Scheduling −→ Anpassbar anspezielle Scheduling-BedurfnisseBei Anforderung eines Betriebssmit-tels:

if Thread muss blockiert werden thenSpeicherung der Daten in der Threadtabelleif Anderer Thread ist ausfuhrbar then

Auswahl dieses Threadselse

Blockierender Systemaufrufend if

elseBM wird zur Verfugung gestellt

end if

Nachteile von User-level-Threads: Bei Seitenfehlerwird gesamter Prozess blockiert

Hybride Threadmodelle: UL-Threads benotigenmind. eines KL-Thread als Trager, Rechenzeit wirdeinzelnen Prozessen zugeordnetmany-to-one (nicht geeignet fur Parallelrechner),one-to-one (Aufwand bei Threaderzeugung), many-to-many (flexibel, Kompromiss)

2.5 Beispiel fur Threadbibliotheken:Pthreads

pthread create

pthread exit

pthread join

pthread cancel

pthread detach

pthread setcancel

pthread mutex init

pthread mutex lock

pthread mutex trylock

pthread mutex unlock

pthread mutex destroy

Beispiel fur Realisierung in Solaris:

O. Kao Betriebssysteme 2-51

Beispielprogramm#include <pthread.h>int sum; /* globale Variable für alle

Threads */void *runner(void *param);

/* Thread */main(int argc, char *argv[]) {

pthread_t handle;pthread_attr_t attr;pthread_attr_init(&attr);

/* Aktuelle Attribute */pthread_create(&handle, &attr,

runner, argv[1]); /* Erzeuge Thread */

pthread_join(&handle, NULL); /* Warte bis Thread fertig */

printf(“sum=%d\n“,sum); }

void *runner(void *param) {/* Der Thread bekommt die

Kontrolle in dieser Funktion */int upper=atoi(param);int i;sum = 0;if (upper>0) {for (i=1;i<=upper;i++);sum += i;

}pthread_exit(NULL); /* Threadbeendet sich und übergibt die Kontrolle an das Hauptprogramm */

O. Kao Betriebssysteme 2-52

Threadbibliothek in Solaris 2• Solaris 2 unterstützt KL- und UL-Threads, symmetrische

Multiprozessoren (SMP) und Echtzeitscheduling (Pthread API)• Erweiterung: Leichtgewichtsprozesse (LWP) als Zwischenstufe

zwischen UL- und KL-Threads! Zuordnung UL-Threads zum Pool von LWPs (many-to-many)! Jeder LWP ist einem KL-Thread zugeordnet (one-to-one)! Sind n UL-Threads einem LWP zugeordnet, dann sind n-1 inaktiv (blockiert,

wartend für LWP) und nur 1 UL-Thread aktuell rechnend (oder bereit)

2.6 Zuteilungsverfahren

Typen von Zuteilungsverfahren: Long-term, z. B.Start eines neuen Prozesses (wie viele Prozessesollen nebeneinander laufen?), Medium-term, z. B.Erstzuweisung von Hauptspeicher (welcher Prozesswird als nachstes ein-/ausgelagert?), Short-term,z. B. Zustandswechsel des Prozesses (Verwaltungvon Ereignissen wie Timer, Systemaufrufen)

Schlusselfaktoren fur Scheduling: Lange der CPU-Nutzung in einem Zyklus, VerwaltungsoverheadfurE/A z. B. bei Festplatten unabhangig von derGroße der gelesenen Daten, Schere zwischen Ge-schwindigkeiten von E/A-Geraten und Prozessor-geschwindigkeit engeht immer weiter auf (−→ Sche-duling von E/A-lastigen Prozessen entscheidend furdie Effizienz des Gesamtsystems)

Scheduling-Verfahren: FIFO, LCFS-PR, SJN,SRTN, PRIO-NP, Round-Robin (siehe KMS)

Multilevel-Feedback-Scheduling: dynamische An-passung der Zeitscheibenlange, Stufenweise Prio-ritatenreduktion fur lang laufende Prozesse

3

Betriebssysteme, Prof. Dr. Odej Kao, Zusammenfassung von Florian SchoppmannDas Copyright fur die dieser Zusammenfassung zugrunde liegenden Vorlesungsunterlagen (Skripte, Folien, etc.) liegt beim Dozenten.Daruber hinaus bin ich, Florian Schoppmann, alleiniger Autor dieses Dokuments und der genannte Dozent ist in keiner Weise verantwortlich.Etwaige Inkorrektheiten sind mit sehr großer Wahrscheinlichkeit erst durch meine Zusammenfassung/Interpretation entstanden.

O. Kao Betriebssysteme 2-59

Multilevel-Feedback-Scheduling

ZugangAbgangWarteschlange 1

Zeitscheibe 8 ms CPU

ZugangAbgangWarteschlange 2

Zeitscheibe 16 ms CPU

ZugangWarteschlange 3

Zeitscheibe 32 msAbgang

ZugangWarteschlange n

FCFS CPUAbgang

CPU

Hohe Priorität

Geringe Priorität

O. Kao Betriebssysteme 2-60

Schedulingbeispiel: Solaris 2• Vier Klassen für prioritätenbasierten Scheduling vorhanden

! Echtzeit, System, Zeitscheiben (Time Sharing) und Interaktiv! Jede Klasse kann über unterschiedliche Schedulingpolicies und Prioritäten

verfügen! Klasse Zeitscheiben wird nach Multilevel-Feedback verwaltet! Klasse Interaktiv benutzt die gleiche Policy wie Zeitscheiben, gewährt

aber Anwendungen mit GUI-Ausgabe höhere Prioritäten! Klasse System umfasst Prozesse, die in Kernmodus laufen, z.B. der

Scheduler und der Paging Daemon" Keine Zeitscheiben ! Prozesse laufen, bis sie blockieren, die CPU

freiwillig abgeben oder bis Prozesse höherer Priorität da sind" Prioritäten ändern sich nicht

! Echtzeitprozesse haben die höchste Priorität aller Klassen• Konvertierung der Klassenprioritäten in globale Prioritäten durch BS• Bei mehrerer Prozessen gleicher Priorität wird nach Round-Robin

vorgegangen

2.7 Prozesse und Scheduling in Linux

Grundprinzipien: Threads uber Biliotheken (ohneKernelunterstutzung), PCBs in doppelt verketteterListe + Hash-Liste von PID −→ PCB

Prozesszustande:TASK RUNNING, TASK INTERRUPTIBLE (durchusleep(), TASK UNINTERRUPTIBLE (durch E/A-Aufruf), TASK ZOMBIE (Prozess beendet, Vaterpro-zess muss Ergebnis noch abrufen), TASK STOPPED(Prozess wurde angehalten, z. B. durch kill-STOP PID)

Multilevel-Feedback-Scheduling: RR/FIFO furEchtzeitprozesse, auf PRIO-P Strategie basieren-des Verfahren fur ”normale“ Prozesse

2.8 Prozesse und Scheduling in Windows

Hierarchie: Jobs→ Processes→ Threads→ Fibers(kooperative ”lightweight“ Threads, deren Schedu-ling nicht vom Betriebssystem vorgenommen wird)

System-Prioritat fur Threads ergibt sichaus Win32-Prozessprioritat und Win32-Threadprioritat

Scheduling: Prioritatenliste mit 32 Prioritaten, RRfur jede PrioritatsstufeVerbesserungen: Prioritatserhohung nach Beendi-gung einer E/A-Operation, temporare Deaktivie-rung des Schedulings, wenn Systemthread in kriti-schem Bereich

3. Speicherverwaltung

3.1 Grundlegendes

Dynamische Speicherallokation, Zugriff auf einenfehlenden Inhalt lost Interrupt aus

3.2 Seitenersetzungsstrategien

Nachschubstrategien: Demand Paging, Pre-Paging

Verdrangungsstrategien (Replacement Policies):Probleme bei Realisierung durch aufwendige Ope-rationen

Working Set: Menge Wi(t, τ) von Seiten, auf dieein Prozess i in den letzten τ Einheiten ab demZeitpunkt t zugegriffen hat.

Realisierung: Jeder Eintrag in der Seitentabelleenthalt mind. Referenzbi, Modifikationsbit und un-gefahre Zeite des letzten Zugriffs

WSClock-Algorithmus: Modifikation des Clock-Algorithmus

3.3 Speicherverwaltung unter Linux

Virtuelle Speicherbereiche: Grafikspeicher oder(memory-mapped) Dateien werden in den Adress-raum eingeblendet

Gemeinsam genutzter Speicher mit copy-on-write

Speicherbereinigung: Aufruf von kswapd alle 1 soder bei Bedarf. Beachtung minimaler Verweildau-er im Speicher zur Vermeidung von Thrashing

3.4 Speicherverwaltung unter Windows

Arbeitet mit Working-Sets:

O. Kao Betriebssysteme 3-31

Physische Speicherverwaltung (Grafische Darstellung)

O. Kao Betriebssysteme 3-32

Physische Speicherverwaltung: Hintergrundprozesse

• Swapper-Thread läuft alle 4 Sekunden und sucht alle Prozesse, deren Threads für eine bestimmte Zeitspanne im Leerlauf waren! Prozess gefunden ! Auflösung des Stapels, Prozessseiten werden auf

Standby oder Modified List geschoben

• Mapped-Page-Writer/Modified-Page-Writer (Hintergrundthreads)! Periodische Prozesse, die nachsehen, ob genügend freie Seiten

vorhanden sind! Keine freie Seiten ! Seiten von der Spitze der Modified list holen,

zurück auf die Festplatte schreiben, verschieben in Standby list

• Lagert ein eine Seite aus ! Seite wird in Free list verschoben, es sei denn, diese wird mit anderen Prozessen geteilt

• Stapelwachstum ! eine Seite gefüllt mit Nullen zwingend notwendig (Sicherheitsgründe)

3.5 Leistungsaspekte des virtuellen Spei-chers

WSClock bietet den besten Kompromiss zwischeneffizienter Implementierung und guter Leistung

Modellierung des Seitentausches (3-34): Was solldas denn?

4

Betriebssysteme, Prof. Dr. Odej Kao, Zusammenfassung von Florian SchoppmannDas Copyright fur die dieser Zusammenfassung zugrunde liegenden Vorlesungsunterlagen (Skripte, Folien, etc.) liegt beim Dozenten.Daruber hinaus bin ich, Florian Schoppmann, alleiniger Autor dieses Dokuments und der genannte Dozent ist in keiner Weise verantwortlich.Etwaige Inkorrektheiten sind mit sehr großer Wahrscheinlichkeit erst durch meine Zusammenfassung/Interpretation entstanden.

Thrashing: Uberlastphanomen, ahnlich Stau imStraßenverkehr. Der Koordinationsaufwand wachstuberproportional an.Zur Verhinderung des Thrashing muss der Multi-programminggrad nmax begrenzt werden:indirekte Strategie Fur jeden Prozess wird indivi-

duell eine sinnvolle Kachelanzahl festgestelt,und der Multiprogramminggrad begrenzt

direkte Strategie Anhand von Messungen der glo-balen Seitentauschaktivitat wird ein optima-ler Wert fur nmax berechnet, bspw. max.Prozessanzahl so bestimmen, dass die durch-schnittliche Zeit zwischen Seitenfehlern nichtgroßer ist als die Seitentransferzeit

Paging Deamon: Technik zur Sicherung eines aus-reichenden Vorrats an freien Kacheln fur schnelleReaktion auf weitere Speicheranforderungen

4. Ein- und Ausgabe

4.1 Klassifikation und Grundaufgaben

Klassifikation:Zeichenorientierte Gerate: Nicht adressierbar, kei-

ne Suchoperation. Beispiele: Tastur, Maus,Netzwerkkarten

Blockorientierte Gerate: Ein Block kann un-abhangig von anderen Blocken gelesen odergeschrieben werden. Beispiele: Festplatten,CD-ROMs, . . .

Abstrakte Gerate zur Reprasentation in der Sys-temsoftware: Device Control Block, Mindestmengevon Funktionen (open/close, read/write), Gerate-treiberGrundaufgaben: Steuern des Gerates (z. B.Lesekopf positionieren), Datentransport vonCPU/Speicher zum Gerat und umgekehrtTransportauftrag: Positionierung der zu ubert-ragenden Daten, Spezifikation der Parameter(Richtung, Lange der Daten), Ruckmeldung:Status-/Fehlersignale

4.2 Schlusselkonzepte von E/A-Software

Anforderungen: Gerateunabhangigkeit, Ein-heitliches Benennungsschema, Fehlerbehandlungmoglichst nah an der Hardware (z. B. automatischeFehlerkorrektur bei CD-ROMs)

Konzepte: Syncrhone ↔ asynchrone Ubertragun-gen, Pufferung, gemeinsame/exklusive Nutzung

Schichtenaufbau: Hardware → Unterbrechungs-behandlung → Geratetreiber: Direkte Ansteue-rung der spezifischen Gerate→ GerateunabhangigeE/A-Systemsoftware → E/A-Software in Anwen-dungen: Systemaufrufe fur die E/A

Unterbrechungsbehandlung:1. Sicherung aller Register

2. Erzeugen des Kontextes fur die Unterbre-chungsroutine

3. Initialisierung von MMU, TLB, Speichertabel-len, . . . und Anlegen neuer Speicherbereiche

4. Interruptcontroller informieren und Behand-lung weiterer Unterbrechungen veranlassen

5. Kopieren der gesicherten Register in die Pro-zesstabelle

6. Aufruf der Unterbrechungsroutine (Informa-tionen aus den E/A-Geraten auslesen und not-wendige Operationen durchfuhren)

7. Auswahl des nachsten auszufuhrenden Prozes-ses

8. Initialisierung/Wiederherstellung des Kontex-tes, Laden der Prozessregister

9. Verarbeitung mit neuem Prozess fortsetzen

4.3 Geratetreiber

Treiber als Betriebssystem-Bestandteil/Modul ↔Benutzerprozess (Gerateserver)

Code ist reentrant, wenn er von mehreren Program-men gleichzeitig verwendet werden kann

4.4 Gerateunabhangige E/A-Software

Pufferung: Keine Pufferung, Pufferung im Benut-zerraum (Nachteil: Sperrung gegen Auslagerungnotig), Pufferung im Kernraum (Nachteil: Siche-rung gegen Uberlauf notig, Benachrichtigung anBenutzerprozess), Wechselpuffer

Prozesskoordination (z. B. fur CD-Brenner)

Spooling: Simultaneous Peripheral Operations On-line

5

Betriebssysteme, Prof. Dr. Odej Kao, Zusammenfassung von Florian SchoppmannDas Copyright fur die dieser Zusammenfassung zugrunde liegenden Vorlesungsunterlagen (Skripte, Folien, etc.) liegt beim Dozenten.Daruber hinaus bin ich, Florian Schoppmann, alleiniger Autor dieses Dokuments und der genannte Dozent ist in keiner Weise verantwortlich.Etwaige Inkorrektheiten sind mit sehr großer Wahrscheinlichkeit erst durch meine Zusammenfassung/Interpretation entstanden.

4.5 Beispiel fur blockorientierteGerate:Festplatten

Bedienzeit als Summe von: Armpositionierzeit,Latenzzeit (Drehwartezeit), Schreib/Lesezeit(Tatsachliche Ausfuhrungszeit), Transferzeit

Low-Level- (Anlegen von Spuren, Sektoren undLucken) ↔ High-Level-Formatierung (Anlegen ei-nes leeren Dateisystems fur jede Partition)

RAIDs: (Redundant Array of Inexepensi-ve/Independent Disks) Level:

0. Virtuelle Festplatte wird in Strips unterteilt,Parallelitat beim Lesen/Schreiben eines sichuber mehrere Strips erstreckenden Blocks, kei-ne Redundanz

1. Alle Platten doppelt vorhanden2. Aufteilung von Wortern oder Bytes3. Wie Level 2, jedoch Speicherung der Parity-

Daten auf einer Platte4. Wie Level 2 und 3, jedoch mit (großeren)

Strips, Parity-Platte als Flaschenhals beimSchreiben

5. Ahnlich Level 4, bei Verteilung der Parity-Strips uber alle Platten zur Eliminierung desFalschenhals

4.6 Strategien fur Plattentreiber

Random Abarbeitung in zufalliger ReihenfolgeFIFS First Come First ServePrioritaten Abarbeitung gemaß PrioritatenSSTF Shortest Seek Time First (Armpositionsie-

rungszeit), Minimierung der Anzahl der Arm-bewegungen, Bei stark belasteten Platten ten-diert der Arm zu den mittleren Sektoren

SCAN Fahrstuhlstratgie, Lokalitat von Anfragennicht ausreichend berucksichtigt

SCAN-C Zyklische SCAN-Strategie, da nach je-dem Durchlauf Rucksprung auf Zylinder 0

4.7 Effizienzbetrachtungen

FCFS: Im Mittel Uberfahren von 13 der Spuren

SCAN, SCAN-C, SSTF: Vorteile in Hochlastsitua-tionen, im Grenzfall Sprung um nur eine SpurSCAN und SSTF benachteiligen die RandspurenSSTF: im Mittel die beste Leistung, Verhungernvon Auftragen moglich

Vorgehensweise Treiber blockieren nach Auftrag /Deblockieren nach Unterbrechung ”Fertig“ fuhrt zulangen Zeiten zwischen zwei Auftragen (Totzeit)

Totzeitreduzierung (Latency Hiding): Uberlappungder Aktivitaten ”Durchfuhrung des aktuellen Auf-trags“ und ”Vorbereitung des nachsten Auftrags“Wie genau soll das funktionieren?

Plattencache: unabhangig vom Betriebssystem-Cache

5. Dateisysteme

5.1 Organisation von Dateisystemen undDateiattribute

Eigenschaften per Definition: Persistente Speiche-rung großer Informationsmengen. Abstraktion derDetails fur die Datenablage, Gleichzeitiger Zugriffauf die Daten durch mehrere Prozesse moglich,Schutzmechanismus fur den Datenzugriff

Typische Strukturierung von Dateien: Folge vonBytes (Interpretation beim Einlesen durch Anwen-dung), Folge von Datensatzen, Hierarchisch

5.2 Zugriffsarten

Sequentiell, wahlfrei (random access), Index-basiert

Indexstrukturen: B-Baume, Index-Sequential Ac-cess Method, invertierte Liste

5.3 Grundlegende Operationen fur Datei-und Verzeichnisverwaltung

selbsterklarend

5.4 Layout eines Dateisystems

Sektor 0 einer Festplatte: Master Boot Record zurLokalisierung der Partitionstabelle und/oder akti-ven Partition

Zwei-Phasen-Realisierung: 1. Abbildung Dateien→nummerierte Blocke fester Lange 2. Abbildung Da-tenblocke → Geometrie des Speichermediums

5.5 Zuordnung Dateien → Datenblocke

Einfachste Moglichkeit: Zusammenhangende Ab-bildung. Jedoch mit Nachteil: Fragmentierung

6

Betriebssysteme, Prof. Dr. Odej Kao, Zusammenfassung von Florian SchoppmannDas Copyright fur die dieser Zusammenfassung zugrunde liegenden Vorlesungsunterlagen (Skripte, Folien, etc.) liegt beim Dozenten.Daruber hinaus bin ich, Florian Schoppmann, alleiniger Autor dieses Dokuments und der genannte Dozent ist in keiner Weise verantwortlich.Etwaige Inkorrektheiten sind mit sehr großer Wahrscheinlichkeit erst durch meine Zusammenfassung/Interpretation entstanden.

Belegung durch verkettete Listen:interne Verkettung Jeder Block enthalt Zeiger auf

nachsten Block. Nachteil: Nur sequentiellerZugriff moglich, wenig robust: Ein Dateiver-lust bei Zerstorung nur eines Blockes

externe Verkettung Externe Allokationstabelle(File Allocation Table, FAT)

Indexblocke Jeder Datei wird ein Indexblock zuge-ordnet, fur große Dateien mehrstufige Index-blocke. Vorteile: Tabelle zur Speicherung derverketteten Liste aller Dateiblocke wachst li-near mit Festplattengroße, Arbeitsspeicherbe-darf beim Zugriff ist ausschließlich proportio-nal zur maximalen Anzahl gleichzeitig geoffne-ter Dateien

Optimierungen: Trennung des Dateinamens (vonvariabler Lange) von den ubrigen Datei-/I-Node-Attributen

5.6 Verwaltung des Plattenspeichers

Verwaltung freier Blocke: Verkettete Listen (sinn-voll: Nutzung der freien Blocke zur Speicherung)↔Bitmaps

5.7 Leistungsaspekte: Caching, Backup,Konsistenz, . . .

Caches: Write Through, Careful write: Schrei-ben nach einer vorgegebenen Maximalverzogerung,Lazy write: Alles wir vorerst im Cache behaltenOptimierungen: Vorauslesen von Blocken, virtuelleFestplatten (RAM-Disks), Optimierung der Block-anordnungKonsistenzuberprufung: Abgleich freier Blocke vs.belegter Blocke, Block in Freiliste vermisst/doppeltvorhanden, kritisch: Block kommt in mehreren Da-teien vor

5.8 Log-basierte Dateisysteme

Motivation: CPU-Geschwindigkeit wachst schnellerals Festplattenzugriffszeiten. Caches werden wich-tiger und damit die Behandlung von Konsistenz-problemenOptimierung: Schreiben eines temporaren Logs, dasspater erst aufgeraumt wird, d. h. die tatsachlichenAnderungen an Dateien vorgenommen werden

5.9 NTFS Dateisystem

Grundeigenschaften: Clustergroße unabhangig vonDatentragergroße, Alle Daten (auch Meta-Daten)als Dateien, Verschlusselung, Komprimierung,mehrere Datenstrome

6. Sicherheit

6.1 Grundlagen der Sicherheit

Sicherheitsanforderungen: Datenvertraulichkeit, --integritat, Systemverfugbarkeit, Datenschutz

Verwendung von Kryptografie: Symmetrische ↔Asymmetrische Verschlusselung, Digitale Signatu-ren, Hashing mit Einwegfunktionen

6.2 Benutzer-Authentifizierung

Authentifizierung durch: ”Geheimnis“ des Benut-zers, z. B. Passwort, biometrische Daten, Zusatz-liche Hardware (z. B. Chipkarten, herklommlicherSchlussel)

Passwortsicherheit in UNIX: Passwortdatei mit jeeiner Zeile mit Attributen und verschlusseltemPasswort je Benutzer. Aktuelle Version: Separa-te Speicherung der verschluselten Passworter inShadow-Datei

Verbesserung der Passwortsicherheit: Verzoge-rungsstrategien, Verwendung schwer zu ermit-telnder Passworter, Einmal-Passworter, Challenge-Response-Verfahren (Erweiterung davon: Smart-Cards mit kleiner CPU)

6.3 Angriffe von innerhalb des Systems

Login-Spoofing: Programm bildet Passwort-Eingabebilschirm exakt nach. Abhilfe: Bspw.Tastenkomnination, die nicht vom Benutzerpro-gramm abgefangen werden kann

Buffer-Overflow: Uberschreibung der Rucksprungs-adresse durch uberlange Eingaben

7

Betriebssysteme, Prof. Dr. Odej Kao, Zusammenfassung von Florian SchoppmannDas Copyright fur die dieser Zusammenfassung zugrunde liegenden Vorlesungsunterlagen (Skripte, Folien, etc.) liegt beim Dozenten.Daruber hinaus bin ich, Florian Schoppmann, alleiniger Autor dieses Dokuments und der genannte Dozent ist in keiner Weise verantwortlich.Etwaige Inkorrektheiten sind mit sehr großer Wahrscheinlichkeit erst durch meine Zusammenfassung/Interpretation entstanden.

O. Kao Betriebssysteme 6-15

Logische Bomben und versteckte Hintertüren

• Logische Bomben = vom Programmierer beim Erstellen des Programms eingebrachter Code, der Schaden einrichten kann! Oft zur Erpressung des Arbeitsgebers eingesetzt

" Solange das Passwort des Entwicklers täglich kommt oder sein Name auf der Gehaltsliste steht, passiert nichts

" Bei Entlassung: Code wird aktiviert und richtet Schaden an

• Versteckte Hintertüren! Veränderung der Einloggprozedur, so dass mit einem bestimmten

Loginname das Einloggen jederzeit und auf allen von diesem Hersteller ausgelieferten Systemen möglich ist ! Hintertür umgeht den gesamten Authentifizierungsprozess

• Vermeidung von logischen Bomben/versteckten Hintertüren durch Einführung eines konsequenten, ausgiebigen Code Reviews möglich! Entwickler erklärt den Code Zeile für Zeile den restlichen Teammitgliedern! Ein oder mehrere Entwickler überprüfen den Code der anderen

Teammitglieder ! siehe Software Engineering

Nicht Klausurrelevant

O. Kao Betriebssysteme 6-16

Pufferüberläufe (Buffer Overflows)

• Ziel: Überschreibung und somit Umlenkung der Rücksprungadresse auf ein eingeschleustes Programm! Bei Funktionsaufrufen wird die Rücksprungadresse und zu übergebende

Parameter auf den Stapel gelegt! Für bestimmte Parameter – z.B. einen Dateinamen – wird Speicherplatz

gemäß der Definition des Strings reserviert! Wird diese Grenze durch einen extralangen Namen überschritten, so wird

die Rücksprungadresse überschrieben und somit abgeändert" Sprung in fremden/gesperrten Adressraum ! Absturz" Pufferinhalt = Programm, das ausgeführt wird ! Großer Schaden

6.4 Angriffe von außerhalb des Systems

nicht klausurrelevant

6.5 Schutzmechanismen

Domane: Menge von Paaren (Objekt, Rechte), je-des Paar spezifiziert ein eindeutig identifiziertesObjekt (HW, Prozesse, Dateien, Semaphore, . . . )und die darauf ausfuhrbaren OperationenEin Prozess lauft zu jedem Zeitpunkt in einer ein-zigen SchutzdomaneDomanenkonzept bei UNIX: Festlegung durchBenutzer-ID und Gruppen-IDKlassische Realisierung des Domanenkonzeptsdurch Speicherung in Matrix:

O. Kao Betriebssysteme 6-21

6.5 Schutzmechanismen• Einführung des Domänenkonzepts (domain)

! Domäne = Menge von Paaren (Objekt, Rechte)! Jedes Paar spezifiziert ein eindeutig identifiziertes Objekt (HW, Prozesse,

Dateien, Semaphore, …) und die darauf ausführbaren Operationen! Recht = Erlaubnis zur Ausführung einer Operation! Domäne kann einem Benutzer entsprechen, aber auch allgemeiner Natur

sein! Ein Prozess läuft zu jedem Zeitpunkt in einer einzigen Schutzdomäne! Domänenwechsel ist möglich, die dazugehörigen Regel sind hochgradig

vom aktuellen System abhängig

• Domänenkonzept bei UNIX! Domäne eines Prozesses wird durch BenutzerID (UID) und GruppenID

(GID) festgelegt ! für jede Kombination (UID, GID) lässt sich eine Liste mit allen benutzbaren Objekten (HW, SW, …) erstellen

! Prozessaufteilung in Benutzer- und Kernteil, die in unterschiedlichen Domänen laufen ! Systemaufruf verursacht einen Domänenwechsel

O. Kao Betriebssysteme 6-22

Realisierung des Domänenkonzepts

• Konzeptionell: Modellierung der Übersicht über Domänen und zulässige Operationen für verschiedene Ressourcen durch eine Matrix! Ein Objekt pro Spalte, eine Domäne pro Zeile! Zellen enthalten – falls vorhanden – die zulässigen Operationen! Domänen sind selbst Objekte ! Modellierung des Übergangs von einer

Domäne in eine andere Domäne• Matrixdarstellung ineffizient, da zu viele leere Felder vorhanden !

Speicherung nur der Spalten (ACL) oder der Zeilen (Capabilities)

Domain

Effizientere Speicherung, da in Matrix zu viele leereFelder vorhanden: Nur die Spalten (Access ControlLists – ACLs) oder der Zeilen (Capabilities)Capabilities: (C-Listen)

6.6 Firewalls

bekannt

8