Betriebssystem ZHAW

Unterstüzt diverse File Systeme
UNIX -> ufs (fast file system), rfs (remote file system), nfs (network file system)
LINUX -> ext2 (extended file version 2), ufs (dito), nfs (dito)
Grundsätzlich werden remote Filesysteme in den lokalen Verzeichnisbaum gemountet. NFS ist eine Implementation oder eine Spezifikation. 
Filesystem: Systemschicht
- Bootblock: Bootcode zum starten des BS
- Superblock: Beschreibt aufbau des Filesystems
- Inode Liste: Inodes enthalten Informationen zu Files
- Datenblöcke: Beginnen nach der Inode Liste, enthalten echte Daten
- Directory Blocks: Gehören zu Directory Files, enthalten die I-Node Nummer und den Filenamen
- I-Node: Enthält sämtliche Informationen zum File, Zugriffsrecht, Datum, Open Count, etc   

# Filegrössen bestimmen
NFS:
- kleine Files direkt Zeiger auf Datenblöcke
- grosse Files Zeiger auf Blöcke
NTFS:
- kleine Files -> im Datenfeld des MFT-Records
- grosse Files -> indexed allocation von Clustern
Befehl: ls -al Filename 
-rw-rw-r-- 1 tha tha 531 <- Grösse

  Wiederherstellbares File System, Daten in Cluster gespeichert, unterstützt mehere Datenströme. Clustering heisst dass mehrere Sektoren in einem Cluster gespeichert werden. Ein Sektor sind 512 Bytes und Clustergrössen zwischen 512B - 4KB. Es gibt ein Master Table File als Array von 1KB of Records, ähnlich wie I-Nodes. Die MFt iist eine Sammlung von Atrribut/Wert Paaren.
Security: Jedes File hat eine ACL (access control list)

Bus Interface

• Ansteuerung der externen Einheiten

Recheneinheiten

• Logische und Arithmetische Rechenleistung der CPU

Adress-, Daten, und Statusregister

• Für Benutzer sichtbar
• Von System- und Anwenderprogrammen genutzt

Instruction (Control) Unit

• Steuereinheit : Interpretation und Ausführung der Instruktionen

• Er unterbricht aktuelle Instruktionsausführung des Prozessors
• KOntrolle geht an den Interrupt Handler über
• evtl. wird zu einem anderen Programm umgeschaltet

Asynchrone Interrupts

• Timer
• I/O Devices
• Hardwarefehler

synchrone Interrupts

• Programmfehler z.B Division durch 0
• Trap --> Exception durch einen User-Prozess
• SWI (Software Interrupts)

Mit den Interrupts wird die CPU last besser verteilt. Wenn ein Programm auf I/O wartet, dann kann es auf den Interrupt warten und muss kein busy waiting betreiben

CPU

Hauptspeicher (Code & Memory)

I/O Module

• Sekundärspeicher
• Monitore & Tastaturen
• Kommunikation

Bus

• Verbindung zwischen i/O Geräten

Das sind die Ressourcen die das Betriebssystem uns zur Verfügung stellt.

Usermode

• Code kann nicht direkt auf Hardware oder Referenzspeicher zugreifen.
• Code muss an System-Apis delegiert werden um Hardware oder Speicher zuzugreifen
• Dadurch können Sitzungen aus Abstürzen wieder hergestellt werden.
• Der Grossteil des ausgeführten Codes im PC ist im Bereich des Benutzermodus

Kernel Mode:

• Uneingeschränkter Zugriff auf Hardware
• Jeder CPU Befehl ausführen und auf jede Speicheradresse verweisen
• Ist die vertrauenswürdigste Funktion der untersten Ebene des Betriebssystem.
• Abstürze in Kernelmodus sind katastrophal --> Ganze PC geht hops

System Calls:

• Schnittstelle zwischen Anwendersoftware und Systemsoftware
• rufen System-funktionen auf
• Schalten zwischen Kernel und Usermode um

Ablauf

• Anwenderprogramm stellt Parameter bereit(Register, Stack)
• Ruft Bibliuotheksfunktion auf: normaler Prozerduraufruf
  • Kernler überprüft Parameter
  • Kernel ruft den System Call handler auf
  • Handler wird ausgeführt
