포크 / 조인 프레임 워크가 스레드 풀보다 나은 점은 무엇입니까?

포크 / 조인 프레임 워크가 스레드 풀보다 나은 점은 무엇입니까?

---

처음에는 큰 작업을 N 개의 하위 작업으로 나누고 ( Executors 의 캐시 된 스레드 풀로 ) 각 작업이 완료되기를 기다리는 것보다 새로운 fork / join 프레임 워크 를 사용하면 어떤 이점이 있습니까? 포크 / 조인 추상화를 사용하여 문제를 단순화하거나 현재 몇 년 동안 솔루션을보다 효율적으로 만드는 방법을 알지 못합니다.

예를 들어, 튜토리얼 예제 의 병렬화 된 흐림 알고리즘은 다음 과 같이 구현 될 수 있습니다.

public class Blur implements Runnable {
    private int[] mSource;
    private int mStart;
    private int mLength;
    private int[] mDestination;

    private int mBlurWidth = 15; // Processing window size, should be odd.

    public ForkBlur(int[] src, int start, int length, int[] dst) {
        mSource = src;
        mStart = start;
        mLength = length;
        mDestination = dst;
    }

    public void run() {
        computeDirectly();
    }

    protected void computeDirectly() {
        // As in the example, omitted for brevity
    }
}

처음에 분할하여 작업을 스레드 풀로 보냅니다.

// source image pixels are in src
// destination image pixels are in dst
// threadPool is a (cached) thread pool

int maxSize = 100000; // analogous to F-J's "sThreshold"
List<Future> futures = new ArrayList<Future>();

// Send stuff to thread pool:
for (int i = 0; i < src.length; i+= maxSize) {
    int size = Math.min(maxSize, src.length - i);
    ForkBlur task = new ForkBlur(src, i, size, dst);
    Future f = threadPool.submit(task);
    futures.add(f);
}

// Wait for all sent tasks to complete:
for (Future future : futures) {
    future.get();
}

// Done!

작업은 스레드 풀의 대기열로 이동하여 작업자 스레드가 사용 가능 해지면 실행됩니다. 분할이 충분히 세분화되고 (특히 마지막 작업을 기다릴 필요가 없도록) 스레드 풀에 충분한 (최소 N 개의 프로세서) 스레드가 있으면 모든 프로세서는 전체 계산이 완료 될 때까지 최고 속도로 작동합니다.

뭔가 빠졌습니까? 포크 / 조인 프레임 워크를 사용하면 어떤 부가 가치가 있습니까?

---

기본적인 오해는 포크 / 조인 예제가 작업 도용을 보여 주지 않고 일종의 표준 나누기와 정복 만 보여주는 것이라고 생각합니다 .

작업 도용은 다음과 같습니다. 작업자 B가 작업을 완료했습니다. 그는 친절한 사람이므로 주위를 둘러보고 작업자 A가 여전히 열심히 일하는 것을 봅니다. 그는 걸어 다니며 물었다. "이봐, 난 너에게 손을 줄 수있어." 답글입니다. "쿨, 나는 1000 단위 의이 작업이 있습니다. 지금까지 나는 345 떠나 655를 완료했습니다. 당신은 번호 673에서 1000에 대해 작업을 할 수 있습니까, 나는 346에서 672를 할 것입니다." B는 "좋아요, 먼저 술집에 갈 수 있도록 시작하겠습니다"라고 말합니다.

알다시피-노동자는 실제 작업을 시작할 때도 서로 의사 소통해야합니다. 이것은 예제에서 빠진 부분입니다.

반면에 예는 "하청 업체 사용"과 같은 것만 보여줍니다.

Worker A : "Dang, 나는 1000 단위의 일을하고있다. 나에게 너무 많은 일이다. 나는 500을 직접하고 다른 사람에게 500을 하청 할 것이다." 이는 큰 작업이 각각 10 개 단위의 작은 패킷으로 분류 될 때까지 계속됩니다. 이들은 가능한 노동자들에 의해 처형 될 것입니다. 그러나 하나의 패킷이 일종의 독약이고 다른 패킷보다 상당히 오래 걸리면 (불운) 분할 단계는 끝납니다.

