Java Đồng thời: CAS vs Khóa

Question

Tôi đang đọc Sách Đồng thời Java trong Thực tiễn. Trong chương 15, họ đang nói về các thuật toán không chặn và phương pháp so sánh so sánh và trao đổi (CAS).

Được viết rằng CAS hoạt động tốt hơn nhiều so với phương pháp khóa. Tôi muốn hỏi những người đã làm việc với cả hai khái niệm này và muốn nghe khi bạn thích một trong những khái niệm này? Nó thực sự nhanh hơn rất nhiều?

Đối với tôi, việc sử dụng ổ khóa rõ ràng hơn và dễ hiểu hơn và thậm chí có thể tốt hơn để duy trì (vui lòng sửa tôi nếu tôi sai). Chúng ta có nên thực sự tập trung vào việc tạo ra mã đồng thời liên quan đến CAS của chúng ta hơn là các khóa để có được hiệu suất tốt hơn hoặc là tính bền vững quan trọng hơn?

Tôi biết có thể không phải là quy tắc nghiêm ngặt khi sử dụng cái gì. Nhưng tôi chỉ muốn nghe một số ý kiến, kinh nghiệm với khái niệm CAS mới.

Answer 1

CAS thường nhanh hơn nhiều so với khóa, nhưng nó phụ thuộc vào mức độ tranh chấp. Bởi vì CAS có thể buộc thử lại nếu giá trị thay đổi giữa đọc và so sánh, một chủ đề về mặt lý thuyết có thể bị kẹt trong sự chờ đợi nếu biến được đề cập đang bị nhiều chủ đề khác đánh mạnh (hoặc nếu tính toán giá trị mới từ giá trị cũ (hoặc cả hai)).

Vấn đề chính với CAS là khó lập trình với chính xác hơn là khóa. Thay vào đó, hãy nhớ rằng, việc khóa lại khó sử dụng chính xác hơn là gửi tin nhắn hoặc STM, vì vậy, đừng coi đây là sự chứng thực cho việc sử dụng khóa.

Answer 2

Bạn có thể xem các số giữa ConcurrentLinkedQueue và BlockingQueue. Những gì bạn sẽ thấy là CAS là đáng chú ý nhanh hơn dưới trung bình (thực tế hơn trong các ứng dụng thế giới thực) chủ đề conention.

Thuộc tính hấp dẫn nhất của thuật toán không chặn là thực tế là nếu một chuỗi bị lỗi (bộ nhớ cache bị lỗi hoặc tệ hơn, lỗi seg) thì các luồng khác sẽ không nhận thấy lỗi này và có thể tiếp tục. Tuy nhiên, khi mua một khóa, nếu khóa giữ thread có một số loại lỗi hệ điều hành, tất cả các thread khác chờ đợi cho khóa được giải phóng sẽ được nhấn với sự thất bại cũng có.

Để trả lời câu hỏi của bạn, có các thuật toán hoặc bộ sưu tập an toàn không chặn luồng (ConcurrentLinkedQueue, ConcurrentSkipListMap/Set) có thể nhanh hơn đáng kể so với các đối tác chặn của chúng. Như Marcelo đã chỉ ra, việc nhận các thuật toán nonblocking đúng là rất khó và đòi hỏi nhiều sự cân nhắc.

Bạn nên đọc về Michael and Scott Queue, đây là triển khai hàng đợi cho ConcurrentLinkedQueue và giải thích cách xử lý hai chiều, an toàn luồng, chức năng nguyên tử với một CAS đơn.

Answer 3

Có cuốn sách tốt liên quan chặt chẽ đến chủ đề của đồng thời lock-free: "The Art of lập trình đa xử lý" bởi Maurice Herlihy

Answer 4

Tốc độ tương đối của các hoạt động phần lớn là một vấn đề không. Điều có liên quan là sự khác biệt về khả năng mở rộng giữa các thuật toán dựa trên khóa và không chặn. Và nếu bạn đang chạy trên một hệ thống lõi 1 hoặc 2, hãy ngừng suy nghĩ về những điều như vậy.

Thuật toán không chặn thường có quy mô tốt hơn vì chúng có "phần quan trọng" ngắn hơn thuật toán dựa trên khóa.

Answer 5

Nếu bạn đang tìm kiếm một so sánh thế giới thực, dưới đây là một. Ứng dụng của chúng tôi có hai (2) chủ đề 1) Một chủ đề đọc cho việc nắm bắt gói mạng và 2) một chuỗi tiêu thụ nhận gói, đếm nó và báo cáo thống kê.

Chủ đề # 1 trao đổi một gói duy nhất tại một thời gian với chủ đề # 2

Kết quả # 1 - sử dụng một tùy chỉnh CAS dựa trao đổi bằng cách sử dụng cùng một nguyên tắc như SynchronousQueue, nơi lớp của chúng tôi được gọi là CASSynchronousQueue:

30,766,538 packets in 59.999 seconds :: 500.763Kpps, 1.115Gbps 0 drops 
libpcap statistics: recv=61,251,128, drop=0(0.0%), ifdrop=0 

quả # 2 - khi chúng ta thay thế thực hiện CAS của chúng tôi với java tiêu chuẩn S ynchronousQueue:

8,782,647 packets in 59.999 seconds :: 142.950Kpps, 324.957Mbps 0 drops 
libpcap statistics: recv=69,955,666, drop=52,369,516(74.9%), ifdrop=0 

Tôi không nghĩ rằng sự khác biệt về hiệu suất không thể rõ ràng hơn.