Sémaphores et programmation parallèle

Définition d'un sémaphore

Un sémaphore est une entité informatique composée

- de données : un entier noté ici SEM et une file d'attente

- et de méthodes : Init, P et V

Un sémaphore est utilisé :

- soit pour l'allocation de ressources (initialisation de l'entier du sémaphore à 1)

- soit pour la synchronisation de processus (initialisation de l'entier du sémaphore à 0)

Les sémaphores sont utilisés ici uniquement en synchronisation

Un sémaphore en synchronisation doit être toujours inititialisé à 0 par un Init( S, 0 )

Et on ne doit appeler qu'une fois la méthode V( S ) et qu'une seule fois la méthode P( S )

Les sémaphores utilisés en allocation seront vus ultérieurement

De manière générale, la méthode Init( S, valeur ) permet d'initialiser l'entier du sémaphore

Methode Init( valeur ) { SEM = valeur; }

La primitive P( S ) permet à un processus de demander l'allocation d'une ressource gardée par le sémaphore S

Dans le cas de la synchronisation, cette ressource sera donnée par un autre processus avec la méthodé V( S )

Le processus demande en fait la Permission de continuer son éxécution

Methode P( S ) { SEM:=SEM-1 Si SEM < 0 Alors état du processus demandeur = bloqué mise en attente dans la file d'attente du sémaphore Fin_Si

La primitive V( S ) permet de libérer une ressource en cours d'utilisation et gardée par le sémaphore

Dans le cas de la synchronisation, le processus donne le feu Vert au processus en attente d'exécution

Methode V( S ) { SEM:=SEM+1; Si SEM <=0 Alors il y a des processus à débloquer état du premier processus en attente = ACTIVABLE Fin_Si

Sémaphores et Programmation Parallèle

Supposons :

• T1 avant T3
• T1 avant T4
• T2 avant T4

Pour programmer ce système de tâches, on doit utiliser au moins un sémaphore.

Choisissons de mettre ce sémaphore entre T1 et T4 pour assurer la synchronisation de ces deux tâches

On commencera par programmer le système de tâche sans la flèche rouge, ce qui a été demandé en exercice 1 de la page précédente

On ajoute ensuite l'appel des méthodes Init, P et V

  Init( S, 0 );
  ParBegin
    { T1; V( S ); T3 }  // T1 donne le feu Vert
    { T2; P( S ); T4 }  // T4 attend la Permisson de s'exécuter
   ParEnd

Il est impératif de vérifier que { T1; V( S ) } et { P( S ); T4 } s'excutent bien en séquence

Le V doit être exécuté après la tâche qui donne le feu Vert

Le P doit être exécuté avant la tâche qui attend la permission

Exercice 1 - Écrire un programme avec un sémaphore entre les taches T1 et T3

  Remarque  { T1; V( S ) }  doit s'exécuter en séquence et non en parallèle

Init( S, 0 ); ParBegin { P( S ); T3 } { ParBegin { T1; V( S ) }; T2 ParEnd; T4 } ParEnd

Exercice 2 - Écrire un programme avec un sémaphore entre les taches T2 et T4

  Remarque   { P( S ); T4 }  doit s'exécuter en séquence et non en parallèle

Init( S, 0 ); ParBegin { T2; V( S ); } { T1; ParBegin T3; { P( S ); T4 } ParEnd; } ParEnd

Pour écrire le programme avec trois sémaphores pour le graphe précédent

On va lancer les 4 tâches en parallèle mais avec :

• un sémaphore S1 entre T1 et T3
• un sémaphore S2 entre T1 et T4
• un sémaphore S3 entre T2 et T4

Init( S1, 0 ) ; Init( S2, 0 ); Init( S3, 0 ); ParBegin { T1; V( S1 ); V( S2 ) } { T2; V( S3 )} { P( S1 ); T3 } { P( S2 ); P( S3 ); T4 } ParEnd

Pour chaque sémaphore on a qu'un seul Init, qu'un seul V et qu'un seul P

Exercice 3 - A faire en dernier

Rendre le graphe minimal en supprimant les flèches inutiles

Préciser lesquelles sont à enlever, par exemple flèche de T1 vers T5

Programmer le graphe obtenu avec un nombre minimal de sémaphores

A vous de programmer ce nouveau graphe plus simple et à ensuite ajouter les P et V des 2 sémaphores nécessaires