Apa itu spinlock di Linux?

32

Saya ingin tahu tentang Linux spinlocks secara rinci; dapatkah seseorang menjelaskannya kepada saya?

Sen
sumber

Jawaban:

34

Spin lock adalah cara untuk melindungi sumber daya bersama agar tidak dimodifikasi oleh dua atau lebih proses secara bersamaan. Proses pertama yang mencoba memodifikasi sumber daya "memperoleh" kunci dan melanjutkan perjalanannya, melakukan apa yang diperlukan dengan sumber daya. Setiap proses lain yang kemudian mencoba untuk mendapatkan kunci dihentikan; mereka dikatakan "berputar di tempat" menunggu kunci yang akan dirilis oleh proses pertama, demikian nama kunci berputar.

Kernel Linux menggunakan kunci spin untuk banyak hal, seperti ketika mengirim data ke perangkat tertentu. Sebagian besar periferal perangkat keras tidak dirancang untuk menangani beberapa pembaruan keadaan simultan. Jika dua modifikasi berbeda harus terjadi, yang satu harus mengikuti yang lain, mereka tidak bisa tumpang tindih. Putaran kunci memberikan perlindungan yang diperlukan, memastikan bahwa modifikasi terjadi satu per satu.

Spin lock adalah masalah karena blok pemintalan yang membuat inti CPU tidak dapat melakukan pekerjaan lain. Sementara kernel Linux memang menyediakan layanan multitasking untuk program ruang pengguna yang berjalan di bawahnya, fasilitas multitasking untuk tujuan umum tidak meluas ke kode kernel.

Situasi ini berubah, dan telah menjadi sebagian besar keberadaan Linux. Sampai melalui Linux 2.0, kernel tersebut hampir murni murni sebuah program penugasan tunggal: setiap kali CPU menjalankan kode kernel, hanya satu inti CPU yang digunakan, karena ada satu putaran kunci yang melindungi semua sumber daya bersama, yang disebut Big Kernel Lock (BKL) ). Dimulai dengan Linux 2.2, BKL perlahan-lahan dipecah menjadi banyak kunci independen yang masing-masing melindungi kelas sumber daya yang lebih fokus. Saat ini, dengan kernel 2.6, BKL masih ada, tetapi hanya digunakan oleh kode yang benar-benar tua yang tidak dapat dengan mudah dipindahkan ke beberapa kunci granular. Sekarang sangat mungkin bagi sebuah kotak multicore untuk membuat setiap CPU menjalankan kode kernel yang berguna.

Ada batas untuk utilitas memecah BKL karena kernel Linux tidak memiliki multitasking umum. Jika sebuah inti CPU diblokir berputar pada kunci putaran kernel, itu tidak dapat ditarik kembali, untuk melakukan sesuatu yang lain sampai kunci dilepaskan. Itu hanya duduk dan berputar sampai kunci dilepaskan.

Spin lock secara efektif dapat mengubah kotak monster 16-core menjadi kotak single-core, jika beban kerjanya sedemikian rupa sehingga setiap inti selalu menunggu kunci spin tunggal. Ini adalah batas utama untuk skalabilitas kernel Linux: menggandakan core CPU dari 2 menjadi 4 mungkin akan hampir dua kali lipat kecepatan kotak Linux, tetapi menggandakannya dari 16 menjadi 32 mungkin tidak akan terjadi, dengan sebagian besar beban kerja.

