Apa artinya "sangat terjadi sebelum"?

9

Ungkapan "sangat terjadi sebelum" digunakan beberapa kali dalam standar konsep C ++.

Misalnya: Pengakhiran [basic.start.term] / 5

Jika penyelesaian inisialisasi objek dengan durasi penyimpanan statis sangat terjadi sebelum panggilan ke std :: atexit (lihat, [support.start.term]), panggilan ke fungsi diteruskan ke std :: atexit diurutkan sebelum panggilan ke destruktor untuk objek. Jika panggilan ke std :: atexit sangat terjadi sebelum penyelesaian inisialisasi objek dengan durasi penyimpanan statis, panggilan ke destruktor untuk objek tersebut diurutkan sebelum panggilan ke fungsi diteruskan ke std :: atexit . Jika panggilan ke std :: atexit sangat terjadi sebelum panggilan lain ke std :: atexit, panggilan ke fungsi diteruskan ke panggilan std :: atexit kedua diurutkan sebelum panggilan ke fungsi dialihkan ke std pertama :: panggilan atexit.

Dan didefinisikan dalam Data races [intro.races] / 12

Evaluasi A sangat terjadi sebelum evaluasi D jika, baik

(12.1) A diurutkan sebelum D, atau

(12.2) A menyinkronkan dengan D, dan baik A maupun D adalah operasi atom yang konsisten secara berurutan ([urutan atom]), atau

(12.3) ada evaluasi B dan C sehingga A diurutkan sebelum B, B hanya terjadi sebelum C, dan C diurutkan sebelum D, atau

(12.4) ada evaluasi B sehingga A sangat terjadi sebelum B, dan B sangat terjadi sebelum D.

[Catatan: Secara informal, jika A sangat terjadi sebelum B, maka A tampaknya dievaluasi sebelum B dalam semua konteks. Sangat terjadi sebelum mengecualikan operasi konsumsi. - catatan akhir]

Mengapa "sangat terjadi sebelum" diperkenalkan? Secara intuitif, apa perbedaan dan hubungannya dengan "terjadi sebelumnya"?

Apa arti "A tampaknya dievaluasi sebelum B dalam semua konteks" dalam catatan?

(Catatan: motivasi untuk pertanyaan ini adalah komentar Peter Cordes di bawah jawaban ini .)

Tambahan kutipan standar draft (terima kasih kepada Peter Cordes)

Ketertiban dan konsistensi [atomics.order] / 4

Ada urutan total tunggal S pada semua operasi memory_order :: seq_cst, termasuk pagar, yang memenuhi batasan berikut. Pertama, jika A dan B adalah operasi memory_order :: seq_cst dan A sangat terjadi sebelum B, maka A mendahului B dalam S. Kedua, untuk setiap pasangan operasi atom A dan B pada objek M, di mana A diperintahkan koherensi sebelum B, empat kondisi berikut ini harus dipenuhi oleh S:

(4.1) jika A dan B keduanya operasi memory_order :: seq_cst, maka A mendahului B dalam S; dan

(4.2) jika A adalah operasi memory_order :: seq_cst dan B terjadi sebelum memory_order :: seq_cst pagar Y, maka A mendahului Y di S; dan

(4.3) jika memory_order :: seq_cst pagar X terjadi sebelum A dan B adalah memory_order :: seq_cst operasi, maka X mendahului B dalam S; dan

(4.4) jika memory_order :: seq_cst pagar X terjadi sebelum A dan B terjadi sebelum memory_order :: seq_cst pagar Y, maka X mendahului Y di S.

