Cố gắng viết một danh sách liên kết đơn lẻ không khóa, gặp sự cố khi xóa

Question

Tôi đang cố gắng viết một danh sách liên kết đơn lẻ miễn phí khóa. Sự nhất quán cuối cùng không phải là một vấn đề (ai đó đi qua một danh sách có thể chứa các mục không chính xác).

Tôi nghĩ rằng tôi có quyền thêm mục (lặp và Interlocked.CompareExchange).

Nhưng tôi không thể tìm ra cách xóa nút (bất kỳ vị trí nào trong danh sách) vì tôi phải lấy mục trước và họ đặt trường Next của nó thành trường hiện tại là Next.

class Node 
{ 
    Node Next; 
    object Value; 
} 

class SinglyLinkedList 
{ 
    Root _root; 

    public void Add(object value) 
    {} 

    public void Remove(object value) 
    {} 
} 

tức

a -> b -> c

để

a -> c

Pseudo mã:

Node prev; 
Node node = _root; 
while (node.Value != nodeValue) 
{ 
    prev = node; 
    node = node.Next; 
} 
prev.Next = node.Next; 

làm thế nào để làm cho đây là một hoạt động nguyên tử (I E. đảm bảo rằng prev.Next = node.Next được gọi mà không cần tiếp theo hoặc bị loại bỏ ở giữa bởi một chuỗi khác)?

Tôi có thể sử dụng ReaderWriterLockSlim thay vào đó, nhưng tôi thấy vấn đề này thú vị vì tôi biết rằng có tồn tại các danh sách được liên kết miễn phí khóa.

mối quan tâm của tôi:

Sau đây có thể xảy ra nếu các chủ đề hiện tại đang lơ lửng giữa vòng lặp và sự phân công:

• prev bản thân có thể đã bị loại bỏ bởi thread khác.
• node có thể đã bị xóa bởi một chuỗi khác.
• Node.Next có thể đã bị loại bỏ

Answer 1

Yep, thêm được một hai bước vòng lặp đơn giản với CAS trên con trỏ .Next trước; nhưng loại bỏ thì khó!

Thực ra bạn không thể làm điều đó mà không cần sử dụng thêm một phần thông tin và logic.

Harris đã tạo giải pháp cho vấn đề này bằng cách thêm bit đánh dấu đã từng đặt không cho phép bất kỳ ai sửa đổi nút. Việc loại bỏ trở thành hai bước: đầu tiên (CAS) đánh dấu nút đã loại bỏ để ngăn chặn bất kỳ ai thay đổi nó (đặc biệt là con trỏ .Next của nó); CAS thứ hai nút trước đó. Con trỏ tiếp theo, hiện đã an toàn vì nút kia đã được đánh dấu.

Vấn đề bây giờ là trong C Harris đã sử dụng hai bit quan trọng nhất của con trỏ .Next là điểm đánh dấu. Điều này là thông minh bởi vì với 4-byte con trỏ liên kết họ luôn luôn không sử dụng (tức là 00) và bởi vì họ phù hợp trong con trỏ 32 bit họ có thể được CAS nguyên tử với con trỏ chính nó, đó là chìa khóa để thuật toán này. Tất nhiên điều này là không thể trong C#, ít nhất là không sử dụng mã không an toàn.

Giải pháp phức tạp hơn một chút và liên quan đến tham chiếu bổ sung cho lớp không thay đổi tiếp giáp hai trường (.Next + marker).

Thay vì đi sâu vào một lời giải thích dài dòng về những ý tưởng, tôi đã tìm thấy một số tài liệu tham khảo trên mạng Internet rằng sẽ đi vào tất cả các chi tiết mà bạn cần, xem:

Lock-free Linked List (Part 1) Giải thích các vấn đề;

Lock-free Linked List (Part 2) Giải thích giải pháp C + giải pháp spinlock;

Lock-free Linked List (Part 3) Giải thích tham chiếu trạng thái bất biến;

Nếu bạn thực sự tò mò về chủ đề có các tài liệu học tập với các giải pháp và phân tích hiệu suất khác nhau của chúng, ví dụ: cái này: Lock-free linked lists and skip lists