Betriebssystemeinführung PDF

Einführung 6 1 Einführung 1.1 Was ist ein Betriebssystem? Ein Betriebssystem ist ein komplexes Programm, das dem Rechnerbenutzer (Anwender, Programmierer, Administrator) folgendes bietet: 1. Verwaltung der...

Einführung 6 1 Einführung 1.1 Was ist ein Betriebssystem? Ein Betriebssystem ist ein komplexes Programm, das dem Rechnerbenutzer (Anwender, Programmierer, Administrator) folgendes bietet: 1. Verwaltung der Peripheriegeräte Das Betriebssystem bietet einen bequemen Zugriff auf Hardware wie Speicherme- dien (Platten, CD, Bänder), Drucker oder Bildschirm. Der Benutzer muss sich nicht um Gerätetechnik kümmern, auch nicht um die Koor- dination konkurrierender Zugriffe durch mehrere Prozesse. 2. Abstrakter Rechner Ein Betriebssystem kann die Eigenheiten der Rechnerplattform völlig verdecken. Es ermöglicht damit eine plattformunabhängige Rechnernutzung. Früher erlaubte dies zunächst nur eine einheitliche Verwendung von Rechnern der- selben Rechnerfamilie eines Herstellers. Heute sieht man insbesondere am Bei- spiel UNIX, dass ein einziges Betriebssystem die Verwendung völlig unterschiedli- cher Rechnertypen gestattet, vom PC über den Großrechner bis zum Supercom- puter. Der Vorteil: Aufwendig entwickelte Software und mühsam erworbene Kenntnisse des Benutzers im Umgang mit dem Rechner sind dadurch plattformunabhängig und übertragbar. 3. Sammlung von Dienstprogrammen Ein Betriebssystem beinhaltet normalerweise eine ganze Reihe ständig benötigter Dienstprogramme, etwa Kopier- oder Sortierprogramme. 4. Sammlung von Kommunikationsmechanismen Das Betriebssystem ist die Schnittstelle zum Rechnernetz und dient somit als Aus- gangspunkt für unterschiedlichste Kommunikationsaktivitäten. In modernen Betriebssystemen sind oft verschiedene Familien“ von Kommuni- ” kationsprotokollen (z.B. TCP/IP) integriert. Die Protokolle bilden die Basis für Kom- munikationsdienste aller Art, im lokalen Netzwerk, unternehmensweit oder im Inter- net. Einführung 7 1.2 Grundbegriffe Nachfolgend gehen wir der Einfachheit halber davon aus, dass ein Rechner nur einen (Zentral-)Prozessor (CPU = central processing unit“) hat. Die Mechanismen zur Un- ” terstützung von Mehrprozessormaschinen werden jeweils explizit und gesondert behan- delt. Prozess (Task) Ein Prozess ist ein Programm, das gerade ausgeführt wird. Die Definition wird in 3, S. 17 verfeinert. Multitasking Ein Multitasking-Betriebssystem führt mehrere Programme gleichzeitig aus. Ge- nauer gesagt stehen mehrere Prozesse zur selben Zeit im Hauptspeicher. Damit ein Programm Bearbeitungsfortschritte macht, benötigt es den Prozessor des Rechners. Es entsteht eine Konkurrenzsituation: N im Speicher befindlichen Programme konkurrieren um einen Prozessor. Zwei Aktivitäten sind nebenläufig (engl. concurrent“), wenn sie zeitlich neben- ” ” einander“, also parallel ausführbar sind. Programme werden im Multitaskingsystem nicht nacheinander ausgeführt, sondern nebenläufig, d.h. zeitlich verschränkt ( qua- ” siparallel“) oder - bei Mehrprozessorsystemen - echt parallel. Die quasiparallele Bearbeitung mehrerer Prozesse in einem Einprozessorsystem wird dadurch gewährleistet, dass das Betriebssystem allen Prozessen reihum je- weils für ein kurzes Zeitquantum (z.B. 100ms) die CPU zuteilt. Aus Sicht des ein- zelnen Prozesses gibt es also abwechselnd immer wieder Wartephasen und Bear- beitungsphasen. Aus Sicht des Betriebssystems ist die CPU eine Ressource, die abwechselnd den darum konkurrierenden Prozessen zugeteilt wird. Ein Wechsel der CPU-Zuteilung von einem Prozess zu einem anderen heißt Kontextwechsel. Die Strategie, nach der die CPU an die konkurrierenden Prozesse vergeben wird, bezeichnet man als Scheduling“-Strategie. (Scheduling heißt in diesem Zusammenhang Einplanung“ ” ” oder Terminplanung“.) Die verantwortliche Betriebssystemfunktion nennen wir den ” Scheduler“. ” Mehrbenutzerbetrieb (Timesharing-Betrieb) Mehrbenutzerbetrieb ermöglicht es verschiedenen Nutzern, gleichzeitig mit einem Rechner zu arbeiten. Die Benutzer können z.B. mit direkt an den Rechner ange- schlossenen Terminals arbeiten, oder über Netzwerkverbindungen. Beim heute üblichen Timesharing-Betrieb hat jeder Nutzer das Gefühl, den Rechner alleine zu nutzen. Dies erfordert neben Multitasking-Unterstützung vom Betriebssy- stem eine Zuordnung von Ressourcen - insbesondere Dateien und Hauptspeicher- bereichen - zu Benutzern (bzw. Prozessen) und eine strikte Zugriffsrechtskontrolle. Kein Programm soll die Daten eines anderen Programms zerstören oder auch nur lesen können, sei es durch fehlerhafte Programmierung oder aus Absicht. Einführung 8 Die immer wieder auftretenden Wartephasen eines interaktiven Prozesses müssen beim Mehrbenutzerbetrieb für den Anwender unmerklich kurz sein. Dann sieht er einen kontinuierlichen Bearbeitungsfortschritt seines Programms. Multiprozessorsystem Ein Rechnersystem mit mehreren Prozessoren heißt Multiprozessorsystem. Das Betriebssystem unterstützt Multitasking. Es muss dafür sorgen, dass soviele Pro- zesse echt parallel bearbeitet werden können, wie Prozessoren vorhanden sind (vgl. auch Multithreading – 3.6, S. 28). Stapelverarbeitung (Batchbetrieb) Bei Stapelverarbeitungsbetrieb stellt ein Benutzer einen Bearbeitungsauftrag (Job) zur späteren Bearbeitung in eine Auftragswarteschlange. Ein Auftrag besteht aus einer Reihe aufzurufender Programme und zugehörigen Parametern. Das Betriebssystem arbeitet die Auftragsstapel nach und nach ab. So können lang- wierige Berechnungen in die Nacht oder aufs Wochenende verlegt werden. Echtzeitsystem Ein Echtzeitsystem ( real time system“) dient zur Kontrolle und Steuerung rechner- ” externer Abläufe (z.B. Steuerung eines Kraftwerks). Das Betriebssystem muss für dringende externe Signale bestimmte anwendungsabhängige maximale Reaktions- zeiten garantieren können. Viele Betriebssysteme können dies deshalb nicht, weil eine sofortige Unter- brechung bestimmter Betriebssystemaktivitäten die vom Betriebssystem selbst benötigten Datenstrukturen in einem inkonsistenten Zustand hinterlassen würde. Virtuelle Maschine Eine virtuelle Maschine ist ein Betriebssystem, das auf einem Rechner andere Rechner und Betriebssysteme emulieren kann. Die bekannteste virtuelle Maschi- ne ist das IBM-System VM ( virtual machine“). Ein anderes bekanntes Beispiel ist ” vmware“, das auf einem realen PC beliebig viele virtuelle“ PCs erzeugen kann, so ” ” dass mehrere Betriebssysteme wie z.B. Windows, Linux oder BSD-UNIX gleichzei- tig genutzt werden können. Verteiltes Betriebssystem Ein verteiltes Betriebssystem erlaubt (im Idealfall) dem Anwendungsentwickler, eine Gruppe vernetzter Rechner so zu benutzen wie einen einzigen Rechner. Es verteilt - möglichst transparent für den Anwender - die Bearbeitung des Anwendungspro- gramms auf mehrere Rechner im Netz. Es besteht aus mehreren auf die vernetzten Rechner verteilten und miteinander kooperierenden Prozessen. Aufbau eines Betriebssystems 9 2 Aufbau eines Betriebssystems Wir beschreiben zwei konkurrierende Architekturmodelle: Monolithische Architektur – der klassische“ Aufbau ” Mikrokern-Architektur – die moderne Konkurrenz“ ” Anschliessend diskutieren wir ein Schichtenmodell für ein monolithisches Betriebssy- stem. 2.1 Monolithische Architektur Der Anwender kann das Betriebssystem als eine Sammlung von Funktionen ansehen, die bei Bedarf aufgerufen werden, genauso wie Funktionen des Anwendungsprogramms oder Funktionen einer Standardbibliothek. Natürlich gehören zum Betriebssystem auch noch eine ganze Reihe von Datenstrukturen zur Verwaltung der Geräte, Benutzer, Pro- zesse usw. Stellen wir uns also vor, ein Betriebssystem ist in einer höheren Programmiersprache wie C implementiert und besteht aus Funktionen und Daten. Wenn das Betriebssystem in Form eines einzigen Programms vorliegt, heißt es monolithisch. Programme im Hauptspeicher Anwendungsprogramm Anwendungsprogramm Betriebssystem Anwendungsprogramm Hauptspeicher Aufbau eines Betriebssystems 10 2.1.1 Systemaufruf Die Implementierung von Systemaufrufen ist sehr aufschlussreich für das Verständnis der Systemarchitektur. Betrachten wir ein Anwendungsprogramm, das genau wie das Betriebssystem aus Funk- tionen und Daten besteht.1 Dieses Anwendungsprogramm benutzt regelmäßig Betriebs- systemdienste durch Aufruf von Betriebssystemfunktionen. Solche Aufrufe sind insofern etwas besonderes, als die aufgerufenen Systemfunktionen ja Bestandteil eines anderen Programms sind. Betrachten wir ein Beispiel: Das Anwendungsprogramm ruft innerhalb der Funktion main eine Systemfunktion write zum Schreiben von Daten auf den Bildschirm auf. Die write-Funktion ist, genauer betrachtet, nicht Bestandteil des Betriebssystems, son- dern eine dem Anwendungsprogramm zugehörige Funktion. Deren Aufgabe ist die Akti- vierung einer entsprechenden Betriebssystemfunktion, nehmen wir an, diese heißt sys- write. Dazu wird ein spezieller Hardwaremechanismus verwendet (SVC = supervisor call“ oder ” Trap): Die Anwendung (write-Funktion) hinterlegt eine dem Systemaufruf (syswrite) zu- geordnete Identifikation zusammen mit den Aufrufparametern an einer bestimmten dem Betriebssystem bekanntgemachten Stelle im Hauptspeicher und erzeugt einen Trap. Der Hardware-Trap unterbricht die Ausführung des Anwendungsprogramms (also der write- Funktion) und veranlasst den Aufruf einer Behandlungsroutine ( trap handler“), die Be- ” standteil des Betriebssystems ist. Die CPU-Kontrolle ist damit vom Anwendungsprogramm (Prozess im Anwendungsmodus / user mode“) an das Betriebssystem übergeben worden. Der Prozess befindet sich ” nun im Systemkernmodus ( kernel mode“). Dieser Zustandübergang spiegelt sich auf der ” Hardwareebene wieder: Beim Übergang wird der Prozessor in einen privilegierten Modus umgeschaltet. In diesem Modus ist der Befehlssatz ggf. erweitert und hardwareseitige Speicherzugriffsbeschränkungen sind aufgehoben. Die von der Hardware aktivierte Trap-Behandlungsroutine kopiert die Parameter für syswrite in den Speicherbereich des Betriebssystems. Anhand der hinterlegten Systemfunktions-Identifikationsnummer kann die Trap-Behandlungsroutine feststellen, dass die Systemfunktion syswrite aufgerufen werden muss. Nach Prüfung der Argumen- te auf Konsistenz wird von der Trap-Behandlungsroutine der Aufruf der gewünschten Sy- stemfunktion durchgeführt. Nach Beendigung des syswrite-Aufrufs kopiert die aufrufende Funktion das Funktions- resultat bzw. Fehlercodes in den Speicherbereich der Anwendung und beendet die Trap-Behandlung. Der Prozessor wird wieder in den normalen (unprivilegierten) Zu- stand zurückversetzt und die Kontrolle wieder an die write-Funktion des Anwendungs- programms übergeben. 1 Wir vergessen dabei für einen Moment, dass Anwendungen heute oft separate, dynamisch angebunde- ne (und gemeinsam benutzbare) Bibliotheken verwenden. Aufbau eines Betriebssystems 11 Systemaufruf im monolithischen Betriebssystem main Anwendungsprogramm Funktionsaufruf (Prozess im Anwendungsmodus) write Trap Hardware Trap−Mechanismus trap handler Betriebssystem Funktionsaufruf (Prozess im Systemmodus) syswrite 2.2 Mikrokern-Architektur Softwaretechnisch ist gegenüber einer monolithischen Struktur eine klar modularisier- te Architektur vorzuziehen. Anstelle eines einzigen großen Betriebssystem-Programms“ ” werden die Systemdienste auf mehrere separate Programme verteilt. Da diese Program- me auftragsorientiert Dienstleistungen erbringen, bezeichnen wir ihre Aktivierungen als Server -Prozesse. Ein Anwendungsprozess kommuniziert mit einem Serverprozess durch einen Inter- prozesskommunikations-Mechanismus (IPC= interprocess communication“). Er sendet ” dem Serverprozess einen Auftrag und erhält eine Antwort. Natürlich können nicht alle Betriebssystemfunktionen in Form separater Serverprozesse implementiert werden. Zumindest eine grundlegende Prozessverwaltung, CPU-Zuteilung und Interprozesskommunikation wird durch einen in klassischer Weise aktivierten Sy- stemkern erfolgen. Wie sollte sonst ein Anwendungsprozess überhaupt entstehen, wie sollte er Nachrichten mit einem Serverprozess austauschen können bzw. den Prozessor zur Auftragsausführung an diesen übergeben? Wenn also nur die Basisfunktionalität eines Betriebssystems durch einen Trap-aktivierten Systemkern übernommen wird, ist dieser Kern (hoffentlich) recht klein und wird deshalb Mikrokern ( micro kernel“) genannt. Andere Betriebssystemdienste sind durch ständig ” aktive, auf Aufträge wartende 2 Betriebssystem-Serverprozesse realisiert, z.B. Dateisy- 2 Ein Serverprogramm kann auch bei Bedarf erst geladen werden. Dies macht insbesondere dann Sinn, wenn seine Dienste nur selten benötigt werden. Aufbau eines Betriebssystems 12 stemdienste, Hauptspeicherverwaltungsstrategien, graphische Benutzeroberfläche. Programme im Hauptspeicher Anwendungsprogramm Anwendungsprogramm Betriebssystem− Kern Betriebssystem− Server A Betriebssystem− Server B Anwendungsprogramm Betriebssystem− Server C 2.2.1 Systemaufruf Die Implementierung von Systemaufrufen ist bei Mikrokernsystemen anders realisiert als bei monolithischen Systemen: durch Auftragserteilung an einen Serverprozess unter Ver- wendung des zugrundeliegenden IPC-Mechanismus. Aufbau eines Betriebssystems 13 Systemaufruf bei Mikrokernsystemen Prozess A Prozess B Anwendungsprogramm Betriebssystem−Serverprogramm main write− Funktionsaufruf Dienst write IPC−Mechanismus Man beachte, dass der Anwendungsprozess einen Trap zur Aktivierung des Mikrokerns benutzt, um dem Systemdienstserver eine Nachricht zu schicken. Der Systemdienstser- ver benutzt seinerseits einen Trap zum Empfang. Die Rolle des Systemkerns bei der Nachrichtenübertragung Prozess A Prozess B Anwendungsprogramm Betriebssystem−Serverprogramm main write− Funktionsaufruf Dienst write Trap Nachricht Trap receive−Resultat send−Parameter Nachricht send receive Mikrokern Aufbau eines Betriebssystems 14 Ein Systemdienstserver kann seinerseits über die Trap-Schnittstelle die Basisdienste des Mikrokerns benutzen, weil er Basisdienste benötigt, um seinen Auftrag auszuführen, oder um Resultate an den auftraggebenden Prozess zurückzuschicken. Eine spezielle Variante eines Systemdienstservers ist ein Server, der eine komplette Systemschnittstelle implementiert. So gibt es für das Betriebssystem Mach einen Ser- verprozess, der die UNIX-Systemaufrufschnittstelle komplett implementiert. Auch das POSIX-Subsystem von Windows NT dient diesem Zweck. Weitere Formen der Arbeitsteilung sind möglich: Ein Systemdienstserver delegiert einen Teil der Arbeit an einen anderen System- dienstserver Der Mikrokern benutzt einen Systemdienstserver für seine Zwecke 2.2.2 Vor- und Nachteile Die Modularisierung des Betriebssystems in Form eines Mikrokerns und separater Ser- verprozesse macht das Betriebssystemdesign klarer, flexibler und von der Komplexität her besser beherrschbar. Probleme bereitet noch die Effizienz der Systemaufrufe, da bei der Client-Server-Struktur zusätzlicher Aufwand anfällt: Der Auftrag muss zum Systemdienstserver übertragen werden Die CPU-Kontrolle muss an den Systemdienstserver übertragen werden Das Resultat muss zum Anwendungsprozess zurückgeschickt werden Die CPU-Kontrolle muss an den Anwendungsprozess übertragen werden Mit verschiedenen Optimierungsmethoden versucht man, den Zusatzaufwand in Grenzen zu halten. 2.3 Schichtenmodell Innerhalb monolithischer Betriebssysteme lassen sich meist mehrere aufeinander auf- bauende Schichten mit folgenden Eigenschaften identifizieren: Jede Schicht definiert eine Reihe von Funktionen. Diese Funktionen werden als Diensteschnittstelle für die darüberliegende Schicht angeboten. Die Implementierung der Funktionen einer Schicht benutzt ausschliesslich die Schnittstelle der darunter angeordneten Schicht, ein Durchgriff nach weiter unten“ ” ist weder nötig noch möglich. Aufbau eines Betriebssystems 15 Jede Schicht entspricht einer Abstraktionsebene in einem abstrakten Modell des Rechnersystems, unten“ heißt hardwarespezifisch, oben“ heißt anwendungsori- ” ” entiert und völlig hardwareunabhängig. Schichtenmodell eines Betriebssystems Anwendung Standardbibliotheken Systemaufruf−Schnittstelle Betriebssystem Dateisystem Basisfunktionen (CPU− / Prozess− / Hauptspeicher− Cache−Verwaltung, IPC ) Hardware−Abstraktionsschicht Hardware In diesem Modell dient die Hardware-Abstraktionsschicht zur Kapselung hardwa- reabhängiger Teile des Systems. Dazu gehören 1. plattformspezifische Funktionen Diese Funktionen isolieren die Eigenschaften einer Rechnerplattform, d.h. eines Rechnertyps wie Pentium-PC“ oder Sun Ultra 1“. Plattformspezifische Hardware ” ” sind z.B. CPU mit Speicherverwaltungseinheit (MMU), Cache und Bussysteme. Zu den plattformspezifischen Funktionen gehören z.B. hardwareabhängige Anteile des Kontextwechsels oder der Hauptspeicherverwaltung. Die Kapselung der Plattformeigenschaften ist Voraussetzung für eine einfache Por- tierung eines Betriebssystems auf unterschiedliche Plattformen. 2. Hardwaretreiber Ein Treiber ist ein Modul zur Steuerung eines bestimmten, meist optional in den Rechner integrierbaren Hardware-Controllers (z.B. Festplatten, Netzwerkkarten, Scanner, Graphikkarte). Diese Module werden genau dann benötigt, wenn ein ent- sprechendes Gerät genutzt werden soll und können oft dynamisch in das Betriebs- system eingebunden werden. Aufbau eines Betriebssystems 16 Als Beispiel für die Nutzung aller Schichten betrachten wir ein C-Programm, das unter UNIX eine Festplattenausgabe macht. Das Programm benutzt eine Funktion aus der ANSI-C-Standardbibliothek, (z.B. printf ). Diese ist betriebssystemunabhängig. Die Standardbibliothek benutzt die Systemschnittstelle des Betriebssystems, im Beispiel die UNIX-Schnittstellenfunktion write. Diese ist betriebssystemspezi- fisch. Die write-Funktion wird über den Systemaufrufmechanismus eine Funktion des Dateisystems aufrufen. Diese Funktion wird z.B. Zugriffsrechte prüfen und schließ- lich die Daten in den Cache-Bereich übertragen. Das Cache-Modul übernimmt die Daten in einen als Puffer reservierten Haupt- speicherbereich. Das Modul stellt sicher, dass nicht für jedes einzelne auszuge- bende Byte ein physikalischer Plattenzugriff erfolgt, indem es zunächst einmal die auszugebenden Daten sammelt. Zu einem späteren Zeitpunkt wird ein Ein-/Ausgabe-Auftragspaket“ ( I/O-Request“) ” ” für den Plattentreiber erstellt und damit der Treiber beauftragt, die Daten tatsächlich auf die Platte zu übertragen. Der Treiber überträgt die Hardware-Befehle zur Ausgabe der Daten an den zuständigen Controller. Dies ist hardwarespezifisch. Ein solches Modell kann nur als Annäherung an die Schichtenarchitektur realer Syste- me betrachtet werden. In unserem UNIX-Beispiel gibt es sicher keine Möglichkeit, am Dateisystem vorbei irgendwelche Geräte zu manipulieren, (Ein-/Ausgabe von Daten). Ein Erfragen der Systemzeit benötigt jedoch keine Dateisystemfunktion, erfolgt als direkter Zugriff auf Information, die von der Schicht unterhalb des Dateisystems geliefert wird. Prozesse und Threads 17 3 Prozesse und Threads 3.1 Prozessmodell, Grundbegriffe Ein Prozess ist ein Programm zur Ausführungszeit, sozusagen die dynamische Sicht eines Programms. Für das Betriebssystem ist ein Prozess ein zu verwaltendes komplexes Objekt mit diversen Bestandteilen. Ein Prozess benötigt zur Ausführung bestimmte Ressourcen, wie Hauptspeicher, Pro- zessor, Dateien, E/A-Geräte (E/A = Ein-/Ausgabe). Zur Kontrolle der Prozesse verwendet das Betriebssystem eine Prozesstabelle, in der für jeden Prozess eine Reihe prozessspezifischer Verwaltungsinformationen gespeichert wird. Wir nennen den zu einem Prozess gehörenden Eintrag in der Tabelle Prozessta- belleneintrag oder Prozessdeskriptor. Prozessbestandteile: Programmspeicher des Prozesses: programmspezifische Hauptspeicherbereiche – Code - Maschinenebefehle (durch Compiler und Linker aus dem Programm- quelltext erzeugt) – Statische Daten - statisch (für die gesamte Ausführungszeit) reservierte Speicherbereiche für Variablen und Konstanten des Programms – Laufzeitstack - dynamisch verwalteter Speicher, in dem die für Unterpro- grammaktivierungen notwendigen Daten (Parameter, lokale Variablen, Rück- sprungadresse usw.) abgelegt werden Hinzu kommen bei vielen Systemen noch ein Speicherbereich, den wir Programm- ” kontext“ (engl: environment“) nennen wollen. Er enthält Argumente, die dem Pro- ” gramm beim Aufruf übergeben wurden, und Umgebungsvariablen. Was ist mit dem Heap“-Speicher, der für dynamisch erzeugte Datenstrukturen ” benötigt wird ? Aus Sicht des Betriebssystems wird typischerweise Stack und Heap im selben Speicherbereich untergebracht. Der Programmspeicher ist für andere Prozesse nicht zugreifbar. Prozesse und Threads 18 Kontext Maschinencode statische Daten Stack Programmspeicher− Layout Heap Bestandteile des Prozessdeskriptors – eindeutige Prozessidentifikation – Zustand (vgl. Zustandsmodell) – Zugriffsrechtsdeskriptor - definiert die Rechte des Prozesses beim Zugriff auf Ressourcen wie Dateien, Hauptspeicherbereiche usw. – Dateideskriptoren - definieren den Zustand der vom Prozess geöffneten Da- teien (z.B. aktuelle Lese-/Schreibposition, Öffnungsmodus) – Hauptspeicherdeskriptor - dient zum Auffinden und zur Zugriffskontrolle der zum Prozess gehörigen Speichersegmente – Maschinenzustand (Register, Programmzähler, Statuswort usw.) (auch Prozesskontrollblock genannt) Er wird bei Unterbrechung der Prozessausführung gespeichert, um nach der Unterbrechungsphase die Wiederhestellung des Maschinenzustands und da- mit die Fortführung der Ausführung zu ermöglichen – Priorität(en) - bestimmen die Geschwindigkeit der Prozessbearbeitung – Ressourcenverbrauch - für Abrechnungszwecke (CPU-Verbrauch, Hauptspei- chernutzung usw.) Der Prozessdeskriptor3 wird vom Betriebssystem angelegt, aktualisiert und gelöscht. Der Anwender kann üblicherweise lesend darauf zugreifen (vgl. z.B. das UNIX-Kommando ps – process status“) ” 3 In der Literatur wird der Prozessdeskriptor teilweise Prozesskontrollblock genannt, wir haben diese Be- zeichnung aber schon für den innerhalb des Prozessdeskriptors gesicherten Maschinenzustand verwendet. In der UNIX-Literatur findet man auch die Bezeichnung Prozessstruktur, da im C-Quelltext dafür der Typ struct process verwendet wird. Prozesse und Threads 19 Komplexe Prozessdeskriptor-Bestandteile (z.B. Dateideskriptor, Hauptspeicherde- skriptor) werden durch separat gespeicherte Datenstrukturen realisiert, im Pro- zessdeskriptor verweist dann je ein Zeiger darauf. 3.2 Prozesszustände Wir unterscheiden zunächst drei Prozesszustände: 1. ausführend (engl. running) Der ausführende Prozess hat die Kontrolle über den Prozessor. In einem Mehrpro- zessorsystem mit N Prozessoren gibt es N ausführende Prozesse. 2. bereit (engl. ready ) Ein Prozess, der bereit ist zur Ausführung (im Gegensatz zu einem blockierten Pro- zess). Die Prozesse in diesem Zustand konkurrieren um die Prozessorzuteilung. 3. blockiert (auch schlafend“ oder wartend“) ” ” Ein Prozess, der auf ein Ereignis wartet, z.B. auf Dateneingabe von der Tastatur die Übertragung von Daten zwischen Festplatte und Hauptspeicher (aus Sicht des Prozessors relativ langwierig) eine Nachricht von einem anderen Prozess Ein blockierter Prozess konkurriert nicht mit anderen Prozessen um die Zuteilung des Prozessors. ausführend warte auf Ereignis Verdrängung CPU− Zuteilung blockiert bereit Ereignis tritt ein Natürlich gibt es nicht beliebige Übergänge zwischen den Zuständen: Prozesse und Threads 20 Ein Prozess blockiert sich selbst, indem er einen blockierenden Systemaufruf ausführt, z.B. Lesen von der Tastatur. Dies kann er nur im ausführenden Zustand, nicht im Zustand bereit. Es macht keinen Sinn, einem blockierten Prozess den Prozessor zu überlassen. Erweiterungen des Zustandsmodells Bei realen Betriebssystemen gibt es weitaus mehr Prozesszustände. Wir betrachten drei Erweiterungsmöglichkeiten: 1. Neue und terminierte Prozesse Ein Prozess ist im Zustand neu, wenn er schon erzeugt wurde, aber noch keine Prozessorzuteilung hatte. Der Zustand gleicht dem Zustand bereit, al- lerdings haben neue Prozesse in der Prozesstabelle noch keinen abgespei- cherten Maschinenzustand (PCB). Ein Prozess ist im Zustand terminiert, wenn die Bearbeitung schon beendet wurde, aber der Prozessdeskriptor noch für irgendwelche Zwecke aufbewahrt wird. Beispiel: Bei UNIX-Systemen steht ein neuer Prozess in einem Kindschafts- verhältnis zu seinem Erzeugerprozess. Terminiert ein Prozess, hat sein El- ternprozess die Möglichkeit, mit einem waitpid-Systemaufruf dessen Termi- nierungsstatus zu erfragen. Bis er dies tut, wird der Kind-Prozessdeskriptor (als sogenannter zombie“) in der Prozesstabelle aufbewahrt. ” neu terminiert erstmalige CPU−Zuteilung beenden ausführend warte auf Ereignis Verdrängung CPU− Zuteilung blockiert bereit Ereignis tritt ein Prozesse und Threads 21 2. Ausgelagerte Prozesse Bei Hauptspeichermangel können die meisten Betriebssysteme Prozesse temporär vom Hauptspeicher auf eine Platte ( swap“-Bereich) auslagern. Durch die Unter- ” scheidung eingelagert“/“ausgelagert“ bei diversen Zuständen vergrößert sich die ” Zustandsmenge. Beispiel: ausführend warte auf Ereignis Verdrängung CPU− Zuteilung blockiert bereit Ereignis tritt ein auslagern einlagern blockiert bereit ausgelagert ausgelagert Ereignis tritt ein Auslagerungskandidaten sind in diesem Modell nur blockierte Prozesse. Man be- achte, dass es nicht unbedingt sinnvoll ist, ausgelagerte Prozesse in den Haupt- speicher zurückzukopieren, solange sie blockiert sind. 3. Verschiedene Wartezustände Betriebssysteme unterscheiden oft blockierte Prozesse nach der Art des erwarteten Ereignisses. Dies ermöglicht bei Eintritt eines Ereignisses eine effizientere Suche nach dem (den) aufzuweckenden Prozess(en). Beispiel: Prozesse und Threads 22 ausführend wartet auf Terminal− Eingabe wartet auf Terminal− Ausgabe blockieren wartet auf. bereit wartet Plattenauf E/A Netzwerk E/A Ereignis tritt ein... wartet auf Seitenfehler− behandlung 3.3 Synchrone und asynchrone Ereignisse und Unterbrechungen Ein ausführender Prozess führt normalerweise die Instruktionen des zugrundeliegenden Anwendungsprogramms aus. Von Hardware oder Software ausgelöste Ereignisse un- terschiedlicher Art führen regelmäßig zur Unterbrechung der normalen Ausführung. Die Prozessorkontrolle wird an das Betriebssystem übergeben. Im Betriebssystem reagiert eine für die Ereignisklasse spezifische Ereignisbehandlungsfunktion auf das Ereignis, bevor die reguläre Programmausführung wieder fortgesetzt werden kann. Ein Ereignis heißt synchron, wenn es durch eine bestimmte Operation des ausführen- den Programms unmittelbar ausgelöst wird, z.B. führt ein Division durch Null gewisser- maßen zu einem Ausnahmezustand“ des Prozessors, der im Betriebssystem behandelt ” wird. Synchrone Ereignisse sind meist reproduzierbar, bei wiederholter Ausführung des Programms tritt an der gleichen Stelle das Ereignis immer wieder auf. Ein Ereignis heißt asynchron, wenn der Zeitpunkt des Auftretens keinen Bezug zu den vom ausführenden Prozess gerade bearbeiteten Befehlen hat. Aus Sicht des ausführen- den Prozesses sind asynchrone Ereignisse unvorhersehbar. Wir unterscheiden folgende Ereignisklassen: Hardware-Unterbrechungen (Interrupts) Ein Interrupt wird asynchron von der Hardware erzeugt, oft im Zusammenhang mit Ein-/Ausgabeoperationen. (Das Konzept wird in 9.3, S. 125 genauer erläutert.) Hardwarefehler (asynchron) Durch Spannungsschwankungen oder defekte Hardware können jederzeit Ausnah- mezustände auftreten. Prozesse und Threads 23 Systemaufrufe (synchron) Systemaufrufe wurden schon behandelt. Die zur Implementierung verwendeten Traps gleichen in vieler Hinsicht den anderen aufgeführten Ereignissen. Aus Sicht des Programmierers sind Traps natürlich keine unerwarteten“ Ereignisse, die Kon- ” trolle wird gewollt an das Betriebssystem übergeben. Programmfehler-Ereignisse (synchron) Bestimmte Programmfehler verursachen Prozessor-Ausnahmezustände, z.B. Fließkommaüberlauf, Division durch Null oder unerlaubte Hauptspeicherzugriffe (oft durch Dereferenzierung fehlerhaft initialisierter Pointer-Variablen). Im Gegensatz zu Systemaufruf-Traps ist die Unterbrechung aus Sicht des Program- mierers nicht beabsichtigt. Oft besteht die Ereignisbehandlung darin, den auslösen- den Prozess mit einer Fehlermeldung zu terminieren. Viele Systeme erlauben es dem Anwendungsprogramm, die Ereignisbehandlung für solche Fehlerzustände selbst zu bestimmen. Dazu muss das Anwendungs- programm eine Fehlerbehandlungsfunktion beim Systemkern registrieren. Die Be- handlung innerhalb des Betriebssystems besteht dann in der Aktivierung der regi- strierten Anwenderfunktion4. Seitenfehler Im Kapitel 6, S. 72 wird erläutert, wie der von einem Prozess benutzte Haupt- speicherbereich in Blöcke fester Größe, Speicherseiten, eingeteilt werden kann. Diese werden bei Hauptspeicherengpässen temporär auf den Swap-Bereich einer Platte ausgelagert. Greift nun ein Prozess auf eine seiner ausgelagerten Seiten zu, muss er unterbro- chen werden, bis diese wieder in den Hauptspeicher kopiert ist. Im Unterschied zu den oben diskutierten Programmfehlern muss der fehlgeschlagene Speicherzugriff dann wiederholt werden. Für den Prozess bleibt die Ereignisbehandlung unsichtbar. Obwohl die Programmausführung die Ausnahmesituation unmittelbar herbeiführt, ist diese jedoch nicht programmiert und nicht reproduzierbar wie etwa Speicherzugriffsschutz-Verletzungen. Seitenfehler haben also eher asynchronen als synchronen Charakter. Software-Interrupts Im Gegensatz zu Hardware-Interrupts werden Software-Interrupts programmiert“. ” (vgl. 9.3, S. 125) 4 Der Mechanismus könnte folgendermaßen aussehen: Das Betriebssystem gibt zwar die Kontrolle an das Anwendungsprogramm zurück, aber nicht an die Unterbrechungsstelle. Der Programmzähler wird vom Be- triebssystem so umgebogen“, dass zunächst die Fehlerbehandlungsfunktion ausgeführt wird. Diese über- ” gibt die Kontrolle wieder zurück an den Systemkern, der den Programmzähler dann ggf. auf den alten Wert zurücksetzt und erneut in den Anwendungsmodus wechselt. Man spricht dann von Trampolin-Code“. ” Prozesse und Threads 24 Ereignisbehandlung und Prozess-Zustandsübergänge Allen Ereignisklassen gemeinsam ist, dass die Kontrolle über den Prozessor an das Be- triebssystem übergeben wird, denn schliesslich sind die von der Hardware aktivierten Ereignis-Behandlungsroutinen Bestandteile des Betriebssystems. Dadurch erhält das Betriebssystem die Möglichkeit, im Rahmen der Ereignisbehandlung die Prozesszustände zu ändern und Kontextwechsel durchzuführen. Betrachten wir typische Beispiele: Ein Prozess versucht einen unerlaubten Hauptspeicher-Zugriff, der die Hardware in einen Ausnahmezustand versetzt. Die Behandlungsroutine kann z.B. den Prozess terminieren und einem anderen Prozess den Prozessor zuteilen. Ein Netzwerk-Controller signalisiert durch einen Interrupt den Empfang von Daten aus dem Netzwerk. Die Behandlungsroutine wird zunächst die Daten aus dem Con- troller in den Hauptspeicher kopieren. Dann wird ggf. ein blockierter Prozess, der auf diese Daten gewartet hat, aufgeweckt“, d.h. in den Zustand bereit“ versetzt. ” ” Gegebenenfalls wird dem aufgeweckten Prozess sogar der Prozessor zugeteilt, weil er eine höhere Priorität hat als der gerade ausführende Prozess. Jeder Rechner hat einen Taktgeber ( clock“), der in regelmäßigen Intervallen In- ” terrupts erzeugt. Die Behandlungsroutine wird die Systemzeit aktualisieren und prüfen, ob der ausführende Prozess sein Quantum verbraucht hat. In diesem Fall kann eine Verdrängung veranlasst werden. (Mehr dazu in 7, S. 100) 3.4 Operationen für Prozesse Prozess erzeugen Bei der Erzeugung wird entweder ein neues Programm in den Hauptspeicher ge- laden oder der erzeugende Prozess kopiert (vgl. UNIX-fork). Das Betriebssystem muss eine eindeutige Prozessidentifikation vergeben und den Prozesstabellenein- trag erzeugen und initialisieren. Die vom Programm unabhängigen Prozessattribute werden dabei entweder explizit angegeben oder vom Erzeuger-Prozess übernommen, also vererbt“. ” Der neue Prozess ist entweder ein Subprozess des Erzeugerprozesses oder ein unabhängiger Prozess ( detached“). ” Prozess beenden Dabei wird der Hauptspeicher und ggf. andere Ressourcen, die der Prozess beleg- te, freigegeben, die offenen Dateien geschlossen und der Prozessdeskriptor aus der Prozesstabelle entfernt. Gegebenenfalls wird der Elternprozess von der Termi- nierung verständigt. Priorität ändern Prozesse und Threads 25 Die Priorität kann durch explizite Systemoperationen beinflusst werden. Daneben werden Prioritäten auch dynamisch an die Interaktionshäufigkeit des Prozesses angepasst (vgl. 7, S. 100). Zustand ändern: verdrängen, ausführen, blockieren, aufwecken Die Zustandsänderungen werden, wie oben erläutert, im Rahmen von Systemauf- rufen oder bei Unterbrechungen vom Betriebssystem durchgeführt. Eine mögliche Implementierung der Prozesszustände: Das Betriebssystem verket- tet die Prozessdeskriptoren aller Prozesse, die sich in einem Zustand Z befinden zu einer Liste. Jedem möglichen Prozesszustand entspricht also eine Liste. Ein Zu- standsübergang führt dazu, dass der betroffene Prozessdeskriptor in eine andere Liste eingefügt wird. Beispiel: Der ausführende Prozess liest Daten von der Tastatur. Er wird blockiert und ein anderer Prozess bekommt den Prozessor. Prozesse und Threads 26 Zustände Prozesse (Listen) ausführend A bereit B warten auf Tastatureingabe warten auf Platten−E/A warten auf... ausführender Prozess liest von Tastatur erster bereiter Prozess erhält Prozessor Zustandsänderung ausführend B bereit warten auf A Tastatureingabe warten auf Platten−E/A warten auf... Prozesse und Threads 27 3.5 Kontextwechsel Das Betriebssystem teilt den Prozessor nacheinander verschiedenen Prozessen zu. Nehmen wir z.B. an, der ausführende Prozesses P1 blockiert, weil er auf Eingabeda- ten vom Netzwerk wartet. Um unnötigen Leerlauf im System zu vermeiden, wird der Prozessor während dieser Wartezeit zur Ausführung eines anderen Prozesses P2 ver- wendet. Wenn P1 später weitergeführt werden soll, muss sein Ausführungszustand zum Unterbrechungszeitpunkt bekannt sein. Diesen Zustand bezeichnet man auch als Pro- zesskontext, den Wechsel von P1 nach P2 als Kontextwechsel. Für die betroffenen Prozesse ist der Kontextwechsel transparent. Ein normales Anwen- dungsprogramm enthält keinerlei Programmcode zur geordneten Übergabe des Prozes- sors an einen anderen Prozess, sondern definiert i.d.R. eine unterbrechungsfrei aus- zuführende Folge von Maschinenbefehlen. Es ist daher Sache des Betriebssystems, den Kontext des unterbrochenen Prozesses zum Unterbrechungszeitpunkt abzuspeichern und bei der späteren Weiterführung so wie- derherzustellen, dass aus Programmsicht die Unterbrechung nicht registriert wird. Was macht nun den Zustand eines Prozesses aus? Aus Programmierersicht sind bei einer Momentaufnahme zur Ausführungszeit folgende Fragen relevant: An welcher Stelle im Programmcode befindet sich die Ausführung? Wie ist die aktuelle Unterprogrammaufruffolge? Welche Werte haben die lokalen und globalen Variablen? Die aktuellen Unterprogrammaktivierungen, sowie die Werte von Parametern und loka- len Hilfsvariablen spiegeln sich im Laufzeitstack des Programms wieder, also in einem zum Prozess gehörenden Hauptspeicherbereich. Auch die anderen Daten stehen im Programmspeicher des Prozesses. Die zum Prozess gehörigen Hauptspeicherbereiche (Programmspeicher mit Code und Daten, sowie Prozessdeskriptor) werden während der Unterbrechungszeit durch andere Prozesse nicht überschrieben. Ein kleiner, aber entscheidender Teil des Prozesszustands ist allerdings nicht im Haupt- speicher, sondern im Prozessor selbst zu finden: die prozessorinternen Speicherplätze, nämlich Mehrzweckregister, Programmzähler und Statusregister. Der Programmzähler enthält die Adresse des nächsten auszuführenden Maschinenbefehls. In den Mehrzweck- registern stehen einige vom Programm benötigte Daten und das Statusregister enthält maschinenspezifische Flags. Das Betriebssystem muss beim Kontextwechsel all diese Register retten, d.h. in den Hauptspeicher kopieren. Platz dafür ist im Prozessdeskriptor vorgesehen. Der zur Ausführung ausgewählte Prozess bekommt den Prozessor im restaurierten Zustand, d.h. die vorher geretteten Registerwerte werden aus dem Prozessdeskriptor wieder in den Prozessor geladen. Neben der CPU gibt es ggf. (maschinenabhängig) weitere Hardwarebausteine mit inter- nen Speicherplätzen, die beim Kontextwechsel genauso behandelt werden müssen, z.B. ein separater Gleitkommaprozessor in einem PC oder die MMU. Prozesse und Threads 28 Bei manchen Rechnern müssen die Register mit separaten Maschinenbefehlen einzeln gerettet bzw. restauriert werden, bei anderen reicht ein einziger Maschinenbefehl für die Übertragung aller Register. Der Maschinencode für den Kontextwechsel ist Bestandteil des Betriebssystems und kann beispielsweise im Rahmen der Bearbeitung von Systemaufrufen aktiviert werden. Im obigen Beispiel heißt das: P1 führt eine Leseoperation aus. Durch den Systemauf- ruf wird die Kontrolle an das Betriebssystem übergeben. Der aktivierte Systemcode wird nach Initiierung der Leseoperation schließlich auch den Kontextwechsel durchführen: Retten des Kontextes von P1 Restaurieren des Kontextes von P2 Umschalten des Prozessors in den nichtprivilegierten Modus Übergabe der Kontrolle an P2 3.6 Threads 3.6.1 Nebenläufigkeit in Programmen In vielen Situationen ist es sinnvoll, innerhalb eines Programms parallel ausführbare Be- arbeitungsschritte zu spezifizieren. Einerseits ergeben sich dadurch manchmal Effizienz- vorteile, andererseits kann eine derartige Zerlegung softwaretechnisch geboten sein. Beispiel 1: Server im Netzwerk, die gleichzeitig mit mehreren Client kommunizieren (Parallelserver -Konzept, concurrent server“). ” Beispiel 2: Ausnutzung der Prozessoren eines Multiprozessorsystems durch eine re- chenintensive Anwendung. Definition Ein Thread ( thread of control“, Kontrollfaden“) ist eine sequentiell abzuarbeitende Be- ” ” fehlsfolge innerhalb eines Programms. Definition Man spricht von Multithreading“, wenn innerhalb eines Programms zwei oder mehr ” nebenläufige Befehlssequenzen spezifiziert werden. Wir nennen ein solches Programm nachfolgend nebenläufig“. ” Die Programmierung mit Threads erfolgt entweder durch entsprechende Konzepte der Programmiersprache (z.B. Java, ADA, Chill) oder Prozesse und Threads 29 durch Verwendung einer Thread-Bibliothek (z.B. POSIX-Thread-Bibliothek für C/C++) 3.6.2 Implementierung von Threads Betrachten wir drei Programme, davon zwei nebenläufige: Programm Programm Programm Thread Bei gleichzeitiger Ausführung der drei Programme konkurrieren 6 Threads um den Pro- zessor. Mehrere Konzepte der Prozessorzuteilung sind denkbar. 1. Jeder Thread eines Programms wird auf einen eigenen Prozess abgebildet. Mit dem wohlbekannten Multitasking-Konzept wird die Nebenläufigkeit der Threads auf Betriebssystemebene realisiert. 2. Eine Thread-Bibliothek auf Benutzerebene, die alle notwendigen Funktionen zur Thread-Verwaltung enthält, insbesondere einen Scheduler. 3. Ein spezifisches Betriebssystemkonzept zur Unterstützung von Threads: leichtge- wichtige Prozesse (LGP) Prozesse und Threads 30 3.6.3 Thread-Implementierung durch Prozesse Programm Programm Programm Betriebssystem sieht 6 konkurrierende Prozesse Prozessor Das herkömmliche Prozesskonzept ist für die nebenläufige Bearbeitung verschiede- ner Programme entwickelt worden. Damit verschiedene Benutzer eines Mehrbenut- zersystems unabhängig voneinander arbeiten können, sind Prozesse durch separate Adressräume, separate Dateideskriptoren und strikte Zugriffschutzkontrollen gegenein- ander abgeschottet. Daraus folgt: – Das Erzeugen eines Prozesses ist aufwändig und benötigt ggf. viel Speicherplatz – Der Kontextwechsel ist aufwändig – Interprozesskommunikation erfolgt über das Betriebssystem und ist dadurch ver- gleichsweise langsam Das Prozesskonzept ist in diesem Sinne ein schwergewichtiges Konzept. Für zwei Threads desselben Programms ist eine gegenseitige Abschottung weder not- wendig noch sinnvoll. Gemeinsam benutzte Datenstrukturen und Dateien dienen einer ef- fizienten Kooperation. Ein Thread benötigt im wesentlichen einen eigenen Laufzeitstack, damit er unabhängig von den anderen Threads Funktionsaufrufe durchführen kann. Threads durch Prozesse zu implementieren, heißt mit Kanonen auf Spatzen zu schies- ” sen“. Es ist ineffizient im Hinblick auf Hauptspeichernutzung (eigene Adressräume) und Geschwindigkeit (Erzeugen, Kontextwechsel, Kommunikation). Prozesse und Threads 31 3.6.4 Thread-Bibliotheken auf Benutzerebene ( Anwender-Threads“, ” user threads“) ” Das Betriebssystem muss die parallelen Aktivitäten eines Programm nicht notwendi- gerweise sehen. Das Programm kann die Verwaltung seiner Threads auch ohne Un- terstützung des Betriebssystems durchführen. Die dazu benötigten Funktionen lassen sich in Form einer Bibliothek implementieren. Bestandteile einer Thread-Bibliothek: Operationen zum Erzeugen und Zerstören von Threads Scheduling-Mechanismus (Blockieren, Aktivieren, Prioritäten) Synchronisationsmechanismen Kommunikationsmechanismen Programm Programm Programm Anwender−Threads Betriebssystem sieht Threads nicht Prozessor Diese besonders leichtgewichtige“ Lösung hat Vorzüge: ” Die wesentlichen Thread-Operationen (erzeugen, vernichten, Kontextwechsel, Kommunikation, Synchronisation) erfolgen ohne Zutun des Betriebssystems. Damit sind sie effizienter implementierbar, denn schliesslich ist die Nutzung des System- kerns immer mit einem gewissen Aufwand verbunden. Anwender-Threads belegen keine Betriebssystemressourcen (wie z.B. Prozessde- skriptoren). Die Anzahl der Anwender-Threads ist damit kaum nach oben be- schränkt. Prozesse und Threads 32 Dem stehen aber auch Nachteile gegenüber: Der Betriebssystemkern sieht nur einen einzigen Prozess, von der Existenz ausführungs- bereiter Threads weiß das BS nichts: Wenn ein Thread im Betriebssystem blockiert (E/A, Seitenfehler), ist der Prozess als Ganzes blockiert inklusive der ausführungsbereiten Threads (von denen das Betriebssystem aber nichts weiss), Echte Parallelausführung ist in Multiprozessorsystemen nicht möglich, da die Pro- zessorzuteilung beim Betriebssystem liegt. 3.6.5 Leichtgewichtige Prozesse Moderne Betriebssysteme tragen dem steigenden Bedarf nach Thread-Unterstützung durch die Einführung eines neuen Objekttyps Rechnung, den wir als leichtgewichtigen ” Prozess“ (LGP – engl. lightweight process“) bezeichnen wollen5. ” Dahinter steckt die Trennung von Programm-bezogener Information, z.B. – Zugriffsrechte – Adressraum – Dateideskriptoren und Thread-spezifischen Daten, z.B. – Laufzeitstack – Zustand – Priorität – Maschinenstatus (Programmzähler, Registerinhalte usw.) 5 In der Literatur oft auch als Kern-Thread“ (engl. kernel thread“) oder einfach nur als Thread“ bezeich- ” ” ” net Prozesse und Threads 33 Programm Programm Programm Prozess LGP Betriebssystem mit leichtgewichtigen Prozessen Prozessor In einem solchen Betriebssystem (z.B. Sun Solaris oder Windows NT) ist ein Prozess kein aktives“ Objekt mehr, sondern eine eher statische Umgebung, die den Rahmen für ” die Ausführung der in ihr ablaufenden Threads bildet. Nicht mehr Prozesse sind es, die um den Prozessor konkurrieren und deren Zustände verwaltet werden, sondern LGPs. Das Betriebssystem benötigt neben der Prozesstabelle pro Prozess eine LGP-Liste mit der benötigten LGP-Verwaltungsinformation. Synchronisation nebenläufiger Prozesse 34 4 Synchronisation nebenläufiger Prozesse 4.1 Nichtdeterminismus durch Nebenläufigkeit Sobald nebenläufige Prozesse (oder Threads) miteinander kooperieren oder um exklusi- ven Zugriff auf Daten oder Geräte konkurrieren, benötigt man Synchronisationsmecha- nismen. Dabei spielt es zunächst keine Rolle, ob die gegenseitige Abstimmung durch Zu- griff auf gemeinsam benutzte Hauptspeicherbereiche, Dateien, Geräte oder durch Nach- richtenübertragung im Netzwerk notwendig wird. Die Problematik gemeinsamen Datenzugriffs verdeutlicht ein Beispiel: Bei zwei nebenläufigen Prozessen lässt sich der relative Bearbeitungsfortschritt nicht vorhersagen. Betrachten wir den nebenläufigen Zugriff auf gemeinsame Variablen: concurrency-example.cc #include #include "concurrent.h" int a=1, b=2; f(){ a=a+b; a=2*a; } g(){ a=5; } main(){ concurrent(f,g); // nebenlaeufiger Aufruf cout tturn=1 Symmetrisch. Aufgabe: Zeigen Sie, dass der Algorithmus auch verklemmungsfrei ist. Synchronisation nebenläufiger Prozesse 46 4.5 Abschalten von Unterbrechungen Gegenseitiger Ausschluss ließe sich auch dadurch implementieren, dass im kritischen Abschnitt die Hardware-Interrupts einfach abgeschaltet“ werden. Der ausführende Pro- ” zess ist dann nicht mehr unterbrechbar und kann ohne Wettbewerb auf gemeinsame Daten zugreifen. Innerhalb des Betriebssystems wird dieser Mechanismus auch teilweise genutzt (näher- es siehe 9.3, S. 125). In einem Multitasking-System kann man eine so mächtige Opera- tion aber nicht dem Anwender zugänglich machen. Zu groß ist die Gefahr, dass durch Programmfehler ein Prozess im kritischen Abschnitt hängenbleibt. Bei abgeschalteten Interrupts führt dies zum Stillstand des gesamten Systems. 4.6 Aktives Warten auf Maschinenebene Für aktives Warten gibt es auf der Maschinenebene meist eine atomare Instruktion (SWAP oder TEST-AND-SET ), die den Inhalt eines Registers in atomarer Weise prüft und modifiziert. Nehmen wir an, die Instruktion heißt SWAP und tauscht die Inhalte zweier Register aus. Wir verwenden ein gemeinsam benutztes Register als Sperre: Ist der darin enthaltene Wert Null, ist der kritische Abschnitt frei und kann betreten werden. Dabei muss die Sperre gesetzt werden. Die Prüfung und das Setzen der Sperre kann in einer einzigen SWAP-Operation erfolgen: int warte1=0; int warte2=0;... thread1(){ while (TRUE) {.. unkritische Aktivität. warte1=1; while (warte1) swap(warte1, sperre);.. kritischer Abschnitt. sperre=0; } } thread2(){ while (TRUE) {. Synchronisation nebenläufiger Prozesse 47. unkritische Aktivität. warte2=1; while (warte2) swap(warte2, sperre);.. kritischer Abschnitt. sperre=0; } } Falls ein Rechner keine solche Maschineninstruktion besitzt, kann das Betriebssystem durch Abschalten der Interrupts zwischen Prüfen und Setzen des Sperr-Registers eine äquivalente Operation implementieren. 4.7 Spinlocks Wir definieren ein Objekttyp Spinlock , der als abstrakte Schnittstelle zu einem Synchro- nisationsmechanismus dient, der auf aktivem Warten basiert. Spinlocks lassen sich (z.B. mit dem Peterson-Algorithmus) auch auf der Anwenderebene implementieren, normaler- weise stellt aber ein Betriebssystem die Operationen zur Verfügung und implementiert sie mittels der oben beschriebenen SWAP-Operation. class spinlock { public: spinlock(void); lock(void); unlock(void); }; Der Konstruktor initialisiert die Sperre mit frei“. ” lock wartet aktiv auf das Freiwerden der Sperre. Ist die Sperre freigegeben, wird sie gesetzt. Man sagt auch, der aufrufende Prozess hält die Sperre“. Prüfung und ” Setzen erfolgt in Form einer atomaren Operation. unlock gibt die Sperre frei. Es liegt in der Verantwortung des Programmierers, dass nur der Prozess, der die Sperre hält, unlock aufrufen darf. Wenn mehrere Prozesse an der selben Sperre warten, bestimmt der Zufall, welcher die Sperre nach der Freigabe zuerst erhält. Gegenseitiger Ausschluss mit Spinlocks spinlock l; while (TRUE) { Synchronisation nebenläufiger Prozesse 48.. unkritische Aktivität. l.lock(); // ggf. Warten.. kritischer Abschnitt. l.unlock(); } 4.8 Blockieren von Prozessen, Warteschlangen Blockieren ist aus Prozess-Sicht eine Meta-Operation: der Prozess manipuliert dabei nicht irgenwelche Datenstrukturen, sondern ist selbst in der Rolle eines manipulierten Objekts. Er wird schlafen gelegt, später wieder aufgeweckt. Die Implementierungen von Blockieroperationen müssen wir also nicht im Anwenderprogramm, sondern auf Betriebs- systemebene suchen. Blockierende Operation gibt es in vielen Varianten. Wir diskutieren Semaphore (Zählende Semaphore) Mutex (Binärsemaphore) Ereignisvariablen Nachrichtenübertragung Gemeinsam ist allen Blockieroperationen, dass jeweils eine Warteschlange zur Imple- mentierung benötigt wird: Beim Blockieren wird der Prozess, der die Blockieroperation aufruft, in die Warte- schlange eingereiht. Beim Aufwecken wird ein Prozess aus der Warteschlange wieder herausgenom- men. Aufwecken kann sich ein Prozess nicht selbst, ein anderer muss die Weck- operation aufrufen! Wenn ein Prozess mit einer Weckoperationen genau einen von mehreren warten- den Prozessen aufweckt, stellt sich die Frage: Welchen? Zwei Strategien sind üblich: – Der Prozess wird geweckt, der am längsten wartet (FIFO = “first in“ – first out“) ” – Das Betriebssystem bestimmt anhand von Prioritätszahlen, dass der Prozess mit der höchsten Priorität aus der Warteschlange genommen wird. In manchen Anwendungen ist es dagegen sinnvoll, alle wartenden Prozesse auf- zuwecken. Synchronisation nebenläufiger Prozesse 49 4.9 Semaphore (Zählende Semaphore) Ein Semaphor wird mit einer Warteschlange und einem Zähler implementiert. Die Schnitt- stelle: class semaphor { public: semaphor(int anfangswert); down(void); up(void); }; Beim Konstruktor-Aufruf wird eine neue, leere Warteschlange eingerichtet und der Zähler mit dem angegebenen Wert initialisiert down – dekrementiert den Zähler, falls dieser positiv ist, oder – blockiert den Aufrufer, falls der Zähler gleich Null ist. up – weckt einen Prozess auf, falls die Warteschlange nicht leer ist, oder – inkrementiert den Zähler Mit Semaphoren kann man recht einfach für die Synchronisation von Prozessen sorgen, die sich um exklusiven Zugriff auf eine von N verfügbaren Ressourcen bemühen. Beispiel: In einem System gibt es 3 Drucker. Um nebenläufige Zugriffe zu synchroni- sieren, wird ein Semaphor mit dem Zählerwert 3 initialisiert. Jeder Druckauftrag führt zu Beginn eine down-Operation durch. Die ersten 3 Aufträge müssen also nicht warten, da nur der Zähler dekrementiert wird. Weitere Aufträge werden blockiert. Nach Beendigung einer Druckernutzung wird up aufgerufen. Ein Drucker ist nun wie- der verfügbar. Ist die Warteschlange leer, wird der Semaphorwert inkrementiert. Warten Prozesse, wird dagegen einer aufgeweckt. Der Zähler gibt zu jedem Zeitpunkt die Anzahl freier Drucker an. class druckdienst { semaphor drucker(DRUCKERANZAHL);... public: void drucke(string datei); }; void druckdienst::drucke(string datei){ drucker.down(); // ggf. warten, bis Drucker frei Synchronisation nebenläufiger Prozesse 50... // Drucker exklusiv nutzen drucker.up(); // freigeben } 4.10 Mutex (Binärsemaphore) Mit Semaphoren kann man natürlich auch für gegenseitigen Ausschluss sorgen. Gemein- same Daten können als eine nur einmal vorhanden Ressource betrachtet werden. Somit lässt sich gegenseitiger Ausschluss als Spezialfall des oben verwendeten Musters für N=1 betrachten. Der Spezialfall wird allerdings so häufig benötigt, dass wir einen neuen Konstruktor ohne Zählerinitialisierung einführen. Einen Semaphor, der nur bis 1 zählen kann, nennt man binären Semaphor oder Mutex (von mutual exclusion“). ” class mutex { public: mutex(void); down(void); up(void); }; Da up und down für Semaphor- und Mutexobjekte identisch sind, bietet sich natürlich auch die Spezialisierung durch Vererbung an: class mutex : public semaphor { public: mutex(void); }; mutex::mutex() :semaphor(1) // Mutex = Semaphor mit Anfangswert 1 {} Gegenseitiger Ausschluss mit einem Mutex mutex m; while (TRUE) {.. unkritische Aktivität. m.down(); // ggf. Warten.. kritischer Abschnitt. m.up(); } Synchronisation nebenläufiger Prozesse 51 Dies gleicht auf der Quelltextebene exakt der Spinlock-Lösung(4.7, S. 47). Man beachte aber, dass Spinlocks durch aktives Warten realisiert sind. Beispiel: Exklusiver Druckerzugriff Wir kommen noch einmal auf das Druckerbeispiel zurück. Nach dem Warten auf einen Drucker drucker.down(); muss noch festgestellt werden, welcher Drucker frei ist. Ein freier Drucker muss reserviert werden, dann wird gedruckt. Nehmen wir an zum Drucken gibt es eine Systemmethode, system.print(int druckernummer, datei d); die sich nicht um die Synchronisation kümmert, sondern voraussetzt, dass der Drucker mit der angegebenen Nummer exklusiv genutzt wird. Betrachten wir folgende Implementierung: class druckdienst { semaphor drucker(DRUCKERANZAHL); boolean istfrei[DRUCKERANZAHL]; public: druckdienst(void); void drucke(string datei); }; druckdienst::druckdienst(){ // alle Drucker als "frei" markieren for(int i=1; i