Transcript
Kapitel 2 Prozesse und Threads 2.1 Prozesse 2.2 Threads 2.3 Interprozesskommunikation 2.4 Klassische Probleme der Interprozesskommunikation 2.5 Scheduling
Prozesse Das Prozessmodell Unterschied Prozess / Programm Prozess ist eine Aktivität Besteht aus Programm, Input, Output und Zustand
a) Multiprogramming von vier Programmen b) Konzeptionelles Modell von vier unabhängigen sequentiellen Prozessen c) Zu einem Zeitpunkt ist nur ein Programm aktiv. Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
2
Prozesserzeugung • OS muss sicherstellen, dass alle wichtigen Prozesse existieren. • Manchmal: alle Prozesse die jemals benötigt werden, werden beim Startup erzeugt • Im allgemeinen: Möglichkeit zur Erzeugung / Beendigung erforderlich
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
3
Prozesserzeugung Ereignisse, die die Erzeugung eines Prozesses auslösen 1. Initialisierung des Systems (boot) 2. Systemaufruf zum Erzeugen eines Prozesses durch einen anderen Prozess 3. Benutzeranfrage, einen neuen Prozess zu erzeugen 4. Start eines Batch Jobs
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
4
Prozesserzeugung Booten Mehrere Prozesse werden gestartet • Prozesse zur Interaktion mit Anwender • Prozesse für bestimmte Funktionen – Email-service – Drucker-Warteschlange – Firewall
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
5
Windows Taskmanager Prozessliste
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
6
Prozessbeendigung Bedingungen, die zum Beenden von Prozessen führen 1. Normales Beenden (freiwillig) 2. Beenden auf Grund eines Fehlers (freiwillig) 3. Beenden auf Grund eines schwerwiegenden Fehlers(unfreiwillig) 4. Beenden durch einen anderen Prozess (unfreiwillig)
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
7
Prozesshierarchien • Elternprozess erzeugt Kindprozess. Kindprozess kann weitere Prozesse erzeugen. In UNIX ist das eine Prozessfamilie • Unter Windows gibt es kein Konzept einer Prozesshierarchie, alle Prozesse sind gleichwertig.
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
8
Prozesszustände (1) 1. Prozess blockiert wegen Eingabe 2. Schedular wählt einen anderen Prozess 3. Schedular wählt diesen Prozess 4. Eingabe vorhanden • Mögliche Prozesszustände – rechnend (running) – blockiert (blocked) – rechenbereit (ready) • Es existieren die dargestellten Übergänge zwischen diesen Zuständen Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
9
Prozesszustände (2)
• Die unterste Schicht eines prozessstrukturierten Betriebssystems behandelt Interrupts und Scheduling • Oberhalb befinden sich sequentielle Prozesse Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
10
Implementierung von Prozessen
Einige Felder eines typischen Eintrags einer Prozesstabelle
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
11
Umschalten zwischen Prozessen Context Switch Aufgaben der untersten Schicht des Betriebssystems bei Auftreten einer Unterbrechung 1. 2. 3. 4. 5. 6. 7. 8.
Hardware sichert Befehlszähler etc Hardware holt neuen Befehlszähler vom Interruptvektor Assemblerfunktion speichert Register Assemblerfunktion erzeugt neuen Stack C-Unterbrechungsroutine läuft (puffert Ein/- Ausgaben) Schedular sucht nächsten Prozess C-Funktion kommt zur Assemblerfunktion zurück Assemblerfunktion startet neuen aktuellen Prozess
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
12
Schritte für den Systemaufruf Adresse 0xFFFFFFFF
Return zum Aufrufer
Bibliotheksprogramm read
Systemaufruf in den Kern 5. Put code for read in register 10.
4.
11. Erhöhe Stackpointer
Benutzerraum
Benutzerprogramm ruft read auf
Rufe read auf
6.
count = read (fd, buffer, nbytes
3. Push fd 2. Push &buffer
1. Push nbytes 9.
Kernadressraum Verteilung
7.
8.
fd : filedescriptor buffer : Ziel nbytes : Länge
Systemaufrufbehandlung 13
Threads Das Threadmodell (1) • Traditionelles Modell: Prozess hat • einen Adressraum • einen Ausführungsfaden • Manchmal ist es wünschenswert, mehrere Ausführungsfäden zu haben
Drei Prozesse mit jeweils einem Thread
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
14
Threads Das Threadmodell (2) • Traditionelles Modell: Prozess hat • einen Adressraum • einen Ausführungsfaden • Manchmal ist es wünschenswert, mehrere Ausführungsfäden zu haben • wie eigene Prozesse, aber gemeinsamer Adressraum
Ein Prozess mit drei Threads
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
15
Das Threadmodell (3)
1. Spalte: Elemente werden zwischen den Threads eines Prozesses aufgeteilt 2. Spalte: Thread-eigene Elemente Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
16
Das Threadmodell (3)
Jeder Thread hat seinen eigenen Stack Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
17
Einsatz von Threads (1)
Ein Textprogramm mit drei Threads Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
18
Einsatz von Threads (2)
Ein Web-Server mit mehreren Threads Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
19
Einsatz von Threads (3)
• Grober Auszug des Codes zur vorherigen Folie. (a) Dispatcher thread (b) Worker thread Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
20
Einsatz von Threads (4) Drei Möglichkeiten, einen Server zu bauen:
Modell
Eigenschaften
Threads
Parallel, blockierende Systemdienste
Prozesse (ein Thread)
Nicht parallel, blockierende Systemdienste
Endlicher Automat
Parallel, nicht blockierende Systemdienste
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
21
Einsatz von Threads (5) Was Threads zu bieten haben: • Sie ermöglichen es, das Konzept von sequenziellen Prozessen, die blockierende Systemaufrufe (z.B. für Platten E/A) machen, beizubehalten und troztdem Parallelität zu erzielen • Blockierende Systemaufrufe vereinfachen die Programmierung und die Parallelität verbessert die Performance • Der Einzel-Thread-Server behält die Einfachheit von blockierenden Systemaufrufen bei, gibt jedoch die Performance auf. • Der dritte Ansatz bringt hohe Performance durch Parallelität, benutzt aber nicht blockierende Aufrufe und ist deshalb schwieriger zu programmieren Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
22
Realisierung von Threads im Benutzeradressraum (1) Ein Benutzer-Level Thread Paket
Vorteile: • kann auch auf Betriebssystemen realisiert werden, die Threads nicht unterstützen • Umschalten zwischen Threads geht vergleichsweise schnell Run-time system – Laufzeitsystem, enthält eine Sammlung von Prozeduren, die auch Threads verwalten (thread_create, thread_exit,...)
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
23
Realisierung von Threads im Benutzeradressraum (2) Ein Benutzer-Level Thread Paket
Dienstag, 30. April 2013
Probleme: • Ruft ein Thread einen blockierenden Systemaufruf auf (z.B. read von Tastatur), werden alle Thread blockiert • Systemaufrufe müssten nicht blockierend implementiert werden und Anwendungsprogramme müssten dafür modifiziert werden (sehr aufwendig) • Seitenfehler eines Threads blockieren ebenso alle Threads • Startet ein Thread, kommt kein anderer an die Reihe, bis der erste von sich aus die CPU freigibt
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
24
Realisierung von Threads im Kern(1) Ein Thread Paket, verwaltet vom Kern
Kern hat Thread-Tabelle, die alle Threads im System verwaltet Zur Sicherheit: Exkurs über Betriebssystemkern!
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
25
Betriebssystemkern (1) Wikipedia: Ein Betriebssystemkern oder Systemkern (engl. kernel ) ist der zentrale Bestandteil eines Betriebssystems. In ihm ist die Prozess- und Datenorganisation festgelegt, auf der alle weiteren Softwarebestandteile des Betriebssystems aufbauen. Er ist meist in der untersten Softwareschicht, hat also Zugriff auf die Hardware. Die Konstruktion eines Betriebssystemkerns gehört zum Themenbereich der Informatik und des Softwareengineerings. Gängige Anforderungen an einen Systemkern sind Parallelverarbeitung verschiedener Aufgaben (Multitasking), Einhaltung zeitkritischer Grenzen, Offenheit für unterschiedlichste Anwendungen und Erweiterungen. Nicht zum Systemkern gehörende Teile werden als Userland bezeichnet. Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
26
Betriebssystemkern (2) Bestandteile Ein Systemkern ist in Schichten (oder Layer, siehe Schichtenmodell) aufgebaut, wobei die unteren (maschinennahen) Schichten die Basis für die darüberliegenden bilden. Die oberen Schichten können Funktionen der unteren Schichten aufrufen, aber nicht umgekehrt. Folgende Schichten sind vorhanden (von unten nach oben): • Schnittstelle zur Hardware (Geräte, Speicher, Prozessoren) • Speicherverwaltung (evtl. einschließlich virtuellem Hauptspeicher) • Prozessverwaltung (auch Scheduler genannt) • Geräteverwaltung (auch Device Management genannt) • Dateisysteme Wenn alle diese Funktionen im Systemkern selbst integriert sind, spricht man von einem monolithischen Kernel. Bei einem Mikrokernel finden wesentliche Teile in getrennten Prozessen statt. Daneben, bzw. zwischen den beiden liegend, gibt es noch den sogenannten Makrokernel. Auf jeden Fall außerhalb des Kernels laufen die Anwenderprozesse, die sich der vom Kernel angebotenen Funktionen bedienen, um mit der Maschine zu Dienstag, 30. April Betriebssysteme und nebenläufige kommunizieren. 2013
Anwendugen - Prozesse und Threads
27
Betriebssystemkern (3) Aufgaben eines Kernels : • Schnittstelle zu Anwenderprogrammen (Starten, Beenden, Ein-/Ausgabe, Speicherzugriff) •Kontrolle des Zugriffs auf Prozessor, Geräte, Speicher (Scheduler, Gerätetreiber, Speicherschutz). Möglichst alleiniger Zugriff des Kernels auf diese Ressourcen. •Verteilung der Ressourcen, etwa der Prozessorzeit(en) (bzw. der Prozessoren) auf die Anwenderprogramme •Strukturierung der Ressourcen, etwa Abbildung von Dateisystemen auf blockorientierte Geräte wie Festplatten, Netzwerkprotokoll-Stack auf Netzwerkkarten. •Auflösung von Zugriffskonflikten, etwa Verriegelung bei Mehrprozessorsystemen, Warteschlangen bei knappen Ressourcen •Virtualisierung der Ressourcen (Prozessor: Prozesse, Festplatte: Dateien, Netzwerkkarte: z. B. Sockets, Speicher: virtueller Speicher, Geräte: Spezialdateien) •Überwachung von Zugriffsrechten auf Dateien und Geräte bei Mehrbenutzersystemen Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
28
Betriebssystemkern (4) Schichten eines Unix Betriebssystems User Interface
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
29
Betriebssystemkern (5) Kernel Mode – User Mode Kernel und user space sind unterschiedliche Teile des Adressraumes. User space ist reservierter Bereich für applikationen (jede einen eigenen Bereich). Kernel space ist auch ein reservierter Bereich, jedoch nur einer für alle Anwendungen, die dort nicht schreiben können. Nur das Betriebssystem kann den Prozessor auf kernel mode umschalten und auf diesen Bereich zugreifen... Anwendungen laufen dagegen normalerweise nur im user mode des prozessors, und verwenden damit einen eingeschränkten Befehlssatz ist. Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
30
Betriebssystemkern (6) CPU- Betriebsarten: Kernel Mode – User Mode Das Programmstatuswort der CPU enthält die aktuelle Betriebsart: kernel mode, user mode Damit wird ein Schutzsystem realisiert kernel mode: - privilegierte Betriebsart (nur für Betriebssystem) - alle Instruktionen sind erlaubt, inbes. IO auf Hardware user mode:- nicht privilegierte Betriebsart - nicht alle Instruktionen sind erlaubt (z.B. Zugriff auf Ein-/Ausgabe) - nicht alle Register dürfen verändert werden (z.B. Register für Speicherkonfiguration) Umschaltung in Kernmodus: mittels Interrupt (über SW oder HW ausgelöst) Umschaltung in Benutzermodus: mittels Maschinenbefehl bzw. PSWModifikation Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
31
Realisierung von Threads im Kern(2) Kern hat Thread-Tabelle, die alle Ein Thread Paket, Threads im System verwaltet verwaltet vom Kern Thread-Tabelle enthält Informationen über Register, Zustand... der einzelnen Threads Alle Aufrufe, die blockieren können, sind als Systemaufrufe realisiert mit höheren Kosten als Aufrufe im Laufzeitsystem – aber: wenn ein Thread blockiert, hat der Kern die Möglichkeit, einen anderen (prozesseigegnen oder fremden) Thread zu starten Fazit: flexibel, aber teuer Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
32
Hybride Implementierung
Multiplexen von Benutzer-Level-Threads in Kern-Threads = Versuch, die Vorteile beider Implementierungen zu verbinden Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
33
Scheduler Activations • Ziel: – Verbindung der Funktionalität von Kern-Threads mit der Performance von Benutzeradressraum Threads • Vermeiden von unnötigen user/kernel Umschaltungen • Kern ordnet jedem Prozess virtuelle Prozessoren zu und veranlasst das Laufzeitsystem (im Benutzeradressraum) den Prozessoren Threads zuzuordnen (geht auch bei Multiprozessorsystemen) • Grundidee: Wenn der Kern weiss, dass ein Thread durch einen blockierenden Systemaufruf oder Seitenfehler blockiert hat, benachrichtigt er das Laufzeitsystem (Upcall) Das Laufzeitsystem kann seine Threads darauf hin neu schedulen, also den gegenwärtigen Thread als blockiert markieren und einen anderen starten • Problem: Fundamental reliance on kernel (lower layer) calling procedures in user space (higher layer) Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
34
Pop-Up Threads
Erzeugen eines neuen Threads, wenn eine Nachricht eintrifft (a) bevor die Nachricht eintrifft (b) nachdem die Nachricht eintrifft Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
35
Multithreading • • • • • •
Üblich: zuerst nur ein Thread Startet weitere threads(z.B. thread_create (proc_name)) Manchmal hierarchisch, manchmal flach Wenn thread fertig: thread_exit Warten auf thread-Ende: thread_wait CPU freiwillig hergeben: thread_yield
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
36
Posix Thread Beispiel – 1 Main 1 PROGRAM ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
ForThreads
Funktionsbeschreibung: Thread Testprogramm Programm kreiert und startet mehrere Threads: - Worker wird mehrmals kreiert (Master-Worker) und gestartet. Diese Workerthreads arbeiten periodisch mit Hilfe eines Timers. Sie stoßen wiederum alle den selben Thread an - Thread2 ist der mittels pthread_cond_signal von Worker angestossene Thread, der in einer Endlosschleife mit pthread_cond_wait auf Aufträge wartet. Er muss vom Hauptprogramm mit pthread_cancel explizit beendet werden - Thread3 läuft als unabhängiger Thread und führt eine Anzahl Iterationen aus. Für ihn werden Scheduling-Parameter (Priorität) gesetzt. - Das Programm endet erst, wenn alle Threads abgearbeitet oder beendet sind. Geprüft wird dies mit pthread_join.
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
37
Posix Thread Beispiel – 2 benutzte Posix Funktionen !
! ! ! ! ! ! ! ! ! ! ! ! ! !
Functions: pthread_cond_init pthread_cond_broadcast pthread_cond_signal pthread_create pthread_join pthread_mutex_init pthread_mutex_lock pthread_mutex_unlock pthread_setschedparam
Conditionvariable erzeugen und mit Defaultwert initialisieren Alle Thread, die auf eine bestimmte Condition-Variable hören, benachrichtigen Einen Thread, der auf eine bestimmte Condition-Variable hört, benachrichtigen Einen Thread erzeugen Synchronisieren mehrerer Threads Mutexvariable erzeugen und mit Defaultwert initialisieren Mutex locken vor broadcast Mutex unlocken nach broadcast Scheduling Verfahren und Priorität für einen Thread festlegen
! !D-
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
38
Posix Thread Beispiel – 3 Datendeklaration INCLUDE 'GEN_INCL:ST(PThreads)' EXTERNAL Test_Thread1 EXTERNAL TestF_Thread2 EXTERNAL Test_Thread3 PARAMETER PTHREAD_MUTEX_DEFAULT = 0 PARAMETER anzworkers = 4 INTEGER *4 ThrCount , SchedNr INTEGER *4 INDX , IStatus INTEGER *4 ThreadStackSize /819200/ !size_t INTEGER *4 exitval RECORD /pthread_mutex_t/ SlowMutex, WeckMutex, CountMutex, RECORD /pthread_cond_t/ WeckCond, CountCond COMMON /COM_Threads/ SlowMutex, WeckMutex, CountMutex, WeckCond, 1 CountCond, ThrCount REAL *4 x /1.0/ RECORD /pthread_t/ Worker (anzworkers) RECORD /pthread_t/ Thread2 RECORD /pthread_t/ Thread3 RECORD /pthread_attr_t/s_gl_pthread_attr RECORD /pthread_attr_t/s_gl_pthread_attr2 RECORD /sched_param/schedparam
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
39
Posix Thread Beispiel – 4 Threads erzeugen ThrCount = 0 schedparam.sched_priority = 9 !PRI_FG_MIN_NP 8 - 15! CALL pthread_mutex_init(CountMutex,%VAL(PTHREAD_MUTEX_DEFAULT)) CALL pthread_mutex_init(WeckMutex,%VAL(PTHREAD_MUTEX_DEFAULT)) ! Thread Condition Varibale initialisieren IStatus = pthread_cond_init(WeckCond, ) IStatus = pthread_cond_init(CountCond,) IStatus = pthread_attr_init(s_gl_pthread_attr) IStatus = pthread_attr_init(s_gl_pthread_attr2) IStatus = pthread_attr_setstacksize(s_gl_pthread_attr, ThreadStackSize) IStatus = pthread_attr_setstacksize(s_gl_pthread_attr2, ThreadStackSize) DO INDX = 1,anzworkers ! Eine Prozedur mehrmals als Thread erzeugen (anzworkers) IStatus = pthread_create(Worker(INDX), %VAL(PTHREAD_CREATE_JOINABLE), 1 test_thread1, %VAL(Indx)) ENDDO IStatus = pthread_create(Thread2, %VAL(PTHREAD_CREATE_JOINABLE), test_thread2, %VAL(anzworker+1)) IStatus = pthread_create(Thread3, %VAL(PTHREAD_CREATE_JOINABLE), test_thread3, %VAL(anzworker+2))
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
40
Posix Thread Beispiel – 5 benachrichten und beenden ! ! Prioritäten der Threads festlegen ! IStatus = pthread_setschedparam (%VAL(Thread3.Pointer), %VAL(Sched_Other), schedparam) ! ! Mittels Broadcast alle Threads der Variante Worker wecken ! IStatus = pthread_cond_broadcast (%REF(WeckCond)) PRINT*,'alle Threads aktiviert, Main wartet noch auf Rückmeldung ' ! ! Mittels Signal Thread2 wecken ! IStatus = pthread_cond_signal(%REF(CountCond)) ! ! Ende aller Threads abwarten/oder herbeiführen ! DO INDX = 1, anzworkers IStatus = pthread_join32(%VAL(Worker(INDX).Pointer),exitval) ENDDO IStatus = pthread_join32(%VAL(Thread3.Pointer),exitval) IStatus = pthread_cancel (%VAL(Thread2.Pointer)) IStatus = pthread_join32(%VAL(Thread2.Pointer),exitval) END
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
41
Posix Thread Beispiel – 6 test_Thread1,arbeitet periodisch, terminiert selbst SUBROUTINE test_thread1(thrnum) IMPLICIT NONE ! ! Thread wird mehrfach (Anzahl= anzworkers), konkurrierend in MAIN erzeugt ! und mittels Broadcast geweckt. ! ! Verwendete Prozeduren: ! ! pthread_cond_wait Warten auf Ereignis und aufwachen des Threads mit Mutex ! pthread_cond_timedwait Warten auf Ereignis mit Timeout (verwendbar als Timer bei Threads) ! pthread_get_expiration_np Bestimmung der Ablaufzeit des Timers indem zur Systemzeit ein ! Delta in Sekunden addiert wird ! pthread_mutex_lock WeckMutex locken für pthreadcond_wait ! INCLUDE 'GEN_INCL:ST(PThreads)' INTEGER *4 ThrCount RECORD /pthread_mutex_t/ SlowMutex RECORD /pthread_mutex_t/ WeckMutex RECORD /pthread_mutex_t/ CountMutex RECORD /pthread_cond_t/ WeckCond RECORD /pthread_cond_t/ CountCond COMMON /COM_Threads/ SlowMutex, WeckMutex, CountMutex, WeckCond, 1 CountCond, ThrCount CHARACTER * 8 CTime INTEGER *4 a , thrnum, Error, INDX /0/, IStatus RECORD /PThread_TimeSpec_T/ WaitTime, ResWaitTime
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
42
Posix Thread Beispiel – 7 test_Thread1,arbeitet periodisch, terminiert selbst CALL TIME (CTime) a = %LOC(thrnum) PRINT *, a,%LOC(a), ' thread ',a,' gestartet um:',CTime,%LOC(CTime), %LOC(WaitTime.tv_sec) WaitTime.tv_sec = 4 WaitTime.tv_nsec = 0 ! Synchronisierung der Threads mit dem Hauptprogramm mittels einer ! Condition Variablen IStatus = pthread_mutex_lock(WeckMutex) IStatus = pthread_cond_wait(WeckCond, WeckMutex) IStatus = pthread_mutex_unlock (WeckMutex) ! ! Timer definieren ! IStatus = pthread_get_expiration_np (%REF(waittime),%REF(reswaittime))
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
43
Posix Thread Beispiel – 8 test_Thread1,arbeitet periodisch, terminiert selbst DO INDX = 1,4 IStatus = pthread_mutex_lock(CountMutex) thrCount = thrCount + 1 IStatus = pthread_mutex_unlock(CountMutex) IStatus = pthread_mutex_lock (WeckMutex) IStatus = pthread_cond_timedwait(WeckCond, WeckMutex, reswaittime) Error = pthread_mutex_unlock (WeckMutex) CALL TIME (CTime) IF (IStatus .EQ. 0)THEN PRINT*,a,%LOC(a),' ', IStatus,' über Mutex/Condition rausgekommen' ELSEIF (IStatus .EQ. ETIMEDOUT) THEN PRINT*,a,%LOC(a),' Timer abgelaufen thread ',a,' Lauf:',INDX,' ',CTime ELSE PRINT*,a,%LOC(a),' Ende von Condition Wait Lauf ',INDX,' um',CTime,' Fehler ', IStatus ENDIF IStatus = pthread_get_expiration_np (%REF(waittime),%REF(reswaittime)) IStatus = pthread_cond_signal(CountCond) ! Signal an einen anderen Thread, einen anderen Thread anstoßen ENDDO PRINT*,a,%LOC(a), ' Fertig....thread',a RETURN END
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
44
Posix Thread Beispiel – 9 Endlos Thread, wird von main gestoppt SUBROUTINE test_thread2(thrnum) IMPLICIT NONE ! ! Endlos-Thread sitzt in ConditionWait und wird von anderen Threads ! via SIGNAL geweckt um dann irgendeinen Unsinn zu machen ! Zusätzlich: Sperren und Freigeben einer globalen Variablen mittels ! Mutex Lock und Unlock ! Beenden des Endlos-Threads via PTHREAD_CANCEL in MAIN ! ! Verwendete Prozeduren: ! ! pthread_mutex_init Initialisierung der Mutexvariablen ! für pthread_cond_wait ! pthread_cond_wait Aufwachen des Threads mit Mutex ! pthread_mutex_lock WeckMutex locken für pthread_cond_wait ! pthread_mutex_unlock WeckMutex freigeben nach ! pthread_cond_wait INCLUDE 'GEN_INCL:ST(PThreads)' INTEGER *4 ThrCount RECORD /pthread_mutex_t/ SlowMutex RECORD /pthread_mutex_t/ WeckMutex RECORD /pthread_mutex_t/ CountMutex RECORD /pthread_cond_t/ WeckCond RECORD /pthread_cond_t/ CountCond COMMON /COM_Threads/ SlowMutex, WeckMutex, CountMutex, WeckCond, 1 CountCond, ThrCount RECORD /pthread_mutex_t/ WaitMutex
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
45
Posix Thread Beispiel – 10 Endlos Thread, wird von main gestoppt CHARACTER * 8 CTime REAL *4 count /3.0/, x, y INTEGER *4 a, thrnum, I, IStatus IStatus = pthread_mutex_init(WaitMutex,) a = %LOC(thrnum) IStatus = 0 DO WHILE (IStatus .EQ. 0) x = SIN(count) Count = Count + 1 CALL Time (CTime) IStatus = pthread_mutex_lock(WaitMutex) IStatus = pthread_cond_wait(CountCond, WaitMutex) IStatus = pthread_mutex_unlock(WaitMutex) ! Bereich der globalen Variablen thrcount schuetzen IStatus = pthread_mutex_lock(CountMutex) thrCount = INT(Count) + 1 DO I =2,3 y = y+(y*(i+1)/(i-1)) ENDDO PRINT*,a,' y in Thread Typ 2',y PRINT*,a,' Absolute Anzahl in Thread Typ 2 ',thrcount IStatus = pthread_mutex_unlock(CountMutex) ENDDO RETURN END
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
46
Posix Thread Beispiel – 11 test_thread3 - 1 SUBROUTINE test_thread3 (thrnum) IMPLICIT NONE ! ! Thread wird in MAIN gestartet und führt Berechnungen mit ! vielen Iterationsschritten durch. Getestet (demontriert) wird die ! Prioriätssteuerung (Scheduling) dieses Threads im Verhältnis ! zu den konkurrierenden Threads. ! INCLUDE 'GEN_INCL:ST(PThreads)' LOGICAL *4 Thread_Hold INTEGER *4 ThrCount RECORD /pthread_mutex_t/ SlowMutex RECORD /pthread_mutex_t/ WeckMutex RECORD /pthread_mutex_t/ CountMutex RECORD /pthread_cond_t/ WeckCond RECORD /pthread_cond_t/ CountCond COMMON /COM_Threads/ SlowMutex, WeckMutex, CountMutex, WeckCond, 1 CountCond, ThrCount CHARACTER *8 CTime REAL *4 x REAL *4 y /1.0/ INTEGER *4 a INTEGER *4 count1 /1/ INTEGER *4 count /3/ INTEGER *4 I INTEGER *4 thrnum
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
47
Posix Thread Beispiel – 12 test_thread3 - 2 a = %LOC(thrnum) CALL TIME (CTime) PRINT *, a,' thread ',a,' gestartet um:',CTime DO count = 1, 999999 y = 1.0 x = sin(float(count)) DO I =3, 5 y = y+(y*(i+1)/(i)) ENDDO IF(MOD (count,10000) .EQ. 0) THEN PRINT*,a,' x = sin(float(count))',x,' count ',count PRINT*,a,' y in Thread Typ 3 ',y ENDIF ENDDO PRINT*,a,' y in Thread Typ 3 ',y PRINT*,a,' Fertig!..thread ',a RETURN END
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
48
Singlethread-Programme multithreadfähig machen (1) Konflikte zwischen Threads beim Gebrauch globaler Variablen
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
49
Singlethread-Programme multithreadfähig machen (2) Threads können private globale Variablen haben
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
50
Interprozesskommunikation IPC • Weil Prozesse vom Betriebssystem gegenseitig von einander geschützt werden (Speicherschutz !), braucht man eine Interprozesskommunikationen, falls Prozesse untereinander kommunizieren, aufeinander warten oder Daten und Ressourcen austauschen müssen. • Typische Fälle dafür sind: – Mehrere Prozesse müssen spezielle Daten gemeinsam verwenden. – Die Prozesse sind untereinander abhängig und müssen aufeinander warten. – Daten müssen von einem Prozess zu einem anderen weitergereicht werden. – Die Verwendung von Systemressourcen muss koordiniert werden
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
51
IPC – Techniken unter Linux Entnommen dem openbook von Galileo unter: http://openbook.galileocomputing.de/linux_unix_programmierung/Kap09000.htm#RxxKap09000040002B71F02D10D
• • • • • • • • •
Namenlose Pipes Benannte Pipes (FIFO Pipes) Message Queue (Nachrichtenspeicher) Semaphore Shared Memory (gemeinsamer Speicher) STREAMS Sockets Lock Files (Sperrdateien) Datei Sperren (Record Locking)
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
52
IPC – Techniken unter Linux Namenlose Pipes • Pipes, wie auch FIFOs (named Pipes), sind die einzigen beiden IPCs, die garantiert auf jedem System vorhanden sind. • Eine Pipe ist ein unidirektionaler Kommunikationskanal zwischen zwei verwandten Prozessen • $ ps ax | less startet in der Shell zwei Prozesse. Einer führt das Kommando ps ax aus und schreibt das Ergebnis an die Standardausgabe. Durch die Pipe (|) wird allerdings diese Standardausgabe an den Prozess less weitergeleitet. less liest hierbei die Daten von der Standardeingabe ein und gibt aus, was ihm das Kommando ps durch die Pipe zuschickt Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
53
IPC – Techniken unter Linux -Pipes • Wenn Daten in beide Richtungen ausgetauscht werden, muss eine zweite Pipe dazu verwendet werden. Eine Pipe ist wie ein Rohr, wo Daten in die eine Seite (Prozess A) hineingesteckt werden und bei Prozess B wieder herauskommen. • Eine Pipe dient außer zur Kommunikation zwischen zwei Prozessen zur Flusskontrolle, weil eine Pipe nur eine bestimmte Menge an Daten aufnehmen kann. Ist die Pipe voll, wird ein Prozess mindestens so lange angehalten, bis mindestens ein Byte aus der vollen Pipe gelesen wurde und Platz vorhanden ist, um die Pipe wieder mit Daten zu befüllen. Andersherum: ist die Pipe leer, wird der lesende Prozess so lange angehalten, bis der schreibende Prozess etwas in diese Pipe schickt. Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
54
IPC – Techniken unter Linux -Pipes • Es gibt also eine Schreibseite und eine Leseseite bei einer Pipe. Somit ist also nur eine Kommunikation in einer Richtung möglich (half-duplex):
Eigenschaften von elementaren E/A-Funktionen bei Pipes •
read() – liest Daten vom Ende des Puffers der Pipe, entweder –
synchron (blockierend), bis sich genügend Daten in der Pipe befinden. Schreibt kein Prozess in die Pipe, blockiert read() so lange, bis der schreibende Prozess den Systemaufruf close() aufruft. Dieses Blockieren von read() eignet sich zum Synchronisieren von Prozessen.
oder –
asynchron (nicht blockierend) , indem mit der Funktion fcntl() das Flag O_NONBLOCK oder O_NDELAY gesetzt wird. Ist die Pipe fürs Schreiben geöffnet worden, aber momentan leer, liefert read() 0 (nicht EOF) zurück
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
55
IPC – Techniken unter Linux -Pipes •
write() schreibt die Daten immer ans Ende des Pipe-Puffers, entweder . –
synchron (blockierend): Ist die Pipe voll, wird der schreibende Prozess so lange blockiert, bis wieder genügend Platz zum Schreiben vorhanden ist
oder –
•
asynchron (nicht blockierend), indem mit der Funktion fcntl() das Flag O_NONBLOCK oder O_NDELAY gesetzt wird. Bei vollem Puffer liefert der schreibende Prozess 0 zurück..
Meistens betreibt man eine Pipe blockierend. Ein Schreiben innerhalb der PIPE_BUF-Grenze ist atomar, kein anderer Prozess kann dieses Schreiben unterbrechen und selbst in die Pipe schreiben. Versucht ein Prozess, in eine Pipe zu schreiben, die noch von keinem anderen Prozess zum Lesen geöffnet wurde, wird dem Prozess das Signal SIGPIPE (broken pipe) gesendet, was standardmäßig den Abbruch des schreibenden Prozesses bedeutet.
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
56
IPC – Techniken unter Linux Benannte Pipes • Mit Pipes können nur miteinander verwandte Prozesse (fork()) kommunizieren. Mit FIFOs (benannten Pipes) kann man mit einem völlig fremden Prozess kommunizieren, da solche Pipes über einen Dateinamen angesprochen werden können.
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
57
IPC – Techniken unter Linux Benannte Pipes - ein Beispiel • • • • • • • • • • • • •
Auf der Shell lässt sich ein FIFO folgendermaßen erstellen: $ mkfifo fifo1 Bei einem Blick ins aktuelle Arbeitsverzeichnis finden Sie das FIFO unter folgendem Eintrag: $ ls -l prw-r--r-- 1 tot users 0 2003–12–07 10:53 fifo1 Am p am Anfang erkennen Sie das FIFO. Sie könnten jetzt etwas in das FIFO schreiben: [tty1] $ echo Der erste Eintrag in das FIFO > fifo1 [tty2] $ echo Der zweite Eintrag in das FIFO > fifo1 Beide Dialogstationen blockieren im Augenblick und warten, bis die Daten im FIFO ausgelesen werden. Wir öffnen eine dritte Konsole und lesen ihn aus: [tty3] $ cat fifo1 Der zweite Eintrag in das FIFO Der erste Eintrag in das FIFO
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
58
IPC – Techniken unter Linux Benannte Pipes - Kommunikationsmodell eines FIFO (First In - First Out)
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
59
IPC – Techniken unter Linux Message Queue (Nachrichtenspeicher) ist ein Mechanismus zum Austausch von Nachrichten zwischen Prozessen. Die Nachrichten werden dabei von einem Prozess an einen Speicher (der Message Queue = Nachrichtenschlange) geschickt und können dort von einem anderen Prozess abgeholt werden. • • • •
Größe und Anzahl der Nachrichten werden vom System festgelegt. Die Nachricht selbst besteht aus einem Text und einem Nachrichtentyp. Die Nachrichten werden in der Reihenfolge, in der diese eintreffen, auch wieder ausgelesen. Fordert ein Prozess eine Nachricht an, so kann über eine Option angegeben werden, dass dieser entweder so lange angehalten wird, bis eine Nachricht eingeht, oder sofort zur Programmausführung zurückkehrt und eventuell einen Fehlercode ausgibt.
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
60
IPC – Techniken unter Linux Message Queue
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
61
IPC – Techniken unter Linux Shared Memory • Mehrere Prozesse können auf einen gemeinsamen Datenspeicherbereich zugreifen. 1. Ein Prozess muss diesen gemeinsamen Datenspeicher anlegen. 2.
Prozesse, die ebenfalls darauf zugreifen sollen, werden mit diesem Datenspeicher bekannt gemacht, indem der Speicherbereich im Adressraum der entsprechenden Prozesse eingefügt wird. Ebenfalls muss hierbei den Prozessen mitgeteilt werden, wie diese auf den Speicherbereich zugreifen können (lesend/schreibend).
• Leider wurde mit dem Shared Memory IPC keine explizite Synchronisation zur Verfügung gestellt, weshalb man diese Kontrolle selbst noch mit z. B. Sperren oder Semaphoren herstellen muss. Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
62
IPC – Techniken unter Linux Sockets • Sockets wurden im Berkeley-UNIX-System (BSD) als Kommunikation zwischen Prozessen auf verschiedenen Rechnern über ein Netzwerk eingeführt. Sockets können zur Kommunikation verschiedenste Protokolle benutzen, z. B. TCP/IP, UDP/IP oder UNIX Domain Sockets.
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
63
Interprozess Kommunikation IPC Race Conditions – Wettlaufsituationen Was passiert, wenn zwei Prozesse auf gemeinsam genutzten Speicher gleichzeitig zugreifen wollen? Beispiel Druckerspooler Prozess A liest in = 7 A wird unterbrochen Prozess B liest in = 7 B trägt Dateinamen an Stelle 7 und aktualisiert in auf 8 A wird aktiviert und trägt ebenfalls den Dateinamen auf Stelle 7. Datei von B wird nicht Dienstag, 30. April Betriebssysteme und nebenläufige gedruckt 2013 Anwendugen - Prozesse und Threads
64
IPC - Race Conditions –Wettlaufsituationen • Situationen, in denen zwei oder mehr Prozesse einen gemeinsamen Speicher lesen oder beschreiben und das Endergebnis davon abhängt, wer wann genau läuft, werden Race Conditions genannt. • Programme, die Race Conditions enthalten, zu debuggen, macht keinen Spaß, weil Abläufe nicht reproduzierbar sind. Sie müssen vermieden werden!
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
65
IPC - Kritische Abschnitte (1) Die Teile des Programms, in denen auf gemeinsam genutzten Speicher (Resourcen) zugegriffen wird, nennt man kritische Region oder kritischer Abschnitt •
Keine zwei Prozesse dürfen gleichzeitig in ihren kritischen Bereichen sein Es dürfen keine Annahmen über Anzahl und Geschwindigkeiten von CPUs gemacht werden Kein Prozess, der außerhalb seines kritischen Bereichs läuft, darf andere Prozesse blockieren Kein Prozess sollte ewig darauf warten müssen, in seine kritische Region einzutreten Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
66
IPC - Kritische Abschnitte (2)
• Wechselseitiger Ausschluss (Mutual exclusion) unter Verwendung von kritischen Regionen Dienstag, 30. April Betriebssysteme und nebenläufige 2013
Anwendugen - Prozesse und Threads
67
IPC - Wechselseitiger Ausschluss durch aktives Warten - Unterbrechungen ausschalten Einfachste Möglichkeit: jeder Prozess kann die Interruptbehandlung im Prozessor ausschalten, wenn er in seinen kritischen Bereich eintritt. -> Schedular kann Prozess nicht unterbrechen – keine Raceconditions - Problem gelöst ! Aber: Was ist , wenn der Prozess nachher die Interruptbehandlung nicht wieder aktiviert?
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
68
IPC - Wechselseitiger Ausschluss durch aktives Warten - Variablen sperren Softwarelösung: es wird eine gemeinsame Sperrvariable (SV) beutzt. Ist SV 0, darf ein Prozess den Bereich betreten, zuvor setzt er SV 1. Notwendige Schritte: 1. SV aus dem Speicher laden 2. SV auf null testen 3. wenn nicht, weiter bei 1. 4. SV auf 1 setzten 5. kritischen Bereich betreten Angenommen, SV = 0. Was passiert, wenn der Scedular P1 im Schritt 2 unterbricht und P2 mit Schritt eins beginnt ?
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
69
IPC - Wechselseitiger Ausschluss durch aktives Warten - Strikter Wechsel
(a) Process 0. a betritt, wenn turn = 0
(b) Process 1. b betritt, wenn turn = 1
"Kein Prozess, der außerhalb seines kritischen Bereichs läuft, darf andere Prozesse blockieren" kann hier verletzt werden ! Betriebssysteme und nebenläufige Dienstag, 30. April 2013
Anwendugen - Prozesse und Threads
70
IPC - Wechselseitiger Ausschluss durch aktives Warten - Petersons Lösung
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
71
IPC - Wechselseitiger Ausschluss durch aktives Warten - Petersons Lösung Angenommen, beide Prozesse rufen enter_region beinahe gleichzeitig auf: Beide speichern ihre Prozessnummern in turn Wer zuletzt kam gewinnt. Das erste Ergebnis geht verloren. z.B. turn = 1: Wenn beide Prozesse zur while Schleife kommen, führt sie Prozess 0 null mal aus und betritt die kritische Region. Prozess 1 geht in die Schleife und betritt seine kritische Region so lange nicht, bis Prozess 0 seine kritische Region verlässt.
Petersons Lösung für wechselseitigen Ausschluss Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
72
IPC - Wechselseitiger Ausschluss durch aktives Warten - TSL Anweisung
Eintreten und Verlassen der kritischen Region unter Verwendung der TSL Anweisung Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
73
IPC - Wechselseitiger Ausschluss durch aktives Warten - Nachteile
Nachteile des aktiven Wartens: • Warten verbraucht CPU Zeit • Ist ein Process mit sehr hoher Priorität in enter_region, kommt er aus der while Schleife nicht mehr heraus, wenn ein Prozess mit sehr niedriger Priorität in leave_region einfach nie dran kommt Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
74
IPC - Sleep and Wakeup ErzeugerVerbraucher Problem Zwei Prozesse benutzen einen gemeisamen allgemeinen Puffer mit fester Größe. Der Erzeuger legt Informationen hinein, der Verbraucher nimmt sie heraus. Synchronisation ist notwendig
bei Aufruf von sleep blockiert der Schedular den thread nach Aufruf von wakeup setzt ihn der Schedular wieder auf laufbereit
Dienstag, 30. April 2013
Erzeuger-Verbraucher Problem Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
75
IPC - Sleep and Wakeup - Ermitteln Sie die Race Condition !
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
76
IPC-Sleep and Wakeup –Race Condition Beispiel: 1. Puffer ist leer 2. consumer hat gerade count gelesen (= = 0) und will sleep aufrufen. 3. Schedular unterbricht consumer 4. Schedular startet producer 5. producer fügt Nachricht ein, erhöht count um 1 6. producer merkt, dass count = 1 ist und weckt den consumer, der offensichtlich schlafen muss. consumer schläft aber noch gar nicht, Weckruf geht verloren. 7. Schedular startet wieder consumer 8. consumer prüft den count, den er vorher gelesen hat (==0) und geht schlafen 9. Irgendwann erzeugt der producer neuen Eintrag und geht auch Problem ist nur, dass ein Wecksignal verloren gehen kann! schlafen. Dienstag, 30. April Betriebssysteme und nebenläufige 10. Jetzt schlafen beide für immer ! 2013
Anwendugen - Prozesse und Threads
77
IPC - Semaphoren : Erzeuger-Verbraucher Problem
Dienstag, 30. April 2013
Die down Operation eines Semaphors prüft, ob der Wert größer 0 ist. S > 0, down erniedrigt den Wert um eins (z.B. um einen gespeicherten Weckruf zu verbrauchen) und macht einfach weiter S = 0, Prozess oder Thread wird sofort schlafen gelegt down ist atomare (nicht unterbrechbare) Operation und verhindert deshalb Race Conditions up und down werden in der Regel als Systemaufrufe realisiert, bei denen das BS alle Unterbrechungen ausschaltet, solange es die Semaphore überprüft, sie aktualisiert und den Prozess ggf. schlafen legt
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
78
IPC Semaphoren : Erzeuger-Verbraucher Problem
Die up Operation erhöht den Wert um eins gibt es schlafende Prozesse ( in der Operation down) wird einer von ihnen geweckt, dekrementiert das Semaphore wieder auf 0 und kommt aus dem down zurück. Somit bleibt nach einem up an ein Semaphore, auf das schlafende Prozesse warten, der Wert des Semaphores immer noch auf 0, aber es gibt einen Prozess weniger, der wegen des Semaphores schläft. up ist ebenfalls eine atomare Operation
.
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
79
IPC - Semaphoren
Dienstag, 30. April 2013
Die Mutex Semaphoren werden für gegenseitigen Ausschluss verwendet. Sie schützen den Puffer vor gleichzeitigem Lesen und Schreiben. Full und empty sind Synchronisationssemaphoren. Empty hält den producer an, wenn der Puffer voll ist. Full hält den Verbraucher an, wenn der Puffer leer ist kein wechselseitiger Ausschluss !
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
80
IPC - Mutexes Realisierung von mutex_lock und mutex_unlock
vereinfachte Semaphore (kann nicht zählen, binäre Semaphore) dient dem gegenseitigen Ausschluss, Schutz für kritischen Bereich Ähnlich wie Folie Wechselseitiger Ausschluss durch aktives Warten (5) aber: thread_yield gibt die CPU wieder frei, kein aktives Warten Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
81
IPC - Probleme mit Semaphoren Angenommen im Code des producer steht: down (&mutex); down (&empty); insert_item(item); ... Angenommen: der consumer läuft nicht dann: producer betritt 100 mal den kritischen Bereich, dekrementiert empty auf null und geht deshalb im kritischen Bereich schlafen. Jetzt kommt der consumer und kann den kritischen Bereich nicht betreten, legt sich auch schlafen Producer wartet auf up(&empty) des consumers und der consumer wartet auf up(&mutex) des producers. Klassischer Fall eines Deadlock Programmierfehler können leicht passieren Deshalb Monitore! Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
82
IPC - Monitor (1) Realisiert ein höherstufiges Synchronisationsprinzip als Semaphore Ist eine Sammlung von Prozeduren, Variablen und Datenstrukturen. Prozeduren können aufgerufen, deren Variablen aber nicht von außen geändert werden Definitionsgemäß darf und kann immer nur ein Prozess im Monitor aktiv sein Monitor ist ein Programmiersprachenkonstrukt, das der Compiler speziell behandlen kann Der Compiler (nicht der Programmierer) realisiert den wechselseitigen Ausschluß
Beispiel eines Monitors in Pidgin Pascal Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
83
IPC - Monitor (2)
•
Outline of producer-consumer problem with monitors only one monitor procedure active at one time, buffer has N slots Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
84
IPC - Monitors (3)
Dienstag, 30. April Betriebssysteme und nebenläufige Solution to producer-consumer problem in Java (part 1) 2013 Anwendugen - Prozesse und Threads
85
IPC - Monitors (4)
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
86
IPC – Möglichkeiten
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
87
Message Passing
The producer-consumer Dienstag, 30. April Betriebssystemeproblem und nebenläufige with N messages 2013
Anwendugen - Prozesse und Threads
88
Barriers
• Use of a barrier – processes approaching a barrier – all processes but one blocked at barrier Dienstag, 30. April Betriebssysteme und nebenläufige 2013 – last process Anwendugen und Threads arrives,- Prozesse all are let through
89
Dining Philosophers (1) • • • •
Philosophers eat/think Eating needs 2 forks Pick one fork at a time How to prevent deadlock
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
90
Dining Philosophers (2)
A nonsolution to the dining philosophers problem Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
91
Dining Philosophers (3)
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
Solution to dining philosophers problem (part 1)
92
Dining Philosophers (4)
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
Solution to dining philosophers problem (part 2)
93
The Readers and Writers Problem
Betriebssysteme und nebenläufige A solution to the readers and writers problem Anwendugen - Prozesse und Threads
Dienstag, 30. April 2013
94
The Sleeping Barber Problem (1)
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
95
The Sleeping Barber Problem (2)
Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Solution to sleeping barber problem. Anwendugen - Prozesse und Threads
96
Scheduling Introduction to Scheduling (1)
• Bursts of CPU usage alternate with periods of I/O wait – a CPU-bound process – an I/O bound process Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
97
Introduction to Scheduling (2)
Dienstag, 30. April 2013
Scheduling Algorithm Goals Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
98
Scheduling in Batch Systems (1)
An example of shortest job first scheduling Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
99
Scheduling in Batch Systems (2)
Dienstag, 30. April 2013
Three levelundscheduling Betriebssysteme nebenläufige Anwendugen - Prozesse und Threads
100
Scheduling in Interactive Systems (1)
• Round Robin Scheduling – list of runnable processes –Dienstag, list 30. ofApril runnable processes after B uses up its quantum Betriebssysteme und nebenläufige 2013
Anwendugen - Prozesse und Threads
101
Scheduling in Interactive Systems (2)
A scheduling algorithm with four priority classes Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
102
Scheduling in Real-Time Systems
Schedulable real-time system • Given – m periodic events – event i occurs within period Pi and requires Ci seconds
• Then the load can only be handled if m
Dienstag, 30. April 2013
Ci 1 i 1 Pi
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
103
Policy versus Mechanism • Separate what is allowed to be done with how it is done – a process knows which of its children threads are important and need priority
• Scheduling algorithm parameterized – mechanism in the kernel
• Parameters filled in by user processes – policy set by user process Dienstag, 30. April 2013
Betriebssysteme und nebenläufige Anwendugen - Prozesse und Threads
104
Thread Scheduling (1)
Possible scheduling of user-level threads • 50-msec process quantum Dienstag,•30. April Betriebssysteme und nebenläufige threads run 5 msec/CPU burst 2013 Anwendugen - Prozesse und Threads
105
Thread Scheduling (2)
Possible scheduling of kernel-level threads • 50-msec process quantum threads runBetriebssysteme 5 msec/CPU burst Dienstag,•30. April und nebenläufige 2013
Anwendugen - Prozesse und Threads
106