Warren Young
sumber
@ Warren: Beberapa keraguan - Saya ingin tahu lebih banyak tentang Kunci Kernel Besar ini dan implikasinya. Saya juga tidak mengerti paragraf terakhir "menggandakan core CPU dari 2 menjadi 4 mungkin akan hampir dua kali lipat kecepatan kotak Linux, tetapi menggandakannya dari 16 menjadi 32 mungkin tidak akan"
Sen
2
Re: implikasi dari BKL: Saya pikir saya sudah menjelaskannya di atas. Dengan hanya satu kunci di kernel, setiap saat dua core mencoba melakukan sesuatu yang dilindungi oleh BKL, satu core diblokir sementara yang pertama selesai menggunakan sumber daya yang dilindungi. Semakin banyak kunci yang dikunci, semakin rendah kemungkinan hal ini akan terjadi, sehingga semakin besar pemanfaatan prosesor.
Warren Young
2
Re: menggandakan: Maksud saya ada hukum pengembalian berkurang ketika menambahkan core prosesor ke komputer. Ketika jumlah inti meningkat, demikian juga kemungkinan bahwa dua atau lebih dari mereka akan perlu mengakses sumber daya yang dilindungi oleh kunci tertentu. Meningkatkan granularity kunci mengurangi kemungkinan tabrakan tersebut, tetapi ada overhead dalam menambahkan terlalu banyak. Anda dapat dengan mudah melihat ini di superkomputer, yang sering memiliki ribuan prosesor saat ini: sebagian besar beban kerja tidak efisien karena mereka tidak dapat menghindari pemalasan banyak prosesor karena pertentangan sumber daya bersama.
Warren Young
1
Walaupun ini adalah penjelasan yang menarik (+1 untuk itu), saya tidak berpikir itu efektif dalam menyampaikan perbedaan antara spinlocks dan jenis kunci lainnya.
Gilles 'SO- stop being evil'
2
Jika seseorang ingin mengetahui perbedaan antara kunci putaran dan, katakanlah, semafor, itu pertanyaan yang berbeda. Pertanyaan lain yang bagus tetapi tangensial adalah, apa tentang desain kernel Linux yang membuat spin mengunci pilihan yang baik alih-alih sesuatu yang lebih umum dalam kode userland, seperti mutex. Jawaban ini banyak menguraikan apa adanya.
Warren Young
11

Putaran kunci adalah ketika suatu proses terus-menerus melakukan pemungutan suara untuk kunci yang akan dihapus. Itu dianggap buruk karena prosesnya menghabiskan siklus (biasanya) sia-sia. Ini bukan khusus Linux, tetapi pola pemrograman umum. Dan meskipun secara umum dianggap praktik yang buruk, itu sebenarnya adalah solusi yang tepat; ada kasus-kasus di mana biaya menggunakan penjadwal lebih tinggi (dalam hal siklus CPU) daripada biaya beberapa siklus yang diperkirakan akan bertahan dengan spinlock.

Contoh spinlock:

#!/bin/sh
#wait for some program to clear a lock before doing stuff
while [ -f /var/run/example.lock ]; do
  sleep 1
done
#do stuff

Seringkali ada cara untuk menghindari kunci putar. Untuk contoh khusus ini, ada alat Linux yang disebut inotifywait (biasanya tidak diinstal secara default). Jika ditulis dalam C, Anda cukup menggunakan inotify API yang disediakan Linux.

Contoh yang sama, menggunakan inotifywait menunjukkan cara menyelesaikan hal yang sama tanpa kunci penguncian:

#/bin/sh
inotifywait -e delete_self /var/run/example.lock
#do stuff
Shawn J. Goff
sumber
Apa peran penjadwal di sana? Atau apakah ia memiliki peran?
Sen
1
Dalam metode spin lock, scheduler melanjutkan proses setiap ~ 1 detik untuk melakukan tugasnya (yang hanya memeriksa keberadaan file). Dalam contoh inotifywait, penjadwal hanya melanjutkan proses ketika proses anak (inotifywait) keluar. Inotifywait juga sedang tidur; scheduler hanya melanjutkannya ketika peristiwa inotify terjadi.
Shawn J. Goff
Jadi bagaimana skenario ini ditangani dalam sistem prosesor inti tunggal?
Sen
@ Sen: Ini dijelaskan dengan cukup baik di Driver Perangkat Linux .
Gilles 'SO- stop being evil'
1
Skrip bash adalah contoh buruk dari spinlock. Anda menjeda proses membuatnya tertidur. Spinlock tidak pernah tidur. Pada mesin inti tunggal, ia hanya menangguhkan penjadwal dan melanjutkan (tanpa menunggu sibuk)
Martin
7

Ketika sebuah utas mencoba untuk mendapatkan kunci, tiga hal dapat terjadi jika gagal, ia dapat mencoba dan memblokir, dapat mencoba dan melanjutkan, ia dapat mencoba kemudian pergi tidur memberitahu OS untuk membangunkannya ketika beberapa peristiwa terjadi.

Sekarang coba dan lanjutkan menggunakan lebih sedikit waktu daripada mencoba dan memblokir. Katakanlah untuk saat ini bahwa "coba dan lanjutkan" akan mengambil unit waktu saya dan "coba dan blokir" akan membutuhkan seratus.

