Mengapa pthread_cond_wait memiliki wakeups palsu?

145

Mengutip halaman manual:

Saat menggunakan variabel kondisi selalu ada predikat Boolean yang melibatkan variabel bersama yang terkait dengan setiap kondisi, tunggu itu benar jika utas harus dilanjutkan. Wakeups palsu dari fungsi pthread_cond_timedwait () atau pthread_cond_wait () dapat terjadi. Karena pengembalian dari pthread_cond_timedwait () atau pthread_cond_wait () tidak menyiratkan apa-apa tentang nilai predikat ini, predikat harus dievaluasi kembali setelah pengembalian tersebut.

Jadi, pthread_cond_waitdapat kembali bahkan jika Anda belum mengisinya. Setidaknya pada pandangan pertama, itu tampak sangat mengerikan. Ini akan seperti fungsi yang secara acak mengembalikan nilai yang salah atau secara acak dikembalikan sebelum benar-benar mencapai pernyataan pengembalian yang tepat. Sepertinya bug utama. Tetapi fakta bahwa mereka memilih untuk mendokumentasikan ini di halaman manual daripada memperbaikinya tampaknya menunjukkan bahwa ada alasan yang sah mengapa pthread_cond_waitakhirnya bangun dengan palsu. Agaknya, ada sesuatu yang intrinsik tentang cara kerjanya yang membuatnya sehingga tidak dapat membantu. Pertanyaannya adalah apa.

Mengapa tidak pthread_cond_waitkembali spuriously? Mengapa tidak bisa menjamin bahwa itu hanya akan bangun ketika sudah diberi sinyal dengan benar? Adakah yang bisa menjelaskan alasan perilakunya yang palsu?

Jonathan M Davis
sumber
5
Saya membayangkan itu ada hubungannya dengan pengembalian setiap kali proses menangkap sinyal. Kebanyakan * nixes tidak memulai kembali panggilan pemblokiran setelah sinyal memotongnya; mereka hanya mengatur / mengembalikan kode kesalahan yang mengatakan sinyal terjadi.
cao
1
@ cHao: walaupun perhatikan bahwa karena variabel kondisi memiliki alasan lain untuk bangun palsu, penanganan sinyal bukanlah kesalahan untuk pthread_cond_(timed)wait: "Jika sinyal dikirim ... utas melanjutkan menunggu variabel kondisi seolah-olah itu adalah tidak terputus, atau akan mengembalikan nol karena bangun palsu ". Fungsi pemblokiran lain menunjukkan EINTRketika terganggu oleh sinyal (misalnya read), atau diminta untuk melanjutkan (misalnya pthread_mutex_lock). Jadi jika tidak ada alasan lain untuk bangun palsu, pthread_cond_waitbisa didefinisikan seperti salah satu dari itu.
Steve Jessop
4
Artikel terkait di Wikipedia: Spurious wakeup
Palec
3
Vladimir Prus Yang Berguna : Spurious Wakeups .
iammilind
Banyak fungsi tidak dapat melakukan pekerjaan mereka sepenuhnya (I / O terputus) dan mengamati fungsi dapat menerima non acara seperti perubahan ke direktori di mana perubahan dibatalkan atau dikembalikan kembali. Apa masalahnya?
curiousguy

Jawaban:

77

Penjelasan berikut diberikan oleh David R. Butenhof dalam "Programming with POSIX Threads" (hlm. 80):

Wake up palsu mungkin terdengar aneh, tetapi pada beberapa sistem multiprosesor, membuat wakeup kondisi sepenuhnya dapat diprediksi secara substansial mungkin memperlambat semua operasi variabel kondisi.

Dalam diskusi comp.programming.threads berikut , ia memperluas pemikiran di balik desain:

Patrick Doyle menulis: 
> Dalam artikel, Tom Payne menulis: 
>> Kaz Kylheku menulis: 
>>: Karena implementasi terkadang tidak dapat menghindari memasukkan 
>>: wakeups palsu ini; mungkin mahal untuk mencegahnya.

>> Tapi mengapa? Mengapa ini sangat sulit? Sebagai contoh, apakah kita sedang membicarakan
>> situasi di mana waktu tunggu habis tepat saat sinyal tiba? 

> Anda tahu, saya ingin tahu apakah para perancang pthreads menggunakan logika seperti ini: 
> Pengguna variabel kondisi harus memeriksa kondisi saat keluar, 
> jadi kami tidak akan menempatkan beban tambahan pada mereka jika kami mengizinkan 
> bangun palsu; dan karena dibayangkan itu memungkinkan palsu
> wakeups bisa membuat implementasi lebih cepat, itu hanya bisa membantu jika kita 
> izinkan mereka. 

> Mereka mungkin tidak memiliki implementasi tertentu dalam pikiran. 

Anda sebenarnya tidak jauh sama sekali, kecuali Anda tidak mendorongnya cukup jauh. 