curiousguy
sumber
1
Draf standar saat ini juga merujuk "A sangat terjadi sebelum B" sebagai syarat untuk aturan yang berlaku seq_cst, dalam Atom 31.4 Urutan dan konsistensi: 4 . Itu tidak dalam standar C ++ 17 n4659 , di mana 32,4 - 3 mendefinisikan keberadaan satu urutan total operasi seq_cst yang konsisten dengan pesanan "terjadi sebelumnya" dan pesanan modifikasi untuk semua lokasi yang terpengaruh ; "sangat" ditambahkan dalam konsep kemudian.
Peter Cordes
2
@PeterCordes Saya pikir komentar mengecualikan konsumsi, menyatakan itu HB "dalam semua konteks" / "kuat" dan berbicara tentang panggilan ke fungsi pointer adalah sesuatu dari hadiah mati. Jika sebuah program multithreaded memanggil atexit()satu utas dan exit()lainnya, itu tidak cukup bagi inisialisasi untuk hanya membawa ketergantungan berbasis konsumsi hanya karena hasilnya kemudian berbeda dari jika exit()dipanggil oleh utas yang sama. Jawaban saya yang lebih tua menyangkut perbedaan ini.
Iwillnotexist Idonotexist
@IwillnotexistIdonotexist Bisakah Anda keluar dari program MT? Apakah itu pada dasarnya bukan ide yang rusak?
curiousguy
1
@curiousguy Itulah tujuannya exit(). Setiap utas dapat mematikan seluruh program dengan keluar, atau utas utama dapat keluar dengan return-ing. Ini menghasilkan panggilan atexit()penangan dan kematian semua utas apa pun yang mereka lakukan.
Iwillnotexist Idonotexist

Jawaban:

5

Mengapa "sangat terjadi sebelum" diperkenalkan? Secara intuitif, apa perbedaan dan hubungannya dengan "terjadi sebelumnya"?

Persiapkan diri Anda untuk "terjadi begitu saja sebelum" juga! Lihatlah snapshot cppref saat ini https://en.cppreference.com/w/cpp/atomic/memory_order

masukkan deskripsi gambar di sini

Tampaknya "cukup terjadi sebelum" ditambahkan dalam C ++ 20.

Cukup terjadi sebelumnya

Terlepas dari utas, evaluasi A hanya terjadi sebelum evaluasi B jika salah satu dari yang berikut ini benar:

1) A diurutkan-sebelum B

2) A menyinkronkan-dengan B

3) A terjadi - sebelum X, dan X terjadi - sebelum B

Catatan: tanpa mengkonsumsi operasi, hanya terjadi-sebelum dan terjadi-sebelum hubungan sama.

Jadi Simply-HB dan HB adalah sama kecuali untuk bagaimana mereka menangani operasi konsumsi. Lihat HB

Terjadi-sebelumnya

Terlepas dari utas, evaluasi A terjadi sebelum evaluasi B jika salah satu dari yang berikut ini benar:

1) A diurutkan-sebelum B

2) Inter-thread terjadi sebelum B

Implementasi diperlukan untuk memastikan bahwa hubungan yang terjadi sebelum hubungan asiklik, dengan memperkenalkan sinkronisasi tambahan jika perlu (hanya dapat diperlukan jika operasi konsumsi terlibat, lihat Batty et al)

Bagaimana mereka berbeda dalam hal mengkonsumsi? Lihat Inter-Thread-HB

Inter-thread terjadi sebelumnya

Di antara utas, evaluasi Antar-utas terjadi sebelum evaluasi B jika salah satu dari yang berikut ini benar

1) A disinkronkan-dengan B

2) A adalah perintah yang dipesan sebelum B

3) ...

...

Operasi yang dipesan ketergantungan (yaitu menggunakan rilis / konsumsi) adalah HB tetapi tidak harus Cukup-HB.

Mengkonsumsi lebih santai daripada memperoleh, jadi jika saya mengerti dengan benar, HB lebih santai dari pada sekadar-HB.

Sangat terjadi sebelumnya

Terlepas dari utas, evaluasi A sangat terjadi sebelum evaluasi B jika ada dari yang berikut ini benar:

1) A diurutkan-sebelum B

2) A menyinkronkan dengan B, dan baik A maupun B adalah operasi atom yang konsisten secara berurutan

3) A diurutkan-sebelum X, X hanya terjadi-sebelum Y, dan Y diurutkan-sebelum B

4) A sangat terjadi-sebelum X, dan X sangat terjadi-sebelum B

Catatan: secara informal, jika A sangat terjadi-sebelum B, maka A tampaknya dievaluasi sebelum B dalam semua konteks.

Catatan: sangat terjadi-sebelum mengecualikan operasi konsumsi.

Jadi operasi rilis / konsumsi tidak boleh Sangat-HB.

