Übersichtwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS19/... · Die Implementierung von resume() erfolgt in zwei Teilen: der erste für den User-Mode, der zweite für den Kernel-Mode

2Betriebssysteme – WS 2019/20 - Teil 6/Threads

Übersicht

• I/O als langsamster Vorgang

• Prozesse und Threads

• Taskwechsel mit der Resume-Operation

• Interrupts

• Scheduler

• Time Sharing


Literatur I

[6-1] https://en.wikipedia.org/wiki/Polling_(computer_science)

[6-2] https://www.os-book.com/OS9/

[6-3] https://techdifferences.com/difference-between-interrupt-and-polling-in-os.html

[6-4] https://en.wikipedia.org/wiki/Interrupt https://en.wikipedia.org/wiki/Interrupt_request_(PC_architecture) https://en.wikipedia.org/wiki/Interrupt_handler

[6-5] https://en.wikipedia.org/wiki/Exception_handling https://en.wikipedia.org/wiki/Trap_(computing)

[6-6] https://en.wikipedia.org/wiki/Time-sharing https://en.wikipedia.org/wiki/Preemption_(computing)#PREEMPTIVE https://en.wikipedia.org/wiki/Cooperative_multitasking

[6-7] https://en.wikipedia.org/wiki/User_space https://en.wikipedia.org/wiki/Protection_ring#Supervisor_mode

[6-8] https://en.wikipedia.org/wiki/Context_switch


Literatur II

[6-9] https://en.wikipedia.org/wiki/Thread_(computing) https://en.wikipedia.org/wiki/Process_(computing) https://en.wikipedia.org/wiki/Process_management_(computing) https://en.wikipedia.org/wiki/Process_state

[6-10] http://pages.cs.wisc.edu/~remzi/OSTEP/ http://pages.cs.wisc.edu/~remzi/OSTEP/cpu-intro.pdf http://pages.cs.wisc.edu/~remzi/OSTEP/cpu-api.pdf

[6-11] https://en.wikipedia.org/wiki/Scheduling_(computing) http://ais.informatik.uni-freiburg.de/teaching/ws16/systems1/slides/kap07-scheduling.pdf http://www.inf.fu-berlin.de/lehre/WS11/OS/slides/OS_V7_Scheduling_Teil_1.pdf


Motivation

• Die Geschwindigkeiten einer CPU und die der I/O-Geräte sind sehr unterschiedlich. Ein fiktives Beispiel:– 1 Befehl sei mit 10 Takten durchgeführt,

d.h. bei einer Taktrate von 1 GHz benötigt ein Befehl 10 ns.

– 1 Plattenzugriff liegt im günstigsten Fall bei 8ms(bei Laptop-Platten ca. 12ms).Dies bedeutet, dass die CPU während eines Plattenzugriffs in diesem Beispiel mind. 800.000 Instruktionen ausführen kann.

• Ziel:Um die CPU während der I/O-Wartezeit zu nutzen, sollte diese Wartezeit mit der Abarbeitung anderer Programme verbracht werden.


Das weitere Vorgehen

• Bevor erklärt werden kann, wie das Ziel der optimierten Benutzung der CPU erreicht wird, sind einige Vorarbeiten notwendig....

• Im folgenden wird schrittweise in immer besser werdenden Versionen das endgültige Konzept vorgestellt.

• Aber:In der Praxis kommen auch die Zwischenversionen vor.


Durchführung von I/O-Vorgängen

• Ein I/O-Vorgang wird durch Beschreiben von Geräteregistern gestartet.

• Seine Beendigung wird durch Abfragen des Status-Registers vom Gerät erkannt. Dort zeigt das Busy-Bit an, ob der letzte Vorgang beendet ist.

• Polling = Befragen des Geräts durch die CPU nach dem Status bzw. nach der Beendigung des letzten I/O-Vorgangs

• Busy Waiting = Ausschließliches Polling durch die CPU

Beschreiben der Geräteregister // Kommando an Gerät

while Busy-Bit = 1 {

; // keine Operation

}

Ergebnis auswerten

