Betriebssysteme, HIT 3. Jahrgang Teil 1: Multithreading (PDF)

Betriebssysteme, HIT 3. Jahrgang Teil 1: Multithreading Prof. Guido Bachmayr Inhalt Wh.: Prozesse (=Single-Thread Prozesse)......................................................................

Betriebssysteme, HIT 3. Jahrgang Teil 1: Multithreading Prof. Guido Bachmayr Inhalt Wh.: Prozesse (=Single-Thread Prozesse)................................................................................. 2 Prozesserzeugung................................................................................................................... 3 Prozessbeendigung................................................................................................................ 3 Zustände eines Prozesses (bzw. dessen einziger Thread)...................................................... 3 Scheduler................................................................................................................................ 4 Prozesstabelle / Prozesskontrollblock.................................................................................... 4 Mehr als 1 Thread (Multithreading)........................................................................................... 5 Threadzustände (identisch zu Singlethread-Prozesszuständen)........................................... 6 Threadwechsel....................................................................................................................... 7 Beispiel: Textverarbeitung..................................................................................................... 7 Beispiel: Computerspiel.......................................................................................................... 8 Popup Thread......................................................................................................................... 8 Unterscheidung User- und Kernel Threads................................................................................ 9 Hybride Implementierung.................................................................................................... 11 Detail bei Blockierenden Aufrufen in User-Threads:........................................................... 12 SYT3-BS_01_Multithreading.docx 2 (12) Wh.: Prozesse (=Single-Thread Prozesse) Prozess: Instanz eines Programmes wird gerade ausgeführt (d.h. liegt im Hauptspeicher) beinhaltet 1 gerade ausgeführten Code-Strang (Multi-Threading: mehrere) inklusive aller (jeweils) aktuellen Variablen Ein Programm kann gleichzeitig mehrmals ausgeführt werden. Z.B.: Texteditor, Taschenrechner, Word, … sind jeweils 2-3 Mal geöffnet. 2 (oder mehrere) Prozesse, die auf demselben Programm beruhen sind 2 (oder mehrere) Prozesse und stellen überhaupt keinen Sonderfall dar. Jeder Prozess arbeitet für sich allein, als hätte er seinen eigenen, einzigen(!) CPU-Kern Realität: 1 CPU (-Kern) schaltet zwischen mehreren Prozessen hin und her (es gibt noch weitere CPU-Kerne… hier egal) Zu jedem Zeitpunkt wird im CPU-Kern nur 1 Prozess abgearbeitet 1 (realer) CPU-Kern verfügt nur über 1 „Befehlszähler“ = Register, in dem die Adresse des nächsten auszuführenden Befehls gespeichert ist (bzw. mitgeführt wird) Der Befehlszähler wird in jedem Prozess-Speicherbereich mitgeführt Beim Prozesswechsel wir der reale Befehlszähler (der CPU) des alten Prozesses im Prozess-Speicher gesichert und vom neuen Prozess geladen SYT3-BS_01_Multithreading.docx 3 (12) Prozesserzeugung 4 Ursachen: 1. Systemstart 2. Systemaufruf durch einen anderen Prozess (→ Kindprozess) 3. Systemaufruf durch eine Benutzeranfrage 4. Initialisierung und Abarbeitung einer Stapelverarbeitung Technisch wird ein Prozess immer durch einen anderen Prozess (mittels Systemaufruf) erzeugt (Sonderfall: Systemstart): a) Implementierung „entscheidet“ Prozesserzeugung b) User startet ein Programm (via Shell) Daemons: Prozesse, die im Hintergrund laufen und im Hintergrund „warten“ für: eMails, Druckaufträge, Antivirus… (>>10) Prozessbeendigung 4 Gründe: 1. „Programmende“ erreicht (freiwillig – selbstinitiiert) Aufgabe erfolgreich erledigt 2. Ende aufgrund eines Fehlers (freiwillig – selbstinitiiert) Exception geworfen – Implementierung „entscheidet“ sich für Abbruch 3. Schwerwiegender Fehler (unfreiwillig – fremdinitiiert) vom Betriebssystem beendet (Speicherschutzverletzung, Division durch 0, …) 4. Beendung durch einen anderen Prozess (unfreiwillig – fremdinitiiert): „kill“ Spezielle Rechte nötig um einen anderen Prozess beenden zu können. Zustände eines Prozesses (bzw. dessen einziger Thread) SYT3-BS_01_Multithreading.docx 4 (12) Ein aktiver (rechnender) Prozess (wird auf der CPU gerade ausgeführt) kann aus 2 Gründen inaktiv werden: Blockiert: d.h. er wartet auf ein best. Ereignis (z.B. Usereingabe) Timeout: Wechsel durch Scheduler (CPU – auf einen anderen Prozess) Ein Prozess der selbst „wartet“ (= blockiert), soll natürlich schnell abgelöst werden! Scheduler Der Scheduler wechselt (entscheidet) die CPU-Verarbeitung zwischen den vorhandenen Prozessen Prozesstabelle / Prozesskontrollblock Verwaltung aller Prozesse Liste mit Datenstrukturen – 1 Eintrag je Prozess = Prozesskontrollblock: Befehlszähler Stackpointer Speicherbelegung (Arbeitsspeicher) Dateiverwaltung (offene Dateien) Zustand seiner geöffneten Dateien Elternprozess Priorität ID Startzeit, benutzte CPU-Zeit Zustand (rechnend, blockiert, rechenbereit) … SYT3-BS_01_Multithreading.docx 5 (12) Ein Prozesskontrollblock enthält (eben) alle Informationen über den Prozess, die nötig sind um zwischen den Zuständen: rechnend blockiert rechenbereit wechseln zu können (als wäre er nie unterbrochen worden) Mehr als 1 Thread (Multithreading) Thread = Ausführungsstrang (= ausgeführter Code) Prozesse können mehrere Threads enthalten: 1 Prozess kann: einen weiteren Prozess erzeugen aber auch einen weiteren Thread → innerhalb des eigenen Prozesses! Multithreading: mehrere Threads eines Prozesses werden „parallel“ ausgeführt: echt parallel: mehrere Threads eines Prozesses werden gleichzeitig auf mehreren Kernen ausgeführt „pseudo-parallel“ (kein offizieller Begriff): die Threads eines Prozesses treffen (zufällig) nicht gleichzeitig in den CPU-Kernen aufeinander – das ist aber egal. Insgesamt liegt dank Multithreading eine neue Situation vor: Es existieren viele 1000 Threads – das Betriebssystem muss mit den verhältnismäßig wenigen vorhandenen Kernen abarbeiten: „pseudo-gleichzeitig“→ der User soll das Gefühl haben, alles geht gleichzeitig → ständiges Durchwechseln aller Threads auf den CPU-Kernen. SYT3-BS_01_Multithreading.docx 6 (12) Thread-Tabelle: Datensatz für Threads Für jeden Thread muss verwaltet werden: Register-Belegung im Prozessor (beim Thread-Wechsel) auszuführender Code benötigte Variablen benötigte Daten, z.B. Datei-Handler All diese Daten müssen im Arbeitsspeicher gehalten werden (die Register-Belegung, wenn der Thread gerade nicht ausgeführt ist) Das Betriebssystem schützt die Zugriffe auf diese Daten zwischen den Threads eines Prozesses deutlich weniger als zwischen Prozessen. Threads (eines Prozesses): „wollen“ grundsätzlich Daten austauschen „wollen“ sich nicht gegenseitig angreifen (gleicher Programmierer bzw. Team) wenn sie sich durch Unachtsamkeit gegenseitig schaden, liegt das ebenfalls in der Verantwortung desselben Urhebers Threadzustände (identisch zu Singlethread-Prozesszuständen) Gedankenmodell: Prozesse konkurrieren (bis hin zu „Schad-Absichten“) Threads kooperieren: deshalb werden sie (innerhalb eines Prozesses) erzeugt SYT3-BS_01_Multithreading.docx 7 (12) Threadwechsel Der Datensatz der gesichert/wiederhergestellt werden muss, ist unverhältnismäßig kleiner als bei einem Prozesswechsel, da Threads prinzipiell auf dieselben Daten zugreifen! Vorteile für Verwendung von Threads: Das Anlegen eines Threads (innerhalb eines existierenden Prozesses) funktioniert 10 bis 100x schneller als das Anlegen eines neuen Prozesses o Muss nicht in Prozesstabellen, Scheduler berücksichtigt werden. Wechsel zwischen Threads viel schneller als Prozesswechsel (Speicherbereiche) Multicore-Prozessoren können für 1 Prozess genutzt werden Kommunikation zwischen Threads ist einfacher/schneller als zw. Prozessen Implementierung kann vereinfacht (geringere Komplexität) werden Überlegung: 1 Kern kann mehrere Threads (im Zeitmultiplex) abarbeiten 1 Thread kann nicht auf mehrere Kerne verteilt werden! Beispiel: Textverarbeitung 1 Word-Datei = 1 Prozess (1 Instanz von Word) Situation: Das vorliegende Dokument hat 100 Seiten, der User verändert etwas auf Seite 1 und „springt“ danach auf Seite 100 → es müssen alle Seiten davor gerendert werden, um Seite 100 rendern zu können. → das würde bzw. wird laggen. Zusatz-Thread #1: nach jeder Änderung (irgendwo) durch den User beginnt ein separater Thread alle nachfolgenden Seiten zu rendern – springt der User weiter nach hinten, hat dieser Thread so bereits einen Vorsprung. Zusatz-Thread #2: alle 2 Minuten sollte automatisch gespeichert werden Was ist einfacher (?): je ein Thread für: User-Interaktion, Rendering, (Auto-)Save alles in 1 Thread User-Interaktion, Rendering, (Auto-)Save = „alle Threads“: Benötigen Zugriff auf dieselben Daten „kommen“ von derselben Entwicklungsabteilung SYT3-BS_01_Multithreading.docx 8 (12) Beispiel: Computerspiel (z.B. Pac-Man, usw.) Mehrere Objekte bewegen sich auf/in einem Spielfeld (2D oder 3D). Jeder „Gegner“ bzw. jedes Objekt verfolgt seine eigene Strategie (zum Spieler hinbewegen, vom Spieler wegbewegen, runterfallen…) Jedes Objekt bekommt seinen eigenen Thread – der Code darin sieht nur vor: jeweils 1 Objekt zu bewegen → das ist ebenfalls einfacher, als eine monolithische Implementierung. Popup Thread Elegante Lösung für Server: Ein Prozess erhält eine Nachricht (die verarbeitet/beantwortet) werden soll Möglichkeiten: o Aktuellen Prozess unterbrechen und die eingehende Nachricht verarbeiten o Neuen Prozess starten (womöglich gemeinsame Daten mit „Ur-Prozess“ nötig) o Neuer Thread(!) für die Verarbeitung der eingehenden Nachricht Vorteil: Antwortzeit bei vielen gleichzeitigen Anfragen (und vielen freien CPU-Kernen) SYT3-BS_01_Multithreading.docx 9 (12) Unterscheidung User- und Kernel Threads User-Threads Kernel-Threads Ort: Thread-Tabelle liegt im: User-Adressraum Kern-Adressraum (OS-Bereich) → 1 Thread-Tabelle je Prozess → 1 Thread-Tabelle über alle Prozesse Das Betriebssystem: kennt/sieht keine einzelnen kennt/sieht die einzelnen Threads Threads braucht Multithreading gar nicht zu unterstützen (beachte: keine Thread-Tabelle im Kernel- Adressraum) Erzeugung eines User-Threads: … eines Kernel-Threads: durch lokale (Bibliotheks-) Funktion durch Kernel-Aufruf (OS-Aufruf) im Prozess Verwaltung der Threads (Threadwechsel): durch Threads selbst durch OS (analog Prozesswechsel) (untereinander) im Kern-Adressraum im User-Adressraum (Prozess) Wenn ein Thread blockiert: sieht das OS nur den gesamten erkennt das OS genau diesen blockierenden Prozess → blockierenden Thread → Prozesswechsel Threadwechsel (ggf. aus anderem Prozess, Entscheidung durch OS) SYT3-BS_01_Multithreading.docx 10 (12) Andere Darstellung für User-Threads (obwohl hier das Betriebssystem Multithreading unterstützt): Auch wenn das Betriebssystem Multithreading unterstützt (beachte: Thread-Tabelle im Kern-Adressraum vorhanden): sieht das Betriebssystem (trotzdem) nur 1 Thread die User-Threads verbergen sich hinter dem einzigen Eintrag in der OS-Thread- Tabelle (im Kern-Adressraum) Alternative Bezeichnungen zu User-Threads: Fibre (engl. Faser), ein Teil eines Threads (engl. Strang) (Microsoft) (Lightweight Thread) Green Thread (Java) User-Threads Kernel-Threads Multi-Core CPU: Parallelisierung nicht möglich Parallelisierung möglich Nur 1 Userthread kann glzt. rechnen Mehrere Kernelthreads können glzt (auf mehreren CPU-Kernen) laufen SYT3-BS_01_Multithreading.docx 11 (12) Hybride Implementierung Kombination aus Kernel- und User-Threads (d.h. separate Thread-Tabellen) Der Prozess (Programmierer) entscheidet bei dem Erzeugen eines neuen Threads, „wo“ dieser angelegt wird (bzw. um welche Art von Thread es sich handelt) OS kennt nur die Kernel-Threads Ein Kernel-Threads kann sich auf mehrere User-Threads aufteilen D.h. jeder User-Thread muss einem Kernel-Thread (= etwas, dass das BS kennt) zugeordnet sein. Prozesse beinhalten (u.U.) mehrere Threads Die einzelnen Threads können sich (u.U.) in mehrere einzelne Fibres aufteilen Ein Thread kann: Ein Fibre (=User-Thread) erzeugen Einen (Kernel-) Thread erzeugen Einen Prozess erzeugen Auf ein Fibre wechseln Das OS wechselt zwischen den: Kernel-Threads Prozessen SYT3-BS_01_Multithreading.docx 12 (12) Detail bei Blockierenden Aufrufen in User-Threads: Z.B. Abfrage auf Usereingabe, die noch nicht erfolgt ist: Kennt das OS die einzelnen Threads nicht (sondern nur den Prozess), so führt ein blockierender Aufruf zu einem Prozesswechsel! Widerspruch: Grund für Threads: 1 blockierender Thread (und andere rechnende Threads) sollen nur einen Thread-Wechsel, aber keinen Prozesswechsel bewirken OS erkennt nur einen blockierenden Prozess(!) (Single-Thread) Threadwechsel obligt der Programmierung selbst! Ansätze: a) Das OS müsste in diesem Fall (also weitere User-Threads vorhanden, davon weiß das OS aber nichts!) auf einen blockierenden Aufruf „anders“ reagieren – im Sinne: dem Thread noch die Chance auf einen internen Userthread- Wechsel geben… Widerspruch: da ein OS genau diese Situation nicht erkennen kann – die User-Threads werden vor dem OS verborgen! b) Die User-Threads übernehmen Threadwechsel selbst, ein blockierender Aufruf aber triggert das OS zu einen Threadwechsel → der blockierende Aufruf muss schon vermieden werden. Statt eines blockierenden Aufrufes muss ein Threadwechsel (auf einen anderen User-Thread, der eben nicht blockiert) ausgeführt werden – aber nur genau dann, wenn der „blockierende Aufruf“ tatsächlich blockiert! Bsp. Unix: o read: (von Tastatur) könnte blockieren o select: prüft dies vorweg (ohne zu blockieren) Aufgrund der kürzeren Zeiten für Thread-Wechsel ergibt sich hier ein „Netto-Zeitgewinn“ Andere Sichtweise: User-Threads sind wie „Absprünge“, wie z.b. für (Bibliotheks-) Funktionen. Der aufrufende Code wird während der Ausführung der Funktion unterbrochen. Allerdings herrscht mit dem Ausführungsende der aufgerufenen Funktion kein Zwang, wieder zum Aufrufer (aufrufenden User-Thread) zurückzukehren: vielmehr kann hier auch wieder eine weitere Funktion (d.h. User-Thread) gestartet werden … Kein rekursiver Abstieg (mit anschließendem Aufstieg) Irgendwann später wird wieder der urprüngliche User-Thread aufgerufen – d.h. fortgesetzt.