Prozessverwaltung 2

Koordinierung des zeitlichen Ablaufs mehrerer nebenläufiger Prozesse

• Koordination von Kooperation und Konkurrenz zwischen Prozessen

• bringt Aktivitäten verschiedener Prozesse in eine Reihenfolge

potentiell gleichzeitig ausführbar

zwei Möglichkeiten:

• P werden parallel von mehreren Prozessoren ausgeführt

• quasi parallel - verzahnt von einem Prozessor ausgeführt

• Einschränkung Verzahnungsmöglichkeiten

• alle Verzahnungsmöglichkeiten müssen dasselbe Ergebniss liefern - Determinismus

  
  

Prozess

• Eintrittsprotokoll

• kritischer Abschnitt

• Ausgangsprotokoll

• Schlossvariablen

• Semaphore

• Monitore

• Anweisungen des Programms und einzelnen Schritte des Algorithmus werden in vorbestimmter Folge durchlaufen

• Nach jedem Schritt der Programmausführung steht eindeutig fest, welches der nächste sein wird - vorausgesetzt es gibt ihn

• alle Schritte werden nacheinander ausgeführt

Determinismus

• Ablauf Program eindeutig vorherbestimmt, Schritte immer in derselben Reihenfolge

Determiniertheit

• Programme die bei gleichen Ausgangswerten bei jeder Ausführung das gleiche Ergebnis liefern

• Anweisungen können parallel von mehrereren Prozessoren ausgeführt werden

• Anweisungen können in beliebigier Reihenfolge sequentiell von einem Prozessor ausgeführt werden

• Ausführung einer Anweisung kann in mehrerern Schritten erfolgen - muss nicht unteilbar sein

Kooperation

• Prozesse erfüllen jeweils bestimmte Teilaufgaben im Rahmen der vorgegebenen Gesamtaufgabn

• Produzent/Konsument

• Auftraggeber/Auftragnehmer

Konkurenz

• Die Aktivitäten eines Prozesses drohen die eines anderen zu behindern

• zugriff auf gemeinsame Ressourcen

schließen sich gegenseitig nicht aus

• Datenaustausch über Prozessgrenzen hinweg

• Kommunikation über gemeinsame Variablen

  
  

Zugriff auf gemeinsame Variablen:

• schreibend (modifizierend)

• lesend (nicht modifizierend)

Schreib/Schreib-Konflikt:

Zwei Prozesse wollen nebenläufig eine gemeinsame Variable verändern

Lese/Schreib-Konflikt:

Ein Prozess schreibt Daten in eine gemeinsame Variable, während ein anderer sie nebenläufig liest.

• Wann welche Prozesse auf die Variablen zugreifen, wird dadurch bestimmt, wie schnell die Prozesse ihre Zugriffe durchführen.

• Man sagt, die Prozesse liefern sich ein Wettrennen.

• Programmsysteme sollen unabhängig vom Ausgang des Wettrennens determiniert sein.

• Aktivität A1 abhängig von Aktivität A2 aber nicht andersherum

• Prozesse warten auf austehende Ergebnise eines anderen - solange wird Prozess blockiert, abwarten wird durch await erreicht

• Synchronisation bei Kooperation

• Relation ist transitiv

A1 <-> A2 symmetrisch, nicht transitiv

Anweisungen deren Ausführungen einen gegenseitigen Ausschluss erfordern heißen kritische Abschnitte

Synchronisation bei Konkurrenz

RElation ist symmetrisch

• gegenseitige Ausschluss von Aktivitäten

• dienen der Beschreibung des Informations- und Materialflusses in nebenläufigen Systemen

• bilden einen gerichteten Graphen mit zwei disjunkten Mengen von Knoten

Stellen sind Kreise S

Transistionen sind Rechtecke T

Flussrelationen sind gerichtete Kanten F

Kanal - Stellen, passive Systemkomponenten, in der Information abgelegt werden kann

Instanz - Transistion, aktive Komponente, die Information verarbeitet

• beschreiben den Zustand eines Systems durch Marken (Tokens)

• Zustandsänderung wird durch Schalten von Transitionen

• Kapazität einer Stelle bezeichnet die maximal aufnehmbaren Marken

• Kanten können eine Gewichtung tragen, die angibt, wie viele Marken beim Schalten an einer Eingangsstelle entfernt oder bei einer Ausgangsstelle generiert werde

Schaltregeln

mindestens eine Transistion kann schalten

das entstehende Netz ist wieder lebendig

todesgefährdet wenn nicht vollständig lebendig

wenn nicht geschaltet werrden kann tot

Konflikt bei der Benutzung von Betriebsmitteln

• umstrittenes Mittel nur exklusiv nutzbar

• umstrittenes Mittel kann nicht entzogen werden

• Prozesse blockieren die schon zugewiesenen Betriebsmittel, auch dann wenn sie noch auf weitere Mittel warten

• zyklische Kette von Prozessen, bei denen jeder mindestens 1 MIttel besitzt, auf das der nächste Prozess in der Kette wartet

• achtet darauf, dass mindestens eine der Bedingungen immer nicht erfüllt ist

  • in komplexen Systemen schwierig

• analysiert zukünftige Betriebsmittelanforderungen der Prozesse und verbietet Zustände, die zu Deadlocks führen

  • Mittel die nur kurz genutzt werden, werden ggf. lange blockiert

• feststellen wenn Deadlock auftritt und diesen beseitigen

  • ggf. lange Wartezeiten