Script Betriebssysteme zur Erlangung des Grades Bachelor im Studiengang Informatik / Computer Science / B.Sc.
<html>
<!DOCTYPE HTML PUBLIC „-W3CDTD HTML 4.01 TransitionalEN“ „http://www.w3c.org/TR/1999/REC-html401-19991224/loose.dtd“>
<HTML lang=de xmlns=„http://www.w3.org/1999/xhtml“ xml:lang=„de“><HEAD><TITLE>Holger Kreissl - Tutorials</TITLE>
<META content=BOHkCLIlpxR8ACzsNHIJ0oiVOE0mxaTjMKhP2KOewgc
name=google-site-verification><LINK
href=„http://www.kreissl.info/style.php?print=1“ type=text/css
rel=stylesheet><LINK
href=„http://www.kreissl.info/SyntaxHighlighter/Styles/SyntaxHighlighter.css“
type=text/css rel=stylesheet></LINK>
<META http-equiv=content-Type content=„text/html; charset=iso-8859-1“><LINK
href=„favicon.ico“ type=image/x-icon rel=icon><LINK href=„favicon.ico“
type=image/x-icon rel=„shortcut icon“>
<META content=„Holger Kreissl - Tutorials“ name=Title>
<META content=„Holger Kreissl“ name=Author>
<META content=„Holger Kreissl“ name=Publisher>
<META content=„Copyright by Holger Kreissl“ name=Copyright>
<META content=10/10/2009 name=Creation_Date>
<META content=„7 Days“ name=Revisit-after>
<META
content=„TU-Chemnitz,Theroretische Informatik,Rechnerarchitektur,Betriebssysteme,Datenbanken,Bilderkennung,Wissenstest,Fachprüfung,Tutorial,Einführung,Olbernhau, Kurzfilm,Deadly Sin,Medieninformatik“
name=Keywords>
<META
content=„Die Seite von Holger Kreissl mit vielen Links und Downloads rund um das Informatik Studium, sowie ausführlichen Tutorials über verschiedene Kerngebiete der Informatik“
name=Description>
<META content=bildung name=page-topic>
<META content=bericht name=page-topic>
<META content=alle name=Audience>
<META content=de name=Language>
<META content=INDEX,FOLLOW name=Robots>
<STYLE type=text/css>@import url( http://www.google.com/cse/api/branding.css );
</STYLE>
<SCRIPT src=„http://www.kreissl.info/functions.js“
type=text/javascript></SCRIPT>
<META content=„MSHTML 6.00.6000.21228“ name=GENERATOR></HEAD>
<BODY>
<TABLE class=FrameTable cellSpacing=0 cellPadding=0 width=950 bgColor=white>
<TBODY>
<TR class=topPageBar>
<TD style=„PADDING-LEFT: 5px; VERTICAL-ALIGN: top“></TD></TR>
<TR>
<TD class=bgunten colSpan=3> </TD></TR>
<TR>
<TD class=content style=„PADDING-RIGHT: 0px; PADDING-LEFT: 0px“>
<TABLE cellSpacing=0 cellPadding=0 width=„100%“ border=0>
<TBODY>
<TR>
<TD class=pagetitle>Betriebssysteme Tutorial - Holger Kreissl -
www.kreissl.info</TD></TR></TBODY></TABLE>
<TABLE cellSpacing=0 cellPadding=0 width=„100%“>
<TBODY>
<TR>
<TD>
<TABLE cellSpacing=0 cellPadding=0 width=„100%“>
<TBODY>
<TR>
<TD>
<TABLE class=tutorialtable cellSpacing=0 cellPadding=0
border=0>
<TBODY>
<TR vAlign=top>
<TD class=tutorial vAlign=top align=left>
<H1>Kapitel 1 - Einleitung Betriebsysteme </H1>
<TABLE width=„100%“>
<TBODY>
<TR>
<TD class=inhaltsliste>
<UL>
<LI>Hauptaufgaben einen Betriebssystems
<LI>Unterschiede zwischen Betriebssystemen
<LI>Bestandteile von Betriebssystemen
</LI></UL></TD></TR></TBODY></TABLE>
<H2>Einleitung - BS Definition </H2>Ein Betriebsystem
stellt <STRONG>Dienste</STRONG> und
<STRONG>Infrastrukturen</STRONG> (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)<BR><BR>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.<BR><BR><IMG
alt=„Organisation eines Betriebssystem“
src=„http://www.kreissl.info/pics/images/bs_08.gif“
border=0>
<H3>Definieren Sie den Begriff Betriebsystem! </H3>Das
Betriebssystem ist die <STRONG>Gesamtheit der
Programme</STRONG> 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.<BR><BR>Das Betriebssystem ermöglicht es
z.B. dem Anwender, Programme auf unterschiedlicher
Hardware laufen zu lassen. D.h. das Betriebssystem
bietet dem Anwender eine <STRONG>virtuelle
Maschine</STRONG>, welche die reale Hardware
„unsichtbar“ für den Programmierer macht. <BR><BR>
<DIV class=HINT>
<UL>
<LI>abstrahiert den Rechner auf eine für Menschen
leichter durchschaubare virtuelle Maschine
<LI>Steuert und koordiniert Prozessabläufe und
verwaltet die Ressourcen </LI></UL>
<DIV align=right><EM>Merktabelle: Definition
Betriebssysteme</EM> </DIV></DIV>
<H2>Wie sieht das Ebenen- oder Schichtenmodell eines
Rechners aus? </H2>
<OL>
<LI>Gatter Ebene
<LI>Mikroprogrammebene
<LI>konventionelle Maschinenebene
<LI>Betriebssystemebene API
<LI>Assemblerebene
<LI>Anwendungsebene </LI></OL>
<H3>Worin Unterscheiden sich Betriebssysteme? </H3>
<UL>
<LI>universal oder dezidiert (Multi-Task /
Single-Task)
<LI>eine oder mehrere Sitzungen (Windows < XP,
Linux)
<LI>Kommunikation mit der Umwelt (Batch, interaktiv
oder in Echtzeit) </LI></UL>
<H3>Was sind die drei Welten des Betriebsystems? </H3>
<UL>
<LI>Betriebssystem selbst
<LI>Komplexe Werkzeuge, wie aufgesetzte Dienste oder
Virtuelle Maschinen
<LI>Programmiersysteme zur Entwicklung von
Erweiterungen </LI></UL>
<H3>Welche Aufgaben hat ein Betriebsystem? </H3>
<OL>
<LI>Abstraktion der Hardware, d.h. Schließen der so
genannten 'Semantischen Lücke' zwischen
Mikroprogrammebene und der Anwendungsebene
<LI>Betriebsmittelverwaltung
<LI>Steuerung von Peripheriegeräten (I/O,
Festplatten…)
<LI>Steuerung des Betriebsablaufs durch
Prozessverwaltung und -Kommunikation und Organisation
des Mehrprogrammbetriebes
<LI>Protokollierung, Schutz und Sicherheit
<LI>Behandlung von Ausnahmesituationen, wie Page
Faults, Division by Zero u.s.w.
<LI>Bereitstellung einer Kommandosprache
<LI>Unterstützung von Administrationsaufgaben
(Datensicherung, Systemkonfigurierung, Benutzerrechte)
</LI></OL>
<H2>Was ist ein Modell? </H2>Ein Modell eines
Rechnersystems ist eine <STRONG>Abbildung eines realen
Systems</STRONG> unter Abstrahierung bestimmter
Kriterien, in dem eine formale Beschreibung durch eine
Theorie in Gesetzen formuliert werden kann.
<H3>Welche drei Punkte sind bei der Realisierung eines
BS grundlegend? </H3><B>Prozessor-Modes
(Betriebszustände)</B><BR><BR>
<TABLE width=„100%“>
<TBODY>
<TR>
<TD class=desc>Supervisor Mode<BR>(Kernel Mode)
</TD>
<TD class=„“>Ist ein privilegierter Modus für
Betriebssystemfunktionen im Kern des Systems,
welches Sicherheit des Systems erhöht, da diese
geschützt von Andwenderprogrammen laufen. </TD></TR>
<TR>
<TD class=desc>User Mode<BR>(Anwendungsmodus) </TD>
<TD class=„“>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.
</TD></TR></TBODY></TABLE><BR><B>Kernel</B><BR><BR>Im
Kern laufen die Systemkritischen Funktionen, wie z.B.
I/O-Aktionen ab. Der Kern muss korrekt, sicher und
geschützt vor Anwendungen sein.<BR><BR><B>Methoden des
Aufrufs von Betriebssystemsdiensten</B><BR><BR>
<TABLE width=„100%“>
<TBODY>
<TR>
<TD class=desc>System Calls </TD>
<TD class=„“>Durch <STRONG>System Calls</STRONG>
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.
</TD></TR>
<TR>
<TD class=desc>Nachrichtenversand </TD>
<TD class=„“>Über eine
<STRONG>Send/Receive-Schnittstelle</STRONG> können
sich User-Mode und Kernel-Mode Nachrichten
zuschicken. </TD></TR></TBODY></TABLE><BR>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.<BR><BR><IMG
alt=„System-Call am Beispiel Windows NT“
src=„http://www.kreissl.info/pics/images/bs_09.gif“
border=0><BR></TD>
<TD></TD></TR></TBODY></TABLE></TD>
<TD class=desc vAlign=top></TD></TR></TBODY></TABLE>
<TABLE cellSpacing=0 cellPadding=0 width=„100%“>
<TBODY>
<TR>
<TD>
<TABLE class=tutorialtable cellSpacing=0 cellPadding=0
border=0>
<TBODY>
<TR vAlign=top>
<TD class=tutorial vAlign=top align=left>
<H1>Kapitel 2 - Modelle </H1>
<TABLE width=„100%“>
<TBODY>
<TR>
<TD class=inhaltsliste>
<UL>
<LI>Modelle für Betriebssysteme
<LI>Hierarchiche Schichtenmodell
<LI>Betriebsmittel und Instanzen
<LI>Schalenmodell
<LI>Modulmodell (Monolithisches Modell)
<LI>Hierarchisches Schichtenmodell
<LI>Client Server Modelle
</LI></UL></TD></TR></TBODY></TABLE>
<H2>Vor- und Nachteile von Schalen- und Modulmodellen
</H2><STRONG>Schalenmodell:</STRONG>
<UL>
<LI>Relationen der einzelnen Schalen sind zur Umwelt
nicht sichtbar
<LI>System ist aber gut strukturiert
<LI>Innere Schalen sind sehr gut abgeschirmt von den
Äußeren </LI></UL><STRONG>Modulmodell:</STRONG>
<UL>
<LI>Das Modell wird in Modulen durch Programmcode
beschrieben
<LI>die Relationen werden daher extrem komplex
(quatradisch)
<LI>Daher ist es nur bei kleinen Modellen umsetzbar
</LI></UL>
<H2>Wie ist das hierarchische Schichtenmodell aufgebaut?
</H2>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.
(<STRONG>Steuerungshierarchie</STRONG>)<BR><BR><B>Bestandteile:</B>
<UL>
<LI>Schichten
<LI>Iterative Ordnungsrelation der Schichten (Dienste,
Steuerungen bzw. Instanzen)
<LI>Betriebsmittel
<LI>Funktionen zum Erzeugen von Betriebsmitteln und
Steuerungen </LI></UL>
<H3>Welche Vorteile hat das hierarchisch
Schichtenmodell? </H3>
<UL>
<LI>obwohl modularisiert, ist die Zahl der Relationen
gering
<LI>Kommunikation mit der Umwelt ist möglich
<LI>Es bietet eine Infrastruktur für Instanzen
(Steuerung, BM-Transformationen) </LI></UL>
<H2>Was ist ein Betriebsmittel? </H2>Ein Betriebsmittel
ist eine abstrakte Ressource, welche über eine Adresse
und einen Wert verfügt. Sie wird definiert über
<UL>
<LI>ID (eindeutiger Identifikator)
<LI>Adressbereich (für alle möglichen Adressen des
Betriebsmittels)
<LI>Wertebereicht (aller möglichen Werte für einen
Wert des BM)
<LI>Funktion (verknüpft die abstrakten Elemente
miteinander) </LI></UL><EM>Der Zustand eines
Betriebsmittels ergibt sich aus Wert x Adresse.</EM>
<H3>Welche Klassen von Betriebsmitteln gibt es? </H3>
<UL>
<LI>Entziehbarkeit (entziehbar wie Prozessor oder
nicht wie Dateideskriptor)
<LI>Zuteilbarkeit (gleichzeitig wie Speicher oder
exklusiv wie Prozessor oder Drucker)
<LI>Wiederverwendbarkeit (einmalig Nutzbar wie
Interrupt oder mehrfach wie Prozessor oder Speicher)
<LI>Hardware / Software (logisches oder physikalisches
Betriebsmittel) </LI></UL>
<H3>Vorgehensweise beim Erstellen eines Betriebsmittels
</H3>
<OL>
<LI>ID bestimmen
<LI>abstrakte Elemente bestimmen, welche einen Wert
und eine Adresse besitzen
<LI>Wert und Adresse festlegen
<LI>Funktionen definieren, welche Zugriff auf alle
Elemente ermöglichen </LI></OL>
<H3>Erläutern sie die Betriebsmittelerstellung am Bsp.
Hauptspeicher! </H3>
<OL>
<LI>Eine ID ist hier nicht sinnvoll, da ein
von-Neumann Rechner nur einen Hauptspeicher hat.
<LI>die abstrakten Elemente sind die ansprechbaren
Speicherzellen mit Adresse und Wert.
<LI>Der Wertebereich beträgt 0 bist 255 bei einem
Byte-Orientierten Speicher
<LI>Funktionen sind Read und Write eines Elementes zum
Speicher </LI></OL>
<H2>Was ist eine Instanz? </H2>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.
<H3>Wechle Klassen von Instanzen kennen Sie? </H3>
<UL>
<LI>Applikationen
<LI>Betriebsmittel-Transformatoren
<LI>Metasteuerungen wie PUM </LI></UL>
<H3>Wie können Relationen zwischen Instanzen technisch
hergestellt werden? </H3>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.<BR><BR>Als
Beispiel nehmen wir einen Spooler. Hier ist die
Schnittstelle ein Betriebsmittel (Speicherbuffer) und
das Protokoll (Verhalten) ist als Dienst
implementiert.<BR><BR><EM>Spool = Simultanously Periphal
Output On Line</EM><BR><BR>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. </TD>
<TD></TD></TR></TBODY></TABLE></TD>
<TD class=desc vAlign=top></TD></TR></TBODY></TABLE>
<TABLE cellSpacing=0 cellPadding=0 width=„100%“>
<TBODY>
<TR>
<TD>
<TABLE class=tutorialtable cellSpacing=0 cellPadding=0
border=0>
<TBODY>
<TR vAlign=top>
<TD class=tutorial vAlign=top align=left>
<H1>Kapitel 3 - Aktivitäten </H1>
<TABLE width=„100%“>
<TBODY>
<TR>
<TD class=inhaltsliste>
<UL>
<LI>Was sind Aktivitätstoken?
<LI>Welche Arten von Token gibt es?
<LI>Was sind Prozesse?
<LI>Unix Prozesserzeugung
<LI>Zustände von Prozessen
</LI></UL></TD></TR></TBODY></TABLE>
<H2>Was ist ein Aktivitätstoken? </H2>
<UL>
<LI>Ist sehr abstrakt zu sehen
<LI>Ein Aktivitätstoken haucht dem Programm erst
„Leben“ ein
<LI>Beschreibt ein aktiven oder wartenden Prozess
<LI>Es muss eine Art virtuellen Programmcounter im
eigenen virtuellen Steuerwerk des Prozesses geben
</LI></UL>
<H2>Was ist Multitasking? </H2>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.
<H2>Welche Aktivitäten gibt es und worin unterscheiden
sie sich? </H2>
<TABLE cellSpacing=2 cellPadding=1 border=0>
<TBODY>
<TR>
<TD class=desc></TD>
<TD class=desc width=80>Token </TD>
<TD class=desc width=80>Verteilung </TD>
<TD class=desc>Protokoll </TD>
<TD class=desc>BM-Zuteilung </TD></TR>
<TR>
<TD class=desc>Prozedur </TD>
<TD class=descsec>Eins für alle </TD>
<TD class=descsec>- </TD>
<TD class=descsec>Call Return </TD>
<TD class=descsec>Exclusiv </TD></TR>
<TR>
<TD class=desc>Coroutine </TD>
<TD class=descsec>Eins für alle </TD>
<TD class=descsec>- </TD>
<TD class=descsec>Resume, aber dynamischer
Eintrittspunkt (kooperatives Multitasking) </TD>
<TD class=descsec>Exclusiv </TD></TR>
<TR>
<TD class=desc>Prozess </TD>
<TD class=descsec>Pro Prozess </TD>
<TD class=descsec>Pro Prozess </TD>
<TD class=descsec>Keine Übergabe, da Prozess Token
behält </TD>
<TD class=descsec>Exclusiv </TD></TR>
<TR>
<TD class=desc>Thread </TD>
<TD class=descsec>Pro Prozess </TD>
<TD class=descsec>Pro Thread Eins </TD>
<TD class=descsec>Keine Übergabe, da Prozess Token
behält </TD>
<TD class=descsec>Threads sind in Prozessen
gruppiert und teilen sich dort die Betriebsmittel
</TD></TR></TBODY></TABLE>
<H2>Welche Betriebsmittel benötigt eine Aktivität
mindestens? </H2>
<UL>
<LI>Programmcode
<LI>Hauptspeicher
<LI>Steuerwerk </LI></UL>
<H3>Wodurch wird ein Prozess beschrieben? </H3>
<UL>
<LI>ein im System eindeutiger Identifikator (PID)
<LI>Liste mit Betriebsmittel-Forderungen
<LI>Liste mit zugeteilten Betriebsmitteln
<LI>Ein Folge der bisherigen Anweisungen
<LI>Die Anfangswertbelegungen der zugeteilten
Betriebsmittel </LI></UL>
<H3>Welche Probleme treten mit Prozessen auf? </H3>
<UL>
<LI>Determiniertheit (Durch Mehrfachverwendung von
Betriebsmitteln ist diese so nicht mehr gegeben und
Synchronisation wird notwendig)
<LI>Mutual Exclusion
<LI>Synchronisation (Abstimmung zwischen Threads)
<LI>Kommunikation (Synchronisation und Austausch von
Daten zwischen Prozessen)
<LI>Lebendigkeit </LI></UL>
<H3>Welche Zustände kann ein Prozess einnehmen? </H3>
<UL>
<LI>nicht existent (Prozess noch nicht definiert)
<LI>bereit (besitzt alle angeforderten Betriebsmittel
außer den Prozessor)
<LI>aktiv (besitzt mindestens die angeforderten
Betriebsmittel)
<LI>wartend (wartet noch auf noch nicht zugeteilte
Betriebsmittel) </LI></UL><BR><BR><IMG alt=Prozess
src=„http://www.kreissl.info/pics/images/bs_01.gif“
border=0><BR><BR>
<H2>Wie wird ein Prozess im Unix erstellt? </H2>
<UL>
<LI>mit Systemaufruf fork() wird ein komplettes
Speicherabbild eines schon bestehenden Prozesses
erzeugt (bei NT wird Prozess mit einem Initialzustand
erstellt)
<LI>Deshalb erben neue Prozesse eventuelle Variablen
des Vaterprozesses </LI></UL>Deshalb terminiert folgende
Schleife nicht unter NT aber unter Unix:<BR><BR><PRE class=c# name=„code“>For ( i=1; i<3; i++) fork();
</PRE>
<H3>Einige Unix-Systembefehle zur Prozesserzeugung:
</H3>
<UL>
<LI>fork(), vfork() zum Prozesserstellen mit
Speicherabbild des Vaters
<LI>clone() erstellt einen Prozess der der den
Speicher und Deskriptoren mit Vater teilt
<LI>execl(), execv(), execle(), execlp(), execvp() zum
Kopieren eines Programms in den Speicher
<LI>wait(), waitpid() zum Warten auf Ende des
Sohnprozesses
<LI>exit() zum Beenden eines Prozesses
</LI></UL>http://unixhelp.ed.ac.uk/CGI/man-cgi
<H3>Ein Beispielcode für eine Einfache Unix-Shell </H3><PRE class=c# name=„code“>#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; }
</PRE>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.<BR><BR>Am Besten
einfach ausprobieren. Den Quellcode eingeben oder
kopieren und mit dem gcc compilieren:<PRE class=c# name="code">gcc minishell.cc -o minishell
</PRE><EM>Aufruf: ./minishell</EM>
<H2>Wie werden Prozesse verwaltet? </H2>Das
Betriebssystem verwaltet alle Prozesse. Die Prozesse
besitzen einen PCB (<STRONG>Process Controll
Block</STRONG>, 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.
<H2>Was ist Timesharing? </H2>Timesharing ist die
<STRONG>gemeinsame Benutzung des Betriebsmittels
Prozessor</STRONG> 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.
<H2>Was sind virtuelle Geräte bzw. Betriebsmittel?
</H2>Virtuelle Geräte stellen durch das Betriebssystem
<STRONG>simulierte Geräte</STRONG> 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. </TD>
<TD></TD></TR></TBODY></TABLE></TD>
<TD class=desc vAlign=top></TD></TR></TBODY></TABLE>
<TABLE cellSpacing=0 cellPadding=0 width="100%">
<TBODY>
<TR>
<TD>
<TABLE class=tutorialtable cellSpacing=0 cellPadding=0
border=0>
<TBODY>
<TR vAlign=top>
<TD class=tutorial vAlign=top align=left>
<H1>Kapitel 4 - Kritischer Abschnitt </H1>
<TABLE width="100%">
<TBODY>
<TR>
<TD class=inhaltsliste>
<UL>
<LI>Kritischer Abschnitt und Mutual Exclusion
<LI>Dezentrale und Zentrale Steuerungen
<LI>Semaphore und ihre Impementierung
<LI>Verschiedenen Synchronisationsprobleme
</LI></UL></TD></TR></TBODY></TABLE>
<H2>Was ist ein Kritischer Abschnitt? </H2>Ein
Kritischer Abschnitt ist ein zeitlicher Bereich, in
welchem mindestens zwei Prozesse auf das gleiche
Betriebsmittel zugreifen und mindestens eines davon
schreibt. (Zeitkritischer Ablauf)
<H3>Erklären sie am Bsp. Druckerspooler den kritischen
Abschnitt! </H3>
<OL>
<LI>in Spooler ist der Platz 4 frei
<LI>Prozess A will drucken und liest die Platznummer
<LI>PUM aktiviert Prozess B, welcher ebenfalls diese
Platznummer liest
<LI>Prozess B schreibt den Auftrag nach Platz 4
<LI>PUM schaltet zu A zurück und A überschreibt nun
den Druckauftrag von B! </LI></OL><EM><STRONG>Deshalb
notwendig:</STRONG> Wechselseitiger Ausschluss!</EM>
<H2>Warum werden keine Interrupt Unterbrechungen zur
Synchronisation verwendet? </H2>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)
<H2>Was ist wechselseitiger Ausschluss? </H2>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.
<H3>Welche Anforderungen muss eine Steuerung für
kritische Abschnitte erfüllen? </H3>
<OL>
<LI>exklusive Nutzung durch verschiedene Teilprozesse
über mutual exclusion
<LI>Ein Prozess darf einen anderen nur behindern, wenn
beide im kritischen Abschnitt
<LI>Der Eintritt in einen kritischen Abschnitt darf
nicht lang dauern
<LI>Alle Prozesse müssen in endlicher Zeit ihre
Betriebsmittel zugewiesen bekommen
<LI>globale Unabhängigkeit von allgemeinen
Fortschreiten der Prozesse </LI></OL>
<H2>Welche dezentralen Steuerungen kennen Sie? (aktives
Warten) </H2>
<UL>
<LI>Test and Set Lock
<LI>Ping-Pong (Striktes Alternieren)
<LI>Decker Algorithmus
<LI>Peterson Algorithmus </LI></UL>
<H3>Wie arbeitet Striktes Alternieren? (Ping Pong) </H3>
<TABLE cellSpacing=2 cellPadding=2 border=0>
<TBODY>
<TR>
<TD class=desc>Prozess A </TD>
<TD class=desc>Prozess B </TD></TR>
<TR>
<TD><PRE class=c# name="code">While (1)
{
while (turn!=FALSE); criticalsection(); turn = TRUE; notcriticalstuff();
}
</PRE></TD>
<TD><PRE class=c# name="code">While (1)
{
while (turn!=TRUE); criticalsection(); turn = FALSE; notcriticalstuff();
} </PRE></TD></TR>
<TR>
<TD colSpan=2>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.
</TD></TR></TBODY></TABLE>
<H3>Wie schaut Peterson's Algorithmus aus? </H3><PRE class=c# name="code">
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 ) AND (interested[other]==TRUE));
} void V(int process) Welcher Prozess verläßt K.A. { interested[process]= FALSE; Kein Interesse mehr } </PRE>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.
<H2>Was sind Semaphore - zentrale Steuerung? </H2>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.<BR>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.
<H3>Wie funktioniert das Grundprinzip von Semaphoren?
</H3>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. <PRE class=c# name="code">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);
} </PRE>sleep und wakup sind Systembefehle, welche einen
Prozess Schlafenlegen oder Aufwecken.<BR><BR>
<TABLE cellSpacing=2 cellPadding=2 border=0>
<TBODY>
<TR>
<TD class=desc>Prozess A </TD>
<TD class=desc>Prozess B </TD></TR>
<TR>
<TD colSpan=2><PRE class=c# name="code">
int sem = 1; zwei Prozesse </PRE></TD></TR> <TR> <TD><PRE class=c# name=„code“> While (1) { P(sem); kritischer Abschnitt
V(sem);
} </PRE></TD>
<TD><PRE class=c# name="code">While (1)
{
P(sem); // kritischer Abschnitt V(sem);
} </PRE></TD></TR>
<TR>
<TD colSpan=2></TD></TR></TBODY></TABLE>
<H3>Wie arbeiten Events bzw. Ereignisse?
</H3>Betriebssysteme wie z.B. Unix benutzen Events als
Abstraktion von Semaphoren zum
<STRONG>Koordinieren</STRONG> von Prozessabläufen (im
Gegensatz zu kritischen Abschnitten). Ein Ereignis
stellt nichts weiter als eine für Software erkennbare
<STRONG>Bedingung</STRONG> dar. Ein Prozess kann sich
Schlafen legen, bis eine bestimmte Bedingung eintreten.
<UL>
<LI>Ein Prozess setzt einen wait()-Aufruf auf ein
Ereignis ab. Er wird dann an dem Event-Deskriptor
wartend gesetzt.
<LI>Wenn an dem Event-Deskriptor das Ereignis
signalisiert wird, so wird ein dort wartender Prozess
bereit gesetzt.
<LI>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.
</LI></UL><STRONG>Semaphore:</STRONG> Wert 0. Kommt das
signal() vor dem wait(): der wait()-aufrufende Prozess
wird nicht blockiert.<BR><BR><STRONG>Event:</STRONG> 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.
<H3>Was versteht man unter einem Monitor und wie
funktioniert er? </H3>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. <BR><BR>
<DIV class=HINT>
<UL>
<LI>Es gibt dezentrale und zentrale Steuerungen für
kritische Abschnitte
<LI>Dezentrale Steuerungen ist das aktives Warten
<LI>Zentrale Steuerungen sind Semaphore (passives
Warten)
<LI>Beim passiven Warten werden Prozesse
schlafengelegt
<LI>Ereignisse dienen der Koordination </LI></UL>
<DIV align=right><EM>Merktabelle:
Synchronisationsmöglichkeiten</EM> </DIV></DIV>
<H2>Was ist das Erzeuger-Verbraucher-Problem? </H2>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.<BR><BR>Nun stellen sich die Fragen
<OL>
<LI>Wie soll man das gleichzeitige Einfügen und
Entnehmen synchronisieren?
<LI>Ein Datum darf nur eingefügt werden wenn der
Puffer nicht voll ist.
<LI>Ein Datum darf nur eingefügt werden, wenn noch
Platz im Buffer ist. </LI></OL>Gelöst werden, kann das
Problem mit mehreren Semaphoren.
<UL>
<LI>Ein Semaphor für die Kontrolle des kritischen
Abschnittes
<LI>Ein Semaphor, welcher die freien Plätze zählt
<LI>Ein Semaphor, welcher die vergebenen Plätze zählt
</LI></UL><PRE class=c# name="code">
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);
}
} </PRE>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.
<H2>Was ist das Philosophenproblem? </H2>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.<BR><BR>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.
<H3>Wie kann das Philosophenproblem gelöst werden?
</H3>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.
<H2>Wie funktionieren Unix-Signale? </H2>Ein Ereignis
wird hier als Signal bezeichnet. Unter Unix gibt es
vorgegebene durchnummerierte Signale. Unter Unix kann
mit <EM>kill(Prozessnummer, Signalnummer)</EM> einem
Prozess ein Ereignis signalisiert werden.<BR><BR>Die
Reaktion eines Prozesses auf ein Signal kann verschieden
ausfallen:<BR><BR>
<UL>
<LI>Aktivierung einer Prozessfunktion, die der Prozess
vorher für dieses Signal mit der Funktion
<STRONG>signal( Signalnummer,
Funktionsadresse)</STRONG> angemeldet hat
<LI>Er kann das Signal mit
<STRONG>signal(Signalnummer, SIG_IGN);</STRONG>
ignorieren
<LI>Der Prozess kann beendet werden.
<LI>Hat der Prozess für eine Signalnummer nichts
festgelegt, dann gibt es Voreinstellungen: </LI></UL>
<TABLE cellSpacing=1 width="100%">
<TBODY>
<TR>
<TD> </TD>
<TD>#define SIGFPE </TD>
<TD>8 </TD>
<TD>/* Floating point trap */ </TD></TR>
<TR>
<TD> </TD>
<TD>#define SIGILL </TD>
<TD>4 </TD>
<TD>/* Illegal instruction */ </TD></TR>
<TR>
<TD> </TD>
<TD>#define SIGINT </TD>
<TD>2 </TD>
<TD>/* voreingestelle Interrupttaste z.B. Ctl -c*/
</TD></TR>
<TR>
<TD> </TD>
<TD>#define SIGSEGV </TD>
<TD>11 </TD>
<TD>/* Memory access violation */ </TD></TR>
<TR>
<TD> </TD>
<TD>#define SIGTERM </TD>
<TD>15 </TD>
<TD>/* Kill -Kommando ohne Angabe*/ </TD></TR>
<TR>
<TD> </TD>
<TD>#define SIGKILL </TD>
<TD>9 </TD>
<TD>/* unbedingter Prozessabbruch*/
</TD></TR></TBODY></TABLE>
<H2>Was unterscheidet Pipes und Named Pipes? </H2>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 <STRONG>Named
Pipe</STRONG> umgangen werden. Eine Named Pipe ist ein
mit einem <STRONG>eindeutigen Namen versehenes
Objekt</STRONG> 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.<BR><IMG
alt="Pipe Schema"
src="http://www.kreissl.info/pics/images/bs_12.gif"
border=0><BR>
<H2>Was sind Sockets? </H2>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:<BR><BR>Ein Serverprozess
erstellt einen Socket mit <EM>create</EM> und wartet
dann auf Verbindungswünsche (<EM>listen</EM>).
<H2>Welche Möglichkeiten zur Kommunikation und
Synchronistation kennen Sie?
</H2><STRONG>Kommunikation</STRONG>
<UL>
<LI>Pipes (FIFO-Puffer - Senden (Schreiben) ist
asynchron, Empfangen (Lesen) blockierend)
<LI>Named Pipes
<LI>Mailboxen (Tool zum Senden und Empfangen von
Nachrichten)
<LI>Send - Receive (BS Unterstützung für Mailboxen -
synchron oder asynchron)
<LI>Queues
<LI>Sockets
<LI>RPC
<LI>Shared Memory
</LI></UL><STRONG>Synchronisation</STRONG>
<UL>
<LI>Monitore
<LI>Events
<LI>Semaphore
<LI>Barierren (oft zur Threadsynchronisation
verwendet) </LI></UL></TD>
<TD></TD></TR></TBODY></TABLE></TD>
<TD class=desc vAlign=top></TD></TR></TBODY></TABLE>
<TABLE cellSpacing=0 cellPadding=0 width="100%">
<TBODY>
<TR>
<TD>
<TABLE class=tutorialtable cellSpacing=0 cellPadding=0
border=0>
<TBODY>
<TR vAlign=top>
<TD class=tutorial vAlign=top align=left>
<H1>Kapitel 5 - Scheduling </H1>
<TABLE width="100%">
<TBODY>
<TR>
<TD class=inhaltsliste>
<UL>
<LI>zentral, dezentral und Modelle für
Scheduling
<LI>Scheduling Strategien
<LI>Prioritätsscheduling und Round Robin
</LI></UL></TD></TR></TBODY></TABLE>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:
<UL>
<LI>Deterministisches Modell - alle Informationen
bekannt (Anzahl Prozesse/Betriebsmittel/Zeitdauer)
<LI>Probabilistisches Modell - offen (Anzahl Prozesse
nicht bekannt) oder geschlossen (Anzahl Prozesse
bekannt, aber Bedienzeiten nicht) </LI></UL>
<H2>Welche Strategien der Prozessorzuteilung werden
unterschieden? </H2>
<UL>
<LI><STRONG>Durchsatz</STRONG> (Anzahl bearbeiteter
Prozesse pro Zeiteinheit maximieren)
<LI><STRONG>Verweilzeit</STRONG> (Prozess soll so
schnell wie möglich abgearbeitet sein)
<LI><STRONG>Wartezeit</STRONG> (Dauer im Zustand
"wartend" minimieren)
<LI><STRONG>Effizienz</STRONG> (Prozessorleistung
maximal ausnutzen)
<LI><STRONG>Antwortzeit</STRONG> (möglichst kurze
Reaktionszeiten für den Benutzer)
<LI><STRONG>Fairness</STRONG> (gerechte Verteilung der
Prozessorzeit) </LI></UL>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.
<H2>Nach welchen Kriterium richtet sich das Scheduling
Verfahren? </H2>Dies hängt in erster Linie vom
Einsatzgebiet des Systems ab:
<UL>
<LI>Echzeitbetrieb
<LI>Dialogbetrieb
<LI>Stabel- bzw. Batchbetrieb
<LI>Hintergrundbetrieb </LI></UL>
<H2>Was ist das deterministische Modell? </H2>Bei diesem
Modell werden die Schedules <STRONG>vor der Ausführung
berechnet</STRONG>. 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...
<H2>Was ist das probabilistisches Modell? </H2>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).<BR><BR><IMG alt=Prozess
src="http://www.kreissl.info/pics/images/bs_02.gif"
border=0><BR><BR>Die Abbildung entspricht einem
Scheduling ohne Prioritäten und ohne Entzug.
<H3>Was ist das Single-Server-Modell? </H3>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 .<BR>
<TABLE width="100%">
<TBODY>
<TR>
<TD align=right colSpan=2><IMG alt=Singe-Server
src="http://www.kreissl.info/pics/images/bs_06.gif"
border=0><BR><BR></TD></TR>
<TR>
<TD class=desc>mittlere Verweildauer in
Warteschlange </TD>
<TD>W </TD></TR>
<TR>
<TD class=desc>Zwischenankunftsabstand </TD>
<TD>A </TD></TR>
<TR>
<TD class=desc>Prozessorzeit der Teilprozesse </TD>
<TD>B </TD></TR>
<TR>
<TD class=desc>Anzahl von Prozessen in
Warteschlange </TD>
<TD>Nq (N=Nq+p) </TD></TR>
<TR>
<TD class=desc>Verkehrswert </TD>
<TD>p=B/A <EM>(Poisson-Prozesse)</EM> </TD></TR>
<TR>
<TD class=desc>Verweildauer im System </TD>
<TD>V=A*N (Littles Theroem)
</TD></TR></TBODY></TABLE><BR><BR>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.
<H3>Wie können Wahrscheinlichkeiten für Prozessgrößen
ermittelt werden? </H3>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).
<H3>Wie arbeitet First Come First Serve - FCFS?
</H3>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.<BR><BR>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.<BR><BR><STRONG>Durchschnittliche Wartezeit
W</STRONG> = (Wartezeit(P1) + Wartezeit(P2) + ... +
Wartezeit(Pn)) / n<BR><BR>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.<BR><BR><STRONG>Bsp.:</STRONG><BR><BR>t(P1) = 24
t(P2) = 3 t(P3) = 3<BR><BR>Bei einer Abarbeitungsfolge
von <STRONG>P1 -> P2 -> P3</STRONG> wäre W =
<EM>17</EM>.<BR>Bei einer Abarbeitungsfolge von
<STRONG>P2 -> P3 -> P1</STRONG> nur <EM>3</EM>!
<H2>Was ist Prioritäts-Scheduling? </H2>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.<BR><BR><EM><STRONG>Bsp:</STRONG> FEP
(<STRONG>Fixed External
Priorities</STRONG>)</EM><BR><BR>
<TABLE width="100%">
<TBODY>
<TR>
<TD align=right><IMG alt=Prioritätsscheduling
src="http://www.kreissl.info/pics/images/bs_07.gif"
border=0> </TD></TR></TBODY></TABLE>
<H3>Was ist das Problem von Schedulern mit Prioritäten?
</H3>Hauptproblem beim Arbeiten mit Prioritäten ist das
<STRONG>Aushungern</STRONG> von Prozessen, welche
möglicherweise nie aktiv werden können, da es immer
Prozesse höherer Priorität gibt.<BR><BR>Lösung hierfür
ist das <STRONG>Aging</STRONG>. (dynamische Anhebung der
Priorität der älter werdenden Prozesse)<BR><BR>Ein
anderes Problem ist die Prioritätenumkehr. Ein
hochpriorisierter Prozess wartet auf ein Betriebsmittel,
welches ein niedrigpriorisierter Prozess reserviert hat.
<H3>Wie funktioniert Shortest Job First (dynamische
Priorität ohne Entzug)? </H3>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.<BR><BR>Deshalb optimiert Shortest Job
First die mittlere Wartezeit. Problem ist hier auch das
Aushungern von Prozessen, was auch durch Aging (Altern)
verhindert werden kann.<BR><BR><STRONG>SJF ist ohne
Entzug</STRONG> (nonpreemtiv). Eine Variante mit Enzug
ist <STRONG>SRTF</STRONG>. Dabei wird der Prozessor
entzogen, falls ein Prozess in der Warteschlange ist,
der kürzer als der verbliebene Rest des aktiven
Prozesses.
<H3>Wie arbeiten Shortest Remaining Time First und
Shortest Elapsed Time (dynamisch mit Entzug)? </H3>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.
<H3>Wie arbeitet Highest Response Ratio Next - HRN?
</H3>Umso länger ein Prozess wartet, umso höher steigt
er in seiner Priorität. So wird Aushungern verhindert.
<H2>Wie funktioniert Round-Robin Scheduling (ohne
Prioritäten)? </H2>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
(<STRONG>Quantum</STRONG>) 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.<BR><BR>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)<BR><BR><EM>Sinnvoll erwiesen sich Quanten von
100 ms.</EM> <BR><BR>
<DIV class=HINT>
<UL>
<LI>Scheduling mit oder ohne Entzug
<LI>Scheduling mit oder ohne Prioritäten
<LI>Zentrale Steuerungen sind Semaphore (passives
Warten)
<LI>Beim passiven Warten werden Prozesse
schlafengelegt
<LI>Ereignisse dienen der Koordination </LI></UL>
<DIV align=right><EM>Merktabelle: Scheduling
Algorithmen</EM> </DIV></DIV>
<H2>Was ist Zweistufiges Scheduling? </H2>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.
<OL>
<LI>Wie lange ist ein Prozess Aus- oder Eingelagert?
<LI>Wieviel Prozessorzeit hat ein Prozess in Anspruch
genommen?
<LI>Wie groß ist der Prozess im Speicher?
<LI>Welche Priorität hat der Prozess? </LI></OL>
<H3>Was steht im Widerspruch zu hohem Durchsatz und
guter Auslastung? </H3>Im Widerspruch dazu stehen
<STRONG>gutes Antwortzeitverhalten</STRONG> 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. </TD>
<TD></TD></TR></TBODY></TABLE></TD>
<TD class=desc vAlign=top></TD></TR></TBODY></TABLE>
<TABLE cellSpacing=0 cellPadding=0 width="100%">
<TBODY>
<TR>
<TD>
<TABLE class=tutorialtable cellSpacing=0 cellPadding=0
border=0>
<TBODY>
<TR vAlign=top>
<TD class=tutorial vAlign=top align=left>
<H1>Kapitel 6 - Speichermanagment </H1>
<TABLE width="100%">
<TBODY>
<TR>
<TD class=inhaltsliste>
<UL>
<LI>Freispeicherverwaltung durch Bitmaps, Listen
und Buddy
<LI>Mehrdimensionale Adressräume durch
Segmentierung
<LI>virtueller Speicher durch Paging
<LI>Zusammenwirken von Segmentierung und Paging
<LI>Adressumrechnung am Beispiel
</LI></UL></TD></TR></TBODY></TABLE><B>Übersicht zur
Freispeicherverwaltung</B><BR><BR>Es gibt drei
grundlegende Ansätze zur Verwaltung des freien
Speichers. Diese werden im folgendem Text erläutert.
<H3>Was sind Bitmaps? </H3>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.
<H3>Welche Möglichkeiten der Suche in Freispeicherlisten
gibt es? </H3>Bei dieser Variante werden Listen für
Löcher und belegte Segmente durch Prozesse
geführt.<BR><BR><BR><STRONG>First
Fit</STRONG><BR><BR>Der erste freie Block der groß genug
ist wird ausgewählt, egal wieviel Speicher dadurch
verschwendet wird (interne
Fragmentierung).<BR><BR><STRONG>Next
Fit</STRONG><BR><BR>Suche beginnt nicht vom Anfang der
Liste, sondern vom zuletzt verwendeten
Listenelement.<BR><BR><STRONG>Best
Fit</STRONG><BR><BR>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.<BR><BR><STRONG>Quick Fit</STRONG><BR><BR>Es gibt
mehrere Listen für verschiedene Blockgrößen.
<H3>Wie funktionieren Buddy Listen? </H3>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.<BR><BR><STRONG>Beispiel:</STRONG><BR><BR>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.<BR><BR>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.<BR><BR>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.
<H3>Zusammenfassung Freispeicherverwaltung </H3>Bitmaps
unterteilen den Speicher in
<STRONG>Allokationseinheiten</STRONG>. 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
<STRONG>starke interne Fragmentation</STRONG>, da ja
immer auf Zweierpotenzen gerundet werden muss. <BR><BR>
<DIV class=HINT>
<UL>
<LI>einfache verkettete Listen mit Best-,Next- oder
First-Fit Suche
<LI>Bitmap-System welches Speicher in gleichgroße
Einheiten teilt
<LI>Buddy-Listen nach dem binären System
<LI>Beim passiven Warten werden Prozesse
schlafengelegt
<LI>Ereignisse dienen der Koordination </LI></UL>
<DIV align=right><EM>Merktabelle: Methoden zur
Freispeicherverwaltung</EM> </DIV></DIV>
<H2>Wie arbeitet Segmentierung (mehrdimensionale
Adressräume)? </H2>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.<BR><BR>Segmentierte Speicherung
wird oft als das Prinzip der <STRONG>gestreuten
Speicherung</STRONG> 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...
<H3>Wie werden Segmenten adressiert? </H3>Um mit
Segmenten arbeiten zu können, sind zweiteilige Adressen
notwendig, bestehend aus <STRONG>Segment</STRONG> und
<STRONG>Offset</STRONG>. 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.<BR>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.
<H3>Was versteht man unter gemeinsam genutzten
Segmenten? </H3>Durch Segmentierung wird es sehr
einfach, verschiedene Codesegmente gemeinsam zu nutzen.
So genannte <STRONG>Shared Libraries</STRONG> 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.
<H2>Wie funktioniert das Prinzip des virtuellen
Speichers durch Paging? </H2>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 <STRONG>Page
Table</STRONG> 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 <STRONG>Dirty Bit</STRONG>,
ob eine Seite im Speicher geändert wurde, um entscheiden
zu können, ob ein zurück schreiben notwendig
wird.<BR><BR>Die momentan verwendeten Seiten eines
Programmablaufes wird <STRONG>Working Set</STRONG>
genannt. Demand Paging bedeutet, dass Seiten erst dann
abgefordert werden, wenn sie benötigt
werden.<BR><BR>Eine virtuelle Adresse besteht aus
<STRONG>Seitenummer und Offset</STRONG>. 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 <STRONG>Seitenverzeichnis</STRONG> (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)<BR><BR>Beim Swapping werden statt Seiten ganze
Prozesse ausgelagert. <BR><BR>
<DIV class=HINT>
<UL>
<LI>Demand Paging und Caching basieren auf den
gleichen Prinzip
<LI>Sie arbeiten nur auf verschiedenen Ebenen
<LI>Cache-Misses werden von der Hardware geregelt,
Page Faults vom Betriebssystem
<LI>Beim passiven Warten werden Prozesse
schlafengelegt
<LI>Ereignisse dienen der Koordination </LI></UL>
<DIV align=right><EM>Merktabelle: Virtual Memory und
Caching</EM> </DIV></DIV>
<H3>Was ist der Translation Lookaside Buffer? </H3>Um
die Zeit der Adressumrechnung zu vermindern, wird in der
MMU ein <STRONG>Assoziativspeicher</STRONG> 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. <BR><BR>
<DIV class=HINT>
<UL>
<LI>TLB's werden verwendet, wenn Seitentabelle auf
Grund eines zu großen Adressraumes nicht möglich ist
<LI>TLB bildet zuletzt genutzten (64 bei UltraSparc)
virtuellen Seitennummern auf physikalische
Seitenrahmen ab
<LI>häufig benutzte Seiten werden in einem Cache
(Translation Storage Buffer) verwaltet
<LI>Dieser Cache bildet Seiten direkt ab und wird bei
TLB-Miss zuerst untersucht
<LI>befindet sich die Seite nicht im Cache, muss sie
in der Translation Table gesucht werden </LI></UL>
<DIV align=right><EM>Merktabelle: Translation Lookaside
Buffer</EM> </DIV></DIV>
<H3>Was sind invertierte Page Tables? </H3>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.
<H3>Was sind Paging Dämons? </H3>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 <STRONG>Frames</STRONG> im Speicher zur
Verfügung stehen. Ist dies nicht der Fall, werden so
viele Seiten wie notwendig mit einem der
<STRONG>Seitenersetzungsalgorithmen</STRONG> aus dem
Speicher entfernt und auf die Platte zurückgeschrieben.
<H3>Erklären Sie das Zusammenspiel von Segmentierung und
Paging? </H3>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
<STRONG>transparent</STRONG>, 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
<OL>
<LI>die Segmentnummer zur Auswahl des richtigen
Segmentdeskriptors und
<LI>den Offset zur Adressierung innerhalb des
Segmentes. </LI></OL>Die Implementierungen unterscheiden
sich nun in der Verwaltung der
<STRONG>Deskriptoren</STRONG> 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.<BR><BR><IMG alt=Adressumsetzung
src="http://www.kreissl.info/pics/images/bs_11.gif"
border=0>
<H3>Was passiert wenn Sie ein Programm starten? </H3>
<UL>
<LI>Der Virtual Memory Manager verwaltet den
virtuellen Speicher.
<LI>Bei Programmstart richtet das BS für den Prozess
eine Seitentabelle ein.
<LI>Eine definierte Anzahl Rahmen werden dem Prozess
als Arbeitsmenge zugeteilt.
<LI>Seiten aus dem Read-Only Bereich der EXE werden
direkt geladen und brauchen nicht zurückgeschrieben
werden.
<LI>Read-Write Bereiche werden zuerst direkt aus der
EXE geladen und im Speicher hinterlegt.
<LI>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) </LI></UL>Der VMM von Windows verwaltet mehrere
Listen für:
<UL>
<LI>freie Seiten, welche mit 0 initialisiert wurden
(zerofilled)
<LI>uninitialisierte freie Seiten, die noch alten
Inhalt haben
<LI>wartende Seiten, die Prozess zugewiesen waren und
nicht modifiziert wurden(standby pages)
<LI>wartende, aber modifizierte Seiten (modified
pages)
<LI>belegte Seiten, welchen einem Prozess zugewiesen /
referenziert sind (valid pages)
<LI>unbenutzbare Seiten, durch z.B. Hardwarefehler
(unusable pages) </LI></UL>
<H3>Wie arbeitet die Adressumrechnung der Multics? </H3>
<OL>
<LI>mit Segmentnummer wird Segmentdeskriptor
festgestellt
<LI>es wird geprüft, ob die Pagetable des Segmentes im
Speicher ist
<LI>ist sie nicht im Speicher tritt ein Segmentfehler
auf und es erfolgt ein Trap
<LI>ist sie im Speicher wird der Pagetableeintrag für
die angefragte Seite überprüft
<LI>falls Seite nicht im Speicher entsteht Page Fault
<LI>ist Seite im Speicher wird die physikalische
Adresse des Seitenursprungs aus dem Pagetableeintrag
entnommen
<LI>Der Offset wird zur gewonnenen Adresse
hinzuaddiert und die physikalische Adresse ist
berechnet. </LI></OL><EM>(nach
Tanenbaum)</EM><BR><BR>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.
<H3>Wie funktioniert die Adressumrechnung beim P2?
</H3>Intel Prozessoren besitzen ab dem i386 eine
<STRONG>LDT</STRONG> (local descriptor table) und eine
<STRONG>GDT</STRONG> (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.
<H3>Was haben Deskriptoren mit Sicherheit und
Segmentverwaltung zu tun? </H3>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:
<UL>
<LI>Level 0: Betriebssystem
<LI>Level 1, 2: Betriebssystemdienste, Treiber,
Systemsoftware
<LI>Level 3: Anwendungssoftware </LI></UL>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.
<H2>Zusammenfassung von Freispeicherverwaltung,
Segmentierung und Paging </H2>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.<BR><BR>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.<BR><BR>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.<BR><BR>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.<BR><BR>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. </TD>
<TD></TD></TR></TBODY></TABLE></TD>
<TD class=desc vAlign=top></TD></TR></TBODY></TABLE>
<TABLE cellSpacing=0 cellPadding=0 width="100%">
<TBODY>
<TR>
<TD>
<TABLE class=tutorialtable cellSpacing=0 cellPadding=0
border=0>
<TBODY>
<TR vAlign=top>
<TD class=tutorial vAlign=top align=left>
<H1>Kapitel 7 - Seitenersetzung </H1>
<TABLE width="100%">
<TBODY>
<TR>
<TD class=inhaltsliste>
<UL>
<LI>Seitenersetzungsalgorithmen wie FiFo, LRU...
<LI>Working Sets als dynamische Variante
<LI>Problem der Seitengröße
</LI></UL></TD></TR></TBODY></TABLE>
<H2>Was sind Seitenersetzungsalgorithmen? </H2>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...
<H3>Welcher wäre der beste Algorithmus zur
Seitenersetzung? </H3>Dieser ist theoretisch gegeben,
aber <STRONG>nicht umsetzbar</STRONG>. Die Seite die am
<STRONG>spätesten erst wieder verwendet</STRONG> 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.
<H3>Wie arbeitet die Seitenersetzung mit
Not-Recently-Used? </H3>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.<BR>Die zwei Bit stellen vier Klassen dar, welche
genutzt werden um einen Paging-Algorithmus zu
realisieren.
<OL>
<LI>nicht referenzierte und nicht modifizierte Seite
<LI>nicht referenzierte und modifizierte Seite
<LI>referenzierte und nicht modifizierte Seite
<LI>referenzierte und modifizierte Seite </LI></OL>LRU
wählt zufällig eine Seite aus der kleinstnummerierten
Klasse zum Entfernen aus.
<H3>Wie arbeitet die Seitenersetzung mit Fifo - First In
First Out? </H3>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 <STRONG>Alter der
Seiten sortiert</STRONG>. 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.<BR><BR>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.
<H3>Wie arbeitet die Seitenersetzung mit Second Chance?
</H3>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.
<H3>Wie arbeitet der Uhr-Seitenersetzungsalgorithmus?
</H3>Der Clock-Algorithmus arbeitet im Prinzip wie
Second Chance, nur das anstelle einer FiFo Liste eine
<STRONG>Ringliste</STRONG> 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.<BR><BR>Der
Uhr Algorithmus ist also eine Implementation von Second
Chance mit einer Ringliste.
<H3>Wie arbeitet die Seitenersetzung mit
Least-Recently-Used? </H3>Dieser Paging Algorithmus
versucht den Optimalen zu approximieren, indem es
versucht die Seiten zu entfernen, welche am Längsten
nicht mehr benutzt wurden.<BR><BR>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.
<H3>Wie arbeitet die Seitenersetzung LRU mit
Matrixumsetzung? </H3>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.<BR><BR>Wenn die notwendige Hardware (Matrix)
nicht vorhanden ist, muss ein anderer effizienter Paging
Algorithmus benutzt werden, der ohne jede Hardware
auskommt.
<H3>Wie arbeitet die Seitenersetzung NFU - Not
Frequently Used? </H3>Bei jeder Uhrunterbrechung wird
das <STRONG>Referenziert-Bit</STRONG> jeder Seite auf
einen Softwarezähler, welcher mit null initialisiert
wurde, hinzuaddiert. Es wird also versucht <STRONG>zu
zählen</STRONG>, 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.<BR><BR>Eine Modifikation von NFU
versucht LRU zu simulieren und diesen Fehler aufzuheben.
<H3>Wie arbeitet die Seitenersetzung mit Aging - LRU
durch Softwareemulation? </H3>
<OL>
<LI>Vor der Addition es Referenziert-Bits werden alle
Zähler um eins nach rechts geschoben<BR><BR>
<LI>das Refenziert-Bit wird auf das am weitesten links
stehende Bit addiert </LI></OL>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... <BR><BR>
<DIV class=HINT>
<UL>
<LI>Not-Recently-Used (referenziert und modifiziert
Bits - vier Zustände)
<LI>Least-Recently-Used (Seiten die lange nicht
benutzt worden auslagern) und LRU mit Matrixumsetzung
<LI>FiFo, Second Chance,
Uhr-Seitenersetzungsalgorithmus
<LI>Aging - LRU durch Softwareemulation
<LI>befindet sich die Seite nicht im Cache, muss sie
in der Translation Table gesucht werden </LI></UL>
<DIV align=right><EM>Merktabelle:
Seitenersetzungsalgorithmen</EM> </DIV></DIV>
<H2>Was sagt die Belady's Anomalie? </H2>Eine Erhöhung
der Seitenrahmen im Speicher, also mehr Speicher, heißt
nicht zwangsläufig eine Verringerung von Seitenfehlern!
<H2>Was passiert beim Einsatz einer schnelleren Platte
mit der Seitenfehlerrate? </H2>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.
<H2>Was sind Working Sets - dynamisches
Seitenaustauschverfahren? </H2>Prozess Arbeitsbereiche
werden eingesetzt und die Zahl der Seitenfehler weiter
zu minimieren. Ein Prozess unterliegt auch einer Art
<STRONG>Lokalität</STRONG>. Es werden im Mittel
bestimmte Seiten häufiger und Andere sogut wie nie oder
gar nicht zur Prozessabarbeitung benötigt. Man nennt
dies <STRONG>Referenzielle
Lokalität</STRONG>.<BR><BR>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.<BR><BR>Die gewonnene Information des Working
Sets kann verwendet werden, um den <STRONG>Clock
Algorithmus</STRONG> 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 <STRONG>übersprungen</STRONG>, egal ob im
Moment referenziert oder nicht.
<H3>Welche Problematik tritt bei der
Arbeitsmengenstrategie auf? </H3>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.
<H2>Welche Gefahr besteht bei Seitenaustauschverfahren?
</H2>Gefahr des <STRONG>Seitenflatterns</STRONG>
(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. <STRONG>Page
Damons</STRONG> können dem Abhilfe schaffen, weil sie
Prozesse auslagern, wenn nicht mehr ausreichend
Seitenrahmen im Speicher zur Verfügung stehen.
<H3>Was kann man gegen Trashing (Seitenflattern) tun?
</H3>Page Dämons benutzten, denn dadurch wird die Anzahl
der gleichzeitig aktiven Prozesse verringert und jedem
Prozeß stehen mehr Seitenrahmen zur Verfügung.
<H2>Wie wird die Seitengröße festgelegt? </H2>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
<STRONG>halb gefüllt</STRONG>, 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.<BR><BR>Verschwendung = Prozessgröße *
Seitentabelleneintragsgöße / Seitengröße + Seitengröße /
2<BR><BR><EM>Die Nullstellenberechnung der ersten
Ableitung in Abhängigkeit der Seitengröße ergibt
:</EM><BR><BR><STRONG>Optimale Seitengröße</STRONG> =
Wurzel aus 2 * Prozessgröße * Seitentabelleneintragsgöße
</TD>
<TD></TD></TR></TBODY></TABLE></TD>
<TD class=desc vAlign=top></TD></TR></TBODY></TABLE>
<TABLE cellSpacing=0 cellPadding=0 width="100%">
<TBODY>
<TR>
<TD>
<TABLE class=tutorialtable cellSpacing=0 cellPadding=0
border=0>
<TBODY>
<TR vAlign=top>
<TD class=tutorial vAlign=top align=left>
<H1>Kapitel 8 - Deadlocks </H1>
<TABLE width="100%">
<TBODY>
<TR>
<TD class=inhaltsliste>
<UL>
<LI>notwendige und hinreichende Bedingung
<LI>Deadlock-Erkennung und Vermeidung
<LI>Bankieralgorithmus
</LI></UL></TD></TR></TBODY></TABLE>
<H2>Was sind die notwendigen Bedingungen für Deadlocks?
</H2>
<OL>
<LI><STRONG>Mutual Exclusion</STRONG> (z.B. via
Druckerspooler über Ersatz-BM Buffer aufgelöst)
<LI><STRONG>Belegungs- und Wartebedingung</STRONG>
(Prozess kann weitere BM anfordern)
<LI><STRONG>Unterbrechbarkeitsbedingung</STRONG> (BM
können nicht entzogen werden)
<LI><STRONG>zyklische Wartebedingung</STRONG> (Zyklus
im Betriebsmittelgraph) </LI></OL>
<H2>Was sind die hinreichende Bedingungen für Deadlocks?
</H2>Es darf keine externe Betriebsmittelinstanz
bestehen.
<H2>Was ist ein Livelock? </H2>Es wurde ein
Betriebsmittel vergeben, es besteht aber keine
Verhinderung. Das BM könnte irgendwann wieder
freigegeben werden, aber der Zeitpunkt
unbekannt.<BR><BR>Z.B.
<STRONG>Priotitätsscheduling</STRONG> (langwierige
Prozesse verhungern da benachteiligt)
<H2>Wie kann man Deadlocks auflösen oder umgehen? </H2>
<OL>
<LI>Vogel-Strauß Algorithmus (einfach Ignorieren)
<LI>Versuchen zu Erkennen und zu beheben (Topologische
Sortierung des BM-Graphs oder Vektoren-Matrix
Variante)
<LI>dynamisches Verhindern (vor Zuteilung auf Deadlock
prüfen)
<LI>konzeptionelles Vermeiden (eine der notwendigen
Bedingungen eliminieren) </LI></OL>
<H3>Welche Prozesse sind an einem Deadlock beteiligt?
</H3>Prozesse die mehrere Betriebsmittel mit jeweils
<STRONG>exklusiven Zugriff</STRONG> benötigen.
<H3>Wie kann man Deadlocks (im Voraus) erkennen?
</H3>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
<STRONG>Preclaiming</STRONG> 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.
<H3>Wie werden Deadlocks beseitigt? </H3>Durch
<STRONG>Abbruch</STRONG> der beteiligten Prozesse und
Freigabe der belegten Betriebsmittel. Siehe
<STRONG>optimistische Sperrverfahren</STRONG> bei DBMS.
<H2>Wie können Deadlocks vermieden werden?
</H2><BR><B>Möglichkeit 1</B><BR><BR>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.<BR><BR><B>Möglichkeit
2:</B><BR><BR>Bei Anforderung zusätzlicher
Betriebsmittel werden alle bisher reservierten
Betriebsmittel freigegeben und dann zusammen mit den
zusätzlichen Betriebsmitteln erneut angefordert (Form
von Preclaiming).<BR><BR><B>Möglichkeit
3</B><BR><BR>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.<BR><BR><B>Möglichkeit 4</B> Der Banker
Algorithmus als Verfahren zur Erkennung sicherer
Systemzustände bei der Verteilung von Ressourcen.
<H3>Wie arbeitet der Bankieralgorithmus? </H3>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.<BR><BR><STRONG>Beispiel
Bankieralgorithmus</STRONG><BR><BR>Der Banker habe 10
Einheiten eines Betriebsmittels verfügbar.
<OL>
<LI>Das Limit von Kunde A betrage 8 Einheiten.
<LI>Das Limit von Kunde B ist 7 Einheiten.
<LI>A hat zur Zeit 5 Einheiten belegt
<LI>und B hat 2 Einheiten reserviert </LI></OL>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.
<H3>Warum funktioniert die Deadlock-Vermeidung bei
linearer Ordnung der Betriebsmittel? </H3>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. </TD>
<TD></TD></TR></TBODY></TABLE></TD>
<TD class=desc vAlign=top></TD></TR></TBODY></TABLE>
<TABLE cellSpacing=0 cellPadding=0 width="100%">
<TBODY>
<TR>
<TD>
<TABLE class=tutorialtable cellSpacing=0 cellPadding=0
border=0>
<TBODY>
<TR vAlign=top>
<TD class=tutorial vAlign=top align=left>
<H1>Kapitel 9 - Dateisysteme </H1>
<TABLE width="100%">
<TBODY>
<TR>
<TD class=inhaltsliste>
<UL>
<LI>Freispeicherverwaltung
<LI>Verschiedene Dateisysteme wie NTFS
<LI>Dateideskriptoren
<LI>Was sind I-Nodes?
</LI></UL></TD></TR></TBODY></TABLE>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.
<H2>Was ist eine Datei? </H2>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.
<H2>Welche Möglichkeiten der Freispeicherverwaltung von
File Systemem gibt es? </H2>
<OL>
<LI>Kontinuierliche Allokation - schlecht wenn Datum
angehangen werden soll
<LI>Verkettete Listen - schlecht, da Wahlfreier
Zugriff extrem langsam
<LI>Listen mit Zuordnungstabellen - Zuordnungstabellen
erlauben schnellen wahlfreien Zugriff (FAT)
<LI>Indizierte Speicherung
<LI>Indirekt indizierte Speicherung </LI></OL>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.
<H3>Wie funktioniert das Prinzip der Verketteten Listen?
</H3>Listen sind langsamer als kontinuierliche
Allokation, bieten nur wahlfreien Zugriff und besitzen
nur geringe Fehlertoleranz. Dafür werden aber nur sehr
<STRONG>wenig Verwaltungsdaten</STRONG> 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.
<H3>Wie funktioniert das Prinzip der Listen mit
Zuordnungstabellen </H3>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.
<H3>Wie funktioniert indizierte Speicherung </H3>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
externen 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.<BR><BR>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.
<H3>Wie funktioniert indirekt indizierte Speicherung
</H3>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.
<H3>Was ist das Besondere an Unix FS Ext 2? </H3>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.
<H2>Welche Festplatten Scheduling-Algorithmen kennen
Sie? </H2>
<UL>
<LI>First Come First Serve
<LI>Shortest Seek Time First (Sektor mit kürzesten
Suchzeit suchen)
<LI>Scan (Diskarm bewegt sich von einem Ende zum
Anderen und bearbeitet Requests)
<LI>C-Scan (Diskarm wird bei Erreichen des Endes
wieder auf Anfang zurückgesetzt - kreisförmig)
<LI>Look (Wie C-Scan, nur wird nur so weit wie
notwendig zurückgesetzt)
<LI>Look (Wie C-Look, nur kreisförmig) </LI></UL>
<H3>Welche Bewertungskriterien für
Festplattenalgorithmen gibt es? </H3>
<UL>
<LI>Caching
<LI>Demand Paging wichtiger als E/A der Anwendungen
<LI>Robustheit nach Systemabstürzen
<LI>Berücksichtigung der hohen
Rotationsgeschwindigkeiten moderner Platten
<LI>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)
</LI></UL>
<H2>Wie arbeitet FAT - File Allocation Table? </H2>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 (<STRONG>abgesetzte verkettete
Allokation</STRONG>). 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).
<H3>Welche Verzeichniseinträge hat FAT? </H3>
<UL>
<LI>Dateiname (8+3 Zeichen)
<LI>Attribut-Byte
<LI>Zeit und Datum der letzten Bearbeitung
<LI>Erste Zuordnungseinheit der Datei
<LI>Dateilänge </LI></UL>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.
<H2>Wie arbeitet NTFS? </H2>NTFS heißt New Technology
File System. NTFS ist mit einem
<STRONG>Zugriffsschutz</STRONG> 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
<STRONG>Master File Table</STRONG>, in welcher jede
Datei einen Eintrag besitzt. Zusammenhängende Bereiche
(extents) werden als <STRONG>B-Baum</STRONG>
organisiert.
<H3>Was ist die MFT von NTFS? </H3>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 <STRONG>B-Baums</STRONG>, dessen
"Blätter" die Verweise auf die zusammenhängenden
Dateibereiche (Extent oder Lauf)
enthalten.<BR><BR>Ähnlich wie die Inode-Tabelle beim
UNIX-System stellt die MFT ein flaches Dateisystem dar.
Über die Verzeichnisse wird darauf die bekannte
Baumstruktur definiert.
<H3>Wie werden unter NTFS Dateien eindeutig
identifiziert? </H3>Jede Datei ist eindeutig über eine
<STRONG>ID</STRONG> identifizierbar. Diese ID ist die
Satznummer ihres Eintrages in der
<STRONG>MasterFileTable</STRONG> (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)
<H3>Wie werden unter NTFS Verzeichnisse umgesetzt?
</H3>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
<STRONG>B-Baum</STRONG>.
<H3>Welche Spezialdateien hat NTFS? </H3>
<UL>
<LI>MasterFileTable (MFT)
<LI>MFT2: enthält die ersten 16 Einträge der MFT als
Backup
<LI>Eine Logdatei (Daten über Transaktionen zum
Wiederherstellen der Daten- bzw. der
Dateisystemkonsistenz)
<LI>Datenträgerdatei enthält den Namen des
Datenträgers, Versionsnummer des Dateisystems und
eventuellen Verdacht auf Inkonsistenz
<LI>Wurzelverzeichnis
<LI>Cluster-Bitmap-Datei für belegte und freie Cluster
des Datenträgers
<LI>Bootdatei mit dem Startcode für NT
<LI>BadClusterDatei, welche Verweise auf defekte
Cluster enthält </LI></UL>
<H2>Wie arbeiten I-Nodes - Das Unix Dateisystem </H2>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 "<STRONG>einfach indirekter Block</STRONG>"
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.<BR><BR><IMG alt=I-Nodes
src="http://www.kreissl.info/pics/images/bs_03.gif"
border=0><BR><BR>
<H2>Was sind Dateideskriptoren? </H2>Jedem Prozess ist
eine eigene Benutzer-Filedecriptor-Tabelle zugeordnet.
Ruft ein Prozess <EM>open</EM> oder <EM>create</EM> 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.
<H3>Was enthält die globale Dateitabelle des Systems?
</H3>Den Offset in Byte zum Dateianfang für den nächsten
<EM>read-</EM> bzw. <EM>write-Befehl</EM> des Benutzers
und die <STRONG>Zugriffsberechtigungen</STRONG> für den
Prozeß, der die Datei eröffnet hat. Die
Benutzer-Filedecriptor-Tabellen enthalten dagegen nur
die geöffneten Dateien eines Prozesses.<BR><BR><IMG
alt=Dateideskriptoren
src="http://www.kreissl.info/pics/images/bs_04.gif"
border=0><BR><BR>
<H3>Was beinhaltet ein I-Node? </H3>
<UL>
<LI>Dateityp
<LI>Eigentümer
<LI>Gruppe des Eigentümers
<LI>Zugriffsschutzbits
<LI>Datumseinträge
<LI>Anzahl der Links für diesen I-Node
<LI>Zeiger auf den Dateiinhalt </LI></UL>
<H2>Geräte als I/O Dateien </H2>Es gibt zwei Klassen
solcher Dateien. Blockorientierte Spezialdateien und
Zeichenorientierte Spezialdateien.
<H3>Was sind Blockorientierte Spezialdateien?
</H3>Blockorientierte Spezialdateien werden benutzt, um
Geräte zu modellieren, die aus frei adressierbaren
Blöcken bestehen. ( <STRONG>random access
devices</STRONG> 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.
<H3>Was sind Zeichenorientierte Spezialdateien?
</H3>werden benutzt, um Geräte zu modellieren, die aus
<STRONG>Zeichenströmen</STRONG> 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.
<H2>Wie ist das Unix Dateisystems aufgebaut?
</H2><BR><BR><IMG alt=Unix
src="http://www.kreissl.info/pics/images/bs_05.gif"
border=0><BR><BR>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.<BR><BR>Der <STRONG>Superblock</STRONG>
beschreibt den <STRONG>Aufbau des Dateisystems</STRONG>.
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:
<UL>
<LI>Größe des Dateisystems
<LI>Anzahl der freien Blöcke
<LI>Liste der freien Blöcke
<LI>Index auf den nächsten freien Block </LI></UL>
<UL>
<LI>Größe der I-Nodeliste
<LI>Anzahl der freien Inodes im Dateisystem
<LI>Liste der freien Inodes
<LI>Index auf den nächsten freien Inode in dieser
Liste </LI></UL>
<UL>
<LI>Sperrkennzeichen für die Listen freier Blöcke und
Inodes
<LI>Flag für durchgeführte Änderungen im Superblock
</LI></UL>
<H2>Wie kann ein Prozeß auf Daten auf der Festplatte
zugreifen? </H2>
<OL>
<LI>Das virtuelle Gerät hinter dem die Festplatte
verborgen wird, heißt Datei.
<LI>Der Prozeß öffnet die Datei und erhält eine
Datei-ID die auf eine Datei-Deskriptor-Tabelle
verweist.
<LI>Es folgt die Adressierung der Sektoren.
<LI>Über die Sektoradresstabelle (FAT oder I-Node
Tabelle) werden die Adressen der Blöcke ermittelt
<LI>Es folgt die Übertragung der Blöcke zum
Hauptspeicher
<LI>Zugriff erfolgt nach speziellem Prinzip, wie z.B.
SSN
<LI>zur Minimierung der Suchzeit muss Wahl einer
effizienten Positionierungsstrategie
<LI>Durch einen Interrupt oder ein spezielles Register
teilt der Controller dem BS das Ende der Übertragung
mit. </LI></OL>
<H3>Wie wird eine Datei unter Unix gesucht? </H3>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.<BR><BR><STRONG>Beispielzugriff:</STRONG>
<OL>
<LI>Es soll die Datei <EM>/var/log/messages</EM>
betrachtet werden
<LI>Der I-Node des Wurzelverzeichnisses
<STRONG>"/"</STRONG> steht an einer definierten Stelle
auf der Platte
<LI>Es wird das Verzeichnis <STRONG>"var"</STRONG> im
Wurzelkatalog (auch eine Datei) gesucht
<LI>In diesem Katalog steht der dazugehörige
<STRONG>I-Node</STRONG> der auf das Verzeichnis bzw.
den Katalog "var" verweist
<LI>nun wird in der Katalogdatei "var" nach
<STRONG>"log"</STRONG> gesucht und der dazugehörige
<STRONG>I-Node</STRONG> gelesen
<LI>Nun kann über den I-Node nach dem Eintrag
<STRONG>"messages"</STRONG> in "log" gesucht werden
<LI>Der I-Node der Datei "messages" wird nun in die
globale <STRONG>Dateideskriptortabelle</STRONG> und
die lokale Deskriptortabelle des Prozesses geladen
<LI>Dieser Dateideskriptor ist das
<STRONG>Handle</STRONG>, mit dem der Prozess auf die
Datei zugreifen kann
<LI>Nach eine <STRONG>Close()</STRONG> wird der I-Node
aus der Dateideskriptorliste wieder entfernt.
</LI></OL></TD>
<TD></TD></TR></TBODY></TABLE></TD>
<TD class=desc vAlign=top></TD></TR></TBODY></TABLE></TD></TR>
<TR>
<TD>
<TABLE cellSpacing=1 cellPadding=1 width=500 border=0>
<TBODY>
<TR>
<TD> </TD>
<TD>
<P><BR><EM><B>Quellen</B><BR>Andrew S. Tanenbaum,
Computerarchitektur<BR>Andrew S. Tanenbaum, Moderne
Betriebssysteme<BR>Petterson, Computer Architectur &
Design<BR>Christian Märtin, Rechnerarchitekturen<BR>Kalfa,
Skript und Vorlesung<BR>Word Wide Web, Verschiedenste
Seiten<BR></EM><BR>Ausgearbeitet von Holger Kreissl. Online
link
http://www.kreissl.info/diggs/bs_inhalt.php<BR><BR></P></TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE></TD></TR>
<TR>
<TD class=pagefooter> </TD></TR>
<TR>
<TD></TD></TR></TBODY></TABLE></TD></TR></TABLE>
<SCRIPT type=text/javascript>var gaJsHost = 1);</SCRIPT>
<SCRIPT type=text/javascript>try{var pageTracker = _gat._getTracker(„UA-982689-1“);pageTracker._trackPageview();} catch(err) {}</SCRIPT> <!– <script src=„http://www.google-analytics.com/urchin.js“ type=„text/javascript“> </script> <script type=„text/javascript“> _uacct = „UA-982689-1“; urchinTracker(); </script> –> <SCRIPT language=javascript src=„http://www.kreissl.info/SyntaxHighlighter/Scripts/shCore.js“ type=text/javascript></SCRIPT>
<SCRIPT language=javascript src=„http://www.kreissl.info/SyntaxHighlighter/Scripts/shBrushCSharp.js“ type=text/javascript></SCRIPT>
<SCRIPT language=javascript src=„http://www.kreissl.info/SyntaxHighlighter/Scripts/shBrushXml.js“ type=text/javascript></SCRIPT>
<SCRIPT language=javascript type=text/javascript> dp.SyntaxHighlighter.ClipboardSwf = '/SyntaxHighlighter/Scripts/clipboard.swf'; dp.SyntaxHighlighter.HighlightAll('code'); </SCRIPT> </BODY></HTML> </html>
1)
„https:“ == document.location.protocol) ? „https://ssl.“ : „http://www.“);document.write(unescape(„%3Cscript src='“ + gaJsHost + „google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E“