Synchronisation sous systeme Linux

Pourquoi synchroniser les processus ?Le nombre de ressources d'un système d'exploitation est limité.

On trouve les processus en situation de concurrence (race) vis-à-vis des ressources.

le But de la synchronisation est de contrôler la concurrence.

Contrôler la concurrence➔ Organiser la compétition:

◆ Fournir des services de synchronisation indirecte par exclusion mutuelle : « Arbitrage », rôle du système.

◆ Ou au contraire, inclure la partie contrôle de concurrence au sein des programmes : « sans arbitrage » par le système.

➔ Coordonner l’utilisation des ressources: ◆ Empêcher ou réparer des blocages

◆ Garantir l’équité ou absence de famine

Section Critique

Section Critique: Toute section de code (séquence d’instructions) manipulant de ressources communes (variables communes, …)

Exclusion mutuelle ou Mutex: Il y a au plus une entité en section critique qui permet de réguler l’accès aux données.

Exemple : accès à une base de données.

Remarque: Plusieurs processus peuvent la lire simultanément.

Outils de synchronisation Matériels :

emploi de Test and Set qui est basée sur l’utilisation d’une instruction permettant de lire et d’écrire le contenu d’un mot mémoire de manière indivisible.

inhibition des interruptions (possible seulement dans le cas d'un processus se déroulant en mode privilégié).

Logiciels :

sémaphores (outils logiciels mis à la disposition des utilisateurs par le système d'exploitation)

algorithmes de synchronisation.

Masquage d ’interruptions (Monoprocesseurs)

Solution brutale: seule l’interruption générée par la fin du quantum de temps nous intéresse.

Le comportement des processus est décrit par le schéma suivant :

while(1){< Section Restante >Masquer les interruptions ;< Section Critique >Démasquer les interruptions ;}

Test And Set (Multiprocesseurs: instruction indivisible)

Cette solution est basée sur l’utilisation d’une instruction permettant de lire et d’écrire le contenu d’un mot mémoire de manière indivisible.

➔ Instruction minimale permettant de bâtir de la synchronisation

➔ Instruction atomique (garantie atomique par le scheduler et le hard)

Le drapeau est partagé par plusieurs processus, il est initialisée à zéro.tas registre, drapeau

⇔

{registre ← drapeau; drapeau ← 1;}

EntreeMutex: tas registre, drapeau cmp registre 0 jnz EntreeMutex ret

Inconvénients de cette technique :

➔ Attente active (busy waiting)

➔ On ne sait pas qui va prendre la main.

On peut avoir une solution pour l’attente active par la mise en sommeil en utilisant sleep(), awake().

Efficace mais (trop) complexe à mettre en œuvre !

SémaphoresUn sémaphore est un type de donnée abstraite. Le sémaphore a été inventé

par Edsger Dijkstra.

Les sémaphores fournissent la solution la plus courante pour le fameux problème du « dîner des philosophes »

Un sémaphore Sem associé à une ressource R est un objet composé :

d'un compteur Sem.Ka qui indique le nombre d'éléments disponibles ou le nombre de processus en attente sur R

d'une file d'attente Sem.L où sont chaînés les processus en attente sur la ressource R.

Les trois opérations prises en charge par un sémaphore sont Init, P et V.

Les operationsP (Proberen signifie tester): elle

teste la disponibilité d’une ressource, et elle alloue immediatement au processus courant.

V (Verhogen signifie incrementer): elle libère la ressource après que le processus a terminé de l'utiliser.

Init: Pour initialiser le sémaphore. Cette opération est utilisée une seule et unique fois.

Operations Initfunction Init (semaphore sem, int val) { disable_Interrupt; sem.K = val; enable_interrupt; }

Operation Pfunction P (semaphore sem) { disable_interrupt; if (sem.K == 0) { L.suivant = processus_courant; processus_courant.état = bloque; reordonnancement = vrai; } else { sem.K = sem.K-1; } enable_interrupt; }

Operation Vfunction V (semaphore sem) { disable_interrupt; sem.K = sem.K+1; if (not L.vide) { processus_réveillé = L.tête; processus_réveillé.état = prêt; reordonnancement = vrai; } enable_interrupt; }

Les cas traités par les SémaphoresProducteur et consommateur

Lecteur et écrivain

Production ConsommationProducteur Consommateur

Ecriture LectureProducteur LecteurEcrivain

R

R

Producteur et consommateur

Producteurcréer un document Dverrouiller F ajouter D à la fin de la file Fdéverrouiller Fenvoyer un signal au processus consommateur

Consommateurrépéter attendre signal de F tant que F n'est pas vide: pour chaque élément E de F: verrouiller F imprimer E supprimer E de F déverrouiller F fin pour fin tant-que attendre un signal d'un producteurfin répéter

Contrôle de La concurrence « sans arbitrage » par le systèm

La concurrence entre le Processus Pi et Pj.Ces algorithmes sont introduits au sein de Pi.

Algorithme de Dekker/* i veut entrer en S.C. */ Etat[i] = 1; while (Etat[j] == 1) {

if (tour == j) { Etat[i] = 0; /* attendre que

l'autre sorte de SC */ while(tour == j)

{ }; Etat[i] = 1;

} } /* debut de section critique */ ... ... /* fin de section critique */ tour = j; Etat[i] = 0;

• Exclusion mutuelle garantie• Pas d'interblocage

Algorithme de Peterson... /* i veut entrer en S.C. */ Etat[i] = 1; /* mais il laisse passer j, si j veut entrer */ tour = j; /* attendre que Pj sorte de SC */ while ((Etat[j] == 1) && (tour == j)) {}; /* debut de S.C. */ ... … /* fin de section critique */ Etat[i] = 0;

● Exclusion mutuelle garantie,

● pas d’interblocage ● attente limitée

Réalisé par :Fadwa Gmiden

Synchronisation sous systeme Linux

Pourquoi synchroniser les processus ?Le nombre de ressources d'un système d'exploitation est limité.

On trouve les processus en situation de concurrence (race) vis-à-vis des ressources.

le But de la synchronisation est de contrôler la concurrence.

Contrôler la concurrence➔ Organiser la compétition:

◆ Fournir des services de synchronisation indirecte par exclusion mutuelle : « Arbitrage », rôle du système.

◆ Ou au contraire, inclure la partie contrôle de concurrence au sein des programmes : « sans arbitrage » par le système.

➔ Coordonner l’utilisation des ressources: ◆ Empêcher ou réparer des blocages

◆ Garantir l’équité ou absence de famine

Section Critique

Section Critique: Toute section de code (séquence d’instructions) manipulant de ressources communes (variables communes, …)

Exclusion mutuelle ou Mutex: Il y a au plus une entité en section critique qui permet de réguler l’accès aux données.

Exemple : accès à une base de données.

Remarque: Plusieurs processus peuvent la lire simultanément.

Outils de synchronisation Matériels :

emploi de Test and Set qui est basée sur l’utilisation d’une instruction permettant de lire et d’écrire le contenu d’un mot mémoire de manière indivisible.

inhibition des interruptions (possible seulement dans le cas d'un processus se déroulant en mode privilégié).

Logiciels :

sémaphores (outils logiciels mis à la disposition des utilisateurs par le système d'exploitation)

algorithmes de synchronisation.

Masquage d ’interruptions (Monoprocesseurs)

Solution brutale: seule l’interruption générée par la fin du quantum de temps nous intéresse.

Le comportement des processus est décrit par le schéma suivant :

while(1){< Section Restante >Masquer les interruptions ;< Section Critique >Démasquer les interruptions ;}

Test And Set (Multiprocesseurs: instruction indivisible)

Cette solution est basée sur l’utilisation d’une instruction permettant de lire et d’écrire le contenu d’un mot mémoire de manière indivisible.

➔ Instruction minimale permettant de bâtir de la synchronisation

➔ Instruction atomique (garantie atomique par le scheduler et le hard)

Le drapeau est partagé par plusieurs processus, il est initialisée à zéro.tas registre, drapeau

⇔

{registre ← drapeau; drapeau ← 1;}

EntreeMutex: tas registre, drapeau cmp registre 0 jnz EntreeMutex ret

Inconvénients de cette technique :

➔ Attente active (busy waiting)

➔ On ne sait pas qui va prendre la main.

On peut avoir une solution pour l’attente active par la mise en sommeil en utilisant sleep(), awake().

Efficace mais (trop) complexe à mettre en œuvre !

SémaphoresUn sémaphore est un type de donnée abstraite. Le sémaphore a été inventé

par Edsger Dijkstra.

Les sémaphores fournissent la solution la plus courante pour le fameux problème du « dîner des philosophes »

Un sémaphore Sem associé à une ressource R est un objet composé :

d'un compteur Sem.Ka qui indique le nombre d'éléments disponibles ou le nombre de processus en attente sur R

d'une file d'attente Sem.L où sont chaînés les processus en attente sur la ressource R.

Les trois opérations prises en charge par un sémaphore sont Init, P et V.

Les operationsP (Proberen signifie tester): elle

teste la disponibilité d’une ressource, et elle alloue immediatement au processus courant.

V (Verhogen signifie incrementer): elle libère la ressource après que le processus a terminé de l'utiliser.

Init: Pour initialiser le sémaphore. Cette opération est utilisée une seule et unique fois.

Operations Initfunction Init (semaphore sem, int val) { disable_Interrupt; sem.K = val; enable_interrupt; }

Operation Pfunction P (semaphore sem) { disable_interrupt; if (sem.K == 0) { L.suivant = processus_courant; processus_courant.état = bloque; reordonnancement = vrai; } else { sem.K = sem.K-1; } enable_interrupt; }

Operation Vfunction V (semaphore sem) { disable_interrupt; sem.K = sem.K+1; if (not L.vide) { processus_réveillé = L.tête; processus_réveillé.état = prêt; reordonnancement = vrai; } enable_interrupt; }

Les cas traités par les SémaphoresProducteur et consommateur

Lecteur et écrivain

Production ConsommationProducteur Consommateur

Ecriture LectureProducteur LecteurEcrivain

R

R

Producteur et consommateur

Producteurcréer un document Dverrouiller F ajouter D à la fin de la file Fdéverrouiller Fenvoyer un signal au processus consommateur

Consommateurrépéter attendre signal de F tant que F n'est pas vide: pour chaque élément E de F: verrouiller F imprimer E supprimer E de F déverrouiller F fin pour fin tant-que attendre un signal d'un producteurfin répéter

Algorithme de Peterson... /* i veut entrer en S.C. */ Etat[i] = 1; /* mais il laisse passer j, si j veut entrer */ tour = j; /* attendre que Pj sorte de SC */ while ((Etat[j] == 1) && (tour == j)) {}; /* debut de S.C. */ ... … /* fin de section critique */ Etat[i] = 0;

● Exclusion mutuelle garantie,

● pas d’interblocage ● attente limitée

Réalisé par :Fadwa Gmiden