Các rào cản bộ nhớ và các hoạt động liên khóa

Question

Tôi đang cố gắng cải thiện sự hiểu biết của mình về các rào cản bộ nhớ. Giả sử chúng ta có một mô hình bộ nhớ yếu và chúng ta thích ứng với Dekker's algorithm. Có thể làm cho nó hoạt động chính xác theo mô hình bộ nhớ yếu bằng cách thêm các rào cản bộ nhớ?

Tôi nghĩ câu trả lời là không đáng ngạc nhiên. Lý do (nếu tôi đúng) là mặc dù một rào cản bộ nhớ có thể được sử dụng để đảm bảo rằng một đọc không được di chuyển qua khác, nó không thể đảm bảo rằng một đọc không nhìn thấy dữ liệu cũ (chẳng hạn như trong bộ đệm). Vì vậy, nó có thể thấy một số thời gian trong quá khứ khi phần quan trọng đã được mở khóa (theo bộ nhớ cache của CPU) nhưng tại thời điểm hiện tại các bộ vi xử lý khác có thể nhìn thấy nó như bị khóa. Nếu sự hiểu biết của tôi là chính xác, người ta phải sử dụng các hoạt động liên khóa như những người thường gọi là kiểm tra và đặt hoặc so sánh và trao đổi để đảm bảo thỏa thuận đồng bộ của một giá trị tại một vị trí bộ nhớ giữa nhiều bộ xử lý.

Vì vậy, chúng ta có thể mong đợi rằng không có hệ thống mô hình bộ nhớ yếu sẽ chỉ cung cấp các rào cản bộ nhớ? Hệ thống phải cung cấp các hoạt động như kiểm tra và thiết lập hoặc so sánh và trao đổi để có ích.

Tôi nhận thấy rằng các bộ vi xử lý phổ biến, bao gồm x86, cung cấp các mô hình bộ nhớ mạnh hơn nhiều so với mô hình bộ nhớ yếu. Hãy tập trung thảo luận về các mô hình bộ nhớ yếu.

(Nếu thuật toán Dekker là một sự lựa chọn tốt, chọn một thuật toán loại trừ lẫn nhau nơi rào cản bộ nhớ thành công có thể đạt được đồng bộ chính xác, nếu có thể.)

Answer 1

Bạn đúng rằng rào cản bộ nhớ không thể đảm bảo rằng một lần đọc thấy các giá trị cập nhật. Những gì nó làm là thực thi một thứ tự giữa các phép toán, cả trên một luồng đơn lẻ và giữa các luồng. Ví dụ, nếu chuỗi A thực hiện một loạt các cửa hàng và sau đó thực hiện một hàng rào phát hành trước khi một cửa hàng cuối cùng đến một vị trí cờ, và chủ đề B đọc từ vị trí cờ và sau đó thực hiện một rào cản có được trước khi đọc các giá trị khác sau đó các biến khác sẽ có những giá trị được lưu trữ bởi thread A:

// initially x=y=z=flag=0 

// thread A 
x=1; 
y=2; 
z=3; 
release_barrier(); 
flag=1; 

// thread B 
while(flag==0) ; // loop until flag is 1 
acquire_barrier(); 
assert(x==1); // asserts will not fire 
assert(y==2); 
assert(z==3); 

Tất nhiên, bạn cần phải đảm bảo rằng các tải và cất giữ để flag là nguyên tử (mà đơn giản tải và lưu trữ hướng dẫn có trên CPU phổ biến nhất, miễn là các biến được điều chỉnh phù hợp). Nếu không có vòng lặp while trong thread B, thread B có thể đọc một giá trị cũ (0) cho flag, và do đó bạn không thể đảm bảo bất kỳ giá trị nào được đọc cho các biến khác.

Hàng rào có thể được sử dụng để thực thi đồng bộ hóa trong thuật toán của Dekker.

Dưới đây là một thực hiện ví dụ trong C++ (sử dụng các biến nguyên tử C++ 0x):

std::atomic<bool> flag0(false),flag1(false); 
std::atomic<int> turn(0); 

void p0() 
{ 
    flag0.store(true,std::memory_order_relaxed); 
    std::atomic_thread_fence(std::memory_order_seq_cst); 

    while (flag1.load(std::memory_order_relaxed)) 
    { 
     if (turn.load(std::memory_order_relaxed) != 0) 
     { 
      flag0.store(false,std::memory_order_relaxed); 
      while (turn.load(std::memory_order_relaxed) != 0) 
      { 
      } 
      flag0.store(true,std::memory_order_relaxed); 
      std::atomic_thread_fence(std::memory_order_seq_cst); 
     } 
    } 
    std::atomic_thread_fence(std::memory_order_acquire); 

    // critical section 


    turn.store(1,std::memory_order_relaxed); 
    std::atomic_thread_fence(std::memory_order_release); 
    flag0.store(false,std::memory_order_relaxed); 
} 

