Mengapa kode yang mengubah variabel bersama di seluruh utas ternyata TIDAK mengalami kondisi balapan?

107

Saya menggunakan Cygwin GCC dan menjalankan kode ini:

#include <iostream>
#include <thread>
#include <vector>
using namespace std;

unsigned u = 0;

void foo()
{
    u++;
}

int main()
{
    vector<thread> threads;
    for(int i = 0; i < 1000; i++) {
        threads.push_back (thread (foo));
    }
    for (auto& t : threads) t.join();

    cout << u << endl;
    return 0;
}

Disusun dengan baris: g++ -Wall -fexceptions -g -std=c++14 -c main.cpp -o main.o.

Ini mencetak 1000, yang benar. Namun, saya mengharapkan jumlah yang lebih rendah karena utas menimpa nilai yang sebelumnya bertambah. Mengapa kode ini tidak saling akses?

Mesin uji saya memiliki 4 inti, dan saya tidak membatasi program yang saya ketahui.

Masalah tetap ada saat mengganti konten yang dibagikan foodengan sesuatu yang lebih kompleks, misalnya

if (u % 3 == 0) {
    u += 4;
} else {
    u -= 1;
}
mafu
sumber
66
CPU Intel memiliki beberapa logika "shoot down" internal yang luar biasa untuk menjaga kompatibilitas dengan CPU x86 paling awal yang digunakan dalam sistem SMP (seperti mesin Pentium Pro ganda). Banyak sekali kondisi kegagalan yang diajarkan kepada kita mungkin terjadi hampir tidak pernah benar-benar terjadi pada mesin x86. Jadi katakanlah sebuah inti pergi untuk menulis ukembali ke memori. CPU benar-benar akan melakukan hal-hal luar biasa seperti pemberitahuan bahwa garis memori untuk utidak ada di cache CPU dan itu akan memulai kembali operasi tambahan. Inilah sebabnya mengapa berpindah dari x86 ke arsitektur lain bisa menjadi pengalaman yang membuka mata!
David Schwartz
1
Mungkin masih terlalu cepat. Anda perlu menambahkan kode untuk memastikan bahwa utas menghasilkan sebelum melakukan apa pun untuk memastikan bahwa utas lain diluncurkan sebelum selesai.
Rob K
1
Seperti yang telah dicatat di tempat lain, kode utas sangat pendek sehingga mungkin dijalankan sebelum utas berikutnya mengantri. Bagaimana dengan 10 utas yang menempatkan u ++ dalam loop 100 hitungan. Dan penundaan singkat dalam waktu sebelum dimulainya loop (atau bendera "go" global untuk memulai semuanya pada waktu yang sama)
RufusVS
5
Sebenarnya, menjalankan program berulang kali dalam satu lingkaran pada akhirnya menunjukkan bahwa program tersebut rusak: sesuatu seperti while true; do res=$(./a.out); if [[ $res != 1000 ]]; then echo $res; break; fi; done;mencetak 999 atau 998 pada sistem saya.
Daniel Kamil Kozar

Jawaban:

266

foo()sangat pendek sehingga setiap utas mungkin selesai bahkan sebelum utas berikutnya muncul. Jika Anda menambahkan tidur untuk waktu acak foo()sebelum u++, Anda mungkin mulai melihat apa yang Anda harapkan.

