BS Zusammenfassung PDF

OS – ÜBERBLICK Entstehung moderner BS Serial Processing (1950) Kein BS, direkte Programmierung der HW Problem: Fehleranfälligkeit, Lösung: Unterprogrammbibliotheken für I/O Problem: Setup benötigt viel Zeit, Lösung 1: Spezialist, Lösung 2: Monitor Monitor (1960) Job-Ausf...

OS – ÜBERBLICK Entstehung moderner BS Serial Processing (1950) Kein BS, direkte Programmierung der HW Problem: Fehleranfälligkeit, Lösung: Unterprogrammbibliotheken für I/O Problem: Setup benötigt viel Zeit, Lösung 1: Spezialist, Lösung 2: Monitor Monitor (1960) Job-Ausführung mit Monitor Aufbau Monitor Speicherschutz Timer Privilegierte Instruktionen Interrupts Problem: entweder CPU od I/O aktiv, Rest der Maschine untätig Lösung: Parallele CPU und I/O → Pufferung und I/O Interrupts Multiprogramming Problem: Kaum ein Programm nützt CPU und periphäre Hardware gleich aus o CPU-intensive Programme (CPU bound) o I/O-intensive Programme (I/O bound) Lösung: Multiprogramming bzw Multitasking 1 / 59 Multiprogrammed Batch Systems “Parallele” Ausführung von Programmen macht neue Mechanismen notwendig zB o Speicherverwaltung o Scheduling (Verwaltung von CPU und Ressourcen) Time-Sharing Systems Problem: Mehrere Benutzer teilen einen Computer; Warten auf Fertigstellung von Jobs Lösung: Preemptive Scheduling, Prioritäten Problem: Daten und Programme sollen für Benutzer leicht verfügbar sein Lösung: Filesystem am Rechner Benutzer-Computerinterface BS als Dienstleister o Programmausführung, Programmerstellung o I/O, Filezugriff, Netzwerkkommunikation o Zugangskontrolle, Fehlererkennung und -behandlung, Logging BS als Ressourcenmanager o Keine externe Kontrollinstanz o Verwendet selbst Ressourcen, gibt Ressourcen vorübergehend ab o Hebt sich durch Funktionalität von anderen Programmen ab „Abstraktion“ o „ungestörte“ Programmabarbeitung ▪ Prozess o „unendlich“ großer Speicher, Files ▪ Speicherverwaltung o „private“ Maschine ▪ Zugriffsschutz, Datensicherheit 2 / 59 PROZESSE UND THREADS Begriffe und Konzepte Ziel: „Gleichzeitiges“, kontrolliertes Ausführen von Programmen auf einem Rechner Prozess „Animated Spirit of a program” Ausführbares Programm + zugehörige Daten (Variable, Stack, Puffer, etc) Kontext o Akt. Zustand des Prozesses (PC, Register, etc) o Daten zur Prozessverwaltung (Wartebedingung, Priorität, etc) Trace Charakterisiert das Verhalten eines Prozesses Sequenz von Instruktionen, die für einen Prozess ausgeführt werden Prozesse im BS Überlappung von Traces verschiedener Prozesse charakterisieren das Prozessorverhalten Trace Bsp Prozesszustände Einfachstes Prozessmodell 3 / 59 BS und Prozesse BS kontrolliert Ausführung der Prozesse (Ausführungsmuster, Ressourcenzuteilung) Repräsentation von Prozessen muss Aufgaben des BS unterstützen o Zustand des Prozesses, vom Prozess belegter Speicherbereich o Verwaltung von Prozessen in Datenstrukturen (Queues) entsprechend ihren Zuständen Erzeugung von Prozessen BS baut Datenstruktur auf und allokiert notwendigen Speicher Wann wird Prozess erzeugt? o Login eines interaktiven Benutzers o BS: Ausführung eines Services o Erzeugung durch einen Benutzerprozess (Process Spawning: Parent bzw Child) o Absetzen eines neuen Jobs Beendigung von Prozessen Prozess zeigt Beendigung an Logout durch Benutzer Service Request an BS Auftreten eines Fehlers bei der Abarbeitung eines Prozesses Halt-Instruktion eines Jobs 5 Zustands-Prozessmodell Running: Prozess ist im Besitz der CPU und wird ausgeführt Ready: Prozess ist bereit zur Ausführung (wartet nur auf Zuteilung der CPU) Blocked / Waiting: Prozess wartet auf ein Ereignis (zB I/O), ist nicht laufbereit Entry: o BS hat Prozess kreiert ▪ Prozessnummer (process identifier) ▪ Tabellen und Tabelleneinträge zur Prozessverwaltung o Prozess ist jedoch noch nicht bereit zur Ausführung ▪ Vermeidung der Ressourcenüberlastung durch Zulassung zu vieler Prozesse Exit: o Zustand wird durch Terminierung erreicht o Prozess wird nicht mehr weiter ausgeführt o Prozessinformationen (Tabellen) werden von Hilfsprogrammen verwendet o Die Prozessinformation, -tabellen werden gelöscht, wenn nicht mehr benötigt 4 / 59 Queing Modell Process Switch Umschalten des aktiven Prozesses Wen das BS im Besitz der CPU ist: o Supervisor Call ▪ Explizierter Aufruf durch das Programm (I/O, …) o Trap ▪ Bedingt durch aktuelle Instruktion (zB Auftreten eines Fehlers) o Interrupt ▪ Ursache lieget außerhalb des Prozesses, Kontrolle geht an Interrupt Handler und BS Prozessmodell mit Swapping Swapping Zuviele Prozesse im Hauptspeicher führen zu einer Verschlechterung der Performance Abhilfe: Swapping = Auslagern von Prozessen auf Sekundärspeicher Zur Realisierung im BS: zwei neue Prozesszustände und Queues Prozesszustände mit Swapping Ursachen für Suspend: Swapping, BS lagert Hintergrundprozess, Utility, oder problembehafteten Prozess aus Interaktiver Request (zB für Debugging) Timing: periodischer Prozess kann zwischen Aktivierungen ausgelagert werden Parent Request: Untersuchung, Modifikation, Koordination von Kinderprozessen 5 / 59 Kontrollstrukturen des BS für Prozessverwaltung BS verwaltet folgende Tabellen für Prozesse und Ressourcen: Memory Tables I/O Tables (für Geräte und Kanäle) File Tables Process Tables Process Image User Program User Data o Modifizierbarer Bereich des User Space (Daten, User Stack, modifizierbare Programme) System Stack o Parameter und Calling Addresses von System Calls Process Control Block (Execution Context) o Process identification, processor state information, process control information Process Image befindet sich im Virtual Memory (muss nicht zusammenhängend sein) Primary Process Table enthält Verweis auf Process Image BS benötigt Teile des Images zur Prozessverwaltung im Hauptspeicher Process Control Block PCB: Process Identification Eindeutige Prozessnummer (Process identifier) = Index in der Primary Process Table Benutzererkennung o Benutzer, dem der Prozess gehört Nummer des Prozesses, der den Prozess generiert hat (Parent Process Identifier) PCB: Processor State Information Registerinhalte Aufbau eines Process Image Kontroll- und Statusregister o Befehlsregister o Program Status Word (PSW) → Kontroll-, Modusinformation, Status-Bit Stack Pointers PCB: Process Control Information Scheduling und Zustandsinformation o Zustand, in dem sich der Prozess befindet; Ereignis, auf das der Prozess wartet o Priorität und Schedulinginformation Querverweise auf andere Prozesse o Realisierung von Prozess-Queues o Verweis auf Parent, Child, … Interprozesskommunikation (IPC) o Flags, Signale, Verweise auf Nachrichten Privileges Memory Management o Verweise auf Segment- oder Seitentabellen 6 / 59  Ressourcen o Verwendete: geöffnete Files, I/O Devices o Bisher konsumierte: CPU Zeit, I/O, etc Prozesslisten Execution Modes Um Datenstrukturen (zB PCB) des BS zu schützen, gibt es min zwei Execution Modes o Privileged Mode (= system mode, kernel mode, supervisor mode, control mode) ▪ Für Zugriff auf Kontrollregister, MM, I/O-Primitive o User Mode Mode Switch in BS-Routine Execution Modes werden durch Mode-Bits der CPU unterstützt Mode Switch vs Process Switch Mode Switch ist Basis für Process Switch Nicht jeder Mode Switch bewirkt Process Switch Example: Interrupt Handling 1. PC → stack, …; load PC from interrupt vector [HW] 2. Save registers, setup new stack [assembly code] 3. Interrupt service, e.g., read/buffer inputs [C code] 4. Scheduler decides on next process [C code] 5. Return to assembly code [C code] 6. Setup for process continuation [assembly code] 7 / 59 Prozesse – BS-Implementierungen Verschiedene Möglichkeiten, ein BS zu implementieren o Strikte Trennung von Kernel und Prozessen o BS exekutiert innerhalb von Benutzerprozessen o Prozessbasiertes BS Nonprocess Kernel Prozessbegriff nur für Benutzerprograme Verlassen des Prozesskontext bei BS-Aktivität BS arbeitet von Prozessen getrennt im Privileged Mode (eigener Speicherbereich, eigener Stack für BS) BS in User-Prozessen BS ist eine Sammlung von Routinen, die vom Benutzerprogramm aufgerufen werden Fast alle BS-Routinen laufen im Prozesskontext Verlassen des Prozesskontexts nur bei Process Switch BS Code und Daten werden im Shared Address Space abgelegt Getrennter Kernel Stack für Kernel Mode Im Prozess laufen sowohl User-Programm als auch BS-Routinen → Programm vs Prozess Prozessbasiertes BS BS ist eine Sammlung von Systemprozessen Nur Basisservices sind nicht als Prozesse realisiert (Process Switching, einfaches Memory Management, IPC, Interrupts und I/O) Kernelarchitekturen Monolithic Operating System o Betriebssystem = Menge von Prozeduren o Jede Prozedur kann jede andere Prozedur aufrufen Layered Operating System o Hierarchische Organisation der BS-Funktionen 8 / 59  o Interaktionen zwischen benachbarten Schichten o Mehrheit der Schichten exekutieren im Kernel Mode Modular Operating System o Hardware Abstraction Layer o Module realisieren verschiedene OS-Funktionalitäten Microkernelarchitektur Basisservices im Kernel Nicht zentrale BS Services als Server Prozesse Nachrichtenkommunikation zwischen BS/Prozessen Microkernel Services o Process Switching, Basic Memory Management o Interrupts und Hardware Access (I/O), Nachrichtenaustausch und -kontrolle Eingenschaften o Einheitliches Interface, Flexibilität und Erweiterbarkeit o Portabilität, Unterstützung von Verteilung o Kernelgröße: 300KB, 140 Sys. Calls (1st gen) bzw 12KB, 7 Sys. Calls (4th gen) Zusammenfassung Prozess Prozess ist zentrales Konzept in BS BS kreiert, verwaltet und beendet Prozesse Prozess durchläuft verschiedene Zustände (Ready, Running, Blocked, Supended, …) Datenstrukturen zur Prozessverwaltung o Prozesstabelle o Process Image: belegter Adressbereich, PCB: ID, Zustand, Steuerinfo; Ressourcen, Priorität, etc Mode Switch zwischen User/Kernel Mode o Interrupt, Trap oder Supervisor Call o Execution Mode vs Prozess/BS Kontext o Unterschiedliche Ansätze der Implementierung von BS und Prozessen ▪ Strikte Trennung BS-Prozesse ▪ BS-Funktionen in User-Prozessen abgearbeitet ▪ Server-Prozesse zur Ausführung von BS-Funktionen Threads Grundlegendes Bisher betrachtete Prozesse bilden Einheit für 1. Ressourcenverwaltung 2. Dispatching (kurzfristiges Scheduling) Entkoppelung von (1) und (2) 9 / 59  o Process (Task): Einheit der Ressourcenverwaltung o Thread (Lightweight Process): Einheit für das Dispatching Multithreading: n > 1 Threads pro Prozess Process o Virtueller Adressraum mit Process Image o Speicherschutz, Files, I/O Ressourcen Thread o Ausführungszustand (Running, Ready, …) o Kontext (wenn nicht gerade laufend) o Stack o Thread-lokale statische und lokale Variablen o Zugriff auf Prozessspeicher und Ressourcen Process Models Singlethreaded Process Model Multithreaded Process Model Thread vs Process Thread-Erzeugung benötigt weniger Zeit Umschaltung zwischen Threads geht schneller als Process Switch Terminierung eines Threads benötigt weniger Zeit als Prozessterminierung Kommunikation zwischen Threads eines Prozesses ohne Einschaltung des Kernels o Aber: Synchronisation notwendig! Einsatzbereiche Threads Applikationen, die zusammengehörige Menge von Abarbeitungseinheiten bilden Bsp: File Server in LAN o Meherer Requests in kurzer Folge, ein Thread für jeden Request Bsp: Spreadsheet-Programm o Ein Thread zeigt Menüs and und liest Input, ein Thread führt Berechnungen und Updates aus 10 / 59 Thread-Zustände Wichtige Zustände: Running, Ready, Blocked Zustand Suspend existiert nicht für einzelne Threads – alle Threads eines Prozesses haben Zugriff auf denselben Adressraum Bei der Terminierung eines Prozesses terminieren alle zugehörigen Threads User-Level Threads (ULT) Threads sind für Kernel unsichtbar Thread Management mittels Thread Library Thread Switching im User Mode (→ kein Mode Switch nötig) Applikationsspezifisches Scheduling Threads Library o Enthält code für ▪ Erzeugung und Terminierung von Threads ▪ Daten-, Nachrichtenaustausch zwischen Threads ▪ Thread Scheduling User-Level Threads ▪ Sichern und Herstellen von Thread Kontexten o Blockierender System Call blockiert alle ULTs eines Prozesses o Keine Verteilung auf mehrere Prozesse Kernel-Level Threads (KLT) Thread Management durch Kernel Kernel Thread API, keine Library Thread Switching durch Kernel Scheduling auf Thread-Basis Thread-weises Blocking Kernel-Routinen multi-threaded Gleichzeitiges Schedulen mehrerer Threads eines Prozesses (bei mehreren Prozessen) Thread Switching innerhalb eines Prozesses über den Kernel benötigt 2 Mode Switches → Verlangsamung ggü ULTs zB kombinierter (hybrider) ULT/KLT Ansatz Kernel-Level Threads Zusammenfassung Threads Thread: Einheit für Dispatching Mehrere Threads pro Prozess möglich Schnelleres Erzeugen und Umschalten als bei Prozessen Verschiedene Implementierungen o user-level vs kernel-level 11 / 59 MUTEX – SYNCHRONISATION Grundlegendes Gemeinsame Ressourcen BS und Prozesse, parallel laufende Prozesse o verwenden dieselben Daten bzw Ressourcen (Puffer, ShM, Files, Geräte) o tauschen Daten aus und/oder interagieren wir brauchen: o disziplinierten Zugriff auf gemeinsame Daten / Ressourcen o geordnete Abarbeitung verteilter Aktionsfolgen sonst Fehlverhalten: o Inkonsistente Daten o Indeterministisches Verhalten (Ereignisfolge, Werte) Race Condition Ergebnis einer Operation hängt ab von o Zeitlichen Verhalten, oder o Der Reihenfolge von Operationen oder Ereignissen außerhalb der Kontrolle eines Prozesses Fehler: ein oder mehrere der möglichen Ergebnisse sind falsch bzw führen zu falschem Verhalten Programmierung von Mutual Exclusion und Bedingungssynchronisation Interaktion von Prozessen Wettstreit um Ressourcen (Comptetition) Wechselseitiger Ausschluss (Mutual Exclusion) o Verhindern des „gleichzeitigen“ Ressourcenzugriffs o Ununterbrechbarkeit einer Aktionsfolge (Atomizität) o Ziel: Konsistenthalten der Daten Bedingungssynchronisation (Condition Synchronisation) o Erreichen einer definierten Abfolge von Operationen o Ziel: Vermeidung von Race Conditions (Abhängigkeit von Ergebnissen von relativem Prozessfortschritt) MutEx und CondSync sind orthogonale Konzepte Mögliche Wechselwirkungen zwischen Prozessen: MutEx CondSync Ziel - - unabhängige Aktionen - + vorgegebene Abfolge + - Konsistenz + + Konsistenz und Abfolge BS-Kontrollaufgaben MutEx – Datenkonsistenz Regelung der Abfolge der Ressourcenvergabe Verhinderung von Deadlock Bsp P1 besitzt R1 und braucht R2, P2 besitzt R2 und braucht R1 Verhinderung von Starvation Bsp P1 und P2 laufen abwechselnd auf CPU, P3 bekommt die CPU nicht 12 / 59 Kritischer Abschnitt (k.A.) Definition k.A. Ein Prozess befindet sich im kritischen Abschnitt (k.A.), wenn er auf gemeinsame Daten bzw Ressourcen zugreift Wechselseitiger Ausschluss (mut ex): zu jedem Zeitpunkt darf sich höchsten ein Prozess in seinem kritischen Abschnitt befinden Eintritt in k.A. muss geregelt sein Prozessstruktur für k.A. Kein Prozess darf in seinem kritischen Abschnitt eintreten, wenn sich bereits ein Prozess in seinem k.A. befindet Prozessstruktur Anforderungen für k.A. Lösung Mutual Exclusion Progress o Wenn sich kein Prozess im k.A. befindet und Prozesse in den k.A. eintreten möchten, darf die Entscheidung über den nächsten Prozess nicht unendlich lange verzögert werden (kein Lifelock, „After You“) Bounded Waiting o Nachdem ein Prozess einen Request für den k.A. abgegeben hat, ist die Anzahl der Eintritte in den k.A. durch andere Prozesse abgeschrankt (keine Starvation) Arten von Lösungen Softwarelösungen o Annahmen: Atomizität einer Lese- bzw Schreiboperation auf dem Speicher Hardwareunterstütze Lösungen o Mächtigere atomare Maschineninstruktionen Höhere Synchronisationskonstrukte o Vom API des BS zur Verfügung gestellt o Stellen dem Programmierer Funktionen und Datenstrukturen zur Verfügung o Semaphore, Monitor, Message Passing, … 13 / 59 Mutual Exclusion in Software Softwarelösungen HW Unterstützung: atomares Lesen/Schreiben eines Wertes vom/in den Speicher Synchronisation über globale Variable Busy Waiting: Warten auf das Eintreten einer Bedingung durch ständiges Testen Dekker-Algorithmus global: Prozess Pi: Peterson-Algorithmus Eleganter, leicher zu durchschauen als Dekker Algorithmus Mutual Exclusion o P0 setzt flag auf true → P0 blockiert o P1 im k.A. → flag = true → P0 blockiert Kein endloses gegenseitiges Blockieren o Annahme: P0 blockiert in while-Schleife (dh flag = true und turn = 1) o P1 will nicht in k.A. >< flag = true o P1 wartet auf k.A. >< turn = 1 o P1 monopolisiert k.A. >< P1 muss turn vor neuerlichem Eintritt in k.A. auf 0 setzen 14 / 59 Bakery-Algorithmus Lösung des k.A.- Problems für n Prozesse Nummernvergabe für k.A.; Prozesse mit der niedrigsten Nummer (>0) tritt als erstes ein Nummer 0 … keine Anforderung für k.A. Pi und Pj mit gleichen Nummern: Pi kommt vor Pj in k.A., wenn i < j Es gilt stets: neu vergebene Nummer >= vorher vergebene Nummern Hardwareunterstütze Lösungen Interrupt Disabling während k.A. o Für Uninprozessorsystem geeignet o Aber: Einschränkungen des BS beim Dispatching o Rückgabe der Kontrolle an das BS? o Schutz vor Instruktionssequenzen im BS Mächtigere atomare Maschineninstruktionen o Test and Set o Exchange (Swap) Test and Set Hardwareinstruktion, die zwei Aktionen atomar (dh ununterbrechbar) ausführt o Mutual Exclusion 15 / 59 Test and Set für k.A. Sicherung des k.A. mit Exchange Test and Set bzw Exchange Gilt für beide: Einfacher Prolog für den k.A. für beliebig viele Prozesse Starvation von Prozessen möglich Busy Waiting Bisherige Lösungen verwenden Busy Waiting: Iterieren, bis Synchronisationsbedingung erfüllt Prozess verschwendet CPU-Zeit mit Warten Kein geeigneter Mechanismus zur Synchronisation für Beneutzer-Code Blockieren der wartenden Prozesse in Blocked Queues (s Abschnitt „Prozesse“) Semaphore Grundlegendes Synchronisationskonstrukt ohne Busy Waiting (vom BS zur Verfügung gestellt) Semaphor S: Integer-Variable, auf die nach der Initialisierung nur mit zwei atomaren Funktionen, wait und signal, zugegriffen werden kann Ziel: Sichern eines kritischen Abschnitts auf „einfache Art“ Semaphore ist ein Record: Auf einen Semaphor S wartende Prozesse werden in die Blocked Queue von S (S.queue) gestellt Semaphoren müssen auf einen nicht-negativen Wert (für MutEx auf 1) initialisiert werden 16 / 59  Operationen auf Semaphoren: init, wait, signal Probleme mit Semaphoren Semaphoroperationen sind über Prozesse verteilt, daher unübersichtlich Operationen müssen in allen Prozessen korrekt verwendet werden Ein Fehlerhafter Prozess bewirkt Fehlverhalten aller Prozesse, die zusammenarbeiten Monitore Beispiele Producer-Consumer mit Puffer Produzent kann jederzeit schreiben Konsument muss auf Daten warten „in“: nächstes freies Puffer-Element; „out“ nächstes zu lesendes Element Mutual Exclusion: zu jedem Zeitpunkt darf nur ein Prozess auf den Puffer zugreifen (Semaphore „s“) Bedingungssynchronisation: ein Konsument darf nur dann lesen, wenn mindestens ein ungelesenes Datenelement im Puffer steht (Counting Semaphore „N“ spiegelt Anzahl der Elemente im Puffer wieder) P-C mit Ringbuffer Begrenzter Buffer mit k Elementen Lesen: mind ein „neuer“ Wert notwendig Schreiben mind ein Element frei 17 / 59  MutEx + Bedingungssynch. wie bei normalen Buffer + Bedingungssynchronisation: ein Produzent darf nur dann schreiben, wenn mindestens ein leerer Speicherbereich vorhanden ist (E) Hinweis! Reihenfolge von V-Operationen „beliebig“ ABER: Abfolge von P-Operationen ist relevant! Systemverklemmung (Deadlock), wenn Consumer bei leerem Puffer (N=0) in k.A. eintritt. Reader-Writer Problem Es gibt Lese- und Schreibprozesse, die auf eine gemeinsame Ressource zugreifen Beliebig viele Lese dürfen parallel lesen Schreiber benötigen exklusiven Zugriff 18 / 59 Dining Philosophers Problem 5 Philosophen denken und essen, jeder braucht dazu zwei Gabeln Zusätzlicher Semaphor, der max 4 Philosophen gleichzeitig das Aufnehmen der Gabel erlaubt atomare P-Operation für mehrere Semaphoren mP, mV: atomare Operation P und V für eine Menge von Semaphoren mP(S1, S2, …, Sn): blockiert Solange, bis alle Semaphore S1 bis Sn größer als 0 sind o Löst Probleme der Reihung von P-Operationen mV(S1, S2, …, Sn): erhöht alle Semaphore S1 bis Sn um 1 Monitor, Nachrichten (u. a. Synchr.-mechanismen) Monitor Softwaremodul, bestehend aus: o Prozeduren o Lokalen Daten o Initialisierungscode Eigenschaften o Zugriff auf lokale Variable: Monitorprozeduren o Eintritt von Prozessen in den Monitor über Monitorprozeduren o Max 1 Prozess zu jedem Zeitpunkt im Monitor Monitor sorgt explizit für MutEx, kein explizites Programmieren Gemeinsamer Speicher ist im Monitorbereich anzulegen Bedingungssynchronisation über Monitorvariable o Programmierung von Wartebedingungen für Bedingungsvariable (Condition Variables) o Monitoreintritt, wenn Wartebedingungen der Bedingungsvariablen erfüllt sind Condition Variables Lokal im Monitor (Zugriff nur im Monitor) Zugriff nur über Zugriffsfunktionen o cwait(c): blockiert aufrufenden Prozess bis Bedingung(svariable) c = true o csignal(c): Setze einen Prozess, der auf die Bedingung c wartet, fort ▪ wenn mehrere Prozesse warten, wähle einen aus ▪ wenn kein Prozess wartet, keine Aktion ▪ keine speichernde Wirkung (≠ Semaphore-Wait) 19 / 59 Monitor: Producer-Consumer Message Passing Methode zur Interprozesskommunikation (IPC) o in zentralen und verteilten Systemen Eine Nachricht ist eine atomare Datenstruktur → Datenkonsistenz Verschiedene Synchronisationssemantiken Funktionen zum Senden und Empfangen o send(destination, msg) o receive(source, msg) Charakteristika von Nachrichten Synchronisation o send: blocking, non-blocking o receive: blocking, non-blocking, test for arrival Datenverwaltung o Ereignissemantik: Warteschlange (Queue) o Zustandssemantik: empfangene Daten überschreiben alte Werte Adressierung o 1:1 vs 1:n physikalisch vs logisch direkt vs indirekt (Mailbox, Portadressierung) Ereignisnachricht für MutEx Prozesse verwenden eine gemeinsame Mailbox mutex und eine Nachricht (Token) Blocking receive, non-blocking send Locks Einfacher Sync.-Mechanismus o enter(lock): blockiert nachfolgende enter-Aufrufe o release(lock): gibt Lock frei enter und release durch den gleichen Prozess 20 / 59 Sequencer und Eventcounts Eventcount E: ganzzahliger Ereigniszähler o advance(E): erhöht E um 1 (Anfangswert: 0) o await(E, val): blockiert bis E >= val Sequencer S: ganzzahliger „Nummernserver“ o ticket(S): retourniert Wert von S und inkrementiert S (Anfangswert: 0) Zusammenfassung Anforderungen paralleler Prozesse o Konsistenter Zugriff auf gemeinsame Daten o Vorgegebene Reihenfolge von Aktionen Mutual Exclusion → Konsistenz Condition Synchronization → Reihenfolge Kritischer Abschnitt o Aktionen, die gemeinsame Daten manipulieren o mit Konstrukten zur Synchronisation gesichert Sicherung des kritischen Abschnitts o Lösungen abhängig vom Instruction Set o Unterstützung durch Betriebssystem → kein Busy Waiting! Semaphor o init, wait bzw. P und signal bzw.V o Achtung: Reihenfolge der wait Operationen Monitor Nachrichten 21 / 59 DEADLOCK Grundlegendes Permanentes Blockieren einer Menge von Prozessen, die um Ressourcen konkurrieren oder miteinander kommunizieren Zyklischer Ressourcenkonflikt zwischen zwei oder mehreren Prozessen: 1. jeder Prozess hält eine Ressource und 2. wartet auf eine Ressource, die gerade ein anderer Prozess hält erneuerbare vs konsumierbare Ressourcen Es gibt keine universelle Lösung des Problems Beispiel „Kreisverkehr“ siehe Foliensatz. Beispiel Synchronisation über Nachrichten (konsumierbare Ressourcen) Beispiel Mutual Exklusion, Prozesse greifen auf zwei gemeinsame Ressourcen zu; Mutual Exclusion Prozessfortschrittsdiagramm Deadlock 4 Deadlock-Bedingungen Drei Voraussetzungen des Systems 1. Mutual Exclusion o exklusiver Zugriff auf Ressourcen 2. Hold and Wait o Prozess kann Ressourcen halten, während er auf andere Ressourcen wartet 3. No Preemption o Zugewiesene Ressourcen werden den Prozessen nicht weggenommen 22 / 59  Auftretem einer bestimmten Ereignisfolge 4. Circular Wait o Geschlossene Kette von Prozessen, von denen jeder Prozess mindestens eine Ressource hält, die von einem anderen Prozess benötigt wird Deadlock tritt genau dann auf, wenn das Circular Wait nicht aufgelöst werden kann Circular Wait kann nicht aufgelöst werden, wenn Bedingungen 1 bis 3 gelten → Bedingungen 1 bis 4 sind notwendig und hinreichend für das Auftreten eines Deadlock Deadlock Behandlung Deadlock Prevention o Verhindern einer der 4 Deadlock-Bedingungen Deadlock Avoidance o Ressourcenreservierung, die zu Deadlock führen könnten, werden nicht gewährt Deadlock Detection o Ressourcenanforderungen werden immer gewährt, sofern Ressourcen vorhanden sind o Periodisches Überprüfen, ob ein Deadlock vorliegt und ggf Recovery Deadlock Prevention Betriebssystemdesign, das Deadlock ausschließt Indirect Deadlock Prevention o Verhindern der Bedingungen 1 bis 3 Direct Deadlock Prevention o Verhindern der Bedingung 4 (Circular Wait) Indirect Deadlock Prevention Mutual Exclusion (Bedingung 1) o Zielsetzung; kann nicht unterbunden werden Hold and Wait o Prozesse fordern alle Ressourcen auf einmal an o Blockieren, bis alle Ressourcen vorhanden sind → Lange Verzögerungen der Prozesse möglich → Schlechte Nutzung allokierter Ressourcen → Prozess braucht Wissen über Ressourcen, die er verwenden wird No Preemption a) Prozess gibt Ressourcen frei, wenn er eine weitere Ressource nicht bekommt; fordert Ressourcen zu einem späteren Zeitpunkt wieder an b) Anforderung eines Prozesses führt dazu, dass ein anderer Prozess Ressourcen freigeben muss o Anwendbar für Ressourcen, deren Zustand leicht gespeichert und später wieder hergestellt werden kann (zB Prozessor, beim Blockieren bei wait) 23 / 59 Direct Deadlock Prevention Protokoll: Verhinderung des Circular Wait o Strikte lineare Ordnung O für Ressourcenarten, zB O(Tape Drives) = 2 o Erste Anforderung: Prozess fordert eine Anzahl von Ressourcen der Art R i an (alle müssen in einem Schritt angefordert werden) o In der Folge werden für den Prozess nur Anforderungen von Ressourcen der Art Rk mit O(Rk) > O(Ri) zugelassen Ind. Beweis: das Protokoll verhindert Circular Wait o Ann: es gibt einen Circular Wait von P0 … Pn dh für alle i gilt: Pi belegt Ri und wartet auf R(i+1) mod n o Entsprechend dem Protokoll gilt daher: O(R0) < O(R1) < … < O(Rn) < O(R0) →lt Protkoll unmöglich! o Das Protokoll verhindert Deadlock Ineffizienz: unnötiges Zurückweisen von Anforderungen aufgrund der Ordnung Deadlock Avoidance Bedingungen 1 bis 3 erlaubt, selektives Vergeben von Ressourcen o Process Initiation Denial: ein Prozess wird nicht gestartet, wenn seine Anforderungen zu einem Deadlock führen könnten o Resource Allocation Denial: eine Ressourcenanforderung eines Prozesses wird verwehrt, wenn dadurch ein Deadlock entstehen könnte Höhere Parallelität als Deadlock Prevention Voraussetzung: Ressourcenbedarf der Prozesse muss bekannt sein Notation n Prozesse m Ressourcenkategorien Vektoren o Resource = (R1, R2, …, Rm) Gesamtzahl der Ressourcen im System o Available = (V1, V2, …, Vm) Anzahl der nicht vergebenen Ressourcen Matrizen o Claim = o Allocation = Process Initiation Denial Prozess Pn+1 wird nur gestartet, wenn seine Ressourcenanforderungen keinen Deadlock hervorrufen können, dh wenn: 𝑛 𝑅𝑖 ≥ 𝐶(𝑛+1)𝑖 + 𝛴𝑘=1 𝐶𝑘𝑖 Nachteil: Annahme, dass alle Prozesse ihre Ressourcen gleichzeitig anfordern → Einschränkung der Paralleliltät Resource Allocation Denial – Banker’s Algorithm State: Ressourcenbelegung der Prozesse, charakterisiert durch Vektoren und Matrizen Safe State: es existiert eine Folge von Schritten, mit der der Algorithmus alle Prozesse als „finished“ markiert in den Endzustand Unsafe State: es existiert keine solche Schrittfolge 24 / 59 Banker’s Algorithm – zusätzliche Notation Zusätzliche Matrix o Required = Vor einer Ressourcenzuweisung: Test, ob die Zuweisung zu Safe State führt Safe State → Zuteilung der Ressourcen Unsafe State → keine Ressourcenzuteilung Banker’s Alg. – Bemerkungen Safe State → kein Deadlock möglich Unsafe State → Deadlock möglich, muss aber nicht eintreten o Prozesse benötigen Ressourcen nicht während der gesamten Ausführungsdauer o Maximalanforderungen in den Ressourcenkategorien treten nicht gemeinsam auf Strategien zur Deadlock Avoidance nehmen Unabhängigkeit der Prozesse an (keine Bedingungssynchronisation zwischen Prozessen) Banker’s Algorithm Anwendung 25 / 59 Beispiel 1 Beispiel 2 Deadlock Detection Ressourcenanforderungen werden immer gewährt, sofern Ressourcen vorhanden Notwendige BS-Vorkerhungen o Algorithmus, um Deadlock zu erkennen o Strategie zur Deadlockbehebung (Recovery) Deadlocküberprüfung zb bei jeder Ressourcenanforderung → CPU-intensiv Bemerkungen Optimistische Annahme, dass Prozesse keine zusätzlichen Ressourcen für ihre Fertigstellung benötigen Wenn diese Annahme nicht stimmt, kann es später zu einem Deadlock kommen o Dieser Deadlock wird beim nächsten Aufruf des Deadlock Detection Algorithmus erkannt 26 / 59 Deadlock Detection Algorithm Beispiel Deadlock Recovery Auflösen eines erkannten Deadlocks Abbrechen aller betroffenen Prozesse (häufig angewandte Strategie) Rollback aller beteiligten Prozesse bis zu einem definierten Aufsetzpunkt (Deadlock kann sich wiederholen) Abbrechen einzelner beteiligter Prozesse, solange bis der Deadlock beseitigt ist (wiederholtes Aufrufen des Detection Algorithm) Ressourcen werden Prozessen schrittweise entzogen und an andere Prozesse vergeben, bis kein Deadlock mehr vorliegt o Rücksetzen der Prozesse, denen Ressourcen entzogen werden, bis zum Punkt der Zuweiseung Auswahl des zu unterbrechenden Prozesses: Wenigste bisher verbrauchte CPU-Zeit? Geringste Anzahl an bisher belegten Ressourcen? Geringster Fortschritt? Integrierte Deadlock-Strategie Kombinieren der genannten Ansätze o Gruppieren der Ressourcen in Klassen und Ordnen der Klassen ▪ Swappable Spaces (Sekundärspeicher) ▪ Prozessressourcen (I/O-Geräte, Files, etc) ▪ Hauptspeicher o Circular Wait Prevention zwischen Klassen o Verwendung der best-geeignten Strategie in den einzelnen Klassen ▪ zB Hauptspeicher – Prevention: Preemption, Processressourcen - Avoidance 27 / 59 Zusammenfassung 4 Bedingungen (notwendig und hinreichend) o Mutual Exclusion o Hold and Wait o No Preemption o Circular Wait Deadlock Prevention Deadlock Avoidance Deadlock Detection und Recovery 28 / 59 MEMORY MANAGEMENT Grundlegendes Speicherverwaltung Effektive Aufteilung und Verwaltung des Arbeitsspeichers für BS und Programme Anforderungen o Partitioning (Speicheraufteilung auf Prozesse) o Relocation (flexible Positionierung von Code und Daten im Speicher), Virtual- Memory Management o Protection (Speicherschutz) o Sharing (gemeinsamer Zugriff auf Speicher) o Performance (erffektive log./phys. Organisation) Partitioning (Partitionierung des Speichers) Einfache Ansätze zur Speicherverwaltung: Prozesse werden als Ganzes im Hauptspeicher (=Arbeitsspeicher) abgelegt Grundlage für moderne Speicherverwaltung o Fixed Partitioning o Dynamic Partitioning o Buddy System Fixed Partitioning Unterteilung des Hauptspeichers in nicht überlappende Teile Prozesse, die kleiner gleich einer Partition sind, können geladen werden o Gleiche bzw ungleiche Partitionsgröße Auslagern eines Prozesses durch das BS, wenn alle Partitionen belegt sind Programme, die größer als Partitionen sind ➔ Programmierung von Overlays 29 / 59 Dynamic Partitioning Partitionen variabler Länge und Anzahl Zwischen Partitionen entstehen Löcher ➔ Compaction: Verschieben der Partitionen, um statt Löchern größeren zusammenhängenden freien Speicherbereich zu erhalten Placement Strategies beim Einfügen o Best Fit o First Fit o Next Fit Speicherfragmentierung Interne Fragmentierung: Verschwendung von Speicherplatz innerhalb einer Partition; Daten und Programm füllen Partition nicht aus (zB bei fixer Partitionierung) Externe Fragmentierung: Zerstückelung des Speicherbereichs außerhalb der Partitionen (zB bei dynamischer Partitionierung) Buddy System Versuch, die Nachteile der vorher angeführten Strategien zu verringern Zerlegung des Speichers in „Buddies“ der Größe 2k , mit MinVal