PilotOS: Prozesse 2 (Zustände und Blockierung)

In meinem ersten Artikel über Threads stand die konkrete Implementierung im Vordergrund, für diesen Artikel gibt es (noch) keine Implementierung in PilotOS, daher hier etwas Theorie über Prozesse, deren Zustände und Blockierung.

Ein Prozess ist eine Einheit der Ausführung oder Code, der sich in Ausführung befindet. Bei der Definition spielt es keine Rolle, ob der Code tatsächlich gerade ausgeführt wird, sondern es genügt, wenn der Code “bereit” ist zur Ausführung, d.h. der Code ist anspringbar, hat Speicher, und könnte theoretisch ausgeführt werden. In realen Betriebssystemen gibt es aber einige Constraints, wann ein Prozess ausgeführt wird. Dazu wurden Prozesszustände eingeführt.

Ein Prozesszustand gibt an, in welchem Zustand eines Automaten sich ein Prozess befindet. Ein Prozess kann meist nur dann ausgeführt werden, wenn er sich im Speicher befindet (siehe virtueller Speicher, MMU, Paging), und nicht auf andere Prozesse wartet. Ein Prozess kann beispielsweise dann auf andere Prozesse wechseln, wenn sich der andere Prozess ein Betriebsmittel genommen hat, welches nur exklusiv genutzt werden kann, aber beide Prozesse benötigen.

Betriebsmittel werden vom Betriebssystem verwaltet. Man unterscheide physische und logische BMs. Physisch ist bspw. die Festplatte, der Speicher; logisch eine Datei. Um einen sicheren Zugriff auf Betriebsmittel gibt es in jedem Betriebssystem den gegenseitigen Ausschluss (Mutex, mutual exclusion) um sicherzustellen, dass nur ein Prozess (bzw. genereller nur k Prozesse) einen kritischen Abschnitt ausführen dürfen. Ein kritischer Abschnitt ist Code, der, wenn er von mehreren Prozessen nebenläufig ausgeführt wird, zu nicht mehr gutzumachendem Schaden im System führen kann.

Es gibt einige Designkritierien für die Implementierung von Mutex. Bspw. Lebendigkeit, d.h. kein Prozess hält ein Betriebsmittel unendlich lange, Sicherheit, d.h. etwas nicht mehr gut zu machendes schlechtes darf nicht passieren, Fairness, die unterschiedlich definiert sein kann. Hier nehmen wir folgende Fairness an: kein Prozess muss unendlich lang warten. Anhand dieser Kritieren kann eine Policy implementiert werden, die angibt wie und wann wartende Prozesse freigegeben werden.

Ein Blockieren eines Prozesses kann entweder vom Prozess selbst erfolgen, oder durch das Betriebssystem beim Zugriff auf ein Betriebsmittel. Bspw. ist es manchmal notwendig auf andere Prozesse zu warten, um synchronisiert arbeiten zu können. Die erste Möglichkeit um auf andere Prozesse zu warten ist einen Busy Wait zu implementieren; d.h. eine while-Schleife, die nachschaut, ob die Bedingung, auf die gewartet wird, schon erfüllt ist. Das ist aber sehr verschwenderisch auf Rechenzeit, weil der Scheduler diesen Prozess weiterhin plant und dieser Prozess sein Zeitintervall nur dafür verwendet zu warten.

Sinnvoller wäre es, diesen Prozess nicht mehr zu schedulen bis die Bedingung erfüllt ist. Dazu setzt man seinen Prozesszustand auf “wartend” oder “blockiert”, was angibt, dass der Prozess auf etwas wartet. Die Bedingung muss ebenfalls gespeichert werden (bspw. in Form eines Mutex-Deskriptors). Wird dieses Mutex (bspw. in Form eines Semaphors implementiert) freigegeben, setzt das Betriebssystem alle darauf wartenden Prozesse in den “bereit”-Zustand. Je nachdem, wie viele Prozesse in den kritischen Abschnitt dürfen, kann auch nur ein Prozess ausgewählt werden, der in den “bereit”-Zustand wechselt.

D.h. wir haben grundlegend drei Prozesszustände: “laufend”, d.h. der Prozess wird in diesem Moment von der CPU ausgeführt, “aktiv” – der Prozess wartet auf die CPU, kann aber ausgeführt werden und “blockiert, wartend” – der Prozess wartet auf Freigabe eines Mutex.

Ein Mutex kann verschiedenen implementiert sein. Es gibt in gewöhnlichen Betriebssystemen meist eine Semaphor-Implementierung, aber auch Monitore. Alternativ kann das auch durch eine bool’sche Zustandsvariable realisiert werden. Der Trick dabei ist, dass, wenn mehrere Prozesse involviert sind, die Implementierung etwas schwierig ist. So muss beim Eintritt in einen kritischen Abschnitt geprüft werden, ob die Variable gesetzt ist (bzw. die Semaphore einen bestimmten Wert erreicht hat). Falls ja, darf der Prozess nicht in den kritischen Abschnitt und muss warten.

Ist die Variable nicht gesetzt, darf der Prozess in den kritischen Abschnitt, muss aber noch (mit einem zweiten Befehl) die Variable setzen. Wird er jetzt verdrängt, kann problemlos ein zweiter Prozess in den kritischen Abschnitt und etwas Schlimmes könnte passieren (siehe Race Condition). Dafür haben die meisten Prozessoren einen Befehl, der gleichzeitig eine Variable testen kann, und sie setzt, sodass kein anderer Prozess in den kritischen Abschnitt gelangen kann.

Alternativ könnte für den Zeitraum, in dem sich ein Prozess im kritischen Abschnitt befindet, der Interrupt ausgeschaltet werden. Das hätte zur Folge, dass der Prozess nicht durch Timer-Interrupts unterbrochen werden kann, aber auch, dass er generell nicht unterbrochen werden kann. Wird diese Methode also angewandt, muss der Programmierer höllisch darauf achten, dass sein kritischer Abschnitt sehr kurz ist, um das System nicht unnötig auszubremsen, da in dieser Zeit kein anderer Prozess ausgeführt werden kann. Wiederum könnt er die Interrupts auch nur für den Zeitraum deaktivieren, in dem er die Variable testet und setzt, und dann wieder aktivieren.

Das könnte Dich auch interessieren...