Sekarang mari kita asumsikan bahwa rata-rata utas akan membutuhkan waktu 4 unit untuk memegang kunci. Sia-sia menunggu 100 unit. Jadi alih-alih Anda menulis satu lingkaran "coba dan lanjutkan". Pada upaya keempat Anda biasanya akan mendapatkan kunci. Ini adalah kunci putaran. Disebut demikian karena utasnya terus berputar sampai terkunci.

Tindakan keamanan tambahan adalah membatasi berapa kali loop berjalan. Jadi, dalam contoh Anda membuat for loop run misalnya enam kali, jika gagal maka Anda "mencoba dan memblokir".

Jika Anda tahu bahwa utas akan selalu menahan kunci untuk mengatakan 200 unit, maka Anda membuang-buang waktu komputer untuk setiap mencoba dan melanjutkan.

Jadi pada akhirnya, kunci kunci bisa sangat efisien atau boros. Akan sia-sia ketika waktu "khas" untuk memegang kunci lebih tinggi daripada waktu yang dibutuhkan untuk "mencoba dan memblokir". Ini efisien ketika waktu khas untuk memegang kunci jauh lebih kecil daripada waktu untuk 'mencoba dan memblokir ".

Ps: Buku yang harus Anda baca di utas adalah "A Primer Utas", jika Anda masih bisa menemukannya.

HandyGandy
sumber
utas terus berputar di tempat sampai mendapat kunci . Bisakah Anda memberi tahu saya apa pemintalan ini? Apakah ini seperti itu datang ke wait_queue dan dieksekusi oleh Penjadwal? Mungkin saya mencoba masuk ke level rendah, tetapi masih tidak bisa menahan keraguan saya.
Sen
Berputar di antara 3-4 instruksi dalam lingkaran, pada dasarnya.
Paul Stelian
5

Sebuah kunci adalah cara untuk dua atau lebih tugas (proses, benang) untuk sinkronisasi. Khususnya, ketika kedua tugas membutuhkan akses intermiten ke sumber daya yang hanya dapat digunakan oleh satu tugas pada satu waktu, itu adalah cara bagi tugas untuk mengatur agar tidak menggunakan sumber daya pada saat yang sama. Untuk mengakses sumber daya, tugas harus melakukan langkah-langkah berikut:

take the lock
use the resource
release the lock

Mengambil kunci tidak dimungkinkan jika tugas lain telah mengambilnya. (Anggap kunci sebagai benda fisik. Entah benda itu ada di laci, atau ada yang memegangnya. Hanya orang yang memegang benda yang dapat mengakses sumber daya.) Jadi, "ambil kunci" benar-benar berarti "tunggu sampai tidak ada orang lain yang memiliki kunci, lalu ambil ”.

Dari sudut pandang tingkat tinggi, ada dua cara utama untuk menerapkan kunci: spinlocks, dan kondisi. Dengan spinlocks , mengambil kunci berarti hanya "berputar" (yaitu tidak melakukan apa-apa dalam satu lingkaran) sampai tidak ada orang lain yang memiliki kunci. Dengan kondisi, jika tugas mencoba untuk mengambil kunci tetapi diblokir karena tugas lain menahannya, pendatang baru memasuki antrian menunggu; operasi rilis memberi sinyal ke setiap tugas menunggu bahwa kunci sekarang tersedia.

(Penjelasan ini tidak cukup untuk membiarkan Anda menerapkan kunci, karena saya belum mengatakan apa pun tentang atomicity. Tetapi atomicity tidak penting di sini.)

Spinlocks jelas boros: tugas menunggu terus memeriksa apakah kunci diambil. Jadi mengapa dan kapan digunakan? Spinlocks seringkali sangat murah untuk didapatkan jika gembok tidak dipegang. Ini membuatnya menarik ketika peluang kunci untuk dipegang kecil. Lebih jauh lagi, spinlocks hanya dapat digunakan jika mendapatkan kunci tidak diharapkan memakan waktu lama. Jadi spinlocks cenderung digunakan dalam situasi di mana mereka akan tetap bertahan untuk waktu yang sangat singkat, sehingga sebagian besar upaya diharapkan berhasil pada percobaan pertama, dan mereka yang membutuhkan menunggu jangan menunggu lama.

Ada penjelasan yang bagus tentang spinlocks dan mekanisme konkurensi lain dari kernel Linux di Linux Device Drivers , bab 5.

