ConcurrentLinkedQueue $ Node vẫn còn trong đống sau khi xóa()

Question

Tôi có một ứng dụng viết nhiều luồng và đọc một ConcurrentLinkedQueue, được sử dụng khái niệm để quay lại các mục trong một danh sách/bảng. Ban đầu tôi sử dụng ConcurrentHashMap để làm việc này. Yêu cầu mới yêu cầu theo dõi các mục nhập đã đến, vì vậy chúng có thể được xóa theo thứ tự cũ nhất, tùy thuộc vào một số điều kiện. ConcurrentLinkedQueue dường như là một lựa chọn tốt và chức năng hoạt động tốt.

Số lượng mục nhập có thể định cấu hình được giữ trong bộ nhớ và khi mục nhập mới được cung cấp khi đạt đến giới hạn, hàng đợi được tìm kiếm theo thứ tự cũ nhất cho thứ tự có thể bị xóa. Một số mục không được hệ thống loại bỏ và chờ tương tác của khách hàng.

Điều gì dường như đang xảy ra là tôi có mục nhập ở phía trước hàng đợi đã xảy ra, nói 100 nghìn mục trước đây. Hàng đợi dường như có số lượng mục được định cấu hình hạn chế (size() == 100), nhưng khi lược tả, tôi thấy rằng có ~ 100K đối tượng ConcurrentLinkedQueue $ Node trong bộ nhớ. Điều này dường như được thiết kế, chỉ cần liếc nhìn nguồn cho ConcurrentLinkedQueue, một loại bỏ chỉ đơn thuần loại bỏ tham chiếu đến đối tượng đang được lưu trữ nhưng để lại danh sách liên kết tại chỗ để lặp lại.

Cuối cùng câu hỏi của tôi: Có cách nào tốt hơn "lười biếng" để xử lý một bộ sưu tập bản chất này không? Tôi thích tốc độ của ConcurrentLinkedQueue, tôi không thể đủ khả năng rò rỉ vô biên mà dường như có thể xảy ra trong trường hợp này. Nếu không, có vẻ như tôi sẽ phải tạo một cấu trúc thứ hai để theo dõi thứ tự và có thể có cùng một vấn đề, cộng với một mối quan tâm đồng bộ hóa.

Answer 1

Điều thực sự đang xảy ra ở đây là phương pháp xóa sẽ chuẩn bị chuỗi thăm dò để loại bỏ tham chiếu được liên kết.

ConcurrentLinkedQueue là một chủ đề không chặn an toàn Thực thi hàng đợi. Tuy nhiên khi bạn cố gắng thăm dò ý kiến ​​một Node từ Queue nó là một quá trình hai chức năng. Đầu tiên bạn null giá trị sau đó bạn null tham chiếu. Một hoạt động CAS là một hàm nguyên tử duy nhất sẽ không cung cấp độ phân giải cho cuộc thăm dò.

Điều gì xảy ra khi bạn thăm dò ý kiến ​​là chuỗi đầu tiên thành công sẽ nhận được giá trị của nút và vô giá trị đó, sau đó chuỗi đó sẽ cố gắng hủy tham chiếu. Có thể một chủ đề khác sẽ đến và cố gắng bình chọn từ hàng đợi. Để đảm bảo Queue này giữ một thuộc tính không bị chặn (đó là thất bại của một luồng sẽ không dẫn đến sự thất bại của một luồng khác) mà luồng mới sẽ thấy nếu giá trị là null, nếu nó là null, luồng đó sẽ không tham chiếu và thử một lần nữa để thăm dò ý kiến ​​().

Vì vậy, những gì bạn thấy xảy ra ở đây là xóa chuỗi chỉ đơn giản là chuẩn bị bất kỳ chuỗi thăm dò ý kiến ​​mới nào để trống tham chiếu. Cố gắng để đạt được một chức năng loại bỏ không chặn tôi sẽ nghĩ là gần như không thể bởi vì đó sẽ đòi hỏi ba chức năng nguyên tử. Null của giá trị null tham chiếu đến nút đã nói, và cuối cùng là tham chiếu mới từ nút cha đó đến người kế thừa của nó.

Để trả lời câu hỏi cuối cùng của bạn. Có unforutnalty không có cách nào tốt hơn để thực hiện loại bỏ và duy trì trạng thái không chặn của hàng đợi. Đó là ít nhất vào thời điểm này. Một khi bộ vi xử lý bắt đầu đi ra với vỏ bọc 2 và 3 thì điều đó là có thể.

Answer 2

Ngữ nghĩa chính của hàng đợi là thêm/bỏ phiếu. Nếu bạn sử dụng cuộc thăm dò ý kiến ​​() trên ConcurrentLinkedQueue, nó sẽ được xóa sạch. Dựa trên mô tả của bạn, cuộc thăm dò ý kiến ​​() sẽ cho phép bạn xóa mục nhập cũ nhất. Tại sao không sử dụng nó thay vì xóa()?

Answer 3

Nhìn vào mã nguồn cho 1.6.0_29, có vẻ như trình lặp của CLQ đã được sửa đổi để thử xóa các nút có các mục rỗng. Thay vì:

p = p.getNext(); 

Mã này bây giờ là:

Node<E> next = succ(p); 
if (pred != null && next != null) 
    pred.casNext(p, next); 
p = next; 

này được đưa vào như một phần của việc sửa chữa cho lỗi: http://bugs.sun.com/view_bug.do?bug_id=6785442

Thật vậy khi tôi cố gắng sau tôi nhận được một OOME với phiên bản cũ nhưng không phải với phiên bản mới:

Queue<Integer> queue = new ConcurrentLinkedQueue<Integer>(); 
for (int i=0; i<10000; i++) 
{ 
    for (int j=0; j<100000; j++) 
    { 
     queue.add(j); 
    } 
    boolean start = true; 
    for (Iterator<Integer> iter = queue.iterator(); iter.hasNext();) 
    { 
     iter.next(); 
     if (!start) 
      iter.remove(); 
     start = false; 
    } 
    System.out.println(i); 
}