Fork / Join과 작업을 미리 분할하는 것의 유일한 차이점은 다음과 같습니다. 미리 분할 할 때 작업 큐가 시작부터 바로 가득 찼습니다. 예 : 1000 단위, 임계 값은 10이므로 큐에 100 개의 항목이 있습니다. 이 패킷은 스레드 풀 멤버에 분배됩니다.

포크 / 조인은 더 복잡하며 큐의 패킷 수를 더 작게 유지하려고합니다.

• 1 단계 : (1 ... 1000)을 포함하는 하나의 패킷을 대기열에 넣습니다.
• 2 단계 : 한 작업자가 패킷을 팝 (1 ... 1000)하여 두 개의 패킷 (1 ... 500) 및 (501 ... 1000)으로 바꿉니다.
• 3 단계 : 한 근로자가 패킷 (500 ... 1000)을 팝하고 (500 ... 750) 및 (751 ... 1000)을 푸시합니다.
• n 단계 : 스택에는 (1..500), (500 ... 750), (750 ... 875) ... (991..1000) 패킷이 포함됩니다.
• n + 1 단계 : 패킷 (991..1000)이 팝되어 실행됩니다.
• 단계 n + 2 : 패킷 (981..990)이 팝되어 실행됩니다
• 단계 n + 3 : 패킷 (961..980)이 팝되어 (961 ... 970) 및 (971..980)으로 분할됩니다. ....

다음을 참조하십시오. 포크 / 조인에서 큐가 더 작고 (예에서 6) "분할"및 "작업"단계가 인터리브됩니다.

여러 근로자가 동시에 튀어 나오면서 밀릴 때 상호 작용은 분명하지 않습니다.

---

사용중인 스레드가 모두 100 %로 독립적으로 작동하는 경우에는 포크 조인 (FJ) 풀의 n 스레드보다 낫습니다. 그러나 결코 그런 식으로 작동하지 않습니다.

문제를 n 개의 동일한 조각으로 정확하게 분할하지 못할 수 있습니다. 그럼에도 불구하고 스레드 스케줄링은 공정하지 않은 방법입니다. 가장 느린 스레드를 기다리게됩니다. 여러 작업이있는 경우 각각 n-way 병렬 처리 (일반적으로 더 효율적)로 실행할 수 있지만 다른 작업이 완료되면 n-way로 올라갈 수 있습니다.

