Modul B-PRG Grundlagen der Programmierung 1Präemptives Scheduling Einführung von „Zeitscheiben“: Rücksichtslose Prozesse/Benutzer! Abbruch Ankunft Warteschlange Abgang Prozessor

1

Modul B-PRG

Grundlagen der Programmierung 1

Teil 3:Teil 3: Betriebssysteme, Betriebssysteme, Dateisysteme,SicherheitDateisysteme,Sicherheit

V20: V20: ProzesseProzesse

Prof. Dr. R. BrauseAdaptive SystemarchitekturInstitut für Informatik Fachbereich Informatik und Mathematik (12)

Grundlagen der Programmierung 1 R.Brause: Prozesse Folie 2

Warum Mehrprozessbetrieb?

Effiziente Nutzung des Systems

u Mehrprogrammbetrieb: mehrere Teilnehmer am Rechner bzw. Server-Betrieb im Netz

v Parallelbetrieb: unterschiedliche CPU-Nutzung parallel auszuführender Prozesse eines Programms

Programme und Prozesse

2


CPU-Idle

Diskette

Festplatte

Drucker

... und noch freie Prozessorkapazität fürrechenintensives Programm im Hintergrund

Parallelbetrieb durch Prozesse

Daten drucken

Platte lesen

Daten lesen Daten lesen Daten lesen Daten lesen

Daten drucken Daten drucken

Platte schreiben Platte lesen Platte..

Prozesse


Was sind Prozesse ?

Prozess = Programmdaten + Prozeßkontext

Prozeß

Daten CPU MMURegister Register

Dateiinfo,Zugriffs- Kernel-rechte stack

Prozeßkontext

Pro-gramm

Stack

3


Unix Prozeßkontext

Speicherresidente Prozeßkontrollblöcke PCB der ProzeßtafelScheduling-ParameterSpeicherreferenzen: Code -, Daten-, Stackadressen im Haupt- bzw. MassenspeicherSignaldaten: Masken, ZuständeVerschiedenes: Prozeßzustand, erwartetes Ereignis, Timerzustand, PID, PID der Eltern, User/Group-IDs

Auslagerbarer Benutzerkontext (swappable user structure)Prozessorzustand: Register, FPU-Register, …

Systemaufruf: Parameter, bisherige Ergebnisse, …

Datei-Info-Tabelle (file descriptor table)

Benutzungsinfo : CPU-Zeit, max. Stackgröße, …Kernel-stack: Platz für Systemaufrufe des Prozesses


Prozeßzustände

Prozesse warten ...auf den Prozessor (bereit)auf eine Nachricht (blockiert)auf ein Zeitsignal (blockiert)auf Daten des I/O-Geräts (blockiert)

nicht-ex.

erzeugt

bereit

iterm niert

nicht-ex

erhalteSignal

aktivrunningZuteilung

blockiert erwarteSignal

Dispatcheraktionen

4


Prozeßerzeugung

Ein Programm (Job) kann mehrere Prozesse erzeugen

z.B. UNIX shell (Elternprozeß)

cat Text1 Text2 | pr | lpr

Kindsprozess3Kindsprozess1 Kindsprozess2


Unix: Prozeßerzeugung

Beispiel shell Pseudocode

LOOPWrite(prompt); (* tippe z. B. ´>´ *)ReadLine(command, params); (* lese strings, getrennt durch Leertaste *)pid := fork(); (* erzeuge Kopie dieses Prozesses *)IF (pid=0) THEN execve(command,params,0)(* Kind: überlade mit Programm *)ELSE wait(pid) (* Eltern: warte aufs Ende vom Kind *)END;

END;

5


Kind

if (PID==0){exec („program“)

...};

/* PID = = 0 */

Unix: Prozeßerzeugung

Eltern

PID = fork()/* PID ≠ 0 */

if (PID==0){ ...

...};wait(PID) . . .

exit () };. . .

NebenlNebenlääufigkeitufigkeit

6


Threads (Coroutinen)

