Ostateczny cel puli wątków i rozwidlenia / łączenia jest podobny: oba chcą maksymalnie wykorzystać dostępną moc procesora, aby uzyskać maksymalną przepustowość. Maksymalna przepustowość oznacza, że jak najwięcej zadań powinno być wykonanych w długim okresie. Co jest do tego potrzebne? (W poniższym przykładzie założymy, że nie brakuje zadań obliczeniowych: zawsze jest wystarczająco dużo do zrobienia dla 100% wykorzystania procesora. Dodatkowo używam „CPU” jako odpowiedników rdzeni lub wirtualnych rdzeni w przypadku hiperwątkowości).
- Przynajmniej musi być uruchomionych tyle wątków, ile jest dostępnych procesorów, ponieważ uruchomienie mniejszej liczby wątków pozostawi rdzeń niewykorzystany.
- Maksymalnie musi być uruchomionych tyle wątków, ile jest dostępnych procesorów, ponieważ uruchomienie większej liczby wątków spowoduje dodatkowe obciążenie dla harmonogramu, który przypisuje procesory do różnych wątków, co powoduje, że część czasu procesora przechodzi do harmonogramu, a nie do naszego zadania obliczeniowego.
W ten sposób ustaliliśmy, że dla maksymalnej przepustowości musimy mieć dokładnie taką samą liczbę wątków jak procesory. W rozmytym przykładzie Oracle można zarówno wziąć pulę wątków o stałym rozmiarze z liczbą wątków równą liczbie dostępnych procesorów, albo użyć puli wątków. To nie ma znaczenia, masz rację!
Kiedy więc będziesz mieć kłopoty z pulami wątków? Dzieje się tak, jeśli wątek blokuje się , ponieważ Twój wątek czeka na zakończenie innego zadania. Przyjmijmy następujący przykład:
class AbcAlgorithm implements Runnable {
public void run() {
Future<StepAResult> aFuture = threadPool.submit(new ATask());
StepBResult bResult = stepB();
StepAResult aResult = aFuture.get();
stepC(aResult, bResult);
}
}
Widzimy tutaj algorytm, który składa się z trzech kroków A, B i C.A i B można wykonać niezależnie od siebie, ale krok C wymaga wyniku kroku A AND B. To, co robi ten algorytm, to przesłanie zadania A do puli wątków i wykonaj zadanie b bezpośrednio. Następnie wątek będzie czekał na wykonanie zadania A i będzie kontynuował od kroku C. Jeśli A i B zostaną zakończone w tym samym czasie, wszystko jest w porządku. Ale co, jeśli A trwa dłużej niż B? Może tak być, ponieważ dyktuje to natura zadania A, ale może też tak być, ponieważ na początku nie ma wątku dla zadania A i zadanie A musi czekać. (Jeśli dostępny jest tylko jeden procesor, a zatem pula wątków ma tylko jeden wątek, spowoduje to nawet zakleszczenie, ale na razie nie ma to znaczenia). Chodzi o to, że wątek, który właśnie wykonał zadanie Bblokuje cały wątek . Ponieważ mamy taką samą liczbę wątków jak procesory, a jeden wątek jest zablokowany, oznacza to, że jeden procesor jest bezczynny .
Fork / Join rozwiązuje ten problem: w ramach fork / Join napisałbyś ten sam algorytm w następujący sposób:
class AbcAlgorithm implements Runnable {
public void run() {
ATask aTask = new ATask());
aTask.fork();
StepBResult bResult = stepB();
StepAResult aResult = aTask.join();
stepC(aResult, bResult);
}
}
Wygląda tak samo, prawda? Jednak wskazówka jest taka, aTask.join że nie będzie blokować . Zamiast tego w grę wchodzi kradzież pracy : wątek rozejrzy się za innymi zadaniami, które zostały rozwidlone w przeszłości i będzie kontynuował te. Najpierw sprawdza, czy zadania, które sam rozwidliły, rozpoczęły przetwarzanie. Więc jeśli A nie został jeszcze uruchomiony przez inny wątek, zrobi A następny, w przeciwnym razie sprawdzi kolejkę innych wątków i wykradnie ich pracę. Po zakończeniu tego innego zadania innego wątku sprawdzi, czy A jest teraz zakończone. Jeśli jest to powyższy algorytm może wywołać stepC. W przeciwnym razie będzie szukał kolejnego zadania do kradzieży. W ten sposób pule rozwidleń / złączeń mogą osiągnąć 100% wykorzystanie procesora, nawet w obliczu działań blokujących .
Jest jednak pułapka: kradzież pracy jest możliwa tylko na joinwezwanie ForkJoinTasks. Nie można tego zrobić w przypadku zewnętrznych akcji blokujących, takich jak oczekiwanie na inny wątek lub oczekiwanie na akcję we / wy. A co z tym, czekanie na zakończenie operacji we / wy jest częstym zadaniem? W takim przypadku, gdybyśmy mogli dodać dodatkowy wątek do puli Rozwidlania / Łączenia, który zostanie zatrzymany ponownie, gdy tylko akcja blokowania zostanie zakończona, będzie drugą najlepszą rzeczą do zrobienia. I ForkJoinPoolfaktycznie może to zrobić, jeśli używamy ManagedBlockers.
Fibonacci
W JavaDoc for RecursiveTask znajduje się przykład obliczania liczb Fibonacciego za pomocą Fork / Join. Aby zapoznać się z klasycznym rozwiązaniem rekurencyjnym, zobacz:
public static int fib(int n) {
if (n <= 1) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
Jak wyjaśniono w JavaDocs, jest to całkiem prosty sposób obliczania liczb Fibonacciego, ponieważ ten algorytm ma złożoność O (2 ^ n), podczas gdy prostsze sposoby są możliwe. Jednak ten algorytm jest bardzo prosty i łatwy do zrozumienia, więc trzymamy się go. Załóżmy, że chcemy to przyspieszyć za pomocą Fork / Join. Naiwna implementacja wyglądałaby tak:
class Fibonacci extends RecursiveTask<Long> {
private final long n;
Fibonacci(long n) {
this.n = n;
}
public Long compute() {
if (n <= 1) {
return n;
}
Fibonacci f1 = new Fibonacci(n - 1);
f1.fork();
Fibonacci f2 = new Fibonacci(n - 2);
return f2.compute() + f1.join();
}
}
Kroki, na które podzielone jest to zadanie, są zbyt krótkie i dlatego będą działać okropnie, ale możesz zobaczyć, jak szkielet ogólnie działa bardzo dobrze: dwa szczyty można obliczyć niezależnie, ale wtedy potrzebujemy ich obu do zbudowania ostatecznego wynik. Więc połowa jest zrobiona w innym wątku. Baw się dobrze, robiąc to samo z pulami wątków bez zakleszczenia (możliwe, ale nie tak proste).
Tylko dla kompletności: jeśli faktycznie chcesz obliczyć liczby Fibonacciego za pomocą tego rekurencyjnego podejścia, oto zoptymalizowana wersja:
class FibonacciBigSubtasks extends RecursiveTask<Long> {
private final long n;
FibonacciBigSubtasks(long n) {
this.n = n;
}
public Long compute() {
return fib(n);
}
private long fib(long n) {
if (n <= 1) {
return 1;
}
if (n > 10 && getSurplusQueuedTaskCount() < 2) {
final FibonacciBigSubtasks f1 = new FibonacciBigSubtasks(n - 1);
final FibonacciBigSubtasks f2 = new FibonacciBigSubtasks(n - 2);
f1.fork();
return f2.compute() + f1.join();
} else {
return fib(n - 1) + fib(n - 2);
}
}
}
Dzięki temu podzadania są znacznie mniejsze, ponieważ są dzielone tylko wtedy, gdy n > 10 && getSurplusQueuedTaskCount() < 2jest prawdziwe, co oznacza, że istnieje znacznie więcej niż 100 wywołań metod do ( n > 10) i nie czekają już zadania bardzo man ( getSurplusQueuedTaskCount() < 2).
Na moim komputerze (4 rdzenie (8, licząc Hyper-Threading), procesor Intel (R) Core (TM) i7-2720QM @ 2,20 GHz) fib(50)zajmuje to 64 sekundy przy klasycznym podejściu i zaledwie 18 sekund przy podejściu Fork / Join, które to dość zauważalny zysk, choć nie tak duży, jak teoretycznie możliwy.
Podsumowanie
- Tak, w twoim przykładzie Fork / Join nie ma przewagi nad klasycznymi pulami wątków.
- Rozwidlanie / łączenie może drastycznie poprawić wydajność podczas blokowania
- Rozwidlenie / łączenie pozwala uniknąć niektórych problemów z zakleszczeniem