Kunci Rekursif (Mutex) vs Kunci Non-Rekursif (Mutex)

183

POSIX memungkinkan mutex bersifat rekursif. Itu berarti utas yang sama dapat mengunci mutex yang sama dua kali dan tidak akan menemui jalan buntu. Tentu saja itu juga perlu membuka kuncinya dua kali, jika tidak, tidak ada utas lain yang dapat memperoleh mutex. Tidak semua sistem yang mendukung pthreads juga mendukung mutex rekursif, tetapi jika mereka ingin menjadi POSIX, mereka harus melakukannya .

API lain (lebih banyak API tingkat tinggi) juga biasanya menawarkan mutex, sering disebut Kunci. Beberapa sistem / bahasa (misalnya Cocoa Objective-C) menawarkan mutex keduanya, rekursif dan non rekursif. Beberapa bahasa juga hanya menawarkan satu atau yang lain. Misal dalam Java mutex selalu bersifat rekursif (utas yang sama mungkin dua kali "menyinkronkan" pada objek yang sama). Bergantung pada fungsionalitas utas lainnya yang mereka tawarkan, tidak memiliki mutex rekursif mungkin tidak ada masalah, karena mereka dapat dengan mudah ditulis sendiri (saya sudah menerapkan sendiri mutex rekursif sendiri berdasarkan operasi mutex / kondisi yang lebih sederhana).

Apa yang tidak saya mengerti: Untuk apa mutex non-rekursif itu bagus? Mengapa saya ingin kebuntuan utas jika mengunci mutex yang sama dua kali? Bahkan bahasa tingkat tinggi yang dapat menghindari itu (misalnya menguji apakah ini akan menemui jalan buntu dan melemparkan pengecualian jika itu benar) biasanya tidak melakukan itu. Mereka akan membiarkan kebuntuan utas sebagai gantinya.

Apakah ini hanya untuk kasus-kasus, di mana saya secara tidak sengaja menguncinya dua kali dan hanya membukanya sekali dan dalam kasus mutex rekursif, akan lebih sulit untuk menemukan masalahnya, jadi alih-alih saya langsung menemui jalan buntu untuk melihat di mana kunci yang salah muncul? Tetapi tidak bisakah saya melakukan hal yang sama dengan mengembalikan penghitung kunci saat membuka kunci dan dalam situasi, di mana saya yakin saya melepaskan kunci terakhir dan penghitungnya tidak nol, saya bisa melempar pengecualian atau mencatat masalahnya? Atau apakah ada kasus penggunaan lain yang lebih berguna dari mutex non rekursif yang gagal saya lihat? Atau mungkin hanya kinerja, karena mutex non-rekursif bisa sedikit lebih cepat daripada yang rekursif? Namun, saya menguji ini dan perbedaannya tidak terlalu besar.

Mecki
sumber

Jawaban:

154

Perbedaan antara mutasi rekursif dan non-rekursif berkaitan dengan kepemilikan. Dalam kasus mutex rekursif, kernel harus melacak thread yang benar-benar mendapatkan mutex pertama kali sehingga dapat mendeteksi perbedaan antara rekursi vs thread lain yang harus diblokir. Sebagai jawaban lain menunjukkan, ada pertanyaan tentang overhead tambahan ini baik dari segi memori untuk menyimpan konteks ini dan juga siklus yang diperlukan untuk mempertahankannya.

Namun , ada pertimbangan lain yang juga dimainkan di sini.

Karena mutex rekursif memiliki rasa memiliki, utas yang meraih mutex haruslah utas yang sama yang melepaskan mutex. Dalam hal mutex non-rekursif, tidak ada rasa memiliki dan setiap utas biasanya dapat melepaskan mutex tidak peduli benang mana yang awalnya mengambil mutex. Dalam banyak kasus, jenis "mutex" ini sebenarnya lebih merupakan tindakan semaphore, di mana Anda tidak harus menggunakan mutex sebagai perangkat pengecualian tetapi menggunakannya sebagai perangkat sinkronisasi atau sinyal antara dua atau lebih utas.

