lockfree

bebas kunci

lockfree adalah kumpulan struktur data bebas kunci yang ditulis dalam standar C++11 dan cocok untuk semua platform - mulai dari yang tertanam secara mendalam hingga HPC.

Apa yang dimaksud dengan struktur data bebas kunci?

Struktur data bebas kunci adalah struktur data yang aman untuk thread dan interupsi untuk penggunaan bersamaan tanpa harus menggunakan mekanisme pengecualian bersama. Mereka paling berguna untuk komunikasi antar proses, dan seringkali berskala jauh lebih baik daripada struktur berbasis kunci dengan jumlah operasi dan thread.

Mengapa menggunakan lockfree

• Ditulis dalam standar C++11, kompatibel dengan semua platform yang mendukungnya
• Semua struktur data aman untuk thread dan interupsi dalam kasus penggunaannya masing-masing
• Tidak ada alokasi dinamis
• Dioptimalkan untuk kinerja tinggi
• Berlisensi MIT
• API tambahan untuk versi C++ yang lebih baru

Struktur data apa yang tersedia?

Struktur data konsumen tunggal produsen tunggal

• Antrian - Terbaik untuk operasi elemen tunggal, API yang sangat cepat dan sederhana yang hanya terdiri dari 2 metode.
• Ring Buffer - Struktur data yang lebih umum dengan kemampuan menangani banyak elemen sekaligus, menggunakan salinan perpustakaan standar sehingga sangat cepat untuk operasi massal.
• Buffer Bipartit - Variasi buffer ring dengan kemampuan untuk selalu menyediakan ruang linier di buffer, memungkinkan pemrosesan dalam buffer.
• Antrean Prioritas - Variasi antrian dengan kemampuan memberikan prioritas berbeda untuk elemen, sangat berguna untuk hal-hal seperti sinyal, peristiwa, dan paket komunikasi.

Struktur data ini lebih berperforma dan umumnya harus digunakan setiap kali hanya ada satu thread/interupsi yang mendorong data dan thread lain mengambilnya.

Struktur data multi-produsen multi-konsumen

• Antrian - Terbaik untuk operasi elemen tunggal, API yang sangat cepat dan sederhana yang hanya terdiri dari 2 metode.
• Antrean Prioritas - Variasi antrian dengan kemampuan memberikan prioritas berbeda untuk elemen, sangat berguna untuk hal-hal seperti sinyal, peristiwa, dan paket komunikasi.

Struktur data ini lebih umum, mendukung banyak produsen dan konsumen pada saat yang sama, namun memiliki penyimpanan dan kinerja yang berlebihan dibandingkan dengan struktur data konsumen tunggal produsen tunggal. Mereka juga memerlukan instruksi atom yang mungkin hilang dari beberapa mikrokontroler kelas bawah.

Bagaimana cara mendapatkan

Ada tiga cara utama untuk mendapatkan perpustakaan:

• Menggunakan CMake FetchContent()
• Sebagai submodul git
• Dengan mengunduh rilis dari GitHub

Konfigurasi

lockfree menggunakan penyelarasan cacheline untuk indeks guna menghindari fenomena False Sharing secara default, menghindari hilangnya kinerja karena pembatalan cacheline pada sistem koheren cache. Ini menyelaraskan indeks ke LOCKFREE_CACHELINE_LENGTH , 64 secara default.

Pada sistem tertanam, LOCKFREE_CACHE_COHERENT hampir selalu disetel sebagai false untuk menghindari pemborosan memori.

Selain itu, beberapa sistem memiliki panjang cacheline yang tidak biasa (misalnya CPU apple M1/M2 memiliki panjang cacheline 128 byte), dan LOCKFREE_CACHELINE_LENGTH harus disetel sesuai dengan kasus tersebut.

Keterbatasan yang diketahui

Semua struktur data di lockfree hanya dimaksudkan untuk digunakan untuk tipe sepele.

Pertanyaan Umum

Mengapa saya menggunakan ini untuk mengunci struktur data pada mesin yang dihosting?

Alasan terbesar Anda ingin menggunakan struktur data bebas kunci pada lingkungan yang dihosting adalah menghindari masalah seputar penguncian seperti kebuntuan, inversi prioritas, dan latensi akses nondeterministik. Jika digunakan dengan benar, struktur data bebas kunci juga dapat meningkatkan performa dalam beberapa skenario.

Selain itu, lockfree menyediakan cara untuk membangun aplikasi dan perpustakaan yang dapat dikompilasi untuk bekerja pada lingkungan POSIX dan non-POSIX tanpa #ifdef atau polimorfisme.

Mengapa menggunakan ini melalui mekanisme IPC yang disediakan RTOS pada sistem tertanam?

Meskipun penguncian biasanya tidak mahal pada sistem tertanam seperti mikrokontroler, terdapat beragam RTOS-es dan tidak ada API standar untuk penguncian. Fakta bahwa terdapat banyak arsitektur dari 8051 hingga RISC-V berarti metode manajemen interupsi juga tidak terstandarisasi.

lockfree menyediakan cara untuk membuat kode tertanam portabel dengan biaya kinerja yang dapat diabaikan dibandingkan dengan penguncian, kode yang menggunakan lockfree dapat dikompilasi untuk dijalankan pada platform tertanam apa pun yang mendukung C++11. Selain itu, kode tersebut dapat dengan mudah diuji pada mesin host tanpa perlu diolok-olok.

Apa keuntungan menggunakan C++ dibandingkan C untuk perpustakaan?

• Keamanan jenis, karena struktur data memiliki templat tipe dan ukuran
• Instansiasi yang jauh lebih sederhana dan tidak rawan kesalahan
• Performa lebih tinggi karena ukuran yang diketahui pada waktu kompilasi dan implementasi hanya header
• Enkapsulasi, buffer data adalah anggota kelas, bukan diteruskan oleh pointer

Apa klasifikasi formal struktur data di lockfree ?

Semua struktur di lockfree dibatasi , berbasis array , dan bebas kunci , struktur data spsc juga bebas menunggu dan aman untuk terminasi .

Teori dan referensi

Untuk wawasan lebih lanjut tentang pemrograman bebas kunci, lihat:

• Seri pembicaraan brilian dari Herb Sutter
• Seri bincang-bincang Live Lock-Free atau Deadlock dari Fedor Pikus
• Blog Dmitry Vyukov yang luar biasa