Prozessplanung und Deadlock-Management

Multi-Level-Feedback-Warteschlangen

Eine Struktur, die folgende Ziele erreicht:

• Förderung kürzerer Prozesse.
• Förderung von I/O-gebundenen Prozessen zur Optimierung der Gerätenutzung.
• Schnellstmögliche Bestimmung der Prozessart zur entsprechenden Planung.

Ein neuer Prozess wird am Ende der obersten Warteschlange in die Bereit-Liste eingefügt.

Er durchläuft die FIFO-Warteschlange, bis er die CPU erhält.

Wenn der Prozess endet, die CPU für eine I/O-Transaktion verlässt oder auf ein anderes Ereignis wartet, verlässt er die Bereit-Liste.

Zwei-Ebenen-Planung

Das Funktionsschema eines Zwei-Ebenen-Planers ist wie folgt:

1. Eine Teilmenge ausführbarer Prozesse wird in den Hauptspeicher geladen.
2. Der untergeordnete Planer (Dispatcher) wählt daraus für eine begrenzte Zeit Prozesse aus.
3. In regelmäßigen Abständen wird ein übergeordneter Planer aufgerufen, der folgende Aufgaben übernimmt:
   • (a) Entfernt Prozesse aus dem Speicher, die dort lange genug waren (Swapping Out).
   • (b) Lädt Prozesse in den Speicher, die zu lange gewartet haben (Swapping In).
4. Der untergeordnete Planer beschränkt sich wieder auf die im Speicher befindlichen, ausführbaren Prozesse.
5. Der übergeordnete Planer ist für das Verschieben von Prozessen zwischen Speicher und Festplatte (Swapping) zuständig.

Interrupts (Unterbrechungen)

Ein Interrupt ist ein Ereignis, das die Reihenfolge der Befehlsausführung durch den Prozessor ändert. Es wird durch die Computer-Hardware ausgelöst.

Wenn ein Interrupt auftritt, übernimmt das Betriebssystem die Kontrolle und führt folgende Schritte aus:

• Übernimmt die Kontrolle.
• Sichert den Status des unterbrochenen Prozesses (üblicherweise im Prozesskontrollblock - PCB).
• Analysiert den Interrupt.
• Übergibt die Steuerung an die zuständige Interrupt-Behandlungsroutine.

Prozesstypen

Es gibt zwei Arten von Prozessen: Unabhängige Prozesse, die andere Prozesse nicht beeinflussen und von ihnen nicht beeinflusst werden, und kooperierende Prozesse, die andere Prozesse beeinflussen können oder von ihnen beeinflusst werden.

Gegenseitiger Ausschluss & Kritischer Abschnitt

Prozesse müssen häufig miteinander kommunizieren. Dabei können Probleme auftreten, die gelöst werden müssen. Um Probleme bei der gemeinsamen Nutzung von Ressourcen (Shared Resources) zu vermeiden, muss sichergestellt werden, dass nicht mehrere Prozesse gleichzeitig auf dieselbe Ressource zugreifen. Hierfür ist gegenseitiger Ausschluss (Mutual Exclusion) erforderlich. Der Programmabschnitt, der auf die gemeinsam genutzte Ressource zugreift, wird als kritischer Abschnitt (Critical Section) bezeichnet.

Race Conditions (Wettlaufsituationen)

Eine Race Condition (Wettlaufsituation) tritt auf, wenn zwei oder mehr Prozesse unkontrolliert auf eine gemeinsame Ressource zugreifen und das Ergebnis vom zeitlichen Ablauf der Zugriffe abhängt.

Unbegrenzte Blockierung (Starvation)

Dies beschreibt die Situation, in der ein oder mehrere Prozesse niemals genügend Rechenzeit erhalten, um ihre Aufgaben abzuschließen (auch als Starvation bezeichnet).

Zirkuläre Wartebedingung

Dies tritt auf, wenn zwei oder mehr Prozesse eine Kette bilden, in der jeder Prozess auf eine Ressource wartet, die vom nächsten Prozess in der Kette gehalten wird.

Nicht-Entziehbarkeit (No Preemption)

Diese Bedingung besagt, dass eine einem Prozess zugewiesene Ressource diesem nicht gewaltsam entzogen werden kann. Die Ressource wird erst freigegeben, wenn der Prozess sie freiwillig abgibt.

Aktives Warten (Busy Waiting)

Dies tritt auf, wenn ein Prozess versucht, auf eine Ressource zuzugreifen, die bereits einem anderen Prozess zugewiesen ist (und die Nicht-Entziehbarkeitsbedingung gilt). Der anfordernde Prozess verbringt dann seine verbleibende Zeitscheibe damit, wiederholt zu prüfen, ob die Ressource freigegeben wurde. Das bedeutet, Rechenzeit wird durch Warten verschwendet.

Gegenseitiger Ausschluss (Bedingung)

Ein Prozess nutzt Ressourcen exklusiv für eine bestimmte Zeit. Der Codeabschnitt, der diese Ressource verwendet, wird als kritischer Bereich bezeichnet. Die Bedingung des gegenseitigen Ausschlusses besagt, dass sich zu jedem Zeitpunkt nur ein Prozess in seinem kritischen Bereich (bezüglich derselben Ressource) befinden darf.

Belegen und Warten (Hold and Wait)

Ein Prozess hält mindestens eine Ressource. Während er diese Ressource(n) hält, fordert er weitere Ressourcen an, die bereits von anderen Prozessen belegt sind.

Deadlock (Verklemmung)

Das vielleicht gravierendste Problem, das in einer Umgebung mit konkurrierenden Prozessen auftreten kann, ist der Deadlock (auch Verklemmung oder tödliche Umarmung genannt). Für einen Deadlock müssen vier Bedingungen gleichzeitig erfüllt sein:

• Nicht-Entziehbarkeit (No Preemption)
• Zirkuläre Wartebedingung (Circular Wait)
• Gegenseitiger Ausschluss (Mutual Exclusion)
• Belegen und Warten (Hold and Wait)

Deadlock-Bedingungen (Zusammenfassung)

Gegenseitiger Ausschluss (Mutual Exclusion): Prozesse benötigen exklusiven Zugriff auf die Ressourcen, die sie verwenden.

Belegen und Warten (Hold and Wait): Prozesse halten bereits zugewiesene Ressourcen, während sie auf zusätzliche Ressourcen warten.

Nicht-Entziehbarkeit (No Preemption): Ressourcen können einem Prozess nicht entzogen werden; sie müssen vom haltenden Prozess explizit freigegeben werden.

Zirkuläre Wartebedingung (Circular Wait): Es existiert eine geschlossene Kette von Prozessen, bei der jeder Prozess auf eine Ressource wartet, die vom nächsten Prozess in der Kette gehalten wird.