Properti lain yang datang dengan rasa memiliki dalam mutex adalah kemampuan untuk mendukung warisan prioritas. Karena kernel dapat melacak utas yang memiliki mutex dan juga identitas dari semua pemblokir, dalam sistem utas prioritas, menjadi mungkin untuk meningkatkan prioritas utas yang saat ini memiliki muteks untuk prioritas utas prioritas tertinggi. yang saat ini memblokir di mutex. Warisan ini mencegah masalah inversi prioritas yang dapat terjadi dalam kasus tersebut. (Perhatikan bahwa tidak semua sistem mendukung pewarisan prioritas pada mutex semacam itu, tetapi fitur lain yang dimungkinkan melalui gagasan kepemilikan).

Jika Anda merujuk ke kernel VxWorks RTOS klasik, mereka mendefinisikan tiga mekanisme:

  • mutex - mendukung rekursi, dan pewarisan prioritas opsional. Mekanisme ini biasanya digunakan untuk melindungi bagian-bagian penting dari data secara koheren.
  • semaphore biner - tidak ada rekursi, tidak ada pewarisan, pengecualian sederhana, pengambil dan pemberi tidak harus utas yang sama, rilis siaran tersedia. Mekanisme ini dapat digunakan untuk melindungi bagian-bagian penting, tetapi juga sangat berguna untuk pensinyalan yang koheren atau sinkronisasi antar utas.
  • menghitung semaphore - tidak ada rekursi atau pewarisan, bertindak sebagai penghitung sumber daya yang koheren dari penghitungan awal yang diinginkan, hanya blok thread di mana jumlah bersih terhadap sumber daya adalah nol.

Sekali lagi, ini agak bervariasi berdasarkan platform - terutama apa yang mereka sebut hal-hal ini, tetapi ini harus mewakili konsep dan berbagai mekanisme yang berperan.

Jeff tinggi
sumber
9
penjelasan Anda tentang mutex non-rekursif terdengar lebih seperti semaphore. Mutex (apakah rekursif atau non-rekursif) memiliki pengertian kepemilikan.
Jay D
@ JayD Sangat membingungkan ketika orang berdebat tentang hal-hal seperti ini .. jadi siapa entitas yang mendefinisikan hal-hal ini?
Pacerier
13
@Pacerier Standar yang relevan. Jawaban ini misalnya salah untuk posix (pthreads), di mana membuka mutex normal di utas selain utas yang menguncinya adalah perilaku yang tidak terdefinisi, sementara melakukan hal yang sama dengan pengecekan kesalahan atau mutasi rekursif menghasilkan kode kesalahan yang dapat diprediksi. Sistem dan standar lain mungkin berperilaku sangat berbeda.
nos
Mungkin ini naif, tetapi saya mendapat kesan bahwa ide sentral dari sebuah mutex adalah bahwa utas penguncian membuka kunci mutex dan kemudian utas lainnya dapat melakukan hal yang sama. Dari computing.llnl.gov/tutorials/pthreads :
user657862
2
@curiousguy - rilis siaran membebaskan setiap dan semua utas yang diblokir di semaphore tanpa secara eksplisit memberikannya (tetap kosong) sedangkan pemberian biner yang normal hanya akan melepaskan utas di bagian depan antrian tunggu (dengan asumsi ada satu yang diblokir).
Tall Jeff
123

Jawabannya bukan efisiensi. Mutex non-reentrant mengarah pada kode yang lebih baik.

Contoh: A :: foo () memperoleh kunci. Itu kemudian memanggil B :: bar (). Ini berfungsi dengan baik ketika Anda menulisnya. Tetapi beberapa saat kemudian seseorang mengubah B :: bar () untuk memanggil A :: baz (), yang juga memperoleh kunci.

Nah, jika Anda tidak memiliki mutex rekursif, ini deadlock. Jika Anda memilikinya, itu berjalan, tetapi mungkin rusak. A :: foo () mungkin telah meninggalkan objek dalam keadaan tidak konsisten sebelum memanggil bar (), dengan asumsi bahwa baz () tidak dapat dijalankan karena ia juga memperoleh mutex. Tapi mungkin tidak boleh berjalan! Orang yang menulis A :: foo () berasumsi bahwa tidak ada yang bisa memanggil A :: baz () pada saat yang sama - itulah alasan mengapa kedua metode tersebut memperoleh kunci.

