Was ist ein Betriebssystem

  • Stellt Services Bereit (Häufig gebrauchte Subroutinen, Zugriff auf Hardware, Abstrakte Funktionalität)
  • Verbirgt die Komplexität des Rechners vor dem User / Entwickler
  • Schafft im Idealfall eine Umgebung die einfach und produktiv für Software und User ist

Eigenschaften eines Betriebssystemes

  • Benutzerfreundlichkeit (Robustheit, Widerspruchsfreiheit, Proportionalität, Komfort)
  • Infrastruktur (Ausreichend für den Verwendungszweck, Vollständig, Angemessen)
  • Kosten (Effizient, Gute Algorithmen, Niedriger Overhead)
  • Anpassungsfähigkeit (Hardwarefortschritte, Erweiterbar)

Historie

  • bis 1955 Kein OS
  • bis 1965 Stapelverwaltung (Lochkarten)
  • bis 1980 Rechnerfamilien mit gleichem Befehlssatz (IBM 360), Mehrprogrammnbetrieb, Terminals statt lochkarten und Drucker
  • 4. Generation bis heute - Mikroprozessoren, Vernetzung, HW Parallelität, Virtualisierung

Schutz vor Bösartiger Software durch Isolation

  • Preemption (Möglichkeit Ressource aktiv zurückzunehmen, wenn sie anderweitig gebraucht werden)
  • Zwischenschaltung: OS zwischen Anwendung und Ressource, Beobachtet Ressourcen, bei jedem Zugriff Rechte prüfen)
  • Priviligierte (Kernel Mode) & unpreviligierte (User Mode) CPU Modi

Arten von Kernels

  • Monolithische Kernels
  • Mikrokernels
  • Hybrid-Kernels

Monolithische Kernels

  • Gesamtes OS läuft im priviligierten Modus (kein Schutz zwischen Komponenten)
  • Erweiterbar
  • Kein Kontextwechsel innherhalb OS
  • Gute Perfomance
  • Univ, Linux, Windows 9x (1995-2000), Android

Mikrokernels

  • Kernel stellt nur Minimalfunktionalität bereit
  • Weitere Dienste auf ausgelagert (Usermode)
  • Gut geeignet für verteilte Systeme
  • Beispiel: Mach Unix von CMU
  • Einheitliche Schnittstellen für Dienste auf User/Kernel mode
  • Erweiterbarkeit durch neue Dienste
  • Nachteil: Viele Kontextwechsel
  • Kommunikation zwischen Komponenten = Overhead

Hybrid-Kernels

  • Mikrokernel Architektur führt aber manche Komponenten wie Monolithische Kernel aus (Ziel: bessere Performance und Sicherheit bzw Verwendbarkeit)
  • Beispiele: Windows NT, BeOS, NetWare

Übersicht Kernel

Arten von Betriebssystemen

  • PC-OS
  • Server OS: viele Benutzer gleichzeitig, Netwerkanbindung, Stabilität
  • Multiprozessor OS: Parallelrechner (heut genereller Fall)
  • Echtzeit OS: Scheduling erlaubt Zeitgarantien (Flugzeuge)
  • Anwendungsspezifische OS: Embedded Systems (Auto, ...), Spielekonsolen

Systemaufrufe

  • Systemaufrufe (System Calls) ermöglichen es, Anwendungen kernel-Funktionalität zu aktivieren (Kernel ruft passenden Handler auf)
  • Ziel: Aktionen durchführen, die im unprivilegierten Modus nicht möglich sind (wie library Aufruf)
  • Kernel bietet ein Systemaufrufs Interface an: Anwenduungen setzen Argumente und lösen Kernel Trap aus | Kernel führt Aktion aus und gibt Resultat zurück
  • Beispiele in POSIX/UNIX: open, close, read, write
  • Hochspracheninterfaces bauen oft auf diesen System calls auf: printf, scanf, gets, ...

Unix Dateisystemaufrufe

  • Anwendungen öffnen Dateien per Namen mit "open": I/O wird über Dateien durchgeführt
    int open(char* path, int flags, /*mode*/);
  • gibt file descriptor zurück
  • Gibt "-1" bei Fehler zurück (wird von den meisten SystemCalls verwendet)
  • perror()
    Funktion schreibt lesbare Fehlermeldung
  • "errno.h" hat makros für mögliche Rückgabewerte
  • Weiterere Dateisystemaufrufe: read, write, lseek, close

Systemkontexte

OS generell in einem von mehreren Kontexten

  • User-Level führt Anwendungen aus
  • Kernel Prozess (Kernel Code für bestimmten Prozess z.b. SystemCall)
  • Kernel Code ohne speziellen Prozess (Timer Interrupt, Device Interrupt)
  • In einem Kontextübergang (context Switch)
  • Idle (Es gibt nichts zu tun - CPU in low power State)

Konstextwechsel

  • Strategie für Kontextwechsel wird vom Scheduler bestimmt
  • Kontextwechsel selbst wird vom Dispatcher erledigt
  • Beispiele
    • User -> Kernel-Prozess: Syscall
    • User/Prozess -> Interrupt Handler: Hardware
    • Kernel-Prozess -> User/Kontextübergang: return
    • Kernel-Prozess -> Kontextübergang: sleep
    • Konteextübergang -> User/Kernel-Prozess: scheduling

CPU Preemption

  • Schutzmechanismus um zu verhindern, dass die CPU monopolisiert wird
  • Beispiel: Kernel programmiert HW timer die Ausführung alle 10ms zu unterbrechen (Interrupt): Dazu nötige I/O Register nur im Kernel Mode schreibbar. Wenn Interrupt auslöst weist der Kernel den CPU einem anderen Prozess zu
  • Resultat: Einzelnes Programm in Endlosschleife kann die CPU nicht monopolisieren: Schlimmstenfalls 1/N CPU mit N Prozessen

Umgehen von Schutzmechanismen

  • Wie könnte man immer noch die CPU monopolisieren? z.b. Mehrere Prozesse verwenden
  • Für viele Jahre:
    int main() {while(1) fork(); }
    Killt das gesamte System. Alternative Speicher belegen
    int main() { while(1) malloc(1); }
  • Häufig kombinierte soziale/technische Lösung (Technisch: Limitiert Zahl der Prozesse pro User, Sozial: System neu starten und lästige Benutzer maßregeln)

Was ist ein Prozess

  • Laufende Instanz eines Programms (benötigt Ressourcen: Prozessorzeiten, Speicher, Files, etc)
  • Betriesbsystem ist verantwortlich für: Erzeugen, terminieren, scheduling, Synchronisierung von Prozessen, Kommunikation zwischen Prozessen, behandlung von Deadlocks(Schleife in der Prozesse auf Input des jeweils anderen warten)

Warum Prozesse

  • Betriebssystem benötigt Abstraktion (CPU Scheduling, Zuweisung von Ressourcen)
  • Besserer Durchsatz (CPU Auslastung, Wartezeiten für den User)
  • Schutz zwischen Prozessen (Isolierung)
  • Nachteile: Ineffizient für gewisse Aufgabenstellungen, Aufwändiger Context Switch, IPC nicht flexibel

Durchsatz

  • Mehrere Prozesse verbessern CPU Auslastung
  • Wenn ein Prozess warten muss (Benutzerinteraktion oder Geräte), kann ein anderer die CPU nutzen

Wartezeit (Latenz)

  • Multi-Prozess-Betriebssystem kann Latenz verringern
  • Ausführung von erst A dann B -> 14s bis B fertig ist
  • A und B gleichzeitig -> z.b. 8s bis B fertig ist (Potenziell weniger als 14s gesamt)

Prozessperspektive auf das System

  • Jeder Prozess hat eine eigene Sicht des Systems (eigener Addressraum, Datei Handler, virtuelle CPU durch Preemption)
  • Anwendungsprogrammierung starkt vereinfacht
  • Interaktion zwischen Prozessen z.b. über Dateien

IPC

  • Interprozess Kommunikation
  • Nachrichten über Kernel (Message passing)
  • Gemeinsamer Zugriff auf den selben physikalischen Speicher (shared Memory)
  • Asynchrone Signale

Prozesse erzeugen

  • Fork kopiert den Prozess
  • Dannach simultane ausführung
  • Rückgabetypen: 0=Kind, -1=Error, sonst PID
  • In Unix Prozesshierarchie = Prozessgruppe (root/kernel startet init system welches daemons und die UI startet usw)
  • Windows kennt keine Prozess hierarchie (Alle gleichwertig)

Signale (Unix)

  • Ermöglichen Ausstausch von 1-Bit Informationen zwischen Prozessen (oder OS und Prozess)
  • Signale benachrichtigen einen Prozess über das Auftreten eines Ereignisses (Systemänderung, Zeit/Alarm, Fehler, I/O, Terminieren, ...)
  • Signale sind ähnlich wie SW-Interrupts
  • Vordefinierte Signale stehen zur verfügung
  • Abhängig vom Zustand des Prozesses und dem Signal: Prozess führt Signal Handler aus sonst wird eine default Aktion ausgeführt
  • Beispiele: SIGHUP, SIGINT, SIGKILL 9

