Multi-threading tanpa kunci adalah untuk ahli threading yang sebenarnya

Saya membaca jawaban yang diberikan Jon Skeet untuk sebuah pertanyaan dan di dalamnya dia menyebutkan ini:

Sejauh yang saya ketahui, multi-threading bebas kunci adalah untuk ahli threading nyata, yang saya bukan salah satunya.

Ini bukan pertama kalinya saya mendengar ini, tetapi saya menemukan sangat sedikit orang yang berbicara tentang bagaimana Anda sebenarnya melakukannya jika Anda tertarik untuk mempelajari cara menulis kode multi-threading tanpa kunci.

Jadi pertanyaan saya adalah selain mempelajari semua yang Anda bisa tentang threading, dll. Di mana Anda mulai mencoba belajar secara khusus menulis kode multi-threading tanpa kunci dan apa saja sumber yang bagus.

Bersulang

Penerapan "bebas kunci" saat ini mengikuti pola yang sama hampir sepanjang waktu:

• membaca beberapa negara bagian dan membuat salinannya *
• ubah salinan *
• melakukan operasi yang saling bertautan
• coba lagi jika gagal

_{(* opsional: tergantung pada struktur data / algoritma)}

Bit terakhir sangat mirip dengan spinlock. Faktanya, ini adalah spinlock dasar . :)
Saya setuju dengan @nobugz dalam hal ini: biaya operasi interlock yang digunakan dalam multi-threading tanpa kunci didominasi oleh tugas cache dan koherensi memori yang harus dijalankannya .

Apa yang Anda peroleh dengan struktur data yang "bebas kunci" adalah bahwa "kunci" Anda sangat halus . Ini mengurangi kemungkinan bahwa dua thread bersamaan mengakses "kunci" yang sama (lokasi memori).

Trik yang sering terjadi adalah Anda tidak memiliki kunci khusus - sebaliknya Anda memperlakukan misalnya semua elemen dalam larik atau semua node dalam daftar tertaut sebagai "kunci putar". Anda membaca, mengubah, dan mencoba memperbarui jika tidak ada pembaruan sejak terakhir Anda membaca. Jika ada, coba lagi.
Hal ini membuat "penguncian" Anda (oh, maaf, non-penguncian :) sangat halus, tanpa memasukkan memori tambahan atau persyaratan sumber daya.
Membuatnya lebih halus mengurangi kemungkinan menunggu. Membuatnya sesempurna mungkin tanpa memasukkan persyaratan sumber daya tambahan kedengarannya bagus, bukan?

Namun, sebagian besar kesenangan dapat datang dari memastikan pemuatan / pemesanan toko yang benar .
Berlawanan dengan intuisi seseorang, CPU bebas menyusun ulang memori baca / tulis - mereka sangat pintar, omong-omong: Anda akan kesulitan mengamati ini dari satu utas. Namun, Anda akan mengalami masalah ketika Anda mulai melakukan multi-threading pada banyak inti. Intuisi Anda akan rusak: hanya karena instruksi lebih awal dalam kode Anda, itu tidak berarti bahwa itu benar-benar akan terjadi lebih awal. CPU dapat memproses instruksi yang tidak berurutan: dan mereka terutama suka melakukan ini pada instruksi dengan akses memori, untuk menyembunyikan latensi memori utama dan memanfaatkan cache mereka dengan lebih baik.

Sekarang, pasti bertentangan dengan intuisi bahwa urutan kode tidak mengalir "dari atas ke bawah", melainkan berjalan seolah-olah tidak ada urutan sama sekali - dan dapat disebut "taman bermain setan". Saya yakin tidak mungkin memberikan jawaban yang tepat seperti apa pemesanan ulang muat / penyimpanan yang akan dilakukan. Sebaliknya, seseorang selalu berbicara dalam istilah mays and mights and can dan bersiap untuk yang terburuk. "Oh, CPU mungkin menyusun ulang pembacaan ini menjadi sebelum penulisan itu, jadi yang terbaik adalah menempatkan penghalang memori di sini, di tempat ini."

Masalah diperumit oleh fakta bahwa mays dan mights ini pun dapat berbeda di seluruh arsitektur CPU. Ini mungkin menjadi kasus, misalnya, bahwa sesuatu yang dijamin untuk tidak terjadi dalam satu arsitektur yang mungkin terjadi pada yang lain.

Untuk mendapatkan hak multi-threading "lock-free", Anda harus memahami model memori.
Namun, mendapatkan model memori dan jaminan yang benar bukanlah hal yang sepele, seperti yang ditunjukkan oleh cerita ini, di mana Intel dan AMD melakukan beberapa koreksi pada dokumentasi yang MFENCEmenyebabkan beberapa kekacauan di antara pengembang JVM . Ternyata, dokumentasi yang diandalkan developer sejak awal tidak begitu akurat.

Kunci di .NET menghasilkan penghalang memori implisit, jadi Anda aman menggunakannya (sebagian besar waktu, yaitu ... lihat misalnya kebesaran Joe Duffy - Brad Abrams - Vance Morrison ini tentang inisialisasi malas, kunci, volatil, dan memori hambatan. :) (Pastikan untuk mengikuti tautan di halaman itu.)