Model mental yang tepat untuk menggunakan mutex: Mutex melindungi invarian. Ketika mutex dipegang, invarian dapat berubah, tetapi sebelum melepaskan mutex, invarian dibuat kembali. Kunci reentran berbahaya karena kedua kali Anda mendapatkan kunci, Anda tidak dapat memastikan invarian benar.

Jika Anda senang dengan kunci reentrant, itu hanya karena Anda belum harus men-debug masalah seperti ini sebelumnya. Java memiliki kunci non-reentrant hari ini di java.util.concurrent.locks, omong-omong.

Jonathan
sumber
4
Butuh beberapa saat untuk mendapatkan apa yang Anda katakan tentang invarian tidak valid ketika Anda mengambil kunci untuk kedua kalinya. Poin bagus! Bagaimana jika itu adalah kunci baca-tulis (seperti ReadWriteLock Java) dan Anda memperoleh kunci baca lalu mendapatkan kembali kunci baca untuk kedua kalinya di utas yang sama. Anda tidak akan membatalkan invarian setelah memperoleh kunci baca, bukan? Jadi, ketika Anda mendapatkan kunci baca kedua, invarian masih benar.
Dgrant
1
@ Jonathan Apakah Java memiliki kunci non-reentrant hari ini di java.util.concurrent.locks ??
user454322
1
+1 Saya kira, bahwa penggunaan yang paling umum untuk kunci reentrant adalah di dalam kelas tunggal, di mana beberapa metode dapat dipanggil dari potongan kode yang dijaga dan tidak dijaga. Ini sebenarnya bisa selalu diperhitungkan. @ user454322 Tentu Semaphore,.
maaartinus
1
Maafkan kesalahpahaman saya, tapi saya tidak melihat bagaimana ini relevan dengan mutex. Misalkan tidak ada multithreading dan penguncian yang terlibat, A::foo()mungkin masih meninggalkan objek dalam keadaan tidak konsisten sebelum memanggil A::bar(). Apa hubungan mutex, rekursif atau tidak, yang ada hubungannya dengan kasus ini?
Siyuan Ren
1
@ SiyuanRen: Masalahnya adalah alasan lokal tentang kode. Orang (setidaknya saya) dilatih untuk mengenali daerah terkunci sebagai pemeliharaan yang tidak berubah, yaitu pada saat Anda memperoleh kunci, tidak ada utas lain yang mengubah keadaan, sehingga penahan di wilayah kritis bertahan. Ini bukan aturan yang sulit, dan Anda dapat membuat kode dengan invarian yang tidak diingat, tetapi itu hanya akan membuat kode Anda lebih sulit untuk dipikirkan dan dipelihara. Hal yang sama terjadi dalam mode berulir tunggal tanpa mutex, tetapi di sana kami tidak dilatih untuk bernalar secara lokal di sekitar kawasan yang dilindungi.
David Rodríguez - dribeas
92

Seperti yang ditulis oleh Dave Butenhof sendiri :

"Yang terbesar dari semua masalah besar dengan mutasi rekursif adalah mereka mendorong Anda untuk sepenuhnya kehilangan jejak skema penguncian dan ruang lingkup Anda. Ini mematikan. Jahat. Ini adalah" pemakan utas ". Anda memegang kunci untuk waktu sesingkat mungkin. Jika Anda memanggil sesuatu dengan kunci dipegang hanya karena Anda tidak tahu itu dipegang, atau karena Anda tidak tahu apakah callee membutuhkan mutex, maka Anda memegangnya terlalu lama. membidik senapan pada aplikasi Anda dan menarik pelatuknya. Anda mungkin mulai menggunakan utas untuk mendapatkan konkurensi; tetapi Anda baru saja MENCEGAH konkurensi. "

