Saya ingin menulis kode portabel (Intel, ARM, PowerPC ...) yang memecahkan varian masalah klasik:
Initially: X=Y=0
Thread A:
X=1
if(!Y){ do something }
Thread B:
Y=1
if(!X){ do something }
di mana tujuannya adalah untuk menghindari situasi di mana kedua utas melakukansomething
. (Tidak apa-apa jika tidak ada yang berjalan; ini bukan mekanisme berjalan-tepat-sekali.) Harap perbaiki saya jika Anda melihat beberapa kekurangan dalam alasan saya di bawah ini.
Saya sadar, bahwa saya dapat mencapai tujuan dengan memory_order_seq_cst
atom store
dan load
s sebagai berikut:
std::atomic<int> x{0},y{0};
void thread_a(){
x.store(1);
if(!y.load()) foo();
}
void thread_b(){
y.store(1);
if(!x.load()) bar();
}
yang mencapai tujuan, karena harus ada beberapa urutan total tunggal pada
{x.store(1), y.store(1), y.load(), x.load()}
acara tersebut, yang harus setuju dengan urutan program "tepi":
x.store(1)
"di TO adalah sebelum"y.load()
y.store(1)
"di TO adalah sebelum"x.load()
dan jika foo()
dipanggil, maka kami memiliki tepi tambahan:
y.load()
"membaca nilai sebelumnya"y.store(1)
dan jika bar()
dipanggil, maka kami memiliki tepi tambahan:
x.load()
"membaca nilai sebelumnya"x.store(1)
dan semua tepi ini digabungkan bersama akan membentuk sebuah siklus:
x.store(1)
"in TO is before" y.load()
"read value before" y.store(1)
"in TO is before" x.load()
"read value before"x.store(true)
yang melanggar fakta bahwa pesanan tidak memiliki siklus.
Saya sengaja menggunakan istilah non-standar "di TO is before" dan "membaca value before" sebagai kebalikan dari istilah standar seperti happens-before
, karena saya ingin meminta umpan balik tentang kebenaran asumsi saya bahwa tepi ini memang menyiratkan happens-before
hubungan, dapat digabungkan bersama dalam satu grafik, dan siklus dalam grafik gabungan tersebut dilarang. Saya tidak yakin tentang hal itu. Yang saya tahu adalah kode ini menghasilkan hambatan yang benar pada Intel gcc & clang dan pada ARM gcc
Sekarang, masalah saya yang sebenarnya sedikit lebih rumit, karena saya tidak memiliki kendali atas "X" - itu tersembunyi di balik beberapa makro, templat dll dan mungkin lebih lemah daripada seq_cst
Saya bahkan tidak tahu apakah "X" adalah variabel tunggal, atau konsep lain (misalnya semaphore atau mutex yang ringan). Yang saya tahu adalah bahwa saya memiliki dua makro set()
dan check()
yang check()
mengembalikan true
"setelah" thread lain telah disebut set()
. (Hal ini juga diketahui bahwa set
dan check
adalah benang-aman dan tidak dapat membuat UB data ras.)
Jadi secara konseptual set()
agak seperti "X = 1" dan check()
seperti "X", tetapi saya tidak memiliki akses langsung ke atom yang terlibat, jika ada.
void thread_a(){
set();
if(!y.load()) foo();
}
void thread_b(){
y.store(1);
if(!check()) bar();
}
Saya khawatir, itu set()
mungkin diterapkan secara internal sebagai x.store(1,std::memory_order_release)
dan / atau check()
mungkin x.load(std::memory_order_acquire)
. Atau secara hipotetis std::mutex
bahwa satu utas membuka dan yang lain sedang masuk try_lock
; dalam standar ISO std::mutex
hanya dijamin memiliki memperoleh dan melepaskan pemesanan, bukan seq_cst.
Jika ini masalahnya, maka check()
jika tubuh dapat "dipesan ulang" sebelumnya y.store(true)
( Lihat jawaban Alex di mana mereka menunjukkan bahwa ini terjadi pada PowerPC ).
Ini akan sangat buruk, karena sekarang urutan kejadian ini dimungkinkan:
thread_b()
pertama memuat nilai lamax
(0
)thread_a()
mengeksekusi semuanya termasukfoo()
thread_b()
mengeksekusi semuanya termasukbar()
Jadi, keduanya foo()
dan bar()
dipanggil, yang harus saya hindari. Apa pilihan saya untuk mencegah itu?
Opsi A
Cobalah untuk memaksa penghalang Store-Load. Ini, dalam praktiknya, dapat dicapai dengan std::atomic_thread_fence(std::memory_order_seq_cst);
- seperti yang dijelaskan oleh Alex dalam jawaban berbeda semua kompiler yang diuji memancarkan pagar penuh:
- x86_64: MFENCE
- PowerPC: hwsync
- Itanuim: mf
- ARMv7 / ARMv8: dmb ish
- MIPS64: sinkronisasi
Masalah dengan pendekatan ini adalah, bahwa saya tidak dapat menemukan jaminan dalam aturan C ++, yang std::atomic_thread_fence(std::memory_order_seq_cst)
harus diterjemahkan ke penghalang memori penuh. Sebenarnya, konsep atomic_thread_fence
s dalam C ++ tampaknya berada pada tingkat abstraksi yang berbeda dari konsep perakitan hambatan memori dan lebih banyak berurusan dengan hal-hal seperti "operasi atom apa yang disinkronkan dengan apa". Apakah ada bukti teoritis bahwa implementasi di bawah ini mencapai tujuan?
void thread_a(){
set();
std::atomic_thread_fence(std::memory_order_seq_cst)
if(!y.load()) foo();
}
void thread_b(){
y.store(true);
std::atomic_thread_fence(std::memory_order_seq_cst)
if(!check()) bar();
}
Opsi B
Gunakan kontrol yang kami miliki atas Y untuk mencapai sinkronisasi, dengan menggunakan operasi memory_order_ac__rel baca-modifikasi-tulis pada Y:
void thread_a(){
set();
if(!y.fetch_add(0,std::memory_order_acq_rel)) foo();
}
void thread_b(){
y.exchange(1,std::memory_order_acq_rel);
if(!check()) bar();
}
Idenya di sini adalah bahwa akses ke satu atom ( y
) harus berupa urutan tunggal yang disetujui semua pengamat, jadi fetch_add
sebelum exchange
atau sebaliknya.
Jika fetch_add
sebelum exchange
maka bagian "release" fetch_add
disinkronkan dengan bagian "memperoleh" exchange
dan dengan demikian semua efek samping set()
harus terlihat oleh pelaksana kode check()
, jadi bar()
tidak akan dipanggil.
Kalau tidak, exchange
adalah sebelumnya fetch_add
, maka fetch_add
akan melihat 1
dan tidak menelepon foo()
. Jadi, tidak mungkin untuk memanggil keduanya foo()
dan bar()
. Apakah alasan ini benar?
Opsi C
Gunakan atom dummy, untuk memperkenalkan "ujung" yang mencegah bencana. Pertimbangkan pendekatan berikut:
void thread_a(){
std::atomic<int> dummy1{};
set();
dummy1.store(13);
if(!y.load()) foo();
}
void thread_b(){
std::atomic<int> dummy2{};
y.store(1);
dummy2.load();
if(!check()) bar();
}
Jika Anda pikir masalahnya di sini adalah masalah atomic
lokal, maka bayangkan memindahkannya ke ruang lingkup global, dengan alasan berikut tampaknya tidak menjadi masalah bagi saya, dan saya sengaja menulis kode sedemikian rupa untuk mengekspos betapa lucunya bahwa itu dummy1 dan dummy2 benar-benar terpisah.
Mengapa ini bisa berhasil? Nah, harus ada beberapa urutan total tunggal {dummy1.store(13), y.load(), y.store(1), dummy2.load()}
yang harus konsisten dengan urutan program "tepi":
dummy1.store(13)
"di TO adalah sebelum"y.load()
y.store(1)
"di TO adalah sebelum"dummy2.load()
(Toko seq_cst + load mudah-mudahan membentuk C ++ yang setara dengan penghalang memori penuh termasuk StoreLoad, seperti yang mereka lakukan dalam asm pada ISA nyata termasuk bahkan AArch64 di mana tidak diperlukan instruksi penghalang terpisah.)
Sekarang, kami memiliki dua kasus untuk dipertimbangkan: y.store(1)
sebelum y.load()
atau sesudah dalam urutan total.
Jika y.store(1)
sebelum y.load()
maka foo()
tidak akan dipanggil dan kita aman.
Jika y.load()
sebelumnya y.store(1)
, lalu menggabungkannya dengan dua sisi yang sudah kita miliki dalam urutan program, kami menyimpulkan bahwa:
dummy1.store(13)
"di TO adalah sebelum"dummy2.load()
Sekarang, dummy1.store(13)
ini adalah operasi rilis, yang melepaskan efek dari set()
, dan dummy2.load()
merupakan operasi perolehan, jadi check()
harus melihat efek dari set()
dan dengan demikian bar()
tidak akan dipanggil dan kami aman.
Apakah benar di sini berpikir bahwa check()
akan melihat hasil set()
? Bisakah saya menggabungkan "edge" dari berbagai jenis ("order program" alias Sequencing Before, "total order", "before release", "after memperoleh") seperti itu? Saya memiliki keraguan serius tentang hal ini: Aturan C ++ sepertinya berbicara tentang hubungan "sinkronisasi-dengan" antara toko dan memuat di lokasi yang sama - di sini tidak ada situasi seperti itu.
Perhatikan bahwa kita hanya khawatir tentang kasus di mana dumm1.store
ini dikenal (melalui penalaran lainnya) untuk menjadi sebelum dummy2.load
di urutan seq_cst keseluruhan. Jadi jika mereka mengakses variabel yang sama, beban akan melihat nilai yang disimpan dan disinkronkan dengannya.
(Alasan memory-barrier / reordering untuk implementasi di mana muatan atom dan toko mengkompilasi setidaknya untuk hambatan memori 1 arah (dan operasi seq_cst tidak dapat dipesan ulang: mis. Toko seq_cst tidak dapat melewati beban seq_cst) adalah bahwa ada beban / toko setelah dummy2.load
pasti menjadi terlihat oleh utas lainnya setelah itu y.store
. Dan juga untuk utas lainnya, ... sebelumnya y.load
.)
Anda dapat bermain dengan implementasi Opsi A, B, C saya di https://godbolt.org/z/u3dTa8
std::atomic_thread_fence(std::memory_order_seq_cst)
kompilasi ke penghalang penuh, tetapi karena seluruh konsep adalah detail implementasi Anda tidak akan menemukan disebutkan dalam standar. (Model memori CPU biasanya yang didefinisikan dalam hal apa reorerings diperbolehkan relatif terhadap konsistensi berurutan misalnya x86 adalah seq-cst + toko penyangga w / forwarding.)foo()
danbar()
dari keduanya dipanggil.compare_exchange_*
untuk melakukan operasi RMW pada bool atom tanpa mengubah nilainya (cukup tetapkan yang diharapkan dan baru dengan nilai yang sama).atomic<bool>
memilikiexchange
dancompare_exchange_weak
. Yang terakhir dapat digunakan untuk melakukan dummy RMW dengan (berusaha) CAS (benar, benar) atau salah, salah. Gagal atau secara atomik menggantikan nilainya dengan dirinya sendiri. (Dalam x86-64 asm, tipuan dengan itulock cmpxchg16b
adalah bagaimana Anda melakukan pemuatan atom 16-byte yang dijamin; tidak efisien tetapi tidak seburuk mengambil kunci yang terpisah.)foo()
ataubar()
akan dipanggil. Saya tidak ingin membawa banyak elemen "dunia nyata" kode, untuk menghindari "Anda pikir Anda memiliki masalah X tetapi Anda memiliki masalah seperti Y" jenis tanggapan. Tapi, jika seseorang benar-benar perlu tahu apa latar belakang lantai:set()
benar-benarsome_mutex_exit()
,check()
adalahtry_enter_some_mutex()
,y
adalah "ada beberapa pelayan",foo()
adalah "keluar tanpa membangunkan siapa pun",bar()
adalah "menunggu wakup" ... Tapi, saya menolak untuk bahas desain ini di sini - saya tidak bisa mengubahnya dengan benar.Jawaban:
Opsi A dan B adalah solusi yang valid.
Namun, Opsi C tidak valid! Hubungan sinkronisasi dengan hanya dapat dibangun dengan memperoleh / melepaskan operasi pada objek yang sama . Dalam kasus Anda, Anda memiliki dua objek yang sepenuhnya berbeda dan independen
dummy1
dandummy2
. Tetapi ini tidak dapat digunakan untuk membangun hubungan yang terjadi sebelum. Bahkan, karena variabel atom adalah murni lokal (yaitu, mereka hanya pernah disentuh oleh satu utas), kompiler bebas untuk menghapusnya berdasarkan aturan as-if .Memperbarui
Opsi A:
Saya berasumsi
set()
dancheck()
beroperasi pada beberapa nilai atom. Maka kita memiliki situasi berikut (-> menunjukkan sequencing-before ):set()
->fence1(seq_cst)
->y.load()
y.store(true)
->fence2(seq_cst)
->check()
Jadi kita bisa menerapkan aturan berikut:
Yaitu, baik
check()
melihat nilai yang disimpan dalamset
, atauy.load()
melihat nilai tertulis menjadiy.store()
(operasiy
bahkan dapat digunakanmemory_order_relaxed
).Opsi C:
The C ++ 17 standar negara [32.4.3, p1347]:
Kata penting di sini adalah "konsisten". Ini menyiratkan bahwa jika operasi A terjadi-sebelum operasi B , maka A harus mendahului B di S . Namun, implikasi logis adalah satu arah jalan, sehingga kita tidak bisa mengambil kesimpulan terbalik: hanya karena beberapa operasi C mendahului operasi D di S tidak berarti bahwa C terjadi sebelum D .
Secara khusus, dua operasi seq-cst pada dua objek yang terpisah tidak dapat digunakan untuk membangun yang terjadi sebelum hubungan, meskipun operasi benar-benar dipesan dalam S. Jika Anda ingin memesan operasi pada objek yang terpisah, Anda harus merujuk ke seq-cst -pagar (lihat Opsi A).
sumber
y.load()
tidak melihat efeky.store(1)
, maka kita dapat membuktikan dari aturan bahwa di S,atomic_thread_fence
dari thread_a adalah sebelumatomic_thread_fence
dari thread_b. Yang tidak saya lihat adalah bagaimana mendapatkan dari kesimpulan ini bahwaset()
efek samping dapat dilihatcheck()
.set
dancheck
dapat dijalankan dengan aman secara paralel, saya mungkin akan pergi dengan Opsi A, terutama jika ini adalah kinerja yang kritis, karena ia menghindari pertengkaran pada variabel bersamay
.Dalam contoh pertama,
y.load()
membaca 0 tidak berarti ituy.load()
terjadi sebelumnyay.store(1)
.Namun itu menyiratkan bahwa itu lebih awal dalam urutan total tunggal berkat aturan bahwa beban seq_cst mengembalikan nilai toko seq_cst terakhir dalam urutan total, atau nilai beberapa toko non-seq_cst yang tidak terjadi sebelumnya itu (yang dalam hal ini tidak ada). Jadi jika
y.store(1)
lebih awal dariy.load()
pada total order,y.load()
akan dikembalikan 1.Buktinya masih benar karena total pesanan tunggal tidak memiliki siklus.
Bagaimana dengan solusi ini?
sumber
if(false) foo();
saya pikir OP juga tidak mau itu: P Poin yang menarik tapi saya pikir OP memang menginginkan panggilan bersyarat didasarkan pada kondisi yang mereka tentukan!check()
(lihat komentar saya untuk pertanyaan saya untuk makna dunia nyataset,check,foo,bar
). Saya pikir itu bisa bekerja dengan baikif(!x2.load()){ if(check())x2.store(0); else bar(); }
sebagai gantinya.@mpoeter menjelaskan mengapa Opsi A dan B aman.
Dalam praktik implementasi nyata, saya pikir Opsi A hanya perlu
std::atomic_thread_fence(std::memory_order_seq_cst)
di Thread A, bukan B.toko seq-cst dalam prakteknya termasuk penghalang memori penuh, atau pada AArch64 setidaknya tidak dapat memesan ulang dengan kemudian memperoleh atau seq_cst memuat (
stlr
rilis berurutan harus mengalir dari buffer toko sebelumldar
dapat membaca dari cache).C ++ -> pemetaan asm memiliki pilihan untuk meletakkan biaya pengeringan buffer toko di toko atom atau muatan atom. Pilihan yang waras untuk implementasi nyata adalah membuat muatan atom menjadi murah, jadi toko seq_cst menyertakan penghalang penuh (termasuk StoreLoad). Sementara seq_cst memuat sama dengan mendapatkan banyak muatan pada sebagian besar.
(Tapi bukan KEKUATAN; bahkan ada beban yang membutuhkan sinkronisasi berat-berat = penghalang penuh untuk menghentikan store-forwarding dari utas SMT lainnya pada inti yang sama yang dapat menyebabkan pengurutan ulang IRIW, karena seq_cst mengharuskan semua utas untuk dapat menyetujui urutan pesanan). semua op seq_cst. Akankah dua atom menulis ke lokasi berbeda di utas berbeda selalu dilihat dalam urutan yang sama oleh utas lain? )
(Tentu saja untuk jaminan formal keselamatan, kita memang membutuhkan pagar di keduanya untuk mempromosikan memperoleh / melepaskan set () -> check () ke seq_cst disinkronkan-dengan. Juga akan bekerja untuk set yang santai, saya pikir, tetapi cek santai bisa memesan ulang dengan bar dari POV utas lainnya.)
Saya pikir masalah sebenarnya dengan Opsi C adalah bahwa itu tergantung pada beberapa pengamat hipotetis yang bisa menyinkronkan-dengan
y
dan operasi boneka. Dan dengan demikian kami mengharapkan kompiler untuk melestarikan pemesanan ketika membuat AS untuk ISA berbasis penghalang.Ini akan berlaku dalam praktik pada ISA nyata; kedua utas termasuk penghalang penuh atau setara dan kompiler tidak (belum) mengoptimalkan atom. Tapi tentu saja "kompilasi ke ISA berbasis penghalang" bukan bagian dari standar ISO C ++. Cache bersama yang koheren adalah pengamat hipotetis yang ada untuk alasan asm tetapi tidak untuk alasan ISO C ++.
Agar Opsi C berfungsi, kita perlu pemesanan seperti
dummy1.store(13);
/y.load()
/set();
(seperti yang dilihat oleh Thread B) untuk melanggar beberapa aturan ISO C ++ .Utas yang menjalankan pernyataan ini harus berperilaku seolah-olah
set()
dieksekusi terlebih dahulu (karena Diurutkan Sebelumnya). Tidak apa-apa, pemesanan memori runtime dan / atau kompilasi pemesanan ulang waktu operasi masih bisa melakukan itu.Dua operasi seq_cst
d1=13
dany
konsisten dengan Sequencing Before (urutan program).set()
tidak berpartisipasi dalam tatanan global seq_cst yang diperlukan untuk ada karena itu bukan seq_cst.Utas B tidak disinkronkan-dengan dummy1.store sehingga tidak ada persyaratan sebelum terjadi pada yang
set
relatifd1=13
berlaku , meskipun penugasan itu adalah operasi pelepasan.Saya tidak melihat kemungkinan pelanggaran aturan lainnya; Saya tidak dapat menemukan apa pun di sini yang harus konsisten dengan
set
Sequencing-Befored1=13
.Alasan "dummy1.store rilis set ()" adalah cacatnya. Pemesanan itu hanya berlaku untuk pengamat nyata yang menyinkronkan-dengannya, atau dalam asm. Ketika @mpoeter menjawab, keberadaan total order seq_cst tidak membuat atau menyiratkan hubungan sebelum-hubungan, dan itulah satu-satunya hal yang secara formal menjamin pemesanan di luar seq_cst.
Setiap jenis "normal" CPU dengan cache bersama yang koheren di mana penataan ulang ini dapat benar-benar terjadi saat runtime tampaknya tidak masuk akal. (Tetapi jika kompiler dapat menghapus
dummy1
dandummy2
kemudian jelas kita akan memiliki masalah, dan saya pikir itu diperbolehkan oleh standar.)Tetapi karena model memori C ++ tidak didefinisikan dalam hal buffer toko, cache koheren bersama, atau tes lakmus dari pemesanan ulang yang diizinkan, hal-hal yang diperlukan oleh kewarasan tidak secara formal diperlukan oleh aturan C ++. Ini mungkin disengaja untuk memungkinkan pengoptimalan bahkan variabel seq_cst yang berubah menjadi utas pribadi. (Kompiler saat ini tidak melakukan itu, tentu saja, atau optimasi objek atom lainnya.)
Sebuah implementasi di mana satu utas benar-benar bisa melihat yang
set()
terakhir sementara yang lain bisa melihatset()
suara pertama tidak masuk akal. Bahkan KEKUATAN tidak bisa melakukan itu; baik seq_cst memuat dan menyimpan termasuk hambatan penuh untuk KEKUATAN. (Saya telah menyarankan dalam komentar bahwa pengorganisasian ulang IRIW mungkin relevan di sini; aturan acq / rel C ++ cukup lemah untuk mengakomodasi hal itu, tetapi total kurangnya jaminan di luar sinkronisasi - dengan atau yang terjadi - sebelum situasi jauh lebih lemah daripada HW. )C ++ tidak menjamin apa pun untuk non-seq_cst kecuali benar - benar ada pengamat, dan hanya untuk pengamat itu. Tanpa kita berada di wilayah kucing Schroedinger. Atau, jika dua pohon tumbang di hutan, apakah satu pohon tumbang sebelum yang lain? (Jika itu adalah hutan besar, relativitas umum mengatakan itu tergantung pada pengamat dan tidak ada konsep simultan yang universal.)
@mpoeter menyarankan kompiler bahkan dapat menghapus beban dummy dan menyimpan operasi, bahkan pada objek seq_cst.
Saya pikir itu mungkin benar ketika mereka dapat membuktikan bahwa tidak ada yang dapat disinkronkan dengan operasi. misalnya kompiler yang dapat melihat yang
dummy2
tidak luput dari fungsi mungkin dapat menghapus beban seq_cst itu.Ini memiliki setidaknya satu konsekuensi dunia nyata: jika mengkompilasi untuk AArch64, itu akan memungkinkan seq_cst store sebelumnya untuk menyusun ulang dalam praktek dengan operasi yang lebih santai, yang tidak akan mungkin terjadi dengan seq_cst store + beban yang menguras buffer toko sebelum ada nanti banyak yang bisa dieksekusi.
Tentu saja kompiler saat ini tidak mengoptimalkan atom sama sekali, meskipun ISO C ++ tidak melarangnya; itu masalah yang belum terpecahkan untuk komite standar.
Ini diperbolehkan saya pikir karena model memori C ++ tidak memiliki pengamat implisit atau persyaratan bahwa semua thread setuju pada pemesanan. Itu memang memberikan beberapa jaminan berdasarkan cache yang koheren, tetapi tidak memerlukan visibilitas untuk semua utas secara simultan.
sumber
set()
, jadi saya masih akan menggunakan pagar di thread B juga. Saya kira toko santai dengan pagar seq-cst akan menghasilkan kode yang hampir sama dengan toko seq-cst.sync
sebelum toko, tidak ada setelah. godbolt.org/z/mAr72P Tapi beban seq-cst membutuhkan beberapa hambatan di kedua sisi.Tetapi tidak ada yang dijamin memiliki "pemesanan seq_cst", karena
seq_cst
bukan properti dari operasi apa pun.seq_cst
adalah jaminan atas semua operasi implementasi yang diberikanstd::atomic
atau kelas atom alternatif. Dengan demikian, pertanyaan Anda tidak sehat.sumber