Synchrone vs Asynchrone Signale

  • Synchrone (Synchron=Blockierend)
    • Entstehen bei der Abarbeitung des Instruction Streams
    • Verursachen einen TRAP im Kernel
    • An den Prozess (Thread) weitergeleitet, der den Trap verursacht hat
  • Asynchrone (Asynchron=Nicht Blockierend)
    • Quelle kommt von außerhalb des gerade exekutierenden Prozesses z.b. Profiling clock, terminal interrupt

Programme Ausführen

  • System Call execv führt Programm (prog) aus, das den aufrufenden Prozess in einen neuen Prozess umwandelt (Kein return - wird vom exit ersetzt - kein neuer Prozess sondern programm wird in image von bestehenden geladen)
  • Es gibt viele verschiedene Implementierungen/Wrapper von execv!!!
  • Komplexeres Interface als Fork dafür keine komplette Speicherkopie (= weniger Overhead)

Prozesszustände

  • Keine 2 Zustände gleichzeitig
  • Zu jedem Zeitpunkt kann immer nur 1 Prozess pro Prozessor ausgeführt werden
  • Typische Zustände (abhängig vom Betriebssystem): New, Ready, Running, Waiting, Terminated

Scheduling (Prozessorzuteilung)

  • Wie wird entschieden welcher Prozess ausgeführt wird?
  • Prozesstabelle nach erstem "ready" durchsuchen?
  • FIFO? Am Anfang einfügen, vom Ende nehmen
  • Prioritäten? Manche sind wichtiger als andere
  • Erfolgt bei folgenden Zustandsübergängen (von Running in Waiting (I/O): non-preemptive-scheduling, von Running in Ready (Interrupt): Preemptive-scheduling, von Waiting in Ready: Preemptive-scheduling, von Ready in Terminated: non-preeemptive-scheduling)

Scheduling Policy

  • Bestimmt Ausführungsreihenfolge (Optimierung) von Prozessen durch Scheduler
  • Viele Ziele für Optimales Scheduling: Fairness (kein verhungern), Prioritäten (wichtigkeit), Deadlines, Durchsatz (system sollte gut ausgenutzt werden), Verarbeitungszeit, Effizienz (min overhead durch scheduling)
  • Konflikte, kein gesamt "bester" Scheduler

Verwaltung von Prozessen

  • OS Speichert Datenstruktur "Process Control Block PCB" für jeden Prozess (Zustand, Register, Speicher, Rechte, Signalmaske, Priorität, ...)
  • PCB's werden in einer Tabelle gespeichert
  • Prozesse werden häufig in Warteschlangen basieren auf Prozesszustand abgespeichert

Erzeugen von neuen Prozessen im Betriebssystem

  • Erzeuge PCB für neuen Prozess (kopiere Einträge von Elternprozess, Initialisiere Abrechnungsinformationen, generiere eindeutige PID / Processidentifier)
  • Speicherzuteilung (Evtl vom Elternprozess übernehmen)
  • Einfügen in Ready Warteschlange

Beenden eines Prozesses im OS

  • Normales Ende (letzte Instruktion des Prozesses wird ausgeführt)
  • Kernel kann terminieren (Ressourcenlimits, illegale Operationen)
  • OS Aktionen beim Beenden: Signal an Elternprozess, Speicher Ressourcen freigeben, PCB in der "Terminated" queue speichern

Context-Switch

  • Prozessorwechsel von einem Prozess zum anderen nenn man Context-Switching - Sichern des Zustandes des aktuellen Prozesses, Laden des Zustandes eines neuen
  • Context Switch kann nur durchgeführt werden, wenn der Kernel den Prozessor hat (Trap (preemptive), Interrupt (preemptive), durch Benutzerprozess z.b. yield - suspend - I/O (non-preemptive))
  • Zeit für Context-Switching ist kritisch!

Preemption

  • Prozess wird ohne sein zutun (preemptive) unterbrochen und der Kernel erlangt Kontrolle über die CPU: Interrupt, I/O, Fehler
  • Nicht preemptive (cooperate): System Call, Sleep, explizites Starten eines anderen Prozesses

Context-Switch Details

  • Sehr Hardwareabhängig
    • Programmcoutner und Registerinhalt abspeichern (immer)
    • Spezialregister abspeichern (z.b. SIMD)
    • Zusätzliche PCB Werte speichern (z.b. Signalmasken)
    • Virtuell Adresstabellen ändern
  • Relative hohe Kosten! Ansätze:
    • Spezialregister nur speichern wenn verwendet
    • Nur Werte uas dem TLB (Hardware zur Addressübersetzung) löschen, die zu dem Prozess gehöhren

Beispiel: Aktionen bei Interrupt

  • HW legt Programmcounter auf den Stack
  • HW lädt neuen Programmcounter aus dem Interruptvektor
  • Assemblercode im OS speichert Registerinhalt
  • Assemblercode im OS erzeugt neuen Stack
  • C Interruptservice wird ausgeführt
  • Scheduler entscheidet welcher Prozess als nächstes ausgeführt wird
  • C Prozedur kehr tzu Assembler zurück
  • Assemblercode im OS startet neuen Prozess

Threads

  • Leichtgewichtprozess, der aus folgenden Komponenten besteht: Programmzähler, Register-Set, Stack, Zustand
  • hat Zugriff auf Speicher und Ressourcen seines Prozesses
  • Kan Priorität haben
  • Threads teilen sich innerhalb eines Prozesses Speicher, Code, Files, Signale
  • Beispiel: Webserver
  • Vorteile: Schnelles Context Switching, Einfacher Datenaustausch
  • Zustände: Spawn, Block, Unblock, Running, Finish

Threads vs Prozesse

Kernel Threads

  • Alle Threads eines Prozessses sind für den Kernel sichtbar und werden von ihm verwaltet
  • Vorteile: Wenn Thread OS Blockiert kann ein anderer weiter arbeiten, Parallelismus kann ausgenutzt werden, Solide implementierung im OS
  • Nachteile: Thread Operationen müssen über Kernel erfolgen, Generische Implementierungen im OS für alle Anforderungen von Anwendung, Höherer Speicheraufwand

User Threads

  • Threads in einer Library implementiert, Kernel sieht nur einen "kernel-level" thread
  • Vorteile: Applikationsspezifische Anpassungen möglich, Portabilität der Libraries über mehrere OS, Reduzierung des Overheads von Thread Operationen (Kein User/Kernel mode switch)
  • Nachteile: Keine Nutzung des HW Parallelismus, Blockierende Systemaufrufe blocken Prozess, Erhöhte Deadlock Chance

Hybrid Threads

  • User Threads auf mehreren Kernel Threads pro Prozess
  • Vorteile: Schneller User-Thread Wechsel innerhalb eines einzelnen Kernel Threads, Möglichkeit HW Parallelismus auszunutzen, Falls ein Kernel Thread blockiert ist nicht gesamter Prozess blockiert
  • Nachteile: Hoher Grad an implemtierungskomplexität, Teilweise ähnliche Probleme wie User threads, Konkurrierende Scheduler auf Anwendungs und Bebtriebssystemebene )Kernel kennt HW Situation besser, Programm kennt Programmeigenschaften)

Scheduling Kriterien

  • Durchsatz (throughput) Anzahl an fertigen Jobs / Zeit (Höher = Besser)
  • Laufzeit (Turnaround time) Zeit für jeden Job (Ready bisTerminated) (Niedriger = Besser)
  • Antwortzeit (Response time): Zeit von der Anfrage bis zur erster Antwort (Tastendruck)
  • Allgemeine Ziele: Maximiere Prozessorauslastung, Durchsatz (Systemorintiert) bzw Minimiere Antwortzeit (Benutzerorientiert), Wartezeit, Laufzeit
  • Weitere Kritieren: Prozessorauslastung, Wartezeit, Scheduler Overhead, ökonomische Kosten, Energieverbrauch

Prozessor und andere Geräte

  • Prozessor ist nur ein Gerät, welches von Jobs benötigt wird
  • Prozessor führt berechnende Jobs aus, Festplatte speichernde Jobs, ...
  • Im Netzwerk könnnen auch Jobs ausgelagert werden
  • Effizientes Scheduling kann den Durchsatz nahezu verdoppeln!

First-come First-served (FCFS)

  • Jobs werden in der Reihenfolge ausgeführt, in der sie eintreffen (FIFO Warteschlangen)
  • Performance

Nächste Seite!

Nächste Seite!

Shortest Job First (SJF)

  • Versucht Laufzeit zu minimieren
  • Ziel: Job wählen dessen nächster Prozessorschub der kürzeste ist wenn gleich dann FCFS
  • Sollte shortest next CPU burst genannt werden weil es sich nicht auf die Gesamtlaufzeit von Jobs bezieht
  • 2 Varianten: Non-preemptive: Sobald ein Prozess gewählt ist, kann dieser nicht unterbrochen werden bis sein Prozessorschub vorbei ist | Preemtive: Wenn ein neuer Prozess verfügbar wird, dessen Schublänge weniger als die verlbiebende ist, wird dieser unterbrochen (Shortest Remaining Time First SRTF)

