Sémaphores Pierre David [email protected] Université de Strasbourg – Licence d’informatique 2014 – 2015 Plan Principes Implémentation Sémaphores IPC System V Sémaphores POSIX Problèmes classiques de synchronisation 2 c Pierre David, [email protected] Plan Principes Implémentation Sémaphores IPC System V Sémaphores POSIX Problèmes classiques de synchronisation 3 c Pierre David, [email protected] Principes Verrou d’exclusion mutuelle (mutex) : mécanisme primitif de synchronisation Mécanisme de plus haut niveau : sémaphore de Dijkstra I I un compteur 3 opérations atomiques I I I initialisation P V c Pierre David, [email protected] 4 Principes I Opération atomique P : P ( cpteur ) { while ( cpteur <= 0) ; /* attente active */ cpteur - } P = proberen (tester) en néerlandais Moyen mnémotechnique : P = « Puis-je ? » I Opération atomique V : V ( cpteur ) { cpteur ++ ; } V = verhogen (incrémenter) en néerlandais Moyen mnémotechnique : V = « Vas-y ! » c Pierre David, [email protected] 5 Principes Compteur = nombre d’exemplaires disponibles d’une ressource Exemple : P P(pk) V(pk) pk = 4 I I I I initialement, le compteur est initialisé à 12 il reste 4 exemplaires disponibles de la ressource « place de parking » barrière d’entrée = P ⇒ teste et décrémente le compteur barrière de sortie = V ⇒ incrémente le compteur 6 c Pierre David, [email protected] Principes Deux cas principaux : I sémaphore général : le compteur peut prendre n’importe quelle valeur I sémaphore binaire : le compteur peut prendre la valeur 0 ou la valeur 1 ⇒ équivalent à un verrou d’exclusion mutuelle (mutex) c Pierre David, [email protected] 7 Exemple Soit les deux processus A et B : A B i1 i2 On veut que i1 soit exécutée avant i2 : A B i1 V(s) P(s) i2 Sémaphore s initialisé à 0 8 c Pierre David, [email protected] Plan Principes Implémentation Sémaphores IPC System V Sémaphores POSIX Problèmes classiques de synchronisation 9 c Pierre David, [email protected] Implémentation naïve Implémentation possible avec des spin mutexes : verrou v1 , v2 ; P ( cpteur ) { spin_lock ( v1 ) ; while ( cpteur <= 0) ; /* attente active */ spin_lock ( v2 ) ; cpteur - - ; spin_unlock ( v2 ) ; spin_unlock ( v1 ) ; } V ( cpteur ) { spin_lock ( v2 ) ; cpteur ++ ; spin_unlock ( v2 ) ; } ⇒ attente active + spin mutexes (attente active également) 10 c Pierre David, [email protected] Implémentation avec attente passive Attente passive ⇒ support du système d’exploitation Modification du sémaphore : I compteur I liste des processus en attente 11 c Pierre David, [email protected] Implémentation avec attente passive Nouvelle définition de P et V (non atomique) : P (S) { S . cpteur - - ; if ( S . cpteur < 0) { ajouter_fifo ( S . liste , ps_courant ) ; attendre () ; } } V (S) { S . cpteur ++ ; if ( S . cpteur <= 0) { ps = extraire_fifo ( S . liste ) ; reveiller ( ps ) ; } } I I cpteur > 0 ⇒ nombre de ressources disponibles cpteur < 0 ⇒ nombre de processus en attente 12 c Pierre David, [email protected] Implémentation avec mutex La définition précédente ne garantit pas l’atomicité de P et V I I I il faut que P soit exécuté en section critique ⇒ mutex S.verrou_p il faut que les modifications du compteur soient atomiques ⇒ mutex S.verrou_cpteur pour réaliser l’attente, on utilise un mutex ⇒ mutex S.attente ⇒ état initial : verrouillé 13 c Pierre David, [email protected] Implémentation avec mutex P (S) { lock ( S . verrou_p ) ; lock ( S . verrou_cpteur ) ; s . cpteur - - ; if ( s . cpteur < 0) { unlock ( S . verrou_cpteur ) ; lock ( S . attente ) ; } else { unlock ( S . verrou_cpteur ) ; } unlock ( S . verrou_p ) ; } V (S) { lock ( S . verrou_cpteur ) ; s . cpteur ++ ; if ( s . cpteur <= 0) { unlock ( S . attente ) ; } unlock ( S . verrou_cpteur ) ; } 14 c Pierre David, [email protected] Plan Principes Implémentation Sémaphores IPC System V Sémaphores POSIX Problèmes classiques de synchronisation 15 c Pierre David, [email protected] IPC System V IPC System V : objet « ensemble de sémaphores » I objet très sophistiqué I opérations atomiques sur un ensemble de sémaphores Exemple : si je peux faire un P sur s[0] et sur s[1], je fais également un V sur s[2] I ⇒ interface de programmation complexe ! c Pierre David, [email protected] 16 IPC System V Primitives d’accès : I semget : crée ou accède à un objet de type « ensemble de sémaphores » I semctl : opérations (p. ex. initialisation ou suppression) sur un ensemble de sémaphores I semop : opérations P et V sur sémaphores c Pierre David, [email protected] 17 IPC System V Opérations spécifiques des sémaphores : I semctl : I I I GETVAL ou SETVAL d’un sémaphore de l’ensemble GETALL ou SETALL : nécessite un tableau pour les valeurs semop : utilise un tableau de structures sembuf ⇒ spécifie les opérations à réaliser sur l’ensemble struct sembuf { unsigned short sem_num ; short sem_op ; short sem_flg ; } ; 18 /* numero de semaphore */ /* P : -1 , V :+1 */ /* 0 */ c Pierre David, [email protected] IPC System V int c reer_semaphore ( int val ) { key_t k ; int id ; k = ftok ( " / etc / passwd " , ’S ’) ; if ( k == -1) erreur ( " ftok " ) ; id = semget (k , 1 , IPC_CREAT | 0666) ; if ( id == -1) erreur ( " semget " ) ; if ( semctl ( id , 0 , SETVAL , val ) == -1) erreur ( " semctl ␣ setval " ) ; } return id ; 19 c Pierre David, [email protected] IPC System V int ac ced er_ sem aph ore ( void ) { key_t k ; int id ; k = ftok ( " / etc / passwd " , ’S ’) ; if ( k == -1) erreur ( " ftok " ) ; id = semget (k , 0 , 0) ; if ( id == -1) erreur ( " semget " ) ; } return id ; 20 c Pierre David, [email protected] IPC System V void s u p p r i m e r _ s em a p h o r e ( int id ) { int r ; } r = semctl ( id , 0 , IPC_RMID , NULL ) ; if ( r == -1) erreur ( " semctl " ) ; 21 c Pierre David, [email protected] IPC System V void P ( int id ) { struct sembuf s [1] = { {0 , -1 , 0} } ; } if ( semop ( id , s , 1) == -1) erreur ( " semop " ) ; void V ( int id ) { struct sembuf s [1] = { {0 , 1 , 0} } ; } if ( semop ( id , s , 1) == -1) erreur ( " semop " ) ; 22 c Pierre David, [email protected] Plan Principes Implémentation Sémaphores IPC System V Sémaphores POSIX Problèmes classiques de synchronisation 23 c Pierre David, [email protected] Sémaphores POSIX Sémaphores IPC System V : complexes pour les cas simples POSIX a normalisé une API simple et homogène plus proche de la définition de Dijkstra 24 c Pierre David, [email protected] Sémaphores POSIX Pour utiliser les sémaphores POSIX : I fichier d’inclusion : #include <semaphore.h> I édition de liens : cc -o ...-l pthread Note : l’API n’est pas spécifique aux threads ⇒ peut être utilisée pour synchroniser des processus Type : I sem_t : identificateur de sémaphore 25 c Pierre David, [email protected] Sémaphores POSIX Fonctions de l’API : I création et initialisation de sémaphore : int sem_init (sem_t *sem, int prtg, unsigned int val) I I I prtg = 0 : accès limité aux threads du processus courant prtg 6= 0 : accès à tous les processus qui partagent la mémoire *sem suppression de sémaphore : int sem_destroy (sem_t *sem) I lecture du compteur : int sem_getvalue (sem_t *sem, int *val) 26 c Pierre David, [email protected] Sémaphores POSIX Fonctions de l’API : I P: int sem_wait (sem_t *sem) I P sans attente : int sem_trywait (sem_t *sem) I I P avec attente bornée : int sem_timedwait (sem_t *sem, struct timespec *habs) Avec struct timespec { time_t tv_sec; long tv_nsec; } ⇒ comme dans pthread_mutex_timedlock V: int sem_post (sem_t *sem) 27 c Pierre David, [email protected] Plan Principes Implémentation Sémaphores IPC System V Sémaphores POSIX Problèmes classiques de synchronisation c Pierre David, [email protected] 28 Problèmes classiques de synchronisation Problèmes classiques de concurrence ⇒ Illustration des mécanismes de synchronisation 1. producteur/consommateur sur tampon infini 2. producteur/consommateur sur tampon borné 3. lecteurs/écrivains avec priorité aux lecteurs ⇒ souvent rencontrés dans les cas réels c Pierre David, [email protected] 29 Producteur/consommateur / tampon infini Énoncé : I plusieurs processus produisent des données I plusieurs processus consomment des données I hypothèse irréaliste (mais pédagogique) : tableau de taille infinie cases produites et déja consommées cases produites et non consommées 0 6 1 2 3 4 5 7 8 9 cases non encore produites 10 11 12 13 14 15 16 17 indice de la première case à consommer ... indice de la prochaine case à produire producteur producteur consommateur consommateur consommateur 30 c Pierre David, [email protected] Producteur/consommateur / tampon infini init () { ip = ic = 0 ; c re er_semaphore ( Sip , 1) ; c re er_semaphore ( Sic , 1) ; c re er_semaphore ( Secrites , 0) ; } produire ( val ) { P ( Sip ) ; tampon [ ip ] = val ; ip = ip + 1 ; V ( Sip ) ; V ( Secrites ) ; } consommer () { P ( Secrites ) ; P ( Sic ) ; val = tampon [ ic ] ; ic = ic + 1 ; V ( Sic ) ; return val ; } c Pierre David, [email protected] 31 Producteur/consommateur / tampon infini Trois sémaphores, pour : I I I protéger les accès concurrents à l’indice de la première case à consommer ⇒ sémaphore binaire protéger les accès concurrents à l’indice de la prochaine case à produire ⇒ sémaphore binaire représenter le nombre de cases produites (i.e. que l’on peut consommer) ⇒ sémaphore général c Pierre David, [email protected] 32 Producteur/consommateur / tampon borné Énoncé : idem précédemment, mais tampon de taille bornée cases produites 0 1 2 3 4 cases disponibles 5 6 7 8 9 cases produites 10 11 12 13 14 15 16 17 18 19 indice de la prochaine case à produire indice de la première case à consommer consommateur producteur consommateur consommateur producteur 33 c Pierre David, [email protected] Producteur/consommateur / tampon infini init () { ip = ic = 0 ; c re er_semaphore ( Sip , 1) ; c re er_semaphore ( Sic , 1) ; c re er_semaphore ( Secrites , 0) ; c re er_semaphore ( Slibres , N ) ; } produire ( val ) { P ( Slibres ) P ( Sip ) ; tampon [ ip ] = val ; ip = ( ip + 1) % N ; V ( Sip ) ; V ( Secrites ) ; } consommer () { P ( Secrites ) ; P ( Sic ) ; val = tampon [ ic ] ; ic = ( ic + 1) % N ; V ( Sic ) ; V ( Slibres ) return val ; } 34 c Pierre David, [email protected] Producteur/consommateur / tampon borné Un sémaphore supplémentaire, pour : I représenter le nombre de cases libres (i.e. que l’on peut produire) ⇒ sémaphore général 35 c Pierre David, [email protected] Lecteurs/écrivains avec priorité aux lecteurs Énoncé : I plusieurs processus peuvent accéder à une donnée I I I les accès en lecture peuvent être concurrents un accès en écriture est exclusif de tout autre accès (en lecture comme en écriture) un écrivain ne peut accéder à la donnée que si plus aucun lecteur n’y accède ⇒ priorité aux lecteurs 36 c Pierre David, [email protected] Lecteurs/écrivains avec priorité aux lecteurs Problème typique de l’accès aux données complexes. Exemples : I struct timespec ⇒ si la donnée est modifiée entre la lecture de tv_sec et tv_nsec, le résultat est inintelligible I accès à une ligne d’une table de SGBD 37 c Pierre David, [email protected] Lecteurs/écrivains avec priorité aux lecteurs init () { c re er_semaphore ( Secrivain , 1) ; c re er_semaphore ( Smutex , 1) ; nlect = 0 ; } ecrivain () { P ( Secrivain ) ; /* ecriture */ V ( Secrivain ) ; } lecteur () { P ( Smutex ) ; nlect ++ ; if ( nlect == 1) { P ( Secrivain ) } V ( Smutex ) ; /* lecture */ P ( Smutex ) ; nlect - - ; if ( nlect == 0) { V ( Secrivain ) } V ( Smutex ) ; } 38 c Pierre David, [email protected] Lecteurs/écrivains avec priorité aux lecteurs Deux sémaphores, pour : I I protéger les accès concurrents à nlect ⇒ sémaphore binaire protéger l’accès en écriture exclusivement de tout autre accès ⇒ sémaphore binaire 39 c Pierre David, [email protected]
© Copyright 2024 ExpyDoc