Rilis / akuisisi dapat berupa HB dan Cukup-HB (karena rilis / perolehan disinkronkan dengan) tetapi tidak harus Sangat-HB. Karena Strongly-HB secara khusus mengatakan bahwa A harus disinkronkan-dengan B DAN menjadi operasi Konsisten Berurutan.

                            Is happens-before guaranteed?

                        HB             Simply-HB          Strongly-HB

relaxed                 no                 no                 no
release/consume        yes                 no                 no      
release/acquire        yes                yes                 no
S.C.                   yes                yes                yes

Apa arti "A tampaknya dievaluasi sebelum B dalam semua konteks" dalam catatan?

Semua konteks: Semua utas / semua CPU melihat (atau "pada akhirnya akan menyetujui") urutan yang sama. Ini adalah jaminan konsistensi berurutan - urutan modifikasi total global semua variabel. Rantai perolehan / rilis hanya menjamin urutan modifikasi yang dirasakan untuk utas yang berpartisipasi dalam rantai. Utas di luar rantai secara teori diizinkan untuk melihat urutan yang berbeda.

Saya tidak tahu mengapa Strongly-HB dan Simply-HB diperkenalkan. Mungkin untuk membantu memperjelas cara beroperasi di sekitar konsumsi? Sangat-HB memiliki sifat yang bagus - jika satu thread mengamati A kuat-terjadi-sebelum B, ia tahu semua utas akan mengamati hal yang sama.

Sejarah mengkonsumsi:

Paul E. McKenney bertanggung jawab untuk mengkonsumsi dalam standar C dan C ++. Mengkonsumsi menjamin pemesanan antara penugasan pointer dan memori yang ditunjuknya. Itu diciptakan karena DEC Alpha. DEC Alpha secara spekulatif dapat melakukan dereferensi pointer, sehingga ia juga memiliki pagar memori untuk mencegah hal ini. DEC Alpha tidak lagi dibuat dan saat ini tidak ada prosesor yang memiliki perilaku ini. Konsumsi dimaksudkan untuk menjadi sangat santai.

Humphrey Winnebago
sumber
1
Menyedihkan. Saya hampir menyesal mengajukan pertanyaan itu. Saya ingin kembali menangani masalah C ++ yang mudah seperti aturan pembatalan iterator, pencarian nama bergantung argumen, operator konversi yang ditentukan pengguna templat, pengurangan argumen templat, ketika pencarian nama terlihat di kelas dasar di anggota templat, dan ketika Anda dapat dikonversi ke basis virtual di awal konstruksi suatu objek.
curiousguy
Re: konsumsi. Apakah Anda mengklaim bahwa nasib mengkonsumsi pesanan terkait dengan nasib DEC Alpha dan tidak memiliki nilai di luar lengkungan tertentu?
curiousguy
1
Itu pertanyaan yang bagus. Melihat lebih dalam sekarang, sepertinya mengkonsumsi secara teoritis dapat memberikan peningkatan kinerja untuk lengkungan yang dipesan dengan lambat seperti ARM dan PowerPC. Beri aku waktu lagi untuk memeriksanya.
Humphrey Winnebago
1
Saya akan mengatakan mengkonsumsi ada karena semua ISA dipesan dengan lemah selain Alpha. Dalam Alpha asm, satu-satunya pilihan adalah santai dan memperoleh (dan seq-cst), bukan pemesanan ketergantungan. mo_consumedimaksudkan untuk mengambil keuntungan dari urutan ketergantungan data pada CPU nyata, dan memformalkan bahwa kompiler tidak dapat memecah ketergantungan data melalui prediksi cabang. misalnya int *p = load(); tmp = *p;bisa rusak oleh kompilator memperkenalkan if(p==known_address) tmp = *known_address; else tmp=*p;jika itu memiliki beberapa alasan untuk mengharapkan nilai pointer tertentu menjadi umum. Itu legal untuk santai tetapi tidak mengkonsumsinya.
Peter Cordes
@PeterCordes benar ... lengkungan dengan urutan lemah harus memancarkan penghalang memori untuk memperoleh, tetapi (secara teoritis) tidak untuk dikonsumsi. Sepertinya Anda berpikir bahwa jika Alpha tidak pernah ada kita masih akan mengkonsumsi? Juga, Anda pada dasarnya mengatakan bahwa mengkonsumsi adalah penghalang kompiler yang mewah (atau "standar").
Humphrey Winnebago