Beranda>Terkait pemrograman>C/C++
Unduh

xenium

xenium adalah perpustakaan khusus header yang menyediakan kumpulan struktur data bersamaan dan algoritma reklamasi memori. Struktur data diparameterisasi sehingga dapat digunakan dengan berbagai skema reklamasi (mirip dengan bagaimana STL memungkinkan penyesuaian pengalokasi).

  • saja
  • sangat dapat disesuaikan
  • tidak diperlukan kode inisialisasi
  • mendukung jumlah utas dinamis (tidak ada spesifikasi waktu kompilasi tetap)

Dokumentasi memberikan rincian lebih lanjut.

Proyek ini didasarkan pada pekerjaan saya sebelumnya di https://github.com/mpoeter/emr

Contoh Penggunaan 

# include < xenium/ramalhete_queue.hpp >
# include < xenium/reclamation/epoch_based.hpp >

struct msg { ... };

xenium::ramalhete_queue<
  std::unique_ptr<msg>,
  xenium::policy::reclaimer<xenium::reclamation::epoch_based<>>,
  xenium::policy::entries_per_node< 2048 >
> queue;

queue.push(std::make_unique<msg>());

std::unique_ptr<msg> data;
if (queue.try_pop(data)) {
    // do something with data
}

Struktur Data

Saat ini jumlah struktur data yang disediakan masih sedikit karena fokus selama ini adalah pada skema reklamasi. Namun, rencananya akan menambah beberapa struktur data lagi dalam waktu dekat.

  • michael_scott_queue - antrean multi-produsen/multi-konsumen bebas kunci tanpa batas yang diusulkan oleh Michael dan Scott [MS96].
  • ramalhete_queue - antrian multi-produsen/multi-konsumen cepat dan bebas kunci tanpa batas yang diusulkan oleh Ramalhete [Ram16].
  • vyukov_bounded_queue - antrian FIFO multi-produsen/multi-konsumen yang dibatasi berdasarkan versi yang diusulkan oleh Vyukov [Vyu10 ].
  • kirsch_kfifo_queue - antrean k-FIFO multi-produsen/multi-konsumen tak terbatas yang diusulkan oleh Kirsch dkk. [KLP13].
  • kirsch_bounded_kfifo_queue - antrian k-FIFO multi-produsen/multi-konsumen terbatas yang diusulkan oleh Kirsch dkk. [KLP13].
  • nikolaev_queue - antrian multi-produsen/multi-konsumen tak terbatas yang diusulkan oleh Nikolaev [Nik19].
  • nikolaev_bounded_queue - antrian multi-produsen/multi-konsumen terbatas yang diusulkan oleh Nikolaev [Nik19].
  • harris_michael_list_based_set - wadah bebas kunci yang berisi sekumpulan objek unik yang diurutkan. Struktur data ini didasarkan pada solusi yang diusulkan oleh Michael [Mic02] yang dibangun berdasarkan proposal asli Harris [Har01].
  • harris_michael_hash_map - peta hash bebas kunci berdasarkan solusi yang diusulkan oleh Michael [Mic02] yang dibuat berdasarkan proposal asli Harris [Har01].
  • chase_work_stealing_deque - deque pencurian karya berdasarkan proposal Chase dan Lev [CL05].
  • vyukov_hash_map - peta hash bersamaan yang menggunakan penguncian terperinci untuk operasi pembaruan. Implementasi ini sangat terinspirasi oleh versi yang diusulkan oleh Vyukov [Vyu08].
  • left_right - implementasi umum dari algoritma LeftRight yang diusulkan oleh Ramalhete dan Correia [RC15].
  • seqlock - implementasi dari kunci urutan (juga sering disebut sebagai "kunci berurutan").

Skema Reklamasi

Implementasi skema reklamasi didasarkan pada versi antarmuka yang diadaptasi yang diusulkan oleh Robison [Rob13].

Skema reklamasi berikut diterapkan:

  • lock_free_ref_count [Val95, MS95]
  • hazard_pointer [Mic04]
  • hazard_eras [RC17]
  • quiescent_state_based
  • generic_epoch_based - ini adalah reclaimer berbasis epoch umum yang dapat dikonfigurasi dalam beberapa cara. Untuk mempermudah, alias berikut telah ditentukan sebelumnya untuk konfigurasi terkait.
    • epoch_based [Fra04]
    • new_epoch_based [HMBW07]
    • debra [Bro15]
  • stamp_it [PT18a, PT18b]

Bangunan

xenium adalah pustaka header saja, jadi untuk menggunakannya, cukup memasukkan folder xenium ke dalam daftar direktori penyertaan Anda. Tidak diperlukan perpustakaan pihak ketiga lainnya. Namun implementasinya menggunakan fitur C++17, sehingga diperlukan compiler dengan dukungan C++17 yang memadai. Kompiler berikut digunakan dalam build CI dan oleh karena itu diketahui didukung:

  • gcc9
  • dentang10
  • Visual Studio 2019

Pengujian unit memerlukan googletest dan benchmark memerlukan taocpp/json dan taocpp/config . Dependensi ini disertakan sebagai submodul, sehingga pengujian unit dan/atau tolok ukur dapat dibuat sebagai berikut: 

 git clone https://github.com/mpoeter/xenium.git && cd xenium
