Có thể cạnh tranh các hoạt động nguyên tử không?

Question

Hãy tưởng tượng một chương trình có hai luồng. Họ đang chạy đoạn mã sau (CAS đề cập đến Compare and Swap):

// Visible to both threads 
static int test; 

// Run by thread A 
void foo() 
{ 
    // Check if value is 'test' and swap in 0xdeadbeef 
    while(!CAS(&test, test, 0xdeadbeef)) {} 
} 

// Run by thread B 
void bar() 
{ 
    while(1) { 
     // Perpetually atomically write rand() into the test variable 
     atomic_write(&test, rand()); 
    } 
} 

Có thể cho thread B để vĩnh viễn gây ra thread của CAS thất bại như vậy 0xdeadbeef không bao giờ được ghi vào 'thử'? Hay tự nhiên lập kế hoạch jitter có nghĩa là trong thực tế điều này không bao giờ xảy ra? Điều gì sẽ xảy ra nếu một số công việc được thực hiện bên trong vòng lặp while A?

Answer 1

Là một vấn đề lý thuyết, có. Nếu bạn có thể quản lý bằng cách nào đó để có được hai chuỗi đang chạy ở chế độ khóa như thế này

 
    time  thread A  thread B 
    ----  --------  -------- 
    ||  CAS 
    ||     atomic_write 
    ||  CAS 
    \/     atomic_write 

Sau đó, CAS sẽ không bao giờ trở lại đúng sự thật.

Trong thực tế, điều này sẽ không bao giờ xảy ra khi các chủ đề chia sẻ CPU/Core và không xảy ra khi các luồng đang chạy trên các CPU hoặc lõi khác nhau. Trong thực tế nó là cực kỳ không xảy ra trong nhiều chu kỳ, và thiên văn không xảy ra với nhiều hơn một lượng tử lịch trình.

Và đó là nếu mã này

void foo() 
{ 
    // Check if value is 'test' and swap in 0xdeadbeef 
    while(!CAS(&test, test, 0xdeadbeef)) {} 
} 

làm những gì nó xuất hiện để làm, mà là để lấy giá trị hiện tại của test, và so sánh nó với test để xem nếu nó đã thay đổi. Trong các lần lặp lại của thế giới thực của CAS sẽ được phân tách bằng mã thực hiện công việc thực tế. Các từ khóa volatile sẽ là cần thiết để đảm bảo rằng trình biên dịch lấy thử nghiệm trước khi gọi CAS thay vì giả định rằng một bản sao nó vẫn có thể có trong sổ đăng ký vẫn hợp lệ.

Hoặc giá trị bạn sẽ thử nghiệm sẽ không là giá trị hiện tại của thử nghiệm, mà là một số loại giá trị được biết gần đây nhất.

Nói cách khác, ví dụ mã này là một thử nghiệm của lý thuyết, nhưng bạn sẽ không sử dụng CAS như thế này trong thực tế, vì vậy ngay cả khi bạn có thể làm được điều này, nó không nhất thiết phải cho bạn biết thất bại khi được sử dụng trong các thuật toán thế giới thực.

Answer 2

Đói đói chắc chắn có thể xảy ra trong những trường hợp như vậy. Trích dẫn the wikipedia page,

Nó cũng đã chỉ ra rằng rộng rãi có sẵn nguyên tử có điều kiện nguyên thủy, CAS và LL/SC, không có thể cung cấp đói miễn triển khai của nhiều dữ liệu chung cấu trúc mà không cần chi phí bộ nhớ phát triển tuyến tính trong số các chủ đề . Do đó, các thuật toán miễn phí là hiếm, cả trong nghiên cứu và trong thực tế.

(Xem liên kết từ trang được đề cập để tìm bằng chứng toán học).