Parallele Systeme und Synchronisation PDF

Kapitel 3 Parallele Systeme und Synchronisation Da die Anforderungen an Rechensysteme immer weiter steigt, aber gleichzeitig die Grenzen der Geschwindigkeitssteigerung von Prozessoren erreicht sind, wer- den vermehrt parallele Systeme eingesetzt. Wenn mehrere Prozesse gleichzeitig rechnen, dann in...

Kapitel 3 Parallele Systeme und Synchronisation Da die Anforderungen an Rechensysteme immer weiter steigt, aber gleichzeitig die Grenzen der Geschwindigkeitssteigerung von Prozessoren erreicht sind, wer- den vermehrt parallele Systeme eingesetzt. Wenn mehrere Prozesse gleichzeitig rechnen, dann interagieren sie auch untereinander, was durchaus erwünscht sein kann. Allerdings können beim gleichzeitigen Zugriff auf Ressourcen wie z.B. den Arbeitsspeicher unerwünschte Effekte, sogenannte Race Conditions entstehen. Das kann beispielsweise in einem falschen Rechenergebnis resultieren. Diese Prin- zipien werden im Abschnitt 3.1 genauer behandelt. Um diese Fehler zu vermeiden, muss der Zugriff auf Ressourcen zwischen den Prozessen synchronisiert werden. Für die Implementierung einer Synchronisati- on werden im Abschnitt 3.2 verschiedene Konzepte vorgestellt. Die Synchroni- sation bringt jedoch einige Herausforderungen mit sich. Um die Schwierigkeiten, die auftreten können, zu veranschaulichen werden im Abschnitt 3.3 zwei beispiel- hafte Probleme beschrieben. Oftmals handelt es sich bei diesen Schwierigkeiten um Verklemmungen. Dabei ist eine Verklemmung ein Zustand, in dem ein oder mehrere Prozesse nicht mehr weiter rechnen können. Der Abschnitt ?? beschreibt sogenannte Deadlocks und andere Verklemmungsarten. Da Deadlocks die häufigste Art der Verklemmung sind, behandelt der Abschnitt 3.5 den Umgang mit diesen. 65 3.1 Parallele Systeme 3.1.1 Sequentielle vs. parallele Systeme Da Anforderungen trotz begrenzter Rechenleistung steigen, besteht der Bedarf nach parallelen Systemen. Sequentielle Programme berechnen bei gleichen Ein- gaben immer die gleichen Ausgaben: Das Programmverhalten ist determiniert. Bei einer parallelen Programmausführung kann es vorkommen, dass unter den gleichen Umständen ein unterschiedliches Ergebnis berechnet wird. Ist das der Fall, dann ist das Programmverhalten nicht determiniert. Bei der parallelen Programmausführung wird außerdem zwischen nebenläufiger und echt paralleler Ausführung unterschieden. Ersteres bezeichnet, wenn Prozes- se zeitlich verzahnt ausgeführt werden. Nur bei echter Parallelität rechnen zwei Prozesse gleichzeitig. Eine echt parallele Programmausführung kann nur stattfinden, wenn mehrere CPUs verfügbar sind (z.B. bei Multi-Core/ Multi-Prozessor Systemen). Aber auch in einem Ein-Prozessor Systemen gibt es zumindest parallele Abläufe, z.B. kann ein Festplatte unabhängig von der CPU Daten lesen. Interaktion paralleler Prozesse Die Interaktion zwischen parallelen Prozessen kann beispielsweise für einen di- rekten Datenaustausch erwünscht, aber durchaus auch zum Beispiel bei Rechen- fehlern unerwünscht sein. Folgende Formen von Interaktionen werden unterschieden: Kausale Beziehungen beschreiben Abhängigkeiten zwischen räumlich ver- teilten und nebenläufig ausgeführten Aktivitäten. Ein Ereignis löst ein an- deres Ereignis aus. Beispiel: Ein Fußgänger drückt den Knopf, die Ampel schaltet auf grün. Bei der Kommunikation findet ein Nachrichtenaustausch zwischen Prozes- sen desselben oder unterschiedlichen Rechensystemen statt. Bei der Koordinierung gibt es eine Beziehung der Art Auftraggeber und Auftragnehmer zwischen zwei Prozessen. Beispiel: Client-Server-Architekturen Eine Konkurrenz entsteht, wenn mehrere Prozesse gleichzeitig auf begrenz- te Ressourcen zugreifen möchten. 66 Nichtdeterminismus Durch die eben beschriebenen Interaktionen kann ein nicht eindeutiges, also ein nicht determiniertes Programmverhalten entstehen. Dies bedeutet, dass das Sy- stem bei gleichen Ausgangsbedingungen und gleichen Eingaben ein unterschied- liches Verhalten aufweist. Zu welchem Ergebnis genau das Programm bei einem bestimmten Durchlauf evaluiert, wird zum Beispiel durch die Reihenfolge, in der die Prozesse ausgeführt werden, beeinflusst. Dies ist ein Problem, da sich so Er- gebnisse nicht reproduzieren lassen. 3.1.2 Beschreibung paralleler Systeme Parallele Systeme können auf unterschiedlichen Abstraktionsebenen beschrieben werden: Modellebene, Programmiersprachen-Ebene und Betriebssystem-Ebene. Auf der Modell-Ebene wird das System weitgehend abstrahiert. Aktionen und deren Abhängigkeiten werden mittels Aktionsstrukturen modelliert, und Zustände sowie Zustandsänderungen werden mittels Petrinetzen mo- delliert. Das Kapitel 4 beschäftigt sich mit diesen Modellen. Auf Programmiersprachen-Ebene wird die Modellierung durch program- miersprachliche Konzepte bereits konkreter, z.B. durch die Aufteilung in Threads. Die Betriebssystem-Ebene beschäftigt sich mit der Verwaltung der vorhan- denen parallelen Aktivitäten. Dabei verwaltet es Prozesse und Threads. Dar- über hinaus bietet das Betriebssystem Möglichkeiten zur Kommunikation und Synchronisation zwischen Threads. Modellierung paralleler Systeme Um parallele Systeme zu beschreiben und zu analysieren, betrachtet man Tätig- keiten (Aktionen, die zu modellierenden Einheiten) und Veränderungen (Ereig- nisse, die modellierten Einheiten, die beobachtbare Veränderungen bewirken). Ein Ereignis löst stets eine Aktion aus. Dazu möchte man ein Modell bauen, dass sich möglichst auf das Wesentliche kon- zentriert und somit das System dabei auf essentielle Eigenschaften reduziert. 67 Eigenschaften paralleler Systeme Folgende Eigenschaften sollten parallele Programme haben: Determiniertheit: Unter gleichen Bedingungen und Eingaben werden glei- che Ergebnisse berechnet. Störungsfreiheit: Unter festgelegter Ausführungsreihenfolge paralleler Er- eignisse und deren Aktionen wird das Ergebnis nicht beeinflusst. Wechselseitiger Ausschluss: Angenommen zwei Prozesse wollen gleichzei- tig auf eine Ressource zugreifen, sodass ein Konflikt entsteht. Ein wechsel- seitiger Ausschluss bedeutet in dieser Situation, dass zu jedem Zeitpunkt maximal ein Prozess auf eine gemeinsame Ressource zugreift. Verklemmungsfreiheit: Als eine Verklemmung wird ein Zustand bezeich- net, in dem ein oder mehrere Prozesse nicht mehr weiter rechnen können. Dies ist z.B. bei einem Deadlock der Fall: Dabei gibt es eine zyklische War- tesituation, sodass niemand den Programmablauf fortsetzen kann. Ein ver- klemmungsfreies System kann nicht in einen solchen Zustand geraten. Kein Verhungern: Man spricht von Verhungern, wenn ein Prozess nicht zur Ausführung kommt, obwohl kein Deadlock entstanden ist. Dies kann z.B. bei einem unfairen Scheduling passieren. 3.1.3 Synchronisation von parallelen Systemen Synchronisation, Race Condition Race Conditions entstehen wenn mindestens zwei Prozesse lesend oder schrei- bend auf eine Ressource zugreifen wollen. Das Ergebnis ist dabei von der Rei- henfolge des der Prozessausführung abhängig. Damit ist es nicht-deterministisch. Race Conditions sollen durch wechselseitigen Ausschluss vermieden werden. Ab- schnitte in denen Race Conditions entstehen können, werden kritische Abschnit- te (critical section) genannt. Als kritischer Abschnitt wird ein Bereich bezeichnet in dem der Zugriff von verschiedenen Prozessen koordniniert, bzw. synchroni- siert werden muss, um Race Conditions zu vermeiden. An diesen Stellen wird der Zugriff sequentialisiert. 68 Kritischer Abschnitt, Wechselseitiger Ausschluss Die vier Phasen eines kritischen Abschnitts sind wie folgt definiert: 1. Ein nicht kritischer Abschnitt wird ausgeführt. 2. Der kritische Abschnitt wird betreten. 3. Der kritische Abschnitt wird ausgeführt. 4. Der kritische Abschnitt wird verlassen. =⇒ Kritische Abschnitte müssen wechselseitig ausgeschlossen werden! Anforderungen für die Synchronisation 1. Die kritischen Abschnitte sind wechselseitig ausgeschlossen. 2. Die Synchronisation darf keine Annahmen über die Reihenfolge, in der die Prozesse einen kritischen Abschnitt betreten, machen. 3. Die Synchronisation darf keine Annahmen über die Ausführungszeit der Prozesse machen. 4. Kein Prozess darf einen anderen unendlich lange daran hindern, einen kri- tischen Abschnitt zu betreten. 3.2 Prozesssynchronisation 3.2.1 Überblick über Lösungskonzepte Für die Realisierung einer Prozesssynchronisation gibt es auf den unterschied- lichen Schichten des Rechensystems verschiedene Lösungskonzepte. Für die Im- plementierung einer Synchronisation wird eine Kombination dieser Konzepte ver- wendet. 1. Hardware-Ebene: Die Hardware, insbesondere die CPU, stellt folgende Me- chanismen zur Verfügung um die Parallelität einzuschränken: Unterbrechungssperre: Durch das Deaktivieren von Interrupts kann ein kritischer Abschnitt nicht unterbrochen werden. 69  Test-and-Set-Lock (TSL): Mittels einem speziellen Maschinenbefehl kann der Eintritt in einen kritischen Abschnitt kontrolliert werden. 2. Betriebssystem-Ebene: Wird man wegen einem kritischen Abschnitt am Wei- terrechnen gehindert, muss der Prozess auf eine Freigabe warten. Für dieses Warten gibt es folgende Möglichkeiten: Aktives Warten: Der wartende Prozess fragt so lange auf eine Freigabe ab, bis der kritische Abschnitt betreten werden kann. Passives Warten: Der Prozess gibt die Kontrolle an das Betriebssystem ab, sodass in der Wartezeit andere Prozesse rechnen können. 3. Höhere Abstraktion: Diese Konzepte veranschaulichen die Implementierung eines wechselseitigen Ausschlusses: Semaphoren: Dies ist ein allgemeines, abstraktes Konzept zur Synchro- nisierung kritischer Abschnitte. Mutexe: Hierbei handelt es sich um einen einfachen Fall einer Sema- phore. 4. Programmiersprachen-Ebene: Da die Anwendung von Semaphoren und Mu- texen noch immer aufwändig und fehleranfällig ist, bieten viele Program- miersprachen noch abstraktere Lösungen an, um die Programmierung zu vereinfachen. Monitor-Konzept: Dies ist eine mögliche Lösung in einer Program- mierumgebung. Erinnerung: Prozesszustände Prozesse befinden sich in unterschiedlichen Zuständen. Prozesse, die wir hier be- handeln, sind der Regel «rechenwillig» oder «rechnend». Außerdem wollen sie natürlich auf eine Ressource zugreifen, sonst wäre ja kein Konflikt da. Wir erinnern uns an die Prozesszustände (s. Bild 3.1). In dem Fall, dass die Prozes- se eine Ressource wollen, aber diese nicht erreichen können, dann gibt es generell zwei Lösungsideen dazu: man kann die Prozesse entweder aktiv warten lassen, indem man denen die CPU wegnimmt, und wieder in die Warteschlange platziert. Hier hofft man, das es bei dem nächsten Ansatz klappen soll. Oder, man versetzt sie in den Zustand «wartend», befreit damit die Ressourcen des Rechners. 70  Zustandsmodell Das Prozess-Zustandsmodell unterscheidet neben den bereits vorgestellten Zuständen rechenwillig, rechnend, wartend auch den Zustand ausgelagert. Letzterer Zustand tritt ein, wenn der Adressraum aufgrund Speichermangels aus dem Arbeitsspeicher auf den Hintergrundspeicher verlagert wird ("swapping"). Beispielsweise verwaltet Windows auf der Festplatte eine Swap-Datei, in die Prozesse ausgelagert werden. resign add retire rechenwillig assign rechnend block ready wartend swap out swap in ausgelagert Abbildung Zustandsübergänge sind: 3.1: Prozess-Zustände add: ein neu erzeugter Prozess wird zu der Menge der rechenwilligen Prozesse hinzugefügt; Exkurs: Ablauf eines assign: Interrupts als Folge eines Kontextwechsels wird dem Prozess die CPU zugeordnet; block: aufgrund eines EA-Aufrufs oder einer Synchronisationsoperation wird der Die Abbildung ?? zeigt eine CPU, auf der der Prozess P1 rechnet. Dieser verwen- Prozess wartend gesetzt; det momentan dienach ready: exklusiv Beendigungnutzbare Ressource der angestoßenen Operation Rwechselt 1. der Prozess in den Problem: Sollte in der Zustand Interrupt-Routine rechenwillig; dieum er bewirbt sich erneut exklusiv die CPU; nutzbare Ressource verwen- det werden, kommt es zu resign: dem einemProzess rechnenden Fehlerzustand. wird die CPUDas System entzogen; würde er bewirbt sichentweder ver- anschließend erneut um die CPU; klemmen oder die Ressource würde unerlaubter Weise von zwei Prozessen be- retire: der aktuell rechnende Prozess terminiert; nutzt werden.swap out: der Prozess wird auf die Festplatte ausgelagert; 110 3.2.2 Unterbrechungssperre Die Unterbrechungssperre bietet eine Möglichkeit, das Problem: «Interrupt in ei- nem kritischen Abschnitt», zu beheben. In der schematischen Darstellung (Abb. ??) würde eine Unterbrechungssperre den Pfeil Nr2 für die Zeitspanne, in der P1 einen kritischen Abschnitt durchläuft, ent- fernen. Kein Interrupt-Signal erreicht währenddessen die CPU. Implementiert wird die Unterbrechungssperre mithilfe des sogenannten Interrupt- Flag im Kontrollregister der CPU. Ist dieses auf 0 gesetzt, nimmt die CPU keinen Interrupt entgegen, ist die Flag auf hingegen auf 1 gesetzt, werden Interrupts wie vorgesehen abgearbeitet. So wird auf einfachste Weise verhindert, dass der kriti- sche Abschnitt von anderen Prozessen unterbrochen werden kann. In Linux kann mit den Befehlen cli und sti das Interrupt-Flag manuell angepasst werden. Mit fortschreitendem Funktionsumfang des Betriebssystems wird jedoch immer stärker davon abgeraten, diese Befehle zu verwenden. Diese privilegierten 71  1. Ein Interrupt wird von einem de- dizierten Gerät (Systemuhr/Tasta- tur) ausgelöst und über bestimmte Interrupt-Leitungen dem Interrupt Controller (PIC) signalisiert. Systemuhr 2. Der PIC übermittelt die gesammel- 1 ten Signale aller Geräte einheitlich an die CPU. Interrupt P1 Controller 3. Die CPU ermittelt anhand ei- ner Interrupt-Tabelle die Anfangs- 2 5 6 adresse der zugehörigen Handler- Routine. Die Handler-Routine, de- CPU R1 ren Anfangsadresse in der Tabelle vermerkt ist, definiert alle Schritte, 3 4 7 8 die nacheinander ausgeführt wer- Interrupt den müssen, sodass eine bestimm- P2 Handler te Funktion gestartet werden kann. 4. Der Interrupt-Handler startet wie- Abbildung 3.2: schematischer Ab- derum die Handler-Routine. lauf eines Interrupts 5. Statt P1 (5) wird ab sofort P2 (7; mit der Interrupt-Methode) ausge- führt. Operationen könnten in fehleranfälligem Code beispielsweise unvollständig auf- gerufen werden, sodass Interrupts nicht mehr aktiviert werden. Ein Programm kann beispielsweise in eine Endlosschleife geraten und könnte bei deaktivierten Interrupts nicht mehr vom Betriebssystem beendet werden. Auch ein Interrupt mittels Strg - C erreicht die CPU nicht. Demnach sollte das Konzept der Unter- brechungssperre nur im Kern des Betriebssystemes verwendet werden. Des Weiteren sollten die kritischen Abschnitte möglichst kurz sein. Durch die De- aktivierung der Interrupts während der Unterbrechungssperre, gehen neu einge- gangenen Interrupts verloren. Beispielsweise werden Tastatureingeben, Datenpa- kete aus dem Internet, Systemuhren und Deadlines ignoriert. 72 Bei einer CPU mit mehr als einem Rechenkern reicht diese Lösung nicht aus, da zu jedem Rechenkern eine eigene Interrupt Leitung führt. Die Unterbrechungs- sperre kann nicht garantieren, dass von anderen Rechenkernen aus nicht auf die Ressource zugegriffen wird. Daher ist auch die Umsetzung der Unterbrechungs- sperre nur für ein System mit einem Rechenkern sinnvoll. 3.2.3 Wechselseitiger Ausschluss mit dem Test-and-Set-Lock-Befehl (TSL) Die Test-and-Set-Lock-Befehle bilden eine Klasse aus atomaren Maschinenbe- fehlen die eine Speicherzelle gleichzeitig lesen und beschreiben. Atomar bedeu- tet, dass der Maschinenbefehl in seiner Ausführung nicht unterbrochen werden kann. Als kleinste unterteilbare Einheit wird ein solcher Befehl entweder ganz oder gar nicht ausgeführt. tsl rax , [ lock ] Der abstrakte tsl-Assembler-Befehl liest den Inhalt der Speicherzelle mit der Adres- se [lock] in das Register rax ein und schreibt anschließend einen unbestimmten Wert in die Speicherzelle. Eine tatsächliche Implementierung des tsl-Befehls bietet unter anderem der As- semblerbefehl cmpxchg (Compare and exchange). Dieser Befehl ist im Befehlsatz aller x86-Prozessoren enthalten. mov rbx , $42 ; Zuweisung des Wertes 42 in rbx cmpxchg [ lock ] , rbx Die Instruktion verwendet das Register rbx und die Speicherzelle an der Adresse [lock]. Der Befehl liest den Wert beider Operanden ein und überschreibt sie in der selben Operation. Während der Befehl ausgeführt wird, wird der gesamte Speicherbus gesperrt, so- dass der Befehl, trotz mehrerer unterschiedlicher Schritte, nicht unterbrochen wer- den kann. Der Befehl ist damit atomar. Im Gegensatz zur Unterbrechungssperre wird also nicht ein einziger Rechenkern abgeriegelt, sondern alle Rechenkerne des Rechensystems sind betroffen. Wäre der Speicherbus nicht gesperrt, könnten zwei 73 Prozesse den selben Speicherwert einlesen und verändern, was unweigerlich zu Fehlerzuständen führt. Da der Befehl nur von einem Prozess zeitgleich ausgeführt werden kann, ermöglichen tsl-Befehle Prozesse untereinander zu synchronisie- ren. Eine mögliche Synchronisation mittels tsl-Befehl könnte wie folgt aussehen: enter _crit_re gion : tsl rax , [ lock ] cmp rax , $0 jne ente r_crit_r egion ret Bevor ein Prozess einen kritischen Abschnitt betritt, muss die Funktion enter_- crit_region aufgerufen werden. Sie führt zuerst den separat beschriebenen tsl-Befehl aus. Der nachfolgende cmp1 - Befehl vergleicht das Register rax mit dem Wert 0. Der Sprung jne2 wird nur ausgeführt, wenn im Vergleich zuvor rax ̸= 0 ergab. Befindet sich ein anderer Prozess in einem kritischen Abschnitt, so ist der Wert von [lock] ̸= 0 und damit auch rax ̸= 0. Durch den jne-Befehl springt die Funktion wieder an die Marke am Anfang der Synchronisationsmethode. Die Schleife wird solange ausgeführt, bis der Wert 0 aus der Speicherzelle [lock] in rax geladen wurde. Der jne-Befehl wird in diesem Fall nicht mehr ausgeführt. Mithilfe des ret3 -Befehl wird in den ursprünglichen Programmablauf zurückgesprungen. Nach Ausführung des tsl-Befehls ist der Wert der Speicherzelle immer ̸= 0. Er muss demnach nicht separat gesetzt werden, wenn ein Prozess den kritischen Ab- schnitt betritt. leave _crit_re gion : mov [ lock ] , $0 ret Die einfachere leave_crit_region Funktion muss am Ende des kritischen Ab- schnittes aufgerufen werden um diesen wieder freizugeben. Sie setzt die [lock]- Speicherzelle auf den Wert 0. 1 compare 2 jump not equals 3 return 74  enter_crit_region tsl rax, [lock] cmp rax, $0 jne enter_crit_region ret Weiter mit kritischem Abschnitt Abbildung 3.3: Kontrollflussdiagramm für die Funktion leave_crit_region. Da immer wieder Werte gegeneinander ausgetauscht werden, wird das tsl-Lock auch Spin-Lock genannt. Wichtig ist hier, dass Lesen und Schreiben als eine atomare Operation ausgeführt und der Speicher von genau einen einzigen Rechenkern zugegriffen wird. 3.2.4 Aktives Warten Bei aktivem Warten prüfen alle wartenden Teilnehmer kontinuierlich und peri- odisch, ob die Ressource weiterhin belegt ist. Dafür wird häufig eine Schleife ver- wendet, die erst verlassen werden kann, wenn die Wartebedingung erfüllt ist. Das eben vorgestellte tsl-Lock verwendet aktives Warten. Die Schleife wird so- lange ausgeführt, bis das Lock nicht mehr gesetzt ist. Aus der Sicht von System- Ressourcen ist dies jedoch nicht effizient: Der Prozess verbraucht Rechenzeit, in- dem er permanent in der Schleife zirkuliert. Im schlimmsten Fall, hindert der ak- tiv wartende Prozess einen rechenden Prozess daran, das Lock freizugeben. Das gesamte System wird durch die wartenden Prozesse ausgebremst. 75 3.2.5 Passives Warten Eine effizientere Alternative zum aktiven Warten bietet das passive Warten. So- bald ein Prozess eine Ressource nicht belegen darf, muss er mit thread_yield oder sleep in den «Warte»-Zustand versetzt werden und die CPU freigeben. Er verbraucht keine Rechenzeit mehr, bis die Ressource wieder freigegeben wird. Je- der passiv wartende Prozess wartet auf ein Signal, welches signalisiert, dass der Programmablauf fortgesetzt werden darf. Ein Prozess sendet ein «weck-Signal», sobald er eine Ressource freigibt. Genau einer der wartenden Prozesse wird auf- geweckt. Sollten mehrere Prozesse auf dieselbe Ressource warten, ist nicht festgelegt, wel- cher Prozess als nächstes reaktiviert wird. Hier kann es, ähnlich wie beim Sche- duling dazu führen, dass ein Prozess verhungert. Passives Warten kann unerwartete Fehler erzeugen. Beispiel: Als Ausgangsla- ge prüft ein Prozess P1 , ob eine bereits belegte Ressource frei ist. Direkt im An- schluss, bevor thread_yield oder sleep aufgerufen werden konnte, wird P1 die CPU entzogen. Der nachfolgende Prozess P2 gibt nun die belegte Ressource wie- der frei. Entsprechend versucht er einen wartenden Prozess aufzuwecken, da P1 noch nicht in den «wartet»-Zustand überführt wurde, wird dieser auch nicht be- nachrichtigt. Wenn P1 das nächste mal Rechenzeit zugewiesen bekommt setzt er seinen Programmablauf fort und begibt sich direkt in den «wartet»-Zustand. Nun kann er nicht mehr aufgeweckt werden. P1 P2 Belegung von R1 prüfen Scheduler R1 freigeben Wartenden Prozess wecken Scheduler Wartet Zustand einnehmen Abbildung 3.4: Sequenzdiagram für das Problem des passiven Wartens. 76 3.2.6 Semaphoren Die Lösung des Problems des passiven Wartens bietet das Semaphoren-Konzept. Eine Semaphore ist eine ganzzahlige Kontrollvariable s. Der Wert s gibt an, wie viele Prozesse den kritischen Abschnitt noch betreten dürfen (s > 0). Wenn s < 0 gibt die Semaphore an, wie viele Prozesse bereits darauf warten, den Abschnitt betreten zu dürfen. Semaphoren sind weniger Hardware-nah als die bisherigen Ansätze und vermei- den Konflikte auf einem höheren Abstraktionslevel. Damit die Semaphore s verwendet werden kann, sind drei Operationen definiert: 1. Initialisierung: Initialisiert wird eine Semaphore, in dem der Wert der Spei- cherzelle auf die maximale Anzahl an Prozessen gesetzt wird, die die Res- source gleichzeitig verwenden dürfen. Diese Variable wird im folgenden de- krementiert und inkrementiert. Der Wert darf dabei niemals den Ausgangs- wert überschreiten. 2. P (alternativ: down, wait): Die Operation ist im Betriebssystem atomar im- plementiert. s dekrementieren, Falls s < 0 muss der Prozess warten. Wenn passives Warten verwendet wird: Prozess muss in den Zustand «wartend» überführt werden. Die- ser wird automatisch in der entsprechenden Warteschlange platziert. Während diesem Schritt darf die CPU nicht abgegeben werden. Falls s >= 0 wurde die Ressource erfolgreich belegt. void down ( semaphore * sema ) { int * s = & sema -> s ; * s = * s - 1; if (* s < 0) { thread_yield ( sema -> wait_queue ) ; } } 3. V (alternativ: up, signal): Die Operation ist im Betriebssystem atomar im- plementiert. 77  s inkrementieren, Falls passives Warten implementiert wird und die Warteschlange nicht leer ist wird ein Prozess aus der Warteschlange entnommen und in den Zustand «rechenwillig» überführt. Falls aktives Warten implementiert ist, überführt sich ein wartender Prozess selbst in den Zustand «rechenwillig». void up ( semaphore * sema ) { int * s = & sema -> s ; * s = * s + 1; if (* s wait_queue ) ; } } Da bei einer Semaphore die Operationen down und up laut Definition atomar sind, können sie nicht unterbrochen werden. Demnach wird verhindert, dass die CPU zwischenzeitlich, wie beim passiven Warten abgegeben werden muss. Mit den definierten Funktionen, kann ein Semaphor-Objekt wa 4 bedient werden. Die Kontrollvariable s von wa wird mit der Maximalzahl an Prozessen n initia- lisiert. Die Maximalzahl n wird auch in dem Objekt wa gespeichert. Vor einem kritischen Abschnitt muss P aufgerufen werden, nach dem kritischen Abschnitt V: down (& wa ) ; e xe c ute _ cr i t_ r e gi o n () ; up (& wa ) ; Die Lösung mit Semaphoren erfüllt all unsere Anforderungen: Der kritische Abschnitt wird geschützt. Die Reihenfolge, in der die Prozesse den kritischen Abschnitt betreten wol- len, spielt keine Rolle. Bei dem passiven Ansatz ist gesichert, dass kein Prozess verhungern wird: Dank der Warteschlange für die Prozesse, wird jeder früher oder später in den kritischen Abschnitt gelangen. Bei einer Implementierung mit aktivem Warten hingegen können weiterhin Prozesse verhungern. 4 wechselseitiger Ausschluss 78 3.2.7 Mutexe Ein Mutex ist ein binärer Semaphor. Er kann nur zwei Zustände annehmen: ent- weder «locked» (0) oder «unlocked» (1). Mit Mutexen kann ein wechselseitiger Ausschluss sehr einfach implementiert werden. Mutexe sind ein Spezialfall von Semaphoren, bei denen die Vielfalt an Möglichkeiten gegen eine einfachere Im- plementierung eingetauscht wird. Implementiert wird ein Mutex identisch wie eine Semaphore, mit der Bedingung, dass die maximale Anzahl an Prozessen in dem kritischen Abschnitt 1 ist. Ein Mutex kann nicht negativ werden. Es ist nicht ersichtlich, wie viele Prozesse in der Warteschlange enthalten sind. Die Implementierung von Mutexen verwendet kein aktives Warten, sondern versetzt alle wartenden Prozesse in den entspre- chenden Zustand. 3.2.8 Monitor-Konzept Out winter 2019 3.3 Beispiele für Prozesssynchronisation 3.3.1 Erzeuger-Verbraucher-Problem Ein Erzeuger (engl.: Producer) produziert Inhalte und fügt sie anschließend in einen Puffer fester Größe ein. Sollte der Puffer voll sein, muss der Erzeuger warten bis mindestens ein freier Platz vorhanden ist. Ein Verbraucher (engl.: Consumer) nimmt Elemente aus dem Puffer und muss war- ten, falls der Puffer leer ist. Erzeuger und Verbraucher sind im Folgenden beides Prozesse, denen bekannt sein muss, wie viele Elemente in dem Puffer enthalten sind. Je nach Implementierung müssen sie sich gegenseitig über bestimmte Zu- stände informieren können. Producer Consumer Puffer mit begrenzter Größe Abbildung 3.5: Erzeuger-Verbraucher Schema 79 Eine einfache Implementierung könnte folgendermaßen aussehen: Conusmer bzw. Producer warten jeweils passiv, wenn der Puffer voll, bzw. leer ist. Dafür werden die beiden Funktionen sleep() und wakeup() verwendet. Ein Prozess versetzt sich in einen wartenden Zustand mit sleep() und wird wieder aktiv, wenn ein anderer Prozess wakeup() aufruft. Die Variable «N» entspricht, in der Implementierung ??, der maximalen Anzahl an Elementen in dem Puffer. Implementierung des Producers: void producer ( void ) { int item ; while ( true ) { item = produce_item () ; if ( count == N ) sleep () ; insert_item ( item ) ; count = count + 1; if ( count == 1) wakeup ( consumer ) ; } } Listing 3.1: Producer Implementierung des Consumers: void consumer ( void ) { int item ; while ( true ) { if ( count == 0) sleep () ; item = remove_item () ; count = count - 1; if ( count == N -1) wakeup ( producer ) ; 80  consume_item ( item ) ; } } Listing 3.2: Consumer Die Implementierung ist jedoch fehlerhaft, denn der Zugriff auf die Variable N erfolgt nicht synchronisiert und kann so zu einem Deadlock führen. Das folgen- den mögliche Beispielszenario illustriert einen möglichen Deadlock, ähnlich wie im Abschnitt passives Warten erwähnt: 1. Consumer registriert, dass der Puffer leer ist. 2. CPU wird dem Consumer durch den Scheduler entzogen und dem Producer zugewiesen. 3. Producer platziert ein Element in den Puffer, inkrementiert die Variable. Er versucht außerdem den schlafenden Consumer zu informieren. 4. Consumer befindet sich nicht im «Schlaf»-Zustand und der Signal geht ver- loren. 5. Wenn nun der Consumer die zuvor ausgelesene Variable testet, hat diese den Wert 0, entsprechend geht er schlafen. 6. Der Producer wird schrittweise den Puffer füllen und geht ebenfalls schlafen wenn der Puffer vollständig gefüllt wurde. Keiner der beteiligten Prozesse kann mehr aufgeweckt werden. Solch ein Fehler ist schwer zu finden, da er sehr selten auftritt. In der Regel wird der Code korrekt ablaufen. Lösungsansatz 1: Ein Mutex Der Mutex sichert, dass lediglich ein Teilnehmer zeitgleich auf den Puffer zugrei- fen kann. Eine mögliche Lösung wäre: while ( true ) { element = produce () ; down (& wa ) ; 81  write_to_buf (W , element ) ; up (& wa ) ; } while ( true ) { down (& wa ) ; element = read_from_buf ( W ) ; up (& wa ) ; consume ( element ) ; } Listing 3.3: Producer-Consumer: schlechte Lösung Trotz des Mutex kann auch hier ein Problem auftreten. Dies wird im folgenden Szenario dargestellt: 1. Producer legt ein Element in den Puffer. 2. Consumer entnimmt das Element. Der Puffer ist jetzt leer. 3. Consumer versucht noch einmal, ein Element zu entnehmen. Da der Puffer aber leer ist, versetzt der Verbraucher sich in den Zustand «wartend» (Zeile 5, Consumer). 4. Der Producer möchte ein weiteres Element ablegen, jedoch kann er den kri- tischen Abschnitt nicht betreten. Da der Consumer die Semaphore weiterhin gesetzt (Zeile 4, Producer) hat. → Das System ist verklemmt. Fazit: Ein Prozess, der einen Mutex gesetzt hat, darf nicht in den «warte»-Zustand überführt werden. Er darf nicht davon abhängig sein, dass ihn andere Prozesse wieder aufwecken. Lösungsansatz 2: Zwei Semaphoren Eine bessere Lösung sieht zwei zusätzliche Semaphoren vor: 1. voll für den Consumer - diesem muss bekannt sein, ob der Puffer aktuell Elemente enthält. Der Wert in voll entspricht der Anzahl an Elementen im Puffer. 82  2. leer für den Producer - diesem muss bekannt sein, ob der Puffer leer ist. Der Wert in leer zeigt die Anzahl der freien Plätzen. while ( true ) { element = produce () ; down (& leer ) ; down (& wa ) ; write_to_buf (W , element ) ; up (& wa ) ; up (& voll ) ; } while ( true ) { down (& voll ) ; down (& wa ) ; element = read_from_buf ( W ) ; up (& wa ) ; up (& leer ) ; consume ( element ) ; } Listing 3.4: Producer-Consumer: gute Lösung Fazit: Mit sinnvoll gesetzten Semaphoren kann das Problem vollständig gelöst werden. Folgende zwei Blickwinkel müssen dabei beachtet werden: 1. Schutz: Prozesse werden aktiv daran gehindert einen kritischen Abschnitt zu betreten. 2. Kommunikation: Informationen, wie zum Beispiel der Füllstand des Puf- fers, werden an andere Prozesse weitergegeben. 83 3.3.2 Speisenden Philosophen Eines der bekanntesten Beispiele zum Darstellen von Deadlocks ist das sogenann- te «Problem der speisenden Philosophen» von Dijsktra: In der Ausgangssituation sitzen fünf Philosophen rund um einen Tisch. Auf diesem stehen fünf Schalen mit Reis. Jeder Philosoph kann entweder «denken» oder «essen». Zwischen je zwei Philosophen liegt ein Stäbchen. Voraussetzung, dass ein Philosoph speisen kann, ist, dass er das direkt links und das rechts liegende Stäbchen in seinen Händen halten muss. Zu Beginn «denken» alle Philosophen. Sobald einer hungrig wird greift dieser nacheinander nach den beiden Stäbchen. Er behält die Stäbchen so lange, bis er mit dem Essen fertig ist, dann legt er beide an ihren ursprünglichen Platz zurück. Ein Deadlock tritt auf, wenn jeder Philosoph genau ein Stäbchen besitzt. Jeder wartet bis das jeweils zweite Stäbchen verfügbar ist. Niemand kann essen, da je- dem ein Stäbchen fehlt. Die Stäbchen können nicht abgegeben werden, sodass ein Philosoph einem Anderen nicht ermöglichen könnte zu speisen. Die Philosophen warten also ohne Abbruchmöglichkeit aufeinander, der Deadlock entsteht. Um einen Deadlock zu verhindern reicht es dabei nicht, jedem Stäbchen eine ei- gene Semaphore zuzuordnen: Zwei Philosophen prüfen gleichzeitig zuerst die Semaphoren ihrer benachbarten Stäbchen und nachdem beide als «frei» markiert sind greifen sie nach beiden Stäbchen. Da erst das eine und dann das andere Stäb- chen aufgehoben wird, kann es passieren, das ein vermeintlich freies Stäbchen zwischen dem Prüfen und Aufheben von einem anderen Philosophen aufgeho- ben wurde (vgl. Passives Warten 3.4). Eine zusätzliche Semaphore (z.B. Tisch) müsste eingefügt werden, auf die nur ein Philosoph auf einmal zugreifen kann. Diese enthält das Aufnehmen und Wieder- ablegen beider Stäbchen, sowie das Essen. Nur ein Philosoph kann auf einmal den Zustand der Stäbchen prüfen und diese eventuell verändern, unerwartete Verän- derungen sind nicht mehr möglich. Nachteil: Dieser Lösungsansatz ist effizient, da mindestens drei der fünf Stäbchen nicht benutzt werden und nur ein Philo- soph gleichzeitig essen kann. Der parallele Ablauf wurde sequentialisiert. 84 3.4 Verklemmungen 3.4.1 Deadlocks Ein Deadlock ist ein Zustand in dem das System verklemmt ist. Jeder Prozess wartet auf ein Ergebnis eines anderen Prozesses, keiner kann daher weiter arbei- ten. In den folgenden Kapiteln wird auf Deadlocks näher eingegangen. Es werden Bedingungen besprochen, aufgrund derer ein Deadlock entstehen kann und ent- sprechende Strategien für den Umgang mit Deadlocks aufgezeigt. Abbildung 3.6: Deadlock R1 R2 P4 R3 R4 P1 P2 P3 P1 belegt R1 P2 fordert R2 Deadlock Abbildung 3.6 zeigt eine typische Deadlocksituation. P1 , P2 , P3 und P4 sind Pro- zesse und R1 , R2 , R3 und R4 sind Ressourcen. Während der Prozess P3 die Res- source R3 fordert, belegt er noch die Ressource R4. Allerdings belegt gleichzeitig Prozess P4 die Ressource R3 und fordert R4. In dieser Situation kann keiner der beiden Prozesse kann seinen Programmablauf fortsetzten, eine Verklemmung ist entstanden. 3.4.2 Bedingungen für das Auftreten von Deadlocks Nach Coffmann (1971) müssen für das Auftreten alle vier der folgenden Bedin- gungen erfüllt sein. Wird eine der Bedingungen außer Kraft gesetzt, kann kein Deadlock auftreten. Exklusiv nutzbare Ressourcen (engl.: mutual exclusion): Diese können nur 85  von einem Prozess genutzt werden. Sie sind entweder in Benutzung oder nicht. Belegen und Anfordern (engl.: Hold-and-wait): Prozesse, die mehrere Res- sourcen benötigen, geben ihre bereits belegten Ressourcen, während die auf die anderen benötigten Ressourcen warten, nicht frei. Nicht entziehbar (engl.: no-preemption): Sind die Ressourcen einmal einem Prozess zugeordnet, können sie diesem nicht entzogen werden. Zyklische Wartebedingungen (engl.: Circular Wait): Es kann eine zyklische Wartekette von Prozessen geben, in der die Prozesse jeweils auf die, vom nachfolgenden Prozess, belegten Ressourcen warten. 3.4.3 Weitere Verklemmungsarten Livelock Bei einem Livelock versuchen zwei Prozesse gleichzeitig zwei Ressourcen anfor- dern. Während jeder Prozess eine der beiden Ressourcen belegt, stellt er fest, dass die jeweils andere Ressource bereits belegt ist. Beide geben daraufhin ihre belegte Ressource wieder frei, ohne diese verwenden zu können. Obwohl sie nicht im klassischen Sinn blockiert sind, kommen beide Prozesse in ihrem Programmablauf nicht voran, sondern werden weiterhin ab- wechselnd versuchen die Ressourcen zu belegen. Verhungern (engl.: Starvation) Ähnlich wie bei den Scheduling Strategien, kann auch ein Prozess verhungern, wenn er auf eine Ressource warten muss, die ihm nicht zugewiesen wird. Dafür muss kein Deadlock auftreten. Die Ursache könnte beispielsweise in einer unfai- ren Verteil-Strategie der Ressourcen liegen. 3.5 Umgang mit Deadlocks Es gibt vier verschiedene Arten um auf Deadlocks zur Laufzeit zu reagieren: Sie können Ignoriert werden, vor dem Auftreten erkannt werden, während der Lauf- zeit verhindert werden oder voraus im System vermieden werden. 86 3.5.1 Ignorieren von Deadlocks Der trivialste Ansatz ist, ein Deadlock zu ignorieren und dementsprechend nicht aufzulösen. Dies ist nur sinnvoll, wenn die Möglichkeit besteht, dass alle blockier- ten Prozesse irgendwann von außen aufgelöst werden. Diese Strategie wird zum Beispiel bei Prozesstabellen im Linux Kernel angewen- det, um fehlerhafte Prozesse (Waisen, Dämonen), die nach langer Rechendauer entstehen können, zu entfernen. Durch einen Neustart des PCs (Einfluss von au- ßen) wird die Blockierung aufgelöst. All die Prozesskontrollblöcke dieser Prozes- sleichen werden nicht aktiv zur Laufzeit entfernt. Diese Strategie ist nur bei selte- nen und nicht schwerwiegenden Fehlern anwendbar. Schwerwiegendere Fehler würden zu Laufzeitfehlern führen. Kein ignoriertes Deadlock darf, aus nahelie- genden Gründen, Auswirkungen auf den Programmablauf haben. 3.5.2 Ermitteln von Deadlocks Das Betriebssystem erkennt und beseitigt Deadlocks idealerweise bevor sie auf- treten. Um potentielle Deadlocks zu identifizieren und eine deadlockfreie Pro- zessreihenfolge zu garantieren wird der folgende Algorithmus angewendet: 1. Starte mit der Prozessmenge P, die alle Prozesse enthält. 2. Suche Prozess p ∈ P, dessen zusätzliche Anforderungen im aktuellen Zu- stand erfüllbar sind (alle benötigten Ressourcen sind verfügbar). 3. Wenn ein p gefunden wurde, simuliere, dass dieser alle von ihm blockierten Ressourcen wieder freigibt. 4. Entferne p aus P und beginne wieder bei Schritt 2. 5. Falls kein Prozess mehr in P enthalten ist, dann terminiert die Suche → kein Deadlock. 6. falls P ̸= ∅ und in Schritt 2 wird kein Prozess mehr gefunden, dessen Anfor- derungen erfüllbar sind, dann terminiert die Suche. P enthält die Menge der verklemmten Prozesse. Das Deadlock ist bereits geschehen und kann durch vorausschauendes Handeln nicht mehr verhindert werden. Der Algorithmus ermöglicht, zum einen, dass frei werdende Ressourcen berück- sichtigt werden. Zum anderen erlaubt er eine Aussage über das zukünftige Ver- halten und nicht nur über den aktuellen Zustand der Ressourcenverteilung zu treffen. 87 Um entdeckte Deadlocks zu beheben, können die verklemmten Prozesse entwe- der abgebrochen werden, alternativ können ihnen Ressourcen entzogen werden oder alle verklemmten Prozesse werden auf einen gemeinsamen Stand zurückge- führt, bei dem die Verklemmung noch nicht vorlag. Abbruch: Ein verklemmter Prozess kann beispielsweise mit dem Befehl kill sofort beendet werden. Da der Prozess neu gestartet werden muss und seine Aufgabe erneut erfüllen muss, ist diese Strategie häufig ineffizient und da- mit eher unbeliebt. Bei einem Neustart kann nicht garantiert werden, dass der Prozess dieselbe Verklemmung nicht erneut erzeugt. Ressourcenentzug: Die betroffene Ressource wird dem Prozess, der diese belegt, entzogen. Dabei kann es zu Datenverlusten kommen, wenn für die Ressource bestimmte Daten, noch nicht abgespeichert wurden. Es wird si- chergestellt, dass der Deadlock aufgelöst wird, und im weiteren Program- mablauf in genau dieser Form nicht erneut auftreten kann. Zurückführen aller verklemmten Prozesse auf einen gemeinsamen Kon- trollpunkt: Dafür ist es notwendig, dass während dem normalen Program- mablauf regelmäßig Checkpoints definiert werden. Diese Checkpoints si- chern die Zustände aller Prozesse und sind dementsprechend aufwändig zu implementieren. Bei einem aufgetretenen Deadlock kann anhand der Check- points soweit zurückgegangen werden, bis einer gefunden wird, bei dem die Verklemmung noch vermeidbar wäre. Das gesamte System läuft somit mit den gleichen Zuständen in denselben Prozessen erneut los, es ist nicht ga- rantiert, dass derselbe Fehler nicht noch einmal auftritt. Diese Strategie wird vor allem in Bereichen mit niedriger Fehlertoleranz, bei denen eine hohe Zu- verlässigkeit erreicht werden muss, angewendet. 3.5.3 Umgehen von Deadlocks Bei jeder Ressourcen-Belegung wird automatisch zur Laufzeit geprüft, ob die Be- legung problemlos erfolgen kann. Ressourcen Belegungen, die später zu einem Deadlock führen, können verboten werden und der Deadlock wird verhindert, bevor er entstehen kann. Alle Zustände, die nicht zu Deadlocks führen, werden als sicher bezeichnet. 88 Der Bankier-Algorithmus ermöglicht vorauszusagen, welche Ressourcenvertei- lung nicht in einem Deadlock enden kann. Für jede Ressourcenanforderung eines Prozesses wird die Ressource erst probeweise zugeteilt und anschließend geprüft, ob dadurch ein Deadlock entstehen kann. Dabei wird immer von der ungünstig- sten Verteilung der Ressourcen ausgegangen, das heißt: Auch bei einer noch so geringen Wahrscheinlichkeit für das Auftreten, wird die mögliche Verklemmung betrachtet. Falls kein Deadlock aus der Verteilung entstehen kann, erfolgt die Zu- teilung tatsächlich. Eine Möglichkeit die zukünftigen Systemzustände vorauszusagen, besteht dar- in, für jeden Prozess zu ermitteln wie viele Ressourcen (max) dieser benötigt um vollständig zu durchlaufen. Jeder Prozess hat in seinem jetzigen Zustand schon eine gewissen Anzahl an Ressourcen (has) belegt. Für die Prognose des System- zustandes werden n Ressourcen freigegeben und können auf die Prozessmenge verteilt werden. Die entstehende Verteilung gilt als sicher, wenn nach der Neuzu- teilung mindestens ein Prozess max viele Ressourcen besitzt. Dieser kann vollstän- dig durchlaufen, ohne auf weitere Ressourcen warten zu müssen und kann somit nicht mit anderen Prozessen verklemmen. Sollte keiner der Prozesse in dem neuen Zustand max viele Ressourcen besitzen, ist nicht gewährleistet, dass kein Deadlock entstehen kann. Die Verteilung wäre unsicher. Der Algorithmus ist jedoch nicht praxistauglich. Nicht jeder Prozess kann zwin- gend die ihm zugewiesene Ressourcen verwenden → zu idealistisch. Voraussa- gen über die zukünftigen Zustände des Systems zu treffen, ist daher schwierig. Da weder die Prozessmenge, noch deren jeweilige Ressourcenanforderungen vor- ausgesagt werden können. 3.5.4 Vermeidung von Deadlocks Ziel dabei ist es, dass Deadlocks bereits durch den Systemaufbau verhindert wer- den. Eine Verklemmung kann nicht auftreten, wenn eine der Deadlock-Bedingungen nicht erfüllt ist: Die Bedingung der exklusiven Ressource kann außer Kraft gesetzt werden, indem ein sogenannter Spooler verwendet wird. Der Spooler kann von allen Prozessen gleichzeitig verwendet werden und ermöglicht den Zugriff auf 89  die Ressource. Er ist damit der Einzige, der tatsächlich auf die Ressource zu- greift und hat dementsprechend keine Konkurrenz, die auf die Freigabe der Ressource warten könnte. Die Aufträge an die Ressource werden von dem Spooler in einer Warteschlange verwaltet. Für alle Ressourcen ohne Spoo- ler gilt, dass sie nur wenn absolut nötig einem Prozess zugeordnet werden dürfen. Diese Zuweisung soll an so wenig Prozesse wie möglich erfolgen. Die Bedingung, dass ein Prozess eine oder mehrere Ressourcen belegen kann und trotzdem Weitere anfordern kann (hold-and-wait), kann verhindert wer- den, indem ein Prozess alle nötigen Ressourcen vor der eigentlichen Ausfüh- rung anfordern muss. Der Prozess muss mit der Ausführung so lange war- ten, bis alle angeforderten Ressourcen frei geworden sind. Problematisch ist, dass Prozesse ihren Ressourcenbedarf normalerweise nicht im Voraus ken- nen und deswegen unterbrochen werden müssen um eine weitere Ressource anzufordern. Während diese neue Ressource angefordert wird, müssen alle bisher von diesem Prozess verwendeten Ressourcen freigegeben werden, da ein wartender Prozess laut Definition keine Ressourcen belegen darf. Diese weiterhin benötigten Ressourcen können währenddessen von einem ande- ren Prozess belegt werden, sodass der ursprüngliche Prozess weiter warten muss, auch wenn die ursprünglich fehlende Ressource frei geworden ist. Ressourcen können also nicht dauerhaft belegt sein, ein Prozess darf erst starten, wenn alle angeforderten Ressourcen zeitgleich nicht belegt sind. Die Bedingung der nichtunterbrechbaren Ressourcen kann durch die Vir- tualisierung der Ressource umgangen werden. Eine nicht unterbrechbare Ressource einem Prozess zu entziehen, ist nur schwer möglich. Ein Drucker, der beispielsweise gerade eine Seite druckt, kann nicht einem zweiten Pro- zess zugewiesen werden, der ebenfalls drucken möchte. Das Ergebnis wären Abschnitte beider Druckaufträge auf einem gemeinsamen Blatt. Der Drucker kann virtualisiert werden indem die Prozesse in ein gemeinsames PDF schrei- ben, welches anschließend vom eigentlichen Drucker abgearbeitet wird. Die Bedingung des zyklischen Wartens kann umgangen werden, indem ei- ne Reihenfolge festgelegt wird, in der die Ressourcen angefordert werden dürfen. Jeder Ressource wird eine Zahl zugeordnet. Eine Ressource darf nur dann angefordert werden, wenn sie sich in der Reihenfolge hinter einer Res- source befindet, die der Prozess bereits belegt hat. 90  P1 R1 P1 R1 P2 R2 P2 R2 P3 R3 P3 R3 P4 R4 P4 R4 P5 R5 P5 R5 P6 R6 P6 R6 a) erlaubter Zustand b) Deadlock möglich Abbildung 3.7: Algorithmus, um zyklische Wartebedingungen zu verhindern In der Graphik zeigen die gestrichelten Pfeile an, welche Ressourcen ein Pro- zess bereits belegt. Die Anforderungen, die durchgezogenen Pfeile, müssen also auf eine Ressource unter einer bereits belegten Ressource zeigen. In der rechten Abbildung ist diese Bedingung für P6. Damit ist es nicht ausgeschlossen, das ein Zyklus entsteht, der nicht mehr aufgelöst werden kann. 3.5.5 Vergleich der Ansätze Ansatz Verfahren Vorteile Nachteile Ignorieren «Laufen lassen» schnell Systemabstürze Erkennung Periodischer Aufruf Interaktive Reaktion Verlust durch Abbruch Verhinderung Feste Reihenfolge bei Keine Laufzeitprüfungen Statisch, inflexibel Zuteilung; Alle Ressourcen Kein Ressourcenentzug Ineffizient auf einmal zuteilen notwendig Ineffizient Vermeidung Bankiers-Algorithmus Kein Ressourcenentzug Zukünftiger Bedarf muss bekannt sein 91