void p1() 
{ 
    flag1.store(true,std::memory_order_relaxed); 
    std::atomic_thread_fence(std::memory_order_seq_cst); 

    while (flag0.load(std::memory_order_relaxed)) 
    { 
     if (turn.load(std::memory_order_relaxed) != 1) 
     { 
      flag1.store(false,std::memory_order_relaxed); 
      while (turn.load(std::memory_order_relaxed) != 1) 
      { 
      } 
      flag1.store(true,std::memory_order_relaxed); 
      std::atomic_thread_fence(std::memory_order_seq_cst); 
     } 
    } 
    std::atomic_thread_fence(std::memory_order_acquire); 

    // critical section 


    turn.store(0,std::memory_order_relaxed); 
    std::atomic_thread_fence(std::memory_order_release); 
    flag1.store(false,std::memory_order_relaxed); 
} 

Đối với một phân tích đầy đủ xem blog entry của tôi tại http://www.justsoftwaresolutions.co.uk/threading/implementing_dekkers_algorithm_with_fences.html

Answer 2

Một số rào cản (ví dụ như iSync powerpc, và một tải .acq trên ia64) cũng có ảnh hưởng đến tải trọng. tức là: nếu một tải có sẵn trước khi đồng bộ do tìm nạp trước nó phải được loại bỏ. Khi được sử dụng một cách thích hợp có lẽ đó là đủ để làm cho thuật toán của Dekker hoạt động trên một mô hình bộ nhớ yếu.

Bạn cũng có logic không hợp lệ bộ nhớ cache hoạt động cho bạn. Nếu bạn biết rằng tải của bạn là hiện tại do một cái gì đó giống như một đồng bộ và phiên bản được lưu trữ của dữ liệu bị vô hiệu hóa nếu một CPU khác chạm vào nó, thì có đủ không?

Câu hỏi thú vị sang một bên, thuật toán của Dekker là dành cho tất cả các mục đích thực tế câm. Bạn sẽ muốn sử dụng các giao diện phần cứng nguyên tử và các rào cản bộ nhớ cho bất kỳ ứng dụng thực tế nào, vì vậy hãy tập trung vào cách sửa chữa Dekker với các nguyên tử không có vẻ đáng giá đối với tôi;)

Answer 3

Giả sử bạn đặt trong một tải và lưu trữ rào cản sau mỗi tuyên bố, và ngoài ra bạn đảm bảo rằng trình biên dịch không sắp xếp lại các cửa hàng của bạn. Điều này không, trên bất kỳ kiến ​​trúc hợp lý nào, cung cấp sự nhất quán nghiêm ngặt? Dekker hoạt động trên các kiến ​​trúc liên tục. Tính nhất quán tuần tự là một điều kiện yếu hơn tính nhất quán nghiêm ngặt.

http://www.cs.nmsu.edu/~pfeiffer/classes/573/notes/consistency.html

Thậm chí trên một CPU mà có một mô hình nhất quán yếu, bạn vẫn mong đợi bộ nhớ cache sự gắn kết. Tôi nghĩ rằng nơi mà mọi thứ bị trật bánh là hành vi của bộ đệm cửa hàng và đọc lần đầu, và những hoạt động có sẵn ghi lưu trữ tuôn ra và làm mất hiệu lực đọc đầu cơ. Nếu không có hàng rào tải có thể làm mất hiệu lực lần đọc đầu cơ, hoặc không có hàng rào viết để xóa bộ đệm cửa hàng, ngoài việc không thể triển khai Dekker, bạn sẽ không thể thực hiện một mutex!

Vì vậy, đây là khiếu nại của tôi. Nếu bạn có một rào cản ghi có sẵn, và một rào cản đọc, và bộ nhớ cache là mạch lạc giữa các CPU, thì bạn có thể làm cho tất cả các mã liên tục bằng cách xóa ghi (hàng rào cửa hàng) sau mỗi lệnh và các suy đoán xả (đọc hàng rào) trước mỗi chỉ dẫn. Vì vậy, tôi tuyên bố rằng bạn không cần atomics cho những gì bạn đang nói về, và rằng bạn có thể làm những gì bạn cần với Dekker chỉ. Chắc chắn bạn sẽ không muốn.

BTW, Corensic, công ty tôi làm việc cho, viết các công cụ tuyệt vời để gỡ lỗi các vấn đề tương tranh. Hãy xem http://www.corensic.com.