Tarea #8 [solución]

Concurrencia para Java

      Utilice los ejemplos de implementaciones concurrentes Java que están en el artículo [DiMare-2010] para obtener 2 algoritmos que calculen las siguientes estadísticas en vectores Java:

• maxmin( A[], izq,der ): Retorna los valores máximo y mínimo del vector A[].
• burbuja( C[], l, r ): Usa el método de la burbuja para reacomodar C[] para que A[l] sea el menor valor desde C[l] hasta C[r-1].

      Sus 2 versiones de estos algorithmos deben usar hilos Java, y deben calcular efectuar en paralelo sus cálculos. Use el paradigma Map/Reduce en ambas implementaciones.

      Como base para su algoritmos maxmin() debe usar esta implementación tomada del curso del profesor Lodha 2001 de la Universidad de California en Santa Cruz [UCSC], impartido en el otoño de 2001:

http://classes.soe.ucsc.edu/cmps102/Fall01/solutions4.pdf

procedure maxmin(A[1...n] of numbers) -> (min, max)
begin
    if (n == 1)
        return (A[1], A[1])
    else if (n == 2)
        if( A[1] < A[2])
            return (A[1], A[2])
        else
            return (A[2], A[1])
    else
        (max_left, min_left) = maxmin(A[1...(n/2)])
        (max_right, min_right) = maxmin(A[(n/2 +1)...n])
        if (max_left < max_right)
            max = max_right
        else
            max = max_left
        if (min_left < min_right)
            max = min_left
        else
            min = min_right
        return (min, max)
end

      Modifique este algoritmo de manera que en el vector quede de primero el valor más pequeño y de último el más grande. Para lograrlo, debe sincronizar los hilos que se encargan de ejecutar cada llamado rercursivo a maxmin().

Algoritmo de la burbuja

      Para obtener su algoritmo Burbuja(), puede usar como base la implementación de la tarea programada:

/** Método que realiza el ordenamiento por "Burbuja". */
public void ordene(Contenedor_Ordenable C) {
    int i,j;
    for (i = C.dimension(); i > 0; --i) {
        for (j = 1; j < i; j++) {
            if ( C.esMenor(j, j-1) ) {
                C.intercambie(j, j-1);
            }
        }
    }
}

      Use 2 tareas que se encarguen de reacomodar concurrentemente la mitad de los valores, pero intercalando la sección del vector en que cada tarea trabaja. Por ejemplo, si el vector tiene 99 valores las dos tareas Tfrente y Tcola trabajarían sobre las partes del vector de la siguiente manera:

                            Tcola->Burbuja(C,50,99)
Tfrente->Burbuja(C,0,51) && Tcola->Burbuja(C,51,99)
Tfrente->Burbuja(C,1,52) && Tcola->Burbuja(C,52,99)
Tfrente->Burbuja(C,2,52) && Tcola->Burbuja(C,52,99)
Tfrente->Burbuja(C,3,53) && Tcola->Burbuja(C,53,99)
Tfrente->Burbuja(C,4,53) && Tcola->Burbuja(C,53,99)
...

Consulta:

Profe: estoy usando 2 semáforos para la burbuja pero siempre se me pone rojo el resultado ... esos mensajes no me salen si uso ... [adjunto] ...

Respuesta:

Al revisar tu implemntación me doy cuenta de que si le quitaras todos los semáforos aún así NO te funcionaría. Antes de implementar un algoritmo concurrente, uno tiene que asegurarse de que la versión secuencial (sin semáforos) funciona, pues de lo contrario otiene un enredo "en paralelo".
      Por eso, lo primero que hay que hacer es modificar el algoritmo maxmin() del enunciado para que funcione en Java. Por ejemplo, hay que usar índices adecuados para delimitar el rango de valores que maxmin() va a examinar, y eso no se puede hacer sin definir los índices del rango a delimtar:
  maxmin(A[1..n]) → NO compila
  maxmin(A[],l,r) → si compila

Para esta tarea programada usted debe enviarme estos archivos:

1. SelectMaxMin.java
2. CARNET.docx
3. CARNET.html
4. CARNET.url

Di Mare, Adolfo:

Introducción de la programación concurrente en el primer curso de programación, Artículo #12 de la Octava Conferencia del Latin American And Caribbean Consortium Of Engineering Institutions LACCEI-2010 (Consorcio de Escuelas de Ingeniería de Latinoamérica y del Caribe), realizado en la Universidad Católica de Santa María de Arequipa, Perú, junio 2010.
    http://www.di-mare.com/adolfo/p/cs1cp.htm

Entrega de Tareas

Soluciones

Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 2012
Derechos de autor reservados © 2012