Kapan orang harus menggunakan spinlock sebagai ganti mutex?

294

Saya pikir keduanya melakukan pekerjaan yang sama, bagaimana Anda memutuskan mana yang akan digunakan untuk sinkronisasi?

kompilasi-fan
sumber
1
kemungkinan duplikat Spinlock Versus Semaphore!
Paul R
11
Mutex dan Semaphore bukan hal yang sama, jadi saya pikir ini bukan duplikat. Jawaban dari artikel yang direferensikan menyatakan ini dengan benar. Untuk detail lebih lanjut, lihat barrgroup.com/Embedded-Systems/How-To/RTOS-Mutex-Semaphore
nanoquack

Jawaban:

729

Teori

Secara teori, ketika sebuah thread mencoba untuk mengunci mutex dan tidak berhasil, karena mutex sudah terkunci, itu akan tertidur, segera memungkinkan thread lain untuk dijalankan. Ini akan terus tidur sampai terbangun, yang akan terjadi begitu mutex sedang dibuka oleh benang apa pun yang memegang kunci sebelumnya. Ketika sebuah thread mencoba untuk mengunci spinlock dan tidak berhasil, ia akan terus mencoba menguncinya lagi, sampai akhirnya berhasil; dengan demikian ia tidak akan membiarkan utas lain menggantikannya (namun, sistem operasi akan secara paksa beralih ke utas lainnya, begitu kuantum runtime CPU dari utas saat ini telah terlampaui, tentu saja).

Masalah

Masalahnya dengan mutex adalah bahwa menempatkan utas untuk tidur dan membangunkannya kembali keduanya adalah operasi yang agak mahal, mereka akan membutuhkan cukup banyak instruksi CPU dan dengan demikian juga membutuhkan waktu. Jika sekarang mutex hanya dikunci untuk waktu yang sangat singkat, waktu yang dihabiskan untuk menidurkan dan membangunkannya lagi mungkin melebihi waktu yang sebenarnya telah ditidurkan oleh benang dan bahkan mungkin melebihi waktu thread tersebut akan telah terbuang dengan terus-menerus memberikan suara pada spinlock. Di sisi lain, pemungutan suara pada spinlock akan terus-menerus menghabiskan waktu CPU dan jika kunci dipegang untuk waktu yang lebih lama, ini akan menghabiskan lebih banyak waktu CPU dan akan jauh lebih baik jika utasnya tidur.

Solusinya

Menggunakan spinlocks pada sistem single-core / single-CPU biasanya tidak masuk akal, karena selama polling spinlock memblokir satu-satunya inti CPU yang tersedia, tidak ada thread lain yang dapat berjalan dan karena tidak ada thread lain yang dapat berjalan, kunci tidak akan dibuka kuncinya juga. TKI, spinlock hanya menghabiskan waktu CPU pada sistem itu tanpa manfaat nyata. Jika utas ditidurkan, utas lain bisa berjalan sekaligus, mungkin membuka kunci kunci dan kemudian membiarkan utas pertama melanjutkan pemrosesan, setelah utas terbangun lagi.

Pada sistem multi-core / multi-CPU, dengan banyak kunci yang ditahan untuk waktu yang sangat singkat saja, waktu yang terbuang untuk terus-menerus membuat thread tertidur dan membangunkannya lagi dapat menurunkan kinerja runtime secara nyata. Saat menggunakan spinlocks sebagai gantinya, utas mendapatkan kesempatan untuk mengambil keuntungan dari kuantum runtime penuh mereka (selalu hanya memblokir untuk periode waktu yang sangat singkat, tetapi kemudian segera melanjutkan pekerjaan mereka), yang mengarah ke throughput pemrosesan yang jauh lebih tinggi.

Latihan

