![[Leonardo]](../../common/images/LeonardoGiordani.jpg)
original in it: Leonardo Giordani
it to en: Leonardo Giordani
en to de: Guido Socher
Voraussetzungen f�r das Verstehen des Artikels sind:
![[run in paralell]](../../common/images/illustration272.jpg)
Diese ist eine grundlegende Funktion des Betriebssystems. Es ist 'der �berwacher aller Prozesse'. Prozesse werden daher in einer eigenen Umgebung ausgef�hrt. Dadurch, dass das Betriebssystem die Kontrolle hat, entsteht f�r den Entwickler ein Problem: Wie ist es m�glich, dass unabh�ngige Prozesse zusammenarbeiten?
Das Problem ist komplexer als es zun�chst aussieht. Es ist nicht nur eine Frage der Synchronisation von Prozessen, sondern auch, wie man Daten teilen kann und gemeinsam lesen und schreiben.
Wir wollen zun�chst mal das klassische Problem des gleichzeitigen Datenzugriffs von zwei Prozessen diskutieren. Wenn zwei Prozesse dieselben Daten nur lesen, dann ist das offensichtlich kein Problem. Nun soll einer der beiden Prozesse die Daten modifizieren: Der andere wird unterschiedliche Daten sehen in Abh�ngigkeit davon, wann er auf die Daten zugreift, vor oder nach dem Schreiben des anderen Prozesses. Nehmen wir z.B. die zwei Prozesse "A" und "B" und die ganze Zahl "d". Prozess A erh�ht sie um eins und Prozess B druckt sie aus. In einer symbolischen Schreibweise kann man das so ausdr�cken:
A { d->d+1 } & B { d->output }
das "&" beschreibt hier gleichzeitige Ausf�hrung. Eine m�gliche L�sung ist:(-) d = 5 (A) d = 6 (B) output = 6
aber wenn B zuerst ausgef�hrt wird, dann erhalten wir:(-) d = 5 (B) output = 5 (A) d = 6
Man versteht sofort, wie wichtig es ist, diese Situationen richtig handzuhaben: Das Risiko, inkonsistente Daten zu erhalten, ist gro� und nicht akzeptabel. Man denke nur daran, dass die Daten auch das Geld auf einem Bankkonto darstellen k�nnte und man wird das Problem nie untersch�tzen.Im vorangegangen Artikel sprachen wir �ber die einfachste Form der Synchronisation, die waitpid(2) Funktion. Mit ihr kann ein Prozess auf den anderen warten, bis er fertig ist. Damit kann man schon einige der Konflikte beim Datenzugriff l�sen: Prozess P2 kann warten, bis P1 mit dem Modifizieren der Daten fertig ist und dann selbst fortfahren.
Das ist sicher eine L�sung, aber nicht die Beste, weil P2 warten muss, bis P1 fertig ist, selbst wenn P1 nicht mehr an gemeinsamen Daten arbeitet, sondern etwas anderes macht. Wir m�ssen daher die Granularit�t erh�hen und eine Regel einf�hren, um den konfliktfreien Zugrifff auf einzelne Daten zu kontrollieren. Die Standard Library bietet hierzu etwas namens SysV IPC (System V InterProcess Communication).
key_t ftok(const char *pathname, int proj_id);
Als Argument braucht die Funktion den Pfad zu einer existierenden Datei (pathname) und eine Integerzahl. Es ist nicht garantiert, dass der Key eine global eindeutige Zahl ist, da sie aus der i-node und device Nummer der Datei, die als Argument gegeben wurde, gebildet wird. Eine gute L�sung ist eine kleine Routine zu schreiben, die die bisher vergebenen Keys speichert und damit feststellen kann, ob es ein Duplikat oder eine neue Zahl ist.Semaphoren kann man verwenden, um Zugriffe zu verwalten: Der Wert der Semaphore beschreibt die Zahl der Prozesse, die Zugriff auf Daten oder andere Dinge haben. Jedes Mal, wenn ein Prozess Zugriff erh�lt, wird die Semaphore heruntergez�hlt und wenn der Zugriff wieder freigegeben wird, z�hlt man hoch. Sollen exklusive Zugriffe vergeben werden, so ist der Anfangswert 1 (nur ein Prozess kann zu jeder Zeit zugreifen).
Die Semaphore kann man auch als Z�hler f�r irgendwelche Dinge verwenden. In diesem Fall repr�sentiert der Wert der Semaphore die Anzahl der verf�gbaren Dinge (z.B. Anzahl freier Speicherzellen).
Nun zu einer praktischen Anwendung: Wir haben einen Pufferspeicher, in den mehrere Prozesse (S1,...,Sn) schreiben k�nnen und der von nur einem Prozess gelesen wird. Zu jedem Zeitpunkt darf immer nur ein Prozess den Wert des Speichers �ndern. Offensichtlich k�nnen die Prozesse S immer schreiben, solange der Speicher nicht voll ist und der Leseprozess L kann nur lesen, wenn der Speicher nicht leer ist. Wir brauchen daher 3 Semaphoren: eine zum Verwalten der Zugriffsrechte und zwei, um mitzuhalten, wieviele Elemente im Puffer sind (wir werden sp�ter sehen, warum nur zwei Semaphoren nicht ausreichen).
Da der Zugriff exklusiv sein soll, muss die erste Semaphore eine bin�re Semaphore sein. Die Werte der beiden anderen Semaphoren h�ngen von der Gr��e des Pufferspeichers ab.
Nun wollen wir lernen, wie man Semaphoren in C mit SysV Funktion benutzt. Mit semget(2) erzeugt man die Semaphoren:
int semget(key_t key, int nsems, int semflg);
Hier ist key ein IPC Key, nsems ist die Zahl der Semaphoren, die wir haben wollen und semflg beschreibt Zugriffsrecht mit 12 Bits. Die ersten 3 h�ngen mit dem Erzeugen der Semaphoren zusammen und die anderen 9 mit Lese- und Schreibrechten f�r user, group und other (beachte den Zusammenhang mit chmod und dem Unix Dateisystem). Eine vollst�ndige Beschreibung findet sich in der man-Page ipc(5). Wie man sieht, verwaltet SysV einen Satz Semaphoren und nicht einzelne, was zu kompakterem Code f�hrt.Nun wollen wir unsere erste Semaphore erzeugen:
#include <stdio.h>
#include <stdlib.h>
#include <linux/types.h>
#include <linux/ipc.h>
#include <linux/sem.h>
int main(void)
{
key_t key;
int semid;
key = ftok("/etc/fstab", getpid());
/* create a semaphore set with only 1 semaphore: */
semid = semget(key, 1, 0666 | IPC_CREAT);
return 0;
}
Nun m�ssen wir lernen, wie man sie verwaltet und entfernt. Das macht man
mit semctl(2):
int semctl(int semid, int semnum, int cmd, ...)
Diese Funktion arbeitet gem�� der Aktion, die in cmd definiert ist, auf dem Satz Semaphoren, semid, und der einzelnen Semaphore semnum. Die man-Page erkl�rt die Funktion genauer. F�r einige Aktionen braucht man noch ein weiteres Argument, dessen Datentyp wie folgt aussieht:
union semun {
int val; /* value for SETVAL */
struct semid_ds *buf; /* buffer for IPC_STAT, IPC_SET */
unsigned short *array; /* array for GETALL, SETALL */
/* Linux specific part: */
struct seminfo *__buf; /* buffer for IPC_INFO */
};
Um den Wert einer Semaphore zu setzen, benutzt man die SETVAL Direktive
und der Wert steht in der union semun. Lasst uns das Programm erweitern
und die Semaphore auf 1 setzen:
[...] /* create a semaphore set with only 1 semaphore */ semid = semget(key, 1, 0666 | IPC_CREAT); /* set value of semaphore number 0 to 1 */ arg.val = 1; semctl(semid, 0, SETVAL, arg); [...]Sp�ter m�ssen wir die Semaphore wieder freigeben. Das macht man mit IPC_RMID und semctl. Das l�scht die Semaphore und schickt eine Nachricht an alle Prozesse, die auf Zugriff zu der Semaphore warten. Eine letzte �nderung des Programms ist:
[...] /* set value of semaphore number 0 to 1 */ arg.val = 1; semctl(semid, 0, SETVAL, arg); /* deallocate semaphore */ semctl(semid, 0, IPC_RMID); [...]Wie wir gesehen haben, ist das Erzeugen und Verwalten einer Kontrollstruktur f�r parallel arbeitende Prozesse �brhaupt nicht schwierig. Wenn noch Fehlerbehandlung eingef�hrt wird, wird der Code etwas l�nger, aber nicht komplexer.
Die Semaphore kann nun mit der Funktion semop(2) benutzt werden:
int semop(int semid, struct sembuf *sops, unsigned nsops);
Hier ist semid, die Nummer, die einen Satz Semaphoren identifiziert, sops ein Array mit Operationen und nsops die Anzahl dieser Operationen. Jede Operation wird durch die sembuf struct dargestellt:unsigned short sem_num; short sem_op; short sem_flg;
sem_num ist die Semaphoren Nummer, sem_op die Operation, und sem_flg ein Flag, das die Wartepolitik beschreibt. Wir benutzen sem_flg=0. Die Operationen werden als Zahlen mit folgenden Werten dargestellt:Lesen und Scheiben ist nur virtuell. Wie wir im vorangegangenen Artikel gesehen haben, hat jeder Prozess seinen eigenen Speicherbereich und kann nicht einfach auf Speicher anderer Prozesse zugreifen. Jeder Prozess sieht hier also eine Kopie des eigenen Speichers. Das �ndert sich, wenn wir �ber shared memory sprechen, aber es ist besser einen Schritt nach dem anderen zu tun.
Warum brauchen wir 3 Semaphoren? Die erste stellt die Zugriffsrechte dar, und die anderen beiden brauchen wir f�r Inhalt und �berlauf (voll).
Wir haben also eine Semaphore (O), die die Anzahl der freien Pl�tze darstellt. Jedesmal, wenn W etwas in den Puffer legt, dann wird der Wert um eins erniedrigt bis Null erreicht ist (Puffer voll). R entnimmt dem Puffer die Werte und erh�ht die Semaphore. Hier gibt es aber keine Grenze. R k�nnte sie unendlich erh�hen. Wir brauchen also noch eine Semaphore (U) f�r das obere Limit. Der Prozess W wird also O um eins erniedrigen und U um eins erh�hen. Im Gegensatz dazu wird R die Semaphore O um eins erh�hen und U erniedrigen.
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <linux/types.h>
#include <linux/ipc.h>
#include <linux/sem.h>
int main(int argc, char *argv[])
{
/* IPC */
pid_t pid;
key_t key;
int semid;
union semun arg;
struct sembuf lock_res = {0, -1, 0};
struct sembuf rel_res = {0, 1, 0};
struct sembuf push[2] = {1, -1, IPC_NOWAIT, 2, 1, IPC_NOWAIT};
struct sembuf pop[2] = {1, 1, IPC_NOWAIT, 2, -1, IPC_NOWAIT};
/* Other */
int i;
if(argc < 2){
printf("Usage: bufdemo [dimensione]\n");
exit(0);
}
/* Semaphores */
key = ftok("/etc/fstab", getpid());
/* Create a semaphore set with 3 semaphore */
semid = semget(key, 3, 0666 | IPC_CREAT);
/* Initialize semaphore #0 to 1 - Resource controller */
arg.val = 1;
semctl(semid, 0, SETVAL, arg);
/* Initialize semaphore #1 to buf_length - Overflow controller */
/* Sem value is 'free space in buffer' */
arg.val = atol(argv[1]);
semctl(semid, 1, SETVAL, arg);
/* Initialize semaphore #2 to buf_length - Underflow controller */
/* Sem value is 'elements in buffer' */
arg.val = 0;
semctl(semid, 2, SETVAL, arg);
/* Fork */
for (i = 0; i < 5; i++){
pid = fork();
if (!pid){
for (i = 0; i < 20; i++){
sleep(rand()%6);
/* Try to lock resource - sem #0 */
if (semop(semid, &lock_res, 1) == -1){
perror("semop:lock_res");
}
/* Lock a free space - sem #1 / Put an element - sem #2*/
if (semop(semid, &push, 2) != -1){
printf("---> Process:%d\n", getpid());
}
else{
printf("---> Process:%d BUFFER FULL\n", getpid());
}
/* Release resource */
semop(semid, &rel_res, 1);
}
exit(0);
}
}
for (i = 0;i < 100; i++){
sleep(rand()%3);
/* Try to lock resource - sem #0 */
if (semop(semid, &lock_res, 1) == -1){
perror("semop:lock_res");
}
/* Unlock a free space - sem #1 / Get an element - sem #2 */
if (semop(semid, &pop, 2) != -1){
printf("<--- Process:%d\n", getpid());
}
else printf("<--- Process:%d BUFFER EMPTY\n", getpid());
/* Release resource */
semop(semid, &rel_res, 1);
}
/* Destroy semaphores */
semctl(semid, 0, IPC_RMID);
return 0;
}
Nun will ich die interessanten Teile etwas erl�utern:
struct sembuf lock_res = {0, -1, 0};
struct sembuf rel_res = {0, 1, 0};
struct sembuf push[2] = {1, -1, IPC_NOWAIT, 2, 1, IPC_NOWAIT};
struct sembuf pop[2] = {1, 1, IPC_NOWAIT, 2, -1, IPC_NOWAIT};
In dieses 4 Zeilen sind die Aktionen, die man auf unsere Semaphoren anwenden
kann. Die ersten zwei sind Einzelaktionen und die letzten zwei
Doppelaktionen. lock_res versucht die Resource zu sperren, also
exklusiven Zugriff zu erhalten: Es wird 1 von der ersten Semaphore (nummer 0)
subtrahiert, wenn der Wert noch nicht Null ist. Das Verhalten (policy), wenn
die Resource schon in Benutzung ist, ist "none" (der Prozess wartet). Die
rel_res Aktion ist identisch zu lock_res, aber die Resource wird
freigegeben (der Wert der Semaphore wird positiv).
Die Push und Pop Aktionen sind etwas komplexer. Es sind Felder mit zwei Aktionen. Die erste Aktion wird auf Semaphore Nummer 1 ausgef�hrt und die zweite auf Semaphore Nummer 2. Die erste wird hochgez�hlt und die zweite Semaphore heruntergez�hlt. Das Verhalten des Prozesses (policy) ist nicht mehr warten, sondern IPC_NOWAIT. Der Prozess arbeitet weiter und wird nicht blockiert.
/* Initialize semaphore #0 to 1 - Resource controller */ arg.val = 1; semctl(semid, 0, SETVAL, arg); /* Initialize semaphore #1 to buf_length - Overflow controller */ /* Sem value is 'free space in buffer' */ arg.val = atol(argv[1]); semctl(semid, 1, SETVAL, arg); /* Initialize semaphore #2 to buf_length - Underflow controller */ /* Sem value is 'elements in buffer' */ arg.val = 0; semctl(semid, 2, SETVAL, arg);Hier initialisieren wir den Wert der Semaphoren: Die Erste auf eins (exclusiver Zugriff), die Zweite erh�lt den Wert der L�nge des Pufferspeichers, und die Dritte wird auf 0 gesetzt. Wie schon gesagt, sind 2 und 3 f�r �berlauf und leer.
/* Try to lock resource - sem #0 */
if (semop(semid, &lock_res, 1) == -1){
perror("semop:lock_res");
}
/* Lock a free space - sem #1 / Put an element - sem #2*/
if (semop(semid, &push, 2) != -1){
printf("---> Process:%d\n", getpid());
}
else{
printf("---> Process:%d BUFFER FULL\n", getpid());
}
/* Release resource */
semop(semid, &rel_res, 1);
Der W Prozess versucht, Exklusivrechte zu erhalten mit der lock_res Aktion.
Wenn das getan ist, wird eine Push Aktion ausgef�hrt und auf den Bildschirm wird
etwas geschrieben, falls die Aktion nicht ausgef�hrt werden kann, weil
der Puffer voll ist. Danach werden die Exklusivrechte wieder abgegeben.
/* Try to lock resource - sem #0 */
if (semop(semid, &lock_res, 1) == -1){
perror("semop:lock_res");
}
/* Unlock a free space - sem #1 / Get an element - sem #2 */
if (semop(semid, &pop, 2) != -1){
printf("<--- Process:%d\n", getpid());
}
else printf("<--- Process:%d BUFFER EMPTY\n", getpid());
/* Release resource */
semop(semid, &rel_res, 1);
Der R Prozess arbeitet wie der W Prozess nur wird ein Pop statt dem
Push ausgef�hrt.
Im n�chsten Artikel werden wir �ber "message queues", eine andere Struktur f�r InterProcess Communication (Kommunikation zwischen Prozessen) und Synchronisation sprechen. Wie immer, schick mir ein E-Mail, wenn du etwas geschrieben hast mit den Funktionen, die wir hier besprochen haben. Ich freue mich, es zu lesen. Gute Arbeit!