그렇다면 문제를 FJ 크기로 잘라서 스레드 풀 작업을 해보는 것이 어떻습니까? 일반적인 FJ 사용법은 문제를 작은 조각으로 줄입니다. 이를 무작위 순서로 수행하려면 하드웨어 수준에서 많은 조정이 필요합니다. 오버 헤드는 살인자 일 것입니다. FJ에서 태스크는 스레드가 LIFO / 스택 (Last In First Out) 순서로 읽는 큐에 배치되며, 작업 도용 (핵심 작업의 경우)은 선입 선출 (FIFO / "대기열)입니다. 결과적으로 긴 배열 처리는 작은 덩어리로 나눠 지더라도 순차적으로 수행 될 수 있습니다. (한 빅뱅에서 작은 크기의 덩어리로 문제를 나누는 것이 사소한 일이 아닐 수도 있습니다. 균형없이 어떤 형태의 계층 구조를 다루는 것을 말합니다.)

결론 : FJ를 사용하면 고르지 않은 상황에서 하드웨어 스레드를보다 효율적으로 사용할 수 있으며, 스레드가 둘 이상인 경우 항상 그렇습니다.

---

스레드 풀과 Fork / Join의 궁극적 인 목표는 모두 같습니다. 둘 다 처리량을 최대화하기 위해 최대한 사용 가능한 CPU 성능을 활용하려고합니다. 최대 처리량은 가능한 많은 작업을 장기간 완료해야 함을 의미합니다. 그렇게하려면 무엇이 필요합니까? (다음은 계산 작업이 부족하지 않다고 가정합니다. 100 % CPU 사용에는 항상 충분한 양이 있습니다. 또한 하이퍼 스레딩의 경우 코어 또는 가상 코어에 대해 "CPU"를 동일하게 사용합니다).

1. 최소한의 스레드를 실행하면 코어가 사용되지 않기 때문에 사용 가능한 CPU 수만큼 스레드를 실행해야합니다.
2. 더 많은 스레드를 실행하면 다른 스레드에 CPU를 할당하는 스케줄러에 추가로드가 발생하여 일부 CPU 시간이 계산 작업이 아닌 스케줄러로 이동하기 때문에 최대한 많은 스레드가 실행 중이어야합니다.

따라서 우리는 최대 처리량을 위해 CPU와 정확히 같은 수의 스레드가 필요하다는 것을 알았습니다. Oracle의 모호한 예에서 사용 가능한 CPU 수와 동일한 스레드 수로 고정 크기 스레드 풀을 사용하거나 스레드 풀을 사용할 수 있습니다. 차이가 없습니다, 당신 말이 맞아요!

그렇다면 언제 스레드 풀에 문제가 생길까요? 스레드가 다른 작업이 완료되기를 기다리고 있기 때문에 스레드가 차단되는 경우 입니다. 다음 예제를 가정하십시오.

class AbcAlgorithm implements Runnable {
    public void run() {
        Future<StepAResult> aFuture = threadPool.submit(new ATask());
        StepBResult bResult = stepB();
        StepAResult aResult = aFuture.get();
        stepC(aResult, bResult);
    }
}

여기서 볼 수있는 것은 3 단계 A, B 및 C로 구성된 알고리즘입니다. A와 B는 서로 독립적으로 수행 될 수 있지만 C 단계는 단계 A와 B의 결과가 필요합니다.이 알고리즘이하는 일은 작업 A를 제출하는 것입니다 스레드 풀과 태스크 b를 직접 수행하십시오. 그런 다음 스레드는 작업 A도 완료 될 때까지 기다렸다가 단계 C를 계속합니다. A와 B가 동시에 완료되면 모든 것이 정상입니다. 그러나 A가 B보다 오래 걸리면 어떻게 될까요? 작업 A의 특성상이를 지시하기 때문일 수도 있지만, 처음에 사용 가능한 작업 A에 대한 스레드가없고 작업 A를 기다려야 할 수도 있습니다. (사용 가능한 단일 CPU가 있고 스레드 풀에 단일 스레드 만있는 경우 교착 상태가 발생할 수 있지만 지금은 문제가 아닙니다.) 요점은 작업 B를 방금 실행 한 스레드가전체 스레드를 차단합니다 . CPU와 동일한 수의 스레드가 있고 하나의 스레드가 차단되므로 하나의 CPU가 유휴 상태 임을 의미합니다 .

포크 / 조인이이 문제를 해결합니다. 포크 / 조인 프레임 워크에서 다음과 같은 알고리즘을 작성합니다.

class AbcAlgorithm implements Runnable {
    public void run() {
        ATask aTask = new ATask());
        aTask.fork();
        StepBResult bResult = stepB();
        StepAResult aResult = aTask.join();
        stepC(aResult, bResult);
    }
}

동일하게 보이지 않습니까? 그러나 단서는 aTask.join 차단되지 않습니다 . 대신에 여기서는 작업 스털링 이 시작됩니다. 스레드는 과거에 포크 된 다른 작업을 둘러보고 계속할 것입니다. 먼저 분기 된 작업이 처리를 시작했는지 확인합니다. 따라서 A가 다른 스레드에서 아직 시작되지 않은 경우 A를 수행하고 그렇지 않으면 다른 스레드의 큐를 확인하고 작업을 훔칩니다. 다른 스레드의 다른 작업이 완료되면 A가 지금 완료되었는지 확인합니다. 위의 알고리즘이라면를 호출 할 수 있습니다 stepC. 그렇지 않으면 훔칠 또 다른 작업을 찾습니다. 따라서 포크 / 조인 풀은 차단 작업에도 불구하고 100 % CPU 사용률을 달성 할 수 있습니다 .