Karena sangat sering programmer tidak dapat mengetahui sebelumnya apakah mutex atau spinlocks akan lebih baik (mis. Karena jumlah core CPU dari arsitektur target tidak diketahui), juga sistem operasi tidak dapat mengetahui apakah suatu kode tertentu telah dioptimalkan untuk single-core atau lingkungan multi-core, kebanyakan sistem tidak benar-benar membedakan antara mutex dan spinlocks. Faktanya, sebagian besar sistem operasi modern memiliki mutex hybrid dan spinlocks hybrid. Apa sebenarnya itu artinya?

Mutex hybrid berperilaku seperti spinlock pada awalnya pada sistem multi-core. Jika utas tidak dapat mengunci mutex, itu tidak akan langsung tertidur, karena mutex mungkin akan segera dibuka, jadi sebaliknya mutex pertama-tama akan berperilaku persis seperti spinlock. Hanya jika kunci masih belum diperoleh setelah waktu tertentu (atau coba lagi atau faktor pengukuran lainnya), utas benar-benar tertidur. Jika kode yang sama berjalan pada sistem dengan hanya satu inti, mutex tidak akan berputar, meskipun, seperti, lihat di atas, itu tidak akan bermanfaat.

Spinlock hybrid berperilaku seperti spinlock normal pada awalnya, tetapi untuk menghindari pemborosan waktu CPU, ini mungkin memiliki strategi back-off. Biasanya tidak akan membuat utas tertidur (karena Anda tidak ingin itu terjadi ketika menggunakan spinlock), tetapi mungkin memutuskan untuk menghentikan utas (baik segera atau setelah waktu tertentu) dan memungkinkan utas lain berjalan , sehingga meningkatkan kemungkinan spinlock tidak terkunci (sakelar ulir murni biasanya lebih murah daripada sakelar yang tidur dan membangunkannya lagi nanti, meskipun tidak jauh).

Ringkasan

Jika ragu, gunakan mutex, mereka biasanya merupakan pilihan yang lebih baik dan kebanyakan sistem modern akan memungkinkan mereka untuk spinlock untuk waktu yang sangat singkat, jika ini tampaknya bermanfaat. Menggunakan spinlocks kadang-kadang dapat meningkatkan kinerja, tetapi hanya dalam kondisi tertentu dan fakta bahwa Anda ragu-ragu memberitahu saya, bahwa Anda tidak bekerja pada proyek apa pun saat ini di mana spinlock mungkin bermanfaat. Anda mungkin mempertimbangkan untuk menggunakan "objek kunci" Anda sendiri, yang dapat menggunakan spinlock atau mutex secara internal (misalnya perilaku ini dapat dikonfigurasi saat membuat objek seperti itu), awalnya menggunakan mutex di mana-mana dan jika Anda berpikir bahwa menggunakan spinlock di suatu tempat mungkin benar-benar membantu, cobalah dan bandingkan hasilnya (mis. menggunakan profiler), tetapi pastikan untuk menguji kedua kasus,

Pembaruan: Peringatan untuk iOS

Sebenarnya bukan khusus iOS tetapi iOS adalah platform di mana sebagian besar pengembang mungkin menghadapi masalah itu: Jika sistem Anda memiliki penjadwal utas, itu tidak menjamin bahwa utas apa pun, tidak peduli seberapa rendah prioritasnya, pada akhirnya akan mendapatkan kesempatan untuk berjalan, kemudian spinlocks dapat menyebabkan deadlock permanen. Penjadwal iOS membedakan berbagai kelas utas dan utas pada kelas yang lebih rendah hanya akan berjalan jika tidak ada utas di kelas yang lebih tinggi yang ingin dijalankan juga. Tidak ada strategi back-off untuk ini, jadi jika Anda memiliki utas kelas tinggi yang tersedia secara permanen, utas kelas rendah tidak akan pernah mendapatkan waktu CPU dan karenanya tidak pernah ada peluang untuk melakukan pekerjaan apa pun.