• Rücksprung in die Bibkiotheksfunktion
• Rückkehr ins Anwenderprogramm

Drei Techniken für Kommunikation mit I/O Geräten

Programmen I/O oder synchroner I/O

• CPU wartet bis jede I/O Operation beendet wird -->busy wait

Interrupt Driven I/O oder asynchroner I/O

• CPU führt währen I/O Operation Code aus, wird unterbrochen wenn I/O Operation fertig ist
• CPU kann andere Arbeiten ausführen

Direct Memory Access

• Speicherblock mit Daten wird vom/zum Speicher übertragen ohne Rechenleistung der CPU zu beanspruchen

Je grösser der Speicher wird, desto langsamer wird der Zugriff auf die Daten.

Formel ist wie folgt

TN = Zugriffszeit auf nächsten Speicher

h = hit ratio, m = Missrate 1-h

Ta = TC + (1-h) * TN

Tc < Ta <Tm

Ist eine dynamische Daternstruktur, wird von den meisten Mikroprozessoren in der Hardware direkt unterstüzt

push(das objekt oben auf den Stapel legen)

pop(liefert das obesrte objekt und ernfertn es vom Stapel)

peek(nachsehen, liefert das erste objekt ohne es zu entfernen)

In Mikroprozessoren gibt es oft ein spezielles Register, den Stackpointer (Stapelzeiger). Dieses Register enthält eine Speicheradresse, die auf den aktuellen Stapeleintrag (des aktuellen Prozesses) zeigt. Viele Befehle/Operationen des Mikroprozessors nutzen diesen Stapeleintrag. Unter anderem gibt es Befehle, mit denen man in den Stack schreiben (z. B. push beim x86-Prozessor) oder von ihm lesen kann (z. B. pop). Dabei wird automatisch der Stapelzeiger verringert oder erhöht.

Unit of Resource Ownership

• Eine Einheit, die Ressourcen besitzt
• ein virtueller Adressraum, in dem das Prozess Image steht
• hat Kontrolle über Ressourcen ( Files, I/0 Geräte, etc)

Unit of Scheduling

• Eine Einheit die schedulierbar ist
• CPU-Scheduler weist der CPU einen Prozess zu (dispatch)
• zum Prozess gehören der Execution State (PC, SP, Register) und eine Ausführungspriorität

• Prozesse werden gleichzeitig "concurrent" ausgeführt
• Sie können mitten der Ausführung unterbrochen und später weiterverarbeitet werden
• Erhalten von CPU vorgegebene Zeitintervall --> abhängig von Schedulingverfahren

Dispachter: Teilt die CPU zu

Scheduler: Plant CPU Zuteilung so das :

• kein Prozess die CPU als Geisel nimmt
• wer als nächster kommt und schaltet zwischen Prozesse um

Prozess können wir aus Sicht der Warteschlangen-Diagramm :

• Beschreibt wo sich ein Prozess befindet
• Mehrere Prozesse können sich im gleichen Zustand befinden -->"Not Running" und würden somit in der Warteschlange

Zustandsmodell:

• Beschreibt den momentanen Zustand eines Prozesses

new - Prozess ist erzeugt, aber noch nicht gestartet

ready - Prozess kann ausgeführt werden

running -Prozess wird gerade ausgeführt (ist aktiv)

blocked - Prozess wartet auf Ereignis z.B I/O etc.

suspend blocked - Prozess wurde ausgelafert, wartet auf Ereignis

suspend ready - Prozess ist ausgelagert aber bereit für Aktivierung

Das Betriebssystem unterhält & verwaltet verschiedene Tabellen für die Verwaltung von Prozessen & Ressourcen

• Speicher    Memory Tabellen
• Geräte        I/O Tabellen
• Files           File Tabellen
• CPU           Prozess Tabellen

Prozess Image besteht aus

• Benutzerprogramm (Code) , Daten, Stack, Heap
• Kontext, im (PCB) Prozesskontrollblock gespeichert

Das BS hat nur Zugriff auf Prozessdaten, wenn der Prozessimage teilweise im physikalischen speicher steht.

