DHW server 
English Español bajar/down

Alejandro Bia: Concurrent Programming


Programación Concurrente
Concurrent Programming

Temario

Objetivos de las asignatura y competencias

El principal objetivo es introducir al alumno en el paradigma de la programación concurrente y en el uso de las herramientas y técnicas utilizadas en general por los lenguajes concurrentes.

La asignatura está centrada en la descripción de los principios y metodologías de la programación concurrente, en los problemas derivados de la ejecución paralela de procesos y en las técnicas y herramientas existentes para resolver estos problemas.

En primer lugar, se introducirán los conceptos, técnicas y herramientas básicas de esta disciplina informática. Para ello, se abordarán los problemas clásicos de los sistemas concurrentes proponiéndose diversas soluciones. Paralelamente se verán ejemplos basados en los lenguajes concurrentes Pascal-FC y Java.

Al finalizar el curso, el alumno habrá adquirido la destreza y conocimientos necesarios para reconocer una aplicación paralela y resolverla mediante la construcción de algoritmos concurentes.


Objetivos específicos:

  • Reconocer las aplicaciones concurrentes.
  • Conocer las técnicas y algoritmos empleados en la programación concurrente.
  • Construir aplicaciones concurrentes mediante la utilización de los lenguajes Pascal-FC y Java.

Métodos docentes

Se realizarán clases teóricas y prácticas en laboratorios. Ver horarios.


Método de aprendizaje

El alumno debe comenzar leyendo el texto base, intentando comprender los conceptos que en él se exponen: problemas típicos de la concurrencia: sincronización condicional, exclusión mutua e interbloqueo (deadlock).

El libro está lleno de ejemplos con los que se explican las distintas posibles soluciones para cada problema, dependiendo del resultado final que se quiera obtener.

Es importante que después de asimilar los problemas y sus soluciones el alumno intente resolverlos por sí mismo aplicando distintas herramientas y enfoques. Se sugiere comenzar por los ejemplos resueltos en el propio libro.


Tipo de exámenes y evaluaciones

Modalidad de asistencia regular: Evaluación continua, parciales y entregas de trabajos prácticos y/o monográficos.

Modalidad libre: Examen final.

Ver modalidades.


Contenido general

Los principales temas a tratar son los siguientes (ver temario detallado más abajo):

  • ¿Qué es la programación Concurrente?
  • Introducción: conceptos de concurrencia
  • Multiprogramación
  • Multitarea
  • Ejecución concurrente
  • Problemas de programación concurrente
  • Objetos compartidos y exclusión Mutua
  • Regiones críticas
  • Deadlock (interbloqueo)
  • Procesos e hilos
  • Programación concurrente orientada a objetos (hilos en Java)
  • Semáforos
  • Monitores y sincronización
  • Paso de mensajes

Temario detallado


MÓDULO 1: Conceptos fundamentales

PARTE 1: Conceptos fundamentales

  1. Introducción
  2. Hitos en la programación concurrente
  3. Concepto de programación concurrente
    • Programa y proceso
    • Concurrencia
    • Definiciones de Proceso
      • Colaboración o Competencia
      • Comunicación y sincronización entre procesos
    • Programación concurrente
  4. Beneficios de la programación concurrente
    • Velocidad de ejecución
    • Solución de problemas inherentemente concurrentes
      • Sistemas de control
      • Tecnologías Web
      • Aplicaciones basadas en interfaces de usuarios
      • Simulación
      • Sistemas Gestores de Bases de Datos
      • Sistemas multiusuario
  5. Concurrencia y arquitecturas hardware
    • Sistemas monoprocesador
    • Sistemas multiprocesador
    • Sistemas fuerte y débilmente acoplados
    • Variables compartidas vs. Paso de mensajes
    • Algunos conceptos importantes
      • Programación concurrente
      • Programación paralela
      • Programación distribuida
  6. Especificación de ejecución concurrente
    • ¿Qué se puede ejecutar concurrentemente?
    • Condiciones de Bernstein
    • Cómo especificar la ejecución concurrente
      • Grafos de precedencia
      • Sentencias COBEGIN-COEND
  7. Características de los sistemas concurrentes
    • Orden de ejecución de las instrucciones
    • Indeterminismo
  8. Problemas inherentes a la programación concurrente
    • Exclusión mutua
      • Condiciones de Bernstein
      • Secciones críticas
    • Condición de sincronización
  9. Corrección de programas concurrentes
    • Propiedades de seguridad
    • Propiedades de vivacidad
  10. Preguntas y ejercicios

PARTE 2: Procesos y Pascal-FC

  1. Procesos
    • Estados de un proceso
    • Disposición en memoria de un proceso
      • Espacio de usuario y espacio del núcleo
      • Bloque de control del proceso o PCB
      • Estructura de un proceso en el SO Unix
      • Varios procesos en un SO multitarea
  2. Procesos en Pascal-FC
    • Pascal-FC vs. Pascal
    • Estructura de un programa Pascal-FC
    • Declaración de procesos
    • Estados de un proceso en Pascal-FC
    • Gestión de procesos en Pascal-FC
    • Planificación de procesos en Pascal-FC
    • Modos FAIR y UNFAIR
    • Ejecución de un programa en Pascal-FC
    • El manual de referencia de Pascal-FC

