Prozesse und Threads

• First Come First Serve (FCFS)
• Shortest Job First (SJF), auch als Shortest Process First (SPF) bzw. Shortest Process Next (SPN) bezeichnet
• Shortest Remaining Time Next (SRTN)
• Round Robin (RR)
• Priority Scheduling (PS)
• Garantiertes Scheduling und Fair-Share-Scheduling
• Lottery Scheduling
• Earliest Deadline First (EDF) oder auch Minimal Deadline First genannt
• Polled Loop
• Interrupt-gesteuert

SJF (Shortest Job First) ist die beste aller Strategien, was die Verweilzeit betrifft. Ein grosser Nachteil ist jedoch, dass sie zum Verhungern von Prozessen führen kann. Es kann passieren, dass Prozesse nie die CPU zugeteilt bekommen, wenn ständig neue Prozesse ins System kommen, die nur eine kurze Ausführungszeit haben. Länger dauernde Prozesse werden dann nie ausgeführt.

Ein Thread stellt eine nebenläufige Ausführungseinheit innerhalb eines Prozesses dar. Threads werden im Gegensatz zu den traditionellen (schwergewichtigen, heavy-weight) Prozessen als leichtgewichtige (light-weight) Prozesse oder kurz LWP bezeichnet.

Threads sind eindeutig einem Prozess zugeordnet und stellen die eigentliche Scheduling-Einheit des Betriebssystems dar. Jeder Prozess startet zunächst mit einem Start-Thread.

Prozesse können wiederum gemeinsam in Gruppen verwaltet werden, indem sie zu einem Job zusammengefasst werden.

Alle Threads eines Prozesses teilen sich den gemeinsamen Adressraum dieses Prozesses und können damit gleichermassen auf Prozessdaten zugreifen und Programmcodes nutzen.

Prozesse sind Betriebsmittel, deren Verwaltung relativ aufwändig ist. Ein ergänzendes, Ressourcen-schonenderes Konzept hierzu sind die sog. Threads (deutsch: Fäden), die heute in allen modernen Betriebssystemen in unterschiedlicher Weise unterstützt werden.

Threads werden in Programmen verwendet, die eine Parallelverarbeitung ermöglichen, wie z.B. in dialogorientierten Anwendungen.

Rahmenwerke in JAVA nutzen Threads zur Realisierung von grafischen Oberflächen

Auch ein Web-Browser oder auch ein Textverarbeitungsprogramm wie Microsoft Word sind beispielsweise Programme, die Threads intensiv einsetzen.

+ Ein wesentlicher Vorteil von Threads gegenüber Prozessen liegt im wesentlich schnelleren Kontextwechsel

+ Threads sind leichter als Prozesse, da sie Ressourcen wie Speicher, offene Dateien und Netzwerkverbindungen eines Prozesses gemeinsam nutzen. Dies macht Threads ressourcenschonender und effizienter für Aufgaben, die parallel ausgeführt werden können.

User-Level-Threads: Diese Threads werden im Benutzermodus verwaltet

Kernel-Level-Threads: Diese Threads werden direkt vom Betriebssystem verwaltet

Die Unterscheidung zwischen User-Level-Threads und Kernel-Level-Threads erfolgt aufgrund ihrer Verwaltung und Effizienz

Auf Benutzerebene übernimmt die Threadbibliothek das Scheduling und Umschalten zwischen den Threads Das Betriebssystem weiss davon nichts. Die Scheduling-Einheit ist der Prozess

Eine Race Condition tritt auf, wenn mehrere Prozesse unkontrolliert auf gemeinsam genutzte Ressourcen zugreifen. Je mehr Prozesse oder Threads um diese Ressourcen konkurrieren, desto grösser wird das Problem

Programmteile, die nicht unterbrochen werden dürfen, werden auch als kritische Abschnitte bezeichnet

Synchronisationsprobleme

Parallele Ausführung (verzahnte oder verkette Ausführung) 

Interrupts Sperren: Bei dieser Methode werden alle Interrupts während eines kritischen Abschnitts deaktiviert, sodass der laufende Prozess nicht durch einen Kontextwechsel unterbrochen werden kann. 

Peterson und Dekker-Lösung: Reine Softwarelösung

TSL, TAS (Test and Set Lock): Ein atomarer Maschinenbefehl wird verwendet, um den Zugriff auf eine Sperrvariable zu steuern. Dieser Befehl testet und setzt eine Sperre in einem einzigen ununterbrechbaren Schritt. 

Low-Level Primitiven wie TSL (Test and Set Lock) oder Spinlocks arbeiten direkt mit der Hardware und bieten eine sehr feine Kontrolle über den Zugriff auf kritische Abschnitte, erfordern jedoch mehr manuelle Verwaltung durch den Programmierer. Sie sind schneller, aber komplizierter zu handhaben.