Prozessimage sind im virtuellen speicher abgelegt und werden mittel MMU auf der physikalischen speicher abgebildet

Kernel mit eigenem Kontext (ältere BS)

• nur Benutzerprogramme sind Prozesse
• innerhalb eines Benutzer-Prozesskontextes wied nie Betriebssystemcode ausgeführt
• Betriebssystemcode
  • eigenständiges Programm mit eigenem Kontext
  • wird im System Mode ausgeführt

BS-Funktionen im Kontext der Benutzerprozesse

• Context Switching meist ausserhalb von Prozessen
• BS stellt "nur Funktionen" zur Verfügung
  • Betriebssystemcode im Kontext des Benutzerprozesses
• System Calls, Interrupts, Traps
  • CPU schaltet in System Mode, Ausführung aber im Benutzerkontext

Prozessbasiertes Betriebssystem

• BS ist eine Sammlung von Systemprozessen
• kleine Anzahl von Systemfunktionen (Prozesswechsel, IPC)
• grösere Kernel Funktionen sind eigenständige Prozesse

Vorteile

• Fördert modulare BS Implementation mit sauberen Schnittstellen
• nicht kritische Funktionen problemlos als Prozesse implementierbar
• implementieren z.B. Funktionen, die nicht einen speziellen Service anbieten, sondern allgemeiner sind: accounting
• gut geeignet für Multiprozessorsysteme
• schlanker Kernel
• leicht erweiterbar

Prozess : unit of resource ownership

• Schwergewicht Prozesse
• virtueller Adressraum, Programmcode, Daten, Betriebssystem-BRessourcen
• single-thread of execution

Thread : unit of scheduling

• leichtgewicht prozess
• immer an Prozess gebunden
• unabhängiges Stück Code innerhalb eines Prozesses
• teilt sich mit anderen Threads: Adressraum, Daten, Kontext
• hat eigene: lokale Variablen, Register, PC, Stack, Stackpointer
• speichert Threadkontext wenn inaktiv

Multithreading --> mehrere Threads pro Prozess

Vorteile :

• Threadwechsel weniger aufwendig  --> günstig
• Aufgabenteilung
• unterstützt Multicore-Prozessoren

Wir wissen das aus einen Prozess mehrere Threads entstehen können. Dies erlaubt uns die arbeiten innerhalb eines Prozess auf mehrere Threads aufzuteilen oder uns nur auf bestimmte Aufgaben zu konzentrieren wenn uns Bedingungen gegeben werden.

Threads werden gebraucht bei :

• DatenServer bei mehreren Anfragen gleichzeitig zu verarbeiten
• Befehle im Hintergrund auszuführen
• Parallelverarbeitung mit viel Kommunikation
• Programme mit Vorder- und Hintergrundaktivitäten
• Repetitive nummerische Aufgaben

User Level Threads

• Kernel weiss nicht, das dies ein Thread ist
• Laufen im Benutzerbereich
• Realisiert mit Bibliotheken
• Anwendung verantwortlich für Threadmanagement
• Threadsheduling applikationspezifisch wählbar
• Bei Blockade --> Prozess blockiert

Kernel Level Threads

• Kernel weiss, das es Threads gibt
• Kernel stellt Systemfunktionen für Threadverwaltung zu Verfügung
• API zu Threadfunktionen im Kernel
• Kernel verwaltet KOntextinformationen von Prozessen und Threads
• Threadwechsel erfordert Intervention des Kernels
• Thread is ein Schedulierbare Einheit
• Thread können auf mehreren Prozessoren verteilt werden
• light weight prozess

+

• Threadwechsel involviert Kernel nicht
• Läuft auf jedem BS ( Bibliothek)
• Schedulingverfahren kann anwendungsspezifisch gewählt werden
• schnell und einfach

-

• Die meisten System Calls blockieren --> Prozess blockiert und damit auch die anderen Threads des Prozesses
• NUr der Kernel kann Prozesse den Prozessoren zuweisen, d.h Parallelverarbeitung nicht möglich

Man kann in grob in unterbrechende(preemptive) und unterbrechende(nonpreemptive) aufteilen.

Bewertungskriterien:

Antwortzeit: Wie lange geht es bis Task reagiert?

Durchsatz: Wie viel Tasks pro Zeit werden verarbeitet?

Fairness: werden Tasks vernachlässigt?

Starvation: können Tasks nie an die Reihe kommen?

Implementierung/Overhead: wie aufdenig ist die Implementierung des Verfahrens?

Nonpreemptive Scheduling

• First Come First Served: Prozesse in ihrer Reihenfolge ihres Eingangs bearbeiten. Neuzuteilung der Prozess findet wieder statt, wenn der laufende Prozess zu warten beginnt oder seine Ausführung beendet ist.
• Shortest Job First: Die kleine Prozesse werden bevorzugt.Es lässt sich in Fällen einsetzen, in denen die benötigte Rechenzeit für die einzelne Aufgaben aus Erfahrungswerten gut vorhergesagt werden kann
• Priority Scheduling:Bei dieser Strategie wird jedem Prozess eine Priorität zugeordnet. Die Abarbeitung erfolgt dann in der Reihenfolge der Prioritäten.Diskussion: Prozesse mit tiefen Prioritäten können verhungern, mögliche Abhilfe --> dynamische Prioritäten, Prioritäten in Funktion der zeit anpassen.

Preemptive Scheduling

• Round Robin:  Wie bei FCFS aber mit kurzen zeitspannen(q). Einem Prozess wird die CPU für eine Zeitspanne zugeteilt.
• Multilevel Scheduling: In üblichen Systemen verschiedene Arten von Jobs: batch, interaktiv, systembezogen, rechenintesivJobs erhalten je nach Art verschiedene Prioritäten, für jede Priorität eine Queue, Scheduler wählt immer Jobs mit höchster Priorität
• Multilevel Feedback Scheduling: Bei diesem Verfahren gibt es mehrere Warteschlangen unterschiedlicher Priorität. Prozesse werden in Abhängigkeit von ihrem bisherige Ressourcenverbrauch dynamisch in eine dieser Warteschlangen eingeordnet

Unix Scheduling TRADITIONELL

Prioritäten:

• Basiert auf Prozesstyp und Geschichte (verbrauchte CPU-Zeit)
• Tiefer Wert = hohe Priorität

CPU und nice Komponenten so gewählt, dass Prioritätsband nicht verlassen werden kann.

Während dem Laufen:

        Wird ein Prozess mehrmals vom Zeitgeber unterbrochen(60 mal pro Sekunde)

        Der Usage Counter wird jeweils inkrementiert zu Beginn des Zeitintervalls

Unix fair Share Scheduling (FSS)

Versucht die CPU fair auf die verschiedenen Gruppen von Prozessen zu verteilen. Wenn beispielweise 4 Benutzer gleichzeitig jeweils einen Prozess ausführen teilt der Scheduler die verfügbaren CPU-Zyklen so, dass jeder Benutzer 25% aller Zyklen bekommt.

Real Time Systeme (Robotik, Laborexperimente, Luftfahrt usw.)

Systeme die auf Ereignisse in der „äusseren Welt“ reagieren, Ereignisse finden in der „reellen Zeit“ statt. Es gibt Hard und Soft Real Time Systeme

Typische Eigenschaften:

• zeitkritische Tasks wiederholen sich in regelmässigen Abständen
• Dauer und die benötigten Betriebsmittel sind bekannt

Systeme verhalten sich korrekt, wenn

• Das logische Resultat einer Berechnung stimmt
• Das Resultat zum richtigen Zeitpunkt ausgeliefert wird

Hard Real Time Systeme(Flugzeugsteuerung, Landeanflug)

• Deadlines müssen eingehalten werden, sonst Ausfall des Systems

Soft Real Time Systeme (Bank überweisung)

                Deadlines sollten eingehalten werden, sonst schwerwiegende Konsequenzen

3 Real Time Task Klassen

• Kritische Tasks(periodische, asynchrone, sporadische Tasks)
• Nicht kritische, aber notwendige Tasks
• Nicht notwendige Tasks(nice to have)

Rate Monotonic Scheduling (RMS)