Sebagai bonus tambahan, Anda akan diperkenalkan dengan model memori .NET di side quest . :)

Ada juga "oldie but goldie" dari Vance Morrison: What Every Dev Must Know About Multithreaded Apps .

... dan tentu saja, seperti yang disebutkan @Eric , Joe Duffy adalah pandai membaca tentang subjek tersebut.

STM yang baik dapat mendekati penguncian yang sangat halus dan mungkin akan memberikan kinerja yang mendekati atau setara dengan implementasi buatan tangan. Salah satunya adalah STM.NET dari proyek DevLabs MS.

Jika Anda bukan seorang fanatik .NET saja, Doug Lea melakukan beberapa pekerjaan hebat di JSR-166 .
Cliff Click memiliki pandangan menarik tentang tabel hash yang tidak bergantung pada lock-striping - seperti yang dilakukan tabel hash bersamaan Java dan .NET - dan tampaknya menskalakan dengan baik ke 750 CPU.

Jika Anda tidak takut untuk menjelajah ke wilayah Linux, artikel berikut memberikan lebih banyak wawasan tentang internal arsitektur memori saat ini dan bagaimana berbagi baris-cache dapat merusak kinerja: Apa yang harus diketahui setiap programmer tentang memori .

@Ben membuat banyak komentar tentang MPI: Saya sangat setuju bahwa MPI dapat bersinar di beberapa daerah. Solusi berbasis MPI dapat lebih mudah untuk dipikirkan, lebih mudah diimplementasikan dan tidak terlalu rentan terhadap kesalahan daripada implementasi penguncian setengah matang yang mencoba untuk menjadi pintar. (Namun demikian - secara subyektif - juga berlaku untuk solusi berbasis STM.) Saya juga berani bertaruh bahwa ini adalah tahun cahaya lebih mudah untuk menulis dengan benar aplikasi terdistribusi yang layak di misalnya Erlang, seperti yang disarankan oleh banyak contoh sukses.

MPI, bagaimanapun, memiliki biaya sendiri dan masalahnya sendiri ketika dijalankan pada sistem multi-inti tunggal . Misalnya di Erlang, ada masalah yang harus diselesaikan seputar sinkronisasi penjadwalan proses dan antrian pesan .
Juga, pada intinya, sistem MPI biasanya mengimplementasikan sejenis penjadwalan N: M kooperatif untuk "proses ringan". Ini misalnya berarti bahwa ada peralihan konteks yang tak terhindarkan antara proses ringan. Memang benar bahwa ini bukan "sakelar konteks klasik" tetapi sebagian besar merupakan operasi ruang pengguna dan dapat dibuat dengan cepat - namun saya sangat meragukan bahwa ini dapat dilakukan di bawah siklus 20-200 operasi yang saling terkait . Pengalihan konteks mode pengguna adalah tentu lebih lambatbahkan di pustaka Intel McRT. Penjadwalan N: M dengan proses ringan bukanlah hal baru. LWP sudah lama ada di Solaris. Mereka ditinggalkan. Ada serat di NT. Mereka sebagian besar adalah peninggalan sekarang. Ada "aktivasi" di NetBSD. Mereka ditinggalkan. Linux memiliki pendapatnya sendiri tentang masalah penguliran N: M. Sepertinya sudah mati sekarang.
Dari waktu ke waktu, ada pesaing baru: misalnya McRT dari Intel , atau yang terbaru Penjadwalan Mode Pengguna bersama dengan ConCRT dari Microsoft.
Pada tingkat terendah, mereka melakukan apa yang dilakukan penjadwal N: M MPI. Erlang - atau sistem MPI lainnya -, mungkin mendapatkan keuntungan besar pada sistem SMP dengan mengeksploitasi UMS baru .

Saya kira pertanyaan OP bukanlah tentang manfaat dan argumen subjektif untuk / melawan solusi apa pun, tetapi jika saya harus menjawabnya, saya kira itu tergantung pada tugasnya: untuk membangun struktur data dasar berkinerja tinggi dan tingkat rendah yang berjalan pada NET juga (meskipun mereka tampaknya tidak aktif). sistem tunggal dengan banyak inti , baik teknik kunci-rendah / "bebas-kunci" atau STM akan menghasilkan hasil terbaik dalam hal kinerja dan mungkin akan mengalahkan solusi MPI kapan pun dari segi kinerja, bahkan jika kerutan di atas telah diperbaiki misalnya di Erlang.
Untuk membangun sesuatu yang cukup lebih kompleks yang berjalan pada satu sistem, saya mungkin akan memilih penguncian berbutir kasar klasik atau jika kinerja sangat diperhatikan, sebuah STM.
Untuk membangun sistem terdistribusi, sistem MPI mungkin akan menjadi pilihan yang wajar.
Perhatikan bahwa ada implementasi MPI untuk

Buku Joe Duffy:

http://www.bluebytesoftware.com/books/winconc/winconc_book_resources.html

Dia juga menulis blog tentang topik ini.