Rob K
sumber
51
Ini memang mengubah keluaran dengan cara yang diharapkan.
mafu
49
Saya akan mencatat bahwa ini secara umum merupakan strategi yang cukup baik untuk menunjukkan kondisi balapan. Anda harus bisa memberikan jeda antara dua operasi; jika tidak, ada syarat balapan.
Matthieu M.
Kami baru saja mengalami masalah dengan C # ini. Biasanya kode hampir tidak pernah gagal, tetapi penambahan baru-baru ini dari panggilan API di antaranya menyebabkan penundaan yang cukup untuk membuatnya berubah secara konsisten.
Obsidian Phoenix
@Bayu_joo Bukankah Microsoft memiliki alat otomatis yang melakukan hal itu, sebagai metode untuk mendeteksi kondisi balapan dan membuatnya dapat direproduksi secara andal?
Mason Wheeler
1
@MasonWheeler: Saya bekerja hampir secara eksklusif di Linux, jadi ... tak tahu :(
Matthieu M.
59

Penting untuk dipahami bahwa kondisi balapan tidak menjamin kode akan berjalan dengan tidak benar, hanya dapat melakukan apa saja, karena ini adalah perilaku yang tidak ditentukan. Termasuk berjalan seperti yang diharapkan.

Khususnya pada mesin X86 dan AMD64, kondisi balapan dalam beberapa kasus jarang menyebabkan masalah karena banyak instruksi bersifat atom dan jaminan koherensi sangat tinggi. Jaminan ini agak berkurang pada sistem multi prosesor di mana awalan kunci diperlukan untuk banyak instruksi menjadi atom.

Jika peningkatan mesin Anda adalah operasi atomik, ini kemungkinan akan berjalan dengan benar meskipun menurut standar bahasa itu adalah Perilaku yang Tidak Ditentukan.

Secara khusus saya berharap dalam kasus ini kode dapat dikompilasi ke instruksi Ambil dan Tambahkan atom (ADD atau XADD dalam perakitan X86) yang memang atom dalam sistem prosesor tunggal, namun pada sistem multiprosesor ini tidak dijamin menjadi atom dan kunci akan diminta untuk membuatnya seperti itu. Jika Anda menjalankan sistem multiprosesor akan ada jendela di mana utas dapat mengganggu dan menghasilkan hasil yang salah.

Secara khusus saya menyusun kode Anda untuk perakitan menggunakan https://godbolt.org/ dan foo()mengkompilasi ke:

foo():
        add     DWORD PTR u[rip], 1
        ret

Ini berarti ia hanya melakukan instruksi penambahan yang untuk satu prosesor akan menjadi atom (meskipun seperti yang disebutkan di atas tidak demikian untuk sistem multi prosesor).

Vality
sumber
41
Penting untuk diingat bahwa "berjalan sesuai keinginan" adalah hasil yang diizinkan dari perilaku yang tidak ditentukan.
Markus
3
Seperti yang Anda tunjukkan, instruksi ini tidak atomic pada mesin SMP (yang semua sistem modern). Bahkan inc [u]tidak atom. The LOCKawalan diperlukan untuk membuat instruksi yang benar-benar atom. OP hanya beruntung. Ingatlah bahwa meskipun Anda memberi tahu CPU "tambahkan 1 ke kata di alamat ini", CPU masih harus mengambil, menambah, menyimpan nilai itu dan CPU lain dapat melakukan hal yang sama secara bersamaan, menyebabkan hasil menjadi salah.
Jonathon Reinhart
2
Saya tidak memilih, tetapi kemudian saya membaca kembali pertanyaan Anda dan menyadari bahwa pernyataan atomicity Anda mengasumsikan satu CPU. Jika Anda mengedit pertanyaan Anda untuk membuatnya lebih jelas (ketika Anda mengatakan "atomic", jelaskan bahwa ini hanya kasus pada satu CPU), maka saya akan dapat menghapus suara tidak suka saya.
Jonathon Reinhart
3
Diremehkan, saya menemukan klaim ini agak meh "Khususnya pada kondisi balapan mesin X86 dan AMD64 dalam beberapa kasus jarang menimbulkan masalah karena banyak instruksi yang bersifat atomik dan jaminan koherensi sangat tinggi." Paragraf harus mulai membuat asumsi eksplisit bahwa Anda berfokus pada inti tunggal. Meski begitu, arsitektur multi-core adalah standar de-facto saat ini di perangkat konsumen yang saya anggap sebagai kasus sudut untuk menjelaskan terakhir, daripada yang pertama.
Patrick Trentin
3
Oh pasti. x86 memiliki banyak kompatibilitas ke belakang ... hal-hal untuk memastikan bahwa kode yang salah ditulis bekerja sejauh mungkin. Itu adalah masalah yang sangat besar ketika Pentium Pro memperkenalkan eksekusi out-of-order. Intel ingin memastikan bahwa basis kode yang diinstal berfungsi tanpa perlu dikompilasi ulang secara khusus untuk chip baru mereka. x86 dimulai sebagai inti CISC, tetapi secara internal telah berkembang menjadi inti RISC, meskipun masih menyajikan dan berperilaku dalam banyak hal sebagai CISC dari perspektif programmer. Untuk lebih lanjut, lihat jawaban Peter Cordes di sini .
Cody Grey
20

Saya pikir tidak apa-apa jika Anda tidur sebelum atau sesudah u++. Ini bukan operasi yang u++diterjemahkan menjadi kode yang - dibandingkan dengan overhead utas pemijahan yang memanggil foo- dilakukan dengan sangat cepat sehingga tidak mungkin dicegat. Namun, jika Anda "memperpanjang" operasi u++, kondisi balapan akan menjadi lebih mungkin:

void foo()
{
    unsigned i = u;
    for (int s=0;s<10000;s++);
    u = i+1;
}

hasil: 694


BTW: Saya juga mencoba

if (u % 2) {
    u += 2;
} else {
    u -= 1;
}

dan itu memberi saya lebih banyak waktu 1997, tetapi terkadang 1995.

Stephan Lechner
sumber
1
Saya berharap pada kompiler yang samar-samar waras bahwa seluruh fungsi akan dioptimalkan untuk hal yang sama. Saya terkejut ternyata tidak. Terima kasih untuk hasil yang menarik.
Vality
Ini benar sekali. Ribuan instruksi perlu dijalankan sebelum utas berikutnya mulai menjalankan fungsi kecil yang dimaksud. Saat Anda membuat waktu eksekusi dalam fungsi lebih dekat ke overhead pembuatan thread, Anda akan melihat dampak kondisi balapan.
Jonathon Reinhart
@Vality: Saya juga mengharapkannya untuk menghapus for-loop palsu di bawah pengoptimalan O3. Tidak?
pengguna21820
Bagaimana bisa else u -= 1dieksekusi? Bahkan dalam lingkungan paralel, nilainya tidak boleh tidak cocok %2, bukan?
mafu
2
dari output, sepertinya else u -= 1dijalankan satu kali, pertama kali foo () dipanggil, ketika u == 0. Sisa 999 kali u ganjil dan u += 2dieksekusi menghasilkan u = -1 + 999 * 2 = 1997; yaitu keluaran yang benar. Kondisi balapan terkadang menyebabkan salah satu dari + = 2 ditimpa oleh utas paralel dan Anda mendapatkan 1995.
Luke
7

Itu memang menderita kondisi ras. Masukan usleep(1000);sebelum u++;di foodan saya melihat output yang berbeda (<1000) setiap kali.

juf
sumber
6
  1. Jawaban yang mungkin mengapa kondisi balapan tidak terwujud untuk Anda, meskipun memang ada, adalah foo()begitu cepat, dibandingkan dengan waktu yang diperlukan untuk memulai utas, sehingga setiap utas selesai bahkan sebelum utas berikutnya dapat dimulai. Tapi...

  2. Bahkan dengan versi asli Anda, hasilnya bervariasi berdasarkan sistem: Saya mencobanya dengan cara Anda pada Macbook (quad-core), dan dalam sepuluh kali proses, saya mendapatkan 1000 tiga kali, 999 enam kali, dan 998 kali. Jadi perlombaan agak jarang, tapi jelas ada.

  3. Anda mengompilasi dengan '-g', yang memiliki cara untuk menghilangkan bug. Saya mengkompilasi ulang kode Anda, masih tidak berubah tetapi tanpa '-g', dan balapan menjadi jauh lebih jelas: Saya mendapat 1000 sekali, 999 tiga kali, 998 dua kali, 997 dua kali, 996 sekali, dan 992 sekali.

  4. Kembali. saran untuk menambahkan tidur - itu membantu, tetapi (a) waktu tidur tetap membuat utas masih miring oleh waktu mulai (tergantung pada resolusi pengatur waktu), dan (b) tidur acak menyebarkannya ketika apa yang kita inginkan adalah tarik mereka lebih dekat. Sebagai gantinya, saya akan mengkodekan mereka untuk menunggu sinyal mulai, jadi saya bisa membuat semuanya sebelum membiarkan mereka mulai bekerja. Dengan versi ini (dengan atau tanpa '-g'), saya mendapatkan hasil di semua tempat, serendah 974, dan tidak lebih tinggi dari 998:

    #include <iostream>
    #include <thread>
    #include <vector>
    using namespace std;
    
    unsigned u = 0;
    bool start = false;
    
    void foo()
    {
        while (!start) {
            std::this_thread::yield();
        }
        u++;
    }
    
    int main()
    {
        vector<thread> threads;
        for(int i = 0; i < 1000; i++) {
            threads.push_back (thread (foo));
        }
        start = true;
        for (auto& t : threads) t.join();
    
        cout << u << endl;
        return 0;
    }
dgould
sumber
Hanya sebuah catatan. The -gbendera tidak dengan cara apapun "make bug menghilang." The -gbendera pada kedua GNU dan dentang compiler hanya menambahkan simbol debug untuk biner disusun. Ini memungkinkan Anda menjalankan alat diagnostik seperti GDB dan Memcheck pada program Anda dengan beberapa keluaran yang dapat dibaca manusia. Misalnya ketika Memcheck dijalankan di atas program dengan kebocoran memori, Memcheck tidak akan memberi tahu Anda nomor baris kecuali jika program tersebut dibuat menggunakan -gflag.
MS-DDOS
Memang, bug yang bersembunyi dari debugger biasanya lebih merupakan masalah pengoptimalan compiler; Aku harus mencoba, dan berkata, "menggunakan -O2 bukan dari -g". Namun demikian, jika Anda belum pernah merasakan kegembiraan dalam berburu bug yang hanya akan terwujud saat dikompilasi tanpa -g , anggaplah diri Anda beruntung. Itu bisa terjadi, dengan beberapa bug aliasing halus yang paling menjijikkan. Saya telah melihatnya, meskipun baru-baru ini, dan saya dapat percaya mungkin itu adalah kekhasan dari kompiler berpemilik lama, jadi saya akan mempercayai Anda, untuk sementara, tentang versi modern GNU dan Clang.
dilakukan
-gtidak menghentikan Anda untuk menggunakan pengoptimalan. misalnya gcc -O3 -gmembuat sama dengan asm gcc -O3, tetapi dengan metadata debug. gdb akan mengatakan "dioptimalkan" jika Anda mencoba mencetak beberapa variabel. -gmungkin dapat mengubah lokasi relatif dari beberapa hal dalam memori, jika salah satu hal yang ditambahkannya merupakan bagian dari .textbagian. Ini pasti membutuhkan ruang di file objek, tetapi saya pikir setelah menghubungkan semuanya berakhir di salah satu ujung segmen teks (bukan bagian), atau bukan bagian dari segmen sama sekali. Mungkin bisa mempengaruhi di mana hal-hal dipetakan untuk perpustakaan dinamis.
Peter Cordes