Es wird davon ausgegangen, dass 1 Busy bedeutet.


Beispiel 1 – Keyboard-Interface

Zitat aus http://www.lowlevel.eu/wiki/KBC

Busy-Bit


Beispiel 2 – SSD-Interface

Auszug aus einem Datenblatt über SSD: www.micron.com


Treiber und Kernel I

• Das Lesen/Schreiben von einzelnen Worten bei Massenspeichern ist viel zu ineffizient: es werden daher immer Blöcke von mindestens 1..4 Kbyte pro Vorgang mit DMA verarbeitet.

• Das Veranlassen eines I/O-Vorgangs wird auch als Absetzen eines I/O-Kommandos bezeichnet.

• Treiber (Device Driver) = Komponenten im Kernel, die Zugriff auf die Geräte-Register haben und Eigenarten der Geräte verdecken (Wrapper)

• Die Treiber verdecken die speziellen Eigenschaften der Geräteregister (Aufbau, Kommandokodierung etc.) durch Realisierung einer einheitlichen Schnittstelle.

• Die Aufgabe der Treiber besteht darin, die I/O-Kommandos abzusetzen und deren Ergebnisse zu verarbeiten.


Treiber und Kernel II

• Kernel = Speicherresidenter Teil des Betriebssystems

• Der Kernel besteht aus Routinen bzw. Komponenten, die gemeinsam von den Threads und Prozessen benutzt werden.

• Diese Routinen bzw. Komponenten werden zum Beginn (Boot) in den RAM geladen und verbleiben dort bis zum Herunterfahren (Shutdown).


Das Problem und die Lösung

• Idee:Während des Wartens auf I/O arbeitet die CPU ein anderes Programm ab bis der I/O-Vorgang beendet ist; dann wendet sie sich wieder dem alten Programm zu. Dazu ist aber ein Programm- oder Threadwechsel notwendig.

• Thread = Sequentiell interpretiertes Programm bzw. Teil davon bestehend aus Code und Daten

• Threadwechsel = Änderung der Zuordnung von Thread-Code zur CPU

Das Problem besteht darin, dass die I/O-Geräte um mindestensden "Faktor" 800.000 langsamer als die CPU sind, so dass die CPU mit dem Busy Waiting sehr viel Zeit vergeudet.

Der Name Thread stammt von der Idee eines Fadens,der die "Spur" des Programm Counters im Code symbolisiert.


Prozesse und Threads I

• Ein Thread besteht immer aus Code und Daten (RAM) sowie dem CPU-Status.

• CPU-Status = Inhalt aller Register der CPU

• Im CPU-Status wird der aktuelle Zustand zum Zeitpunkt des Wechsels zu einem anderen Thread abgespeichert.


Prozesse und Threads II

• Ein Prozess besteht aus gegenüber anderen Prozessen abgetrennten Code und Daten samt eigenen CPU-Status.

• Ein Prozess kann mehrere Threads umfassen/beinhalten.

• Threads teilen sich innerhalb von Prozessen den RAM, während Prozesse in getrennten RAM-Bereichen residieren.

• Im folgenden wird nicht zwischen Prozessen und Threads unterschieden.

Thread T1 Thread T2


Threadwechsel mit resume() I

• Es wird nun eine fiktive Operation namens resume() definiert, die immer dann benutzt wird, wenn die CPU abgegeben werden muss.

• Folgende Definition von resume(Thread) beschreibt den Ablauf beim Wechsel ausgehend von einem Thread zu einen anderen:

resume(Thread P) ==> // Ablauf! Wechsel in den Kernel-Modus Rette PC und SR // aktueller Thread Rette die allgemeinen Register ------------ // Wechsel Stelle allgemeine Register her Stelle PC und SR her Wechsel in den geretteten Modus // neuer Thread P

TRAP

RTT


Threadwechsel mit resume() II

Threadwechsel mit resume(Thread): beide Threads arbeiten im User-ModeNur während der Ausführung von resume() wird im Kernel-Modus gearbeitet.resume() ist daher ein Systemaufruf (Syscall).

