ArrayBlockingQueue sử dụng một khóa duy nhất cho chèn và loại bỏ nhưng LinkedBlockingQueue sử dụng 2 ổ khóa riêng

Question

Tôi đã đi qua mã nguồn của ArrayBlockingQueue và LinkedBlockingQueue. LinkedBlockingQueue có một putLock và một takeLock để chèn và loại bỏ tương ứng nhưng ArrayBlockingQueue chỉ sử dụng 1 khóa. Tôi tin rằng LinkedBlockingQueue đã được triển khai dựa trên thiết kế được mô tả trong Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms. Trong bài báo này, họ đề cập rằng họ giữ một nút giả để các enqueuers không bao giờ phải truy cập vào đầu và dequeuers không bao giờ phải truy cập đuôi mà tránh các tình huống bế tắc. Tôi đã tự hỏi tại sao ArrayBlockingQueue không vay cùng một ý tưởng và sử dụng 2 khóa thay thế.

Answer 1

ArrayBlockingQueue có để tránh ghi đè lên mục để mà nó cần phải biết được nơi bắt đầu và cuối cùng là. Một LinkedBlockQueue không cần phải biết điều này vì nó cho phép GC lo lắng về việc làm sạch các nút trong hàng đợi.

Answer 2

Tôi đã tự hỏi tại sao ArrayBlockingQueue không vay cùng một ý tưởng và sử dụng 2 khóa thay thế.

Do cấu trúc dữ liệu đơn giản hơn nhiều để giữ các mục hàng đợi.

ArrayBlockingQueue lưu trữ dữ liệu của nó trong một mảng private final E[] items;. Đối với nhiều chủ đề để đối phó với cùng một không gian lưu trữ này, hoặc nếu thêm hoặc khử, chúng phải sử dụng cùng một khóa. Điều này không chỉ vì rào cản bộ nhớ mà vì bảo vệ mutex vì chúng đang sửa đổi cùng một mảng. Mặt khác,

LinkedBlockingQueue là danh sách các phần tử xếp hàng được liên kết hoàn toàn khác và cho phép khả năng khóa kép. Đây là lưu trữ nội bộ của các phần tử trong hàng đợi đã bật các cấu hình khóa khác nhau.

Answer 3

Tôi nghĩ ABQ có thể vay cùng ý tưởng như LBQ. Vui lòng tham khảo mã số http://pastebin.com/ZD1uFy7S của tôi và một câu hỏi tương tự mà tôi đã hỏi trên SO ArrayBlockingQueue: concurrent put and take.

Lý do tại sao họ không sử dụng nó, chủ yếu là vì sự phức tạp trong việc thực hiện đặc biệt là vòng lặp và đánh đổi giữa tính phức tạp và đạt được hiệu suất là không phải là béo bở.

Để tham khảo thêm, vui lòng xem http://jsr166-concurrency.10961.n7.nabble.com/ArrayBlockingQueue-concurrent-put-and-take-tc1306.html.

Answer 4

2 khóa được sử dụng trong LBQ để hạn chế quyền truy cập vào đầu và khóa đồng thời. Khóa đầu không cho phép hai phần tử bị loại bỏ đồng thời và khóa đuôi không cho phép hai phần tử được đồng thời được thêm vào hàng đợi. hai khóa lại với nhau ngăn chặn các cuộc đua.