Upload
buitruc
View
215
Download
0
Embed Size (px)
Citation preview
Prozessverwaltung
Ein Prozess ist das zentrale Konzept in jedem
Betriebssystem.
Wir machen die Annahme, dass jeder Prozess ein Thread
innerhalb des Betriebssystems zugeordnet bekommt.
Prozesse
Stapel
Programm
BSS
Daten
Prozess im Speicher
ProzessabbildParameter von Funktionen,return-Adressen und lokale Variablen werden hier gespeichert.
Daten, die dynamisch erzeugt werden, während der Programmausführung
Statische Datenstrukturen, die am Anfang der Programmausführung erzeugt werden.
Um einen Prozesswechsel zu ermöglichen, beinhaltet ein Prozess neben dem Programm zusätzliche Information.
"Block started by symbol"
Prozesse
Für die Prozesssteuerung verwendet das
Betriebssystem eine Prozesstabelle. Dort
befindet sich ein Eintrag pro Prozess.
Dieser Eintrag wird oft
Prozesskontrollblock genannt.
PCB Process Control Block
Der Prozesskontrollblock stellt die wichtigste Datenstruktur des Betriebssystems dar.
Stapel
Programm
BSS
Daten
Prozess im Speicher
Prozessabbild
Prozesstabelle Eine Prozesstabelle enthält einen Eintrag pro Prozess.
Jeder Eintrag enthält aktuelle Informationen über den Zustand der Prozesse.
Beispiel: Prozesskontrollblock (PCB)
• Prozess ID (PID)
• Prozesszustand
• Befehlszähler
• CPU Register
• CPU Scheduling-Information
• Prozessverwaltungsinformation
• Speicherverwaltungsinformation
• Eingabe/Ausgabe Statusinformation
Prozesskontrollblock
Prozesszustand
PCB Process Control Block
aktiv, bereit, wartend, blockiert usw.
Befehlszähler Adresse des nächsten abzurufenden Befehls
CPU-Register Programmstatuswort, Stapelzeiger, Indexregister, allgemeine Register, usw.
Ablaufplanung Information
Prozesspriorität, Wartezeit, Ereignisse, auf die der Prozess wartet, usw.
Ressourcennutzung Benutzte CPU-Zeit, Startzeit des Prozesses, CPU-Zeit der Kindprozesse, usw.
I/O Status Information
I/O Geräte-Reservierung, Arbeitsverzeichnis, Geöffnete Dateien, Benutzer-ID, usw.
Information über Speicherverwaltung
Speichergrenzen, Seitentabellen der Segmenttabellen, usw.
Allgemeine Struktur der Betriebssystemtabellen
Prozesse
Speicher
I/O-Geräte
Dateien
Betriebssystemtabellen
Prozess 1
Prozess 2
.
.
.Prozess
nSpeichertabellen
Gerätetabellen
Dateitabellen
Prozesstabelle
PCB1
PCB2
PCB3
.
.
.PCBn
Prozessabbild
Prozess 1
Prozess 2
.
.
.Prozess
n
Prozesstabelle
PCB1
PCB2
PCB3
.
.
.PCBn
Stapel
Programm
Heap
Daten
ProzessabbildProzessabbild
PCB in Linux
Gundlegende Struktur ist:
task_struct
Diese Struktur beinhaltet alles, was an Information zu einem
Linux-Prozess gehört.
Beispiel: Prozesszustand
Information für den Scheduler
Information für die Speicherverwaltung
Liste der geöffneten Dateien
Zeiger auf den Vater-Prozess
Zeiger auf alle Kind-Prozesse
Prozessverwaltung in LinuxIn dem Linux-Kernel werden Prozesse mit Hilfe einer doppelt
verketteten Liste von task_struct-Strukturen verwaltet.
Prozess in Ausführung
current
struct tast_struct…
Prozessinformation
struct tast_struct…
Prozessinformation
struct tast_struct…
Prozessinformation
…
Prozessverwaltung in Linux
Einige Komponenten der task_struct-Struktur sind:
pid_t pid; // Prozess-ID
long state; // Prozesszustand
unsigned int time_slice; // Scheduling-Information
task_struct *parent; // Zeiger auf den Vater-Prozess
struct list_head children; // Liste der Kind-Prozesse
struct files_struct *files; // Liste der offenen Dateien
struct mm_struct *mm; // Adressraum des Prozesses
// usw.
SchedulerDer Scheduler regelt die zeitliche Abfolge der Verarbeitung von Tasks
oder Prozessen.
Der Scheduler ist ein besonders wichtiger Programmteil jedes Betriebssystems.
Da die Verwaltung von Prozessen besonders zeitkritisch ist, werden Scheduler in Assembler programmiert.
Scheduler
...
P1 P2 P3 Pn
Prozesse
SchedulerProzess P1
Die Ausführung von Prozess P1
wird fortgesetzt
Prozess P2
speichert Zustand von P1 in PCB1
lädt Zustand von P2 aus PCB2
Die Ausführung von Prozess P2
wird fortgesetzt
speichert Zustand von P2 in PCB2
lädt Zustand von P1 aus PCB1
Time-Interrupt oder Systemaufruf
Prozess P1
Prozesswarteschlangen
PCB5
PCB1 PCB3 PCB6 PCB2
Aktiv head
Bereitheadtail
Blockiertheadtail
PCB4 PCB7 PCB8
I/O Warteschlange
Die Prozesse wechseln zwischen verschiedenen Warteschlangen
Prozesskontrollblock
Prozessverwaltungsdiagramm
Pb1Pb2Pb3 CPU
Ein-/Ausgabe Pio3Pio2Pio1 Pio4
Zeit abgelaufen
Neue Prozesse
fork()Kindprozess
Wartet auf ein Ereignis
Ereignis kommt
Lebenszyklus eines Prozesses
RECHNENDRECHENBEREIT
Der Scheduler wählt diesen Prozess
BOCKIERT
Eingabe oder
Ausgabe vorhanden
blockiert z.B. wegen Eingabe oder Ausgabe
Ein neuer Prozess wird erzeugt
angenommenbeendet
BEENDET
Der Scheduler wählt einen anderen Prozess
Ein Prozess kann in Bezug auf seine aktuelle Aktivität verschiedene Zustände annehmen.
Lebenszyklus eines Prozesses in Pintos
THREAD_RUNNINGTHREAD_READY
Der Scheduler wählt diesen Prozess
THREAD_BLOCKED
Ein neuer Prozess wird erzeugt
angenommen beendet
THREAD_DYING
Der Scheduler wählt einen anderen Prozess
Interprozesskommunikation (IPC)
Interprozess-Kommunikation
Kommunikation über Pipes
Kommunikation über Messages-Passing
Schreibender Prozess
LesenderProzess
Daten
Warteschlange
Sender 2Sender 1 Sender 3
Empfänger
Prozesse müssen oft kommunizieren und das Betriebssystem
verwendet gemeinsame Datenstrukturen, um das zu gewährleisten.
KooperationsmodelleNachrichtenverkehr
Message passing
Gemeinsame Speicher
Shared memory
PAPA
PBPB
Kernel Kernel
share memory
message passing
message passing
message passing
Nebenläufigkeit Die ersten Konzepte sind mindestens seit 1960 durch die
Programmierung von Betriebssystemen entstanden.
Heute wird Nebenläufigkeit praktisch überall eingesetzt und nicht nur auf Betriebssystem-Ebene.
Viele moderne Anwendungen sind multithreaded.
• GUIs
• Browser
• Textverarbeitungsprogramme
• Multimedia-Anwendungen
• Server
• Datenbanken
• Client-Server-Anwendungen
• Java RMI (Remote Method Invocation) Systeme
• Moderne Betriebssystem-Kernel
Warum Threads auf Anwendungsebene?Vorteile:
- schnellere Antwortzeit
- gemeinsamer Adressraum
- effizienter Kontextwechsel
- in Multiprozessorsystemen kann echte Parallelität erreicht werden
Probleme:
Der Benutzer muss darauf achten, dass der gemeinsame Adressraum und die Anwendung von Ressourcen fehlerfrei laufen.
Synchronisationsprobleme müssen von Softwareentwicklern gelöst werden.
- Besonderes geeignet für interaktive Systeme (GUIs.)
Kritische Abschnitte
Eines der wichtigsten Ziele bei der Entwicklung von Betriebssystemen
ist es, geeignete und effiziente Synchronisationsmechanismen
anzubieten, um den wechselseitigen Ausschluss zu garantieren.
Das Vermeiden von kritischen Abschnitten reicht allein nicht aus, um
eine effiziente Ausführung von parallelen Prozessen zu garantieren.
Prof. Dr. Margarita Esponda
Kritische AbschnitteWas ist eine gute Lösung?
• Keine zwei Prozesse/Threads dürfen in ihren kritischen
Regionen sein.
• Es dürfen keine Annahmen über die Geschwindigkeit
und Anzahl der CPUs gemacht werden.
• Kein Prozess/Thread, der außerhalb seines kritischen
Abschnitts läuft, darf anderen Prozessen den Eintritt
zum kritischen Abschnitt blockieren.
• Kein Prozess darf ewig auf seinen kritischen Abschnitt
warten.
• Die Lösung soll auch bei Mehrprozessorsystemen
funktionieren.
Prof. Dr. Margarita Esponda
Lösungen für die SynchronisationsproblemeKritische Abschnitte sind die Teile des Programms, in denen auf gemeinsam benutzte Speicherbereiche bzw. Ressourcen zugegriffen werden kann.
1. Unterbrechungen ausschalten
3. Strikter Wechsel
4. Petersons Lösung
5. Die TSL- Anweisung
6. Semaphoren
7. Monitorkonzept
Verschiedene Lösungsansätze sind:
2. Variablen Sperre
1. Unterbrechungen ausschalten
Die Ausschaltung von Unterbrechungen ist ein Privileg des Betriebssystems.
Nicht geeignet als Ausschlussmechanismus für Benutzerprozesse.
disable_Interrupts();
kritischer_abschnitt();
enable_Interrupts();
- Preemptive Kernels
1. Unterbrechungen ausschalten
- Nonpreemptive Kernels
- Einfache Lösung in Einprozessorsysteme.
- Komplexer in Mehrprozessorsystem.
- Effizienzprobleme (Interrupt-Mask)
- TestAndTest- und Swap-Befehle
Eingesetzt wird in Einprozessor- und Mehrprozessor-Systeme
- verwendet in Kernel-Funktionen - und Interrupt-Handlers
Linux Version < 2.6
ab Linux 2.6, Windows NT, BSD, usw.
4. Petersons Lösung für zwei Prozessepublic class PetersonThread extends Thread {
static int turn = 0; static boolean[] ready = { false, false };
int id, other;
public PetersonThread( int id ){ this.id = id; this.other = 1-id; }
public void run() { while(true){ ready[id] = true; turn = other; while( ready[other] && turn==other ); critical_region(); ready[id]=false; noncritical_region(); } }}
1. TSL-Anweisung
Insbesondere Mehrprozessorrechner haben TSL-Anweisungen.
TSL RX, LOCK Test and Set Lock
Wenn die CPU eine TSL-Anweisung im Speicher ausführt, wird der Speicherbus gesperrt, bis er fertig ist.
Hardware-Unterstützung
1. TSL-Anweisung
Einfache Lösung für zwei Prozesse mit aktivem Warten
Um TSL-Anweisungen zu verwenden, brauchen wir eine gemeinsame Variable LOCK
enter_region:
TSL RX, LOCK
CMP RX, #0
JNE enter_region
RET
kopiere und sperre mit 1
war LOCK gleich 0?
wenn nicht, dann war es gesperrt
kritische Region wurde betreten
leave_region:
MOVE LOCK, #0
RET
schreibe 0 in LOCK
TestAndSet-Befehl
void TestAndSet( boolean *target ){ boolean svar = *target;
*target = TRUE;
return svar;}
do { while (TestAndSet(&lock));
// kritische Region
lock = FALSE; // nicht kritische Region
} while (TRUE);
Das gleiche in C
ausgedrückt.
1. XCHG-Anweisung
enter_region:
MOVE RX, #1
XCHG RX, LOCK
CMP RX, #0
JNE enter_region
RET
speichere eine 1 im Register
vertausche RX und LOCK
war LOCK gleich 0?
wenn nicht 0, in Schleife gehen
kritische Region wird betreten
XCHG-Anweisung für einfache Synchronisation zwischen zwei Prozessen mit aktivem Warten.
leave_region:
MOVE LOCK, #0
RET
schreibe 0 in LOCK
Swap-Befehlvoid Swap( boolean *a, boolean *b ){
boolean temp= *a;
*a = *b; *b= temp;
}
Das gleiche in C
ausgedrückt.
do { key = TRUE;
while ( key == TRUE )
Swap (&lock, &key); // kritische Region
lock= FALSE;
// nicht kritische Region
} while (TRUE);
Das ewige Warten wird hier nicht gelöst.
Hier werden alle Anforderungen für eine gute Lösung des kritischen Abschnitts für n Prozesse erfüllt.
do { waiting[i]= TRUE; key == TRUE; while ( waiting[i] && key ) key = TestAndSet(&lock); waiting[i] = FALSE; // kritische Region j = (i+1)%n; while ( j != i && !waiting[j] ) j = (j+1)%n; if ( j== i ) lock = FALSE; else waiting[j]= FALSE; // nicht kritische Region} while (TRUE);
boolean waiting[n] = {FALSE};boolean lock = FALSE;
Datenstrukturen
Peterson + TSL-Anweisung
Der Peterson-Algorithmus und die TSL-Lösung haben
den Nachteil, dass aktives Warten erforderlich ist.
1. CPU-Zeit Verschwendung
2. PrioritätsumkehrproblemProbleme
Prioritätsumkehrproblem
Obwohl P0 eine höhere Priorität als P1 hat, muss er
immer länger als P1 warten, um in seinen kritischen
Abschnitt eintreten zu können.
Zwei oder mehr Prozesse können mit Hilfe einfacher Signale
miteinander kooperieren.
Ein Prozess kann an einer bestimmten Stelle anhalten und
warten, bis er ein bestimmtes Signal erhält.
Schlafen und Aufwecken
Schlafen gehen, anstatt CPU-Zeit zu verschwenden.
Aber ein schlafender Prozess kann sich selber nicht aufwecken.
D.h. er braucht einen entsprechenden Partner, der ihn wieder
aufweckt.
Semaphore
Monitore
Mechanismen
Prioritäts-InvertierungPriority inversion
Task-Low Resource R
Task-High
Aktiv
Prioritäts-InvertierungPriority inversion
Task-Middle
Task-Low Resource R Task-HighAktiv Wait
Prioritäts-InvertierungPriority inversion
Task-Middle
Task-Low Resource R Task-HighWait
Aktiv
Wait
Task-Middle
Prioritäts-InvertierungPriority inversion
Task-MiddleTask-Low Resource R Task-HighWait
Aktiv
Wait
Task-Middle
Fertig
Prioritäts-InvertierungPriority inversion
Task-Low Resource R Task-HighWaitWait
Task-Middle
Task-Middle
Fertig
Prioritäts-InvertierungPriority inversion
Task-Low Resource R Task-HighWaitAktiv
Task-Middle
Task-Middle
Fertig
Prioritäts-InvertierungPriority inversion
Task-Low
Resource R Task-HighWait
Task-Middle
Task-Middle
Fertig
Prioritäts-InvertierungPriority inversion
Task-Low
Resource R Task-HighAktiv
Task-Middle
Task-Middle
Fertig
Prioritäts-InvertierungPriority inversion
Task-Low
Resource R
Task-High
Task-Middle
Task-Middle
Fertig
Task-High kommt am Ende dran oder verhungert.
Vererbung von Prioritäten
T1
T2
T3
lock R fails lock(R)
lock(R)
unlock(R)
unlock(R)
T3 blockiert T2
T1 blockiert T2 und T1
T3 bekommt die Priorität p1
T1 startet hier und hat
die höchste Priorität (p1)
T2 startet
T2 blockiert T1
Das Erzeuger-Verbraucher-Problem mit Semaphoren
Die Mensa wäre kostengünstiger, wenn jeder Student seinen Teller spült.
Es gibt nur so viele Teller wie es Sitzplätze in der Mensa gibt.
Verlässt ein Student die Mensa, stellt er seinen gespülten Teller in den Stapel zurück.
WartezimmerAlarm
Beispiel aus dem Buch von Ehses, Köhler, Riemer, Stenzel und Victor:
Semaphoren
Semaphoren sind eine der wichtigsten Datenstrukturen, die für die Synchronisation von Prozessen in fast allen Betriebssystemen zur Verfügung gestellt werden.
Semaphoren als eine Lösung für Prozesssynchronisation wurde von Edsger W. Dijkstra 1965 konzipiert.
Semaphoren haben folgende Komponenten:
- ein Zähler
- eine acquire-Operation
- eine release-Operation
Semaphoren
Der Inhalt der Semaphoren wird nur mit
Hilfe der Operationen acquire und release
verändert.
Die aquire- und release-Operationen sind
atomare Operationen, die einen Thread
eventuell wecken oder zum Schlafen schicken.
Andere Namen:
P(S) = Down(S) = Wait(S)V(S) = Up(S) = Signal(S)
Semaphore (Definition)
. . . typedef struct { int count; ThreadQueue queue; } Semaphore;
void sem_acquire ( Semaphore *sem ) { sem->count--; if (sem->count < 0) { // diesen Thread in sem->queue ablegen sleep(); } }
void sem_release ( Semaphore *sem ) { sem->count++; if (sem->count <= 0) { // ein Thread t aus sem->queue entfernen wakeup( t ); } }. . .
- Ein Semaphor kann auf einen nichtnegativen Wert
initialisiert werden.
- Wenn eine Operation eines
Semaphors begonnen
wurde, kann kein anderer
Prozess auf das Semaphor zugreifen
(atomare Aktionen).
diesen Thread blockieren.
Thread t in Liste bereiter Threads ablegen.
Implementierungsbeispiel in C
Binäres Semaphore (Definition)
. . . typedef struct { bool value; ThreadQueue queue; } Mutex;
void mutex_acquire ( Mutex *bin_sem ) { if ( bin_sem->value == true ) bin_sem->value = false; else { diesen Thread in bin_sem->queue ablegen sleep(); } }
void mutex_release ( Mutex *sem ) { if ( empty( bin_sem->queue ) { bin_sem->value = true; else { ein Thread t aus bin_sem->queue entfernen wakeup( t ); } }. . .
Semaphore
import Machine.*;public class Semaphore { private int value; private ThreadQueue waitQueue = Kernel.initThreadQueue(false);
public Semaphore( int initValue ) { value = initValue; }
public void acquire() { boolean initStatus = Machine.interrupt().disable(); if (value == 0) { waitQueue.enqueue( KThread.currentThread() ); KThread.sleep(); } else { value--; } Machine.interrupt().restore( initStatus ); }
public void release() { boolean initStatus = Machine.interrupt().disable(); KThread thread = waitQueue.dequeue(); if ( thread != null ) { thread.ready(); } else { value++; } Machine.interrupt().restore( initStatus ); }}
Mutex
mutex_lock: TSL REGISTER, MUTEX | kopiere MUTEX in REGISTER, setze MUTEX = 1 CMP REGISTER, #0 | war mutex 0? JZE ok | wenn 0, war Mutex nicht gesperrt, Rücksprung CALL thread_yield | Mutex belegt: führe anderen Thread aus JMP mutex_lock | versuche es wiederok: RET | Rücksprung; kritische Region wurde betreten
mutex_unlock: MOVE MUTEX, #0 | speichere eine 0 in Mutex RET | Rücksprung
Quelle: Tanenbaum