• Thao tác Pop
bool pop ( int & t ) { Node * current = head ; while ( current ) { if ( cas (& head , current- > next , current )) { t = current- > data ; return true ;
} current = head ;
} return false ;
}
• Thread 1 gọi CompareAndSet nhìn thấy giá trị X đã bị đổi , sau đó thử lại .
• Thread 2 thay đổi lại giá trị X là A .
• Thread 1 thực hiện lại và thành công với CompareAndSet .
Vấn đề ở đây chính là việc Thread 1 “ tưởng ” là mình đã gán thành công khi biến X không bị thay đổi từ bên ngoài nhưng thực ra X đã bị thay đổi mà Thread 1 không hề biết . Khi stack dạng lock-free gặp phải vấn đề này thì sẽ có khả năng bạn đã gọi thao tác pop 2 lần trên cùng một node và sẽ bị tình trạng segfault .
Ở đây câu lệnh cas (* Node x , * Node oldValue , * Node newValue ) sẽ so sánh giá trị của biến X với oldValue ( giá trị cũ ). Nếu giá trị của biến X bằng với giá trị oldValue thì hàm cas sẽ dược thực thi , gán giá trị newValue vào cho biến X . Đối với trường hợp giá trị của biến X không bằng với giá trị oldValue thì hàm cas sẽ không được thực thi ( do đã có thread khác tác động lên biến X dẫn đến giá trị thay đổi ).
Bạn có thể thấy một cấu trúc dữ liệu stack dạng lock free chỉ đơn thuần là một stack có áp dụng các phép toán atomic kết hợp với vòng lặp while .
2 . DANH SÁCH LIÊN KẾT DẠNG LOCK-FREE
Danh sách liên kết dạng lock-free ( lock-free linked list ) là một ví dụ rất tốt để chứng minh vấn đề hiệu năng giữa việc sử dụng lock hay không sử dụng lock .
Với danh sách liên kết ( linked list ) thì đôi khi bạn sẽ phải duyệt qua một quãng đường dài để tìm kiếm một phần tử nào đó . Vì vậy nếu sử dụng lock thông thường thì bạn sẽ phải lock toàn bộ danh sách khi cần duyệt !! Cho nên việc vận dụng cấu trúc dữ liệu Lock-free trong tình huống này sẽ giúp tiết kiệm thời gian rất nhiều .
Cách hiện thực danh sách liên kết dạng lock-free khá phức tạp do có liên quan đến thao tác xóa nên các bạn có thể tham khảo thêm chi tiết trong bài viết “ Generic Concurrent Lock-Free Linked List “ [ 2 ].
Ngoài ra có một bài báo khác khá nổi tiếng về danh sách liên kết dạng lock-free với tiêu đề “ A Pragmatic Implementation of Non-Blocking Linked-Lists ” [ 3 ] mà bạn đọc có thể tham khảo thêm .
Bài toán ABA
Với lock free sử dụng atomic operation sẽ xảy ra một hiện tượng rất thú vị gọi là ABA , hiện tượng đó được diễn giải như dưới đây :
• Thread 1 nhìn vào một biến chia sẻ X và định thay đổi nó . Lúc thread 1 nhìn thì X có giá trị là A .
• Thread 1 tính toán một vài thứ thú vị dựa trên sự thật là X có giá trị là A
• Thread 2 chạy , biến đổi X thành giá trị là B .
Để vượt qua vấn đề này thì chúng ta có thể thêm một biến là “ update count ” dựa vào khái niệm “ doubleword CAS ” ( cần sự hỗ trợ phần cứng ).
Chú ý và kết luận
Lock free không phải là thuốc chữa cho bài toán tranh chấp tài nguyên . Việc nhiều thread cùng tranh chấp một tài nguyên vẫn có thể xẩy ra , chỉ khác là ở tần suất thấp hơn , và được giải quyết tốt hơn ( về mặt giải thuật + sự hỗ trợ về phần cứng ). Starvation ( chết đói ) , hay là hiện tượng khi một vài thread không nhận được resource đủ để chạy vẫn có thể xảy ra .
Để áp dụng lock free thì bạn cần lưu ý hai yếu tố :
• Bài toán đủ đơn giản .
• Bạn tự nghĩ ra được một thuật toán lock free để áp dụng cho một vài trường hợp hẹp .
Lock free sẽ làm tăng hiệu năng cho ứng dụng nhưng để hiện thực đúng là hoàn toàn không dễ ( vấn đề ABA là một ví dụ ).
Đọc và thảo luận bài viết online : https :// engineering . grokking . org /
16 DIJSKTRA