java Fork/Tham gia làm rõ về cách sử dụng ngăn xếp

Question

Tôi đọc về việc triển khai khung công tác Fork/Join đã được giới thiệu trong Java 7 và tôi chỉ muốn kiểm tra xem tôi có hiểu cách hoạt động của phép thuật không.

Như tôi đã hiểu, khi có một nhánh ren, nó tạo ra các phần phụ trong hàng đợi của nó (mà chủ đề khác có thể hoặc không thể đánh cắp). Khi thread cố gắng "join", nó thực sự kiểm tra hàng đợi của nó cho các nhiệm vụ hiện có và sau đó đệ quy thực hiện chúng, có nghĩa là đối với bất kỳ hoạt động 'join' nào - 2 khung sẽ được thêm vào ngăn xếp chuỗi cuộc gọi (một cho phép nối và một) cho lời gọi nhiệm vụ mới được thực hiện).

Như tôi biết rằng JVM không hỗ trợ tối ưu hóa cuộc gọi đuôi (có thể phục vụ trong trường hợp này để loại bỏ khung ngăn xếp phương thức kết nối) Tôi tin rằng trong khi thực hiện thao tác phức tạp với nhiều nhánh và tham gia một chuỗi có thể ném an StackOverflowError.

Tôi có đúng hay họ đã tìm thấy một số cách hay để ngăn chặn nó?

EDIT

Dưới đây là một kịch bản để giúp làm rõ câu hỏi: Say (vì đơn giản) mà chúng ta chỉ có một thread trong hồ bơi forkjoin. Tại một thời điểm nào đó - các nhánh ren và sau đó các cuộc gọi tham gia. Trong khi trong phương thức join, thread phát hiện ra rằng nó có thể thực hiện nhiệm vụ được chia đôi (như nó được tìm thấy trong hàng đợi của nó) để nó gọi nhiệm vụ tiếp theo. Nhiệm vụ này lần lượt dĩa và sau đó gọi tham gia - vì vậy trong khi thực hiện các phương pháp tham gia các chủ đề sẽ tìm thấy nhiệm vụ chia rẽ trong hàng đợi của nó (như trước) và gọi nó. trong giai đoạn đó ngăn xếp cuộc gọi sẽ chứa ít nhất các khung cho hai phép nối và hai tác vụ.

vì bạn có thể thấy khung nối ghép nối được chuyển thành đệ quy đơn giản. Bởi vì java không hỗ trợ tối ưu hóa cuộc gọi đuôi - mọi đệ quy trong java có thể gây ra StackOverflowError nếu nó đủ sâu.

Câu hỏi của tôi là - người thực hiện khung ngã ba/tham gia có tìm thấy một số cách hay để ngăn chặn tình huống này không.

Answer 1

Thật không may là không có gì huyền diệu xảy ra về mặt ngăn xếp đệ quy. Nếu công việc ban đầu của bạn dĩa/chia tách và không có một điểm giải quyết hợp lý thì bạn sẽ chạy vào StackOverflowErrors.

Bạn có thể hiểu tại sao hướng dẫn trên JavaDoc tách từng phần phụ thành một nửa.

Answer 2

Thường thì mỗi tác vụ mới được đẩy lên ngăn xếp bằng một nửa kích thước của hình trước đó. Vì vậy, số lượng công việc tăng theo cấp số nhân với kích thước ngăn xếp. Ngay cả với một ngăn xếp nhỏ, bạn sẽ có thể phù hợp với quá nhiều công việc để giữ cho bạn bận rộn trong một thời gian.

Answer 3

Tôi hy vọng tôi hiểu bạn đúng cách.

Có hàng đợi nội bộ trong forkjoinpool giữ các tác vụ bạn muốn thực thi, vì vậy không thể tràn ngăn xếp ngăn xếp, nhưng bạn phải chuẩn bị để sử dụng bộ nhớ cao.

Nơi rất thú vị cho phương thức ngã ba là ForkJoinWorkerThread.pushTask với cách sử dụng đối tượng không an toàn, vì vậy bạn nên chú ý rằng mảng được sử dụng để lưu trữ tác vụ.

EDIT: Đầu tiên và đơn giản - khi bạn đang ở trên cùng của hàng đợi, bạn chỉ đơn giản là chưa được thực hiện và được thực thi, và việc trả lại được trả về. (forkjointask.java:353)

Cách tiếp cận khác nhau được sử dụng khi bạn có phụ thuộc, trong trường hợp này, kiểm soát được trả về cho WorkerThread, người chịu trách nhiệm phát hiện chuỗi và thực thi chúng. Bởi công nhân đầu tiên kiểm tra hàng đợi địa phương cho bất kỳ nhiệm vụ nào không được thực hiện, và nếu không có nhiệm vụ như vậy nó thực hiện công việc đã qua và trả về kết quả, nếu không nó sẽ đi đến trường hợp tiếp theo. Đó là giúp đỡ để ăn cắp nhiều lần. Không có gì có thể giúp ...retries mà là ở bước đầu tiên bằng với MAX_HELP là số không bây giờ - kiểm soát được thông qua để bơi, trong đó thực hiện một số kiểm tra và thực hiện tryAwaitDone. Và trong phương thức chờ đợi này được gọi để chờ hoàn thành nhiệm vụ.

Điều này có nghĩa là ngã ba tham gia hồ bơi sẽ hoàn thành trong một vài bước, cố gắng tối ưu hóa tốc độ và thời gian bằng cách tránh cuộc gọi chờ đợi. Tuy nhiên nó có thể kết thúc trong chờ đợi, sau đó điều này có nghĩa là quá trình đồng bộ hóa để bắt đầu mà là rất tốn kém.

Vì vậy, không có tham gia tiếp theo cho độ sâu không xác định, nhưng cố gắng hợp lý để thực hiện các tác vụ nhanh nhất có thể.