Làm thế nào để chứng minh rằng mô hình kiểm tra lại-lock với từ điển của TryGetValue không threadsafe

Question

Gần đây tôi đã nhìn thấy một số dự án C# sử dụng một mô hình kiểm tra lại-lock trên Dictionary. Một cái gì đó như thế này:

private static readonly object _lock = new object(); 
private static volatile IDictionary<string, object> _cache = 
    new Dictionary<string, object>(); 

public static object Create(string key) 
{ 
    object val; 
    if (!_cache.TryGetValue(key, out val)) 
    { 
     lock (_lock) 
     { 
      if (!_cache.TryGetValue(key, out val)) 
      { 
       val = new object(); // factory construction based on key here. 
       _cache.Add(key, val); 
      } 
     } 
    } 
    return val; 
} 

Mã này là không chính xác, vì Dictionary có thể được "phát triển" bộ sưu tập trong _cache.Add() khi _cache.TryGetValue (bên ngoài khóa) được lặp lại trên bộ sưu tập. Nó có thể là rất khó xảy ra trong nhiều tình huống, nhưng vẫn còn sai.

Có một chương trình đơn giản để chứng minh rằng mã này không thành công?

Có hợp lý khi kết hợp điều này vào thử nghiệm đơn vị không? Và nếu vậy, làm thế nào?

Answer 1

Trong ví dụ này, ngoại trừ # 1 được ném gần như ngay lập tức trên máy tính của tôi:

var dict = new Dictionary<int, string>() { { 1234, "OK" } }; 

new Thread(() => 
{ 
    for (; ;) 
    { 
     string s; 
     if (!dict.TryGetValue(1234, out s)) 
     { 
      throw new Exception(); // #1 
     } 
     else if (s != "OK") 
     { 
      throw new Exception(); // #2 
     } 
    } 
}).Start(); 

Thread.Sleep(1000); 
Random r = new Random(); 
for (; ;) 
{ 
    int k; 
    do { k = r.Next(); } while (k == 1234); 
    Debug.Assert(k != 1234); 
    dict[k] = "FAIL"; 
} 

Tuy nhiên, hành vi chính xác mã mà không được thiết kế để được thread-an toàn là không thể đoán trước .
Bạn không thể dựa vào nó. Vì vậy, mã kiểm tra kép thực sự bị hỏng.

Tôi không chắc chắn nếu tôi muốn kiểm tra đơn vị này, tuy nhiên, như kiểm tra mã đồng thời (và nhận được nó phải) là phức tạp hơn nhiều so với việc viết mã đồng thời ở nơi đầu tiên.

Answer 2

Bao gồm mã trong câu hỏi, bạn có thể thử nghiệm nó với đoạn mã sau.

//using System.Collections.Generic; 
//using System.Threading; 

private static volatile int numRunning = 2; 
private static volatile int spinLock = 0; 

static void Main(string[] args) 
{ 
    new Thread(TryWrite).Start(); 
    new Thread(TryWrite).Start(); 
} 

static void TryWrite() 
{ 
    while(true) 
    { 
     for (int i = 0; i < 1000000; i++) 
     { 
      Create(i.ToString()); 
     } 

     Interlocked.Decrement(ref numRunning); 
     while (numRunning > 0) { } // make sure every thread has passed the previous line before proceeding (call this barrier 1) 

     while (Interlocked.CompareExchange(ref spinLock, 1, 0) != 0){Thread.Sleep(0);} // Aquire lock (spin lock) 
     // only one thread can be here at a time... 

     if (numRunning == 0) // only the first thread to get here executes this... 
     { 
      numRunning = 2; // resets barrier 1 
      // since the other thread is beyond the barrier, but is waiting on the spin lock, 
      // nobody is accessing the cache, so we can clear it... 
      _cache = new Dictionary<string, object>(); // clear the cache... 
     } 

     spinLock = 0; // release lock... 
    } 

} 

Chương trình này chỉ cố gắng lấy Create để duyệt bộ sưu tập khi nó đang được "phát triển". Nó sẽ được chạy trên một máy có ít nhất hai lõi (hoặc hai bộ xử lý), và rất có thể sẽ thất bại sau một thời gian với ngoại lệ này.

