Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

NFP137 Cours 12 1 Contrôle de concurrence par sémaphores NFP137 Cours 12 2 Rapp

NFP137 Cours 12 1 Contrôle de concurrence par sémaphores NFP137 Cours 12 2 Rappel du concept de sémaphore Définition (Dijkstra-1965) Un sémaphore S est un objet partagé constitué de - un entier E initialisé à une valeur ≥0 - une file d’attente F des processus bloqués Un sémaphore est accessible uniquement par 3 primitives atomiques : P(S) : Puis-je (Proberen) contrôle d’autorisation + blocage éventuel du demandeur V(S) : Vas-y (Verhogen) ajout d’une autorisation + déblocage éventuel d’un demandeur E0(S,I) : initialisation du sémaphore à I≥0 autorisations et file d’attente vide NFP137 Cours 12 3 Rappel du concept de sémaphore Définition Primitive P(sémaphore S) : début S.E=S.E-1;//retrait d’une autorisation si S.E<0 alors bloquer le processus; placer son id dans la file; fin Primitive V(sémaphore S) : début S.E=S.E+1;//ajout d’une autorisation si S.E≤0 alors //il y a au moins un processus bloqué choix et retrait d’un processus de F; réveil du processus;finsi; fin Primitive E0(sémaphore S,entier I) : début S.E=I; S.F=vide;//I≥0 fin NFP137 Cours 12 4 Rappel du concept de sémaphore Propriétés - Un processus qui se bloque en exécutant P(S) termine son exécution de P(S) - Un processus ne peut accéder à un sémaphore que par les primitives P(S) et V(S), l’initialisation E0(S,I) doit précéder tout accès au sémaphore - Un seul processus peut exécuter P(S) ou V(S) à un instant donné - S.E initialisé à I≥0 signifie qu’on peut exécuter I fois P(S) sans blocage -S.E≥0 représente le nombre d’autorisations de franchissements de P(S) sans blocage, à un instant donné -S.E<0 |S.E| représente le nombre de processus bloqués à un instant donné NFP137 Cours 12 5 Rappel du concept de sémaphore Propriétés Soient NP(S) le nombre d’appels à P(S), NV(S) le nombre d’appels à V(S) NF(S) le nombre de franchissements de P(S) NBLOC(S) le nombre de processus bloqués -S.E=I-NP(S)+NV(S) -NBLOC(S)= max(0, -S.E) -NF(S)=Min(NP(S), I+NV(S)) NFP137 Cours 12 6 Exclusion mutuelle Accès exclusif à une ressource critique ou à un ensemble de variables partagées par N processus s’exécutant en concurrence Contexte commun ressource ou variables partagées Sémaphore mutex; E0(mutex,1); Processus Pi Début tant que vrai faire P(mutex); //entrée en section critique Section_critique; V(mutex);//sortie de section critique Hors section critique; Fin; NFP137 Cours 12 7 Exclusion mutuelle Respect des propriétés 1- Accès exclusif L’accès est autorisé dans P(mutex) si mutex.E ≥0, soit NP(mutex)≤1+NV(mutex) c’est-à-dire NP(mutex)-NV(mutex)≤1. Il y a donc au plus un processus au plus en section critique 2-Pas d’interblocage actif : si aucun processus en SC mutex.E=1 3-pas d’interblocage passif NFP137 Cours 12 8 La cohorte N processus au plus coopèrent pour -se répartir une tâche -partager N ressources banalisées Schéma d’exécution Processus Pi tant que vrai faire entrée-groupe//contrôle l’accès au groupe groupe //participation au groupe sortie-groupe // libère un accès hors groupe; fait NFP137 Cours 12 9 La cohorte Contexte commun sémaphore S_C; E0(S_C,N); Processus Pi tant que vrai faire P(S_C);//entrée-groupe groupe //participation au groupe V(S_C) //sortie-groupe hors groupe; fait NFP137 Cours 12 10 Cohorte : lot de ressources banalisées Problématique Un ensemble de processus se partagent un stock de N ressources banalisées, par exemple des pages mémoires, allouables dynamiquement une à une. -un sémaphore S_C initialisé à N modélise le nombre d’autorisations d’accès au stock -une structure de données partagée reflète l’état d’allocation de chaque ressource, on doit y accéder en exclusion mutuelle un sémaphore mutex initialisé à 1 contrôle la section critique NFP137 Cours 12 11 Cohorte : lot de ressources banalisées Cas de demande d’une seule ressource Contexte commun sémaphore S_C, mutex; E0(S_C,N); E0(mutex,1); booleen stock[N]; initialisé à faux; Processus Pi entier j; tant que vrai faire //acquisition d’une autorisation; P(S_C); // choix d’une ressource P(mutex); j=1; tant que stock[j] faire j=j+1;fait stock[j]=vrai; V(mutex); NFP137 Cours 12 12 Cohorte : lot de ressources banalisées Cas de demande d’une seule ressource(suite) Utilisation de la ressource j; //restitution de la ressource P(mutex); stock[j]=faux;V(mutex); V(S_C) //sortie-groupe hors groupe; fait NFP137 Cours 12 13 Cohorte : lot de ressources banalisées Problème : Cas de demande de plusieurs ressources Contexte commun sémaphore S_C, mutex; E0(S_C,N); E0(mutex,1); booleen stock[N] initialisé à faux; Processus Pi tant que vrai faire //acquisition des autorisations; P(S_C); P(S_C);… // choix des ressources P(mutex);… V[mutex]; //utilisation des ressources //restitution des ressources P(mutex);…V(mutex); V(S_C);V(S_C);… //sortie-groupe hors groupe; fait; Risque d’interblocage! NFP137 Cours 12 14 Producteurs-Consommateurs Spécification Contexte commun tampon de N cases producteur consommateur tant que vrai faire tant que vrai faire produire un message; retirer un message; déposer un message; consommer le message; fait fait Objectif Asservir la vitesse moyenne de production à la vitesse moyenne de consommation en ralentissant le moins possible le producteur NFP137 Cours 12 15 Producteurs-Consommateurs Hypothèses 1- vitesses relatives quelconques 2- tampon de taille fixe, 1 case=1message, vide initialement 3- tout message est déposé et retiré une fois et une seule 4- le dépôt et le retrait se font en un temps fini NFP137 Cours 12 16 Producteurs-Consommateurs Propriétés de la solution 1- exclusion mutuelle d’accès aux messages 2- le producteur attend si le tampon est plein, il est réveillé dès que le tampon n’est plus plein 3- le consommateur attend si le tampon est vide, il est réveillé dès que le tampon n’est plus vide 4- pas d’interblocage NFP137 Cours 12 17 Producteur-Consommateur Schéma d’exécution Contexte commun tampon de N cases vide; Processus producteur tant que vrai faire produire un message; si tampon plein alors se bloquer; déposer un message; si consommateur bloqué alors réveil du consommateur; fait; Processus consommateur tantque vrai faire si tampon vide alors se bloquer; retirer un message; si producteur bloqué alors réveil du producteur; consommer le message; fait; NFP137 Cours 12 18 Producteur-Consommateur Schéma de synchronisation - un sémaphore Nvide initialisé à N pour le contrôle du nombre de cases vides le producteur exécute P(Nvide) pour réserver une case le consommateur exécute V(Nvide) pour libérer une case - un sémaphore Nplein initialisé à 0 pour le contrôle du nombre de messages (cases pleines) le producteur exécute V(Nplein) pour signaler au consommateur 1 nouveau message dans le tampon le consommateur exécute P(Nplein) pour attendre un message NFP137 Cours 12 19 Producteur-Consommateur Schéma de synchronisation Contexte commun tampon de N cases vide; Sémaphore Nplein,Nvide; E0(Nplein,0);E0(Nvide,N) Processus producteur message m; tant que vrai faire produire un message(m); P(Nvide); déposer(m); V(Nplein); fait; Processus consommateur message m; tant que vrai faire P(Nplein); retirer(m); V(Nvide); consommer(m); fait; NFP137 Cours 12 20 Producteur-Consommateur Respect des propriétés 2- le producteur attend si le tampon est plein : P(Nvide) il est réveillé dès que le tampon n’est plus plein : V(Nvide) 3- le consommateur attend si le tampon est vide : P(Nplein) il est réveillé dès que le tampon n’est plus vide : V(Nplein) 4- pas d’interblocage : le producteur et le consommateur ne peuvent être bloqués simultanément, respectivement sur P(Nvide) et P(Nplein) NFP137 Cours 12 21 Producteur-Consommateur Gestion du tampon -Le tampon est géré circulairement, implanté par un tableau -On définit un indice de production queue et un indice de consommation tête -les messages doivent être consommés dans l’ordre de leur production, tête et queue sont initialisées à la même valeur Contexte commun Sémaphore Nplein,Nvide; E0(Nplein,0);E0(Nvide,N) Message tampon[N]; NFP137 Cours 12 22 Producteur-Consommateur Schéma avec gestion du tampon Processus producteur message m; entier queue=0; tant que vrai faire produire un message(m); P(Nvide); tampon[queue]=m;//déposer(m); V(Nplein); queue=(queue+1)%N; fait; NFP137 Cours 12 23 Producteur-Consommateur Schéma avec gestion du tampon Processus consommateur message m; entier tête=0; tant que vrai faire P(Nplein); m=tampon[tête];//retirer(m); V(Nvide); tête=(tête+1)%N; fait NFP137 Cours 12 24 Producteur-Consommateur Propriété 1- exclusion mutuelle d’accès aux messages Si le producteur et le consommateur “travaillent” sur la même case c’est que tête=queue tête=queue tampon vide alors le producteur est bloqué tête=queue tampon plein alors le consommateur est bloqué NFP137 Cours 12 25 Producteurs-Consommateurs Producteurs consommateurs multiples Le schéma de synchronisation assure une exclusion mutuelle entre producteurs et consommateurs - plusieurs producteurs ne doivent pas déposer dans la même case, l’indice de production queue est partagé ⇒Exclusion mutuelle entre producteurs - plusieurs consommateurs ne doivent pas prélever le même message, l’indice de consommation tête est partagé =>exclusion mutuelle entre consommateurs NFP137 Cours 12 26 Producteurs-Consommateurs Producteurs consommateurs multiples Contexte commun Sémaphore Nplein,Nvide; E0(Nplein,0);E0(Nvide,N); Sémaphore mutexProd,mutexCons; E0(mutexProd,1); E0(mutexCons,1); Entier tête,queue=0; Message tampon[N]; NFP137 Cours 12 27 Producteurs-Consommateurs Producteurs consommateurs multiples Processus producteur message m; tant que vrai faire produire un message(m); P(Nvide); P(mutexProd); tampon[queue]=m;//déposer(m); queue=(queue+1)%N; V(mutexProd) V(Nplein); fait; NFP137 Cours 12 28 Producteurs-Consommateurs Producteurs consommateurs multiples Processus consommateur message m; tant que vrai faire P(Nplein); P(mutexCons); m=tampon[tête];//retirer(m); tête=(tête+1)%N; V(mutexCons); V(Nvide); fait; NFP137 Cours 12 29 Lecteurs-Rédacteurs Compétition d’accès à un ensemble de données par un ensemble de processus - lecteurs accès seulement en lecture - rédacteurs accès en lecture et écriture Objectif Garantir la cohérence des données Spécification - plusieurs lectures simultanément - les écritures sont en exclusion mutuelle NFP137 Cours 12 30 Lecteurs-Rédacteurs Hypothèse complémentaire tout processus termine sa lecture ou son écriture au bout d’un temps fini Spécification de comportement - Les lectures sont concurrentes et cohérentes, les écritures sont en exclusion mutuelle - Priorité aux lecteurs, équité entre lecteurs et rédacteurs, service à l’ancienneté NFP137 Cours 12 31 Lecteurs-Rédacteurs uploads/Industriel/ c12semaphoresb-1-pdf.pdf