PARTE 3: Hilos y Java

  1. Hilos
    • Introducción
    • Concurrencia a dos niveles: procesos e hilos
    • Entidades pesadas y ligeras
    • Hilos de usuario e hilos del sistema
    • Estándares de hilos
    • Implementación de hilos
    • Planificación de hilos
      • Muchos hilos en un procesador lógico
      • Un hilo por procesador lógico
      • Muchos hilos en muchos procesadores lógicos (estricto)
      • Muchos hilos en muchos procesadores lógicos (no estricto)
  2. Hilos en Java
    • Introducción al lenguaje Java
      • Del IDE al Hardware
      • Java es multiplataforma
      • Java es compilado e interpetado
      • Ejecución en la Máquina Virtual Java
    • Hilos y objetos
    • Creación de hilos
      • Heredando de Thread y redefiniendo el método run
      • Implementando la interfaz Runnable
      • Comparación de ambos métodos
      • Objeto autónomo en un hilo
    • Estados de un hilo en Java
    • Planificación y prioridades
    • Hilos daemon (demonios)
    • Los principales métodos de la clase Thread

PARTE 4: Primeras aproximaciones a la solución de los problemas de la programación concurrente

  1. Introducción
    • Procesos que compiten
    • Procesos cooperan compartiendo información
    • Procesos cooperan mediante el paso de mensajes
    • Historia: de Dijkstra a hoy
  2. Tipos de sincronización y su solución
    • Exclusión mutua
      • Protocolos de entrada y de salida
      • Exclusión mutua
      • Limitación en la espera
      • Progreso en la ejecución
    • Condición de sincronización
    • Soluciones a los dos tipos de sincronización
      • Inhibición de las interrupciones.
      • Soluciones basadas en variables compartidas:
        • Espera ocupada (busy waiting)
        • Semáforos
        • Regiones críticas
        • Regiones críticas condicionales
        • Monitores
      • Soluciones basadas en el paso de mensajes:
        • Operaciones de paso de mensajes send/receive
        • Llamadas a procedimientos remotos
        • Invocaciones remotas
  3. Espera-Ocupada para la exclusión mutua (soluciones software)
    • Algoritmos no eficientes
      • Primer intento
      • Segundo intento (alternancia)
      • Tercer intento (falta de exclusión mutua)
      • Cuarto intento (espera infinita)
      • Quinto intento (tratamiento de cortesía)
    • Algoritmo de Dekker
    • Algoritmo de Peterson
    • Algoritmo incorrecto de Hyman
    • Algoritmo de Eisenberg-McGuire
    • Algoritmo de Lamport
  4. Espera-Ocupada para la exclusión mutua (soluciones hardware)
    1. Instrucción exchange
    2. Instrucción de decremento/incremento
    3. Instrucción testset
  5. Resumen
  6. Preguntas y ejercicios

MÓDULO II: Primitivas de sincronización basadas en memoria compartida

PARTE 5. Semáforos

  1. Introducción
  2. Definición de semáforo
  3. Resolución de problemas usando semáforos
    • Exclusión mutua y condición de sincronización
    • Problemas clásicos
      • El problema del productor/consumidor
      • El problema de los lectores y escritores
      • El problema de la comida de filósofos
  4. Inconvenientes del mecanismo de los semáforos

PARTE 6. Regiones críticas condicionales

  1. Introducción
  2. Definición de región crítica condicional
  3. Resolución de problemas usando regiones críticas condicionales
    • El problema del productor/consumidor
    • El problema de lectores y escritores
      • Prioridad en la lectura
      • Prioridad en la escritura
    • El problema de la comida de filósofos
  4. Inconvenientes del mecanismo de regiones críticas condicionales

PARTE 7. Monitores

  1. Introducción
  2. Definición de monitor
  3. Condición de sincronización en monitores
    • Bloqueo de procesos. Operación delay
    • Desbloqueo de procesos. Operación resume
    • La función empty
  4. Resolución de problemas usando monitores
    • El problema del productor/consumidor
    • El problema de los lectores y escritores
      • Prioridad en la lectura
      • Prioridad en la escritura
    • El problema de la comida de filósofos

MÓDULO III: Paso de mensajes

A modo de introducción al tema, se recomienda ver la sección 8 de los apuntes colgados en la sección de materiales.

PARTE 8. Mecanismo de paso de mensaje

  1. Introducción
  2. Identificación en el proceso de comunicación
  3. Sincronización
  4. Canal de comunicación y mensajes
  5. Condiciones de error en los sistemas de paso de mensajes
  6. Espera selectiva

PARTE 9. Paso de mensaje asíncrono

  1. Introducción
  2. Resolución de problemas empleando paso de mensaje asín­crono
    • El problema del productor/consumidor
    • El problema de los lectores y escritores
      • Prioridad en la lectura
      • Prioridad en la escritura
    • El problema de la comida de filósofos

PARTE 10. Paso de mensaje síncrono con canales

  1. Introducción
  2. Comunicación mediante canales en Pascal-FC
    • Espera selectiva básica
    • Espera selectiva con guardas
    • Espera selectiva con la alternativa termínate
    • Espera selectiva con la alternativa else
    • Espera selectiva con la alternativa timeout
    • Espera selectiva con prioridad
  3. Resolución de problemas empleando canales en Pascal-FC
    • El problema del productor/consumidor
    • El problema de los lectores y escritores
      • Prioridad en la lectura
      • Prioridad en la escritura
    • El problema de la comida de los filósofos

PARTE 11. Invocación remota y llamada a procedimiento remoto (RPC)

  1. Introducción
  2. Invocación remota
    • Sentencia ACCEPT
    • Espera selectiva. Alternativas
  3. Resolución de problemas mediante invocación remota en Pascal-FC
    • El problema del productor/consumidor
    • El problema de los lectores y escritores
      • Prioridad en la lectura
      • Prioridad en la escritura
    • El problema de la comida de filósofos


Subir / Up


Contact: DHWorkgroup