Cours Electronique AOP - laurent.bobelin.free.frlaurent.bobelin.free.fr/documents/courses/e2i5Unix/C4rousseau.pdf · FR : Université Joseph Fourier Unix - 7 Implémentation en C

Unix - 1FR : Université Joseph Fourier

Les sémaphores

• La problématique– Synchronisation multi-processus

– Accès à une section critique

• Les sémaphores– Définition, utilisation, opérations génériques

• Implémentation en C sous Linux– IPC SystemV et Posix

– Détermination de la clé

• Sémaphore et exclusion mutuelle• Problème classique : le dîner des philosophes• Pour aller plus loin

– Autres solutions …


Les IPC SystemV

• Avec la version SystemV d’Unix sont apparus 3 nouveaux mécanismes de communications (ou synchronisation) entre les processus locaux : files de messages, sémaphores, mémoire partagée

• IPC : Inter Processus Communication

• Ces 3 mécanismes sont extérieurs au système de fichiers– Pas de descripteur (pas de référence à un fichier)– Mécanismes de communication (ou synchronisation) pour des processus

sans lien de parenté mais s’exécutant sur la même machine– Le système gère une table de files pour chacun de ces mécanismes

• Le système assure la gestion de ces objets

• La commande ipcs donne la liste des IPC

• La commande ipcrm permet de détruire les IPC qui vous appartiennent• Chaque objet dispose d’une identification interne (entier positif ou nul). Les

processus qui veulent utiliser ces objets doivent connaître l’identificateur

• Les objets sont identifiés par un système de clé. L’attribution et la gestion des clés est un des points les plus délicats pour ces objets


Les sémaphores

• Utilisation des sémaphores– Synchronisation : Nécessité de bloquer ou débloquer des processus en cours

de fonctionnement, de synchroniser plusieurs processus– Exclusion mutuelle : Accès protégé à une section critique (gestion des

conflits)

• Autres mécanismes de synchronisation– Attente active (boucle)

• Coûteux car consomme du temps CPU• Admissible dans le cas multiprocesseur pour un durée brève

– Signaux• Suppose de connaître le PID du processus (difficile si plusieurs …)

• Les sémaphores ont été inventés en 1965 par Edsger Dijkstra (mathématicien et informaticien néerlandais 1930 – 2002)

• Un sémaphore est une variable protégée– Valeur numérique d’une variable entière– L’accès à cette variable ne doit se faire qu’avec des fonctions particulières


Opérations sur les sémaphores

• Soit S la valeur numérique d’un sémaphore

• P(S, n) : Si (S – n) ≥ 0, alors S = S – n et le processus continuesinon le processus est stoppé

• V(S, n) : S = S + n et tous les processus en attente du sémaphore sont débloqués (dans l’ordre des demandes …)

• Z(S) : le processus qui effectue cette opération est suspendu jusqu’à ce que S = 0

• Quand on parle des opérations P et V sur un sémaphore, on considère que n = 1

• Atomicité des opérations P et V (suite non interruptible)• Existence d’un mécanisme mémorisant les processus faisant P


Utilisation des sémaphores

• Synchronisation de 2 processus

• Synchronisation de plusieurs processus

Processus A

/* Création de 2 sémaphores etInitialisation à 0 */. . .P(sem1) /* blocage */. . .V(sem2) /* Deblocage */. . .

Processus B

. . .V(sem1) /* On déblocage le processus A*/. . .P(sem2) /* blocage */. . .

Processus A

/* Création du sémaphore etInitialisation à n + 1 */. . .P(sem)Z(sem) /* blocage */. . .

Processus 1

. . .P(sem)Z(sem) /* blocage */. . .

Processus n

. . .P(sem)Z(sem) /* blocage */. . .

. . .


Risque d’inter blocage

• Attention aux inter blocages …

Processus A

/* Création des sémaphores etInitialisation à 0 */. . .P(sem1) /* blocage */. . .V(sem2) /* Deblocage */. . .

Processus B

. . .P(sem2) /* blocage */. . .V(sem1) /* On déblocage le processus A*/. . .


Implémentation en C sous Linux : POSIX

• Norme POSIX– Déclaré dans <semaphore.h>

– 2 types de sémaphores• Anonymes : utilisable seulement dans le processus qui l’a créé

• Nommés : utilisable par des processus indépendants

– Utilisation• sem_t mon_semaphore

• int sem_init(sem_t *semap, int partage, unsigned int valeur);

• int sem_destroy(sem_t *semap);

• Pour accéder à un sémaphore nommé– sem_t * sem_open(const char * nom, int options, … /* mode_t mode, unsigned int valeur */);– int sem_close(sem_t *semap);

• int sem_wait(sem_t * semap); équivalent à P(semid)

• int sem_post(sem_t *semap); équivalent à V(semid)

