Khóa vs So sánh và hoán đổi

Question

Tôi đã đọc về các kỹ thuật không có khóa, như So sánh và trao đổi và tận dụng các lớp Interlocked và SpinWait để đạt được đồng bộ hóa luồng mà không cần khóa.

Tôi đã chạy một vài thử nghiệm của riêng mình, nơi tôi chỉ đơn giản là có nhiều chủ đề cố gắng gắn thêm một ký tự vào một chuỗi. Tôi đã thử sử dụng thường xuyên lock s và so sánh và trao đổi. Đáng ngạc nhiên (ít nhất là với tôi), ổ khóa cho thấy kết quả tốt hơn nhiều so với sử dụng CAS.

Đây là phiên bản CAS của mã của tôi (dựa trên this). Nó sau một mô hình copy-> Modify-> swap:

private string _str = ""; 
    public void Append(char value) 
    { 
     var spin = new SpinWait(); 
     while (true) 
     { 
      var original = Interlocked.CompareExchange(ref _str, null, null); 

      var newString = original + value;     
      if (Interlocked.CompareExchange(ref _str, newString, original) == original) 
       break; 
      spin.SpinOnce(); 
     } 
    } 

Và phiên bản khóa đơn giản (và hiệu quả hơn):

private object lk = new object(); 
    public void AppendLock(char value) 
    { 
     lock (lk) 
     { 
      _str += value; 
     } 
    } 

Nếu tôi cố gắng thêm 50.000 ký tự, phiên bản CAS mất 1.2 giây và khóa phiên bản 700ms (trung bình). Đối với 100k ký tự, chúng mất 7 giây và 3,8 giây tương ứng. Điều này được chạy trên một quad-core (i5 2500k).

Tôi nghi ngờ lý do CAS hiển thị các kết quả này là do không thực hiện bước "hoán đổi" cuối cùng nhiều. Tôi đã đúng. Khi tôi thử thêm 50 nghìn ký tự (50 nghìn lần hoán đổi thành công), tôi có thể đếm từ 70k (trường hợp tốt nhất) và gần như 200k (kịch bản xấu nhất) thất bại. Kịch bản trường hợp xấu nhất, 4 trong số 5 lần thử không thành công.

Vì vậy, câu hỏi của tôi là:

1. tôi thiếu gì? CAS có nên cho kết quả tốt hơn không? Lợi ích ở đâu?
2. Tại sao CAS chính xác và khi nào là một lựa chọn tốt hơn? (Tôi biết điều này đã được yêu cầu, nhưng tôi không thể tìm thấy bất kỳ câu trả lời thỏa mãn nào cũng giải thích kịch bản cụ thể của tôi).

Đó là sự hiểu biết của tôi rằng các giải pháp sử dụng CAS, mặc dù khó viết mã, quy mô tốt hơn nhiều và thực hiện tốt hơn so với khóa khi tranh chấp tăng lên. Trong ví dụ của tôi, các hoạt động rất nhỏ và thường xuyên, có nghĩa là tranh chấp cao và tần số cao. Vậy tại sao các bài kiểm tra của tôi cho thấy khác?

Tôi giả định rằng các hoạt động dài hơn sẽ làm cho trường hợp thậm chí tệ hơn -> tỷ lệ thất bại "hoán đổi" sẽ tăng nhiều hơn.

PS: đây là đoạn code tôi sử dụng để chạy các bài kiểm tra:

Stopwatch watch = Stopwatch.StartNew(); 
var cl = new Class1(); 
Parallel.For(0, 50000, i => cl.Append('a')); 

var time = watch.Elapsed; 
Debug.WriteLine(time.TotalMilliseconds); 

Answer 1

Vấn đề là sự kết hợp của tỷ lệ thất bại trên vòng lặp và thực tế là chuỗi là không thay đổi. Tôi đã tự làm một vài thử nghiệm bằng cách sử dụng các tham số sau đây.