Für unterbrechbare, periodische Jobs. Die Prioritäten werden statisch anhand Periodendauer eines Jobs festgelegt, je kürzer Periodendauer eines Jobs, desto höher ist seine Priorität.

Task müssen unterbrechbar, periodisch und unabhängig sein.

Was ist daran so interessant? Grenze für erfolgreiches Scheduling kann berechnet werden.

Rechenzeit(C)/Periode(T) = Auslastung(U≤1)à zu optimistisch, nur bei perfektem Schedule möglich

Korrekter Scheduler für n Tasks

Garantiert bei Einhaltung folgender Grenze

Bei Einhaltung obiger Grenze:

                Schedule immer garantiert, aber eher konservativ für grosse n für 70% CPU Auslastung

Deadline Scheduling

Idee: Tasks zum richtigen Zeitpunkt starten resp. Beenden

Funktionsweise: Alle zu dem betrachteten Zeitpunkt bereitstehende Task werden nach aufsteigenden Fertigstellungsterminen geordnet.

Der Task der als erste fertig sein muss erhält den Prozessor,

RT-Linux

Antwortzeiten in der Grössenordnung von Mikrosekunden

• Abhängig von Treibern: wie lange wird die CPU blockiert
• Abhängig von anderen RT-Tasks

Kritische real-time Tasksà foreground tasks

                Threads

                Direktzugriff auf Hardware & Interrupts

Nicht kritische Tasksà background tasks

                Linux tradionell asl taks

                Visualisierung

                Vernetzung etc.

Beispiel Vorlesung, Milch Kaufen gehen 2 Mitbewohner "Kühlschrank-Problem"

Race Condition

• Mindestens 2 Tasks greifen auf gemeinsame Daten zu
• Mindestens 1 Zugriff ist ein Schreibzugriff
• Das Resultat hängt von Ausführungsreihenfolge der beteiligten Tasks ab

Mögliche Abläufe der Programme

• Unabhängig
  • Keine gegenseitige Beeinflussung
  • Nutzung verschiedener Ressourcen
  • Keine Synchronisation/Koordination notwendig
• Abhängig
  • Programm kooperieren
  • Nutzen Daten und Ressourcen gemeinsam
  • Zugriff muss synchronisiert bzw. koordiniert werden

Lösung für Kühlschrankproblem --> kritischer Abschnitt (abschliessbarer Kühlschrank, der, der einkaufen geht hat den Schlüssel)

Taskzugriff auf gemeinsame Daten/Ressourcen --> Task befindet sich in seinem kritischen Abschnitt

Aufenthalt im kritischen Abschnitt, muss gegenseitig ausschließend seinà zu jedem Zeitpunkt befindet sich höchstens ein Task im kritischen Abschnitt

Zutritt zum kritischen Abschnitt --> nur über „Erlaubnis“

Gegenseitiger Ausschluss --> Mutual exclusion = Mutex

Support für gegenseitigen Ausschluss muss folgende Anforderungen erfüllen:
- nur ein Task darf sich in seinem kritischen Abschnitt aufhalten (Tasks aus der
Menge der Tasks, die auf die gemeinsamen Daten oder Ressourcen Zugriff
haben)
- ein Task, der sich nicht im kritischen Abschnitt befindet und anhält, darf dies
nur tun ohne andere Tasks zu beeinflussen
- wartet ein Task auf Eintritt in den kritischen Abschnitt, muss ihm dieser irgend
wann auch gewährt werden
- wenn sich kein Task im kritischen Abschnitt befindet, muss jedem Task der in
den kritischen Abschnitt eintreten möchte, sofort Eintritt gewährt werden
- es dürfen keine Annahmen zur Abarbeitungsgeschwindigkeit von Tasks oder zur
Anzahl Prozessoren gemacht werden
- ein Task bleibt nur für eine endliche Zeit in seinem kritischen Abschnitt

• Reine Softwarelösungen
  • Software-Algorithmen, deren Korrektheit von keinen weiteren Bedingungen abhängt

• Hardwarelösungen
  • Unterstützung durch spezielle Maschineninstruktionen
• Lösungen mit Hilfe des Betriebssystems
  • stellen dem Anwender Funktionen und Datenstrukturen zur Verfügung
  • Semaphore, Mutexes, etc.
