Kết quả đầu tiên trong Google về "khóa vectơ miễn phí" là một nghiên cứu được viết bởi Damian Dechev, Peter Pirkelbauer và Bjarne Stroustrup mô tả một vector không khóa lý thuyết. Điều này, hoặc bất kỳ vector không khóa nào khác, đã được triển khai chưa?Có triển khai vector không khóa không?
MS cung cấp ppl :: concurrent_vector và Intel cung cấp tbb :: concurrent_vector. Trên Windows, ít nhất ppl và tbb là một phần của C-Runtime.
* Đồng thời * và không có khóa là những thứ hoàn toàn khác nhau –
Bạn chính xác, đồng thời và không có khóa không giống nhau. Tôi đã được ấn tượng trong việc thực hiện MS ppl concurrent_vector đã được khóa miễn phí. Đây có phải là không? – Unknown1987
Tôi có xu hướng giả định rằng trừ khi có quy định khác không có thư viện là khóa-ít hơn, và tôi đã không nhìn thấy bất kỳ tài liệu tham khảo trong một cái nhìn nhanh chóng tại các tài liệu nói rằng ppl :: concurrent_vector là khóa-ít hơn. –
Tôi vừa mới tìm hiểu xem vector là gì, trong wikipedia.
Tôi nghĩ (chỉ một hoặc hai phút suy nghĩ, suy nghĩ) một phiên bản hoàn toàn không có khóa là một chút vấn đề.
Xem xét; bạn tạo mảng, truy cập vào nó như bình thường, vv Đối với điều này bạn không cần khóa-miễn phí. Vấn đề chúng xuất hiện khi bạn cần thay đổi kích thước. Các chủ đề mà đi vào và phát hiện ra nhu cầu này để malloc. Đây là một hoạt động thực sự độc đáo - các chủ đề khác tại thời điểm này phải chặn/quay. Nếu họ cố gắng giúp đỡ, ví dụ: làm malloc mình, bạn có thể có nhiều chủ đề phát hành malloc. Bây giờ nó có thể là trong thực tế số lượng các chủ đề làm là thấp đến mức không sao - trong trường hợp này bạn có thể có một số chủ đề thực hiện malloc, với người chiến thắng kích hoạt nguyên tử bộ nhớ mới và những kẻ thua cuộc thấy điều này và sau đó tự do () vào bộ nhớ của họ. Sau đó, để thực hiện sao chép, khi một chủ đề truy cập vào một phần tử, chúng tôi sẽ cần theo dõi tất cả của các mảng được phân bổ trong danh sách và chúng tôi truy cập chúng thông qua danh sách, cũ nhất trước tiên. , cho đến khi chúng ta tìm thấy phần tử chúng ta muốn và nếu nó không nằm trong mảng gần đây nhất, chúng ta di chuyển nó và sau đó truy cập nó.
Sau đó, chúng tôi cũng cần một cách để biết chuỗi đã di chuyển phần tử cuối cùng và có thể giải phóng mảng đó, vì vậy chúng tôi sẽ phải tính các phần tử; vì vậy chúng tôi có nguy cơ về các yêu cầu phân bổ có khả năng không bị ràng buộc. Hơn nữa, cấu trúc dữ liệu (tôi đã nói một danh sách, nhưng nó có thể là những thứ khác, mặc dù chúng sẽ không tốt, prolly) sẽ cần phải là nguyên tử (vì có thể các luồng có thể xóa một mảng cùng một lúc) và một danh sách không có khóa nguyên tử cho đến gần đây là đỉnh cao của các cấu trúc dữ liệu không khóa, phức tạp như chúng nhận được, yêu cầu SMR và với việc triển khai phức tạp.
(tôi nói cho đến thời gian gần đây - một người nào đó vừa phát minh ra một màu đỏ-đen cây lock-free, toàn bộ điều, thêm và xóa!)
TBH, tôi không hiểu tại sao mọi người sẽ sử dụng một vector. Tại sao không chỉ sử dụng cây nhị phân cân bằng hay băm?
http://www.linuxsoftware.co.nz/containerchoice.png –
Có thể [libcds] (http://libcds.sourceforge.net/)? –
Cử tri xuống có thể tự giải thích mình không? – qdii
Bỏ phiếu xuống số – Justicle