Java 7: Fork/Join Framework

Question

Ai đó có thể giải thích Fork/Join là gì?

Answer 1

Kiểm tra những liên kết này -

http://www.artima.com/forums/flat.jsp?forum=276&thread=219155

http://lambda-the-ultimate.org/node/3521

http://www.ibm.com/developerworks/java/library/j-jtp11137.html

Answer 2

Giả sử bạn có một bộ sưu tập những thứ cần phải được xử lý. Bạn có một số chủ đề có thể lấy các tập hợp con của bộ sưu tập này và xử lý chúng. Tất cả đều làm điều này đồng thời (phần ngã ba) sau đó chờ đợi trên một cuối cùng để kết thúc (phần tham gia) trước khi trở về.

Answer 3

Tham gia ngã ba là một khung công tác mới có API dễ sử dụng hơn cho thuật toán song song, phân chia và chinh phục.

Giả sử bạn có một tác vụ chạy dài, trong trường hợp này, có một thuật toán phức tạp. Bạn sẽ muốn chia nhỏ các nhiệm vụ lớn và bây giờ làm việc trên hai nhiệm vụ đó. Bây giờ hãy nói rằng hai nhiệm vụ đó vẫn còn quá lớn, bạn sẽ chia từng phần thành hai nhiệm vụ (tại thời điểm này có bốn).

Bạn sẽ tiếp tục điều này cho đến khi mỗi tác vụ ở kích thước có thể chấp nhận và gọi thuật toán. Điều quan trọng là phải biết lời gọi của mỗi tác vụ được thực hiện song song. Khi nhiệm vụ được hoàn thành, nó được nối với nhiệm vụ khác nó được chia nhỏ và củng cố kết quả.

Điều này sẽ tiếp tục cho đến khi tất cả các tác vụ đã được tham gia và một nhiệm vụ được trả về.

Answer 4

Ngoài những gì đã được nói, ngã ba/tham gia sử dụng trộm cắp công việc - chủ đề chạy ra khỏi những thứ để làm có thể ăn cắp nhiệm vụ từ các chủ đề khác mà vẫn còn bận rộn. Và đây là một ví dụ có thể giúp bạn hiểu làm thế nào FJ có thể được sử dụng:

public class SumCounter extends RecursiveTask<Long> { 

    private final Node node; 

    public SumCounter(Node node) { 
    this.node = node; 
    } 

    @Override 
    protected Long compute() { 
    long sum = node.getValue(); 
    List<ValueSumCounter> subTasks = new LinkedList<>(); 

    for(Node child : node.getChildren()) { 
     SumCounter task = new SumCounter(child); 
     task.fork(); // run asynchronously 
     subTasks.add(task); 
    } 

    for(SumCounter task : subTasks) { 
     sum += task.join(); // wait for the result 
    } 

    return sum; 
    } 

    public static void main(String[] args) { 
    Node root = getRootNode(); 
    new ForkJoinPool().invoke(new SumCounter(root)); 
    } 

} 

Answer 5

này là một nguồn lực rất tốt để hiểu Fork và Tham gia:

Fork and Join: Java Can Excel at Painless Parallel Programming Too! By Julien Ponge

Answer 6

Lết tôi chỉ cần đặt hai xu của tôi để làm cho sự hiểu biết cơ bản của Fork/Tham gia đơn giản.

What is Fork/Join? 

The fork/join framework is an implementation of the ExecutorService interface 
that helps you take advantage of multiple processors. It is designed for work 
that can be broken into smaller pieces recursively. The goal is to use all the 
available processing power to enhance the performance of your application. 

• khuôn khổ này là rất hữu ích cho mô hình chia-và-chinh phục vấn đề. Cách tiếp cận này phù hợp cho các nhiệm vụ có thể được chia đệ quy và được tính toán trên quy mô nhỏ hơn; kết quả tính toán là rồi kết hợp.
• Khuôn khổ là triển khai giao diện ExecutorService và cung cấp nền tảng đồng thời dễ sử dụng để khai thác nhiều bộ xử lý.

Term hữu ích cho khuôn khổ này

• forking: Chia nhiệm vụ thành các nhiệm vụ nhỏ hơn là forking.
• Tham gia: Kết hợp các kết quả từ các nhiệm vụ nhỏ hơn sẽ tham gia

Như với bất kỳ thực hiện ExecutorService, ngã ba/join khung phân phối nhiệm vụ cho đề người lao động trong một hồ bơi thread. Khung ngã ba/tham gia là khác biệt vì nó sử dụng thuật toán đánh cắp công việc . Chuỗi công việc chạy ra khỏi những việc cần làm có thể lấy cắp các tác vụ từ các chủ đề khác vẫn đang bận.

Các Fork/Tham thuật toán được thiết kế như sau:

• nhiệm vụ chia
• ngã ba nhiệm vụ
• tham gia các nhiệm vụ
• soạn kết quả

doRecursiveTask(input){ 
    if(task is small enough to handled by a thread){ 
     compute the small task; 
     if there is result to return, then do so 
    }else{ 
     divide the task i.e, fork() into two parts 
     call compute on first task, join on second task, combine both results and return 
    } 
} 

Thuật toán đánh cắp công việc là gì?

Mỗi chuỗi công việc trong khung Fork/Join có hàng đợi công việc được triển khai bằng cách sử dụng Deque. Mỗi lần một nhiệm vụ mới (hoặc subtask) là được tạo, nó được đẩy lên đầu hàng đợi của chính nó. Khi một nhiệm vụ hoàn thành một nhiệm vụ và thực hiện một phép nối với một nhiệm vụ khác chưa hoàn thành , nó hoạt động thông minh. Chủ đề xuất hiện một nhiệm vụ mới từ đầu của hàng đợi và bắt đầu thực hiện thay vì ngủ (theo thứ tự để đợi công việc khác hoàn thành). Trong thực tế, nếu hàng đợi của một chuỗi trống, thì chuỗi sẽ xuất hiện một nhiệm vụ từ đuôi của hàng đợi thuộc về một chuỗi khác. Đây không phải là một thuật toán ăn cắp công việc . More detail is here