C++ 11 nguyên tử: tại sao mã này hoạt động?

Question

Chúng ta hãy struct này:

struct entry { 
    atomic<bool> valid; 
    atomic_flag writing; 
    char payload[128]; 
} 

Hai treads A và B đồng thời truy cập struct này theo cách này (giả sử e là một thể hiện của entry):

if (e.valid) { 
    // do something with e.payload... 
} else { 
    while (e.writing.test_and_set(std::memory_order_acquire)); 
    if (!e.valid) { 
     // write e.payload one byte at a time 
     // (the payload written by A may be different from the payload written by B) 
     e.valid = true; 
     e.writing.clear(std::memory_order_release); 
    } 
} 

Tôi đoán rằng mã này là chính xác và không trình bày vấn đề, nhưng tôi muốn hiểu tại sao nó hoạt động.

Trích dẫn tiêu chuẩn C++ (29.3.13):

Triển khai nên các cửa hàng nguyên tử có thể nhìn thấy tải nguyên tử trong một số tiền hợp lý thời gian.

Bây giờ, hãy ghi nhớ rằng cả hai luồng A và B đều nhập khối else. Điều này xen kẽ có thể?

1. Cả A và B nhập chi nhánh else, vì valid là false
2. A đặt writing cờ
3. B bắt đầu quay khóa trên lá cờ writing
4. A đọc valid cờ (đó là false) và nhập vào if khối
5. A ghi trọng tải
6. A viết true trên cờ hợp lệ; Rõ ràng, nếu A đọc valid một lần nữa, nó sẽ đọc true
7. A xóa cờ writing
8. B đặt cờ writing
9. B đọc một giá trị cũ của lá cờ hợp lệ (false) và đi vào khối if
10. B ghi trọng tải của nó
11. B viết true trên valid cờ
12. B xóa writing cờ

Tôi hy vọng điều này là không thể, nhưng khi nói đến thực sự trả lời câu hỏi "tại sao nó không phải là có thể?", Tôi không chắc chắn về câu trả lời. Đây là ý tưởng của tôi.

Trích dẫn từ tiêu chuẩn một lần nữa (29.3.12):

Atomic đọc-chỉnh sửa-ghi hoạt động sẽ luôn luôn đọc giá trị cuối cùng (theo thứ tự sửa đổi) bằng văn bản trước khi ghi liên quan đến đọc -modify-write operation.

atomic_flag::test_and_set() là hoạt động đọc-sửa đổi nguyên tử, như đã nêu trong 29.7.5.

Kể từ atomic_flag::test_and_set() luôn đọc một "giá trị mới", và tôi gọi nó với thứ tự bộ nhớ std::memory_order_acquire, sau đó tôi không thể đọc một giá trị cũ của valid cờ, bởi vì tôi phải xem tất cả các tác dụng phụ gây ra trước A trước cuộc gọi atomic_flag::clear() (sử dụng std::memory_order_release).

Tôi có đúng không?

Làm rõ. Toàn bộ lý do của tôi (sai hoặc chính xác) dựa trên 29.3.12. Đối với những gì tôi đã hiểu cho đến nay, nếu chúng tôi bỏ qua số atomic_flag, hãy đọc dữ liệu cũ từ valid có thể ngay cả khi đó là atomic. atomic dường như không có nghĩa là "luôn hiển thị ngay lập tức" cho mọi chuỗi. Bảo đảm tối đa bạn có thể yêu cầu là một thứ tự nhất quán trong các giá trị bạn đọc, nhưng bạn vẫn có thể đọc dữ liệu cũ trước khi nhận được dữ liệu mới. May mắn thay, atomic_flag::test_and_set() và mọi hoạt động exchange đều có tính năng quan trọng này: chúng luôn đọc dữ liệu mới. Vì vậy, chỉ khi bạn có được/phát hành trên cờ writing (không chỉ trên valid), thì bạn sẽ có được hành vi mong đợi. Bạn có thấy quan điểm của tôi (đúng hay không)?

---

EDIT: câu hỏi ban đầu của tôi bao gồm một vài dòng sau đó đã đạt được quá nhiều sự chú ý nếu so với lõi của câu hỏi. Tôi để chúng phù hợp với các câu trả lời đã được đưa ra, nhưng hãy bỏ qua chúng nếu bạn đang đọc câu hỏi ngay bây giờ.

Có bất kỳ điểm nào trong valid là một atomic<bool> và không phải là một đồng bằng bool? Hơn nữa, nếu nó phải là một atomic<bool>, hạn chế thứ tự bộ nhớ 'tối thiểu' của nó là gì sẽ không hiển thị vấn đề?

Answer 1

Bên trong else chi nhánh valid cần được bảo vệ bởi ngữ nghĩa Acquire/release áp đặt bởi các hoạt động trên waiting. Tuy nhiên, điều này không làm cho nhu cầu tạo valid một nguyên tử:

