Conservatoire National des Arts et Metiers - cursus informatique
COURS SUR LES APPLICATIONS CONCURRENTES
Conception
et Outils de Validation de
programmes concurrents
Cette unite d'enseignement CNAM porte le code NFP103 (ancienne UV 16981)
( voir les actualites)
- programme officiel du cours (on l'obtient aussi en cliquant sur l'image ci-contre)
- polycopie du cours, annales des sujets d'examen et des projets, documents
- sujets de TP et de dossiers pour l'annee 2004-2005 UV 16981
- programme, dates et lieux des seances de cours en 2005-2006 UE NFP103
- equipe pedagogique
ACTUALITES ET DERNIERES NOUVELLES DU COURS
PRESENTATION,
ACTUALITE ET OBJECTIFS DU
COURS
Cette unite d'enseignement est une unite de base pour un cursus de formation dans les domaines des applications et systemes concurrents, qu'ils soient embarques, temps reel, centralises, repartis ou cooperatifs. Elle apporte une vision approfondie des problemes de la gestion de la concurrence des processus. Elle permet de comprendre les aspects concurrents des plates-formes informatiques que l'on trouve dans les serveurs ou sites (des reseaux locaux ou sur le web).
__________________________
Avec l'extension du Web, de Java et de Ada95, des outils de programmation reseau, avec la programmation par evenements associee a des "threads" et a des actions reparties, avec l'approche client-serveur, avec le "peer to peer", il va etre de plus en plus facile de faire de la programmation concurrente ou parallele. Cela parait facile a programmer, mais c'est difficile a faire correctement. Il y aura beaucoup de programmes faux parce que concurrents.
Il faut sensibiliser les auditeurs aux bons paradigmes, aux bons "patterns" de concurrence ou de parallelisme, bons parce que bien connus et bien eprouves par ceux qui developpent des programmes concurrents depuis longtemps, mais aussi parce qu ils peuvent etre prouves et valides avec des outils de validation. Or ces outils sont disponibles au CNAM et sur le Web, et ils sont utilises pour des programmes et des problemes reels. Il est donc d'actualite d'enseigner ces "patterns" et leur evaluation, pour qu'ils soient utilises dans le developpement d'applications et de systemes comportant des processus concurrents.
Ce n'est pas seulement nous qui le disons, c'est aussi Doug Lea, le celebre auteur de : Concurrent Programming in Java : Design Principles and Patterns, Addison Wesley 97, et professeur a l'universite de New-York. Dans la revue "IIE Concurrency", Parallel, Distributed & Mobile Computing, vol.6, n. 4, oct.-dec. 1998, a la rubrique Object-Oriented Applications, il a publie un article "Patterns and the democratization of concurrent programming", pages 11-13, ou il ecrit :
"The number of concurrent programmers has skyrocketed over the past few years and will continue to do so."..."Although only a small proportion of code found in today's production programs, applications, and systems directly exploits concurrency, every programmer should at least be aware of concurrency."..."Concurrent programming's diversity appears in the wide range of designs and design approaches seen in practical applications."..."Concurrency techniques have become indispensable for programmers who create the highly available services and reactive applications that are now commonplace."..."Despite its increasing centrality, concurrency remains intrinsically more complex, unfamiliar, and prone to design and programming errors than most other aspects of programming."..."Many programmers increasingly cope with new, concurrency-driven complexities. And without expert guidance, they're also expected to occasionally fail."..."However, these multithreading constructs - threads, locks, monitors, sockets, and related interprocess messaging support - are now commonly accepted as the standard basis for building practical concurrent programs. And they can serve as building blocks for nearly any other style of concurrency support a programmer desires (such as Ada tasks)."..."Concurrent design-pattern descriptions thus typically address design forces and integrity issues."..."Temporal dimensions of correctness introduced by concurrency - safety and liveness (including fault-tolerance) - are central concerns in any concurrent design and its implementation."
Ce cours approfondit les notions sur la programmation concurrente vues dans l'unite d'enseignement NFP137 "Systemes informatiques et applications concurrentes" (ancienne UV 19339). En s'interessant, au premier chef, aux systemes multiprocesseurs (architectures a couplage fort), ce cours peut utilement completer le cours d'approfondissement "Systemes et Applications repartis" (UE NFP111) qui s'applique exclusivement aux aspects souleves par la repartition (architectures a couplage faible). Il apporte des bases pour les UE NFP214 et NFP215 "Reseaux et Systemes repartis". Ce cours presente aussi un grand interet pour les applications embarquees, mobiles ou en temps reel, domaines ou les consequences des fautes de programmation sont souvent dramatiques.
Au niveau de l'analyse operationnelle des applications cooperatives, centralisees, temps reel ou distribuees, apprehender les structures qui concernent l'execution des processus concurrents, le partage des ressources et des objets et qui expriment leurs relations et leur controle au moment de l'execution. Degager les paradigmes de la concurrence et les patrons de construction ("design patterns") qui sous-tendent les architectures logiques de ces applications, en etudier la programmation avec les mecanismes des langages, apprendre a en faire la validation en utilisant des outils disponibles, connaitre les principaux motifs d'erreur de parallelisme ("error patterns").
Savoir ainsi maitriser les difficultes de la concurrence lors de la construction, la modification, l'integration ou la maintenance d'applications comportant des processus cooperants, locaux ou distants. Disposer de techniques utiles pour receptionner les systemes informatiques de ces applications, pour les soumettre a des tests couvrant les principaux cas d'erreurs de gestion de la concurrence, et pour faire la recette par validation de travaux en sous-traitance ou en regie.
__________________________
Votre navigateur doit etre configure pour les lire, par exemple avec Acrobat Reader.
FICHIERS COMPRESSeS : vous pouvez telecharger le Cours ACCOV
tous fichiers en .tgz (ouvrir avec StuffitExpander par exemple)
__________________________
Actualite,
objectifs, bibliographie (4
pages) [ACCOV01Presentation.pdf]
__________________________
PLAN DU TOME 1 : programmation
concurrente [ACCOV10Couverture.pdf]
1.1.
Introduction
et exemples (30 pages)
[ACCOV11Introduction.pdf]
1.2. Paradigmes de la concurrence (28 pages) [ACCOV12Paradigmes.pdf]
1.3.
Communication
par memoire commune :
semaphores,
moniteurs, objets proteges Ada (48 pages) [ACCOV13ObjProteges.pdf]
1.4. Concurrence avec des taches serveur en Ada (24 pages) [ACCOV14TachesADA.pdf]
1.5. Concurrence en Java (19 pages) [ACCOV15ThreadsJava.pdf]
1.6. Ouvertures : interruptions, AST, distribution (19 pages) [ACCOV16Ouvertures.pdf]
1.7. Annexe Ada (15 pages) [ACCOV17AnnexeAda.pdf]
1.8.
Annexe
Reseaux de Petri (6
pages)
[ACCOV18AnnexeRdP.pdf]
1.9. Comparaisons Ada-java
[Brosgol1998.pdf]
[Sanden2002.pdf] [ACCOV19KPP2003.pdf]
1.A. System and Real-time programming in
Ada : Ada tasking [BingueCookDupaix.pdf]
1.B. Concurrency and Real-Time Programming
Support in Java, Ada and POSIX [BrosgolRosen.ppt]
__________________________
PLAN DU TOME 2 :
outils de
specification et de validation
2.1. Specification avec les reseaux de Petri (28 pages) [ACCOV21.pdf]
2.2
Verification
avec les reseaux de Petri (30 pages)
[ACCOV22.pdf]
2.3. Exemple d'analyse de programmes Ada (11 pages) [ACCOV23BKP1997]
2.4.
Comparaison
de
solutions pour un probleme d'allocation de ressources (17
pages) [ACCOV24KPP1998.pdf]
voir aussi http://quasar.cnam.fr
__________________________
- Le
sujet
[ACCOV31Examen2002.pdf]
- La
correction
[ACCOV31Correction2002.pdf]
- La
specification en
RdP de la solution du dernier exercice [ACCOV31Prog2Net.pdf]
- La
specification en Promela de cette meme
solution
[ACCOV31PromelaSpec.pdf]
EXAMEN DE JUIN 2004 :
- Le
sujet
[ACCOV32Examen2004.pdf]
- La correction [ACCOV32Correction2004.pdf]
EXAMEN DE JUIN 2005 :
- Le
sujet
[ACCOV33Examen2005.pdf]
- La correction [ACCOV33Correction2005.pdf]
__________________________
__________________________
PROJETS 2001-02 Mini projet de programmation concurrente (2001) [ACCOV41Projet2001.pdf]
PROJETS 2004-05 1. Surveillance par Webcams [ACCOV62SurveillanceWebcams.pdf]
2. Synoptique pour suivre plusieurs usines [ACCOV63SynoptiqueUsine.pdf]
3. Cooperation pair à pair [ACCOV64Chameneos.pdf]
On pourra programmer une solution en Ada, Java, Posix. Non interblocage, allocation equitable. On pourra considerer la repartition de l application.
canevas programmes projets 2004-05 : chameneos, synoptique, webcam,
__________________________
__________________________
PROGRAMMATION
DES APPLICATIONS DISTRIBUEES
1. texte de
Franco Gasperoni
: "Software
development"(en particulier en ADA) [ACCOV51Gasperoni.pdf]
2. la presentation des paradigmes de la distribution : messages, RPC, objets distribues
3a. la presentation de l utilisation de Ada pour la repartition
3b. la presentation de CORBA
4. une comparaison en conclusion avec [ACCOV52ProbatoireAlzeari2004.pdf]
2. Probatoire CNAM sur Ada Annexe distribuee, CORBA et POLYORB [ACCOV52ProbatoireAlzeari2004.pdf]
3. ANNONCE : PolyORB aims at providing a uniform solution to build distributed applications; relying either on industrial-strength middleware standards such as CORBA, the Distributed System Annex of Ada 95, distribution programming paradigms such as Web Services, Message Oriented Middleware (MOM), or to implement application-specific middleware. Voir (http://libre.act-europe.fr/polyorb/).
CONFERENCES SUR LE TEMPS REEL
1. Presentation du temps reel [TRK1Presentation.pdf]2. Structures d'accueil et langages [TRK2StructuresAccueil.pdf]
3. Modeles pour l'ordonnancement [TRK3Modeles.pdf]
4. Evolutions des plates-formes [TRK4Evolutions.pdf]
5. Travaux equipe Cratere/CNAM [TRK5TravauxCratere.pdf]
COURS
SUR LE TEMPS REEL
2. Programmation concurrente [TRPP2concur.pdf]
3. Ordonnancement temps reel [TRPP3Ordo.pdf]
4. Programmation Ada et Posix [TRPP4Programmation.pdf]
5. Synchronisation entre taches [TRPP5Synchro.pdf]
6. Synchronisation Ada et Posix [TRPP6SynchroLg.pdf]
7. Exemple d'application [TRPP7ExempleAppli.pdf]
1. Real-time Convergence of Ada and Java [BrosgolDobbing2001.pdf]
2. Le profil RAVENSCAR pour la programmation fiable des applications temps rel [BurnsDobbingVardanega2003.pdf]
__________________________
1. Enseigner
Ada [FeneuilleEnseignerAda.zip],
voir aussi plus de details sur http://www.ada-france.org/
http://libre.act-europe.fr/Software_Matters/
4 . Un site pour la programmation concurrente [http://stwww.weizmann.ac.il/g-cs/benari/cp.HTM]
5 . Un autre site pour la programmation concurrente [http://www.seas.gwu.edu/~mfeldman/cs2-book/chap15.html]
4. Paradigmes de la concurrence : solutions avec semaphores dans l'UE NFP137 Systemes informatiques et applications concurrentes
cours complet [http://deptinfo.cnam.fr/Enseignement/CycleProbatoire/SRI/Systemes/]
solutions avec semaphores manuel [http://deptinfo.cnam.fr/Enseignement/CycleProbatoire/SRI/Systemes/902Manuel.pdf]
solutions avec semaphores illustrations [http://deptinfo.cnam.fr/Enseignement/CycleProbatoire/SRI/Systemes/903Illustrations.pdf]
COURS,
DATES ET LIEUX EN 2005-2006 (UE NFP 103 ACCOV))
ENSEIGNANTS : Claude KAISER,
Jean-Francois
PEYRE (responsable du
cours : C
Kaiser)
COURS-ED-TP integres (60 heures)
SALLES DE COURS : MARDI
ENSAM salle P4, MERCREDI Icap sante salle Anemone
PLANNING ACCOV 2005-2006 (version septembre 2005),
(formule avec 2h par seance, une formule avec 3h par seance sera examinee)
|
dates |
programme des seances |
enseignants |
|||
|
04 octobre 2005 |
1. Presentation et organisation du cours. Introduction |
C.
Kaiser |
|
||
|
05 octobre 2005 |
2. Concurrence des processus des applications, programmation concurrente |
C. Kaiser |
|
||
|
11 octobre 2005 |
3. Paradigmes de la concurrence des processus |
C. Kaiser |
|
||
|
12 octobre 2005 |
4. programmation de la concurrence par ressource commune |
C. Kaiser |
|
||
|
18 octobre 2005 |
5. programmation de la concurrence avec semaphores Posix |
C. Kaiser |
|
||
|
19 octobre 2005 |
6. programmation de la concurrence par objets proteges |
C. Kaiser |
|
||
|
25 octobre 2005 |
7. TP de programmation concurrente avec objets protege |
C. Kaiser |
|
||
|
26 octobre 2005 |
8. programmation de la concurrence par objets proteges |
C. Kaiser |
|
||
| 08 novembre 2005 |
9.
Programmation de la repartition en Ada |
C. Kaiser |
|
||
|
09 novembre 2005 |
10. Programmation de la concurrence avec des taches serveur (Ada) |
C. Kaiser |
|
||
|
15 novembre 2005 |
11. Programmation de la concurrence avec des "threads" Java |
C. Kaiser |
|
||
|
16 novembre 2005 |
12.Programmation de la concurrence avec des "threads" Java |
C. Kaiser |
|
||
|
22 novembre 2005 |
13. Questions sur les projets de programmation concurrente |
C. Kaiser |
|
||
|
23 novembre 2005 |
14. Concurrence au niveau machine : interruptions |
C. Kaiser |
|
||
|
29 novembre 2005 |
15. Questions sur les projets de programmation concurrente |
C.
Kaiser |
|
||
|
30 novembre 2005 |
16.
Apercu : methodes de specification et de validation de la
concurrence |
J.F. Peyre |
|
||
|
06 decembre 2005 |
17. Expression et validation des paradigmes par reseaux de Petri |
J.F. Peyre |
|
||
|
07 decembre 2005 |
18. Presentation des outils de simulation et de validation et TP |
J.F. Peyre |
|
||
|
13 decembre 2005 |
19.
TP d'Utilisation des outils de simulation et de validation |
J.F. Peyre |
|
||
|
14 decembre 2005 |
20. Expression et validation de solutions par reseaux de Petri |
J.F. Peyre |
|
||
|
03 janvier 2006 |
21. Validation des solutions et reseaux de Petri; outils et TP |
J.F. Peyre |
|
||
|
04 janvier 2006 |
22. Validation des solutions et reseaux de Petri; outils et TP |
J.F. Peyre |
|
||
|
10 janvier 2006 |
23. Validation des solutions avec la logique temporelle (TP) |
J.F. Peyre |
|
||
|
11 janvier 2006 |
24. TP : outils de validation de la concurrence |
J.F. Peyre |
|
||
|
17 janvier 2006 |
25. TP : outils de validation de la concurrence |
J.F. Peyre |
|
||
|
18 janvier 2006 |
26. TP : outils de validation de la concurrence |
J.F. Peyre |
|
||
|
24 janvier 2006 |
27. TP : outils de
validation de la concurrence (projet) |
J.F. Peyre |
|
||
|
25 janvier 2006 |
28. TP : outils de
validation de la concurrence (projet) |
J.F. Peyre | |||
|
31 janvier 2006 |
29. TP : outils de
validation de la concurrence (projet) |
J.F. Peyre |
|
||
|
01 fevrier 2006 |
30. TP : outils de
validation de la concurrence (projet) |
J.F. Peyre | |||
examen 1ere session le mardi 8
fevrier 2006
(date probable, a confirmer ulterieurement). Examen avec
documents
examen 2eme session le mardi 11 avril 2006 (date probable, a confirmer
ulterieurement).
Examen avec
documents
Chaque auditeur doit realiser deux dossiers au cours de l'annee. Le
premier
dossier, a remettre le 3 janvier 2006, concerne la programmation d'une
petite
application concurrente. Le second dossier, a remettre le fin janvier
2006,
concerne la
validation d'une petite application concurrente (de preference la
meme
application pour ces deux dossiers). Chaque dossier permet d'obtenir un
bonus
de 0 a 5 points, a valoir sur la note de l'examen final.
Le total des boni est plafonne a 9 points. L'examen est obligatoire.
PLANNING
ACCOV 04-05 [version octobre
2004.pdf]
Le total des boni est plafonne a 9 points. L'examen est obligatoire.
Un site Web utilise 8 appareils webcam de surveillance et recupere des images avec un lot de serveurs connectes a des clients. On a l architecture suivante : ... voir la suite dans [ACCOV62SurveillanceWebcams.pdf]
On pourra programmer et comparer les solutions en Ada, Java, Posix. Non interblocage, equite. On pourra considerer la repartition de l application.
2. SYNOPTIQUE POUR SUIVRE PLUSIEURS USINES
Une societe qui possede 5 usines veut installer a son siege un ecran synoptique pour suivre l activite de ses usines. Apres avoir etudie le systeme d information et produit une architecture logique, cette societe fait appel a vous pour gerer la cooperation entre les processus concurrents de cette architecture.
... voir la suite dans [ACCOV63SynoptiqueUsine.pdf]
On pourra programmer et comparer les solutions en Ada, Java, Posix. Allocation equitable et sans interblocage. On pourra considerer la repartition de l application.
3. COOPERATION PAIR PAIR : PARADIGME DES CAMENEONS
Le but du projet est l etude de la synchronisation dans une relation de pair a pair, en se servant du paradigme des cameneons. ... voir la suite dans [ACCOV64Chameneos.pdf]
On pourra programmer une solution en Ada, Java, Posix . On pourra considerer du pair a pair de groupe. On pourra considerer la repartition de l application. Voir aussi l'examen de juin 2001.
canevas programmes projets 2004-05 : chameneos, synoptique, webcam
DOSSIER POUR CHAQUE PROJET
1. DOSSIER A FOURNIR
Plan du dossier a remettre. ... voir la suite dans [ACCOV61Dossier.pdf]
2. PLANNING DE TRAVAIL
2.1. Choix d un projet parmi les trois projets presentes ci-dessus
Constitution des binomes. Chaque binome choisit le projet qu'il prefere et me communique son choix avant le 7 novembre.
2.2. Premiere etape du dossier : reformulation et analyse du probleme.
Ecrire un cahier des charges comprenant les trois premieres phases du dossier, a savoir :
- l'architecture globale du projet
- la description du probleme de concurrence
- la specification de programmation de chaque composant, actif ou passif
- la simulation envisagee, la recette prevue pour tester la solution au probleme de concurrence
Remettre cette etape, quel que soit son etat, au plus tard le 1 decembre.
2.3. Deuxieme etape du dossier avec une premiere solution
Programmer une solution en Ada avec des objets proteges. Compiler et executer. Faire un dossier de programmation et donner les resultats obtenus par la simulation et pour la recette. Expliquer pourquoi le programme vous parait correct (enoncer les points delicats ou sensibles). Analyser la possibilite d interblocage (fournir une trace qui conduit a interblocage, si vous pouvez). Examiner comment faire une prevention d interblocage. Analyser la possibilite de famine (fournir une trace si possible). Cette etape est une application directe du cours.
Remettre cette premiere redaction au plus tard le 4 janvier, quel que soit l etat dans lequel elle se trouve.
2.4. Troisieme etape du dossier avec une seconde solution
Pour cette etape, correspondant a une evolution du probleme, vous pouvez choisir :
a) soit de developper une solution soit en Ada avec des taches serveurs, soit en Java, soit en Posix, et de comparer les styles et fiabilites de programmation entre la solution en objets proteges Ada et la solution nouvelle choisie
b) soit de programmer en Ada une solution repartie sur plusieurs sites.
Quel que soit votre choix (a, ou b), cette etape comporte a son tour
a. un cahier des charges
b. un dossier de programmation,
c. une analyse de la correction de la solution
Remettre cette seconde solution, completee par la premiere redaction mise a jour, en fevrier
2.5.
Quatrieme etape en forme de conclusion
Comparer les solutions des deux etapes
Comparer les styles et les facilites des langages pour la concurrence
(facilite de mise au point, evolutivite de solution, facteur d echelle
"scalability", documentation, possibilite de validation, etc...)
Ceci est a remettre en fevrier, avec la redaction finale revue et
corrigee a la suite de discussions pendant les derniers cours de
programmation concurrente.
retour debut ACCOV
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
SEANCE DE TRAVAUX PRATIQUES DE
PROGRAMMATION ADA
On vous donne le schema de base des producteurs et consommateurs
(c'est Deposer_Un et Retire_Un)
avec un programme d essai.
Le TP comporte trois composants : Global, Prod_Cons et Stock.
Le composant de communication entre les processus producteurs et consommateurs est
package Stock is
procedure Deposer_Un (X : in Message);
procedure Retirer_Un (X : out Message);
procedure Deposer_Deux (X, Y : in Message);
procedure Retirer_Deux (X, Y : out Message);
procedure Deposer (Z : in Tab_Message);
procedure Retirer (Z : out Tab_Message);
end Stock;
On vous demande de
programmer les
entrees
de l'objet protege appelees par les procedures qui permettent de
deposer et retirer deux messages lors d'un unique appel ou qui
permettent de deposer et retirer un
tableau
Z contenant un ou deux messages.
Dans ce dernier cas, la solution utilise
Un tableau dynamique Z
Z'Length qui fournit la longueur actuelle du tableau Z
une entry Poser_Bis et une entry Tirer_bis
et on utilise l'instruction requeue.
Les 4 modules de
bibliotheque :
Global.ads, Prod_Cons.ads, Stock.ads, Stock.adb, sont disponibles dans
[ACCOV2004TP.zip]
et [ACCOV2004TP.html]
Il vous faut completer le dernier module
une solution du TP est maintenant dans [ACCOV2004TP.zip]
vous trouverez aussi un autre exemple simple de programmation concurrente
avec un module generique pour un generateur aleatoire partage et sous controle d un objet protege
dans [ACCOV42Concurrents2003.zip]
**************************************
Pour telecharger compilateur Ada GNAT et l'essayer, visiter l'un des sites
ENSMA :: http://www.lisi.ensma.fr/ftp/enseignement/ada/
ACT Europe &GNAT :: http://libre.act-europe.fr/
Adalog :: http://perso.wanadoo.fr/adalog/freeada1.htm
ou un autre site obtenu par une recherche sur le web
On le trouve aussi par ftp au CNAM :: ftp.cnam.fr/pub/Ada/PAL/compiler/gnat/distrib
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
retour debut site ACCOV