Gilles 'SANGAT berhenti menjadi jahat'
sumber
Apa cara yang baik untuk mengimplementasikan primitif sinkronisasi lainnya? Ambil spinlock, periksa apakah orang lain sudah menerapkan primitif yang sebenarnya, lalu gunakan penjadwal atau berikan akses? Bisakah kita menganggap blok disinkronkan () di Jawa bentuk spinlock, dan di primitif yang diterapkan dengan benar hanya menggunakan spinlock?
Paul Stelian
@PaulStelian Memang umum untuk menerapkan kunci "lambat" dengan cara ini. Saya tidak tahu cukup Java untuk menjawab bagian itu, tapi saya ragu itu synchronizedakan diterapkan oleh spinlock: sebuah synchronizedblok bisa berjalan untuk waktu yang sangat lama. synchronizedadalah konstruksi bahasa untuk membuat kunci mudah digunakan dalam kasus-kasus tertentu, bukan primitif untuk membangun primitif sinkronisasi yang lebih besar.
Gilles 'SANGAT berhenti menjadi jahat'
3

Spinlock adalah kunci yang beroperasi dengan menonaktifkan penjadwal dan mungkin menyela (varian irqsave) pada inti tertentu tempat kunci tersebut diperoleh. Ini berbeda dari mutex karena menonaktifkan penjadwalan sehingga hanya utas Anda yang dapat berjalan saat spinlock ditahan. Mutex memungkinkan utas prioritas lainnya yang lebih tinggi dijadwalkan sementara itu diadakan tetapi tidak memungkinkan mereka untuk secara bersamaan menjalankan bagian yang dilindungi. Karena spinlocks menonaktifkan multitasking Anda tidak dapat mengambil spinlock dan kemudian memanggil beberapa kode lain yang akan mencoba untuk mendapatkan mutex. Kode Anda di dalam bagian spinlock tidak boleh tidur (kode biasanya tertidur ketika bertemu dengan mutex yang terkunci atau semaphore kosong).

Perbedaan lain dengan mutex adalah bahwa thread biasanya mengantri untuk mutex sehingga mutex di bawahnya memiliki antrian. Sedangkan spinlock hanya memastikan bahwa tidak ada utas lain yang akan berjalan meskipun harus. Karena itu, Anda tidak boleh memegang spinlock saat memanggil fungsi di luar file Anda yang Anda tidak yakin tidak akan tidur.

Saat Anda ingin membagikan spinlock dengan interupsi, Anda harus menggunakan varian irqsave. Ini tidak hanya akan menonaktifkan scheduler tetapi juga akan menonaktifkan interupsi. Masuk akal bukan? Spinlock berfungsi dengan memastikan tidak ada lagi yang akan berjalan. Jika Anda tidak ingin interupsi dijalankan, Anda menonaktifkannya dan melanjutkan dengan aman ke bagian kritis.

Pada mesin multicore, spinlock sebenarnya akan berputar menunggu inti lain yang memegang kunci untuk melepaskannya. Pemintalan ini hanya terjadi pada mesin multicore karena pada inti tunggal itu tidak dapat terjadi (Anda memegang spinlock dan melanjutkan atau Anda tidak pernah menjalankan sampai kunci dilepaskan).

Spinlock tidak sia-sia di tempat yang masuk akal. Untuk bagian-bagian kritis yang sangat kecil, akan sia-sia untuk mengalokasikan antrian tugas mutex dibandingkan dengan hanya menangguhkan penjadwal untuk beberapa mikrodetik yang diperlukan untuk menyelesaikan pekerjaan penting. Jika Anda perlu tidur atau menahan kunci di operasi io (yang mungkin tidur) kemudian gunakan mutex. Tentu saja jangan pernah mengunci spinlock dan kemudian coba lepaskan di dalam interupsi. Meskipun ini akan berhasil, itu akan seperti omong kosong Arduino (flagnotset); dalam hal demikian gunakan semaphore.

Ambil spinlock saat Anda membutuhkan pengecualian mutual sederhana untuk blok transaksi memori. Raih mutex ketika Anda ingin beberapa utas berhenti tepat sebelum kunci mutex dan kemudian utas prioritas tertinggi yang akan dipilih untuk melanjutkan ketika mutex menjadi bebas dan ketika Anda mengunci dan melepaskan di utas yang sama. Ambil semafor saat Anda ingin mempostingnya di satu utas atau interupsi dan ambil di utas lain. Ini tiga cara yang sedikit berbeda untuk memastikan saling pengecualian dan mereka digunakan untuk tujuan yang sedikit berbeda.

Martin
sumber