Nächste Seite!

Nächste Seite!

Nächste Seite

Optimierungen SJF/SRTF

  • Resultiert in der beweisbar, minimalen durchschnittlichen wartezeit
  • Vorausgesetzt: alle Jobs und deren Laufzeiten sind bekannt und liegen zu einem bestimmten Zeitpunkt vor.
  • Reduktion der Wartezeit verringert häufig die Laufzeit
  • Minimiere durschnittliche Laufzeit für Jobs mit variierender Laufzeit (kurze sollen nicht durch lange verzögert werden)

SJF Nachteile

  • Minimiert nicht immer Laufzeit (nur warte und antwortzeit)
  • Kann zu unfairer Verteilung bzw verhungern von langen jobs führen
  • Praktisch können Prozessorschübe nur schwer vorausgesagt werden (Vorhersage basiert auf Historischen Messwerten)

Round Robin

  • Wähle Jobs zyklisch aus Ready Warteschlange auf Basis des Round-Robin Prinzips
  • Löst Probleme der Fairness und des Verhungerns von Prozessen (Jobs werden nach fixen Zeitintervall unterbrochen)
  • Vorteile: Fairness, Gut wenn wenig Jobs
  • Nachteile: Kurzes Zeitinterval vervielfacht Kontextwechsel (CPU!), Bei Großen Jobs ebenso viele Kontextwechsel

Nächste Seite!

Nächste Seite!

Nächste Seite

Context Switch Aufwand

  • Reine Zeitkosten im Kernel (Speichern & Laden von Registern, Addressraumwechsel, ...)
  • Indirekte Kosten (Cache, TLB Misses)

Zeitintervall / Quantum

  • Bei wahl Zeiterverlust durch Context Switches miteinbeziehen
  • Großteil z.b. 80% der Prozessorschübe sollte kürzer als ein Quantum sein
  • Nicht so groß, dass Resultat äquivalent zu FCFS ist
  • Nicht zu klein - Durchsatz verschlechtert sich!
  • Typisch: 10-100ms

Zwei-Stufen Scheduling

  • Wechsel zu Prozessen, die auf die Festplatte ausgelagert sind, ist sehr zeitintensiv
  • Zwei-Stufen Scheduling berücksichtigt diesen Umstand
  • Wahl des Subsets und Definition für eine Weile

