Upload
katrina-stuewe
View
113
Download
2
Embed Size (px)
Citation preview
Universität Rostock, Fakultät für Informatik und Elektrotechnik
Institut für Angewandte Mikroelektronik und Datentechnik
Institut für Angewandte Mikroelektronik und DatentechnikUniversität Rostock
11. April 2023
EchtzeitbetriebssystemeÜbungen
M.Sc. Alexander Nitsch, M.Sc. Michael Rethfeldt(mit freundlicher Unterstützung von Dr.-Ing. Guido Moritz)
Universität Rostock, Fakultät für Informatik und Elektrotechnik
Institut für Angewandte Mikroelektronik und Datentechnik 2
ÜbungsfahrplanNr. Beschreibung Inhalte
1 Erzeugen und Starten von Prozessen IVon Threads und Prozessen
2 Erzeugen und Starten von Prozessen II
3 Pipes & SignaleInter-Prozess-Kommunikation (IPC)
4 Messagequeues, Shared Memory
5 POSIX & Threads
Inter-Prozess-Synchronisation (IPS)6 Mutexe, Conditions & Semaphore unter POSIX
7 Synchronisationsprotokolle & DeadlocksSchedulinganalysen
8 Schedulinganalyse
Universität Rostock, Fakultät für Informatik und Elektrotechnik
Institut für Angewandte Mikroelektronik und Datentechnik 3
Übung 1 – Hello World
//////////////////////////////////////////////////////////// Veranstaltung: Echtzeitbetriebssysteme// Dozent: Dr.-Ing. Frank Golatowski// Übungsleiter: Dipl.-Ing. Guido Moritz// Übung: 1// Aufgabe: 1// Name: aufgabe1.c// Beschreibung: Hello World Ausgabe//////////////////////////////////////////////////////////#include <stdio.h>
int main(int argc, char *argv[]){
printf("Hello world!\n");}
Universität Rostock, Fakultät für Informatik und Elektrotechnik
Institut für Angewandte Mikroelektronik und Datentechnik
Übung 1 – fork()#include <stdio.h>#include <stdlib.h>
int main(void){
int status;int fork_pid;
fork_pid=fork() ;
if ( fork_pid == 0 ){
printf("* Ich bin der Sohn. *\n");exit(3);
}else if (fork_pid == -1){
printf("Aufruf von fork() gescheitert!\n");exit(2);
}wait(&status); // warten auf Ende des Sohnesprintf("wait-Status: 0x%x | 0x%x | 0x%x |\n", status, (status>>8) & 0xff, status & 0xff);return 0;
}
4
fork()fork()
fork_pid =fork_pid = fork_pid =fork_pid =
fork_pid!=0fork_pid!=0 fork_pid==0fork_pid==0
printf()printf()
exit()exit()
fork_pid!=-1fork_pid!=-1
wait()wait()
printf()printf()
Universität Rostock, Fakultät für Informatik und Elektrotechnik
Institut für Angewandte Mikroelektronik und Datentechnik 6
Übung 1 – Speicherbelegung
Vater
Code
Daten
Speicher
Code
Daten
Speicher
Daten
Daten des Vaters
Daten des Sohnes
Code beider Prozesse
Universität Rostock, Fakultät für Informatik und Elektrotechnik
Institut für Angewandte Mikroelektronik und Datentechnik 7
Übung 1 – Wieviele Söhne werden erzeugt?int main(int argc, char *argv[]){
fork();fork();
}
int main(int argc, char *argv[]){
switch ( fork() ) {case 0: printf(„Sohn erzeugt\n“);
break;default: switch ( fork() ) {
case 0: printf(„Sohn erzeugt\n“);break;default: printf(„Vater\n“);
break;}break;
}}
Universität Rostock, Fakultät für Informatik und Elektrotechnik
Institut für Angewandte Mikroelektronik und Datentechnik
Übung 1 – Wieviele Söhne werden erzeugt?
8
1. fork()1. fork()
printf()printf()
Vater
Sohn2 2. fork()2. fork()
Sohn1
2. fork()2. fork() Sohn3
ENDEENDE
printf()printf()
printf()printf()
Vater
Sohn2
Sohn11. fork()1. fork()
2. fork()2. fork()
Universität Rostock, Fakultät für Informatik und Elektrotechnik
Institut für Angewandte Mikroelektronik und Datentechnik 9
Übung 2
VaterPID=1
Sohn 1PID: 2
Sohn 2PID: 3
Sohn 3PID: 3
Sohn 4PID: 4
Sohn 5PID: 4
Sohn 6PID: 5
Frage: Kann es sein, dass PID=3 und PID=4 zweimal vergeben werden?
Universität Rostock, Fakultät für Informatik und Elektrotechnik
Institut für Angewandte Mikroelektronik und Datentechnik 10
Typischer Prozessbaum
3774 ? Ss 0:00 /usr/sbin/privoxy --user privoxy privoxy --pidfile 3779 ? Ss 0:00 /usr/sbin/sshd -o PidFile=/var/run/sshd.init.pid10341 ? Ss 0:00 \_ sshd: bj [priv] 10343 ? S 0:00 | \_ sshd: bj@pts/3
10344 pts/3 Ss+ 0:00 | \_ -bash27959 ? Ss 0:00 \_ sshd: bj [priv] 27961 ? S 0:00 \_ sshd: bj@pts/4
27962 pts/4 Ss 0:00 \_ -bash28213 pts/4 R+ 0:00 \_ ps -fax 3834 ? S 0:00 /bin/sh /usr/bin/mysqld_safe --user=mysql 4016 ? S 0:00 \_ /usr/sbin/mysqld --basedir=/usr -- 4682 ? S 0:00 /usr/lib/AntiVir/antivir --updater-daemon 4770 ? Ss 0:00 /usr/sbin/cupsd 4815 ? Ss 0:01 /usr/sbin/nscd 4835 ? Ss 0:00 /usr/sbin/smbd -D -s /etc/samba/smb.conf 4842 ? S 0:00 \_ /usr/sbin/smbd -D -s /etc/samba/smb.conf 7378 ? S 0:04 \_ /usr/sbin/smbd -D -s /etc/samba/smb.conf27995 ? S 0:00 \_ /usr/sbin/smbd -D -s /etc/samba/smb.conf
Universität Rostock, Fakultät für Informatik und Elektrotechnik
Institut für Angewandte Mikroelektronik und Datentechnik 11
Übung 2 #include <stdio.h>int main(void){int var;printf(“PID(Father)=%d, var=%d\n", getpid(), var);if ( fork() == -1 ){fprintf( stderr, "Aufruf fork() gescheitert!\n" );
}else{var++;printf(“PID=%d, var=%d\n", getpid(), var);if ( fork() == -1 ){fprintf( stderr, "Fehler beim 2. fork()!\n");
}else{var++;printf(“PID=%d, var=%d\n", getpid(), var);
}}return 0;
}
Universität Rostock, Fakultät für Informatik und Elektrotechnik
Institut für Angewandte Mikroelektronik und Datentechnik 12
Übung 2
Typische Ausgaben nach stdout
PID(Father): 5179, var=0PID=5180, var=1PID=5181, var=2PID=5180, var=2PID=5179, var=1PID=5182, var=2PID=5179, var=2
Universität Rostock, Fakultät für Informatik und Elektrotechnik
Institut für Angewandte Mikroelektronik und Datentechnik 13
Übung 2: Execl()
Vater
fork()
Vater Sohn
fork()
ExternesProgramm
Vater
Universität Rostock, Fakultät für Informatik und Elektrotechnik
Institut für Angewandte Mikroelektronik und Datentechnik 14
Übung 2: Execl
• Fork() dient der Prozessverzweigung• Execl() dient dem Starten des externen Programmes• Nebeneffekt:
– Alle Daten des Vaters werden gelöscht– Alle Filedescriptoren des Vaters werden freigegeben
• Anwendung:– Starten von Programmen, z.B. init
Universität Rostock, Fakultät für Informatik und Elektrotechnik
Institut für Angewandte Mikroelektronik und Datentechnik 15
Execl()-Parametermapping
int execl(const char *path, const char *arg, ...);
Ausführbare Datei
Execl-Parameter Argument der Main-Funktion
Anzahl der Parameter-1
argn
const char *arg argv[0]
…. argv[1]
int execl(“/bin/ls”, “ls”, “-lias”, NULL); Argument der Main-Funktion Argumente
argn 2
argv[0] ls
argv[1] -lias
Universität Rostock, Fakultät für Informatik und Elektrotechnik
Institut für Angewandte Mikroelektronik und Datentechnik 16
Übung 3
• Fork() erzeugt Kopie aller Daten des Prozesses A• Direkter Datenaustausch zwischen Prozessen nicht möglich• Ausweg: Pipe des Betriebssystems
Prozess A Prozess BBetriebssystem
Universität Rostock, Fakultät für Informatik und Elektrotechnik
Institut für Angewandte Mikroelektronik und Datentechnik 17
Übung 3
• Array aus zwei File-Descriptoren: int fd[2]• Erzeugen der Pipe mit pipe()• Vererbung von fd[2] durch fork() an Sohn• Lesen: fd[0] Schreiben: fd[1]• Schließen der korrespondierenden File-Descriptoren
– Writer schließt fd[0]– Reader schließt fd[1]
Prozess A Prozess BBetriebssystem
write(fd[1]); read(fd[0]);
Universität Rostock, Fakultät für Informatik und Elektrotechnik
Institut für Angewandte Mikroelektronik und Datentechnik 18
Übung 3Prozess A Prozess B
pipe(fd)
fork()
Initialisieren einer Pipe fd[2], File-Zähler=2
close(fd[0]) close(fd[1])Schließen des Lesedescriptors (fd[0]) und des Schreibdescriptors (fd[1]), File-Zähler=2
Erzeugen des Sohn-Prozesses, File-Zähler=4
write(fd[1]) read(fd[0])Datenaustausch über Pipe
Universität Rostock, Fakultät für Informatik und Elektrotechnik
Institut für Angewandte Mikroelektronik und Datentechnik 19
Übung 3
Idealer Programmverlauf
Unterbrochener Programmverlauf
Signal
• Signale können jederzeit auftreten
• Nebenläufige Fehlerbehandlung erfolgt in Signal-Handlern
• Behandlung des Signals, sodass Hauptprogramm fehlerfrei weiterläuft !
Signal-behandlung
Universität Rostock, Fakultät für Informatik und Elektrotechnik
Institut für Angewandte Mikroelektronik und Datentechnik 20
Übung 4
• Systemweiten eindeutigen Key erzeugen• Öffnen der Nachrichtenwarteschlange (Messagequeue) • Projektidentifier proj_id kennzeichnet Nummer der Pipe
Prozess A Prozess Bftok(…,1)ftok(…,2)msgget()msgget()msgsnd()
ftok(…,1)msgget()msgrcv();
Prozess C
Betriebssystem
Proj_id=2
ftok(…,2)msgget()msgrcv();
Proj_id=1
Universität Rostock, Fakultät für Informatik und Elektrotechnik
Institut für Angewandte Mikroelektronik und Datentechnik 21
Übung 4
void main(void){ pid_t p=getpid(); switch ( fork() ) {
case 0: printf(„The son!\n“);break;
default:
printf(„The father!\n“);printf(„pid: %d\n“,p);
break; }}
void main(void){
switch ( fork() ) { case 0: printf(„The son!\n“);
break; default: {
pid_t p=getpid();printf(„The father!\n“);printf(„pid: %d\n“,p);}break;
}}
Was ist an welcher Schreibweise günstiger?
Universität Rostock, Fakultät für Informatik und Elektrotechnik
Institut für Angewandte Mikroelektronik und Datentechnik 22
Übung 5 – Casting von Funktionszeigern
Casting notwendig: Kein Casting notwendig:
int main(int argc, char *argv[]){ … pthread_create( &thread, &attr, (void*)&thread_start, 0); …}
void thread_start(void *ptr){ return;}
int main(int argc, char *argv[]){ … pthread_create( &thread, &attr, thread_start, 0); …}
void* thread_start(void *ptr){ return 0;}
Linke Variante ist inkorrekt, da Rückgabetyp von thread_start falsch ist!
Universität Rostock, Fakultät für Informatik und Elektrotechnik
Institut für Angewandte Mikroelektronik und Datentechnik 23
Übung 5 – Typen von FunktionszeigernZeigerübergabe von Funktionen ohne typedef Zeigerübergabe von Funktionen mit typedef
#include <stdio.h>
int printme(const char *msg);void thread1(int (*function)(const char *ptr) );void thread2(int (*)(const char *ptr) );
int main(int argc, char *argv[]){
thread1(printme);thread2(printme);return 0;
}
void thread1(int (*function)(const char *ptr) ){ function("Hans im Glück\n");}
void thread2(int (*function)(const char *ptr) ){ function("Der Wolf im Schafspelz\n");}
int printme(const char *msg){ printf(msg);
return 0;}
#include <stdio.h>typedef int (*CALLBACK)(const char *ptr);int printme(const char *msg);void thread1(CALLBACK function);void thread2(CALLBACK);
int main(int argc, char *argv[]){
thread1(printme);thread2(printme);return 0;
}
void thread1(CALLBACK function){ function("Hans im Glück\n");}
void thread2(CALLBACK function){ function("Der Wolf im Schafspelz\n");}
int printme(const char *msg){ printf(msg);
return 0;}
Universität Rostock, Fakultät für Informatik und Elektrotechnik
Institut für Angewandte Mikroelektronik und Datentechnik 24
Übung 6 – Condition Variablen
Aktives Warten Warten mit Conditionvariablen
void* reader_function(void *ptr){ char a=0; while( a!= 'q' ) { pthread_mutex_lock( &mutex ); if ( buffer_has_item == 1) { a=buffer; if ( a != 'q' ) consume_item(a,count); buffer_has_item = 0; } pthread_mutex_unlock( &mutex ); } return 0;}
void* reader_function(void *ptr){ char a=0; while( a!= 'q' ) { pthread_mutex_lock( &mutex ); while ( buffer_has_item != 1) pthread_cond_wait(
&cond_buffer_full, &mutex); a=buffer; buffer_has_item = 0; pthread_cond_signal( &cond_buffer_empty); pthread_mutex_unlock( &mutex ); } return 0;}
Universität Rostock, Fakultät für Informatik und Elektrotechnik
Institut für Angewandte Mikroelektronik und Datentechnik 25
Übung 7 – Deadlock
0 105 15 20
P2
P12
1 2
1
• Zwei Prozesse betreten in unterschiedlicher Reihenfolge zwei kritische Abschnitte
• Kritischer Punkt: Threadumschaltung, wenn einer der Threads in einem kritischen Abschnitt ist DEADLOCK
Universität Rostock, Fakultät für Informatik und Elektrotechnik
Institut für Angewandte Mikroelektronik und Datentechnik 26
Übung 7 – Prioritäteninversion
0 50
PL
PH
100
• Ein höher priorisierter Thread wird durch einen niedriger priorisierten Thread unterbrochen.
• Bezeichnung: Direct Blocking
Universität Rostock, Fakultät für Informatik und Elektrotechnik
Institut für Angewandte Mikroelektronik und Datentechnik 27
Übung 7 – Pass Through Blocking
Prozess Priorität Periode Offset Deadline Rechenzeit Auslastung
PH 3 (hoch) 120 20 120 30 0,25
PM 2 (mittel) 120 40 120 30 0,25
PL 1 (niedrig) 120 0 120 50 0,42
0 50
PL
PM
PH
100
Universität Rostock, Fakultät für Informatik und Elektrotechnik
Institut für Angewandte Mikroelektronik und Datentechnik 28
Übung 7 – Priority Inheritance Protocol
• PL wird auf Priorität von PH angehoben, wenn PH das Mutex anfordert
• PM kommt nicht zum Zuge• Zeit im kritischen Abschnitt wird verringert• Keine Kenntnis der nutzenden Threads nötig
0 50
PL
PM
PH
100
P=3 P=1
Universität Rostock, Fakultät für Informatik und Elektrotechnik
Institut für Angewandte Mikroelektronik und Datentechnik 29
Übung 7 – Priority Ceiling Protocol (PCP)
• Vermeidung von Deadlocks und Mehrfachvererbungen (Chained Blocking) [Raj91] • Einführung einer Ceiling-Konstanten c(Sj) pro Semaphor Sj
– c(Sj) = Priorität des höchst-prioren Prozesses, der das Semaphor nutzen wird– Prozess P kann ein Semaphor S nur setzen, wenn seine Priorität größer als die der
Ceiling-Konstanten aller nicht von P zur Zeit belegten Semaphoren ist (außer er besitzt bereits das höchst-priore Semaphor)
– Kann ein Prozess ein Semaphor nicht setzen, wird die Priorität des unterbrochenen Prozesses auf die des unterbrechenden Prozesses erhöht
• Einführung einer System-Ceiling-Konstanten S* zur einfacheren Berechnung Maximum aller Semaphor-Ceiling-Konstanten, die gerade genutzt werden
Der Grundgedanke bei PCP ist, sicherzustellen, dass ein Prozess, der andere Prozesse in kritischen Abschnitten unterbricht und einen eigenen betritt, eine höhere Priorität in diesem Abschnitt garantieren muss als die Prioritäten aller unterbrochenen kritischen Abschnitte. Kann diese Bedingung nicht erfüllt werden, wird der Prozess blockiert.
Universität Rostock, Fakultät für Informatik und Elektrotechnik
Institut für Angewandte Mikroelektronik und Datentechnik 30
Übung 7 – Beispiel PCP
Prozess Priorität Periode Offset Deadline Rechenzeit Auslastung
P0 3 (hoch) 150 50 150 40 0,27
P1 2 (mittel) 150 20 150 30 0,2
P2 1 (niedrig) 150 0 150 70 0,47
0 50
P2
P1S2
S2
P0
100
S*=2 S*=3S1
S0
S1S*=2
S*=3
S0
S*S*=2
S0
S*=2
S*=3
S1
S*=2 S*=2S*=3
S2S*=0
S*=2
S2S*=2
S2S*=0
150
3 Prozesse (P0, P1 & P2) konkurrieren über 3 Semaphoren (S0, S1 & S2)
Statische Prio
P0 P1 P2
Prio
3
2
1
Prio-Vererbung P1P2
S*=2
S*=3
S*=0 S*=0
S*=2 S*=0
Da alle Semaphore anfangs noch komplett frei sind, ist die Ceiling des Systems S* noch 0 P2 bekommt in jedem Fall S2 danach ist S* = S2 = 2 (S2 ‚begründet‘ S*)
Universität Rostock, Fakultät für Informatik und Elektrotechnik
Institut für Angewandte Mikroelektronik und Datentechnik 31
Übung 7 – Deadlockvermeidung
0 105 15 20
P2
P12
1
1
S*S*=1
1 2
12 21
Prio(P1) = Prio(P2) = 1C(S1) = C(S2) = 1