| FOTO | AUTO | EDV | AUDIO |

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

Beide Seiten der vorigen RevisionVorhergehende Überarbeitung
Nächste Überarbeitung		Vorhergehende Überarbeitung
edv:betriebsysteme:start [29 15 2026 19 : 15] – angelegt André Reichert-Creutzedv:betriebsysteme:start [29 41 2026 19 : 41] (aktuell) – André Reichert-Creutz
Zeile 2: Zeile 2:
 {{ :edv:betriebsysteme:bsscript.pdf |Script Betriebssysteme zur Erlangung des Grades Bachelor im Studiengang Informatik / Computer Science / B.Sc.}} {{ :edv:betriebsysteme:bsscript.pdf |Script Betriebssysteme zur Erlangung des Grades Bachelor im Studiengang Informatik / Computer Science / B.Sc.}}
  
-====== Kapitel 1 - Einleitung Betriebsysteme ======+====== DON'T PANIC: Per Anhalter durch das Betriebssystem ======
  
-  * Hauptaufgaben einen Betriebssystems  +Willkommen, Anhalter! Dieser zweiwöchige Kurs ist euer Handtuch für die Reise durch die Galaxis der Betriebssysteme. Ein Betriebssystem (OS) ist weit mehr als nur Code auf einem Bildschirm – es ist der ultimative Vermittler zwischen Benutzer, Anwendungen und der Hardware. 
-  * Unterschiede zwischen Betriebssystemen  +
-  * Bestandteile von Betriebssystemen +
  
-===== Einleitung - BS Definition =====+Ohne ein Betriebssystem müsstet ihr jede Spannungsänderung im Silizium selbst steuern – eine Aufgabe, die selbst die Geduld eines Vogonen überstrapazieren würde. In den nächsten zwei Wochen werden wir die fundamentalen Konzepte entschlüsseln. Die Antwort auf alle Fragen lautet vielleicht 42, aber bis wir dort ankommen, müssen wir verstehen, wie die Frage überhaupt im Speicher abgelegt wird.
  
-Ein Betriebsystem stellt **Dienste** und **Infrastrukturen** (Metasteuerungen) bereit. Daten oder Virtuelle Maschinen sind kein Teil des Betriebssystems sondern des Dienstleistungssystems. Die Metasteuerungen sind entscheidend beim Entwurf. (z.B. in Bezug auf Uni- oder Mehrbenutzersystem)+---
  
-Grob gesagt ist ein Betriebssystem eine erweiterte Maschine (Top-Down-Sicht), um durch Abstraktionen eine für den Menschen (Programmierer) überschaubare Form als Programmiergrundlage zu bieten.+===== Woche 1: Das Fundament der informationstechnischen Existenz =====
  