However there is a trap: Work-stealing is only possible for the join call of ForkJoinTasks. It cannot be done for external blocking actions like waiting for another thread or waiting for an I/O action. So what about that, waiting for I/O to complete is a common task? In this case if we could add an additional thread to Fork/Join pool that will be stopped again as soon as the blocking action has completed will be the second best thing to do. And the ForkJoinPool can actually do just that if we are using ManagedBlockers.

Fibonacci

In the JavaDoc for RecursiveTask is an example for calculating Fibonacci numbers using Fork/Join. For a classic recursive solution see:

public static int fib(int n) {
    if (n <= 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

As is explained int the JavaDocs this is a pretty dump way to calculate fibonacci numbers, as this algorithm has O(2^n) complexity while simpler ways are possible. However this algorithm is very simple and easy to understand, so we stick with it. Let's assume we want to speed this up with Fork/Join. A naive implementation would look like this:

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();
   }
}

The steps that this Task is split into are way too short and thus this will perform horribly, but you can see how the framework generally works very well: The two summands can be calculated independently, but then we need both of them to build the final result. So one half is done in an other thread. Have fun doing the same with thread pools without getting a deadlock (possible, but not nearly as simple).

Just for completeness: If you'd actually want to calculate Fibonacci numbers using this recursive approach here is an optimized version:

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);
        }
    }
}

This keeps the subtasks much smaller because they are only split when n > 10 && getSurplusQueuedTaskCount() < 2 is true, which means that there are significantly more than 100 method calls to do (n > 10) and there are not very man tasks already waiting (getSurplusQueuedTaskCount() < 2).

On my computer (4 core (8 when counting Hyper-threading), Intel(R) Core(TM) i7-2720QM CPU @ 2.20GHz) the fib(50) takes 64 seconds with the classic approach and just 18 seconds with the Fork/Join approach which is quite a noticeable gain, although not as much as theoretically possible.

Summary

• Yes, in your example Fork/Join has no advantage over classic thread pools.
• Fork/Join can drastically improve performance when blocking is involved
• Fork/Join circumvents some deadlock problems

---

Fork/join is different from a thread pool because it implements work stealing. From Fork/Join

As with any ExecutorService, the fork/join framework distributes tasks to worker threads in a thread pool. The fork/join framework is distinct because it uses a work-stealing algorithm. Worker threads that run out of things to do can steal tasks from other threads that are still busy.

Say you have two threads, and 4 tasks a, b, c, d which take 1, 1, 5 and 6 seconds respectively. Initially, a and b are assigned to thread 1 and c and d to thread 2. In a thread pool, this would take 11 seconds. With fork/join, thread 1 finishes and can steal work from thread 2, so task d would end up being executed by thread 1. Thread 1 executes a, b and d, thread 2 just c. Overall time: 8 seconds, not 11.

EDIT: As Joonas points out, tasks are not necessarily pre-allocated to a thread. The idea of fork/join is that a thread can choose to split a task into multiple sub-pieces. So to restate the above:

We have two tasks (ab) and (cd) which take 2 and 11 seconds respectively. Thread 1 starts to execute ab and split it into two sub-tasks a & b. Similarly with thread 2, it splits into two sub-tasks c & d. When thread 1 has finished a & b, it can steal d from thread 2.

---

Everyone above is correct the benefits are achieved by the work stealing, but to expand on why this is.

The primary benefit is the efficient coordination between worker threads. The work has to be split up and reassembled, which requires coordination. As you can see in A.H's answer above each thread has its own work list. An important property of this list is that it is sorted (large tasks at the top and small tasks at the bottom). Each thread executes the tasks at the bottom of its list and steals tasks from the top of other threads lists.

The result of this is:

• The head and tail of the task lists can the synchronised independently, reducing contention on the list.
• Significant subtrees of the work are split up and reassembled by the same thread, so no inter thread coordination is required for these subtrees.
• When a thread steals work it takes a large piece which it then subdivides onto its own list
• The work steeling means the threads are nearly fully utilised until the end of the process.

Most other divide and conquer schemes using thread pools require more inter-thread communication and coordination.

---

In this example Fork/Join adds no value because forking is not needed and the workload is evenly split across worker threads. Fork/Join only adds overhead.

