Stage

a Confiturerie: Synchronisation de processus ......................................... 1-30 Atelier automatisé - Synchronisation par sémaphores .............................. 1-32 Problème du barbier ................................................................................ 1-34 Problème des fumeurs .............................................................................. 1-35

1.6. PRODUCTEURS-CONSOMMATEURS OU TAMPON LIMITÉ.......................... 1-36

1.6.1. 1.6.2. 1.6.3. 1.6.4. Par ajout de code:.................................................................................... 1-36 Par sémaphore: ....................................................................................... 1-37 Avec moniteur: ( par message en Turing Plus)........................................ 1-38 Gestion de grandes zones tampons (messages)......................................... 1-40

1.7. LES LECTEURS ET LES ÉCRIVAINS ................................................................. 1-41

1.7.1. 1.7.2. 1.7.3. Solution avec sémaphores ........................................................................ 1-41 Le problème des lecteurs et des écrivains en Turing Plus ......................... 1-42 Traversee de la riviere ............................................................................. 1-45

1.8. LE PROBLÈME DES PHILOSOPHES ............................................................... 1-47

1.8.1. 1.8.2. 1.8.3. Solutions avec sémaphores....................................................................... 1-47 Solution avec moniteur en Turing Plus ..................................................... 1-48 Une autre solution avec moniteur ............................................................. 1-50

ii 1.9. PROBLEMES AVEC SÉMAPHORES................................................................... 1-51

1.9.1. 1.9.2. 1.9.3. 1.9.4. 1.9.5. Graphe de préséance................................................................................ 1-51 Graphe de préséance avec sémaphores..................................................... 1-51 Sémaphores binaires ................................................................................ 1-52 Allocation de ressources par ENQ et DEQ ............................................... 1-52 Sémaphore multiple.................................................................................. 1-53

1.10. PROBLEMES AVEC MONITEURS.................................................................... 1-54

1.10.1. 1.10.2. 1.10.3. 1.10.4. 1.10.5. 1.10.6. 1.10.7. 1.10.8. 1.10.9. Allocation d'espace mémoire .................................................................... 1-54 Allocation de zone tampon........................................................................ 1-54 Accès à un fichier..................................................................................... 1-55 Allocation d'imprimante avec priorité....................................................... 1-55 Déplacement entre deux salles.................................................................. 1-56 Gestion des ventes et inventaires .............................................................. 1-58 Espace de travail partagé entre machines................................................. 1-61 GESTION DES ACCÈS À UN DISQUE.................................................... 1-63 ORDONNANCEUR TEMPS RÉEL ......................................................... 1-68

1.11. MONITEUR DANS TURING PLUS ............................................................................ 1-70

1.11.1. 1.11.2. 1.11.3. 1.11.4. Processus concurrent ............................................................................... 1-70 Moniteur.................................................................................................. 1-70 Condition, wait et signal........................................................................... 1-71 Pause....................................................................................................... 1-72

1-1

CHAPITRE 1 1. LA PROGRAMMATION CONCURRENTE

Références: Chapitres 5 et 6 de William Stallings, OPERATING e SYSTEMS: INTERNALS AND DESIGN PRINCIPLES, 3 ed., Prentice Hall, 1998, isbn: 0-13-887407-7.

Chapitres 6 et 7 de Silberschatz et Galvin, 4e ed., Addison Wesley, 1994, isbn: 0-201-50480-4; 5e ed., 1998, isbn: 0-201-59113-8.

OPERATING SYSTEM CONCEPTS,

1.1. EXÉCUTION CONCURRENTE ET SYNCHRONISATION

1.1.1. Séquence d'instruction et interrelation:

Un programme est une séquence d'instructions et le résultat que doit fournir un programme est directement relié à l'ordre particulier dans lequel les instructions sont exécutées. Une manière de considérer l'exécution d'un programme est de se placer au niveau du processeur. Il s'agit de regarder la séquence d'instructions machines qui est soumise au processeur. La séquence implique un aspect temporel. Chaque instruction est exécutée à un moment précis. Le résultat est déterminé par la suite d'instructions. La suite d'instructions constitue un profil ou une signature du programme. Un programme correct doit être reproductible et donc posséder une signature ou profil particulier et distinctif. Lorsque deux programmes s'exécutent en même temps, en parallèle, nous pouvons considérer que nous avons deux séquences d'instructions parallèles. Cependant, il se peut que le rythme de progression des séquences ne soit pas constant dans le temps. A un moment donné, une séquence peut aller plus rapidement et plus tard ralentir. Dans un système complexe, plusieurs causes peuvent expliquer un tel changement de rythme. La mémoire virtuelle peut impliquer un délai variable selon que le contenu demandé est déjà en mémoire ou non. Le temps d'accès à une information sur disque est variable.

PROCESSUS CONCURRENT INTERRELATION Considérer toutes les séquences (états) possibles - aspect temporel

réduction des séquences possibles Est-ce la bonne réduction ? Pouvez-vous imaginer toutes les séquences ?

Synchronisation

à à à à à à

à à à à à à à

à à à à à à

à à à à à à

à

P1

S1 S2

séquences possibles S1 S1 S1 S3 S3 S3 S2 S3 S3 S1 S1 S4 S3 S2 S4 S2 S4 S1

P2

S3 S4

S4 S4 S2 S4 S2 S2

1-2

PROCESSUS CONCURRENT

des deux séquences originales. Il nous faut considérer tous les cas d'entrelacements possibles. Pour des programmes indépendants, tous ces entrelacements sont acceptables. Cependant, pour des programmes dépendants, seulement quelques uns de ces cas sont acceptables. Les autres doivent être évités, car ils conduisent à des résultats erronés ou à la catastrophe. Dans la programmation de programmes concurrents (et, sous-entendu, dépendants), il faut introduire des mécanismes qui permettent de synchroniser les processus et d'éliminer les séquences catastrophiques. La synchronisation implique que la progression d'un processus est éventuellement contrôlée par un autre. Cela implique l'arrêt éventuel d'un processus. La coopération entre processus peut prendre la forme de 1) échange d'information (par exemple, mémoire partagée ou par message) par

P1

S1 S2

Sémaphore a = 0, b = 0 ;

P1

S1 signal( a) wait( b) S2

SECTION CRITIQUE:

P1

wait( ex) S1 S2 signal( ex)

?

La variation dans la progression des programmes est sans importance si les deux programmes sont indépendants. C'est-à-dire que les résultats et la progression d'un programme ne sont pas affectés par les instructions exécutées par l'autre programme. Cependant, si les deux programmes sont dépendants, il faut préciser si une instruction d'un programme a eu lieu avant ou après une instruction de l'autre programme. Il faut alors tenir compte de la progression stricte dans le temps des deux programmes. On peut ainsi être amené à combiner les deux séquences en une seule, tenant compte de la progression relative des deux séquences. La séquence produite va consister en un entrelacement

à à à à

une seule séquence possible : S1 S3 S4

Sémaphore ex = 1 ;