Spinlocks trọng lượng nhẹ được chế tạo từ các hoạt động nguyên tử GCC?

Question

Tôi muốn giảm thiểu đồng bộ hóa và viết mã không có khóa khi có thể trong dự án của tôi. Khi hoàn toàn cần thiết tôi muốn thay thế spinlocks trọng lượng nhẹ được xây dựng từ các hoạt động nguyên tử cho pthread và win32 mutex khóa. Sự hiểu biết của tôi là đây là các cuộc gọi hệ thống bên dưới và có thể gây ra một chuyển đổi ngữ cảnh (có thể không cần thiết cho các phần rất quan trọng mà chỉ cần quay vài lần là thích hợp hơn).

Các hoạt động nguyên tử tôi đề cập đến cũng là tài liệu ở đây: http://gcc.gnu.org/onlinedocs/gcc-4.4.1/gcc/Atomic-Builtins.html

Dưới đây là một ví dụ để minh họa cho những gì tôi đang nói về. Hãy tưởng tượng một cây RB với nhiều độc giả và nhà văn có thể. RBTree :: exist() là chỉ đọc và thread an toàn, RBTree :: insert() sẽ yêu cầu truy cập độc quyền bởi một nhà văn duy nhất (và không có độc giả) để được an toàn. Một số mã:

class IntSetTest 
{ 
private: 
    unsigned short lock; 
    RBTree<int>* myset; 

public: 
    // ... 

    void add_number(int n) 
    { 
     // Aquire once locked==false (atomic) 
     while (__sync_bool_compare_and_swap(&lock, 0, 0xffff) == false); 

     // Perform a thread-unsafe operation on the set 
     myset->insert(n); 

     // Unlock (atomic) 
     __sync_bool_compare_and_swap(&lock, 0xffff, 0); 
    } 

    bool check_number(int n) 
    { 
     // Increment once the lock is below 0xffff 
     u16 savedlock = lock; 
     while (savedlock == 0xffff || __sync_bool_compare_and_swap(&lock, savedlock, savedlock+1) == false) 
      savedlock = lock; 

     // Perform read-only operation  
     bool exists = tree->exists(n); 

     // Decrement 
     savedlock = lock; 
     while (__sync_bool_compare_and_swap(&lock, savedlock, savedlock-1) == false) 
      savedlock = lock; 

     return exists; 
    } 
}; 

(cho phép giả định nó không cần phải ngoại lệ an toàn)

Là mã này thực sự thread-an toàn không? Có bất kỳ ưu/khuyết điểm nào đối với ý tưởng này không? Lời khuyên nào? Việc sử dụng spinlocks như thế này là một ý tưởng tồi nếu các chủ đề không thực sự đồng thời?

Xin cảm ơn trước. ;)

Answer 1

Bạn cần một mã định danh volatile trên lock và tôi cũng sẽ làm cho nó là sig_atomic_t. Nếu không có sự volatile vòng loại, mã này:

u16 savedlock = lock; 
    while (savedlock == 0xffff || __sync_bool_compare_and_swap(&lock, savedlock, savedlock+1) == false) 
     savedlock = lock; 

có thể không đọc lại lock khi cập nhật savedlock trong cơ thể của vòng lặp while. Hãy xem xét trường hợp lock là 0xffff. Sau đó, savedlock sẽ là 0xffff trước khi kiểm tra điều kiện vòng lặp, do đó, điều kiện while sẽ ngắn mạch trước khi gọi __sync_bool_compare_and_swap. Vì __sync_bool_compare_and_swap không được gọi, trình biên dịch không gặp phải rào cản bộ nhớ, vì vậy có thể giả định hợp lý rằng giá trị của lock không thay đổi bên dưới bạn và tránh tải lại nó trong savedlock.

Re: sig_atomic_t, có thảo luận chi tiết here. Các cân nhắc tương tự áp dụng cho các trình xử lý tín hiệu cũng sẽ áp dụng cho các luồng.

Với những thay đổi này, tôi đoán rằng mã của bạn sẽ an toàn chỉ. Tôi vẫn sẽ khuyên bạn nên sử dụng mutexes, mặc dù, vì bạn thực sự không biết bao lâu RB-cây chèn của bạn sẽ mất trong trường hợp chung (mỗi bình luận trước đây của tôi theo câu hỏi).

Answer 2

Có thể đáng lưu ý rằng nếu bạn đang sử dụng các mutex của Win32, từ Vista trở đi, một nhóm luồng sẽ được cung cấp cho bạn. Tùy thuộc vào những gì bạn sử dụng cây RB cho, bạn có thể thay thế bằng điều đó.

Ngoài ra, điều bạn nên nhớ là các hoạt động nguyên tử không phải là đặc biệt nhanh. Microsoft cho biết họ là một vài trăm chu kỳ, mỗi chu kỳ. Thay vì cố gắng "bảo vệ" chức năng theo cách này, nó có thể sẽ hiệu quả hơn nhiều khi chỉ đơn giản là đồng bộ hóa các chủ đề, hoặc thay đổi theo cách tiếp cận hồ bơi SIMD/thread, hoặc chỉ sử dụng một mutex.

Nhưng, tất nhiên, không nhìn thấy mã của bạn, tôi thực sự không thể tạo thêm bất kỳ nhận xét nào. Vấn đề với đa luồng là bạn phải xem toàn bộ mô hình của ai đó để hiểu nó.