• . . . (cf doc)


Implémentation en C sous Linux : SystemV

• En Unix SystemV, l’implémentation des sémaphores est beaucoup plus riche qu’une simple implémentation de P et V– Famille de sémaphores (plusieurs sémaphores d’une même famille)

• Intérêts – Atomicité des opérations sur tous les membres de la famille– Acquisition simultanée d’exemplaires multiples de ressources différentes

– Définition des opérations Pn() et Vn()• Diminution ou augmentation de la valeur du sémaphore de n de façon atomique

– Fonction Z()

• Les constantes et les prototypes des fonctions sont définies dans– #include <sys/sem.h> et <ipc.h>


Création d’une famille de sémaphores

• La fonction semget permet de créer une famille de sémaphores

int semget(key_t cle, int nb_sem, int option);

• cle : CF plus loin dans le cours

• nb_sem : nombre de sémaphores dans la famille– Les membres de la famille sont numérotés de 0 à nb_sem - 1

• option : Ou logique entre plusieurs constantes– IPC_CREAT : Crée l’objet si il n’existe pas

– IPC_EXCL : avec IPC_CREAT, signale par une erreur que l’objet existe

– Droit en lecture-écriture

• Retourne un identificateur de sémaphore

• Exemple

int semid;int nombre_de_sem = 4;

