Thao tác có thể không thực sự lưu trữ giá trị mới vào đích vì cuộc đua với chuỗi khác thay đổi giá trị tại cùng thời điểm bạn đang cố gắng. Các nguyên thủy CAS không đảm bảo rằng việc ghi xảy ra - chỉ rằng ghi xảy ra nếu giá trị đã là những gì mong đợi. Nguyên thủy không thể biết hành vi chính xác là gì nếu giá trị không được mong đợi, vì vậy không có gì xảy ra trong trường hợp đó - bạn cần sửa lỗi bằng cách kiểm tra giá trị trả về để xem hoạt động có hoạt động hay không.
Vì vậy, ví dụ bạn:
elem->next = __sync_val_compare_and_swap(&head, head, elem); //always inserts?
sẽ không nhất thiết phải chèn các yếu tố mới. Nếu một chuỗi khác chèn một phần tử vào cùng một thời điểm, có một điều kiện chủng tộc có thể khiến cuộc gọi của chủ đề này bị __sync_val_compare_and_swap() không cập nhật head (nhưng phần tử của chủ đề này hoặc của chủ đề khác sẽ bị mất nếu bạn xử lý chính xác).
Nhưng, có một vấn đề với điều đó dòng mã - ngay cả khi head đã được cập nhật, có một khoảnh khắc ngắn ngủi của thời gian mà head điểm để các yếu tố chèn, nhưng con trỏ next của yếu tố đó chưa được cập nhật để trỏ đến người đứng đầu danh sách trước đó. Nếu một chuỗi khác lặp lại trong thời điểm đó và cố gắng đi bộ trong danh sách, những điều xấu sẽ xảy ra.
Để cập nhật một cách chính xác danh sách thay đổi điều đó dòng mã để một cái gì đó như:
whatever_t* prev_head = NULL;
do {
elem->next = head; // set up `elem->head` so the list will still be linked
// correctly the instant the element is inserted
prev_head = __sync_val_compare_and_swap(&head, elem->next, elem);
} while (prev_head != elem->next);
Hoặc sử dụng bool biến thể, mà tôi nghĩ là thuận tiện hơn một chút:
do {
elem->next = head; // set up `elem->head` so the list will still be linked
// correctly the instant the element is inserted
} while (!__sync_bool_compare_and_swap(&head, elem->next, elem));
Đó là loại xấu xí, và tôi hy vọng tôi đã làm đúng (thật dễ dàng để có được vấp trong các chi tiết của mã an toàn thread). Nó phải được gói trong một hàm insert_element() (hoặc thậm chí tốt hơn, sử dụng một thư viện thích hợp).
Phát biểu vấn đề ABA:
Tôi không nghĩ rằng vấn đề ABA có liên quan đến này "thêm một yếu tố để người đứng đầu danh sách" mã. Giả sử rằng một chuỗi muốn thêm đối tượng X vào danh sách và khi nó thực hiện elem->next = head, head có giá trị A1.
Sau đó, trước khi __sync_val_compare_and_swap() được thực thi, một tập hợp các đề xuất hiện và:
- loại bỏ
A1 từ danh sách, làm head điểm đến B
- làm bất cứ điều gì với đối tượng
A1 và giải phóng nó
- phân bổ một đối tượng khác,
A2 xảy ra ở cùng một địa chỉ với A1 là
- thêm
A2 vào danh sách để head nay trỏ tới A2
Kể từ A1 và A2 có cùng một định danh/địa chỉ, đây là một thể hiện của vấn đề ABA.
Tuy nhiên, nó không quan trọng trong trường hợp này kể từ thread thêm đối tượng X không quan tâm rằng head điểm đến một đối tượng khác nhau hơn nó bắt đầu ra với - tất cả những gì quan tâm đến là khi X được xếp hàng đợi:
- danh sách là nhất quán,
- không có đối tượng trong danh sách đã bị mất, và
- không có đối tượng khác ngoài
X đã được thêm vào danh sách (bởi thread này)
Các mã này bị vấn đề ABA. – ddoman
@ddoman: bạn có thể giải thích cách bạn sẽ sửa chữa nó không? Hoặc bạn sẽ chỉ sử dụng một trong những phương pháp được đề xuất trong bài viết wikipedia về vấn đề ABA? – Aktau
Tôi không chắc chắn rằng vấn đề ABA là một vấn đề ở đây - tôi đã cập nhật câu trả lời để cho biết lý do. Nếu tôi nhầm, tôi sẽ đánh giá cao các chi tiết. –