Bạn quên bao gồm dòng đầu tiên (if (e.valid)) trong phân tích của mình. Nếu valid là bool thay vì atomic<bool> quyền truy cập này sẽ hoàn toàn không được bảo vệ. Do đó, bạn có thể có tình huống khi thay đổi valid hiển thị với các chủ đề khác trước khi payload hoàn toàn được viết/hiển thị. Điều này có nghĩa là một chuỗi B có thể đánh giá e.valid đến true và nhập chi nhánh do something with e.payload trong khi payload chưa được viết hoàn toàn.

Khác sau đó phân tích của bạn có vẻ hơi hợp lý nhưng không hoàn toàn chính xác với tôi. Điều cần nhớ với thứ tự bộ nhớ là có được và phát hành ngữ nghĩa sẽ ghép nối.Tất cả mọi thứ được viết trước khi một hoạt động phát hành có thể được đọc một cách an toàn sau khi một hoạt động có được trên cùng một bản ghi có thể đọc giá trị được sửa đổi. Với ý nghĩ đó, ngữ nghĩa phát hành trên waiting.clear(...) đảm bảo rằng ghi vào valid phải được hiển thị khi vòng lặp trên writing.test_and_set(...) thoát, vì sau này đọc thay đổi chờ đợi (the write done in waiting.clear (...) `) với ngữ nghĩa có được và doesn ' t thoát trước khi thay đổi đó hiển thị.

Về §29.3.12: Nó có liên quan đến tính chính xác của mã của bạn, nhưng không liên quan đến việc đọc cờ valid cũ. Bạn không thể thiết lập cờ trước khi rõ ràng, vì vậy ngữ nghĩa phát hành sẽ đảm bảo tính chính xác ở đó. §29.3.12 bảo vệ bạn khỏi các tình huống sau:

1. Cả A và B vào ngành khác, bởi vì có hiệu lực là sai
2. Một bộ cờ viết
3. B thấy một giá trị cũ để viết và cũng đặt nó
4. Cả A và B đọc lá cờ hợp lệ (đó là sai), nhập nếu khối và viết payload tạo ra một tình trạng chủng tộc

Chỉnh sửa: Đối với các ràng buộc Ordering tối thiểu: có được cho tải và phát hành cho các cửa hàng nên có thể làm công việc, tuy nhiên tùy thuộc vào phần cứng mục tiêu của bạn, bạn cũng có thể ở lại với tính nhất quán tuần tự. Để biết sự khác biệt giữa các ngữ nghĩa đó, hãy xem here.

Answer 2

Nếu valid không phải là nguyên tử thì đọc ban đầu của e.valid trên dòng đầu tiên xung đột với việc gán cho e.valid.

Không có đảm bảo nào cả hai chủ đề đã đọc xong trước khi một trong số các chủ đề nhận được spinlock, tức là các bước 1 và 6 không được đặt hàng.

Answer 3

Phần 29.3.12 không liên quan gì đến lý do mã này chính xác hoặc không chính xác. Phần bạn muốn (trong the draft version of the standard available online) là Phần 1.10: "Hành động đa luồng và các cuộc đua dữ liệu". Phần 1.10 định nghĩa một mối quan hệ xảy ra trước đó về các phép toán nguyên tử và các hoạt động phi nguyên tử liên quan đến các hoạt động nguyên tử.

Mục 1.10 nói rằng nếu có hai hoạt động phi nguyên tử mà bạn không thể xác định mối quan hệ xảy ra trước đó thì bạn có một cuộc đua dữ liệu. Nó tiếp tục tuyên bố (Đoạn 21) rằng bất kỳ chương trình nào có cuộc đua dữ liệu đều có hành vi không xác định.

Nếu e.valid không phải là nguyên tử thì bạn có cuộc đua dữ liệu giữa dòng mã đầu tiên và dòng e.valid=true. Vì vậy, tất cả các lý do của bạn về hành vi trong mệnh đề else là không chính xác (chương trình không có hành vi được xác định để không có lý do gì.)

Mặt khác nếu tất cả các truy cập của bạn đến e.valid được bảo vệ bởi các hoạt động nguyên tử trên e.writing (như nếu mệnh đề else là toàn bộ chương trình của bạn) thì lý do của bạn sẽ chính xác. Sự kiện 9 trong danh sách của bạn không thể xảy ra. Nhưng lý do không phải là Mục 29.3.12, nó lại là Phần 1.10, mà nói rằng các hoạt động phi nguyên tử của bạn sẽ xuất hiện để được tuần tự phù hợp nếu không có dataraces.

Mẫu bạn đang sử dụng được gọi là double checked locking‌​. Trước C++ 11, không thể thực hiện khóa kiểm tra kép một cách hợp lý. Trong C++ 11, bạn có thể thực hiện việc kiểm tra khóa kép một cách chính xác và dễ dàng.Cách bạn thực hiện bằng cách tuyên bố valid là atomic.

Answer 4

Cửa hàng để e.valid cần phát hành và tải trong điều kiện cần phải có được. Nếu không, trình biên dịch/bộ xử lý được tự do đặt e.valid ở trên bằng cách viết tải trọng. Có một công cụ mã nguồn mở, CDSChecker, để xác minh mã như thế này đối với mô hình bộ nhớ C/C++ 11.