Thread T1 Thread T2

resume(T1)resume(T2)

resume(T2) resume(T1)


Threadwechsel mit resume() III - Bemerkung

• Aus Gründen des Schutzes wird– der CPU-Status im Kernel gehalten,

– läuft die resume()-Routine daher im Kernelmodus.

• Aus diesem Grund wird zum Beginn von resume() mittels der Trap-Instruktion in den Kernelmodus gewechselt

• und zum Ende mittels der RTT-Instruktion wieder zurück in den User-Modus.

• D.h. resume() wechselt über den Kernel von einem User-Thread zu einem anderen.


Threadwechsel mit resume() IV

• Jeder Thread wird mit einem Threaddeskriptor verwaltet:

• Aufbau des Threaddeskriptors:– Identifikation

– Verbrauchte CPU-Zeit

– Priorität

– etc.

• Die Zusammenfassung aller Deskriptoren in einer Tabelle wird meist Threadtabelle genannt.

• Wir werden später nach der Einführung des Virtuellen Speichers von einem Processdeskriptor sprechen.Die Tabelle heißt dann Prozesstabelle.Ein anderer Name ist auch Process Control Block.

• Im Linux-Umfeld wird der Begriff der Task als Oberbegriff von Thread und Prozess benutzt. Daher heißt dann diese Tabelle Tasktabelle.


Thread-Tabelle I

• Die Threads erhalten eine eindeutige Nummer – dies könnte auch der Index in der Tabelle threadTbl[] sein.

• Das Thread-Layout beschreibt den Bereich des Threads im RAM, d.h. wo Code und Daten im RAM liegen, welche Adressen den Stack und Heap beschreiben.

• Der CPU-Status wird teilweise auf einen eigenen Stack im Kernelmode abgespeichert.