• Đã chạy 8 chủ đề khác nhau (Tôi có máy 8 lõi).
• Mỗi chuỗi được gọi là Append 10.000 lần.

Điều tôi quan sát được là độ dài cuối cùng của chuỗi là 80.000 (8 x 10.000) sao cho hoàn hảo. Số lần thử thêm vào trung bình ~ 300.000 cho tôi. Đó là tỷ lệ thất bại ~ 73%. Chỉ 27% thời gian CPU dẫn đến công việc hữu ích. Bây giờ bởi vì chuỗi là bất biến có nghĩa là một thể hiện mới của chuỗi được tạo trên heap và nội dung gốc cộng với một ký tự phụ được sao chép vào nó.Nhân tiện, thao tác sao chép này là O (n) để nó hoạt động lâu hơn và dài hơn khi độ dài của chuỗi tăng lên. Bởi vì các hoạt động sao chép giả thuyết của tôi là tỷ lệ thất bại sẽ tăng lên khi chiều dài của chuỗi tăng lên. Lý do là vì hoạt động sao chép mất nhiều thời gian hơn và có nhiều khả năng xảy ra xung đột khi các chủ đề dành nhiều thời gian hơn để cạnh tranh để hoàn thành ICX. Các bài kiểm tra của tôi đã xác nhận điều này. Bạn nên thử cùng một bài kiểm tra này.

Vấn đề lớn nhất ở đây là các chuỗi nối tiếp tuần tự không cho phép chúng tương đương với nhau. Kể từ khi kết quả của hoạt động X _n phụ thuộc vào X _n-1 nó sẽ nhanh hơn để có khóa đầy đủ đặc biệt là nếu nó có nghĩa là bạn tránh tất cả các thất bại và thử lại. Một chiến lược bi quan thắng trận chiến chống lại một chiến thắng lạc quan trong trường hợp này. Các kỹ thuật thấp làm việc tốt hơn khi bạn có thể phân vùng vấn đề thành các bảng độc lập mà thực sự có thể chạy không bị cản trở song song.

Lưu ý rằng việc sử dụng Interlocked.CompareExchange để đọc ban đầu _str là không cần thiết. Lý do là một rào cản bộ nhớ là không cần thiết cho việc đọc trong trường hợp này. Điều này là do cuộc gọi Interlocked.CompareExchange thực sự thực hiện công việc (mã thứ hai trong mã của bạn) sẽ tạo ra một rào cản đầy đủ. Vì vậy, kịch bản trường hợp xấu nhất là đọc đầu tiên là "cũ", hoạt động ICX không kiểm tra, và vòng quay quay lại để thử lại. Lần này, tuy nhiên, ICX trước đó đã buộc phải đọc "mới".

Mã sau đây là cách tôi tổng quát hóa hoạt động phức tạp bằng cơ chế khóa thấp. Trong thực tế, mã được trình bày dưới đây cho phép bạn chuyển một đại biểu đại diện cho hoạt động để nó được tổng quát hóa. Bạn có muốn sử dụng nó trong sản xuất? Có lẽ không phải vì việc gọi đại biểu là chậm, nhưng bạn ít nhất bạn có được ý tưởng. Bạn luôn có thể mã hóa hoạt động.

public static class InterlockedEx 
{ 
    public static T Change<T>(ref T destination, Func<T, T> operation) where T : class 
    { 
    T original, value; 
    do 
    { 
     original = destination; 
     value = operation(original); 
    } 
    while (Interlocked.CompareExchange(ref destination, value, original) != original); 
    return original; 
    } 
} 

---

Tôi thực sự không thích các thuật ngữ "cũ" và "tươi" khi thảo luận về rào cản bộ nhớ bởi vì đó không phải là những gì họ đang thực sự về. Đó là nhiều hơn một tác dụng phụ như trái ngược với bảo đảm thực tế. Nhưng, trong trường hợp này nó minh họa quan điểm của tôi tốt hơn.