Prioritäten Scheduling

  • Numerische Priorität
  • Probleme: Verhungern von Prozessen mit schlechter Priorität (Lösung: Prio steigt mit wartezeit)
  • Priorität basierend auf (Kosten für User, Bedeutung des Jobs, Alter, Prozessoranteil in der letzten Zeit

Nächste Seite!

Nächste Seite!

Preemtion bedeutet, dass der Scheduler den Prozess wechselt sobald ein neuer mit höherer Priorität daherkommt. In diesem Fall kein Unterschied.

Lotterie-Scheduling

  • Verteilt CPU Lose an Jobs und zieht dann ein Ticket, das festlegt welcher Job die CPU erhält
  • Nachteile: Schwer vorhersehbare Antwortzeiten (Binomialverteilung von warscheinlichkeiten wirklich fair?)

Nächste Seite!

Nächste Seite!

Echtzeit-Scheduling

  • Zwei Kategorien: Soft real time (Falls die Deadlinen icht erriecht wird, klingt die Musik kurz komisch), Hard real time (falls nicht erreicht, stürzt flugzeug ab)
  • System muss periodische und aperiodische Events behandeln
  • Spezielle Scheduling Strategien (z.b. First Daedline First)

Multiprozessor Scheduling

  • Welcher Prozess auf welchem Prozessor
  • Bewegung zwischen Prozessoren bewirkt MehrKosten
  • Kommunizierende Prozesse/Threads auf demselben Prozessor

IPC: Probleme mit Kommunikation über Dateien

  • Umständlich
  • Langsam
  • Gemeinsame Benutzung muss koordiniert werden
  • Mögliche Lösungen: Sperrdateien, Record-Locking
  • Beste Lösung: IPC

IPC Übersicht

  • Pipes (Unnamed)
  • Named Pipes (FIFOs)
  • XSI IPC
  • Nachrichtenwarteschlangen
  • Gemeinsamer Speicher (Shared-Memory)
  • Semaphore

Pipes (Unnamed)

  • Waren die 1. Form der IPC
  • Werden heute von allen UNIX-Systemen angeboten
  • 2 wichtige Eigenschaften: Nur zwischen Prozessen die gemeinsame Vorfahren haben, halbduplex (Daten können immer nur in eine Richtugn fließen)
  • Der Befehl "pipe" richtet Pipe im Kern ein. Anschließend via "fork" oder "exec" Kindprozess erzeugen und schon kann mit der Pipe gearbeitet werden

Named Pipes (FIFOs)

  • Im Gegensatz zu unnamed Pipes können FIFOs zwischen beliebigen Prozessen verwendet werden
  • Wird wie Datei behandelt
  • Daten können nur 1x gelesen werden (daher wie FIFO Queue)
  • Unterstützt mehrere Schreibprozesse
  • Bsp Clients schreiben, Server liest

XSI IPC

  • Definiert drei Methoden: Message-Queues, synchronisiert durch Semaphore, Shared-Memory
  • Kommunikation zwischen nicht Verwandten Prozessen möglich
  • Keine File-Deskriptoren werden verwendet
  • Kennung (Identifier): ID für Kern
  • Schlüssel (Key): wird vom Kern mit Kennung verbunden, ID für gemeinsame verwendung des Objektes

Message Queues (Nachrichtenwarteschlangen)

  • Werden im Kern in Form einer verketteten Liste verwaltet
  • Standardmäßig nach dem FIFO-Prinzip
  • Prioritäten möglich
  • Zwei oder mehrere Prozese tauschen Informationen über eine Message Queue aus. Der Sender gibt mit Hilfe eines System-Calls eine Nachricht in die Queue und der Empfänger holt diese aktiv
  • Zu jeder Queue exisitert eine msquid_ds Struktur die den aktuellen Status festlegt (Maximale Bytes/Msg, Nachrichten im System, ...)

Shared Memory (Gemeinsamer Speicher)

  • Vorteil: Schnellster IPC-Mechanismus
  • Nachteil: Der Zugriff muss extern synchronisiert werden z.b. durch Semaphore
  • Bei Fork erbt der Kindprozess alle Shahred, Memory segmente, bei exec nicht!
  • Shared Memory Segmente werden erst gelöscht, wenn der letzte Prozess, der diese verwendet terminiert

Semaphore

  • Synchronosierung des Zugriffs auf Ressourcen
  • Geschützte Variable, die von einer Menge von Prozessen gelesen oder geschrieben werden kann
  • Steps: Überprüfen des Semaphors (Wert > 0 = kann benützt werden, Wert = 0 wird benützt daher warten), Inkrementieren um 1 wenn Zugriff beendet wurde
  • Überprüfen und Dekrementieren müssen Atomare Operationen sein und sind daher für gewöhnlich im Kern implementiert
  • Das Erstellen ist unabhängig vom Initialisieren (Kann Vorteil oder Nachteil sein)
  • Muss immer explizit freigegeben (gelöscht) werden

Arten von Semaphoren

  • Hängt vom Unix-System ab
  • Namenlose Semaphore (analog zu Pipes): Einfache Synchronisierung von Threads oder Vater/Kind Prozessen
  • Benannte Semaphore (analog zu FIFOs): Zur synchronisierung von Prozessen ohne gemeinsamen Speicher

Posix-Threads

  • Gemeinsame Ressourcen: Addressraum, File Descriptoren, Signal Handler, Benutzer und Grupppen Kennung, Arbeitsverzeichnis
  • Eigene Elemente: Thread Kennung, Kopie der Prozessorregister, Stack, Signalmaske, Priorität, Errno
  • Posix Standard definiert einheitliche API unabhängig von der Implementierung (Kann Kernel oder Benutzer thread sein)
  • Erhältlich auf Unix-Systemen wie Linux oder Solaris aber auch auf Windows

Thread-Safe

  • Wenn eine Komponente gleichzeitig von mehreren Programmbereichen benützt werden kann, phne dass diese sich gegenseitig behindern

Mutex

  • Nur notwendige Teile schützen da Mutexe Zeit kosten
  • Verschiedene Codeteile durch einzelne Mutexe schützten (evtl vorher größere, ...)
  • Statisch: Endet der var scope, so auch der Mutex
  • Dynamisch: Mutex bleibt bestehen - für dynamisch allozierten Speicher

Deadlocks und Backoff-Algorithmus

  • Deadlocks (Zugriffs Zyklus) könenn bei gegenseiten Abhängigkeiten auftreten
  • Einfache Möglichkeit der Vermeidung: Backoff Algorithmus
    • Erster mutex wird gesperrt
    • Alle nachfolgenden werden versucht zu entsperren
    • Ist einer Gesperrt, dann werden rücckwärtes alle gesperrten wieder freigegeben

Bedingungsvariablen (Condition)

  • Bei Mutexen warten | mit Bedinungsvariablen kann man informiert werden, wenn sich der Status ändert
  • Statisch: Thread muss mutex gesperrt haben, gibt frei und wartet bis bedinung erfüllt, sperre anschließend autom. eingerichtet
  • Dynamisch:

Spin Locks

  • Wie mutex nur dass anstatt den Prozess durch schlafen (warten auf event / interrupt) zu blocken, dieser durch busy-waiting(aktives warten) bzw spinning geblock wird. Das bedeutet keinen Kontextwechsel, dafür mehr wartezeit
  • Nützlich bei kurzen zeiten bzw wenn Kontext wechsel verhindert werden soll (dafür kann cpu nichts anderes machen in der zeit).

Barriers

  • Koordination für eine Reihe von Threads
  • Threads warten, bis alle anderen an jenem Punkt angekommen sind (z.b. pthread_join)

Race Conditions

Wenn mehrer worker daten lesen, verarbeiten und schreiben kann es passieren, das 1 worker ein ergebnis schreibt, obwohl ein anderer seines noch nicht verarbeitet hat. Letzterer Worker wird dann das Ergebnis vom vorherigen überschreiben

Lösung: Wechselseitiger Ausschluss (Mutual Exclusion) - Nur ein Prozess kann Ressource verwenden oder Atomarer Zugiff (garantiert in einem Prozessor Zyklus ausgeführt)

Kritische Region

  • Programmregion in der gemeinsame Daten geändert oder verwendet werden
  • Jeder Prozess hat eine Code-Region (kritische Region) in der auf jene Daten zugegriffen wird
  • Problem: es darf zu jedem Zeitpunkt nur 1 Prozess in der kritischen Region sein
  • Prozess kan in der kritischen Region unterbrochen werden (Interrupt, Contex Switching, ...)

Realisierung von kritischen Regionen

  • Software: Lösung muss für alle Szenarien funktionieren. Lösungen: Busy Waiting (Warten auf das Eintreten einer Bedinung durch perm. testen / pollen benötigt viel Prozessorzeit), Dekker Algorithmus
  • Hardware: spezielle atomare Meschineninstruktionen
  • Betriebssystem: Stellt spezielle Funktionen und Datenstrukturen zur verfügung z.b. Semaphore, Monitore, ...

Dekker Algorithmus

  • für 2 Prozesse
  • Verwende gemeinsame Variable turn (0 oder 1)
  • Prozess i kann kritische Region betreten, wenn turn = i
  • wenn 1 Prozess ausfällt, ist der andere dauerhaft blockiert
  • Probleme: Name wird gespeicchert

Decker Algorithmus 2

  • ähnlich wie nr 1
  • Verwende Prozess array um festzulegen, welcher Prozess die kritische Region betreten darf
  • Es gibt auch noch 3 version die die 1. und 2. kombiniert

Bakery Algorithmus

  • Wie ticket System
  • Aktuelles Ticket / Nr wird immer um 1 erhöht
  • Prozess mit niedrigster nummer darf als nächstes in die Kritische Region
  • Für mehr als 2 Prozesse möglich
  • First Come First Serve

HW Lösung für Kritische Regionen (Interrupt Disabling)

  • Wird von Einprozessorsystmen verwendet
  • Mehrere Prozesse verwenden die CPU im Time-Sharing-Modus
  • Prozess behält die CPU solange bis ein Systemaufruf getätigt wird oder ein Innterrupt erfolgt
  • Durch verhindern von Interrupts können kritische Regionen realisiert werden (Möglichkeiten im OS)
  • Nachteile: Verlust von Performance, funktioniert nicht für alle Multiprozessor-systeme

HW Lösung für Kritische Regionen (Test and set)

  • Hardwarebefehl der 2 Aktionen (Lesen und Schreiben/Prüfen) auf einer einzelnen Speicherstelle atomar mit nur 1. Befehlszyklus ausführt
  • Mehrprozessorfähige HW Lösung
  • Alle anderen im Busy-Waiting Modus
  • Vorteil: Beliebige Anzal an Prozessen auf beliebig vielen Prozessoren, einfach, mehrere Kritische Regionen möglich
  • Nachteil: Starvation von Prozessen ist möglich, ebenso deadlock

Leser/Schreib Problem

  • Prozesse tielen sich daten
  • Einige Lese, 1er schreibt
  • Schreiber hat Priorität (keiner kann lesen wenn schreiber schreibt)

Monitor

  • Konstrukt bestehend aus Variablen die den Zustand des Monitors spezifizieren, Prozeduren die jene Variablen abfragen oder verändern können
  • Wrapper von Synchronisationsprimitiven wie z.b. Semaphoren
  • Klasse/Modul von ausen für Entwickler einfach zu verwendetn ohne Gedanken über synchron. machen zu müssen / Logik wird in der Klasse selbst behandelt

Dining Philosophers Problem

  • 5 Philisophen denken und essen
  • Jeder braucht 2 Esstäbe es gibt aber nur 5
  • Jeder kann nur einen Esstab zu einem bestimmten Zeitpunkt aufheben
  • Gesucht: Lösung ohne Deadlock (verklemmung weil esstäbe zwischen den Personen liegen - wer nimmt wen? bzw verhungern)
  • Mögliche Lösung: Jeder Philisoph = Prozess, Esstab = Semaphore | Jeder Philisoph darf Esstab nur aufnehmen (Kritische Region) wenn beide verfügbar sind | Assymaterische Lösung: Abh. vond er ID nehmen sie versetzt zuerst das Linke und dann das Rechte Stäbchen | Zusatz var für max. 2 phil gleichzeitig aufnehmen?

Bedingungen für Deadlocks

  • Wechselseitiger Ausschluss: Ressource verfügbar oder Proc zugeordnet
  • Hold and Wait: Procs die schon Ressourcen reserviert haben, können weitere anfordern
  • Kein unfreiwilliges Abgeben von Ressourcen: Nur Ressourcen abgeben, wenn diese nicht benötigt werden
  • Circular wait: Philisophers Problem?

Behandlung von Deadlocks

  • Ignoriere Deadlocks - Rebooten
  • Verhindere eine der 4 Bedingungen
  • Avoidance: Ressourcenreservierungen die dazu führen können vermeiden
  • Erkennung & Recovery: Ressourcenanforderungen gewährt sofern vorhanden. Periodisches Prüfen ob vorliegt ggf Recovery / Ressourcen zurücknehmen / reset

Banker Algorithmus: Deadlock Avoidance

  • Bestimmt ob system in einem Sicheren Zustand ist
  • Bedingungen: Maximale Ressourcen Instanzen pro Prozess
  • Wird selten verwendet da variablen selten bekannt
  • Überprüft ob vorhandene Ressourcen für nicht terminierte Prozesse reichen. Nimmt dabei vorerst an, dass ein deadlock statt findet, arbeitet alle prozesse ab und wenn alle ihre ressourcen haben wird die variable auf false gesetzt. Sollte true zurückgegbeen werden, so kann ein rollback/reset durchgeführt werden oder es kann schon in der schleife nachfolgende prozesse blockieren und warten bis ressourcen frei sind

Load-time Linking (Virtueller Speicher)

  • Wenn das Programm geladen wird, so wird auch der Speicher festgelegt
  • Probleme: fehlender Schutz, kein bewegen der Programme möglich

Base & Bound Register (Virtueller Speicher)

  • Zwei spezielle HW Register: Base und Bound (Zugriff nur im privilegierten Modus / Kernel Mode)
  • Bei jedem Speicherzugriff: 1. Physische Adresse = Virtuelle Addresse + Base | 2. Überprüfe 0 $\leq$ Virtuelle Addr. $\le$ Bound, falls nicht -> kernel trap
  • Wie bewegen: OS muss Base register anpassen
  • Context Switch: Base und Baund des aktuellen Prozesses sichern und vom neuen laden
  • Vorteile: Einfach, effizient, in hw implementieren
  • Nachteile: Speichergröße erhöhen schwierig, daten teilen nicht möglich

Segmentierung (Virtueller Speicher)

  • Prozess hat mehrere Base & Bound Register
  • Teilen ist auf Basis der Segmentgranularität möglich
  • Segment muss als Teil der virtuellen Adresse angegeben werden
  • Vorteile: Erlaubt gemeinsame Verwendung von Segmenten zwischen Prozessen. Prozess kann partiell ausgelagert werden
  • Nachteile: Benötigt ÜBersetzungshardware | Segmente nicht transparent für Anwendungsprogrammierer | Fragmentierung durch Freibereiche = ernstes Problem

Fragmentierung

Verhindert das Nutzen freien Speichers durch "Löcher"

Alternativen zur Hardware MMU (Hardware Memory Management)

  • Schutz azf Sprachebene z.b. Java (Nur einzelner Addressraum für mehrere Module, Programmiersprache sichert Isolation)
  • Software Fehlerschutz: Compiler instrumentiert Ausgabeprogramm und überprüft bei jeder Schreiboperation auf korrektheit z.b. Google Native Client Projekt

PAging - Idee & Hardware

  • Unterteile Speicher in viele kleine Pages (Seiten)
  • Virtuellen Seiten auf physische Frames übers.
  • Strikte Trennung zwischen Logischen Adressen und psyikalischen
  • Bei jedem Speicherzugriff wird logische auf physikalische Abgebildet
  • Erlaubt OS kontrolle über Operation
  • HW setzt accessed und dirty bits
  • Kontrolle über Caching von Pages sowie Ausführbarkeit zusätzlich von Read/Write
  • Vortiele: Externe Fragmentierung elliminieren, Speicherschutz, Memory Sharing
  • Nachteil: Interne Fragmentierung hoch

Unix System Structure

Paging Datenstrukturen

  • Pages haben fixe Größe z.b. 4KB, niedrige 12 bits der Adresse sind PAge Offset, Hohe bits sind Page Number
  • Jeder Prozess hat eien PAge Table - Mapped Virtual Page Numbers (VPN) auf physische(PPN), Enthält auch bits für Zugriffsrechte (vgl Segmente)
  • Bei Speicherzugriff: Übersetze VPN auf PPN, Überprüfe Rechte, Addiere Offset
  • Beschleunigung: Translation Lookaside Buffer TLB -> Cache welcher von virtueleln auf physikalischen Speicher übersetzt

Paging Seitengrößen Vor- und Nachteile

  • Betriebssystem verwaltet physikalischen Speicher
  • Normalerweise hat jeder Prozess seine eigene Seitentabelle: 1 Eintrag pro Seite, die Prozess verwendet
  • Seitengrößen mit Vir- und Nachteieln: Prozesse benötigen nicht immer das Vielfache einer Seite als Speicher. Je kleiner die Seiten, deso größer die Seitentabellen

Thrashing

  • Virtueller Speicher kann zu hohen Speicherzugriffskosten führen. Trashing: Wenn Prozess nicht genügend Frames hat, kann das Syystem die gesamte Zeit dazu verwenden, Seiten von der Platte in den Hauptspeicher zu laden und umgekehrt
  • Swapping: Schreibe Speicher auf Platte und vermeide weitere Ausführung (da platte=langsam)
  • Woher weis man, ob Thrashing statt findet? Überprüfe Auslastung des Prozessors und das auslagern von Seiten (Paging). Geringe Auslastung des Prozessors + hohe Paging Rate beduetet Trashing

Resident Set

  • Seiten eines Prozesses, die sich im Hauptspeicher befinden. Wie viele Frames sollen dem Prozess zugeteilt werden?
  • wenige Frames -> viele Seitenfehler
  • viele Frames -> reduzierte Anzahl der Prozesse im Hauptspeicher (Einschränkung der Parallelität)
  • statische Zuteilung
  • dynamische Zuteilung

Working Set

  • Programme haben in der Regel Lokalität von Referenzen: temporär (Wiederholter Zugriff auf diesselbe Speicherposition), räumlich (Zugriffe auf Speicherposition, die nahe beieinander liegen)
  • Working Set: Menge von Seiten definiert durch die letzten N Seitenreferenzen
  • Strategie: Variable Allokation von Seiten für einen Prozess basierend auf Lokalitätsannahme

Modell: Page Fault

Ein Seitenfehler tritt bei Betriebssystemen mit Virtueller Speicherverwaltung und Paging auf, wenn ein Programm auf einen Speicherbereich zugreift, der sich gerade nicht im Hauptspeicher befindet, sondern beispielsweise auf die Festplatte ausgelagert wurde oder wenn zu der betreffenden Adresse gerade kein Beschreibungseintrag in der MMU verfügbar ist.

Weitere Herausforderungen

  • Wie Prozess nach Page fault weiter ausführen? (Zustand muss gespeichert und geladen werden, auch mitten in einer Instruktion)
  • Was von der Festplatte Laden (nuur 1 Page oder mehr?)
  • Was aus dem Hauptspeicher entfernen (Welche PAges von welchem Prozess sind wichtig?)

Algorithmus für das Ersetzen von Seiten: Optimale Strategie (OPT)

  • ersetzt die Seite, deren nächste Referenz am weitesten in der Zukunft liegt
  • erzeugt die wenigsten Seitenfehler
  • Keine reale Strategie
  • Wird zur Bewertung anderer Strategien herangezogen
  • Beispiel auf nächster Seite!

Algorithmus für das Ersetzen von Seiten: FIFO

  • Ersetze die älteste Seite im Hauptspeicher
  • Auf alte Seiten kann häufig zugegriffen werden! Anzahl der Seitenfehler kann ansteigen, wenn die Anzahl der Frames erhöhrt wird!
  • Beispiel auf nächster Seite!

Algorithmus für das Ersetzen von Seiten: LRU (last-recently-used)

  • Ersetze die Seite, die am längsten nicht verwendet worden ist
  • Annahme: Seite wird auch in der Zukunft nicht referenziert (Lokalitätsorenzip)
  • Anzahl der Seitenfehler kaum höher als bei OPT
  • Implementierung kann teuer sein (erwalte Stack, Seite kommt auf Top-of Stack, Jede Seite bekommt Zeit stempel)
  • Beispiel auf nächster Seite!

Algorithmus für das Ersetzen von Seiten: Clock Policy

  • FIFO Variante
  • Ringpuffer mit Frames, die für Austausch in Frage kommen + Positionszeiger
  • nach Seitenfehler: Zeiger wird auf den Folgenden frame im Ringpuffer gesetzt
  • Use Bit pro Frame wird auf 1 gesetzt wenn Seite geladen oder referenziert wird
  • Bei Seitenfehler: Suche erste Seite ab Zeigerpos mit Use Bit = 0
  • Second Chance: eine Seite bekommt eine 2. Chance
  • Beispiel auf nächster Seite!

Best fit Allocator

  • Strategie: Minimiere Fragmentierung durch Allokation von dem freien block, der kleinstes Restfragment erzeugt

Slab Allocator

  • Beobachtung: Viele Objekte selber Größe alloziert
  • Häufig zusammenhängender Speicher erwünscht
  • Slab Allocator optimiert für diesen Anwendungsfall
  • Objekte desselben Typs werden zu Slabs zusammengefasst

Garbage Collection: Stop and Copy

  • Speicher wird in 2 Bereiche zerlegt: Old Space: für laufende Allokation Operationen und New Space für GC Reserviert
  • Heap Pointer zeigt auf nächstes freues Wort im Old Space und wird immer erhöht
  • GC startet wenn old space voll. Das Programm wird unterbrochen
  • Kopiert alle erreichbaren objekte vom old space in den new space (garbage wird nicht mit kopiert)
  • Dann werden rollen von old und new space vertauscht
  • Vortiele: Sehr schnell, effizient
  • NAachteile: Sprachen wie C, C++ erlauben kein kopieren als Teil von Stop and Copy (inahlt von speicher nicht identifizierbar)

Garbage Collection: Reference Counting

  • JEdes Objekt hat Referenz Count von Pointern die darauf zeigen
  • Funktioniert gut für hierarchische und lineare Datenstrukturen z.b. Pages im pysischen Speicher
  • Kann manuell für jede Programmiersprache implementiert werden (aber fehleranfällig)
  • Zyklische Datenstrukturen haben immer Ref Count > 0 (Gegenseite abhängigkeiten obwohl nicht verwendet vom eigentlichen Programm!)
  • KAnn effizienter sein als "echte" GC oder auch nicht (IMPLEMENTIERUNG!)

I/O Devices

  • Block devices: hdd, tapes
  • Character Devices: Printers, scanners, NIC, mice
  • Others: Touch screen, clocks

Memory-mapped I/O

  • Map all the control registers into the memory space
  • Each control register is assignd a unique memory address
  • Near the top of the address space
  • Advantages: Can be written in C, No special protetction needed, every instruction can also reference control registers
  • Disadvantages: Cannot cache a device control register, In a single-bus architecture both I/O and memory have to look for each address

Magnetic Disks

  • organized via cylinders
  • Each cylinder contains as many tracks as tehre are heads stacked vertically
  • The trackks are divided into sectors
  • heads varies from 1 to 16

Data Scheduling: FCFS

  • First Come First Serve
  • Advantages: Easy to implement, Fair
  • Disadvantages: Does not use locality of multiple requests (caching) | Increase average latency & reduces throughput

Bsp auf nächster Seite!

Data Scheduling: Shortest Positioning Time First (SPTF)

  • Choose request with the shortest Seek time
  • Advantages: Uses locality, higher thoughput
  • Disadvantages: Starving, unfair, minimal response time is difficult to achieve, not allways clear which request is the fastest

Bsp auf nächster Seite!

Data Scheduling: Aged SPTF

  • Größtes Problem mit SPTF: Verhungern
  • Verbesserung Aged SPTF: Ältere Prozesse bekommen höhere Priorität
  • $T_{eff} = T_{pos} - W * T_{wait}$

Data Scheduling: SCAN Scheduling

  • Moving in one direction over the hard disk, while editing all the requests that are happening - like SPTF but only in one direction (only if there are no further requests)
  • Advantages: Uses locality, limited waiting times
  • Disadvantages: Cylinders in the middle are preferred
  • Locality could be less well exploited than SPTF

Data Scheduling: CSCAN

  • SCAN immer nur in eine richtung (Elevator) und dann reset.

Bsp auf nächster Seite!

Data Scheduling: VSCAN

  • Mischung zwischen STPF und scan
  • Wie gewichtete effektive Seek Zeit mit Richtung
  • Mischt vor und Nachteile von SPTF und SCAN
  • $T_{eff} = T_{pos} + r*T_{m}$

Stack, Heap, Globale Daten/Code

  • Heap: Während Runtime erzeugt von malloc. Compiler und Linker nicht involviert (ausser Startadresse). Namen werden vom Programm verwaltet (Pointer)
  • Stack: Alloziert zur Runtime Layout durch Compiler Namen entsprechen relativen Offsets zum Stackpointer. Vom Compiler verwaltet, Linker nicht involviert.
  • Globale Daten/Code: Allokation = Compiler, Layout = Linker. Compiler erzeugt syymbolische Referenzen. Linker erzeugt Layouut und übersetzt Refrenzen.

Linker

  • Teile des Programms sammeln, gleichartige Segmente verschmelzen, Adressen von Code und Daten anpassen
  • Warum nicht im Compiler? Für Sprachen wie C/C++ sieht der Compiler nicht das ganze Programm, sondern immer nur eine Datei
  • Optimierung im Linker: Im Normalfall ändern Linker nicht die Reihenfolge von Segmenten oder innerhalb von Segmenten

Einfacher Linker: 2 Passes

  • Pass1: Gleichartige Segmente verschmelzen & in nicht-überlappenden Speicher arrangieren. Symboltabellen der Dateien auslesen, globale Symboltabelle mit Eintrag für jedes verwendete oder definierte Symbol anlegen. Virtuelle Adresse jedes Segments berechnetn
  • Pass2: Alle Refrenzen mit Hilfe der neuen Symboltabelle updated und resultat ausgeben
  • Symboltabelle hält mehr Informationen über Programm: Segmente Namen, Größe, alter Position, neue Position. Symbole: Name, Eingabesegment, Offset im Segment

Linking und Sicherheit

  • Buffer Overflow: Angreifer positioniert Code im Datensegment
  • Versuche, im Linker dagegen zu Arbeiten: W^X Kein Speicher ist sowohl beschreib als auch ausführbar, Zufällige Adressvergabe

Kommunikationssysteme

Low-Level Kommunikationssysteme

  • Classic: Nic in the OS Address Space: Sending/Receiving via sys call, ost must copy betwenn user and os address space
  • Modern multicomputers: Nic is mapped in the user address space: Faster but more challanges (Race condition, ....)

Senden

  • Blockierend: Weitere Instruktionen werden nicht ausgeführt bis vollst. gesendet. Direktes kopieren in empf. speicher möglich. Sender blockiert bis empf. bereit
  • Nicht Blockierend: ADV (volle kontrolle die ganze zeit), DIS (buffer kann nicht modif. werden solange sendet)

Recieve

  • Blockierend: Blocks until message received
  • Nicht Blockierend: tells kernel where to find receive buffer and returns control (interrupts, polling, popup threads, active messages)

RPC (Remote Procedure Call)

  • Allo Programs to call precedures located on other CPU's
  • Instead of I/O using send and receive. Remote communication is done by faking a normal procedure call

Distributed Shared Memory

  • Hardware, OS, Software realized
  • False Sharing: DSM (2 unrelated variables that happen to be on the same page are used by 2 different CPUs at the same time), ccNUMA (2 unrelated variables randomly on the same cache line are used by 2 different CPUs simultaneously

Multicomputer Scheduling und Lastverteilung

  • Each node has its own memry and os
  • llocation of processes to nodes
  • a
  • Space sharing: Nodes are assigned exclusively to an application
  • Gang scheduling: is also possible or useful, but requires snychronization of all nodes

Ebenen der Parallelverarbeitung:

  • Programmebene (Jobebene): Unabhängige Programme oder Prozesse
  • Prozessebene (Taskebene): Kooperierende Prozesse oder Threads | Meist mit Kommunikation durch Nachrichtenaustausch
  • Blockebene: Leichtgewichtige Prozesse/Threads | Kommunikation über gem. Speicher | Aufteilung der Iterationen von Schleifen durch Compiler
  • Anweisungsebene (Befehlsebene): Gleichz. ausf. elementarer Anweisungen. Hardware nah
  • Suboperationsebene: Bef. durch Comp. oder Prozesorren aufgebrauchen und parallell verarbeitet

UMA Multiprozessoren

  • Uniform Memory Access (UMA)
  • Alle CPUs greifen über den Bus auf den gem. Speicher zu (gleich schnell/langsam)
  • Bus und Speicher sind gemeinsame Betriebsmittel und werden schnell zum Engpass
  • Begrenzt Skalierbar
  • Bsp: Multikernprozessor PCs, Mehrprozessor-PCs

Numa Multiprozessoren

  • NON Uniform Memory Access
  • Every CPU has its own memory but shares it with others at different speeds. Local storage is fast and direct
  • Programmer and OS must consider different access times

Write-Back Cachse Schreibstrategie

  • Memory is not updated when writing in the cache
  • three processors access the same memory word and may get different results (in the worst case)

Write-Through

  • Consisten writing
  • hen writing main memory is always updated
  • W
  • Three processors access the same memory word and may get different results

Cache Kohhärenz

  • Each read operation on a memory word returns the last value written to this memory word according to the executed program
  • a cache memory system is coherent if and only if each processor sees its own write operations immediately, every write operation is seen at some point by every other processor (write propagation), all processors see write operations to the same memory word in the same order (write serialization)

Snooping basierte Cache Kohärenz

  • Special hardware removes a word if also consits in other caches when the cpus modifies it

Betriebssystem Pro CPU

  • Jede CPU aht eigenes OS
  • Haupt speicher wird statisch partitioniert und isoliert
  • System funktioniert wie n eigenst. computer
  • Shared I/O, flexible speicher allozierung

Master Slave Multiprozessoren

  • OS is executed by fixed master cpu
  • Slave cpus only execute user processes
  • system calls are redirected via interupt to master

Symmetrische Multiprozessoren

  • Only once instance of os in memory, executable by each cpu
  • cpus and memory dynamicall balacned
  • c
  • only one set of os data structures
  • no bottleneck by master
  • Problem: Accesing os data through os code on multiple CPUs requres mutual exclusion for ALL data structures

Timesharing

  • Preemptive scheduling: each thread can perform its tasks for the duration of a timeslice, then send back to waiting list
  • sysstem wide list of ready-to-run threads
  • each cpu selects and remoeves a thread with the highest priority from the list

Space sharing

  • Ensures that threads of a process always compute at the same time
  • process gets assigned a partition exclusively: one ccpu for each thread, process is only started if enought cpu is available, each thread remeians allocated to its cpu until it terminates
  • Batch scheduling of processes (First come first serve, shortest job first, ....

gang-scheduling

  • Betrachtet Gruppe verwandter Threads als Einheit oder GANG
  • Alle Mitgleider einer Gang laufen zeitgleich auf verschiedenen CPUs mit Timesharing, beginnen und beenden ihre Zeitabschgnitte gemeinsam
  • ynchroens Scheduling aller CPUs. Scheduling nur am Ende festgelegter Zeitscheiben. Bei Blockierung wird ie CPU bis zum Ende der Zeitscheibe unbenutzt

Besonderheiten bei OS für CC-Numa Parallelrechner

  • Speicherverwaltung: Zuteilung von kacheln auf möglichst nahem knoten. Auslagerung von Seiten pro Speicherzone (Knoten). Jeder Knoten lager nur lokale Seiten aus
  • Scheduling mit hoer Prozessor Affinität: Prozess oder Thread möglichst nahe bei seinen Daten starten. Processor Pinning feste Zuordnung eienr CPU
  • Teilweise statische Ressourcenzuteilung möglich. Threads und Bereichen des Logischen Addressraums können bei Programmstart über Knof file feste knoten zugeordnet werden

Multitenancy Architecture

  • Mehr-Mandaten Architektur
  • Mehrere Kunden / Systeme auf einer Maschine: Bessere Auslastungen, Mehr flexibilität

Was kann virtualisiert werden?

  • Server (VM), Netzwerk geräte (VNF), Hauptspeicher, Festspeicher
  • Generell gilt: Die Hardware softwarizen

VM Architectures

VMM = Virtual Machine Monitor (Middleware between the hardware and virtual machines)

Low Level VMM Operations

  • Suspend (Pause): Zustand/Abbild der Virtuellen Maschine (incl ram usw) wird in den Fest-Speicher des VM Hosts gelegt
  • Resume (Weiter): Vom Festspeicher des VM-Hosts wird der Zustand der Maschine in den Arbeitsspeicher geladen und die Maschine läuft wieder
  • Migration: Abbild/Zustand wird von einer VM in eine andere geladen (evtl auf einen anderen VM-Host)

Abstraction Levels

  • Application: Best isolation but lowest performance and high complexity: JVM/ .NET CLR/Panot
  • Library User-Level: Low implementation effor but pool perfomance and isolation: Wine / WABI/LxRun / Visual MainWin / vCuda
  • OS: Scalabilty, Low requirements but only same kind of os: Jail (Root Jail) / Virtual Environment / Ensims VPS / FVM / Docker
  • Hardware Abstraction Layer HAL: Good Performance, isolation but expensive and complex: VMware / Xen / L4 / Plex86 / VirtualBox
  • Instruction set Architecture (ISA): Bochs / Crusoe / Qemu / Bird / Dynamo

Instruction Level Abstraction

  • 2 Key Principles today: Instructions represented as numbers, Programs are stored in memory to be read or written like numbers
  • Programs are delivered as ready files of binary numbers
  • Computers may use the ready-made software only if its compatible to the instruction set
  • ISA (Instrcution Set Architecture): CISC, RISC
  • VLIW: Very Long Instruction Word

Hypervisor

  • Abstrahierende Schicht zwischen Hardware und dem zu Installierenden Betriebssystem.
  • Wird auch Virtual Machine Monitor VMM genannt

Bare Metal Hypervisor

  • Sits on the bare metal computer hardware like cpu, memory, ...
  • All the guest operating systems are a layer above the hypervisor
  • it is the first layer over the hardware
  • I

VMM Design

  • Each VMM acts as a traditional OS
  • Each time programs access the hardware, the vmm captures the processes
  • 3 Requirements: Identical environment, minor decrease in speed of programs, be in complete control of system ressources
  • 2 exceptions: Availability of system ressources (not enough), timing dependencies (2 vms on a machine)

Driver Management

  • Microsoft Hyper-V
    • Device drivers are loaded in the management partition (primary partition)
    • If the primary partition fails, vm lose the ability to talk to the outside world (if they survive at all)
  • VMWare ESX
    • loaded by the vmkernel into usermode space within the vmkernel
    • if the service console (modified red hat linux) fails, your vms continue to operate without problem

Xen Architecture

  • Open Source hypervisor program
  • Supports hardware level virtualization
  • Developed by Cambridge University
  • Microkernel hypervisor like Microsoft Hyper-V
  • Provides a mechanism by which a guest OS can have direct access to the physical devcices
  • Core Components: hypervisor, kernel, apps
  • The guest os which has control ability = Domain 0 (access ahrdware directly and manage devices, allocate and map hw ressources for D. U)
  • Others are called Domain U
  • Xen is based on linux (sec lvl C2): Mgmt in Domain 0 (behaves as VMM) and manages vms

Hosted Hypervisor

  • Runs over a host OS (not over bare metal hardware)
  • Hypervisor is the 2nd layer over the hardware
  • The guest OS runs a layer over the hypervisor and so they form the third layer
  • OS is usally unaware of th virtualization

KVM

  • Type 1 and Type 2 (Bare Metal and runs via host OS)
  • KVM Kernel module turns linux kernel into a type 1 bare metal hypervisor
  • The Overall system can be seen as type 2 since its a fully functional OS

Full Virtualization

  • Emulator
  • Simulates underlying hardware
  • Represented using data structures in the program
  • Instraction execution involves a dispatch loop that calls appropriate procedures to update these data structure for each instruction
  • Advantages: Runsy anywhere, requires no support from host
  • Disadvantages: Slow
  • Does not need to modify guest OS
  • Critical instructions are emulated by software (slow!)
  • Running non-cricital on hw (efficiency, security)

Paravirtualization

  • Hypervisor
  • Modifying the guest OS kernel to replace nonvirutalizable instructions with hypercalls
  • VM builds kernel-based VM on Linux
  • Needs to modify OS. Non-Virtualizable instrcution are replaced by hypercalls that communicate diractly with the hypervisor VM
  • Advantages: Reduces the overhead
  • Disadvantages: Compatability and portability is reduced because of deep connection with Host OS, Maintenance costs are high

Hypercalls

  • Use of Para virtualized guest OS assisted by an intelligent compiler to replace nonvirtualizable OS instruction by hypercalls
  • Execution: In order to issue a guest OS system call, APP VM interrupts the hypervisor to handle it and then pass contorl back to the guest OS because ParaVirtualization works in Ring 1 and cannot execute some sensitive / privileged instructions

CPU virtualization

  • Classic VMM trick: Directly execute VM in less prvileged mode. Trap and emulate privileged instructions
  • Popular x86 VMMs use binary translation to detect an demulate privileged instructions
  • Works well becaus eof high trap overheads

Intel hardware assisted CPU virtualization
  • OS runs at Rign 0, hypervisor can run at Ring -1
  • ll privileged and sensitive instructions are trapped in the hypervisor automatically

Memory Virtualization

  • Address translation: Expects contiguous (zusammenhängend) physical memory. VMM preserves this illusion
  • Page-Table shadowing: VMM intercepts paging operations. Constructs ccopy of page tables
  • Overheads: VM exists add to execution time. Shadow page tables consume significant host memory

Virtual IO devices

Virtualization Summmary

  • CPU virtualization demands hardware assited traps of sensitive instructions by vmm
  • Memory virtualization demands special hw support to help translate virtual address into physical address and machine memory in 2 steps
  • IO virtualization is the most difficult one to realize due to complexity of IO service routines and the emulation needed between the guest OS and host OS

Ringe

  • Auch Domain genannt
  • Privilegierungs bzw Sicherheitsstufe eines Prozesses im Bezug zum OS

Multicore virtualization

  • More difficult than a single core virtualization.
  • Challanges: Parallelize by utilizing all cores, Software must explicitly assign tasks to the cores (Scheduling, Ressourcce management policies), Dynamic heterogeneity

Virtual Cluster Characterostics

  • Nodes can be either physical or virtual machines
  • Host OS manages the ressources in the physical machine, where the VM is implemented
  • The purpose of using VMs is to consolidate multiple functionalities on the same server (Greatly enhances the server utilization and app flexibility)
  • VMs can be replicated in multiple servers. distr. parallelism, fault tolerance, and disaster rec.
  • The size (number of nodes) can grow or shrink dynamically
  • The Failure of any phyiscal node may disable some VMs instealled on the failing nodes (will not kill host system)

Changing the Network Architecture

Memory hot plugging

  • Hot add *
  • Hot remove * (Challange - how to release used memory)
  • Without stopping and starting your guest
  • W
  • Limited to a single server (host)

Memory Ballooning

  • Resize Overutilized VMs memory: Reclaim (borrow) a memory from another underutilized VM, Reallocate it to the overutiilized VM

Hot Plug vs ballooning

Inter-VM memory management

  • Cooperative memory swapping
  • Automatic memory control of multiple VMs: Dynamically adjusts memory allocation according to the used memory by the vms
  • A sharedmemory pool. Fast just in time page recovery

How to detect similar same pages

  • Reduce page comparisons by 68.5%
  • Classify pages: Check in teh stable sub-tree. If not found, check in teh global unstable tree. If find, deduplicate. If not, add
  • Use NVram as swap
  • Reduce swaps, thereby write to NVRAM (extends its life)
  • write count disparity: few pages of applications are frequently updated
  • most pages of applications are rarely updated

Cache misses

  • When data requested for processing by a component or app is not found in the memory. It causes execution delays

Page Faults

  • Wenn ein Programm auf einen Speicherbereich zugreift der sich gerade nicht im Hauptspeicher befindet sondern z.b. auf die Festplatte ausgelagert worden ist.

Quiescing

  • Shutds down a VM
  • Waits until the server bcomes underutilzed or
  • migrates it to another underutilized physical server

Streaming Disk

  • Migrates a small part of the VMs local disk only which is necessary to start the VM to another underutilized (nicht ausgelasted) server
  • Still, this technique proveds a gragmented disk space
  • Usually

Puma (Pooling unused memory in VM)

  • VM can use the memory of another VM (for caching purposes)
  • Can be even on different physical server
  • Suffer from fragmentation

Live Migration

Live Migration Approaches

  • Need to transfer only CPU/Memory status
  • Iterative Copy (Precopy)
  • Suspend VM and copy approach. If appliacations writable working set becomes small
  • Checkpoint/Recovery Trace/Replay approach. The size of log is smaller than dirty pages. Move and replay. Valid if log replac rate is larger than the log groth rate.

Other Migration Challanges

  • Which VM to migrate (80% in media cloud is internal traffic)
  • VM PLacement: Migrate a pair of VMs together. Communication Pair place on the same host. Communication Pair of hosts place on the same switch (or with smallest network diameter)

Software-ized Stirage

  • Network attached block storage
  • 99.999% Availability ~5minutes downtime per year
  • Attach / Detach to VMs (Restart required)
  • Can be used to create a snapshot in real time
  • Special add-ons: Burst packet

Definitions

  • IOPS: IO operations per second
  • Throughput: R/W Rate to a storage MB/s
  • Latency: Delay between a request and competition (ms)
  • Capacity: Volume of data that can be stored (GB)
  • BLock size: Size of each IO (KB)

Homework: Create Processes

Create 16 Child processes -> print to screen -> wait for them to finish. Order?

Homework: Signals

Create 1 child process. Send Signal to it every 5 seconds

Homework: Server

Multiple Servers which want to log to a logging server

  • Logging Service
    • Declare fifo files
    • mkfifo's
    • In Endless Loop: openFifos and read messages (via select)
  • Other Service
    • Other Services: Declare fifo file
    • Other Services: in endless loop: open and write to file and sleep afterwards

Homework: Shared Memory

  • Master
    • Allocate segment via shmget (Key for kernel and other process)
    • Attach to lokal variable via shmat
    • Set initial value
    • S
    • Detach afterwards
  • Slave
    • Same as on master

Homework: Threads

  • Create thread structure "pthread_t"
  • "pthread_mutex_init" to initialize mutex
  • "pthread_create" creates a thread with a thread handler (function)
  • Cancel via "pthread_cancel"
  • Join via "pthread_join"

Homework: Mutex

  • Setup environment with threads/processes
  • "pthread_mutex_lock(&mutex);" to lock the mutex
  • "pthread_mutex_unlock(&mutex);" to unlock the mutex

Write a code and explain the main steps to create a pipe from the parent to the child

  • create the child process
  • create the pipe at the parent process
  • attach parent to the pipe, parent has write rights
  • attach child to the pipe, child has read rights

Write a code and explain the main steps to create a two-way communication between parent and child process

  • create the child process
  • create the pipe at the parent process
  • attach parent to the pipe, parent has write rights
  • attach child to the pipe, child has read rights
  • create another pipe at the parent process
  • attach the parent to the pipe, parent has read rights
  • attach the child to the pipe, child has write rights

What is the difference between pipes and FIFOs

  • pipe is unnamed and only between processes who have connections to each other FIFO is a pipe which can be used by totally independent processes

Write a code and explain the main steps to create a program that duplicates its output to two other programs

  • Create a FIFO and then start prog3 in the background, reading from the FIFO.
  • After that, start prog1 and use tee to send its input to both the FIFO and prog2

Advantages of Memory-mapped I/O over I/O port numbers communication

  • I/O device driver can be written entirely in C (Device control registers are just variables, I/O Port has to use assembly code for In/OUT which is Impossible!?? in C
  • No special protection mechanism is needed to keep user processes from perofming I/O
  • Every instruction that can reference memory can also reference control registers

Advantages of I/O port numbers over Memory-mapped I/O communication

  • can cache a device ocontrol registers
  • needs less memory

The newly computer architectures use dual-bus (one to communicate to I/O and another high-bandwidth for CPU-memory communication. Does this provide benefit for I/O port numbers or Memory-mapped I/O communication? Explain the benefit.

  • WTF nothing in slides?

How to speed up the data access to hard drives?

  • better scheduling
  • better hardware
  • RAID: redudant array of inexpensive disks (split bits for faster reading/writing, use redudant bits/disks for parity checks, use full copy for heighest redundancy)

Explain aged SPTF

  • Scheduling Algorithmus (Shortest Positioning Time First)
  • Higher priority to the oldest requests
  • Calculates "effective" seek time from real time and weighting factor $T_{eff} = T_{Pos} - W * T_{wait}$
  • Sort requests for this weighted time

Name and explain one advantage of blocking versus non-blocking communication

  • Easier to use, so only non-blocking when neccessary
  • Single client strict protocol

Is distributed shared memory (DSM) UMA or NUMA? Is DSM implemented at hardware, OS or Application layer

  • (DSM), eine Speicherverwaltung ohne Replikation der Daten, das heißt, es gibt keine Kopien. Dadurch werden Inkonsistenzen des Hauptspeichers vermieden (Definition von NUMA)
  • OS Since it is about memory distribution

Write and explain one advantage and one disadvantage of using DSM

  • (DSM=Distributed Shared Memory)
  • Verteilung des Speichers bei Computer Clustern (kein gemeinsamer Speicherbus da verschiedene Mainboards)
  • Vorteil: Aus User sicht verhält sich DSM wie bei herkömmlichen Einzel-Systemen
  • Nachteil: Speicherverwaltung ohne Replikation daher keine Kopien

Write one advantage and one disadvantage of using copies of memory pages in DSM.

  • Vorteil: Inkonsistenzen werden vermieden???
  • Nachteil: Keine kopien möglich

How to mitigate (mildern) the risk of false sharing in DSM?

  • making use of private data as much as possible;
  • utilizing the compiler’s optimization features to eliminate memory loads and stores

What is space sharing and where it is used?

  • Nodes are assigned exclusively to an application
  • Used in virtualization

Propose some best effort scheduling for process placement in multi computer systems (not NP-complete complex).

  • Gang scheduling

Is write-through cache a cache coherent (zusammenhängend/einheitlich) technique? Why?

  • No because different processors access the same memory word and get different results!

Is write-back cache a cache coherent technique? Why?

  • No because different processors access the same memory word and get different results!

which technique write-back or write-through generates more traffic through the bus? More traffic on writes or reads?

  • write-through weil write-back nicht den main speicher updated
  • More traffic on writes!

Explain a protocol that achieves ccNUMA.

  • mesif protocol (developed by intel, consits of 5 states)

Explain symmetric multiprocessor operating system

  • Ist eine Multiprozessor-Architektur, bei der zwei oder mehr identische Prozessoren einen gemeinsamen Adressraum besitzen
  • Dies bedeutet, dass jeder Prozessor mit derselben (physikalischen) Adresse dieselbe Speicherzelle oder dasselbe Peripherieregister adressiert
  • Die meisten Mehrprozessorsysteme heute sind SMP-Architekturen.

Explain why using caching does not fit well when using spin-locks? Indeed, the caching will reduce the bus traffic. Then, what is the problem?

  • Spin-locks pollen andauernd und schreiben den Status in den cache was das System belastet und traffic erzeugt

time sharing vs space sharing

  • Time Sharing: Sharing Power (CPU, GPU)
  • Space Sharing: Sharing Memory

Explain why virtualization provides better elasticity and resource utilization

  • Virtual Machine Migration (Multiple machines/systems share the same ressources e.g. hdd vmware space provisioning)
  • Accessibility (Easy to manage)
  • Isolating Application (Security)

What is the difference between VM and VM image?

  • The VM is the whole system
  • The VM Image is just a copy of the hard drive

can you sketch a solution in which you can run two applications that use different operating system by using virtualization at an operating system abstraction level?

Sketch a solution with hypervisor type 1 and virtualization at an operating system abstraction level.

Which virtualization provides better performance and why? Full or Para?

  • Para since its not fully virtualized and uses the drivers/devices from the system/host

Which virtualization provides better portability and why? Full or Para?

  • Full because you can deploy it anywhere (on any system that supports virtualization)

Name and explain two techniques to reduce the memory utilization and page faults at hypervisor level

  • Write-Count Disparty
  • Read-Count Disparity???

Explain the “write count disparity” in memory management. How can be it exploited to reduce the memory page faults in virtual environment?

  • read misses are more critical than write misses because they stall the processor
  • Design a cache that favors ready over writes to increase perfomance

What is memory overcommitment? When does it make sense to use it? What are the challenges?

  • Give more ram to the vm's than there is avaiable on the host system in sum
  • Most of the time, the vm's will not eat all ram
  • When they are all consuming nearly all ram (the host or the admin should shutdown vms or do other countermeasures)

Present and explain two countermeasures for overcommitment.

  • temporary Shutdown or migration to another vm host
  • network memory or hdd swap

Explain the steps of live migration

  • Ressourcen Check am Ziel System
  • VM Ausschalten/Pausieren
  • VM Image Exportieren/Speichern
  • VM Image auf dem Ziel-Host Importieren
  • VM Einschalten

Explain the difference in Load balancing and consolidation. Name by one advantage for each of them.

  • Load Balancing: Every system should do the same amount work (work will be done faster)
  • Load Consolidation: Work should be done by as few systems as possible (not all ressources/systems are running and consuming power)

Ein Computer hat 8 Bandlaufwerke, um die sich n Prozesse streiten. Jeder Prozess braucht bis zu zwei Laufwerke. Für welche n kann es keinen Deadlock geben?

Bis 4 prozesse kannes keinen Deadlock geben

Ein verteiltes System, das Mailboxen zur Kommunikation verwendet, hat zwei IPC-Aufrufe, Send und Receive. Beim Aufruf von Receive muss der Absenderprozess angegeben werden. Receive blockiert, wenn keine Nachricht von dem angegebenen Prozess angekommen ist, auch wenn Nachrichten von anderen Prozessen in der Mailbox warten. Es gibt keine gemeinsamen Ressourcen, aber Prozesse müssen aus anderen Gründen häufig kommunizieren. Überlegen Sie, ob Deadlocks möglich sind. Geben Sie eine detailierte Begründung an.

Wenn Sterntpologie (Server = Zentrum, alles geht über Server) dann nicht

Wenn vermascht (client to client) dann können Deadlocks entstehen weil systeme untereinander auf antworten warten können (circle)