diff options
Diffstat (limited to 'docs/VS2007/verteilte-systeme.tex')
| -rw-r--r-- | docs/VS2007/verteilte-systeme.tex | 2857 |
1 files changed, 0 insertions, 2857 deletions
diff --git a/docs/VS2007/verteilte-systeme.tex b/docs/VS2007/verteilte-systeme.tex deleted file mode 100644 index 9c3e771..0000000 --- a/docs/VS2007/verteilte-systeme.tex +++ /dev/null @@ -1,2857 +0,0 @@ -\documentclass[bibtotocnumbered, headsepline,normalheadings]{scrreprt} - -\usepackage[latin1]{inputenc} -\usepackage{german} -\usepackage{scrpage} -\usepackage{eurosym} -\usepackage{alltt} -\usepackage{graphicx} -\usepackage{hyperref} - -\pagestyle{headings} - -\begin{document} -\title{Vorlesungsmitschrift \\ Verteilte Systeme \\ SS 2007 FH-Aachen} -\author{Bei Prof. Dr.-Ing. O{\ss}mann \\ \\ Getext von Paul B\"{u}tow} -\date{Letzte Aktualisierung: \today} -\maketitle - -\tableofcontents - -\newcommand{\m}[1]{$~\qquad {#1}$\\} -\newcommand{\n}[1]{$~\qquad {#1}$} -\newcommand{\q}{$ ~ \qquad $} -\newcommand{\bs}{$\backslash$} -\newcommand{\pre}[1]{\texttt{{#1}}} -\newcommand{\set}[1]{\{{#1}\}} -\newcommand{\ra}{ \rightarrow } -\newcommand{\Ra}{ \Rightarrow } -\newcommand{\E}{$\epsilon$} -\newcommand{\N}{\mbox{$I\!\!N$}} - -\chapter{Diverses} - -\section{Ein bischen Blabla...} -Ich garantiere nicht, dass der Inhalt dieses Dokuments weder korrekt noch vollst\"{a}ndig ist. \textit{Kursiv geschriebene Kommentare habe ich selbst hinzugef\"{u}gt.} Bei Fehlern bitte per E-Mail (\texttt{skript@paul.buetow.org}) an mich wenden! - -\subsection{Anmerkung zu den Grafiken} -Die Grafiken sind etwas pixelig/unscharf. Ich bitte dies zu entschuldigen. Sie erf\"{u}llen jedoch ihren Zweck. - -\subsection{Download URL} -Das aktuelle Dokument mitsamt Sourcen liegt unter:\\ - -\url{ftp://ftp.buetow.org/pub/studium/FHAC\_VS-SS07/} - -\subsection{Technische Informationen} -Falls es interessiert: Dieses Dokument wurde erstellt mithilfe von: -\begin{itemize} - \item LaTeX, rubber, make - \item Dia (http://www.gnome.org/projects/dia/) - \item Vim (http://www.vim.org) - \item FreeBSD (http://www.FreeBSD.org) -\end{itemize} - -\chapter{Vorlesung} - -\section{\"{U}berblick} - -\begin{itemize} - \item Grundeigenschaften - \item Systemmodelle - \item Netzwerke, Interprozesskommunikation - \item Verteilte Objekte, entfernte Aufrufe - \item Verteilte Dateisysteme - \item Namensdienste - \item Zeit und globale Zust\"{a}nde - \item Koordination und Nebenl\"{a}ufigkeitskontrolle - \item Transaktionen - \item Replikationen -\end{itemize} - -\section{Literatur} - -\begin{itemize} - \item Coulouris, Dollimore, Kindberg ``Verteilte Systeme'' - \item Tanenbaum, van Steen ``Verteilte Systeme'' -\end{itemize} - -\section{Grundeigenschaften} - -Grundeingenschaften verteilter Systeme: Zusammenarbeit mehrerer Komponenten auf vernetzten Computern. -Koordination und Kommunikation erfolgt durch den Austausch von Nachrichten.\\ -\\ -Daraus ergibt sich die Nebenl\"{a}ufigkeit der Komponenten. Keine globale Uhr. Unabh\"{a}ngige Ausf\"{a}lle von Komponenten. - -\section{Beispiele} - -\begin{itemize} - \item Tauschb\"{o}rsen - \item Sichere Speicherung auf verteilten Servern - \item Mobiles und Allgegenw\"{a}rtiges - \item Rechnen -\end{itemize} - -\section{Motivation} - -Motivation f\"{u}r den Aufbau verteilter Systeme: Gemeinsame Nutzung von Ressourcen.\\ -\\ -Was ist der Unterschied zur Betriebssystem-Motivation? - -\begin{itemize} - \item Heterogenit\"{a}t der Komponenten - \item Offenheit (weltweit akzeptierte Standards) - \item Sicherheit bei Teilausf\"{a}llen (Fehler, Angriffe) - \item Skalierbarkeit (Systeme wachsen) -\end{itemize} - -\section{Beispiele f\"{u}r gemeinsam genutzte Ressourcen} - -\begin{itemize} - \item Hardware: Drucker, Festplatten - \item Daten: Dateien - \item Dienste z.B. Suchmaschinen -\end{itemize} - -\section{Client Server Modell} - -In verteilten Systemem verwendet man oft das ``Client Server Modell''. Ein Server bietet einen Dienst (Service) an (``passiv''). Ein Client fragt bei einem Server nach einen Dienst (``request for service'').\\ -\\ -Die Dienste bergrenzen den Ressourcenzugriff auf eine wohldefinierte Operationsmenge. -Implementation von Servern erfolgt \"{u}blicher Weise durch einen Prozess auf einem vernetzten Computer. - -\begin{enumerate} - \item Client: Ruft eine Operation auf dem Server auf - \item Server: Schickt Antwort - \item Client: Erh\"{a}lt die Antwort -\end{enumerate} - -$\ra$ ``Eine Interaktion'', ``remote invocation''\\ -\\ -Remote hei{\ss}t nicht ``geometrisch entfernt''. Besser: Es wird ein Dienst erbracht, der in einem anderen Adressraum bereitliegt. - -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=100mm]{vs1.png} -\end{center} -\end{figure} -\subsubsection{Frage} -Gibt es in Java einen Adressraum? Antwort: Ja (Siehe NullPointerException).\\ -\\ -Ein Prozess kann gleichzeitig Client und Server sein. -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=105mm]{vs3.png} -\end{center} -\end{figure} -\"{A}hnliche Beziehung: Funktions- bzw. Methodenaufruf. Server werden ``st\"{a}ndig'' ausgef\"{u}hrt. Clients reden mit der \"{u}bergeordneten Applikation. Das Client-Server Modell beschreibt viele verteilte Systeme (nicht alle). - -\section{Ziele beim Design eines verteilten Systems} - -Ber\"{u}cksichtigt werden: - -\begin{itemize} - \item Heterogenit\"{a}t - \item Offenheit - \item Skalierbarkeit - \item Sicherheit (gegen Angriffe) - \item Fehlertoleranz - \item Nebenl\"{a}ufigkeit - \item Transparenz -\end{itemize} -\subsection{Heterogenit\"{a}t} -Heterogenit\"{a}t in den Bereichen -\begin{itemize} - \item Netzwerk - \item Computerhardware - \item Betriebssysteme - \item Programmiersprachen -\end{itemize} -Wesentliches Hilfsmittel zur Implementation heterogener Systeme: Einf\"{u}hrung einer Middleware. -Middleware ist eine Softwareschicht, die eine Programmierabstraktion zur Verf\"{u}gung stellt, und die Heterogenit\"{a}t des darunterliegenden Systems verbirgt. -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=30mm]{vs4.png} -\end{center} -\end{figure} -\\ -Beispiele: Java, RMI, CORBA, SQL, RPC. (Bereitstellung einer einheitlichen Programmierschnittstelle). - -\subsection{Offenheit} -Ziel Offenheit (Um sp\"{a}ter Erweiterungen vornehmen zu koennen). Z.B. Hinzuf\"{u}gung neuer Dienste f\"{u}r unterschiedliche Client-Programme. -\begin{itemize} - \item Ziel wird erreicht durch Offenlegung der Spezifikation aller Softwareschnittstellen - \item Wird unterst\"{u}tzt durch Standardisierung der Schnittstellen. -\end{itemize} -Beispiele f\"{u}r Offenheit: -\begin{itemize} - \item Internet-Protokolle - \item RFC (Request For Comment)\\ - \url{http://www.ietf.org} -\end{itemize} - -\subsection{Skalierbarkeit} -Die Leistungsf\"{a}higkeit von Systemen soll durch Hinzuf\"{u}gen von Komponenten steigen. Steigender Bedarf an Dienstleistungen mu{\ss} mit beschr\"{a}nkten Kosten befriedigt werden.\\ -\\ -Ist ein Linux-Cluster ein skalierbares System? Nur schwer skalierbar (wg. Neuverkabelung bei Hinzunahme neuer Rechner).\\ -\\ -Wachstum bringt oft (relativen) Verlust an Leistung. Beispiel: Finden eines Objekts unter $n$ (Skalierungsgr\"{o}{\ss}e) Objekten. - -\begin{itemize} - \item Bei linearem Suchen: Aufwand $\sim n$ - \item Bei bin\"{a}rem Suchen: Aufwand $\sim log(n)$ -\end{itemize} -Angestrebt wird ein Aufwandswachstum $\approx log(n)$ ($n$ ``Gr\"{o}{\ss}e des Systems'').\\ -\\ -Weiteres Problem: Manche Ressourcen ersch\"{o}pfen sich! Beispiel: IP-Adressen. Leistungsengp\"{a}sse sollten durch Dezentralisierung vermieden werden!\\ -\\ -Anfangs: Ein zentraler DNS-Server, der ``alles'' in einer Datei wusste. - -\subsection{Behandlung von Fehlern} - -Erkennen von Fehlern: - -\begin{itemize} - \item Pr\"{u}fsummen (``leicht m\"{o}glich'') - \item Absturz eines Servers schwer zu erkennen -\end{itemize} -Maskierung von Fehlern: -\begin{itemize} - \item Mehrfaches \"{U}bertragen von Nachrichten - \item Mehrfache Speicherung von Daten -\end{itemize} -Frage: Greifen diese Ma{\ss}nahmen garantiert? Nein. Absolute Garantien kann man nie erwarten. Im Normalfall kann man die Sicherheit jedoch ausreichend ``hochschrauben''.\\ -\\ -``Tolerieren von Fehlern'' ist eine weitere Vorgehensweise. -\begin{itemize} - \item Weiterleitung von Fehlern an den Benutzer (\"{u}bergeordnete Schicht). Beispiele: - \begin{enumerate} - \item Browser findet Seite nicht - \item Java: Exception - \item C: Nichts (nur einen Crash) - \end{enumerate} - \item Oft kann die Schicht, die den Fehler feststellt, nicht entscheiden, wie weiter vorzugehen ist. -\end{itemize} -Zur Maskierung von Fehlern verwendet man oft redundante Komponenten. Beispiele: -\begin{itemize} - \item Mehrere Routen im Netzwerk - \item DNS: Jede Tabelle auf mehreren Servern - \item Replizierte Datenbanken (Techniken sp\"{a}ter im Detail) -\end{itemize} - -\subsection{Nebenl\"{a}ufigkeit} -``Gleichzeitige'' Benutzung von einer Ressource durch mehrere Benutzer. Ohne Nebenl\"{a}ufigkeit h\"{a}tten wir die sequentielle Benutzung von Ressourcen. -$\ra$ Schlechter Durchsatz. -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=33mm]{vs5.png} -\end{center} -\end{figure} -Im Allgemeinen lassen Server viele Clients gleichzeitig zu. Ressource sei als Objekt gekapselt (Siehe Bild).\\ -\\ -In vielen F\"{a}llen ist die Synchronisation notwendig um inkonsistente Ergebnisse zu vermeiden. Objekte, die gemeinsam genutzte Ressourcen verwalten, m\"{u}ssen in einer nebenl\"{a}ufigen Umgebung \underline{korrekt} arbeiten. - -\subsection{Transparenz} -Transparenz bedeutet, dass der Benutzer gewisse Details nicht ber\"{u}cksichtigen mu\ss, die die Implementation effizient machen. - -\begin{itemize} - \item \textbf{Zugriffstransparenz:} Lokale und entferne Zugriffe auf Objekte erfolgen mit den gleichen Methoden. Wenn man Sockets verwendet, kann man Nachrichten lokal und entfernt gleichartig verschicken. - \item \textbf{Orts- und Positionstransparenz:} Man kann auf Ressourcen zugreifen, ohne ihren Ort zu kennen. Man kann die Ressourcen von verschiedensten Orten aus benutzen. - \item \textbf{Nebenl\"{a}ufigkeitstransparenz:} Gemeinsame ``gleichzeitige'' Nutzung ohne Beeintr\"{a}chtigung. - \item \textbf{Replikationstransparenz:} Man arbeitet mit Repliken (Kopien) ohne Beeintr\"{a}chtigung. - \item \textbf{Fehlertransparenz:} Partielle (teilweise) Ausf\"{a}lle beeintr\"{a}chtigen den Benutzer nicht. - \item \textbf{Leistungs- und Skalierungstransparenz:} Das System kann neu konfiguriert oder erweitert werden, um h\"{o}here Leistungen zu erzielen. -\end{itemize} - -\section{Systemmodelle} -Modelle heben strukturierte Eigenschaften von Systemen hervor und erm\"{o}glichen eine einheitliche Sichtweise auf verschiedenartige Realisationen. - -\begin{itemize} - \item \textbf{Architektonisches Modell:} Platzierung von Komponenten. Verbindungen und Beziehungen zwischen Komponenten. - \item \textbf{Interaktionsmodell:} Zusammenspiel zwischen Teilen beim Nachrichtentausch. - \item \textbf{Fehlermodell:} Beschreibung von Fehlerm\"{o}glichkeiten der Prozesse und Kommunikationskan\"{a}le. Festlegung was man als ``korrekt'' bzw. ``zuverl\"{a}ssig'' interpretiert. - \item \textbf{Sicherheitsmodell:} Beschreibung von Gefahren durch Angriffe und Abwehrma{\ss}nahmen. -\end{itemize} -\subsection{Beispiele f\"{u}r architektonische Modelle} -\begin{itemize} - \item Client - Server - \item Peer to Peer (gleichrangige Prozesse) - \item Schichten-Architektur -\end{itemize} -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=60mm]{vs6.png} -\end{center} -\end{figure} -Die Middleware stellt zur Verf\"{u}gung: -\begin{itemize} - \item Entfernte Methodenaufrufe - \item Kommunikation in Gruppen - \item Benachrichtigung \"{u}ber Ereignisse - \item Replikation von Daten - \item Namensdienste (z.B. Matr.-Nr. in einer HS) - \item Sicherheitskonzepte - \item Transaktionen -\end{itemize} -Die \"{U}bertragung von Aufgaben an die Middleware vereinfacht den Entwurf und die Implementation von verteilten Systemen.\\ -\\ -Aber es gibt Funktionalit\"{a}ten, die vollst\"{a}ndig und zuverl\"{a}ssig nur bei Kenntnis der Applikation implementiert werden k\"{o}nnen. Solche Funktionen kann man nicht vollst\"{a}ndig in Middleware verstecken.\\ -\\ -\textbf{Beispiel:} Ist TCP/IP die geeigente Middleware um Sicherheit beim Transport von E-Mails zu gew\"{a}hrleisten?\\ -\\ -$\ra$ TCP/IP ist daf\"{u}r nicht geeignet, weil z.B. keine geeigneten Ma{\ss}nahmen gibt, um l\"{a}ngere Ausf\"{a}lle von Servern zu maskieren! - -\section{Interaktionsmodelle} -\begin{itemize} - \item Wer kommuniziert mit wem, wann, warum, ... ? - \item Wie beeinflusst das Timing von Nachrichten die Kommunikation und den Ablauf? - \item Was ist der ``Zustand'' von einem verteilten Algorithmus? -\end{itemize} - -\subsection{Synchrones verteiltes System} -\begin{itemize} - \item F\"{u}r die Ausf\"{u}hrungszeit zu jedem Schritt eines Prozesses gibt es bekannte obere und untere Schranken. - \item Jede Nachricht wird innerhalb einer begrenzten Zeit (fehlerfrei) empfangen. - \item Die Abweichungsgeschwindigkeit von lokalen Uhren im Bezug wahren Zeit ist beschr\"{a}nkt. (\textit{Uhren gehen eigentlich nie zu 100 Prozent gleich. Die Abweichungsgeschwindigkeit ist das, wie schnell Uhren ``auseinanderwandern''}) -\end{itemize} -Das sind sehr harte Forderungen! Von normalen Systemen sind diese nicht zu erf\"{u}llen. \textit{Dieses Modell ist eigentlich ein Wunschmodell.} (Wahrscheinliche Werte, Mittelwerte usw. sind oft leicht zu erf\"{u}llen). - -\subsection{Asynchrones verteiltes System} -\begin{itemize} - \item Keine Begrenzung f\"{u}r Prozessausf\"{u}hrung - \item Unbegrenzte Nachrichtenverz\"{o}gerung - \item Uhrabweichungen -\end{itemize} -Schon das ``Einigungsproblem'' zwischen 2 Teilnehmern im asynchronen System ist nicht l\"{o}sbar. - -\section{Zeit und globale Zust\"{a}nde} -F\"{u}r Ereignisse gilt: -\begin{itemize} - \item Man will wissen, ob ein Ereignis vor oder nach einem anderen Ereignis stattfand (\textit{Wir denken bisher mit vor und nach an die Zeit, sp\"{a}ter werden wir auch an was Anderes denken}). - \item Man will wissen, ob man alle Informationen hat, die zu einem bestimmten Ereignis gef\"{u}hrt haben. - \item Man will wissen, ob ein System (aus mehreren Komponenten) sich (zu einem Zeitpunkt) in einem Zustand befunden hat. -\end{itemize} -\textbf{Ansatz 1:} Versuche Uhren zu bauen\\ -\\ -\q $N$ Prozesse (evtl. auf verschiedenen Rechnern)\\ -\\ -\q Die echte wahre Zeit sei $t$.\\ -\\ -\q Hardwareuhr: $H_i(t) \quad i = 1, ..., N$\\ -\\ -\q Softwareuhr: $C_i(t) = \alpha * H_i(t) + \beta$\\ -\\ -Ziele: -\begin{enumerate} - \item $C_i(t) \approx t$\\ - \\ - $C_i(t) - t$ hei{\ss}t Uhrabweichung von Uhr $i$ zum Zeitpunkt $t$. - \item $C_i(t) \approx C_j(t)$\\ - \\ - $C_i(t) - C_j(t)$ hei{\ss}t Synchronisationsfehler zwischen den Uhren $i$ und $j$ zum Zeitpunkt $t$. -\end{enumerate} -Uhren werden ``synchronisiert''. $S(t)$ sei eine Referenzuhr (z.B. UTC). -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=115mm]{gps.png} -\end{center} -\end{figure} - -\begin{enumerate} - \item \underline{Externe Synchronisierung} \"{u}ber einem Zeitintervall gilt f\"{u}r alle $t \in I$:\\ -\\ -\q $|S(t) - C_i(t) | < D$ f\"{u}r alle $i = 1, ..., N$\\ -\\ -So heissen die Uhren $C_i$ mit $i = 1, ..., N$ extern synchronisiert mit Genauigkeit $D$. ($D$ ist fest f\"{u}r alle $i$, $t$). Uhrabweichung in $I$ ist kleiner als $D$.\\ -\\ -$5$ Sekunden Abweichungen pro Tag: $\frac{5s}{24 * 3600s} = 57 * 10^{-6} = 57ppm$\\ -\\\textit{Bei billigen Uhren die man im Laden bekommt kann man leicht $10ppm$ erreichen. Atomuhren liegen bei einem Faktor von ca. $10^{-15}$.} - \item \underline{Interne Synchronisierung} git f\"{u}r alle $t \in I$ und $i,j \in {1, ..., N}$ dass\\ - \\ - \q $|C_i(t) - C_j(t) | < D$\\ - \\ - so heissen die Uhren intern synchronisiert mit Genauigkeit $D$. (Uhren stimmen untereiander bis auf $D$ \"{u}berein. -\end{enumerate} -Ist ein System extern $D$-Synchronisiert, ist es intern garantiert $2D$-synchronisiert. Wenn ein System intern $D$-Synchronisiert ist, kann das zugeh\"{o}rige externe $D$ beliebig gro{\ss} sein. - -\subsection{Einige Korrektheitsbegriffe f\"{u}r Uhren} - -\textit{Eine Uhr die still steht, geht 2 mal am Tag richtig. Eine Uhr die 1 Minute vor geht, geht immer falsch?!? Es ist nicht einfach die Korrektheit einer Uhr zu definieren.} -\ -\begin{enumerate} - \item Eine Hardwareuhr hei{\ss}t korrekt, wenn ihre Abweichgeschwindigkeit (drift-rate) durch eine Schranke $\rho > 0$ begrenzt ist.\\ - \\ - D.h., der Fehler beim Messen von Intervallen zwischen Echtzeiten $t$ und $t'$ ist begrenzt durch:\\ - \\ - \q $(1-\rho) (t'-t) \le H(t') - H(t) \le (t'-t) (1+\rho)$\\ - \\ - \q $ \Leftrightarrow 1-\rho \le \frac{H(t')-H(t)}{t'-t} \le 1 + \rho$\\ - \\ - \q $ \ra -\rho \le \frac{H(t')-H(t)}{t'-t} -1 \le \rho$ (Gangabweichungsgeschwindigkeit)\\ - \\ - Erster Korrektheitsbegriff: Gangabweichungsgeschwindigkeit beschr\"{a}nkt.\\ - \\ - Frage: Darf eine in dem Sinne korrekte Uhr ``springen''? Antwort: \underline{nein}! \textit{Differenzierbare Funktionen m\"{u}ssen stetig sein}. Derartige Uhren d\"{u}rfte man nicht synchronisieren (``stellen''). $\ra$ Dieser Korrektheitsbegriff ist oft zu stark. - - \item Ein weiterer Korrektheitsbegriff: Eine Hardwareuhr hei{\ss}t korrekt, wenn sie ``monoton'' ist.\\ - \\ - \q $t < t' \ra H(t) < H(t')$\\ - \\ - $\ra$ Das ist oft ein zu schwacher Korrektheitsbegriff. - - \item Eine Hardwareuhr hei{\ss}t korrekt, wenn sie monoton ist und die Gangabweichung zwischen Synchronisationspunkten begrenzt ist. -\end{enumerate} -\section{Methoden zur Synchronisation} -\subsection{Interne Synchronisation in einem synchronem System} -Annahme: Die Transportzeit einer Nachricht (vom Senden zum Empfangen) liegt garantiert zwischen $t_{min}$ und $t_{max}$. D.h. $t_{min} \le t_{tr} \le t_{max}$. Die anderen Zeiten seien vernachl\"{a}ssigibar. Nenne $t_{max} - t_{min}$ die ``Unsicherheit''.\\ -\\ -Prozess $P_1$ senden seine Zeit $t$ in einer Nachricht zu Prozess $P_2$.\\ - -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=85mm]{vs7.png} -\end{center} -\end{figure} -$P_2$ setzt beim Empfang seine Zeit auf:\\ -\\ -\q $t_2 = t + \frac{1}{2}(t_{max} + t_{min}) \ra$ Synchronisationsfehler $< \frac{U}{2}$\\ -\\ -Wenn man so $N$ Uhren intern synchronisiert, ist der Fehler $\le U(1-\frac{1}{N})$\\ -\\ -In asynchronen Systemen k\"{o}nnen keine Garantien gegeben werden.\\ -\\ -Beobachtung: Die Round-Trip Zeit (RTT) in realen Systemen ist oft relativ kurz. - -\subsection{Christians Methode zur externen Synchronisation} -\begin{itemize} - \item Es handelt sich um einen ``probabilistischen Algorithmus''. - \item Mit Wahrscheinlichkeit $> p_0$ ist eine Synchronisation m\"{o}glich. - \item Typische Roundtrip-Zeiten sind $1, ..., 10ms$ - \item Abweichungsgeschwindigkeit der lokalen Uhr die zur Roundtrip-Zeimessung benutzt wird, ist vernachl\"{a}ssigbar klein. - \item Der Prozess, der mit Round-Trip den Zeitserver nach der Zeit gefragt hat, setzt seine Zeit auf $t$ (Zeitpunkt des Servers) $ + \frac{T_{round}}{2}$ sofern man keine zus\"{a}tzlichen Informationen hat. -\end{itemize} -Christians Methode: Benutze die Round-Trip Zeit, um die Transportzeit von Nachrichten f\"{u}r den Einzelfall zu ``kennen''.\\ -\\ -Der Prozess p setzt seine eigene Zeit auf $t + \frac{T_{round}}{2}$. Mit $t :=$ Zeitstempel des Servers. -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=70mm]{vs8.png} -\end{center} -\end{figure} -Annahme: Es ist etwas mehr bekannt, n\"{a}mlich eine untere Schranke $T_{min}$ f\"{u}r den Nachrichtentransport ($\ra T_{round} \le T_{min}$). -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=75mm]{vs9.png} -\end{center} -\end{figure} -Client setzt seine Uhr wie vorher auf $t + \frac{T_{round}}{2}$. Die Genauigkeit ist $\pm(\frac{T_{round}}{2} - T_{min})$.\\ -\\ -Synchronisiere nur, wenn die beobachte Round-Trip-Zeit klein genug ist. Vorsicht: Beim Synchronisieren sind ggf. Korrektheitsbedinungen (Monotonie o.\"{A}...) zu beachten! -\begin{itemize} - \item Schutz gegen Ausfall: Einrichtung mehrerer Server. - \item Erreichen kleinerer Round-Trip-Zeit: Benutze ``nahe'' Server. - \item Problem: Betr\"{u}gerische Server: Kryptologische Methoden (Authentifizierung). \\ - Abgleich mehrerer Servern. -\end{itemize} - -\subsection{Berkeley Algorithmus zur internen Synchronisierung} -\begin{itemize} - \item Auswahll eines Koordinierungsmasters. - \item Der Master fragt die Slaves ab. Diese senden ihre eigene Uhrzeiten zur\"{u}ck. - \item Der Master sch\"{a}tzt die lokalen Zeiten der Slaves durch Beobachtung der Roundtrip-Zeit. - \item Der Master bildet (durch gewichtete Mittelung) eine ``m\"{o}glichst genaue'' Referenzzeit. - \item Der Master schickt allen Slaves ``Korrekturwerte'' die angeben, wie sie jeweils aus ihrer lokalen Zeit die Referenzzeit berechnen k\"{o}nnen. -\end{itemize} -Experiment: 15 Computer kann man in \"{u}blichen LANs relativ leicht auf ca. 25$\mu$s synchronisieren. (Bei ca 10ms Roundtrip)\\ -\\ -Keine Garantien!\\ -\\ -Problem (weiterhin): Uhren erm\"{o}glichen es nicht immer, die Frage zu beantworten, ob ein Ereignis a vor einem Ereignis b stattgefunden hat.\\ -\\ -Einf\"{u}hrung eines anderen Konzepts: -\section{Logische Zeit und logische Uhren} -Beobachtung: -\begin{enumerate} - \item Innerhalb eines Prozesses ist es leicht zu entscheiden, was ``fr\"{u}her'' oder ``sp\"{a}ter'' ist. - \item Prozesse treten nur mit Nachrichten in Kontakt. (Keine Back-Channels) -\end{enumerate} -\textbf{Modellvorstellung:} Ein Prozess ist eine wohldefinierte Abfolge von Ereignissen.\\ -\\ -\textbf{Typische Ereignisse:} Senden einer Nachricht, Empfangen einer Nachricht, Berechnung eines Ergebnisses, \"{A}nderung eines Attributes eines Objekts, Speichern einer Datei. \\ -\\ -Idee (Lamport) definiere eine ``geschehen vor'' Relation. Relation zwischen zwei Ereignissen.\\ - -Schreibweise ``$\ra$''\\ -\\ -Zuerst f\"{u}r Ereignisse in einem Prozess $i$:\\ -\\ -$l_1 \ra_i l_2 \qquad l_1$ und $l_2$ im selben Prozess, dann ist die Reihenfolge klar.\\ -\\ -Die durch $\ra_i$ sortierte Folge der Ereignisse in einem Prozess nennt man eine ``history''. Klar ist: Eine Nachricht kann erst empfangen werden, nachdem sie gesendet wurde.\\ -\\ -Definiere die ``geschehen-vor'' Relation $\ra$ nun wie folgt: -\begin{enumerate} - \item Falls es einen Prozess $i$ gibt, so dass\\ - $l \ra_i e'$ dann gillt $l \ra e'$ - \item F\"{u}r jede Nachricht $m$ gilt\\ - send($m$)$\ra$receive($m$) - \item Es gilt $e\ra e'$ und $e'\ra e''$ dann gilt $e\ra e''\\$ -\end{enumerate} -Beispiel: -\newpage -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=90mm]{vs10.png} -\end{center} -\end{figure} - -Ergibt:\\ -\\ -Wegen 1.: $\quad a\ra b \qquad c\ra d \qquad e\ra f$\\ -Wegen 2.: $\quad b\ra c \qquad d\ra f$\\ -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=60mm]{vs11.png} -\end{center} -\end{figure} -\\ -Frage: Gilt $e\ra c$?? Kann es sein, dass f\"{u}r zwei Ereignisse $e$ und $e'$ sowohl $e\ra e'$ als auch $e'\ra e$ gilt? Antwort: Nein! -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=70mm]{vs12.png} -\end{center} -\end{figure} -Hier gibt es zwei Begr\"{u}ndungen f\"{u}r $a\ra f$.\\ -\\ -Es gilt weder $a\ra e$ noch $e\ra a$ so bezeichnet man $a$ und $e$ als nebenl\"{a}ufig. Schreibweise: $a||e$\\ -\\ -Die ``geschehen vor'' Relation stellt einen m\"{o}glichen Datenfluss dar. Fragen der Art: ``Hat Ereignis $e_i$ das Ereignis $e_j$ m\"{o}glicherweise beeinflusst?'' sollen beantwortet werden.\\ -\\ -Wie stellt man ``$\ra$'' auf einem Rechner fest?\\ -\\ -Erster Ansatz: -\subsection{Logische Uhr von Lamport} -\begin{itemize} - \item Jeder Prozess $i$ hat seine eigene logische Uhr $L_i$. $L_i$ w\"{a}chst monoton. - \item Die eigene Zeit wird Nachrichten als Zeitstempel mitgegeben. -\end{itemize} -Wie wird $L_i$ jeweils aktualisiert? $L_i$ wird vor (bei) einem Ereignis in $P_i$ erh\"{o}t. - -\begin{itemize} - \item Sendet Prozess $P_i$ eine Nachricht $m$, so wird der Nachricht der Zeitstempel $t=L_i$ mitgegeben. - \item Beim Empfang einer Nachricht berechnet Prozess $P_j$ das Wort $L_j = max(L_j, t)+1$ und weist diesen Stempel dem Empfangsereignis zu. - \item Die $L_i$ (Lamport-Zeitstempel) werden mit $0$ initialisiert. -\end{itemize} -\textit{Diese Definition wurde W\"{o}rtlich aus dem Buch abgeschrieben, nicht ganz Widerspruchsfrei. Daher wirds im Folgenden nochmal Veranschaulicht dargestellt}.\\ -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=110mm]{vs13.png} -\end{center} -\end{figure} -\\ -Anschaulich: Das Empfangsereignis bekommt einen Zeitstempel der sowohl h\"{o}her ist als der Stempel des Sendeereignis als auch der Zeitstempel, der im eigenem Prozess vor ihm liegt.\\ -\\ -Frage: Was kann man aus Lamport-Zeitstempeln ableiten? Beispiel:\\ -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=100mm]{vs14.png} -\end{center} -\end{figure} -\begin{itemize} - \item Wenn $e\ra e'$ dann gilt $L(e) < L(e')$ - \item Es gilt nicht: $L(e) < L(e') \Ra e\ra e'$ (Ein Beispiel: $L(b) > L(e)$ aber $e||b$) - \item Man kann aus $L(e) < L(e')$ nur folgern $e' \not \rightarrow e$ -\end{itemize} -Manchmal gibt es Probleme, bei welchen sich alle Teilnehmer \"{u}ber eine Reihenfolge einig sein m\"{u}ssen, wobei egal ist, welche Reihenfolge es ist.\\ -\\ -\textbf{Beispiel:} Eine Bank f\"{u}hrt Konten mehrfach damit man gegen Abst\"{u}rze einzelner Server gesichert ist. -Transaktionen (\"{U}berweisungen) werden an alle Server geschickt. -F\"{u}r den Kunden ist die Ausf\"{u}hrungsreihenfolge von Transaktionen egal.\\ -\\ -Korrektheitsforderung: -\begin{itemize} - \item Jede einzele Transaktion mu{\ss} korrekt gesendet werden. - \item Alle Server m\"{u}ssen zu dem gleichen Ergebnis kommen. D.h. die Server m\"{u}ssen sich auf eine (beliebige) Reihenfolge einigen. -\end{itemize} -Wenn die Server sich nicht einigen k\"{o}nnte folgendes passieren: -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=100mm]{vs15.png} -\end{center} -\end{figure} -\begin{itemize} - \item Kunde hat 1000 EUR - \item Transaktion A: Einzahlung 100 \officialeuro - \item Transaktion B: Verzinsung um 1\% -\end{itemize} -Dieses Probem kann mit Lamport-Zeitstempeln gel\"{o}st werden, wie im Folgendem gezeigt wird:\\ -\\ -Grundidee der L\"{o}sung: Alle Server m\"{u}ssen die Transaktionen in der gleichen Reihenfolge ausf\"{u}hren. Angewandtes Konzept ist ein ``vollst\"{a}ndig geordneter Multicast'' (Totally Ordered Multicast).\\ -\\ -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=90mm]{vs16.png} -\end{center} -\end{figure} -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=90mm]{vs16b.png} -\end{center} -\end{figure} -Unterscheide von jetzt an konzeptionell zwischen dem Empfang von Nachrichten und der Auslierferung von Nachrichten. Bei einem ``vollst\"{a}ngig geordneten Multicast'' sorgt die Middleware daf\"{u}r, dass alle Anwendungen die Nachrichten in der gleichen Reihenfolge ausgeliefert bekommen.\\ -\begin{enumerate} - \item Teilschritt zur Realisation eines vollst. geordn. Multicasts mit Hilfe von Lamport Zeitstempeln: Erweitere die Lamport-Zeitstempel um die Rechner-Nummer (Prozess-ID o.\"{A}.) als Nachkommastelle!\\ - \\ - $\Ra$ Es gibt keine gleichen Zeitstempel mehr! D.h. f\"{u}r zwei verschiedene Ereignisse $e_1$ und $e_2$ gilt jetzt entweder $L(e_1) < L(e_2)$ oder $L(e_2) < L(e_1)$. - \item Teilschritt: Implementiere damit den ``Totally Ordered Multicast'' wie folgt:\\ - \\ - Jede Nachricht bekommt den Zeitstempel des Senders und wird auch an den Absender gesandt. Empfangene Nachrichten werden in eine lokale Warteschlange eingef\"{u}gt die nach Zeitstempeln geordnet wird.\\ -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=70mm]{vs17.png} -\end{center} -\end{figure} -\\ -Nun stelle eine weitere Forderung auf: Die Nachrichten die \underline{ein Sender} abschickt, kommen bei allen Empf\"{a}ngern in der Reihenfolge des Absendens an! -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=70mm]{vs17b.png} -\end{center} -\end{figure} -Diese Forderung ist entscheidend, aber relativ leicht zu erf\"{u}llen (z.B. durch Nummerierung von Paketen oder verbindungsorientiertem Protokoll).\\ - \\ - Der Empf\"{a}nger einer Nachricht multicastet eine Best\"{a}tigungsnachricht (ACK Acknowledge) an alle anderen Prozesse. (Nachricht bekommt Zeitstempel und wird an den eigenen Absender gesandt!) Nun sammeln sich in den Warteschlangen die Originalnachrichten (die vollst. \textit{geordnet} ausgeliefert werden sollten) und die zugeh\"{o}rigen Best\"{a}tigungen.\\ - \\ - Eine Nachricht wird aus der Hold-Back Queue ausgeliefert, wenn sie an der Spitze steht und man von allen Prozessen die zugeh\"{o}rige ACK-Meldung bekommen hat. -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=70mm]{vs18.png} -\end{center} -\end{figure} -Damit werden Nachrichten erst ausgeliefert, wenn klar ist, dass alle anderen Prozesse diese Nachricht auch empfangen haben.\\ -Vorsicht: Jede Nachricht die ``gemulticastet'' werden soll hat bei $N$ Teilnehmern $N^2$ ACK-Nachrichten zur Folge. -\end{enumerate} -Die Lamport-Zeitstempel waren nicht geeignet, die ``$\ra$''-Relation auf einfache Weise zu \"{u}berpr\"{u}fen. Deswegen: Erweiterung des Konzepts. - -\subsection{Vektor-Zeitstempel} -\begin{itemize} - \item $N$-Prozesse, jeder Prozess $I$ f\"{u}hrt seine eigene Vektor-Uhr $V_i$. Jede Vektor-Uhr $V_i$ ist ein Vektor mit $N$ Eintr\"{a}gen $V_i[j]$. - \item Idee: $V_i[j] \quad$ (mit $i \ne j$) ist die Anzahl von Ereignissen in $P_j$, von welchen eventuell ein Datenfluss zu $P_i$ erfolgen konnte. - \item $V_i[i]$ ist die Anzahl der Ereignisse, welchen $P_i$ selbst Zeitstempel zugewiesen hat. - \item Initialisierung: $V_i[j] = 0 \quad$ f\"{u}r alle $i, j = 1 ..N$. -\end{itemize} -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=85mm]{vs19.png} -\end{center} -\end{figure} -Zuweisung eines Zeitstempels zu einem Ereignis: -\begin{enumerate} - \item Eigenzeit erh\"{o}hen $V_i[i] := V_i[i]+1$ - \item Bei einem Sendeereignis schickt man den eigenen Zeitstempel in der Nachricht mit, d.h. die korrekte Vektoruhr. - \item Beim Empfang: Nach Erh\"{o}hen der Eigenzeit (vgl. 1) Bildung des Maximums aus empfangenem Zeitstempel und eigener Vektoruhr (elementweise) ergibt neue Vektoruhrzeit. -\end{enumerate} -\subsubsection{Vergleich von Vektorzeitstempeln} -\begin{itemize} - \item $v=v' \quad$ iff $\quad v[j] = v'[j]\quad$ ist f\"{u}r alle $j$ - \item $v\le v' \quad$ iff $\quad v[j] \le v'[j]\quad$ ist f\"{u}r alle $j$ - \item $v< v' \quad$ iff $\quad v[j] \le v'[j]$ und $v\ne v'\quad$ ist f\"{u}r alle $j$ -\end{itemize} -Man kann zeigen: $e\ra e' \Ra v(e) < v(e')$ \textit{Das ging auch schon bei Lamport-Zeitstempeln}. $\quad$ und $v(e)<v(e') \Ra e\ra e'$. \textit{Das ging bei den Lamport-Zeitstempeln noch nicht}.\\ -\\ -Man kann erkennen, ob Ereignisse nebenl\"{a}ufig sind: $x||y$ wenn weder $x\le y$ ist noch $y\le x$ ist.\\ -\\ -D.h. Vektorzeitstempel erlauben es, die ``$\ra$''-Relation auszuwerten. -\textbf{Nachteil:} Hoher Aufwand (Speicher und Netzlast) bei gr\"{o}sserem $N$. \textbf{Aber:} Es gibt kein Verfahren mit ``kleinerem Aufwand'' um durch Vergleich logischer Uhren Nebenl\"{a}ufigkeit festzustellen. - -\section{Globale Zust\"{a}nde} -\textbf{Aufgabe:} Man mu{\ss} feststellen k\"{o}nnen ob bestimmte Situationen vorliegen.\\ -\\ -\textbf{Beispiele:} -\begin{itemize} - \item Ist ein Objekt \"{u}berfl\"{u}ssig? (Garbage Collection) - \item Ist ein verteilter Algorithmus fertig? - \item Ist ein Deadlock vorhanden? - \item Ist garantiert, dass Ereignis $A$ ``vor'' Ereignis $B$ auftritt? - \item Kann es m\"{o}glicherweise passieren, dass zwei Benutzer eine Datei gleichzeitig benutzen? -\end{itemize} -Zur verteilten Garbage Collection: -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=105mm]{vs20.png} -\end{center} -\end{figure} -Objekte werden durch Referenzen benutzbar. Referenzen, die momentan transferiert werden, m\"{u}ssen ber\"{u}cksichtig werden.\\ -\\ -Das Erkennen, ob ein Algorithmus in einem verteilten System abgeschlossen ist, kann z.B. schwer sein, wenn folgendes gemacht wird:\\ -\\ -Prozesse warten (passiv) auf Aktivierung (d.h. Zusendung eines Arbeitspaketes). -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=85mm]{vs21.png} -\end{center} -\end{figure} -W\"{a}hrend das Paket unterwegs ist, sind alle Prozesse ``passiv'', aber der Algorithmus noch nicht abgeschlossen.\\ -\\ -Problem: Weil es keine globale Zeit gibt, ist man nicht in der Lage eine Momentaufnahme (Snapshot) des Systems herzustellen. Deswegen kann man nicht feststellen ob zu einer Zeit $t$ eine Situation vorliegt.\\ -\\ -\textbf{Frage:} kann man aus lokalen Zust\"{a}nden, die zu unterschiedlichen Zeiten aufgenommen wurden, einen sinnvollen globalen Zustand zusammensetzen?\\ -\\ -\textit{Einfache aber schlechte} \textbf{Antwort:} Manchmal.\\ -\\ -Antworten auf Fragen der Art: -\begin{itemize} - \item H\"{a}tte das System in dem Zustand $X$ sein k\"{o}nnen? - \item Ist das System garantiert nie im Zustand $X$ gewesen? -\end{itemize} -sind teilweise m\"{o}glich. -\newpage -\subsection{Konzepte zur ``Formalisierung''} -\subsubsection{Idee des ``Schnittes'' eines Systems} -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=95mm]{vs22.png} -\end{center} -\end{figure} -~\\ -Die ``History'' von $P_1$ ist $e_1^0\quad e_1^1\quad e_1^2\quad e_1^3\quad ...$\\ -\\ -Die ``History'' von $P_2$ ist $e_2^0\quad e_2^1\quad e_2^2\quad e_2^3\quad ...$\\ -\\ -\begin{tabular}{cccc|} -$e_1^0$ & $ e_1^1$ & $ ... $ & $ e_1^k$\\ -$e_2^0$ & $ e_2^1$ & $ ... $ & $ e_2^j$ -\end{tabular} -\\ -\\ -\textit{$e_1^k$ und $e_2^j$ bilden die Front eines Schnittes. Die Front einschliesslich alle vorherigen Zust\"{a}nde sind ``im Schnitt enthalten''}\\ -\\ -Ein m\"{o}glicher Schnitt des obigen Systems w\"{a}re:\\ -\\ -\begin{tabular}{ccc|} -~ & ~ & $e_1^0$\\ -$e_2^0$ & $e_2^1$ & $e_2^2$ -\end{tabular} -\\ -\\ -\\ -Ein Schnitt ist konsistent, wenn f\"{u}r jedes Ereignis des in ihm enthalten ist, auch alle Ereignisse enthalten sind, die im Sinne der ``geschehen vor''-Relation ``vor ihm'' liegen.\\ -\\ -Der Schnitt \textit{von oben} ist inkonsistent, weil z.B. $e_1^1 \ra e_2^0$ und $e_2^0$ ist im Schnitt und $e_1^1$ ist nicht im Schnitt. -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=95mm]{vs23.png} -\end{center} -\end{figure} -Ein konsistenter globaler Zustand wird definiert als konsistenter Schnitt. Der Zustand eines Systems entspricht nie einen inkonsistenten Schnitt.\\ -\\ -Die konsistenten Schnitte ensprechen alle m\"{o}glichen Situationen. Ein verteiltes System bewergt sich durch konsistente globale Zust\"{a}nde.\\ - -$S_0 \ra S_1 \ra S_2 \ra ...$\\ -\\ -Ereignisse ``$\ra$'' in einzelnen Prozessen: ``Senden'', ``Empfangen'', ``inneres Ereignis''.\\ -\\ -Ein ``RUN'' ist eine Anordnung aller Ereignisse in einem System die konsistent ist mit jeder lokalen history. F\"{u}r das obige System ist\\ - -$e_1^0 \quad e_1^1 \quad e_1^2 \quad e_1^3 \quad e_2^0 \quad e_2^1 \quad e_2^2$\\ -\\ -ein RUN.\\ -\\ -Ist ein RUN auch konsistent mit der globalen ``geschehen vor''-Relation, nennt man ihn eine Linearisierung des Systems. Es kann mehrere Linearisierungen geben! -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=100mm]{vs24.png} -\end{center} -\end{figure} -\subsection{Auswertung von Pr\"{a}dikaten in globalen Zust\"{a}nden} -Interessante Pr\"{a}dikate: -\begin{itemize} - \item System ist in einem Deadlock - \item Objekt ist ``Garbage'' - \item Prozess ist terminiert - \item Ein Attribut eines Objektes hat einen bestimmten Wert -\end{itemize} -F\"{u}r viele Pr\"{a}dikate ist die Auswertung schwer. Deswegen definiert man ``neue Pr\"{a}dikate'' mit Hilfe der gew\"{u}nschten Pr\"{a}dikate.\\ -\\ -$\varphi$ ist ein Pr\"{a}dikat das in einem globalen Zustand ausgewertet werden kann.\\ -\\ -M\"{o}glicherweise $\varphi \quad$ iff $\quad$ Es gibt einen konsistenten globalen Zustand $S$, der eine Linearisierung der Hostorie $H$ durchl\"{a}uft, so dass $\varphi(S) = true$. -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=40mm]{vs25.png} -\end{center} -\end{figure} -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=100mm]{vs25b.png} -\end{center} -\end{figure} -Definitiv $\varphi \quad$ iff $\quad$ F\"{u}r alle Linearisierungen $L$ von $H$ gibt es einen konsistenten globalen Zustand $S$ (der kann von der Linearisierung abh\"{a}ngen) den $L$ durchl\"{a}uft mit $\varphi(S) = true$.\\ -\\ -Vorsicht: $\overline{moeglicherweise} \quad \varphi \ra definitiv \quad \overline{\varphi}$\\ -\\ -aber\\ -\\ -aus definitiv $\overline{\varphi}$ $\not{\ra}$ $\overline{moeglicherweise \quad \varphi}$\\ -\\ -Oft interessieren einen ``stabile Pr\"{a}dikate''. Ein Pr\"{a}dikat hei{\ss}t stabil, wenn daraus, dass es einen Zustand wahr ist folgt, dass es in m\"{o}glichen Folgezust\"{a}nde wahr ist.\\ -\\ -Anschaulich:\\ -\\ -M\"{o}glicherweise $\varphi$:$\quad$M\"{o}glicherweise hat sich das System so entwickelt, dass zu irgendeinem Zeitpunkt einmal $\varphi$ galt.\\ -\\ -Definitiv $\varphi$:$\quad$Das System hat sich definitiv so entwickelt, dass auf jeden Fall in irgendeinem Zustand $\varphi$ galt.\\ -\\ -\textbf{Beispiel:} -\begin{itemize} - \item Objekte k\"{o}nnen von Prozessen ``gelockt'' werden - \item $L(x)$ Lock auf ein Objekt haben - \item $U(x)$ Unlock (Lock sperrt) zur\"{u}ckgeben -\end{itemize} -Pr\"{a}dikat $\varphi$ ``es liegt ein Konflikt vor''. D.h. wenn ein Objekt zweimal gelockt wurde, liegt ein Konflikt vor. -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=70mm]{vs26.png} -\end{center} -\end{figure} -\begin{itemize} - \item definitiv (Konflikt) nein - \item m\"{o}glicherweise (Konflikt) nein - \item definitiv (kein Konflikt) ja - \item m\"{o}glicherweise (kein Konflikt) ja -\end{itemize} -\newpage -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=70mm]{vs27.png} -\end{center} -\end{figure} -Alle Linearisierungen des Systems: $abc$, $acb$, $cab$. -\begin{itemize} - \item definitiv (Konflikt) nein $abc$ - \item m\"{o}glicherweise (Konflikt) ja $acb$ - \item definitiv (kein Konflikt) ja am Anfang - \item m\"{o}glicherweise (kein Konflikt) ja am Anfang -\end{itemize} -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=70mm]{vs28.png} -\end{center} -\end{figure} -Reicht noch nicht um ``definitiv (Konflikt)'' wahr zu machen (denn es gibt noch die Linearisierung $abc$ die konfliktfrei ist) -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=70mm]{vs29.png} -\end{center} -\end{figure} -\begin{itemize} - \item definitiv (Konflikt) ja - \item m\"{o}glicherweise (Konflikt) ja - \item definitiv (kein Konflikt) nein - \item m\"{o}glicherweise (kein Konflikt) nein -\end{itemize} - -\section{Koordination und \"{U}bereinstimmung} -Grundprobleme: -\begin{itemize} - \item Zugriff auf gemeinsam genutzte Ressourcen mu{\ss} koordiniert werden. - \item In vielen Situationen mu{\ss} Einigkeit hergestellt werden (z.B. wer der Master ist, ob eine Transaktion g\"{u}ltig ist, ...). -\end{itemize} -Algorithmmus f\"{u}r wechselseitigen Ausschluss:\\ -\\ -$N$ Prozesse $P_i\quad i = 1 ... N \quad$ greifen mit dem folgenden Protokoll auf eine Ressource zu: -\begin{itemize} - \item enter(): Eintritt in den kritischen Bereich (ggf. blockiert) - \item exit(): Kritischen Bereich verlassen -\end{itemize} -Anforderungen an einem Algorithmus zur Realisierung des wechselseitigen Ausschlusses: -\begin{enumerate} - \item Sicherheit: H\"{o}chstens ein Prozess ist zu einer Zeit in einem kritischen Bereich. - \item Liveness: Anforderungen in dem kritischen Bereich einzutreten sind irgendwann erfolgreich. - \item Reihenfolgeforderungen: Reihenfolge des Eintretens darf nicht gegen die ``$\ra$''-Relation zwischen Anforderungen verstossen. \textit{Diese Anforderung ist schwer zu erf\"{u}llen, daher wird diese vorerst weggelassen}. -\end{enumerate} -Bewertung und Messung der Leistungsf\"{a}higkeit von Algorithmen in verteilten Systemen: -\begin{itemize} - \item ``Verbrauchte Bandbreite'' (Anzahl der Nachrichten pro enter/exit-Operationen) - \item ``Client-Verz\"{o}gerung'' bei jeder enter/exit-Operation. - \item ``Systemdurchsatz'': Wieviele Vorg\"{a}nge erreicht man pro Zeiteinheit. -\end{itemize} - -\subsubsection{Beispiel 1} -...f\"{u}r ein Verfahren zur Sicherung des ``wechselseitigen Ausschlusses''.\\ -\\ -Algorithmus mit zentralem ``Token''-Server. Ein Zentralserver vergibt \underline{``ein Token''} an einen Client, der Zugriff auf die Ressource haben will. Der Client, der das Token besitzt, darf die Ressource benutzen. Nach der Benutzung gibt der Client das Token an den Zentralserver zur\"{u}ck. -\begin{itemize} |