Tujuannya adalah untuk memaksakan kode yang benar / kuat dengan memerlukan loop predikat. Ini
didorong oleh kontingen akademis yang terbukti benar di antara "inti benang" di Indonesia 
kelompok kerja, meskipun saya tidak berpikir ada yang benar-benar tidak setuju dengan maksud tersebut 
begitu mereka mengerti apa artinya. 

Kami mengikuti niat itu dengan beberapa tingkat pembenaran. Yang pertama adalah itu
"religius" menggunakan loop melindungi aplikasi terhadap ketidaksempurnaannya sendiri 
praktik pengkodean. Yang kedua adalah tidak sulit membayangkan secara abstrak
mesin dan kode implementasi yang dapat memanfaatkan persyaratan ini untuk meningkatkan 
kinerja kondisi rata - rata menunggu operasi melalui optimalisasi 
mekanisme sinkronisasi. 
/ ------------------ [David.Buten ... @ compaq.com] ------------------ \ 
| Compaq Computer Corporation, Arsitek POSIX Thread |
| Buku saya: http://www.awl.com/cseng/titles/0-201-63392-2/ |
\ ----- [http://home.earthlink.net/~anneart/family/dave.html] ----- / 

NPE
sumber
22
pada dasarnya ini tidak mengatakan apa-apa. Tidak ada penjelasan yang diberikan di sini selain dari pemikiran awal bahwa "itu dapat membuat segalanya lebih cepat" tetapi tidak ada yang tahu bagaimana atau apakah itu bisa terjadi.
Bogdan Ionitza
107

Setidaknya ada dua hal 'bangun palsu' bisa berarti:

  • Utas yang diblokir pthread_cond_waitdapat kembali dari panggilan meskipun tidak ada panggilan ke pthread_call_signalatau pthread_cond_broadcastpada kondisi yang terjadi.
  • Utas diblokir sebagai pthread_cond_waitbalasannya karena panggilan ke pthread_cond_signalatau pthread_cond_broadcast, namun setelah mendapatkan kembali mutex, predikat yang mendasarinya ternyata tidak lagi benar.

Tetapi kasus terakhir dapat terjadi bahkan jika implementasi variabel kondisi tidak memungkinkan kasus sebelumnya. Pertimbangkan antrean konsumen produsen, dan tiga utas.

  • Thread 1 baru saja mengeluarkan elemen dan merilis mutex, dan antrian sekarang kosong. Thread melakukan apa pun yang dilakukannya dengan elemen yang diperolehnya pada beberapa CPU.
  • Thread 2 mencoba untuk mengeluarkan elemen, tetapi menemukan antrian kosong ketika diperiksa di bawah mutex, panggilan pthread_cond_wait, dan blokir dalam panggilan menunggu sinyal / siaran.
  • Thread 3 mendapatkan mutex, memasukkan elemen baru ke dalam antrian, memberitahukan variabel kondisi, dan melepaskan kunci.
  • Menanggapi pemberitahuan dari utas 3, utas 2, yang menunggu dengan syarat, dijadwalkan untuk berjalan.
  • Namun sebelum utas 2 mengelola CPU dan mengambil kunci antrian, utas 1 menyelesaikan tugasnya saat ini, dan kembali ke antrian untuk pekerjaan lebih lanjut. Ia mendapatkan kunci antrian, memeriksa predikat, dan menemukan bahwa ada pekerjaan dalam antrian. Itu melanjutkan untuk mengeluarkan item yang dimasukkan thread 3, melepaskan kunci, dan melakukan apa pun yang dilakukan dengan item yang di-thread 3 enqueued.
  • Thread 2 sekarang mendapatkan CPU dan mendapatkan kunci, tetapi ketika memeriksa predikat, ia menemukan bahwa antrian kosong. Thread 1 'mencuri' item, sehingga bangun tampaknya palsu. Thread 2 perlu menunggu pada kondisi lagi.

Jadi karena Anda sudah selalu perlu memeriksa predikat di bawah satu lingkaran, tidak ada bedanya jika variabel kondisi yang mendasari dapat memiliki jenis lain dari bangun palsu.

acm
sumber
23
Iya. Pada dasarnya, inilah yang terjadi ketika suatu acara digunakan sebagai ganti mekanisme sinkronisasi dengan hitungan. Sayangnya, tampaknya POSIX semaphores, (tetap pada Linux), juga mengalami spurius wakeups. Saya hanya merasa agak aneh bahwa kegagalan fungsionalitas dasar primitif sinkronisasi hanya diterima sebagai 'normal' dan harus dikerjakan di tingkat pengguna :( Mungkin, pengembang akan siap jika sistem panggilan didokumentasikan dengan bagian 'Spurious segfault' atau, mungkin 'Spurious menghubungkan ke URL yang salah' atau 'Pembukaan palsu file yang salah'
Martin James
2
Skenario yang lebih umum dari "wake up" adalah kemungkinan besar efek samping dari panggilan ke pthread_cond_broadcast (). Katakanlah Anda memiliki kumpulan 5 utas, dua bangun untuk siaran dan melakukan pekerjaan. Tiga lainnya bangun dan menemukan pekerjaan telah dilakukan. Sistem multi-prosesor juga dapat menyebabkan sinyal kondisional membangunkan banyak utas secara tidak sengaja. Kode hanya memeriksa predikat lagi, melihat keadaan tidak valid, dan kembali tidur. Dalam kedua kasus, memeriksa predikat menyelesaikan masalah. IMO, secara umum, pengguna tidak boleh menggunakan mutasi dan syarat POSIX mentah.
CubicleSoft
1
@ MartinJames - Bagaimana dengan EINTR "palsu" klasik? Saya akan setuju bahwa terus-menerus menguji EINTR dalam satu lingkaran sedikit mengganggu dan membuat kode agak jelek tetapi pengembang tetap melakukannya untuk menghindari kerusakan acak.
CubicleSoft
2
@Yola Tidak itu tidak bisa, karena Anda seharusnya mengunci mutex di sekitar pthread_cond_signal/broadcastdan Anda tidak akan dapat melakukannya, sampai mutex dibuka dengan menelepon pthread_cond_wait.
a3f
1
Contoh jawaban ini sangat realistis dan saya setuju bahwa memeriksa predikat adalah ide yang bagus. Namun, tidak dapat diperbaiki dengan baik dengan mengambil langkah bermasalah "utas 1 menyelesaikan tugasnya saat ini, dan kembali ke antrian untuk pekerjaan yang lebih banyak" dan menggantinya dengan "utas 1 menyelesaikan tugasnya saat ini, dan kembali menunggu variabel kondisi "? Itu akan menghilangkan mode kegagalan yang dijelaskan dalam jawaban, dan saya cukup yakin itu akan membuat kode yang benar, dengan tidak adanya bangun palsu . Apakah ada implementasi aktual yang menghasilkan bangun palsu dalam praktik?
Quuxplusone
7

Bagian "Kebangkitan Berganda oleh Sinyal Kondisi" di pthread_cond_signal memiliki contoh implementasi pthread_cond_wait dan pthread_cond_signal yang melibatkan wakekup palsu.

Jingguo Yao
sumber
2
Saya pikir jawaban ini salah, sejauh ini. Implementasi sampel pada halaman tersebut memiliki implementasi "beri tahu satu" yang setara dengan "beri tahu semua"; tetapi tampaknya tidak menghasilkan wakeups sebenarnya palsu . Satu-satunya cara agar sebuah thread terbangun adalah dengan beberapa utas lain yang memanggil "beri tahu semua", atau dengan utas lain yang memanggil-hal-berlabel- "beri tahu satu" - yang mana benar-benar- "beri tahu semua".
Quuxplusone
5

Sementara saya tidak berpikir itu dianggap pada saat desain, berikut adalah alasan teknis sebenarnya: Dalam kombinasi dengan pembatalan ulir, ada beberapa kondisi di mana mengambil opsi untuk membangunkan "secara palsu" mungkin benar-benar diperlukan, setidaknya kecuali Anda Bersedia memberikan batasan yang sangat kuat pada strategi implementasi seperti apa yang mungkin.

Masalah utama adalah bahwa, jika sebuah thread bekerja pada pembatalan saat diblokir pthread_cond_wait, efek sampingnya haruslah seolah-olah tidak mengkonsumsi sinyal apa pun pada variabel kondisi. Namun, sulit (dan sangat membatasi) untuk memastikan bahwa Anda belum mengkonsumsi sinyal ketika Anda mulai bertindak pada pembatalan, dan pada tahap ini mungkin tidak mungkin untuk "memposting ulang" sinyal ke variabel kondisi, karena Anda mungkin berada dalam situasi di mana penelepon pthread_cond_signalsudah dibenarkan telah menghancurkan condvar dan membebaskan memori di mana ia tinggal.

Penyisihan untuk bangun palsu memberi Anda jalan keluar yang mudah. Alih-alih terus bertindak atas pembatalan ketika tiba sementara diblokir pada variabel kondisi, jika Anda mungkin telah mengkonsumsi sinyal (atau jika Anda ingin malas, tidak peduli apa), Anda dapat mendeklarasikan bahwa peringatan palsu telah terjadi sebagai gantinya, dan kembali dengan sukses. Ini sama sekali tidak mengganggu operasi pembatalan, karena penelepon yang benar hanya akan bertindak pada pembatalan yang tertunda saat berikutnya ia mengulang dan menelepon pthread_cond_waitlagi.

R .. GitHub BERHENTI MEMBANTU ICE
sumber