gemeinsamer Prozeßkontext (Speicher-Addressbereich, Dateien (file handles)

Thread 1

Thread 2

Thread 3

Gemeinsamer Prozeßkontext

asynchroner, paralleler, unterschiedlicher Programmverlauf (eigener stack)


Thread- Typen: lightweight threads

n kontrolliert vom Benutzerprogramm (z.B. Unix-Bibliothek)

Vorteil: sehr schneller thread-WechselNachteil: Blockieren aller threads bei I/O-Warten

von einem thread.

Prozeß

T1 T2

Prozeß- I/O

Systemaufruf

7


Thread- Typen: heavyweight threads

n kontrolliert vom Betriebssystem (z.B. Windows NT)

Vorteil: Unabhängiger I/O aller threadsNachteil:langsamer BS-Systemaufruf nötig

⇒ fibers in NT

Prozeß

T1 T2

thread I/O thread I/O

Systemaufruf


Threads in Python

Modul thread:§ Funktionen zur Erstellung und Verwaltung von Threads.§ Low-Level Thread-Programmierung

Modul threading:§ Basiert auf Modul thread.

§ Gekapselte Thread-Klasse

§ High-Level Thread-Programmierung

Hinweis: Die mitgelieferte Entwicklungsumgebung von Python – IDLE – ist nicht thread-sicher, so sind zum Beispiel die Ausgabefunktionen nicht synchronisiert.

Insbesondere bringt die gleichzeitige Ausführung von print-Anweisungen IDLE zum Absturz!? Eigene Programme, die Threads benutzen, von der

Kommandozeile aus starten!

8


Threads in Python

Definition der Klasse Thread im Modul threading:

Konstruktor (Auszug):Thread(target =None, name =None,...)§ target ist ein aufrufbares Objekt, das von der run()-Methode

aufgerufen wird. Aufrufbares Objekt: __call__() Methode ist definiert.

§ name ist der Name des Threads. § Wenn die Subklasse den Konstruktor überschreibt, so muss

sichergestellt werden, dass zuerst der Konstruktor der Basisklasse (Thread.__init__()) aufgerufen wird, bevor der Thread benutzt wird.


Threads in Python

Methode start():§ Starten des Threads. § Derselbe Thread kann nicht mehrmals gestartet werden.

§ Methode start() fügt den Thread dem Python-Schedulerhinzu, und kehrt dann sofort zurück.

Methode run():§ Wird vom Python-Scheduler aufgerufen

§ Sobald die Methode run() beendet ist, beendet sich auch der Thread.

Implementierung von Threads durch § überladen der Methode run(self) in der Klasse Thread§ oder durch Übergeben eines aufrufbaren Objekts.

9


Threads in Python

Beispiel (Implementierung durch Überladen der Methode run()):3 Threads zählen „gleichzeitig“ von 0 bis 9:import threading

class countThread(threading.Thread):def run(self):

self.counter = 0while self.counter != 10:

print self.getName() , self.counterself.counter = self.counter + 1

t1 = countThread(name = "Thread-1")t2 = countThread(name = "Thread-2")t3 = countThread(name = "Thread-3")t1.start()t2.start()t3.start()


Threads in Python

Ausgabe:Thread-1 0Thread-1 1Thread-1 2Thread-1 3Thread-1 4Thread-1 5Thread-1 6Thread-1 7Thread-1 8Thread-1 9Thread-2 0Thread-2 1Thread-2 2Thread-2 3Thread-2 4

Thread-3 0Thread-3 1Thread-3 2Thread-3 3Thread-3 4Thread-2 5Thread-2 6Thread-2 7Thread-3 5Thread-2 8Thread-3 6Thread-2 Thread-3 79Thread-3 8Thread-3 9…

…

Fehlende Synchronisation!

Thread 3 unterbricht Thread 2während der Ausgabe!

10

ProzeProzeßß--SchedulingScheduling


Prozeßscheduling

Vorplanung in verschiedenen ZeitmaVorplanung in verschiedenen Zeitmaßßststääbenben

Jobende Nutzer

Langzeit-schedul

Kurzzeit-schedul

Hier: Nur Hier: Nur KurzzeitschedulKurzzeitschedul !!

Ankunft Warteschlange Abgang

Prozessor

11


Prozeßscheduling: Ziele

n Maximale Auslastung der CPUZiel ist die 100%ige Auslastung der CPU, normal 40%–90%.

n Minimale Wartezeit (waiting time)Wartezeit in der bereit-Liste minimieren (einziger Scheduling-parameter)

Problem: Die Ziele sind weder vollständig noch konsistent

Beispiel AutovermietungWerden bestimmte Kunden bevorzugt, müssen andere warten.Sind alle Wagen gut ausgelastet, müssen neue Kunden warten.

Es gibt keinen idealen Schedulingalgorithmus !


„Jeder Prozeß läuft so lange, wie er will.“

First Come First Serve (FCFS).Einsortieren in der Ankunftsreihenfolge (FIFO-Warteschlange).

Nicht-präemptives Scheduling

Shortest Job First (SJF)Job mit kürzester Bedienzeit zuerst (min. mittl. Wartezeit).


Prozessor

Priority Scheduling (PS)PrioÚProzeß; Bevorzugung von hoher Prio.

ProblemSJF und PS erlauben verhungern (starvation) von benachteiligten Prozessen

12


Präemptives Scheduling

Einführung von „Zeitscheiben“: Rücksichtslose Prozesse/Benutzer!

Abbruch


Prozessor

Prozeß2Prozeß1Prozeß3Prozeß2Prozeß1

Zeitscheibe

„Jeder Prozeß läuft nur so lange, wie er darf.“


Round Robin (RR)Einsortieren in der Ankunftsreihenfolge (FIFO-Warteschlange) + Zeitscheibe

Präemptives Scheduling

Shortest Remaining Time FirstJob mit kürzester verbleibender Bedienzeit zuerst .

Dynamic Priority Round Robin (DPRR)wachsende Prio-Vorstufe + RR

Kombinationen aller Strategien

Documents

Modul B-PRG Grundlagen der Programmierung 1Präemptives Scheduling Einführung von „Zeitscheiben“: Rücksichtslose Prozesse/Benutzer! Abbruch Ankunft Warteschlange Abgang Prozessor