Masalahnya muncul sebagai berikut: Kode Anda mendapatkan spinlock di utas kelas prio rendah dan saat itu berada di tengah-tengah kunci itu, waktu kuantum telah terlampaui dan utas berhenti berjalan. Satu-satunya cara bagaimana spinlock ini dapat dilepaskan lagi adalah jika utas kelas rendah itu mendapatkan waktu CPU lagi tetapi ini tidak dijamin akan terjadi. Anda mungkin memiliki beberapa utas kelas prio tinggi yang selalu ingin dijalankan dan penjadwal tugas akan selalu memprioritaskan itu. Salah satu dari mereka mungkin berlari melintasi spinlock dan mencoba untuk mendapatkannya, yang tentu saja tidak mungkin, dan sistem akan membuatnya menghasilkan. Masalahnya adalah: Utas yang menghasilkan segera tersedia untuk berjalan lagi! Memiliki prio yang lebih tinggi daripada utas yang menahan kunci, utas yang memegang kunci tidak memiliki peluang untuk mendapatkan runtime CPU.

Mengapa masalah ini tidak terjadi pada mutex? Ketika thread prio tinggi tidak dapat memperoleh mutex, itu tidak akan menghasilkan, itu mungkin berputar sedikit tetapi pada akhirnya akan dikirim untuk tidur. Thread tidur tidak tersedia untuk berjalan sampai dibangunkan oleh suatu peristiwa, misalnya acara seperti mutex sedang dibuka yang sudah ditunggu-tunggu. Apple sadar akan masalah itu dan karenanya sudah usang OSSpinLock. Kunci baru disebut os_unfair_lock. Kunci ini menghindari situasi yang disebutkan di atas karena menyadari adanya kelas prioritas utas berbeda. Jika Anda yakin menggunakan spinlocks adalah ide yang bagus di proyek iOS Anda, gunakan yang itu. Menjauh dariOSSpinLock! Dan dalam keadaan apa pun, terapkan spinlocks Anda sendiri di iOS! Jika ragu, gunakan mutex! macOS tidak terpengaruh oleh masalah ini karena memiliki penjadwal utas yang berbeda yang tidak akan mengizinkan utas apa pun (bahkan utas prio rendah) untuk "berjalan kering" pada waktu CPU, masih situasi yang sama dapat muncul di sana dan kemudian akan menyebabkan sangat buruk kinerja, dengan demikian OSSpinLocksudah usang pada macOS juga.

Mecki
sumber
3
penjelasan yang luar biasa ... Saya ragu tentang spinlock i, apakah saya dapat menggunakan spinlock di ISR? jika tidak mengapa tidak
haris
4
@Mecki Jika saya tidak salah, saya yakin Anda menyarankan jawaban Anda bahwa mengiris waktu hanya terjadi pada sistem prosesor tunggal. Ini tidak benar! Anda dapat menggunakan kunci putaran pada sistem prosesor tunggal dan akan berputar hingga kuantum waktunya habis. Kemudian utas lain dengan prioritas yang sama dapat mengambil alih (seperti apa yang Anda gambarkan untuk sistem multi-prosesor).
fumoboy007
7
@ fumoboy007 "dan itu akan berputar sampai kuantum waktunya habis" // Yang berarti Anda membuang waktu CPU / daya baterai untuk apa-apa tanpa manfaat tunggal, yang benar-benar gila. Dan tidak, saya tidak mengatakan bahwa pemotongan waktu hanya terjadi pada sistem inti tunggal, saya katakan pada sistem inti tunggal HANYA mengiris waktu, sementara ada paralelisme NYATA dari sistem multicore (dan juga pemotongan waktu, namun tidak relevan dengan apa yang saya tulis di buku saya). balasan); Anda juga sama sekali tidak mengerti apa itu hybrid spinlock dan mengapa itu bekerja dengan baik pada sistem tunggal dan multicore.
Mecki
11
@ fumoboy007 Thread A memegang kunci dan terputus. Thread B berjalan dan menginginkan kunci, tetapi tidak bisa mendapatkannya, jadi ia berputar. Pada sistem multicore, Thread A dapat terus berjalan pada core lain sementara Thread B masih berputar, lepaskan kunci, dan Thread B dapat melanjutkan dalam kuantum waktu saat ini. Pada sistem inti tunggal, hanya ada satu inti yang dapat dijalankan Thread A untuk melepaskan kunci dan inti ini disibukkan oleh pemintalan Thread B. Jadi tidak mungkin spinlock bisa dilepaskan sebelum Thread B melampaui kuantum waktunya dan dengan demikian semua pemintalan hanyalah buang-buang waktu saja.
Mecki
2
Jika Anda ingin mempelajari lebih lanjut tentang spinlocks dan mutexes diimplementasikan dalam kernel Linux, saya sangat merekomendasikan membaca bab 5 dari besar Linux Device Drivers, Edisi Ketiga (LDD3) (mutexes: halaman 109; spinlocks: Halaman 116).
patryk.beza
7

