Skip to end of metadata
Go to start of metadata

A Java 5 hozott néhány újdonságot a párhuzamos programozás terén, a Java 7 további könnyítéseket tartalmaz, amelyek közül az egyiket Fork/Join néven találjuk meg a dokumentációt böngészve, s a megoldás használatához csak három osztályt kell megismernünk:

Az elnevezésekből láthatjuk, hogy alapvetően hosszabb ideig tartó rekurzív feladatokra találták ki ezt a technológiát, mint a fájlrendszer felderítése vagy egy weboldal letöltése, de remekül használható matematikai és/vagy fizikai szimulációkhoz is. A RecursiveTask dokumentációs oldalán egy tipikus rekurzív feladat: a Fibonacci számsor kiszámolása a példa, nézzük meg közelebbről.

FibonacciTask.java
public class Fibonacci extends RecursiveTask<BigInteger>
{
  final Integer number;

  public Fibonacci(final Integer number)
  {
    this.number = number;
  }

  @Override
  public BigInteger compute()
  {
    if (number <= 1)
    {
      return new BigInteger("" + number);
    }

    final Fibonacci f1 = new Fibonacci(number - 1);
    f1.fork();

    final Fibonacci f2 = new Fibonacci(number - 2);
    f2.fork();

    return f2.join().add(f1.join());
  }
}

Két fontos dolgot kell észrevennünk:

  • Az osztály a RecursiveTask osztályból származik és implementálja a compute metódust az átadott BigInteger típus szerint (mivelhogy nagy számokkal dolgozunk).
  • Létrehozunk két példányt, amelyeket a fork használatával elindításra jelölünk, majd a join hívással várjuk meg az eredményeket.

A használatához kell egy új osztály, amely létrehozza a ForkJoinPool példányt, majd elindítja a folyamatot, ezt alább látjuk:

App.java
public class App
{
  public BigInteger computeFibonacci(Integer number)
  {
    final Fibonacci fibonacci = new Fibonacci(number);
    final ForkJoinPool fjPool = new ForkJoinPool(5);
    return fjPool.invoke(fibonacci);
  }
  public static void main(String[] args)
  {
    final Integer number = Integer.parseInt(args[0]);
    final App app = new App();
    System.out.println(app.computeFibonacci(number));
  }
}

Ez esetben a lényeg a computeFibonacci metódusban van, ahol létrehozunk egy új Fibonacci osztályt, egy új ForkJoinPool osztályt maximum öt szállal, majd egyszerűen az invoke használatával elindítjuk a többszálú folyamatot. A szálak számáról és a ForkJoinPool gondoskodik, a szálak indításáról és lezárásáról pedig a RecursiveTask ősosztályban megvalósított fork és join metódusok: a fejlesztőnek egyszerűen csak a feladatra kell koncentrálnia, minden mást megold a Java 7.

Megfelelően nagy számmal indítva – az 40 már bőven sok – láthatjuk, hogy egy négymagos (nyolcutas) i7 processzort szépen kiterhel öt szálon az adott java processz (495%):

PID  USER      PR  NI  VIRT  RES  SHR S   %CPU %MEM    TIME+  COMMAND
7268 auth.gab  20   0 1191m 391m 7024 S    495  5.0   8:26.22 java

Ha megnöveljük a használt szálak számát, akkor egészen a processzor végső határig tudjuk növelni a párhuzamosságot (736%):

PID  USER      PR  NI  VIRT  RES  SHR S   %CPU %MEM    TIME+  COMMAND
7442 auth.gab  20   0 1192m 369m 7008 S    736  4.7   1:52.95 java 

A kapott eredményt leellenőrizhetjük a maths.surrey.ac.uk adott oldalán; 40 esetén ez 102334155 kell legyen.

      
      
Page viewed times

4 Comments

  1. Anonymous

    Hova tunt a google-s bejelentkezes? Most nem latom.

    Nincs java7-em, igy nem tudom kiprobalni, de a fibonacci-t 40-re kiszamolni nem kellene, hogy 1 mp-nel tovabb tartson. Persze tudom, hogy ez a fibonacci csak egy eroltetett pelda, de az szerintem latszik belole, hogy nem feltetlenul eri meg parhuzamositani az algoritmusokat.

    Andras

    1. Auth Gábor AUTHOR

      Nyilván egy sima rekurzív metódushívásnál költségesebb a szálak kezelése, tehát akkor éri meg, ha összetettebb a párhuzamosítható feladat. Ha tudsz egyszerű és nem erőltetett példát, akkor ne tartsd magadban... (smile)

      Hova tunt a google-s bejelentkezes? Most nem latom.

      Lejárt az eval licenc és még nem kaptam újat. Utánanézek. Utánanéztem, már van licenc, elvileg működik is.

       

  2. Természetesen a Fibonacci számolás az egyik leggyakoribb példa. Azért használjuk lépten nyomon, mert nagyon egyszerű megérteni. Azért rossz példa, mert akár zárt alakban is megadható az n-edik elem.

    Ezeket a Java 7 konstrukciókat akkor lehet jól használni, amikor eddig is párhuzamos szálakat indítottál volna, ezt így egyszerűbb leírni.

  3. Anonymous

    Nem tartozik szorosan a cikkhez, de eljátszogattam a fenti példával és az jutott eszembe, mi lenne ha a rekurziós feltétel inkább ez lenne:

    if (number <= 2) {
        return new BigInteger("" + 1);
    }

    Mivel F(2) = F(1) + F(0) = 1 + 0 = 1 és F(1) = 1, gondoltam ezzel azt érem el hogy kevesebb művelet is elég lesz, hiszen nem fogja még az F(2)-t is párhuzamosítani.
    Meglepődtem, de nem ezt tapasztaltam. Kipróbáltam az eredeti és a módosított módszert is többször és azt tapasztaltam, hogy

    • változó a Fibonacci osztály példányosítások száma
    • a két módszerből jellemzően a módosított több példányosítást eredményez, viszont valamivel jobb időt

    Szóval egyrészt nem értem, miért nem konstans a példányosítások száma, másrészt hogy miért nem eredményez egyértelműen kevesebb példányosítást a módosított módszer.
    Ha esetleg valakinek van kedve játszani még vele, szívesen fogadom a választ! (smile)

    Példa nálam: (c a példányszám)

    F(40)_1 = 102334155, msec: 14070, c: 60786289 (eredeti)
    F(40)_2 = 102334155, msec: 13385, c: 65125964 (módosított)