• Lösungen zusammen mit Programmiersprache
  • Monitore, z.B. Java

Software Lösung 1

Mittels Busy Wait:

• Task wartet aktiv
• Er konsumiert Rechenzeit, bis Scheduler einen Task-Switch durchführt
• Wird auch Spinnlock genannt

Diskussion:

• Gegenseitiger Ausschluss wird zwar erreicht, aber Tasks können nur abwechselnd den kritischen Abschnitt durchlaufen

Semaphore

Der Semaphor ist eigentlich eine Datenstruktur(integer), die zugriff erlauben und verweigern kann auf eine Ressource in einer Multi-Processing Umgebung.

Operationen auf Semaphore:

• Wait(S) Semaphor schliessen auch P(S), down(S)
• Post(S) Semaphor öffnen auch V(S), Up(S),signal(S)

Vorteile:

• Kein Busy wait
• Wartende Tasks
  • In Queue eingereith
  • Blockieren bis Sperre Frei

Probleme:

• Wait(s) & post(s) ev. Über mehrere Tasks verteilt
  • Schwierig den Überblick zu behalten à fehleranfällig
  • Fehler schwierig zu finden, treten nur unter bestimmten Bedingungen auf
  • Anwendung muss in allen Tasks korrekt sein

Monitore

Ist ein Softwaremodul, die Daten Prozeduren und eine Initialisierungssequenz enthält. Jedes Java Objekt ist ein Monitor. Eingänge in den Monitor sind synchronized Methoden

Funktionsweise:

• Zugriff auf lokale Variable nur über Monitormethoden
• Zutritt in Monitor mit Aufruf einer dieser Methoden
• Nur ein Task kann Code innerhalb des Monitors ausführen
• Andere Tasks: warten auf Eintritt, warten auf Bedingung im Wartebereich

Unterstützung durch Prozessorhardware (Hardware unterstützt nur, ist keine Lösung!)

Verhindert, dass laufende Programme an beliebigen Stellen unterrbrochen werden können

Möglichkeiten:

• Interrupt ausschalten
  • Problematisch in Multicore-Systemen
• Atomare Instruktionen für
  • TAS: Test and Set
  • CAS. Compare And Swap
• Neu: Transactional Memory(HW noch eher experimentell)

Interrupt ausschalten

• Nur auf Uniprozessoren möglich bzw. sinnvoll, Performancebusse à kein Multiprogramming
• Wird in Kernelprogrammierung angewendet
  • Kernel dürfen nur an sicheren Stellen unterbrochen werden
  • Unterbrüche, aber nur kurz

Idee: Nur Interrupts könne Instruktionsfluss unterbrechen, einfach zu implementieren, realisiert MUTEX

Interrupt abschalten -> keine Unterbrechungen -> mutual exclusion garantiert

InterruptOFF(); kritischeAbschnitt();InterruptOFF();)

Test and Set

Idee: Zutritt zu kritischem Abschnitt Lösung: Sperrvariable(Lock) gleichzeitig lesen & setzen

• „Anfragen und Sperren“ nicht unterbrechbar
• Sonst inkonsistente Sichten möglich

Funktionalität:

Initialisierung: lock = false -> offen

Rückgabewert:

                False, wenn „Test and Set“ erfolglos bzw. das Lock gesperrt war

                True, wenn „Test and Set“ erfolgreich bzw. das Lock offen war

Deadlock (Verklemmung)
• Tasks warten gegenseitig auf Freigabe von Ressourcen
• kein Task arbeitet weiter
 Livelock (Threshing)
• Tasks arbeiten, aber Arbeit ist nicht produktiv
• Arbeit: ungewollter busy wait
Starvation (Verhungern)
• Prozess erhält keinen Zugriff auf Ressource(n)
• Ursache, z.B. unfaire Zuweisungspolicy: FILO (Stack)
• Abhilfe: nur faire Policies verwenden, z.B. FIFO