Melanjutkan saran Mecki , artikel pthread mutex vs pthread spinlock di blog Alexander Sandler, Alex di Linux menunjukkan bagaimana spinlock& mutexesdapat diimplementasikan untuk menguji perilaku menggunakan #ifdef.

Namun, pastikan untuk menerima panggilan terakhir berdasarkan pengamatan Anda, pemahaman sebagai contoh yang diberikan adalah kasus yang terisolasi, persyaratan proyek Anda, lingkungan mungkin sama sekali berbeda.

TheCottonSilk
sumber
6

Harap perhatikan juga bahwa pada lingkungan dan kondisi tertentu (seperti berjalan di windows pada level pengiriman> = TINGKAT PENGIRIMAN), Anda tidak dapat menggunakan mutex melainkan spinlock. Pada unix - hal yang sama.

Berikut ini adalah pertanyaan yang setara pada situs unix stackexchange pesaing: /unix/5107/why-are-spin-locks-good-choices-in-linux-kernel-design-instead-of-something- lebih

Info tentang pengiriman pada sistem windows: http://download.microsoft.com/download/e/b/a/eba1050f-a31d-436b-9281-92cdfeae4b45/IRQL_thread.doc

Dan Jobs
sumber
6

Jawaban Mecki cukup baik. Namun, pada prosesor tunggal, menggunakan spinlock mungkin masuk akal ketika tugas menunggu di kunci untuk diberikan oleh Rutin Layanan Interupsi. Interupsi akan mentransfer kontrol ke ISR, yang akan menyiapkan sumber daya untuk digunakan oleh tugas yang menunggu. Itu akan berakhir dengan melepaskan kunci sebelum memberikan kontrol kembali ke tugas yang terputus. Tugas pemintalan akan menemukan spinlock tersedia dan melanjutkan.

AlanC
sumber
2
Saya tidak yakin sepenuhnya setuju dengan jawaban ini. Satu prosesor tunggal, jika tugas memegang kunci pada sumber daya, maka ISR tidak dapat melanjutkan dengan aman dan tidak bisa menunggu tugas untuk membuka kunci sumber daya (karena tugas memegang sumber daya terganggu). Dalam kasus seperti itu, tugas tersebut seharusnya menonaktifkan interupsi untuk menegakkan pengecualian antara dirinya dan ISR. Tentu saja, ini harus dilakukan untuk interval waktu yang sangat singkat.
user1202136
3

Mekanisme sinkronisasi Spinlock dan Mutex sangat umum saat ini untuk dilihat.

Mari kita pikirkan Spinlock terlebih dahulu.