System.Collections.Generic.Dictionary`2.FindEntry(TKey key) 

Thêm thử nghiệm này rất khó vì đây là thử nghiệm xác suất và bạn không biết mất bao lâu (nếu có). Tôi đoán bạn có thể chọn một giá trị như 10 giây và để nó chạy trong thời gian dài. Nếu nó không thất bại trong khoảng thời gian đó, thì bài kiểm tra sẽ trôi qua. Không phải là tốt nhất, nhưng một cái gì đó. Bạn cũng nên xác minh rằng Environment.ProcessorCount > 1 trước khi chạy thử nghiệm, nếu không khả năng bị lỗi là trừ đi.

Answer 3

tôi không thực sự nghĩ rằng bạn cần để chứng minh điều này, bạn chỉ cần tham khảo mọi người đến documentation for Dictionary<TKey, TValue>: từ điển

A có thể hỗ trợ nhiều độc giả đồng thời, miễn là bộ sưu tập là không được sửa đổi. Mặc dù vậy, việc đếm qua bộ sưu tập thực chất là không phải là quy trình an toàn chỉ. Trong trường hợp hiếm hoi mà một liệt kê có liên quan đến quyền ghi, bộ sưu tập phải được khóa trong toàn bộ liệt kê. Để cho phép bộ sưu tập được truy cập bởi nhiều luồng để đọc và viết, bạn phải thực hiện đồng bộ hóa của riêng mình.

Thực tế là một thực tế nổi tiếng (hoặc phải là) mà bạn không thể đọc từ điển trong khi một chủ đề khác đang viết cho nó.Tôi đã nhìn thấy một vài "vấn đề đa luồng kỳ quái" ở đây trên SO, hóa ra tác giả đã không nhận ra rằng điều này không an toàn.

Sự cố không liên quan cụ thể đến khóa được kiểm tra kép, chỉ là từ điển không phải là một lớp an toàn cho chủ đề, ngay cả đối với kịch bản một người viết/độc giả.

---

Tôi sẽ đi một bước xa hơn và cho bạn thấy lý do tại sao, trong suy nghi, đây không phải là thread-safe:

private int FindEntry(TKey key) 
{ 
    // Snip a bunch of code 
    for (int i = this.buckets[num % this.buckets.Length]; i >= 0; 
     i = this.entries[i].next) 
    // Snip a bunch more code 
} 

private void Resize() 
{ 
    int prime = HashHelpers.GetPrime(this.count * 2); 
    int[] numArray = new int[prime]; 
    // Snip a whole lot of code 
    this.buckets = numArray; 
} 

Nhìn vào những gì có thể xảy ra nếu các phương pháp Resize xảy ra để được chạy trong khi ngay cả một người đọc gọi FindEntry:

1. Chủ đề A: Thêm thành phần, dẫn đến thay đổi kích thước động;
2. Chủ đề B: Tính toán độ lệch của nhóm như (mã băm% số lượng nhóm);
3. Chủ đề A: Thay đổi các nhóm có kích thước (nguyên tố) khác;
4. Chủ đề B: Chọn chỉ mục phần tử từ mảng xô mới tại chỉ số nhóm cũ;
5. Con trỏ của chủ đề B không còn giá trị.

Và đây chính xác là điều không thành công trong ví dụ của dtb. Chủ đề Một tìm kiếm cho một khóa là được biết trước để có trong từ điển, nhưng nó không được tìm thấy. Tại sao? Bởi vì phương pháp FindValue chọn những gì nó nghĩ là xô đúng, nhưng trước khi nó thậm chí còn có cơ hội nhìn vào bên trong, Thread B đã thay đổi các thùng, và bây giờ Thread A đang tìm trong một số nhóm hoàn toàn ngẫu nhiên không chứa hoặc thậm chí dẫn đến mục nhập đúng.

Đạo đức của câu chuyện: TryGetValue không phải là hoạt động nguyên tử và Dictionary<TKey, TValue> không phải là lớp an toàn theo chủ đề. Nó không chỉ là viết đồng thời mà bạn cần phải lo lắng; bạn cũng không thể đọc đồng thời. Trong thực tế, vấn đề thực sự chạy sâu hơn rất nhiều, do hướng dẫn sắp xếp lại bởi jitter và CPU, cache cũ, v.v. - không có rào cản bộ nhớ nào được sử dụng ở đây - nhưng điều này phải chứng minh vượt quá sự nghi ngờ rằng có một điều kiện chủng tộc rõ ràng nếu bạn có yêu cầu Add chạy cùng lúc với yêu cầu TryGetValue.

Answer 4

Lý do tôi đoán câu hỏi này đi lên một lần nữa và một lần nữa:

Pre-2.0, Trước Generics (B.G.), Hashtable là container kết hợp chính trong .NET, mà thực sự cung cấp một số bảo đảm luồng. Từ MSDN:
"Hashtable là chủ đề an toàn để sử dụng cho nhiều chủ đề của trình đọc và một chủ đề viết đơn. Đây là chủ đề an toàn cho việc sử dụng đa luồng khi chỉ có một chủ đề thực hiện thao tác ghi (cập nhật), cho phép khóa miễn phí lần đọc miễn là các nhà văn được đăng theo thứ tự đến Hashtable. "

Trước khi mọi người nhận được cực kỳ vui mừng, có một số hạn chế.
Xem ví dụ:this post from Brad Abrams, người sở hữu Hashtable.
Một số bối cảnh lịch sử thêm về Hashtable thể được tìm thấy here (...near the end: "After this lengthy diversion - What about Hashtable?").

Tại sao Dictionary<TKey, TValue> thất bại trong trường hợp trên:

Để chứng minh rằng nó không thành công, nó là đủ để tìm một ví dụ, vì vậy tôi sẽ hãy thử điều đó.
Thay đổi kích thước sẽ xảy ra khi bảng tăng lên.
On thay đổi kích thước, một rehash xảy ra và một xem đây là hai dòng cuối cùng:

this.buckets = newBuckets; 
//One of the problems here. 
this.entries = newEntries; 

Mảng buckets giữ chỉ số vào mảng entries. Hãy nói rằng chúng tôi có 10 mục cho đến nay và ngay bây giờ chúng tôi đang thêm một mới.
Hãy tiếp tục giả vờ vì lợi ích của sự đơn giản mà chúng tôi đã không và sẽ không bị va chạm.
Trong số buckets cũ, chúng tôi đã lập chỉ mục chạy từ 0 đến 9 - nếu chúng tôi không có xung đột.
Bây giờ các chỉ mục trong mảng buckets mới chạy từ 0 đến 10 (!).
Bây giờ chúng tôi thay đổi trường buckets riêng để trỏ đến các nhóm mới.
Nếu có một người đọc làm TryGetValue() tại thời điểm này, nó sử dụng xô mới để có được chỉ số, nhưng sau đó sử dụng mới chỉ số để đọc vào mảng cũ mục, kể từ khi lĩnh vực entries vẫn trỏ tới các mục cũ.
Một trong những điều mà người ta có thể nhận được - ngoài việc đọc sai - là một số IndexOutOfRangeException thân thiện.
Một cách "tuyệt vời" khác để có được điều này là trong giải thích @Aaronaught's. (... và cả hai có thể xảy ra, ví dụ như trong ví dụ dtb's).

Đây thực sự chỉ là một ví dụ, Dictonary không được thiết kế và không bao giờ có nghĩa là an toàn chỉ. Nó được thiết kế để được nhanh chóng, tuy nhiên - đó có nghĩa là khóa sẽ không được tổ chức trong thời gian dài.

Answer 5

Rõ ràng mã không an toàn. Những gì chúng tôi có ở đây là một trường hợp rõ ràng về các mối nguy hiểm của việc tối ưu hóa sớm.

Hãy nhớ rằng, mục đích của mẫu khóa được kiểm tra kép là cải thiện hiệu suất mã bằng cách loại bỏ chi phí khóa. Nếu khóa là uncontested nó là cực kỳ rẻ tiền rồi. Do đó, mẫu khóa được kiểm tra kép chỉ được hợp lý trong các trường hợp (1) trong đó khóa sẽ bị tranh chấp nhiều, hoặc (2) trong đó mã là cực kỳ nhạy cảm với hiệu suất mà chi phí của khóa không bị khóa là vẫn còn quá cao.

Rõ ràng chúng tôi không thuộc trường hợp thứ hai. Bạn đang sử dụng một từ điển vì lợi ích của thiên đàng. Ngay cả khi không có khóa nó sẽ được thực hiện tra cứu và so sánh đó sẽ là hàng trăm hoặc hàng ngàn lần đắt hơn tiết kiệm của tránh một khóa không được kiểm soát.

Nếu chúng tôi đang trong trường hợp đầu tiên thì tìm ra nguyên nhân gây tranh chấp và loại bỏ điều đó.Nếu bạn đang làm rất nhiều chờ đợi xung quanh trên một khóa sau đó tìm ra lý do tại sao đó là và thay thế các khóa với một người đọc-ghi-khóa mỏng hoặc cơ cấu lại các ứng dụng để không quá nhiều chủ đề đang đập trên cùng một khóa tại cùng một thời gian.

Trong cả hai trường hợp, không có lý do nào để thực hiện các kỹ thuật khóa thấp, nguy hiểm, có tính thực thi. Bạn chỉ nên sử dụng các kỹ thuật khóa thấp trong những trường hợp cực kỳ hiếm hoi mà bạn thực sự, thực sự không thể lấy chi phí của một khóa không bị cản trở.