Aumentar letras   Inicio   Información   Contactar   Mapa
Català   English

Programación Concurrente y Distribuida (PCD)

Créditos Dept.
6.0 ECTS LSI

Profesores

Responsable:  Xavier Messeguer Peypoch (peypoch@lsi.upc.edu)
Otros:Jorge Castro Rabal (castro@lsi.upc.edu)

Objectivos Generales

Se pretende que los estudiantes aprendan a diseñar e implementar programas concurrentes y distribuidos de forma segura y fiable. Para guiar a los estudiantes en las tareas de diseño se introduce el LST (Labelled System Analyser), un lenguaje de programación sencillo que permite diseñar, visualizar y analizar sistemas de transiciones. Con el fin de que los estudiantes tengan una visión más completa de la concurrencia y de los sistemas distribuidos, se enseñan otros modelos como por ejemplo las redes de Petri y el software diseñado para analizarlas. Con el fin de tener una visión completa de los pasos que van de la modelización a la implementación se realizan prácticas en el lenguaje de programación Java.

Objectivos Específicos

Conocimientos

  1. Que conozcan los sistemas de transición etiquetados como herramienta de diseño y análisis de los programas concurrentes y distribuidos.
  2. Que conozcan algún software, por ejemplo LTS, de diseño y análisis de sistemas de transición.
  3. Que conozcan las Redes de Petri como otro modelo formal de diseño y análisis, así como algún software específico de análisis.
  4. Que tengan una idea clara de los problemas básicos que pueden aparecer en programación concurrente y distribuida.
  5. Que conozcan las partes de Java relacionadas con programación concurrente y distribuida.

Habilidades

  1. Que los estudiantes puedan modelar y analizar a mano ejemplos muy sencillos de programas concurrentes mediante un sistema de transición etiquetado.
  2. Que puedan utilizar con fluidez una herramienta de análisis basado en sistemas de transición, por ejemplo el LTS.
  3. Que sepan utilizar las Redes de Petri como otro modelo formal de diseño y análisis, así como algún software específico de análisis de Redes de Petri.
  4. Que puedan utilizar con fluidez las partes de Java relacionadas con programación concurrente y distribuida.

Competencias

  1. Que puedan razonar de manera formal, empleando si hace falta programas, con objeto de poder decir si un diseño es o no correcto.
  2. Poder pasar de herramientas abstractas de diseño y análisis e implementaciones en lenguajes de programación, como por ejemplo Java.

Contenidos

Horas estimadas de:

T P L Alt L Ext. Est O. Ext.
Teoria Problemas Laboratorio Otras actividades Laboratorio externo Estudio Otras horas fuera del horario fijado

1. Sistemas de transición y álgebra de procesos.
T      P      L      Alt    L Ext. Est    O. Ext. Total 
4,0 4,0 2,0 0 2,0 8,0 0 20,0
Sistemas de transición y procesos primitivos. Operaciones de prefijo y selección. Procesos concurrentes y su ejecución. Descripción de los sistemas LTS. Implementación Java.

2. Objetos concurrentes, exclusión mutua y condiciones de sincronización, problema del deadlock.
T      P      L      Alt    L Ext. Est    O. Ext. Total 
4,0 4,0 2,0 0 2,0 9,0 0 21,0
Problema de la interferencia destructiva. Locks y exclusión mutua. Modelado de semáforos y del problema de los monitores imbricados. Problema de deadlock, análisis mediante LST.

3. Propiedades de seguridad (safety) y vivacidad (liveness).
T      P      L      Alt    L Ext. Est    O. Ext. Total 
4,0 4,0 2,0 0 2,0 9,0 0 21,0
Descripción y ejemplos de propiedades de seguridad e implementación mediante LTS. Descripción de las propiedades de vivacidad, en especial la de progreso, e implementación en LTS.

4. Paso de mensajes y arquitectura cliente/servidor, otras arquitecturas.
T      P      L      Alt    L Ext. Est    O. Ext. Total 
4,0 4,0 2,0 0 2,0 8,0 0 20,0
Paso de mensajes síncronos y asíncronos. Rendez-vous y arquitectura cliente servidor. Modelado en LTS.

Introducción a otras arquitecturas: pipelines de filtros, supervisor/trabajadores, anunciante/oyente.

5. Redes de Petri, modelo y algoritmos básicos.
T      P      L      Alt    L Ext. Est    O. Ext. Total 
4,0 4,0 2,0 0 2,0 9,0 0 21,0
Ejemplos de redes de Petri. Algoritmo de Karp y Miller.

Clases especiales de redes de Petri. Herramientas soft para analizar estas redes.

6. Redes de Petri; modelado.
T      P      L      Alt    L Ext. Est    O. Ext. Total 
4,0 4,0 2,0 0 2,0 9,0 0 21,0
Estudio de casos: "reordenamiento distribuido", exclusión mutua autoestabilizante, protocolos con mensajes ack.

7. Algoritmos en redes
T      P      L      Alt    L Ext. Est    O. Ext. Total 
4,0 4,0 2,0 0 2,0 8,0 0 20,0
Elección de líder, algoritmo de eco, exclusión mutua en red, consenso, árboles no dirigidos, autoestabilización.


Total por tipo T      P      L      Alt    L Ext. Est    O. Ext. Total 
28,0 28,0 14,0 0 14,0 60,0 0 144,0
Horas adicionales dedicadas a la evaluación 6,0
Total horas de trabajo para el estudiante 150,0

Metodología docente

En las clases de teoría se presentarán los conceptos básicos mediante ejemplos. En las clases de ejercicios, los estudiantes resolverán ejercicios sobre los temas de las clases de teoría. En las clases de laboratorio se verá cómo implementar estos problemas (o problemas parecidos) en Java. Tanto en clases de problemas como de laboratorio se podrán utilizar herramientas de diseño y análisis como el LTS.

Método de evaluación

Habrá examen final y nota de laboratorio. El examen será de problemas sobre la teoría explicada. La nota de laboratorio reflejará la calidad del trabajo realizado. La nota final será:

examen final*0.7 + laboratorio*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 complementaria

  • 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.

Enlaces web

  1. Obrir nova finestra http://www-dse.doc.ic.ac.uk/concurrency/


  2. Obrir nova finestra http://java.sun.com/


Capacidades previas

Buenos conocimientos de Java a nivel de clases y objetos.



 
logo FIB © Facultad de Informática de Barcelona - webmaster@fib.upc.edu - RSS RSS