Pada dasarnya ini adalah tindakan menunggu yang sibuk, yang berarti bahwa kita harus menunggu kunci tertentu dilepaskan sebelum kita dapat melanjutkan dengan tindakan selanjutnya. Secara konseptual sangat sederhana, sementara mengimplementasikannya tidak pada kasus ini. Misalnya: Jika kunci belum dilepaskan maka utasnya diganti dan masuk ke kondisi tidur, haruskah kita menghadapinya? Bagaimana cara menangani kunci sinkronisasi ketika dua utas secara bersamaan meminta akses?

Secara umum, ide paling intuitif adalah berurusan dengan sinkronisasi melalui variabel untuk melindungi bagian kritis. Konsep Mutex serupa, tetapi mereka masih berbeda. Fokus pada: Penggunaan CPU. Spinlock menghabiskan waktu CPU untuk menunggu melakukan tindakan, dan oleh karena itu, kita dapat meringkaskan perbedaan antara keduanya:

Dalam lingkungan multi-core yang homogen, jika waktu yang dihabiskan untuk bagian kritis lebih kecil daripada menggunakan Spinlock, karena kita dapat mengurangi waktu pengalihan konteks. (Perbandingan single-core tidak penting, karena beberapa implementasi sistem Spinlock di tengah sakelar)

Di Windows, menggunakan Spinlock akan memutakhirkan utas ke DISPATCH_LEVEL, yang dalam beberapa kasus mungkin tidak diizinkan, jadi kali ini kami harus menggunakan Mutex (APC_LEVEL).

Marcus Thornton
sumber
-6

Menggunakan spinlocks pada sistem single-core / single-CPU biasanya tidak masuk akal, karena selama polling spinlock memblokir satu-satunya inti CPU yang tersedia, tidak ada thread lain yang dapat berjalan dan karena tidak ada thread lain yang dapat berjalan, kunci tidak akan dibuka kuncinya juga. TKI, spinlock hanya menghabiskan waktu CPU pada sistem itu tanpa manfaat nyata

Ini salah. Tidak ada pemborosan siklus cpu dalam menggunakan spinlocks pada sistem prosesor uni, karena begitu suatu proses mengambil kunci putaran, preemption dinonaktifkan, sehingga tidak mungkin ada orang lain yang berputar! Hanya saja menggunakannya tidak masuk akal! Oleh karena itu, spinlocks pada sistem Uni digantikan oleh preempt_disable pada waktu kompilasi oleh kernel!

Neelansh Mittal
sumber
Kutipan masih sepenuhnya benar. Jika hasil kompilasi kode sumber tidak mengandung spinlocks, maka yang dikutip tidak relevan. Dengan asumsi apa yang Anda katakan benar tentang penggantian kernel spinlocks pada waktu kompilasi, bagaimana spinlocks ditangani ketika dikompilasi di komputer lain yang mungkin atau mungkin bukan uniprocessor, kecuali kita benar-benar berbicara tentang spinlocks hanya di kernel itu sendiri?
Hydranix
"Setelah suatu proses mengambil kunci putaran, preemption dinonaktifkan". Preemption tidak dinonaktifkan ketika suatu proses berputar. Jika itu yang terjadi, satu proses dapat menurunkan seluruh mesin dengan hanya memasukkan spinlock dan tidak pernah pergi. Perhatikan bahwa jika utas Anda berjalan di ruang kernel (alih-alih ruang pengguna), mengambil spin lock memang menonaktifkan preemption, tapi saya tidak berpikir itulah yang sedang dibahas di sini.
Konstantin Weitz
Pada waktu kompilasi oleh kernel ?
Shien
@konstantin FYI spin lock hanya dapat diambil di ruang kernel. Dan ketika spin lock diambil, preemption dinonaktifkan pada prosesor lokal.
Neelansh Mittal
@hydranix Tidak mengerti Anda? Jelas Anda tidak dapat mengompilasi modul dengan kernel di mana CONFIG_SMP diaktifkan, dan menjalankan modul yang sama pada kernel yang menonaktifkan CONFIG_SMP.
Neelansh Mittal