Cây đồng thời hiệu quả

Question

Tôi đang tìm một cách hiệu quả để triển khai cấu trúc cây đồng thời. Nếu điều đó giúp, giả sử rằng tôi có nhiều quyền truy cập đọc nhiều hơn thay đổi cấu trúc.

Cây nên hỗ trợ các hoạt động này:

• Thêm và xóa các nút
• Sắp xếp các chi nhánh mỗi khi một nút mới được chèn
• lặp qua tất cả các nút (không ConcurrentModificationException)
• Tra cứu một phần tử theo đường dẫn

Answer 1

Hãy xem tại địa chỉ: Concurrent-Trees trên mã Google kiếm một cách để thay đổi cơ cấu cây giống mà không cần khóa.

Dự án cung cấp các cây phối trộn đồng thời và hậu tố cho Java. Chúng hỗ trợ đọc và ghi đồng thời, và đọc là không có khóa. Nó hoạt động bằng cách áp dụng các bản vá lỗi cho cây một cách nguyên tử. Mặc dù các loại cây này có thể không chính xác những gì bạn muốn, nhưng cách tiếp cận bằng cách sử dụng "vá" như được mô tả trong TreeDesign hữu ích cho bất kỳ loại cấu trúc giống cây nào.

Cây được dùng cho các trường hợp sử dụng đa số đọc đồng thời cao, trong đó có một chủ đề nền có thể chèn hoặc xóa các mục từ cây trong khi nhiều chủ đề tiền cảnh sẽ tiếp tục di chuyển nó không bị thay đổi bởi các sửa đổi.

Answer 2

Bạn có thể sử dụng khóa người đọc trong cấu trúc của mình, tôi n một cách mà nhiều luồng có thể đọc đồng thời nhưng chỉ có một luồng tại một thời điểm có thể sửa đổi nó. Nếu một số chủ đề cố gắng sửa đổi cấu trúc, nó không thể làm điều đó cho đến khi tất cả người đọc đọc xong. Nếu một chủ đề muốn đọc nó chỉ có thể nếu một người viết chưa hoạt động, hoặc nó là trên shedule thực hiện một số sửa đổi. Có lẽ nhìn vào điều này có thể giúp:

http://docs.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/locks/ReentrantReadWriteLock.html

Answer 3

ý tưởng cơ bản với Read/Write khóa

Đối với tất cả các phương pháp viết sử dụng sau thành ngữ:

someWriteMethod(){ 
    writeLock.lock(); 
    // logic 
    writeLock.unlock(); 
} 

Đối với tất cả đọc phương pháp sử dụng tương tự mã:

someReadMethod(){ 
    readLock.lock(); 
    // logic 
    readLock.unlock(); 
} 

• Nếu ít nhất một phương pháp thực hiện viết, không ai có thể có được khóa đọc hoặc ghi.
• Nếu ít nhất một phương pháp thực hiện việc đọc, bất kỳ số lượng chuỗi nào đều có thể đọc được khóa.
• Nếu ít nhất một phương pháp thực hiện việc đọc, không ai có thể lấy khóa ghi.

Lưu ý, nếu mã của bạn (thay thế nhận xét logic ở trên) có thể ném ngoại lệ, hãy đảm bảo bạn giải phóng khóa trước khi thoát khỏi phương pháp trong phần cuối cùng.

Answer 4

Cấu trúc Java gần nhất với những gì bạn cần là ConcurrentSkipListSet (hoặc có thể ConcurrentSkipListMap).

---

Nếu bạn cần thêm phương pháp tùy chỉnh, bạn có thể triển khai cấu trúc cây tùy chỉnh nếu bạn có khóa đọc ghi phân cấp. Dưới đây là một answerto một câu hỏi tương tự về cách triển khai một reentrant read-write lock: https://stackoverflow.com/a/6154873/272388