Trik untuk mendapatkan program rendah-kunci yang tepat adalah untuk memahami secara mendalam tepat apa aturan dari model memori yang di kombinasi tertentu Anda dari perangkat keras, sistem operasi, dan lingkungan runtime.

Saya pribadi tidak cukup pintar untuk melakukan pemrograman kunci-rendah yang benar di luar InterlockedIncrement, tetapi jika Anda, hebat, lakukanlah. Pastikan Anda meninggalkan banyak dokumentasi dalam kode sehingga orang yang tidak secerdas Anda tidak secara tidak sengaja merusak salah satu invarian model memori Anda dan memunculkan bug yang tidak mungkin ditemukan.

Tidak ada yang namanya "lock-free threading" hari ini. Itu adalah taman bermain yang menarik bagi akademisi dan sejenisnya, pada akhir abad lalu ketika perangkat keras komputer lambat dan mahal. Algoritma Dekker selalu menjadi favorit saya, perangkat keras modern telah memadamkannya. Itu tidak berfungsi lagi.

Dua perkembangan telah mengakhiri ini: perbedaan yang semakin besar antara kecepatan RAM dan CPU. Dan kemampuan produsen chip untuk menempatkan lebih dari satu inti CPU pada sebuah chip.

Masalah kecepatan RAM mengharuskan perancang chip untuk menempatkan buffer pada chip CPU. Buffer menyimpan kode dan data, yang dapat diakses dengan cepat oleh inti CPU. Dan dapat dibaca dan ditulis dari / ke RAM dengan kecepatan yang jauh lebih lambat. Buffer ini disebut cache CPU, kebanyakan CPU memiliki setidaknya dua di antaranya. Cache tingkat pertama kecil dan cepat, tingkat kedua besar dan lebih lambat. Selama CPU dapat membaca data dan instruksi dari cache tingkat 1, itu akan berjalan cepat. Cache miss sangat mahal, ini membuat CPU tertidur selama 10 siklus jika data tidak ada di cache pertama, sebanyak 200 siklus jika tidak ada di cache ke-2 dan perlu dibaca dari RAM.

Setiap inti CPU memiliki cache sendiri, mereka menyimpan "tampilan" RAM mereka sendiri. Saat CPU menulis data, penulisan dilakukan ke cache yang kemudian, perlahan, dialihkan ke RAM. Tak terelakkan, setiap inti sekarang akan memiliki tampilan konten RAM yang berbeda. Dengan kata lain, satu CPU tidak tahu apa yang telah ditulis oleh CPU lain sampai siklus penulisan RAM tersebut selesai dan CPU menyegarkan tampilannya sendiri.

Itu sangat tidak sesuai dengan threading. Kamu selalu benar peduli dengan status utas lain ketika Anda harus membaca data yang ditulis oleh utas lain. Untuk memastikan ini, Anda perlu secara eksplisit memprogram apa yang disebut penghalang memori. Ini adalah CPU primitif tingkat rendah yang memastikan bahwa semua cache CPU berada dalam keadaan konsisten dan memiliki tampilan RAM terkini. Semua penulisan yang tertunda harus di-flush ke RAM, cache kemudian perlu di-refresh.

Ini tersedia di .NET, metode Thread.MemoryBarrier () mengimplementasikannya. Mengingat bahwa ini adalah 90% dari pekerjaan yang dilakukan oleh pernyataan kunci (dan 95 +% dari waktu eksekusi), Anda tidak berada di depan dengan menghindari alat yang diberikan .NET kepada Anda dan mencoba menerapkannya sendiri.

Google untuk mengunci struktur data gratis dan memori transaksional perangkat lunak .

Saya setuju dengan John Skeet tentang hal ini; lock-free threading adalah tempat bermain iblis, dan paling baik diserahkan kepada orang-orang yang tahu bahwa mereka tahu apa yang perlu mereka ketahui.

Ketika datang ke multi-threading, Anda harus tahu persis apa yang Anda lakukan. Maksud saya, jelajahi semua kemungkinan skenario / kasus yang mungkin terjadi saat Anda bekerja di lingkungan multi-utas. Multithreading tanpa kunci bukanlah perpustakaan atau kelas yang kami gabungkan, ini adalah pengetahuan / pengalaman yang kami peroleh selama perjalanan kami di utas.

Meskipun penguncian tanpa kunci mungkin sulit dilakukan di .NET, sering kali Anda dapat membuat peningkatan yang signifikan saat menggunakan kunci dengan mempelajari secara tepat apa yang perlu dikunci, dan meminimalkan bagian terkunci ... ini juga dikenal sebagai meminimalkan perincian kunci .

Sebagai contoh, katakan saja Anda perlu membuat utas koleksi aman. Jangan hanya mengunci secara membabi buta di sekitar metode iterasi atas koleksi jika ia melakukan beberapa tugas intensif CPU pada setiap item. Anda mungkin hanya perlu memasang kunci untuk membuat salinan koleksi yang dangkal. Iterasi salinan kemudian bisa bekerja tanpa kunci. Tentu saja ini sangat tergantung pada spesifikasi kode Anda, tetapi saya telah dapat memperbaiki masalah konvoi kunci dengan pendekatan ini.