Voraussetzungen für einen Deadlock
1. Mutual exlusion
mindestens eine Ressource ist exklusiv reserviert
2. Hold and wait
mindestens ein Task hat eine Ressource exklusiv reserviert und wartet
auf weitere Ressourcen
3. No preemption
reservierte Ressourcen können dem Task nicht entzogen werden
(freiwillige Rückgabe nur, wenn Aufgabe gelöst)
4. Circular wait
geschlossene „Kette “ von Tasks existiert, in der jeder Prozess mindestens
eine Ressource reserviert hat, die auch von einem Nachfolger in der
Kette benötigt wird
• Auftreten eines Deadlocks
- Bedingungen 1-3 sind Vorbedingung, genügen aber nicht für einen Deadlock,
erst Bedingung 4 zusammen mit 1-3 konstitutiert einen Deadlock.
- Deadlock, wenn sich die Circular Wait Bedingung nicht lösen lässt
die Circular Wait Bedingung kann nicht gelöst werden, wenn Bedingungen
1, 2 und 3 gegeben sind
- alle 4 Bedingungen zusammen bilden eine notwendige und hinreichende
Bedingung für Deadlock

3 Möglichkeiten zur Verhinderung
• keine Deadlocks zulassen
- verhindern (prevention)
- vermeiden (avoidance)
• Deadlocks zulassen
- diesen Zustand lösen,
wenn er eingetreten ist
• das Problem ignorieren
- annehmen, dass kein
Deadlock auftritt
- "the ostrich algorithm"
- die meisten Betriebssysteme
inkl. UNIX, Linux, etc. verwenden diese Methode

Stellen Ressourcenzuordnungn dar.

Ressourcengraf

- Kreise: Tasks

- Rechtecke: Ressourcen

- Pfeil von Ressource ->Task: Task hat Ressource alloziert

- Pfeil von Task -> Ressource: Task fordert Ressource an

- Ressourcen mit mehreren Instanzen: jede Instanz entspricht einem Punkt innerhalb des Rechtecks

• Deadlock existiert
- Prozess P2 wartet auf Ressource R2 , die von Prozess P3 gehalten wird
- Prozesse P3 wartet auf R3, die von den Prozessen P1 und P2 gehalten wird
- Prozess P1 wartet auf Ressource R1, die von Prozess P2 gehalten wird

Betriebssystem überprüft
• ob ein Deadlock aufgetreten ist
• falls ja
- Deadlock auflösen
- lauffähigen Zustand wiederherstellen

 Erkennen
• z.B. Verfahren von Coffman (siehe Stallings 5th ed., Brause)

Wann Überprüfung?
• wenn Task auf Ressource warten muss (eher zu aufwendig)
• z.B. jede halbe Stunde oder jede Stunde, etc.
• wenn CPU Auslastung unter bestimmten Wert (z.B. 40%) sinkt

Möglichkeiten zum Lösen von Deadlocks
1. alle beteiligten Tasks stoppen
2. alle beteiligten Tasks auf Checkpoint zurücksetzen
3. beteiligte Tasks der Reihe nach stoppen, bis Deadlock gelöst
4. beteiligten Tasks Ressourcen wegnehmen, bis Deadlock gelöst
Strategie zur Wahl von Tasks bei 3. und 4.
• Task, der am wenigsten CPU konsumiert hat
• Task, der am wenigsten Output produziert hat
• Task, der am wenigsten Ressourcen alloziert hat
• Task mit kleinster Priorität
• Task, der längste geschätzte Rechenzeit hat (?)

Interprozesskommunikation (IPC) bezeichnet verschiedene Verfahren des Informationsaustausches zwischen den Prozessen eines Systems.

2 Varianten von IPC:

• Innerhalb eines System(1 BS)
  • Kommunikation zwischen Prozessräumen im gleichen Speicher
• Zwischen verschiedenen Systemen(2 BS)
  • Kommunikation zwischen Prozessen über ein Netzwerk

Prozesse arbeiten zusammen um (für beide Datenaustausch notwendig):

• Gemeinsam eine Aufgabe zu lösen
• Gemeinsam Ressourcen zu nutzen

Gründe für Zusammenarbeit

• Parallelverarbeitung
  • Leistungssteigerung (Rechenlast auf mehrere CPU verteilt)
  • Benutzerfreundlichkeit (mehrere Aufgaben gleichzeitig ausführen)