Here is a nice article on the subject. Quote:

Overall, we can say that the ThreadPoolExecutor is to be preferred where the workload is evenly split across worker threads. To be able to guarantee this, you do need to know precisely what the input data looks like. By contrast, the ForkJoinPool provides good performance irrespective of the input data and is thus a significantly more robust solution.

---

Another important difference seems to be that with F-J, you can do multiple, complex "Join" phases. Consider the merge sort from http://faculty.ycp.edu/~dhovemey/spring2011/cs365/lecture/lecture18.html, there would be too much orchestration required to pre-split this work. e.g. You need to do the following things:

• sort the first quarter
• sort the second quarter
• merge the first 2 quarters
• sort the third quarter
• sort the forth quarter
• merge the last 2 quarters
• merge the 2 halves

How do you specify that you must do the sorts before the merges which concerns them etc.

I have been looking at how best to do a certain thing for each of a list of items. I think I will just pre-split the list and use a standard ThreadPool. F-J seems most useful when the work cannot be pre-split into enough independant tasks but can be recursively split into tasks which are independant amongst themselves (e.g. sorting the halves are independant but merging the 2 sorted halves into a sorted whole is not).

---

F/J also has a distinct advantage when you have expensive merge operations. Because it splits into a tree structure you do only log2(n) merges as opposed to n merges with linear thread splitting. (This does make the theoretical assumption that you have as many processors as threads, but still an advantage) For a homework assignment we had to merge several-thousand 2D arrays (all the same dimensions) by summing the values at each index. With fork join and P processors the time approaches log2(n) as P approaches infinity.

1 2 3 .. 7 3 1 .... 8 5 4
4 5 6 + 2 4 3 => 6 9 9
7 8 9 .. 1 1 0 .... 8 9 9

---

You would be amazed on ForkJoin performance in application like crawler. here is the best tutorial you would learn from.

Fork/Join's logic is very simple: (1) separate (fork) each large task into smaller tasks; (2) process each task in a separate thread (separating those into even smaller tasks if necessary); (3) join the results.

---

If the problem is such that we have to wait for other threads to complete(as in case of sorting of array or sum of array), fork join should be used, as Executor(Executors.newFixedThreadPool(2)) will choke due to limited number of threads. The forkjoin pool will create more threads in this case to coverup for the blocked thread to maintain same parallelism

Source: http://www.oracle.com/technetwork/articles/java/fork-join-422606.html

The problem with the executors for implementing divide and conquer algorithms is not related to creating subtasks, because a Callable is free to submit a new subtask to its executor and wait for its result in a synchronous or asynchronous fashion. The issue is that of parallelism: When a Callable waits for the result of another Callable, it is put in a waiting state, thus wasting an opportunity to handle another Callable queued for execution.

The fork/join framework added to the java.util.concurrent package in Java SE 7 through Doug Lea’s efforts fills that gap

Source: https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ForkJoinPool.html

The pool attempts to maintain enough active (or available) threads by dynamically adding, suspending, or resuming internal worker threads, even if some tasks are stalled waiting to join others. However, no such adjustments are guaranteed in the face of blocked IO or other unmanaged synchronization

public int getPoolSize() Returns the number of worker threads that have started but not yet terminated. The result returned by this method may differ from getParallelism() when threads are created to maintain parallelism when others are cooperatively blocked.

---

I would like to add a short answer for those who don't have much time to read long answers. The comparison is taken from the book Applied Akka Patterns:

Your decision as to whether to use a fork-join-executor or a thread-pool-executor is largely based on whether the operations in that dispatcher will be blocking. A fork-join- executor gives you a maximum number of active threads, whereas a thread-pool-executor gives you a fixed number of threads. If threads are blocked, a fork-join-executor will create more, whereas a thread-pool-executor will not. For blocking operations, you are generally better off with a thread-pool-executor because it prevents your thread counts from exploding. More “reactive” operations are better in a fork-join-executor.

참고URL : https://stackoverflow.com/questions/7926864/how-is-the-fork-join-framework-better-than-a-thread-pool