High-Level Primitiven wie Semaphore und Monitore bieten eine einfachere Möglichkeit, Synchronisationsprobleme zu lösen. Sie verstecken die Komplexität der Low-Level Primitiven und bieten benutzerfreundliche Mechanismen, um sicherzustellen, dass nur ein Prozess gleichzeitig auf kritische Abschnitte zugreifen kann.

Die korrekte Implementierung eines Semaphors benötigt daher am besten auch eine unteilbare Hardware-Operation wie etwa TSL. Das bedeutet, dass High-Level Primitiven oft auf den Low-Level Mechanismen aufbauen.

Das Semaphore-Konzept ist ein höherwertiger Synchronisationsmechanismus, der speziell entwickelt wurde, um das Mutual-Exclusion-Problem zu lösen. Dieses Problem tritt auf, wenn mehrere Prozesse oder Threads gleichzeitig auf gemeinsam genutzte Ressourcen zugreifen wollen, was zu Konflikten führen kann.

1. Binäre Semaphore (Mutex): Der Zähler hat nur die Werte 0 oder 1 / locked oder unlocked, wodurch immer nur ein Prozess oder Thread gleichzeitig die Ressource nutzen kann.
2. Zählsemaphore: Der Zähler kann belibigeWerte annehmen, um mehrere gleichzeitige Zugriffe auf die Ressource zu ermöglichen, abhängig von der Anzahl der verfügbaren Einheiten der Ressource.

(P): Beim Eintritt in den kritischen Abschnitt wird der Semaphorzähler um 1 reduziert, sofern er grösser als 0 ist. Steht der Zähler auf 0, wird der Eintritt verwehrt und der Prozess/Thread in eine Warteschlange eingereiht.

(V): Beim Verlassen des kritischen Abschnitts wird der Semaphorzähler wieder um 1 erhöht, sodass ein weiterer Prozess/Thread den kritischen Abschnitt betreten kann.

Ein Semaphore wird eingesetzt, wann: mehrere Prozesse oder Threads auf gemeinsame Ressourcen zugreifen müssen, wo: in Multithreading- oder parallelen Umgebungen, und wie: durch einen Zähler, der steuert, wie viele Prozesse gleichzeitig Zugriff auf die Ressource haben.

Semaphoren allein können Deadlocks nicht verhindern.

Ein Thread stellt eine nebenläufige Ausführungseinheit innerhalb eines Prozesses dar. Threads werden im Gegensatz zu den traditionellen (schwergewichtigen, heavy-weight) Prozessen als leichtgewichtige (light-weight) Prozesse oder kurz LWP bezeichnet.

Threads erhalten den vollen Zugriff auf den zugehörigen Prozessadressraum.

Bei einem Prozess-Kontextwechsel wird ein aktiver Prozess unterbrochen. Die gesamte Information des unterbrochenen Prozesses, also der Prozesskontext, wird gesichert und der Prozesskontext des neu aktivierten Prozesses in die Ablaufumgebung (CPU-Register, MMU-Register, …) geladen. Ein Thread-Kontextwechsel innerhalb des laufenden Prozesses kann schneller sein als ein Prozess-Kontextwechsel, weil meist Speicherbereiche des gleichen Prozesses verwendet werden. Ein Austausch von Speicherbereichen ist daher oft nicht erforderlich, was den Betriebssystem-Overhead reduziert.

User-Level-Threads laufen auf der Benutzerebene (Benutzermodus), Kernel-Level-Threads dagegen auf der Kernelebene (Kernelmodus, Systemmodus) ab.

Ein Prozess kann mehrere Threads beherbergen. 1:n-Beziehungen, bei denen ein Prozess nahezu beliebig viele Threads enthalten kann, sind heute in Betriebssystemen üblich.

Es besteht die Möglichkeit, eine eigene Threadklasse zu implementieren, indem man diese von der Basisklasse Thread ableitet. Die Methode run muss überschrieben werden, da dies die Methode ist, die beim Starten eines Threads aufgerufen wird. Die andere Variante, einen Thread zu erzeugen, ist die Definition einer Klasse, die das Interface Runnable implementiert. In der Klasse wird ebenfalls die Methode run implementiert. Als Runnable-Objekt wird die Klasse angegeben, welche das Interface Runnable implementiert. Beide Varianten sind semantisch vollkommen identisch.

In der Methode run, die über die Methode start aufgerufen wird.

Mit dem Systemcall fork wird ein neuer Prozess als Kindprozess des erzeugenden Prozesses erzeugt.

Threads stellen die eigentliche Scheduling-Einheit des Windows-Betriebssystems dar.

Nein, ein Thread wird innerhalb eines Prozesses erzeugt und ist diesem bis zur Terminierung zugeordnet.

Threads sind leichtgewichtiger als Prozesse. Ein Thread-Kontextwechsel innerhalb des laufenden Prozesses kann schneller sein als ein Prozess-Kontextwechsel, weil meist Speicherbereiche des gleichen Prozesses verwendet werden. Ein Austausch von Speicherbereichen ist daher oft nicht erforderlich, was den Betriebssystem-Overhead reduziert.