struct Thread { // 1. Version int id; // Identifikation des Threads ThreadLayout data; // Aufbau des Datensegments}

Thread threadTbl[MAX_THREADS];


Thread-Tabelle II - ThreadLayout

• Jeder Thread hat eigene Werte von SP und SL, sowie einen eigenen Datenbereich.

• Im ThreadLayout-Deskriptor werden diese Werte abgespeichert.

• Im Layout fehlt noch die Beschreibung des Code-Bereichs.

struct ThreadLayout {// 1. Version address min; // Untere Adresse address max; // Obere Adresse address SP; // Stackpointer address SL; // Stacklimit}


Speicher-Layout für mehrere Threads I

… … …

Thread1 Thread2 ThreadN

Mehrere Threads werden in einemProzess zusammengefasst.


Speicher-Layout für mehrere Threads II

• In der Thread-Verwaltung des Kernels befindet sich die Thread-Tabelle.

• Der Code wird von allen Threads eines Prozesses gemeinsam benutzt.

• Diese Aufteilung des RAMs betrifft hier die gesamte Maschine.

• Es gibt auch Realisierungen von Threads innerhalb eines Prozesses; dann befindet sich die Verwaltung dazu auch im Prozess und kann ohne Wechsel des CPU-Modes benutzt werden.

CodeDaten

Thread1Daten

Thread2Thread-

VerwaltungDaten

ThreadN…

0 max

... ...

... ...

Prozess


resume() I - Beispiel

User-Mode

resume(Thread P){ push(P) trap #1 pop()}

Kernel-Mode

Trap-Handler#1(){ push(Alle-Register-ohne-SP) store SP in ThreadDescriptor get new Threaddeskriptor P set new values of SP Alle-Register-ohne-SP= pop() rtt}

Die Implementierung von resume() erfolgt in zwei Teilen:der erste für den User-Mode, der zweite für den Kernel-Mode.

Der Parameter P – der Name des neuen Threads – wird vor dem Trap auf denStack gebracht und anschließend dort wieder entfernt. Es gibt auch Realisierungen, bei denen der 1. Parameter in einem Registerübergeben wird.


resume() II - Beispiel

User-Mode

resume(Thread P){ push(Alle-Register-ohne-SP) store SP, SL in ThreadDescriptor get new Threaddeskriptor P set new values of SP Alle-Register-ohne-SP= pop()}

• Es ist aber auch möglich ohne die beiden CPU-Modi eine Thread-Umschaltung zu realisieren.

• Das ist dann der Fall, wenn innerhalb eines Programms bzw. Prozesses über Bibliotheksroutinen Threads realisiert werden.


resume() III - Zusammenfassung

• In dieser Version läuft die Verwaltung der Threads innerhalb des Kernels.

• Die Threads selbst laufen im User-Mode (User-Threads).

• Der Kernel selbst kann auch selbst in mehreren Threads realisiert sein, so dass die Thread-Verwaltung auch Kernel-Threads verwaltet.

…... Code

DatenThread1

DatenThread2

Thread-Verwaltung

DatenThreadN

…

0 max

…...

Die Zuordnung des CPU-Modus zu den Komponenten


resume() IV

<- SP

(User-)Stack

Situation zum Beginnder Trap-Handlers

Situation bei Abgabeder Kontrolle

<- SP

(User-)Stack

<- SP

(User-)Stack

Situation direktvor dem Trap

nach Aufruf vonresume()


resume() V

<- SP

(User-)Stack (User-)Stack

Situation vor Annahmeder Kontrolle des neuen

Threads

Situation währendder Ausführung des

neuen Threads


Beispiel-Situation

<- SP

Thread1

<- SP

Thread2

<- SP

ThreadN

<- SP

Thread3

schläft schläft schläftläuft


Systemaufruf I

• Ein Systemaufruf ist das Aufrufen einer Routine des Kernels, die im Kernel-Modus der CPU abläuft.

• Ein Systemaufruf ist vollkommen analog zum Aufruf einer Routine – so wie bisher behandelt.

• Warum ist der Kernel-Modus erforderlich?Ausführen von I/O-Instruktionen bzw. der Zugriff auf die Geräte-Register sollte aus Sicherheitsgründen nur in diesem Modus möglich sein.


Systemaufruf II

• resume() betrifft den Fall, dass ein Threadwechsel aus einem laufenden Thread zu einem anderen laufenden Thread im User-Modus stattfinden soll.

• Ein Systemaufruf ohne Threadwechsel läuft sehr ähnlich zu resume() ab, nur dass eine Routine ausgeführt wird:

Syscall(Name, Parameter) = // Verkürzter Ablauf! Wechsel in den Kernel-Modus Rette PC und SR // aktueller Thread Rette die allgemeinen Register // aktueller Thread ..... Führe den Systemaufruf Name mit Parameter aus ..... Stelle allgemeine Register her // aktueller Thread Stelle PC und SR her // aktueller Thread Wechsel in den User-Modus

TRAP

RTT


Das Ganze mit Busy Waiting (Ablauf)

Syscall(Name, Parameter) = // Verkürzter Ablauf! Wechsel in den Kernel-Modus Rette PC und SR // aktueller Thread Rette die allgemeinen Register // aktueller Thread ..... Beschreiben der Geräteregister // Kommando an Gerät while Busy-Bit = 1 { ; // keine Operation } Ergebnis auswerten ..... Stelle allgemeine Register her // aktueller Thread Stelle PC und SR her // aktueller Thread Wechsel in den User-Modus

TRAP

RTT

Das gilt im Prinzip für alle I/O-Routinen.


Implementierung von Systemaufrufen

User-Mode

syscall(int N,Param) = { push(N) trap #1 pop()}

Kernel-Mode

Trap-Handler#1() = { push(Alle-Register-ohne-SP) Get Syscallnumber N Get Parameter Call N(Parameter) Alle-Register-ohne-SP= pop() rtt}

Die Ähnlichkeiten zum resume() sind nicht zufällig,denn das resume() ist eigentlich ein Syscall...


Threadwechsel innerhalb des Systemaufrufs

• Wenn nun ein Syscall mit I/O, z. B. Lesen von einer Platte, durchgeführt wird, wird der erste Teil des resume() wie bei einem Syscall ausgeführt.

• Der Threadwechsel findet dann im Code des Systemaufrufs statt, wobei die Operation continue(Thread) die 2. Hälfte des resume() realisiert.

• Damit wird ein Threadwechsel bei jedem Warten realisiert:

// während des Syscalls im KernelSetzen der Geräteregister // Absetzen eines Kommandoswhile Busy-Bit = 1 { continue(Thread) // CPU abgeben}Ergebnis auswerten.....


continue() I

• continue() ist eine Variante von resume(), bei der initial keine Trap-Instruktion ausgeführt wird. Es wird daher das Stacklayout einer Trap-Instruktion nachgebaut, so dass dieselbe Stack-Struktur am Ende entsteht.

• continue() wird als Subroutine im Kernel aufgerufen, so dass der normale Stackaufbau eines Routinenaufrufs entsteht.

• Nach Beendigung von continue(Thread P) wird der Thread P direkt nach dessen letzten continue() fortgesetzt.

continue(Thread P) = // Verkürzter Ablauf! Rette PC und SR // explizit im Kernel Rette die allgemeinen Register // aktueller Thread ------------ // Wechsel Stelle allgemeine Register her Stelle PC und SR her // aktueller Thread Wechsel in den geretteten Modus // neuer Thread P

RTT

Ein Wechsel kann auch innerhalb des Kernel stattfinden.


continue() II – ein Beispiel

(3): Wechsel Kernel- -> User-Mode, (5), (7), (9) Wechsel innerhalb des Kernel-Modes

Start(1)

(3)

(5)

(9)

(7)

Prozesswechsel innerhalb von Systemaufrufen

User-Mode

Kernel-Mode

Thread1 Thread2

continue(T1)continue(T2)

continue(T2) continue(T1)


continue() III

• War die letzte Aktion des zukünftigen Threads T ein continue(), so wird im Kernel weiter gemacht, eben nach dessen continue().

• Hierbei entsteht eine kleine Schwierigkeit:continue() selbst wurde als eine Subroutine aufgerufen, was stört. Daher wird der Stackaufbau des Calls beseitigt.

• War die letzte Aktion des zukünftigen Threads T ein resume(), so wird in dessen User-Mode weiter gemacht.

• Das wird dadurch erleichtert, dass für beide Fälle derselbe Stackaufbau benutzt wird.

• Der zukünftige CPU-Modus wird durch den alten auf dem Stack geretteten SR-Wert bestimmt; dieser Wert wird von der RTT-Instruktion zur Bestimmung des zukünftigen CPU-Modus verwendet.


continue() IV

So sieht die Stack-Struktureines schlafenden Threads

aus

<- SP <- SP

Das ist der CPU-Statusohne den Stackpointer

<- SP

Stack-Struktureines schlafenden Threads,

wenn vorher continue()aufgerufen wurde

Stack-Struktureines schlafenden Threads,

wenn vorher resume()aufgerufen wurde


continue() V

continue(Thread T){ return-adr:= pop() push(SR) push(return-adr) push(Alle-Register-ohne-SP) store SP in Threaddeskriptor --- Wechsel get new Threaddeskriptor of T set new values of SP Alle-Register-ohne-SP= pop() rtt}

<- SP

Alter Thread T

Aus trap heraus

Aktueller Thread

<- SP

Stackaufbau zumZeitpunkt des Wechsels


continue() VI

continue(Thread T){ return-adr:= pop() push(SR) push(return-adr) push(Alle-Register-ohne-SP) store SP in Threaddescriptor --- Wechsel get new Threaddeskriptor of T set new values of SP Alle-Register-ohne-SP= pop() rtt}

Aktuell

<- SP

Thread T

<- SP

Direkt nach RTTbeim Aufrufer vom

continue()

Nach derThread-Abgabe


Bemerkungen

• Wird kein I/O gemacht, so sollten sich die Prozesse in dieser Version gegenseitig per resume() aufrufen (so wie zum Anfang).

• resume() wird wie ein Syscall ohne I/O behandelt.

• Syscalls ohne I/O rufen nie continue() auf.

• Alle Syscalls mit I/O rufen immer continue() auf.

continue() aktiviert einen anderen Thread, der im Kernel ist.

Aber: alle schlafenden Threads sind immer im Kernel. Warum?


Busy Waiting mit continue() (Ablauf)

Syscall(Name, Parameter) = // Verkürzter Ablauf! Wechsel in den Kernel-Modus Rette PC und SR // aktueller Thread Rette die allgemeinen Register // aktueller Thread ..... Beschreiben der Geräteregister // Kommando an Gerät while Busy-Bit = 1 { continue(Thread) // CPU abgeben } Ergebnis auswerten ..... Stelle allgemeine Register her // aktueller Thread Stelle PC und SR her // aktueller Thread Wechsel in den User-Modus

TRAP

RTT

Warum immer noch die While-Schleife?Weil der Thread vorzeitig die Kontrolle bekommen kann.


Scheduler I

Doch es gibt ein Problem:

Der Thread, der zu warten beginnt, d.h. der continue-Aufrufer,muss wissen, welche Threads existieren und welcher von diesenweiter arbeiten soll.

Lösung: Es wird immer zu einem Thread Namens Scheduler

gewechselt, der den nächsten zu aktivierenden Thread bestimmt.


Scheduler II

• in der Threadtabelle mitschreiben, welche Threads existieren,

• vermerken, welcher Thread zu welchem Anteil die CPU schon bekommen hat,

• vermerken des Thread-Zustandes (state):– Running: Thread hat gerade die CPU

– Ready: Thread wartet auf CPU

– Waiting: Thread wartet auf Beendigung von I/O

– Sleeping: Thread benötigt irgendwann später die CPU,

• ändern des Threadzustands entsprechend einer neuen Situation,

• zuteilen der CPU dem nächsten Thread.

Der Scheduler wird in einem eigenen Thread innerhalb des Kernelsrealisiert, der für folgende Aufgaben zuständig ist:


Scheduler III

• Scheduler = Thread, der die Zuteilung der CPU zu den Threads nach einem Verfahren (Scheduling Strategie) realisiert

• In der Threadtabelle werden dann die dafür notwendigen Informationen untergebracht.

struct Thread { // 2. Version int id; // Identifikation int state; // Zustand ThreadLayout data; // Datensegment}

Thread threadTbl[MAX_THREADS]


Scheduler IV

Thread T1

......

......

continue(Scheduler); ......

......


Thread T2

......

......


......


Start

(1) (3)

(5)(7)

(9)

Thread Scheduler

while true { look_for_next;

continue(Thread);

}

[Verkürzte Version: das continue(Scheduler) ist Teil eines SyscallsDer Scheduler selbst arbeitet permanent im Kernel-Modus]

Kernel-Mode

User-Mode

(2), (4), (6), (8), (10)


Dann gibt es noch zwei kleine Probleme...

1. Es ist immer noch das Polling notwendig - Nachsehen, ob der I/O-Vorgang beendet ist.Dies ist zwar schon reduziert, aber noch vorhanden.

2. Eine Endlosschleife in einem Thread ohne ein Syscall/Continue bringt das gesamte System zum Absturz, da nur mit der Beendigung des Ganzen dieser eine Thread beendet werden kann.Besser ist, dass nur der Thread mit der Endlosschleife getrennt von den übrigen beendet wird.


Unterbrechungen (Interrupts) I

• Wenn ein I/O-Gerät seine Operation beendet hat, sendet es über den Bus ein Signal, das von der CPU als Unterbrechung (Interrupt) behandelt wird.

• Empfängt die CPU dieses Signal, so passiert folgendes:– Die Ausführung der aktuellen Instruktion wird beendet.

– Anstatt die nächste Instruktion auszuführen, wird eine Art Trap-Instruktion ausgeführt.

• Die Behandlung im Kernel besteht in der Ausführung einer für diesen Interrupt speziellen Routine, dem Interrupt-Handler (Unterbrechungsbehandler).Dieser tut folgendes:– Feststellen, welches Gerät die Unterbrechung signalisierte

– In der Threadtabelle alle Threads, die auf diese Unterbrechung warten, in den Zustand Ready bringen


Unterbrechungen (Interrupts) II

Interrupt-Nummer

Adresse F1

Tabelle steht aneiner speziellendafür vorgesehenenStelle

Adresse F2

Adresse F3

Adresse F4

.....

Adresse FN

Indizieren

Handler F4

Handler F3

Handler F2

.....

Der Mechanismus zur Bestimmung des Handlers nach einem Interrupt istderselbe wie bei einer Exception, wenn jedem Interrupt eine Nummerzugeordnet ist.


Ablauf beim Interrupt - Version 1

• In dieser Version wird das aktuell laufende Programm lediglich unterbrochen und nach dem Ändern der Threadtabelle wieder fortgeführt, d.h. es findet kein Threadwechsel statt.

• Der Interrupt kann auftreten, wenn die CPU im User-Modus ist aber auch im Kernel-Modus!

• Dieses Verfahren hat den Nachteil, dass Threads, die auf den Interrupt lange gewartet haben, noch weiter warten müssen.

Interrupt Handler = // Ablauf! Wechsel in den Kernel-Modus // wie bei Trap-Instruktion Rette PC und SR Rette die allgemeinen Register Bestimme signalisierendes Gerät Setze wartende Prozesse auf Ready Stelle allgemeine Register her // alte Werte Stelle PC und SR her // alte Werte Wechsel in den geretteten Modus

INT

RTI


Ablauf beim Interrupt - Version 2

• In dieser 2. Version wird direkt nach dem Ändern der Threadtabelle zum Scheduler gewechselt.

• Der Scheduler durchsucht bei jedem seiner Aufrufe die Threadtabelle nach Threads im Zustand "Ready" bzw. "Running", um einen von diesen auszuwählen. Alle anderen Threads werden von ihm ignoriert.

• Das heißt, dass ein Signal/Interrupt die Bedeutung eines resume(Scheduler) hat, wenn der aktuelle Thread im User-Modus war, oder eines continue(Scheduler), wenn der aktuelle Thread im Kernel-Modus war.

Interrupt Handler = // Ablauf! Wechsel in den Kernel-Modus // gilt auch für den Kernel Rette PC und SR Rette die allgemeinen Register Bestimme signalisierendes Gerät Setze wartende Prozesse auf Ready continue(Scheduler)

INT


Die beiden Behandlungsmöglichkeiten

Thread T1 Thread T1 Thread T2


Warten auf I/O mit Interrupts I

• Der Thread setzt sich freiwillig auf eine Warteliste, indem er in den Zustand "Waiting" geht. Ein I/O-Deskriptor beschreibt das Gerät bzw. den Vorgang, auf den der Thread wartet.

• Wenn der Interrupt-Handler dieses Geräts aktiviert wird, werden alle mit dessen I/O-Deskriptor wartenden Threads in den Status "Ready" gesetzt.

Thread Tn ..... Beschreiben der Geräteregister; wait(I/O-Descriptor); Ergebnis auswerten; .....

PROC wait(I/O-Descriptor) Setze Thread Status("Waiting"); Setze I/O-Descriptor in IO-Tabelle; continue(Scheduler);

struct I/O-Descriptor { Address SR-Register; int Busy-Bit-Number;}


Warten auf I/O mit Interrupts II

• Wir kennen nun zwei Tabellen: die Threadtabelle und die Tabelle mit den I/O-Desriptoren.

• Die I/O-Descriptoren sind fest den Geräten zugeordnet. In ihnen wird auch der Aufbau der Geräte-Register beschrieben.

• In der Threadtabelle ist daher ein Verweis auf den I/O-Descriptor vorgesehen, der beim Warten gesetzt wird:

struct Thread { // 3. Version int id; // Identifikation des Threads int state; // Zustand ref I/O-Descriptor // Verweis auf das Gerät ThreadLayout data; // Datensegment}


Priorisierung von Interrupts III

• sind im ersten Fall alle Interrupts ausgeschaltet

• hat die CPU im zweiten Fall den Level des Interrupts

Das bedeutet, dass der Interrupt-Handler nicht oder nur durch Interrupts höherer Priorität unterbrochen werden kann.

• Selbstverständlich kann der Interrupt-Handler den Level ändern.

• Aber:Die Interrupt-Handler sollten immer nur so kurz wie nur möglich die Interrupts verhindern, da ansonsten Interrupts verloren gehen könnten.

• Und was passiert, wenn ein Interrupt verloren geht?Der Thread, der auf diesen Interrupt wartet, würde niemals aufgeweckt werden.

Wenn der Interrupt-Handler läuft...


Damit ist das erste Problem gelöst....

• Durch den Mechanismus des Interrupts entfällt vollkommen das Polling und damit auch das Busy Waiting.

• Ein auf I/O wartender Thread wird erst dann aktiviert, wenn der I/O-Vorgang beendet ist.Besser geht es nicht mehr.

• Was aber passiert, wenn alle Threads auf I/O warten?Dann findet der Scheduler keinen Thread, den er aktivieren kann und durchsucht in einer Endlosschleife seine Tabelle bis er selbst unterbrochen wird.

• Dieser unterbrechende Interrupt-Handler setzt dann einen der Threads auf "Ready" und aktiviert direkt den Scheduler; der findet dann, was er sucht.


Time Sharing Verfahren

• Mit den vorgestellten Mechanismen lassen sich alle Nachteile bis auf die "Ungerechtigkeiten" bei der CPU-Vergabe sowie bis auf den Fall der Endlosschleifen beseitigen.Das letztere Problem wird durch einen Timer gelöst.

• Ein Timer ist ein spezielles I/O-Gerät, das nach einer eingestellten Zeit bzw. in zyklischen Abständen einen Interrupt sendet. Dieser wird immer mit dem Aktivieren des Schedulers aus dem Timer-Handler heraus behandelt.

• Zeitscheibe = Dauer zwischen zwei Timer-Interrupts

• Nach Ablauf einer Zeitscheibe kann damit der Scheduler die CPU an einen anderen Thread geben, unabhängig davon, ob ein I/O-Vorgang erfolgte oder nicht.


Hinweis zu den beiden Stacks (Kernel und User)

• Es gibt zwei Möglichkeiten für die Stacks pro Thread:– Es gibt pro Thread/Prozess/Task nur einen Stack, der im User- und

im Kernelmodus gemeinsam benutzt wird. Auf diesen Stack wird der CPU-Status gerettet.

– Es gibt pro Thread/Prozess/Task für jeden Modus jeweils einen eigenen Stack, d.h. zwei Stackpointer. Mit dem Modus-Wechsel findet auch ein Stackwechsel statt. In diesem Fall wird der CPU-Status auf den Kernelstack gerettet.

• In Unix-Systemen wird die zweite Möglichkeit benutzt, da diese sicherer ist (Schutz des CPU-Status gegenüber anderen Threads innerhalb einer Prozesses).

• In den obigen Folien wurde aus Gründen der Einfachheit nicht immer genau zwischen den beiden Varianten unterschieden.


Zwei Begriffe noch...

• Ein Task, dem zwangsweise die CPU weggenommen werden kann, wird preemptive genannt, genauer das Scheduling dieser CPU ist preemptive.

• Non-preemptive bedeutet, dass eine Task nur freiwillig die CPU abgeben kann oder der Scheduler nimmt dieser Task nie die CPU weg (kann aber trotzdem quasi-parallel zur Task aktiv sein).

• Das oben vorgestellte Timesharing-Verfahren realisiert preemptive Tasks.

• Siehe dazu– https://de.wikipedia.org/wiki/Multitasking#Pr

%C3%A4emptives_Multitasking

– https://en.wikipedia.org/wiki/Preemption_(computing)

– https://kernelnewbies.org/FAQ/Preemption


Nach dieser Anstrengung etwas Entspannung....

Documents

Übersichtwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS19/... · Die Implementierung von resume() erfolgt in zwei Teilen: der erste für den User-Mode, der zweite für den Kernel-Mode