git submodule update --init --recursive
mkdir build && cd build
cmake ..
make gtest
make benchmark

Referensi

[Kawan15] Trevor Alexander Brown. Merebut kembali memori untuk struktur data bebas kunci: Pasti ada cara yang lebih baik. Dalam Prosiding Simposium ACM 2015 tentang Prinsip Komputasi Terdistribusi (PODC) , halaman 261–270. ACM, 2015.
[CL05] David Chase dan Yossi Lev. Deque mencuri pekerjaan melingkar yang dinamis. Dalam Prosiding Simposium ACM Tahunan ke-17 tentang Paralelisme dalam Algoritma dan Arsitektur (SPAA) , halaman 21–28. ACM, 2005.
[Fra04] Keir Fraser. Kebebasan kunci yang praktis . Tesis PhD, Laboratorium Komputer Universitas Cambridge, 2004.
[Har01] Timotius L.Harris. Implementasi pragmatis dari daftar tertaut yang tidak memblokir. Dalam Prosiding Konferensi Internasional ke-15 tentang Komputasi Terdistribusi (DISC) , halaman 300–314. Springer-Verlag, 2001.
[HMBW07] Thomas E. Hart, Paul E. McKenney, Angela Demke Brown, dan Jonathan Walpole. Kinerja reklamasi memori untuk sinkronisasi tanpa kunci. Jurnal Komputasi Paralel dan Terdistribusi, 67(12):1270–1285, 2007.
[KLP13] Christoph Kirsch, Michael Lippautz, dan Hannes Payer. Antrean k-FIFO yang cepat dan terukur, bebas kunci. Dalam Prosiding Konferensi Internasional tentang Teknologi Komputasi Paralel (PaCT) , halaman 208–223, Springer-Verlag, 2013.
[Mik02] Maged M.Michael. Tabel hash dinamis bebas kunci berkinerja tinggi dan kumpulan berbasis daftar. Dalam Prosiding Simposium ACM Tahunan ke-14 tentang Algoritma dan Arsitektur Paralel (SPAA) , halaman 73–82. ACM, 2002.
[Mik04] Maged M.Michael. Petunjuk bahaya: Reklamasi memori yang aman untuk objek bebas kunci. Transaksi IEEE pada Sistem Paralel dan Terdistribusi, 15(6):491–504, 2004.
[MS95] Maged M. Michael dan Michael L. Scott. Koreksi metode manajemen memori untuk struktur data bebas kunci. Laporan teknis, Universitas Rochester, 1995.
[MS96] Maged M. Michael dan Michael L. Scott. Algoritma antrian bersamaan non-pemblokiran dan pemblokiran yang sederhana, cepat, dan praktis. Dalam Prosiding Simposium ACM Tahunan ke-15 tentang Prinsip Komputasi Terdistribusi (PODC) , halaman 267–275. ACM, 1996.
[Nik19] Ruslan Nikolaev Antrean fifo bebas kunci yang skalabel, portabel, dan hemat memori. Dalam Prosiding Simposium Internasional tentang Komputasi Terdistribusi (DISC) ke-33 , 2019.
[PT18a] Manuel Pöter dan Jesper Larsson Traff. Pengumuman singkat: Stamp-it, skema reklamasi memori bersamaan yang lebih efisien dalam model memori C++. Dalam Prosiding Simposium ACM Tahunan ke-30 tentang Paralelisme dalam Algoritma dan Arsitektur (SPAA) , halaman 355–358. ACM, 2018.
[PT18b] Manuel Pöter dan Jesper Larsson Traff. Stamp-it, skema reklamasi memori bersamaan yang lebih efisien dalam model memori C++. Laporan teknis, 2018.
[Ram16] Pedro Ramalhete. FAAArrayQueue - antrian bebas kunci MPMC (bagian 4 dari 4). Blog, November 2016.
[RC15] Pedro Ramalhete dan Andreia Correia. Kiri-Kanan - Teknik Kontrol Konkurensi dengan Pembacaan Tanpa Kesadaran Populasi Tanpa Tunggu. Oktober 2015
[RC17] Pedro Ramalhete dan Andreia Correia. Pengumuman singkat: Era bahaya - reklamasi memori yang tidak menghalangi. Dalam Prosiding Simposium ACM Tahunan ke-29 tentang Paralelisme dalam Algoritma dan Arsitektur (SPAA) , halaman 367–369. ACM, 2017.
[Rob13] Lengkungan D. Robison. Desain berbasis kebijakan untuk pemusnahan yang aman dalam kontainer secara bersamaan. Makalah komite standar C++, 2013.
[Val95] John D.Valois. Struktur Data Bebas Kunci . Tesis PhD, Institut Politeknik Rensselaer, 1995.
[Vyu08] Dmitry Vyukov. Peta hash yang dapat diskalakan. Postingan Google Grup, 2008.
[Vyu10] Dmitry Vyukov. Antrean MPMC berbatas yang sederhana dan efisien. Postingan Google Grup, 2010.
Memperluas
Informasi Tambahan
Aplikasi Terkait
Direkomendasikan untuk Anda
Informasi Terkait Semua