Threads können auf der Benutzerebene implementiert werden. Vorteil dieser Implementierungsvariante ist die hohe Effizienz, da beim Thread-Kontextwechsel kein Umschalten in den Kernelmodus notwendig ist. Nachteilig ist, dass alle Threads eines Prozesses blockieren, wenn ein Systemaufruf innerhalb eines einzelnen Threads blockiert. Threads können auch auf der Kernelebene implementiert werden. Bei Kernel-Threads werden die Threads im Kernelmodus verwaltet. Die Implementierung von Threads auf Kernelebene hat Vorteile, aber auch Nachteile. Von Vorteil ist beispielsweise, dass das Betriebssystem in der Lage ist, die Zuteilung der Rechenzeit über die Threads zu gestalten und so einen Prozess nicht unnötig zu blockieren. Mit dieser Implementierungsvariante kann man auch Multiprozessorsysteme besser unterstützen, da das Betriebssystem ablaufbereite Threads selbstständig auf die verfügbaren CPUs verteilen kann. Ein weiterer Vorteil für Kernel-Threads ist, dass ein Prozess nicht blockiert ist, wenn ein Thread innerhalb des Prozesses blockiert ist. Ein anderer Thread des Prozesses kann weiterarbeiten. Nachteilig ist beispielsweise, dass im Kernel implementierte Threads nicht so effizient sind, da sie sich bei jedem Thread-Kontextwechsel an den Kernel wenden müssen (Software-Interrupt). Weiterhin ist die größere Systemabhängigkeit von Nachteil.

Ein einfacher Zustandsautomat für einen Prozess hat vier Zustände. Im Zustand „bereit“ ist der Prozess zur Bearbeitung vorbereitet, im aktiven Zustand hat er eine CPU und im Zustand „blockiert“ wartet er auf Ressourcen, um weitermachen zu können. Im Zustand „beendet“ ist der Prozess dann schon nicht mehr im System vorhanden.

Die Zustandsüberg.nge lassen sich wie folgt beschreiben:
• bereit → aktiv: Das Betriebssystem wählt den Prozess aus (Aktivieren)

• aktiv → bereit: Das Betriebssystem wählt einen anderen Prozess aus (Deaktivieren, Preemption, Vorrangunterbrechung)

• aktiv → blockiert: Der Prozess wird blockiert (z. B. wegen Warten auf Input, Betriebsmittel wird angefordert)

• blockiert → bereit: Der Blockierungsgrund wird aufgehoben (Betriebsmittel verfügbar)

• aktiv → beendet: Prozessbeendigung oder schwerwiegender Fehler (Terminieren des Prozesses)

Unix organisiert die Prozesse in einer baumartigen Prozessstruktur, wobei der sog. init-Prozess der Urvater aller zeitlich folgenden Prozesse ist. Der Prozess init hat die PID 1. Bei der Erzeugung eines Prozesses erbt der „Kindprozess“ vom „Elternprozess“ die gesamte Umgebung (inkl. Umgebungsvariablen), alle offenen Dateien und Netzwerkverbindungen sowie den Adressraum mit den Daten- und Codebereichen als Kopie. Er kann dann das gleiche Programm ausführen oder lädt sich bei Bedarf durch Aufruf des Systemcalls execve ein neues Programm und überl.dt somit das Programm des Elternprozesses.

Ein Zombie ist ein Prozess in einem speziellen Zustand. In diesen Zustand gelangt ein Prozess, der terminieren will. Er verweilt solange in diesem Zustand, bis der Elternprozess eine Nachricht über das Ableben des Kindprozesses erhalten hat und terminiert erst dann.

• Ready → Running: Direkte Zuordnung eines Threads zu einem Prozessor.

• Deferred Ready → Running: Zuordnung des ersten Threads zu einem bereits festgelegten Prozessor aus einer speziellen Warteschlange.

• Standby → Running: Dieser Zustandsübergang wird für einen Thread durchgeführt, der schon einem Prozessor zugeordnet ist.

• Waiting → Running: Dieser Zustandsübergang kommt vor, wenn ein Thread die CPU abgegeben hat, um auf ein Ereignis zu warten, z. B. weil ein Seitenfehler aufgetreten ist. Nach Eintreffen des Ereignisses kann der Thread sofort wieder auf Running gesetzt werden.

Der Zustand Running wird aufgegliedert in einen Running-Zustand für Prozesse, die im User- und solche, die im Kernelmodus ablaufen.

Ein Programm ist die (statische) Verfahrensvorschrift für die Verarbeitung auf einem Rechnersystem.

Ein Prozess (in manchen Betriebssystemen auch Task genannt) stellt auf einem Rechnersystem die Ablaufumgebung für ein Programm bereit und ist eine dynamische Folge von Aktionen mit entsprechenden Zustandsänderungen, oder anders ausgedrückt, die Instanziierung eines Programms.