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:
- RecursiveAction – visszatérési érték nélküli feladat
- RecursiveTask – visszatérési értéket adó feladat
- ForkJoinPool – a szálakat kezelő osztály (thread pool)
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.
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:
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.
4 Comments
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
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...
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.
Peter Verhas
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.
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:
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
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!
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)