Chris Cleeland
sumber
9
Perhatikan juga bagian terakhir dalam respons ...you're not DONE until they're [recursive mutex] all gone.. Or sit back and let someone else do the design.
Butenhof
2
Dia juga memberi tahu bahwa menggunakan satu global recursive mutex (pendapatnya adalah bahwa Anda hanya perlu satu) tidak apa-apa sebagai penopang untuk secara sadar menunda kerja keras memahami invarian perpustakaan eksternal ketika Anda mulai menggunakannya dalam kode multithreaded. Tetapi Anda tidak boleh menggunakan tongkat penyangga untuk selamanya, tetapi pada akhirnya menginvestasikan waktu untuk memahami dan memperbaiki invarian konkurensi kode. Jadi kita dapat memparafrasekan bahwa menggunakan mutasi rekursif adalah hutang teknis.
FooF
13

Model mental yang tepat untuk menggunakan mutex: Mutex melindungi invarian.

Mengapa Anda yakin bahwa ini adalah model mental yang benar untuk menggunakan mutex? Saya pikir model yang tepat adalah melindungi data tetapi tidak invarian.

Masalah melindungi invarian hadir bahkan dalam aplikasi single-threaded dan tidak memiliki kesamaan dengan multi-threading dan mutex.

Selanjutnya, jika Anda perlu melindungi invarian, Anda masih dapat menggunakan semaphore biner yang tidak pernah bersifat rekursif.


sumber
Benar. Ada mekanisme yang lebih baik untuk melindungi invarian.
ActiveTrayPrntrTagDataStrDrvr
8
Ini harus menjadi komentar untuk jawaban yang menawarkan pernyataan itu. Mutex tidak hanya melindungi data, tetapi juga melindungi invarian. Cobalah untuk menulis beberapa wadah sederhana (yang paling sederhana menjadi tumpukan) dalam hal atom (di mana data melindungi dirinya sendiri), bukan mutex dan Anda akan memahami pernyataan itu.
David Rodríguez - dribeas
Mutex tidak melindungi data, mereka melindungi invarian. Namun invarian itu dapat digunakan untuk melindungi data.
Jon Hanna
4

Salah satu alasan utama bahwa mutex rekursif berguna adalah dalam hal mengakses metode beberapa kali dengan utas yang sama. Sebagai contoh, katakanlah jika mutex lock melindungi bank A / c untuk ditarik, maka jika ada biaya yang juga terkait dengan penarikan itu, maka mutex yang sama harus digunakan.

avis
sumber
4

Satu-satunya kasus penggunaan yang baik untuk mutasi rekursi adalah ketika suatu objek berisi beberapa metode. Ketika salah satu metode memodifikasi konten objek, dan karenanya harus mengunci objek sebelum keadaan konsisten lagi.

Jika metode menggunakan metode lain (yaitu: addNewArray () memanggil addNewPoint (), dan menyelesaikan dengan recheckBounds ()), tetapi salah satu dari fungsi itu sendiri perlu mengunci mutex, maka mutex rekursif adalah win-win.

Untuk kasus lain (menyelesaikan pengkodean yang buruk, menggunakannya bahkan pada objek yang berbeda) jelas salah!

DarkZeros
sumber
1

Apa gunanya mutex non-rekursif?

Mereka benar-benar baik ketika Anda harus memastikan mutex dibuka sebelum melakukan sesuatu. Ini karena pthread_mutex_unlockdapat menjamin bahwa mutex tidak terkunci hanya jika tidak rekursif.

pthread_mutex_t      g_mutex;

void foo()
{
    pthread_mutex_lock(&g_mutex);
    // Do something.
    pthread_mutex_unlock(&g_mutex);

    bar();
}

Jika g_mutexnon-rekursif, kode di atas dijamin untuk memanggil bar()dengan mutex yang tidak dikunci .

Dengan demikian menghilangkan kemungkinan kebuntuan jika bar()terjadi fungsi eksternal yang tidak diketahui yang mungkin melakukan sesuatu yang dapat mengakibatkan utas lain mencoba untuk mendapatkan mutex yang sama. Skenario semacam itu tidak jarang dalam aplikasi yang dibangun di atas kumpulan thread, dan dalam aplikasi terdistribusi, di mana panggilan antarproses dapat menelurkan utas baru tanpa disadari bahkan oleh programmer klien. Dalam semua skenario seperti itu, terbaik untuk menjalankan fungsi eksternal tersebut hanya setelah kunci dilepaskan.

Jika g_mutexrekursif, tidak akan ada cara untuk memastikan itu dibuka sebelum melakukan panggilan.

Igor G
sumber