CC61G Seminario de Programación Concurrente
Tarea Nro. 1

Prof.: Luis Mateu B.

Plazo de entrega: Lunes 6 de Septiembre a media noche.

Mecanismo de entrega: archivo zip a lmateu@dcc.uchile.cl.

Observación: entregue un zip que incluya (i) los programas pedidos, y (ii) un archivo en donde responde el texto que aparece en itálicas en este documento.

Problema 1: Fib Paralelo

  1. Estudie el programa ParFib.java.
  2. Compílelo.
  3. Ejecute java ParFib n 0 con n= 20, 25, 30.

    Ud. encontrará que para algunos n pequeños, la versión secuencial es más lenta que la paralela que usa exactamente un thread !y que por lo tanto invoca la versión secuencial!

    Explique por qué. Hint.: recuerde que hay un compilador JIT.

  4. Ejecute java ParFib 35 7

    Calcula fib(35) secuencialmente y en paralelo con 128 threads. Edite el programa y borre el mensaje computing paralell fib ... y re-ejecute el programa.

    Explique por qué la versión secuencial es más rápida que la versión paralela.

Problema 2: Factorial paralelo

  1. Estudie el programa Factorial.java.
  2. Compílelo.
  3. Ejecute java Factorial 20000

    Este programa usa BigInteger para calcular secuencialmente el número de dígitos del factorial de 20000.

    Escriba la clase ParFact que calcula factorial(n) in paralelo con 2^p threads. Tome ParFib como modelo.

  4. Ejecute java ParFact 20000 5

    Esta vez se usan 32 threads para calcular el factorial de 20000.

    Compare los tiempos de ejecución de la versión paralela y la versión secuencial.

    Explique por qué la versión paralela es tanto más rápida qué la versión secuencial considerando que se ejecuta en un monoprocesador.

  5. Explique como haría una versión secuencial eficiente para factorial. Sólo explique, no programe.

Problema 3: Diccionario

  1. Estudie el programa MTDict.java.
  2. Compílelo.
  3. Ejecute java MTDict

    Este programa nunca termina.

    Haga un diagrama de threads que muestre por qué este programa lanza NullPointerException en forma aleatoria.

  4. Se establece un cambio en la especificación de MTDict: si el método query encuentra que la llave no existe, query debe esperar hasta que algún otro threads agregue la llave.

    5. Cambie la implementación de MTDict para hacer que funcione de acuerdo a la nueva especificación.

  5. Pruebe su programa con MTDictVerifier.java

    Este programa le dirá si su implementación funciona como se pide.

  6. Estudie cuidadosamente la clase MTDict original.

    Discuta si es posible cambiar una pocas líneas en MTDict para hacer que funcione apropiadamente sin sicronizar el método query.

Problema 4: Búsqueda en árboles desordenados

  1. Estudie el programa incompleto Finder.java.

    El método seqLookup busca una palabra en un arbol binario desordenado. El método parLookup, aún no implementado, debe buscar una palabra en el árbol utilizando 2^p threads.

    Implemente el método parLookup.

  2. Observe el operador || en las invocaciones recursivas de seqLookup:

          seqLookup(info, node.left) || seqLookup(info, node.right);

    Modifique su implementación de tal forma que si un thread encuentra la palabra en el árbol, el resto de los threads detenga la búsqueda.

    Observación: ¡No use Thread.stop! Use una variable booleana compartida que se coloca en verdadero cuando un thread encontro la palabra. Todos los threads consultan esta variable en puntos estratégicos para decidir si continuar con la búsqueda.

    (Usar Thread.stop es poco robusto porque no se puede asegurar que un thread va a detenerse en un estado consistente.)

  3. Pruebe su solución con FinderVerifier.java.

    Este programa no termina nunca en su intento de encontrar alguna condición de borde que haga que su programe no funcione. En buenas cuenta si el programa no termina, quiere decir que funciona. Si termina, el programa no funciona y se le explicará por qué.

  4. Observe que el acceso a la variable booleana compartida no se sincroniza en absoluto.

    Discuta si este tipo de acceso es o no safe, i.e. no produce data-races.