-{{http://www.kreissl.info/pics/images/bs_08.gif|Organisation eines Betriebssystem}}+==== Modul 1: Historie und Architektur (Tag 1) ==== 
 +Wie strukturieren wir das Chaos aus Nullen und Einsen? Alles begann mechanisch.  
 +  * Konrad Zuse konstruierte mit der Z1 das erste Rechenwerk, das voll auf der Grundlage des Dualsystems arbeitete.  
 +  * Die Z22 war später der erste Röhrenrechner der Zuse KG, in dem Programme direkt in der Maschine gespeichert werden konnten. 
 +  * Die erste Computergeneration (1945-1955) besaß gar kein Betriebssystem, programmiert wurde direkt mit Steckbrett oder Lochkarte. 
 +  * Danach kam die Stapelverarbeitung (Batch-Betrieb) der zweiten Generation, bevor die dritte Generation den Dialogbetrieb und Multiprogramming einführte.
  
-==== Definieren Sie den Begriff Betriebsystem! ==== +**Architektur des Kernels:** 
-Das Betriebssystem ist die **Gesamtheit der Programme** eines Rechensystems, welche die Betriebssteuerung erledigen und die Benutzeraufträgen eine zugängliche Umgebung bereitstellen. Betriebsmittel sind Komponenten sowohl der Hardware als auch der Software (System und Anwendersoftware), wie z.B. Prozessor, Speicher, Ein-Ausgabe-Geräte, Dateien, Programme etc.+  * **Die Monolithische Architektur:** Alle Komponenten sind starr zu einem homogenen Gebilde zusammengefügt. Das bringt extrem hohe Effizienz, auf Kosten der Flexibilität. Linux nutzt diese monolithische Architektur.  
 +  * **Die Mikrokern Architektur:** Der Kernel verfügt über deutlich weniger Funktionen (meist nur Speicher- und Prozessverwaltung) als ein Monolith. Er wird vor allem bei Echtzeitbetriebssystemen eingesetzt. 
 +  * **Mehrschichtige Architektur:** Das System wird in funktionelle, hierarchische Schichten oder Schalen getrennt, die mit unterschiedlichen Privilegien ausgestattet sind.
  
-Das Betriebssystem ermöglicht es z.B. dem Anwender, Programme auf unterschiedlicher Hardware laufen zu lassen. D.h. das Betriebssystem bietet dem Anwender eine **virtuelle Maschine**, welche die reale Hardware "unsichtbar" für den Programmierer macht. +{{http://www.kreissl.info/pics/images/bs_08.gif|Organisation eines Betriebssystem}}
  
->   * abstrahiert den Rechner auf eine für Menschen leichter durchschaubare virtuelle Maschine  +==== Modul 2: Prozesse, Threads und die galaktische Bürokratie (Tag 2) ==== 
->   * Steuert und koordiniert Prozessabläufe und verwaltet die Ressourcen  +Ein Prozess ist in der Informatik ein Programm, das sich in Befehle (Codebereich) und Programmdaten gliedert. Ein Thread ist eine Erweiterung dieses Modells – ein "leichtes Programm", das sich mit anderen Threads die Betriebsmittel teilt, aber einen eigenen Stapelspeicher (Stack) besitzt.
-> //Merktabelle: Definition Betriebssysteme//+
  
-===== Wie sieht das Ebenen- oder Schichtenmodell eines Rechners aus? ===== +Damit wir nicht Äonen warten müssen, nutzt das OS ein **Prozessmodell** mit diesen Zuständen: 
-  - Gatter Ebene  +  * **WARTEND (rechenbereit):** Der Prozess wartet auf die Zuteilung eines Prozessors. 
-  - Mikroprogrammebene  +  * **LAUFEND (rechnend):** Der Prozess ist aktuell einem Prozessor zugeordnet und läuft ab. 
-  - konventionelle Maschinenebene  +  * **UNTERBROCHEN:** Der Prozess wurde durch einen anderen Prozess unterbrochen. 
-  - Betriebssystemebene API  +  * **BLOCKIERT:** Der Prozess wartet auf ein Ereignis (z. B. I/O).
-  - Assemblerebene  +
-  - Anwendungsebene +
  
-==== Worin Unterscheiden sich Betriebssysteme? ==== +{{http://www.kreissl.info/pics/images/bs_09.gif|Prozessübergänge}}
-  * universal oder dezidiert (Multi-Task / Single-Task)  +
-  * eine oder mehrere Sitzungen (Windows < XP, Linux)  +
-  * Kommunikation mit der Umwelt (Batch, interaktiv oder in Echtzeit) +
  
-==== Was sind die drei Welten des Betriebsystems? ==== +Ein **Scheduler** bestimmt, wer rechnen darf. Beim **Round Robin** (Zeitscheibenverfahren) erhält jeder Prozess eine feste Zeitspanne, bevor er verdrängt wird. Beim **Prioritäts-Scheduling** wird einem Prozess eine Priorität zugeordnet, wodurch Prozesse niedrigerer Priorität warten müssen. Bei "First come, first served" wird schlicht derjenige bedient, der zuerst da ist.
-  * Betriebssystem selbst  +
-  * Komplexe Werkzeuge, wie aufgesetzte Dienste oder Virtuelle Maschinen  +
-  * Programmiersysteme zur Entwicklung von Erweiterungen +
  
-==== Welche Aufgaben hat ein Betriebsystem? ==== +==== Modul 3: Prozesskommunikation, Hierarchien und Deadlocks (Tag 3) ==== 
-  - Abstraktion der Hardware, d.h. Schließen der so genannten 'Semantischen Lücke' zwischen Mikroprogrammebene und der Anwendungsebene  +Ein Prozess kann einen neuen Prozess starten, wodurch ein "Elternprozess" und ein "Kindprozess" entstehen. Wird der Elternprozess beendet, beenden sich normalerweise auch alle seine Kindprozesse.
-  - Betriebsmittelverwaltung  +
-  - Steuerung von Peripheriegeräten (I/O, Festplatten...)  +
-  - Steuerung des Betriebsablaufs durch Prozessverwaltung und -Kommunikation und Organisation des Mehrprogrammbetriebes  +
-  - Protokollierung, Schutz und Sicherheit  +
-  - Behandlung von Ausnahmesituationen, wie Page Faults, Division by Zero u.s.w.  +
-  - Bereitstellung einer Kommandosprache  +
-  - Unterstützung von Administrationsaufgaben (Datensicherung, Systemkonfigurierung, Benutzerrechte) +
  
-===== Was ist ein Modell? ===== +Prozesse müssen kommunizieren (Inter-Process Communication). Dafür gibt es mehrere Wege: 
-Ein Modell eines Rechnersystems ist eine **Abbildung eines realen Systems** unter Abstrahierung bestimmter Kriterien, in dem eine formale Beschreibung durch eine Theorie in Gesetzen formuliert werden kann. +  * **Gemeinsamer Speicher:** Prozesse teilen sich Datenbereiche und Variablen. 
 +  * **Pipes:** Direkte Datenkanäle zwischen zwei Prozessen – einer schreibt, der andere liest. 
 +  * **Signale:** Ereignisse, die einen Software-Interrupt erzeugen. 
 +  * **Prozedurfernaufrufe (RPC):** Ein Prozess ruft eine Prozedur auf, die in einem anderen Prozess liegt.
  
-==== Welche drei Punkte sind bei der Realisierung eines BS grundlegend? ==== +Wenn Prozesse um Ressourcen kämpfen, droht der **Deadlock** (Stillstand). Dafür müssen vier Bedingungen erfüllt sein: 
-**Prozessor-Modes (Betriebszustände)**+  1. Mutual Exclusion (wechselseitiger Ausschluss). 
 +  2. Belegungs- und Wartebedingung (Prozess kann weitere Betriebsmittel anfordern). 
 +  3. Unterbrechbarkeitsbedingung (Betriebsmittel können nicht entzogen werden). 
 +  4. Zyklische Wartebedingung (Zyklus im Betriebsmittelgraph).
  
-| Supervisor Mode\\ (Kernel Mode) | Ist ein privilegierter Modus für Betriebssystemfunktionen im Kern des Systems, welches Sicherheit des Systems erhöht, da diese geschützt von Andwenderprogrammen laufen. | +==== Modul 4: Speicherverwaltung & Der Unwahrscheinlichkeitsdrive (Tag 4) ==== 
-| User Mode\\ (Anwendungsmodus) | Die Betriebsart wird über ein "Mode"-Bit angezeigt. Privilegierte Funktionen (wie I/O Funktionen) sind aber nur im Kernelmode ausführbar. Diese können über bestimmte Methoden gerufen werden. |+Der Arbeitsspeicher ist chronisch zu klein. Früher nutzte man **Overlay-Verwaltung**, bei der der Programmierer sein Programm selbst in Teile (Overlays) spalten musste, die das OS nacheinander lud. 
  
-**Kernel**+Heute rettet uns der **virtuelle Speicher**: Der Speicheradressraum des Prozessors wird vom realen Adressraum des Arbeitsspeichers getrennt.  
 +  * Beim **Paging** wird der virtuelle Adressraum in "Seiten" (Pages) unterteilt. Die korrespondierenden Einheiten im physikalischen Speicher heißen Seitenrahmen. 
 +  * Die Umrechnung erledigt die **Memory Management Unit (MMU)**. 
 +  * Ein **Translation Look-aside Buffer (TLB)** speichert die zuletzt verwendeten Umrechnungen zwischen – ein enormer Geschwindigkeitsvorteil. 
 +  * Alternativ (oder ergänzend) gibt es das **Segmentieren**, bei dem der logische Adressraum in Abschnitte variabler Größe (z. B. für Unterprogramme) geteilt wird. Die logische Adresse besteht dann aus Segment-Nummer und Offset.
  
-Im Kern laufen die Systemkritischen Funktionen, wie z.B. I/O-Aktionen ab. Der Kern muss korrekt, sicher und geschützt vor Anwendungen sein.+==== Modul 5: Eingabe, Ausgabe und Geräte (Tag 5) ==== 
 +Peripheriegeräte werden in das Dateisystem eingebunden und aus Benutzersicht meist wie Dateien behandelt. Wir unterscheiden: 
 +  * **Block Devices:** Blockorientierte Geräte wie Festplatten, die Daten nur in Form von Datenblöcken fester Länge verarbeiten. 
 +  * **Character Devices:** Zeichenorientierte Geräte wie Terminals, die einen Datenstrom aus einzelnen Bytes verarbeiten.
  
-**Methoden des Aufrufs von Betriebssystemsdiensten**+Die Gerätesteuerung kann programmgesteuert, unterbrechungsgesteuert (Interrupts) oder via **DMA (Direct Memory Access)** erfolgen. Beim DMA-Betrieb übernimmt eine DMA-Steuerung die Datenübertragung zwischen Hauptspeicher und Peripheriegerät völlig selbstständig, um den Prozessor zu entlasten.
  
-| System Calls | Durch **System Calls** können BS-Funktionen gerufen werden. Die Schnittstelle zwischen Usermode und Kernel sind sogenannte Traps (Einstiegspunkte). Geräte können Traps nicht nutzen, sondern können die BS-Dienste durch spezielle Interruptsmechanismen erreichen. | +---
-| Nachrichtenversand | Über eine **Send/Receive-Schnittstelle** können sich User-Mode und Kernel-Mode Nachrichten zuschicken. |+
  
-Sinn und zweck ist eine Entkopplung von System und Anwendung! Windows NT bietet eine API mit mehr als 10.000 Systemaufrufen, Unix dagegen ca. 300.+===== Woche 2: Dateisysteme, Cluster und die Zukunft =====
  
-{{http://www.kreissl.info/pics/images/bs_09.gif|System-Call am Beispiel Windows NT}}+==== Modul 6: Dateisysteme - Everything is a File (Tag 6) ==== 
 +Ein Dateisystem muss die physischen Blöcke einer Festplatte in die logische Form einer Datei übersetzen.
  
- +**Linux/Unix:** 
-====== Kapitel 2 - Modelle ====== +Unix nutzt zur Adressierung **INodes (Index Nodes)**.  
- +  * Ein INode enthält Informationen über Eigentümer, Zugriffsberechtigungen und Attribute. 
-  * Modelle für Betriebssysteme  +  * Er hat 13 Einträge zur Adressierung. Die ersten 10 zeigen direkt auf Datenblöcke. 
-  * Hierarchiche Schichtenmodell  +  * Der 11. Eintrag zeigt auf einen INode, der weitere Blöcke adressiert (einfach indirekt). Eintrag 12 ist doppelt indirekt, der letzte dreifach indirekt.
-  * Betriebsmittel und Instanzen  +
-  * Schalenmodell  +
-  * Modulmodell (Monolithisches Modell)  +
-  * Hierarchisches Schichtenmodell  +
-  * Client Server Modelle  +
- +
-===== Vor- und Nachteile von Schalen- und Modulmodellen ===== +
-**Schalenmodell:**  +
-  * Relationen der einzelnen Schalen sind zur Umwelt nicht sichtbar  +
-  * System ist aber gut strukturiert  +
-  * Innere Schalen sind sehr gut abgeschirmt von den Äußeren  +
- +
-**Modulmodell:**  +
-  * Das Modell wird in Modulen durch Programmcode beschrieben  +
-  * die Relationen werden daher extrem komplex (quatradisch)  +
-  * Daher ist es nur bei kleinen Modellen umsetzbar  +
- +
-===== Wie ist das hierarchische Schichtenmodell aufgebaut? ===== +
-Jede Schicht stellt Betriebsmittel und Dienste für den Zugriff auf die jeweilige übergeordnete Schicht bereit. Somit kann jede Schicht auch die Betriebsmittel und Dienste darunterliegender Schichten nutzen. Eine Schicht steuert die unmittelbare Schicht über ihr. (**Steuerungshierarchie**) +
- +
-**Bestandteile:**  +
-  * Schichten  +
-  * Iterative Ordnungsrelation der Schichten (Dienste, Steuerungen bzw. Instanzen)  +
-  * Betriebsmittel  +
-  * Funktionen zum Erzeugen von Betriebsmitteln und Steuerungen  +
- +
-==== Welche Vorteile hat das hierarchisch Schichtenmodell? ==== +
-  * obwohl modularisiert, ist die Zahl der Relationen gering  +
-  * Kommunikation mit der Umwelt ist möglich  +
-  * Es bietet eine Infrastruktur für Instanzen (Steuerung, BM-Transformationen)  +
- +
-===== Was ist ein Betriebsmittel? ===== +
-Ein Betriebsmittel ist eine abstrakte Ressource, welche über eine Adresse und einen Wert verfügt. Sie wird definiert über  +
-  * ID (eindeutiger Identifikator)  +
-  * Adressbereich (für alle möglichen Adressen des Betriebsmittels)  +
-  * Wertebereicht (aller möglichen Werte für einen Wert des BM)  +
-  * Funktion (verknüpft die abstrakten Elemente miteinander)  +
-//Der Zustand eines Betriebsmittels ergibt sich aus Wert x Adresse.//  +
- +
-==== Welche Klassen von Betriebsmitteln gibt es? ==== +
-  * Entziehbarkeit (entziehbar wie Prozessor oder nicht wie Dateideskriptor)  +
-  * Zuteilbarkeit (gleichzeitig wie Speicher oder exklusiv wie Prozessor oder Drucker)  +
-  * Wiederverwendbarkeit (einmalig Nutzbar wie Interrupt oder mehrfach wie Prozessor oder Speicher)  +
-  * Hardware / Software (logisches oder physikalisches Betriebsmittel)  +
- +
-==== Vorgehensweise beim Erstellen eines Betriebsmittels ==== +
-  - ID bestimmen  +
-  - abstrakte Elemente bestimmen, welche einen Wert und eine Adresse besitzen  +
-  - Wert und Adresse festlegen  +
-  - Funktionen definieren, welche Zugriff auf alle Elemente ermöglichen  +
- +
-==== Erläutern sie die Betriebsmittelerstellung am Bsp. Hauptspeicher! ==== +
-  - Eine ID ist hier nicht sinnvoll, da ein von-Neumann Rechner nur einen Hauptspeicher hat.  +
-  - die abstrakten Elemente sind die ansprechbaren Speicherzellen mit Adresse und Wert.  +
-  - Der Wertebereich beträgt 0 bist 255 bei einem Byte-Orientierten Speicher  +
-  - Funktionen sind Read und Write eines Elementes zum Speicher  +
- +
-===== Was ist eine Instanz? ===== +
-Eine Instanz ist ein Tupel aus id (Betriebsmittel) und einem Aktivitätstoken, welches die einzelnen Dienste ruft. Zwischen Betriebsmitteln untereinander und zwischen Instanzen untereinander bestehen Relationen.  +
- +
-==== Wechle Klassen von Instanzen kennen Sie? ==== +
-  * Applikationen  +
-  * Betriebsmittel-Transformatoren  +
-  * Metasteuerungen wie PUM  +
- +
-==== Wie können Relationen zwischen Instanzen technisch hergestellt werden? ==== +
-Protokolle und Schnittstellen verbinden sich Instanzen. Dabei treten beide immer zusammen auf. Eine Schnittstelle kennzeichnet das statische Verhalten einer Relation und ein Protokoll das dynamische, d.h. die Semantik der Relation. +
- +
-Als Beispiel nehmen wir einen Spooler. Hier ist die Schnittstelle ein Betriebsmittel (Speicherbuffer) und das Protokoll (Verhalten) ist als Dienst implementiert. +
- +
-//Spool = Simultanously Periphal Output On Line// +
- +
-Es gibt datenorientierte und steuerungsorientierte Schnittstellen. Datenorientierte Schnittstellen arbeiten ohne Synchronisation und verbrauchen viel Ressourcen (Busy Waiting). Steurerungsorientierte Schnittstellen sind z.B. Systemcalls und Interrupts. +
- +
- +
-====== Kapitel 3 - Aktivitäten ====== +
- +
-  * Was sind Aktivitätstoken?  +
-  * Welche Arten von Token gibt es?  +
-  * Was sind Prozesse?  +
-  * Unix Prozesserzeugung  +
-  * Zustände von Prozessen  +
- +
-===== Was ist ein Aktivitätstoken? ===== +
-  * Ist sehr abstrakt zu sehen  +
-  * Ein Aktivitätstoken haucht dem Programm erst "Leben" ein  +
-  * Beschreibt ein aktiven oder wartenden Prozess  +
-  * Es muss eine Art virtuellen Programmcounter im eigenen virtuellen Steuerwerk des Prozesses geben  +
- +
-===== Was ist Multitasking? ===== +
-Ist die Fähigkeit Prozesse parallel laufen zu lassen. Bei Einprozessormaschinen (kooperativ oder preemtiv) wird die Leistungsfähigkeit damit optimal ausgenutzt. Die verschiedenen Betriebsmittel können von mehreren Prozessen mehrfach bzw. parallel genutzt werden.  +
- +
-===== Welche Aktivitäten gibt es und worin unterscheiden sie sich? ===== +
-^ ^ Token ^ Verteilung ^ Protokoll ^ BM-Zuteilung ^ +
-| Prozedur | Eins für alle | - | Call Return | Exclusiv | +
-| Coroutine | Eins für alle | - | Resume, aber dynamischer Eintrittspunkt (kooperatives Multitasking) | Exclusiv | +
-| Prozess | Pro Prozess | Pro Prozess | Keine Übergabe, da Prozess Token behält | Exclusiv | +
-| Thread | Pro Prozess | Pro Thread Eins | Keine Übergabe, da Prozess Token behält | Threads sind in Prozessen gruppiert und teilen sich dort die Betriebsmittel | +
- +
-===== Welche Betriebsmittel benötigt eine Aktivität mindestens? ===== +
-  * Programmcode  +
-  * Hauptspeicher  +
-  * Steuerwerk  +
- +
-==== Wodurch wird ein Prozess beschrieben? ==== +
-  * ein im System eindeutiger Identifikator (PID)  +
-  * Liste mit Betriebsmittel-Forderungen  +
-  * Liste mit zugeteilten Betriebsmitteln  +
-  * Ein Folge der bisherigen Anweisungen  +
-  * Die Anfangswertbelegungen der zugeteilten Betriebsmittel  +
- +
-==== Welche Probleme treten mit Prozessen auf? ==== +
-  * Determiniertheit (Durch Mehrfachverwendung von Betriebsmitteln ist diese so nicht mehr gegeben und Synchronisation wird notwendig)  +
-  * Mutual Exclusion  +
-  * Synchronisation (Abstimmung zwischen Threads)  +
-  * Kommunikation (Synchronisation und Austausch von Daten zwischen Prozessen)  +
-  * Lebendigkeit  +
- +
-==== Welche Zustände kann ein Prozess einnehmen? ==== +
-  * nicht existent (Prozess noch nicht definiert)  +
-  * bereit (besitzt alle angeforderten Betriebsmittel außer den Prozessor)  +
-  * aktiv (besitzt mindestens die angeforderten Betriebsmittel)  +
-  * wartend (wartet noch auf noch nicht zugeteilte Betriebsmittel)  +
- +
-{{http://www.kreissl.info/pics/images/bs_01.gif|Prozess}} +
- +
-===== Wie wird ein Prozess im Unix erstellt? ===== +
-  * mit Systemaufruf fork() wird ein komplettes Speicherabbild eines schon bestehenden Prozesses erzeugt (bei NT wird Prozess mit einem Initialzustand erstellt)  +
-  * Deshalb erben neue Prozesse eventuelle Variablen des Vaterprozesses  +
- +
-Deshalb terminiert folgende Schleife nicht unter NT aber unter Unix: +
-<code c> +
-For ( i=1; i<3; i++) fork(); +
-</code> +
- +
-==== Einige Unix-Systembefehle zur Prozesserzeugung: ==== +
-  * fork(), vfork() zum Prozesserstellen mit Speicherabbild des Vaters  +
-  * clone() erstellt einen Prozess der der den Speicher und Deskriptoren mit Vater teilt  +
-  * execl(), execv(), execle(), execlp(), execvp() zum Kopieren eines Programms in den Speicher  +
-  * wait(), waitpid() zum Warten auf Ende des Sohnprozesses  +
-  * exit() zum Beenden eines Prozesses  +
- +
-==== Ein Beispielcode für eine Einfache Unix-Shell ==== +
-<code c> +
-#include <sys/types.h> +
-#include <sys/wait.h> +
-#include <unistd.h> +
-#include <stdlib.h> +
-#include <stdio.h> +
-#include <string.h> +
- +
-using namespace std; +
- +
-int main(void){ +
- +
-pid_t pid; //für PID des Sohnes  +
-char str1[1000]; //Befehlsbuffer +
- +
-while(1){ +
- +
-        printf("\nDiggs mini bash. (PID=%d)\n\n",getpid()); +
- printf("> "); +
- +
-        scanf("%s",str1); //Befehl lesen +
-       if (strcmp(str1,"exit")==0) break; //exit beendet +
- +
-        if ((pid=fork())<0) //Prozess kopieren +
-        { +
-        printf("EXEC Operation failed!\n\n"); +
-        exit(0); +
- } +
- +
-        if (pid==0) //im Sohnprozess exec +
- {                             +
-        char *cmd=strtok(str1," "); +
-        execlp (cmd,cmd,0); //Speicher überschreiben +
-         +
-        printf("command not found!\n"); +
-        exit(0); //manuell terminieren +
-       } //Vaterprozess muss warten +
- else waitpid(pid,0,0);  +
-} +
- +
-return 0;  +
-} +
-</code> +
-Der Vaterprozess liest einen Befehl (hier nur ohne Parameter) und startet danach einen Sohnprozess mit fork() in welchem mit dem Befehl exec das aufzurufende Programm in den Speicher kopiert wird. Schlägt exec fehl muss mit exit der Sohnprozess manuell beendet werden, da dieser sonst nicht terminieren würde. +
- +
-Am Besten einfach ausprobieren. Den Quellcode eingeben oder kopieren und mit dem gcc compilieren: +
-<code c> +
-gcc minishell.cc -o minishell  +
-</code> +
-//Aufruf: ./minishell//  +
- +
-===== Wie werden Prozesse verwaltet? ===== +
-Das Betriebssystem verwaltet alle Prozesse. Die Prozesse besitzen einen PCB (**Process Controll Block**), in welchem alle zum Prozess gehörigen Informationen gespeichert werden. Das Betriebssystem hat nun die Aufgabe alle n Prozesse auf einen oder mehr Prozessoren abzubilden.  +
- +
-===== Was ist Timesharing? ===== +
-Timesharing ist die **gemeinsame Benutzung des Betriebsmittels Prozessor** von mehreren Prozessen. Dabei ermittelt ein Scheduler den nächst auszuführenden Prozess. Ein Task-Switch bzw. Context-Switch bezeichnet eine solche Umschaltung zwischen den Prozessen.  +
- +
-===== Was sind virtuelle Geräte bzw. Betriebsmittel? ===== +
-Virtuelle Geräte stellen durch das Betriebssystem **simulierte Geräte** mit idealisierten Eigenschaften dar. Bewerkstelligt wird damit die Abstraktion von den Eigenschaften realer Geräte mit dem Ziel der Geräteunabhängigkeit. In der Regel stellen virtuelle Geräte jedem Prozeß eine synchrone Operation zur Verfügung. Dabei kann es erheblich mehr virtuelle als reale Geräte geben. Beispiele für virtuelle Betriebsmittel sind Druckerspooler oder Dateien.  +
- +
- +
-====== Kapitel 4 - Kritischer Abschnitt ====== +
- +
-  * Kritischer Abschnitt und Mutual Exclusion  +
-  * Dezentrale und Zentrale Steuerungen  +
-  * Semaphore und ihre Impementierung  +
-  * Verschiedenen Synchronisationsprobleme  +
- +
-===== Was ist ein Kritischer Abschnitt? ===== +
-Ein Kritischer Abschnitt ist ein zeitlicher Bereich, in welchem mindestens zwei Prozesse auf das gleiche Betriebsmittel zugreifen und mindestens eines davon schreibt. (Zeitkritischer Ablauf)  +
- +
-==== Erklären sie am Bsp. Druckerspooler den kritischen Abschnitt! ==== +
-  - in Spooler ist der Platz 4 frei  +
-  - Prozess A will drucken und liest die Platznummer  +
-  - PUM aktiviert Prozess B, welcher ebenfalls diese Platznummer liest  +
-  - Prozess B schreibt den Auftrag nach Platz 4  +
-  - PUM schaltet zu A zurück und A überschreibt nun den Druckauftrag von B!  +
-//**Deshalb notwendig:** Wechselseitiger Ausschluss!//  +
- +
-===== Warum werden keine Interrupt Unterbrechungen zur Synchronisation verwendet? ===== +
-Ein Prozeß der auf gemeinsame Daten und Ressourcen zugreift, kann nicht einfach alle Interrupts abschalten. Dies würde zu keinem optimalen Scheduling führen, weil dann jeder Prozeß solange die Kontrolle behalten darf wie er will. D.h. die wartenden Prozesse sind auf die Kooperation des gerade laufenden Prozesses angewiesen (kooperatives Multitasking wie Win 3.11)  +
- +
-===== Was ist wechselseitiger Ausschluss? ===== +
-Es muss gewährleistet werden, daß niemals sich mehr als ein Prozess in einem kritischen Abschnitt befinden darf. Die Anwendung einer einfachen Sperrvariable ist hier nicht möglich, da der Zugriff und das Setzen dieser, selbst einen kritischen Abschnitt darstellt. Es müssen Algorithmen gefunden werden, welche die Funktionalität gefahrlos implementieren.  +
- +
-==== Welche Anforderungen muss eine Steuerung für kritische Abschnitte erfüllen? ==== +
-  - exklusive Nutzung durch verschiedene Teilprozesse über mutual exclusion  +
-  - Ein Prozess darf einen anderen nur behindern, wenn beide im kritischen Abschnitt  +
-  - Der Eintritt in einen kritischen Abschnitt darf nicht lang dauern  +
-  - Alle Prozesse müssen in endlicher Zeit ihre Betriebsmittel zugewiesen bekommen  +
-  - globale Unabhängigkeit von allgemeinen Fortschreiten der Prozesse  +
- +
-===== Welche dezentralen Steuerungen kennen Sie? (aktives Warten) ===== +
-  * Test and Set Lock  +
-  * Ping-Pong (Striktes Alternieren)  +
-  * Decker Algorithmus  +
-  * Peterson Algorithmus  +
- +
-==== Wie arbeitet Striktes Alternieren? (Ping Pong) ==== +
-^ Prozess A ^ Prozess B ^ +
-| <code c> +
-While (1) +
-{ +
-    while (turn!=FALSE); +
- criticalsection(); +
- turn = TRUE; +
- notcriticalstuff(); +
-} +
-</code> | <code c> +
-While (1) +
-{ +
- while (turn!=TRUE); +
- criticalsection(); +
- turn = FALSE; +
- notcriticalstuff(); +
-} +
-</code> | +
-| ::: | Hier wird nur mit einer TURN Variable zwischen den Prozessen hin und her geschalten. Nachteil ist das die Abläufe nur abwechselnd in die kritischen Abschnitte eintreten können und das ein nicht im kritischen Abschnitt arbeitender Prozess trotzdem warten muss, bis der andere diesen wieder verlassen hat. | +
- +
-==== Wie schaut Peterson's Algorithmus aus? ==== +
-<code c> +
-CONST           N = 2;  //konkurrierende Prozesse +
-INT             turn; //Container für aktiven Prozess +
-INT             interested[N]; +
- +
-void P(int process)    //Eintreten +
-{ +
- int other = 1-process; //Gegenteil des Prozesses +
- interested[process] = TRUE;    //Interesse bekunden +
- turn = process;                //Flag setzen +
- while(( turn==process ) && (interested[other]==TRUE)); +
-} +
-void V(int process)    //Welcher Prozess verläßt K.A. +
-{ +
- interested[process]= FALSE;    //Kein Interesse mehr +
-}        +
-</code> +
-Das turn erzwingt ein Warten des interessierten Prozesses, solange ein andere Prozess im K.A. ist. Der Hauptnachteil von dezentralen Steuerungen für kritische Abschnitte ist das Aktive Warten (Spin Locks), was bedeutet, dass die Blockierzeit anderer Prozesse nicht genutzt werden kann.  +
- +
-===== Was sind Semaphore - zentrale Steuerung? ===== +
-Ein Semaphor ist ein allgemeiner Mechanismus zur Synchronisation, ohne aktiv warten zu müssen. Das Verfahren wurde von Dijkstra (1965) entwickelt und hat sich durchgesetzt. Ein Semaphor arbeitet auf einer priviligierten Schicht des Betriebssystems und ist somit nicht Teil der Prozesse.\\ +
-Ein Binärer Semaphor kann einen Kritischen Abschnitt für zwei Prozesse verwalten. Falls mehrere Prozesse gleichzeitig auf ein Betriebsmittel zugreifen dürfen, reicht der binäre Semaphor nich aus. Der Semaphor wird dann als Zähler implementiert. Falls er 0 ist, ist das Betriebsmittel voll ausgelastet. Ist er größer als 0, so sind noch Ressourcen vorhanden, d.h. andere Prozesse dürfen in den Kritischen Abschnitt eintreten, solange der Semaphor nicht Null ist. Dabei dekrementieren sie diesen und blockieren ihn für andere Prozesse, falls der Semaphor nun Null ist. Verläßt ein Prozess den Kritischen Abschnitt, inkrementiert der Prozess den Semaphor wieder und signalisiert damit, dass er seine Arbeit getan hat und nun ein anderer eintreten darf. Daher werden die beiden Operationen vor und nach dem Kritischen Abschnitt oft als Down(sem) und Up(sem) definiert.  +
- +
-==== Wie funktioniert das Grundprinzip von Semaphoren? ==== +
-Es wird nicht mehr eine Art Sperrvariable verwendet, sondern ein Zähler. Für dieses Zähler gibt es die Operationen up(s) bzw. V und down(s) bzw. P zum Erhöhen bzw. Dekrementieren des Zählers. Ist nach einem down(s) der Zähler null, wird gewartet. Ist er irgendwann wieder größer als null werden die Anweisungen ausgeführt. Der Semaphor ist nun nichts weiter als dieser Zähler, welcher nur durch up und down ansprechbar ist! Die beiden Operationen P und V stellen natürlich auch kleine kritische Abschnitte dar, welche über aktives Warten synchronisiert werden. +
-<code c> +
-P(sem) //Probiere in kritischen Abschnitt einzutreten +
-{ +
- if (sem == 0) +
-    sleep(sem); //Prozess auf wartend setzen +
- sem--; +
-}        +
-V(sem) //Verlasse kritischen Abschnitt +
-{ +
- sem++; //Zugang wieder freigeben +
- wakeup(sem); +
-} +
-</code> +
-sleep und wakup sind Systembefehle, welche einen Prozess Schlafenlegen oder Aufwecken. +
- +
-^ Prozess A ^ Prozess B ^ +
-| <code c>int sem = 1; //zwei Prozesse</code> | ::: | +
-| <code c> +
-While (1) +
-{ +
-   P(sem); +
-   // kritischer Abschnitt +
-   V(sem); +
-} +
-</code> | <code c> +
-While (1)   +
-{ +
-   P(sem); +
-   // kritischer Abschnitt +
-   V(sem);    +
-} +
-</code> | +
- +
-==== Wie arbeiten Events bzw. Ereignisse? ==== +
-Betriebssysteme wie z.B. Unix benutzen Events als Abstraktion von Semaphoren zum **Koordinieren** von Prozessabläufen (im Gegensatz zu kritischen Abschnitten). Ein Ereignis stellt nichts weiter als eine für Software erkennbare **Bedingung** dar. Ein Prozess kann sich Schlafen legen, bis eine bestimmte Bedingung eintreten.  +
-  * Ein Prozess setzt einen wait()-Aufruf auf ein Ereignis ab. Er wird dann an dem Event-Deskriptor wartend gesetzt.  +
-  * Wenn an dem Event-Deskriptor das Ereignis signalisiert wird, so wird ein dort wartender Prozess bereit gesetzt.  +
-  * Der wesentliche Unterschied zu den Semaphor-Operationen ergibt sich daraus, dass die Signale nicht gespeichert werden, bei Semaphoren wird dagegen der Wert bei signal() um 1 erhöht.  +
- +
-**Semaphore:** Wert 0. Kommt das signal() vor dem wait(): der wait()-aufrufende Prozess wird nicht blockiert. +
- +
-**Event:** Ein Wert ist nicht vorhanden, kein Prozess wartet. Das Ereignis wird vor dem wait()-Aufruf signalisiert: der wait()-aufrufende Prozess wird blockiert, bis ein weiteres Ereignis eintrifft. Das erste Ereignis wird nicht gemerkt.  +
- +
-==== Was versteht man unter einem Monitor und wie funktioniert er? ==== +
-Ein Monitor besteht aus einigen Prozeduren, Variablen und Datenstrukturen die zu einer besonderen Art Modul zusammengefasst werden. Dieses Monitormodul verkapselt Semaphore und die Operationen auf diesen Semaphoren. Nützlichste Eigenschaft eines Monitors ist, daß jeweils nur ein Prozeß zu einer Zeit einen Monitor benutzen kann. Ein Monitor ist zwar vielen Prozessen zugänglich, aber nur jeweils ein Prozeß kann den Monitor zu einem gegebenen Zeitpunkt benutzen. Monitore werden häufig zur Verwaltung von Puffern und Geräten eingesetzt.  +
- +
->   * Es gibt dezentrale und zentrale Steuerungen für kritische Abschnitte  +
->   * Dezentrale Steuerungen ist das aktives Warten  +
->   * Zentrale Steuerungen sind Semaphore (passives Warten)  +
->   * Beim passiven Warten werden Prozesse schlafengelegt  +
->   * Ereignisse dienen der Koordination +
-> //Merktabelle: Synchronisationsmöglichkeiten// +
- +
-===== Was ist das Erzeuger-Verbraucher-Problem? ===== +
-Zwei Prozesse nutzen einen Puffer mit N Plätzen zum Datenaustausch. Während Prozess A Daten sequentiell in den Puffer schreibt, entnimmt Prozess B ein Datum aus dem Puffer. +
- +
-Nun stellen sich die Fragen  +
-  - Wie soll man das gleichzeitige Einfügen und Entnehmen synchronisieren?  +
-  - Ein Datum darf nur eingefügt werden wenn der Puffer nicht voll ist.  +
-  - Ein Datum darf nur eingefügt werden, wenn noch Platz im Buffer ist.  +
- +
-Gelöst werden, kann das Problem mit mehreren Semaphoren.  +
-  * Ein Semaphor für die Kontrolle des kritischen Abschnittes  +
-  * Ein Semaphor, welcher die freien Plätze zählt  +
-  * Ein Semaphor, welcher die vergebenen Plätze zählt  +
-<code c> +
-const N 100      //buffer size +
- +
-int mutex = 1 //Für Kritischen Abschnitt +
-int empty = N //Anfangs leerer Buffer +
-int full  = 0 //noch keine Daten im Buffer +
-void ErzeugerProzess() +
-{ +
- int item;       +
-    while(1) +
- { +
-    iNode = CreateItem(); +
-    P(empty); +
-    P(mutex); +
-    Insert(item) //Critical Section +
-    V(mutex);        //Mutex wieder erhöhen +
-    V(full);         //full=full+1 +
- } +
-} +
-void VerbraucherProzess() +
-{ +
- int item; +
-    while(1) +
- { +
-    P(full); +
-    P(mutex); +
-    Item = RemoveItem(); //Critical Section +
-    V(mutex); +
-    V(empty); +
-    MakeSomething(Item); +
- } +
-} +
-</code> +
-Der Semaphor mutex verhindert, daß gleichzeitig Verbraucher und Erzeuger im kritischen Abschnitt sind. Denn falls der Erzeuger gerade eingetreten ist, ist der Semaphore mutex null. Versucht nun der Verbraucher in den kritischen Abschnitt einzutreten, muss er bei P(mutex) warten, da der mutex noch null ist. Um nun zu Verhindern das aus einer leeren Liste gelesen oder in eine volle geschrieben wird, werden hier elegant zwei weitere Semaphoren verwendet, welche das Vorhandensein von freien Plätzen (empty) und belegten P lätzen (full) zählen.  +
- +
-===== Was ist das Philosophenproblem? ===== +
-Beim Philosophenproblem geht es nicht um Kommunikation sondern um Synchronisation. Abstrakt gesehen, gibt es N Prozesse und N Betriebsmittel. Ein Prozess benötigt mindestens zwei der Betriebsmittel um fortschreiten zu können. Ohne Synchronisation, würden im schlimmsten Fall alle 5 Prozesse je ein Betriebsmittel bekommen und dann unendlich darauf warten, daß ein anderer Prozess eins freigibt. +
- +
-Es sitzen fünf Personen an einem runden Tisch. Sie können entweder Denken oder Essen. Es gibt zwar für jeden einen Teller, aber nur fünf Stäbchen. Um Essen zu können braucht man aber bekanntermaßen zwei.  +
- +
-==== Wie kann das Philosophenproblem gelöst werden? ==== +
-Natürlich denkt man zuerst an Semaphoren. Nur funktioniert die triviale Lösung mit einem Semaphor pro Stäbchen nicht. Es können immer noch alle Philosophen je ein Stäbchen gleichzeitig aufnehmen und die Prozesse wären allesamt verklemmt. Es muss also irgendwie möglich sein, mehr als ein Stäbchen gleichzeitig aufzunehmen. Bei den verschiedenen Implementationen ist vor allem darauf zu achten, daß dieses Aufnehmen der beiden Stäbe eine Atomare Funktion ist.  +
- +
-===== Wie funktionieren Unix-Signale? ===== +
-Ein Ereignis wird hier als Signal bezeichnet. Unter Unix gibt es vorgegebene durchnummerierte Signale. Unter Unix kann mit //kill(Prozessnummer, Signalnummer)// einem Prozess ein Ereignis signalisiert werden. +
- +
-Die Reaktion eines Prozesses auf ein Signal kann verschieden ausfallen: +
-  * Aktivierung einer Prozessfunktion, die der Prozess vorher für dieses Signal mit der Funktion **signal( Signalnummer, Funktionsadresse)** angemeldet hat  +
-  * Er kann das Signal mit **signal(Signalnummer, SIG_IGN);** ignorieren  +
-  * Der Prozess kann beendet werden.  +
-  * Hat der Prozess für eine Signalnummer nichts festgelegt, dann gibt es Voreinstellungen:  +
- +
-| | #define SIGFPE | 8 | /* Floating point trap */ | +
-| | #define SIGILL | 4 | /* Illegal instruction */ | +
-| | #define SIGINT | 2 | /* voreingestelle Interrupttaste z.B. Ctl -c*/ | +
-| | #define SIGSEGV | 11 | /* Memory access violation */ | +
-| | #define SIGTERM | 15 | /* Kill -Kommando ohne Angabe*/ | +
-| | #define SIGKILL | 9 | /* unbedingter Prozessabbruch*/ | +
- +
-===== Was unterscheidet Pipes und Named Pipes? ===== +
-Pipes sind nur innerhalb von Prozessgruppen (UNIX) oder zwischen Threads eines Prozesses verwendbar, da diese nur dort bekannt ist (und eindeutig identifizierbar). Diese Einschränkung kann mit der **Named Pipe** umgangen werden. Eine Named Pipe ist ein mit einem **eindeutigen Namen versehenes Objekt** des Betriebssystems. Ein Prozess kann die Pipe erstellen, ein anderer kann eine Verbindung zu der Pipe herstellen. Im UNIX erhält eine Named Pipe einen Pfadnamen, wie eine Datei. +
-{{http://www.kreissl.info/pics/images/bs_12.gif|Pipe Schema}} +
- +
-===== Was sind Sockets? ===== +
-Sockets sind im Grunde Pipe Erweiterungen für Internet und andere Netzdienste. Dabei werden ein SocketA und ein SocketB zu einer bidirektionalen Pipe verbunden. Identifiziert wird ein Socket über Rechneradresse und Portnummer. So ermöglichen Sie eine Client-Server-Kommunikation: +
- +
-Ein Serverprozess erstellt einen Socket mit //create// und wartet dann auf Verbindungswünsche (//listen//).  +
- +
-===== Welche Möglichkeiten zur Kommunikation und Synchronistation kennen Sie? ===== +
-**Kommunikation**  +
-  * Pipes (FIFO-Puffer - Senden (Schreiben) ist asynchron, Empfangen (Lesen) blockierend)  +
-  * Named Pipes  +
-  * Mailboxen (Tool zum Senden und Empfangen von Nachrichten)  +
-  * Send - Receive (BS Unterstützung für Mailboxen - synchron oder asynchron)  +
-  * Queues  +
-  * Sockets  +
-  * RPC  +
-  * Shared Memory  +
- +
-**Synchronisation**  +
-  * Monitore  +
-  * Events  +
-  * Semaphore  +
-  * Barierren (oft zur Threadsynchronisation verwendet)  +
- +
- +
-====== Kapitel 5 - Scheduling ====== +
- +
-  * zentral, dezentral und Modelle für Scheduling  +
-  * Scheduling Strategien  +
-  * Prioritätsscheduling und Round Robin  +
- +
-Scheduling wird notwendig, wenn die Anzahl der gleichzeitig laufenden Prozesse die Anzahl der physikalischen Prozessoren übersteigt. Die Verwaltung kann dezentral (Prozesse selbst) oder zentral erfolgen. Es gibt zwei grundlegende Modelle für zentrale Scheduling-Verwaltung:  +
-  * Deterministisches Modell - alle Informationen bekannt (Anzahl Prozesse/Betriebsmittel/Zeitdauer)  +
-  * Probabilistisches Modell - offen (Anzahl Prozesse nicht bekannt) oder geschlossen (Anzahl Prozesse bekannt, aber Bedienzeiten nicht)  +
- +
-===== Welche Strategien der Prozessorzuteilung werden unterschieden? ===== +
-  * **Durchsatz** (Anzahl bearbeiteter Prozesse pro Zeiteinheit maximieren)  +
-  * **Verweilzeit** (Prozess soll so schnell wie möglich abgearbeitet sein)  +
-  * **Wartezeit** (Dauer im Zustand "wartend" minimieren)  +
-  * **Effizienz** (Prozessorleistung maximal ausnutzen)  +
-  * **Antwortzeit** (möglichst kurze Reaktionszeiten für den Benutzer)  +
-  * **Fairness** (gerechte Verteilung der Prozessorzeit)  +
- +
-Es ist nicht möglich CPU-Auslastung und Durchsatz zu maximieren und gleichzeitig Warte- und Antwortzeit zu minimieren. Deshalb müssen alle Scheduling Algorithmen Kompromisse eingehen.  +
- +
-===== Nach welchen Kriterium richtet sich das Scheduling Verfahren? ===== +
-Dies hängt in erster Linie vom Einsatzgebiet des Systems ab:  +
-  * Echzeitbetrieb  +
-  * Dialogbetrieb  +
-  * Stabel- bzw. Batchbetrieb  +
-  * Hintergrundbetrieb  +
- +
-===== Was ist das deterministische Modell? ===== +
-Bei diesem Modell werden die Schedules **vor der Ausführung berechnet**. Dies funktioniert natürlich nicht in interaktiven offenen Systemen, sondern nur in geschlossenen Systemen mit fester Prozessanahl und vordefinierter Betriebsmittelnutzung mit statischen Ablauf. In Dialogsystemen wird deshalb das offene probabilistische System verwendet, da hier Anzahl der Prozesse und Betriebsmittelnutzung dynamisch erfolgen...  +
- +
-===== Was ist das probabilistisches Modell? ===== +
-Die Entscheidung welcher Prozess den Prozessor bekommt, wird dynamisch wärend der Prozessabarbeitung gefällt. Hierbei gibt es einige wichtige Größen, welche als stochastische Variablen zur Berechnung herangezogen werden können. Die Warteschlangentheorie ist wichtiges Mittel für Untersuchungen. (Alle Prozesse welche den Prozessor fordern werden in eine Warteschlange eingereiht). +
- +
-{{http://www.kreissl.info/pics/images/bs_02.gif|Prozess}} +
- +
-Die Abbildung entspricht einem Scheduling ohne Prioritäten und ohne Entzug.  +
- +
-==== Was ist das Single-Server-Modell? ==== +
-Eine Warteschlange nimmt Prozesse in einem bestimmten Abstand (A) auf. Der Scheduler entnimmt nach einer gewissen Wartezeit (W) im Pool einen Prozess und führt diesen in einer bestimmten Zeit (B) aus . +
-{{http://www.kreissl.info/pics/images/bs_06.gif|Singe-Server}} +
- +
-| mittlere Verweildauer in Warteschlange | W | +
-| Zwischenankunftsabstand | A | +
-| Prozessorzeit der Teilprozesse | B | +
-| Anzahl von Prozessen in Warteschlange | Nq (N=Nq+p) | +
-| Verkehrswert | p=B/A //(Poisson-Prozesse)// | +
-| Verweildauer im System | V=A*N (Littles Theroem) | +
- +
-Weiter Größen wie durchschnittliche Warteschlangellänge oder die Wahrscheinlichkeit das sich n Prozesse im System befinden, lassen sich mit Poissen-Verteilungen genauso wie die oben erwähnte mittlere Verweildauer ermitteln.  +
- +
-==== Wie können Wahrscheinlichkeiten für Prozessgrößen ermittelt werden? ==== +
-Durch Poisson-Prozesse (Markow) können Erwartungswerte, Mittelwerte und Varianzen für Zwischenankunftsabstände, Bedienwünsche und Auslastung berechnet werden. Die Betrachtungen beziehen sich hier auf den stationären Fall (t->unendlich, also FiFo).  +
- +
-==== Wie arbeitet First Come First Serve - FCFS? ==== +
-Ankommende Prozesse werden in eine FIFO Liste eingereiht und sequentiell abgearbeitet. Somit ist dieses Modell nicht für Timesharing geeignet, da es eher eine Batchverarbeitung ist. +
- +
-Kommt ein langer Prozess zuerst, müssen andere winzige Prozesse alle auf die Beendigung des großen Prozesses warten! Unfair. Bessere Implementationen können deshalb das Token entziehen. +
- +
-**Durchschnittliche Wartezeit W** = (Wartezeit(P1) + Wartezeit(P2) + ... + Wartezeit(Pn)) / n +
- +
-Ist P1 ein vielfach größerer Prozess als die restlichen, so müssen alle folgenden Prozesse auf die Beendigung von P1 warten. Dies läßt die durchschnittliche Wartezeit extrem steigen. +
- +
-**Bsp.:** +
- +
-t(P1) = 24  +
-t(P2) = 3  +
-t(P3) = 3 +
- +
-Bei einer Abarbeitungsfolge von **P1 -> P2 -> P3** wäre W = //17//. +
-Bei einer Abarbeitungsfolge von **P2 -> P3 -> P1** nur //3//!  +
- +
-===== Was ist Prioritäts-Scheduling? ===== +
-Hier wird jedem Prozess eine Priorität zugewiesen. Ausgewählt wird vom Scheduler der ausführbereite Prozess mit der höchsten Priorität. Die Prioritäten können statisch definiert und dynamisch zugewiesen werden. +
- +
-//**Bsp:** FEP (**Fixed External Priorities**)// +
- +
-{{http://www.kreissl.info/pics/images/bs_07.gif|Prioritätsscheduling}} +
- +
-==== Was ist das Problem von Schedulern mit Prioritäten? ==== +
-Hauptproblem beim Arbeiten mit Prioritäten ist das **Aushungern** von Prozessen, welche möglicherweise nie aktiv werden können, da es immer Prozesse höherer Priorität gibt. +
- +
-Lösung hierfür ist das **Aging**. (dynamische Anhebung der Priorität der älter werdenden Prozesse) +
- +
-Ein anderes Problem ist die Prioritätenumkehr. Ein hochpriorisierter Prozess wartet auf ein Betriebsmittel, welches ein niedrigpriorisierter Prozess reserviert hat.  +
- +
-==== Wie funktioniert Shortest Job First (dynamische Priorität ohne Entzug)? ==== +
-Es wird der kürzeste Job zur Verarbeitung ausgewählt. Dabei werden die Durchlauflängen der einzelnen Prozesse protokolliert. Nach jedem Prozesswechsel wird die "bereit"-Warteschlange anhand der Wartezeiten absteigend neu sortiert. +
- +
-Deshalb optimiert Shortest Job First die mittlere Wartezeit. Problem ist hier auch das Aushungern von Prozessen, was auch durch Aging (Altern) verhindert werden kann. +
- +
-**SJF ist ohne Entzug** (nonpreemtiv). Eine Variante mit Enzug ist **SRTF**. Dabei wird der Prozessor entzogen, falls ein Prozess in der Warteschlange ist, der kürzer als der verbliebene Rest des aktiven Prozesses.  +
- +
-==== Wie arbeiten Shortest Remaining Time First und Shortest Elapsed Time (dynamisch mit Entzug)? ==== +
-Diese beiden Verfahren sind mit Prioritäten und mit Entzug. Sie sind daher relativ aufwendig, da ein ständiger Abgleich der Prioritätsdaten erfolgen muss. Bei SET wird Prozessen, welche schon viel Prozessorzeit zugesprochen bekamen, die die Prozessorzeit entzogen.  +
- +
-==== Wie arbeitet Highest Response Ratio Next - HRN? ==== +
-Umso länger ein Prozess wartet, umso höher steigt er in seiner Priorität. So wird Aushungern verhindert.  +
- +
-===== Wie funktioniert Round-Robin Scheduling (ohne Prioritäten)? ===== +
-Das RR ist die verbreitetste Strategie, da sie fair ist und sich auch einfach implementieren lässt. Das Prinzip ist einfach. Jeder Prozess erhält für eine konstante Zeit t (**Quantum**) die Prozessorzeit. Nach Ablauf des Zeitquantums wird der nächste Prozess aus der Warteschlange entnommen und bearbeitet. Der zuvor bearbeitete Prozess wird wieder am Anfang der Liste eingefügt. +
- +
-Hauptproblem ist eine sinnvolle Zeitspanne für das Quantum zu finden. Da bei jedem Kontextwechsel Register umgeladen müssen, muss ein gewisser Zeitraum für Verwaltungsarbeiten eingerechnet werden. Dauert das Umladen der Register 5 ms macht ein Quantum von 10 ms wenig sinn, da 50% Prozessorzeit verschwendet werden würde. Wählt man das Quantum aber zu groß (z.B. 500 ms) so ist im Mehrbenutzerbetrieb nur bedingte Interaktivität möglich. (RR nähert sich somit FCFS an) +
- +
-//Sinnvoll erwiesen sich Quanten von 100 ms.//  +
- +
->   * Scheduling mit oder ohne Entzug  +
->   * Scheduling mit oder ohne Prioritäten  +
->   * Zentrale Steuerungen sind Semaphore (passives Warten)  +
->   * Beim passiven Warten werden Prozesse schlafengelegt  +
->   * Ereignisse dienen der Koordination  +
-> //Merktabelle: Scheduling Algorithmen// +
- +
-===== Was ist Zweistufiges Scheduling? ===== +
-Angenommen der Arbeitsspeicher reicht nicht aus, um alle Prozesse abzubilden, müssen diese auf einen Tertiärspeicher ausgelagert werden. Da das Auslagern bzw. Einlagern eines Prozesses sehr viel Zeit in Anspruch nimmt, werden zwei Stufen benutzt, um das Scheduling zu realisieren. Die erste Stufe arbeitet nur im Hauptspeicher, während die zweite Stufe für das Ein- oder Auslagern von Prozessen verantwortlich ist. Kriterien sind hier dieselben wie oben schon erwähnt.  +
-  - Wie lange ist ein Prozess Aus- oder Eingelagert?  +
-  - Wieviel Prozessorzeit hat ein Prozess in Anspruch genommen?  +
-  - Wie groß ist der Prozess im Speicher?  +
-  - Welche Priorität hat der Prozess?  +
- +
-==== Was steht im Widerspruch zu hohem Durchsatz und guter Auslastung? ==== +
-Im Widerspruch dazu stehen **gutes Antwortzeitverhalten** im Dialog- und Stapelbetrieb. Denn ein hoher Durchsatz und eine gute Auslastung bedingen viele Prozesse im Rechner, so daß jeder Prozeß nur relativ selten aktiv werden kann, d.h. das Antwortzeitverhalten schlechter wird. Auch die Zuteilungsfairness wird dadurch zunehmend schlechter bzw. unfairer.  +
- +
- +
-====== Kapitel 6 - Speichermanagment ====== +
- +
-  * Freispeicherverwaltung durch Bitmaps, Listen und Buddy  +
-  * Mehrdimensionale Adressräume durch Segmentierung  +
-  * virtueller Speicher durch Paging  +
-  * Zusammenwirken von Segmentierung und Paging  +
-  * Adressumrechnung am Beispiel  +
- +
-**Übersicht zur Freispeicherverwaltung** +
- +
-Es gibt drei grundlegende Ansätze zur Verwaltung des freien Speichers. Diese werden im folgendem Text erläutert.  +
- +
-==== Was sind Bitmaps? ==== +
-Bitmaps teilen den Hauptspeicher in gleich große Einheiten und assoziieren zu jedem Eintrag ein Bit in der Bitmap. Ist der Eintrag 0, so ist der Speicherbereich noch frei. Bei Nutzung eines Speicherbereiches wird in dem assoziierenden Bitmapplatz eine eins platziert. Umso kleiner die zusammengefassten Einheiten werden, umso größer wird die Bitmap. Der größte Nachteil von Bitmaps ist das Suchen von freien Speicherbereichen, was eine aufwendige Operation darstellt.  +
- +
-==== Welche Möglichkeiten der Suche in Freispeicherlisten gibt es? ==== +
-Bei dieser Variante werden Listen für Löcher und belegte Segmente durch Prozesse geführt. +
- +
-**First Fit** +
- +
-Der erste freie Block der groß genug ist wird ausgewählt, egal wieviel Speicher dadurch verschwendet wird (interne Fragmentierung). +
- +
-**Next Fit** +
- +
-Suche beginnt nicht vom Anfang der Liste, sondern vom zuletzt verwendeten Listenelement. +
- +
-**Best Fit** +
- +
-Es wird der optimale Platz in Bezug auf Speicherausnutzung gesucht. Dadurch das immer Blöcke mit der geringsten Speicherplatzverschwendung gesucht werden, werden die freien Blöcke irgendwann zu klein. +
- +
-**Quick Fit** +
- +
-Es gibt mehrere Listen für verschiedene Blockgrößen.  +
- +
-==== Wie funktionieren Buddy Listen? ==== +
-Listen haben den Nachteil, daß benachbarte freie oder belegte Speicherbereiche sich nicht zusammenlegen lassen. Abhilfe schafft hier das Buddy-System. Die Idee beruht darauf, dass mehrere Listen geführt werden, welche aber nur Blockgrößen von 2^n zulassen. Zweierpotenz deshalb, weil ein Rechner Binärzahlen zur Adressierung benutzt. +
- +
-**Beispiel:** +
- +
-Die maximale Blockgröße beträgt 64 Mbytes und die minimale Blockgröße 4 Kbyte. D.h. 226 - 212, also müssen Listen für N=12 bis N=26 verwaltet werden. Somit wären für diese Blockgrößenwahl mit dem Buddysystem 15 Listen notwendig. +
- +
-Anfragen werden nun immer zur nächsthöhren Zweierpotenz aufgerundet. D.h. wird eine Anfrage an einen 75 Kbyte Block gestellt, muss ein 128 Kbyte großer Slot verwendet werden. Anfangs gibt es eine Liste für in unserem Beispiel 64 Mbyte Speicher. Der Buddymanager würde die Liste rekursiv so oft teilen, bis ein 128 Kbyte großer Block in eine der anderen Listen frei ist. +
- +
-Falls die angeforderten Blockgrößen aussschliesslich Zweierpotenzen wären, würde es zu keiner Internen Fragmentierung kommen können. Da dies aber nie der Fall ist, wird viel Speicher durch interne Fragmentierung verschwendet.  +
- +
-==== Zusammenfassung Freispeicherverwaltung ==== +
-Bitmaps unterteilen den Speicher in **Allokationseinheiten**. Für jede Einheit gibt es ein Bit im Bitmap. Verknüpfte Listen bieten Suchmöglichkeiten mit First Fit, Best Fit oder Quick Fit. Quick Fit setzt mehrere Listen bestimmter Lochgößen voraus. Das Buddy System verwaltet n Listen von 1,2, 4, 8 bis zur Größe des Speichers. D.h. ein 1 MByte großer Speicher benötigt 21 Listen und hat Initial nur einen einzigen Eintrag in der letzten Liste, der das 1 MByte große Loch beschreibt. Alle anderen Listen sind leer. Speicher wird nun immer in Abhängigkeit von einer Potenz von 2 vergeben, der gerade noch groß genug ist, um die Daten aufzunehmen. Dies wird einfach implementiert, in dem der Große block einfach solange geteilt wird, bis der Datenblock in den Freispeicherblock passt. Das Buddysystem ist zwar schnell, aber impliziert eine **starke interne Fragmentation**, da ja immer auf Zweierpotenzen gerundet werden muss.  +
- +
->   * einfache verkettete Listen mit Best-,Next- oder First-Fit Suche  +
->   * Bitmap-System welches Speicher in gleichgroße Einheiten teilt  +
->   * Buddy-Listen nach dem binären System  +
->   * Beim passiven Warten werden Prozesse schlafengelegt  +
->   * Ereignisse dienen der Koordination  +
-> //Merktabelle: Methoden zur Freispeicherverwaltung// +
- +
-===== Wie arbeitet Segmentierung (mehrdimensionale Adressräume)? ===== +
-Eindimensionale Adressierung hat den Nachteil, daß Programme mit verschieden dynamisch wachsenden Programmteilen nur schlecht realisierbar sind. Code, Stack und Daten würden hintereinander im Speicher liegen. Benötigt ein Programm aber extrem viele Variablen, würde der Compiler mit der Fehlermeldung abbrechen, daß es nicht genug Speicher gäbe. Um nun mehrere Stack, Daten und Codebereiche getrennt voneinander adressieren zu können, ohne daß die verschiedenen Teile in Konflikt geraten, wurden die Segmente eingeführt. +
- +
-Segmentierte Speicherung wird oft als das Prinzip der **gestreuten Speicherung** benannt. Gestreut deshalb, weil die einzelnen Seiten nicht nacheinander im Speicher liegen müssen, sondern dort eingefügt werden, wo Platz ist. Anders als z.B. bei Kontinuierlicher Allokation, wo viel Speicher durch externe Fragmentierung verlorengeht, tritt bei Segmentation dieses Problem nicht auf. Dafür aber interne Fragmentierung...  +
- +
-==== Wie werden Segmenten adressiert? ==== +
-Um mit Segmenten arbeiten zu können, sind zweiteilige Adressen notwendig, bestehend aus **Segment** und **Offset**. Die Segmentation muss also dem Programmierer bewusst sein, da ein Segment nur eine logische Einheit darstellt. Besonders einfach gestaltet sich das übersetzen von Prozeduren. Angenommen jede Prozedur hat ihr eigenes Codesegment, benötigt man nur die Segmentnummer, um die Funktion aufzurufen, da der Eintrittspunkt bei der logischen Adresse 0 dieses Segmentes ist.\\ +
-Wird nun eine Prozedur neu kompiliert, müssen die restlichen Prozeduren nicht neu kompiliert werden, da der Eintrittspunkt immer noch der gleiche ist. Und zwar 0. Die Segmentnummern werden eh dynamisch vergeben.  +
- +
-==== Was versteht man unter gemeinsam genutzten Segmenten? ==== +
-Durch Segmentierung wird es sehr einfach, verschiedene Codesegmente gemeinsam zu nutzen. So genannte **Shared Libraries** sind in jedem modernen Betriebssystem notwendig, denn sie stellen für viele Programme Frameworks oder API's bereit, deren Funktionalität sich jedes Programm bedienen kann, soweit es die dafür notwendigen Zugriffsrechte hat. Ob ein Segment ausführbar ist oder nicht, wird über die Schutzart des Segmentes definiert.  +
- +
-===== Wie funktioniert das Prinzip des virtuellen Speichers durch Paging? ===== +
-Um mehr Speicher bereitzustellen werden statt echter physikalischer Adressen virtuelle benutzt, welche durch die MMU in reale Adressen bei Benutzung umgewandelt werden. Durch das Paging können Seiten aus- oder eingelagert (nach einem Page Fault) werden. Eine **Page Table** referenziert virtuelle auf physikalische Adressen. Swapping ist in Reinform sehr langsam. Sinnvollerweise werden Segmente in Seiten geteilt, welche durch Paging ein oder ausgelagert werden. (Protected Mode) Die MMU kann, muss aber nicht auf der CPU liegen. Jede Seitentabelleneintrag hat ein Present/Absent Bit, welches Auskunft darüber gibt, ob eine Seite sich im Speicher befindet oder nicht. Des Weiteren vermerkt eine Art **Dirty Bit**, ob eine Seite im Speicher geändert wurde, um entscheiden zu können, ob ein zurück schreiben notwendig wird. +
- +
-Die momentan verwendeten Seiten eines Programmablaufes wird **Working Set** genannt. Demand Paging bedeutet, dass Seiten erst dann abgefordert werden, wenn sie benötigt werden. +
- +
-Eine virtuelle Adresse besteht aus **Seitenummer und Offset**. Bei einem Contextswitch wird nach der entsprechenden Seitennummer in der Page Table gesucht und die zugehörige physikalische Adresse errechnet. Es wird meist ein n-stufiges Paging angewandt, um die Suche mach den Seiten zu beschleunigen (Unix) . Bei i386 gibt es ein so genanntes **Seitenverzeichnis** (DIR) mit 1024 Zeilen, welche wiederum je auf eine Seitentabelle verweisen. Somit enthält eine lineare Adresse beim Intel DIR,PAGE und OFFSET Teil. (mehrstufiges Paging) +
- +
-Beim Swapping werden statt Seiten ganze Prozesse ausgelagert.  +
- +
->   * Demand Paging und Caching basieren auf den gleichen Prinzip  +
->   * Sie arbeiten nur auf verschiedenen Ebenen  +
->   * Cache-Misses werden von der Hardware geregelt, Page Faults vom Betriebssystem  +
->   * Beim passiven Warten werden Prozesse schlafengelegt  +
->   * Ereignisse dienen der Koordination  +
-> //Merktabelle: Virtual Memory und Caching// +
- +
-==== Was ist der Translation Lookaside Buffer? ==== +
-Um die Zeit der Adressumrechnung zu vermindern, wird in der MMU ein **Assoziativspeicher** mit meist nicht mehr als 32 Einträgen verwaltet. Die Einträge enthalten die zuletzt verwendeten virtuellen Seiten mit der dazugehörigen Seitenrahmennummer im Speicher. Gleichzeitig wird dort vermerkt, welche Art von Lese/Schreibzugriff erlaubt ist und ob die Seite verändert wurde. Kommt eine Anforderung auf eine nicht im TLB vorhandene Seite, wird ein Eintrag aus dem TLB mit der neu dekodierten Adresse überschrieben, so daß bei der nächsten Anfrage die Adressumrechnung entfallen kann.  +
- +
->   * TLB's werden verwendet, wenn Seitentabelle auf Grund eines zu großen Adressraumes nicht möglich ist  +
->   * TLB bildet zuletzt genutzten (64 bei UltraSparc) virtuellen Seitennummern auf physikalische Seitenrahmen ab  +
->   * häufig benutzte Seiten werden in einem Cache (Translation Storage Buffer) verwaltet  +
->   * Dieser Cache bildet Seiten direkt ab und wird bei TLB-Miss zuerst untersucht  +
->   * befindet sich die Seite nicht im Cache, muss sie in der Translation Table gesucht werden +
-> //Merktabelle: Translation Lookaside Buffer// +
- +
-==== Was sind invertierte Page Tables? ==== +
-Eine Seitentabelle enthält hier einen Eintrag für jeden Seitenrahmen des physikalischen Speichers. Der Eintrag enthält Informationen über den besitzenden Prozess und die virtuelle Seite. So entspricht die Anzahl der Einträge der Anzahl der Seitenrahmen im Speicher. Die Tabelle verwaltet nur, welche Seite, von welchem Prozess in den Seitenrahmen des Arbeitsspeicher geladen wurden.  +
- +
-==== Was sind Paging Dämons? ==== +
-Paging arbeitet nur effizient, wenn jederzeit genügend Seitenrahmen im Speicher frei sind, um diese bei einem Page Fault neuen Seiten belegen zu können. Doch wie wird sichergestellt, daß der Speicher komplett ausgefüllt werden muss und somit bei einem Page Fault erst eine Seite ausgelagert werden muss? Viele Betriebssysteme haben dafür einen speziellen Dienst vorgesehen. Der Paging Dämon wird in zyklischen Abständen aktiviert. Dieser schaut nun nach ob genügend **Frames** im Speicher zur Verfügung stehen. Ist dies nicht der Fall, werden so viele Seiten wie notwendig mit einem der **Seitenersetzungsalgorithmen** aus dem Speicher entfernt und auf die Platte zurückgeschrieben.  +
- +
-==== Erklären Sie das Zusammenspiel von Segmentierung und Paging? ==== +
-Um beide Vorteile (Mehrdimensionalität und virtuellen Speicher) nutzen zu können, werden in fast allen modernen Betriebssystemen beide Techniken angewandt. Dabei wird das Paging **transparent**, also für den Programmierer nicht sichtbar, hinter die Segmentierung geschalten. Auf dieser Basis bauen sich auch die Adressen dieser Maschinen auf. Es gibt verschiedene Implementationen von Segmentierung und Paging. Aber letztendlich haben sie eines gemeinsam. Die logische Adresse besteht aus  +
-  - die Segmentnummer zur Auswahl des richtigen Segmentdeskriptors und  +
-  - den Offset zur Adressierung innerhalb des Segmentes.  +
-Die Implementierungen unterscheiden sich nun in der Verwaltung der **Deskriptoren** und der Art und Weise wie die aus Segment + Offset entstandene virtuelle Adresse über die Page Table auf den realen Speicher projiziert bzw. umgerechnet wird. +
- +
-{{http://www.kreissl.info/pics/images/bs_11.gif|Adressumsetzung}} +
- +
-==== Was passiert wenn Sie ein Programm starten? ==== +
-  * Der Virtual Memory Manager verwaltet den virtuellen Speicher.  +
-  * Bei Programmstart richtet das BS für den Prozess eine Seitentabelle ein.  +
-  * Eine definierte Anzahl Rahmen werden dem Prozess als Arbeitsmenge zugeteilt.  +
-  * Seiten aus dem Read-Only Bereich der EXE werden direkt geladen und brauchen nicht zurückgeschrieben werden.  +
-  * Read-Write Bereiche werden zuerst direkt aus der EXE geladen und im Speicher hinterlegt.  +
-  * Bei einem Schreib-Bezug wird sie als private Kopie in die Auslagerungsdatei geschrieben. So können mehrere Prozesse die selbe EXE im benutzen. (Copy On Write)  +
- +
-Der VMM von Windows verwaltet mehrere Listen für:  +
-  * freie Seiten, welche mit 0 initialisiert wurden (zerofilled)  +
-  * uninitialisierte freie Seiten, die noch alten Inhalt haben  +
-  * wartende Seiten, die Prozess zugewiesen waren und nicht modifiziert wurden(standby pages)  +
-  * wartende, aber modifizierte Seiten (modified pages)  +
-  * belegte Seiten, welchen einem Prozess zugewiesen / referenziert sind (valid pages)  +
-  * unbenutzbare Seiten, durch z.B. Hardwarefehler (unusable pages)  +
- +
-==== Wie arbeitet die Adressumrechnung der Multics? ==== +
-  - mit Segmentnummer wird Segmentdeskriptor festgestellt  +
-  - es wird geprüft, ob die Pagetable des Segmentes im Speicher ist  +
-  - ist sie nicht im Speicher tritt ein Segmentfehler auf und es erfolgt ein Trap  +
-  - ist sie im Speicher wird der Pagetableeintrag für die angefragte Seite überprüft  +
-  - falls Seite nicht im Speicher entsteht Page Fault  +
-  - ist Seite im Speicher wird die physikalische Adresse des Seitenursprungs aus dem Pagetableeintrag entnommen  +
-  - Der Offset wird zur gewonnenen Adresse hinzuaddiert und die physikalische Adresse ist berechnet.  +
-//(nach Tanenbaum)// +
- +
-Meist wird ein Assoziativspeicher verwendet, um die letzten paar Umrechnungen ohne Verzögerung ausgeben zu können. Ein TLB enthält zwei Vergleichsfelder für Segmentnummer und korrespondierende virtuelle Seite und einige zusätzliche Attribute, wie Schutzattribute, Age oder Referenziert-Bits.  +
- +
-==== Wie funktioniert die Adressumrechnung beim P2? ==== +
-Intel Prozessoren besitzen ab dem i386 eine **LDT** (local descriptor table) und eine **GDT** (global descriptor table). Die Local Descriptor Tables enthalten die programmeigenen Segmente, wie Stack-, Code- und Datensegment der verschiedenen Benutzerprogramme. Die Global Descriptor Table enthält dagegen die Systemsegmente samt deren des Betriebssystems , welche erst geladen werden muss. Wird ein Segmentselektor in ein Segmentregister geladen, wird der entsprechende Bezeichner aus der LDT oder GDT geholt und in MMU Registern gespeichert. Ob L- oder GDT kann dem Selektor entnommen werden, da dort ein Bit für diese Auswahl reserviert ist. Der Deskriptor besteht nun aus der Basisadresse des Segmentes, der Größe des Segmentes und verschiedenen Privilegbits. Es wird nun eine virtuelle Adresse über Segmenteselektor + Offset gebildet. Bei deaktiviertem Paging ist nun diese Adresse die lineare physikalische. Ist aber Paging aktiv wird die Adresse als virtuell interpretiert und über die Seitentabelle auf den realen Speicher abgebildet.  +
- +
-==== Was haben Deskriptoren mit Sicherheit und Segmentverwaltung zu tun? ==== +
-Jeder Deskriptor in einer Deskriptortabelle ist mehrere Byte breit und enthält Beschreibungsinformationen für ein Segment aus dem linearen Adressraum. Neben der Segment-Basisadresse (BASE) enthält er das LIMIT, das die Segmentgröße angibt. Dabei wird durch ein Granularitätsbit festgelegt, ob das LIMIT direkt als Länge interpretiert wird (Segmentgrößen bis 1 MB) oder mit dem Wert 4096 multipliziert wird und damit Segmentgrößen bis 4 GB unterstützt. Der Descriptor-Privilege-Level gibt an, mit welcher Berechtigungsstufe der Zugriff auf das Segment erfolgen muss:  +
-  * Level 0: Betriebssystem  +
-  * Level 1, 2: Betriebssystemdienste, Treiber, Systemsoftware  +
-  * Level 3: Anwendungssoftware  +
- +
-Weitere Informationen im Deskriptor zeigen an, ob auf das Segment lesend, schreibend oder ausführend zugegriffen werden darf und ob es sich um ein System- oder Anwendungssegment handelt. Ein Present-Bit gibt an, ob das Segment sich derzeit überhaupt im Hauptspeicher befindet.  +
- +
-===== Zusammenfassung von Freispeicherverwaltung, Segmentierung und Paging ===== +
-Segmentierung wird genutzt, um statt einen linearen Adressraum (wie beim virtuellen Speicher), mehrere virtuelle Adressräume nutzen zu können. Segmentierung wurde entworfen, um dynamisch wachsende Tabellen besser Handhaben zu können. Somit ist schafft Segmentierung einen mehrdimensionalen Adressraum. +
- +
-Unter Swapping versteht man das komplette Ein- und Auslagern von Prozessen. Das Swapping des segmentierten Speichers ist vergleichbar mit dem Demand-Paging des virtuellen Speichers. Nur das Segmente unterschiedlich groß sein können. Aus diesem Grund tritt hier das Problem der externen Fragmentierung auf. +
- +
-Um die externe Fragmentierung zu minimieren, werden die Löcher als verkettete Liste im Speicher gehalten. Falls ein Segment geladen werden soll, sucht z.B. Best Fit, dass nächst größere Loch unter allen, wo das Segment passen würde. First Fit nimmt das Nächste Loch, welches für das Segment groß genug wäre. +
- +
-Neben dem Swapping kann auch Paging zum Auslagern von Segmenten benutzt werden. Hierbei sind die auszulagernden Blöcke gleich groß, da die Segmente in gleich große Seiten eingeteilt werden. Zur Auslagerung wird das bekannte Demand Paging benutzt. Meist wird eine Kombination aus Segmentierung und Paging angewandt, bei der die Adresse aus zwei Teilen besteht. (Segmentnummer und Offset innerhalb des Segments). Segmente werden also in Seiten unterteilt. Zur Leistungsverbesserung werden die zuletzt verwendeten Segment-Seiten- Kombinationen in einem Assoziativspeicher (TLB) gehalten. Im Gegensatz zum Paging ist es beim reinen Swapping nicht möglich, Prozesse auszuführen, die alleine schon nicht in den Hauptspeicher passen. +
- +
-Bitmaps unterteilen den Speicher in Allokationseinheiten. Für jede Einheit gibt es ein Bit im Bitmap. Verknüpfte Listen bieten Suchmöglichkeiten mit First Fit, Best Fit oder Quick Fit. Quick Fit setzt mehrere Listen bestimmter Lochgößen voraus. Das Buddy System verwaltet n Listen von 1,2, 4, 8 bis zur Größe des Speichers. D.h. ein 1 MByte großer Speicher benötigt 21 Listen und hat Initial nur einen einzigen Eintrag in der letzten Liste, der das 1 MByte große Loch beschreibt. Alle anderen Listen sind leer. Speicher wird nun immer in Abhängigkeit von einer Potenz von 2 vergeben, der gerade noch groß genug ist, um die Daten aufzunehmen. Dies wird einfach implementiert, in dem der Große block einfach solange geteilt wird, bis der Datenblock in den Freispeicherblock passt. Das Buddysystem ist zwar schnell, aber impliziert eine starke interne Fragmentation, da ja immer auf Zweierpotenzen gerundet werden muss.  +
- +
- +
-====== Kapitel 7 - Seitenersetzung ====== +
- +
-  * Seitenersetzungsalgorithmen wie FiFo, LRU...  +
-  * Working Sets als dynamische Variante  +
-  * Problem der Seitengröße  +
- +
-===== Was sind Seitenersetzungsalgorithmen? ===== +
-Falls eine Seite angefordert wird, aber kein Platz für deren Einlagerung im Speicher mehr vorhanden ist, so muss eine andere Seite entfernt werden. Aber welche? Es gibt nun verschiedene Ansätze für dieses Problem...  +
- +
-==== Welcher wäre der beste Algorithmus zur Seitenersetzung? ==== +
-Dieser ist theoretisch gegeben, aber **nicht umsetzbar**. Die Seite die am **spätesten erst wieder verwendet** wird, wird ausgelagert. Da in einem Echtzeitsystem nie vorhersagbar ist, welcher Prozess wann wie lange aktiv sein wird, ist diese Strategie nicht umsetzbar... In einem deterministischen Modell wäre er aber durchaus denkbar, da dort jeder Schritt eindeutig definiert ist.  +
- +
-==== Wie arbeitet die Seitenersetzung mit Not-Recently-Used? ==== +
-Jede Seite bekommt zwei Statusbits zugeordnet. R wird gesetzt, wenn die Seite lesend oder schreibend referenziert wurde. M wird gesetzt, falls die Seite verändert wird. Diese beiden Bits sind in jedem Seitentabelleneintrag enthalten und müssen bei jeder Seitenreferenzierung aktualisiert werden.\\ +
-Die zwei Bit stellen vier Klassen dar, welche genutzt werden um einen Paging-Algorithmus zu realisieren.  +
-  - nicht referenzierte und nicht modifizierte Seite  +
-  - nicht referenzierte und modifizierte Seite  +
-  - referenzierte und nicht modifizierte Seite  +
-  - referenzierte und modifizierte Seite  +
-LRU wählt zufällig eine Seite aus der kleinstnummerierten Klasse zum Entfernen aus.  +
- +
-==== Wie arbeitet die Seitenersetzung mit Fifo - First In First Out? ==== +
-Es wird eine Liste geführt, welche alle Seiten enthält. Neue Seiten werden an das Ende der Liste angefügt. So ist die Liste nach dem **Alter der Seiten sortiert**. Der FiFo Paging-Algorithmus macht nichts weiter, als bei einem Seitenfehler die älteste Seite zu entfernen, also die Seite, die am Anfang der Liste steht. +
- +
-Das Problem an Fifo ist, daß auch extrem häufig referenzierte Seiten ausgelagert werden. Um dies zu umgehen wird das oben schon erwähnte R (Referenziert) Bit verwendet, um jeder Seite eine zweite Chance zu geben, falls das R-Bit nicht null ist.  +
- +
-==== Wie arbeitet die Seitenersetzung mit Second Chance? ==== +
-Arbeitet wie Fifo, nur wird beim Entfernen des Kopfes nachgeschaut, ob das R Bit null ist. Wurde die Seite nie referenziert, so wird sie entfernt, wie für FiFo üblich. Wurde sie aber referenziert, wird sie zum Ende der Liste verschoben, als wurde sie neu geladen. Das R-Bit wird dabei auf Null gesetzt. So wird gewährleistet, das häufig benutzte Seiten weniger oft als nicht referenzierte Seiten ausgelagert werden. Second Chance ist ein durchaus guter Paging Algorithmus mit einem Nachteil. Es müssen ständig konstante Seiten innerhalb der Liste von Anfang zum Ende verschoben werden. Diesen Nachteil bügelt der Uhr Algorithmus aus.  +
- +
-==== Wie arbeitet der Uhr-Seitenersetzungsalgorithmus? ==== +
-Der Clock-Algorithmus arbeitet im Prinzip wie Second Chance, nur das anstelle einer FiFo Liste eine **Ringliste** verwendet wird. Dabei wird in einem Pointer (Zeiger der Uhr) auf den aktuellen Anfang der Liste gezeigt. Bei einer Second Chance muss nun nicht die Seite verschoben werden, es wird einfach der Zeiger auf das nächste Element referenziert. +
- +
-Der Uhr Algorithmus ist also eine Implementation von Second Chance mit einer Ringliste.  +
- +
-==== Wie arbeitet die Seitenersetzung mit Least-Recently-Used? ==== +
-Dieser Paging Algorithmus versucht den Optimalen zu approximieren, indem es versucht die Seiten zu entfernen, welche am Längsten nicht mehr benutzt wurden. +
- +
-Die Implementation ist trotzdem nicht ganz einfach. Es müsste theoretisch eine Liste geführt werden, welche nach dem oben genannten Kriterium sortiert ist. Diese Liste müsste nach jeder Seiteneinlagerung neu Sortiert werden. Da dies eine zu komplexe Operation darstellt, muss dafür eine Softwarelösung approximiert werden, welche wesentlich schneller arbeitet.  +
- +
-==== Wie arbeitet die Seitenersetzung LRU mit Matrixumsetzung? ==== +
-Es wird eine globale N x N Matrix für alle N Seiten geführt. Diese Matrix wird mit 0 initialisiert. Wird eine Seite x referenziert, so wird die Zeile x auf 1 gesetzt und danach die Spalte x auf 0. In jedem Moment ist die Zeile deren Summe am Kleinsten ist, die am wenigsten genutzte und die Zeile mit dem größten Wert, die am häufigsten genutzte Seite. +
- +
-Wenn die notwendige Hardware (Matrix) nicht vorhanden ist, muss ein anderer effizienter Paging Algorithmus benutzt werden, der ohne jede Hardware auskommt.  +
- +
-==== Wie arbeitet die Seitenersetzung NFU - Not Frequently Used? ==== +
-Bei jeder Uhrunterbrechung wird das **Referenziert-Bit** jeder Seite auf einen Softwarezähler, welcher mit null initialisiert wurde, hinzuaddiert. Es wird also versucht **zu zählen**, wie oft eine Seite referenziert wird. Das Problem von NFU ist es, dass Spitzen in der Referenzierung starke Auswirkungen auf den Zähler haben. So kann es vorkommen, daß eine Seite, welche anfangs stark genutzt wurde und später nicht mehr, einer zyklisch genutzten Seite nicht zur Auslagerung vorgezogen wird. +
- +
-Eine Modifikation von NFU versucht LRU zu simulieren und diesen Fehler aufzuheben.  +
- +
-==== Wie arbeitet die Seitenersetzung mit Aging - LRU durch Softwareemulation? ==== +
-  - Vor der Addition es Referenziert-Bits werden alle Zähler um eins nach rechts geschoben +
-  - das Refenziert-Bit wird auf das am weitesten links stehende Bit addiert  +
-Bei einem Seitenfehler wird auch hier die Seite mit dem kleinsten Fehler entfernt. Durch das Rechtsverschieben verkleinert sich der Wert eines Zählers rapide und es wird verhindert, daß nur kurzeitig verwendete Seiten fälschlicherweiße als oft referenziert angesehen werden...  +
- +
->   * Not-Recently-Used (referenziert und modifiziert Bits - vier Zustände)  +
->   * Least-Recently-Used (Seiten die lange nicht benutzt worden auslagern) und LRU mit Matrixumsetzung  +
->   * FiFo, Second Chance, Uhr-Seitenersetzungsalgorithmus  +
->   * Aging - LRU durch Softwareemulation  +
->   * befindet sich die Seite nicht im Cache, muss sie in der Translation Table gesucht werden +
-> //Merktabelle: Seitenersetzungsalgorithmen// +
- +
-===== Was sagt die Belady's Anomalie? ===== +
-Eine Erhöhung der Seitenrahmen im Speicher, also mehr Speicher, heißt nicht zwangsläufig eine Verringerung von Seitenfehlern!  +
- +
-===== Was passiert beim Einsatz einer schnelleren Platte mit der Seitenfehlerrate? ===== +
-Die Seitenfehlerrate steigt, da die Übertragungszeit für Seiten sinkt. Die Anzahl der gleichzeitig ausführbaren Prozesse steigt, da jeder Prozeß nun mit weniger Seitenrahmen - und einer höheren Fehlerrate - "leben" kann.  +
- +
-===== Was sind Working Sets - dynamisches Seitenaustauschverfahren? ===== +
-Prozess Arbeitsbereiche werden eingesetzt und die Zahl der Seitenfehler weiter zu minimieren. Ein Prozess unterliegt auch einer Art **Lokalität**. Es werden im Mittel bestimmte Seiten häufiger und Andere sogut wie nie oder gar nicht zur Prozessabarbeitung benötigt. Man nennt dies **Referenzielle Lokalität**. +
- +
-Mit Arbeitsbereichen wird versucht Informationen vor dem Laden eines Prozesses auszunutzen, um häufig verwendete Referenzen bevorzugt zu behandeln. Die Erfassung der für das Working Set notwendigen Daten wird auch über eine Art Aging Algorithmus umgesetzt. Jede Seite gehört zu einem bestimmten Working Set. Wird eine Seite länger als N Ticks nicht mehr benutzt, wird sie aus dem Working Set entfernt. +
- +
-Die gewonnene Information des Working Sets kann verwendet werden, um den **Clock Algorithmus** zu verbessern. Und zwar wird nicht nur nach einer nichtreferenzierten Seite geschaut, sondern auch ob die Seite zu einem Working Set gehört oder nicht. Falls sie einem Arbeitsbereich angehört, wird sie **übersprungen**, egal ob im Moment referenziert oder nicht.  +
- +
-==== Welche Problematik tritt bei der Arbeitsmengenstrategie auf? ==== +
-Das Hauptproblem ist die Seitenauslagerung durch Herausfallen von Seiten aus dem Working Set. Seiten können aus dem Working Set ausgelagert werden, ohne das ein Seitenfehler vorliegt und ohne das für diese Seite eine Neue eingelagert wurde. Die aktuelle Lokalität wird eben nur approximiert. Die Arbeitsmenge enthält möglicherweise auch Seiten die nur einmal benutzt wurden. Der Übergang zu einer neuen Lokalität erfolgt nur allmählich.  +
- +
-===== Welche Gefahr besteht bei Seitenaustauschverfahren? ===== +
-Gefahr des **Seitenflatterns** (Trashing). Bei Überlastung mit zu vielen Prozessen die entweder zu viele Pagefaults produzieren und/oder zuwenig Seitenrahmen zur Verfügung haben, ist der Rechner weitgehend mit dem Ein-/und Auslagern von Seiten beschäftigt und kann an den eigentlichen Aufgaben der Prozesse kaum noch weiterarbeiten. Effektive CPU Auslastung sinkt durch viele Seitenfehler. Weitere Gefahr besteht dann durch zu einfach konstruierte Scheduler, die bei sinkender CPU-Auslastung mit einer höheren Prozessintensität reagieren. **Page Damons** können dem Abhilfe schaffen, weil sie Prozesse auslagern, wenn nicht mehr ausreichend Seitenrahmen im Speicher zur Verfügung stehen.  +
- +
-==== Was kann man gegen Trashing (Seitenflattern) tun? ==== +
-Page Dämons benutzten, denn dadurch wird die Anzahl der gleichzeitig aktiven Prozesse verringert und jedem Prozeß stehen mehr Seitenrahmen zur Verfügung.  +
- +
-===== Wie wird die Seitengröße festgelegt? ===== +
-Die Seitengröße ist normalerweise klein. Dies hat verschiedene Gründe sie klein zu halten, aber auch einen wichtigen Grund, die Größe nicht zu klein zu definieren. Im Mittel ist die letzte Seite eines Codestückes nur **halb gefüllt**, da logischerweise nicht jedes Code, Stack oder Datensegment genau in eine Seite passen kann oder sich so auf mehrere verteilt, daß kein freier Speicher mehr verbleibt. Des Weiteren muss beachtet werden, dass es auch viele kleine Segment gibt. Angenommen man legt eine Seitengröße von 32 KB fest, so werden bei 4 KB großen Segmenten stets 28 KB verschwendet. Andersherum benötigt man mit kleinen Seiten eine größere Seitentabelle, deren Anzahl proportional zur Seitengröße ist. Des Weiteren muss man einkalkulieren, daß das Einladen einer Seite von Platte eine langwierige Operation ist. Es ist trivial das das Einlagern von vier 8K-Seiten schneller ist, als das Einlagern von 64 512 Byte großen Seiten. Es muss also ein Mittelweg gefunden werden, welcher einen optimalen Nutzen aus den oben genannten Kriterien zieht. +
- +
-Verschwendung = Prozessgröße * Seitentabelleneintragsgöße / Seitengröße + Seitengröße / 2 +
- +
-//Die Nullstellenberechnung der ersten Ableitung in Abhängigkeit der Seitengröße ergibt :// +
- +
-**Optimale Seitengröße** = Wurzel aus 2 * Prozessgröße * Seitentabelleneintragsgöße  +
- +
- +
-====== Kapitel 8 - Deadlocks ====== +
- +
-  * notwendige und hinreichende Bedingung  +
-  * Deadlock-Erkennung und Vermeidung  +
-  * Bankieralgorithmus  +
- +
-===== Was sind die notwendigen Bedingungen für Deadlocks? ===== +
-  - **Mutual Exclusion** (z.B. via Druckerspooler über Ersatz-BM Buffer aufgelöst)  +
-  - **Belegungs- und Wartebedingung** (Prozess kann weitere BM anfordern)  +
-  - **Unterbrechbarkeitsbedingung** (BM können nicht entzogen werden)  +
-  - **zyklische Wartebedingung** (Zyklus im Betriebsmittelgraph)  +
- +
-===== Was sind die hinreichende Bedingungen für Deadlocks? ===== +
-Es darf keine externe Betriebsmittelinstanz bestehen.  +
- +
-===== Was ist ein Livelock? ===== +
-Es wurde ein Betriebsmittel vergeben, es besteht aber keine Verhinderung. Das BM könnte irgendwann wieder freigegeben werden, aber der Zeitpunkt unbekannt. +
- +
-Z.B. **Priotitätsscheduling** (langwierige Prozesse verhungern da benachteiligt)  +
- +
-===== Wie kann man Deadlocks auflösen oder umgehen? ===== +
-  - Vogel-Strauß Algorithmus (einfach Ignorieren)  +
-  - Versuchen zu Erkennen und zu beheben (Topologische Sortierung des BM-Graphs oder Vektoren-Matrix Variante)  +
-  - dynamisches Verhindern (vor Zuteilung auf Deadlock prüfen)  +
-  - konzeptionelles Vermeiden (eine der notwendigen Bedingungen eliminieren)  +
- +
-==== Welche Prozesse sind an einem Deadlock beteiligt? ==== +
-Prozesse die mehrere Betriebsmittel mit jeweils **exklusiven Zugriff** benötigen.  +
- +
-==== Wie kann man Deadlocks (im Voraus) erkennen? ==== +
-Die zur Ausführung eines Prozesses notwendigen Betriebsmittel müssten vor Ausführung bekannt sein. Das ist aber in einem offenen System nicht möglich. Das Prinzip ist das gleiche wie das **Preclaiming** im DBMS. Erst wenn alle angeforderten Betriebsmittel verfügbar sind, führt der Prozess den nächsten Schritt aus. Algorithmisch wäre dies durch zyklische Prüfung (für jeden Prozeß) auf Vorhandensein der erforderlichen Betriebsmittel erreichbar.  +
- +
-==== Wie werden Deadlocks beseitigt? ==== +
-Durch **Abbruch** der beteiligten Prozesse und Freigabe der belegten Betriebsmittel. Siehe **optimistische Sperrverfahren** bei DBMS.  +
- +
-===== Wie können Deadlocks vermieden werden? ===== +
- +
-**Möglichkeit 1** +
- +
-Es müsste bei jeder Betriebsmittelanforderung geprüft werden, ob diese zu einem Deadlock führen würde. Da dies sehr aufwendig ist, wird so nicht verfahren. +
- +
-**Möglichkeit 2:** +
- +
-Bei Anforderung zusätzlicher Betriebsmittel werden alle bisher reservierten Betriebsmittel freigegeben und dann zusammen mit den zusätzlichen Betriebsmitteln erneut angefordert (Form von Preclaiming). +
- +
-**Möglichkeit 3** +
- +
-Betriebsmitteltypen werden linear nach Priorität angefordert . Falls schon Betriebsmittel reserviert sind, können keine Betriebsmittel, die wichtiger sind als die schon reservierten, angefordert werden. Damit wird zyklisches Warten unmöglich (ähnelt dem 2-Phasen-Sperrprotokoll). Problem ist aber die Vergabe geeigneter Nummerierungen, da reale und abstrakte Betriebsmittel (z.B. Spoolbereiche auf Festplatten) sich nur schwer Ordnen lassen. +
- +
-**Möglichkeit 4**  +
- +
-Der Banker Algorithmus als Verfahren zur Erkennung sicherer Systemzustände bei der Verteilung von Ressourcen.  +
- +
-==== Wie arbeitet der Bankieralgorithmus? ==== +
-Ein Banker hat einen bestimmte Menge einer Ressource. Jeder Kunde hat ein Limit, bis zu dem er Ressourcen vom Banker erhalten kann. Der Banker hat aber so viele Ressourcen, daß er das größte vorhandene Limit gerade noch bedienen kann. Der Kunde bekommt die Ressource, falls der Banker danach noch genügend Ressourcen hat, um mindestens einem der Kunden sein komplettes Limit zuteilen zu können. +
- +
-**Beispiel Bankieralgorithmus** +
- +
-Der Banker habe 10 Einheiten eines Betriebsmittels verfügbar.  +
-  - Das Limit von Kunde A betrage 8 Einheiten.  +
-  - Das Limit von Kunde B ist 7 Einheiten.  +
-  - A hat zur Zeit 5 Einheiten belegt  +
-  - und B hat 2 Einheiten reserviert  +
-Falls B nun eine weitere Einheit anfordert, so muss dies verweigert werden, da dann der Banker nur noch 2 Einheiten übrig hätte, diese aber nicht zur Befriedigung einer kompletten Reservierung von A oder B ausreichen würde und zu einem Deadlock führen würde. Solch ein Zustand heißt unsicherer Zustand. Der Problem ist nun, daß jeder Prozeß muß im Voraus wissen muss, wieviele Einheiten eines Betriebsmittels er maximal während seiner Abarbeitung benötigen wird.  +
- +
-==== Warum funktioniert die Deadlock-Vermeidung bei linearer Ordnung der Betriebsmittel? ==== +
-Prozesse können zwar alle Betriebsmittel anfordern, aber alle Anforderungen müssen gemäß der Nummerierungsreihenfolge geschehen. Somit ist es von vornherein ausgeschlossen, daß ein Prozeß der ein Betriebsmittel höherer Ordnung besitzt, ein Betriebsmittel niedrigerer Ordnung, das von einem anderen Prozeß belegt ist, anfordern kann. Also werden Schlingen im Wartegraph und damit Deadlocks vermieden, da nun eine notwendige Voraussetzung für Deadlocks eliminiert wurde. Umgesetzt kann das Ganze durch eine Nummerierung der Betriebsmittel werden. Das Prinzip ähnelt dem Zeitstempelverfahren bei DBMS.  +
- +
- +
-====== Kapitel 9 - Dateisysteme ====== +
- +
-  * Freispeicherverwaltung  +
-  * Verschiedene Dateisysteme wie NTFS  +
-  * Dateideskriptoren  +
-  * Was sind I-Nodes?  +
- +
-Hier geht es im Besonderem um Verwaltung, Zugriffsoptimierung und die Umsetzung einer für den Menschen vereinfacht nutzbaren Abstraktion. Der Zugriff auf Daten erfolgt nicht wie beim Hauptspeicher Byte-orientiert, sondern aus Effizienzgründen blockweise, da Platten um ein vielfaches langsamer als Arbeitspeicher sind. Des Weiteren sind bis auf einige Ausnahmen, wie CD ISO9660, die meisten Dateisysteme Betriebssystemspezifisch.  +
- +
-===== Was ist eine Datei? ===== +
-Eine Datei ist ein logisches Betriebsmittel, welches eine endliche Menge zusammengehöriger Daten beinhaltet. Verzeichnisse sind spezielle Dateien, welche zur Strukturierung von Dateisystemen eingeführt wurden.  +
- +
-===== Welche Möglichkeiten der Freispeicherverwaltung von File Systemem gibt es? ===== +
-  - Kontinuierliche Allokation - schlecht wenn Datum angehangen soll  +
-  - Verkettete Listen - schlecht, da Wahlfreier Zugriff extrem langsam  +
-  - Listen mit Zuordnungstabellen - Zuordnungstabellen erlauben schnellen wahlfreien Zugriff (FAT)  +
-  - Indizierte Speicherung  +
-  - Indirekt indizierte Speicherung  +
-Ein leeres Dateisystem wird als lineares Medium betrachtet und nach und nach linear aufgefüllt. Vorteil dieser Variante ist schneller Zugriff. Nachteil ist die extreme externe Fragmentierung bei Änderungen von Dateigrößen.  +
- +
-==== Wie funktioniert das Prinzip der Verketteten Listen? ==== +
-Listen sind langsamer als kontinuierliche Allokation, bieten nur wahlfreien Zugriff und besitzen nur geringe Fehlertoleranz. Dafür werden aber nur sehr **wenig Verwaltungsdaten** benötigt. (Hier nur Pointer auf den nächsten belegten Block) Eine Verbesserung der Effizienz wird durch das Nutzen doppelt verketteter Listen erzielt, wobei sich aber auch der Zahl der Verwaltungsdaten verdoppelt.  +
- +
-==== Wie funktioniert das Prinzip der Listen mit Zuordnungstabellen ==== +
-Hier werden die Nutzdaten von den Zeigern in eine extra Tabelle ausgelagert. Die Dateizuordnungstabelle am Bsp. FAT enthält für jeden Block einen Eintrag mit einem Verweis auf den Folgeblock oder einen bestimmten Eintrag für EOF. Die Effizient wird hier bei großen Tabellen eingeschränkt.  +
- +
-==== Wie funktioniert indizierte Speicherung ==== +
-Für jede Datei wird hier die Startadresse und die Indexlänge gemerkt. So ist zwar schneller wahlfreier Zugriff möglich, aber es herrscht das gleiche Problem der externe Fragmentierung wie bei kontinuierlicher Allokation. Die Geschwindigkeitssteigerung gegenüber Zuordnungstabellen kommt daher, dass Zusammenhängende Blöcke in Zuordnungstabellen nicht hintereinander liegen, sondern verstreut in der Tabelle. Die indizierte Speicherung führt sogenannte Indexblöcke ein, in welche hintereinander die zur Datei gehörigen Blocknummern eingetragen werden. So muss bei einem Zugriff im Worst Case nicht die ganze Zuordnungstabelle nach den Blocknummern durchsucht werden. +
- +
-Wie groß sollte nun aber so ein Indexblock gewählt werden? Variable längen sind schlecht realisierbar. Wählt man sie zu groß, geht Speicher durch interne Fragmentierung verloren. Wählt man sie zu klein, beschränkt man die Dateigröße... Deshalb wurde die indirekt indizierte Speicherung eingeführt.  +
- +
-==== Wie funktioniert indirekt indizierte Speicherung ==== +
-Ein Eintrag im Verwaltungsblock (Indexblock) zeigt wieder auf einen oder mehrere Blöcke, die nun die Verweise auf die wirklichen Datenblöcke enthalten, oder wiederrum auf weitere Indexblöcke. (Dreifach Indirekt) So ist auch auf große Dateien der Zugriff gewährleistet.  +
- +
-==== Was ist das Besondere an Unix FS Ext 2? ==== +
-Es werden Inodes für den Zugriff auf Datenblöcke verwendet. Die Dateinamen werden in einer extra Tabelle verwaltet, welche die Attribute (Eigentümer, Zeiten, Größe) und 12 direkte Zeiger auf Blockadressen (einfach, doppelt, dreifach indirekt) enthält.  +
- +
-===== Welche Festplatten Scheduling-Algorithmen kennen Sie? ===== +
-  * First Come First Serve  +
-  * Shortest Seek Time First (Sektor mit kürzesten Suchzeit suchen)  +
-  * Scan (Diskarm bewegt sich von einem Ende zum Anderen und bearbeitet Requests)  +
-  * C-Scan (Diskarm wird bei Erreichen des Endes wieder auf Anfang zurückgesetzt - kreisförmig)  +
-  * Look (Wie C-Scan, nur wird nur so weit wie notwendig zurückgesetzt)  +
-  * Look (Wie C-Look, nur kreisförmig)  +
- +
-==== Welche Bewertungskriterien für Festplattenalgorithmen gibt es? ==== +
-  * Caching  +
-  * Demand Paging wichtiger als E/A der Anwendungen  +
-  * Robustheit nach Systemabstürzen  +
-  * Berücksichtigung der hohen Rotationsgeschwindigkeiten moderner Platten  +
-  * Verzeichnisse und Indexblöcke sollten in mittleren statt äußeren oder inneren Zylindern sein, da dort die mittlere Zugriffszeit am kleinsten ist (im Durchschnitt befindet sich der Lesekopf in der Mitte)  +
- +
-===== Wie arbeitet FAT - File Allocation Table? ===== +
-Die FAT Dateizuordnungstabelle liegt auf den ersten Spuren einer Platte. Sie wird aus Sicherheitsgründen oft gesichert. Alle Blöcke einer Platte sind über die FAT miteinander verkettet (**abgesetzte verkettete Allokation**). Die Größe einer Zuordnungseinheit ist für eine Partition statisch, kann sich aber zwischen den Partitionen unterscheiden (üblich sind 512, 1024 oder 4096 Bytes). FAT bietet weder Schutzmechanismen, noch unterstützt es lange Dateinamen (erst ab VFAT).  +
- +
-==== Welche Verzeichniseinträge hat FAT? ==== +
-  * Dateiname (8+3 Zeichen)  +
-  * Attribut-Byte  +
-  * Zeit und Datum der letzten Bearbeitung  +
-  * Erste Zuordnungseinheit der Datei  +
-  * Dateilänge  +
-Das Dateisystem assoziiert eine Baumstruktur. Für jede Datei enthält die Dateizuordnungstabelle eine lineare, gezeigerte Liste, mit der die Blöcke der Datei bzw. des Unterverzeichnisses bestimmt werden können. Der Index der Tabelleneinträge stellt die Blocknummer der Festplatte dar.  +
- +
-===== Wie arbeitet NTFS? ===== +
-NTFS heißt New Technology File System. NTFS ist mit einem **Zugriffsschutz** ausgestattet und hat auch keine Größenbegrenzung mehr. Ein Logfile wird verwendet, um nach einem Systemausfall Daten rekonstruieren zu können. NTFS besitzt nur Dateien. Analog zu den I-Nodes beim Unix gibt es beim NTFS eine **Master File Table**, in welcher jede Datei einen Eintrag besitzt. Zusammenhängende Bereiche (extents) werden als **B-Baum** organisiert.  +
- +
-==== Was ist die MFT von NTFS? ==== +
-Bei kleinen Dateien bzw. Verzeichnissen werden alle Attribute (incl. der Daten) innerhalb des MFT-Eintrages abgelegt (bis zu 1 bis 4 KB). Ein Eintrag in der MFT benötigt einen oder mehrere Sätze der MFT (Satzlänge ist konfigurierbar). Bei großen Dateien enthält der MFT-Eintrag den Wurzelknoten eines **B-Baums**, dessen "Blätter" die Verweise auf die zusammenhängenden Dateibereiche (Extent oder Lauf) enthalten. +
- +
-Ähnlich wie die Inode-Tabelle beim UNIX-System stellt die MFT ein flaches Dateisystem dar. Über die Verzeichnisse wird darauf die bekannte Baumstruktur definiert.  +
- +
-==== Wie werden unter NTFS Dateien eindeutig identifiziert? ==== +
-Jede Datei ist eindeutig über eine **ID** identifizierbar. Diese ID ist die Satznummer ihres Eintrages in der **MasterFileTable** (48 Bit). Zusätzlich wird eine Folgenummer (16 Bit) angehängt, die bei jedem Bezug auf den MFT-Eintrag (z.B. beim Öffnen der Datei) um 1 erhöht wird (für Konsistenzüberprüfungen)  +
- +
-==== Wie werden unter NTFS Verzeichnisse umgesetzt? ==== +
-Ein Verzeichniseintrag besteht aus dem Dateinamen, der ID-Nummer der Datei bzw. des Unterverzeichnisses, einer Kopie der Update-Zeit und der Dateilänge aus dem MFT-Eintrag. Verzeichnisse werden nicht wie bei FAT in einer linearen Liste verwaltet, sondern als **B-Baum**.  +
- +
-==== Welche Spezialdateien hat NTFS? ==== +
-  * MasterFileTable (MFT)  +
-  * MFT2: enthält die ersten 16 Einträge der MFT als Backup  +
-  * Eine Logdatei (Daten über Transaktionen zum Wiederherstellen der Daten- bzw. der Dateisystemkonsistenz)  +
-  * Datenträgerdatei enthält den Namen des Datenträgers, Versionsnummer des Dateisystems und eventuellen Verdacht auf Inkonsistenz  +
-  * Wurzelverzeichnis  +
-  * Cluster-Bitmap-Datei für belegte und freie Cluster des Datenträgers  +
-  * Bootdatei mit dem Startcode für NT  +
-  * BadClusterDatei, welche Verweise auf defekte Cluster enthält  +
- +
-===== Wie arbeiten I-Nodes - Das Unix Dateisystem ===== +
-Die ersten Adressen von Plattenblöcken sind in dem I-Node gespeichert. Diese Adressen reichen aber nur für kleine Dateien aus. Für größere Dateien, welche nicht durch ein I-Node adressierbar sind, gibt es Adressen in dem I-Node, die die Adresse eines Plattenblockes enthalten, welcher weitere Plattenadressen enthält. Dieser Block wird "**einfach indirekter Block**" genannt. "Einfach indirekte" Blöcke verweisen auf Blöcke, die ihrerseits eine Reihe von direkten Blocknummern enthalten. Beim Zugriff auf Daten über einen indirekten Block muß der Kern zuerst diesen indirekten Block lesen, den passenden direkten Blockeintrag ermitteln und dann diesen Block lesen. Es gibt auch Adressen, die auf Blöcke zeigen, die die Adressen von einfach indirekten Blöcken enthalten. Solche "doppelt indirekten" Blöcke enthalten eine Liste indirekter Blocknummern. Blöcke mit dem Kennzeichen "dreifach indirekt" enthalten eine Liste von doppelt indirekten Blocknummern u.s.w.+
  
 {{http://www.kreissl.info/pics/images/bs_03.gif|I-Nodes}} {{http://www.kreissl.info/pics/images/bs_03.gif|I-Nodes}}
  
-===== Was sind Dateideskriptoren? ===== +**Windows (NTFS):** 
-Jedem Prozess ist eine eigene Benutzer-Filedecriptor-Tabelle zugeordnet. Ruft ein Prozess //open// oder //create// holt der Systemkern einen freien Inode aus der Inode-Tabelle und übergibt diesen an die globale Dateitabelle und erzeugt einen Eintrag in der Benutzer-Filedecriptor-Tabelle. +NTFS nutzt eine **Master File Table (MFT)**.  
 +  * Jede Datei besitzt hier einen Eintrag.  
 +  * Bei kleinen Dateien werden alle Attribute (inklusive der Daten) direkt innerhalb des MFT-Eintrags abgelegt.  
 +  * Bei großen Dateien enthält der Eintrag den Wurzelknoten eines B-Baums, dessen Blätter auf die Dateibereiche (Extents) verweisen.
  
-==== Was enthält die globale Dateitabelle des Systems? ==== +Um Dateien von mehreren Orten zugänglich zu machen, nutzt man **Links**. Das "symbolic linking" legt eine spezielle Datei an, die den absoluten Pfadnamen der gelinkten Datei enthält.
-Den Offset in Byte zum Dateianfang für den nächsten //read-// bzw. //write-Befehl// des Benutzers und die **Zugriffsberechtigungen** für den Prozeß, der die Datei eröffnet hat. Die Benutzer-Filedecriptor-Tabellen enthalten dagegen nur die geöffneten Dateien eines Prozesses.+
  
-{{http://www.kreissl.info/pics/images/bs_04.gif|Dateideskriptoren}}+==== Modul 7: Linux, GNU und die Open-Source-Galaxis (Tag 7) ==== 
 +Historisch stammt Unix aus den 1960er Jahren, hervorgegangen aus dem System Multics. Ken Thompson und Dennis Ritchie entwickelten die erste Unix-Version und schufen dafür die Sprache C. 
  
-==== Was beinhaltet ein I-Node? ==== +1991 initiierte Linus Torvalds den Kernel für Linux. Ein Großteil der grundlegenden Software in Linux (wie C-Compiler oder Shells) stammt aus dem GNU-Projekt.  
-  * Dateityp  +**Systemvergleich:** 
-  * Eigentümer  +  * **Linux:** Extrem ressourcenschonend (eine GUI ist optional), sehr sicheres Multiusersystem, extrem konfigurierbar. Alle Sourcen sind frei verfügbar. 
-  * Gruppe des Eigentümers  +  * **macOS X:** Basiert auf einem Unix-Derivat (Darwin/Mach), glänzt durch Hardwarebindung und Multimedia-Integration. 
-  * Zugriffsschutzbits  +  * **Windows:** Gigantische Verbreitung und riesige Software-Auswahl. Es ist stark von Microsoft getrieben, anfälliger für Viren und oft schwieriger in tiefen Kernelsystemen zu debuggen.
-  * Datumseinträge  +
-  * Anzahl der Links für diesen I-Node  +
-  * Zeiger auf den Dateiinhalt +
  
-===== Geräte als I/O Dateien ===== +==== Modul 8: Verteilte Systeme & Cluster (Tag 8) ==== 
-Es gibt zwei Klassen solcher Dateien. Blockorientierte Spezialdateien und Zeichenorientierte Spezialdateien. +Ein verteiltes System ist laut Andrew Tanenbaum ein Zusammenschluss unabhängiger Computer, der sich für den Benutzer als ein einzelnes System präsentiert. 
 +Die bekannteste Architektur ist das **Client-Server-Modell**, bei dem der Client eine Aufgabe (z. B. Datenbankabfrage) anfordert und der Server diese bereitstellt.
  
-==== Was sind Blockorientierte Spezialdateien? ==== +Noch spannender sind **Cluster**, die vernetzte Computer zu einem mächtigen Gebilde vereinen. Es gibt primär diese Typen: 
-Blockorientierte Spezialdateien werden benutzt, um Geräte zu modellieren, die aus frei adressierbaren Blöcken bestehen. ( **random access devices** wie Festplatten). Wird eine blockorientierte Spezialdatei geöffnet, so kann ein Block gelesen werden, ohne daß man sich um die Struktur des Dateisystems, das dies ermöglicht, kümmern zu müssen. +  * **HA Cluster (High Availability):** Ein Knoten ist aktiv, der andere passiv. Sie tauschen "Heartbeat"-Signale aus. Fällt der aktive Knoten aus, übernimmt der passive. Um den gefährlichen "Split-Brain"-Zustand zu verhindern, schießt der passive Knoten den defekten Partner vor der Übernahme über STONITH (Shoot The Other Node In The Head) hardwareseitig ab. 
 +  * **HPC Cluster (High Performance Computing):** Hier werden Jobs durch ein Decomposition-Programm in kleine Teile zerlegt und parallel auf mehreren Rechenknoten ausgeführt. Die Kommunikation erfolgt meist via MPI (Message Passing Interface). 
 +  * **Load Balancing Cluster:** Clientanfragen werden durch einen Loadbalancer an den Serverknoten mit der voraussichtlich besten Performance verteilt.
  
-==== Was sind Zeichenorientierte Spezialdateien? ==== +==== Modul 9: Grid & Cloud Computing (Tag 9) ==== 
-werden benutzt, um Geräte zu modellieren, die aus **Zeichenströmen** bestehen. Beispiele hierfür sind Terminals, Drucker, Netzschnittstellen. Ein Programm schreibt auf das entsprechende I/O-Gerät, indem es in die korrespondierende zeichenorientierte Spezialdatei schreibt. Analoges gilt für das Lesen. +Wenn der lokale Rechner nicht reicht, wandern wir ins Netz. 
 +**Grid Computing** vernetzt Tausende einzelner Computer zu einem komplexen System mit enormer Rechenleistung. Es gibt z. B. Computer Grids für Rechenkapazität, Data Grids für große verteilte Datenmengen und Application Grids zur Bereitstellung von Software über virtuelle Organisationen.
  
-===== Wie ist das Unix Dateisystems aufgebaut? ===== +**Cloud Computing** treibt dies auf die Spitze. Dienste werden On-Demand abgerechnet ("pay per use"). Wir unterscheiden: 
-{{http://www.kreissl.info/pics/images/bs_05.gif|Unix}}+  * **IaaS (Infrastructure as a Service):** Der Anbieter stellt Speicherplatz, Server und Rechenkapazität bereit. 
 +  * **PaaS (Platform as a Service):** Bereitstellung einer transparenten Entwicklungsumgebung (z.B. Webserver) zum Testen und Hosten von Apps. 
 +  * **SaaS (Software as a Service):** Der Anbieter hostet eine vollständige Software-Applikation; der Anwender benötigt nur noch einen Web-Browser.
  
-Der Bootblock ist meistens im ersten Sektor einer Partition. Er enthält den Bootstrap-Code, der beim Hochfahren eines UNIX-Rechners in den Speicher gelesen wird. Er lädt bzw. initialisiert das Betriebssystem.+Die Bereitstellung erfolgt über **Private Clouds** (nur für interne Unternehmenszwecke), **Public Clouds** (öffentlich verfügbar) oder als **Hybrid Cloud**.
  
-Der **Superblock** beschreibt den **Aufbau des Dateisystems**. Eine Kopie des Superblocks befindet sich permanent im Speicher. Der Kern schreibt periodisch den Superblock auf die Platte zurück, so daß er immer mit den aktuellen Daten im Dateisystem übereinstimmt. Der Superblock enthält folgende Felder:  +==== Modul 10: Embedded Systems & Organic Computing (Tag 10) ==== 
-  * Größe des Dateisystems  +Betriebssysteme der Zukunft steuern nicht nur Desktop-PCs.  
-  * Anzahl der freien Blöcke  +**Embedded Systems** verrichten unsichtbar ihren Dienst in Waschmaschinen, Autos oder DVD-Playern. Eines der ersten war der Apollo Guidance Computer für die Mondlandung. Die Elektronik besteht meist aus Mikroprozessoren (wie ARM oder PowerPC) und hochspezialisierten Betriebssystemen wie QNX, VxWorks oder Embedded Linux.
-  * Liste der freien Blöcke  +
-  * Index auf den nächsten freien Block  +
-  * Größe der I-Nodeliste  +
-  * Anzahl der freien Inodes im Dateisystem  +
-  * Liste der freien Inodes  +
-  * Index auf den nächsten freien Inode in dieser Liste  +
-  * Sperrkennzeichen für die Listen freier Blöcke und Inodes  +
-  * Flag für durchgeführte Änderungen im Superblock +
  
-===== Wie kann ein Prozeß auf Daten auf der Festplatte zugreifen? ===== +Die absolute Spitze der Evolution bildet das **Organic Computing**. Systeme werden künftig so komplex, dass sie lebensähnlich ("organisch") reagieren müssen. Sie benötigen "self-x" Eigenschaften: 
-  - Das virtuelle Gerät hinter dem die Festplatte verborgen wird, heißt Datei.  +  * **selbst-konfigurierend** 
-  - Der Prozeß öffnet die Datei und erhält eine Datei-ID die auf eine Datei-Deskriptor-Tabelle verweist.  +  * **selbst-optimierend** 
-  - Es folgt die Adressierung der Sektoren.  +  * **selbst-heilend** 
-  - Über die Sektoradresstabelle (FAT oder I-Node Tabelle) werden die Adressen der Blöcke ermittelt  +  * **selbst-schützend**
-  - Es folgt die Übertragung der Blöcke zum Hauptspeicher  +
-  - Zugriff erfolgt nach speziellem Prinzip, wie z.B. SSN  +
-  - zur Minimierung der Suchzeit muss Wahl einer effizienten Positionierungsstrategie  +
-  - Durch einen Interrupt oder ein spezielles Register teilt der Controller dem BS das Ende der Übertragung mit.  +
- +
-==== Wie wird eine Datei unter Unix gesucht? ==== +
-Linux identifiziert Dateien indirekt über den absoluten Pfadnamen, indem es durch diesen den dazugehörigen I-Node sucht. Jede Datei wird durch einen oder mehrere I-Nodes beschrieben. Die I-Nodes enthalten die Blockadressen der Datei. Ein Katalog (Verzeichnis) enthält alle im Verzeichnis enthaltenen Datei- bzw. Verzeichnisnamen und die dazugehörigen I-Nodes. +
- +
-**Beispielzugriff:**  +
-  - Es soll die Datei ///var/log/messages// betrachtet werden  +
-  - Der I-Node des Wurzelverzeichnisses **"/"** steht an einer definierten Stelle auf der Platte  +
-  - Es wird das Verzeichnis **"var"** im Wurzelkatalog (auch eine Datei) gesucht  +
-  - In diesem Katalog steht der dazugehörige **I-Node** der auf das Verzeichnis bzw. den Katalog "var" verweist  +
-  - nun wird in der Katalogdatei "var" nach **"log"** gesucht und der dazugehörige **I-Node** gelesen  +
-  - Nun kann über den I-Node nach dem Eintrag **"messages"** in "log" gesucht werden  +
-  - Der I-Node der Datei "messages" wird nun in die globale **Dateideskriptortabelle** und die lokale Deskriptortabelle des Prozesses geladen  +
-  - Dieser Dateideskriptor ist das **Handle**, mit dem der Prozess auf die Datei zugreifen kann  +
-  - Nach eine **Close()** wird der I-Node aus der Dateideskriptorliste wieder entfernt. +
  
 +Ein "Smart Network" wird sich spontan vernetzen, Ausfälle erkennen und Aufgaben bei Überlastung autonom neu verteilen. 
  
 ---- ----
- +//**Quellen & Materialien**//\\ 
-//**Quellen**//\\ +//Alle Inhalte dieses Kurses basieren auf dem Skript "Betriebssysteme" der German-Baltic Management School. Zusätzliche Anreicherungen und Strukturierung durch den Kursleiter.//
-//Andrew S. Tanenbaum, Computerarchitektur//\\ +
-//Andrew S. Tanenbaum, Moderne Betriebssysteme//\\ +
-//Petterson, Computer Architectur & Design//\\ +
-//Christian Märtin, Rechnerarchitekturen//\\ +
-//Kalfa, Skript und Vorlesung//\\ +
-//Word Wide Web, Verschiedenste Seiten// +
- +
-Ausgearbeitet von Holger Kreissl. Online link http://www.kreissl.info/diggs/bs_inhalt.php+