Programació Concurrent i Distribuïda ( PCD )
| Crèdits: |
Departament: |
Tipus: |
Requisits: |
| 7.5 |
LSI |
Optativa per l'EI
Optativa per l'ETIG
Optativa per l'ETIS
|
|
PRED
- Pre-requisit per l' EI , ETIG
|
|
|
PS
- Pre-requisit per l' ETIS
|
|
|
Professors
| Responsable: | Joaquim Gabarró Vallés (gabarro lsi.upc.edu). |
| Altres: | Jorge Castro Rabal (castrolsi.upc.edu)
Xavier Messeguer Peypoch (messeguerlsi.upc.edu). |
Objectius Generals
Que els estudiants aprenguin a dissenyar i implementar programes concurrents i distribuïts de manera segura i fiable. Per guiar als estudiants en les tasques de disseny s'introdueix el LST (Labelled System Analyser), un llenguatge de programació senzill que permet dissenyar, visualitzar i analitzar sistemes de transicions. A fi de que els estudiants tinguin una visió més completa de la concurrència i dels sistèmes distribuïts s'ensenyen altres models com per exemple les xarxes de Petri i els software disenyat per analitzar-les. A fi de tenir una visió completa dels passos que van de la modelització a la implementació es fan pràctiques en el llenguatge de programació Java.
Objectius Específics
Coneixements
- Que coneguin els sistemes de transició etiquetas com a eina de disseny i anàlsisi dels programas concurrent i distribuïts.
- Que coneguin algun software, per exemple LTS, de disseny i anàlisi de sistemes de transició.
- Que coneguin les Xarxes de Petri com un altre model formal de disseny i anàlisi, així com algun software específic d'anàlisi.
- Que tinguin una idea clara dels problemes bàsics que poden apareixer en programació cocurrent i distribuïda.
- Que coneguin les parts de Java relacionades amb programació concurrent i distribuïda.
Habilitats
- Que als estudiants puguin modelitzar i analitzar a ma, exemples molt senzills de programes concurrents mitjaçant un sistemes de transició etiquetats.
- Que puguin utilitzar amb fluïdesa una eina d'anàlisi basada en sistemes de transició per exemple el LTS.
- Que pugin utilitzar les Xarxes de Petri com un altre model formal de disseny i anàlisi, així com algun software específic d'anàlisi de Xarxes de Petri.
- Que puguin utilitzar amb fluïdesa les parts de Java relacionades amb programació concurrent i distribuïda.
Competències
- Que puguin raonar de manera formal, emprant si cal programes, a fi de poder dir
si un disseny és o no correcte.
- Poder passar d'eines abstractes de disseny i anàlisi i implementacions en llenguatges de programació, com per exemple Java.
Continguts
Hores estimades de:
| T |
P |
L |
Alt |
L Ext. |
Est |
A Ext. |
| Teoria |
Problemes |
Laboratori |
Altres activitats |
Laboratori extern |
Estudi |
Altres hores fora d'horari fixat |
|
1. Sistemes de transició i álgebra de processos.
|
| T |
P |
L |
Alt |
L Ext |
Est |
A Ext |
Total |
| 4,0 |
4,0 |
2,0 |
0 |
2,0 |
8,0 |
0 |
20,0 |
|
|
Sistemes de transició i processos primitius. Operacions de prefix i tria. Processos concurrents i la seva execució. Descripció dels sistema LTS. Implementació en Java.
|
|
2. Objectes concurrents, exclusió mútua i condicions de sincronització, problema del deadlock.
|
| T |
P |
L |
Alt |
L Ext |
Est |
A Ext |
Total |
| 4,0 |
4,0 |
2,0 |
0 |
2,0 |
9,0 |
0 |
21,0 |
|
|
Problema de l'interferència destructiva. Locks i exclusió mútua. Modelització de semàfors i del problema dels monitors imbricats. Problema de deadlock, analisi mitjançant LST.
|
|
3. Propietats de seguretat (safety) i vivacitat (liveness).
|
| T |
P |
L |
Alt |
L Ext |
Est |
A Ext |
Total |
| 4,0 |
4,0 |
2,0 |
0 |
2,0 |
9,0 |
0 |
21,0 |
|
|
Descripció i exemples de propietats de seguretat i implementació mitjançant LTS. Descripció de les propitats de vivacitat, en especial la de progress, i implementació en LTS.
|
|
4. Pas de missatges i arquitectura client/servidor, altres arquitectures.
|
| T |
P |
L |
Alt |
L Ext |
Est |
A Ext |
Total |
| 4,0 |
4,0 |
2,0 |
0 |
2,0 |
8,0 |
0 |
20,0 |
|
Pas de missatges síncrons i asíncrons. Rendez-vous i arquitectura client servidor. modalització en LTS.
Inroducció a altres arquitectures: pilelines de filtres, suvervisor/treballadors, anunciant/oïent.
|
|
5. Xarxes de Petri, model i algorismes bàsics.
|
| T |
P |
L |
Alt |
L Ext |
Est |
A Ext |
Total |
| 4,0 |
4,0 |
2,0 |
0 |
2,0 |
9,0 |
0 |
21,0 |
|
Exemples de xarxes de Petri. Algorisme de Karp i Miller.
Classes especials de xarxes de Petri. Eines soft per analizar aquestes xarxes.
|
|
6. Xarxes de Petri; modelitzacio.
|
| T |
P |
L |
Alt |
L Ext |
Est |
A Ext |
Total |
| 4,0 |
4,0 |
2,0 |
0 |
2,0 |
9,0 |
0 |
21,0 |
|
|
Estudi de casos: "rearrangement distribuït", exclusió mútua autoestabilitzant, protocols amb missatges ack.
|
|
7. Algorismes en xarxes
|
| T |
P |
L |
Alt |
L Ext |
Est |
A Ext |
Total |
| 4,0 |
4,0 |
2,0 |
0 |
2,0 |
8,0 |
0 |
20,0 |
|
|
Elecció de lider, algorisme de eco, exclusió mútua en xarxa, consens, arbres no dirigits, autoestabilització.
|
| - Total per tipus |
T |
P |
L |
Alt |
L Ext |
Est |
A Ext |
Total |
| 28,0 |
28,0 |
14,0 |
0 |
14,0 |
60,0 |
0 |
144,0 |
- Hores addicionals dedicades a l'avaluació:
|
6,0 |
- Total hores de treball per l'estudiant |
150,0 |
|
Metodologia docent
A les classes de teoria s'introduiran els conceptes bàsics mitjançant exemples. En les classes d'exercicis, els estudiants, resoldran exercicis sobre els temes de de les classes de teoria. En les classes de laboratori es veurà com implementar aquests problemes (o problemes semblants) en Java. Tant en classes de problemes com de laboratori es podrà utilitzar eines de disseny i anàlisi com el LTS.
Mètode d'avaluació
Hi haurà examen final i nota de laboratori. L'exàmen serà de problemes sobre la teoria explicada. La nota de laboratori reflectirà la qualitat del treball realitzat. La nota final serà:
examen final*0.7 + laboratori*0.3
Bibliografía bàsica
- Magee, Jeff Cramer, Jeff Concurrency, state models & Java programs, Wiley, 1999.
- Reisig, Wolfgang Elements of distributed algorithms, modeling and analysis with Petri nets, Springer, 1988.
- Perterson, James Petri net theory and the modeling of systems, Prentice-Hall, 1981.
- Tomás, José i d'altres Programación concurrente, Thomson, 2003.
- Tel, G. Introduction to distributed algorithms, Cambridge, 1994.
Bibliografía complementària
- Lea, Doug Concurrent programming in Java (hi ha traducció al castellà), Addison Wesley, 1999.
- Lewis, Bill, Berg, Daniel Multithreading programming with Java (existeix traducció al castellà), Prentica-Hall , 2000.
Enllaços web
-
 http://www-dse.doc.ic.ac.uk/concurrency/
El lloc de referència pel LTS i per la primera part del curs.
-
http://java.sun.com/
Molt interessant per tot el que és de Java.
Capacitats prèvies
Bons coneixements de Java a nivell de classes i objectes.
|
fib.upc.edu