• Vereinfachte Strukturierung von Anwendungen
  • Anwendungen in kleine Einheiten unterteilen
  • Einfachere Struktur (übersichtlich, geringere Fehleranfälligkeit)
• Daten- und Informationsaustausch
  • Gemeinsame Datenhaltung
  • Client/Server Anwendungen
• Echtzeitsysteme
  • Verschiedene Aufgaben müssen verschieden oft ausgeführt werden,aber gemeinsames Resultat notwendig

Das Erzeuger/Verbraucher Problem thematisiert die Zugriffsregelung auf eine Datestruktu mit elemterzeugenden(schreibenden) und elemtverbrauchenden(lesenden) Prozessen.

Somit teilen sich zwei Prozesse einen Puffer mit fester Grösse.

Einer der Prozesse(Erzeuger) legt Informationen in den Puffer, der Verbraucher nimmt sie heraus.

Es soll verhindert werden das der Verabraucher den Puffer zugreift wenn dieser leer ist oder der Erzeuger auf diese Datenstruktur zugreift.

Eine mögliche Lösung dafür wäre, die Anzahl Nachrichten in einem Puffer mit einer Variable "count" zu verfolgen. Wenn count max ist geht Erzeuger schlafen und kann keine Nachricht mehr hinzufügen. Wenn count 0 ist geht Verbraucher schalfen und kann keine Nachricht entfernen.

Man geht nun von der Situation aus, dass eine Menge von Lesern und Schreibern einen gemeinsamen kritischen Bereich betreten wollen. Dabei gilt es jedoch, folgende Bedingungen einzuhalten:

• Im kritischen Abschnitt dürfen sich niemals Leser und Schreiber gleichzeitig aufhalten.
• Im kritischen Abschnitt dürfen sich beliebig viele Leser gleichzeitig aufhalten.
• Im kritischen Abschnitt dürfen sich niemals mehrere Schreiber gleichzeitig aufhalten

Eine Lösung dafür wäre mithilef eines Semaphors.

Eine Lösung bietet sich mit Hilfe eines Semaphors db an: Wenn ein Leser Zugriff auf die Datenbank bekommt, führt er ein down auf das Semaphor db aus. Wenn er fertig ist, führt er ein up aus. Solange mindestens ein aktiver Leser existiert, kann kein Schreiber in den kritischen Abschnitt eintreten. Ein Schreiber, der eintreten will, wird also solange stillgelegt, als es Leser im kritischen Abschnitt gibt. Falls jedoch fortlaufend neue Leser in den kritischen Bereich eintreten, kann es sein, dass ein Schreiber niemals Zugriff erhält. Er verhungert. Eine mögliche Lösung für dieses Problem besteht darin, dass ankommende Leser hinter bereits wartende Schreiber gestellt werden. Auf diese Weise braucht der Schreiber nur auf Leser zu warten, die vor ihm da waren, bis er zugreifen kann.

Grundfunktionen:

• send(dest, message)
• receive(src, message)
• beide Funktionen können blockieren

Bereich des physikalischen Speichers wird in den virtuellen Addressraum der Prozesse abgebildet.Shared Memory ist die schnellste Form der Interprozesskommunikation, da von 2 oder mehreren Prozessen ein bestimmter Speicherbereich gemeinsam benutzt wird, und somit das Kopieren zwischen Server und Clients nicht notwendig ist.

Shared Memory
• muss bei Betriebssystem angefordert werden
• keine implizite Synchronisation
- Synchronisation z.B. mit Semaphoren
• Zugriff sehr schnell: Speicherzugriff
• nur in Shared Memory Systemen verfügbar

Mittels Shared Memory können mehrere Prozesse auf einen gemeinsamen Datenspeicher zugreifen. Dies wird ermöglich, indem ein Prozess als Erstes ein gemeinsamen Datenspeicher anlegt. Dannach müssen Prozesse mit dem Datenspeicher bekannte gemacht werden um mit ihm kommunizieren zu können.

Dies geschiet indem der Speicherbereich im Adressraum der ensprechenden Prozesse eingefügt wird. Hier wird auch festgelegt wie sie auf ihn zugreifen können(lesen/schreiben).

TEST

test