semid = semget(cle, nombre_de_sem, IPC_CREAT | IPC_EXCL | 0666); if (semid < 0) { printf(“Erreur semget\n"); exit(0); }


Initialisation d’une famille de sémaphores

• La fonction semctl permet d’initialiser une famille de sémaphoresint semctl(int semid, int semnum, int option, … /* arg */);

• Initialisation (et consultation …) des valeurs des sémaphores

• La fonction semctl rend -1 en cas d'erreur

• En fonction de option, semnum et arg ont les valeurs suivantes :– SETALL, semnum est ignoré, arg reçoit un pointeur sur un tableau d’entiers courts

pour initialiser les valeurs de toute la famille– SETVAL, semnum indique le numéro du sémaphore dans la famille, arg reçoit

l’entier correspondant à la valeur d’initialisation– GETALL et GETVAL permettent de connaître la valeur des sémaphores …

– IPC_RMID pour supprimer la famille de sémaphore (semnum et arg sont ignorés)


La structure sembuf

• C’est la structure à remplir (une par sémaphore de la famille, donc un tableau de structures si plusieurs membres) pour demander l’opération à effectuer.

– Définie dans <sys/sem.h>

– Les flags : IPC_NOWAIT (non bloquant) et SEM_UNDO (terminaison)

struct sembuf { unsigned short int sem_num; short sem_op; short sem_flg; };

Numéro du sémaphore dans la famille

Options de l’opération

Définition de l’action- Si > 0, V(semid, n)- Si = 0, Z- Si < 0, P(semid, n)


Opération sur les sémaphores avec semop()

• La fonction semop permet de réaliser un ensemble d’opérations sur une famille de sémaphoresint semop(int semid, struct sembuf *tab_str, int

nb_op);– Semid est l’identificateur de la famille– tab_str est un tableau de structures sembuf (nb_op structures)– nb_op nombre d’opérations à effectuer– Retourne 0 si OK, -1 en cas d’échec

• Opérations réalisées de façon atomique– Toutes ou aucune : annule les i – 1 ième si la nième opération ne

peut être effectuée– L’ordre des opérations n’est pas indifférent (sauf si toutes bloquantes

ou toutes non bloquantes)


Exemples de fonction P() et V()

/* Operation P (-1) sur le semaphore */int P(SEMAPHORE sem){ struct sembuf sb; sb.sem_num = 0; sb.sem_op = -1; sb.sem_flg = SEM_UNDO;

return semop(sem, &sb, 1);}

typedef int SEMAPHORE;

/* Operation V (+1) sur le semaphore */int V(SEMAPHORE sem){ struct sembuf sb; sb.sem_num = 0; sb.sem_op = 1; sb.sem_flg = SEM_UNDO;

return semop(sem, &sb, 1);}


Comment obtenir la clé ?

• Les IPC sont identifiés par un mécanisme de clé. Ces clés jouent le rôles de références pour les fichiers. Ces clés ont des valeurs numériques.– Le type de ces variables est key_t défini dans <sys/types.h>

– Chaque type d’IPC possède son propre ensemble de clés

– Important pour la portabilité des applications

• Le problème de clé peut se résoudre avec la fonction ftok– key_t ftok(const char *, int num);

• Cette fonction rend une clé obtenue à partir du nom d’un fichier existant et d’une valeur entière

• Les mêmes paramètres fourniront les mêmes clés (sauf déplacement de fichiers, qui dans ce cas change de numéro d’index …)

– Avec IPC_PRIVATE (clé privée) quand tous les processus qui utiliseront l’objet IPC sont des descendants de celui qui le crée


Exemples d’obtention d’une clé

int main(){SEMAPHORE semid; . . .if ((semid = semget(IPC_PRIVATE, nb_sem, IPC_CREAT|IPC_EXCL|0666)) == -1) /* Erreur */ . . .}

int main(){SEMAPHORE semid;key_t cle;. . .if ((cle = ftok("Exo2.c", 15)) == -1) /* Erreur */ . . .if ((semid = semget(cle, nb_sem, IPC_CREAT|IPC_EXCL|0666)) == -1) /* Erreur */ . . .}


L'exclusion mutuelle

• L'exclusion mutuelle (Mutex) est une fonctionnalité de synchronisation utilisée en programmation pour éviter que des ressources partagées d'un système ne soient utilisées en même temps

– Concerne les ressources partagées ou "section critique"• Exemple : accès simultanée en lecture/écriture dans une mémoire

• Avant d'utiliser une ressource, ou d'entrer en section critique, un processus fait une demande explicite

– Si la ressource est libre, il la prend et indique qu'elle est utilisée– Si la ressource est déjà utilisée, il attend

– Un sémaphore peut être utilisé pour cela. C'est lui qui indique si la ressource est disponible ou non

• Section critique : suite d'instructions qui peut produire un résultat imprévisible si elle est exécutée simultanément par plusieurs processus


Exclusion mutuelle : exemple

int processus1( . . .){. . ./* On vérifie la disponibilité de la ressource */P(semid);

/* On accède à la ressource ou à la section critique */. . .

/* Quand on a terminé, on libère la ressource */V(semid);. . .}

int processus2(. . .){ . . ./* On vérifie la disponibilité de la ressource */P(semid);

/* On accède à la ressource ou à la section critique */. . .

/* Quand on a terminé, on libère la ressource */V(semid);. . .}

A quelle valeur faut il initialiser le sémaphore pour qu'il fonctionne en mutex ?


Problème classique résolu grâce aux sémaphores :Le dîner des philosophes

• Problème classique d'ordonnancement des processus et d'allocation de ressources

• 5 philosophes (ou plus), autour d'une table partagent leur temps entre penser et manger. Chacun des philosophes possède devant lui une assiettes de spaghetti. A gauche de chaque assiette se trouve une fourchette. Il faut 2 fourchettes (ils sont maladroits) pour manger, celle à la gauche et celle à la droite de l'assiette– Un philosophe a 3 états possibles

• Il pense (pendant un temps indéterminé)• Il a faim (pendant un temps déterminé et fini, sinon il y a famine)

• Il mange (pendant un temps déterminé et fini)

• Le problème consiste à trouver un ordonnancement des philosophes tel qu'ils puissent tous manger chacun leur tour.– C'est un problème complexe en systèmes distribués


Le dîner des philosophes : solution naïve

• Solution naïve– Les fourchettes sont les ressources partagées

• 1 sémaphore par fourchette

• Prendre une fourchette consiste à faire un P()• Rendre une fourchette consiste à faire un V()

– Les philosophes sont numérotés de 0 à 4 (idem pour les fourchettes)

int philosophe(int i, . .) { . . . while (1) { penser(); P(semid[i]); /* On attend la fourchette de gauche */ P(semid[(i + 1) % N]); /* On attend la fourchette de droite */ manger() V(semid[i]); /* On libère la fourchette de gauche */ V(semid[(i + 1) % N]); /* On libère la fourchette de droite N = 5 */ } }


Le dîner des philosophes : problème de la solution naïve

• Inter blocage possible (si tous les philosophes prennent la fourchette de gauche, personne ne pourra prendre la fourchette à sa droite)

• Causes du problème– Chaque philosophe doit acquérir 2 ressources

• En 2 étapes• Dans un ordre qui peut mener à un blocage• Sans annulation possible

• Il existe d'autres solutions– Utilisation d'un tableau pour conserver le nombre de fourchettes

disponible pour chaque philosophe, un sémaphore par philosophe– . . .


Pour aller plus loin …

• Sémaphore binaire (ou verrou) : sémaphore ayant comme valeur 0 ou 1

• Exclusion mutuelle sur une architecture monoprocesseur– Blocage des IT

• Pour empêcher le changement de contexte• Jusqu'à la fin du temps donné au processus

• Réalisation dans les systèmes multiprocesseurs– Logiciel

• Attente active (instruction spéciale des processeurs test_and_set, SWP, …

– Matériel (sur FPGA …)

Documents

Cours Electronique AOP - laurent.bobelin.free.frlaurent.bobelin.free.fr/documents/courses/e2i5Unix/C4rousseau.pdf · FR : Université Joseph Fourier Unix - 7 Implémentation en C